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
hash_domain(const char * domain)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
domaininfo_print_stats(void)84 domaininfo_print_stats (void)
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 log_info ("domaininfo: items=%d chainlen=%d..%d nn=%d nf=%d ns=%d s=%d\n",
116 count,
117 minlen > 0? minlen : 0,
118 maxlen,
119 no_name, wkd_not_found, wkd_not_supported, wkd_supported);
120 }
121
122
123 /* Return true if DOMAIN definitely does not support WKD. Note that
124 * DOMAIN is expected to be lowercase. */
125 int
domaininfo_is_wkd_not_supported(const char * domain)126 domaininfo_is_wkd_not_supported (const char *domain)
127 {
128 domaininfo_t di;
129
130 for (di = domainbuckets[hash_domain (domain)]; di; di = di->next)
131 if (!strcmp (di->name, domain))
132 return !!di->wkd_not_supported;
133
134 return 0; /* We don't know. */
135 }
136
137
138 /* Core update function. DOMAIN is expected to be lowercase.
139 * CALLBACK is called to update the existing or the newly inserted
140 * item. */
141 static void
insert_or_update(const char * domain,void (* callback)(domaininfo_t di,int insert_mode))142 insert_or_update (const char *domain,
143 void (*callback)(domaininfo_t di, int insert_mode))
144 {
145 domaininfo_t di;
146 domaininfo_t di_new;
147 domaininfo_t drop = NULL;
148 domaininfo_t drop_extra = NULL;
149 int nkept = 0;
150 int ndropped = 0;
151 u32 hash;
152 int count;
153
154 hash = hash_domain (domain);
155 for (di = domainbuckets[hash]; di; di = di->next)
156 if (!strcmp (di->name, domain))
157 {
158 callback (di, 0); /* Update */
159 return;
160 }
161
162 di_new = xtrycalloc (1, sizeof *di + strlen (domain));
163 if (!di_new)
164 return; /* Out of core - we ignore this. */
165 strcpy (di_new->name, domain);
166
167 /* Need to do another lookup because the malloc is a system call and
168 * thus the hash array may have been changed by another thread. */
169 for (count=0, di = domainbuckets[hash]; di; di = di->next, count++)
170 if (!strcmp (di->name, domain))
171 {
172 callback (di, 0); /* Update */
173 xfree (di_new);
174 return;
175 }
176
177 /* Before we insert we need to check whether the chain gets too long. */
178 if (count >= MAX_DOMAINBUCKET_LEN)
179 {
180 domaininfo_t bucket;
181 domaininfo_t *array;
182 int narray, idx;
183 domaininfo_t keep = NULL;
184
185 /* Unlink from the global list before doing a syscall. */
186 bucket = domainbuckets[hash];
187 domainbuckets[hash] = NULL;
188
189 array = xtrycalloc (count, sizeof *array);
190 if (!array)
191 {
192 /* That's bad; give up the entire bucket. */
193 log_error ("domaininfo: error allocating helper array: %s\n",
194 gpg_strerror (gpg_err_code_from_syserror ()));
195 drop_extra = bucket;
196 goto leave;
197 }
198 narray = 0;
199
200 /* Move all items into an array for easier processing. */
201 for (di = bucket; di; di = di->next)
202 array[narray++] = di;
203 log_assert (narray == count);
204
205 /* Mark all item in the array which are flagged to support wkd
206 * but not more than half of the maximum. This way we will at
207 * the end drop half of the items. */
208 count = 0;
209 for (idx=0; idx < narray; idx++)
210 {
211 di = array[idx];
212 di->keepmark = 0; /* Clear flag here on the first pass. */
213 if (di->wkd_supported && count < MAX_DOMAINBUCKET_LEN/2)
214 {
215 di->keepmark = 1;
216 count++;
217 }
218 }
219 /* Now mark those which are marked as not found. */
220 /* FIXME: we should use an LRU algorithm here. */
221 for (idx=0; idx < narray; idx++)
222 {
223 di = array[idx];
224 if (!di->keepmark
225 && di->wkd_not_supported && count < MAX_DOMAINBUCKET_LEN/2)
226 {
227 di->keepmark = 1;
228 count++;
229 }
230 }
231
232 /* Build a bucket list and a second list for later freeing the
233 * items (we can't do it directly because a free is a system
234 * call and we want to avoid locks in this module. Note that
235 * the kept items will be reversed order which does not matter. */
236 for (idx=0; idx < narray; idx++)
237 {
238 di = array[idx];
239 if (di->keepmark)
240 {
241 di->next = keep;
242 keep = di;
243 nkept++;
244 }
245 else
246 {
247 di->next = drop;
248 drop = di;
249 ndropped++;
250 }
251 }
252
253 /* In case another thread added new stuff to the domain list we
254 * simply drop them instead all. It would also be possible to
255 * append them to our list but then we can't guarantee that a
256 * bucket list is almost all of the time limited to
257 * MAX_DOMAINBUCKET_LEN. Not sure whether this is really a
258 * sensible strategy. */
259 drop_extra = domainbuckets[hash];
260 domainbuckets[hash] = keep;
261 }
262
263 /* Insert */
264 callback (di_new, 1);
265 di = di_new;
266 di->next = domainbuckets[hash];
267 domainbuckets[hash] = di;
268
269 if (opt.verbose && (nkept || ndropped))
270 log_info ("domaininfo: bucket=%lu kept=%d purged=%d\n",
271 (unsigned long)hash, nkept, ndropped);
272
273 leave:
274 /* Remove the dropped items. */
275 while (drop)
276 {
277 di = drop->next;
278 xfree (drop);
279 drop = di;
280 }
281 while (drop_extra)
282 {
283 di = drop_extra->next;
284 xfree (drop_extra);
285 drop_extra = di;
286 }
287 }
288
289
290 /* Helper for domaininfo_set_no_name. May not do any syscalls. */
291 static void
set_no_name_cb(domaininfo_t di,int insert_mode)292 set_no_name_cb (domaininfo_t di, int insert_mode)
293 {
294 (void)insert_mode;
295
296 di->no_name = 1;
297 /* Obviously the domain is in this case also not supported. */
298 di->wkd_not_supported = 1;
299
300 /* The next should already be 0 but we clear it anyway in the case
301 * of a temporary DNS failure. */
302 di->wkd_supported = 0;
303 }
304
305
306 /* Mark DOMAIN as not existent. */
307 void
domaininfo_set_no_name(const char * domain)308 domaininfo_set_no_name (const char *domain)
309 {
310 insert_or_update (domain, set_no_name_cb);
311 }
312
313
314 /* Helper for domaininfo_set_wkd_supported. May not do any syscalls. */
315 static void
set_wkd_supported_cb(domaininfo_t di,int insert_mode)316 set_wkd_supported_cb (domaininfo_t di, int insert_mode)
317 {
318 (void)insert_mode;
319
320 di->wkd_supported = 1;
321 /* The next will already be set unless the domain enabled WKD in the
322 * meantime. Thus we need to clear it. */
323 di->wkd_not_supported = 0;
324 }
325
326
327 /* Mark DOMAIN as supporting WKD. */
328 void
domaininfo_set_wkd_supported(const char * domain)329 domaininfo_set_wkd_supported (const char *domain)
330 {
331 insert_or_update (domain, set_wkd_supported_cb);
332 }
333
334
335 /* Helper for domaininfo_set_wkd_not_supported. May not do any syscalls. */
336 static void
set_wkd_not_supported_cb(domaininfo_t di,int insert_mode)337 set_wkd_not_supported_cb (domaininfo_t di, int insert_mode)
338 {
339 (void)insert_mode;
340
341 di->wkd_not_supported = 1;
342 di->wkd_supported = 0;
343 }
344
345
346 /* Mark DOMAIN as not supporting WKD queries (e.g. no policy file). */
347 void
domaininfo_set_wkd_not_supported(const char * domain)348 domaininfo_set_wkd_not_supported (const char *domain)
349 {
350 insert_or_update (domain, set_wkd_not_supported_cb);
351 }
352
353
354
355 /* Helper for domaininfo_set_wkd_not_found. May not do any syscalls. */
356 static void
set_wkd_not_found_cb(domaininfo_t di,int insert_mode)357 set_wkd_not_found_cb (domaininfo_t di, int insert_mode)
358 {
359 /* Set the not found flag but there is no need to do this if we
360 * already know that the domain either does not support WKD or we
361 * know that it supports WKD. */
362 if (insert_mode)
363 di->wkd_not_found = 1;
364 else if (!di->wkd_not_supported && !di->wkd_supported)
365 di->wkd_not_found = 1;
366
367 /* Better clear this flag in case we had a DNS failure in the
368 * past. */
369 di->no_name = 0;
370 }
371
372
373 /* Update a counter for DOMAIN to keep track of failed WKD queries. */
374 void
domaininfo_set_wkd_not_found(const char * domain)375 domaininfo_set_wkd_not_found (const char *domain)
376 {
377 insert_or_update (domain, set_wkd_not_found_cb);
378 }
379