buffers.c 24.8 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
2
/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
Nick Mathewson's avatar
Nick Mathewson committed
3
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
Nick Mathewson's avatar
Nick Mathewson committed
4
 * Copyright (c) 2007-2019, The Tor Project, Inc. */
5
/* See LICENSE for licensing information */
Roger Dingledine's avatar
Roger Dingledine committed
6

7
8
/**
 * \file buffers.c
9
10
11
12
13
14
15
16
17
18
 * \brief Implements a generic buffer interface.
 *
 * A buf_t is a (fairly) opaque byte-oriented FIFO that can read to or flush
 * from memory, sockets, file descriptors, TLS connections, or another buf_t.
 * Buffers are implemented as linked lists of memory chunks.
 *
 * All socket-backed and TLS-based connection_t objects have a pair of
 * buffers: one for incoming data, and one for outcoming data.  These are fed
 * and drained from functions in connection.c, trigged by events that are
 * monitored in main.c.
19
20
21
22
 *
 * This module only handles the buffer implementation itself. To use a buffer
 * with the network, a compressor, or a TLS connection, see the other buffer_*
 * modules.
23
 **/
24

25
#define BUFFERS_PRIVATE
26
27
#include "orconfig.h"
#include <stddef.h>
Nick Mathewson's avatar
Nick Mathewson committed
28
#include "lib/container/buffers.h"
29
#include "lib/cc/torint.h"
30
#include "lib/log/log.h"
Nick Mathewson's avatar
Nick Mathewson committed
31
32
#include "lib/log/util_bug.h"
#include "lib/ctime/di_ops.h"
Nick Mathewson's avatar
Nick Mathewson committed
33
#include "lib/malloc/malloc.h"
Nick Mathewson's avatar
Nick Mathewson committed
34
35
36
#include "lib/string/printf.h"
#include "lib/time/compat_time.h"

37
38
39
40
#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif

Nick Mathewson's avatar
Nick Mathewson committed
41
42
43
#include <stdlib.h>
#include <string.h>

44
//#define PARANOIA
45

46
#ifdef PARANOIA
47
48
/** Helper: If PARANOIA is defined, assert that the buffer in local variable
 * <b>buf</b> is well-formed. */
49
#define check() STMT_BEGIN buf_assert_ok(buf); STMT_END
50
#else
51
#define check() STMT_NIL
52
#endif /* defined(PARANOIA) */
53

54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/* Implementation notes:
 *
 * After flirting with memmove, and dallying with ring-buffers, we're finally
 * getting up to speed with the 1970s and implementing buffers as a linked
 * list of small chunks.  Each buffer has such a list; data is removed from
 * the head of the list, and added at the tail.  The list is singly linked,
 * and the buffer keeps a pointer to the head and the tail.
 *
 * Every chunk, except the tail, contains at least one byte of data.  Data in
 * each chunk is contiguous.
 *
 * When you need to treat the first N characters on a buffer as a contiguous
 * string, use the buf_pullup function to make them so.  Don't do this more
 * than necessary.
 *
 * The major free Unix kernels have handled buffers like this since, like,
 * forever.
71
 */
72

73
74
/* Chunk manipulation functions */

Neel Chauhan's avatar
Neel Chauhan committed
75
#define CHUNK_HEADER_LEN offsetof(chunk_t, mem[0])
76

77
/* We leave this many NUL bytes at the end of the buffer. */
78
79
80
#ifdef DISABLE_MEMORY_SENTINELS
#define SENTINEL_LEN 0
#else
81
#define SENTINEL_LEN 4
82
#endif
83
84
85
86

/* Header size plus NUL bytes at the end */
#define CHUNK_OVERHEAD (CHUNK_HEADER_LEN + SENTINEL_LEN)

87
88
/** Return the number of bytes needed to allocate a chunk to hold
 * <b>memlen</b> bytes. */
89
#define CHUNK_ALLOC_SIZE(memlen) (CHUNK_OVERHEAD + (memlen))
90
91
/** Return the number of usable bytes in a chunk allocated with
 * malloc(<b>memlen</b>). */
92
93
94
95
#define CHUNK_SIZE_WITH_ALLOC(memlen) ((memlen) - CHUNK_OVERHEAD)

#define DEBUG_SENTINEL

96
#if defined(DEBUG_SENTINEL) && !defined(DISABLE_MEMORY_SENTINELS)
97
98
99
100
101
#define DBG_S(s) s
#else
#define DBG_S(s) (void)0
#endif

