From 15938f6d22f09d568d437de0693b222fc25ac6bc Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Fri, 8 Aug 2008 16:09:15 -0700 Subject: [PATCH] Don't compare wildcards, nw_src_mask, nw_dst_mask fields in hash table. They should always compare equal, so there's no point in wasting the time. --- datapath/flow.h | 46 +++++++++++++++++++++++++------------------ datapath/table-hash.c | 8 ++++---- include/flow.h | 3 ++- switch/table-hash.c | 8 ++++---- 4 files changed, 37 insertions(+), 28 deletions(-) diff --git a/datapath/flow.h b/datapath/flow.h index 00445f4aa..cd58327c6 100644 --- a/datapath/flow.h +++ b/datapath/flow.h @@ -16,29 +16,37 @@ struct sk_buff; struct ofp_flow_mod; /* Identification data for a flow. - Network byte order except for the "wildcards" field. - In decreasing order by size, so that sw_flow_key structures can - be hashed or compared bytewise. - It might be useful to reorder members from (expected) greatest to least - inter-flow variability, so that failing bytewise comparisons with memcmp - terminate as quickly as possible on average. */ + * Network byte order except for the "wildcards" field. + * Ordered to make bytewise comparisons (e.g. with memcmp()) fail quickly and + * to keep the amount of padding to a minimum. + * If you change the ordering of fields here, change flow_keys_equal() to + * compare the proper fields. + */ struct sw_flow_key { - uint32_t wildcards; /* Wildcard fields (host byte order). */ - uint32_t nw_src; /* IP source address. */ + uint32_t nw_src; /* IP source address. */ + uint32_t nw_dst; /* IP destination address. */ + uint16_t in_port; /* Input switch port */ + uint16_t dl_vlan; /* Input VLAN. */ + uint16_t dl_type; /* Ethernet frame type. */ + uint16_t tp_src; /* TCP/UDP source port. */ + uint16_t tp_dst; /* TCP/UDP destination port. */ + uint8_t dl_src[ETH_ALEN]; /* Ethernet source address. */ + uint8_t dl_dst[ETH_ALEN]; /* Ethernet destination address. */ + uint8_t nw_proto; /* IP protocol. */ + uint8_t pad; /* Pad to 32-bit alignment. */ + uint32_t wildcards; /* Wildcard fields (host byte order). */ uint32_t nw_src_mask; /* 1-bit in each significant nw_src bit. */ - uint32_t nw_dst; /* IP destination address. */ - uint32_t nw_dst_mask; /* 1-bit in each significant nw_dst bit. */ - uint16_t in_port; /* Input switch port */ - uint16_t dl_vlan; /* Input VLAN. */ - uint16_t dl_type; /* Ethernet frame type. */ - uint16_t tp_src; /* TCP/UDP source port. */ - uint16_t tp_dst; /* TCP/UDP destination port. */ - uint8_t dl_src[ETH_ALEN]; /* Ethernet source address. */ - uint8_t dl_dst[ETH_ALEN]; /* Ethernet destination address. */ - uint8_t nw_proto; /* IP protocol. */ - uint8_t pad; /* NB: Pad to make 32-bit aligned */ + uint32_t nw_dst_mask; /* 1-bit in each significant nw_dst bit. */ }; +/* Compare two sw_flow_keys and return true if they are the same flow, false + * otherwise. Wildcards and netmasks are not considered. */ +static inline int flow_keys_equal(const struct sw_flow_key *a, + const struct sw_flow_key *b) +{ + return !memcmp(a, b, offsetof(struct sw_flow_key, wildcards)); +} + /* We need to manually make sure that the structure is 32-bit aligned, * since we don't want garbage values in compiler-generated pads from * messing up hash matches. diff --git a/datapath/table-hash.c b/datapath/table-hash.c index 46acf80e3..26db5229c 100644 --- a/datapath/table-hash.c +++ b/datapath/table-hash.c @@ -39,7 +39,7 @@ static struct sw_flow *table_hash_lookup(struct sw_table *swt, const struct sw_flow_key *key) { struct sw_flow *flow = *find_bucket(swt, key); - return flow && !memcmp(&flow->key, key, sizeof *key) ? flow : NULL; + return flow && flow_keys_equal(&flow->key, key) ? flow : NULL; } static int table_hash_insert(struct sw_table *swt, struct sw_flow *flow) @@ -58,7 +58,7 @@ static int table_hash_insert(struct sw_table *swt, struct sw_flow *flow) retval = 1; } else { struct sw_flow *old_flow = *bucket; - if (!memcmp(&old_flow->key, &flow->key, sizeof flow->key)) { + if (!flow_keys_equal(&old_flow->key, &flow->key)) { rcu_assign_pointer(*bucket, flow); flow_deferred_free(old_flow); retval = 1; @@ -90,7 +90,7 @@ static int table_hash_delete(struct sw_table *swt, if (key->wildcards == 0) { struct sw_flow **bucket = find_bucket(swt, key); struct sw_flow *flow = *bucket; - if (flow && !memcmp(&flow->key, key, sizeof *key)) + if (flow && flow_keys_equal(&flow->key, key)) count = do_delete(bucket, flow); } else { unsigned int i; @@ -239,7 +239,7 @@ static struct sw_flow *table_hash2_lookup(struct sw_table *swt, for (i = 0; i < 2; i++) { struct sw_flow *flow = *find_bucket(t2->subtable[i], key); - if (flow && !memcmp(&flow->key, key, sizeof *key)) + if (flow && flow_keys_equal(&flow->key, key)) return flow; } return NULL; diff --git a/include/flow.h b/include/flow.h index 57754c126..1364e3a74 100644 --- a/include/flow.h +++ b/include/flow.h @@ -33,6 +33,7 @@ #ifndef FLOW_H #define FLOW_H 1 +#include #include #include "util.h" @@ -53,7 +54,7 @@ struct flow { uint8_t dl_src[6]; /* Ethernet source address. */ uint8_t dl_dst[6]; /* Ethernet destination address. */ uint8_t nw_proto; /* IP protocol. */ - uint8_t reserved; /* One byte of padding. */ + uint8_t reserved; /* Pad to 32-bit alignment. */ }; BUILD_ASSERT_DECL(sizeof (struct flow) == 32); diff --git a/switch/table-hash.c b/switch/table-hash.c index 90fd87aae..014529b8b 100644 --- a/switch/table-hash.c +++ b/switch/table-hash.c @@ -60,7 +60,7 @@ static struct sw_flow *table_hash_lookup(struct sw_table *swt, const struct sw_flow_key *key) { struct sw_flow *flow = *find_bucket(swt, key); - return flow && !memcmp(&flow->key, key, sizeof *key) ? flow : NULL; + return flow && !flow_compare(&flow->key.flow, &key->flow) ? flow : NULL; } static int table_hash_insert(struct sw_table *swt, struct sw_flow *flow) @@ -79,7 +79,7 @@ static int table_hash_insert(struct sw_table *swt, struct sw_flow *flow) retval = 1; } else { struct sw_flow *old_flow = *bucket; - if (!memcmp(&old_flow->key, &flow->key, sizeof flow->key)) { + if (!flow_compare(&old_flow->key.flow, &flow->key.flow)) { *bucket = flow; flow_free(old_flow); retval = 1; @@ -111,7 +111,7 @@ static int table_hash_delete(struct sw_table *swt, if (key->wildcards == 0) { struct sw_flow **bucket = find_bucket(swt, key); struct sw_flow *flow = *bucket; - if (flow && !memcmp(&flow->key, key, sizeof *key)) { + if (flow && !flow_compare(&flow->key.flow, &key->flow)) { do_delete(bucket); count = 1; } @@ -251,7 +251,7 @@ static struct sw_flow *table_hash2_lookup(struct sw_table *swt, for (i = 0; i < 2; i++) { struct sw_flow *flow = *find_bucket(t2->subtable[i], key); - if (flow && !memcmp(&flow->key, key, sizeof *key)) + if (flow && !flow_compare(&flow->key.flow, &key->flow)) return flow; } return NULL; -- 2.43.0