Redisソース-データ構造のsds文字列

国慶節は呂友に付き添う以外に、2日足らずでRedisを初歩的に理解して、次のしばらくの時間、Redisのソースコードを深く読んで、1つの記録をして、1つのソースコードを見て、私はやはり先に基礎のモジュールから見て、例えば、データ構造、Redisの中の多くのデータ構造を実現して、もちろん、多くのオープンソースプロジェクトも自分で各種のデータ構造を実現してカスタマイズの需要を満たすと思っています.まず最初に読んだのは下位文字列モジュール-SDSです
sdsの定義:

typedef char *sds;

はっきり言って文字列の別名で、Redis全体の文字列はこれを使っていますが、内部ではこのsdsを維持するために構造が使われています.

struct sdshdr {                 
    unsigned int len;                       
    unsigned int free;                                     
    char buf[];                                                                          
}; 

このように設計されたのは、Redisのいくつかの特性に合致するためであり、総じて、sdsはC言語の文字列に比べて以下のいくつかの利点を有する.
1.文字列長を取得する複雑さはO(1)であり、内部で文字列長を保存するlenが維持されているため

static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

lenとfreeフィールドにアクセスするには、ポインタを構造体が出始めるまで、ここを見てためらったが、基礎知識はだめだった——!
2.バイナリセキュリティ
ここではバイナリセキュリティとは何かを説明し、C言語の文字列はASCII符号化で表されていますが、ここでは文字配列を使っています.

    sds s = sdsnewlen("test", 5); 
    printf("%s
", s); 
    size_t len = sdslen(s);
    printf("%zu
", len);
    size_t free = sdsavail(s);
    printf("%zu
", free);

得られるlen=5
ソース:

/* Create a new sds string with the content specified by the 'init' pointer
 * and 'initlen'.
 * If NULL is used for 'init' the string is initialized with zero bytes.
 *
 * The string is always null-termined (all the sds strings are, always) so
 * even if you create an sds string with:
 *
 * mystring = sdsnewlen("abc",3");
 *
 * You can print the string with printf() as there is an implicit \0 at the
 * end of the string. However the string is binary safe and can contain
 * \0 characters in the middle, as the length is stored in the sds header. */
sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh; 

    if (init) {
        sh = malloc(sizeof(struct sdshdr)+initlen+1);
    } else {
        sh = calloc(1,sizeof(struct sdshdr)+initlen+1);
    }    
    if (sh == NULL) return NULL;
    sh->len = initlen;
    sh->free = 0; 
    if (initlen && init)
        memcpy(sh->buf, init, initlen);
    sh->buf[initlen] = '\0';
    return (char*)sh->buf;
}

3.バッファオーバーフローは発生しません.freeフィールドを使用すると、文字列の長さを変更したメモリの再割り当てを減らすことができます.
C言語のこの2つの関数のセットが不適切に使用されると、バッファがオーバーフローすることを知っています.

char *strcat(char *dest, const char *src);
char *strncat(char *dest, const char *src, size_t n);
The  strcat()  function  appends the src string to the dest string, overwriting the null byte ('\0') at the end of dest, and then adds a terminating null byte.  The strings may not overlap, and the dest string must have enough space for the result.
The strncat() function is similar, except that
*  it will use at most n characters from src; and
*  src does not need to be null terminated if it contains n or more characters.
As with strcat(), the resulting string in dest is always null terminated.

、sdsのcatは以下のように実現される.

/* 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) {
    struct sdshdr *sh; 
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    sh = (void*) (s-(sizeof(struct sdshdr)));
    memcpy(s+curlen, t, len);
    sh->len = curlen+len;
    sh->free = sh->free-len;
    s[curlen+len] = '\0';
    return s;
}

では、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) {
    struct sdshdr *sh, *newsh;
    size_t free = sdsavail(s);
    size_t len, newlen;

    if (free >= addlen) return s;
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else 
        newlen += SDS_MAX_PREALLOC;
    newsh = realloc(sh, sizeof(struct sdshdr)+newlen+1);
    if (newsh == NULL) return NULL;

    newsh->free = newlen - len; 
    return newsh->buf;
}

は、sdsが文字列長の変更に対してこのような規則があることを示している.
AddLenAddLen > free && AddLen < 1M free = len
AddLen > free && AddLen > 1M free = 1M