Skip to content

Instantly share code, notes, and snippets.

@antirez
Created Feb 1, 2018
Embed
What would you like to do?

Hello!

That's the C function (you can find it inside the Redis source code, inside rax.c).

raxNode *raxRemoveChild(raxNode *parent, raxNode *child) {
    debugnode("raxRemoveChild before", parent);
    /* If parent is a compressed node (having a single child, as for definition
     * of the data structure), the removal of the child consists into turning
     * it into a normal node without children. */
    if (parent->iscompr) {
        void *data = NULL;
        if (parent->iskey) data = raxGetData(parent);
        parent->isnull = 0;
        parent->iscompr = 0;
        parent->size = 0;
        if (parent->iskey) raxSetData(parent,data);
        debugnode("raxRemoveChild after", parent);
        return parent;
    }

    /* Otherwise we need to scan for the children pointer and memmove()
     * accordingly.
     *
     * 1. To start we seek the first element in both the children
     *    pointers and edge bytes in the node. */
    raxNode **cp = raxNodeFirstChildPtr(parent);
    raxNode **c = cp;
    unsigned char *e = parent->data;

    /* 2. Search the child pointer to remove inside the array of children
     *    pointers. */
    while(1) {
        raxNode *aux;
        memcpy(&aux,c,sizeof(aux));
        if (aux == child) break;
        c++;
        e++;
    }

    /* 3. Remove the edge and the pointer by memmoving the remaining children
     *    pointer and edge bytes one position before. */
    int taillen = parent->size - (e - parent->data) - 1;
    debugf("raxRemoveChild tail len: %d\n", taillen);
    memmove(e,e+1,taillen);

    /* Since we have one data byte less, also child pointers start one byte
     * before now. */
    memmove(((char*)cp)-1,cp,(parent->size-taillen-1)*sizeof(raxNode**));

    /* Move the remaining "tail" pointer at the right position as well. */
    size_t valuelen = (parent->iskey && !parent->isnull) ? sizeof(void*) : 0;
    memmove(((char*)c)-1,c+1,taillen*sizeof(raxNode**)+valuelen);

    /* 4. Update size. */
    parent->size--;
    
    /* realloc the node according to the theoretical memory usage, to free
     * data if we are over-allocating right now. */
    raxNode *newnode = rax_realloc(parent,raxNodeCurrentLength(parent));
    if (newnode) {
        debugnode("raxRemoveChild after", newnode);
    }
    /* Note: if rax_realloc() fails we just return the old address, which
     * is valid. */
    return newnode ? newnode : parent;
}

And this is the disassembled code of the binary sent by the users compiled with GCC 5.4:

   0x000000000049c010 <+0>:	push   %r14
   0x000000000049c012 <+2>:	push   %r13
   0x000000000049c014 <+4>:	push   %r12
   0x000000000049c016 <+6>:	push   %rbp
   0x000000000049c017 <+7>:	mov    %rdi,%rbp        RDI,RBP = parent
   0x000000000049c01a <+10>:	push   %rbx
   0x000000000049c01b <+11>:	movzbl (%rdi),%eax      EAX = parent header
   0x000000000049c01e <+14>:	test   $0x4,%al         parent->iscompr ?
   0x000000000049c020 <+16>:	je     0x49c058 <raxRemoveChild+72> goto 72 ifz

   -- Some code we never enter in the case of the bug removed, let's jump
   -- to +72

   0x000000000049c058 <+72>:	mov    (%rdi),%r12d     R12D = parent header
   0x000000000049c05b <+75>:	lea    0x4(%rdi),%rax   RAX = parent->data ptr
   0x000000000049c05f <+79>:	mov    %rax,%rdi        RDI = parent->data[0]
   0x000000000049c062 <+82>:	shr    $0x3,%r12d       R12D = parent->size
   0x000000000049c066 <+86>:	mov    %r12d,%r13d      R13D = parent->size
   0x000000000049c069 <+89>:	add    %rax,%r13        R13 = parent->child ptr
   0x000000000049c06c <+92>:	cmp    0x0(%r13),%rsi   child[0] == child?
   0x000000000049c070 <+96>:	mov    %r13,%rbx        RBX = parent->child ptr
   0x000000000049c073 <+99>:	je     0x49c17d <raxRemoveChild+365> goto 365 ife
   0x000000000049c079 <+105>:	nopl   0x0(%rax)
   0x000000000049c080 <+112>:	add    $0x8,%rbx        RBX = next child ptr
   0x000000000049c084 <+116>:	add    $0x1,%rdi        RDI = next edge ptr
   0x000000000049c088 <+120>:	cmp    (%rbx),%rsi      child[j] == child?
   0x000000000049c08b <+123>:	jne    0x49c080 <raxRemoveChild+112> goto 112

   -- child found

   0x000000000049c08d <+125>:	mov    %edi,%ecx     ECX = low 32bit 'e' pointer
   0x000000000049c08f <+127>:	sub    %eax,%ecx     ECX = (e - parent->data)
   0x000000000049c091 <+129>:	mov    %ecx,%eax     EAX = (e - parent->data)
   0x000000000049c093 <+131>:	sub    $0x1,%r12d    R12D = parent->size - 1
   0x000000000049c097 <+135>:	lea    0x1(%rdi),%rsi RSI = e+1
   0x000000000049c09b <+139>:	sub    %eax,%r12d    R12D = taillen
   0x000000000049c09e <+142>:	movslq %r12d,%r14    R14 = taillen
   0x000000000049c0a1 <+145>:	mov    %r14,%rdx     RDX = taillen
   0x000000000049c0a4 <+148>:	callq  0x4221f0 <memmove@plt>

   0x000000000049c0a9 <+153>:	mov    0x0(%rbp),%edx   RBP = parent->header
   0x000000000049c0ac <+156>:	lea    -0x1(%r13),%rdi  RDI = parent->child-1
   0x000000000049c0b0 <+160>:	mov    %r13,%rsi        RSI = parent->child
   0x000000000049c0b3 <+163>:	shr    $0x3,%edx        EDX = parent->size
   0x000000000049c0b6 <+166>:	sub    %r12d,%edx    EDX = parent->size-taillen
   0x000000000049c0b9 <+169>:	sub    $0x1,%edx     EDX = psize-taillen-1
   0x000000000049c0bc <+172>:	movslq %edx,%rdx     RDX = psize-taillen-1
   0x000000000049c0bf <+175>:	shl    $0x3,%rdx     RDX = RDX*8
   0x000000000049c0c3 <+179>:	callq  0x4221f0 <memmove@plt>
                                memmove(RDI,RSI,RDX)

   0x000000000049c0c8 <+184>:	movzbl 0x0(%rbp),%edx   EDX = parent->header
   0x000000000049c0cc <+188>:	lea    0x8(%rbx),%rsi   RSI = cur_child_ptr+8
   0x000000000049c0d0 <+192>:	lea    -0x1(%rbx),%rdi  R0I = cur_child_ptr-1
   0x000000000049c0d4 <+196>:	and    $0x1,%edx        EDX = is_key?
   0x000000000049c0d7 <+199>:	add    %r14,%rdx        RDX = taillen + is_key
   0x000000000049c0da <+202>:	shl    $0x3,%rdx        RDX = RDX * 8
   0x000000000049c0de <+206>:	callq  0x4221f0 <memmove@plt>

                          ***  Where is the test for is_null? ***

