From 5d8dfe892a2ea89f706ee140c3bdcfd89fe03fda Mon Sep 17 00:00:00 2001 From: Mitja Felicijan Date: Wed, 21 Jan 2026 22:40:55 +0100 Subject: Add Redis source code for testing --- examples/redis-unstable/src/entry.c | 408 ++++++++++++++++++++++++++++++++++++ 1 file changed, 408 insertions(+) create mode 100644 examples/redis-unstable/src/entry.c (limited to 'examples/redis-unstable/src/entry.c') 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)); + } +} -- cgit v1.2.3