1 ======================== 2 Segmented Stacks in LLVM 3 ======================== 4 5 .. contents:: 6 :local: 7 8 Introduction 9 ============ 10 11 Segmented stack allows stack space to be allocated incrementally than as a 12 monolithic chunk (of some worst case size) at thread initialization. This is 13 done by allocating stack blocks (henceforth called *stacklets*) and linking them 14 into a doubly linked list. The function prologue is responsible for checking if 15 the current stacklet has enough space for the function to execute; and if not, 16 call into the libgcc runtime to allocate more stack space. Segmented stacks are 17 enabled with the ``"split-stack"`` attribute on LLVM functions. 18 19 The runtime functionality is `already there in libgcc 20 <http://gcc.gnu.org/wiki/SplitStacks>`_. 21 22 Implementation Details 23 ====================== 24 25 .. _allocating stacklets: 26 27 Allocating Stacklets 28 -------------------- 29 30 As mentioned above, the function prologue checks if the current stacklet has 31 enough space. The current approach is to use a slot in the TCB to store the 32 current stack limit (minus the amount of space needed to allocate a new block) - 33 this slot's offset is again dictated by ``libgcc``. The generated 34 assembly looks like this on x86-64: 35 36 .. code-block:: nasm 37 38 leaq -8(%rsp), %r10 39 cmpq %fs:112, %r10 40 jg .LBB0_2 41 42 # More stack space needs to be allocated 43 movabsq $8, %r10 # The amount of space needed 44 movabsq $0, %r11 # The total size of arguments passed on stack 45 callq __morestack 46 ret # The reason for this extra return is explained below 47 .LBB0_2: 48 # Usual prologue continues here 49 50 The size of function arguments on the stack needs to be passed to 51 ``__morestack`` (this function is implemented in ``libgcc``) since that number 52 of bytes has to be copied from the previous stacklet to the current one. This is 53 so that SP (and FP) relative addressing of function arguments work as expected. 54 55 The unusual ``ret`` is needed to have the function which made a call to 56 ``__morestack`` return correctly. ``__morestack``, instead of returning, calls 57 into ``.LBB0_2``. This is possible since both, the size of the ``ret`` 58 instruction and the PC of call to ``__morestack`` are known. When the function 59 body returns, control is transferred back to ``__morestack``. ``__morestack`` 60 then de-allocates the new stacklet, restores the correct SP value, and does a 61 second return, which returns control to the correct caller. 62 63 Variable Sized Allocas 64 ---------------------- 65 66 The section on `allocating stacklets`_ automatically assumes that every stack 67 frame will be of fixed size. However, LLVM allows the use of the ``llvm.alloca`` 68 intrinsic to allocate dynamically sized blocks of memory on the stack. When 69 faced with such a variable-sized alloca, code is generated to: 70 71 * Check if the current stacklet has enough space. If yes, just bump the SP, like 72 in the normal case. 73 * If not, generate a call to ``libgcc``, which allocates the memory from the 74 heap. 75 76 The memory allocated from the heap is linked into a list in the current 77 stacklet, and freed along with the same. This prevents a memory leak. 78
