Deprecate referring to ports by name in ovs-ofctl.

This is a necessary step toward supporting full 32-bit OF1.1+ port numbers
in a later version of OVS.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

ofp-actions: Add support for OpenFlow 1.2 "set-field" action.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Simon Horman <horms@verge.net.au>
[blp@nicira.com extracted this code from a larger patch by above, so:]
Signed-off-by: Ben Pfaff <blp@nicira.com>
[regarding final version of patch:]
Reviewed-by: Simon Horman <horms@verge.net.au>

ofp-actions: Allow OF1.1+ actions to be variable-length.

Previously there was no need for this, because all implemented standard
OpenFlow actions had a fixed length, but the OF1.2 "set-field" action (soon
to be implemented) is variable length.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Reviewed-by: Simon Horman <horms@verge.net.au>

ofp-actions: Prepare to treat OF1.2 actions as OF1.1 actions.

The numbering of OpenFlow 1.0 actions overlaps with the numbering
of OpenFlow 1.1+ actions, so the two sets of actions have to be
distinguished for input and output.  But OpenFlow 1.1 and 1.2
actions are numbered to avoid this problem, so there is no need
to distinguish them in the same way.  Therefore, this commit
prepares to treat them together.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Reviewed-by: Simon Horman <horms@verge.net.au>

openflow-1.2: Remove OFPAT12_* definitions that duplicate OFPAT11_* ones.

OpenFlow 1.1 and 1.2 action numbering is compatible, in that no
OpenFlow 1.2 action uses an OpenFlow 1.1 action number in a different
way from OpenFlow 1.1.  So it's confusing and unnecessary to have
separate definitions for these numbers.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Reviewed-by: Simon Horman <horms@verge.net.au>

packets: Add ECN constants.

Upcoming tunnel code will be able to handle ECN encapsulation/
decapsulation in userspace.  This adds the necessary constants for ECN
manipulation.

Signed-off-by: Jesse Gross <jesse@nicira.com>
Acked-by: Kyle Mestery <kmestery@cisco.com>

netdev-vport: Fix ToS/TTL mixup in unparsing.

When unparsing the kernel tunnel configuration, TTL was incorrectly
converted to "tos".  Although it leads to confusing configuration
output, actual operation is not affected.

Signed-off-by: Jesse Gross <jesse@nicira.com>
Acked-by: Kyle Mestery <kmestery@cisco.com>

ovsdb-server: Add support for multiple databases.

The OVSDB protocol has supported multiple databases for a long time, but
the ovsdb-server implementation only supported one database at a time.
This commit adds support for multiple databases.

Feature #12353.
Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

ovsdb-server: Add --enable-dummy option for unit tests.

This will allow an upcoming unit test to use the "time/warp" ovs-appctl
command with ovsdb-server.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

ovsdb-server: Fix null pointer deref when bool "is_connected" is empty.

The ovsdb-server supports obtaining its remote connection targets from a
database table and updating that table with connection status information.
One of the supported connection status columns is a boolean column named
"is_connected".  The code in ovsdb-server blindly assigned a bool into
this column without checking that it actually had space allocated for one.
This was and is fine with the ovs-vswitchd schema, which always has exactly
one value in this column.  However, if a database schema makes this column
optional, and there are actually no values in it, then this assignment
dereferences a null pointer.

This commit fixes the problem by allocating space for a bool if none has
yet been allocated.

Noticed while adding an extra test for the connection status feature.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

ovsdb-client: Make "list-dbs" print the list of databases in sorted order.

This makes the command's behavior more predictable when there is more than
one database.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

ovsdb-client: Use svec instead of sset for list of database.

This will make it easier to print a list of databases in sorted order,
which will happen in a followup commit.

This commit should have no effect on visible OVS behavior.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

ovs-lib: Move DAEMON_CWD initialization to top of file.

All the other variables are initialized at the top and I don't see a reason
that this variable is special.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

ovsdb-tool: Fix indentation in manpage.

This paragraph is about show-log so it should be indented the same as the
other paragraph about show-log.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

unixctl: Fix comment on unixctl_command_register().

The arguments to the callback were changed some time ago but the comment
still described the older form.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

