buffers.c 31 KB

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