Is there a way to shrink a memory allocation from the left in C without copying data?

Question

I understand that the C standard library allows for the resizing of a memory allocation through the use of the realloc function, like in the following example:

char *a = malloc(10);
char *b = realloc(a, 8);

In this case, a and b could potentially be equal, and the allocation has effectively been shrunk by two bytes from the right.

However, I'm wondering if there's a way to shrink a memory allocation from the left, something like this:

char *a = malloc(10);
char *b = /* ... */;  // shrink a from the left by 2 bytes

Where (a + 2) == b, and the original 2 bytes at the start of a are now free for the allocator to use. This should happen without having to copy the data to a new location in memory. Just shrink the allocation.

I'm aware that using realloc to shrink the memory from the right or manually copying the data to a new, smaller allocation might be an option, but these methods don't suit my needs.

Is there any way to achieve this using C's standard library or any other library that provides this functionality?

I'm not asking for 100% guarantee, realloc also could return a pointer to a different location, but it is likely that it will.

Thank you in advance for your insights.

I could shift all bytes to the left and try to shrink, but it involves copying.

Answer 1

Edit: As mentioned in the comments below, i have rewritten some of this (late but anyway), as especially the part about paging and the buddy system was quite inaccurate.

Back to the subject:

Even though it is an intriguing idea to manage memory like this yourself, I might be able to provide some explanation of why it is also a bad idea in most circumstances:

Managing a memory efficiently is an actual science in itself. This article provides a good overview and has nice references for a deep dive if you are interested in how an operating system does it.

Say you have a block of memory like below with previously allocated areas.

Now imagine some of the areas are no longer needed and get freed (blocks in blue). Suddenly your memory does not look that pretty anymore. New areas have to be allocated, more of the old ones are freed, your memory looks like Swiss cheese - holes all over it - in no time. This is memory fragmentation. Sure - you could keep a list (or similar) of the free memory spaces, where you are still able to allocate, but your implementation already is growing bigger and bigger. If you now try to free from the left, where does your next memory header go etc? (Even ignoring compaction of memory in this case)

To make matters worse: If you free memory, how do you know if the memory blocks next to that free chunk are still in use? Even more management to do. If you do not, your memory can be free, but still fragmented like this:

There are solutions, but my advice would be to let malloc() and realloc() do their job. Work with what you got.

Answer 2

With more informations about your system, we could answer the question in more direct way (if it is a good idea or not is a different question).

If you are using a POSIX system, you can maybe use mmap() and munmap() for this. This makes only sense when you need large amounts of memory which is multiple times the page size and worth freeing. You can reserve memory with mmap() (check man mmap). After you no longer need the first N bytes of it (N must be a larger than a page), you can use munmap() to free M pages (N>=M*pageSize), and still use the memory after that.

I made a short demonstration for that:

#include <stdio.h>
#include <sys/mman.h>

int main(void)
  {
    //Map pages for the memory needed
    unsigned char *t=mmap(NULL,1024*1024,PROT_READ|PROT_WRITE,MAP_PRIVATE|MAP_ANONYMOUS,-1,0);
    printf("mmap returned address %p for 1MiB\n",t);
    if(!t)
      { perror("mmap"); return -1; }
    printf("Writing to the mapped pages\n");
    t[12]='A';

    printf("unmap the first 16 KiB we don't need anymore\n",t);
    if(munmap(t,16*1024)<0)
      { perror("munmap"); return -1; }
    printf("Writing after the unmapped pages, to the still mapped pages\n");
    t[16*1024+12]='A';

    #if 0 //Set to 0 when you don't want to see the segement fault
      printf("Create segment fault\n");
      t[15]='A'; //accessing the unmapped pages will cause a segment fault or any other UB.
    #endif

    printf("unmap the rest of the memory\n");
    if(munmap(t+16*1024,(1024-16)*1024)<0)
      { perror("munmap 2"); return -1; }
    printf("Test done successfully\n");
    return 0;
  }

This demonstration does not check the page size, for a real program you have to get the page size and make sure to only map and unmap whole pages. You also will have a harder time when you want to grow the reserved memory (make sure you don't collide with other pages, ..., maybe move_pages() can become handy when available on your system). There are probably similar solution for other, non-Posix, platforms that have a MMU.

Answer 3

When you allocate something on the heap, pretty much every implementation out there requires more data to be allocated in addition to the user data. The bytes you see through the malloc & friends interface is just the user data. A common way for the standard library/OS to implement heap allocation is to first allocate a segment header, followed by the data.

This means that to the immediate "left" (lower addresses) of the data part of the segment sits the header. Leaving a gap there between header and data doesn't make any sense. Rather, you'd have to move the whole thing to a new memory location.

---

but these methods don't suit my needs.

And what are those needs, exactly? When using dynamic memory we must be aware that:

• It is much slower than statically allocated memory at the point of allocation and initialization.
• It always comes with a memory overhead. Overhead in terms of headers/look-up tables etc, overhead in terms of dealing with alignment, overhead in terms of heap fragmentation.

For example:

char *a = malloc(10);
char *b = realloc(a, 8);

Probably consumes much more RAM memory overall than lets say char c[12];. And it will almost certainly be some ~100 to 1000 times slower.

It is also quite likely that the execution time overhead involved in calling realloc is far more expensive than a memcpy/memmove call.

So what is the actual problem you are trying to solve here?

Answer 4

realloc or any other standard library function doesn't allow you to control in what direction the memory region is contracted. In fact, it's possible that calling realloc(a, 8) will contract it from the left side, though that's not how it's typically implemented.

Solution 1 - don't realloc, just do pointer arithmetic

You could do this manually using pointer arithmetic though:

char *a = malloc(10);
char *b = a + 2;

// TODO: free(a), or
//       free(b - 2)

Note that free(b) wouldn't be allowed, because free must be called exactly with the same pointer as returned by malloc or realloc.

Solution 2 - contract from the right, view array in reverse

Another possibility is interacting with the array in reverse, always. Instead of indexing it with a[i], index it with a[end - i - 1].

int end = 10;
char *a = malloc(end);
// first byte of reverse array is at a a[9]

end = 8;
a = realloc(a, end);
// first byte is now at a[7]

This way, even if we contract from the right, it is as if we contracted from the left.