diff options
Diffstat (limited to 'examples/redis-unstable/src/entry.c')
| -rw-r--r-- | examples/redis-unstable/src/entry.c | 408 |
1 files changed, 0 insertions, 408 deletions
diff --git a/examples/redis-unstable/src/entry.c b/examples/redis-unstable/src/entry.c deleted file mode 100644 index 9176c98..0000000 --- a/examples/redis-unstable/src/entry.c +++ /dev/null @@ -1,408 +0,0 @@ -/* - * 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)); - } -} |