From: Nick Alcock <nick.alcock@oracle.com>
To: binutils@sourceware.org
Subject: [PATCH 22/59] libctf, hash: save per-item space when no key/item freeing function
Date: Wed, 1 Jul 2020 00:31:09 +0100 [thread overview]
Message-ID: <20200630233146.338613-23-nick.alcock@oracle.com> (raw)
In-Reply-To: <20200630233146.338613-1-nick.alcock@oracle.com>
The libctf dynhash hashtab abstraction supports per-hashtab arbitrary
key/item freeing functions -- but it also has a constant slot type that
holds both key and value requested by the user, so it needs to use its
own freeing function to free that -- and it has nowhere to store the
freeing functions the caller requested.
So it copies them into every hash item, bloating every slot, even though
all items in a given hash table must have the same key and value freeing
functions.
So point back to the owner using a back-pointer, but don't even spend
space in the item or the hashtab allocating those freeing functions
unless necessary: if none are needed, we can simply arrange to not pass
in ctf_dynhash_item_free as a del_f to hashtab_create_alloc, and none of
those fields will ever be accessed.
The only downside is that this makes the code sensitive to the order of
fields in the ctf_helem_t and ctf_hashtab_t: but the deduplicator
allocates so many hash tables that doing this alone cuts memory usage
during deduplication by about 10%. (libiberty hashtab itself has a lot
of per-hashtab bloat: in the future we might trim that down, or make a
trimmer version.)
libctf/
* ctf-hash.c (ctf_helem_t) <key_free>: Remove.
<value_free>: Likewise.
<owner>: New.
(ctf_dynhash_item_free): Indirect through the owner.
(ctf_dynhash_create): Only pass in ctf_dynhash_item_free and
allocate space for the key_free and value_free fields fields
if necessary.
(ctf_hashtab_insert): Likewise. Fix OOM errno value.
(ctf_dynhash_insert): Only access ctf_hashtab's key_free and
value_free if they will exist. Set the slot's owner, but only
if it exists.
(ctf_dynhash_remove): Adjust.
---
libctf/ctf-hash.c | 68 ++++++++++++++++++++++++++++++++---------------
1 file changed, 47 insertions(+), 21 deletions(-)
diff --git a/libctf/ctf-hash.c b/libctf/ctf-hash.c
index 1c37d7515b4..caefd99c37f 100644
--- a/libctf/ctf-hash.c
+++ b/libctf/ctf-hash.c
@@ -31,14 +31,19 @@
not support removal. These can be implemented by the same underlying hashmap
if you wish. */
+/* The helem is used for general key/value mappings in both the ctf_hash and
+ ctf_dynhash: the owner may not have space allocated for it, and will be
+ garbage (not NULL!) in that case. */
+
typedef struct ctf_helem
{
void *key; /* Either a pointer, or a coerced ctf_id_t. */
void *value; /* The value (possibly a coerced int). */
- ctf_hash_free_fun key_free;
- ctf_hash_free_fun value_free;
+ ctf_dynhash_t *owner; /* The hash that owns us. */
} ctf_helem_t;
+/* Equally, the key_free and value_free may not exist. */
+
struct ctf_dynhash
{
struct htab *htab;
@@ -106,17 +111,17 @@ ctf_hash_eq_type_mapping_key (const void *a, const void *b)
/* The dynhash, used for hashes whose size is not known at creation time. */
-/* Free a single ctf_helem. */
+/* Free a single ctf_helem with arbitrary key/value functions. */
static void
ctf_dynhash_item_free (void *item)
{
ctf_helem_t *helem = item;
- if (helem->key_free && helem->key)
- helem->key_free (helem->key);
- if (helem->value_free && helem->value)
- helem->value_free (helem->value);
+ if (helem->owner->key_free && helem->key)
+ helem->owner->key_free (helem->key);
+ if (helem->owner->value_free && helem->value)
+ helem->owner->value_free (helem->value);
free (helem);
}
@@ -125,21 +130,31 @@ ctf_dynhash_create (ctf_hash_fun hash_fun, ctf_hash_eq_fun eq_fun,
ctf_hash_free_fun key_free, ctf_hash_free_fun value_free)
{
ctf_dynhash_t *dynhash;
+ htab_del del = ctf_dynhash_item_free;
- dynhash = malloc (sizeof (ctf_dynhash_t));
+ if (key_free || value_free)
+ dynhash = malloc (sizeof (ctf_dynhash_t));
+ else
+ dynhash = malloc (offsetof (ctf_dynhash_t, key_free));
if (!dynhash)
return NULL;
- /* 7 is arbitrary and untested for now.. */
+ if (key_free == NULL && value_free == NULL)
+ del = free;
+
+ /* 7 is arbitrary and untested for now. */
if ((dynhash->htab = htab_create_alloc (7, (htab_hash) hash_fun, eq_fun,
- ctf_dynhash_item_free, xcalloc, free)) == NULL)
+ del, xcalloc, free)) == NULL)
{
free (dynhash);
return NULL;
}
- dynhash->key_free = key_free;
- dynhash->value_free = value_free;
+ if (key_free || value_free)
+ {
+ dynhash->key_free = key_free;
+ dynhash->value_free = value_free;
+ }
return dynhash;
}
@@ -162,13 +177,18 @@ ctf_hashtab_insert (struct htab *htab, void *key, void *value,
if (!slot)
{
- errno = -ENOMEM;
+ errno = ENOMEM;
return NULL;
}
if (!*slot)
{
- *slot = malloc (sizeof (ctf_helem_t));
+ /* Only spend space on the owner if we're going to use it: if there is a
+ key or value freeing function. */
+ if (key_free || value_free)
+ *slot = malloc (sizeof (ctf_helem_t));
+ else
+ *slot = malloc (offsetof (ctf_helem_t, owner));
if (!*slot)
return NULL;
(*slot)->key = key;
@@ -188,19 +208,25 @@ int
ctf_dynhash_insert (ctf_dynhash_t *hp, void *key, void *value)
{
ctf_helem_t *slot;
+ ctf_hash_free_fun key_free = NULL, value_free = NULL;
+ if (hp->htab->del_f == ctf_dynhash_item_free)
+ {
+ key_free = hp->key_free;
+ value_free = hp->value_free;
+ }
slot = ctf_hashtab_insert (hp->htab, key, value,
- hp->key_free, hp->value_free);
+ key_free, value_free);
if (!slot)
return errno;
- /* We need to keep the key_free and value_free around in each item because the
- del function has no visibility into the hash as a whole, only into the
- individual items. */
+ /* Keep track of the owner, so that the del function can get at the key_free
+ and value_free functions. Only do this if one of those functions is set:
+ if not, the owner is not even present in the helem. */
- slot->key_free = hp->key_free;
- slot->value_free = hp->value_free;
+ if (key_free || value_free)
+ slot->owner = hp;
return 0;
}
@@ -208,7 +234,7 @@ ctf_dynhash_insert (ctf_dynhash_t *hp, void *key, void *value)
void
ctf_dynhash_remove (ctf_dynhash_t *hp, const void *key)
{
- ctf_helem_t hep = { (void *) key, NULL, NULL, NULL };
+ ctf_helem_t hep = { (void *) key, NULL, NULL };
htab_remove_elt (hp->htab, &hep);
}
--
2.27.0.247.g3dff7de930
next prev parent reply other threads:[~2020-06-30 23:34 UTC|newest]
Thread overview: 80+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-06-30 23:30 [PATCH 00/59] Deduplicating CTF linker Nick Alcock
2020-06-30 23:30 ` [PATCH 01/59] include, libctf: typo fixes Nick Alcock
2020-06-30 23:30 ` [PATCH 02/59] libctf: restructure error handling to reduce relocations Nick Alcock
2020-07-22 9:31 ` [PATCH 02/59] fixup! " Nick Alcock
2020-06-30 23:30 ` [PATCH 03/59] libctf, create: support addition of references to the unimplemented type Nick Alcock
2020-06-30 23:30 ` [PATCH 04/59] libctf, create: do not corrupt function types' arglists at insertion time Nick Alcock
2020-06-30 23:30 ` [PATCH 05/59] libctf, create: add explicit casts for variables' and slices' types Nick Alcock
2020-06-30 23:30 ` [PATCH 06/59] libctf, types: allow ctf_type_reference of dynamic slices Nick Alcock
2020-06-30 23:30 ` [PATCH 07/59] libctf, open: drop unnecessary historical wart around forwards Nick Alcock
2020-06-30 23:30 ` [PATCH 08/59] libctf, create: member names of "" and NULL should be the same Nick Alcock
2020-06-30 23:30 ` [PATCH 09/59] libctf, create: fix addition of anonymous struct/union members Nick Alcock
2020-06-30 23:30 ` [PATCH 10/59] libctf, create: empty dicts are dirty to start with Nick Alcock
2020-06-30 23:30 ` [PATCH 11/59] libctf, types: support slices of anything terminating in an int Nick Alcock
2020-06-30 23:30 ` [PATCH 12/59] libctf, types: ints, floats and typedefs with no name are invalid Nick Alcock
2020-06-30 23:31 ` [PATCH 13/59] libctf, archive: stop ctf_arc_bufopen triggering crazy unmaps Nick Alcock
2020-06-30 23:31 ` [PATCH 14/59] libctf: having debugging enabled is unlikely Nick Alcock
2020-06-30 23:31 ` [PATCH 15/59] libctf: add ctf_type_name_raw Nick Alcock
2020-06-30 23:31 ` [PATCH 16/59] libctf: add ctf_type_kind_forwarded Nick Alcock
2020-06-30 23:31 ` [PATCH 17/59] libctf: add ctf_member_count Nick Alcock
2020-06-30 23:31 ` [PATCH 18/59] libctf: add ctf_archive_count Nick Alcock
2020-06-30 23:31 ` [PATCH 19/59] libctf: fix __extension__ with non-GNU C compilers Nick Alcock
2020-06-30 23:31 ` [PATCH 20/59] libctf: add new dynhash functions Nick Alcock
2020-06-30 23:31 ` [PATCH 21/59] libctf, hash: improve insertion of existing keys into dynhashes Nick Alcock
2020-06-30 23:31 ` Nick Alcock [this message]
2020-06-30 23:31 ` [PATCH 23/59] libctf, hash: introduce the ctf_dynset Nick Alcock
2020-06-30 23:31 ` [PATCH 24/59] libctf: move existing inlines into ctf-inlines.h Nick Alcock
2020-06-30 23:31 ` [PATCH 25/59] libctf: add ctf_forwardable_kind Nick Alcock
2020-06-30 23:31 ` [PATCH 26/59] libctf: add ctf_ref Nick Alcock
2020-06-30 23:31 ` [PATCH 27/59] libctf, next: introduce new class of easier-to-use iterators Nick Alcock
2020-07-22 9:29 ` [PATCH 27/59] fixup! " Nick Alcock
2020-06-30 23:31 ` [PATCH 28/59] libctf, next, hash: add dynhash and dynset _next iteration Nick Alcock
2020-06-30 23:31 ` [PATCH 29/59] libctf: pass the thunk down properly when wrapping qsort_r Nick Alcock
2020-06-30 23:31 ` [PATCH 30/59] libctf: error out on corrupt CTF with invalid header flags Nick Alcock
2020-06-30 23:31 ` [PATCH 31/59] libctf, types: ensure the emission of ECTF_NOPARENT Nick Alcock
2020-06-30 23:31 ` [PATCH 32/59] libctf, ld, binutils: add textual error/warning reporting for libctf Nick Alcock
2020-06-30 23:31 ` [PATCH 33/59] libctf, types: enhance ctf_type_aname to print function arg types Nick Alcock
2020-06-30 23:31 ` [PATCH 34/59] libctf, decl: avoid leaks of the formatted string on error Nick Alcock
2020-06-30 23:31 ` [PATCH 35/59] libctf, dump: migrate towards dumping errors rather than truncation Nick Alcock
2020-06-30 23:31 ` [PATCH 36/59] libctf, dump: fix slice dumping Nick Alcock
2020-06-30 23:31 ` [PATCH 37/59] libctf, open: fix opening CTF in binaries with no symtab Nick Alcock
2020-06-30 23:31 ` [PATCH 38/59] libctf, archive: fix bad error message Nick Alcock
2020-06-30 23:31 ` [PATCH 39/59] libctf: check for vasprintf Nick Alcock
2020-06-30 23:31 ` [PATCH 40/59] libctf: rename the type_mapping_key to type_key Nick Alcock
2020-07-22 9:35 ` [PATCH 40/59] fixup! " Nick Alcock
2020-06-30 23:31 ` [PATCH 41/59] libctf: sort out potential refcount loops Nick Alcock
2020-06-30 23:31 ` [PATCH 42/59] libctf: drop error-prone ctf_strerror Nick Alcock
2020-06-30 23:31 ` [PATCH 43/59] libctf, link: add lazy linking: clean up input members: err/warn cleanup Nick Alcock
2020-06-30 23:31 ` [PATCH 44/59] libctf, link: fix ctf_link_write fd leak Nick Alcock
2020-06-30 23:31 ` [PATCH 45/59] libctf, link: redo cu-mapping handling Nick Alcock
2020-06-30 23:31 ` [PATCH 46/59] ctf, link: fix spurious conflicts of variables in the variable section Nick Alcock
2020-07-01 10:40 ` Nick Alcock
2020-06-30 23:31 ` [PATCH 47/59] libctf, link: add the ability to filter out variables from the link Nick Alcock
2020-06-30 23:31 ` [PATCH 48/59] libctf: add SHA-1 support for libctf Nick Alcock
2020-06-30 23:31 ` [PATCH 49/59] libctf, dedup: add new configure option --enable-libctf-hash-debugging Nick Alcock
2020-07-22 9:30 ` [PATCH 49/59] fixup! " Nick Alcock
2020-06-30 23:31 ` [PATCH 50/59] libctf, dedup: add deduplicator Nick Alcock
2020-07-22 9:33 ` [PATCH 50/59] squash! " Nick Alcock
2020-07-22 9:33 ` [PATCH 50/59] fixup! " Nick Alcock
2020-07-22 9:34 ` Nick Alcock
2020-06-30 23:31 ` [PATCH 51/59] libctf, link: add CTF_LINK_OMIT_VARIABLES_SECTION Nick Alcock
2020-06-30 23:31 ` [PATCH 52/59] libctf, link: tie in the deduplicating linker Nick Alcock
2020-07-22 9:36 ` [PATCH 52/59] fixup! " Nick Alcock
2020-06-30 23:31 ` [PATCH 53/59] binutils: objdump: ctf: drop incorrect linefeeds Nick Alcock
2020-06-30 23:31 ` [PATCH 54/59] ld: Reformat CTF errors into warnings Nick Alcock
2020-06-30 23:31 ` [PATCH 55/59] ld: new options --ctf-variables and --ctf-share-types Nick Alcock
2020-06-30 23:31 ` [PATCH 56/59] binutils, testsuite: allow compilation before doing run_dump_test Nick Alcock
2020-06-30 23:31 ` [PATCH 57/59] ld: new CTF testsuite Nick Alcock
2020-06-30 23:31 ` [PATCH 58/59] ld, testsuite: only run CTF tests when ld and GCC support CTF Nick Alcock
2020-07-22 9:32 ` [PATCH 58/59] fixup! " Nick Alcock
2020-06-30 23:31 ` [PATCH 59/59] ld: do not produce one empty output .ctf section for every input .ctf Nick Alcock
2020-07-14 21:31 ` [PATCH 00/59] Deduplicating CTF linker Nick Alcock
2020-07-20 5:49 ` Alan Modra
2020-07-20 21:06 ` Nick Alcock
2020-07-22 9:39 ` [PATCH 0/4] fallout of various portability testing Nick Alcock
2020-07-22 9:39 ` [PATCH 1/4] ld, testsuite: do not run CTF tests at all on non-ELF for now Nick Alcock
2020-07-22 9:39 ` [PATCH 2/4] libctf, binutils: fix big-endian libctf archive opening Nick Alcock
2020-07-22 9:39 ` [PATCH 3/4] libctf: fix isspace casts Nick Alcock
2020-07-22 9:39 ` [PATCH 4/4] libctf: fixes for systems on which sizeof (void *) > sizeof (long) Nick Alcock
2020-07-22 14:06 ` [PATCH 0/4] fallout of various portability testing Nick Alcock
2020-07-22 17:08 ` [PATCH 00/59] Deduplicating CTF linker Nick Alcock
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=20200630233146.338613-23-nick.alcock@oracle.com \
--to=nick.alcock@oracle.com \
--cc=binutils@sourceware.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).