flow: Only show IPv4 flow information for IPv4 flows

Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofproto: Fix uninitialized field in ofputil_flow_update.

Two instances of ofputil_flow_update had the priority field uninitialized.
This would cause flow updates to contain undefined priority values.

This bug was introduced by commit 81a76618 (classifier: Break cls_rule
'flow' and 'wc' members into new "struct match".)

Signed-off-by: Anupam Chanda <achanda@nicira.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>

bridge: Omit alerts on the cfm_remote_opstate column.

This column should be write only, otherwise every call to update it
has to make a trip to the database.  Since this column is updated
every time through the run loop as part of refresh_instant_stats(),
this patch fixes a significant performance degradation.

Signed-off-by: Ethan Jackson <ethan@nicira.com>

ovs-ofctl: Accept port keywords, OF1.1 port numbers, reject port number 0.

OpenFlow 1.0 has special reserved ports in the range 0xfff8 to 0xffff.
OpenFlow 1.1 and later has the same ports in the range 0xfffffff8 to
0xffffffff and allows the OF1.0 range to be used for ordinary ("physical")
switch ports.  This means that, naively, the meaning of a port number in
the range 0xfff8 to 0xffff given on the ovs-ofctl command line depends on
the protocol in use.  This commit implements something a little smarter:

    - Accept keyword names (e.g. LOCAL) for special reserved ports
      everywhere that such a port can plausibly be used (previously they
      were only accepted in some places).

    - Translate 0xfff8...0xffff to 0xfffffff8...0xffffffff for now, since
      OF1.1+ isn't in widespread use and those particular ports aren't
      likely to be in use in OF1.1+ anyway.

    - Log warnings about those ports when they are specified by number, to
      allow users to fix their invocations.

Also:

    - Accept the OF1.1+ port numbers for these ports, without warning, for
      compatibility with the upcoming OF1.1+ support.

    - Stop accepting port number 0, which has never been a valid port
      number in OpenFlow 1.0 and later.  (This required fixing some tests
      that inadvertently used this port number).

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Simon Horman <horms@verge.net.au>

ofp-actions: Improve explanation of 'compat' member in struct ofpact.

Suggested-by: Justin Pettit <jpettit@nicira.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>

datapath: Remove unecessary semicolon

Found by http://coccinelle.lip6.fr/

Signed-off-by: Peter Senna Tschudin <peter.senna@gmail.com>
Signed-off-by: Jesse Gross <jesse@nicira.com>

jsonrpc: Fix Python implementation of inactivity logic.

When a JSON-RPC session receives bytes, or when it successfully sends
queued bytes, then it should count that as activity.  However, the code
here was reversed, in that it used the wrong check in each place.  That is,
when it tried to receive data, it would check whether data had just been
sent, and when it tried to send data, it would check whether data had just
been received.  Neither one makes sense and doesn't work.

Bug #13214.
Reported-by: Luca Giraudo <lgiraudo@nicira.com>
CC: James Schmidt <jschmidt@nicira.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>

FAQ: Describe difference between ovs-dpctl and ovs-ofctl "dump-flows".

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Kyle Mestery <kmestery@cisco.com>

datapath: Add version info for out-of-tree modules.

The upstream version of the module always has the version of the running kernel
but for out-of-tree modules it can be difficult to tell the current version.
This adds the information to the module where it can be read using modinfo for
the on-disk version or from /sys/module/openvswitch/version for the currently
loaded module.

Suggested-by: Duffie Cooley <dcooley@nicira.com>
Signed-off-by: Jesse Gross <jesse@nicira.com>
Acked-by: Kyle Mestery <kmestery@cisco.com>

stream-unix: Reduce connection failure log level from ERR to WARN.

Sometimes this just means that the daemon we're connecting to is
restarting.

Bug #13177.
Reported-by: Scott Hendricks <shendricks@nicira.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>

tests: Fix sensitivity to record ordering in test-netflow output.

The order of records in a NetFlow message is essentially random, but the
test case was picky about it.  I started getting failures when I modified
apparently unrelated code, so here's a fix.

Signed-off-by: Ben Pfaff <blp@nicira.com>

