44  PART 9: DYNAMIC MEMORY ALLOCATION  TEX82 §115

115. Dynamic memory allocation. The TEX system does nearly all of its own memory allocation, so that it can readily be transported into environments that do not have automatic facilities for strings, garbage collection, etc., and so that it can be in control of what error messages the user receives. The dynamic storage requirements of TEX are handled by providing a large array mem in which consecutive blocks of words are used as nodes by the TEX routines.

Pointer variables are indices into this array, or into another array called eqtb that will be explained later. A pointer variable might also be a special flag that lies outside the bounds of mem, so we allow pointers to assume any halfword value. The minimum halfword value represents a null pointer. TEX does not assume that mem[null ] exists.

define pointer ≡ halfword { a flag or a location in mem or eqtb }

define null ≡ min halfword { the null pointer } ⟨ Global variables 13 ⟩ +≡ temp ptr : pointer ; { a pointer variable for occasional emergency use }

116. The mem array is divided into two regions that are allocated separately, but the dividing line between these two regions is not fixed; they grow together until finding their “natural” size in a particular job. Locations less than or equal to lo mem max are used for storing variable-length records consisting of two or more words each. This region is maintained using an algorithm similar to the one described in exercise 2.5–19 of The Art of Computer Programming. However, no size field appears in the allocated nodes; the program is responsible for knowing the relevant size when a node is freed. Locations greater than or equal to hi mem min are used for storing one-word records; a conventional stack is used for allocation in this region.

Locations of mem between mem bot and mem top may be dumped as part of preloaded format files, by the preprocessor. Production versions of TEX may extend the memory at both ends in order to provide more space; locations between mem min and mem bot are always used for variable-size nodes, and locations between mem top and mem max are always used for single-word nodes.

The key pointers that govern mem allocation have a prescribed order:

null ≤ mem min ≤ mem bot < lo mem max < hi mem min < mem top ≤ mem end ≤ mem max .

Empirical tests show that the present implementation of TEX tends to spend about 9% of its running time allocating nodes, and about 6% deallocating them after their use. ⟨ Global variables 13 ⟩ +≡ mem: array [mem min . . mem max ] of memory word ; { the big dynamic storage area } lo mem max : pointer ; { the largest location of variable-size memory in use } hi mem min: pointer ; { the smallest location of one-word memory in use }

§118  TEX82  PART 9: DYNAMIC MEMORY ALLOCATION 45

117. In order to study the memory requirements of particular applications, it is possible to prepare a version of TEX that keeps track of current and maximum memory usage. When code between the delimiters stat … tats is not “commented out,” TEX will run a bit slower but it will report these statistics when tracing stats is sufficiently large. ⟨ Global variables 13 ⟩ +≡ var used , dyn used : integer ; { how much memory is in use } 118. Let’s consider the one-word memory region first, since it’s the simplest. The pointer variable mem end holds the highest-numbered location of mem that has ever been used. The free locations of mem that occur between hi mem min and mem end , inclusive, are of type two halves , and we write info(p) and link (p) for the lh and rh fields of mem[p] when it is of this type. The single-word free locations form a linked list

avail , link (avail ), link (link (avail )), …

terminated by null .

