Tor  0.4.7.0-alpha-dev
buffers.c
Go to the documentation of this file.
1 /* Copyright (c) 2001 Matej Pfajfar.
2  * Copyright (c) 2001-2004, Roger Dingledine.
3  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4  * Copyright (c) 2007-2021, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
7 /**
8  * \file buffers.c
9  * \brief Implements a generic buffer interface.
10  *
11  * A buf_t is a (fairly) opaque byte-oriented FIFO that can read to or flush
12  * from memory, sockets, file descriptors, TLS connections, or another buf_t.
13  * Buffers are implemented as linked lists of memory chunks.
14  *
15  * All socket-backed and TLS-based connection_t objects have a pair of
16  * buffers: one for incoming data, and one for outcoming data. These are fed
17  * and drained from functions in connection.c, triggered by events that are
18  * monitored in main.c.
19  *
20  * This module only handles the buffer implementation itself. To use a buffer
21  * with the network, a compressor, or a TLS connection, see the other buffer_*
22  * modules.
23  **/
24 
25 #define BUFFERS_PRIVATE
26 #include "orconfig.h"
27 #include <stddef.h>
28 #include "lib/buf/buffers.h"
29 #include "lib/cc/torint.h"
30 #include "lib/log/log.h"
31 #include "lib/log/util_bug.h"
32 #include "lib/ctime/di_ops.h"
33 #include "lib/malloc/malloc.h"
34 #include "lib/string/printf.h"
35 #include "lib/time/compat_time.h"
36 
37 #ifdef HAVE_UNISTD_H
38 #include <unistd.h>
39 #endif
40 
41 #include <stdlib.h>
42 #include <string.h>
43 
44 //#define PARANOIA
45 
46 #ifdef PARANOIA
47 /** Helper: If PARANOIA is defined, assert that the buffer in local variable
48  * <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 /* Implementation notes:
55  *
56  * After flirting with memmove, and dallying with ring-buffers, we're finally
57  * getting up to speed with the 1970s and implementing buffers as a linked
58  * list of small chunks. Each buffer has such a list; data is removed from
59  * the head of the list, and added at the tail. The list is singly linked,
60  * and the buffer keeps a pointer to the head and the tail.
61  *
62  * Every chunk, except the tail, contains at least one byte of data. Data in
63  * each chunk is contiguous.
64  *
65  * When you need to treat the first N characters on a buffer as a contiguous
66  * string, use the buf_pullup function to make them so. Don't do this more
67  * than necessary.
68  *
69  * The major free Unix kernels have handled buffers like this since, like,
70  * forever.
71  */
72 
73 /* Chunk manipulation functions */
74 
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 #ifdef DISABLE_MEMORY_SENTINELS
79 #define SENTINEL_LEN 0
80 #else
81 #define SENTINEL_LEN 4
82 #endif
83 
84 /* Header size plus NUL bytes at the end */
85 #define CHUNK_OVERHEAD (CHUNK_HEADER_LEN + SENTINEL_LEN)
86 
87 /** Return the number of bytes needed to allocate a chunk to hold
88  * <b>memlen</b> bytes. */
89 #define CHUNK_ALLOC_SIZE(memlen) (CHUNK_OVERHEAD + (memlen))
90 /** Return the number of usable bytes in a chunk allocated with
91  * malloc(<b>memlen</b>). */
92 #define CHUNK_SIZE_WITH_ALLOC(memlen) ((memlen) - CHUNK_OVERHEAD)
93 
94 #define DEBUG_SENTINEL
95 
96 #if defined(DEBUG_SENTINEL) && !defined(DISABLE_MEMORY_SENTINELS)
97 #define DBG_S(s) s
98 #else
99 #define DBG_S(s) (void)0
100 #endif
101 
102 #ifndef COCCI
103 #ifdef DISABLE_MEMORY_SENTINELS
104 #define CHUNK_SET_SENTINEL(chunk, alloclen) STMT_NIL
105 #else
106 #define CHUNK_SET_SENTINEL(chunk, alloclen) do { \
107  uint8_t *a = (uint8_t*) &(chunk)->mem[(chunk)->memlen]; \
108  DBG_S(uint8_t *b = &((uint8_t*)(chunk))[(alloclen)-SENTINEL_LEN]); \
109  DBG_S(tor_assert(a == b)); \
110  memset(a,0,SENTINEL_LEN); \
111  } while (0)
112 #endif /* defined(DISABLE_MEMORY_SENTINELS) */
113 #endif /* !defined(COCCI) */
114 
115 /** Move all bytes stored in <b>chunk</b> to the front of <b>chunk</b>->mem,
116  * to free up space at the end. */
117 static inline void
118 chunk_repack(chunk_t *chunk)
119 {
120  if (chunk->datalen && chunk->data != &chunk->mem[0]) {
121  memmove(chunk->mem, chunk->data, chunk->datalen);
122  }
123  chunk->data = &chunk->mem[0];
124 }
125 
126 /** Keep track of total size of allocated chunks for consistency asserts */
128 static void
129 buf_chunk_free_unchecked(chunk_t *chunk)
130 {
131  if (!chunk)
132  return;
133 #ifdef DEBUG_CHUNK_ALLOC
134  tor_assert(CHUNK_ALLOC_SIZE(chunk->memlen) == chunk->DBG_alloc);
135 #endif
137  CHUNK_ALLOC_SIZE(chunk->memlen));
139  tor_free(chunk);
140 }
141 static inline chunk_t *
142 chunk_new_with_alloc_size(size_t alloc)
143 {
144  chunk_t *ch;
145  ch = tor_malloc(alloc);
146  ch->next = NULL;
147  ch->datalen = 0;
148 #ifdef DEBUG_CHUNK_ALLOC
149  ch->DBG_alloc = alloc;
150 #endif
151  ch->memlen = CHUNK_SIZE_WITH_ALLOC(alloc);
153  ch->data = &ch->mem[0];
154  CHUNK_SET_SENTINEL(ch, alloc);
155  return ch;
156 }
157 
158 /** Expand <b>chunk</b> until it can hold <b>sz</b> bytes, and return a
159  * new pointer to <b>chunk</b>. Old pointers are no longer valid. */
160 static inline chunk_t *
161 chunk_grow(chunk_t *chunk, size_t sz)
162 {
163  ptrdiff_t offset;
164  const size_t memlen_orig = chunk->memlen;
165  const size_t orig_alloc = CHUNK_ALLOC_SIZE(memlen_orig);
166  const size_t new_alloc = CHUNK_ALLOC_SIZE(sz);
167  tor_assert(sz > chunk->memlen);
168  offset = chunk->data - chunk->mem;
169  chunk = tor_realloc(chunk, new_alloc);
170  chunk->memlen = sz;
171  chunk->data = chunk->mem + offset;
172 #ifdef DEBUG_CHUNK_ALLOC
173  tor_assert(chunk->DBG_alloc == orig_alloc);
174  chunk->DBG_alloc = new_alloc;
175 #endif
176  total_bytes_allocated_in_chunks += new_alloc - orig_alloc;
177  CHUNK_SET_SENTINEL(chunk, new_alloc);
178  return chunk;
179 }
180 
181 /** Every chunk should take up at least this many bytes. */
182 #define MIN_CHUNK_ALLOC 256
183 /** No chunk should take up more than this many bytes. */
184 #define MAX_CHUNK_ALLOC 65536
185 
186 /** Return the allocation size we'd like to use to hold <b>target</b>
187  * bytes. */
188 size_t
190 {
191  tor_assert(target <= SIZE_T_CEILING - CHUNK_OVERHEAD);
192  if (CHUNK_ALLOC_SIZE(target) >= MAX_CHUNK_ALLOC)
193  return CHUNK_ALLOC_SIZE(target);
194  size_t sz = MIN_CHUNK_ALLOC;
195  while (CHUNK_SIZE_WITH_ALLOC(sz) < target) {
196  sz <<= 1;
197  }
198  return sz;
199 }
200 
201 /** Collapse data from the first N chunks from <b>buf</b> into buf->head,
202  * growing it as necessary, until buf->head has the first <b>bytes</b> bytes
203  * of data from the buffer, or until buf->head has all the data in <b>buf</b>.
204  *
205  * Set *<b>head_out</b> to point to the first byte of available data, and
206  * *<b>len_out</b> to the number of bytes of data available at
207  * *<b>head_out</b>. Note that *<b>len_out</b> may be more or less than
208  * <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  chunk_t *dest, *src;
214  size_t capacity;
215  if (!buf->head) {
216  *head_out = NULL;
217  *len_out = 0;
218  return;
219  }
220 
221  check();
222  if (buf->datalen < bytes)
223  bytes = buf->datalen;
224 
225  capacity = bytes;
226  if (buf->head->datalen >= bytes) {
227  *head_out = buf->head->data;
228  *len_out = buf->head->datalen;
229  return;
230  }
231 
232  if (buf->head->memlen >= capacity) {
233  /* We don't need to grow the first chunk, but we might need to repack it.*/
234  size_t needed = capacity - buf->head->datalen;
235  if (CHUNK_REMAINING_CAPACITY(buf->head) < needed)
236  chunk_repack(buf->head);
237  tor_assert(CHUNK_REMAINING_CAPACITY(buf->head) >= needed);
238  } else {
239  chunk_t *newhead;
240  size_t newsize;
241  /* We need to grow the chunk. */
242  chunk_repack(buf->head);
243  newsize = CHUNK_SIZE_WITH_ALLOC(buf_preferred_chunk_size(capacity));
244  newhead = chunk_grow(buf->head, newsize);
245  tor_assert(newhead->memlen >= capacity);
246  if (newhead != buf->head) {
247  if (buf->tail == buf->head)
248  buf->tail = newhead;
249  buf->head = newhead;
250  }
251  }
252 
253  dest = buf->head;
254  while (dest->datalen < bytes) {
255  size_t n = bytes - dest->datalen;
256  src = dest->next;
257  tor_assert(src);
258  if (n >= src->datalen) {
259  memcpy(CHUNK_WRITE_PTR(dest), src->data, src->datalen);
260  dest->datalen += src->datalen;
261  dest->next = src->next;
262  if (buf->tail == src)
263  buf->tail = dest;
264  buf_chunk_free_unchecked(src);
265  } else {
266  memcpy(CHUNK_WRITE_PTR(dest), src->data, n);
267  dest->datalen += n;
268  src->data += n;
269  src->datalen -= n;
270  tor_assert(dest->datalen == bytes);
271  }
272  }
273 
274  check();
275  *head_out = buf->head->data;
276  *len_out = buf->head->datalen;
277 }
278 
279 #ifdef TOR_UNIT_TESTS
280 /* Write sz bytes from cp into a newly allocated buffer buf.
281  * Returns NULL when passed a NULL cp or zero sz.
282  * Asserts on failure: only for use in unit tests.
283  * buf must be freed using buf_free(). */
284 buf_t *
285 buf_new_with_data(const char *cp, size_t sz)
286 {
287  /* Validate arguments */
288  if (!cp || sz <= 0 || sz > BUF_MAX_LEN) {
289  return NULL;
290  }
291 
293 
294  /* Allocate a buffer */
295  buf_t *buf = buf_new_with_capacity(sz);
296  tor_assert(buf);
297  buf_assert_ok(buf);
298  tor_assert(!buf->head);
299 
300  /* Allocate a chunk that is sz bytes long */
301  buf->head = chunk_new_with_alloc_size(CHUNK_ALLOC_SIZE(sz));
302  buf->tail = buf->head;
303  tor_assert(buf->head);
304  buf_assert_ok(buf);
305  tor_assert(buf_allocation(buf) >= sz);
306 
307  /* Copy the data and size the buffers */
308  tor_assert(sz <= buf_slack(buf));
309  tor_assert(sz <= CHUNK_REMAINING_CAPACITY(buf->head));
310  memcpy(&buf->head->mem[0], cp, sz);
311  buf->datalen = sz;
312  buf->head->datalen = sz;
313  buf->head->data = &buf->head->mem[0];
314  buf_assert_ok(buf);
315 
316  /* Make sure everything is large enough */
317  tor_assert(buf_allocation(buf) >= sz);
318  tor_assert(buf_allocation(buf) >= buf_datalen(buf) + buf_slack(buf));
319  /* Does the buffer implementation allocate more than the requested size?
320  * (for example, by rounding up). If so, these checks will fail. */
321  tor_assert(buf_datalen(buf) == sz);
322  tor_assert(buf_slack(buf) == 0);
323 
324  return buf;
325 }
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 {
332  tor_assert(buf->datalen >= n);
333  while (n) {
334  tor_assert(buf->head);
335  if (buf->head->datalen > n) {
336  buf->head->datalen -= n;
337  buf->head->data += n;
338  buf->datalen -= n;
339  return;
340  } else {
341  chunk_t *victim = buf->head;
342  n -= victim->datalen;
343  buf->datalen -= victim->datalen;
344  buf->head = victim->next;
345  if (buf->tail == victim)
346  buf->tail = NULL;
347  buf_chunk_free_unchecked(victim);
348  }
349  }
350  check();
351 }
352 
353 /** Create and return a new buf with default chunk capacity <b>size</b>.
354  */
355 buf_t *
357 {
358  buf_t *b = buf_new();
359  b->default_chunk_size = buf_preferred_chunk_size(size);
360  return b;
361 }
362 
363 /** Allocate and return a new buffer with default capacity. */
364 buf_t *
365 buf_new(void)
366 {
367  buf_t *buf = tor_malloc_zero(sizeof(buf_t));
368  buf->magic = BUFFER_MAGIC;
369  buf->default_chunk_size = 4096;
370  return buf;
371 }
372 
373 size_t
374 buf_get_default_chunk_size(const buf_t *buf)
375 {
376  return buf->default_chunk_size;
377 }
378 
379 /** Remove all data from <b>buf</b>. */
380 void
381 buf_clear(buf_t *buf)
382 {
383  chunk_t *chunk, *next;
384  buf->datalen = 0;
385  for (chunk = buf->head; chunk; chunk = next) {
386  next = chunk->next;
387  buf_chunk_free_unchecked(chunk);
388  }
389  buf->head = buf->tail = NULL;
390 }
391 
392 /** Return the number of bytes stored in <b>buf</b> */
393 MOCK_IMPL(size_t,
394 buf_datalen, (const buf_t *buf))
395 {
396  return buf->datalen;
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  size_t total = 0;
404  const chunk_t *chunk;
405  for (chunk = buf->head; chunk; chunk = chunk->next) {
406  total += CHUNK_ALLOC_SIZE(chunk->memlen);
407  }
408  return total;
409 }
410 
411 /** Return the number of bytes that can be added to <b>buf</b> without
412  * performing any additional allocation. */
413 size_t
414 buf_slack(const buf_t *buf)
415 {
416  if (!buf->tail)
417  return 0;
418  else
419  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  if (!buf)
427  return;
428 
429  buf_clear(buf);
430  buf->magic = 0xdeadbeef;
431  tor_free(buf);
432 }
433 
434 /** Return a new copy of <b>in_chunk</b> */
435 static chunk_t *
436 chunk_copy(const chunk_t *in_chunk)
437 {
438  chunk_t *newch = tor_memdup(in_chunk, CHUNK_ALLOC_SIZE(in_chunk->memlen));
440 #ifdef DEBUG_CHUNK_ALLOC
441  newch->DBG_alloc = CHUNK_ALLOC_SIZE(in_chunk->memlen);
442 #endif
443  newch->next = NULL;
444  if (in_chunk->data) {
445  ptrdiff_t offset = in_chunk->data - in_chunk->mem;
446  newch->data = newch->mem + offset;
447  }
448  return newch;
449 }
450 
451 /** Return a new copy of <b>buf</b> */
452 buf_t *
453 buf_copy(const buf_t *buf)
454 {
455  chunk_t *ch;
456  buf_t *out = buf_new();
457  out->default_chunk_size = buf->default_chunk_size;
458  for (ch = buf->head; ch; ch = ch->next) {
459  chunk_t *newch = chunk_copy(ch);
460  if (out->tail) {
461  out->tail->next = newch;
462  out->tail = newch;
463  } else {
464  out->head = out->tail = newch;
465  }
466  }
467  out->datalen = buf->datalen;
468  return out;
469 }
470 
471 /** Append a new chunk with enough capacity to hold <b>capacity</b> bytes to
472  * the tail of <b>buf</b>. If <b>capped</b>, don't allocate a chunk bigger
473  * 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  } else if (capped && CHUNK_ALLOC_SIZE(capacity) > MAX_CHUNK_ALLOC) {
482  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  if (buf->tail) {
490  tor_assert(buf->head);
491  buf->tail->next = chunk;
492  buf->tail = chunk;
493  } else {
494  tor_assert(!buf->head);
495  buf->head = buf->tail = chunk;
496  }
497  check();
498  return chunk;
499 }
500 
501 /** Return the age of the oldest chunk in the buffer <b>buf</b>, in
502  * timestamp units. Requires the current monotonic timestamp as its
503  * input <b>now</b>.
504  */
505 uint32_t
506 buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now)
507 {
508  if (buf->head) {
509  return now - buf->head->inserted_time;
510  } else {
511  return 0;
512  }
513 }
514 
515 size_t
516 buf_get_total_allocation(void)
517 {
519 }
520 
521 /** Append <b>string_len</b> bytes from <b>string</b> to the end of
522  * <b>buf</b>.
523  *
524  * Return the new length of the buffer on success, -1 on failure.
525  */
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();
532 
533  if (BUG(buf->datalen > BUF_MAX_LEN))
534  return -1;
535  if (BUG(buf->datalen > BUF_MAX_LEN - string_len))
536  return -1;
537 
538  while (string_len) {
539  size_t copy;
540  if (!buf->tail || !CHUNK_REMAINING_CAPACITY(buf->tail))
541  buf_add_chunk_with_capacity(buf, string_len, 1);
542 
543  copy = CHUNK_REMAINING_CAPACITY(buf->tail);
544  if (copy > string_len)
545  copy = string_len;
546  memcpy(CHUNK_WRITE_PTR(buf->tail), string, copy);
547  string_len -= copy;
548  string += copy;
549  buf->datalen += copy;
550  buf->tail->datalen += copy;
551  }
552 
553  check();
554  tor_assert(buf->datalen <= BUF_MAX_LEN);
555  return (int)buf->datalen;
556 }
557 
558 /** Add a nul-terminated <b>string</b> to <b>buf</b>, not including the
559  * terminating NUL. */
560 void
561 buf_add_string(buf_t *buf, const char *string)
562 {
563  buf_add(buf, string, strlen(string));
564 }
565 
566 /** As tor_snprintf, but write the results into a buf_t */
567 void
568 buf_add_printf(buf_t *buf, const char *format, ...)
569 {
570  va_list ap;
571  va_start(ap,format);
572  buf_add_vprintf(buf, format, ap);
573  va_end(ap);
574 }
575 
576 /** As tor_vsnprintf, but write the results into a buf_t. */
577 void
578 buf_add_vprintf(buf_t *buf, const char *format, va_list args)
579 {
580  /* XXXX Faster implementations are easy enough, but let's optimize later */
581  char *tmp;
582  tor_vasprintf(&tmp, format, args);
583  tor_assert(tmp != NULL);
584  buf_add(buf, tmp, strlen(tmp));
585  tor_free(tmp);
586 }
587 
588 /** Return a heap-allocated string containing the contents of <b>buf</b>, plus
589  * a NUL byte. If <b>sz_out</b> is provided, set *<b>sz_out</b> to the length
590  * of the returned string, not including the terminating NUL. */
591 char *
592 buf_extract(buf_t *buf, size_t *sz_out)
593 {
594  tor_assert(buf);
595 
596  size_t sz = buf_datalen(buf);
597  char *result;
598  result = tor_malloc(sz+1);
599  buf_peek(buf, result, sz);
600  result[sz] = 0;
601  if (sz_out)
602  *sz_out = sz;
603  return result;
604 }
605 
606 /** Helper: copy the first <b>string_len</b> bytes from <b>buf</b>
607  * 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;
613 
614  tor_assert(string);
615  /* make sure we don't ask for too much */
616  tor_assert(string_len <= buf->datalen);
617  /* buf_assert_ok(buf); */
618 
619  chunk = buf->head;
620  while (string_len) {
621  size_t copy = string_len;
622  tor_assert(chunk);
623  if (chunk->datalen < copy)
624  copy = chunk->datalen;
625  memcpy(string, chunk->data, copy);
626  string_len -= copy;
627  string += copy;
628  chunk = chunk->next;
629  }
630 }
631 
632 /** Remove <b>string_len</b> bytes from the front of <b>buf</b>, and store
633  * them into <b>string</b>. Return the new buffer size. <b>string_len</b>
634  * 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  /* There must be string_len bytes in buf; write them onto string,
640  * then memmove buf back (that is, remove them from buf).
641  *
642  * Return the number of bytes still on the buffer. */
643 
644  check();
645  buf_peek(buf, string, string_len);
646  buf_drain(buf, string_len);
647  check();
648  tor_assert(buf->datalen <= BUF_MAX_LEN);
649  return (int)buf->datalen;
650 }
651 
652 /** Move up to *<b>buf_flushlen</b> bytes from <b>buf_in</b> to
653  * <b>buf_out</b>, and modify *<b>buf_flushlen</b> appropriately.
654  * Return the number of bytes actually copied.
655  */
656 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  char b[4096];
661  size_t cp, len;
662 
663  if (BUG(buf_out->datalen > BUF_MAX_LEN || *buf_flushlen > BUF_MAX_LEN))
664  return -1;
665  if (BUG(buf_out->datalen > BUF_MAX_LEN - *buf_flushlen))
666  return -1;
667 
668  len = *buf_flushlen;
669  if (len > buf_in->datalen)
670  len = buf_in->datalen;
671 
672  cp = len; /* Remember the number of bytes we intend to copy. */
673  tor_assert(cp <= BUF_MAX_LEN);
674  while (len) {
675  /* This isn't the most efficient implementation one could imagine, since
676  * it does two copies instead of 1, but I kinda doubt that this will be
677  * critical path. */
678  size_t n = len > sizeof(b) ? sizeof(b) : len;
679  buf_get_bytes(buf_in, b, n);
680  buf_add(buf_out, b, n);
681  len -= n;
682  }
683  *buf_flushlen -= cp;
684  return (int)cp;
685 }
686 
687 /** Moves all data from <b>buf_in</b> to <b>buf_out</b>, without copying.
688  * Return the number of bytes that were moved.
689  */
690 size_t
691 buf_move_all(buf_t *buf_out, buf_t *buf_in)
692 {
693  tor_assert(buf_out);
694  if (!buf_in)
695  return 0;
696  if (buf_datalen(buf_in) == 0)
697  return 0;
698  if (BUG(buf_out->datalen > BUF_MAX_LEN || buf_in->datalen > BUF_MAX_LEN))
699  return 0;
700  if (BUG(buf_out->datalen > BUF_MAX_LEN - buf_in->datalen))
701  return 0;
702 
703  size_t n_bytes_moved = buf_in->datalen;
704 
705  if (buf_out->head == NULL) {
706  buf_out->head = buf_in->head;
707  buf_out->tail = buf_in->tail;
708  } else {
709  buf_out->tail->next = buf_in->head;
710  buf_out->tail = buf_in->tail;
711  }
712 
713  buf_out->datalen += buf_in->datalen;
714  buf_in->head = buf_in->tail = NULL;
715  buf_in->datalen = 0;
716 
717  return n_bytes_moved;
718 }
719 
720 /** Internal structure: represents a position in a buffer. */
721 typedef struct buf_pos_t {
722  const chunk_t *chunk; /**< Which chunk are we pointing to? */
723  ptrdiff_t pos;/**< Which character inside the chunk's data are we pointing
724  * to? */
725  size_t chunk_pos; /**< Total length of all previous chunks. */
726 } buf_pos_t;
727 
728 /** Initialize <b>out</b> to point to the first character of <b>buf</b>.*/
729 static void
730 buf_pos_init(const buf_t *buf, buf_pos_t *out)
731 {
732  out->chunk = buf->head;
733  out->pos = 0;
734  out->chunk_pos = 0;
735 }
736 
737 /** Advance <b>out</b> to the first appearance of <b>ch</b> at the current
738  * position of <b>out</b>, or later. Return -1 if no instances are found;
739  * otherwise returns the absolute position of the character. */
740 static ptrdiff_t
742 {
743  const chunk_t *chunk;
744  ptrdiff_t pos;
745  tor_assert(out);
746  if (out->chunk) {
747  if (out->chunk->datalen) {
748  tor_assert(out->pos < (ptrdiff_t)out->chunk->datalen);
749  } else {
750  tor_assert(out->pos == 0);
751  }
752  }
753  pos = out->pos;
754  for (chunk = out->chunk; chunk; chunk = chunk->next) {
755  char *cp = memchr(chunk->data+pos, ch, chunk->datalen - pos);
756  if (cp) {
757  out->chunk = chunk;
758  tor_assert(cp - chunk->data <= BUF_MAX_LEN);
759  out->pos = (int)(cp - chunk->data);
760  return out->chunk_pos + out->pos;
761  } else {
762  out->chunk_pos += chunk->datalen;
763  pos = 0;
764  }
765  }
766  return -1;
767 }
768 
769 /** Advance <b>pos</b> by a single character, if there are any more characters
770  * in the buffer. Returns 0 on success, -1 on failure. */
771 static inline int
773 {
774  tor_assert(pos->pos < BUF_MAX_LEN);
775  ++pos->pos;
776  if (pos->pos == (ptrdiff_t)pos->chunk->datalen) {
777  if (!pos->chunk->next)
778  return -1;
779  pos->chunk_pos += pos->chunk->datalen;
780  pos->chunk = pos->chunk->next;
781  pos->pos = 0;
782  }
783  return 0;
784 }
785 
786 /** Return true iff the <b>n</b>-character string in <b>s</b> appears
787  * (verbatim) at <b>pos</b>. */
788 static int
789 buf_matches_at_pos(const buf_pos_t *pos, const char *s, size_t n)
790 {
791  buf_pos_t p;
792  if (!n)
793  return 1;
794 
795  memcpy(&p, pos, sizeof(p));
796 
797  while (1) {
798  char ch = p.chunk->data[p.pos];
799  if (ch != *s)
800  return 0;
801  ++s;
802  /* If we're out of characters that don't match, we match. Check this
803  * _before_ we test incrementing pos, in case we're at the end of the
804  * string. */
805  if (--n == 0)
806  return 1;
807  if (buf_pos_inc(&p)<0)
808  return 0;
809  }
810 }
811 
812 /** Return the first position in <b>buf</b> at which the <b>n</b>-character
813  * string <b>s</b> occurs, or -1 if it does not occur. */
814 int
815 buf_find_string_offset(const buf_t *buf, const char *s, size_t n)
816 {
817  buf_pos_t pos;
818  buf_pos_init(buf, &pos);
819  while (buf_find_pos_of_char(*s, &pos) >= 0) {
820  if (buf_matches_at_pos(&pos, s, n)) {
821  tor_assert(pos.chunk_pos + pos.pos <= BUF_MAX_LEN);
822  return (int)(pos.chunk_pos + pos.pos);
823  } else {
824  if (buf_pos_inc(&pos)<0)
825  return -1;
826  }
827  }
828  return -1;
829 }
830 
831 /** Return 1 iff <b>buf</b> starts with <b>cmd</b>. <b>cmd</b> must be a null
832  * terminated string, of no more than PEEK_BUF_STARTSWITH_MAX bytes. */
833 int
834 buf_peek_startswith(const buf_t *buf, const char *cmd)
835 {
836  char tmp[PEEK_BUF_STARTSWITH_MAX];
837  size_t clen = strlen(cmd);
838  if (clen == 0)
839  return 1;
840  if (BUG(clen > sizeof(tmp)))
841  return 0;
842  if (buf->datalen < clen)
843  return 0;
844  buf_peek(buf, tmp, clen);
845  return fast_memeq(tmp, cmd, clen);
846 }
847 
848 /** Return the index within <b>buf</b> at which <b>ch</b> first appears,
849  * or -1 if <b>ch</b> does not appear on buf. */
850 static ptrdiff_t
851 buf_find_offset_of_char(buf_t *buf, char ch)
852 {
853  chunk_t *chunk;
854  ptrdiff_t offset = 0;
855  tor_assert(buf->datalen <= BUF_MAX_LEN);
856  for (chunk = buf->head; chunk; chunk = chunk->next) {
857  char *cp = memchr(chunk->data, ch, chunk->datalen);
858  if (cp)
859  return offset + (cp - chunk->data);
860  else
861  offset += chunk->datalen;
862  }
863  return -1;
864 }
865 
866 /** Try to read a single LF-terminated line from <b>buf</b>, and write it
867  * (including the LF), NUL-terminated, into the *<b>data_len</b> byte buffer
868  * at <b>data_out</b>. Set *<b>data_len</b> to the number of bytes in the
869  * line, not counting the terminating NUL. Return 1 if we read a whole line,
870  * return 0 if we don't have a whole line yet, and return -1 if the line
871  * length exceeds *<b>data_len</b>.
872  */
873 int
874 buf_get_line(buf_t *buf, char *data_out, size_t *data_len)
875 {
876  size_t sz;
877  ptrdiff_t offset;
878 
879  if (!buf->head)
880  return 0;
881 
882  offset = buf_find_offset_of_char(buf, '\n');
883  if (offset < 0)
884  return 0;
885  sz = (size_t) offset;
886  if (sz+2 > *data_len) {
887  *data_len = sz + 2;
888  return -1;
889  }
890  buf_get_bytes(buf, data_out, sz+1);
891  data_out[sz+1] = '\0';
892  *data_len = sz+1;
893  return 1;
894 }
895 
896 /** Set *<b>output</b> to contain a copy of the data in *<b>input</b> */
897 int
898 buf_set_to_copy(buf_t **output,
899  const buf_t *input)
900 {
901  if (*output)
902  buf_free(*output);
903  *output = buf_copy(input);
904  return 0;
905 }
906 
907 /** Log an error and exit if <b>buf</b> is corrupted.
908  */
909 void
910 buf_assert_ok(buf_t *buf)
911 {
912  tor_assert(buf);
913  tor_assert(buf->magic == BUFFER_MAGIC);
914 
915  if (! buf->head) {
916  tor_assert(!buf->tail);
917  tor_assert(buf->datalen == 0);
918  } else {
919  chunk_t *ch;
920  size_t total = 0;
921  tor_assert(buf->tail);
922  for (ch = buf->head; ch; ch = ch->next) {
923  total += ch->datalen;
924  tor_assert(ch->datalen <= ch->memlen);
925  tor_assert(ch->datalen <= BUF_MAX_LEN);
926  tor_assert(ch->data >= &ch->mem[0]);
927  tor_assert(ch->data <= &ch->mem[0]+ch->memlen);
928  if (ch->data == &ch->mem[0]+ch->memlen) {
929  /* LCOV_EXCL_START */
930  static int warned = 0;
931  if (! warned) {
932  log_warn(LD_BUG, "Invariant violation in buf.c related to #15083");
933  warned = 1;
934  }
935  /* LCOV_EXCL_STOP */
936  }
937  tor_assert(ch->data+ch->datalen <= &ch->mem[0] + ch->memlen);
938  if (!ch->next)
939  tor_assert(ch == buf->tail);
940  }
941  tor_assert(buf->datalen == total);
942  }
943 }
static chunk_t * chunk_grow(chunk_t *chunk, size_t sz)
Definition: buffers.c:161
void buf_add_printf(buf_t *buf, const char *format,...)
Definition: buffers.c:568
static size_t total_bytes_allocated_in_chunks
Definition: buffers.c:127
size_t buf_move_all(buf_t *buf_out, buf_t *buf_in)
Definition: buffers.c:691
void buf_clear(buf_t *buf)
Definition: buffers.c:381
chunk_t * buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped)
Definition: buffers.c:475
buf_t * buf_new_with_capacity(size_t size)
Definition: buffers.c:356
static void chunk_repack(chunk_t *chunk)
Definition: buffers.c:118
int buf_add(buf_t *buf, const char *string, size_t string_len)
Definition: buffers.c:527
buf_t * buf_new(void)
Definition: buffers.c:365
void buf_drain(buf_t *buf, size_t n)
Definition: buffers.c:330
size_t buf_allocation(const buf_t *buf)
Definition: buffers.c:401
#define CHUNK_SIZE_WITH_ALLOC(memlen)
Definition: buffers.c:92
static int buf_pos_inc(buf_pos_t *pos)
Definition: buffers.c:772
int buf_find_string_offset(const buf_t *buf, const char *s, size_t n)
Definition: buffers.c:815
size_t buf_datalen(const buf_t *buf)
Definition: buffers.c:394
buf_t * buf_copy(const buf_t *buf)
Definition: buffers.c:453
uint32_t buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now)
Definition: buffers.c:506
int buf_peek_startswith(const buf_t *buf, const char *cmd)
Definition: buffers.c:834
static chunk_t * chunk_copy(const chunk_t *in_chunk)
Definition: buffers.c:436
static ptrdiff_t buf_find_pos_of_char(char ch, buf_pos_t *out)
Definition: buffers.c:741
void buf_assert_ok(buf_t *buf)
Definition: buffers.c:910
#define MIN_CHUNK_ALLOC
Definition: buffers.c:182
#define CHUNK_ALLOC_SIZE(memlen)
Definition: buffers.c:89
int buf_get_line(buf_t *buf, char *data_out, size_t *data_len)
Definition: buffers.c:874
size_t buf_slack(const buf_t *buf)
Definition: buffers.c:414
void buf_add_vprintf(buf_t *buf, const char *format, va_list args)
Definition: buffers.c:578
static ptrdiff_t buf_find_offset_of_char(buf_t *buf, char ch)
Definition: buffers.c:851
void buf_peek(const buf_t *buf, char *string, size_t string_len)
Definition: buffers.c:610
#define MAX_CHUNK_ALLOC
Definition: buffers.c:184
static void buf_pos_init(const buf_t *buf, buf_pos_t *out)
Definition: buffers.c:730
int buf_move_to_buf(buf_t *buf_out, buf_t *buf_in, size_t *buf_flushlen)
Definition: buffers.c:657
void buf_free_(buf_t *buf)
Definition: buffers.c:424
void buf_add_string(buf_t *buf, const char *string)
Definition: buffers.c:561
size_t buf_preferred_chunk_size(size_t target)
Definition: buffers.c:189
int buf_set_to_copy(buf_t **output, const buf_t *input)
Definition: buffers.c:898
int buf_get_bytes(buf_t *buf, char *string, size_t string_len)
Definition: buffers.c:637
static int buf_matches_at_pos(const buf_pos_t *pos, const char *s, size_t n)
Definition: buffers.c:789
char * buf_extract(buf_t *buf, size_t *sz_out)
Definition: buffers.c:592
void buf_pullup(buf_t *buf, size_t bytes, const char **head_out, size_t *len_out)
Definition: buffers.c:211
Header file for buffers.c.
#define BUF_MAX_LEN
Definition: buffers.h:33
uint32_t monotime_coarse_get_stamp(void)
Definition: compat_time.c:844
Functions and types for monotonic times.
Headers for di_ops.c.
#define fast_memeq(a, b, c)
Definition: di_ops.h:35
Headers for log.c.
#define LD_BUG
Definition: log.h:86
Headers for util_malloc.c.
#define tor_free(p)
Definition: malloc.h:52
int tor_vasprintf(char **strp, const char *fmt, va_list args)
Definition: printf.c:96
Header for printf.c.
const chunk_t * chunk
Definition: buffers.c:722
size_t chunk_pos
Definition: buffers.c:725
ptrdiff_t pos
Definition: buffers.c:723
#define MOCK_IMPL(rv, funcname, arglist)
Definition: testsupport.h:133
Integer definitions used throughout Tor.
#define SIZE_T_CEILING
Definition: torint.h:126
#define SSIZE_T_CEILING
Definition: torint.h:124
Macros to manage assertions, fatal and non-fatal.
#define tor_assert(expr)
Definition: util_bug.h:102