Line data Source code
1 : /* Hash routine.
2 : * Copyright (C) 1998 Kunihiro Ishiguro
3 : *
4 : * This file is part of GNU Zebra.
5 : *
6 : * GNU Zebra is free software; you can redistribute it and/or modify
7 : * it under the terms of the GNU General Public License as published
8 : * by the Free Software Foundation; either version 2, or (at your
9 : * option) any later version.
10 : *
11 : * GNU Zebra is distributed in the hope that it will be useful, but
12 : * WITHOUT ANY WARRANTY; without even the implied warranty of
13 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 : * General Public License for more details.
15 : *
16 : * You should have received a copy of the GNU General Public License along
17 : * with this program; see the file COPYING; if not, write to the Free Software
18 : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 : */
20 :
21 : #include <zebra.h>
22 : #include <math.h>
23 :
24 : #include "hash.h"
25 : #include "memory.h"
26 : #include "linklist.h"
27 : #include "termtable.h"
28 : #include "vty.h"
29 : #include "command.h"
30 : #include "libfrr.h"
31 : #include "frr_pthread.h"
32 : #include "libfrr_trace.h"
33 :
34 18 : DEFINE_MTYPE_STATIC(LIB, HASH, "Hash");
35 18 : DEFINE_MTYPE_STATIC(LIB, HASH_BUCKET, "Hash Bucket");
36 18 : DEFINE_MTYPE_STATIC(LIB, HASH_INDEX, "Hash Index");
37 :
38 : static pthread_mutex_t _hashes_mtx = PTHREAD_MUTEX_INITIALIZER;
39 : static struct list *_hashes;
40 :
41 1673 : struct hash *hash_create_size(unsigned int size,
42 : unsigned int (*hash_key)(const void *),
43 : bool (*hash_cmp)(const void *, const void *),
44 : const char *name)
45 : {
46 1673 : struct hash *hash;
47 :
48 1673 : assert((size & (size - 1)) == 0);
49 1673 : hash = XCALLOC(MTYPE_HASH, sizeof(struct hash));
50 3346 : hash->index =
51 1673 : XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_bucket *) * size);
52 1673 : hash->size = size;
53 1673 : hash->hash_key = hash_key;
54 1673 : hash->hash_cmp = hash_cmp;
55 1673 : hash->count = 0;
56 1673 : hash->name = name ? XSTRDUP(MTYPE_HASH, name) : NULL;
57 1673 : hash->stats.empty = hash->size;
58 :
59 3346 : frr_with_mutex (&_hashes_mtx) {
60 1673 : if (!_hashes)
61 6 : _hashes = list_new();
62 :
63 1673 : listnode_add(_hashes, hash);
64 : }
65 :
66 1673 : return hash;
67 : }
68 :
69 130 : struct hash *hash_create(unsigned int (*hash_key)(const void *),
70 : bool (*hash_cmp)(const void *, const void *),
71 : const char *name)
72 : {
73 130 : return hash_create_size(HASH_INITIAL_SIZE, hash_key, hash_cmp, name);
74 : }
75 :
76 10219 : void *hash_alloc_intern(void *arg)
77 : {
78 10219 : return arg;
79 : }
80 :
81 : /*
82 : * ssq = ssq + (new^2 - old^2)
83 : * = ssq + ((new + old) * (new - old))
84 : */
85 : #define hash_update_ssq(hz, old, new) \
86 : do { \
87 : int _adjust = (new + old) * (new - old); \
88 : if (_adjust < 0) \
89 : atomic_fetch_sub_explicit(&hz->stats.ssq, -_adjust, \
90 : memory_order_relaxed); \
91 : else \
92 : atomic_fetch_add_explicit(&hz->stats.ssq, _adjust, \
93 : memory_order_relaxed); \
94 : } while (0)
95 :
96 : /* Expand hash if the chain length exceeds the threshold. */
97 249 : static void hash_expand(struct hash *hash)
98 : {
99 249 : unsigned int i, new_size;
100 249 : struct hash_bucket *hb, *hbnext, **new_index;
101 :
102 249 : new_size = hash->size * 2;
103 :
104 249 : if (hash->max_size && new_size > hash->max_size)
105 : return;
106 :
107 249 : new_index = XCALLOC(MTYPE_HASH_INDEX,
108 : sizeof(struct hash_bucket *) * new_size);
109 :
110 249 : hash->stats.empty = new_size;
111 :
112 11721 : for (i = 0; i < hash->size; i++)
113 22944 : for (hb = hash->index[i]; hb; hb = hbnext) {
114 11472 : unsigned int h = hb->key & (new_size - 1);
115 :
116 11472 : hbnext = hb->next;
117 11472 : hb->next = new_index[h];
118 :
119 11472 : int oldlen = hb->next ? hb->next->len : 0;
120 11472 : int newlen = oldlen + 1;
121 :
122 11472 : if (newlen == 1)
123 9077 : hash->stats.empty--;
124 : else
125 2395 : hb->next->len = 0;
126 :
127 11472 : hb->len = newlen;
128 :
129 11472 : hash_update_ssq(hash, oldlen, newlen);
130 :
131 11472 : new_index[h] = hb;
132 : }
133 :
134 : /* Switch to new table */
135 249 : XFREE(MTYPE_HASH_INDEX, hash->index);
136 249 : hash->size = new_size;
137 249 : hash->index = new_index;
138 : }
139 :
140 22031 : void *hash_get(struct hash *hash, void *data, void *(*alloc_func)(void *))
141 : {
142 22031 : frrtrace(2, frr_libfrr, hash_get, hash, data);
143 :
144 22031 : unsigned int key;
145 22031 : unsigned int index;
146 22031 : void *newdata;
147 22031 : struct hash_bucket *bucket;
148 :
149 22031 : if (!alloc_func && !hash->count)
150 : return NULL;
151 :
152 21168 : key = (*hash->hash_key)(data);
153 21168 : index = key & (hash->size - 1);
154 :
155 34316 : for (bucket = hash->index[index]; bucket != NULL;
156 13148 : bucket = bucket->next) {
157 14441 : if (bucket->key == key && (*hash->hash_cmp)(bucket->data, data))
158 1294 : return bucket->data;
159 : }
160 :
161 19875 : if (alloc_func) {
162 10546 : newdata = (*alloc_func)(data);
163 10546 : if (newdata == NULL)
164 : return NULL;
165 :
166 10546 : if (HASH_THRESHOLD(hash->count + 1, hash->size)) {
167 249 : hash_expand(hash);
168 249 : index = key & (hash->size - 1);
169 : }
170 :
171 10546 : bucket = XCALLOC(MTYPE_HASH_BUCKET, sizeof(struct hash_bucket));
172 10546 : bucket->data = newdata;
173 10546 : bucket->key = key;
174 10546 : bucket->next = hash->index[index];
175 10546 : hash->index[index] = bucket;
176 10546 : hash->count++;
177 :
178 10546 : frrtrace(3, frr_libfrr, hash_insert, hash, data, key);
179 :
180 10546 : int oldlen = bucket->next ? bucket->next->len : 0;
181 10546 : int newlen = oldlen + 1;
182 :
183 10546 : if (newlen == 1)
184 5718 : hash->stats.empty--;
185 : else
186 4828 : bucket->next->len = 0;
187 :
188 10546 : bucket->len = newlen;
189 :
190 10546 : hash_update_ssq(hash, oldlen, newlen);
191 :
192 10546 : return bucket->data;
193 : }
194 : return NULL;
195 : }
196 :
197 10519 : void *hash_lookup(struct hash *hash, void *data)
198 : {
199 10519 : return hash_get(hash, data, NULL);
200 : }
201 :
202 60 : unsigned int string_hash_make(const char *str)
203 : {
204 60 : unsigned int hash = 0;
205 :
206 3615 : while (*str)
207 3555 : hash = (hash * 33) ^ (unsigned int)*str++;
208 :
209 60 : return hash;
210 : }
211 :
212 208 : void *hash_release(struct hash *hash, void *data)
213 : {
214 208 : void *ret = NULL;
215 208 : unsigned int key;
216 208 : unsigned int index;
217 208 : struct hash_bucket *bucket;
218 208 : struct hash_bucket *pp;
219 :
220 208 : key = (*hash->hash_key)(data);
221 208 : index = key & (hash->size - 1);
222 :
223 276 : for (bucket = pp = hash->index[index]; bucket; bucket = bucket->next) {
224 273 : if (bucket->key == key
225 231 : && (*hash->hash_cmp)(bucket->data, data)) {
226 205 : int oldlen = hash->index[index]->len;
227 205 : int newlen = oldlen - 1;
228 :
229 205 : if (bucket == pp)
230 168 : hash->index[index] = bucket->next;
231 : else
232 37 : pp->next = bucket->next;
233 :
234 205 : if (hash->index[index])
235 52 : hash->index[index]->len = newlen;
236 : else
237 153 : hash->stats.empty++;
238 :
239 205 : hash_update_ssq(hash, oldlen, newlen);
240 :
241 205 : ret = bucket->data;
242 205 : XFREE(MTYPE_HASH_BUCKET, bucket);
243 205 : hash->count--;
244 205 : break;
245 : }
246 68 : pp = bucket;
247 : }
248 :
249 208 : frrtrace(3, frr_libfrr, hash_release, hash, data, ret);
250 :
251 208 : return ret;
252 : }
253 :
254 130 : void hash_iterate(struct hash *hash, void (*func)(struct hash_bucket *, void *),
255 : void *arg)
256 : {
257 130 : unsigned int i;
258 130 : struct hash_bucket *hb;
259 130 : struct hash_bucket *hbnext;
260 :
261 38106 : for (i = 0; i < hash->size; i++)
262 38107 : for (hb = hash->index[i]; hb; hb = hbnext) {
263 : /* get pointer to next hash bucket here, in case (*func)
264 : * decides to delete hb by calling hash_release
265 : */
266 131 : hbnext = hb->next;
267 131 : (*func)(hb, arg);
268 : }
269 130 : }
270 :
271 186 : void hash_walk(struct hash *hash, int (*func)(struct hash_bucket *, void *),
272 : void *arg)
273 : {
274 186 : unsigned int i;
275 186 : struct hash_bucket *hb;
276 186 : struct hash_bucket *hbnext;
277 186 : int ret = HASHWALK_CONTINUE;
278 :
279 47058 : for (i = 0; i < hash->size; i++) {
280 46882 : for (hb = hash->index[i]; hb; hb = hbnext) {
281 : /* get pointer to next hash bucket here, in case (*func)
282 : * decides to delete hb by calling hash_release
283 : */
284 10 : hbnext = hb->next;
285 10 : ret = (*func)(hb, arg);
286 10 : if (ret == HASHWALK_ABORT)
287 : return;
288 : }
289 : }
290 : }
291 :
292 1535 : void hash_clean(struct hash *hash, void (*free_func)(void *))
293 : {
294 1535 : unsigned int i;
295 1535 : struct hash_bucket *hb;
296 1535 : struct hash_bucket *next;
297 :
298 178255 : for (i = 0; i < hash->size; i++) {
299 187061 : for (hb = hash->index[i]; hb; hb = next) {
300 10341 : next = hb->next;
301 :
302 10341 : if (free_func)
303 209 : (*free_func)(hb->data);
304 :
305 10341 : XFREE(MTYPE_HASH_BUCKET, hb);
306 10341 : hash->count--;
307 : }
308 176720 : hash->index[i] = NULL;
309 : }
310 :
311 1535 : hash->stats.ssq = 0;
312 1535 : hash->stats.empty = hash->size;
313 1535 : }
314 :
315 0 : static void hash_to_list_iter(struct hash_bucket *hb, void *arg)
316 : {
317 0 : struct list *list = arg;
318 :
319 0 : listnode_add(list, hb->data);
320 0 : }
321 :
322 0 : struct list *hash_to_list(struct hash *hash)
323 : {
324 0 : struct list *list = list_new();
325 :
326 0 : hash_iterate(hash, hash_to_list_iter, list);
327 0 : return list;
328 : }
329 :
330 1657 : void hash_free(struct hash *hash)
331 : {
332 3314 : frr_with_mutex (&_hashes_mtx) {
333 1657 : if (_hashes) {
334 1657 : listnode_delete(_hashes, hash);
335 1657 : if (_hashes->count == 0) {
336 2 : list_delete(&_hashes);
337 : }
338 : }
339 : }
340 :
341 1657 : XFREE(MTYPE_HASH, hash->name);
342 :
343 1657 : XFREE(MTYPE_HASH_INDEX, hash->index);
344 1657 : XFREE(MTYPE_HASH, hash);
345 1657 : }
346 :
347 :
348 : /* CLI commands ------------------------------------------------------------ */
349 :
350 0 : DEFUN_NOSH(show_hash_stats,
351 : show_hash_stats_cmd,
352 : "show debugging hashtable [statistics]",
353 : SHOW_STR
354 : DEBUG_STR
355 : "Statistics about hash tables\n"
356 : "Statistics about hash tables\n")
357 0 : {
358 0 : struct hash *h;
359 0 : struct listnode *ln;
360 0 : struct ttable *tt = ttable_new(&ttable_styles[TTSTYLE_BLANK]);
361 :
362 0 : ttable_add_row(tt, "Hash table|Buckets|Entries|Empty|LF|SD|FLF|SD");
363 0 : tt->style.cell.lpad = 2;
364 0 : tt->style.cell.rpad = 1;
365 0 : tt->style.corner = '+';
366 0 : ttable_restyle(tt);
367 0 : ttable_rowseps(tt, 0, BOTTOM, true, '-');
368 :
369 : /* Summary statistics calculated are:
370 : *
371 : * - Load factor: This is the number of elements in the table divided
372 : * by the number of buckets. Since this hash table implementation
373 : * uses chaining, this value can be greater than 1.
374 : * This number provides information on how 'full' the table is, but
375 : * does not provide information on how evenly distributed the
376 : * elements are.
377 : * Notably, a load factor >= 1 does not imply that every bucket has
378 : * an element; with a pathological hash function, all elements could
379 : * be in a single bucket.
380 : *
381 : * - Full load factor: this is the number of elements in the table
382 : * divided by the number of buckets that have some elements in them.
383 : *
384 : * - Std. Dev.: This is the standard deviation calculated from the
385 : * relevant load factor. If the load factor is the mean of number of
386 : * elements per bucket, the standard deviation measures how much any
387 : * particular bucket is likely to deviate from the mean.
388 : * As a rule of thumb this number should be less than 2, and ideally
389 : * <= 1 for optimal performance. A number larger than 3 generally
390 : * indicates a poor hash function.
391 : */
392 :
393 0 : double lf; // load factor
394 0 : double flf; // full load factor
395 0 : double var; // overall variance
396 0 : double fvar; // full variance
397 0 : double stdv; // overall stddev
398 0 : double fstdv; // full stddev
399 :
400 0 : long double x2; // h->count ^ 2
401 0 : long double ldc; // (long double) h->count
402 0 : long double full; // h->size - h->stats.empty
403 0 : long double ssq; // ssq casted to long double
404 :
405 0 : pthread_mutex_lock(&_hashes_mtx);
406 0 : if (!_hashes) {
407 0 : pthread_mutex_unlock(&_hashes_mtx);
408 0 : ttable_del(tt);
409 0 : vty_out(vty, "No hash tables in use.\n");
410 0 : return CMD_SUCCESS;
411 : }
412 :
413 0 : for (ALL_LIST_ELEMENTS_RO(_hashes, ln, h)) {
414 0 : if (!h->name)
415 0 : continue;
416 :
417 0 : ssq = (long double)h->stats.ssq;
418 0 : x2 = h->count * h->count;
419 0 : ldc = (long double)h->count;
420 0 : full = h->size - h->stats.empty;
421 0 : lf = h->count / (double)h->size;
422 0 : flf = full ? h->count / (double)(full) : 0;
423 0 : var = ldc ? (1.0 / ldc) * (ssq - x2 / ldc) : 0;
424 0 : fvar = full ? (1.0 / full) * (ssq - x2 / full) : 0;
425 0 : var = (var < .0001) ? 0 : var;
426 0 : fvar = (fvar < .0001) ? 0 : fvar;
427 0 : stdv = sqrt(var);
428 0 : fstdv = sqrt(fvar);
429 :
430 0 : ttable_add_row(tt, "%s|%d|%ld|%.0f%%|%.2lf|%.2lf|%.2lf|%.2lf",
431 : h->name, h->size, h->count,
432 0 : (h->stats.empty / (double)h->size) * 100, lf,
433 : stdv, flf, fstdv);
434 : }
435 0 : pthread_mutex_unlock(&_hashes_mtx);
436 :
437 : /* display header */
438 0 : char header[] = "Showing hash table statistics for ";
439 0 : char underln[sizeof(header) + strlen(frr_protonameinst)];
440 0 : memset(underln, '-', sizeof(underln));
441 0 : underln[sizeof(underln) - 1] = '\0';
442 0 : vty_out(vty, "%s%s\n", header, frr_protonameinst);
443 0 : vty_out(vty, "%s\n", underln);
444 :
445 0 : vty_out(vty, "# allocated: %d\n", _hashes->count);
446 0 : vty_out(vty, "# named: %d\n\n", tt->nrows - 1);
447 :
448 0 : if (tt->nrows > 1) {
449 0 : ttable_colseps(tt, 0, RIGHT, true, '|');
450 0 : char *table = ttable_dump(tt, "\n");
451 0 : vty_out(vty, "%s\n", table);
452 0 : XFREE(MTYPE_TMP, table);
453 : } else
454 0 : vty_out(vty, "No named hash tables to display.\n");
455 :
456 0 : ttable_del(tt);
457 :
458 0 : return CMD_SUCCESS;
459 : }
460 :
461 6 : void hash_cmd_init(void)
462 : {
463 6 : install_element(ENABLE_NODE, &show_hash_stats_cmd);
464 6 : }
|
