Re: [PATCH 3/3] lib + libdw: Add and use a concurrent version of the dynamic-size hash table.

2019-11-04 Thread Mark Wielaard
Hi,

On Fri, 2019-10-25 at 23:11 -0500, Jonathon Anderson wrote:
> > I tried to simplify the code a little. You already observed that
> > COMPARE can be zero. But it always is. We never try comparing values.
> > So all the COMPARE and value passing to the find functions can simply
> > be removed. So if you agree I would like to merge the attached
> > simplification diff into this patch.
> 
> I'm fine with it, although at a glance it seems that this means 
> insert_helper will never return -1. Which doesn't quite sound accurate, 
> so I'll have to defer to Srdan on this one.

Srdan, any feedback on this?

Thanks,

Mark
From b70b350242d9752f41407c0ed7fe4683c8f31ce6 Mon Sep 17 00:00:00 2001
From: Mark Wielaard 
Date: Sat, 26 Oct 2019 01:54:43 +0200
Subject: [PATCH] no compare or val pass

---
 lib/dynamicsizehash_concurrent.c | 51 +---
 lib/dynamicsizehash_concurrent.h |  2 +-
 libdw/dwarf_abbrev_hash.h|  1 -
 libdw/dwarf_getabbrev.c  |  2 +-
 libdw/dwarf_tag.c|  2 +-
 5 files changed, 10 insertions(+), 48 deletions(-)

diff --git a/lib/dynamicsizehash_concurrent.c b/lib/dynamicsizehash_concurrent.c
index d645b143..5fa38713 100644
--- a/lib/dynamicsizehash_concurrent.c
+++ b/lib/dynamicsizehash_concurrent.c
@@ -36,46 +36,24 @@
 
NAME  name of the hash table structure.
TYPE  data type of the hash table entries
-   COMPARE   comparison function taking two pointers to TYPE objects
-
-   The following macros if present select features:
-
-   ITERATE   iterating over the table entries is possible
-   REVERSE   iterate in reverse order of insert
  */
 
 
 static size_t
-lookup (NAME *htab, HASHTYPE hval, TYPE val __attribute__ ((unused)))
+lookup (NAME *htab, HASHTYPE hval)
 {
   /* First hash function: simply take the modul but prevent zero.  Small values
   can skip the division, which helps performance when this is common.  */
   size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
 
-#if COMPARE != 0  /* A handful of tables don't actually compare the entries in
-the table, they instead rely on the hash.  In that case, we
-can skip parts that relate to the value. */
-  TYPE val_ptr;
-#endif
   HASHTYPE hash;
 
   hash = atomic_load_explicit(&htab->table[idx].hashval,
   memory_order_acquire);
   if (hash == hval)
-{
-#if COMPARE == 0
-  return idx;
-#else
-  val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
-memory_order_acquire);
-  if (COMPARE(val_ptr, val) == 0)
-  return idx;
-#endif
-}
+return idx;
   else if (hash == 0)
-{
-  return 0;
-}
+return 0;
 
   /* Second hash function as suggested in [Knuth].  */
   HASHTYPE second_hash = 1 + hval % (htab->size - 2);
@@ -90,20 +68,9 @@ lookup (NAME *htab, HASHTYPE hval, TYPE val __attribute__ ((unused)))
   hash = atomic_load_explicit(&htab->table[idx].hashval,
   memory_order_acquire);
   if (hash == hval)
-{
-#if COMPARE == 0
-  return idx;
-#else
-  val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
-memory_order_acquire);
-  if (COMPARE(val_ptr, val) == 0)
-  return idx;
-#endif
-}
+	return idx;
   else if (hash == 0)
-{
-  return 0;
-}
+	return 0;
 }
 }
 
@@ -123,8 +90,6 @@ insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
 {
   val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
 memory_order_acquire);
