[PATCH 0/3] RISC-V: Disassembler Core Optimization 1-2 (Mapping symbols)

[PATCH 0/3] RISC-V: Disassembler Core Optimization 1-2 (Mapping symbols)

[Tsukasa OI]

Hello,

This is the Part 4 of 4-part project to improve disassembler performance
drastically:
<https://github.com/a4lg/binutils-gdb/wiki/proj_dis_perf_improvements_1>

** this patchset does not apply to master directly. **

This patchset requires following patchset(s) to be applied first:
<https://sourceware.org/pipermail/binutils/2022-November/124378.html>
<https://sourceware.org/pipermail/binutils/2022-November/124519.html>

Following is basically a copy from the PATCH 3/3 commit message.


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)


Thanks,
Tsukasa




Tsukasa OI (3):
  RISC-V: Easy optimization on riscv_search_mapping_symbol
  RISC-V: Per-section private data initialization
  RISC-V: Optimized search on mapping symbols

 opcodes/disassemble.c |   1 +
 opcodes/disassemble.h |   2 +
 opcodes/riscv-dis.c   | 443 +++++++++++++++++++++++++++++-------------
 3 files changed, 311 insertions(+), 135 deletions(-)


base-commit: 844db363911065a3b5f0c5e4601f89ee1d7360c5
-- 
2.38.1

[PATCH 1/3] RISC-V: Easy optimization on riscv_search_mapping_symbol

[Tsukasa OI]

From: Tsukasa OI <research_trasio@irq.a4lg.com>

Before further optimization, we can optimize the function
riscv_search_mapping_symbol a bit for clarity.

opcodes/ChangeLog:

	* riscv-dis.c (riscv_search_mapping_symbol): Make MAP_INSN default
	considering major usecases.  Remove setting found here as no one
	uses the value after setting this.  memaddr cannot be negative
	so simplify and change comment.

Idea-by: Nelson Chu <nelson@rivosinc.com>
---
 opcodes/riscv-dis.c | 13 +++++--------
 1 file changed, 5 insertions(+), 8 deletions(-)

diff --git a/opcodes/riscv-dis.c b/opcodes/riscv-dis.c
index 32e7b1174436..9ea4da9b219b 100644
--- a/opcodes/riscv-dis.c
+++ b/opcodes/riscv-dis.c
@@ -1132,18 +1132,16 @@ riscv_search_mapping_symbol (bfd_vma memaddr,
 
   /* Decide whether to print the data or instruction by default, in case
      we can not find the corresponding mapping symbols.  */
-  mstate = MAP_DATA;
-  if ((info->section
-       && info->section->flags & SEC_CODE)
-      || !info->section)
-    mstate = MAP_INSN;
+  mstate = MAP_INSN;
+  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)
     return mstate;
 
-  /* Reset the last_map_symbol if we start to dump a new section.  */
-  if (memaddr <= 0)
+  /* 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
@@ -1195,7 +1193,6 @@ riscv_search_mapping_symbol (bfd_vma memaddr,
 	  if (riscv_get_map_state (n, &mstate, info, true))
 	    {
 	      symbol = n;
-	      found = true;
 	      break;
 	    }
 	}
-- 
2.38.1

[PATCH 2/3] RISC-V: Per-section private data initialization

[Tsukasa OI]

From: Tsukasa OI <research_trasio@irq.a4lg.com>

This is one more preparation for mapping symbol optimization.  It adds a
separate function that is called when the section to disassemble is changed.

This commit enables tracking per-section state management required for the
next optimization ("RISC-V: Optimized search on mapping symbols").

opcodes/ChangeLog:

	* riscv-dis.c (struct riscv_private_data): Add last_section.
	(init_riscv_dis_private_data): Initialize last_section.
	(init_riscv_dis_private_data_for_section): New function. update
	last_section here.
	(print_insn_riscv): Track section changes.
---
 opcodes/riscv-dis.c | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/opcodes/riscv-dis.c b/opcodes/riscv-dis.c
index 9ea4da9b219b..1a7ca74b8020 100644
--- a/opcodes/riscv-dis.c
+++ b/opcodes/riscv-dis.c
@@ -89,6 +89,7 @@ struct riscv_private_data
   bfd_vma gp;
   bfd_vma print_addr;
   bfd_vma hi_addr[NGPR];
+  void* last_section;
   bool to_print_addr;
   bool has_gp;
 };
@@ -245,6 +246,7 @@ 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->last_section = NULL;
   pd->to_print_addr = false;
   pd->has_gp = false;
 
@@ -256,6 +258,15 @@ init_riscv_dis_private_data (struct disassemble_info *info)
       }
 }
 
+/* Initialize private data when the section to disassemble is changed.  */
+
+static void
+init_riscv_dis_private_data_for_section (struct disassemble_info *info)
+{
+  struct riscv_private_data *pd = info->private_data;
+  pd->last_section = info->section;
+}
+
 /* Update architecture for disassembler with its context.
    Call initialization functions if either:
    -  the architecture for current context is changed or
@@ -1308,7 +1319,13 @@ print_insn_riscv (bfd_vma memaddr, struct disassemble_info *info)
 
   /* Initialize the private data.  */
   if (info->private_data == NULL)
