[ovs-git] Open vSwitch: Introduce sparse flows and masks, to reduce memory usage and improve speed. (master)
dev at openvswitch.org
dev at openvswitch.org
Tue Sep 4 19:51:21 UTC 2012
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "Open vSwitch".
The branch, master has been updated
via 5cb7a798405c6ccc07bf9a932b709643c072b086 (commit)
via 9879b94f4381a342c66489dae3b4d4150d0dce6b (commit)
via 0ee140fb69ec924fe5280c1ceaa82c7a3d8f4223 (commit)
via 3ca1de08b4d0374e4b9389d98351b2b0192c8189 (commit)
via 48d28ac16112f72ef0985ec2d013425202af8f5c (commit)
via 81a76618be9ea195a1e4a881ba9591728891d10b (commit)
via dbda2960f64238e80570aafeae7af5a752f54f59 (commit)
via a656cb7736fd9f5926c2b1bdd6f50dafc3aa796a (commit)
via 8472a3cecc6c370e227dd477470e4a8cf760ddb5 (commit)
via 659c23467978f40200686695c48b09582f2c534b (commit)
via e7b4ef5eacebe5d5cae85c0076960f276b16554c (commit)
via 26720e2449918b92be1fd0e3a7c57012c057c733 (commit)
via 16c6d0c38406d860027c12d7da5138f35f6264b5 (commit)
via 51c14ddd8df9617e641748a98ac52b78fd19290a (commit)
via 0bdc4bec4fd00e8140c16915e2aa817a18ea166d (commit)
via e2170cffc1e736db85b461b9bff2afa74ba180f2 (commit)
via 851d3105c7a4166d0cd05f3f9198edea2623bcd7 (commit)
via 3840c40624f366f560af6165c7e36ec13fc3a51b (commit)
via 5d9499c4dc43bb40f49bf7a819821750a43039d2 (commit)
via 27cafc5fc0869236b8cd696eef535eca879a0949 (commit)
via 548de4ddb3efed9b7e5e543fec636ae5f077eda7 (commit)
via 9185896026dc384f39e9bce79a05b736e4cc4ba4 (commit)
from 43924b126d7a962889a755c0dddcce631d6ebda9 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit 5cb7a798405c6ccc07bf9a932b709643c072b086
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=5cb7a798405c6ccc07bf9a932b709643c072b086
Author: Ben Pfaff <blp at nicira.com>
Introduce sparse flows and masks, to reduce memory usage and improve speed.
A cls_rule is 324 bytes on i386 now. The cost of a flow table lookup is
currently proportional to this size, which is going to continue to grow.
However, the required cost of a flow table lookup, with the classifier that
we currently use, is only proportional to the number of bits that a rule
actually matches. This commit implements that optimization by replacing
the match inside "struct cls_rule" by a sparse representation.
This reduces struct cls_rule to 100 bytes on i386.
There is still some headroom for further optimization following this
commit:
- I suspect that adding an 'n' member to struct miniflow would make
miniflow operations faster, since popcount() has some cost.
- It's probably possible to replace the "struct minimatch" in cls_rule
by just a "struct miniflow", since the cls_rule's cls_table has a
copy of the minimask.
- Some of the miniflow operations aren't well-optimized.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 9879b94f4381a342c66489dae3b4d4150d0dce6b
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=9879b94f4381a342c66489dae3b4d4150d0dce6b
Author: Ben Pfaff <blp at nicira.com>
hash: Introduce an implementation of murmurhash.
Murmurhash is generally superior to the Jenkins lookup3 hash according to
the available figures. Perhaps we should generally replace our current
hashes by murmurhash.
For now, I'm introducing a parallel implementation to allow it to be used
in cases where an incremental one-word-at-a-time hash is desirable. The
first user will be added in an upcoming commit.
Signed-off-by: Ben Pfaff <blp at nicira.com>
Acked-by: Ethan Jackson <ethan at nicira.com>
commit 0ee140fb69ec924fe5280c1ceaa82c7a3d8f4223
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=0ee140fb69ec924fe5280c1ceaa82c7a3d8f4223
Author: Ben Pfaff <blp at nicira.com>
util: New function raw_ctz().
This will acquire a user in an upcoming commit.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 3ca1de08b4d0374e4b9389d98351b2b0192c8189
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=3ca1de08b4d0374e4b9389d98351b2b0192c8189
Author: Ben Pfaff <blp at nicira.com>
classifier: Optimize iteration with a catch-all target rule.
When cls_cursor_init() is given a NULL target, it can skip an expensive
step comparing the rule against the target for every table and every rule
in the classifier. collect_rule_loose() and other callers could take
advantage of this optimization, except that they actually pass in a rule
that matches everything instead of a NULL rule (e.g. for "ovs-ofctl
dump-flows <bridge>" without specifying a matching rule).
This optimizes that case.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 48d28ac16112f72ef0985ec2d013425202af8f5c
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=48d28ac16112f72ef0985ec2d013425202af8f5c
Author: Ben Pfaff <blp at nicira.com>
classifier: Prepare for "struct cls_rule" needing to be destroyed.
Until now, "struct cls_rule" didn't own any data outside its own memory
block. An upcoming commit will make "struct cls_rule" sometimes own blocks
of memory, so it needs "destroy" and to a lesser extent "clone" functions.
This commit adds these in advance, even though they are mostly no-ops, to
make it possible to separately review the memory management.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 81a76618be9ea195a1e4a881ba9591728891d10b
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=81a76618be9ea195a1e4a881ba9591728891d10b
Author: Ben Pfaff <blp at nicira.com>
classifier: Break cls_rule 'flow' and 'wc' members into new "struct match".
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit dbda2960f64238e80570aafeae7af5a752f54f59
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=dbda2960f64238e80570aafeae7af5a752f54f59
Author: Ben Pfaff <blp at nicira.com>
classifier: Fix typo in comment.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit a656cb7736fd9f5926c2b1bdd6f50dafc3aa796a
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=a656cb7736fd9f5926c2b1bdd6f50dafc3aa796a
Author: Ben Pfaff <blp at nicira.com>
util: New function popcount().
This is the fastest portable implementation among the ones below, as
measured with GCC 4.4 on a Xeon X3430. The measeured times were, in
seconds:
popcount1 25.6
popcount2 6.9 (but is not portable)
popcount3 31.4
popcount4 25.6
popcount5 61.6 (and is buggy)
popcount6 64.6
popcount7 32.3
popcount8 11.2
int
popcount1(unsigned int x)
{
return __builtin_popcount(x);
}
int
popcount2(unsigned int x)
{
unsigned int y;
asm("popcnt %1, %0" : "=r" (y) : "g" (x));
return y;
}
int
popcount3(unsigned int x)
{
unsigned int n;
n = (x >> 1) & 033333333333;
x -= n;
n = (n >> 1) & 033333333333;
x -= n;
x = (x + (x >> 3)) & 030707070707;
return x % 63;
}
int
popcount4(unsigned int x)
{
x -= (x >> 1) & 0x55555555;
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0f0f0f0f;
x += x >> 8;
x += x >> 16;
return x & 0x3f;
}
int
popcount5(unsigned int x)
{
int n;
n = 0;
while (x) {
if (x & 0xf) {
n += ((0xe9949440 >> (x & 0xf)) & 3) + 1;
}
x >>= 4;
}
return n;
}
int
popcount6(unsigned int x)
{
int n;
n = 0;
while (x) {
n += (0xe994 >> (x & 7)) & 3;
x >>= 3;
}
return n;
}
int
popcount7(unsigned int x)
{
static const int table[16] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};
return (table[x & 0xf]
+ table[(x >> 4) & 0xf]
+ table[(x >> 8) & 0xf]
+ table[(x >> 12) & 0xf]
+ table[(x >> 16) & 0xf]
+ table[(x >> 20) & 0xf]
+ table[(x >> 24) & 0xf]
+ table[x >> 28]);
}
static int
popcount8(unsigned int x)
{
((((X) & (1 << 0)) != 0) + \
(((X) & (1 << 1)) != 0) + \
(((X) & (1 << 2)) != 0) + \
(((X) & (1 << 3)) != 0) + \
(((X) & (1 << 4)) != 0) + \
(((X) & (1 << 5)) != 0) + \
(((X) & (1 << 6)) != 0) + \
(((X) & (1 << 7)) != 0))
static const uint8_t popcount8[256] = {
INIT64(0), INIT64(64), INIT64(128), INIT64(192)
};
return (popcount8[x & 0xff] +
popcount8[(x >> 8) & 0xff] +
popcount8[(x >> 16) & 0xff] +
popcount8[x >> 24]);
}
int
main(void)
{
unsigned long long int x;
int n;
n = 0;
for (x = 0; x <= UINT32_MAX; x++) {
n += popcount8(x);
}
printf("%d\n", n);
return 0;
}
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 8472a3cecc6c370e227dd477470e4a8cf760ddb5
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=8472a3cecc6c370e227dd477470e4a8cf760ddb5
Author: Ben Pfaff <blp at nicira.com>
util: New function zero_rightmost_1bit().
It's probably easier to understand
x = zero_rightmost_1bit(x);
than
x &= x - 1;
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 659c23467978f40200686695c48b09582f2c534b
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=659c23467978f40200686695c48b09582f2c534b
Author: Ben Pfaff <blp at nicira.com>
flow: Simplify many functions for working with flows and wildcards.
Now that "struct flow" and "struct flow_wildcards" have the same simple
and uniform structure, it's easy to handle common operations by just
iterating over the bits inside them.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit e7b4ef5eacebe5d5cae85c0076960f276b16554c
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=e7b4ef5eacebe5d5cae85c0076960f276b16554c
Author: Ben Pfaff <blp at nicira.com>
flow: Remove flow_wildcards_is_exact().
It's only used in a not-very-useful assertion in some test code. In
general, exact-match flows make very little sense anymore, and they're
basically on their way out.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 26720e2449918b92be1fd0e3a7c57012c057c733
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=26720e2449918b92be1fd0e3a7c57012c057c733
Author: Ben Pfaff <blp at nicira.com>
flow: Replace flow_wildcards members by a single "struct flow".
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 16c6d0c38406d860027c12d7da5138f35f6264b5
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=16c6d0c38406d860027c12d7da5138f35f6264b5
Author: Ben Pfaff <blp at nicira.com>
flow: Take advantage of zero-padding in struct flow and flow_wildcards.
Since we know these bytes are always 0 in both structures, we can use
faster functions that only work with full words.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 51c14ddd8df9617e641748a98ac52b78fd19290a
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=51c14ddd8df9617e641748a98ac52b78fd19290a
Author: Ben Pfaff <blp at nicira.com>
flow: Ensure that padding is always zeroed.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 0bdc4bec4fd00e8140c16915e2aa817a18ea166d
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=0bdc4bec4fd00e8140c16915e2aa817a18ea166d
Author: Ben Pfaff <blp at nicira.com>
flow: Use bit-mask for in_port match, instead of FWW_* flag.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit e2170cffc1e736db85b461b9bff2afa74ba180f2
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=e2170cffc1e736db85b461b9bff2afa74ba180f2
Author: Ben Pfaff <blp at nicira.com>
flow: Use bit-mask for Ethernet type match, instead of FWW_* flag.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 851d3105c7a4166d0cd05f3f9198edea2623bcd7
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=851d3105c7a4166d0cd05f3f9198edea2623bcd7
Author: Ben Pfaff <blp at nicira.com>
flow: Use bit-mask for IP protocol match, instead of FWW_* flag.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 3840c40624f366f560af6165c7e36ec13fc3a51b
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=3840c40624f366f560af6165c7e36ec13fc3a51b
Author: Ben Pfaff <blp at nicira.com>
flow: Use bit-mask for TTL match, instead of FWW_* flag.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 5d9499c4dc43bb40f49bf7a819821750a43039d2
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=5d9499c4dc43bb40f49bf7a819821750a43039d2
Author: Ben Pfaff <blp at nicira.com>
flow: Use bit-mask for DSCP and ECN bits, instead of FWW_* flags.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 27cafc5fc0869236b8cd696eef535eca879a0949
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=27cafc5fc0869236b8cd696eef535eca879a0949
Author: Ben Pfaff <blp at nicira.com>
flow: Fully separate FWW_* from OFPFW10_*.
It might have been a useful optimization at one point to have FWW_*
correspond in OFPFW10_* where possible, but it doesn't seem worthwhile for
only 3 corresponding values. It also makes the code somewhat more
confusing.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 548de4ddb3efed9b7e5e543fec636ae5f077eda7
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=548de4ddb3efed9b7e5e543fec636ae5f077eda7
Author: Ben Pfaff <blp at nicira.com>
ofproto: Move ofpacts_check() calls from ofproto-dpif to ofproto.
Signed-off-by: Ben Pfaff <blp at nicira.com>
commit 9185896026dc384f39e9bce79a05b736e4cc4ba4
Diffs: http://openvswitch.org/cgi-bin/gitweb.cgi?p=openvswitch;a=commitdiff;h=9185896026dc384f39e9bce79a05b736e4cc4ba4
Author: Ben Pfaff <blp at nicira.com>
ofproto: Move 'max_ports' from ofproto-dpif.c to ofproto.c.
This allows port numbers in actions and elsewhere in OpenFlow messages to
be checked at a higher level.
Signed-off-by: Ben Pfaff <blp at nicira.com>
-----------------------------------------------------------------------
Summary of changes:
lib/automake.mk | 2 +
lib/classifier.c | 948 +++++---------------------------------------
lib/classifier.h | 112 +-----
lib/flow.c | 723 +++++++++++++++++++++------------
lib/flow.h | 179 ++++++---
lib/hash.c | 15 +
lib/hash.h | 42 ++
lib/learn.c | 32 +-
lib/learning-switch.c | 5 +-
lib/match.c | 849 +++++++++++++++++++++++++++++++++++++++
lib/match.h | 140 +++++++
lib/meta-flow.c | 470 +++++++++++-----------
lib/meta-flow.h | 15 +-
lib/nx-match.c | 189 ++++-----
lib/nx-match.h | 19 +-
lib/ofp-parse.c | 33 +-
lib/ofp-print.c | 24 +-
lib/ofp-util.c | 658 +++++++++++++++----------------
lib/ofp-util.h | 43 +-
lib/util.c | 74 +++-
lib/util.h | 35 ++-
ofproto/connmgr.c | 12 +-
ofproto/connmgr.h | 3 +-
ofproto/fail-open.c | 13 +-
ofproto/in-band.c | 134 ++++---
ofproto/ofproto-dpif.c | 110 +++---
ofproto/ofproto-provider.h | 63 ++--
ofproto/ofproto.c | 169 ++++++---
tests/classifier.at | 10 +
tests/library.at | 2 +
tests/ofp-print.at | 8 +-
tests/test-bundle.c | 1 +
tests/test-classifier.c | 511 ++++++++++++++++++++----
tests/test-flows.c | 8 +-
tests/test-hash.c | 62 ++--
tests/test-multipath.c | 1 +
tests/test-util.c | 57 +++
utilities/ovs-ofctl.c | 153 ++++----
38 files changed, 3477 insertions(+), 2447 deletions(-)
create mode 100644 lib/match.c
create mode 100644 lib/match.h
hooks/post-receive
--
Open vSwitch
More information about the git
mailing list