ovs-ofctl: Fix indentation in manpage.

This .RE (to reduce the current indentation level) needs to go after all
the actions, but it was mistakenly put before the fin_timeout action.

Reported-by: Paul Ingram <paul@nicira.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofp-actions: helper functions for of12 set-field action

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofp-util: Allow decoding of Open Flow 1.1 & 1.2 Table Statistics Request Messages

Signed-off-by: Simon Horman <horms@verge.net.au>
[blp@nicira.com then made substantial changes that were then:]
Reviewed-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

python/ovs/db/idl.py: Transaction._substitute doesn't handle list/tuple

Since Transaction._substitute doesn't substitute elements of list/tuple,
setting list references results in transaction error. Teach it such case.

Example:
{"op": "update",
 "row":{"bridges":["set",[["uuid",
                           "1f42bc19-307f-42e7-a9c0-c12178bd8b51"],
                          ["uuid",
                           "f97e0c76-7146-489d-9bed-29bc704f65fe"]]]},
 "table": "Open_vSwitch",
 "where":[["_uuid", "==", ["uuid",
                           "20c2a046-ae7e-4453-a576-11034db24985"]]]}

In the above case, uuid in "row" aren't replaced by "named-uuid" because
the function doesn't look into elements of lists.
When list/tuple is found, look into elements recursively.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofp-actions: Right-justify the value in ofpact_reg_load 'subvalue' member.

This is what I intended when I suggested using mf_subvalue, but I didn't
notice the difference until after applying the patch.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Simon Horman <horms@verge.net.au>

python/ovs/db/idl: make SchemaHelper accept schema in json form

This is needed when using schema that was retrieved from ovsdb by get_schema
method.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Ben Pfaff <blp@nicira.com>

python/ovs/db/idl: add counterpart of ovsdb_idl_add_table()

Add register_table method to SchemaHelper as Python counterpart of
ovsdb_idl_add_table() in the C version of the IDL.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Ben Pfaff <blp@nicira.com>

python/ovs: socket_util uses select.poll

The changeset of ed815d9bd28422a490fe370d7804d24bcd676806 eliminated
the use of select.poll for eventlet/gevent.
It forgot to select.poll in socket_util.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Ben Pfaff <blp@nicira.com>

lib/ofp-actions: use mf_subvalue in struct ofpact_reg_load.

Use a uninion mf_subvalue instead of a uint64_t for
the value member of struct ofpact_reg_load.

set_field action needs to hold values wider than 64 bits.
This is preparation for set_field action.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

INSTALL: Recommend installing kernel modules with "make modules_install".

Reported-by: Valentin Bud <valentin@hackaserver.com>
Acked-by: Kyle Mestery <kmestery@cisco.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>

jsonrpc: Treat receiving part of a message as activity.

Until now, the jsonrpc code has only counted receiving a full JSON-RPC
messages as activity.  This could theoretically time out, then, while a
very long message is in transit or if a slow link is involved.  This commit
changes this code to count receiving any part of a message as activity.

This isn't a problem for OpenFlow connections because OpenFlow messages are
at most 64 kB in size.

This problem hasn't actually been observed in practice.

Bug #12789.
Signed-off-by: Ben Pfaff <blp@nicira.com>

jsonrpc: Treat draining data from send queue as activity.

Until now, the jsonrpc module has used messages received from the
remote peer as the sole means to determine that the JSON-RPC
connection is up.  This could in theory interact badly with a
remote peer that stops reading and processing messages from the
receive queue when there is a backlog in the send queue for a
given connection (ovsdb-server is an example of a program that
behaves this way).  This commit fixes the problem by expanding
the definition of "activity" to include successfully sending
JSON-RPC data that was previously queued.

The above change is exactly analogous to the similar change
made to the rconn library in commit 133f2dc95454 (rconn: Treat
draining a message from the send queue as activity.).

Bug #12789.
Signed-off-by: Ben Pfaff <blp@nicira.com>

reconnect: Rename reconnect_received() to reconnect_activity().

Receiving data is not the only reasonable way to verify that a connection
is up.  For example, on a TCP connection, receiving an acknowledgment that
the remote side has accepted data that we sent is also a reasonable means.
Therefore, this commit generalizes the naming.

Also, similarly for the Python implementation: Reconnect.received() becomes
Reconnect.activity().

Signed-off-by: Ben Pfaff <blp@nicira.com>

third-party: Fix tcpdump patch

Other parts of OVS have moved on since the tcpdump patch was created. This
commit brings the patch up to date and will compile cleanly against
tcpdump-4.3.0.

Signed-off-by: Joe Stringer <joe@wand.net.nz>
Signed-off-by: Justin Pettit <jpettit@nicira.com>

dpif-linux: Report packet loss as WARN instead of ERR.

Packet loss is recoverable so it doesn't warrant an ERR.

Bug #12920.
Reported-by: Scott Hendricks <shendricks@nicira.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ovsdb: Enforce immutability of immutable columns.

OVSDB has always had the ability to mark a column as "immutable", so that
its value cannot be changed in a given row after that row is initially
inserted.  However, we discovered recently that ovsdb-server has never
enforced this constraint.  This commit implements enforcement.

Reported-by: Paul Ingram <paul@nicira.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Kyle Mestery <kmestery@cisco.com>

ofp-errors: Use OFPERR_OFPBRC_BAD_TABLE_ID

* In the case of OpenFlow 1.1+ OFPERR_OFPBRC_BAD_TABLE_ID is defined
  in the specification and seems to be the most appropriate error
  to use when an unknown table id is encountered.

* In the case of OpenFlow 1.0 no appropriate error message
  seems to exist. Perhaps because an invalid port is not possible?
  I'm unsure.

  In any case, make use of a non-standard error code (1,512).
  This was formerly known as OFPERR_NXBRC_BAD_TABLE_ID but
  has been rolled into OFPERR_OFPBRC_BAD_TABLE_ID to allow the
  latter to be used without concern for the prevailing Open Flow version.

Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofp-errors: Use OFPERR_OFPBRC_BAD_PORT

* In the case of OpenFlow 1.2+ OFPERR_OFPBRC_BAD_PORT is defined
  in the specification and seems to be the most appropriate error
  to use when an invalid port is encountered in a Packet Out request.

* In the case of OpenFlow 1.0 and 1.1 no appropriate error message
  seems to exist. Perhaps because an invalid port is not possible?
  I'm unsure.

  In any case, make use of a non-standard error code (1,514).
  This was formerly known as OFPERR_NXBRC_BAD_IN_PORT but
  has been rolled into OFPERR_NXBRC_BAD_IN_PORT to allow the
  latter to be used without concern for the prevailing Open Flow version.

Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

extract-ofp-errors: Check that error codes are in the expected ranges.

All real OpenFlow error codes are small numbers, and for Nicira extensions
we've intentionally chosen large numbers.  This commit adds a check that
standard and extension codes are properly designated in the ofp-errors.h
header.

Signed-off-by: Ben Pfaff <blp@nicira.com>

ofp-errors: Ignore text enclosed in square brackets

Enhance to extract-ofp-errors to omit text enclosed in square brackets from
error description. This allows some commentary other than
the error description to be supplied in ofp-errors.h

As suggested by Ben Pfaff <blp@nicira.com>

Signed-off-by: Simon Horman <horms@verge.net.au>
[blp@nicira.com added the large comment on enum ofperr.]
Signed-off-by: Ben Pfaff <blp@nicira.com>

python/ovs/poller: use select.select instead of select.poll.

eventlet/gevent doesn't work well with select.poll because select.poll blocks
python interpreter as a whole instead of switching from the current thread
which is about to block to other runnable thread.
So ovsdb python binding can't be used with eventlet/gevent.
Emulate select.poll with select.select because using python means that
performance isn't so important.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Ben Pfaff <blp@nicira.com>

lib/ofp-util: preparation for OF12 of ofp-util

Add necessary macros to ofp-util for OF12 support.
This is just a placeholder.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofp-errors: Use standardised code for OFPERR_OFPBMC_BAD_VALUE

Use standardised code for Open Flow 1.1 OFPERR_OFPBMC_BAD_VALUE

