From d6443d1a4df6057f9012d105037f52daaca911f1 Mon Sep 17 00:00:00 2001 From: Heather McIntyre Date: Fri, 12 Jul 2024 18:23:56 -0400 Subject: 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 Signed-off-by: Aaron Merey Signed-off-by: Mark Wielaard --- lib/Makefile.am | 5 ++-- lib/eu-config.h | 30 +------------------- lib/eu-search.c | 85 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/eu-search.h | 64 +++++++++++++++++++++++++++++++++++++++++++ lib/locks.h | 62 +++++++++++++++++++++++++++++++++++++++++ 5 files changed, 215 insertions(+), 31 deletions(-) create mode 100644 lib/eu-search.c create mode 100644 lib/eu-search.h create mode 100644 lib/locks.h (limited to 'lib') 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 -# include -# 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 /* 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 . */ + +#ifdef HAVE_CONFIG_H +#include +#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 . */ + +#ifndef EU_SEARCH_H +#define EU_SEARCH_H 1 + +#include +#include +#include + +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 . */ + +#ifndef LOCKS_H +#define LOCKS_H 1 + +#ifdef USE_LOCKS +# include +# include +# 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 */ -- cgit v1.2.3