/* * 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 stores the suffixes associated * to each prefix, where each value in the map points to a separate hash * table 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 #include #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 */