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

Mika Nystrom mika at async.caltech.edu
Thu Feb 24 03:20:29 CET 2011


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
>
>
>
>
>
>



More information about the M3devel mailing list