gpg: New caching functions.

* g10/objcache.c: New.
* g10/objcache.h: New.
* g10/Makefile.am (common_source): Add them.
* g10/gpg.c: Include objcache.h.
(g10_exit): Call objcache_dump_stats.
* g10/getkey.c: Include objcache.h.
(get_primary_uid, release_keyid_list): Remove.
(cache_user_id): Remove.
(finish_lookup): Call the new cache_put_keyblock instead of
cache_user_id.
(get_user_id_string): Remove code for mode 2.
(get_user_id): Implement using cache_get_uid_bykid.
--

This generic caching module is better than the ad-hoc code we used in
getkey.c.  More cleanup in getkey is still required but it is a
start.  There is also a small performance increase with the new cache:

With a large keyring and --list-sigs I get these numbers:

|      | before     | after      |
|------+------------+------------|
| real | 14m1.028s  | 12m16.186s |
| user |  2m18.484s |  1m36.040s |
| sys  | 11m42.420s | 10m40.044s |

Note the speedup in the user time which is due to the improved cache
algorithm.  This is obvious, because the old cache was just a long
linked list; the new cache are two hash tables.

Signed-off-by: Werner Koch <[email protected]>

5 files changed, 702 insertions, 119 deletions

diff --git a/g10/Makefile.am b/g10/Makefile.am
index 3b4464364..884b4749b 100644
--- a/g10/Makefile.am
+++ b/g10/Makefile.am
@@ -121,6 +121,7 @@ common_source =  \
 	      sig-check.c	\
 	      keylist.c 	\
 	      pkglue.c pkglue.h \
+	      objcache.c objcache.h \
 	      ecdh.c
 
 gpg_sources = server.c          \
diff --git a/g10/getkey.c b/g10/getkey.c
index 49e237add..34bc4bf0e 100644
--- a/g10/getkey.c
+++ b/g10/getkey.c
@@ -36,6 +36,7 @@
 #include "../common/i18n.h"
 #include "keyserver-internal.h"
 #include "call-agent.h"
+#include "objcache.h"
 #include "../common/host2net.h"
 #include "../common/mbox-util.h"
 #include "../common/status.h"
@@ -141,7 +142,6 @@ typedef struct user_id_db
   char name[1];
 } *user_id_db_t;
 static user_id_db_t user_id_db;
