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

5 files changed, 215 insertions, 31 deletions

diff --git a/lib/Makefile.am b/lib/Makefile.am
index b3bb929f..e324c18d 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -34,10 +34,11 @@ AM_CPPFLAGS += -I$(srcdir)/../libelf
 noinst_LIBRARIES = libeu.a
 
 libeu_a_SOURCES = xasprintf.c xstrdup.c xstrndup.c xmalloc.c next_prime.c \
-		  crc32.c crc32_file.c \
+		  crc32.c crc32_file.c eu-search.c \
 		  color.c error.c printversion.c
 
 noinst_HEADERS = fixedsizehash.h libeu.h system.h dynamicsizehash.h list.h \
 		 eu-config.h color.h printversion.h bpf.h \
-		 atomics.h stdatomic-fbsd.h dynamicsizehash_concurrent.h
+		 atomics.h stdatomic-fbsd.h dynamicsizehash_concurrent.h \
+		 eu-search.h locks.h
 EXTRA_DIST = dynamicsizehash.c dynamicsizehash_concurrent.c
diff --git a/lib/eu-config.h b/lib/eu-config.h
index feb079db..0bf2aa76 100644
--- a/lib/eu-config.h
+++ b/lib/eu-config.h
@@ -29,35 +29,7 @@
 #ifndef EU_CONFIG_H
 #define EU_CONFIG_H	1
 
