#!/usr/bin/env python3
"""Reproduce MEM-16. Standard library only; no host configuration or external I/O."""
from collections import Counter
from fractions import Fraction
from itertools import product
import json
from random import Random

class Buddy:
    def __init__(self, order=4):
        self.order = order
        self.free = [set() for _ in range(order + 1)]
        self.free[order].add(0)
        self.allocated = {}
    def alloc(self, request):
        if not 1 <= request <= 1 << self.order:
            raise ValueError('request must fit the teaching root block')
        k = (request - 1).bit_length()
        j = next((j for j in range(k, self.order + 1) if self.free[j]), None)
        if j is None:
            return None
        b = min(self.free[j]); self.free[j].remove(b)
        while j > k:
            j -= 1; self.free[j].add(b + (1 << j))
        self.allocated[b] = k
        self.check()
        return b, k
    def release(self, b):
        if b not in self.allocated:
            raise ValueError('release requires a currently owned block start')
        k = self.allocated.pop(b)
        while k < self.order and (b ^ (1 << k)) in self.free[k]:
            other = b ^ (1 << k); self.free[k].remove(other)
            b = min(b, other); k += 1
        self.free[k].add(b); self.check()
    def check(self):
        owned = set()
        for k, blocks in enumerate(self.free):
            for b in blocks:
                assert b % (1 << k) == 0 and 0 <= b < (1 << self.order)
                assert (b ^ (1 << k)) not in blocks
                span = set(range(b, b + (1 << k)))
                assert not owned & span; owned |= span
        for b, k in self.allocated.items():
            assert b % (1 << k) == 0
            span = set(range(b, b + (1 << k)))
            assert not owned & span; owned |= span
        assert owned == set(range(1 << self.order))
    def snapshot(self):
        return {'free_by_order': {str(k): sorted(v) for k,v in enumerate(self.free) if v},
                'allocated': {str(b): k for b,k in sorted(self.allocated.items())},
                'free_pages': sum((1 << k)*len(v) for k,v in enumerate(self.free))}

def lru(trace, capacity):
    cache = []; result = []
    for x in trace:
        miss = x not in cache; victim = None
        if not miss:
            cache.remove(x)
        elif len(cache) == capacity:
            victim = cache.pop(0)
        cache.append(x)
        result.append({'page': x, 'miss': miss, 'victim': victim, 'old_to_new': cache[:]})
    return result

def local_lru(trace, quotas):
    caches = {owner: [] for owner in quotas}; result = []
    for x in trace:
        owner = x[0]; cache = caches[owner]; miss = x not in cache; victim = None
        if not miss:
            cache.remove(x)
        elif len(cache) == quotas[owner]:
            victim = cache.pop(0)
        cache.append(x)
        result.append({'page': x, 'miss': miss, 'victim': victim,
                       'old_to_new': {owner: cache[:] for owner,cache in caches.items()}})
    return result

def faults(rows):
    return sum(row['miss'] for row in rows)

def window_counts(seq, width):
    queue = []; count = Counter(); result = []
    for x in seq:
        queue.append(x); count[x] += 1
        if len(queue) > width:
            old = queue.pop(0); count[old] -= 1
            if not count[old]: del count[old]
        result.append(sorted(count))
    return result

def zones_demo():
    free = {'D':4, 'G':6}; reserve = {'D':2, 'G':2}; result = []
    def take(n, eligible, exempt=False):
        for z in eligible:
            if free[z] - n >= (0 if exempt else reserve[z]):
                free[z] -= n
                return z
        return None
    for n, eligible, exempt in [(4,['G','D'],False),(1,['G','D'],False),
                               (1,['G','D'],False),(1,['G','D'],False),
                               (2,['D'],True),(1,['D'],True)]:
        chosen = take(n, eligible, exempt)
        result.append({'request_pages':n,'eligible':eligible,'reserve_exempt':exempt,
                       'chosen':chosen,'free':free.copy()})
    return result

