数据结构和内存分配 - redis-sds - 《开发笔记》

涉及文件
结构体定义
内存分布
概念
实际案例
include
include
include
include
- Redis 内部操作

内容全部是自我理解梳理而成，可能存在错误内容。

涉及文件

sds.h
sds.c

具体了解sds的可以看 http://github.com/antirez/sds

结构体定义

struct test {
    int age;
    int len;
    unsigned char flags;
    char name[];
} test;

内存分布

通过这个图，(如果不考虑结构体对齐)可知

dd->name 下移一位就是flags的地址， unsigned char flags = dd->name[-1] printf(“输出输出flags:%c\n”, dd->name[-1]);===> output: 【输出flags:B】

获取结构体，通过结构体获取其他属性 struct test sh = (void ) ((dd->name) - sizeof(struct test));
printf(“name:%s\n”, sh->name); ===> output: 【name址:chenshun001】

而实际上会出现内存对齐，导致flags也会占用4个字节，从而导致移动内存获取结构体指针失败。

概念

结构体内存对齐: 按照int 4个字节对齐，此时通过sizeof(struct test)进行计算，结构体test占用12个字节。
```
struct test {
  int age;
  int len;
  unsigned char flags;
  char name[];
} test;
```
结构体属性压缩: 只占用对应的内存长度，此时通过sizeof(struct test)进行计算，结构体test占用9个字节。
```
struct __attribute__ ((__packed__)) test {
  int age;
  int len;
  unsigned char flags;
  char name[];
} test;
```
实际案例
```c

include
include
include
include

struct attribute ((packed)) test { int age; int len; unsigned char flags; char name[]; } test;

int main() { struct test dd = malloc(sizeof(struct test)); if (dd == NULL) { return 1; } char f = “chenshun001”; dd->age = 456; dd->len = 456; dd->flags = 66;

printf("输出flags:%d\n", dd->name[-1]);
printf("结构体地址:%p\n", &dd);
printf("结构体指向的地址:%p\n", *&dd);
printf("结构体age地址:%p\n", &dd->age);
printf("结构体len地址:%p\n", &dd->len);
printf("结构体flags地址:%p\n", &dd->flags);
memcpy(dd->name, f, strlen(f));
printf("结构体name地址:%p\n", &dd->name);
//如果加上内存对齐，那么这里获取的内存地址是错误的
struct test *sh = (void *) ((dd->name) - sizeof(struct test));
printf("name址:%s\n", sh->name);
free(dd);
return 0;

} //output //输出flags:66 //结构体地址:0x7ffee97a48c0 //结构体指向的地址:0x7fe937c05a20 //结构体age地址:0x7fe937c05a20 //结构体len地址:0x7fe937c05a24 //结构体flags地址:0x7fe937c05a28 //结构体name地址:0x7fe937c05a29 //name址:chenshun001

<a name="cKGFu"></a>
### Redis SDS结构体
```c
// sdshdr 结构 低版本
struct sdshdr {
    int len;
    int free;
    char buf[];
};
//=============================================================================
//高版本
struct __attribute__ ((__packed__)) sdshdr5 {
    //低3个字节表示类型 高5个字节表示长度 2^5=32,必须小于32
    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[];
};

老版本的SDS内存图如上图所示
高版本的如下图所示

Redis 内部操作

创建一个SDS

