title: realloc() use-after-free address sanitizer issue with recursion
body: <p>I wrote a small program to in-order traverse a binary tree, I wanted to practice <code>realloc</code> and wrote the following code to dynamically fill an array with the elements of a binary search tree:</p>
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;stdbool.h&gt;
  
  struct TreeNode {
      int val;
      struct TreeNode *left;
      struct TreeNode *right;
  };
   
  void inorder(struct TreeNode *root, int *inorder_arr, int *size) {
      if (root) {
          inorder(root-&gt;left, inorder_arr, size);
          inorder_arr[(*size)-1] = root-&gt;val;
          (*size)++;
          inorder_arr = (int *)realloc(inorder_arr, (*size) * sizeof(int));
          inorder(root-&gt;right, inorder_arr, size);
      }
  }
  
  bool findTarget(struct TreeNode *root, int k) {
      if (!root) return false;
      int size =1;
      
      int *inorder_arr = (int *)malloc(sizeof(int));
      inorder(root, inorder_arr, &amp;size);
      return false;
  }
  
  int main () {
      // this is for creating a binary search tree which its inorder traversal looks like this : 2,3,4,5,6,7
      struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
      root-&gt;val = 5;
      root-&gt;left = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
      root-&gt;left-&gt;val = 3;
      root-&gt;right = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
      root-&gt;right-&gt;val = 6;
      root-&gt;right-&gt;right = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
      root-&gt;right-&gt;right-&gt;val = 7;
      root-&gt;left-&gt;right = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
      root-&gt;left-&gt;right-&gt;val = 4;
      root-&gt;left-&gt;left = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
      root-&gt;left-&gt;left-&gt;val = 2;
      printf(&quot;%d&quot;, FindTarget(root, 9));
  }
  </code></pre>
  <p><strong>~please neglect the fact that my function <code>FindTarget</code> will always return <code>false</code>, this is not the full purpose of this program, and not the purpose of my question.</strong></p>
  <p>also it might be useful to note that my binary search tree looks like this:
  <a href="https://i.stack.imgur.com/EYBhz.png" rel="nofollow noreferrer">binary search tree.png</a></p>
  <p><strong>~My program seems to work but I have a big issue when compiling it with address sanitizer using:</strong></p>
  <pre><code>gcc -ggdb 2_sum_bst.c -fsanitize=address
  </code></pre>
  <p>when I run my program &quot;a.out&quot; I get the following error:</p>
  <pre><code>=================================================================
  ==13399==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000014 at pc 0x55c7a8ef5d77 bp 0x7ffebafbf0c0 sp 0x7ffebafbf0b0
  WRITE of size 4 at 0x602000000014 thread T0
      #0 0x55c7a8ef5d76 in inorder /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:15
      #1 0x55c7a8ef5cb8 in inorder /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:14
      #2 0x55c7a8ef5ef3 in findTarget /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:28
      #3 0x55c7a8ef628b in main /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:45
      #4 0x7f1186741b96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
      #5 0x55c7a8ef5b79 in _start (/home/yarin/my_dev/C_C++_learning/basics/a.out+0xb79)
  
  0x602000000014 is located 0 bytes to the right of 4-byte region [0x602000000010,0x602000000014)
  freed by thread T0 here:
      #0 0x7f1186beff30 in realloc (/usr/lib/x86_64-linux-gnu/libasan.so.4+0xdef30)
      #1 0x55c7a8ef5da6 in inorder /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:17
      #2 0x55c7a8ef5cb8 in inorder /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:14
      #3 0x55c7a8ef5cb8 in inorder /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:14
      #4 0x55c7a8ef5ef3 in findTarget /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:28
      #5 0x55c7a8ef628b in main /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:45
      #6 0x7f1186741b96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
  
  previously allocated by thread T0 here:
      #0 0x7f1186befb40 in __interceptor_malloc (/usr/lib/x86_64-linux-gnu/libasan.so.4+0xdeb40)
      #1 0x55c7a8ef5ecf in findTarget /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:27
      #2 0x55c7a8ef628b in main /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:45
      #3 0x7f1186741b96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
  
  SUMMARY: AddressSanitizer: heap-use-after-free /home/yarin/my_dev/C_C++_learning/basics/2_sum_bst.c:15 in inorder
  Shadow bytes around the buggy address:
    0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
    0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
    0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
    0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
    0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  =&gt;0x0c047fff8000: fa fa[fd]fa fa fa 00 fa fa fa fa fa fa fa fa fa
    0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  Shadow byte legend (one shadow byte represents 8 application bytes):
    Addressable:           00
    Partially addressable: 01 02 03 04 05 06 07 
    Heap left redzone:       fa
    Freed heap region:       fd
    Stack left redzone:      f1
    Stack mid redzone:       f2
    Stack right redzone:     f3
    Stack after return:      f5
    Stack use after scope:   f8
    Global redzone:          f9
    Global init order:       f6
    Poisoned by user:        f7
    Container overflow:      fc
    Array cookie:            ac
    Intra object redzone:    bb
    ASan internal:           fe
    Left alloca redzone:     ca
    Right alloca redzone:    cb
  ==13399==ABORTING
  </code></pre>
  <p>~ as we can see I got heap-use-after-free and i got curious and started to debug the program</p>
  <p>~ I started to debug the program and realized my mistake, when my function &quot;inorder&quot; is doing its recursive calls when it starts to backtrack the pointer that points to my array at each call in the call stack is unique to that specific call , but I used realloc and realloc frees the memory and allocates new memory and returns the pointer to that pointer in that call and not to all pointers in the call stack, running this issue which is little complicated I thought how could I do a workaround this issue without using a global pointer, I thought about using static pointer but that also did not work..</p>
  <p><strong>as of now I can't think how can I possibly work around this issue without using a global pointer, I would like to hear suggestions since I am a beginner to C Programming and want to know the best solution to such case without using a global pointer or without traversing the whole tree getting its size and then using malloc to get enough memory for all the nodes, as you can see my purpose here is to do it as my program Traverses the tree.</strong></p>
  <p>thank you in advance for reading and helping!</p>