LoadBal: Use intrinsics and use protocol number 94/3394/3
authorPierre Pfister <ppfister@cisco.com>
Thu, 13 Oct 2016 12:36:18 +0000 (13:36 +0100)
committerDamjan Marion <dmarion.lists@gmail.com>
Tue, 18 Oct 2016 08:17:27 +0000 (08:17 +0000)
This patch modifies the load balancer hash table such that
it uses vector operations.

It also fixes the hash computation logic such that the port
is only looked-up for TCP and UDP.
Some additional work is still needed for other types of traffic.

Change-Id: I788b4c782a9923d3792f3985f0580c0c81b3aad3
Signed-off-by: Pierre Pfister <ppfister@cisco.com>
plugins/lb-plugin/lb/lb.h
plugins/lb-plugin/lb/lbhash.h
plugins/lb-plugin/lb/node.c

index 09cfde3..882b9b3 100644 (file)
@@ -116,8 +116,10 @@ typedef struct {
 } lb_new_flow_entry_t;
 
 #define lb_foreach_vip_counter \
- _(TRACKED_SESSION, "tracked session", 0) \
- _(UNTRACKED_PACKET, "untracked packet", 1)
+ _(NEXT_PACKET, "packet from existing sessions", 0) \
+ _(FIRST_PACKET, "first session packet", 1) \
+ _(UNTRACKED_PACKET, "untracked packet", 2) \
+ _(NO_SERVER, "no server configured", 3)
 
 typedef enum {
 #define _(a,b,c) LB_VIP_COUNTER_##a = c,
index 12e8925..d47b498 100644 (file)
 
 #include <vnet/vnet.h>
 
-#define LBHASH_ENTRY_PER_BUCKET_LOG2 2
-#define LBHASH_ENTRY_PER_BUCKET (1 << LBHASH_ENTRY_PER_BUCKET_LOG2)
-#define LBHASH_ENTRY_PER_BUCKET_MASK (LBHASH_ENTRY_PER_BUCKET - 1)
+#include <immintrin.h>
 
+/*
+ * @brief Number of entries per bucket.
+ */
+#define LBHASH_ENTRY_PER_BUCKET 4
+
+#define LB_HASH_DO_NOT_USE_SSE_BUCKETS 0
+
+/*
+ * @brief One bucket contains 4 entries.
+ * Each bucket takes one 64B cache line in memory.
+ */
 typedef struct {
-  u64 key[5];
-  u32 value;
-  u32 last_seen;
-} lb_hash_entry_t;
+  CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
+  u32 hash[LBHASH_ENTRY_PER_BUCKET];
+  u32 timeout[LBHASH_ENTRY_PER_BUCKET];
+  u32 vip[LBHASH_ENTRY_PER_BUCKET];
+  u32 value[LBHASH_ENTRY_PER_BUCKET];
+} lb_hash_bucket_t;
 
 typedef struct {
   u32 buckets_mask;
   u32 timeout;
-  lb_hash_entry_t entries[];
+  lb_hash_bucket_t buckets[];
 } lb_hash_t;
 
-#define lb_hash_nbuckets(h) (((h)->buckets_mask >> LBHASH_ENTRY_PER_BUCKET_LOG2) + 1)
+#define lb_hash_nbuckets(h) (((h)->buckets_mask) + 1)
 #define lb_hash_size(h) ((h)->buckets_mask + LBHASH_ENTRY_PER_BUCKET)
 
-#define lb_hash_foreach_entry(h, e) \
-  for (e = (h)->entries; e < h->entries + lb_hash_size(h); e++)
+#define lb_hash_foreach_bucket(h, bucket) \
+  for (bucket = (h)->buckets; \
+       bucket < (h)->buckets + lb_hash_nbuckets(h); \
+       bucket++)
+
+#define lb_hash_foreach_entry(h, bucket, i) \
+    lb_hash_foreach_bucket(h, bucket) \
+      for (i = 0; i < LBHASH_ENTRY_PER_BUCKET; i++)
 
