1 /* objcache.c - Caching functions for keys and user ids.
2 * Copyright (C) 2019 g10 Code GmbH
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * GnuPG is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, see <https://www.gnu.org/licenses/>.
18 * SPDX-License-Identifier: GPL-3.0-or-later
19 */
20
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "gpg.h"
27 #include "../common/util.h"
28 #include "packet.h"
29 #include "keydb.h"
30 #include "options.h"
31 #include "objcache.h"
32
33 /* Note that max value for uid_items is actually the threshold when
34 * we start to look for items which can be removed. */
35 #define NO_OF_UID_ITEM_BUCKETS 107
36 #define MAX_UID_ITEMS_PER_BUCKET 20
37
38 #define NO_OF_KEY_ITEM_BUCKETS 383
39 #define MAX_KEY_ITEMS_PER_BUCKET 20
40
41
42 /* An object to store a user id. This describes an item in the linked
43 * lists of a bucket in hash table. The reference count will
44 * eventually be used to remove items from the table. */
45 typedef struct uid_item_s
46 {
47 struct uid_item_s *next;
48 unsigned int refcount; /* The reference count for this item. */
49 unsigned int namelen; /* The length of the UID sans the nul. */
50 char name[1];
51 } *uid_item_t;
52
53 static uid_item_t *uid_table; /* Hash table for with user ids. */
54 static size_t uid_table_size; /* Number of allocated buckets. */
55 static unsigned int uid_table_max; /* Max. # of items in a bucket. */
56 static unsigned int uid_table_added; /* # of items added. */
57 static unsigned int uid_table_dropped;/* # of items dropped. */
58
59
60 /* An object to store properties of a key. Note that this can be used
61 * for a primary or a subkey. The key is linked to a user if that
62 * exists. */
63 typedef struct key_item_s
64 {
65 struct key_item_s *next;
66 unsigned int usecount;
67 byte fprlen;
68 char fpr[MAX_FINGERPRINT_LEN];
69 u32 keyid[2];
70 uid_item_t ui; /* NULL of a ref'ed user id item. */
71 } *key_item_t;
72
73 static key_item_t *key_table; /* Hash table with the keys. */
74 static size_t key_table_size; /* Number of allocated buckents. */
75 static unsigned int key_table_max; /* Max. # of items in a bucket. */
76 static unsigned int key_table_added; /* # of items added. */
77 static unsigned int key_table_dropped;/* # of items dropped. */
78 static key_item_t key_item_attic; /* List of freed items. */
79
80
81
82 /* Dump stats. */
83 void
objcache_dump_stats(void)84 objcache_dump_stats (void)
85 {
86 unsigned int idx;
87 int len, minlen, maxlen;
88 unsigned int count, attic, empty;
89 key_item_t ki;
90 uid_item_t ui;
91
92 count = empty = 0;
93 minlen = -1;
94 maxlen = 0;
95 for (idx = 0; idx < key_table_size; idx++)
96 {
97 len = 0;
98 for (ki = key_table[idx]; ki; ki = ki->next)
99 {
100 count++;
101 len++;
102 /* log_debug ("key bucket %u: kid=%08lX used=%u ui=%p\n", */
103 /* idx, (ulong)ki->keyid[0], ki->usecount, ki->ui); */
104 }
105 if (len > maxlen)
106 maxlen = len;
107
108 if (!len)
109 empty++;
110 else if (minlen == -1 || len < minlen)
111 minlen = len;
112 }
113 for (attic=0, ki = key_item_attic; ki; ki = ki->next)
114 attic++;
115 log_info ("objcache: keys=%u/%u/%u chains=%u,%d..%d buckets=%zu/%u"
116 " attic=%u\n",
117 count, key_table_added, key_table_dropped,
118 empty, minlen > 0? minlen : 0, maxlen,
119 key_table_size, key_table_max, attic);
120
121 count = empty = 0;
122 minlen = -1;
123 maxlen = 0;
124 for (idx = 0; idx < uid_table_size; idx++)
125 {
126 len = 0;
127 for (ui = uid_table[idx]; ui; ui = ui->next)
128 {
129 count++;
130 len++;
131 /* log_debug ("uid bucket %u: %p ref=%u l=%u (%.20s)\n", */
132 /* idx, ui, ui->refcount, ui->namelen, ui->name); */
133 }
134 if (len > maxlen)
135 maxlen = len;
136
137 if (!len)
138 empty++;
139 else if (minlen == -1 || len < minlen)
140 minlen = len;
141 }
142 log_info ("objcache: uids=%u/%u/%u chains=%u,%d..%d buckets=%zu/%u\n",
143 count, uid_table_added, uid_table_dropped,
144 empty, minlen > 0? minlen : 0, maxlen,
145 uid_table_size, uid_table_max);
146 }
147
148
149
150 /* The hash function we use for the uid_table. Must not call a system
151 * function. */
152 static inline unsigned int
uid_table_hasher(const char * name,unsigned namelen)153 uid_table_hasher (const char *name, unsigned namelen)
154 {
155 const unsigned char *s = (const unsigned char*)name;
156 unsigned int hashval = 0;
157 unsigned int carry;
158
159 for (; namelen; namelen--, s++)
160 {
161 hashval = (hashval << 4) + *s;
162 if ((carry = (hashval & 0xf0000000)))
163 {
164 hashval ^= (carry >> 24);
165 hashval ^= carry;
166 }
167 }
168
169 return hashval % uid_table_size;
170 }
171
172
173 /* Run time allocation of the uid table. This allows us to eventually
174 * add an option to gpg to control the size. */
175 static void
uid_table_init(void)176 uid_table_init (void)
177 {
178 if (uid_table)
179 return;
180 uid_table_size = NO_OF_UID_ITEM_BUCKETS;
181 uid_table_max = MAX_UID_ITEMS_PER_BUCKET;
182 uid_table = xcalloc (uid_table_size, sizeof *uid_table);
183 }
184
185
186 static uid_item_t
uid_item_ref(uid_item_t ui)187 uid_item_ref (uid_item_t ui)
188 {
189 if (ui)
190 ui->refcount++;
191 return ui;
192 }
193
194 static void
uid_item_unref(uid_item_t uid)195 uid_item_unref (uid_item_t uid)
196 {
197 if (!uid)
198 return;
199 if (!uid->refcount)
200 log_fatal ("too many unrefs for uid_item\n");
201
202 uid->refcount--;
203 /* We do not release the item here because that would require that
204 * we locate the head of the list which has this item. This will
205 * take too long and thus the item is removed when we need to purge
206 * some items for the list during uid_item_put. */
207 }
208
209
210 /* Put (NAME,NAMELEN) into the UID_TABLE and return the item. The
211 * reference count for that item is incremented. NULL is return on an
212 * allocation error. The caller should release the returned item
213 * using uid_item_unref. */
214 static uid_item_t
uid_table_put(const char * name,unsigned int namelen)215 uid_table_put (const char *name, unsigned int namelen)
216 {
217 unsigned int hash;
218 uid_item_t ui;
219 unsigned int count;
220
221 if (!uid_table)
222 uid_table_init ();
223
224 hash = uid_table_hasher (name, namelen);
225 for (ui = uid_table[hash], count = 0; ui; ui = ui->next, count++)
226 if (ui->namelen == namelen && !memcmp (ui->name, name, namelen))
227 return uid_item_ref (ui); /* Found. */
228
229 /* If the bucket is full remove all unrefed items. */
230 if (count >= uid_table_max)
231 {
232 uid_item_t ui_next, ui_prev, list_head, drop_head;
233
234 /* No syscalls from here .. */
235 list_head = uid_table[hash];
236 drop_head = NULL;
237 while (list_head && !list_head->refcount)
238 {
239 ui = list_head;
240 list_head = ui->next;
241 ui->next = drop_head;
242 drop_head = ui;
243 }
244 if ((ui_prev = list_head))
245 for (ui = ui_prev->next; ui; ui = ui_next)
246 {
247 ui_next = ui->next;
248 if (!ui->refcount)
249 {
250 ui->next = drop_head;
251 drop_head = ui;
252 ui_prev->next = ui_next;
253 }
254 else
255 ui_prev = ui;
256 }
257 uid_table[hash] = list_head;
258 /* ... to here */
259
260 for (ui = drop_head; ui; ui = ui_next)
261 {
262 ui_next = ui->next;
263 xfree (ui);
264 uid_table_dropped++;
265 }
266 }
267
268 count = uid_table_added + uid_table_dropped;
269 ui = xtrycalloc (1, sizeof *ui + namelen);
270 if (!ui)
271 return NULL; /* Out of core. */
272 if (count != uid_table_added + uid_table_dropped)
273 {
274 /* During the malloc another thread added an item. Thus we need
275 * to check again. */
276 uid_item_t ui_new = ui;
277 for (ui = uid_table[hash]; ui; ui = ui->next)
278 if (ui->namelen == namelen && !memcmp (ui->name, name, namelen))
279 {
280 /* Found. */
281 xfree (ui_new);
282 return uid_item_ref (ui);
283 }
284 ui = ui_new;
285 }
286
287 memcpy (ui->name, name, namelen);
288 ui->name[namelen] = 0; /* Extra Nul so we can use it as a string. */
289 ui->namelen = namelen;
290 ui->refcount = 1;
291 ui->next = uid_table[hash];
292 uid_table[hash] = ui;
293 uid_table_added++;
294 return ui;
295 }
296
297
298
299 /* The hash function we use for the key_table. Must not call a system
300 * function. */
301 static inline unsigned int
key_table_hasher(u32 * keyid)302 key_table_hasher (u32 *keyid)
303 {
304 /* A fingerprint could be used directly as a hash value. However,
305 * we use the keyid here because it is used in encrypted packets and
306 * older signatures to identify a key. Since v4 keys the keyid is
307 * anyway a part of the fingerprint so it quickly extracted from a
308 * fingerprint. Note that v3 keys are not supported by gpg. */
309 return keyid[0] % key_table_size;
310 }
311
312
313 /* Run time allocation of the key table. This allows us to eventually
314 * add an option to gpg to control the size. */
315 static void
key_table_init(void)316 key_table_init (void)
317 {
318 if (key_table)
319 return;
320 key_table_size = NO_OF_KEY_ITEM_BUCKETS;
321 key_table_max = MAX_KEY_ITEMS_PER_BUCKET;
322 key_table = xcalloc (key_table_size, sizeof *key_table);
323 }
324
325
326 static void
key_item_free(key_item_t ki)327 key_item_free (key_item_t ki)
328 {
329 if (!ki)
330 return;
331 uid_item_unref (ki->ui);
332 ki->ui = NULL;
333 ki->next = key_item_attic;
334 key_item_attic = ki;
335 }
336
337
338 /* Get a key item from PK or if that is NULL from KEYID. The
339 * reference count for that item is incremented. NULL is return if it
340 * was not found. */
341 static key_item_t
key_table_get(PKT_public_key * pk,u32 * keyid)342 key_table_get (PKT_public_key *pk, u32 *keyid)
343 {
344 unsigned int hash;
345 key_item_t ki, ki2;
346
347 if (!key_table)
348 key_table_init ();
349
350 if (pk)
351 {
352 byte fpr[MAX_FINGERPRINT_LEN];
353 size_t fprlen;
354 u32 tmpkeyid[2];
355
356 fingerprint_from_pk (pk, fpr, &fprlen);
357 keyid_from_pk (pk, tmpkeyid);
358 hash = key_table_hasher (tmpkeyid);
359 for (ki = key_table[hash]; ki; ki = ki->next)
360 if (ki->fprlen == fprlen && !memcmp (ki->fpr, fpr, fprlen))
361 return ki; /* Found */
362 }
363 else if (keyid)
364 {
365 hash = key_table_hasher (keyid);
366 for (ki = key_table[hash]; ki; ki = ki->next)
367 if (ki->keyid[0] == keyid[0] && ki->keyid[1] == keyid[1])
368 {
369 /* Found. We need to check for dups. */
370 for (ki2 = ki->next; ki2; ki2 = ki2->next)
371 if (ki2->keyid[0] == keyid[0] && ki2->keyid[1] == keyid[1])
372 return NULL; /* Duplicated keyid - return NULL. */
373
374 /* This is the only one - return it. */
375 return ki;
376 }
377 }
378 return NULL;
379 }
380
381
382 /* Helper for the qsort in key_table_put. */
383 static int
compare_key_items(const void * arg_a,const void * arg_b)384 compare_key_items (const void *arg_a, const void *arg_b)
385 {
386 const key_item_t a = *(const key_item_t *)arg_a;
387 const key_item_t b = *(const key_item_t *)arg_b;
388
389 /* Reverse sort on the usecount. */
390 if (a->usecount > b->usecount)
391 return -1;
392 else if (a->usecount == b->usecount)
393 return 0;
394 else
395 return 1;
396 }
397
398
399 /* Put PK into the KEY_TABLE and return a key item. The reference
400 * count for that item is incremented. If UI is given it is put into
401 * the entry. NULL is return on an allocation error. */
402 static key_item_t
key_table_put(PKT_public_key * pk,uid_item_t ui)403 key_table_put (PKT_public_key *pk, uid_item_t ui)
404 {
405 unsigned int hash;
406 key_item_t ki;
407 u32 keyid[2];
408 byte fpr[MAX_FINGERPRINT_LEN];
409 size_t fprlen;
410 unsigned int count, n;
411
412 if (!key_table)
413 key_table_init ();
414
415 fingerprint_from_pk (pk, fpr, &fprlen);
416 keyid_from_pk (pk, keyid);
417 hash = key_table_hasher (keyid);
418 for (ki = key_table[hash], count=0; ki; ki = ki->next, count++)
419 if (ki->fprlen == fprlen && !memcmp (ki->fpr, fpr, fprlen))
420 return ki; /* Found */
421
422 /* If the bucket is full remove a couple of items. */
423 if (count >= key_table_max)
424 {
425 key_item_t list_head, *list_tailp, ki_next;
426 key_item_t *array;
427 int narray, idx;
428
429 /* Unlink from the global list so that other threads don't
430 * disturb us. If another thread adds or removes something only
431 * one will be the winner. Bad luck for the drooped cache items
432 * but after all it is just a cache. */
433 list_head = key_table[hash];
434 key_table[hash] = NULL;
435
436 /* Put all items into an array for sorting. */
437 array = xtrycalloc (count, sizeof *array);
438 if (!array)
439 {
440 /* That's bad; give up all items of the bucket. */
441 log_info ("Note: malloc failed while purging from the key_tabe: %s\n",
442 gpg_strerror (gpg_error_from_syserror ()));
443 goto leave_drop;
444 }
445 narray = 0;
446 for (ki = list_head; ki; ki = ki_next)
447 {
448 ki_next = ki->next;
449 array[narray++] = ki;
450 ki->next = NULL;
451 }
452 log_assert (narray == count);
453
454 /* Sort the array and put half of it onto a new list. */
455 qsort (array, narray, sizeof *array, compare_key_items);
456 list_head = NULL;
457 list_tailp = &list_head;
458 for (idx=0; idx < narray/2; idx++)
459 {
460 *list_tailp = array[idx];
461 list_tailp = &array[idx]->next;
462 }
463
464 /* Put the new list into the bucket. */
465 ki = key_table[hash];
466 key_table[hash] = list_head;
467 list_head = ki;
468
469 /* Free the remaining items and the array. */
470 for (; idx < narray; idx++)
471 {
472 key_item_free (array[idx]);
473 key_table_dropped++;
474 }
475 xfree (array);
476
477 leave_drop:
478 /* Free any items added in the meantime by other threads. This
479 * is also used in case of a malloc problem (which won't update
480 * the counters, though). */
481 for ( ; list_head; list_head = ki_next)
482 {
483 ki_next = list_head->next;
484 key_item_free (list_head);
485 }
486 }
487
488 /* Add an item to the bucket. We allocate a whole block of items
489 * for cache performance reasons. */
490 if (!key_item_attic)
491 {
492 key_item_t kiblock;
493 int kiblocksize = 256;
494
495 kiblock = xtrymalloc (kiblocksize * sizeof *kiblock);
496 if (!kiblock)
497 return NULL; /* Out of core. */
498 for (n = 0; n < kiblocksize; n++)
499 {
500 ki = kiblock + n;
501 ki->next = key_item_attic;
502 key_item_attic = ki;
503 }
504
505 /* During the malloc another thread may have changed the bucket.
506 * Thus we need to check again. */
507 for (ki = key_table[hash]; ki; ki = ki->next)
508 if (ki->fprlen == fprlen && !memcmp (ki->fpr, fpr, fprlen))
509 return ki; /* Found */
510 }
511
512 /* We now know that there is an item in the attic. */
513 ki = key_item_attic;
514 key_item_attic = ki->next;
515 ki->next = NULL;
516
517 memcpy (ki->fpr, fpr, fprlen);
518 ki->fprlen = fprlen;
519 ki->keyid[0] = keyid[0];
520 ki->keyid[1] = keyid[1];
521 ki->ui = uid_item_ref (ui);
522 ki->usecount = 0;
523 ki->next = key_table[hash];
524 key_table[hash] = ki;
525 key_table_added++;
526 return ki;
527 }
528
529
530
531 /* Return the user ID from the given keyblock. We use the primary uid
532 * flag which should have already been set. The returned value is
533 * only valid as long as the given keyblock is not changed. */
534 static const char *
primary_uid_from_keyblock(kbnode_t keyblock,size_t * uidlen)535 primary_uid_from_keyblock (kbnode_t keyblock, size_t *uidlen)
536 {
537 kbnode_t k;
538
539 for (k = keyblock; k; k = k->next)
540 {
541 if (k->pkt->pkttype == PKT_USER_ID
542 && !k->pkt->pkt.user_id->attrib_data
543 && k->pkt->pkt.user_id->flags.primary)
544 {
545 *uidlen = k->pkt->pkt.user_id->len;
546 return k->pkt->pkt.user_id->name;
547 }
548 }
549 return NULL;
550 }
551
552
553 /* Store the associations of keyid/fingerprint and userid. Only
554 * public keys should be fed to this function. */
555 void
cache_put_keyblock(kbnode_t keyblock)556 cache_put_keyblock (kbnode_t keyblock)
557 {
558 uid_item_t ui = NULL;
559 kbnode_t k;
560
561 restart:
562 for (k = keyblock; k; k = k->next)
563 {
564 if (k->pkt->pkttype == PKT_PUBLIC_KEY
565 || k->pkt->pkttype == PKT_PUBLIC_SUBKEY)
566 {
567 if (!ui)
568 {
569 /* Initially we just test for an entry to avoid the need
570 * to create a user id item for a put. Only if we miss
571 * key in the cache we create a user id and restart. */
572 if (!key_table_get (k->pkt->pkt.public_key, NULL))
573 {
574 const char *uid;
575 size_t uidlen;
576
577 uid = primary_uid_from_keyblock (keyblock, &uidlen);
578 if (uid)
579 {
580 ui = uid_table_put (uid, uidlen);
581 if (!ui)
582 {
583 log_info ("Note: failed to cache a user id: %s\n",
584 gpg_strerror (gpg_error_from_syserror ()));
585 goto leave;
586 }
587 goto restart;
588 }
589 }
590 }
591 else /* With a UID we use the update cache mode. */
592 {
593 if (!key_table_put (k->pkt->pkt.public_key, ui))
594 {
595 log_info ("Note: failed to cache a key: %s\n",
596 gpg_strerror (gpg_error_from_syserror ()));
597 goto leave;
598 }
599 }
600 }
601 }
602
603 leave:
604 uid_item_unref (ui);
605 }
606
607
608 /* Return the user id string for KEYID. If a user id is not found (or
609 * on malloc error) NULL is returned. If R_LENGTH is not NULL the
610 * length of the user id is stored there; this does not included the
611 * always appended nul. Note that a user id may include an internal
612 * nul which can be detected by the caller by comparing to the
613 * returned length. */
614 char *
cache_get_uid_bykid(u32 * keyid,unsigned int * r_length)615 cache_get_uid_bykid (u32 *keyid, unsigned int *r_length)
616 {
617 key_item_t ki;
618 char *p;
619
620 if (r_length)
621 *r_length = 0;
622
623 ki = key_table_get (NULL, keyid);
624 if (!ki)
625 return NULL; /* Not found or duplicate keyid. */
626
627 if (!ki->ui)
628 p = NULL; /* No user id known for key. */
629 else
630 {
631 p = xtrymalloc (ki->ui->namelen + 1);
632 if (p)
633 {
634 memcpy (p, ki->ui->name, ki->ui->namelen + 1);
635 if (r_length)
636 *r_length = ki->ui->namelen;
637 ki->usecount++;
638 }
639 }
640
641 return p;
642 }
643
644
645 /* Return the user id string for FPR with FPRLEN. If a user id is not
646 * found (or on malloc error) NULL is returned. If R_LENGTH is not
647 * NULL the length of the user id is stored there; this does not
648 * included the always appended nul. Note that a user id may include
649 * an internal nul which can be detected by the caller by comparing to
650 * the returned length. */
651 char *
cache_get_uid_byfpr(const byte * fpr,size_t fprlen,size_t * r_length)652 cache_get_uid_byfpr (const byte *fpr, size_t fprlen, size_t *r_length)
653 {
654 char *p;
655 unsigned int hash;
656 u32 keyid[2];
657 key_item_t ki;
658
659 if (r_length)
660 *r_length = 0;
661
662 if (!key_table)
663 return NULL;
664
665 keyid_from_fingerprint (NULL, fpr, fprlen, keyid);
666 hash = key_table_hasher (keyid);
667 for (ki = key_table[hash]; ki; ki = ki->next)
668 if (ki->fprlen == fprlen && !memcmp (ki->fpr, fpr, fprlen))
669 break; /* Found */
670
671 if (!ki)
672 return NULL; /* Not found. */
673
674 if (!ki->ui)
675 p = NULL; /* No user id known for key. */
676 else
677 {
678 p = xtrymalloc (ki->ui->namelen + 1);
679 if (p)
680 {
681 memcpy (p, ki->ui->name, ki->ui->namelen + 1);
682 if (r_length)
683 *r_length = ki->ui->namelen;
684 ki->usecount++;
685 }
686 }
687
688 return p;
689 }
690