2 * Copyright (C) 1998 Kunihiro Ishiguro
4 * This file is part of GNU Zebra.
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.
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.
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
27 #include "termtable.h"
31 #include "frr_pthread.h"
32 #include "libfrr_trace.h"
34 DEFINE_MTYPE_STATIC(LIB
, HASH
, "Hash");
35 DEFINE_MTYPE_STATIC(LIB
, HASH_BUCKET
, "Hash Bucket");
36 DEFINE_MTYPE_STATIC(LIB
, HASH_INDEX
, "Hash Index");
38 static pthread_mutex_t _hashes_mtx
= PTHREAD_MUTEX_INITIALIZER
;
39 static struct list
*_hashes
;
41 struct hash
*hash_create_size(unsigned int size
,
42 unsigned int (*hash_key
)(const void *),
43 bool (*hash_cmp
)(const void *, const void *),
48 assert((size
& (size
- 1)) == 0);
49 hash
= XCALLOC(MTYPE_HASH
, sizeof(struct hash
));
51 XCALLOC(MTYPE_HASH_INDEX
, sizeof(struct hash_bucket
*) * size
);
53 hash
->hash_key
= hash_key
;
54 hash
->hash_cmp
= hash_cmp
;
56 hash
->name
= name
? XSTRDUP(MTYPE_HASH
, name
) : NULL
;
57 hash
->stats
.empty
= hash
->size
;
59 frr_with_mutex(&_hashes_mtx
) {
63 listnode_add(_hashes
, hash
);
69 struct hash
*hash_create(unsigned int (*hash_key
)(const void *),
70 bool (*hash_cmp
)(const void *, const void *),
73 return hash_create_size(HASH_INITIAL_SIZE
, hash_key
, hash_cmp
, name
);
76 void *hash_alloc_intern(void *arg
)
82 * ssq = ssq + (new^2 - old^2)
83 * = ssq + ((new + old) * (new - old))
85 #define hash_update_ssq(hz, old, new) \
87 int _adjust = (new + old) * (new - old); \
89 atomic_fetch_sub_explicit(&hz->stats.ssq, -_adjust, \
90 memory_order_relaxed); \
92 atomic_fetch_add_explicit(&hz->stats.ssq, _adjust, \
93 memory_order_relaxed); \
96 /* Expand hash if the chain length exceeds the threshold. */
97 static void hash_expand(struct hash
*hash
)
99 unsigned int i
, new_size
;
100 struct hash_bucket
*hb
, *hbnext
, **new_index
;
102 new_size
= hash
->size
* 2;
104 if (hash
->max_size
&& new_size
> hash
->max_size
)
107 new_index
= XCALLOC(MTYPE_HASH_INDEX
,
108 sizeof(struct hash_bucket
*) * new_size
);
110 hash
->stats
.empty
= new_size
;
112 for (i
= 0; i
< hash
->size
; i
++)
113 for (hb
= hash
->index
[i
]; hb
; hb
= hbnext
) {
114 unsigned int h
= hb
->key
& (new_size
- 1);
117 hb
->next
= new_index
[h
];
119 int oldlen
= hb
->next
? hb
->next
->len
: 0;
120 int newlen
= oldlen
+ 1;
129 hash_update_ssq(hash
, oldlen
, newlen
);
134 /* Switch to new table */
135 XFREE(MTYPE_HASH_INDEX
, hash
->index
);
136 hash
->size
= new_size
;
137 hash
->index
= new_index
;
140 void *hash_get(struct hash
*hash
, void *data
, void *(*alloc_func
)(void *))
142 frrtrace(2, frr_libfrr
, hash_get
, hash
, data
);
147 struct hash_bucket
*bucket
;
149 if (!alloc_func
&& !hash
->count
)
152 key
= (*hash
->hash_key
)(data
);
153 index
= key
& (hash
->size
- 1);
155 for (bucket
= hash
->index
[index
]; bucket
!= NULL
;
156 bucket
= bucket
->next
) {
157 if (bucket
->key
== key
&& (*hash
->hash_cmp
)(bucket
->data
, data
))
162 newdata
= (*alloc_func
)(data
);
166 if (HASH_THRESHOLD(hash
->count
+ 1, hash
->size
)) {
168 index
= key
& (hash
->size
- 1);
171 bucket
= XCALLOC(MTYPE_HASH_BUCKET
, sizeof(struct hash_bucket
));
172 bucket
->data
= newdata
;
174 bucket
->next
= hash
->index
[index
];
175 hash
->index
[index
] = bucket
;
178 frrtrace(3, frr_libfrr
, hash_insert
, hash
, data
, key
);
180 int oldlen
= bucket
->next
? bucket
->next
->len
: 0;
181 int newlen
= oldlen
+ 1;
186 bucket
->next
->len
= 0;
188 bucket
->len
= newlen
;
190 hash_update_ssq(hash
, oldlen
, newlen
);
197 void *hash_lookup(struct hash
*hash
, void *data
)
199 return hash_get(hash
, data
, NULL
);
202 unsigned int string_hash_make(const char *str
)
204 unsigned int hash
= 0;
207 hash
= (hash
* 33) ^ (unsigned int)*str
++;
212 void *hash_release(struct hash
*hash
, void *data
)
217 struct hash_bucket
*bucket
;
218 struct hash_bucket
*pp
;
220 key
= (*hash
->hash_key
)(data
);
221 index
= key
& (hash
->size
- 1);
223 for (bucket
= pp
= hash
->index
[index
]; bucket
; bucket
= bucket
->next
) {
224 if (bucket
->key
== key
225 && (*hash
->hash_cmp
)(bucket
->data
, data
)) {
226 int oldlen
= hash
->index
[index
]->len
;
227 int newlen
= oldlen
- 1;
230 hash
->index
[index
] = bucket
->next
;
232 pp
->next
= bucket
->next
;
234 if (hash
->index
[index
])
235 hash
->index
[index
]->len
= newlen
;
239 hash_update_ssq(hash
, oldlen
, newlen
);
242 XFREE(MTYPE_HASH_BUCKET
, bucket
);
249 frrtrace(3, frr_libfrr
, hash_release
, hash
, data
, ret
);
254 void hash_iterate(struct hash
*hash
, void (*func
)(struct hash_bucket
*, void *),
258 struct hash_bucket
*hb
;
259 struct hash_bucket
*hbnext
;
261 for (i
= 0; i
< hash
->size
; i
++)
262 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
271 void hash_walk(struct hash
*hash
, int (*func
)(struct hash_bucket
*, void *),
275 struct hash_bucket
*hb
;
276 struct hash_bucket
*hbnext
;
277 int ret
= HASHWALK_CONTINUE
;
279 for (i
= 0; i
< hash
->size
; i
++) {
280 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
285 ret
= (*func
)(hb
, arg
);
286 if (ret
== HASHWALK_ABORT
)
292 void hash_clean(struct hash
*hash
, void (*free_func
)(void *))
295 struct hash_bucket
*hb
;
296 struct hash_bucket
*next
;
298 for (i
= 0; i
< hash
->size
; i
++) {
299 for (hb
= hash
->index
[i
]; hb
; hb
= next
) {
303 (*free_func
)(hb
->data
);
305 XFREE(MTYPE_HASH_BUCKET
, hb
);
308 hash
->index
[i
] = NULL
;
312 hash
->stats
.empty
= hash
->size
;
315 static void hash_to_list_iter(struct hash_bucket
*hb
, void *arg
)
317 struct list
*list
= arg
;
319 listnode_add(list
, hb
->data
);
322 struct list
*hash_to_list(struct hash
*hash
)
324 struct list
*list
= list_new();
326 hash_iterate(hash
, hash_to_list_iter
, list
);
330 void hash_free(struct hash
*hash
)
332 frr_with_mutex(&_hashes_mtx
) {
334 listnode_delete(_hashes
, hash
);
335 if (_hashes
->count
== 0) {
336 list_delete(&_hashes
);
341 XFREE(MTYPE_HASH
, hash
->name
);
343 XFREE(MTYPE_HASH_INDEX
, hash
->index
);
344 XFREE(MTYPE_HASH
, hash
);
348 /* CLI commands ------------------------------------------------------------ */
350 DEFUN_NOSH(show_hash_stats
,
352 "show debugging hashtable [statistics]",
355 "Statistics about hash tables\n"
356 "Statistics about hash tables\n")
360 struct ttable
*tt
= ttable_new(&ttable_styles
[TTSTYLE_BLANK
]);
362 ttable_add_row(tt
, "Hash table|Buckets|Entries|Empty|LF|SD|FLF|SD");
363 tt
->style
.cell
.lpad
= 2;
364 tt
->style
.cell
.rpad
= 1;
365 tt
->style
.corner
= '+';
367 ttable_rowseps(tt
, 0, BOTTOM
, true, '-');
369 /* Summary statistics calculated are:
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
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.
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.
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.
393 double lf
; // load factor
394 double flf
; // full load factor
395 double var
; // overall variance
396 double fvar
; // full variance
397 double stdv
; // overall stddev
398 double fstdv
; // full stddev
400 long double x2
; // h->count ^ 2
401 long double ldc
; // (long double) h->count
402 long double full
; // h->size - h->stats.empty
403 long double ssq
; // ssq casted to long double
405 pthread_mutex_lock(&_hashes_mtx
);
407 pthread_mutex_unlock(&_hashes_mtx
);
409 vty_out(vty
, "No hash tables in use.\n");
413 for (ALL_LIST_ELEMENTS_RO(_hashes
, ln
, h
)) {
417 ssq
= (long double)h
->stats
.ssq
;
418 x2
= h
->count
* h
->count
;
419 ldc
= (long double)h
->count
;
420 full
= h
->size
- h
->stats
.empty
;
421 lf
= h
->count
/ (double)h
->size
;
422 flf
= full
? h
->count
/ (double)(full
) : 0;
423 var
= ldc
? (1.0 / ldc
) * (ssq
- x2
/ ldc
) : 0;
424 fvar
= full
? (1.0 / full
) * (ssq
- x2
/ full
) : 0;
425 var
= (var
< .0001) ? 0 : var
;
426 fvar
= (fvar
< .0001) ? 0 : fvar
;
430 ttable_add_row(tt
, "%s|%d|%ld|%.0f%%|%.2lf|%.2lf|%.2lf|%.2lf",
431 h
->name
, h
->size
, h
->count
,
432 (h
->stats
.empty
/ (double)h
->size
) * 100, lf
,
435 pthread_mutex_unlock(&_hashes_mtx
);
438 char header
[] = "Showing hash table statistics for ";
439 char underln
[sizeof(header
) + strlen(frr_protonameinst
)];
440 memset(underln
, '-', sizeof(underln
));
441 underln
[sizeof(underln
) - 1] = '\0';
442 vty_out(vty
, "%s%s\n", header
, frr_protonameinst
);
443 vty_out(vty
, "%s\n", underln
);
445 vty_out(vty
, "# allocated: %d\n", _hashes
->count
);
446 vty_out(vty
, "# named: %d\n\n", tt
->nrows
- 1);
449 ttable_colseps(tt
, 0, RIGHT
, true, '|');
450 char *table
= ttable_dump(tt
, "\n");
451 vty_out(vty
, "%s\n", table
);
452 XFREE(MTYPE_TMP
, table
);
454 vty_out(vty
, "No named hash tables to display.\n");
461 void hash_cmd_init(void)
463 install_element(ENABLE_NODE
, &show_hash_stats_cmd
);