Lecture 10: Tuples and Memory Allocation

1 Tuples and Memory Allocation

1.1 Turtles all the way down?

• If we’re using ESI to store the memory address where our available heap space begins, where do we get its initial value from?

• main.c uses malloc (or calloc) to preallocate a large region of memory that we can use in our programs. But where does malloc know where available memory begins? We don’t pass malloc a starting address, so the start address isn’t on the stack. And we’ve accounted for the purposes of all the available registers, so it’s not hiding in a register (the way that we’re using ESI).

• The implementation of malloc stores several pointers that maintain a clever structure of free and allocated chunks of memory, divided among arenas of allocations of similar sizes. But where can those pointers live? They can’t be on the heap itself, since they help manage the heap!

• Instead, we need to store those pointers in some well-known, statically known location.

  Before, when introducing stacks, we had a simple memory-layout diagram that looked like this:

  

  This is a bit simplistic – particularly that “Global” section. What goes in there? Among other things, that section breaks down into smaller sections, with various purposes:

  • The .data section includes global constants known at compile-time

  • The .bss section includes global names whose values aren’t known (and so are initialized to zero)

  • The .tdata and .tbss sections are analogous to .data and .bss sections, but are thread-local

  Crucially, the addresses of these four sections are constant, determined by the linker when the executable is produced, and their sizes are known statically: they’re not part of the heap, and any variables stored within them are stored at predictable locations. So the implementation of malloc ultimately relies on a thread-local variable, stored in the .tbss section and initialized as part of the startup of the program before main() ever gets called, to hold the pointer to the first arena.

• Walking our way back up the list above: since the address of the pointer to the first arena is statically known, it doesn’t need to be passed in via a function parameter, or via a register; it’s now possible for malloc to correctly provide us with unique, newly-allocated regions of memory, which we can then use in our programs with impunity.