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.