-#ifdef USE_LOCKS
-# include <pthread.h>
-# include <assert.h>
-# define rwlock_define(class,name)	class pthread_rwlock_t name
-# define once_define(class,name)  class pthread_once_t name = PTHREAD_ONCE_INIT
-# define RWLOCK_CALL(call)		\
-  ({ int _err = pthread_rwlock_ ## call; assert_perror (_err); })
-# define ONCE_CALL(call)  \
-  ({ int _err = pthread_ ## call; assert_perror (_err); })
-# define rwlock_init(lock)		RWLOCK_CALL (init (&lock, NULL))
-# define rwlock_fini(lock)		RWLOCK_CALL (destroy (&lock))
-# define rwlock_rdlock(lock)		RWLOCK_CALL (rdlock (&lock))
-# define rwlock_wrlock(lock)		RWLOCK_CALL (wrlock (&lock))
-# define rwlock_unlock(lock)		RWLOCK_CALL (unlock (&lock))
-# define once(once_control, init_routine)  \
-  ONCE_CALL (once (&once_control, init_routine))
-#else
-/* Eventually we will allow multi-threaded applications to use the
-   libraries.  Therefore we will add the necessary locking although
-   the macros used expand to nothing for now.  */
-# define rwlock_define(class,name) class int name
-# define rwlock_init(lock) ((void) (lock))
-# define rwlock_fini(lock) ((void) (lock))
-# define rwlock_rdlock(lock) ((void) (lock))
-# define rwlock_wrlock(lock) ((void) (lock))
-# define rwlock_unlock(lock) ((void) (lock))
-# define once_define(class,name)
-# define once(once_control, init_routine)	init_routine()
-#endif	/* USE_LOCKS */
+#include "locks.h"
 
 #include <libintl.h>
 /* gettext helper macros.  */
diff --git a/lib/eu-search.c b/lib/eu-search.c
new file mode 100644
index 00000000..fc31fe87
--- /dev/null
+++ b/lib/eu-search.c
@@ -0,0 +1,85 @@
+/* Definitions for thread-safe tsearch/tfind
+   Copyright (C) 2023 Rice University
+   This file is part of elfutils.
+
+   This file is free software; you can redistribute it and/or modify
+   it under the terms of either
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at
+       your option) any later version
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at
+       your option) any later version
+
+   or both in parallel, as here.
+
+   elfutils is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see <http://www.gnu.org/licenses/>.  */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include "eu-search.h"
+
+void *eu_tsearch (const void *key, search_tree *tree,
+		  int (*compare)(const void *, const void *))
+{
+  rwlock_wrlock (tree->lock);
+  void *ret = tsearch (key, &tree->root, compare);
+  rwlock_unlock (tree->lock);
+
+  return ret;
+}
+
+void *eu_tfind (const void *key, search_tree *tree,
+	        int (*compare)(const void *, const void *))
+{
+  rwlock_rdlock (tree->lock);
+  void *ret = tfind (key, &tree->root, compare);
+  rwlock_unlock (tree->lock);
+
+  return ret;
+}
+
+void *eu_tdelete (const void *key, search_tree *tree,
+		  int (*compare)(const void *, const void *))
+{
+  rwlock_wrlock (tree->lock);
+  void *ret = tdelete (key, &tree->root, compare);
+  rwlock_unlock (tree->lock);
+
+  return ret;
+}
+
+void eu_tdestroy (search_tree *tree, void (*free_node)(void *))
+{
+  rwlock_wrlock (tree->lock);
+
+  tdestroy (tree->root, free_node);
+  tree->root = NULL;
+
+  rwlock_unlock (tree->lock);
+}
+
+void eu_search_tree_init (search_tree *tree)
+{
+  tree->root = NULL;
+  rwlock_init (tree->lock);
+}
+
+void eu_search_tree_fini (search_tree *tree, void (*free_node)(void *))
+{
+  eu_tdestroy (tree, free_node);
+  rwlock_fini (tree->lock);
+}
diff --git a/lib/eu-search.h b/lib/eu-search.h
new file mode 100644
index 00000000..67b54c18
--- /dev/null
+++ b/lib/eu-search.h
@@ -0,0 +1,64 @@
+/* Calls for thread-safe tsearch/tfind
+   Copyright (C) 2023 Rice University
+   This file is part of elfutils.
+
+   This file is free software; you can redistribute it and/or modify
+   it under the terms of either
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at
+       your option) any later version
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at
+       your option) any later version
+
+   or both in parallel, as here.
+
+   elfutils is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef EU_SEARCH_H
+#define EU_SEARCH_H 1
+
+#include <stdlib.h>
+#include <search.h>
+#include <locks.h>
+
+typedef struct
+{
+  void *root;
+  rwlock_define (, lock);
+} search_tree;
+
+/* Search TREE for KEY and add KEY if not found. Synchronized using
+   TREE's lock.  */
+extern void *eu_tsearch (const void *key, search_tree *tree,
+			 int (*compare)(const void *, const void *));
+
+/* Search TREE for KEY. Synchronized with TREE's lock.  */
+extern void *eu_tfind (const void *key, search_tree *tree,
+		       int (*compare)(const void *, const void *));
+
+/* Delete key from TREE. Synchronized with TREE's lock.  */
+extern void *eu_tdelete (const void *key, search_tree *tree,
+		         int (*compare)(const void *, const void *));
+
+/* Free all nodes from TREE.  */
+void eu_tdestroy (search_tree *tree, void (*free_node)(void *));
+
+/* Initialize TREE's root and lock.  */
+void eu_search_tree_init (search_tree *tree);
+
+/* Free all nodes from TREE as well as TREE's lock.  */
+void eu_search_tree_fini (search_tree *tree, void (*free_node)(void *));
+
+#endif
diff --git a/lib/locks.h b/lib/locks.h
new file mode 100644
index 00000000..90fe3f1b
--- /dev/null
+++ b/lib/locks.h
@@ -0,0 +1,62 @@
+/* Configuration definitions.
+   Copyright (C) 2024 Red Hat, Inc.
+   This file is part of elfutils.
+
+   This file is free software; you can redistribute it and/or modify
+   it under the terms of either
+
+     * the GNU Lesser General Public License as published by the Free
+       Software Foundation; either version 3 of the License, or (at
+       your option) any later version
+
+   or
+
+     * the GNU General Public License as published by the Free
+       Software Foundation; either version 2 of the License, or (at
+       your option) any later version
+
+   or both in parallel, as here.
+
+   elfutils is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received copies of the GNU General Public License and
+   the GNU Lesser General Public License along with this program.  If
+   not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef LOCKS_H
+#define LOCKS_H     1
+
+#ifdef USE_LOCKS
+# include <pthread.h>
+# include <assert.h>
+# define rwlock_define(class,name)      class pthread_rwlock_t name
+# define once_define(class,name)  class pthread_once_t name = PTHREAD_ONCE_INIT
+# define RWLOCK_CALL(call)              \
+  ({ int _err = pthread_rwlock_ ## call; assert_perror (_err); })
+# define ONCE_CALL(call)  \
+  ({ int _err = pthread_ ## call; assert_perror (_err); })
+# define rwlock_init(lock)              RWLOCK_CALL (init (&lock, NULL))
+# define rwlock_fini(lock)              RWLOCK_CALL (destroy (&lock))
+# define rwlock_rdlock(lock)            RWLOCK_CALL (rdlock (&lock))
+# define rwlock_wrlock(lock)            RWLOCK_CALL (wrlock (&lock))
+# define rwlock_unlock(lock)            RWLOCK_CALL (unlock (&lock))
+# define once(once_control, init_routine)  \
+  ONCE_CALL (once (&once_control, init_routine))
+#else
+/* Eventually we will allow multi-threaded applications to use the
+   libraries.  Therefore we will add the necessary locking although
+   the macros used expand to nothing for now.  */
+# define rwlock_define(class,name) class int name
+# define rwlock_init(lock) ((void) (lock))
+# define rwlock_fini(lock) ((void) (lock))
+# define rwlock_rdlock(lock) ((void) (lock))
+# define rwlock_wrlock(lock) ((void) (lock))
+# define rwlock_unlock(lock) ((void) (lock))
+# define once_define(class,name)
+# define once(once_control, init_routine)       init_routine()
+#endif  /* USE_LOCKS */
+
+#endif  /* locks.h */