#include <linux/if_vlan.h>
#include <net/llc_pdu.h>
#include <linux/kernel.h>
-#include <linux/hash.h>
+#include <linux/jhash.h>
#include <linux/jiffies.h>
#include <linux/llc.h>
#include <linux/module.h>
return ERR_PTR(-ENOMEM);
}
-int ovs_flow_tbl_count(struct flow_table *table)
+int ovs_flow_tbl_count(const struct flow_table *table)
{
return table->count;
}
{
int node;
- kfree((struct sw_flow_actions __force *)flow->sf_acts);
+ kfree(rcu_dereference_raw(flow->sf_acts));
for_each_node(node)
if (flow->stats[node])
kmem_cache_free(flow_stats_cache,
- (struct flow_stats __force *)flow->stats[node]);
+ rcu_dereference_raw(flow->stats[node]));
kmem_cache_free(flow_cache, flow);
}
{
struct mask_array *new;
+ size = max(MASK_ARRAY_SIZE_MIN, size);
new = kzalloc(sizeof(struct mask_array) +
sizeof(struct sw_flow_mask *) * size, GFP_KERNEL);
if (!new)
old = ovsl_dereference(tbl->mask_array);
if (old) {
- int i;
+ int i, count = 0;
- for (i = 0; i < old->max; i++)
- new->masks[i] = old->masks[i];
+ for (i = 0; i < old->max; i++) {
+ if (ovsl_dereference(old->masks[i]))
+ new->masks[count++] = old->masks[i];
+ }
- new->count = old->count;
+ new->count = count;
}
rcu_assign_pointer(tbl->mask_array, new);
return 0;
}
-static void tbl_mask_array_delete_mask(struct mask_array *ma,
- const struct sw_flow_mask *mask)
-{
- int i = 0;
-
- /* Delete a mask pointer from the valid section.
- *
- * Also move the last entry in its place, so there is no
- * whole in the valid section.
- *
- * Notice the last entry still points to the original mask.
- *
- * <Note>: there is a small race window that may cause a mask
- * to be missed in a search. Imaging a core is
- * walking through the array, passing the index of deleting mask.
- * But before reaching the last entry, it is overwritten,
- * by another core that is adding a new mask, now the last entry
- * will point to the new mask. In this case, the moved up last
- * entry can be missed by the core walking the mask array.
- *
- * In case this missed mask would have led to successful
- * lookup, Hitting the race window could cause a packet to miss
- * kernel flow cache, and be sent to the user space.
- * </Note>
- */
- for (i = 0; i < ma->count; i++)
- if (mask == ovsl_dereference(ma->masks[i])) {
- struct sw_flow_mask *last;
-
- last = ovsl_dereference(ma->masks[ma->count - 1]);
- rcu_assign_pointer(ma->masks[i], last);
- ma->count--;
- break;
- }
-
- /* Remove the deleted mask pointers from the invalid section. */
- for (i = ma->count; i < ma->max; i++)
- if (mask == ovsl_dereference(ma->masks[i]))
- RCU_INIT_POINTER(ma->masks[i], NULL);
-}
-
int ovs_flow_tbl_init(struct flow_table *table)
{
struct table_instance *ti;
return 0;
free_mask_array:
- kfree((struct mask_array __force *)table->mask_array);
+ kfree(ma);
free_mask_cache:
free_percpu(table->mask_cache);
return -ENOMEM;
}
/* No need for locking this function is called from RCU callback or
- * error path. */
+ * error path.
+ */
void ovs_flow_tbl_destroy(struct flow_table *table)
{
- struct table_instance *ti = (struct table_instance __force *)table->ti;
+ struct table_instance *ti = rcu_dereference_raw(table->ti);
free_percpu(table->mask_cache);
- kfree((struct mask_array __force *)table->mask_array);
+ kfree(rcu_dereference_raw(table->mask_array));
table_instance_destroy(ti, false);
}
/* Make sure number of hash bytes are multiple of u32. */
BUILD_BUG_ON(sizeof(long) % sizeof(u32));
- return arch_fast_hash2(hash_key, hash_u32s, 0);
+ return jhash2(hash_key, hash_u32s, 0);
}
static int flow_key_start(const struct sw_flow_key *key)
}
bool ovs_flow_cmp_unmasked_key(const struct sw_flow *flow,
- struct sw_flow_match *match)
+ const struct sw_flow_match *match)
{
struct sw_flow_key *key = match->key;
int key_start = flow_key_start(key);
static struct sw_flow *masked_flow_lookup(struct table_instance *ti,
const struct sw_flow_key *unmasked,
- struct sw_flow_mask *mask,
+ const struct sw_flow_mask *mask,
u32 *n_mask_hit)
{
struct sw_flow *flow;
return NULL;
}
+/* Flow lookup does full lookup on flow table. It starts with
+ * mask from index passed in *index.
+ */
static struct sw_flow *flow_lookup(struct flow_table *tbl,
struct table_instance *ti,
- struct mask_array *ma,
+ const struct mask_array *ma,
const struct sw_flow_key *key,
u32 *n_mask_hit,
u32 *index)
{
+ struct sw_flow_mask *mask;
struct sw_flow *flow;
int i;
- for (i = 0; i < ma->count; i++) {
- struct sw_flow_mask *mask;
-
- mask = rcu_dereference_ovsl(ma->masks[i]);
+ if (*index < ma->max) {
+ mask = rcu_dereference_ovsl(ma->masks[*index]);
if (mask) {
flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
- if (flow) { /* Found */
- *index = i;
+ if (flow)
return flow;
- }
}
}
- return NULL;
-}
+ for (i = 0; i < ma->max; i++) {
-/* If the the cache index is outside of the valid region, update the index
- * in case cache entry was moved up. */
-static void fixup_cache_entry_index(struct mask_cache_entry *e,
- const struct mask_array *ma,
- const struct sw_flow_mask *cache)
-{
- int i;
+ if (i == *index)
+ continue;
- for (i = 0; i < ma->count; i++)
- if (cache == ovsl_dereference(ma->masks[i])) {
- e->mask_index = i;
- return;
+ mask = rcu_dereference_ovsl(ma->masks[i]);
+ if (!mask)
+ continue;
+
+ flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
+ if (flow) { /* Found */
+ *index = i;
+ return flow;
}
+ }
+
+ return NULL;
}
/*
* cache entry in mask cache.
* This is per cpu cache and is divided in MC_HASH_SEGS segments.
* In case of a hash collision the entry is hashed in next segment.
- * */
+ */
struct sw_flow *ovs_flow_tbl_lookup_stats(struct flow_table *tbl,
const struct sw_flow_key *key,
u32 skb_hash,
u32 *n_mask_hit)
{
- struct mask_array *ma = rcu_dereference_ovsl(tbl->mask_array);
- struct table_instance *ti = rcu_dereference_ovsl(tbl->ti);
+ struct mask_array *ma = rcu_dereference(tbl->mask_array);
+ struct table_instance *ti = rcu_dereference(tbl->ti);
struct mask_cache_entry *entries, *ce;
struct sw_flow *flow;
u32 hash = skb_hash;
*n_mask_hit = 0;
if (unlikely(!skb_hash)) {
- u32 __always_unused mask_index;
+ u32 mask_index = 0;
return flow_lookup(tbl, ti, ma, key, n_mask_hit, &mask_index);
}
e = &entries[index];
if (e->skb_hash == skb_hash) {
- struct sw_flow_mask *cache;
- int i = e->mask_index;
-
- if (likely(i < ma->count)) {
- cache = rcu_dereference_ovsl(ma->masks[i]);
- flow = masked_flow_lookup(ti, key, cache,
- n_mask_hit);
- } else if (i < ma->max) {
- flow = NULL;
- cache = rcu_dereference_ovsl(ma->masks[i]);
- if (cache) {
- fixup_cache_entry_index(e, ma, cache);
- flow = masked_flow_lookup(ti, key,
- cache, n_mask_hit);
- }
- } else {
- flow = NULL;
- }
-
- if (flow) /* Cache hit. */
- return flow;
-
- /* Cache miss. This is the best cache
- * replacement candidate. */
- e->skb_hash = 0;
- ce = e;
- break;
+ flow = flow_lookup(tbl, ti, ma, key, n_mask_hit,
+ &e->mask_index);
+ if (!flow)
+ e->skb_hash = 0;
+ return flow;
}
if (!ce || e->skb_hash < ce->skb_hash)
struct table_instance *ti = rcu_dereference_ovsl(tbl->ti);
struct mask_array *ma = rcu_dereference_ovsl(tbl->mask_array);
u32 __always_unused n_mask_hit;
- u32 __always_unused index;
+ u32 index = 0;
- n_mask_hit = 0;
return flow_lookup(tbl, ti, ma, key, &n_mask_hit, &index);
}
+struct sw_flow *ovs_flow_tbl_lookup_exact(struct flow_table *tbl,
+ const struct sw_flow_match *match)
+{
+ struct mask_array *ma = ovsl_dereference(tbl->mask_array);
+ int i;
+
+ /* Always called under ovs-mutex. */
+ for (i = 0; i < ma->max; i++) {
+ struct table_instance *ti = ovsl_dereference(tbl->ti);
+ u32 __always_unused n_mask_hit;
+ struct sw_flow_mask *mask;
+ struct sw_flow *flow;
+
+ mask = ovsl_dereference(ma->masks[i]);
+ if (!mask)
+ continue;
+ flow = masked_flow_lookup(ti, match->key, mask, &n_mask_hit);
+ if (flow && ovs_flow_cmp_unmasked_key(flow, match))
+ return flow;
+ }
+ return NULL;
+}
+
int ovs_flow_tbl_num_masks(const struct flow_table *table)
{
struct mask_array *ma;
return table_instance_rehash(ti, ti->n_buckets * 2);
}
+static void tbl_mask_array_delete_mask(struct mask_array *ma,
+ struct sw_flow_mask *mask)
+{
+ int i;
+
+ /* Remove the deleted mask pointers from the array */
+ for (i = 0; i < ma->max; i++) {
+ if (mask == ovsl_dereference(ma->masks[i])) {
+ RCU_INIT_POINTER(ma->masks[i], NULL);
+ ma->count--;
+ call_rcu(&mask->rcu, rcu_free_sw_flow_mask_cb);
+ return;
+ }
+ }
+ BUG();
+}
+
/* Remove 'mask' from the mask list, if it is not needed any more. */
static void flow_mask_remove(struct flow_table *tbl, struct sw_flow_mask *mask)
{
struct mask_array *ma;
ma = ovsl_dereference(tbl->mask_array);
- /* Shrink the mask array if necessary. */
- if (ma->max > MASK_ARRAY_SIZE_MIN * 2
- && ma->count <= ma->max / 4) {
+ tbl_mask_array_delete_mask(ma, mask);
+ /* Shrink the mask array if necessary. */
+ if (ma->max >= (MASK_ARRAY_SIZE_MIN * 2) &&
+ ma->count <= (ma->max / 3))
tbl_mask_array_realloc(tbl, ma->max / 2);
- ma = ovsl_dereference(tbl->mask_array);
- }
- tbl_mask_array_delete_mask(ma, mask);
- call_rcu(&mask->rcu, rcu_free_sw_flow_mask_cb);
}
}
}
table->count--;
/* RCU delete the mask. 'flow->mask' is not NULLed, as it should be
- * accessible as long as the RCU read lock is held. */
+ * accessible as long as the RCU read lock is held.
+ */
flow_mask_remove(table, flow->mask);
}
int i;
ma = ovsl_dereference(tbl->mask_array);
- for (i = 0; i < ma->count; i++) {
+ for (i = 0; i < ma->max; i++) {
struct sw_flow_mask *t;
t = ovsl_dereference(ma->masks[i]);
/* Add 'mask' into the mask list, if it is not already there. */
static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow,
- struct sw_flow_mask *new)
+ const struct sw_flow_mask *new)
{
struct sw_flow_mask *mask;
mask = flow_mask_find(tbl, new);
if (!mask) {
struct mask_array *ma;
+ int i;
/* Allocate a new mask if none exsits. */
mask = mask_alloc();
int err;
err = tbl_mask_array_realloc(tbl, ma->max +
- MASK_ARRAY_SIZE_MIN);
+ MASK_ARRAY_SIZE_MIN);
if (err) {
kfree(mask);
return err;
ma = ovsl_dereference(tbl->mask_array);
}
- rcu_assign_pointer(ma->masks[ma->count], mask);
- ma->count++;
+ for (i = 0; i < ma->max; i++) {
+ struct sw_flow_mask *t;
+
+ t = ovsl_dereference(ma->masks[i]);
+ if (!t) {
+ rcu_assign_pointer(ma->masks[i], mask);
+ ma->count++;
+ break;
+ }
+ }
+
} else {
BUG_ON(!mask->ref_count);
mask->ref_count++;
/* Must be called with OVS mutex held. */
int ovs_flow_tbl_insert(struct flow_table *table, struct sw_flow *flow,
- struct sw_flow_mask *mask)
+ const struct sw_flow_mask *mask)
{
struct table_instance *new_ti = NULL;
struct table_instance *ti;
}
/* Initializes the flow module.
- * Returns zero if successful or a negative error code. */
+ * Returns zero if successful or a negative error code.
+ */
int ovs_flow_init(void)
{
BUILD_BUG_ON(__alignof__(struct sw_flow_key) % __alignof__(long));