1 /* Copyright (c) 2007-2010, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
11 #define MEMPOOL_PRIVATE
16 * This is an implementation of memory pools for Tor cells. It may be
19 * Generally, a memory pool is an allocation strategy optimized for large
20 * numbers of identically-sized objects. Rather than the elaborate arena
21 * and coalescing strategies you need to get good performance for a
22 * general-purpose malloc(), pools use a series of large memory "chunks",
23 * each of which is carved into a bunch of smaller "items" or
26 * To get decent performance, you need to:
27 * - Minimize the number of times you hit the underlying allocator.
28 * - Try to keep accesses as local in memory as possible.
29 * - Try to keep the common case fast.
31 * Our implementation uses three lists of chunks per pool. Each chunk can
32 * be either "full" (no more room for items); "empty" (no items); or
33 * "used" (not full, not empty). There are independent doubly-linked
34 * lists for each state.
38 * I wrote this after looking at 3 or 4 other pooling allocators, but
39 * without copying. The strategy this most resembles (which is funny,
40 * since that's the one I looked at longest ago) is the pool allocator
41 * underlying Python's obmalloc code. Major differences from obmalloc's
43 * - We don't even try to be threadsafe.
44 * - We only handle objects of one size.
45 * - Our list of empty chunks is doubly-linked, not singly-linked.
46 * (This could change pretty easily; it's only doubly-linked for
48 * - We keep a list of full chunks (so we can have a "nuke everything"
49 * function). Obmalloc's pools leave full chunks to float unanchored.
52 * - Not even slightly threadsafe.
53 * - Likes to have lots of items per chunks.
54 * - One pointer overhead per allocated thing. (The alternative is
55 * something like glib's use of an RB-tree to keep track of what
56 * chunk any given piece of memory is in.)
57 * - Only aligns allocated things to void* level: redefine ALIGNMENT_TYPE
58 * if you need doubles.
59 * - Could probably be optimized a bit; the representation contains
60 * a bit more info than it really needs to have.
64 /* Tor dependencies */
69 #define ALLOC(x) tor_malloc(x)
70 #define FREE(x) tor_free(x)
71 #define ASSERT(x) tor_assert(x)
72 #undef ALLOC_CAN_RETURN_NULL
74 //#define ALLOC_ROUNDUP(p) tor_malloc_roundup(p)
75 /* End Tor dependencies */
77 /* If you're not building this as part of Tor, you'll want to define the
78 * following macros. For now, these should do as defaults.
81 #define PREDICT_UNLIKELY(x) (x)
82 #define PREDICT_LIKELY(x) (x)
83 #define ALLOC(x) malloc(x)
84 #define FREE(x) free(x)
85 #define STRUCT_OFFSET(tp, member) \
86 ((off_t) (((char*)&((tp*)0)->member)-(char*)0))
87 #define ASSERT(x) assert(x)
88 #define ALLOC_CAN_RETURN_NULL
91 /* Tuning parameters */
92 /** Largest type that we need to ensure returned memory items are aligned to.
93 * Change this to "double" if we need to be safe for structs with doubles. */
94 #define ALIGNMENT_TYPE void *
95 /** Increment that we need to align allocated. */
96 #define ALIGNMENT sizeof(ALIGNMENT_TYPE)
97 /** Largest memory chunk that we should allocate. */
98 #define MAX_CHUNK (8*(1L<<20))
99 /** Smallest memory chunk size that we should allocate. */
100 #define MIN_CHUNK 4096
102 typedef struct mp_allocated_t mp_allocated_t
;
103 typedef struct mp_chunk_t mp_chunk_t
;
105 /** Holds a single allocated item, allocated as part of a chunk. */
106 struct mp_allocated_t
{
107 /** The chunk that this item is allocated in. This adds overhead to each
108 * allocated item, thus making this implementation inappropriate for
109 * very small items. */
110 mp_chunk_t
*in_chunk
;
112 /** If this item is free, the next item on the free list. */
113 mp_allocated_t
*next_free
;
114 /** If this item is not free, the actual memory contents of this item.
115 * (Not actual size.) */
117 /** An extra element to the union to insure correct alignment. */
118 ALIGNMENT_TYPE _dummy
;
122 /** 'Magic' value used to detect memory corruption. */
123 #define MP_CHUNK_MAGIC 0x09870123
125 /** A chunk of memory. Chunks come from malloc; we use them */
127 unsigned long magic
; /**< Must be MP_CHUNK_MAGIC if this chunk is valid. */
128 mp_chunk_t
*next
; /**< The next free, used, or full chunk in sequence. */
129 mp_chunk_t
*prev
; /**< The previous free, used, or full chunk in sequence. */
130 mp_pool_t
*pool
; /**< The pool that this chunk is part of. */
131 /** First free item in the freelist for this chunk. Note that this may be
132 * NULL even if this chunk is not at capacity: if so, the free memory at
133 * next_mem has not yet been carved into items.
135 mp_allocated_t
*first_free
;
136 int n_allocated
; /**< Number of currently allocated items in this chunk. */
137 int capacity
; /**< Number of items that can be fit into this chunk. */
138 size_t mem_size
; /**< Number of usable bytes in mem. */
139 char *next_mem
; /**< Pointer into part of <b>mem</b> not yet carved up. */
140 char mem
[1]; /**< Storage for this chunk. (Not actual size.) */
143 /** Number of extra bytes needed beyond mem_size to allocate a chunk. */
144 #define CHUNK_OVERHEAD STRUCT_OFFSET(mp_chunk_t, mem[0])
146 /** Given a pointer to a mp_allocated_t, return a pointer to the memory
148 #define A2M(a) (&(a)->u.mem)
149 /** Given a pointer to a memory_item_t, return a pointer to its enclosing
151 #define M2A(p) ( ((char*)p) - STRUCT_OFFSET(mp_allocated_t, u.mem) )
153 #ifdef ALLOC_CAN_RETURN_NULL
154 /** If our ALLOC() macro can return NULL, check whether <b>x</b> is NULL,
155 * and if so, return NULL. */
156 #define CHECK_ALLOC(x) \
157 if (PREDICT_UNLIKELY(!x)) { return NULL; }
159 /** If our ALLOC() macro can't return NULL, do nothing. */
160 #define CHECK_ALLOC(x)
163 /** Helper: Allocate and return a new memory chunk for <b>pool</b>. Does not
164 * link the chunk into any list. */
166 mp_chunk_new(mp_pool_t
*pool
)
168 size_t sz
= pool
->new_chunk_capacity
* pool
->item_alloc_size
;
170 size_t alloc_size
= CHUNK_OVERHEAD
+ sz
;
171 mp_chunk_t
*chunk
= ALLOC_ROUNDUP(&alloc_size
);
173 mp_chunk_t
*chunk
= ALLOC(CHUNK_OVERHEAD
+ sz
);
176 ++pool
->total_chunks_allocated
;
179 memset(chunk
, 0, sizeof(mp_chunk_t
)); /* Doesn't clear the whole thing. */
180 chunk
->magic
= MP_CHUNK_MAGIC
;
182 chunk
->mem_size
= alloc_size
- CHUNK_OVERHEAD
;
183 chunk
->capacity
= chunk
->mem_size
/ pool
->item_alloc_size
;
185 chunk
->capacity
= pool
->new_chunk_capacity
;
186 chunk
->mem_size
= sz
;
188 chunk
->next_mem
= chunk
->mem
;
193 /** Take a <b>chunk</b> that has just been allocated or removed from
194 * <b>pool</b>'s empty chunk list, and add it to the head of the used chunk
197 add_newly_used_chunk_to_used_list(mp_pool_t
*pool
, mp_chunk_t
*chunk
)
199 chunk
->next
= pool
->used_chunks
;
201 chunk
->next
->prev
= chunk
;
202 pool
->used_chunks
= chunk
;
203 ASSERT(!chunk
->prev
);
206 /** Return a newly allocated item from <b>pool</b>. */
208 mp_pool_get(mp_pool_t
*pool
)
211 mp_allocated_t
*allocated
;
213 if (PREDICT_LIKELY(pool
->used_chunks
!= NULL
)) {
214 /* Common case: there is some chunk that is neither full nor empty. Use
215 * that one. (We can't use the full ones, obviously, and we should fill
216 * up the used ones before we start on any empty ones. */
217 chunk
= pool
->used_chunks
;
219 } else if (pool
->empty_chunks
) {
220 /* We have no used chunks, but we have an empty chunk that we haven't
221 * freed yet: use that. (We pull from the front of the list, which should
222 * get us the most recently emptied chunk.) */
223 chunk
= pool
->empty_chunks
;
225 /* Remove the chunk from the empty list. */
226 pool
->empty_chunks
= chunk
->next
;
228 chunk
->next
->prev
= NULL
;
230 /* Put the chunk on the 'used' list*/
231 add_newly_used_chunk_to_used_list(pool
, chunk
);
233 ASSERT(!chunk
->prev
);
234 --pool
->n_empty_chunks
;
235 if (pool
->n_empty_chunks
< pool
->min_empty_chunks
)
236 pool
->min_empty_chunks
= pool
->n_empty_chunks
;
238 /* We have no used or empty chunks: allocate a new chunk. */
239 chunk
= mp_chunk_new(pool
);
242 /* Add the new chunk to the used list. */
243 add_newly_used_chunk_to_used_list(pool
, chunk
);
246 ASSERT(chunk
->n_allocated
< chunk
->capacity
);
248 if (chunk
->first_free
) {
249 /* If there's anything on the chunk's freelist, unlink it and use it. */
250 allocated
= chunk
->first_free
;
251 chunk
->first_free
= allocated
->u
.next_free
;
252 allocated
->u
.next_free
= NULL
; /* For debugging; not really needed. */
253 ASSERT(allocated
->in_chunk
== chunk
);
255 /* Otherwise, the chunk had better have some free space left on it. */
256 ASSERT(chunk
->next_mem
+ pool
->item_alloc_size
<=
257 chunk
->mem
+ chunk
->mem_size
);
259 /* Good, it did. Let's carve off a bit of that free space, and use
261 allocated
= (void*)chunk
->next_mem
;
262 chunk
->next_mem
+= pool
->item_alloc_size
;
263 allocated
->in_chunk
= chunk
;
264 allocated
->u
.next_free
= NULL
; /* For debugging; not really needed. */
267 ++chunk
->n_allocated
;
269 ++pool
->total_items_allocated
;
272 if (PREDICT_UNLIKELY(chunk
->n_allocated
== chunk
->capacity
)) {
273 /* This chunk just became full. */
274 ASSERT(chunk
== pool
->used_chunks
);
275 ASSERT(chunk
->prev
== NULL
);
277 /* Take it off the used list. */
278 pool
->used_chunks
= chunk
->next
;
280 chunk
->next
->prev
= NULL
;
282 /* Put it on the full list. */
283 chunk
->next
= pool
->full_chunks
;
285 chunk
->next
->prev
= chunk
;
286 pool
->full_chunks
= chunk
;
288 /* And return the memory portion of the mp_allocated_t. */
289 return A2M(allocated
);
292 /** Return an allocated memory item to its memory pool. */
294 mp_pool_release(void *item
)
296 mp_allocated_t
*allocated
= (void*) M2A(item
);
297 mp_chunk_t
*chunk
= allocated
->in_chunk
;
300 ASSERT(chunk
->magic
== MP_CHUNK_MAGIC
);
301 ASSERT(chunk
->n_allocated
> 0);
303 allocated
->u
.next_free
= chunk
->first_free
;
304 chunk
->first_free
= allocated
;
306 if (PREDICT_UNLIKELY(chunk
->n_allocated
== chunk
->capacity
)) {
307 /* This chunk was full and is about to be used. */
308 mp_pool_t
*pool
= chunk
->pool
;
309 /* unlink from the full list */
311 chunk
->prev
->next
= chunk
->next
;
313 chunk
->next
->prev
= chunk
->prev
;
314 if (chunk
== pool
->full_chunks
)
315 pool
->full_chunks
= chunk
->next
;
317 /* link to the used list. */
318 chunk
->next
= pool
->used_chunks
;
321 chunk
->next
->prev
= chunk
;
322 pool
->used_chunks
= chunk
;
323 } else if (PREDICT_UNLIKELY(chunk
->n_allocated
== 1)) {
324 /* This was used and is about to be empty. */
325 mp_pool_t
*pool
= chunk
->pool
;
327 /* Unlink from the used list */
329 chunk
->prev
->next
= chunk
->next
;
331 chunk
->next
->prev
= chunk
->prev
;
332 if (chunk
== pool
->used_chunks
)
333 pool
->used_chunks
= chunk
->next
;
335 /* Link to the empty list */
336 chunk
->next
= pool
->empty_chunks
;
339 chunk
->next
->prev
= chunk
;
340 pool
->empty_chunks
= chunk
;
342 /* Reset the guts of this chunk to defragment it, in case it gets
344 chunk
->first_free
= NULL
;
345 chunk
->next_mem
= chunk
->mem
;
347 ++pool
->n_empty_chunks
;
349 --chunk
->n_allocated
;
352 /** Allocate a new memory pool to hold items of size <b>item_size</b>. We'll
353 * try to fit about <b>chunk_capacity</b> bytes in each chunk. */
355 mp_pool_new(size_t item_size
, size_t chunk_capacity
)
358 size_t alloc_size
, new_chunk_cap
;
360 pool
= ALLOC(sizeof(mp_pool_t
));
362 memset(pool
, 0, sizeof(mp_pool_t
));
364 /* First, we figure out how much space to allow per item. We'll want to
365 * use make sure we have enough for the overhead plus the item size. */
366 alloc_size
= (size_t)(STRUCT_OFFSET(mp_allocated_t
, u
.mem
) + item_size
);
367 /* If the item_size is less than sizeof(next_free), we need to make
368 * the allocation bigger. */
369 if (alloc_size
< sizeof(mp_allocated_t
))
370 alloc_size
= sizeof(mp_allocated_t
);
372 /* If we're not an even multiple of ALIGNMENT, round up. */
373 if (alloc_size
% ALIGNMENT
) {
374 alloc_size
= alloc_size
+ ALIGNMENT
- (alloc_size
% ALIGNMENT
);
376 if (alloc_size
< ALIGNMENT
)
377 alloc_size
= ALIGNMENT
;
378 ASSERT((alloc_size
% ALIGNMENT
) == 0);
380 /* Now we figure out how many items fit in each chunk. We need to fit at
381 * least 2 items per chunk. No chunk can be more than MAX_CHUNK bytes long,
382 * or less than MIN_CHUNK. */
383 if (chunk_capacity
> MAX_CHUNK
)
384 chunk_capacity
= MAX_CHUNK
;
385 /* Try to be around a power of 2 in size, since that's what allocators like
386 * handing out. 512K-1 byte is a lot better than 512K+1 byte. */
387 chunk_capacity
= (size_t) round_to_power_of_2(chunk_capacity
);
388 while (chunk_capacity
< alloc_size
* 2 + CHUNK_OVERHEAD
)
390 if (chunk_capacity
< MIN_CHUNK
)
391 chunk_capacity
= MIN_CHUNK
;
393 new_chunk_cap
= (chunk_capacity
-CHUNK_OVERHEAD
) / alloc_size
;
394 tor_assert(new_chunk_cap
< INT_MAX
);
395 pool
->new_chunk_capacity
= (int)new_chunk_cap
;
397 pool
->item_alloc_size
= alloc_size
;
399 log_debug(LD_MM
, "Capacity is %lu, item size is %lu, alloc size is %lu",
400 (unsigned long)pool
->new_chunk_capacity
,
401 (unsigned long)pool
->item_alloc_size
,
402 (unsigned long)(pool
->new_chunk_capacity
*pool
->item_alloc_size
));
407 /** Helper function for qsort: used to sort pointers to mp_chunk_t into
408 * descending order of fullness. */
410 mp_pool_sort_used_chunks_helper(const void *_a
, const void *_b
)
412 mp_chunk_t
*a
= *(mp_chunk_t
**)_a
;
413 mp_chunk_t
*b
= *(mp_chunk_t
**)_b
;
414 return b
->n_allocated
- a
->n_allocated
;
417 /** Sort the used chunks in <b>pool</b> into descending order of fullness,
418 * so that we preferentially fill up mostly full chunks before we make
419 * nearly empty chunks less nearly empty. */
421 mp_pool_sort_used_chunks(mp_pool_t
*pool
)
423 int i
, n
=0, inverted
=0;
424 mp_chunk_t
**chunks
, *chunk
;
425 for (chunk
= pool
->used_chunks
; chunk
; chunk
= chunk
->next
) {
427 if (chunk
->next
&& chunk
->next
->n_allocated
> chunk
->n_allocated
)
432 //printf("Sort %d/%d\n",inverted,n);
433 chunks
= ALLOC(sizeof(mp_chunk_t
*)*n
);
434 #ifdef ALLOC_CAN_RETURN_NULL
435 if (PREDICT_UNLIKELY(!chunks
)) return;
437 for (i
=0,chunk
= pool
->used_chunks
; chunk
; chunk
= chunk
->next
)
439 qsort(chunks
, n
, sizeof(mp_chunk_t
*), mp_pool_sort_used_chunks_helper
);
440 pool
->used_chunks
= chunks
[0];
441 chunks
[0]->prev
= NULL
;
443 chunks
[i
-1]->next
= chunks
[i
];
444 chunks
[i
]->prev
= chunks
[i
-1];
446 chunks
[n
-1]->next
= NULL
;
448 mp_pool_assert_ok(pool
);
451 /** If there are more than <b>n</b> empty chunks in <b>pool</b>, free the
452 * excess ones that have been empty for the longest. If
453 * <b>keep_recently_used</b> is true, do not free chunks unless they have been
454 * empty since the last call to this function.
457 mp_pool_clean(mp_pool_t
*pool
, int n_to_keep
, int keep_recently_used
)
459 mp_chunk_t
*chunk
, **first_to_free
;
461 mp_pool_sort_used_chunks(pool
);
462 ASSERT(n_to_keep
>= 0);
464 if (keep_recently_used
) {
465 int n_recently_used
= pool
->n_empty_chunks
- pool
->min_empty_chunks
;
466 if (n_to_keep
< n_recently_used
)
467 n_to_keep
= n_recently_used
;
470 ASSERT(n_to_keep
>= 0);
472 first_to_free
= &pool
->empty_chunks
;
473 while (*first_to_free
&& n_to_keep
> 0) {
474 first_to_free
= &(*first_to_free
)->next
;
477 if (!*first_to_free
) {
478 pool
->min_empty_chunks
= pool
->n_empty_chunks
;
482 chunk
= *first_to_free
;
484 mp_chunk_t
*next
= chunk
->next
;
485 chunk
->magic
= 0xdeadbeef;
488 ++pool
->total_chunks_freed
;
490 --pool
->n_empty_chunks
;
494 pool
->min_empty_chunks
= pool
->n_empty_chunks
;
495 *first_to_free
= NULL
;
498 /** Helper: Given a list of chunks, free all the chunks in the list. */
500 destroy_chunks(mp_chunk_t
*chunk
)
504 chunk
->magic
= 0xd3adb33f;
511 /** Free all space held in <b>pool</b> This makes all pointers returned from
512 * mp_pool_get(<b>pool</b>) invalid. */
514 mp_pool_destroy(mp_pool_t
*pool
)
516 destroy_chunks(pool
->empty_chunks
);
517 destroy_chunks(pool
->used_chunks
);
518 destroy_chunks(pool
->full_chunks
);
519 memset(pool
, 0xe0, sizeof(mp_pool_t
));
523 /** Helper: make sure that a given chunk list is not corrupt. */
525 assert_chunks_ok(mp_pool_t
*pool
, mp_chunk_t
*chunk
, int empty
, int full
)
527 mp_allocated_t
*allocated
;
530 ASSERT(chunk
->prev
== NULL
);
534 ASSERT(chunk
->magic
== MP_CHUNK_MAGIC
);
535 ASSERT(chunk
->pool
== pool
);
536 for (allocated
= chunk
->first_free
; allocated
;
537 allocated
= allocated
->u
.next_free
) {
538 ASSERT(allocated
->in_chunk
== chunk
);
541 ASSERT(chunk
->n_allocated
== 0);
543 ASSERT(chunk
->n_allocated
== chunk
->capacity
);
545 ASSERT(chunk
->n_allocated
> 0 && chunk
->n_allocated
< chunk
->capacity
);
547 ASSERT(chunk
->capacity
== pool
->new_chunk_capacity
);
549 ASSERT(chunk
->mem_size
==
550 pool
->new_chunk_capacity
* pool
->item_alloc_size
);
552 ASSERT(chunk
->next_mem
>= chunk
->mem
&&
553 chunk
->next_mem
<= chunk
->mem
+ chunk
->mem_size
);
556 ASSERT(chunk
->next
->prev
== chunk
);
563 /** Fail with an assertion if <b>pool</b> is not internally consistent. */
565 mp_pool_assert_ok(mp_pool_t
*pool
)
569 n_empty
= assert_chunks_ok(pool
, pool
->empty_chunks
, 1, 0);
570 assert_chunks_ok(pool
, pool
->full_chunks
, 0, 1);
571 assert_chunks_ok(pool
, pool
->used_chunks
, 0, 0);
573 ASSERT(pool
->n_empty_chunks
== n_empty
);
577 /** Dump information about <b>pool</b>'s memory usage to the Tor log at level
578 * <b>severity</b>. */
579 /*FFFF uses Tor logging functions. */
581 mp_pool_log_status(mp_pool_t
*pool
, int severity
)
583 uint64_t bytes_used
= 0;
584 uint64_t bytes_allocated
= 0;
585 uint64_t bu
= 0, ba
= 0;
587 int n_full
= 0, n_used
= 0;
591 for (chunk
= pool
->empty_chunks
; chunk
; chunk
= chunk
->next
) {
592 bytes_allocated
+= chunk
->mem_size
;
594 log_fn(severity
, LD_MM
, U64_FORMAT
" bytes in %d empty chunks",
595 U64_PRINTF_ARG(bytes_allocated
), pool
->n_empty_chunks
);
596 for (chunk
= pool
->used_chunks
; chunk
; chunk
= chunk
->next
) {
598 bu
+= chunk
->n_allocated
* pool
->item_alloc_size
;
599 ba
+= chunk
->mem_size
;
600 log_fn(severity
, LD_MM
, " used chunk: %d items allocated",
603 log_fn(severity
, LD_MM
, U64_FORMAT
"/"U64_FORMAT
604 " bytes in %d partially full chunks",
605 U64_PRINTF_ARG(bu
), U64_PRINTF_ARG(ba
), n_used
);
607 bytes_allocated
+= ba
;
609 for (chunk
= pool
->full_chunks
; chunk
; chunk
= chunk
->next
) {
611 bu
+= chunk
->n_allocated
* pool
->item_alloc_size
;
612 ba
+= chunk
->mem_size
;
614 log_fn(severity
, LD_MM
, U64_FORMAT
"/"U64_FORMAT
615 " bytes in %d full chunks",
616 U64_PRINTF_ARG(bu
), U64_PRINTF_ARG(ba
), n_full
);
618 bytes_allocated
+= ba
;
620 log_fn(severity
, LD_MM
, "Total: "U64_FORMAT
"/"U64_FORMAT
" bytes allocated "
621 "for cell pools are full.",
622 U64_PRINTF_ARG(bytes_used
), U64_PRINTF_ARG(bytes_allocated
));
625 log_fn(severity
, LD_MM
, U64_FORMAT
" cell allocations ever; "
626 U64_FORMAT
" chunk allocations ever; "
627 U64_FORMAT
" chunk frees ever.",
628 U64_PRINTF_ARG(pool
->total_items_allocated
),
629 U64_PRINTF_ARG(pool
->total_chunks_allocated
),
630 U64_PRINTF_ARG(pool
->total_chunks_freed
));