llvm dev - Jan 2014 - [LLVMdev] Position-independent stacks

Hi,
I am toying with an idea of having LLVM generate code that has
position-independent stacks.   This would be a very useful property for
implementing all sorts of micro-thread libraries (I am thinking something
similar to Python greenlets <http://stackoverflow.com/a/17447308>),
because
you'd be able to easily save threadlet state from one OS thread and later
restore it into another.

On the surface, it seems entirely do-able - basically, one needs to get rid
of all the things that point into the stack.  It should be sufficient to:
1. write a function pass that finds all local variables, whose address is
ever taken, and hoists them into a heap-allocated secondary "stack
frame",
2. either turn off frame base pointers, or make sure they are adjusted
after the stack had been relocated,
3. ... can't think of anything else, actually.

What do you guys think?  Any reasons this approach wouldn't fly?

Vadim
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140122/d80a2028/attachment.html>

On 22 January 2014 22:10, Vadim <vadimcn at gmail.com> wrote:
> Hi,
> I am toying with an idea of having LLVM generate code that has
> position-independent stacks.   This would be a very useful property for
> implementing all sorts of micro-thread libraries (I am thinking something
> similar to Python greenlets <http://stackoverflow.com/a/17447308>),
> because you'd be able to easily save threadlet state from one OS thread
and
> later restore it into another.
>
> On the surface, it seems entirely do-able - basically, one needs to get
> rid of all the things that point into the stack.  It should be sufficient
> to:
> 1. write a function pass that finds all local variables, whose address is
> ever taken, and hoists them into a heap-allocated secondary "stack
frame",
> 2. either turn off frame base pointers, or make sure they are adjusted
> after the stack had been relocated,
> 3. ... can't think of anything else, actually.
>
> What do you guys think?  Any reasons this approach wouldn't fly?
>
I've implemented something similar, but with the motivation of implementing
SFI sandboxing rather than making the stack relocatable.

The code is here: https://codereview.chromium.org/29743003/  In particular,
see the ExpandAlloca pass.

That code implements sandboxing at the level of LLVM IR.  It restricts all
memory accesses to a range of address space by truncating the memory
address and adding a base pointer.  Here are some notes explaining further:

https://docs.google.com/presentation/d/1RD3bxsBfTZOIfrlq7HzGMsygPHgb61A1eTdelIYOurs/edit

Cheers,
Mark
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140123/4b40bf6e/attachment.html>

Thanks Mark!  That'd be a useful starting point.


For the rest of the people here: to be a bit more specific, I am having
doubts about the following:
- Can later optimization passes or code generation still create machine
code that takes and stores (in a register perhaps) an address of something
on the stack, even if not semantically visible to the programmer?   Can
this somehow be detected?
- Can frame pointers be disabled on all architectures?  If not, is the
frame pointer chain always walkable?
- Can frame pointers be disabled on a per-function basis?  (this is in case
not the whole program's stacks need to be made relocatable).

Vadim



On Thu, Jan 23, 2014 at 8:22 AM, Mark Seaborn <mseaborn at chromium.org>
wrote:
> On 22 January 2014 22:10, Vadim <vadimcn at gmail.com> wrote:
>
>> Hi,
>> I am toying with an idea of having LLVM generate code that has
>> position-independent stacks.   This would be a very useful property for
>> implementing all sorts of micro-thread libraries (I am thinking
something
>> similar to Python greenlets
<http://stackoverflow.com/a/17447308>),
>> because you'd be able to easily save threadlet state from one OS
thread and
>> later restore it into another.
>>
>> On the surface, it seems entirely do-able - basically, one needs to get
>> rid of all the things that point into the stack.  It should be
sufficient
>> to:
>> 1. write a function pass that finds all local variables, whose address
is
>> ever taken, and hoists them into a heap-allocated secondary "stack
frame",
>> 2. either turn off frame base pointers, or make sure they are adjusted
>> after the stack had been relocated,
>> 3. ... can't think of anything else, actually.
>>
>> What do you guys think?  Any reasons this approach wouldn't fly?
>>
>
> I've implemented something similar, but with the motivation of
> implementing SFI sandboxing rather than making the stack relocatable.
>
> The code is here: https://codereview.chromium.org/29743003/  In
> particular, see the ExpandAlloca pass.
>
> That code implements sandboxing at the level of LLVM IR.  It restricts all
> memory accesses to a range of address space by truncating the memory
> address and adding a base pointer.  Here are some notes explaining further:
>
>
https://docs.google.com/presentation/d/1RD3bxsBfTZOIfrlq7HzGMsygPHgb61A1eTdelIYOurs/edit
>
> Cheers,
> Mark
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140123/792040e9/attachment.html>