[C] Dynamic Memory (Part 4.0): Get Deep(er) in the Heap

memory
cprogramming
heap
dynamic

(oaktree) #1

Hi everyone! It’s been a while since Part 3, but rest assured that the wait has been worth it! (I hope)

This paper will cover the Linux versions of two system calls that are paramount in memory management. The same system calls, possibly different in implementation, exist on *BSD and its derivatives (macOS and such). I wouldn’t be able to tell you about the equivalent calls for Windows.

You may or may not know this, but malloc and its family of functions are not system calls. At least on Linux, you are most commonly using GLibC’s implementations of the malloc family of functions. This memory management suite is meant to be more portable than the system calls I’m about to show you. In fact, there are a handful of memory management libraries out there.

So, anyway, let’s begin with a quote from man malloc:

Normally,  malloc() allocates memory from the heap, and adjusts
the size of the heap as required, using sbrk(2).

What is this sbrk() of which the above excerpt speaks!?! Turns out it’s the inner-workings of malloc!

Note: At this point, some of you C gods and/or Linux pros may be questioning whether or not sbrk is a system call. It’s the cousin to a system call, actually. It essentially adds on a little extra functionality. So, its being a syscall is a bit “wishy-washy,” but for this paper I will likely refer to it as one.

I’ll tell you right now that sbrk actually calls a cousin function brk, which is the actual system call. Let’s look into these functions a bit more to see how they work:

$ man brk

brk()  and  sbrk()  change  the  location of the program break,
which defines the end of the process's data segment (i.e.,  the
program break is the first location after the end of the unini‐
tialized data segment).  Increasing the program break  has  the
effect  of  allocating  memory  to  the process; decreasing the
break deallocates memory.

As said above, brk and sbrk change the location of a program’s break. But what does that actually mean? Essentially, the heap has a given boundary. If you want to allocate memory, you can extend the heap. You’re basically asking the kernel to extend how much memory your process has to work with.

A question may pop in your mind: But, oaktree, how can we extend memory if there are other running processes that might be right next to our process? The answer to this is Virtual Memory – perhaps one of the best things about modern kernels/operating systems. Virtual Memory allows us as programmers to work with guaranteed-to-be contiguous memory. While our data may be spread out in RAM, the kernel provides the abstraction of one stretch of memory. (If anyone wants to dispute or clarify this, I definitely don’t have a PhD in CS [yet] so your input would be much appreciated)

So anyway, we know that we can use brk and sbrk to extend our program’s allotted memory. Let’s take a closer look at each one’s parameter specifications:

int brk(void *addr);

void *sbrk(intptr_t increment);

Both functions demand a single parameter to do essentially the same task.

brk is rawer. It asks for an address in memory to which you want the program break moved. If you pass it an address before the current break, you shrink the break and deallocate memory; if you pass it an address past the current break, you allocate memory.

sbrk provides a little more abstraction. But, in fact, it simply calls on brk and does a few extra things:

On Linux, sbrk() is implemented as a library function that uses
the  brk()  system  call, and does some internal bookkeeping so
that it can return the old break value.

So, like I said above, sbrk isn’t really a system call. When you call sbrk, you pass it a number of bytes: a negative number implies deallocation; a positive number, allocation.

brk returns 0 upon success and -1 upon failure – the typical nature of a system call. sbrk returns the address of the new program break.

Note: When you call sbrk or brk, you are shrinking/growing from the end. If you want to deallocate something that wasn’t the last-allocated thing, you have to move other things around in memory so that you end up deallocating the right stuff. And now you know why malloc/free is a thing.

To sum up the above:

  • malloc calls sbrk
  • sbrk calls brk
  • brk moves a process’s data segment/program break, allocating/deallocating memory.

Let’s get our hands dirty a little:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

My demonstration requires the above four headers.

int main(void) {
 
    /* we can use void*'s to store the program break */
    void *proc_break = sbrk(0);
   
    printf("Boundary: %p\n", proc_break);
   
    /* should increase by 4 bytes */
    if (brk(proc_break + 4) < 0) {
        perror("Couldn't Allocate Memory!!!\n");
        exit(1);
    }
   
    /* observe the wonderful black magic of pointer type-casting! */
    int *int_ptr = (int*)proc_break;
    *int_ptr = 16;
   
    printf("This is stored at %p : %i\n", int_ptr, *int_ptr ); 
    printf("Boundary: %p\n", sbrk(0));
 
    float *f_ptr = (float*)proc_break;
    *f_ptr = 0.1;
    printf("And now %p holds a float %.30f\n", f_ptr, *f_ptr);
   
    printf("Now I'm \"freeing\" that memory...\nsbrk(0) returns %p\n", sbrk(0));
    if (brk(proc_break) < 0) {
        perror("Couldn't Deallocate!!!\n");
        exit(2);
    }
 
    printf("But now it returns... %p\n", sbrk(0));
    printf("Now let's allocate for 'hello world'\n");
 
    char *feed = "hello world"; // we're gonna copy this literal to the heap!
 
    if (brk(proc_break + strlen(feed)+1 ) < 0) {
        perror("Couldn't Allocate Memory!!!\n");
        exit(3);
    }
 
    char *c_ptr = (char*)proc_break;
   
    for (int i = 0; i < strlen(feed) + 1; i++)
        c_ptr[i] = feed[i];
 
    printf("c_ptr = %p and holds %s\n", c_ptr, c_ptr);
 
    brk(proc_break - 12);
 
    return 0;
}

