redis4.0_sds源码剖析

1.sds介绍

  1. sds:Simple Dynamic String即简单动态字符串,为redis的默认字符串表示。

2.sds.h源码分析

  1. sds结构体的内存布局

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /* 0长度数组的妙用
    * ----------------
    * | len |
    * |——————————————|
    * | alloc |
    * |——————————————|
    * | flags |
    * |——————————————|<----buf
    * | buf[0~n] |
    * | . |
    * | . |
    | . |
    * |——————————————|
    */
  2. sds结构体的定义

  3. sds结构体定义在src/sds.h,其中根据buf[]中字符串的长度来选择不同的sds结构体
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    typedef char *sds;
    /* Note: sdshdr5 is never used, we just access the flags byte directly.
    * However is here to document the layout of type 5 SDS strings. */
    //sdshdr5与其他sds结构体的区别是:没有alloc字段,即无法获得free=alloc-len
    //sdshdr5中flags字段的低3bits表示sds类型,高5bits位buf的length字段
    struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];//等价于char buf[0];
    };
    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 */
    //0长度数组 char buf[]等价于char buf[0]
    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 */
    //sdsnhdr的类型
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
    };
  1. sds.h中相关函数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    //返回sds的已使用空间字节数即:sds结构体中的len字段
    //函数的参数s为sds结构体中buf[]的首地址
    static inline size_t sdslen(const sds s) {
    //s[-1]即:*(s-1)
    unsigned char flags = s[-1];
    //判断结构体的类型
    switch(flags&SDS_TYPE_MASK) {
    case SDS_TYPE_5:
    return SDS_TYPE_5_LEN(flags);//高5bits表示buf len
    case SDS_TYPE_8:
    return __SDS_HR(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;
    }
    //获取可用的buf空间大小,即:free = alloc-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: {
    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;
    }
    //设置sds结构体len
    static inline void sdssetlen(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
    case SDS_TYPE_5:
    {
    unsigned char *fp = ((unsigned char*)s)-1;
    *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
    }
    break;
    case SDS_TYPE_8:
    SDS_HDR(8,s)->len = newlen;
    break;
    case SDS_TYPE_16:
    SDS_HDR(16,s)->len = newlen;
    break;
    case SDS_TYPE_32:
    SDS_HDR(32,s)->len = newlen;
    break;
    case SDS_TYPE_64:
    SDS_HDR(64,s)->len = newlen;
    break;
    }
    }
    static inline void sdsinclen(sds s, size_t inc) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
    case SDS_TYPE_5:
    {
    unsigned char *fp = ((unsigned char*)s)-1;
    unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
    *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
    }
    break;
    case SDS_TYPE_8:
    SDS_HDR(8,s)->len += inc;
    break;
    case SDS_TYPE_16:
    SDS_HDR(16,s)->len += inc;
    break;
    case SDS_TYPE_32:
    SDS_HDR(32,s)->len += inc;
    break;
    case SDS_TYPE_64:
    SDS_HDR(64,s)->len += inc;
    break;
    }
    }
    //alloc不包括\0
    /* sdsalloc() = sdsavail() + sdslen() */
    static inline size_t sdsalloc(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)->alloc;
    case SDS_TYPE_16:
    return SDS_HDR(16,s)->alloc;
    case SDS_TYPE_32:
    return SDS_HDR(32,s)->alloc;
    case SDS_TYPE_64:
    return SDS_HDR(64,s)->alloc;
    }
    return 0;
    }
    //设置sds中alloc字段为newlen
    static inline void sdssetalloc(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
    case SDS_TYPE_5:
    /* Nothing to do, this type has no total allocation info. */
    break;
    case SDS_TYPE_8:
    SDS_HDR(8,s)->alloc = newlen;
    break;
    case SDS_TYPE_16:
    SDS_HDR(16,s)->alloc = newlen;
    break;
    case SDS_TYPE_32:
    SDS_HDR(32,s)->alloc = newlen;
    break;
    case SDS_TYPE_64:
    SDS_HDR(64,s)->alloc = newlen;
    break;
    }
    }

3.sds.c源码分析

  1. sdsnew:创建一个包含给定C字符串的sds

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    ds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
    * since type 5 is not good at this. */
    //因为type 5没有free=alloc-len字段,只有len字段
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    sh = s_malloc(hdrlen+initlen+1);
    //如果init为NULL,则buff内容为0
    if (!init)
    memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    s = (char*)sh+hdrlen;
    //flags字段
    fp = ((unsigned char*)s)-1;
    switch(type) {
    case SDS_TYPE_5: {
    //低3bits位type,高5bits位buff的length
    *fp = type | (initlen << SDS_TYPE_BITS);
    break;
    }
    case SDS_TYPE_8: {
    SDS_HDR_VAR(8,s);
    sh->len = initlen;
    sh->alloc = initlen;
    *fp = type;
    break;
    }
    case SDS_TYPE_16: {
    SDS_HDR_VAR(16,s);
    sh->len = initlen;
    sh->alloc = initlen;
    *fp = type;
    break;
    }
    case SDS_TYPE_32: {
    SDS_HDR_VAR(32,s);
    sh->len = initlen;
    sh->alloc = initlen;
    *fp = type;
    break;
    }
    case SDS_TYPE_64: {
    SDS_HDR_VAR(64,s);
    sh->len = initlen;
    sh->alloc = initlen;
    *fp = type;
    break;
    }
    }
    if (initlen && init)
    memcpy(s, init, initlen);
    //buff以0结尾
    s[initlen] = '\0';
    return s;
    }
  2. sdsfree:释放给定的sds

    1
    2
    3
    4
    void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
    }
  3. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    //保证alloc-len >= addlen
    sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    //avail=alloc-len
    size_t avail = sdsavail(s);
    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(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    //如果newlen小于1M,则分配和newlen同样大小的未使用空间
    if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;
    else
    newlen += SDS_MAX_PREALLOC;//如果newlen的长度大于1M,则分配1M的未使用空间.
    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);
    //如果新的sds结构体类型与old sds结构体类型相同
    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;
    memcpy((char*)newsh+hdrlen, s, len+1);
    s_free(sh);
    s = (char*)newsh+hdrlen;
    s[-1] = type;
    sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
    }
  4. sdscat:将给定的C字符串拼接到sds字符串的末尾

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    ds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);
    //确保s所指向的buf[]有足够空间
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
    }
  5. 其他函数注释在参考文献2指向的github仓库查看相关文件。

4.参考文献

redis_reading