Skip to content

Instantly share code, notes, and snippets.

@antirez

antirez/wft.md

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
You can’t perform that action at this time.