Hi Mark, I think having unique per-root locks might be a good idea. From a brief test, I saw around 70 roots created when parsing the test file I have been using. I have an initial idea for this that I don't think will be too complicated. I will go over my idea with John to get his input and then get back to you.
Best, Heather On Tue, Oct 10, 2023 at 11:51 AM Mark Wielaard <m...@klomp.org> wrote: > Hi Heather, > > On Tue, 2023-10-10 at 15:42 +0200, Mark Wielaard wrote: > > From: Heather McIntyre <h...@rice.edu> > > > > * lib/eu-search.h: New file. > > Declarations for read/write locked eu_tsearch/eu_tfind. > > Like in the previous case, don't forget to add such a new header to > noinst_HEADERS so make dist adds them. > > diff --git a/lib/Makefile.am b/lib/Makefile.am > index ce8f3e1b..9df0a8c6 100644 > --- a/lib/Makefile.am > +++ b/lib/Makefile.am > @@ -39,5 +39,6 @@ libeu_a_SOURCES = xasprintf.c xstrdup.c xstrndup.c > xmalloc.c next_prime.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 > EXTRA_DIST = dynamicsizehash.c dynamicsizehash_concurrent.c > > > * lib/eu-search.c: New file. > > Definitions for read/write locked eu_tsearch/eu_tfind. > > * Makefile.am (libeu_a_SOURCES): Add eu-search.c. > > > > Signed-off-by: Heather S. McIntyre <h...@rice.edu> > > Signed-off-by: Mark Wielaard <m...@klomp.org> > > --- > > lib/Makefile.am | 2 +- > > lib/eu-search.c | 60 +++++++++++++++++++++++++++++++++++++++++++++++++ > > lib/eu-search.h | 39 ++++++++++++++++++++++++++++++++ > > 3 files changed, 100 insertions(+), 1 deletion(-) > > create mode 100644 lib/eu-search.c > > create mode 100644 lib/eu-search.h > > > > diff --git a/lib/Makefile.am b/lib/Makefile.am > > index b3bb929f..ce8f3e1b 100644 > > --- a/lib/Makefile.am > > +++ b/lib/Makefile.am > > @@ -34,7 +34,7 @@ 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 > > OK. > > > noinst_HEADERS = fixedsizehash.h libeu.h system.h dynamicsizehash.h > list.h \ > > diff --git a/lib/eu-search.c b/lib/eu-search.c > > new file mode 100644 > > index 00000000..a6b04f4f > > --- /dev/null > > +++ b/lib/eu-search.c > > @@ -0,0 +1,60 @@ > > +/* 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 < > https://urldefense.com/v3/__http://www.gnu.org/licenses/__;!!BuQPrrmRaQ!j_izX_1hkv80LnClL5l2GD-1nTSH3dTTKjXsHtkYvr7TyudmXWLEZ7zOOkpQZFgo_0QKiWAkkvj7SBE54w$ > >. */ > > + > > +#ifdef HAVE_CONFIG_H > > +#include <config.h> > > +#endif > > + > > +#include <stdlib.h> > > +#include "eu-search.h" > > + > > +rwlock_define(static, search_find_lock); > > + > > +void *eu_tsearch(const void *key, void **rootp, > > + int (*compar)(const void *, const void *)) > > +{ > > + void *ret = NULL; > > + rwlock_wrlock(search_find_lock); > > + > > + ret = tsearch(key, rootp, compar); > > + > > + rwlock_unlock(search_find_lock); > > + return ret; > > +} > > + > > +void *eu_tfind(const void *key, void *const *rootp, > > + int (*compar)(const void *, const void *)) > > +{ > > + void *ret = NULL; > > + rwlock_rdlock(search_find_lock); > > + > > + ret = tfind(key, rootp, compar); > > + > > + rwlock_unlock(search_find_lock); > > + return ret; > > +} > > So this uses on static lock for all eu-tsearch/eu-tfind calls. But > searches with different roots should be independent. Would it make > sense to add different locks for different roots? > > That would make the code a little more complicated, but we could hide > the root and lock in a new structure that will be passed the the > eu_tsearch/eu_tfind calls. > > Maybe something like: > > struct eu_search_root > { > void *root; > rwlock_define (,lock); > }; > > With helper functions to create/init and destroy/delete them? > void eu_tinit (struct eu_search_root *search_root); > (Or is there no real initing to do?) > > void eu_tdestroy (struct eu_search_root *search_root, > void (*free_node)(void *nodep)); > > Or is all this way too complicated and a global lock just fine? > > Cheers, > > Mark > > > diff --git a/lib/eu-search.h b/lib/eu-search.h > > new file mode 100644 > > index 00000000..4ce0139a > > --- /dev/null > > +++ b/lib/eu-search.h > > @@ -0,0 +1,39 @@ > > +/* 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 < > https://urldefense.com/v3/__http://www.gnu.org/licenses/__;!!BuQPrrmRaQ!j_izX_1hkv80LnClL5l2GD-1nTSH3dTTKjXsHtkYvr7TyudmXWLEZ7zOOkpQZFgo_0QKiWAkkvj7SBE54w$ > >. */ > > + > > +#ifndef EU_SEARCH_H > > +#define EU_SEARCH_H 1 > > + > > +#include <search.h> > > + > > +extern void *eu_tsearch(const void *key, void **rootp, > > + int (*compar)(const void *, const void *)); > > +extern void *eu_tfind(const void *key, void *const *rootp, > > + int (*compar)(const void *, const void *)); > > + > > +#endif > >
