Segmented Stacks in LLVM

Introduction

Segmented stack allows stack space to be allocated incrementally than as amonolithic chunk (of some worst case size) at thread initialization. This isdone by allocating stack blocks (henceforth called stacklets) and linking theminto a doubly linked list. The function prologue is responsible for checking ifthe current stacklet has enough space for the function to execute; and if not,call into the libgcc runtime to allocate more stack space. Segmented stacks areenabled with the "split-stack" attribute on LLVM functions.

The runtime functionality is already there in libgcc.

Implementation Details

Allocating Stacklets

As mentioned above, the function prologue checks if the current stacklet hasenough space. The current approach is to use a slot in the TCB to store thecurrent stack limit (minus the amount of space needed to allocate a new block) -this slot’s offset is again dictated by libgcc. The generatedassembly looks like this on x86-64:

  leaq     -8(%rsp), %r10
  cmpq     %fs:112,  %r10
  jg       .LBB0_2
 
  # More stack space needs to be allocated
  movabsq  $8, %r10   # The amount of space needed
  movabsq  $0, %r11   # The total size of arguments passed on stack
  callq    __morestack
  ret                 # The reason for this extra return is explained below
.LBB0_2:
  # Usual prologue continues here

The size of function arguments on the stack needs to be passed to__morestack (this function is implemented in libgcc) since that numberof bytes has to be copied from the previous stacklet to the current one. This isso that SP (and FP) relative addressing of function arguments work as expected.

The unusual ret is needed to have the function which made a call tomorestack return correctly. morestack, instead of returning, callsinto .LBB0_2. This is possible since both, the size of the retinstruction and the PC of call to morestack are known. When the functionbody returns, control is transferred back to morestack. __morestackthen de-allocates the new stacklet, restores the correct SP value, and does asecond return, which returns control to the correct caller.

Variable Sized Allocas

The section on allocating stacklets automatically assumes that every stackframe will be of fixed size. However, LLVM allows the use of the llvm.allocaintrinsic to allocate dynamically sized blocks of memory on the stack. Whenfaced with such a variable-sized alloca, code is generated to:

• Check if the current stacklet has enough space. If yes, just bump the SP, likein the normal case.
• If not, generate a call to libgcc, which allocates the memory from theheap.

The memory allocated from the heap is linked into a list in the currentstacklet, and freed along with the same. This prevents a memory leak.