102
103
104
#ifdef DISABLE_MEMORY_SENTINELS
#define CHUNK_SET_SENTINEL(chunk, alloclen) STMT_NIL
#else
105
106
107
108
109
110
#define CHUNK_SET_SENTINEL(chunk, alloclen) do {                        \
    uint8_t *a = (uint8_t*) &(chunk)->mem[(chunk)->memlen];             \
    DBG_S(uint8_t *b = &((uint8_t*)(chunk))[(alloclen)-SENTINEL_LEN]);  \
    DBG_S(tor_assert(a == b));                                          \
    memset(a,0,SENTINEL_LEN);                                           \
  } while (0)
111
#endif /* defined(DISABLE_MEMORY_SENTINELS) */
112
113
114

/** Move all bytes stored in <b>chunk</b> to the front of <b>chunk</b>->mem,
 * to free up space at the end. */
115
static inline void
116
chunk_repack(chunk_t *chunk)
117
{
118
119
120
121
  if (chunk->datalen && chunk->data != &chunk->mem[0]) {
    memmove(chunk->mem, chunk->data, chunk->datalen);
  }
  chunk->data = &chunk->mem[0];
122
123
}

124
125
/** Keep track of total size of allocated chunks for consistency asserts */
static size_t total_bytes_allocated_in_chunks = 0;
126
static void
127
buf_chunk_free_unchecked(chunk_t *chunk)
128
{
129
130
  if (!chunk)
    return;
131
132
133
#ifdef DEBUG_CHUNK_ALLOC
  tor_assert(CHUNK_ALLOC_SIZE(chunk->memlen) == chunk->DBG_alloc);
#endif
134
135
  tor_assert(total_bytes_allocated_in_chunks >=
             CHUNK_ALLOC_SIZE(chunk->memlen));
136
  total_bytes_allocated_in_chunks -= CHUNK_ALLOC_SIZE(chunk->memlen);
137
138
  tor_free(chunk);
}
139
static inline chunk_t *
140
141
142
chunk_new_with_alloc_size(size_t alloc)
{
  chunk_t *ch;
Nick Mathewson's avatar
Nick Mathewson committed
143
  ch = tor_malloc(alloc);
144
145
  ch->next = NULL;
  ch->datalen = 0;
146
147
148
#ifdef DEBUG_CHUNK_ALLOC
  ch->DBG_alloc = alloc;
#endif
149
  ch->memlen = CHUNK_SIZE_WITH_ALLOC(alloc);
150
  total_bytes_allocated_in_chunks += alloc;
151
  ch->data = &ch->mem[0];
152
  CHUNK_SET_SENTINEL(ch, alloc);
153
154
  return ch;
}
155

156
157
/** Expand <b>chunk</b> until it can hold <b>sz</b> bytes, and return a
 * new pointer to <b>chunk</b>.  Old pointers are no longer valid. */
158
static inline chunk_t *
159
160
161
chunk_grow(chunk_t *chunk, size_t sz)
{
  off_t offset;
162
163
164
  const size_t memlen_orig = chunk->memlen;
  const size_t orig_alloc = CHUNK_ALLOC_SIZE(memlen_orig);
  const size_t new_alloc = CHUNK_ALLOC_SIZE(sz);
165
166
  tor_assert(sz > chunk->memlen);
  offset = chunk->data - chunk->mem;
167
  chunk = tor_realloc(chunk, new_alloc);
168
169
  chunk->memlen = sz;
  chunk->data = chunk->mem + offset;
170
#ifdef DEBUG_CHUNK_ALLOC
171
172
  tor_assert(chunk->DBG_alloc == orig_alloc);
  chunk->DBG_alloc = new_alloc;
173
#endif
174
175
  total_bytes_allocated_in_chunks += new_alloc - orig_alloc;
  CHUNK_SET_SENTINEL(chunk, new_alloc);
176
  return chunk;
177
178
}

179
180
/** Every chunk should take up at least this many bytes. */
#define MIN_CHUNK_ALLOC 256
181
/** No chunk should take up more than this many bytes. */
182
183
184
185
#define MAX_CHUNK_ALLOC 65536

/** Return the allocation size we'd like to use to hold <b>target</b>
 * bytes. */
186
187
size_t
buf_preferred_chunk_size(size_t target)
188
{
189
  tor_assert(target <= SIZE_T_CEILING - CHUNK_OVERHEAD);
190
191
  if (CHUNK_ALLOC_SIZE(target) >= MAX_CHUNK_ALLOC)
    return CHUNK_ALLOC_SIZE(target);
192
193
194
  size_t sz = MIN_CHUNK_ALLOC;
  while (CHUNK_SIZE_WITH_ALLOC(sz) < target) {
    sz <<= 1;
195
  }
196
  return sz;
197
198
}

