ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/ircd-hybrid/trunk/src/mempool.c
Revision: 6527
Committed: Fri Sep 11 16:33:29 2015 UTC (11 years ago) by michael
Content type: text/x-csrc
File size: 21645 byte(s)
Log Message:
- Fixed inconsistent style in several places

File Contents

# User Rev Content
1 michael 1656 /*
2     * Copyright (c) 2007-2012, The Tor Project, Inc.
3 michael 5347 * Copyright (c) 2012-2015 ircd-hybrid development team
4 michael 1656 *
5     * Redistribution and use in source and binary forms, with or without
6     * modification, are permitted provided that the following conditions are
7     * met:
8     *
9     * * Redistributions of source code must retain the above copyright
10     * notice, this list of conditions and the following disclaimer.
11     *
12     * * Redistributions in binary form must reproduce the above
13     * copyright notice, this list of conditions and the following disclaimer
14     * in the documentation and/or other materials provided with the
15     * distribution.
16     *
17     * * Neither the names of the copyright owners nor the names of its
18     * contributors may be used to endorse or promote products derived from
19     * this software without specific prior written permission.
20     *
21     * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22     * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23     * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24     * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25     * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26     * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27     * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28     * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29     * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30     * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31     * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32     */
33    
34     /*! \file mempool.c
35     * \brief A pooling allocator
36 michael 1662 * \version $Id$
37 michael 1656 */
38    
39     #include "stdinc.h"
40     #include "memory.h"
41     #include "event.h"
42     #include "log.h"
43     #include "mempool.h"
44    
45 michael 6527
46 michael 1656 /** Returns floor(log2(u64)). If u64 is 0, (incorrectly) returns 0. */
47     static int
48     tor_log2(uint64_t u64)
49     {
50     int r = 0;
51    
52     if (u64 >= (1LLU << 32))
53     {
54     u64 >>= 32;
55     r = 32;
56     }
57 michael 3279
58 michael 1656 if (u64 >= (1LLU << 16))
59     {
60     u64 >>= 16;
61     r += 16;
62     }
63 michael 3279
64 michael 1656 if (u64 >= (1LLU << 8))
65     {
66     u64 >>= 8;
67     r += 8;
68     }
69 michael 3279
70 michael 1656 if (u64 >= (1LLU << 4))
71     {
72     u64 >>= 4;
73     r += 4;
74     }
75 michael 3279
76 michael 1656 if (u64 >= (1LLU << 2))
77     {
78     u64 >>= 2;
79     r += 2;
80     }
81 michael 3279
82 michael 1656 if (u64 >= (1LLU << 1))
83     {
84     u64 >>= 1;
85     r += 1;
86     }
87    
88     return r;
89     }
90    
91     /** Return the power of 2 in range [1,UINT64_MAX] closest to <b>u64</b>. If
92     * there are two powers of 2 equally close, round down. */
93     static uint64_t
94     round_to_power_of_2(uint64_t u64)
95     {
96     int lg2;
97     uint64_t low;
98     uint64_t high;
99    
100     if (u64 == 0)
101     return 1;
102    
103     lg2 = tor_log2(u64);
104     low = 1LLU << lg2;
105    
106     if (lg2 == 63)
107     return low;
108    
109     high = 1LLU << (lg2 + 1);
110     if (high - u64 < u64 - low)
111     return high;
112     else
113     return low;
114     }
115    
116     /* OVERVIEW:
117     *
118     * This is an implementation of memory pools for Tor cells. It may be
119     * useful for you too.
120     *
121     * Generally, a memory pool is an allocation strategy optimized for large
122     * numbers of identically-sized objects. Rather than the elaborate arena
123     * and coalescing strategies you need to get good performance for a
124     * general-purpose malloc(), pools use a series of large memory "chunks",
125     * each of which is carved into a bunch of smaller "items" or
126     * "allocations".
127     *
128     * To get decent performance, you need to:
129     * - Minimize the number of times you hit the underlying allocator.
130     * - Try to keep accesses as local in memory as possible.
131     * - Try to keep the common case fast.
132     *
133     * Our implementation uses three lists of chunks per pool. Each chunk can
134     * be either "full" (no more room for items); "empty" (no items); or
135     * "used" (not full, not empty). There are independent doubly-linked
136     * lists for each state.
137     *
138     * CREDIT:
139     *
140     * I wrote this after looking at 3 or 4 other pooling allocators, but
141     * without copying. The strategy this most resembles (which is funny,
142     * since that's the one I looked at longest ago) is the pool allocator
143     * underlying Python's obmalloc code. Major differences from obmalloc's
144     * pools are:
145     * - We don't even try to be threadsafe.
146     * - We only handle objects of one size.
147     * - Our list of empty chunks is doubly-linked, not singly-linked.
148     * (This could change pretty easily; it's only doubly-linked for
149     * consistency.)
150     * - We keep a list of full chunks (so we can have a "nuke everything"
151     * function). Obmalloc's pools leave full chunks to float unanchored.
152     *
153     * LIMITATIONS:
154     * - Not even slightly threadsafe.
155     * - Likes to have lots of items per chunks.
156     * - One pointer overhead per allocated thing. (The alternative is
157     * something like glib's use of an RB-tree to keep track of what
158     * chunk any given piece of memory is in.)
159     * - Only aligns allocated things to void* level: redefine ALIGNMENT_TYPE
160     * if you need doubles.
161     * - Could probably be optimized a bit; the representation contains
162     * a bit more info than it really needs to have.
163     */
164    
165     /* Tuning parameters */
166     /** Largest type that we need to ensure returned memory items are aligned to.
167     * Change this to "double" if we need to be safe for structs with doubles. */
168     #define ALIGNMENT_TYPE void *
169     /** Increment that we need to align allocated. */
170     #define ALIGNMENT sizeof(ALIGNMENT_TYPE)
171     /** Largest memory chunk that we should allocate. */
172     #define MAX_CHUNK (8 *(1L << 20))
173     /** Smallest memory chunk size that we should allocate. */
174     #define MIN_CHUNK 4096
175    
176     typedef struct mp_allocated_t mp_allocated_t;
177     typedef struct mp_chunk_t mp_chunk_t;
178    
179     /** Holds a single allocated item, allocated as part of a chunk. */
180 michael 3279 struct mp_allocated_t
181     {
182 michael 1656 /** The chunk that this item is allocated in. This adds overhead to each
183     * allocated item, thus making this implementation inappropriate for
184     * very small items. */
185     mp_chunk_t *in_chunk;
186    
187 michael 3279 union
188     {
189 michael 1656 /** If this item is free, the next item on the free list. */
190     mp_allocated_t *next_free;
191    
192     /** If this item is not free, the actual memory contents of this item.
193     * (Not actual size.) */
194     char mem[1];
195    
196     /** An extra element to the union to insure correct alignment. */
197     ALIGNMENT_TYPE dummy_;
198     } u;
199     };
200    
201     /** 'Magic' value used to detect memory corruption. */
202     #define MP_CHUNK_MAGIC 0x09870123
203    
204     /** A chunk of memory. Chunks come from malloc; we use them */
205 michael 3279 struct mp_chunk_t
206     {
207 michael 1656 uint32_t magic; /**< Must be MP_CHUNK_MAGIC if this chunk is valid. */
208     mp_chunk_t *next; /**< The next free, used, or full chunk in sequence. */
209     mp_chunk_t *prev; /**< The previous free, used, or full chunk in sequence. */
210     mp_pool_t *pool; /**< The pool that this chunk is part of. */
211    
212     /** First free item in the freelist for this chunk. Note that this may be
213     * NULL even if this chunk is not at capacity: if so, the free memory at
214     * next_mem has not yet been carved into items.
215     */
216     mp_allocated_t *first_free;
217     int n_allocated; /**< Number of currently allocated items in this chunk. */
218     int capacity; /**< Number of items that can be fit into this chunk. */
219     size_t mem_size; /**< Number of usable bytes in mem. */
220     char *next_mem; /**< Pointer into part of <b>mem</b> not yet carved up. */
221     char mem[]; /**< Storage for this chunk. */
222     };
223    
224     static mp_pool_t *mp_allocated_pools = NULL;
225    
226     /** Number of extra bytes needed beyond mem_size to allocate a chunk. */
227     #define CHUNK_OVERHEAD offsetof(mp_chunk_t, mem[0])
228    
229     /** Given a pointer to a mp_allocated_t, return a pointer to the memory
230     * item it holds. */
231     #define A2M(a) (&(a)->u.mem)
232     /** Given a pointer to a memory_item_t, return a pointer to its enclosing
233     * mp_allocated_t. */
234     #define M2A(p) (((char *)p) - offsetof(mp_allocated_t, u.mem))
235    
236     void
237     mp_pool_init(void)
238     {
239 michael 4094 static struct event event_mp_gc =
240     {
241     .name = "mp_pool_garbage_collect",
242     .handler = mp_pool_garbage_collect,
243 michael 4098 .when = 187
244 michael 4094 };
245    
246     event_add(&event_mp_gc, NULL);
247 michael 1656 }
248    
249     /** Helper: Allocate and return a new memory chunk for <b>pool</b>. Does not
250     * link the chunk into any list. */
251     static mp_chunk_t *
252     mp_chunk_new(mp_pool_t *pool)
253     {
254     size_t sz = pool->new_chunk_capacity * pool->item_alloc_size;
255 michael 3504 mp_chunk_t *chunk = MyCalloc(CHUNK_OVERHEAD + sz);
256 michael 1656
257     #ifdef MEMPOOL_STATS
258     ++pool->total_chunks_allocated;
259     #endif
260     chunk->magic = MP_CHUNK_MAGIC;
261     chunk->capacity = pool->new_chunk_capacity;
262     chunk->mem_size = sz;
263     chunk->next_mem = chunk->mem;
264     chunk->pool = pool;
265     return chunk;
266     }
267    
268     /** Take a <b>chunk</b> that has just been allocated or removed from
269     * <b>pool</b>'s empty chunk list, and add it to the head of the used chunk
270     * list. */
271     static void
272     add_newly_used_chunk_to_used_list(mp_pool_t *pool, mp_chunk_t *chunk)
273     {
274     chunk->next = pool->used_chunks;
275     if (chunk->next)
276     chunk->next->prev = chunk;
277     pool->used_chunks = chunk;
278     assert(!chunk->prev);
279     }
280    
281     /** Return a newly allocated item from <b>pool</b>. */
282     void *
283     mp_pool_get(mp_pool_t *pool)
284     {
285     mp_chunk_t *chunk;
286     mp_allocated_t *allocated;
287 michael 4086 void *ptr = NULL;
288 michael 1656
289 michael 3279 if (pool->used_chunks)
290     {
291 michael 1656 /*
292     * Common case: there is some chunk that is neither full nor empty. Use
293     * that one. (We can't use the full ones, obviously, and we should fill
294     * up the used ones before we start on any empty ones.
295     */
296     chunk = pool->used_chunks;
297    
298 michael 3279 }
299     else if (pool->empty_chunks)
300     {
301 michael 1656 /*
302     * We have no used chunks, but we have an empty chunk that we haven't
303     * freed yet: use that. (We pull from the front of the list, which should
304     * get us the most recently emptied chunk.)
305     */
306     chunk = pool->empty_chunks;
307    
308     /* Remove the chunk from the empty list. */
309     pool->empty_chunks = chunk->next;
310     if (chunk->next)
311     chunk->next->prev = NULL;
312    
313     /* Put the chunk on the 'used' list*/
314     add_newly_used_chunk_to_used_list(pool, chunk);
315    
316     assert(!chunk->prev);
317     --pool->n_empty_chunks;
318     if (pool->n_empty_chunks < pool->min_empty_chunks)
319     pool->min_empty_chunks = pool->n_empty_chunks;
320 michael 3279 }
321     else
322     {
323 michael 1656 /* We have no used or empty chunks: allocate a new chunk. */
324     chunk = mp_chunk_new(pool);
325    
326     /* Add the new chunk to the used list. */
327     add_newly_used_chunk_to_used_list(pool, chunk);
328     }
329    
330     assert(chunk->n_allocated < chunk->capacity);
331    
332 michael 3279 if (chunk->first_free)
333     {
334 michael 1656 /* If there's anything on the chunk's freelist, unlink it and use it. */
335     allocated = chunk->first_free;
336     chunk->first_free = allocated->u.next_free;
337     allocated->u.next_free = NULL; /* For debugging; not really needed. */
338     assert(allocated->in_chunk == chunk);
339 michael 3279 }
340     else
341     {
342 michael 1656 /* Otherwise, the chunk had better have some free space left on it. */
343     assert(chunk->next_mem + pool->item_alloc_size <=
344     chunk->mem + chunk->mem_size);
345    
346     /* Good, it did. Let's carve off a bit of that free space, and use
347     * that. */
348     allocated = (void *)chunk->next_mem;
349     chunk->next_mem += pool->item_alloc_size;
350     allocated->in_chunk = chunk;
351     allocated->u.next_free = NULL; /* For debugging; not really needed. */
352     }
353    
354     ++chunk->n_allocated;
355     #ifdef MEMPOOL_STATS
356     ++pool->total_items_allocated;
357     #endif
358    
359 michael 3279 if (chunk->n_allocated == chunk->capacity)
360     {
361 michael 1656 /* This chunk just became full. */
362     assert(chunk == pool->used_chunks);
363     assert(chunk->prev == NULL);
364    
365     /* Take it off the used list. */
366     pool->used_chunks = chunk->next;
367     if (chunk->next)
368     chunk->next->prev = NULL;
369    
370     /* Put it on the full list. */
371     chunk->next = pool->full_chunks;
372     if (chunk->next)
373     chunk->next->prev = chunk;
374     pool->full_chunks = chunk;
375     }
376 michael 4086
377 michael 1656 /* And return the memory portion of the mp_allocated_t. */
378 michael 4086 ptr = A2M(allocated);
379     memset(ptr, 0, pool->item_size);
380    
381     return ptr;
382 michael 1656 }
383    
384     /** Return an allocated memory item to its memory pool. */
385     void
386     mp_pool_release(void *item)
387     {
388     mp_allocated_t *allocated = (void *)M2A(item);
389     mp_chunk_t *chunk = allocated->in_chunk;
390    
391     assert(chunk);
392     assert(chunk->magic == MP_CHUNK_MAGIC);
393     assert(chunk->n_allocated > 0);
394    
395     allocated->u.next_free = chunk->first_free;
396     chunk->first_free = allocated;
397    
398 michael 3279 if (chunk->n_allocated == chunk->capacity)
399     {
400 michael 1656 /* This chunk was full and is about to be used. */
401     mp_pool_t *pool = chunk->pool;
402     /* unlink from the full list */
403     if (chunk->prev)
404     chunk->prev->next = chunk->next;
405     if (chunk->next)
406     chunk->next->prev = chunk->prev;
407     if (chunk == pool->full_chunks)
408     pool->full_chunks = chunk->next;
409    
410     /* link to the used list. */
411     chunk->next = pool->used_chunks;
412     chunk->prev = NULL;
413 michael 3279
414 michael 1656 if (chunk->next)
415     chunk->next->prev = chunk;
416     pool->used_chunks = chunk;
417 michael 3279 }
418     else if (chunk->n_allocated == 1)
419     {
420 michael 1656 /* This was used and is about to be empty. */
421     mp_pool_t *pool = chunk->pool;
422    
423     /* Unlink from the used list */
424     if (chunk->prev)
425     chunk->prev->next = chunk->next;
426     if (chunk->next)
427     chunk->next->prev = chunk->prev;
428     if (chunk == pool->used_chunks)
429     pool->used_chunks = chunk->next;
430    
431     /* Link to the empty list */
432     chunk->next = pool->empty_chunks;
433     chunk->prev = NULL;
434     if (chunk->next)
435     chunk->next->prev = chunk;
436     pool->empty_chunks = chunk;
437    
438     /* Reset the guts of this chunk to defragment it, in case it gets
439     * used again. */
440     chunk->first_free = NULL;
441     chunk->next_mem = chunk->mem;
442    
443     ++pool->n_empty_chunks;
444     }
445    
446     --chunk->n_allocated;
447     }
448    
449     /** Allocate a new memory pool to hold items of size <b>item_size</b>. We'll
450     * try to fit about <b>chunk_capacity</b> bytes in each chunk. */
451     mp_pool_t *
452     mp_pool_new(size_t item_size, size_t chunk_capacity)
453     {
454     mp_pool_t *pool;
455     size_t alloc_size, new_chunk_cap;
456    
457     /* assert(item_size < SIZE_T_CEILING);
458     assert(chunk_capacity < SIZE_T_CEILING);
459     assert(SIZE_T_CEILING / item_size > chunk_capacity);
460     */
461 michael 3504 pool = MyCalloc(sizeof(mp_pool_t));
462 michael 1656 /*
463     * First, we figure out how much space to allow per item. We'll want to
464     * use make sure we have enough for the overhead plus the item size.
465     */
466     alloc_size = (size_t)(offsetof(mp_allocated_t, u.mem) + item_size);
467     /*
468     * If the item_size is less than sizeof(next_free), we need to make
469     * the allocation bigger.
470     */
471     if (alloc_size < sizeof(mp_allocated_t))
472     alloc_size = sizeof(mp_allocated_t);
473    
474     /* If we're not an even multiple of ALIGNMENT, round up. */
475 michael 3279 if (alloc_size % ALIGNMENT)
476 michael 1656 alloc_size = alloc_size + ALIGNMENT - (alloc_size % ALIGNMENT);
477     if (alloc_size < ALIGNMENT)
478     alloc_size = ALIGNMENT;
479 michael 3279
480 michael 1656 assert((alloc_size % ALIGNMENT) == 0);
481    
482     /*
483     * Now we figure out how many items fit in each chunk. We need to fit at
484     * least 2 items per chunk. No chunk can be more than MAX_CHUNK bytes long,
485     * or less than MIN_CHUNK.
486     */
487     if (chunk_capacity > MAX_CHUNK)
488     chunk_capacity = MAX_CHUNK;
489    
490     /*
491     * Try to be around a power of 2 in size, since that's what allocators like
492     * handing out. 512K-1 byte is a lot better than 512K+1 byte.
493     */
494     chunk_capacity = (size_t) round_to_power_of_2(chunk_capacity);
495 michael 3279
496 michael 1656 while (chunk_capacity < alloc_size * 2 + CHUNK_OVERHEAD)
497     chunk_capacity *= 2;
498     if (chunk_capacity < MIN_CHUNK)
499     chunk_capacity = MIN_CHUNK;
500    
501     new_chunk_cap = (chunk_capacity-CHUNK_OVERHEAD) / alloc_size;
502     assert(new_chunk_cap < INT_MAX);
503     pool->new_chunk_capacity = (int)new_chunk_cap;
504    
505 michael 4086 pool->item_size = item_size;
506 michael 1656 pool->item_alloc_size = alloc_size;
507    
508     pool->next = mp_allocated_pools;
509     mp_allocated_pools = pool;
510    
511 michael 1967 ilog(LOG_TYPE_DEBUG, "Capacity is %lu, item size is %lu, alloc size is %lu",
512 michael 1656 (unsigned long)pool->new_chunk_capacity,
513     (unsigned long)pool->item_alloc_size,
514     (unsigned long)(pool->new_chunk_capacity*pool->item_alloc_size));
515    
516     return pool;
517     }
518    
519     /** Helper function for qsort: used to sort pointers to mp_chunk_t into
520     * descending order of fullness. */
521     static int
522     mp_pool_sort_used_chunks_helper(const void *_a, const void *_b)
523     {
524     mp_chunk_t *a = *(mp_chunk_t * const *)_a;
525     mp_chunk_t *b = *(mp_chunk_t * const *)_b;
526     return b->n_allocated - a->n_allocated;
527     }
528    
529     /** Sort the used chunks in <b>pool</b> into descending order of fullness,
530     * so that we preferentially fill up mostly full chunks before we make
531     * nearly empty chunks less nearly empty. */
532     static void
533     mp_pool_sort_used_chunks(mp_pool_t *pool)
534     {
535     int i, n = 0, inverted = 0;
536     mp_chunk_t **chunks, *chunk;
537    
538 michael 3279 for (chunk = pool->used_chunks; chunk; chunk = chunk->next)
539     {
540 michael 1656 ++n;
541     if (chunk->next && chunk->next->n_allocated > chunk->n_allocated)
542     ++inverted;
543     }
544    
545     if (!inverted)
546     return;
547    
548 michael 3504 chunks = MyCalloc(sizeof(mp_chunk_t *) * n);
549 michael 1656
550 michael 3079 for (i = 0, chunk = pool->used_chunks; chunk; chunk = chunk->next)
551 michael 1656 chunks[i++] = chunk;
552    
553     qsort(chunks, n, sizeof(mp_chunk_t *), mp_pool_sort_used_chunks_helper);
554     pool->used_chunks = chunks[0];
555     chunks[0]->prev = NULL;
556    
557 michael 3279 for (i = 1; i < n; ++i)
558     {
559 michael 1656 chunks[i - 1]->next = chunks[i];
560     chunks[i]->prev = chunks[i - 1];
561     }
562    
563     chunks[n - 1]->next = NULL;
564     MyFree(chunks);
565     mp_pool_assert_ok(pool);
566     }
567    
568     /** If there are more than <b>n</b> empty chunks in <b>pool</b>, free the
569     * excess ones that have been empty for the longest. If
570     * <b>keep_recently_used</b> is true, do not free chunks unless they have been
571     * empty since the last call to this function.
572     **/
573     void
574     mp_pool_clean(mp_pool_t *pool, int n_to_keep, int keep_recently_used)
575     {
576     mp_chunk_t *chunk, **first_to_free;
577    
578     mp_pool_sort_used_chunks(pool);
579     assert(n_to_keep >= 0);
580    
581 michael 3279 if (keep_recently_used)
582     {
583 michael 1656 int n_recently_used = pool->n_empty_chunks - pool->min_empty_chunks;
584 michael 3279
585 michael 1656 if (n_to_keep < n_recently_used)
586     n_to_keep = n_recently_used;
587     }
588    
589     assert(n_to_keep >= 0);
590    
591     first_to_free = &pool->empty_chunks;
592 michael 3279
593     while (*first_to_free && n_to_keep > 0)
594     {
595 michael 1656 first_to_free = &(*first_to_free)->next;
596     --n_to_keep;
597     }
598 michael 3279
599     if (!*first_to_free)
600     {
601 michael 1656 pool->min_empty_chunks = pool->n_empty_chunks;
602     return;
603     }
604    
605     chunk = *first_to_free;
606 michael 3279
607     while (chunk)
608     {
609 michael 1656 mp_chunk_t *next = chunk->next;
610     chunk->magic = 0xdeadbeef;
611     MyFree(chunk);
612     #ifdef MEMPOOL_STATS
613     ++pool->total_chunks_freed;
614     #endif
615     --pool->n_empty_chunks;
616     chunk = next;
617     }
618    
619     pool->min_empty_chunks = pool->n_empty_chunks;
620     *first_to_free = NULL;
621     }
622    
623 michael 3036 #if 0
624 michael 1656 /** Helper: Given a list of chunks, free all the chunks in the list. */
625     static void
626     destroy_chunks(mp_chunk_t *chunk)
627     {
628     mp_chunk_t *next;
629    
630     while (chunk) {
631     chunk->magic = 0xd3adb33f;
632     next = chunk->next;
633     MyFree(chunk);
634     chunk = next;
635     }
636     }
637 michael 3036 #endif
638 michael 1656
639     /** Helper: make sure that a given chunk list is not corrupt. */
640     static int
641     assert_chunks_ok(mp_pool_t *pool, mp_chunk_t *chunk, int empty, int full)
642     {
643     mp_allocated_t *allocated;
644     int n = 0;
645    
646     if (chunk)
647     assert(chunk->prev == NULL);
648    
649 michael 3279 while (chunk)
650     {
651 michael 1656 n++;
652     assert(chunk->magic == MP_CHUNK_MAGIC);
653     assert(chunk->pool == pool);
654 michael 3279
655 michael 1656 for (allocated = chunk->first_free; allocated;
656 michael 3279 allocated = allocated->u.next_free)
657 michael 1656 assert(allocated->in_chunk == chunk);
658 michael 3279
659 michael 1656 if (empty)
660     assert(chunk->n_allocated == 0);
661     else if (full)
662     assert(chunk->n_allocated == chunk->capacity);
663     else
664     assert(chunk->n_allocated > 0 && chunk->n_allocated < chunk->capacity);
665    
666     assert(chunk->capacity == pool->new_chunk_capacity);
667    
668     assert(chunk->mem_size ==
669     pool->new_chunk_capacity * pool->item_alloc_size);
670    
671     assert(chunk->next_mem >= chunk->mem &&
672     chunk->next_mem <= chunk->mem + chunk->mem_size);
673    
674     if (chunk->next)
675     assert(chunk->next->prev == chunk);
676    
677     chunk = chunk->next;
678     }
679    
680     return n;
681     }
682    
683     /** Fail with an assertion if <b>pool</b> is not internally consistent. */
684     void
685     mp_pool_assert_ok(mp_pool_t *pool)
686     {
687     int n_empty;
688    
689     n_empty = assert_chunks_ok(pool, pool->empty_chunks, 1, 0);
690     assert_chunks_ok(pool, pool->full_chunks, 0, 1);
691     assert_chunks_ok(pool, pool->used_chunks, 0, 0);
692    
693     assert(pool->n_empty_chunks == n_empty);
694     }
695    
696     void
697 michael 4439 mp_pool_garbage_collect(void *unused)
698 michael 1656 {
699 michael 4387 for (mp_pool_t *pool = mp_allocated_pools; pool; pool = pool->next)
700 michael 1656 mp_pool_clean(pool, 0, 1);
701     }
702    
703     /** Dump information about <b>pool</b>'s memory usage to the Tor log at level
704     * <b>severity</b>. */
705     void
706     mp_pool_log_status(mp_pool_t *pool)
707     {
708     uint64_t bytes_used = 0;
709     uint64_t bytes_allocated = 0;
710     uint64_t bu = 0, ba = 0;
711     mp_chunk_t *chunk;
712     int n_full = 0, n_used = 0;
713    
714     assert(pool);
715    
716     for (chunk = pool->empty_chunks; chunk; chunk = chunk->next)
717     bytes_allocated += chunk->mem_size;
718    
719     ilog(LOG_TYPE_DEBUG, "%llu bytes in %d empty chunks",
720     bytes_allocated, pool->n_empty_chunks);
721 michael 3279 for (chunk = pool->used_chunks; chunk; chunk = chunk->next)
722     {
723 michael 1656 ++n_used;
724     bu += chunk->n_allocated * pool->item_alloc_size;
725     ba += chunk->mem_size;
726    
727     ilog(LOG_TYPE_DEBUG, " used chunk: %d items allocated",
728     chunk->n_allocated);
729     }
730    
731     ilog(LOG_TYPE_DEBUG, "%llu/%llu bytes in %d partially full chunks",
732     bu, ba, n_used);
733     bytes_used += bu;
734     bytes_allocated += ba;
735     bu = ba = 0;
736    
737 michael 3279 for (chunk = pool->full_chunks; chunk; chunk = chunk->next)
738     {
739 michael 1656 ++n_full;
740     bu += chunk->n_allocated * pool->item_alloc_size;
741     ba += chunk->mem_size;
742     }
743    
744     ilog(LOG_TYPE_DEBUG, "%llu/%llu bytes in %d full chunks",
745     bu, ba, n_full);
746     bytes_used += bu;
747     bytes_allocated += ba;
748    
749     ilog(LOG_TYPE_DEBUG, "Total: %llu/%llu bytes allocated "
750     "for cell pools are full.",
751     bytes_used, bytes_allocated);
752    
753     #ifdef MEMPOOL_STATS
754     ilog(LOG_TYPE_DEBUG, "%llu cell allocations ever; "
755     "%llu chunk allocations ever; "
756     "%llu chunk frees ever.",
757     pool->total_items_allocated,
758     pool->total_chunks_allocated,
759     pool->total_chunks_freed);
760     #endif
761     }

Properties

Name Value
svn:eol-style native
svn:keywords Id Revision