"""The counterfactuals behind the commentary. Every one runs against mlfq.py.

    python3 verify_cf.py
"""
from mlfq import Job, MLFQ, DEMOTE_BURST, DEMOTE_ALLOT

Q = (10, 20, 40)


def hogs(policy, quanta=Q, boost=0, yield_at=9, n=2, horizon=1000,
         switch=0, preempt=True, block=0, allots=None):
    jobs = [Job(0, 0, 10 ** 9, yield_after=yield_at, block=block)]
    jobs += [Job(i, 0, 10 ** 9) for i in range(1, n + 1)]
    sim = MLFQ(jobs, quanta=quanta, allots=allots, policy=policy, boost=boost,
               switch=switch, preempt=preempt)
    sim.run(horizon)
    return jobs, sim


print("== CF1: the load-bearing line, flipped ==")
print("mlfq.py:173-178 chooses what 'used too much CPU' means. Same trace,")
print("same jobs, same everything else:")
for pol, name in ((DEMOTE_BURST, "demote = slice_over           (R4-old)"),
                  (DEMOTE_ALLOT, "demote = allot >= allots[lvl] (R4-new)")):
    j, _ = hogs(pol)
    print("  %s  gamer=%4d  honest=%s" % (name, j[0].cpu, [x.cpu for x in j[1:]]))
print("980 -> 135, from one line. Nothing else in the scheduler moved.")
print()

print("== CF2: preemption on wake-up decides the SIGN of the result ==")
print("With a release that really blocks (block=2), whether a waking job")
print("takes the CPU from a lower-priority one is the whole result:")
for pre in (True, False):
    j, s = hogs(DEMOTE_BURST, block=2, preempt=pre)
    print("  preempt=%-5s  gamer=%4d  honest=%s  preemptions=%d"
          % (pre, j[0].cpu, [x.cpu for x in j[1:]], s.preempts))
print("Without preemption the exploit INVERTS: the gamer does worse than the")
print("jobs it was trying to rob. This was a live bug in the prototype.")
print()

print("== CF3: everyone games, and nobody wins ==")
print("  gamers/4   each gamer's cpu       each honest job's cpu")
for k in range(0, 5):
    jobs = [Job(i, 0, 10 ** 9, yield_after=(9 if i < k else None))
            for i in range(4)]
    MLFQ(jobs, quanta=Q, policy=DEMOTE_BURST).run(1000)
    gs = [x.cpu for x in jobs if x.yield_after is not None]
    hs = [x.cpu for x in jobs if x.yield_after is None]
    print("  %d          %-22s %s" % (k, gs if gs else "-", hs if hs else "-"))
print("At 4/4 it is round robin again, and the leader is worse off (252) than")
print("the leader of the honest run (270). The exploit is positional.")
print()

print("== CF4: the closed form, checked ==")
print("The honest jobs each get exactly one top-level quantum, so the gamer")
print("takes horizon - n*quantum[0]. Checked at ten configurations:")
print("  n hogs   quantum   gamer cpu   horizon - n*quantum")
ok = True
for n in (1, 2, 3, 5, 9):
    for q0 in (10, 50):
        j, _ = hogs(DEMOTE_BURST, quanta=(q0, 2 * q0, 4 * q0),
                    yield_at=q0 - 1, n=n)
        pred = 1000 - n * q0
        ok = ok and j[0].cpu == pred
        print("  %6d   %7d   %9d   %19d" % (n, q0, j[0].cpu, pred))
print("all ten exact: %s" % ok)
print()

print("== CF5: the yield point is inert until a release costs something ==")
print("  yield_at   switch=0   switch=1   switch=2   switch=4")
for y in (1, 2, 3, 5, 7, 9):
    row = [hogs(DEMOTE_BURST, yield_at=y, switch=sw)[0][0].cpu
           for sw in (0, 1, 2, 4)]
    print("  %8d   %8d   %8d   %8d   %8d" % (y, row[0], row[1], row[2], row[3]))
print("Column 1 is flat at 980. Every other column rises with the yield point,")
print("and the optimum is quantum-1 in each. The folklore is right about the")
print("strategy and wrong about the reason.")
print()

print("== CF6: the allotment, swept (R4-new) ==")
print("How much rope does the fix give before the exploit returns?")
print("  allot[0]   gamer cpu   honest cpu     (quanta fixed at 10/20/40)")
for a0 in (10, 20, 50, 100, 200, 500, 1000):
    j, _ = hogs(DEMOTE_ALLOT, allots=(a0, 2 * a0, 4 * a0))
    print("  %8d   %9d   %s" % (a0, j[0].cpu, [x.cpu for x in j[1:]]))
print("Even a 100x allotment tops out near round robin (315/345/340), because")
print("the quantum still preempts: a big allotment buys the gamer more time at")
print("level 0, not exclusive possession of it.")
print()

print("== CF7: 400 seeded random configurations ==")


class LCG:
    def __init__(self, seed):
        self.s = seed & 0xFFFFFFFF

    def next(self):
        self.s = (1103515245 * self.s + 12345) & 0x7FFFFFFF
        return self.s

    def pick(self, xs):
        return xs[self.next() % len(xs)]

    def rng(self, lo, hi):
        return lo + self.next() % (hi - lo + 1)


r = LCG(20260803)
wins = {DEMOTE_BURST: 0, DEMOTE_ALLOT: 0}
ratios = {DEMOTE_BURST: [], DEMOTE_ALLOT: []}
worst = None
for _ in range(400):
    n = r.rng(2, 8)
    q0 = r.pick([4, 8, 10, 16, 25, 50])
    nl = r.rng(2, 4)
    quanta = tuple(q0 * 2 ** i for i in range(nl))
    boost = r.pick([0, 0, 100, 200, 500])
    yat = max(1, q0 - r.rng(1, 3))
    arrivals = [r.rng(0, 50) for _ in range(n + 1)]
    for pol in (DEMOTE_BURST, DEMOTE_ALLOT):
        js = [Job(0, arrivals[0], 10 ** 9, yield_after=yat)]
        js += [Job(i, arrivals[i], 10 ** 9) for i in range(1, n + 1)]
        MLFQ(js, quanta=quanta, policy=pol, boost=boost).run(2000)
        fair = sum(x.cpu for x in js) / len(js)
        ratio = js[0].cpu / fair if fair else 0.0
        ratios[pol].append(ratio)
        if ratio > 1.0:
            wins[pol] += 1
        if pol == DEMOTE_BURST and (worst is None or ratio > worst[0]):
            worst = (ratio, n, quanta, boost, yat, js[0].cpu)


def pct(xs, p):
    s = sorted(xs)
    return s[min(len(s) - 1, int(round(p / 100.0 * (len(s) - 1))))]


print("Random job count (2-8), quanta, level count, boost and arrivals.")
print("The gamer's CPU as a multiple of its fair share:")
for pol, name in ((DEMOTE_BURST, "R4-old"), (DEMOTE_ALLOT, "R4-new")):
    xs = ratios[pol]
    print("  %s:  min %.2fx  p25 %.2fx  median %.2fx  p75 %.2fx  max %.2fx"
          "   | above fair share in %d/400"
          % (name, min(xs), pct(xs, 25), pct(xs, 50), pct(xs, 75), max(xs),
             wins[pol]))
print("  worst R4-old case: %.2fx fair share (n=%d, quanta=%s, boost=%d,"
      " yield_at=%d, gamer got %d)" % worst)