From 4a6e708ed62d1b075029e9e0d0b0077a8f1cf746 Mon Sep 17 00:00:00 2001 From: "jimblandy@gmail.com" Date: Thu, 30 Jul 2009 17:36:23 +0000 Subject: Linux dumper: Use a sorted array of addresses in computing function and line sizes. Replace the sorted lists of files and functions with an array of boundary addresses. This replaces CompareAddress with the default comparison, and SortByAddress and NextAddress with the stock STL sort and upper_bound algorithms, losing ~50 lines of code. a=jimblandy r=nealsid git-svn-id: http://google-breakpad.googlecode.com/svn/trunk@367 4c0a9323-5329-0410-9bdc-e9ce6186880e --- src/common/linux/dump_symbols.cc | 117 ++++++++++++--------------------------- 1 file changed, 34 insertions(+), 83 deletions(-) diff --git a/src/common/linux/dump_symbols.cc b/src/common/linux/dump_symbols.cc index b8846e33..1be6bb78 100644 --- a/src/common/linux/dump_symbols.cc +++ b/src/common/linux/dump_symbols.cc @@ -305,71 +305,6 @@ static int LoadFuncSymbols(struct nlist *list, return cur_list - list; } -// Comapre the address. -// The argument should have a memeber named "addr" -template -static bool CompareAddress(T1 *a, T2 *b) { - return a->addr < b->addr; -} - -// Sort the array into increasing ordered array based on the virtual address. -// Return vector of pointers to the elements in the incoming array. So caller -// should make sure the returned vector lives longer than the incoming vector. -template -static std::vector SortByAddress( - Container *container) { - typedef typename Container::iterator It; - typedef typename Container::value_type T; - std::vector sorted_array_ptr; - sorted_array_ptr.reserve(container->size()); - for (It it = container->begin(); it != container->end(); it++) - sorted_array_ptr.push_back(&(*it)); - std::sort(sorted_array_ptr.begin(), - sorted_array_ptr.end(), - std::ptr_fun(CompareAddress)); - - return sorted_array_ptr; -} - -// Find the address of the next function or source file symbol in the symbol -// table. The address should be bigger than the current function's address. -static ElfW(Addr) NextAddress( - std::vector *sorted_functions, - std::vector *sorted_files, - const struct FuncInfo &func_info) { - std::vector::iterator next_func_iter = - std::find_if(sorted_functions->begin(), - sorted_functions->end(), - std::bind1st( - std::ptr_fun( - CompareAddress - ), - &func_info) - ); - std::vector::iterator next_file_iter = - std::find_if(sorted_files->begin(), - sorted_files->end(), - std::bind1st( - std::ptr_fun( - CompareAddress - ), - &func_info) - ); - if (next_func_iter != sorted_functions->end()) { - if (next_file_iter != sorted_files->end()) - return std::min((*next_file_iter)->addr, (*next_func_iter)->addr); - else - return (*next_func_iter)->addr; - } else { - if (next_file_iter != sorted_files->end()) - return (*next_file_iter)->addr; - else - return 0; - } -} - // Add included file information. // Also fix the source id for the line info. static void AddIncludedFiles(struct SymbolInfo *symbols, @@ -442,21 +377,37 @@ static void AddIncludedFiles(struct SymbolInfo *symbols, // Compute size and rva information based on symbols loaded from stab section. static bool ComputeSizeAndRVA(ElfW(Addr) loading_addr, struct SymbolInfo *symbols) { + SourceFileInfoList::iterator file_it; + FuncInfoList::iterator func_it; + LineInfoList::iterator line_it; + + // A table of all the addresses at which files and functions start. + // We build this from our lists, sort it, and then use it to find + // the ends of functions and source lines for which we have no size + // information. + std::vector boundaries; + for (file_it = symbols->source_file_info.begin(); + file_it != symbols->source_file_info.end(); file_it++) { + boundaries.push_back(file_it->addr); + for (func_it = file_it->func_info.begin(); + func_it != file_it->func_info.end(); func_it++) + boundaries.push_back(func_it->addr); + } + std::sort(boundaries.begin(), boundaries.end()); + int no_next_addr_count = 0; - std::vector sorted_files = - SortByAddress(&(symbols->source_file_info)); - for (size_t i = 0; i < sorted_files.size(); ++i) { - struct SourceFileInfo &source_file = *sorted_files[i]; - std::vector sorted_functions = - SortByAddress(&(source_file.func_info)); - for (size_t j = 0; j < sorted_functions.size(); ++j) { - struct FuncInfo &func_info = *sorted_functions[j]; + for (file_it = symbols->source_file_info.begin(); + file_it != symbols->source_file_info.end(); file_it++) { + for (func_it = file_it->func_info.begin(); + func_it != file_it->func_info.end(); func_it++) { + struct FuncInfo &func_info = *func_it; assert(func_info.addr >= loading_addr); func_info.rva_to_base = func_info.addr - loading_addr; func_info.size = 0; - ElfW(Addr) next_addr = NextAddress(&sorted_functions, - &sorted_files, - func_info); + std::vector::iterator boundary + = std::upper_bound(boundaries.begin(), boundaries.end(), + func_info.addr); + ElfW(Addr) next_addr = (boundary == boundaries.end()) ? 0 : *boundary; // I've noticed functions with an address bigger than any other functions // and source files modules, this is probably the last function in the // module, due to limitions of Linux stab symbol, it is impossible to get @@ -491,15 +442,15 @@ static bool ComputeSizeAndRVA(ElfW(Addr) loading_addr, func_info.size = kDefaultSize; } // Compute line size. - for (LineInfoList::iterator line_info_it = func_info.line_info.begin(); - line_info_it != func_info.line_info.end(); line_info_it++) { - struct LineInfo &line_info = *line_info_it; - LineInfoList::iterator next_line_info_it = line_info_it; - next_line_info_it++; + for (line_it = func_info.line_info.begin(); + line_it != func_info.line_info.end(); line_it++) { + struct LineInfo &line_info = *line_it; + LineInfoList::iterator next_line_it = line_it; + next_line_it++; line_info.size = 0; - if (next_line_info_it != func_info.line_info.end()) { + if (next_line_it != func_info.line_info.end()) { line_info.size = - next_line_info_it->rva_to_func - line_info.rva_to_func; + next_line_it->rva_to_func - line_info.rva_to_func; } else { // The last line in the function. // If we can find a function or source file symbol immediately -- cgit v1.2.1