define link (#) ≡ mem[#].hh.rh { the link field of a memory word }

define info(#) ≡ mem[#].hh.lh { the info field of a memory word } ⟨ Global variables 13 ⟩ +≡ avail : pointer ; { head of the list of available one-word nodes } mem end : pointer ; { the last one-word node used in mem }

119. If memory is exhausted, it might mean that the user has forgotten a right brace. We will define some procedures later that try to help pinpoint the trouble.

⟨ Declare the procedure called show token list 292 ⟩

⟨ Declare the procedure called runaway 306 ⟩

120. The function get avail returns a pointer to a new one-word node whose link field is null. However, TEX will halt if there is no more room left.

If the available-space list is empty, i.e., if avail = null , we try first to increase mem end . If that cannot be done, i.e., if mem end = mem max , we try to decrease hi mem min. If that cannot be done, i.e., if hi mem min = lo mem max + 1, we have to quit. function get avail : pointer ; { single-word node allocation }

var p: pointer ; { the new node being got }

begin p ← avail ; { get top location in the avail stack }

if p ≠ null then avail ← link (avail ) { and pop it off }

else if mem end < mem max then { or go into virgin territory } begin incr (mem end ); p ← mem end ; end

else begin decr (hi mem min); p ← hi mem min;

if hi mem min ≤ lo mem max then begin runaway ; { if memory is exhausted, display possible runaway text } overflow ( ␣ ␣ , mem max + 1 − mem min); { quit; all one-word nodes are busy } end; end;

link (p) ← null ; { provide an oft-desired initialization of the new node }

stat incr (dyn used ); tats { maintain statistics }

get avail ← p;

end;

121. Conversely, a one-word node is recycled by calling free avail . This routine is part of TEX’s “inner loop,” so we want it to be fast.

define free avail (#) ≡ { single-word node liberation } begin link (#) ← avail ; avail ← #; stat decr (dyn used ); tats end 122. There’s also a fast get avail routine, which saves the procedure-call overhead at the expense of extra programming. This routine is used in the places that would otherwise account for the most calls of get avail .

define fast get avail (#) ≡ begin # ← avail ; { avoid get avail if possible, to save time } if # = null then # ← get avail else begin avail ← link (#); link (#) ← null ;

stat incr (dyn used ); tats end; end

123. The procedure flush list (p) frees an entire linked list of one-word nodes that starts at position p. procedure flush list (p : pointer ); { makes list of single-word nodes available }

var q, r: pointer ; { list traversers }

begin if p ≠ null then begin r ← p; repeat q ← r; r ← link (r); stat decr (dyn used ); tats

until r = null ; { now q is the last node on the list } link (q) ← avail ; avail ← p; end;

end;

124. The available-space list that keeps track of the variable-size portion of mem is a nonempty, doublylinked circular list of empty nodes, pointed to by the roving pointer rover .

Each empty node has size 2 or more; the first word contains the special value max halfword in its link field and the size in its info field; the second word contains the two pointers for double linking.

Each nonempty node also has size 2 or more. Its first word is of type two halves, and its link field is never equal to max halfword . Otherwise there is complete flexibility with respect to the contents of its other fields and its other words.

(We require mem max < max halfword because terrible things can happen when max halfword appears in the link field of a nonempty node.)

define empty flag ≡ max halfword { the link of an empty variable-size node }

define is empty (#) ≡ (link (#) = empty flag ) { tests for empty node }

define node size ≡ info { the size field in empty variable-size nodes }

define llink (#) ≡ info(# + 1) { left link in doubly-linked list of empty nodes }

define rlink (#) ≡ link (# + 1) { right link in doubly-linked list of empty nodes } ⟨ Global variables 13 ⟩ +≡ rover : pointer ; { points to some node in the list of empties } 125. A call to get node with argument s returns a pointer to a new node of size s, which must be 2 or more. The link field of the first word of this new node is set to null. An overflow stop occurs if no suitable space exists.

If get node is called with s = 2^{30}, it simply merges adjacent free areas and returns the value max halfword . function get node(s : integer ): pointer ; { variable-size node allocation }

label found , exit , restart ; var p: pointer ; { the node currently under inspection }

q: pointer ; { the node physically after node p }

r: integer ; { the newly allocated node, or a candidate for this honor } t: integer ; { temporary register }

begin restart : p ← rover ; { start at some free node in the ring } repeat ⟨ Try to allocate within node p and its physical successors, and goto found if allocation was

possible 127 ⟩; p ← rlink (p); { move to the next node in the ring }

until p = rover ; { repeat until the whole list has been traversed } if s = ´ 10000000000 then

begin get node ← max halfword ; return;

end; if lo mem max + 2 < hi mem min then

if lo mem max + 2 ≤ mem bot + max halfword then

⟨ Grow more variable-size memory and goto restart 126 ⟩; overflow ( ␣ ␣ , mem max + 1 − mem min); { sorry, nothing satisfactory is left }

found : link (r) ← null ; { this node is now nonempty } stat var used ← var used + s; { maintain usage statistics } tats get node ← r;

exit : end;

126. The lower part of mem grows by 1000 words at a time, unless we are very close to going under. When it grows, we simply link a new node into the available-space list. This method of controlled growth helps to keep the mem usage consecutive when TEX is implemented on “virtual memory” systems. ⟨ Grow more variable-size memory and goto restart 126 ⟩ ≡

begin if hi mem min − lo mem max ≥ 1998 then t ← lo mem max + 1000 else t ← lo mem max + 1 + (hi mem min − lo mem max ) div 2; { lo mem max + 2 ≤ t < hi mem min } p ← llink (rover ); q ← lo mem max ; rlink (p) ← q; llink (rover ) ← q; if t > mem bot + max halfword then t ← mem bot + max halfword ; rlink (q) ← rover ; llink (q) ← p; link (q) ← empty flag ; node size(q) ← t − lo mem max ; lo mem max ← t; link (lo mem max ) ← null ; info(lo mem max ) ← null ; rover ← q; goto restart ; end

This code is used in section 125.

127. Empirical tests show that the routine in this section performs a node-merging operation about 0.75 times per allocation, on the average, after which it finds that r > p + 1 about 95% of the time. ⟨ Try to allocate within node p and its physical successors, and goto found if allocation was possible 127 ⟩ ≡

q ← p + node size(p); { find the physical successor } while is empty (q) do { merge node p with node q }

begin t ← rlink (q);

if q = rover then rover ← t;

llink (t) ← llink (q); rlink (llink (q)) ← t;

q ← q + node size(q);

end; r ← q − s; if r > p + 1 then ⟨ Allocate from the top of node p and goto found 128 ⟩; if r = p then

if rlink (p) ≠ p then ⟨ Allocate entire node p and goto found 129 ⟩; node size(p) ← q − p { reset the size in case it grew }

This code is used in section 125.

128. ⟨ Allocate from the top of node p and goto found 128 ⟩ ≡ begin node size(p) ← r − p; { store the remaining size } rover ← p; { start searching here next time } goto found ; end

This code is used in section 127.

129. Here we delete node p from the ring, and let rover rove around. ⟨ Allocate entire node p and goto found 129 ⟩ ≡

begin rover ← rlink (p); t ← llink (p); llink (rover ) ← t; rlink (t) ← rover ; goto found ; end

This code is used in section 127.

130. Conversely, when some variable-size node p of size s is no longer needed, the operation free node(p, s) will make its words available, by inserting p as a new empty node just before where rover now points. procedure free node(p : pointer ; s : halfword ); { variable-size node liberation }

var q: pointer ; { llink (rover ) } begin node size(p) ← s; link (p) ← empty flag ; q ← llink (rover ); llink (p) ← q; rlink (p) ← rover ;

{ set both links } llink (rover ) ← p; rlink (q) ← p; { insert p into the ring } stat var used ← var used − s; tats { maintain statistics } end; 131. Just before writes out the memory, it sorts the doubly linked available space list. The list is probably very short at such times, so a simple insertion sort is used. The smallest available location will be pointed to by rover , the next-smallest by rlink (rover ), etc.

init procedure sort avail ; { sorts the available variable-size nodes by location } var p, q, r: pointer ; { indices into mem }

old rover : pointer ; { initial rover setting } begin p ← get node(´ 10000000000 ); { merge adjacent free areas } p ← rlink (rover ); rlink (rover ) ← max halfword ; old rover ← rover ; while p ≠ old rover do ⟨ Sort p into the list starting at rover and advance p to rlink (p) 132 ⟩; p ← rover ; while rlink (p) ≠ max halfword do

begin llink (rlink (p)) ← p; p ← rlink (p);

end; rlink (p) ← rover ; llink (rover ) ← p; end; tini

132. The following while loop is guaranteed to terminate, since the list that starts at rover ends with max halfword during the sorting procedure. ⟨ Sort p into the list starting at rover and advance p to rlink (p) 132 ⟩ ≡

if p < rover then begin q ← p; p ← rlink (q); rlink (q) ← rover ; rover ← q; end

else begin q ← rover ; while rlink (q) < p do q ← rlink (q); r ← rlink (p); rlink (p) ← rlink (q); rlink (q) ← p; p ← r; end

This code is used in section 131.