58  PART 11: MEMORY LAYOUT  TEX82 §162

162. Memory layout. Some areas of mem are dedicated to fixed usage, since static allocation is more efficient than dynamic allocation when we can get away with it. For example, locations mem bot to mem bot + 3 are always used to store the specification for glue that is ‘ ’. The following macro definitions accomplish the static allocation by giving symbolic names to the fixed positions. Static variable-size nodes appear in locations mem bot through lo mem stat max , and static single-word nodes appear in locations hi mem stat min through mem top, inclusive. It is harmless to let lig trick and garbage share the same location of mem.

define zero glue ≡ mem bot { specification for } define fil glue ≡ zero glue + glue spec size { } define fill glue ≡ fil glue + glue spec size { } define ss glue ≡ fill glue + glue spec size { } define fil neg glue ≡ ss glue + glue spec size { } define lo mem stat max ≡ fil neg glue + glue spec size − 1

{ largest statically allocated word in the variable-size mem }

define page ins head ≡ mem top { list of insertion data for current page } define contrib head ≡ mem top − 1 { vlist of items not yet on current page } define page head ≡ mem top − 2 { vlist for current page } define temp head ≡ mem top − 3 { head of a temporary list of some kind } define hold head ≡ mem top − 4 { head of a temporary list of another kind } define adjust head ≡ mem top − 5 { head of adjustment list returned by hpack } define active ≡ mem top − 7 { head of active list in line break , needs two words } define align head ≡ mem top − 8 { head of preamble list for alignments } define end span ≡ mem top − 9 { tail of spanned-width lists } define omit template ≡ mem top − 10 { a constant token list } define null list ≡ mem top − 11 { permanently empty list } define lig trick ≡ mem top − 12 { a ligature masquerading as a char node } define garbage ≡ mem top − 12 { used for scrap information } define backup head ≡ mem top − 13 { head of token list built by scan keyword } define hi mem stat min ≡ mem top − 13 { smallest statically allocated word in the one-word mem } define hi mem stat usage = 14 { the number of one-word nodes always present }

§164  TEX82  PART 11: MEMORY LAYOUT 59

163. The following code gets mem off to a good start, when TEX is initializing itself the slow way. ⟨ Local variables for initialization 19 ⟩ +≡ k: integer ; { index into mem, eqtb, etc. } 164. ⟨ Initialize table entries (done by only) 164 ⟩ ≡

for k ← mem bot + 1 to lo mem stat max do mem[k].sc ← 0; { all glue dimensions are zeroed } k ← mem bot ; while k ≤ lo mem stat max do { set first words of glue specifications }

begin glue ref count (k) ← null + 1; stretch order (k) ← normal ; shrink order (k) ← normal ; k ← k + glue spec size; end;

stretch(fil glue) ← unity ; stretch order (fil glue) ← fil ; stretch(fill glue) ← unity ; stretch order (fill glue) ← fill ; stretch(ss glue) ← unity ; stretch order (ss glue) ← fil ; shrink (ss glue) ← unity ; shrink order (ss glue) ← fil ; stretch(fil neg glue) ← −unity ; stretch order (fil neg glue) ← fil ; rover ← lo mem stat max + 1; link (rover ) ← empty flag ; { now initialize the dynamic memory } node size(rover ) ← 1000; { which is a 1000-word available node } llink (rover ) ← rover ; rlink (rover ) ← rover ; lo mem max ← rover + 1000; link (lo mem max ) ← null ; info(lo mem max ) ← null ; for k ← hi mem stat min to mem top do mem[k] ← mem[lo mem max ]; { clear list heads } ⟨ Initialize the special list heads and constant nodes 790 ⟩; avail ← null ; mem end ← mem top; hi mem min ← hi mem stat min;

{ initialize the one-word memory } var used ← lo mem stat max + 1 − mem bot ; dyn used ← hi mem stat usage; { initialize statistics }

See also sections 222, 228, 232, 240, 250, 258, 552, 946, 951, 1216, 1301, and 1369. This code is used in section 8.

165. If TEX is extended improperly, the mem array might get screwed up. For example, some pointers might be wrong, or some “dead” nodes might not have been freed when the last reference to them disappeared. Procedures check mem and search mem are available to help diagnose such problems. These procedures make use of two arrays called free and was free that are present only if TEX’s debugging routines have been included. (You may want to decrease the size of mem while you are debugging.) ⟨ Global variables 13 ⟩ +≡

debug free: packed array [mem min . . mem max ] of boolean; { free cells } was free: packed array [mem min . . mem max ] of boolean; { previously free cells } was mem end , was lo max , was hi min: pointer ; { previous mem end , lo mem max , and hi mem min } panicking : boolean; { do we want to check memory constantly? } gubed

