summaryrefslogtreecommitdiffstats
path: root/lib/hash.h (follow)
Commit message (Collapse)AuthorAgeFilesLines
* lib: Reduce size of hash_bucket by 8 bytesDonald Sharp2024-02-011-3/+3
| | | | | | | | pahole reports that the hash_bucket has 2 4 byte holes in the data structure. Let's reorganize this a bit and save 8 bytes per hash_bucket instance. Signed-off-by: Donald Sharp <sharpd@nvidia.com>
* *: Add a hash_clean_and_free() functionDonald Sharp2023-03-211-0/+11
| | | | | | | | | | Add a hash_clean_and_free() function as well as convert the code to use it. This function also takes a double pointer to the hash to set it NULL. Also it cleanly does nothing if the pointer is NULL( as a bunch of code tested for ). Signed-off-by: Donald Sharp <sharpd@nvidia.com>
* *: auto-convert to SPDX License IDsDavid Lamparter2023-02-091-16/+1
| | | | | | Done with a combination of regex'ing and banging my head against a wall. Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* lib: Update hash.h documentation to warn of a possible crashDonald Sharp2022-02-041-5/+8
| | | | | | | | | Multiple deletions from the hash_walk or hash_iteration calls during a single invocation of the passed in function can and will cause the program to crash. Warn against doing such a thing. Signed-off-by: Donald Sharp <sharpd@nvidia.com>
* lib: fix spelling nits in more lib filesewlumpkin2021-10-051-1/+1
| | | | Signed-off-by: ewlumpkin <ewlumpkin@gmail.com>
* *: fix all backetsIgor Ryzhov2021-02-021-1/+1
| | | | Signed-off-by: Igor Ryzhov <iryzhov@nfware.com>
* doc: update doc comment on hash_cmp (round 2)Donatas Abraitis2020-12-101-1/+1
| | | | | | Related: c8aad9c3a4b3e6d6d85fcedaab80cc271015b1f9 Signed-off-by: Donatas Abraitis <donatas.abraitis@gmail.com>
* lib: update doc comment on hash_cmpQuentin Young2020-12-011-1/+1
| | | | Signed-off-by: Quentin Young <qlyoung@nvidia.com>
* lib: add doc to clear-up hash_iterate multi deletionStephen Worley2020-09-281-1/+2
| | | | | | | | | Add some header documentation to make it clear that you cannot delete more than one item during each iteration. Doing so could cause memory corruption for next pointer if its also deleted from the table. Signed-off-by: Stephen Worley <sworley@cumulusnetworks.com>
* *: change hash_backet to hash_bucketDonald Sharp2020-02-281-5/+0
| | | | | | | It's been a year search and destroy. Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com> Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* Revert "*: change hash_backet to hash_bucket"Jafar Al-Gharaibeh2020-02-271-0/+5
| | | | | | | | This reverts commit 3895c42a2eb534a70ef25412547e798c1c1ef5a1. LabN CI update needs to be coordinated before merging this Signed-off-by: Jafar Al-Gharaibeh <jafar@atcorp.com>
* *: change hash_backet to hash_bucketDonald Sharp2020-02-271-5/+0
| | | | | | It's been a year search and destroy. Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
* lib: use MTYPE_STATICDavid Lamparter2019-06-211-3/+0
| | | | Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* lib: hashing functions should take const argumentsQuentin Young2019-05-141-3/+3
| | | | | | | | | | It doesn't make much sense for a hash function to modify its argument, so const the hash input. BGP does it in a couple places, those cast away the const. Not great but not any worse than it was. Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* lib: add compatibility #define for hash_backetQuentin Young2019-02-251-0/+5
| | | | Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* *: Rename backet to bucketTim Bray2019-02-251-11/+11
| | | | | | Presume typo from original author Signed-off-by: Tim Bray <tim@kooky.org>
* lib: add extern "C" {} blocks to all libfrr headersRenato Westphal2019-02-121-0/+8
| | | | | | | These are necessary to use functions defined in these headers from C++. Signed-off-by: David Lamparter <equinox@diac24.net> Signed-off-by: Renato Westphal <renato@opensourcerouting.org>
* lib: make atomic ops C++ compatibleDavid Lamparter2019-02-111-2/+2
| | | | | | | C++ doesn't have ISO C11 stdatomic.h or "_Atomic inttype", so use std::atomic instead to get the headers compatible. Signed-off-by: David Lamparter <equinox@diac24.net>
* *: Replace hash_cmp function return value to a boolDonald Sharp2018-10-191-3/+4
| | | | | | | | | The ->hash_cmp and linked list ->cmp functions were sometimes being used interchangeably and this really is not a good thing. So let's modify the hash_cmp function pointer to return a boolean and convert everything to use the new syntax. Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
* lib: Update hash.h documentationDonald Sharp2018-08-151-1/+7
| | | | | | | | | | | | | The hash_get function when called and the alloc_func returns a NULL value, we do not create a backet nor do we insert anything into the hash. As such backet->data must always be non-NULL. Modify the description in hash_get to inform of this. Additionally indicate that hash_walk and hash_iterate cannot have a NULL backet->data value. Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
* lib: Add some documentationDonald Sharp2018-07-061-2/+6
| | | | | | | Add some documentation to hash_walk/iterate to tell people to not do something stupid. Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
* lib: add proper doc comments for hash & linklistQuentin Young2018-05-251-20/+215
| | | | | | | | * Remove references to ospf source files from linklist.[ch] * Remove documentation comments from hash.c and linklist.c * Add comprehensive documentation comments to linklist.h and hash.h Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* lib: add hash_to_list()Quentin Young2018-05-251-0/+9
| | | | | | Convenience function to convert hash table to an unsorted linked list. Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* lib: use load factor as hash expansion triggerQuentin Young2017-08-091-2/+3
| | | | | | | | | | | | | | | | | | | | | Previous strategy was to resize the hash table when the length of any one bucket exceeded a certain size, with some logic for intelligently stopping resizes when the gains from doing so weren't sufficient. While this was a good idea that attempted to optimize both space and lookup time, unfortunately under transient degenerate conditions this led to some issues with the tables not resizing when they should have, harming performance. The resizing restriction was lifted, but this had the result of exacerbating degenerate behavior and caused out of memory conditions. This patch changes the hash expansion criterion to be based on the number of elements in the table. Once the # of elements in the table exceeds the number of buckets, the table size is doubled. While the space efficiency of this method decreases relative to the perfectness of the hash function, at least this strategy puts the table performance squarely in the hands of the hash function. Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* bgpd: peer hash expands until we are out of memoryDaniel Walton2017-07-311-0/+3
| | | | | | | | | | | | | | | | | | | | | | | Signed-off-by: Daniel Walton <dwalton@cumulusnetworks.com> swpX peers all start out with the same sockunion so initially they all go into the same hash bucket. Once IPv6 ND has worked its magic they will have different sockunions and will go in different buckets...life is good. Until then though, we are in a phase where all swpX peers have the same socknunion. Once we have HASH_THRESHOLD (10) swpX peers and call hash_get for a new swpX peer the hash code calls hash_expand(). This happens because there are more than HASH_THRESHOLD entries in a single bucket so the logic is "expand the hash to spread things out"...in our case expanding doesn't spread out the swpX peers because all of their sockunions are the same. I looked at having peer_hash_make and peer_hash_same consider the ifname of the swpX peer but that is a large change that we don't want to make at the moment. So the fix is to put a cap on how large we are willing to let the hash table get. By default there is no limit but if max_size is set we will not allow the hash to expand above that.
* lib: Remove expansion of hash tableDonald Sharp2017-07-271-3/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The hash code has the idea of stopping expanding the hash table when certain criteria are set. With the recent addition of `show hashtable` we can now see that when we have a full internet feed we've stopped expanding the table at 1k buckets. This results in some serious performance issues at scale. Since we now have the ability to see the statistics on a hash table, let's allow it to expand. Doing so on a full feed showed this: before: Hash table | Buckets Entries Empty LF SD FLF SD ----------------------+---------------------------------------------------------------- route table hash | 1024 1187579 0% 1159.75 34.06 1159.75 35.08 route table hash | 32768 76208 10% 2.33 2.80 2.58 4.03 route table hash | 1024 1187572 0% 1159.74 34.06 1159.74 35.08 route table hash | 2048 76205 0% 37.21 6.13 37.21 7.29 Showing hash table statistics for BGP ------------------------------------- Hash table | Buckets Entries Empty LF SD FLF SD ---------------------+-------------------------------------------------------------- BGP Attributes | 131072 251229 15% 1.92 2.48 2.25 3.33 route table hash | 4096 1187572 0% 289.93 17.03 289.93 17.87 route table hash | 32768 76205 10% 2.33 2.90 2.58 4.21 After: Hash table | Buckets Entries Empty LF SD FLF SD ----------------------+-------------------------------------------------------- route table hash | 1048576 1187349 32% 1.13 2.57 1.67 3.16 route table hash | 32768 76195 10% 2.33 2.81 2.58 4.03 route table hash | 1048576 1187342 32% 1.13 2.58 1.67 3.16 route table hash | 32768 76192 10% 2.33 2.68 2.58 3.81 Showing hash table statistics for BGP ------------------------------------- Hash table | Buckets Entries Empty LF SD FLF SD ---------------------+-------------------------------------------------------- BGP Attributes | 131072 251222 15% 1.92 2.64 2.25 3.58 route table hash | 1048576 1187342 32% 1.13 2.52 1.67 3.07 route table hash | 32768 76192 10% 2.33 2.86 2.58 4.12 We should see some significant performance improvements across the board for full feeds. Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
* *: reindentreindent-master-afterwhitespace / reindent2017-07-171-53/+51
| | | | | | indent.py `git ls-files | pcregrep '\.[ch]$' | pcregrep -v '^(ldpd|babeld|nhrpd)/'` Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* lib: use 32-bit atomics, s/pow/mulQuentin Young2017-07-111-2/+2
| | | | | | | Some platforms don't support 64-bit atomics, missed converting a floating point pow() to an integral mul when changing SD algo. Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* Merge commit '3d22338f04d9554fa' into evpn-prepDavid Lamparter2017-07-101-0/+2
|\ | | | | | | | | | | | | Conflicts: lib/Makefile.am Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
| * lib: Macro for number of entries in hash tablevivek2017-05-251-0/+2
| | | | | | | | Signed-off-by: Vivek Venkatraman <vivek@cumulusnetworks.com>
* | lib, vtysh: hashtable statisticsQuentin Young2017-07-021-6/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Adds the ability to name hash tables, and a new cli command that will show various summary statistics for named hash tables. Statistics computed are - load factor - full load factor (see comments) - stddev of full load factor Standard deviation is computed by storing the sum of squares of bucket lengths. This is somewhat susceptible to overflow. On platforms where a double is 32 bits, placing 65535 or more elements into a hash table opens up the potential for overflow, depending on how they are arranged in buckets (which depends on the hash function). For example, placing 65535 elements into one hash bucket would cause ssq overflow, but distributing 40000000 elements evenly among 400000 buckets (100 elements per bucket) would not. These cases are extremely degenerate, so the vague possibility of overflow in an informational command is deemed an acceptable tradeoff for constant time calculation of variance without locks or compromising efficiency of actual table operations. Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* | lib: add statistics for hash tablesQuentin Young2017-07-021-0/+8
|/ | | | | | | Adds a function that calculates various statistics on our implementation of a hash table. These are useful for evaluating performance. Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* *: make consistent & update GPLv2 file headersDavid Lamparter2017-05-151-18/+18
| | | | | | | | | | | The FSF's address changed, and we had a mixture of comment styles for the GPL file header. (The style with * at the beginning won out with 580 to 141 in existing files.) Note: I've intentionally left intact other "variations" of the copyright header, e.g. whether it says "Zebra", "Quagga", "FRR", or nothing. Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* *: split & distribute memtypes and stop (re|ab)using lib/ MTYPEsDavid Lamparter2016-09-191-0/+5
| | | | | | | | | | | | | | | | | | | This is a rather large mechanical commit that splits up the memory types defined in lib/memtypes.c and distributes them into *_memory.[ch] files in the individual daemons. The zebra change is slightly annoying because there is no nice place to put the #include "zebra_memory.h" statement. bgpd, ospf6d, isisd and some tests were reusing MTYPEs defined in the library for its own use. This is bad practice and would break when the memtype are made static. Acked-by: Vincent JARDIN <vincent.jardin@6wind.com> Acked-by: Donald Sharp <sharpd@cumulusnetworks.com> [CF: rebased for cmaster-next] Signed-off-by: David Lamparter <equinox@opensourcerouting.org> Signed-off-by: Christian Franke <chris@opensourcerouting.org>
* lib: lib-warnings.patchDonald Sharp2015-05-201-1/+1
| | | | | | Remove compile warnings for the lib directory Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com> Reviewed-by:
* BGP: Add dynamic update group supportDonald Sharp2015-05-201-0/+6
| | | | | | | | | | | | | | | | | | | | This patch implements the 'update-groups' functionality in BGP. This is a function that can significantly improve BGP performance for Update generation and resultant network convergence. BGP Updates are formed for "groups" of peers and then replicated and sent out to each peer rather than being formed for each peer. Thus major BGP operations related to outbound policy application, adj-out maintenance and actual Update packet formation are optimized. BGP update-groups dynamically groups peers together based on configuration as well as run-time criteria. Thus, it is more flexible than update-formation based on peer-groups, which relies on operator configuration. [Note that peer-group based update formation has been introduced into BGP by Cumulus but is currently intended only for specific releases.] From 11098af65b2b8f9535484703e7f40330a71cbae4 Mon Sep 17 00:00:00 2001 Subject: [PATCH] updgrp commits
* hash: dynamically grow hash tableStephen Hemminger2013-02-241-1/+5
| | | | | | | | | | | | | | Dynamically grow the hash table index if the chains get too long. If expansion doesn't help keep chain length short, then stop expanding, to avoid bad behavior if there is a poor hash function. Not a new idea, based on concepts in uthash. Depends on my previous patch to restrict hash to power of 2. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> [profiling results: sum of cycles spent in hash_get/jhash with RIPE RIS test data (single simple BGP peer) improved to 69% of previously spent] Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* hash: force size to be a power of 2Stephen Hemminger2013-02-241-1/+1
| | | | | | | | | By forcing the hash table size to be a power of 2, a potentially expensive divide can be replaced by a mask operation. Almost all usage of the hash table was using default size of 1024. Only places with different size was thread library (1011) and bgp aspath. Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* lib: Better hashing of string values using Bernstein hashStephen Hemminger2011-03-211-0/+2
| | | | | | | | | * hash.{h,c}: (string_hash_make) Hash optimised for strings, current implementation using Bernstein hash, which offers a good compromise between distribution and performance. * distribute.c: (distribute_hash_make) use previous instead of additive string hash. * if_rmap.c: (if_rmap_hash_make) ditto
* [lib] hash compare function arguments ought to be const qualifiedStephen Hemminger2008-08-221-3/+3
| | | | | | | | | | | | 2008-08-14 Stephen Hemminger <stephen.hemminger@vyatta.com> * lib/hash.h: (struct hash) Hash comparator callback really ought to treat storage behind arguments as constant - a compare function with side-effects would be evil. * */*.c: Adjust comparator functions similarly, thus fixing at least a few compiler warnings about const qualifier being dropped. Signed-off-by: Paul Jakma <paul@quagga.net>
* 2005-05-06 Paul Jakma <paul@dishone.st>paul2005-05-061-11/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | * (general) extern and static'ification of functions in code and header. Cleanup any definitions with unspecified arguments. Add casts for callback assignments where the callback is defined, typically, as passing void *, but the function being assigned has some other pointer type defined as its argument, as gcc complains about casts from void * to X* via function arguments. Fix some old K&R style function argument definitions. Add noreturn gcc attribute to some functions, as appropriate. Add unused gcc attribute to some functions (eg ones meant to help while debugging) Add guard defines to headers which were missing them. * command.c: (install_node) add const qualifier, still doesnt shut up the warning though, because of the double pointer. (cmp_node) ditto * keychain.c: (key_str2time) Add GET_LONG_RANGE() macro, derived fromn vty.h ones to fix some of the (long) < 0 warnings. * thread.c: (various) use thread_empty (cpu_record_hash_key) should cast to uintptr_t, a stdint.h type * vty.h: Add VTY_GET_IPV4_ADDRESS and VTY_GET_IPV4_PREFIX so they removed from ospfd/ospf_vty.h * zebra.h: Move definition of ZEBRA_PORT to here, to remove dependence of lib on zebra/zserv.h
* Initial revisionpaul2002-12-131-0/+71
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-11 09:31:08 +0100