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 1621 : 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 1621 : struct hash *hash;
47 :
48 1621 : assert((size & (size - 1)) == 0);
49 1621 : hash = XCALLOC(MTYPE_HASH, sizeof(struct hash));
50 3242 : hash->index =
51 1621 : XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_bucket *) * size);
52 1621 : hash->size = size;
53 1621 : hash->hash_key = hash_key;
54 1621 : hash->hash_cmp = hash_cmp;
55 1621 : hash->count = 0;
56 1621 : hash->name = name ? XSTRDUP(MTYPE_HASH, name) : NULL;
57 1621 : hash->stats.empty = hash->size;
58 :
59 3242 : frr_with_mutex (&_hashes_mtx) {
60 1621 : if (!_hashes)
61 6 : _hashes = list_new();
62 :
63 1621 : listnode_add(_hashes, hash);
64 : }
65 :
66 1621 : return hash;
67 : }
68 :
69 85 : struct hash *hash_create(unsigned int (*hash_key)(const void *),
70 : bool (*hash_cmp)(const void *, const void *),
71 : const char *name)
72 : {
73 85 : return hash_create_size(HASH_INITIAL_SIZE, hash_key, hash_cmp, name);
74 : }
75 :
76 10183 : void *hash_alloc_intern(void *arg)
77 : {
78 10183 : 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 245 : static void hash_expand(struct hash *hash)
98 : {
99 245 : unsigned int i, new_size;
100 245 : struct hash_bucket *hb, *hbnext, **new_index;
101 :
102 245 : new_size = hash->size * 2;
103 :
104 245 : if (hash->max_size && new_size > hash->max_size)
105 : return;
106 :
107 245 : new_index = XCALLOC(MTYPE_HASH_INDEX,
108 : sizeof(struct hash_bucket *) * new_size);
109 :
110 245 : hash->stats.empty = new_size;
111 :
112 11669 : for (i = 0; i < hash->size; i++)
113 22848 : for (hb = hash->index[i]; hb; hb = hbnext) {
114 11424 : unsigned int h = hb->key & (new_size - 1);
115 :
116 11424 : hbnext = hb->next;
117 11424 : hb->next = new_index[h];
118 :
119 11424 : int oldlen = hb->next ? hb->next->len : 0;
120 11424 : int newlen = oldlen + 1;
121 :
122 11424 : if (newlen == 1)
123 8973 : hash->stats.empty--;
124 : else
125 2451 : hb->next->len = 0;
126 :
127 11424 : hb->len = newlen;
128 :
129 11424 : hash_update_ssq(hash, oldlen, newlen);
130 :
131 11424 : new_index[h] = hb;
132 : }
133 :
134 : /* Switch to new table */
135 245 : XFREE(MTYPE_HASH_INDEX, hash->index);
136 245 : hash->size = new_size;
137 245 : hash->index = new_index;
138 : }
139 :
140 20608 : void *hash_get(struct hash *hash, void *data, void *(*alloc_func)(void *))
141 : {
142 20608 : frrtrace(2, frr_libfrr, hash_get, hash, data);
143 :
144 20608 : unsigned int key;
145 20608 : unsigned int index;
146 20608 : void *newdata;
147 20608 : struct hash_bucket *bucket;
148 :
149 20608 : if (!alloc_func && !hash->count)
150 : return NULL;
151 :
152 20217 : key = (*hash->hash_key)(data);
153 20218 : index = key & (hash->size - 1);
154 :
155 33305 : for (bucket = hash->index[index]; bucket != NULL;
156 13087 : bucket = bucket->next) {
157 13701 : if (bucket->key == key && (*hash->hash_cmp)(bucket->data, data))
158 614 : return bucket->data;
159 : }
160 :
161 19604 : if (alloc_func) {
162 10374 : newdata = (*alloc_func)(data);
163 10374 : if (newdata == NULL)
164 : return NULL;
165 :
166 10374 : if (HASH_THRESHOLD(hash->count + 1, hash->size)) {
167 245 : hash_expand(hash);
168 245 : index = key & (hash->size - 1);
169 : }
170 :
171 10374 : bucket = XCALLOC(MTYPE_HASH_BUCKET, sizeof(struct hash_bucket));
172 10374 : bucket->data = newdata;
173 10374 : bucket->key = key;
174 10374 : bucket->next = hash->index[index];
175 10374 : hash->index[index] = bucket;
176 10374 : hash->count++;
177 :
178 10374 : frrtrace(3, frr_libfrr, hash_insert, hash, data, key);
179 :
180 10374 : int oldlen = bucket->next ? bucket->next->len : 0;
181 10374 : int newlen = oldlen + 1;
182 :
183 10374 : if (newlen == 1)
184 5604 : hash->stats.empty--;
185 : else
186 4770 : bucket->next->len = 0;
187 :
188 10374 : bucket->len = newlen;
189 :
190 10374 : hash_update_ssq(hash, oldlen, newlen);
191 :
192 10374 : return bucket->data;
193 : }
194 : return NULL;
195 : }
196 :
197 9797 : void *hash_lookup(struct hash *hash, void *data)
198 : {
199 9797 : return hash_get(hash, data, NULL);
200 : }
201 :
202 3 : unsigned int string_hash_make(const char *str)
203 : {
204 3 : unsigned int hash = 0;
205 :
206 129 : while (*str)
207 126 : hash = (hash * 33) ^ (unsigned int)*str++;
208 :
209 3 : return hash;
210 : }
211 :
212 106 : void *hash_release(struct hash *hash, void *data)
213 : {
214 106 : void *ret = NULL;
215 106 : unsigned int key;
216 106 : unsigned int index;
217 106 : struct hash_bucket *bucket;
218 106 : struct hash_bucket *pp;
219 :
220 106 : key = (*hash->hash_key)(data);
221 106 : index = key & (hash->size - 1);
222 :
223 162 : for (bucket = pp = hash->index[index]; bucket; bucket = bucket->next) {
224 160 : if (bucket->key == key
225 122 : && (*hash->hash_cmp)(bucket->data, data)) {
226 104 : int oldlen = hash->index[index]->len;
227 104 : int newlen = oldlen - 1;
228 :
229 104 : if (bucket == pp)
230 75 : hash->index[index] = bucket->next;
231 : else
232 29 : pp->next = bucket->next;
233 :
234 104 : if (hash->index[index])
235 35 : hash->index[index]->len = newlen;
236 : else
237 69 : hash->stats.empty++;
238 :
239 104 : hash_update_ssq(hash, oldlen, newlen);
240 :
241 104 : ret = bucket->data;
242 104 : XFREE(MTYPE_HASH_BUCKET, bucket);
243 104 : hash->count--;
244 104 : break;
245 : }
246 56 : pp = bucket;
247 : }
248 :
249 106 : frrtrace(3, frr_libfrr, hash_release, hash, data, ret);
250 :
251 106 : return ret;
252 : }
253 :
254 89 : void hash_iterate(struct hash *hash, void (*func)(struct hash_bucket *, void *),
255 : void *arg)
256 : {
257 89 : unsigned int i;
258 89 : struct hash_bucket *hb;
259 89 : struct hash_bucket *hbnext;
260 :
261 19049 : for (i = 0; i < hash->size; i++)
262 19009 : 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 49 : hbnext = hb->next;
267 49 : (*func)(hb, arg);
268 : }
269 89 : }
270 :
271 3 : void hash_walk(struct hash *hash, int (*func)(struct hash_bucket *, void *),
272 : void *arg)
273 : {
274 3 : unsigned int i;
275 3 : struct hash_bucket *hb;
276 3 : struct hash_bucket *hbnext;
277 3 : int ret = HASHWALK_CONTINUE;
278 :
279 27 : for (i = 0; i < hash->size; i++) {
280 24 : 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 0 : hbnext = hb->next;
285 0 : ret = (*func)(hb, arg);
286 0 : if (ret == HASHWALK_ABORT)
287 : return;
288 : }
289 : }
290 : }
291 :
292 1514 : void hash_clean(struct hash *hash, void (*free_func)(void *))
293 : {
294 1514 : unsigned int i;
295 1514 : struct hash_bucket *hb;
296 1514 : struct hash_bucket *next;
297 :
298 174298 : for (i = 0; i < hash->size; i++) {
299 183054 : for (hb = hash->index[i]; hb; hb = next) {
300 10270 : next = hb->next;
301 :
302 10270 : if (free_func)
303 145 : (*free_func)(hb->data);
304 :
305 10270 : XFREE(MTYPE_HASH_BUCKET, hb);
306 10270 : hash->count--;
307 : }
308 172784 : hash->index[i] = NULL;
309 : }
310 :
311 1514 : hash->stats.ssq = 0;
312 1514 : hash->stats.empty = hash->size;
313 1514 : }
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 1605 : void hash_free(struct hash *hash)
331 : {
332 3210 : frr_with_mutex (&_hashes_mtx) {
333 1605 : if (_hashes) {
334 1605 : listnode_delete(_hashes, hash);
335 1605 : if (_hashes->count == 0) {
336 2 : list_delete(&_hashes);
337 : }
338 : }
339 : }
340 :
341 1605 : XFREE(MTYPE_HASH, hash->name);
342 :
343 1605 : XFREE(MTYPE_HASH_INDEX, hash->index);
344 1605 : XFREE(MTYPE_HASH, hash);
345 1605 : }
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 : }
|
