来自 金沙js77888 2020-01-31 20:23 的文章
当前位置: 金沙js77888 > 金沙js77888 > 正文

也就是说实际上sds类型就是char

最近打算阅读redis源码,但是担心读完就忘了,所以决定把阅读的笔记在简书里记录起来,希望能够坚持读下去。之所以选择3.2是因为公司把redis升级成了这个版本。

redis在处理字符串的时候没有直接使用以'\0'结尾的C语言字符串,而是封装了一下C语言字符串并命名为sds(simple dynamic string),在sds.h文件里我们可以看到如下类型定义:typedef char *sds;也就是说实际上sds类型就是char*类型,那sds和char*有什么区别呢?主要区别就是:sds一定有一个所属的结构,这个header结构在每次创建sds时被创建,用来存储sds以及sds的相关信息(下文sds的含义仅仅是redis的字符串,sdshdr才表示sds的header)。

那为什么redis不直接使用char*呢?总结起来理由如下:

  • 想用O的时间复杂度获取字符串长度。
  • sds实现了部分自己的字符串处理函数,能够存储二进制字符串 保证二进制安全,而所有C语言str前缀的字符串处理函数不保证二进制安全(遇到'\0'就停下,认为它是字符串的结尾,不能存二进制数据)。
  • 制定内存重分配方法,减少 因修改字符串而导致的 内存分配和释放 的次数。

这只是我看完代码后得出的结论,看不懂也没事,先列出来只是为了直观一点。当然还有其他使用sds的理由,想到再加上。接下来看代码:

sdshdr和sds是一一对应的关系,一个sds一定会有一个sdshdr用来记录sds的信息。在redis3.2分支出现之前sdshdr只有一个类型,定义如下:

struct sdshdr { unsigned int len;//表示sds当前的长度 unsigned int free;//已为sds分配的长度-sds当前的长度 char buf[];//sds实际存放的位置};

这些版本的redis每次创建一个sds 不管sds实际有多长,都会分配一个大小固定的sdshdr。根据成员len的类型可知,sds最多能存长度为2^(8*sizeof(unsigned int))的字符串。而3.2分支引入了五种sdshdr类型,每次在创建一个sds时根据sds的实际长度判断应该选择什么类型的sdshdr,不同类型的sdshdr占用的内存空间不同。这样细分一下可以省去很多不必要的内存开销,下面是3.2的sdshdr定义:

struct __attribute__ ((__packed__)) sdshdr5 { //实际上这个类型redis不会被使用。他的内部结构也与其他sdshdr不同,直接看sdshdr8就好。 unsigned char flags; //一共8位,低3位用来存放真实的flags,高5位用来存放len。 char buf[];//sds实际存放的位置};struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len;//表示当前sds的长度 uint8_t alloc; //表示已为sds分配的内存大小 unsigned char flags; //用一个字节表示当前sdshdr的类型,因为有sdshdr有五种类型,所以至少需要3位来表示000:sdshdr5,001:sdshdr8,010:sdshdr16,011:sdshdr32,100:sdshdr64。高5位用不到所以都为0。 char buf[];//sds实际存放的位置};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[];};

根据以上定义,我画了一个sdshdr8图来说明它们的内存布局:

图片 1

首先要说明之所以sizeof(struct sdshdr8)的大小是len alloc flags 是因为这个struct拥有一个柔性数组成员 buf,柔性数组成员是C99之后引入的一个新feature,这里可以通过sizeof整个struct给出buf变量的偏移量,从而确定buf的位置。Flexible array member, is a feature introduced in the [C99] standard of the C programming language,which is an array without a given dimension, and it must be the last member of such a struct. The 'sizeof' operator on such a struct is required to give the offset of the flexible array member. --维基百科

其次需要说明的是定义sdshdr的这部分代码用了__attribute__ ((__packed__)),这个语法不存在于任何C语言标准,是GCC的一个extension,用来告诉编译器使用最小的内存来存储sdshdr。

packed: ...,This attribute, attached to struct or union type definition, specifies that each member of the structure or union is placed to minimize the memory required.

引用里"minimize the memory required"其实就是让编译器尽量不使用内存对齐(alignment),以避免不必要的空间浪费,但其实这么做会有时间上的开销,假设CPU总是从存储器中读取8个字节,则变量地址必须为8的倍数,为了获取一个没对齐的8字节的uint8_t数据,CPU需要执行两次内存访问 从两个8字节的内存块中取出完整的8字节数据。关于内存对齐的更多信息,《深入理解计算机系统》第三章和《程序员的自我修养》 都有非常详细的描述。但这里我们只需要知道禁用(准确地说是尽量不使用)内存对齐是redis为了节省内存开支的一种手段。

接下来分析每个成员:

