Section 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 0pt plus 0pt minus 0pt. 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.

constants.h
#define ZERO_GLUE       MEM_BOT                      // specification for 0pt plus 0pt minus 0pt
#define FIL_GLUE        (ZERO_GLUE + GLUE_SPEC_SIZE) // 0pt plus 1fil minus 0pt
#define FILL_GLUE       (FIL_GLUE + GLUE_SPEC_SIZE)  // 0pt plus 1fill minus 0pt
#define SS_GLUE         (FILL_GLUE + GLUE_SPEC_SIZE) // 0pt plus 1fil minus 1fil
#define FIL_NEG_GLUE    (SS_GLUE + GLUE_SPEC_SIZE)   // 0pt plus -1fil minus 0pt
// largest statically allocated word in the variable-size |mem|
#define LO_MEM_STAT_MAX (FIL_NEG_GLUE + GLUE_SPEC_SIZE - 1) 

#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

Section 163

The following code gets mem off to a good start, when is initializing itself the slow way.

⟨ Local variables for initialization 19 ⟩+≡

int k; // index into |mem|, |eqtb|, etc

Section 164

⟨ Initialize table entries (done by INITEX only) 164 ⟩≡

for(k = MEM_BOT + 1; k <= LO_MEM_STAT_MAX; k++) {
    mem[k].sc = 0; // all glue dimensions are zeroed
}
k = MEM_BOT;
while (k <= LO_MEM_STAT_MAX) {
    // set first words of glue specifications
    glue_ref_count(k) = null + 1;
    stretch_order(k) = NORMAL;
    shrink_order(k) = NORMAL;
    k += GLUE_SPEC_SIZE;
}

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;

// now initialize the dynamic memory
rover = LO_MEM_STAT_MAX + 1;
link(rover) = EMPTY_FLAG;
// which is a 1000-word available node
node_size(rover) = 1000;
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; k <= MEM_TOP; k++) {
    mem[k] = mem[lo_mem_max]; // clear list heads
}

// << Initialize the special list heads and constant nodes, 790 >>

// initialize the one-word memory
avail = null;
mem_end = MEM_TOP;
hi_mem_min = HI_MEM_STAT_MIN;
// initialize statistics
var_used = LO_MEM_STAT_MAX + 1 - MEM_BOT;
dyn_used = HI_MEM_STAT_USAGE;

See also sections 222, 228, 232, 240, 250, 258, 552, 946, 951, 1216, 1301, and 1369.

This code is used in section 8.

Section 165

If 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 is_free and was_free that are present only if ’s debugging routines have been included. (You may want to decrease the size of mem while you are debugging.)

NOTE

The free array has been renamed free_cells since “free” is a reserved word in C.

⟨ Global variables 13 ⟩+≡

#ifdef DEBUG
bool free_cells[MEM_MAX + 1]; // free_cells
bool was_free[MEM_MAX + 1];   // previously free cells
pointer was_mem_end, was_lo_max, was_hi_min; // previous |mem_end|, |lo_mem_max|, and |hi_mem_min|
bool panicking; // do we want to check memory constantly?
#endif

Section 166

⟨ Set initial values of key variables 21 ⟩+≡

#ifdef DEBUG
was_mem_end = MEM_MIN; // indicate that everything was previously free
was_lo_max = MEM_MIN;
was_hi_min = MEM_MAX;
panicking = false;
#endif

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

memory.c
#ifdef DEBUG
void check_mem(bool print_locs) {
    pointer p, q;   // current locations of interest in |mem|
    bool clobbered; // is something amiss?
    for(p = MEM_MIN; p <= lo_mem_max; p++) {
        free_cells[p] = false; // you can probably do this faster
    }
    for(p = hi_mem_min; p <= mem_end; p++) {
        free_cells[p] = false; // ditto
    }
    // << Check single-word |avail| list, 168 >>
    // << Check variable-size |avail| list, 169 >>
    // << Check flags of unavailable nodes, 170 >>
    if (print_locs) {
        // << Print newly busy locations, 171 >>
    }
    for(p = MEM_MIN; p <= lo_mem_max; p++) {
        was_free[p] = free_cells[p];
    }
    for(p = hi_mem_min; p <= mem_end; p++) {
        was_free[p] = free_cells[p];
    }
    was_mem_end = mem_end;
    was_lo_max = lo_mem_max;
    was_hi_min = hi_mem_min;
}
#endif

Section 168

⟨ Check single-word avail list 168 ⟩≡

p = avail;
q = null;
while (p != null) {
    if (p > mem_end
        || p < hi_mem_min
        || free_cells[p])
    {
        print_nl("AVAIL list clobbered at ");
        print_int(q);
        break; // Goto done1
    }
    free_cells[p] = true;
    q = p;
    p = link(q);
}
// done1:

This code is used in section 167.

Section 169

⟨ Check variable-size avail list 169 ⟩≡

p = rover;
q = null;
do {
    if (p >= lo_mem_max
        || p < MEM_MIN
        || rlink(p) >= lo_mem_max
        || rlink(p) < MEM_MIN
        || !is_empty(p)
        || node_size(p) < 2
        || p + node_size(p) > lo_mem_max
        || llink(rlink(p)) != p)
    {
        print_nl("Double-AVAIL list clobbered at ");
        print_int(q);
        goto done2;
    }
    for(q = p;  q < (p + node_size(p)); q++) {
        if (free_cells[q]) {
            print_nl("Doubly free location at ");
            print_int(q);
            goto done2;
        }
        free_cells[q] = true;
    }
    q = p;
    p = rlink(p);
} while (p != rover);
done2:

This code is used in section 167.

Section 170

⟨ Check flags of unavailable nodes 170 ⟩≡

p = MEM_MIN;
while (p <= lo_mem_max) {
    // node |p| should not be empty
    if (is_empty(p)) {
        print_nl("Bad flag at ");
        print_int(p);
    }
    while (p <= lo_mem_max && !free_cells[p]) {
        incr(p);
    }
    while (p <= lo_mem_max && free_cells[p]) {
        incr(p);
    }
}

This code is used in section 167.

Section 171

⟨ Print newly busy locations 171 ⟩≡

print_nl("New busy locs:");
for(p = MEM_MIN;  p <= lo_mem_max; p++) {
    if (!free_cells[p]
        && (p > was_lo_max || was_free[p]))
    {
        print_char(' ');
        print_int(p);
    }
}
for(p = hi_mem_min; p <= mem_end; p++) {
    if (!free_cells[p] && (p < was_hi_min
        || p > was_mem_end
        || was_free[p]))
    {
        print_char(' ');
        print_int(p);
    }
}

This code is used in section 167.

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

memory.c
#ifdef DEBUG
// look for pointers to |p|
void search_mem(pointer p) {
    int q; // current position being searched
    for(q = MEM_MIN; q <= lo_mem_max; q++) {
        if (link(q) == p) {
            print_nl("LINK(");
            print_int(q);
            print_char(')');
        }
        if (info(q) == p) {
            print_nl("INFO(");
            print_int(q);
            print_char(')');
        }
    }
    for(q = hi_mem_min; q <= mem_end; q++) {
        if (link(q) == p) {
            print_nl("LINK(");
            print_int(q);
            print_char(')');
        }
        if (info(q) == p) {
            print_nl("INFO(");
            print_int(q);
            print_char(')');
        }
    }

    // << 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 >>
}
#endif