OFPERR_OFPBMC_BAD_VALUE is defined in Open Flow 1.1 as (4,7),
so use that code instead of a non-standard one.

Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofp-errors: Remove OFPERR_NXFMFC_GROUPS_NOT_SUPPORTED

OFPERR_NXFMFC_GROUPS_NOT_SUPPORTED is currently only used in paths which
are part of a non-NX extension portions of the Open Flow 1.1+
implementation.

After recent discussion it has been decided to attempt to only use
standardised, albeit lest-specify, errors unless errors arise from use of
an NX extension.

With the above in mind it seems appropriate to:
* Use OFPERR_OFPFMFC_UNKNOWN in place of OFPERR_NXFMFC_GROUPS_NOT_SUPPORTED.
* Remove OFPERR_NXFMFC_GROUPS_NOT_SUPPORTED as it is no longer used.

An unfortunate side-effect of this change is that the error for
the case in question is now less-specific.

Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofp-errors: Remove OFPERR_NXBIC_DUP_TYPE

OFPERR_NXBIC_DUP_TYPE is currently only used in
decode_openflow11_instructions() which is part of a non-NX extension
portion of the Open Flow 1.1+ implementation.

After recent discussion it has been decided to attempt to only use
standardised, albeit less-specific, errors unless errors arise from use of
an NX extension.

With the above in mind it seems appropriate to:
* Use OFPERR_OFPIT_BAD_INSTRUCTION in place of OFPERR_NXBIC_DUP_TYPE.
* Remove OFPERR_NXBIC_DUP_TYPE as it is no longer used.

An unfortunate side-effect of this change is that the error for
the case in question is now less-specific.

Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@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@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@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

util: New function raw_ctz().

This will acquire a user in an upcoming commit.

Signed-off-by: Ben Pfaff <blp@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@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@nicira.com>

classifier: Break cls_rule 'flow' and 'wc' members into new "struct match".

Signed-off-by: Ben Pfaff <blp@nicira.com>

classifier: Fix typo in comment.

Signed-off-by: Ben Pfaff <blp@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@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@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@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@nicira.com>

flow: Replace flow_wildcards members by a single "struct flow".

Signed-off-by: Ben Pfaff <blp@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@nicira.com>

flow: Ensure that padding is always zeroed.

Signed-off-by: Ben Pfaff <blp@nicira.com>

flow: Use bit-mask for in_port match, instead of FWW_* flag.

Signed-off-by: Ben Pfaff <blp@nicira.com>

flow: Use bit-mask for Ethernet type match, instead of FWW_* flag.

Signed-off-by: Ben Pfaff <blp@nicira.com>

flow: Use bit-mask for IP protocol match, instead of FWW_* flag.

Signed-off-by: Ben Pfaff <blp@nicira.com>

flow: Use bit-mask for TTL match, instead of FWW_* flag.

Signed-off-by: Ben Pfaff <blp@nicira.com>

flow: Use bit-mask for DSCP and ECN bits, instead of FWW_* flags.

Signed-off-by: Ben Pfaff <blp@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@nicira.com>

ofproto: Move ofpacts_check() calls from ofproto-dpif to ofproto.

Signed-off-by: Ben Pfaff <blp@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@nicira.com>

datapath: Drop comment describing vport node.

Commit f36ff26ac08bcba28b5befba7b1dcff9b963769d (datapath: Remove
vport list node.) removed an unused list node in struct vport but
did not remove the comment describing it.  This does that.

Signed-off-by: Jesse Gross <jesse@nicira.com>

datapath: Fix FLOW_BUFSIZE definition.

This is analogous to the change made in userspace with
2508ac16defd417b94fb69689b6b1da4fbc76282 (odp-util: Update
ODPUTIL_FLOW_KEY_BYTES for current kernel flow format.).  The extra
space for vlan encapsulation was not included in the allocation for
maximum length flows.

Found by code inspection and to my knowledge has never been hit, likely
because skb allocations are padded out to a cacheline, making userspace
more susceptible to this problem than the kernel.  In theory, however,
the right combination of flow and packet size could result in a kernel
panic.

Signed-off-by: Jesse Gross <jesse@nicira.com>
Acked-by: Kyle Mestery <kmestery@cisco.com>