-    init_riscv_dis_private_data (info);
+    {
+      init_riscv_dis_private_data (info);
+      init_riscv_dis_private_data_for_section (info);
+    }
+  struct riscv_private_data *pd = info->private_data;
+  if (info->section != pd->last_section)
+    init_riscv_dis_private_data_for_section (info);
 
   /* Guess and update XLEN if we haven't determined it yet.  */
   if (xlen == 0)
-- 
2.38.1

[PATCH 3/3] RISC-V: Optimized search on mapping symbols

[Tsukasa OI]

From: Tsukasa OI <research_trasio@irq.a4lg.com>

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,
 \f
 
 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

[PATCH v2 0/3] RISC-V: Disassembler Core Optimization 1-2 (Mapping symbols)

[Tsukasa OI]

Hello,

This is the Part 4 of 4-part project to improve disassembler performance
drastically:
<https://github.com/a4lg/binutils-gdb/wiki/proj_dis_perf_improvements_1>

** this patchset does not apply to master directly. **

This patchset requires following patchset(s) to be applied first:
<https://sourceware.org/pipermail/binutils/2022-November/124378.html>
<https://sourceware.org/pipermail/binutils/2022-November/124519.html>

[Changes: v1 -> v2]
-   Rebased against commit 97f006bc56af:
    "RISC-V: Better support for long instructions (disassembler)"


Following is basically a copy from the PATCH 3/3 commit message.


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(m + n*log(n)) time on initialization where n < m),
-   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
in development:

-   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)


Thanks,
Tsukasa




Tsukasa OI (3):
  RISC-V: Easy optimization on riscv_search_mapping_symbol
  RISC-V: Per-section private data initialization
  RISC-V: Optimized search on mapping symbols

 opcodes/disassemble.c |   1 +
 opcodes/disassemble.h |   2 +
 opcodes/riscv-dis.c   | 443 +++++++++++++++++++++++++++++-------------
 3 files changed, 311 insertions(+), 135 deletions(-)


base-commit: 5b561967091a59d0052bd717d1b9f3e31ef841cc
-- 
2.38.1

[PATCH v2 1/3] RISC-V: Easy optimization on riscv_search_mapping_symbol

[Tsukasa OI]

From: Tsukasa OI <research_trasio@irq.a4lg.com>

Before further optimization, we can optimize the function
riscv_search_mapping_symbol a bit for clarity.

opcodes/ChangeLog:

	* riscv-dis.c (riscv_search_mapping_symbol): Make MAP_INSN default
	considering major usecases.  Remove setting found here as no one
	uses the value after setting this.  memaddr cannot be negative
	so simplify and change comment.

Idea-by: Nelson Chu <nelson@rivosinc.com>
---
 opcodes/riscv-dis.c | 13 +++++--------
 1 file changed, 5 insertions(+), 8 deletions(-)