>  0x000000000049c0e3 <+211>:	mov    0x0(%rbp),%edx
   0x000000000049c0e6 <+214>:	mov    $0x8,%esi
   0x000000000049c0eb <+219>:	mov    %rbp,%rdi
   0x000000000049c0ee <+222>:	mov    %edx,%eax
   0x000000000049c0f0 <+224>:	and    $0x7,%edx
   0x000000000049c0f3 <+227>:	shr    $0x3,%eax
   0x000000000049c0f6 <+230>:	add    $0x1fffffff,%eax
   0x000000000049c0fb <+235>:	and    $0x1fffffff,%eax
   0x000000000049c100 <+240>:	lea    0x0(,%rax,8),%ecx
   0x000000000049c107 <+247>:	or     %ecx,%edx
   0x000000000049c109 <+249>:	lea    0x0(,%rax,8),%rcx
   0x000000000049c111 <+257>:	test   $0x4,%dl
   0x000000000049c114 <+260>:	mov    %edx,0x0(%rbp)
   0x000000000049c117 <+263>:	cmovne %rsi,%rcx
   0x000000000049c11b <+267>:	and    $0x3,%edx
   0x000000000049c11e <+270>:	cmp    $0x1,%dl
   0x000000000049c121 <+273>:	sete   %dl
   0x000000000049c124 <+276>:	movzbl %dl,%edx
   0x000000000049c127 <+279>:	lea    0x4(%rax,%rdx,8),%rsi
   0x000000000049c12c <+284>:	add    %rcx,%rsi
   0x000000000049c12f <+287>:	callq  0x432cf0 <zrealloc>
   0x000000000049c134 <+292>:	test   %rax,%rax
   0x000000000049c137 <+295>:	je     0x49c045 <raxRemoveChild+53>
   0x000000000049c13d <+301>:	pop    %rbx
   0x000000000049c13e <+302>:	pop    %rbp
   0x000000000049c13f <+303>:	pop    %r12
   0x000000000049c141 <+305>:	pop    %r13
   0x000000000049c143 <+307>:	pop    %r14
   0x000000000049c145 <+309>:	retq
   0x000000000049c146 <+310>:	nopw   %cs:0x0(%rax,%rax,1)
   0x000000000049c150 <+320>:	mov    %rbp,%rdi
   0x000000000049c153 <+323>:	callq  0x49ba10 <raxSetData>
   0x000000000049c158 <+328>:	jmpq   0x49c045 <raxRemoveChild+53>
   0x000000000049c15d <+333>:	nopl   (%rax)
   0x000000000049c160 <+336>:	and    $0x3,%eax
   0x000000000049c163 <+339>:	xor    %edx,%edx
   0x000000000049c165 <+341>:	cmp    $0x1,%al
   0x000000000049c167 <+343>:	mov    (%rdi),%eax
   0x000000000049c169 <+345>:	sete   %dl
   0x000000000049c16c <+348>:	lea    (%rdi,%rdx,8),%rdx
   0x000000000049c170 <+352>:	shr    $0x3,%eax
   0x000000000049c173 <+355>:	mov    0x4(%rax,%rdx,1),%rsi

As you can see, where the code is like:

size_t valuelen = (parent->iskey && !parent->isnull) ? sizeof(void*) : 0;
memmove(((char*)c)-1,c+1,taillen*sizeof(raxNode**)+valuelen);

In the assembler it's not clear where the !parent->isnull test is. And in the crash report, failing to check for this, accounts exactly for doing a memmove() 8 bytes larger, creating the segfault.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment