buffers.c 29.4 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
2
/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
3
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4
 * Copyright (c) 2007-2017, 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
#define BUFFERS_PRIVATE
22
23
#include "orconfig.h"
#include <stddef.h>
Sebastian Hahn's avatar
Sebastian Hahn committed
24
#include "buffers.h"
25
26
#include "compat.h"
#include "compress.h"
27
#include "util.h"
28
#include "torint.h"
29
#include "torlog.h"
30
31
32
33
#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif

34
//#define PARANOIA
35

36
#ifdef PARANOIA
37
38
/** Helper: If PARANOIA is defined, assert that the buffer in local variable
 * <b>buf</b> is well-formed. */
39
#define check() STMT_BEGIN buf_assert_ok(buf); STMT_END
40
#else
41
#define check() STMT_NIL
42
#endif /* defined(PARANOIA) */
43

44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/* 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.
61
 */
62

63
64
/* Chunk manipulation functions */

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

67
/* We leave this many NUL bytes at the end of the buffer. */
68
69
70
#ifdef DISABLE_MEMORY_SENTINELS
#define SENTINEL_LEN 0
#else
71
#define SENTINEL_LEN 4
72
#endif
73
74
75
76

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

77
78
/** Return the number of bytes needed to allocate a chunk to hold
 * <b>memlen</b> bytes. */
79
#define CHUNK_ALLOC_SIZE(memlen) (CHUNK_OVERHEAD + (memlen))
80
81
/** Return the number of usable bytes in a chunk allocated with
 * malloc(<b>memlen</b>). */
82
83
84
85
#define CHUNK_SIZE_WITH_ALLOC(memlen) ((memlen) - CHUNK_OVERHEAD)

#define DEBUG_SENTINEL

86
#if defined(DEBUG_SENTINEL) && !defined(DISABLE_MEMORY_SENTINELS)
87
88
89
90
91
#define DBG_S(s) s
#else
#define DBG_S(s) (void)0
#endif

92
93
94
#ifdef DISABLE_MEMORY_SENTINELS
#define CHUNK_SET_SENTINEL(chunk, alloclen) STMT_NIL
#else
95
96
97
98
99
100
#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)
101
#endif /* defined(DISABLE_MEMORY_SENTINELS) */
102
103
104

/** Move all bytes stored in <b>chunk</b> to the front of <b>chunk</b>->mem,
 * to free up space at the end. */
105
static inline void
106
chunk_repack(chunk_t *chunk)
107
{
108
109
110
111
  if (chunk->datalen && chunk->data != &chunk->mem[0]) {
    memmove(chunk->mem, chunk->data, chunk->datalen);
  }
  chunk->data = &chunk->mem[0];
112
113
}

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

146
147
/** 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. */
148
static inline chunk_t *
149
150
151
chunk_grow(chunk_t *chunk, size_t sz)
{
  off_t offset;
152
153
154
  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);
155
156
  tor_assert(sz > chunk->memlen);
  offset = chunk->data - chunk->mem;
157
  chunk = tor_realloc(chunk, new_alloc);
158
159
  chunk->memlen = sz;
  chunk->data = chunk->mem + offset;
160
#ifdef DEBUG_CHUNK_ALLOC
161
162
  tor_assert(chunk->DBG_alloc == orig_alloc);
  chunk->DBG_alloc = new_alloc;
163
#endif
164
165
  total_bytes_allocated_in_chunks += new_alloc - orig_alloc;
  CHUNK_SET_SENTINEL(chunk, new_alloc);
166
  return chunk;
167
168
}

169
170
/** Every chunk should take up at least this many bytes. */
#define MIN_CHUNK_ALLOC 256
171
/** No chunk should take up more than this many bytes. */
172
173
174
175
#define MAX_CHUNK_ALLOC 65536

/** Return the allocation size we'd like to use to hold <b>target</b>
 * bytes. */
