mempool.c 17.9 KB
Newer Older
1
/* Copyright (c) 2007, The Tor Project, Inc. */
2
/* See LICENSE for licensing information */
3
/* $Id$ */
4
5
6
7
8
#if 1
/* Tor dependencies */
#include "orconfig.h"
#endif

9
10
11
12
13
14
#include <stdlib.h>
#include <string.h>

#define MEMPOOL_PRIVATE
#include "mempool.h"

15
/* OVERVIEW:
16
17
18
19
20
21
 *
 *     This is an implementation of memory pools for Tor cells.  It may be
 *     useful for you too.
 *
 *     Generally, a memory pool is an allocation strategy optimized for large
 *     numbers of identically-sized objects.  Rather than the elaborate arena
Roger Dingledine's avatar
Roger Dingledine committed
22
 *     and coalescing strategies you need to get good performance for a
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 *     general-purpose malloc(), pools use a series of large memory "chunks",
 *     each of which is carved into a bunch of smaller "items" or
 *     "allocations".
 *
 *     To get decent performance, you need to:
 *        - Minimize the number of times you hit the underlying allocator.
 *        - Try to keep accesses as local in memory as possible.
 *        - Try to keep the common case fast.
 *
 *     Our implementation uses three lists of chunks per pool.  Each chunk can
 *     be either "full" (no more room for items); "empty" (no items); or
 *     "used" (not full, not empty).  There are independent doubly-linked
 *     lists for each state.
 *
 * CREDIT:
 *
 *     I wrote this after looking at 3 or 4 other pooling allocators, but
 *     without copying.  The strategy this most resembles (which is funny,
Roger Dingledine's avatar
Roger Dingledine committed
41
 *     since that's the one I looked at longest ago) is the pool allocator
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 *     underlying Python's obmalloc code.  Major differences from obmalloc's
 *     pools are:
 *       - We don't even try to be threadsafe.
 *       - We only handle objects of one size.
 *       - Our list of empty chunks is doubly-linked, not singly-linked.
 *         (This could change pretty easily; it's only doubly-linked for
 *         consistency.)
 *       - We keep a list of full chunks (so we can have a "nuke everything"
 *         function).  Obmalloc's pools leave full chunks to float unanchored.
 *
 *         [XXXX020 Another way to support 'nuke everything' would be to keep
 *         _all_ the chunks in a doubly-linked-list.  This would have more
 *         space overhead per chunk, but less pointer manipulation overhead
 *         than the current approach.]
 *
 * LIMITATIONS:
58
59
60
61
62
63
64
65
66
 *   - Not even slightly threadsafe.
 *   - Likes to have lots of items per chunks.
 *   - One pointer overhead per allocated thing.  (The alternative is
 *     something like glib's use of an RB-tree to keep track of what
 *     chunk any given piece of memory is in.)
 *   - Only aligns allocated things to void* level: redefign ALIGNMENT_TYPE
 *     if you need doubles.
 *   - Could probably be optimized a bit; the representation contains
 *     a bit more info than it really needs to have.
67
 *   - probably, chunks should always be a power of 2.
68
69
70
71
72
73
74
75
76
77
78
 */

#if 1
/* Tor dependencies */
#include "orconfig.h"
#include "util.h"
#include "compat.h"
#include "log.h"
#define ALLOC(x) tor_malloc(x)
#define FREE(x) tor_free(x)
#define ASSERT(x) tor_assert(x)
79
#undef ALLOC_CAN_RETURN_NULL
80
#define TOR
81
82
/* End Tor dependencies */
#else
83
84
85
/* If you're not building this as part of Tor, you'll want to define the
 * following macros.  For now, these should do as defaults.
 */
86
87
88
89
90
91
92
93
#include <assert.h>
#define PREDICT_UNLIKELY(x) (x)
#define PREDICT_LIKELY(x) (x)
#define ALLOC(x) malloc(x)
#define FREE(x) free(x)
#define STRUCT_OFFSET(tp, member)                       \
  ((off_t) (((char*)&((tp*)0)->member)-(char*)0))
