aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAndrew Yourtchenko <ayourtch@gmail.com>2019-03-20 17:47:03 +0100
committerDamjan Marion <dmarion@me.com>2019-03-22 17:33:09 +0000
commit8e843bbf40aa2bd21f6d7fef02c4230ea66c3bdd (patch)
tree44f5e200d056c1142f3b409582f992ec39974e95
parent9f3d3ceb0130aba2eb11a5cbd2fcef3384864fe8 (diff)
acl-plugin: get rid of doubly-linked list fields in hash applied ACEs
With collision match vector, the doubly-linked list is not needed anymore. Change-Id: Iaf667ebe6ce0bdd78306bec31d3949e6acb8d401 Signed-off-by: Andrew Yourtchenko <ayourtch@gmail.com>
-rw-r--r--src/plugins/acl/hash_lookup.c120
-rw-r--r--src/plugins/acl/hash_lookup_types.h14
2 files changed, 35 insertions, 99 deletions
diff --git a/src/plugins/acl/hash_lookup.c b/src/plugins/acl/hash_lookup.c
index ec3c62e5947..436e5122b50 100644
--- a/src/plugins/acl/hash_lookup.c
+++ b/src/plugins/acl/hash_lookup.c
@@ -541,6 +541,7 @@ add_colliding_rule (acl_main_t * am,
cr.acl_position = pae->acl_position;
cr.applied_entry_index = applied_entry_index;
cr.rule = am->acls[pae->acl_index].rules[pae->ace_index];
+ pae->collision_head_ae_index = head_index;
vec_add1 (head_pae->colliding_rules, cr);
if (ACL_HASH_LOOKUP_DEBUG > 0)
acl_plugin_print_pae(acl_main.vlib_main, head_index, head_pae);
@@ -554,7 +555,6 @@ activate_applied_ace_hash_entry(acl_main_t *am,
{
clib_bihash_kv_48_8_t kv;
ASSERT(new_index != ~0);
- applied_hash_ace_entry_t *pae = vec_elt_at_index((*applied_hash_aces), new_index);
DBG("activate_applied_ace_hash_entry lc_index %d new_index %d", lc_index, new_index);
fill_applied_hash_ace_kv(am, applied_hash_aces, lc_index, new_index, &kv);
@@ -569,27 +569,17 @@ activate_applied_ace_hash_entry(acl_main_t *am,
ASSERT(new_index != ~0);
ASSERT(new_index < vec_len((*applied_hash_aces)));
if (res == 0) {
- /* There already exists an entry or more. Append at the end. */
u32 first_index = result_val->applied_entry_index;
ASSERT(first_index != ~0);
+ ASSERT(first_index < vec_len((*applied_hash_aces)));
+ /* There already exists an entry or more. Append at the end. */
DBG("A key already exists, with applied entry index: %d", first_index);
- applied_hash_ace_entry_t *first_pae = vec_elt_at_index((*applied_hash_aces), first_index);
- u32 last_index = first_pae->tail_applied_entry_index;
- ASSERT(last_index != ~0);
- applied_hash_ace_entry_t *last_pae = vec_elt_at_index((*applied_hash_aces), last_index);
- DBG("...advance to chained entry index: %d", last_index);
- /* link ourselves in */
- last_pae->next_applied_entry_index = new_index;
- pae->prev_applied_entry_index = last_index;
- /* adjust the pointer to the new tail */
- first_pae->tail_applied_entry_index = new_index;
add_colliding_rule(am, applied_hash_aces, first_index, new_index);
return first_index;
} else {
/* It's the very first entry */
hashtable_add_del(am, &kv, 1);
ASSERT(new_index != ~0);
- pae->tail_applied_entry_index = new_index;
add_colliding_rule(am, applied_hash_aces, new_index, new_index);
return new_index;
}
@@ -773,9 +763,7 @@ hash_acl_apply(acl_main_t *am, u32 lc_index, int acl_index, u32 acl_position)
pae->hitcount = 0;
pae->hash_ace_info_index = i;
/* we might link it in later */
- pae->next_applied_entry_index = ~0;
- pae->prev_applied_entry_index = ~0;
- pae->tail_applied_entry_index = ~0;
+ pae->collision_head_ae_index = ~0;
pae->colliding_rules = NULL;
pae->mask_type_index = ~0;
assign_mask_type_index_to_pae(am, lc_index, is_ip6, pae);
@@ -791,19 +779,21 @@ done:
static u32
find_head_applied_ace_index(applied_hash_ace_entry_t **applied_hash_aces, u32 curr_index)
{
- /*
- * find back the first entry. Inefficient so might need to be a bit cleverer
- * if this proves to be a problem..
- */
- u32 an_index = curr_index;
- ASSERT(an_index != ~0);
- applied_hash_ace_entry_t *head_pae = vec_elt_at_index((*applied_hash_aces), an_index);
- while(head_pae->prev_applied_entry_index != ~0) {
- an_index = head_pae->prev_applied_entry_index;
- ASSERT(an_index != ~0);
- head_pae = vec_elt_at_index((*applied_hash_aces), an_index);
- }
- return an_index;
+ ASSERT(curr_index != ~0);
+ applied_hash_ace_entry_t *pae = vec_elt_at_index((*applied_hash_aces), curr_index);
+ ASSERT(pae);
+ ASSERT(pae->collision_head_ae_index != ~0);
+ return pae->collision_head_ae_index;
+}
+
+static void
+set_collision_head_ae_index(applied_hash_ace_entry_t **applied_hash_aces, collision_match_rule_t *colliding_rules, u32 new_index)
+{
+ collision_match_rule_t *cr;
+ vec_foreach(cr, colliding_rules) {
+ applied_hash_ace_entry_t *pae = vec_elt_at_index((*applied_hash_aces), cr->applied_entry_index);
+ pae->collision_head_ae_index = new_index;
+ }
}
static void
@@ -826,35 +816,10 @@ move_applied_ace_hash_entry(acl_main_t *am,
acl_plugin_print_pae(am->vlib_main, old_index, pae);
}
- if (new_pae->tail_applied_entry_index == old_index) {
- /* fix-up the tail index if we are the tail and the start */
- new_pae->tail_applied_entry_index = new_index;
- }
-
- if (pae->prev_applied_entry_index != ~0) {
- applied_hash_ace_entry_t *prev_pae = vec_elt_at_index((*applied_hash_aces), pae->prev_applied_entry_index);
- ASSERT(prev_pae->next_applied_entry_index == old_index);
- prev_pae->next_applied_entry_index = new_index;
- } else {
+ if (pae->collision_head_ae_index == old_index) {
/* first entry - so the hash points to it, update */
add_del_hashtable_entry(am, lc_index,
applied_hash_aces, new_index, 1);
- ASSERT(pae->tail_applied_entry_index != ~0);
- }
- if (pae->next_applied_entry_index != ~0) {
- applied_hash_ace_entry_t *next_pae = vec_elt_at_index((*applied_hash_aces), pae->next_applied_entry_index);
- ASSERT(next_pae->prev_applied_entry_index == old_index);
- next_pae->prev_applied_entry_index = new_index;
- } else {
- /*
- * Moving the very last entry, so we need to update the tail pointer in the first one.
- */
- u32 head_index = find_head_applied_ace_index(applied_hash_aces, old_index);
- ASSERT(head_index != ~0);
- applied_hash_ace_entry_t *head_pae = vec_elt_at_index((*applied_hash_aces), head_index);
-
- ASSERT(head_pae->tail_applied_entry_index == old_index);
- head_pae->tail_applied_entry_index = new_index;
}
if (new_pae->colliding_rules) {
/* update the information within the collision rule entry */
@@ -862,6 +827,7 @@ move_applied_ace_hash_entry(acl_main_t *am,
collision_match_rule_t *cr = vec_elt_at_index (new_pae->colliding_rules, 0);
ASSERT(cr->applied_entry_index == old_index);
cr->applied_entry_index = new_index;
+ set_collision_head_ae_index(applied_hash_aces, new_pae->colliding_rules, new_index);
} else {
/* find the index in the collision rule entry on the head element */
u32 head_index = find_head_applied_ace_index(applied_hash_aces, new_index);
@@ -881,9 +847,7 @@ move_applied_ace_hash_entry(acl_main_t *am,
}
}
/* invalidate the old entry */
- pae->prev_applied_entry_index = ~0;
- pae->next_applied_entry_index = ~0;
- pae->tail_applied_entry_index = ~0;
+ pae->collision_head_ae_index = ~0;
pae->colliding_rules = NULL;
}
@@ -900,40 +864,25 @@ deactivate_applied_ace_hash_entry(acl_main_t *am,
acl_plugin_print_pae(am->vlib_main, old_index, pae);
}
- if (pae->prev_applied_entry_index != ~0) {
- DBG("UNAPPLY = index %d has prev_applied_entry_index %d", old_index, pae->prev_applied_entry_index);
- applied_hash_ace_entry_t *prev_pae = vec_elt_at_index((*applied_hash_aces), pae->prev_applied_entry_index);
- ASSERT(prev_pae->next_applied_entry_index == old_index);
- prev_pae->next_applied_entry_index = pae->next_applied_entry_index;
+ if (pae->collision_head_ae_index != old_index) {
+ DBG("UNAPPLY = index %d has collision head %d", old_index, pae->collision_head_ae_index);
u32 head_index = find_head_applied_ace_index(applied_hash_aces, old_index);
ASSERT(head_index != ~0);
- applied_hash_ace_entry_t *head_pae = vec_elt_at_index((*applied_hash_aces), head_index);
del_colliding_rule(applied_hash_aces, head_index, old_index);
- if (pae->next_applied_entry_index == ~0) {
- /* it was a last entry we removed, update the pointer on the first one */
- ASSERT(head_pae->tail_applied_entry_index == old_index);
- head_pae->tail_applied_entry_index = pae->prev_applied_entry_index;
- } else {
- applied_hash_ace_entry_t *next_pae = vec_elt_at_index((*applied_hash_aces), pae->next_applied_entry_index);
- next_pae->prev_applied_entry_index = pae->prev_applied_entry_index;
- }
} else {
/* It was the first entry. We need either to reset the hash entry or delete it */
/* delete our entry from the collision vector first */
del_colliding_rule(applied_hash_aces, old_index, old_index);
- if (pae->next_applied_entry_index != ~0) {
- /* the next element becomes the new first one, so needs the tail pointer to be set */
- applied_hash_ace_entry_t *next_pae = vec_elt_at_index((*applied_hash_aces), pae->next_applied_entry_index);
- ASSERT(pae->tail_applied_entry_index != ~0);
- next_pae->tail_applied_entry_index = pae->tail_applied_entry_index;
+ if (vec_len(pae->colliding_rules) > 0) {
+ u32 next_pae_index = pae->colliding_rules[0].applied_entry_index;
+ applied_hash_ace_entry_t *next_pae = vec_elt_at_index((*applied_hash_aces), next_pae_index);
/* Remove ourselves and transfer the ownership of the colliding rules vector */
next_pae->colliding_rules = pae->colliding_rules;
- /* unlink from the next element */
- next_pae->prev_applied_entry_index = ~0;
+ set_collision_head_ae_index(applied_hash_aces, next_pae->colliding_rules, next_pae_index);
add_del_hashtable_entry(am, lc_index,
- applied_hash_aces, pae->next_applied_entry_index, 1);
+ applied_hash_aces, next_pae_index, 1);
} else {
/* no next entry, so just delete the entry in the hash table */
add_del_hashtable_entry(am, lc_index,
@@ -944,9 +893,7 @@ deactivate_applied_ace_hash_entry(acl_main_t *am,
release_mask_type_index(am, pae->mask_type_index);
/* invalidate the old entry */
pae->mask_type_index = ~0;
- pae->prev_applied_entry_index = ~0;
- pae->next_applied_entry_index = ~0;
- pae->tail_applied_entry_index = ~0;
+ pae->collision_head_ae_index = ~0;
/* always has to be 0 */
pae->colliding_rules = NULL;
}
@@ -1334,11 +1281,10 @@ static void
acl_plugin_print_pae (vlib_main_t * vm, int j, applied_hash_ace_entry_t * pae)
{
vlib_cli_output (vm,
- " %4d: acl %d rule %d action %d bitmask-ready rule %d mask type index: %d colliding_rules: %d next %d prev %d tail %d hitcount %lld acl_pos: %d",
+ " %4d: acl %d rule %d action %d bitmask-ready rule %d mask type index: %d colliding_rules: %d collision_head_ae_idx %d hitcount %lld acl_pos: %d",
j, pae->acl_index, pae->ace_index, pae->action,
- pae->hash_ace_info_index, pae->mask_type_index, vec_len(pae->colliding_rules), pae->next_applied_entry_index,
- pae->prev_applied_entry_index,
- pae->tail_applied_entry_index, pae->hitcount, pae->acl_position);
+ pae->hash_ace_info_index, pae->mask_type_index, vec_len(pae->colliding_rules), pae->collision_head_ae_index,
+ pae->hitcount, pae->acl_position);
int jj;
for(jj=0; jj<vec_len(pae->colliding_rules); jj++)
acl_plugin_print_colliding_rule(vm, jj, vec_elt_at_index(pae->colliding_rules, jj));
diff --git a/src/plugins/acl/hash_lookup_types.h b/src/plugins/acl/hash_lookup_types.h
index 3efcf4e372c..63b92455325 100644
--- a/src/plugins/acl/hash_lookup_types.h
+++ b/src/plugins/acl/hash_lookup_types.h
@@ -61,19 +61,9 @@ typedef struct {
/* applied mask type index */
u32 mask_type_index;
/*
- * in case of the same key having multiple entries,
- * this holds the index of the next entry.
+ * index of applied entry, which owns the colliding_rules vector
*/
- u32 next_applied_entry_index;
- /*
- * previous entry in the list of the chained ones,
- * if ~0 then this is entry in the hash.
- */
- u32 prev_applied_entry_index;
- /*
- * chain tail, if this is the first entry
- */
- u32 tail_applied_entry_index;
+ u32 collision_head_ae_index;
/*
* Collision rule vector for matching - set only on head entry
*/