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