datapath: optimize flow compare and mask functions

Make sure the sw_flow_key structure and valid mask boundaries are always
machine word aligned. Optimize the flow compare and mask operations
using machine word size operations. This patch improves throughput on
average by 15% when CPU is the bottleneck of forwarding packets.

This patch is inspired by ideas and code from a patch submitted by Peter
Klausler titled "replace memcmp() with specialized comparator".
However, The original patch only optimizes for architectures
support unaligned machine word access. This patch optimizes for all
architectures.

Signed-off-by: Andy Zhou <azhou@nicira.com>
Signed-off-by: Jesse Gross <jesse@nicira.com>
Fix typos in a couple of OpenFlow related comments.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>
classifier: New function cls_rule_move().

This function will acquire its first user in an upcoming commit.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>
ofproto-dpif-xlate: Fix fin_timeout to make rules expirable.

In an Open vSwitch flow table that has a configured maximum number of
flows, flows that have an idle or hard timeout, or both, are expirable,
and flows with neither are permanent.  The fin_timeout action can change
a flow that has no idle or hard timeout into one that has either one or
both, which should make a permanent flow into an expirable one, but the
implementation was buggy and did not actually make the flow expirable.
This commit fixes the problem.

This commit also moves most of the implementation of fin_timeout from
ofproto-dpif-xlate into ofproto, because this seems to better respect the
layering.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>
ofp-util: Abstract flow_mod OFPFF_* flags.

The OFPFF_* flags used in flow_mods are just confusing enough that it
seems worthwhile to try to abstract them out.  In particular:

    * OFPFF_EMERG was introduced in OF1.0, deleted in OF1.1, and then
      its bit was reused for a different purpose in OF1.2.

    * OFPFF_RESET_COUNTS was introduced in OF1.2 but the semantics that it
      specifies are implied by "add" commands in earlier versions, so
      proper translation requires the OpenFlow version number and flow_mod
      command.

This commit does the abstraction.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>
ofproto: Make OFPFC_ADD internally modify a rule instead of swapping.

add_flow() in ofproto.c has a race: it adds a new flow to the flow table
before calling ->rule_construct().  That means that (in ofproto-dpif) the
new flow is visible to the forwarder threads before gets properly
initialized.

One solution would be to lock the flow table across the entire operation,
but this is not desirable:

   * We would need a write-lock but this would be expensive for
     implementing "learn" flow_mods that often don't really modify anything
     at all.

   * The code would need to keep the lock across a couple of differen calls
     into the client, which seems undesirable if it can be avoided.

   * The code in add_flow() is difficult to understand already.

Instead, I've decided to refactor add_flow() to simplify it and make it
easier to understand.  I think this will also improve the potential for
concurrency.

This commit starts off by collapsing two different cases together into
(almost) one.  In particular, OpenFlow has two ways to modify a flow with a
"flow_mod" command.  You can use an "add" flow_mod to replace the flow, or
you can use a "modify" flow_mod to change it.  The differences in semantics
are minor, but until now Open vSwitch has treated them quite differently.
This commit merges both cases, treating them as variants of what was
previously a "modify".  The advantage is that add_flow() no longer has to
deal with two flows at a time in the "add" case (the old flow being
deleted, the new flow replacing that one).  This does not fix the race, but
it makes it easier to deal with in a later commit.

Transforming "add" into a form of "modify" requires that "modify" be able
to reset flow statistic counters.  OpenFlow 1.2 and later make this an
optional flag in a "flow_mod".  Until now, we haven't implemented that
feature of OF1.2+, but we get it pretty much for free with this
refactoring, so this commit also adds that OF1.2+ feature too.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>
datapath: add rounddown() definition into compatibility code

rounddown() was not available in older kenrel, such as kernel 2.6.32.61.
Add it to the compatibility code.

Signed-off-by: Andy Zhou <azhou@nicira.com>
Signed-off-by: Jesse Gross <jesse@nicira.com>
ofproto: Fully construct rules before putting them in the classifier.

add_flow() in ofproto.c has a race: it adds a new flow to the flow table
before calling ->rule_construct().  That means that (in ofproto-dpif) the
new flow is visible to the forwarder threads before gets properly
initialized.

One solution would be to lock the flow table across the entire operation,
but this is not desirable:

   * We would need a write-lock but this would be expensive for
     implementing "learn" flow_mods that often don't really modify anything
     at all.

   * The code would need to keep the lock across a couple of different calls
     into the client, which seems undesirable if it can be avoided.

   * The code in add_flow() is difficult to understand already.

Instead, I've decided to refactor add_flow() to simplify it and make it
easier to understand.  I think this will also improve the potential for
concurrency.

This commit completes the initial refactoring and solves the race.  It makes
two key changes:

    1. It disentangles insertion of a new flow from evicting some existing
       flow to make room for it (if necessary).  Instead, if inserting a
       new flow would make the flow table overfull, it evicts a flow and
       commits that operation before it attempts the insertion.  This is
       a user-visible change in behavior, in that previously a flow table
       insertion could never cause the number of flows in the flow table
       to decrease, and now it theoretically could if the eviction succeeds
       but the insertion fails.  However, I do not think that this is a
       serious problem.

    2. It adds two new steps to the life cycle of a rule.  Previously,
       rules had "alloc", "construct", "destruct", and "dealloc" steps,
       like other ofproto objects do.  This adds "insert" and "delete"
       steps between "construct" and "destruct".  The new steps are
       intended to handle the actual insertion and deletion into the
       datapath flow table.

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