#define ASSERT(x) assert(x)
94
#define ALLOC_CAN_RETURN_NULL
95
96
97
#endif

/* Tuning parameters */
98
99
/** Largest type that we need to ensure returned memory items are aligned to.
 * Change this to "double" if we need to be safe for structs with doubles. */
100
#define ALIGNMENT_TYPE void *
Roger Dingledine's avatar
Roger Dingledine committed
101
/** Increment that we need to align allocated. */
102
103
#define ALIGNMENT sizeof(ALIGNMENT_TYPE)
/** Largest memory chunk that we should allocate. */
104
#define MAX_CHUNK (8*(1L<<20))
105
/** Smallest memory chunk size that we should allocate. */
106
107
#define MIN_CHUNK 4096

108
typedef struct mp_allocated_t mp_allocated_t;
109
typedef struct mp_chunk_t mp_chunk_t;
110

111
/** Holds a single allocated item, allocated as part of a chunk. */
112
struct mp_allocated_t {
113
114
115
  /** The chunk that this item is allocated in.  This adds overhead to each
   * allocated item, thus making this implementation inappropriate for
   * very small items. */
116
117
  mp_chunk_t *in_chunk;
  union {
118
    /** If this item is free, the next item on the free list. */
119
    mp_allocated_t *next_free;
120
121
    /** If this item is not free, the actual memory contents of this item.
     * (Not actual size.) */
122
    char mem[1];
123
    /** An extra element to the union to insure correct alignment. */
124
    ALIGNMENT_TYPE _dummy;
125
  } u;
126
127
};

128
129
130
131
/** 'Magic' value used to detect memory corruption. */
#define MP_CHUNK_MAGIC 0x09870123

/** A chunk of memory.  Chunks come from malloc; we use them  */
132
struct mp_chunk_t {
133
134
135
  unsigned long magic; /**< Must be MP_CHUNK_MAGIC if this chunk is valid. */
  mp_chunk_t *next; /**< The next free, used, or full chunk in sequence. */
  mp_chunk_t *prev; /**< The previous free, used, or full chunk in sequence. */
Roger Dingledine's avatar
Roger Dingledine committed
136
  mp_pool_t *pool; /**< The pool that this chunk is part of. */
137
138
139
140
  /** First free item in the freelist for this chunk.  Note that this may be
   * NULL even if this chunk is not at capacity: if so, the free memory at
   * next_mem has not yet been carved into items.
   */
141
  mp_allocated_t *first_free;
Roger Dingledine's avatar
Roger Dingledine committed
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
145
146
  size_t mem_size; /**< Number of usable bytes in mem. */
  char *next_mem; /**< Pointer into part of <b>mem</b> not yet carved up. */
  char mem[1]; /**< Storage for this chunk. (Not actual size.) */
147
148
};

149
/** Number of extra bytes needed beyond mem_size to allocate a chunk. */
150
151
#define CHUNK_OVERHEAD (sizeof(mp_chunk_t)-1)

152
153
/** Given a pointer to a mp_allocated_t, return a pointer to the memory
 * item it holds. */
154
#define A2M(a) (&(a)->u.mem)
155
156
/** Given a pointer to a memory_item_t, return a pointer to its enclosing
 * mp_allocated_t. */
157
#define M2A(p) ( ((char*)p) - STRUCT_OFFSET(mp_allocated_t, u.mem) )
158

159
160
161
162
163
164
165
166
167
#ifdef ALLOC_CAN_RETURN_NULL
/** If our ALLOC() macro can return NULL, check whether <b>x</b> is NULL,
 * and if so, return NULL. */
#define CHECK_ALLOC(x)                           \
  if (PREDICT_UNLIKELY(!x)) { return NULL; }
