I hope everyone can really read the source code, to understand firsthand knowledge. Instead of just going to see each public number copy to copy a few articles, some or even wrong.

^_^

How come so many people say that the magic reading problem in mysql is solved by MVCC?

SDS string: The name is simple dynamic string, but it is anything but simple. If all you know is that he can dynamically expand, that’s far from it.

Dynamic object header

First, the SDS object header definition and implementation of the basic string functions are in the SDS.h header file. A total of 5 SDS header formats are defined as follows:

/* 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 */
    charbuf[]; }; .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[];
};
Copy the code

Where sdshdr5 is not used according to the comments, we ignore it.

The only other structure types that differ are len, which represents length, and alloc, which records allocated memory.

Unalignment of bytes

Again, notice the __attribute__ ((__packed__)) modifier on the structure, which cancellations byte alignment.

To verify this, I wrote the following little code:

struct packed_test_a
{
    char i;        
    uint32_t j; 
};
struct __attribute__(((packed__)) packed_test_b
{
    char i;        
    uint32_tj; }; .struct packed_test_a a;
    struct packed_test_b b;

    a.i = 'a';
    b.i = 'b';

    a.j = 1u;
    b.j = 2u;
    printf("%d \n".sizeof(a));    / / 5
    printf("%d \n".sizeof(b));    / / 8

Copy the code

It’s not enough to just look at sizeof, so let’s use GDB to debug:

1 Type the breakpoint at the location of the first printf and run the r command to the breakpoint (line 37).

Thread 2 hit Breakpoint 1, main (argc=1, argv=0x7ffeefbff7d8)
    at packed_test.c:37
37	    printf("%d \n".sizeof(a));
Copy the code

2 Check the memory at variable A, using x/ 24xb&a

0x7ffeefbff798:	0x61	0x01	0x00	0x00	0x00	0x00	0x00	0x00.Copy the code

3 Check the memory at variable b, using x/ 24xb&b

0x7ffeefbff790:	0x62	0x00	0x00	0x00	0x02	0x00	0x00	0x00.Copy the code

In this way, it is obvious that on variable A with an __attribute__ ((__packed__)) modifier, the data a.i = 0x61 and a.j = 0x01 are stored consecutively.

In variable B, b.I = 0x62 and B.j = 0x02 are filled with 3 bytes of 0x00 data for alignment.

Select the appropriate object header based on the length

create

Take a look at the function that creates the SDS string: sdsnewlen.

The function signature is as follows:

sds sdsnewlen(const void *init, size_t initlen) 
Copy the code

Step one, uses_mallocAllocate enough memory. That is, the length of the object header + the initial length of the string + 1(C string terminator placeholder).

    sh = s_malloc(hdrlen+initlen+1);
Copy the code

The second step is to initialize the allocated memory and use memset to batch set zero values.
Third, set the variable Pointers s, FP.

    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)- 1;
Copy the code

Here, a little plot twist: * FP points to *s-1. Where *s points to the start address of the data area, *s-1 is sdS.flags.

Step 4 set the object header properties according to the type:

    switch(type) {
        ...
            case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break; }... }Copy the code

Step 5: Set the initial value in the data area

    memcpy(s, init, initlen);
Copy the code

Finally, wrap things up

    s[initlen] = '\ 0';
    return s;
Copy the code

Note: The actual pointer returned here is*s. This is the starting address of the SDS string data area.

capacity

Here we go straight to the sdsMakeRoomFor function.

If the capacity is smaller than 1MB, the capacity is directly multiplied by 2. Otherwise, the capacity is expanded by 1MB. Yeah, it comes from here.

    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
Copy the code

Then, it will judge whether the original object header is consistent with the expanded object header to decide whether to expand directly or… Removable nipple?

    hdrlen = sdsHdrSize(type);
    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);
    }
Copy the code

Thanks to Redis’s single-threaded model, the code is also extremely simple: allocate sufficient length, copy and free the original memory.

Shrinkage capacity

The function is the same as expansion, see sdsRemoveFreeSpace.