-#define lb_hash_foreach_valid_entry(h, e, now) \
-    lb_hash_foreach_entry(h, e) \
-       if (!clib_u32_loop_gt((now), (e)->last_seen + (h)->timeout))
+#define lb_hash_foreach_valid_entry(h, bucket, i, now) \
+    lb_hash_foreach_entry(h, bucket, i) \
+       if (!clib_u32_loop_gt((now), bucket->timeout[i]))
 
 static_always_inline
 lb_hash_t *lb_hash_alloc(u32 buckets, u32 timeout)
 {
-  if ((!is_pow2(buckets)) ||
-      ((buckets << LBHASH_ENTRY_PER_BUCKET_LOG2) == 0))
+  if (!is_pow2(buckets))
     return NULL;
 
   // Allocate 1 more bucket for prefetch
-  u32 size = sizeof(lb_hash_t) + ((buckets << LBHASH_ENTRY_PER_BUCKET_LOG2) + 1)* sizeof(lb_hash_entry_t);
+  u32 size = ((u64)&((lb_hash_t *)(0))->buckets[0]) +
+      sizeof(lb_hash_bucket_t) * (buckets + 1);
   u8 *mem = 0;
   lb_hash_t *h;
   vec_alloc_aligned(mem, size, CLIB_CACHE_LINE_BYTES);
   h = (lb_hash_t *)mem;
-  h->buckets_mask = (buckets - 1) << LBHASH_ENTRY_PER_BUCKET_LOG2;
+  h->buckets_mask = (buckets - 1);
   h->timeout = timeout;
   return h;
 }
@@ -78,102 +95,117 @@ lb_hash_t *lb_hash_alloc(u32 buckets, u32 timeout)
 static_always_inline
 void lb_hash_free(lb_hash_t *h)
 {
-  vec_free(h);
+  u8 *mem = (u8 *)h;
+  vec_free(mem);
 }
 
 #if __SSE4_2__
 static_always_inline
-u32 lb_hash_crc_u32(u32 data, u32 value)
-{
-  __asm__ volatile( "crc32l %[data], %[value];"
-                    : [value] "+r" (value)
-                    : [data] "rm" (data));
-  return value;
-}
-
-static_always_inline
-u32 lb_hash_hash(u64 k[5])
+u32 lb_hash_hash(u64 k0, u64 k1, u64 k2, u64 k3, u64 k4)
 {
-  u32 * dp = (u32 *) k;
-  u32 value = 0;
-
-  value = lb_hash_crc_u32 (dp[0], value);
-  value = lb_hash_crc_u32 (dp[1], value);
-  value = lb_hash_crc_u32 (dp[2], value);
-  value = lb_hash_crc_u32 (dp[3], value);
-  value = lb_hash_crc_u32 (dp[4], value);
-  value = lb_hash_crc_u32 (dp[5], value);
-  value = lb_hash_crc_u32 (dp[6], value);
-  value = lb_hash_crc_u32 (dp[7], value);
-  value = lb_hash_crc_u32 (dp[8], value);
-  value = lb_hash_crc_u32 (dp[9], value);
-  return value;
+  u64 val = 0;
+  val = _mm_crc32_u64(val, k0);
+  val = _mm_crc32_u64(val, k1);
+  val = _mm_crc32_u64(val, k2);
+  val = _mm_crc32_u64(val, k3);
+  val = _mm_crc32_u64(val, k4);
+  return (u32) val;
 }
 #else
 static_always_inline
-u32 lb_hash_hash(u64 k[5])
+u32 lb_hash_hash(u64 k0, u64 k1, u64 k2, u64 k3, u64 k4)
 {
-  u64 tmp = k[0] ^ k[1] ^ k[2] ^ k[3] ^ k[4];
+  u64 tmp = k0 ^ k1 ^ k2 ^ k3 ^ k4;
   return (u32)clib_xxhash (tmp);
 }
 #endif
 
-
+static_always_inline
+void lb_hash_prefetch_bucket(lb_hash_t *ht, u32 hash)
+{
+  lb_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
+  CLIB_PREFETCH(bucket, sizeof(*bucket), READ);
+}
 
 static_always_inline
