gpg: Cache keybox searches.
authorWerner Koch <wk@gnupg.org>
Tue, 8 Jan 2013 13:44:49 +0000 (14:44 +0100)
committerWerner Koch <wk@gnupg.org>
Tue, 8 Jan 2013 13:46:06 +0000 (14:46 +0100)
* common/iobuf.c (iobuf_seek): Fix for temp streams.
* g10/pubkey-enc.c (get_session_key, get_it): Add some log_clock calls.
* g10/keydb.c (dump_search_desc): New.
(enum_keyblock_states, struct keyblock_cache): New.
(keyblock_cache_clear): New.
(keydb_get_keyblock, keydb_search): Implement a keyblock cache.
(keydb_update_keyblock, keydb_insert_keyblock, keydb_delete_keyblock)
(keydb_rebuild_caches, keydb_search_reset): Clear the cache.
--

Gpg uses the key database at several places without a central
coordination.  This leads to several scans of the keybox for the same
key.  To improve that we now use a simple cache to store a retrieved
keyblock in certain cases.  In theory this caching could also be done
for old keyrings, but it is a bit more work and questionable whether
it is needed; the keybox scheme is anyway much faster than keyrings.

Using a keybox with 20000 384 bit ECDSA/ECHD keypairs and a 252 byte
sample text we get these values for encrypt and decrypt operations on
an Core i5 4*3.33Ghz system.  The option --trust-model=always is used.
Times are given in milliseconds wall time.

|           | enc | dec | dec,q |
|-----------+-----+-----+-------|
| key 1     |  48 |  96 |    70 |
| key 10000 |  60 |  98 |    80 |
| key 20000 |  69 | 106 |    88 |
| 10 keys   | 540 | 290 |    70 |

The 10 keys test uses a mix of keys, the first one is used for
decryption but all keys are looked up so that information about are
printed.  The last column gives decryption results w/o information
printing (--quiet).

The keybox is always scanned sequentially without using any index.  By
adding an index to the keybox it will be possible to further reduce
the time required for keys stored to the end of the file.

common/iobuf.c
g10/keydb.c
g10/pubkey-enc.c

index 3ba3582..a305830 100644 (file)
@@ -2311,7 +2311,7 @@ iobuf_seek (iobuf_t a, off_t newpos)
        }
       clearerr (fp);
     }
-  else
+  else if (a->use != 3)  /* Not a temp stream.  */
     {
       for (; a; a = a->chain)
        {
@@ -2338,7 +2338,8 @@ iobuf_seek (iobuf_t a, off_t newpos)
        }
 #endif
     }
-  a->d.len = 0;                        /* discard buffer */
+  if (a->use != 3)
+    a->d.len = 0;      /* Discard the buffer  unless it is a temp stream.  */
   a->d.start = 0;
   a->nbytes = 0;
   a->nlimit = 0;
index 7166203..79ab5af 100644 (file)
@@ -72,10 +72,42 @@ struct keydb_handle
 };
 
 
+/* This is a simple cache used to return the last result of a
+   successful long kid search.  This works only for keybox resources
+   because (due to lack of a copy_keyblock function) we need to store
+   an image of the keyblock which is fortunately instantly available
+   for keyboxes.  */
+enum keyblock_cache_states {
+  KEYBLOCK_CACHE_EMPTY,
+  KEYBLOCK_CACHE_PREPARED,
+  KEYBLOCK_CACHE_FILLED
+};
+
+struct {
+  enum keyblock_cache_states state;
+  u32 kid[2];
+  iobuf_t iobuf; /* Image of the keyblock.  */
+  u32 *sigstatus;
+  int pk_no;
+  int uid_no;
+} keyblock_cache;
+
+
 static int lock_all (KEYDB_HANDLE hd);
 static void unlock_all (KEYDB_HANDLE hd);
 
 