176
177
size_t
buf_preferred_chunk_size(size_t target)
178
{
179
  tor_assert(target <= SIZE_T_CEILING - CHUNK_OVERHEAD);
180
181
  if (CHUNK_ALLOC_SIZE(target) >= MAX_CHUNK_ALLOC)
    return CHUNK_ALLOC_SIZE(target);
182
183
184
  size_t sz = MIN_CHUNK_ALLOC;
  while (CHUNK_SIZE_WITH_ALLOC(sz) < target) {
    sz <<= 1;
185
  }
186
  return sz;
187
188
}

189
190
191
/** 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>.
192
193
194
195
196
 *
 * 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.
197
 */
198
void
199
buf_pullup(buf_t *buf, size_t bytes, const char **head_out, size_t *len_out)
200
201
202
{
  chunk_t *dest, *src;
  size_t capacity;
203
204
205
  if (!buf->head) {
    *head_out = NULL;
    *len_out = 0;
206
    return;
207
  }
208

209
210
211
212
  check();
  if (buf->datalen < bytes)
    bytes = buf->datalen;

213
  capacity = bytes;
214
215
216
  if (buf->head->datalen >= bytes) {
    *head_out = buf->head->data;
    *len_out = buf->head->datalen;
217
    return;
218
  }
219

220
221
  if (buf->head->memlen >= capacity) {
    /* We don't need to grow the first chunk, but we might need to repack it.*/
222
223
    size_t needed = capacity - buf->head->datalen;
    if (CHUNK_REMAINING_CAPACITY(buf->head) < needed)
224
      chunk_repack(buf->head);
225
    tor_assert(CHUNK_REMAINING_CAPACITY(buf->head) >= needed);
226
  } else {
227
228
229
230
    chunk_t *newhead;
    size_t newsize;
    /* We need to grow the chunk. */
    chunk_repack(buf->head);
231
    newsize = CHUNK_SIZE_WITH_ALLOC(buf_preferred_chunk_size(capacity));
232
233
234
235
236
237
    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;
238
    }
239
240
  }

241
242
243
244
245
  dest = buf->head;
  while (dest->datalen < bytes) {
    size_t n = bytes - dest->datalen;
    src = dest->next;
    tor_assert(src);
246
    if (n >= src->datalen) {
247
248
249
250
251
      memcpy(CHUNK_WRITE_PTR(dest), src->data, src->datalen);
      dest->datalen += src->datalen;
      dest->next = src->next;
      if (buf->tail == src)
        buf->tail = dest;
252
      buf_chunk_free_unchecked(src);
253
254
255
256
257
258
259
    } else {
      memcpy(CHUNK_WRITE_PTR(dest), src->data, n);
      dest->datalen += n;
      src->data += n;
      src->datalen -= n;
      tor_assert(dest->datalen == bytes);
    }
260
  }
261
262

  check();
263
264
  *head_out = buf->head->data;
  *len_out = buf->head->datalen;
265
266
}

267
#ifdef TOR_UNIT_TESTS
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
/* 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 */
  if (!cp || sz <= 0) {
    return NULL;
  }

  tor_assert(sz < SSIZE_T_CEILING);

  /* Allocate a buffer */
  buf_t *buf = buf_new_with_capacity(sz);
  tor_assert(buf);
285
  buf_assert_ok(buf);
286
287
288
289
290
291
  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);
292
  buf_assert_ok(buf);
293
294
295
296
297
298
299
300
301
  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];
302
  buf_assert_ok(buf);
303
304
305
306
307
308
309
310
311
312
313

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

316
/** Remove the first <b>n</b> bytes from buf. */
317
void
318
buf_drain(buf_t *buf, size_t n)
319
{
Roger Dingledine's avatar
Roger Dingledine committed
320
  tor_assert(buf->datalen >= n);
321
322
323
324
325
326
327
328
329
330
331
332
333
334
  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;
335
      buf_chunk_free_unchecked(victim);
336
    }
337
  }
338
  check();
339
340
}

341
342
/** Create and return a new buf with default chunk capacity <b>size</b>.
 */
