Text preview for : Alto_BCPL_Storage_Allocation_Jun73.pdf part of xerox Alto BCPL Storage Allocation Jun73 xerox alto memos_1973 Alto_BCPL_Storage_Allocation_Jun73.pdf
Back to : Alto_BCPL_Storage_Allocat | Home
'-/EnJr~\/ f/l
I~,~
' - H ~~,'~
Ih'l.iLJ 't:.
To CSL and SSL Date June 19, 1973
From Butler Lampson Location Palo Alto
Subject Al to/Bcpl stcrage allocation Organization PARC / CSL
and function calls
1. Overview
This document describes the facilities provided by the
standard Alto microcode for storage allocation and function
calls. They are intended to support function calls and returns
for languages \'1hich pass parameters by value and allocate the
local environment or iram~ for a function vlhen it is called, vJi th
a corresponding deallocation on the return. Provis~on is also
made for statically allocated frames, for a global storage region
which may change during a call or return, and for a coroutine
linkage. Finally" function descriFtors and return links are
interpreted as segmented addresses, so tha~ code segments can be
swapped or'relocated.
2. Background
This section discusses the major alternatives which were
considered in arriving at the present scheme. Hopefully, it will
make it easier for the'reader to understand why things are done
the way they are.
During a transfer of control from one function to another,
it is necessary to:
a) obtain the address of the first instruction to be
executed in the ne\;7 function;
b) allocat storage for the new function or release
storage fer the old one;
c) possibly set up pointers to the environment of the new
function;
d) pass parameters, possibly including a return link.
Item (a) is complicated by our desire to be able to move code or
to keep code out of core, until it is referenced. Both (a) and
(b) are closely related to the question of hC\-J memory is to be
ALTO/BCPL STORAGE ALLOCATION AND FUNCTION CALLS / Butler Lampson
June 19, 1973 Page 2
,allocated. Item (c) requires decisions about how much
environment should be set up automatically.
It is \Olell knC\r1n that two areas \-1hich grow and shrink at one
end can be conveniently allocated in a single block of memory, by
putting one at the top and gro\'ling i t do\vn, and putting the other
at the bottom and growing i t up. vJith more than tvl0 areas, life
is much more difficult.
Bcpl programs need three kinds of storage: program q stack,
and heap. The observation of the preceding paragraph motivates
us to combine the stack and the heap, so that there vlill be only
t'f.r-10 areas.. This arrangement results in a som5'lhat different kind
of storage fragmentaticn than one gets with a stack, which we now
proceed to examine.
A stack has several desirable properties:
81) Frames are physically adjacent, so that parameters can
be deposited by a caller at the end of his frame and
magically appear at the beginning