UP

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.

{arcane}The full form of this operation is:

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.

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

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));).

B(BANK__SEVER_NODE{=2};N ==> c;T).

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).

{arcane}B(BANK__MAKE_NODE_GRATIS{=3};N,AC ==> c;).

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.

{arcane}The full form of this operation is:

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

{arcane}B(BANK__MAKE_NODE_NON_GRATIS{=4}; 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;).

B(BANK__QUERY_NODE_SPACE{=5}; ==> c, (4, n);).

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.

B(BANK__QUERY_NODE_STATISTICS{=6}; ==> c, (4, nc), (4, nd);).

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.}

B(BANK__CREATE_TWO_NODES{=7}; ,AC ==> c;N1,N2).

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.

B(BANK__CREATE_THREE_NODES{=8}; ,AC ==> c;N1,N2,N3).

Similar to BANK__CREATE_TWO_NODES.

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

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

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.

To clarify the return code:

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.

{arcane}The full form of this operation is:

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]));).

B(BANK__DESTROY_THREE_NODES{=10}; N[1],N[2],N[3] ==> (c[1] + 2*c[2] + 4*c[3]), ((1,g[1]), (1,g[2]), (1,g[3]));).

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)}.

B(11,(4,change_limit) ==> c,(4,new_limit);)

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.

Operations for Pages

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.

Miscellaneous Operations

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.

B(64; ==> c;) {"destroy and zap space"}

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;==>c;) returns in c X'C'.

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 refered to by code 64 {(o64)}. See, however, (keep64).

{arcane}How to enlarge the primordial space bank

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.

{ni}Proposed SBT Elimination

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.

{ni}Space bank 2 proposal

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.

Correcting these problems requires the following additions and changes to the external specs

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 that 2**32-1 nodes are available

B(6{=Query nodes statistics}==>c,(4,buys),(4,sells)) will return X'FFFFFFFF' when buys are more that 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.

B(BANK__CHANGE_NODE_LIMIT{=13},(8,change_limit) ==> c,(8,new_limit))

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.

B(BANK__QUERY_NODES_AVAILABLE{=14} ==> c, (8, n);).

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.

Similar changes and new order codes exist for pages with the order codes greater by a value of 16.

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.}

B(BANK__VERIFY_BANK{=66};B1==>c;)

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.

B(BANK__CREATE_BANK{=67}==>c;B1)

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.

{ni}B(BANK__TEST_ZAP_EFFECTS{=68};K==>c)

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.

{ni}B(BANK__LOCK_GUARDED{69};KRT==>c)

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.

{ni} B(BANK__UNLOCK_GUARDED==>c)

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

Existing range key functions used

{???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.

RANGE(2;K==>0;) Sever

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

{???May not need???}RANGE(5,(4,rcda)==>c;K) Allocate

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.

RANGE(6;K==>c) Sever and zero

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

{ni}New range key functions

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.

RANGE(8,(6,rcda)==>c) Sever, Fork, and Zero

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.

RANGE(9,(6,rcda)==>c;K) Allocate and clear

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.

RANGE(10,(6,rcda)==>c,(6,nextcda)) Find next mounted

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;

RANGE(11,(6,rcda)==>c,(6,nextcda)) Find next not mounted

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.

The change described in (p1,localslot) will be required so the space bank can receive 3 keys, the node key to the front end node, and the resume key to the caller.

Internal Design

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

Data Structure Format

(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)

Guard Segment Format

(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

Format = 1 (large 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.

Page five

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.

Page 2**21 (address 2 * 2**32)

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.

Conversion Between Formats

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.

"Quick" Space Bank Domain

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.

"Slow" Space Bank Domain

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

Allocation Strategy

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.

The following definitions are in PLIGATES and DOMAIN MACLIB member SBDEFS.

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.