When trying to track down a MTYPE_TMP memory leak
it's harder to search for it when you happen to
have some usage of ttable_dump. Let's just give
it it's own memory type so that we can avoid
confusion in the future.
Signed-off-by: Donald Sharp <sharpd@nvidia.com>
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>
convert:
frr_with_mutex(..)
to:
frr_with_mutex (..)
To make all our code agree with what clang-format is going to produce
Signed-off-by: Donald Sharp <sharpd@nvidia.com>
Back when I put this together in 2015, ISO C11 was still reasonably new
and we couldn't require it just yet. Without ISO C11, there is no
"good" way (only bad hacks) to require a semicolon after a macro that
ends with a function definition. And if you added one anyway, you'd get
"spurious semicolon" warnings on some compilers...
With C11, `_Static_assert()` at the end of a macro will make it so that
the semicolon is properly required, consumed, and not warned about.
Consistently requiring semicolons after "file-level" macros matches
Linux kernel coding style and helps some editors against mis-syntax'ing
these macros.
Signed-off-by: David Lamparter <equinox@diac24.net>
- tracepoint() -> frrtrace()
- tracelog() -> frrtracelog()
- tracepoint_enabled() -> frrtrace_enabled()
Also removes copypasta'd #ifdefs for those LTTng macros, those are
handled in lib/trace.h
Signed-off-by: Quentin Young <qlyoung@nvidia.com>
hash_get is used for both lookup and insert; add a tracepoint for when
we insert something into the hash
Signed-off-by: Quentin Young <qlyoung@nvidia.com>
Signed values get converted to unsigned for addition, so when the value
to adjust a stats variable for hash tables was negative this resulted in
overflow arithmetic, which we generally don't want.
Signed-off-by: Quentin Young <qlyoung@nvidia.com>
frr_with_mutex(...) { ... } locks and automatically unlocks the listed
mutex(es) when the block is exited. This adds a bit of safety against
forgetting the unlock in error paths & co. and makes the code a slight
bit more readable.
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
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>
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>
When we are iterating through the hash, keep count of how many
we've called and if we have finished calling the hash->size
iterator times, then short-circuit and stop looping over
the entire array.
Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
* 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>
These are mostly trivial fixes for leaks in the error path of some functions.
The changes in bgpd/bgp_mpath.c deserves a bit of explanation though. In
the bgp_info_mpath_aggregate_update() function, we were allocating memory
for the lcomm variable but doing nothing with it. Since the code for
communities, extended communities and large communities is pretty much
the same in this function, it's clear that this was a copy and paste
error where most of the ext. community code was copied but not all of
it as it should have been.
Signed-off-by: Renato Westphal <renato@opensourcerouting.org>
There is no need to generate a hash key *if* the hash_alloc_function
is NULL and the hash is empty.
This changed showed a measurable increase in performance for
table hash lookup for tables that were meant to be empty in
bgp( the distance commands ).
Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
Convert the list_delete(struct list *) function to use
struct list **. This is to allow the list pointer to be nulled.
I keep running into uses of this list_delete function where we
forget to set the returned pointer to NULL and attempt to use
it and then experience a crash, usually after the developer
has long since left the building.
Let's make the api explicit in it setting the list pointer
to null.
Cynical Prediction: This code will expose a attempt
to use the NULL'ed list pointer in some obscure bit
of code.
Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
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>
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.
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>
hash_cmd_init will overwrite _hashes with a new list, while _hashes
already has been initialised from cmd_init(), thread_master_create(), or
any other function that may have created a hash.
Found while valgrind'ing ospf6d/test_lsdb.
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
NetBSD can't take the square root of a long double
and we should be fine just using a double here anyway
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
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>
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>
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>
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>
