buffers.c 25 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.
4
 * Copyright (c) 2007-2020, 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>
28
#include "lib/buf/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
#ifndef COCCI
103
104
105
#ifdef DISABLE_MEMORY_SENTINELS
#define CHUNK_SET_SENTINEL(chunk, alloclen) STMT_NIL
#else
106
107
108
109
110
111
#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)
112
#endif /* defined(DISABLE_MEMORY_SENTINELS) */
Nick Mathewson's avatar
Nick Mathewson committed
113
#endif /* !defined(COCCI) */
114
115
116

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

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

158
159
/** 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. */
160
static inline chunk_t *
161
162
chunk_grow(chunk_t *chunk, size_t sz)
{
163
  ptrdiff_t offset;
164
165
166
  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);
167
168
  tor_assert(sz > chunk->memlen);
  offset = chunk->data - chunk->mem;
169
  chunk = tor_realloc(chunk, new_alloc);
170
171
  chunk->memlen = sz;
  chunk->data = chunk->mem + offset;
172
#ifdef DEBUG_CHUNK_ALLOC
173
174
  tor_assert(chunk->DBG_alloc == orig_alloc);
  chunk->DBG_alloc = new_alloc;
175
#endif
176
177
  total_bytes_allocated_in_chunks += new_alloc - orig_alloc;
  CHUNK_SET_SENTINEL(chunk, new_alloc);
178
  return chunk;
179
180
}

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

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

201
202
203
/** 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>.
204
205
206
207
208
 *
 * 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.
209
 */
210
void
211
buf_pullup(buf_t *buf, size_t bytes, const char **head_out, size_t *len_out)
212
213
214
{
  chunk_t *dest, *src;
  size_t capacity;
215
216
217
  if (!buf->head) {
    *head_out = NULL;
    *len_out = 0;
218
    return;
219
  }
220

221
222
223
224
  check();
  if (buf->datalen < bytes)
    bytes = buf->datalen;

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

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

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

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

279
#ifdef TOR_UNIT_TESTS
280
281
282
283
284
285
286
287
/* 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 */
288
  if (!cp || sz <= 0 || sz >= INT_MAX) {
289
290
291
292
293
294
295
296
    return NULL;
  }

  tor_assert(sz < SSIZE_T_CEILING);

  /* Allocate a buffer */
  buf_t *buf = buf_new_with_capacity(sz);
  tor_assert(buf);
297
  buf_assert_ok(buf);
298
299
300
301
302
303
  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);
304
  buf_assert_ok(buf);
305
306
307
308
309
310
311
312
313
  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];
314
  buf_assert_ok(buf);
315
316
317
318
319
320
321
322
323
324
325

  /* 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;
}
326
#endif /* defined(TOR_UNIT_TESTS) */
327

328
/** Remove the first <b>n</b> bytes from buf. */
329
void
330
buf_drain(buf_t *buf, size_t n)
331
{
Roger Dingledine's avatar
Roger Dingledine committed
332
  tor_assert(buf->datalen >= n);
333
334
335
336
337
338
339
340
341
342
343
344
345
346
  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;
347
      buf_chunk_free_unchecked(victim);
348
    }
349
  }
350
  check();
351
352
}

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

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

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

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

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

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

411
412
413
414
/** 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)
415
{
416
417
418
419
  if (!buf->tail)
    return 0;
  else
    return CHUNK_REMAINING_CAPACITY(buf->tail);
420
421
}

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

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

434
435
436
437
438
/** 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));
439
  total_bytes_allocated_in_chunks += CHUNK_ALLOC_SIZE(in_chunk->memlen);
440
441
442
#ifdef DEBUG_CHUNK_ALLOC
  newch->DBG_alloc = CHUNK_ALLOC_SIZE(in_chunk->memlen);
#endif
443
444
  newch->next = NULL;
  if (in_chunk->data) {
445
    ptrdiff_t offset = in_chunk->data - in_chunk->mem;
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
    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;
}

471
472
473
/** 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. */
474
chunk_t *
475
buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped)
476
477
{
  chunk_t *chunk;
478

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

487
  chunk->inserted_time = monotime_coarse_get_stamp();
488

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

501
/** Return the age of the oldest chunk in the buffer <b>buf</b>, in
502
503
 * timestamp units.  Requires the current monotonic timestamp as its
 * input <b>now</b>.
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
 */
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
521
522
523
/** Append <b>string_len</b> bytes from <b>string</b> to the end of
 * <b>buf</b>.
 *
524
525
 * Return the new length of the buffer on success, -1 on failure.
 */
526
int
527
buf_add(buf_t *buf, const char *string, size_t string_len)
528
{
529
  if (!string_len)
530
    return (int)buf->datalen;
531
  check();
Roger Dingledine's avatar
Roger Dingledine committed
532

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

538
539
540
541
542
543
  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);
544
545
546
547
548
549
550
    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;
551
  }
