From d048b00742e6a2e9f0fe5d82d8e44747f34a5a8b Mon Sep 17 00:00:00 2001 From: Gabriel Corona Date: Fri, 6 May 2016 10:38:01 +0200 Subject: [PATCH 1/1] [mc] Use std::set for the list-of-heap-location-pairs --- src/mc/compare.cpp | 143 +++++++++++++++++++++------------------------ 1 file changed, 68 insertions(+), 75 deletions(-) diff --git a/src/mc/compare.cpp b/src/mc/compare.cpp index 5d60d7678c..72e930ba0d 100644 --- a/src/mc/compare.cpp +++ b/src/mc/compare.cpp @@ -10,6 +10,7 @@ #include #include +#include #include #include @@ -48,6 +49,10 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_compare, xbt, namespace simgrid { namespace mc { +struct HeapLocation; +typedef std::array HeapLocationPair; +typedef std::set HeapLocationPairs; +struct HeapArea; struct ProcessComparisonState; struct StateComparator; @@ -55,7 +60,7 @@ static int compare_heap_area( StateComparator& state, int process_index, const void *area1, const void* area2, Snapshot* snapshot1, Snapshot* snapshot2, - xbt_dynar_t previous, Type* type, int pointer_level); + HeapLocationPairs* previous, Type* type, int pointer_level); } } @@ -71,11 +76,29 @@ namespace mc { struct HeapLocation { int block = 0; int fragment = 0; + HeapLocation() {} HeapLocation(int block, int fragment = 0) : block(block), fragment(fragment) {} + + bool operator==(HeapLocation const& that) const + { + return block == that.block && fragment == that.fragment; + } + bool operator<(HeapLocation const& that) const + { + return std::make_pair(block, fragment) + < std::make_pair(that.block, that.fragment); + } }; -typedef std::array HeapLocationPair; +static inline +HeapLocationPair makeHeapLocationPair(int block1, int fragment1, int block2, int fragment2) +{ + return simgrid::mc::HeapLocationPair({ + simgrid::mc::HeapLocation(block1, fragment1), + simgrid::mc::HeapLocation(block2, fragment2) + }); +} struct HeapArea : public HeapLocation { bool valid = false; @@ -200,7 +223,7 @@ struct StateComparator { && this->equals_to2_(b2, f2).fragment == f1; } - void match_equals(xbt_dynar_t list); + void match_equals(HeapLocationPairs* list); }; } @@ -208,35 +231,6 @@ struct StateComparator { /************************************************************************************/ -static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, - int block2, int fragment2) -{ - - unsigned int cursor = 0; - simgrid::mc::HeapLocationPair* current_pair; - xbt_dynar_foreach(list, cursor, current_pair) - if ((*current_pair)[0].block == block1 - && (*current_pair)[1].block == block2 - && (*current_pair)[0].fragment == fragment1 - && (*current_pair)[1].fragment == fragment2) - return 0; - return 1; -} - -static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, - int block2, int fragment2) -{ - if (!is_new_heap_area_pair(list, block1, fragment1, block2, fragment2)) - return 0; - simgrid::mc::HeapLocationPair* pair = xbt_new0(simgrid::mc::HeapLocationPair, 1); - (*pair)[0].block = block1; - (*pair)[0].fragment = fragment1; - (*pair)[1].block = block2; - (*pair)[1].fragment = fragment2; - xbt_dynar_push(list, &pair); - return 1; -} - static ssize_t heap_comparison_ignore_size( std::vector* ignore_list, const void *address) @@ -278,22 +272,19 @@ static bool is_block_stack(int block) namespace simgrid { namespace mc { -void StateComparator::match_equals(xbt_dynar_t list) +void StateComparator::match_equals(HeapLocationPairs* list) { - unsigned int cursor = 0; - simgrid::mc::HeapLocationPair* current_pair; - - xbt_dynar_foreach(list, cursor, current_pair) { - if ((*current_pair)[0].fragment != -1) { - this->equals_to1_((*current_pair)[0].block, (*current_pair)[0].fragment) = - simgrid::mc::HeapArea((*current_pair)[1].block, (*current_pair)[1].fragment); - this->equals_to2_((*current_pair)[1].block, (*current_pair)[1].fragment) = - simgrid::mc::HeapArea((*current_pair)[0].block, (*current_pair)[0].fragment); + for (auto const& pair : *list) { + if (pair[0].fragment != -1) { + this->equals_to1_(pair[0].block, pair[0].fragment) = + simgrid::mc::HeapArea(pair[1].block, pair[1].fragment); + this->equals_to2_(pair[1].block, pair[1].fragment) = + simgrid::mc::HeapArea(pair[0].block, pair[0].fragment); } else { - this->equals_to1_((*current_pair)[0].block, 0) = - simgrid::mc::HeapArea((*current_pair)[1].block, (*current_pair)[1].fragment); - this->equals_to2_((*current_pair)[1].block, 0) = - simgrid::mc::HeapArea((*current_pair)[0].block, (*current_pair)[0].fragment); + this->equals_to1_(pair[0].block, 0) = + simgrid::mc::HeapArea(pair[1].block, pair[1].fragment); + this->equals_to2_(pair[1].block, 0) = + simgrid::mc::HeapArea(pair[0].block, pair[0].fragment); } } } @@ -654,7 +645,7 @@ static int compare_heap_area_without_type( const void *real_area1, const void *real_area2, simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot* snapshot2, - xbt_dynar_t previous, int size, + HeapLocationPairs* previous, int size, int check_ignore) { simgrid::mc::Process* process = &mc_model_checker->process(); @@ -738,7 +729,7 @@ static int compare_heap_area_with_type( const void *real_area1, const void *real_area2, simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot* snapshot2, - xbt_dynar_t previous, simgrid::mc::Type* type, + HeapLocationPairs* previous, simgrid::mc::Type* type, int area_size, int check_ignore, int pointer_level) { @@ -1009,7 +1000,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, const void *area1, const void *area2, simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot* snapshot2, - xbt_dynar_t previous, + HeapLocationPairs* previous, simgrid::mc::Type* type, int pointer_level) { simgrid::mc::Process* process = &mc_model_checker->process(); @@ -1038,8 +1029,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, malloc_info heapinfo_temp1, heapinfo_temp2; if (previous == nullptr) { - previous = xbt_dynar_new(sizeof(simgrid::mc::HeapLocationPair*), [](void *d) { - xbt_free((simgrid::mc::HeapLocationPair*) * (void **) d); }); + previous = new HeapLocationPairs(); match_pairs = 1; } @@ -1053,10 +1043,11 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, // If either block is a stack block: if (is_block_stack((int) block1) && is_block_stack((int) block2)) { - add_heap_area_pair(previous, block1, -1, block2, -1); + previous->insert(simgrid::mc::makeHeapLocationPair( + block1, -1, block2, -1)); if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return 0; } @@ -1067,7 +1058,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, || ((char *) area2 < (char *) state.std_heap_copy.heapbase) || (block2 > (ssize_t) state.processStates[1].heapsize) || (block2 < 1)) { if (match_pairs) - xbt_dynar_free(&previous); + delete previous; return 1; } @@ -1109,7 +1100,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, /* Free block */ if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return 0; } @@ -1128,7 +1119,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, && state.blocksEqual(block1, block2)) { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return 0; } @@ -1139,7 +1130,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, && (type->name.empty() || type->name == "struct s_smx_context")) { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return -1; } @@ -1147,20 +1138,21 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, if (heapinfo1->busy_block.size != heapinfo2->busy_block.size) { if (match_pairs) - xbt_dynar_free(&previous); + delete previous; return 1; } if (heapinfo1->busy_block.busy_size != heapinfo2->busy_block.busy_size) { if (match_pairs) - xbt_dynar_free(&previous); + delete previous; return 1; } - if (!add_heap_area_pair(previous, block1, -1, block2, -1)) { + if (!previous->insert(simgrid::mc::makeHeapLocationPair( + block1, -1, block2, -1)).second) { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return 0; } @@ -1177,7 +1169,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, if (size <= 0) { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return 0; } @@ -1211,7 +1203,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, || heapinfo2->busy_frag.frag_size[frag2] == -1) { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return -1; } @@ -1220,7 +1212,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, || type_size != heapinfo2->busy_frag.frag_size[frag2]) { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return -1; } @@ -1232,7 +1224,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, if (offset1==offset2 && state.fragmentsEqual(block1, frag1, block2, frag2)) { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return 0; } @@ -1243,12 +1235,12 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, if (type_size == -1) { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return -1; } else { if (match_pairs) - xbt_dynar_free(&previous); + delete previous; return 1; } } @@ -1300,7 +1292,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, } else { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return -1; } @@ -1320,7 +1312,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, } else { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return -1; } @@ -1332,10 +1324,11 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, } if (offset1 == 0 && offset2 == 0 - && !add_heap_area_pair(previous, block1, frag1, block2, frag2)) { + && !previous->insert(simgrid::mc::makeHeapLocationPair( + block1, frag1, block2, frag2)).second) { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return 0; } @@ -1343,7 +1336,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, if (size <= 0) { if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return 0; } @@ -1355,7 +1348,7 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, } else { if (match_pairs) - xbt_dynar_free(&previous); + delete previous; return 1; } @@ -1373,13 +1366,13 @@ int compare_heap_area(simgrid::mc::StateComparator& state, int process_index, if (res_compare == 1) { if (match_pairs) - xbt_dynar_free(&previous); + delete previous; return res_compare; } if (match_pairs) { state.match_equals(previous); - xbt_dynar_free(&previous); + delete previous; } return 0; -- 2.20.1