src/plugins/acl/hash_lookup.c

   1 /*
   2  *------------------------------------------------------------------
   3  * Copyright (c) 2017 Cisco and/or its affiliates.
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  *------------------------------------------------------------------
  16  */
  17
  18 #include <stddef.h>
  19 #include <netinet/in.h>
  20
  21 #include <vlibapi/api.h>
  22 #include <vlibmemory/api.h>
  23
  24 #include <vlib/vlib.h>
  25 #include <vnet/vnet.h>
  26 #include <vnet/pg/pg.h>
  27 #include <vppinfra/error.h>
  28 #include <vnet/plugin/plugin.h>
  29 #include <acl/acl.h>
  30 #include <vppinfra/bihash_48_8.h>
  31
  32 #include "hash_lookup.h"
  33 #include "hash_lookup_private.h"
  34
  35
  36 always_inline applied_hash_ace_entry_t **get_applied_hash_aces(acl_main_t *am, u32 lc_index)
  37 {
  38   applied_hash_ace_entry_t **applied_hash_aces = vec_elt_at_index(am->hash_entry_vec_by_lc_index, lc_index);
  39
  40 /*is_input ? vec_elt_at_index(am->input_hash_entry_vec_by_sw_if_index, sw_if_index)
  41                                                           : vec_elt_at_index(am->output_hash_entry_vec_by_sw_if_index, sw_if_index);
  42 */
  43   return applied_hash_aces;
  44 }
  45
  46
  47 static void
  48 hashtable_add_del(acl_main_t *am, clib_bihash_kv_48_8_t *kv, int is_add)
  49 {
  50     DBG("HASH ADD/DEL: %016llx %016llx %016llx %016llx %016llx %016llx %016llx add %d",
  51                         kv->key[0], kv->key[1], kv->key[2],
  52                         kv->key[3], kv->key[4], kv->key[5], kv->value, is_add);
  53     BV (clib_bihash_add_del) (&am->acl_lookup_hash, kv, is_add);
  54 }
  55
  56 static void
  57 fill_applied_hash_ace_kv(acl_main_t *am,
  58                             applied_hash_ace_entry_t **applied_hash_aces,
  59                             u32 lc_index,
  60                             u32 new_index, clib_bihash_kv_48_8_t *kv)
  61 {
  62   fa_5tuple_t *kv_key = (fa_5tuple_t *)kv->key;
  63   hash_acl_lookup_value_t *kv_val = (hash_acl_lookup_value_t *)&kv->value;
  64   applied_hash_ace_entry_t *pae = vec_elt_at_index((*applied_hash_aces), new_index);
  65   hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, pae->acl_index);
  66
  67   memcpy(kv_key, &(vec_elt_at_index(ha->rules, pae->hash_ace_info_index)->match), sizeof(*kv_key));
  68   /* initialize the sw_if_index and direction */
  69   kv_key->pkt.lc_index = lc_index;
  70   kv_val->as_u64 = 0;
  71   kv_val->applied_entry_index = new_index;
  72   kv_val->need_portrange_check = vec_elt_at_index(ha->rules, pae->hash_ace_info_index)->src_portrange_not_powerof2 ||
  73                                    vec_elt_at_index(ha->rules, pae->hash_ace_info_index)->dst_portrange_not_powerof2;
  74   /* by default assume all values are shadowed -> check all mask types */
  75   kv_val->shadowed = 1;
  76 }
  77
  78 static void
  79 add_del_hashtable_entry(acl_main_t *am,
  80                             u32 lc_index,
  81                             applied_hash_ace_entry_t **applied_hash_aces,
  82                             u32 index, int is_add)
  83 {
  84   clib_bihash_kv_48_8_t kv;
  85
  86   fill_applied_hash_ace_kv(am, applied_hash_aces, lc_index, index, &kv);
  87   hashtable_add_del(am, &kv, is_add);
  88 }
  89
  90
  91
  92 static void
  93 activate_applied_ace_hash_entry(acl_main_t *am,
  94                             u32 lc_index,
  95                             applied_hash_ace_entry_t **applied_hash_aces,
  96                             u32 new_index)
  97 {
  98   clib_bihash_kv_48_8_t kv;
  99   ASSERT(new_index != ~0);
 100   applied_hash_ace_entry_t *pae = vec_elt_at_index((*applied_hash_aces), new_index);
 101   DBG("activate_applied_ace_hash_entry lc_index %d new_index %d", lc_index, new_index);
 102
 103   fill_applied_hash_ace_kv(am, applied_hash_aces, lc_index, new_index, &kv);
 104
 105   DBG("APPLY ADD KY: %016llx %016llx %016llx %016llx %016llx %016llx",
 106                         kv.key[0], kv.key[1], kv.key[2],
 107                         kv.key[3], kv.key[4], kv.key[5]);
 108
 109   clib_bihash_kv_48_8_t result;
 110   hash_acl_lookup_value_t *result_val = (hash_acl_lookup_value_t *)&result.value;
 111   int res = BV (clib_bihash_search) (&am->acl_lookup_hash, &kv, &result);
 112   ASSERT(new_index != ~0);
 113   ASSERT(new_index < vec_len((*applied_hash_aces)));
 114   if (res == 0) {
 115     /* There already exists an entry or more. Append at the end. */
 116     u32 first_index = result_val->applied_entry_index;
 117     ASSERT(first_index != ~0);
 118     DBG("A key already exists, with applied entry index: %d", first_index);
 119     applied_hash_ace_entry_t *first_pae = vec_elt_at_index((*applied_hash_aces), first_index);
 120     u32 last_index = first_pae->tail_applied_entry_index;
 121     ASSERT(last_index != ~0);
 122     applied_hash_ace_entry_t *last_pae = vec_elt_at_index((*applied_hash_aces), last_index);
 123     DBG("...advance to chained entry index: %d", last_index);
 124     /* link ourseves in */
 125     last_pae->next_applied_entry_index = new_index;
 126     pae->prev_applied_entry_index = last_index;
 127     /* adjust the pointer to the new tail */
 128     first_pae->tail_applied_entry_index = new_index;
 129   } else {
 130     /* It's the very first entry */
 131     hashtable_add_del(am, &kv, 1);
 132     ASSERT(new_index != ~0);
 133     pae->tail_applied_entry_index = new_index;
 134   }
 135 }
 136
 137 static void
 138 applied_hash_entries_analyze(acl_main_t *am, applied_hash_ace_entry_t **applied_hash_aces)
 139 {
 140   /*
 141    * Go over the rules and check which ones are shadowed and which aren't.
 142    * Naive approach: try to match the match value from every ACE as if it
 143    * was a live packet, and see if the resulting match happens earlier in the list.
 144    * if it does not match or it is later in the ACL - then the entry is not shadowed.
 145    *
 146    * This approach fails, an example:
 147    *   deny tcp 2001:db8::/32 2001:db8::/32
 148    *   permit ip 2001:db8::1/128 2001:db8::2/128
 149    */
 150 }
 151
 152 static void *
 153 hash_acl_set_heap(acl_main_t *am)
 154 {
 155   if (0 == am->hash_lookup_mheap) {
 156     am->hash_lookup_mheap = mheap_alloc (0 /* use VM */ , am->hash_lookup_mheap_size);
 157     mheap_t *h = mheap_header (am->hash_lookup_mheap);
 158     h->flags |= MHEAP_FLAG_THREAD_SAFE;
 159   }
 160   void *oldheap = clib_mem_set_heap(am->hash_lookup_mheap);
 161   return oldheap;
 162 }
 163
 164 void
 165 acl_plugin_hash_acl_set_validate_heap(int on)
 166 {
 167   acl_main_t *am = &acl_main;
 168   clib_mem_set_heap(hash_acl_set_heap(am));
 169   mheap_t *h = mheap_header (am->hash_lookup_mheap);
 170   if (on) {
 171     h->flags |= MHEAP_FLAG_VALIDATE;
 172     h->flags &= ~MHEAP_FLAG_SMALL_OBJECT_CACHE;
 173     mheap_validate(h);
 174   } else {
 175     h->flags &= ~MHEAP_FLAG_VALIDATE;
 176     h->flags |= MHEAP_FLAG_SMALL_OBJECT_CACHE;
 177   }
 178 }
 179
 180 void
 181 acl_plugin_hash_acl_set_trace_heap(int on)
 182 {
 183   acl_main_t *am = &acl_main;
 184   clib_mem_set_heap(hash_acl_set_heap(am));
 185   mheap_t *h = mheap_header (am->hash_lookup_mheap);
 186   if (on) {
 187     h->flags |= MHEAP_FLAG_TRACE;
 188   } else {
 189     h->flags &= ~MHEAP_FLAG_TRACE;
 190   }
 191 }
 192
 193 void
 194 hash_acl_apply(acl_main_t *am, u32 lc_index, int acl_index, u32 acl_position)
 195 {
 196   int i;
 197
 198   DBG0("HASH ACL apply: lc_index %d acl %d", lc_index, acl_index);
 199   if (!am->acl_lookup_hash_initialized) {
 200     BV (clib_bihash_init) (&am->acl_lookup_hash, "ACL plugin rule lookup bihash",
 201                            am->hash_lookup_hash_buckets, am->hash_lookup_hash_memory);
 202     am->acl_lookup_hash_initialized = 1;
 203   }
 204
 205   void *oldheap = hash_acl_set_heap(am);
 206   vec_validate(am->hash_entry_vec_by_lc_index, lc_index);
 207   vec_validate(am->hash_acl_infos, acl_index);
 208   applied_hash_ace_entry_t **applied_hash_aces = get_applied_hash_aces(am, lc_index);
 209
 210   hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, acl_index);
 211   u32 **hash_acl_applied_lc_index = &ha->lc_index_list;
 212
 213   int base_offset = vec_len(*applied_hash_aces);
 214
 215   /* Update the bitmap of the mask types with which the lookup
 216      needs to happen for the ACLs applied to this lc_index */
 217   applied_hash_acl_info_t **applied_hash_acls = &am->applied_hash_acl_info_by_lc_index;
 218   vec_validate((*applied_hash_acls), lc_index);
 219   applied_hash_acl_info_t *pal = vec_elt_at_index((*applied_hash_acls), lc_index);
 220
 221   /* ensure the list of applied hash acls is initialized and add this acl# to it */
 222   u32 index = vec_search(pal->applied_acls, acl_index);
 223   if (index != ~0) {
 224     clib_warning("BUG: trying to apply twice acl_index %d on lc_index %d, according to lc",
 225                  acl_index, lc_index);
 226     goto done;
 227   }
 228   vec_add1(pal->applied_acls, acl_index);
 229   u32 index2 = vec_search((*hash_acl_applied_lc_index), lc_index);
 230   if (index2 != ~0) {
 231     clib_warning("BUG: trying to apply twice acl_index %d on lc_index %d, according to hash h-acl info",
 232                  acl_index, lc_index);
 233     goto done;
 234   }
 235   vec_add1((*hash_acl_applied_lc_index), lc_index);
 236
 237   pal->mask_type_index_bitmap = clib_bitmap_or(pal->mask_type_index_bitmap,
 238                                      ha->mask_type_index_bitmap);
 239   /*
 240    * if the applied ACL is empty, the current code will cause a
 241    * different behavior compared to current linear search: an empty ACL will
 242    * simply fallthrough to the next ACL, or the default deny in the end.
 243    *
 244    * This is not a problem, because after vpp-dev discussion,
 245    * the consensus was it should not be possible to apply the non-existent
 246    * ACL, so the change adding this code also takes care of that.
 247    */
 248
 249   /* expand the applied aces vector by the necessary amount */
 250   vec_resize((*applied_hash_aces), vec_len(ha->rules));
 251
 252   /* add the rules from the ACL to the hash table for lookup and append to the vector*/
 253   for(i=0; i < vec_len(ha->rules); i++) {
 254     u32 new_index = base_offset + i;
 255     applied_hash_ace_entry_t *pae = vec_elt_at_index((*applied_hash_aces), new_index);
 256     pae->acl_index = acl_index;
 257     pae->ace_index = ha->rules[i].ace_index;
 258     pae->acl_position = acl_position;
 259     pae->action = ha->rules[i].action;
 260     pae->hitcount = 0;
 261     pae->hash_ace_info_index = i;
 262     /* we might link it in later */
 263     pae->next_applied_entry_index = ~0;
 264     pae->prev_applied_entry_index = ~0;
 265     pae->tail_applied_entry_index = ~0;
 266     activate_applied_ace_hash_entry(am, lc_index, applied_hash_aces, new_index);
 267   }
 268   applied_hash_entries_analyze(am, applied_hash_aces);
 269 done:
 270   clib_mem_set_heap (oldheap);
 271 }
 272
 273 static u32
 274 find_head_applied_ace_index(applied_hash_ace_entry_t **applied_hash_aces, u32 curr_index)
 275 {
 276   /*
 277    * find back the first entry. Inefficient so might need to be a bit cleverer
 278    * if this proves to be a problem..
 279    */
 280   u32 an_index = curr_index;
 281   ASSERT(an_index != ~0);
 282   applied_hash_ace_entry_t *head_pae = vec_elt_at_index((*applied_hash_aces), an_index);
 283   while(head_pae->prev_applied_entry_index != ~0) {
 284     an_index = head_pae->prev_applied_entry_index;
 285     ASSERT(an_index != ~0);
 286     head_pae = vec_elt_at_index((*applied_hash_aces), an_index);
 287   }
 288   return an_index;
 289 }
 290
 291 static void
 292 move_applied_ace_hash_entry(acl_main_t *am,
 293                             u32 lc_index,
 294                             applied_hash_ace_entry_t **applied_hash_aces,
 295                             u32 old_index, u32 new_index)
 296 {
 297   ASSERT(old_index != ~0);
 298   ASSERT(new_index != ~0);
 299   /* move the entry */
 300   *vec_elt_at_index((*applied_hash_aces), new_index) = *vec_elt_at_index((*applied_hash_aces), old_index);
 301
 302   /* update the linkage and hash table if necessary */
 303   applied_hash_ace_entry_t *pae = vec_elt_at_index((*applied_hash_aces), old_index);
 304
 305   if (pae->prev_applied_entry_index != ~0) {
 306     applied_hash_ace_entry_t *prev_pae = vec_elt_at_index((*applied_hash_aces), pae->prev_applied_entry_index);
 307     ASSERT(prev_pae->next_applied_entry_index == old_index);
 308     prev_pae->next_applied_entry_index = new_index;
 309   } else {
 310     /* first entry - so the hash points to it, update */
 311     add_del_hashtable_entry(am, lc_index,
 312                             applied_hash_aces, new_index, 1);
 313     ASSERT(pae->tail_applied_entry_index != ~0);
 314   }
 315   if (pae->next_applied_entry_index != ~0) {
 316     applied_hash_ace_entry_t *next_pae = vec_elt_at_index((*applied_hash_aces), pae->next_applied_entry_index);
 317     ASSERT(next_pae->prev_applied_entry_index == old_index);
 318     next_pae->prev_applied_entry_index = new_index;
 319   } else {
 320     /*
 321      * Moving the very last entry, so we need to update the tail pointer in the first one.
 322      */
 323     u32 head_index = find_head_applied_ace_index(applied_hash_aces, old_index);
 324     ASSERT(head_index != ~0);
 325     applied_hash_ace_entry_t *head_pae = vec_elt_at_index((*applied_hash_aces), head_index);
 326
 327     ASSERT(head_pae->tail_applied_entry_index == old_index);
 328     head_pae->tail_applied_entry_index = new_index;
 329   }
 330   /* invalidate the old entry */
 331   pae->prev_applied_entry_index = ~0;
 332   pae->next_applied_entry_index = ~0;
 333   pae->tail_applied_entry_index = ~0;
 334 }
 335
 336 static void
 337 deactivate_applied_ace_hash_entry(acl_main_t *am,
 338                             u32 lc_index,
 339                             applied_hash_ace_entry_t **applied_hash_aces,
 340                             u32 old_index)
 341 {
 342   applied_hash_ace_entry_t *pae = vec_elt_at_index((*applied_hash_aces), old_index);
 343   DBG("UNAPPLY DEACTIVATE: lc_index %d applied index %d", lc_index, old_index);
 344
 345   if (pae->prev_applied_entry_index != ~0) {
 346     DBG("UNAPPLY = index %d has prev_applied_entry_index %d", old_index, pae->prev_applied_entry_index);
 347     applied_hash_ace_entry_t *prev_pae = vec_elt_at_index((*applied_hash_aces), pae->prev_applied_entry_index);
 348     ASSERT(prev_pae->next_applied_entry_index == old_index);
 349     prev_pae->next_applied_entry_index = pae->next_applied_entry_index;
 350     if (pae->next_applied_entry_index == ~0) {
 351       /* it was a last entry we removed, update the pointer on the first one */
 352       u32 head_index = find_head_applied_ace_index(applied_hash_aces, old_index);
 353       DBG("UNAPPLY = index %d head index to update %d", old_index, head_index);
 354       ASSERT(head_index != ~0);
 355       applied_hash_ace_entry_t *head_pae = vec_elt_at_index((*applied_hash_aces), head_index);
 356
 357       ASSERT(head_pae->tail_applied_entry_index == old_index);
 358       head_pae->tail_applied_entry_index = pae->prev_applied_entry_index;
 359     } else {
 360       applied_hash_ace_entry_t *next_pae = vec_elt_at_index((*applied_hash_aces), pae->next_applied_entry_index);
 361       next_pae->prev_applied_entry_index = pae->prev_applied_entry_index;
 362     }
 363   } else {
 364     /* It was the first entry. We need either to reset the hash entry or delete it */
 365     if (pae->next_applied_entry_index != ~0) {
 366       /* the next element becomes the new first one, so needs the tail pointer to be set */
 367       applied_hash_ace_entry_t *next_pae = vec_elt_at_index((*applied_hash_aces), pae->next_applied_entry_index);
 368       ASSERT(pae->tail_applied_entry_index != ~0);
 369       next_pae->tail_applied_entry_index = pae->tail_applied_entry_index;
 370       DBG("Resetting the hash table entry from %d to %d, setting tail index to %d", old_index, pae->next_applied_entry_index, pae->tail_applied_entry_index);
 371       /* unlink from the next element */
 372       next_pae->prev_applied_entry_index = ~0;
 373       add_del_hashtable_entry(am, lc_index,
 374                               applied_hash_aces, pae->next_applied_entry_index, 1);
 375     } else {
 376       /* no next entry, so just delete the entry in the hash table */
 377       add_del_hashtable_entry(am, lc_index,
 378                               applied_hash_aces, old_index, 0);
 379     }
 380   }
 381   /* invalidate the old entry */
 382   pae->prev_applied_entry_index = ~0;
 383   pae->next_applied_entry_index = ~0;
 384   pae->tail_applied_entry_index = ~0;
 385 }
 386
 387
 388 static void
 389 hash_acl_build_applied_lookup_bitmap(acl_main_t *am, u32 lc_index)
 390 {
 391   int i;
 392   uword *new_lookup_bitmap = 0;
 393
 394   applied_hash_acl_info_t **applied_hash_acls = &am->applied_hash_acl_info_by_lc_index;
 395   vec_validate((*applied_hash_acls), lc_index);
 396   applied_hash_acl_info_t *pal = vec_elt_at_index((*applied_hash_acls), lc_index);
 397
 398   for(i=0; i < vec_len(pal->applied_acls); i++) {
 399     u32 a_acl_index = *vec_elt_at_index((pal->applied_acls), i);
 400     hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, a_acl_index);
 401     DBG("Update bitmask = %U or %U (acl_index %d)\n", format_bitmap_hex, new_lookup_bitmap,
 402           format_bitmap_hex, ha->mask_type_index_bitmap, a_acl_index);
 403     new_lookup_bitmap = clib_bitmap_or(new_lookup_bitmap,
 404                                        ha->mask_type_index_bitmap);
 405   }
 406   uword *old_lookup_bitmap = pal->mask_type_index_bitmap;
 407   pal->mask_type_index_bitmap = new_lookup_bitmap;
 408   clib_bitmap_free(old_lookup_bitmap);
 409 }
 410
 411 void
 412 hash_acl_unapply(acl_main_t *am, u32 lc_index, int acl_index)
 413 {
 414   int i;
 415
 416   DBG0("HASH ACL unapply: lc_index %d acl %d", lc_index, acl_index);
 417   applied_hash_acl_info_t **applied_hash_acls = &am->applied_hash_acl_info_by_lc_index;
 418   applied_hash_acl_info_t *pal = vec_elt_at_index((*applied_hash_acls), lc_index);
 419
 420   hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, acl_index);
 421   u32 **hash_acl_applied_lc_index = &ha->lc_index_list;
 422
 423   /* remove this acl# from the list of applied hash acls */
 424   u32 index = vec_search(pal->applied_acls, acl_index);
 425   if (index == ~0) {
 426     clib_warning("BUG: trying to unapply unapplied acl_index %d on lc_index %d, according to lc",
 427                  acl_index, lc_index);
 428     return;
 429   }
 430   vec_del1(pal->applied_acls, index);
 431
 432   u32 index2 = vec_search((*hash_acl_applied_lc_index), lc_index);
 433   if (index2 == ~0) {
 434     clib_warning("BUG: trying to unapply twice acl_index %d on lc_index %d, according to h-acl info",
 435                  acl_index, lc_index);
 436     return;
 437   }
 438   vec_del1((*hash_acl_applied_lc_index), index2);
 439
 440   applied_hash_ace_entry_t **applied_hash_aces = get_applied_hash_aces(am, lc_index);
 441
 442   for(i=0; i < vec_len((*applied_hash_aces)); i++) {
 443     if (vec_elt_at_index(*applied_hash_aces,i)->acl_index == acl_index) {
 444       DBG("Found applied ACL#%d at applied index %d", acl_index, i);
 445       break;
 446     }
 447   }
 448   if (vec_len((*applied_hash_aces)) <= i) {
 449     DBG("Did not find applied ACL#%d at lc_index %d", acl_index, lc_index);
 450     /* we went all the way without finding any entries. Probably a list was empty. */
 451     return;
 452   }
 453
 454   void *oldheap = hash_acl_set_heap(am);
 455   int base_offset = i;
 456   int tail_offset = base_offset + vec_len(ha->rules);
 457   int tail_len = vec_len((*applied_hash_aces)) - tail_offset;
 458   DBG("base_offset: %d, tail_offset: %d, tail_len: %d", base_offset, tail_offset, tail_len);
 459
 460   for(i=0; i < vec_len(ha->rules); i ++) {
 461     deactivate_applied_ace_hash_entry(am, lc_index,
 462                                       applied_hash_aces, base_offset + i);
 463   }
 464   for(i=0; i < tail_len; i ++) {
 465     /* move the entry at tail offset to base offset */
 466     /* that is, from (tail_offset+i) -> (base_offset+i) */
 467     DBG("UNAPPLY MOVE: lc_index %d, applied index %d -> %d", lc_index, tail_offset+i, base_offset + i);
 468     move_applied_ace_hash_entry(am, lc_index, applied_hash_aces, tail_offset + i, base_offset + i);
 469   }
 470   /* trim the end of the vector */
 471   _vec_len((*applied_hash_aces)) -= vec_len(ha->rules);
 472
 473   applied_hash_entries_analyze(am, applied_hash_aces);
 474
 475   /* After deletion we might not need some of the mask-types anymore... */
 476   hash_acl_build_applied_lookup_bitmap(am, lc_index);
 477   clib_mem_set_heap (oldheap);
 478 }
 479
 480 /*
 481  * Create the applied ACEs and update the hash table,
 482  * taking into account that the ACL may not be the last
 483  * in the vector of applied ACLs.
 484  *
 485  * For now, walk from the end of the vector and unapply the ACLs,
 486  * then apply the one in question and reapply the rest.
 487  */
 488
 489 void
 490 hash_acl_reapply(acl_main_t *am, u32 lc_index, int acl_index)
 491 {
 492   acl_lookup_context_t *acontext = pool_elt_at_index(am->acl_lookup_contexts, lc_index);
 493   u32 **applied_acls = &acontext->acl_indices;
 494   int i;
 495   int start_index = vec_search((*applied_acls), acl_index);
 496
 497   DBG0("Start index for acl %d in lc_index %d is %d", acl_index, lc_index, start_index);
 498   /*
 499    * This function is called after we find out the sw_if_index where ACL is applied.
 500    * If the by-sw_if_index vector does not have the ACL#, then it's a bug.
 501    */
 502   ASSERT(start_index < vec_len(*applied_acls));
 503
 504   /* unapply all the ACLs at the tail side, up to the current one */
 505   for(i = vec_len(*applied_acls) - 1; i > start_index; i--) {
 506     hash_acl_unapply(am, lc_index, *vec_elt_at_index(*applied_acls, i));
 507   }
 508   for(i = start_index; i < vec_len(*applied_acls); i++) {
 509     hash_acl_apply(am, lc_index, *vec_elt_at_index(*applied_acls, i), i);
 510   }
 511 }
 512
 513 static void
 514 make_address_mask(ip46_address_t *addr, u8 is_ipv6, u8 prefix_len)
 515 {
 516   if (is_ipv6) {
 517     ip6_address_mask_from_width(&addr->ip6, prefix_len);
 518   } else {
 519     /* FIXME: this may not be correct way */
 520     ip6_address_mask_from_width(&addr->ip6, prefix_len + 3*32);
 521     ip46_address_mask_ip4(addr);
 522   }
 523 }
 524
 525 static u8
 526 make_port_mask(u16 *portmask, u16 port_first, u16 port_last)
 527 {
 528   if (port_first == port_last) {
 529     *portmask = 0xffff;
 530     /* single port is representable by masked value */
 531     return 0;
 532   }
 533   if ((port_first == 0) && (port_last == 65535)) {
 534     *portmask = 0;
 535     /* wildcard port is representable by a masked value */
 536     return 0;
 537   }
 538
 539   /*
 540    * For now match all the ports, later
 541    * here might be a better optimization which would
 542    * pick out bitmaskable portranges.
 543    *
 544    * However, adding a new mask type potentially
 545    * adds a per-packet extra lookup, so the benefit is not clear.
 546    */
 547   *portmask = 0;
 548   /* This port range can't be represented via bitmask exactly. */
 549   return 1;
 550 }
 551
 552 static void
 553 make_mask_and_match_from_rule(fa_5tuple_t *mask, acl_rule_t *r, hash_ace_info_t *hi, int match_nonfirst_fragment)
 554 {
 555   memset(mask, 0, sizeof(*mask));
 556   memset(&hi->match, 0, sizeof(hi->match));
 557   hi->action = r->is_permit;
 558
 559   /* we will need to be matching based on lc_index and mask_type_index when applied */
 560   mask->pkt.lc_index = ~0;
 561   /* we will assign the match of mask_type_index later when we find it*/
 562   mask->pkt.mask_type_index_lsb = ~0;
 563
 564   mask->pkt.is_ip6 = 1;
 565   hi->match.pkt.is_ip6 = r->is_ipv6;
 566
 567   make_address_mask(&mask->addr[0], r->is_ipv6, r->src_prefixlen);
 568   hi->match.addr[0] = r->src;
 569   make_address_mask(&mask->addr[1], r->is_ipv6, r->dst_prefixlen);
 570   hi->match.addr[1] = r->dst;
 571
 572   if (r->proto != 0) {
 573     mask->l4.proto = ~0; /* L4 proto needs to be matched */
 574     hi->match.l4.proto = r->proto;
 575     if (match_nonfirst_fragment) {
 576       /* match the non-first fragments only */
 577       mask->pkt.is_nonfirst_fragment = 1;
 578       hi->match.pkt.is_nonfirst_fragment = 1;
 579     } else {
 580       /* Calculate the src/dst port masks and make the src/dst port matches accordingly */
 581       hi->src_portrange_not_powerof2 = make_port_mask(&mask->l4.port[0], r->src_port_or_type_first, r->src_port_or_type_last);
 582       hi->match.l4.port[0] = r->src_port_or_type_first & mask->l4.port[0];
 583       hi->dst_portrange_not_powerof2 = make_port_mask(&mask->l4.port[1], r->dst_port_or_code_first, r->dst_port_or_code_last);
 584       hi->match.l4.port[1] = r->dst_port_or_code_first & mask->l4.port[1];
 585       /* L4 info must be valid in order to match */
 586       mask->pkt.l4_valid = 1;
 587       hi->match.pkt.l4_valid = 1;
 588       /* And we must set the mask to check that it is an initial fragment */
 589       mask->pkt.is_nonfirst_fragment = 1;
 590       hi->match.pkt.is_nonfirst_fragment = 0;
 591       if ((r->proto == IPPROTO_TCP) && (r->tcp_flags_mask != 0)) {
 592         /* if we want to match on TCP flags, they must be masked off as well */
 593         mask->pkt.tcp_flags = r->tcp_flags_mask;
 594         hi->match.pkt.tcp_flags = r->tcp_flags_value;
 595         /* and the flags need to be present within the packet being matched */
 596         mask->pkt.tcp_flags_valid = 1;
 597         hi->match.pkt.tcp_flags_valid = 1;
 598       }
 599     }
 600   }
 601   /* Sanitize the mask and the match */
 602   u64 *pmask = (u64 *)mask;
 603   u64 *pmatch = (u64 *)&hi->match;
 604   int j;
 605   for(j=0; j<6; j++) {
 606     pmatch[j] = pmatch[j] & pmask[j];
 607   }
 608 }
 609
 610 static u32
 611 find_mask_type_index(acl_main_t *am, fa_5tuple_t *mask)
 612 {
 613   ace_mask_type_entry_t *mte;
 614   /* *INDENT-OFF* */
 615   pool_foreach(mte, am->ace_mask_type_pool,
 616   ({
 617     if(memcmp(&mte->mask, mask, sizeof(*mask)) == 0)
 618       return (mte - am->ace_mask_type_pool);
 619   }));
 620   /* *INDENT-ON* */
 621   return ~0;
 622 }
 623
 624 static u32
 625 assign_mask_type_index(acl_main_t *am, fa_5tuple_t *mask)
 626 {
 627   u32 mask_type_index = find_mask_type_index(am, mask);
 628   ace_mask_type_entry_t *mte;
 629   if(~0 == mask_type_index) {
 630     pool_get_aligned (am->ace_mask_type_pool, mte, CLIB_CACHE_LINE_BYTES);
 631     mask_type_index = mte - am->ace_mask_type_pool;
 632     clib_memcpy(&mte->mask, mask, sizeof(mte->mask));
 633     mte->refcount = 0;
 634     /*
 635      * We can use only 16 bits, since in the match there is only u16 field.
 636      * Realistically, once you go to 64K of mask types, it is a huge
 637      * problem anyway, so we might as well stop half way.
 638      */
 639     ASSERT(mask_type_index < 32768);
 640   }
 641   mte = am->ace_mask_type_pool + mask_type_index;
 642   mte->refcount++;
 643   return mask_type_index;
 644 }
 645
 646 static void
 647 release_mask_type_index(acl_main_t *am, u32 mask_type_index)
 648 {
 649   ace_mask_type_entry_t *mte = pool_elt_at_index(am->ace_mask_type_pool, mask_type_index);
 650   mte->refcount--;
 651   if (mte->refcount == 0) {
 652     /* we are not using this entry anymore */
 653     pool_put(am->ace_mask_type_pool, mte);
 654   }
 655 }
 656
 657 int hash_acl_exists(acl_main_t *am, int acl_index)
 658 {
 659   if (acl_index >= vec_len(am->hash_acl_infos))
 660     return 0;
 661
 662   hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, acl_index);
 663   return ha->hash_acl_exists;
 664 }
 665
 666 void hash_acl_add(acl_main_t *am, int acl_index)
 667 {
 668   void *oldheap = hash_acl_set_heap(am);
 669   DBG("HASH ACL add : %d", acl_index);
 670   int i;
 671   acl_list_t *a = &am->acls[acl_index];
 672   vec_validate(am->hash_acl_infos, acl_index);
 673   hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, acl_index);
 674   memset(ha, 0, sizeof(*ha));
 675   ha->hash_acl_exists = 1;
 676
 677   /* walk the newly added ACL entries and ensure that for each of them there
 678      is a mask type, increment a reference count for that mask type */
 679   for(i=0; i < a->count; i++) {
 680     hash_ace_info_t ace_info;
 681     fa_5tuple_t mask;
 682     memset(&ace_info, 0, sizeof(ace_info));
 683     ace_info.acl_index = acl_index;
 684     ace_info.ace_index = i;
 685
 686     make_mask_and_match_from_rule(&mask, &a->rules[i], &ace_info, 0);
 687     ace_info.mask_type_index = assign_mask_type_index(am, &mask);
 688     /* assign the mask type index for matching itself */
 689     ace_info.match.pkt.mask_type_index_lsb = ace_info.mask_type_index;
 690     DBG("ACE: %d mask_type_index: %d", i, ace_info.mask_type_index);
 691     /* Ensure a given index is set in the mask type index bitmap for this ACL */
 692     ha->mask_type_index_bitmap = clib_bitmap_set(ha->mask_type_index_bitmap, ace_info.mask_type_index, 1);
 693     vec_add1(ha->rules, ace_info);
 694     if (am->l4_match_nonfirst_fragment) {
 695       /* add the second rule which matches the noninitial fragments with the respective mask */
 696       make_mask_and_match_from_rule(&mask, &a->rules[i], &ace_info, 1);
 697       ace_info.mask_type_index = assign_mask_type_index(am, &mask);
 698       ace_info.match.pkt.mask_type_index_lsb = ace_info.mask_type_index;
 699       DBG("ACE: %d (non-initial frags) mask_type_index: %d", i, ace_info.mask_type_index);
 700       /* Ensure a given index is set in the mask type index bitmap for this ACL */
 701       ha->mask_type_index_bitmap = clib_bitmap_set(ha->mask_type_index_bitmap, ace_info.mask_type_index, 1);
 702       vec_add1(ha->rules, ace_info);
 703     }
 704   }
 705   /*
 706    * if an ACL is applied somewhere, fill the corresponding lookup data structures.
 707    * We need to take care if the ACL is not the last one in the vector of ACLs applied to the interface.
 708    */
 709   if (acl_index < vec_len(am->lc_index_vec_by_acl)) {
 710     u32 *lc_index;
 711     vec_foreach(lc_index, am->lc_index_vec_by_acl[acl_index]) {
 712       hash_acl_reapply(am, *lc_index, acl_index);
 713     }
 714   }
 715   clib_mem_set_heap (oldheap);
 716 }
 717
 718 void hash_acl_delete(acl_main_t *am, int acl_index)
 719 {
 720   void *oldheap = hash_acl_set_heap(am);
 721   DBG0("HASH ACL delete : %d", acl_index);
 722   /*
 723    * If the ACL is applied somewhere, remove the references of it (call hash_acl_unapply)
 724    * this is a different behavior from the linear lookup where an empty ACL is "deny all",
 725    *
 726    * However, following vpp-dev discussion the ACL that is referenced elsewhere
 727    * should not be possible to delete, and the change adding this also adds
 728    * the safeguards to that respect, so this is not a problem.
 729    *
 730    * The part to rememeber is that this routine is called in process of reapplication
 731    * during the acl_add_replace() API call - the old acl ruleset is deleted, then
 732    * the new one is added, without the change in the applied ACLs - so this case
 733    * has to be handled.
 734    */
 735   hash_acl_info_t *ha = vec_elt_at_index(am->hash_acl_infos, acl_index);
 736   u32 *lc_list_copy = 0;
 737   {
 738     u32 *lc_index;
 739     lc_list_copy = vec_dup(ha->lc_index_list);
 740     vec_foreach(lc_index, lc_list_copy) {
 741       hash_acl_unapply(am, *lc_index, acl_index);
 742     }
 743     vec_free(lc_list_copy);
 744   }
 745
 746   /* walk the mask types for the ACL about-to-be-deleted, and decrease
 747    * the reference count, possibly freeing up some of them */
 748   int i;
 749   for(i=0; i < vec_len(ha->rules); i++) {
 750     release_mask_type_index(am, ha->rules[i].mask_type_index);
 751   }
 752   clib_bitmap_free(ha->mask_type_index_bitmap);
 753   ha->hash_acl_exists = 0;
 754   vec_free(ha->rules);
 755   clib_mem_set_heap (oldheap);
 756 }
 757
 758
 759 void
 760 show_hash_acl_hash (vlib_main_t * vm, acl_main_t *am, u32 verbose)
 761 {
 762   vlib_cli_output(vm, "\nACL lookup hash table:\n%U\n",
 763                   BV (format_bihash), &am->acl_lookup_hash, verbose);
 764 }
 765
 766 void
 767 acl_plugin_show_tables_mask_type (void)
 768 {
 769   acl_main_t *am = &acl_main;
 770   vlib_main_t *vm = am->vlib_main;
 771   ace_mask_type_entry_t *mte;
 772
 773   vlib_cli_output (vm, "Mask-type entries:");
 774     /* *INDENT-OFF* */
 775     pool_foreach(mte, am->ace_mask_type_pool,
 776     ({
 777       vlib_cli_output(vm, "     %3d: %016llx %016llx %016llx %016llx %016llx %016llx  refcount %d",
 778                     mte - am->ace_mask_type_pool,
 779                     mte->mask.kv.key[0], mte->mask.kv.key[1], mte->mask.kv.key[2],
 780                     mte->mask.kv.key[3], mte->mask.kv.key[4], mte->mask.kv.value, mte->refcount);
 781     }));
 782     /* *INDENT-ON* */
 783 }
 784
 785 void
 786 acl_plugin_show_tables_acl_hash_info (u32 acl_index)
 787 {
 788   acl_main_t *am = &acl_main;
 789   vlib_main_t *vm = am->vlib_main;
 790   u32 i, j;
 791   u64 *m;
 792   vlib_cli_output (vm, "Mask-ready ACL representations\n");
 793   for (i = 0; i < vec_len (am->hash_acl_infos); i++)
 794     {
 795       if ((acl_index != ~0) && (acl_index != i))
 796         {
 797           continue;
 798         }
 799       hash_acl_info_t *ha = &am->hash_acl_infos[i];
 800       vlib_cli_output (vm, "acl-index %u bitmask-ready layout\n", i);
 801       vlib_cli_output (vm, "  applied lc_index list: %U\n",
 802                        format_vec32, ha->lc_index_list, "%d");
 803       vlib_cli_output (vm, "  mask type index bitmap: %U\n",
 804                        format_bitmap_hex, ha->mask_type_index_bitmap);
 805       for (j = 0; j < vec_len (ha->rules); j++)
 806         {
 807           hash_ace_info_t *pa = &ha->rules[j];
 808           m = (u64 *) & pa->match;
 809           vlib_cli_output (vm,
 810                            "    %4d: %016llx %016llx %016llx %016llx %016llx %016llx mask index %d acl %d rule %d action %d src/dst portrange not ^2: %d,%d\n",
 811                            j, m[0], m[1], m[2], m[3], m[4], m[5],
 812                            pa->mask_type_index, pa->acl_index, pa->ace_index,
 813                            pa->action, pa->src_portrange_not_powerof2,
 814                            pa->dst_portrange_not_powerof2);
 815         }
 816     }
 817 }
 818
 819 void
 820 acl_plugin_print_pae (vlib_main_t * vm, int j, applied_hash_ace_entry_t * pae)
 821 {
 822   vlib_cli_output (vm,
 823                    "    %4d: acl %d rule %d action %d bitmask-ready rule %d next %d prev %d tail %d hitcount %lld",
 824                    j, pae->acl_index, pae->ace_index, pae->action,
 825                    pae->hash_ace_info_index, pae->next_applied_entry_index,
 826                    pae->prev_applied_entry_index,
 827                    pae->tail_applied_entry_index, pae->hitcount);
 828 }
 829
 830 void
 831 acl_plugin_show_tables_applied_info (u32 sw_if_index)
 832 {
 833   acl_main_t *am = &acl_main;
 834   vlib_main_t *vm = am->vlib_main;
 835   u32 swi; //, j;
 836   vlib_cli_output (vm, "Applied lookup entries for interfaces");
 837
 838   for (swi = 0;
 839        (swi < vec_len (am->input_lc_index_by_sw_if_index))
 840        || (swi < vec_len (am->output_lc_index_by_sw_if_index)); swi++)
 841     {
 842       if ((sw_if_index != ~0) && (sw_if_index != swi))
 843         {
 844           continue;
 845         }
 846 /*
 847       vlib_cli_output (vm, "sw_if_index %d:", swi);
 848       if (swi < vec_len (am->input_applied_hash_acl_info_by_sw_if_index))
 849         {
 850           applied_hash_acl_info_t *pal =
 851             &am->input_applied_hash_acl_info_by_sw_if_index[swi];
 852           vlib_cli_output (vm, "  input lookup mask_type_index_bitmap: %U",
 853                            format_bitmap_hex, pal->mask_type_index_bitmap);
 854           vlib_cli_output (vm, "  input applied acls: %U", format_vec32,
 855                            pal->applied_acls, "%d");
 856         }
 857       if (swi < vec_len (am->input_hash_entry_vec_by_sw_if_index))
 858         {
 859           vlib_cli_output (vm, "  input lookup applied entries:");
 860           for (j = 0;
 861                j < vec_len (am->input_hash_entry_vec_by_sw_if_index[swi]);
 862                j++)
 863             {
 864               acl_plugin_print_pae (vm, j,
 865                                     &am->input_hash_entry_vec_by_sw_if_index
 866                                     [swi][j]);
 867             }
 868         }
 869
 870       if (swi < vec_len (am->output_applied_hash_acl_info_by_sw_if_index))
 871         {
 872           applied_hash_acl_info_t *pal =
 873             &am->output_applied_hash_acl_info_by_sw_if_index[swi];
 874           vlib_cli_output (vm, "  output lookup mask_type_index_bitmap: %U",
 875                            format_bitmap_hex, pal->mask_type_index_bitmap);
 876           vlib_cli_output (vm, "  output applied acls: %U", format_vec32,
 877                            pal->applied_acls, "%d");
 878         }
 879       if (swi < vec_len (am->output_hash_entry_vec_by_sw_if_index))
 880         {
 881           vlib_cli_output (vm, "  output lookup applied entries:");
 882           for (j = 0;
 883                j < vec_len (am->output_hash_entry_vec_by_sw_if_index[swi]);
 884                j++)
 885             {
 886               acl_plugin_print_pae (vm, j,
 887                                     &am->output_hash_entry_vec_by_sw_if_index
 888                                     [swi][j]);
 889             }
 890         }
 891 */
 892     }
 893 }
 894
 895 void
 896 acl_plugin_show_tables_bihash (u32 show_bihash_verbose)
 897 {
 898   acl_main_t *am = &acl_main;
 899   vlib_main_t *vm = am->vlib_main;
 900   show_hash_acl_hash (vm, am, show_bihash_verbose);
 901 }
 902