552

553
  check();
554
555
  tor_assert(buf->datalen < INT_MAX);
  return (int)buf->datalen;
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
/** 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);
583
  tor_assert(tmp != NULL);
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
  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;
}

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

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

619
620
621
622
623
624
625
626
627
628
  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;
629
630
631
  }
}

632
633
634
/** 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.
635
 */
636
int
637
buf_get_bytes(buf_t *buf, char *string, size_t string_len)
638
639
640
641
642
643
{
  /* 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. */

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

652
653
/** 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.
654
655
656
 * Return the number of bytes actually copied.
 */
int
657
buf_move_to_buf(buf_t *buf_out, buf_t *buf_in, size_t *buf_flushlen)
658
{
659
  /* We can do way better here, but this doesn't turn up in any profiles. */
660
661
  char b[4096];
  size_t cp, len;
662

663
  if (BUG(buf_out->datalen >= INT_MAX || *buf_flushlen >= INT_MAX))
664
665
666
667
    return -1;
  if (BUG(buf_out->datalen >= INT_MAX - *buf_flushlen))
    return -1;

668
669
670
671
672
  len = *buf_flushlen;
  if (len > buf_in->datalen)
    len = buf_in->datalen;

  cp = len; /* Remember the number of bytes we intend to copy. */
673
  tor_assert(cp < INT_MAX);
674
675
676
677
678
  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;
679
680
    buf_get_bytes(buf_in, b, n);
    buf_add(buf_out, b, n);
681
682
683
    len -= n;
  }
  *buf_flushlen -= cp;
684
  return (int)cp;
685
686
}

687
688
689
690
691
692
693
694
/** 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;
695
696
  if (buf_datalen(buf_in) == 0)
    return;
697
698
699
700
  if (BUG(buf_out->datalen >= INT_MAX || buf_in->datalen >= INT_MAX))
    return;
  if (BUG(buf_out->datalen >= INT_MAX - buf_in->datalen))
    return;
701
702
703
704
705
706
707
708
709
710
711
712
713
714

  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;
}

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

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

732
733
734
/** 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. */
735
static ptrdiff_t
736
buf_find_pos_of_char(char ch, buf_pos_t *out)
737
{
738
  const chunk_t *chunk;
739
  ptrdiff_t pos;
740
  tor_assert(out);
741
  if (out->chunk) {
742
    if (out->chunk->datalen) {
743
      tor_assert(out->pos < (ptrdiff_t)out->chunk->datalen);
744
745
    } else {
      tor_assert(out->pos == 0);
746
747
    }
  }
748
  pos = out->pos;
749
  for (chunk = out->chunk; chunk; chunk = chunk->next) {
750
    char *cp = memchr(chunk->data+pos, ch, chunk->datalen - pos);
751
752
    if (cp) {
      out->chunk = chunk;
753
754
      tor_assert(cp - chunk->data < INT_MAX);
      out->pos = (int)(cp - chunk->data);
755
      return out->chunk_pos + out->pos;
756
    } else {
757
      out->chunk_pos += chunk->datalen;
758
759
760
761
762
763
      pos = 0;
    }
  }
  return -1;
}

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

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

790
  memcpy(&p, pos, sizeof(p));
791

792
  while (1) {
793
    char ch = p.chunk->data[p.pos];
794
795
796
    if (ch != *s)
      return 0;
    ++s;
797
798
799
800
801
    /* 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;
802
    if (buf_pos_inc(&p)<0)
803
804
805
806
      return 0;
  }
}

807
808
/** 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. */
809
int
810
buf_find_string_offset(const buf_t *buf, const char *s, size_t n)
811
812
813
{
  buf_pos_t pos;
  buf_pos_init(buf, &pos);
814
815
  while (buf_find_pos_of_char(*s, &pos) >= 0) {
    if (buf_matches_at_pos(&pos, s, n)) {
816
817
      tor_assert(pos.chunk_pos + pos.pos < INT_MAX);
      return (int)(pos.chunk_pos + pos.pos);
818
    } else {
819
      if (buf_pos_inc(&pos)<0)
820
821
822
823
824
825
        return -1;
    }
  }
  return -1;
}

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

843
844
/** 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. */
845
static ptrdiff_t
846
847
848
buf_find_offset_of_char(buf_t *buf, char ch)
{
  chunk_t *chunk;
849
  ptrdiff_t offset = 0;
850
  tor_assert(buf->datalen < INT_MAX);
851
852
853
854
855
856
857
858
859
860
  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;
}

861
862
863
864
865
866
/** 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>.
867
868
 */
int
869
buf_get_line(buf_t *buf, char *data_out, size_t *data_len)
870
871
{
  size_t sz;
872
  ptrdiff_t offset;
873

874
875
  if (!buf->head)
    return 0;
876
877
878

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

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

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

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