diff options
Diffstat (limited to 'hicn-light/src/hicn/core/packet_cache.h')
| -rw-r--r-- | hicn-light/src/hicn/core/packet_cache.h | 502 |
1 files changed, 502 insertions, 0 deletions
diff --git a/hicn-light/src/hicn/core/packet_cache.h b/hicn-light/src/hicn/core/packet_cache.h new file mode 100644 index 000000000..1abdc57c2 --- /dev/null +++ b/hicn-light/src/hicn/core/packet_cache.h @@ -0,0 +1,502 @@ +/* + * Copyright (c) 2021-2022 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. + */ + +/** + * \file packet_cache.h + * \brief hICN packet cache + * + * The packet cache is a data structure that merges together the PIT and the CS, + * to which it holds a reference. + * It contains PIT and CS entries, indexed in a two-level hash table. + * + * Each entry has shared fields, e.g. entry type (PIT or CS) and timestamps, + * which are used by both PIT and CS entries. In addition, a C union holds + * the PIT or CS specific fields. + * + * Having a single entry that can hold PIT or CS entries allows to reduce + * the number of lookups. + * + * A prefix hash table <prefix, suffix_hashtable> stores the suffixes associated + * to each prefix, where each value in the map points to a separate hash + * table <suffix, packet_cache_reference> that can be used to retrieved the + * packet cache entry. + * When an interest/data packet is received, the prefix and the associated + * suffixes are saved; if the next packet cache operation involves the same + * prefix, no additional lookups in the prefix hash hashtable are needed. + */ + +#ifndef HICNLIGHT_PACKET_CACHE_H +#define HICNLIGHT_PACKET_CACHE_H + +#include <hicn/util/khash.h> +#include <hicn/util/slab.h> +#include "content_store.h" +#include "pit.h" +#include "msgbuf_pool.h" +#include "../content_store/lru.h" + +#define DEFAULT_PKT_CACHE_SIZE 2048 + +typedef enum { PKT_CACHE_PIT_TYPE, PKT_CACHE_CS_TYPE } pkt_cache_entry_type_t; + +#define foreach_kh_verdict \ + _(FORWARD_INTEREST) \ + _(AGGREGATE_INTEREST) \ + _(RETRANSMIT_INTEREST) \ + _(FORWARD_DATA) \ + _(INTEREST_EXPIRED_FORWARD_INTEREST) \ + _(DATA_EXPIRED_FORWARD_INTEREST) \ + _(STORE_DATA) \ + _(CLEAR_DATA) \ + _(UPDATE_DATA) \ + _(IGNORE_DATA) \ + _(ERROR) + +typedef enum { +#define _(x) PKT_CACHE_VERDICT_##x, + foreach_kh_verdict +#undef _ +} pkt_cache_verdict_t; + +extern const char *_pkt_cache_verdict_str[]; + +#define pkt_cache_verdict_str(x) _pkt_cache_verdict_str[x] + +#define foreach_kh_lookup \ + _(INTEREST_NOT_EXPIRED) \ + _(INTEREST_EXPIRED) \ + _(DATA_NOT_EXPIRED) \ + _(DATA_EXPIRED) \ + _(NONE) + +typedef enum { +#define _(x) PKT_CACHE_LU_##x, + foreach_kh_lookup +#undef _ +} pkt_cache_lookup_t; + +KHASH_MAP_INIT_INT(pkt_cache_suffix, unsigned); +KHASH_INIT(pkt_cache_prefix, const hicn_name_prefix_t *, + kh_pkt_cache_suffix_t *, 1, hicn_name_prefix_get_hash, + hicn_name_prefix_equals); + +typedef struct { + hicn_name_t name; + pkt_cache_entry_type_t entry_type; + + Ticks create_ts; + Ticks expire_ts; + // TODO(eloparco): Is it necessary? + // Now it is always set to true + bool has_expire_ts; + + union { + pit_entry_t pit_entry; + cs_entry_t cs_entry; + } u; +} pkt_cache_entry_t; + +typedef struct { + pit_t *pit; + cs_t *cs; + pkt_cache_entry_t *entries; + kh_pkt_cache_prefix_t *prefix_to_suffixes; + slab_t *prefix_keys; + + // Cached prefix info to avoid double lookups, + // used for both single interest speculation and interest manifest + hicn_name_prefix_t cached_prefix; + kh_pkt_cache_suffix_t *cached_suffixes; +} pkt_cache_t; + +/** + * @brief Create a new packet cache. + * + * @return pkt_cache_t* The newly created packet cache + */ +pkt_cache_t *pkt_cache_create(size_t cs_size); + +/** + * @brief Add an entry with the specified name to the packet cache. + * + * @param[in] pkt_cache Pointer to the pool data structure to use. + * @param[in, out] entry Empty entry that will be used to return the + * allocated one from the msgbuf pool. + * @param[in] name hicn_name_t to use + * + * NOTE: unlike other pools, PIT and CS entries allocation does not update the + * index as the key is a hicn_name_t * which should point to : + * - the name inside the PIT entry (which is thus not set during allocation), + * - the name inside the msgbuf_t in the CS entry, which is always available + * during the lifetime of the cache entry. + * + * The index is therefore updated in pkt_cache_add_to_pit and + * pkt_cache_add_to_cs functions. + * + * + */ +pkt_cache_entry_t *pkt_cache_allocate(pkt_cache_t *pkt_cache); + +void pkt_cache_add_to_index(const pkt_cache_t *pkt_cache, + const pkt_cache_entry_t *entry); + +void pkt_cache_remove_from_index(const pkt_cache_t *pkt_cache, + const hicn_name_t *name); + +/** + * @brief Free a packet cache data structure. + * + * @param[in] pkt_cache Pointer to packet cache data structure to free. + */ +void pkt_cache_free(pkt_cache_t *pkt_cache); + +/** + * @brief Get a reference to the PIT data structure contained in the packet + * cache. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to get the + * PIT from. + */ +pit_t *pkt_cache_get_pit(pkt_cache_t *pkt_cache); + +/** + * @brief Get a reference to the CS data structure contained in the packet + * cache. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to get the + * CS from. + */ +cs_t *pkt_cache_get_cs(pkt_cache_t *pkt_cache); + +/** + * @brief Return the total packet cache size (i.e. PIT + CS). + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + */ +size_t pkt_cache_get_size(pkt_cache_t *pkt_cache); + +/** + * @brief Return the number of stale entries (i.e. expired) in the CS. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + */ +size_t pkt_cache_get_num_cs_stale_entries(pkt_cache_t *pkt_cache); + +/** + * @brief Change the maximum capacity of the content store (LRU eviction will + * be used after reaching the provided size) + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in] size Maximum size of the content store + * @return int 0 if success, -1 if the provided maximum size is smaller than + * the number of elements currently stored in the CS + */ +int pkt_cache_set_cs_size(pkt_cache_t *pkt_cache, size_t size); + +/** + * @brief Return the content store size. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + */ +size_t pkt_cache_get_cs_size(pkt_cache_t *pkt_cache); + +/** + * @brief Return the PIT size. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + */ +size_t pkt_cache_get_pit_size(pkt_cache_t *pkt_cache); + +#define pkt_cache_entry_get_create_ts(E) ((E)->create_ts) +#define pkt_cache_entry_get_expire_ts(E) ((E)->expire_ts) +#define pkt_cache_entry_set_expire_ts(E, EXPIRY_TIME) \ + (entry)->expire_ts = EXPIRY_TIME +#define pkt_cache_get_entry_id(pkt_cache, entry) (entry - pkt_cache->entries) +#define pkt_cache_entry_at(pkt_cache, id) (&(pkt_cache)->entries[id]) +#define pkt_cache_at(pkt_cache, i) (pkt_cache->entries + i) + +/** + * @brief Retrieve from the packet cache the entry associated with the + * specified name. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to retrieve + * the entry from + * @param[in] name Packet name to use for the lookup + * @param[in] msgbuf_pool Pointer to the msgbuf pool data structure to use + * @param[in, out] lookup_result Pointer to store the result of the lookup + * @param[in, out] entry_id Pointer to store the entry_id in case of a lookup + * match + * @param[in] is_serve_from_cs_enabled Boolean to specify if the forwarder is + * allowed to serve contents from the CS + * @return pkt_cache_entry_t* Entry retrieved, NULL if none found + */ +pkt_cache_entry_t *pkt_cache_lookup(pkt_cache_t *pkt_cache, + const hicn_name_t *name, + msgbuf_pool_t *msgbuf_pool, + pkt_cache_lookup_t *lookup_result, + off_t *entry_id, + bool is_serve_from_cs_enabled); + +/** + * @brief Clear the content of the CS (PIT entries are left unmodified). + * + * @param pkt_cache Pointer to the packet cache data structure to use + */ +void pkt_cache_cs_clear(pkt_cache_t *pkt_cache); + +/** + * @brief Log packet cache statistics. + * + * @param pkt_cache Pointer to the packet cache data structure to use + */ +void pkt_cache_log(pkt_cache_t *pkt_cache); + +pkt_cache_stats_t pkt_cache_get_stats(pkt_cache_t *pkt_cache); + +// TODO(eloparco): To implement +void pkt_cache_print(const pkt_cache_t *pkt_cache); + +/************** Packet cache entry operations *************/ + +/** + * @brief Remove a content store entry from the packet cache. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in] entry Pointer to the content store entry to remove + * @param[in] msgbuf_pool Pointer to the msgbuf pool data structure to use + * @param[in] is_evicted Boolean to specify if the content store entry has + * already been evicted from the LRU cache + */ +void pkt_cache_cs_remove_entry(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, + msgbuf_pool_t *msgbuf_pool, bool is_evicted); + +/** + * @brief Remove a PIT entry from the packet cache. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in] entry Pointer to the PIT entry to remove + */ +void pkt_cache_pit_remove_entry(pkt_cache_t *pkt_cache, + pkt_cache_entry_t *entry); + +/** + * @brief Convert a PIT entry to a CS entry. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in, out] entry Pointer to the PIT entry to replace + * @param[in] msgbuf_pool Pointer to the msgbuf pool data structure to use + * @param[in] msgbuf Pointer to the msgbuf associated with the CS entry to + * insert + * @param[in] msgbuf_id Msgbuf ID (i.e. ID in the msgbuf pool) associated with + * the CS entry to insert + * @param[in] entry_id Entry ID (i.e. ID in the packet cache pool of entries) + * associated with the PIT entry to replace + */ +void pkt_cache_pit_to_cs(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, + msgbuf_pool_t *msgbuf_pool, msgbuf_t *msgbuf, + off_t msgbuf_id, off_t entry_id); + +/** + * @brief Convert a CS entry to a PIT entry. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in, out] entry Pointer to the CS entry to replace + * @param[in] msgbuf Pointer to the msgbuf associated with the PIT entry to + * insert + * @param[in] msgbuf_id Msgbuf ID (i.e. ID in the msgbuf pool) associated with + * the PIT entry to insert + * @param[in] entry_id Entry ID (i.e. ID in the packet cache pool of entries) + * associated with the CS entry to replace + */ +void pkt_cache_cs_to_pit(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, + msgbuf_pool_t *msgbuf_pool, const msgbuf_t *msgbuf, + off_t msgbuf_id, off_t entry_id); + +/** + * @brief Add PIT entry to the packet cache. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in] msgbuf Pointer to the msgbuf associated with the PIT entry to + * insert + * @param[in] name Interest name to use; in case of aggregated interests, it is + * different from the name stored in the msgbuf + * @return pkt_cache_entry_t* Pointer to the packet cache (PIT) entry created + */ +pkt_cache_entry_t *pkt_cache_add_to_pit(pkt_cache_t *pkt_cache, + const msgbuf_t *msgbuf, + const hicn_name_t *name); + +/** + * @brief Add CS entry to the packet cache. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in] msgbuf_pool Pointer to the msgbuf pool data structure to use + * @param[in] msgbuf Pointer to the msgbuf associated with the CS entry to + * insert + * @param[in] msgbuf_id Msgbuf ID (i.e. ID in the msgbuf pool) associated with + * the CS entry to insert + * @return pkt_cache_entry_t* Pointer to the packet cache (CS) entry created + */ +pkt_cache_entry_t *pkt_cache_add_to_cs(pkt_cache_t *pkt_cache, + msgbuf_pool_t *msgbuf_pool, + msgbuf_t *msgbuf, off_t msgbuf_id); + +/** + * @brief Update PIT entry in the packet cache in case of an expired PIT + * entry. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in, out] entry Pointer to the PIT entry to update + * @param[in] msgbuf Pointer to the msgbuf associated with the PIT entry to + * update + */ +void pkt_cache_update_pit(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, + const msgbuf_t *msgbuf); + +/** + * @brief Update CS entry in the packet cache. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in] msgbuf_pool Pointer to the msgbuf pool data structure to use + * @param[in, out] entry Pointer to the CS entry to update + * @param[in] msgbuf Pointer to the msgbuf associated with the CS entry to + * update + * @param msgbuf_id Msgbuf ID (i.e. ID in the msgbuf pool) associated with the + * CS entry to update + */ +void pkt_cache_update_cs(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, + pkt_cache_entry_t *entry, msgbuf_t *msgbuf, + off_t msgbuf_id); + +/** + * @brief Update PIT entry in the packet cache in case of retransmission or + * aggregation. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in, out] entry Pointer to the PIT entry to update + * @param[in] msgbuf Pointer to the msgbuf associated with the PIT entry to + * update + * @param[in] name Interest name to use; in case of aggregated interests, it is + * different from the name stored in the msgbuf + * @return true If aggregation (interest sent from a connection not stored in + * the PIT entry) + * @return false If retransmission (interest sent from a connection already + * stored in the PIT entry) + */ +bool pkt_cache_try_aggregate_in_pit(pkt_cache_t *pkt_cache, + pkt_cache_entry_t *entry, + const msgbuf_t *msgbuf, + const hicn_name_t *name); + +/** + * @brief Cache prefix info (prefix + associated suffixes) to speed up lookups. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + * @param[in] prefix Name prefix to cache + */ +void pkt_cache_save_suffixes_for_prefix(pkt_cache_t *pkt_cache, + const hicn_name_prefix_t *prefix); + +/** + * @brief Reset cached prefix info to force double lookups. + * + * @param[in] pkt_cache Pointer to the packet cache data structure to use + */ +void pkt_cache_reset_suffixes_for_prefix(pkt_cache_t *pkt_cache); + +/************ Handle data/interest packets received *******/ + +/** + * @brief Handle data packet reception. + * @details Perform packet cache lookup and execute operations based on it. + * If: + * - INTEREST not expired: Convert PIT entry to CS entry; return the + * nexthops (that can be used to forward the data + * packet now stored in the CS) + * - INTEREST expired: Convert PIT entry to CS entry + * - DATA expired/not expired: Update the CS + * - No match: Add data packet to CS + */ +nexthops_t *pkt_cache_on_data(pkt_cache_t *pkt_cache, + msgbuf_pool_t *msgbuf_pool, off_t msgbuf_id, + bool is_cs_store_enabled, + bool is_connection_local, bool *wrong_egress, + pkt_cache_verdict_t *verdict); + +/** + * @brief Handle interest packet reception. + * @details Perform packet cache lookup and execute operations based on it. + * If: + * - No match: Do nothing + * - DATA not expired: get data message from CS + * - INTEREST not expired: Aggregate or retransmit the interest received; + * - INTEREST expired: Update the PIT; + * - DATA expired: Convert CS entry to PIT entry; + */ +void pkt_cache_on_interest(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, + off_t msgbuf_id, pkt_cache_verdict_t *verdict, + off_t *data_msgbuf_id, pkt_cache_entry_t **entry_ptr, + const hicn_name_t *name, + bool is_serve_from_cs_enabled); + +/********* Low-level operations on the hash table *********/ +#ifdef WITH_TESTS +unsigned __get_suffix(kh_pkt_cache_suffix_t *suffixes, + hicn_name_suffix_t suffix); +unsigned _get_suffix(kh_pkt_cache_prefix_t *prefixes, + const hicn_name_prefix_t *prefix, + hicn_name_suffix_t suffix, slab_t *prefix_keys); +void __add_suffix(kh_pkt_cache_suffix_t *suffixes, hicn_name_suffix_t suffix, + unsigned val); +void _add_suffix(kh_pkt_cache_prefix_t *prefixes, + const hicn_name_prefix_t *prefix, + const hicn_name_suffix_t suffix, unsigned val, slab_t *slab); +void _remove_suffix(kh_pkt_cache_prefix_t *prefixes, + const hicn_name_prefix_t *prefix, hicn_name_suffix_t suffix, + slab_t *slab); +void _prefix_map_free(kh_pkt_cache_prefix_t *prefix_to_suffixes); +kh_pkt_cache_suffix_t *_get_suffixes(kh_pkt_cache_prefix_t *prefix_to_suffixes, + const hicn_name_prefix_t *prefix, + bool create, slab_t *prefix_keys); +#endif + +/************** Content Store *****************************/ + +typedef struct { + const char *name; + void (*initialize)(cs_t *cs); + void (*finalize)(cs_t *cs); + int (*add_entry)(pkt_cache_t *pkt_cache, off_t entry_id); + void (*update_entry)(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry); + int (*remove_entry)(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry); +} cs_ops_t; +extern const cs_ops_t *const cs_vft[]; + +/** + * @brief Initialize the virtual function table used for the + * CS cache strategy (e.g. LRU). + * + */ +#define DECLARE_CS(NAME) \ + const cs_ops_t cs_##NAME = { \ + .name = #NAME, \ + .initialize = cs_##NAME##_initialize, \ + .finalize = cs_##NAME##_finalize, \ + .add_entry = cs_##NAME##_add_entry, \ + .update_entry = cs_##NAME##_update_entry, \ + .remove_entry = cs_##NAME##_remove_entry, \ + } + +#endif /* HICNLIGHT_PACKET_CACHE_H */ |