/*sds本身就是一个字符指针，使用sds可以直接在上层使用c标准库的函数*/ 
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    //确定sds结构体类型SDS_TYPE_5/SDS_TYPE_8/SDS_TYPE_16/SDS_TYPE_32/SDS_TYPE_64
    char type = sdsReqType(initlen);
    //...移除一点点代码
    //获取结构体需要的内存 sizeof(struct 对应的结构体)
    int hdrlen = sdsHdrSize(type);
    //char指针
    unsigned char *fp; /* flags pointer. */
    //分配内存 = 结构体需要的内存+初始化的长度内存+1('\0'需要的内存)
    sh = s_malloc(hdrlen + initlen + 1);
    //分配内存失败
    if (sh == NULL) return NULL;
    //结构体指针的起始地址+hdrlen的地址==sds char柔性数组的开始地址
    s = (char *) sh + hdrlen;
    //char指针赋值，这样下边的*fp就是指向sds结构体的flags字段了
    fp = ((unsigned char *) s) - 1;
    switch (type) {
        case SDS_TYPE_5: {
            //设置fp指针的数据高5位 就是initlen，字符长度
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            //调用SDS_HDR_VAR获取到sh的结构体指针， 初始化结构体数据
            struct sdshdr8* sh = (void*)(s - sizeof(struct sdshdr8));
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            //调用SDS_HDR_VAR获取到sh的结构体指针， 初始化结构体数据
            struct sdshdr16* sh = (void*)(s - sizeof(struct sdshdr16));
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            //调用SDS_HDR_VAR获取到sh的结构体指针， 初始化结构体数据
            struct sdshdr32* sh = (void*)(s - sizeof(struct sdshdr32));
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            //调用SDS_HDR_VAR获取到sh的结构体指针， 初始化结构体数据
            struct sdshdr64* sh = (void*)(s - sizeof(struct sdshdr64));
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    //使用memcpy进行数据拷贝
    if (initlen && init)
        memcpy(s, init, initlen);
    //字符串结尾部分放置位'\0', 直接利用c标准库的函数
    s[initlen] = '\0';
    return s;
}

获取SDS信息

//sds内存的起始地址
#define SDS_HDR(T, s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
//返回sds剩余可用空间 = sds.alloc - sds.len;
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: {
            struct sdshdr8 *sh = SDS_HDR(8, s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            struct sdshdr16 *sh = SDS_HDR(16, s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            struct sdshdr32 *sh = SDS_HDR(32, s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            struct sdshdr64 *sh = SDS_HDR(64, s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

SDS扩容

sds sdsMakeRoomFor(sds s, size_t addlen) {
    //2个sds的结构体指针，这里的sds都特指为struct sds，而不是char* sds.
    void *sh, *newsh;
    //获取free大小free=avail (available)
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    //获取sds的结构体类型
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    //结构体字节数大小
    int hdrlen;
    /* 如果可用字节数> 待分配字节数 Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;
    //获取已使用字节数，如果是3.2版本的，直接可用通过 (struct sds* (void*)(s-sizeof(struct sds)))->len 获取
    //这里必须根据type 去判断一下header
    len = sdslen(s);
    //sds的开始内存地址向下移动 sdsHdrSize(oldtype) 位就是sds结构体的开始地址， 结构体指针*sh指向sds结构体内存地址，完美
    sh = (char *) s - sdsHdrSize(oldtype);
    //需要的内存数 = len(已使用) + addlen(待添加的字节数)
    reqlen = newlen = (len + addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    //如果小于1M，进行翻倍，后续拓展就不需要重新分配内存了
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        //大于1M，每次只加一M，和Netty的内存分配策略有异曲同工之妙
        newlen += SDS_MAX_PREALLOC;
    //获取新的sds type
    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;
    //type对应的结构体指针内存大小
    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    //内存没有发生变化
    if (oldtype == type) {
        //分配内存
        newsh = s_realloc(sh, hdrlen + newlen + 1);
        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(hdrlen + newlen + 1);
        //分配地址失败
        if (newsh == NULL) return NULL;
        //将sds的数据拷贝到新生成的sds，拷贝数据为真实数据+1('\0')
        memcpy((char *) newsh + hdrlen, s, len + 1);
        //释放内存
        s_free(sh);
        //指向新的地址
        s = (char *) newsh + hdrlen;
        //设置结构体sds的type
        s[-1] = type;
        //设置新的长度
        sdssetlen(s, len);
    }
    //设置总的内存大小
    sdssetalloc(s, newlen);
    return s;
}

redis-sds

涉及文件

结构体定义

内存分布

概念

实际案例

include

include

include

include

Redis 内部操作

创建一个SDS

获取SDS信息

SDS扩容