[3/9,v2] lib: Add eu_tsearch, eu_tfind, eu_tdelete and eu_tdestroy
Commit Message
From: Heather McIntyre <hsm2@rice.edu>
Add new 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.
Move the rwlock_* macros out of eu-config.h and into a new header file
locks.h. This was done so that the rwlock_* macros can be included
in libdwP.h without having to also include the rest of eu-config.h.
Signed-off-by: Heather S. McIntyre <hsm2@rice.edu>
Signed-off-by: Aaron Merey <amerey@redhat.com>
Signed-off-by: Mark Wielaard <mark@klomp.org>
v2 changes:
This patch replaces v1 03/16 and 14/16.
---
lib/Makefile.am | 5 ++-
lib/eu-config.h | 30 +------------
lib/eu-search.c | 85 +++++++++++++++++++++++++++++++++++
lib/eu-search.h | 64 ++++++++++++++++++++++++++
lib/locks.h | 62 +++++++++++++++++++++++++
libdw/cfi.h | 6 +--
libdw/cie.c | 10 +++--
libdw/dwarf_begin_elf.c | 7 +--
libdw/dwarf_end.c | 17 +++----
libdw/dwarf_getcfi.c | 5 ++-
libdw/dwarf_getlocation.c | 24 +++++-----
libdw/dwarf_getmacros.c | 6 +--
libdw/dwarf_getsrclines.c | 8 ++--
libdw/fde.c | 6 +--
libdw/frame-cache.c | 8 ++--
libdw/libdwP.h | 26 ++++++++---
libdw/libdw_find_split_unit.c | 10 ++---
libdw/libdw_findcu.c | 18 ++++----
libdwfl/cu.c | 8 ++--
libdwfl/dwfl_module.c | 4 +-
libdwfl/libdwflP.h | 3 +-
libelf/elf_begin.c | 2 +
libelf/elf_end.c | 13 +++---
libelf/elf_getdata_rawchunk.c | 12 ++---
libelf/libelfP.h | 10 +++--
25 files changed, 331 insertions(+), 118 deletions(-)
create mode 100644 lib/eu-search.c
create mode 100644 lib/eu-search.h
create mode 100644 lib/locks.h
Comments
Hi,
On Wed, 2024-07-17 at 18:34 -0400, Aaron Merey wrote:
> From: Heather McIntyre <hsm2@rice.edu>
>
> Add new 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.
>
> Move the rwlock_* macros out of eu-config.h and into a new header file
> locks.h. This was done so that the rwlock_* macros can be included
> in libdwP.h without having to also include the rest of eu-config.h.
>
> Signed-off-by: Heather S. McIntyre <hsm2@rice.edu>
> Signed-off-by: Aaron Merey <amerey@redhat.com>
> Signed-off-by: Mark Wielaard <mark@klomp.org>
>
> v2 changes:
>
> This patch replaces v1 03/16 and 14/16.
In this case I missed a ChangeLog entry which would have helped knowing
which changes were deliberate.
In general this looks good. Mostly the same "style" comment that local
includes should use #include "lock.h", not <lock.h> (we aren't totally
consistent here and the <> variant does work).
Besides the new search_tree (which includes a lock object) it does seem
to introduce various locks that aren't used in the rest of code. It
would be better to introduce them in a later patch were those are
actually used.
> ---
> lib/Makefile.am | 5 ++-
> lib/eu-config.h | 30 +------------
> lib/eu-search.c | 85 +++++++++++++++++++++++++++++++++++
> lib/eu-search.h | 64 ++++++++++++++++++++++++++
> lib/locks.h | 62 +++++++++++++++++++++++++
> libdw/cfi.h | 6 +--
> libdw/cie.c | 10 +++--
> libdw/dwarf_begin_elf.c | 7 +--
> libdw/dwarf_end.c | 17 +++----
> libdw/dwarf_getcfi.c | 5 ++-
> libdw/dwarf_getlocation.c | 24 +++++-----
> libdw/dwarf_getmacros.c | 6 +--
> libdw/dwarf_getsrclines.c | 8 ++--
> libdw/fde.c | 6 +--
> libdw/frame-cache.c | 8 ++--
> libdw/libdwP.h | 26 ++++++++---
> libdw/libdw_find_split_unit.c | 10 ++---
> libdw/libdw_findcu.c | 18 ++++----
> libdwfl/cu.c | 8 ++--
> libdwfl/dwfl_module.c | 4 +-
> libdwfl/libdwflP.h | 3 +-
> libelf/elf_begin.c | 2 +
> libelf/elf_end.c | 13 +++---
> libelf/elf_getdata_rawchunk.c | 12 ++---
> libelf/libelfP.h | 10 +++--
> 25 files changed, 331 insertions(+), 118 deletions(-)
> create mode 100644 lib/eu-search.c
> create mode 100644 lib/eu-search.h
> create mode 100644 lib/locks.h
>
> 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
OK.
> diff --git a/lib/eu-config.h b/lib/eu-config.h
> index feb079db..a38d75da 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. */
OK, move to locks.h. But please use #include "locks.h" to make clear
this is a local include file, not some global one.
> diff --git a/lib/eu-search.c b/lib/eu-search.c
> new file mode 100644
> index 00000000..b7256eba
> --- /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>
Please use #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);
> +}
Looks good.
> 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>
#include "locks.h"
(stdlib.h and search.h are fine since those are global).
> +typedef struct
> +{
> + void *root;
> + rwlock_define (, lock);
> +} search_tree;
OK. I did have to lookup what the "missing" relock_define argument was
(it is so you can add static, but that isn't necessary here).
> +/* 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
OK.
Is eu_tdestroy ever used now?
It looks like everything now uses eu_search_tree_fine.
Could still be a useful function to have, just checking.
> 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>
Why the assert.h 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 */
OK, moved from eu-config.h
> diff --git a/libdw/cfi.h b/libdw/cfi.h
> index 1b0d712f..bb9dc0df 100644
> --- a/libdw/cfi.h
> +++ b/libdw/cfi.h
> @@ -90,13 +90,13 @@ struct Dwarf_CFI_s
> Dwarf_Off next_offset;
>
> /* Search tree for the CIEs, indexed by CIE_pointer (section offset). */
> - void *cie_tree;
> + search_tree cie_tree;
>
> /* Search tree for the FDEs, indexed by PC address. */
> - void *fde_tree;
> + search_tree fde_tree;
>
> /* Search tree for parsed DWARF expressions, indexed by raw pointer. */
> - void *expr_tree;
> + search_tree expr_tree;
>
> /* Backend hook. */
> struct ebl *ebl;
OK, nice to have a proper type for this now.
> diff --git a/libdw/cie.c b/libdw/cie.c
> index 1b0aae7c..3d56b057 100644
> --- a/libdw/cie.c
> +++ b/libdw/cie.c
> @@ -33,7 +33,7 @@
> #include "cfi.h"
> #include "encoded-value.h"
> #include <assert.h>
> -#include <search.h>
> +#include <eu-search.h>
> #include <stdlib.h>
>
Please use #include "eu-search.h" (and maybe move it at the end after
the system headers, although we aren't very consistent doing that).
> @@ -144,7 +144,7 @@ intern_new_cie (Dwarf_CFI *cache, Dwarf_Off offset, const Dwarf_CIE *info)
> cie->initial_state = NULL;
>
> /* Add the new entry to the search tree. */
> - if (tsearch (cie, &cache->cie_tree, &compare_cie) == NULL)
> + if (eu_tsearch (cie, &cache->cie_tree, &compare_cie) == NULL)
> {
> free (cie);
> __libdw_seterrno (DWARF_E_NOMEM);
> @@ -160,7 +160,8 @@ internal_function
> __libdw_find_cie (Dwarf_CFI *cache, Dwarf_Off offset)
> {
> const struct dwarf_cie cie_key = { .offset = offset };
> - struct dwarf_cie **found = tfind (&cie_key, &cache->cie_tree, &compare_cie);
> + struct dwarf_cie **found = eu_tfind (&cie_key, &cache->cie_tree,
> + &compare_cie);
> if (found != NULL)
> return *found;
>
> @@ -189,7 +190,8 @@ internal_function
> __libdw_intern_cie (Dwarf_CFI *cache, Dwarf_Off offset, const Dwarf_CIE *info)
> {
> const struct dwarf_cie cie_key = { .offset = offset };
> - struct dwarf_cie **found = tfind (&cie_key, &cache->cie_tree, &compare_cie);
> + struct dwarf_cie **found = eu_tfind (&cie_key, &cache->cie_tree,
> + &compare_cie);
> if (found == NULL)
> /* We have not read this CIE yet. Enter it. */
> (void) intern_new_cie (cache, offset, info);
OK.
> diff --git a/libdw/dwarf_begin_elf.c b/libdw/dwarf_begin_elf.c
> index ca2b7e2a..56abef6a 100644
> --- a/libdw/dwarf_begin_elf.c
> +++ b/libdw/dwarf_begin_elf.c
> @@ -354,11 +354,11 @@ valid_p (Dwarf *result)
> result->fake_loc_cu->endp
> = (result->sectiondata[IDX_debug_loc]->d_buf
> + result->sectiondata[IDX_debug_loc]->d_size);
> - result->fake_loc_cu->locs = NULL;
> result->fake_loc_cu->address_size = elf_addr_size;
> result->fake_loc_cu->offset_size = 4;
> result->fake_loc_cu->version = 4;
> result->fake_loc_cu->split = NULL;
> + eu_search_tree_init (&result->fake_loc_cu->locs_tree);
> }
> }
>
> @@ -382,11 +382,11 @@ valid_p (Dwarf *result)
> result->fake_loclists_cu->endp
> = (result->sectiondata[IDX_debug_loclists]->d_buf
> + result->sectiondata[IDX_debug_loclists]->d_size);
> - result->fake_loclists_cu->locs = NULL;
> result->fake_loclists_cu->address_size = elf_addr_size;
> result->fake_loclists_cu->offset_size = 4;
> result->fake_loclists_cu->version = 5;
> result->fake_loclists_cu->split = NULL;
> + eu_search_tree_init (&result->fake_loclists_cu->locs_tree);
> }
> }
>
> @@ -415,11 +415,11 @@ valid_p (Dwarf *result)
> result->fake_addr_cu->endp
> = (result->sectiondata[IDX_debug_addr]->d_buf
> + result->sectiondata[IDX_debug_addr]->d_size);
> - result->fake_addr_cu->locs = NULL;
> result->fake_addr_cu->address_size = elf_addr_size;
> result->fake_addr_cu->offset_size = 4;
> result->fake_addr_cu->version = 5;
> result->fake_addr_cu->split = NULL;
> + eu_search_tree_init (&result->fake_addr_cu->locs_tree);
> }
> }
OK, the locs are renamed to locs_tree and should now be inited instead
of NULLed.
> @@ -579,6 +579,7 @@ dwarf_begin_elf (Elf *elf, Dwarf_Cmd cmd, Elf_Scn *scngrp)
> __libdw_seterrno (DWARF_E_NOMEM); /* no memory. */
> return NULL;
> }
> + rwlock_init(result->dwarf_lock);
> result->mem_stacks = 0;
> result->mem_tails = NULL;
What is this doing here?
> diff --git a/libdw/dwarf_end.c b/libdw/dwarf_end.c
> index ed8d27be..a593c881 100644
> --- a/libdw/dwarf_end.c
> +++ b/libdw/dwarf_end.c
> @@ -61,14 +61,15 @@ static void
> cu_free (void *arg)
> {
> struct Dwarf_CU *p = (struct Dwarf_CU *) arg;
> -
> - tdestroy (p->locs, noop_free);
> + eu_search_tree_fini (&p->locs_tree, noop_free);
OK.
> /* Only free the CU internals if its not a fake CU. */
> - if(p != p->dbg->fake_loc_cu && p != p->dbg->fake_loclists_cu
> + if (p != p->dbg->fake_loc_cu && p != p->dbg->fake_loclists_cu
> && p != p->dbg->fake_addr_cu)
> {
> Dwarf_Abbrev_Hash_free (&p->abbrev_hash);
> + rwlock_fini (p->abbrev_lock);
> + rwlock_fini (p->split_lock);
>
Why?
>
> /* Free split dwarf one way (from skeleton to split). */
> if (p->unit_type == DW_UT_skeleton
> @@ -102,17 +103,17 @@ dwarf_end (Dwarf *dwarf)
> /* The search tree for the CUs. NB: the CU data itself is
> allocated separately, but the abbreviation hash tables need
> to be handled. */
> - tdestroy (dwarf->cu_tree, cu_free);
> - tdestroy (dwarf->tu_tree, cu_free);
> + eu_search_tree_fini (&dwarf->cu_tree, cu_free);
> + eu_search_tree_fini (&dwarf->tu_tree, cu_free);
>
> /* Search tree for macro opcode tables. */
> - tdestroy (dwarf->macro_ops, noop_free);
> + eu_search_tree_fini (&dwarf->macro_ops_tree, noop_free);
>
> /* Search tree for decoded .debug_lines units. */
> - tdestroy (dwarf->files_lines, noop_free);
> + eu_search_tree_fini (&dwarf->files_lines_tree, noop_free);
>
> /* And the split Dwarf. */
> - tdestroy (dwarf->split_tree, noop_free);
> + eu_search_tree_fini (&dwarf->split_tree, noop_free);
>
> /* Free the internally allocated memory. */
> for (size_t i = 0; i < dwarf->mem_stacks; i++)
OK, replace tdestroy with eu_search_tree_fini.
> diff --git a/libdw/dwarf_getcfi.c b/libdw/dwarf_getcfi.c
> index afa8a460..a4497152 100644
> --- a/libdw/dwarf_getcfi.c
> +++ b/libdw/dwarf_getcfi.c
> @@ -66,7 +66,10 @@ dwarf_getcfi (Dwarf *dbg)
> cfi->default_same_value = false;
>
> cfi->next_offset = 0;
> - cfi->cie_tree = cfi->fde_tree = cfi->expr_tree = NULL;
> +
> + eu_search_tree_init (&cfi->cie_tree);
> + eu_search_tree_init (&cfi->fde_tree);
> + eu_search_tree_init (&cfi->expr_tree);
>
> cfi->ebl = NULL;
>
OK, replace NULL init with eu_search_tree_init.
>
> diff --git a/libdw/dwarf_getlocation.c b/libdw/dwarf_getlocation.c
> index 37b32fc1..409bda6f 100644
> --- a/libdw/dwarf_getlocation.c
> +++ b/libdw/dwarf_getlocation.c
> @@ -31,10 +31,11 @@
> #endif
>
> #include <dwarf.h>
> -#include <search.h>
> +#include <eu-search.h>
> #include <stdlib.h>
> #include <assert.h>
Please use #include "eu-search.h" here (and <dwarf.h> is not really
consistent already).
> +#include <cfi.h>
> #include <libdwP.h>
>
Why do we need cfi.h here?
>
> @@ -137,9 +138,9 @@ loc_compare (const void *p1, const void *p2)
>
> /* For each DW_OP_implicit_value, we store a special entry in the cache.
> This points us directly to the block data for later fetching.
> - Returns zero on success, -1 on bad DWARF or 1 if tsearch failed. */
> + Returns zero on success, -1 on bad DWARF or 1 if eu_tsearch failed. */
> static int
> -store_implicit_value (Dwarf *dbg, void **cache, Dwarf_Op *op)
> +store_implicit_value (Dwarf *dbg, search_tree *cache, Dwarf_Op *op)
> {
> if (dbg == NULL)
> return -1;
> @@ -154,7 +155,7 @@ store_implicit_value (Dwarf *dbg, void **cache, Dwarf_Op *op)
> block->addr = op;
> block->data = (unsigned char *) data;
> block->length = op->number;
> - if (unlikely (tsearch (block, cache, loc_compare) == NULL))
> + if (unlikely (eu_tsearch (block, cache, loc_compare) == NULL))
> return 1;
> return 0;
> }
OK, the cache search tree comes from __libdw_intern_expression and is
either a cfi cache expr_tree or a cu locs_tree.
> @@ -167,7 +168,8 @@ dwarf_getlocation_implicit_value (Dwarf_Attribute *attr, const Dwarf_Op *op,
> return -1;
>
> struct loc_block_s fake = { .addr = (void *) op };
> - struct loc_block_s **found = tfind (&fake, &attr->cu->locs, loc_compare);
> + struct loc_block_s **found = eu_tfind (&fake, &attr->cu->locs_tree,
> + loc_compare);
> if (unlikely (found == NULL))
> {
> __libdw_seterrno (DWARF_E_NO_BLOCK);
> @@ -211,7 +213,7 @@ is_constant_offset (Dwarf_Attribute *attr,
>
> /* Check whether we already cached this location. */
> struct loc_s fake = { .addr = attr->valp };
> - struct loc_s **found = tfind (&fake, &attr->cu->locs, loc_compare);
> + struct loc_s **found = eu_tfind (&fake, &attr->cu->locs_tree, loc_compare);
>
> if (found == NULL)
> {
> @@ -235,7 +237,7 @@ is_constant_offset (Dwarf_Attribute *attr,
> newp->loc = result;
> newp->nloc = 1;
>
> - found = tsearch (newp, &attr->cu->locs, loc_compare);
> + found = eu_tsearch (newp, &attr->cu->locs_tree, loc_compare);
> }
>
> assert ((*found)->nloc == 1);
OK.
> @@ -253,7 +255,7 @@ int
> internal_function
> __libdw_intern_expression (Dwarf *dbg, bool other_byte_order,
> unsigned int address_size, unsigned int ref_size,
> - void **cache, const Dwarf_Block *block,
> + search_tree *cache, const Dwarf_Block *block,
> bool cfap, bool valuep,
> Dwarf_Op **llbuf, size_t *listlen, int sec_index)
> {
OK, cache is as above (in store_implicit_value).
> @@ -266,7 +268,7 @@ __libdw_intern_expression (Dwarf *dbg, bool other_byte_order,
>
> /* Check whether we already looked at this list. */
> struct loc_s fake = { .addr = block->data };
> - struct loc_s **found = tfind (&fake, cache, loc_compare);
> + struct loc_s **found = eu_tfind (&fake, cache, loc_compare);
> if (found != NULL)
> {
> /* We already saw it. */
> @@ -655,7 +657,7 @@ __libdw_intern_expression (Dwarf *dbg, bool other_byte_order,
> newp->addr = block->data;
> newp->loc = result;
> newp->nloc = *listlen;
> - (void) tsearch (newp, cache, loc_compare);
> + eu_tsearch (newp, cache, loc_compare);
>
> /* We did it. */
> return 0;
OK.
> @@ -677,7 +679,7 @@ getlocation (struct Dwarf_CU *cu, const Dwarf_Block *block,
> cu->address_size, (cu->version == 2
> ? cu->address_size
> : cu->offset_size),
> - &cu->locs, block,
> + &cu->locs_tree, block,
> false, false,
> llbuf, listlen, sec_index);
> }
OK.
> diff --git a/libdw/dwarf_getmacros.c b/libdw/dwarf_getmacros.c
> index 2667eb45..41d510a9 100644
> --- a/libdw/dwarf_getmacros.c
> +++ b/libdw/dwarf_getmacros.c
> @@ -32,7 +32,7 @@
>
> #include <assert.h>
> #include <dwarf.h>
> -#include <search.h>
> +#include <eu-search.h>
> #include <stdlib.h>
> #include <string.h>
Please use #include "eu-search" (and see comment about dwarf.h above).
> @@ -317,7 +317,7 @@ cache_op_table (Dwarf *dbg, int sec_index, Dwarf_Off macoff,
> Dwarf_Die *cudie)
> {
> Dwarf_Macro_Op_Table fake = { .offset = macoff, .sec_index = sec_index };
> - Dwarf_Macro_Op_Table **found = tfind (&fake, &dbg->macro_ops,
> + Dwarf_Macro_Op_Table **found = eu_tfind (&fake, &dbg->macro_ops_tree,
> macro_op_compare);
> if (found != NULL)
> return *found;
> @@ -329,7 +329,7 @@ cache_op_table (Dwarf *dbg, int sec_index, Dwarf_Off macoff,
> if (table == NULL)
> return NULL;
>
> - Dwarf_Macro_Op_Table **ret = tsearch (table, &dbg->macro_ops,
> + Dwarf_Macro_Op_Table **ret = eu_tsearch (table, &dbg->macro_ops_tree,
> macro_op_compare);
> if (unlikely (ret == NULL))
> {
OK.
> diff --git a/libdw/dwarf_getsrclines.c b/libdw/dwarf_getsrclines.c
> index 987a86fd..759b9c7b 100644
> --- a/libdw/dwarf_getsrclines.c
> +++ b/libdw/dwarf_getsrclines.c
> @@ -33,7 +33,7 @@
> #include <assert.h>
> #include <stdlib.h>
> #include <string.h>
> -#include <search.h>
> +#include <eu-search.h>
Please use #include "eu-search.h"
> #include "dwarf.h"
> #include "libdwP.h"
> @@ -1320,8 +1320,8 @@ get_lines_or_files (Dwarf *dbg, Dwarf_Off debug_line_offset,
> Dwarf_Lines **linesp, Dwarf_Files **filesp)
> {
> struct files_lines_s fake = { .debug_line_offset = debug_line_offset };
> - struct files_lines_s **found = tfind (&fake, &dbg->files_lines,
> - files_lines_compare);
> + struct files_lines_s **found = eu_tfind (&fake, &dbg->files_lines_tree,
> + files_lines_compare);
> if (found == NULL)
> {
> /* This .debug_line is being read for the first time. */
> @@ -1354,7 +1354,7 @@ get_lines_or_files (Dwarf *dbg, Dwarf_Off debug_line_offset,
>
> node->debug_line_offset = debug_line_offset;
>
> - found = tsearch (node, &dbg->files_lines, files_lines_compare);
> + found = eu_tsearch (node, &dbg->files_lines_tree, files_lines_compare);
> if (found == NULL)
> {
> __libdw_seterrno (DWARF_E_NOMEM);
OK.
> diff --git a/libdw/fde.c b/libdw/fde.c
> index 73d551b6..55065528 100644
> --- a/libdw/fde.c
> +++ b/libdw/fde.c
> @@ -31,7 +31,7 @@
> #endif
>
> #include "cfi.h"
> -#include <search.h>
> +#include <eu-search.h>
> #include <stdlib.h>
Please use #include "eu-search.h"
> #include "encoded-value.h"
> @@ -122,7 +122,7 @@ intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry)
> fde->instructions += cie->fde_augmentation_data_size;
>
> /* Add the new entry to the search tree. */
> - struct dwarf_fde **tres = tsearch (fde, &cache->fde_tree, &compare_fde);
> + struct dwarf_fde **tres = eu_tsearch (fde, &cache->fde_tree, &compare_fde);
> if (tres == NULL)
> {
> free (fde);
> @@ -252,7 +252,7 @@ __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
> /* Look for a cached FDE covering this address. */
>
> const struct dwarf_fde fde_key = { .start = address, .end = 0 };
> - struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde);
> + struct dwarf_fde **found = eu_tfind (&fde_key, &cache->fde_tree, &compare_fde);
> if (found != NULL)
> return *found;
>
OK.
> diff --git a/libdw/frame-cache.c b/libdw/frame-cache.c
> index 683f7f17..6c89858a 100644
> --- a/libdw/frame-cache.c
> +++ b/libdw/frame-cache.c
> @@ -60,10 +60,10 @@ void
> internal_function
> __libdw_destroy_frame_cache (Dwarf_CFI *cache)
> {
> - /* Most of the data is in our two search trees. */
> - tdestroy (cache->fde_tree, free_fde);
> - tdestroy (cache->cie_tree, free_cie);
> - tdestroy (cache->expr_tree, free_expr);
> + /* Most of the data is in our three search trees. */
> + eu_search_tree_fini (&cache->fde_tree, free_fde);
> + eu_search_tree_fini (&cache->cie_tree, free_cie);
> + eu_search_tree_fini (&cache->expr_tree, free_expr);
>
> if (cache->ebl != NULL && cache->ebl != (void *) -1l)
> ebl_closebackend (cache->ebl);
OK.
> diff --git a/libdw/libdwP.h b/libdw/libdwP.h
> index e55ff50a..a4f26b82 100644
> --- a/libdw/libdwP.h
> +++ b/libdw/libdwP.h
> @@ -32,6 +32,7 @@
> #include <stdbool.h>
> #include <pthread.h>
>
> +#include <eu-search.h>
> #include <libdw.h>
> #include <dwarf.h>
Please use "" variants here
(I know it was already inconsistent, sorry)
> @@ -215,22 +216,22 @@ struct Dwarf
> size_t pubnames_nsets;
>
> /* Search tree for the CUs. */
> - void *cu_tree;
> + search_tree cu_tree;
> Dwarf_Off next_cu_offset;
>
> /* Search tree and sig8 hash table for .debug_types type units. */
> - void *tu_tree;
> + search_tree tu_tree;
> Dwarf_Off next_tu_offset;
> Dwarf_Sig8_Hash sig8_hash;
>
> /* Search tree for split Dwarf associated with CUs in this debug. */
> - void *split_tree;
> + search_tree split_tree;
>
> /* Search tree for .debug_macro operator tables. */
> - void *macro_ops;
> + search_tree macro_ops_tree;
>
> /* Search tree for decoded .debug_line units. */
> - void *files_lines;
> + search_tree files_lines_tree;
>
> /* Address ranges read from .debug_aranges. */
> Dwarf_Aranges *aranges;
OK.
> @@ -263,6 +264,10 @@ struct Dwarf
> allocations for this Dwarf. */
> pthread_rwlock_t mem_rwl;
>
> + /* The dwarf_lock is a read-write lock designed to ensure thread-safe access
> + and modification of Dwarf objects. */
> + rwlock_define(, dwarf_lock);
What is this doing here (in this patch?)
> /* Internal memory handling. This is basically a simplified thread-local
> reimplementation of obstacks. Unfortunately the standard obstack
> implementation is not usable in libraries. */
> @@ -423,7 +428,7 @@ struct Dwarf_CU
> Dwarf_Files *files;
>
> /* Known location lists. */
> - void *locs;
> + search_tree locs_tree;
>
> /* Base address for use with ranges and locs.
> Don't access directly, call __libdw_cu_base_address. */
OK.
> @@ -446,6 +451,12 @@ struct Dwarf_CU
> Don't access directly, call __libdw_cu_locs_base. */
> Dwarf_Off locs_base;
>
> + /* Synchronize Dwarf_Die abbrev access. */
> + rwlock_define(, abbrev_lock);
> +
> + /* Synchronize split Dwarf access. */
> + rwlock_define(, split_lock);
> +
> /* Memory boundaries of this CU. */
> void *startp;
> void *endp;
What are these doing here (in this patch?)
> @@ -912,7 +923,8 @@ extern int __libdw_intern_expression (Dwarf *dbg,
> bool other_byte_order,
> unsigned int address_size,
> unsigned int ref_size,
> - void **cache, const Dwarf_Block *block,
> + search_tree *cache,
> + const Dwarf_Block *block,
> bool cfap, bool valuep,
> Dwarf_Op **llbuf, size_t *listlen,
> int sec_index)
OK. Nice to have a proper type for the cache.
> diff --git a/libdw/libdw_find_split_unit.c b/libdw/libdw_find_split_unit.c
> index 8426a925..67d31a9c 100644
> --- a/libdw/libdw_find_split_unit.c
> +++ b/libdw/libdw_find_split_unit.c
> @@ -34,7 +34,7 @@
> #include "libelfP.h"
>
> #include <limits.h>
> -#include <search.h>
> +#include <eu-search.h>
> #include <stdlib.h>
> #include <string.h>
> #include <sys/types.h>
Please use "eu-search.h".
> @@ -57,8 +57,8 @@ try_split_file (Dwarf_CU *cu, const char *dwo_path)
> if (split->unit_type == DW_UT_split_compile
> && cu->unit_id8 == split->unit_id8)
> {
> - if (tsearch (split->dbg, &cu->dbg->split_tree,
> - __libdw_finddbg_cb) == NULL)
> + if (eu_tsearch (split->dbg, &cu->dbg->split_tree,
> + __libdw_finddbg_cb) == NULL)
> {
> /* Something went wrong. Don't link. */
> __libdw_seterrno (DWARF_E_NOMEM);
> @@ -132,8 +132,8 @@ try_dwp_file (Dwarf_CU *cu)
> cu->unit_id8);
> if (split != NULL)
> {
> - if (tsearch (split->dbg, &cu->dbg->split_tree,
> - __libdw_finddbg_cb) == NULL)
> + if (eu_tsearch (split->dbg, &cu->dbg->split_tree,
> + __libdw_finddbg_cb) == NULL)
> {
> /* Something went wrong. Don't link. */
> __libdw_seterrno (DWARF_E_NOMEM);
OK.
> diff --git a/libdw/libdw_findcu.c b/libdw/libdw_findcu.c
> index 6c7dcfb5..72cf261c 100644
> --- a/libdw/libdw_findcu.c
> +++ b/libdw/libdw_findcu.c
> @@ -32,7 +32,7 @@
> #endif
>
> #include <assert.h>
> -#include <search.h>
> +#include <eu-search.h>
> #include "libdwP.h"
Please use #include "eu-search.h".
> static int
> @@ -101,7 +101,7 @@ __libdw_intern_next_unit (Dwarf *dbg, bool debug_types)
> {
> Dwarf_Off *const offsetp
> = debug_types ? &dbg->next_tu_offset : &dbg->next_cu_offset;
> - void **tree = debug_types ? &dbg->tu_tree : &dbg->cu_tree;
> + search_tree *tree = debug_types ? &dbg->tu_tree : &dbg->cu_tree;
>
> Dwarf_Off oldoff = *offsetp;
> uint16_t version;
OK.
> @@ -167,7 +167,6 @@ __libdw_intern_next_unit (Dwarf *dbg, bool debug_types)
> newp->orig_abbrev_offset = newp->last_abbrev_offset = abbrev_offset;
> newp->files = NULL;
> newp->lines = NULL;
> - newp->locs = NULL;
> newp->split = (Dwarf_CU *) -1;
> newp->base_address = (Dwarf_Addr) -1;
> newp->addr_base = (Dwarf_Off) -1;
> @@ -177,6 +176,7 @@ __libdw_intern_next_unit (Dwarf *dbg, bool debug_types)
>
> newp->startp = data->d_buf + newp->start;
> newp->endp = data->d_buf + newp->end;
> + eu_search_tree_init (&newp->locs_tree);
>
> /* v4 debug type units have version == 4 and unit_type == DW_UT_type. */
> if (debug_types)
OK.
> @@ -221,7 +221,7 @@ __libdw_intern_next_unit (Dwarf *dbg, bool debug_types)
> Dwarf_Sig8_Hash_insert (&dbg->sig8_hash, unit_id8, newp);
>
> /* Add the new entry to the search tree. */
> - if (tsearch (newp, tree, findcu_cb) == NULL)
> + if (eu_tsearch (newp, tree, findcu_cb) == NULL)
> {
> /* Something went wrong. Undo the operation. */
> *offsetp = oldoff;
> @@ -236,13 +236,13 @@ struct Dwarf_CU *
> internal_function
> __libdw_findcu (Dwarf *dbg, Dwarf_Off start, bool v4_debug_types)
> {
> - void **tree = v4_debug_types ? &dbg->tu_tree : &dbg->cu_tree;
> + search_tree *tree = v4_debug_types ? &dbg->tu_tree : &dbg->cu_tree;
> Dwarf_Off *next_offset
> = v4_debug_types ? &dbg->next_tu_offset : &dbg->next_cu_offset;
>
> /* Maybe we already know that CU. */
> struct Dwarf_CU fake = { .start = start, .end = 0 };
> - struct Dwarf_CU **found = tfind (&fake, tree, findcu_cb);
> + struct Dwarf_CU **found = eu_tfind (&fake, tree, findcu_cb);
> if (found != NULL)
> return *found;
>
OK.
> @@ -270,7 +270,7 @@ struct Dwarf_CU *
> internal_function
> __libdw_findcu_addr (Dwarf *dbg, void *addr)
> {
> - void **tree;
> + search_tree *tree;
> Dwarf_Off start;
> if (addr >= dbg->sectiondata[IDX_debug_info]->d_buf
> && addr < (dbg->sectiondata[IDX_debug_info]->d_buf
> @@ -291,7 +291,7 @@ __libdw_findcu_addr (Dwarf *dbg, void *addr)
> return NULL;
>
> struct Dwarf_CU fake = { .start = start, .end = 0 };
> - struct Dwarf_CU **found = tfind (&fake, tree, findcu_cb);
> + struct Dwarf_CU **found = eu_tfind (&fake, tree, findcu_cb);
>
> if (found != NULL)
> return *found;
OK, tree will be the cu_tree or tu_tree here.
> @@ -306,7 +306,7 @@ __libdw_find_split_dbg_addr (Dwarf *dbg, void *addr)
> /* XXX Assumes split DWARF only has CUs in main IDX_debug_info. */
> Elf_Data fake_data = { .d_buf = addr, .d_size = 0 };
> Dwarf fake = { .sectiondata[IDX_debug_info] = &fake_data };
> - Dwarf **found = tfind (&fake, &dbg->split_tree, __libdw_finddbg_cb);
> + Dwarf **found = eu_tfind (&fake, &dbg->split_tree, __libdw_finddbg_cb);
>
> if (found != NULL)
> return *found;
OK.
> diff --git a/libdwfl/cu.c b/libdwfl/cu.c
> index 06684357..d10c562a 100644
> --- a/libdwfl/cu.c
> +++ b/libdwfl/cu.c
> @@ -33,7 +33,7 @@
> #include "libdwflP.h"
> #include "libdwP.h"
> #include "memory-access.h"
> -#include <search.h>
> +#include <eu-search.h>
>
Please use "eu-search.h" here.
>
> static inline Dwarf_Arange *
> @@ -151,8 +151,7 @@ less_lazy (Dwfl_Module *mod)
> return;
>
> /* We know about all the CUs now, we don't need this table. */
> - tdestroy (mod->lazy_cu_root, nofree);
> - mod->lazy_cu_root = NULL;
> + eu_tdestroy (&mod->lazy_cu_tree, nofree);
> }
OK, a eu_tdestroy here, and then there is a eu_search_tree_fini in
__libdwfl_module_free, which will call eu_tdestroy again (on the now
NULL tree). Is that correct? Does [eu_]tdestroy handle NULL trees?
> static inline Dwarf_Off
> @@ -198,7 +197,8 @@ intern_cu (Dwfl_Module *mod, Dwarf_Off cuoff, struct dwfl_cu **result)
>
> struct dwfl_cu key;
> key.die.cu = die->cu;
> - struct dwfl_cu **found = tsearch (&key, &mod->lazy_cu_root, &compare_cukey);
> + struct dwfl_cu **found = eu_tsearch (&key, &mod->lazy_cu_tree,
> + &compare_cukey);
> if (unlikely (found == NULL))
> return DWFL_E_NOMEM;
OK.
> diff --git a/libdwfl/dwfl_module.c b/libdwfl/dwfl_module.c
> index c4d872d4..b4ddf806 100644
> --- a/libdwfl/dwfl_module.c
> +++ b/libdwfl/dwfl_module.c
> @@ -61,8 +61,7 @@ void
> internal_function
> __libdwfl_module_free (Dwfl_Module *mod)
> {
> - if (mod->lazy_cu_root != NULL)
> - tdestroy (mod->lazy_cu_root, nofree);
> + eu_search_tree_fini (&mod->lazy_cu_tree, nofree);
See question above about (indirectly) calling eu_tdestroy on a NULL
tree above.
>
> if (mod->aranges != NULL)
> free (mod->aranges);
> @@ -200,6 +199,7 @@ dwfl_report_module (Dwfl *dwfl, const char *name,
> mod->low_addr = start;
> mod->high_addr = end;
> mod->dwfl = dwfl;
> + eu_search_tree_init (&mod->lazy_cu_tree);
>
> return use (mod, tailp, dwfl);
> }
OK.
> diff --git a/libdwfl/libdwflP.h b/libdwfl/libdwflP.h
> index d27bfdc2..395ab9c8 100644
> --- a/libdwfl/libdwflP.h
> +++ b/libdwfl/libdwflP.h
> @@ -37,6 +37,7 @@
> #include <stdbool.h>
> #include <stdlib.h>
> #include <string.h>
> +#include <eu-search.h>
Please use #include "eu-search.h".
> #include "libdwP.h" /* We need its INTDECLs. */
> #include "libdwelfP.h"
> @@ -201,7 +202,7 @@ struct Dwfl_Module
> /* Known CU's in this module. */
> struct dwfl_cu *first_cu, **cu;
>
> - void *lazy_cu_root; /* Table indexed by Dwarf_Off of CU. */
> + search_tree lazy_cu_tree; /* Table indexed by Dwarf_Off of CU. */
>
> struct dwfl_arange *aranges; /* Mapping of addresses in module to CUs. */
>
OK.
> 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;
OK, these were inited to NULL by calloc before.
> 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)
OK.
> diff --git a/libelf/elf_getdata_rawchunk.c b/libelf/elf_getdata_rawchunk.c
> index 1751878d..3269dc6c 100644
> --- a/libelf/elf_getdata_rawchunk.c
> +++ b/libelf/elf_getdata_rawchunk.c
> @@ -33,8 +33,7 @@
>
> #include <assert.h>
> #include <errno.h>
> -#include <search.h>
> -#include <stdlib.h>
> +#include <eu-search.h>
> #include <string.h>
Please use #include "eu-search.h".
>
> #include "libelfP.h"
> @@ -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;
OK.
> diff --git a/libelf/libelfP.h b/libelf/libelfP.h
> index bdd2cc6a..3e4ab2f3 100644
> --- a/libelf/libelfP.h
> +++ b/libelf/libelfP.h
> @@ -33,6 +33,7 @@
>
> #include <ar.h>
> #include <gelf.h>
> +#include <eu-search.h>
Slightly surprising ar.h is a global system header, but gelf.h and eu-
search.h are not.
>
> #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. */
OK.
Cheers,
Mark
@@ -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
@@ -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. */
new file mode 100644
@@ -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);
+}
new file mode 100644
@@ -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
new file mode 100644
@@ -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 */
@@ -90,13 +90,13 @@ struct Dwarf_CFI_s
Dwarf_Off next_offset;
/* Search tree for the CIEs, indexed by CIE_pointer (section offset). */
- void *cie_tree;
+ search_tree cie_tree;
/* Search tree for the FDEs, indexed by PC address. */
- void *fde_tree;
+ search_tree fde_tree;
/* Search tree for parsed DWARF expressions, indexed by raw pointer. */
- void *expr_tree;
+ search_tree expr_tree;
/* Backend hook. */
struct ebl *ebl;
@@ -33,7 +33,7 @@
#include "cfi.h"
#include "encoded-value.h"
#include <assert.h>
-#include <search.h>
+#include <eu-search.h>
#include <stdlib.h>
@@ -144,7 +144,7 @@ intern_new_cie (Dwarf_CFI *cache, Dwarf_Off offset, const Dwarf_CIE *info)
cie->initial_state = NULL;
/* Add the new entry to the search tree. */
- if (tsearch (cie, &cache->cie_tree, &compare_cie) == NULL)
+ if (eu_tsearch (cie, &cache->cie_tree, &compare_cie) == NULL)
{
free (cie);
__libdw_seterrno (DWARF_E_NOMEM);
@@ -160,7 +160,8 @@ internal_function
__libdw_find_cie (Dwarf_CFI *cache, Dwarf_Off offset)
{
const struct dwarf_cie cie_key = { .offset = offset };
- struct dwarf_cie **found = tfind (&cie_key, &cache->cie_tree, &compare_cie);
+ struct dwarf_cie **found = eu_tfind (&cie_key, &cache->cie_tree,
+ &compare_cie);
if (found != NULL)
return *found;
@@ -189,7 +190,8 @@ internal_function
__libdw_intern_cie (Dwarf_CFI *cache, Dwarf_Off offset, const Dwarf_CIE *info)
{
const struct dwarf_cie cie_key = { .offset = offset };
- struct dwarf_cie **found = tfind (&cie_key, &cache->cie_tree, &compare_cie);
+ struct dwarf_cie **found = eu_tfind (&cie_key, &cache->cie_tree,
+ &compare_cie);
if (found == NULL)
/* We have not read this CIE yet. Enter it. */
(void) intern_new_cie (cache, offset, info);
@@ -354,11 +354,11 @@ valid_p (Dwarf *result)
result->fake_loc_cu->endp
= (result->sectiondata[IDX_debug_loc]->d_buf
+ result->sectiondata[IDX_debug_loc]->d_size);
- result->fake_loc_cu->locs = NULL;
result->fake_loc_cu->address_size = elf_addr_size;
result->fake_loc_cu->offset_size = 4;
result->fake_loc_cu->version = 4;
result->fake_loc_cu->split = NULL;
+ eu_search_tree_init (&result->fake_loc_cu->locs_tree);
}
}
@@ -382,11 +382,11 @@ valid_p (Dwarf *result)
result->fake_loclists_cu->endp
= (result->sectiondata[IDX_debug_loclists]->d_buf
+ result->sectiondata[IDX_debug_loclists]->d_size);
- result->fake_loclists_cu->locs = NULL;
result->fake_loclists_cu->address_size = elf_addr_size;
result->fake_loclists_cu->offset_size = 4;
result->fake_loclists_cu->version = 5;
result->fake_loclists_cu->split = NULL;
+ eu_search_tree_init (&result->fake_loclists_cu->locs_tree);
}
}
@@ -415,11 +415,11 @@ valid_p (Dwarf *result)
result->fake_addr_cu->endp
= (result->sectiondata[IDX_debug_addr]->d_buf
+ result->sectiondata[IDX_debug_addr]->d_size);
- result->fake_addr_cu->locs = NULL;
result->fake_addr_cu->address_size = elf_addr_size;
result->fake_addr_cu->offset_size = 4;
result->fake_addr_cu->version = 5;
result->fake_addr_cu->split = NULL;
+ eu_search_tree_init (&result->fake_addr_cu->locs_tree);
}
}
@@ -579,6 +579,7 @@ dwarf_begin_elf (Elf *elf, Dwarf_Cmd cmd, Elf_Scn *scngrp)
__libdw_seterrno (DWARF_E_NOMEM); /* no memory. */
return NULL;
}
+ rwlock_init(result->dwarf_lock);
result->mem_stacks = 0;
result->mem_tails = NULL;
@@ -61,14 +61,15 @@ static void
cu_free (void *arg)
{
struct Dwarf_CU *p = (struct Dwarf_CU *) arg;
-
- tdestroy (p->locs, noop_free);
+ eu_search_tree_fini (&p->locs_tree, noop_free);
/* Only free the CU internals if its not a fake CU. */
- if(p != p->dbg->fake_loc_cu && p != p->dbg->fake_loclists_cu
+ if (p != p->dbg->fake_loc_cu && p != p->dbg->fake_loclists_cu
&& p != p->dbg->fake_addr_cu)
{
Dwarf_Abbrev_Hash_free (&p->abbrev_hash);
+ rwlock_fini (p->abbrev_lock);
+ rwlock_fini (p->split_lock);
/* Free split dwarf one way (from skeleton to split). */
if (p->unit_type == DW_UT_skeleton
@@ -102,17 +103,17 @@ dwarf_end (Dwarf *dwarf)
/* The search tree for the CUs. NB: the CU data itself is
allocated separately, but the abbreviation hash tables need
to be handled. */
- tdestroy (dwarf->cu_tree, cu_free);
- tdestroy (dwarf->tu_tree, cu_free);
+ eu_search_tree_fini (&dwarf->cu_tree, cu_free);
+ eu_search_tree_fini (&dwarf->tu_tree, cu_free);
/* Search tree for macro opcode tables. */
- tdestroy (dwarf->macro_ops, noop_free);
+ eu_search_tree_fini (&dwarf->macro_ops_tree, noop_free);
/* Search tree for decoded .debug_lines units. */
- tdestroy (dwarf->files_lines, noop_free);
+ eu_search_tree_fini (&dwarf->files_lines_tree, noop_free);
/* And the split Dwarf. */
- tdestroy (dwarf->split_tree, noop_free);
+ eu_search_tree_fini (&dwarf->split_tree, noop_free);
/* Free the internally allocated memory. */
for (size_t i = 0; i < dwarf->mem_stacks; i++)
@@ -66,7 +66,10 @@ dwarf_getcfi (Dwarf *dbg)
cfi->default_same_value = false;
cfi->next_offset = 0;
- cfi->cie_tree = cfi->fde_tree = cfi->expr_tree = NULL;
+
+ eu_search_tree_init (&cfi->cie_tree);
+ eu_search_tree_init (&cfi->fde_tree);
+ eu_search_tree_init (&cfi->expr_tree);
cfi->ebl = NULL;
@@ -31,10 +31,11 @@
#endif
#include <dwarf.h>
-#include <search.h>
+#include <eu-search.h>
#include <stdlib.h>
#include <assert.h>
+#include <cfi.h>
#include <libdwP.h>
@@ -137,9 +138,9 @@ loc_compare (const void *p1, const void *p2)
/* For each DW_OP_implicit_value, we store a special entry in the cache.
This points us directly to the block data for later fetching.
- Returns zero on success, -1 on bad DWARF or 1 if tsearch failed. */
+ Returns zero on success, -1 on bad DWARF or 1 if eu_tsearch failed. */
static int
-store_implicit_value (Dwarf *dbg, void **cache, Dwarf_Op *op)
+store_implicit_value (Dwarf *dbg, search_tree *cache, Dwarf_Op *op)
{
if (dbg == NULL)
return -1;
@@ -154,7 +155,7 @@ store_implicit_value (Dwarf *dbg, void **cache, Dwarf_Op *op)
block->addr = op;
block->data = (unsigned char *) data;
block->length = op->number;
- if (unlikely (tsearch (block, cache, loc_compare) == NULL))
+ if (unlikely (eu_tsearch (block, cache, loc_compare) == NULL))
return 1;
return 0;
}
@@ -167,7 +168,8 @@ dwarf_getlocation_implicit_value (Dwarf_Attribute *attr, const Dwarf_Op *op,
return -1;
struct loc_block_s fake = { .addr = (void *) op };
- struct loc_block_s **found = tfind (&fake, &attr->cu->locs, loc_compare);
+ struct loc_block_s **found = eu_tfind (&fake, &attr->cu->locs_tree,
+ loc_compare);
if (unlikely (found == NULL))
{
__libdw_seterrno (DWARF_E_NO_BLOCK);
@@ -211,7 +213,7 @@ is_constant_offset (Dwarf_Attribute *attr,
/* Check whether we already cached this location. */
struct loc_s fake = { .addr = attr->valp };
- struct loc_s **found = tfind (&fake, &attr->cu->locs, loc_compare);
+ struct loc_s **found = eu_tfind (&fake, &attr->cu->locs_tree, loc_compare);
if (found == NULL)
{
@@ -235,7 +237,7 @@ is_constant_offset (Dwarf_Attribute *attr,
newp->loc = result;
newp->nloc = 1;
- found = tsearch (newp, &attr->cu->locs, loc_compare);
+ found = eu_tsearch (newp, &attr->cu->locs_tree, loc_compare);
}
assert ((*found)->nloc == 1);
@@ -253,7 +255,7 @@ int
internal_function
__libdw_intern_expression (Dwarf *dbg, bool other_byte_order,
unsigned int address_size, unsigned int ref_size,
- void **cache, const Dwarf_Block *block,
+ search_tree *cache, const Dwarf_Block *block,
bool cfap, bool valuep,
Dwarf_Op **llbuf, size_t *listlen, int sec_index)
{
@@ -266,7 +268,7 @@ __libdw_intern_expression (Dwarf *dbg, bool other_byte_order,
/* Check whether we already looked at this list. */
struct loc_s fake = { .addr = block->data };
- struct loc_s **found = tfind (&fake, cache, loc_compare);
+ struct loc_s **found = eu_tfind (&fake, cache, loc_compare);
if (found != NULL)
{
/* We already saw it. */
@@ -655,7 +657,7 @@ __libdw_intern_expression (Dwarf *dbg, bool other_byte_order,
newp->addr = block->data;
newp->loc = result;
newp->nloc = *listlen;
- (void) tsearch (newp, cache, loc_compare);
+ eu_tsearch (newp, cache, loc_compare);
/* We did it. */
return 0;
@@ -677,7 +679,7 @@ getlocation (struct Dwarf_CU *cu, const Dwarf_Block *block,
cu->address_size, (cu->version == 2
? cu->address_size
: cu->offset_size),
- &cu->locs, block,
+ &cu->locs_tree, block,
false, false,
llbuf, listlen, sec_index);
}
@@ -32,7 +32,7 @@
#include <assert.h>
#include <dwarf.h>
-#include <search.h>
+#include <eu-search.h>
#include <stdlib.h>
#include <string.h>
@@ -317,7 +317,7 @@ cache_op_table (Dwarf *dbg, int sec_index, Dwarf_Off macoff,
Dwarf_Die *cudie)
{
Dwarf_Macro_Op_Table fake = { .offset = macoff, .sec_index = sec_index };
- Dwarf_Macro_Op_Table **found = tfind (&fake, &dbg->macro_ops,
+ Dwarf_Macro_Op_Table **found = eu_tfind (&fake, &dbg->macro_ops_tree,
macro_op_compare);
if (found != NULL)
return *found;
@@ -329,7 +329,7 @@ cache_op_table (Dwarf *dbg, int sec_index, Dwarf_Off macoff,
if (table == NULL)
return NULL;
- Dwarf_Macro_Op_Table **ret = tsearch (table, &dbg->macro_ops,
+ Dwarf_Macro_Op_Table **ret = eu_tsearch (table, &dbg->macro_ops_tree,
macro_op_compare);
if (unlikely (ret == NULL))
{
@@ -33,7 +33,7 @@
#include <assert.h>
#include <stdlib.h>
#include <string.h>
-#include <search.h>
+#include <eu-search.h>
#include "dwarf.h"
#include "libdwP.h"
@@ -1320,8 +1320,8 @@ get_lines_or_files (Dwarf *dbg, Dwarf_Off debug_line_offset,
Dwarf_Lines **linesp, Dwarf_Files **filesp)
{
struct files_lines_s fake = { .debug_line_offset = debug_line_offset };
- struct files_lines_s **found = tfind (&fake, &dbg->files_lines,
- files_lines_compare);
+ struct files_lines_s **found = eu_tfind (&fake, &dbg->files_lines_tree,
+ files_lines_compare);
if (found == NULL)
{
/* This .debug_line is being read for the first time. */
@@ -1354,7 +1354,7 @@ get_lines_or_files (Dwarf *dbg, Dwarf_Off debug_line_offset,
node->debug_line_offset = debug_line_offset;
- found = tsearch (node, &dbg->files_lines, files_lines_compare);
+ found = eu_tsearch (node, &dbg->files_lines_tree, files_lines_compare);
if (found == NULL)
{
__libdw_seterrno (DWARF_E_NOMEM);
@@ -31,7 +31,7 @@
#endif
#include "cfi.h"
-#include <search.h>
+#include <eu-search.h>
#include <stdlib.h>
#include "encoded-value.h"
@@ -122,7 +122,7 @@ intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry)
fde->instructions += cie->fde_augmentation_data_size;
/* Add the new entry to the search tree. */
- struct dwarf_fde **tres = tsearch (fde, &cache->fde_tree, &compare_fde);
+ struct dwarf_fde **tres = eu_tsearch (fde, &cache->fde_tree, &compare_fde);
if (tres == NULL)
{
free (fde);
@@ -252,7 +252,7 @@ __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
/* Look for a cached FDE covering this address. */
const struct dwarf_fde fde_key = { .start = address, .end = 0 };
- struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde);
+ struct dwarf_fde **found = eu_tfind (&fde_key, &cache->fde_tree, &compare_fde);
if (found != NULL)
return *found;
@@ -60,10 +60,10 @@ void
internal_function
__libdw_destroy_frame_cache (Dwarf_CFI *cache)
{
- /* Most of the data is in our two search trees. */
- tdestroy (cache->fde_tree, free_fde);
- tdestroy (cache->cie_tree, free_cie);
- tdestroy (cache->expr_tree, free_expr);
+ /* Most of the data is in our three search trees. */
+ eu_search_tree_fini (&cache->fde_tree, free_fde);
+ eu_search_tree_fini (&cache->cie_tree, free_cie);
+ eu_search_tree_fini (&cache->expr_tree, free_expr);
if (cache->ebl != NULL && cache->ebl != (void *) -1l)
ebl_closebackend (cache->ebl);
@@ -32,6 +32,7 @@
#include <stdbool.h>
#include <pthread.h>
+#include <eu-search.h>
#include <libdw.h>
#include <dwarf.h>
@@ -215,22 +216,22 @@ struct Dwarf
size_t pubnames_nsets;
/* Search tree for the CUs. */
- void *cu_tree;
+ search_tree cu_tree;
Dwarf_Off next_cu_offset;
/* Search tree and sig8 hash table for .debug_types type units. */
- void *tu_tree;
+ search_tree tu_tree;
Dwarf_Off next_tu_offset;
Dwarf_Sig8_Hash sig8_hash;
/* Search tree for split Dwarf associated with CUs in this debug. */
- void *split_tree;
+ search_tree split_tree;
/* Search tree for .debug_macro operator tables. */
- void *macro_ops;
+ search_tree macro_ops_tree;
/* Search tree for decoded .debug_line units. */
- void *files_lines;
+ search_tree files_lines_tree;
/* Address ranges read from .debug_aranges. */
Dwarf_Aranges *aranges;
@@ -263,6 +264,10 @@ struct Dwarf
allocations for this Dwarf. */
pthread_rwlock_t mem_rwl;
+ /* The dwarf_lock is a read-write lock designed to ensure thread-safe access
+ and modification of Dwarf objects. */
+ rwlock_define(, dwarf_lock);
+
/* Internal memory handling. This is basically a simplified thread-local
reimplementation of obstacks. Unfortunately the standard obstack
implementation is not usable in libraries. */
@@ -423,7 +428,7 @@ struct Dwarf_CU
Dwarf_Files *files;
/* Known location lists. */
- void *locs;
+ search_tree locs_tree;
/* Base address for use with ranges and locs.
Don't access directly, call __libdw_cu_base_address. */
@@ -446,6 +451,12 @@ struct Dwarf_CU
Don't access directly, call __libdw_cu_locs_base. */
Dwarf_Off locs_base;
+ /* Synchronize Dwarf_Die abbrev access. */
+ rwlock_define(, abbrev_lock);
+
+ /* Synchronize split Dwarf access. */
+ rwlock_define(, split_lock);
+
/* Memory boundaries of this CU. */
void *startp;
void *endp;
@@ -912,7 +923,8 @@ extern int __libdw_intern_expression (Dwarf *dbg,
bool other_byte_order,
unsigned int address_size,
unsigned int ref_size,
- void **cache, const Dwarf_Block *block,
+ search_tree *cache,
+ const Dwarf_Block *block,
bool cfap, bool valuep,
Dwarf_Op **llbuf, size_t *listlen,
int sec_index)
@@ -34,7 +34,7 @@
#include "libelfP.h"
#include <limits.h>
-#include <search.h>
+#include <eu-search.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
@@ -57,8 +57,8 @@ try_split_file (Dwarf_CU *cu, const char *dwo_path)
if (split->unit_type == DW_UT_split_compile
&& cu->unit_id8 == split->unit_id8)
{
- if (tsearch (split->dbg, &cu->dbg->split_tree,
- __libdw_finddbg_cb) == NULL)
+ if (eu_tsearch (split->dbg, &cu->dbg->split_tree,
+ __libdw_finddbg_cb) == NULL)
{
/* Something went wrong. Don't link. */
__libdw_seterrno (DWARF_E_NOMEM);
@@ -132,8 +132,8 @@ try_dwp_file (Dwarf_CU *cu)
cu->unit_id8);
if (split != NULL)
{
- if (tsearch (split->dbg, &cu->dbg->split_tree,
- __libdw_finddbg_cb) == NULL)
+ if (eu_tsearch (split->dbg, &cu->dbg->split_tree,
+ __libdw_finddbg_cb) == NULL)
{
/* Something went wrong. Don't link. */
__libdw_seterrno (DWARF_E_NOMEM);
@@ -32,7 +32,7 @@
#endif
#include <assert.h>
-#include <search.h>
+#include <eu-search.h>
#include "libdwP.h"
static int
@@ -101,7 +101,7 @@ __libdw_intern_next_unit (Dwarf *dbg, bool debug_types)
{
Dwarf_Off *const offsetp
= debug_types ? &dbg->next_tu_offset : &dbg->next_cu_offset;
- void **tree = debug_types ? &dbg->tu_tree : &dbg->cu_tree;
+ search_tree *tree = debug_types ? &dbg->tu_tree : &dbg->cu_tree;
Dwarf_Off oldoff = *offsetp;
uint16_t version;
@@ -167,7 +167,6 @@ __libdw_intern_next_unit (Dwarf *dbg, bool debug_types)
newp->orig_abbrev_offset = newp->last_abbrev_offset = abbrev_offset;
newp->files = NULL;
newp->lines = NULL;
- newp->locs = NULL;
newp->split = (Dwarf_CU *) -1;
newp->base_address = (Dwarf_Addr) -1;
newp->addr_base = (Dwarf_Off) -1;
@@ -177,6 +176,7 @@ __libdw_intern_next_unit (Dwarf *dbg, bool debug_types)
newp->startp = data->d_buf + newp->start;
newp->endp = data->d_buf + newp->end;
+ eu_search_tree_init (&newp->locs_tree);
/* v4 debug type units have version == 4 and unit_type == DW_UT_type. */
if (debug_types)
@@ -221,7 +221,7 @@ __libdw_intern_next_unit (Dwarf *dbg, bool debug_types)
Dwarf_Sig8_Hash_insert (&dbg->sig8_hash, unit_id8, newp);
/* Add the new entry to the search tree. */
- if (tsearch (newp, tree, findcu_cb) == NULL)
+ if (eu_tsearch (newp, tree, findcu_cb) == NULL)
{
/* Something went wrong. Undo the operation. */
*offsetp = oldoff;
@@ -236,13 +236,13 @@ struct Dwarf_CU *
internal_function
__libdw_findcu (Dwarf *dbg, Dwarf_Off start, bool v4_debug_types)
{
- void **tree = v4_debug_types ? &dbg->tu_tree : &dbg->cu_tree;
+ search_tree *tree = v4_debug_types ? &dbg->tu_tree : &dbg->cu_tree;
Dwarf_Off *next_offset
= v4_debug_types ? &dbg->next_tu_offset : &dbg->next_cu_offset;
/* Maybe we already know that CU. */
struct Dwarf_CU fake = { .start = start, .end = 0 };
- struct Dwarf_CU **found = tfind (&fake, tree, findcu_cb);
+ struct Dwarf_CU **found = eu_tfind (&fake, tree, findcu_cb);
if (found != NULL)
return *found;
@@ -270,7 +270,7 @@ struct Dwarf_CU *
internal_function
__libdw_findcu_addr (Dwarf *dbg, void *addr)
{
- void **tree;
+ search_tree *tree;
Dwarf_Off start;
if (addr >= dbg->sectiondata[IDX_debug_info]->d_buf
&& addr < (dbg->sectiondata[IDX_debug_info]->d_buf
@@ -291,7 +291,7 @@ __libdw_findcu_addr (Dwarf *dbg, void *addr)
return NULL;
struct Dwarf_CU fake = { .start = start, .end = 0 };
- struct Dwarf_CU **found = tfind (&fake, tree, findcu_cb);
+ struct Dwarf_CU **found = eu_tfind (&fake, tree, findcu_cb);
if (found != NULL)
return *found;
@@ -306,7 +306,7 @@ __libdw_find_split_dbg_addr (Dwarf *dbg, void *addr)
/* XXX Assumes split DWARF only has CUs in main IDX_debug_info. */
Elf_Data fake_data = { .d_buf = addr, .d_size = 0 };
Dwarf fake = { .sectiondata[IDX_debug_info] = &fake_data };
- Dwarf **found = tfind (&fake, &dbg->split_tree, __libdw_finddbg_cb);
+ Dwarf **found = eu_tfind (&fake, &dbg->split_tree, __libdw_finddbg_cb);
if (found != NULL)
return *found;
@@ -33,7 +33,7 @@
#include "libdwflP.h"
#include "libdwP.h"
#include "memory-access.h"
-#include <search.h>
+#include <eu-search.h>
static inline Dwarf_Arange *
@@ -151,8 +151,7 @@ less_lazy (Dwfl_Module *mod)
return;
/* We know about all the CUs now, we don't need this table. */
- tdestroy (mod->lazy_cu_root, nofree);
- mod->lazy_cu_root = NULL;
+ eu_tdestroy (&mod->lazy_cu_tree, nofree);
}
static inline Dwarf_Off
@@ -198,7 +197,8 @@ intern_cu (Dwfl_Module *mod, Dwarf_Off cuoff, struct dwfl_cu **result)
struct dwfl_cu key;
key.die.cu = die->cu;
- struct dwfl_cu **found = tsearch (&key, &mod->lazy_cu_root, &compare_cukey);
+ struct dwfl_cu **found = eu_tsearch (&key, &mod->lazy_cu_tree,
+ &compare_cukey);
if (unlikely (found == NULL))
return DWFL_E_NOMEM;
@@ -61,8 +61,7 @@ void
internal_function
__libdwfl_module_free (Dwfl_Module *mod)
{
- if (mod->lazy_cu_root != NULL)
- tdestroy (mod->lazy_cu_root, nofree);
+ eu_search_tree_fini (&mod->lazy_cu_tree, nofree);
if (mod->aranges != NULL)
free (mod->aranges);
@@ -200,6 +199,7 @@ dwfl_report_module (Dwfl *dwfl, const char *name,
mod->low_addr = start;
mod->high_addr = end;
mod->dwfl = dwfl;
+ eu_search_tree_init (&mod->lazy_cu_tree);
return use (mod, tailp, dwfl);
}
@@ -37,6 +37,7 @@
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
+#include <eu-search.h>
#include "libdwP.h" /* We need its INTDECLs. */
#include "libdwelfP.h"
@@ -201,7 +202,7 @@ struct Dwfl_Module
/* Known CU's in this module. */
struct dwfl_cu *first_cu, **cu;
- void *lazy_cu_root; /* Table indexed by Dwarf_Off of CU. */
+ search_tree lazy_cu_tree; /* Table indexed by Dwarf_Off of CU. */
struct dwfl_arange *aranges; /* Mapping of addresses in module to CUs. */
@@ -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;
@@ -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)
@@ -33,8 +33,7 @@
#include <assert.h>
#include <errno.h>
-#include <search.h>
-#include <stdlib.h>
+#include <eu-search.h>
#include <string.h>
#include "libelfP.h"
@@ -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;
@@ -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. */