From: Heather McIntyre <hsm2@rice.edu>
To: Mark Wielaard <mark@klomp.org>
Cc: elfutils-devel@sourceware.org
Subject: Re: [PATCH 07/16] lib: Add eu_tsearch and eu_tfind
Date: Tue, 17 Oct 2023 15:52:58 -0500 [thread overview]
Message-ID: <CAK-+vz1Y2n-83DLuhdzkF4seDXJiK8CUKTdHx-A6XbBno9mq7Q@mail.gmail.com> (raw)
In-Reply-To: <3d7ddb9ac7498f97388f3606dbda4115b6596d10.camel@klomp.org>
[-- Attachment #1: Type: text/plain, Size: 7697 bytes --]
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
>
>
next prev parent reply other threads:[~2023-10-17 20:53 UTC|newest]
Thread overview: 51+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-08-08 17:07 [PATCH] Fix thread-safety for elfutils Heather McIntyre
2023-08-21 22:08 ` John Mellor-Crummey
2023-08-25 14:10 ` Mark Wielaard
2023-10-10 13:40 ` Mark Wielaard
2023-10-10 13:42 ` [PATCH 01/16] lib: Add new once_define and once macros to eu-config.h Mark Wielaard
2023-10-10 13:42 ` [PATCH 02/16] libelf: Make elf_version thread-safe Mark Wielaard
2023-10-10 14:00 ` Mark Wielaard
2023-10-17 19:05 ` Heather McIntyre
2023-10-19 21:00 ` Mark Wielaard
2023-10-10 13:42 ` [PATCH 03/16] libelf: Fix deadlock in __libelf_readall Mark Wielaard
2023-10-10 15:06 ` Mark Wielaard
2023-10-17 19:11 ` Heather McIntyre
2023-11-09 13:26 ` Mark Wielaard
2023-10-10 13:42 ` [PATCH 04/16] libelf: Fix deadlock in elf_cntl Mark Wielaard
2023-10-10 15:23 ` Mark Wielaard
2023-10-17 19:14 ` Heather McIntyre
2023-10-10 13:42 ` [PATCH 05/16] libelf: Fix elf_end deadlock Mark Wielaard
2023-10-10 15:28 ` Mark Wielaard
2023-10-10 13:42 ` [PATCH 06/16] libelf: Make elf32_getchdr and elf64_getchdr thread-safe Mark Wielaard
2023-10-10 16:28 ` Mark Wielaard
2023-10-10 13:42 ` [PATCH 07/16] lib: Add eu_tsearch and eu_tfind Mark Wielaard
2023-10-10 16:51 ` Mark Wielaard
2023-10-17 20:52 ` Heather McIntyre [this message]
2023-10-10 13:42 ` [PATCH 08/16] libcpu: Change calls for tsearch/tfind to eu_tsearch/eu_tfind Mark Wielaard
2023-10-10 21:10 ` Mark Wielaard
2023-10-10 13:42 ` [PATCH 09/16] src: Use eu-search in nm and findtextrel Mark Wielaard
2023-10-10 21:25 ` Mark Wielaard
2023-10-17 19:20 ` Heather McIntyre
2023-10-10 13:42 ` [PATCH 10/16] libdw: make dwarf_getalt thread-safe Mark Wielaard
2023-10-10 22:02 ` Mark Wielaard
2023-10-17 19:25 ` Heather McIntyre
2023-10-10 13:42 ` [PATCH 11/16] libdw: Add locking around __libdw_dieabbrev for dwarf_hasattr Mark Wielaard
2023-10-11 15:10 ` Mark Wielaard
2023-10-17 19:57 ` Heather McIntyre
2023-10-19 22:06 ` Mark Wielaard
2023-10-10 13:42 ` [PATCH 12/16] libdw: Make libdw_find_split_unit thread-safe Mark Wielaard
2023-10-11 17:17 ` Mark Wielaard
2023-10-17 20:01 ` Heather McIntyre
2023-10-10 13:42 ` [PATCH 13/16] libdw: Make libdw_findcu thread-safe Mark Wielaard
2023-10-12 22:02 ` Mark Wielaard
2023-10-17 20:10 ` Heather McIntyre
2023-10-10 13:42 ` [PATCH 14/16] libdw,libdwfl: Use eu-search for thread-safety Mark Wielaard
2023-10-12 22:05 ` Mark Wielaard
2023-10-10 13:42 ` [PATCH 15/16] tests: Add eu-search tests Mark Wielaard
2023-10-13 14:38 ` Mark Wielaard
2023-10-10 13:43 ` [PATCH 16/16] configure: No longer mark --enable-thread-safety as EXPERIMENTAL Mark Wielaard
2023-10-12 22:09 ` Mark Wielaard
2023-10-10 13:54 ` [PATCH 01/16] lib: Add new once_define and once macros to eu-config.h Mark Wielaard
2023-10-14 15:39 ` [PATCH] Fix thread-safety for elfutils Mark Wielaard
2023-10-14 18:29 ` Heather McIntyre
2023-10-17 15:04 ` Mark Wielaard
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAK-+vz1Y2n-83DLuhdzkF4seDXJiK8CUKTdHx-A6XbBno9mq7Q@mail.gmail.com \
--to=hsm2@rice.edu \
--cc=elfutils-devel@sourceware.org \
--cc=mark@klomp.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).