datapath: Remove vport list node.

The datapath list of ports was removed when we switched to using a
hash-based port lookup so the list node is no longer used.

Signed-off-by: Jesse Gross <jesse@nicira.com>
Acked-by: Kyle Mestery <kmestery@cisco.com>

datapath: Fix typo

Signed-off-by: Joe Stringer <joe@wand.net.nz>
Signed-off-by: Jesse Gross <jesse@nicira.com>

lockfile: Log more helpful message when locking fails due to a conflict.

Reported-by: rahim entezari <rahim.entezari@gmail.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

lockfile: In tests, also verify log messages.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

vswitchd: Respect other_config:stp-enable port setting.

Commit a699f614 (lib: Utilize smaps in the idl.) broke the
other_config:stp-enable port setting in two ways.  First, it
changed the default if the setting was missing to disabled.
Second, if the setting was present, it did the opposite of what the
user configured.

Bug #13122.
Reported-by: Paul Ingram <paul@nicira.com>
Signed-off-by: Ethan Jackson <ethan@nicira.com>

ofproto-dpif: Make OFPP_TABLE send packet-in on miss.

The OpenFlow specification for OFPP_TABLE implies that a miss
should generate a packet-in, but Open vSwitch has never done
that.  This corrects the behavior.

This also prepares for the goto-table instruction, which will
need to generate a table-miss in some circumstances.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
[blp@nicira.com rebased and updated commit message]
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofp-msgs: Allow encoding and decoding of Open Flow 1.1 & 1.2 Barrier Messages

Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ovs-ofctl: Use vconn as a parameter of dump_stats_transaction()

In order to form a stats message for the prevailing OpenFlow version
of a vconn the vconn needs to be open at the time the request is
encoded. Thus there is no longer a case where it makes sense to
use dump_stats_transaction() without a vconn already being open and
available to pass as a parameter.

Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofp-msgs: Split OFPRAW_OFPST_AGGREGATE_REQUEST

Split OFPRAW_OFPST_AGGREGATE_REQUEST into OpenFlow 1.0 and 1.1+
versions.

This should be sufficient to allow adding encoding and decoding of
Open Flow 1.1 and 1.2 Aggregate Stats Request messages.

Encoding and decoding of Open Flow 1.1 and 1.2 Aggregate Stats Response
messages works using the existing code without modification.

Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofp-util: Allow decoding of Open Flow 1.2 Flow Statistics Request Messages

Allow decoding of Open Flow 1.1 and 1.2 flow statistics request messages.

Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Ben Pfaff <blp@nicira.com>

ofproto-dpif: refactor rule_dpif_lookup() for table miss whose id > 0

The refactored function, rule_dpif_miss_rule(), will be used for
handling table miss whose table_id > 0 by goto-table instruction.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Ben Pfaff <blp@nicira.com>

tests: Fix autopath tests

With the deprecation of autopath, some tests were broken. This patch fixes
the test breakages.

Signed-off-by: Joe Stringer <joe@wand.net.nz>
Signed-off-by: Ben Pfaff <blp@nicira.com>

bridge: Deprecate the null interface type.

It's not entirely clear what problem the null interface type is
trying to solve, nor how it could be of use to any controller.
This patch deprecates it, and schedules its removal for February
2013.  If there are concerns, please email dev@openvswitch.org.

Signed-off-by: Ethan Jackson <ethan@nicira.com>

nicira-ext: Deprecate the autopath action.

The autopath action is an obsolete attempt to replicate
functionality contained in the bundle action.  It is ugly and of
questionable usefulness.  This patch deprecates it and schedules
its removal for February 2013.  If there are concerns, please email
dev@openvswitch.org.

Signed-off-by: Ethan Jackson <ethan@nicira.com>

bond: Deprecate stable bonds.

The stable bond mode is an obsolete attempt to replicate the
functionality contained in the bundle action.  They are ugly and of
questionable usefulness.  This patch deprecates them and schedules
their removal for February 2013.  If there are concerns, please
email dev@openvswitch.org.

Signed-off-by: Ethan Jackson <ethan@nicira.com>

lib/ofp-actions: improve ofpact_instruction_name_from_type()