-void lb_hash_get(lb_hash_t *h, u64 k[5], u32 hash, u32 time_now, u32 *available_index, u32 *value)
+void lb_hash_get(lb_hash_t *ht, u32 hash, u32 vip, u32 time_now,
+                u32 *available_index, u32 *found_value)
 {
-  lb_hash_entry_t *e = &h->entries[hash & h->buckets_mask];
-  u32 i;
-  *value = ~0;
+  lb_hash_bucket_t *bucket = &ht->buckets[hash & ht->buckets_mask];
+  *found_value = ~0;
   *available_index = ~0;
-  CLIB_PREFETCH (&(e[1]), sizeof(lb_hash_entry_t), STORE);
-  for (i=0; i<LBHASH_ENTRY_PER_BUCKET; i++) {
-    CLIB_PREFETCH (&(e[i+2]), sizeof(lb_hash_entry_t), STORE); //+2 somehow performs best
-    u64 cmp =
-        (e[i].key[0] ^ k[0]) |
-        (e[i].key[1] ^ k[1]) |
-        (e[i].key[2] ^ k[2]) |
-        (e[i].key[3] ^ k[3]) |
-        (e[i].key[4] ^ k[4]);
-
-    u8 timeouted = clib_u32_loop_gt(time_now, e[i].last_seen + h->timeout);
-
-    *value = (cmp || timeouted)?*value:e[i].value;
-    e[i].last_seen = (cmp || timeouted)?e[i].last_seen:time_now;
-    *available_index = (timeouted && (*available_index == ~0))?(&e[i] - h->entries):*available_index;
-
-    if (!cmp)
-      return;
+#if __SSE4_2__ && LB_HASH_DO_NOT_USE_SSE_BUCKETS == 0
+  u32 bitmask, found_index;
+  __m128i mask;
+
+  // mask[*] = timeout[*] > now
+  mask = _mm_cmpgt_epi32(_mm_loadu_si128 ((__m128i *) bucket->timeout),
+                        _mm_set1_epi32 (time_now));
+  // bitmask[*] = now <= timeout[*/4]
+  bitmask = (~_mm_movemask_epi8(mask)) & 0xffff;
+  // Get first index with now <= timeout[*], if any.
+  *available_index = (bitmask)?__builtin_ctz(bitmask)/4:*available_index;
+
+  // mask[*] = (timeout[*] > now) && (hash[*] == hash)
+  mask = _mm_and_si128(mask,
+                      _mm_cmpeq_epi32(
+                          _mm_loadu_si128 ((__m128i *) bucket->hash),
+                          _mm_set1_epi32 (hash)));
+
+  // Load the array of vip values
+  // mask[*] = (timeout[*] > now) && (hash[*] == hash) && (vip[*] == vip)
+  mask = _mm_and_si128(mask,
+                      _mm_cmpeq_epi32(
+                          _mm_loadu_si128 ((__m128i *) bucket->vip),
+                          _mm_set1_epi32 (vip)));
+
+  // mask[*] = (timeout[*x4] > now) && (hash[*x4] == hash) && (vip[*x4] == vip)
+  bitmask = _mm_movemask_epi8(mask);
+  // Get first index, if any
+  found_index = (bitmask)?__builtin_ctzll(bitmask)/4:0;
+  ASSERT(found_index < 4);
+  *found_value = (bitmask)?bucket->value[found_index]:*found_value;
+  bucket->timeout[found_index] =
+      (bitmask)?time_now + ht->timeout:bucket->timeout[found_index];
+#else
+  u32 i;
+  for (i = 0; i < LBHASH_ENTRY_PER_BUCKET; i++) {
+      u8 cmp = (bucket->hash[i] == hash && bucket->vip[i] == vip);
+      u8 timeouted = clib_u32_loop_gt(time_now, bucket->timeout[i]);
+      *found_value = (cmp || timeouted)?*found_value:bucket->value[i];
+      bucket->timeout[i] = (cmp || timeouted)?time_now + ht->timeout:bucket->timeout[i];
+      *available_index = (timeouted && (*available_index == ~0))?i:*available_index;
+
+      if (!cmp)
+       return;
   }
+#endif
 }
 
 static_always_inline
-u32 lb_hash_available_value(lb_hash_t *h, u32 available_index)
+u32 lb_hash_available_value(lb_hash_t *h, u32 hash, u32 available_index)
 {
-  return h->entries[available_index].value;
+  return h->buckets[hash & h->buckets_mask].value[available_index];
 }
 
 static_always_inline
-u32 lb_hash_put(lb_hash_t *h, u64 k[5], u32 value, u32 available_index, u32 time_now)
+void lb_hash_put(lb_hash_t *h, u32 hash, u32 value, u32 vip,
+                u32 available_index, u32 time_now)
 {
-  lb_hash_entry_t *e = &h->entries[available_index];
-  e->key[0] = k[0];
-  e->key[1] = k[1];
-  e->key[2] = k[2];
-  e->key[3] = k[3];
-  e->key[4] = k[4];
-  e->value = value;
-  e->last_seen = time_now;
-  return 0;
+  lb_hash_bucket_t *bucket = &h->buckets[hash & h->buckets_mask];
+  bucket->hash[available_index] = hash;
+  bucket->value[available_index] = value;
+  bucket->timeout[available_index] = time_now + h->timeout;
+  bucket->vip[available_index] = vip;
 }
 
 static_always_inline
 u32 lb_hash_elts(lb_hash_t *h, u32 time_now)
 {
   u32 tot = 0;
-  lb_hash_entry_t *e;
-  lb_hash_foreach_valid_entry(h, e, time_now) {
+  lb_hash_bucket_t *bucket;
+  u32 i;
+  lb_hash_foreach_valid_entry(h, bucket, i, time_now) {
     tot++;
   }
   return tot;
index 82f0cb5..8b763c5 100644 (file)
@@ -20,8 +20,7 @@
 
 #define foreach_lb_error \
  _(NONE, "no error") \
- _(PROTO_NOT_SUPPORTED, "protocol not supported") \
- _(NO_SERVER, "no configured application server")
+ _(PROTO_NOT_SUPPORTED, "protocol not supported")
 
 typedef enum {
 #define _(sym,str) LB_ERROR_##sym,
@@ -66,19 +65,20 @@ lb_hash_t *lb_get_sticky_table(u32 cpu_index)
   lb_main_t *lbm = &lb_main;
   lb_hash_t *sticky_ht = lbm->per_cpu[cpu_index].sticky_ht;
   //Check if size changed
-  if (PREDICT_FALSE(sticky_ht && (lbm->per_cpu_sticky_buckets != lb_hash_nbuckets(sticky_ht)))) {
+  if (PREDICT_FALSE(sticky_ht && (lbm->per_cpu_sticky_buckets != lb_hash_nbuckets(sticky_ht))))
+    {
+      //Dereference everything in there
+      lb_hash_bucket_t *b;
+      u32 i;
+      lb_hash_foreach_entry(sticky_ht, b, i) {
+       vlib_refcount_add(&lbm->as_refcount, cpu_index, b->value[i], -1);
+       vlib_refcount_add(&lbm->as_refcount, cpu_index, 0, 1);
+      }
 
-    //Dereference everything in there
-    lb_hash_entry_t *e;
-    lb_hash_foreach_entry(sticky_ht, e) {
-      vlib_refcount_add(&lbm->as_refcount, cpu_index, e->value, -1);
-      vlib_refcount_add(&lbm->as_refcount, cpu_index, 0, -1);
+      lb_hash_free(sticky_ht);
+      sticky_ht = NULL;
     }
 
-    lb_hash_free(sticky_ht);
-    sticky_ht = NULL;
-  }
-
   //Create if necessary
   if (PREDICT_FALSE(sticky_ht == NULL)) {
     lbm->per_cpu[cpu_index].sticky_ht = lb_hash_alloc(lbm->per_cpu_sticky_buckets, lbm->flow_timeout);
@@ -93,6 +93,58 @@ lb_hash_t *lb_get_sticky_table(u32 cpu_index)
   return sticky_ht;
 }
 
+u64
+lb_node_get_other_ports4(ip4_header_t *ip40)
+{
+  return 0;
+}
+
+u64
+lb_node_get_other_ports6(ip6_header_t *ip60)
+{
+  return 0;
+}
+
+static_always_inline u32
+lb_node_get_hash(vlib_buffer_t *p, u8 is_input_v4)
+{
+  u32 hash;
+  if (is_input_v4)
+    {
+      ip4_header_t *ip40;
+      u64 ports;
+      ip40 = vlib_buffer_get_current (p);
+      if (PREDICT_TRUE (ip40->protocol == IP_PROTOCOL_TCP ||
+                      ip40->protocol == IP_PROTOCOL_UDP))
+       ports = ((u64)((udp_header_t *)(ip40 + 1))->src_port << 16) |
+         ((u64)((udp_header_t *)(ip40 + 1))->dst_port);
+      else
+       ports = lb_node_get_other_ports4(ip40);
+
+      hash = lb_hash_hash(*((u64 *)&ip40->address_pair), ports,
+                         0, 0, 0);
+    }
+  else
+    {
+      ip6_header_t *ip60;
+      ip60 = vlib_buffer_get_current (p);
+      u64 ports;
+      if (PREDICT_TRUE (ip60->protocol == IP_PROTOCOL_TCP ||
+                       ip60->protocol == IP_PROTOCOL_UDP))
+       ports = ((u64)((udp_header_t *)(ip60 + 1))->src_port << 16) |
+       ((u64)((udp_header_t *)(ip60 + 1))->dst_port);
+      else
+       ports = lb_node_get_other_ports6(ip60);
+
+      hash = lb_hash_hash(ip60->src_address.as_u64[0],
+                         ip60->src_address.as_u64[1],
+                         ip60->dst_address.as_u64[0],
+                         ip60->dst_address.as_u64[1],
+                         ports);
+    }
+  return hash;
+}
+
 static_always_inline uword
 lb_node_fn (vlib_main_t * vm,
          vlib_node_runtime_t * node, vlib_frame_t * frame,
@@ -100,7 +152,6 @@ lb_node_fn (vlib_main_t * vm,
          u8 is_encap_v4) //Compile-time parameter stating that is GRE encap is v4 (or v6)
 {
   lb_main_t *lbm = &lb_main;
-  vlib_node_runtime_t *error_node = node;
   u32 n_left_from, *from, next_index, *to_next, n_left_to_next;
   u32 cpu_index = os_get_cpu_number();
   u32 lb_time = lb_hash_time_now(vm);
@@ -110,6 +161,10 @@ lb_node_fn (vlib_main_t * vm,
   n_left_from = frame->n_vectors;
   next_index = node->cached_next_index;
 
+  u32 nexthash0 = 0;
+  if (PREDICT_TRUE(n_left_from > 0))
+    nexthash0 = lb_node_get_hash(vlib_get_buffer (vm, from[0]), is_input_v4);
+
   while (n_left_from > 0)
   {
     vlib_get_next_frame (vm, node, next_index, to_next, n_left_to_next);
@@ -118,21 +173,30 @@ lb_node_fn (vlib_main_t * vm,
       u32 pi0;
       vlib_buffer_t *p0;
       lb_vip_t *vip0;
-      lb_as_t *as0;
-      gre_header_t *gre0;
+      u32 asindex0;
       u16 len0;
-      u32 value0, available_index0, hash0;
-      u64 key0[5];
-      lb_error_t error0 = LB_ERROR_NONE;
+      u32 available_index0;
+      u8 counter = 0;
+      u32 hash0 = nexthash0;
 
       if (PREDICT_TRUE(n_left_from > 1))
-      {
-        vlib_buffer_t *p2;
-        p2 = vlib_get_buffer(vm, from[1]);
-        vlib_prefetch_buffer_header(p2, STORE);
-        /* IPv4 + 8 = 28. possibly plus -40 */
-        CLIB_PREFETCH (vlib_buffer_get_current(p2) - 40, 128, STORE);
-      }
+       {
+         vlib_buffer_t *p1 = vlib_get_buffer (vm, from[1]);
+         //Compute next hash and prefetch bucket
+         nexthash0 = lb_node_get_hash(p1, is_input_v4);
+         lb_hash_prefetch_bucket(sticky_ht, nexthash0);
+         //Prefetch for encap, next
+         CLIB_PREFETCH (vlib_buffer_get_current(p1) - 64, 64, STORE);
+       }
+
+      if (PREDICT_TRUE(n_left_from > 2))
+       {
+         vlib_buffer_t *p2;
+         p2 = vlib_get_buffer(vm, from[2]);
+         /* prefetch packet header and data */
+         vlib_prefetch_buffer_header(p2, STORE);
+         CLIB_PREFETCH (vlib_buffer_get_current(p2), 64, STORE);
+       }
 
       pi0 = to_next[0] = from[0];
       from += 1;
@@ -144,112 +208,112 @@ lb_node_fn (vlib_main_t * vm,
       vip0 = pool_elt_at_index (lbm->vips,
                                vnet_buffer (p0)->ip.adj_index[VLIB_TX]);
 
-      if (is_input_v4) {
-        ip4_header_t *ip40;
-        ip40 = vlib_buffer_get_current (p0);
-        len0 = clib_net_to_host_u16(ip40->length);
-        key0[0] = (u64) ip40->src_address.as_u32;
-        key0[1] = (u64) ip40->dst_address.as_u32;
-        key0[2] = 0;
-        key0[3] = 0;
-        key0[4] = ((u64)((udp_header_t *)(ip40 + 1))->src_port << 32) |
-            ((u64)((udp_header_t *)(ip40 + 1))->dst_port << 16);
-
-        hash0 = lb_hash_hash(key0);
-      } else {
-        ip6_header_t *ip60;
-        ip60 = vlib_buffer_get_current (p0);
-        len0 = clib_net_to_host_u16(ip60->payload_length) + sizeof(ip6_header_t);
-        key0[0] = ip60->src_address.as_u64[0];
-        key0[1] = ip60->src_address.as_u64[1];
-        key0[2] = ip60->dst_address.as_u64[0];
-        key0[3] = ip60->dst_address.as_u64[1];
-        key0[4] = ((u64)((udp_header_t *)(ip60 + 1))->src_port << 32) |
-            ((u64)((udp_header_t *)(ip60 + 1))->dst_port << 16);
-
-        hash0 = lb_hash_hash(key0);
-      }
-
-      //NOTE: This is an ugly trick to not include the VIP index in the hash calculation
-      //but actually use it in the key determination.
-      key0[4] |= ((vip0 - lbm->vips));
-
-      lb_hash_get(sticky_ht, key0, hash0, lb_time, &available_index0, &value0);
-      if (PREDICT_TRUE(value0 != ~0)) {
-        //Found an existing entry
-        as0 = &lbm->ass[value0];
-      } else if (PREDICT_TRUE(available_index0 != ~0)) {
-        //There is an available slot for a new flow
-        as0 = &lbm->ass[vip0->new_flow_table[hash0 & vip0->new_flow_table_mask].as_index];
-        if (PREDICT_FALSE(as0 == lbm->ass)) { //Special first element
-          error0 = LB_ERROR_NO_SERVER;
-        } else {
-          vlib_increment_simple_counter(&lbm->vip_counters[LB_VIP_COUNTER_TRACKED_SESSION],
-                                        cpu_index, vip0 - lbm->vips, 1);
-        }
-
-        //TODO: There are race conditions with as0 and vip0 manipulation.
-        //Configuration may be changed, vectors resized, etc...
-
-        //Dereference previously used
-        vlib_refcount_add(&lbm->as_refcount, cpu_index, lb_hash_available_value(sticky_ht, available_index0), -1);
-        vlib_refcount_add(&lbm->as_refcount, cpu_index, as0 - lbm->ass, 1);
-
-        //Add sticky entry
-        //Note that when there is no AS configured, an entry is configured anyway.
-        //But no configured AS is not something that should happen
-        lb_hash_put(sticky_ht, key0, as0 - lbm->ass, available_index0, lb_time);
-      } else {
-        //Could not store new entry in the table
-        as0 = &lbm->ass[vip0->new_flow_table[hash0 & vip0->new_flow_table_mask].as_index];
-        vlib_increment_simple_counter(&lbm->vip_counters[LB_VIP_COUNTER_UNTRACKED_PACKET],
-                                                cpu_index, vip0 - lbm->vips, 1);
-      }
+      if (is_input_v4)
+       {
+         ip4_header_t *ip40;
+         ip40 = vlib_buffer_get_current (p0);
+         len0 = clib_net_to_host_u16(ip40->length);
+       }
+      else
+       {
+         ip6_header_t *ip60;
+         ip60 = vlib_buffer_get_current (p0);
+         len0 = clib_net_to_host_u16(ip60->payload_length) + sizeof(ip6_header_t);
+       }
+
+      lb_hash_get(sticky_ht, hash0, vnet_buffer (p0)->ip.adj_index[VLIB_TX],
+                 lb_time, &available_index0, &asindex0);
+
+      if (PREDICT_TRUE(asindex0 != ~0))
+       {
+         //Found an existing entry
+         counter = LB_VIP_COUNTER_NEXT_PACKET;
+       }
+      else if (PREDICT_TRUE(available_index0 != ~0))
+       {
+         //There is an available slot for a new flow
+         asindex0 = vip0->new_flow_table[hash0 & vip0->new_flow_table_mask].as_index;
+         counter = LB_VIP_COUNTER_FIRST_PACKET;
+         counter = (asindex0 == 0)?LB_VIP_COUNTER_NO_SERVER:counter;
+
+         //TODO: There are race conditions with as0 and vip0 manipulation.
+         //Configuration may be changed, vectors resized, etc...
+
+         //Dereference previously used
+         vlib_refcount_add(&lbm->as_refcount, cpu_index,
+                           lb_hash_available_value(sticky_ht, hash0, available_index0), -1);
+         vlib_refcount_add(&lbm->as_refcount, cpu_index,
+                           asindex0, 1);
+
+         //Add sticky entry
+         //Note that when there is no AS configured, an entry is configured anyway.
+         //But no configured AS is not something that should happen
+         lb_hash_put(sticky_ht, hash0, asindex0,
+                     vnet_buffer (p0)->ip.adj_index[VLIB_TX],
+                     available_index0, lb_time);
+       }
+      else
+       {
+         //Could not store new entry in the table
+         asindex0 = vip0->new_flow_table[hash0 & vip0->new_flow_table_mask].as_index;
+         counter = LB_VIP_COUNTER_UNTRACKED_PACKET;
+       }
+
+      vlib_increment_simple_counter(&lbm->vip_counters[counter],
+                                   cpu_index,
+                                   vnet_buffer (p0)->ip.adj_index[VLIB_TX],
+                                   1);
 
       //Now let's encap
-      if (is_encap_v4) {
-        ip4_header_t *ip40;
-        vlib_buffer_advance(p0, - sizeof(ip4_header_t) - sizeof(gre_header_t));
-        ip40 = vlib_buffer_get_current(p0);
-        gre0 = (gre_header_t *)(ip40 + 1);
-        ip40->src_address = lbm->ip4_src_address;
-        ip40->dst_address = as0->address.ip4;
-        ip40->ip_version_and_header_length = 0x45;
-        ip40->ttl = 128;
-        ip40->length = clib_host_to_net_u16(len0 + sizeof(gre_header_t) + sizeof(ip4_header_t));
-        ip40->protocol = IP_PROTOCOL_GRE;
-        ip40->checksum = ip4_header_checksum (ip40);
-      } else {
-        ip6_header_t *ip60;
-        vlib_buffer_advance(p0, - sizeof(ip6_header_t) - sizeof(gre_header_t));
-        ip60 = vlib_buffer_get_current(p0);
-        gre0 = (gre_header_t *)(ip60 + 1);
-        ip60->dst_address = as0->address.ip6;
-        ip60->src_address = lbm->ip6_src_address;
-        ip60->hop_limit = 128;
-        ip60->ip_version_traffic_class_and_flow_label = clib_host_to_net_u32 (0x6<<28);
-        ip60->payload_length = clib_host_to_net_u16(len0 + sizeof(gre_header_t));
-        ip60->protocol = IP_PROTOCOL_GRE;
-      }
-
-      gre0->flags_and_version = 0;
-      gre0->protocol = (is_input_v4)?
-          clib_host_to_net_u16(0x0800):
-          clib_host_to_net_u16(0x86DD);
-
-      vnet_buffer (p0)->ip.adj_index[VLIB_TX] = as0->dpo.dpoi_index;
-
-      if (PREDICT_FALSE (p0->flags & VLIB_BUFFER_IS_TRACED))
       {
-        lb_trace_t *tr = vlib_add_trace (vm, node, p0, sizeof (*tr));
-        tr->as_index = as0 - lbm->ass;
-        tr->vip_index = vip0 - lbm->vips;
+       gre_header_t *gre0;
+       if (is_encap_v4)
+         {
+           ip4_header_t *ip40;
+           vlib_buffer_advance(p0, - sizeof(ip4_header_t) - sizeof(gre_header_t));
+           ip40 = vlib_buffer_get_current(p0);
+           gre0 = (gre_header_t *)(ip40 + 1);
+           ip40->src_address = lbm->ip4_src_address;
+           ip40->dst_address = lbm->ass[asindex0].address.ip4;
+           ip40->ip_version_and_header_length = 0x45;
+           ip40->ttl = 128;
+           ip40->length = clib_host_to_net_u16(len0 + sizeof(gre_header_t) + sizeof(ip4_header_t));
+           ip40->protocol = IP_PROTOCOL_GRE;
+           ip40->checksum = ip4_header_checksum (ip40);
+         }
+       else
+         {
+           ip6_header_t *ip60;
+           vlib_buffer_advance(p0, - sizeof(ip6_header_t) - sizeof(gre_header_t));
+           ip60 = vlib_buffer_get_current(p0);
+           gre0 = (gre_header_t *)(ip60 + 1);
+           ip60->dst_address = lbm->ass[asindex0].address.ip6;
+           ip60->src_address = lbm->ip6_src_address;
+           ip60->hop_limit = 128;
+           ip60->ip_version_traffic_class_and_flow_label = clib_host_to_net_u32 (0x6<<28);
+           ip60->payload_length = clib_host_to_net_u16(len0 + sizeof(gre_header_t));
+           ip60->protocol = IP_PROTOCOL_GRE;
+         }
+
+       gre0->flags_and_version = 0;
+       gre0->protocol = (is_input_v4)?
+           clib_host_to_net_u16(0x0800):
+           clib_host_to_net_u16(0x86DD);
       }
 
-      p0->error = error_node->errors[error0];
+      if (PREDICT_FALSE (p0->flags & VLIB_BUFFER_IS_TRACED))
+       {
+         lb_trace_t *tr = vlib_add_trace (vm, node, p0, sizeof (*tr));
+         tr->as_index = asindex0;
+         tr->vip_index = vnet_buffer (p0)->ip.adj_index[VLIB_TX];
+       }
+
+      //Enqueue to next
+      //Note that this is going to error if asindex0 == 0
+      vnet_buffer (p0)->ip.adj_index[VLIB_TX] = lbm->ass[asindex0].dpo.dpoi_index;
       vlib_validate_buffer_enqueue_x1 (vm, node, next_index, to_next,
-                                       n_left_to_next, pi0,
-                                      as0->dpo.dpoi_next_node);
+                                      n_left_to_next, pi0,
+                                      lbm->ass[asindex0].dpo.dpoi_next_node);
     }
     vlib_put_next_frame (vm, node, next_index, n_left_to_next);
   }