random: Add entropy test.

This test would have made the bug fixed in the previous commit obvious.  It
would have printed the following:

average=0007c220

bit      0     1
  0  5012  4988
  1  5019  4981
  2  5154  4846
  3  4909  5091
  4  5011  4989
  5  5021  4979
  6  4911  5089
  7  4910  5090
  8  5011  4989
  9  5020  4980
 10  5154  4846
 11  5021  4979
 12  5155  4845
 13  5019  4981
 14  5153  4847
 15  5153  4847
 16  5153  4847
 17  5153  4847
 18  5153  4847
 19  5152  4848
 20 10000     0
 21 10000     0
 22 10000     0
 23 10000     0
 24 10000     0
 25 10000     0
 26 10000     0
 27 10000     0
 28 10000     0
 29 10000     0
 30 10000     0
 31 10000     0
(expected values are 5000)

nibble   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
     0 696 646 564 693 542 545 612 611 687 663 645 560 674 566 592 704
     1 625 589 597 571 638 623 604 663 670 652 650 557 541 683 686 651
     2 628 644 659 672 648 569 585 616 623 647 681 600 586 675 601 566
     3 683 665 717 549 633 613 701 592 663 531 545 800 623 608 590 487
     4 622 657 777 557 720 608 613 598 657 678 551 654 615 596 598 499
     5 10000   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
     6 10000   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
     7 10000   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
(expected values are 625)

random: Fix random number generator.

As written, this "32-bit" random number generator nevers returns a value
bigger than 0xfffe0.  This fixes the problem.

hmap: New macro HMAP_FOR_EACH_CONTINUE.

classifier: Delete dead code specialized for the exact table.

These functions and macros are no longer used.

classifier: Drop CLS_INC_* enumerations and related 'include' parameters.

This type and these parameters were useful when ofproto had the need to
separately traverse exact-match rules looking for subrules, but it no
longer does that because subrules (now called "facets") are not kept in
the classifier any longer.  All the callers are now passing CLS_INC_ALL
anyhow, so we might as well delete this feature and simplify the code.

test-classifier: Use get_unaligned_u32() from unaligned.h.

There's no point in defining our own code to do this here.

ofproto: Simplify rule_insert().

There's no reason for the 'packet' and 'in_port' arguments; the caller can
call rule_execute() just as easily as rule_insert() can.

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

ofproto: Don't bother returning value from facet_make_actions().

None of the remaining callers use the return value.

ofproto: Fix accounting in facet_revalidate().

