From 6ee6b65ef03f8a479cccb2ae04e6b156f309f045 Mon Sep 17 00:00:00 2001 From: "Enrico Loparco (eloparco)" Date: Thu, 8 Sep 2022 12:18:09 +0000 Subject: feat(slab): add slab allocator to store hashtables' keys Ref: HICN-777 Signed-off-by: Enrico Loparco (eloparco) Change-Id: Ibbd5c5e73cfd2f6adf757f7248dff8a933515d21 --- ctrl/libhicnctrl/src/modules/hicn_light.c | 2 +- hicn-light/src/hicn/cli/hicns.c | 2 +- hicn-light/src/hicn/config/configuration.c | 23 ++- hicn-light/src/hicn/core/connection_table.c | 38 ++-- hicn-light/src/hicn/core/connection_table.h | 3 + hicn-light/src/hicn/core/forwarder.c | 11 +- hicn-light/src/hicn/core/listener_table.c | 38 ++-- hicn-light/src/hicn/core/listener_table.h | 3 + hicn-light/src/hicn/core/packet_cache.c | 61 ++++--- hicn-light/src/hicn/core/packet_cache.h | 14 +- hicn-light/src/hicn/test/test-configuration.cc | 1 + hicn-light/src/hicn/test/test-connection_table.cc | 8 +- hicn-light/src/hicn/test/test-listener_table.cc | 8 +- hicn-light/src/hicn/test/test-packet_cache.cc | 33 ++-- lib/includes/CMakeLists.txt | 2 +- lib/includes/hicn/util/log.h | 15 +- lib/includes/hicn/util/slab.h | 126 ++++++++++++++ lib/includes/hicn/util/sstrncpy.h | 1 + lib/src/CMakeLists.txt | 1 + lib/src/test/CMakeLists.txt | 1 + lib/src/test/test_khash.cc | 4 +- lib/src/test/test_slab.cc | 148 ++++++++++++++++ lib/src/util/slab.c | 203 ++++++++++++++++++++++ 23 files changed, 637 insertions(+), 109 deletions(-) create mode 100644 lib/includes/hicn/util/slab.h create mode 100644 lib/src/test/test_slab.cc create mode 100644 lib/src/util/slab.c diff --git a/ctrl/libhicnctrl/src/modules/hicn_light.c b/ctrl/libhicnctrl/src/modules/hicn_light.c index 1af6c79e2..658043b7f 100644 --- a/ctrl/libhicnctrl/src/modules/hicn_light.c +++ b/ctrl/libhicnctrl/src/modules/hicn_light.c @@ -1155,7 +1155,7 @@ static ssize_t hicnlight_prepare(hc_sock_t *sock, hc_request_t *request, */ static int hicnlight_process(hc_sock_t *sock, size_t count) { hc_sock_light_data_t *s = (hc_sock_light_data_t *)sock->data; - int rc; + int rc = -99; if (count > 0) s->woff += count; diff --git a/hicn-light/src/hicn/cli/hicns.c b/hicn-light/src/hicn/cli/hicns.c index fa668062d..c03fa8599 100644 --- a/hicn-light/src/hicn/cli/hicns.c +++ b/hicn-light/src/hicn/cli/hicns.c @@ -58,7 +58,7 @@ int shell(hc_sock_t *s) { hc_command_t command = {0}; char *pos; - if ((pos = strchr(line, '\n')) != NULL) { + if (line != NULL && (pos = strchr(line, '\n')) != NULL) { *pos = '\0'; } else { fprintf(stderr, "Error while reading command.\n"); diff --git a/hicn-light/src/hicn/config/configuration.c b/hicn-light/src/hicn/config/configuration.c index f38c4f22f..b7e931e53 100644 --- a/hicn-light/src/hicn/config/configuration.c +++ b/hicn-light/src/hicn/config/configuration.c @@ -46,6 +46,8 @@ #include #include #include +#include +#include #include "configuration.h" @@ -63,6 +65,10 @@ (msg)->header.seq_num = (seq_number); \ } while (0); +typedef struct { + char prefix[MAXSZ_HICN_PREFIX]; +} prefix_key_t; + struct configuration_s { const char *fn_config; uint16_t port; @@ -72,7 +78,10 @@ struct configuration_s { const char *logfile; int logfile_fd; bool daemon; + kh_strategy_map_t *strategy_map; + slab_t *prefix_keys; + size_t n_suffixes_per_split; int_manifest_split_strategy_t split_strategy; }; @@ -95,6 +104,7 @@ configuration_t *configuration_create() { #endif configuration_set_loglevel(config, loglevel_from_str(DEFAULT_LOGLEVEL)); config->strategy_map = kh_init_strategy_map(); + config->prefix_keys = slab_create(prefix_key_t, SLAB_INIT_SIZE); config->n_suffixes_per_split = DEFAULT_N_SUFFIXES_PER_SPLIT; config->split_strategy = DEFAULT_DISAGGREGATION_STRATEGY; @@ -104,13 +114,8 @@ configuration_t *configuration_create() { void configuration_free(configuration_t *config) { assert(config); - const char *k_prefix; - unsigned _; - (void)_; - - // Free the strategy hashmap - kh_foreach(config->strategy_map, k_prefix, _, { free((char *)k_prefix); }); kh_destroy_strategy_map(config->strategy_map); + slab_free(config->prefix_keys); free(config); } @@ -202,7 +207,11 @@ bool configuration_get_daemon(const configuration_t *config) { void configuration_set_strategy(configuration_t *config, const char *prefix, strategy_type_t strategy_type) { int res; - khiter_t k = kh_put_strategy_map(config->strategy_map, strdup(prefix), &res); + prefix_key_t *prefix_copy = slab_get(prefix_key_t, config->prefix_keys); + strcpy_s(prefix_copy->prefix, sizeof(prefix_key_t), prefix); + + khiter_t k = + kh_put_strategy_map(config->strategy_map, prefix_copy->prefix, &res); kh_value(config->strategy_map, k) = strategy_type; } diff --git a/hicn-light/src/hicn/core/connection_table.c b/hicn-light/src/hicn/core/connection_table.c index 7bc0e2f4c..a6b114c01 100644 --- a/hicn-light/src/hicn/core/connection_table.c +++ b/hicn-light/src/hicn/core/connection_table.c @@ -19,6 +19,7 @@ */ #include +#include #include "connection.h" #include "connection_table.h" @@ -27,6 +28,10 @@ */ #define DEFAULT_CONNECTION_TABLE_SIZE 64 +typedef struct { + char name[SYMBOLIC_NAME_LEN]; +} name_key_t; + connection_table_t *_connection_table_create(size_t init_size, size_t max_size) { if (init_size == 0) init_size = DEFAULT_CONNECTION_TABLE_SIZE; @@ -38,7 +43,9 @@ connection_table_t *_connection_table_create(size_t init_size, /* Initialize indices */ table->id_by_pair = kh_init_ct_pair(); + table->pair_keys = slab_create(address_pair_t, SLAB_INIT_SIZE); table->id_by_name = kh_init_ct_name(); + table->name_keys = slab_create(name_key_t, SLAB_INIT_SIZE); /* * We start by allocating a reasonably-sized pool, as this will eventually @@ -50,26 +57,20 @@ connection_table_t *_connection_table_create(size_t init_size, } void connection_table_free(connection_table_t *table) { - const char *k_name; - const address_pair_t *k_pair; - unsigned v_conn_id; + unsigned conn_id; + kh_foreach_value(table->id_by_name, conn_id, { + connection_t *connection = connection_table_get_by_id(table, conn_id); + const char *name = connection_get_name(connection); - connection_t *connection; - const char *name; - kh_foreach(table->id_by_name, k_name, v_conn_id, { - connection = connection_table_get_by_id(table, v_conn_id); - name = connection_get_name(connection); INFO("Removing connection %s [%d]", name, connection->fd); connection_finalize(connection); }); - (void)v_conn_id; - kh_foreach(table->id_by_name, k_name, v_conn_id, { free((char *)k_name); }); - kh_foreach(table->id_by_pair, k_pair, v_conn_id, - { free((address_pair_t *)k_pair); }); - kh_destroy_ct_pair(table->id_by_pair); + slab_free(table->pair_keys); kh_destroy_ct_name(table->id_by_name); + slab_free(table->name_keys); + pool_free(table->connections); free(table); } @@ -93,12 +94,15 @@ connection_t *connection_table_allocate(const connection_table_t *table, int rc; // Add in name hash table - khiter_t k = kh_put_ct_name(table->id_by_name, strdup(name), &rc); + name_key_t *name_copy = slab_get(name_key_t, table->name_keys); + strcpy_s(name_copy->name, sizeof(name_key_t), name); + + khiter_t k = kh_put_ct_name(table->id_by_name, name_copy->name, &rc); assert(rc == KH_ADDED || rc == KH_RESET); kh_value(table->id_by_name, k) = (unsigned int)id; // Add in pair hash table - address_pair_t *pair_copy = (address_pair_t *)malloc(sizeof(address_pair_t)); + address_pair_t *pair_copy = slab_get(address_pair_t, table->pair_keys); memcpy(pair_copy, pair, sizeof(address_pair_t)); k = kh_put_ct_pair(table->id_by_pair, pair_copy, &rc); @@ -125,14 +129,14 @@ void connection_table_deallocate(const connection_table_t *table, // 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)); - free((char *)kh_key(table->id_by_name, k)); kh_del_ct_name(table->id_by_name, k); + slab_put(table->name_keys, kh_key(table->id_by_name, k)); // Remove from pair hash table k = kh_get_ct_pair(table->id_by_pair, pair); assert(k != kh_end(table->id_by_pair)); - free((address_pair_t *)kh_key(table->id_by_pair, k)); kh_del_ct_pair(table->id_by_pair, k); + slab_put(table->pair_keys, kh_key(table->id_by_pair, k)); assert(kh_size(table->id_by_name) == kh_size(table->id_by_pair)); pool_put(table->connections, conn); diff --git a/hicn-light/src/hicn/core/connection_table.h b/hicn-light/src/hicn/core/connection_table.h index 566443d93..dcfb1e1dd 100644 --- a/hicn-light/src/hicn/core/connection_table.h +++ b/hicn-light/src/hicn/core/connection_table.h @@ -32,6 +32,7 @@ #include #include +#include #include "address_pair.h" #include "connection.h" #include @@ -48,7 +49,9 @@ typedef struct { size_t max_size; kh_ct_pair_t *id_by_pair; + slab_t *pair_keys; kh_ct_name_t *id_by_name; + slab_t *name_keys; connection_t *connections; // pool } connection_table_t; diff --git a/hicn-light/src/hicn/core/forwarder.c b/hicn-light/src/hicn/core/forwarder.c index 72bb22118..d148f845d 100644 --- a/hicn-light/src/hicn/core/forwarder.c +++ b/hicn-light/src/hicn/core/forwarder.c @@ -805,7 +805,7 @@ int _forwarder_forward_aggregated_interest( assert(msgbuf_id_is_valid(msgbuf_id) && msgbuf_get_type(msgbuf) == HICN_PACKET_TYPE_INTEREST); - bool ret = -1; + int ret = -1; fib_entry_t *fib_entry = fib_match_msgbuf(forwarder->fib, msgbuf); if (!fib_entry) goto END; @@ -843,9 +843,8 @@ int _forwarder_forward_aggregated_interest( BITMAP_SIZE * sizeof(hicn_uword)); size_t suffix_index = 0; // Position of suffix in initial manifest - interest_manifest_header_t *manifest; + interest_manifest_header_t *manifest = NULL; size_t payload_size; - int ret; while (suffix_index < total_suffixes) { // If more than one sub-manifest, // clone original interest manifest and update suffix @@ -869,9 +868,9 @@ int _forwarder_forward_aggregated_interest( // Update manifest bitmap in current msgbuf - ret = + int ret = _forwarder_get_interest_manifest(msgbuf, &manifest, &payload_size); - assert(ret == 0); + _ASSERT(ret == 0); memcpy(manifest->request_bitmap, curr_bitmap, BITMAP_SIZE * sizeof(hicn_uword)); WITH_TRACE({ @@ -1088,7 +1087,7 @@ static ssize_t forwarder_process_interest(forwarder_t *forwarder, pkt_cache_save_suffixes_for_prefix( forwarder->pkt_cache, hicn_name_get_prefix(msgbuf_get_name(msgbuf))); - if (!int_manifest_header) + if (ret == -1) return forwarder_process_single_interest(forwarder, msgbuf_pool, msgbuf, msgbuf_id); return forwarder_process_aggregated_interest(forwarder, int_manifest_header, diff --git a/hicn-light/src/hicn/core/listener_table.c b/hicn-light/src/hicn/core/listener_table.c index c130399a5..4a0f74a13 100644 --- a/hicn-light/src/hicn/core/listener_table.c +++ b/hicn-light/src/hicn/core/listener_table.c @@ -19,6 +19,7 @@ */ #include +#include #include "listener_table.h" #include "listener.h" @@ -27,6 +28,10 @@ */ #define DEFAULT_LISTENER_TABLE_SIZE 64 +typedef struct { + char name[SYMBOLIC_NAME_LEN]; +} name_key_t; + listener_table_t *_listener_table_create(size_t init_size, size_t max_size) { if (init_size == 0) init_size = DEFAULT_LISTENER_TABLE_SIZE; @@ -37,7 +42,9 @@ listener_table_t *_listener_table_create(size_t init_size, size_t max_size) { /* Initialize indices */ table->id_by_name = kh_init_lt_name(); + table->name_keys = slab_create(name_key_t, SLAB_INIT_SIZE); table->id_by_key = kh_init_lt_key(); + table->listener_keys = slab_create(listener_key_t, SLAB_INIT_SIZE); /* * We start by allocating a reasonably-sized pool, as this will eventually @@ -49,25 +56,19 @@ listener_table_t *_listener_table_create(size_t init_size, size_t max_size) { } void listener_table_free(listener_table_t *table) { - const char *k_name; - const listener_key_t *k_key; - unsigned v; - - listener_t *listener; - const char *name; - kh_foreach(table->id_by_key, k_key, v, { - listener = listener_table_get_by_id(table, v); - name = listener_get_name(listener); + unsigned listener_id; + kh_foreach_value(table->id_by_key, listener_id, { + listener_t *listener = listener_table_get_by_id(table, listener_id); + const char *name = listener_get_name(listener); INFO("Removing listener %s [%d]", name, listener->fd); listener_finalize(listener); }); - (void)v; - kh_foreach(table->id_by_name, k_name, v, { free((char *)k_name); }); - kh_foreach(table->id_by_key, k_key, v, { free((listener_key_t *)k_key); }); - kh_destroy_lt_name(table->id_by_name); + slab_free(table->name_keys); kh_destroy_lt_key(table->id_by_key); + slab_free(table->listener_keys); + pool_free(table->listeners); free(table); } @@ -83,12 +84,15 @@ listener_t *listener_table_allocate(const listener_table_t *table, int rc; // Add in name hash table - khiter_t k = kh_put_lt_name(table->id_by_name, strdup(name), &rc); + name_key_t *name_copy = slab_get(name_key_t, table->name_keys); + strcpy_s(name_copy->name, sizeof(name_key_t), name); + + khiter_t k = kh_put_lt_name(table->id_by_name, name_copy->name, &rc); assert(rc == KH_ADDED || rc == KH_RESET); kh_value(table->id_by_name, k) = (unsigned int)id; // Add in key hash table - listener_key_t *key_copy = (listener_key_t *)malloc(sizeof(listener_key_t)); + listener_key_t *key_copy = slab_get(listener_key_t, table->listener_keys); memcpy(key_copy, key, sizeof(listener_key_t)); k = kh_put_lt_key(table->id_by_key, key_copy, &rc); @@ -107,14 +111,14 @@ void listener_table_deallocate(const listener_table_t *table, // Remove from name hash table khiter_t k = kh_get_lt_name(table->id_by_name, name); assert(k != kh_end(table->id_by_name)); - free((char *)kh_key(table->id_by_name, k)); kh_del_lt_name(table->id_by_name, k); + slab_put(table->name_keys, kh_key(table->id_by_name, k)); // Remove from key hash table k = kh_get_lt_key(table->id_by_key, key); assert(k != kh_end(table->id_by_key)); - free((listener_key_t *)kh_key(table->id_by_key, k)); kh_del_lt_key(table->id_by_key, k); + slab_put(table->listener_keys, kh_key(table->id_by_key, k)); assert(kh_size(table->id_by_name) == kh_size(table->id_by_key)); pool_put(table->listeners, listener); diff --git a/hicn-light/src/hicn/core/listener_table.h b/hicn-light/src/hicn/core/listener_table.h index 27c5daa04..062d1748e 100644 --- a/hicn-light/src/hicn/core/listener_table.h +++ b/hicn-light/src/hicn/core/listener_table.h @@ -32,6 +32,7 @@ #include #include +#include #include "address.h" #include "listener.h" #include @@ -48,7 +49,9 @@ typedef struct { size_t max_size; kh_lt_key_t *id_by_key; + slab_t *listener_keys; kh_lt_name_t *id_by_name; + slab_t *name_keys; listener_t *listeners; // pool } listener_table_t; diff --git a/hicn-light/src/hicn/core/packet_cache.c b/hicn-light/src/hicn/core/packet_cache.c index 9d0b041c3..7fa18b48f 100644 --- a/hicn-light/src/hicn/core/packet_cache.c +++ b/hicn-light/src/hicn/core/packet_cache.c @@ -84,13 +84,9 @@ const char *_pkt_cache_verdict_str[] = { * Free the two level packet cache structure (helper) */ void _prefix_map_free(kh_pkt_cache_prefix_t *prefix_to_suffixes) { - const hicn_name_prefix_t *key; - kh_pkt_cache_suffix_t *value; - kh_foreach(prefix_to_suffixes, key, value, { - //(void)key; - free((hicn_name_prefix_t *)key); - kh_destroy_pkt_cache_suffix(value); - }); + kh_pkt_cache_suffix_t *suffix; + kh_foreach_value(prefix_to_suffixes, suffix, + { kh_destroy_pkt_cache_suffix(suffix); }); kh_destroy_pkt_cache_prefix(prefix_to_suffixes); } @@ -99,7 +95,7 @@ void _prefix_map_free(kh_pkt_cache_prefix_t *prefix_to_suffixes) { */ kh_pkt_cache_suffix_t *_get_suffixes(kh_pkt_cache_prefix_t *prefix_to_suffixes, const hicn_name_prefix_t *prefix, - bool create) { + bool create, slab_t *prefix_keys) { khiter_t k = kh_get_pkt_cache_prefix(prefix_to_suffixes, prefix); /* Return suffixes if found... */ @@ -114,8 +110,8 @@ kh_pkt_cache_suffix_t *_get_suffixes(kh_pkt_cache_prefix_t *prefix_to_suffixes, */ kh_pkt_cache_suffix_t *suffixes = kh_init_pkt_cache_suffix(); - hicn_name_prefix_t *prefix_copy = malloc(sizeof(hicn_name_prefix_t)); - *prefix_copy = *prefix; + hicn_name_prefix_t *prefix_copy = slab_get(hicn_name_prefix_t, prefix_keys); + memcpy(prefix_copy, prefix, sizeof(hicn_name_prefix_t)); int rc; k = kh_put_pkt_cache_prefix(prefix_to_suffixes, prefix_copy, &rc); @@ -129,8 +125,9 @@ kh_pkt_cache_suffix_t *_get_suffixes(kh_pkt_cache_prefix_t *prefix_to_suffixes, */ void _remove_suffix(kh_pkt_cache_prefix_t *prefixes, const hicn_name_prefix_t *prefix, - const hicn_name_suffix_t suffix) { - kh_pkt_cache_suffix_t *suffixes = _get_suffixes(prefixes, prefix, false); + const hicn_name_suffix_t suffix, slab_t *prefix_keys) { + kh_pkt_cache_suffix_t *suffixes = + _get_suffixes(prefixes, prefix, false, prefix_keys); assert(suffixes != NULL); khiter_t k = kh_get_pkt_cache_suffix(suffixes, suffix); @@ -159,8 +156,10 @@ void __add_suffix(kh_pkt_cache_suffix_t *suffixes, hicn_name_suffix_t suffix, */ 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); + const hicn_name_suffix_t suffix, unsigned val, + slab_t *prefix_keys) { + kh_pkt_cache_suffix_t *suffixes = + _get_suffixes(prefixes, prefix, true, prefix_keys); assert(suffixes != NULL); __add_suffix(suffixes, suffix, val); @@ -184,9 +183,10 @@ unsigned __get_suffix(kh_pkt_cache_suffix_t *suffixes, unsigned _get_suffix(kh_pkt_cache_prefix_t *prefixes, const hicn_name_prefix_t *prefix, - hicn_name_suffix_t suffix) { + hicn_name_suffix_t suffix, slab_t *prefix_keys) { /* create is false as this function is always called by lookup */ - kh_pkt_cache_suffix_t *suffixes = _get_suffixes(prefixes, prefix, false); + kh_pkt_cache_suffix_t *suffixes = + _get_suffixes(prefixes, prefix, false, prefix_keys); if (!suffixes) { return HICN_INVALID_SUFFIX; } @@ -197,11 +197,11 @@ unsigned _get_suffix(kh_pkt_cache_prefix_t *prefixes, * 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_t *name, slab_t *prefix_keys) { 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); + return _get_suffix(prefixes, prefix, suffix, prefix_keys); } void pkt_cache_save_suffixes_for_prefix(pkt_cache_t *pkt_cache, @@ -216,8 +216,9 @@ void pkt_cache_save_suffixes_for_prefix(pkt_cache_t *pkt_cache, // Update cached prefix information pkt_cache->cached_prefix = *prefix; pkt_cache->cached_suffixes = - _get_suffixes(pkt_cache->prefix_to_suffixes, prefix, true); // XXX - // + _get_suffixes(pkt_cache->prefix_to_suffixes, prefix, true, + pkt_cache->prefix_keys); // XXX + // } void pkt_cache_reset_suffixes_for_prefix(pkt_cache_t *pkt_cache) { @@ -237,6 +238,7 @@ pkt_cache_t *pkt_cache_create(size_t cs_size) { if (!pkt_cache->cs) return NULL; pkt_cache->prefix_to_suffixes = kh_init_pkt_cache_prefix(); + pkt_cache->prefix_keys = slab_create(hicn_name_prefix_t, SLAB_INIT_SIZE); pool_init(pkt_cache->entries, DEFAULT_PKT_CACHE_SIZE, 0); pkt_cache->cached_prefix = HICN_NAME_PREFIX_EMPTY; @@ -250,6 +252,7 @@ void pkt_cache_free(pkt_cache_t *pkt_cache) { // Free prefix hash table and pool _prefix_map_free(pkt_cache->prefix_to_suffixes); + slab_free(pkt_cache->prefix_keys); pool_free(pkt_cache->entries); // Free PIT and CS @@ -261,8 +264,10 @@ 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 hicn_name_prefix_t *prefix, - bool create) { - return _get_suffixes(pkt_cache->prefix_to_suffixes, prefix, create); + bool create, + slab_t *prefix_keys) { + return _get_suffixes(pkt_cache->prefix_to_suffixes, prefix, create, + prefix_keys); } pkt_cache_entry_t *pkt_cache_allocate(pkt_cache_t *pkt_cache) { @@ -286,7 +291,8 @@ void pkt_cache_add_to_index(const pkt_cache_t *pkt_cache, (unsigned int)id); } else { _add_suffix(pkt_cache->prefix_to_suffixes, hicn_name_get_prefix(name), - hicn_name_get_suffix(name), (unsigned int)id); + hicn_name_get_suffix(name), (unsigned int)id, + pkt_cache->prefix_keys); } } @@ -296,7 +302,7 @@ void pkt_cache_add_to_index(const pkt_cache_t *pkt_cache, 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)); + hicn_name_get_suffix(name), pkt_cache->prefix_keys); // TODO #if 0 @@ -321,7 +327,8 @@ pkt_cache_entry_t *pkt_cache_lookup(pkt_cache_t *pkt_cache, index = __get_suffix(pkt_cache->cached_suffixes, hicn_name_get_suffix(name)); } else { - index = _get_suffix_from_name(pkt_cache->prefix_to_suffixes, name); + index = _get_suffix_from_name(pkt_cache->prefix_to_suffixes, name, + pkt_cache->prefix_keys); } if (index == HICN_INVALID_SUFFIX) { @@ -364,7 +371,7 @@ void pkt_cache_cs_remove_entry(pkt_cache_t *pkt_cache, pkt_cache_entry_t *entry, // 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)); + hicn_name_get_suffix(&entry->name), pkt_cache->prefix_keys); // Do not update the LRU cache for evicted entries if (!is_evicted) cs_vft[pkt_cache->cs->type]->remove_entry(pkt_cache, entry); @@ -391,7 +398,7 @@ void pkt_cache_pit_remove_entry(pkt_cache_t *pkt_cache, const hicn_name_t *name = &entry->name; _remove_suffix(pkt_cache->prefix_to_suffixes, hicn_name_get_prefix(name), - hicn_name_get_suffix(name)); + hicn_name_get_suffix(name), pkt_cache->prefix_keys); pool_put(pkt_cache->entries, entry); diff --git a/hicn-light/src/hicn/core/packet_cache.h b/hicn-light/src/hicn/core/packet_cache.h index dcbc20c7d..1abdc57c2 100644 --- a/hicn-light/src/hicn/core/packet_cache.h +++ b/hicn-light/src/hicn/core/packet_cache.h @@ -41,6 +41,7 @@ #define HICNLIGHT_PACKET_CACHE_H #include +#include #include "content_store.h" #include "pit.h" #include "msgbuf_pool.h" @@ -112,6 +113,7 @@ typedef struct { cs_t *cs; pkt_cache_entry_t *entries; kh_pkt_cache_prefix_t *prefix_to_suffixes; + slab_t *prefix_keys; // Cached prefix info to avoid double lookups, // used for both single interest speculation and interest manifest @@ -455,19 +457,19 @@ unsigned __get_suffix(kh_pkt_cache_suffix_t *suffixes, hicn_name_suffix_t suffix); unsigned _get_suffix(kh_pkt_cache_prefix_t *prefixes, const hicn_name_prefix_t *prefix, - hicn_name_suffix_t suffix); + hicn_name_suffix_t suffix, slab_t *prefix_keys); void __add_suffix(kh_pkt_cache_suffix_t *suffixes, hicn_name_suffix_t suffix, unsigned val); void _add_suffix(kh_pkt_cache_prefix_t *prefixes, - const hicn_name_prefix_t *prefix, hicn_name_suffix_t suffix, - unsigned val); + const hicn_name_prefix_t *prefix, + const hicn_name_suffix_t suffix, unsigned val, slab_t *slab); void _remove_suffix(kh_pkt_cache_prefix_t *prefixes, - const hicn_name_prefix_t *prefix, - hicn_name_suffix_t suffix); + const hicn_name_prefix_t *prefix, hicn_name_suffix_t suffix, + slab_t *slab); void _prefix_map_free(kh_pkt_cache_prefix_t *prefix_to_suffixes); kh_pkt_cache_suffix_t *_get_suffixes(kh_pkt_cache_prefix_t *prefix_to_suffixes, const hicn_name_prefix_t *prefix, - bool create); + bool create, slab_t *prefix_keys); #endif /************** Content Store *****************************/ diff --git a/hicn-light/src/hicn/test/test-configuration.cc b/hicn-light/src/hicn/test/test-configuration.cc index b631bb20b..2d3b5329f 100644 --- a/hicn-light/src/hicn/test/test-configuration.cc +++ b/hicn-light/src/hicn/test/test-configuration.cc @@ -69,6 +69,7 @@ TEST_F(ConfigurationTest, SetLogParameters) { EXPECT_EQ(log_file, LOG_FILE); int write_fd = configuration_get_logfile_fd(config); EXPECT_NE(write_fd, -1); + configuration_flush_log(); } TEST_F(ConfigurationTest, SetStrategyParameter) { diff --git a/hicn-light/src/hicn/test/test-connection_table.cc b/hicn-light/src/hicn/test/test-connection_table.cc index 171921b53..6723d0ff1 100644 --- a/hicn-light/src/hicn/test/test-connection_table.cc +++ b/hicn-light/src/hicn/test/test-connection_table.cc @@ -28,14 +28,18 @@ extern "C" { #define WITH_TESTS #include #include +#include } -#define CONNECTION_NAME "connection_name_test" -#define CONNECTION_NAME_2 "connection_name_test_2" +#define CONNECTION_NAME "conn_name" +#define CONNECTION_NAME_2 "conn_name_2" class ConnectionTableTest : public ::testing::Test { protected: ConnectionTableTest() { + assert(is_symbolic_name(CONNECTION_NAME, SYMBOLIC_NAME_LEN)); + assert(is_symbolic_name(CONNECTION_NAME_2, SYMBOLIC_NAME_LEN)); + log_conf.log_level = LOG_WARN; conn_table_ = connection_table_create(); diff --git a/hicn-light/src/hicn/test/test-listener_table.cc b/hicn-light/src/hicn/test/test-listener_table.cc index f4af02ee1..6bd2a6ab7 100644 --- a/hicn-light/src/hicn/test/test-listener_table.cc +++ b/hicn-light/src/hicn/test/test-listener_table.cc @@ -28,14 +28,18 @@ extern "C" { #define WITH_TESTS #include #include +#include } -#define LISTENER_NAME "listener_name_test" -#define LISTENER_NAME_2 "listener_name_test_2" +#define LISTENER_NAME "listener_name" +#define LISTENER_NAME_2 "listener_name_2" class ListenerTableTest : public ::testing::Test { protected: ListenerTableTest() { + assert(is_symbolic_name(LISTENER_NAME, SYMBOLIC_NAME_LEN)); + assert(is_symbolic_name(LISTENER_NAME_2, SYMBOLIC_NAME_LEN)); + log_conf.log_level = LOG_INFO; listener_table_ = listener_table_create(); diff --git a/hicn-light/src/hicn/test/test-packet_cache.cc b/hicn-light/src/hicn/test/test-packet_cache.cc index 76fdb4516..37f4fe985 100644 --- a/hicn-light/src/hicn/test/test-packet_cache.cc +++ b/hicn-light/src/hicn/test/test-packet_cache.cc @@ -96,25 +96,26 @@ class PacketCacheTest : public ::testing::Test { TEST_F(PacketCacheTest, LowLevelOperations) { kh_pkt_cache_prefix_t *prefix_to_suffixes = kh_init_pkt_cache_prefix(); const hicn_name_prefix_t *prefix = hicn_name_get_prefix(&name); - _add_suffix(prefix_to_suffixes, prefix, 1, 11); - _add_suffix(prefix_to_suffixes, prefix, 2, 22); + _add_suffix(prefix_to_suffixes, prefix, 1, 11, pkt_cache->prefix_keys); + _add_suffix(prefix_to_suffixes, prefix, 2, 22, pkt_cache->prefix_keys); - unsigned id = _get_suffix(prefix_to_suffixes, prefix, 1); + unsigned id = + _get_suffix(prefix_to_suffixes, prefix, 1, pkt_cache->prefix_keys); EXPECT_EQ(id, 11UL); - id = _get_suffix(prefix_to_suffixes, prefix, 2); + id = _get_suffix(prefix_to_suffixes, prefix, 2, pkt_cache->prefix_keys); EXPECT_EQ(id, 22UL); - id = _get_suffix(prefix_to_suffixes, prefix, 5); + id = _get_suffix(prefix_to_suffixes, prefix, 5, pkt_cache->prefix_keys); EXPECT_EQ(id, HICN_INVALID_SUFFIX); - _add_suffix(prefix_to_suffixes, prefix, 5, 55); - id = _get_suffix(prefix_to_suffixes, prefix, 5); + _add_suffix(prefix_to_suffixes, prefix, 5, 55, pkt_cache->prefix_keys); + id = _get_suffix(prefix_to_suffixes, prefix, 5, pkt_cache->prefix_keys); EXPECT_EQ(id, 55UL); - _remove_suffix(prefix_to_suffixes, prefix, 2); - _add_suffix(prefix_to_suffixes, prefix, 2, 222); - id = _get_suffix(prefix_to_suffixes, prefix, 2); + _remove_suffix(prefix_to_suffixes, prefix, 2, pkt_cache->prefix_keys); + _add_suffix(prefix_to_suffixes, prefix, 2, 222, pkt_cache->prefix_keys); + id = _get_suffix(prefix_to_suffixes, prefix, 2, pkt_cache->prefix_keys); EXPECT_EQ(id, 222UL); _prefix_map_free(prefix_to_suffixes); @@ -585,13 +586,15 @@ TEST_F(PacketCacheTest, PerformanceDoubleLookup) { for (int seq = 0; seq < N_OPS; seq++) { hicn_name_set_suffix(&tmp, seq); _add_suffix(prefix_to_suffixes, hicn_name_get_prefix(&tmp), - hicn_name_get_suffix(&tmp), hicn_name_get_suffix(&tmp)); + hicn_name_get_suffix(&tmp), hicn_name_get_suffix(&tmp), + pkt_cache->prefix_keys); } // Read from hash table for (int seq = 0; seq < N_OPS; seq++) { hicn_name_set_suffix(&tmp, seq); - _get_suffix(prefix_to_suffixes, hicn_name_get_prefix(&tmp), seq); + _get_suffix(prefix_to_suffixes, hicn_name_get_prefix(&tmp), seq, + pkt_cache->prefix_keys); } _prefix_map_free(prefix_to_suffixes); @@ -605,7 +608,8 @@ TEST_F(PacketCacheTest, PerformanceCachedLookup) { auto elapsed_time_single = get_execution_time([&]() { kh_pkt_cache_prefix_t *prefix_to_suffixes = kh_init_pkt_cache_prefix(); kh_pkt_cache_suffix_t *suffixes = - _get_suffixes(prefix_to_suffixes, hicn_name_get_prefix(&tmp), true); + _get_suffixes(prefix_to_suffixes, hicn_name_get_prefix(&tmp), true, + pkt_cache->prefix_keys); // Add to hash table for (int seq = 0; seq < N_OPS; seq++) { @@ -638,7 +642,8 @@ TEST_F(PacketCacheTest, PerformanceCachedLookupRandom) { auto elapsed_time_single_rand = get_execution_time([&]() { kh_pkt_cache_prefix_t *prefix_to_suffixes = kh_init_pkt_cache_prefix(); kh_pkt_cache_suffix_t *suffixes = - _get_suffixes(prefix_to_suffixes, hicn_name_get_prefix(&tmp), true); + _get_suffixes(prefix_to_suffixes, hicn_name_get_prefix(&tmp), true, + pkt_cache->prefix_keys); // Add to hash table for (int seq = 0; seq < N_OPS; seq++) { diff --git a/lib/includes/CMakeLists.txt b/lib/includes/CMakeLists.txt index 61af7eca8..3c79fb891 100644 --- a/lib/includes/CMakeLists.txt +++ b/lib/includes/CMakeLists.txt @@ -47,6 +47,7 @@ set(LIBHICN_HEADER_FILES_UTIL ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/pool.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/ring.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/set.h + ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/slab.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/sstrncpy.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/token.h ${CMAKE_CURRENT_SOURCE_DIR}/hicn/util/types.h @@ -55,4 +56,3 @@ set(LIBHICN_HEADER_FILES_UTIL ) set_property(GLOBAL PROPERTY LIBHICN_HEADER_FILES_UTIL_PROPERTY "${LIBHICN_HEADER_FILES_UTIL}") - diff --git a/lib/includes/hicn/util/log.h b/lib/includes/hicn/util/log.h index 6b35d1fef..b9b7725d6 100644 --- a/lib/includes/hicn/util/log.h +++ b/lib/includes/hicn/util/log.h @@ -20,12 +20,15 @@ #include // FILE #include // time, localtime -#define LOG_FATAL 0 -#define LOG_ERROR 1 -#define LOG_WARN 2 -#define LOG_INFO 3 -#define LOG_DEBUG 4 -#define LOG_TRACE 5 +typedef enum +{ + LOG_FATAL, + LOG_ERROR, + LOG_WARN, + LOG_INFO, + LOG_DEBUG, + LOG_TRACE +} log_level_t; typedef struct { diff --git a/lib/includes/hicn/util/slab.h b/lib/includes/hicn/util/slab.h new file mode 100644 index 000000000..2c6546add --- /dev/null +++ b/lib/includes/hicn/util/slab.h @@ -0,0 +1,126 @@ +/* + * 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. + */ + +/** + * @brief The slab is used to store elements of the same size. + * + * The slab contains blocks of contiguous memory. Each block contains multiple + * chunks. An element is stored inside a chunk and the chunk has a header with + * a pointer to the block it belongs to. + * + * Blocks are stored in two doubly-linked lists: 'full' for blocks that + * are already full, 'partial_or_empty' for blocks with available chunks. When + * a block becomes full it is moved into the 'full' list and vice versa. + * + * When allocationg an element, a block is taken from the 'partial_or_empty' + * list if such list is not empty. If empty, a new block of contiguous memory + * is created and put in the 'partial_or_empty' list. Then, a chunk is taken + * from the block. When releasing an element, the block it belongs to is + * retrieved from the chunk header and used to release the chunk. + * + * Blocks are created with increasing capacity (i.e. number of chunks they + * contain) such that every new block allocaion doubles the total number of + * chunks stored in the slab. + */ + +#ifndef UTIL_SLAB_H +#define UTIL_SLAB_H + +#include + +#define SLAB_INIT_SIZE 32 + +/* CHUNK */ + +typedef struct block_s block_t; +typedef struct +{ + block_t *block; // Pointer to the block that contains the chunk +} chunk_hdr_t; + +#define CHUNK_HDRLEN SIZEOF_ALIGNED (chunk_hdr_t) +#define chunk_hdr(chunk) ((chunk_hdr_t *) ((uint8_t *) (chunk) -CHUNK_HDRLEN)) + +/* BLOCK */ + +struct block_s +{ + void *pool; + block_t *prev; + block_t *next; +}; + +/* SLAB */ + +typedef struct +{ + size_t num_chunks; // Total number of chunks (from all blocks) currently + // stored in the slab + size_t chunk_size; + block_t *full; + block_t *partial_or_empty; +} slab_t; + +/* Internal API */ + +slab_t *_slab_create (size_t elt_size, size_t num_elts); +void *_slab_get (slab_t *slab); +void _slab_put (slab_t *slab, void *elt); + +/* Public API */ + +/** + * @brief Create a slab able to store elements of type 'TYPE'. + * + * @param[in] TYPE Type of the elements to store in the slab. + * @param[in] SIZE Initial size of the slab, i.e. size of the initial block. + * @return slab_t* The slab created, NULL if error. + */ +#define slab_create(TYPE, SIZE) _slab_create (sizeof (TYPE), SIZE) + +/** + * @brief Free a slab. + * + * @param[in] slab Slab to free. + */ +void slab_free (slab_t *slab); + +/** + * @brief Get an element from the slab. + * + * @param[in] TYPE Type of the elements stored in the slab. + * @param[in] SLAB Slab to take the element from. + * @return TYPE* Element retrieved from the slab + */ +#define slab_get(TYPE, SLAB) (TYPE *) _slab_get (SLAB) + +/** + * @brief Same as 'slab_get' but with a different signature, to avoid passing + * the type that is instead inferred from the element. + * + * @param[in] SLAB Slab to take the element from. + * @param[in, out] ELT Element retrieved from the slab. + */ +#define slab_get2(SLAB, ELT) ELT = (typeof (*(ELT)) *) _slab_get (SLAB) + +/** + * @brief Put an element back into the slab. + * + * @param[in] SLAB Slab to return the element to. + * @param[in] ELT Element to put in the slab. + */ +#define slab_put(SLAB, ELT) _slab_put (SLAB, (void *) ELT) + +#endif /* UTIL_SLAB_H */ diff --git a/lib/includes/hicn/util/sstrncpy.h b/lib/includes/hicn/util/sstrncpy.h index 81427be6b..0b397c26b 100644 --- a/lib/includes/hicn/util/sstrncpy.h +++ b/lib/includes/hicn/util/sstrncpy.h @@ -20,6 +20,7 @@ #define __STDC_WANT_LIB_EXT1__ 1 #endif +#include #include #ifdef __STDC_LIB_EXT1__ diff --git a/lib/src/CMakeLists.txt b/lib/src/CMakeLists.txt index 10c39fae2..27446a493 100644 --- a/lib/src/CMakeLists.txt +++ b/lib/src/CMakeLists.txt @@ -36,6 +36,7 @@ list(APPEND LIBHICN_SOURCE_FILES util/log.c util/pool.c util/ring.c + util/slab.c util/types.c util/vector.c ) diff --git a/lib/src/test/CMakeLists.txt b/lib/src/test/CMakeLists.txt index 17cf835d2..d828c8dd8 100644 --- a/lib/src/test/CMakeLists.txt +++ b/lib/src/test/CMakeLists.txt @@ -27,6 +27,7 @@ list(APPEND TESTS_SRC test_khash.cc test_pool.cc test_ring.cc + test_slab.cc test_vector.cc ) diff --git a/lib/src/test/test_khash.cc b/lib/src/test/test_khash.cc index b0423ab5d..70b2f2258 100644 --- a/lib/src/test/test_khash.cc +++ b/lib/src/test/test_khash.cc @@ -159,11 +159,11 @@ TEST_F (KHashTest, Collisions) k = kh_put_test_map (map, &key1, &ret); EXPECT_EQ (ret, 1); - kh_val (map, k) = 15; + kh_val (map, k) = 15u; k = kh_put_test_map (map, &key2, &ret); EXPECT_EQ (ret, 1); - kh_val (map, k) = 27; + kh_val (map, k) = 27u; k = kh_get_test_map (map, &key1); ASSERT_NE (k, kh_end (map)); diff --git a/lib/src/test/test_slab.cc b/lib/src/test/test_slab.cc new file mode 100644 index 000000000..15deff3c1 --- /dev/null +++ b/lib/src/test/test_slab.cc @@ -0,0 +1,148 @@ +/* + * 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 + +extern "C" +{ +#include +} + +class SlabTest : public ::testing::Test +{ +protected: + SlabTest () {} + virtual ~SlabTest () { slab_free (slab); } + + slab_t *slab; +}; + +typedef struct +{ + int index; + int val; +} element_t; + +TEST_F (SlabTest, SlabCreateAndGetSingleChunk) +{ + slab = slab_create (element_t, 16); + ASSERT_NE (slab, nullptr); + + element_t *e = slab_get (element_t, slab); + ASSERT_NE (e, nullptr); + slab_put (slab, e); +} + +TEST_F (SlabTest, SlabGetChunks) +{ + slab = slab_create (element_t, 2); + + // Force creation of multiple blocks (since initial size is only 2) + for (int i = 0; i < 100; i++) + { + element_t *e = slab_get (element_t, slab); + EXPECT_NE (e, nullptr); + } +} + +TEST_F (SlabTest, SlabGetAndPutChunksNoResize) +{ + constexpr int NUM_ELEMENTS = 64; + element_t *elements[NUM_ELEMENTS]; + for (int i = 0; i < NUM_ELEMENTS; i++) + elements[i] = NULL; + + // Initial size=NUM_ELEMENTS, only one block will be created + slab = slab_create (element_t, NUM_ELEMENTS); + + for (int i = 0; i < NUM_ELEMENTS; i++) + { + elements[i] = slab_get (element_t, slab); + EXPECT_NE (elements[i], nullptr); + } + + // Release all chunks + for (int i = 0; i < NUM_ELEMENTS; i++) + slab_put (slab, elements[i]); +} + +TEST_F (SlabTest, SlabGetAndPutChunks) +{ + constexpr int NUM_ELEMENTS = 100; + element_t *elements[NUM_ELEMENTS]; + for (int i = 0; i < NUM_ELEMENTS; i++) + elements[i] = NULL; + + // Initial size=2 while NUM_ELEMENTS=100, to force creation of multiple + // blocks + slab = slab_create (sizeof (element_t), 2); + + for (int i = 0; i < NUM_ELEMENTS; i++) + { + elements[i] = slab_get (element_t, slab); + EXPECT_NE (elements[i], nullptr); + } + + // Release all chunks + for (int i = 0; i < NUM_ELEMENTS; i++) + slab_put (slab, elements[i]); +} + +TEST_F (SlabTest, SlabGetAndPutSomeChunks) +{ + slab = slab_create (element_t, 2); + + constexpr int NUM_ELEMENTS = 100; + element_t *elements[NUM_ELEMENTS]; + for (int i = 0; i < NUM_ELEMENTS; i++) + elements[i] = NULL; + + // Get chunks... + for (int i = 0; i < NUM_ELEMENTS; i++) + { + elements[i] = slab_get (element_t, slab); + EXPECT_NE (elements[i], nullptr); + + // ...and return only some of them + if (i % 5 == 0) + slab_put (slab, elements[i]); + } +} + +TEST_F (SlabTest, SlabGetSameChunkTwice) +{ + slab = slab_create (element_t, 1); + + // Get chunk and update it before returning it + element_t *e = slab_get (element_t, slab); + ASSERT_NE (e, nullptr); + element_t *prev = e; + e->index = 2; + e->val = 3; + slab_put (slab, e); + + // Get a chunk again: it should return the previous one + // without wiping its memory + e = slab_get (element_t, slab); + ASSERT_NE (e, nullptr); + EXPECT_EQ (e, prev); + EXPECT_EQ (e->index, 2); + EXPECT_EQ (e->val, 3); + + // Try to get an additional chunk: it should return a new chunk + // (different from previous one) + e = slab_get (element_t, slab); + EXPECT_NE (e, prev); +} \ No newline at end of file diff --git a/lib/src/util/slab.c b/lib/src/util/slab.c new file mode 100644 index 000000000..763dcb444 --- /dev/null +++ b/lib/src/util/slab.c @@ -0,0 +1,203 @@ +/* + * 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 +#include +#include + +/* BLOCK LINKED LISTS */ + +static void +block_add_to_head (block_t **head_ptr, block_t *block) +{ + if (head_ptr == NULL || block == NULL) + return; + + block->prev = NULL; + if (*head_ptr != NULL) + { + block->next = *head_ptr; + block->next->prev = block; + } + + *head_ptr = block; +} + +static block_t * +block_remove_from_head (block_t **head_ptr) +{ + if (head_ptr == NULL || *head_ptr == NULL) + return NULL; + + block_t *old_head = *head_ptr; + *head_ptr = old_head->next; + + if (*head_ptr != NULL) + (*head_ptr)->prev = NULL; + return old_head; +} + +static void +block_remove (block_t **head_ptr, block_t *block) +{ + if (*head_ptr == NULL || block == NULL) + return; + + if (block == *head_ptr) + *head_ptr = block->next; + if (block->next != NULL) + block->next->prev = block->prev; + if (block->prev != NULL) + block->prev->next = block->next; +} + +static bool +is_block_list_empty (block_t *block) +{ + return block == NULL; +} + +static void +block_list_free (block_t **head) +{ + if (head == NULL || *head == NULL) + return; + + block_t *curr_block = *head; + while (curr_block != NULL) + { + block_t *next = curr_block->next; + pool_free (curr_block->pool); + free (curr_block); + + curr_block = next; + } + + *head = NULL; +} + +/* BLOCK */ + +static bool +is_block_full (block_t *block) +{ + return pool_get_free_indices_size (block->pool) == 0; +} + +static void +block_set_ptr_in_chunks (block_t *block, size_t chunk_size) +{ + void *chunk = block->pool; + + // Cannot use `pool_foreach()` since it requires to know the type + // while here we use a generic (void *) + for (int i = 0; i < pool_get_alloc_size (block->pool); i++) + { + chunk_hdr_t *hdr = (chunk_hdr_t *) chunk; + hdr->block = block; + + chunk = (uint8_t *) (chunk) + chunk_size; // Move to next chunk + } +} + +static block_t * +block_create (size_t chunk_size, size_t num_chunks) +{ + block_t *block = malloc (sizeof (block_t)); + if (block == NULL) + return NULL; + + block->prev = block->next = NULL; + _pool_init (&block->pool, chunk_size, num_chunks, 0); + block_set_ptr_in_chunks (block, chunk_size); + + return block; +} + +/* SLAB */ + +slab_t * +_slab_create (size_t elt_size, size_t num_elts) +{ + // Initialize slab + slab_t *slab = malloc (sizeof (slab_t)); + if (slab == NULL) + return NULL; + + *slab = (slab_t){ .num_chunks = next_pow2 (num_elts), + .chunk_size = CHUNK_HDRLEN + elt_size, + .full = NULL, + .partial_or_empty = NULL }; + + // Add initial empty block to partial or empty list + block_t *block = block_create (slab->chunk_size, slab->num_chunks); + block_add_to_head (&slab->partial_or_empty, block); + + return slab; +} + +void +slab_free (slab_t *slab) +{ + block_list_free (&slab->full); + block_list_free (&slab->partial_or_empty); + free (slab); +} + +void * +_slab_get (slab_t *slab) +{ + // Create new empty block if none with available chunks + if (is_block_list_empty (slab->partial_or_empty)) + { + block_t *block = block_create (slab->chunk_size, slab->num_chunks); + block_add_to_head (&slab->partial_or_empty, block); + + slab->num_chunks *= 2; // Grow size exponentially + } + + // Get chunck from first block in 'partial_or_empty' list + void *chunk; + _pool_get (&slab->partial_or_empty->pool, &chunk, slab->chunk_size); + + // If the current block (i.e. head of 'partial_or_empty' list) if full, + // move it to the 'full' list + if (is_block_full (slab->partial_or_empty)) + { + block_t *block = block_remove_from_head (&slab->partial_or_empty); + block_add_to_head (&slab->full, block); + } + + return (uint8_t *) chunk + CHUNK_HDRLEN; +} + +void +_slab_put (slab_t *slab, void *chunk) +{ + // Get which block the chunk (that we want to release) belong to + chunk_hdr_t *hdr = chunk_hdr (chunk); + block_t *block = hdr->block; + + // Put chunk back into block + bool is_full = is_block_full (block); + _pool_put (&block->pool, (void *) &hdr, slab->chunk_size); + + // If the block was previously full, move it to 'partial_or_empty' list + if (is_full) + { + block_remove (&slab->full, block); + block_add_to_head (&slab->partial_or_empty, block); + } +} \ No newline at end of file -- cgit 1.2.3-korg