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 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: 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>
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>
ofproto: Move ofpacts_check() calls from ofproto-dpif to ofproto.

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>
flow: Use bit-mask for DSCP and ECN bits, instead of FWW_* flags.

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 IP protocol 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 in_port match, instead of FWW_* flag.

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Ensure that padding is always zeroed.

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: Replace flow_wildcards members by a single "struct flow".

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: 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>
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>
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>
classifier: Fix typo in comment.

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>