g10: Simplify cache. Only include data that is actually used.
authorNeal H. Walfield <neal@g10code.com>
Wed, 26 Aug 2015 10:22:24 +0000 (12:22 +0200)
committerNeal H. Walfield <neal@g10code.com>
Wed, 26 Aug 2015 10:25:53 +0000 (12:25 +0200)
* g10/keydb.c (struct kid_list_s): Rename from this...
(struct kid_not_found_cache_bucket): ... to this.  Update users.
Remove field state.
(kid_list_t): Remove type.
(KID_NOT_FOUND_CACHE_BUCKETS): Define.  Use this instead of a literal.
(kid_found_table): Rename from this...
(kid_not_found_cache_bucket): ... to this.  Update users.
(kid_found_table_count): Rename from this...
(kid_not_found_cache_count): ... to this.  Update users.
(kid_not_found_p): Only return whether a key with the specified key id
is definitely not in the database.
(kid_not_found_insert): Remove parameter found.  Update callers.
(keydb_search): Only insert a key id in the not found cache if it is
not found.  Rename local variable once_found to already_in_cache.

--
Signed-off-by: Neal H. Walfield <neal@g10code.com>.
Commit e0873a33 started tracking whether key ids where definitely in
the database.  This information is, however, never used and thus just
unnecessarily inflates the cache.  This patch effectively reverts that
change (however, e0873a33 contains two separate changes and this only
reverts that change).

g10/keydb.c
g10/keydb.h

index b31c6a6..1446c07 100644 (file)
@@ -74,23 +74,32 @@ struct keydb_handle
   struct resource_item active[MAX_KEYDB_RESOURCES];
 };
 
