"""Independent logical-resource oracle; candidate execution is subprocess-only.""" import collections import hashlib import json import random import subprocess import sys import tempfile from pathlib import Path U64 = (1 << 64) - 1 class Model: def __init__(self): self.reset() def reset(self): self.definitions = [None] * 8 self.active = [0] * 8 self.ordinal = [-1] * 8 self.maps = {} self.next_token = 1 self.history = [0] * 7 def mapping_fields(self, token): m = self.maps[token] return [token, m['owner'], m['index'], m['start'], m['size'], m['reads'], m['writes'], m['fills']] def apply(self, event): command, *args = event result = [] valid_id = lambda value: 0 <= value < 8 if command == 'Z': self.reset() elif command == 'C': device, count, *flat = args resources = [flat[i:i+3] for i in range(0, len(flat), 3)] bad = not valid_id(device) or count > 4 or any( kind not in (1, 2) or not 0 <= start < 65536 or not 1 <= size <= 64 or start + size > 65536 for kind, start, size in resources) if bad: result = [1] elif self.active[device]: result = [2] else: self.definitions[device] = [row[:] for row in resources] result = [0] elif command == 'P': device, ordinal, fault = args token = 0 selected = None if not valid_id(device) or not 0 <= ordinal <= 3 or not 0 <= fault <= 2: code = 1 elif self.active[device]: code = 2 else: memory = [(i, r) for i, r in enumerate(self.definitions[device] or []) if r[0] == 1] if self.definitions[device] is None or ordinal >= len(memory): code = 3 else: selected = memory[ordinal] _, (kind, start, size) = selected overlap = any(start < m['start'] + m['size'] and m['start'] < start + size for m in self.maps.values()) if overlap: code = 4 elif fault == 1: self.history[3] += 1 code = 5 else: token = self.next_token self.next_token += 1 self.history[0] += 1 self.maps[token] = dict(owner=device, index=selected[0], start=start, size=size, reads=0, writes=0, fills=0, data=[0] * size) if fault == 2: del self.maps[token] self.history[1] += 1 self.history[3] += 1 token = 0 code = 5 else: self.active[device] = token self.ordinal[device] = ordinal self.history[2] += 1 code = 0 result = [code, token] elif command == 'X': device, = args if not valid_id(device): result = [1] else: token = self.active[device] if token: del self.maps[token] self.active[device] = 0 self.ordinal[device] = -1 self.history[1] += 1 result = [0] elif command in ('R', 'W'): token, offset, width, *values = args mapping = self.maps.get(token) if mapping is None: code = 6 elif width not in (1, 2, 4): code = 1 elif offset + width > mapping['size']: code = 7 elif command == 'W' and values[0] >= 1 << (width * 8): code = 8 else: code = 0 if command == 'R': value = 0 if not code: value = int.from_bytes(bytes(mapping['data'][offset:offset+width]), 'little') mapping['reads'] += 1 self.history[4] += 1 result = [code, value] else: if not code: mapping['data'][offset:offset+width] = list(values[0].to_bytes(width, 'little')) mapping['writes'] += 1 self.history[5] += 1 result = [code] elif command in ('F', 'B'): token, offset, count, *values = args mapping = self.maps.get(token) if mapping is None: code = 6 elif not 0 <= count <= 64 or (command == 'F' and not 0 <= values[0] <= 255): code = 1 elif offset > mapping['size'] or offset + count > mapping['size']: code = 7 else: code = 0 if command == 'B': data = [] if code else mapping['data'][offset:offset+count] result = [code, len(data), *data] else: if not code: mapping['data'][offset:offset+count] = [values[0]] * count mapping['fills'] += 1 self.history[6] += 1 result = [code] elif command == 'D': device, = args if not valid_id(device): result = [1, 0, 0, 0, 0, -1] else: resources = self.definitions[device] result = [0, int(resources is not None), int(bool(self.active[device])), len(resources or []), self.active[device], self.ordinal[device]] elif command == 'E': device, index = args if not valid_id(device) or not 0 <= index <= 3: result = [1, 0, 0, 0] elif self.definitions[device] is None or index >= len(self.definitions[device]): result = [3, 0, 0, 0] else: result = [0, *self.definitions[device][index]] elif command == 'M': token, = args result = [0, *self.mapping_fields(token)] if token in self.maps else [6, *([0] * 8)] elif command == 'L': tokens = sorted(self.maps, key=lambda token: (self.maps[token]['start'], token)) result = [len(tokens)] for token in tokens: result.extend(self.mapping_fields(token)) elif command == 'S': result = [*self.history, len(self.maps), sum(m['size'] for m in self.maps.values())] else: raise ValueError('unknown trusted event') return command + ((' ' + ' '.join(map(str, result))) if result else '') + '\n' def configure(device, resources): return ['C', device, len(resources), *(value for row in resources for value in row)] def inspect(device, token, size=0): result = [['D', device], ['M', token], ['L'], ['S']] if size: result.append(['B', token, 0, size]) return result def scenes(seeds): result = [('empty', [])] result.append(('smoke', [['Z'], configure(0, [(1,4096,16)]), ['P',0,0,0], ['X',0], ['P',0,0,0]])) events = [['Z']] for device in [-2147483648, -1, *range(8), 8, 2147483647]: events.extend([['D',device],['E',device,0],['X',device],['P',device,0,0]]) for token in (0,1,U64): events.extend([['M',token],['R',token,U64,0],['W',token,U64,0,U64], ['F',token,U64,-1,-1],['B',token,U64,-1]]) events.extend([['L'],['S'],configure(0,[]),['D',0],['E',0,0],['P',0,0,0],['S']]) result.append(('initial_direct_and_stale', events)) events = [['Z']] valid_descriptors = [(1,0,1),(2,65535,1),(1,65472,64),(2,1,64)] for device in range(8): events.append(configure(device, valid_descriptors)) for index in (-1,0,1,2,3,4): events.append(['E',device,index]) events.append(['D',device]) invalid_sets = [[(0,0,1)],[(3,0,1)],[(1,65536,1)],[(1,U64,1)],[(1,0,0)], [(1,0,-1)],[(1,0,65)],[(1,65535,2)],[(1,65500,64)], [(1,1,1),(2,2,1),(1,3,1),(2,4,1),(1,5,1)], [(1,123,4),(2,456,0)]] for resources in invalid_sets: events.extend([configure(0,resources),['D',0],['E',0,0],['E',0,3],['S']]) for device in (-1,8): events.extend([configure(device,[]),configure(device,valid_descriptors),['D',device]]) events.extend([configure(0,[(1,0,1)]),['P',0,0,0]]) for resources in [[],valid_descriptors,*invalid_sets]: events.extend([configure(0,resources),['D',0],['E',0,0],['M',1],['S']]) events.extend([['X',0],configure(0,[(2,9,2)]),['P',0,0,0],['D',0],['E',0,0]]) result.append(('configuration_validation_and_atomicity', events)) events = [['Z'],configure(0,[(2,0,64),(1,200,8),(2,99,1),(1,100,7)])] events.extend([['P',0,2,2],['P',0,0,1],*inspect(0,1),['P',0,0,2],*inspect(0,1), ['P',0,1,0],*inspect(0,2,7)]) for ordinal in (-2147483648,-1,0,1,3,4,2147483647): for fault in (-1,0,1,2,3): events.extend([['P',0,ordinal,fault],['S']]) events.extend([['X',0],['X',0],*inspect(0,2),['R',2,0,1],['W',2,0,1,1], ['F',2,0,1,1],['B',2,0,1],['P',0,0,0],*inspect(0,3,8),['Z'],*inspect(0,3)]) for device in (0,7): events.extend([configure(device,[(1,65535,1)]),['P',device,0,2],['D',device],['S'], ['P',device,0,1],['S'],['P',device,0,0],['L'],['X',device],['L'],['S']]) result.append(('injection_precedence_retry_and_revoke', events)) events = [['Z'],configure(0,[(1,10,1),(1,10,1),(1,20,2),(1,30,4)])] for index in range(4): events.append(['E',0,index]) events.extend([['P',0,3,0],*inspect(0,1,4),['X',0],['P',0,1,0],*inspect(0,2,1), configure(1,[(2,10,1)]),['P',1,0,2],['D',1],['S'], configure(2,[(1,10,1)]),['P',2,0,2],['S'],['X',0],['P',2,0,0], *inspect(2,3,1),['E',0,0],['E',0,1]]) result.append(('ordinal_endpoints_and_duplicate_descriptors', events)) events = [['Z']] windows = [(400,8),(100,8),(108,1),(107,2),(0,64),(65535,1),(164,1),(63,2)] token = 0 for device,(start,size) in enumerate(windows): events.extend([configure(device,[(2,0,64),(1,start,size)]),['P',device,0,0],['D',device],['L'],['S']]) events.extend([['P',3,0,2],['P',7,0,1],['S'],['X',1],['P',3,0,0],['L'],['S'], ['M',1],['M',2],['M',3],['M',7],['E',3,1],['X',0],['D',4],['M',4],['L'],['S']]) result.append(('overlap_adjacency_sorting_isolation', events)) events = [['Z'],configure(0,[(1,1000,8)]),['P',0,0,0],['W',1,4,4,305419896], ['R',1,4,4],*inspect(0,1,8),['W',1,5,4,4294967295],['R',1,5,4], ['W',1,5,4,U64],*inspect(0,1,8)] result.append(('precise_size_minus_4_minus_3', events)) events = [] for size in (1,2,3,4,5,7,8,16,31,63,64): events.extend([['Z'],configure(0,[(1,20,size)]),['P',0,0,0],['F',1,0,size,165]]) for width in (1,2,4): for offset in sorted({0,max(0,size-width),max(0,size-width+1),size-1,size,U64}): value=(1 << (8*width))-1 events.extend([['W',1,offset,width,value],['R',1,offset,width], ['B',1,0,size],['M',1],['S']]) for width in (-2147483648,-1,0,3,5,2147483647): events.extend([['R',1,U64,width],['W',1,U64,width,U64],['M',1],['S']]) events.extend([['W',1,0,1,256],['W',1,0,2,65536],['W',1,0,4,4294967296], ['W',1,U64,1,U64],['R',1,U64,1],['B',1,0,size],['M',1],['S']]) result.append(('full_width_boundary_and_no_partial_effects', events)) events = [['Z'],configure(7,[(1,65472,64)]),['P',7,0,0]] for count in (-2147483648,-1,0,1,2,63,64,65,2147483647): for offset in (0,1,63,64,65,U64): events.extend([['F',1,offset,count,255],['B',1,offset,count],['M',1],['S']]) for value in (-2147483648,-1,0,1,255,256,2147483647): events.extend([['F',1,0,0,value],['F',1,U64,65,value],['B',1,0,64],['S']]) events.extend([['F',1,0,64,0],['W',1,1,4,305419896],['R',1,1,1],['R',1,2,2], ['R',1,1,4],['B',1,0,8],['M',1],['S'],['X',7],['P',7,0,0],['B',2,0,64],['S']]) result.append(('byte_zero_maximum_little_endian', events)) for seed in seeds: rng=random.Random(seed) events=[['Z']] model=Model() for _ in range(260): device=rng.randrange(8) action=rng.choice('CCPPPXRWFFBDEM') tokens=list(model.maps) token=rng.choice(tokens+[0,model.next_token, U64]) if action=='C': resources=[] for _ in range(rng.randrange(5)): resources.append((rng.choice((1,1,2)),rng.choice((0,64,128,65535,rng.randrange(600))),rng.choice((1,4,7,16,64)))) event=configure(device,resources) elif action=='P':event=['P',device,rng.randrange(4),rng.randrange(3)] elif action=='X':event=['X',device] elif action in 'RW': size=model.maps[token]['size'] if token in model.maps else 8 offset=rng.choice((0,1,max(0,size-4),max(0,size-3),size-1,size,U64)) width=rng.choice((1,2,4,0,3)) event=[action,token,offset,width]+([rng.choice((0,255,65535,4294967295,U64))] if action=='W' else []) elif action in 'FB': event=[action,token,rng.choice((0,1,4,64,U64)),rng.choice((-1,0,1,4,64,65))] if action=='F':event.append(rng.choice((-1,0,17,255,256))) elif action=='D':event=['D',device] elif action=='E':event=['E',device,rng.randrange(-1,5)] else:event=['M',token] events.append(event) model.apply(event) for observation in inspect(device,token): events.append(observation) model.apply(observation) events.extend([['Z'],['S'],['L'],['D',0],['M',1]]) result.append(('mixed_seed_'+str(seed),events)) return result def first_difference(actual, expected): limit=min(len(actual),len(expected)) offset=next((i for i in range(limit) if actual[i]!=expected[i]),limit) return 'byte=%d got=%r wanted=%r actual_len=%d expected_len=%d' % ( offset,actual[offset:offset+70],expected[offset:offset+70],len(actual),len(expected)) def main(): config=json.loads(Path(__file__).with_name('cases.json').read_text()) prepared=[] for name,events in scenes(config['seeds']): model=Model() expected=''.join(model.apply(event) for event in events).encode('ascii') stdin=''.join(' '.join(map(str,event))+'\n' for event in events).encode('ascii') prepared.append((name,stdin,expected)) sources={name:(Path(sys.argv[1])/name).read_bytes() for name in config['candidates']} scratch=Path(tempfile.mkdtemp(prefix='resource-map-',dir=Path.cwd())) for name,data in sources.items(): destination=scratch/name destination.parent.mkdir(parents=True,exist_ok=True) destination.write_bytes(data) (scratch/'observer.cpp').write_text(config['observer']) command=['g++','-std=c++17','-O2','-Wall','-Wextra','-pedantic','-Iinclude','-Isrc', 'observer.cpp','src/pool.cpp','src/session.cpp','-o','resource-observer'] # All trusted file IO is complete. Only argv subprocesses and memory below. build_exit='not_run' exits=collections.Counter() stdout_equal=True stderr_empty=True first=None try: built=subprocess.run(command,cwd=scratch,capture_output=True,timeout=35) build_exit=built.returncode if built.returncode: first='build: '+built.stderr[-700:].decode('utf-8','backslashreplace') else: for name,stdin,expected in prepared: try: run=subprocess.run([str(scratch/'resource-observer')],cwd=scratch,input=stdin, capture_output=True,timeout=5) exits[str(run.returncode)]+=1 same=run.stdout==expected quiet=run.stderr==b'' stdout_equal=stdout_equal and same stderr_empty=stderr_empty and quiet if first is None and (run.returncode or not same or not quiet): if run.returncode: first=name+': run_exit='+str(run.returncode)+' stderr='+repr(run.stderr[-120:]) elif not same: first=name+': stdout '+first_difference(run.stdout,expected) else: first=name+': stderr forbidden '+repr(run.stderr[:120]) except subprocess.TimeoutExpired: exits['timeout']+=1 stdout_equal=False if first is None:first=name+': run timeout' except (OSError,subprocess.TimeoutExpired) as error: first='build infrastructure: '+str(error) passed=build_exit==0 and sum(exits.values())==len(prepared) and exits=={'0':len(prepared)} and stdout_equal and stderr_empty print('SUMMARY '+json.dumps(dict(build_exit=build_exit,run_exit_counts=dict(exits),scenes=len(prepared), stdout_equal=stdout_equal,stderr_empty=stderr_empty,first_reason=first),sort_keys=True),file=sys.stderr) print('PASS' if passed else 'FAIL') return 0 if passed else 1 if __name__=='__main__': raise SystemExit(main())