When a facet moves from one rule to another, facet_revalidate() would
credit the packet and byte counters for the facet to the new rule (which
hasn't actually had any packets sent with the new actions at this point),
instead of to the old rule (which did potentially get some packets sent
with its old actions).  This commit fixes the problem.

ofproto: Break subrules out of "struct rule" into new "struct facet".

Until now, there have been three types of struct rule:

   - An OpenFlow rule with wildcards, that may have exact-match "subrules".

   - An OpenFlow rule without wildcards.

   - A subrule that has no wildcards.

This is at best confusing.  At worst, it leads to bugs.

This commit changes the situation to:

   - "struct rule" represents an OpenFlow rule, with or without wildcards.

   - "struct facet" is what was called a subrule before.

This commit is intended to be more or less the minimal patch necessary to
implement this change.  Followup commits will further improve the code.

netdev-linux: HFSC in linux

This commit implements the Hierarchical Fair Service Curve queuing
discipline in linux. HFSC performs better at high bandwidth and
implements min-rate proportional sharing of excess bandwidth.  Only
a simplified configuration interface is exposed to the user.  This
can be expand to allow more tweaking in the future.

ofproto: Avoid clearing NetFlow stats twice upon rule creation.

This seems cleaner to me: it seems risky to "clear" something that has not
been initialized yet.  It's also a super-minor optimization, I suppose.

ofproto: Make xlate_actions() initialize '*tags' itself.

This seems cleaner than expecting the caller to do it.

ofproto: Disable timeouts for flows added by ofproto_add_flow().

None of the existing callers of ofproto_add_flow() want an idle timeout,
but ofproto_add_flow() was giving them a 5-second timeout anyway.  I don't
know how this worked properly--in-band will patiently add the flow back
every few seconds anyway, but the bridge doesn't do that.

Also add an explanatory comment to ofproto_add_flow().

ofproto: Fix used time of revalidated subrules.

Despite the comment, the 'used' member of a rule is always set to at least
the value of 'created', except in one case in revalidation.  That case
appears to be just a mistake, so this commit changes it and corrects the
comment.

ofp-parse: Refactor flow parsing.

ofp-parse: Generalize parse_ofp_add_flow_str() as parse_ofp_flow_mod_str().

This generalization allows us to delete several lines of code from
ovs-ofctl.c.

nx-match: Add tests that wildcard bits are zeroed by flow parser.

Suggested-by: Justin Pettit <jpettit@nicira.com>

Add support for matching Ethernet multicast frames.

ofproto: Implement support for registers in extended flow match.

test-classifier: Test CLASSIFIER_FOR_EACH_EXACT_RULE.

This would have found the bug fixed by the previous commit.

classifier: Pass correct member to CONTAINER_OF in cls_table_next_rule().

Fixes a segmentation fault in uses of CLASSIFIER_FOR_EACH_EXACT_RULE.

Reported-by: Derek Cormier <derek.cormier@lab.ntt.co.jp>

ofproto: Fix use of uninitialized variable.

My compiler didn't report this but Ethan's did.

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

socket-util: Work around Unix domain socket path name limits on Linux.

Many Open vSwitch tests fail on Debian's automatic build machines because
the builds occur in deeply nested directories with long names.  OVS tries
to bind and connect to Unix domain sockets using absolute path names, which
in combination with long directory names means that the socket's name
exceeds the limit for Unix domain socket names (108 bytes on Linux).

This commit works around the problem on Linux by indirecting through
/proc/self/fd/<dirfd>/<basename> when names exceed the maximum that can be
used directly.

Reported-by: Hector Oron <hector.oron@gmail.com>
Reported-by: Sebastian Andrzej Siewior <sebastian@breakpoint.cc>
Reported-by: Roger Leigh <rleigh@codelibre.net>
Debian bug #602891.
Debian bug #602911.

socket-util: Define LINUX macro at top of file.

This will be used further in the following commit.

util: New function base_name().

CodingStyle: Clarify C dialect section and add rationale.

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

debian: Remove corekeeper package.

The corekeeper package has little or nothing to do with Open vSwitch
itself, so remove it.

lib: Distribute nx-match.def, fixing "make dist".

ofproto: Factor out code from do_xlate_actions() into new function.

This helper will be useful elsewhere in upcoming commits.

ofp-util: Make validate_actions() take a struct flow *.

The upcoming support for actions on registers will require the flow to
validate actions, so this commit adds the parameter in advance.  It is
not yet used.

ofproto: Refactor handle_packet_out().

An upcoming commit will require the flow to be passed in as part of
OpenFlow action validation, but handle_packet_out() has until now been
structured to make this difficult.  This commit refactors it to better
suit this purpose.

ofproto: Implement Nicira Extended Match flexible flow match (NXM).

ofproto: Fix type of 'out_port' parameter to query_aggregate_stats().

Reported-by: Justin Pettit <jpettit@nicira.com>

ofproto: Rename *_stats_reply() functions for clarity.

Suggested-by: Justin Pettit <jpettit@nicira.com>

datapath: Fix build on 2.6.18.

Build-tested (only) on 2.6.18 from XenServer 5.5.0, 2.6.26, 2.6.29, 2.6.34,
and 2.6.36.

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

Fix distribution by adding include/linux/if_link.h to "make dist".

Why can't I ever get this right the first time?

datapath: Use "struct rtnl_link_stats64" instead of "struct odp_vport_stats".

Linux 2.6.35 added struct rtnl_link_stats64, which as a set of 64-bit
network device counters is what the OVS datapath needs.  We might as well
use it instead of our own.

This commit moves the if_link.h compat header from datapath/ into the
top-level include/ directory so that it is visible both to kernel and
userspace code.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Jesse Gross <jesse@nicira.com>

datapath: Clean up netdev_get_stats() very slightly.

dev_get_stats() is documented to return its output argument, so there's no
need to maintain a separate pointer variable.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Jesse Gross <jesse@nicira.com>

datapath: Add clean compat layer for dev_get_stats().

Build tested (only) only on i386 for 2.6.26, 2.6.29, 2.6.33, 2.6.34,
and 2.6.36, and on x86-64 for 2.6.31 and 2.6.36.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Jesse Gross <jesse@nicira.com>

datapath: Use struct assignment in place of memcpy() for copying stats.

We might as well take advantage of type safety when we can get it.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Jesse Gross <jesse@nicira.com>

ovsdb: Fix "make dist" by distributing dot2pic.

flow: Better abstract flow_wildcards and use it more widely.

nicira-ext: Shuffle comments around.

It seemed to me that the descriptions of what actions do should be just
above the action structures, where the reader can see the arguments,
instead of just above the enumeration name, so I rearranged the code
this way.

A few actions didn't have their own structures, so to do this I had to give
them some.

classifier: Add more cls_rule_set_*() functions.

These will be handy later but are not used yet.

classifier: Move in-band set_<field>() functions publicly available.

These will be useful elsewhere later.

ofproto: Change ofproto_add_flow(), ofproto_delete_flow() to take cls_rule.

This is a small cleanup that will make later changes to wildcards easier.

ofproto: Refactor handle_flow_mod().

This breaks this OpenFlow handler into two parts, one responsible
for parsing and constructing OpenFlow messages and one that works
with the flow table.  The latter will be reused in a later commit
that implements the Nicira Extended Match flexible flow match
extension.

Rename cls_rule_zero_wildcards() to cls_rule_zero_wildcarded_fields().

Justin said that he found the shorter name confusing.

ofproto: Refactor handle_aggregate_stats_request().

This breaks this OpenFlow handler into two parts, one responsible
for parsing and constructing OpenFlow messages and one that works
with the flow table.  The latter will be reused in a later commit
that implements the Nicira Extended Match flexible flow match
extension.

ofproto: Generalize reject_slave_controller().

ofproto: Factor flow duration calculation into new calc_flow_duration().

ofproto: Get rid of redundant ofproto parameters in presence of ofconn.

An ofconn has a member that points to its ofproto, so there's never a need
to pass both an ofconn and its ofproto as parameters to a function.

Suggested-by: Justin Pettit <jpettit@nicira.com>

ofproto: Make flow format specific to an OpenFlow connection.

Until now the flow format has been a global property of an ofproto.
This is no longer appropriate, because the Nicira Extended Match
flow format that upcoming commits will add is not compatible with
OpenFlow 1.0-only controllers.  This commit changes the flow format
to a property of an individual OpenFlow connection.

ofproto: Generalize tun_id_from_cookie into flow_format.

Upcoming commits will add more flow formats, so this needs to be
an enumerated type instead of a bool.

Add "Manager" and "manager_options" to allow options for OVSDB connections.

I'm retaining the "managers" column in the Open_vSwitch table for now, but
I hope that applications transition to using "manager_options" eventually
so that we could drop it.

CC: Andrew Lambeth <wal@nicira.com>
CC: Jeremy Stribling <strib@nicira.com>

in-band: Make in_band_create() always initialize its output argument.

This isn't a bug fix but it seems like a good thing to do.

reconnect: Use macros instead of literals for default timeouts.

docs: Implement our own dot->pic translator.

Recent versions of Graphviz no longer support output to PIC format, so this
commit adds our own internal translator from dot's "plain" output format
to PIC format.  The "plain" format works best with slightly different
"dot" input (advised by the Graphviz manual description of the "plain"
format) so this commit also adjusts ovsdb-dot's output.

configure: Fix Graphviz test and input generation.

This check for Graphviz never actually worked properly because Autoconf
swallows up the [] around [gG], so Graphviz was always detected as missing.
This commit fixes the problem by doubling up to [[gG]].

Because Graphviz was never used, I never noticed that ovsdb-dot had not
been revised to use the latest Python interface to OVSDB, so this commit
fixes up those problems too.

ofproto: Improve comment in send_flow_removed().

ofproto: Simplify send_flow_removed().

I have no evidence that the optimization in this function is valuable.
An upcoming commit will introduce a new form of flow expiration message
that is sent to controllers that ask for it, while the standard OpenFlow
1.0 message is sent to other controllers.  Since retaining this
optimization with that logic would complicate the function, this commit
drops it.

ofp-util: New functions make_nxmsg(), make_nxmsg_xid().

These functions slightly simplify constructing Nicira vendor extension
messages.

ofp-util: Add macros for composing error codes.

These are useful in static initializers and case labels, where function
calls are not allowed.

Sync Nicira error number assignments with "wdp" branch.

This adds the error numbers that the "wdp" branch added, without adding
any uses of them (because they are not needed on "master" yet).

ofp-util: Use our usual variable naming convention in make_ofp_error_msg().

ofp-util: Actually map vendor codes to IDs correctly.

Reported-by: Justin Pettit <jpettit@nicira.com>

ofp-util.h: Use NX_VENDOR_ID instead of literal numeric constant.

Fix typos in comments.

ofp-util: Add infrastructure for vendor extensions to OpenFlow error codes.

Cross-ported from "wdp" branch.

ofp-util: Add more functions for supporting OpenFlow error codes.

Cross-ported from "wdp" branch.

AUTHORS: Add Romain Lenglet.

ofp-print: always print the flow nw_tos if not wildcarded

Print the nw_tos field for all flows if it is not wildcarded, instead
of only if the dl_type is IP and the nw_proto is not ICMP, TCP, or
UDP.

datapath: Directly use free_netdev for internal devices.

Currently internal devices register a destructor function which
simply calls free_netdev.  Instead we can simply set the destructor
to free_netdev.  In addition to being cleaner, it is also a bug fix
because the module could be unloaded before the destructor is called,
making a call into our code illegal.

Signed-off-by: Jesse Gross <jesse@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>

ovs-vsctl: Create bridge interface as type "internal".

The bridge device is always an internal interface, so it seems best to
actually mark it as one.  Jesse would like to eventually make the "type"
column mandatory for Interface records, so here's a step in the right
direction.

netdev: Assert that the type of a new network device is correct.

This would have found a bug that I accidentally inserted while working on
netdev-linux.

PORTING: Update to describe netdev-vport.c

The "lib/netdev-gre.c" and "lib/netdev-patch.c" files have been
consolidated into "lib/netdev-vport.c".  This change reflect that.

CodingStyle: Mention that "free" functions should accept a null pointer.

I've always written OVS code this way, so this just codifies it so that
others know.

ovsdb-client: Add JSON output format.

Requested-by: DK Moon <dkmoon@nicira.com>
CC: DK Moon <dkmoon@nicira.com>

ovsdb-client: Refactor table code to save original json during formatting.

This refactoring should not change user-visible behavior, but saving the
JSON used to format tables will make it possible to print the raw JSON in
the following commit.

configure: Simplify use of OVS_GREP_IFELSE.

Most users of OVS_GREP_IFELSE simply defined HAVE_<regex>, so make this
the default.

ofproto: Don't show separate wildcard and exact-match tables via OpenFlow.

Formerly the classifier used in Open vSwitch was very sensitive to the
number of exact-match versus wildcarded rules, so it made sense to show
them as separate tables over OpenFlow.  The current classifier doesn't
have the same performance sensitivity, so we might as well just show one
table.

classifier: Rewrite.

The old classifier was not adaptive: it required knowing the structure of
the flows that were likely to be in use to get good performance.  It is
likely that it degenerated to linear search in any real-world case.

This new classifier is adaptive and should perform better in the real
world.

autoconf: Compat checks no longer support multiple files.

We now test that a file exists before grepping but that doesn't
work if there are multiple possible files.  For the one case that
needs this (kmemdup) break the test into two: check the first file
and if the pattern isn't found check the second file.

datapath: Work around debugging for csum_and_copy_to_user().

Certain versions of XenServer add debugging to csum_and_copy_to_user()
in such a way that it changes the function signature.  This adds a
check and a workaround to allow us to build on these versions.

Signed-off-by: Jesse Gross <jesse@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>

autoconf: Tolerate missing file when grepping.

Currently we die when grepping for compatibility strings if the
file does not exist.  Since this can be a valid situation when
files are added in later versions, we shouldn't kill the build.
Instead, note that the file doesn't exist but otherwise treat it
as if the string was not found.

ovsdb: Fix formatting of ovs.db.Error on Python 2.6.

All of the negative Python OVSDB tests were failing on Python 2.6 because
"%s\n" % e yielded the empty string on that version of Python.  In turn,
that was because ovs.db.error.Error.__unicode__ was being called instead of
ovs.db.error.Error.__str__.  I'm puzzled why that was happening, but this
commit fixes it and also seems like a small code cleanup.

Peter Balland helped me gain some insight on this problem.

CC: Peter Balland <peter@nicira.com>
CC: Reid Price <reid@nicira.com>

datapath: The definition of struct tbl is needed by rcu_dereference()

Due to the use of typeof(*p) by __rcu_dereference_check(),
which was introduced by the Linux changeset
ca5ecddfa8fcbd948c95530e7e817cee9fb43a3d
(rcu: define __rcu address space modifier for sparse) the definition
of the type of a the parameter to rcu_dereference() is needed.

In terms of the datapath, this means that the definition of
struct tbl needs to be available wherever rcu_dereference(dp->table)
is called.

Signed-off-by: Simon Horman <horms@verge.net.au>
Signed-off-by: Jesse Gross <jesse@nicira.com>

datapath: IFF_OVS_DATAPATH will exist in in 2.6.37

Signed-off-by: Simon Horman <horms@verge.net.au>
[Jesse: drop comment that no longer applies]
Signed-off-by: Jesse Gross <jesse@nicira.com>

Fix "make dist" by adding include/openvswitch/types.h to the distribution.

classifier: Change classifier_rule_overlaps() to take a cls_rule *.

There's no benefit to spelling out all of the components of a cls_rule
separately.  Just use cls_rule itself.

classifier: Change classifier_find_rule_exactly() to take a cls_rule *.

There's no benefit to spelling out all of the components of a cls_rule
separately.  Just use cls_rule itself.

classifier: Merge classifier_lookup_wild(), classifier_lookup_exact().

Merge these functions into classifier_lookup() and update its interface.

The new version of the classifier soon to be implemented naturally merges
these functions, so this commit updates the interface early.

classifier: Remove classifier_insert_exact().

This function doesn't provide any extra useful functionality.  It is
amenable to a slightly optimized implementation in the current classifier,
but not in the one that will soon replace it, so get rid of it.

classifier: Remove unused functions cls_rule_moved(), cls_rule_replace().

In preparation for rewriting the classifier, remove some functions that
nothing uses and have no tests.

odp-util: Print in_port in decimal in format_odp_flow_key().

Suggested-by: Justin Pettit <jpettit@nicira.com>

odp-util: Print tunnel id as part of ODP flow key in format_odp_flow_key().

flow: Add more functions for working with flow_wildcards.

These have limited use now but will become more important later.

flow: Use vlan_tci_to_pcp() helper.

This is just a small cleanup that should not change any behavior.

flow: Un-inline flow_wildcards functions.

These functions really seem too big to inline.