diff options
-rw-r--r-- | dwarflint/Makefile.am | 13 | ||||
-rw-r--r-- | dwarflint/check_debug_aranges.cc | 18 | ||||
-rw-r--r-- | dwarflint/check_debug_info.cc | 20 | ||||
-rw-r--r-- | dwarflint/check_debug_loc_range.cc | 98 | ||||
-rw-r--r-- | dwarflint/check_debug_loc_range.hh | 8 | ||||
-rw-r--r-- | dwarflint/check_range_out_of_scope.cc | 25 | ||||
-rw-r--r-- | dwarflint/coverage.cc | 320 | ||||
-rw-r--r-- | dwarflint/coverage.hh | 99 | ||||
-rw-r--r-- | dwarflint/cu_coverage.cc | 11 | ||||
-rw-r--r-- | dwarflint/cu_coverage.hh | 1 | ||||
-rw-r--r-- | dwarflint/test-coverage.cc | 151 |
11 files changed, 416 insertions, 348 deletions
diff --git a/dwarflint/Makefile.am b/dwarflint/Makefile.am index f4160884..6d73fae6 100644 --- a/dwarflint/Makefile.am +++ b/dwarflint/Makefile.am @@ -35,7 +35,7 @@ AM_LDFLAGS = -Wl,-rpath-link,../libelf:../libdw no_mudflap.os = -fmudflap -bin_PROGRAMS = dwarflint +bin_PROGRAMS = dwarflint test-coverage dwarflint_SOURCES = \ addr-record.cc addr-record.hh \ @@ -85,7 +85,10 @@ dwarflint_SOURCES = \ \ ../src/dwarfstrings.c -TESTS = tests/run-debug_abbrev-duplicate-attribute.sh \ +test_coverage_SOURCES = test-coverage.cc coverage.cc pri.cc \ + ../src/dwarfstrings.c + +EXTRA_TESTS = tests/run-debug_abbrev-duplicate-attribute.sh \ tests/run-check_duplicate_DW_tag_variable.sh \ tests/run-location-leaks.sh \ tests/run-nodebug.sh \ @@ -93,7 +96,10 @@ TESTS = tests/run-debug_abbrev-duplicate-attribute.sh \ tests/run-check_debug_info_refs.sh \ tests/run-aranges_terminate_early.sh -EXTRA_DIST = $(TESTS) \ +TESTS = $(EXTRA_TESTS) \ + test-coverage + +EXTRA_DIST = $(EXTRA_TESTS) \ tests/debug_abbrev-duplicate-attribute.bz2 \ tests/crc7.ko.debug.bz2 \ tests/location-leaks.bz2 \ @@ -134,6 +140,7 @@ libeu = ../lib/libeu.a libdwpp = ../libdw/libdwpp.a $(libdw) dwarflint_LDADD = $(libebl) $(libelf) $(libdwpp) $(libeu) $(libmudflap) -ldl +test_coverage_LDADD = $(libebl) $(libelf) $(libdwpp) $(libeu) $(libmudflap) -ldl installcheck-binPROGRAMS: $(bin_PROGRAMS) bad=0; pid=$$$$; list="$(bin_PROGRAMS)"; for p in $$list; do \ diff --git a/dwarflint/check_debug_aranges.cc b/dwarflint/check_debug_aranges.cc index 87f96832..a2fcd450 100644 --- a/dwarflint/check_debug_aranges.cc +++ b/dwarflint/check_debug_aranges.cc @@ -147,12 +147,9 @@ compare_coverage_1 (struct elf_file *file, enum section_id id, char const *what, bool reverse) { - struct coverage *cov = coverage_clone (coverage); - coverage_remove_all (cov, other); + struct coverage cov = *coverage - *other; hole_user info (file, id, what, reverse); - coverage_find_ranges (cov, hole, &info); - coverage_free (cov); - free (cov); + cov.find_ranges (hole, &info); } static void @@ -169,7 +166,7 @@ aranges_coverage_add (struct coverage *aranges_coverage, uint64_t begin, uint64_t length, struct where *where) { - if (coverage_is_overlap (aranges_coverage, begin, length)) + if (aranges_coverage->is_overlap (begin, length)) { char buf[128]; /* Not a show stopper, this shouldn't derail high-level. */ @@ -178,7 +175,7 @@ aranges_coverage_add (struct coverage *aranges_coverage, range_fmt (buf, sizeof buf, begin, begin + length)); } - coverage_add (aranges_coverage, begin, length); + aranges_coverage->add (begin, length); } /* COVERAGE is portion of address space covered by CUs (either via @@ -196,9 +193,7 @@ check_aranges_structural (struct elf_file *file, bool retval = true; struct coverage *aranges_coverage - = coverage != NULL - ? (struct coverage *)calloc (1, sizeof (struct coverage)) - : NULL; + = coverage != NULL ? new struct coverage () : NULL; while (!read_ctx_eof (&ctx)) { @@ -418,8 +413,7 @@ check_aranges_structural (struct elf_file *file, { compare_coverage (file, coverage, aranges_coverage, sec_aranges, "aranges"); - coverage_free (aranges_coverage); - free (aranges_coverage); + delete aranges_coverage; } return retval; diff --git a/dwarflint/check_debug_info.cc b/dwarflint/check_debug_info.cc index b4ea0208..afb8bbf8 100644 --- a/dwarflint/check_debug_info.cc +++ b/dwarflint/check_debug_info.cc @@ -455,7 +455,7 @@ namespace << " is not zero-terminated." << std::endl; if (ctx->strings_coverage != NULL) - coverage_add (ctx->strings_coverage, addr, strp - startp + 1); + ctx->strings_coverage->add (addr, strp - startp + 1); } } @@ -861,7 +861,7 @@ namespace cu->low_pc = low_pc; if (high_pc != (uint64_t)-1) - coverage_add (pc_coverage, low_pc, high_pc - low_pc); + pc_coverage->add (low_pc, high_pc - low_pc); } if (high_pc != (uint64_t)-1 && low_pc != (uint64_t)-1) @@ -971,12 +971,9 @@ check_debug_info::check_info_structural () bool success = true; - struct coverage strings_coverage_mem, *strings_coverage = NULL; - if (strings != NULL && check_category (mc_strings)) - { - WIPE (strings_coverage_mem); - strings_coverage = &strings_coverage_mem; - } + coverage *strings_coverage = + (strings != NULL && check_category (mc_strings)) + ? new coverage () : NULL; struct relocation_data *reloc = sec.rel.size > 0 ? &sec.rel : NULL; if (reloc != NULL) @@ -1088,10 +1085,9 @@ check_debug_info::check_info_structural () if (success) { struct hole_info info = {sec_str, mc_strings, strings->d_buf, 0}; - coverage_find_holes (strings_coverage, 0, strings->d_size, - found_hole, &info); + strings_coverage->find_holes (0, strings->d_size, found_hole, &info); } - coverage_free (strings_coverage); + delete strings_coverage; } } @@ -1102,7 +1098,6 @@ check_debug_info::check_debug_info (checkstack &stack, dwarflint &lint) , _m_abbrevs (lint.check (stack, _m_abbrevs)) , _m_cu_headers (lint.check (stack, _m_cu_headers)) { - memset (&_m_cov, 0, sizeof (_m_cov)); check_info_structural (); // re-link CUs so that they form a chain again. This is to @@ -1133,7 +1128,6 @@ check_debug_info::~check_debug_info () ref_record_free (&it->loc_refs); ref_record_free (&it->decl_file_refs); } - coverage_free (&_m_cov); } cu * diff --git a/dwarflint/check_debug_loc_range.cc b/dwarflint/check_debug_loc_range.cc index 24ddc8c9..f3b5f5a4 100644 --- a/dwarflint/check_debug_loc_range.cc +++ b/dwarflint/check_debug_loc_range.cc @@ -96,19 +96,6 @@ check_debug_loc::descriptor () namespace { - void - section_coverage_init (struct section_coverage *sco, - struct sec *sec, bool warn) - { - assert (sco != NULL); - assert (sec != NULL); - - sco->sec = sec; - WIPE (sco->cov); - sco->hit = false; - sco->warn = warn; - } - bool coverage_map_init (struct coverage_map *coverage_map, struct elf_file *elf, @@ -119,7 +106,6 @@ namespace assert (coverage_map != NULL); assert (elf != NULL); - WIPE (*coverage_map); coverage_map->elf = elf; coverage_map->allow_overlap = allow_overlap; @@ -130,11 +116,8 @@ namespace bool normal = (sec->shdr.sh_flags & mask) == mask; bool warn = (sec->shdr.sh_flags & warn_mask) == warn_mask; if (normal || warn) - { - REALLOC (coverage_map, scos); - section_coverage_init - (coverage_map->scos + coverage_map->size++, sec, !normal); - } + coverage_map->scos + .push_back (section_coverage (sec, !normal)); } return true; @@ -143,13 +126,13 @@ namespace struct coverage_map * coverage_map_alloc_XA (struct elf_file *elf, bool allow_overlap) { - coverage_map *ret = (coverage_map *)xmalloc (sizeof (*ret)); + coverage_map *ret = new coverage_map (); if (!coverage_map_init (ret, elf, SHF_EXECINSTR | SHF_ALLOC, SHF_ALLOC, allow_overlap)) { - free (ret); + delete ret; return NULL; } return ret; @@ -258,10 +241,9 @@ namespace { for (size_t i = 0; i < coverage_map->size; ++i) { - section_coverage *sco = coverage_map->scos + i; + section_coverage *sco = &coverage_map->scos[i]; wrap_cb_arg arg = {cb, sco, user}; - if (!coverage_find_holes (&sco->cov, 0, sco->sec->shdr.sh_size, - unwrap_cb, &arg)) + if (!sco->cov.find_holes (0, sco->sec->shdr.sh_size, unwrap_cb, &arg)) return false; } @@ -284,12 +266,11 @@ namespace /* This is for analyzing how much of the current range falls into sections in coverage map. Whatever is left uncovered doesn't fall anywhere and is reported. */ - struct coverage range_cov; - WIPE (range_cov); + coverage range_cov; for (size_t i = 0; i < coverage_map->size; ++i) { - struct section_coverage *sco = coverage_map->scos + i; + struct section_coverage *sco = &coverage_map->scos[i]; GElf_Shdr *shdr = &sco->sec->shdr; struct coverage *cov = &sco->cov; @@ -326,7 +307,7 @@ namespace uint64_t r_cov_end = cov_end + r_delta; if (!overlap && !coverage_map->allow_overlap - && coverage_is_overlap (cov, cov_begin, cov_end - cov_begin)) + && cov->is_overlap (cov_begin, cov_end - cov_begin)) { /* Not a show stopper, this shouldn't derail high-level. */ wr_message (cat | mc_impact_2 | mc_error, where, @@ -341,11 +322,11 @@ namespace range_fmt (buf, sizeof buf, address, end), sco->sec->name); /* Section coverage... */ - coverage_add (cov, cov_begin, cov_end - cov_begin); + cov->add (cov_begin, cov_end - cov_begin); sco->hit = true; /* And range coverage... */ - coverage_add (&range_cov, r_cov_begin, r_cov_end - r_cov_begin); + range_cov.add (r_cov_begin, r_cov_end - r_cov_begin); } if (!found) @@ -356,27 +337,7 @@ namespace else if (length > 0) { hole_env env = {where, address, end}; - coverage_find_holes (&range_cov, 0, length, range_hole, &env); - } - - coverage_free (&range_cov); - } - - void - coverage_map_free (struct coverage_map *coverage_map) - { - for (size_t i = 0; i < coverage_map->size; ++i) - coverage_free (&coverage_map->scos[i].cov); - free (coverage_map->scos); - } - - void - coverage_map_free_XA (coverage_map *coverage_map) - { - if (coverage_map != NULL) - { - coverage_map_free (coverage_map); - free (coverage_map); + range_cov.find_holes (0, length, range_hole, &env); } } @@ -413,7 +374,7 @@ namespace bool retval = true; bool contains_locations = sec->id == sec_loc; - if (coverage_is_covered (coverage, addr, 1)) + if (coverage->is_covered (addr, 1)) { wr_error (wh, ": reference to %#" PRIx64 " points into another location or range list.\n", addr); @@ -443,7 +404,7 @@ namespace GElf_Sym begin_symbol_mem, *begin_symbol = &begin_symbol_mem; bool begin_relocated = false; if (!overlap - && coverage_is_overlap (coverage, begin_off, cu->head->address_size)) + && coverage->is_overlap (begin_off, cu->head->address_size)) HAVE_OVERLAP; if (!read_ctx_read_offset (&ctx, cu->head->address_size == 8, &begin_addr)) @@ -467,7 +428,7 @@ namespace GElf_Sym end_symbol_mem, *end_symbol = &end_symbol_mem; bool end_relocated = false; if (!overlap - && coverage_is_overlap (coverage, end_off, cu->head->address_size)) + && coverage->is_overlap (end_off, cu->head->address_size)) HAVE_OVERLAP; if (!read_ctx_read_offset (&ctx, cu->head->address_size == 8, @@ -530,7 +491,7 @@ namespace if (coverage_map != NULL) coverage_map_add (coverage_map, address, length, &where, cat); if (pc_coverage != NULL) - coverage_add (pc_coverage, address, length); + pc_coverage->add (address, length); } if (contains_locations) @@ -538,8 +499,7 @@ namespace /* location expression length */ uint16_t len; if (!overlap - && coverage_is_overlap (coverage, - read_ctx_get_offset (&ctx), 2)) + && coverage->is_overlap (read_ctx_get_offset (&ctx), 2)) HAVE_OVERLAP; if (!read_ctx_read_2ubyte (&ctx, &len)) @@ -557,8 +517,7 @@ namespace return false; uint64_t expr_end = read_ctx_get_offset (&ctx); if (!overlap - && coverage_is_overlap (coverage, - expr_start, expr_end - expr_start)) + && coverage->is_overlap (expr_start, expr_end - expr_start)) HAVE_OVERLAP; if (!read_ctx_skip (&ctx, len)) @@ -580,7 +539,7 @@ namespace } #undef HAVE_OVERLAP - coverage_add (coverage, where.addr1, read_ctx_get_offset (&ctx) - where.addr1); + coverage->add (where.addr1, read_ctx_get_offset (&ctx) - where.addr1); if (done) break; } @@ -626,7 +585,6 @@ namespace /* Overlap discovery. */ struct coverage coverage; - WIPE (coverage); enum message_category cat = sec->id == sec_loc ? mc_loc : mc_ranges; @@ -691,7 +649,7 @@ namespace struct hole_info hi = { sec->id, cat, ctx.data->d_buf, cu_chain->head->address_size }; - coverage_find_holes (&coverage, 0, ctx.data->d_size, found_hole, &hi); + coverage.find_holes (0, ctx.data->d_size, found_hole, &hi); if (coverage_map) { @@ -703,13 +661,20 @@ namespace } } - coverage_free (&coverage); - coverage_map_free_XA (coverage_map); + delete coverage_map; return retval; } } +section_coverage::section_coverage (struct sec *a_sec, bool a_warn) + : sec (a_sec) + , hit (false) + , warn (a_warn) +{ + assert (a_sec); +} + check_debug_ranges::check_debug_ranges (checkstack &stack, dwarflint &lint) : _m_sec_ranges (lint.check (stack, _m_sec_ranges)) , _m_info (lint.check (stack, _m_info)) @@ -722,11 +687,6 @@ check_debug_ranges::check_debug_ranges (checkstack &stack, dwarflint &lint) throw check_base::failed (); } -check_debug_ranges::~check_debug_ranges () -{ - coverage_free (&_m_cov); -} - check_debug_loc::check_debug_loc (checkstack &stack, dwarflint &lint) : _m_sec_loc (lint.check (stack, _m_sec_loc)) , _m_info (lint.check (stack, _m_info)) diff --git a/dwarflint/check_debug_loc_range.hh b/dwarflint/check_debug_loc_range.hh index 21319692..cec5911c 100644 --- a/dwarflint/check_debug_loc_range.hh +++ b/dwarflint/check_debug_loc_range.hh @@ -35,14 +35,15 @@ struct section_coverage struct sec *sec; struct coverage cov; bool hit; /* true if COV is not pristine. */ - bool warn; /* dwarflint should emit a warning if a coverage - appears in this section */ + bool warn; /* dwarflint should emit a warning if a coverage appears + in this section */ + section_coverage (struct sec *a_sec, bool a_warn); }; struct coverage_map { struct elf_file *elf; - struct section_coverage *scos; + std::vector<section_coverage> scos; size_t size; size_t alloc; bool allow_overlap; @@ -60,7 +61,6 @@ public: coverage const &cov () const { return _m_cov; } check_debug_ranges (checkstack &stack, dwarflint &lint); - ~check_debug_ranges (); }; class check_debug_loc diff --git a/dwarflint/check_range_out_of_scope.cc b/dwarflint/check_range_out_of_scope.cc index 7a175598..64fc3ce6 100644 --- a/dwarflint/check_range_out_of_scope.cc +++ b/dwarflint/check_range_out_of_scope.cc @@ -163,24 +163,18 @@ check_range_out_of_scope::recursively_validate case DW_TAG_catch_block: { coverage cov1; - WIPE (cov1); - for (ranges_t::const_iterator it = my_ranges.begin (); it != my_ranges.end (); ++it) - coverage_add (&cov1, (*it).first, (*it).second - (*it).first); + cov1.add ((*it).first, (*it).second - (*it).first); coverage cov2; - WIPE (cov2); for (ranges_t::const_iterator it = ranges.begin (); it != ranges.end (); ++it) - coverage_add (&cov2, (*it).first, (*it).second - (*it).first); + cov2.add ((*it).first, (*it).second - (*it).first); - coverage result; - WIPE (result); - coverage_add_all (&result, &cov1); - coverage_remove_all (&result, &cov2); + coverage result = cov1 - cov2; - if (result.size > 0) + if (!result.empty ()) { wr_error (wh) << "PC range " << cov::format_ranges (cov1) @@ -191,10 +185,6 @@ check_range_out_of_scope::recursively_validate << "in this context: " << cov::format_ranges (cov2) << std::endl; } - - coverage_free (&result); - coverage_free (&cov2); - coverage_free (&cov1); } } } @@ -203,11 +193,10 @@ check_range_out_of_scope::recursively_validate ranges_t const &use_ranges = my_ranges.size () > 0 ? my_ranges : ranges; coverage cov; - WIPE (cov); for (ranges_t::const_iterator it = use_ranges.begin (); it != use_ranges.end (); ++it) - coverage_add (&cov, (*it).first, (*it).second - (*it).first); + cov.add ((*it).first, (*it).second - (*it).first); // Now finally look for location attributes and check that // _their_ PCs form a subset of ranges of this DIE. @@ -231,7 +220,7 @@ check_range_out_of_scope::recursively_validate ::Dwarf_Addr end = (*lt).first.second; //1st past end ::Dwarf_Addr length = end - start; if (length > 0 // skip empty ranges - && !coverage_is_covered (&cov, start, length)) + && !cov.is_covered (start, length)) { runoff = true; wr_error (wh) @@ -248,8 +237,6 @@ check_range_out_of_scope::recursively_validate } } - coverage_free (&cov); - // Check children recursively. for (dwarf::debug_info_entry::children_type::const_iterator jt = die.children ().begin (); diff --git a/dwarflint/coverage.cc b/dwarflint/coverage.cc index fde4351b..bdd1e2c8 100644 --- a/dwarflint/coverage.cc +++ b/dwarflint/coverage.cc @@ -37,215 +37,186 @@ #include <string.h> #include <inttypes.h> -namespace +coverage::const_iterator +coverage::find (uint64_t start) const { - template <class X> - decltype (((X *)0)->ranges) - coverage_find (X *cov, uint64_t start) - { - assert (cov->size > 0); + assert (!empty ()); - size_t a = 0; - size_t b = cov->size; + size_t a = 0; + size_t b = size (); - while (a < b) - { - size_t i = (a + b) / 2; - cov_range const *r = cov->ranges + i; + while (a < b) + { + size_t i = (a + b) / 2; + cov_range const &r = at (i); - if (r->start > start) - b = i; - else if (r->start < start) - a = i + 1; - else - return cov->ranges + i; - } + if (r.start > start) + b = i; + else if (r.start < start) + a = i + 1; + else + return begin () + i; + } - return cov->ranges + a; - } + return begin () + a; } -void -coverage_add (struct coverage *cov, uint64_t start, uint64_t length) +coverage::iterator +coverage::find (uint64_t start) { - if (length == 0) - return; + const_iterator it = const_cast<coverage const *> (this)->find (start); + return begin () + (it - begin ()); +} - struct cov_range nr = (struct cov_range){start, length}; - if (cov->size == 0) +void +coverage::add (uint64_t start, uint64_t length) +{ + cov_range nr = (struct cov_range){start, length}; + if (empty ()) { - REALLOC (cov, ranges); - cov->ranges[cov->size++] = nr; + push_back (nr); return; } - struct cov_range *r = coverage_find (cov, start); + iterator r_i = find (start); - struct cov_range *insert = &nr; - struct cov_range *coalesce = &nr; - struct cov_range *end = cov->ranges + cov->size; + cov_range *to_insert = &nr; + cov_range *coalesce = &nr; // Coalesce with previous range? - struct cov_range *p = r - 1; - if (r > cov->ranges && coalesce->start <= p->start + p->length) + iterator p_i = r_i - 1; + if (r_i > begin () && coalesce->start <= p_i->start + p_i->length) { uint64_t coalesce_end = coalesce->start + coalesce->length; - if (coalesce_end > p->start + p->length) + if (coalesce_end > p_i->start + p_i->length) { - p->length = coalesce_end - p->start; - coalesce = p; + p_i->length = coalesce_end - p_i->start; + coalesce = &*p_i; } else coalesce = NULL; - insert = NULL; + to_insert = NULL; } // Coalesce with one or more following ranges? - if (coalesce != NULL && coalesce != end) + if (coalesce != NULL && r_i != end ()) { - p = r; - while (p != end && coalesce->start + coalesce->length >= p->start) + p_i = r_i; + while (p_i != end () + && coalesce->start + coalesce->length >= p_i->start) { - uint64_t p_end = p->start + p->length; + uint64_t p_end = p_i->start + p_i->length; if (p_end > coalesce->start + coalesce->length) coalesce->length = p_end - coalesce->start; - if (insert != NULL) + if (to_insert != NULL) { - *p = *insert; - insert = NULL; - coalesce = p; - assert (p == r); - ++r; // when doing memory moves, don't overwrite this range + *p_i = *to_insert; + to_insert = NULL; + coalesce = &*p_i; + assert (p_i == r_i); + ++r_i; // keep this element } - ++p; - } - if (p > r) - { - size_t rem = cov->size - (p - cov->ranges); - memmove (r, p, sizeof (*cov->ranges) * rem); - cov->size -= p - r; + ++p_i; } + if (p_i > r_i) + erase (r_i, p_i); } - if (insert != NULL) + if (to_insert != NULL) { - size_t rem = end - r; - size_t idx = r - cov->ranges; - REALLOC (cov, ranges); - r = cov->ranges + idx; - - cov->size++; - if (rem > 0) - memmove (r + 1, r, sizeof (*cov->ranges) * rem); - *r = nr; + size_t idx = r_i - begin (); + insert (begin () + idx, *to_insert); } } bool -coverage_remove (struct coverage *cov, uint64_t begin, uint64_t length) +coverage::remove (uint64_t start, + uint64_t length) { - uint64_t end = begin + length; - if (cov->size == 0 || begin == end) + uint64_t a_end = start + length; + if (empty () || start == a_end) return false; - struct cov_range *r = coverage_find (cov, begin); - struct cov_range *erase_begin = NULL, *erase_end = r; // end exclusive + iterator r_i = find (start); + iterator erase_begin_i = end (); + iterator erase_end_i = r_i; // end exclusive bool overlap = false; // Cut from previous range? - struct cov_range *p = r - 1; - if (r > cov->ranges && begin < p->start + p->length) + iterator p_i = r_i - 1; + if (r_i > begin () && start < p_i->start + p_i->length) { - uint64_t r_end = p->start + p->length; + uint64_t r_end = p_i->start + p_i->length; // Do we cut the beginning of the range? - if (begin == p->start) - p->length = end >= r_end ? 0 : r_end - end; + if (start == p_i->start) + p_i->length = a_end >= r_end ? 0 : r_end - a_end; else { - p->length = begin - p->start; + p_i->length = start - p_i->start; // Do we shoot a hole in that range? - if (end < r_end) + if (a_end < r_end) { - coverage_add (cov, end, r_end - end); + add (a_end, r_end - a_end); return true; } } overlap = true; - if (p->length == 0) - erase_begin = p; + if (p_i->length == 0) + erase_begin_i = p_i; } - if (erase_begin == NULL) - erase_begin = r; + if (erase_begin_i == end ()) + erase_begin_i = r_i; // Cut from next range? - while (r < cov->ranges + cov->size - && r->start < end) + while (r_i < end () && r_i->start < a_end) { overlap = true; - if (end >= r->start + r->length) + if (a_end >= r_i->start + r_i->length) { - ++erase_end; - ++r; + ++erase_end_i; + ++r_i; } else { - uint64_t end0 = r->start + r->length; - r->length = end0 - end; - r->start = end; - assert (end0 == r->start + r->length); + uint64_t end0 = r_i->start + r_i->length; + r_i->length = end0 - a_end; + r_i->start = a_end; + assert (end0 == r_i->start + r_i->length); } } // Did we cut out anything completely? - if (erase_end > erase_begin) - { - struct cov_range *cov_end = cov->ranges + cov->size; - size_t rem = cov_end - erase_end; - if (rem > 0) - memmove (erase_begin, erase_end, sizeof (*cov->ranges) * rem); - cov->size -= erase_end - erase_begin; - } + if (erase_end_i > erase_begin_i) + erase (erase_begin_i, erase_end_i); return overlap; } bool -coverage_is_covered (struct coverage const *cov, - uint64_t start, uint64_t length) +coverage::is_covered (uint64_t start, uint64_t length) const { assert (length > 0); - if (cov->size == 0) + if (empty ()) return false; - struct cov_range const *r = coverage_find (cov, start); - uint64_t end = start + length; - if (r < cov->ranges + cov->size) - if (start >= r->start) - return end <= r->start + r->length; + const_iterator r_i = find (start); + uint64_t a_end = start + length; + if (r_i < end ()) + if (start >= r_i->start) + return a_end <= r_i->start + r_i->length; - if (r > cov->ranges) + if (r_i > begin ()) { - --r; - return end <= r->start + r->length; + --r_i; + return a_end <= r_i->start + r_i->length; } return false; } -namespace -{ - bool overlaps (uint64_t start, uint64_t end, - struct cov_range const *r) - { - return (start >= r->start && start < r->start + r->length) - || (end > r->start && end <= r->start + r->length) - || (start < r->start && end > r->start + r->length); - } -} - char * range_fmt (char *buf, size_t buf_size, uint64_t start, uint64_t end) { @@ -256,104 +227,111 @@ range_fmt (char *buf, size_t buf_size, uint64_t start, uint64_t end) return buf; } +namespace +{ + bool overlaps (uint64_t start, uint64_t end, cov_range const &r) + { + return (start >= r.start && start < r.start + r.length) + || (end > r.start && end <= r.start + r.length) + || (start < r.start && end > r.start + r.length); + } +} + bool -coverage_is_overlap (struct coverage const *cov, - uint64_t start, uint64_t length) +coverage::is_overlap (uint64_t start, uint64_t length) const { - if (length == 0 || cov->size == 0) + if (empty () || length == 0) return false; - uint64_t end = start + length; - - struct cov_range const *r = coverage_find (cov, start); + uint64_t a_end = start + length; + const_iterator r_i = find (start); - if (r < cov->ranges + cov->size && overlaps (start, end, r)) + if (r_i < end () && overlaps (start, a_end, *r_i)) return true; - if (r > cov->ranges) - return overlaps (start, end, r - 1); + if (r_i > begin ()) + return overlaps (start, a_end, *--r_i); return false; } bool -coverage_find_holes (struct coverage const *cov, - uint64_t start, uint64_t length, - bool (*hole)(uint64_t start, uint64_t length, void *data), - void *data) +coverage::find_holes (uint64_t start, uint64_t length, + bool (*hole)(uint64_t start, uint64_t length, + void *user_data), + void *user_data) const { if (length == 0) return true; - if (cov->size == 0) - return hole (start, length, data); + if (empty ()) + return hole (start, length, user_data); - if (start < cov->ranges[0].start) - if (!hole (start, cov->ranges[0].start - start, data)) + if (start < front ().start) + if (!hole (start, front ().start - start, user_data)) return false; - for (size_t i = 0; i < cov->size - 1; ++i) + for (size_t i = 0; i < size () - 1; ++i) { - uint64_t end_i = cov->ranges[i].end (); - if (!hole (end_i, cov->ranges[i+1].start - end_i, data)) + uint64_t end_i = at (i).end (); + if (!hole (end_i, at (i+1).start - end_i, user_data)) return false; } - if (start + length > cov->back ().end ()) + if (start + length > back ().end ()) { - uint64_t end_last = cov->back ().end (); - return hole (end_last, start + length - end_last, data); + uint64_t end_last = back ().end (); + return hole (end_last, start + length - end_last, user_data); } return true; } bool -coverage_find_ranges (struct coverage const *cov, - bool (*cb)(uint64_t start, uint64_t length, void *data), - void *data) +coverage::find_ranges (bool (*cb)(uint64_t start, uint64_t length, void *data), + void *user_data) const { - for (size_t i = 0; i < cov->size; ++i) - if (!cb (cov->ranges[i].start, cov->ranges[i].length, data)) + for (const_iterator it = begin (); it != end (); ++it) + if (!cb (it->start, it->length, user_data)) return false; return true; } void -coverage_free (struct coverage *cov) +coverage::add_all (coverage const &other) { - free (cov->ranges); + for (size_t i = 0; i < other.size (); ++i) + add (other[i].start, other[i].length); } -coverage * -coverage_clone (struct coverage const *cov) +bool +coverage::remove_all (coverage const &other) { - coverage *ret = (coverage *)xmalloc (sizeof (*ret)); - WIPE (*ret); - coverage_add_all (ret, cov); + bool ret = false; + for (size_t i = 0; i < other.size (); ++i) + if (remove (other[i].start, other[i].length)) + ret = true; return ret; } -void -coverage_add_all (struct coverage *__restrict__ cov, - struct coverage const *__restrict__ other) +coverage +coverage::operator+ (coverage const &rhs) const { - for (size_t i = 0; i < other->size; ++i) - coverage_add (cov, other->ranges[i].start, other->ranges[i].length); + coverage ret = *this; + ret.add_all (rhs); + return ret; } -bool -coverage_remove_all (struct coverage *__restrict__ cov, - struct coverage const *__restrict__ other) +coverage +coverage::operator- (coverage const &rhs) const { - bool ret = false; - for (size_t i = 0; i < other->size; ++i) - if (coverage_remove (cov, other->ranges[i].start, other->ranges[i].length)) - ret = true; + coverage ret = *this; + ret.remove_all (rhs); return ret; } + bool cov::_format_base::fmt (uint64_t start, uint64_t length) { @@ -380,7 +358,7 @@ cov::format_ranges::format_ranges (coverage const &cov, std::string const &delim) : _format_base (delim) { - coverage_find_ranges (&cov, &wrap_fmt, this); + cov.find_ranges (&wrap_fmt, this); } cov::format_holes::format_holes (coverage const &cov, @@ -388,5 +366,5 @@ cov::format_holes::format_holes (coverage const &cov, std::string const &delim) : _format_base (delim) { - coverage_find_holes (&cov, start, length, &wrap_fmt, this); + cov.find_holes (start, length, &wrap_fmt, this); } diff --git a/dwarflint/coverage.hh b/dwarflint/coverage.hh index e13344be..381d5216 100644 --- a/dwarflint/coverage.hh +++ b/dwarflint/coverage.hh @@ -29,6 +29,7 @@ #include <string> #include <sstream> +#include <vector> /* Functions and data structures for handling of address range coverage. We use that to find holes of unused bytes in DWARF @@ -39,63 +40,67 @@ struct cov_range uint64_t start; uint64_t length; -#ifdef __cplusplus uint64_t end () const { return start + length; } -#endif + + bool operator== (cov_range const &rhs) const + { + return start == rhs.start + && length == rhs.length; + } }; struct coverage + : private std::vector<cov_range> { - struct cov_range *ranges; - size_t size; - size_t alloc; - -#ifdef __cplusplus - cov_range &back () { return ranges[size - 1]; } - cov_range const &back () const { return ranges[size - 1]; } -#endif + iterator find (uint64_t start); + const_iterator find (uint64_t start) const; + +public: + using std::vector<cov_range>::front; + using std::vector<cov_range>::back; + using std::vector<cov_range>::size; + using std::vector<cov_range>::empty; + + void add (uint64_t start, uint64_t length); + + /// Returns true if something was actually removed, false if whole + /// range falls into hole in coverage. + bool remove (uint64_t start, uint64_t length); + + void add_all (coverage const &other); + + // Returns true if something was actually removed, false if whole + // range falls into hole in coverage. + bool remove_all (coverage const &other); + + bool find_ranges (bool (*cb)(uint64_t start, uint64_t length, void *data), + void *data) const; + + /// Returns true if whole range ADDRESS/LENGTH is covered by COV. + /// If LENGTH is zero, it's checked that the address is inside or at + /// the edge of covered range, or that there is a zero-length range + /// at that address. + bool is_covered (uint64_t start, uint64_t length) const; + + /// Returns true if at least some of the range ADDRESS/LENGTH is + /// covered by COV. Zero-LENGTH range never overlaps. */ + bool is_overlap (uint64_t start, uint64_t length) const; + + bool find_holes (uint64_t start, uint64_t length, + bool (*cb)(uint64_t start, uint64_t length, void *data), + void *data) const; + + coverage operator+ (coverage const &rhs) const; + coverage operator- (coverage const &rhs) const; + bool operator== (coverage const &rhs) const + { + return static_cast<std::vector<cov_range> > (rhs) == *this; + } }; char *range_fmt (char *buf, size_t buf_size, uint64_t start, uint64_t end); -struct coverage *coverage_clone (struct coverage const *cov) - __attribute__ ((malloc)); -void coverage_free (struct coverage *cov); - -void coverage_add (struct coverage *cov, uint64_t start, uint64_t length); -void coverage_add_all (struct coverage *__restrict__ cov, - struct coverage const *__restrict__ other); - -/* Returns true if something was actually removed, false if whole - range falls into hole in coverage. */ -bool coverage_remove (struct coverage *cov, uint64_t start, uint64_t length); - -/* Returns true if something was actually removed, false if whole - range falls into hole in coverage. */ -bool coverage_remove_all (struct coverage *__restrict__ cov, - struct coverage const *__restrict__ other); - -/* Returns true if whole range ADDRESS/LENGTH is covered by COV. - LENGTH may not be zero. */ -bool coverage_is_covered (struct coverage const *cov, - uint64_t start, uint64_t length); - -/* Returns true if at least some of the range ADDRESS/LENGTH is - covered by COV. Zero-LENGTH range never overlaps. */ -bool coverage_is_overlap (struct coverage const *cov, - uint64_t start, uint64_t length); - -bool coverage_find_holes (struct coverage const *cov, - uint64_t start, uint64_t length, - bool (*cb)(uint64_t start, uint64_t length, - void *data), - void *data); -bool coverage_find_ranges (struct coverage const *cov, - bool (*cb)(uint64_t start, uint64_t length, - void *data), - void *data); - namespace cov { class _format_base diff --git a/dwarflint/cu_coverage.cc b/dwarflint/cu_coverage.cc index 9098806c..f836040b 100644 --- a/dwarflint/cu_coverage.cc +++ b/dwarflint/cu_coverage.cc @@ -41,14 +41,7 @@ cu_coverage::descriptor () cu_coverage::cu_coverage (checkstack &stack, dwarflint &lint) : _m_info (lint.check (stack, _m_info)) , _m_ranges (lint.check_if (_m_info->need_ranges (), stack, _m_ranges)) + , cov (_m_info->cov () + + (_m_ranges != NULL ? _m_ranges->cov () : coverage ())) { - std::memset (&cov, 0, sizeof (cov)); - coverage_add_all (&cov, &_m_info->cov ()); - if (_m_ranges) - coverage_add_all (&cov, &_m_ranges->cov ()); -} - -cu_coverage::~cu_coverage () -{ - coverage_free (&cov); } diff --git a/dwarflint/cu_coverage.hh b/dwarflint/cu_coverage.hh index 273eb336..da1d14b2 100644 --- a/dwarflint/cu_coverage.hh +++ b/dwarflint/cu_coverage.hh @@ -44,7 +44,6 @@ public: coverage cov; cu_coverage (checkstack &stack, dwarflint &lint); - ~cu_coverage (); }; #endif//DWARFLINT_CU_COVERAGE_HH diff --git a/dwarflint/test-coverage.cc b/dwarflint/test-coverage.cc new file mode 100644 index 00000000..6f94685a --- /dev/null +++ b/dwarflint/test-coverage.cc @@ -0,0 +1,151 @@ +#include <iostream> +#include <cstdlib> +#include <cassert> +#include "coverage.hh" +#include "pri.hh" + +bool fail = false; + +void +cmpfmt (coverage const &cov, + std::string const &exp) +{ + std::string act = cov::format_ranges (cov); + if (act != exp) + std::cerr << "FAIL: expected: " << exp << std::endl + << " got: " << act << std::endl; +} + +void +cmpholes (coverage const &cov, + std::string const &exp) +{ + uint64_t start = cov.front ().start; + uint64_t len = cov.back ().end () - start; + std::string act = cov::format_holes (cov, start, len); + if (act != exp) + std::cerr << "FAIL: expected: " << exp << std::endl + << " got: " << act << std::endl; +} + +void +chkcov (coverage const &cov, uint64_t start, uint64_t length) +{ + assert (cov.is_covered (start, length)); + for (uint64_t i = start; i < start + length; ++i) + { + assert (cov.is_covered (i, 1)); + for (unsigned k = 0; k < 100; ++k) + { + assert (cov.is_overlap (i, k + 1)); + if (i >= k) + { + assert (cov.is_overlap (i - k, k + 1)); + assert (cov.is_overlap (i - k, 2*k + 1)); + } + } + } +} + +void +chkncov (coverage const &cov, uint64_t start, uint64_t length) +{ + assert (!cov.is_overlap (start, length)); + for (uint64_t i = start; i < start + length; ++i) + { + assert (!cov.is_covered (i, 1)); + assert (!cov.is_overlap (i, 1)); + } +} + +class check_assert_used +{ + bool _m_used; + +public: + check_assert_used () + : _m_used (false) + { + assert (_m_used = true); + if (!_m_used) + abort (); + } +}; + +int +main () +{ + check_assert_used (); + + coverage cov; + assert (cov.empty ()); + cmpfmt(cov, ""); + chkncov (cov, 0x0, 0x100); + + cov.add (0x10, 0x20); + chkncov (cov, 0x0, 0x10); + chkcov (cov, 0x10, 0x20); + chkncov (cov, 0x30, 0x100); + cmpfmt(cov, "[0x10, 0x30)"); + cmpholes(cov, ""); + + cov.add (0x40, 0x20); + chkncov (cov, 0x0, 0x10); + chkcov (cov, 0x10, 0x20); + chkncov (cov, 0x30, 0x10); + chkcov (cov, 0x40, 0x20); + chkncov (cov, 0x60, 0x100); + cmpfmt(cov, "[0x10, 0x30), [0x40, 0x60)"); + cmpholes(cov, "[0x30, 0x40)"); + + cov.add (0x50, 0x20); + cmpfmt(cov, "[0x10, 0x30), [0x40, 0x70)"); + cmpholes(cov, "[0x30, 0x40)"); + + cov.add (5, 1); + cmpfmt(cov, "[0x5, 0x6), [0x10, 0x30), [0x40, 0x70)"); + cmpholes(cov, "[0x6, 0x10), [0x30, 0x40)"); + + cov.add (5, 1); + cmpfmt(cov, "[0x5, 0x6), [0x10, 0x30), [0x40, 0x70)"); + cmpholes(cov, "[0x6, 0x10), [0x30, 0x40)"); + + cov.add (0, 5); + cmpfmt(cov, "[0x0, 0x6), [0x10, 0x30), [0x40, 0x70)"); + cmpholes(cov, "[0x6, 0x10), [0x30, 0x40)"); + + { + coverage cov2 = cov; + cov2.add (0, 0x40); + cmpfmt(cov2, "[0x0, 0x70)"); + } + cov.add (0, 0x30); + cmpfmt(cov, "[0x0, 0x30), [0x40, 0x70)"); + cov.add (0x31, 5); + cmpfmt(cov, "[0x0, 0x30), [0x31, 0x36), [0x40, 0x70)"); + + assert (cov.remove (0x40, 0x30)); + cmpfmt(cov, "[0x0, 0x30), [0x31, 0x36)"); + assert (!cov.remove (0x30, 1)); + cmpfmt(cov, "[0x0, 0x30), [0x31, 0x36)"); + assert (cov.remove (0x2f, 3)); + cmpfmt(cov, "[0x0, 0x2f), [0x32, 0x36)"); + assert (cov.remove (0x10, 0x10)); + cmpfmt(cov, "[0x0, 0x10), [0x20, 0x2f), [0x32, 0x36)"); + assert (cov.remove (0x2, 3)); + cmpfmt(cov, "[0x0, 0x2), [0x5, 0x10), [0x20, 0x2f), [0x32, 0x36)"); + cmpholes(cov, "[0x2, 0x5), [0x10, 0x20), [0x2f, 0x32)"); + assert (cov.remove (0x1, 0x40)); + cmpfmt(cov, "[0x0, 0x1)"); + assert (cov.remove (0x0, 0x40)); + assert (cov.empty ()); + cmpfmt(cov, ""); + + assert (cov == cov); + assert (cov == coverage (cov)); + assert (cov == coverage (cov) + coverage (cov)); + assert ((coverage (cov) - coverage (cov)).empty ()); + + if (fail) + std::exit (1); +} |