199
200
201
/** Collapse data from the first N chunks from <b>buf</b> into buf->head,
 * growing it as necessary, until buf->head has the first <b>bytes</b> bytes
 * of data from the buffer, or until buf->head has all the data in <b>buf</b>.
202
203
204
205
206
 *
 * Set *<b>head_out</b> to point to the first byte of available data, and
 * *<b>len_out</b> to the number of bytes of data available at
 * *<b>head_out</b>. Note that *<b>len_out</b> may be more or less than
 * <b>bytes</b>, depending on the number of bytes available.
207
 */
208
void
209
buf_pullup(buf_t *buf, size_t bytes, const char **head_out, size_t *len_out)
210
211
212
{
  chunk_t *dest, *src;
  size_t capacity;
213
214
215
  if (!buf->head) {
    *head_out = NULL;
    *len_out = 0;
216
    return;
217
  }
218

219
220
221
222
  check();
  if (buf->datalen < bytes)
    bytes = buf->datalen;

223
  capacity = bytes;
224
225
226
  if (buf->head->datalen >= bytes) {
    *head_out = buf->head->data;
    *len_out = buf->head->datalen;
227
    return;
228
  }
229

230
231
  if (buf->head->memlen >= capacity) {
    /* We don't need to grow the first chunk, but we might need to repack it.*/
232
233
    size_t needed = capacity - buf->head->datalen;
    if (CHUNK_REMAINING_CAPACITY(buf->head) < needed)
234
      chunk_repack(buf->head);
235
    tor_assert(CHUNK_REMAINING_CAPACITY(buf->head) >= needed);
236
  } else {
237
238
239
240
    chunk_t *newhead;
    size_t newsize;
    /* We need to grow the chunk. */
    chunk_repack(buf->head);
241
    newsize = CHUNK_SIZE_WITH_ALLOC(buf_preferred_chunk_size(capacity));
242
243
244
245
246
247
    newhead = chunk_grow(buf->head, newsize);
    tor_assert(newhead->memlen >= capacity);
    if (newhead != buf->head) {
      if (buf->tail == buf->head)
        buf->tail = newhead;
      buf->head = newhead;
248
    }
249
250
  }

251
252
253
254
255
  dest = buf->head;
  while (dest->datalen < bytes) {
    size_t n = bytes - dest->datalen;
    src = dest->next;
    tor_assert(src);
256
    if (n >= src->datalen) {
257
258
259
260
261
      memcpy(CHUNK_WRITE_PTR(dest), src->data, src->datalen);
      dest->datalen += src->datalen;
      dest->next = src->next;
      if (buf->tail == src)
        buf->tail = dest;
262
      buf_chunk_free_unchecked(src);
263
264
265
266
267
268
269
    } else {
      memcpy(CHUNK_WRITE_PTR(dest), src->data, n);
      dest->datalen += n;
      src->data += n;
      src->datalen -= n;
      tor_assert(dest->datalen == bytes);
    }
270
  }
271
272

  check();
273
274
  *head_out = buf->head->data;
  *len_out = buf->head->datalen;
275
276
}

277
#ifdef TOR_UNIT_TESTS
278
279
280
281
282
283
284
285
/* Write sz bytes from cp into a newly allocated buffer buf.
 * Returns NULL when passed a NULL cp or zero sz.
 * Asserts on failure: only for use in unit tests.
 * buf must be freed using buf_free(). */
buf_t *
buf_new_with_data(const char *cp, size_t sz)
{
  /* Validate arguments */
286
  if (!cp || sz <= 0 || sz >= INT_MAX) {
287
288
289
290
291
292
293
294
    return NULL;
  }

  tor_assert(sz < SSIZE_T_CEILING);

  /* Allocate a buffer */
  buf_t *buf = buf_new_with_capacity(sz);
  tor_assert(buf);
295
  buf_assert_ok(buf);
296
297
298
299
300
301
  tor_assert(!buf->head);

  /* Allocate a chunk that is sz bytes long */
  buf->head = chunk_new_with_alloc_size(CHUNK_ALLOC_SIZE(sz));
  buf->tail = buf->head;
  tor_assert(buf->head);
302
  buf_assert_ok(buf);
303
304
305
306
307
308
309
310
311
  tor_assert(buf_allocation(buf) >= sz);

  /* Copy the data and size the buffers */
  tor_assert(sz <= buf_slack(buf));
  tor_assert(sz <= CHUNK_REMAINING_CAPACITY(buf->head));
  memcpy(&buf->head->mem[0], cp, sz);
  buf->datalen = sz;
  buf->head->datalen = sz;
  buf->head->data = &buf->head->mem[0];
312
  buf_assert_ok(buf);
313
314
315
316
317
318
319
320
321
322
323

  /* Make sure everything is large enough */
  tor_assert(buf_allocation(buf) >= sz);
  tor_assert(buf_allocation(buf) >= buf_datalen(buf) + buf_slack(buf));
  /* Does the buffer implementation allocate more than the requested size?
   * (for example, by rounding up). If so, these checks will fail. */
  tor_assert(buf_datalen(buf) == sz);
  tor_assert(buf_slack(buf) == 0);

  return buf;
}
324
#endif /* defined(TOR_UNIT_TESTS) */
325