343
buf_t *
344
345
buf_new_with_capacity(size_t size)
{
346
  buf_t *b = buf_new();
347
  b->default_chunk_size = buf_preferred_chunk_size(size);
348
  return b;
349
}
Roger Dingledine's avatar
Roger Dingledine committed
350

351
/** Allocate and return a new buffer with default capacity. */
352
353
buf_t *
buf_new(void)
354
{
355
356
357
358
  buf_t *buf = tor_malloc_zero(sizeof(buf_t));
  buf->magic = BUFFER_MAGIC;
  buf->default_chunk_size = 4096;
  return buf;
359
}
Roger Dingledine's avatar
Roger Dingledine committed
360

361
362
363
364
365
366
size_t
buf_get_default_chunk_size(const buf_t *buf)
{
  return buf->default_chunk_size;
}

367
/** Remove all data from <b>buf</b>. */
368
369
void
buf_clear(buf_t *buf)
370
{
371
  chunk_t *chunk, *next;
372
  buf->datalen = 0;
373
374
  for (chunk = buf->head; chunk; chunk = next) {
    next = chunk->next;
375
    buf_chunk_free_unchecked(chunk);
376
377
  }
  buf->head = buf->tail = NULL;
378
}
Roger Dingledine's avatar
Roger Dingledine committed
379

Roger Dingledine's avatar
Roger Dingledine committed
380
/** Return the number of bytes stored in <b>buf</b> */
Andrea Shepard's avatar
Andrea Shepard committed
381
382
MOCK_IMPL(size_t,
buf_datalen, (const buf_t *buf))
383
384
{
  return buf->datalen;
Roger Dingledine's avatar
Roger Dingledine committed
385
386
}

387
/** Return the total length of all chunks used in <b>buf</b>. */
388
size_t
389
buf_allocation(const buf_t *buf)
390
{
391
392
393
  size_t total = 0;
  const chunk_t *chunk;
  for (chunk = buf->head; chunk; chunk = chunk->next) {
394
    total += CHUNK_ALLOC_SIZE(chunk->memlen);
395
396
  }
  return total;
397
398
}

399
400
401
402
/** 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)
403
{
404
405
406
407
  if (!buf->tail)
    return 0;
  else
    return CHUNK_REMAINING_CAPACITY(buf->tail);
408
409
}

410
/** Release storage held by <b>buf</b>. */
411
412
413
void
buf_free(buf_t *buf)
{
414
415
  if (!buf)
    return;
416

417
418
419
420
421
  buf_clear(buf);
  buf->magic = 0xdeadbeef;
  tor_free(buf);
}

422
423
424
425
426
/** 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));
427
  total_bytes_allocated_in_chunks += CHUNK_ALLOC_SIZE(in_chunk->memlen);
428
429
430
#ifdef DEBUG_CHUNK_ALLOC
  newch->DBG_alloc = CHUNK_ALLOC_SIZE(in_chunk->memlen);
#endif
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
  newch->next = NULL;
  if (in_chunk->data) {
    off_t offset = in_chunk->data - in_chunk->mem;
    newch->data = newch->mem + offset;
  }
  return newch;
}

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

459
460
461
/** 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. */
462
chunk_t *
463
buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped)
464
465
{
  chunk_t *chunk;
466

467
  if (CHUNK_ALLOC_SIZE(capacity) < buf->default_chunk_size) {
468
    chunk = chunk_new_with_alloc_size(buf->default_chunk_size);
469
470
  } else if (capped && CHUNK_ALLOC_SIZE(capacity) > MAX_CHUNK_ALLOC) {
    chunk = chunk_new_with_alloc_size(MAX_CHUNK_ALLOC);
471
  } else {
472
    chunk = chunk_new_with_alloc_size(buf_preferred_chunk_size(capacity));
473
  }
474

475
  chunk->inserted_time = (uint32_t)monotime_coarse_absolute_msec();
476

477
478
479
480
481
482
483
  if (buf->tail) {
    tor_assert(buf->head);
    buf->tail->next = chunk;
    buf->tail = chunk;
  } else {
    tor_assert(!buf->head);
    buf->head = buf->tail = chunk;
484
  }
485
486
  check();
  return chunk;
Roger Dingledine's avatar
Roger Dingledine committed
487
488
}

