Add Redis source code for testing

1 files changed, 408 insertions, 0 deletions

diff --git a/examples/redis-unstable/src/entry.c b/examples/redis-unstable/src/entry.c
new file mode 100644
index 0000000..9176c98
--- /dev/null
+++ b/examples/redis-unstable/src/entry.c
@@ -0,0 +1,408 @@
+/*
+ * Copyright (c) 2009-Present, Redis Ltd.
+ * All rights reserved.
+ *
+ * Copyright (c) 2024-present, Valkey contributors.
+ * All rights reserved.
+ */
+
+#include "server.h"
+#include "redisassert.h"
+#include "entry.h"
+
+/* Aggregates parameters for entry layout and serialization.
+ * Populated by setEntryWriteInfo() and consumed by needsNewAlloc() and entryWrite*(). */
+typedef struct EntryWriteInfo {
+    int isEmbdNewVal;          /* Whether value should be embedded */
+    int embdFieldType;         /* SDS type for the field */
+    size_t embdFieldSize;      /* Allocated size for SDS field */
+    size_t embdValueSize;      /* Required size for new embd value (SDS_TYPE_8) */
+    size_t expirySize;         /* Size of expiry metadata (0 if none) */
+    size_t newEntryAllocSize;  /* Total allocation size needed for new entry */
+    uint32_t flags;            /* Entry creation/update flags */
+} EntryWriteInfo;
+
+enum {
+    /* SDS aux flag. If set, it indicates that the entry has TTL metadata set. */
+    FIELD_SDS_AUX_BIT_ENTRY_HAS_EXPIRY = 0,
+    /* SDS aux flag. If set, it indicates that the entry has an embedded value
+     * pointer located in memory before the embedded field. If unset, the entry
+     * instead has an embedded value located after the embedded field. */
+    FIELD_SDS_AUX_BIT_ENTRY_HAS_VALUE_PTR = 1,
+    FIELD_SDS_AUX_BIT_ENTRY_MAX
+};
+static_assert(FIELD_SDS_AUX_BIT_ENTRY_MAX + SDS_TYPE_BITS < sizeof(char) * CHAR_BIT, 
+              "too many sds bits are used for entry metadata");
+
+/* Returns true if the entry's value is not embedded (stored by pointer). */
+static inline int entryHasValuePtr(const Entry *entry) {
+    return sdsGetAuxBit(entryGetField(entry), FIELD_SDS_AUX_BIT_ENTRY_HAS_VALUE_PTR);
+}
+
+/* Returns true if the entry's value is embedded in the entry. */
+static inline int entryHasEmbeddedValue(Entry *entry) {
+    return !entryHasValuePtr(entry);
+}
+
+/* Returns true if the entry has an expiration timestamp. */
+int entryHasExpiry(const Entry *entry) {
+    return sdsGetAuxBit(entryGetField(entry), FIELD_SDS_AUX_BIT_ENTRY_HAS_EXPIRY);
+}
+
+/* Returns the location of a pointer to a separately allocated value. Only for
+ * an entry without an embedded value. */
+static sds *entryGetValueRef(const Entry *entry) {
+    serverAssert(entryHasValuePtr(entry));
+    char *fieldHdr = sdsAllocPtr(entryGetField(entry));
+    char *valuePtr = fieldHdr - sizeof(sds);
+    return (sds *) valuePtr;
+}
+
+/* A pointer to the value pointer. If embedded or doesn't have a value, returns NULL. */
+sds *entryGetValuePtrRef(const Entry *entry) {
+    return entryHasValuePtr(entry) ? entryGetValueRef(entry) : NULL;
+}
+
+/* Returns the sds of the entry's value. */
+sds entryGetValue(const Entry *entry) {
+    if (entryHasValuePtr(entry)) {
+        return *entryGetValueRef(entry);
+    } else {
+        /* Skip field content, field null terminator and value sds8 hdr. */
+        size_t offset = sdslen(entryGetField(entry)) + 1 + sdsHdrSize(SDS_TYPE_8);
+        return (sds)((char *)entry + offset);
+    }
+}
+
+/* Returns the address of the entry allocation. */
+void *entryGetAllocPtr(const Entry *entry) {
+    char *buf = sdsAllocPtr(entryGetField(entry));
+    if (entryHasValuePtr(entry)) buf -= sizeof(sds);
+    if (entryHasExpiry(entry)) buf -= sizeof(ExpireMeta);
+    return buf;
+}
+
+/**************************************** Entry Expiry API *****************************************/
+
+/* Returns the entry expiration timestamp, or EB_EXPIRE_TIME_INVALID */
+uint64_t entryGetExpiry(const Entry *entry) {
+    if (!entryHasExpiry(entry))
+        return EB_EXPIRE_TIME_INVALID;
+
+    ExpireMeta *expireMeta = (ExpireMeta *)entryGetAllocPtr(entry);
+    if (expireMeta->trash)
+        return EB_EXPIRE_TIME_INVALID;
+
+    return ebGetMetaExpTime(expireMeta);
+}
+
+int entryIsExpired(const Entry *entry) {
+    if (server.allow_access_expired)
+        return 0;
+
+    /* Condition remains valid even if entryGetExpiry() returns EB_EXPIRE_TIME_INVALID,
+     * as the constant is equivalent to (EB_EXPIRE_TIME_MAX + 1). */
+    uint64_t expireTime = entryGetExpiry(entry);
+    return (mstime_t)expireTime < commandTimeSnapshot();
+}
+
+/**************************************** Entry Expiry API - End *****************************************/
+
+/* Calculate entry allocation size based on SDS alloc fields.
+ * This is used for size accounting. */
+size_t entryMemUsage(Entry *entry) {
+    size_t size = sdsAllocSize(entryGetField(entry));
+    size += sdsAllocSize(entryGetValue(entry));
+    if (entryHasValuePtr(entry)) size += sizeof(sds);
+    if (entryHasExpiry(entry)) size += sizeof(ExpireMeta);
+    return size;
+}
+
+void entryFree(Entry *entry, size_t *usable) {
+    if (usable) *usable = entryMemUsage(entry);
+
+    if (entryHasValuePtr(entry))
+        sdsfree(entryGetValue(entry));
+
+    zfree(entryGetAllocPtr(entry));
+}
+
+/* Determine the appropriate SDS type for the field based on length and expiry.
+ * SDS_TYPE_5 cannot be used if expiry is present (no aux bits available). */
+static inline int entryCalcFieldSdsType(size_t fieldLen, int hasExpiry) {
+    int sdsType = sdsReqType(fieldLen);
+    if (sdsType == SDS_TYPE_5 && hasExpiry) {
+        sdsType = SDS_TYPE_8;
+    }
+    return sdsType;
+}
+
+/* Calculate required size and layout for an entry */
+static inline void setEntryWriteInfo(EntryWriteInfo *info, sds field, sds value, uint32_t flags) {
+    info->flags = flags;
+
+    /* Calculate expiry allocation size */
+    info->expirySize = (flags & ENTRY_HAS_EXPIRY) ? sizeof(ExpireMeta) : 0;
+
+    /* Calculate field allocation size */
+    size_t fieldLen = sdslen(field);
+    info->embdFieldType = entryCalcFieldSdsType(fieldLen, info->expirySize > 0);
+    info->embdFieldSize = sdsReqSize(fieldLen, info->embdFieldType);
+    info->isEmbdNewVal = 0;
+
+    /* Calculate value allocation size (Always use SDS_TYPE_8 for embedded values) */
+    size_t valueLen = value ? sdslen(value) : 0;
+    info->embdValueSize = value ? sdsReqSize(valueLen, SDS_TYPE_8) : 0;
+
+    /* Start with field and expiry */
+    size_t allocSize = info->embdFieldSize + info->expirySize;
+    
+    if (unlikely(!value)) {
+        info->newEntryAllocSize = allocSize;
+        return;
+    }
+    
+    /* Decide whether to embed the value or use a pointer */
+    if (allocSize + info->embdValueSize <= EMBED_VALUE_MAX_ALLOC_SIZE) {
+        /* Embed field and value (SDS_TYPE_8). Unused space in value's SDS header.
+         *   [ExpireMeta | Field hdr "foo"\0 | Value hdr8 "bar"\0] 
+         */
+        info->isEmbdNewVal = 1;
+        allocSize += info->embdValueSize;
+    } else {
+        /* Embed field only (>= SDS_TYPE_8 to encode value ptr flag).
+         *   [ExpireMeta | Value Ptr | Field hdr8 "foo"\0] 
+         */
+        info->isEmbdNewVal = 0;
+        allocSize += sizeof(sds);
+
+        /* Upgrade field to SDS_TYPE_8 if needed for aux bits */
+        if (info->embdFieldType == SDS_TYPE_5) {
+            info->embdFieldType = SDS_TYPE_8;
+            info->embdFieldSize = sdsReqSize(fieldLen, info->embdFieldType);
+            allocSize = info->embdFieldSize + info->expirySize + sizeof(sds);
+        }
+    }
+    info->newEntryAllocSize = allocSize;
+}
+
+/* Serialize the content of the entry into the provided buffer */
+static Entry *entryWriteNew(EntryWriteInfo *info, sds field, sds value) {
+    char *fieldBuf, *buf = zmalloc(info->newEntryAllocSize);
+
+    /* Take into account expiry metadata if present */
+    if (info->expirySize) {
+        ExpireMeta *expMeta = (ExpireMeta *)buf;
+        expMeta->trash = 1;  /* Mark as trash until added to ebuckets */
+        fieldBuf = buf + info->expirySize;
+    } else {
+        fieldBuf = buf;
+    }
+
+    /* Write value (either as pointer or embedded) */
+    if (value) {
+        if (info->isEmbdNewVal) {
+            /* Embed the value after the field - always copy content */
+            sdsnewplacement(fieldBuf + info->embdFieldSize, info->embdValueSize,
+                          SDS_TYPE_8, value, sdslen(value));
+            /* Free value only if ownership was transferred */
+            if (info->flags & ENTRY_TAKE_VALUE)
+                sdsfree(value);
+            info->flags &= ~ENTRY_TAKE_VALUE;
+        } else {
+            /* Store value as a pointer. dup if ownership wasn't transferred */
+            *(sds *)fieldBuf = ((info->flags & ENTRY_TAKE_VALUE)) ? value : sdsdup(value);
+            info->flags &= ~ENTRY_TAKE_VALUE;
+            fieldBuf += sizeof(sds);
+        }
+    }
+
+    /* Write the field */
+    Entry *newEntry = (Entry *)sdsnewplacement(fieldBuf, info->embdFieldSize,
+                                               info->embdFieldType, field, sdslen(field));
+
+    /* Set aux bits to encode entry type */
+    sdsSetAuxBit(entryGetField(newEntry), FIELD_SDS_AUX_BIT_ENTRY_HAS_VALUE_PTR, !info->isEmbdNewVal);
+    sdsSetAuxBit(entryGetField(newEntry), FIELD_SDS_AUX_BIT_ENTRY_HAS_EXPIRY, info->expirySize > 0);
+
+    /* Verify the entry was built correctly */
+    debugServerAssert(entryHasValuePtr(newEntry) == !info->isEmbdNewVal);
+    debugServerAssert(entryHasExpiry(newEntry) == (info->expirySize > 0));
+
+    return newEntry;
+}
+
+Entry *entryCreate(sds field, sds value, uint32_t flags, size_t *usable) {
+    /* Calculate required size and layout */
+    EntryWriteInfo info;
+    setEntryWriteInfo(&info, field, value, flags);
+
+    /* Allocate and write the entry */
+    Entry *entry = entryWriteNew(&info, field, value);
+
+    /* Calculate usable size if requested */
+    if (usable)
+        *usable = entryMemUsage(entry);
+
+    return entry;
+}
+
+/* Helper: Check if we need to create a new entry allocation during update.
+ * Returns true if a new allocation is needed, false if we can update in-place. */
+static inline int needsNewAlloc(Entry *e,
+                                EntryWriteInfo *info,
+                                int isUpdateValue,
+                                int expiryAddRemove)
+{
+    /* if we need to add/remove expiration metadata */
+    if (expiryAddRemove)
+        return 1;
+    
+    /* If not updating value, no need to allocate new entry */
+    if (!isUpdateValue)
+        return 0;
+    
+    /* If value embedding <> pointer changed */
+    if (info->isEmbdNewVal != entryHasEmbeddedValue(e))
+        return 1;
+    
+    /* If old & new are both pointers, no need to allocate new entry */
+    if (!info->isEmbdNewVal)
+        return 0;
+    
+    /* Check if new embedded value fits in old allocation */
+    size_t oldAllocSize = sdsAllocSize(entryGetValue(e));
+    size_t newReqSize = info->embdValueSize;
+    return !((newReqSize <= oldAllocSize) && (newReqSize >= oldAllocSize * 3 / 4));
+}
+
+/* Helper: Update entry in-place */
+static Entry *entryWriteOver(Entry *e, EntryWriteInfo *info, sds value)
+{
+    /* No need to touch expiration metadata. It's done by caller */
+
+    if (entryHasValuePtr(e)) {
+        /* Replace pointer value */
+        sds *valueRef = entryGetValueRef(e);
+        sdsfree(*valueRef);
+        *valueRef = (info->flags & ENTRY_TAKE_VALUE) ? value : sdsdup(value);
+    } else {
+        /* Update embedded value in-place - always copy content */
+        sds oldValue = entryGetValue(e);
+        /* Use the old value's allocation size */
+        size_t valueSize = sdsAllocSize(oldValue);
+        sdsnewplacement(sdsAllocPtr(oldValue), valueSize, SDS_TYPE_8, value, sdslen(value));
+        /* Free value only if we took ownership */
+        if (info->flags & ENTRY_TAKE_VALUE)
+            sdsfree(value);
+    }
+    info->flags &= ~ENTRY_TAKE_VALUE;
+    return e;
+}
+
+/* Modify the entry's value and/or reserve space for expiration metadata */
+Entry *entryUpdate(Entry *entry, sds value, uint32_t flags, ssize_t *usableDiff) {
+    /* Check if we need to add/remove expiration metadata */
+    int oldHasExpiry = entryHasExpiry(entry) != 0;
+    int newHasExpiry = (flags & ENTRY_HAS_EXPIRY) != 0;    
+    int expiryAddRemove = (oldHasExpiry != newHasExpiry);
+    
+    int isUpdateVal = (value != NULL);
+
+    /* Early return if nothing changes */
+    if (!isUpdateVal && !expiryAddRemove) {
+        if (usableDiff)
+            *usableDiff = 0;
+        if (flags & ENTRY_TAKE_VALUE)
+            sdsfree(value);
+        return entry;
+    }
+
+    /* Calculate old usable size before any modifications */
+    size_t oldUsable = entryMemUsage(entry);
+
+    /* Get the value to use (either provided or existing) */
+    if (!value)
+        value = entryGetValue(entry);
+
+    /* Calculate required size and layout for the updated entry */
+    EntryWriteInfo info;
+    setEntryWriteInfo(&info, entryGetField(entry), value, flags);
+
+    /* Decide whether to update in-place or create a new entry */
+    Entry *newEntry;
+    size_t newUsable;
+
+    if (needsNewAlloc(entry, &info, isUpdateVal, expiryAddRemove)) {
+        Entry *oldEntry = entry;
+        /* If not updating value */
+        if (value == NULL) {
+            /* Should not flag ownership of value if not updating value */
+            debugServerAssert((info.flags & ENTRY_TAKE_VALUE) == 0);
+            
+            /* Try reuse the existing value */
+            value = entryGetValue(oldEntry);
+            
+            /* If value is a pointer, we can transfer it from old to new entry  */
+            if (entryHasValuePtr(oldEntry)) {
+                sds *oldValuePtr = entryGetValueRef(oldEntry);
+                *oldValuePtr = NULL;
+                info.flags |= ENTRY_TAKE_VALUE;
+            }
+        }
+        
+        newEntry = entryWriteNew(&info, entryGetField(oldEntry), value);
+        entryFree(oldEntry, NULL);
+
+        newUsable = entryMemUsage(newEntry);
+    } else {
+        /* Update in-place */
+        newEntry = entryWriteOver(entry, &info, value);
+        newUsable = entryMemUsage(newEntry);
+    }
+
+    /* Calculate the difference in memory usage */
+    if (usableDiff)
+        *usableDiff = (ssize_t)newUsable - (ssize_t)oldUsable;
+
+    /* Verify the entry was built correctly */
+    debugServerAssert(entryHasValuePtr(newEntry) == !info.isEmbdNewVal);
+    debugServerAssert(entryHasExpiry(newEntry) == (info.expirySize != 0));
+    debugServerAssert((info.flags & ENTRY_TAKE_VALUE) == 0); /* verify the flag is cleared */
+    serverAssert(newEntry);
+
+    return newEntry;
+}
+
+/* Defragments a hashtable entry (field-value pair) if needed, using the
+ * provided defrag functions. The defrag functions return NULL if the allocation
+ * was not moved, otherwise they return a pointer to the new memory location.
+ * A separate sds defrag function is needed because of the unique memory layout
+ * of sds strings.
+ * If the location of the entry changed we return the new location,
+ * otherwise we return NULL. */
+Entry *entryDefrag(Entry *e, void *(*defragfn)(void *), sds (*sdsdefragfn)(sds)) {
+    if (entryHasValuePtr(e)) {
+        sds *valueRef = entryGetValueRef(e);
+        sds newValue = sdsdefragfn(*valueRef);
+        if (newValue) *valueRef = newValue;
+    }
+    char *allocation = entryGetAllocPtr(e);
+    char *newAllocation = defragfn(allocation);
+    if (newAllocation != NULL) {
+        /* Return the same offset into the new allocation as the entry's offset
+         * in the old allocation. */
+        int entryPointerOffset = (char *)e - allocation;
+        return (Entry *)(newAllocation + entryPointerOffset);
+    }
+    return NULL;
+}
+
+/* Used for releasing memory to OS to avoid unnecessary CoW. Called when we've
+ * forked and memory won't be used again. See zmadvise_dontneed() */
+void entryDismissMemory(Entry *entry) {
+    /* Only dismiss values memory since the field size usually is small. */
+    if (entryHasValuePtr(entry)) {
+        dismissSds(*entryGetValueRef(entry));
+    }
+}