326
/** Remove the first <b>n</b> bytes from buf. */
327
void
328
buf_drain(buf_t *buf, size_t n)
329
{
Roger Dingledine's avatar
Roger Dingledine committed
330
  tor_assert(buf->datalen >= n);
331
332
333
334
335
336
337
338
339
340
341
342
343
344
  while (n) {
    tor_assert(buf->head);
    if (buf->head->datalen > n) {
      buf->head->datalen -= n;
      buf->head->data += n;
      buf->datalen -= n;
      return;
    } else {
      chunk_t *victim = buf->head;
      n -= victim->datalen;
      buf->datalen -= victim->datalen;
      buf->head = victim->next;
      if (buf->tail == victim)
        buf->tail = NULL;
345
      buf_chunk_free_unchecked(victim);
346
    }
347
  }
348
  check();
349
350
}

351
352
/** Create and return a new buf with default chunk capacity <b>size</b>.
 */
353
buf_t *
354
355
buf_new_with_capacity(size_t size)
{
356
  buf_t *b = buf_new();
357
  b->default_chunk_size = buf_preferred_chunk_size(size);
358
  return b;
359
}
Roger Dingledine's avatar
Roger Dingledine committed
360

361
/** Allocate and return a new buffer with default capacity. */
362
363
buf_t *
buf_new(void)
364
{
365
366
367
368
  buf_t *buf = tor_malloc_zero(sizeof(buf_t));
  buf->magic = BUFFER_MAGIC;
  buf->default_chunk_size = 4096;
  return buf;
369
}
Roger Dingledine's avatar
Roger Dingledine committed
370

371
372
373
374
375
376
size_t
buf_get_default_chunk_size(const buf_t *buf)
{
  return buf->default_chunk_size;
}

377
/** Remove all data from <b>buf</b>. */
378
379
void
buf_clear(buf_t *buf)
380
{
381
  chunk_t *chunk, *next;
382
  buf->datalen = 0;
383
384
  for (chunk = buf->head; chunk; chunk = next) {
    next = chunk->next;
385
    buf_chunk_free_unchecked(chunk);
386
387
  }
  buf->head = buf->tail = NULL;
388
}
Roger Dingledine's avatar
Roger Dingledine committed
389

Roger Dingledine's avatar
Roger Dingledine committed
390
/** Return the number of bytes stored in <b>buf</b> */
Andrea Shepard's avatar
Andrea Shepard committed
391
392
MOCK_IMPL(size_t,
buf_datalen, (const buf_t *buf))
393
394
{
  return buf->datalen;
Roger Dingledine's avatar
Roger Dingledine committed
395
396
}

397
/** Return the total length of all chunks used in <b>buf</b>. */
398
size_t
399
buf_allocation(const buf_t *buf)
400
{
401
402
403
  size_t total = 0;
  const chunk_t *chunk;
  for (chunk = buf->head; chunk; chunk = chunk->next) {
404
    total += CHUNK_ALLOC_SIZE(chunk->memlen);
405
406
  }
  return total;
407
408
}

409
410
411
412
/** Return the number of bytes that can be added to <b>buf</b> without
 * performing any additional allocation. */
size_t
buf_slack(const buf_t *buf)
413
{
414
415
416
417
  if (!buf->tail)
    return 0;
  else
    return CHUNK_REMAINING_CAPACITY(buf->tail);
418
419
}

420
/** Release storage held by <b>buf</b>. */
421
void
422
buf_free_(buf_t *buf)
423
{
424
425
  if (!buf)
    return;
426

427
428
429
430
431
  buf_clear(buf);
  buf->magic = 0xdeadbeef;
  tor_free(buf);
}

432
433
434
435
436
/** Return a new copy of <b>in_chunk</b> */
static chunk_t *
chunk_copy(const chunk_t *in_chunk)
{
  chunk_t *newch = tor_memdup(in_chunk, CHUNK_ALLOC_SIZE(in_chunk->memlen));
437
  total_bytes_allocated_in_chunks += CHUNK_ALLOC_SIZE(in_chunk->memlen);
438
439
440
#ifdef DEBUG_CHUNK_ALLOC
  newch->DBG_alloc = CHUNK_ALLOC_SIZE(in_chunk->memlen);
#endif
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
  newch->next = NULL;
  if (in_chunk->data) {
    off_t offset = in_chunk->data - in_chunk->mem;
    newch->data = newch->mem + offset;
  }
  return newch;
}