  • len表示sds当前sds的长度,不包括'\0'终止符,通过len直接获取字符串长度,不需要扫一遍string,这就是上文说的封装sds的理由之一
  • alloc表示当前为sds分配的大小(3.2以前的版本用的free是表示还剩free字节可用空间),不包括'\0'终止符;
  • flags表示当前sdshdr的类型,声明为char 一共有1个字节,仅用低三位就可以表示所有5种sdshdr类型:
#define SDS_TYPE_5 0 //00000000#define SDS_TYPE_8 1 //00000001#define SDS_TYPE_16 2 //00000010#define SDS_TYPE_32 3 //00000011#define SDS_TYPE_64 4 //00000100#define SDS_TYPE_MASK 7 //00000111,作为取flags低3位的掩码

要判断一个sds属于什么类型的sdshdr,只需 flags&SDS_TYPE_MASKSDS_TYPE_n比较即可(之所以需要SDS_TYPE_MASK是因为有sdshdr5这个特例,它的高5位不一定为0,参考上面sdshdr5定义里的代码注释)

sds.h里所有给出定义的内联函数都是通过sds作为参数,通过比较flags&SDS_TYPE_MASKSDS_TYPE_n来判断该sds属于哪种类型sdshdr,再按照指定的sdshdr类型取出sds的相关信息。例如sdslen函数:

#define SDS_HDR ((struct sdshdr##T *)-(sizeof(struct sdshdr##T)))) //返回一个类型为T包含s字符串的sdshdr的指针#define SDS_TYPE_5_LEN>>SDS_TYPE_BITS) //用sdshdr5的flags成员变量做参数返回sds的长度,这其实是一个没办法的hack#define SDS_TYPE_BITS 3 static inline size_t sdslen(const sds s) { unsigned char flags = s[-1]; //sdshdr的flags成员变量 switch(flags&SDS_TYPE_MASK) { case SDS_TYPE_5: return SDS_TYPE_5_LEN; case SDS_TYPE_8: return SDS_HDR->len;//取出sdshdr的len成员 case SDS_TYPE_16: return SDS_HDR->len; case SDS_TYPE_32: return SDS_HDR->len; case SDS_TYPE_64: return SDS_HDR->len; } return 0;}

第一行里的双井号##的意思是在一个宏定义里连接两个子串,连接之后这##号两边的子串就被编译器识别为一个。sdslen函数里第一行出现了s[-1],看起来感觉会是一个undefined behavior,其实不是,这是一种正常又正确的使用方式,它就等同于*。The definition of the subscript operator [] is that E1[E2] is identical to . --C99。又因为s是一个sds所以s指向的类型是char,-1就是-1*sizeof,这也刚好是一个flags(unsigned char)的地址,所以通过s[-1]我们可以获得sds所属的sdshdr的成员变量flags。类似sdslen这样利用sds找到sdshdr类型的还有如下几个函数,就不一一分析了:

static inline size_t sdsavail(const sds s)static inline void sdssetlen(sds s, size_t newlen)static inline void sdsinclen(sds s, size_t inc)static inline size_t sdsalloc(const sds s)static inline void sdssetalloc(sds s, size_t newlen)

前面说的是在已有结果的情况下,根据一个sds通过flags变量来判断它的sdshdr类型。那么最开始创建一个sds时应该选用什么类型的sdshdr来存放它的信息呢?这就得根据要存储的sds的长度决定了,redis在创建一个sds之前会调用sdsReqType(size_t string_size)来判断用哪个sdshdr。该函数传递一个sds的长度作为参数,返回应该选用的sdshdr类型。

static inline char sdsReqType(size_t string_size) { if (string_size < 1<<5) //小于2^5,flags成员的高5位即可表示 return SDS_TYPE_5; if (string_size < 1<<8) //小于2^8,8位整数(sdshdr8里的uint8_t)即可表示string_size return SDS_TYPE_8; if (string_size < 1<<16) //小于2^16,16位整数(sdshdr16里的uint16_t)即可表示string_size return SDS_TYPE_16; if (string_size < 1ll<<32) /小于2^32,32位整数(sdshrd32里的uint32_t)即可表示string_size,1ll是指1long long的意思,如果没有ll,1就是一个int,假设int为4字节32位,1<<32就会导致undefined behavior. return SDS_TYPE_32; return SDS_TYPE_64; //若sds的长度超过2^64,则所有类型都不法表示这个sds的len}

知道了创建一个sds时应选用什么类型的sdshdr后我们就可以看看创建sds的函数了:

//用init指针指向的内存的内容截取initlen长度来new一个sds,这个函数是二进制安全的sds sdsnewlen(const void *init, size_t initlen) { void *sh;//sdshdr的指针 sds s; //char * s; char type = sdsReqType;//根据需要的长度决定sdshdr的类型 /* Empty strings are usually created in order to append. Use type 8 * since type 5 is not good at this. */ if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;//如果initlen为空并且sdshdr的类型为sdshdr5,则将类型设置为sdshdr8 int hdrlen = sdsHdrSize;//每个sdshdr类型的大小都不一样,根据类型返回sdshdr的大小以计算需要分配的空间 unsigned char *fp; /* flags pointer. */ sh = s_malloc(hdrlen initlen 1);//在heap里申请一段连续的空间给sdshdr和属于它的sds, 1是因为要在尾部放置'\0' if  memset(sh, 0, hdrlen initlen 1);//如果init为空,则整个sdshdr都用0即字符'\0'初始化 if (sh == NULL) return NULL; s = sh hdrlen;//通过sdshdr指针找到sds的位置 fp = ((unsigned char*)s)-1;//找到flags的位置,等同于&s[-1] switch { case SDS_TYPE_5: { *fp = type | (initlen << SDS_TYPE_BITS);//initlen左移3位到高5位,给type腾出位置,和type做或运算 break; } case SDS_TYPE_8: { SDS_HDR_VAR;//#define SDS_HDR_VAR struct sdshdr##T *sh = -(sizeof(struct sdshdr##T))); 可以理解为在switch作用域下申明了一个新的局部变量sh,类型是struct sdshdr##T,跟外面的sh值一样,变量名一样,但不是一个东西。 sh->len = initlen; sh->alloc = initlen; *fp = type;//设置flags break; } case SDS_TYPE_16: { SDS_HDR_VAR; sh->len = initlen; sh->alloc = initlen; *fp = type; break; } case SDS_TYPE_32: { SDS_HDR_VAR; sh->len = initlen; sh->alloc = initlen; *fp = type; break; } case SDS_TYPE_64: { SDS_HDR_VAR; sh->len = initlen; sh->alloc = initlen; *fp = type; break; } } if (initlen && init) memcpy(s, init, initlen); //memcpy不会因为'\0'而停下,支持二进制数据的拷贝 s[initlen] = '\0'; //不管是不是二进制数据,尾部都会加上'\0' return s;}static inline int sdsHdrSize(char type) { switch(type&SDS_TYPE_MASK) { case SDS_TYPE_5: return sizeof(struct sdshdr5);//之前说的柔性数组成员不会计入struct的大小,所以这个hdrsize没有包括sds的长度 case SDS_TYPE_8: return sizeof(struct sdshdr8); case SDS_TYPE_16: return sizeof(struct sdshdr16); case SDS_TYPE_32: return sizeof(struct sdshdr32); case SDS_TYPE_64: return sizeof(struct sdshdr64); } return 0;}

这就是用于新建或拷贝sds的代码,流程写在注释里可能还是不够清晰,结合图来看应该会好一点(sdshdr5的图不一样,我就偷懒不画了,反正也不用它):

图片 2

流程如下:

  • 根据sds的长度判断需要选用sdshdr的类型
  • 根据sdshdr的类型用sdsHdrSize函数得到hdrlen(其实就是sizeof(struct sdshdr))
  • 为sdshdr分配一个hdrlen initlen 1大小的堆内存( 1是为了放置'\0',这个'\0'不计入alloc或len)
  • 按参数填充成员变量len、alloc和type
  • 用memcpy给sds赋值,并在尾部加上'\0'

如果用字符串"PHP is the best programming language" 调用sdsnewlen(),最终会产生如下布局:

图片 3

上文提到 redis不直接使用C语言字符串还有个原因是为了定制的自己的内存重分配的方法,减少因堆内存申请与释放产生的时间开销。如果redis使用的是普通的C语言字符串char*,那么每次拼接或者截断一个字符串之前都需要重新分配/释放内存,否则会造成内存溢出或泄露。但是每次进行分配/释放内存的操作又非常影响性能,所以redis做了两件事:

  • 提供一个函数sdsMakeRoomFor,当需要扩充一个sds字符串时调用它,它的内部实现了sds的内存分配算法,尽可能地降低内存分配次数。
  • 在截断一个sds字符串时不立刻释放掉之前为它申请的内存,而是通过alloc成员变量记录下这个值,供后续操作使用,然后提供一个函数sdsRemoveFreeSpace让我们根据需要释放掉多出的内存。

下面是sdsMakeRoomFor的源码:

//注意:这个函数是在扩充sds前调用,sds不会被扩充也不会改变lensds sdsMakeRoomFor(sds s, size_t addlen) { //addlen是扩充部分的长度 void *sh, *newsh; size_t avail = sdsavail; size_t len, newlen; char type, oldtype = s[-1] & SDS_TYPE_MASK; int hdrlen; /* Return ASAP if there is enough space left. */ if (avail >= addlen) return s;//如果足够存放扩充的部分,则直接返回不申请内存。 len = sdslen; sh = s-sdsHdrSize; newlen = (len addlen); if (newlen < SDS_MAX_PREALLOC) //扩充后的总长度小于1M(1024*1024),则直接多分配newlen个字节闲置。 newlen *= 2; else //扩充后的总长度大于1M(1024*1024),则多分配1M字节闲置 newlen  = SDS_MAX_PREALLOC; type = sdsReqType;//根据扩充后的总长度决定需要这个sds要用什么类型的sdshdr /* 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; if (oldtype==type) { //如果扩充后的sdshdr类型不变,则在原有的地方realloc就好。因为len和alloc的类型还是原来的。 //ps: s_realloc封装了realloc,realloc返回的指针未必是sh指向的地址,可能为了内存对齐移动了这块内存 newsh = s_realloc(sh, hdrlen newlen 1); if (newsh == NULL) return NULL; s = newsh hdrlen; } else { //如果扩充后的sdshdr类型变了,那就只能重新在别的地方分配内存,然后重新赋值,释放掉旧的内存。 /* Since the header size changes, need to move the string forward, * and can't use realloc */ newsh = s_malloc(hdrlen newlen 1); if (newsh == NULL) return NULL; memcpynewsh hdrlen, s, len 1); s_free; s = newsh hdrlen; s[-1] = type; sdssetlen; } sdssetalloc(s, newlen); return s;}

刚才已经创建了的sds"PHP is the best programming language",它的len是36,alloc也是36,现在给它扩充一下,把" in the world"加上,算上空格一共要加13个字节,这时会调用sdscatlen()函数完成整个拼接sds的操作,它内部需要先调用sdsMakeRoomFor走一遍内存重分配的算法,以下是sdsMakeRoomFor的流程

  • len addlen=49个字节,小于SDS_MAX_PREALLOC,所以最终会分配49*2=98字节的内存给这个需要扩充的sds字符串(实际是99,多分配一字节的'\0')。
  • 根据sdsReqType()函数,98字节小于2^8字节,所以扩充后的类型仍是sdshdr8,realloc一片内存。
  • 重置sds的alloc为98。

最终获得如下内存布局:

图片 4

接下来sdscatlen()函数用memcpy把" in the world"append到这个已经经历过内存分配的sds的尾部,并更新len:

图片 5附上sdscatlen的代码:

sds sdscatlen(sds s, const void *t, size_t len) { size_t curlen = sdslen; s = sdsMakeRoomFor; if (s == NULL) return NULL; memcpy(s curlen, t, len); sdssetlen(s, curlen len); s[curlen len] = '\0'; return s;}

我粗略地在源码里找了找,缩短sds字符串的有三个函数:sdsclear、sdstrim、sdsrange,他们都不会改变alloc的大小即不会释放任何内存,这就是sds字符串内存管理的一种方式:惰性释放。额外调用sdsRemoveFreeSpace释放内存,这样就节省了每次sds缩减长度而导致的内存释放开销。三个缩短sds的函数就不一一介绍了,有兴趣直接去代码里看就好,需要注意的这些函数里移动字符串用的memmove()是允许内存重叠的,这点跟memcpy()不一样。下面介绍一下sdsRemoveFreeSpace,先放源码:

//这个函数压缩内存,让alloc=len。如果type变小了,则另开一片内存复制,如果type不变,则reallocsds sdsRemoveFreeSpace { void *sh, *newsh; char type, oldtype = s[-1] & SDS_TYPE_MASK; int hdrlen; size_t len = sdslen; sh = s-sdsHdrSize; type = sdsReqType; hdrlen = sdsHdrSize; //这之后的代码就跟sdsMakeRoomFor后面的代码差不多了,释放掉多余内存并重置alloc。 if (oldtype==type) { newsh = s_realloc(sh, hdrlen len 1); if (newsh == NULL) return NULL; s = newsh hdrlen; } else { newsh = s_malloc(hdrlen len 1); if (newsh == NULL) return NULL; memcpynewsh hdrlen, s, len 1); s_free; s = newsh hdrlen; s[-1] = type; sdssetlen; } sdssetalloc; return s;}

继续拿之前用sdscatlen()扩充的sds执行一遍sdsRemoveFreeSpace(),会得到如下布局:

图片 6

以上就是sds相关代码分析,还有很多针对sds的基本操作函数在这里就不一一列举了。

本文由金沙js77888发布于金沙js77888,转载请注明出处:也就是说实际上sds类型就是char

关键词: 金沙澳门娱乐 源码 字符串 动态