Redis源码阅读笔记（2）-SDS
在redis中，使用了SDS（Simple Synamic String）来存储字符串。
数据结构定义
不同于c语言中的char*使用了连续内存空间和\0作为结尾来表示字符串的方式，redis中的sds结构还添加了额外的元信息。
len表示字符串现在的长度，alloc表示已分配的长度，flags表示sds的类型，buf[]表示存储的数据。
对应到代码中，如下：
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
我们可以看到，为了节省内存，redis使用了多种类型的sds结构。
有些小朋友可能会对__attribute__ ((__packed__))不太熟悉，其实这个是GCC编译器中的类型属性（Function Attribute），用来取消对齐结构体字段的指令，减小内存占用。
在sds.h中，我们可以看到SDS类型实际还是char*：
typedef char *sds;
创建SDS
创建SDS时，可以使用函数sds sdsnewlen(const void *init, size_t initlen)来创建，其对应的实现如下：
/* 创建一个新的sds字符串，内容由'init'指针和'initlen'指定。
* 如果'init'为NULL，则字符串用零字节初始化。
* 如果使用SDS_NOINIT，则缓冲区保持未初始化状态；
*
* 字符串总是以null结尾（所有sds字符串都是如此），所以
* 即使你用以下方式创建一个sds字符串：
*
* mystring = sdsnewlen("abc",3);
*
* 你也可以用printf()打印字符串，因为字符串的末尾隐含了一个\0。
* 但是，字符串是二进制安全的，可以在中间包含\0字符，
* 因为长度存储在sds头部。 */
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
void *sh; // 用于保存分配的内存的指针
sds s; // 用于保存新创建的sds的指针
char type = sdsReqType(initlen); // 根据initlen的大小，选择合适的sds类型
/* 空字符串通常是为了追加而创建的。使用类型8
* 因为类型5在这方面不好。 */
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type); // 计算sds头部的大小
unsigned char *fp; /* flags指针。 */
size_t usable; // 用于保存可用内存大小的变量
assert(initlen + hdrlen + 1 > initlen); /* 捕获size_t溢出 */
// 根据trymalloc的值，选择合适的内存分配函数，并分配内存
sh = trymalloc?
s_trymalloc_usable(hdrlen+initlen+1, &usable) :
s_malloc_usable(hdrlen+initlen+1, &usable);
if (sh == NULL) return NULL; // 如果内存分配失败，返回NULL
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1); // 如果init为NULL，将分配的内存初始化为0
s = (char*)sh+hdrlen; // 计算sds字符串的起始地址
fp = ((unsigned char*)s)-1; // 计算flags的地址
usable = usable-hdrlen-1; // 计算可用内存大小
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type); // 如果可用内存大小超过了当前sds类型的最大值，将其设置为最大值
// 根据sds类型，设置sds头部的信息
switch(type) {
case SDS_TYPE_5: {
*fp = type | (initlen << SDS_TYPE_BITS); // 设置flags字段
break;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s); // 定义一个类型为sdshdr8的指针sh，并将其指向sds的头部
sh->len = initlen; // 设置已使用的长度
sh->alloc = usable; // 设置分配的内存大小
*fp = type; // 设置flags字段
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s); // 定义一个类型为sdshdr16的指针sh，并将其指向sds的头部
sh->len = initlen; // 设置已使用的长度
sh->alloc = usable; // 设置分配的内存大小
*fp = type; // 设置flags字段
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s); // 定义一个类型为sdshdr32的指针sh，并将其指向sds的头部
sh->len = initlen; // 设置已使用的长度
sh->alloc = usable; // 设置分配的内存大小
*fp = type; // 设置flags字段
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s); // 定义一个类型为sdshdr64的指针sh，并将其指向sds的头部
sh->len = initlen; // 设置已使用的长度
sh->alloc = usable; // 设置分配的内存大小
*fp = type; // 设置flags字段
break;
}
}
if (initlen && init)
memcpy(s, init, initlen); // 如果提供了初始化字符串，将其复制到新分配的内存中
s[initlen] = '\0'; // 在字符串的末尾添加一个空字符作为终止符
return s; // 返回新创建的sds
}
这段代码是创建一个新的SDS字符串的函数。首先，它会根据需要存储的字符串长度选择合适的SDS类型（5、8、16、32、64）。然后，根据选择的类型，分配相应的内存，并设置SDS的头部信息，包括已使用的长度和分配的内存大小。最后，如果提供了初始化字符串，就将其复制到新分配的内存中，并在末尾添加一个空字符作为终止符。
根据参数trymalloc是否为1，调用s_trymalloc_usable或者s_malloc_usable。这两个函数的区别如下：
/* 尝试分配内存，如果失败则返回NULL。
* 如果'*usable'非NULL，则设置为可用大小。 */
void *ztrymalloc_usable(size_t size, size_t *usable) {
ASSERT_NO_SIZE_OVERFLOW(size); // 断言，防止size溢出
void *ptr = malloc(MALLOC_MIN_SIZE(size)+PREFIX_SIZE); // 尝试分配内存
if (!ptr) return NULL; // 如果分配失败，返回NULL
#ifdef HAVE_MALLOC_SIZE
size = zmalloc_size(ptr); // 如果定义了HAVE_MALLOC_SIZE宏，使用系统的malloc_size函数获取实际分配的内存大小
update_zmalloc_stat_alloc(size); // 更新内存统计信息
if (usable) *usable = size; // 如果usable非NULL，设置其值为实际可用的内存大小
return ptr; // 返回分配的内存指针
#else
*((size_t*)ptr) = size; // 如果没有定义HAVE_MALLOC_SIZE宏，将请求的大小存储在分配的内存块的开始处
update_zmalloc_stat_alloc(size+PREFIX_SIZE); // 更新内存统计信息
if (usable) *usable = size; // 如果usable非NULL，设置其值为实际可用的内存大小
return (char*)ptr+PREFIX_SIZE; // 返回分配的内存指针，偏移PREFIX_SIZE以跳过存储的大小
#endif
}
/* 分配内存或者触发内存不足处理程序。
* 如果'*usable'非NULL，则设置为可用大小。 */
void *zmalloc_usable(size_t size, size_t *usable) {
void *ptr = ztrymalloc_usable(size, usable); // 尝试分配内存
if (!ptr) zmalloc_oom_handler(size); // 如果分配失败，调用内存不足处理程序
return ptr; // 返回分配的内存指针
}
zmalloc_usable函数在调用前者返回空指针后，会直接调abort()终止程序执行。
注意SDS_HDR_VAR这个宏：#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));，用来获取SDS头结构的指针。
这个函数返回的SDS结构可以兼容所有c语言中的str系列函数。
SDS支持的方法
sds sdsnewlen(const void *init, size_t initlen); // 根据给定的初始化字符串和长度，创建一个新的sds
sds sdstrynewlen(const void *init, size_t initlen); // 尝试根据给定的初始化字符串和长度，创建一个新的sds
sds sdsnew(const char *init); // 根据给定的初始化字符串，创建一个新的sds
sds sdsempty(void); // 创建一个空的sds
sds sdsdup(const sds s); // 复制给定的sds
void sdsfree(sds s); // 释放给定的sds
sds sdsgrowzero(sds s, size_t len); // 将sds扩展到给定的长度，新分配的空间用0填充
sds sdscatlen(sds s, const void *t, size_t len); // 将长度为len的字符串t追加到sds s的末尾
sds sdscat(sds s, const char *t); // 将字符串t追加到sds s的末尾
sds sdscatsds(sds s, const sds t); // 将sds t追加到sds s的末尾
sds sdscpylen(sds s, const char *t, size_t len); // 将长度为len的字符串t复制到sds s
sds sdscpy(sds s, const char *t); // 将字符串t复制到sds s
sds sdscatvprintf(sds s, const char *fmt, va_list ap); // 将格式化字符串追加到sds s的末尾
#ifdef __GNUC__
sds sdscatprintf(sds s, const char *fmt, ...)
__attribute__((format(printf, 2, 3))); // 将格式化字符串追加到sds s的末尾
#else
sds sdscatprintf(sds s, const char *fmt, ...); // 将格式化字符串追加到sds s的末尾
#endif
sds sdscatfmt(sds s, char const *fmt, ...); // 将格式化字符串追加到sds s的末尾
sds sdstrim(sds s, const char *cset); // 从sds s中移除所有在cset中的字符
void sdssubstr(sds s, size_t start, size_t len); // 获取sds s的子字符串
void sdsrange(sds s, ssize_t start, ssize_t end); // 保留sds s的一部分，从start到end
void sdsupdatelen(sds s); // 更新sds s的长度
void sdsclear(sds s); // 清空sds s，但不释放内存
int sdscmp(const sds s1, const sds s2); // 比较两个sds
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count); // 根据分隔符sep，将字符串s分割为多个sds
void sdsfreesplitres(sds *tokens, int count); // 释放由sdssplitlen函数分割得到的sds数组
void sdstolower(sds s); // 将sds s转换为小写
void sdstoupper(sds s); // 将sds s转换为大写
sds sdsfromlonglong(long long value); // 将长整数转换为sds
sds sdscatrepr(sds s, const char *p, size_t len); // 将长度为len的字符串p以可打印的格式追加到sds s的末尾
sds *sdssplitargs(const char *line, int *argc); // 将命令行参数字符串分割为多个sds
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen); // 将sds s中的字符从from映射到to
sds sdsjoin(char **argv, int argc, char *sep); // 将多个字符串用sep连接为一个sds
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen); // 将多个sds用sep连接为一个sds
typedef sds (*sdstemplate_callback_t)(const sds variable, void *arg); // sdstemplate的回调函数类型
sds sdstemplate(const char *template, sdstemplate_callback_t cb_func, void *cb_arg); // 根据模板和回调函数，生成一个新的sds
sds sdsMakeRoomFor(sds s, size_t addlen); // 为sds s分配额外的空间
void sdsIncrLen(sds s, ssize_t incr); // 增加sds s的长度
sds sdsRemoveFreeSpace(sds s); // 移除sds s的未使用空间
size_t sdsAllocSize(sds s); // 获取sds s的分配空间大小
void *sdsAllocPtr(sds s); // 获取sds s的分配空间的指针
void *sds_malloc(size_t size); // 分配内存
void *sds_realloc(void *ptr, size_t size); // 重新分配内存
void sds_free(void *ptr); // 释放内存
这些函数都是sds库的一部分，提供了创建、复制、释放、修改、比较和格式化sds的功能，以及一些低级别的内存管理功能。
SDS支持了常见的字符串操作相关方法，挑一个比较复杂的字符串追加操作sdscatlen来看：
/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
* end of the specified sds string 's'.
*
* After the call, the passed sds string is no longer valid and all the
* references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {
size_t curlen = sdslen(s);
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
memcpy(s+curlen, t, len);
sdssetlen(s, curlen+len);
s[curlen+len] = '\0';
return s;
}
我们先看下sdslen()的实现：
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
static inline size_t sdslen(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return SDS_TYPE_5_LEN(flags);
case SDS_TYPE_8:
return SDS_HDR(8,s)->len;
case SDS_TYPE_16:
return SDS_HDR(16,s)->len;
case SDS_TYPE_32:
return SDS_HDR(32,s)->len;
case SDS_TYPE_64:
return SDS_HDR(64,s)->len;
}
return 0;
}
获取SDS的flag类型，根据类型判断偏移拿到len。
在我们拿到len之后，调用了sdsMakeRoomFor来进行扩容：
/* Enlarge the free space at the end of the sds string so that the caller
* is sure that after calling this function can overwrite up to addlen
* bytes after the end of the string, plus one more byte for nul term.
*
* Note: this does not change the *length* of the sds string as returned
* by sdslen(), but only the free buffer space we have. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s);
size_t len, newlen, reqlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
size_t usable;
/* Return ASAP if there is enough space left. */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
reqlen = newlen = (len+addlen);
assert(newlen > len); /* Catch size_t overflow */
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
type = sdsReqType(newlen);
/* Don't use type 5: the user is appending to the string and type 5 is
* not able to remember empty space, so sdsMakeRoomFor() must be called
* at every appending operation. */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */
if (oldtype==type) {
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward,
* and can't use realloc */
newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
sdssetlen(s, len);
}
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
sdssetalloc(s, usable);
return s;
}
这个函数首先调用sdsavail获取了sds的可用空间：
static inline size_t sdsavail(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5: {
return 0;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
return sh->alloc - sh->len;
}
}
return 0;
}
如果可用空间足够直接返回。
对新创建的长度和最大预分配长度比较，若小于则2倍，否则直接加上最大预分配长度。
通过sdsReqType获取新sds的类型：
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5)
return SDS_TYPE_5;
if (string_size < 1<<8)
return SDS_TYPE_8;
if (string_size < 1<<16)
return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32)
return SDS_TYPE_32;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}
如果新老sds类型一直，则会尝试realloc，最终会调用到这里：
/* Try reallocating memory, and return NULL if failed.
* '*usable' is set to the usable size if non NULL. */
void *ztryrealloc_usable(void *ptr, size_t size, size_t *usable) {
ASSERT_NO_SIZE_OVERFLOW(size);
#ifndef HAVE_MALLOC_SIZE
void *realptr;
#endif
size_t oldsize;
void *newptr;
/* not allocating anything, just redirect to free. */
if (size == 0 && ptr != NULL) {
zfree(ptr);
if (usable) *usable = 0;
return NULL;
}
/* Not freeing anything, just redirect to malloc. */
if (ptr == NULL)
return ztrymalloc_usable(size, usable);
#ifdef HAVE_MALLOC_SIZE
oldsize = zmalloc_size(ptr);
newptr = realloc(ptr,size);
if (newptr == NULL) {
if (usable) *usable = 0;
return NULL;
}
update_zmalloc_stat_free(oldsize);
size = zmalloc_size(newptr);
update_zmalloc_stat_alloc(size);
if (usable) *usable = size;
return newptr;
#else
realptr = (char*)ptr-PREFIX_SIZE;
oldsize = *((size_t*)realptr);
newptr = realloc(realptr,size+PREFIX_SIZE);
if (newptr == NULL) {
if (usable) *usable = 0;
return NULL;
}
*((size_t*)newptr) = size;
update_zmalloc_stat_free(oldsize);
update_zmalloc_stat_alloc(size);
if (usable) *usable = size;
return (char*)newptr+PREFIX_SIZE;
#endif
}
类型不一致，直接分配新内存，将原来的内容memcpy过去，设置好已使用的len，alloc长度。
使用范围
在redis的源代码中，client,server,sentinel等模块都有使用sds的地方。
参考资料
- https://github.com/redis/redis
- https://docs.oracle.com/cd/E19205-01/820-7599/giqdb/index.html#:~:text=5%20Program%20Organization-,4.11%20The%20__packed__%20Attribute,integral%20type%20should%20be%20used.
- https://stackoverflow.com/questions/11770451/what-is-the-meaning-of-attribute-packed-aligned4
- https://gcc.gnu.org/onlinedocs/gcc-4.0.2/gcc/Type-Attributes.html
- http://blog.sina.com.cn/s/blog_7e719f0501012tkt.html