diff --git a/opcodes/riscv-dis.c b/opcodes/riscv-dis.c
index eb3e64816bf6..bb7c03ad5fbf 100644
--- a/opcodes/riscv-dis.c
+++ b/opcodes/riscv-dis.c
@@ -1134,18 +1134,16 @@ riscv_search_mapping_symbol (bfd_vma memaddr,
 
   /* Decide whether to print the data or instruction by default, in case
      we can not find the corresponding mapping symbols.  */
-  mstate = MAP_DATA;
-  if ((info->section
-       && info->section->flags & SEC_CODE)
-      || !info->section)
-    mstate = MAP_INSN;
+  mstate = MAP_INSN;
+  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)
     return mstate;
 
-  /* Reset the last_map_symbol if we start to dump a new section.  */
-  if (memaddr <= 0)
+  /* 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
@@ -1197,7 +1195,6 @@ riscv_search_mapping_symbol (bfd_vma memaddr,
 	  if (riscv_get_map_state (n, &mstate, info, true))
 	    {
 	      symbol = n;
-	      found = true;
 	      break;
 	    }
 	}
-- 
2.38.1

[PATCH v2 2/3] RISC-V: Per-section private data initialization

[Tsukasa OI]

From: Tsukasa OI <research_trasio@irq.a4lg.com>

This is one more preparation for mapping symbol optimization.  It adds a
separate function that is called when the section to disassemble is changed.

This commit enables tracking per-section state management required for the
next optimization ("RISC-V: Optimized search on mapping symbols").

opcodes/ChangeLog:

	* riscv-dis.c (struct riscv_private_data): Add last_section.
	(init_riscv_dis_private_data): Initialize last_section.
	(init_riscv_dis_private_data_for_section): New function. update
	last_section here.
	(print_insn_riscv): Track section changes.
---
 opcodes/riscv-dis.c | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/opcodes/riscv-dis.c b/opcodes/riscv-dis.c
index bb7c03ad5fbf..ba9b16afeb46 100644
--- a/opcodes/riscv-dis.c
+++ b/opcodes/riscv-dis.c
@@ -89,6 +89,7 @@ struct riscv_private_data
   bfd_vma gp;
   bfd_vma print_addr;
   bfd_vma hi_addr[NGPR];
+  void* last_section;
   bool to_print_addr;
   bool has_gp;
 };
@@ -245,6 +246,7 @@ 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->last_section = NULL;
   pd->to_print_addr = false;
   pd->has_gp = false;
 
@@ -256,6 +258,15 @@ init_riscv_dis_private_data (struct disassemble_info *info)
       }
 }
 
+/* Initialize private data when the section to disassemble is changed.  */
+
+static void
+init_riscv_dis_private_data_for_section (struct disassemble_info *info)
+{
+  struct riscv_private_data *pd = info->private_data;
+  pd->last_section = info->section;
+}
+
 /* Update architecture for disassembler with its context.
    Call initialization functions if either:
    -  the architecture for current context is changed or
@@ -1312,7 +1323,13 @@ print_insn_riscv (bfd_vma memaddr, struct disassemble_info *info)
 
   /* Initialize the private data.  */
   if (info->private_data == NULL)
-    init_riscv_dis_private_data (info);
+    {
+      init_riscv_dis_private_data (info);
+      init_riscv_dis_private_data_for_section (info);
+    }
+  struct riscv_private_data *pd = info->private_data;
+  if (info->section != pd->last_section)
+    init_riscv_dis_private_data_for_section (info);
 
   /* Guess and update XLEN if we haven't determined it yet.  */
   if (xlen == 0)
-- 
2.38.1

[PATCH v2 3/3] RISC-V: Optimized search on mapping symbols

[Tsukasa OI]

From: Tsukasa OI <research_trasio@irq.a4lg.com>

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(m + n*log(n)) time on initialization where n < m),
-   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 ba9b16afeb46..56522c9aa270 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,
 \f
 
 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;
 }
 
@@ -1088,60 +1242,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.  */
@@ -1149,72 +1307,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;
 }
 
@@ -1226,25 +1351,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)
@@ -1335,6 +1454,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.  */
@@ -1357,6 +1477,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.  */
@@ -1368,7 +1512,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, packet, info);
+  /* Print, save the next expected address and return current size.  */
+  status = (*riscv_disassembler) (memaddr, insn, packet, info);
+  pd->expected_next_addr = memaddr + status;
+  return status;
 }
 
 disassembler_ftype
@@ -1423,6 +1570,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