From: Marion Guthmuller Date: Sat, 29 Sep 2012 20:20:47 +0000 (+0200) Subject: model-checker : store equality detected in heap comparison if fragment or block numbe... X-Git-Tag: v3_8~129 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/a326f3588402d8813b4556d92e9266c9ed10215b model-checker : store equality detected in heap comparison if fragment or block numbers are different --- diff --git a/include/xbt/mmalloc.h b/include/xbt/mmalloc.h index aa6eeaa7d9..e47604ffb5 100644 --- a/include/xbt/mmalloc.h +++ b/include/xbt/mmalloc.h @@ -58,7 +58,7 @@ extern xbt_mheap_t mmalloc_get_default_md(void); void mmalloc_set_current_heap(xbt_mheap_t new_heap); xbt_mheap_t mmalloc_get_current_heap(void); -int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stacks1, xbt_dynar_t *stacks2); +int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stacks1, xbt_dynar_t *stacks2, xbt_dynar_t *equals); int mmalloc_linear_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2); void mmalloc_backtrace_block_display(void* heapinfo, int block); diff --git a/src/include/mc/datatypes.h b/src/include/mc/datatypes.h index dba1759506..db6d8344a7 100644 --- a/src/include/mc/datatypes.h +++ b/src/include/mc/datatypes.h @@ -12,8 +12,12 @@ SG_BEGIN_DECL() /******************************* Transitions **********************************/ + typedef struct s_mc_transition *mc_transition_t; + +/*********** Structures for snapshot comparison **************************/ + typedef struct s_mc_ignore_region{ int block; int fragment; @@ -24,7 +28,13 @@ typedef struct s_mc_ignore_region{ typedef struct s_stack_region{ void *address; char *process_name; + size_t size; }s_stack_region_t, *stack_region_t; +typedef struct s_heap_equality{ + void *address1; + void *address2; +}s_heap_equality_t, *heap_equality_t; + SG_END_DECL() #endif /* _MC_MC_H */ diff --git a/src/xbt/mmalloc/mm_diff.c b/src/xbt/mmalloc/mm_diff.c index 8bc6173235..a6da0077ea 100644 --- a/src/xbt/mmalloc/mm_diff.c +++ b/src/xbt/mmalloc/mm_diff.c @@ -18,23 +18,19 @@ extern char *xbt_binary_name; xbt_dynar_t mmalloc_ignore; xbt_dynar_t stacks_areas; -typedef struct s_heap_area_pair{ - int block1; - int fragment1; - int block2; - int fragment2; -}s_heap_area_pair_t, *heap_area_pair_t; - static void heap_area_pair_free(heap_area_pair_t pair); static void heap_area_pair_free_voidp(void *d); static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2); static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2); +static heap_area_t new_heap_area(int block, int fragment); static int compare_area(void *area1, void* area2, size_t size, xbt_dynar_t previous, int check_ignore); -static void match_equals(xbt_dynar_t list); +static void match_equals(xbt_dynar_t list, xbt_dynar_t *equals); static int in_mmalloc_ignore(int block, int fragment); static size_t heap_comparison_ignore(void *address); +static void add_heap_equality(xbt_dynar_t *equals, void *a1, void *a2); +static void remove_heap_equality(xbt_dynar_t *equals, int address, void *a); static char* is_stack(void *address); @@ -89,13 +85,14 @@ void mmalloc_backtrace_fragment_display(void* heapinfo, int block, int frag){ } + void *s_heap, *heapbase1, *heapbase2; malloc_info *heapinfo1, *heapinfo2; size_t heaplimit, heapsize1, heapsize2; int ignore_done; -int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stack1, xbt_dynar_t *stack2){ +int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stack1, xbt_dynar_t *stack2, xbt_dynar_t *equals){ if(heap1 == NULL && heap1 == NULL){ XBT_DEBUG("Malloc descriptors null"); @@ -126,6 +123,7 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2; void *real_addr_block1, *real_addr_block2; char *stack_name; + int nb_block1=0, nb_frag1=0, nb_block2=0, nb_frag2=0; xbt_dynar_t previous = xbt_dynar_new(sizeof(heap_area_pair_t), heap_area_pair_free_voidp); @@ -138,11 +136,15 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac while(i1<=heaplimit){ if(heapinfo1[i1].type == 0){ - heapinfo1[i1].busy_block.equal_to = -1; + if(heapinfo1[i1].busy_block.busy_size > 0) + nb_block1++; + heapinfo1[i1].busy_block.equal_to = NULL; } if(heapinfo1[i1].type > 0){ - for(j1=0; j1 < MAX_FRAGMENT_PER_BLOCK; j1++){ - heapinfo1[i1].busy_frag.equal_to[j1] = -1; + for(j1=0; j1 < (size_t) (BLOCKSIZE >> heapinfo1[i1].type); j1++){ + if(heapinfo1[i1].busy_frag.frag_size[j1] > 0) + nb_frag1++; + heapinfo1[i1].busy_frag.equal_to[j1] = NULL; } } i1++; @@ -152,16 +154,25 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac while(i2<=heaplimit){ if(heapinfo2[i2].type == 0){ - heapinfo2[i2].busy_block.equal_to = -1; + if(heapinfo2[i2].busy_block.busy_size > 0) + nb_block2++; + heapinfo2[i2].busy_block.equal_to = NULL; } if(heapinfo2[i2].type > 0){ - for(j2=0; j2 < MAX_FRAGMENT_PER_BLOCK; j2++){ - heapinfo2[i2].busy_frag.equal_to[j2] = -1; + for(j2=0; j2 < (size_t) (BLOCKSIZE >> heapinfo2[i2].type); j2++){ + if(heapinfo2[i2].busy_frag.frag_size[j2] > 0) + nb_frag2++; + heapinfo2[i2].busy_frag.equal_to[j2] = NULL; } } i2++; } + if(nb_block1 != nb_block2 || nb_frag1 != nb_frag2){ + XBT_DEBUG("Different number of busy blocks (%d - %d) or busy fragments (%d - %d)", nb_block1, nb_block2, nb_frag1, nb_frag2); + return 1; + } + /* Check busy blocks*/ i1 = 1; @@ -176,15 +187,15 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac } addr_block1 = ((void*) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE + (char*)heapbase1)); + real_addr_block1 = (char*)((xbt_mheap_t)s_heap)->heapbase + (((char *)addr_block1) - (char *)heapbase1); if(heapinfo1[i1].type == 0){ /* Large block */ - real_addr_block1 = (char*)((xbt_mheap_t)s_heap)->heapbase + (((char *)addr_block1) - (char *)heapbase1); - if((stack_name = is_stack(real_addr_block1)) != NULL){ stack_region_t stack = xbt_new0(s_stack_region_t, 1); stack->address = addr_block1; stack->process_name = strdup(stack_name); + stack->size = heapinfo1[i1].busy_block.busy_size; xbt_dynar_push(*stack1, &stack); } @@ -192,52 +203,61 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac i1++; continue; } + + if(heapinfo1[i1].busy_block.equal_to != NULL){ + i1++; + continue; + } i2 = 1; equal = 0; - + /* Try first to associate to same block in the other heap */ if(heapinfo2[current_block].type == heapinfo1[current_block].type){ + + if(heapinfo2[current_block].busy_block.equal_to == NULL){ - if(heapinfo1[current_block].busy_block.busy_size == heapinfo2[current_block].busy_block.busy_size){ + if(heapinfo1[current_block].busy_block.busy_size == heapinfo2[current_block].busy_block.busy_size){ - addr_block2 = ((void*) (((ADDR2UINT(current_block)) - 1) * BLOCKSIZE + (char*)heapbase2)); + addr_block2 = ((void*) (((ADDR2UINT(current_block)) - 1) * BLOCKSIZE + (char*)heapbase2)); - real_addr_block2 = (char*)((xbt_mheap_t)s_heap)->heapbase + (((char *)addr_block2) - (char *)heapbase2); + real_addr_block2 = (char*)((xbt_mheap_t)s_heap)->heapbase + (((char *)addr_block2) - (char *)heapbase2); - if((stack_name = is_stack(real_addr_block2)) != NULL){ - stack_region_t stack = xbt_new0(s_stack_region_t, 1); - stack->address = addr_block2; - stack->process_name = strdup(stack_name); - xbt_dynar_push(*stack2, &stack); - } - + if((stack_name = is_stack(real_addr_block2)) != NULL){ + stack_region_t stack = xbt_new0(s_stack_region_t, 1); + stack->address = addr_block2; + stack->process_name = strdup(stack_name); + stack->size = heapinfo2[current_block].busy_block.busy_size; + xbt_dynar_push(*stack2, &stack); + } - add_heap_area_pair(previous, current_block, -1, current_block, -1); - - if(ignore_done < xbt_dynar_length(mmalloc_ignore)){ - if(in_mmalloc_ignore((int)current_block, -1)) - res_compare = compare_area(addr_block1, addr_block2, heapinfo1[current_block].busy_block.busy_size, previous, 1); - else + add_heap_area_pair(previous, current_block, -1, current_block, -1); + + if(ignore_done < xbt_dynar_length(mmalloc_ignore)){ + if(in_mmalloc_ignore((int)current_block, -1)) + res_compare = compare_area(addr_block1, addr_block2, heapinfo1[current_block].busy_block.busy_size, previous, 1); + else + res_compare = compare_area(addr_block1, addr_block2, heapinfo1[current_block].busy_block.busy_size, previous, 0); + }else{ res_compare = compare_area(addr_block1, addr_block2, heapinfo1[current_block].busy_block.busy_size, previous, 0); - }else{ - res_compare = compare_area(addr_block1, addr_block2, heapinfo1[current_block].busy_block.busy_size, previous, 0); - } - - if(res_compare == 0){ - for(k=1; k < heapinfo2[current_block].busy_block.size; k++) - heapinfo2[current_block+k].busy_block.equal_to = 1 ; - for(k=1; k < heapinfo1[current_block].busy_block.size; k++) - heapinfo1[current_block+k].busy_block.equal_to = 1 ; - equal = 1; - match_equals(previous); - i1 = i1 + heapinfo1[i1].busy_block.size; + } + + if(res_compare == 0){ + for(k=1; k < heapinfo2[current_block].busy_block.size; k++) + heapinfo2[current_block+k].busy_block.equal_to = new_heap_area(i1, -1); + for(k=1; k < heapinfo1[current_block].busy_block.size; k++) + heapinfo1[current_block+k].busy_block.equal_to = new_heap_area(i1, -1); + equal = 1; + match_equals(previous, equals); + i1 = i1 + heapinfo1[current_block].busy_block.size; + } + + xbt_dynar_reset(previous); + } - xbt_dynar_reset(previous); - } - + } while(i2 <= heaplimit && !equal){ @@ -250,6 +270,7 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac stack_region_t stack = xbt_new0(s_stack_region_t, 1); stack->address = addr_block2; stack->process_name = strdup(stack_name); + stack->size = heapinfo2[i2].busy_block.busy_size; xbt_dynar_push(*stack2, &stack); } @@ -263,7 +284,7 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac continue; } - if(heapinfo2[i2].busy_block.equal_to == 1){ + if(heapinfo2[i2].busy_block.equal_to != NULL){ i2++; continue; } @@ -290,13 +311,14 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac res_compare = compare_area(addr_block1, addr_block2, heapinfo1[i1].busy_block.busy_size, previous, 0); } - if(!res_compare){ + if(res_compare == 0){ for(k=1; k < heapinfo2[i2].busy_block.size; k++) - heapinfo2[i2+k].busy_block.equal_to = 1; + heapinfo2[i2+k].busy_block.equal_to = new_heap_area(i1, -1); for(k=1; k < heapinfo1[i1].busy_block.size; k++) - heapinfo1[i1+k].busy_block.equal_to = 1; + heapinfo1[i1+k].busy_block.equal_to = new_heap_area(i2, -1); equal = 1; - match_equals(previous); + match_equals(previous, equals); + i1 = i1 + heapinfo1[i1].busy_block.size; } xbt_dynar_reset(previous); @@ -317,6 +339,9 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac if(heapinfo1[i1].busy_frag.frag_size[j1] == 0) /* Free fragment */ continue; + if(heapinfo1[i1].busy_frag.equal_to[j1] != NULL) + continue; + addr_frag1 = (void*) ((char *)addr_block1 + (j1 << heapinfo1[i1].type)); i2 = 1; @@ -324,36 +349,40 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac /* Try first to associate to same fragment in the other heap */ if(heapinfo2[current_block].type == heapinfo1[current_block].type){ - - if(heapinfo1[current_block].busy_frag.frag_size[current_fragment] == heapinfo2[current_block].busy_frag.frag_size[current_fragment]){ - addr_block2 = ((void*) (((ADDR2UINT(current_block)) - 1) * BLOCKSIZE + (char*)heapbase2)); - addr_frag2 = (void*) ((char *)addr_block2 + (current_fragment << heapinfo2[current_block].type)); + if(heapinfo2[current_block].busy_frag.equal_to[current_fragment] == NULL){ + + if(heapinfo1[current_block].busy_frag.frag_size[current_fragment] == heapinfo2[current_block].busy_frag.frag_size[current_fragment]){ - add_heap_area_pair(previous, current_block, current_fragment, current_block, current_fragment); + addr_block2 = ((void*) (((ADDR2UINT(current_block)) - 1) * BLOCKSIZE + (char*)heapbase2)); + addr_frag2 = (void*) ((char *)addr_block2 + (current_fragment << heapinfo2[current_block].type)); + + add_heap_area_pair(previous, current_block, current_fragment, current_block, current_fragment); - if(ignore_done < xbt_dynar_length(mmalloc_ignore)){ - if(in_mmalloc_ignore((int)current_block, (int)current_fragment)) - res_compare = compare_area(addr_frag1, addr_frag2, heapinfo1[current_block].busy_frag.frag_size[current_fragment], previous, 1); - else - res_compare = compare_area(addr_frag1, addr_frag2, heapinfo1[current_block].busy_frag.frag_size[current_fragment], previous, 0); - }else{ - res_compare = compare_area(addr_frag1, addr_frag2, heapinfo1[current_block].busy_frag.frag_size[current_fragment], previous, 0); - } - - if(res_compare == 0){ - equal = 1; - match_equals(previous); - } + if(ignore_done < xbt_dynar_length(mmalloc_ignore)){ + if(in_mmalloc_ignore((int)current_block, (int)current_fragment)) + res_compare = compare_area(addr_frag1, addr_frag2, heapinfo1[current_block].busy_frag.frag_size[current_fragment], previous, 1); + else + res_compare = compare_area(addr_frag1, addr_frag2, heapinfo1[current_block].busy_frag.frag_size[current_fragment], previous, 0); + }else{ + res_compare = compare_area(addr_frag1, addr_frag2, heapinfo1[current_block].busy_frag.frag_size[current_fragment], previous, 0); + } + + if(res_compare == 0){ + equal = 1; + match_equals(previous, equals); + } - xbt_dynar_reset(previous); + xbt_dynar_reset(previous); - } + } - } + } + } while(i2 <= heaplimit && !equal){ + if(heapinfo2[i2].type <= 0){ i2++; @@ -365,7 +394,7 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac if(heapinfo2[i2].type == heapinfo1[i1].type && i2 == current_block && j2 == current_fragment) continue; - if(heapinfo2[i2].busy_frag.equal_to[j2] == 1) + if(heapinfo2[i2].busy_frag.equal_to[j2] != NULL) continue; if(heapinfo1[i1].busy_frag.frag_size[j1] != heapinfo2[i2].busy_frag.frag_size[j2]) /* Different size_used */ @@ -386,10 +415,9 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac res_compare = compare_area(addr_frag1, addr_frag2, heapinfo1[i1].busy_frag.frag_size[j1], previous, 0); } - if(!res_compare){ + if(res_compare == 0){ equal = 1; - match_equals(previous); - xbt_dynar_reset(previous); + match_equals(previous, equals); break; } @@ -416,7 +444,7 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac while(i 0){ - if(heapinfo1[i].busy_block.equal_to == -1){ + if(heapinfo1[i].busy_block.equal_to == NULL){ if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){ addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1)); XBT_DEBUG("Block %zu (%p) not found (size used = %zu)", i, addr_block1, heapinfo1[i].busy_block.busy_size); @@ -427,11 +455,11 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac } } if(heapinfo1[i].type > 0){ + addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1)); for(j=0; j < (size_t) (BLOCKSIZE >> heapinfo1[i].type); j++){ if(heapinfo1[i].busy_frag.frag_size[j] > 0){ - if(heapinfo1[i].busy_frag.equal_to[j] == -1){ + if(heapinfo1[i].busy_frag.equal_to[j] == NULL){ if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){ - addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1)); addr_frag1 = (void*) ((char *)addr_block1 + (j << heapinfo1[i].type)); XBT_DEBUG("Block %zu, Fragment %zu (%p) not found (size used = %d)", i, j, addr_frag1, heapinfo1[i].busy_frag.frag_size[j]); mmalloc_backtrace_fragment_display((void*)heapinfo1, i, j); @@ -445,14 +473,14 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac i++; } - XBT_DEBUG("Different blocks or fragments in heap1 : %d\n", nb_diff1); + XBT_DEBUG("Different blocks or fragments in heap1 : %d", nb_diff1); i = 1; while(i 0){ - if(heapinfo2[i].busy_block.equal_to == -1){ + if(heapinfo2[i].busy_block.equal_to == NULL){ if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){ addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2)); XBT_DEBUG("Block %zu (%p) not found (size used = %zu)", i, addr_block2, heapinfo2[i].busy_block.busy_size); @@ -463,11 +491,11 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac } } if(heapinfo2[i].type > 0){ + addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2)); for(j=0; j < (size_t) (BLOCKSIZE >> heapinfo2[i].type); j++){ if(heapinfo2[i].busy_frag.frag_size[j] > 0){ - if(heapinfo2[i].busy_frag.equal_to[j] == -1){ + if(heapinfo2[i].busy_frag.equal_to[j] == NULL){ if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){ - addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2)); addr_frag2 = (void*) ((char *)addr_block2 + (j << heapinfo2[i].type)); XBT_DEBUG( "Block %zu, Fragment %zu (%p) not found (size used = %d)", i, j, addr_frag2, heapinfo2[i].busy_frag.frag_size[j]); mmalloc_backtrace_fragment_display((void*)heapinfo2, i, j); @@ -480,7 +508,7 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac i++; } - XBT_DEBUG("Different blocks or fragments in heap2 : %d\n", nb_diff2); + XBT_DEBUG("Different blocks or fragments in heap2 : %d", nb_diff2); xbt_dynar_free(&previous); @@ -488,6 +516,14 @@ int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stac } +static heap_area_t new_heap_area(int block, int fragment){ + heap_area_t area = NULL; + area = xbt_new0(s_heap_area_t, 1); + area->block = block; + area->fragment = fragment; + return area; +} + static int in_mmalloc_ignore(int block, int fragment){ unsigned int cursor = 0; @@ -601,7 +637,7 @@ static int compare_area(void *area1, void* area2, size_t size, xbt_dynar_t previ res_compare = compare_area(addr_block_pointed1, addr_block_pointed2, heapinfo1[block_pointed1].busy_block.busy_size, previous, 0); } - if(res_compare) + if(res_compare == 1) return 1; } @@ -629,7 +665,7 @@ static int compare_area(void *area1, void* area2, size_t size, xbt_dynar_t previ res_compare = compare_area(addr_frag_pointed1, addr_frag_pointed2, heapinfo1[block_pointed1].busy_frag.frag_size[frag_pointed1], previous, 0); } - if(res_compare) + if(res_compare == 1) return 1; } @@ -646,7 +682,7 @@ static int compare_area(void *area1, void* area2, size_t size, xbt_dynar_t previ frag_pointed1 = ((uintptr_t) (ADDR2UINT (address_pointed1) % (BLOCKSIZE))) >> heapinfo1[block_pointed1].type; frag_pointed2 = ((uintptr_t) (ADDR2UINT (address_pointed2) % (BLOCKSIZE))) >> heapinfo2[block_pointed2].type; - if(heapinfo1[block_pointed1].busy_frag.frag_size[frag_pointed1] != heapinfo2[block_pointed2].busy_frag.frag_size[frag_pointed2]) /* Different size_used */ + if(heapinfo1[block_pointed1].busy_frag.frag_size[frag_pointed1] != heapinfo2[block_pointed2].busy_frag.frag_size[frag_pointed2]) /* Different size_used */ return 1; addr_frag_pointed1 = (void*) ((char *)addr_block_pointed1 + (frag_pointed1 << heapinfo1[block_pointed1].type)); @@ -663,7 +699,7 @@ static int compare_area(void *area1, void* area2, size_t size, xbt_dynar_t previ res_compare = compare_area(addr_frag_pointed1, addr_frag_pointed2, heapinfo1[block_pointed1].busy_frag.frag_size[frag_pointed1], previous, 0); } - if(res_compare) + if(res_compare == 1) return 1; } @@ -731,25 +767,78 @@ static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, in return 1; } -static void match_equals(xbt_dynar_t list){ +static void match_equals(xbt_dynar_t list, xbt_dynar_t *equals){ unsigned int cursor = 0; heap_area_pair_t current_pair; + heap_area_t previous_area; + + void *real_addr_block1, *real_addr_block2, *real_addr_frag1, *real_addr_frag2; xbt_dynar_foreach(list, cursor, current_pair){ + if(current_pair->fragment1 != -1){ - heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1] = 1; - heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2] = 1; + + real_addr_block1 = ((void*) (((ADDR2UINT((size_t)current_pair->block1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase)); + real_addr_frag1 = (void*) ((char *)real_addr_block1 + (current_pair->fragment1 << heapinfo1[current_pair->block1].type)); + real_addr_block2 = ((void*) (((ADDR2UINT((size_t)current_pair->block2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase)); + real_addr_frag2 = (void*) ((char *)real_addr_block2 + (current_pair->fragment2 << heapinfo2[current_pair->block2].type)); + + if(heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1] != NULL){ + remove_heap_equality(equals, 1, real_addr_frag1); + previous_area = heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1]; + xbt_free( heapinfo2[previous_area->block].busy_frag.equal_to[previous_area->fragment]); + heapinfo2[previous_area->block].busy_frag.equal_to[previous_area->fragment] = NULL; + xbt_free(heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1]); + } + if(heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2] != NULL){ + remove_heap_equality(equals, 2, real_addr_frag2); + previous_area = heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2]; + xbt_free(heapinfo1[previous_area->block].busy_frag.equal_to[previous_area->fragment]); + heapinfo1[previous_area->block].busy_frag.equal_to[previous_area->fragment] = NULL; + xbt_free(heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2]); + } + + if(real_addr_frag1 != real_addr_frag2) + add_heap_equality(equals, real_addr_frag1, real_addr_frag2); + + heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1] = new_heap_area(current_pair->block2, current_pair->fragment2); + heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2] = new_heap_area(current_pair->block1, current_pair->fragment1); + }else{ - heapinfo1[current_pair->block1].busy_block.equal_to = 1; - heapinfo2[current_pair->block2].busy_block.equal_to = 1; + + real_addr_block1 = ((void*) (((ADDR2UINT((size_t)current_pair->block1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase)); + real_addr_block2 = ((void*) (((ADDR2UINT((size_t)current_pair->block2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase)); + + if(heapinfo1[current_pair->block1].busy_block.equal_to != NULL){ + remove_heap_equality(equals, 1, real_addr_block1); + previous_area = heapinfo1[current_pair->block1].busy_block.equal_to; + xbt_free(heapinfo2[previous_area->block].busy_block.equal_to); + heapinfo2[previous_area->block].busy_block.equal_to = NULL; + xbt_free(heapinfo1[current_pair->block1].busy_block.equal_to); + } + if(heapinfo2[current_pair->block2].busy_block.equal_to != NULL){ + remove_heap_equality(equals, 2, real_addr_block2); + previous_area = heapinfo2[current_pair->block2].busy_block.equal_to; + xbt_free(heapinfo1[previous_area->block].busy_block.equal_to); + heapinfo1[previous_area->block].busy_block.equal_to = NULL; + xbt_free(heapinfo2[current_pair->block2].busy_block.equal_to); + } + + if(real_addr_block1 != real_addr_block2) + add_heap_equality(equals, real_addr_block1, real_addr_block2); + + heapinfo1[current_pair->block1].busy_block.equal_to = new_heap_area(current_pair->block2, current_pair->fragment2); + heapinfo2[current_pair->block2].busy_block.equal_to = new_heap_area(current_pair->block1, current_pair->fragment1); + } } + } #ifndef max - #define max( a, b ) ( ((a) > (b)) ? (a) : (b) ) +#define max( a, b ) ( ((a) > (b)) ? (a) : (b) ) #endif int mmalloc_linear_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2){ @@ -887,3 +976,89 @@ static char * is_stack(void *address){ return NULL; } + +static void add_heap_equality(xbt_dynar_t *equals, void *a1, void *a2){ + + heap_equality_t he = xbt_new0(s_heap_equality_t, 1); + he->address1 = a1; + he->address2 = a2; + + if(xbt_dynar_is_empty(*equals)){ + + xbt_dynar_insert_at(*equals, 0, &he); + + }else{ + + unsigned int cursor = 0; + int start = 0; + int end = xbt_dynar_length(*equals) - 1; + heap_equality_t current_equality = NULL; + + while(start <= end){ + cursor = (start + end) / 2; + current_equality = (heap_equality_t)xbt_dynar_get_as(*equals, cursor, heap_equality_t); + if(current_equality->address1 == a1){ + if(current_equality->address2 == a2) + return; + if(current_equality->address2 < a2) + start = cursor + 1; + if(current_equality->address2 > a2) + end = cursor - 1; + } + if(current_equality->address1 < a1) + start = cursor + 1; + if(current_equality->address1 > a1) + end = cursor - 1; + } + + if(current_equality->address1 < a1) + xbt_dynar_insert_at(*equals, cursor + 1 , &he); + else + xbt_dynar_insert_at(*equals, cursor, &he); + + } + +} + +static void remove_heap_equality(xbt_dynar_t *equals, int address, void *a){ + + unsigned int cursor = 0; + heap_equality_t current_equality; + int found = 0; + + if(address == 1){ + + int start = 0; + int end = xbt_dynar_length(*equals) - 1; + + + while(start <= end && found == 0){ + cursor = (start + end) / 2; + current_equality = (heap_equality_t)xbt_dynar_get_as(*equals, cursor, heap_equality_t); + if(current_equality->address1 == a) + found = 1; + if(current_equality->address1 < a) + start = cursor + 1; + if(current_equality->address1 > a) + end = cursor - 1; + } + + if(found == 1) + xbt_dynar_remove_at(*equals, cursor, NULL); + + }else{ + + xbt_dynar_foreach(*equals, cursor, current_equality){ + if(current_equality->address2 == a){ + found = 1; + break; + } + } + + if(found == 1) + xbt_dynar_remove_at(*equals, cursor, NULL); + + } + + +} diff --git a/src/xbt/mmalloc/mmalloc.c b/src/xbt/mmalloc/mmalloc.c index f3f4b844f9..be68060138 100644 --- a/src/xbt/mmalloc/mmalloc.c +++ b/src/xbt/mmalloc/mmalloc.c @@ -184,7 +184,6 @@ void *mmalloc(xbt_mheap_t mdp, size_t size) block = BLOCK(result); for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i) { mdp->heapinfo[block].busy_frag.frag_size[i] = 0; - mdp->heapinfo[block].busy_frag.equal_to[i] = -1; next = (struct list *) ((char *) result + (i << log)); next->next = mdp->fraghead[log].next; next->prev = &mdp->fraghead[log]; diff --git a/src/xbt/mmalloc/mmprivate.h b/src/xbt/mmalloc/mmprivate.h index 4f61135c78..53d17c92db 100644 --- a/src/xbt/mmalloc/mmprivate.h +++ b/src/xbt/mmalloc/mmprivate.h @@ -107,6 +107,18 @@ struct mstats size_t bytes_free; /* Byte total of chunks in the free list. */ }; +typedef struct s_heap_area{ + int block; + int fragment; +}s_heap_area_t, *heap_area_t; + +typedef struct s_heap_area_pair{ + int block1; + int fragment1; + int block2; + int fragment2; +}s_heap_area_pair_t, *heap_area_pair_t; + /* Data structure giving per-block information. * * There is one such structure in the mdp->heapinfo array per block used in that heap, @@ -143,14 +155,14 @@ typedef struct { size_t first; /* First free fragment of the block. */ unsigned short frag_size[MAX_FRAGMENT_PER_BLOCK]; void *bt[MAX_FRAGMENT_PER_BLOCK][XBT_BACKTRACE_SIZE]; /* Where it was malloced (or realloced lastly) */ - int equal_to[MAX_FRAGMENT_PER_BLOCK]; + heap_area_t equal_to[MAX_FRAGMENT_PER_BLOCK]; } busy_frag; struct { size_t size; /* Size (in blocks) of a large cluster. */ size_t busy_size; /* Actually used space, in bytes */ void *bt[XBT_BACKTRACE_SIZE]; /* Where it was malloced (or realloced lastly) */ int bt_size; - int equal_to; + heap_area_t equal_to; } busy_block; /* Heap information for a free block (that may be the first of a free cluster). */ struct {