Implementing deep recursion in traditional Mac OS

[Joshua Juran]

Modern operating systems have demand-paged virtual memory, which is
used for, among other things, thread stacks. A thread might get 8MB
of virtual space allocated for its stack, of which just the first page
is backed by real memory, growing as needed one page at a time.

Traditional Mac OS, of course, doesn't have this. A process' stack
size is essentially fixed when it launches, as are thread stacks. A
typical default stack size for the Thread Manager is 32K; Lamp uses a
minimum of 64K. This is fine for most programs, but it prohibits deep
recursion.

I've come up with a solution for Lamp: Dynamically allocate and
switch to a new stack.

Since stacks grow down, the new custom stack objects have a footer
rather than a header, containing bookkeeping information and a
transition stack frame.

Define _lamp_stack_footer and declare _lamp_restack()
http://github.com/jjuran/metamage_1/blob/master/posix/compat/lamp/restack.h

The function _lamp_restack() is implemented in assembler. It takes as
parameters the total size of the function arguments, the function
address, and the arguments themselves. It calls _create_new_stack()
to allocate and partially initialize the new stack, then fills in the
return address and previous frame pointer.

Implement _lamp_restack() for 68K and PPC
http://github.com/jjuran/metamage_1/blob/master/lamp/Kerosene/Library/restack.68k.cc
http://github.com/jjuran/metamage_1/blob/master/lamp/Kerosene/Library/restack.ppc.cc

The _create_new_stack() function allocates memory for a new stack
(raising SIGSTKFLT if it fails) and links the new stack into the
global stack chain for the process. (This will become per-thread when
thread-local storage is implemented.)

The new stack will be deallocated either when _lamp_stack_space() is
called and the stack is lo longer in use or when the process terminates.

Define _create_new_stack() (and _lamp_stack_space())
http://github.com/jjuran/metamage_1/blob/master/lamp/Kerosene/stack-chain/stack-chain.cc

A C++ interface to restack is lamp::recurse(). It's used by replacing
foo( bar, baz ) with lamp::recurse( foo, bar, baz ). If stack space
is sufficient, it just calls foo() as before. Otherwise, it calls
_lamp_restack( size, foo, bar, baz ), with references converted to
pointers.

Define lamp::recurse() template
http://github.com/jjuran/metamage_1/blob/master/posix/compat/lamp/recurse.hh

New stacks are allocated with malloc(). It's highly recommended to
link with dlmalloc, which is implemented in terms of mmap() (which has
access to temporary memory) instead of using MSL's malloc(), which
calls NewPtr(). The latter is bounded by the application heap; the
former won't fail until all Process Manager heap memory is exhausted
-- which usually enough.

So there you have it, another shock absorber on the bumpy ride of
classic Mac OS development.

Josh

[Cameron Kaiser]

> Traditional Mac OS, of course, doesn't have this. A process' stack
> size is essentially fixed when it launches, as are thread stacks. A
> typical default stack size for the Thread Manager is 32K; Lamp uses a
> minimum of 64K. This is fine for most programs, but it prohibits deep
> recursion.
>
> I've come up with a solution for Lamp: Dynamically allocate and
> switch to a new stack.

Nice work. MachTen has this problem in spades; I always run out of stack
with wacky apps and have to restart, recompile and hope (or compile with
a ridiculous amount of stack and work down).

--
------------------------------------ personal: http://www.cameronkaiser.com/ --
Cameron Kaiser * Floodgap Systems * www.floodgap.com * cka...@floodgap.com
-- Just another Sojourner of the Dispersion (1 Peter 1:1) ---------------------