/* Memory tracking allocator. */ /* A memory block. */ struct block { struct block *next; /* Next in linked list. */ int idx; /* Allocation order index number. */ size_t size; /* Size in bytes. */ size_t used; /* MT_SUBALLOC: amount used so far. */ void *content; /* Allocated region. */ }; /* Indexes into |arg[]| within |struct mt_allocator|. */ enum mt_arg_index { MT_COUNT = 0, /* |MT_FAIL_COUNT|: Remaining successful allocations. */ MT_PERCENT = 0, /* |MT_FAIL_PERCENT|: Failure percentage. */ MT_BLOCK_SIZE = 0, /* |MT_SUBALLOC|: Size of block to suballocate. */ MT_ALIGN = 1 /* |MT_SUBALLOC|: Alignment of suballocated blocks. */ }; /* Memory tracking allocator. */ struct mt_allocator { struct libavl_allocator allocator; /* Allocator. Must be first member. */ /* Settings. */ enum mt_policy policy; /* Allocation policy. */ int arg[2]; /* Policy arguments. */ int verbosity; /* Message verbosity level. */ /* Current state. */ struct block *head, *tail; /* Head and tail of block list. */ int alloc_idx; /* Number of allocations so far. */ int block_cnt; /* Number of still-allocated blocks. */ }; static void *mt_allocate (struct libavl_allocator *, size_t); static void mt_free (struct libavl_allocator *, void *); /* Initializes the memory manager for use with allocation policy |policy| and policy arguments |arg[]|, at verbosity level |verbosity|, where 0 is a ``normal'' value. */ struct mt_allocator * mt_create (enum mt_policy policy, int arg[2], int verbosity) { struct mt_allocator *mt = xmalloc (sizeof *mt); mt->allocator.libavl_malloc = mt_allocate; mt->allocator.libavl_free = mt_free; mt->policy = policy; mt->arg[0] = arg[0]; mt->arg[1] = arg[1]; mt->verbosity = verbosity; mt->head = mt->tail = NULL; mt->alloc_idx = 0; mt->block_cnt = 0; return mt; } /* Frees and destroys memory tracker |mt|, reporting any memory leaks. */ void mt_destroy (struct mt_allocator *mt) { assert (mt != NULL); if (mt->block_cnt == 0) { if (mt->policy != MT_NO_TRACK && mt->verbosity >= 1) printf (" No memory leaks.\n"); } else { struct block *iter, *next; if (mt->policy != MT_SUBALLOC) printf (" Memory leaks detected:\n"); for (iter = mt->head; iter != NULL; iter = next) { if (mt->policy != MT_SUBALLOC) printf (" block #%d: %lu bytes\n", iter->idx, (unsigned long) iter->size); next = iter->next; free (iter->content); free (iter); } } free (mt); } /* Returns the |struct libavl_allocator| associated with |mt|. */ void * mt_allocator (struct mt_allocator *mt) { return &mt->allocator; } /* Creates a new |struct block| containing |size| bytes of content and returns a pointer to content. */ static void * new_block (struct mt_allocator *mt, size_t size) { struct block *new; /* Allocate and initialize new |struct block|. */ new = xmalloc (sizeof *new); new->next = NULL; new->idx = mt->alloc_idx++; new->size = size; new->used = 0; new->content = xmalloc (size); /* Add block to linked list. */ if (mt->head == NULL) mt->head = new; else mt->tail->next = new; mt->tail = new; /* Alert user. */ if (mt->verbosity >= 3) printf (" block #%d: allocated %lu bytes\n", new->idx, (unsigned long) size); /* Finish up and return. */ mt->block_cnt++; return new->content; } /* Prints a message about a rejected allocation if appropriate. */ static void reject_request (struct mt_allocator *mt, size_t size) { if (mt->verbosity >= 2) printf (" block #%d: rejected request for %lu bytes\n", mt->alloc_idx++, (unsigned long) size); } /* Allocates and returns a block of |size| bytes. */ static void * mt_allocate (struct libavl_allocator *allocator, size_t size) { struct mt_allocator *mt = (struct mt_allocator *) allocator; /* Special case. */ if (size == 0) return NULL; switch (mt->policy) { case MT_TRACK: return new_block (mt, size); case MT_NO_TRACK: return xmalloc (size); case MT_FAIL_COUNT: if (mt->arg[MT_COUNT] == 0) { reject_request (mt, size); return NULL; } mt->arg[MT_COUNT]--; return new_block (mt, size); case MT_FAIL_PERCENT: if (rand () / (RAND_MAX / 100 + 1) < mt->arg[MT_PERCENT]) { reject_request (mt, size); return NULL; } else return new_block (mt, size); case MT_SUBALLOC: if (mt->tail == NULL || mt->tail->used + size > (size_t) mt->arg[MT_BLOCK_SIZE]) new_block (mt, mt->arg[MT_BLOCK_SIZE]); if (mt->tail->used + size <= (size_t) mt->arg[MT_BLOCK_SIZE]) { void *p = (char *) mt->tail->content + mt->tail->used; size = ((size + mt->arg[MT_ALIGN] - 1) / mt->arg[MT_ALIGN] * mt->arg[MT_ALIGN]); mt->tail->used += size; if (mt->verbosity >= 3) printf (" block #%d: suballocated %lu bytes\n", mt->tail->idx, (unsigned long) size); return p; } else fail ("blocksize %lu too small for %lu-byte allocation", (unsigned long) mt->tail->size, (unsigned long) size); default: assert (0); } } /* Releases |block| previously returned by |mt_allocate()|. */ static void mt_free (struct libavl_allocator *allocator, void *block) { struct mt_allocator *mt = (struct mt_allocator *) allocator; struct block *iter, *prev; /* Special cases. */ if (block == NULL || mt->policy == MT_NO_TRACK) { free (block); return; } if (mt->policy == MT_SUBALLOC) return; /* Search for |block| within the list of allocated blocks. */ for (prev = NULL, iter = mt->head; iter; prev = iter, iter = iter->next) { if (iter->content == block) { /* Block found. Remove it from the list. */ struct block *next = iter->next; if (prev == NULL) mt->head = next; else prev->next = next; if (next == NULL) mt->tail = prev; /* Alert user. */ if (mt->verbosity >= 4) printf (" block #%d: freed %lu bytes\n", iter->idx, (unsigned long) iter->size); /* Free block. */ free (iter->content); free (iter); /* Finish up and return. */ mt->block_cnt--; return; } } /* Block not in list. */ printf (" attempt to free unknown block %p (already freed?)\n", block); }