166. ⟨ Set initial values of key variables 21 ⟩ +≡ debug was mem end ← mem min; { indicate that everything was previously free } was lo max ← mem min; was hi min ← mem max ; panicking ← false; gubed 167. Procedure check mem makes sure that the available space lists of mem are well formed, and it optionally prints out all locations that are reserved now but were free the last time this procedure was called.

debug procedure check mem(print locs : boolean); label done1 , done2 ; { loop exits } var p, q: pointer ; { current locations of interest in mem }

clobbered : boolean; { is something amiss? } begin for p ← mem min to lo mem max do free[p] ← false; { you can probably do this faster } for p ← hi mem min to mem end do free[p] ← false; { ditto } ⟨ Check single-word avail list 168 ⟩; ⟨ Check variable-size avail list 169 ⟩; ⟨ Check flags of unavailable nodes 170 ⟩; if print locs then ⟨ Print newly busy locations 171 ⟩; for p ← mem min to lo mem max do was free[p] ← free[p]; for p ← hi mem min to mem end do was free[p] ← free[p]; { was free ← free might be faster } was mem end ← mem end ; was lo max ← lo mem max ; was hi min ← hi mem min; end; gubed

168. ⟨ Check single-word avail list 168 ⟩ ≡ p ← avail ; q ← null ; clobbered ← false; while p ≠ null do

begin if (p > mem end ) ∨ (p < hi mem min) then clobbered ← true else if free[p] then clobbered ← true;

if clobbered then

begin print nl ( ␣ ␣ ␣ ␣ ); print int (q); goto done1 ; end;

free[p] ← true; q ← p; p ← link (q);

end; done1 :

This code is used in section 167.

169. ⟨ Check variable-size avail list 169 ⟩ ≡ p ← rover ; q ← null ; clobbered ← false; repeat if (p ≥ lo mem max ) ∨ (p < mem min) then clobbered ← true

else if (rlink (p) ≥ lo mem max ) ∨ (rlink (p) < mem min) then clobbered ← true

else if ¬(is empty (p)) ∨ (node size(p) < 2) ∨ (p + node size(p) > lo mem max ) ∨

(llink (rlink (p)) ≠ p) then clobbered ← true;

if clobbered then

begin print nl ( ␣ ␣ ␣ ␣ ); print int (q); goto done2 ; end;

for q ← p to p + node size(p) − 1 do { mark all locations free }

begin if free[q] then begin print nl ( ␣ ␣ ␣ ␣ ); print int (q); goto done2 ; end; free[q] ← true; end;

q ← p; p ← rlink (p); until p = rover ;

done2 :

This code is used in section 167.

170. ⟨ Check flags of unavailable nodes 170 ⟩ ≡ p ← mem min; while p ≤ lo mem max do { node p should not be empty }

begin if is empty (p) then begin print nl ( ␣ ␣ ␣ ); print int (p); end;

while (p ≤ lo mem max ) ∧ ¬free[p] do incr (p);

while (p ≤ lo mem max ) ∧ free[p] do incr (p);

end

This code is used in section 167.

171. ⟨ Print newly busy locations 171 ⟩ ≡ begin print nl ( ␣ ␣ ); for p ← mem min to lo mem max do

if ¬free[p] ∧ ((p > was lo max ) ∨ was free[p]) then begin print char ( ␣ ); print int (p); end;

for p ← hi mem min to mem end do

if ¬free[p] ∧ ((p < was hi min) ∨ (p > was mem end ) ∨ was free[p]) then begin print char ( ␣ ); print int (p); end;

end

This code is used in section 167.

172. The search mem procedure attempts to answer the question “Who points to node p?” In doing so, it fetches link and info fields of mem that might not be of type two halves . Strictly speaking, this is undefined in Pascal, and it can lead to “false drops” (words that seem to point to p purely by coincidence). But for debugging purposes, we want to rule out the places that do not point to p, so a few false drops are tolerable.

debug procedure search mem(p : pointer ); { look for pointers to p } var q: integer ; { current position being searched } begin for q ← mem min to lo mem max do

begin if link (q) = p then begin print nl ( ); print int (q); print char ( ); end;

if info(q) = p then begin print nl ( ); print int (q); print char ( ); end;

end; for q ← hi mem min to mem end do

begin if link (q) = p then begin print nl ( ); print int (q); print char ( ); end;

if info(q) = p then begin print nl ( ); print int (q); print char ( ); end;

end; ⟨ Search eqtb for equivalents equal to p 255 ⟩; ⟨ Search save stack for equivalents that point to p 285 ⟩; ⟨ Search hyph list for pointers to p 933 ⟩; end; gubed