+/*
+ * TupleMerge
+ *
+ * Initial adaptation by Valerio Bruschi (valerio.bruschi@telecom-paristech.fr)
+ * based on the TupleMerge [1] simulator kindly made available
+ * by James Daly (dalyjamese@gmail.com) and Eric Torng (torng@cse.msu.edu)
+ * ( http://www.cse.msu.edu/~dalyjame/ or http://www.cse.msu.edu/~torng/ ),
+ * refactoring by Andrew Yourtchenko.
+ *
+ * [1] James Daly, Eric Torng "TupleMerge: Building Online Packet Classifiers
+ * by Omitting Bits", In Proc. IEEE ICCCN 2017, pp. 1-10
+ *
+ */
+
+static int
+count_bits (u64 word)
+{
+ int counter = 0;
+ while (word)
+ {
+ counter += word & 1;
+ word >>= 1;
+ }
+ return counter;
+}
+
+/* check if mask2 can be contained by mask1 */
+static u8
+first_mask_contains_second_mask(int is_ip6, fa_5tuple_t * mask1, fa_5tuple_t * mask2)
+{
+ int i;
+ if (is_ip6)
+ {
+ for (i = 0; i < 2; i++)
+ {
+ if ((mask1->ip6_addr[0].as_u64[i] & mask2->ip6_addr[0].as_u64[i]) !=
+ mask1->ip6_addr[0].as_u64[i])
+ return 0;
+ if ((mask1->ip6_addr[1].as_u64[i] & mask2->ip6_addr[1].as_u64[i]) !=
+ mask1->ip6_addr[1].as_u64[i])
+ return 0;
+ }
+ }
+ else
+ {
+ /* check the pads, both masks must have it 0 */
+ u32 padcheck = 0;
+ int i;
+ for (i=0; i<6; i++) {
+ padcheck |= mask1->l3_zero_pad[i];
+ padcheck |= mask2->l3_zero_pad[i];
+ }
+ if (padcheck != 0)
+ return 0;
+ if ((mask1->ip4_addr[0].as_u32 & mask2->ip4_addr[0].as_u32) !=
+ mask1->ip4_addr[0].as_u32)
+ return 0;
+ if ((mask1->ip4_addr[1].as_u32 & mask2->ip4_addr[1].as_u32) !=
+ mask1->ip4_addr[1].as_u32)
+ return 0;
+ }
+
+ /* take care if port are not exact-match */
+ if ((mask1->l4.as_u64 & mask2->l4.as_u64) != mask1->l4.as_u64)
+ return 0;
+
+ if ((mask1->pkt.as_u64 & mask2->pkt.as_u64) != mask1->pkt.as_u64)
+ return 0;
+
+ return 1;
+}
+
+
+
+/*
+ * TupleMerge:
+ *
+ * Consider the situation when we have to create a new table
+ * T for a given rule R. This occurs for the first rule inserted and
+ * for later rules if it is incompatible with all existing tables.
+ * In this event, we need to determine mT for a new table.
+ * Setting mT = mR is not a good strategy; if another similar,
+ * but slightly less specific, rule appears we will be unable to
+ * add it to T and will thus have to create another new table. We
+ * thus consider two factors: is the rule more strongly aligned
+ * with source or destination addresses (usually the two most
+ * important fields) and how much slack needs to be given to
+ * allow for other rules. If the source and destination addresses
+ * are close together (within 4 bits for our experiments), we use
+ * both of them. Otherwise, we drop the smaller (less specific)
+ * address and its associated port field from consideration; R is
+ * predominantly aligned with one of the two fields and should
+ * be grouped with other similar rules. This is similar to TSS
+ * dropping port fields, but since it is based on observable rule
+ * characteristics it is more likely to keep important fields and
+ * discard less useful ones.
+ * We then look at the absolute lengths of the addresses. If
+ * the address is long, we are more likely to try to add shorter
+ * lengths and likewise the reverse. We thus remove a few bits
+ * from both address fields with more bits removed from longer
+ * addresses. For 32 bit addresses, we remove 4 bits, 3 for more
+ * than 24, 2 for more than 16, and so on (so 8 and fewer bits
+ * don’t have any removed). We only do this for prefix fields like
+ * addresses; both range fields (like ports) and exact match fields
+ * (like protocol) should remain as they are.
+ */
+
+
+static u32
+shift_ip4_if(u32 mask, u32 thresh, int numshifts, u32 else_val)
+{
+ if (mask > thresh)
+ return clib_host_to_net_u32((clib_net_to_host_u32(mask) << numshifts) & 0xFFFFFFFF);
+ else
+ return else_val;
+}
+
+static void
+relax_ip4_addr(ip4_address_t *ip4_mask, int relax2) {
+ int shifts_per_relax[2][4] = { { 6, 5, 4, 2 }, { 3, 2, 1, 1 } };
+
+ int *shifts = shifts_per_relax[relax2];
+ if(ip4_mask->as_u32 == 0xffffffff)
+ ip4_mask->as_u32 = clib_host_to_net_u32((clib_net_to_host_u32(ip4_mask->as_u32) << shifts[0])&0xFFFFFFFF);
+ else
+ ip4_mask->as_u32 = shift_ip4_if(ip4_mask->as_u32, 0xffffff00, shifts[1],
+ shift_ip4_if(ip4_mask->as_u32, 0xffff0000, shifts[2],
+ shift_ip4_if(ip4_mask->as_u32, 0xff000000, shifts[3], ip4_mask->as_u32)));
+}
+
+static void
+relax_ip6_addr(ip6_address_t *ip6_mask, int relax2) {
+ /*
+ * This "better than nothing" relax logic is based on heuristics
+ * from IPv6 knowledge, and may not be optimal.
+ * Some further tuning may be needed in the future.
+ */
+ if (ip6_mask->as_u64[0] == 0xffffffffffffffffULL) {
+ if (ip6_mask->as_u64[1] == 0xffffffffffffffffULL) {
+ /* relax a /128 down to /64 - likely to have more hosts */
+ ip6_mask->as_u64[1] = 0;
+ } else if (ip6_mask->as_u64[1] == 0) {
+ /* relax a /64 down to /56 - likely to have more subnets */
+ ip6_mask->as_u64[0] = clib_host_to_net_u64(0xffffffffffffff00ULL);
+ }
+ }
+}
+
+static void
+relax_tuple(fa_5tuple_t *mask, int is_ip6, int relax2){
+ fa_5tuple_t save_mask = *mask;
+
+ int counter_s = 0, counter_d = 0;
+ if (is_ip6) {
+ int i;
+ for(i=0; i<2; i++){
+ counter_s += count_bits(mask->ip6_addr[0].as_u64[i]);
+ counter_d += count_bits(mask->ip6_addr[1].as_u64[i]);
+ }
+ } else {
+ counter_s += count_bits(mask->ip4_addr[0].as_u32);
+ counter_d += count_bits(mask->ip4_addr[1].as_u32);
+ }
+
+/*
+ * is the rule more strongly aligned with source or destination addresses
+ * (usually the two most important fields) and how much slack needs to be
+ * given to allow for other rules. If the source and destination addresses
+ * are close together (within 4 bits for our experiments), we use both of them.
+ * Otherwise, we drop the smaller (less specific) address and its associated
+ * port field from consideration
+ */
+ const int deltaThreshold = 4;
+ /* const int deltaThreshold = 8; if IPV6? */
+ int delta = counter_s - counter_d;
+ if (-delta > deltaThreshold) {
+ if (is_ip6)
+ mask->ip6_addr[0].as_u64[1] = mask->ip6_addr[0].as_u64[0] = 0;
+ else
+ mask->ip4_addr[0].as_u32 = 0;
+ mask->l4.port[0] = 0;
+ } else if (delta > deltaThreshold) {
+ if (is_ip6)
+ mask->ip6_addr[1].as_u64[1] = mask->ip6_addr[1].as_u64[0] = 0;
+ else
+ mask->ip4_addr[1].as_u32 = 0;
+ mask->l4.port[1] = 0;
+ }
+
+ if (is_ip6) {
+ relax_ip6_addr(&mask->ip6_addr[0], relax2);
+ relax_ip6_addr(&mask->ip6_addr[1], relax2);
+ } else {
+ relax_ip4_addr(&mask->ip4_addr[0], relax2);
+ relax_ip4_addr(&mask->ip4_addr[1], relax2);
+ }
+ mask->pkt.is_nonfirst_fragment = 0;
+ mask->pkt.l4_valid = 0;
+ if(!first_mask_contains_second_mask(is_ip6, mask, &save_mask)){
+ DBG( "TM-relaxing-ERROR");
+ *mask = save_mask;
+ }
+ DBG( "TM-relaxing-end");
+}
+
+static u32
+find_mask_type_index(acl_main_t *am, fa_5tuple_t *mask)
+{
+ ace_mask_type_entry_t *mte;
+ /* *INDENT-OFF* */
+ pool_foreach(mte, am->ace_mask_type_pool,
+ ({
+ if(memcmp(&mte->mask, mask, sizeof(*mask)) == 0)
+ return (mte - am->ace_mask_type_pool);
+ }));
+ /* *INDENT-ON* */
+ return ~0;
+}
+
+static u32
+assign_mask_type_index(acl_main_t *am, fa_5tuple_t *mask)
+{
+ u32 mask_type_index = find_mask_type_index(am, mask);
+ ace_mask_type_entry_t *mte;
+ if(~0 == mask_type_index) {
+ pool_get_aligned (am->ace_mask_type_pool, mte, CLIB_CACHE_LINE_BYTES);
+ mask_type_index = mte - am->ace_mask_type_pool;
+ clib_memcpy_fast(&mte->mask, mask, sizeof(mte->mask));
+ mte->refcount = 0;
+
+ /*
+ * We can use only 16 bits, since in the match there is only u16 field.
+ * Realistically, once you go to 64K of mask types, it is a huge
+ * problem anyway, so we might as well stop half way.
+ */
+ ASSERT(mask_type_index < 32768);
+ }
+ mte = am->ace_mask_type_pool + mask_type_index;
+ mte->refcount++;
+ DBG0("ASSIGN MTE index %d new refcount %d", mask_type_index, mte->refcount);
+ return mask_type_index;
+}
+
+static void
+lock_mask_type_index(acl_main_t *am, u32 mask_type_index)
+{
+ DBG0("LOCK MTE index %d", mask_type_index);
+ ace_mask_type_entry_t *mte = pool_elt_at_index(am->ace_mask_type_pool, mask_type_index);
+ mte->refcount++;
+ DBG0("LOCK MTE index %d new refcount %d", mask_type_index, mte->refcount);
+}
+
+
+static void
+release_mask_type_index(acl_main_t *am, u32 mask_type_index)
+{
+ DBG0("RELEAS MTE index %d", mask_type_index);
+ ace_mask_type_entry_t *mte = pool_elt_at_index(am->ace_mask_type_pool, mask_type_index);
+ mte->refcount--;
+ DBG0("RELEAS MTE index %d new refcount %d", mask_type_index, mte->refcount);
+ if (mte->refcount == 0) {
+ /* we are not using this entry anymore */
+ clib_memset(mte, 0xae, sizeof(*mte));
+ pool_put(am->ace_mask_type_pool, mte);
+ }
+}
+
+
+static u32
+tm_assign_mask_type_index(acl_main_t *am, fa_5tuple_t *mask, int is_ip6, u32 lc_index)
+{
+ u32 mask_type_index = ~0;
+ u32 for_mask_type_index = ~0;
+ ace_mask_type_entry_t *mte = 0;
+ int order_index;
+ /* look for existing mask comparable with the one in input */
+
+ hash_applied_mask_info_t **hash_applied_mask_info_vec = vec_elt_at_index(am->hash_applied_mask_info_vec_by_lc_index, lc_index);
+ hash_applied_mask_info_t *minfo;
+
+ if (vec_len(*hash_applied_mask_info_vec) > 0) {
+ for(order_index = vec_len((*hash_applied_mask_info_vec)) -1; order_index >= 0; order_index--) {
+ minfo = vec_elt_at_index((*hash_applied_mask_info_vec), order_index);
+ for_mask_type_index = minfo->mask_type_index;
+ mte = vec_elt_at_index(am->ace_mask_type_pool, for_mask_type_index);
+ if(first_mask_contains_second_mask(is_ip6, &mte->mask, mask)){
+ mask_type_index = (mte - am->ace_mask_type_pool);
+ lock_mask_type_index(am, mask_type_index);
+ break;
+ }
+ }
+ }
+
+ if(~0 == mask_type_index) {
+ /* if no mask is found, then let's use a relaxed version of the original one, in order to be used by new ace_entries */
+ DBG( "TM-assigning mask type index-new one");
+ fa_5tuple_t relaxed_mask = *mask;
+ relax_tuple(&relaxed_mask, is_ip6, 0);
+ mask_type_index = assign_mask_type_index(am, &relaxed_mask);
+
+ hash_applied_mask_info_t **hash_applied_mask_info_vec = vec_elt_at_index(am->hash_applied_mask_info_vec_by_lc_index, lc_index);
+
+ int spot = vec_len((*hash_applied_mask_info_vec));
+ vec_validate((*hash_applied_mask_info_vec), spot);
+ minfo = vec_elt_at_index((*hash_applied_mask_info_vec), spot);
+ minfo->mask_type_index = mask_type_index;
+ minfo->num_entries = 0;
+ minfo->max_collisions = 0;
+ minfo->first_rule_index = ~0;
+
+ /*
+ * We can use only 16 bits, since in the match there is only u16 field.
+ * Realistically, once you go to 64K of mask types, it is a huge
+ * problem anyway, so we might as well stop half way.
+ */
+ ASSERT(mask_type_index < 32768);
+ }
+ mte = am->ace_mask_type_pool + mask_type_index;
+ DBG0("TM-ASSIGN MTE index %d new refcount %d", mask_type_index, mte->refcount);
+ return mask_type_index;
+}
+
+