-  if (COMPARE(val_ptr, val) != 0)
-  return -1;
 }
   else if (hash == 0)
 {
@@ -168,8 +133,6 @@ insert_helper (NAME *htab, HASHTYPE hval, TYPE val)
 {
   val_ptr = (TYPE) atomic_load_explicit(&htab->table[idx].val_ptr,
 memory_order_acquire);
-  if (COMPARE(val_ptr, val) != 0)
-  return -1;
 }
   else if (hash == 0)
 {
@@ -495,7 +458,7 @@ TYPE
 #define FIND(name) _FIND (name)
 #define _FIND(name) \
   name##_find
-FIND(NAME) (NAME *htab, HASHTYPE hval, TYPE val)
+FIND(NAME) (NAME *htab, HASHTYPE hval)
 {
   while (pthread_rwlock_tryrdlock(&htab->resize_rwl) != 0)
   resize_worker(htab);
@@ -504,7 +467,7 @@ FIND(NAME) (NAME *htab, HASHTYPE hval, TYPE val)
 
   /* Make the hash data nonzero.  */
   hval = hval ?: 1;
-  idx = lookup(htab, hval, val);
+  idx = lookup(htab, hval);
 
   if (idx == 0)
 {
diff --git a/lib/dynamicsizehash_concurrent.h b/lib/dynamicsizehash_concurrent.h
index a137cbd0..73e66e91 100644
--- a/lib/dynamicsizehash_concurrent.h
+++ b/lib/dynamicsizehash_concurrent.h
@@ -97,7 +97,7 @@ extern int name##_free (name *htab);\
 extern int name##_insert (name *htab, HASHTYPE

Re: [PATCH 3/3] lib + libdw: Add and use a concurrent version of the dynamic-size hash table.

2019-11-04 Thread Mark Wielaard
Hi,

On Mon, 2019-10-28 at 21:12 +0100, Mark Wielaard wrote:
> On Sun, 2019-10-27 at 17:13 +0100, Mark Wielaard wrote:
> > On Fri, 2019-10-25 at 23:11 -0500, Jonathon Anderson wrote:
> > > A quick grep -r shows that ITERATE and REVERSE are used for the 
> > > asm_symbol_tab. If iteration and insertion are not concurrent we can 
> > > easily add bidirectional iteration (using the same Treiber stack-like 
> > > structure as used for the memory management). Also COMPARE is not 
> > > defined to be (0) in this instance.
> > 
> > Yes. We would need some other solution for the libasm code. But I think
> > we can use the concurrent table for everything in libdw.
> 
> And everything in libdw besides the abbrev hash is the sig8 hash.
> And adopting the concurrent dynamic size hash for that is almost
> trivial. See attached.
> 
> I only tested it lightly because I don't have any large projects build
> with -fdebug-types-dection. But it seems to work as intended.

Any comment on this patch?

Thanks,

Mark
From a4bf12a8b906911172897f14d62b3f43cc4066ad Mon Sep 17 00:00:00 2001
From: Mark Wielaard 
Date: Mon, 28 Oct 2019 20:54:35 +0100
Subject: [PATCH] libdw: Use dynamicsizehash_concurrent for Dwarf_Sig8_Hash.

Dwarf_Sig8_Hash is used as part of a Dwarf object to quickly find a type
unit based on the type signature. Use the concurrent variant of the dynamic
size hash to make it thread-safe to use.

Signed-off-by: Mark Wielaard 
---
 libdw/ChangeLog   | 8 
 libdw/dwarf_formref_die.c | 2 +-
 libdw/dwarf_sig8_hash.c   | 2 +-
 libdw/dwarf_sig8_hash.h   | 9 +++--
 4 files changed, 17 insertions(+), 4 deletions(-)

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index 28563b4d..61231e5c 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,11 @@
+2019-10-28  Mark Wielaard  
+
+	* dwarf_sig8_hash.h: Include libdw.h. Remove COMPARE. Include
+	dynamicsizehash_concurrent.h.
+	* dwarf_sig8_hash.c: Include dynamicsizehash_concurrent.c.
+	* dwarf_formref_die.c (dwarf_formref_die): Drop NULL argument to
+	Dwarf_Sig8_Hash_find.
+
 2019-08-26  Srđan Milaković  
 
 	* dwarf_abbrev_hash.{c,h}: Use the *_concurrent hash table.
diff --git a/libdw/dwarf_formref_die.c b/libdw/dwarf_formref_die.c
index f196331a..48ba8194 100644
--- a/libdw/dwarf_formref_die.c
+++ b/libdw/dwarf_formref_die.c
@@ -83,7 +83,7 @@ dwarf_formref_die (Dwarf_Attribute *attr, Dwarf_Die *result)
 	 have to match in the type unit headers.  */
 
   uint64_t sig = read_8ubyte_unaligned (cu->dbg, attr->valp);
-  cu = Dwarf_Sig8_Hash_find (&cu->dbg->sig8_hash, sig, NULL);
+  cu = Dwarf_Sig8_Hash_find (&cu->dbg->sig8_hash, sig);
   if (cu == NULL)
 	{
 	  /* Not seen before.  We have to scan through the type units.
diff --git a/libdw/dwarf_sig8_hash.c b/libdw/dwarf_sig8_hash.c
index 043cac78..777f9ebc 100644
--- a/libdw/dwarf_sig8_hash.c
+++ b/libdw/dwarf_sig8_hash.c
@@ -38,4 +38,4 @@
 #define next_prime __libdwarf_next_prime
 extern size_t next_prime (size_t) attribute_hidden;
 
-#include 
+#include 
diff --git a/libdw/dwarf_sig8_hash.h b/libdw/dwarf_sig8_hash.h
index 705ffbcd..c399919a 100644
--- a/libdw/dwarf_sig8_hash.h
+++ b/libdw/dwarf_sig8_hash.h
@@ -29,10 +29,15 @@
 #ifndef _DWARF_SIG8_HASH_H
 #define _DWARF_SIG8_HASH_H	1
 
+#ifdef HAVE_CONFIG_H
+# include 
+#endif
+
+#include "libdw.h"
+
 #define NAME Dwarf_Sig8_Hash
 #define TYPE struct Dwarf_CU *
-#define COMPARE(a, b) (0)
 
-#include 
+#include 
 
 #endif	/* dwarf_sig8_hash.h */
-- 
2.18.1



[PATCH] lib + libdw: Add and use a concurrent version of the dynamic-size hash table.

2019-11-04 Thread Jonathon Anderson
From: Srđan Milaković 

Signed-off-by: Srđan Milaković 
---
Apologies for the delay, things have been busy here the past week.

> On Fri, 2019-10-25 at 23:11 -0500, Jonathon Anderson wrote:
> > I tried to simplify the code a little. You already observed that
> > COMPARE can be zero. But it always is. We never try comparing values.
> > So all the COMPARE and value passing to the find functions can simply
> > be removed. So if you agree I would like to merge the attached
> > simplification diff into this patch.
> >
> > I'm fine with it, although at a glance it seems that this means
> > insert_helper will never return -1. Which doesn't quite sound accurate,
> > so I'll have to defer to Srdan on this one.
>
> Srdan, any feedback on this?

Apologies, I talked with Srdan in person and forgot to relay the message. He
gave me an updated version of the hash table that handles that issue (and
another previously harmless typo).

> On Mon, 2019-10-28 at 21:12 +0100, Mark Wielaard wrote:
> > On Sun, 2019-10-27 at 17:13 +0100, Mark Wielaard wrote:
> > > On Fri, 2019-10-25 at 23:11 -0500, Jonathon Anderson wrote:
> > > > A quick grep -r shows that ITERATE and REVERSE are used for the
> > > > asm_symbol_tab. If iteration and insertion are not concurrent we can
> > > > easily add bidirectional iteration (using the same Treiber stack-like
> > > > structure as used for the memory management). Also COMPARE is not
> > > > defined to be (0) in this instance.
> > >
> > > Yes. We would need some other solution for the libasm code. But I think
> > > we can use the concurrent table for everything in libdw.
> >
> > And everything in libdw besides the abbrev hash is the sig8 hash.
> > And adopting the concurrent dynamic size hash for that is almost
> > trivial. See attached.
> >
> > I only tested it lightly because I don't have any large projects build
> > with -fdebug-types-dection. But it seems to work as intended.
>
> Any comment on this patch?

I'm a little wary of applying this to Sig8, only because the contents are
entire CUs (rather than just Abbrevs). It seems to work though, so I just
need to make a more careful pass to convince myself that it works in
general too.

This patch has the updated hash table and all the other suggested patches
integrated in, it compiles and passes both the test suite and our tests.

 lib/ChangeLog|   5 +
 lib/Makefile.am  |   4 +-
 lib/dynamicsizehash_concurrent.c | 482 +++
 lib/dynamicsizehash_concurrent.h | 118 
 libdw/ChangeLog  |  12 +
 libdw/dwarf_abbrev_hash.c|   2 +-
 libdw/dwarf_abbrev_hash.h|   3 +-
 libdw/dwarf_formref_die.c|   2 +-
 libdw/dwarf_getabbrev.c  |   2 +-
 libdw/dwarf_sig8_hash.c  |   2 +-
 libdw/dwarf_sig8_hash.h  |   9 +-
 libdw/dwarf_tag.c|   2 +-
 12 files changed, 632 insertions(+), 11 deletions(-)
 create mode 100644 lib/dynamicsizehash_concurrent.c
 create mode 100644 lib/dynamicsizehash_concurrent.h

diff --git a/lib/ChangeLog b/lib/ChangeLog
index 3799c3aa..51c79841 100644
--- a/lib/ChangeLog
+++ b/lib/ChangeLog
@@ -1,3 +1,8 @@
+2019-08-25  Srđan Milaković  
+
+   * dynamicsizehash_concurrent.{c,h}: New files.
+   * Makefile.am (noinst_HEADERS): Added dynamicsizehash_concurrent.h.
+
 2019-08-25  Jonathon Anderson  
 
* stdatomic-fbsd.h: New file, taken from FreeBSD.
diff --git a/lib/Makefile.am b/lib/Makefile.am
index 3086cf06..97bf7329 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -39,8 +39,8 @@ libeu_a_SOURCES = 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
-EXTRA_DIST = dynamicsizehash.c
+atomics.h stdatomic-fbsd.h dynamicsizehash_concurrent.h
+EXTRA_DIST = dynamicsizehash.c dynamicsizehash_concurrent.c
 
 if !GPROF
 xmalloc_CFLAGS = -ffunction-sections
diff --git a/lib/dynamicsizehash_concurrent.c b/lib/dynamicsizehash_concurrent.c
new file mode 100644
index ..2d53bec6
--- /dev/null
+++ b/lib/dynamicsizehash_concurrent.c
@@ -0,0 +1,482 @@
+/* Copyright (C) 2000-2019 Red Hat, Inc.
+   This file is part of elfutils.
+   Written by Srdan Milakovic , 2019.
+   Derived from Ulrich Drepper , 2000.
+
+   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; wit

patch 3/3 debuginfod client interruptability

2019-11-04 Thread Frank Ch. Eigler
Hi -

At the wise counsel of gdb folks such as  and :

debuginfod 3/3: client interruptability

For interactive clients such as gdb, interruptibility is important for
usability during longer downloads.  This patchset adds a
download-progress callback function to the debuginfod client library,
with which a caller app can interrupt a download as well as be
notified of its quantitative progress.

diff --git a/debuginfod/ChangeLog b/debuginfod/ChangeLog
index b5679a2f9d16..34713746350d 100644
--- a/debuginfod/ChangeLog
+++ b/debuginfod/ChangeLog
@@ -1,3 +1,18 @@
+2019-11-04  Frank Ch. Eigler  
+
+   * debuginfo-client.c (debuginfod_set_progressfn): New function
+   for progress/interrupt callback.
+   (debuginfod_clean_cache, debuginfod_query_server): Call it.
+   * debuginfo.h: Declare it.
+   * debuginfod_set_progressfn.3, *_find_debuginfo.3: Document it.
+   * Makefile.am: Install it.
+   * libdebuginfod.map: Export it all under ELFUTILS_0.178 symversion.
+
+   * debuginfod-find.c: Add -v option to activate progress cb.
+   * debuginfod-find.1: Document it.
+   * debuginfod.cxx: Add $DEBUGINFOD_TEST_WEBAPI_SLEEP env var
+   to insert sleep in webapi callbacks, to help manual testing.
+
 2019-10-28  Frank Ch. Eigler  
 
* debuginfod.cxx: New file: debuginfod server.
diff --git a/debuginfod/Makefile.am b/debuginfod/Makefile.am
index 6e5c7290e68d..790e42317972 100644
--- a/debuginfod/Makefile.am
+++ b/debuginfod/Makefile.am
@@ -60,7 +60,7 @@ debuginfod_SOURCES = debuginfod.cxx
 debuginfod_cxx_CXXFLAGS = -Wno-unused-functions
 # g++ 4.8 on rhel7 otherwise errors gthr-default.h / 
__gthrw2(__gthrw_(__pthread_key_create) undefs
 dist_man8_MANS = debuginfod.8
-dist_man3_MANS = debuginfod_find_debuginfo.3 debuginfod_find_source.3 
debuginfod_find_executable.3
+dist_man3_MANS = debuginfod_find_debuginfo.3 debuginfod_find_source.3 
debuginfod_find_executable.3 debuginfod_set_progressfn.3
 dist_man1_MANS = debuginfod-find.1
 debuginfod_LDADD = $(libdw) $(libelf) $(libeu) $(libdebuginfod) 
$(libmicrohttpd_LIBS) $(libcurl_LIBS) $(sqlite3_LIBS) $(libarchive_LIBS) 
-lpthread -ldl
 
diff --git a/debuginfod/debuginfod-client.c b/debuginfod/debuginfod-client.c
index dd8d99c7af17..6a1ffbf7455f 100644
--- a/debuginfod/debuginfod-client.c
+++ b/debuginfod/debuginfod-client.c
@@ -28,6 +28,7 @@
 
 #include "config.h"
 #include "debuginfod.h"
+#include "atomics.h"
 #include 
 #include 
 #include 
@@ -77,6 +78,9 @@ static const char url_delim_char = ' ';
 static const char *server_timeout_envvar = DEBUGINFOD_TIMEOUT_ENV_VAR;
 static int server_timeout = 5;
 
+/* Progress/interrupt callback function. */
+static debuginfod_progressfn_t progressfn;
+
 /* Data associated with a particular CURL easy handle. Passed to
the write callback.  */
 struct handle_data
@@ -207,8 +211,14 @@ debuginfod_clean_cache(char *cache_path, char 
*interval_path, char *max_unused_p
 return -errno;
 
   FTSENT *f;
+  long files = 0;
   while ((f = fts_read(fts)) != NULL)
 {
+  files++;
+  if (progressfn) /* inform/check progress callback */
+if ((*progressfn) (files, 0))
+  break;
+
   switch (f->fts_info)
 {
 case FTS_F:
@@ -237,7 +247,8 @@ debuginfod_clean_cache(char *cache_path, char 
*interval_path, char *max_unused_p
 /* Query each of the server URLs found in $DEBUGINFOD_URLS for the file
with the specified build-id, type (debuginfo, executable or source)
and filename. filename may be NULL. If found, return a file
-   descriptor for the target, otherwise return an error code.  */
+   descriptor for the target, otherwise return an error code.
+*/
 static int
 debuginfod_query_server (const unsigned char *build_id,
  int build_id_len,
@@ -446,10 +457,35 @@ debuginfod_query_server (const unsigned char *build_id,
 
   /* Query servers in parallel.  */
   int still_running;
+  unsigned loops = 0;
   do
 {
   CURLMcode curl_res;
 
+  if (progressfn) /* inform/check progress callback */
+{
+  loops ++;
+  long pa = loops; /* default params for progress callback */
+  long pb = 0;
+  if (target_handle) /* we've committed to a server; report its 
download progress */
+{
+  curl_off_t cl, dl;
+  curl_res = curl_easy_getinfo(target_handle,
+   CURLINFO_SIZE_DOWNLOAD_T,
+   &dl);
+  if (curl_res == 0 && dl >= 0)
+pa = (dl > LONG_MAX ? LONG_MAX : (long)dl);
+
+  curl_res = curl_easy_getinfo(target_handle,
+   CURLINFO_CONTENT_LENGTH_DOWNLOAD_T,
+   &cl);
+  if (curl_res == 0 && cl >= 0)
+pb = (cl > LONG_MAX ? LONG_MAX : (long)cl);
+}
+  if ((*progressfn) (pa, pb))
+