src/vnet/lisp-cp/gid_dictionary.c - fdio/vpp - Gitiles

 /*
  * Copyright (c) 2016 Cisco and/or its affiliates.
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at:
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include <vnet/lisp-cp/gid_dictionary.h>

 typedef struct
 {
   void *arg;
   ip_prefix_t src;
   foreach_subprefix_match_cb_t cb;
   union
   {
     gid_ip4_table_t *ip4_table;
     gid_ip6_table_t *ip6_table;
   };
 } sfib_entry_arg_t;

 static u32 ip4_lookup (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key);

 static u32 ip6_lookup (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key);

 static void
 foreach_sfib4_subprefix (BVT (clib_bihash_kv) * kvp, void *arg)
 {
   sfib_entry_arg_t *a = arg;
   u32 ip = (u32) kvp->key[0];
   ip4_address_t *mask;
   u8 plen = ip_prefix_len (&a->src);

   ASSERT (plen <= 32);
   mask = &a->ip4_table->ip4_fib_masks[plen];

   u32 src_ip = ip_prefix_v4 (&a->src).as_u32;
   src_ip &= mask->as_u32;
   ip &= mask->as_u32;

   if (src_ip == ip)
     {
       /* found sub-prefix of src prefix */
       (a->cb) (kvp->value, a->arg);
     }
 }

 static void
 gid_dict_foreach_ip4_subprefix (gid_dictionary_t * db, u32 vni,
 				ip_prefix_t * src, ip_prefix_t * dst,
 				foreach_subprefix_match_cb_t cb, void *arg)
 {
   u32 sfi;
   gid_ip4_table_t *sfib4;
   sfib_entry_arg_t a;

   sfi = ip4_lookup (&db->dst_ip4_table, vni, dst);
   if (GID_LOOKUP_MISS == sfi)
     return;

   sfib4 = pool_elt_at_index (db->src_ip4_table_pool, sfi);

   a.arg = arg;
   a.cb = cb;
   a.src = src[0];
   a.ip4_table = sfib4;

   BV (clib_bihash_foreach_key_value_pair) (&sfib4->ip4_lookup_table,
 					   foreach_sfib4_subprefix, &a);
 }

 static void
 foreach_sfib6_subprefix (BVT (clib_bihash_kv) * kvp, void *arg)
 {
   sfib_entry_arg_t *a = arg;
   ip6_address_t ip;
   ip6_address_t *mask;
   u8 plen = ip_prefix_len (&a->src);

   mask = &a->ip6_table->ip6_fib_masks[plen];
   ip.as_u64[0] = kvp->key[0];
   ip.as_u64[1] = kvp->key[1];

   if (ip6_address_is_equal_masked (&ip_prefix_v6 (&a->src), &ip, mask))
     {
       /* found sub-prefix of src prefix */
       (a->cb) (kvp->value, a->arg);
     }
 }

 static void
 gid_dict_foreach_ip6_subprefix (gid_dictionary_t * db, u32 vni,
 				ip_prefix_t * src, ip_prefix_t * dst,
 				foreach_subprefix_match_cb_t cb, void *arg)
 {
   u32 sfi;
   gid_ip6_table_t *sfib6;
   sfib_entry_arg_t a;

   sfi = ip6_lookup (&db->dst_ip6_table, vni, dst);
   if (GID_LOOKUP_MISS == sfi)
     return;

   sfib6 = pool_elt_at_index (db->src_ip6_table_pool, sfi);

   a.arg = arg;
   a.cb = cb;
   a.src = src[0];
   a.ip6_table = sfib6;

   BV (clib_bihash_foreach_key_value_pair) (&sfib6->ip6_lookup_table,
 					   foreach_sfib6_subprefix, &a);
 }

 void
 gid_dict_foreach_subprefix (gid_dictionary_t * db, gid_address_t * eid,
 			    foreach_subprefix_match_cb_t cb, void *arg)
 {
   ip_prefix_t *ippref = &gid_address_sd_dst_ippref (eid);

   if (IP4 == ip_prefix_version (ippref))
     gid_dict_foreach_ip4_subprefix (db, gid_address_vni (eid),
 				    &gid_address_sd_src_ippref (eid),
 				    &gid_address_sd_dst_ippref (eid), cb,
 				    arg);
   else
     gid_dict_foreach_ip6_subprefix (db, gid_address_vni (eid),
 				    &gid_address_sd_src_ippref (eid),
 				    &gid_address_sd_dst_ippref (eid), cb,
 				    arg);
 }

 static void
 make_mac_sd_key (BVT (clib_bihash_kv) * kv, u32 vni, u8 src_mac[6],
 		 u8 dst_mac[6])
 {
   kv->key[0] = (u64) vni;
   kv->key[1] = mac_to_u64 (dst_mac);
   kv->key[2] = src_mac ? mac_to_u64 (src_mac) : (u64) 0;
 }

 static u32
 mac_sd_lookup (gid_mac_table_t * db, u32 vni, u8 * dst, u8 * src)
 {
   int rv;
   BVT (clib_bihash_kv) kv, value;

   make_mac_sd_key (&kv, vni, src, dst);
   rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv, &value);

   /* no match, try with src 0, catch all for dst */
   if (rv != 0)
     {
       kv.key[2] = 0;
       rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv,
 					     &value);
       if (rv == 0)
 	return value.value;
     }
   else
     return value.value;

   return GID_LOOKUP_MISS;
 }

 static u32
 ip4_lookup_exact_match (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
 {
   int rv;
   BVT (clib_bihash_kv) kv, value;

   ip4_address_t *mask;

   mask = &db->ip4_fib_masks[ip_prefix_len (key)];

   kv.key[0] = ((u64) vni << 32) | (ip_prefix_v4 (key).as_u32 & mask->as_u32);
   kv.key[1] = 0;
   kv.key[2] = 0;

   rv = BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
   if (rv == 0)
     return value.value;

   return GID_LOOKUP_MISS;
 }

 static u32
 ip4_lookup (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
 {
   int i, len;
   int rv;
   BVT (clib_bihash_kv) kv, value;

   len = vec_len (db->ip4_prefix_lengths_in_search_order);

   for (i = 0; i < len; i++)
     {
       int dst_address_length = db->ip4_prefix_lengths_in_search_order[i];
       ip4_address_t *mask;

       ASSERT (dst_address_length >= 0 && dst_address_length <= 32);

       mask = &db->ip4_fib_masks[dst_address_length];

       kv.key[0] =
 	((u64) vni << 32) | (ip_prefix_v4 (key).as_u32 & mask->as_u32);
       kv.key[1] = 0;
       kv.key[2] = 0;

       rv =
 	BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
       if (rv == 0)
 	return value.value;
     }

   return GID_LOOKUP_MISS;
 }

 static u32
 ip6_lookup_exact_match (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
 {
   int rv;
   BVT (clib_bihash_kv) kv, value;

   ip6_address_t *mask;
   mask = &db->ip6_fib_masks[ip_prefix_len (key)];

   kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
   kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
   kv.key[2] = (u64) vni;

   rv = BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
   if (rv == 0)
     return value.value;

   return GID_LOOKUP_MISS;
 }

 static u32
 ip6_lookup (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
 {
   int i, len;
   int rv;
   BVT (clib_bihash_kv) kv, value;

   len = vec_len (db->ip6_prefix_lengths_in_search_order);

   for (i = 0; i < len; i++)
     {
       int dst_address_length = db->ip6_prefix_lengths_in_search_order[i];
       ip6_address_t *mask;

       ASSERT (dst_address_length >= 0 && dst_address_length <= 128);

       mask = &db->ip6_fib_masks[dst_address_length];

       kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
       kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
       kv.key[2] = (u64) vni;

       rv =
 	BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
       if (rv == 0)
 	return value.value;
     }

   return GID_LOOKUP_MISS;
 }

 static u32
 ip_sd_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst,
 	      ip_prefix_t * src)
 {
   u32 sfi;
   gid_ip4_table_t *sfib4;
   gid_ip6_table_t *sfib6;

   switch (ip_prefix_version (dst))
     {
     case IP4:
       sfi = ip4_lookup (&db->dst_ip4_table, vni, dst);
       if (GID_LOOKUP_MISS != sfi)
 	sfib4 = pool_elt_at_index (db->src_ip4_table_pool, sfi);
       else
 	return GID_LOOKUP_MISS;

       if (!src)
 	{
 	  ip_prefix_t sp;
 	  memset (&sp, 0, sizeof (sp));
 	  return ip4_lookup_exact_match (sfib4, 0, &sp);
 	}
       else
 	return ip4_lookup (sfib4, 0, src);

       break;
     case IP6:
       sfi = ip6_lookup (&db->dst_ip6_table, vni, dst);
       if (GID_LOOKUP_MISS != sfi)
 	sfib6 = pool_elt_at_index (db->src_ip6_table_pool, sfi);
       else
 	return GID_LOOKUP_MISS;

       if (!src)
 	{
 	  ip_prefix_t sp;
 	  memset (&sp, 0, sizeof (sp));
 	  ip_prefix_version (&sp) = IP6;
 	  return ip6_lookup_exact_match (sfib6, 0, &sp);
 	}
       else
 	return ip6_lookup (sfib6, 0, src);

       break;
     default:
       clib_warning ("address type %d not supported!",
 		    ip_prefix_version (dst));
       break;
     }
   return GID_LOOKUP_MISS;
 }

 u32
 gid_dictionary_lookup (gid_dictionary_t * db, gid_address_t * key)
 {
   switch (gid_address_type (key))
     {
     case GID_ADDR_IP_PREFIX:
       return ip_sd_lookup (db, gid_address_vni (key),
 			   &gid_address_ippref (key), 0);
     case GID_ADDR_MAC:
       return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
 			    gid_address_mac (key), 0);
     case GID_ADDR_SRC_DST:
       switch (gid_address_sd_dst_type (key))
 	{
 	case FID_ADDR_IP_PREF:
 	  return ip_sd_lookup (db, gid_address_vni (key),
 			       &gid_address_sd_dst_ippref (key),
 			       &gid_address_sd_src_ippref (key));
 	  break;
 	case FID_ADDR_MAC:
 	  return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
 				gid_address_sd_dst_mac (key),
 				gid_address_sd_src_mac (key));
 	  break;
 	default:
 	  clib_warning ("Source/Dest address type %d not supported!",
 			gid_address_sd_dst_type (key));
 	  break;
 	}
       break;
     default:
       clib_warning ("address type %d not supported!", gid_address_type (key));
       break;
     }
   return GID_LOOKUP_MISS;
 }

 u32
 gid_dictionary_sd_lookup (gid_dictionary_t * db, gid_address_t * dst,
 			  gid_address_t * src)
 {
   switch (gid_address_type (dst))
     {
     case GID_ADDR_IP_PREFIX:
       return ip_sd_lookup (db, gid_address_vni (dst),
 			   &gid_address_ippref (dst),
 			   &gid_address_ippref (src));
     case GID_ADDR_MAC:
       return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
 			    gid_address_mac (dst), gid_address_mac (src));
     case GID_ADDR_SRC_DST:
       switch (gid_address_sd_dst_type (dst))
 	{
 	case FID_ADDR_IP_PREF:
 	  return ip_sd_lookup (db, gid_address_vni (dst),
 			       &gid_address_sd_dst_ippref (dst),
 			       &gid_address_sd_src_ippref (dst));
 	  break;
 	case FID_ADDR_MAC:
 	  return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
 				gid_address_sd_dst_mac (dst),
 				gid_address_sd_src_mac (dst));
 	  break;
 	default:
 	  clib_warning ("Source/Dest address type %d not supported!",
 			gid_address_sd_dst_type (dst));
 	  break;
 	}
       break;
     default:
       clib_warning ("address type %d not supported!", gid_address_type (dst));
       break;
     }
   return GID_LOOKUP_MISS;
 }

 static void
 ip4_compute_prefix_lengths_in_search_order (gid_ip4_table_t * db)
 {
   int i;
   vec_reset_length (db->ip4_prefix_lengths_in_search_order);
   /* Note: bitmap reversed so this is in fact a longest prefix match */

   /* *INDENT-OFF* */
   clib_bitmap_foreach (i, db->ip4_non_empty_dst_address_length_bitmap,
   ({
     int dst_address_length = 32 - i;
     vec_add1 (db->ip4_prefix_lengths_in_search_order, dst_address_length);
   }));
   /* *INDENT-ON* */

 }

 static u32
 add_del_ip4_key (gid_ip4_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 		 u8 is_add)
 {
   BVT (clib_bihash_kv) kv, value;
   u32 old_val = ~0;
   ip4_address_t key;
   u8 plen = ip_prefix_len (pref);

   clib_memcpy (&key, &ip_prefix_v4 (pref), sizeof (key));
   key.as_u32 &= db->ip4_fib_masks[plen].as_u32;
   if (is_add)
     {
       db->ip4_non_empty_dst_address_length_bitmap =
 	clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
 			 32 - plen, 1);
       ip4_compute_prefix_lengths_in_search_order (db);

       db->ip4_prefix_len_refcount[plen]++;
     }
   else
     {
       ASSERT (db->ip4_prefix_len_refcount[plen] != 0);

       db->ip4_prefix_len_refcount[plen]--;

       if (db->ip4_prefix_len_refcount[plen] == 0)
 	{
 	  db->ip4_non_empty_dst_address_length_bitmap =
 	    clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
 			     32 - plen, 0);
 	  ip4_compute_prefix_lengths_in_search_order (db);
 	}
     }

   kv.key[0] = ((u64) vni << 32) | key.as_u32;
   kv.key[1] = 0;
   kv.key[2] = 0;

   if (BV (clib_bihash_search) (&db->ip4_lookup_table, &kv, &value) == 0)
     old_val = value.value;

   if (!is_add)
     BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 0 /* is_add */ );
   else
     {
       kv.value = val;
       BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 1 /* is_add */ );
     }
   return old_val;
 }

 static void
 ip4_lookup_init (gid_ip4_table_t * db)
 {
   uword i;

   memset (db->ip4_prefix_len_refcount, 0,
 	  sizeof (db->ip4_prefix_len_refcount));

   for (i = 0; i < ARRAY_LEN (db->ip4_fib_masks); i++)
     {
       u32 m;

       if (i < 32)
 	m = pow2_mask (i) << (32 - i);
       else
 	m = ~0;
       db->ip4_fib_masks[i].as_u32 = clib_host_to_net_u32 (m);
     }
   if (db->ip4_lookup_table_nbuckets == 0)
     db->ip4_lookup_table_nbuckets = IP4_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;

   db->ip4_lookup_table_nbuckets =
     1 << max_log2 (db->ip4_lookup_table_nbuckets);

   if (db->ip4_lookup_table_size == 0)
     db->ip4_lookup_table_size = IP4_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;

   BV (clib_bihash_init) (&db->ip4_lookup_table, "ip4 lookup table",
 			 db->ip4_lookup_table_nbuckets,
 			 db->ip4_lookup_table_size);
 }

 static u32
 add_del_sd_ip4_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
 		    ip_prefix_t * src_pref, u32 val, u8 is_add)
 {
   u32 sfi, old_val = ~0;
   gid_ip4_table_t *sfib;

   sfi = ip4_lookup_exact_match (&db->dst_ip4_table, vni, dst_pref);

   if (is_add)
     {
       if (GID_LOOKUP_MISS == sfi)
 	{
 	  pool_get (db->src_ip4_table_pool, sfib);
 	  ip4_lookup_init (sfib);
 	  add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref,
 			   sfib - db->src_ip4_table_pool, is_add);
 	  if (src_pref)
 	    add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 	  else
 	    {
 	      ip_prefix_t sp;
 	      memset (&sp, 0, sizeof (sp));
 	      add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
 	    }
 	}
       else
 	{
 	  ASSERT (!pool_is_free_index (db->src_ip4_table_pool, sfi));
 	  sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 	  if (src_pref)
 	    {
 	      old_val = ip4_lookup_exact_match (sfib, 0, src_pref);
 	      add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 	    }
 	  else
 	    {
 	      ip_prefix_t sp;
 	      memset (&sp, 0, sizeof (sp));
 	      old_val =
 		add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
 	    }
 	}
     }
   else
     {
       if (GID_LOOKUP_MISS != sfi)
 	{
 	  add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref, 0, is_add);
 	  sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 	  if (src_pref)
 	    old_val = add_del_ip4_key (sfib, 0, src_pref, 0, is_add);
 	  else
 	    {
 	      ip_prefix_t sp;
 	      memset (&sp, 0, sizeof (sp));
 	      old_val = add_del_ip4_key (sfib, 0, &sp, 0, is_add);
 	    }
 	}
       else
 	clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
 		      dst_pref);
     }
   return old_val;
 }

 static void
 ip6_compute_prefix_lengths_in_search_order (gid_ip6_table_t * db)
 {
   int i;
   vec_reset_length (db->ip6_prefix_lengths_in_search_order);
   /* Note: bitmap reversed so this is in fact a longest prefix match */

   /* *INDENT-OFF* */
   clib_bitmap_foreach (i, db->ip6_non_empty_dst_address_length_bitmap,
   ({
     int dst_address_length = 128 - i;
     vec_add1 (db->ip6_prefix_lengths_in_search_order, dst_address_length);
   }));
   /* *INDENT-ON* */
 }

 static u32
 add_del_ip6_key (gid_ip6_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 		 u8 is_add)
 {
   BVT (clib_bihash_kv) kv, value;
   u32 old_val = ~0;
   ip6_address_t key;
   u8 plen = ip_prefix_len (pref);

   clib_memcpy (&key, &ip_prefix_v6 (pref), sizeof (key));
   ip6_address_mask (&key, &db->ip6_fib_masks[plen]);
   if (is_add)
     {
       db->ip6_non_empty_dst_address_length_bitmap =
 	clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 			 128 - plen, 1);
       ip6_compute_prefix_lengths_in_search_order (db);
       db->ip6_prefix_len_refcount[plen]++;
     }
   else
     {
       ASSERT (db->ip6_prefix_len_refcount[plen] != 0);

       db->ip6_prefix_len_refcount[plen]--;

       if (db->ip6_prefix_len_refcount[plen] == 0)
 	{
 	  db->ip6_non_empty_dst_address_length_bitmap =
 	    clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 			     128 - plen, 0);
 	  ip6_compute_prefix_lengths_in_search_order (db);
 	}
     }

   kv.key[0] = key.as_u64[0];
   kv.key[1] = key.as_u64[1];
   kv.key[2] = (u64) vni;
 //  kv.key[2] = ((u64)((fib - im->fibs))<<32) | ip_prefix_len(key);

   if (BV (clib_bihash_search) (&db->ip6_lookup_table, &kv, &value) == 0)
     old_val = value.value;

   if (!is_add)
     BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 0 /* is_add */ );
   else
     {
       kv.value = val;
       BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 1 /* is_add */ );
     }
   return old_val;
 }

 static u32
 add_del_mac (gid_mac_table_t * db, u32 vni, u8 * dst_mac, u8 * src_mac,
 	     u32 val, u8 is_add)
 {
   BVT (clib_bihash_kv) kv, value;
   u32 old_val = ~0;

   make_mac_sd_key (&kv, vni, src_mac, dst_mac);

   if (BV (clib_bihash_search) (&db->mac_lookup_table, &kv, &value) == 0)
     old_val = value.value;

   if (!is_add)
     BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 0 /* is_add */ );
   else
     {
       kv.value = val;
       BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 1 /* is_add */ );
     }
   return old_val;
 }

 static void
 ip6_lookup_init (gid_ip6_table_t * db)
 {
   uword i;

   memset (db->ip6_prefix_len_refcount, 0,
 	  sizeof (db->ip6_prefix_len_refcount));

   for (i = 0; i < ARRAY_LEN (db->ip6_fib_masks); i++)
     {
       u32 j, i0, i1;

       i0 = i / 32;
       i1 = i % 32;

       for (j = 0; j < i0; j++)
 	db->ip6_fib_masks[i].as_u32[j] = ~0;

       if (i1)
 	db->ip6_fib_masks[i].as_u32[i0] =
 	  clib_host_to_net_u32 (pow2_mask (i1) << (32 - i1));
     }

   if (db->ip6_lookup_table_nbuckets == 0)
     db->ip6_lookup_table_nbuckets = IP6_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;

   db->ip6_lookup_table_nbuckets =
     1 << max_log2 (db->ip6_lookup_table_nbuckets);

   if (db->ip6_lookup_table_size == 0)
     db->ip6_lookup_table_size = IP6_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;

   BV (clib_bihash_init) (&db->ip6_lookup_table, "ip6 lookup table",
 			 db->ip6_lookup_table_nbuckets,
 			 db->ip6_lookup_table_size);
 }

 static u32
 add_del_sd_ip6_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
 		    ip_prefix_t * src_pref, u32 val, u8 is_add)
 {
   u32 sfi, old_val = ~0;
   gid_ip6_table_t *sfib;

   sfi = ip6_lookup_exact_match (&db->dst_ip6_table, vni, dst_pref);

   if (is_add)
     {
       if (GID_LOOKUP_MISS == sfi)
 	{
 	  pool_get (db->src_ip6_table_pool, sfib);
 	  ip6_lookup_init (sfib);
 	  add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref,
 			   sfib - db->src_ip6_table_pool, is_add);
 	  if (src_pref)
 	    add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 	  else
 	    {
 	      ip_prefix_t sp;
 	      memset (&sp, 0, sizeof (sp));
 	      ip_prefix_version (&sp) = IP6;
 	      add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 	    }
 	}
       else
 	{
 	  ASSERT (!pool_is_free_index (db->src_ip6_table_pool, sfi));
 	  sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 	  if (src_pref)
 	    {
 	      old_val = ip6_lookup_exact_match (sfib, 0, src_pref);
 	      add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 	    }
 	  else
 	    {
 	      ip_prefix_t sp;
 	      memset (&sp, 0, sizeof (sp));
 	      ip_prefix_version (&sp) = IP6;
 	      old_val =
 		add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 	    }
 	}
     }
   else
     {
       if (GID_LOOKUP_MISS != sfi)
 	{
 	  add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref, 0, is_add);
 	  sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 	  if (src_pref)
 	    old_val = add_del_ip6_key (sfib, 0, src_pref, 0, is_add);
 	  else
 	    {
 	      ip_prefix_t sp;
 	      memset (&sp, 0, sizeof (sp));
 	      ip_prefix_version (&sp) = IP6;
 	      old_val = add_del_ip6_key (sfib, 0, &sp, 0, is_add);
 	    }
 	}
       else
 	clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
 		      dst_pref);
     }
   return old_val;
 }

 static u32
 add_del_ip (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_key,
 	    ip_prefix_t * src_key, u32 value, u8 is_add)
 {
   switch (ip_prefix_version (dst_key))
     {
     case IP4:
       return add_del_sd_ip4_key (db, vni, dst_key, src_key, value, is_add);
       break;
     case IP6:
       return add_del_sd_ip6_key (db, vni, dst_key, src_key, value, is_add);
       break;
     default:
       clib_warning ("address type %d not supported!",
 		    ip_prefix_version (dst_key));
       break;
     }
   return ~0;
 }

 static u32
 add_del_sd (gid_dictionary_t * db, u32 vni, source_dest_t * key, u32 value,
 	    u8 is_add)
 {
   switch (sd_dst_type (key))
     {
     case FID_ADDR_IP_PREF:
       add_del_ip (db, vni, &sd_dst_ippref (key), &sd_src_ippref (key),
 		  value, is_add);

     case FID_ADDR_MAC:
       return add_del_mac (&db->sd_mac_table, vni, sd_dst_mac (key),
 			  sd_src_mac (key), value, is_add);

     default:
       clib_warning ("SD address type %d not supprted!", sd_dst_type (key));
       break;
     }

   return ~0;
 }

 u32
 gid_dictionary_add_del (gid_dictionary_t * db, gid_address_t * key, u32 value,
 			u8 is_add)
 {
   switch (gid_address_type (key))
     {
     case GID_ADDR_IP_PREFIX:
       return add_del_ip (db, gid_address_vni (key), &gid_address_ippref (key),
 			 0, value, is_add);
     case GID_ADDR_MAC:
       return add_del_mac (&db->sd_mac_table, gid_address_vni (key),
 			  gid_address_mac (key), 0, value, is_add);
     case GID_ADDR_SRC_DST:
       return add_del_sd (db, gid_address_vni (key), &gid_address_sd (key),
 			 value, is_add);
     default:
       clib_warning ("address type %d not supported!", gid_address_type (key));
       break;
     }
   return ~0;
 }

 static void
 mac_lookup_init (gid_mac_table_t * db)
 {
   if (db->mac_lookup_table_nbuckets == 0)
     db->mac_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;

   db->mac_lookup_table_nbuckets =
     1 << max_log2 (db->mac_lookup_table_nbuckets);

   if (db->mac_lookup_table_size == 0)
     db->mac_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;

   BV (clib_bihash_init) (&db->mac_lookup_table, "mac lookup table",
 			 db->mac_lookup_table_nbuckets,
 			 db->mac_lookup_table_size);
 }

 void
 gid_dictionary_init (gid_dictionary_t * db)
 {
   ip4_lookup_init (&db->dst_ip4_table);
   ip6_lookup_init (&db->dst_ip6_table);
   mac_lookup_init (&db->sd_mac_table);
 }

 /*
  * fd.io coding-style-patch-verification: ON
  *
  * Local Variables:
  * eval: (c-set-style "gnu")
  * End:
  */
	/*
	* Copyright (c) 2016 Cisco and/or its affiliates.
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at:
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include <vnet/lisp-cp/gid_dictionary.h>

	typedef struct
	{
	void *arg;
	ip_prefix_t src;
	foreach_subprefix_match_cb_t cb;
	union
	{
	gid_ip4_table_t *ip4_table;
	gid_ip6_table_t *ip6_table;
	};
	} sfib_entry_arg_t;

	static u32 ip4_lookup (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key);

	static u32 ip6_lookup (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key);

	static void
	foreach_sfib4_subprefix (BVT (clib_bihash_kv) * kvp, void *arg)
	{
	sfib_entry_arg_t *a = arg;
	u32 ip = (u32) kvp->key[0];
	ip4_address_t *mask;
	u8 plen = ip_prefix_len (&a->src);

	ASSERT (plen <= 32);
	mask = &a->ip4_table->ip4_fib_masks[plen];

	u32 src_ip = ip_prefix_v4 (&a->src).as_u32;
	src_ip &= mask->as_u32;
	ip &= mask->as_u32;

	if (src_ip == ip)
	{
	/* found sub-prefix of src prefix */
	(a->cb) (kvp->value, a->arg);
	}
	}

	static void
	gid_dict_foreach_ip4_subprefix (gid_dictionary_t * db, u32 vni,
	ip_prefix_t * src, ip_prefix_t * dst,
	foreach_subprefix_match_cb_t cb, void *arg)
	{
	u32 sfi;
	gid_ip4_table_t *sfib4;
	sfib_entry_arg_t a;

	sfi = ip4_lookup (&db->dst_ip4_table, vni, dst);
	if (GID_LOOKUP_MISS == sfi)
	return;

	sfib4 = pool_elt_at_index (db->src_ip4_table_pool, sfi);

	a.arg = arg;
	a.cb = cb;
	a.src = src[0];
	a.ip4_table = sfib4;

	BV (clib_bihash_foreach_key_value_pair) (&sfib4->ip4_lookup_table,
	foreach_sfib4_subprefix, &a);
	}

	static void
	foreach_sfib6_subprefix (BVT (clib_bihash_kv) * kvp, void *arg)
	{
	sfib_entry_arg_t *a = arg;
	ip6_address_t ip;
	ip6_address_t *mask;
	u8 plen = ip_prefix_len (&a->src);

	mask = &a->ip6_table->ip6_fib_masks[plen];
	ip.as_u64[0] = kvp->key[0];
	ip.as_u64[1] = kvp->key[1];

	if (ip6_address_is_equal_masked (&ip_prefix_v6 (&a->src), &ip, mask))
	{
	/* found sub-prefix of src prefix */
	(a->cb) (kvp->value, a->arg);
	}
	}

	static void
	gid_dict_foreach_ip6_subprefix (gid_dictionary_t * db, u32 vni,
	ip_prefix_t * src, ip_prefix_t * dst,
	foreach_subprefix_match_cb_t cb, void *arg)
	{
	u32 sfi;
	gid_ip6_table_t *sfib6;
	sfib_entry_arg_t a;

	sfi = ip6_lookup (&db->dst_ip6_table, vni, dst);
	if (GID_LOOKUP_MISS == sfi)
	return;

	sfib6 = pool_elt_at_index (db->src_ip6_table_pool, sfi);

	a.arg = arg;
	a.cb = cb;
	a.src = src[0];
	a.ip6_table = sfib6;

	BV (clib_bihash_foreach_key_value_pair) (&sfib6->ip6_lookup_table,
	foreach_sfib6_subprefix, &a);
	}

	void
	gid_dict_foreach_subprefix (gid_dictionary_t * db, gid_address_t * eid,
	foreach_subprefix_match_cb_t cb, void *arg)
	{
	ip_prefix_t *ippref = &gid_address_sd_dst_ippref (eid);

	if (IP4 == ip_prefix_version (ippref))
	gid_dict_foreach_ip4_subprefix (db, gid_address_vni (eid),
	&gid_address_sd_src_ippref (eid),
	&gid_address_sd_dst_ippref (eid), cb,
	arg);
	else
	gid_dict_foreach_ip6_subprefix (db, gid_address_vni (eid),
	&gid_address_sd_src_ippref (eid),
	&gid_address_sd_dst_ippref (eid), cb,
	arg);
	}

	static void
	make_mac_sd_key (BVT (clib_bihash_kv) * kv, u32 vni, u8 src_mac[6],
	u8 dst_mac[6])
	{
	kv->key[0] = (u64) vni;
	kv->key[1] = mac_to_u64 (dst_mac);
	kv->key[2] = src_mac ? mac_to_u64 (src_mac) : (u64) 0;
	}

	static u32
	mac_sd_lookup (gid_mac_table_t * db, u32 vni, u8 * dst, u8 * src)
	{
	int rv;
	BVT (clib_bihash_kv) kv, value;

	make_mac_sd_key (&kv, vni, src, dst);
	rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv, &value);

	/* no match, try with src 0, catch all for dst */
	if (rv != 0)
	{
	kv.key[2] = 0;
	rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv,
	&value);
	if (rv == 0)
	return value.value;
	}
	else
	return value.value;

	return GID_LOOKUP_MISS;
	}

	static u32
	ip4_lookup_exact_match (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
	{
	int rv;
	BVT (clib_bihash_kv) kv, value;

	ip4_address_t *mask;

	mask = &db->ip4_fib_masks[ip_prefix_len (key)];

	kv.key[0] = ((u64) vni << 32) \| (ip_prefix_v4 (key).as_u32 & mask->as_u32);
	kv.key[1] = 0;
	kv.key[2] = 0;

	rv = BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
	if (rv == 0)
	return value.value;

	return GID_LOOKUP_MISS;
	}

	static u32
	ip4_lookup (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
	{
	int i, len;
	int rv;
	BVT (clib_bihash_kv) kv, value;

	len = vec_len (db->ip4_prefix_lengths_in_search_order);

	for (i = 0; i < len; i++)
	{
	int dst_address_length = db->ip4_prefix_lengths_in_search_order[i];
	ip4_address_t *mask;

	ASSERT (dst_address_length >= 0 && dst_address_length <= 32);

	mask = &db->ip4_fib_masks[dst_address_length];

	kv.key[0] =
	((u64) vni << 32) \| (ip_prefix_v4 (key).as_u32 & mask->as_u32);
	kv.key[1] = 0;
	kv.key[2] = 0;

	rv =
	BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
	if (rv == 0)
	return value.value;
	}

	return GID_LOOKUP_MISS;
	}

	static u32
	ip6_lookup_exact_match (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
	{
	int rv;
	BVT (clib_bihash_kv) kv, value;

	ip6_address_t *mask;
	mask = &db->ip6_fib_masks[ip_prefix_len (key)];

	kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
	kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
	kv.key[2] = (u64) vni;

	rv = BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
	if (rv == 0)
	return value.value;

	return GID_LOOKUP_MISS;
	}

	static u32
	ip6_lookup (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
	{
	int i, len;
	int rv;
	BVT (clib_bihash_kv) kv, value;

	len = vec_len (db->ip6_prefix_lengths_in_search_order);

	for (i = 0; i < len; i++)
	{
	int dst_address_length = db->ip6_prefix_lengths_in_search_order[i];
	ip6_address_t *mask;

	ASSERT (dst_address_length >= 0 && dst_address_length <= 128);

	mask = &db->ip6_fib_masks[dst_address_length];

	kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
	kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
	kv.key[2] = (u64) vni;

	rv =
	BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
	if (rv == 0)
	return value.value;
	}

	return GID_LOOKUP_MISS;
	}

	static u32
	ip_sd_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst,
	ip_prefix_t * src)
	{
	u32 sfi;
	gid_ip4_table_t *sfib4;
	gid_ip6_table_t *sfib6;

	switch (ip_prefix_version (dst))
	{
	case IP4:
	sfi = ip4_lookup (&db->dst_ip4_table, vni, dst);
	if (GID_LOOKUP_MISS != sfi)
	sfib4 = pool_elt_at_index (db->src_ip4_table_pool, sfi);
	else
	return GID_LOOKUP_MISS;

	if (!src)
	{
	ip_prefix_t sp;
	memset (&sp, 0, sizeof (sp));
	return ip4_lookup_exact_match (sfib4, 0, &sp);
	}
	else
	return ip4_lookup (sfib4, 0, src);

	break;
	case IP6:
	sfi = ip6_lookup (&db->dst_ip6_table, vni, dst);
	if (GID_LOOKUP_MISS != sfi)
	sfib6 = pool_elt_at_index (db->src_ip6_table_pool, sfi);
	else
	return GID_LOOKUP_MISS;

	if (!src)
	{
	ip_prefix_t sp;
	memset (&sp, 0, sizeof (sp));
	ip_prefix_version (&sp) = IP6;
	return ip6_lookup_exact_match (sfib6, 0, &sp);
	}
	else
	return ip6_lookup (sfib6, 0, src);

	break;
	default:
	clib_warning ("address type %d not supported!",
	ip_prefix_version (dst));
	break;
	}
	return GID_LOOKUP_MISS;
	}

	u32
	gid_dictionary_lookup (gid_dictionary_t * db, gid_address_t * key)
	{
	switch (gid_address_type (key))
	{
	case GID_ADDR_IP_PREFIX:
	return ip_sd_lookup (db, gid_address_vni (key),
	&gid_address_ippref (key), 0);
	case GID_ADDR_MAC:
	return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
	gid_address_mac (key), 0);
	case GID_ADDR_SRC_DST:
	switch (gid_address_sd_dst_type (key))
	{
	case FID_ADDR_IP_PREF:
	return ip_sd_lookup (db, gid_address_vni (key),
	&gid_address_sd_dst_ippref (key),
	&gid_address_sd_src_ippref (key));
	break;
	case FID_ADDR_MAC:
	return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
	gid_address_sd_dst_mac (key),
	gid_address_sd_src_mac (key));
	break;
	default:
	clib_warning ("Source/Dest address type %d not supported!",
	gid_address_sd_dst_type (key));
	break;
	}
	break;
	default:
	clib_warning ("address type %d not supported!", gid_address_type (key));
	break;
	}
	return GID_LOOKUP_MISS;
	}

	u32
	gid_dictionary_sd_lookup (gid_dictionary_t * db, gid_address_t * dst,
	gid_address_t * src)
	{
	switch (gid_address_type (dst))
	{
	case GID_ADDR_IP_PREFIX:
	return ip_sd_lookup (db, gid_address_vni (dst),
	&gid_address_ippref (dst),
	&gid_address_ippref (src));
	case GID_ADDR_MAC:
	return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
	gid_address_mac (dst), gid_address_mac (src));
	case GID_ADDR_SRC_DST:
	switch (gid_address_sd_dst_type (dst))
	{
	case FID_ADDR_IP_PREF:
	return ip_sd_lookup (db, gid_address_vni (dst),
	&gid_address_sd_dst_ippref (dst),
	&gid_address_sd_src_ippref (dst));
	break;
	case FID_ADDR_MAC:
	return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
	gid_address_sd_dst_mac (dst),
	gid_address_sd_src_mac (dst));
	break;
	default:
	clib_warning ("Source/Dest address type %d not supported!",
	gid_address_sd_dst_type (dst));
	break;
	}
	break;
	default:
	clib_warning ("address type %d not supported!", gid_address_type (dst));
	break;
	}
	return GID_LOOKUP_MISS;
	}

	static void
	ip4_compute_prefix_lengths_in_search_order (gid_ip4_table_t * db)
	{
	int i;
	vec_reset_length (db->ip4_prefix_lengths_in_search_order);
	/* Note: bitmap reversed so this is in fact a longest prefix match */

	/* INDENT-OFF */
	clib_bitmap_foreach (i, db->ip4_non_empty_dst_address_length_bitmap,
	({
	int dst_address_length = 32 - i;
	vec_add1 (db->ip4_prefix_lengths_in_search_order, dst_address_length);
	}));
	/* INDENT-ON */

	}

	static u32
	add_del_ip4_key (gid_ip4_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
	u8 is_add)
	{
	BVT (clib_bihash_kv) kv, value;
	u32 old_val = ~0;
	ip4_address_t key;
	u8 plen = ip_prefix_len (pref);

	clib_memcpy (&key, &ip_prefix_v4 (pref), sizeof (key));
	key.as_u32 &= db->ip4_fib_masks[plen].as_u32;
	if (is_add)
	{
	db->ip4_non_empty_dst_address_length_bitmap =
	clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
	32 - plen, 1);
	ip4_compute_prefix_lengths_in_search_order (db);

	db->ip4_prefix_len_refcount[plen]++;
	}
	else
	{
	ASSERT (db->ip4_prefix_len_refcount[plen] != 0);

	db->ip4_prefix_len_refcount[plen]--;

	if (db->ip4_prefix_len_refcount[plen] == 0)
	{
	db->ip4_non_empty_dst_address_length_bitmap =
	clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
	32 - plen, 0);
	ip4_compute_prefix_lengths_in_search_order (db);
	}
	}

	kv.key[0] = ((u64) vni << 32) \| key.as_u32;
	kv.key[1] = 0;
	kv.key[2] = 0;

	if (BV (clib_bihash_search) (&db->ip4_lookup_table, &kv, &value) == 0)
	old_val = value.value;

	if (!is_add)
	BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 0 /* is_add */ );
	else
	{
	kv.value = val;
	BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 1 /* is_add */ );
	}
	return old_val;
	}

	static void
	ip4_lookup_init (gid_ip4_table_t * db)
	{
	uword i;

	memset (db->ip4_prefix_len_refcount, 0,
	sizeof (db->ip4_prefix_len_refcount));

	for (i = 0; i < ARRAY_LEN (db->ip4_fib_masks); i++)
	{
	u32 m;

	if (i < 32)
	m = pow2_mask (i) << (32 - i);
	else
	m = ~0;
	db->ip4_fib_masks[i].as_u32 = clib_host_to_net_u32 (m);
	}
	if (db->ip4_lookup_table_nbuckets == 0)
	db->ip4_lookup_table_nbuckets = IP4_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;

	db->ip4_lookup_table_nbuckets =
	1 << max_log2 (db->ip4_lookup_table_nbuckets);

	if (db->ip4_lookup_table_size == 0)
	db->ip4_lookup_table_size = IP4_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;

	BV (clib_bihash_init) (&db->ip4_lookup_table, "ip4 lookup table",
	db->ip4_lookup_table_nbuckets,
	db->ip4_lookup_table_size);
	}

	static u32
	add_del_sd_ip4_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
	ip_prefix_t * src_pref, u32 val, u8 is_add)
	{
	u32 sfi, old_val = ~0;
	gid_ip4_table_t *sfib;

	sfi = ip4_lookup_exact_match (&db->dst_ip4_table, vni, dst_pref);

	if (is_add)
	{
	if (GID_LOOKUP_MISS == sfi)
	{
	pool_get (db->src_ip4_table_pool, sfib);
	ip4_lookup_init (sfib);
	add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref,
	sfib - db->src_ip4_table_pool, is_add);
	if (src_pref)
	add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
	else
	{
	ip_prefix_t sp;
	memset (&sp, 0, sizeof (sp));
	add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
	}
	}
	else
	{
	ASSERT (!pool_is_free_index (db->src_ip4_table_pool, sfi));
	sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
	if (src_pref)
	{
	old_val = ip4_lookup_exact_match (sfib, 0, src_pref);
	add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
	}
	else
	{
	ip_prefix_t sp;
	memset (&sp, 0, sizeof (sp));
	old_val =
	add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
	}
	}
	}
	else
	{
	if (GID_LOOKUP_MISS != sfi)
	{
	add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref, 0, is_add);
	sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
	if (src_pref)
	old_val = add_del_ip4_key (sfib, 0, src_pref, 0, is_add);
	else
	{
	ip_prefix_t sp;
	memset (&sp, 0, sizeof (sp));
	old_val = add_del_ip4_key (sfib, 0, &sp, 0, is_add);
	}
	}
	else
	clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
	dst_pref);
	}
	return old_val;
	}

	static void
	ip6_compute_prefix_lengths_in_search_order (gid_ip6_table_t * db)
	{
	int i;
	vec_reset_length (db->ip6_prefix_lengths_in_search_order);
	/* Note: bitmap reversed so this is in fact a longest prefix match */

	/* INDENT-OFF */
	clib_bitmap_foreach (i, db->ip6_non_empty_dst_address_length_bitmap,
	({
	int dst_address_length = 128 - i;
	vec_add1 (db->ip6_prefix_lengths_in_search_order, dst_address_length);
	}));
	/* INDENT-ON */
	}

	static u32
	add_del_ip6_key (gid_ip6_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
	u8 is_add)
	{
	BVT (clib_bihash_kv) kv, value;
	u32 old_val = ~0;
	ip6_address_t key;
	u8 plen = ip_prefix_len (pref);

	clib_memcpy (&key, &ip_prefix_v6 (pref), sizeof (key));
	ip6_address_mask (&key, &db->ip6_fib_masks[plen]);
	if (is_add)
	{
	db->ip6_non_empty_dst_address_length_bitmap =
	clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
	128 - plen, 1);
	ip6_compute_prefix_lengths_in_search_order (db);
	db->ip6_prefix_len_refcount[plen]++;
	}
	else
	{
	ASSERT (db->ip6_prefix_len_refcount[plen] != 0);

	db->ip6_prefix_len_refcount[plen]--;

	if (db->ip6_prefix_len_refcount[plen] == 0)
	{
	db->ip6_non_empty_dst_address_length_bitmap =
	clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
	128 - plen, 0);
	ip6_compute_prefix_lengths_in_search_order (db);
	}
	}

	kv.key[0] = key.as_u64[0];
	kv.key[1] = key.as_u64[1];
	kv.key[2] = (u64) vni;
	// kv.key[2] = ((u64)((fib - im->fibs))<<32) \| ip_prefix_len(key);

	if (BV (clib_bihash_search) (&db->ip6_lookup_table, &kv, &value) == 0)
	old_val = value.value;

	if (!is_add)
	BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 0 /* is_add */ );
	else
	{
	kv.value = val;
	BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 1 /* is_add */ );
	}
	return old_val;
	}

	static u32
	add_del_mac (gid_mac_table_t * db, u32 vni, u8 * dst_mac, u8 * src_mac,
	u32 val, u8 is_add)
	{
	BVT (clib_bihash_kv) kv, value;
	u32 old_val = ~0;

	make_mac_sd_key (&kv, vni, src_mac, dst_mac);

	if (BV (clib_bihash_search) (&db->mac_lookup_table, &kv, &value) == 0)
	old_val = value.value;

	if (!is_add)
	BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 0 /* is_add */ );
	else
	{
	kv.value = val;
	BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 1 /* is_add */ );
	}
	return old_val;
	}

	static void
	ip6_lookup_init (gid_ip6_table_t * db)
	{
	uword i;

	memset (db->ip6_prefix_len_refcount, 0,
	sizeof (db->ip6_prefix_len_refcount));

	for (i = 0; i < ARRAY_LEN (db->ip6_fib_masks); i++)
	{
	u32 j, i0, i1;

	i0 = i / 32;
	i1 = i % 32;

	for (j = 0; j < i0; j++)
	db->ip6_fib_masks[i].as_u32[j] = ~0;

	if (i1)
	db->ip6_fib_masks[i].as_u32[i0] =
	clib_host_to_net_u32 (pow2_mask (i1) << (32 - i1));
	}

	if (db->ip6_lookup_table_nbuckets == 0)
	db->ip6_lookup_table_nbuckets = IP6_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;

	db->ip6_lookup_table_nbuckets =
	1 << max_log2 (db->ip6_lookup_table_nbuckets);

	if (db->ip6_lookup_table_size == 0)
	db->ip6_lookup_table_size = IP6_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;

	BV (clib_bihash_init) (&db->ip6_lookup_table, "ip6 lookup table",
	db->ip6_lookup_table_nbuckets,
	db->ip6_lookup_table_size);
	}

	static u32
	add_del_sd_ip6_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
	ip_prefix_t * src_pref, u32 val, u8 is_add)
	{
	u32 sfi, old_val = ~0;
	gid_ip6_table_t *sfib;

	sfi = ip6_lookup_exact_match (&db->dst_ip6_table, vni, dst_pref);

	if (is_add)
	{
	if (GID_LOOKUP_MISS == sfi)
	{
	pool_get (db->src_ip6_table_pool, sfib);
	ip6_lookup_init (sfib);
	add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref,
	sfib - db->src_ip6_table_pool, is_add);
	if (src_pref)
	add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
	else
	{
	ip_prefix_t sp;
	memset (&sp, 0, sizeof (sp));
	ip_prefix_version (&sp) = IP6;
	add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
	}
	}
	else
	{
	ASSERT (!pool_is_free_index (db->src_ip6_table_pool, sfi));
	sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
	if (src_pref)
	{
	old_val = ip6_lookup_exact_match (sfib, 0, src_pref);
	add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
	}
	else
	{
	ip_prefix_t sp;
	memset (&sp, 0, sizeof (sp));
	ip_prefix_version (&sp) = IP6;
	old_val =
	add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
	}
	}
	}
	else
	{
	if (GID_LOOKUP_MISS != sfi)
	{
	add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref, 0, is_add);
	sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
	if (src_pref)
	old_val = add_del_ip6_key (sfib, 0, src_pref, 0, is_add);
	else
	{
	ip_prefix_t sp;
	memset (&sp, 0, sizeof (sp));
	ip_prefix_version (&sp) = IP6;
	old_val = add_del_ip6_key (sfib, 0, &sp, 0, is_add);
	}
	}
	else
	clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
	dst_pref);
	}
	return old_val;
	}

	static u32
	add_del_ip (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_key,
	ip_prefix_t * src_key, u32 value, u8 is_add)
	{
	switch (ip_prefix_version (dst_key))
	{
	case IP4:
	return add_del_sd_ip4_key (db, vni, dst_key, src_key, value, is_add);
	break;
	case IP6:
	return add_del_sd_ip6_key (db, vni, dst_key, src_key, value, is_add);
	break;
	default:
	clib_warning ("address type %d not supported!",
	ip_prefix_version (dst_key));
	break;
	}
	return ~0;
	}

	static u32
	add_del_sd (gid_dictionary_t * db, u32 vni, source_dest_t * key, u32 value,
	u8 is_add)
	{
	switch (sd_dst_type (key))
	{
	case FID_ADDR_IP_PREF:
	add_del_ip (db, vni, &sd_dst_ippref (key), &sd_src_ippref (key),
	value, is_add);

	case FID_ADDR_MAC:
	return add_del_mac (&db->sd_mac_table, vni, sd_dst_mac (key),
	sd_src_mac (key), value, is_add);

	default:
	clib_warning ("SD address type %d not supprted!", sd_dst_type (key));
	break;
	}

	return ~0;
	}

	u32
	gid_dictionary_add_del (gid_dictionary_t * db, gid_address_t * key, u32 value,
	u8 is_add)
	{
	switch (gid_address_type (key))
	{
	case GID_ADDR_IP_PREFIX:
	return add_del_ip (db, gid_address_vni (key), &gid_address_ippref (key),
	0, value, is_add);
	case GID_ADDR_MAC:
	return add_del_mac (&db->sd_mac_table, gid_address_vni (key),
	gid_address_mac (key), 0, value, is_add);
	case GID_ADDR_SRC_DST:
	return add_del_sd (db, gid_address_vni (key), &gid_address_sd (key),
	value, is_add);
	default:
	clib_warning ("address type %d not supported!", gid_address_type (key));
	break;
	}
	return ~0;
	}

	static void
	mac_lookup_init (gid_mac_table_t * db)
	{
	if (db->mac_lookup_table_nbuckets == 0)
	db->mac_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;

	db->mac_lookup_table_nbuckets =
	1 << max_log2 (db->mac_lookup_table_nbuckets);

	if (db->mac_lookup_table_size == 0)
	db->mac_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;

	BV (clib_bihash_init) (&db->mac_lookup_table, "mac lookup table",
	db->mac_lookup_table_nbuckets,
	db->mac_lookup_table_size);
	}

	void
	gid_dictionary_init (gid_dictionary_t * db)
	{
	ip4_lookup_init (&db->dst_ip4_table);
	ip6_lookup_init (&db->dst_ip6_table);
	mac_lookup_init (&db->sd_mac_table);
	}

	/*
	* fd.io coding-style-patch-verification: ON
	*
	* Local Variables:
	* eval: (c-set-style "gnu")
	* End:
	*/