Chris Capel <ch....@iba.nktech.net> wrote: > Are there extenuating circumstances where this is particularly hard? I can't > figure out how to make an infinitely recursing function in SBCL that > doesn't throw a control-stack-exhausted-error.
In current SBCL you should not be able to: stack overflow protection is implemented with a pair of protected pages at the end of the allocated stack space: sbcl-devel definitely wants to know if you manage to bypass that without first corrupting the image in some other way.
That said, the situation is _really_ slightly hairier. Try this on for size:
Chris Capel <ch....@iba.nktech.net> writes: > Wade Humeniuk wrote:
>> Chris Capel wrote: >>> Hi everyone,
>>> I'm interesting in defining a subset of Lisp that is safe in the sense >>> that any arbitrary code written in the subset can be executed without >>> fear of the code compromising the security of the system, or taking down >>> the lisp image (absent impl. bugs), or accessing certain protected >>> information in the lisp image, or hanging the lisp image in a tight loop, >>> or doing other malicious things. The code would have to be verified to >>> exist in that subset with a function that reads in the code from text >>> (with read-time evaluation disabled, of course) and returns whether it's >>> safe. Is it possible to define such a subset?
>> I think this problem is exactly equivalent to running any arbitrary >> Program within an Operating System. Even the best Operating Systems >> can get compromised by either oversight, malice or pure random >> chance (say a cosmic ray randomly mutating memory). The general >> problem is so hard that no OS can handle it fully. Perhaps you >> could narrow down your scope in what you specifically want to do?
> I'm not exactly sure the scope can be narrowed. What I'm planning on > using it for is a Terrarium-like[1] server process that communicates > with other servers over the internet automatically exchanging bits > of creature AI code and running them in a simulation.
But why do the creatures need to be implemented in full Common Lisp? Surely they don't need to open files, manipulate pathnames, or any of a number of other things.
> So I want to define a subset of CL that can be verified so that the > code that's exchanged can be guaranteed not to do bad things, but > can still be used to define a sophisticated and efficient creature > AI.
Hmmmm. So having taken a quick glance at the Terrarium stuff I think you're making your problem harder than the problem they solved--it sounds like they just scan the code for certain "operations" which are disallowed such as accessing the local disk or system registry. I didn't see anything that suggested the Terrarium environment protects itself from stack overflow, etc. I think you can get this level security by walking the tree of source code you get and looking for occurences of symbols that name bad operations. If you want to be slick you write a real tree walker that recognizes special operators and expands macros so you can tell if the suspect symbol is actually being used as the name of an operation. But more conservatively you just do a simple tree walk:
(Of course with this implementation you've got to worry about stack overflow while checking the code. ;-))
I'd be interested to know what Terrarium does about DOS attacks such as creatures that allocate tons of memory or try to overflow the stack. (The later is easier to deal with as long as the .NET runtime signals an appropriate exception--you just have to watch out that creature code can't touch shared objects that require mutual exclusion to be thread safe since a creature thread could obtain a lock on an object, temporarily violate its invariants, and then blow the stack, leaving that object in a corrupted state. Out of memory is harder since the final failure may affect an innocent thread that just happens to allocate memory at the wrong time.
In article <10ra64uqnhn6...@corp.supernews.com>, Chris Capel wrote:
> On the other hand, I'm probably not clear on what you mean by "compiler". > What does it involve? Something like Pascal was talking about, where you > simply wrap functions like
> (cl:defun cons (car cdr) > (cl:if (cl:< *allocated* +max-mem+) > (cl:cons car cdr) > (error "Too much memory")))
I'm not Pascal, but I think something like this would work for your purpose. Except that you couldn't track the allocated memory this way, because you wouldn't know when garbage collections occur. You could however limit the amount of consing (GC-ed or not) any user program is allowed to perform.
[...]
> and so on? If this is what you mean by compiler, then it's not much more > than I was talking about originally. Couldn't you simply re-export many of > CL's symbols?
It depends whether you a) trust the standard for requiring all the safety checks that matter to you, and b) the implementation for actually implementing these checks. If you don't, you would have to include these checks in your version of cons, +, etc.
THEN you have to trust that c) after the safety checks are passed your implementation doesn't produce buggy machine code.
Security is annoying :-)
Personally I would not let c) bother me, but would be mindful of a) and b).
> > (one more good reason to implement it above common-lisp).
> With an execution stack implemented entirely in CL (I think this is what > Pascal means), I don't see any other way than to completely rewrite every > function I want to include. Then I end up with some sort of > CL-to-lots-more-CL compiler that's not much faster than an interpreter. Is > this what you mean by implementing it above common lisp?
Strictly speaking, Pascal is right. But you could also limit the number of recursive calls at run time (insert the appropriate check in your version of DEFUN). You would still have to check what else your implementation uses the stack for.
> Thomas F. Burdick wrote: > > ... and you'll then have a > > tiny CL subset that is effectively protected from accessing the host > > CL.
> Would you call a subset that provided CL macros, lists, arrays, a lot of > CLOS, and all utility macros and functions "tiny"? At what point close to > "tiny" does including more functions dispreportionately increase the danger > of missing a security hole?
I don't think anybody knows for sure... Look at the OpenBSD guys. They set out specifically to produce a secure OS, and they still get holes every once in a while.
Consider this: even if you rewrite CL-on-top-of-CL, you can still introduce your own bugs. They wouldn't be related to the system stack or wild pointers, but they could allow, say, the user to access or modify objects that should be protected.
This being said, I think your project can come "close enough" to being secure. It may take more work than the rest of your anthill simulation, but it would have uses beyond that.
Actually I may need this for some other project. Would you like to work together on it?
1. Why not use the operating system facilities for limiting the amount of memory each process can use? That sounds easier to me than re-implementing and verifying a Common Lisp implementation to add such a feature.
2. The way that Java addresses this problem should be instructive.
Peter Seibel wrote: > Chris Capel <ch....@iba.nktech.net> writes:
>> Wade Humeniuk wrote:
>>> I think this problem is exactly equivalent to running any arbitrary >>> Program within an Operating System. Even the best Operating Systems >>> can get compromised by either oversight, malice or pure random >>> chance (say a cosmic ray randomly mutating memory). The general >>> problem is so hard that no OS can handle it fully. Perhaps you >>> could narrow down your scope in what you specifically want to do?
>> I'm not exactly sure the scope can be narrowed. What I'm planning on >> using it for is a Terrarium-like[1] server process that communicates >> with other servers over the internet automatically exchanging bits >> of creature AI code and running them in a simulation.
> But why do the creatures need to be implemented in full Common Lisp? > Surely they don't need to open files, manipulate pathnames, or any of > a number of other things.
No, not at all. But pathname and package functions are just two really big holes. Once I've filled in all the big holes, there might be smaller ones.
>> So I want to define a subset of CL that can be verified so that the >> code that's exchanged can be guaranteed not to do bad things, but >> can still be used to define a sophisticated and efficient creature >> AI.
> Hmmmm. So having taken a quick glance at the Terrarium stuff I think > you're making your problem harder than the problem they solved--it > sounds like they just scan the code for certain "operations" which are > disallowed such as accessing the local disk or system registry. I > didn't see anything that suggested the Terrarium environment protects > itself from stack overflow, etc.
The .NET runtime environment provides these guarantees. It's pretty complicated, I understand. Full type safety, for one. Also, it assigns different parts of the standard library to different permission groups, and any given code can be executed with a reduced set of permissions based on just about any kind of policy. Two assemblies (.dll's) that call each other back and forth can run under two different permission sets, etc. etc.
I'm pretty sure it guarantees that no code that doesn't call out into foreign functions can crash the runtime. Of course, if an application runs out of memory, it's going down. But if a sub-process causes everything to run out of memory, the parent can handle the OutOfMemoryException (called when memory is low, I believe) and terminate some threads and free resources so a GC can reclaim it all.
I was running a Terrarium server for a few months way back when it first started. I never had it crash, or heard anything about there being successful malware-creatures.
> (Of course with this implementation you've got to worry about stack > overflow while checking the code. ;-))
Hehe. Good point.
> I'd be interested to know what Terrarium does about DOS attacks such > as creatures that allocate tons of memory or try to overflow the > stack.
Terrarium's only safety features that aren't provided by the runtime itself were cutting off a creature's processing after a certain amount of time (2 to 5 ms). I could be wrong on this, of course.
> (The later is easier to deal with as long as the .NET runtime > signals an appropriate exception--you just have to watch out that > creature code can't touch shared objects that require mutual exclusion > to be thread safe since a creature thread could obtain a lock on an > object, temporarily violate its invariants, and then blow the stack, > leaving that object in a corrupted state. Out of memory is harder > since the final failure may affect an innocent thread that just > happens to allocate memory at the wrong time.
This is an interesting issue that I'm not sure about the answer to.
Eric Daniel wrote: > In article <10ra64uqnhn6...@corp.supernews.com>, Chris Capel wrote:
>> On the other hand, I'm probably not clear on what you mean by >> "compiler". What does it involve? Something like Pascal was talking >> about, where you simply wrap functions like
>> (cl:defun cons (car cdr) >> (cl:if (cl:< *allocated* +max-mem+) >> (cl:cons car cdr) >> (error "Too much memory")))
> I'm not Pascal, but I think something like this would work for your > purpose. Except that you couldn't track the allocated memory this way, > because you wouldn't know when garbage collections occur. You could > however limit the amount of consing (GC-ed or not) any user program is > allowed to perform.
That gives me another idea. Given that we restrict the safety package to running on implementations with real threads and with total-allocated-memory type counters, and given that only one sandboxed process is run at a time, it'd be possible to run a loop in a high-priority thread that checks to make sure that the sandboxed code (a) hasn't run for too long and (b) hasn't allocated more than X bytes, and even to keep up with the total number of bytes allocated by that process and set a limit on that. If it runs every five thousand cycles, there's not much a process can do in that time.
>> > (one more good reason to implement it above common-lisp).
>> With an execution stack implemented entirely in CL (I think this is what >> Pascal means), I don't see any other way than to completely rewrite >> every function I want to include. Then I end up with some sort of >> CL-to-lots-more-CL compiler that's not much faster than an interpreter. >> Is this what you mean by implementing it above common lisp?
> Strictly speaking, Pascal is right.
Right that this is the only way to portably protect and limit the execution stack?
In any case, I don't think this is feasible. You end up using the host lisp process as a virtual machine in which to implement a child lisp! CL wasn't designed to be a VM!
> This being said, I think your project can come "close enough" to being > secure. It may take more work than the rest of your anthill simulation, > but it would have uses beyond that.
That's what I was thinking.
> Actually I may need this for some other project. Would you like to work > together on it?
I think I might get some first steps published in a Arch archive pretty soon now. But I really wanted to get a basic simulation up and going first. After I get the simulator itself down, which shouldn't be too terribly hard, I'd be happy to collaborate.
In article <10rd49cecao1...@corp.supernews.com>, Chris Capel wrote:
> Right that this is the only way to portably protect and limit the execution > stack?
As far as I know: 1) there may be implementation-dependent way to know the current size of the stack (e.g ROOM on CMUCL)
2) it doesn't guarantee safety, because what is needed is to predict that an operation (function call, etc.) is about to blow the stack before it happens!
So yes, for full portability you need to rool out your own call stack. I'm not 100% sure how to do it. A good start would probably be Chapter 20 on Graham's /On Lisp/ (Continuations). That is, you would perform a slightly complicated transformation on the user-provided code, and compile the resulting Lisp code. This is, by the way, a testament to the power of Lisp. I wouldn't even consider doing it in any other language.
* Chris Capel wrote: > I'm interesting in defining a subset of Lisp that is safe in the sense that > any arbitrary code written in the subset can be executed without fear of > the code compromising the security of the system, or taking down the lisp > image (absent impl. bugs), or accessing certain protected information in > the lisp image, or hanging the lisp image in a tight loop, or doing other > malicious things. The code would have to be verified to exist in that > subset with a function that reads in the code from text (with read-time > evaluation disabled, of course) and returns whether it's safe. Is it > possible to define such a subset?
I looked at doing this for CL subsets. My conclusion was that (a) in practice it is probably doable in a mildly implementation-dependent way by controlling the subset of symbols you allow (you need to rely on the implementation catching stack overflows, being able to kill threads in tight loops and so on), and (b) if you want it done *properly* you need a language & runtime designed with safety in mind from the ground up, which CL obviously was not.
Java was intended to satisfy (b) I think, but even then there are issues both with what you need to do and just plain bugs as far as I can tell (I've never looked at Java's security stuff).
If I was doing this now I'd use one of the `container' facilities offered by various systems as well - *BSD jails or Solaris containers or something.
Tim Bradshaw <t...@cley.com> writes: > * Chris Capel wrote: > > I'm interesting in defining a subset of Lisp that is safe in the sense that > > any arbitrary code written in the subset can be executed without fear of > > the code compromising the security of the system, or taking down the lisp > > image (absent impl. bugs), or accessing certain protected information in > > the lisp image, or hanging the lisp image in a tight loop, or doing other > > malicious things. The code would have to be verified to exist in that > > subset with a function that reads in the code from text (with read-time > > evaluation disabled, of course) and returns whether it's safe. Is it > > possible to define such a subset?
> I looked at doing this for CL subsets. My conclusion was that (a) in > practice it is probably doable in a mildly implementation-dependent > way by controlling the subset of symbols you allow (you need to rely > on the implementation catching stack overflows, being able to kill > threads in tight loops and so on), and (b) if you want it done > *properly* you need a language & runtime designed with safety in mind > from the ground up, which CL obviously was not.
> Java was intended to satisfy (b) I think, but even then there are > issues both with what you need to do and just plain bugs as far as I > can tell (I've never looked at Java's security stuff).
> If I was doing this now I'd use one of the `container' facilities > offered by various systems as well - *BSD jails or Solaris containers > or something.
For a small example of (a), see my following implementation of AIM-8 lisp in Common-Lisp (and in AIM-8 lisp). You don't need any implementation-dependent stuff to control stack overflow, if the underlying implementation is safe in this respect, just a strategically placed HANDLER-CASE. Only for timeout an implementation specific API should be used: WITH-TIMEOUT is provided in the non-standard PROCESS package.
;;************************************************************************* *** ;;FILE: aim-8.lisp ;;LANGUAGE: Common-Lisp ;;SYSTEM: Common-Lisp ;;USER-INTERFACE: NONE ;;DESCRIPTION ;; ;; Implements the LISP described in AIM-8 in Common-Lisp. ;; Usage: (load "aim-8.lisp") ;; (aim-8:repl) ;; Then at the aim-8 prompt, you have LISP, plus: ;; (DEFINE name sexp) corresponding to = ;; (RELOAD) to reload aim-8 if you edit it. ;; (DUMP-ENVIRONMENT) to dump the defined symbols. ;; (LOAD "path") to load an aim-8 source. Try "aim-8.aim-8". ;; ;;AUTHORS ;; <PJB> Pascal Bourguignon <p...@informatimago.com> ;;MODIFICATIONS ;; 2004-10-24 <PJB> Created. ;;BUGS ;;LEGAL ;; GPL ;; ;; Copyright Pascal Bourguignon 2004 - 2004 ;; ;; This program is free software; you can redistribute it and/or ;; modify it under the terms of the GNU General Public License ;; as published by the Free Software Foundation; either version ;; 2 of the License, or (at your option) any later version. ;; ;; This program is distributed in the hope that it will be ;; useful, but WITHOUT ANY WARRANTY; without even the implied ;; warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR ;; PURPOSE. See the GNU General Public License for more details. ;; ;; You should have received a copy of the GNU General Public ;; License along with this program; if not, write to the Free ;; Software Foundation, Inc., 59 Temple Place, Suite 330, ;; Boston, MA 02111-1307 USA ;;************************************************************************* *** ;; ;; AIM-8 -- 23 MARCH 1959 -- J. MCCARTHY
(DEFPACKAGE "AIM-8" (:USE "COMMON-LISP") (:EXPORT "REPL") (:DOCUMENTATION "Implements the lisp of AIM-8 -- 23 MARCH 1959 -- J. McCarthy"));;AIM-8 (IN-PACKAGE "AIM-8")
(DEFINE NIL ()) (DEFINE F ()) (DEFINE T T) (DEFINE AND (LAMBDA (A B) (COND (A (COND (B T) (T NIL))) (T NIL)))) (DEFINE OR (LAMBDA (A B) (COND (A T) (B T) (T NIL)))) (DEFINE NOT (LAMBDA (A) (COND (A NIL) (T NIL)))) (DEFINE MAPLIST (LAMBDA (X F) (COND ((NULL X) NIL) (T (COMBINE (F X) (MAPLIST (REST X) F)))))) (DEFINE SUBST (LAMBDA (X Y A) (COND ((NULL A) NIL) ((ATOM A) (COND ((EQ Y A) X) (T A))) (T (COMBINE (SUBST X Y (FIRST A)) (SUBST X Y (REST A)))) )));;SUBST
(DEFUN %SUBST (X Y A) (COND ((NULL A) NIL) ((ATOM A) (COND ((EQ Y A) X) (T A))) (T (CONS (%SUBST X Y (FIRST A)) (%SUBST X Y (REST A))))))
(DEFUN %SUBSQ (X Y Z) (COND ((NULL Z) NIL) ((ATOM Z) (COND ((EQ Y Z) X) (T Z))) ((EQ (FIRST Z) 'QUOTE) Z) (T (CONS (%SUBSQ X Y (FIRST Z)) (%SUBSQ X Y (REST Z))))));;%SUBSQ
;; -*- mode: Lisp -*- ;;************************************************************************* *** ;;FILE: aim-8.aim-8 ;;LANGUAGE: AIM-8 LISP ;;SYSTEM: AIM-8 LISP ;;USER-INTERFACE: NONE ;;DESCRIPTION ;; ;; Implements the LISP described in AIM-8 in AIM-8 LISP ;; Usage: At the AIM-8> prompt: ;; (LOAD (QUOTE "aim-8.aim-8")) ;; (REPL) ;; The AIM-8 evaluation algorithm is pure substitution, no binding! ;; Therefore (read) is called every time it's _used_: ;; you need to enter the same sexp several times to get it processed! ;; ;; (EVAL (QUOTE (FF1 (QUOTE ((())()()((A)B C))))) ;; (QUOTE ((FF1 LAMBDA (X) (COND ((OR (NULL X) (ATOM X)) X) ;; (T (COND ((FF1 (FIRST X)) (FF1 (FIRST X))) ;; (T (FF1 (REST X))))))))) ;; Note: Since this implements an substitution interpreter on an interpreter ;; on a lisp system, it usually quite slow to compute the result of non ;; trivial functions. ;; ;;AUTHORS ;;
Chris Capel <ch....@iba.nktech.net> writes: > Right that this is the only way to portably protect and limit the execution > stack?
> In any case, I don't think this is feasible. You end up using the host lisp > process as a virtual machine in which to implement a child lisp! CL wasn't > designed to be a VM!
Ah but you should not underestimate the power of virtual machines.
Common-Lisp is a general language, you can use it to implement a virtual machine. It's even easy and fast to do. (Writting it in Modula-2 could give a faster VM, but it would be harder and slower to implement).
Now, the killer feature of Common-Lisp for virtual machines is JIT: once you've got a sequence a VM instructions, you can build a Common-Lisp function from the VM microcode and compile it, which would produce an optimized native code for the original function.
Since you can do this with a page or two of Common-Lisp code, and could not do this with less than a lot more of C (even if you tried to system("gcc ...") and dlopen("lib...")). Well, if it was so simple in C, Apple would have delivered Xcode ten years ago.
-- __Pascal Bourguignon__ http://www.informatimago.com/ The world will now reboot; don't bother saving your artefacts.
* Pascal Bourguignon wrote: > For a small example of (a), see my following implementation of AIM-8 > lisp in Common-Lisp (and in AIM-8 lisp). You don't need any > implementation-dependent stuff to control stack overflow, if the > underlying implementation is safe in this respect, just a > strategically placed HANDLER-CASE.
That's what I meant by `mildly implementation-dependent': you need to know that the implementation is safe. In particular the code should refuse to run on one that is not.
> >> I don't think, for what I'm going to use it for, implementing CL entirely > >> on top of CL will be efficient enough without going all the way. The > >> executed code needs to run rather quickly. And that sounds like a lot of > >> work! I was hoping it would be easier than that.
> > A simple CL->CL compiler isn't that much work,
> It doesn't comfort me that much that Thomas Burdick thinks a CL->CL compiler > wouldn't be that much work. :-)
> On the other hand, I'm probably not clear on what you mean by "compiler".
I mean a program that takes input in the form of s-expressions, views that input as the source code to a CL-safe program, and produces an equivalent CL program. You can then compile that CL code with the host compiler. The guts of it might look something like this:
(defun compile-form (form env) (let ((form (macroexpand form env))) (cond ((symbolp form) (if (forbidden-symbol-p form) (error "Access to this symbol is forbidden: ~S" form) form)) ((not (listp form)) (if (forbidden-object-p form) (error "Access to this object is forbidden: ~S" form) form)) ((special-operator-p (first form)) (ecase (first form) (quote (if (forbidden-object-p (second form)) (error "You get the idea.") `(quote ,(second form)))) (unwind-protect (destructuring-bind (protected &rest cleanup) (rest form) `(unwind-protect ,(compile-form protected env) ;; We want to be able to throw past user code if we're trying ;; to abort their execution. (unless *aborting* ,@(mapcar (lambda (x) (compile-form x env)) cleanup))))) ;; ... etc ... )) ((not (symbolp (first form))) (compile-form `(funcall #',(first form) ,@(rest form)) env)) ;; If we get here, we have a normal function call ((or (find-lexical-function (first form) env) (safe-function-p (first form))) (list* (first form) (mapcar (lambda (x) (compile-form x env)) (rest form)))) (t `(funcall (get-safe-fun ',(first form)) ,@(mapcar (lambda (x) (compile-form x env)) (rest form)))))))
I'm kind of fudging on the issue of lexical environments above, but if you reuse your implementation's lexical environments, you can do it like this. Also, you'll might want to check for the safety of macros before you expand them. Now you can compile CL-safe functions to CL:
(defun safe-eval (form) (let ((cl (compile-form form (make-null-environment)))) (eval cl)))
The functions SAFE-FUNCTION-P, FORBIDDEN-SYMBOL-P, and FORBIDDEN-OBJECT-P define the allowed subset, probably by looking things up in tables.
> Thomas F. Burdick wrote: > > ... and you'll then have a > > tiny CL subset that is effectively protected from accessing the host > > CL.
> Would you call a subset that provided CL macros, lists, arrays, a lot of > CLOS, and all utility macros and functions "tiny"? At what point close to > "tiny" does including more functions dispreportionately increase the danger > of missing a security hole?
I meant you'll have a tiny subset before you populate the tables used by SAFE-FUNCTION-P, etc. At first your CL-safe subset won't be able to call any functions except those it defines itself. So, no CONS, no LIST, no ERROR. Not all that useful, but the host Lisp is protected from it. Then you start exposing parts of the host Lisp, to make it useful, which is the hard part, not the compiler per se.
Oh, and in SBCL, I'd consider any access to CLOS unsafe, because PCL can really fuck itself up, breaking any CLOS-using code in the image.
Pascal Bourguignon wrote: > program you get informed immediately. For collisions between the > stack and the heap, it's more difficult. And in any case, you're back
All contemporary Unix systems have at least one unmapped page between the top of the "heap" and the bottom of the stack, and stack overflows are always caught. I bet that goes for Windows aswell.
Matthias Buelow <m...@mukappabeta.de> writes: > Pascal Bourguignon wrote: > > program you get informed immediately. For collisions between the > > stack and the heap, it's more difficult. And in any case, you're back
> All contemporary Unix systems have at least one unmapped page between > the top of the "heap" and the bottom of the stack, and stack overflows > are always caught. I bet that goes for Windows aswell.
That does not help much. Try: alloca(1024*1024*1024);
-- __Pascal Bourguignon__ http://www.informatimago.com/ The world will now reboot; don't bother saving your artefacts.
* Pascal Bourguignon wrote: > Tim Bradshaw <t...@cley.com> writes: >> Are you assuming some broken implementation of alloca which does not >> check? > What would you check exactly?
Tim Bradshaw <t...@cley.com> writes: > * Pascal Bourguignon wrote: > > Tim Bradshaw <t...@cley.com> writes:
> >> Are you assuming some broken implementation of alloca which does not > >> check?
> > What would you check exactly?
> that it hasn't overflowed the stack.
So it would have to browse a table of mapped pages, the current value of sbrk(), to identify the heap zones and the other stacks (eg. in case of multithreading), and to check whether the stack pointer would cross any heap zone or other stack. That would quite defeat the purpose of alloca which is to get a fast allocation on stack. I don't think many do.
-- __Pascal Bourguignon__ http://www.informatimago.com/ The world will now reboot; don't bother saving your artefacts.
* Pascal Bourguignon wrote: > So it would have to browse a table of mapped pages, the current value > of sbrk(), to identify the heap zones and the other stacks (eg. in > case of multithreading), and to check whether the stack pointer would > cross any heap zone or other stack. That would quite defeat the > purpose of alloca which is to get a fast allocation on stack. I don't > think many do.
Um. No, of course it wouldn't. It just needs to do a single bound check (`am I trying to allocate beyond the end of the heap'). If that fails it might have to do something complicated, but more likely just return failure.
Tim Bradshaw <t...@cley.com> writes: > * Pascal Bourguignon wrote:
> > So it would have to browse a table of mapped pages, the current value > > of sbrk(), to identify the heap zones and the other stacks (eg. in > > case of multithreading), and to check whether the stack pointer would > > cross any heap zone or other stack. That would quite defeat the > > purpose of alloca which is to get a fast allocation on stack. I don't > > think many do.
> Um. No, of course it wouldn't. It just needs to do a single bound > check (`am I trying to allocate beyond the end of the heap'). If that > fails it might have to do something complicated, but more likely just > return failure.
The limit is dependent on the stack (there are several stacks with multithreading) and varies each time you call mmap, shmat, sbrk, etc. If you allow FFI and foreign libraries, you cannot count on them to update the stack limit table, so you'll have to scan more than what is done currently. You'd have the choice between doing it at alloca time or whenever a FFI returns, with perhaps some more optimization depending on the actual stack you're on, but this is not something that's done by alloca(3).
-- __Pascal Bourguignon__ http://www.informatimago.com/ The world will now reboot; don't bother saving your artefacts.
* Pascal Bourguignon wrote: > The limit is dependent on the stack (there are several stacks with > multithreading) and varies each time you call mmap, shmat, sbrk, etc. > If you allow FFI and foreign libraries, you cannot count on them to > update the stack limit table, so you'll have to scan more than what is > done currently. You'd have the choice between doing it at alloca time > or whenever a FFI returns, with perhaps some more optimization > depending on the actual stack you're on, but this is not something > that's done by alloca(3).
So, how do all the systems which treat stack pages specially (no execute perm for instance) do it? Let's see... they know the bounds of the stack. All the time.
