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