+/* Looking up keys is expensive.  To hide the cost, we cache whether
+   keys exist in the key database.  Then, if we know a key does not
+   exist, we don't have to spend time looking it up.  This
+   particularly helps the --list-sigs and --check-sigs commands.
 
-/* This object is used to keep a list of keyids in a linked list.  */
-typedef struct kid_list_s
+   The cache stores the results in a hash using separate chaining.
+   Concretely: we use the LSB of the keyid to index the hash table and
+   each bucket consists of a linked list of entries.  An entry
+   consists of the 64-bit key id.  If a key id is not in the cache,
+   then we don't know whether it is in the DB or not.
+
+   To simplify the cache consistency protocol, we simply flush the
+   whole cache whenever a key is inserted or updated.  */
+
+#define KID_NOT_FOUND_CACHE_BUCKETS 256
+static struct kid_not_found_cache_bucket *
+  kid_not_found_cache[KID_NOT_FOUND_CACHE_BUCKETS];
+
+/* The total number of entries in the hash table.  */
+static unsigned int kid_not_found_cache_count;
+
+struct kid_not_found_cache_bucket
 {
-  struct kid_list_s *next;
+  struct kid_not_found_cache_bucket *next;
   u32 kid[2];
-  int state;  /* True if found.  */
-} *kid_list_t;
-
-/* To avoid looking up a key by keyid where we know that it does not
-   yet exist, we keep a table of keyids with search results.  This
-   improves the --list-sigs and --check-sigs commands substantively.
-   To avoid extra complexity we clear the entire table on any insert
-   or update operation.  The array is indexed by the LSB of the keyid.
-   KID_FOUND_TABLE_COUNT gives the number of keys in the table.  */
-static kid_list_t kid_found_table[256];
-static unsigned int kid_found_table_count;
+};
 
 
 /* This is a simple cache used to return the last result of a
@@ -118,81 +127,84 @@ static int lock_all (KEYDB_HANDLE hd);
 static void unlock_all (KEYDB_HANDLE hd);
 
 
-/* Checkwhether the keyid KID is in the table of found or not found
-   keyids.
+/* Check whether the keyid KID is in key id is definately not in the
+   database.
 
    Returns:
-     0 - Keyid not in table
-     1 - Keyid in table because not found in a previous search
-     2 - Keyid in table because found in a previous search
- */
+
+     0 - Indeterminate: the key id is not in the cache; we don't know
+         whether the key is in the database or not.  If you want a
+         definitive answer, you'll need to perform a lookup.
+
+     1 - There is definitely no key with this key id in the database.
+         We searched for a key with this key id previously, but we
+         didn't find it in the database.  */
 static int
 kid_not_found_p (u32 *kid)
 {
-  kid_list_t k;
+  struct kid_not_found_cache_bucket *k;
 
-  for (k = kid_found_table[kid[0] % 256]; k; k = k->next)
+  for (k = kid_not_found_cache[kid[0] % KID_NOT_FOUND_CACHE_BUCKETS]; k; k = k->next)
     if (k->kid[0] == kid[0] && k->kid[1] == kid[1])
       {
         if (DBG_CACHE)
-          log_debug ("keydb: kid_not_found_p (%08lx%08lx) => %s\n",
-                     (ulong)kid[0], (ulong)kid[1],
-                     k->state? "false (found)": "true");
-        return k->state? 2 : 1;
+          log_debug ("keydb: kid_not_found_p (%08lx%08lx) => not in DB\n",
+                     (ulong)kid[0], (ulong)kid[1]);
+        return 1;
       }
 
   if (DBG_CACHE)
-    log_debug ("keydb: kid_not_found_p (%08lx%08lx) => false\n",
+    log_debug ("keydb: kid_not_found_p (%08lx%08lx) => indeterminate\n",
                (ulong)kid[0], (ulong)kid[1]);
   return 0;
 }
 
 
-/* Put the keyid KID into the table of keyids with their find states of
-   previous searches.  Note that there is no check whether the keyid
-   is already in the table, thus kid_not_found_p() should be used prior.  */
+/* Insert the keyid KID into the kid_not_found_cache.  FOUND is whether
+   the key is in the key database or not.
+
+   Note this function does not check whether the key id is already in
+   the cache.  As such, kid_not_found_p() should be called first.  */
 static void
-kid_not_found_insert (u32 *kid, int found)
+kid_not_found_insert (u32 *kid)
 {
-  kid_list_t k;
+  struct kid_not_found_cache_bucket *k;
 
   if (DBG_CACHE)
-    log_debug ("keydb: kid_not_found_insert (%08lx%08lx, %d)\n",
-               (ulong)kid[0], (ulong)kid[1], found);
+    log_debug ("keydb: kid_not_found_insert (%08lx%08lx)\n",
+               (ulong)kid[0], (ulong)kid[1]);
   k = xmalloc (sizeof *k);
   k->kid[0] = kid[0];
   k->kid[1] = kid[1];
-  k->state = found;
-  k->next = kid_found_table[kid[0]%256];
-  kid_found_table[kid[0]%256] = k;
-  kid_found_table_count++;
+  k->next = kid_not_found_cache[kid[0] % KID_NOT_FOUND_CACHE_BUCKETS];
+  kid_not_found_cache[kid[0] % KID_NOT_FOUND_CACHE_BUCKETS] = k;
+  kid_not_found_cache_count++;
 }
 
 
-/* Flush the entire table of keyids whche were not found in previous
-   searches.  */
+/* Flush kid found cache.  */
 static void
 kid_not_found_flush (void)
 {
-  kid_list_t k, knext;
+  struct kid_not_found_cache_bucket *k, *knext;
   int i;
 
   if (DBG_CACHE)
     log_debug ("keydb: kid_not_found_flush\n");
 
-  if (!kid_found_table_count)
+  if (!kid_not_found_cache_count)
     return;
 
-  for (i=0; i < DIM(kid_found_table); i++)
+  for (i=0; i < DIM(kid_not_found_cache); i++)
     {
-      for (k = kid_found_table[i]; k; k = knext)
+      for (k = kid_not_found_cache[i]; k; k = knext)
         {
           knext = k->next;
           xfree (k);
         }
-      kid_found_table[i] = NULL;
+      kid_not_found_cache[i] = NULL;
     }
-  kid_found_table_count = 0;
+  kid_not_found_cache_count = 0;
 }
 
 
@@ -210,9 +222,9 @@ keyblock_cache_clear (void)
 /* Handle the creation of a keyring or a keybox if it does not yet
    exist.  Take into account that other processes might have the
    keyring/keybox already locked.  This lock check does not work if
-   the directory itself is not yet available.  If is IS_BOX is true
-   the filename is expected to be a keybox.  If FORCE_CREATE is true
-   the keyring or keybox shall be created.  */
+   the directory itself is not yet available.  If IS_BOX is true the
+   filename is expected to refer to a keybox.  If FORCE_CREATE is true
+   the keyring or keybox will be created.  */
 static int
 maybe_create_keyring_or_box (char *filename, int is_box, int force_create)
 {
@@ -646,8 +658,9 @@ keydb_add_resource (const char *url, unsigned int flags)
 void
 keydb_dump_stats (void)
 {
-  if (kid_found_table_count)
-    log_info ("keydb: kid_not_found_table: total: %u\n", kid_found_table_count);
+  if (kid_not_found_cache_count)
+    log_info ("keydb: kid_not_found_cache: total: %u\n",
+             kid_not_found_cache_count);
 }
 
 
@@ -1619,7 +1632,7 @@ keydb_search (KEYDB_HANDLE hd, KEYDB_SEARCH_DESC *desc,
               size_t ndesc, size_t *descindex)
 {
   gpg_error_t rc;
-  int once_found = 0;
+  int already_in_cache = 0;
 
   if (descindex)
     *descindex = 0; /* Make sure it is always set on return.  */
@@ -1634,14 +1647,8 @@ keydb_search (KEYDB_HANDLE hd, KEYDB_SEARCH_DESC *desc,
     dump_search_desc (hd, "keydb_search", desc, ndesc);
 
 
-  /* Note that we track the found state in the table to cope with the
-     case that a initial search found the key and the next search
-     (without a reset) did not found the key.  Without keeping the
-     found state we would falsely claim that the key has not been
-     found.  Actually this is quite common because we need to check
-     for ambgious keyids.  */
   if (ndesc == 1 && desc[0].mode == KEYDB_SEARCH_MODE_LONG_KID
-      && (once_found = kid_not_found_p (desc[0].u.kid)) == 1 )
+      && (already_in_cache = kid_not_found_p (desc[0].u.kid)) == 1 )
     {
       if (DBG_CLOCK)
         log_clock ("keydb_search leave (not found, cached)");
@@ -1706,12 +1713,10 @@ keydb_search (KEYDB_HANDLE hd, KEYDB_SEARCH_DESC *desc,
       memcpy (keyblock_cache.fpr, desc[0].u.fpr, 20);
     }
 
-  if ((!rc || gpg_err_code (rc) == GPG_ERR_NOT_FOUND)
+  if (gpg_err_code (rc) == GPG_ERR_NOT_FOUND
       && ndesc == 1 && desc[0].mode == KEYDB_SEARCH_MODE_LONG_KID
-      && !once_found)
-    {
-      kid_not_found_insert (desc[0].u.kid, !rc);
-    }
+      && !already_in_cache)
+    kid_not_found_insert (desc[0].u.kid);
 
   if (DBG_CLOCK)
     log_clock (rc? "keydb_search leave (not found)"
index b64438c..727c96f 100644 (file)
@@ -235,6 +235,10 @@ int get_pubkey_byfprint_fast (PKT_public_key *pk,
 int get_keyblock_byfprint( KBNODE *ret_keyblock, const byte *fprint,
                                                 size_t fprint_len );
 
+/* Return whether a secret key is available for the public key with
+   key id KEYID.  Note: this is just a fast check and does not tell us
+   whether the secret key is valid; this check merely indicates
+   whether there is some secret key with the specified key id.  */
 int have_secret_key_with_kid (u32 *keyid);
 
 gpg_error_t get_seckey_byname (PKT_public_key *pk, const char *name);