mempool.c 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552
  1. /* Copyright 2007 Nick Mathewson */
  2. /* See LICENSE for licensing information */
  3. /* $Id$ */
  4. #if 1
  5. /* Tor dependencies */
  6. #include "orconfig.h"
  7. #endif
  8. #include <stdlib.h>
  9. #include <string.h>
  10. #define MEMPOOL_PRIVATE
  11. #include "mempool.h"
  12. /* OVERVIEW:
  13. *
  14. * This is an implementation of memory pools for Tor cells. It may be
  15. * useful for you too.
  16. *
  17. * Generally, a memory pool is an allocation strategy optimized for large
  18. * numbers of identically-sized objects. Rather than the elaborate arena
  19. * and coalescing strategies you need to get good performance for a
  20. * general-purpose malloc(), pools use a series of large memory "chunks",
  21. * each of which is carved into a bunch of smaller "items" or
  22. * "allocations".
  23. *
  24. * To get decent performance, you need to:
  25. * - Minimize the number of times you hit the underlying allocator.
  26. * - Try to keep accesses as local in memory as possible.
  27. * - Try to keep the common case fast.
  28. *
  29. * Our implementation uses three lists of chunks per pool. Each chunk can
  30. * be either "full" (no more room for items); "empty" (no items); or
  31. * "used" (not full, not empty). There are independent doubly-linked
  32. * lists for each state.
  33. *
  34. * CREDIT:
  35. *
  36. * I wrote this after looking at 3 or 4 other pooling allocators, but
  37. * without copying. The strategy this most resembles (which is funny,
  38. * since that's the one I looked at longest ago) is the pool allocator
  39. * underlying Python's obmalloc code. Major differences from obmalloc's
  40. * pools are:
  41. * - We don't even try to be threadsafe.
  42. * - We only handle objects of one size.
  43. * - Our list of empty chunks is doubly-linked, not singly-linked.
  44. * (This could change pretty easily; it's only doubly-linked for
  45. * consistency.)
  46. * - We keep a list of full chunks (so we can have a "nuke everything"
  47. * function). Obmalloc's pools leave full chunks to float unanchored.
  48. *
  49. * [XXXX020 Another way to support 'nuke everything' would be to keep
  50. * _all_ the chunks in a doubly-linked-list. This would have more
  51. * space overhead per chunk, but less pointer manipulation overhead
  52. * than the current approach.]
  53. *
  54. * LIMITATIONS:
  55. * - Not even slightly threadsafe.
  56. * - Likes to have lots of items per chunks.
  57. * - One pointer overhead per allocated thing. (The alternative is
  58. * something like glib's use of an RB-tree to keep track of what
  59. * chunk any given piece of memory is in.)
  60. * - Only aligns allocated things to void* level: redefign ALIGNMENT_TYPE
  61. * if you need doubles.
  62. * - Could probably be optimized a bit; the representation contains
  63. * a bit more info than it really needs to have.
  64. * - probably, chunks should always be a power of 2.
  65. */
  66. #if 1
  67. /* Tor dependencies */
  68. #include "orconfig.h"
  69. #include "util.h"
  70. #include "compat.h"
  71. #include "log.h"
  72. #define ALLOC(x) tor_malloc(x)
  73. #define FREE(x) tor_free(x)
  74. #define ASSERT(x) tor_assert(x)
  75. #undef ALLOC_CAN_RETURN_NULL
  76. #define TOR
  77. /* End Tor dependencies */
  78. #else
  79. /* If you're not building this as part of Tor, you'll want to define the
  80. * following macros. For now, these should do as defaults.
  81. */
  82. #include <assert.h>
  83. #define PREDICT_UNLIKELY(x) (x)
  84. #define PREDICT_LIKELY(x) (x)
  85. #define ALLOC(x) malloc(x)
  86. #define FREE(x) free(x)
  87. #define STRUCT_OFFSET(tp, member) \
  88. ((off_t) (((char*)&((tp*)0)->member)-(char*)0))
  89. #define ASSERT(x) assert(x)
  90. #define ALLOC_CAN_RETURN_NULL
  91. #endif
  92. /* Tuning parameters */
  93. /** Largest type that we need to ensure returned memory items are aligned to.
  94. * Change this to "double" if we need to be safe for structs with doubles. */
  95. #define ALIGNMENT_TYPE void *
  96. /** Increment that we need to align allocated. */
  97. #define ALIGNMENT sizeof(ALIGNMENT_TYPE)
  98. /** Largest memory chunk that we should allocate. */
  99. #define MAX_CHUNK (8*(1L<<20))
  100. /** Smallest memory chunk size that we should allocate. */
  101. #define MIN_CHUNK 4096
  102. typedef struct mp_allocated_t mp_allocated_t;
  103. typedef struct mp_chunk_t mp_chunk_t;
  104. /** Holds a single allocated item, allocated as part of a chunk. */
  105. struct mp_allocated_t {
  106. /** The chunk that this item is allocated in. This adds overhead to each
  107. * allocated item, thus making this implementation inappropriate for
  108. * very small items. */
  109. mp_chunk_t *in_chunk;
  110. union {
  111. /** If this item is free, the next item on the free list. */
  112. mp_allocated_t *next_free;
  113. /** If this item is not free, the actual memory contents of this item.
  114. * (Not actual size.) */
  115. char mem[1];
  116. /** An extra element to the union to insure correct alignment. */
  117. ALIGNMENT_TYPE _dummy;
  118. } u;
  119. };
  120. /** 'Magic' value used to detect memory corruption. */
  121. #define MP_CHUNK_MAGIC 0x09870123
  122. /** A chunk of memory. Chunks come from malloc; we use them */
  123. struct mp_chunk_t {
  124. unsigned long magic; /**< Must be MP_CHUNK_MAGIC if this chunk is valid. */
  125. mp_chunk_t *next; /**< The next free, used, or full chunk in sequence. */
  126. mp_chunk_t *prev; /**< The previous free, used, or full chunk in sequence. */
  127. mp_pool_t *pool; /**< The pool that this chunk is part of. */
  128. /** First free item in the freelist for this chunk. Note that this may be
  129. * NULL even if this chunk is not at capacity: if so, the free memory at
  130. * next_mem has not yet been carved into items.
  131. */
  132. mp_allocated_t *first_free;
  133. int n_allocated; /**< Number of currently allocated items in this chunk. */
  134. int capacity; /**< Number of items that can be fit into this chunk. */
  135. size_t mem_size; /**< Number of usable bytes in mem. */
  136. char *next_mem; /**< Pointer into part of <b>mem</b> not yet carved up. */
  137. char mem[1]; /**< Storage for this chunk. (Not actual size.) */
  138. };
  139. /** Number of extra bytes needed beyond mem_size to allocate a chunk. */
  140. #define CHUNK_OVERHEAD (sizeof(mp_chunk_t)-1)
  141. /** Given a pointer to a mp_allocated_t, return a pointer to the memory
  142. * item it holds. */
  143. #define A2M(a) (&(a)->u.mem)
  144. /** Given a pointer to a memory_item_t, return a pointer to its enclosing
  145. * mp_allocated_t. */
  146. #define M2A(p) ( ((char*)p) - STRUCT_OFFSET(mp_allocated_t, u.mem) )
  147. #ifdef ALLOC_CAN_RETURN_NULL
  148. /** If our ALLOC() macro can return NULL, check whether <b>x</b> is NULL,
  149. * and if so, return NULL. */
  150. #define CHECK_ALLOC(x) \
  151. if (PREDICT_UNLIKELY(!x)) { return NULL; }
  152. #else
  153. /** If our ALLOC() macro can't return NULL, do nothing. */
  154. #define CHECK_ALLOC(x)
  155. #endif
  156. /** Helper: Allocate and return a new memory chunk for <b>pool</b>. Does not
  157. * link the chunk into any list. */
  158. static mp_chunk_t *
  159. mp_chunk_new(mp_pool_t *pool)
  160. {
  161. size_t sz = pool->new_chunk_capacity * pool->item_alloc_size;
  162. mp_chunk_t *chunk = ALLOC(CHUNK_OVERHEAD + sz);
  163. CHECK_ALLOC(chunk);
  164. memset(chunk, 0, sizeof(mp_chunk_t)); /* Doesn't clear the whole thing. */
  165. chunk->magic = MP_CHUNK_MAGIC;
  166. chunk->capacity = pool->new_chunk_capacity;
  167. chunk->mem_size = sz;
  168. chunk->next_mem = chunk->mem;
  169. chunk->pool = pool;
  170. return chunk;
  171. }
  172. /** Return an newly allocated item from <b>pool</b>. */
  173. void *
  174. mp_pool_get(mp_pool_t *pool)
  175. {
  176. mp_chunk_t *chunk;
  177. mp_allocated_t *allocated;
  178. if (PREDICT_LIKELY(pool->used_chunks != NULL)) {
  179. /* Common case: there is some chunk that is neither full nor empty. Use
  180. * that one. (We can't use the full ones, obviously, and we should fill
  181. * up the used ones before we start on any empty ones. */
  182. chunk = pool->used_chunks;
  183. } else if (pool->empty_chunks) {
  184. /* We have no used chunks, but we have an empty chunk that we haven't
  185. * freed yet: use that. (We pull from the front of the list, which should
  186. * get us the most recently emptied chunk.) */
  187. chunk = pool->empty_chunks;
  188. /* Remove the chunk from the empty list. */
  189. pool->empty_chunks = chunk->next;
  190. if (chunk->next)
  191. chunk->next->prev = NULL;
  192. /* Put the chunk on the 'used' list*/
  193. chunk->next = pool->used_chunks;
  194. if (chunk->next)
  195. chunk->next->prev = chunk;
  196. pool->used_chunks = chunk;
  197. ASSERT(!chunk->prev);
  198. --pool->n_empty_chunks;
  199. if (pool->n_empty_chunks < pool->min_empty_chunks)
  200. pool->min_empty_chunks = pool->n_empty_chunks;
  201. } else {
  202. /* We have no used or empty chunks: allocate a new chunk. */
  203. chunk = mp_chunk_new(pool);
  204. CHECK_ALLOC(chunk);
  205. /* Add the new chunk to the used list. */
  206. chunk->next = pool->used_chunks;
  207. if (chunk->next)
  208. chunk->next->prev = chunk;
  209. pool->used_chunks = chunk;
  210. ASSERT(!chunk->prev);
  211. }
  212. ASSERT(chunk->n_allocated < chunk->capacity);
  213. if (chunk->first_free) {
  214. /* If there's anything on the chunk's freelist, unlink it and use it. */
  215. allocated = chunk->first_free;
  216. chunk->first_free = allocated->u.next_free;
  217. allocated->u.next_free = NULL; /* For debugging; not really needed. */
  218. ASSERT(allocated->in_chunk == chunk);
  219. } else {
  220. /* Otherwise, the chunk had better have some free space left on it. */
  221. ASSERT(chunk->next_mem + pool->item_alloc_size <=
  222. chunk->mem + chunk->mem_size);
  223. /* Good, it did. Let's carve off a bit of that free space, and use
  224. * that. */
  225. allocated = (void*)chunk->next_mem;
  226. chunk->next_mem += pool->item_alloc_size;
  227. allocated->in_chunk = chunk;
  228. allocated->u.next_free = NULL; /* For debugging; not really needed. */
  229. }
  230. ++chunk->n_allocated;
  231. if (PREDICT_UNLIKELY(chunk->n_allocated == chunk->capacity)) {
  232. /* This chunk just became full. */
  233. ASSERT(chunk == pool->used_chunks);
  234. ASSERT(chunk->prev == NULL);
  235. /* Take it off the used list. */
  236. pool->used_chunks = chunk->next;
  237. if (chunk->next)
  238. chunk->next->prev = NULL;
  239. /* Put it on the full list. */
  240. chunk->next = pool->full_chunks;
  241. if (chunk->next)
  242. chunk->next->prev = chunk;
  243. pool->full_chunks = chunk;
  244. }
  245. /* And return the memory portion of the mp_allocated_t. */
  246. return A2M(allocated);
  247. }
  248. /** Return an allocated memory item to its memory pool. */
  249. void
  250. mp_pool_release(void *item)
  251. {
  252. mp_allocated_t *allocated = (void*) M2A(item);
  253. mp_chunk_t *chunk = allocated->in_chunk;
  254. ASSERT(chunk);
  255. ASSERT(chunk->magic == MP_CHUNK_MAGIC);
  256. ASSERT(chunk->n_allocated > 0);
  257. allocated->u.next_free = chunk->first_free;
  258. chunk->first_free = allocated;
  259. if (PREDICT_UNLIKELY(chunk->n_allocated == chunk->capacity)) {
  260. /* This chunk was full and is about to be used. */
  261. mp_pool_t *pool = chunk->pool;
  262. /* unlink from the full list */
  263. if (chunk->prev)
  264. chunk->prev->next = chunk->next;
  265. if (chunk->next)
  266. chunk->next->prev = chunk->prev;
  267. if (chunk == pool->full_chunks)
  268. pool->full_chunks = chunk->next;
  269. /* link to the used list. */
  270. chunk->next = pool->used_chunks;
  271. chunk->prev = NULL;
  272. if (chunk->next)
  273. chunk->next->prev = chunk;
  274. pool->used_chunks = chunk;
  275. } else if (PREDICT_UNLIKELY(chunk->n_allocated == 1)) {
  276. /* This was used and is about to be empty. */
  277. mp_pool_t *pool = chunk->pool;
  278. /* Unlink from the used list */
  279. if (chunk->prev)
  280. chunk->prev->next = chunk->next;
  281. if (chunk->next)
  282. chunk->next->prev = chunk->prev;
  283. if (chunk == pool->used_chunks)
  284. pool->used_chunks = chunk->next;
  285. /* Link to the empty list */
  286. chunk->next = pool->empty_chunks;
  287. chunk->prev = NULL;
  288. if (chunk->next)
  289. chunk->next->prev = chunk;
  290. pool->empty_chunks = chunk;
  291. /* Reset the guts of this chunk to defragment it, in case it gets
  292. * used again. */
  293. chunk->first_free = NULL;
  294. chunk->next_mem = chunk->mem;
  295. ++pool->n_empty_chunks;
  296. }
  297. --chunk->n_allocated;
  298. }
  299. /** Allocate a new memory pool to hold items of size <b>item_size</b>. We'll
  300. * try to fit about <b>chunk_capacity</b> bytes in each chunk. */
  301. mp_pool_t *
  302. mp_pool_new(size_t item_size, size_t chunk_capacity)
  303. {
  304. mp_pool_t *pool;
  305. size_t alloc_size;
  306. pool = ALLOC(sizeof(mp_pool_t));
  307. CHECK_ALLOC(pool);
  308. memset(pool, 0, sizeof(mp_pool_t));
  309. /* First, we figure out how much space to allow per item. We'll want to
  310. * use make sure we have enough for the overhead plus the item size. */
  311. alloc_size = (size_t)(STRUCT_OFFSET(mp_allocated_t, u.mem) + item_size);
  312. /* If the item_size is less than sizeof(next_free), we need to make
  313. * the allocation bigger. */
  314. if (alloc_size < sizeof(mp_allocated_t))
  315. alloc_size = sizeof(mp_allocated_t);
  316. /* If we're not an even multiple of ALIGNMENT, round up. */
  317. if (alloc_size % ALIGNMENT) {
  318. alloc_size = alloc_size + ALIGNMENT - (alloc_size % ALIGNMENT);
  319. }
  320. if (alloc_size < ALIGNMENT)
  321. alloc_size = ALIGNMENT;
  322. ASSERT((alloc_size % ALIGNMENT) == 0);
  323. /* Now we figure out how many items fit in each chunk. We need to fit at
  324. * least 2 items per chunk. No chunk can be more than MAX_CHUNK bytes long,
  325. * or less than MIN_CHUNK. */
  326. if (chunk_capacity > MAX_CHUNK)
  327. chunk_capacity = MAX_CHUNK;
  328. /* Try to be around a power of 2 in size, since that's what allocators like
  329. * handing out. 512K-1 byte is a lot better than 512K+1 byte. */
  330. chunk_capacity = (size_t) round_to_power_of_2(chunk_capacity);
  331. while (chunk_capacity < alloc_size * 2 + CHUNK_OVERHEAD)
  332. chunk_capacity *= 2;
  333. if (chunk_capacity < MIN_CHUNK)
  334. chunk_capacity = MIN_CHUNK;
  335. pool->new_chunk_capacity = (chunk_capacity-CHUNK_OVERHEAD) / alloc_size;
  336. pool->item_alloc_size = alloc_size;
  337. log_debug(LD_MM, "Capacity is %lu, item size is %lu, alloc size is %lu",
  338. (unsigned long)pool->new_chunk_capacity,
  339. (unsigned long)pool->item_alloc_size,
  340. (unsigned long)(pool->new_chunk_capacity*pool->item_alloc_size));
  341. return pool;
  342. }
  343. /** If there are more than <b>n</b> empty chunks in <b>pool</b>, free the
  344. * excess ones that have been empty for the longest. (If <b>n</b> is less
  345. * than zero, free only empty chunks that were not used since the last
  346. * call to mp_pool_clean(), leaving only -<b>n</b>.) */
  347. void
  348. mp_pool_clean(mp_pool_t *pool, int n)
  349. {
  350. mp_chunk_t *chunk, **first_to_free;
  351. if (n < 0) {
  352. /* As said in the documentation, "negative n" means "leave an additional
  353. * -n chunks". So replace n with a positive number. */
  354. n = pool->min_empty_chunks + (-n);
  355. if (n < pool->n_empty_chunks)
  356. pool->min_empty_chunks = n;
  357. }
  358. ASSERT(n>=0);
  359. first_to_free = &pool->empty_chunks;
  360. while (*first_to_free && n > 0) {
  361. first_to_free = &(*first_to_free)->next;
  362. --n;
  363. }
  364. if (!*first_to_free)
  365. return;
  366. chunk = *first_to_free;
  367. while (chunk) {
  368. mp_chunk_t *next = chunk->next;
  369. chunk->magic = 0xdeadbeef;
  370. FREE(chunk);
  371. --pool->n_empty_chunks;
  372. chunk = next;
  373. }
  374. *first_to_free = NULL;
  375. }
  376. /** Helper: Given a list of chunks, free all the chunks in the list. */
  377. static void
  378. destroy_chunks(mp_chunk_t *chunk)
  379. {
  380. mp_chunk_t *next;
  381. while (chunk) {
  382. chunk->magic = 0xd3adb33f;
  383. next = chunk->next;
  384. FREE(chunk);
  385. chunk = next;
  386. }
  387. }
  388. /** Free all space held in <b>pool</b> This makes all pointers returned from
  389. * mp_pool_get(<b>pool</b>) invalid. */
  390. void
  391. mp_pool_destroy(mp_pool_t *pool)
  392. {
  393. destroy_chunks(pool->empty_chunks);
  394. destroy_chunks(pool->used_chunks);
  395. destroy_chunks(pool->full_chunks);
  396. memset(pool, 0xe0, sizeof(mp_pool_t));
  397. FREE(pool);
  398. }
  399. /** Helper: make sure that a given chunk list is not corrupt. */
  400. static int
  401. assert_chunks_ok(mp_pool_t *pool, mp_chunk_t *chunk, int empty, int full)
  402. {
  403. mp_allocated_t *allocated;
  404. int n = 0;
  405. if (chunk)
  406. ASSERT(chunk->prev == NULL);
  407. while (chunk) {
  408. n++;
  409. ASSERT(chunk->magic == MP_CHUNK_MAGIC);
  410. ASSERT(chunk->pool == pool);
  411. for (allocated = chunk->first_free; allocated;
  412. allocated = allocated->u.next_free) {
  413. ASSERT(allocated->in_chunk == chunk);
  414. }
  415. if (empty)
  416. ASSERT(chunk->n_allocated == 0);
  417. else if (full)
  418. ASSERT(chunk->n_allocated == chunk->capacity);
  419. else
  420. ASSERT(chunk->n_allocated > 0 && chunk->n_allocated < chunk->capacity);
  421. ASSERT(chunk->capacity == pool->new_chunk_capacity);
  422. ASSERT(chunk->mem_size ==
  423. pool->new_chunk_capacity * pool->item_alloc_size);
  424. ASSERT(chunk->next_mem >= chunk->mem &&
  425. chunk->next_mem <= chunk->mem + chunk->mem_size);
  426. if (chunk->next)
  427. ASSERT(chunk->next->prev == chunk);
  428. chunk = chunk->next;
  429. }
  430. return n;
  431. }
  432. /** Fail with an assertion if <b>pool</b> is not internally consistent. */
  433. void
  434. mp_pool_assert_ok(mp_pool_t *pool)
  435. {
  436. int n_empty;
  437. n_empty = assert_chunks_ok(pool, pool->empty_chunks, 1, 0);
  438. assert_chunks_ok(pool, pool->full_chunks, 0, 1);
  439. assert_chunks_ok(pool, pool->used_chunks, 0, 0);
  440. ASSERT(pool->n_empty_chunks == n_empty);
  441. }
  442. #ifdef TOR
  443. /** Dump information about <b>pool</b>'s memory usage to the Tor log at level
  444. * <b>severity</b>. */
  445. /*FFFF uses Tor logging functions. */
  446. void
  447. mp_pool_log_status(mp_pool_t *pool, int severity)
  448. {
  449. uint64_t bytes_used = 0;
  450. uint64_t bytes_allocated = 0;
  451. uint64_t bu = 0, ba = 0;
  452. mp_chunk_t *chunk;
  453. int n_full = 0, n_used = 0;
  454. ASSERT(pool);
  455. for (chunk = pool->empty_chunks; chunk; chunk = chunk->next) {
  456. bytes_allocated += chunk->mem_size;
  457. }
  458. log_fn(severity, LD_MM, U64_FORMAT" bytes in %d empty chunks",
  459. U64_PRINTF_ARG(bytes_used), pool->n_empty_chunks);
  460. for (chunk = pool->used_chunks; chunk; chunk = chunk->next) {
  461. ++n_used;
  462. bu += chunk->n_allocated * pool->item_alloc_size;
  463. ba += chunk->mem_size;
  464. }
  465. log_fn(severity, LD_MM, U64_FORMAT"/"U64_FORMAT
  466. " bytes in %d partially full chunks",
  467. U64_PRINTF_ARG(bu), U64_PRINTF_ARG(ba), n_used);
  468. bytes_used += bu;
  469. bytes_allocated += ba;
  470. bu = ba = 0;
  471. for (chunk = pool->full_chunks; chunk; chunk = chunk->next) {
  472. ++n_full;
  473. bu += chunk->n_allocated * pool->item_alloc_size;
  474. ba += chunk->mem_size;
  475. }
  476. log_fn(severity, LD_MM, U64_FORMAT"/"U64_FORMAT
  477. " bytes in %d full chunks",
  478. U64_PRINTF_ARG(bu), U64_PRINTF_ARG(ba), n_full);
  479. bytes_used += bu;
  480. bytes_allocated += ba;
  481. log_fn(severity, LD_MM, "Total: "U64_FORMAT"/"U64_FORMAT" bytes allocated "
  482. "for cell pools are full.",
  483. U64_PRINTF_ARG(bytes_used), U64_PRINTF_ARG(bytes_allocated));
  484. }
  485. #endif