19 #include <netinet/in.h> 43 return applied_hash_aces;
50 DBG(
"HASH ADD/DEL: %016llx %016llx %016llx %016llx %016llx %016llx %016llx add %d",
89 for (i = 0; i < 2; i++)
104 for (i=0; i<6; i++) {
168 return clib_host_to_net_u32((clib_net_to_host_u32(mask) << numshifts) & 0xFFFFFFFF);
175 int shifts_per_relax[2][4] = { { 6, 5, 4, 2 }, { 3, 2, 1, 1 } };
177 int *shifts = shifts_per_relax[relax2];
178 if(ip4_mask->
as_u32 == 0xffffffff)
179 ip4_mask->
as_u32 = clib_host_to_net_u32((clib_net_to_host_u32(ip4_mask->
as_u32) << shifts[0])&0xFFFFFFFF);
193 if (ip6_mask->as_u64[0] == 0xffffffffffffffffULL) {
194 if (ip6_mask->as_u64[1] == 0xffffffffffffffffULL) {
196 ip6_mask->as_u64[1] = 0;
197 }
else if (ip6_mask->as_u64[1] == 0) {
199 ip6_mask->as_u64[0] = clib_host_to_net_u64(0xffffffffffffff00ULL);
208 int counter_s = 0, counter_d = 0;
228 const int deltaThreshold = 4;
230 int delta = counter_s - counter_d;
231 if (-delta > deltaThreshold) {
237 }
else if (delta > deltaThreshold) {
255 DBG(
"TM-relaxing-ERROR");
258 DBG(
"TM-relaxing-end");
268 if(memcmp(&mte->mask, mask, sizeof(*mask)) == 0)
269 return (mte - am->ace_mask_type_pool);
280 if(~0 == mask_type_index) {
291 ASSERT(mask_type_index < 32768);
295 DBG0(
"ASSIGN MTE index %d new refcount %d", mask_type_index, mte->
refcount);
296 return mask_type_index;
302 DBG0(
"LOCK MTE index %d", mask_type_index);
305 DBG0(
"LOCK MTE index %d new refcount %d", mask_type_index, mte->
refcount);
312 DBG0(
"RELEAS MTE index %d", mask_type_index);
315 DBG0(
"RELEAS MTE index %d new refcount %d", mask_type_index, mte->
refcount);
327 u32 mask_type_index = ~0;
328 u32 for_mask_type_index = ~0;
336 if (
vec_len(*hash_applied_mask_info_vec) > 0) {
337 for(order_index =
vec_len((*hash_applied_mask_info_vec)) -1; order_index >= 0; order_index--) {
349 if(~0 == mask_type_index) {
351 DBG(
"TM-assigning mask type index-new one");
358 int spot =
vec_len((*hash_applied_mask_info_vec));
371 ASSERT(mask_type_index < 32768);
374 DBG0(
"TM-ASSIGN MTE index %d new refcount %d", mask_type_index, mte->
refcount);
375 return mask_type_index;
398 *pkey++ = *pmatch++ & *pmask++;
399 *pkey++ = *pmatch++ & *pmask++;
400 *pkey++ = *pmatch++ & *pmask++;
401 *pkey++ = *pmatch++ & *pmask++;
402 *pkey++ = *pmatch++ & *pmask++;
403 *pkey++ = *pmatch++ & *pmask++;
408 kv_val->applied_entry_index = new_index;
427 applied_hash_aces,
u32 lc_index)
429 DBG0(
"remake applied hash mask info lc_index %d", lc_index);
435 for (i = 0; i <
vec_len ((*applied_hash_aces)); i++)
441 u32 new_pointer =
vec_len (new_hash_applied_mask_info_vec);
443 for (search = 0; search <
vec_len (new_hash_applied_mask_info_vec);
451 vec_validate ((new_hash_applied_mask_info_vec), search);
453 if (search == new_pointer)
455 DBG0(
"remaking index %d", search);
474 vec_free ((*hash_applied_mask_info_vec));
475 (*hash_applied_mask_info_vec) = new_hash_applied_mask_info_vec;
480 u32 applied_entry_index)
484 while (i < _vec_len ((*pvec)))
492 DBG0(
"vec_del_collision_rule deleting one at index %d", i);
507 u32 head_index,
u32 applied_entry_index)
509 DBG0(
"DEL COLLIDING RULE: head_index %d applied index %d", head_index, applied_entry_index);
527 u32 head_index,
u32 applied_entry_index)
533 DBG0(
"ADD COLLIDING RULE: head_index %d applied index %d", head_index, applied_entry_index);
558 DBG(
"activate_applied_ace_hash_entry lc_index %d new_index %d", lc_index, new_index);
562 DBG(
"APPLY ADD KY: %016llx %016llx %016llx %016llx %016llx %016llx",
568 int res = BV (clib_bihash_search) (&am->
acl_lookup_hash, &kv, &result);
573 ASSERT(first_index != ~0);
576 DBG(
"A key already exists, with applied entry index: %d", first_index);
597 clib_error(
"ACL plugin failed to allocate lookup heap of %U bytes",
668 DBG0(
"HASH ACL apply: lc_index %d acl %d", lc_index, acl_index);
683 int base_offset =
vec_len(*applied_hash_aces);
694 clib_warning(
"BUG: trying to apply twice acl_index %d on lc_index %d, according to lc",
695 acl_index, lc_index);
699 u32 index2 =
vec_search((*hash_acl_applied_lc_index), lc_index);
701 clib_warning(
"BUG: trying to apply twice acl_index %d on lc_index %d, according to hash h-acl info",
702 acl_index, lc_index);
705 vec_add1((*hash_acl_applied_lc_index), lc_index);
722 int old_vec_len =
vec_len(*applied_hash_aces);
724 _vec_len((*applied_hash_aces)) = old_vec_len;
736 u32 new_index = base_offset +
i;
782 u32 old_index,
u32 new_index)
794 clib_warning(
"Moving pae from %d to %d", old_index, new_index);
801 applied_hash_aces, new_index, 1);
824 clib_warning(
"Head pae at index %d after adjustment", head_index);
840 DBG(
"UNAPPLY DEACTIVATE: lc_index %d applied index %d", lc_index, old_index);
842 clib_warning(
"Deactivating pae at index %d", old_index);
864 applied_hash_aces, next_pae_index, 1);
868 applied_hash_aces, old_index, 0);
871 DBG0(
"Releasing mask type index %d for pae index %d on lc_index %d", pae->
mask_type_index, old_index, lc_index);
886 DBG0(
"HASH ACL unapply: lc_index %d acl %d", lc_index, acl_index);
903 clib_warning(
"BUG: trying to unapply unapplied acl_index %d on lc_index %d, according to lc",
904 acl_index, lc_index);
909 u32 index2 =
vec_search((*hash_acl_applied_lc_index), lc_index);
911 clib_warning(
"BUG: trying to unapply twice acl_index %d on lc_index %d, according to h-acl info",
912 acl_index, lc_index);
915 vec_del1((*hash_acl_applied_lc_index), index2);
919 for(i=0; i <
vec_len((*applied_hash_aces)); i++) {
921 DBG(
"Found applied ACL#%d at applied index %d", acl_index, i);
925 if (
vec_len((*applied_hash_aces)) <= i) {
926 DBG(
"Did not find applied ACL#%d at lc_index %d", acl_index, lc_index);
934 int tail_len =
vec_len((*applied_hash_aces)) - tail_offset;
935 DBG(
"base_offset: %d, tail_offset: %d, tail_len: %d", base_offset, tail_offset, tail_len);
939 applied_hash_aces, base_offset + i);
941 for(i=0; i < tail_len; i ++) {
944 DBG0(
"UNAPPLY MOVE: lc_index %d, applied index %d -> %d", lc_index, tail_offset+i, base_offset + i);
952 if (
vec_len((*applied_hash_aces)) == 0) {
974 int start_index =
vec_search((*applied_acls), acl_index);
976 DBG0(
"Start index for acl %d in lc_index %d is %d", acl_index, lc_index, start_index);
984 for(i =
vec_len(*applied_acls) - 1; i > start_index; i--) {
987 for(i = start_index; i <
vec_len(*applied_acls); i++) {
1003 int i, byte, bit, bitnum;
1006 for (i = 0; i < width; i++)
1008 bitnum = (7 - (i & 7));
1011 a->
as_u8[byte] |= bit;
1025 if (port_first == port_last) {
1062 if (r->
proto != 0) {
1088 u64 *pmask = (
u64 *)mask;
1091 for(j=0; j<6; j++) {
1092 pmatch[j] = pmatch[j] & pmask[j];
1109 DBG(
"HASH ACL add : %d", acl_index);
1126 for(i=0; i <
vec_len(acl_rules); i++) {
1157 DBG0(
"HASH ACL delete : %d", acl_index);
1172 u32 *lc_list_copy = 0;
1213 vlib_cli_output(vm,
" %3d: %016llx %016llx %016llx %016llx %016llx %016llx refcount %d",
1214 mte - am->ace_mask_type_pool,
1215 mte->mask.kv_40_8.key[0], mte->mask.kv_40_8.key[1], mte->mask.kv_40_8.key[2],
1216 mte->mask.kv_40_8.key[3], mte->mask.kv_40_8.key[4], mte->mask.kv_40_8.value, mte->refcount);
1231 if ((acl_index != ~0) && (acl_index !=
i))
1244 " %4d: %016llx %016llx %016llx %016llx %016llx %016llx base mask index %d acl %d rule %d action %d\n",
1245 j, m[0], m[1], m[2], m[3], m[4], m[5],
1255 " %4d: acl %d ace %d acl pos %d pae index: %d",
1263 " %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",
1276 " %4d: mask type index %d first rule index %d num_entries %d max_collisions %d",
1291 if ((lc_index != ~0) && (lc_index != lci))
1361 (clib_net_to_host_u64 (mask_addr->as_u64[0]) <
1362 clib_net_to_host_u64 (min_addr->as_u64[0]))
1364 ((clib_net_to_host_u64 (mask_addr->as_u64[0]) ==
1365 clib_net_to_host_u64 (min_addr->as_u64[0]))
1366 && (clib_net_to_host_u64 (mask_addr->as_u64[1]) <
1367 clib_net_to_host_u64 (min_addr->as_u64[1])));
1370 min_addr->as_u64[0] = mask_addr->as_u64[0];
1371 min_addr->as_u64[1] = mask_addr->as_u64[1];
1379 (clib_net_to_host_u64 (mask_addr->as_u64[0]) >
1380 clib_net_to_host_u64 (max_addr->as_u64[0]))
1382 ((clib_net_to_host_u64 (mask_addr->as_u64[0]) ==
1383 clib_net_to_host_u64 (max_addr->as_u64[0]))
1384 && (clib_net_to_host_u64 (mask_addr->as_u64[1]) >
1385 clib_net_to_host_u64 (max_addr->as_u64[1])));
1388 max_addr->as_u64[0] = mask_addr->as_u64[0];
1389 max_addr->as_u64[1] = mask_addr->as_u64[1];
1397 (clib_net_to_host_u32 (mask_addr->
as_u32) <
1398 clib_net_to_host_u32 (min_addr->
as_u32));
1407 (clib_net_to_host_u32 (mask_addr->
as_u32) >
1408 clib_net_to_host_u32 (max_addr->
as_u32));
1426 DBG(
"TM-split_partition - first_entry:%d", first_index);
1429 fa_5tuple_t the_min_tuple, *min_tuple = &the_min_tuple;
1430 fa_5tuple_t the_max_tuple, *max_tuple = &the_max_tuple;
1435 clib_memset(&the_min_tuple, 0,
sizeof(the_min_tuple));
1436 clib_memset(&the_max_tuple, 0,
sizeof(the_max_tuple));
1441 for(i=0; i<collisions; i++){
1443 pae =
vec_elt_at_index((*applied_hash_aces), colliding_rules[i].applied_entry_index);
1446 DBG(
"TM-collision: base_ace:%d (ace_mask:%d, first_collision_mask:%d)",
1496 int best_dim=-1, best_delta=0, delta=0;
1507 if(delta > best_delta){
1522 if(delta > best_delta){
1529 if(delta > best_delta){
1536 if(delta > best_delta){
1543 if(delta > best_delta){
1551 shifting = (best_delta)/2;
1554 clib_host_to_net_u32((clib_net_to_host_u32(max_tuple->
ip4_addr[0].
as_u32) << (shifting))&0xFFFFFFFF);
1558 shifting = (best_delta)/2;
1572 clib_host_to_net_u32((clib_net_to_host_u32(max_tuple->
ip4_addr[1].
as_u32) << (shifting))&0xFFFFFFFF);
1593 for (search=0; search <
vec_len((*hash_applied_mask_info_vec)); search++){
1606 DBG(
"TM-split_partition - mask type index-assigned!! -> %d", new_mask_type_index);
1608 if(coll_mask_type_index == new_mask_type_index){
1615 DBG(
"TM-Populate new partition");
1616 u32 r_ace_index = first_index;
1617 int repopulate_count = 0;
1620 collisions =
vec_len(temp_colliding_rules);
1622 for(i=0; i<collisions; i++){
1628 DBG(
"TM-Population-collision: base_ace:%d (ace_mask:%d, first_collision_mask:%d)",
1640 DBG(
"TM-new partition can insert -> applied_ace:%d", r_ace_index);
1648 if (++repopulate_count > 1)
1656 DBG(
"TM-Populate new partition-END");
1657 DBG(
"TM-split_partition - END");
static void move_applied_ace_hash_entry(acl_main_t *am, u32 lc_index, applied_hash_ace_entry_t **applied_hash_aces, u32 old_index, u32 new_index)
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
static void ensure_ip4_max_addr(ip4_address_t *max_addr, ip4_address_t *mask_addr)
static void deactivate_applied_ace_hash_entry(acl_main_t *am, u32 lc_index, applied_hash_ace_entry_t **applied_hash_aces, u32 old_index)
void acl_plugin_show_tables_mask_type(void)
static void ensure_ip6_min_addr(ip6_address_t *min_addr, ip6_address_t *mask_addr)
static void * hash_acl_set_heap(acl_main_t *am)
void hash_acl_unapply(acl_main_t *am, u32 lc_index, int acl_index)
void acl_plugin_hash_acl_set_trace_heap(int on)
void acl_plugin_show_tables_applied_info(u32 lc_index)
void hash_acl_reapply(acl_main_t *am, u32 lc_index, int acl_index)
#define clib_error(format, args...)
#define clib_memcpy_fast(a, b, c)
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
static void add_colliding_rule(acl_main_t *am, applied_hash_ace_entry_t **applied_hash_aces, u32 head_index, u32 applied_entry_index)
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
static u32 activate_applied_ace_hash_entry(acl_main_t *am, u32 lc_index, applied_hash_ace_entry_t **applied_hash_aces, u32 new_index)
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
static u32 find_head_applied_ace_index(applied_hash_ace_entry_t **applied_hash_aces, u32 curr_index)
void hash_acl_add(acl_main_t *am, int acl_index)
u32 ** lc_index_vec_by_acl
static void ensure_ip6_max_addr(ip6_address_t *max_addr, ip6_address_t *mask_addr)
u16 dst_port_or_code_last
static void make_port_mask(u16 *portmask, u16 port_first, u16 port_last)
#define ACL_HASH_LOOKUP_DEBUG
#define pool_foreach(VAR, POOL, BODY)
Iterate through pool.
int clib_bihash_add_del(clib_bihash *h, clib_bihash_kv *add_v, int is_add)
Add or delete a (key,value) pair from a bi-hash table.
static void assign_mask_type_index_to_pae(acl_main_t *am, u32 lc_index, int is_ip6, applied_hash_ace_entry_t *pae)
#define vec_new(T, N)
Create new vector of given type and length (unspecified alignment, no header).
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
static void lock_mask_type_index(acl_main_t *am, u32 mask_type_index)
#define vec_resize(V, N)
Resize a vector (no header, unspecified alignment) Add N elements to end of given vector V...
#define vec_search(v, E)
Search a vector for the index of the entry that matches.
static void release_mask_type_index(acl_main_t *am, u32 mask_type_index)
void hash_acl_apply(acl_main_t *am, u32 lc_index, int acl_index, u32 acl_position)
static u32 assign_mask_type_index(acl_main_t *am, fa_5tuple_t *mask)
int hash_acl_exists(acl_main_t *am, int acl_index)
static void add_del_hashtable_entry(acl_main_t *am, u32 lc_index, applied_hash_ace_entry_t **applied_hash_aces, u32 index, int is_add)
collision_match_rule_t * colliding_rules
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
static void ip4_address_mask_from_width(ip4_address_t *a, u32 width)
u16 dst_port_or_code_first
hash_applied_mask_info_t ** hash_applied_mask_info_vec_by_lc_index
DLMALLOC_EXPORT void mspace_disable_expand(mspace msp)
hash_acl_info_t * hash_acl_infos
#define pool_put(P, E)
Free an object E in pool P.
#define vec_dup(V)
Return copy of vector (no header, no alignment)
static void make_mask_and_match_from_rule(fa_5tuple_t *mask, acl_rule_t *r, hash_ace_info_t *hi)
#define vec_del1(v, i)
Delete the element at index I.
static void check_collision_count_and_maybe_split(acl_main_t *am, u32 lc_index, int is_ip6, u32 first_index)
clib_bihash_48_8_t acl_lookup_hash
void show_hash_acl_hash(vlib_main_t *vm, acl_main_t *am, u32 verbose)
static u32 shift_ip4_if(u32 mask, u32 thresh, int numshifts, u32 else_val)
void acl_plugin_hash_acl_set_validate_heap(int on)
void clib_bihash_init(clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
initialize a bounded index extensible hash table
u16 src_port_or_type_first
void acl_plugin_show_tables_bihash(u32 show_bihash_verbose)
#define pool_get_aligned(P, E, A)
Allocate an object E from a pool P with alignment A.
static void vec_del_collision_rule(collision_match_rule_t **pvec, u32 applied_entry_index)
static void split_partition(acl_main_t *am, u32 first_index, u32 lc_index, int is_ip6)
sll srl srl sll sra u16x4 i
applied_hash_acl_info_t * applied_hash_acl_info_by_lc_index
#define vec_free(V)
Free vector's memory (no header).
static void make_ip4_address_mask(ip4_address_t *addr, u8 prefix_len)
int acl_lookup_hash_initialized
static void * clib_mem_set_heap(void *heap)
void hash_acl_delete(acl_main_t *am, int acl_index)
#define clib_warning(format, args...)
static int count_bits(u64 word)
applied_hash_ace_entry_t ** hash_entry_vec_by_lc_index
static u8 first_mask_contains_second_mask(int is_ip6, fa_5tuple_t *mask1, fa_5tuple_t *mask2)
uword hash_lookup_hash_memory
int tuple_merge_split_threshold
static void relax_ip6_addr(ip6_address_t *ip6_mask, int relax2)
static void acl_plugin_print_colliding_rule(vlib_main_t *vm, int j, collision_match_rule_t *cr)
u32 hash_lookup_hash_buckets
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
static void ensure_ip4_min_addr(ip4_address_t *min_addr, ip4_address_t *mask_addr)
#define vec_delete(V, N, M)
Delete N elements starting at element M.
u16 src_port_or_type_last
void * mheap_alloc_with_lock(void *memory, uword size, int locked)
static void acl_plugin_print_pae(vlib_main_t *vm, int j, applied_hash_ace_entry_t *pae)
u32 collision_head_ae_index
static void acl_plugin_print_applied_mask_info(vlib_main_t *vm, int j, hash_applied_mask_info_t *mi)
static applied_hash_ace_entry_t ** get_applied_hash_aces(acl_main_t *am, u32 lc_index)
ace_mask_type_entry_t * ace_mask_type_pool
static u32 find_mask_type_index(acl_main_t *am, fa_5tuple_t *mask)
static void fill_applied_hash_ace_kv(acl_main_t *am, applied_hash_ace_entry_t **applied_hash_aces, u32 lc_index, u32 new_index, clib_bihash_kv_48_8_t *kv)
acl_lookup_context_t * acl_lookup_contexts
uword hash_lookup_mheap_size
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static void relax_ip4_addr(ip4_address_t *ip4_mask, int relax2)
static void hashtable_add_del(acl_main_t *am, clib_bihash_kv_48_8_t *kv, int is_add)
static void ip6_address_mask_from_width(ip6_address_t *a, u32 width)
static u32 tm_assign_mask_type_index(acl_main_t *am, fa_5tuple_t *mask, int is_ip6, u32 lc_index)
#define vec_foreach(var, vec)
Vector iterator.
static void del_colliding_rule(applied_hash_ace_entry_t **applied_hash_aces, u32 head_index, u32 applied_entry_index)
static void relax_tuple(fa_5tuple_t *mask, int is_ip6, int relax2)
ip4_address_t ip4_addr[2]
static void remake_hash_applied_mask_info_vec(acl_main_t *am, applied_hash_ace_entry_t **applied_hash_aces, u32 lc_index)
static void make_ip6_address_mask(ip6_address_t *addr, u8 prefix_len)
#define CLIB_CACHE_LINE_BYTES
static void set_collision_head_ae_index(applied_hash_ace_entry_t **applied_hash_aces, collision_match_rule_t *colliding_rules, u32 new_index)
void acl_plugin_show_tables_acl_hash_info(u32 acl_index)
ip6_address_t ip6_addr[2]
foreach_fa_cleaner_counter vlib_main_t * vlib_main