Multics may crash due to Overflow Fault in scheduler (pxss.alm)

[Gary Dixon]

This bug description resulted from dump analysis of a system crash on Eric Swenson's GHM system on March 1, 2021. Details of the dump analysis will be attached as later comments to this bug description.

The Multics process scheduler (pxss.alm) maintains a "bank account" of quantum credits that it doles out to work classes containing a ready-to-run process in the work class queue. These credits are refreshed on a per-CPU basis each time the scheduler is invoked on that CPU. The pxss label "compute_virtual_clocks" is preceded by a comment suggesting its purpose is to split idle CPU time among the various categories of idle. However, one of its initial functions is to measure the number of microseconds that have elapsed since pxss last ran on this CPU, and to add those microseconds (which it calls delta_t) to the tc_data|governing_credit_bank: a one-word data field manipulated as a signed fixed bin(35) integer by the referencing instructions.

The ALM listing for the code in question is shown below.

    004300                        3893  compute_virtual_clocks:
    004300  4a  4 00152 3521 20   3894            eppbp     pds$apt_ptr,*       set bp to this process
    004301  4a  4 00262 2351 20   3895            lda       pds$page_waits      copy page fault count into APT entry
    004302  aa  2 00002 7551 00   3896            sta       bp|apte.page_faults
    004303  aa  2 00046 2371 00   3897            ldaq      bp|apte.virtual_cpu_time Remember bp's vcpu
    004304  aa  6 00134 7571 00   3898            staq      temp                Use temp for delta virtual time.
                                  3899
                                  3900            read_clock
    004305  4a  4 00104 6331 20                   rccl      sys_info$clock_,*
    004306  aa  3 00034 7571 00   3901            staq      bb|last_time        save last time anyone run
    004307  4a  4 00324 1771 20   3902            sbaq      prds$last_recorded_time delta t in microseconds
    004310  aa  6 00154 7571 00   3903            staq      delta_t
    004311  aa  3 00451 0561 00   3904            asq       bb|governing_credit_bank

Beginning at line 3900, the read_clock macro reads the system's calendar clock into the AQ register as a signed fixed bin(71) integer. It saves this clock reading into tc_data|last_time to record when the scheduler last ran on any processor. It then subtracts from this time stamp the value prds$last_recorded_time (which is the time at which the scheduler last ran on this processor). This gives a delta_t value, the microseconds of quanta that can be added to tc_data|governing_bank_credit, which is also a signed fixed bin(71) integer value. [See lines 3902-3903 above.]

The problem occurs in the ASQ instruction on line 3904. That instruction uses signed arithmetic to add two single-word integers together: C(Q) + C(Y) -> C(Y). In this case, Y is the address of tc_data|governing_credit_bank, a fixed bin(35) signed value. Q contains the right word of a double-word fixed bin(71) value; it is effectively an unsigned fixed bin(36) integer. But the ASQ instruction treats Q as a signed fixed bin(35) value, with the left-most bit in this word being the sign bit.

In situations where that sign bit is negative, the ASQ can add a negative value to the previous tc_data|governing_credit_bank, causing it to become negative. Code which assigns those credits (see pxss.alm line 2963++) ignore assignments of credits if the bank value is negative. Thus the negative tc_data|govern_credit_bank value remains negative when scheduling ends on that CPU.

The next time the schedules runs on that CPU, if the delta_t value has a right-word storage that again looks like a negative integer, that negative value again gets added to the still-negative tc_data|governing_credit_bank value. This process can continue until the ASQ instruction overflows the negative range of the fixed bin(35) signed storage space. ASQ then turns on the Overflow indicator bit. And if the Overflow Mask indicator bit is off, then an Overflow Fault is triggered. That scenario (or some variant), and Overflow Fault while running in ring-0, is what caused the GHM system to crash.