Let B be a space bank. Some space banks are prompt.

Operations for Nodes

- B(BANK__CREATE_NODE{=0}; ,AC ==> c;N).

- AC can be omitted if the bank does not require an account.

If successful, c will be 0 and N will be the only key to a node which contains all zero data keys, and there will be no process in the node.

Return codes c:

- If the bank is unable to create the node because none
is available, c will be 1.

Some banks require an account for the number of gratis nodes. If the account is insufficient or the node limit is reached, c will be 3.

Some banks require an account which is charged some amount for the node. Others place a limit on the number of nodes that can be created. If the account AC is insufficient for this purpose or the limit of some superior bank is reached, c will be 4.

- B(BANK__CREATE_NODE{=0},((4,lower_limit),(4,upper_limit),
(1,want_gratis)); ,AC ==> c;N).

If want_gratis is supplied and is nonzero, the node will be gratis; otherwise, it will be non-gratis. Lower_limit and upper_limit can be used to restrict the range from which the node may be allocated; for details, see the formal description of space banks in Algol68. If it is not desired to restrict the range, lower_limit should be absent or zero and upper_limit should be absent or the maximum {unsigned} integer.

The node is acceptable to the bank provided the same limits are used.

- If N is not a node key acceptable to this bank, c will
be 1. Otherwise, all keys to the node, or to domains whose
root is this node are changed to zero data keys; if there
was a process in the node it is destroyed; c will be 0;
and if the node was gratis g will be 1 otherwise 0. If
the bank uses an account, AC will receive any refund for
the node.

{arcane}The full form of this operation is:

- B(BANK__DESTROY_NODE{=1},((4,lower_limit),(4,upper_limit));
N, AC ==> c,((1,g));).

- If N is not a node key acceptable to this bank, c will
be 1. Otherwise, c will be zero, all keys to the node, or
to domains whose root is this node are replaced by zero
data keys, if there was a process in the node it is destroyed,
and a new key T to the node is returned.

{arcane}The full form of this operation is:

- B(BANK__SEVER_NODE{=2},((4,lower_limit),(4,upper_limit));N
==> c;T).

- The return code c tells the result:

- If N is not a node key acceptable to this bank, c will
be 1.

If N is already gratis, c will be 2.

If N cannot be made gratis, because either account AC is insufficient or a limit was reached, c will be 3.

Otherwise, c is 0 and the node is made gratis.

- B(BANK__MAKE_NODE_GRATIS{=3}, ((4,lower_limit), (4,upper_limit));N,AC
==> c;).

- If N is not a node key acceptable to this bank, c will
be 1. If N is already non-gratis, c will be 2. Otherwise,
c is 0 and the node is made non-gratis. If the bank use
an account, AC will receive any refund.

Design Note: While we have not yet made use of the gratis attribute, this order plays the important function of non destructive verification of the "accptability of a node to a bank".

{arcane}The full form of this operation is:

- B(BANK__MAKE_NODE_NON_GRATIS{=4},((4,lower_limit),(4,upper_
li mit)); N,AC ==> c;).

- If key B or any of its superior banks does not have query
rights, c is 3. Otherwise c is 0 and n is the number of
nodes that could be created.

{arcane}The full form of this operation is:

- B(BANK__QUERY_NODE_SPACE{=5},

((4,lower_limit),(4,upper_limit)); ==> c, (4, n);)

N is the number of nodes that could be created in the specified range.

- If key B does not have query rights, c is 3. Otherwise
c is 0, nc is the total number of successful "create node"
operations performed on this bank since its creation, and
nd is the total number of successful "destroy node" operations.
{nc minus nd is usually the number of nodes outstanding
from this bank.}

- Similar to BANK__CREATE_NODE.

C will be zero if the operation is successful. N1 and N2 are node keys with zero databytes to two different nodes, and there are no other keys to those nodes. The nodes will contain all zero data keys and will not have processes. They will be non-gratis.

C will be 1 if two nodes are not available. No node keys are returned.

{arcane}C will be 3 if want_gratis is nonzero and for that reason account AC is insufficient or a limit is reached. No node keys are returned.