/** Return a new copy of <b>buf</b> */
buf_t *
buf_copy(const buf_t *buf)
{
  chunk_t *ch;
  buf_t *out = buf_new();
  out->default_chunk_size = buf->default_chunk_size;
  for (ch = buf->head; ch; ch = ch->next) {
    chunk_t *newch = chunk_copy(ch);
    if (out->tail) {
      out->tail->next = newch;
      out->tail = newch;
    } else {
      out->head = out->tail = newch;
    }
  }
  out->datalen = buf->datalen;
  return out;
}

469
470
471
/** Append a new chunk with enough capacity to hold <b>capacity</b> bytes to
 * the tail of <b>buf</b>.  If <b>capped</b>, don't allocate a chunk bigger
 * than MAX_CHUNK_ALLOC. */
472
chunk_t *
473
buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped)
474
475
{
  chunk_t *chunk;
476

477
  if (CHUNK_ALLOC_SIZE(capacity) < buf->default_chunk_size) {
478
    chunk = chunk_new_with_alloc_size(buf->default_chunk_size);
479
480
  } else if (capped && CHUNK_ALLOC_SIZE(capacity) > MAX_CHUNK_ALLOC) {
    chunk = chunk_new_with_alloc_size(MAX_CHUNK_ALLOC);
481
  } else {
482
    chunk = chunk_new_with_alloc_size(buf_preferred_chunk_size(capacity));
483
  }
484

485
  chunk->inserted_time = monotime_coarse_get_stamp();
486

487
488
489
490
491
492
493
  if (buf->tail) {
    tor_assert(buf->head);
    buf->tail->next = chunk;
    buf->tail = chunk;
  } else {
    tor_assert(!buf->head);
    buf->head = buf->tail = chunk;
494
  }
495
496
  check();
  return chunk;
Roger Dingledine's avatar
Roger Dingledine committed
497
498
}

499
/** Return the age of the oldest chunk in the buffer <b>buf</b>, in
500
501
 * timestamp units.  Requires the current monotonic timestamp as its
 * input <b>now</b>.
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
 */
uint32_t
buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now)
{
  if (buf->head) {
    return now - buf->head->inserted_time;
  } else {
    return 0;
  }
}

size_t
buf_get_total_allocation(void)
{
  return total_bytes_allocated_in_chunks;
}

Roger Dingledine's avatar
Roger Dingledine committed
519
520
521
/** Append <b>string_len</b> bytes from <b>string</b> to the end of
 * <b>buf</b>.
 *
522
523
 * Return the new length of the buffer on success, -1 on failure.
 */
524
int
525
buf_add(buf_t *buf, const char *string, size_t string_len)
526
{
527
  if (!string_len)
528
    return (int)buf->datalen;
529
  check();
Roger Dingledine's avatar
Roger Dingledine committed
530

531
532
533
534
535
  if (BUG(buf->datalen >= INT_MAX))
    return -1;
  if (BUG(buf->datalen >= INT_MAX - string_len))
    return -1;

536
537
538
539
540
541
  while (string_len) {
    size_t copy;
    if (!buf->tail || !CHUNK_REMAINING_CAPACITY(buf->tail))
      buf_add_chunk_with_capacity(buf, string_len, 1);

    copy = CHUNK_REMAINING_CAPACITY(buf->tail);
542
543
544
545
546
547
548
    if (copy > string_len)
      copy = string_len;
    memcpy(CHUNK_WRITE_PTR(buf->tail), string, copy);
    string_len -= copy;
    string += copy;
    buf->datalen += copy;
    buf->tail->datalen += copy;
549
  }
550

551
  check();
552
553
  tor_assert(buf->datalen < INT_MAX);
  return (int)buf->datalen;
554
555
}

556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
/** Add a nul-terminated <b>string</b> to <b>buf</b>, not including the
 * terminating NUL. */
void
buf_add_string(buf_t *buf, const char *string)
{
  buf_add(buf, string, strlen(string));
}

/** As tor_snprintf, but write the results into a buf_t */
void
buf_add_printf(buf_t *buf, const char *format, ...)
{
  va_list ap;
  va_start(ap,format);
  buf_add_vprintf(buf, format, ap);
  va_end(ap);
}

