From a16f9afb531847043b9ac315c95222f32d1774f1 Mon Sep 17 00:00:00 2001 From: Petr Machata Date: Tue, 14 Jul 2009 15:40:00 +0200 Subject: [PATCH] dwarflint: Changes in coverage analysis module --- src/dwarflint-coverage.c | 157 +++++++++++++++++++++++++++++++++++++-- src/dwarflint-coverage.h | 29 +++++++- src/dwarflint.c | 25 ++----- 3 files changed, 184 insertions(+), 27 deletions(-) diff --git a/src/dwarflint-coverage.c b/src/dwarflint-coverage.c index a0d058c0f..fd9bcdbe8 100644 --- a/src/dwarflint-coverage.c +++ b/src/dwarflint-coverage.c @@ -36,6 +36,9 @@ coverage_find (struct coverage *cov, uint64_t start) void coverage_add (struct coverage *cov, uint64_t start, uint64_t length) { + if (length == 0) + return; + struct cov_range nr = (struct cov_range){start, length}; if (cov->size == 0) { @@ -52,7 +55,7 @@ coverage_add (struct coverage *cov, uint64_t start, uint64_t length) // Coalesce with previous range? struct cov_range *p = r - 1; - if (p >= cov->ranges && coalesce->start <= p->start + p->length) + if (r > cov->ranges && coalesce->start <= p->start + p->length) { uint64_t coalesce_end = coalesce->start + coalesce->length; if (coalesce_end > p->start + p->length) @@ -107,21 +110,120 @@ coverage_add (struct coverage *cov, uint64_t start, uint64_t length) } bool -coverage_is_covered (struct coverage *cov, uint64_t address) +coverage_remove (struct coverage *cov, uint64_t begin, uint64_t length) { + uint64_t end = begin + length; + if (cov->size == 0 || begin == end) + return false; + + struct cov_range *r = coverage_find (cov, begin); + struct cov_range *erase_begin = NULL, *erase_end = r; // end exclusive + bool overlap = false; + + // Cut from previous range? + struct cov_range *p = r - 1; + if (r > cov->ranges && begin < p->start + p->length) + { + uint64_t r_end = p->start + p->length; + // Do we cut the beginning of the range? + if (begin == p->start) + p->length = end >= r_end ? 0 : r_end - end; + else + { + p->length = begin - p->start; + // Do we shoot a hole in that range? + if (end < r_end) + { + coverage_add (cov, end, r_end - end); + return true; + } + } + + overlap = true; + if (p->length == 0) + erase_begin = p; + } + + if (erase_begin == NULL) + erase_begin = r; + + // Cut from next range? + while (r < cov->ranges + cov->size + && r->start < end) + { + overlap = true; + if (end >= r->start + r->length) + { + ++erase_end; + ++r; + } + else + { + uint64_t end0 = r->start + r->length; + r->length = end0 - end; + r->start = end; + assert (end0 == r->start + r->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; + } + + return overlap; +} + +bool +coverage_is_covered (struct coverage *cov, uint64_t start, uint64_t length) +{ + assert (length > 0); + if (cov->size == 0) return false; - struct cov_range *r = coverage_find (cov, address); + struct cov_range *r = coverage_find (cov, start); + uint64_t end = start + length; if (r < cov->ranges + cov->size) - if (address >= r->start && address < r->start + r->length) - return true; + if (start >= r->start) + return end <= r->start + r->length; + if (r > cov->ranges) { --r; - if (address >= r->start && address < r->start + r->length) - return true; + return end <= r->start + r->length; } + + return false; +} + +bool +coverage_is_overlap (struct coverage *cov, uint64_t start, uint64_t length) +{ + if (length == 0 || cov->size == 0) + return false; + + uint64_t end = start + length; + bool overlaps (struct cov_range *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); + } + + struct cov_range *r = coverage_find (cov, start); + + if (r < cov->ranges + cov->size && overlaps (r)) + return true; + + if (r > cov->ranges) + return overlaps (r - 1); + return false; } @@ -130,6 +232,9 @@ coverage_find_holes (struct coverage *cov, uint64_t start, uint64_t length, bool (*hole)(uint64_t start, uint64_t length, void *data), void *data) { + if (length == 0) + return true; + if (cov->size == 0) return hole (start, length, data); @@ -158,8 +263,46 @@ coverage_find_holes (struct coverage *cov, uint64_t start, uint64_t length, return true; } +bool +coverage_find_ranges (struct coverage *cov, + bool (*cb)(uint64_t start, uint64_t length, void *data), + void *data) +{ + for (size_t i = 0; i < cov->size; ++i) + if (!cb (cov->ranges[i].start, cov->ranges[i].length, data)) + return false; + + return true; +} + void coverage_free (struct coverage *cov) { free (cov->ranges); } + +struct coverage * +coverage_clone (struct coverage *cov) +{ + struct coverage *ret = xmalloc (sizeof (*ret)); + WIPE (*ret); + coverage_add_all (ret, cov); + return ret; +} + +void +coverage_add_all (struct coverage *cov, struct coverage *other) +{ + for (size_t i = 0; i < other->size; ++i) + coverage_add (cov, other->ranges[i].start, other->ranges[i].length); +} + +bool +coverage_remove_all (struct coverage *cov, struct coverage *other) +{ + 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; + return ret; +} diff --git a/src/dwarflint-coverage.h b/src/dwarflint-coverage.h index ac80dbf65..9a6d364c3 100644 --- a/src/dwarflint-coverage.h +++ b/src/dwarflint-coverage.h @@ -1,6 +1,7 @@ #include #include #include +#include #define REALLOC(A, BUF) \ do { \ @@ -35,9 +36,31 @@ struct coverage size_t alloc; }; -void coverage_add (struct coverage *ar, uint64_t begin, uint64_t end); -bool coverage_is_covered (struct coverage *ar, uint64_t address); +struct coverage *coverage_clone (struct coverage *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 *cov, struct coverage *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 *cov, struct coverage *other); + +/* Returns true if whole range ADDRESS/LENGTH is covered by COV. + LENGTH may not be zero. */ +bool coverage_is_covered (struct coverage *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 *cov, uint64_t start, uint64_t length); + bool coverage_find_holes (struct coverage *cov, uint64_t start, uint64_t length, bool (*cb)(uint64_t start, uint64_t length, void *data), void *data); -void coverage_free (struct coverage *ar); +bool coverage_find_ranges (struct coverage *cov, + bool (*cb)(uint64_t start, uint64_t length, void *data), + void *data); diff --git a/src/dwarflint.c b/src/dwarflint.c index 380876674..6a314505e 100644 --- a/src/dwarflint.c +++ b/src/dwarflint.c @@ -2114,15 +2114,6 @@ ref_record_free (struct ref_record *rr) free (rr->refs); } -bool -coverage_pristine (struct coverage *cov, uint64_t begin, uint64_t length) -{ - for (uint64_t i = 0; i < length; ++i) - if (coverage_is_covered (cov, begin + i)) - return false; - return true; -} - bool found_hole (uint64_t start, uint64_t length, void *data) { @@ -2317,7 +2308,7 @@ coverage_map_add (struct coverage_map *coverage_map, uint64_t r_cov_end = cov_end + r_delta; if (!overlap && !coverage_map->allow_overlap - && !coverage_pristine (cov, cov_begin, cov_end - cov_begin)) + && coverage_is_overlap (cov, 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, @@ -4410,7 +4401,7 @@ check_loc_or_range_ref (const struct read_ctx *parent_ctx, bool retval = true; bool contains_locations = sec == sec_loc; - if (coverage_is_covered (coverage, addr)) + if (coverage_is_covered (coverage, addr, 1)) { wr_error (wh, ": reference to %#" PRIx64 " points into location or range list.\n", addr); @@ -4439,7 +4430,7 @@ check_loc_or_range_ref (const struct read_ctx *parent_ctx, GElf_Sym begin_symbol_mem, *begin_symbol = &begin_symbol_mem; bool begin_relocated = false; if (!overlap - && !coverage_pristine (coverage, begin_off, addr_64 ? 8 : 4)) + && coverage_is_overlap (coverage, begin_off, addr_64 ? 8 : 4)) HAVE_OVERLAP; if (!read_ctx_read_offset (&ctx, addr_64, &begin_addr)) @@ -4463,7 +4454,7 @@ check_loc_or_range_ref (const struct read_ctx *parent_ctx, GElf_Sym end_symbol_mem, *end_symbol = &end_symbol_mem; bool end_relocated = false; if (!overlap - && !coverage_pristine (coverage, end_off, addr_64 ? 8 : 4)) + && coverage_is_overlap (coverage, end_off, addr_64 ? 8 : 4)) HAVE_OVERLAP; if (!read_ctx_read_offset (&ctx, addr_64, &end_addr)) @@ -4530,8 +4521,8 @@ check_loc_or_range_ref (const struct read_ctx *parent_ctx, /* location expression length */ uint16_t len; if (!overlap - && !coverage_pristine (coverage, - read_ctx_get_offset (&ctx), 2)) + && coverage_is_overlap (coverage, + read_ctx_get_offset (&ctx), 2)) HAVE_OVERLAP; if (!read_ctx_read_2ubyte (&ctx, &len)) @@ -4547,8 +4538,8 @@ check_loc_or_range_ref (const struct read_ctx *parent_ctx, return false; uint64_t expr_end = read_ctx_get_offset (&ctx); if (!overlap - && !coverage_pristine (coverage, - expr_start, expr_end - expr_start)) + && coverage_is_overlap (coverage, + expr_start, expr_end - expr_start)) HAVE_OVERLAP; if (!read_ctx_skip (&ctx, len)) -- 2.47.2