From ea39fd08c260e7faa92334952d4acd37e3892b6c Mon Sep 17 00:00:00 2001 From: Martin Quinson Date: Tue, 16 Oct 2012 18:06:31 +0200 Subject: [PATCH] Do not store any metadata where the user (was) legitimate to write Before, free fragments were chained within the user area, leading to obscure breakdown when the user was mean enough to write into the block after a free(). Now, these data are stored as swag directly into the mdp->heapinfo that is where we store our metadata. We have one extra complication due to the fact that heapinfo must be reallocated when we mmap more memory. When this happens, we have to update all swag hooks manually to apply the offset. Yup, this went that bad :-/ --- src/xbt/mmalloc/mfree.c | 52 +++++------------ src/xbt/mmalloc/mm_module.c | 23 +------- src/xbt/mmalloc/mmalloc.c | 110 ++++++++++++++++++++++-------------- src/xbt/mmalloc/mmorecore.c | 10 +++- src/xbt/mmalloc/mmprivate.h | 17 ++++-- src/xbt/mmalloc/mrealloc.c | 2 + 6 files changed, 102 insertions(+), 112 deletions(-) diff --git a/src/xbt/mmalloc/mfree.c b/src/xbt/mmalloc/mfree.c index 01cf670188..af8372068e 100644 --- a/src/xbt/mmalloc/mfree.c +++ b/src/xbt/mmalloc/mfree.c @@ -22,9 +22,11 @@ void mfree(struct mdesc *mdp, void *ptr) int type; size_t block, frag_nb; register size_t i; - struct list *prev, *next; int it; + mmalloc_paranoia(mdp); +// fprintf(stderr,"free(%p)\n",ptr); + if (ptr == NULL) return; @@ -35,8 +37,6 @@ void mfree(struct mdesc *mdp, void *ptr) abort(); } - check_fraghead(mdp); - type = mdp->heapinfo[block].type; switch (type) { @@ -148,11 +148,6 @@ void mfree(struct mdesc *mdp, void *ptr) mdp -> heapstats.chunks_free++; mdp -> heapstats.bytes_free += 1 << type; - /* Get the address of the first free fragment in this block. */ - prev = (struct list *) - ((char *) ADDRESS(block) + - (mdp->heapinfo[block].busy_frag.first << type)); - frag_nb = RESIDUAL(ptr, BLOCKSIZE) >> type; if( mdp->heapinfo[block].busy_frag.frag_size[frag_nb] == -1){ @@ -163,18 +158,12 @@ void mfree(struct mdesc *mdp, void *ptr) /* Set size used in the fragment to -1 */ mdp->heapinfo[block].busy_frag.frag_size[frag_nb] = -1; +// fprintf(stderr,"nfree:%zu capa:%d\n", mdp->heapinfo[block].busy_frag.nfree,(BLOCKSIZE >> type)); if (mdp->heapinfo[block].busy_frag.nfree == (BLOCKSIZE >> type) - 1) { - /* If all fragments of this block are free, remove them - from the fragment list and free the whole block. */ - next = prev; - for (i = 1; i < (size_t) (BLOCKSIZE >> type); ++i) { - next = next->next; - } - prev->prev->next = next; - if (next != NULL) { - next->prev = prev->prev; - } + /* If all fragments of this block are free, remove this block from its swag and free the whole block. */ + xbt_swag_remove(&mdp->heapinfo[block],&mdp->fraghead[type]); + /* pretend that this block is used and free it so that it gets properly coalesced with adjacent free blocks */ mdp->heapinfo[block].type = 0; mdp->heapinfo[block].busy_block.size = 1; @@ -188,33 +177,18 @@ void mfree(struct mdesc *mdp, void *ptr) mfree((void *) mdp, (void *) ADDRESS(block)); } else if (mdp->heapinfo[block].busy_frag.nfree != 0) { - /* If some fragments of this block are free, link this - fragment into the fragment list after the first free - fragment of this block. */ - next = (struct list *) ptr; - next->next = prev->next; - next->prev = prev; - prev->next = next; - if (next->next != NULL) { - next->next->prev = next; - } + /* If some fragments of this block are free, you know what? I'm already happy. */ ++mdp->heapinfo[block].busy_frag.nfree; } else { /* No fragments of this block were free before the one we just released, - * so link this fragment into the fragment list and announce that + * so add this block to the swag and announce that it is the first free fragment of this block. */ - prev = (struct list *) ptr; mdp->heapinfo[block].busy_frag.nfree = 1; - mdp->heapinfo[block].busy_frag.first = frag_nb; - prev->next = mdp->fraghead[type].next; - prev->prev = &mdp->fraghead[type]; - prev->prev->next = prev; - if (prev->next != NULL) { - prev->next->prev = prev; - } + mdp->heapinfo[block].freehook.prev = NULL; + mdp->heapinfo[block].freehook.next = NULL; + + xbt_swag_insert(&mdp->heapinfo[block],&mdp->fraghead[type]); } break; } - - check_fraghead(mdp); } diff --git a/src/xbt/mmalloc/mm_module.c b/src/xbt/mmalloc/mm_module.c index 8f538f19e5..06f6266191 100644 --- a/src/xbt/mmalloc/mm_module.c +++ b/src/xbt/mmalloc/mm_module.c @@ -312,8 +312,6 @@ static void mmalloc_fork_child(void) } } - - /* Initialize the default malloc descriptor. */ void *mmalloc_preinit(void) { @@ -323,7 +321,7 @@ void *mmalloc_preinit(void) void *addr = (void*)(((unsigned long)sbrk(0) + HEAP_OFFSET) & mask); __mmalloc_default_mdp = xbt_mheap_new(-1, addr); /* Fixme? only the default mdp in protected against forks */ - res = xbt_os_thread_atfork(mmalloc_fork_prepare, + res = xbt_os_thread_atfork(mmalloc_fork_prepare, //FIXME: KILLME when things settle a bit mmalloc_fork_parent, mmalloc_fork_child); if (res != 0) THROWF(system_error,0,"xbt_os_thread_atfork() failed: return value %d",res); @@ -339,22 +337,3 @@ void mmalloc_postexit(void) // mmalloc_detach(__mmalloc_default_mdp); xbt_mheap_destroy_no_free(__mmalloc_default_mdp); } - -void check_fraghead(struct mdesc *mdp){ - - struct list* next; - int j; - - for (j=8; j<12; j++){ - next = mdp->fraghead[j].next; - if(next != NULL){ - while(next->next != NULL){ - if(next->next->prev == NULL); - next = next->next; - } - } - } - - //fprintf(stderr, "check fraghead ok\n"); - -} diff --git a/src/xbt/mmalloc/mmalloc.c b/src/xbt/mmalloc/mmalloc.c index aaa9e242c9..95c5db6671 100644 --- a/src/xbt/mmalloc/mmalloc.c +++ b/src/xbt/mmalloc/mmalloc.c @@ -51,6 +51,9 @@ static void *align(struct mdesc *mdp, size_t size) * properly, we need to make the align function publicly visible, too */ static void initialize(xbt_mheap_t mdp) { + int i; + malloc_info mi; /* to compute the offset of the swag hook */ + mdp->heapsize = HEAP / BLOCKSIZE; mdp->heapinfo = (malloc_info *) align(mdp, mdp->heapsize * sizeof(malloc_info)); @@ -62,12 +65,20 @@ static void initialize(xbt_mheap_t mdp) mdp->heapindex = 0; mdp->heapbase = (void *) mdp->heapinfo; mdp->flags |= MMALLOC_INITIALIZED; + + for (i=0;ifraghead[i]), + xbt_swag_offset(mi, freehook)); + } } +#define update_hook(a,offset) do { if (a) { a = ((char*)a +(offset));} }while(0) + /* Get neatly aligned memory from the low level layers, and register it * into the heap info table as necessary. */ static void *register_morecore(struct mdesc *mdp, size_t size) { + int i; void *result; malloc_info *newinfo, *oldinfo; size_t newsize; @@ -87,6 +98,21 @@ static void *register_morecore(struct mdesc *mdp, size_t size) newinfo = (malloc_info *) align(mdp, newsize * sizeof(malloc_info)); memset(newinfo, 0, newsize * sizeof(malloc_info)); memcpy(newinfo, oldinfo, mdp->heapsize * sizeof(malloc_info)); + + /* Update the swag of busy blocks containing free fragments by applying the offset to all swag_hooks. Yeah. My hand is right in the fan and I still type */ + size_t offset=((char*)newinfo)-((char*)oldinfo); + + for (i=1/*first element of heapinfo describes the mdesc area*/; + iheaplimit; + i++) { + update_hook(newinfo[i].freehook.next,offset); + update_hook(newinfo[i].freehook.prev,offset); + } + // also update the starting points of the swag + for (i=0;ifraghead[i].head,offset); + update_hook(mdp->fraghead[i].tail,offset); + } mdp->heapinfo = newinfo; /* mark the space previously occupied by the block info as free by first marking it @@ -104,10 +130,12 @@ static void *register_morecore(struct mdesc *mdp, size_t size) mdp->heaplimit = BLOCK((char *) result + size); return (result); } +#undef update_hook /* Allocate memory from the heap. */ void *mmalloc(xbt_mheap_t mdp, size_t size) { void *res= mmalloc_no_memset(mdp,size); +// fprintf(stderr,"malloc(%zu)~>%p\n",size,res); memset(res,0,size); return res; } @@ -119,14 +147,11 @@ void *mmalloc_no_memset(xbt_mheap_t mdp, size_t size) void *result; size_t block, blocks, lastblocks, start; register size_t i; - struct list *next; register size_t log; int it; size_t requested_size = size; // The amount of memory requested by user, for real - check_fraghead(mdp); - /* 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. @@ -139,6 +164,8 @@ void *mmalloc_no_memset(xbt_mheap_t mdp, size_t size) if (!(mdp->flags & MMALLOC_INITIALIZED)) initialize(mdp); + mmalloc_paranoia(mdp); + /* Determine the allocation policy based on the request size. */ if (size <= BLOCKSIZE / 2) { /* Small allocation to receive a fragment of a block. @@ -149,30 +176,33 @@ void *mmalloc_no_memset(xbt_mheap_t mdp, size_t size) ++log; } - /* Look in the fragment lists for a - free fragment of the desired size. */ - next = mdp->fraghead[log].next; - if (next != NULL) { - /* 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; - xbt_backtrace_no_malloc(mdp->heapinfo[block].busy_frag.bt[frag_nb],XBT_BACKTRACE_SIZE); - - next->prev->next = next->next; - if (next->next != NULL) { - next->next->prev = next->prev; - } - if (--mdp->heapinfo[block].busy_frag.nfree != 0) { - mdp->heapinfo[block].busy_frag.first = - RESIDUAL(next->next, BLOCKSIZE) >> log; + /* Look in the fragment lists for a free fragment of the desired size. */ + if (xbt_swag_size(&mdp->fraghead[log])>0) { + /* There are free fragments of this size; Get one of them and prepare to return it. + Update the block's nfree and if no other free fragment, get out of the swag. */ + + /* search a fragment that I could return as a result */ + malloc_info *candidate_info = xbt_swag_getFirst(&mdp->fraghead[log]); + size_t candidate_block = (candidate_info - &(mdp->heapinfo[0])); + size_t candidate_frag; + for (candidate_frag=0;candidate_frag<(size_t) (BLOCKSIZE >> log);candidate_frag++) + if (candidate_info->busy_frag.frag_size[candidate_frag] == -1) + break; + xbt_assert(candidate_frag < (size_t) (BLOCKSIZE >> log), + "Block %zu was registered as containing free fragments of type %zu, but I can't find any",candidate_block,log); + + result = (void*) (((char*)ADDRESS(candidate_block)) + (candidate_frag << log)); + + /* Remove this fragment from the list of free guys */ + candidate_info->busy_frag.nfree--; + if (candidate_info->busy_frag.nfree == 0) { + xbt_swag_remove(candidate_info,&mdp->fraghead[log]); } + /* Update our metadata about this fragment */ + candidate_info->busy_frag.frag_size[candidate_frag] = requested_size; + xbt_backtrace_no_malloc(candidate_info->busy_frag.bt[candidate_frag],XBT_BACKTRACE_SIZE); + /* Update the statistics. */ mdp -> heapstats.chunks_used++; mdp -> heapstats.bytes_used += 1 << log; @@ -182,30 +212,26 @@ void *mmalloc_no_memset(xbt_mheap_t mdp, size_t size) } else { /* 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); // does not return NULL - - /* Link all fragments but the first into the free list, and mark their requested size to -1. */ block = BLOCK(result); + + mdp->heapinfo[block].type = log; + /* Link all fragments but the first as free, and add the block to the swag of blocks containing free frags */ for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i) { mdp->heapinfo[block].busy_frag.frag_size[i] = -1; - next = (struct list *) ((char *) result + (i << log)); - next->next = mdp->fraghead[log].next; - next->prev = &mdp->fraghead[log]; - next->prev->next = next; - if (next->next != NULL) { - next->next->prev = next; - } } + mdp->heapinfo[block].busy_frag.nfree = i - 1; + mdp->heapinfo[block].freehook.prev = NULL; + mdp->heapinfo[block].freehook.next = NULL; + + xbt_swag_insert(&mdp->heapinfo[block], &(mdp->fraghead[log])); + + /* mark the fragment returned as busy */ mdp->heapinfo[block].busy_frag.frag_size[0] = requested_size; xbt_backtrace_no_malloc(mdp->heapinfo[block].busy_frag.bt[0],XBT_BACKTRACE_SIZE); - /* Initialize the nfree and first counters for this block. */ - mdp->heapinfo[block].type = log; - mdp->heapinfo[block].busy_frag.nfree = i - 1; - mdp->heapinfo[block].busy_frag.first = i - 1; - + /* update stats */ mdp -> heapstats.chunks_free += (BLOCKSIZE >> log) - 1; mdp -> heapstats.bytes_free += BLOCKSIZE - (1 << log); mdp -> heapstats.bytes_used -= BLOCKSIZE - (1 << log); @@ -254,8 +280,6 @@ void *mmalloc_no_memset(xbt_mheap_t mdp, size_t size) mdp -> heapstats.chunks_used++; mdp -> heapstats.bytes_used += blocks * BLOCKSIZE; - check_fraghead(mdp); - return result; } /* Need large block(s), but found some in the existing heap */ @@ -299,6 +323,6 @@ void *mmalloc_no_memset(xbt_mheap_t mdp, size_t size) } //printf("(%s) Done mallocing. Result is %p\n",xbt_thread_self_name(),result);fflush(stdout); - check_fraghead(mdp); + return (result); } diff --git a/src/xbt/mmalloc/mmorecore.c b/src/xbt/mmalloc/mmorecore.c index d374c7e55d..dfd9cf743d 100644 --- a/src/xbt/mmalloc/mmorecore.c +++ b/src/xbt/mmalloc/mmorecore.c @@ -3,8 +3,7 @@ Contributed by Fred Fish at Cygnus Support. fnf@cygnus.com */ -/* Copyright (c) 2010. The SimGrid Team. - * All rights reserved. */ +/* Copyright (c) 2010-2012. The SimGrid Team. All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ @@ -64,6 +63,7 @@ void *mmorecore(struct mdesc *mdp, int size) void *mapto; /* Address we actually mapped to */ char buf = 0; /* Single byte to write to extend mapped file */ +// fprintf(stderr,"increase %p by %u\n",mdp,size); if (pagesize == 0) pagesize = getpagesize(); @@ -120,7 +120,11 @@ void *mmorecore(struct mdesc *mdp, int size) MAP_FIXED, MAP_ANON_OR_FD(mdp), foffset); if (mapto == (void *) -1/* That's MAP_FAILED */) { - fprintf(stderr,"Internal error: mmap returned MAP_FAILED! error: %s",strerror(errno)); + char buff[1024]; + fprintf(stderr,"Internal error: mmap returned MAP_FAILED! error: %s\n",strerror(errno)); + sprintf(buff,"cat /proc/%d/maps",getpid()); + system(buff); + sleep(1); abort(); } diff --git a/src/xbt/mmalloc/mmprivate.h b/src/xbt/mmalloc/mmprivate.h index 63ee257685..4fce4c64d0 100644 --- a/src/xbt/mmalloc/mmprivate.h +++ b/src/xbt/mmalloc/mmprivate.h @@ -18,6 +18,7 @@ #include "xbt/mmalloc.h" #include "xbt/ex.h" #include "xbt/dynar.h" +#include "xbt/swag.h" #include #include @@ -144,6 +145,7 @@ typedef struct s_heap_area_pair{ * */ typedef struct { + s_xbt_swag_hookup_t freehook; /* to register this block as having empty frags when needed */ int type; /* 0: busy large block >0: busy fragmented (fragments of size 2^type bytes) <0: free block */ @@ -151,8 +153,7 @@ typedef struct { union { /* Heap information for a busy block. */ struct { - size_t nfree; /* Free fragments in a fragmented block. */ - size_t first; /* First free fragment of the block. */ + size_t nfree; /* Free fragments in a fragmented block. */ short frag_size[MAX_FRAGMENT_PER_BLOCK]; void *bt[MAX_FRAGMENT_PER_BLOCK][XBT_BACKTRACE_SIZE]; /* Where it was malloced (or realloced lastly) */ heap_area_t equal_to[MAX_FRAGMENT_PER_BLOCK]; @@ -220,8 +221,10 @@ struct mdesc { /* Table indexed by block number giving per-block information. */ malloc_info *heapinfo; - /* List of all blocks containing free fragments of this size. The array indice is the log2 of requested size */ - struct list fraghead[BLOCKLOG]; + /* List of all blocks containing free fragments of this size. + * The array indice is the log2 of requested size. + * Actually only the sizes 8->11 seem to be used, but who cares? */ + s_xbt_swag_t fraghead[BLOCKLOG]; /* The base address of the memory region for this malloc heap. This is the location where the bookkeeping data for mmap and for malloc @@ -280,6 +283,10 @@ extern void *mmorecore(struct mdesc *mdp, int size); #define LOCK(mdp) sem_wait(&mdp->sem) #define UNLOCK(mdp) sem_post(&mdp->sem) -void check_fraghead(struct mdesc *mdp); +static XBT_INLINE void mmalloc_paranoia(struct mdesc *mdp){ + + /* nothing to fear for no */ + +} #endif /* __MMPRIVATE_H */ diff --git a/src/xbt/mmalloc/mrealloc.c b/src/xbt/mmalloc/mrealloc.c index c1078bdeaf..b9deaffdde 100644 --- a/src/xbt/mmalloc/mrealloc.c +++ b/src/xbt/mmalloc/mrealloc.c @@ -112,6 +112,8 @@ void *mrealloc(xbt_mheap_t mdp, void *ptr, size_t size) mdp->heaplimit = oldlimit; result = mmalloc_no_memset(mdp, requested_size); + //fprintf(stderr,"remalloc(%zu)~>%p\n",requested_size,result); + if (ptr != result) memmove(result, ptr, blocks * BLOCKSIZE); /* FIXME: we should memset the end of the recently area */ -- 2.20.1