| Age | Commit message (Collapse) | Author |
|---|
|
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>
|
|
Signed-off-by: Igor Ryzhov <iryzhov@nfware.com>
|
|
- 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>
|
|
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>
|
|
Define some initial tracepoints for hash table operations, thread
schedules, and thread cancels
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>
|
|
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>
|
|
Don't need these in our DSO tables
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
|
|
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
|
|
They never return NULL
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
|
|
Presume typo from original author
Signed-off-by: Tim Bray <tim@kooky.org>
|
|
Signed-off-by: Ruben Kerkhof <ruben@rubenkerkhof.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>
|
|
Signed-off-by: David Lamparter <equinox@diac24.net>
|
|
This reverts commit fc61644e440c875eefa222ab34d726c6281ca806.
|
|
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>
|
|
Convenience function to convert hash table to an unsorted linked list.
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>
|
|
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
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: Quentin Young <qlyoung@cumulusnetworks.com>
|
|
Signed-off-by: Christian Franke <chris@opensourcerouting.org>
|
|
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.
|
|
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>
|
|
indent.py `git ls-files | pcregrep '\.[ch]$' | pcregrep -v '^(ldpd|babeld|nhrpd)/'`
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
(PRs merged to master added another few vty_outln() calls)
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
Lots of conflicts from CMD_WARNING_CONFIG_FAILED...
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
lib: use 32-bit atomics, s/pow/mul
|
|
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>
|
|
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
|
|
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>
|
|
Remove compile warnings for the lib directory
Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>
Reviewed-by:
|
|
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
|
|
Fixes commit 97c84db00c (hash: dynamically grow hash table). The
no_expand field it's not initialized and could make the hashes to
never grow the table index.
Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Acked-by: Feng Lu <lu.feng@6wind.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
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>
|
|
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>
|
