How does realloc manages pointer size?

Question

I'm working with realloc() function in C and I've a question about how this function really works...

Imagine that I read an ASCII file containing a list of integers

$ cat liste.txt
1
2
3

I want this list to be stored in a integer table. Here is my code, which uses realloc() each time a new value is read from the file

int *table, *table_tmp;
int n;
int taille = 0;

while ( fscanf(fid, "%d", &n) != EOF)
    {
    table_tmp = (int *) realloc((void *) table, (taille+1)*sizeof(int));
    if (table_tmp != NULL)
        table = table_tmp;

    *(table+taille) = n;
    fprintf(stdout, "READ : %02d\tSTORED : %02d\n", n, *(table+taille));
    taille++;
    }

My question is : how does this function knows the actual size of table ??? Since it's just a pointer, I thought we can not know the number of elements right ? We explicitly have track of the current size through the taille variable which is increased at each step and tell us the maximum value acceptable for reading *(table+k)

The realloc() function changes the size of the memory block pointed to by >ptr to size bytes. The contents will be unchanged in the range from >the start of the region up to the minimum of the old and new sizes.

man realloc

Thanks a lot for your answer :)

BR

It depends on the implementation, but usually `malloc` will store metadata a couple of bytes before the pointer it returns to you. I.e. it allocates a slightly larger block, stores the length, and then advances the pointer a bit. — Lou, Aug 29 '19 at 08:31
You're absolutely right that in general, there's no way to determine how much memory a pointer points to. But `malloc`, `realloc`, and `free` are special: They use special techniques (see the referenced questions) to track the sizes of the memory blocks. That's why you have to use *only* pointers returned by `malloc` when handing them to `realloc` or `free`. — Steve Summit, Aug 29 '19 at 10:37
I realise this is probably just test code to illustrate the point, but it fails to initialise `table` and fails if `realloc()` returns `null` (`table` wouldn't be updated, so `*(table+taille) = n;` will be out-of-bounds). — TripeHound, Aug 29 '19 at 10:53

klutt · Answer 1 · 2019-08-29T11:16:29.687

1

That's handled by the operating system or equivalent. The information about sizes is not required by the C standard to be available to the programmer.

A very common approach is that the information is stored right before the address the pointer is pointing to.

edited Aug 29 '19 at 11:16

answered Aug 29 '19 at 08:58

klutt

30,332
17
55
95

1

While in some implementations these functions _may_ just be wrappers around OS calls, I believe it's perfectly possible for the C library to handle things itself... e.g. it allocates (larger) blocks of memory from the OS as and when needed, which it then manages internally to satisfy individual `malloc()`/`realloc()` calls. – TripeHound Aug 29 '19 at 10:49

Donut · Answer 2 · 2019-08-29T12:18:07.337

thank you to all of you for your quick answer.

Following your suggestion, I dig a little bit in the glibc source code and here some little information about how it is done.

definition of realloc() in malloc.c

void *
__libc_realloc (void *oldmem, size_t bytes)
    {
     (...)

  /* realloc of null is supposed to be same as malloc */
  if (oldmem == 0)
    return __libc_malloc (bytes);

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

(...)

In the same file, we can see that the mem2chunk is a macro that offsets the pointer (with negative value, so indeed in seems that the size of the pointed memory is stored BEFORE the pointer) :

#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))

and SIZE_SZ is defined in malloc_internal.h

#ifndef INTERNAL_SIZE_T
# define INTERNAL_SIZE_T size_t
#endif

/* The corresponding word size.  */
#define SIZE_SZ (sizeof (INTERNAL_SIZE_T))

Going back to malloc.c, we can finally find a definition of the chuncksize function which (as far as I understood the code) returns the size of the given memory.

/* Get size, ignoring use bits */
#define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))

/* Like chunksize, but do not mask SIZE_BITS.  */
#define chunksize_nomask(p)         ((p)->mchunk_size)

The last and final step is to find the precise definition of the mchunkptr structure. Sadly I didn't manage to find it in the source code... It should request more investigation.. The closest that I have found is the following (still in malloc.c file) :

/*
  -----------------------  Chunk representations -----------------------
*/


/*
  This struct declaration is misleading (but accurate and necessary).
  It declares a "view" into memory allowing access to necessary
  fields at known offsets from a given base. See explanation below.
*/

struct malloc_chunk {

  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};


/*
   malloc_chunk details:

    (The following includes lightly edited explanations by Colin Plumb.)

    Chunks of memory are maintained using a `boundary tag' method as
    described in e.g., Knuth or Standish.  (See the paper by Paul
    Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
    survey of such techniques.)  Sizes of free chunks are stored both
    in the front of each chunk and at the end.  This makes
    consolidating fragmented chunks into bigger chunks very fast.  The
    size fields also hold bits representing whether chunks are free or
    in use.

    An allocated chunk looks like this:


    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of previous chunk, if unallocated (P clear)  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of chunk, in bytes                     |A|M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             User data starts here...                          .
        .                                                               .
        .             (malloc_usable_size() bytes)                      .
        .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             (size of chunk, but used for application data)    |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of next chunk, in bytes                |A|0|1|
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

How does realloc manages pointer size?

man realloc

2 Answers2