From: andy@research.canon.oz.au (Andy Newman)
Newsgroups: comp.sys.transputer
Subject: Dynamic Memory Allocation (was Re: Why Occam3 probably won't be recursive)
Keywords: Occam3 recursive, no
Date: 19 Nov 92 06:54:17 GMT
Organization: Canon Information Systems Research Australia

dbc@ecs.soton.ac.uk (Bryan Carpenter) writes:
>
>Personally, I wouldn't object to building my own stack, if I just
>had `malloc' to do it with.  Building my own `malloc' I object to
>more strongly.
>
>Bryan
>

Building a memory allocation module isn't all that difficult (once
you've done it once or twice :-). Anyway in most "serious"
applications you layer an application specific allocator on the
"standard" allocator.

I worked on a (now defunct) TV animation product based on T800's. It
comprised a LARGE amount of occam (the last I heard it was up around
the 500,000 line mark) We used a dynamic memory allocation quite
extensively. We used a very obvious and simple method but it worked
quite well and gave us the facilities we needed.

I'll describe what we did but first I must state that we
didn't adopt the occam "way", i.e. we used dynamically allocated
things; we turned off the compiler's checking (it didn't work for us
anyway), etc... We were heathens! We used occam because it was the
only thing available at the time for transputers that could generate
reasonable code. There were the first C compilers available but we'd
gone too far by the time they were useful.

The system comprised a number of long lived processes, i.e. the
modules in the system. Each of these processes accepted a number of
parameters, one of which was a unsized vector of INT - the memory pool.

One of the standard "kernel" processes was a memory allocator. It
"owned" the memory pool vector and serviced requests for portions of
the pool - it serialised other processes attempts to modify the
memory allocator data structure.

The allocator process understood a few requests; allocate some memory,
add some memory to the freelist, report the largest block available,
etc... You know, standard general purpose allocator things. As I
recall we had a couple of procedures....

    PROC Alloc.Mem( [2]CHAN OF ANY mm.chans, VAL INT nbytes, INT ptr )
    PROC Free.Mem( [2]CHAN OF ANY mm.chans, INT ptr )

Notes:

    Yes we used CHAN OF ANY - it allowed our configuration langauage and
communications system work! The two element vector holds the "to"
channel and the "from" channel used to perform the RPC with the memory
allocator process (this use exposed a limitation in the compiler, it
assumed all channels in a vector were used in the same "direction")
Passing the channels also allowed these procs to be used with
different allocators (we had a few - one for the local processor's
memory, one for our processor board's shared memory and one for the
on-chip memory).

    The ptr parameter to Free.Mem is not a VAL INT. It should be the
exact same actual parameter passed as ptr in the call to Alloc.Mem.

"Addresses" were the (INT) index into the memory pool vector. You'd
send a message to the allocator process (or more specifically call a
proc that hid the protocol) requesting some memory and it would return
the index of the first word you could use. To free something you sent
the index back to the allocator and it would put a block onto the
freelist. This is quite open to abuse of course but in our environment
we had control and there are a number of simple techniques that assist
in detecting memory corruption and mis-use. We didn't have all that
much trouble.

This scheme goes totally against occam's usage checking! We were
passing a single vector to nearly every process in the system and
those processes are accessing practically any part of the vector. Not
a checkable thing really.

Okay this method is not safe (in fact its downright dangerous!) but it
gave us flexible dynamic allocation facilities. I'm not advocating its
use (its not wise to "bend" occam, if you want to do these things use
a language that supports them properly) but it did work.

-- 
Andy Newman (andy@research.canon.oz.au)
Newsgroups: comp.sys.transputer