#else
/** If our ALLOC() macro can't return NULL, do nothing. */
#define CHECK_ALLOC(x)
#endif
168

169
170
/** Helper: Allocate and return a new memory chunk for <b>pool</b>.  Does not
 * link the chunk into any list. */
171
172
173
174
175
static mp_chunk_t *
mp_chunk_new(mp_pool_t *pool)
{
  size_t sz = pool->new_chunk_capacity * pool->item_alloc_size;
  mp_chunk_t *chunk = ALLOC(CHUNK_OVERHEAD + sz);
176
  CHECK_ALLOC(chunk);
177
178
179
180
181
182
183
184
185
  memset(chunk, 0, sizeof(mp_chunk_t)); /* Doesn't clear the whole thing. */
  chunk->magic = MP_CHUNK_MAGIC;
  chunk->capacity = pool->new_chunk_capacity;
  chunk->mem_size = sz;
  chunk->next_mem = chunk->mem;
  chunk->pool = pool;
  return chunk;
}

186
/** Return an newly allocated item from <b>pool</b>. */
187
188
189
190
191
void *
mp_pool_get(mp_pool_t *pool)
{
  mp_chunk_t *chunk;
  mp_allocated_t *allocated;
192

193
  if (PREDICT_LIKELY(pool->used_chunks != NULL)) {
194
195
196
    /* Common case: there is some chunk that is neither full nor empty.  Use
     * that one. (We can't use the full ones, obviously, and we should fill
     * up the used ones before we start on any empty ones. */
197
    chunk = pool->used_chunks;
198

199
  } else if (pool->empty_chunks) {
200
201
202
    /* We have no used chunks, but we have an empty chunk that we haven't
     * freed yet: use that.  (We pull from the front of the list, which should
     * get us the most recently emptied chunk.) */
203
    chunk = pool->empty_chunks;
204
205

    /* Remove the chunk from the empty list. */
206
207
208
    pool->empty_chunks = chunk->next;
    if (chunk->next)
      chunk->next->prev = NULL;
209
210

    /* Put the chunk on the 'used' list*/
211
212
213
214
    chunk->next = pool->used_chunks;
    if (chunk->next)
      chunk->next->prev = chunk;
    pool->used_chunks = chunk;
215

216
    ASSERT(!chunk->prev);
217
    --pool->n_empty_chunks;
218
219
    if (pool->n_empty_chunks < pool->min_empty_chunks)
      pool->min_empty_chunks = pool->n_empty_chunks;
220
  } else {
221
    /* We have no used or empty chunks: allocate a new chunk. */
222
    chunk = mp_chunk_new(pool);
223
224
225
    CHECK_ALLOC(chunk);

    /* Add the new chunk to the used list. */
226
227
228
229
230
231
232
233
234
235
    chunk->next = pool->used_chunks;
    if (chunk->next)
      chunk->next->prev = chunk;
    pool->used_chunks = chunk;
    ASSERT(!chunk->prev);
  }

  ASSERT(chunk->n_allocated < chunk->capacity);

  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
239
    chunk->first_free = allocated->u.next_free;
    allocated->u.next_free = NULL; /* For debugging; not really needed. */
240
    ASSERT(allocated->in_chunk == chunk);
241
  } else {
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);
245
246
247

    /* Good, it did.  Let's carve off a bit of that free space, and use
     * that. */
248
249
250
    allocated = (void*)chunk->next_mem;
    chunk->next_mem += pool->item_alloc_size;
    allocated->in_chunk = chunk;
251
    allocated->u.next_free = NULL; /* For debugging; not really needed. */
252
253
254
  }

  ++chunk->n_allocated;
255

