id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc
228	Multics may crash due to Overflow Fault in scheduler (pxss.alm)	Gary Dixon	Eric Swenson	"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.
GHM was running in a 2-CPU Multics configuration with a near R2.0 version of the dps8 simulator.

The Multics process scheduler (pxss.alm) maintains a ""bank account"" of quantum credits that it doles out to work classes containing at least one ready-to-run process in its 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: the time at which the scheduler last ran on this processor.  This gives a delta_t value: the microseconds of quanta 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 delta_t: a double-word fixed bin(71) value.  The right-word 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 ""1""b, the ASQ instruction adds a negative value to the previous tc_data|governing_credit_bank, often causing it to become negative.  Code which assigns those credits (see pxss.alm line 2963++) ignores assignment 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 scheduler 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 since the Overflow Mask indicator bit is off, an Overflow Fault is also triggered.  

That scenario (or some variant) caused an Overflow Fault while running in ring-0,  producing the GHM system to crash.

"	defect	closed	major	MR12.9	Hardcore	MR12.6f	fixed