The above code does a few things:

  1. We call sbrk(0) to acquire the current program break address. The man page actually notes the use of sbrk(0) to keep track of the break.
  2. We print out that program break and then allocate enough memory for an int, four bytes, by expanding the program break by four bytes. We then assign an integer value to the new memory.
  3. Then, with that same memory, we store a float, which is also 4 bytes.
  4. We free up the memory by returning our program break to its original spot.

After messing around with ints and floats I decided to have a little fun by getting a string on the heap. As can be seen, the fact that it took so much code to do so should help you appreciate malloc and free.

  1. Allocate for “hello world” and initialize that string on the heap.
  2. Return to the original program break.

Conclusion

I strongly encourage you to run the above code, which can also be found here, a few times. Note how the memory addresses outputted change on each run.

There are a few things we can take away from this:

  1. Now you’ll appreciate the malloc family a bit more.
  2. If you never re-shrank the program break, and you just kept expanding it, you’d exhaust all your memory. This is what a memory leak is!!!
  3. malloc isn’t a system call.
  4. A process’s memory is contiguous (nowadays).

In the man page of brk, it is explicitly stated that brk and sbrk should never be used in your code. Let memory management libraries do the work for you! Nonetheless, understanding the brk system call and the closely-related sbrk function can help you learn more about the heap.

Last, I want you to think: what if we went beyond our program’s break? What are the implications of it? Could it even be done? Was it ever doable?

This may or may not be the last article in this series, depending on the responses to this one. If this was already too technical, I don’t think I’ll document my further explorations.

Later…
@oaktree


[C] Dynamic Memory (Part 5.0): Make Your Own Malloc
[C] Dynamic Memory (Part 6.0): A Closer Look at [My]Malloc
#2

Great stuff. I’m sure this is useful for any potential exploit devs.


(pico) #3

Congrat @oaktree. Good stuff.

That’s ASLR in action. Try to disable it to get it fixed.

I think you should keep sharing your findings. Knowing how this works… specially the insides of malloc/free data structures are basic to understand things like heap overflows.


(oaktree) #4

Thanks @0x00pf! Next, I’ll be walking through a rough implementation of malloc.


(pico) #5

That sounds great! I’m looking forward to it!


#6

I really enjoyed reading this, thank you.


(123loaded) #7

Yeah @oaktree, pleaaaaaaase keep doing these tutorials. I am very interested in the Stack and the Heap and exactly how these behave in relation to each other, and more specifically how a compiler such as GCC handles this in assembly… but I know that’s still a little ways off before we’ll get a tutorial of such nature, but just know that this isn’t too technical by any means… if anything I think it’s right on point where the users on this forum are, or should be (at least the active ones no doubt).

PS - I would be really interested to see (either theories or practically), what kind of behavior happens when the Heap meets the Stack… which one gets precedence? Does a program crash? Is there any sort of prevention measures for this built in? Obviously I’m sure malloc has these things somewhat built in… but what happens when we try to call a function with a LOT of parameters that would cause the stack to meet the heap before such prevention mechanisms maybe were flagged? I don’t know the answers to these myself, so I don’t expect you to right now either haha! Food for thought I guess… and/or an IRC discussion hahaha… Look forward to seeing these series continue!! Thanks!


(oaktree) #8

@123loaded: I have a fifth tutorial now. Yes, I might get into stack overflows and whatnot eventually. This series was meant to teach people about how dynamic memory works.

Memory management in assembly, however, will not likely be covered in this (outside of reversing my C binaries). If you want, I could ask someone like @_py or @unh0lys0da if they would like to do a disassembling of malloc/free.

As far as the above goes, heap-allocated instances of structs are the most obvious way to limit the number of parameters passed to a function. Yet I will certainly have to research more on how limits are handled.


(oaktree) #9

This topic was automatically closed after 30 days. New replies are no longer allowed.