489
/** Return the age of the oldest chunk in the buffer <b>buf</b>, in
490
491
 * milliseconds.  Requires the current monotonic time, in truncated msec,
 * as its input <b>now</b>.
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
 */
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;
}

509
/** Read up to <b>at_most</b> bytes from the socket <b>fd</b> into
510
 * <b>chunk</b> (which must be on <b>buf</b>). If we get an EOF, set
511
512
 * *<b>reached_eof</b> to 1.  Return -1 on error, 0 on eof or blocking,
 * and the number of bytes read otherwise. */
513
static inline int
514
read_to_chunk(buf_t *buf, chunk_t *chunk, tor_socket_t fd, size_t at_most,
515
              int *reached_eof, int *socket_error)
516
{
517
  ssize_t read_result;
518
519
  if (at_most > CHUNK_REMAINING_CAPACITY(chunk))
    at_most = CHUNK_REMAINING_CAPACITY(chunk);
520
  read_result = tor_socket_recv(fd, CHUNK_WRITE_PTR(chunk), at_most, 0);
521

522
  if (read_result < 0) {
523
    int e = tor_socket_errno(fd);
524
    if (!ERRNO_IS_EAGAIN(e)) { /* it's a real error */
525
#ifdef _WIN32
526
527
528
      if (e == WSAENOBUFS)
        log_warn(LD_NET,"recv() failed: WSAENOBUFS. Not enough ram?");
#endif
529
      *socket_error = e;
530
531
532
533
      return -1;
    }
    return 0; /* would block. */
  } else if (read_result == 0) {
534
    log_debug(LD_NET,"Encountered eof on fd %d", (int)fd);
535
536
    *reached_eof = 1;
    return 0;
537
  } else { /* actually got bytes. */
538
    buf->datalen += read_result;
539
    chunk->datalen += read_result;
540
    log_debug(LD_NET,"Read %ld bytes. %d on inbuf.", (long)read_result,
541
              (int)buf->datalen);
542
543
    tor_assert(read_result < INT_MAX);
    return (int)read_result;
544
545
546
  }
}

Nick Mathewson's avatar
Nick Mathewson committed
547
/** Read from socket <b>s</b>, writing onto end of <b>buf</b>.  Read at most
548
549
550
 * <b>at_most</b> bytes, growing the buffer as necessary.  If recv() returns 0
 * (because of EOF), set *<b>reached_eof</b> to 1 and return 0. Return -1 on
 * error; else return the number of bytes read.
551
 */
552
/* XXXX indicate "read blocked" somehow? */
553
int
554
buf_read_from_socket(buf_t *buf, tor_socket_t s, size_t at_most,
555
556
                     int *reached_eof,
                     int *socket_error)
557
{
558
  /* XXXX It's stupid to overload the return values for these functions:
559
560
   * "error status" and "number of bytes read" are not mutually exclusive.
   */
561
562
  int r = 0;
  size_t total_read = 0;
Roger Dingledine's avatar
Roger Dingledine committed
563

564
  check();
565
  tor_assert(reached_eof);
566
  tor_assert(SOCKET_OK(s));
567

568
569
570
571
572
  if (BUG(buf->datalen >= INT_MAX))
    return -1;
  if (BUG(buf->datalen >= INT_MAX - at_most))
    return -1;

573
574
  while (at_most > total_read) {
    size_t readlen = at_most - total_read;
575
576
    chunk_t *chunk;
    if (!buf->tail || CHUNK_REMAINING_CAPACITY(buf->tail) < MIN_READ_LEN) {
577
578
579
      chunk = buf_add_chunk_with_capacity(buf, at_most, 1);
      if (readlen > chunk->memlen)
        readlen = chunk->memlen;
580
    } else {
581
582
583
584
      size_t cap = CHUNK_REMAINING_CAPACITY(buf->tail);
      chunk = buf->tail;
      if (cap < readlen)
        readlen = cap;
Roger Dingledine's avatar
Roger Dingledine committed
585
    }
586

587
    r = read_to_chunk(buf, chunk, s, readlen, reached_eof, socket_error);
588
589
590
    check();
    if (r < 0)
      return r; /* Error */
591
    tor_assert(total_read+r < INT_MAX);
592
    total_read += r;
593
594
595
    if ((size_t)r < readlen) { /* eof, block, or no more to read. */
      break;
    }
596
  }
597
  return (int)total_read;
Roger Dingledine's avatar
Roger Dingledine committed
598
599
}

