diff options
Diffstat (limited to 'src/vppinfra')
-rw-r--r-- | src/vppinfra/CMakeLists.txt | 8 | ||||
-rw-r--r-- | src/vppinfra/cJSON.c | 185 | ||||
-rw-r--r-- | src/vppinfra/cJSON.h | 23 | ||||
-rw-r--r-- | src/vppinfra/crypto/sha2.h | 494 | ||||
-rw-r--r-- | src/vppinfra/format.h | 6 | ||||
-rw-r--r-- | src/vppinfra/heap.c | 1 | ||||
-rw-r--r-- | src/vppinfra/mhash.c | 52 | ||||
-rw-r--r-- | src/vppinfra/mhash.h | 5 | ||||
-rw-r--r-- | src/vppinfra/pmalloc.c | 45 | ||||
-rw-r--r-- | src/vppinfra/test/compress.c | 60 | ||||
-rw-r--r-- | src/vppinfra/test_mhash.c | 403 | ||||
-rw-r--r-- | src/vppinfra/unformat.c | 25 | ||||
-rw-r--r-- | src/vppinfra/unix-misc.c | 95 | ||||
-rw-r--r-- | src/vppinfra/unix.h | 4 | ||||
-rw-r--r-- | src/vppinfra/vector/array_mask.h | 1 | ||||
-rw-r--r-- | src/vppinfra/vector/compress.h | 116 | ||||
-rw-r--r-- | src/vppinfra/vector/mask_compare.h | 154 |
17 files changed, 1338 insertions, 339 deletions
diff --git a/src/vppinfra/CMakeLists.txt b/src/vppinfra/CMakeLists.txt index f34ceed9d15..154e3a77cb1 100644 --- a/src/vppinfra/CMakeLists.txt +++ b/src/vppinfra/CMakeLists.txt @@ -229,7 +229,12 @@ elseif("${CMAKE_SYSTEM_NAME}" STREQUAL "FreeBSD") ) endif() -option(VPP_USE_EXTERNAL_LIBEXECINFO "Use external libexecinfo (useful for non-glibc targets)." OFF) +if("${CMAKE_SYSTEM_NAME}" STREQUAL "FreeBSD") + option(VPP_USE_EXTERNAL_LIBEXECINFO "Use external libexecinfo (useful for non-glibc targets)." ON) +else() + option(VPP_USE_EXTERNAL_LIBEXECINFO "Use external libexecinfo (useful for non-glibc targets)." OFF) +endif() + if(VPP_USE_EXTERNAL_LIBEXECINFO) set(EXECINFO_LIB execinfo) endif() @@ -260,6 +265,7 @@ if(VPP_BUILD_VPPINFRA_TESTS) longjmp macros maplog + mhash pmalloc pool_alloc pool_iterate diff --git a/src/vppinfra/cJSON.c b/src/vppinfra/cJSON.c index 448435de4dc..24e0110ed08 100644 --- a/src/vppinfra/cJSON.c +++ b/src/vppinfra/cJSON.c @@ -20,6 +20,7 @@ THE SOFTWARE. */ /* clang-format off */ + /* cJSON */ /* JSON parser in C. */ @@ -96,9 +97,9 @@ CJSON_PUBLIC(const char *) cJSON_GetErrorPtr(void) return (const char*) (global_error.json + global_error.position); } -CJSON_PUBLIC(char *) cJSON_GetStringValue(const cJSON * const item) +CJSON_PUBLIC (char *) cJSON_GetStringValue (const cJSON *const item) { - if (!cJSON_IsString(item)) + if (!cJSON_IsString (item)) { return NULL; } @@ -106,9 +107,9 @@ CJSON_PUBLIC(char *) cJSON_GetStringValue(const cJSON * const item) return item->valuestring; } -CJSON_PUBLIC(double) cJSON_GetNumberValue(const cJSON * const item) +CJSON_PUBLIC (double) cJSON_GetNumberValue (const cJSON *const item) { - if (!cJSON_IsNumber(item)) + if (!cJSON_IsNumber (item)) { return (double) NAN; } @@ -117,8 +118,9 @@ CJSON_PUBLIC(double) cJSON_GetNumberValue(const cJSON * const item) } /* This is a safeguard to prevent copy-pasters from using incompatible C and header files */ -#if (CJSON_VERSION_MAJOR != 1) || (CJSON_VERSION_MINOR != 7) || (CJSON_VERSION_PATCH != 14) - #error cJSON.h and cJSON.c have different versions. Make sure that both have the same. +#if (CJSON_VERSION_MAJOR != 1) || (CJSON_VERSION_MINOR != 7) || \ + (CJSON_VERSION_PATCH != 17) +#error cJSON.h and cJSON.c have different versions. Make sure that both have the same. #endif CJSON_PUBLIC(const char*) cJSON_Version(void) @@ -157,7 +159,7 @@ typedef struct internal_hooks { void *(CJSON_CDECL *allocate)(size_t size); void (CJSON_CDECL *deallocate)(void *pointer); - void *(CJSON_CDECL *reallocate)(void *pointer, size_t new_size, size_t old_size); + void *(CJSON_CDECL *reallocate) (void *pointer, size_t size); } internal_hooks; #if defined(_MSC_VER) @@ -170,20 +172,17 @@ static void CJSON_CDECL internal_free(void *pointer) { free(pointer); } +static void *CJSON_CDECL +internal_realloc (void *pointer, size_t size) +{ + return realloc (pointer, size); +} #else #define internal_malloc malloc #define internal_free free +#define internal_realloc realloc #endif -static void * CJSON_CDECL internal_realloc(void *pointer, size_t new_size, - size_t old_size) -{ - return realloc(pointer, new_size); -} - -static void * -cjson_realloc_internal (void *ptr, size_t new_size, size_t old_size); - /* strlen of character literals resolved at compile time */ #define static_strlen(string_literal) (sizeof(string_literal) - sizeof("")) @@ -217,8 +216,8 @@ CJSON_PUBLIC(void) cJSON_InitHooks(cJSON_Hooks* hooks) /* Reset hooks */ global_hooks.allocate = malloc; global_hooks.deallocate = free; - global_hooks.reallocate = internal_realloc; - return; + global_hooks.reallocate = realloc; + return; } global_hooks.allocate = malloc; @@ -233,16 +232,11 @@ CJSON_PUBLIC(void) cJSON_InitHooks(cJSON_Hooks* hooks) global_hooks.deallocate = hooks->free_fn; } - /* use realloc only if both free and malloc are used */ - global_hooks.reallocate = NULL; - if ((global_hooks.allocate == malloc) && (global_hooks.deallocate == free)) - { - global_hooks.reallocate = internal_realloc; - } - else - { - global_hooks.reallocate = cjson_realloc_internal; - } + global_hooks.reallocate = realloc; + if (hooks->realloc_fn != NULL) + { + global_hooks.reallocate = hooks->realloc_fn; + } } /* Internal constructor. */ @@ -405,14 +399,22 @@ CJSON_PUBLIC(double) cJSON_SetNumberHelper(cJSON *object, double number) return object->valuedouble = number; } +/* Note: when passing a NULL valuestring, cJSON_SetValuestring treats this as + * an error and return NULL */ CJSON_PUBLIC(char*) cJSON_SetValuestring(cJSON *object, const char *valuestring) { char *copy = NULL; /* if object's type is not cJSON_String or is cJSON_IsReference, it should not set valuestring */ - if (!(object->type & cJSON_String) || (object->type & cJSON_IsReference)) - { - return NULL; - } + if ((object == NULL) || !(object->type & cJSON_String) || + (object->type & cJSON_IsReference)) + { + return NULL; + } + /* return NULL if the object is corrupted or valuestring is NULL */ + if (object->valuestring == NULL || valuestring == NULL) + { + return NULL; + } if (strlen(valuestring) <= strlen(object->valuestring)) { strcpy(object->valuestring, valuestring); @@ -443,27 +445,6 @@ typedef struct internal_hooks hooks; } printbuffer; -static void * -cjson_realloc_internal (void *ptr, size_t new_size, size_t old_size) -{ - size_t copy_size; - if (old_size < new_size) - copy_size = old_size; - else - copy_size = new_size; - - unsigned char *newbuffer = global_hooks.allocate(new_size); - if (!newbuffer) - { - global_hooks.deallocate(ptr); - return NULL; - } - - memcpy (newbuffer, ptr, copy_size); - global_hooks.deallocate (ptr); - return newbuffer; -} - /* realloc printbuffer if necessary to have at least "needed" bytes more */ static unsigned char* ensure(printbuffer * const p, size_t needed) { @@ -515,14 +496,35 @@ static unsigned char* ensure(printbuffer * const p, size_t needed) newsize = needed * 2; } - newbuffer = p->hooks.reallocate (p->buffer, newsize, p->length); - if (newbuffer == NULL) - { - p->hooks.deallocate(p->buffer); - p->length = 0; - p->buffer = NULL; - return NULL; - } + if (p->hooks.reallocate != NULL) + { + /* reallocate with realloc if available */ + newbuffer = (unsigned char *) p->hooks.reallocate (p->buffer, newsize); + if (newbuffer == NULL) + { + p->hooks.deallocate (p->buffer); + p->length = 0; + p->buffer = NULL; + + return NULL; + } + } + else + { + /* otherwise reallocate manually */ + newbuffer = (unsigned char *) p->hooks.allocate (newsize); + if (!newbuffer) + { + p->hooks.deallocate (p->buffer); + p->length = 0; + p->buffer = NULL; + + return NULL; + } + + memcpy (newbuffer, p->buffer, p->offset + 1); + p->hooks.deallocate (p->buffer); + } p->length = newsize; p->buffer = newbuffer; @@ -570,6 +572,10 @@ static cJSON_bool print_number(const cJSON * const item, printbuffer * const out { length = sprintf((char*)number_buffer, "null"); } + else if (d == (double) item->valueint) + { + length = sprintf ((char *) number_buffer, "%d", item->valueint); + } else { /* Try 15 decimal places of precision to avoid nonsignificant nonzero digits */ @@ -1111,7 +1117,7 @@ CJSON_PUBLIC(cJSON *) cJSON_ParseWithLengthOpts(const char *value, size_t buffer } buffer.content = (const unsigned char*)value; - buffer.length = buffer_length; + buffer.length = buffer_length; buffer.offset = 0; buffer.hooks = global_hooks; @@ -1216,11 +1222,13 @@ static unsigned char *print(const cJSON * const item, cJSON_bool format, const i /* check if reallocate is available */ if (hooks->reallocate != NULL) { - printed = (unsigned char*) hooks->reallocate(buffer->buffer, buffer->offset + 1, default_buffer_size); - if (printed == NULL) { - goto fail; - } - buffer->buffer = NULL; + printed = (unsigned char *) hooks->reallocate (buffer->buffer, + buffer->offset + 1); + if (printed == NULL) + { + goto fail; + } + buffer->buffer = NULL; } else /* otherwise copy the JSON over to a new buffer */ { @@ -1658,8 +1666,13 @@ static cJSON_bool parse_object(cJSON * const item, parse_buffer * const input_bu current_item = new_item; } - /* parse the name of the child */ - input_buffer->offset++; + if (cannot_access_at_index (input_buffer, 1)) + { + goto fail; /* nothing comes after the comma */ + } + + /* parse the name of the child */ + input_buffer->offset++; buffer_skip_whitespace(input_buffer); if (!parse_string(current_item, input_buffer)) { @@ -2268,10 +2281,10 @@ CJSON_PUBLIC(cJSON_bool) cJSON_InsertItemInArray(cJSON *array, int which, cJSON { cJSON *after_inserted = NULL; - if (which < 0) - { - return false; - } + if (which < 0 || newitem == NULL) + { + return false; + } after_inserted = get_array_item(array, (size_t)which); if (after_inserted == NULL) @@ -2279,6 +2292,12 @@ CJSON_PUBLIC(cJSON_bool) cJSON_InsertItemInArray(cJSON *array, int which, cJSON return add_item_to_array(array, newitem); } + if (after_inserted != array->child && after_inserted->prev == NULL) + { + /* return false if after_inserted is a corrupted array item */ + return false; + } + newitem->next = after_inserted; newitem->prev = after_inserted->prev; after_inserted->prev = newitem; @@ -2295,7 +2314,8 @@ CJSON_PUBLIC(cJSON_bool) cJSON_InsertItemInArray(cJSON *array, int which, cJSON CJSON_PUBLIC(cJSON_bool) cJSON_ReplaceItemViaPointer(cJSON * const parent, cJSON * const item, cJSON * replacement) { - if ((parent == NULL) || (replacement == NULL) || (item == NULL)) + if ((parent == NULL) || (parent->child == NULL) || (replacement == NULL) || + (item == NULL)) { return false; } @@ -2365,6 +2385,11 @@ static cJSON_bool replace_item_in_object(cJSON *object, const char *string, cJSO cJSON_free(replacement->string); } replacement->string = (char*)cJSON_strdup((const unsigned char*)string, &global_hooks); + if (replacement->string == NULL) + { + return false; + } + replacement->type &= ~cJSON_StringIsConst; return cJSON_ReplaceItemViaPointer(object, get_object_item(object, string, case_sensitive), replacement); @@ -2639,9 +2664,9 @@ CJSON_PUBLIC(cJSON *) cJSON_CreateDoubleArray(const double *numbers, int count) for (i = 0; a && (i < (size_t) count); i++) { - n = cJSON_CreateNumber(numbers[i]); - if(!n) - { + n = cJSON_CreateNumber (numbers[i]); + if (!n) + { cJSON_Delete(a); return NULL; } @@ -2988,7 +3013,7 @@ CJSON_PUBLIC(cJSON_bool) cJSON_IsRaw(const cJSON * const item) CJSON_PUBLIC(cJSON_bool) cJSON_Compare(const cJSON * const a, const cJSON * const b, const cJSON_bool case_sensitive) { - if ((a == NULL) || (b == NULL) || ((a->type & 0xFF) != (b->type & 0xFF)) || cJSON_IsInvalid(a)) + if ((a == NULL) || (b == NULL) || ((a->type & 0xFF) != (b->type & 0xFF))) { return false; } @@ -3121,7 +3146,7 @@ CJSON_PUBLIC(void) cJSON_free(void *object) global_hooks.deallocate(object); } -CJSON_PUBLIC(void *) cJSON_realloc(void *object, size_t new_size, size_t old_size) +CJSON_PUBLIC (void *) cJSON_realloc (void *object, size_t size) { - return global_hooks.reallocate(object, new_size, old_size); + return global_hooks.reallocate (object, size); } diff --git a/src/vppinfra/cJSON.h b/src/vppinfra/cJSON.h index 1474c4e5c49..1c98dfac70e 100644 --- a/src/vppinfra/cJSON.h +++ b/src/vppinfra/cJSON.h @@ -81,7 +81,7 @@ then using the CJSON_API_VISIBILITY flag to "export" the same symbols the way CJ /* project version */ #define CJSON_VERSION_MAJOR 1 #define CJSON_VERSION_MINOR 7 -#define CJSON_VERSION_PATCH 14 +#define CJSON_VERSION_PATCH 17 #include <stddef.h> @@ -127,8 +127,7 @@ typedef struct cJSON_Hooks /* malloc/free are CDECL on Windows regardless of the default calling convention of the compiler, so ensure the hooks allow passing those functions directly. */ void *(CJSON_CDECL *malloc_fn)(size_t sz); void (CJSON_CDECL *free_fn)(void *ptr); - void *(CJSON_CDECL *realloc_fn) (void *ptr, size_t new_size, - size_t old_size); + void *(CJSON_CDECL *realloc_fn) (void *ptr, size_t sz); } cJSON_Hooks; typedef int cJSON_bool; @@ -256,9 +255,10 @@ CJSON_PUBLIC(cJSON *) cJSON_Duplicate(const cJSON *item, cJSON_bool recurse); * case_sensitive determines if object keys are treated case sensitive (1) or case insensitive (0) */ CJSON_PUBLIC(cJSON_bool) cJSON_Compare(const cJSON * const a, const cJSON * const b, const cJSON_bool case_sensitive); -/* Minify a strings, remove blank characters(such as ' ', '\t', '\r', '\n') from strings. - * The input pointer json cannot point to a read-only address area, such as a string constant, - * but should point to a readable and writable adress area. */ +/* Minify a strings, remove blank characters(such as ' ', '\t', '\r', '\n') + * from strings. The input pointer json cannot point to a read-only address + * area, such as a string constant, + * but should point to a readable and writable address area. */ CJSON_PUBLIC(void) cJSON_Minify(char *json); /* Helper functions for creating and adding items to an object at the same time. @@ -281,14 +281,21 @@ CJSON_PUBLIC(double) cJSON_SetNumberHelper(cJSON *object, double number); /* Change the valuestring of a cJSON_String object, only takes effect when type of object is cJSON_String */ CJSON_PUBLIC(char*) cJSON_SetValuestring(cJSON *object, const char *valuestring); +/* If the object is not a boolean type this does nothing and returns + * cJSON_Invalid else it returns the new type*/ +#define cJSON_SetBoolValue(object, boolValue) \ + ((object != NULL && ((object)->type & (cJSON_False | cJSON_True))) ? \ + (object)->type = ((object)->type & (~(cJSON_False | cJSON_True))) | \ + ((boolValue) ? cJSON_True : cJSON_False) : \ + cJSON_Invalid) + /* Macro for iterating over an array or object */ #define cJSON_ArrayForEach(element, array) for(element = (array != NULL) ? (array)->child : NULL; element != NULL; element = element->next) /* malloc/free objects using the malloc/free functions that have been set with cJSON_InitHooks */ CJSON_PUBLIC(void *) cJSON_malloc(size_t size); CJSON_PUBLIC(void) cJSON_free(void *object); -CJSON_PUBLIC (void *) -cJSON_realloc (void *object, size_t new_size, size_t old_size); +CJSON_PUBLIC (void *) cJSON_realloc (void *object, size_t size); #ifdef __cplusplus } diff --git a/src/vppinfra/crypto/sha2.h b/src/vppinfra/crypto/sha2.h index 51006151365..69a24a2d087 100644 --- a/src/vppinfra/crypto/sha2.h +++ b/src/vppinfra/crypto/sha2.h @@ -1,16 +1,5 @@ -/* - * Copyright (c) 2019 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. +/* SPDX-License-Identifier: Apache-2.0 + * Copyright(c) 2024 Cisco Systems, Inc. */ #ifndef included_sha2_h @@ -18,12 +7,8 @@ #include <vppinfra/clib.h> #include <vppinfra/vector.h> +#include <vppinfra/string.h> -#define SHA224_DIGEST_SIZE 28 -#define SHA224_BLOCK_SIZE 64 - -#define SHA256_DIGEST_SIZE 32 -#define SHA256_BLOCK_SIZE 64 #define SHA256_ROTR(x, y) ((x >> y) | (x << (32 - y))) #define SHA256_CH(a, b, c) ((a & b) ^ (~a & c)) #define SHA256_MAJ(a, b, c) ((a & b) ^ (a & c) ^ (b & c)) @@ -60,17 +45,6 @@ s[0] = t1 + t2; \ } -#define SHA512_224_DIGEST_SIZE 28 -#define SHA512_224_BLOCK_SIZE 128 - -#define SHA512_256_DIGEST_SIZE 32 -#define SHA512_256_BLOCK_SIZE 128 - -#define SHA384_DIGEST_SIZE 48 -#define SHA384_BLOCK_SIZE 128 - -#define SHA512_DIGEST_SIZE 64 -#define SHA512_BLOCK_SIZE 128 #define SHA512_ROTR(x, y) ((x >> y) | (x << (64 - y))) #define SHA512_CH(a, b, c) ((a & b) ^ (~a & c)) #define SHA512_MAJ(a, b, c) ((a & b) ^ (a & c) ^ (b & c)) @@ -125,7 +99,7 @@ static const u32 sha256_h[8] = { 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19 }; -static const u32 sha256_k[64] = { +static const u32 clib_sha2_256_k[64] = { 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, @@ -159,7 +133,7 @@ static const u64 sha512_256_h[8] = { 0x22312194fc2bf72c, 0x9f555fa3c84c64c2, 0x96283ee2a88effe3, 0xbe5e1e2553863992, 0x2b0199fc2c85b8aa, 0x0eb72ddc81c52ca2 }; -static const u64 sha512_k[80] = { +static const u64 clib_sha2_512_k[80] = { 0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc, 0x3956c25bf348b538, 0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118, 0xd807aa98a3030242, @@ -199,80 +173,102 @@ typedef enum CLIB_SHA2_512_256, } clib_sha2_type_t; -#define SHA2_MAX_BLOCK_SIZE SHA512_BLOCK_SIZE -#define SHA2_MAX_DIGEST_SIZE SHA512_DIGEST_SIZE +#define CLIB_SHA2_256_BLOCK_SIZE 64 +#define CLIB_SHA2_512_BLOCK_SIZE 128 +#define SHA2_MAX_BLOCK_SIZE CLIB_SHA2_512_BLOCK_SIZE +#define SHA2_MAX_DIGEST_SIZE 64 -typedef struct +static const struct { - u64 total_bytes; - u16 n_pending; u8 block_size; u8 digest_size; - union - { - u32 h32[8]; - u64 h64[8]; + const u32 *h32; + const u64 *h64; +} clib_sha2_variants[] = { + [CLIB_SHA2_224] = { + .block_size = CLIB_SHA2_256_BLOCK_SIZE, + .digest_size = 28, + .h32 = sha224_h, + }, + [CLIB_SHA2_256] = { + .block_size = CLIB_SHA2_256_BLOCK_SIZE, + .digest_size = 32, + .h32 = sha256_h, + }, + [CLIB_SHA2_384] = { + .block_size = CLIB_SHA2_512_BLOCK_SIZE, + .digest_size = 48, + .h64 = sha384_h, + }, + [CLIB_SHA2_512] = { + .block_size = CLIB_SHA2_512_BLOCK_SIZE, + .digest_size = 64, + .h64 = sha512_h, + }, + [CLIB_SHA2_512_224] = { + .block_size = CLIB_SHA2_512_BLOCK_SIZE, + .digest_size = 28, + .h64 = sha512_224_h, + }, + [CLIB_SHA2_512_256] = { + .block_size = CLIB_SHA2_512_BLOCK_SIZE, + .digest_size = 32, + .h64 = sha512_256_h, + }, +}; + +typedef union +{ + u32 h32[8]; + u64 h64[8]; #ifdef CLIB_SHA256_ISA - u32x4 h32x4[2]; + u32x4 h32x4[2]; #endif - }; +} clib_sha2_h_t; + +typedef struct +{ + u64 total_bytes; + u16 n_pending; + clib_sha2_h_t h; union { u8 as_u8[SHA2_MAX_BLOCK_SIZE]; u64 as_u64[SHA2_MAX_BLOCK_SIZE / sizeof (u64)]; uword as_uword[SHA2_MAX_BLOCK_SIZE / sizeof (uword)]; } pending; +} clib_sha2_state_t; + +typedef struct +{ + clib_sha2_type_t type; + u8 block_size; + u8 digest_size; + clib_sha2_state_t state; } clib_sha2_ctx_t; static_always_inline void -clib_sha2_init (clib_sha2_ctx_t *ctx, clib_sha2_type_t type) +clib_sha2_state_init (clib_sha2_state_t *state, clib_sha2_type_t type) { - const u32 *h32 = 0; - const u64 *h64 = 0; + clib_sha2_state_t st = {}; - ctx->total_bytes = 0; - ctx->n_pending = 0; - - switch (type) - { - case CLIB_SHA2_224: - h32 = sha224_h; - ctx->block_size = SHA224_BLOCK_SIZE; - ctx->digest_size = SHA224_DIGEST_SIZE; - break; - case CLIB_SHA2_256: - h32 = sha256_h; - ctx->block_size = SHA256_BLOCK_SIZE; - ctx->digest_size = SHA256_DIGEST_SIZE; - break; - case CLIB_SHA2_384: - h64 = sha384_h; - ctx->block_size = SHA384_BLOCK_SIZE; - ctx->digest_size = SHA384_DIGEST_SIZE; - break; - case CLIB_SHA2_512: - h64 = sha512_h; - ctx->block_size = SHA512_BLOCK_SIZE; - ctx->digest_size = SHA512_DIGEST_SIZE; - break; - case CLIB_SHA2_512_224: - h64 = sha512_224_h; - ctx->block_size = SHA512_224_BLOCK_SIZE; - ctx->digest_size = SHA512_224_DIGEST_SIZE; - break; - case CLIB_SHA2_512_256: - h64 = sha512_256_h; - ctx->block_size = SHA512_256_BLOCK_SIZE; - ctx->digest_size = SHA512_256_DIGEST_SIZE; - break; - } - if (h32) + if (clib_sha2_variants[type].block_size == CLIB_SHA2_256_BLOCK_SIZE) for (int i = 0; i < 8; i++) - ctx->h32[i] = h32[i]; - - if (h64) + st.h.h32[i] = clib_sha2_variants[type].h32[i]; + else for (int i = 0; i < 8; i++) - ctx->h64[i] = h64[i]; + st.h.h64[i] = clib_sha2_variants[type].h64[i]; + + *state = st; +} + +static_always_inline void +clib_sha2_init (clib_sha2_ctx_t *ctx, clib_sha2_type_t type) +{ + clib_sha2_state_init (&ctx->state, type); + ctx->block_size = clib_sha2_variants[type].block_size; + ctx->digest_size = clib_sha2_variants[type].digest_size; + ctx->type = type; } #ifdef CLIB_SHA256_ISA @@ -295,7 +291,7 @@ static inline void clib_sha256_vec_4_rounds (u32x4 w, u8 n, u32x4 s[]) { #ifdef CLIB_SHA256_ISA_INTEL - u32x4 r = *(u32x4 *) (sha256_k + 4 * n) + w; + u32x4 r = *(u32x4 *) (clib_sha2_256_k + 4 * n) + w; s[0] = (u32x4) _mm_sha256rnds2_epu32 ((__m128i) s[0], (__m128i) s[1], (__m128i) r); r = (u32x4) u64x2_interleave_hi ((u64x2) r, (u64x2) r); @@ -303,7 +299,7 @@ clib_sha256_vec_4_rounds (u32x4 w, u8 n, u32x4 s[]) (__m128i) r); #elif defined(CLIB_SHA256_ISA_ARM) u32x4 r0, s0; - const u32x4u *k = (u32x4u *) sha256_k; + const u32x4u *k = (u32x4u *) clib_sha2_256_k; r0 = w + k[n]; s0 = s[0]; @@ -338,14 +334,14 @@ clib_sha256_vec_shuffle (u32x4 d[2]) #endif static inline void -clib_sha256_block (clib_sha2_ctx_t *ctx, const u8 *msg, uword n_blocks) +clib_sha256_block (clib_sha2_state_t *st, const u8 *msg, uword n_blocks) { #if defined(CLIB_SHA256_ISA) u32x4 h[2]; u32x4u *m = (u32x4u *) msg; - h[0] = ctx->h32x4[0]; - h[1] = ctx->h32x4[1]; + h[0] = st->h.h32x4[0]; + h[1] = st->h.h32x4[1]; clib_sha256_vec_shuffle (h); @@ -399,159 +395,176 @@ clib_sha256_block (clib_sha2_ctx_t *ctx, const u8 *msg, uword n_blocks) clib_sha256_vec_shuffle (h); - ctx->h32x4[0] = h[0]; - ctx->h32x4[1] = h[1]; + st->h.h32x4[0] = h[0]; + st->h.h32x4[1] = h[1]; #else u32 w[64], s[8], i; + clib_sha2_h_t h; + + h = st->h; - while (n_blocks) + for (; n_blocks; msg += CLIB_SHA2_256_BLOCK_SIZE, n_blocks--) { for (i = 0; i < 8; i++) - s[i] = ctx->h32[i]; + s[i] = h.h32[i]; for (i = 0; i < 16; i++) { - w[i] = clib_net_to_host_u32 (*((u32 *) msg + i)); - SHA256_TRANSFORM (s, w, i, sha256_k[i]); + w[i] = clib_net_to_host_u32 ((((u32u *) msg)[i])); + SHA256_TRANSFORM (s, w, i, clib_sha2_256_k[i]); } for (i = 16; i < 64; i++) { SHA256_MSG_SCHED (w, i); - SHA256_TRANSFORM (s, w, i, sha256_k[i]); + SHA256_TRANSFORM (s, w, i, clib_sha2_256_k[i]); } for (i = 0; i < 8; i++) - ctx->h32[i] += s[i]; - - /* next */ - msg += SHA256_BLOCK_SIZE; - n_blocks--; + h.h32[i] += s[i]; } + + st->h = h; #endif } static_always_inline void -clib_sha512_block (clib_sha2_ctx_t *ctx, const u8 *msg, uword n_blocks) +clib_sha512_block (clib_sha2_state_t *st, const u8 *msg, uword n_blocks) { u64 w[80], s[8], i; + clib_sha2_h_t h; + + h = st->h; - while (n_blocks) + for (; n_blocks; msg += CLIB_SHA2_512_BLOCK_SIZE, n_blocks--) { for (i = 0; i < 8; i++) - s[i] = ctx->h64[i]; + s[i] = h.h64[i]; for (i = 0; i < 16; i++) { - w[i] = clib_net_to_host_u64 (*((u64 *) msg + i)); - SHA512_TRANSFORM (s, w, i, sha512_k[i]); + w[i] = clib_net_to_host_u64 ((((u64u *) msg)[i])); + SHA512_TRANSFORM (s, w, i, clib_sha2_512_k[i]); } for (i = 16; i < 80; i++) { SHA512_MSG_SCHED (w, i); - SHA512_TRANSFORM (s, w, i, sha512_k[i]); + SHA512_TRANSFORM (s, w, i, clib_sha2_512_k[i]); } for (i = 0; i < 8; i++) - ctx->h64[i] += s[i]; - - /* next */ - msg += SHA512_BLOCK_SIZE; - n_blocks--; + h.h64[i] += s[i]; } + + st->h = h; } static_always_inline void -clib_sha2_update (clib_sha2_ctx_t *ctx, const u8 *msg, uword n_bytes) +clib_sha2_update_internal (clib_sha2_state_t *st, u8 block_size, const u8 *msg, + uword n_bytes) { uword n_blocks; - if (ctx->n_pending) + if (st->n_pending) { - uword n_left = ctx->block_size - ctx->n_pending; + uword n_left = block_size - st->n_pending; if (n_bytes < n_left) { - clib_memcpy_fast (ctx->pending.as_u8 + ctx->n_pending, msg, n_bytes); - ctx->n_pending += n_bytes; + clib_memcpy_fast (st->pending.as_u8 + st->n_pending, msg, n_bytes); + st->n_pending += n_bytes; return; } else { - clib_memcpy_fast (ctx->pending.as_u8 + ctx->n_pending, msg, n_left); - if (ctx->block_size == SHA512_BLOCK_SIZE) - clib_sha512_block (ctx, ctx->pending.as_u8, 1); + clib_memcpy_fast (st->pending.as_u8 + st->n_pending, msg, n_left); + if (block_size == CLIB_SHA2_512_BLOCK_SIZE) + clib_sha512_block (st, st->pending.as_u8, 1); else - clib_sha256_block (ctx, ctx->pending.as_u8, 1); - ctx->n_pending = 0; - ctx->total_bytes += ctx->block_size; + clib_sha256_block (st, st->pending.as_u8, 1); + st->n_pending = 0; + st->total_bytes += block_size; n_bytes -= n_left; msg += n_left; } } - if ((n_blocks = n_bytes / ctx->block_size)) + if ((n_blocks = n_bytes / block_size)) { - if (ctx->block_size == SHA512_BLOCK_SIZE) - clib_sha512_block (ctx, msg, n_blocks); + if (block_size == CLIB_SHA2_512_BLOCK_SIZE) + clib_sha512_block (st, msg, n_blocks); else - clib_sha256_block (ctx, msg, n_blocks); - n_bytes -= n_blocks * ctx->block_size; - msg += n_blocks * ctx->block_size; - ctx->total_bytes += n_blocks * ctx->block_size; + clib_sha256_block (st, msg, n_blocks); + n_bytes -= n_blocks * block_size; + msg += n_blocks * block_size; + st->total_bytes += n_blocks * block_size; } if (n_bytes) { - clib_memset_u8 (ctx->pending.as_u8, 0, ctx->block_size); - clib_memcpy_fast (ctx->pending.as_u8, msg, n_bytes); - ctx->n_pending = n_bytes; + clib_memset_u8 (st->pending.as_u8, 0, block_size); + clib_memcpy_fast (st->pending.as_u8, msg, n_bytes); + st->n_pending = n_bytes; } else - ctx->n_pending = 0; + st->n_pending = 0; } static_always_inline void -clib_sha2_final (clib_sha2_ctx_t *ctx, u8 *digest) +clib_sha2_update (clib_sha2_ctx_t *ctx, const u8 *msg, uword n_bytes) +{ + clib_sha2_update_internal (&ctx->state, ctx->block_size, msg, n_bytes); +} + +static_always_inline void +clib_sha2_final_internal (clib_sha2_state_t *st, u8 block_size, u8 digest_size, + u8 *digest) { int i; - ctx->total_bytes += ctx->n_pending; - if (ctx->n_pending == 0) + st->total_bytes += st->n_pending; + if (st->n_pending == 0) { - clib_memset (ctx->pending.as_u8, 0, ctx->block_size); - ctx->pending.as_u8[0] = 0x80; + clib_memset (st->pending.as_u8, 0, block_size); + st->pending.as_u8[0] = 0x80; } - else if (ctx->n_pending + sizeof (u64) + sizeof (u8) > ctx->block_size) + else if (st->n_pending + sizeof (u64) + sizeof (u8) > block_size) { - ctx->pending.as_u8[ctx->n_pending] = 0x80; - if (ctx->block_size == SHA512_BLOCK_SIZE) - clib_sha512_block (ctx, ctx->pending.as_u8, 1); + st->pending.as_u8[st->n_pending] = 0x80; + if (block_size == CLIB_SHA2_512_BLOCK_SIZE) + clib_sha512_block (st, st->pending.as_u8, 1); else - clib_sha256_block (ctx, ctx->pending.as_u8, 1); - clib_memset (ctx->pending.as_u8, 0, ctx->block_size); + clib_sha256_block (st, st->pending.as_u8, 1); + clib_memset (st->pending.as_u8, 0, block_size); } else - ctx->pending.as_u8[ctx->n_pending] = 0x80; + st->pending.as_u8[st->n_pending] = 0x80; - ctx->pending.as_u64[ctx->block_size / 8 - 1] = - clib_net_to_host_u64 (ctx->total_bytes * 8); - if (ctx->block_size == SHA512_BLOCK_SIZE) - clib_sha512_block (ctx, ctx->pending.as_u8, 1); - else - clib_sha256_block (ctx, ctx->pending.as_u8, 1); + st->pending.as_u64[block_size / 8 - 1] = + clib_net_to_host_u64 (st->total_bytes * 8); - if (ctx->block_size == SHA512_BLOCK_SIZE) + if (block_size == CLIB_SHA2_512_BLOCK_SIZE) { - for (i = 0; i < ctx->digest_size / sizeof (u64); i++) - *((u64 *) digest + i) = clib_net_to_host_u64 (ctx->h64[i]); + clib_sha512_block (st, st->pending.as_u8, 1); + for (i = 0; i < digest_size / sizeof (u64); i++) + ((u64 *) digest)[i] = clib_net_to_host_u64 (st->h.h64[i]); /* sha512-224 case - write half of u64 */ - if (i * sizeof (u64) < ctx->digest_size) - *((u32 *) digest + 2 * i) = clib_net_to_host_u32 (ctx->h64[i] >> 32); + if (i * sizeof (u64) < digest_size) + ((u32 *) digest)[2 * i] = clib_net_to_host_u32 (st->h.h64[i] >> 32); } else - for (i = 0; i < ctx->digest_size / sizeof (u32); i++) - *((u32 *) digest + i) = clib_net_to_host_u32 (ctx->h32[i]); + { + clib_sha256_block (st, st->pending.as_u8, 1); + for (i = 0; i < digest_size / sizeof (u32); i++) + *((u32 *) digest + i) = clib_net_to_host_u32 (st->h.h32[i]); + } +} + +static_always_inline void +clib_sha2_final (clib_sha2_ctx_t *ctx, u8 *digest) +{ + clib_sha2_final_internal (&ctx->state, ctx->block_size, ctx->digest_size, + digest); } static_always_inline void @@ -570,70 +583,133 @@ clib_sha2 (clib_sha2_type_t type, const u8 *msg, uword len, u8 *digest) #define clib_sha512_224(...) clib_sha2 (CLIB_SHA2_512_224, __VA_ARGS__) #define clib_sha512_256(...) clib_sha2 (CLIB_SHA2_512_256, __VA_ARGS__) -static_always_inline void -clib_hmac_sha2 (clib_sha2_type_t type, const u8 *key, uword key_len, - const u8 *msg, uword len, u8 *digest) +/* + * HMAC + */ + +typedef struct { - clib_sha2_ctx_t _ctx, *ctx = &_ctx; - uword key_data[SHA2_MAX_BLOCK_SIZE / sizeof (uword)]; - u8 i_digest[SHA2_MAX_DIGEST_SIZE]; - int i, n_words; + clib_sha2_h_t ipad_h; + clib_sha2_h_t opad_h; +} clib_sha2_hmac_key_data_t; + +typedef struct +{ + clib_sha2_type_t type; + u8 block_size; + u8 digest_size; + clib_sha2_state_t ipad_state; + clib_sha2_state_t opad_state; +} clib_sha2_hmac_ctx_t; - clib_sha2_init (ctx, type); - n_words = ctx->block_size / sizeof (uword); +static_always_inline void +clib_sha2_hmac_key_data (clib_sha2_type_t type, const u8 *key, uword key_len, + clib_sha2_hmac_key_data_t *kd) +{ + u8 block_size = clib_sha2_variants[type].block_size; + u8 data[SHA2_MAX_BLOCK_SIZE] = {}; + u8 ikey[SHA2_MAX_BLOCK_SIZE]; + u8 okey[SHA2_MAX_BLOCK_SIZE]; + clib_sha2_state_t ipad_state; + clib_sha2_state_t opad_state; /* key */ - if (key_len > ctx->block_size) + if (key_len > block_size) { /* key is longer than block, calculate hash of key */ - clib_sha2_update (ctx, key, key_len); - for (i = (ctx->digest_size / sizeof (uword)) / 2; i < n_words; i++) - key_data[i] = 0; - clib_sha2_final (ctx, (u8 *) key_data); - clib_sha2_init (ctx, type); + clib_sha2_ctx_t ctx; + clib_sha2_init (&ctx, type); + clib_sha2_update (&ctx, key, key_len); + clib_sha2_final (&ctx, (u8 *) data); } else + clib_memcpy_fast (data, key, key_len); + + for (int i = 0, w = 0; w < block_size; w += sizeof (uword), i++) { - for (i = 0; i < n_words; i++) - key_data[i] = 0; - clib_memcpy_fast (key_data, key, key_len); + ((uwordu *) ikey)[i] = ((uwordu *) data)[i] ^ 0x3636363636363636UL; + ((uwordu *) okey)[i] = ((uwordu *) data)[i] ^ 0x5c5c5c5c5c5c5c5cUL; } - /* ipad */ - for (i = 0; i < n_words; i++) - ctx->pending.as_uword[i] = key_data[i] ^ (uword) 0x3636363636363636; - if (ctx->block_size == SHA512_BLOCK_SIZE) - clib_sha512_block (ctx, ctx->pending.as_u8, 1); - else - clib_sha256_block (ctx, ctx->pending.as_u8, 1); - ctx->total_bytes += ctx->block_size; - - /* message */ - clib_sha2_update (ctx, msg, len); - clib_sha2_final (ctx, i_digest); - - /* opad */ - clib_sha2_init (ctx, type); - for (i = 0; i < n_words; i++) - ctx->pending.as_uword[i] = key_data[i] ^ (uword) 0x5c5c5c5c5c5c5c5c; - if (ctx->block_size == SHA512_BLOCK_SIZE) - clib_sha512_block (ctx, ctx->pending.as_u8, 1); + clib_sha2_state_init (&ipad_state, type); + clib_sha2_state_init (&opad_state, type); + + if (block_size == CLIB_SHA2_512_BLOCK_SIZE) + { + clib_sha512_block (&ipad_state, ikey, 1); + clib_sha512_block (&opad_state, okey, 1); + } else - clib_sha256_block (ctx, ctx->pending.as_u8, 1); - ctx->total_bytes += ctx->block_size; + { + clib_sha256_block (&ipad_state, ikey, 1); + clib_sha256_block (&opad_state, okey, 1); + } + + kd->ipad_h = ipad_state.h; + kd->opad_h = opad_state.h; +} + +static_always_inline void +clib_sha2_hmac_init (clib_sha2_hmac_ctx_t *ctx, clib_sha2_type_t type, + clib_sha2_hmac_key_data_t *kd) +{ + u8 block_size = clib_sha2_variants[type].block_size; + u8 digest_size = clib_sha2_variants[type].digest_size; + + *ctx = (clib_sha2_hmac_ctx_t) { + .type = type, + .block_size = block_size, + .digest_size = digest_size, + .ipad_state = { + .h = kd->ipad_h, + .total_bytes = block_size, + }, + .opad_state = { + .h = kd->opad_h, + .total_bytes = block_size, + }, + }; +} + +static_always_inline void +clib_sha2_hmac_update (clib_sha2_hmac_ctx_t *ctx, const u8 *msg, uword len) +{ + clib_sha2_update_internal (&ctx->ipad_state, ctx->block_size, msg, len); +} + +static_always_inline void +clib_sha2_hmac_final (clib_sha2_hmac_ctx_t *ctx, u8 *digest) +{ + u8 i_digest[SHA2_MAX_DIGEST_SIZE]; + + clib_sha2_final_internal (&ctx->ipad_state, ctx->block_size, + ctx->digest_size, i_digest); + clib_sha2_update_internal (&ctx->opad_state, ctx->block_size, i_digest, + ctx->digest_size); + clib_sha2_final_internal (&ctx->opad_state, ctx->block_size, + ctx->digest_size, digest); +} + +static_always_inline void +clib_sha2_hmac (clib_sha2_type_t type, const u8 *key, uword key_len, + const u8 *msg, uword len, u8 *digest) +{ + clib_sha2_hmac_ctx_t _ctx, *ctx = &_ctx; + clib_sha2_hmac_key_data_t kd; - /* digest */ - clib_sha2_update (ctx, i_digest, ctx->digest_size); - clib_sha2_final (ctx, digest); + clib_sha2_hmac_key_data (type, key, key_len, &kd); + clib_sha2_hmac_init (ctx, type, &kd); + clib_sha2_hmac_update (ctx, msg, len); + clib_sha2_hmac_final (ctx, digest); } -#define clib_hmac_sha224(...) clib_hmac_sha2 (CLIB_SHA2_224, __VA_ARGS__) -#define clib_hmac_sha256(...) clib_hmac_sha2 (CLIB_SHA2_256, __VA_ARGS__) -#define clib_hmac_sha384(...) clib_hmac_sha2 (CLIB_SHA2_384, __VA_ARGS__) -#define clib_hmac_sha512(...) clib_hmac_sha2 (CLIB_SHA2_512, __VA_ARGS__) +#define clib_hmac_sha224(...) clib_sha2_hmac (CLIB_SHA2_224, __VA_ARGS__) +#define clib_hmac_sha256(...) clib_sha2_hmac (CLIB_SHA2_256, __VA_ARGS__) +#define clib_hmac_sha384(...) clib_sha2_hmac (CLIB_SHA2_384, __VA_ARGS__) +#define clib_hmac_sha512(...) clib_sha2_hmac (CLIB_SHA2_512, __VA_ARGS__) #define clib_hmac_sha512_224(...) \ - clib_hmac_sha2 (CLIB_SHA2_512_224, __VA_ARGS__) + clib_sha2_hmac (CLIB_SHA2_512_224, __VA_ARGS__) #define clib_hmac_sha512_256(...) \ - clib_hmac_sha2 (CLIB_SHA2_512_256, __VA_ARGS__) + clib_sha2_hmac (CLIB_SHA2_512_256, __VA_ARGS__) #endif /* included_sha2_h */ diff --git a/src/vppinfra/format.h b/src/vppinfra/format.h index 24511735a53..a1a70a2d64f 100644 --- a/src/vppinfra/format.h +++ b/src/vppinfra/format.h @@ -276,6 +276,12 @@ unformat_init_cstring (unformat_input_t * input, char *string) /* Setup for unformat of given vector string; vector will be freed by unformat_string. */ void unformat_init_vector (unformat_input_t * input, u8 * vector_string); +/* Unformat u8 */ +unformat_function_t unformat_u8; + +/* Unformat u16 */ +unformat_function_t unformat_u16; + /* Format function for unformat input usable when an unformat error has occurred. */ u8 *format_unformat_error (u8 * s, va_list * va); diff --git a/src/vppinfra/heap.c b/src/vppinfra/heap.c index 7db814200f8..9920528732d 100644 --- a/src/vppinfra/heap.c +++ b/src/vppinfra/heap.c @@ -680,6 +680,7 @@ debug_elt (u8 * s, void *v, word i, word n) i = -n / 2; for (e = e0; 1; e = heap_next (e)) { + s = format (s, " "); if (heap_is_free (e)) s = format (s, "index %4d, free\n", e - h->elts); else if (h->format_elt) diff --git a/src/vppinfra/mhash.c b/src/vppinfra/mhash.c index f0f1aa470d7..babaaeec726 100644 --- a/src/vppinfra/mhash.c +++ b/src/vppinfra/mhash.c @@ -164,6 +164,8 @@ mhash_sanitize_hash_user (mhash_t * mh) h->user = pointer_to_uword (mh); } +static u8 *mhash_format_pair_default (u8 *s, va_list *args); + __clib_export void mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes) { @@ -208,12 +210,12 @@ mhash_init (mhash_t * h, uword n_value_bytes, uword n_key_bytes) vec_validate (h->key_tmps, os_get_nthreads () - 1); ASSERT (n_key_bytes < ARRAY_LEN (t)); - h->hash = hash_create2 ( /* elts */ 0, + h->hash = hash_create2 (/* elts */ 0, /* user */ pointer_to_uword (h), /* value_bytes */ n_value_bytes, t[n_key_bytes].key_sum, t[n_key_bytes].key_equal, /* format pair/arg */ - 0, 0); + mhash_format_pair_default, 0); } static uword @@ -331,8 +333,8 @@ mhash_set_mem (mhash_t * h, void *key, uword * new_value, uword * old_value) { if (key_alloc_from_free_list) { - h->key_vector_free_indices[l] = i; - vec_set_len (h->key_vector_free_indices, l + 1); + vec_set_len (h->key_vector_free_indices, l); + h->key_vector_free_indices[l - 1] = i; } else vec_dec_len (h->key_vector_or_heap, h->n_key_bytes); @@ -371,8 +373,8 @@ mhash_unset (mhash_t * h, void *key, uword * old_value) return 1; } -u8 * -format_mhash_key (u8 * s, va_list * va) +__clib_export u8 * +format_mhash_key (u8 *s, va_list *va) { mhash_t *h = va_arg (*va, mhash_t *); u32 ki = va_arg (*va, u32); @@ -387,7 +389,43 @@ format_mhash_key (u8 * s, va_list * va) else if (h->format_key) s = format (s, "%U", h->format_key, k); else - s = format (s, "%U", format_hex_bytes, k, h->n_key_bytes); + s = format (s, "0x%U", format_hex_bytes, k, h->n_key_bytes); + + return s; +} + +static u8 * +mhash_format_pair_default (u8 *s, va_list *args) +{ + void *CLIB_UNUSED (user_arg) = va_arg (*args, void *); + void *v = va_arg (*args, void *); + hash_pair_t *p = va_arg (*args, hash_pair_t *); + hash_t *h = hash_header (v); + mhash_t *mh = uword_to_pointer (h->user, mhash_t *); + + s = format (s, "%U", format_mhash_key, mh, (u32) p->key); + if (hash_value_bytes (h) > 0) + s = format (s, " -> 0x%8U", format_hex_bytes, &p->value[0], + hash_value_bytes (h)); + return s; +} + +__clib_export u8 * +format_mhash (u8 *s, va_list *va) +{ + mhash_t *h = va_arg (*va, mhash_t *); + int verbose = va_arg (*va, int); + + s = format (s, "mhash %p, %wd elts, \n", h, mhash_elts (h)); + if (mhash_key_vector_is_heap (h)) + s = format (s, " %U", format_heap, h->key_vector_or_heap, verbose); + else + s = format (s, " keys %wd elts, %wd size, %wd free, %wd bytes used\n", + vec_len (h->key_vector_or_heap) / h->n_key_bytes, + h->n_key_bytes, vec_len (h->key_vector_free_indices), + vec_bytes (h->key_vector_or_heap) + + vec_bytes (h->key_vector_free_indices)); + s = format (s, " %U", format_hash, h->hash, verbose); return s; } diff --git a/src/vppinfra/mhash.h b/src/vppinfra/mhash.h index 7eb1918384e..62aee365fa3 100644 --- a/src/vppinfra/mhash.h +++ b/src/vppinfra/mhash.h @@ -166,8 +166,13 @@ do { \ })); \ } while (0) +u8 *format_mhash (u8 *s, va_list *va); + format_function_t format_mhash_key; +/* Main test routine. */ +int test_mhash_main (unformat_input_t *input); + #endif /* included_clib_mhash_h */ /* diff --git a/src/vppinfra/pmalloc.c b/src/vppinfra/pmalloc.c index 2a27379b573..85b9db9d56c 100644 --- a/src/vppinfra/pmalloc.c +++ b/src/vppinfra/pmalloc.c @@ -17,6 +17,9 @@ #include <stdlib.h> #include <sys/types.h> #include <sys/stat.h> +#ifdef __FreeBSD__ +#include <sys/memrange.h> +#endif /* __FreeBSD__ */ #include <fcntl.h> #include <unistd.h> #include <sched.h> @@ -184,8 +187,9 @@ next_chunk: } static void -pmalloc_update_lookup_table (clib_pmalloc_main_t * pm, u32 first, u32 count) +pmalloc_update_lookup_table (clib_pmalloc_main_t *pm, u32 first, u32 count) { +#ifdef __linux uword seek, va, pa, p; int fd; u32 elts_per_page = 1U << (pm->def_log2_page_sz - pm->lookup_log2_page_sz); @@ -223,6 +227,45 @@ pmalloc_update_lookup_table (clib_pmalloc_main_t * pm, u32 first, u32 count) if (fd != -1) close (fd); +#elif defined(__FreeBSD__) + struct mem_extract meme; + uword p; + int fd; + u32 elts_per_page = 1U << (pm->def_log2_page_sz - pm->lookup_log2_page_sz); + + vec_validate_aligned (pm->lookup_table, + vec_len (pm->pages) * elts_per_page - 1, + CLIB_CACHE_LINE_BYTES); + + p = (uword) first * elts_per_page; + if (pm->flags & CLIB_PMALLOC_F_NO_PAGEMAP) + { + while (p < (uword) elts_per_page * count) + { + pm->lookup_table[p] = + pointer_to_uword (pm->base) + (p << pm->lookup_log2_page_sz); + p++; + } + return; + } + + fd = open ((char *) "/dev/mem", O_RDONLY); + if (fd == -1) + return; + + while (p < (uword) elts_per_page * count) + { + meme.me_vaddr = + pointer_to_uword (pm->base) + (p << pm->lookup_log2_page_sz); + if (ioctl (fd, MEM_EXTRACT_PADDR, &meme) == -1) + continue; + pm->lookup_table[p] = meme.me_vaddr - meme.me_paddr; + p++; + } + return; +#else +#error "Unsupported OS" +#endif } static inline clib_pmalloc_page_t * diff --git a/src/vppinfra/test/compress.c b/src/vppinfra/test/compress.c index 7b97f4c31af..083065f9bda 100644 --- a/src/vppinfra/test/compress.c +++ b/src/vppinfra/test/compress.c @@ -51,18 +51,21 @@ static compress_test_t tests[] = { static clib_error_t * test_clib_compress_u64 (clib_error_t *err) { - u64 src[513]; - u64 dst[513]; u32 i, j; - for (i = 0; i < ARRAY_LEN (src); i++) - src[i] = i; - for (i = 0; i < ARRAY_LEN (tests); i++) { compress_test_t *t = tests + i; + u64 src[t->n_elts]; +#ifdef CLIB_SANITIZE_ADDR + u64 dst[t->n_elts]; +#else /* CLIB_SANITIZE_ADDR */ + u64 dst[513]; +#endif /* CLIB_SANITIZE_ADDR */ u64 *dp = dst; u32 r; + for (j = 0; j < t->n_elts; j++) + src[j] = j; for (j = 0; j < ARRAY_LEN (dst); j++) dst[j] = 0xa5a5a5a5a5a5a5a5; @@ -81,8 +84,10 @@ test_clib_compress_u64 (clib_error_t *err) dp++; } +#ifndef CLIB_SANITIZE_ADDR if (dst[dp - dst + 1] != 0xa5a5a5a5a5a5a5a5) return clib_error_return (err, "buffer overrun in testcase %u", i); +#endif /* CLIB_SANITIZE_ADDR */ if (dp - dst != r) return clib_error_return (err, "wrong number of elts in testcase %u", @@ -95,18 +100,21 @@ test_clib_compress_u64 (clib_error_t *err) static clib_error_t * test_clib_compress_u32 (clib_error_t *err) { - u32 src[513]; - u32 dst[513]; u32 i, j; - for (i = 0; i < ARRAY_LEN (src); i++) - src[i] = i; - for (i = 0; i < ARRAY_LEN (tests); i++) { compress_test_t *t = tests + i; + u32 src[t->n_elts]; +#ifdef CLIB_SANITIZE_ADDR + u32 dst[t->n_elts]; +#else /* CLIB_SANITIZE_ADDR */ + u32 dst[513]; +#endif /* CLIB_SANITIZE_ADDR */ u32 *dp = dst; u32 r; + for (j = 0; j < t->n_elts; j++) + src[j] = j; for (j = 0; j < ARRAY_LEN (dst); j++) dst[j] = 0xa5a5a5a5; @@ -126,8 +134,10 @@ test_clib_compress_u32 (clib_error_t *err) dp++; } +#ifndef CLIB_SANITIZE_ADDR if (dst[dp - dst + 1] != 0xa5a5a5a5) return clib_error_return (err, "buffer overrun in testcase %u", i); +#endif /* CLIB_SANITIZE_ADDR */ if (dp - dst != r) return clib_error_return (err, "wrong number of elts in testcase %u", @@ -140,18 +150,21 @@ test_clib_compress_u32 (clib_error_t *err) static clib_error_t * test_clib_compress_u16 (clib_error_t *err) { - u16 src[513]; - u16 dst[513]; u32 i, j; - for (i = 0; i < ARRAY_LEN (src); i++) - src[i] = i; - for (i = 0; i < ARRAY_LEN (tests); i++) { compress_test_t *t = tests + i; + u16 src[t->n_elts]; +#ifdef CLIB_SANITIZE_ADDR + u16 dst[t->n_elts]; +#else /* CLIB_SANITIZE_ADDR */ + u16 dst[513]; +#endif /* CLIB_SANITIZE_ADDR */ u16 *dp = dst; u32 r; + for (j = 0; j < t->n_elts; j++) + src[j] = j; for (j = 0; j < ARRAY_LEN (dst); j++) dst[j] = 0xa5a5; @@ -170,8 +183,10 @@ test_clib_compress_u16 (clib_error_t *err) dp++; } +#ifndef CLIB_SANITIZE_ADDR if (dst[dp - dst + 1] != 0xa5a5) return clib_error_return (err, "buffer overrun in testcase %u", i); +#endif /* CLIB_SANITIZE_ADDR */ if (dp - dst != r) return clib_error_return (err, "wrong number of elts in testcase %u", @@ -184,18 +199,21 @@ test_clib_compress_u16 (clib_error_t *err) static clib_error_t * test_clib_compress_u8 (clib_error_t *err) { - u8 src[513]; - u8 dst[513]; u32 i, j; - for (i = 0; i < ARRAY_LEN (src); i++) - src[i] = i; - for (i = 0; i < ARRAY_LEN (tests); i++) { compress_test_t *t = tests + i; + u8 src[t->n_elts]; +#ifdef CLIB_SANITIZE_ADDR + u8 dst[t->n_elts]; +#else /* CLIB_SANITIZE_ADDR */ + u8 dst[513]; +#endif /* CLIB_SANITIZE_ADDR */ u8 *dp = dst; u32 r; + for (j = 0; j < t->n_elts; j++) + src[j] = j; for (j = 0; j < ARRAY_LEN (dst); j++) dst[j] = 0xa5; @@ -214,8 +232,10 @@ test_clib_compress_u8 (clib_error_t *err) dp++; } +#ifndef CLIB_SANITIZE_ADDR if (dst[dp - dst + 1] != 0xa5) return clib_error_return (err, "buffer overrun in testcase %u", i); +#endif /* CLIB_SANITIZE_ADDR */ if (dp - dst != r) return clib_error_return (err, "wrong number of elts in testcase %u", diff --git a/src/vppinfra/test_mhash.c b/src/vppinfra/test_mhash.c new file mode 100644 index 00000000000..70be2b9b382 --- /dev/null +++ b/src/vppinfra/test_mhash.c @@ -0,0 +1,403 @@ +/* SPDX-License-Identifier: Apache-2.0 + * Copyright(c) 2023 Yandex LLC. + */ + +#ifdef CLIB_LINUX_KERNEL +#include <linux/unistd.h> +#endif + +#ifdef CLIB_UNIX +#include <unistd.h> +#include <stdlib.h> +#include <stdio.h> +#include <vppinfra/time.h> +#endif + +#include <vppinfra/random.h> +#include <vppinfra/mem.h> +#include <vppinfra/hash.h> +#include <vppinfra/mhash.h> +#include <vppinfra/error.h> +#include <vppinfra/format.h> +#include <vppinfra/bitmap.h> + +static int verbose; +#define if_verbose(format, args...) \ + if (verbose) \ + { \ + clib_warning (format, ##args); \ + } + +typedef struct +{ + int n_iterations; + + int n_iterations_per_print; + + /* Number of pairs to insert into mhash. */ + int n_pairs; + + /* True to validate correctness of mhash functions. */ + int n_iterations_per_validate; + + /* Verbosity level for mhash formats. */ + int verbose; + + /* Random number seed. */ + u32 seed; +} mhash_test_t; + +static clib_error_t * +mhash_next_test (mhash_t *h) +{ + hash_next_t hn = { 0 }; + hash_pair_t *p0, *p1; + clib_error_t *error = 0; + + hash_foreach_pair (p0, h->hash, { + p1 = hash_next (h->hash, &hn); + error = CLIB_ERROR_ASSERT (p0 == p1); + if (error) + break; + }); + + if (!error) + error = CLIB_ERROR_ASSERT (!hash_next (h->hash, &hn)); + + return error; +} + +static clib_error_t * +test_word_key (mhash_test_t *ht) +{ + mhash_t _h = { 0 }, *h = &_h; + word i, j; + + word *keys = 0, *vals = 0; + uword *is_inserted = 0; + + clib_error_t *error = 0; + + vec_resize (keys, ht->n_pairs); + vec_resize (vals, vec_len (keys)); + + mhash_init (h, sizeof (vals[0]), sizeof (keys[0])); + /* borrow 0 elt to make index keys non-zero */ + vec_validate (h->key_vector_or_heap, 0); + + { + uword *unique = 0; + u32 k; + + for (i = 0; i < vec_len (keys); i++) + { + do + { + k = random_u32 (&ht->seed) & 0xfffff; + } + while (clib_bitmap_get (unique, k)); + unique = clib_bitmap_ori (unique, k); + keys[i] = k; + vals[i] = i; + } + + clib_bitmap_free (unique); + } + + for (i = 0; i < ht->n_iterations; i++) + { + u32 vi = random_u32 (&ht->seed) % vec_len (keys); + + if (clib_bitmap_get (is_inserted, vi)) + { + mhash_unset (h, &keys[vi], 0); + mhash_unset (h, &keys[vi], 0); + } + else + { + mhash_set (h, &keys[vi], vals[vi], 0); + mhash_set (h, &keys[vi], vals[vi], 0); + } + + is_inserted = clib_bitmap_xori (is_inserted, vi); + + if (ht->n_iterations_per_print > 0 && + ((i + 1) % ht->n_iterations_per_print) == 0) + if_verbose ("iteration %d\n %U", i + 1, format_mhash, h, ht->verbose); + + if (ht->n_iterations_per_validate == 0 || + (i + 1) % ht->n_iterations_per_validate) + continue; + + { + uword ki, *k, *v; + + mhash_foreach (k, v, h, { + ki = v[0]; + ASSERT (keys[ki] == k[0]); + }); + } + + if ((error = hash_validate (h->hash))) + goto done; + + for (j = 0; j < vec_len (keys); j++) + { + uword *v; + v = mhash_get (h, &keys[j]); + if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == + (v != 0)))) + goto done; + if (v) + { + if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j]))) + goto done; + } + } + } + + if ((error = mhash_next_test (h))) + goto done; + + if_verbose ("%U", format_mhash, h, ht->verbose); + + for (i = 0; i < vec_len (keys); i++) + { + if (!clib_bitmap_get (is_inserted, i)) + continue; + + mhash_unset (h, &keys[i], 0); + mhash_unset (h, &keys[i], 0); + is_inserted = clib_bitmap_xori (is_inserted, i); + + if (ht->n_iterations_per_validate == 0 || + (i + 1) % ht->n_iterations_per_validate) + continue; + + if ((error = hash_validate (h->hash))) + goto done; + + for (j = 0; j < vec_len (keys); j++) + { + uword *v; + v = mhash_get (h, &keys[j]); + if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == + (v != 0)))) + goto done; + if (v) + { + if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j]))) + goto done; + } + } + } + +done: + mhash_free (h); + vec_free (keys); + vec_free (vals); + clib_bitmap_free (is_inserted); + + if (verbose) + fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0); + + return error; +} + +static u8 * +test2_format (u8 *s, va_list *args) +{ + void *CLIB_UNUSED (user_arg) = va_arg (*args, void *); + void *v = va_arg (*args, void *); + hash_pair_t *p = va_arg (*args, hash_pair_t *); + hash_t *h = hash_header (v); + mhash_t *mh = uword_to_pointer (h->user, mhash_t *); + + return format (s, "0x%8U <- %U", format_hex_bytes, &p->value[0], + hash_value_bytes (h), format_mhash_key, mh, (u32) p->key); +} + +static clib_error_t * +test_string_key (mhash_test_t *ht, uword is_c_string) +{ + mhash_t _h = { 0 }, *h = &_h; + word i, j; + + u8 **keys = 0; + word *vals = 0; + uword *is_inserted = 0; + + clib_error_t *error = 0; + + vec_resize (keys, ht->n_pairs); + vec_resize (vals, vec_len (keys)); + + if (is_c_string) + mhash_init_c_string (h, sizeof (vals[0])); + else + mhash_init_vec_string (h, sizeof (vals[0])); + hash_set_pair_format (h->hash, test2_format, 0); + + for (i = 0; i < vec_len (keys); i++) + { + keys[i] = random_string (&ht->seed, 5 + (random_u32 (&ht->seed) & 0xf)); + keys[i] = format (keys[i], "%x", i); + if (is_c_string) + vec_terminate_c_string (keys[i]); + vals[i] = random_u32 (&ht->seed); + } + + for (i = 0; i < ht->n_iterations; i++) + { + u32 vi = random_u32 (&ht->seed) % vec_len (keys); + + if (clib_bitmap_get (is_inserted, vi)) + { + mhash_unset (h, keys[vi], 0); + mhash_unset (h, keys[vi], 0); + } + else + { + mhash_set (h, keys[vi], vals[vi], 0); + mhash_set (h, keys[vi], vals[vi], 0); + } + + is_inserted = clib_bitmap_xori (is_inserted, vi); + + if (ht->n_iterations_per_print > 0 && + ((i + 1) % ht->n_iterations_per_print) == 0) + if_verbose ("iteration %d\n %U", i + 1, format_mhash, h, ht->verbose); + + if (ht->n_iterations_per_validate == 0 || + (i + 1) % ht->n_iterations_per_validate) + continue; + + if ((error = hash_validate (h->hash))) + goto done; + + for (j = 0; j < vec_len (keys); j++) + { + uword *v; + v = mhash_get (h, keys[j]); + if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == + (v != 0)))) + goto done; + if (v) + { + if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j]))) + goto done; + } + } + } + + if ((error = mhash_next_test (h))) + goto done; + + if_verbose ("%U", format_mhash, h, ht->verbose); + + for (i = 0; i < vec_len (keys); i++) + { + if (!clib_bitmap_get (is_inserted, i)) + continue; + + mhash_unset (h, keys[i], 0); + mhash_unset (h, keys[i], 0); + is_inserted = clib_bitmap_xori (is_inserted, i); + + if (ht->n_iterations_per_validate == 0 || + (i + 1) % ht->n_iterations_per_validate) + continue; + + if ((error = hash_validate (h->hash))) + goto done; + + for (j = 0; j < vec_len (keys); j++) + { + uword *v; + v = mhash_get (h, keys[j]); + if ((error = CLIB_ERROR_ASSERT (clib_bitmap_get (is_inserted, j) == + (v != 0)))) + goto done; + if (v) + { + if ((error = CLIB_ERROR_ASSERT (v[0] == vals[j]))) + goto done; + } + } + } + +done: + mhash_free (h); + vec_free (vals); + clib_bitmap_free (is_inserted); + + for (i = 0; i < vec_len (keys); i++) + vec_free (keys[i]); + vec_free (keys); + + if (verbose) + fformat (stderr, "%U\n", format_clib_mem_usage, /* verbose */ 0); + + return error; +} + +int +test_mhash_main (unformat_input_t *input) +{ + mhash_test_t _ht = { 0 }, *ht = &_ht; + clib_error_t *error; + + ht->n_iterations = 100; + ht->n_pairs = 10; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) + { + if (0 == unformat (input, "iter %d", &ht->n_iterations) && + 0 == unformat (input, "print %d", &ht->n_iterations_per_print) && + 0 == unformat (input, "elts %d", &ht->n_pairs) && + 0 == unformat (input, "seed %d", &ht->seed) && + 0 == unformat (input, "verbose %=", &ht->verbose, 1) && + 0 == unformat (input, "valid %d", &ht->n_iterations_per_validate)) + { + clib_warning ("unknown input `%U'", format_unformat_error, input); + return 1; + } + } + + if (!ht->seed) + ht->seed = random_default_seed (); + + if_verbose ("testing %d iterations, seed %d", ht->n_iterations, ht->seed); + + error = test_word_key (ht); + if (error) + clib_error_report (error); + + error = test_string_key (ht, 0); + if (error) + clib_error_report (error); + + error = test_string_key (ht, 1); + if (error) + clib_error_report (error); + + return 0; +} + +#ifdef CLIB_UNIX +int +main (int argc, char *argv[]) +{ + unformat_input_t i; + int ret; + + clib_mem_init (0, 3ULL << 30); + + verbose = (argc > 1); + unformat_init_command_line (&i, argv); + ret = test_mhash_main (&i); + unformat_free (&i); + + return ret; +} +#endif /* CLIB_UNIX */ diff --git a/src/vppinfra/unformat.c b/src/vppinfra/unformat.c index fe1a46e4a12..522517888c3 100644 --- a/src/vppinfra/unformat.c +++ b/src/vppinfra/unformat.c @@ -1185,6 +1185,31 @@ unformat_double_quoted_string (unformat_input_t *input, va_list *va) #endif /* CLIB_UNIX */ +__clib_export uword +unformat_u8 (unformat_input_t *input, va_list *args) +{ + u8 *d = va_arg (*args, u8 *); + + u32 tmp; + if (!unformat (input, "%u", &tmp) || tmp > CLIB_U8_MAX) + return 0; + + *d = tmp; + return 1; +} + +__clib_export uword +unformat_u16 (unformat_input_t *input, va_list *args) +{ + u16 *d = va_arg (*args, u16 *); + + u32 tmp; + if (!unformat (input, "%u", &tmp) || tmp > CLIB_U16_MAX) + return 0; + + *d = tmp; + return 1; +} /* * fd.io coding-style-patch-verification: ON diff --git a/src/vppinfra/unix-misc.c b/src/vppinfra/unix-misc.c index e0591ff4604..31c0a489e8d 100644 --- a/src/vppinfra/unix-misc.c +++ b/src/vppinfra/unix-misc.c @@ -35,6 +35,10 @@ WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + #include <vppinfra/error.h> #include <vppinfra/os.h> #include <vppinfra/bitmap.h> @@ -42,6 +46,15 @@ #include <vppinfra/format.h> #ifdef __linux__ #include <vppinfra/linux/sysfs.h> +#include <sched.h> +#elif defined(__FreeBSD__) +#define _WANT_FREEBSD_BITSET +#include <sys/cdefs.h> +#include <sys/param.h> +#include <sys/types.h> +#include <sys/cpuset.h> +#include <sys/domainset.h> +#include <sys/sysctl.h> #endif #include <sys/stat.h> @@ -275,10 +288,70 @@ os_get_online_cpu_core_bitmap () } __clib_export clib_bitmap_t * +os_get_cpu_affinity_bitmap (int pid) +{ +#if __linux + int index, ret; + cpu_set_t cpuset; + uword *affinity_cpus; + + clib_bitmap_alloc (affinity_cpus, sizeof (cpu_set_t)); + clib_bitmap_zero (affinity_cpus); + + __CPU_ZERO_S (sizeof (cpu_set_t), &cpuset); + + ret = sched_getaffinity (0, sizeof (cpu_set_t), &cpuset); + + if (ret < 0) + { + clib_bitmap_free (affinity_cpus); + return 0; + } + + for (index = 0; index < sizeof (cpu_set_t); index++) + if (__CPU_ISSET_S (index, sizeof (cpu_set_t), &cpuset)) + clib_bitmap_set (affinity_cpus, index, 1); + return affinity_cpus; +#elif defined(__FreeBSD__) + cpuset_t mask; + uword *r = NULL; + + if (cpuset_getaffinity (CPU_LEVEL_CPUSET, CPU_WHICH_CPUSET, -1, + sizeof (mask), &mask) != 0) + { + clib_bitmap_free (r); + return NULL; + } + + for (int bit = 0; bit < CPU_SETSIZE; bit++) + clib_bitmap_set (r, bit, CPU_ISSET (bit, &mask)); + + return r; +#else + return NULL; +#endif +} + +__clib_export clib_bitmap_t * os_get_online_cpu_node_bitmap () { #if __linux__ return clib_sysfs_read_bitmap ("/sys/devices/system/node/online"); +#elif defined(__FreeBSD__) + domainset_t domain; + uword *r = NULL; + int policy; + + if (cpuset_getdomain (CPU_LEVEL_CPUSET, CPU_WHICH_CPUSET, -1, + sizeof (domain), &domain, &policy) != 0) + { + clib_bitmap_free (r); + return NULL; + } + + for (int bit = 0; bit < CPU_SETSIZE; bit++) + clib_bitmap_set (r, bit, CPU_ISSET (bit, &domain)); + return r; #else return 0; #endif @@ -327,6 +400,28 @@ os_get_cpu_phys_core_id (int cpu_id) #endif } +__clib_export u8 * +os_get_exec_path () +{ + u8 *rv = 0; +#ifdef __linux__ + char tmp[PATH_MAX]; + ssize_t sz = readlink ("/proc/self/exe", tmp, sizeof (tmp)); + + if (sz <= 0) + return 0; +#else + char tmp[MAXPATHLEN]; + int mib[4] = { CTL_KERN, KERN_PROC, KERN_PROC_PATHNAME, -1 }; + size_t sz = MAXPATHLEN; + + if (sysctl (mib, 4, tmp, &sz, NULL, 0) == -1) + return 0; +#endif + vec_add (rv, tmp, sz); + return rv; +} + /* * fd.io coding-style-patch-verification: ON * diff --git a/src/vppinfra/unix.h b/src/vppinfra/unix.h index 651f9bb99e0..d0ddb93a46f 100644 --- a/src/vppinfra/unix.h +++ b/src/vppinfra/unix.h @@ -68,6 +68,10 @@ clib_bitmap_t *os_get_cpu_on_node_bitmap (int node); /* Retrieve physical core id of specific cpu, -1 if not available */ int os_get_cpu_phys_core_id (int cpu); +/* Retrieve the path of the current executable as a vector (not + * null-terminated). */ +u8 *os_get_exec_path (); + #endif /* included_clib_unix_h */ /* diff --git a/src/vppinfra/vector/array_mask.h b/src/vppinfra/vector/array_mask.h index ba22d79560f..3d4a82ac01b 100644 --- a/src/vppinfra/vector/array_mask.h +++ b/src/vppinfra/vector/array_mask.h @@ -57,6 +57,7 @@ clib_array_mask_u32 (u32 *src, u32 mask, u32 n_elts) u32x4 mask4 = u32x4_splat (mask); *(u32x4u *) src &= mask4; *(u32x4u *) (src + n_elts - 4) &= mask4; + return; } #endif diff --git a/src/vppinfra/vector/compress.h b/src/vppinfra/vector/compress.h index d2ed716ac8e..5429113984b 100644 --- a/src/vppinfra/vector/compress.h +++ b/src/vppinfra/vector/compress.h @@ -34,6 +34,37 @@ clib_compress_u64_x64 (u64 *dst, u64 *src, u64 mask) return dst; } +static_always_inline u64 * +clib_compress_u64_x64_masked (u64 *dst, u64 *src, u64 mask) +{ +#if defined(CLIB_HAVE_VEC512_COMPRESS) && \ + defined(CLIB_HAVE_VEC512_MASK_LOAD_STORE) + u64x8u *sv = (u64x8u *) src; + for (int i = 0; i < 8; i++) + { + u64x8u s = u64x8_mask_load_zero (&sv[i], mask); + u64x8_compress_store (s, mask, dst); + dst += _popcnt32 ((u8) mask); + mask >>= 8; + } +#elif defined(CLIB_HAVE_VEC256_COMPRESS) && \ + defined(CLIB_HAVE_VEC256_MASK_LOAD_STORE) + u64x4u *sv = (u64x4u *) src; + for (int i = 0; i < 16; i++) + { + u64x4u s = u64x4_mask_load_zero (&sv[i], mask); + u64x4_compress_store (s, mask, dst); + dst += _popcnt32 (((u8) mask) & 0x0f); + mask >>= 4; + } +#else + u32 i; + foreach_set_bit_index (i, mask) + dst++[0] = src[i]; +#endif + return dst; +} + /** \brief Compress array of 64-bit elemments into destination array based on * mask @@ -66,7 +97,9 @@ clib_compress_u64 (u64 *dst, u64 *src, u64 *mask, u32 n_elts) if (PREDICT_TRUE (n_elts == 0)) return dst - dst0; - return clib_compress_u64_x64 (dst, src, mask[0] & pow2_mask (n_elts)) - dst0; + return clib_compress_u64_x64_masked (dst, src, + mask[0] & pow2_mask (n_elts)) - + dst0; } static_always_inline u32 * @@ -97,6 +130,38 @@ clib_compress_u32_x64 (u32 *dst, u32 *src, u64 mask) return dst; } +static_always_inline u32 * +clib_compress_u32_x64_masked (u32 *dst, u32 *src, u64 mask) +{ +#if defined(CLIB_HAVE_VEC512_COMPRESS) && \ + defined(CLIB_HAVE_VEC512_MASK_LOAD_STORE) + u32x16u *sv = (u32x16u *) src; + for (int i = 0; i < 4; i++) + { + u32x16u s = u32x16_mask_load_zero (&sv[i], mask); + u32x16_compress_store (s, mask, dst); + dst += _popcnt32 ((u16) mask); + mask >>= 16; + } + +#elif defined(CLIB_HAVE_VEC256_COMPRESS) && \ + defined(CLIB_HAVE_VEC256_MASK_LOAD_STORE) + u32x8u *sv = (u32x8u *) src; + for (int i = 0; i < 8; i++) + { + u32x8u s = u32x8_mask_load_zero (&sv[i], mask); + u32x8_compress_store (s, mask, dst); + dst += _popcnt32 ((u8) mask); + mask >>= 8; + } +#else + u32 i; + foreach_set_bit_index (i, mask) + dst++[0] = src[i]; +#endif + return dst; +} + /** \brief Compress array of 32-bit elemments into destination array based on * mask @@ -129,7 +194,9 @@ clib_compress_u32 (u32 *dst, u32 *src, u64 *mask, u32 n_elts) if (PREDICT_TRUE (n_elts == 0)) return dst - dst0; - return clib_compress_u32_x64 (dst, src, mask[0] & pow2_mask (n_elts)) - dst0; + return clib_compress_u32_x64_masked (dst, src, + mask[0] & pow2_mask (n_elts)) - + dst0; } static_always_inline u16 * @@ -151,6 +218,27 @@ clib_compress_u16_x64 (u16 *dst, u16 *src, u64 mask) return dst; } +static_always_inline u16 * +clib_compress_u16_x64_masked (u16 *dst, u16 *src, u64 mask) +{ +#if defined(CLIB_HAVE_VEC512_COMPRESS_U8_U16) && \ + defined(CLIB_HAVE_VEC512_MASK_LOAD_STORE) + u16x32u *sv = (u16x32u *) src; + for (int i = 0; i < 2; i++) + { + u16x32u s = u16x32_mask_load_zero (&sv[i], mask); + u16x32_compress_store (s, mask, dst); + dst += _popcnt32 ((u32) mask); + mask >>= 32; + } +#else + u32 i; + foreach_set_bit_index (i, mask) + dst++[0] = src[i]; +#endif + return dst; +} + /** \brief Compress array of 16-bit elemments into destination array based on * mask @@ -183,7 +271,9 @@ clib_compress_u16 (u16 *dst, u16 *src, u64 *mask, u32 n_elts) if (PREDICT_TRUE (n_elts == 0)) return dst - dst0; - return clib_compress_u16_x64 (dst, src, mask[0] & pow2_mask (n_elts)) - dst0; + return clib_compress_u16_x64_masked (dst, src, + mask[0] & pow2_mask (n_elts)) - + dst0; } static_always_inline u8 * @@ -201,6 +291,23 @@ clib_compress_u8_x64 (u8 *dst, u8 *src, u64 mask) return dst; } +static_always_inline u8 * +clib_compress_u8_x64_masked (u8 *dst, u8 *src, u64 mask) +{ +#if defined(CLIB_HAVE_VEC512_COMPRESS_U8_U16) && \ + defined(CLIB_HAVE_VEC512_MASK_LOAD_STORE) + u8x64u *sv = (u8x64u *) src; + u8x64u s = u8x64_mask_load_zero (sv, mask); + u8x64_compress_store (s, mask, dst); + dst += _popcnt64 (mask); +#else + u32 i; + foreach_set_bit_index (i, mask) + dst++[0] = src[i]; +#endif + return dst; +} + /** \brief Compress array of 8-bit elemments into destination array based on * mask @@ -233,7 +340,8 @@ clib_compress_u8 (u8 *dst, u8 *src, u64 *mask, u32 n_elts) if (PREDICT_TRUE (n_elts == 0)) return dst - dst0; - return clib_compress_u8_x64 (dst, src, mask[0] & pow2_mask (n_elts)) - dst0; + return clib_compress_u8_x64_masked (dst, src, mask[0] & pow2_mask (n_elts)) - + dst0; } #endif diff --git a/src/vppinfra/vector/mask_compare.h b/src/vppinfra/vector/mask_compare.h index 92d5ca35474..fc72d7dac35 100644 --- a/src/vppinfra/vector/mask_compare.h +++ b/src/vppinfra/vector/mask_compare.h @@ -8,7 +8,7 @@ #include <vppinfra/memcpy.h> static_always_inline u64 -clib_mask_compare_u16_x64 (u16 v, u16 *a, u32 n_elts) +clib_mask_compare_u16_x64 (u16 v, u16 *a) { u64 mask = 0; #if defined(CLIB_HAVE_VEC512) @@ -47,6 +47,38 @@ clib_mask_compare_u16_x64 (u16 v, u16 *a, u32 n_elts) (u64) i8x16_msb_mask (i8x16_pack (v8 == av[4], v8 == av[5])) << 32 | (u64) i8x16_msb_mask (i8x16_pack (v8 == av[6], v8 == av[7])) << 48); #else + for (int i = 0; i < 64; i++) + if (a[i] == v) + mask |= 1ULL << i; +#endif + return mask; +} + +static_always_inline u64 +clib_mask_compare_u16_x64_n (u16 v, u16 *a, u32 n_elts) +{ + u64 mask = 0; + CLIB_UNUSED (u64 data_mask) = pow2_mask (n_elts); +#if defined(CLIB_HAVE_VEC512) + u16x32 v32 = u16x32_splat (v); + u16x32u *av = (u16x32u *) a; + mask = ((u64) u16x32_is_equal_mask ( + u16x32_mask_load_zero (&av[0], data_mask), v32) | + (u64) u16x32_is_equal_mask ( + u16x32_mask_load_zero (&av[1], data_mask >> 32), v32) + << 32); +#elif defined(CLIB_HAVE_VEC256) && defined(CLIB_HAVE_VEC256_MASK_LOAD_STORE) + u16x16 v16 = u16x16_splat (v); + u16x16u *av = (u16x16u *) a; + i8x32 x; + + x = i8x32_pack (v16 == u16x16_mask_load_zero (&av[0], data_mask), + v16 == u16x16_mask_load_zero (&av[1], data_mask >> 16)); + mask = i8x32_msb_mask ((i8x32) u64x4_permute (x, 0, 2, 1, 3)); + x = i8x32_pack (v16 == u16x16_mask_load_zero (&av[2], data_mask >> 32), + v16 == u16x16_mask_load_zero (&av[3], data_mask >> 48)); + mask |= (u64) i8x32_msb_mask ((i8x32) u64x4_permute (x, 0, 2, 1, 3)) << 32; +#else for (int i = 0; i < n_elts; i++) if (a[i] == v) mask |= 1ULL << i; @@ -68,7 +100,7 @@ clib_mask_compare_u16 (u16 v, u16 *a, u64 *mask, u32 n_elts) { while (n_elts >= 64) { - mask++[0] = clib_mask_compare_u16_x64 (v, a, 64); + mask++[0] = clib_mask_compare_u16_x64 (v, a); n_elts -= 64; a += 64; } @@ -76,11 +108,11 @@ clib_mask_compare_u16 (u16 v, u16 *a, u64 *mask, u32 n_elts) if (PREDICT_TRUE (n_elts == 0)) return; - mask[0] = clib_mask_compare_u16_x64 (v, a, n_elts) & pow2_mask (n_elts); + mask[0] = clib_mask_compare_u16_x64_n (v, a, n_elts) & pow2_mask (n_elts); } static_always_inline u64 -clib_mask_compare_u32_x64 (u32 v, u32 *a, u32 n_elts) +clib_mask_compare_u32_x64 (u32 v, u32 *a) { u64 mask = 0; #if defined(CLIB_HAVE_VEC512) @@ -131,6 +163,57 @@ clib_mask_compare_u32_x64 (u32 v, u32 *a, u32 n_elts) } #else + for (int i = 0; i < 64; i++) + if (a[i] == v) + mask |= 1ULL << i; +#endif + return mask; +} + +static_always_inline u64 +clib_mask_compare_u32_x64_n (u32 v, u32 *a, u32 n_elts) +{ + u64 mask = 0; + CLIB_UNUSED (u64 data_mask) = pow2_mask (n_elts); +#if defined(CLIB_HAVE_VEC512) + u32x16 v16 = u32x16_splat (v); + u32x16u *av = (u32x16u *) a; + mask = ((u64) u32x16_is_equal_mask ( + u32x16_mask_load_zero (&av[0], data_mask), v16) | + (u64) u32x16_is_equal_mask ( + u32x16_mask_load_zero (&av[1], data_mask >> 16), v16) + << 16 | + (u64) u32x16_is_equal_mask ( + u32x16_mask_load_zero (&av[2], data_mask >> 32), v16) + << 32 | + (u64) u32x16_is_equal_mask ( + u32x16_mask_load_zero (&av[3], data_mask >> 48), v16) + << 48); +#elif defined(CLIB_HAVE_VEC256) && defined(CLIB_HAVE_VEC256_MASK_LOAD_STORE) + u32x8 v8 = u32x8_splat (v); + u32x8u *av = (u32x8u *) a; + u32x8 m = { 0, 4, 1, 5, 2, 6, 3, 7 }; + i8x32 c; + + c = i8x32_pack ( + i16x16_pack ( + (i32x8) (v8 == u32x8_mask_load_zero (&av[0], data_mask)), + (i32x8) (v8 == u32x8_mask_load_zero (&av[1], data_mask >> 8))), + i16x16_pack ( + (i32x8) (v8 == u32x8_mask_load_zero (&av[2], data_mask >> 16)), + (i32x8) (v8 == u32x8_mask_load_zero (&av[3], data_mask >> 24)))); + mask = i8x32_msb_mask ((i8x32) u32x8_permute ((u32x8) c, m)); + + c = i8x32_pack ( + i16x16_pack ( + (i32x8) (v8 == u32x8_mask_load_zero (&av[4], data_mask >> 32)), + (i32x8) (v8 == u32x8_mask_load_zero (&av[5], data_mask >> 40))), + i16x16_pack ( + (i32x8) (v8 == u32x8_mask_load_zero (&av[6], data_mask >> 48)), + (i32x8) (v8 == u32x8_mask_load_zero (&av[7], data_mask >> 56)))); + mask |= (u64) i8x32_msb_mask ((i8x32) u32x8_permute ((u32x8) c, m)) << 32; + mask |= (u64) i8x32_msb_mask ((i8x32) u32x8_permute ((u32x8) c, m)) << 32; +#else for (int i = 0; i < n_elts; i++) if (a[i] == v) mask |= 1ULL << i; @@ -152,7 +235,7 @@ clib_mask_compare_u32 (u32 v, u32 *a, u64 *bitmap, u32 n_elts) { while (n_elts >= 64) { - bitmap++[0] = clib_mask_compare_u32_x64 (v, a, 64); + bitmap++[0] = clib_mask_compare_u32_x64 (v, a); n_elts -= 64; a += 64; } @@ -160,11 +243,11 @@ clib_mask_compare_u32 (u32 v, u32 *a, u64 *bitmap, u32 n_elts) if (PREDICT_TRUE (n_elts == 0)) return; - bitmap[0] = clib_mask_compare_u32_x64 (v, a, n_elts) & pow2_mask (n_elts); + bitmap[0] = clib_mask_compare_u32_x64_n (v, a, n_elts) & pow2_mask (n_elts); } static_always_inline u64 -clib_mask_compare_u64_x64 (u64 v, u64 *a, u32 n_elts) +clib_mask_compare_u64_x64 (u64 v, u64 *a) { u64 mask = 0; #if defined(CLIB_HAVE_VEC512) @@ -190,6 +273,59 @@ clib_mask_compare_u64_x64 (u64 v, u64 *a, u32 n_elts) mask |= _pext_u64 (l | h << 32, 0x0101010101010101) << (i * 4); } #else + for (int i = 0; i < 64; i++) + if (a[i] == v) + mask |= 1ULL << i; +#endif + return mask; +} + +static_always_inline u64 +clib_mask_compare_u64_x64_n (u64 v, u64 *a, u32 n_elts) +{ + u64 mask = 0; + CLIB_UNUSED (u64 data_mask) = pow2_mask (n_elts); +#if defined(CLIB_HAVE_VEC512) + u64x8 v8 = u64x8_splat (v); + u64x8u *av = (u64x8u *) a; + mask = + ((u64) u64x8_is_equal_mask (u64x8_mask_load_zero (&av[0], data_mask), v8) | + (u64) u64x8_is_equal_mask (u64x8_mask_load_zero (&av[1], data_mask >> 8), + v8) + << 8 | + (u64) u64x8_is_equal_mask (u64x8_mask_load_zero (&av[2], data_mask >> 16), + v8) + << 16 | + (u64) u64x8_is_equal_mask (u64x8_mask_load_zero (&av[3], data_mask >> 24), + v8) + << 24 | + (u64) u64x8_is_equal_mask (u64x8_mask_load_zero (&av[4], data_mask >> 32), + v8) + << 32 | + (u64) u64x8_is_equal_mask (u64x8_mask_load_zero (&av[5], data_mask >> 40), + v8) + << 40 | + (u64) u64x8_is_equal_mask (u64x8_mask_load_zero (&av[6], data_mask >> 48), + v8) + << 48 | + (u64) u64x8_is_equal_mask (u64x8_mask_load_zero (&av[7], data_mask >> 56), + v8) + << 56); + +#elif defined(CLIB_HAVE_VEC256) && defined(__BMI2__) && \ + defined(CLIB_HAVE_VEC256_MASK_LOAD_STORE) + u64x4 v4 = u64x4_splat (v); + u64x4u *av = (u64x4u *) a; + + for (int i = 0; i < 16; i += 2) + { + u64 l = u8x32_msb_mask (v4 == u64x4_mask_load_zero (&av[i], data_mask)); + u64 h = u8x32_msb_mask ( + v4 == u64x4_mask_load_zero (&av[i + 1], data_mask >> 4)); + mask |= _pext_u64 (l | h << 32, 0x0101010101010101) << (i * 4); + data_mask >>= 8; + } +#else for (int i = 0; i < n_elts; i++) if (a[i] == v) mask |= 1ULL << i; @@ -211,7 +347,7 @@ clib_mask_compare_u64 (u64 v, u64 *a, u64 *bitmap, u32 n_elts) { while (n_elts >= 64) { - bitmap++[0] = clib_mask_compare_u64_x64 (v, a, 64); + bitmap++[0] = clib_mask_compare_u64_x64 (v, a); n_elts -= 64; a += 64; } @@ -219,7 +355,7 @@ clib_mask_compare_u64 (u64 v, u64 *a, u64 *bitmap, u32 n_elts) if (PREDICT_TRUE (n_elts == 0)) return; - bitmap[0] = clib_mask_compare_u64_x64 (v, a, n_elts) & pow2_mask (n_elts); + bitmap[0] = clib_mask_compare_u64_x64_n (v, a, n_elts) & pow2_mask (n_elts); } #endif |