1 /* Copyright 2007 Nick Mathewson */
2 /* See LICENSE for licensing information */
12 #define MEMPOOL_PRIVATE
17 * This is an implementation of memory pools for Tor cells. It may be
20 * Generally, a memory pool is an allocation strategy optimized for large
21 * numbers of identically-sized objects. Rather than the elaborate arena
22 * and coalescing strategies you need to get good performance for a
23 * general-purpose malloc(), pools use a series of large memory "chunks",
24 * each of which is carved into a bunch of smaller "items" or
27 * To get decent performance, you need to:
28 * - Minimize the number of times you hit the underlying allocator.
29 * - Try to keep accesses as local in memory as possible.
30 * - Try to keep the common case fast.
32 * Our implementation uses three lists of chunks per pool. Each chunk can
33 * be either "full" (no more room for items); "empty" (no items); or
34 * "used" (not full, not empty). There are independent doubly-linked
35 * lists for each state.
39 * I wrote this after looking at 3 or 4 other pooling allocators, but
40 * without copying. The strategy this most resembles (which is funny,
41 * since that's the one I looked at longest ago) is the pool allocator
42 * underlying Python's obmalloc code. Major differences from obmalloc's
44 * - We don't even try to be threadsafe.
45 * - We only handle objects of one size.
46 * - Our list of empty chunks is doubly-linked, not singly-linked.
47 * (This could change pretty easily; it's only doubly-linked for
49 * - We keep a list of full chunks (so we can have a "nuke everything"
50 * function). Obmalloc's pools leave full chunks to float unanchored.
52 * [XXXX020 Another way to support 'nuke everything' would be to keep
53 * _all_ the chunks in a doubly-linked-list. This would have more
54 * space overhead per chunk, but less pointer manipulation overhead
55 * than the current approach.]
58 * - Not even slightly threadsafe.
59 * - Likes to have lots of items per chunks.
60 * - One pointer overhead per allocated thing. (The alternative is
61 * something like glib's use of an RB-tree to keep track of what
62 * chunk any given piece of memory is in.)
63 * - Only aligns allocated things to void* level: redefign ALIGNMENT_TYPE
64 * if you need doubles.
65 * - Could probably be optimized a bit; the representation contains
66 * a bit more info than it really needs to have.
67 * - probably, chunks should always be a power of 2.
71 /* Tor dependencies */
76 #define ALLOC(x) tor_malloc(x)
77 #define FREE(x) tor_free(x)
78 #define ASSERT(x) tor_assert(x)
79 #undef ALLOC_CAN_RETURN_NULL
81 /* End Tor dependencies */
83 /* If you're not building this as part of Tor, you'll want to define the
84 * following macros. For now, these should do as defaults.
87 #define PREDICT_UNLIKELY(x) (x)
88 #define PREDICT_LIKELY(x) (x)
89 #define ALLOC(x) malloc(x)
90 #define FREE(x) free(x)
91 #define STRUCT_OFFSET(tp, member) \
92 ((off_t) (((char*)&((tp*)0)->member)-(char*)0))
93 #define ASSERT(x) assert(x)
94 #define ALLOC_CAN_RETURN_NULL
97 /* Tuning parameters */
98 /** Largest type that we need to ensure returned memory items are aligned to.
99 * Change this to "double" if we need to be safe for structs with doubles. */
100 #define ALIGNMENT_TYPE void *
101 /** Increment that we need to align allocated. */
102 #define ALIGNMENT sizeof(ALIGNMENT_TYPE)
103 /** Largest memory chunk that we should allocate. */
104 #define MAX_CHUNK (8*(1L<<20))
105 /** Smallest memory chunk size that we should allocate. */
106 #define MIN_CHUNK 4096
108 typedef struct mp_allocated_t mp_allocated_t
;
109 typedef struct mp_chunk_t mp_chunk_t
;
111 /** Holds a single allocated item, allocated as part of a chunk. */
112 struct mp_allocated_t
{
113 /** The chunk that this item is allocated in. This adds overhead to each
114 * allocated item, thus making this implementation inappropriate for
115 * very small items. */
116 mp_chunk_t
*in_chunk
;
118 /** If this item is free, the next item on the free list. */
119 mp_allocated_t
*next_free
;
120 /** If this item is not free, the actual memory contents of this item.
121 * (Not actual size.) */
123 /** An extra element to the union to insure correct alignment. */
124 ALIGNMENT_TYPE _dummy
;
128 /** 'Magic' value used to detect memory corruption. */
129 #define MP_CHUNK_MAGIC 0x09870123
131 /** A chunk of memory. Chunks come from malloc; we use them */
133 unsigned long magic
; /**< Must be MP_CHUNK_MAGIC if this chunk is valid. */
134 mp_chunk_t
*next
; /**< The next free, used, or full chunk in sequence. */
135 mp_chunk_t
*prev
; /**< The previous free, used, or full chunk in sequence. */
136 mp_pool_t
*pool
; /**< The pool that this chunk is part of. */
137 /** First free item in the freelist for this chunk. Note that this may be
138 * NULL even if this chunk is not at capacity: if so, the free memory at
139 * next_mem has not yet been carved into items.
141 mp_allocated_t
*first_free
;
142 int n_allocated
; /**< Number of currently allocated items in this chunk. */
143 int capacity
; /**< Number of items that can be fit into this chunk. */
144 size_t mem_size
; /**< Number of usable bytes in mem. */
145 char *next_mem
; /**< Pointer into part of <b>mem</b> not yet carved up. */
146 char mem
[1]; /**< Storage for this chunk. (Not actual size.) */
149 /** Number of extra bytes needed beyond mem_size to allocate a chunk. */
150 #define CHUNK_OVERHEAD (sizeof(mp_chunk_t)-1)
152 /** Given a pointer to a mp_allocated_t, return a pointer to the memory
154 #define A2M(a) (&(a)->u.mem)
155 /** Given a pointer to a memory_item_t, return a pointer to its enclosing
157 #define M2A(p) ( ((char*)p) - STRUCT_OFFSET(mp_allocated_t, u.mem) )
159 #ifdef ALLOC_CAN_RETURN_NULL
160 /** If our ALLOC() macro can return NULL, check whether <b>x</b> is NULL,
161 * and if so, return NULL. */
162 #define CHECK_ALLOC(x) \
163 if (PREDICT_UNLIKELY(!x)) { return NULL; }
165 /** If our ALLOC() macro can't return NULL, do nothing. */
166 #define CHECK_ALLOC(x)
169 /** Helper: Allocate and return a new memory chunk for <b>pool</b>. Does not
170 * link the chunk into any list. */
172 mp_chunk_new(mp_pool_t
*pool
)
174 size_t sz
= pool
->new_chunk_capacity
* pool
->item_alloc_size
;
175 mp_chunk_t
*chunk
= ALLOC(CHUNK_OVERHEAD
+ sz
);
177 memset(chunk
, 0, sizeof(mp_chunk_t
)); /* Doesn't clear the whole thing. */
178 chunk
->magic
= MP_CHUNK_MAGIC
;
179 chunk
->capacity
= pool
->new_chunk_capacity
;
180 chunk
->mem_size
= sz
;
181 chunk
->next_mem
= chunk
->mem
;
186 /** Return an newly allocated item from <b>pool</b>. */
188 mp_pool_get(mp_pool_t
*pool
)
191 mp_allocated_t
*allocated
;
193 if (PREDICT_LIKELY(pool
->used_chunks
!= NULL
)) {
194 /* Common case: there is some chunk that is neither full nor empty. Use
195 * that one. (We can't use the full ones, obviously, and we should fill
196 * up the used ones before we start on any empty ones. */
197 chunk
= pool
->used_chunks
;
199 } else if (pool
->empty_chunks
) {
200 /* We have no used chunks, but we have an empty chunk that we haven't
201 * freed yet: use that. (We pull from the front of the list, which should
202 * get us the most recently emptied chunk.) */
203 chunk
= pool
->empty_chunks
;
205 /* Remove the chunk from the empty list. */
206 pool
->empty_chunks
= chunk
->next
;
208 chunk
->next
->prev
= NULL
;
210 /* Put the chunk on the 'used' list*/
211 chunk
->next
= pool
->used_chunks
;
213 chunk
->next
->prev
= chunk
;
214 pool
->used_chunks
= chunk
;
216 ASSERT(!chunk
->prev
);
217 --pool
->n_empty_chunks
;
218 if (pool
->n_empty_chunks
< pool
->min_empty_chunks
)
219 pool
->min_empty_chunks
= pool
->n_empty_chunks
;
221 /* We have no used or empty chunks: allocate a new chunk. */
222 chunk
= mp_chunk_new(pool
);
225 /* Add the new chunk to the used list. */
226 chunk
->next
= pool
->used_chunks
;
228 chunk
->next
->prev
= chunk
;
229 pool
->used_chunks
= chunk
;
230 ASSERT(!chunk
->prev
);
233 ASSERT(chunk
->n_allocated
< chunk
->capacity
);
235 if (chunk
->first_free
) {
236 /* If there's anything on the chunk's freelist, unlink it and use it. */
237 allocated
= chunk
->first_free
;
238 chunk
->first_free
= allocated
->u
.next_free
;
239 allocated
->u
.next_free
= NULL
; /* For debugging; not really needed. */
240 ASSERT(allocated
->in_chunk
== chunk
);
242 /* Otherwise, the chunk had better have some free space left on it. */
243 ASSERT(chunk
->next_mem
+ pool
->item_alloc_size
<=
244 chunk
->mem
+ chunk
->mem_size
);
246 /* Good, it did. Let's carve off a bit of that free space, and use
248 allocated
= (void*)chunk
->next_mem
;
249 chunk
->next_mem
+= pool
->item_alloc_size
;
250 allocated
->in_chunk
= chunk
;
251 allocated
->u
.next_free
= NULL
; /* For debugging; not really needed. */
254 ++chunk
->n_allocated
;
256 if (PREDICT_UNLIKELY(chunk
->n_allocated
== chunk
->capacity
)) {
257 /* This chunk just became full. */
258 ASSERT(chunk
== pool
->used_chunks
);
259 ASSERT(chunk
->prev
== NULL
);
261 /* Take it off the used list. */
262 pool
->used_chunks
= chunk
->next
;
264 chunk
->next
->prev
= NULL
;
266 /* Put it on the full list. */
267 chunk
->next
= pool
->full_chunks
;
269 chunk
->next
->prev
= chunk
;
270 pool
->full_chunks
= chunk
;
273 /* And return the memory portion of the mp_allocated_t. */
274 return A2M(allocated
);
277 /** Return an allocated memory item to its memory pool. */
279 mp_pool_release(void *item
)
281 mp_allocated_t
*allocated
= (void*) M2A(item
);
282 mp_chunk_t
*chunk
= allocated
->in_chunk
;
285 ASSERT(chunk
->magic
== MP_CHUNK_MAGIC
);
286 ASSERT(chunk
->n_allocated
> 0);
288 allocated
->u
.next_free
= chunk
->first_free
;
289 chunk
->first_free
= allocated
;
291 if (PREDICT_UNLIKELY(chunk
->n_allocated
== chunk
->capacity
)) {
292 /* This chunk was full and is about to be used. */
293 mp_pool_t
*pool
= chunk
->pool
;
294 /* unlink from the full list */
296 chunk
->prev
->next
= chunk
->next
;
298 chunk
->next
->prev
= chunk
->prev
;
299 if (chunk
== pool
->full_chunks
)
300 pool
->full_chunks
= chunk
->next
;
302 /* link to the used list. */
303 chunk
->next
= pool
->used_chunks
;
306 chunk
->next
->prev
= chunk
;
307 pool
->used_chunks
= chunk
;
308 } else if (PREDICT_UNLIKELY(chunk
->n_allocated
== 1)) {
309 /* This was used and is about to be empty. */
310 mp_pool_t
*pool
= chunk
->pool
;
312 /* Unlink from the used list */
314 chunk
->prev
->next
= chunk
->next
;
316 chunk
->next
->prev
= chunk
->prev
;
317 if (chunk
== pool
->used_chunks
)
318 pool
->used_chunks
= chunk
->next
;
320 /* Link to the empty list */
321 chunk
->next
= pool
->empty_chunks
;
324 chunk
->next
->prev
= chunk
;
325 pool
->empty_chunks
= chunk
;
327 /* Reset the guts of this chunk to defragment it, in case it gets
329 chunk
->first_free
= NULL
;
330 chunk
->next_mem
= chunk
->mem
;
332 ++pool
->n_empty_chunks
;
335 --chunk
->n_allocated
;
338 /** Allocate a new memory pool to hold items of size <b>item_size</b>. We'll
339 * try to fit about <b>chunk_capacity</b> bytes in each chunk. */
341 mp_pool_new(size_t item_size
, size_t chunk_capacity
)
346 pool
= ALLOC(sizeof(mp_pool_t
));
348 memset(pool
, 0, sizeof(mp_pool_t
));
350 /* First, we figure out how much space to allow per item. We'll want to
351 * use make sure we have enough for the overhead plus the item size. */
352 alloc_size
= (size_t)(STRUCT_OFFSET(mp_allocated_t
, u
.mem
) + item_size
);
353 /* If the item_size is less than sizeof(next_free), we need to make
354 * the allocation bigger. */
355 if (alloc_size
< sizeof(mp_allocated_t
))
356 alloc_size
= sizeof(mp_allocated_t
);
358 /* If we're not an even multiple of ALIGNMENT, round up. */
359 if (alloc_size
% ALIGNMENT
) {
360 alloc_size
= alloc_size
+ ALIGNMENT
- (alloc_size
% ALIGNMENT
);
362 if (alloc_size
< ALIGNMENT
)
363 alloc_size
= ALIGNMENT
;
364 ASSERT((alloc_size
% ALIGNMENT
) == 0);
366 /* Now we figure out how many items fit in each chunk. We need to fit at
367 * least 2 items per chunk. No chunk can be more than MAX_CHUNK bytes long,
368 * or less than MIN_CHUNK. */
369 if (chunk_capacity
> MAX_CHUNK
)
370 chunk_capacity
= MAX_CHUNK
;
371 /* Try to be around a power of 2 in size, since that's what allocators like
372 * handing out. 512K-1 byte is a lot better than 512K+1 byte. */
373 chunk_capacity
= (size_t) round_to_power_of_2(chunk_capacity
);
374 while (chunk_capacity
< alloc_size
* 2 + CHUNK_OVERHEAD
)
376 if (chunk_capacity
< MIN_CHUNK
)
377 chunk_capacity
= MIN_CHUNK
;
379 pool
->new_chunk_capacity
= (chunk_capacity
-CHUNK_OVERHEAD
) / alloc_size
;
380 pool
->item_alloc_size
= alloc_size
;
382 log_debug(LD_MM
, "Capacity is %lu, item size is %lu, alloc size is %lu",
383 (unsigned long)pool
->new_chunk_capacity
,
384 (unsigned long)pool
->item_alloc_size
,
385 (unsigned long)(pool
->new_chunk_capacity
*pool
->item_alloc_size
));
390 /** If there are more than <b>n</b> empty chunks in <b>pool</b>, free the
391 * excess ones that have been empty for the longest. (If <b>n</b> is less
392 * than zero, free only empty chunks that were not used since the last
393 * call to mp_pool_clean(), leaving only -<b>n</b>.) */
395 mp_pool_clean(mp_pool_t
*pool
, int n
)
397 mp_chunk_t
*chunk
, **first_to_free
;
399 /* As said in the documentation, "negative n" means "leave an additional
400 * -n chunks". So replace n with a positive number. */
401 n
= pool
->min_empty_chunks
+ (-n
);
402 if (n
< pool
->n_empty_chunks
)
403 pool
->min_empty_chunks
= n
;
407 first_to_free
= &pool
->empty_chunks
;
408 while (*first_to_free
&& n
> 0) {
409 first_to_free
= &(*first_to_free
)->next
;
415 chunk
= *first_to_free
;
417 mp_chunk_t
*next
= chunk
->next
;
418 chunk
->magic
= 0xdeadbeef;
420 --pool
->n_empty_chunks
;
424 *first_to_free
= NULL
;
427 /** Helper: Given a list of chunks, free all the chunks in the list. */
429 destroy_chunks(mp_chunk_t
*chunk
)
433 chunk
->magic
= 0xd3adb33f;
440 /** Free all space held in <b>pool</b> This makes all pointers returned from
441 * mp_pool_get(<b>pool</b>) invalid. */
443 mp_pool_destroy(mp_pool_t
*pool
)
445 destroy_chunks(pool
->empty_chunks
);
446 destroy_chunks(pool
->used_chunks
);
447 destroy_chunks(pool
->full_chunks
);
448 memset(pool
, 0xe0, sizeof(mp_pool_t
));
452 /** Helper: make sure that a given chunk list is not corrupt. */
454 assert_chunks_ok(mp_pool_t
*pool
, mp_chunk_t
*chunk
, int empty
, int full
)
456 mp_allocated_t
*allocated
;
459 ASSERT(chunk
->prev
== NULL
);
463 ASSERT(chunk
->magic
== MP_CHUNK_MAGIC
);
464 ASSERT(chunk
->pool
== pool
);
465 for (allocated
= chunk
->first_free
; allocated
;
466 allocated
= allocated
->u
.next_free
) {
467 ASSERT(allocated
->in_chunk
== chunk
);
470 ASSERT(chunk
->n_allocated
== 0);
472 ASSERT(chunk
->n_allocated
== chunk
->capacity
);
474 ASSERT(chunk
->n_allocated
> 0 && chunk
->n_allocated
< chunk
->capacity
);
476 ASSERT(chunk
->capacity
== pool
->new_chunk_capacity
);
478 ASSERT(chunk
->mem_size
==
479 pool
->new_chunk_capacity
* pool
->item_alloc_size
);
481 ASSERT(chunk
->next_mem
>= chunk
->mem
&&
482 chunk
->next_mem
<= chunk
->mem
+ chunk
->mem_size
);
485 ASSERT(chunk
->next
->prev
== chunk
);
492 /** Fail with an assertion if <b>pool</b> is not internally consistent. */
494 mp_pool_assert_ok(mp_pool_t
*pool
)
498 n_empty
= assert_chunks_ok(pool
, pool
->empty_chunks
, 1, 0);
499 assert_chunks_ok(pool
, pool
->full_chunks
, 0, 1);
500 assert_chunks_ok(pool
, pool
->used_chunks
, 0, 0);
502 ASSERT(pool
->n_empty_chunks
== n_empty
);
506 /** Dump information about <b>pool</b>'s memory usage to the Tor log at level
507 * <b>severity</b>. */
508 /*FFFF uses Tor logging functions. */
510 mp_pool_log_status(mp_pool_t
*pool
, int severity
)
512 uint64_t bytes_used
= 0;
513 uint64_t bytes_allocated
= 0;
514 uint64_t bu
= 0, ba
= 0;
516 int n_full
= 0, n_used
= 0;
520 for (chunk
= pool
->empty_chunks
; chunk
; chunk
= chunk
->next
) {
521 bytes_allocated
+= chunk
->mem_size
;
523 log_fn(severity
, LD_MM
, U64_FORMAT
" bytes in %d empty chunks",
524 U64_PRINTF_ARG(bytes_used
), pool
->n_empty_chunks
);
525 for (chunk
= pool
->used_chunks
; chunk
; chunk
= chunk
->next
) {
527 bu
+= chunk
->n_allocated
* pool
->item_alloc_size
;
528 ba
+= chunk
->mem_size
;
530 log_fn(severity
, LD_MM
, U64_FORMAT
"/"U64_FORMAT
531 " bytes in %d partially full chunks",
532 U64_PRINTF_ARG(bu
), U64_PRINTF_ARG(ba
), n_used
);
534 bytes_allocated
+= ba
;
536 for (chunk
= pool
->full_chunks
; chunk
; chunk
= chunk
->next
) {
538 bu
+= chunk
->n_allocated
* pool
->item_alloc_size
;
539 ba
+= chunk
->mem_size
;
541 log_fn(severity
, LD_MM
, U64_FORMAT
"/"U64_FORMAT
542 " bytes in %d full chunks",
543 U64_PRINTF_ARG(bu
), U64_PRINTF_ARG(ba
), n_full
);
545 bytes_allocated
+= ba
;
547 log_fn(severity
, LD_MM
, "Total: "U64_FORMAT
"/"U64_FORMAT
" bytes allocated "
548 "for cell pools are full.",
549 U64_PRINTF_ARG(bytes_used
), U64_PRINTF_ARG(bytes_allocated
));