dirmngr/domaininfo.c

   1 /* domaininfo.c - Gather statistics about accessed domains
   2  * Copyright (C) 2017 Werner Koch
   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  *
  19  * SPDX-License-Identifier: GPL-3.0+
  20  */
  21
  22 #include <config.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #include "dirmngr.h"
  27
  28
  29 /* Number of bucket for the hash array and limit for the length of a
  30  * bucket chain.  For debugging values of 13 and 10 are more suitable
  31  * and a command like
  32  *   for j   in a b c d e f g h i j k l m n o p q r s t u v w z y z; do \
  33  *     for i in a b c d e f g h i j k l m n o p q r s t u v w z y z; do \
  34  *       gpg-connect-agent --dirmngr "wkd_get foo@$i.$j.gnupg.net" /bye \
  35  *       >/dev/null ; done; done
  36  * will quickly add a couple of domains.
  37  */
  38 #define NO_OF_DOMAINBUCKETS  103
  39 #define MAX_DOMAINBUCKET_LEN  20
  40
  41
  42 /* Object to keep track of a domain name.  */
  43 struct domaininfo_s
  44 {
  45   struct domaininfo_s *next;
  46   unsigned int no_name:1;            /* Domain name not found.            */
  47   unsigned int wkd_not_found:1;      /* A WKD query failed.               */
  48   unsigned int wkd_supported:1;      /* One WKD entry was found.          */
  49   unsigned int wkd_not_supported:1;  /* Definitely does not support WKD.  */
  50   unsigned int keepmark:1;           /* Private to insert_or_update().    */
  51   char name[1];
  52 };
  53 typedef struct domaininfo_s *domaininfo_t;
  54
  55 /* And the hashed array.  */
  56 static domaininfo_t domainbuckets[NO_OF_DOMAINBUCKETS];
  57
  58
  59 /* The hash function we use.  Must not call a system function.  */
  60 static inline u32
  61 hash_domain (const char *domain)
  62 {
  63   const unsigned char *s = (const unsigned char*)domain;
  64   u32 hashval = 0;
  65   u32 carry;
  66
  67   for (; *s; s++)
  68     {
  69       if (*s == '.')
  70         continue;
  71       hashval = (hashval << 4) + *s;
  72       if ((carry = (hashval & 0xf0000000)))
  73         {
  74           hashval ^= (carry >> 24);
  75           hashval ^= carry;
  76         }
  77     }
  78
  79   return hashval % NO_OF_DOMAINBUCKETS;
  80 }
  81
  82
  83 void
  84 domaininfo_print_stats (ctrl_t ctrl)
  85 {
  86   int bidx;
  87   domaininfo_t di;
  88   int count, no_name, wkd_not_found, wkd_supported, wkd_not_supported;
  89   int len, minlen, maxlen;
  90
  91   count = no_name = wkd_not_found = wkd_supported = wkd_not_supported = 0;
  92   maxlen = 0;
  93   minlen = -1;
  94   for (bidx = 0; bidx < NO_OF_DOMAINBUCKETS; bidx++)
  95     {
  96       len = 0;
  97       for (di = domainbuckets[bidx]; di; di = di->next)
  98         {
  99           count++;
 100           len++;
 101           if (di->no_name)
 102             no_name++;
 103           if (di->wkd_not_found)
 104             wkd_not_found++;
 105           if (di->wkd_supported)
 106             wkd_supported++;
 107           if (di->wkd_not_supported)
 108             wkd_not_supported++;
 109         }
 110       if (len > maxlen)
 111         maxlen = len;
 112       if (minlen == -1 || len < minlen)
 113         minlen = len;
 114     }
 115   dirmngr_status_helpf
 116     (ctrl, "domaininfo: items=%d chainlen=%d..%d nn=%d nf=%d ns=%d s=%d\n",
 117      count,
 118      minlen > 0? minlen : 0,
 119      maxlen,
 120      no_name, wkd_not_found, wkd_not_supported, wkd_supported);
 121 }
 122
 123
 124 /* Return true if DOMAIN definitely does not support WKD.  Note that
 125  * DOMAIN is expected to be lowercase.  */
 126 int
 127 domaininfo_is_wkd_not_supported (const char *domain)
 128 {
 129   domaininfo_t di;
 130
 131   for (di = domainbuckets[hash_domain (domain)]; di; di = di->next)
 132     if (!strcmp (di->name, domain))
 133       return !!di->wkd_not_supported;
 134
 135   return 0;  /* We don't know.  */
 136 }
 137
 138
 139 /* Core update function.  DOMAIN is expected to be lowercase.
 140  * CALLBACK is called to update the existing or the newly inserted
 141  * item.  */
 142 static void
 143 insert_or_update (const char *domain,
 144                   void (*callback)(domaininfo_t di, int insert_mode))
 145 {
 146   domaininfo_t di;
 147   domaininfo_t di_new;
 148   domaininfo_t drop = NULL;
 149   domaininfo_t drop_extra = NULL;
 150   int nkept = 0;
 151   int ndropped = 0;
 152   u32 hash;
 153   int count;
 154
 155   hash = hash_domain (domain);
 156   for (di = domainbuckets[hash]; di; di = di->next)
 157     if (!strcmp (di->name, domain))
 158       {
 159         callback (di, 0);  /* Update */
 160         return;
 161       }
 162
 163   di_new = xtrycalloc (1, sizeof *di + strlen (domain));
 164   if (!di_new)
 165     return;  /* Out of core - we ignore this.  */
 166   strcpy (di_new->name, domain);
 167
 168   /* Need to do another lookup because the malloc is a system call and
 169    * thus the hash array may have been changed by another thread.  */
 170   for (count=0, di = domainbuckets[hash]; di; di = di->next, count++)
 171     if (!strcmp (di->name, domain))
 172       {
 173         callback (di, 0);  /* Update */
 174         xfree (di_new);
 175         return;
 176       }
 177
 178   /* Before we insert we need to check whether the chain gets too long.  */
 179   if (count >= MAX_DOMAINBUCKET_LEN)
 180     {
 181       domaininfo_t bucket;
 182       domaininfo_t *array;
 183       int narray, idx;
 184       domaininfo_t keep = NULL;
 185
 186       /* Unlink from the global list before doing a syscall.  */
 187       bucket = domainbuckets[hash];
 188       domainbuckets[hash] = NULL;
 189
 190       array = xtrycalloc (count, sizeof *array);
 191       if (!array)
 192         {
 193           /* That's bad; give up the entire bucket.  */
 194           log_error ("domaininfo: error allocating helper array: %s\n",
 195                      gpg_strerror (gpg_err_code_from_syserror ()));
 196           drop_extra = bucket;
 197           goto leave;
 198         }
 199       narray = 0;
 200
 201       /* Move all items into an array for easier processing.  */
 202       for (di = bucket; di; di = di->next)
 203         array[narray++] = di;
 204       log_assert (narray == count);
 205
 206       /* Mark all item in the array which are flagged to support wkd
 207        * but not more than half of the maximum.  This way we will at
 208        * the end drop half of the items. */
 209       count = 0;
 210       for (idx=0; idx < narray; idx++)
 211         {
 212           di = array[idx];
 213           di->keepmark = 0; /* Clear flag here on the first pass.  */
 214           if (di->wkd_supported && count < MAX_DOMAINBUCKET_LEN/2)
 215             {
 216               di->keepmark = 1;
 217               count++;
 218             }
 219         }
 220       /* Now mark those which are marked as not found.  */
 221       /* FIXME: we should use an LRU algorithm here.    */
 222       for (idx=0; idx < narray; idx++)
 223         {
 224           di = array[idx];
 225           if (!di->keepmark
 226               && di->wkd_not_supported && count < MAX_DOMAINBUCKET_LEN/2)
 227             {
 228               di->keepmark = 1;
 229               count++;
 230             }
 231         }
 232
 233       /* Build a bucket list and a second list for later freeing the
 234        * items (we can't do it directly because a free is a system
 235        * call and we want to avoid locks in this module.  Note that
 236        * the kept items will be reversed order which does not matter.  */
 237       for (idx=0; idx < narray; idx++)
 238         {
 239           di = array[idx];
 240           if (di->keepmark)
 241             {
 242               di->next = keep;
 243               keep = di;
 244               nkept++;
 245             }
 246           else
 247             {
 248               di->next = drop;
 249               drop = di;
 250               ndropped++;
 251             }
 252         }
 253
 254       /* In case another thread added new stuff to the domain list we
 255        * simply drop them instead all.  It would also be possible to
 256        * append them to our list but then we can't guarantee that a
 257        * bucket list is almost all of the time limited to
 258        * MAX_DOMAINBUCKET_LEN.  Not sure whether this is really a
 259        * sensible strategy.  */
 260       drop_extra = domainbuckets[hash];
 261       domainbuckets[hash] = keep;
 262     }
 263
 264   /* Insert */
 265   callback (di_new, 1);
 266   di = di_new;
 267   di->next = domainbuckets[hash];
 268   domainbuckets[hash] = di;
 269
 270   if (opt.verbose && (nkept || ndropped))
 271     log_info ("domaininfo: bucket=%lu kept=%d purged=%d\n",
 272               (unsigned long)hash, nkept, ndropped);
 273
 274  leave:
 275   /* Remove the dropped items.  */
 276   while (drop)
 277     {
 278       di = drop->next;
 279       xfree (drop);
 280       drop = di;
 281     }
 282   while (drop_extra)
 283     {
 284       di = drop_extra->next;
 285       xfree (drop_extra);
 286       drop_extra = di;
 287     }
 288 }
 289
 290
 291 /* Helper for domaininfo_set_no_name.  May not do any syscalls. */
 292 static void
 293 set_no_name_cb (domaininfo_t di, int insert_mode)
 294 {
 295   (void)insert_mode;
 296
 297   di->no_name = 1;
 298   /* Obviously the domain is in this case also not supported.  */
 299   di->wkd_not_supported = 1;
 300
 301   /* The next should already be 0 but we clear it anyway in the case
 302    * of a temporary DNS failure.  */
 303   di->wkd_supported = 0;
 304 }
 305
 306
 307 /* Mark DOMAIN as not existent.  */
 308 void
 309 domaininfo_set_no_name (const char *domain)
 310 {
 311   insert_or_update (domain, set_no_name_cb);
 312 }
 313
 314
 315 /* Helper for domaininfo_set_wkd_supported.  May not do any syscalls. */
 316 static void
 317 set_wkd_supported_cb (domaininfo_t di, int insert_mode)
 318 {
 319   (void)insert_mode;
 320
 321   di->wkd_supported = 1;
 322   /* The next will already be set unless the domain enabled WKD in the
 323    * meantime.  Thus we need to clear it.  */
 324   di->wkd_not_supported = 0;
 325 }
 326
 327
 328 /* Mark DOMAIN as supporting WKD.  */
 329 void
 330 domaininfo_set_wkd_supported (const char *domain)
 331 {
 332   insert_or_update (domain, set_wkd_supported_cb);
 333 }
 334
 335
 336 /* Helper for domaininfo_set_wkd_not_supported.  May not do any syscalls. */
 337 static void
 338 set_wkd_not_supported_cb (domaininfo_t di, int insert_mode)
 339 {
 340   (void)insert_mode;
 341
 342   di->wkd_not_supported = 1;
 343   di->wkd_supported = 0;
 344 }
 345
 346
 347 /* Mark DOMAIN as not supporting WKD queries (e.g. no policy file).  */
 348 void
 349 domaininfo_set_wkd_not_supported (const char *domain)
 350 {
 351   insert_or_update (domain, set_wkd_not_supported_cb);
 352 }
 353
 354
 355
 356 /* Helper for domaininfo_set_wkd_not_found.  May not do any syscalls. */
 357 static void
 358 set_wkd_not_found_cb (domaininfo_t di, int insert_mode)
 359 {
 360   /* Set the not found flag but there is no need to do this if we
 361    * already know that the domain either does not support WKD or we
 362    * know that it supports WKD.  */
 363   if (insert_mode)
 364     di->wkd_not_found = 1;
 365   else if (!di->wkd_not_supported && !di->wkd_supported)
 366     di->wkd_not_found = 1;
 367
 368   /* Better clear this flag in case we had a DNS failure in the
 369    * past.  */
 370   di->no_name = 0;
 371 }
 372
 373
 374 /* Update a counter for DOMAIN to keep track of failed WKD queries.  */
 375 void
 376 domaininfo_set_wkd_not_found (const char *domain)
 377 {
 378   insert_or_update (domain, set_wkd_not_found_cb);
 379 }