600
/** Helper for buf_flush_to_socket(): try to write <b>sz</b> bytes from chunk
601
602
603
 * <b>chunk</b> of buffer <b>buf</b> onto socket <b>s</b>.  On success, deduct
 * the bytes written from *<b>buf_flushlen</b>.  Return the number of bytes
 * written on success, 0 on blocking, -1 on failure.
604
 */
605
static inline int
606
flush_chunk(tor_socket_t s, buf_t *buf, chunk_t *chunk, size_t sz,
607
            size_t *buf_flushlen)
608
{
609
  ssize_t write_result;
610

611
612
  if (sz > chunk->datalen)
    sz = chunk->datalen;
613
  write_result = tor_socket_send(s, chunk->data, sz, 0);
614

615
616
617
  if (write_result < 0) {
    int e = tor_socket_errno(s);
    if (!ERRNO_IS_EAGAIN(e)) { /* it's a real error */
618
#ifdef _WIN32
619
620
621
      if (e == WSAENOBUFS)
        log_warn(LD_NET,"write() failed: WSAENOBUFS. Not enough ram?");
#endif
622
623
      return -1;
    }
624
    log_debug(LD_NET,"write() would block, returning.");
625
626
627
    return 0;
  } else {
    *buf_flushlen -= write_result;
628
    buf_drain(buf, write_result);
629
630
    tor_assert(write_result < INT_MAX);
    return (int)write_result;
631
632
633
  }
}

Roger Dingledine's avatar
Roger Dingledine committed
634
/** Write data from <b>buf</b> to the socket <b>s</b>.  Write at most
635
 * <b>sz</b> bytes, decrement *<b>buf_flushlen</b> by
Roger Dingledine's avatar
Roger Dingledine committed
636
637
638
 * the number of bytes actually written, and remove the written bytes
 * from the buffer.  Return the number of bytes written on success,
 * -1 on failure.  Return 0 if write() would block.
639
 */
640
int
641
buf_flush_to_socket(buf_t *buf, tor_socket_t s, size_t sz,
642
                    size_t *buf_flushlen)
643
{
644
  /* XXXX It's stupid to overload the return values for these functions:
645
646
   * "error status" and "number of bytes flushed" are not mutually exclusive.
   */
647
648
  int r;
  size_t flushed = 0;
649
  tor_assert(buf_flushlen);
650
  tor_assert(SOCKET_OK(s));
651
  tor_assert(*buf_flushlen <= buf->datalen);
652
  tor_assert(sz <= *buf_flushlen);
Roger Dingledine's avatar
Roger Dingledine committed
653

654
  check();
655
656
657
658
659
660
661
  while (sz) {
    size_t flushlen0;
    tor_assert(buf->head);
    if (buf->head->datalen >= sz)
      flushlen0 = sz;
    else
      flushlen0 = buf->head->datalen;
662

663
    r = flush_chunk(s, buf, buf->head, flushlen0, buf_flushlen);
664
    check();
665
    if (r < 0)
666
667
      return r;
    flushed += r;
668
    sz -= r;
669
670
    if (r == 0 || (size_t)r < flushlen0) /* can't flush any more now. */
      break;
671
  }
672
673
  tor_assert(flushed < INT_MAX);
  return (int)flushed;
674
}
675