-static int uid_cache_entries;	/* Number of entries in uid cache. */
 
 static void merge_selfsigs (ctrl_t ctrl, kbnode_t keyblock);
 static int lookup (ctrl_t ctrl, getkey_ctx_t ctx, int want_secret,
@@ -263,115 +263,6 @@ user_id_not_found_utf8 (void)
 
 
 
-/* Return the user ID from the given keyblock.
- * We use the primary uid flag which has been set by the merge_selfsigs
- * function.  The returned value is only valid as long as the given
- * keyblock is not changed.  */
-static const char *
-get_primary_uid (KBNODE keyblock, size_t * uidlen)
-{
-  KBNODE k;
-  const char *s;
-
-  for (k = keyblock; k; k = k->next)
-    {
-      if (k->pkt->pkttype == PKT_USER_ID
-	  && !k->pkt->pkt.user_id->attrib_data
-	  && k->pkt->pkt.user_id->flags.primary)
-	{
-	  *uidlen = k->pkt->pkt.user_id->len;
-	  return k->pkt->pkt.user_id->name;
-	}
-    }
-  s = user_id_not_found_utf8 ();
-  *uidlen = strlen (s);
-  return s;
-}
-
-
-static void
-release_keyid_list (keyid_list_t k)
-{
-  while (k)
-    {
-      keyid_list_t k2 = k->next;
-      xfree (k);
-      k = k2;
-    }
-}
-
-/****************
- * Store the association of keyid and userid
- * Feed only public keys to this function.
- */
-static void
-cache_user_id (KBNODE keyblock)
-{
-  user_id_db_t r;
-  const char *uid;
-  size_t uidlen;
-  keyid_list_t keyids = NULL;
-  KBNODE k;
-  size_t n;
-
-  for (k = keyblock; k; k = k->next)
-    {
-      if (k->pkt->pkttype == PKT_PUBLIC_KEY
-	  || k->pkt->pkttype == PKT_PUBLIC_SUBKEY)
-	{
-	  keyid_list_t a = xmalloc_clear (sizeof *a);
-	  /* Hmmm: For a long list of keyids it might be an advantage
-	   * to append the keys.  */
-          fingerprint_from_pk (k->pkt->pkt.public_key, a->fpr, &n);
-          a->fprlen = n;
-	  keyid_from_pk (k->pkt->pkt.public_key, a->keyid);
-	  /* First check for duplicates.  */
-	  for (r = user_id_db; r; r = r->next)
-	    {
-	      keyid_list_t b;
-
-	      for (b = r->keyids; b; b = b->next)
-		{
-		  if (b->fprlen == a->fprlen
-                      && !memcmp (b->fpr, a->fpr, a->fprlen))
-		    {
-		      if (DBG_CACHE)
-			log_debug ("cache_user_id: already in cache\n");
-		      release_keyid_list (keyids);
-		      xfree (a);
-		      return;
-		    }
-		}
-	    }
-	  /* Now put it into the cache.  */
-	  a->next = keyids;
-	  keyids = a;
-	}
-    }
-  if (!keyids)
-    BUG (); /* No key no fun.  */
-
-
-  uid = get_primary_uid (keyblock, &uidlen);
-
-  if (uid_cache_entries >= MAX_UID_CACHE_ENTRIES)
-    {
-      /* fixme: use another algorithm to free some cache slots */
-      r = user_id_db;
-      user_id_db = r->next;
-      release_keyid_list (r->keyids);
-      xfree (r);
-      uid_cache_entries--;
-    }
-  r = xmalloc (sizeof *r + uidlen - 1);
-  r->keyids = keyids;
-  r->len = uidlen;
-  memcpy (r->name, uid, r->len);
-  r->next = user_id_db;
-  user_id_db = r;
-  uid_cache_entries++;
-}
-
 
 /* Disable and drop the public key cache (which is filled by
    cache_public_key and get_pubkey).  Note: there is currently no way
@@ -3627,7 +3518,7 @@ finish_lookup (kbnode_t keyblock, unsigned int req_usage, int want_exact,
       xfree (tempkeystr);
     }
 
-  cache_user_id (keyblock);
+  cache_put_keyblock (keyblock);
 
   return latest_key ? latest_key : keyblock; /* Found.  */
 }