C will be 4 if account AC is insufficient or a limit is reached. No node keys are returned.

{arcane}The full form of this operation is:

- B(BANK__CREATE_TWO_NODES{=7},((4,lower_limit),(4,upper_limi
t) , (1,want_gratis)); ,AC ==> c;N1,N2).

The nodes will be from the range specified by lower_limit and upper_limit, if specified. If want_gratis is supplied and is nonzero, the nodes will be gratis; otherwise, they will be non-gratis. The nodes will be acceptable to the bank provided the same or wider limits are used.

- Similar to BANK__CREATE_TWO_NODES.

Time is 4.6 ms. {(p3,ob1)}.

- For i from 1 to 2:

- If N[i] is not a node key acceptable to this bank, c[i]
will be 1.

Otherwise: c[i] will be 0; all keys that designate the node N[i], including keys that designate a domain whose root is N[i], are changed to zero data keys; if there was a process in the node it is destroyed; and if the node was gratis g[i] will be 1 otherwise 0. If the bank uses an account, AC will receive any refund for the node.

- 0 means N[1] and N[2] were both acceptable.

1 means N[1] was not acceptable but N[2] was.

2 means N[1] was acceptable but N[2] wasn't.

3 means neither N[1] nor N[2] was acceptable.

- B(BANK__DESTROY_TWO_NODES{=9},((4,lower_limit),(4,upper_lim
it )); N[1],N[2],AC ==> (c[1] + 2*c[2]), ((1,g[1]), (1,g[2]));).

- Similar to BANK__DESTROY_TWO_NODES. If the bank uses
an account, no refund for the nodes will be given, so this
operation is not recommended for such banks.

Time is 2.6 ms. {(p3,ob1)}.

- If B does not have change_limit rights then c=3 and B's
node limit is not changed or returned,

Otherwise change_limit is regarded as a signed number and added to B's current node limit unless that would cause it to become negative or exceed 2**32-1. Instead of going negative the unmodified limit is returned and c=1. Instead of exceeding 2**32-1 the unmodified limit is returned and c=2.

- For every node operation above, there is a corresponding
page operation. The order codes are greater by 16 {for
example, BANK__CREATE_PAGE is 16}.

A newly created page contains all zeros and you get a read/write key to it. A page key must be read/write to be acceptable to a bank.

- Orders 33 thru 39. B(32+m+q+d ==> WB) returns a key
to the same bank with fewer rights.

- d is 0 or 1 and WB has destroy rights if (B does and
d = 0).

q is 0 or 2 and WB has query rights if (B does and q = 0).

m is 0 or 4 and WB has limit change rights if (B does and m = 0).

d, q and m may not all be zero.

- If B does not have destroy rights, c will be 3. Otherwise
c will be 0, the bank B and its sub-banks are destroyed
{as with kt+4}, and also all the space that was created
using this bank is destroyed, by returning it to the superior
bank. It is best if that bank does not use an account.

As each node is destroyed, all resume keys in the node are invoked with order code kt+1. The idea is to notify a caller when an object is destroyed by this method.

B(kt+4; ==> c;) {"destroy"}

- If B does not have destroy rights, c will be 3. Otherwise
c will be 0 and bank B and all its sub-banks are destroyed.
When a bank is destroyed, all keys to it will be DK(0),
and the account that was paying rent for it stops being
charged.

This operation may be deimplemented and order code kt+4 made to provide the operation now referred to by code 64 {(o64)}. See, however, (keep64).

- First format the additional disk. The available CDA's
must be in a contiguous range starting at X'1000' and limited
by X'600000'. In other words, the new CDA's must start
where the old ones left off with no gap.

There should be at least a few pages and a few nodes. In other words, not all pages or all nodes. The bank needs both to build the bit map that keeps track of which pages and nodes are available.

Then mount the disk and ready it.

Then get a domain key to the primordial space bank domain. {There is one in SYSNODE.PRIMORDSTUFF.0 {sysnode.2}.} Make an entry key to it with databyte X'20'. Call it with order code 69. It will find the new space and begin using it.

