Add Redis source code for testing

1 files changed, 227 insertions, 0 deletions

diff --git a/examples/redis-unstable/src/mstr.h b/examples/redis-unstable/src/mstr.h
new file mode 100644
index 0000000..f711e98
--- /dev/null
+++ b/examples/redis-unstable/src/mstr.h
@@ -0,0 +1,227 @@
+/*
+ * 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).
+ *
+ *
+ * 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 <sys/types.h>
+#include <stdarg.h>
+#include <stdint.h>
+
+/* 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<<MSTR_META_BITS) + ismeta) << (MSTR_TYPE_BITS)) | type )
+
+/* mimic plain c-string */
+typedef char *mstr;
+
+/* Flags that can be set on mstring to indicate for attached metadata. It is
+ * */
+typedef uint16_t mstrFlags;
+
+struct __attribute__ ((__packed__)) mstrhdr5 {
+    unsigned char info; /* 2 lsb of type, 1 metadata, and 5 msb of string length */
+    char buf[];
+};
+struct __attribute__ ((__packed__)) mstrhdr8 {
+    uint8_t unused;  /* To achieve odd size header (See comment above) */
+    uint8_t len;
+    unsigned char info; /* 2 lsb of type, 6 unused bits */
+    char buf[];
+};
+struct __attribute__ ((__packed__)) mstrhdr16 {
+    uint16_t len;
+    unsigned char info; /* 2 lsb of type, 6 unused bits */
+    char buf[];
+};
+struct __attribute__ ((__packed__)) mstrhdr64 {
+    uint64_t len;
+    unsigned char info; /* 2 lsb of type, 6 unused bits */
+    char buf[];
+};
+
+#define NUM_MSTR_FLAGS (sizeof(mstrFlags)*8)
+
+/* mstrKind is used to define a kind (a group) of mstring with its own metadata layout */
+ typedef struct mstrKind {
+    const char *name;
+    int metaSize[NUM_MSTR_FLAGS];
+} mstrKind;
+
+mstr mstrNew(const char *initStr, size_t lenStr, int trymalloc, size_t *usable);
+
+mstr mstrNewWithMeta(struct mstrKind *kind, const char *initStr, size_t lenStr, mstrFlags flags, int trymalloc, size_t *usable);
+
+mstr mstrNewCopy(struct mstrKind *kind, mstr src, mstrFlags newFlags, size_t *usable);
+
+void *mstrGetAllocPtr(struct mstrKind *kind, mstr str);
+
+void mstrFree(struct mstrKind *kind, mstr s, size_t *usable);
+
+mstrFlags *mstrFlagsRef(mstr s);
+
+void *mstrMetaRef(mstr s, struct mstrKind *kind, int flagIdx);
+
+size_t mstrlen(const mstr s);
+
+/* return non-zero if metadata is attached to mstring */
+static inline int mstrIsMetaAttached(mstr s) { return s[-1] & MSTR_META_MASK; }
+
+/* return whether if a specific flag-index is set */
+static inline int mstrGetFlag(mstr s, int flagIdx) { return *mstrFlagsRef(s) & (1 << flagIdx); }
+
+/* DEBUG */
+void mstrPrint(mstr s, struct mstrKind *kind, int verbose);
+
+/* See comment above about MSTR-ALIGNMENT(2) */
+static_assert(sizeof(struct mstrhdr5 ) % 2 == 1, "must be odd");
+static_assert(sizeof(struct mstrhdr8 ) % 2 == 1, "must be odd");
+static_assert(sizeof(struct mstrhdr16 ) % 2 == 1, "must be odd");
+static_assert(sizeof(struct mstrhdr64 ) % 2 == 1, "must be odd");
+static_assert(sizeof(mstrFlags ) % 2 == 0, "must be even to keep mstr pointer odd");
+
+#ifdef REDIS_TEST
+int mstrTest(int argc, char *argv[], int flags);
+#endif
+
+#endif