def main():
    if not __debug__:
        raise SystemExit('Run without -O: this checker requires assertions to be enabled.')
    b = Buddy(); a = b.alloc(3)
    assert a == (0,2)
    first = b.snapshot(); b.release(0)
    assert b.free[4] == {0}
    b = Buddy()
    assert [b.alloc(4) for _ in range(4)] == [(0,2),(4,2),(8,2),(12,2)]
    b.release(0); b.release(8)
    before = b.snapshot(); assert b.alloc(8) is None
    assert before == b.snapshot(), 'failed allocation must not mutate state'
    b.release(4); merged = b.snapshot(); assert b.alloc(8) == (0,3)
    after = b.snapshot()
    # Every subset of free individual frames: independent aligned-bitmask oracle.
    mask_states = 0; shape_probes = 0
    for mask in range(1 << 16):
        free = [set() for _ in range(5)]
        for p in range(16):
            if mask & (1 << p): free[0].add(p)
        for k in range(4):
            for start in range(0,16,1 << (k+1)):
                buddy = start + (1 << k)
                if start in free[k] and buddy in free[k]:
                    free[k].remove(start); free[k].remove(buddy); free[k+1].add(start)
        assert sum((1 << k)*len(v) for k,v in enumerate(free)) == mask.bit_count()
        for k in range(5):
            oracle = any((mask & (((1 << (1 << k))-1) << start)) ==
                         (((1 << (1 << k))-1) << start)
                         for start in range(0,16,1 << k))
            assert oracle == any(free[j] for j in range(k,5))
            shape_probes += 1
        mask_states += 1
    # Mixed real allocator transitions; oracle enumerates aligned free chunks.
    rng = Random(1602); mixed = Buddy(); allocator_transitions = 0
    for _ in range(4000):
        if mixed.allocated and rng.randrange(3) == 0:
            mixed.release(rng.choice(sorted(mixed.allocated)))
        else:
            request = rng.randrange(1,17); k = (request-1).bit_length()
            used = {p for b,j in mixed.allocated.items() for p in range(b,b+(1 << j))}
            candidates = [(j,b) for j in range(k,5) for b in range(0,16,1 << j)
                          if not used.intersection(range(b,b+(1 << j)))]
            # A free chunk inside a larger free buddy block will be obtained by splitting.
            possible = bool(candidates)
            result = mixed.alloc(request)
            assert (result is not None) == possible
            if result is not None:
                start,order = result
                assert order == k and not used.intersection(range(start,start+(1 << order)))
        mixed.check(); allocator_transitions += 1
    # A buddy-rounded request must charge the whole physical block to the reserve.
    requested, free_pages, reserve = 3, 5, 2
    charged = 1 << (requested - 1).bit_length()
    assert charged == 4 and free_pages-requested >= reserve and free_pages-charged < reserve
    rounded_budget = {'requested': requested, 'charged': charged, 'free': free_pages,
                      'reserve': reserve, 'accepted': free_pages-charged >= reserve,
                      'free_after_rejection': free_pages}
    zones = zones_demo()
    assert [r['chosen'] for r in zones] == ['G','D','D',None,'D',None]
    assert [r['free'] for r in zones] == [{'D':4,'G':2},{'D':3,'G':2},{'D':2,'G':2},
                                       {'D':2,'G':2},{'D':0,'G':2},{'D':0,'G':2}]
    seq = list('abacbddde'); windows = window_counts(seq,4)
    assert [len(x) for x in windows] == [1,2,2,3,3,4,3,2,2]
    assert len({'Pa','Pb','S'} | {'Qc','Qd','S'}) == 5
    window_tests = lru_tests = 0
    for n in range(9):
        for seq0 in product('abc',repeat=n):
            for width in range(1,6):
                expected = [sorted(set(seq0[max(0,t-width+1):t+1])) for t in range(n)]
                assert window_counts(seq0,width) == expected
                window_tests += 1
            for capacity in range(1,4):
                # Distinct pages since the preceding reference, not the LRU-list code.
                previous = {}; expected = []
                for t,x in enumerate(seq0):
                    miss = x not in previous or len(set(seq0[previous[x]+1:t])) >= capacity
                    expected.append(miss); previous[x] = t
                assert [r['miss'] for r in lru(seq0,capacity)] == expected
                lru_tests += 1
    trace = 'Pa Pb Qx Qy Pa Pb Qz Qw Qu Qv Pa Pb'.split()
    global_rows = lru(trace,4); local_rows = local_lru(trace,{'P':2,'Q':2})
    assert (faults(global_rows),faults(local_rows)) == (10,8)
    assert [r['victim'] for r in global_rows[6:]] == ['Qx','Qy','Pa','Pb','Qz','Qw']
    for owner in ['P','Q']:
        isolated = lru([x for x in trace if x[0] == owner],2)
        assert faults(isolated) == sum(r['miss'] for r in local_rows if r['page'][0] == owner)
    solo = ['Pa','Pb','Pc']*4
    assert (faults(lru(solo,4)),faults(local_lru(solo,{'P':2,'Q':2}))) == (3,12)
    small_faults = faults(lru(list('abc')*4,2)); big_faults = faults(lru(list('abc')*4,3))
    assert (small_faults,big_faults) == (12,3)
    times = [12+5*f for f in [small_faults,big_faults]]
    assert times == [72,27]
    addresses = [256*i for i in range(8)]*3
    small_tlb = lru([a//256 for a in addresses],2)
    huge_tlb = lru([a//1024 for a in addresses],2)
    assert (faults(small_tlb),faults(huge_tlb)) == (24,2)
    assert faults(lru([i//4 for i in list(range(12))*3],2)) == 9
    vpn,offset = divmod(0x1a5f,1024)
    assert (vpn,offset,0x6000+offset) == (6,0x25f,0x625f)
    saving = lambda m,alpha: Fraction(80)*(2*alpha-1)*m-8000
    assert (saving(100,Fraction(1)),saving(101,Fraction(1))) == (0,80)
    assert saving(200,Fraction(3,4)) == 0 and saving(201,Fraction(3,4)) == 40
    exact_mixed = min(m for m in range(1,1000) if m%4 == 0 and saving(m,Fraction(3,4)) > 0)
    assert exact_mixed == 204
    assert all(saving(m,Fraction(1,2)) == -8000 for m in [1,100,10000])
    result = {
        'status':'PASS',
        'buddy':{'request_3_pages':first,'free_0_and_8':before,'release_4':merged,'allocate_8':after},
        'zones':zones,'rounded_block_budget':rounded_budget,
        'working_set_width_4':windows,
        'shared_union_pages':5,
        'replacement':{'global_faults':faults(global_rows),'local_faults':faults(local_rows),
                       'global_rows':global_rows,'local_rows':local_rows,'solo_global_local':[3,12]},
        'thrashing':{'faults':[12,3],'elapsed':[72,27],'useful_fraction':[str(Fraction(12,t)) for t in times]},
        'tlb':{'small_huge_misses':[24,2],'page_faults':0,'reach_bytes':[512,2048],
               'twelve_base_pages_huge_misses':9,'translated_address':hex(0x6000+offset)},
        'numa':{'all_N1_first_profitable':101,'alpha_3_4_expected_first_profitable':201,
                'exact_3_4_ratio_first_profitable':exact_mixed,'half_half_saving':'-8000'},
        'checks':{'free_frame_subsets':mask_states,'aligned_shape_probes':shape_probes,
                  'mixed_allocator_transitions':allocator_transitions,'working_window_cases':window_tests,'lru_reuse_distance_cases':lru_tests},
        'limits':'Finite exhaustive tests supplement, not replace, the stated invariants; models do not measure a host OS.'}
    print(json.dumps(result,ensure_ascii=False,indent=2))

if __name__ == '__main__':
    main()