lib: Add eu_tsearch, eu_tfind, eu_tdelete and eu_tdestroy

Add struct search_tree to hold tree root and lock.  Add new eu_t*
functions for ensuring synchronized tree access.

Replace tsearch, tfind, etc with eu_t* equivalents.

lib:
	* Makefile.am (libeu_a_SOURCES): Add eu-search.c.
	(noinst_HEADERS): Add eu-search.h and locks.h.
	* eu-config.h: Move rwlock macros to locks.h.
	* eu-search.c: New file containing tree search functions with
	  locking.
	* eu-search.h: New file.
	* locks.h: New file containing rwlock macros previously in
	  eu-config.h.
libdw:
	* cfi.h (struct Dwarf_CFI_s): Change type of search tree members
	  from void * to search_tree.
	* cie.c: Replace tree search functions with eu-search equivalents.
	* dwarf_begin_elf.c (valid_p): Initialize search trees.
	* dwarf_end.c (cu_free): Replace tree search functions
	  with eu-search equivalents.
	* dwarf_getcfi.c (dwarf_getcfi): Initialize search trees.
	* dwarf_getlocations.c: Replace search tree functions with
	  eu-search equivalents.
	  (__libdw_intern_expression): Change type of cache parameter to
	  search_tree *.
	* dwarf_getmacros.c: Replace tree search functions with
	  eu-search equivalents.
	* dwarf_getsrclines.c: Ditto.
	* fde.c: Ditto.
	* frame-cache.c (__libdw_destroy_frame_cache): Initialize search
	  trees.
	* libdwP.h (struct Dwarf): Change type of search tree members
	  from void * to search_tree.
	  (struct Dwarf_CU): Ditto.
	  (__libdw_intern_expression): Change type of cache parameter to
	  search_tree *.
	* libdw_find_split_unit.c: Replace tree search functions with
	  eu-search equivalents.
	* libdw_findcu.c: Ditto.
libdwfl:
	* cu.c: Ditto.
	* libdwflP.h (struct Dwfl_Module): Replace void *lazy_cu_root
	  with search_tree lazy_cu_tree.
libelf:
	* elf_begin.c (file_read_elf): Initialize rawchunck_tree.
	* elf_end.c (elf_end): Replace tree search function with
	  eu-search equivalent.
	* elf_getdata_rawchunck.c: Ditto.
	* libelfP.h (struct Elf): Replace void * rawchuncks member with
	search_tree rawchunk_tree.

Signed-off-by: Heather S. McIntyre <[email protected]>
Signed-off-by: Aaron Merey <[email protected]>
Signed-off-by: Mark Wielaard <[email protected]>

4 files changed, 22 insertions, 15 deletions

