/* * Copyright Redis Ltd. 2024 - present * * Licensed under your choice of the Redis Source Available License 2.0 (RSALv2) * or the Server Side Public License v1 (SSPLv1). * * * WHAT IS MSTR (M-STRING)? * ------------------------ * mstr stands for immutable string with optional metadata attached. * * sds string is widely used across the system and serves as a general purpose * container to hold data. The need to optimize memory and aggregate strings * along with metadata and store it into Redis data-structures as single bulk keep * reoccur. One thought might be, why not to extend sds to support metadata. The * answer is that sds is mutable string in its nature, with wide API (split, join, * etc.). Pushing metadata logic into sds will make it very fragile, and complex * to maintain. * * Another idea involved using a simple struct with flags and a dynamic buf[] at the * end. While this could be viable, it introduces considerable complexity and would * need maintenance across different contexts. * * As an alternative, we introduce a new implementation of immutable strings, * with limited API, and with the option to attach metadata. The representation * of the string, without any metadata, in its basic form, resembles SDS but * without the API to manipulate the string. Only to attach metadata to it. The * following diagram shows the memory layout of mstring (mstrhdr8) when no * metadata is attached: * * +----------------------------------------------+ * | mstrhdr8 | c-string | | * +--------------------------------+-------------+ * |8b |2b |1b |5b |?bytes |8b| * | Len | Type |m-bit=0 | Unused | String |\0| * +----------------------------------------------+ * ^ * | * mstrNew() returns pointer to here --+ * * If metadata-flag is set, depicted in diagram above as m-bit in the diagram, * then the header will be preceded with additional 16 bits of metadata flags such * that if i'th bit is set, then the i'th metadata structure is attached to the * mstring. The metadata layout and their sizes are defined by mstrKind structure * (More below). * * The following diagram shows the memory layout of mstr (mstrhdr8) when 3 bits in mFlags * are set to indicate that 3 fields of metadata are attached to the mstring at the * beginning. * * +-------------------------------------------------------------------------------+ * | METADATA FIELDS | mflags | mstrhdr8 | c-string | | * +-----------------------+--------+--------------------------------+-------------+ * |?bytes |?bytes |?bytes |16b |8b |2b |1b |5b |?bytes |8b| * | Meta3 | Meta2 | Meta0 | 0x1101 | Len | Type |m-bit=1 | Unused | String |\0| * +-------------------------------------------------------------------------------+ * ^ * | * mstrNewWithMeta() returns pointer to here --+ * * mstr allows to define different kinds (groups) of mstrings, each with its * own unique metadata layout. For example, in case of hash-fields, all instances of * it can optionally have TTL metadata attached to it. This is achieved by first * prototyping a single mstrKind structure that defines the metadata layout and sizes * of this specific kind. Now each hash-field instance has still the freedom to * attach or not attach the metadata to it, and metadata flags (mFlags) of the * instance will reflect this decision. * * In the future, the keys of Redis keyspace can be another kind of mstring that * has TTL, LRU or even dictEntry metadata embedded into. Unlike vptr in c++, this * struct won't be attached to mstring but will be passed as yet another argument * to API, to save memory. In addition, each instance of a given mstrkind can hold * any subset of metadata and the 8 bits of metadata-flags will reflect it. * * The following example shows how to define mstrKind for possible future keyspace * that aggregates several keyspace related metadata into one compact, singly * allocated, mstring. * * typedef enum HkeyMetaFlags { * HKEY_META_VAL_REF_COUNT = 0, // refcount * HKEY_META_VAL_REF = 1, // Val referenced * HKEY_META_EXPIRE = 2, // TTL and more * HKEY_META_TYPE_ENC_LRU = 3, // TYPE + LRU + ENC * HKEY_META_DICT_ENT_NEXT = 4, // Next dict entry * // Following two must be together and in this order * HKEY_META_VAL_EMBED8 = 5, // Val embedded, max 7 bytes * HKEY_META_VAL_EMBED16 = 6, // Val embedded, max 15 bytes (23 with EMBED8) * } HkeyMetaFlags; * * mstrKind hkeyKind = { * .name = "hkey", * .metaSize[HKEY_META_VAL_REF_COUNT] = 4, * .metaSize[HKEY_META_VAL_REF] = 8, * .metaSize[HKEY_META_EXPIRE] = sizeof(ExpireMeta), * .metaSize[HKEY_META_TYPE_ENC_LRU] = 8, * .metaSize[HKEY_META_DICT_ENT_NEXT] = 8, * .metaSize[HKEY_META_VAL_EMBED8] = 8, * .metaSize[HKEY_META_VAL_EMBED16] = 16, * }; * * MSTR-ALIGNMENT * -------------- * There are two types of alignments to take into consideration: * 1. Alignment of the metadata. * 2. Alignment of returned mstr pointer * * 1) As the metadatas layout are reversed to their enumeration, it is recommended * to put metadata with "better" alignment first in memory layout (enumerated * last) and the worst, or those that simply don't require any alignment will be * last in memory layout (enumerated first). This is similar the to the applied * consideration when defining new struct in C. Note also that each metadata * might either be attached to mstr or not which complicates the design phase * of a new mstrKind a little. * * In the example above, HKEY_META_VAL_REF_COUNT, with worst alignment of 4 * bytes, is enumerated first, and therefore, will be last in memory layout. * * 2) Few optimizations in Redis rely on the fact that sds address is always an odd * pointer. We can achieve the same with a little effort. It was already taken * care that all headers of type mstrhdrX has odd size. With that in mind, if * a new kind of mstr is required to be limited to odd addresses, then we must * make sure that sizes of all related metadatas that are defined in mstrKind * are even in size. */ #ifndef __MSTR_H #define __MSTR_H #include #include #include /* Selective copy of ifndef from server.h instead of including it */ #ifndef static_assert #define static_assert(expr, lit) extern char __static_assert_failure[(expr) ? 1:-1] #endif #define MSTR_TYPE_5 0 #define MSTR_TYPE_8 1 #define MSTR_TYPE_16 2 #define MSTR_TYPE_64 3 #define MSTR_TYPE_MASK 3 #define MSTR_TYPE_BITS 2 #define MSTR_META_MASK 4 #define MSTR_HDR(T,s) ((struct mstrhdr##T *)((s)-(sizeof(struct mstrhdr##T)))) #define MSTR_HDR_VAR(T,s) struct mstrhdr##T *sh = (void*)((s)-(sizeof(struct mstrhdr##T))); #define MSTR_META_BITS 1 /* is metadata attached? */ #define MSTR_TYPE_5_LEN(f) ((f) >> (MSTR_TYPE_BITS + MSTR_META_BITS)) #define CREATE_MSTR_INFO(len, ismeta, type) ( (((len<