[M3devel] Avoding thread-stack overflow, proof of concept of "leapfrog stacks"

[Jay K]

 > But if user threads don't work (say Windows?) then it probably won't
 > work.  We do know, however, that user threads work just about everywhere.
 
 They don't. One could use fibers if one really wanted
 to do one's own scheduling, and locking.
 (user threads implies writing your own locks).
 
 
 On NT, alloca touches every page between the current
 and the result. (not every byte, that'd be wasteful,
 just every page) Touching the end of the stack generates
 stack overflow exceptions. So you can't go past it.
 That is, the very problem people were worried about,
 is solved on NT.
 
 
"Native exception handling" is what e.g. C++ uses.
I believe it validates the stack to be in range.
In particular, on NT, the stack range is available somewhere,
and occasionally used.


 - Jay

> To: jay.krell at cornell.edu
> Date: Wed, 23 Feb 2011 18:20:29 -0800
> From: mika at async.caltech.edu
> CC: m3devel at elegosoft.com
> Subject: Re: [M3devel] Avoding thread-stack overflow,	proof of concept of "leapfrog stacks"
> 
> Jay K writes:
> >--_6d651072-194c-4975-9e55-045a636fc1ed_
> >Content-Type: text/plain; charset="iso-8859-1"
> >Content-Transfer-Encoding: quoted-printable
> >
> >
> > > that alloca doesn't do any error checking
> >
> >
> >No. There is also native exception handling to consider.
> >NT essentially does error checking in both.
> 
> Native exception handling?  What do you mean?  
> 
> >
> >
> >> thousands=2C tens of thousands=2C millions of threads
> >
> > - 64bit address spaces
> > - multiple machines ("cloud")
> >=20
> >
> > > Won't work.  alloca releases memory at the }.
> >=20
> >=20
> > Only sort of.
> > You can still return that point and still use the memory.
> > You do risk=2C e.g. if you make any function calls=2C then the
> > alloca memory and the function parameters might overlap.
> > You could..platform-dependent..probably skip the first
> > "few" bytes of the alloca memory.
> 
> Well that's the whole point of the alloca, that it moves the stack
> pointer beyond the danger region...(and keeps it there till you return)
> if you let it come back ... it defeats the purpose.
> 
> >
> >
> > > Note that in my design=2C the stacks are all contiguous---but overlappin=
> >g!
> >=20
> > Are your stacks also traversing heap and what-not=2C
> > or are you just chopping up the current stack into lots
> > of smaller stacks?
> 
> 
> Yes traverses heap, protected pages, I/O buffers, text segments,... whatever
> junk is in between the old stack and the newly allocated area.
> 
> 
> >=20
> > i.e. alloca stack size times n and then create n threads?
> > That's less bad.
> >=20
> > I had the impression you were skipping over other memory.
> >=20
> > You know=2C like=2C malloc your stack=2C and then alloca to get
> > the stack pointer to hit the malloced memory.
> 
> That's exactly right.  malloc a new stack and use alloca to fiddle
> the stack pointer so it lands at the start of the new stack.
> 
> Now, I don't know a darn thing about Windows, but I've been looking at
> Unix code and I see the following:
> 
> * all alloca does is it modifies the stack pointer.  It does this from
>   user code without calling any sort of operating system or other runtime
>   routines.
> 
> * nothing special is done to "stacks" in Modula-3's "POSIX" user threading
>   library---threads are allocated with a NEW(UNTRACED REF...) using the
>   normal Modula-3 memory management routines.
> 
> * the concept of "stack" (another one of those EWD inventions,
>   incidentally) itself is a bit of a misnomer.  There is only the
>   stack pointer + conventions on how you use it.  The "stack" is simply
>   the area between where the thread began execution and the current
>   value of the stack pointer.  It's a matter of definition, simply.
> 
> >
> > > What would avoid it is generating the call to alloca in the front end.
> >=20
> >We could w/o much difficulty provide alloca in the frontend.
> >Probably limit it to unsafe modules.
> >At least to support your experimenting and somewhat platform-dependent code=
> >.
> 
> Sure that would be fun :)
> 
> >
> > > in the 1970s..
> >=20
> >=20
> >I think the right place to experiment with this stuff is at a lower level.
> >Or with more complete control of the system.
> >ie. in the kernel=2C or on only one specific kernel=2C that you
> >build/modify/write-from-scratch yourself.
> 
> Let me put it like this: if Modula-3's "user threads" work on
> architecture/OS combination X, I think you can just about (perhaps
> you can actually) prove that "leapfrog stacks" would work on the same
> architecture/OS combination, just based on an analysis of how the user
> threads allocate and use their stacks.  But if user threads don't work
> (say Windows?) then it probably won't work.  We do know, however, that
> user threads work just about everywhere...
> 
>      Mika
> 
> >
> >
> >Gotta go=2C
> > - Jay
> >
> >
> >
> >
> >
> >
 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20110224/8b5552b7/attachment-0002.html>