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 670 : DEFINE_MTYPE_STATIC(LIB, HASH, "Hash");
35 670 : DEFINE_MTYPE_STATIC(LIB, HASH_BUCKET, "Hash Bucket");
36 670 : 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 50138 : 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 50138 : struct hash *hash;
47 :
48 50138 : assert((size & (size - 1)) == 0);
49 50138 : hash = XCALLOC(MTYPE_HASH, sizeof(struct hash));
50 100276 : hash->index =
51 50138 : XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_bucket *) * size);
52 50138 : hash->size = size;
53 50138 : hash->hash_key = hash_key;
54 50138 : hash->hash_cmp = hash_cmp;
55 50138 : hash->count = 0;
56 50138 : hash->name = name ? XSTRDUP(MTYPE_HASH, name) : NULL;
57 50138 : hash->stats.empty = hash->size;
58 :
59 100276 : frr_with_mutex (&_hashes_mtx) {
60 50138 : if (!_hashes)
61 226 : _hashes = list_new();
62 :
63 50138 : listnode_add(_hashes, hash);
64 : }
65 :
66 50138 : return hash;
67 : }
68 :
69 2586 : struct hash *hash_create(unsigned int (*hash_key)(const void *),
70 : bool (*hash_cmp)(const void *, const void *),
71 : const char *name)
72 : {
73 2586 : return hash_create_size(HASH_INITIAL_SIZE, hash_key, hash_cmp, name);
74 : }
75 :
76 292759 : void *hash_alloc_intern(void *arg)
77 : {
78 292759 : 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 7216 : static void hash_expand(struct hash *hash)
98 : {
99 7216 : unsigned int i, new_size;
100 7216 : struct hash_bucket *hb, *hbnext, **new_index;
101 :
102 7216 : new_size = hash->size * 2;
103 :
104 7216 : if (hash->max_size && new_size > hash->max_size)
105 : return;
106 :
107 7216 : new_index = XCALLOC(MTYPE_HASH_INDEX,
108 : sizeof(struct hash_bucket *) * new_size);
109 :
110 7216 : hash->stats.empty = new_size;
111 :
112 328072 : for (i = 0; i < hash->size; i++)
113 641712 : for (hb = hash->index[i]; hb; hb = hbnext) {
114 320856 : unsigned int h = hb->key & (new_size - 1);
115 :
116 320856 : hbnext = hb->next;
117 320856 : hb->next = new_index[h];
118 :
119 320856 : int oldlen = hb->next ? hb->next->len : 0;
120 320856 : int newlen = oldlen + 1;
121 :
122 320856 : if (newlen == 1)
123 253231 : hash->stats.empty--;
124 : else
125 67625 : hb->next->len = 0;
126 :
127 320856 : hb->len = newlen;
128 :
129 320856 : hash_update_ssq(hash, oldlen, newlen);
130 :
131 320856 : new_index[h] = hb;
132 : }
133 :
134 : /* Switch to new table */
135 7216 : XFREE(MTYPE_HASH_INDEX, hash->index);
136 7216 : hash->size = new_size;
137 7216 : hash->index = new_index;
138 : }
139 :
140 636003 : void *hash_get(struct hash *hash, void *data, void *(*alloc_func)(void *))
141 : {
142 636003 : frrtrace(2, frr_libfrr, hash_get, hash, data);
143 :
144 636003 : unsigned int key;
145 636003 : unsigned int index;
146 636003 : void *newdata;
147 636003 : struct hash_bucket *bucket;
148 :
149 636003 : if (!alloc_func && !hash->count)
150 : return NULL;
151 :
152 610305 : key = (*hash->hash_key)(data);
153 610307 : index = key & (hash->size - 1);
154 :
155 986584 : for (bucket = hash->index[index]; bucket != NULL;
156 376277 : bucket = bucket->next) {
157 418833 : if (bucket->key == key && (*hash->hash_cmp)(bucket->data, data))
158 42559 : return bucket->data;
159 : }
160 :
161 567751 : if (alloc_func) {
162 301625 : newdata = (*alloc_func)(data);
163 301627 : if (newdata == NULL)
164 : return NULL;
165 :
166 301627 : if (HASH_THRESHOLD(hash->count + 1, hash->size)) {
167 7216 : hash_expand(hash);
168 7216 : index = key & (hash->size - 1);
169 : }
170 :
171 301627 : bucket = XCALLOC(MTYPE_HASH_BUCKET, sizeof(struct hash_bucket));
172 301627 : bucket->data = newdata;
173 301627 : bucket->key = key;
174 301627 : bucket->next = hash->index[index];
175 301627 : hash->index[index] = bucket;
176 301627 : hash->count++;
177 :
178 301627 : frrtrace(3, frr_libfrr, hash_insert, hash, data, key);
179 :
180 301627 : int oldlen = bucket->next ? bucket->next->len : 0;
181 301627 : int newlen = oldlen + 1;
182 :
183 301627 : if (newlen == 1)
184 166250 : hash->stats.empty--;
185 : else
186 135377 : bucket->next->len = 0;
187 :
188 301627 : bucket->len = newlen;
189 :
190 301627 : hash_update_ssq(hash, oldlen, newlen);
191 :
192 301627 : return bucket->data;
193 : }
194 : return NULL;
195 : }
196 :
197 301362 : void *hash_lookup(struct hash *hash, void *data)
198 : {
199 301362 : return hash_get(hash, data, NULL);
200 : }
201 :
202 2084 : unsigned int string_hash_make(const char *str)
203 : {
204 2084 : unsigned int hash = 0;
205 :
206 193558 : while (*str)
207 191474 : hash = (hash * 33) ^ (unsigned int)*str++;
208 :
209 2084 : return hash;
210 : }
211 :
212 4529 : void *hash_release(struct hash *hash, void *data)
213 : {
214 4529 : void *ret = NULL;
215 4529 : unsigned int key;
216 4529 : unsigned int index;
217 4529 : struct hash_bucket *bucket;
218 4529 : struct hash_bucket *pp;
219 :
220 4529 : key = (*hash->hash_key)(data);
221 4529 : index = key & (hash->size - 1);
222 :
223 6248 : for (bucket = pp = hash->index[index]; bucket; bucket = bucket->next) {
224 6208 : if (bucket->key == key
225 5310 : && (*hash->hash_cmp)(bucket->data, data)) {
226 4489 : int oldlen = hash->index[index]->len;
227 4489 : int newlen = oldlen - 1;
228 :
229 4489 : if (bucket == pp)
230 3443 : hash->index[index] = bucket->next;
231 : else
232 1046 : pp->next = bucket->next;
233 :
234 4489 : if (hash->index[index])
235 1404 : hash->index[index]->len = newlen;
236 : else
237 3085 : hash->stats.empty++;
238 :
239 4489 : hash_update_ssq(hash, oldlen, newlen);
240 :
241 4489 : ret = bucket->data;
242 4489 : XFREE(MTYPE_HASH_BUCKET, bucket);
243 4489 : hash->count--;
244 4489 : break;
245 : }
246 1719 : pp = bucket;
247 : }
248 :
249 4529 : frrtrace(3, frr_libfrr, hash_release, hash, data, ret);
250 :
251 4529 : return ret;
252 : }
253 :
254 2992 : void hash_iterate(struct hash *hash, void (*func)(struct hash_bucket *, void *),
255 : void *arg)
256 : {
257 2992 : unsigned int i;
258 2992 : struct hash_bucket *hb;
259 2992 : struct hash_bucket *hbnext;
260 :
261 480168 : for (i = 0; i < hash->size; i++)
262 499479 : 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 22303 : hbnext = hb->next;
267 22303 : (*func)(hb, arg);
268 : }
269 2992 : }
270 :
271 1955 : void hash_walk(struct hash *hash, int (*func)(struct hash_bucket *, void *),
272 : void *arg)
273 : {
274 1955 : unsigned int i;
275 1955 : struct hash_bucket *hb;
276 1955 : struct hash_bucket *hbnext;
277 1955 : int ret = HASHWALK_CONTINUE;
278 :
279 566667 : for (i = 0; i < hash->size; i++) {
280 564810 : 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 98 : hbnext = hb->next;
285 98 : ret = (*func)(hb, arg);
286 98 : if (ret == HASHWALK_ABORT)
287 : return;
288 : }
289 : }
290 : }
291 :
292 45039 : void hash_clean(struct hash *hash, void (*free_func)(void *))
293 : {
294 45039 : unsigned int i;
295 45039 : struct hash_bucket *hb;
296 45039 : struct hash_bucket *next;
297 :
298 3721719 : for (i = 0; i < hash->size; i++) {
299 3932690 : for (hb = hash->index[i]; hb; hb = next) {
300 256010 : next = hb->next;
301 :
302 256010 : if (free_func)
303 6604 : (*free_func)(hb->data);
304 :
305 256010 : XFREE(MTYPE_HASH_BUCKET, hb);
306 256010 : hash->count--;
307 : }
308 3676680 : hash->index[i] = NULL;
309 : }
310 :
311 45039 : hash->stats.ssq = 0;
312 45039 : hash->stats.empty = hash->size;
313 45039 : }
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 47930 : void hash_free(struct hash *hash)
331 : {
332 95860 : frr_with_mutex (&_hashes_mtx) {
333 47930 : if (_hashes) {
334 47930 : listnode_delete(_hashes, hash);
335 47930 : if (_hashes->count == 0) {
336 80 : list_delete(&_hashes);
337 : }
338 : }
339 : }
340 :
341 47930 : XFREE(MTYPE_HASH, hash->name);
342 :
343 47930 : XFREE(MTYPE_HASH_INDEX, hash->index);
344 47930 : XFREE(MTYPE_HASH, hash);
345 47930 : }
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 218 : void hash_cmd_init(void)
462 : {
463 218 : install_element(ENABLE_NODE, &show_hash_stats_cmd);
464 218 : }
|
