From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-sender-0.a4lg.com (mail-sender-0.a4lg.com [IPv6:2401:2500:203:30b:4000:6bfe:4757:0]) by sourceware.org (Postfix) with ESMTPS id 12DC93895FD6 for ; Sun, 20 Nov 2022 01:10:44 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 12DC93895FD6 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=irq.a4lg.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=irq.a4lg.com Received: from [127.0.0.1] (localhost [127.0.0.1]) by mail-sender-0.a4lg.com (Postfix) with ESMTPSA id 5D1E1300089; Sun, 20 Nov 2022 01:10:42 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=irq.a4lg.com; s=2017s01; t=1668906642; bh=M4gV8i9QYbjFKg8y9PqNr9mdeiYXRhilIDDSyrkl+b4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: Mime-Version:Content-Transfer-Encoding; b=FRVh0ma18WvulcBzE3YHSOYZBsEqx6fGZpbv+H4MqgbyLrYxEF+YyMzxDom7I505F mQdL/Jk7TAIFovGRpL0307kFUmJSdIKmB5fDs0iC3ermhqjz75cybeOb9RMWSmruvh 11qrZvsNp+cPZeKy1hoLyh/+v7vDncLQGmDrAV94= From: Tsukasa OI To: Tsukasa OI , Nelson Chu , Kito Cheng , Palmer Dabbelt Cc: binutils@sourceware.org Subject: [PATCH 3/3] RISC-V: Optimized search on mapping symbols Date: Sun, 20 Nov 2022 01:10:09 +0000 Message-Id: In-Reply-To: References: Mime-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.2 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,GIT_PATCH_0,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: From: Tsukasa OI For ELF files with many symbols and/or sections (static libraries, partially linked files [e.g. vmlinux.o] or large object files), the disassembler is drastically slowed down by looking up the suitable mapping symbol. This is caused by the fact that: - It used an inefficient linear search to find the suitable mapping symbol - symtab_pos is not always a good hint for forward linear search and - The symbol table accessible by the disassembler is sorted by address and then section (not section, then address). They sometimes force O(n^2) mapping symbol search time while searching for the suitable mapping symbol for given address. This commit implements: - A binary search to look up suitable mapping symbol (O(log(n)) time per a lookup call, O(n) time on initialization), - Separate mapping symbol table, sorted by section and then address (unless the section to disassemble is NULL), - A very short linear search, even faster than binary search, when disassembling consecutive addresses (usually traverses only 1 or 2 symbols, O(n) on the worst case but this is only expected on adversarial samples) and - Efficient tracking of mapping symbols with ISA string (by propagating arch field of "$x+(arch)" to succeeding "$x" symbols). It also changes when the disassembler reuses the last mapping symbol. This commit only uses the last disassembled address to determine whether the last mapping symbol should be reused. This commit doesn't improve the disassembler performance much on regular programs in general. However, it expects >50% disassembler performance improvements on some files that "RISC-V: Use faster hash table on disassembling" was not effective enough. On bigger libraries, following numbers are observed during the benchmark: - x 2.13 - 2.22 : Static library : Newlib (libc.a) - x 5.67 - 6.09 : Static library : GNU libc (libc.a) - x 11.72 - 12.04 : Shared library : OpenSSL (libcrypto.so) - x 96.29 : Shared library : LLVM 14 (libLLVM-14.so) opcodes/ChangeLog: * disassemble.c (disassemble_free_target): Call new disassemble_free_riscv function to free the memory. * disassemble.h (disassemble_free_riscv): Declare. * riscv-dis.c (struct riscv_mapping_sym): Separate structure to represent a mapping symbol and ISA string corresponding to it. (struct riscv_private_data): Add mapping symbol-related fields. Add is_elf_with_mapsyms. (last_map_symbol, last_stop_offset): Remove. The role is replaced by riscv_private_data.{last_mapping_sym,expected_next_addr}. (from_last_map_symbol): Remove as this is no longer required with the new design. (init_riscv_dis_private_data): Initialize new fields. Filter mapping symbols and make a separate mapping symbol table. (compare_mapping_syms_without_section): New function to sort mapping symbols when the current section is NULL. (compare_mapping_syms_with_section): New function to sort mapping symbols when the current section is not NULL. (riscv_propagate_prev_arch_for_mapping_syms): New function to propagate arch field to succeeding mapping "$x" symbols. (init_riscv_dis_private_data_for_section): Reset last_mapping_sym. Sort the mapping symbol table depending on the current section and propagate arch field. (riscv_get_map_state): Remove. (riscv_search_mapping_sym): Do a binary search to update the mapping state but without reinitializing the architecture here. (riscv_search_mapping_symbol): Use riscv_search_mapping_sym to do a optimized lookup. Reuse the last mapping symbol if able. Use is_elf_with_mapsyms to determine whether the object is an ELF one with mapping symbols. (riscv_data_length): Use last_mapping_sym instead of last_map_symbol. (print_insn_riscv): Add a comment. Update the architecture if the suitable mapping symbol in the table has a non-default one. Update expected_next_addr here. (disassemble_free_riscv): Free the mapping symbol table. --- opcodes/disassemble.c | 1 + opcodes/disassemble.h | 2 + opcodes/riscv-dis.c | 413 +++++++++++++++++++++++++++++------------- 3 files changed, 289 insertions(+), 127 deletions(-) diff --git a/opcodes/disassemble.c b/opcodes/disassemble.c index 704fb476ea9f..49a2b2ac8521 100644 --- a/opcodes/disassemble.c +++ b/opcodes/disassemble.c @@ -790,6 +790,7 @@ disassemble_free_target (struct disassemble_info *info) #endif #ifdef ARCH_riscv case bfd_arch_riscv: + disassemble_free_riscv (info); break; #endif #ifdef ARCH_rs6000 diff --git a/opcodes/disassemble.h b/opcodes/disassemble.h index 2c4c13480990..ac3cddbd78a3 100644 --- a/opcodes/disassemble.h +++ b/opcodes/disassemble.h @@ -105,6 +105,8 @@ extern disassembler_ftype csky_get_disassembler (bfd *); extern disassembler_ftype rl78_get_disassembler (bfd *); extern disassembler_ftype riscv_get_disassembler (bfd *); +extern void disassemble_free_riscv (struct disassemble_info *); + extern void ATTRIBUTE_NORETURN opcodes_assert (const char *, int); #define OPCODES_ASSERT(x) \ diff --git a/opcodes/riscv-dis.c b/opcodes/riscv-dis.c index 1a7ca74b8020..8012e4bd450a 100644 --- a/opcodes/riscv-dis.c +++ b/opcodes/riscv-dis.c @@ -83,22 +83,34 @@ static riscv_parse_subset_t riscv_rps_dis = false, /* check_unknown_prefixed_ext. */ }; +/* A RISC-V mapping symbol (parsed and expanded). */ +struct riscv_mapping_sym +{ + uintptr_t section; + bfd_vma address; + const char *arch; + int index; + enum riscv_seg_mstate mstate; + bool with_arch; +}; + /* Private data structure for the RISC-V disassembler. */ struct riscv_private_data { bfd_vma gp; bfd_vma print_addr; bfd_vma hi_addr[NGPR]; + bfd_vma expected_next_addr; void* last_section; + struct riscv_mapping_sym *mapping_syms; + struct riscv_mapping_sym *last_mapping_sym; + struct riscv_mapping_sym *prev_last_mapping_sym; + size_t mapping_syms_size; bool to_print_addr; bool has_gp; + bool is_elf_with_mapsyms; }; -/* Used for mapping symbols. */ -static int last_map_symbol = -1; -static bfd_vma last_stop_offset = 0; -static bool from_last_map_symbol = false; - /* Register names as used by the disassembler. */ static const char * const *riscv_gpr_names; static const char * const *riscv_fpr_names; @@ -167,6 +179,10 @@ set_riscv_dis_arch_context (riscv_dis_arch_context_t *context, static void build_riscv_opcodes_hash_table (void); +static enum riscv_seg_mstate riscv_get_map_state_by_name (const char *name, + const char **arch); +static void +riscv_propagate_prev_arch_for_mapping_syms (struct disassemble_info *, bool); /* Guess and update current XLEN. */ @@ -246,16 +262,129 @@ init_riscv_dis_private_data (struct disassemble_info *info) pd->print_addr = 0; for (int i = 0; i < (int)ARRAY_SIZE (pd->hi_addr); i++) pd->hi_addr[i] = -1; + pd->expected_next_addr = 0; pd->last_section = NULL; + pd->mapping_syms = NULL; + pd->last_mapping_sym = NULL; + pd->prev_last_mapping_sym = NULL; + pd->mapping_syms_size = 0; pd->to_print_addr = false; pd->has_gp = false; + size_t n_mapping_syments = 0; + for (int i = 0; i < info->symtab_size; i++) - if (strcmp (bfd_asymbol_name (info->symtab[i]), RISCV_GP_SYMBOL) == 0) - { - pd->gp = bfd_asymbol_value (info->symtab[i]); - pd->has_gp = true; - } + { + if (strcmp (bfd_asymbol_name (info->symtab[i]), RISCV_GP_SYMBOL) == 0) + { + pd->gp = bfd_asymbol_value (info->symtab[i]); + pd->has_gp = true; + } + if (riscv_get_map_state_by_name (bfd_asymbol_name (info->symtab[i]), NULL) + != MAP_NONE) + n_mapping_syments++; + } + + pd->is_elf_with_mapsyms + = info->symtab_size != 0 + && bfd_asymbol_flavour (*info->symtab) == bfd_target_elf_flavour + && n_mapping_syments; + if (pd->is_elf_with_mapsyms) + { + /* Allocate mapping symbols (with head/tail sentinel entries). */ + struct riscv_mapping_sym *msym = pd->mapping_syms + = xcalloc (n_mapping_syments + 2, sizeof (struct riscv_mapping_sym)); + /* Head sentinel entry. */ + msym->index = -1; + msym->mstate = MAP_NONE; + msym++; + /* Mapping symbols. */ + for (int i = 0; i < info->symtab_size; i++) + { + const char* arch = NULL; + enum riscv_seg_mstate state = riscv_get_map_state_by_name ( + bfd_asymbol_name (info->symtab[i]), &arch); + if (state == MAP_NONE) + continue; + msym->section = (uintptr_t)info->symtab[i]->section; + msym->address = bfd_asymbol_value (info->symtab[i]); + msym->index = i; + msym->mstate = state; + msym->with_arch = (arch != NULL); + if (arch != NULL) + /* Assume symbol name is $x[ARCH]. */ + msym->arch = bfd_asymbol_name (info->symtab[i]) + 2; + msym++; + } + /* Tail sentinel entry. */ + msym->index = -1; + msym->mstate = MAP_NONE; + + pd->mapping_syms_size = n_mapping_syments; + /* Mapping symbols are now ordered for section == NULL. + will be qsort-ed on the first non-NULL section. + Although following propagation is redundant on most cases, + this is required for functional correctness. */ + riscv_propagate_prev_arch_for_mapping_syms (info, false); + } +} + +/* Compare two mapping symbols (sort by original index). */ + +static int +compare_mapping_syms_without_section (const void *ap, const void *bp) +{ + const struct riscv_mapping_sym *a = ap; + const struct riscv_mapping_sym *b = bp; + return a->index - b->index; +} + +/* Compare two mapping symbols (sort by section, address and + original index for a stable sort). */ + +static int +compare_mapping_syms_with_section (const void* ap, const void* bp) +{ + const struct riscv_mapping_sym *a = ap; + const struct riscv_mapping_sym *b = bp; + if (a->section < b->section) + return -1; + else if (a->section > b->section) + return +1; + else if (a->address < b->address) + return -1; + else if (a->address > b->address) + return +1; + return compare_mapping_syms_without_section (a, b); +} + +/* Update "previous" architecture for sorted mapping symbol table. + If is_per_section is true, section boundary is handled. */ + +static void +riscv_propagate_prev_arch_for_mapping_syms (struct disassemble_info *info, + bool is_per_section) +{ + struct riscv_private_data *pd = info->private_data; + struct riscv_mapping_sym *msym = pd->mapping_syms + 1; + struct riscv_mapping_sym *mend = msym + pd->mapping_syms_size; + const char *prev_arch = NULL; + uintptr_t prev_section = 0; + for (; msym != mend; msym++) + { + if (msym->mstate != MAP_INSN) + continue; + if (is_per_section && prev_section != msym->section) + { + prev_section = msym->section; + /* Revert to default arch (NULL) if head of the section. */ + prev_arch = NULL; + } + if (msym->with_arch) + prev_arch = msym->arch; + else + msym->arch = prev_arch; + } } /* Initialize private data when the section to disassemble is changed. */ @@ -264,6 +393,31 @@ static void init_riscv_dis_private_data_for_section (struct disassemble_info *info) { struct riscv_private_data *pd = info->private_data; + + if (pd->is_elf_with_mapsyms) + { + /* Clear the last mapping symbol because we start to + dump a new section. */ + pd->last_mapping_sym = NULL; + + /* Sort the mapping symbols depending on the current section + (depending on whether the current section is NULL or not). */ + if (pd->last_section == NULL && info->section != NULL) + { + qsort (pd->mapping_syms + 1, pd->mapping_syms_size, + sizeof (struct riscv_mapping_sym), + compare_mapping_syms_with_section); + riscv_propagate_prev_arch_for_mapping_syms (info, true); + } + else if (pd->last_section != NULL && info->section == NULL) + { + qsort (pd->mapping_syms + 1, pd->mapping_syms_size, + sizeof (struct riscv_mapping_sym), + compare_mapping_syms_without_section); + riscv_propagate_prev_arch_for_mapping_syms (info, false); + } + } + pd->last_section = info->section; } @@ -1086,60 +1240,64 @@ riscv_get_map_state_by_name (const char *name, const char** arch) return MAP_NONE; } -/* Return true if we find the suitable mapping symbol, - and also update the STATE. Otherwise, return false. */ +/* Search for the suitable mapping symbol and + update the state data depending on the result. + It assumes that ELF mapping symbol table is not empty. */ -static bool -riscv_get_map_state (int n, - enum riscv_seg_mstate *state, - struct disassemble_info *info, - bool update) +static void +riscv_search_mapping_sym (bfd_vma memaddr, + enum riscv_seg_mstate *state, + struct disassemble_info *info) { - const char *name, *arch = NULL; - - /* If the symbol is in a different section, ignore it. */ - if (info->section != NULL - && info->section != info->symtab[n]->section) - return false; - - name = bfd_asymbol_name (info->symtab[n]); - enum riscv_seg_mstate newstate = riscv_get_map_state_by_name (name, &arch); - if (newstate == MAP_NONE) - return false; - *state = newstate; - if (newstate == MAP_INSN && update) - { - if (arch) - { - /* Override the architecture. */ - update_riscv_dis_arch (&dis_arch_context_override, arch); - } - else if (!from_last_map_symbol - && set_riscv_current_dis_arch_context (&dis_arch_context_default)) - { - /* Revert to the default architecture and call init functions if: - - there's no ISA string in the mapping symbol, - - mapping symbol is not reused and - - current disassembler context is changed to the default one. - This is a shortcut path to avoid full update_riscv_dis_arch. */ - init_riscv_dis_state_for_arch (); - init_riscv_dis_state_for_arch_and_options (); - } - } - return true; + struct riscv_private_data *pd = info->private_data; + struct riscv_mapping_sym *msym = pd->mapping_syms; + uintptr_t cur_section = (uintptr_t) info->section; + /* Do a binary search to find the last mapping symbol (which does not + violate upper address and section boundaries) that may be suitable + for a given section and address. + This part is equivalent to std::partition_point(...)-1. */ + size_t low = 1, len = pd->mapping_syms_size; + while (len != 0) + { + size_t half = len / 2; + size_t mid = low + half; + bool is_mid_in_bound = cur_section + ? (msym[mid].section < cur_section + || (msym[mid].section == cur_section + && msym[mid].address <= memaddr)) + : msym[mid].address <= memaddr; + if (is_mid_in_bound) + { + len -= half + 1; + low = mid + 1; + } + else + len = half; + } + msym += low - 1; + /* The result may however violate lower boundaries. + Check if the result is actually suitable. */ + if ((cur_section && cur_section != msym->section) + || msym->mstate == MAP_NONE) + { + pd->last_mapping_sym = NULL; + return; + } + /* Update the state and the last suitable mapping symbol. */ + pd->last_mapping_sym = msym; + *state = msym->mstate; } -/* Check the sorted symbol table (sorted by the symbol value), find the - suitable mapping symbols. */ +/* Check the sorted mapping symbol table (or section flags if not available) + and find the suitable mapping symbol. + Update last mapping symbol-related data and return the new state. */ static enum riscv_seg_mstate riscv_search_mapping_symbol (bfd_vma memaddr, struct disassemble_info *info) { enum riscv_seg_mstate mstate; - bool found = false; - int symbol = -1; - int n; + struct riscv_private_data *pd = info->private_data; /* Decide whether to print the data or instruction by default, in case we can not find the corresponding mapping symbols. */ @@ -1147,72 +1305,39 @@ riscv_search_mapping_symbol (bfd_vma memaddr, if (info->section && (info->section->flags & SEC_CODE) == 0) mstate = MAP_DATA; - if (info->symtab_size == 0 - || bfd_asymbol_flavour (*info->symtab) != bfd_target_elf_flavour) + if (!pd->is_elf_with_mapsyms) return mstate; - /* Reset the last_map_symbol if the address is zero. */ - if (memaddr == 0) - last_map_symbol = -1; - - /* If the last stop offset is different from the current one, then - don't use the last_map_symbol to search. We usually reset the - info->stop_offset when handling a new section. */ - from_last_map_symbol = (last_map_symbol >= 0 - && info->stop_offset == last_stop_offset); - - /* Start scanning at the start of the function, or wherever - we finished last time. */ - n = info->symtab_pos + 1; - if (from_last_map_symbol && n >= last_map_symbol) - n = last_map_symbol; - - /* Find the suitable mapping symbol to dump. */ - for (; n < info->symtab_size; n++) + if (pd->last_mapping_sym != NULL + && memaddr != 0 + && memaddr == pd->expected_next_addr) { - bfd_vma addr = bfd_asymbol_value (info->symtab[n]); - /* We have searched all possible symbols in the range. */ - if (addr > memaddr) - break; - if (riscv_get_map_state (n, &mstate, info, true)) + /* Reuse the last mapping symbol. */ + mstate = pd->last_mapping_sym->mstate; + /* Do a forward linear search to find the next mapping symbol. */ + struct riscv_mapping_sym *msym = pd->last_mapping_sym + 1; + while (true) { - symbol = n; - found = true; - /* Do not stop searching, in case there are some mapping - symbols have the same value, but have different names. - Use the last one. */ + /* Break if we reached to the end. */ + if (msym->mstate == MAP_NONE) + break; + /* For section symbols, only test symbols in the same section. */ + if (info->section && (uintptr_t)info->section != msym->section) + break; + /* Don't go beyond memaddr. */ + if (memaddr < msym->address) + break; + /* Update the state and go to the next symbol. */ + mstate = msym->mstate; + pd->last_mapping_sym = msym++; } } - - /* We can not find the suitable mapping symbol above. Therefore, we - look forwards and try to find it again, but don't go pass the start - of the section. Otherwise a data section without mapping symbols - can pick up a text mapping symbol of a preceeding section. */ - if (!found) + else { - n = info->symtab_pos; - if (from_last_map_symbol && n >= last_map_symbol) - n = last_map_symbol; - - for (; n >= 0; n--) - { - bfd_vma addr = bfd_asymbol_value (info->symtab[n]); - /* We have searched all possible symbols in the range. */ - if (addr < (info->section ? info->section->vma : 0)) - break; - /* Stop searching once we find the closed mapping symbol. */ - if (riscv_get_map_state (n, &mstate, info, true)) - { - symbol = n; - break; - } - } + /* Can't reuse the mapping symbol. Do a binary search. */ + riscv_search_mapping_sym (memaddr, &mstate, info); } - /* Save the information for next use. */ - last_map_symbol = symbol; - last_stop_offset = info->stop_offset; - return mstate; } @@ -1224,25 +1349,19 @@ riscv_data_length (bfd_vma memaddr, { bfd_vma length; bool found = false; + struct riscv_private_data *pd = info->private_data; length = 4; - if (info->symtab_size != 0 - && bfd_asymbol_flavour (*info->symtab) == bfd_target_elf_flavour - && last_map_symbol >= 0) + if (pd->last_mapping_sym != NULL) { - int n; - enum riscv_seg_mstate m = MAP_NONE; - for (n = last_map_symbol + 1; n < info->symtab_size; n++) + /* Get the next mapping symbol and adjust the length. */ + struct riscv_mapping_sym *msym = pd->last_mapping_sym + 1; + if (msym->mstate != MAP_NONE + && (!info->section || (uintptr_t)info->section == msym->section)) { - bfd_vma addr = bfd_asymbol_value (info->symtab[n]); - if (addr > memaddr - && riscv_get_map_state (n, &m, info, false)) - { - if (addr - memaddr < length) - length = addr - memaddr; - found = true; - break; - } + if (msym->address - memaddr < length) + length = msym->address - memaddr; + found = true; } } if (!found) @@ -1331,6 +1450,7 @@ print_insn_riscv (bfd_vma memaddr, struct disassemble_info *info) if (xlen == 0) update_riscv_dis_xlen (info); + /* Update default state (data or code) for the disassembler. */ mstate = riscv_search_mapping_symbol (memaddr, info); /* Set the size to dump. */ @@ -1353,6 +1473,30 @@ print_insn_riscv (bfd_vma memaddr, struct disassemble_info *info) insn = (insn_t) bfd_getl16 (packet); dump_size = riscv_insn_length (insn); riscv_disassembler = riscv_disassemble_insn; + /* Update the architecture if the mapping symbol is updated. */ + if (pd->last_mapping_sym != pd->prev_last_mapping_sym) + { + /* mapping_syms is always available but last_mapping_sym may not. */ + const char *arch + = pd->last_mapping_sym ? pd->last_mapping_sym->arch : NULL; + if (arch) + { + /* Override the architecture. */ + update_riscv_dis_arch (&dis_arch_context_override, arch); + } + else if (set_riscv_current_dis_arch_context ( + &dis_arch_context_default)) + { + /* Revert to the default architecture and call init functions if: + - there's no ISA string in the mapping symbol entry and + - current disassembler context is changed to the default one. + This is a shortcut path to avoid full update_riscv_dis_arch. + */ + init_riscv_dis_state_for_arch (); + init_riscv_dis_state_for_arch_and_options (); + } + pd->prev_last_mapping_sym = pd->last_mapping_sym; + } } /* Fetch the instruction to dump. */ @@ -1364,7 +1508,10 @@ print_insn_riscv (bfd_vma memaddr, struct disassemble_info *info) } insn = (insn_t) bfd_get_bits (packet, dump_size * 8, false); - return (*riscv_disassembler) (memaddr, insn, info); + /* Print, save the next expected address and return current size. */ + status = (*riscv_disassembler) (memaddr, insn, info); + pd->expected_next_addr = memaddr + status; + return status; } disassembler_ftype @@ -1419,6 +1566,18 @@ disassemble_init_riscv (struct disassemble_info *info) init_riscv_dis_state_for_arch_and_options (); } +/* Free disassemble_info and all disassembler-related info + (e.g. heap-allocated information that depends on either disassemble_info + or BFD). */ + +void +disassemble_free_riscv (struct disassemble_info *info) +{ + struct riscv_private_data *pd = info->private_data; + if (pd) + free (pd->mapping_syms); +} + /* Prevent use of the fake labels that are generated as part of the DWARF and for relaxable relocations in the assembler. */ -- 2.38.1