Re-write cmap's loops using multi-variable helpers.
For iterators based on cmap_cursor, we just need to make sure the NODE
variable is not used after the loop, so we set it to NULL.
Acked-by: Eelco Chaudron <echaudro@redhat.com>
Acked-by: Dumitru Ceara <dceara@redhat.com>
Signed-off-by: Adrian Moreno <amorenoz@redhat.com>
Signed-off-by: Ilya Maximets <i.maximets@ovn.org>
Using SHORT version of the *_SAFE loops makes the code cleaner and less
error prone. So, use the SHORT version and remove the extra variable
when possible for hmap and all its derived types.
In order to be able to use both long and short versions without changing
the name of the macro for all the clients, overload the existing name
and select the appropriate version depending on the number of arguments.
Acked-by: Dumitru Ceara <dceara@redhat.com>
Acked-by: Eelco Chaudron <echaudro@redhat.com>
Signed-off-by: Adrian Moreno <amorenoz@redhat.com>
Signed-off-by: Ilya Maximets <i.maximets@ovn.org>
Shadowing is when a variable with a given name in an inner scope hides a
different variable with the same name in a surrounding scope. This is
generally undesirable because it can confuse programmers. This commit
eliminates most of it.
Found with -Wshadow=local in GCC 7. The repo is not really ready to enable
this option by default because of a few cases that are harder to fix, and
harmless, such as nested use of CMAP_FOR_EACH.
Signed-off-by: Ben Pfaff <blp@ovn.org>
Acked-by: Andy Zhou <azhou@ovn.org>
ovs-dpctl and ovs-ofctl lack a read-only option to prevent
running of commands that perform read-write operations. Add
it and the necessary scaffolding to each.
Signed-off-by: Ryan Moats <rmoats@us.ibm.com>
Signed-off-by: Ben Pfaff <blp@ovn.org>
To easily allow both in- and out-of-tree building of the Python
wrapper for the OVS JSON parser (e.g. w/ pip), move json.h to
include/openvswitch. This also requires moving lib/{hmap,shash}.h.
Both hmap.h and shash.h were #include-ing "util.h" even though the
headers themselves did not use anything from there, but rather from
include/openvswitch/util.h. Fixing that required including util.h
in several C files mostly due to OVS_NOT_REACHED and things like
xmalloc.
Signed-off-by: Terry Wilson <twilson@redhat.com>
Signed-off-by: Ben Pfaff <blp@ovn.org>
Sometimes code is much simpler if we can statically initialize data
structures. Until now, this has not been possible for cmap-based data
structures, so this commit introduces a CMAP_INITIALIZER macro.
This works by adding a singleton empty cmap_impl that simply forces the
first insertion into any cmap that points to it to allocate a real
cmap_impl. There could be some risk that rogue code modifies the
singleton, so for safety it is also marked 'const' to allow the linker to
put it into a read-only page.
This adds a new OVS_ALIGNED_VAR macro with GCC and MSVC implementations.
The latter is based on Microsoft webpages, so developers who know Windows
might want to scrutinize it.
As examples of the kind of simplification this can make possible, this
commit removes an initialization function from ofproto-dpif-rid.c and a
call to cmap_init() from tnl-neigh-cache.c. An upcoming commit will add
another user.
CC: Jarno Rajahalme <jarno@ovn.org>
CC: Gurucharan Shetty <guru@ovn.org>
Signed-off-by: Ben Pfaff <blp@ovn.org>
Acked-by: Ryan Moats <rmoats@us.ibm.com>
Currently the functions to set, clear, and iterate over bitmaps
only operate over 32 bit values. If we convert them to handle
64 bit bitmaps, they can be used in more places.
Suggested-by: Ben Pfaff <blp@nicira.com>
Signed-off-by: Jesse Gross <jesse@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>
I started working on a new command line utility that used this shared
code. I wanted the ability to pass some data from common
initialization code to all of the commands. You can find a similar
pattern in ovs-vsctl.
This patch updates the command handler to take a new struct,
ovs_cmdl_context, instead of argc and argv directly. It includes argc
and argv, but also includes an opaque type (void *), where the user of
this API can attach its custom data it wants passed along to command
handlers.
This patch affected the ovstest sub-programs, as well. The patch
includes a bit of an odd hack to OVSTEST_REGISTER() to avoid making
the main() function of the sub-programs take a ovs_cmdl_context.
The test main() functions still receive argc and argv directly, as
that seems more natural. The test-subprograms themselves are able to
make use of a context internally, though.
Signed-off-by: Russell Bryant <rbryant@redhat.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>
The coding style guidelines include the following:
- Pick a unique name prefix (ending with an underscore) for each
module, and apply that prefix to all of that module's externally
visible names. Names of macro parameters, struct and union members,
and parameters in function prototypes are not considered externally
visible for this purpose.
This patch adds the new prefix to the externally visible names. This
makes it a bit more obvious what code is coming from common command
line handling code.
Signed-off-by: Russell Bryant <rbryant@redhat.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>
./configure accepts --enable-ndebug option. Make ovs_assert() honor
it, and make sure all test programs disable it.
The order of include files in test programs is also made uniform:
1. #include <config.h>
2. #undef NDEBUG
3. Include file of the test subject (to make sure it itself has
sufficient include directives).
4. System includes in alphapetical order.
5. OVS includes in aplhapetical order.
Suggested-by: Ben Pfaff <blp@nicira.com>
Signed-off-by: Jarno Rajahalme <jrajahalme@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>
This commit adds a new variable in 'struct command' for
recording the command usage. Also, a new function is
added to print the usage given the array of defined
commands.
Later patch will use the output in bash command-line
completion script.
Signed-off-by: Alex Wang <alexw@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>
Batching the cmap find improves the memory behavior with large cmaps
and can make searches twice as fast:
$ tests/ovstest test-cmap benchmark 2000000 8 0.1 16
Benchmarking with n=2000000, 8 threads, 0.10% mutations, batch size 16:
cmap insert: 533 ms
cmap iterate: 57 ms
batch search: 146 ms
cmap destroy: 233 ms
cmap insert: 552 ms
cmap iterate: 56 ms
cmap search: 299 ms
cmap destroy: 229 ms
hmap insert: 222 ms
hmap iterate: 198 ms
hmap search: 2061 ms
hmap destroy: 209 ms
Batch size 1 has small performance penalty, but all other batch sizes
are faster than non-batched cmap_find(). The batch size 16 was
experimentally found better than 8 or 32, so now
classifier_lookup_miniflow_batch() performs the cmap find operations
in batches of 16.
Signed-off-by: Jarno Rajahalme <jrajahalme@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>
The test cases have been carefully crafted so that we do the same
amount of "overhead" operations in each case. Earlier, with no
mutations, the number of random number generations was different for
hmap and cmap test cases. hmap test was also missing an ignore() call.
Now the numbers look like this:
$ tests/ovstest test-cmap benchmark 2000000 8 0
Benchmarking with n=2000000, 8 threads, 0.00% mutations:
cmap insert: 597 ms
cmap iterate: 65 ms
cmap search: 299 ms
cmap destroy: 251 ms
hmap insert: 243 ms
hmap iterate: 201 ms
hmap search: 299 ms
hmap destroy: 202 ms
So it seems search on cmap can be as fast as on hmap in the
single-threaded case.
Signed-off-by: Jarno Rajahalme <jrajahalme@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>
cmap_next_position() didn't update the node pointer while iterating through a
list of nodes with the same hash.
This commit fixes the bug and improve test-cmap to detect it.
Signed-off-by: Daniele Di Proietto <ddiproietto@vmware.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>
This further eases porting existing hmap code to use cmap instead.
The iterator variants taking an explicit cursor are retained (renamed)
as they are needed when iteration is to be continued from the last
iterated node.
Signed-off-by: Jarno Rajahalme <jrajahalme@nicira.com>
Add cmap_replace() and cmap_first(), as well as CMAP_FOR_EACH_SAFE and
CMAP_FOR_EACH_CONTINUE to make porting existing hmap using code a bit
easier.
CMAP_FOR_EACH_SAFE is useful in RCU postponed destructors, when it is
known that additional postponing is not needed.
Signed-off-by: Jarno Rajahalme <jrajahalme@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>
This implements an "optimistic concurrent cuckoo hash", a single-writer,
multiple-reader hash table data structure. The point of this data
structure is performance, so this commit message focuses on performance.
I tested the performance of cmap with the test-cmap utility included in
this commit. It takes three parameters for benchmarking:
- n, the number of elements to insert.
- n_threads, the number of threads to use for searching and
mutating the hash table.
- mutations, the percentage of operations that should modify the
hash table, from 0% to 100%.
e.g. "test-cmap 1000000 16 1" inserts one million elements, uses 16
threads, and 1% of the operations modify the hash table.
Any given run does the following for both hmap and cmap
implementations:
- Inserts n elements into a hash table.
- Iterates over all of the elements.
- Spawns n_threads threads, each of which searches for each of the
elements in the hash table, once, and removes the specified
percentage of them.
- Removes each of the (remaining) elements and destroys the hash
table.
and reports the time taken by each step,
The tables below report results for various parameters with a draft version
of this library. The tests were not formally rerun for the final version,
but the intermediate changes should only have improved performance, and
this seemed to be the case in some informal testing.
n_threads=16 was used each time, on a 16-core x86-64 machine. The compiler
used was Clang 3.5. (GCC yields different numbers but similar relative
results.)
The results show:
- Insertion is generally 3x to 5x faster in an hmap.
- Iteration is generally about 3x faster in a cmap.
- Search and mutation is 4x faster with .1% mutations and the
advantage grows as the fraction of mutations grows. This is
because a cmap does not require locking for read operations,
even in the presence of a writer.
With no mutations, however, no locking is required in the hmap
case, and the hmap is somewhat faster. This is because raw hmap
search is somewhat simpler and faster than raw cmap search.
- Destruction is faster, usually by less than 2x, in an hmap.
n=10,000,000:
.1% mutations 1% mutations 10% mutations no mutations
cmap hmap cmap hmap cmap hmap cmap hmap
insert: 6132 2182 6136 2178 6111 2174 6124 2180
iterate: 370 1203 378 1201 370 1200 371 1202
search: 1375 8692 2393 28197 18402 80379 1281 1097
destroy: 1382 1187 1197 1034 324 241 1405 1205
n=1,000,000:
.1% mutations 1% mutations 10% mutations no mutations
cmap hmap cmap hmap cmap hmap cmap hmap
insert: 311 25 310 60 311 59 310 60
iterate: 25 62 25 64 25 57 25 60
search: 115 637 197 2266 1803 7284 101 67
destroy: 103 64 90 59 25 13 104 66
n=100,000:
.1% mutations 1% mutations 10% mutations no mutations
cmap hmap cmap hmap cmap hmap cmap hmap
insert: 25 6 26 5 25 5 25 5
iterate: 1 3 1 3 1 3 2 3
search: 12 57 27 219 164 735 10 5
destroy: 5 3 6 3 2 1 6 4
Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Jarno Rajahalme <jrajahalme@nicira.com>