+static void
+keyblock_cache_clear (void)
+{
+  keyblock_cache.state = KEYBLOCK_CACHE_EMPTY;
+  xfree (keyblock_cache.sigstatus);
+  keyblock_cache.sigstatus = NULL;
+  iobuf_close (keyblock_cache.iobuf);
+  keyblock_cache.iobuf = NULL;
+}
+
+
 /* Handle the creation of a keyring or a keybox if it does not yet
    exist.  Take into acount that other processes might have the
    keyring/keybox already locked.  This lock check does not work if
@@ -427,6 +459,9 @@ keydb_new (void)
   KEYDB_HANDLE hd;
   int i, j;
 
+  if (DBG_CLOCK)
+    log_clock ("keydb_new");
+
   hd = xmalloc_clear (sizeof *hd);
   hd->found = -1;
 
@@ -787,6 +822,19 @@ keydb_get_keyblock (KEYDB_HANDLE hd, KBNODE *ret_kb)
   if (!hd)
     return gpg_error (GPG_ERR_INV_ARG);
 
+  if (keyblock_cache.state == KEYBLOCK_CACHE_FILLED)
+    {
+      iobuf_seek (keyblock_cache.iobuf, 0);
+      err = parse_keyblock_image (keyblock_cache.iobuf,
+                                  keyblock_cache.pk_no,
+                                  keyblock_cache.uid_no,
+                                  keyblock_cache.sigstatus,
+                                  ret_kb);
+      if (err)
+        keyblock_cache_clear ();
+      return err;
+    }
+
   if (hd->found < 0 || hd->found >= hd->used)
     return gpg_error (GPG_ERR_VALUE_NOT_FOUND);
 
@@ -810,13 +858,27 @@ keydb_get_keyblock (KEYDB_HANDLE hd, KBNODE *ret_kb)
           {
             err = parse_keyblock_image (iobuf, pk_no, uid_no, sigstatus,
                                         ret_kb);
-            xfree (sigstatus);
-            iobuf_close (iobuf);
+            if (!err && keyblock_cache.state == KEYBLOCK_CACHE_PREPARED)
+              {
+                keyblock_cache.state     = KEYBLOCK_CACHE_FILLED;
+                keyblock_cache.sigstatus = sigstatus;
+                keyblock_cache.iobuf     = iobuf;
+                keyblock_cache.pk_no     = pk_no;
+                keyblock_cache.uid_no    = uid_no;
+              }
+            else
+              {
+                xfree (sigstatus);
+                iobuf_close (iobuf);
+              }
           }
       }
       break;
     }
 
+  if (keyblock_cache.state != KEYBLOCK_CACHE_FILLED)
+    keyblock_cache_clear ();
+
   return err;
 }
 
@@ -914,6 +976,8 @@ keydb_update_keyblock (KEYDB_HANDLE hd, kbnode_t kb)
   if (!hd)
     return gpg_error (GPG_ERR_INV_ARG);
 
+  keyblock_cache_clear ();
+
   if (hd->found < 0 || hd->found >= hd->used)
     return gpg_error (GPG_ERR_VALUE_NOT_FOUND);
 
@@ -957,6 +1021,8 @@ keydb_insert_keyblock (KEYDB_HANDLE hd, kbnode_t kb)
   if (!hd)
     return gpg_error (GPG_ERR_INV_ARG);
 
+  keyblock_cache_clear ();
+
   if (opt.dry_run)
     return 0;
 
@@ -1017,6 +1083,8 @@ keydb_delete_keyblock (KEYDB_HANDLE hd)
   if (!hd)
     return gpg_error (GPG_ERR_INV_ARG);
 
+  keyblock_cache_clear ();
+
   if (hd->found < 0 || hd->found >= hd->used)
     return gpg_error (GPG_ERR_VALUE_NOT_FOUND);
 
@@ -1113,6 +1181,8 @@ keydb_rebuild_caches (int noisy)
 {
   int i, rc;
 
+  keyblock_cache_clear ();
+
   for (i=0; i < used_resources; i++)
     {
       if (!keyring_is_writable (all_resources[i].token))
@@ -1145,6 +1215,11 @@ keydb_search_reset (KEYDB_HANDLE hd)
   if (!hd)
     return gpg_error (GPG_ERR_INV_ARG);
 
+  keyblock_cache_clear ();
+
+  if (DBG_CLOCK)
+    log_clock ("keydb_search_reset");
+
   hd->current = 0;
   hd->found = -1;
   /* Now reset all resources.  */
@@ -1166,6 +1241,52 @@ keydb_search_reset (KEYDB_HANDLE hd)
 }
 
 
