diff options
Diffstat (limited to 'examples/redis-unstable/src/mstr.c')
| -rw-r--r-- | examples/redis-unstable/src/mstr.c | 528 |
1 files changed, 528 insertions, 0 deletions
diff --git a/examples/redis-unstable/src/mstr.c b/examples/redis-unstable/src/mstr.c new file mode 100644 index 0000000..97f7145 --- /dev/null +++ b/examples/redis-unstable/src/mstr.c @@ -0,0 +1,528 @@ +/* + * Copyright Redis Ltd. 2024 - present + * + * Licensed under your choice of (a) the Redis Source Available License 2.0 + * (RSALv2); or (b) the Server Side Public License v1 (SSPLv1); or (c) the + * GNU Affero General Public License v3 (AGPLv3). + */ + +#include <string.h> +#include <assert.h> +#include "sdsalloc.h" +#include "mstr.h" +#include "stdio.h" + +#define NULL_SIZE 1 + +static inline char mstrReqType(size_t string_size); +static inline int mstrHdrSize(char type); +static inline int mstrSumMetaLen(mstrKind *k, mstrFlags flags); +static inline size_t mstrAllocLen(const mstr s, struct mstrKind *kind); + +/*** mstr API ***/ + +/* Create mstr without any metadata attached, based on string 'initStr'. + * - If initStr equals NULL, then only allocation will be made. + * - string of mstr is always null-terminated. + */ +mstr mstrNew(const char *initStr, size_t lenStr, int trymalloc, size_t *usable) { + unsigned char *pInfo; /* pointer to mstr info field */ + void *sh; + mstr s; + char type = mstrReqType(lenStr); + int mstrHdr = mstrHdrSize(type); + + assert(lenStr + mstrHdr + 1 > lenStr); /* Catch size_t overflow */ + + size_t len = mstrHdr + lenStr + NULL_SIZE; + sh = trymalloc? s_trymalloc_usable(len, usable) : s_malloc_usable(len, usable); + + if (sh == NULL) return NULL; + + s = (char*)sh + mstrHdr; + pInfo = ((unsigned char*)s) - 1; + + switch(type) { + case MSTR_TYPE_5: { + *pInfo = CREATE_MSTR_INFO(lenStr, 0 /*ismeta*/, type); + break; + } + case MSTR_TYPE_8: { + MSTR_HDR_VAR(8,s); + *pInfo = CREATE_MSTR_INFO(0 /*unused*/, 0 /*ismeta*/, type); + sh->len = lenStr; + break; + } + case MSTR_TYPE_16: { + MSTR_HDR_VAR(16,s); + *pInfo = CREATE_MSTR_INFO(0 /*unused*/, 0 /*ismeta*/, type); + sh->len = lenStr; + break; + } + case MSTR_TYPE_64: { + MSTR_HDR_VAR(64,s); + *pInfo = CREATE_MSTR_INFO(0 /*unused*/, 0 /*ismeta*/, type); + sh->len = lenStr; + break; + } + } + + if (initStr && lenStr) + memcpy(s, initStr, lenStr); + + s[lenStr] = '\0'; + return s; +} + +/* Creates mstr with given string. Reserve space for metadata. + * + * Note: mstrNew(s,l,u) and mstrNewWithMeta(s,l,0,u) are not the same. The first allocates + * just string. The second allocates a string with flags (yet without any metadata + * structures allocated). + */ +mstr mstrNewWithMeta(struct mstrKind *kind, const char *initStr, size_t lenStr, mstrFlags metaFlags, int trymalloc, size_t *usable) { + unsigned char *pInfo; /* pointer to mstr info field */ + char *allocMstr; + mstr mstrPtr; + char type = mstrReqType(lenStr); + int mstrHdr = mstrHdrSize(type); + int sumMetaLen = mstrSumMetaLen(kind, metaFlags); + + + /* mstrSumMetaLen() + sizeof(mstrFlags) + sizeof(mstrhdrX) + lenStr */ + + size_t allocLen = sumMetaLen + sizeof(mstrFlags) + mstrHdr + lenStr + NULL_SIZE; + allocMstr = trymalloc? s_trymalloc_usable(allocLen, usable) : s_malloc_usable(allocLen, usable); + + if (allocMstr == NULL) return NULL; + + /* metadata is located at the beginning of the allocation, then meta-flags and lastly the string */ + mstrFlags *pMetaFlags = (mstrFlags *) (allocMstr + sumMetaLen) ; + mstrPtr = ((char*) pMetaFlags) + sizeof(mstrFlags) + mstrHdr; + pInfo = ((unsigned char*)mstrPtr) - 1; + + switch(type) { + case MSTR_TYPE_5: { + *pInfo = CREATE_MSTR_INFO(lenStr, 1 /*ismeta*/, type); + break; + } + case MSTR_TYPE_8: { + MSTR_HDR_VAR(8, mstrPtr); + sh->len = lenStr; + *pInfo = CREATE_MSTR_INFO(0 /*unused*/, 1 /*ismeta*/, type); + break; + } + case MSTR_TYPE_16: { + MSTR_HDR_VAR(16, mstrPtr); + sh->len = lenStr; + *pInfo = CREATE_MSTR_INFO(0 /*unused*/, 1 /*ismeta*/, type); + break; + } + case MSTR_TYPE_64: { + MSTR_HDR_VAR(64, mstrPtr); + sh->len = lenStr; + *pInfo = CREATE_MSTR_INFO(0 /*unused*/, 1 /*ismeta*/, type); + break; + } + } + *pMetaFlags = metaFlags; + if (initStr != NULL) memcpy(mstrPtr, initStr, lenStr); + mstrPtr[lenStr] = '\0'; + + return mstrPtr; +} + +/* Create copy of mstr. Flags can be modified. For each metadata flag, if + * same flag is set on both, then copy its metadata. */ +mstr mstrNewCopy(struct mstrKind *kind, mstr src, mstrFlags newFlags, size_t *usable) { + mstr dst; + + /* if no flags are set, then just copy the string */ + if (newFlags == 0) return mstrNew(src, mstrlen(src), 0, usable); + + dst = mstrNewWithMeta(kind, src, mstrlen(src), newFlags, 0, usable); + memcpy(dst, src, mstrlen(src) + 1); + + /* if metadata is attached to src, then selectively copy metadata */ + if (mstrIsMetaAttached(src)) { + mstrFlags *pFlags1 = mstrFlagsRef(src), + *pFlags2 = mstrFlagsRef(dst); + + mstrFlags flags1Shift = *pFlags1, + flags2Shift = *pFlags2; + + unsigned char *at1 = ((unsigned char *) pFlags1), + *at2 = ((unsigned char *) pFlags2); + + /* if the flag is set on both, then copy the metadata */ + for (int i = 0; flags1Shift != 0; ++i) { + int isFlag1Set = flags1Shift & 0x1; + int isFlag2Set = flags2Shift & 0x1; + + if (isFlag1Set) at1 -= kind->metaSize[i]; + if (isFlag2Set) at2 -= kind->metaSize[i]; + + if (isFlag1Set && isFlag2Set) + memcpy(at2, at1, kind->metaSize[i]); + flags1Shift >>= 1; + flags2Shift >>= 1; + } + } + return dst; +} + +/* Free mstring. Note, mstrKind is required to eval sizeof metadata and find start + * of allocation but if mstrIsMetaAttached(s) is false, you can pass NULL as well. + */ +void mstrFree(struct mstrKind *kind, mstr s, size_t *usable) { + size_t oldsize = 0; + if (s != NULL) + s_free_usable(mstrGetAllocPtr(kind, s), &oldsize); + if (usable != NULL) *usable = oldsize; +} + +/* return ref to metadata flags. Useful to modify directly flags which doesn't + * include metadata payload */ +mstrFlags *mstrFlagsRef(mstr s) { + switch(s[-1]&MSTR_TYPE_MASK) { + case MSTR_TYPE_5: + return ((mstrFlags *) (s - sizeof(struct mstrhdr5))) - 1; + case MSTR_TYPE_8: + return ((mstrFlags *) (s - sizeof(struct mstrhdr8))) - 1; + case MSTR_TYPE_16: + return ((mstrFlags *) (s - sizeof(struct mstrhdr16))) - 1; + default: /* MSTR_TYPE_64: */ + return ((mstrFlags *) (s - sizeof(struct mstrhdr64))) - 1; + } +} + +/* Return a reference to corresponding metadata of the specified metadata flag + * index (flagIdx). If the metadata doesn't exist, it still returns a reference + * to the starting location where it would have been written among other metadatas. + * To verify if `flagIdx` of some metadata is attached, use `mstrGetFlag(s, flagIdx)`. + */ +void *mstrMetaRef(mstr s, struct mstrKind *kind, int flagIdx) { + int metaOffset = 0; + /* start iterating from flags backward */ + mstrFlags *pFlags = mstrFlagsRef(s); + mstrFlags tmp = *pFlags; + + for (int i = 0 ; i <= flagIdx ; ++i) { + if (tmp & 0x1) metaOffset += kind->metaSize[i]; + tmp >>= 1; + } + return ((char *)pFlags) - metaOffset; +} + +/* mstr layout: [meta-data#N]...[meta-data#0][mstrFlags][mstrhdr][string][null] */ +void *mstrGetAllocPtr(struct mstrKind *kind, mstr str) { + if (!mstrIsMetaAttached(str)) + return (char*)str - mstrHdrSize(str[-1]); + + int totalMetaLen = mstrSumMetaLen(kind, *mstrFlagsRef(str)); + return (char*)str - mstrHdrSize(str[-1]) - sizeof(mstrFlags) - totalMetaLen; +} + +/* Prints in the following fashion: + * [0x7f8bd8816017] my_mstr: foo (strLen=3, mstrLen=11, isMeta=1, metaFlags=0x1) + * [0x7f8bd8816010] >> meta[0]: 0x78 0x56 0x34 0x12 (metaLen=4) + */ +void mstrPrint(mstr s, struct mstrKind *kind, int verbose) { + mstrFlags mflags, tmp; + int isMeta = mstrIsMetaAttached(s); + + tmp = mflags = (isMeta) ? *mstrFlagsRef(s) : 0; + + if (!isMeta) { + printf("[%p] %s: %s (strLen=%zu, mstrLen=%zu, isMeta=0)\n", + (void *)s, kind->name, s, mstrlen(s), mstrAllocLen(s, kind)); + return; + } + + printf("[%p] %s: %s (strLen=%zu, mstrLen=%zu, isMeta=1, metaFlags=0x%x)\n", + (void *)s, kind->name, s, mstrlen(s), mstrAllocLen(s, kind), mflags); + + if (verbose) { + for (unsigned int i = 0 ; i < NUM_MSTR_FLAGS ; ++i) { + if (tmp & 0x1) { + int mSize = kind->metaSize[i]; + void *mRef = mstrMetaRef(s, kind, i); + printf("[%p] >> meta[%d]:", mRef, i); + for (int j = 0 ; j < mSize ; ++j) { + printf(" 0x%02x", ((unsigned char *) mRef)[j]); + } + printf(" (metaLen=%d)\n", mSize); + } + tmp >>= 1; + } + } +} + +/* return length of the string (ignoring metadata attached) */ +size_t mstrlen(const mstr s) { + unsigned char info = s[-1]; + switch(info & MSTR_TYPE_MASK) { + case MSTR_TYPE_5: + return MSTR_TYPE_5_LEN(info); + case MSTR_TYPE_8: + return MSTR_HDR(8,s)->len; + case MSTR_TYPE_16: + return MSTR_HDR(16,s)->len; + default: /* MSTR_TYPE_64: */ + return MSTR_HDR(64,s)->len; + } +} + +/*** mstr internals ***/ + +static inline int mstrSumMetaLen(mstrKind *k, mstrFlags flags) { + int total = 0; + int i = 0 ; + while (flags) { + total += (flags & 0x1) ? k->metaSize[i] : 0; + flags >>= 1; + ++i; + } + return total; +} + +/* mstrSumMetaLen() + sizeof(mstrFlags) + sizeof(mstrhdrX) + strlen + '\0' */ +static inline size_t mstrAllocLen(const mstr s, struct mstrKind *kind) { + int hdrlen; + mstrFlags *pMetaFlags; + size_t strlen = 0; + + int isMeta = mstrIsMetaAttached(s); + unsigned char info = s[-1]; + + switch(info & MSTR_TYPE_MASK) { + case MSTR_TYPE_5: + strlen = MSTR_TYPE_5_LEN(info); + hdrlen = sizeof(struct mstrhdr5); + pMetaFlags = ((mstrFlags *) MSTR_HDR(5, s)) - 1; + break; + case MSTR_TYPE_8: + strlen = MSTR_HDR(8,s)->len; + hdrlen = sizeof(struct mstrhdr8); + pMetaFlags = ((mstrFlags *) MSTR_HDR(8, s)) - 1; + break; + case MSTR_TYPE_16: + strlen = MSTR_HDR(16,s)->len; + hdrlen = sizeof(struct mstrhdr16); + pMetaFlags = ((mstrFlags *) MSTR_HDR(16, s)) - 1; + break; + default: /* MSTR_TYPE_64: */ + strlen = MSTR_HDR(64,s)->len; + hdrlen = sizeof(struct mstrhdr64); + pMetaFlags = ((mstrFlags *) MSTR_HDR(64, s)) - 1; + break; + } + return hdrlen + strlen + NULL_SIZE + ((isMeta) ? (mstrSumMetaLen(kind, *pMetaFlags) + sizeof(mstrFlags)) : 0); +} + +/* returns pointer to the beginning of malloc() of mstr */ +void *mstrGetStartAlloc(mstr s, struct mstrKind *kind) { + int hdrlen; + mstrFlags *pMetaFlags; + + int isMeta = mstrIsMetaAttached(s); + + switch(s[-1]&MSTR_TYPE_MASK) { + case MSTR_TYPE_5: + hdrlen = sizeof(struct mstrhdr5); + pMetaFlags = ((mstrFlags *) MSTR_HDR(5, s)) - 1; + break; + case MSTR_TYPE_8: + hdrlen = sizeof(struct mstrhdr8); + pMetaFlags = ((mstrFlags *) MSTR_HDR(8, s)) - 1; + break; + case MSTR_TYPE_16: + hdrlen = sizeof(struct mstrhdr16); + pMetaFlags = ((mstrFlags *) MSTR_HDR(16, s)) - 1; + break; + default: /* MSTR_TYPE_64: */ + hdrlen = sizeof(struct mstrhdr64); + pMetaFlags = ((mstrFlags *) MSTR_HDR(64, s)) - 1; + break; + } + return (char *) s - hdrlen - ((isMeta) ? (mstrSumMetaLen(kind, *pMetaFlags) + sizeof(mstrFlags)) : 0); +} + +static inline int mstrHdrSize(char type) { + switch(type&MSTR_TYPE_MASK) { + case MSTR_TYPE_5: + return sizeof(struct mstrhdr5); + case MSTR_TYPE_8: + return sizeof(struct mstrhdr8); + case MSTR_TYPE_16: + return sizeof(struct mstrhdr16); + case MSTR_TYPE_64: + return sizeof(struct mstrhdr64); + } + return 0; +} + +static inline char mstrReqType(size_t string_size) { + if (string_size < 1<<5) + return MSTR_TYPE_5; + if (string_size < 1<<8) + return MSTR_TYPE_8; + if (string_size < 1<<16) + return MSTR_TYPE_16; + return MSTR_TYPE_64; +} + +#ifdef REDIS_TEST +#include <stdlib.h> +#include <assert.h> +#include "testhelp.h" +#include "limits.h" + +#ifndef UNUSED +#define UNUSED(x) (void)(x) +#endif + +/* Challenge mstr with metadata interesting enough that can include the case of hfield and hkey and more */ +#define B(idx) (1<<(idx)) + +#define META_IDX_MYMSTR_TTL4 0 +#define META_IDX_MYMSTR_TTL8 1 +#define META_IDX_MYMSTR_TYPE_ENC_LRU 2 // 4Bbit type, 4bit encoding, 24bits lru +#define META_IDX_MYMSTR_VALUE_PTR 3 +#define META_IDX_MYMSTR_FLAG_NO_META 4 + +#define TEST_CONTEXT(context) printf("\nContext: %s \n", context); + +int mstrTest(int argc, char **argv, int flags) { + UNUSED(argc); + UNUSED(argv); + UNUSED(flags); + + struct mstrKind kind_mymstr = { + .name = "my_mstr", + .metaSize[META_IDX_MYMSTR_TTL4] = 4, + .metaSize[META_IDX_MYMSTR_TTL8] = 8, + .metaSize[META_IDX_MYMSTR_TYPE_ENC_LRU] = 4, + .metaSize[META_IDX_MYMSTR_VALUE_PTR] = 8, + .metaSize[META_IDX_MYMSTR_FLAG_NO_META] = 0, + }; + + TEST_CONTEXT("Create simple short mstr") + { + char *str = "foo"; + mstr s = mstrNew(str, strlen(str), 0, NULL); + size_t expStrLen = strlen(str); + + test_cond("Verify str length and alloc length", + mstrAllocLen(s, NULL) == (1 + expStrLen + 1) && /* mstrhdr5 + str + null */ + mstrlen(s) == expStrLen && /* expected strlen(str) */ + memcmp(s, str, expStrLen + 1) == 0); + mstrFree(&kind_mymstr, s, NULL); + } + + TEST_CONTEXT("Create simple 40 bytes mstr") + { + char *str = "0123456789012345678901234567890123456789"; // 40 bytes + mstr s = mstrNew(str, strlen(str), 0, NULL); + + test_cond("Verify str length and alloc length", + mstrAllocLen(s, NULL) == (3 + 40 + 1) && /* mstrhdr8 + str + null */ + mstrlen(s) == 40 && + memcmp(s,str,40) == 0); + mstrFree(&kind_mymstr, s, NULL); + } + + TEST_CONTEXT("Create mstr with random characters") + { + long unsigned int i; + char str[66000]; + for (i = 0 ; i < sizeof(str) ; ++i) str[i] = rand() % 256; + + size_t len[] = { 31, 32, 33, 255, 256, 257, 65535, 65536, 65537, 66000}; + for (i = 0 ; i < sizeof(len) / sizeof(len[0]) ; ++i) { + char title[100]; + mstr s = mstrNew(str, len[i], 0, NULL); + size_t mstrhdrSize = (len[i] < 1<<5) ? sizeof(struct mstrhdr5) : + (len[i] < 1<<8) ? sizeof(struct mstrhdr8) : + (len[i] < 1<<16) ? sizeof(struct mstrhdr16) : + sizeof(struct mstrhdr64); + + snprintf(title, sizeof(title), "Verify string of length %zu", len[i]); + test_cond(title, + mstrAllocLen(s, NULL) == (mstrhdrSize + len[i] + 1) && /* mstrhdrX + str + null */ + mstrlen(s) == len[i] && + memcmp(s,str,len[i]) == 0); + mstrFree(&kind_mymstr, s, NULL); + } + } + + TEST_CONTEXT("Create short mstr with TTL4") + { + uint32_t *ttl; + mstr s = mstrNewWithMeta(&kind_mymstr, + "foo", + strlen("foo"), + B(META_IDX_MYMSTR_TTL4), /* allocate with TTL4 metadata */ + 0, + NULL); + + ttl = mstrMetaRef(s, &kind_mymstr, META_IDX_MYMSTR_TTL4); + *ttl = 0x12345678; + + test_cond("Verify memory-allocation and string lengths", + mstrAllocLen(s, &kind_mymstr) == (1 + 3 + 2 + 1 + 4) && /* mstrhdr5 + str + null + mstrFlags + TLL */ + mstrlen(s) == 3); + + unsigned char expMem[] = {0xFF, 0xFF, 0xFF, 0xFF, 0x01, 0x00, 0x1c, 'f', 'o', 'o', '\0' }; + uint32_t value = 0x12345678; + memcpy(expMem, &value, sizeof(uint32_t)); + test_cond("Verify string and TTL4 payload", memcmp( + mstrMetaRef(s, &kind_mymstr, 0) , expMem, sizeof(expMem)) == 0); + + test_cond("Verify mstrIsMetaAttached() function works", mstrIsMetaAttached(s) != 0); + + mstrFree(&kind_mymstr, s, NULL); + } + + TEST_CONTEXT("Create short mstr with TTL4 and value ptr ") + { + mstr s = mstrNewWithMeta(&kind_mymstr, "foo", strlen("foo"), + B(META_IDX_MYMSTR_TTL4) | B(META_IDX_MYMSTR_VALUE_PTR), 0, NULL); + *((uint32_t *) (mstrMetaRef(s, &kind_mymstr, + META_IDX_MYMSTR_TTL4))) = 0x12345678; + + test_cond("Verify length and alloc length", + mstrAllocLen(s, &kind_mymstr) == (1 + 3 + 1 + 2 + 4 + 8) && /* mstrhdr5 + str + null + mstrFlags + TLL + PTR */ + mstrlen(s) == 3); + mstrFree(&kind_mymstr, s, NULL); + } + + TEST_CONTEXT("Copy mstr and add it TTL4") + { + mstr s1 = mstrNew("foo", strlen("foo"), 0, NULL); + mstr s2 = mstrNewCopy(&kind_mymstr, s1, B(META_IDX_MYMSTR_TTL4), NULL); + *((uint32_t *) (mstrMetaRef(s2, &kind_mymstr, META_IDX_MYMSTR_TTL4))) = 0x12345678; + + test_cond("Verify new mstr includes TTL4", + mstrAllocLen(s2, &kind_mymstr) == (1 + 3 + 1 + 2 + 4) && /* mstrhdr5 + str + null + mstrFlags + TTL4 */ + mstrlen(s2) == 3 && /* 'foo' = 3bytes */ + memcmp(s2, "foo\0", 4) == 0); + + mstr s3 = mstrNewCopy(&kind_mymstr, s2, B(META_IDX_MYMSTR_TTL4), NULL); + unsigned char expMem[] = { 0xFF, 0xFF, 0xFF, 0xFF, 0x1, 0x0, 0x1c, 'f', 'o', 'o', '\0' }; + uint32_t value = 0x12345678; + memcpy(expMem, &value, sizeof(uint32_t)); + + char *ppp = mstrGetStartAlloc(s3, &kind_mymstr); + test_cond("Verify string and TTL4 payload", + memcmp(ppp, expMem, sizeof(expMem)) == 0); + + mstrPrint(s3, &kind_mymstr, 1); + mstrFree(&kind_mymstr, s1, NULL); + mstrFree(&kind_mymstr, s2, NULL); + mstrFree(&kind_mymstr, s3, NULL); + } + + return 0; +} +#endif |