diff options
| author |   Luca Muscariello <muscariello@ieee.org> | 2022-08-04 16:06:34 +0200 |
|---|---|---|
| committer | Luca Muscariello <muscariello@ieee.org> | 2022-08-04 16:31:51 +0200 |
| commit | 6d22a0db96aa7f8e3102ae44d00c09e36a2e9c57 (patch) | |
| tree | 79546bbf09f6fbf74db7bc89117843f06ce937ea /hicn-light/src/hicn/core | |
| parent | 012843b1c0bc0838e69085ed83a79ec8b6f97360 (diff) | |
feat: Due to the deep modifications related to names and packet format,
this task cover a large part of the codebase and involves several changes:
- the library provides a name data structure (hicn_name_t ), which is composed
of a name prefix (hicn_name_prefix_t) and a name suffix (hicn_name_suffix_t),
and it has been extended to provide all support functions required for name
manipulation, including common prefix computation, as required for the Longest
Prefix Match (LPM)in the forwarder, in addition to Exact Prefix Match (EPM).
- all code has been rewritten to use this data structure instead of having for
instance the forwarder define its own name class (used to be Name and NameBitVector)
the code has been refactored to minimize name allocations and copies, one remaining
aspect is the difference of name storage between PIT and CS entries (respectively
in the PIT entry, and in the message buffer), which causes the packet cache
index to be updated when a PIT entry is converted into a CS entry. By storing
the name in the PIT/CS entry everytime, we might save on this operation).
- hicn-light FIB has been rewritten : code has been refactored and should now be
shorter and documented; unit tests have been drafted but more would be required
to cover all cases and match the algorithms to add/remove nodes, as specified in the doc.
all protocol details and hICN header formats are now abstracted by the library
for the forwarder (and thus header.h and protocols/*.h have been removed from
public includes, and replaced by packet.h providing protocol agnostic packet
level functions, completely replacing the compat.h header that used to provide
similar functions.
- this works by exposing a opaque buffer to the application (a kind of socket buffer)
which is used by the lib to cache the packet format and offsets of the different
layers in the buffer and provider efficient operations (the packet format is
either defined for packet construction, or guessed at ingress, and this structure
is updated accordingly only once).
Co-authored-by: Jordan Augé <jordan.auge+fdio@cisco.com>
Signed-off-by: Luca Muscariello <muscariello@ieee.org>
Change-Id: I31e321897f85f0267fe8ba4720363c180564492f
Diffstat (limited to 'hicn-light/src/hicn/core')
38 files changed, 1866 insertions, 2345 deletions
diff --git a/hicn-light/src/hicn/core/CMakeLists.txt b/hicn-light/src/hicn/core/CMakeLists.txt index 9516a6a72..94295bdf1 100644 --- a/hicn-light/src/hicn/core/CMakeLists.txt +++ b/hicn-light/src/hicn/core/CMakeLists.txt @@ -3,7 +3,7 @@ # 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 +# 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, @@ -21,7 +21,6 @@ list(APPEND HEADER_FILES ${CMAKE_CURRENT_SOURCE_DIR}/fib_entry.h ${CMAKE_CURRENT_SOURCE_DIR}/fib.h ${CMAKE_CURRENT_SOURCE_DIR}/forwarder.h - ${CMAKE_CURRENT_SOURCE_DIR}/interest_manifest.h ${CMAKE_CURRENT_SOURCE_DIR}/listener.h ${CMAKE_CURRENT_SOURCE_DIR}/listener_table.h ${CMAKE_CURRENT_SOURCE_DIR}/listener_vft.h @@ -34,13 +33,11 @@ list(APPEND HEADER_FILES ${CMAKE_CURRENT_SOURCE_DIR}/strategy_vft.h ${CMAKE_CURRENT_SOURCE_DIR}/subscription.h ${CMAKE_CURRENT_SOURCE_DIR}/ticks.h -# ${CMAKE_CURRENT_SOURCE_DIR}/system.h + + # ${CMAKE_CURRENT_SOURCE_DIR}/system.h ${CMAKE_CURRENT_SOURCE_DIR}/mapme.h ${CMAKE_CURRENT_SOURCE_DIR}/wldr.h - ${CMAKE_CURRENT_SOURCE_DIR}/messageHandler.h - ${CMAKE_CURRENT_SOURCE_DIR}/nameBitvector.h ${CMAKE_CURRENT_SOURCE_DIR}/nexthops.h - ${CMAKE_CURRENT_SOURCE_DIR}/name.h ) list(APPEND SOURCE_FILES @@ -53,15 +50,12 @@ list(APPEND SOURCE_FILES ${CMAKE_CURRENT_SOURCE_DIR}/fib.c ${CMAKE_CURRENT_SOURCE_DIR}/fib_entry.c ${CMAKE_CURRENT_SOURCE_DIR}/forwarder.c - ${CMAKE_CURRENT_SOURCE_DIR}/interest_manifest.c ${CMAKE_CURRENT_SOURCE_DIR}/listener.c ${CMAKE_CURRENT_SOURCE_DIR}/listener_table.c ${CMAKE_CURRENT_SOURCE_DIR}/listener_vft.c ${CMAKE_CURRENT_SOURCE_DIR}/mapme.c ${CMAKE_CURRENT_SOURCE_DIR}/msgbuf.c ${CMAKE_CURRENT_SOURCE_DIR}/msgbuf_pool.c - ${CMAKE_CURRENT_SOURCE_DIR}/nameBitvector.c - ${CMAKE_CURRENT_SOURCE_DIR}/name.c ${CMAKE_CURRENT_SOURCE_DIR}/nexthops.c ${CMAKE_CURRENT_SOURCE_DIR}/packet_cache.c ${CMAKE_CURRENT_SOURCE_DIR}/pit.c diff --git a/hicn-light/src/hicn/core/address.c b/hicn-light/src/hicn/core/address.c index a4b41c8b5..65664fa17 100644 --- a/hicn-light/src/hicn/core/address.c +++ b/hicn-light/src/hicn/core/address.c @@ -21,8 +21,8 @@ #include <hicn/core/address.h> #include <hicn/util/sstrncpy.h> -int address_from_ip_port(address_t *address, int family, ip_address_t *addr, - uint16_t port) { +int address_from_ip_port(address_t *address, int family, + hicn_ip_address_t *addr, uint16_t port) { switch (family) { case AF_INET: *address = ADDRESS4(ntohl(addr->v4.as_inaddr.s_addr), ntohs(port)); diff --git a/hicn-light/src/hicn/core/address.h b/hicn-light/src/hicn/core/address.h index 7958bd063..38cd1e87c 100644 --- a/hicn-light/src/hicn/core/address.h +++ b/hicn-light/src/hicn/core/address.h @@ -63,8 +63,8 @@ static inline bool _address6_is_local(struct sockaddr_in6 *sin6) { ((address)->as_ss.ss_family == AF_INET) ? address4_is_local(address) \ : address6_is_local(address) -int address_from_ip_port(address_t *address, int family, ip_address_t *addr, - uint16_t port); +int address_from_ip_port(address_t *address, int family, + hicn_ip_address_t *addr, uint16_t port); static inline address_t ADDRESS4(in_addr_t in_addr, int port) { address_t address = { diff --git a/hicn-light/src/hicn/core/address_pair.c b/hicn-light/src/hicn/core/address_pair.c index facbb8dc4..c4f8b397b 100644 --- a/hicn-light/src/hicn/core/address_pair.c +++ b/hicn-light/src/hicn/core/address_pair.c @@ -30,8 +30,10 @@ address_pair_t address_pair_factory(address_t local, address_t remote) { } int address_pair_from_ip_port(address_pair_t* pair, int family, - ip_address_t* local_addr, uint16_t local_port, - ip_address_t* remote_addr, uint16_t remote_port) { + hicn_ip_address_t* local_addr, + uint16_t local_port, + hicn_ip_address_t* remote_addr, + uint16_t remote_port) { memset(pair, 0, sizeof(*pair)); if (address_from_ip_port(&pair->local, family, local_addr, local_port) < 0) return -1; diff --git a/hicn-light/src/hicn/core/address_pair.h b/hicn-light/src/hicn/core/address_pair.h index 2fd207d34..b2872ad35 100644 --- a/hicn-light/src/hicn/core/address_pair.h +++ b/hicn-light/src/hicn/core/address_pair.h @@ -40,8 +40,10 @@ typedef struct { address_pair_t address_pair_factory(address_t local, address_t remote); int address_pair_from_ip_port(address_pair_t* pair, int family, - ip_address_t* local_addr, uint16_t local_port, - ip_address_t* remote_addr, uint16_t remote_port); + hicn_ip_address_t* local_addr, + uint16_t local_port, + hicn_ip_address_t* remote_addr, + uint16_t remote_port); static inline int address_pair_equals(const address_pair_t* pair1, const address_pair_t* pair2) { diff --git a/hicn-light/src/hicn/core/connection.c b/hicn-light/src/hicn/core/connection.c index 2108d30af..ff73a9ae8 100644 --- a/hicn-light/src/hicn/core/connection.c +++ b/hicn-light/src/hicn/core/connection.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -22,8 +22,9 @@ #include <hicn/core/forwarder.h> #include <hicn/core/listener.h> -#include <hicn/util/log.h> #include <hicn/core/wldr.h> +#include <hicn/policy.h> +#include <hicn/util/log.h> #include "connection.h" #include "connection_vft.h" @@ -31,7 +32,7 @@ // This is called by configuration connection_t *connection_create(face_type_t type, const char *name, const address_pair_t *pair, - forwarder_t *forwarder) { + const forwarder_t *forwarder) { assert(face_type_is_valid(type)); assert(pair); assert(forwarder); @@ -70,6 +71,38 @@ connection_t *connection_create(face_type_t type, const char *name, return connection_table_at(table, connection_id); } +netdevice_type_t connection_get_netdevice_type(const char *interface_name) { + if (strncmp(interface_name, "lo", 2) == 0) { + return NETDEVICE_TYPE_LOOPBACK; + } + if ((strncmp(interface_name, "eth", 3) == 0) || + (strncmp(interface_name, "en", 2) == 0)) { + /* eth* en* enx* */ + return NETDEVICE_TYPE_WIRED; + } + if (strncmp(interface_name, "wl", 2) == 0) { + /* wlan* wlp* wlx* */ + return NETDEVICE_TYPE_WIFI; + } + if (strncmp(interface_name, "rmnet_ipa", 9) == 0) { + /* Qualcomm IPA driver */ + return NETDEVICE_TYPE_UNDEFINED; + } + if ((strncmp(interface_name, "rmnet", 5) == 0) || + (strncmp(interface_name, "rev_rmnet", 9) == 0) || + (strncmp(interface_name, "ccmni", 5) == 0)) { + /* + * rmnet* (Qualcomm) ccmni* (MediaTek) + */ + return NETDEVICE_TYPE_CELLULAR; + } + /* usb0 might be cellular (eg Zenfone2) */ + /* what about tethering */ + /* tun* dummy* ... */ + /* bnet* pan* hci* for bluetooth */ + return NETDEVICE_TYPE_UNDEFINED; +} + /** * @brief Initializes a connection * @@ -122,6 +155,30 @@ int connection_initialize(connection_t *connection, face_type_t type, .wldr_autostart = true, }; + connection->interface_type = + connection_get_netdevice_type(connection->interface_name); + +#ifdef WITH_POLICY + connection_clear_tags(connection); + switch (connection->interface_type) { +#if 0 + case NETDEVICE_TYPE_LOOPBACK: + connection_add_tag(connection, POLICY_TAG_LOOPBACK); + break; +#endif + case NETDEVICE_TYPE_WIRED: + connection_add_tag(connection, POLICY_TAG_WIRED); + break; + case NETDEVICE_TYPE_WIFI: + connection_add_tag(connection, POLICY_TAG_WIFI); + break; + case NETDEVICE_TYPE_CELLULAR: + connection_add_tag(connection, POLICY_TAG_CELLULAR); + default: + break; + } +#endif + connection->data = malloc(connection_vft[get_protocol(connection->type)]->data_size); if (!connection->data) goto ERR_DATA; @@ -200,8 +257,8 @@ int connection_finalize(connection_t *connection) { return 0; } -int connection_send_packet(const connection_t *connection, - const uint8_t *packet, size_t size) { +bool connection_send_packet(const connection_t *connection, + const uint8_t *packet, size_t size) { assert(connection); assert(face_type_is_valid(connection->type)); assert(packet); @@ -231,10 +288,12 @@ bool connection_send(connection_t *connection, off_t msgbuf_id, bool queue) { const msgbuf_pool_t *msgbuf_pool = forwarder_get_msgbuf_pool(forwarder); msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); +#if 0 if (connection->wldr) wldr_set_label(connection->wldr, msgbuf); else msgbuf_reset_wldr_label(msgbuf); +#endif return _connection_send(connection, msgbuf, queue); } diff --git a/hicn-light/src/hicn/core/connection.h b/hicn-light/src/hicn/core/connection.h index ac75428dd..b459a6d81 100644 --- a/hicn-light/src/hicn/core/connection.h +++ b/hicn-light/src/hicn/core/connection.h @@ -33,25 +33,30 @@ #define CONNECTION_ID_UNDEFINED ~0 -#ifdef WITH_MAPME +#define foreach_connection_event \ + _(UNDEFINED) \ + _(CREATE) \ + _(DELETE) \ + _(UPDATE) \ + _(SET_UP) \ + _(SET_DOWN) \ + _(PRIORITY_CHANGED) \ + _(TAGS_CHANGED) \ + _(N) + typedef enum { - CONNECTION_EVENT_CREATE, - CONNECTION_EVENT_DELETE, - CONNECTION_EVENT_UPDATE, - CONNECTION_EVENT_SET_UP, - CONNECTION_EVENT_SET_DOWN, - CONNECTION_EVENT_PRIORITY_CHANGED, - CONNECTION_EVENT_TAGS_CHANGED, +#define _(x) CONNECTION_EVENT_##x, + foreach_connection_event +#undef _ } connection_event_t; -#endif /* WITH_MAPME */ - struct wldr_s; typedef struct { unsigned id; char* name; char* interface_name; + netdevice_type_t interface_type; face_type_t type; address_pair_t pair; // bool up; @@ -111,6 +116,7 @@ typedef struct { #define connection_get_admin_state(C) ((C)->admin_state) #define connection_set_admin_state(C, STATE) (C)->admin_state = STATE #define connection_get_interface_name(C) ((C)->interface_name) +#define connection_get_interface_type(C) ((C)->interface_type) #ifdef WITH_POLICY #define connection_get_priority(C) ((C)->priority) @@ -118,7 +124,7 @@ typedef struct { #define connection_get_tags(C) ((C)->tags) #define connection_set_tags(C, TAGS) (C)->tags = TAGS #define connection_has_tag(C, TAG) policy_tags_has(connection_get_tags(C), TAG) -#define connection_add_tag(C, TAG) policy_tags_add(connection_get_tags(X), TAG) +#define connection_add_tag(C, TAG) policy_tags_add(&connection_get_tags(C), TAG) #define connection_remove_tag(C, TAG) \ do { \ policy_tags_t _conn_var(tags); \ @@ -198,7 +204,7 @@ static inline void connection_set_tags(connection_t* connection, connection_t* connection_create(face_type_t type, const char* name, const address_pair_t* pair, - struct forwarder_s* forwarder); + const struct forwarder_s* forwarder); int connection_initialize(connection_t* connection, face_type_t type, const char* name, const char* interface_name, int fd, @@ -207,8 +213,8 @@ int connection_initialize(connection_t* connection, face_type_t type, int connection_finalize(connection_t* connection); -int connection_send_packet(const connection_t* connection, - const uint8_t* packet, size_t size); +bool connection_send_packet(const connection_t* connection, + const uint8_t* packet, size_t size); bool connection_flush(connection_t* connection); diff --git a/hicn-light/src/hicn/core/connection_table.c b/hicn-light/src/hicn/core/connection_table.c index c723073a1..7bc0e2f4c 100644 --- a/hicn-light/src/hicn/core/connection_table.c +++ b/hicn-light/src/hicn/core/connection_table.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -81,6 +81,14 @@ connection_t *connection_table_allocate(const connection_table_t *table, pool_get(table->connections, conn); if (!conn) return NULL; +#ifdef __APPLE__ + // set __uint8_t sin_len to 0 + uint8_t *ptr = (uint8_t *)address_pair_get_local(pair); + *ptr = 0x0; + ptr = (uint8_t *)address_pair_get_remote(pair); + *ptr = 0x0; +#endif /* __APPLE__ */ + off_t id = conn - table->connections; int rc; @@ -106,6 +114,14 @@ void connection_table_deallocate(const connection_table_t *table, const char *name = connection_get_name(conn); const address_pair_t *pair = connection_get_pair(conn); +#ifdef __APPLE__ + // set __uint8_t sin_len to 0 + uint8_t *ptr = (uint8_t *)address_pair_get_local(pair); + *ptr = 0x0; + ptr = (uint8_t *)address_pair_get_remote(pair); + *ptr = 0x0; +#endif /* __APPLE__ */ + // Remove from name hash table khiter_t k = kh_get_ct_name(table->id_by_name, name); assert(k != kh_end(table->id_by_name)); @@ -124,6 +140,14 @@ void connection_table_deallocate(const connection_table_t *table, connection_t *connection_table_get_by_pair(const connection_table_t *table, const address_pair_t *pair) { +#ifdef __APPLE__ + // set __uint8_t sin_len to 0 + uint8_t *ptr = (uint8_t *)address_pair_get_local(pair); + *ptr = 0x0; + ptr = (uint8_t *)address_pair_get_remote(pair); + *ptr = 0x0; +#endif /* __APPLE__ */ + khiter_t k = kh_get_ct_pair(table->id_by_pair, pair); if (k == kh_end(table->id_by_pair)) return NULL; return table->connections + kh_val(table->id_by_pair, k); @@ -196,7 +220,7 @@ int connection_table_get_random_name(const connection_table_t *table, int i, n_attempts = 2 * USHRT_MAX; for (i = 0; i < n_attempts; i++) { int rc = snprintf(name, SYMBOLIC_NAME_LEN, "conn%u", RAND16()); - if (rc >= SYMBOLIC_NAME_LEN) continue; + if (rc < 0 || rc >= SYMBOLIC_NAME_LEN) continue; // Check if generated connection name is a duplicate khiter_t k = kh_get_ct_name(table->id_by_name, name); @@ -209,4 +233,4 @@ int connection_table_get_random_name(const connection_table_t *table, } return 0; -}
\ No newline at end of file +} diff --git a/hicn-light/src/hicn/core/connection_table.h b/hicn-light/src/hicn/core/connection_table.h index 7d4bad761..566443d93 100644 --- a/hicn-light/src/hicn/core/connection_table.h +++ b/hicn-light/src/hicn/core/connection_table.h @@ -160,11 +160,14 @@ connection_t *_connection_table_get_by_id(connection_table_t *table, off_t id); * @return off_t The index of the specified connection in the connection table. */ #define connection_table_get_connection_id(table, conn) \ - (conn - table->connections) + (unsigned)(conn - table->connections) #define connection_table_foreach(table, conn, BODY) \ pool_foreach(table->connections, (conn), BODY) +#define connection_table_foreach_new(table, CONN, BODY) \ + pool_foreach_typed(table->connections, connection_t *, CONN, BODY) + #define connection_table_enumerate(table, i, conn, BODY) \ pool_enumerate(table->connections, (i), (conn), BODY) diff --git a/hicn-light/src/hicn/core/connection_vft.h b/hicn-light/src/hicn/core/connection_vft.h index 1a6ecbb78..cc736905c 100644 --- a/hicn-light/src/hicn/core/connection_vft.h +++ b/hicn-light/src/hicn/core/connection_vft.h @@ -30,8 +30,8 @@ typedef struct { const address_t* remote, const char* interface_name); bool (*flush)(connection_t* connection); bool (*send)(connection_t* connection, msgbuf_t* msgbuf, bool queue); - int (*send_packet)(const connection_t* connection, const uint8_t* packet, - size_t size); + bool (*send_packet)(const connection_t* connection, const uint8_t* packet, + size_t size); // void (*read_callback)(connection_t * connection, int fd, void * data); size_t data_size; } connection_ops_t; diff --git a/hicn-light/src/hicn/core/fib.c b/hicn-light/src/hicn/core/fib.c index d8d3c7cfa..64dd3fe7d 100644 --- a/hicn-light/src/hicn/core/fib.c +++ b/hicn-light/src/hicn/core/fib.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -19,20 +19,21 @@ #include <hicn/core/fib.h> typedef struct fib_node_s { - struct fib_node_s *left; - struct fib_node_s *right; + struct fib_node_s *child[2]; /* 0: left, 1: right */ fib_entry_t *entry; bool is_used; } fib_node_t; +#define ZERO 0 +#define ONE 1 + static fib_node_t *fib_node_create(fib_node_t *left, fib_node_t *right, fib_entry_t *entry, bool is_used) { fib_node_t *node = malloc(sizeof(fib_node_t)); if (!node) return NULL; *node = (fib_node_t){ - .left = left, - .right = right, + .child = {left, right}, .entry = entry, .is_used = is_used, }; @@ -43,8 +44,8 @@ static fib_node_t *fib_node_create(fib_node_t *left, fib_node_t *right, static void fib_node_free(fib_node_t *node) { if (!node) return; - fib_node_free(node->right); - fib_node_free(node->left); + fib_node_free(node->child[ZERO]); + fib_node_free(node->child[ONE]); fib_entry_free(node->entry); free(node); @@ -82,293 +83,387 @@ size_t fib_get_size(const fib_t *fib) { return fib->size; } -#define FIB_SET(CURR, NEW_PREFIX, CURR_PREFIX_LEN) \ - do { \ - bool bit; \ - int res = nameBitvector_testBit(NEW_PREFIX, CURR_PREFIX_LEN, &bit); \ - assert(res >= 0); \ - (void)res; /* unused */ \ - CURR = bit ? CURR->right : CURR->left; \ - } while (0) - -#define FIB_INSERT(DST, SRC, PREFIX, PREFIX_LEN) \ - do { \ - bool bit; \ - int res = nameBitvector_testBit(PREFIX, PREFIX_LEN, &bit); \ - assert(res >= 0); \ - (void)res; /* unused */ \ - if (bit) \ - DST->right = SRC; \ - else \ - DST->left = SRC; \ - } while (0) - -void fib_add(fib_t *fib, fib_entry_t *entry) { - assert(fib); - assert(entry); +/* + * This struct will hold various information related to the returned node such + * as its parent and grandparent if any, as well as some already computed + * information about the prefix. + */ +typedef struct { + /* Result node ancestors (NULL if not applicable) */ + fib_node_t *parent; + fib_node_t *gparent; + /* Information related to the result node */ + hicn_prefix_t *prefix; + uint32_t prefix_len; + uint32_t match_len; +} fib_search_t; +/* + * @brief Search for longest subprefix (helper function) + * @param [in] fib - Pointer to the FIB to search + * @param [in] prefix - The prefix used for search + * @param [out] search - A pointer to a structure that will hold related search + * information, that can be NULL if this is not needed. + * + * @returns The node whose entry corresponds to the longest subprefix of the + * prefix passed in parameter, or NULL if not found. The longest prefix match is + * thus the resulting node if curr_len == prefix_len, and its parent + * otherwise. + * + * Implementation details: + * + * This function performs a descent in the tree, following branches + * corresponding to the value of the next bit, until reaching past a leaf, or + * either the current node prefix: + * when one of the two following conditions is met: + * - is not a prefix of the searched one (match_len < curr_len), or + * - is longer or equal than the inserted one (curr_len >= prefix_len) + */ +fib_node_t *fib_search(const fib_t *fib, const hicn_prefix_t *prefix, + fib_search_t *search) { + uint32_t prefix_len = hicn_prefix_get_len(prefix); + uint32_t curr_len; + uint32_t match_len; - NameBitvector *new_prefix = name_GetContentName(fib_entry_get_prefix(entry)); - uint32_t new_prefix_len = nameBitvector_GetLength(new_prefix); + fib_node_t *parent = NULL; + fib_node_t *gparent = NULL; fib_node_t *curr = fib->root; - fib_node_t *last = NULL; + while (curr) { + const hicn_prefix_t *curr_prefix = fib_entry_get_prefix(curr->entry); + curr_len = hicn_prefix_get_len(curr_prefix); + match_len = hicn_prefix_lpm(prefix, curr_prefix); + + // XXX >= vs == for the second stop condition + // curr_len >= prefix_len l >= L + // L is a prefix of l + // > means we did not find + // = means we could have found + // leverage this info for contains! + // XXX remove this comment when done + if (match_len < curr_len || curr_len >= prefix_len) break; + + gparent = parent; + parent = curr; - NameBitvector *curr_name; - uint32_t curr_prefix_len; - uint32_t match_len; + /* The following lookup won't fail since curr_len < prefix_len */ + uint8_t next_bit = hicn_prefix_get_bit(prefix, curr_len); + curr = curr->child[next_bit]; + } - while (curr) { - curr_name = name_GetContentName(fib_entry_get_prefix(curr->entry)); + if (search) { + search->parent = parent; + search->gparent = gparent; + if (curr) { + search->prefix_len = curr_len; + search->match_len = match_len; + } + } + return curr; +} - match_len = nameBitvector_lpm(new_prefix, curr_name); - curr_prefix_len = nameBitvector_GetLength(curr_name); +/* + * Helper: insert a new node between parent and child. + * + * parent == NULL means we set the root of the FIB + * child == NULL means our node has no child + */ +fib_node_t *_fib_insert(fib_t *fib, fib_entry_t *entry, fib_node_t *parent, + fib_node_t *child, bool is_used) { + fib_node_t *new_node = fib_node_create(NULL, NULL, entry, is_used); + const hicn_prefix_t *prefix = fib_entry_get_prefix(entry); - if (curr_prefix_len != - match_len || // the new entry does not match the curr - curr_prefix_len >= - new_prefix_len) // in this case we cannot procede anymore - break; + if (!parent) { + fib->root = new_node; + } else { + const hicn_prefix_t *parent_prefix = fib_entry_get_prefix(parent->entry); + uint32_t parent_prefix_len = hicn_prefix_get_len(parent_prefix); + uint8_t next_bit = hicn_prefix_get_bit(prefix, parent_prefix_len); + parent->child[next_bit] = new_node; + } - last = curr; - FIB_SET(curr, new_prefix, curr_prefix_len); + if (child) { + const hicn_prefix_t *curr_prefix = fib_entry_get_prefix(entry); + uint32_t match_len = hicn_prefix_lpm(prefix, curr_prefix); + uint8_t next_bit = hicn_prefix_get_bit(curr_prefix, match_len); + new_node->child[next_bit] = child; } - // this is the root (empty trie) or an empty child - if (!curr) { - fib_node_t *new_node = fib_node_create(NULL, NULL, entry, true); - if (!last) { - fib->root = new_node; - } else { - uint32_t last_prefix_len = nameBitvector_GetLength( - name_GetContentName(fib_entry_get_prefix(last->entry))); + if (is_used) fib->size++; + return new_node; +} - FIB_INSERT(last, new_node, new_prefix, last_prefix_len); - } - fib->size++; - return; +/* + * Helper: remove a node from parent + */ +void _fib_remove(fib_t *fib, fib_node_t *curr, fib_node_t *parent) { + /* + * If we remove the node, curr has either 0 or 1 child. In the latter case, + * we attach it to parent + */ + fib_node_t *child = curr->child[ZERO] ? curr->child[ZERO] : curr->child[ONE]; + if (!parent) { + fib->root = child; + } else { + if (parent->child[ZERO] == curr) + parent->child[ZERO] = child; + else + parent->child[ONE] = child; } + if (curr->is_used) fib->size--; + fib_node_free(curr); +} + +/* + * - Stop condition: curr == NULL. This corresponds to: + * + * (CASE 1) Our parent is a strict prefix and we simply have to create a new + * leaf child in the correct branch based on the next bit following the parent + * prefix. + * + * Otherwise, our parent node exist. Based on the stop condition, we + * either have: + * + * - Stop condition 1 : curr_len == match_len AND curr_len >= + * prefix_len l == m && l >= L + * + * 2 sub-cases: + * - l = m > L : IMPOSSIBLE L < m since m = LPM(l, L) means L >= m + * - l = m = L : insert the current node, either it exists or not + * + * We thus have: + * + * (CASE 2) The node already exist. If is not in use we turn it on and we set + * the right fib entry. + * + * The case when it is used should never occur because of the way we add + * entries in the FIB... but let's add the nexthops we wish to insert into + * the existing FIB entry. + * + * - Stop condition 2: curr_len != match_len + * l != m => l > m + * + * We have two possibilities: + * - Only one is bigger than m (case 3) + * - They are both bigger than m (case 4) + * + * (CASE 3) Only one is bigger than m + * L == m => L < l (since l != m and l >= m) + * l > L = m + * + * This means L is a prefix of l. + * l' + * / + * L + * / + * l + * + * (CASE 4) They are both bigger than m + * - l > L > m + * - L > l > m + * - L = l > m + * + * Both share L and l share l' as a common prefix, and this is not l' since + * they share the name next bit. + * + * So this case is impossible and we would have taken the other branch during + * the descent: + * + * l' + * / \ + * l L + * + * We are in a situation where e need to insert an internal node: + * + * l' + * | + * X <------ internal node + * / \ + * l L + */ +void fib_add(fib_t *fib, fib_entry_t *entry) { + assert(fib); + assert(entry); + + const hicn_prefix_t *prefix = fib_entry_get_prefix(entry); + uint32_t prefix_len = hicn_prefix_get_len(prefix); + + fib_search_t search; + fib_node_t *curr = fib_search(fib, prefix, &search); - // curr is not null + /* Case 1 */ + if (!curr) { + _fib_insert(fib, entry, search.parent, NULL, true); + return; + } - // the node already exist - // if is not in use we turn it on and we set the rigth fib entry - if (curr_prefix_len == match_len && new_prefix_len == match_len) { + /* Case 2 */ + if (search.prefix_len == search.match_len && prefix_len == search.match_len) { if (!curr->is_used) { curr->is_used = true; + if (curr->entry) fib_entry_free(curr->entry); curr->entry = entry; fib->size++; - return; } else { - // this case should never happen beacuse of the way we add - // entries in the fib const nexthops_t *nexthops = fib_entry_get_nexthops(entry); - unsigned nexthop; nexthops_foreach(nexthops, nexthop, { fib_entry_nexthops_add(curr->entry, nexthop); }); + fib_entry_free(entry); } + return; } - // key is prefix of the curr node (so new_prefix_len < curr_prefix_len) - if (new_prefix_len == match_len) { - fib_node_t *new_node = fib_node_create(NULL, NULL, entry, true); - if (!last) { - fib->root = new_node; - } else { - uint32_t last_prefix_len = nameBitvector_GetLength( - name_GetContentName(fib_entry_get_prefix(last->entry))); - FIB_INSERT(last, new_node, new_prefix, last_prefix_len); - } - FIB_INSERT(new_node, curr, curr_name, match_len); - fib->size++; + /* Case 3 */ + if (prefix_len == search.match_len) { + _fib_insert(fib, entry, search.parent, curr, true); return; } - // in the last case we need to add an inner node - Name inner_prefix = EMPTY_NAME; - name_Copy(fib_entry_get_prefix(entry), &inner_prefix); - nameBitvector_clear(name_GetContentName(&inner_prefix), match_len); - name_setLen(&inner_prefix, match_len); - - // this is an inner node, we don't want an acctive strategy - // like low_latency that sends probes in this node + /* Case 4 */ + hicn_prefix_t inner_prefix; /* dup'ed in fib_entry_create */ + hicn_prefix_copy(&inner_prefix, prefix); + hicn_prefix_truncate(&inner_prefix, search.match_len); fib_entry_t *inner_entry = fib_entry_create( &inner_prefix, STRATEGY_TYPE_UNDEFINED, NULL, fib->forwarder); - - fib_node_t *inner_node = fib_node_create(NULL, NULL, inner_entry, false); - fib_node_t *new_node = fib_node_create(NULL, NULL, entry, true); - - if (!last) { - // we need to place the inner_node at the root - fib->root = inner_node; - } else { - uint32_t last_prefix_len = nameBitvector_GetLength( - name_GetContentName(fib_entry_get_prefix(last->entry))); - NameBitvector *inner_name = name_GetContentName(&inner_prefix); - FIB_INSERT(last, inner_node, inner_name, last_prefix_len); - } - - bool bit; - int res = nameBitvector_testBit(new_prefix, match_len, &bit); - assert(res >= 0); - (void)res; /* unused */ - inner_node->left = bit ? curr : new_node; - inner_node->right = bit ? new_node : curr; - fib->size++; + fib_node_t *new_node = + _fib_insert(fib, inner_entry, search.parent, curr, false); + _fib_insert(fib, entry, new_node, NULL, true); } -fib_entry_t *fib_contains(const fib_t *fib, const Name *prefix) { +/* + * Implementation details: + * + * To find whether the fib contains a prefix, we issue a search, and based on + * the stopping conditions, we return the entry if and only if curr + * is not NULL, and prefix_len == curr_len (== match_len) + */ +fib_entry_t *fib_contains(const fib_t *fib, const hicn_prefix_t *prefix) { assert(fib); assert(prefix); - NameBitvector *key_name = name_GetContentName(prefix); - uint32_t key_prefix_len = nameBitvector_GetLength(key_name); + uint32_t prefix_len = hicn_prefix_get_len(prefix); - fib_node_t *curr = fib->root; + fib_search_t search; + fib_node_t *curr = fib_search(fib, prefix, &search); - while (curr) { - NameBitvector *curr_name = - name_GetContentName(fib_entry_get_prefix(curr->entry)); - uint32_t match_len = nameBitvector_lpm(key_name, curr_name); - uint32_t curr_prefix_len = nameBitvector_GetLength(curr_name); - - if (match_len < curr_prefix_len) { - // the current node does not match completelly the key, so - // the key is not in the trie - // this implies curr_prefix_len > key_prefix_len - return NULL; - } - - if (curr_prefix_len == key_prefix_len) { //== match_len - // this is an exact match - if (!curr->is_used) { - // the key does not exists - return NULL; - } - // we found the key - return curr->entry; - } - - FIB_SET(curr, key_name, curr_prefix_len); - } - - return NULL; + if (!curr) return NULL; + if (search.prefix_len != prefix_len) return NULL; + return curr->is_used ? curr->entry : NULL; } -static void fib_node_remove(fib_t *fib, const Name *prefix) { +/* + * @brief Remove a prefix (and the associated node) from FIB + * + * We search for + * + * Actions depend on N, the number of children of the node to remove + * Examples are build using 'left' children only, but the cases with 'right' + * children are symmetrical. + * + * Legend: + * (empty) : no children + * * : 0 or more children + * + : at least one children + * + * N == 2 - Mark the node as unused + * + * parent parent + * / \ / \ + * curr ... ==> (curr) ... + * / \ / \ + * L R L R + * + * N == 1 - Attach the child to the parent node (whether parent is used or not) + * + * a) curr has no parent (curr is the root) + * + * curr + + * / ==> + * + + * + * b) curr has a parent + * parent parent + * / \ / \ + * curr * ==> L * + * / \ + * L + * + * (parent) (parent) + * / \ / \ + * curr + ==> L + + * / \ + * L + * + * N == 0 + * + * a) curr has no parent (curr is the root) + * + * curr + * / \ ==> + * + * b) parent is unused. + * + * Assuming curr is the left child, then parent must have a + * right child, and the grand-parent must be used. + * + * gp gp gp + * / / / + * (parent) ==> (parent) ==> + + * / \ / \ + * curr + + + * / \ + * + * c) parent is used. + * + * Assuming curr is the left child, we simply remove it from + * parent, leaving parent unchanged whether it has a right child or not. + * + * parent parent + * / \ / \ + * curr * ==> * + * / \ + * + * + */ +static void fib_node_remove(fib_t *fib, const hicn_prefix_t *prefix) { assert(fib); assert(prefix); - NameBitvector *key_name = name_GetContentName(prefix); - uint32_t key_prefix_len = nameBitvector_GetLength(key_name); + uint32_t prefix_len = hicn_prefix_get_len(prefix); - fib_node_t *curr = fib->root; - fib_node_t *parent = NULL; - fib_node_t *grandpa = NULL; + fib_search_t search; + fib_node_t *curr = fib_search(fib, prefix, &search); - uint32_t match_len; - uint32_t curr_prefix_len; + /* + * If we reach a NULL, unused node, or a node not matching, that means the + * node does not exist + */ + if (!curr || !curr->is_used || (search.prefix_len != prefix_len)) return; - while (curr) { - NameBitvector *curr_name = - name_GetContentName(fib_entry_get_prefix(curr->entry)); - match_len = nameBitvector_lpm(key_name, curr_name); - curr_prefix_len = nameBitvector_GetLength(curr_name); + uint8_t N = 0; + if (curr->child[ZERO]) N++; + if (curr->child[ONE]) N++; - if (match_len < curr_prefix_len || curr_prefix_len == key_prefix_len) { + switch (N) { + case 2: + curr->is_used = false; break; - } - - grandpa = parent; - parent = curr; - FIB_SET(curr, key_name, curr_prefix_len); - } - - if (!curr || !curr->is_used || (curr_prefix_len != key_prefix_len)) { - // the node does not exists - return; - } - - // curr has 2 children, leave it there and mark it as inner - if (curr->right && curr->left) { - curr->is_used = false; - fib->size--; - return; - } - - // curr has no children - if (!curr->right && !curr->left) { - if (!parent) { - // curr is the root and is the only node in the fib - fib->root = NULL; - fib->size--; - fib_node_free(curr); - return; - } - if (!grandpa) { - // parent is the root - if (fib->root->left == curr) - fib->root->left = NULL; - else - fib->root->right = NULL; - fib->size--; - fib_node_free(curr); - return; - } - if (!parent->is_used) { - // parent is an inner node - // remove curr and inner_node (parent), connect the other child - // of the parent to the grandpa - fib_node_t *tmp = (parent->right == curr) ? parent->left : parent->right; - - if (grandpa->right == parent) - grandpa->right = tmp; - else - grandpa->left = tmp; - - fib->size--; - fib_node_free(curr); - fib_node_free(parent); - return; - } - // parent is node not an inner_node - // just remove curr the node - if (parent->right == curr) - parent->right = NULL; - else - parent->left = NULL; - fib->size--; - fib_node_free(curr); - return; - } - - // curr has one child - if (curr->right || curr->left) { - if (!parent) { - // curr is the root - fib->root = fib->root->right ? fib->root->right : fib->root->left; - fib->size--; - fib_node_free(curr); - return; - } - // attach the child of curr to parent - fib_node_t *tmp = curr->right ? curr->right : curr->left; - - if (parent->right == curr) - parent->right = tmp; - else - parent->left = tmp; + case 1: + _fib_remove(fib, curr, search.parent); + break; - fib->size--; - fib_node_free(curr); - return; + case 0: + _fib_remove(fib, curr, search.parent); + if (!search.parent->is_used) + _fib_remove(fib, search.parent, search.gparent); + break; } } -void fib_remove(fib_t *fib, const Name *name, unsigned conn_id) { +void fib_remove(fib_t *fib, const hicn_prefix_t *prefix, unsigned conn_id) { assert(fib); - assert(name); + assert(prefix); - fib_entry_t *entry = fib_contains(fib, name); + fib_entry_t *entry = fib_contains(fib, prefix); if (!entry) return; fib_entry_nexthops_remove(entry, conn_id); @@ -382,16 +477,24 @@ static size_t fib_node_remove_connection_id(fib_node_t *node, unsigned conn_id, if (!node) return pos; if (node->is_used) { fib_entry_nexthops_remove(node->entry, conn_id); + + /* When using MAP-Me, we keep empty FIB entries */ #ifndef WITH_MAPME if (fib_entry_nexthops_len(node->entry) == 0) array[pos++] = node->entry; #endif /* WITH_MAPME */ } - pos = fib_node_remove_connection_id(node->right, conn_id, array, pos); - pos = fib_node_remove_connection_id(node->left, conn_id, array, pos); + pos = fib_node_remove_connection_id(node->child[ONE], conn_id, array, pos); + pos = fib_node_remove_connection_id(node->child[ZERO], conn_id, array, pos); return pos; } -void fib_remove_connection_id(fib_t *fib, unsigned conn_id) { +void fib_remove_entry(fib_t *fib, fib_entry_t *entry) { + fib_node_remove(fib, fib_entry_get_prefix(entry)); +} + +void fib_remove_connection(fib_t *fib, unsigned conn_id, + fib_entry_t ***removed_entries, + size_t *num_removed_entries) { assert(fib); fib_entry_t **array = malloc(sizeof(fib_entry_t *) * fib->size); @@ -399,61 +502,64 @@ void fib_remove_connection_id(fib_t *fib, unsigned conn_id) { size_t pos = 0; pos = fib_node_remove_connection_id(fib->root, conn_id, array, pos); - for (int i = 0; i < pos; i++) - fib_node_remove(fib, fib_entry_get_prefix(array[i])); - free(array); -} + if (removed_entries) { + /* + * The caller is taking charge of releasing entries (as well as the returned + * array + */ + assert(num_removed_entries); -fib_entry_t *fib_match_message(const fib_t *fib, - const msgbuf_t *interest_msgbuf) { - assert(fib); - assert(interest_msgbuf); + *removed_entries = array; + *num_removed_entries = pos; - return fib_match_bitvector( - fib, name_GetContentName(msgbuf_get_name(interest_msgbuf))); + } else { + for (int i = 0; i < pos; i++) + fib_node_remove(fib, fib_entry_get_prefix(array[i])); + } + free(array); } -fib_entry_t *fib_match_name(const fib_t *fib, const Name *name) { +fib_entry_t *fib_match_msgbuf(const fib_t *fib, const msgbuf_t *msgbuf) { assert(fib); - assert(name); + assert(msgbuf); - return fib_match_bitvector(fib, name_GetContentName(name)); + return fib_match_name(fib, msgbuf_get_name(msgbuf)); } -fib_entry_t *fib_match_bitvector(const fib_t *fib, const NameBitvector *name) { +/* + * Implementation details: + * + * fib_search returns the longest non-strict subprefix. + * - curr == NULL means no such prefix exist and we can return the parent. + * - if we have an exact match (curr_len == key_prefix_len), then we + * return curr unless is_used is false, in which case we return the parent. + * - otherwise, the parent is the longest prefix match + */ +fib_entry_t *fib_match_prefix(const fib_t *fib, const hicn_prefix_t *prefix) { assert(fib); - assert(name); - - uint32_t key_prefix_len = nameBitvector_GetLength(name); + assert(prefix); - fib_node_t *curr = fib->root; - fib_node_t *candidate = NULL; + uint32_t prefix_len = hicn_prefix_get_len(prefix); - while (curr) { - NameBitvector *curr_name = - name_GetContentName(fib_entry_get_prefix(curr->entry)); - uint32_t match_len = nameBitvector_lpm(name, curr_name); - uint32_t curr_prefix_len = nameBitvector_GetLength(curr_name); - - if (match_len < curr_prefix_len) { - // the current node does not match completelly the key, so - // return the parent of this node (saved in candidate) - break; - } - - if (curr->is_used) candidate = curr; + fib_search_t search; + fib_node_t *curr = fib_search(fib, prefix, &search); - // if we are here match_len == curr_prefix_len (can't be larger) - // so this node is actually a good candidate for a match - if (curr_prefix_len == key_prefix_len) { - // this an exact match, do not continue - break; - } - - FIB_SET(curr, name, curr_prefix_len); + if (!curr) { + /* This can happen with an empty FIB for instance */ + if (!search.parent) return NULL; + return search.parent->entry; } + if ((search.prefix_len <= prefix_len) && curr->is_used) return curr->entry; + if (search.parent) return search.parent->entry; + return NULL; +} - return candidate ? candidate->entry : NULL; +fib_entry_t *fib_match_name(const fib_t *fib, const hicn_name_t *name) { + hicn_prefix_t prefix; + const hicn_name_prefix_t *name_prefix = hicn_name_get_prefix(name); + prefix.name = *name_prefix; + prefix.len = hicn_name_prefix_get_len_bits(name_prefix); + return fib_match_prefix(fib, &prefix); } static size_t fib_node_collect_entries(fib_node_t *node, fib_entry_t **array, @@ -464,8 +570,8 @@ static size_t fib_node_collect_entries(fib_node_t *node, fib_entry_t **array, if (node->is_used) array[pos++] = node->entry; - pos = fib_node_collect_entries(node->right, array, pos); - pos = fib_node_collect_entries(node->left, array, pos); + pos = fib_node_collect_entries(node->child[ONE], array, pos); + pos = fib_node_collect_entries(node->child[ZERO], array, pos); return pos; } @@ -476,3 +582,123 @@ size_t fib_get_entry_array(const fib_t *fib, fib_entry_t ***array_p) { pos = fib_node_collect_entries(fib->root, *array_p, pos); return pos; } + +bool _fib_is_valid(const fib_node_t *node) { + if (!node) return true; + + const hicn_prefix_t *prefix = fib_entry_get_prefix(node->entry); + uint32_t prefix_len = hicn_prefix_get_len(prefix); + + for (unsigned i = 0; i < 2; i++) { + const fib_node_t *child = node->child[i]; + if (!child) continue; + const hicn_prefix_t *child_prefix = fib_entry_get_prefix(child->entry); + + uint32_t match_len = hicn_prefix_lpm(prefix, child_prefix); + if (match_len != prefix_len) return false; + if (!node->is_used && !child->is_used) return false; + if (hicn_prefix_get_bit(child_prefix, match_len) != i) return false; + if (!_fib_is_valid(child)) return false; + } + return true; +} + +/* + * @brief Check that the structure of the FIB is correct : prefixes are + * correctly nested, 0 are on the left, 1 on the right, and that we have no + * more than 1 unused prefix as parents. + */ +bool fib_is_valid(const fib_t *fib) { return _fib_is_valid(fib->root); } + +/* + * Checks whether the preorder traversal of the sub-tree corresponds to the + * prefix and used arrays, starting from pos (helper) + */ +bool __fib_check_preorder(const fib_node_t *node, + const hicn_prefix_t **prefix_array, bool *used_array, + size_t size, size_t *pos) { + /* Check left subtree... */ + fib_node_t *left = node->child[ZERO]; + if (left && !__fib_check_preorder(left, prefix_array, used_array, size, pos)) + return false; + + /* ... then current node ... */ + if (*pos > size) { + ERROR("size error"); + return false; + } + + const hicn_prefix_t *prefix = fib_entry_get_prefix(node->entry); + + if (!hicn_prefix_equals(prefix, prefix_array[*pos])) { + char buf[MAXSZ_HICN_PREFIX]; + int rc; + + ERROR("Prefix mismatch in position %d %s != %s", pos); + rc = hicn_prefix_snprintf(buf, MAXSZ_HICN_PREFIX, prefix); + if (rc < 0 || rc >= MAXSZ_HICN_PREFIX) + snprintf(buf, MAXSZ_HICN_PREFIX, "%s", "(error)"); + ERROR("Expected: %s", buf); + + rc = hicn_prefix_snprintf(buf, MAXSZ_HICN_PREFIX, prefix_array[*pos]); + if (rc < 0 || rc >= MAXSZ_HICN_PREFIX) + snprintf(buf, MAXSZ_HICN_PREFIX, "%s", "(error)"); + ERROR("Expected: %s", buf); + return false; + } + + (*pos)++; + + /* ... then right subtree */ + fib_node_t *right = node->child[ONE]; + if (right && + !__fib_check_preorder(right, prefix_array, used_array, size, pos)) + return false; + + return true; +} + +/* + * Checks whether the preorder traversal of the trie + * corresponds to the prefix and used arrays. + */ +bool _fib_check_preorder(const fib_t *fib, const hicn_prefix_t **prefix_array, + bool *used_array, size_t size) { + if (!fib->root) return true; + size_t pos = 0; + if (!__fib_check_preorder(fib->root, prefix_array, used_array, size, &pos)) + return false; + /* We need to check that we don't miss elements */ + return pos == size; +} + +// XXX print empty node but not recurse +void _fib_dump(const fib_node_t *node, int start, int indent) { + char buf[MAXSZ_HICN_PREFIX]; + + if (node) { + const hicn_prefix_t *prefix = fib_entry_get_prefix(node->entry); + int rc = hicn_prefix_snprintf(buf, MAXSZ_HICN_PREFIX, prefix); + if (rc < 0 || rc >= MAXSZ_HICN_PREFIX) + snprintf(buf, MAXSZ_HICN_PREFIX, "%s %d", "(error)", rc); + } else { + snprintf(buf, MAXSZ_HICN_PREFIX, "%s", "(null)"); + } + + // Left + if (indent > 0) { + for (int i = 0; i < start - 1; i++) printf(" "); + for (int i = start + 1; i < indent; i++) printf("| "); + printf("|"); + printf("_ %s\n", buf); + } else { + printf("%s\n", buf); + } + + if (!node) return; + + _fib_dump(node->child[ZERO], start, indent + 1); + _fib_dump(node->child[ONE], start + 1, indent + 1); +} + +void fib_dump(const fib_t *fib) { _fib_dump(fib->root, 0, 0); } diff --git a/hicn-light/src/hicn/core/fib.h b/hicn-light/src/hicn/core/fib.h index c0fda960b..501935b0b 100644 --- a/hicn-light/src/hicn/core/fib.h +++ b/hicn-light/src/hicn/core/fib.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -18,7 +18,7 @@ #include "fib_entry.h" #include "msgbuf.h" -#include "name.h" +#include <hicn/name.h> #define _fib_var(x) _fib_##x @@ -32,24 +32,39 @@ size_t fib_get_size(const fib_t *fib); void fib_add(fib_t *fib, fib_entry_t *node); -fib_entry_t *fib_contains(const fib_t *fib, const Name *prefix); +fib_entry_t *fib_contains(const fib_t *fib, const hicn_prefix_t *prefix); -void fib_remove(fib_t *fib, const Name *prefix, unsigned conn_id); +void fib_remove(fib_t *fib, const hicn_prefix_t *prefix, unsigned conn_id); -void fib_remove_connection_id(fib_t *fib, unsigned conn_id); +void fib_remove_entry_connection(fib_t *fib, fib_entry_t *entry, + unsigned conn_id, fib_entry_t **removed_entry); -fib_entry_t *fib_match_message(const fib_t *fib, - const msgbuf_t *interest_msgbuf); -fib_entry_t *fib_match_name(const fib_t *fib, const Name *name); -fib_entry_t *fib_match_bitvector(const fib_t *fib, const NameBitvector *name); +void fib_remove_name_connection(fib_t *fib, const hicn_prefix_t *prefix, + unsigned conn_id); + +void fib_remove_entry(fib_t *fib, fib_entry_t *entry); + +void fib_remove_connection(fib_t *fib, unsigned conn_id, + fib_entry_t ***removed_entries, + size_t *num_removed_entries); + +fib_entry_t *fib_match_msgbuf(const fib_t *fib, const msgbuf_t *msgbuf); + +fib_entry_t *fib_match_prefix(const fib_t *fib, const hicn_prefix_t *prefix); + +fib_entry_t *fib_match_name(const fib_t *fib, const hicn_name_t *name); size_t fib_get_entry_array(const fib_t *fib, fib_entry_t ***array_p); +/* + * NOTE : do not use return on the loop body to avoid leaking memory + */ #define fib_foreach_entry(FIB, ENTRY, BODY) \ do { \ fib_entry_t **_fib_var(array); \ size_t _fib_var(n) = fib_get_entry_array((FIB), &_fib_var(array)); \ size_t _fib_var(i); \ + fib_entry_t *ENTRY; \ for (_fib_var(i) = 0; _fib_var(i) < _fib_var(n); _fib_var(i)++) { \ ENTRY = _fib_var(array)[_fib_var(i)]; \ do { \ @@ -59,4 +74,13 @@ size_t fib_get_entry_array(const fib_t *fib, fib_entry_t ***array_p); free(_fib_var(array)); \ } while (0) +bool fib_is_valid(const fib_t *fib); +bool _fib_check_preorder(const fib_t *fib, const hicn_prefix_t **prefix_array, + bool *used_array, size_t size); + +#define fib_check_preorder(F, PA, UA) \ + _fib_check_preorder(F, PA, UA, sizeof(PA) / sizeof(hicn_prefix_t *)) + +void fib_dump(const fib_t *fib); + #endif /* HICNLIGHT_FIB_H */ diff --git a/hicn-light/src/hicn/core/fib_entry.c b/hicn-light/src/hicn/core/fib_entry.c index 80d337884..b588e3638 100644 --- a/hicn-light/src/hicn/core/fib_entry.c +++ b/hicn-light/src/hicn/core/fib_entry.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -18,7 +18,6 @@ #include <hicn/hicn-light/config.h> #include <hicn/core/fib_entry.h> #include <hicn/core/strategy.h> -#include <hicn/core/nameBitvector.h> #ifdef WITH_MAPME #include <hicn/core/ticks.h> @@ -38,17 +37,22 @@ #include <hicn/core/policy_stats.h> #endif /* WITH_POLICY_STATS */ -fib_entry_t *fib_entry_create(Name *name, strategy_type_t strategy_type, +fib_entry_t *fib_entry_create(const hicn_prefix_t *prefix, + strategy_type_t strategy_type, strategy_options_t *strategy_options, const forwarder_t *forwarder) { - assert(name); - assert(forwarder); + assert(prefix); + /* + * For tests, we allow forwarder to be NULL, some + * functions cannot be called but otherwise we need a main loop, etc. + */ + // assert(forwarder); fib_entry_t *entry = malloc(sizeof(fib_entry_t)); if (!entry) goto ERR_MALLOC; memset(entry, 0, sizeof(*entry)); - name_Copy(name, &entry->name); + hicn_prefix_copy(&entry->prefix, prefix); entry->nexthops = NEXTHOPS_EMPTY; fib_entry_add_strategy_options(entry, STRATEGY_TYPE_BESTPATH, NULL); @@ -148,8 +152,10 @@ void fib_entry_set_strategy(fib_entry_t *entry, strategy_type_t strategy_type, strategy_initialize(&entry->strategy, entry->forwarder); } -#ifdef WITH_POLICY - +/* + * Filters the set of nexthops passed as parameters (and not the one stored in + * the FIB entry + */ nexthops_t *fib_entry_filter_nexthops(fib_entry_t *entry, nexthops_t *nexthops, unsigned ingress_id, bool prefer_local) { assert(entry); @@ -165,7 +171,6 @@ nexthops_t *fib_entry_filter_nexthops(fib_entry_t *entry, nexthops_t *nexthops, const connection_table_t *table = forwarder_get_connection_table(entry->forwarder); connection_t *conn; - unsigned nexthop, i; uint_fast32_t flags; hicn_policy_t policy = fib_entry_get_policy(entry); @@ -205,6 +210,7 @@ nexthops_t *fib_entry_filter_nexthops(fib_entry_t *entry, nexthops_t *nexthops, conn = connection_table_at(table, nexthop); nexthops_disable_if(nexthops, i, (connection_is_local(conn))); +#ifdef WITH_POLICY /* Policy filtering : next hops */ nexthops_disable_if( nexthops, i, @@ -238,6 +244,7 @@ nexthops_t *fib_entry_filter_nexthops(fib_entry_t *entry, nexthops_t *nexthops, nexthops, i, (policy.tags[POLICY_TAG_TRUSTED].state == POLICY_STATE_PROHIBIT) && (connection_has_tag(conn, POLICY_TAG_TRUSTED))); +#endif /* WITH_POLICY */ }); if (nexthops_get_curlen(nexthops) == 0) { @@ -248,6 +255,7 @@ nexthops_t *fib_entry_filter_nexthops(fib_entry_t *entry, nexthops_t *nexthops, /* We have at least one matching next hop, implement heuristic */ +#ifdef WITH_POLICY /* * As VPN connections might trigger duplicate uses of one interface, we start * by filtering out interfaces based on trust status. @@ -329,6 +337,8 @@ nexthops_t *fib_entry_filter_nexthops(fib_entry_t *entry, nexthops_t *nexthops, }); if (nexthops_get_curlen(nexthops) == 0) nexthops->flags = flags; } +// XXX backup curlen ??? +#endif /* WITH_POLICY */ DEBUG("[fib_entry_filter_nexthops] before face priority num=%d/%d", nexthops_get_curlen(nexthops), nexthops_get_len(nexthops)); @@ -349,10 +359,63 @@ nexthops_t *fib_entry_filter_nexthops(fib_entry_t *entry, nexthops_t *nexthops, DEBUG("[fib_entry_filter_nexthops] result num=%d/%d", nexthops_get_curlen(nexthops), nexthops_get_len(nexthops)); + /* Nexthop priority */ + + /* + * Filter out nexthops with lowest strategy priority. + * Initializing at 0 allows to disable nexthops with a negative priority + */ + max_priority = 0; + nexthops_enumerate(nexthops, i, nexthop, { + (void)nexthop; + int priority = nexthops->state[i].priority; + if (priority > max_priority) max_priority = priority; + }); + nexthops_enumerate(nexthops, i, nexthop, { + int priority = nexthops->state[i].priority; + nexthops_disable_if(nexthops, i, (priority < max_priority)); + }); + + /* + * If multipath is disabled, we don't offer much choice to the forwarding + * strategy, but still go through it for accounting purposes. + */ + if ((policy.tags[POLICY_TAG_MULTIPATH].state == POLICY_STATE_PROHIBIT) || + (policy.tags[POLICY_TAG_MULTIPATH].state == POLICY_STATE_AVOID)) { + DEBUG( + "[fib_entry_get_nexthops_from_strategy] select single nexthops due to " + "multipath policy"); + nexthops_select_first(nexthops); + } + return nexthops; } /* + * Retrieve all candidate nexthops for sending mapme updates == all non local + * connections. We don't apply the policy at this stage. + */ +nexthops_t *fib_entry_get_mapme_nexthops(fib_entry_t *entry, + nexthops_t *new_nexthops) { + assert(new_nexthops); + + const connection_table_t *table = + forwarder_get_connection_table(entry->forwarder); + + /* We create a nexthop structure based on connections */ + // XXX This should be done close to where it is needed + connection_t *connection; + connection_table_foreach(table, connection, { + if (connection_is_local(connection)) continue; + new_nexthops->elts[nexthops_get_len(new_nexthops)] = + connection_table_get_connection_id(table, connection); + nexthops_inc(new_nexthops); + }); + + return new_nexthops; +} + +/* * Update available next hops following policy update. * * The last nexthop parameter is only used if needed, otherwise the pointer to @@ -397,13 +460,20 @@ nexthops_t *fib_entry_get_available_nexthops(fib_entry_t *entry, #endif } +#ifdef WITH_POLICY + hicn_policy_t fib_entry_get_policy(const fib_entry_t *entry) { return entry->policy; } void fib_entry_set_policy(fib_entry_t *entry, hicn_policy_t policy) { + INFO("fib_entry_set_policy"); entry->policy = policy; + forwarder_on_route_event(entry->forwarder, entry); + + // XXX generic mechanism to perform a mapme update +#if 0 #ifdef WITH_MAPME /* * Skip entries that do not correspond to a producer ( / have a locally @@ -411,8 +481,8 @@ void fib_entry_set_policy(fib_entry_t *entry, hicn_policy_t policy) { */ if (!fib_entry_has_local_nexthop(entry)) return; mapme_t *mapme = forwarder_get_mapme(entry->forwarder); - mapme_set_all_adjacencies(mapme, entry); #endif /* WITH_MAPME */ +#endif } #endif /* WITH_POLICY */ @@ -475,10 +545,7 @@ nexthops_t *fib_entry_get_nexthops_from_strategy(fib_entry_t *entry, * Initializing at 0 allows to disable nexthops with a negative priority */ unsigned max_priority = 0; - unsigned i; - nexthop_t nexthop; nexthops_enumerate(nexthops, i, nexthop, { - (void)nexthop; int priority = nexthops->state[i].priority; if (priority > max_priority) max_priority = priority; }); @@ -546,9 +613,9 @@ void fib_entry_on_timeout(fib_entry_t *entry, strategy_on_timeout(&entry->strategy, &entry->nexthops, timeout_nexthops); } -const Name *fib_entry_get_prefix(const fib_entry_t *entry) { +const hicn_prefix_t *fib_entry_get_prefix(const fib_entry_t *entry) { assert(entry); - return &(entry->name); + return &(entry->prefix); } /* @@ -557,7 +624,6 @@ const Name *fib_entry_get_prefix(const fib_entry_t *entry) { bool fib_entry_has_local_nexthop(const fib_entry_t *entry) { connection_table_t *table = forwarder_get_connection_table(entry->forwarder); - unsigned nexthop; nexthops_foreach(fib_entry_get_nexthops(entry), nexthop, { const connection_t *conn = connection_table_at(table, nexthop); /* Ignore non-local connections */ diff --git a/hicn-light/src/hicn/core/fib_entry.h b/hicn-light/src/hicn/core/fib_entry.h index 628c4cd4f..b625a33ef 100644 --- a/hicn-light/src/hicn/core/fib_entry.h +++ b/hicn-light/src/hicn/core/fib_entry.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -37,16 +37,20 @@ #ifndef fib_entry_h #define fib_entry_h -#include "name.h" +#include <hicn/name.h> #include "strategy.h" #include "msgbuf.h" #include "nexthops.h" #include "policy_stats.h" typedef struct { - Name name; + hicn_prefix_t prefix; unsigned refcount; nexthops_t nexthops; + + /* This is used for producer prefixes only */ + uint32_t nexthops_hash; + strategy_entry_t strategy; const void *forwarder; @@ -59,10 +63,12 @@ typedef struct { policy_stats_t policy_stats; #ifdef WITH_MAPME +#if 0 /* In case of no multipath, this stores the previous decision taken by policy. * As the list of nexthops is not expected to change, we can simply store the * flags */ uint_fast32_t prev_nexthops_flags; +#endif void *user_data; void (*user_data_release)(void **user_data); #endif /* WITH_MAPME */ @@ -73,6 +79,7 @@ typedef struct { #define fib_entry_strategy_type(fib_entry) ((fib_entry)->strategy.type) #define fib_entry_get_nexthops(fib_entry) (&(fib_entry)->nexthops) + #define fib_entry_nexthops_len(fib_entry) \ (nexthops_get_len(&(fib_entry)->nexthops)) #define fib_entry_nexthops_curlen(fib_entry) \ @@ -81,14 +88,36 @@ typedef struct { #define fib_entry_foreach_nexthop(fib_entry, nexthop, BODY) \ nexthops_foreach(fib_entry->nexthops, BODY) -#define fib_entry_nexthops_changed(fib_entry) \ - ((fib_entry)->prev_nexthops_flags == fib_entry_get_nexthops(fib_entry)->flags) - -#define fib_entry_set_prev_nexthops(fib_entry) \ - ((fib_entry)->prev_nexthops_flags = fib_entry_get_nexthops(fib_entry)->flags) +#define fib_entry_get_nexthops_hash(E) ((E)->nexthops_hash) +#define fib_entry_set_nexthops_hash(E, H) (E)->nexthops_hash = (H) + +static inline void fib_entry_set_nexthops(fib_entry_t *entry, + nexthops_t *nexthops) { + entry->nexthops = *nexthops; +} + +static inline void fib_entry_initialize_nexthops(fib_entry_t *entry) { + entry->nexthops = NEXTHOPS_EMPTY; +} + +static inline bool fib_entry_nexthops_changed(fib_entry_t *entry, + nexthops_t *nexthops) { + uint32_t old_hash = fib_entry_get_nexthops_hash(entry); + uint32_t hash = nexthops_get_hash(nexthops); + if (hash != old_hash) { + fib_entry_set_nexthops_hash(entry, hash); + return true; + } + return false; +}; struct forwarder_s; -fib_entry_t *fib_entry_create(Name *name, strategy_type_t strategy_type, + +/* + * This does a copy of the name passed as parameter + */ +fib_entry_t *fib_entry_create(const hicn_prefix_t *prefix, + strategy_type_t strategy_type, strategy_options_t *strategy_options, const struct forwarder_s *table); @@ -106,8 +135,6 @@ void fib_entry_nexthops_add(fib_entry_t *fib_entry, unsigned nexthop); void fib_entry_nexthops_remove(fib_entry_t *fib_entry, unsigned nexthop); -size_t fib_entry_NexthopCount(const fib_entry_t *fib_entry); - /** * @function fib_entry_nexthops_get * @abstract Returns the nexthop set of the FIB entry. You must Acquire if it @@ -132,6 +159,12 @@ void fib_entry_set_policy(fib_entry_t *fib_entry, hicn_policy_t policy); void fib_entry_update_stats(fib_entry_t *fib_entry, uint64_t now); #endif /* WITH_POLICY */ +nexthops_t *fib_entry_filter_nexthops(fib_entry_t *entry, nexthops_t *nexthops, + unsigned ingress_id, bool prefer_local); + +nexthops_t *fib_entry_get_mapme_nexthops(fib_entry_t *entry, + nexthops_t *new_nexthops); + nexthops_t *fib_entry_get_available_nexthops(fib_entry_t *fib_entry, unsigned in_connection, nexthops_t *new_nexthops); @@ -145,7 +178,7 @@ nexthops_t *fib_entry_get_nexthops_from_strategy( * @abstract Returns a copy of the prefix. * @return A reference counted copy that you must destroy */ -const Name *fib_entry_get_prefix(const fib_entry_t *fib_entry); +const hicn_prefix_t *fib_entry_get_prefix(const fib_entry_t *fib_entry); bool fib_entry_has_local_nexthop(const fib_entry_t *entry); diff --git a/hicn-light/src/hicn/core/forwarder.c b/hicn-light/src/hicn/core/forwarder.c index 74be6431a..482e3d6f1 100644 --- a/hicn-light/src/hicn/core/forwarder.c +++ b/hicn-light/src/hicn/core/forwarder.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -69,7 +69,7 @@ #endif /* WITH_POLICY_STATS */ #include <hicn/core/wldr.h> -#include <hicn/core/interest_manifest.h> +#include <hicn/interest_manifest.h> #include <hicn/util/log.h> struct forwarder_s { @@ -189,9 +189,10 @@ forwarder_t *forwarder_create(configuration_t *configuration) { vector_init(forwarder->pending_conn, MAX_MSG, 0); vector_init(forwarder->acquired_msgbuf_ids, MAX_MSG, 0); - char *n_suffixes_per_split_str = getenv("N_SUFFIXES_PER_SPIT"); + char *n_suffixes_per_split_str = getenv("N_SUFFIXES_PER_SPLIT"); if (n_suffixes_per_split_str) - N_SUFFIXES_PER_SPIT = atoi(n_suffixes_per_split_str); + configuration_set_suffixes_per_split(forwarder_get_configuration(forwarder), + atoi(n_suffixes_per_split_str)); return forwarder; @@ -239,6 +240,162 @@ void forwarder_free(forwarder_t *forwarder) { free(forwarder); } +/* + * An event occurred that might trigger an update of the FIB cache. It is + * possible that the flags have been reset following a connection add or remote. + * The objective of this function is to prepare the cache entry, and to alert of + * any change for both consumer and producer prefixes. + */ +void forwarder_on_route_event(const forwarder_t *forwarder, + fib_entry_t *entry) { + commands_notify_route(forwarder, entry); + + nexthops_t new_nexthops = NEXTHOPS_EMPTY; + nexthops_t *nexthops; + + char *prefix_type_s; + + const connection_table_t *table = + forwarder_get_connection_table(entry->forwarder); + + const hicn_prefix_t *prefix = fib_entry_get_prefix(entry); + + WITH_INFO({ + char buf[MAXSZ_HICN_PREFIX]; + hicn_prefix_snprintf(buf, MAXSZ_HICN_NAME, prefix); + INFO("fib_entry_on_event: %s", buf); + )}; + + if (!fib_entry_has_local_nexthop(entry)) { + /* Recompute FIB cache, then check whether it has changed based on hash */ + prefix_type_s = "consumer"; + nexthops = fib_entry_get_nexthops(entry); + nexthops_reset(nexthops); + fib_entry_filter_nexthops(entry, nexthops, ~0, false); + } else { + /* Check available non-local connections (on which we would send MAP-Me + * updates */ + prefix_type_s = "producer"; + + nexthops = fib_entry_get_mapme_nexthops(entry, &new_nexthops); + fib_entry_filter_nexthops(entry, nexthops, ~0, true); + +#ifdef WITH_MAPME + mapme_set_adjacencies(forwarder->mapme, entry, nexthops); +#endif /* WITH_MAPME */ + } + + if (!fib_entry_nexthops_changed(entry, nexthops)) return; + + /* Send notification */ + WITH_INFO({ + char buf[MAXSZ_HICN_PREFIX]; + hicn_prefix_snprintf(buf, MAXSZ_HICN_NAME, prefix); + INFO("Active interfaces changed for %s prefix %s", prefix_type_s, buf); + }); + + netdevice_flags_t flags = NETDEVICE_FLAGS_EMPTY; + nexthops_foreach(nexthops, nh, { + connection_t *connection = connection_table_get_by_id(table, nh); + netdevice_flags_add(flags, connection_get_interface_type(connection)); + }); + + hicn_ip_prefix_t ip_prefix; + hicn_prefix_get_ip_prefix(prefix, &ip_prefix); + commands_notify_active_interface_update(forwarder, &ip_prefix, flags); +} + +int forwarder_add_connection(const forwarder_t *forwarder, + const char *symbolic_name, face_type_t type, + address_pair_t *pair, policy_tags_t tags, + int priority, face_state_t admin_state) { + connection_table_t *table = forwarder_get_connection_table(forwarder); + connection_t *connection = connection_table_get_by_pair(table, pair); + + if (!connection) { + connection = connection_create(type, symbolic_name, pair, forwarder); + if (!connection) { + ERROR("Failed to create %s connection", face_type_str(type)); + return -1; + } + + } else { + WARN("Connection already exists"); + } + +#ifdef WITH_POLICY + connection_set_tags(connection, tags); + connection_set_priority(connection, priority); +#endif /* WITH_POLICY */ + + connection_set_admin_state(connection, admin_state); + return 0; +} + +int forwarder_remove_connection(const forwarder_t *forwarder, + unsigned connection_id, bool finalize) { + /* Remove connection from the FIB */ + forwarder_remove_connection_id_from_routes(forwarder, connection_id); + + /* Remove connection */ + connection_table_t *table = forwarder_get_connection_table(forwarder); + + /* Hook: connection deleted through the control protocol */ + connection_t *connection = connection_table_at(table, connection_id); + forwarder_on_connection_event(forwarder, connection, CONNECTION_EVENT_DELETE); + + connection_table_remove_by_id(table, connection_id); + if (finalize) connection_finalize(connection); + + return 0; +} + +/* + * This is currently called from commands.c for every command sent to update + * a connection. + */ +void forwarder_on_connection_event(const forwarder_t *forwarder, + const connection_t *connection, + connection_event_t event) { + assert(connection); + + commands_notify_connection(forwarder, event, connection); + + unsigned conn_id = connection_get_id(connection); + + /* We need to send a MapMe update on the newly selected connections for + * each concerned fib_entry : connection is involved, or no more involved */ + fib_t *fib = forwarder_get_fib(forwarder); + fib_foreach_entry(fib, entry, { + const nexthops_t *nexthops = fib_entry_get_nexthops(entry); + + if (!fib_entry_has_local_nexthop(entry)) { + /* Consumer prefix */ + /* + * A new connection has no impact until it is added to FIB, which will + * be handled in a route event + */ + if (event == CONNECTION_EVENT_CREATE) break; + + /* + * For each FIB entry, trigger an event only if the connection is part + * of nexthops */ + // XXX Replace this by a function + nexthops_foreach(nexthops, nexthop, { + if (nexthop != conn_id) continue; + forwarder_on_route_event(forwarder, entry); + break; + }); + } else { + /* Producer prefix */ + if (connection_is_local(connection)) break; + + // XXX we could optimize event more + forwarder_on_route_event(forwarder, entry); + } + }); +} + void forwarder_setup_local_listeners(forwarder_t *forwarder, uint16_t port) { assert(forwarder); listener_setup_local(forwarder, port); @@ -249,7 +406,8 @@ configuration_t *forwarder_get_configuration(forwarder_t *forwarder) { return forwarder->config; } -subscription_table_t *forwarder_get_subscriptions(forwarder_t *forwarder) { +subscription_table_t *forwarder_get_subscriptions( + const forwarder_t *forwarder) { return forwarder->subscriptions; } @@ -259,7 +417,7 @@ connection_table_t *forwarder_get_connection_table( return forwarder->connection_table; } -listener_table_t *forwarder_get_listener_table(forwarder_t *forwarder) { +listener_table_t *forwarder_get_listener_table(const forwarder_t *forwarder) { assert(forwarder); return forwarder->listener_table; } @@ -295,7 +453,8 @@ void forwarder_cs_set_size(forwarder_t *forwarder, size_t size) { if (pkt_cache_set_cs_size(forwarder->pkt_cache, size) < 0) { ERROR( "Unable to resize the CS: provided maximum size (%u) is smaller than " - "the number of elements currently stored in the CS (%u). Clear the CS " + "the number of elements currently stored in the CS (%u). Clear the " + "CS " "and retry.", size, pkt_cache_get_cs_size(forwarder->pkt_cache)); } @@ -335,11 +494,11 @@ static ssize_t forwarder_drop(forwarder_t *forwarder, off_t msgbuf_id) { const msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); switch (msgbuf_get_type(msgbuf)) { - case MSGBUF_TYPE_INTEREST: + case HICN_PACKET_TYPE_INTEREST: forwarder->stats.countInterestsDropped++; break; - case MSGBUF_TYPE_DATA: + case HICN_PACKET_TYPE_DATA: forwarder->stats.countObjectsDropped++; break; @@ -384,7 +543,7 @@ static ssize_t forwarder_forward_via_connection(forwarder_t *forwarder, // Here we need to update the path label of a data packet before send // it. The path label update can be done here because the packet is sent // directly to the socket - if (msgbuf_get_type(msgbuf) == MSGBUF_TYPE_DATA) + if (msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_DATA) msgbuf_update_pathlabel(msgbuf, connection_get_id(conn)); bool success = connection_send_packet(conn, msgbuf_get_packet(msgbuf), @@ -415,11 +574,11 @@ static ssize_t forwarder_forward_via_connection(forwarder_t *forwarder, } switch (msgbuf_get_type(msgbuf)) { - case MSGBUF_TYPE_INTEREST: + case HICN_PACKET_TYPE_INTEREST: forwarder->stats.countInterestForwarded++; break; - case MSGBUF_TYPE_DATA: + case HICN_PACKET_TYPE_DATA: forwarder->stats.countObjectsForwarded++; break; @@ -451,7 +610,6 @@ static unsigned forwarder_forward_to_nexthops(forwarder_t *forwarder, msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); unsigned ingressId = msgbuf_get_connection_id(msgbuf); - unsigned nexthop; nexthops_foreach(nexthops, nexthop, { // DEBUG("[forwarder_forward_to_nexthops] - nexthop = %d"); if (nexthop == ingressId) continue; @@ -469,43 +627,57 @@ static bool forwarder_forward_via_fib(forwarder_t *forwarder, off_t msgbuf_id, pkt_cache_entry_t *entry) { assert(forwarder && entry && msgbuf_id_is_valid(msgbuf_id)); + bool ret = true; + const msgbuf_pool_t *msgbuf_pool = forwarder_get_msgbuf_pool(forwarder); msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); - assert(msgbuf_get_type(msgbuf) == MSGBUF_TYPE_INTEREST); + assert(msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_INTEREST); - fib_entry_t *fib_entry = fib_match_message(forwarder->fib, msgbuf); + fib_entry_t *fib_entry = fib_match_msgbuf(forwarder->fib, msgbuf); if (!fib_entry) return false; - // DEBUG("[forwarder] Getting nexthops from strategy"); - nexthops_t *nexthops = fib_entry_get_nexthops_from_strategy( - fib_entry, msgbuf, verdict == PKT_CACHE_VERDICT_RETRANSMIT_INTEREST); + nexthops_t *nexthops = fib_entry_get_nexthops(fib_entry); + + /* Backup flags and cur_len*/ + uint_fast32_t flags = nexthops->flags; + size_t cur_len = nexthops_get_curlen(nexthops); + + /* This affects the nexthops */ + nexthops = strategy_lookup_nexthops(&fib_entry->strategy, nexthops, msgbuf); if (nexthops_get_curlen(nexthops) == 0) { ERROR("Message %p returned an empty next hop set", msgbuf); - return false; + ret = false; + goto END; } pit_entry_t *pit_entry = &entry->u.pit_entry; - if (!pit_entry) return false; + if (!pit_entry) { + ret = false; + goto END; + } pit_entry_set_fib_entry(pit_entry, fib_entry); // this requires some additional checks. It may happen that some of the output // faces selected by the forwarding strategy are not usable. So far all the // forwarding strategy return only valid faces (or an empty list) - unsigned nexthop; nexthops_foreach(nexthops, nexthop, { // DEBUG("Adding egress to PIT for nexthop %d", nexthop); pit_entry_egress_add(pit_entry, nexthop); }); if (forwarder_forward_to_nexthops(forwarder, msgbuf_id, nexthops) <= 0) { - // this should never happen - ERROR("Message %p returned an empty next hop set", msgbuf); - return false; + ERROR("Error forwarding mMessage %p to next hops", msgbuf); + ret = false; } - return true; +END: + /* Restore flags & curlen */ + nexthops->flags = flags; + nexthops->cur_elts = cur_len; + + return ret; } #endif /* ! BYPASS_FIB */ @@ -519,7 +691,7 @@ int _forwarder_forward_upon_interest( // - Aggregation can be perfomed, do not forward if (verdict == PKT_CACHE_VERDICT_AGGREGATE_INTEREST) { forwarder_drop(forwarder, interest_msgbuf_id); - return msgbuf_get_len(msgbuf); + return (int)msgbuf_get_len(msgbuf); } // - Data packet matching the interest was found, forward reply @@ -532,12 +704,12 @@ int _forwarder_forward_upon_interest( msgbuf_reset_pathlabel(data_msgbuf); forwarder_forward_via_connection(forwarder, data_msgbuf_id, msgbuf_get_connection_id(interest_msgbuf)); - return msgbuf_get_len(msgbuf); + return (int)msgbuf_get_len(msgbuf); } // - For aggregated interest, the interest forwarding is done in // `_forwarder_forward_aggregated_interest()` - if (is_aggregated) return msgbuf_get_len(msgbuf); + if (is_aggregated) return (int)msgbuf_get_len(msgbuf); // - Try to forward the interest int rc = @@ -552,7 +724,7 @@ int _forwarder_forward_upon_interest( return -1; } - return msgbuf_get_len(msgbuf); + return (int)msgbuf_get_len(msgbuf); } static void _forwarder_update_interest_stats(forwarder_t *forwarder, @@ -601,54 +773,60 @@ static void _forwarder_update_interest_stats(forwarder_t *forwarder, } } +/** + * Return the interest manifest from the interest payload + */ static interest_manifest_header_t *_forwarder_get_interest_manifest( msgbuf_t *msgbuf) { - uint8_t *packet = msgbuf_get_packet(msgbuf); - hicn_header_t *header = (hicn_header_t *)packet; - hicn_type_t type = hicn_header_to_type(header); + uint8_t *payload; + size_t payload_size; - hicn_payload_type_t payload_type; - int rc = hicn_ops_vft[type.l1]->get_payload_type(type, &header->protocol, - &payload_type); - _ASSERT(rc == HICN_LIB_ERROR_NONE); - if (payload_type != HPT_MANIFEST) return NULL; + hicn_packet_buffer_t *pkbuf = msgbuf_get_pkbuf(msgbuf); - size_t header_length, payload_length; - rc = hicn_ops_vft[type.l1]->get_header_length(type, &header->protocol, - &header_length); + hicn_payload_type_t payload_type; + HICN_UNUSED(int rc) = hicn_packet_get_payload_type(pkbuf, &payload_type); assert(rc == HICN_LIB_ERROR_NONE); - rc = hicn_ops_vft[type.l1]->get_payload_length(type, &header->protocol, - &payload_length); - assert(rc == HICN_LIB_ERROR_NONE); + if (payload_type != HPT_MANIFEST) return NULL; - u8 *payload = (u8 *)header + header_length; - interest_manifest_header_t *int_manifest_header = - (interest_manifest_header_t *)payload; - if (!interest_manifest_is_valid(int_manifest_header, payload_length)) - return NULL; + rc = hicn_packet_get_payload(pkbuf, &payload, &payload_size, false); + _ASSERT(rc == HICN_LIB_ERROR_NONE); - return int_manifest_header; + return (interest_manifest_header_t *)payload; } // Manifest is split using splitting strategy, then every // sub-manifest is sent using the forwarding strategy defined for the prefix int _forwarder_forward_aggregated_interest( forwarder_t *forwarder, interest_manifest_header_t *int_manifest_header, - int n_suffixes_to_fwd, msgbuf_t *msgbuf, off_t msgbuf_id, - pkt_cache_entry_t **entries) { + msgbuf_t *msgbuf, off_t msgbuf_id, pkt_cache_entry_t **entries) { assert(msgbuf_id_is_valid(msgbuf_id) && - msgbuf_get_type(msgbuf) == MSGBUF_TYPE_INTEREST); + msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_INTEREST); - fib_entry_t *fib_entry = fib_match_message(forwarder->fib, msgbuf); - if (!fib_entry) return -1; + bool ret = -1; + + fib_entry_t *fib_entry = fib_match_msgbuf(forwarder->fib, msgbuf); + if (!fib_entry) goto END; + + nexthops_t *nexthops = fib_entry_get_nexthops(fib_entry); + if (nexthops_get_curlen(nexthops) == 0) { + ret = 0; + goto END; + } - int n_suffixes_per_split = N_SUFFIXES_PER_SPIT; + /* Backup flags and cur_len*/ + uint_fast32_t flags = nexthops->flags; + size_t cur_len = nexthops_get_curlen(nexthops); + + size_t n_suffixes_per_split = configuration_get_suffixes_per_split( + forwarder_get_configuration(forwarder)); + int_manifest_split_strategy_t disaggregation_strategy = + configuration_get_split_strategy(forwarder_get_configuration(forwarder)); switch (disaggregation_strategy) { - case INT_MANIFEST_SPLIT_NONE: + case INT_MANIFEST_SPLIT_STRATEGY_NONE: n_suffixes_per_split = int_manifest_header->n_suffixes + 1; - case INT_MANIFEST_SPLIT_MAX_N_SUFFIXES: { + case INT_MANIFEST_SPLIT_STRATEGY_MAX_N_SUFFIXES: { // Generate sub-manifests: same as original manifest, // but different suffix in the header and different bitmap @@ -658,11 +836,11 @@ int _forwarder_forward_aggregated_interest( // Save copy of original bitmap to use as a reference // to generate bitmaps for sub-manifests - u32 original_bitmap[BITMAP_SIZE] = {0}; + hicn_uword original_bitmap[BITMAP_SIZE] = {0}; memcpy(&original_bitmap, int_manifest_header->request_bitmap, - BITMAP_SIZE * sizeof(u32)); + BITMAP_SIZE * sizeof(hicn_uword)); - int suffix_index = 0; // Position of suffix in initial manifest + size_t suffix_index = 0; // Position of suffix in initial manifest while (suffix_index < total_suffixes) { // If more than one sub-manifest, // clone original interest manifest and update suffix @@ -677,38 +855,48 @@ int _forwarder_forward_aggregated_interest( msgbuf = clone; } - u32 curr_bitmap[BITMAP_SIZE] = {0}; - int first_suffix_index_in_submanifest = suffix_index; + hicn_uword curr_bitmap[BITMAP_SIZE] = {0}; + size_t first_suffix_index_in_submanifest = suffix_index; suffix_index = interest_manifest_update_bitmap( original_bitmap, curr_bitmap, suffix_index, total_suffixes, n_suffixes_per_split); - int first_suffix_index_in_next_submanifest = suffix_index; + size_t first_suffix_index_in_next_submanifest = suffix_index; // Update manifest bitmap in current msgbuf interest_manifest_header_t *manifest = _forwarder_get_interest_manifest(msgbuf); assert(manifest != NULL); memcpy(manifest->request_bitmap, curr_bitmap, - BITMAP_SIZE * sizeof(u32)); + BITMAP_SIZE * sizeof(hicn_uword)); WITH_TRACE({ bitmap_print(manifest->request_bitmap, BITMAP_SIZE); printf("\n"); }); - // Update PIT entries for suffixes in current sub-manifest - nexthops_t *nexthops = - fib_entry_get_nexthops_from_strategy(fib_entry, msgbuf, false); - if (nexthops_get_curlen(nexthops) == 0) return -1; + /* + * Update PIT entries for suffixes in current sub-manifest. + * + * Note that strategy lookup affects the nexthops, and we need to + *restore the initial state before every lookup + */ + nexthops->flags = flags; + nexthops->cur_elts = cur_len; + nexthops = + strategy_lookup_nexthops(&fib_entry->strategy, nexthops, msgbuf); + + if (nexthops_get_curlen(nexthops) == 0) { + ERROR("Message %p returned an empty next hop set", msgbuf); + goto RESTORE; + } - for (int i = first_suffix_index_in_submanifest; + for (size_t i = first_suffix_index_in_submanifest; i < first_suffix_index_in_next_submanifest; i++) { - if (!is_bit_set(manifest->request_bitmap, i)) continue; + if (!bitmap_is_set_no_check(manifest->request_bitmap, i)) continue; pit_entry_t *pit_entry = &(entries[i]->u.pit_entry); - if (!pit_entry) return -1; + if (!pit_entry) goto RESTORE; pit_entry_set_fib_entry(pit_entry, fib_entry); - unsigned nexthop; nexthops_foreach(nexthops, nexthop, { pit_entry_egress_add(pit_entry, nexthop); }); } @@ -722,12 +910,21 @@ int _forwarder_forward_aggregated_interest( total_len += msgbuf_get_len(msgbuf); } - return total_len; + ret = total_len; + goto END; } default: - return -1; + break; } + +RESTORE: + /* Restore flags & curlen */ + nexthops->flags = flags; + nexthops->cur_elts = cur_len; + +END: + return ret; } static ssize_t forwarder_process_single_interest(forwarder_t *forwarder, @@ -742,6 +939,7 @@ static ssize_t forwarder_process_single_interest(forwarder_t *forwarder, pkt_cache_on_interest(forwarder->pkt_cache, msgbuf_pool, msgbuf_id, &verdict, &data_msgbuf_id, &entry, msgbuf_get_name(msgbuf), forwarder->serve_from_cs); + _forwarder_update_interest_stats(forwarder, verdict, msgbuf, entry->has_expire_ts, entry->expire_ts); @@ -749,9 +947,7 @@ static ssize_t forwarder_process_single_interest(forwarder_t *forwarder, forwarder, msgbuf_pool, data_msgbuf_id, msgbuf_id, entry, verdict, false); // No route when trying to forward interest, remove from PIT - if (rc == -1) - pkt_cache_pit_remove_entry(forwarder->pkt_cache, entry, - msgbuf_get_name(msgbuf)); + if (rc == -1) pkt_cache_pit_remove_entry(forwarder->pkt_cache, entry); return msgbuf_get_len(msgbuf); } @@ -769,15 +965,16 @@ static ssize_t forwarder_process_aggregated_interest( int pos = 0; // Position of current suffix in manifest int n_suffixes_to_fwd = 0; u32 *suffix = (u32 *)(int_manifest_header + 1); - u32 seq = name_GetSegment(msgbuf_get_name(msgbuf)); + u32 seq = hicn_name_get_suffix(msgbuf_get_name(msgbuf)); - Name name_copy = EMPTY_NAME; - name_Copy(msgbuf_get_name(msgbuf), &name_copy); + hicn_name_t name_copy = HICN_NAME_EMPTY; + hicn_name_copy(&name_copy, msgbuf_get_name(msgbuf)); // The fist loop iteration handles the suffix in the header, // the following ones handle the suffiexes in the manifest while (true) { - if (!is_bit_set(int_manifest_header->request_bitmap, pos)) goto NEXT_SUFFIX; + if (!bitmap_is_set_no_check(int_manifest_header->request_bitmap, pos)) + goto NEXT_SUFFIX; // Update packet cache pkt_cache_on_interest(forwarder->pkt_cache, msgbuf_pool, msgbuf_id, @@ -794,14 +991,13 @@ static ssize_t forwarder_process_aggregated_interest( msgbuf_id, entry, verdict, true); // No route when trying to forward interest, remove from PIT - if (rc == -1) - pkt_cache_pit_remove_entry(forwarder->pkt_cache, entry, &name_copy); + if (rc == -1) pkt_cache_pit_remove_entry(forwarder->pkt_cache, entry); // Unset in bitmap if no interest forwarding needed, // otherwise increase count of suffixes to forward if (rc == -1 || verdict == PKT_CACHE_VERDICT_AGGREGATE_INTEREST || verdict == PKT_CACHE_VERDICT_FORWARD_DATA) { - unset_bit(int_manifest_header->request_bitmap, pos); + bitmap_unset_no_check(int_manifest_header->request_bitmap, pos); } else { n_suffixes_to_fwd++; } @@ -812,12 +1008,15 @@ static ssize_t forwarder_process_aggregated_interest( // Use next segment in manifest seq = *suffix; suffix++; - name_SetSegment(&name_copy, seq); + hicn_name_set_suffix(&name_copy, seq); WITH_DEBUG({ - char *nameString = name_ToString(&name_copy); - DEBUG("Next in manifest: %s", nameString); - free(nameString); + char buf[MAXSZ_HICN_PREFIX]; + int rc = + hicn_name_snprintf(buf, MAXSZ_HICN_NAME, msgbuf_get_name(msgbuf)); + if (rc < 0 || rc >= MAXSZ_HICN_PREFIX) + snprintf(buf, MAXSZ_HICN_PREFIX, "(error)"); + DEBUG("Next in manifest: %s", buf); }); } @@ -825,8 +1024,7 @@ static ssize_t forwarder_process_aggregated_interest( if (n_suffixes_to_fwd == 0) return msgbuf_get_len(msgbuf); return _forwarder_forward_aggregated_interest(forwarder, int_manifest_header, - n_suffixes_to_fwd, msgbuf, - msgbuf_id, entries); + msgbuf, msgbuf_id, entries); } /** @@ -850,7 +1048,7 @@ static ssize_t forwarder_process_interest(forwarder_t *forwarder, connection_t *conn = connection_table_get_by_id(table, msgbuf_get_connection_id(msgbuf)); - assert(msgbuf_get_type(msgbuf) == MSGBUF_TYPE_INTEREST); + assert(msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_INTEREST); u32 n_suffixes = 0; interest_manifest_header_t *int_manifest_header = @@ -863,16 +1061,20 @@ static ssize_t forwarder_process_interest(forwarder_t *forwarder, conn->stats.interests.rx_bytes += msgbuf_get_len(msgbuf); WITH_DEBUG({ - char *nameString = name_ToString(msgbuf_get_name(msgbuf)); - DEBUG("INTEREST (%s) suffixes=%u msgbuf_id=%lu ingress=%u length=%u", - nameString, n_suffixes, msgbuf_id, msgbuf_get_connection_id(msgbuf), + char buf[MAXSZ_HICN_PREFIX]; + int rc = hicn_name_snprintf(buf, MAXSZ_HICN_NAME, msgbuf_get_name(msgbuf)); + if (rc < 0 || rc >= MAXSZ_HICN_PREFIX) + snprintf(buf, MAXSZ_HICN_PREFIX, "(error)"); + DEBUG("INTEREST (%s) msgbuf_id=%lu ingress=%u length=%u", buf, msgbuf_id, + msgbuf_get_connection_id(msgbuf), msgbuf_get_len(msgbuf)); + DEBUG("INTEREST (%s) suffixes=%u msgbuf_id=%lu ingress=%u length=%u", buf, + n_suffixes, msgbuf_id, msgbuf_get_connection_id(msgbuf), msgbuf_get_len(msgbuf)); - free(nameString); }); // Cache suffixes for current prefix to (possibly) avoid double lookups pkt_cache_save_suffixes_for_prefix( - forwarder->pkt_cache, name_GetContentName(msgbuf_get_name(msgbuf))); + forwarder->pkt_cache, hicn_name_get_prefix(msgbuf_get_name(msgbuf))); if (!int_manifest_header) return forwarder_process_single_interest(forwarder, msgbuf_pool, msgbuf, @@ -888,7 +1090,9 @@ static void _forwarder_log_on_data(forwarder_t *forwarder, DEBUG("Message added to CS from PIT"); break; case PKT_CACHE_VERDICT_STORE_DATA: - DEBUG("Message added to CS (expired or no previous interest pending)"); + DEBUG( + "Message added to CS (expired or no previous interest " + "pending)"); break; case PKT_CACHE_VERDICT_CLEAR_DATA: break; @@ -921,10 +1125,12 @@ static ssize_t forwarder_process_data(forwarder_t *forwarder, off_t msgbuf_id) { msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); WITH_DEBUG({ - char *nameString = name_ToString(msgbuf_get_name(msgbuf)); - DEBUG("DATA (%s) msgbuf_id=%lu ingress=%u length=%u", nameString, msgbuf_id, + char buf[MAXSZ_HICN_PREFIX]; + int rc = hicn_name_snprintf(buf, MAXSZ_HICN_NAME, msgbuf_get_name(msgbuf)); + if (rc < 0 || rc >= MAXSZ_HICN_PREFIX) + snprintf(buf, MAXSZ_HICN_PREFIX, "(error)"); + DEBUG("DATA (%s) msgbuf_id=%lu ingress=%u length=%u", buf, msgbuf_id, msgbuf_get_connection_id(msgbuf), msgbuf_get_len(msgbuf)); - free(nameString); }); const connection_table_t *table = forwarder_get_connection_table(forwarder); @@ -938,7 +1144,7 @@ static ssize_t forwarder_process_data(forwarder_t *forwarder, off_t msgbuf_id) { // Cache suffixes for current prefix to (possibly) avoid double lookups pkt_cache_save_suffixes_for_prefix( - forwarder->pkt_cache, name_GetContentName(msgbuf_get_name(msgbuf))); + forwarder->pkt_cache, hicn_name_get_prefix(msgbuf_get_name(msgbuf))); pkt_cache_verdict_t verdict = PKT_CACHE_VERDICT_ERROR; bool wrong_egress; @@ -955,17 +1161,13 @@ static ssize_t forwarder_process_data(forwarder_t *forwarder, off_t msgbuf_id) { forwarder->stats.countDroppedNoReversePath++; DEBUG("Message %lu did not match PIT, no reverse path", msgbuf_id); - // MOVE PROBE HOOK ELSEWHERE - // XXX relationship with forwarding strategy... insert hooks - // if the packet is a probe we need to analyze it // NOTE : probes are not stored in PIT if (msgbuf_is_probe(msgbuf)) { - fib_entry_t *entry = fib_match_message(forwarder->fib, msgbuf); + fib_entry_t *entry = fib_match_msgbuf(forwarder->fib, msgbuf); if (entry && fib_entry_strategy_type(entry) == STRATEGY_TYPE_BESTPATH) { nexthops_t probe_nexthops = NEXTHOPS_EMPTY; nexthops_add(&probe_nexthops, msgbuf_get_connection_id(msgbuf)); fib_entry_on_data(entry, &probe_nexthops, msgbuf, 0, ticks_now()); - // XXX TODO CONFIRM WE DON'T EXIT HERE ? } } forwarder_drop(forwarder, msgbuf_id); @@ -982,7 +1184,8 @@ void forwarder_flush_connections(forwarder_t *forwarder) { // DEBUG("[forwarder_flush_connections]"); const connection_table_t *table = forwarder_get_connection_table(forwarder); - for (unsigned i = 0; i < vector_len(forwarder->pending_conn); i++) { + unsigned num_pending_conn = (unsigned)vector_len(forwarder->pending_conn); + for (unsigned i = 0; i < num_pending_conn; i++) { unsigned conn_id = forwarder->pending_conn[i]; connection_t *conn = connection_table_at(table, conn_id); if (!connection_flush(conn)) { @@ -994,14 +1197,15 @@ void forwarder_flush_connections(forwarder_t *forwarder) { // DEBUG("[forwarder_flush_connections] done"); } +#if WITH_WLDR // XXX move to wldr file, worst case in connection. void forwarder_apply_wldr(const forwarder_t *forwarder, const msgbuf_t *msgbuf, connection_t *connection) { - // this are the checks needed to implement WLDR. We set wldr only on the STAs - // and we let the AP to react according to choice of the client. - // if the STA enables wldr using the set command, the AP enable wldr as well - // otherwise, if the STA disable it the AP remove wldr - // WLDR should be enabled only on the STAs using the command line + // this are the checks needed to implement WLDR. We set wldr only on the + // STAs and we let the AP to react according to choice of the client. if + // the STA enables wldr using the set command, the AP enable wldr as + // well otherwise, if the STA disable it the AP remove wldr WLDR should + // be enabled only on the STAs using the command line // TODO // disable WLDR command line on the AP if (msgbuf_has_wldr(msgbuf)) { @@ -1023,8 +1227,10 @@ void forwarder_apply_wldr(const forwarder_t *forwarder, const msgbuf_t *msgbuf, } } } +#endif -bool forwarder_add_or_update_route(forwarder_t *forwarder, ip_prefix_t *prefix, +bool forwarder_add_or_update_route(forwarder_t *forwarder, + hicn_ip_prefix_t *prefix, unsigned ingress_id) { assert(forwarder); assert(prefix); @@ -1032,7 +1238,7 @@ bool forwarder_add_or_update_route(forwarder_t *forwarder, ip_prefix_t *prefix, configuration_t *config = forwarder_get_configuration(forwarder); char prefix_s[MAXSZ_IP_PREFIX]; - int rc = ip_prefix_snprintf(prefix_s, MAXSZ_IP_PREFIX, prefix); + int rc = hicn_ip_prefix_snprintf(prefix_s, MAXSZ_IP_PREFIX, prefix); assert(rc < MAXSZ_IP_PREFIX); if (rc < 0) return false; @@ -1041,9 +1247,9 @@ bool forwarder_add_or_update_route(forwarder_t *forwarder, ip_prefix_t *prefix, // XXX TODO this should store options too strategy_type_t strategy_type = configuration_get_strategy(config, prefix_s); - Name name_prefix = EMPTY_NAME; - name_CreateFromAddress(&name_prefix, prefix->family, prefix->address, - prefix->len); + hicn_prefix_t name_prefix = HICN_PREFIX_EMPTY; + hicn_prefix_create_from_ip_address_len(&prefix->address, prefix->len, + &name_prefix); fib_entry_t *entry = fib_contains(forwarder->fib, &name_prefix); if (!entry) { entry = fib_entry_create(&name_prefix, strategy_type, NULL, forwarder); @@ -1054,17 +1260,19 @@ bool forwarder_add_or_update_route(forwarder_t *forwarder, ip_prefix_t *prefix, fib_entry_nexthops_add(entry, ingress_id); } + forwarder_on_route_event(forwarder, entry); + return true; } -bool forwarder_remove_route(forwarder_t *forwarder, ip_prefix_t *prefix, +bool forwarder_remove_route(forwarder_t *forwarder, hicn_ip_prefix_t *prefix, unsigned ingress_id) { assert(forwarder); assert(prefix); - Name name_prefix = EMPTY_NAME; - name_CreateFromAddress(&name_prefix, prefix->family, prefix->address, - prefix->len); + hicn_prefix_t name_prefix = HICN_PREFIX_EMPTY; + hicn_prefix_create_from_ip_address_len(&prefix->address, prefix->len, + &name_prefix); fib_remove(forwarder->fib, &name_prefix, ingress_id); return true; @@ -1072,31 +1280,32 @@ bool forwarder_remove_route(forwarder_t *forwarder, ip_prefix_t *prefix, #ifdef WITH_POLICY -bool forwarder_add_or_update_policy(forwarder_t *forwarder, ip_prefix_t *prefix, +bool forwarder_add_or_update_policy(forwarder_t *forwarder, + hicn_ip_prefix_t *prefix, hicn_policy_t *policy) { assert(forwarder); assert(prefix); assert(policy); - Name name_prefix = EMPTY_NAME; - name_CreateFromAddress(&name_prefix, prefix->family, prefix->address, - prefix->len); + hicn_prefix_t name_prefix = HICN_PREFIX_EMPTY; + hicn_prefix_create_from_ip_address_len(&prefix->address, prefix->len, + &name_prefix); fib_entry_t *entry = fib_contains(forwarder->fib, &name_prefix); if (!entry) return false; + fib_entry_set_policy(entry, *policy); return true; } -bool forwarder_remove_policy(forwarder_t *forwarder, ip_prefix_t *prefix) { +bool forwarder_remove_policy(forwarder_t *forwarder, hicn_ip_prefix_t *prefix) { assert(forwarder); assert(prefix); - Name name_prefix = EMPTY_NAME; - name_CreateFromAddress(&name_prefix, prefix->family, prefix->address, - prefix->len); + hicn_prefix_t name_prefix = HICN_PREFIX_EMPTY; + hicn_prefix_create_from_ip_address_len(&prefix->address, prefix->len, + &name_prefix); fib_entry_t *entry = fib_contains(forwarder->fib, &name_prefix); - if (!entry) return false; fib_entry_set_policy(entry, POLICY_EMPTY); @@ -1106,14 +1315,30 @@ bool forwarder_remove_policy(forwarder_t *forwarder, ip_prefix_t *prefix) { #endif /* WITH_POLICY */ -void forwarder_remove_connection_id_from_routes(forwarder_t *forwarder, +void forwarder_remove_connection_id_from_routes(const forwarder_t *forwarder, unsigned connection_id) { + fib_entry_t **removed_entries = NULL; + size_t num_removed_entries; + assert(forwarder); - fib_remove_connection_id(forwarder->fib, connection_id); + fib_remove_connection(forwarder->fib, connection_id, &removed_entries, + &num_removed_entries); + + if (num_removed_entries > 0) { + assert(removed_entries); + + for (int i = 0; i < num_removed_entries; i++) { + fib_entry_t *entry = removed_entries[i]; + forwarder_on_route_event(forwarder, entry); + fib_remove_entry(forwarder->fib, entry); + } + free(removed_entries); + } } -void forwarder_add_strategy_options(forwarder_t *forwarder, Name *name_prefix, +void forwarder_add_strategy_options(forwarder_t *forwarder, + hicn_prefix_t *name_prefix, strategy_type_t strategy_type, strategy_options_t *strategy_options) { assert(forwarder); @@ -1127,18 +1352,18 @@ void forwarder_add_strategy_options(forwarder_t *forwarder, Name *name_prefix, fib_entry_add_strategy_options(entry, strategy_type, strategy_options); } -void forwarder_set_strategy(forwarder_t *forwarder, Name *name_prefix, +void forwarder_set_strategy(forwarder_t *forwarder, hicn_prefix_t *prefix, strategy_type_t strategy_type, strategy_options_t *strategy_options) { assert(forwarder); - assert(name_prefix); + assert(prefix); assert(STRATEGY_TYPE_VALID(strategy_type)); /* strategy_options might be NULL */ - fib_entry_t *entry = fib_contains(forwarder->fib, name_prefix); + fib_entry_t *entry = fib_contains(forwarder->fib, prefix); if (!entry) { - // there is no exact match. so if the forwarding strategy is not in the list - // of strategies that can be set by the transport, return + // there is no exact match. so if the forwarding strategy is not in + // the list of strategies that can be set by the transport, return if (strategy_type != STRATEGY_TYPE_BESTPATH && strategy_type != STRATEGY_TYPE_REPLICATION) { return; @@ -1148,7 +1373,7 @@ void forwarder_set_strategy(forwarder_t *forwarder, Name *name_prefix, // no knowledge of the length of the prefix. so we apply the strategy at the // matching fib entry, which later will be the one that will be used to send // interests with this name - entry = fib_match_name(forwarder->fib, name_prefix); + entry = fib_match_prefix(forwarder->fib, prefix); if (!entry) { return; // no fib match, return } @@ -1163,10 +1388,11 @@ cs_t *forwarder_get_cs(const forwarder_t *forwarder) { return pkt_cache_get_cs(forwarder->pkt_cache); } -// IMPORTANT: Use this function ONLY for read-only operations since a realloc -// would otherwise modify the returned copy but not the original msgbuf ids -// vector in the forwarder. This constraint cannot be enforced by returning a -// (const off_t *) because the vector_t macros still cast to (void **). +// IMPORTANT: Use this function ONLY for read-only operations since a +// realloc would otherwise modify the returned copy but not the original +// msgbuf ids vector in the forwarder. This constraint cannot be enforced +// by returning a (const off_t *) because the vector_t macros still cast +// to (void **). off_t *forwarder_get_acquired_msgbuf_ids(const forwarder_t *forwarder) { return forwarder->acquired_msgbuf_ids; } @@ -1182,25 +1408,18 @@ void forwarder_acquired_msgbuf_ids_push(const forwarder_t *forwarder, // ======================================================= -fib_t *forwarder_get_fib(forwarder_t *forwarder) { return forwarder->fib; } +fib_t *forwarder_get_fib(const forwarder_t *forwarder) { + return forwarder->fib; +} msgbuf_pool_t *forwarder_get_msgbuf_pool(const forwarder_t *forwarder) { return forwarder->msgbuf_pool; } -#ifdef WITH_MAPME -void forwarder_on_connection_event(const forwarder_t *forwarder, - const connection_t *connection, - connection_event_t event) { - mapme_on_connection_event(forwarder->mapme, connection, event); -} - mapme_t *forwarder_get_mapme(const forwarder_t *forwarder) { return forwarder->mapme; } -#endif /* WITH_MAPME */ - #ifdef WITH_POLICY_STATS const policy_stats_mgr_t *forwarder_get_policy_stats_mgr( const forwarder_t *forwarder) { @@ -1209,39 +1428,6 @@ const policy_stats_mgr_t *forwarder_get_policy_stats_mgr( #endif /* WITH_POLICY_STATS */ /** - * @brief Process a packet by creating the corresponding message buffer and - * dispatching it to the forwarder for further processing. - * @param[in] forwarder Forwarder instance. - * - */ -// XXX ??? XXX = process for listener as we are resolving connection id -// - -msgbuf_type_t get_type_from_packet(uint8_t *packet) { - if (messageHandler_IsTCP(packet)) { - if (messageHandler_IsData(packet)) { - return MSGBUF_TYPE_DATA; - } else if (messageHandler_IsInterest(packet)) { - return MSGBUF_TYPE_INTEREST; - } else { - return MSGBUF_TYPE_UNDEFINED; - } - - } else if (messageHandler_IsWldrNotification(packet)) { - return MSGBUF_TYPE_WLDR_NOTIFICATION; - - } else if (mapme_match_packet(packet)) { - return MSGBUF_TYPE_MAPME; - - } else if (*packet == REQUEST_LIGHT) { - return MSGBUF_TYPE_COMMAND; - - } else { - return MSGBUF_TYPE_UNDEFINED; - } -} - -/** * @brief Finalize (i.e. close fd and free internal data structures) * the current connection ("SELF") when the command is received. * The connection cannot be removed inside the command handling @@ -1268,7 +1454,6 @@ ssize_t forwarder_receive(forwarder_t *forwarder, listener_t *listener, msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); assert(msgbuf); - uint8_t *packet = msgbuf_get_packet(msgbuf); size_t size = msgbuf_get_len(msgbuf); /* Connection lookup */ @@ -1281,81 +1466,128 @@ ssize_t forwarder_receive(forwarder_t *forwarder, listener_t *listener, assert((conn_id != CONNECTION_ID_UNDEFINED) || listener); +#if 0 + /* + * We have a msgbuf with payload and size, we nee to populate other + * information, including packet type etc. + */ msgbuf_type_t type = get_type_from_packet(msgbuf_get_packet(msgbuf)); forwarder->stats.countReceived++; msgbuf->type = type; +#endif + /* Initialize packet buffer stored in msgbuf through libhicn */ + msgbuf_initialize_from_packet(msgbuf); + hicn_packet_analyze(msgbuf_get_pkbuf(msgbuf)); + msgbuf->connection_id = conn_id; msgbuf->recv_ts = now; - switch (type) { - case MSGBUF_TYPE_INTEREST: + hicn_name_t name; + +RETRY: + + switch (msgbuf_get_type(msgbuf)) { + case HICN_PACKET_TYPE_INTEREST: if (!connection_id_is_valid(msgbuf->connection_id)) { char conn_name[SYMBOLIC_NAME_LEN]; int rc = connection_table_get_random_name(table, conn_name); - if (rc < 0) return 0; + if (rc < 0) { + ERROR("Could not create name for new connection"); + goto DROP; + } unsigned connection_id = listener_create_connection(listener, conn_name, pair); + if (connection_id == CONNECTION_ID_UNDEFINED) { + ERROR("Could not create new connection"); + goto DROP; + } msgbuf->connection_id = connection_id; connection = connection_table_get_by_id(table, connection_id); } msgbuf->path_label = 0; // not used for interest packets - name_create_from_interest(packet, msgbuf_get_name(msgbuf)); + hicn_interest_get_name(msgbuf_get_pkbuf(msgbuf), &name); + msgbuf_set_name(msgbuf, &name); +#ifdef WITH_WLDR forwarder_apply_wldr(forwarder, msgbuf, connection); +#endif /* WITH_WLDR */ forwarder_process_interest(forwarder, msgbuf_id); pkt_cache_log(forwarder->pkt_cache); - return size; + break; - case MSGBUF_TYPE_DATA: - if (!connection_id_is_valid(msgbuf->connection_id)) - return forwarder_drop(forwarder, msgbuf_id); + case HICN_PACKET_TYPE_DATA: + /* This include probes */ + if (!connection_id_is_valid(msgbuf->connection_id)) { + ERROR("Invalid connection for data packet"); + goto DROP; + } msgbuf_init_pathlabel(msgbuf); - name_create_from_data(packet, msgbuf_get_name(msgbuf)); + hicn_data_get_name(msgbuf_get_pkbuf(msgbuf), &name); + msgbuf_set_name(msgbuf, &name); +#ifdef WITH_WLDR forwarder_apply_wldr(forwarder, msgbuf, connection); +#endif /* WITH_WLDR */ forwarder_process_data(forwarder, msgbuf_id); pkt_cache_log(forwarder->pkt_cache); - return size; + break; - case MSGBUF_TYPE_WLDR_NOTIFICATION: - if (!connection_id_is_valid(msgbuf->connection_id)) - return forwarder_drop(forwarder, msgbuf_id); + case HICN_PACKET_TYPE_WLDR_NOTIFICATION: + if (!connection_id_is_valid(msgbuf->connection_id)) { + ERROR("Invalid connection for WLDR packet"); + goto DROP; + } connection_wldr_handle_notification(connection, msgbuf); - return size; + break; - case MSGBUF_TYPE_MAPME: + case HICN_PACKET_TYPE_MAPME: // XXX what about acks ? if (!connection_id_is_valid(msgbuf->connection_id)) { char conn_name[SYMBOLIC_NAME_LEN]; int rc = connection_table_get_random_name(table, conn_name); - if (rc < 0) return 0; + if (rc < 0) { + ERROR("Could not create name for new connection"); + goto DROP; + } - msgbuf->connection_id = + unsigned connection_id = listener_create_connection(listener, conn_name, pair); + if (connection_id == CONNECTION_ID_UNDEFINED) { + ERROR("Could not create new connection"); + goto DROP; + } + msgbuf->connection_id = connection_id; } mapme_process(forwarder->mapme, msgbuf); - return size; + break; - case MSGBUF_TYPE_COMMAND: + case HICN_PACKET_TYPE_COMMAND: // Create the connection to send the ack back if (!connection_id_is_valid(msgbuf->connection_id)) { char conn_name[SYMBOLIC_NAME_LEN]; int rc = connection_table_get_random_name(table, conn_name); - if (rc < 0) return 0; + if (rc < 0) { + ERROR("Could not create name for new connection"); + goto DROP; + } unsigned connection_id = listener_create_connection(listener, conn_name, pair); + if (connection_id == CONNECTION_ID_UNDEFINED) { + ERROR("Could not create new connection"); + goto DROP; + } msgbuf->connection_id = connection_id; connection = connection_table_get_by_id(table, connection_id); } - msg_header_t *msg = (msg_header_t *)packet; + msg_header_t *msg = (msg_header_t *)msgbuf_get_packet(msgbuf); msgbuf->command.type = msg->header.command_id; if (!command_type_is_valid(msgbuf->command.type)) { - ERROR("Invalid command"); - return 0; + ERROR("Invalid command %d", msgbuf->command.type); + goto DROP; } size = command_process_msgbuf(forwarder, msgbuf); @@ -1364,19 +1596,32 @@ ssize_t forwarder_receive(forwarder_t *forwarder, listener_t *listener, return size; default: - ERROR("Invalid msgbuf type"); - forwarder_drop(forwarder, msgbuf_id); - return 0; + /* Commands are not recognized by the packet parser */ + if (msgbuf_is_command(msgbuf)) { + msgbuf_set_type(msgbuf, HICN_PACKET_TYPE_COMMAND); + goto RETRY; + } + goto DROP; } + + return size; + +DROP: + forwarder_drop(forwarder, msgbuf_id); + return 0; } void forwarder_log(forwarder_t *forwarder) { DEBUG( "Forwarder: received = %u (interest = %u, data = %u), dropped = %u " - "(interest = %u, data = %u, other = %u), forwarded = { interests = %u, " - "data = %u }, dropped = { connection_not_found = %u, send_failure = %u, " + "(interest = %u, data = %u, other = %u), forwarded = { interests = " + "%u, " + "data = %u }, dropped = { connection_not_found = %u, send_failure " + "= " + "%u, " "no_route_in_fib = %u }, interest processing = { aggregated = %u, " - "retransmitted = %u, satisfied_from_cs = %u, expired_interests = %u, " + "retransmitted = %u, satisfied_from_cs = %u, expired_interests = " + "%u, " "expired_data = %u }, data processing = { " "no_reverse_path = %u }\n", forwarder->stats.countReceived, forwarder->stats.countInterestsReceived, @@ -1396,4 +1641,4 @@ void forwarder_log(forwarder_t *forwarder) { forwarder_stats_t forwarder_get_stats(forwarder_t *forwarder) { return forwarder->stats; -}
\ No newline at end of file +} diff --git a/hicn-light/src/hicn/core/forwarder.h b/hicn-light/src/hicn/core/forwarder.h index 2f940cf15..b7ce5ff4d 100644 --- a/hicn-light/src/hicn/core/forwarder.h +++ b/hicn-light/src/hicn/core/forwarder.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -74,7 +74,7 @@ void forwarder_setup_local_listeners(forwarder_t *forwarder, uint16_t port); configuration_t *forwarder_get_configuration(forwarder_t *forwarder); -subscription_table_t *forwarder_get_subscriptions(forwarder_t *forwarder); +subscription_table_t *forwarder_get_subscriptions(const forwarder_t *forwarder); /** * Returns the set of currently active listeners @@ -84,7 +84,7 @@ subscription_table_t *forwarder_get_subscriptions(forwarder_t *forwarder); * @retval non-null The set of active listeners * @retval null An error */ -listener_table_t *forwarder_get_listener_table(forwarder_t *forwarder); +listener_table_t *forwarder_get_listener_table(const forwarder_t *forwarder); /** * Returns the forwrder's connection table @@ -122,40 +122,43 @@ void forwarder_cs_clear(forwarder_t *forwarder); /** * @brief Adds or updates a route on all the message processors */ -bool forwarder_add_or_update_route(forwarder_t *forwarder, ip_prefix_t *prefix, +bool forwarder_add_or_update_route(forwarder_t *forwarder, + hicn_ip_prefix_t *prefix, unsigned ingress_id); /** * @brief Removes a route from all the message processors */ -bool forwarder_remove_route(forwarder_t *forwarder, ip_prefix_t *prefix, +bool forwarder_remove_route(forwarder_t *forwarder, hicn_ip_prefix_t *prefix, unsigned ingress_id); #ifdef WITH_POLICY /** * @brief Adds or updates a policy on the message processor */ -bool forwarder_add_or_update_policy(forwarder_t *forwarder, ip_prefix_t *prefix, +bool forwarder_add_or_update_policy(forwarder_t *forwarder, + hicn_ip_prefix_t *prefix, hicn_policy_t *policy); /** * @brief Removes a policy from the message processor */ -bool forwarder_remove_policy(forwarder_t *forwarder, ip_prefix_t *prefix); +bool forwarder_remove_policy(forwarder_t *forwarder, hicn_ip_prefix_t *prefix); #endif /* WITH_POLICY */ /** * Removes a connection id from all routes */ -void forwarder_remove_connection_id_from_routes(forwarder_t *forwarder, +void forwarder_remove_connection_id_from_routes(const forwarder_t *forwarder, unsigned connection_id); -void forwarder_add_strategy_options(forwarder_t *forwarder, Name *name_prefix, +void forwarder_add_strategy_options(forwarder_t *forwarder, + hicn_prefix_t *name_prefix, strategy_type_t strategy_type, strategy_options_t *strategy_options); -void forwarder_set_strategy(forwarder_t *forwarder, Name *name_prefix, +void forwarder_set_strategy(forwarder_t *forwarder, hicn_prefix_t *prefix, strategy_type_t strategy_type, strategy_options_t *strategy_options); @@ -178,7 +181,7 @@ void forwarder_acquired_msgbuf_ids_push(const forwarder_t *forwarder, * @param[in] forwarder - Pointer to the forwarder. * @returns Pointer to the hICN FIB. */ -fib_t *forwarder_get_fib(forwarder_t *forwarder); +fib_t *forwarder_get_fib(const forwarder_t *forwarder); /** * @brief Return the forwarder packet pool. @@ -190,6 +193,16 @@ msgbuf_pool_t *forwarder_get_msgbuf_pool(const forwarder_t *forwarder); #ifdef WITH_MAPME +void forwarder_on_route_event(const forwarder_t *forwarder, fib_entry_t *entry); + +int forwarder_add_connection(const forwarder_t *forwarder, + const char *symbolic_name, face_type_t type, + address_pair_t *pair, policy_tags_t tags, + int priority, face_state_t admin_state); + +int forwarder_remove_connection(const forwarder_t *forwarder, + unsigned connection_id, bool finalize); + /** * @brief Callback fired upon addition of a new connection through the * control protocol. diff --git a/hicn-light/src/hicn/core/interest_manifest.c b/hicn-light/src/hicn/core/interest_manifest.c deleted file mode 100644 index 1be8a3fb5..000000000 --- a/hicn-light/src/hicn/core/interest_manifest.c +++ /dev/null @@ -1,64 +0,0 @@ -/* - * Copyright (c) 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. - */ - -#include "interest_manifest.h" - -int_manifest_split_strategy_t disaggregation_strategy = - INT_MANIFEST_SPLIT_MAX_N_SUFFIXES; -unsigned N_SUFFIXES_PER_SPIT = 256; - -bool interest_manifest_is_valid(interest_manifest_header_t *int_manifest_header, - size_t payload_length) { - if (int_manifest_header->n_suffixes == 0 || - int_manifest_header->n_suffixes > MAX_SUFFIXES_IN_MANIFEST) { - ERROR("Manifest with invalid number of suffixes (%d)", - int_manifest_header->n_suffixes); - return false; - } - - uint32_t empty_bitmap[BITMAP_SIZE] = {0}; - if (memcmp(empty_bitmap, int_manifest_header->request_bitmap, - sizeof(empty_bitmap)) == 0) { - ERROR("Manifest with empty bitmap"); - return false; - } - - if (payload_length - sizeof(interest_manifest_header_t) != - int_manifest_header->n_suffixes * sizeof(u32)) { - ERROR("Size of suffixes in intereset manifest (%d) is not equal to %d", - payload_length - sizeof(interest_manifest_header_t), - int_manifest_header->n_suffixes * sizeof(u32)); - return false; - } - - return true; -} - -int interest_manifest_update_bitmap(const u32 *initial_bitmap, - u32 *bitmap_to_update, int start, int n, - int max_suffixes) { - int i = start, n_ones = 0; - while (i < n) { - if (is_bit_set(initial_bitmap, i)) { - set_bit(bitmap_to_update, i); - n_ones++; - } - i++; - - if (n_ones == max_suffixes) break; - } - - return i; -} diff --git a/hicn-light/src/hicn/core/interest_manifest.h b/hicn-light/src/hicn/core/interest_manifest.h deleted file mode 100644 index fcb2b9897..000000000 --- a/hicn-light/src/hicn/core/interest_manifest.h +++ /dev/null @@ -1,40 +0,0 @@ -/* - * Copyright (c) 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. - */ - -#ifndef HICNLIGHT_INTEREST_MANIFEST_H -#define HICNLIGHT_INTEREST_MANIFEST_H - -#include <string.h> -#include <stdbool.h> - -#include <hicn/util/log.h> -#include <hicn/base.h> - -typedef enum { - INT_MANIFEST_SPLIT_NONE, - INT_MANIFEST_SPLIT_MAX_N_SUFFIXES -} int_manifest_split_strategy_t; - -extern int_manifest_split_strategy_t disaggregation_strategy; -extern unsigned N_SUFFIXES_PER_SPIT; - -bool interest_manifest_is_valid(interest_manifest_header_t *int_manifest_header, - size_t payload_length); - -int interest_manifest_update_bitmap(const u32 *initial_bitmap, - u32 *bitmap_to_update, int start, int n, - int max_suffixes); - -#endif /* HICNLIGHT_INTEREST_MANIFEST_H */ diff --git a/hicn-light/src/hicn/core/listener.c b/hicn-light/src/hicn/core/listener.c index 188f0c317..a3c5c8a12 100644 --- a/hicn-light/src/hicn/core/listener.c +++ b/hicn-light/src/hicn/core/listener.c @@ -247,38 +247,8 @@ unsigned listener_create_connection(listener_t *listener, connection_table_print_by_pair(table); }) -#if 0 - DEBUG("Notification for new connections"); - // Generate notification message - flag_interface_type_t interface_type = - FLAG_INTERFACE_TYPE_WIRED | FLAG_INTERFACE_TYPE_CELLULAR; - struct { - cmd_header_t header; - hc_event_interface_update_t payload; - } msg = {.header = - { - .message_type = NOTIFICATION_LIGHT, - .command_id = EVENT_INTERFACE_UPDATE, - .length = 0, - .seq_num = 0, - }, - .payload = {.interface_type = interface_type}}; - size_t size = sizeof(msg); - - // Retrieve subscribed connections - subscription_table_t *subscriptions = - forwarder_get_subscriptions(listener->forwarder); - unsigned *subscribed_conn_ids = subscription_table_get_connections_for_topic( - subscriptions, TOPIC_CONNECTION); - - // Send notification to subscribed connections - for (int i = 0; i < vector_len(subscribed_conn_ids); i++) { - DEBUG("Sending notification to connection: %u", subscribed_conn_ids[i]); - const connection_t *conn = - connection_table_at(table, subscribed_conn_ids[i]); - connection_send_packet(conn, (uint8_t *)&msg, size); - } -#endif + forwarder_on_connection_event(listener->forwarder, connection, + CONNECTION_EVENT_CREATE); return connection_id; } @@ -441,4 +411,4 @@ void listener_setup_local(forwarder_t *forwarder, uint16_t port) { address_t localhost_ipv6_addr = ADDRESS6_LOCALHOST(port); listener_create(FACE_TYPE_UDP_LISTENER, &localhost_ipv6_addr, "lo", "lo_udp6", forwarder); -}
\ No newline at end of file +} diff --git a/hicn-light/src/hicn/core/listener_table.c b/hicn-light/src/hicn/core/listener_table.c index 220b738bb..c130399a5 100644 --- a/hicn-light/src/hicn/core/listener_table.c +++ b/hicn-light/src/hicn/core/listener_table.c @@ -58,7 +58,7 @@ void listener_table_free(listener_table_t *table) { kh_foreach(table->id_by_key, k_key, v, { listener = listener_table_get_by_id(table, v); name = listener_get_name(listener); - INFO("Removing listner %s [%d]", name, listener->fd); + INFO("Removing listener %s [%d]", name, listener->fd); listener_finalize(listener); }); @@ -199,4 +199,4 @@ void listener_table_print_by_name(const listener_table_t *table) { INFO("%s:%d - %s\t\t\t\t(%u, %s)", addr_str, port, face_type_str(key->type), v, k); }) -}
\ No newline at end of file +} diff --git a/hicn-light/src/hicn/core/listener_table.h b/hicn-light/src/hicn/core/listener_table.h index 7e2e99d7f..27c5daa04 100644 --- a/hicn-light/src/hicn/core/listener_table.h +++ b/hicn-light/src/hicn/core/listener_table.h @@ -161,9 +161,13 @@ listener_t *_listener_table_get_by_id(listener_table_t *table, off_t id); #define listener_table_get_listener_id(table, listener) \ (listener - table->listeners) -#define listener_table_foreach(table, listener, BODY) \ - pool_foreach( \ - table->listeners, listener, do { BODY } while (0)) +#define listener_table_foreach(table, listener, BODY) \ + do { \ + listener_t *listener; \ + (void)listener; \ + pool_foreach( \ + table->listeners, listener, do { BODY } while (0)); \ + } while (0) #define listener_table_enumerate(table, i, conn, BODY) \ pool_enumerate(table->listeners, (i), (conn), BODY) diff --git a/hicn-light/src/hicn/core/mapme.c b/hicn-light/src/hicn/core/mapme.c index dfb30da5c..b151d6cb0 100644 --- a/hicn-light/src/hicn/core/mapme.c +++ b/hicn-light/src/hicn/core/mapme.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -294,15 +294,6 @@ static void mapme_create_tfib(const mapme_t *mapme, fib_entry_t *entry) { fib_entry_set_user_data(entry, tfib, (void (*)(void **))mapme_release_tfib); } -int hicn_prefix_from_name(const Name *name, hicn_prefix_t *prefix) { - NameBitvector *bv = name_GetContentName(name); - ip_prefix_t ip_prefix; - nameBitvector_ToIPAddress(bv, &ip_prefix); - - /* The name length will be equal to ip address' prefix length */ - return hicn_prefix_create_from_ip_prefix(&ip_prefix, prefix); -} - /** * @brief Update/Notification heuristic: * @@ -350,12 +341,14 @@ int mapme_send_to_nexthops(const mapme_t *mapme, fib_entry_t *entry, tfib = TFIB(entry); } - const Name *name = fib_entry_get_prefix(entry); + const hicn_prefix_t *prefix = fib_entry_get_prefix(entry); WITH_DEBUG({ - char *name_str = name_ToString(name); - DEBUG("sending IU/IN for name %s on all nexthops", name_str); - free(name_str); + char buf[MAXSZ_HICN_PREFIX]; + int rc = hicn_prefix_snprintf(buf, MAXSZ_HICN_PREFIX, prefix); + if (rc < 0 || rc >= MAXSZ_HICN_PREFIX) + snprintf(buf, MAXSZ_HICN_PREFIX, "(error)"); + DEBUG("sending IU/IN for name %s on all nexthops", buf); }) mapme_params_t params = { @@ -364,14 +357,8 @@ int mapme_send_to_nexthops(const mapme_t *mapme, fib_entry_t *entry, .seq = tfib->seq, }; - hicn_prefix_t prefix; - if (hicn_prefix_from_name(name, &prefix) < 0) { - ERROR("Failed to create lib's name"); - return -1; - } - uint8_t packet[MTU]; - size_t size = hicn_mapme_create_packet(packet, &prefix, ¶ms); + size_t size = hicn_mapme_create_packet(packet, prefix, ¶ms); if (size <= 0) { ERROR("Could not create MAP-Me packet"); return -1; @@ -379,7 +366,6 @@ int mapme_send_to_nexthops(const mapme_t *mapme, fib_entry_t *entry, connection_table_t *table = forwarder_get_connection_table(mapme->forwarder); - unsigned nexthop; nexthops_foreach(nexthops, nexthop, { INFO("sending mapme packet on connection %d", nexthop); const connection_t *conn = connection_table_get_by_id(table, nexthop); @@ -389,6 +375,7 @@ int mapme_send_to_nexthops(const mapme_t *mapme, fib_entry_t *entry, return 0; } +#if 0 /** * * Here nexthops is not necessarily FIB nexthops as we might advertise given FIB @@ -410,6 +397,7 @@ void mapme_maybe_send_to_nexthops(const mapme_t *mapme, fib_entry_t *fib_entry, mapme_send_to_nexthops(mapme, fib_entry, nexthops); } +#endif /****************************************************************************** * MAPME API @@ -423,15 +411,16 @@ int mapme_set_all_adjacencies(const mapme_t *mapme, fib_entry_t *entry) { /* Apply the policy of the fib_entry over all neighbours */ nexthops_t new_nexthops = NEXTHOPS_EMPTY; - nexthops_t *nexthops = - fib_entry_get_available_nexthops(entry, ~0, &new_nexthops); + nexthops_t *nexthops = fib_entry_get_mapme_nexthops(entry, &new_nexthops); /* We set force to true to avoid overriding the FIB cache */ - return mapme_set_adjacencies(mapme, entry, nexthops, true); + return mapme_set_adjacencies(mapme, entry, nexthops); } +// XXX this will change with the FIB cache +// XXX we are sometimes incrementing tfib seq for nothing int mapme_set_adjacencies(const mapme_t *mapme, fib_entry_t *entry, - nexthops_t *nexthops, bool force) { + nexthops_t *nexthops) { if (mapme->enabled == false) { WARN("MAP-Me is NOT enabled"); return -1; @@ -449,12 +438,7 @@ int mapme_set_adjacencies(const mapme_t *mapme, fib_entry_t *entry, nexthops_clear(&tfib->nexthops); tfib->seq++; - if (force) { - mapme_send_to_nexthops(mapme, entry, nexthops); - return 0; - } - - mapme_maybe_send_to_nexthops(mapme, entry, nexthops); + mapme_send_to_nexthops(mapme, entry, nexthops); return 0; } @@ -473,7 +457,7 @@ int mapme_update_adjacencies(const mapme_t *mapme, fib_entry_t *entry, if (inc_iu_seq) tfib->seq++; - mapme_maybe_send_to_nexthops(mapme, entry, &tfib->nexthops); + mapme_send_to_nexthops(mapme, entry, &tfib->nexthops); return 0; } @@ -490,6 +474,7 @@ int mapme_send_to_nexthop(const mapme_t *mapme, fib_entry_t *entry, return mapme_send_to_nexthops(mapme, entry, &nexthops); } +#if 0 /* * Callback called everytime a new connection is created by the control protocol */ @@ -539,9 +524,9 @@ void mapme_on_connection_event(const mapme_t *mapme, /* We need to send a MapMe update on the newly selected connections for * each concerned fib_entry : connection is involved, or no more involved */ const fib_t *fib = forwarder_get_fib(mapme->forwarder); - fib_entry_t *entry; fib_foreach_entry(fib, entry, { mapme_set_all_adjacencies(mapme, entry); }); } +#endif /*------------------------------------------------------------------------------ * Special Interest handling @@ -811,30 +796,25 @@ static void mapme_on_interest(mapme_t *mapme, msgbuf_t *msgbuf, uint8_t *ack_packet = msgbuf_get_packet(ack); size_t size = hicn_mapme_create_ack(ack_packet, params); - if (connection_send_packet(conn_in, ack_packet, size) < 0) { + if (!connection_send_packet(conn_in, ack_packet, size)) { /* We accept the packet knowing we will get a retransmit */ ERROR("Failed to send ACK packet"); } msgbuf_pool_put(msgbuf_pool, ack); - /* process received interest */ - uint8_t *packet = msgbuf_get_packet(msgbuf); - name_create_from_interest(packet, msgbuf_get_name(msgbuf)); - Name name = EMPTY_NAME; - name_Copy(msgbuf_get_name(msgbuf), &name); - name_setLen(&name, prefix->len); - WITH_DEBUG({ - char *name_str = name_ToString(&name); - DEBUG("Ack'ed interest : connection=%d prefix=%s seq=%d", ingress_id, - name_str, params->seq); - free(name_str); + char buf[MAXSZ_HICN_PREFIX]; + int rc = hicn_prefix_snprintf(buf, MAXSZ_HICN_PREFIX, prefix); + if (rc < 0 || rc >= MAXSZ_HICN_PREFIX) + snprintf(buf, MAXSZ_HICN_PREFIX, "%s", "(error)"); + DEBUG("Ack'ed interest : connection=%d prefix=%s seq=%d", ingress_id, buf, + params->seq); }); /* EPM on FIB */ const fib_t *fib = forwarder_get_fib(mapme->forwarder); - fib_entry_t *entry = fib_contains(fib, &name); + fib_entry_t *entry = fib_contains(fib, prefix); if (!entry) { #ifdef HICN_MAPME_ALLOW_NONEXISTING_FIB_ENTRY if (mapme_create_fib_entry(mapme, &name, ingress_id) < 0) { @@ -883,7 +863,6 @@ static void mapme_on_interest(mapme_t *mapme, msgbuf_t *msgbuf, * This could might optimized for situations where nothing changes, but * this is very unlikely if not impossible... * */ - unsigned prevhop; nexthops_foreach(&entry->nexthops, prevhop, { nexthops_add(&tfib->nexthops, prevhop); }); nexthops_remove(&tfib->nexthops, ingress_id); @@ -943,23 +922,17 @@ static void mapme_on_interest(mapme_t *mapme, msgbuf_t *msgbuf, static void mapme_on_data(mapme_t *mapme, msgbuf_t *msgbuf, unsigned ingress_id, hicn_prefix_t *prefix, mapme_params_t *params) { - INFO("Receive IU/IN Ack on connection %d", ingress_id); - - uint8_t *packet = msgbuf_get_packet(msgbuf); - name_create_from_data(packet, msgbuf_get_name(msgbuf)); - Name name = EMPTY_NAME; - name_Copy(msgbuf_get_name(msgbuf), &name); - name_setLen(&name, prefix->len); - WITH_DEBUG({ - char *name_str = name_ToString(&name); - DEBUG("Received ack for name prefix=%s seq=%d on conn id=%d", name_str, + char buf[MAXSZ_HICN_PREFIX]; + int rc = hicn_prefix_snprintf(buf, MAXSZ_HICN_PREFIX, prefix); + if (rc < 0 || rc >= MAXSZ_HICN_PREFIX) + snprintf(buf, MAXSZ_HICN_PREFIX, "(error)"); + DEBUG("Received ack for name prefix=%s seq=%d on conn id=%d", buf, params->seq, ingress_id); - free(name_str); }) const fib_t *fib = forwarder_get_fib(mapme->forwarder); - fib_entry_t *entry = fib_contains(fib, &name); + fib_entry_t *entry = fib_contains(fib, prefix); if (!entry) { INFO("Ignored ACK with no corresponding FIB entry"); return; @@ -1031,6 +1004,7 @@ void mapme_process(mapme_t *mapme, msgbuf_t *msgbuf) { } } +#if 0 /* * Returns true iif the message corresponds to a MAP-Me packet */ @@ -1048,6 +1022,7 @@ bool mapme_match_packet(const uint8_t *packet) { return false; } } +#endif void mapme_set_enable(mapme_t *mapme, bool enable) { mapme->enabled = enable; } void mapme_set_discovery(mapme_t *mapme, bool enable) { diff --git a/hicn-light/src/hicn/core/mapme.h b/hicn-light/src/hicn/core/mapme.h index 8c2ca477f..188607421 100644 --- a/hicn-light/src/hicn/core/mapme.h +++ b/hicn-light/src/hicn/core/mapme.h @@ -26,7 +26,7 @@ #include <stdbool.h> #include <stdint.h> -#include <hicn/ctrl/hicn-light-ng.h> +#include <hicn/ctrl/hicn-light.h> #include <hicn/hicn.h> #include "connection.h" @@ -87,7 +87,7 @@ int mapme_set_all_adjacencies(const mapme_t *mapme, fib_entry_t *entry); * @param [in] nexthops - next hops on which to send the update. */ int mapme_set_adjacencies(const mapme_t *mapme, fib_entry_t *entry, - nexthops_t *nexthops, bool force); + nexthops_t *nexthops); /** * @function mapme_update_adjacencies diff --git a/hicn-light/src/hicn/core/messageHandler.h b/hicn-light/src/hicn/core/messageHandler.h deleted file mode 100644 index fe26d0579..000000000 --- a/hicn-light/src/hicn/core/messageHandler.h +++ /dev/null @@ -1,660 +0,0 @@ -/* - * Copyright (c) 2021 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 HICNLIGHT_MESSAGE_HANDLER_H -#define HICNLIGHT_MESSAGE_HANDLER_H - -#include <stdlib.h> -#ifndef _WIN32 -#include <unistd.h> // close -#endif /* _WIN32 */ - -#include <hicn/hicn.h> - -//#include <hicn/core/connection_table.h> - -#define H(packet) ((hicn_header_t *)packet) -#define H6(packet) (H(packet)->v6.ip) -#define H6T(packet) (H(packet)->v6.tcp) -#define H4(packet) (H(packet)->v4.ip) -#define H4T(packet) (H(packet)->v4.tcp) - -#define HICN_V6_LEN(packet) (H6(packet).len) -#define HICN_V4_LEN(packet) (H4(packet).len) - -/*** codes and types ***/ -#define IPv6_TYPE 6 -#define IPv4_TYPE 4 -#define ICMP_WLDR_TYPE 42 -#define ICMP_WLDR_CODE 0 -#define ICMP_LB_TYPE 43 - -/*** masks and constants ***/ -#define PATH_LABEL_MASK 0x8000 // 1000 0000 0000 0000 -#define NOT_PATH_LABEL_MASK 0x7fff // 0111 0000 0000 0000 -#define UINT16_T_MASK 0x0000ffff // 1111 1111 1111 1111 - -/*** HICN ALLOWED PORTS ***/ -#define CONTROL_PORT 9695 -#define HTTP_PORT 8080 - -#define MIN_PROBE_SUFFIX 0xefffffff -#define MAX_PROBE_SUFFIX 0xffffffff - 1 - -// XXX Hardcoded packet format HF_INET6_TCP - -#define IPV6_DEFAULT_VERSION 6 -#define IPV6_DEFAULT_TRAFFIC_CLASS 0 -#define IPV6_DEFAULT_FLOW_LABEL 0 - -//#include <hicn/core/forwarder.h> - -//#ifdef WITH_MAPME -//#include <hicn/core/mapme.h> -//#include <hicn/socket/api.h> -//#endif /* WITH_MAPME */ - -#define BFD_PORT 3784 - -static inline uint8_t messageHandler_GetIPPacketType(const uint8_t *message) { - return HICN_IP_VERSION(message); -} - -static inline void messageHandler_UpdateTCPCheckSum(uint8_t *message, - uint16_t *old_val, - uint16_t *new_val, - uint8_t size) { - switch (messageHandler_GetIPPacketType(message)) { - case IPv4_TYPE: - for (uint8_t i = 0; i < size; i++) { - uint16_t old_csum = ~(H4T(message).csum); - uint16_t not_old_val = ~(*old_val); - uint32_t sum = (uint32_t)old_csum + not_old_val + *new_val; - - while (sum >> 16) { - sum = (sum >> 16) + (sum & UINT16_T_MASK); - } - - H4T(message).csum = ~sum; - ++old_val; - ++new_val; - } - break; - case IPv6_TYPE: - for (uint8_t i = 0; i < size; i++) { - uint16_t old_csum = ~(H6T(message).csum); - uint16_t not_old_val = ~(*old_val); - uint32_t sum = (uint32_t)old_csum + not_old_val + *new_val; - - while (sum >> 16) { - sum = (sum >> 16) + (sum & UINT16_T_MASK); - } - - H6T(message).csum = ~sum; - ++old_val; - ++new_val; - } - break; - default: - return; - } -} - -static inline void messageHandler_UpdateIPv4CheckSum(uint8_t *message, - uint16_t *old_val, - uint16_t *new_val, - uint8_t size) { - for (uint8_t i = 0; i < size; i++) { - uint16_t old_csum = ~(H4(message).csum); - uint16_t not_old_val = ~(*old_val); - uint32_t sum = (uint32_t)old_csum + not_old_val + *new_val; - - while (sum >> 16) { - sum = (sum >> 16) + (sum & UINT16_T_MASK); - } - - H4(message).csum = ~sum; - ++old_val; - ++new_val; - } -} - -static inline size_t messageHandler_GetEmptyTCPPacketSize(unsigned ipVersion) { - if (ipVersion == IPv4_TYPE) - return IPV4_HDRLEN + TCP_HDRLEN; - else if (ipVersion == IPv6_TYPE) - return IPV6_HDRLEN + TCP_HDRLEN; - else - return 0; -} - -static inline size_t messageHandler_GetICMPPacketSize(unsigned ipVersion) { - if (ipVersion == IPv4_TYPE) - return IPV4_HDRLEN + ICMP_HDRLEN; - else if (ipVersion == IPv6_TYPE) - return IPV6_HDRLEN + ICMP_HDRLEN; - else - return 0; -} - -static inline size_t messageHandler_GetIPHeaderLength(unsigned ipVersion) { - if (ipVersion == IPv4_TYPE) - return IPV4_HDRLEN; - else if (ipVersion == IPv6_TYPE) - return IPV6_HDRLEN; - else - return 0; -} - -#if 0 -static inline bool messageHandler_IsValidHicnPacket(const uint8_t *message) { - uint8_t version = messageHandler_GetIPPacketType(message); - if (version == IPv6_TYPE || version == IPv4_TYPE) { - return true; - } - return false; -} -#endif - -static inline uint8_t messageHandler_NextHeaderType(const uint8_t *message) { - switch (messageHandler_GetIPPacketType(message)) { - case IPv6_TYPE: - return (uint8_t)H6(message).nxt; - case IPv4_TYPE: - return (uint8_t)H4(message).protocol; - default: - return 0; - } -} - -static inline bool messageHandler_IsTCP(const uint8_t *message) { - if (messageHandler_NextHeaderType(message) != IPPROTO_TCP) return false; - return true; -} - -static inline bool messageHandler_IsInterest(const uint8_t *message) { - if (!messageHandler_IsTCP(message)) return false; - - bool flag; - hicn_packet_test_ece(HF_INET6_TCP, (hicn_header_t *)message, - &flag); // ECE flag is set to 0 in interest packets - if (flag == false) return true; - return false; -} - -static inline bool messageHandler_IsData(const uint8_t *message) { - if (!messageHandler_IsTCP(message)) return false; - - bool flag; - hicn_packet_test_ece(HF_INET6_TCP, (hicn_header_t *)message, - &flag); // ECE flag is set to 1 in data packets - if (flag == true) return true; - return false; -} - -static inline bool messageHandler_IsWldrNotification(const uint8_t *message) { - // this function returns true only if the packet is an ICMP packet in Wldr - // form. type must be equal to ICMP_WLDR_TYPE and code equal to ICMP_WLDR_CODE - uint8_t next_header = messageHandler_NextHeaderType(message); - - const uint8_t *icmp_ptr; - if (next_header == IPPROTO_ICMP) { - icmp_ptr = message + IPV4_HDRLEN; - } else if (next_header == IPPROTO_ICMPV6) { - icmp_ptr = message + IPV6_HDRLEN; - } else { - return false; - } - - uint8_t type = ((_icmp_header_t *)icmp_ptr)->type; - uint8_t code = ((_icmp_header_t *)icmp_ptr)->code; - if (type == ICMP_WLDR_TYPE && code == ICMP_WLDR_CODE) { - return true; - } - - return false; -} - -static inline bool messageHandler_IsLoadBalancerProbe(const uint8_t *message) { - uint8_t next_header = messageHandler_NextHeaderType(message); - - const uint8_t *icmp_ptr; - if (next_header == IPPROTO_ICMP) { - icmp_ptr = message + IPV4_HDRLEN; - } else if (next_header == IPPROTO_ICMPV6) { - icmp_ptr = message + IPV6_HDRLEN; - } else { - return false; - } - - uint8_t type = ((_icmp_header_t *)icmp_ptr)->type; - if (type == ICMP_LB_TYPE) { - return true; - } - - return false; -} - -static inline uint16_t messageHandler_GetTotalPacketLength( - const uint8_t *message) { - switch (messageHandler_GetIPPacketType(message)) { - case IPv6_TYPE: - return ntohs((uint16_t)HICN_V6_LEN(message)) + IPV6_HDRLEN; - case IPv4_TYPE: - return ntohs((uint16_t)HICN_V4_LEN(message)); - default: - return 0; - } -} - -static inline uint32_t messageHandler_GetSegment(const uint8_t *message) { - if (!messageHandler_IsTCP(message)) return 0; - - switch (messageHandler_GetIPPacketType(message)) { - case IPv6_TYPE: - return ntohl((uint32_t)H6T(message).seq); - case IPv4_TYPE: - return ntohl((uint32_t)H4T(message).seq); - default: - return 0; - } -} - -static inline uint16_t messageHandler_GetExpectedWldrLabel( - const uint8_t *message) { - const uint8_t *icmp_ptr; - switch (messageHandler_GetIPPacketType(message)) { - case IPv6_TYPE: - icmp_ptr = message + IPV6_HDRLEN; - break; - case IPv4_TYPE: - icmp_ptr = message + IPV4_HDRLEN; - break; - default: - return 0; - } - - return ntohs( - ((_icmp_wldr_header_t *)icmp_ptr)->wldr_notification_lbl.expected_lbl); -} - -static inline uint16_t messageHandler_GetWldrLastReceived( - const uint8_t *message) { - const uint8_t *icmp_ptr; - switch (messageHandler_GetIPPacketType(message)) { - case IPv6_TYPE: - icmp_ptr = message + IPV6_HDRLEN; - break; - case IPv4_TYPE: - icmp_ptr = message + IPV4_HDRLEN; - break; - default: - return 0; - } - - return ntohs( - ((_icmp_wldr_header_t *)icmp_ptr)->wldr_notification_lbl.received_lbl); -} - -static inline uint16_t messageHandler_GetWldrLabel(const uint8_t *message) { - switch (messageHandler_GetIPPacketType(message)) { - case IPv6_TYPE: - return ntohs((uint16_t)H6T(message).window); - case IPv4_TYPE: - return ntohs((uint16_t)H4T(message).window); - default: - return 0; - } -} - -static inline void messageHandler_SetWldrLabel(uint8_t *message, - uint16_t label) { - uint16_t old_val = messageHandler_GetWldrLabel(message); - - switch (messageHandler_GetIPPacketType(message)) { - case IPv6_TYPE: - H6T(message).window = htons(label); - break; - case IPv4_TYPE: - H4T(message).window = htons(label); - break; - default: - break; - } - - messageHandler_UpdateTCPCheckSum(message, &old_val, &label, 1); -} - -static inline void messageHandler_ResetWldrLabel(uint8_t *message) { - messageHandler_SetWldrLabel(message, 0); -} - -static inline bool messageHandler_HasWldr(const uint8_t *message) { - if (messageHandler_IsTCP(message)) { - uint16_t lbl = messageHandler_GetWldrLabel(message); - if (lbl != 0) { - return true; - } - } - return false; -} - -static inline uint32_t messageHandler_GetPathLabel(const uint8_t *message) { - if (!messageHandler_IsTCP(message)) return 0; - - uint32_t path_label; - int res = hicn_data_get_path_label((hicn_header_t *)message, &path_label); - if (res < 0) return 0; - return path_label; -} - -static inline void messageHandler_SetPathLabel(uint8_t *message, - uint32_t old_path_label, - uint32_t new_path_label) { - if (!messageHandler_IsTCP(message)) return; - - hicn_data_set_path_label((hicn_header_t *)message, new_path_label); - - messageHandler_UpdateTCPCheckSum(message, (uint16_t *)&old_path_label, - (uint16_t *)&new_path_label, 2); -} - -static inline void messageHandler_UpdatePathLabel(uint8_t *message, - uint8_t outFace) { - if (!messageHandler_IsTCP(message)) return; - - uint32_t pl_old_32bit = messageHandler_GetPathLabel(message); - uint8_t pl_old_8bit = (uint8_t)(pl_old_32bit >> 24UL); - uint32_t pl_new_32bit = - (uint32_t)((((pl_old_8bit << 1) | (pl_old_8bit >> 7)) ^ outFace) << 24UL); - - // XXX path label should be 8 bits now ? - messageHandler_SetPathLabel(message, pl_old_32bit, pl_new_32bit); -} - -static inline void messageHandler_ResetPathLabel(uint8_t *message) { - messageHandler_SetPathLabel(message, messageHandler_GetPathLabel(message), 0); -} - -static inline uint32_t messageHandler_GetInterestLifetime( - const uint8_t *message) { - if (!messageHandler_IsTCP(message)) return 0; - - hicn_lifetime_t lifetime; - int res = hicn_interest_get_lifetime((hicn_header_t *)message, &lifetime); - if (res < 0) return 0; - return lifetime; -} - -static inline bool messageHandler_SetInterestLifetime(uint8_t *message, - u32 lifetime) { - if (!messageHandler_IsTCP(message)) return false; - - int res = hicn_interest_set_lifetime((hicn_header_t *)message, lifetime); - if (res < 0) return false; - return true; -} - -static inline bool messageHandler_SetDataExpiryTime(uint8_t *message, - u32 lifetime) { - if (!messageHandler_IsTCP(message)) return false; - - int res = hicn_data_set_expiry_time((hicn_header_t *)message, lifetime); - if (res < 0) return false; - return true; -} - -static inline bool messageHandler_HasInterestLifetime(const uint8_t *message) { - if (!messageHandler_IsTCP(message)) return false; - - if (messageHandler_GetInterestLifetime(message) == 0) return false; - return true; -} - -static inline uint32_t messageHandler_GetContentExpiryTime( - const uint8_t *message) { - if (!messageHandler_IsTCP(message)) return 0; - - uint32_t expirationTime; - int res = - hicn_data_get_expiry_time((hicn_header_t *)message, &expirationTime); - if (res < 0) return 0; - return expirationTime; -} - -static inline bool messageHandler_HasContentExpiryTime(const uint8_t *message) { - if (!messageHandler_IsTCP(message)) return 0; - - uint32_t expirationTime; - int res = - hicn_data_get_expiry_time((hicn_header_t *)message, &expirationTime); - if (res < 0) return false; - - if (expirationTime == HICN_MAX_LIFETIME) return false; - - return true; -} - -static inline void *messageHandler_GetSource(const uint8_t *message) { - switch (messageHandler_GetIPPacketType(message)) { - case IPv6_TYPE: - return &H6(message).saddr; - break; - case IPv4_TYPE: - return &H4(message).saddr; - break; - default: - return NULL; - } -} - -static inline void *messageHandler_GetDestination(const uint8_t *message) { - switch (messageHandler_GetIPPacketType(message)) { - case IPv6_TYPE: - return &H6(message).daddr; - break; - case IPv4_TYPE: - return &H4(message).daddr; - break; - default: - return NULL; - } -} - -static inline void messageHandler_SetSource_IPv6(uint8_t *message, - struct in6_addr *address) { - if (messageHandler_IsTCP(message)) { - uint16_t *old_src = (uint16_t *)messageHandler_GetSource(message); - messageHandler_UpdateTCPCheckSum(message, old_src, (uint16_t *)address, 8); - } - H6(message).saddr.as_in6addr = *address; -} - -static inline void messageHandler_SetDestination_IPv6( - uint8_t *message, struct in6_addr *address) { - if (messageHandler_IsTCP(message)) { - uint16_t *old_dst = (uint16_t *)messageHandler_GetDestination(message); - messageHandler_UpdateTCPCheckSum(message, old_dst, (uint16_t *)address, 8); - } - H6(message).daddr.as_in6addr = *address; -} - -static inline void messageHandler_SetSource_IPv4(uint8_t *message, - uint32_t *address) { - // update tcp checksum - uint16_t *old_src = (uint16_t *)messageHandler_GetSource(message); - if (messageHandler_IsTCP(message)) { - messageHandler_UpdateTCPCheckSum(message, old_src, (uint16_t *)address, 2); - } - // update IPv4 cheksum - // the IPv4 checksum is not part of the psudo header for TCP checksum - // calculation we can update them separetelly - messageHandler_UpdateIPv4CheckSum(message, old_src, (uint16_t *)address, 2); - - H4(message).saddr.as_u32 = *address; -} - -static inline void messageHandler_SetDestination_IPv4(uint8_t *message, - uint32_t *address) { - uint16_t *old_dst = (uint16_t *)messageHandler_GetDestination(message); - if (messageHandler_IsTCP(message)) { - messageHandler_UpdateTCPCheckSum(message, old_dst, (uint16_t *)address, 2); - } - messageHandler_UpdateIPv4CheckSum(message, old_dst, (uint16_t *)address, 2); - H4(message).daddr.as_u32 = *address; -} - -static inline void messageHandler_SetWldrNotification(uint8_t *notification, - uint8_t *original, - uint16_t expected, - uint16_t received) { - hicn_header_t *h = (hicn_header_t *)notification; - switch (messageHandler_GetIPPacketType(original)) { - case IPv6_TYPE: { - *h = (hicn_header_t){.v6 = { - .ip = - (_ipv6_header_t){ - .version_class_flow = htonl( - (IPV6_DEFAULT_VERSION << 28) | - (IPV6_DEFAULT_TRAFFIC_CLASS << 20) | - (IPV6_DEFAULT_FLOW_LABEL & 0xfffff)), - .len = htons(ICMP_HDRLEN), - .nxt = IPPROTO_ICMPV6, - .hlim = 5, - }, - /* - .wldr = - { - .type = ICMP_WLDR_TYPE, - .code = ICMP_WLDR_CODE, - .wldr_notification_lbl = - { - .expected_lbl = htons(expected), - .received_lbl = htons(received), - }, - },*/ - }}; - messageHandler_SetSource_IPv6( - notification, - (struct in6_addr *)messageHandler_GetDestination(original)); - messageHandler_SetDestination_IPv6( - notification, (struct in6_addr *)messageHandler_GetSource(original)); - break; - } - case IPv4_TYPE: { - break; - } - default: - break; - } -} - -static inline void messageHandler_ModifySuffix(uint8_t *packet, - uint32_t new_suffix) { - hicn_format_t format; - hicn_name_t name; - hicn_packet_get_format((hicn_header_t *)packet, &format); - hicn_interest_get_name(format, (hicn_header_t *)packet, &name); - hicn_name_set_seq_number(&name, new_suffix); - hicn_interest_set_name(format, (hicn_header_t *)packet, &name); -} - -static inline uint8_t *messageHandler_CreateProbePacket( - hicn_format_t format, uint32_t probe_lifetime) { - size_t header_length; - hicn_packet_get_header_length_from_format(format, &header_length); - - uint8_t *pkt = (uint8_t *)calloc(header_length, 1); - - hicn_packet_init_header(format, (hicn_header_t *)pkt); - - hicn_packet_set_dst_port(format, (hicn_header_t *)pkt, BFD_PORT); - hicn_interest_set_lifetime((hicn_header_t *)pkt, probe_lifetime); - - return pkt; -} - -static inline void messageHandler_CreateProbeReply(uint8_t *probe, - hicn_format_t format) { - hicn_name_t probe_name; - hicn_interest_get_name(format, (const hicn_header_t *)probe, &probe_name); - ip_address_t probe_locator; - hicn_interest_get_locator(format, (const hicn_header_t *)probe, - &probe_locator); - - uint16_t src_prt; - uint16_t dst_prt; - hicn_packet_get_src_port(format, (const hicn_header_t *)probe, &src_prt); - hicn_packet_get_dst_port(format, (const hicn_header_t *)probe, &dst_prt); - hicn_packet_set_src_port(format, (hicn_header_t *)probe, dst_prt); - hicn_packet_set_dst_port(format, (hicn_header_t *)probe, src_prt); - - hicn_data_set_name(format, (hicn_header_t *)probe, &probe_name); - hicn_data_set_locator(format, (hicn_header_t *)probe, &probe_locator); - hicn_data_set_expiry_time((hicn_header_t *)probe, 0); -} - -static inline hicn_name_t *messageHandler_CreateProbeName( - const ip_prefix_t *address) { - hicn_name_t *name = (hicn_name_t *)calloc(sizeof(hicn_name_t), 1); - hicn_name_create_from_ip_prefix(address, 0, name); - return name; -} - -static inline void messageHandler_SetProbeName(uint8_t *probe, - hicn_format_t format, - hicn_name_t *name, - uint32_t seq) { - hicn_name_set_seq_number(name, seq); - hicn_interest_set_name(format, (hicn_header_t *)probe, name); -} - -static inline bool messageHandler_IsAProbe(const uint8_t *packet) { - hicn_format_t format; - hicn_name_t name; - uint32_t seq; - hicn_packet_get_format((hicn_header_t *)packet, &format); - hicn_data_get_name(format, (hicn_header_t *)packet, &name); - hicn_name_get_seq_number(&name, &seq); - if (seq >= MIN_PROBE_SUFFIX && seq <= MAX_PROBE_SUFFIX) return true; - return false; - -#if 0 - // old probe version - uint16_t src_prt; - uint16_t dst_prt; - hicn_packet_get_src_port (HF_INET6_TCP, (const hicn_header_t *) packet, &src_prt); - hicn_packet_get_dst_port (HF_INET6_TCP, (const hicn_header_t *) packet, &dst_prt); - - if(dst_prt == BFD_PORT){ - //interest probe - return true; - } - - if(src_prt == BFD_PORT){ - //data (could be a probe) - uint32_t expiry_time; - hicn_data_get_expiry_time ((const hicn_header_t *) packet, &expiry_time); - if(expiry_time == 0){ - //this is a probe - return true; - } - } - - return false; -#endif -} - -#endif /* HICNLIGHT_MESSAGE_HANDLER_H */ diff --git a/hicn-light/src/hicn/core/msgbuf.c b/hicn-light/src/hicn/core/msgbuf.c index 299b20f9b..c58f7a7dc 100644 --- a/hicn-light/src/hicn/core/msgbuf.c +++ b/hicn-light/src/hicn/core/msgbuf.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -19,3 +19,37 @@ */ #include "msgbuf.h" +#include "../strategies/probe_generator.h" + +int msgbuf_initialize(msgbuf_t *msgbuf) { + /* + * We define the format and the storage area of the packet buffer we + * manipulate + */ + hicn_packet_buffer_t *pkbuf = msgbuf_get_pkbuf(msgbuf); + hicn_packet_set_buffer(pkbuf, msgbuf->packet, MTU, 0); + hicn_packet_init_header(pkbuf, 0); + return 0; +} + +int msgbuf_initialize_from_packet(msgbuf_t *msgbuf) { + hicn_packet_set_buffer(msgbuf_get_pkbuf(msgbuf), msgbuf->packet, MTU, + msgbuf_get_len(msgbuf)); + return 0; +} + +bool msgbuf_is_command(const msgbuf_t *msgbuf) { + return (*msgbuf->packet == REQUEST_LIGHT); +} + +bool msgbuf_is_probe(const msgbuf_t *msgbuf) { + hicn_name_t name; + hicn_name_suffix_t suffix; + + assert(msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_DATA); + + const hicn_packet_buffer_t *pkbuf = msgbuf_get_pkbuf(msgbuf); + hicn_data_get_name(pkbuf, &name); + suffix = hicn_name_get_suffix(&name); + return (suffix >= MIN_PROBE_SUFFIX && suffix <= MAX_PROBE_SUFFIX); +} diff --git a/hicn-light/src/hicn/core/msgbuf.h b/hicn-light/src/hicn/core/msgbuf.h index e437f1d09..26fd47540 100644 --- a/hicn-light/src/hicn/core/msgbuf.h +++ b/hicn-light/src/hicn/core/msgbuf.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -21,10 +21,10 @@ #ifndef HICNLIGHT_MSGBUF #define HICNLIGHT_MSGBUF -#include "name.h" +#include <hicn/name.h> #include "ticks.h" -#include "messageHandler.h" -#include <hicn/ctrl/hicn-light-ng.h> +#include <hicn/hicn.h> +#include <hicn/ctrl/hicn-light.h> #define MTU 1500 #define INVALID_MSGBUF_ID ~0ul @@ -32,33 +32,19 @@ #define msgbuf_id_is_valid(msgbuf_id) \ ((unsigned long)msgbuf_id != INVALID_MSGBUF_ID) -#define foreach_msg_type \ - _(UNDEFINED) \ - _(INTEREST) \ - _(DATA) \ - _(WLDR_NOTIFICATION) \ - _(MAPME) \ - _(COMMAND) \ - _(N) - -typedef enum { -#define _(x) MSGBUF_TYPE_##x, - foreach_msg_type -#undef _ -} msgbuf_type_t; -#undef foreach_msg_type - typedef struct { - unsigned length; - msgbuf_type_t type; - unsigned connection_id; - Ticks recv_ts; - unsigned refs; - unsigned path_label; + hicn_packet_buffer_t pkbuf; + unsigned connection_id; // ingress + Ticks recv_ts; // timestamp + unsigned refs; // refcount + unsigned path_label; // XXX what is this ? + + // XXX Cache storage union { /* Interest or data packet */ struct { - Name name; + hicn_name_t name; + u32 name_hash; // XXX should be always populate when name is assigned } id; /* Command packet */ struct { @@ -68,53 +54,142 @@ typedef struct { uint8_t packet[MTU]; } msgbuf_t; -#define msgbuf_get_name(M) (&((M)->id.name)) +int msgbuf_initialize(msgbuf_t *msgbuf); +int msgbuf_initialize_from_packet(msgbuf_t *msgbuf); + +#define msgbuf_get_pkbuf(M) (&(M)->pkbuf) + +static inline hicn_packet_type_t msgbuf_get_type(const msgbuf_t *msgbuf) { + return hicn_packet_get_type(msgbuf_get_pkbuf(msgbuf)); +} + +static inline void msgbuf_set_type(msgbuf_t *msgbuf, hicn_packet_type_t type) { + hicn_packet_set_type(msgbuf_get_pkbuf(msgbuf), type); +} + +static inline const hicn_name_t *msgbuf_get_name(const msgbuf_t *msgbuf) { + hicn_packet_type_t type = msgbuf_get_type(msgbuf); + assert(type == HICN_PACKET_TYPE_INTEREST || type == HICN_PACKET_TYPE_DATA); + (void)type; + + return &msgbuf->id.name; +} + #define msgbuf_get_connection_id(M) ((M)->connection_id) -#define msgbuf_get_type(M) ((M)->type) -#define msgbuf_has_wldr(M) (messageHandler_HasWldr((M)->packet)) -#define msgbuf_get_len(M) ((M)->length) #define msgbuf_get_packet(M) ((M)->packet) #define msgbuf_get_command_type(M) ((M)->command.type) +#if WITH_WLDR +#define msgbuf_has_wldr(M) (messageHandler_HasWldr((M)->packet)) +#endif + +static inline void msgbuf_set_name(msgbuf_t *msgbuf, const hicn_name_t *name) { + msgbuf->id.name = *name; +} + +static inline size_t msgbuf_get_len(const msgbuf_t *msgbuf) { + return hicn_packet_get_len(msgbuf_get_pkbuf(msgbuf)); +} -// XXX TODO EXPLAIN THE CONSTANT -#define msgbuf_get_lifetime(M) \ - (NSEC_TO_TICKS(messageHandler_GetInterestLifetime((M)->packet) * 1000000ULL)) +static inline void msgbuf_set_len(msgbuf_t *msgbuf, size_t len) { + int rc = hicn_packet_set_len(msgbuf_get_pkbuf(msgbuf), len); + assert(rc == HICN_LIB_ERROR_NONE); // XXX + _unused(rc); +} + +static inline u32 msgbuf_get_name_hash(const msgbuf_t *msgbuf) { + hicn_packet_type_t type = msgbuf_get_type(msgbuf); + assert(type == HICN_PACKET_TYPE_INTEREST || type == HICN_PACKET_TYPE_DATA); + _unused(type); + return msgbuf->id.name_hash; +} // Lifetimes/expiry times in milliseconds -#define msgbuf_get_interest_lifetime(M) \ - (messageHandler_GetInterestLifetime((M)->packet)) -#define msgbuf_get_data_expiry_time(M) \ - (messageHandler_GetContentExpiryTime((M)->packet)) +static inline u32 msgbuf_get_interest_lifetime(const msgbuf_t *msgbuf) { + u32 lifetime; + int rc = hicn_interest_get_lifetime(msgbuf_get_pkbuf(msgbuf), &lifetime); + assert(rc == HICN_LIB_ERROR_NONE); // XXX + _unused(rc); + return lifetime; +} + +//#define msgbuf_get_lifetime(M) +// (NSEC_TO_TICKS(messageHandler_GetInterestLifetime((M)->packet) * +// 1000000ULL)) +#define msgbuf_get_lifetime msgbuf_get_interest_lifetime static inline bool msgbuf_set_interest_lifetime(msgbuf_t *msgbuf, u32 lifetime) { - return messageHandler_SetInterestLifetime(msgbuf->packet, lifetime); + int rc = hicn_interest_set_lifetime(msgbuf_get_pkbuf(msgbuf), lifetime); + return (rc == HICN_LIB_ERROR_NONE); } -static inline bool msgbuf_set_data_expiry_time(msgbuf_t *msgbuf, u32 lifetime) { - return messageHandler_SetDataExpiryTime(msgbuf->packet, lifetime); + +static inline u32 msgbuf_get_data_expiry_time(const msgbuf_t *msgbuf) { + u32 lifetime; + int rc = hicn_data_get_expiry_time(msgbuf_get_pkbuf(msgbuf), &lifetime); + assert(rc == HICN_LIB_ERROR_NONE); // XXX + _unused(rc); + return lifetime; } -#define msgbuf_is_probe(M) messageHandler_IsAProbe((M)->packet) +static inline bool msgbuf_set_data_expiry_time(msgbuf_t *msgbuf, u32 lifetime) { + int rc = hicn_data_set_expiry_time(msgbuf_get_pkbuf(msgbuf), lifetime); + return (rc == HICN_LIB_ERROR_NONE); +} /* Path label */ -#define msgbuf_init_pathlabel(M) \ - ((M)->path_label = messageHandler_GetPathLabel((M)->packet)) -#define msgbuf_update_pathlabel(M, outface) \ - { \ - messageHandler_SetPathLabel((M)->packet, \ - messageHandler_GetPathLabel((M)->packet), \ - (M)->path_label); \ - messageHandler_UpdatePathLabel((M)->packet, outface); \ - } -#define msgbuf_reset_pathlabel(M) \ - { \ - (M)->path_label = 0; \ - messageHandler_ResetPathLabel((M)->packet); \ - } +static inline void msgbuf_init_pathlabel(msgbuf_t *msgbuf) { + hicn_path_label_t pl; + int rc = hicn_data_get_path_label(msgbuf_get_pkbuf(msgbuf), &pl); + assert(rc == HICN_LIB_ERROR_NONE); + _unused(rc); + msgbuf->path_label = pl; +} + +static inline int msgbuf_get_path_label(const msgbuf_t *msgbuf, + hicn_path_label_t *pl) { + assert(msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_DATA); + return hicn_data_get_path_label(msgbuf_get_pkbuf(msgbuf), pl); +} + +static inline int msgbuf_set_path_label(msgbuf_t *msgbuf, + hicn_path_label_t pl) { + assert(msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_DATA); + return hicn_data_set_path_label(msgbuf_get_pkbuf(msgbuf), pl); +} + +static inline int msgbuf_update_pathlabel(msgbuf_t *msgbuf, + hicn_faceid_t outface) { + assert(msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_DATA); + + hicn_path_label_t pl, newpl; + if (msgbuf_get_path_label(msgbuf, &pl) < 0) return -1; + + update_path_label(pl, outface, &newpl); + + return msgbuf_set_path_label(msgbuf, newpl); +} + +static inline void msgbuf_reset_pathlabel(msgbuf_t *msgbuf) { + msgbuf->path_label = 0; + hicn_data_set_path_label(msgbuf_get_pkbuf(msgbuf), 0); + // ERROR ? +} + +static inline void msgbuf_modify_suffix(msgbuf_t *msgbuf, uint32_t new_suffix) { + hicn_name_t name; + assert(msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_INTEREST); + hicn_interest_get_name(msgbuf_get_pkbuf(msgbuf), &name); + hicn_name_set_suffix(&name, new_suffix); + hicn_interest_set_name(msgbuf_get_pkbuf(msgbuf), &name); +} + +bool msgbuf_is_command(const msgbuf_t *msgbuf); +bool msgbuf_is_probe(const msgbuf_t *msgbuf); /* WLDR */ +#if 0 #define msgbuf_reset_wldr_label(M) (messageHandler_ResetWldrLabel((M)->packet)) #define msgbuf_get_wldr_label(M) (messageHandler_GetWldrLabel((M)->packet)) #define msgbuf_get_wldr_expected_label(M) \ @@ -123,5 +198,6 @@ static inline bool msgbuf_set_data_expiry_time(msgbuf_t *msgbuf, u32 lifetime) { (messageHandler_GetWldrLastReceived((M)->packet)) #define msgbuf_set_wldr_label(M, label) \ (messageHandler_GetWldrLabel((M)->packet, label)) +#endif #endif /* HICNLIGHT_MSGBUF */ diff --git a/hicn-light/src/hicn/core/msgbuf_pool.c b/hicn-light/src/hicn/core/msgbuf_pool.c index a2092aaf6..892bd59a1 100644 --- a/hicn-light/src/hicn/core/msgbuf_pool.c +++ b/hicn-light/src/hicn/core/msgbuf_pool.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -19,6 +19,7 @@ */ #include <hicn/util/pool.h> +#include <hicn/util/log.h> #include "msgbuf_pool.h" msgbuf_pool_t *_msgbuf_pool_create(size_t init_size, size_t max_size) { @@ -90,16 +91,20 @@ void msgbuf_pool_release(msgbuf_pool_t *msgbuf_pool, msgbuf_t **msgbuf_ptr) { if (msgbuf->refs == 0) { WITH_TRACE({ off_t msgbuf_id = msgbuf_pool_get_id(msgbuf_pool, msgbuf); - if (msgbuf->type != MSGBUF_TYPE_INTEREST && - msgbuf->type != MSGBUF_TYPE_DATA) { + if (msgbuf_get_type(msgbuf) != HICN_PACKET_TYPE_INTEREST && + msgbuf_get_type(msgbuf) != HICN_PACKET_TYPE_DATA) { TRACE("Msgbuf %d (%p) - put to msgbuf pool", msgbuf_id, msgbuf); } else { - char *name_str = name_ToString(msgbuf_get_name(msgbuf)); + char buf[MAXSZ_HICN_NAME]; + int rc = + hicn_name_snprintf(buf, MAXSZ_HICN_NAME, msgbuf_get_name(msgbuf)); + if (rc < 0 || rc >= MAXSZ_HICN_NAME) + snprintf(buf, MAXSZ_HICN_NAME, "%s", "(error)"); const char *msgbuf_type_str = - msgbuf->type == MSGBUF_TYPE_INTEREST ? "interest" : "data"; + msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_INTEREST ? "interest" + : "data"; TRACE("Msgbuf %d (%p) - %s (%s) put to msgbuf pool", msgbuf_id, msgbuf, - name_str, msgbuf_type_str); - free(name_str); + buf, msgbuf_type_str); } }) diff --git a/hicn-light/src/hicn/core/name.c b/hicn-light/src/hicn/core/name.c deleted file mode 100644 index d30cebefc..000000000 --- a/hicn-light/src/hicn/core/name.c +++ /dev/null @@ -1,195 +0,0 @@ -/* - * Copyright (c) 2021 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 <assert.h> -#include <limits.h> -#include <hicn/hicn-light/config.h> -#include <stdbool.h> -#include <stdio.h> -#include <string.h> - -#include <hicn/core/messageHandler.h> -#include <hicn/core/name.h> -#include <hicn/util/log.h> -#include <hicn/util/hash.h> - -#define IPv6_TYPE 6 -#define IPv4_TYPE 4 - -static uint32_t _computeHash(Name *name) { - assert(name); - - uint32_t hash1 = nameBitvector_GetHash32(&(name->content_name)); - return hashlittle(&name->segment, sizeof(name->segment), hash1); -} - -// ============================================================================ - -void name_create_from_interest(const uint8_t *packet, Name *name) { - assert(packet); - assert(name); - - if (messageHandler_GetIPPacketType(packet) == IPv6_TYPE) { - nameBitvector_CreateFromIn6Addr( - &(name->content_name), - (struct in6_addr *)messageHandler_GetDestination(packet), 128); - } else if (messageHandler_GetIPPacketType(packet) == IPv4_TYPE) { - nameBitvector_CreateFromInAddr( - &(name->content_name), - *((uint32_t *)messageHandler_GetDestination(packet)), 32); - } else { - ERROR("Error: unknown message type\n"); - return; - } - - name->segment = messageHandler_GetSegment(packet); - name->name_hash = _computeHash(name); -} - -void name_create_from_data(const uint8_t *packet, Name *name) { - assert(packet); - assert(name); - - if (messageHandler_GetIPPacketType(packet) == IPv6_TYPE) { - nameBitvector_CreateFromIn6Addr( - &(name->content_name), - (struct in6_addr *)messageHandler_GetSource(packet), 128); - } else if (messageHandler_GetIPPacketType(packet) == IPv4_TYPE) { - nameBitvector_CreateFromInAddr( - &(name->content_name), *((uint32_t *)messageHandler_GetSource(packet)), - 32); - } else { - printf("Error: unknown message type\n"); - return; - } - - name->segment = messageHandler_GetSegment(packet); - name->name_hash = _computeHash(name); -} - -void name_CreateFromAddress(Name *name, int family, ip_address_t addr, - uint8_t len) { - assert(name); - - switch (family) { - case AF_INET: - nameBitvector_CreateFromInAddr(&(name->content_name), addr.v4.as_u32, - len); - break; - case AF_INET6: - nameBitvector_CreateFromIn6Addr(&(name->content_name), - &addr.v6.as_in6addr, len); - break; - default: - return; - } - - name->segment = 0; - name->name_hash = _computeHash(name); -} - -void name_Copy(const Name *original, Name *copy) { - assert(original); - assert(copy); - - nameBitvector_Copy(&(original->content_name), &(copy->content_name)); - copy->segment = original->segment; - copy->name_hash = original->name_hash; -} - -uint32_t name_HashCode(const Name *name) { - assert(name); - return name->name_hash; -} - -NameBitvector *name_GetContentName(const Name *name) { - assert(name); - return (NameBitvector *)&(name->content_name); -} - -uint32_t name_GetSegment(const Name *name) { - assert(name); - return name->segment; -} - -void name_SetSegment(Name *name, uint32_t segment) { name->segment = segment; } - -bool name_Equals(const Name *a, const Name *b) { - assert(a); - assert(b); - - if ((nameBitvector_Equals(&(a->content_name), &(b->content_name)) && - a->segment == b->segment)) - return true; - return false; -} - -int name_Compare(const Name *a, const Name *b) { - assert(a); - assert(b); - - if (a == NULL && b == NULL) { - return 0; - } - if (a == NULL) { - return -1; - } - if (b == NULL) { - return +1; - } - - int res = nameBitvector_Compare(&(a->content_name), &(b->content_name)); - - if (res != 0) { - return res; - } else { - if (a->segment < b->segment) { - return -1; - } else if (a->segment > b->segment) { - return +1; - } else { - return 0; - } - } -} - -char *name_ToString(const Name *name) { - char *output = malloc(NI_MAXHOST * 2); - address_t address; - nameBitvector_ToAddress(name_GetContentName(name), &address); - - char addr_str[NI_MAXHOST]; - int err = address_to_string(&address, addr_str, NULL); - _ASSERT(!err); - - int chars_written = - snprintf(output, NI_MAXHOST * 2, "name=%s|%u", addr_str, name->segment); - _ASSERT(chars_written > 0); - - return output; -} - -void name_setLen(Name *name, uint8_t len) { - nameBitvector_setLen(&(name->content_name), len); - name->name_hash = _computeHash(name); -} - -#ifdef WITH_POLICY -uint32_t name_GetSuffix(const Name *name) { return name->segment; } - -uint8_t name_GetLen(const Name *name) { - return nameBitvector_GetLength(&(name->content_name)); -} -#endif /* WITH_POLICY */ diff --git a/hicn-light/src/hicn/core/name.h b/hicn-light/src/hicn/core/name.h deleted file mode 100644 index 23505243b..000000000 --- a/hicn-light/src/hicn/core/name.h +++ /dev/null @@ -1,106 +0,0 @@ -/* - * Copyright (c) 2021 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 name_h -#define name_h - -#include <stdbool.h> -#include <stdlib.h> - -#include "nameBitvector.h" - -typedef struct { - NameBitvector content_name; - uint32_t segment; - uint32_t name_hash; -} Name; - -#define EMPTY_NAME \ - (Name) { .content_name = EMPTY_NAME_BITVECTOR, .segment = 0, .name_hash = 0, } - -/** - * Creates a name from packet - * - */ -void name_create_from_interest(const uint8_t *packet, Name *name); -void name_create_from_data(const uint8_t *packet, Name *name); - -/** - * returns a copy of the name - */ -void name_Copy(const Name *original, Name *copy); - -/** - * A hash value for use in hash tables - * - */ -uint32_t name_HashCode(const Name *name); - -/** - * Returns the content name without the segment value - * - */ -NameBitvector *name_GetContentName(const Name *name); - -/** - * Returns the segment value - * - */ -uint32_t name_GetSegment(const Name *name); - -/** - * Set the sequence number of the name provided - * - */ -void name_SetSegment(Name *name, uint32_t segment); - -/** - * Determine if two HicnName instances are equal. - */ -bool name_Equals(const Name *a, const Name *b); - -/** - * Compares two names and returns their ordering - * - */ -int name_Compare(const Name *a, const Name *b); - -/** - * return the name in string format (bitvector + segment number) - * - */ -char *name_ToString(const Name *name); - -/** - * @function message_setNameLen - * @abstract Sets a message name length - * @param [in] message - Interest message - * @param [in] len - Name length - */ -void name_setLen(Name *name, uint8_t len); - -/** - * Creates a name from a Address - * - */ -void name_CreateFromAddress(Name *name, int family, ip_address_t addr, - uint8_t len); - -#ifdef WITH_POLICY -uint32_t name_GetSuffix(const Name *name); -uint8_t name_GetLen(const Name *name); -#endif /* WITH_POLICY */ - -#endif // name_h diff --git a/hicn-light/src/hicn/core/nameBitvector.c b/hicn-light/src/hicn/core/nameBitvector.c deleted file mode 100644 index aa431879c..000000000 --- a/hicn-light/src/hicn/core/nameBitvector.c +++ /dev/null @@ -1,296 +0,0 @@ -/* - * Copyright (c) 2021 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 <stdint.h> -#include <stdio.h> -#include <stdlib.h> - -#include <hicn/core/messageHandler.h> -#include <hicn/core/nameBitvector.h> - -#include <hicn/util/hash.h> -#include <hicn/ctrl/hicn-light-ng.h> - -#define DEFAULT_PORT 1234 - -const uint64_t BV_SIZE = 64; -const uint64_t WIDTH = 128; -const uint64_t ONE = 0x1; - -// address b000:0000:0000:0001:c000:0000:0000:0001 is encodend as follow -// [bits[0] uint64_t ] [bits[1] unit64_t ] -// ^ ^ ^ ^ -// 63 0 127 64 -// [1000 0000 ... 0000 1011] [1000 0000 ... 0000 0011] //binary -// 1 b 1 c //hex - -void nameBitvector_CreateFromInAddr(NameBitvector *bitvector, uint32_t addr, - uint8_t len) { - assert(bitvector); - - bitvector->bits[0] = 0; - bitvector->bits[1] = 0; - - uint8_t addr_1 = (addr & 0xff000000) >> 24; - uint8_t addr_2 = (addr & 0x00ff0000) >> 16; - uint8_t addr_3 = (addr & 0x0000ff00) >> 8; - uint8_t addr_4 = (addr & 0x000000ff); - - bitvector->bits[0] = (bitvector->bits[0] | addr_4) << 8; - bitvector->bits[0] = (bitvector->bits[0] | addr_3) << 8; - bitvector->bits[0] = (bitvector->bits[0] | addr_2) << 8; - bitvector->bits[0] = (bitvector->bits[0] | addr_1); - bitvector->bits[0] = bitvector->bits[0] << 32; - - bitvector->len = len; - - bitvector->IPversion = IPv4_TYPE; -} - -void nameBitvector_CreateFromIn6Addr(NameBitvector *bitvector, - struct in6_addr *addr, uint8_t len) { - assert(addr); - assert(bitvector); - - bitvector->bits[0] = 0; - bitvector->bits[1] = 0; - - for (int i = 0; i < 8; ++i) { - bitvector->bits[0] = (bitvector->bits[0] << 8) | addr->s6_addr[i]; - } - - for (int i = 8; i < 16; ++i) { - bitvector->bits[1] = (bitvector->bits[1] << 8) | addr->s6_addr[i]; - } - - bitvector->len = len; - - bitvector->IPversion = IPv6_TYPE; -} - -void nameBitvector_Copy(const NameBitvector *original, NameBitvector *copy) { - assert(original); - assert(copy); - - copy->bits[0] = original->bits[0]; - copy->bits[1] = original->bits[1]; - copy->len = original->len; - copy->IPversion = original->IPversion; -} - -uint8_t nameBitvector_GetLength(const NameBitvector *name) { return name->len; } - -uint32_t nameBitvector_GetHash32(const NameBitvector *name) { - return hash(&name->bits, 16); -} - -bool nameBitvector_Equals(const NameBitvector *a, const NameBitvector *b) { - if (nameBitvector_Compare(a, b) == 0) return true; - return false; -} - -int nameBitvector_Compare(const NameBitvector *a, const NameBitvector *b) { - if (a == NULL && b == NULL) { - return 0; - } - if (a == NULL) { - return -1; - } - if (b == NULL) { - return +1; - } - - if (a->bits[0] < b->bits[0]) { - return -1; - } else if (a->bits[0] > b->bits[0]) { - return +1; - } else if (a->bits[1] < b->bits[1]) { - return -1; - } else if (a->bits[1] > b->bits[1]) { - return +1; - } else if (a->len < b->len) { - return -1; - } else if (a->len > b->len) { - return +1; - } else { - return 0; - } -} - -int nameBitvector_testBit(const NameBitvector *name, uint8_t pos, bool *bit) { - if (pos >= name->len || pos > (WIDTH - 1)) return -1; - - *bit = - (name->bits[pos / BV_SIZE] & (ONE << ((BV_SIZE - 1) - (pos % BV_SIZE)))); - - return 0; -} - -// TODO XXX use ffs(ll) -uint64_t _diff_bit_log2(uint64_t val) { - // base 2 log of an uint64_t. This is the same as get the position of - // the highest bit set (or most significant bit set, MSB) - uint64_t result = 0; - - if (val & 0xFFFFFFFF00000000) { - val = val >> 32; - result = result | 32; - } - if (val & 0xFFFF0000) { - val = val >> 16; - result = result | 16; - } - if (val & 0xFF00) { - val = val >> 8; - result = result | 8; - } - if (val & 0xF0) { - val = val >> 4; - result = result | 4; - } - if (val & 0xC) { - val = val >> 2; - result = result | 2; - } - if (val & 0x2) { - val = val >> 1; - result = result | 1; - } - return result; -} - -uint32_t nameBitvector_lpm(const NameBitvector *a, const NameBitvector *b) { - uint32_t limit; - uint32_t prefix_len; - if (a->len < b->len) - limit = a->len; - else - limit = b->len; - - uint64_t diff = a->bits[0] ^ b->bits[0]; - if (diff) { - prefix_len = (uint32_t)(BV_SIZE - (_diff_bit_log2(diff) + 1)); - // printf("if 1 diff = %lu plen = %d\n", diff, prefix_len); - } else { - prefix_len = BV_SIZE; - diff = a->bits[1] ^ b->bits[1]; - if (diff) { - prefix_len += (BV_SIZE - (_diff_bit_log2(diff) + 1)); - // printf("if 2 diff = %lu plen = %d\n", diff, prefix_len); - } else { - prefix_len += BV_SIZE; - } - } - - if (prefix_len < limit) return prefix_len; - return limit; -} - -void nameBitvector_clear(NameBitvector *a, uint8_t start_from) { - for (uint8_t pos = start_from; pos < WIDTH; pos++) - a->bits[pos / BV_SIZE] &= ~(ONE << ((BV_SIZE - 1) - (pos % BV_SIZE))); -} - -int nameBitvector_ToIPAddress(const NameBitvector *name, ip_prefix_t *prefix) { - if (name->IPversion == IPv4_TYPE) { - struct in_addr *addr = (struct in_addr *)(&prefix->address.v4.buffer); - prefix->family = AF_INET; - prefix->len = IPV4_ADDR_LEN_BITS; - - uint32_t tmp_addr = name->bits[0] >> 32ULL; - uint8_t addr_1 = (tmp_addr & 0xff000000) >> 24; - uint8_t addr_2 = (tmp_addr & 0x00ff0000) >> 16; - uint8_t addr_3 = (tmp_addr & 0x0000ff00) >> 8; - uint8_t addr_4 = (tmp_addr & 0x000000ff); - - addr->s_addr = 0; - addr->s_addr = (addr->s_addr | addr_4) << 8; - addr->s_addr = (addr->s_addr | addr_3) << 8; - addr->s_addr = (addr->s_addr | addr_2) << 8; - addr->s_addr = (addr->s_addr | addr_1); - - } else { - struct in6_addr *addr = (struct in6_addr *)(&prefix->address.v6.buffer); - prefix->family = AF_INET6; - prefix->len = name->len; // IPV6_ADDR_LEN_BITS; - - for (int i = 0; i < 8; i++) { - addr->s6_addr[i] = (uint8_t)((name->bits[0] >> 8 * (7 - i)) & 0xFF); - } - - int x = 0; - for (int i = 8; i < 16; ++i) { - addr->s6_addr[i] = (uint8_t)((name->bits[1] >> 8 * (7 - x)) & 0xFF); - x++; - } - } - return true; -} - -void nameBitvector_setLen(NameBitvector *name, uint8_t len) { name->len = len; } - -void nameBitvector_ToAddress(const NameBitvector *name, address_t *address) { - if (name->IPversion == IPv4_TYPE) { - struct sockaddr_in *sin = address4(address); - sin->sin_family = AF_INET; - sin->sin_port = htons(DEFAULT_PORT); - - uint32_t tmp_addr = name->bits[0] >> 32ULL; - uint8_t addr_1 = (tmp_addr & 0xff000000) >> 24; - uint8_t addr_2 = (tmp_addr & 0x00ff0000) >> 16; - uint8_t addr_3 = (tmp_addr & 0x0000ff00) >> 8; - uint8_t addr_4 = (tmp_addr & 0x000000ff); - - sin->sin_addr.s_addr = 0; - sin->sin_addr.s_addr = (sin->sin_addr.s_addr | addr_4) << 8; - sin->sin_addr.s_addr = (sin->sin_addr.s_addr | addr_3) << 8; - sin->sin_addr.s_addr = (sin->sin_addr.s_addr | addr_2) << 8; - sin->sin_addr.s_addr = (sin->sin_addr.s_addr | addr_1); - } else { - struct sockaddr_in6 *sin6 = address6(address); - sin6->sin6_family = AF_INET6; - sin6->sin6_port = htons(DEFAULT_PORT); - sin6->sin6_scope_id = 0; - sin6->sin6_flowinfo = 0; - - for (int i = 0; i < 8; i++) { - sin6->sin6_addr.s6_addr[i] = - (uint8_t)((name->bits[0] >> 8 * (7 - i)) & 0xFF); - } - - int x = 0; - for (int i = 8; i < 16; ++i) { - sin6->sin6_addr.s6_addr[i] = - (uint8_t)((name->bits[1] >> 8 * (7 - x)) & 0xFF); - x++; - } - } -} - -char *nameBitvector_ToString(const NameBitvector *name) { - char *output = malloc(WIDTH); - - address_t address; - nameBitvector_ToAddress(name, &address); - - // XXX TODO -#if 0 - sprintf(output, "prefix: %s len: %u", addressToString(packetAddr), name->len); -#else - snprintf(output, WIDTH, "%s", "ENOIMPL"); -#endif - - return output; -} diff --git a/hicn-light/src/hicn/core/nameBitvector.h b/hicn-light/src/hicn/core/nameBitvector.h deleted file mode 100644 index 549b26679..000000000 --- a/hicn-light/src/hicn/core/nameBitvector.h +++ /dev/null @@ -1,66 +0,0 @@ -/* - * Copyright (c) 2021 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 name_bitvector_h -#define name_bitvector_h - -#include <hicn/hicn.h> -#include <stdint.h> -#include <stdlib.h> - -#include "address.h" - -#define NAME_LEN 2 -typedef struct __attribute__((__packed__)) { - uint64_t bits[NAME_LEN]; - uint32_t len; - uint32_t IPversion; -} NameBitvector; -static_assert(sizeof(NameBitvector) == 24, - "Name prefix should be stored on 24 bytes"); - -#define EMPTY_NAME_BITVECTOR \ - (NameBitvector) { .bits[0] = 0, .bits[1] = 0, .len = 0, .IPversion = 0, } - -void nameBitvector_CreateFromInAddr(NameBitvector *bitvector, uint32_t addr, - uint8_t len); - -void nameBitvector_CreateFromIn6Addr(NameBitvector *bitvector, - struct in6_addr *addr, uint8_t len); - -void nameBitvector_Copy(const NameBitvector *original, NameBitvector *copy); - -uint8_t nameBitvector_GetLength(const NameBitvector *name); - -uint32_t nameBitvector_GetHash32(const NameBitvector *name); - -bool nameBitvector_Equals(const NameBitvector *a, const NameBitvector *b); - -int nameBitvector_Compare(const NameBitvector *a, const NameBitvector *b); - -int nameBitvector_testBit(const NameBitvector *name, uint8_t pos, bool *bit); - -uint32_t nameBitvector_lpm(const NameBitvector *a, const NameBitvector *b); - -void nameBitvector_clear(NameBitvector *a, uint8_t start_from); - -int nameBitvector_ToIPAddress(const NameBitvector *name, ip_prefix_t *prefix); -void nameBitvector_setLen(NameBitvector *name, uint8_t len); - -void nameBitvector_ToAddress(const NameBitvector *name, address_t *address); - -char *nameBitvector_ToString(const NameBitvector *name); - -#endif // name_bitvector_h diff --git a/hicn-light/src/hicn/core/nexthops.c b/hicn-light/src/hicn/core/nexthops.c index 190f09ab0..70089399d 100644 --- a/hicn-light/src/hicn/core/nexthops.c +++ b/hicn-light/src/hicn/core/nexthops.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -18,6 +18,8 @@ * \brief Nexthops implementation */ +#include <hicn/util/hash.h> + #include "nexthops.h" int nexthops_disable(nexthops_t *nexthops, off_t offset) { @@ -34,7 +36,6 @@ void nexthops_reset(nexthops_t *nexthops) { off_t nexthops_add(nexthops_t *nexthops, nexthop_t nexthop) { off_t id; - unsigned i, n; nexthops_enumerate(nexthops, i, n, { if (n == nexthop) return i; }); @@ -45,7 +46,6 @@ off_t nexthops_add(nexthops_t *nexthops, nexthop_t nexthop) { } off_t nexthops_remove(nexthops_t *nexthops, nexthop_t nexthop) { - unsigned i, n; nexthops_enumerate(nexthops, i, n, { if (n == nexthop) { nexthops->num_elts--; @@ -59,7 +59,6 @@ off_t nexthops_remove(nexthops_t *nexthops, nexthop_t nexthop) { } bool nexthops_contains(nexthops_t *nexthops, unsigned nexthop) { - unsigned n; nexthops_foreach(nexthops, n, { if (n == nexthop) return true; }); @@ -67,7 +66,6 @@ bool nexthops_contains(nexthops_t *nexthops, unsigned nexthop) { } off_t nexthops_find(nexthops_t *nexthops, unsigned nexthop) { - unsigned i, n; nexthops_enumerate(nexthops, i, n, { if (n == nexthop) return i; }); @@ -75,7 +73,6 @@ off_t nexthops_find(nexthops_t *nexthops, unsigned nexthop) { } unsigned nexthops_get_one(nexthops_t *nexthops) { - unsigned n; nexthops_foreach(nexthops, n, { return n; }); return INVALID_NEXTHOP; } @@ -92,8 +89,6 @@ int nexthops_select(nexthops_t *nexthops, off_t i) { void nexthops_set_priority(nexthops_t *nexthops, nexthop_t nexthop, int priority) { - unsigned i; - nexthop_t nh; nexthops_enumerate(nexthops, i, nh, { if (nexthop == nh) nexthops_set_priority_by_id(nexthops, i, priority); }); @@ -112,8 +107,6 @@ void nexthops_reset_priority_by_id(nexthops_t *nexthops, off_t i) { } void nexthops_reset_priorities(nexthops_t *nexthops) { - unsigned i; - nexthop_t nh; nexthops_enumerate(nexthops, i, nh, { (void)nh; nexthops_reset_priority(nexthops, i); @@ -121,7 +114,6 @@ void nexthops_reset_priorities(nexthops_t *nexthops) { } bool nexthops_equal(nexthops_t *a, nexthops_t *b) { - unsigned n; if (nexthops_get_len(a) != nexthops_get_len(b)) return false; nexthops_foreach(a, n, { if (!nexthops_contains(b, n)) return false; @@ -139,4 +131,19 @@ void nexthops_copy(nexthops_t *src, nexthops_t *dst) { dst->cur_elts = src->cur_elts; } +/* Adapted from Jenkins hash (commutative) */ +uint32_t nexthops_get_hash(nexthops_t *nexthops) { + uint32_t hash = 0; + + nexthops_foreach(nexthops, nh, { + hash += nh; + hash += hash << 10; + hash ^= hash >> 6; + }); + hash += hash << 3; + hash ^= hash >> 11; + hash += hash << 15; + return hash; +} + #endif /* WITH_POLICY */ diff --git a/hicn-light/src/hicn/core/nexthops.h b/hicn-light/src/hicn/core/nexthops.h index 2a7fc0b32..ff83199a6 100644 --- a/hicn-light/src/hicn/core/nexthops.h +++ b/hicn-light/src/hicn/core/nexthops.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -106,21 +106,24 @@ int nexthops_disable(nexthops_t *nexthops, off_t offset); void nexthops_reset(nexthops_t *nexthops); -#define nexthops_enumerate(NH, i, X, BODY) \ +#define nexthops_enumerate(NH, I, X, BODY) \ do { \ - for ((i) = 0; (i) < nexthops_get_len(NH); (i)++) { \ - if (nexthops_is_disabled((NH), (i))) continue; \ - X = (NH)->elts[(i)]; \ + nexthop_t X; \ + (void)X; \ + unsigned I; \ + (void)I; \ + for ((I) = 0; (I) < nexthops_get_len(NH); (I)++) { \ + if (nexthops_is_disabled((NH), (I))) continue; \ + X = (NH)->elts[(I)]; \ do { \ BODY \ } while (0); \ } \ } while (0) -#define nexthops_foreach(NH, X, BODY) \ - do { \ - unsigned _nexthops_var(i); \ - nexthops_enumerate((NH), _nexthops_var(i), (X), {BODY}); \ +#define nexthops_foreach(NH, X, BODY) \ + do { \ + nexthops_enumerate((NH), _nexthops_var(i), X, {BODY}); \ } while (0) off_t nexthops_add(nexthops_t *nexthops, nexthop_t nexthop); @@ -173,4 +176,6 @@ void nexthops_copy(nexthops_t *src, nexthops_t *dst); #endif /* WITH_POLICY */ +uint32_t nexthops_get_hash(nexthops_t *nexthops); + #endif /* HICNLIGHT_NEXTHOPS_H */ diff --git a/hicn-light/src/hicn/core/packet_cache.c b/hicn-light/src/hicn/core/packet_cache.c index 8bd188c8b..9d0b041c3 100644 --- a/hicn-light/src/hicn/core/packet_cache.c +++ b/hicn-light/src/hicn/core/packet_cache.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -16,48 +16,121 @@ /** * \file packet_cache.c * \brief Implementation of hICN packet cache + * + * _get_suffixes : first level lookup to return the suffixes + * + * _remove_suffix : Remove suffix from the two level packet cache structure + * + * __add_suffix : Add a packet cache entry in the second level of the + * two-level data structure _add_suffix : Add a packet cache entry in the both + * the first and second level of the two-level data tructure (helper) + * + * __get_suffix : Lookup in the second level of the packet cache + * + * _get_suffix : Lookup in both the first and second levels of the packet cache + * + * ---- + * + * pkt_cache_save_suffixes_for_prefix : always done at packet reception to keep + * the latest suffixes + * + * pkt_cache_reset_suffixes_for_prefix + * + * ---- + * + * pkt_cache_allocate + * + * pkt_cache_add_to_index + * + * pkt_cache_remove_from_index + * + * pkt_cache_pit_remove_entry + * + * pkt_cache_cs_remove_entry + * + * pkt_cache_add_to_pit + * pkt_cache_add_to_cs + * + * _pkt_cache_add_to_pit + * used by pkt_cache_add_to_pit + * plt_cache_update_pit + * _pkt_cache_add_to_cs + * + * pkt_cache_pit_to_cs + * pkt_cache_cs_to_pit + * + * pkt_cache_update_pit : when an interest expired + * pkt_cache_update_cs + * + * pkt_cache_try_aggregate_in_pit + * + * + * */ #include "packet_cache.h" +const char *_pkt_cache_verdict_str[] = { +#define _(x) [PKT_CACHE_VERDICT_##x] = #x, + foreach_kh_verdict +#undef _ +}; + /****************************************************************************** * Low-level operations on the hash table ******************************************************************************/ +/** + * Free the two level packet cache structure (helper) + */ void _prefix_map_free(kh_pkt_cache_prefix_t *prefix_to_suffixes) { - const NameBitvector *key; + const hicn_name_prefix_t *key; kh_pkt_cache_suffix_t *value; kh_foreach(prefix_to_suffixes, key, value, { - free((NameBitvector *)key); + //(void)key; + free((hicn_name_prefix_t *)key); kh_destroy_pkt_cache_suffix(value); }); kh_destroy_pkt_cache_prefix(prefix_to_suffixes); } +/** + * Perform the first level lookup to return the suffixes (helper) + */ kh_pkt_cache_suffix_t *_get_suffixes(kh_pkt_cache_prefix_t *prefix_to_suffixes, - const NameBitvector *prefix) { + const hicn_name_prefix_t *prefix, + bool create) { khiter_t k = kh_get_pkt_cache_prefix(prefix_to_suffixes, prefix); - // Return suffixes found + /* Return suffixes if found... */ if (k != kh_end(prefix_to_suffixes)) { kh_pkt_cache_suffix_t *suffixes = kh_val(prefix_to_suffixes, k); return suffixes; } + if (!create) return NULL; + + /* ... otherwise populate the first level and return the newly added entry. + */ kh_pkt_cache_suffix_t *suffixes = kh_init_pkt_cache_suffix(); - NameBitvector *nb_copy = (NameBitvector *)malloc(sizeof(NameBitvector)); - *nb_copy = *prefix; + + hicn_name_prefix_t *prefix_copy = malloc(sizeof(hicn_name_prefix_t)); + *prefix_copy = *prefix; int rc; - k = kh_put_pkt_cache_prefix(prefix_to_suffixes, nb_copy, &rc); + k = kh_put_pkt_cache_prefix(prefix_to_suffixes, prefix_copy, &rc); assert(rc == KH_ADDED || rc == KH_RESET); kh_value(prefix_to_suffixes, k) = suffixes; return suffixes; } +/** + * Remove suffix from the two level packet cache structure (helper) + */ void _remove_suffix(kh_pkt_cache_prefix_t *prefixes, - const NameBitvector *prefix, uint32_t suffix) { - kh_pkt_cache_suffix_t *suffixes = _get_suffixes(prefixes, prefix); + const hicn_name_prefix_t *prefix, + const hicn_name_suffix_t suffix) { + kh_pkt_cache_suffix_t *suffixes = _get_suffixes(prefixes, prefix, false); assert(suffixes != NULL); khiter_t k = kh_get_pkt_cache_suffix(suffixes, suffix); @@ -67,60 +140,90 @@ void _remove_suffix(kh_pkt_cache_prefix_t *prefixes, // TODO(eloparco): Remove prefix if no associated suffixes? } -void __add_suffix(kh_pkt_cache_suffix_t *suffixes, uint32_t suffix, +/** + * Add a packet cache entry in the second level of the two-level data structure + * (helper) + */ +void __add_suffix(kh_pkt_cache_suffix_t *suffixes, hicn_name_suffix_t suffix, unsigned val) { + // INFO("suffix add suffixes=%p suffix=%d val=%d", suffixes, suffix, val); int rc; khiter_t k = kh_put_pkt_cache_suffix(suffixes, suffix, &rc); assert(rc == KH_ADDED || rc == KH_RESET); kh_value(suffixes, k) = val; } -void _add_suffix(kh_pkt_cache_prefix_t *prefixes, const NameBitvector *prefix, - uint32_t suffix, unsigned val) { - kh_pkt_cache_suffix_t *suffixes = _get_suffixes(prefixes, prefix); +/** + * Add a packet cache entry in the both the first and second level of the + * two-level data tructure (helper) + */ +void _add_suffix(kh_pkt_cache_prefix_t *prefixes, + const hicn_name_prefix_t *prefix, + const hicn_name_suffix_t suffix, unsigned val) { + kh_pkt_cache_suffix_t *suffixes = _get_suffixes(prefixes, prefix, true); assert(suffixes != NULL); __add_suffix(suffixes, suffix, val); } -unsigned __get_suffix(kh_pkt_cache_suffix_t *suffixes, uint32_t suffix, - int *rc) { - *rc = KH_FOUND; +/** + * Lookup in the second level of the packet cache (helper) + */ +unsigned __get_suffix(kh_pkt_cache_suffix_t *suffixes, + hicn_name_suffix_t suffix) { khiter_t k = kh_get_pkt_cache_suffix(suffixes, suffix); // Not Found if (k == kh_end(suffixes)) { - *rc = KH_NOT_FOUND; - return -1; + return HICN_INVALID_SUFFIX; } unsigned index = kh_val(suffixes, k); return index; } +unsigned _get_suffix(kh_pkt_cache_prefix_t *prefixes, + const hicn_name_prefix_t *prefix, + hicn_name_suffix_t suffix) { + /* create is false as this function is always called by lookup */ + kh_pkt_cache_suffix_t *suffixes = _get_suffixes(prefixes, prefix, false); + if (!suffixes) { + return HICN_INVALID_SUFFIX; + } + return __get_suffix(suffixes, suffix); +} + +/** + * Lookup in both the first and second levels of the packet cache (helper) + */ +unsigned _get_suffix_from_name(kh_pkt_cache_prefix_t *prefixes, + const hicn_name_t *name) { + const hicn_name_prefix_t *prefix = hicn_name_get_prefix(name); + const hicn_name_suffix_t suffix = hicn_name_get_suffix(name); + + return _get_suffix(prefixes, prefix, suffix); +} + void pkt_cache_save_suffixes_for_prefix(pkt_cache_t *pkt_cache, - const NameBitvector *prefix) { + const hicn_name_prefix_t *prefix) { // Cached prefix matches the current one - if (nameBitvector_Compare(&pkt_cache->cached_prefix, prefix) == 0) return; + if (hicn_name_prefix_equals(&pkt_cache->cached_prefix, prefix)) return; + + char buf[MAXSZ_HICN_PREFIX]; + hicn_name_prefix_snprintf(buf, MAXSZ_HICN_PREFIX, &pkt_cache->cached_prefix); + hicn_name_prefix_snprintf(buf, MAXSZ_HICN_PREFIX, prefix); // Update cached prefix information pkt_cache->cached_prefix = *prefix; pkt_cache->cached_suffixes = - _get_suffixes(pkt_cache->prefix_to_suffixes, prefix); + _get_suffixes(pkt_cache->prefix_to_suffixes, prefix, true); // XXX + // } void pkt_cache_reset_suffixes_for_prefix(pkt_cache_t *pkt_cache) { pkt_cache->cached_suffixes = NULL; } -unsigned _get_suffix(kh_pkt_cache_prefix_t *prefixes, - const NameBitvector *prefix, uint32_t suffix, int *rc) { - kh_pkt_cache_suffix_t *suffixes = _get_suffixes(prefixes, prefix); - assert(suffixes != NULL); - - return __get_suffix(suffixes, suffix, rc); -} - /****************************************************************************** * Public API ******************************************************************************/ @@ -136,7 +239,7 @@ pkt_cache_t *pkt_cache_create(size_t cs_size) { pkt_cache->prefix_to_suffixes = kh_init_pkt_cache_prefix(); pool_init(pkt_cache->entries, DEFAULT_PKT_CACHE_SIZE, 0); - pkt_cache->cached_prefix = EMPTY_NAME_BITVECTOR; + pkt_cache->cached_prefix = HICN_NAME_PREFIX_EMPTY; pkt_cache->cached_suffixes = NULL; return pkt_cache; @@ -157,50 +260,71 @@ void pkt_cache_free(pkt_cache_t *pkt_cache) { } kh_pkt_cache_suffix_t *pkt_cache_get_suffixes(const pkt_cache_t *pkt_cache, - const NameBitvector *prefix) { - return _get_suffixes(pkt_cache->prefix_to_suffixes, prefix); + const hicn_name_prefix_t *prefix, + bool create) { + return _get_suffixes(pkt_cache->prefix_to_suffixes, prefix, create); } -pkt_cache_entry_t *pkt_cache_allocate(pkt_cache_t *pkt_cache, - const Name *name) { +pkt_cache_entry_t *pkt_cache_allocate(pkt_cache_t *pkt_cache) { pkt_cache_entry_t *entry = NULL; pool_get(pkt_cache->entries, entry); - if (!entry) return NULL; + assert(entry); + return entry; +} +void pkt_cache_add_to_index(const pkt_cache_t *pkt_cache, + const pkt_cache_entry_t *entry) { off_t id = entry - pkt_cache->entries; + /* It is important that the name used for the index is the one in the packet + * cache entry, which is common for PIT and CS + */ + const hicn_name_t *name = &entry->name; + if (pkt_cache->cached_suffixes) { - __add_suffix(pkt_cache->cached_suffixes, name_GetSegment(name), + __add_suffix(pkt_cache->cached_suffixes, hicn_name_get_suffix(name), (unsigned int)id); } else { - _add_suffix(pkt_cache->prefix_to_suffixes, name_GetContentName(name), - name_GetSegment(name), (unsigned int)id); + _add_suffix(pkt_cache->prefix_to_suffixes, hicn_name_get_prefix(name), + hicn_name_get_suffix(name), (unsigned int)id); } +} - return entry; +/** + * Remove a name pointer to the packet cache index (helper) + */ +void pkt_cache_remove_from_index(const pkt_cache_t *pkt_cache, + const hicn_name_t *name) { + _remove_suffix(pkt_cache->prefix_to_suffixes, hicn_name_get_prefix(name), + hicn_name_get_suffix(name)); + +// TODO +#if 0 + khiter_t k = kh_get_pkt_cache_name(pkt_cache->index_by_name, name); + assert(k != kh_end(pkt_cache->index_by_name)); + kh_del(pkt_cache_name, pkt_cache->index_by_name, k); +#endif } pit_t *pkt_cache_get_pit(pkt_cache_t *pkt_cache) { return pkt_cache->pit; } cs_t *pkt_cache_get_cs(pkt_cache_t *pkt_cache) { return pkt_cache->cs; } -pkt_cache_entry_t *pkt_cache_lookup(pkt_cache_t *pkt_cache, const Name *name, +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) { - int rc; - - unsigned index = -1; + unsigned index = HICN_INVALID_SUFFIX; if (pkt_cache->cached_suffixes) { index = - __get_suffix(pkt_cache->cached_suffixes, name_GetSegment(name), &rc); + __get_suffix(pkt_cache->cached_suffixes, hicn_name_get_suffix(name)); } else { - index = _get_suffix(pkt_cache->prefix_to_suffixes, - name_GetContentName(name), name_GetSegment(name), &rc); + index = _get_suffix_from_name(pkt_cache->prefix_to_suffixes, name); } - if (rc == KH_NOT_FOUND) { + if (index == HICN_INVALID_SUFFIX) { *lookup_result = PKT_CACHE_LU_NONE; return NULL; } @@ -237,9 +361,10 @@ void pkt_cache_cs_remove_entry(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, off_t msgbuf_id = entry->u.cs_entry.msgbuf_id; msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); - const Name *name = msgbuf_get_name(msgbuf); - _remove_suffix(pkt_cache->prefix_to_suffixes, name_GetContentName(name), - name_GetSegment(name)); + // XXX const hicn_name_t *name = msgbuf_get_name(msgbuf); + _remove_suffix(pkt_cache->prefix_to_suffixes, + hicn_name_get_prefix(&entry->name), + hicn_name_get_suffix(&entry->name)); // Do not update the LRU cache for evicted entries if (!is_evicted) cs_vft[pkt_cache->cs->type]->remove_entry(pkt_cache, entry); @@ -248,28 +373,34 @@ void pkt_cache_cs_remove_entry(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, pool_put(pkt_cache->entries, entry); WITH_DEBUG({ - char *name_str = name_ToString(msgbuf_get_name(msgbuf)); - DEBUG("Packet %s removed from CS", name_str); - free(name_str); + char buf[MAXSZ_HICN_NAME]; + int rc = hicn_name_snprintf(buf, MAXSZ_HICN_NAME, &entry->name); + if (rc < 0 || rc >= MAXSZ_HICN_NAME) + snprintf(buf, MAXSZ_HICN_NAME, "%s", "(error)"); + DEBUG("Packet %s removed from CS", buf); }) msgbuf_pool_release(msgbuf_pool, &msgbuf); } void pkt_cache_pit_remove_entry(pkt_cache_t *pkt_cache, - pkt_cache_entry_t *entry, const Name *name) { + pkt_cache_entry_t *entry) { assert(pkt_cache); assert(entry); assert(entry->entry_type == PKT_CACHE_PIT_TYPE); - _remove_suffix(pkt_cache->prefix_to_suffixes, name_GetContentName(name), - name_GetSegment(name)); + const hicn_name_t *name = &entry->name; + _remove_suffix(pkt_cache->prefix_to_suffixes, hicn_name_get_prefix(name), + hicn_name_get_suffix(name)); + pool_put(pkt_cache->entries, entry); WITH_DEBUG({ - char *name_str = name_ToString(name); - DEBUG("Packet %s removed from PIT", name_str); - free(name_str); + char buf[MAXSZ_HICN_NAME]; + int rc = hicn_name_snprintf(buf, MAXSZ_HICN_NAME, name); + if (rc < 0 || rc >= MAXSZ_HICN_NAME) + snprintf(buf, MAXSZ_HICN_NAME, "%s", "(error)"); + DEBUG("Packet %s removed from PIT", buf); }) } @@ -279,8 +410,9 @@ void _pkt_cache_add_to_cs(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, entry->u.cs_entry = (cs_entry_t){.msgbuf_id = msgbuf_id, .lru = {.prev = INVALID_ENTRY_ID, .next = INVALID_ENTRY_ID}}; - entry->create_ts = ticks_now(); - entry->expire_ts = ticks_now() + msgbuf_get_data_expiry_time(msgbuf); + Ticks now = ticks_now(); + entry->create_ts = now; + entry->expire_ts = now + msgbuf_get_data_expiry_time(msgbuf); entry->has_expire_ts = true; entry->entry_type = PKT_CACHE_CS_TYPE; @@ -299,18 +431,21 @@ void _pkt_cache_add_to_cs(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, msgbuf_pool_acquire(msgbuf); } -void pkt_cache_pit_to_cs(pkt_cache_t *pkt_cache, - pkt_cache_entry_t *interest_entry, - msgbuf_pool_t *msgbuf_pool, msgbuf_t *data_msgbuf, - off_t data_msgbuf_id, off_t entry_id) { +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) { assert(pkt_cache); - assert(interest_entry); - assert(interest_entry->entry_type == PKT_CACHE_PIT_TYPE); + assert(entry); + assert(entry->entry_type == PKT_CACHE_PIT_TYPE); - _pkt_cache_add_to_cs(pkt_cache, interest_entry, msgbuf_pool, data_msgbuf, - data_msgbuf_id, entry_id); + _pkt_cache_add_to_cs(pkt_cache, entry, msgbuf_pool, msgbuf, msgbuf_id, + entry_id); } +/** + * entry : newly allocated cache entry + * msgbuf : used for name, ingress connection id and lifetime + */ void _pkt_cache_add_to_pit(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, const msgbuf_t *msgbuf) { entry->u.pit_entry = (pit_entry_t){ @@ -366,11 +501,13 @@ void pkt_cache_update_cs(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, pkt_cache_entry_t *pkt_cache_add_to_pit(pkt_cache_t *pkt_cache, const msgbuf_t *msgbuf, - const Name *name) { + const hicn_name_t *name) { assert(pkt_cache); - pkt_cache_entry_t *entry = pkt_cache_allocate(pkt_cache, name); + pkt_cache_entry_t *entry = pkt_cache_allocate(pkt_cache); + entry->name = *name; _pkt_cache_add_to_pit(pkt_cache, entry, msgbuf); + pkt_cache_add_to_index(pkt_cache, entry); return entry; } @@ -379,12 +516,13 @@ pkt_cache_entry_t *pkt_cache_add_to_cs(pkt_cache_t *pkt_cache, msgbuf_t *msgbuf, off_t msgbuf_id) { assert(pkt_cache); - pkt_cache_entry_t *entry = - pkt_cache_allocate(pkt_cache, msgbuf_get_name(msgbuf)); + pkt_cache_entry_t *entry = pkt_cache_allocate(pkt_cache); + const hicn_name_t *name = msgbuf_get_name(msgbuf); + entry->name = *name; off_t entry_id = pkt_cache_get_entry_id(pkt_cache, entry); _pkt_cache_add_to_cs(pkt_cache, entry, msgbuf_pool, msgbuf, msgbuf_id, entry_id); - + pkt_cache_add_to_index(pkt_cache, entry); return entry; } @@ -404,7 +542,8 @@ void pkt_cache_update_pit(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, bool pkt_cache_try_aggregate_in_pit(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, - const msgbuf_t *msgbuf, const Name *name) { + const msgbuf_t *msgbuf, + const hicn_name_t *name) { assert(pkt_cache); assert(entry); assert(entry->entry_type == PKT_CACHE_PIT_TYPE); @@ -422,15 +561,17 @@ bool pkt_cache_try_aggregate_in_pit(pkt_cache_t *pkt_cache, if (is_aggregated) pit_entry_ingress_add(pit_entry, connection_id); WITH_DEBUG({ - char *name_str = name_ToString(name); + char buf[MAXSZ_HICN_NAME]; + int rc = hicn_name_snprintf(buf, MAXSZ_HICN_NAME, msgbuf_get_name(msgbuf)); + if (rc < 0 || rc >= MAXSZ_HICN_NAME) + snprintf(buf, MAXSZ_HICN_NAME, "%s", "(error)"); if (is_aggregated) { - DEBUG("Interest %s already existing (expiry %lu): aggregate", name_str, + DEBUG("Interest %s already existing (expiry %lu): aggregate", buf, entry->expire_ts); } else { - DEBUG("Interest %s already existing (expiry %lu): retransmit", name_str, + DEBUG("Interest %s already existing (expiry %lu): retransmit", buf, entry->expire_ts); } - free(name_str); }) return is_aggregated; @@ -445,7 +586,7 @@ nexthops_t *pkt_cache_on_data(pkt_cache_t *pkt_cache, assert(msgbuf_id_is_valid(msgbuf_id)); msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); - assert(msgbuf_get_type(msgbuf) == MSGBUF_TYPE_DATA); + assert(msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_DATA); *wrong_egress = false; off_t entry_id; @@ -487,7 +628,7 @@ nexthops_t *pkt_cache_on_data(pkt_cache_t *pkt_cache, entry_id); *verdict = PKT_CACHE_VERDICT_FORWARD_DATA; } else { - pkt_cache_pit_remove_entry(pkt_cache, entry, msgbuf_get_name(msgbuf)); + pkt_cache_pit_remove_entry(pkt_cache, entry); *verdict = PKT_CACHE_VERDICT_CLEAR_DATA; } @@ -503,7 +644,7 @@ nexthops_t *pkt_cache_on_data(pkt_cache_t *pkt_cache, entry_id); *verdict = PKT_CACHE_VERDICT_STORE_DATA; } else { - pkt_cache_pit_remove_entry(pkt_cache, entry, msgbuf_get_name(msgbuf)); + pkt_cache_pit_remove_entry(pkt_cache, entry); *verdict = PKT_CACHE_VERDICT_CLEAR_DATA; } return NULL; @@ -543,12 +684,13 @@ nexthops_t *pkt_cache_on_data(pkt_cache_t *pkt_cache, 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 Name *name, bool is_serve_from_cs_enabled) { + const hicn_name_t *name, + bool is_serve_from_cs_enabled) { assert(pkt_cache); assert(msgbuf_id_is_valid(msgbuf_id)); msgbuf_t *msgbuf = msgbuf_pool_at(msgbuf_pool, msgbuf_id); - assert(msgbuf_get_type(msgbuf) == MSGBUF_TYPE_INTEREST); + assert(msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_INTEREST); off_t entry_id; pkt_cache_lookup_t lookup_result; @@ -628,7 +770,7 @@ void pkt_cache_cs_clear(pkt_cache_t *pkt_cache) { }); // Reset cached prefix - pkt_cache->cached_prefix = EMPTY_NAME_BITVECTOR; + pkt_cache->cached_prefix = HICN_NAME_PREFIX_EMPTY; pkt_cache->cached_suffixes = NULL; // Re-create CS diff --git a/hicn-light/src/hicn/core/packet_cache.h b/hicn-light/src/hicn/core/packet_cache.h index 47926fcdc..dcbc20c7d 100644 --- a/hicn-light/src/hicn/core/packet_cache.h +++ b/hicn-light/src/hicn/core/packet_cache.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -69,6 +69,10 @@ typedef enum { #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) \ @@ -83,10 +87,12 @@ typedef enum { } pkt_cache_lookup_t; KHASH_MAP_INIT_INT(pkt_cache_suffix, unsigned); -KHASH_INIT(pkt_cache_prefix, const NameBitvector *, kh_pkt_cache_suffix_t *, 1, - nameBitvector_GetHash32, nameBitvector_Equals); +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; @@ -109,7 +115,7 @@ typedef struct { // Cached prefix info to avoid double lookups, // used for both single interest speculation and interest manifest - NameBitvector cached_prefix; + hicn_name_prefix_t cached_prefix; kh_pkt_cache_suffix_t *cached_suffixes; } pkt_cache_t; @@ -123,12 +129,29 @@ 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 msgbuf pool data structure to use. + * @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 Name to use + * @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, const Name *name); +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. @@ -150,8 +173,8 @@ 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. + * @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); @@ -170,13 +193,13 @@ size_t pkt_cache_get_size(pkt_cache_t *pkt_cache); 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) + * @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 + * @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); @@ -203,8 +226,8 @@ size_t pkt_cache_get_pit_size(pkt_cache_t *pkt_cache); #define pkt_cache_at(pkt_cache, i) (pkt_cache->entries + i) /** - * @brief Retrieve from the packet cache the entry associated with the specified - * name. + * @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 @@ -217,7 +240,8 @@ size_t pkt_cache_get_pit_size(pkt_cache_t *pkt_cache); * 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 Name *name, +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, @@ -260,11 +284,10 @@ void pkt_cache_cs_remove_entry(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, * @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 PITe entry to remove - * @param[in] name Name associated with the PIT entry to remove + * @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, const Name *name); + pkt_cache_entry_t *entry); /** * @brief Convert a PIT entry to a CS entry. @@ -311,7 +334,7 @@ void pkt_cache_cs_to_pit(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, */ pkt_cache_entry_t *pkt_cache_add_to_pit(pkt_cache_t *pkt_cache, const msgbuf_t *msgbuf, - const Name *name); + const hicn_name_t *name); /** * @brief Add CS entry to the packet cache. @@ -329,7 +352,8 @@ pkt_cache_entry_t *pkt_cache_add_to_cs(pkt_cache_t *pkt_cache, msgbuf_t *msgbuf, off_t msgbuf_id); /** - * @brief Update PIT entry in the packet cache in case of an expired PIT entry. + * @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 @@ -371,7 +395,8 @@ void pkt_cache_update_cs(pkt_cache_t *pkt_cache, msgbuf_pool_t *msgbuf_pool, */ bool pkt_cache_try_aggregate_in_pit(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, - const msgbuf_t *msgbuf, const Name *name); + const msgbuf_t *msgbuf, + const hicn_name_t *name); /** * @brief Cache prefix info (prefix + associated suffixes) to speed up lookups. @@ -380,7 +405,7 @@ bool pkt_cache_try_aggregate_in_pit(pkt_cache_t *pkt_cache, * @param[in] prefix Name prefix to cache */ void pkt_cache_save_suffixes_for_prefix(pkt_cache_t *pkt_cache, - const NameBitvector *prefix); + const hicn_name_prefix_t *prefix); /** * @brief Reset cached prefix info to force double lookups. @@ -393,7 +418,8 @@ void pkt_cache_reset_suffixes_for_prefix(pkt_cache_t *pkt_cache); /** * @brief Handle data packet reception. - * @details Perform packet cache lookup and execute operations based on it. If: + * @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) @@ -409,7 +435,8 @@ nexthops_t *pkt_cache_on_data(pkt_cache_t *pkt_cache, /** * @brief Handle interest packet reception. - * @details Perform packet cache lookup and execute operations based on it. If: + * @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; @@ -419,23 +446,28 @@ nexthops_t *pkt_cache_on_data(pkt_cache_t *pkt_cache, 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 Name *name, bool is_serve_from_cs_enabled); + 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, uint32_t suffix, - int *rc); +unsigned __get_suffix(kh_pkt_cache_suffix_t *suffixes, + hicn_name_suffix_t suffix); unsigned _get_suffix(kh_pkt_cache_prefix_t *prefixes, - const NameBitvector *prefix, uint32_t suffix, int *rc); -void __add_suffix(kh_pkt_cache_suffix_t *suffixes, uint32_t suffix, + const hicn_name_prefix_t *prefix, + hicn_name_suffix_t suffix); +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 NameBitvector *prefix, - uint32_t suffix, unsigned val); +void _add_suffix(kh_pkt_cache_prefix_t *prefixes, + const hicn_name_prefix_t *prefix, hicn_name_suffix_t suffix, + unsigned val); void _remove_suffix(kh_pkt_cache_prefix_t *prefixes, - const NameBitvector *prefix, uint32_t suffix); + const hicn_name_prefix_t *prefix, + hicn_name_suffix_t suffix); 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 NameBitvector *prefix); + const hicn_name_prefix_t *prefix, + bool create); #endif /************** Content Store *****************************/ diff --git a/hicn-light/src/hicn/core/policy_stats.c b/hicn-light/src/hicn/core/policy_stats.c index 1acbccf69..470e74a24 100644 --- a/hicn-light/src/hicn/core/policy_stats.c +++ b/hicn-light/src/hicn/core/policy_stats.c @@ -1,3 +1,18 @@ +/* + * Copyright (c) 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. + */ + #ifdef WITH_POLICY_STATS // This has to be included first because of _GNU_SOURCE @@ -24,7 +39,6 @@ static int policy_stats_mgr_tick(void* mgr_arg, int fd, void* data) { /* Loop over FIB entries to compute statistics from counters */ const fib_t* fib = forwarder_get_fib(mgr->forwarder); - fib_entry_t* entry; fib_foreach_entry(fib, entry, { policy_stats_update(&entry->policy_stats, &entry->policy_counters, now); @@ -59,7 +73,6 @@ void policy_stats_on_retransmission(const policy_stats_mgr_t* mgr, policy_counters_t* counters, const nexthops_t* nexthops) { connection_table_t* table = forwarder_get_connection_table(mgr->forwarder); - unsigned nexthop; nexthops_foreach(nexthops, nexthop, { #ifdef WITH_POLICY const connection_t* conn = connection_table_at(table, nexthop); @@ -97,7 +110,6 @@ void policy_stats_on_data(const policy_stats_mgr_t* mgr, policy_stats_t* stats, size_t msg_size = msgbuf_get_len(msgbuf); - unsigned nexthop; nexthops_foreach(nexthops, nexthop, { #ifdef WITH_POLICY const connection_t* conn = connection_table_at(table, nexthop); @@ -121,7 +133,6 @@ void policy_stats_on_timeout(const policy_stats_mgr_t* mgr, #ifdef WITH_POLICY connection_table_t* table = forwarder_get_connection_table(mgr->forwarder); - unsigned nexthop; nexthops_foreach(nexthops, nexthop, { const connection_t* conn = connection_table_at(table, nexthop); if (!conn) continue; diff --git a/hicn-light/src/hicn/core/strategy_vft.h b/hicn-light/src/hicn/core/strategy_vft.h index 0256cba57..55e61db17 100644 --- a/hicn-light/src/hicn/core/strategy_vft.h +++ b/hicn-light/src/hicn/core/strategy_vft.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2021 Cisco and/or its affiliates. + * 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: @@ -24,13 +24,11 @@ #include "../strategies/best_path.h" #include "../strategies/load_balancer.h" -#include "../strategies/low_latency.h" #include "../strategies/random.h" #include "../strategies/replication.h" typedef union { strategy_load_balancer_options_t load_balancer; - strategy_low_latency_options_t low_latency; strategy_random_options_t random; strategy_replication_options_t replication; strategy_bestpath_options_t bestpath; @@ -42,7 +40,6 @@ typedef struct { #endif /* WITH_POLICY */ union { strategy_load_balancer_nexthop_state_t load_balancer; - strategy_low_latency_nexthop_state_t low_latency; strategy_random_nexthop_state_t random; strategy_replication_nexthop_state_t replication; strategy_bestpath_nexthop_state_t bestpath; @@ -58,7 +55,6 @@ typedef struct { typedef union { strategy_load_balancer_state_t load_balancer; - strategy_low_latency_state_t low_latency; strategy_random_state_t random; strategy_replication_state_t replication; strategy_bestpath_state_t bestpath; diff --git a/hicn-light/src/hicn/core/subscription.c b/hicn-light/src/hicn/core/subscription.c index ad4006531..fb954a245 100644 --- a/hicn-light/src/hicn/core/subscription.c +++ b/hicn-light/src/hicn/core/subscription.c @@ -17,12 +17,6 @@ bool topics_contains(hc_topics_t topic_list, hc_topic_t topic) { #define topic_is_set(topic_list, topic_index) \ ((topic_list) & (1 << (topic_index))) -const char *event_str[] = { -#define _(x) [EVENT_##x] = #x, - foreach_event_type -#undef _ -}; - /*----------------------------------------------------------------------------* * Subscriptions *----------------------------------------------------------------------------*/ @@ -56,13 +50,13 @@ int subscription_table_add_topics_for_connection( int ret = vector_push(subscriptions->table[topic_index], connection_id); if (ret < 0) { ERROR("Unable to perform subscription for connection %d, topic %s", - connection_id, object_str(topic_index)); + connection_id, object_type_str(topic_index)); return -1; } if (num_duplicates > 0) { DEBUG("Connection %d had already a subscription for topic %s", - connection_id, object_str(topic_index)); + connection_id, object_type_str(topic_index)); is_subscription_already_present = true; } } @@ -111,14 +105,14 @@ unsigned *subscription_table_get_connections_for_topic( } void subscription_table_print(subscription_table_t *subscriptions) { - for (int topic_index = OBJECT_UNDEFINED + 1; topic_index < NUM_TOPICS; + for (int topic_index = OBJECT_TYPE_UNDEFINED + 1; topic_index < NUM_TOPICS; topic_index++) { printf("topic %s (%lu subscription/s) from connection/s: [ ", - object_str(topic_index), + object_type_str(topic_index), (unsigned long)vector_len(subscriptions->table[topic_index])); unsigned *connection_id; vector_foreach(subscriptions->table[topic_index], connection_id, { printf("%d ", *connection_id); }); printf("]\n"); } -}
\ No newline at end of file +} |