Line data Source code
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 6 : chunk_repack(chunk_t *chunk)
119 : {
120 6 : if (chunk->datalen && chunk->data != &chunk->mem[0]) {
121 2 : memmove(chunk->mem, chunk->data, chunk->datalen);
122 : }
123 6 : chunk->data = &chunk->mem[0];
124 6 : }
125 :
126 : /** Keep track of total size of allocated chunks for consistency asserts */
127 : static size_t total_bytes_allocated_in_chunks = 0;
128 : static void
129 3435 : buf_chunk_free_unchecked(chunk_t *chunk)
130 : {
131 3435 : if (!chunk)
132 : return;
133 : #ifdef DEBUG_CHUNK_ALLOC
134 3435 : tor_assert(CHUNK_ALLOC_SIZE(chunk->memlen) == chunk->DBG_alloc);
135 : #endif
136 3435 : tor_assert(total_bytes_allocated_in_chunks >=
137 : CHUNK_ALLOC_SIZE(chunk->memlen));
138 3435 : total_bytes_allocated_in_chunks -= CHUNK_ALLOC_SIZE(chunk->memlen);
139 3435 : tor_free(chunk);
140 : }
141 : static inline chunk_t *
142 3421 : chunk_new_with_alloc_size(size_t alloc)
143 : {
144 3421 : chunk_t *ch;
145 3421 : ch = tor_malloc(alloc);
146 3421 : ch->next = NULL;
147 3421 : ch->datalen = 0;
148 : #ifdef DEBUG_CHUNK_ALLOC
149 3421 : ch->DBG_alloc = alloc;
150 : #endif
151 3421 : ch->memlen = CHUNK_SIZE_WITH_ALLOC(alloc);
152 3421 : total_bytes_allocated_in_chunks += alloc;
153 3421 : ch->data = &ch->mem[0];
154 3421 : CHUNK_SET_SENTINEL(ch, alloc);
155 3421 : 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 5 : chunk_grow(chunk_t *chunk, size_t sz)
162 : {
163 5 : ptrdiff_t offset;
164 5 : const size_t memlen_orig = chunk->memlen;
165 5 : const size_t orig_alloc = CHUNK_ALLOC_SIZE(memlen_orig);
166 5 : const size_t new_alloc = CHUNK_ALLOC_SIZE(sz);
167 5 : tor_assert(sz > chunk->memlen);
168 5 : offset = chunk->data - chunk->mem;
169 5 : chunk = tor_realloc(chunk, new_alloc);
170 5 : chunk->memlen = sz;
171 5 : chunk->data = chunk->mem + offset;
172 : #ifdef DEBUG_CHUNK_ALLOC
173 5 : tor_assert(chunk->DBG_alloc == orig_alloc);
174 5 : chunk->DBG_alloc = new_alloc;
175 : #endif
176 5 : total_bytes_allocated_in_chunks += new_alloc - orig_alloc;
177 5 : CHUNK_SET_SENTINEL(chunk, new_alloc);
178 5 : 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
189 202 : buf_preferred_chunk_size(size_t target)
190 : {
191 202 : tor_assert(target <= SIZE_T_CEILING - CHUNK_OVERHEAD);
192 202 : if (CHUNK_ALLOC_SIZE(target) >= MAX_CHUNK_ALLOC)
193 : return CHUNK_ALLOC_SIZE(target);
194 : size_t sz = MIN_CHUNK_ALLOC;
195 561 : while (CHUNK_SIZE_WITH_ALLOC(sz) < target) {
196 363 : 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 1990 : buf_pullup(buf_t *buf, size_t bytes, const char **head_out, size_t *len_out)
212 : {
213 1990 : chunk_t *dest, *src;
214 1990 : size_t capacity;
215 1990 : if (!buf->head) {
216 1 : *head_out = NULL;
217 1 : *len_out = 0;
218 1 : return;
219 : }
220 :
221 1989 : check();
222 1989 : if (buf->datalen < bytes)
223 : bytes = buf->datalen;
224 :
225 1989 : capacity = bytes;
226 1989 : if (buf->head->datalen >= bytes) {
227 1983 : *head_out = buf->head->data;
228 1983 : *len_out = buf->head->datalen;
229 1983 : return;
230 : }
231 :
232 6 : if (buf->head->memlen >= capacity) {
233 : /* We don't need to grow the first chunk, but we might need to repack it.*/
234 1 : size_t needed = capacity - buf->head->datalen;
235 1 : if (CHUNK_REMAINING_CAPACITY(buf->head) < needed)
236 1 : chunk_repack(buf->head);
237 1 : tor_assert(CHUNK_REMAINING_CAPACITY(buf->head) >= needed);
238 : } else {
239 5 : chunk_t *newhead;
240 5 : size_t newsize;
241 : /* We need to grow the chunk. */
242 5 : chunk_repack(buf->head);
243 5 : newsize = CHUNK_SIZE_WITH_ALLOC(buf_preferred_chunk_size(capacity));
244 5 : newhead = chunk_grow(buf->head, newsize);
245 5 : tor_assert(newhead->memlen >= capacity);
246 5 : if (newhead != buf->head) {
247 5 : if (buf->tail == buf->head)
248 0 : buf->tail = newhead;
249 5 : buf->head = newhead;
250 : }
251 : }
252 :
253 6 : dest = buf->head;
254 17 : while (dest->datalen < bytes) {
255 11 : size_t n = bytes - dest->datalen;
256 11 : src = dest->next;
257 11 : tor_assert(src);
258 11 : if (n >= src->datalen) {
259 7 : memcpy(CHUNK_WRITE_PTR(dest), src->data, src->datalen);
260 7 : dest->datalen += src->datalen;
261 7 : dest->next = src->next;
262 7 : if (buf->tail == src)
263 2 : buf->tail = dest;
264 7 : buf_chunk_free_unchecked(src);
265 : } else {
266 4 : memcpy(CHUNK_WRITE_PTR(dest), src->data, n);
267 4 : dest->datalen += n;
268 4 : src->data += n;
269 4 : src->datalen -= n;
270 4 : tor_assert(dest->datalen == bytes);
271 : }
272 : }
273 :
274 6 : check();
275 6 : *head_out = buf->head->data;
276 6 : *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 0 : buf_new_with_data(const char *cp, size_t sz)
286 : {
287 : /* Validate arguments */
288 0 : if (!cp || sz <= 0 || sz > BUF_MAX_LEN) {
289 : return NULL;
290 : }
291 :
292 0 : tor_assert(sz < SSIZE_T_CEILING);
293 :
294 : /* Allocate a buffer */
295 0 : buf_t *buf = buf_new_with_capacity(sz);
296 0 : tor_assert(buf);
297 0 : buf_assert_ok(buf);
298 0 : tor_assert(!buf->head);
299 :
300 : /* Allocate a chunk that is sz bytes long */
301 0 : buf->head = chunk_new_with_alloc_size(CHUNK_ALLOC_SIZE(sz));
302 0 : buf->tail = buf->head;
303 0 : tor_assert(buf->head);
304 0 : buf_assert_ok(buf);
305 0 : tor_assert(buf_allocation(buf) >= sz);
306 :
307 : /* Copy the data and size the buffers */
308 0 : tor_assert(sz <= buf_slack(buf));
309 0 : tor_assert(sz <= CHUNK_REMAINING_CAPACITY(buf->head));
310 0 : memcpy(&buf->head->mem[0], cp, sz);
311 0 : buf->datalen = sz;
312 0 : buf->head->datalen = sz;
313 0 : buf->head->data = &buf->head->mem[0];
314 0 : buf_assert_ok(buf);
315 :
316 : /* Make sure everything is large enough */
317 0 : tor_assert(buf_allocation(buf) >= sz);
318 0 : 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 0 : tor_assert(buf_datalen(buf) == sz);
322 0 : 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 1892 : buf_drain(buf_t *buf, size_t n)
331 : {
332 1892 : tor_assert(buf->datalen >= n);
333 3149 : while (n) {
334 2021 : tor_assert(buf->head);
335 2021 : if (buf->head->datalen > n) {
336 764 : buf->head->datalen -= n;
337 764 : buf->head->data += n;
338 764 : buf->datalen -= n;
339 764 : return;
340 : } else {
341 1257 : chunk_t *victim = buf->head;
342 1257 : n -= victim->datalen;
343 1257 : buf->datalen -= victim->datalen;
344 1257 : buf->head = victim->next;
345 1257 : if (buf->tail == victim)
346 1118 : buf->tail = NULL;
347 1257 : buf_chunk_free_unchecked(victim);
348 : }
349 : }
350 1892 : check();
351 : }
352 :
353 : /** Create and return a new buf with default chunk capacity <b>size</b>.
354 : */
355 : buf_t *
356 132 : buf_new_with_capacity(size_t size)
357 : {
358 132 : buf_t *b = buf_new();
359 132 : b->default_chunk_size = buf_preferred_chunk_size(size);
360 132 : return b;
361 : }
362 :
363 : /** Allocate and return a new buffer with default capacity. */
364 : buf_t *
365 1065 : buf_new(void)
366 : {
367 1065 : buf_t *buf = tor_malloc_zero(sizeof(buf_t));
368 1065 : buf->magic = BUFFER_MAGIC;
369 1065 : buf->default_chunk_size = 4096;
370 1065 : return buf;
371 : }
372 :
373 : size_t
374 21 : buf_get_default_chunk_size(const buf_t *buf)
375 : {
376 21 : return buf->default_chunk_size;
377 : }
378 :
379 : /** Remove all data from <b>buf</b>. */
380 : void
381 2180 : buf_clear(buf_t *buf)
382 : {
383 2180 : chunk_t *chunk, *next;
384 2180 : buf->datalen = 0;
385 4351 : for (chunk = buf->head; chunk; chunk = next) {
386 2171 : next = chunk->next;
387 2171 : buf_chunk_free_unchecked(chunk);
388 : }
389 2180 : buf->head = buf->tail = NULL;
390 2180 : }
391 :
392 : /** Return the number of bytes stored in <b>buf</b> */
393 10851 : MOCK_IMPL(size_t,
394 : buf_datalen, (const buf_t *buf))
395 : {
396 10851 : return buf->datalen;
397 : }
398 :
399 : /** Return the total length of all chunks used in <b>buf</b>. */
400 : size_t
401 26 : buf_allocation(const buf_t *buf)
402 : {
403 26 : size_t total = 0;
404 26 : const chunk_t *chunk;
405 1052 : for (chunk = buf->head; chunk; chunk = chunk->next) {
406 1026 : total += CHUNK_ALLOC_SIZE(chunk->memlen);
407 : }
408 26 : 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 0 : buf_slack(const buf_t *buf)
415 : {
416 0 : if (!buf->tail)
417 : return 0;
418 : else
419 0 : return CHUNK_REMAINING_CAPACITY(buf->tail);
420 : }
421 :
422 : /** Release storage held by <b>buf</b>. */
423 : void
424 1049 : buf_free_(buf_t *buf)
425 : {
426 1049 : if (!buf)
427 : return;
428 :
429 1046 : buf_clear(buf);
430 1046 : buf->magic = 0xdeadbeef;
431 1046 : tor_free(buf);
432 : }
433 :
434 : /** Return a new copy of <b>in_chunk</b> */
435 : static chunk_t *
436 14 : chunk_copy(const chunk_t *in_chunk)
437 : {
438 14 : chunk_t *newch = tor_memdup(in_chunk, CHUNK_ALLOC_SIZE(in_chunk->memlen));
439 14 : total_bytes_allocated_in_chunks += CHUNK_ALLOC_SIZE(in_chunk->memlen);
440 : #ifdef DEBUG_CHUNK_ALLOC
441 14 : newch->DBG_alloc = CHUNK_ALLOC_SIZE(in_chunk->memlen);
442 : #endif
443 14 : newch->next = NULL;
444 14 : if (in_chunk->data) {
445 14 : ptrdiff_t offset = in_chunk->data - in_chunk->mem;
446 14 : newch->data = newch->mem + offset;
447 : }
448 14 : return newch;
449 : }
450 :
451 : /** Return a new copy of <b>buf</b> */
452 : buf_t *
453 5 : buf_copy(const buf_t *buf)
454 : {
455 5 : chunk_t *ch;
456 5 : buf_t *out = buf_new();
457 5 : out->default_chunk_size = buf->default_chunk_size;
458 19 : for (ch = buf->head; ch; ch = ch->next) {
459 14 : chunk_t *newch = chunk_copy(ch);
460 14 : if (out->tail) {
461 10 : out->tail->next = newch;
462 10 : out->tail = newch;
463 : } else {
464 4 : out->head = out->tail = newch;
465 : }
466 : }
467 5 : out->datalen = buf->datalen;
468 5 : 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 3421 : buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped)
476 : {
477 3421 : chunk_t *chunk;
478 :
479 3421 : if (CHUNK_ALLOC_SIZE(capacity) < buf->default_chunk_size) {
480 3364 : chunk = chunk_new_with_alloc_size(buf->default_chunk_size);
481 57 : } else if (capped && CHUNK_ALLOC_SIZE(capacity) > MAX_CHUNK_ALLOC) {
482 1 : chunk = chunk_new_with_alloc_size(MAX_CHUNK_ALLOC);
483 : } else {
484 56 : chunk = chunk_new_with_alloc_size(buf_preferred_chunk_size(capacity));
485 : }
486 :
487 3421 : chunk->inserted_time = monotime_coarse_get_stamp();
488 :
489 3421 : if (buf->tail) {
490 1149 : tor_assert(buf->head);
491 1149 : buf->tail->next = chunk;
492 1149 : buf->tail = chunk;
493 : } else {
494 2272 : tor_assert(!buf->head);
495 2272 : buf->head = buf->tail = chunk;
496 : }
497 3421 : check();
498 3421 : 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 126 : buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now)
507 : {
508 126 : if (buf->head) {
509 124 : return now - buf->head->inserted_time;
510 : } else {
511 : return 0;
512 : }
513 : }
514 :
515 : size_t
516 38 : buf_get_total_allocation(void)
517 : {
518 38 : return total_bytes_allocated_in_chunks;
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 6459 : buf_add(buf_t *buf, const char *string, size_t string_len)
528 : {
529 6459 : if (!string_len)
530 26 : return (int)buf->datalen;
531 6433 : check();
532 :
533 6433 : if (BUG(buf->datalen > BUF_MAX_LEN))
534 0 : return -1;
535 6433 : if (BUG(buf->datalen > BUF_MAX_LEN - string_len))
536 0 : return -1;
537 :
538 13914 : while (string_len) {
539 7481 : size_t copy;
540 7481 : if (!buf->tail || !CHUNK_REMAINING_CAPACITY(buf->tail))
541 3276 : buf_add_chunk_with_capacity(buf, string_len, 1);
542 :
543 7481 : copy = CHUNK_REMAINING_CAPACITY(buf->tail);
544 7481 : if (copy > string_len)
545 : copy = string_len;
546 7481 : memcpy(CHUNK_WRITE_PTR(buf->tail), string, copy);
547 7481 : string_len -= copy;
548 7481 : string += copy;
549 7481 : buf->datalen += copy;
550 7481 : buf->tail->datalen += copy;
551 : }
552 :
553 6433 : check();
554 6433 : tor_assert(buf->datalen <= BUF_MAX_LEN);
555 6433 : 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 135 : buf_add_string(buf_t *buf, const char *string)
562 : {
563 135 : buf_add(buf, string, strlen(string));
564 135 : }
565 :
566 : /** As tor_snprintf, but write the results into a buf_t */
567 : void
568 255 : buf_add_printf(buf_t *buf, const char *format, ...)
569 : {
570 255 : va_list ap;
571 255 : va_start(ap,format);
572 255 : buf_add_vprintf(buf, format, ap);
573 255 : va_end(ap);
574 255 : }
575 :
576 : /** As tor_vsnprintf, but write the results into a buf_t. */
577 : void
578 255 : 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 255 : char *tmp;
582 255 : tor_vasprintf(&tmp, format, args);
583 255 : tor_assert(tmp != NULL);
584 255 : buf_add(buf, tmp, strlen(tmp));
585 255 : tor_free(tmp);
586 255 : }
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 44 : buf_extract(buf_t *buf, size_t *sz_out)
593 : {
594 44 : tor_assert(buf);
595 :
596 44 : size_t sz = buf_datalen(buf);
597 44 : char *result;
598 44 : result = tor_malloc(sz+1);
599 44 : buf_peek(buf, result, sz);
600 44 : result[sz] = 0;
601 44 : if (sz_out)
602 0 : *sz_out = sz;
603 44 : 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 1070 : buf_peek(const buf_t *buf, char *string, size_t string_len)
611 : {
612 1070 : chunk_t *chunk;
613 :
614 1070 : tor_assert(string);
615 : /* make sure we don't ask for too much */
616 1070 : tor_assert(string_len <= buf->datalen);
617 : /* buf_assert_ok(buf); */
618 :
619 1070 : chunk = buf->head;
620 2264 : while (string_len) {
621 1194 : size_t copy = string_len;
622 1194 : tor_assert(chunk);
623 1194 : if (chunk->datalen < copy)
624 : copy = chunk->datalen;
625 1194 : memcpy(string, chunk->data, copy);
626 1194 : string_len -= copy;
627 1194 : string += copy;
628 1194 : chunk = chunk->next;
629 : }
630 1070 : }
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 982 : 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 982 : check();
645 982 : buf_peek(buf, string, string_len);
646 982 : buf_drain(buf, string_len);
647 982 : check();
648 982 : tor_assert(buf->datalen <= BUF_MAX_LEN);
649 982 : 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 102 : 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 102 : char b[4096];
661 102 : size_t cp, len;
662 :
663 102 : if (BUG(buf_out->datalen > BUF_MAX_LEN || *buf_flushlen > BUF_MAX_LEN))
664 0 : return -1;
665 102 : if (BUG(buf_out->datalen > BUF_MAX_LEN - *buf_flushlen))
666 0 : return -1;
667 :
668 102 : len = *buf_flushlen;
669 102 : if (len > buf_in->datalen)
670 : len = buf_in->datalen;
671 :
672 102 : cp = len; /* Remember the number of bytes we intend to copy. */
673 102 : tor_assert(cp <= BUF_MAX_LEN);
674 208 : 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 106 : size_t n = len > sizeof(b) ? sizeof(b) : len;
679 106 : buf_get_bytes(buf_in, b, n);
680 106 : buf_add(buf_out, b, n);
681 106 : len -= n;
682 : }
683 102 : *buf_flushlen -= cp;
684 102 : 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 35 : buf_move_all(buf_t *buf_out, buf_t *buf_in)
692 : {
693 35 : tor_assert(buf_out);
694 35 : if (!buf_in)
695 : return 0;
696 35 : if (buf_datalen(buf_in) == 0)
697 : return 0;
698 33 : if (BUG(buf_out->datalen > BUF_MAX_LEN || buf_in->datalen > BUF_MAX_LEN))
699 0 : return 0;
700 33 : if (BUG(buf_out->datalen > BUF_MAX_LEN - buf_in->datalen))
701 0 : return 0;
702 :
703 33 : size_t n_bytes_moved = buf_in->datalen;
704 :
705 33 : if (buf_out->head == NULL) {
706 31 : buf_out->head = buf_in->head;
707 31 : buf_out->tail = buf_in->tail;
708 : } else {
709 2 : buf_out->tail->next = buf_in->head;
710 2 : buf_out->tail = buf_in->tail;
711 : }
712 :
713 33 : buf_out->datalen += buf_in->datalen;
714 33 : buf_in->head = buf_in->tail = NULL;
715 33 : buf_in->datalen = 0;
716 :
717 33 : 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 90 : buf_pos_init(const buf_t *buf, buf_pos_t *out)
731 : {
732 90 : out->chunk = buf->head;
733 90 : out->pos = 0;
734 90 : out->chunk_pos = 0;
735 90 : }
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
741 267 : buf_find_pos_of_char(char ch, buf_pos_t *out)
742 : {
743 267 : const chunk_t *chunk;
744 267 : ptrdiff_t pos;
745 267 : tor_assert(out);
746 267 : if (out->chunk) {
747 267 : if (out->chunk->datalen) {
748 267 : tor_assert(out->pos < (ptrdiff_t)out->chunk->datalen);
749 : } else {
750 0 : tor_assert(out->pos == 0);
751 : }
752 : }
753 267 : pos = out->pos;
754 272 : for (chunk = out->chunk; chunk; chunk = chunk->next) {
755 267 : char *cp = memchr(chunk->data+pos, ch, chunk->datalen - pos);
756 267 : if (cp) {
757 262 : out->chunk = chunk;
758 262 : tor_assert(cp - chunk->data <= BUF_MAX_LEN);
759 262 : out->pos = (int)(cp - chunk->data);
760 262 : return out->chunk_pos + out->pos;
761 : } else {
762 5 : out->chunk_pos += chunk->datalen;
763 5 : 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
772 808 : buf_pos_inc(buf_pos_t *pos)
773 : {
774 808 : tor_assert(pos->pos < BUF_MAX_LEN);
775 808 : ++pos->pos;
776 808 : if (pos->pos == (ptrdiff_t)pos->chunk->datalen) {
777 2 : if (!pos->chunk->next)
778 : return -1;
779 0 : pos->chunk_pos += pos->chunk->datalen;
780 0 : pos->chunk = pos->chunk->next;
781 0 : 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 262 : buf_matches_at_pos(const buf_pos_t *pos, const char *s, size_t n)
790 : {
791 262 : buf_pos_t p;
792 262 : if (!n)
793 : return 1;
794 :
795 262 : memcpy(&p, pos, sizeof(p));
796 :
797 891 : while (1) {
798 891 : char ch = p.chunk->data[p.pos];
799 891 : if (ch != *s)
800 : return 0;
801 716 : ++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 716 : if (--n == 0)
806 : return 1;
807 631 : 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 90 : buf_find_string_offset(const buf_t *buf, const char *s, size_t n)
816 : {
817 90 : buf_pos_t pos;
818 90 : buf_pos_init(buf, &pos);
819 267 : while (buf_find_pos_of_char(*s, &pos) >= 0) {
820 262 : if (buf_matches_at_pos(&pos, s, n)) {
821 85 : tor_assert(pos.chunk_pos + pos.pos <= BUF_MAX_LEN);
822 85 : return (int)(pos.chunk_pos + pos.pos);
823 : } else {
824 177 : 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 39 : buf_peek_startswith(const buf_t *buf, const char *cmd)
835 : {
836 39 : char tmp[PEEK_BUF_STARTSWITH_MAX];
837 39 : size_t clen = strlen(cmd);
838 39 : if (clen == 0)
839 : return 1;
840 37 : if (BUG(clen > sizeof(tmp)))
841 0 : return 0;
842 37 : if (buf->datalen < clen)
843 : return 0;
844 20 : buf_peek(buf, tmp, clen);
845 20 : 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 57 : buf_find_offset_of_char(buf_t *buf, char ch)
852 : {
853 57 : chunk_t *chunk;
854 57 : ptrdiff_t offset = 0;
855 57 : tor_assert(buf->datalen <= BUF_MAX_LEN);
856 65 : for (chunk = buf->head; chunk; chunk = chunk->next) {
857 57 : char *cp = memchr(chunk->data, ch, chunk->datalen);
858 57 : if (cp)
859 49 : return offset + (cp - chunk->data);
860 : else
861 8 : 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 74 : buf_get_line(buf_t *buf, char *data_out, size_t *data_len)
875 : {
876 74 : size_t sz;
877 74 : ptrdiff_t offset;
878 :
879 74 : if (!buf->head)
880 : return 0;
881 :
882 57 : offset = buf_find_offset_of_char(buf, '\n');
883 57 : if (offset < 0)
884 : return 0;
885 49 : sz = (size_t) offset;
886 49 : if (sz+2 > *data_len) {
887 1 : *data_len = sz + 2;
888 1 : return -1;
889 : }
890 48 : buf_get_bytes(buf, data_out, sz+1);
891 48 : data_out[sz+1] = '\0';
892 48 : *data_len = sz+1;
893 48 : return 1;
894 : }
895 :
896 : /** Set *<b>output</b> to contain a copy of the data in *<b>input</b> */
897 : int
898 4 : buf_set_to_copy(buf_t **output,
899 : const buf_t *input)
900 : {
901 4 : if (*output)
902 2 : buf_free(*output);
903 4 : *output = buf_copy(input);
904 4 : return 0;
905 : }
906 :
907 : /** Log an error and exit if <b>buf</b> is corrupted.
908 : */
909 : void
910 863 : buf_assert_ok(buf_t *buf)
911 : {
912 863 : tor_assert(buf);
913 863 : tor_assert(buf->magic == BUFFER_MAGIC);
914 :
915 863 : if (! buf->head) {
916 841 : tor_assert(!buf->tail);
917 841 : tor_assert(buf->datalen == 0);
918 : } else {
919 22 : chunk_t *ch;
920 22 : size_t total = 0;
921 22 : tor_assert(buf->tail);
922 49 : for (ch = buf->head; ch; ch = ch->next) {
923 27 : total += ch->datalen;
924 27 : tor_assert(ch->datalen <= ch->memlen);
925 27 : tor_assert(ch->datalen <= BUF_MAX_LEN);
926 27 : tor_assert(ch->data >= &ch->mem[0]);
927 27 : tor_assert(ch->data <= &ch->mem[0]+ch->memlen);
928 27 : 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 27 : tor_assert(ch->data+ch->datalen <= &ch->mem[0] + ch->memlen);
938 27 : if (!ch->next)
939 22 : tor_assert(ch == buf->tail);
940 : }
941 22 : tor_assert(buf->datalen == total);
942 : }
943 863 : }
|