+static void
+dump_search_desc (const char *text, KEYDB_SEARCH_DESC *desc, size_t ndesc)
+{
+  int n;
+  const char *s;
+
+  for (n=0; n < ndesc; n++)
+    {
+      switch (desc[n].mode)
+        {
+        case KEYDB_SEARCH_MODE_NONE:      s = "none";      break;
+        case KEYDB_SEARCH_MODE_EXACT:     s = "exact";     break;
+        case KEYDB_SEARCH_MODE_SUBSTR:    s = "substr";    break;
+        case KEYDB_SEARCH_MODE_MAIL:      s = "mail";      break;
+        case KEYDB_SEARCH_MODE_MAILSUB:   s = "mailsub";   break;
+        case KEYDB_SEARCH_MODE_MAILEND:   s = "mailend";   break;
+        case KEYDB_SEARCH_MODE_WORDS:     s = "words";     break;
+        case KEYDB_SEARCH_MODE_SHORT_KID: s = "short_kid"; break;
+        case KEYDB_SEARCH_MODE_LONG_KID:  s = "long_kid";  break;
+        case KEYDB_SEARCH_MODE_FPR16:     s = "fpr16";     break;
+        case KEYDB_SEARCH_MODE_FPR20:     s = "fpr20";     break;
+        case KEYDB_SEARCH_MODE_FPR:       s = "fpr";       break;
+        case KEYDB_SEARCH_MODE_ISSUER:    s = "issuer";    break;
+        case KEYDB_SEARCH_MODE_ISSUER_SN: s = "issuer_sn"; break;
+        case KEYDB_SEARCH_MODE_SN:        s = "sn";        break;
+        case KEYDB_SEARCH_MODE_SUBJECT:   s = "subject";   break;
+        case KEYDB_SEARCH_MODE_KEYGRIP:   s = "keygrip";   break;
+        case KEYDB_SEARCH_MODE_FIRST:     s = "first";     break;
+        case KEYDB_SEARCH_MODE_NEXT:      s = "next";      break;
+        default:                          s = "?";         break;
+        }
+      if (!n)
+        log_debug ("%s: mode=%s", text, s);
+      else
+        log_debug ("%*s  mode=%s", (int)strlen (text), "", s);
+      if (desc[n].mode == KEYDB_SEARCH_MODE_LONG_KID)
+        log_printf (" %08lX%08lX", (unsigned long)desc[n].u.kid[0],
+                    (unsigned long)desc[n].u.kid[1]);
+      else if (desc[n].mode == KEYDB_SEARCH_MODE_SHORT_KID)
+        log_printf (" %08lX", (unsigned long)desc[n].u.kid[1]);
+      else if (desc[n].mode == KEYDB_SEARCH_MODE_SUBSTR)
+        log_printf (" '%s'", desc[n].u.name);
+    }
+}
+
+
 /*
  * Search through all keydb resources, starting at the current
  * position, for a keyblock which contains one of the keys described
@@ -1184,6 +1305,19 @@ keydb_search (KEYDB_HANDLE hd, KEYDB_SEARCH_DESC *desc,
   if (DBG_CLOCK)
     log_clock ("keydb_search enter");
 
+  if (DBG_CACHE)
+    dump_search_desc ("keydb_search", desc, ndesc);
+
+  if (ndesc == 1 && desc[0].mode == KEYDB_SEARCH_MODE_LONG_KID
+      && keyblock_cache.state  == KEYBLOCK_CACHE_FILLED
+      && keyblock_cache.kid[0] == desc[0].u.kid[0]
+      && keyblock_cache.kid[1] == desc[0].u.kid[1])
+    {
+      if (DBG_CLOCK)
+        log_clock ("keydb_search leave (cached)");
+      return 0;
+    }
+
   rc = -1;
   while ((rc == -1 || gpg_err_code (rc) == GPG_ERR_EOF)
          && hd->current >= 0 && hd->current < hd->used)
@@ -1210,11 +1344,22 @@ keydb_search (KEYDB_HANDLE hd, KEYDB_SEARCH_DESC *desc,
         hd->found = hd->current;
     }
 
+  rc = ((rc == -1 || gpg_err_code (rc) == GPG_ERR_EOF)
+        ? gpg_error (GPG_ERR_NOT_FOUND)
+        : rc);
+
+  keyblock_cache_clear ();
+  if (!rc && ndesc == 1 && desc[0].mode == KEYDB_SEARCH_MODE_LONG_KID)
+    {
+      keyblock_cache.state = KEYBLOCK_CACHE_PREPARED;
+      keyblock_cache.kid[0] = desc[0].u.kid[0];
+      keyblock_cache.kid[1] = desc[0].u.kid[1];
+    }
+
   if (DBG_CLOCK)
-    log_clock ("keydb_search leave");
-  return ((rc == -1 || gpg_err_code (rc) == GPG_ERR_EOF)
-          ? gpg_error (GPG_ERR_NOT_FOUND)
-          : rc);
+    log_clock (rc? "keydb_search leave (not found)"
+                 : "keydb_search leave (found)");
+  return rc;
 }
 
 
index 254e810..a69536e 100644 (file)
@@ -77,6 +77,9 @@ get_session_key (PKT_pubkey_enc * k, DEK * dek)
   PKT_public_key *sk = NULL;
   int rc;
 
+  if (DBG_CLOCK)
+    log_clock ("get_session_key enter");
+
   rc = openpgp_pk_test_algo2 (k->pubkey_algo, PUBKEY_USAGE_ENC);
   if (rc)
     goto leave;
@@ -129,6 +132,8 @@ get_session_key (PKT_pubkey_enc * k, DEK * dek)
 
 leave:
   free_public_key (sk);
+  if (DBG_CLOCK)
+    log_clock ("get_session_key leave");
   return rc;
 }
 
@@ -149,6 +154,9 @@ get_it (PKT_pubkey_enc *enc, DEK *dek, PKT_public_key *sk, u32 *keyid)
   size_t fpn;
   const int pkalgo = map_pk_openpgp_to_gcry (sk->pubkey_algo);
 
+  if (DBG_CLOCK)
+    log_clock ("decryption start");
+
   /* Get the keygrip.  */
   err = hexkeygrip_from_pk (sk, &keygrip);
   if (err)
@@ -321,6 +329,8 @@ get_it (PKT_pubkey_enc *enc, DEK *dek, PKT_public_key *sk, u32 *keyid)
       err = gpg_error (GPG_ERR_WRONG_SECKEY);
       goto leave;
     }
+  if (DBG_CLOCK)
+    log_clock ("decryption ready");
   if (DBG_CIPHER)
     log_printhex ("DEK is:", dek->key, dek->keylen);