3.2.5 Constraints and Invariants

The text in the preceding sections ignores the complication of interfering, interlaced list manipulation by concurrent threads.

Fortuitously, if all threads obey the rules for performing list operations, and the program they run under is correct, certain properties of the descriptor list are guaranteed:

• While a thread holds a block allocated, the corresponding descriptor cannot become unused (that is, it cannot be made unused by a different thread).
• While a thread holds a block allocated, the allocd, addr and nxt fields of the corresponding descriptor cannot change.
• While a thread holds a block allocated, the addr field of the descriptor pointed to by the nxt field of the corresponding descriptor cannot change.
• While a descriptor has a non-zero penult field, its addr and nxt fields cannot change.

In addition to these, an implementation of the algorithm must uphold additional, necessary invariants and constraints:

• No unused descriptor may be marked as free.
• A penult field may only be changed from zero to non-zero by a thread attaching a new end-marker to the descriptor list.
• All unused descriptors must have a zero penult field.
• A write to the nxt field of a descriptor must set it to either nil or to point to an in-use descriptor.