Roger Dingledine's avatar
Roger Dingledine committed
676
677
678
/** Append <b>string_len</b> bytes from <b>string</b> to the end of
 * <b>buf</b>.
 *
679
680
 * Return the new length of the buffer on success, -1 on failure.
 */
681
int
682
buf_add(buf_t *buf, const char *string, size_t string_len)
683
{
684
  if (!string_len)
685
    return (int)buf->datalen;
686
  check();
Roger Dingledine's avatar
Roger Dingledine committed
687

688
689
690
691
692
  if (BUG(buf->datalen >= INT_MAX))
    return -1;
  if (BUG(buf->datalen >= INT_MAX - string_len))
    return -1;

693
694
695
696
697
698
  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);
699
700
701
702
703
704
705
    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;
706
  }
707

708
  check();
709
710
  tor_assert(buf->datalen < INT_MAX);
  return (int)buf->datalen;
711
712
}

713
714
/** Helper: copy the first <b>string_len</b> bytes from <b>buf</b>
 * onto <b>string</b>.
715
 */
716
void
717
buf_peek(const buf_t *buf, char *string, size_t string_len)
718
{
719
  chunk_t *chunk;
Roger Dingledine's avatar
Roger Dingledine committed
720

Roger Dingledine's avatar
Roger Dingledine committed
721
  tor_assert(string);
722
723
  /* make sure we don't ask for too much */
  tor_assert(string_len <= buf->datalen);
724
  /* buf_assert_ok(buf); */
Roger Dingledine's avatar
Roger Dingledine committed
725

726
727
728
729
730
731
732
733
734
735
  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;
736
737
738
  }
}

739
740
741
/** 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.
742
 */
743
int
744
buf_get_bytes(buf_t *buf, char *string, size_t string_len)
745
746
747
748
749
750
{
  /* 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. */

751
  check();
752
  buf_peek(buf, string, string_len);
753
  buf_drain(buf, string_len);
754
  check();
755
756
  tor_assert(buf->datalen < INT_MAX);
  return (int)buf->datalen;
Roger Dingledine's avatar
Roger Dingledine committed
757
758
}

759
760
/** 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.
761
762
763
 * Return the number of bytes actually copied.
 */
int
764
buf_move_to_buf(buf_t *buf_out, buf_t *buf_in, size_t *buf_flushlen)
765
{
766
  /* We can do way better here, but this doesn't turn up in any profiles. */
767
768
  char b[4096];
  size_t cp, len;
769
770
771
772
773
774

  if (BUG(buf_out->datalen >= INT_MAX))
    return -1;
  if (BUG(buf_out->datalen >= INT_MAX - *buf_flushlen))
    return -1;

775
776
777
778
779
  len = *buf_flushlen;
  if (len > buf_in->datalen)
    len = buf_in->datalen;

  cp = len; /* Remember the number of bytes we intend to copy. */
780
  tor_assert(cp < INT_MAX);
781
782
783
784
785
  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;
786
787
    buf_get_bytes(buf_in, b, n);
    buf_add(buf_out, b, n);
788
789
790
    len -= n;
  }
  *buf_flushlen -= cp;
791
  return (int)cp;
792
793
}

794
/** Internal structure: represents a position in a buffer. */
795
typedef struct buf_pos_t {
796
  const chunk_t *chunk; /**< Which chunk are we pointing to? */
797
  int pos;/**< Which character inside the chunk's data are we pointing to? */
798
  size_t chunk_pos; /**< Total length of all previous chunks. */
799
} buf_pos_t;
800

801
/** Initialize <b>out</b> to point to the first character of <b>buf</b>.*/
802
static void
803
buf_pos_init(const buf_t *buf, buf_pos_t *out)
804
805
806
{
  out->chunk = buf->head;
  out->pos = 0;
807
  out->chunk_pos = 0;
808
809
}

