"""Independent lifecycle oracle; children report observations, never expectations.""" import base64 import hashlib import json import math import os from pathlib import Path import random import re import subprocess import sys import tempfile import time import zlib COMPILE_DEADLINE = 20 RUN_DEADLINE = 12 CLEAN_DEADLINE = 8 ABSENCE_DEADLINE = 8 REAP_MARGIN = 4 SUPERVISOR = r''' import base64, ctypes, hashlib, json, os, signal, subprocess, sys, time args = json.loads(sys.argv[1]) started = time.monotonic() errors = [] def error(where, exc): errors.append([where, type(exc).__name__, str(exc)]) def stat(pid): try: raw = open('/proc/%d/stat' % pid).read() tail = raw[raw.rfind(')') + 2:].split() return {'pid':pid, 'ppid':int(tail[1]), 'state':tail[0], 'start':int(tail[19]), 'pgid':int(tail[2])} except (FileNotFoundError, ProcessLookupError): return None except BaseException as exc: error('stat', exc) return None def table(): result = {} try: names = os.listdir('/proc') except BaseException as exc: error('proc-list', exc) return result for name in names: if name.isascii() and name.isdigit(): item = stat(int(name)) if item: result[item['pid']] = item return result def closure(rows, root, tracked): roots = {root} for pid, start in tracked.items(): item = rows.get(pid) if item and item['start'] == start and item['state'] not in ('Z','X'): roots.add(pid) result = set() changed = True while changed: changed = False for pid, item in rows.items(): if pid != root and (item['ppid'] in roots or item['ppid'] in result) and pid not in result: result.add(pid) changed = True result.update(pid for pid in roots if pid != root) return {pid:rows[pid]['start'] for pid in result if pid in rows} def fresh_signal(pid, start): current = stat(pid) if current and current['start'] == start and current['state'] not in ('Z','X'): try: os.kill(pid, signal.SIGKILL) except (ProcessLookupError, FileNotFoundError): pass except BaseException as exc: error('kill', exc) def reap_adopted(rows, leader): for pid, item in rows.items(): if pid == leader: continue if item['ppid'] == os.getpid() and item['state'] in ('Z','X'): try: got, status = os.waitpid(pid, os.WNOHANG) if got: adopted.append([got, item['start'], status]) except (ChildProcessError, ProcessLookupError): pass except BaseException as exc: error('reap', exc) identity = {'uid':os.getuid(), 'gid':os.getgid(), 'groups':os.getgroups()} supervisor = os.getpid() selfstat = stat(supervisor) leader = None leader_start = None real_rc = None stdout = b'' stderr = b'' timeout = False adopted = [] tracked = {} absence = False leader_reaped = False pipes_done = False pending = None try: libc = ctypes.CDLL(None, use_errno=True) if libc.prctl(36, 1, 0, 0, 0) != 0: raise OSError(ctypes.get_errno(), 'PR_SET_CHILD_SUBREAPER') raw_input = sys.stdin.buffer.read() child = subprocess.Popen(args['argv'], cwd=args['cwd'], stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE, start_new_session=True) leader = child.pid item = stat(leader) if item is None: raise RuntimeError('leader identity unavailable') leader_start = item['start'] tracked[leader] = leader_start pending = raw_input pipes_done = False deadline = started + args['deadline'] while True: real_rc = child.poll() if real_rc is not None: leader_reaped = True rows = table() discovered = closure(rows, supervisor, tracked) tracked.update(discovered) if time.monotonic() >= deadline and (real_rc is None or not pipes_done): timeout = True if timeout or real_rc is not None: for pid, token in discovered.items(): fresh_signal(pid, token) reap_adopted(rows, leader) if not pipes_done: try: stdout, stderr = child.communicate(input=pending, timeout=0.03) pipes_done = True real_rc = child.returncode leader_reaped = True except subprocess.TimeoutExpired: pending = None rows = table() live = closure(rows, supervisor, tracked) for pid, token in live.items(): tracked[pid] = token if pipes_done and real_rc is not None and not live: absence = True break if time.monotonic() > deadline + 3: raise RuntimeError('recovery exceeded margin') time.sleep(0.005) except BaseException as exc: error('execute', exc) if leader is not None: recovery_deadline = min(time.monotonic() + 3, started + args['deadline'] + 3.5) while time.monotonic() < recovery_deadline: try: real_rc = child.poll() leader_reaped = real_rc is not None rows = table() discovered = closure(rows, supervisor, tracked) tracked.update(discovered) for pid, token in discovered.items(): fresh_signal(pid, token) reap_adopted(rows, leader) if not pipes_done: try: stdout, stderr = child.communicate(timeout=0.03) real_rc = child.returncode leader_reaped = True pipes_done = True except subprocess.TimeoutExpired: pass rows = table() live = closure(rows, supervisor, tracked) tracked.update(live) absence = leader_reaped and not live if absence and pipes_done: break except BaseException as second: error('recovery', second) time.sleep(0.005) real_rc = child.poll() leader_reaped = real_rc is not None absence = leader_reaped and not closure(table(), supervisor, tracked) if not absence or not pipes_done: error('recovery', RuntimeError('recovery incomplete')) controlled_rc = 124 if timeout else real_rc meta = dict(identity=identity, supervisor=supervisor, supervisor_start=selfstat['start'] if selfstat else None, leader=leader, leader_start=leader_start, leader_rc=real_rc, leader_reaped=leader_reaped, timeout=timeout, controlled_rc=controlled_rc, absence=absence, pgid=leader, pg_absence=absence, errors=errors, elapsed=time.monotonic()-started, deadline=args['deadline'], stdout_length=len(stdout), stderr_length=len(stderr), stdout_sha256=hashlib.sha256(stdout).hexdigest(), stderr_sha256=hashlib.sha256(stderr).hexdigest(), adopted=adopted, tracked=sorted(tracked.items()), argv=args['argv']) wire = dict(meta=meta, stdout=base64.b64encode(stdout).decode(), stderr=base64.b64encode(stderr).decode()) sys.stdout.write(json.dumps(wire, separators=(',',':'))) ''' CLEAN = 'import shutil,sys; shutil.rmtree(sys.argv[1])' ABSENCE = '''import os,sys try: os.lstat(sys.argv[1]) except FileNotFoundError: raise SystemExit(0) raise SystemExit(1) ''' def sha(raw): return hashlib.sha256(raw).hexdigest() def compact(record): raw = json.dumps(record, sort_keys=True, separators=(',', ':')).encode() sys.stderr.write('RCMETA:' + base64.b64encode(zlib.compress(raw, 9)).decode() + '\n') def validate(meta, output, diagnostic, deadline, argv): required = {'identity','supervisor','supervisor_start','leader','leader_start','leader_rc','leader_reaped', 'timeout','controlled_rc','absence','pgid','pg_absence','errors','elapsed','deadline','stdout_length','stderr_length', 'stdout_sha256','stderr_sha256','adopted','tracked','argv'} if not isinstance(meta, dict) or not required.issubset(meta): raise ValueError('incomplete execution metadata') for key in ('supervisor','supervisor_start','leader','leader_start'): if type(meta[key]) is not int or meta[key] <= 0: raise ValueError('invalid process identity') if meta['supervisor'] == meta['leader']: raise ValueError('leader identity conflict') expected_uid = 65534 if os.environ.get('ROLLOUT_GRADE_ISOLATION') == 'uid65534' else os.getuid() expected_gid = 65534 if expected_uid == 65534 else os.getgid() expected_groups = [] if expected_uid == 65534 else os.getgroups() identity = meta['identity'] if (not isinstance(identity, dict) or set(identity) != {'uid','gid','groups'} or type(identity['uid']) is not int or type(identity['gid']) is not int or not isinstance(identity['groups'], list) or any(type(group) is not int for group in identity['groups'])): raise ValueError('invalid execution identity types') if identity != {'uid':expected_uid,'gid':expected_gid,'groups':expected_groups}: raise ValueError('execution identity conflict') elapsed = meta['elapsed'] if type(elapsed) not in (int,float) or not math.isfinite(elapsed) or not 0 <= elapsed <= deadline + REAP_MARGIN: raise ValueError('invalid execution elapsed') if type(meta['deadline']) not in (int,float) or meta['deadline'] != deadline: raise ValueError('deadline conflict') if type(meta['pgid']) is not int or meta['pgid'] != meta['leader']: raise ValueError('process group conflict') for key in ('leader_reaped','timeout','absence','pg_absence'): if type(meta[key]) is not bool: raise ValueError('invalid bool metadata') for key in ('leader_rc','controlled_rc'): if type(meta[key]) is not int: raise ValueError('invalid return code') if meta['controlled_rc'] != (124 if meta['timeout'] else meta['leader_rc']): raise ValueError('controlled return code conflict') for name, raw in [('stdout',output),('stderr',diagnostic)]: if type(meta[name+'_length']) is not int or meta[name+'_length'] < 0 or meta[name+'_length'] != len(raw): raise ValueError('invalid IO length') if meta[name+'_sha256'] != sha(raw): raise ValueError('IO digest conflict') if not isinstance(meta['errors'],list) or meta['errors']: raise ValueError('execution exceptions present') if not isinstance(meta['tracked'],list) or not isinstance(meta['adopted'],list): raise ValueError('invalid descendant metadata') if meta['argv'] != argv: raise ValueError('argv conflict') if not meta['leader_reaped'] or not meta['absence'] or not meta['pg_absence']: raise ValueError('process cleanup unconfirmed') if meta['timeout'] or meta['leader_rc'] != 0 or meta['controlled_rc'] != 0: raise ValueError('controlled rejection rc=%s timeout=%s' % (meta['leader_rc'],meta['timeout'])) def execute(stage, argv, cwd, data, deadline, records): payload = dict(argv=argv,cwd=str(cwd),deadline=deadline) completed = subprocess.run([sys.executable,'-I','-c',SUPERVISOR,json.dumps(payload)], input=data,capture_output=True,timeout=deadline+REAP_MARGIN+2) record = dict(stage=stage,wrapper_rc=completed.returncode,wire_length=len(completed.stdout), wire_sha256=sha(completed.stdout),wrapper_stderr_length=len(completed.stderr), wrapper_stderr_sha256=sha(completed.stderr)) records.append(record) if completed.returncode != 0: raise ValueError('supervisor nonzero') wire = json.loads(completed.stdout) output = base64.b64decode(wire['stdout'],validate=True) diagnostic = base64.b64decode(wire['stderr'],validate=True) record['meta'] = wire['meta'] validate(record['meta'],output,diagnostic,deadline,argv) return output class Oracle: def __init__(self): self.nodes = {} self.held = {} self.resources = {} self.next = 1 self.counts = [0]*5 self.fail = False self.events = [] def event(self, kind, object, argument=0): self.events.extend([kind, object, argument]) def finish(self, handle): node = self.nodes[handle] if node['closing'] and not node['writer'] and not node['tickets']: obj = node['resource'] self.resources[obj][1] = False self.counts[3] += 1 self.event(8,obj) self.resources[obj][0] = False self.counts[1] += 1 self.event(9,obj) del self.nodes[handle] def available(self, handle): if handle not in self.nodes: return 4 if self.nodes[handle]['closing']: return 6 return 0 def operation(self, line): self.events = [] if '\v' in line or '\f' in line: return self.view(1,-777,-888) fields = re.split(r'[ \t\r]+',line.strip(' \t\r')) op = fields[0] arities = {'C':2,'W':2,'B':2,'E':1,'X':1,'S':1,'K':2,'A':1,'F':0,'Q':0} rc, value, version = 1,-777,-888 if op not in arities or len(fields) != arities[op]+1: return self.view(rc,value,version) nums = [int(x) for x in fields[1:]] h = nums[0] if nums else 0 node = self.nodes.get(h) if op == 'F': self.fail = True rc = 0 elif op == 'Q': rc = 0 elif op == 'C': if not 1 <= h <= 1000000: rc = 1 elif node: rc = 3 else: obj = self.next self.next += 1 self.counts[0] += 1 self.event(1,obj) if self.fail: self.fail = False self.resources[obj] = [False,False,0,False] self.counts[1] += 1 self.event(3,obj) self.event(9,obj) rc = 5 else: self.counts[2] += 1 self.event(2,obj) self.resources[obj] = [True,True,0,False] self.nodes[h] = dict(resource=obj,value=nums[1],version=0,tickets=set(),writer=False,closing=False) rc = 0 elif op == 'B': rc = self.available(h) ticket = nums[1] if rc == 0: if not 1 <= ticket <= 1000000: rc = 1 elif ticket in self.held: rc = 3 elif node['writer']: rc = 2 else: node['tickets'].add(ticket) value,version = node['value'],node['version'] self.held[ticket] = [h,value,version] self.resources[node['resource']][2] += 1 self.event(4,node['resource'],len(node['tickets'])) elif op == 'E': if h not in self.held: rc = 4 else: owner = self.held.pop(h)[0] node = self.nodes[owner] node['tickets'].remove(h) self.resources[node['resource']][2] -= 1 self.event(5,node['resource'],len(node['tickets'])) self.finish(owner) rc = 0 elif op == 'X': if not node: rc = 4 else: node['closing'] = True self.finish(h) rc = 0 elif op in ('S','W'): rc = self.available(h) if rc == 0: if node['writer'] or node['tickets']: rc = 2 else: self.event(6,node['resource']) if op == 'S': node['writer'] = True self.resources[node['resource']][3] = True else: node['value'] = nums[1] node['version'] += 1 self.event(7,node['resource']) elif op in ('K','A'): if not node: rc = 4 elif not node['writer']: rc = 1 else: if op == 'K': node['value'] = nums[1] node['version'] += 1 node['writer'] = False self.resources[node['resource']][3] = False self.event(7,node['resource']) self.finish(h) rc = 0 return self.view(rc,value,version) def view(self,rc,value,version): result = [rc,value,version]+self.counts[:] result += [sum(int(row[index]) for row in self.resources.values()) for index in range(4)] result += [len(self.nodes)] for handle,node in sorted(self.nodes.items()): result += [handle,int(node['closing']),node['resource'],node['value'],node['version'],len(node['tickets']),int(node['writer'])] result += [len(self.held)] for ticket,row in sorted(self.held.items()): result += [ticket]+row result += [len(self.events)//3]+self.events return result def cases(): lines = ['C 7 0','W 7 42','B 7 101','E 101','X 7','Q', 'C 9 6','B 9 301','B 9 302','X 9','X 9','B 9 303','W 9 99','S 9','E 301','E 302','X 9', 'F','F','C 0 5','C 7 81','C 7 -1000000000000','C 7 5','S 7','B 7 2','W 7 8','X 7','K 7 1000000000000','Q', 'C 1000000 -9','S 1000000','X 1000000','A 1000000','C 1000001 0','E 0','K 1 5','A 1','', 'Q x','B 1','unknown 1'] rng=random.Random(1022315) for cycle in range(60): h=10+cycle%13 t=1000+cycle*3 initial=rng.randrange(-10**12,10**12) lines += [f'C {h} {initial}', f'B {h} {t}',f'B {h} {t+1}',f'W {h} {rng.randrange(-1000,1000)}'] if cycle%2: lines += [f'X {h}',f'B {h} {t+2}',f'E {t+1}',f'E {t}'] else: lines += [f'E {t}',f'E {t+1}',f'S {h}',f'X {h}',(f'K {h} {initial//7}' if cycle%4 else f'A {h}')] lines += [f'C {h} {initial}',f'W {h} {initial+1}',f'X {h}'] for i in range(350): op=rng.choice(['C','W','B','E','X','S','K','A','F','Q']) h=rng.choice([0,1,2,3,4,5,999999,1000000,1000001]) t=rng.randrange(1,19) if op in ('C','W','K'): line=f'{op} {h} {rng.randrange(-1000000,1000000)}' elif op=='B':line=f'B {h} {t}' elif op=='E':line=f'E {t}' elif op in ('F','Q'):line=op else:line=f'{op} {h}' lines.append(line) lines += ['C 61 5','B 61 0','B 61 1000001','B 61 1000000','B 61 1000000','C 62 3','B 62 1000000','E 1000000','X 61','X 62','C\v80 5','C\f80 5','C 80\v5','C 80\f5','Q\v','Q\f','X\v7','B 7\f8','Q',' C\t+00042\t-0009\r','B 42 +001234','X 42','E 1234','Q'] model=Oracle() expected=[model.operation(line) for line in lines] return ('\n'.join(lines)+'\n').encode('ascii'),expected def integer(raw): if re.fullmatch(rb'[+-]?[0-9]+',raw) is None: raise ValueError('non ASCII decimal token') negative = raw.startswith(b'-') digits = raw.lstrip(b'+-').lstrip(b'0') or b'0' if len(digits)>16: raise ValueError('observable integer outside public bounds') return (-1 if negative else 1)*int(digits) def observations(raw): lines=raw.split(b'\n') if lines[-1:] == [b'']:lines.pop() result=[] for line in lines: stripped=line.strip(b' \t\r') tokens=re.split(rb'[ \t\r]+',stripped) result.append([integer(token) for token in tokens]) return result def main(): records=[] errors=[] success=False cleaned=False absent=False scratch=None try: source=Path(sys.argv[1])/'cache.cpp' candidate=source.read_bytes() support=json.loads((Path(__file__).parent/'context.json').read_text()) data,expected=cases() scratch=Path(tempfile.mkdtemp(prefix='reader-cache-')) work=scratch/'build' work.mkdir(mode=0o777) os.chmod(work,0o777) (work/'cache.cpp').write_bytes(candidate) for name,body in support.items(): (work/name).write_text(body) for path in work.iterdir(): os.chmod(path,0o644) compiler=['g++','-std=c++17','-O2','-Wall','-Wextra','-pedantic','cache.cpp','pool.cpp','observe.cpp','-o','replay'] execute('compiler',compiler,work,b'',COMPILE_DEADLINE,records) output=execute('candidate',['./replay'],work,data,RUN_DEADLINE,records) got=observations(output) if got != expected: first=next((i for i,(actual,wanted) in enumerate(zip(got,expected)) if actual!=wanted),min(len(got),len(expected))) raise ValueError('normal observation difference row=%d observed_rows=%d expected_rows=%d' % (first,len(got),len(expected))) success=True except BaseException as exc: errors.append(['main',type(exc).__name__,str(exc)]) finally: if scratch is not None: try: execute('cleanup',[sys.executable,'-I','-c',CLEAN,str(scratch)],'/',b'',CLEAN_DEADLINE,records) cleaned=True except BaseException as exc: errors.append(['cleanup',type(exc).__name__,str(exc)]) try: execute('absence',[sys.executable,'-I','-c',ABSENCE,str(scratch)],'/',b'',ABSENCE_DEADLINE,records) absent=True except BaseException as exc: errors.append(['absence',type(exc).__name__,str(exc)]) compact(dict(records=records,errors=errors,success=success,cleaned=cleaned,absent=absent)) if success and cleaned and absent and not errors: print('PASS') return 0 print('FAIL lifecycle validation') return 1 if __name__=='__main__': sys.exit(main())