- For each of the order codes defined for the space bank
transformer in (p2,sbt), except
0 and kt, a space bank will obey that order code + 256 and
apply the transformation with itself as the "B1" parameter.
The "verify" operation {order code 0} does not make sense
in this context. Another order code for banks will be designated
for the function of asking one bank about another.

A space bank will not pass a factory discression test since it (through its counters) may be used to pass information. Factory products may use the Prompt Space Bank from the factory for "offical space bank" tests since it has already passed the Factory's "offical" test.

- This proposal is made to solve several problems with
the current space bank design. They are:

- Each sub-bank adds to the cost (in gate jumps) for creating
and destroying pages or nodes

Space limits and counters are not large enough for 6 byte CDAs or 100 MIP machines

Space banks do not permit non-mounted holes in their range keys.

Many domains require the space bank transformer solely for the purposes of testing for "offical" banks and creating sub-banks.

- Create, destroy, and query calls no longer accept a limit
string. (i.e. order codes 0, 1, 2, 5, 7, 8, 9, 10, 16, 17,
18, 21, 23, 24, 25, 26).

Create and Destroy calls do not use an Account key.

Destroy calls do not return a string.

"Gratis" is not implemented.

B(5{=Query nodes available}==>c,(4,count)) will return X'FFFFFFFF' whenever more than 2**32-1 nodes are available

B(6{=Query nodes statistics}==>c,(4,buys),(4,sells)) will return X'FFFFFFFF' when buys are more than 2**32-1. The sells value will be adjusted (if possible) so the difference (buys-sells) is the number of nodes currently allocated.

B(BANK__SET_NODE_RANGE_LIMIT{=12},(8,node_lower_limit),(8,node _upper_limit) ==> c)

- If B does not have change_limit rights then c=3 and B's
node range limit is not changed,

Otherwise if node_lower_limit is greater than node_upper_limit c=2 and no change is made to the node limits.

Otherwise the space bank is changed to only allocate nodes with CDAs between node_lower_limit and node_upper_limit (inclusive). Note that this bank is also subject to the node range limits imposed upon superior banks.

- If B does not have change_limit rights then c=3 and B's
node limit is not changed or returned,

Otherwise change_limit is regarded as a signed number and added to B's current node limit unless that would cause it to become negative or exceed 2**48-1. Instead of going negative the unmodified limit is returned and c=1. Instead of exceeding 2**48-1 the unmodified limit is returned and c=2.

- If key B or any of its superior banks does not have query
rights, c is 3. Otherwise c is 0 and n is the number of
nodes that could be created.

B(BANK__QUERY_STATISTICS{=65} ==> c, (8,nc), (8,nd), (8,pc), (8,pd)).

- If key B does not have query rights, c is 3. Otherwise
c is 0, nc is the total number of successful "create node"
operations performed on this bank since its creation, and
nd is the total number of successful "destroy node" operations.
{nc minus nd is usually the number of nodes outstanding
from this bank.}

- If B1 is not an official space bank, c will be -1. If
B1 is an official bank then bit 0 of c is 0 and c will be
P + Q + D + L. If B1 is prompt P is 0 otherwise 128. If
B1 has query rights Q is 0 otherwise 2. If B1 has destroy
rights D is 0 otherwise 1. If B1 has limit set rights L
is 0 othewise 4.

- If c=0 a new bank B1 subservient to B has been created.
The new bank, B1 can be used to provide a point for keeping
statistics, or for using the "destroy" operation. B1 is
prompt iff B is prompt. Key B1 has destroy and set limit
rights. It has query rights if and only if B has them. The
initial limits are 2**32-1 pages and nodes. The initial
range limits are the full range supported by the bank. Note
that limits are heirarchial and a sub-bank can can not allocate
more than or out side the range limits of its superior bank(s).
c=1 if there is not enough space to create the subbank.

