This is the first commit of the hicn projectv19.01

Change-Id: I6f2544ad9b9f8891c88cc4bcce3cf19bd3cc863f
Signed-off-by: Luca Muscariello <lumuscar+fdio@cisco.com>

1 files changed, 213 insertions, 0 deletions

diff --git a/hicn-plugin/src/cache_policies/cs_lru.c b/hicn-plugin/src/cache_policies/cs_lru.c
new file mode 100755
index 000000000..f35bee3c9
--- /dev/null
+++ b/hicn-plugin/src/cache_policies/cs_lru.c
@@ -0,0 +1,213 @@
+/*
+ * Copyright (c) 2017-2019 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 "../hashtb.h"
+#include "../strategy_dpo_manager.h"
+#include "../error.h"
+#include "cs_lru.h"
+#include "cs_policy.h"
+
+hicn_cs_policy_vft_t hicn_cs_lru = {
+  .hicn_cs_insert = &hicn_cs_lru_insert,
+  .hicn_cs_update = &hicn_cs_lru_update_head,
+  .hicn_cs_dequeue = &hicn_cs_lru_dequeue,
+  .hicn_cs_delete_get = &hicn_cs_lru_delete_get,
+  .hicn_cs_trim = &hicn_cs_lru_trim,
+};
+
+/*
+ * Insert a new CS element at the head of the CS LRU
+ */
+void
+hicn_cs_lru_insert (hicn_pit_cs_t * p, hicn_hash_node_t * node,
+		    hicn_pcs_entry_t * pcs, hicn_cs_policy_t * policy_state)
+{
+  hicn_hash_node_t *lrunode;
+  hicn_pcs_entry_t *lrupcs;
+  u32 idx;
+
+  idx = hicn_hashtb_node_idx_from_node (p->pcs_table, node);
+
+  if (policy_state->head != 0)
+    {
+      lrunode = hicn_hashtb_node_from_idx (p->pcs_table, policy_state->head);
+      lrupcs = hicn_pit_get_data (lrunode);
+
+      ASSERT (lrupcs->u.cs.cs_lru_prev == 0);
+      lrupcs->u.cs.cs_lru_prev = idx;
+
+      pcs->u.cs.cs_lru_prev = 0;
+      pcs->u.cs.cs_lru_next = policy_state->head;
+
+      policy_state->head = idx;
+    }
+  else
+    {
+      ASSERT (policy_state->tail == 0);	/* We think the list is
+					 * empty */
+
+      policy_state->head = policy_state->tail = idx;
+
+      pcs->u.cs.cs_lru_next = pcs->u.cs.cs_lru_prev = 0;
+    }
+
+  policy_state->count++;
+}
+
+void
+hicn_cs_lru_delete_get (hicn_pit_cs_t * p, hicn_cs_policy_t * policy_state,
+			hicn_hash_node_t ** nodep,
+			hicn_pcs_entry_t ** pcs_entry,
+			hicn_hash_entry_t ** hash_entry)
+{
+  *nodep = hicn_hashtb_node_from_idx (p->pcs_table, policy_state->tail);
+  *pcs_entry = hicn_pit_get_data (*nodep);
+
+  *hash_entry = hicn_hashtb_get_entry (p->pcs_table, (*nodep)->entry_idx,
+				       (*nodep)->bucket_id,
+				       (*nodep)->hn_flags &
+				       HICN_HASH_NODE_OVERFLOW_BUCKET);
+}
+
+/*
+ * Dequeue an LRU element, for example when it has expired.
+ */
+void
+hicn_cs_lru_dequeue (hicn_pit_cs_t * pit, hicn_hash_node_t * pnode,
+		     hicn_pcs_entry_t * pcs, hicn_cs_policy_t * lru)
+{
+  hicn_hash_node_t *lrunode;
+  hicn_pcs_entry_t *lrupcs;
+
+  if (pcs->u.cs.cs_lru_prev != 0)
+    {
+      /* Not already on the head of the LRU */
+      lrunode = hicn_hashtb_node_from_idx (pit->pcs_table,
+					   pcs->u.cs.cs_lru_prev);
+      lrupcs = hicn_pit_get_data (lrunode);
+
+      lrupcs->u.cs.cs_lru_next = pcs->u.cs.cs_lru_next;
+    }
+  else
+    {
+      ASSERT (lru->head ==
+	      hicn_hashtb_node_idx_from_node (pit->pcs_table, pnode));
+      lru->head = pcs->u.cs.cs_lru_next;
+    }
+
+  if (pcs->u.cs.cs_lru_next != 0)
+    {
+      /* Not already the end of the LRU */
+      lrunode = hicn_hashtb_node_from_idx (pit->pcs_table,
+					   pcs->u.cs.cs_lru_next);
+      lrupcs = hicn_pit_get_data (lrunode);
+
+      lrupcs->u.cs.cs_lru_prev = pcs->u.cs.cs_lru_prev;
+    }
+  else
+    {
+      /* This was the last LRU element */
+      ASSERT (lru->tail ==
+	      hicn_hashtb_node_idx_from_node (pit->pcs_table, pnode));
+      lru->tail = pcs->u.cs.cs_lru_prev;
+    }
+
+  pcs->u.cs.cs_lru_next = pcs->u.cs.cs_lru_prev = 0;
+  lru->count--;
+}
+
+/*
+ * Move a CS LRU element to the head, probably after it's been used.
+ */
+void
+hicn_cs_lru_update_head (hicn_pit_cs_t * pit, hicn_hash_node_t * pnode,
+			 hicn_pcs_entry_t * pcs, hicn_cs_policy_t * lru)
+{
+  if (pcs->u.cs.cs_lru_prev != 0)
+    {
+      /*
+       * Not already on the head of the LRU, detach it from its
+       * current position
+       */
+      hicn_cs_lru_dequeue (pit, pnode, pcs, lru);
+
+      /* Now detached from the list; attach at head */
+      hicn_cs_lru_insert (pit, pnode, pcs, lru);
+
+    }
+  else
+    {
+      ASSERT (lru->head ==
+	      hicn_hashtb_node_idx_from_node (pit->pcs_table, pnode));
+    }
+}
+
+/*
+ * Remove a batch of nodes from the CS LRU, copying their node indexes into
+ * the caller's array. We expect this is done when the LRU size exceeds the
+ * CS's limit. Return the number of removed nodes.
+ */
+int
+hicn_cs_lru_trim (hicn_pit_cs_t * pit, u32 * node_list, int sz,
+		  hicn_cs_policy_t * lru)
+{
+  hicn_hash_node_t *lrunode;
+  hicn_pcs_entry_t *lrupcs;
+  u32 idx;
+  int i;
+
+  idx = lru->tail;
+
+  for (i = 0; i < sz; i++)
+    {
+
+      if (idx == 0)
+	{
+	  break;
+	}
+      lrunode = hicn_hashtb_node_from_idx (pit->pcs_table, idx);
+      lrupcs = hicn_pit_get_data (lrunode);
+
+      node_list[i] = idx;
+
+      idx = lrupcs->u.cs.cs_lru_prev;
+      lrupcs->u.cs.cs_lru_prev = 0;
+      lrupcs->u.cs.cs_lru_next = 0;
+    }
+
+  lru->count -= i;
+
+  lru->tail = idx;
+  if (idx != 0)
+    {
+      lrunode = hicn_hashtb_node_from_idx (pit->pcs_table, idx);
+      lrupcs = hicn_pit_get_data (lrunode);
+
+      lrupcs->u.cs.cs_lru_next = 0;
+    }
+  else
+    {
+      /* If the tail is empty, the whole lru is empty */
+      lru->head = 0;
+    }
+
+  return (i);
+}
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables: eval: (c-set-style "gnu") End:
+ */