From e4e5049b7bb41c36b6696a59f59eaafee95aedb1 Mon Sep 17 00:00:00 2001 From: Craig Silverstein Date: Thu, 1 May 2008 00:25:33 +0000 Subject: [PATCH] * dwarf_reader.cc (next_generation_count): New static var. (Addr2line_cache_entry): New struct. (addr2line_cache): New static var. (Dwarf_line_info::one_addr2line): Added caching. (Dwarf_line_info::clear_addr2line_cache): New function. * dwarf_reader.h (Dwarf_line_info::one_addr2line): Add cache-size parameter. (Dwarf_line_info::one_addr2line_cache): New function. * symtab.cc (Symbol_table::detect_odr_violations): Pass new cache-size argument to one_addr2line(), and clear cache. --- gold/ChangeLog | 13 +++++ gold/dwarf_reader.cc | 118 +++++++++++++++++++++++++++++++++++++------ gold/dwarf_reader.h | 18 +++++-- gold/symtab.cc | 8 ++- 4 files changed, 134 insertions(+), 23 deletions(-) diff --git a/gold/ChangeLog b/gold/ChangeLog index 9f056436e5f..10823b52136 100644 --- a/gold/ChangeLog +++ b/gold/ChangeLog @@ -1,3 +1,16 @@ +2008-04-30 Craig Silverstein + + * dwarf_reader.cc (next_generation_count): New static var. + (Addr2line_cache_entry): New struct. + (addr2line_cache): New static var. + (Dwarf_line_info::one_addr2line): Added caching. + (Dwarf_line_info::clear_addr2line_cache): New function. + * dwarf_reader.h (Dwarf_line_info::one_addr2line): Add + cache-size parameter. + (Dwarf_line_info::one_addr2line_cache): New function. + * symtab.cc (Symbol_table::detect_odr_violations): Pass + new cache-size argument to one_addr2line(), and clear cache. + 2008-04-28 Cary Coutant * i386.cc (Relocate::relocate): Fix typos for R_386_PC16 and diff --git a/gold/dwarf_reader.cc b/gold/dwarf_reader.cc index d3faeebea63..ec697e428ef 100644 --- a/gold/dwarf_reader.cc +++ b/gold/dwarf_reader.cc @@ -23,6 +23,7 @@ #include "gold.h" #include +#include #include "elfcpp_swap.h" #include "dwarf.h" @@ -799,35 +800,120 @@ Sized_dwarf_line_info::do_addr2line(unsigned int shndx, // Dwarf_line_info routines. +static unsigned int next_generation_count = 0; + +struct Addr2line_cache_entry +{ + Object* object; + unsigned int shndx; + Dwarf_line_info* dwarf_line_info; + unsigned int generation_count; + unsigned int access_count; + + Addr2line_cache_entry(Object* o, unsigned int s, Dwarf_line_info* d) + : object(o), shndx(s), dwarf_line_info(d), + generation_count(next_generation_count), access_count(0) + { + if (next_generation_count < (1U << 31)) + ++next_generation_count; + } +}; +// We expect this cache to be small, so don't bother with a hashtable +// or priority queue or anything: just use a simple vector. +static std::vector addr2line_cache; + std::string Dwarf_line_info::one_addr2line(Object* object, - unsigned int shndx, off_t offset) + unsigned int shndx, off_t offset, + size_t cache_size) { - switch (parameters->size_and_endianness()) + Dwarf_line_info* lineinfo = NULL; + std::vector::iterator it; + + // First, check the cache. If we hit, update the counts. + for (it = addr2line_cache.begin(); it != addr2line_cache.end(); ++it) { + if (it->object == object && it->shndx == shndx) + { + lineinfo = it->dwarf_line_info; + it->generation_count = next_generation_count; + // We cap generation_count at 2^31 -1 to avoid overflow. + if (next_generation_count < (1U << 31)) + ++next_generation_count; + // We cap access_count at 31 so 2^access_count doesn't overflow + if (it->access_count < 31) + ++it->access_count; + break; + } + } + + // If we don't hit the cache, create a new object and insert into the + // cache. + if (lineinfo == NULL) + { + switch (parameters->size_and_endianness()) + { #ifdef HAVE_TARGET_32_LITTLE - case Parameters::TARGET_32_LITTLE: - return Sized_dwarf_line_info<32, false>(object, shndx).addr2line(shndx, - offset); + case Parameters::TARGET_32_LITTLE: + lineinfo = new Sized_dwarf_line_info<32, false>(object, shndx); break; #endif #ifdef HAVE_TARGET_32_BIG - case Parameters::TARGET_32_BIG: - return Sized_dwarf_line_info<32, true>(object, shndx).addr2line(shndx, - offset); + case Parameters::TARGET_32_BIG: + lineinfo = new Sized_dwarf_line_info<32, true>(object, shndx); break; #endif #ifdef HAVE_TARGET_64_LITTLE - case Parameters::TARGET_64_LITTLE: - return Sized_dwarf_line_info<64, false>(object, shndx).addr2line(shndx, - offset); + case Parameters::TARGET_64_LITTLE: + lineinfo = new Sized_dwarf_line_info<64, false>(object, shndx); break; #endif #ifdef HAVE_TARGET_64_BIG - case Parameters::TARGET_64_BIG: - return Sized_dwarf_line_info<64, true>(object, shndx).addr2line(shndx, - offset); + case Parameters::TARGET_64_BIG: + lineinfo = new Sized_dwarf_line_info<64, true>(object, shndx); break; #endif - default: - gold_unreachable(); + default: + gold_unreachable(); + } + addr2line_cache.push_back(Addr2line_cache_entry(object, shndx, lineinfo)); + } + + // Now that we have our object, figure out the answer + std::string retval = lineinfo->addr2line(shndx, offset); + + // Finally, if our cache has grown too big, delete old objects. We + // assume the common (probably only) case is deleting only one object. + // We use a pretty simple scheme to evict: function of LRU and MFU. + while (addr2line_cache.size() > cache_size) + { + unsigned int lowest_score = ~0U; + std::vector::iterator lowest + = addr2line_cache.end(); + for (it = addr2line_cache.begin(); it != addr2line_cache.end(); ++it) + { + const unsigned int score = (it->generation_count + + (1U << it->access_count)); + if (score < lowest_score) + { + lowest_score = score; + lowest = it; + } + } + if (lowest != addr2line_cache.end()) + { + delete lowest->dwarf_line_info; + addr2line_cache.erase(lowest); + } } + + return retval; +} + +void +Dwarf_line_info::clear_addr2line_cache() +{ + for (std::vector::iterator it = addr2line_cache.begin(); + it != addr2line_cache.end(); + ++it) + delete it->dwarf_line_info; + addr2line_cache.clear(); } #ifdef HAVE_TARGET_32_LITTLE diff --git a/gold/dwarf_reader.h b/gold/dwarf_reader.h index 9c6b175839d..173e8c25495 100644 --- a/gold/dwarf_reader.h +++ b/gold/dwarf_reader.h @@ -72,12 +72,20 @@ class Dwarf_line_info addr2line(unsigned int shndx, off_t offset) { return do_addr2line(shndx, offset); } - // A helper function for a single addr2line lookup. It uses - // parameters() to figure out the size and endianness. This is less - // efficient than using the templatized size and endianness, so only - // call this from an un-templatized context. + // A helper function for a single addr2line lookup. It also keeps a + // cache of the last CACHE_SIZE Dwarf_line_info objects it created; + // set to 0 not to cache at all. The larger CACHE_SIZE is, the more + // chance this routine won't have to re-create a Dwarf_line_info + // object for its addr2line computation; such creations are slow. + // NOTE: Not thread-safe, so only call from one thread at a time. static std::string - one_addr2line(Object* object, unsigned int shndx, off_t offset); + one_addr2line(Object* object, unsigned int shndx, off_t offset, + size_t cache_size); + + // This reclaims all the memory that one_addr2line may have cached. + // Use this when you know you will not be calling one_addr2line again. + static void + clear_addr2line_cache(); private: virtual std::string diff --git a/gold/symtab.cc b/gold/symtab.cc index eeb32fdd572..170a2093680 100644 --- a/gold/symtab.cc +++ b/gold/symtab.cc @@ -2343,10 +2343,12 @@ Symbol_table::detect_odr_violations(const Task* task, // want to run this in a general Task for better // performance, we will need one Task for object, plus // appropriate locking to ensure that we don't conflict with - // other uses of the object. + // other uses of the object. Also note, one_addr2line is not + // currently thread-safe. Task_lock_obj tl(task, locs->object); + // 16 is the size of the object-cache that one_addr2line should use. std::string lineno = Dwarf_line_info::one_addr2line( - locs->object, locs->shndx, locs->offset); + locs->object, locs->shndx, locs->offset, 16); if (!lineno.empty()) line_nums.insert(lineno); } @@ -2362,6 +2364,8 @@ Symbol_table::detect_odr_violations(const Task* task, fprintf(stderr, " %s\n", it2->c_str()); } } + // We only call one_addr2line() in this function, so we can clear its cache. + Dwarf_line_info::clear_addr2line_cache(); } // Warnings functions. -- 2.30.2