Programming note: A more restrictive sub-bank may be created by using CHANGE_NODE_LIMIT, CHANGE_PAGE_LIMIT, CHANGE_NODE_RANGE_LIMIT, and CHANGE_PAGE_RANGE_LIMIT as desired and then using order code 36 to restrict change limits rights.

- If K is any key to a page or node guarded by this bank
or any of its sub-banks then c is 1. Otherwise c is 0. If
the range key held by the bank does not support order code
7, then c is KT+2.

- -acb- Can K be any key to a NODE (such as SEGMENT) -
(wsf) Yes.

- If KRT is a Kernel Realtime Key (krealtime)
then all the pages and nodes guarded by this bank will be
locked into real memory. c=0 - All locked, c=1 - Kernel
limit exceeded, some not locked. c=KT+3 KRT is not a Kernel
Realtime Key.

- All pages and nodes guarded by this bank are unlocked
from real memory. c is 0.

- {???Use oc=7 below???}RANGE(1;K==>c,(4,rcda)) Identify

- If K is a strong key in the range returns c=0 and rcda,
otherwise returns -1.

- Changes all slots holding keys to the object designated
by K to hold DK(0).

- Returns 0 in c and a strong key in K to the page or node
whose Coded Disk Address is rcda + the range offset. If
rcda is not in the range, it returns 1 in c. If the page
or node is not mounted, it returns 2 in c. If there is a
permanent I/O error for that page, c is 3.

- Returns -1 if K is not a strong key in the range.

- RANGE(7;K==>c,(1,type),(1,databyte),(6,rcda)) Relative
Unspec

- If K designates a node or page and RANGE is a range key
which can produce a node key or page key to that node or
page then c is 0 if K is to a page or a node without a process
or 1 if K is to a node with a process; type, databyte, and
rcda are the type and databyte from the key and rcda is
the rcda of the node or page. Otherwise c is -1 and no string
is returned.

- rc=0: the object O designated by rcda has been severed,
any resume keys in O (none for a page) have been forked
with O(KT+1,(6,0)==>), and the object has been zeroed.
c=1: rcda not in range. c=2: object not mounted. c=3: perm
I/O error.

- Returns 0 in c and a strong key in K to the page or node
whose Coded Disk Address is rcda + the range offset. The
page or node has been zeroed. If rcda is not in the range,
c is 1. If the page or node is not mounted, c is 2. If there
is a permanent I/O error for that page or node, c is 3.

- If c=0 then nextcda is the next higher or equal relative
CDA from rcda which is mounted. If there is no higher mounted
CDA in the range then c=1;

- If c=0 then nextcda is the next higher or equal relative
CDA from rcda which is not mounted or is outside the range.
If nextcda is greater than X'FFFFFFFFFFFF' then c=1.

- This design is limited to 2**32 nodes and 2**32 pages.

Each space bank is represented by a red segment node, a data structure in a common segment, and a guard segment. The keeper of the red segment is the "quick" space bank domain. It has a friend called the "slow" (although still prompt) space bank domain.

Red Segment Node Format

- Slot 0 - Format 0 guard page key or Format 1 guard segment
node key.

Slot 9 - Slot to receive caller's 3rd key parameter.

Slot 10 - Forward sibling node key (or self)

Slot 11 - Backward sibling node key (or self)

Slot 12 - Descendent node key (one of possibly many) or DK0

Slot 13 - Ancestor node key

Slot 14 - Keeper start key

Slot 15 - Red segment node format data key

- (4,lower node range limit as set)

(4,upper node range limit as set)

(4,lower page range limit as set)

(4,upper page range limit as set)

(8,page allocation limit)

(8,node allocation limit)

(8,nodes allocated)

(8,node sells)

(8,pages allocated)

(8,page sells)

(4,ancestor data structure segment id)

(4,ancestor data structure index within segment)

- (4,data structure segment id)

(4,data structure index within segment)

(1,node presence presence bits) Iff 0 then node data is format 0

(1,page presence presence bits) Iff 0 then page data is format 0

(4,node allocation cursor)

(4,page allocation cursor)

Format = 0 (small bitmap)

- (4,first node) - First guarded cda, must be a multiple
of 32 (on a word boundry in the bitmap)

