Some high level review, I'm not the best expert on dwarf.
It might be useful to state how you tested this. Just with gcc current
version dwarf for some projects or other compiler's binaries too?
Does it survive running with random program generators like csmith
or yarpgen?
> +
> +/* Normalize path separators and redundant "." components. */
> +std::string
> +canonical_source_path (std::string path)
It's a bit surprising this is needed, but ok.
Ideally someone else would fix this. I assume it's coming from build
systems?
> +{
> + if (path.empty ())
> + return path;
> + for (char &c : path)
> + if (c == '\\')
> + c = '/';
> + while (path.size () >= 2 && path[0] == '.' && path[1] == '/')
> + path.erase (0, 2);
> + for (;;)
> + {
> + const size_t pos = path.find ("/./");
> + if (pos == std::string::npos)
> + break;
Indentation issues again, also elsewhere. Or do you have an unusual tab
width setting?
> + for (;;)
> + {
> + const size_t pos = path.find ("//");
> + if (pos == std::string::npos)
> + break;
> + path.erase (pos, 1);
> + }
> + return path;
> +}
> +
> +/* Build INDEX for RANGES, which must be sorted by start. Each leaf stores
> + one range's end, and each internal node stores the maximum end below it.
> */
> +template <typename Range>
> +void
> +build_range_max_tree (const std::vector<Range> &ranges,
> + range_max_tree_index &index)
> +{
> + index.leaf_base = 1;
> + while (index.leaf_base < ranges.size ())
> + index.leaf_base *= 2;
Just do a shift directly?
But can't this easily overflow?
> + index.max_ends.assign (index.leaf_base * 2, 0);
> + for (size_t i = 0; i < ranges.size (); ++i)
> + index.max_ends[index.leaf_base + i] = ranges[i].end;
> + for (size_t i = index.leaf_base; i-- > 1;)
> + index.max_ends[i]
> + = std::max (index.max_ends[i * 2], index.max_ends[i * 2 + 1]);
The tree in a vector doesn't seem to be space efficient, i assume it has
a lot of holes for large data? How big could it be?
I would consider some tree with pointers, even though the base memory overhead
will be higher. Perhaps just standard map<>?
> + if (start >= end || ranges.empty ())
> + return;
> + const auto limit
> + = std::lower_bound (ranges.begin (),
> + ranges.end (),
> + end,
> + [] (const Range &range, uint64_t address)
> + {
> + return range.start < address;
> + });
> + const size_t range_limit = static_cast<size_t> (limit - ranges.begin ());
> + visit_range_max_tree (
> + index, 1, 0, index.leaf_base, range_limit, start, visitor);
> +}
> +
> +/* A DWARF file-table entry usable as a profile source file. GCC also emits
> + pseudo-files (<built-in>, <artificial>) that name no source. */
> +bool
> +dwarf_source_file_is_usable (const char *file)
> +{
> + return file != nullptr && file[0] != '\0' && file[0] != '<';
> +}
Real files could legitimately with < ? I'm not sure it would be easy
to handle, but it seems like a real issue.
> +/* ELF symtab entries treated as correlatable function ranges: STT_FUNC,
> + trailing .cold blocks, and .__part.N splits; reject @plt and size 0. */
> +bool
> +symtab_accepts_function_symbol (const char *name, uint64_t size, int
> sym_type)
> +{
> + if (name == nullptr || name[0] == '\0' || size == 0)
> + return false;
> +
> + std::string sv (name);
> + if (gcc_symbol::has_suffix (sv, "@plt"))
> + return false;
> + if (sym_type == STT_FUNC || gcc_symbol::has_suffix (sv, ".cold"))
> + return true;
> +
> + while (!sv.empty ()
> + && std::isdigit (static_cast<unsigned char> (sv.back ())))
> + sv.pop_back ();
> + return gcc_symbol::has_suffix (sv, ".__part.");
Some of this would be a lot simpler with C++ regexprs, but ok.
> +/* True if every child PC range lies inside some parent range. */
> +bool
> +pc_ranges_subset_of (const pc_range_list &child, const pc_range_list &parent)
> +{
> + if (child.empty ())
> + return false;
> + return std::all_of (child.begin (), child.end (), [&] (const auto &cr)
> + {
> + const uint64_t clo = cr.first;
> + const uint64_t chi = cr.second;
> + if (chi <= clo)
> + return true;
> + return std::any_of (parent.begin (), parent.end (), [&] (const auto &pr)
> + {
> + return pr.first <= clo && chi <= pr.second;
> + });
> + });
> +}
Isn't this O(n^2)? hopefully the nests are small, but i assume it
wouldn't be that hard to fix.
> +/* CU path for DW_AT_call_file, or null. libdw's table is already indexed by
> + the raw attribute value (DWARF 5 from 0; earlier versions keep a dummy
> + row 0). */
> +const char *
> +die_call_file_path (Dwarf_Die *die)
> +{
> + Dwarf_Attribute attr_mem;
> + if (die == nullptr || dwarf_attr (die, DW_AT_call_file, &attr_mem) ==
> nullptr)
> + return nullptr;
> + Dwarf_Word file_idx = 0;
> + if (dwarf_formudata (&attr_mem, &file_idx) != 0)
> + return nullptr;
> + Dwarf_Die cu_mem;
> + Dwarf_Die *cu = dwarf_diecu (die, &cu_mem, nullptr, nullptr);
> + Dwarf_Files *files = nullptr;
> + size_t nfiles = 0;
> + if (cu == nullptr || dwarf_getsrcfiles (cu, &files, &nfiles) != 0
Isn't this expensive to call repeatedly without any caching for CUs
with lots of files?
> + Dwarf_Die *scopes = nullptr;
> + const int nscopes = dwarf_getscopes_die (&origin, &scopes);
> + /* scopes[0] is ORIGIN itself; enclosing scopes begin at index 1. */
> + for (int i = 1; i < nscopes; ++i)
> + {
> + const int tag = dwarf_tag (&scopes[i]);
> + if (tag != DW_TAG_class_type && tag != DW_TAG_structure_type
> + && tag != DW_TAG_union_type)
> + continue;
Can a union have code scope?
> +/* Open a libdw session on BINARY_PATH; each thread needs its own, as handles
> + are not thread-safe. */
Okay I guess i'll learn later how this uses threading, but it's a bit
surprising.
> +/* Construct over BINARY_PATH, narrowing the DWARF scope to SAMPLED_RANGES.
> */
> +dwarf_reader_impl::dwarf_reader_impl (std::string binary_path,
> + pc_range_list sampled_ranges)
> + : binary_path_ (std::move (binary_path))
> +{
> + /* Split sample scope into merged intervals. */
> + pc_range_list ranges;
> + ranges.reserve (sampled_ranges.size ());
> + for (const auto &sampled_range : sampled_ranges)
> + {
> + const uint64_t start = sampled_range.first;
> + const uint64_t end = sampled_range.second;
> + if (end <= start)
> + continue;
> + ranges.emplace_back (start, end);
> + }
So why not remove empty ranges earlier? Then it's just a copy
> +
> + std::sort (ranges.begin (), ranges.end ());
> + for (const auto &r : ranges)
> + {
> + if (!profile_sample_ranges_.empty ()
> + && r.first <= profile_sample_ranges_.back ().second)
> + profile_sample_ranges_.back ().second
> + = std::max (profile_sample_ranges_.back ().second, r.second);
Can this happen to any entry except the last?
> + else
> + profile_sample_ranges_.push_back (r);
> + }
> +}
> +
> +{
> + out.clear ();
> + std::unordered_set<uint64_t> seen;
> + seen.reserve (64);
> + visit_overlapping_ranges
> + (address_ranges_, address_range_index_, start, end, [&] (size_t i)
> + {
> + const address_range_entry &entry = address_ranges_[i];
> + const uint64_t seed_pc
> + = entry.line_table_pc != 0 ? entry.line_table_pc : entry.start;
> + if (seed_pc >= start && seed_pc < end && seen.insert (seed_pc).second)
> + out.push_back (seed_pc);
> + });
Is that really catching all overlaps when you just check the ends? Or I
might be misunderstanding the algorithm.
> + return 0;
> + const bool is_clone = has_gcc_generated_suffix (name);
> + const function_range entry = dwarf_functions_at_entry (start_addr);
> + uint32_t unnamed = 0;
> + bool unnamed_ambiguous = false;
> + for (auto it = entry.first; it != entry.second; ++it)
> + {
> + if (it->end_addr <= it->start_addr)
> + continue;
> + if (is_clone
> + && gcc_symbol::name_equivalent (string_value (it->name), name))
> + return it->start_line;
> + if (it->start_line == 0)
> + continue;
> + if (unnamed == 0)
> + unnamed = it->start_line;
> + else if (unnamed != it->start_line)
> + {
> + unnamed_ambiguous = true;
> + unnamed = std::min (unnamed, it->start_line);
> + }
> + }
We're sure this cannot jump between different files? How about someone
doing #include inside a function?
> + return !profile_cu_offs_.empty ();
> +}
> +
> +/* Every CU DIE offset in the binary, in .debug_info order. */
> +std::vector<Dwarf_Off>
> +dwarf_reader_impl::all_cu_die_offsets () const
> +{
> + std::vector<Dwarf_Off> cu_dies;
No reserve? I guess you could do some kind of estimate.
Or maybe there aren't that many cus.
> + for (Dwarf_Off off = 0;;)
> + {
> + Dwarf_Off next_off = 0;
> + size_t header_size = 0;
> + if (dwarf_nextcu (
> + dw_.dwarf, off, &next_off, &header_size, nullptr, nullptr, nullptr)
> + != 0)
> + break;
> + cu_dies.push_back (off + header_size);
> + if (next_off <= off)
> + break;
> + off = next_off;
> + }
> + return cu_dies;
> +}
> +
> +/* How many threads to walk N_CUS compilation units with: the configured
> + count, capped so none of them sits idle. */
> +unsigned
> +dwarf_reader_impl::dwarf_parse_thread_count (size_t n_cus) const
> +{
> + return static_cast<unsigned> (std::min<size_t> (n_cus, parse_threads_));
> +}
> +
> +/* Run BODY on NUM_THREADS workers, giving each its own libdw session since
> + handles are not thread-safe, or running it inline on the reader's session
> + when a single worker is asked for. False when a worker could not reopen
> + the binary; the others still finish, as they share one work queue. */
Okay I hope the threading is worth it and won't lead to difficult to
reproduce bugs. I guess eventually you could have a signal handler
like main gcc that reruns with a single thread.
Did you ever run it with a thread sanitizer like setup to check for data
races?
One worry would be memory consumption with parallel builds on large
files.
-Andi
