From patchwork Sat Jul 18 20:03:41 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bill Fischofer X-Patchwork-Id: 51258 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-lb0-f198.google.com (mail-lb0-f198.google.com [209.85.217.198]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id D28B622A28 for ; Sat, 18 Jul 2015 20:14:28 +0000 (UTC) Received: by lbbvz8 with SMTP id vz8sf32208181lbb.2 for ; Sat, 18 Jul 2015 13:14:27 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:delivered-to:from:to:date :message-id:in-reply-to:references:cc:subject:precedence:list-id :list-unsubscribe:list-archive:list-post:list-help:list-subscribe :mime-version:content-type:content-transfer-encoding:errors-to :sender:x-original-sender:x-original-authentication-results :mailing-list; bh=WpF1zm/G2YDektd0KMrYjk5T9ovcTKZRjh5PHM314OE=; b=U8ONIz8QuT7r/aJFHVfjfb869SuVlvCVXZ78K0DpKzgDBC1DnWmQDCYhg+RdSc4sab yjGBeCKE+w1L37MLzbFis5t4CsH2XNEyjNswxYxyU10UCt4aCjMIe7ZT3WrNctbGzs6I QL/NENlvCezcYy/BpZh+gBlaNk9/yrYM1788bLYKySZXs/1Mm+GXiJJ9J7H4MWknhL8F w4jWLdlCjQlW2TJPyn/7GGjmJsuy8wRZtqOYozjr8nvQq0tLEKX60xoKENdrk2UkaYm4 kOv/kEBfS9TMfUxs9OAjVOM4vJSPCUiY2ukIJBjx1SJq8LtzKEMTVUN70JZ7sq8a9iU9 CL4g== X-Gm-Message-State: ALoCoQl2Pl9iXdh4WbsSUj/qlfyl7zCVnUOA77Hj++SUj0nOLb45bWQ/m+5Ok5JijMm7f9O9kji5 X-Received: by 10.152.6.103 with SMTP id z7mr10865329laz.8.1437250467759; Sat, 18 Jul 2015 13:14:27 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.152.179.171 with SMTP id dh11ls557686lac.47.gmail; Sat, 18 Jul 2015 13:14:27 -0700 (PDT) X-Received: by 10.112.142.105 with SMTP id rv9mr12647625lbb.11.1437250467249; Sat, 18 Jul 2015 13:14:27 -0700 (PDT) Received: from mail-la0-f49.google.com (mail-la0-f49.google.com. [209.85.215.49]) by mx.google.com with ESMTPS id eu8si13394665lbc.171.2015.07.18.13.14.26 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 18 Jul 2015 13:14:26 -0700 (PDT) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.49 as permitted sender) client-ip=209.85.215.49; Received: by laem6 with SMTP id m6so77308223lae.0 for ; Sat, 18 Jul 2015 13:14:26 -0700 (PDT) X-Received: by 10.112.126.101 with SMTP id mx5mr20702456lbb.35.1437250466446; Sat, 18 Jul 2015 13:14:26 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.112.108.230 with SMTP id hn6csp536609lbb; Sat, 18 Jul 2015 13:14:24 -0700 (PDT) X-Received: by 10.140.101.97 with SMTP id t88mr36367186qge.9.1437250464041; Sat, 18 Jul 2015 13:14:24 -0700 (PDT) Received: from lists.linaro.org (lists.linaro.org. [54.225.227.206]) by mx.google.com with ESMTP id z103si18655417qgz.67.2015.07.18.13.14.23; Sat, 18 Jul 2015 13:14:24 -0700 (PDT) Received-SPF: pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.225.227.206 as permitted sender) client-ip=54.225.227.206; Received: by lists.linaro.org (Postfix, from userid 109) id 2D29961D0F; Sat, 18 Jul 2015 20:14:23 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on ip-10-142-244-252.ec2.internal X-Spam-Level: X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, URIBL_BLOCKED autolearn=disabled version=3.4.0 Received: from ip-10-142-244-252.ec2.internal (localhost [127.0.0.1]) by lists.linaro.org (Postfix) with ESMTP id 668AA61CEC; Sat, 18 Jul 2015 20:05:51 +0000 (UTC) X-Original-To: lng-odp@lists.linaro.org Delivered-To: lng-odp@lists.linaro.org Received: by lists.linaro.org (Postfix, from userid 109) id 65B0961D03; Sat, 18 Jul 2015 20:04:39 +0000 (UTC) Received: from mail-oi0-f52.google.com (mail-oi0-f52.google.com [209.85.218.52]) by lists.linaro.org (Postfix) with ESMTPS id 4883961D17 for ; Sat, 18 Jul 2015 20:04:03 +0000 (UTC) Received: by oibn4 with SMTP id n4so88794090oib.3 for ; Sat, 18 Jul 2015 13:04:02 -0700 (PDT) X-Received: by 10.202.242.212 with SMTP id q203mr18381549oih.52.1437249842839; Sat, 18 Jul 2015 13:04:02 -0700 (PDT) Received: from localhost.localdomain (cpe-24-28-70-239.austin.res.rr.com. [24.28.70.239]) by smtp.gmail.com with ESMTPSA id y5sm8537998oes.15.2015.07.18.13.04.01 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sat, 18 Jul 2015 13:04:02 -0700 (PDT) From: Bill Fischofer To: lng-odp@lists.linaro.org Date: Sat, 18 Jul 2015 15:03:41 -0500 Message-Id: <1437249827-578-7-git-send-email-bill.fischofer@linaro.org> X-Mailer: git-send-email 2.1.4 In-Reply-To: <1437249827-578-1-git-send-email-bill.fischofer@linaro.org> References: <1437249827-578-1-git-send-email-bill.fischofer@linaro.org> X-Topics: patch Cc: Barry Spinney Subject: [lng-odp] [RFC API-NEXT PATCH 06/12] linux-generic: tm: add name_table support routines X-BeenThere: lng-odp@lists.linaro.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: , List-Help: , List-Subscribe: , MIME-Version: 1.0 Errors-To: lng-odp-bounces@lists.linaro.org Sender: "lng-odp" X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: bill.fischofer@linaro.org X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.49 as permitted sender) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 Signed-off-by: Barry Spinney Signed-off-by: Mike Holmes Signed-off-by: Bill Fischofer --- platform/linux-generic/Makefile.am | 2 + .../include/odp_name_table_internal.h | 61 + platform/linux-generic/odp_name_table.c | 1357 ++++++++++++++++++++ 3 files changed, 1420 insertions(+) create mode 100644 platform/linux-generic/include/odp_name_table_internal.h create mode 100644 platform/linux-generic/odp_name_table.c diff --git a/platform/linux-generic/Makefile.am b/platform/linux-generic/Makefile.am index 80c57de..f1815e7 100644 --- a/platform/linux-generic/Makefile.am +++ b/platform/linux-generic/Makefile.am @@ -130,6 +130,7 @@ noinst_HEADERS = \ ${srcdir}/include/odp_schedule_internal.h \ ${srcdir}/include/odp_spin_internal.h \ ${srcdir}/include/odp_timer_internal.h \ + ${srcdir}/include/odp_name_table_internal.h \ ${srcdir}/Makefile.inc __LIB__libodp_la_SOURCES = \ @@ -141,6 +142,7 @@ __LIB__libodp_la_SOURCES = \ odp_errno.c \ odp_event.c \ odp_init.c \ + odp_name_table.c \ odp_impl.c \ odp_packet.c \ odp_packet_flags.c \ diff --git a/platform/linux-generic/include/odp_name_table_internal.h b/platform/linux-generic/include/odp_name_table_internal.h new file mode 100644 index 0000000..6764203 --- /dev/null +++ b/platform/linux-generic/include/odp_name_table_internal.h @@ -0,0 +1,61 @@ +/* Copyright 2015 EZchip Semiconductor Ltd. All Rights Reserved. + * + * Copyright (c) 2015, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +#ifndef ODP_INT_NAME_TABLE_H_ +#define ODP_INT_NAME_TABLE_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include +#include + +typedef enum { + ODP_COS_HANDLE, + ODP_PKTIO_HANDLE, + ODP_POOL_HANDLE, + ODP_QUEUE_HANDLE, + ODPH_RING_HANDLE, + ODP_SHM_HANDLE, + ODP_TIMER_POOL_HANDLE, + ODP_TM_HANDLE, + ODP_TM_SHAPER_PROFILE_HANDLE, + ODP_TM_SCHED_PROFILE_HANDLE, + ODP_TM_THRESHOLD_PROFILE_HANDLE, + ODP_TM_WRED_PROFILE_HANDLE, + ODP_TM_NODE_HANDLE +} odp_int_name_kind_t; + +typedef uint32_t odp_int_name_t; +#define ODP_INVALID_NAME 0 + +#define ODP_INT_NAME_LEN 32 + +odp_int_name_t odp_int_name_tbl_add(char *name, + uint8_t name_kind, + uint64_t user_data); + +odp_int_name_t odp_int_name_tbl_lookup(char *name, + uint8_t name_kind); + +int odp_int_name_tbl_delete(odp_int_name_t odp_name); + +const char *odp_int_name_tbl_name(odp_int_name_t odp_name); + +uint64_t odp_int_name_tbl_user_data(odp_int_name_t odp_name); + +void odp_int_name_tbl_stats_print(void); + +void odp_int_name_tbl_init(void); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/platform/linux-generic/odp_name_table.c b/platform/linux-generic/odp_name_table.c new file mode 100644 index 0000000..edd0e9c --- /dev/null +++ b/platform/linux-generic/odp_name_table.c @@ -0,0 +1,1357 @@ + /* Copyright 2015 EZchip Semiconductor Ltd. All Rights Reserved. + + * Copyright (c) 2015, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +#include +#include +#include +#include +#include +#include + +#define MAX(a, b) (((a) > (b)) ? (a) : (b)) +#define MIN(a, b) (((a) < (b)) ? (a) : (b)) + + /* The following constants define some tunable parameters of this module. + * They are set to fairly reasonable values (perhaps somewhat biased toward + * handling a number of names in the range of one thousand to one million). + * Change these values ONLY if your needs are outside of this range AND you + * have a complete understanding of how this code works. + * + * The primary hash table size should be a power of 2 in the range 256 to 64K. + * The size of the secondary hash tables should be a power of 2 in the range + * 64 to 256. + */ +#define PRIMARY_HASH_TBL_SIZE (16 * 1024) +#define SECONDARY_HASH_TBL_SIZE 128 + + /* The following thresholds set the number of primary table hash collisions + * before either replacing the name_table entry linked list with a secondary + * hash table (in the case of MAX_PRIMARY_LIST_SIZE) when adding OR + * replacing a secondary hash table with a linked list (MIN_SECONDARY_TBL_SIZE) + * when deleting. It is important to make sure these values are sufficiently + * different in value so as to exhibit meaningful hysteresis. + */ +#define MAX_PRIMARY_LIST_SIZE 12 +#define MAX_SECONDARY_LIST_SIZE 12 +#define MIN_SECONDARY_TBL_SIZE 4 + + /* Still to be documented.*/ +#define INITIAL_NAME_TBL_SIZE 1024 + + /* The number of name tables should not be changed. */ +#define NUM_NAME_TBLS 16 + +#define SECONDARY_HASH_HISTO_PRINT 1 + + /* #define USE_AES */ + +#if defined __x86_64__ + +#ifdef USE_AES + +typedef long long int v2di __attribute__((vector_size(16))); + +static const v2di HASH_CONST1 = { 0x123456, 0xFEBCDA383 }; +static const v2di HASH_CONST2 = { 0x493BA3F689, 0x102F5D73A8C }; + +#define PLATFORM_HASH_STATE v2di + +#define PLATFORM_HASH32_INIT(hash_state, name_len) \ + ({ \ + hash_state = HASH_CONST1; \ + hash_state[0] ^= name_len; \ + }) + +#define PLATFORM_HASH32(hash_state, name_word) \ + ({ \ + v2di data; \ + \ + data[0] = name_word; \ + data[1] = name_word << 1; \ + hash_state = __builtin_ia32_aesenc128(hash_state, data); \ + }) + +#define PLATFORM_HASH32_FINISH(hash_state, kind) \ + ({ \ + uint64_t result; \ + v2di data; \ + \ + data[0] = name_kind; \ + data[1] = name_kind << 7; \ + hash_state = __builtin_ia32_aesenc128(hash_state, data); \ + hash_state = __builtin_ia32_aesenc128(hash_state, \ + HASH_CONST2); \ + hash_state = __builtin_ia32_aesenc128(hash_state, \ + HASH_CONST1); \ + result = (uint64_t)hash_state[0] ^ hash_state[1]; \ + result = result ^ result >> 32; \ + (uint32_t)result; \ + }) + +#else + +#define PLATFORM_HASH_STATE uint64_t + +#define PLATFORM_HASH32_INIT(hash_state, name_len) \ + ({ \ + hash_state = (uint64_t)name_len; \ + hash_state |= hash_state << 8; \ + hash_state |= hash_state << 16; \ + hash_state |= hash_state << 32; \ + }) + +#define PLATFORM_HASH32(hash_state, name_word) \ + ({ \ + uint64_t temp; \ + \ + temp = ((uint64_t)name_word) * 0xFEFDFCF5; \ + hash_state = hash_state * 0xFF; \ + hash_state ^= temp ^ (uint64_t)name_word; \ + }) + +#define PLATFORM_HASH32_FINISH(hash_state, kind) \ + ({ \ + hash_state ^= (((uint32_t)kind) << 13); \ + hash_state = hash_state * 0xFEFDFCF5; \ + hash_state = hash_state ^ hash_state >> 32; \ + hash_state = hash_state % 0xFEEDDCCBBAA1; \ + hash_state = hash_state ^ hash_state >> 32; \ + (uint32_t)hash_state; \ + }) + +#endif + +#elif defined(__tile_gx__) + +#define PLATFORM_HASH_STATE uint32_t + +#define PLATFORM_HASH32_INIT(hash_state, name_len) \ + ({ \ + hash_state = 0xFEFDFCF5; \ + hash_state = __insn_crc_32_32(hash_state, name_len); \ + }) + +#define PLATFORM_HASH32(hash_state, name_word) \ + ({ \ + hash_state = __insn_crc_32_32(hash_state, name_word); \ + }) + +#define PLATFORM_HASH32_FINISH(hash_state, kind) \ + ({ \ + hash_state = __insn_crc_32_32(hash_state, kind); \ + hash_state = __insn_crc_32_32(hash_state, 0xFFFFFFFF); \ + hash_state = __insn_crc_32_32(hash_state, 0xFEFDFCF5); \ + (uint32_t)hash_state; \ + }) + +#elif defined(__arm__) && defined(__aarch64__) + +#define PLATFORM_HASH_STATE uint32_t + +#define PLATFORM_HASH32_INIT(hash_state, name_len) \ + ({ \ + hash_state = 0xFEFDFCF5; \ + hash_state = __crc32w(hash_state, name_len); \ + }) + +#define PLATFORM_HASH32(hash_state, name_word) \ + ({ \ + asm volatile ("crc32w %0, %0, %1" : \ + "=r" (hash_state) : \ + "r" (name_word)); \ + }) + +#define PLATFORM_HASH32_FINISH(hash_state, kind) \ + ({ \ + hash_state = __crc32w(hash_state, kind); \ + hash_state = __crc32w(hash_state, 0xFFFFFFFF); \ + hash_state = __crc32w(hash_state, 0xFEFDFCF5); \ + (uint32_t)hash_state; \ + }) + +#else +#error "Need to define PLATFORM_DEPENDENT_HASH32 macro" +#endif + +typedef struct name_tbl_entry_s name_tbl_entry_t; + + /* It is important for most platforms that the following struct fit within + * one cacheline. + */ +struct name_tbl_entry_s { + name_tbl_entry_t *next_entry; + uint64_t user_data; + odp_int_name_t name_tbl_id; + uint32_t hash_value; + uint8_t name_kind; + uint8_t name_len; + char name[ODP_INT_NAME_LEN + 1]; +} ODP_ALIGNED_CACHE; + +typedef struct { + uint32_t num_allocd; + uint32_t num_used; + uint32_t num_added_to_free_list; + uint32_t num_avail_to_add; + uint32_t base_id; + name_tbl_entry_t *free_list_head; + name_tbl_entry_t entries[0]; +} ODP_ALIGNED_CACHE name_tbl_t; + +typedef struct { + name_tbl_t *tbls[NUM_NAME_TBLS]; + uint64_t avail_space_bit_mask; + uint64_t num_adds; + uint64_t num_deletes; + uint32_t current_num_names; + uint8_t num_name_tbls; +} name_tbls_t; + + /* A hash table entry is LOGICALLY either empty, a pointer to a 64-byte + * aligned name_tbl_entry_t OR a pointer to a 64-byte aligned secondary hash + * table. Since the bottom 6-bits of this value are not needed to hold the + * address, these 6 bits are used to indicate the what type of object this + * address refers to AND in one case the maximum number of hash "collisions" + * at this level. Specifically, if the entire value is 0 then this entry is + * empty, else if the bottom 6 bits are 0, then this hash_tbl_entry_t value is + * a pointer to a secondary hash table. Otherwise if the bottom 6 bits are + * NOT zero then this values points to a (linked list of) name_table_entry_t + * records AND the bottom 6 bits are the length of this list. + */ +typedef uintptr_t hash_tbl_entry_t; + +typedef struct { + hash_tbl_entry_t hash_entries[SECONDARY_HASH_TBL_SIZE]; +} secondary_hash_tbl_t; + +typedef struct { + hash_tbl_entry_t hash_entries[PRIMARY_HASH_TBL_SIZE]; + uint32_t hash_collisions[PRIMARY_HASH_TBL_SIZE]; + uint32_t num_secondary_tbls[2]; +} primary_hash_tbl_t; + +static uint8_t name_tbls_initialized; +static name_tbls_t name_tbls; +static odp_ticketlock_t name_table_lock; +static primary_hash_tbl_t name_hash_tbl; + +static void *aligned_malloc(uint32_t length, uint32_t align) +{ + uintptr_t malloc_addr, mem_addr, alignment, total_length; + uint32_t pad_len, *pad_len_ptr; + + /* This code assumes that malloc always uses at least 4-byte + * alignment. + */ + alignment = (uintptr_t)align; + total_length = ((uintptr_t)length) + alignment; + malloc_addr = (uintptr_t)malloc(total_length); + mem_addr = (malloc_addr + alignment) & ~(alignment - 1); + pad_len = (uint32_t)(mem_addr - malloc_addr); + pad_len_ptr = (uint32_t *)(mem_addr - 4); + *pad_len_ptr = pad_len; + return (void *)mem_addr; +} + +static void aligned_free(void *mem_ptr) +{ + uintptr_t mem_addr, malloc_addr; + uint32_t *pad_len_ptr; + + mem_addr = (uintptr_t)mem_ptr; + pad_len_ptr = (uint32_t *)(mem_addr - 4); + malloc_addr = mem_addr - *pad_len_ptr; + free((void *)malloc_addr); +} + +static uint32_t hash_name_and_kind(char *name, uint8_t name_kind) +{ + PLATFORM_HASH_STATE hash_state; + uint32_t name_len, name_word, hash_value; + + name_len = strlen(name); + PLATFORM_HASH32_INIT(hash_state, name_len); + + while (4 <= name_len) { + /* Get the next four characters. Note that endianness doesn't + * matter here! Also note that this assumes that there is + * either no alignment loading restrictions OR that name is + * 32-bit aligned. Shouldn't be too hard to add code to deal + * with the case when this assumption is false. + */ + name_word = *((uint32_t *)name); + PLATFORM_HASH32(hash_state, name_word); + + name_len -= 4; + name += 4; + } + + if (name_len != 0) { + name_word = 0; + + if (2 <= name_len) { + name_word = (uint32_t)*((uint16_t *)name); + name_len -= 2; + name += 2; + } + + if (name_len == 1) + name_word |= ((uint32_t)*name) << 16; + + PLATFORM_HASH32(hash_state, name_word); + } + + hash_value = PLATFORM_HASH32_FINISH(hash_state, name_kind); + return hash_value; +} + +static uint32_t linked_list_len(name_tbl_entry_t *name_tbl_entry) +{ + uint32_t count; + + count = 0; + while (name_tbl_entry) { + count++; + name_tbl_entry = name_tbl_entry->next_entry; + } + + return count; +} + +static secondary_hash_tbl_t *secondary_hash_tbl_alloc(void) +{ + secondary_hash_tbl_t *secondary_hash_tbl; + + secondary_hash_tbl = aligned_malloc(sizeof(secondary_hash_tbl_t), + ODP_CACHE_LINE_SIZE); + memset(secondary_hash_tbl, 0, sizeof(secondary_hash_tbl_t)); + return secondary_hash_tbl; +} + +static void secondary_hash_tbl_free(secondary_hash_tbl_t *secondary_hash_tbl) +{ + aligned_free(secondary_hash_tbl); +} + +static void check_secondary_hash(secondary_hash_tbl_t *secondary_hash_tbl) +{ + hash_tbl_entry_t hash_tbl_entry, hash_tbl_entry2; + uint64_t tbn1, tbn2; + uint32_t idx, idx2; + + for (idx = 0; idx < SECONDARY_HASH_TBL_SIZE; idx++) { + hash_tbl_entry = secondary_hash_tbl->hash_entries[idx]; + tbn1 = hash_tbl_entry & ~0x3F; + + if (hash_tbl_entry != 0) { + if ((hash_tbl_entry >> 48) == 0x7FFF) + ; + else if ((hash_tbl_entry >> 48) == 0) + ; + else + abort(); + + for (idx2 = 0; idx2 < idx; idx2++) { + hash_tbl_entry2 = + secondary_hash_tbl->hash_entries[idx2]; + if (hash_tbl_entry2 != 0) { + tbn2 = hash_tbl_entry2 & ~0x3F; + if (tbn1 == tbn2) + abort(); + } + } + } + } +} + +#ifdef NOT_USED /* @todo */ +static void secondary_hash_dump(secondary_hash_tbl_t *secondary_hash_tbl) +{ + name_tbl_entry_t *name_tbl_entry; + hash_tbl_entry_t hash_tbl_entry; + uint32_t count, idx, entry_cnt, list_cnt; + + count = 0; + for (idx = 0; idx < SECONDARY_HASH_TBL_SIZE; idx++) { + hash_tbl_entry = secondary_hash_tbl->hash_entries[idx]; + if (hash_tbl_entry != 0) { + if ((hash_tbl_entry & 0x3F) != 0) { + name_tbl_entry = (name_tbl_entry_t *) + (hash_tbl_entry & ~0x3F); + entry_cnt = hash_tbl_entry & 0x3F; + list_cnt = linked_list_len(name_tbl_entry); + if (entry_cnt != list_cnt) + ODP_DBG("%s idx=%u entry_cnt=%u " + "list_cnt=%u\n", + __func__, + idx, entry_cnt, list_cnt); + + count += entry_cnt; + } else { + ODP_DBG("%s inner secondary tbl\n", + __func__); + } + } + } + + ODP_DBG("%s count=%u\n", __func__, count); +} +#endif + +static uint32_t name_tbl_free_list_add(name_tbl_t *name_tbl, + uint32_t num_to_add) +{ + uint32_t first_idx, name_tbl_id, entry_idx, num_added, cnt; + + first_idx = name_tbl->num_added_to_free_list; + name_tbl_id = name_tbl->base_id | first_idx; + entry_idx = first_idx; + + num_added = MIN(num_to_add, name_tbl->num_avail_to_add); + if (num_added == 0) + return 0; + + for (cnt = 1; cnt < num_added; cnt++) { + name_tbl->entries[entry_idx].name_tbl_id = name_tbl_id; + name_tbl->entries[entry_idx].next_entry = + &name_tbl->entries[entry_idx + 1]; + name_tbl_id++; + entry_idx++; + } + + name_tbl->entries[entry_idx].name_tbl_id = name_tbl_id; + name_tbl->entries[entry_idx].next_entry = name_tbl->free_list_head; + + name_tbl->free_list_head = &name_tbl->entries[first_idx]; + name_tbl->num_added_to_free_list += num_added; + name_tbl->num_avail_to_add -= num_added; + return num_added; +} + +static name_tbl_t *name_tbl_alloc(uint32_t name_tbls_idx, uint32_t num_entries) +{ + name_tbl_t *name_tbl; + uint32_t name_tbl_size; + + name_tbl_size = sizeof(name_tbl_t) + + num_entries * sizeof(name_tbl_entry_t); + name_tbl = aligned_malloc(name_tbl_size, ODP_CACHE_LINE_SIZE); + memset(name_tbl, 0, name_tbl_size); + + name_tbl->num_allocd = num_entries; + name_tbl->num_used = 0; + name_tbl->num_added_to_free_list = 0; + name_tbl->num_avail_to_add = num_entries; + name_tbl->free_list_head = NULL; + name_tbl->base_id = (name_tbls_idx + 1) << 26; + return name_tbl; +} + +static int new_name_tbl_add(void) +{ + name_tbl_t *new_name_tbl; + uint32_t name_tbls_idx, num_entries; + + if (NUM_NAME_TBLS <= name_tbls.num_name_tbls) + return -1; + + name_tbls_idx = name_tbls.num_name_tbls; + num_entries = INITIAL_NAME_TBL_SIZE << name_tbls_idx; + new_name_tbl = name_tbl_alloc(name_tbls_idx, num_entries); + name_tbl_free_list_add(new_name_tbl, MIN(num_entries, 256)); + + name_tbls.tbls[name_tbls_idx] = new_name_tbl; + name_tbls.avail_space_bit_mask |= 1 << name_tbls_idx; + name_tbls.num_name_tbls++; + return 0; +} + +static name_tbl_entry_t *name_tbl_entry_alloc(void) +{ + name_tbl_entry_t *name_tbl_entry; + name_tbl_t *name_tbl; + uint32_t name_tbls_idx, num_added; + int rc; + + /* If avail_space_bit_mask == 0 then we need to make a new name_tbl. */ + if (name_tbls.avail_space_bit_mask == 0) { + rc = new_name_tbl_add(); + if (rc < 0) + return NULL; + } + + /* Find first bit set in avail_space_bit_mask. */ + name_tbls_idx = __builtin_ctzl(name_tbls.avail_space_bit_mask); + name_tbl = name_tbls.tbls[name_tbls_idx]; + + name_tbl_entry = name_tbl->free_list_head; + name_tbl->free_list_head = name_tbl_entry->next_entry; + name_tbl->num_used++; + + if (!name_tbl->free_list_head) { + num_added = name_tbl_free_list_add(name_tbl, 256); + if (num_added == 0) + name_tbls.avail_space_bit_mask ^= 1 << name_tbls_idx; + } + + return name_tbl_entry; +} + +static name_tbl_entry_t *name_tbl_id_parse(odp_int_name_t name_tbl_id, + name_tbl_t **name_tbl_ptr) +{ + name_tbl_t *name_tbl; + uint32_t name_tbls_idx, name_tbl_idx; + + /* Convert the name_tbl_id into a name_tbls_idx and name_tbl_idx */ + if (name_tbl_id == ODP_INVALID_NAME) + return NULL; + + name_tbls_idx = (((uint32_t)name_tbl_id) >> 26) - 1; + name_tbl_idx = ((uint32_t)name_tbl_id) & 0x03FFFFFF; + if (name_tbls.num_name_tbls < name_tbls_idx) + return NULL; + + name_tbl = name_tbls.tbls[name_tbls_idx]; + if (!name_tbl) + return NULL; + + if (name_tbl->num_used < name_tbl_idx) + return NULL; + + if (name_tbl_ptr) + *name_tbl_ptr = name_tbl; + + return &name_tbl->entries[name_tbl_idx]; +} + +static void name_tbl_entry_free(name_tbl_entry_t *name_tbl_entry) +{ + name_tbl_entry_t *entry; + odp_int_name_t name_tbl_id; + name_tbl_t *name_tbl; + + name_tbl_id = name_tbl_entry->name_tbl_id; + entry = name_tbl_id_parse(name_tbl_id, &name_tbl); + if (!entry) + return; + + memset(name_tbl_entry, 0, sizeof(name_tbl_entry_t)); + name_tbl_entry->next_entry = name_tbl->free_list_head; + name_tbl->free_list_head = name_tbl_entry; +} + +static hash_tbl_entry_t make_hash_tbl_entry(name_tbl_entry_t *name_tbl_entry, + uint32_t entry_cnt) +{ + hash_tbl_entry_t hash_tbl_entry; + uint32_t new_entry_cnt; + + new_entry_cnt = MIN(entry_cnt + 1, 0x3F); + hash_tbl_entry = (hash_tbl_entry_t)name_tbl_entry; + hash_tbl_entry &= ~0x3F; + hash_tbl_entry |= new_entry_cnt; + return hash_tbl_entry; +} + +static name_tbl_entry_t *name_hash_tbl_lookup(uint32_t hash_value) +{ + secondary_hash_tbl_t *secondary_hash; + hash_tbl_entry_t hash_tbl_entry; + uint32_t hash_idx; + + hash_idx = hash_value & (PRIMARY_HASH_TBL_SIZE - 1); + hash_tbl_entry = name_hash_tbl.hash_entries[hash_idx]; + if (hash_tbl_entry == 0) + return NULL; + else if ((hash_tbl_entry & 0x3F) != 0) + return (name_tbl_entry_t *)(hash_tbl_entry & ~0x3F); + + /* This hash_tbl_entry references a secondary hash table, so get + * some more hash_value bits and index that table. + */ + hash_idx = (hash_value >> 16) & (SECONDARY_HASH_TBL_SIZE - 1); + secondary_hash = (secondary_hash_tbl_t *)hash_tbl_entry; + hash_tbl_entry = secondary_hash->hash_entries[hash_idx]; + if (hash_tbl_entry == 0) + return NULL; + else if ((hash_tbl_entry & 0x3F) != 0) + return (name_tbl_entry_t *)(hash_tbl_entry & ~0x3F); + + /* Yet again, this hash_tbl_entry references a secondary hash table, + * so get some more hash_value bits and index that table. We only + * allow two secondary tables in the path, so if this hash_tbl_entry + * doesn't point to a name_tbl_entry then we signal failure by + * returning NULL. + */ + hash_idx = (hash_value >> 24) & (SECONDARY_HASH_TBL_SIZE - 1); + secondary_hash = (secondary_hash_tbl_t *)hash_tbl_entry; + hash_tbl_entry = secondary_hash->hash_entries[hash_idx]; + if (hash_tbl_entry == 0) + return NULL; + else if ((hash_tbl_entry & 0x3F) != 0) + return (name_tbl_entry_t *)(hash_tbl_entry & ~0x3F); + + return NULL; +} + +static name_tbl_entry_t *internal_name_lookup(char *name, + uint8_t name_kind) +{ + name_tbl_entry_t *name_tbl_entry; + uint32_t hash_value, name_len; + + hash_value = hash_name_and_kind(name, name_kind); + name_len = strlen(name); + + name_tbl_entry = name_hash_tbl_lookup(hash_value); + while (name_tbl_entry) { + if ((name_tbl_entry->name_kind == name_kind) && + (name_tbl_entry->name_len == name_len) && + (memcmp(name_tbl_entry->name, name, name_len) == 0)) + return name_tbl_entry; + + name_tbl_entry = name_tbl_entry->next_entry; + } + + return NULL; +} + +static hash_tbl_entry_t secondary_hash_add(name_tbl_entry_t *name_tbl_entry, + uint32_t level, /* 0 or 1 */ + uint32_t hash_shift) +{ + secondary_hash_tbl_t *secondary_hash; + name_tbl_entry_t *next_entry, *first_entry; + hash_tbl_entry_t hash_tbl_entry, new_hash_tbl_entry; + uint32_t shifted_hash_value, hash_idx, entry_cnt; + + secondary_hash = secondary_hash_tbl_alloc(); + name_hash_tbl.num_secondary_tbls[level]++; + while (name_tbl_entry) { + next_entry = name_tbl_entry->next_entry; + shifted_hash_value = name_tbl_entry->hash_value >> hash_shift; + hash_idx = shifted_hash_value & + (SECONDARY_HASH_TBL_SIZE - 1); + + hash_tbl_entry = secondary_hash->hash_entries[hash_idx]; + entry_cnt = hash_tbl_entry & 0x3F; + first_entry = (name_tbl_entry_t *)(hash_tbl_entry & ~0x3F); + + name_tbl_entry->next_entry = first_entry; + new_hash_tbl_entry = + make_hash_tbl_entry(name_tbl_entry, entry_cnt); + + secondary_hash->hash_entries[hash_idx] = new_hash_tbl_entry; + name_tbl_entry = next_entry; + } + + /* secondary_hash_dump(secondary_hash); */ + return (hash_tbl_entry_t)secondary_hash; +} + +static hash_tbl_entry_t hash_tbl_remove(secondary_hash_tbl_t *hash_tbl, + uint32_t level, /* 0 or 1 */ + name_tbl_entry_t **list_head_ptr, + name_tbl_entry_t **list_tail_ptr) +{ + secondary_hash_tbl_t *secondary_hash; + name_tbl_entry_t *linked_list_head, *linked_list_tail; + name_tbl_entry_t *head_entry, *tail_entry; + hash_tbl_entry_t hash_tbl_entry; + uint32_t idx, entry_cnt; + + check_secondary_hash(hash_tbl); + linked_list_head = NULL; + linked_list_tail = NULL; + + for (idx = 0; idx < SECONDARY_HASH_TBL_SIZE; idx++) { + hash_tbl_entry = hash_tbl->hash_entries[idx]; + if (hash_tbl_entry != 0) { + if ((hash_tbl_entry & 0x3F) != 0) { + /* This secondar hash table points to a + * name_tbl_entry_t linked list, so add this + * new entry onto the front of it. + */ + head_entry = (name_tbl_entry_t *) + (hash_tbl_entry & ~0x3F); + tail_entry = head_entry; + } else { + secondary_hash = (secondary_hash_tbl_t *) + hash_tbl_entry; + check_secondary_hash(secondary_hash); + if (level == 1) + break; + + hash_tbl_remove(secondary_hash, level + 1, + &head_entry, &tail_entry); + } + + /* Now concate lists. */ + if (!linked_list_tail) { + linked_list_head = head_entry; + linked_list_tail = tail_entry; + } else { + linked_list_tail->next_entry = head_entry; + linked_list_tail = tail_entry; + } + } + } + + if (list_head_ptr) + *list_head_ptr = linked_list_head; + + if (list_tail_ptr) + *list_tail_ptr = linked_list_tail; + + secondary_hash_tbl_free(hash_tbl); + if (name_hash_tbl.num_secondary_tbls[level] != 0) + name_hash_tbl.num_secondary_tbls[level]--; + + entry_cnt = linked_list_len(linked_list_head); + if ((!linked_list_head) || (entry_cnt == 0)) + return 0; + + hash_tbl_entry = make_hash_tbl_entry(linked_list_head, entry_cnt - 1); + return hash_tbl_entry; +} + +static int name_hash_tbl_add(name_tbl_entry_t *entry_to_add, + uint32_t hash_value) +{ + secondary_hash_tbl_t *secondary_hash; + name_tbl_entry_t *name_tbl_entry; + hash_tbl_entry_t hash_tbl_entry; + uint32_t primary_hash_idx, hash_idx, collisions, entry_cnt; + + primary_hash_idx = hash_value & (PRIMARY_HASH_TBL_SIZE - 1); + hash_tbl_entry = name_hash_tbl.hash_entries[primary_hash_idx]; + entry_cnt = hash_tbl_entry & 0x3F; + name_hash_tbl.hash_collisions[primary_hash_idx]++; + if (hash_tbl_entry == 0) { + /* This primary hash table entry points to an empty bucket, so + * start a new name_tbl_entry_t linked list. + */ + hash_tbl_entry = make_hash_tbl_entry(entry_to_add, 0); + name_hash_tbl.hash_entries[primary_hash_idx] = hash_tbl_entry; + return 0; + } else if (entry_cnt != 0) { + /* This primary hash table entry points to a name_tbl_entry_t + * linked list, so add this new entry onto the front of it. + */ + name_tbl_entry = (name_tbl_entry_t *)(hash_tbl_entry & ~0x3F); + entry_to_add->next_entry = name_tbl_entry; + hash_tbl_entry = make_hash_tbl_entry(entry_to_add, entry_cnt); + name_hash_tbl.hash_entries[primary_hash_idx] = hash_tbl_entry; + + /* See if there are enough hash collisions within this hash + * bucket to justify replacing the linked list with a + * secondary hash table. + */ + collisions = name_hash_tbl.hash_collisions[primary_hash_idx]; + if (collisions <= MAX_PRIMARY_LIST_SIZE) + return 0; + + /* Replace the current linked list with a secondary hash + * table. + */ + hash_tbl_entry = secondary_hash_add(entry_to_add, 0, 16); + name_hash_tbl.hash_entries[primary_hash_idx] = hash_tbl_entry; + return 0; + } + + /* This hash_tbl_entry references a secondary hash table, so get + * some more hash_value bits and index that table. + */ + hash_idx = (hash_value >> 16) & (SECONDARY_HASH_TBL_SIZE - 1); + secondary_hash = (secondary_hash_tbl_t *)hash_tbl_entry; + check_secondary_hash(secondary_hash); + hash_tbl_entry = secondary_hash->hash_entries[hash_idx]; + entry_cnt = hash_tbl_entry & 0x3F; + if (hash_tbl_entry == 0) { + /* This secondary hash table entry points to an empty bucket, + * so start a new name_tbl_entry_t linked list. + */ + hash_tbl_entry = make_hash_tbl_entry(entry_to_add, 0); + secondary_hash->hash_entries[hash_idx] = hash_tbl_entry; + return 0; + } else if (entry_cnt != 0) { + /* This secondary hash table entry points to a + * name_tbl_entry_t linked list, so add this new entry onto + * the front of it. + */ + name_tbl_entry = (name_tbl_entry_t *)(hash_tbl_entry & ~0x3F); + entry_to_add->next_entry = name_tbl_entry; + hash_tbl_entry = make_hash_tbl_entry(entry_to_add, entry_cnt); + secondary_hash->hash_entries[hash_idx] = hash_tbl_entry; + + /* See if there are enough hash collisions within this + * secondary hash bucket to justify replacing the linked list + * with yet another secondary hash table. + */ + if (entry_cnt < MAX_SECONDARY_LIST_SIZE) + return 0; + + /* Replace the current linked list with a secondary hash + * table. + */ + hash_tbl_entry = secondary_hash_add(entry_to_add, 1, 24); + secondary_hash->hash_entries[hash_idx] = hash_tbl_entry; + check_secondary_hash(secondary_hash); + return 0; + } + + /* Yet again, this (secondary) hash_tbl_entry references a level 2 + * secondary hash table, so get some more hash_value bits and index + * that table. We only allow two secondary tables in the path, so if + * this hash_tbl_entry doesn't point to a name_tbl_entry then we + * signal failure by returning -1. + */ + hash_idx = (hash_value >> 24) & (SECONDARY_HASH_TBL_SIZE - 1); + secondary_hash = (secondary_hash_tbl_t *)hash_tbl_entry; + check_secondary_hash(secondary_hash); + hash_tbl_entry = secondary_hash->hash_entries[hash_idx]; + entry_cnt = hash_tbl_entry & 0x3F; + if (hash_tbl_entry == 0) { + /* This secondary hash table entry points to an empty bucket, + * so start a new name_tbl_entry_t linked list. + */ + hash_tbl_entry = make_hash_tbl_entry(entry_to_add, 0); + secondary_hash->hash_entries[hash_idx] = hash_tbl_entry; + check_secondary_hash(secondary_hash); + return 0; + } else if (entry_cnt != 0) { + /* This secondary hash table entry points to a + * name_tbl_entry_t linked list, so add this new entry onto + * the front of it. Note that regardless of the size of this + * linked list, we never add another hash table, so we don't + * need to update any secondary table counts. + */ + name_tbl_entry = (name_tbl_entry_t *)(hash_tbl_entry & ~0x3F); + entry_to_add->next_entry = name_tbl_entry; + hash_tbl_entry = make_hash_tbl_entry(entry_to_add, entry_cnt); + secondary_hash->hash_entries[hash_idx] = hash_tbl_entry; + check_secondary_hash(secondary_hash); + return 0; + } + + name_hash_tbl.hash_collisions[primary_hash_idx]--; + return -1; +} + +static int name_tbl_entry_list_remove(hash_tbl_entry_t *hash_entry_ptr, + name_tbl_entry_t *linked_list, + name_tbl_entry_t *entry_to_delete, + uint32_t entry_cnt) +{ + name_tbl_entry_t *name_tbl_entry, *prev_entry, *next_entry; + hash_tbl_entry_t hash_tbl_entry; + + name_tbl_entry = linked_list; + prev_entry = NULL; + while (name_tbl_entry) { + next_entry = name_tbl_entry->next_entry; + if (name_tbl_entry == entry_to_delete) { + /* We have found the name_tbl_entry that is to be + * deleted. + */ + if (!prev_entry) { + hash_tbl_entry = (hash_tbl_entry_t)next_entry; + hash_tbl_entry &= ~0x3F; + hash_tbl_entry |= entry_cnt; + *hash_entry_ptr = hash_tbl_entry; + } else { + prev_entry->next_entry = next_entry; + } + + /* Now decrement the entry_cnt field - if in the range + * 1 - 0x3E + */ + if ((entry_cnt != 0) && (entry_cnt < 0x3F)) + *hash_entry_ptr = (*hash_entry_ptr) - 1; + + return 0; + } + + prev_entry = name_tbl_entry; + name_tbl_entry = next_entry; + } + + return -2; +} + +static int name_hash_tbl_delete(name_tbl_entry_t *entry_to_delete, + uint32_t hash_value) +{ + secondary_hash_tbl_t *secondary_hash; + hash_tbl_entry_t *hash_entry_ptr, hash_tbl_entry; + name_tbl_entry_t *name_tbl_entry; + uint64_t tbn; + uint32_t primary_hash_idx, hash_idx, collisions, entry_cnt; + int rc; + + primary_hash_idx = hash_value & (PRIMARY_HASH_TBL_SIZE - 1); + hash_entry_ptr = &name_hash_tbl.hash_entries[primary_hash_idx]; + hash_tbl_entry = *hash_entry_ptr; + entry_cnt = hash_tbl_entry & 0x3F; + if (hash_tbl_entry == 0) { + /* This primary hash table entry points to an empty bucket, so + * we have failed to find the matching entry. + */ + return -1; + } else if (entry_cnt != 0) { + /* This primary hash table entry points to a name_tbl_entry_t + * linked list, so remove entry from this linked list. + */ + name_tbl_entry = (name_tbl_entry_t *)(hash_tbl_entry & ~0x3F); + rc = name_tbl_entry_list_remove(hash_entry_ptr, name_tbl_entry, + entry_to_delete, entry_cnt); + tbn = (*hash_entry_ptr) & ~0x3F; + if (tbn == 0xFFFFFFFFFFFFFFC0) + abort(); + + if (rc < 0) + return rc; + + name_hash_tbl.hash_collisions[primary_hash_idx]--; + return 0; + } + + /* This hash_tbl_entry references a secondary hash table, so get + * some more hash_value bits and index that table. + */ + hash_idx = (hash_value >> 16) & (SECONDARY_HASH_TBL_SIZE - 1); + secondary_hash = (secondary_hash_tbl_t *)hash_tbl_entry; + check_secondary_hash(secondary_hash); + hash_entry_ptr = &secondary_hash->hash_entries[hash_idx]; + hash_tbl_entry = *hash_entry_ptr; + entry_cnt = hash_tbl_entry & 0x3F; + if (hash_tbl_entry == 0) { + /* This secondary hash table entry points to an empty bucket, + * so we have failed to find the matching entry. + */ + return -1; + } else if (entry_cnt != 0) { + /* This secondary hash table entry points to a + * name_tbl_entry_t linked list, so try to remove + * entry_to_delete from this linked list. + */ + name_tbl_entry = (name_tbl_entry_t *)(hash_tbl_entry & ~0x3F); + rc = name_tbl_entry_list_remove(hash_entry_ptr, name_tbl_entry, + entry_to_delete, entry_cnt); + tbn = (*hash_entry_ptr) & ~0x3F; + if (tbn == 0xFFFFFFFFFFFFFFC0) + abort(); + + check_secondary_hash(secondary_hash); + if (rc < 0) + return rc; + + name_hash_tbl.hash_collisions[primary_hash_idx]--; + + /* See if we should replace this secondary hash table with a + * linked list. + */ + collisions = name_hash_tbl.hash_collisions[primary_hash_idx]; + if (MIN_SECONDARY_TBL_SIZE < collisions) + return 0; + + /* Replace the secondary hash table with a linked list. */ + hash_tbl_entry = hash_tbl_remove(secondary_hash, 0, NULL, NULL); + name_hash_tbl.hash_entries[primary_hash_idx] = hash_tbl_entry; + return 0; + } + + /* Yet again, this (secondary) hash_tbl_entry references a level 2 + * secondary hash table, so get some more hash_value bits and index + * that table. We only allow two secondary tables in the path, so if + * this hash_tbl_entry doesn't point to a name_tbl_entry then we + * signal failure by returning -1. + */ + hash_idx = (hash_value >> 24) & (SECONDARY_HASH_TBL_SIZE - 1); + secondary_hash = (secondary_hash_tbl_t *)hash_tbl_entry; + check_secondary_hash(secondary_hash); + hash_entry_ptr = &secondary_hash->hash_entries[hash_idx]; + hash_tbl_entry = *hash_entry_ptr; + entry_cnt = hash_tbl_entry & 0x3F; + if (hash_tbl_entry == 0) { + /* This secondary hash table entry points to an empty bucket, + * so we have failed to find the matching entry. + */ + return -1; + } else if (entry_cnt != 0) { + /* This secondary hash table entry points to a + * name_tbl_entry_t linked list, so try to remove + * entry_to_delete from this linked list. + */ + name_tbl_entry = (name_tbl_entry_t *)(hash_tbl_entry & ~0x3F); + rc = name_tbl_entry_list_remove(hash_entry_ptr, name_tbl_entry, + entry_to_delete, entry_cnt); + tbn = (*hash_entry_ptr) & ~0x3F; + if (tbn == 0xFFFFFFFFFFFFFFC0) + abort(); + + check_secondary_hash(secondary_hash); + if (rc < 0) + return rc; + + name_hash_tbl.hash_collisions[primary_hash_idx]--; + check_secondary_hash(secondary_hash); + return 0; + } + + return -1; +} + +odp_int_name_t odp_int_name_tbl_add(char *name, + uint8_t name_kind, + uint64_t user_data) +{ + name_tbl_entry_t *name_tbl_entry; + uint32_t hash_value, name_len; + int rc; + + /* Check for name_tbls_initialized. */ + if (name_tbls_initialized == 0) + return ODP_INVALID_NAME; + + /* Check for NULL names or zero length names. */ + if ((!name) || (name[0] == '\0')) + return ODP_INVALID_NAME; + + /* Check for names that are too long. */ + name_len = strlen(name); + if (ODP_INT_NAME_LEN < name_len) + return ODP_INVALID_NAME; + + /* Next lookup the pair to make sure it doesn't + * already exist. + */ + odp_ticketlock_lock(&name_table_lock); + name_tbl_entry = internal_name_lookup(name, name_kind); + if (name_tbl_entry) { + odp_ticketlock_unlock(&name_table_lock); + return ODP_INVALID_NAME; + } + + /* Allocate a name_tbl_entry record.*/ + name_len = strlen(name); + name_tbl_entry = name_tbl_entry_alloc(); + if (!name_tbl_entry) { + odp_ticketlock_unlock(&name_table_lock); + return ODP_INVALID_NAME; + } + + hash_value = hash_name_and_kind(name, name_kind); + name_tbl_entry->next_entry = NULL; + name_tbl_entry->user_data = user_data; + name_tbl_entry->hash_value = hash_value; + name_tbl_entry->name_kind = name_kind; + name_tbl_entry->name_len = name_len; + memcpy(name_tbl_entry->name, name, name_len); + name_tbl_entry->name[name_len] = '\0'; + + rc = name_hash_tbl_add(name_tbl_entry, hash_value); + if (rc < 0) { + name_tbl_entry_free(name_tbl_entry); + odp_ticketlock_unlock(&name_table_lock); + return ODP_INVALID_NAME; + } + + name_tbls.num_adds++; + name_tbls.current_num_names++; + odp_ticketlock_unlock(&name_table_lock); + return name_tbl_entry->name_tbl_id; +} + +int odp_int_name_tbl_delete(odp_int_name_t odp_name) +{ + name_tbl_entry_t *entry_to_delete; + int rc; + + /* Check for name_tbls_initialized. */ + if (name_tbls_initialized == 0) + return -3; + + entry_to_delete = name_tbl_id_parse(odp_name, NULL); + if (!entry_to_delete) + return -1; + + /* First disconnect this entry from its hash bucket linked list. */ + odp_ticketlock_lock(&name_table_lock); + rc = name_hash_tbl_delete(entry_to_delete, entry_to_delete->hash_value); + if (0 <= rc) { + name_tbls.num_deletes++; + if (name_tbls.current_num_names != 0) + name_tbls.current_num_names--; + + name_tbl_entry_free(entry_to_delete); + } + + odp_ticketlock_unlock(&name_table_lock); + return rc; +} + +const char *odp_int_name_tbl_name(odp_int_name_t odp_name) +{ + name_tbl_entry_t *name_tbl_entry; + + name_tbl_entry = name_tbl_id_parse(odp_name, NULL); + if (!name_tbl_entry) + return NULL; + else + return name_tbl_entry->name; +} + +uint64_t odp_int_name_tbl_user_data(odp_int_name_t odp_name) +{ + name_tbl_entry_t *name_tbl_entry; + + name_tbl_entry = name_tbl_id_parse(odp_name, NULL); + if (!name_tbl_entry) + return 0; /* @todo */ + else + return name_tbl_entry->user_data; +} + +odp_int_name_t odp_int_name_tbl_lookup(char *name, uint8_t name_kind) +{ + name_tbl_entry_t *name_tbl_entry; + odp_int_name_t name_tbl_id; + + /* Check for name_tbls_initialized. */ + if (name_tbls_initialized == 0) + return ODP_INVALID_NAME; + + /* Check for NULL names or zero length names. */ + name_tbl_id = ODP_INVALID_NAME; + if ((!name) || (name[0] == '\0')) + return name_tbl_id; + + odp_ticketlock_lock(&name_table_lock); + name_tbl_entry = internal_name_lookup(name, name_kind); + if (name_tbl_entry) + name_tbl_id = name_tbl_entry->name_tbl_id; + odp_ticketlock_unlock(&name_table_lock); + + return name_tbl_id; +} + +#ifdef SECONDARY_HASH_HISTO_PRINT + +static uint32_t level2_hash_histo(secondary_hash_tbl_t *hash_tbl, + uint32_t level2_histo[]) +{ + name_tbl_entry_t *name_tbl_entry; + hash_tbl_entry_t hash_tbl_entry; + uint32_t idx, collisions, total_collisions; + + total_collisions = 0; + for (idx = 0; idx < SECONDARY_HASH_TBL_SIZE; idx++) { + hash_tbl_entry = hash_tbl->hash_entries[idx]; + if (hash_tbl_entry == 0) { + collisions = 0; + } else { + name_tbl_entry = (name_tbl_entry_t *) + (hash_tbl_entry & ~0x3F); + collisions = linked_list_len(name_tbl_entry); + } + + level2_histo[MIN(collisions, 256)]++; + total_collisions += collisions; + } + + return total_collisions; +} + +static uint32_t level1_hash_histo(secondary_hash_tbl_t *hash_tbl, + uint32_t level1_histo[], + uint32_t level2_histo[]) +{ + secondary_hash_tbl_t *secondary_hash; + name_tbl_entry_t *name_tbl_entry; + hash_tbl_entry_t hash_tbl_entry; + uint32_t idx, collisions, total_collisions; + + total_collisions = 0; + for (idx = 0; idx < SECONDARY_HASH_TBL_SIZE; idx++) { + hash_tbl_entry = hash_tbl->hash_entries[idx]; + if (hash_tbl_entry == 0) { + collisions = 0; + } else if ((hash_tbl_entry & 0x3F) != 0) { + name_tbl_entry = (name_tbl_entry_t *) + (hash_tbl_entry & ~0x3F); + collisions = linked_list_len(name_tbl_entry); + } else { + secondary_hash = (secondary_hash_tbl_t *) + hash_tbl_entry; + collisions = level2_hash_histo(secondary_hash, + level2_histo); + } + + level1_histo[MIN(collisions, 256)]++; + total_collisions += collisions; + } + + return total_collisions; +} + +static void secondary_hash_histo_print(void) +{ + secondary_hash_tbl_t *secondary_hash; + hash_tbl_entry_t hash_tbl_entry; + uint32_t level1_histo[257], level2_histo[257]; + uint32_t avg, idx, count, total_count; + + memset(level1_histo, 0, sizeof(level1_histo)); + memset(level2_histo, 0, sizeof(level2_histo)); + + for (idx = 0; idx < PRIMARY_HASH_TBL_SIZE; idx++) { + hash_tbl_entry = name_hash_tbl.hash_entries[idx]; + if ((hash_tbl_entry != 0) && ((hash_tbl_entry & 0x3F) == 0)) { + /* This hash_tbl_entry references a level 0 secondary + * hash table + */ + secondary_hash = (secondary_hash_tbl_t *) + hash_tbl_entry; + level1_hash_histo(secondary_hash, level1_histo, + level2_histo); + } + } + + if (name_hash_tbl.num_secondary_tbls[0] == 0) + return; + + ODP_DBG(" level1 secondary hash histogram:\n"); + total_count = 0; + for (idx = 0; idx < 256; idx++) { + count = level1_histo[idx]; + if (idx != 0) + total_count += count * idx; + + if (count != 0) + ODP_DBG(" num collisions=%02u count=%u\n", + idx, count); + } + + count = level1_histo[256]; + total_count += count; + if (count != 0) + ODP_DBG(" num collisions >=256 count=%u\n", count); + + avg = (100 * total_count) / name_hash_tbl.num_secondary_tbls[0]; + avg = avg / SECONDARY_HASH_TBL_SIZE; + ODP_DBG(" avg collisions=%02u.%02u total=%u\n\n", + avg / 100, avg % 100, total_count); + + if (name_hash_tbl.num_secondary_tbls[1] == 0) + return; + + ODP_DBG(" level2 secondary hash histogram:\n"); + total_count = 0; + for (idx = 0; idx < 256; idx++) { + count = level2_histo[idx]; + if (idx != 0) + total_count += count * idx; + + if (count != 0) + ODP_DBG(" num collisions=%02u count=%u\n", + idx, count); + } + + count = level2_histo[256]; + total_count += count; + if (count != 0) + ODP_DBG(" num collisions >=256 count=%u\n", count); + + avg = (100 * total_count) / name_hash_tbl.num_secondary_tbls[1]; + avg = avg / SECONDARY_HASH_TBL_SIZE; + ODP_DBG(" avg collisions=%02u.%02u total=%u\n\n", + avg / 100, avg % 100, total_count); +} + +#endif + +void odp_int_name_tbl_stats_print(void) +{ + name_tbl_t *name_tbl; + uint32_t primary_hash_histo[257], idx, collisions, + count, total_count; + uint32_t avg; + + ODP_DBG("\nname table stats:\n"); + ODP_DBG(" num_names=%u num_adds=%lu " + "num_deletes=%lu num_name_tbls=%u\n", + name_tbls.current_num_names, name_tbls.num_adds, + name_tbls.num_deletes, name_tbls.num_name_tbls); + for (idx = 0; idx < NUM_NAME_TBLS; idx++) { + name_tbl = name_tbls.tbls[idx]; + if ((name_tbl) && (name_tbl->num_used != 0)) + ODP_DBG(" name_tbl %u num_allocd=%7u " + "num_added_to_free_list=%7u " + "num_used=%7u num_avail_to_add=%7u\n", idx, + name_tbl->num_allocd, + name_tbl->num_added_to_free_list, + name_tbl->num_used, + name_tbl->num_avail_to_add); + } + + memset(primary_hash_histo, 0, sizeof(primary_hash_histo)); + for (idx = 0; idx < PRIMARY_HASH_TBL_SIZE; idx++) { + collisions = MIN(name_hash_tbl.hash_collisions[idx], 256); + primary_hash_histo[collisions]++; + } + + ODP_DBG(" name_tbl primary hash histogram:\n"); + total_count = 0; + for (idx = 0; idx < 256; idx++) { + count = primary_hash_histo[idx]; + if (idx != 0) + total_count += count * idx; + + if (count != 0) + ODP_DBG(" num collisions=%02u count=%u\n", + idx, count); + } + + count = primary_hash_histo[256]; + total_count += count; + if (count != 0) + ODP_DBG(" num collisions >=256 count=%u\n", count); + + avg = (100 * total_count) / PRIMARY_HASH_TBL_SIZE; + ODP_DBG(" avg collisions=%02u.%02u total=%u\n\n", + avg / 100, avg % 100, total_count); + + ODP_DBG(" num of first level secondary hash tbls=%u " + "second level tbls=%u\n", + name_hash_tbl.num_secondary_tbls[0], + name_hash_tbl.num_secondary_tbls[1]); + +#ifdef SECONDARY_HASH_HISTO_PRINT + if (name_hash_tbl.num_secondary_tbls[0] != 0) + secondary_hash_histo_print(); +#endif +} + +void odp_int_name_tbl_init(void) +{ + name_tbl_t *new_name_tbl; + + memset(&name_hash_tbl, 0, sizeof(name_hash_tbl)); + odp_ticketlock_init(&name_table_lock); + + memset(&name_tbls, 0, sizeof(name_tbls)); + new_name_tbl = name_tbl_alloc(0, INITIAL_NAME_TBL_SIZE); + name_tbl_free_list_add(new_name_tbl, INITIAL_NAME_TBL_SIZE); + + name_tbls.tbls[0] = new_name_tbl; + name_tbls.avail_space_bit_mask |= 1; + name_tbls.num_name_tbls = 1; + name_tbls_initialized = 1; +}