(2000, node guard bitmap) allocated node CDAs are bit offset in guard bitmap + first node.

(4,first page) - First guarded cda, must be a multiple of 32 (on a word boundry in the bitmap)

(2000, page guard bitmap) used similary to the node guard bitmap

- Page one

- Start of up to four pages of node guard map page presence
bits. A page is present iff its bit in node presence presence
bits is one.

- Start of up to four pages of page guard map page presence
bits. A page is present iff its bit in page presence presence
bits is one.

- Start of up to 2**17 pages of node guard bitmap. Pages
are present in this bitmap when the associated node guard
map page present bit is one.

- Start of up to 2**17 pages of page guard bitmap. Pages
are present in this bitmap when the associated page guard
map page present bit is one.

- Space banks are created with format 0 guard segments.
When it becomes necessary to set a guard bit outside the
range of the guard bitmap, then the format for that type
of guard (node or page) is converted to format 1 as follows:

- If the other guard is also format zero, then get a node
with a lss=3 node key. Install the guard page key in slot
zero. Set the presence presence bits to zero.

Get a node with a lss=8 node key. Install the lss3 node key in its slot 0. Store the lss=8 node key in slot 0 of the space bank front end node. Set the format to 1.

The guard segment structure is now valid for a format 1 segment. Use grow_segment to allocate a page at first_node or first_page (whichever guard needs to be converted). Copy the first part (or all) of the bitmap to the page at the offset. If only part copied use grow_segment to allocate a second page and copy the rest.

- The "quick" space bank domain handles all calls that
execute quickly. These are creating and destroying pages
and nodes, changing limits, queries, making keys with restricted
rights, testing space banks, creating new sub-banks.

It performs the initial processing when a space bank is zapped. This processing consists of severing the space bank node for the bank and each of its sub-banks, placing the bank nodes on a work queue for the "slow" domain.

It also implements an internal key to allow the slow space bank domain to make pages and nodes available for allocation (update the allocation map), de-queue and return space bank nodes and data structures, and request more work from the "quick" domain.

- The slow domain recovers space when a space bank is zapped.

- A space bank always attempts to perform allocation in
a way which will not require new guard pages. Within the
range of cdas it can allocate with its current guard allocation,
it allocates in circular order.

The space bank keeps two bit maps to control node and page allocation. The format and stratigy for using these bitmaps is similar to the that for format 1 guard maps described in (newbank_guard)

The space bank keeps two global (for all space banks using a keeper domain) allocation cursors, one for nodes and one for pages. When a space bank bank needs to create a new guard page, the space bank starts its search at the cda of the appropreate global allocation cursor and then sets the cursor to the first available cda + 8000. Note that to be considered available the cda must be not allocated and in a mounted range.

Each new space bank is created with initial values in the first_node and first_page fields of its format 0 guard page. These values are calculated by finding the first available cdas above the global cursors and updating the global cursors by that cda + 8000.

- BANK__CREATE_NODE=0, BANK__DESTROY_NODE=1, BANK__SEVER_NODE=2,
BANK__MAKE_NODE_GRATIS=3, BANK__MAKE_NODE_NON_GRATIS=4,
BANK__QUERY_NODE_SPACE=5, BANK__QUERY_NODE_STATISTICS=6,
BANK__CREATE_TWO_NODES=7, BANK__CREATE_THREE_NODES=8, BANK__DESTROY_TWO_NODES=9,
BANK__DESTROY_THREE_NODES=10, BANK__CREATE_PAGE=16, BANK__DESTROY_PAGE=17,
BANK__SEVER_PAGE=18, BANK__MAKE_PAGE_GRATIS=19, BANK__MAKE_PAGE_NON_GRATIS=20,
BANK__QUERY_PAGE_SPACE=21, BANK__QUERY_PAGE_STATISTICS=22,
BANK__CREATE_TWO_PAGES=23, BANK__CREATE_THREE_PAGES=24,
BANK__DESTROY_TWO_PAGES=25, BANK__DESTROY_THREE_PAGES=26.