On Fri, Aug 1, 2014 at 11:12 PM, Philip Reames <listmail at philipreames.com> wrote:> Thanks for the explanation. I'm used to hearing the term "stack banging" > used for this mechanism, but I understand your objective. > > I believe having a general mechanism here would be valuable, but only if > the implementation doesn't make assumptions about runtime environment. For > example, let's say my runtime uses a three page guard region and considers > anything in that region to be a stack expansion. This should work with > your attribute. > > There's also different ways of implementing this. Depending on your > runtime, you might want to a) call a function, b) emit some special loads. > There's also numerous optimizations which apply for the later > implementation choice. >> Worth noting is that stack banging only when the stack size is larger than > a page size is NOT sufficient unless you can *prove* that every smaller > frame actually reads or writes to the frame before calling a subroutine. > > As an example, consider the following recursive function: > int test(int i) { char buff[50]; if( i == 0 ) return 0; else return > test(i-1); } > > The arguments will be passed in registers. The buffer won't be > initialized (assuming it's not compiled away), and you'll push a stack > frame without touching the stack memory. >I don't think that will happen unless there's a separate call stack. Either the call instruction itself will write to the stack or it will be tail recursive call and the stack will be reused.> > > It would be nice if your attribute could also represent an explicit > conditional check implementation as well. >The "split-stack" attribute can be used for that, and that's what Rust currently does.> > > Also, are you expecting the runtime to be able to throw an exception at > the site of the check? If so, there's a bunch of other issues which need > handled. > > > Straw man ideas: > - Start with an string attribute, work out the semantics and > implementation, then propose a "real attribute" once we've settled on a > workable implementation. >I seemed to have read that string attributes were for platform specific things, would that be incorrect?> - Pick a more generic name. Possibly "StackOverflowGuard"? > - Use two parameters. First, "minimum guard region size" (non-negative > integer number of bytes). Second, "test mechanism" (enum (FuncCall, Load, > Store, ConditionalCheck)). For the conditional check version, you'd need a > way to specify a failure handler. For the func call version, you need a > way to set the routine. > > > Now, I realize this is well beyond what you originally wanted to > implement. If you wanted to make the minimum change you could to support > forcing the enable of the existing stack probe mechanism, we can discuss > specifically that. I'd lean away from a general attribute for that > purpose, but am open to being convinced otherwise. :) >I think this should be limited to only lightweight stack probing, which either emits probe instructions or calls a function (provided by libgcc/compiler-rt) which does exactly the same. One extension I'm open for is to always force a probe which ensures the stack overflow happens in a well defined point in the prologue. That could be used for languages which can recover from stack overflows.> > Philip > > > > On 07/31/2014 07:27 PM, John Kåre Alsaker wrote: > > The point of this is to cheaply detect all stack overflows using a guard > page. For a guard page to actually detect all stack overflows, we need to > ensure that the code touches each page of the stack in the right order, > otherwise it could skip the guard page and write outside the stack. That is > very bad for languages such as Rust which provides memory safety, so it > currently does an explicit comparison against the end of the stack for each > function, which is again bad for performance. This would correspond to > GCC's -fstack-check (if that worked). > > > On Thu, Jul 31, 2014 at 6:40 PM, Philip Reames <listmail at philipreames.com> > wrote: > >> Giving a bit of background and motivation would be good here. What are >> you trying to accomplish and why? >> >> Philip >> >> >> On 07/28/2014 04:16 PM, John Kåre Alsaker wrote: >> >> Hi, I want to add a stack probe function attribute which would insert >> stack probes on all platforms, not just Windows. This will be useful for >> Rust since it must guarantee that the stack can't overflow, which it >> currently abuses the segmented stack support for. I'm not sure which kind >> of attribute is appropriate here. It must be added to the caller when >> inlined and clients of LLVM should be able to tell if code generation >> supports it. I would like some tips on how to implement this. >> >> >> _______________________________________________ >> LLVM Developers mailing listLLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.eduhttp://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >> >> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140802/7978d906/attachment.html>
On 08/01/2014 05:38 PM, John Kåre Alsaker wrote:> On Fri, Aug 1, 2014 at 11:12 PM, Philip Reames > <listmail at philipreames.com <mailto:listmail at philipreames.com>> wrote: > > Thanks for the explanation. I'm used to hearing the term "stack > banging" used for this mechanism, but I understand your objective. > > I believe having a general mechanism here would be valuable, but > only if the implementation doesn't make assumptions about runtime > environment. For example, let's say my runtime uses a three page > guard region and considers anything in that region to be a stack > expansion. This should work with your attribute. > > There's also different ways of implementing this. Depending on > your runtime, you might want to a) call a function, b) emit some > special loads. There's also numerous optimizations which apply > for the later implementation choice. > > > Worth noting is that stack banging only when the stack size is > larger than a page size is NOT sufficient unless you can *prove* > that every smaller frame actually reads or writes to the frame > before calling a subroutine. > > As an example, consider the following recursive function: > int test(int i) { char buff[50]; if( i == 0 ) return 0; else > return test(i-1); } > > The arguments will be passed in registers. The buffer won't be > initialized (assuming it's not compiled away), and you'll push a > stack frame without touching the stack memory. > > I don't think that will happen unless there's a separate call stack. > Either the call instruction itself will write to the stack or it will > be tail recursive call and the stack will be reused.Er, yeah. Please ignore my momentary stupidity. You're entirely correct.> > > > It would be nice if your attribute could also represent an > explicit conditional check implementation as well. > > The "split-stack" attribute can be used for that, and that's what Rust > currently does.Interesting. I did not know this. Using it for that purpose honestly feels like a bit of a hack. I'd rather factor the stack bounds checking and the handling separately. Looking around, it looks like we also have an Erlang specific implementation which does essentially the same thing. Yuck. Not saying we need to actually do so, just that I'd prefer that design in an ideal world. :)> > > > Also, are you expecting the runtime to be able to throw an > exception at the site of the check? If so, there's a bunch of > other issues which need handled. > > > Straw man ideas: > - Start with an string attribute, work out the semantics and > implementation, then propose a "real attribute" once we've settled > on a workable implementation. > > I seemed to have read that string attributes were for platform > specific things, would that be incorrect?Generally, they're either a) platform specific, and b) prototyping something. t.m.k. there is nothing that says a string attribute can't be used long term, but generally, they don't seem to be.> - Pick a more generic name. Possibly "StackOverflowGuard"? > - Use two parameters. First, "minimum guard region size" > (non-negative integer number of bytes). Second, "test mechanism" > (enum (FuncCall, Load, Store, ConditionalCheck)). For the > conditional check version, you'd need a way to specify a failure > handler. For the func call version, you need a way to set the > routine. > > > Now, I realize this is well beyond what you originally wanted to > implement. If you wanted to make the minimum change you could to > support forcing the enable of the existing stack probe mechanism, > we can discuss specifically that. I'd lean away from a general > attribute for that purpose, but am open to being convinced > otherwise. :) > > I think this should be limited to only lightweight stack probing, > which either emits probe instructions or calls a function (provided by > libgcc/compiler-rt) which does exactly the same.Given what you said about split-stack, I'm okay with this. The general cleanup is a worthwhile, but separate task.> One extension I'm open for is to always force a probe which ensures > the stack overflow happens in a well defined point in the prologue. > That could be used for languages which can recover from stack overflows.This would need to be carefully specified. Going back to your original proposal. I've come around to accepting the idea of adding a stack-probe attribute, but I'll request you improve the documentation some. In particular, mention the split-stack case, and mention that the called function is platform specific. I still think a better factored design is possibly, but you didn't create the mess we have, so I can't really expect you to fix it. :) I'll add a couple of more detailed code comments on the review thread as well.> > > > Philip > > > > On 07/31/2014 07:27 PM, John Kåre Alsaker wrote: >> The point of this is to cheaply detect all stack overflows using >> a guard page. For a guard page to actually detect all stack >> overflows, we need to ensure that the code touches each page of >> the stack in the right order, otherwise it could skip the guard >> page and write outside the stack. That is very bad for languages >> such as Rust which provides memory safety, so it currently does >> an explicit comparison against the end of the stack for each >> function, which is again bad for performance. This would >> correspond to GCC's -fstack-check (if that worked). >> >> >> On Thu, Jul 31, 2014 at 6:40 PM, Philip Reames >> <listmail at philipreames.com <mailto:listmail at philipreames.com>> wrote: >> >> Giving a bit of background and motivation would be good >> here. What are you trying to accomplish and why? >> >> Philip >> >> >> On 07/28/2014 04:16 PM, John Kåre Alsaker wrote: >>> Hi, I want to add a stack probe function attribute which >>> would insert stack probes on all platforms, not just >>> Windows. This will be useful for Rust since it must >>> guarantee that the stack can't overflow, which it currently >>> abuses the segmented stack support for. I'm not sure which >>> kind of attribute is appropriate here. It must be added to >>> the caller when inlined and clients of LLVM should be able >>> to tell if code generation supports it. I would like some >>> tips on how to implement this. >>> >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> http://llvm.cs.uiuc.edu >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140804/79809c87/attachment.html>
Would the __probestack functions be a suitable addition to compiler-rt? Does it already have __chkstk or is that provided by something else on Windows? I noticed that libgcc implemented them in cygwin.S. On Mon, Aug 4, 2014 at 9:08 PM, Philip Reames <listmail at philipreames.com> wrote:> > On 08/01/2014 05:38 PM, John Kåre Alsaker wrote: > > On Fri, Aug 1, 2014 at 11:12 PM, Philip Reames <listmail at philipreames.com > > wrote: > >> Thanks for the explanation. I'm used to hearing the term "stack >> banging" used for this mechanism, but I understand your objective. >> >> I believe having a general mechanism here would be valuable, but only if >> the implementation doesn't make assumptions about runtime environment. For >> example, let's say my runtime uses a three page guard region and considers >> anything in that region to be a stack expansion. This should work with >> your attribute. >> >> There's also different ways of implementing this. Depending on your >> runtime, you might want to a) call a function, b) emit some special loads. >> There's also numerous optimizations which apply for the later >> implementation choice. >> > >> Worth noting is that stack banging only when the stack size is larger >> than a page size is NOT sufficient unless you can *prove* that every >> smaller frame actually reads or writes to the frame before calling a >> subroutine. >> >> As an example, consider the following recursive function: >> int test(int i) { char buff[50]; if( i == 0 ) return 0; else return >> test(i-1); } >> >> The arguments will be passed in registers. The buffer won't be >> initialized (assuming it's not compiled away), and you'll push a stack >> frame without touching the stack memory. >> > I don't think that will happen unless there's a separate call stack. > Either the call instruction itself will write to the stack or it will be > tail recursive call and the stack will be reused. > > Er, yeah. Please ignore my momentary stupidity. You're entirely > correct. > > > >> >> >> It would be nice if your attribute could also represent an explicit >> conditional check implementation as well. >> > The "split-stack" attribute can be used for that, and that's what Rust > currently does. > > Interesting. I did not know this. Using it for that purpose honestly > feels like a bit of a hack. I'd rather factor the stack bounds checking > and the handling separately. > > Looking around, it looks like we also have an Erlang specific > implementation which does essentially the same thing. Yuck. > > Not saying we need to actually do so, just that I'd prefer that design in > an ideal world. :) > > > >> >> >> Also, are you expecting the runtime to be able to throw an exception at >> the site of the check? If so, there's a bunch of other issues which need >> handled. >> >> >> Straw man ideas: >> - Start with an string attribute, work out the semantics and >> implementation, then propose a "real attribute" once we've settled on a >> workable implementation. >> > I seemed to have read that string attributes were for platform specific > things, would that be incorrect? > > Generally, they're either a) platform specific, and b) prototyping > something. t.m.k. there is nothing that says a string attribute can't be > used long term, but generally, they don't seem to be. > > > > >> - Pick a more generic name. Possibly "StackOverflowGuard"? >> - Use two parameters. First, "minimum guard region size" (non-negative >> integer number of bytes). Second, "test mechanism" (enum (FuncCall, Load, >> Store, ConditionalCheck)). For the conditional check version, you'd need a >> way to specify a failure handler. For the func call version, you need a >> way to set the routine. >> >> >> Now, I realize this is well beyond what you originally wanted to >> implement. If you wanted to make the minimum change you could to support >> forcing the enable of the existing stack probe mechanism, we can discuss >> specifically that. I'd lean away from a general attribute for that >> purpose, but am open to being convinced otherwise. :) >> > I think this should be limited to only lightweight stack probing, which > either emits probe instructions or calls a function (provided by > libgcc/compiler-rt) which does exactly the same. > > Given what you said about split-stack, I'm okay with this. The general > cleanup is a worthwhile, but separate task. > > One extension I'm open for is to always force a probe which ensures the > stack overflow happens in a well defined point in the prologue. That could > be used for languages which can recover from stack overflows. > > This would need to be carefully specified. > > > Going back to your original proposal. I've come around to accepting the > idea of adding a stack-probe attribute, but I'll request you improve the > documentation some. In particular, mention the split-stack case, and > mention that the called function is platform specific. I still think a > better factored design is possibly, but you didn't create the mess we have, > so I can't really expect you to fix it. :) >Is there a place for documentation of string attributes, or should that just go in the commit messages?> > I'll add a couple of more detailed code comments on the review thread as > well. > > > > >> >> Philip >> >> >> >> On 07/31/2014 07:27 PM, John Kåre Alsaker wrote: >> >> The point of this is to cheaply detect all stack overflows using a guard >> page. For a guard page to actually detect all stack overflows, we need to >> ensure that the code touches each page of the stack in the right order, >> otherwise it could skip the guard page and write outside the stack. That is >> very bad for languages such as Rust which provides memory safety, so it >> currently does an explicit comparison against the end of the stack for each >> function, which is again bad for performance. This would correspond to >> GCC's -fstack-check (if that worked). >> >> >> On Thu, Jul 31, 2014 at 6:40 PM, Philip Reames <listmail at philipreames.com >> > wrote: >> >>> Giving a bit of background and motivation would be good here. What >>> are you trying to accomplish and why? >>> >>> Philip >>> >>> >>> On 07/28/2014 04:16 PM, John Kåre Alsaker wrote: >>> >>> Hi, I want to add a stack probe function attribute which would insert >>> stack probes on all platforms, not just Windows. This will be useful for >>> Rust since it must guarantee that the stack can't overflow, which it >>> currently abuses the segmented stack support for. I'm not sure which kind >>> of attribute is appropriate here. It must be added to the caller when >>> inlined and clients of LLVM should be able to tell if code generation >>> supports it. I would like some tips on how to implement this. >>> >>> >>> _______________________________________________ >>> LLVM Developers mailing listLLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.eduhttp://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>> >>> >>> >> >> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140805/093d24d1/attachment.html>