[07/16] lib: Add eu_tsearch and eu_tfind

  From: Heather McIntyre <hsm2@rice.edu>

	* lib/eu-search.h: New file.
	Declarations for read/write locked eu_tsearch/eu_tfind.
	* 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 <hsm2@rice.edu>
Signed-off-by: Mark Wielaard <mark@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
  

Hi Heather,

On Tue, 2023-10-10 at 15:42 +0200, Mark Wielaard wrote:
> From: Heather McIntyre <hsm2@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 <hsm2@rice.edu>
> Signed-off-by: Mark Wielaard <mark@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 <http://www.gnu.org/licenses/>.  */
> +
> +#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 <http://www.gnu.org/licenses/>.  */
> +
> +#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
  

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 <mark@klomp.org> wrote:

> Hi Heather,
>
> On Tue, 2023-10-10 at 15:42 +0200, Mark Wielaard wrote:
> > From: Heather McIntyre <hsm2@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 <hsm2@rice.edu>
> > Signed-off-by: Mark Wielaard <mark@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
>
>