810
811
812
/** 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. */
813
static off_t
814
buf_find_pos_of_char(char ch, buf_pos_t *out)
815
{
816
  const chunk_t *chunk;
817
  int pos;
818
  tor_assert(out);
819
  if (out->chunk) {
820
821
822
823
    if (out->chunk->datalen) {
      tor_assert(out->pos < (off_t)out->chunk->datalen);
    } else {
      tor_assert(out->pos == 0);
824
825
    }
  }
826
  pos = out->pos;
827
  for (chunk = out->chunk; chunk; chunk = chunk->next) {
828
    char *cp = memchr(chunk->data+pos, ch, chunk->datalen - pos);
829
830
    if (cp) {
      out->chunk = chunk;
831
832
      tor_assert(cp - chunk->data < INT_MAX);
      out->pos = (int)(cp - chunk->data);
833
      return out->chunk_pos + out->pos;
834
    } else {
835
      out->chunk_pos += chunk->datalen;
836
837
838
839
840
841
      pos = 0;
    }
  }
  return -1;
}

842
/** Advance <b>pos</b> by a single character, if there are any more characters
Nick Mathewson's avatar
Nick Mathewson committed
843
 * in the buffer.  Returns 0 on success, -1 on failure. */
844
static inline int
845
846
buf_pos_inc(buf_pos_t *pos)
{
847
  ++pos->pos;
848
  if (pos->pos == (off_t)pos->chunk->datalen) {
849
850
    if (!pos->chunk->next)
      return -1;
851
    pos->chunk_pos += pos->chunk->datalen;
852
853
854
    pos->chunk = pos->chunk->next;
    pos->pos = 0;
  }
855
  return 0;
856
857
}

858
859
/** Return true iff the <b>n</b>-character string in <b>s</b> appears
 * (verbatim) at <b>pos</b>. */
860
static int
861
buf_matches_at_pos(const buf_pos_t *pos, const char *s, size_t n)
862
863
{
  buf_pos_t p;
864
865
866
  if (!n)
    return 1;

867
  memcpy(&p, pos, sizeof(p));
868

869
  while (1) {
870
    char ch = p.chunk->data[p.pos];
871
872
873
    if (ch != *s)
      return 0;
    ++s;
874
875
876
877
878
    /* 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;
879
    if (buf_pos_inc(&p)<0)
880
881
882
883
      return 0;
  }
}

884
885
/** 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. */
886
int
887
buf_find_string_offset(const buf_t *buf, const char *s, size_t n)
888
889
890
{
  buf_pos_t pos;
  buf_pos_init(buf, &pos);
891
892
  while (buf_find_pos_of_char(*s, &pos) >= 0) {
    if (buf_matches_at_pos(&pos, s, n)) {
893
894
      tor_assert(pos.chunk_pos + pos.pos < INT_MAX);
      return (int)(pos.chunk_pos + pos.pos);
895
    } else {
896
      if (buf_pos_inc(&pos)<0)
897
898
899
900
901
902
        return -1;
    }
  }
  return -1;
}

903
/** Return 1 iff <b>buf</b> starts with <b>cmd</b>. <b>cmd</b> must be a null
904
 * terminated string, of no more than PEEK_BUF_STARTSWITH_MAX bytes. */
905
int
906
buf_peek_startswith(const buf_t *buf, const char *cmd)
907
{
908
  char tmp[PEEK_BUF_STARTSWITH_MAX];
Nick Mathewson's avatar
Nick Mathewson committed
909
  size_t clen = strlen(cmd);
910
911
912
913
  if (BUG(clen > sizeof(tmp)))
    return 0;
  if (buf->datalen < clen)
    return 0;
914
  buf_peek(buf, tmp, clen);
915
  return fast_memeq(tmp, cmd, clen);
916
917
}

918
919
/** 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. */
920
static off_t
921
922
923
buf_find_offset_of_char(buf_t *buf, char ch)
{
  chunk_t *chunk;
924
  off_t offset = 0;
925
926
927
928
929
930
931
932
933
934
  for (chunk = buf->head; chunk; chunk = chunk<