/** As tor_vsnprintf, but write the results into a buf_t. */
void
buf_add_vprintf(buf_t *buf, const char *format, va_list args)
{
  /* XXXX Faster implementations are easy enough, but let's optimize later */
  char *tmp;
  tor_vasprintf(&tmp, format, args);
  buf_add(buf, tmp, strlen(tmp));
  tor_free(tmp);
}

/** Return a heap-allocated string containing the contents of <b>buf</b>, plus
 * a NUL byte. If <b>sz_out</b> is provided, set *<b>sz_out</b> to the length
 * of the returned string, not including the terminating NUL. */
char *
buf_extract(buf_t *buf, size_t *sz_out)
{
  tor_assert(buf);

  size_t sz = buf_datalen(buf);
  char *result;
  result = tor_malloc(sz+1);
  buf_peek(buf, result, sz);
  result[sz] = 0;
  if (sz_out)
    *sz_out = sz;
  return result;
}

603
604
/** Helper: copy the first <b>string_len</b> bytes from <b>buf</b>
 * onto <b>string</b>.
605
 */
606
void
607
buf_peek(const buf_t *buf, char *string, size_t string_len)
608
{
609
  chunk_t *chunk;
Roger Dingledine's avatar
Roger Dingledine committed
610

Roger Dingledine's avatar
Roger Dingledine committed
611
  tor_assert(string);
612
613
  /* make sure we don't ask for too much */
  tor_assert(string_len <= buf->datalen);
614
  /* buf_assert_ok(buf); */
Roger Dingledine's avatar
Roger Dingledine committed
615

616
617
618
619
620
621
622
623
624
625
  chunk = buf->head;
  while (string_len) {
    size_t copy = string_len;
    tor_assert(chunk);
    if (chunk->datalen < copy)
      copy = chunk->datalen;
    memcpy(string, chunk->data, copy);
    string_len -= copy;
    string += copy;
    chunk = chunk->next;
626
627
628
  }
}

629
630
631
/** Remove <b>string_len</b> bytes from the front of <b>buf</b>, and store
 * them into <b>string</b>.  Return the new buffer size.  <b>string_len</b>
 * must be \<= the number of bytes on the buffer.
632
 */
633
int
634
buf_get_bytes(buf_t *buf, char *string, size_t string_len)
635
636
637
638
639
640
{
  /* There must be string_len bytes in buf; write them onto string,
   * then memmove buf back (that is, remove them from buf).
   *
   * Return the number of bytes still on the buffer. */

641
  check();
642
  buf_peek(buf, string, string_len);
643
  buf_drain(buf, string_len);
644
  check();
645
646
  tor_assert(buf->datalen < INT_MAX);
  return (int)buf->datalen;
Roger Dingledine's avatar
Roger Dingledine committed
647
648
}

649
650
/** Move up to *<b>buf_flushlen</b> bytes from <b>buf_in</b> to
 * <b>buf_out</b>, and modify *<b>buf_flushlen</b> appropriately.
651
652
653
 * Return the number of bytes actually copied.
 */
int
654
buf_move_to_buf(buf_t *buf_out, buf_t *buf_in, size_t *buf_flushlen)
655
{
656
  /* We can do way better here, but this doesn't turn up in any profiles. */
657
658
  char b[4096];
  size_t cp, len;
659

660
  if (BUG(buf_out->datalen >= INT_MAX || *buf_flushlen >= INT_MAX))
661
662
663
664
    return -1;
  if (BUG(buf_out->datalen >= INT_MAX - *buf_flushlen))
    return -1;

665
666
667
668
669
  len = *buf_flushlen;
  if (len > buf_in->datalen)
    len = buf_in->datalen;

  cp = len; /* Remember the number of bytes we intend to copy. */
670
  tor_assert(cp < INT_MAX);
671
672
673
674
675
  while (len) {
    /* This isn't the most efficient implementation one could imagine, since
     * it does two copies instead of 1, but I kinda doubt that this will be
     * critical path. */
    size_t n = len > sizeof(b) ? sizeof(b) : len;
676
677
    buf_get_bytes(buf_in, b, n);
    buf_add(buf_out, b, n);
678
679
680
    len -= n;
  }
  *buf_flushlen -= cp;
681
  return (int)cp;
682
683
}

684
685
686
687
688
689
690
691
/** Moves all data from <b>buf_in</b> to <b>buf_out</b>, without copying.
 */
