How is realloc implemented in the C standard library?

Question

I can't find any source code for the realloc function and it seems to break the fundamental rule of C: it doesn't take the length of the memory to reallocate.

1. How is memory reallocated without knowing the length of the original memory?

2. How could I implement this function myself?

Answer 1

There are at least 3 considerations that make it difficult or impossible to implement realloc entirely in "userland" C.

1. Interacting with the same data structures that malloc and free use.

2. malloc and realloc are required to return storage that is suitably aligned for any object. Until C11 we have not had all the necessary macros to calculate this alignment 100% portably.

3. There's a tricksy language-lawyerly reason that malloc and realloc cannot be implemented in portable C. I may be garbling the terminology here, but the problem is that after the function has computed the pointer value that it will return, it has no means to relinquish the "effective type" which has become associated with the storage. So even if you can get your versions to work, it is de facto non-standard.

Answer 2

Consider an example (in c):

#include <stdio.h>
#include <stdlib.h>
struct A {
    int x[10];
    int y[1];
};

int main()
{
  struct A *ptr = calloc(1, sizeof(struct A));
  ptr->x[10] = 4;
  printf("%i\n", ptr->x[10]);
  ptr = realloc(ptr, 80);  // realloc
  ptr->x[20] = 4;
  printf("%i\n", ptr->x[20]);
  free(ptr);
  return 0;
}

Now consider the following assembly code (relevant to the realloc function) (off course if you are interested):

  400604:       48 8b 45 f8             mov    rax,QWORD PTR [rbp-0x8]
  400608:       be 50 00 00 00          mov    esi,0x50
  40060d:       48 89 c7                mov    rdi,rax
  400610:       e8 bb fe ff ff          call   4004d0 <realloc@plt>
  400615:       48 89 45 f8             mov    QWORD PTR [rbp-0x8],rax

Now, in here, the pointer ptr is getting moved into the register rax, which eventually gets moved into the register esi. And the size of the pointer to be re-allocated into the register rdi. The line 4 is a call to the realloc@GLIBC function. Here pointer ptr must have been allocated previously by malloc, calloc (in this case) and realloc functions. In the last line, rax contains the pointer to the new memory region (returned by realloc) which is assigned to the pointer ptr (notice, rbp-0x8 is the location of the pointer on the stack).

How is memory reallocated without knowing the length of the original memory?

This realloc function in the standard library (e.g. library code used) is defined as:

void * __libc_realloc (void *oldmem, size_t bytes)

Here, *oldmem is the pointer to the old memory, pointer ptr in our case. and bytes is the size to be allocated, 80 in our case. This function has a lot checks like, to check if the pointer is null if so, treat it as a simple malloc function, to check if the bytes are 0, if so treat it as a free, etc. We are interested in the following lines:

  /* chunk corresponding to oldmem */
  const mchunkptr oldp = mem2chunk (oldmem);
  /* its size */
  const INTERNAL_SIZE_T oldsize = chunksize (oldp);

It means that the all the information is being kept internally (in the malloc program headers, as pointed out previously by @SirDarius in the comments), i.e. every pointer and the size associated with it. If everything goes right, then it calls another function (in this case):

_int_realloc(mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
             INTERNAL_SIZE_T nb)

This function allocates the actual size in the memory. and returns a new_pointer, which is eventually returned by __libc_realloc and we receive that in the register rax.

How could I implement this function myself?

If you are interested, you can look at the complete code here.