eliminate unnecessary loop.

Signed-off-by: Isaku Yamahata <yamahata@valinux.co.jp>
Signed-off-by: Ben Pfaff <blp@nicira.com>

datapath: Fix namespace refcount leak on failed init.

If a datapath fails to initialze fully (likely due to out-of-memory)
then it's possible that we can take a reference to a network
namespace but never release it.  This fixes the problem by releasing
any resources in the event of an error.

Found by code inspection, it's likely to be extremely rare in practice.

Signed-off-by: Jesse Gross <jesse@nicira.com>
Acked-by: Pravin B Shelar <pshelar@nicira.com>

stp: port_no counter is off by one

This counter was off by one, because port_num
should be less than STP_MAX_PORTS.

This caused an assert hit later in stp_get_port().

Issue: 13059
Signed-off-by: Ansis Atteka <aatteka@nicira.com>
Reported-by: Ram Jothikumar <rjothikumar@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

ofproto-dpif: Make sure one-packet flows have zero duration (again).

commit 6a0a5bbbc (ofproto-dpif: Make sure one-packet flows have zero
duration.) was supposed to fix failures in the "ofproto-dpif - NetFlow
flow expiration" test, but it didn't fix the whole problem.  That commit
eliminated one reason why a one-packet flow might be shown as having an
nonzero duration, but missed another.

The other reason was that the call to dpif_flow_stats_extract() could
obtain a time later than the time that a new facet was created.  (This
wasn't obvious because dpif_flow_stats_extract() obtained the time
internally instead of taking it from the caller.)  This commit fixes that
problem, by using the facet creation there too for the first packet in
a facet.

This problem has suddenly started showing up in a lot of builds.  I think
it's probably because of the recent change that makes x86-64 skip the timer
optimizations, so that the return value of time_msec() changes every 1 ms,
not just every 100 ms.

I've tested this by running the test in question in a loop for several
minutes, without any failures.

Signed-off-by: Ben Pfaff <blp@nicira.com>

dpif: Add 'used' argument to dpif_flow_stats_extract().

The following commit will need to use a value other than a literal
time_msec() in one case.  This commit is just preparation.

Factoring the time_msec() call out of the loop in
handle_flow_miss_without_facet() is a really minor optimization.  It isn't
the main point here.

Signed-off-by: Ben Pfaff <blp@nicira.com>

bond: Tag flows according to their hash bucket, not just their slave.

The bonding code is supposed to tag flows two ways:

    - According to the chosen bond slave, to make it easy to invalidate all
      of the flows assigned to a given slave.

    - According to the hash value for a flow, to make it easy to invalidate
      all of the flows that hash into the same bucket.

However, the code wasn't actually applying the hash-based tags.  This
meant that rebalancing didn't take effect immediately, and so after
rebalancing we could get log messages like this:

   inconsistency in subfacet (actions were: 5) (correct actions: 4)

specifying some flow that was moved by the rebalance.

This commit fixes the problem by applying the hash-based tags.

Bug #12847.
Reported-by: Pratap Reddy <preddy@nicira.com>
Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

ofp-actions: Correct copyright statement.

This patch changes the name of Nicira from "Nicira Networks" which
is incorrect, to "Nicira, Inc." which is correct.

Signed-off-by: Ethan Jackson <ethan@nicira.com>

ofproto-dpif: Kill off test-netflow daemon if test fails.

Signed-off-by: Ben Pfaff <blp@nicira.com>

tests: New m4 macro ON_EXIT to add a cleanup action.

Several of the tests start daemons and then need to make sure that the
daemons get killed when the test completes, even if it completes in the
middle due to an early failure.  Until now, they have been using manual
shell "trap" calls to do this.  This works well enough for simple cases,
but sometimes multiple macros start daemons in a single test, and then
each "trap" has to be carefully written to kill off the daemons for the
previously invoked macros.

This commit introduces a new macro ON_EXIT whose use is composable: each
call appends a new action to the ones already specified.

Signed-off-by: Ben Pfaff <blp@nicira.com>

bonding: Update bonding documentation in INTERNALS.

Signed-off-by: Ethan Jackson <ethan@nicira.com>