void
buf_move_all(buf_t *buf_out, buf_t *buf_in)
{
  tor_assert(buf_out);
  if (!buf_in)
    return;
692
693
  if (buf_datalen(buf_in) == 0)
    return;
694
695
696
697
  if (BUG(buf_out->datalen >= INT_MAX || buf_in->datalen >= INT_MAX))
    return;
  if (BUG(buf_out->datalen >= INT_MAX - buf_in->datalen))
    return;
698
699
700
701
702
703
704
705
706
707
708
709
710
711

  if (buf_out->head == NULL) {
    buf_out->head = buf_in->head;
    buf_out->tail = buf_in->tail;
  } else {
    buf_out->tail->next = buf_in->head;
    buf_out->tail = buf_in->tail;
  }

  buf_out->datalen += buf_in->datalen;
  buf_in->head = buf_in->tail = NULL;
  buf_in->datalen = 0;
}

712
/** Internal structure: represents a position in a buffer. */
713
typedef struct buf_pos_t {
714
  const chunk_t *chunk; /**< Which chunk are we pointing to? */
715
  int pos;/**< Which character inside the chunk's data are we pointing to? */
716
  size_t chunk_pos; /**< Total length of all previous chunks. */
717
} buf_pos_t;
718

719
/** Initialize <b>out</b> to point to the first character of <b>buf</b>.*/
720
static void
721
buf_pos_init(const buf_t *buf, buf_pos_t *out)
722
723
724
{
  out->chunk = buf->head;
  out->pos = 0;
725
  out->chunk_pos = 0;
726
727
}

728
729
730
/** Advance <b>out</b> to the first appearance of <b>ch</b> at the current
 * position of <b>out</b>, or later.  Return -1 if no instances are found;
 * otherwise returns the absolute position of the character. */
731
static off_t
732
buf_find_pos_of_char(char ch, buf_pos_t *out)
733
{
734
  const chunk_t *chunk;
735
  int pos;
736
  tor_assert(out);
737
  if (out->chunk) {
738
739
740
741
    if (out->chunk->datalen) {
      tor_assert(out->pos < (off_t)out->chunk->datalen);
    } else {
      tor_assert(out->pos == 0);
742
743
    }
  }
744
  pos = out->pos;
745
  for (chunk = out->chunk; chunk; chunk = chunk->next) {
746
    char *cp = memchr(chunk->data+pos, ch, chunk->datalen - pos);
747
748
    if (cp) {
      out->chunk = chunk;
749
750
      tor_assert(cp - chunk->data < INT_MAX);
      out->pos = (int)(cp - chunk->data);
751
      return out->chunk_pos + out->pos;
752
    } else {
753
      out->chunk_pos += chunk->datalen;
754
755
756
757
758
759
      pos = 0;
    }
  }
  return -1;
}

760
/** Advance <b>pos</b> by a single character, if there are any more characters
Nick Mathewson's avatar
Nick Mathewson committed
761
 * in the buffer.  Returns 0 on success, -1 on failure. */
762
static inline int
763
764
buf_pos_inc(buf_pos_t *pos)
{
765
  tor_assert(pos->pos < INT_MAX - 1);
766
  ++pos->pos;
767
  if (pos->pos == (off_t)pos->chunk->datalen) {
768
769
    if (!pos->chunk->next)
      return -1;
770
    pos->chunk_pos += pos->chunk->datalen;
771
772
773
    pos->chunk = pos->chunk->next;
    pos->pos = 0;
  }
774
  return 0;
775
776
}

777
778
/** Return true iff the <b>n</b>-character string in <b>s</b> appears
 * (verbatim) at <b>pos</b>. */
779
static int
780
buf_matches_at_pos(const buf_pos_t *pos, const char *s, size_t n)
781
782
{
  buf_pos_t p;
783
784
785
  if (!n)
    return 1;

786
  memcpy(&p, pos, sizeof(p));
787

788
  while (1) {
789
    char ch = p.chunk->data[p.pos];
790
791
792
    if (ch != *s)
      return 0;
    ++s;
793
794
795
796
797
    /* If we're out of characters that don't match, we match.  Check this
     * _before_ we test incrementing pos, in case we're at the end of the
     * string. */
    if (--n == 0)
      return 1;
798
    if (buf_pos_inc(&p)<0)
799
800
801
802
      return 0;
  }
}

803
804
/** Return the first position in <b>buf</b> at which the <b>n</b>-character
 * string <b>s</b> occurs, or -1 if it does not occur. */
805
int
806
buf_find_string_offset(const buf_t *buf, const char *s, size_t n)
807
808
809
{
  buf_pos_t pos;
  buf_pos_init(buf, &pos);
810
811
  while (buf_find_pos_of_char(*s, &pos) >= 0) {
    if (buf_matches_at_pos(&pos, s, n)) {
812
813
      tor_assert(pos.chunk_pos + pos.pos < INT_MAX);
      return (int)(pos.chunk_pos + pos.pos);
814
    } else {
815
      if (buf_pos_inc(&pos)<0)
816
817
818
819
820
821
        return -1;
    }
  }
  return -1;
}