diff --git a/libelf/elf_begin.c b/libelf/elf_begin.c
index 8a49f351..2b3b465f 100644
--- a/libelf/elf_begin.c
+++ b/libelf/elf_begin.c
@@ -439,6 +439,7 @@ file_read_elf (int fildes, void *map_address, unsigned char *e_ident,
 
       /* So far only one block with sections.  */
       elf->state.elf32.scns_last = &elf->state.elf32.scns;
+      eu_search_tree_init (&elf->state.elf32.rawchunk_tree);
     }
   else
     {
@@ -536,6 +537,7 @@ file_read_elf (int fildes, void *map_address, unsigned char *e_ident,
 
       /* So far only one block with sections.  */
       elf->state.elf64.scns_last = &elf->state.elf64.scns;
+      eu_search_tree_init (&elf->state.elf64.rawchunk_tree);
     }
 
   return elf;
diff --git a/libelf/elf_end.c b/libelf/elf_end.c
index 80f4d13f..da8f3a20 100644
--- a/libelf/elf_end.c
+++ b/libelf/elf_end.c
@@ -126,13 +126,14 @@ elf_end (Elf *elf)
 
     case ELF_K_ELF:
       {
-	void *rawchunks
+	search_tree *rawchunk_tree
 	  = (elf->class == ELFCLASS32
-	     || (offsetof (struct Elf, state.elf32.rawchunks)
-		 == offsetof (struct Elf, state.elf64.rawchunks))
-	     ? elf->state.elf32.rawchunks
-	     : elf->state.elf64.rawchunks);
-	tdestroy (rawchunks, free_chunk);
+	     || (offsetof (struct Elf, state.elf32.rawchunk_tree)
+		 == offsetof (struct Elf, state.elf64.rawchunk_tree))
+	     ? &elf->state.elf32.rawchunk_tree
+	     : &elf->state.elf64.rawchunk_tree);
+
+	eu_search_tree_fini (rawchunk_tree, free_chunk);
 
 	Elf_ScnList *list = (elf->class == ELFCLASS32
 			     || (offsetof (struct Elf, state.elf32.scns)
diff --git a/libelf/elf_getdata_rawchunk.c b/libelf/elf_getdata_rawchunk.c
index 1751878d..010fac90 100644
--- a/libelf/elf_getdata_rawchunk.c
+++ b/libelf/elf_getdata_rawchunk.c
@@ -33,12 +33,11 @@
 
 #include <assert.h>
 #include <errno.h>
-#include <search.h>
-#include <stdlib.h>
 #include <string.h>
 
 #include "libelfP.h"
 #include "common.h"
+#include "eu-search.h"
 
 static int
 chunk_compare (const void *a, const void *b)
@@ -95,8 +94,9 @@ elf_getdata_rawchunk (Elf *elf, int64_t offset, size_t size, Elf_Type type)
   key.offset = offset;
   key.data.d.d_size = size;
   key.data.d.d_type = type;
-  Elf_Data_Chunk **found = tsearch (&key, &elf->state.elf.rawchunks,
-				    &chunk_compare);
+  Elf_Data_Chunk **found
+    = eu_tsearch (&key, &elf->state.elf.rawchunk_tree, &chunk_compare);
+
   if (found == NULL)
     goto nomem;
 
@@ -136,7 +136,7 @@ elf_getdata_rawchunk (Elf *elf, int64_t offset, size_t size, Elf_Type type)
       if (rawchunk == NULL)
 	{
 	nomem:
-	  tdelete (&key, &elf->state.elf.rawchunks, &chunk_compare);
+	  eu_tdelete (&key, &elf->state.elf.rawchunk_tree, &chunk_compare);
 	  __libelf_seterrno (ELF_E_NOMEM);
 	  goto out;
 	}
@@ -147,7 +147,7 @@ elf_getdata_rawchunk (Elf *elf, int64_t offset, size_t size, Elf_Type type)
 		    != size))
 	{
 	  /* Something went wrong.  */
-	  tdelete (&key, &elf->state.elf.rawchunks, &chunk_compare);
+	  eu_tdelete (&key, &elf->state.elf.rawchunk_tree, &chunk_compare);
 	  free (rawchunk);
 	  __libelf_seterrno (ELF_E_READ_ERROR);
 	  goto out;
diff --git a/libelf/libelfP.h b/libelf/libelfP.h
index bdd2cc6a..a9213ab3 100644
--- a/libelf/libelfP.h
+++ b/libelf/libelfP.h
@@ -33,6 +33,7 @@
 
 #include <ar.h>
 #include <gelf.h>
+#include "eu-search.h"
 
 #include <errno.h>
 #include <stdbool.h>
@@ -323,7 +324,8 @@ struct Elf
       Elf_ScnList *scns_last;	/* Last element in the section list.
 				   If NULL the data has not yet been
 				   read from the file.  */
-      void *rawchunks;		/* Tree of elf_getdata_rawchunk results.  */
+      search_tree rawchunk_tree;  /* Tree and lock for elf_getdata_rawchunk
+				     results.  */
       unsigned int scnincr;	/* Number of sections allocate the last
 				   time.  */
       int ehdr_flags;		/* Flags (dirty) for ELF header.  */
@@ -342,7 +344,8 @@ struct Elf
       Elf_ScnList *scns_last;	/* Last element in the section list.
 				   If NULL the data has not yet been
 				   read from the file.  */
-      void *rawchunks;		/* Tree of elf_getdata_rawchunk results.  */
+      search_tree rawchunk_tree;  /* Tree and lock for
+				     elf_getdata_rawchunk results.  */
       unsigned int scnincr;	/* Number of sections allocate the last
 				   time.  */
       int ehdr_flags;		/* Flags (dirty) for ELF header.  */
@@ -367,7 +370,8 @@ struct Elf
       Elf_ScnList *scns_last;	/* Last element in the section list.
 				   If NULL the data has not yet been
 				   read from the file.  */
-      void *rawchunks;		/* Tree of elf_getdata_rawchunk results.  */
+      search_tree rawchunk_tree;  /* Tree and lock for
+				     elf_getdata_rawchunk results.  */
       unsigned int scnincr;	/* Number of sections allocate the last
 				   time.  */
       int ehdr_flags;		/* Flags (dirty) for ELF header.  */