From: Martin Quinson Date: Fri, 3 Feb 2012 14:17:14 +0000 (+0100) Subject: Further simplify the mmallocs, and improve its introspection abilities X-Git-Tag: exp_20120216~72 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/04eb21634ce9041eaf00274eec16e20dbf5f70d0 Further simplify the mmallocs, and improve its introspection abilities - Ensure that the mmallocation code will never return NULL (but die verbosely), and simplify the using code accordingly. - Stop using THROWF in there, because these functions probably need malloc to work, and that what broke when we want to issue a message. Use printf/abort instead. - Introduce a SMALLEST_POSSIBLE_MALLOC. It already existed (and were defined to sizeof(struct list) to ensure that free fragments can be enlisted, but I need this to declare the block metadata - Add a frag_size information within the bloc info structure. It may not perfectly be kept uptodate yet (in particular, by realloc) --- diff --git a/src/xbt/mmalloc/mmalloc.c b/src/xbt/mmalloc/mmalloc.c index 57fa34ea57..816f03465d 100644 --- a/src/xbt/mmalloc/mmalloc.c +++ b/src/xbt/mmalloc/mmalloc.c @@ -16,11 +16,14 @@ /* Prototypes for local functions */ -static int initialize(xbt_mheap_t mdp); +static void initialize(xbt_mheap_t mdp); static void *register_morecore(xbt_mheap_t mdp, size_t size); static void *align(xbt_mheap_t mdp, size_t size); -/* Allocation aligned on block boundary */ +/* Allocation aligned on block boundary. + * + * It never returns NULL, but dies verbosely on error. + */ static void *align(struct mdesc *mdp, size_t size) { void *result; @@ -46,14 +49,12 @@ static void *align(struct mdesc *mdp, size_t size) /* Finish the initialization of the mheap. If we want to inline it * properly, we need to make the align function publicly visible, too */ -static int initialize(xbt_mheap_t mdp) +static void initialize(xbt_mheap_t mdp) { mdp->heapsize = HEAP / BLOCKSIZE; mdp->heapinfo = (malloc_info *) align(mdp, mdp->heapsize * sizeof(malloc_info)); - if (mdp->heapinfo == NULL) { - return (0); - } + memset((void *) mdp->heapinfo, 0, mdp->heapsize * sizeof(malloc_info)); mdp->heapinfo[0].type=-1; mdp->heapinfo[0].free_block.size = 0; @@ -61,7 +62,6 @@ static int initialize(xbt_mheap_t mdp) mdp->heapindex = 0; mdp->heapbase = (void *) mdp->heapinfo; mdp->flags |= MMALLOC_INITIALIZED; - return (1); } /* Get neatly aligned memory from the low level layers, and register it @@ -72,10 +72,7 @@ static void *register_morecore(struct mdesc *mdp, size_t size) malloc_info *newinfo, *oldinfo; size_t newsize; - result = align(mdp, size); - if (result == NULL) { - return (NULL); - } + result = align(mdp, size); // Never returns NULL /* Check if we need to grow the info table (in a multiplicative manner) */ if ((size_t) BLOCK((char *) result + size) > mdp->heapsize) { @@ -118,23 +115,19 @@ void *mmalloc(xbt_mheap_t mdp, size_t size) register size_t log; int it; - /* Work even if the user was stupid enough to ask a 0-byte block, ie return a valid block that can be realloced or freed - * glibc malloc does not use this trick but return a constant pointer, but my hack is quicker to implement ;) + size_t requested_size = size; // The amount of memory requested by user, for real + + /* Work even if the user was stupid enough to ask a ridicullously small block (even 0-length), + * ie return a valid block that can be realloced and freed. + * glibc malloc does not use this trick but return a constant pointer, but we need to enlist the free fragments later on. */ - if (size == 0) - size = 1; + if (size < SMALLEST_POSSIBLE_MALLOC) + size = SMALLEST_POSSIBLE_MALLOC; // printf("(%s) Mallocing %d bytes on %p (default: %p)...",xbt_thread_self_name(),size,mdp,__mmalloc_default_mdp);fflush(stdout); - if (!(mdp->flags & MMALLOC_INITIALIZED)) { - if (!initialize(mdp)) { - return (NULL); - } - } - - if (size < sizeof(struct list)) { - size = sizeof(struct list); - } + if (!(mdp->flags & MMALLOC_INITIALIZED)) + initialize(mdp); /* Determine the allocation policy based on the request size. */ if (size <= BLOCKSIZE / 2) { @@ -153,12 +146,18 @@ void *mmalloc(xbt_mheap_t mdp, size_t size) /* There are free fragments of this size. Pop a fragment out of the fragment list and return it. Update the block's nfree and first counters. */ + int frag_nb; result = (void *) next; + block = BLOCK(result); + + frag_nb = RESIDUAL(result, BLOCKSIZE) >> log; + mdp->heapinfo[block].busy_frag.frag_size[frag_nb] = requested_size; + //FIXME setup backtrace + next->prev->next = next->next; if (next->next != NULL) { next->next->prev = next->prev; } - block = BLOCK(result); if (--mdp->heapinfo[block].busy_frag.nfree != 0) { mdp->heapinfo[block].busy_frag.first = RESIDUAL(next->next, BLOCKSIZE) >> log; @@ -168,14 +167,13 @@ void *mmalloc(xbt_mheap_t mdp, size_t size) /* No free fragments of the desired size, so get a new block and break it into fragments, returning the first. */ //printf("(%s) No free fragment...",xbt_thread_self_name()); - result = mmalloc(mdp, BLOCKSIZE); - //printf("(%s) Fragment: %p...",xbt_thread_self_name(),result); - if (result == NULL) { - return (NULL); - } - /* Link all fragments but the first into the free list. */ + result = mmalloc(mdp, BLOCKSIZE); // does not return NULL + + /* Link all fragments but the first into the free list, and mark their requested size to 0. */ + block = BLOCK(result); for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i) { + mdp->heapinfo[block].busy_frag.frag_size[i] = 0; next = (struct list *) ((char *) result + (i << log)); next->next = mdp->fraghead[log].next; next->prev = &mdp->fraghead[log]; @@ -184,9 +182,10 @@ void *mmalloc(xbt_mheap_t mdp, size_t size) next->next->prev = next; } } + mdp->heapinfo[block].busy_frag.frag_size[0] = requested_size; + // FIXME: setup backtrace /* Initialize the nfree and first counters for this block. */ - block = BLOCK(result); mdp->heapinfo[block].type = log; mdp->heapinfo[block].busy_frag.nfree = i - 1; mdp->heapinfo[block].busy_frag.first = i - 1; @@ -199,7 +198,7 @@ void *mmalloc(xbt_mheap_t mdp, size_t size) blocks = BLOCKIFY(size); start = block = MALLOC_SEARCH_START; while (mdp->heapinfo[block].free_block.size < blocks) { - if (mdp->heapinfo[block].type >=0) { + if (mdp->heapinfo[block].type >=0) { // Don't trust xbt_die and friends in malloc-level library, you fool! fprintf(stderr,"Internal error: found a free block not marked as such (block=%lu type=%lu). Please report this bug.\n",(unsigned long)block,(unsigned long)mdp->heapinfo[block].type); abort(); } @@ -224,16 +223,17 @@ void *mmalloc(xbt_mheap_t mdp, size_t size) continue; } result = register_morecore(mdp, blocks * BLOCKSIZE); - if (result == NULL) { - return (NULL); - } + block = BLOCK(result); for (it=0;itheapinfo[block+it].type = 0; mdp->heapinfo[block].busy_block.size = blocks; - mdp->heapinfo[block].busy_block.busy_size = size; - return (result); + mdp->heapinfo[block].busy_block.busy_size = requested_size; + // FIXME: setup backtrace + + return result; } + /* Need large block(s), but found some in the existing heap */ } /* At this point we have found a suitable free list entry. @@ -263,7 +263,7 @@ void *mmalloc(xbt_mheap_t mdp, size_t size) for (it=0;itheapinfo[block+it].type = 0; mdp->heapinfo[block].busy_block.size = blocks; - mdp->heapinfo[block].busy_block.busy_size = size; + mdp->heapinfo[block].busy_block.busy_size = requested_size; } //printf("(%s) Done mallocing. Result is %p\n",xbt_thread_self_name(),result);fflush(stdout); return (result); diff --git a/src/xbt/mmalloc/mmorecore.c b/src/xbt/mmalloc/mmorecore.c index 9e2d22ed53..338a1b6de7 100644 --- a/src/xbt/mmalloc/mmorecore.c +++ b/src/xbt/mmalloc/mmorecore.c @@ -50,12 +50,14 @@ static size_t pagesize; /* Get core for the memory region specified by MDP, using SIZE as the amount to either add to or subtract from the existing region. Works - like sbrk(), but using mmap(). */ + like sbrk(), but using mmap(). + + It never returns NULL. Instead, it dies verbosely on errors. */ void *mmorecore(struct mdesc *mdp, int size) { ssize_t test = 0; - void *result = NULL; + void *result; // please keep it uninitialized to track issues off_t foffset; /* File offset at which new mapping will start */ size_t mapbytes; /* Number of bytes to map */ void *moveto; /* Address where we wish to move "break value" to */ @@ -72,8 +74,8 @@ void *mmorecore(struct mdesc *mdp, int size) } else if (size < 0) { /* We are deallocating memory. If the amount requested would cause us to try to deallocate back past the base of the mmap'd region - then do nothing, and return NULL. Otherwise, deallocate the - memory and return the old break value. */ + then die verbosely. Otherwise, deallocate the memory and return + the old break value. */ if (((char *) mdp->breakval) + size >= (char *) mdp->base) { result = (void *) mdp->breakval; mdp->breakval = (char *) mdp->breakval + size; @@ -81,13 +83,16 @@ void *mmorecore(struct mdesc *mdp, int size) munmap(moveto, (size_t) (((char *) mdp->top) - ((char *) moveto)) - 1); mdp->top = moveto; + } else { + fprintf(stderr,"Internal error: mmap was asked to deallocate more memory than it previously allocated. Bailling out now!\n"); + abort(); } } else { /* We are allocating memory. Make sure we have an open file descriptor if not working with anonymous memory. */ if (!(mdp->flags & MMALLOC_ANONYMOUS) && mdp->fd < 0) { - THROWF(system_error,0,"mmap file descriptor <0 (%d), without MMALLOC_ANONYMOUS being in the flags",mdp->fd); - result = NULL; + fprintf(stderr,"Internal error: mmap file descriptor <0 (%d), without MMALLOC_ANONYMOUS being in the flags.\n",mdp->fd); + abort(); } else if ((char *) mdp->breakval + size > (char *) mdp->top) { /* The request would move us past the end of the currently mapped memory, so map in enough more memory to satisfy @@ -102,8 +107,10 @@ void *mmorecore(struct mdesc *mdp, int size) /* FIXME: Test results of lseek() */ lseek(mdp->fd, foffset + mapbytes - 1, SEEK_SET); test = write(mdp->fd, &buf, 1); - if (test == -1) - THROWF(system_error, 0, "write to mmap'ed fd failed! error: %s", strerror(errno)); + if (test == -1) { + fprintf(stderr,"Internal error: write to mmap'ed fd failed! error: %s", strerror(errno)); + abort(); + } } /* Let's call mmap. Note that it is possible that mdp->top @@ -112,8 +119,10 @@ void *mmorecore(struct mdesc *mdp, int size) MAP_PRIVATE_OR_SHARED(mdp) | MAP_IS_ANONYMOUS(mdp) | MAP_FIXED, MAP_ANON_OR_FD(mdp), foffset); - if (mapto == (void *) -1/* That's MAP_FAILED */) - THROWF(system_error,0,"mmap returned MAP_FAILED! error: %s",strerror(errno)); + if (mapto == (void *) -1/* That's MAP_FAILED */) { + fprintf(stderr,"Internal error: mmap returned MAP_FAILED! error: %s",strerror(errno)); + abort(); + } if (mdp->top == 0) mdp->base = mdp->breakval = mapto; diff --git a/src/xbt/mmalloc/mmprivate.h b/src/xbt/mmalloc/mmprivate.h index 423c57f5a6..24ca7e8449 100644 --- a/src/xbt/mmalloc/mmprivate.h +++ b/src/xbt/mmalloc/mmprivate.h @@ -35,13 +35,26 @@ requests receive one or more whole blocks, and small requests receive a fragment of a block. Fragment sizes are powers of two, and all fragments of a block are the same size. When all the - fragments in a block have been freed, the block itself is freed. */ + fragments in a block have been freed, the block itself is freed. + + FIXME: we are not targeting 16bits machines anymore; update values */ #define INT_BIT (CHAR_BIT * sizeof(int)) #define BLOCKLOG (INT_BIT > 16 ? 12 : 9) #define BLOCKSIZE ((unsigned int) 1 << BLOCKLOG) #define BLOCKIFY(SIZE) (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE) +/* We keep fragment-specific meta-data for introspection purposes, and these + * information are kept in fixed lenght arrays. Here is the computation of + * that size. + * + * Never make SMALLEST_POSSIBLE_MALLOC smaller than sizeof(list) because we + * need to enlist the free fragments. + */ + +#define SMALLEST_POSSIBLE_MALLOC (sizeof(struct list)) +#define MAX_FRAGMENT_PER_BLOCK (BLOCKSIZE / SMALLEST_POSSIBLE_MALLOC) + /* The difference between two pointers is a signed int. On machines where the data addresses have the high bit set, we need to ensure that the difference becomes an unsigned int when we are using the address as an @@ -58,8 +71,8 @@ #define HEAP (INT_BIT > 16 ? 4194304 : 65536) /* Number of contiguous free blocks allowed to build up at the end of - memory before they will be returned to the system. */ - + memory before they will be returned to the system. + FIXME: this is not used anymore: we never return memory to the system. */ #define FINAL_FREE_BLOCKS 8 /* Where to start searching the free list when looking for new memory. @@ -77,6 +90,12 @@ const char *xbt_thread_self_name(void); +/* Doubly linked lists of free fragments. */ +struct list { + struct list *next; + struct list *prev; +}; + /* Data structure giving per-block information. * * There is one such structure in the mdp->heapinfo array, @@ -113,6 +132,7 @@ typedef struct { struct { size_t nfree; /* Free fragments in a fragmented block. */ size_t first; /* First free fragment of the block. */ + unsigned short frag_size[MAX_FRAGMENT_PER_BLOCK]; } busy_frag; struct { size_t size; /* Size (in blocks) of a large cluster. */ @@ -127,12 +147,6 @@ typedef struct { }; } malloc_info; -/* Doubly linked lists of free fragments. */ -struct list { - struct list *next; - struct list *prev; -}; - /* Internal structure that defines the format of the malloc-descriptor. This gets written to the base address of the region that mmalloc is managing, and thus also becomes the file header for the mapped file, diff --git a/src/xbt/mmalloc/mrealloc.c b/src/xbt/mmalloc/mrealloc.c index 82ab8768df..0e03a922e2 100644 --- a/src/xbt/mmalloc/mrealloc.c +++ b/src/xbt/mmalloc/mrealloc.c @@ -55,10 +55,11 @@ void *mrealloc(xbt_mheap_t mdp, void *ptr, size_t size) switch (type) { case 0: /* Maybe reallocate a large block to a small fragment. */ - if (size <= BLOCKSIZE / 2) { - //printf("(%s) alloc large block...",xbt_thread_self_name()); + + if (size <= BLOCKSIZE / 2) { // Full block -> Fragment; no need to optimize for time + result = mmalloc(mdp, size); - if (result != NULL) { + if (result != NULL) { // useless (mmalloc never returns NULL), but harmless memcpy(result, ptr, size); mfree(mdp, ptr); return (result);