Note that the scaling function returns the unallocated space in the SDS. The value of the string itself does not change.

    /* If the type is the same, or at least a large enough type is still * required, we just realloc(), letting the allocator to do the copy * only if really needed. Otherwise if the change is huge, we manually * reallocate the string to use the different header type. */
    if (oldtype==type || type > SDS_TYPE_8) {
        newsh = s_realloc(sh, oldhdrlen+len+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+oldhdrlen;
    } else {
        newsh = s_malloc(hdrlen+len+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);
    }
Copy the code

When the original type is the same as the target type, or the original type is above sdSHdr8, the type is not replaced, but only reassigned to an exact capacity using s_realloc.

Notice the presence of an S [-1] in the code? Can an array index be negative? That’s weird, right? Hold on

Storage structure

By looking at the structure definition of the SDS string, we can draw its memory storage structure (we use sdSHdr8 as an example) :

Except for SDSHDR5, the storage structure of the other four is the same.

Note that len,alloc,flags,*buf must be tightly connected in memory because the __attribute__ ((__packed__)) modifier is added to the structure.

Those “dirty” operations in the code

Negative array subscripts

If you take a closer look at the code, you’ll notice that there are plenty of ways to write this:

    unsigned char flags = s[- 1];
Copy the code

In some languages, a negative index of an array indicates the number of elements to access. But C, the top of the contempt chain, is a different story

In C, an array is a pointer, and s[-1] has the same effect as *s-1.

So, we know that s[-1] calls the flags property in the structure.

So why use it this way?

Because you’ve seen the function that creates SDS. We know that after creation, the exposed pointer only points to the location of the data area, namely the *buf property.

So, let’s start with this question: why is only the address of the data area directly returned, and not the entire SDS header address

*bufIs a native C array on which all string-related functions provided in the STL can be used directly.
sdsThe head is dynamic, just onesdsYou can’t access any properties because you don’t know how the data is currently distributed.

So, if we return a pointer to an address between flags and *buf.

Since we know that flags is fixed length, we can retrieve the entire flags data by moving one char forward. And once we have flags we can know the distribution of the data in the header of the object and access the other len alloc properties.

The compiler preprocesses macros

Now let’s look at how to fetch the other fields in the header now that we have the *s pointer and flags.

How about continuing to use negative subscripts: -(1+1), -(1+1+1) and so on, that’s really completely unreadable.

Let’s look at the len method:

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_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}
Copy the code

As you can see, the same SDS_HDR macro is used for different types (except SDS_TYPE_5), except that the first argument is different.

Take a look at his macro definition:

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
Copy the code

It’s just one line of code, and there’s a symbol ## : another type of preprocessor macro. Two hacks, called connectives, join two tokens into one.

For example, SDS_HDR(8,s), after being preprocessed by the compiler, would look like this:

((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))
Copy the code

Isn’t that amazing? Macro parameters also become part of the code itself.

So, let’s see what this code does:

Sizeof (struct sdshdr8), sizeof(struct sdshdr8), sizeof(struct sdshdr8), sizeof(struct sdshdr8

Then, the first half: is a cast, because we have the head pointer to the SDS, so we just need to cast, and then we can do whatever we want.

conclusion

Simple dynamic strings: As one of the most photographed data structures in Redis, it is anything but simple. Not only the length has been dynamically expanded, but the head has also been dynamically expanded in order to maximize the use of space.

Also, the header stores the length of the current string, which is obvious: even though *buf refers to a standard C string, using the strlen function to find the length would have to traverse the entire string.

If you store extra, it’s a whole different story.

And, thanks to Redis’s single-threaded system, complex operations become incredibly simple.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Redis source code read SDS you don’t know

Dynamic object header

Unalignment of bytes

Select the appropriate object header based on the length

create

capacity

Shrinkage capacity

Storage structure

Those “dirty” operations in the code

Negative array subscripts

The compiler preprocesses macros

conclusion

Redis source code read SDS you don’t know

Dynamic object header

Unalignment of bytes

Select the appropriate object header based on the length

create

capacity

Shrinkage capacity

Storage structure

Those “dirty” operations in the code

Negative array subscripts

The compiler preprocesses macros

conclusion

Related Posts

Java Inheritance: A brief explanation of Java inheritance

S01E02 Common Chrome extension + Vim entry + Crossover + Hosts

Some special types in TypeScript