summaryrefslogtreecommitdiffstats
path: root/hicn-plugin/src/cache_policies
diff options
context:
space:
mode:
authorMauro Sardara <msardara@cisco.com>2020-09-18 17:39:03 +0200
committerMauro Sardara <msardara@cisco.com>2020-09-18 17:41:14 +0200
commit20a773677230374ffa2d5d140f7d46032fb7bc9d (patch)
tree972ba743c7b1cfbbabd38024215af670d4dc2e3c /hicn-plugin/src/cache_policies
parent22738e6177e9e1348e5a9c23c5a71e1d1ef7246f (diff)
Revert to [HICN-638] Check if systemd is running before enabling hicn-light service
Signed-off-by: Mauro Sardara <msardara@cisco.com> Change-Id: I1810d96e001a4e6e097e1efa331b682af750925d
Diffstat (limited to 'hicn-plugin/src/cache_policies')
-rw-r--r--hicn-plugin/src/cache_policies/cs_lru.c268
-rw-r--r--hicn-plugin/src/cache_policies/cs_lru.h76
-rw-r--r--hicn-plugin/src/cache_policies/cs_policy.h96
3 files changed, 440 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 100644
index 000000000..079af58ab
--- /dev/null
+++ b/hicn-plugin/src/cache_policies/cs_lru.c
@@ -0,0 +1,268 @@
+/*
+ * 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,
+ .hicn_cs_flush = &hicn_cs_lru_flush,
+};
+
+/*
+ * 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
+ {
+ /* The element is already dequeue */
+ if (pcs->u.cs.cs_lru_next == 0)
+ {
+ /* Now detached from the list; attach at head */
+ hicn_cs_lru_insert (pit, pnode, pcs, lru);
+ }
+ 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);
+}
+
+int
+hicn_cs_lru_flush (vlib_main_t * vm, struct hicn_pit_cs_s *pitcs,
+ hicn_cs_policy_t * state)
+{
+ if (state->head == 0 && state->tail == 0)
+ return 0;
+
+ hicn_hash_node_t *lrunode;
+ hicn_pcs_entry_t *lrupcs;
+ u32 idx;
+ int i = 0;
+
+ idx = state->tail;
+
+ while (idx != 0)
+ {
+ lrunode = hicn_hashtb_node_from_idx (pitcs->pcs_table, idx);
+ lrupcs = hicn_pit_get_data (lrunode);
+
+ u64 hashval = 0;
+ hicn_hashtb_fullhash ((u8 *) & (lrunode->hn_key.ks.key),
+ lrunode->hn_keysize, &hashval);
+ hicn_hash_bucket_t *bucket = NULL;
+ if ((hashval & (pitcs->pcs_table->ht_bucket_count - 1)) ==
+ lrunode->bucket_id)
+ {
+ //The bucket is in the non overflown
+ bucket = pitcs->pcs_table->ht_buckets + lrunode->bucket_id;
+ }
+ else
+ {
+ bucket =
+ pool_elt_at_index (pitcs->pcs_table->ht_overflow_buckets,
+ lrunode->bucket_id);
+ }
+ hicn_hash_entry_t *hash_entry =
+ &(bucket->hb_entries[lrunode->entry_idx]);
+ hash_entry->locks++;
+ hicn_pcs_cs_delete (vm, pitcs, &lrupcs, &lrunode, hash_entry, NULL,
+ NULL);
+ idx = state->tail;
+ i++;
+ }
+
+ return (i);
+
+}
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables: eval: (c-set-style "gnu") End:
+ */
diff --git a/hicn-plugin/src/cache_policies/cs_lru.h b/hicn-plugin/src/cache_policies/cs_lru.h
new file mode 100644
index 000000000..3bd18060d
--- /dev/null
+++ b/hicn-plugin/src/cache_policies/cs_lru.h
@@ -0,0 +1,76 @@
+/*
+ * Copyright (c) 2017-2020 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.
+ */
+
+#ifndef __LRU_H__
+#define __LRU_H__
+
+#include "../pcs.h"
+#include "../hashtb.h"
+#include "cs_policy.h"
+
+/**
+ * @file cs_lru.h
+ *
+ * This file implements the LRU policy for the CS
+ */
+
+
+extern hicn_cs_policy_vft_t hicn_cs_lru;
+
+/*
+ * Insert a new CS element at the head of the CS LRU
+ */
+void
+hicn_cs_lru_insert (hicn_pit_cs_t * pcs, hicn_hash_node_t * pnode,
+ hicn_pcs_entry_t * entry, hicn_cs_policy_t * lru);
+
+
+/*
+ * Dequeue an LRU element, for example when it has expired.
+ */
+void
+hicn_cs_lru_dequeue (hicn_pit_cs_t * pcs, hicn_hash_node_t * pnode,
+ hicn_pcs_entry_t * entry, hicn_cs_policy_t * lru);
+
+/*
+ * Move a CS LRU element to the head, probably after it's been used.
+ */
+void
+hicn_cs_lru_update_head (hicn_pit_cs_t * pcs, hicn_hash_node_t * pnode,
+ hicn_pcs_entry_t * entry, hicn_cs_policy_t * lru);
+
+void
+hicn_cs_lru_delete_get (hicn_pit_cs_t * p, hicn_cs_policy_t * policy,
+ hicn_hash_node_t ** node, hicn_pcs_entry_t ** pcs,
+ hicn_hash_entry_t ** hash_entry);
+
+/*
+ * 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 * pcs, u32 * node_list, int sz,
+ hicn_cs_policy_t * lru);
+
+
+int hicn_cs_lru_flush (vlib_main_t * vm, struct hicn_pit_cs_s *pitcs,
+ hicn_cs_policy_t * state);
+#endif /* // __LRU_H__ */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables: eval: (c-set-style "gnu") End:
+ */
diff --git a/hicn-plugin/src/cache_policies/cs_policy.h b/hicn-plugin/src/cache_policies/cs_policy.h
new file mode 100644
index 000000000..0bf745915
--- /dev/null
+++ b/hicn-plugin/src/cache_policies/cs_policy.h
@@ -0,0 +1,96 @@
+/*
+ * Copyright (c) 2017-2020 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.
+ */
+
+#ifndef __HICN_CS_POLICY_H__
+#define __HICN_CS_POLICY_H__
+
+#include "../hashtb.h"
+
+/**
+ * @file cs_policy.h
+ *
+ * This file provides the needed structures to implement a CS policy
+ */
+
+
+/*
+ * Structure
+ */
+typedef struct hicn_cs_policy_s
+{
+ u32 max;
+ u32 count;
+
+ /* Indexes to hashtable nodes forming CS LRU */
+ u32 head;
+ u32 tail;
+
+} hicn_cs_policy_t;
+
+/* Forward declaration */
+struct hicn_pit_cs_s;
+struct hicn_hash_node_s;
+struct hicn_pcs_entry_s;
+struct hicn_cs_policy_s;
+
+/**
+ * @brief Definition of the virtual functin table for a cache policy.
+ *
+ * A cache policy must implement all the following functions:
+ * - insert: add a new element
+ * - update: update the position of an existing element
+ * - dequeue: remove an element from the list
+ * - delete_get: return the next element that should be removed trim
+ * - flush: clean the cs
+ */
+typedef struct hicn_cs_policy_vft_s
+{
+ void (*hicn_cs_insert) (struct hicn_pit_cs_s * p,
+ struct hicn_hash_node_s * node,
+ struct hicn_pcs_entry_s * pcs,
+ hicn_cs_policy_t * policy);
+
+ void (*hicn_cs_update) (struct hicn_pit_cs_s * p,
+ struct hicn_hash_node_s * node,
+ struct hicn_pcs_entry_s * pcs,
+ hicn_cs_policy_t * policy);
+
+ void (*hicn_cs_dequeue) (struct hicn_pit_cs_s * p,
+ struct hicn_hash_node_s * node,
+ struct hicn_pcs_entry_s * pcs,
+ hicn_cs_policy_t * policy);
+
+ void (*hicn_cs_delete_get) (struct hicn_pit_cs_s * p,
+ hicn_cs_policy_t * policy,
+ struct hicn_hash_node_s ** node,
+ struct hicn_pcs_entry_s ** pcs,
+ struct hicn_hash_entry_s ** hash_entry);
+
+ int (*hicn_cs_trim) (struct hicn_pit_cs_s * p, u32 * node_list, int sz,
+ hicn_cs_policy_t * policy);
+
+ int (*hicn_cs_flush) (vlib_main_t * vm, struct hicn_pit_cs_s * p,
+ hicn_cs_policy_t * policy_state);
+} hicn_cs_policy_vft_t;
+
+
+
+#endif /* // __HICN_POLICY_H__ */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables: eval: (c-set-style "gnu") End:
+ */