822
/** Return 1 iff <b>buf</b> starts with <b>cmd</b>. <b>cmd</b> must be a null
823
 * terminated string, of no more than PEEK_BUF_STARTSWITH_MAX bytes. */
824
int
825
buf_peek_startswith(const buf_t *buf, const char *cmd)
826
{
827
  char tmp[PEEK_BUF_STARTSWITH_MAX];
Nick Mathewson's avatar
Nick Mathewson committed
828
  size_t clen = strlen(cmd);
829
830
  if (clen == 0)
    return 1;
831
832
833
834
  if (BUG(clen > sizeof(tmp)))
    return 0;
  if (buf->datalen < clen)
    return 0;
835
  buf_peek(buf, tmp, clen);
836
  return fast_memeq(tmp, cmd, clen);
837
838
}

839
840
/** Return the index within <b>buf</b> at which <b>ch</b> first appears,
 * or -1 if <b>ch</b> does not appear on buf. */
841
static off_t
842
843
844
buf_find_offset_of_char(buf_t *buf, char ch)
{
  chunk_t *chunk;
845
  off_t offset = 0;
846
  tor_assert(buf->datalen < INT_MAX);
847
848
849
850
851
852
853
854
855
856
  for (chunk = buf->head; chunk; chunk = chunk->next) {
    char *cp = memchr(chunk->data, ch, chunk->datalen);
    if (cp)
      return offset + (cp - chunk->data);
    else
      offset += chunk->datalen;
  }
  return -1;
}

857
858
859
860
861
862
/** Try to read a single LF-terminated line from <b>buf</b>, and write it
 * (including the LF), NUL-terminated, into the *<b>data_len</b> byte buffer
 * at <b>data_out</b>.  Set *<b>data_len</b> to the number of bytes in the
 * line, not counting the terminating NUL.  Return 1 if we read a whole line,
 * return 0 if we don't have a whole line yet, and return -1 if the line
 * length exceeds *<b>data_len</b>.
863
864
 */
int
865
buf_get_line(buf_t *buf, char *data_out, size_t *data_len)
866
867
{
  size_t sz;
868
  off_t offset;
869

870
871
  if (!buf->head)
    return 0;
872
873
874

  offset = buf_find_offset_of_char(buf, '\n');
  if (offset < 0)
875
    return 0;
876
  sz = (size_t) offset;
877
  if (sz+2 > *data_len) {
878
    *data_len = sz + 2;
879
880
    return -1;
  }
881
  buf_get_bytes(buf, data_out, sz+1);
882
883
884
885
886
  data_out[sz+1] = '\0';
  *data_len = sz+1;
  return 1;
}

887
888
/** Set *<b>output</b> to contain a copy of the data in *<b>input</b> */
int
889
890
buf_set_to_copy(buf_t **output,
                const buf_t *input)
891
892
893
894
895
896
897
{
  if (*output)
    buf_free(*output);
  *output = buf_copy(input);
  return 0;
}

Roger Dingledine's avatar
Roger Dingledine committed
898
/** Log an error and exit if <b>buf</b> is corrupted.
899
 */
900
void
901
buf_assert_ok(buf_t *buf)
902
{
Roger Dingledine's avatar
Roger Dingledine committed
903
904
  tor_assert(buf);
  tor_assert(buf->magic == BUFFER_MAGIC);
905

906
907
908
  if (! buf->head) {
    tor_assert(!buf->tail);
    tor_assert(buf->datalen == 0);
909
  } else {
910
911
912
913
914
915
    chunk_t *ch;
    size_t total = 0;
    tor_assert(buf->tail);
    for (ch = buf->head; ch; ch = ch->next) {
      total += ch->datalen;
      tor_assert(ch->datalen <= ch->memlen);
916
      tor_assert(ch->datalen < INT_MAX);
917
      tor_assert(ch->data >= &ch->mem[0]);
918
919
      tor_assert(ch->data <= &ch->mem[0]+ch->memlen);
      if (ch->data == &ch->mem[0]+ch->memlen) {
920
        /* LCOV_EXCL_START */
921
922
923
924
925
        static int warned = 0;
        if (! warned) {
          log_warn(LD_BUG, "Invariant violation in buf.c related to #15083");
          warned = 1;
        }
926
        /* LCOV_EXCL_STOP */
927
      }
928
929
930
931
932
      tor_assert(ch->data+ch->datalen <= &ch->mem[0] + ch->memlen);
      if (!ch->next)
        tor_assert(ch == buf->tail);
    }
    tor_assert(buf->datalen == total);
933
  }
934
}