@@ -3848,6 +3739,7 @@ get_user_id_string (ctrl_t ctrl, u32 * keyid, int mode, size_t *r_len,
   int pass = 0;
   char *p;
 
+  log_assert (mode != 2);
   if (r_nouid)
     *r_nouid = 0;
 
@@ -3862,13 +3754,7 @@ get_user_id_string (ctrl_t ctrl, u32 * keyid, int mode, size_t *r_len,
 		{
                   if (mode == 2)
                     {
-                      /* An empty string as user id is possible.  Make
-                         sure that the malloc allocates one byte and
-                         does not bail out.  */
-                      p = xmalloc (r->len? r->len : 1);
-                      memcpy (p, r->name, r->len);
-                      if (r_len)
-                        *r_len = r->len;
+                      BUG ();
                     }
                   else
                     {
@@ -3926,7 +3812,31 @@ get_long_user_id_string (ctrl_t ctrl, u32 * keyid)
 char *
 get_user_id (ctrl_t ctrl, u32 *keyid, size_t *rn, int *r_nouid)
 {
-  return get_user_id_string (ctrl, keyid, 2, rn, r_nouid);
+  char *name;
+  unsigned int namelen;
+
+  if (r_nouid)
+    *r_nouid = 0;
+
+  name = cache_get_uid_bykid (keyid, &namelen);
+  if (!name)
+    {
+      /* Get it so that the cache will be filled.  */
+      if (!get_pubkey (ctrl, NULL, keyid))
+        name = cache_get_uid_bykid (keyid, &namelen);
+    }
+
+  if (!name)
+    {
+      name = xstrdup (user_id_not_found_utf8 ());
+      namelen = strlen (name);
+      if (r_nouid)
+        *r_nouid = 1;
+    }
+
+  if (rn && name)
+    *rn = namelen;
+  return name;
 }
 
 
diff --git a/g10/gpg.c b/g10/gpg.c
index 1ab7b0497..b46d22690 100644
--- a/g10/gpg.c
+++ b/g10/gpg.c
@@ -59,6 +59,7 @@
 #include "../common/asshelp.h"
 #include "call-dirmngr.h"
 #include "tofu.h"
+#include "objcache.h"
 #include "../common/init.h"
 #include "../common/mbox-util.h"
 #include "../common/shareddefs.h"
@@ -5223,6 +5224,7 @@ g10_exit( int rc )
     {
       keydb_dump_stats ();
       sig_check_dump_stats ();
+      objcache_dump_stats ();
       gcry_control (GCRYCTL_DUMP_MEMORY_STATS);
       gcry_control (GCRYCTL_DUMP_RANDOM_STATS);
     }
diff --git a/g10/objcache.c b/g10/objcache.c
new file mode 100644
index 000000000..7eb92cd0d
--- /dev/null
+++ b/g10/objcache.c
@@ -0,0 +1,642 @@
+/* objcache.c - Caching functions for keys and user ids.
+ * Copyright (C) 2019 g10 Code GmbH
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG 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 a copy of the GNU General Public License
+ * along with this program; if not, see <https://www.gnu.org/licenses/>.
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include <config.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "gpg.h"
+#include "../common/util.h"
+#include "packet.h"
+#include "keydb.h"
+#include "options.h"
+#include "objcache.h"
+
+/* Note that max value for uid_items is actually a the threshold when
+ * we start to look for ietms which can be removed.  */
+#define NO_OF_UID_ITEM_BUCKETS    107
+#define MAX_UID_ITEMS_PER_BUCKET  20
+
+#define NO_OF_KEY_ITEM_BUCKETS    383
+#define MAX_KEY_ITEMS_PER_BUCKET  20
+
+
+/* An object to store a user id.  This describes an item in the linked
+ * lists of a bucket in hash table.  The reference count will
+ * eventually be used to remove items from the table.  */
+typedef struct uid_item_s
+{
+  struct uid_item_s *next;
+  unsigned int refcount;  /* The reference count for this item.   */
+  unsigned int namelen;   /* The length of the UID sans the nul.  */
+  char name[1];
+} *uid_item_t;
+
+static uid_item_t *uid_table; /* Hash table for with user ids.  */
+static size_t uid_table_size; /* Number of allocated buckets.   */
+static unsigned int uid_table_max;    /* Max. # of items in a bucket.  */
+static unsigned int uid_table_added;  /* # of items added.   */
+static unsigned int uid_table_dropped;/* # of items dropped.  */
+
+
+/* An object to store properties of a key.  Note that this can be used
+ * for a primary or a subkey.  The key is linked to a user if that
+ * exists.  */
+typedef struct key_item_s
+{
+  struct key_item_s *next;
+  unsigned int usecount;
+  byte fprlen;
+  char fpr[MAX_FINGERPRINT_LEN];
+  u32 keyid[2];
+  uid_item_t ui;          /* NULL of a ref'ed user id item.      */
+} *key_item_t;
+
+static key_item_t *key_table; /* Hash table with the keys.      */
+static size_t key_table_size; /* Number of allocated buckents.  */
+static unsigned int key_table_max;    /* Max. # of items in a bucket.  */
+static unsigned int key_table_added;  /* # of items added.   */
+static unsigned int key_table_dropped;/* # of items dropped.  */
+static key_item_t key_item_attic;     /* List of freed items.  */
+
+
+
+/* Dump stats.  */
+void
+objcache_dump_stats (void)
+{
+  unsigned int idx;
+  int len, minlen, maxlen;
+  unsigned int count, attic, empty;
+  key_item_t ki;
+  uid_item_t ui;
+
+  count = empty = 0;
+  minlen = -1;
+  maxlen = 0;
+  for (idx = 0; idx < key_table_size; idx++)
+    {
+      len = 0;
+      for (ki = key_table[idx]; ki; ki = ki->next)
+        {
+          count++;
+          len++;
+          /* log_debug ("key bucket %u: kid=%08lX used=%u ui=%p\n", */
+          /*            idx, (ulong)ki->keyid[0], ki->usecount, ki->ui); */
+        }
+      if (len > maxlen)
+        maxlen = len;
+
+      if (!len)
+        empty++;
+      else if (minlen == -1 || len < minlen)
+        minlen = len;
+    }
+  for (attic=0, ki = key_item_attic; ki; ki = ki->next)
+    attic++;
+  log_info ("objcache: keys=%u/%u/%u chains=%u,%d..%d buckets=%zu/%u"
+            " attic=%u\n",
+            count, key_table_added, key_table_dropped,
+            empty, minlen > 0? minlen : 0, maxlen,
+            key_table_size, key_table_max, attic);
+
+  count = empty = 0;
+  minlen = -1;
+  maxlen = 0;
+  for (idx = 0; idx < uid_table_size; idx++)
+    {
+      len = 0;
+      for (ui = uid_table[idx]; ui; ui = ui->next)
+        {
+          count++;
+          len++;
+          /* log_debug ("uid bucket %u: %p ref=%u l=%u (%.20s)\n", */
+          /*            idx, ui, ui->refcount, ui->namelen, ui->name); */
+        }
+      if (len > maxlen)
+        maxlen = len;
+
+      if (!len)
+        empty++;
+      else if (minlen == -1 || len < minlen)
+        minlen = len;
+    }
+  log_info ("objcache: uids=%u/%u/%u chains=%u,%d..%d buckets=%zu/%u\n",
+            count, uid_table_added, uid_table_dropped,
+            empty, minlen > 0? minlen : 0, maxlen,
+            uid_table_size, uid_table_max);
+}
+
+
+
+/* The hash function we use for the uid_table.  Must not call a system
+ * function.  */
+static inline unsigned int
+uid_table_hasher (const char *name, unsigned namelen)
+{
+  const unsigned char *s = (const unsigned char*)name;
+  unsigned int hashval = 0;
+  unsigned int carry;
+
+  for (; namelen; namelen--, s++)
+    {
+      hashval = (hashval << 4) + *s;
+      if ((carry = (hashval & 0xf0000000)))
+        {
+          hashval ^= (carry >> 24);
+          hashval ^= carry;
+        }
+    }
+
+  return hashval % uid_table_size;
+}
+
+
+/* Run time allocation of the uid table.  This allows us to eventually
+ * add an option to gpg to control the size.  */
+static void
+uid_table_init (void)
+{
+  if (uid_table)
+    return;
+  uid_table_size = NO_OF_UID_ITEM_BUCKETS;
+  uid_table_max = MAX_UID_ITEMS_PER_BUCKET;
+  uid_table = xcalloc (uid_table_size, sizeof *uid_table);
+}
+
+
+static uid_item_t
+uid_item_ref (uid_item_t ui)
+{
+  if (ui)
+    ui->refcount++;
+  return ui;
+}
+
+static void
+uid_item_unref (uid_item_t uid)
+{
+  if (!uid)
+    return;
+  if (!uid->refcount)
+    log_fatal ("too many unrefs for uid_item\n");
+
+  uid->refcount--;
+  /* We do not release the item here because that would require that
+   * we locate the head of the list which has this item.  This will
+   * take too long and thus the item is removed when we need to purge
+   * some items for the list during uid_item_put.  */
+}
+
+
+/* Put (NAME,NAMELEN) into the UID_TABLE and return the item.  The
+ * reference count for that item is incremented.  NULL is return on an
+ * allocation error.  The caller should release the returned item
+ * using uid_item_unref.  */
+static uid_item_t
+uid_table_put (const char *name, unsigned int namelen)
+{
+  unsigned int hash;
+  uid_item_t ui;
+  unsigned int count;
+
+  if (!uid_table)
+    uid_table_init ();
+
+  hash = uid_table_hasher (name, namelen);
+  for (ui = uid_table[hash], count = 0; ui; ui = ui->next, count++)
+    if (ui->namelen == namelen && !memcmp (ui->name, name, namelen))
+      return uid_item_ref (ui);  /* Found.  */
+
+  /* If the bucket is full remove all unrefed items.  */
+  if (count >= uid_table_max)
+    {
+      uid_item_t ui_next, ui_prev, list_head, drop_head;
+
+      /* No syscalls from here .. */
+      list_head = uid_table[hash];
+      drop_head = NULL;
+      while (list_head && !list_head->refcount)
+        {
+          ui = list_head;
+          list_head = ui->next;
+          ui->next = drop_head;
+          drop_head = ui;
+        }
+      if ((ui_prev = list_head))
+        for (ui = ui_prev->next; ui; ui = ui_next)
+          {
+            ui_next = ui->next;
+            if (!ui->refcount)
+              {
+                ui->next = drop_head;
+                drop_head = ui;
+                ui_prev->next = ui_next;
+              }
+            else
+              ui_prev = ui;
+          }
+      uid_table[hash] = list_head;
+      /* ... to here */
+
+      for (ui = drop_head; ui; ui = ui_next)
+        {
+          ui_next = ui->next;
+          xfree (ui);
+          uid_table_dropped++;
+        }
+    }
+
+  count = uid_table_added + uid_table_dropped;
+  ui = xtrycalloc (1, sizeof *ui + namelen);
+  if (!ui)
+    return NULL;  /* Out of core.  */
+  if (count != uid_table_added + uid_table_dropped)
+    {
+      /* During the malloc another thread added an item.  Thus we need
+       * to check again.  */
+      uid_item_t ui_new = ui;
+      for (ui = uid_table[hash]; ui; ui = ui->next)
+        if (ui->namelen == namelen && !memcmp (ui->name, name, namelen))
+          {
+            /* Found.  */
+            xfree (ui_new);
+            return uid_item_ref (ui);
+          }
+      ui = ui_new;
+    }
+
+  memcpy (ui->name, name, namelen);
+  ui->name[namelen] = 0; /* Extra Nul so we can use it as a string.  */
+  ui->namelen = namelen;
+  ui->refcount = 1;
+  ui->next = uid_table[hash];
+  uid_table[hash] = ui;
+  uid_table_added++;
+  return ui;
+}
+
+
+
+/* The hash function we use for the key_table.  Must not call a system
+ * function.  */
+static inline unsigned int
+key_table_hasher (u32 *keyid)
+{
+  /* A fingerprint could be used directly as a hash value.  However,
+   * we use the keyid here because it is used in encrypted packets and
+   * older signatures to identify a key.  Since v4 keys the keyid is
+   * anyway a part of the fingerprint so it quickly extracted from a
+   * fingerprint.  Note that v3 keys are not supported by gpg.  */
+  return keyid[0] % key_table_size;
+}
+
+
+/* Run time allocation of the key table.  This allows us to eventually
+ * add an option to gpg to control the size.  */
+static void
+key_table_init (void)
+{
+  if (key_table)
+    return;
+  key_table_size = NO_OF_KEY_ITEM_BUCKETS;
+  key_table_max  = MAX_KEY_ITEMS_PER_BUCKET;
+  key_table = xcalloc (key_table_size, sizeof *key_table);
+}
+
+
+static void
+key_item_free (key_item_t ki)
+{
+  if (!ki)
+    return;
+  uid_item_unref (ki->ui);
+  ki->ui = NULL;
+  ki->next = key_item_attic;
+  key_item_attic = ki;
+}
+
+
+/* Get a key item from PK or if that is NULL from KEYID.  The
+ * reference count for that item is incremented.  NULL is return if it
+ * was not found.  */
+static key_item_t
+key_table_get (PKT_public_key *pk, u32 *keyid)
+{
+  unsigned int hash;
+  key_item_t ki, ki2;
+
+  if (!key_table)
+    key_table_init ();
+
+  if (pk)
+    {
+      byte fpr[MAX_FINGERPRINT_LEN];
+      size_t fprlen;
+      u32 tmpkeyid[2];
+
+      fingerprint_from_pk (pk, fpr, &fprlen);
+      keyid_from_pk (pk, tmpkeyid);
+      hash = key_table_hasher (tmpkeyid);
+      for (ki = key_table[hash]; ki; ki = ki->next)
+        if (ki->fprlen == fprlen && !memcmp (ki->fpr, fpr, fprlen))
+          return ki; /* Found */
+    }
+  else if (keyid)
+    {
+      hash = key_table_hasher (keyid);
+      for (ki = key_table[hash]; ki; ki = ki->next)
+        if (ki->keyid[0] == keyid[0] && ki->keyid[1] == keyid[1])
+          {
+            /* Found.  We need to check for dups.  */
+            for (ki2 = ki->next; ki2; ki2 = ki2->next)
+              if (ki2->keyid[0] == keyid[0] && ki2->keyid[1] == keyid[1])
+                return NULL;  /* Duplicated keyid - retrun NULL.  */
+
+            /* This is the only one - return it.  */
+            return ki;
+          }
+    }
+  return NULL;
+}
+
+
+/* Helper for the qsort in key_table_put.  */
+static int
+compare_key_items (const void *arg_a, const void *arg_b)
+{
+  const key_item_t a = *(const key_item_t *)arg_a;
+  const key_item_t b = *(const key_item_t *)arg_b;
+
+  /* Reverse sort on the usecount.  */
+  if (a->usecount > b->usecount)
+    return -1;
+  else if (a->usecount == b->usecount)
+    return 0;
+  else
+    return 1;
+}
+
+
+/* Put PK into the KEY_TABLE and return a key item.  The reference
+ * count for that item is incremented.  If UI is given it is put into
+ * the entry.  NULL is return on an allocation error.  */
+static key_item_t
+key_table_put (PKT_public_key *pk, uid_item_t ui)
+{
+  unsigned int hash;
+  key_item_t ki;
+  u32 keyid[2];
+  byte fpr[MAX_FINGERPRINT_LEN];
+  size_t fprlen;
+  unsigned int count, n;
+
+  if (!key_table)
+    key_table_init ();
+
+  fingerprint_from_pk (pk, fpr, &fprlen);
+  keyid_from_pk (pk, keyid);
+  hash = key_table_hasher (keyid);
+  for (ki = key_table[hash], count=0; ki; ki = ki->next, count++)
+    if (ki->fprlen == fprlen && !memcmp (ki->fpr, fpr, fprlen))
+      return ki;  /* Found  */
+
+  /* If the bucket is full remove a couple of items. */
+  if (count >= key_table_max)
+    {
+      key_item_t list_head, *list_tailp, ki_next;
+      key_item_t *array;
+      int narray, idx;
+
+      /* Unlink from the global list so that other threads don't
+       * disturb us.  If another thread adds or removes something only
+       * one will be the winner.  Bad luck for the drooped cache items
+       * but after all it is just a cache.  */
+      list_head = key_table[hash];
+      key_table[hash] = NULL;
+
+      /* Put all items into an array for sorting.  */
+      array = xtrycalloc (count, sizeof *array);
+      if (!array)
+        {
+          /* That's bad; give up all  items of the bucket.  */
+          log_info ("Note: malloc failed while purging from the key_tabe: %s\n",
+                    gpg_strerror (gpg_error_from_syserror ()));
+          goto leave_drop;
+        }
+      narray = 0;
+      for (ki = list_head; ki; ki = ki_next)
+        {
+          ki_next = ki->next;
+          array[narray++] = ki;
+          ki->next = NULL;
+        }
+      log_assert (narray == count);
+
+      /* Sort the array and put half of it onto a new list.  */
+      qsort (array, narray, sizeof *array, compare_key_items);
+      list_head = NULL;
+      list_tailp = &list_head;
+      for (idx=0; idx < narray/2; idx++)
+        {
+          *list_tailp = array[idx];
+          list_tailp = &array[idx]->next;
+        }
+
+      /* Put the new list into the bucket.  */
+      ki = key_table[hash];
+      key_table[hash] = list_head;
+      list_head = ki;
+
+      /* Free the remaining items and the array.  */
+      for (; idx < narray; idx++)
+        {
+          key_item_free (array[idx]);
+          key_table_dropped++;
+        }
+      xfree (array);
+
+    leave_drop:
+      /* Free any items added in the meantime by other threads.  This
+       * is also used in case of a malloc problem (which won't update
+       * the counters, though). */
+      for ( ; list_head; list_head = ki_next)
+        {
+          ki_next = list_head->next;
+          key_item_free (list_head);
+        }
+    }
+
+  /* Add an item to the bucket.  We allocate a whole block of items
+   * for cache performace reasons.  */
+  if (!key_item_attic)
+    {
+      key_item_t kiblock;
+      int kiblocksize = 256;
+
+      kiblock = xtrymalloc (kiblocksize * sizeof *kiblock);
+      if (!kiblock)
+        return NULL;  /* Out of core.  */
+      for (n = 0; n < kiblocksize; n++)
+        {
+          ki = kiblock + n;
+          ki->next = key_item_attic;
+          key_item_attic = ki;
+        }
+
+      /* During the malloc another thread may have changed the bucket.
+       * Thus we need to check again.  */
+      for (ki = key_table[hash]; ki; ki = ki->next)
+        if (ki->fprlen == fprlen && !memcmp (ki->fpr, fpr, fprlen))
+          return ki;  /* Found  */
+    }
+
+  /* We now know that there is an item in the attic.  */
+  ki = key_item_attic;
+  key_item_attic = ki->next;
+  ki->next = NULL;
+
+  memcpy (ki->fpr, fpr, fprlen);
+  ki->fprlen = fprlen;
+  ki->keyid[0] = keyid[0];
+  ki->keyid[1] = keyid[1];
+  ki->ui = uid_item_ref (ui);
+  ki->usecount = 0;
+  ki->next = key_table[hash];
+  key_table[hash] = ki;
+  key_table_added++;
+  return ki;
+}
+
+
+
+/* Return the user ID from the given keyblock.  We use the primary uid
+ * flag which should have already been set.  The returned value is
+ * only valid as long as the given keyblock is not changed. */
+static const char *
+primary_uid_from_keyblock (kbnode_t keyblock, size_t *uidlen)
+{
+  kbnode_t k;
+
+  for (k = keyblock; k; k = k->next)
+    {
+      if (k->pkt->pkttype == PKT_USER_ID
+	  && !k->pkt->pkt.user_id->attrib_data
+	  && k->pkt->pkt.user_id->flags.primary)
+	{
+	  *uidlen = k->pkt->pkt.user_id->len;
+	  return k->pkt->pkt.user_id->name;
+	}
+    }
+  return NULL;
+}
+
+
+/* Store the associations of keyid/fingerprint and userid.  Only
+ * public keys should be fed to this function.  */
+void
+cache_put_keyblock (kbnode_t keyblock)
+{
+  uid_item_t ui = NULL;
+  kbnode_t k;
+
+ restart:
+  for (k = keyblock; k; k = k->next)
+    {
+      if (k->pkt->pkttype == PKT_PUBLIC_KEY
+	  || k->pkt->pkttype == PKT_PUBLIC_SUBKEY)
+	{
+          if (!ui)
+            {
+              /* Initially we just test for an entry to avoid the need
+               * to create a user id item for a put.  Only if we miss
+               * key in the cache we create a user id and restart.  */
+              if (!key_table_get (k->pkt->pkt.public_key, NULL))
+                {
+                  const char *uid;
+                  size_t uidlen;
+
+                  uid = primary_uid_from_keyblock (keyblock, &uidlen);
+                  if (uid)
+                    {
+                      ui = uid_table_put (uid, uidlen);
+                      if (!ui)
+                        {
+                          log_info ("Note: failed to cache a user id: %s\n",
+                                    gpg_strerror (gpg_error_from_syserror ()));
+                          goto leave;
+                        }
+                      goto restart;
+                    }
+                }
+            }
+          else /* With a UID we use the update cache mode.  */
+            {
+              if (!key_table_put (k->pkt->pkt.public_key, ui))
+                {
+                  log_info ("Note: failed to cache a key: %s\n",
+                            gpg_strerror (gpg_error_from_syserror ()));
+                  goto leave;
+                }
+            }
+        }
+    }
+
+ leave:
+  uid_item_unref (ui);
+}
+
+
+/* Return the user id string for KEYID.  If a user id is not found (or
+ * on malloc error) NULL is returned.  If R_LENGTH is not NULL the
+ * length of the user id is stored there; this does not included the
+ * always appended nul.  Note that a user id may include an internal
+ * nul which can be detected by the caller by comparing to the
+ * returned length.  */
+char *
+cache_get_uid_bykid (u32 *keyid, unsigned int *r_length)
+{
+  key_item_t ki;
+  char *p;
+
+  if (r_length)
+    *r_length = 0;
+
+  ki = key_table_get (NULL, keyid);
+  if (!ki)
+    return NULL; /* Not found or duplicate keyid.  */
+
+  if (!ki->ui)
+    p = NULL;  /* No user id known for key.  */
+  else
+    {
+      p = xtrymalloc (ki->ui->namelen + 1);
+      if (p)
+        {
+          memcpy (p, ki->ui->name, ki->ui->namelen + 1);
+          if (r_length)
+            *r_length = ki->ui->namelen;
+          ki->usecount++;
+        }
+    }
+
+  return p;
+}
diff --git a/g10/objcache.h b/g10/objcache.h
new file mode 100644
index 000000000..e92679168
--- /dev/null
+++ b/g10/objcache.h
@@ -0,0 +1,28 @@
+/* objcache.h - Caching functions for keys and user ids.
+ * Copyright (C) 2019 g10 Code GmbH
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG 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 a copy of the GNU General Public License
+ * along with this program; if not, see <https://www.gnu.org/licenses/>.
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#ifndef GNUPG_G10_OBJCACHE_H
+#define GNUPG_G10_OBJCACHE_H
+
+void objcache_dump_stats (void);
+void cache_put_keyblock (kbnode_t keyblock);
+char *cache_get_uid_bykid (u32 *keyid, unsigned int *r_length);
+
+#endif /*GNUPG_G10_OBJCACHE_H*/