256
  if (PREDICT_UNLIKELY(chunk->n_allocated == chunk->capacity)) {
257
    /* This chunk just became full. */
258
259
    ASSERT(chunk == pool->used_chunks);
    ASSERT(chunk->prev == NULL);
260
261

    /* Take it off the used list. */
262
263
264
265
    pool->used_chunks = chunk->next;
    if (chunk->next)
      chunk->next->prev = NULL;

266
    /* Put it on the full list. */
267
    chunk->next = pool->full_chunks;
268
269
    if (chunk->next)
      chunk->next->prev = chunk;
270
271
272
    pool->full_chunks = chunk;
  }

273
  /* And return the memory portion of the mp_allocated_t. */
274
275
276
  return A2M(allocated);
}

277
/** Return an allocated memory item to its memory pool. */
278
void
279
mp_pool_release(void *item)
280
{
281
  mp_allocated_t *allocated = (void*) M2A(item);
282
283
284
285
286
287
  mp_chunk_t *chunk = allocated->in_chunk;

  ASSERT(chunk);
  ASSERT(chunk->magic == MP_CHUNK_MAGIC);
  ASSERT(chunk->n_allocated > 0);

288
  allocated->u.next_free = chunk->first_free;
289
290
291
292
293
  chunk->first_free = allocated;

  if (PREDICT_UNLIKELY(chunk->n_allocated == chunk->capacity)) {
    /* This chunk was full and is about to be used. */
    mp_pool_t *pool = chunk->pool;
294
    /* unlink from the full list  */
295
296
297
298
299
300
301
    if (chunk->prev)
      chunk->prev->next = chunk->next;
    if (chunk->next)
      chunk->next->prev = chunk->prev;
    if (chunk == pool->full_chunks)
      pool->full_chunks = chunk->next;

302
    /* link to the used list. */
303
304
305
306
307
308
309
310
    chunk->next = pool->used_chunks;
    chunk->prev = NULL;
    if (chunk->next)
      chunk->next->prev = chunk;
    pool->used_chunks = chunk;
  } else if (PREDICT_UNLIKELY(chunk->n_allocated == 1)) {
    /* This was used and is about to be empty. */
    mp_pool_t *pool = chunk->pool;
311
312

    /* Unlink from the used list */
313
314
315
316
317
318
319
    if (chunk->prev)
      chunk->prev->next = chunk->next;
    if (chunk->next)
      chunk->next->prev = chunk->prev;
    if (chunk == pool->used_chunks)
      pool->used_chunks = chunk->next;

320
    /* Link to the empty list */
321
322
323
324
325
326
    chunk->next = pool->empty_chunks;
    chunk->prev = NULL;
    if (chunk->next)
      chunk->next->prev = chunk;
    pool->empty_chunks = chunk;

327
328
    /* Reset the guts of this chunk to defragment it, in case it gets
     * used again. */
329
330
331
332
333
    chunk->first_free = NULL;
    chunk->next_mem = chunk->mem;

    ++pool->n_empty_chunks;
  }
334

335
336
337
  --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. */
340
341
342
343
344
345
346
mp_pool_t *
mp_pool_new(size_t item_size, size_t chunk_capacity)
{
  mp_pool_t *pool;
  size_t alloc_size;

  pool = ALLOC(sizeof(mp_pool_t));
347
  CHECK_ALLOC(pool);
348
349
  memset(pool, 0, sizeof(mp_pool_t));

350
351
  /* First, we figure out how much space to allow per item.  We'll want to
   * 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
354
  /* If the item_size is less than sizeof(next_free), we need to make
   * the allocation bigger. */
355
356
357
  if (alloc_size < sizeof(mp_allocated_t))
    alloc_size = sizeof(mp_allocated_t);

358
  /* If we're not an even multiple of ALIGNMENT, round up. */
359
360
361
362
363
364
365
  if (alloc_size % ALIGNMENT) {
    alloc_size = alloc_size + ALIGNMENT - (alloc_size % ALIGNMENT);
  }
  if (alloc_size < ALIGNMENT)
    alloc_size = ALIGNMENT;
  ASSERT((alloc_size % ALIGNMENT) == 0);

366
367
368
  /* Now we figure out how many items fit in each chunk.  We need to fit at
   * least 2 items per chunk. No chunk can be more than MAX_CHUNK bytes long,
   * or less than MIN_CHUNK. */
369
370
  if (chunk_capacity > MAX_CHUNK)
    chunk_capacity = MAX_CHUNK;
371
372
373
374
375
  /* Try to be around a power of 2 in size, since that's what allocators like
   * handing out. 512K-1 byte is a lot better than 512K+1 byte. */
  chunk_capacity = (size_t) round_to_power_of_2(chunk_capacity);
  while (chunk_capacity < alloc_size * 2 + CHUNK_OVERHEAD)
    chunk_capacity *= 2;
376
  if (chunk_capacity < MIN_CHUNK)
377
378
    chunk_capacity = MIN_CHUNK;

379
  pool->new_chunk_capacity = (chunk_capacity-CHUNK_OVERHEAD) / alloc_size;
380
381
  pool->item_alloc_size = alloc_size;

382
383
384
385
386
  log_debug(LD_MM, "Capacity is %lu, item size is %lu, alloc size is %lu",
            (unsigned long)pool->new_chunk_capacity,
            (unsigned long)pool->item_alloc_size,
            (unsigned long)(pool->new_chunk_capacity*pool->item_alloc_size));

387
388
389
  return pool;
}

390
/** If there are more than <b>n</b> empty chunks in <b>pool</b>, free the
Roger Dingledine's avatar
Roger Dingledine committed
391
 * excess ones that have been empty for the longest.  (If <b>n</b> is less
392
393
 * than zero, free only empty chunks that were not used since the last
 * call to mp_pool_clean(), leaving only -<b>n</b>.) */
394
void
395
mp_pool_clean(mp_pool_t *pool, int n)
396
{
397
  mp_chunk_t *chunk, **first_to_free;
398
  if (n < 0) {
399
400
    /* As said in the documentation, "negative n" means "leave an additional
     * -n chunks". So replace n with a positive number. */
401
402
403
404
405
406
    n = pool->min_empty_chunks + (-n);
    if (n < pool->n_empty_chunks)
      pool->min_empty_chunks = n;
  }
  ASSERT(n>=0);

407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
  first_to_free = &pool->empty_chunks;
  while (*first_to_free && n > 0) {
    first_to_free = &(*first_to_free)->next;
    --n;
  }
  if (!*first_to_free)
    return;

  chunk = *first_to_free;
  while (chunk) {
    mp_chunk_t *next = chunk->next;
    chunk->magic = 0xdeadbeef;
    FREE(chunk);
    --pool->n_empty_chunks;
    chunk = next;
422
  }
423
424

  *first_to_free = NULL;
425
426
}

427
/** Helper: Given a list of chunks, free all the chunks in the list. */
428
429
430
431
432
433
434
435
436
437
438
439
static void
destroy_chunks(mp_chunk_t *chunk)
{
  mp_chunk_t *next;
  while (chunk) {
    chunk->magic = 0xd3adb33f;
    next = chunk->next;
    FREE(chunk);
    chunk = next;
  }
}

440
441
/** Free all space held in <b>pool</b>  This makes all pointers returned from
 * mp_pool_get(<b>pool</b>) invalid. */
442
443
444
445
446
447
448
449
450
451
void
mp_pool_destroy(mp_pool_t *pool)
{
  destroy_chunks(pool->empty_chunks);
  destroy_chunks(pool->used_chunks);
  destroy_chunks(pool->full_chunks);
  memset(pool, 0xe0, sizeof(mp_pool_t));
  FREE(pool);
}

452
/** Helper: make sure that a given chunk list is not corrupt. */
453
454
455
456
457
458
459
460
461
462
463
464
465
static int
assert_chunks_ok(mp_pool_t *pool, mp_chunk_t *chunk, int empty, int full)
{
  mp_allocated_t *allocated;
  int n = 0;
  if (chunk)
    ASSERT(chunk->prev == NULL);

  while (chunk) {
    n++;
    ASSERT(chunk->magic == MP_CHUNK_MAGIC);
    ASSERT(chunk->pool == pool);
    for (allocated = chunk->first_free; allocated;
466
         allocated = allocated->u.next_free) {
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
      ASSERT(allocated->in_chunk == chunk);
    }
    if (empty)
      ASSERT(chunk->n_allocated == 0);
    else if (full)
      ASSERT(chunk->n_allocated == chunk->capacity);
    else
      ASSERT(chunk->n_allocated > 0 && chunk->n_allocated < chunk->capacity);

    ASSERT(chunk->capacity == pool->new_chunk_capacity);

    ASSERT(chunk->mem_size ==
           pool->new_chunk_capacity * pool->item_alloc_size);

    ASSERT(chunk->next_mem >= chunk->mem &&
           chunk->next_mem <= chunk->mem + chunk->mem_size);

    if (chunk->next)
      ASSERT(chunk->next->prev == chunk);

    chunk = chunk->next;
  }
  return n;
}

492
/** Fail with an assertion if <b>pool</b> is not internally consistent. */
493
494
495
496
497
498
499
500
501
502
503
504
void
mp_pool_assert_ok(mp_pool_t *pool)
{
  int n_empty;

  n_empty = assert_chunks_ok(pool, pool->empty_chunks, 1, 0);
  assert_chunks_ok(pool, pool->full_chunks, 0, 1);
  assert_chunks_ok(pool, pool->used_chunks, 0, 0);

  ASSERT(pool->n_empty_chunks == n_empty);
}

505
#ifdef TOR
506
507
/** Dump information about <b>pool</b>'s memory usage to the Tor log at level
 * <b>severity</b>. */
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
/*FFFF uses Tor logging functions. */
void
mp_pool_log_status(mp_pool_t *pool, int severity)
{
  uint64_t bytes_used = 0;
  uint64_t bytes_allocated = 0;
  uint64_t bu = 0, ba = 0;
  mp_chunk_t *chunk;
  int n_full = 0, n_used = 0;

  ASSERT(pool);

  for (chunk = pool->empty_chunks; chunk; chunk = chunk->next) {
    bytes_allocated += chunk->mem_size;
  }
  log_fn(severity, LD_MM, U64_FORMAT" bytes in %d empty chunks",
         U64_PRINTF_ARG(bytes_used), pool->n_empty_chunks);
  for (chunk = pool->used_chunks; chunk; chunk = chunk->next) {
    ++n_used;
    bu += chunk->n_allocated * pool->item_alloc_size;
    ba += chunk->mem_size;
  }
  log_fn(severity, LD_MM, U64_FORMAT"/"U64_FORMAT
         " bytes in %d partially full chunks",
         U64_PRINTF_ARG(bu), U64_PRINTF_ARG(ba), n_used);
  bytes_used += bu;
534
  bytes_allocated += ba;
535
536
537
538
539
540
541
542
543
544
  bu = ba = 0;
  for (chunk = pool->full_chunks; chunk; chunk = chunk->next) {
    ++n_full;
    bu += chunk->n_allocated * pool->item_alloc_size;
    ba += chunk->mem_size;
  }
  log_fn(severity, LD_MM, U64_FORMAT"/"U64_FORMAT
         " bytes in %d full chunks",
         U64_PRINTF_ARG(bu), U64_PRINTF_ARG(ba), n_full);
  bytes_used += bu;
545
  bytes_allocated += ba;
546
547
548
549
550
551
552

  log_fn(severity, LD_MM, "Total: "U64_FORMAT"/"U64_FORMAT" bytes allocated "
         "for cell pools are full.",
         U64_PRINTF_ARG(bytes_used), U64_PRINTF_ARG(bytes_allocated));
}
#endif