import hashlib import json from pathlib import Path import random import re import subprocess import sys import tempfile CODES = ['OK','RANGE','MISSING','EXISTS','BUSY','ZOMBIE','DENIED','NOT_CHILD','RUNNING','NO_GROUP','CROSS_SESSION'] ARITY = {'seed':1,'fork':2,'sid':1,'pg':3,'exit':2,'reap':2,'proc':1,'group':1,'session':1,'stats':0,'all':0} DOMAINS = {'seed':[(1,32)], 'fork':[(1,32),(1,32)], 'sid':[(1,32)], 'pg':[(1,32)]*3, 'exit':[(1,32),(0,255)], 'reap':[(0,32),(1,32)], 'proc':[(1,32)], 'group':[(1,32)], 'session':[(1,32)]} class Model: def __init__(self): self.records = {} self.births = self.exits = self.reaps = 0 def process(self, pid): if not 1 <= pid <= 32: return [1,0,0,0,0,0,0,0,0] if pid not in self.records: return [2,0,0,0,0,0,0,0,0] p,g,s,l,x = self.records[pid] return [0,pid,p,g,s,l,x,int(pid==g),int(pid==s)] def group(self, gid): if not 1 <= gid <= 32: return [1,0,0,0,0,0] members = [(pid,row) for pid,row in self.records.items() if row[3] and row[1] == gid] if not members: return [2,0,0,0,0,0] sids = {row[2] for _,row in members} assert len(sids)==1, ('cross-session group', gid, self.records) return [0,gid,next(iter(sids)),len(members),int(any(pid==gid for pid,_ in members)),sum(1<<(pid-1) for pid,_ in members)] def session(self, sid): if not 1 <= sid <= 32: return [1,0,0,0,0,0] members = [(pid,row) for pid,row in self.records.items() if row[3] and row[2] == sid] if not members: return [2,0,0,0,0,0] return [0,sid,len({row[1] for _,row in members}),len(members),int(any(pid==sid for pid,_ in members)),sum(1<<(pid-1) for pid,_ in members)] def stats(self): live = [row for row in self.records.values() if row[3]] return [len(self.records),len(live),len(self.records)-len(live),len({r[1] for r in live}),len({r[2] for r in live}),self.births,self.exits,self.reaps] def state(self): return (tuple((pid,tuple(self.records[pid])) for pid in sorted(self.records)),tuple(self.stats())) def invoke(self, verb, args): if verb == 'proc': return 'P', self.process(args[0]) if verb == 'group': return 'G', self.group(args[0]) if verb == 'session': return 'S', self.session(args[0]) if verb == 'stats': return 'T', self.stats() if verb == 'all': return 'A', [self.process(pid) for pid in sorted(self.records)] def fail(name): return 'R',[CODES.index(name),0] if any(not low <= value <= high for value,(low,high) in zip(args,DOMAINS[verb])): return fail('RANGE') if verb == 'seed': pid, = args if self.records: return fail('BUSY') self.records[pid] = [0,pid,pid,1,0] self.births += 1 return 'R',[0,pid] if verb == 'fork': parent,child = args if parent not in self.records: return fail('MISSING') if not self.records[parent][3]: return fail('ZOMBIE') if child in self.records: return fail('EXISTS') if any(row[3] and child in row[1:3] for row in self.records.values()): return fail('BUSY') source = self.records[parent] self.records[child] = [parent,source[1],source[2],1,0] self.births += 1 return 'R',[0,child] if verb == 'sid': pid, = args if pid not in self.records: return fail('MISSING') row = self.records[pid] if not row[3]: return fail('ZOMBIE') if row[1] == pid or any(r[3] and r[1] == pid for r in self.records.values()): return fail('DENIED') row[1] = row[2] = pid return 'R',[0,pid] if verb == 'pg': caller,target,gid = args if caller not in self.records: return fail('MISSING') issuer = self.records[caller] if not issuer[3]: return fail('ZOMBIE') if target not in self.records: return fail('MISSING') row = self.records[target] if not row[3]: return fail('ZOMBIE') if caller != target and row[0] != caller: return fail('NOT_CHILD') if issuer[2] != row[2]: return fail('CROSS_SESSION') if row[2] == target: return fail('DENIED') if gid != target and not any(r[3] and r[1] == gid and r[2] == row[2] for r in self.records.values()): return fail('NO_GROUP') row[1] = gid return 'R',[0,gid] if verb == 'exit': pid,status = args if pid not in self.records: return fail('MISSING') row = self.records[pid] if not row[3]: return fail('ZOMBIE') row[3],row[4] = 0,status for child in self.records.values(): if child[0] == pid: child[0] = 0 self.exits += 1 return 'R',[0,status] parent,child = args if parent: if parent not in self.records: return fail('MISSING') if not self.records[parent][3]: return fail('ZOMBIE') if child not in self.records: return fail('MISSING') row = self.records[child] if row[0] != parent: return fail('NOT_CHILD') if row[3]: return fail('RUNNING') status = row[4] del self.records[child] self.reaps += 1 return 'R',[0,status] def raw(tag, value): if tag == 'A': return 'A '+str(len(value))+'\n'+''.join(raw('P',row) for row in value) return tag+' '+' '.join(map(str,value))+'\n' def formatted(tag, value): if tag == 'A': return 'A '+str(len(value))+'\n'+''.join(formatted('P',row) for row in value) values = list(value) if tag != 'T': values[0] = CODES[values[0]] return tag+' '+' '.join(map(str,values))+'\n' def cli_model(model, text): physical = text.split('\n') if text else [] if physical and physical[-1] == '': physical.pop() output, syntax, errors = [],0,0 events = [] for line in physical[:64]: tokens = [part for part in re.split('[ \t]+',line) if part] if not tokens or tokens[0] not in ARITY or len(tokens) != ARITY.get(tokens[0],-1)+1: syntax += 1 output.append('SYNTAX\n') continue args = [] for token in tokens[1:]: if not re.fullmatch('-?[0-9]+',token) or not -(2**31) <= int(token) <= 2**31-1: break args.append(int(token)) if len(args) != len(tokens)-1: syntax += 1 output.append('SYNTAX\n') continue before = model.state() tag, values = model.invoke(tokens[0],args) code = 0 if tag in ('A','T') else values[0] if code: assert before == model.state() errors += 1 events.append((tokens[0],tuple(args),code)) output.append(formatted(tag,values)) limited = len(physical)>64 if limited: output.append('LIMIT\n') return [min(64,len(physical)),syntax,errors,int(limited)],''.join(output),events class Suite: def __init__(self): self.models = [Model(),Model(),Model()] self.input = [] self.expected = [] self.api_codes = {v:set() for v in ARITY} self.cli_codes = {v:set() for v in ARITY} self.endpoint_guards = [] self.range_guards = [] self.cli_calls = 0 self.failures = 0 def fresh(self, slot=0): self.models[slot] = Model() self.input.append('N '+str(slot)+'\n') def op(self, verb, args=(), slot=0): self.input.append('O '+str(slot)+' '+verb+(' '+' '.join(map(str,args)) if args else '')+'\n') model = self.models[slot] before = model.state() tag, values = model.invoke(verb,list(args)) code = 0 if tag in ('A','T') else values[0] self.api_codes[verb].add(CODES[code]) if code: assert before == model.state() self.failures += 1 self.expected.append(raw(tag,values)) return code def cli(self,text,slot=0): encoded = text.encode('utf-8') self.input.append('C '+str(slot)+' '+(encoded.hex() if encoded else '-')+'\n') summary,output,events = cli_model(self.models[slot],text) data = output.encode('ascii') self.expected.append('C '+' '.join(map(str,summary+[len(data)]))+' '+(data.hex() if data else '-')+'\n') for verb,args,code in events: self.cli_codes[verb].add(CODES[code]) self.failures += bool(code) self.cli_calls += 1 return events def dump(self, slot=0): self.op('stats',slot=slot) self.op('all',slot=slot) for method in ('proc','group','session'): for pid in range(1,33): self.op(method,(pid,),slot) def commands(self, commands, channel, slot=0): if channel == 'API': return [self.op(v,a,slot) for v,a in commands] return [event[2] for event in self.cli(''.join(v+(' '+' '.join(map(str,a)) if a else '')+'\n' for v,a in commands),slot)] def setup_for(verb, parameter, value): other = 16 if value != 16 else 17 if verb=='seed': return [],[value] if verb=='fork': parent,child = (value,other) if parameter==0 else (other,value) return [('seed',[parent])],[parent,child] if verb=='sid': return [('seed',[other]),('fork',[other,value])],[value] if verb=='pg': if parameter==0: return [('seed',[other]),('fork',[other,value])],[value,value,value] if parameter==1: return [('seed',[other]),('fork',[other,value])],[other,value,value] return [('seed',[value]),('fork',[value,other]),('pg',[value,other,other])],[value,other,value] if verb=='exit': if parameter==0: return [('seed',[value])],[value,73] return [('seed',[16]),('fork',[16,17])],[17,value] if verb=='reap': if parameter==0 and value==0: return [('seed',[16]),('exit',[16,73])],[0,16] if parameter==0: return [('seed',[value]),('fork',[value,other]),('exit',[other,73])],[value,other] return [('seed',[other]),('fork',[other,value]),('exit',[value,73])],[other,value] return [('seed',[value])],[value] def build_suite(): s=Suite() for channel in ('API','CLI'): for verb,domains in DOMAINS.items(): for parameter,(low,high) in enumerate(domains): for endpoint in (low,high): s.fresh() setup,args=setup_for(verb,parameter,endpoint) codes=s.commands(setup+[(verb,args)],channel) assert all(code==0 for code in codes), (channel,verb,parameter,endpoint,codes) s.endpoint_guards.append([channel,verb,parameter,endpoint,CODES[codes[-1]]]) s.dump() for rejected in (low-1,high+1,-2147483648,2147483647): s.fresh() # Nonzero existing process state precedes every rejected argument. s.commands([('seed',[16]),('fork',[16,17]),('exit',[17,91])],channel) defaults={'seed':[18],'fork':[16,18],'sid':[16],'pg':[16,17,16],'exit':[16,73],'reap':[16,17],'proc':[16],'group':[16],'session':[16]} args=list(defaults[verb]);args[parameter]=rejected before=s.models[0].state() code=s.commands([(verb,args)],channel)[-1] assert code==1 and before==s.models[0].state() s.range_guards.append([channel,verb,parameter,rejected,'RANGE']) s.dump() error_cases = [ ([('seed',[7])],('seed',[9]),'BUSY'), ([('seed',[7])],('fork',[8,9]),'MISSING'), ([('seed',[7]),('exit',[7,41])],('fork',[7,9]),'ZOMBIE'), ([('seed',[7]),('fork',[7,9])],('fork',[7,9]),'EXISTS'), ([('seed',[7]),('fork',[7,9]),('exit',[7,41]),('reap',[0,7])],('fork',[9,7]),'BUSY'), ([('seed',[7])],('sid',[9]),'MISSING'), ([('seed',[7]),('fork',[7,9]),('exit',[9,41])],('sid',[9]),'ZOMBIE'), ([('seed',[7]),('fork',[7,9])],('sid',[7]),'DENIED'), ([('seed',[7])],('pg',[8,9,9]),'MISSING'), ([('seed',[7]),('exit',[7,41])],('pg',[7,9,9]),'ZOMBIE'), ([('seed',[7])],('pg',[7,9,9]),'MISSING'), ([('seed',[7]),('fork',[7,9]),('exit',[9,41])],('pg',[7,9,9]),'ZOMBIE'), ([('seed',[7]),('fork',[7,9]),('fork',[7,11])],('pg',[9,11,11]),'NOT_CHILD'), ([('seed',[7]),('fork',[7,9]),('sid',[9])],('pg',[7,9,9]),'CROSS_SESSION'), ([('seed',[7]),('fork',[7,9])],('pg',[7,7,7]),'DENIED'), ([('seed',[7]),('fork',[7,9])],('pg',[7,9,11]),'NO_GROUP'), ([('seed',[7])],('exit',[9,41]),'MISSING'), ([('seed',[7]),('exit',[7,41])],('exit',[7,51]),'ZOMBIE'), ([('seed',[7])],('reap',[9,7]),'MISSING'), ([('seed',[7]),('fork',[7,9]),('exit',[7,41])],('reap',[7,9]),'ZOMBIE'), ([('seed',[7])],('reap',[7,9]),'MISSING'), ([('seed',[7]),('fork',[7,9])],('reap',[0,9]),'NOT_CHILD'), ([('seed',[7]),('fork',[7,9])],('reap',[7,9]),'RUNNING'), ] for verb in ('proc','group','session'): error_cases.append(([('seed',[7])],(verb,[9]),'MISSING')) for channel in ('API','CLI'): for setup,target,expected in error_cases: s.fresh();s.commands(setup,channel) before=s.models[0].state() code=s.commands([target],channel)[-1] assert CODES[code]==expected and before==s.models[0].state(), (channel,target,CODES[code],expected) s.dump() # Changes in group/session leaders, orphaned live and zombie children, PID reuse and cumulative counters. lifecycle = [('seed',[7]),('fork',[7,9]),('fork',[9,11]),('fork',[9,13]),('pg',[7,9,9]),('pg',[9,11,9]),('pg',[9,13,9]),('pg',[9,9,7]),('sid',[9]),('exit',[13,255]),('exit',[9,0]),('reap',[0,13]),('reap',[7,9]),('fork',[7,9]),('exit',[11,73]),('reap',[0,11]),('fork',[7,9]),('sid',[9]),('fork',[9,11]),('exit',[9,71]),('reap',[7,9]),('fork',[7,9]),('exit',[11,3]),('reap',[0,11]),('fork',[7,9]),('exit',[7,51]),('exit',[9,19]),('reap',[0,9]),('reap',[0,7]),('seed',[32]),('exit',[32,0]),('reap',[0,32]),('seed',[1])] for channel in ('API','CLI'): s.fresh() for command in lifecycle: s.commands([command],channel);s.dump() # All live objects have the same identifiers with different state. for slot,root in enumerate((7,7,7)): s.fresh(slot);s.commands([('seed',[root]),('fork',[root,9])],'API',slot) s.op('sid',(9,),0);s.op('exit',(9,0),1);s.op('pg',(7,9,9),2) for slot in range(3): s.dump(slot) # Same process and same ledger are reused; every stream has hostile caller formatting. s.fresh() s.cli('seed 0007\nfork 7 0009\nproc 9\nstats\nall\n') s.cli('') s.cli('sid 9') s.cli('group 7\nsession 9\nproc 9\n') malformed=[] for verb,count in ARITY.items(): if count: malformed.append(verb+' '+' '.join(['7']*(count-1))) malformed.append(verb+' '+' '.join(['7']*(count+1))) for parameter in range(count): for bad in ('+7','--7','7x','0x7','1.0','2147483648','-2147483649','7','7\r','-'): args=['7']*count;args[parameter]=bad malformed.append(verb+' '+' '.join(args)) malformed += ['', ' \t ', 'STATS', 'missing', 'stats\r', '\x00', 'seed\v7'] for offset in range(0,len(malformed),37): before=s.models[0].state() s.cli('\n'.join(malformed[offset:offset+37])+'\n') assert before==s.models[0].state() s.dump() s.cli('proc -0\nproc -0000\nproc 0009\t\n\tstats\t\n') s.dump() limit_prefix=['seed 7','fork 7 9']+[('stats' if i%3==0 else 'unknown' if i%3==1 else 'proc 33') for i in range(61)] exact='\n'.join(limit_prefix+['exit 9 255']) for trailing in ('','\n'): s.fresh();s.cli(exact+trailing);s.dump() assert s.models[0].records[9][3:]==[0,255] s.fresh();s.cli(exact+'\nreap 7 9\nexit 7 3'+trailing);s.dump() assert 9 in s.models[0].records and s.models[0].records[7][3]==1 # Counter freshness: limit belongs only to the previous call. s.cli('stats\nproc 9\n');s.dump() rng=random.Random(20817032) for epoch in range(6): s.fresh(epoch%3) slot=epoch%3 s.op('seed',(rng.choice([1,7,16,32]),),slot) for index in range(80): verb=rng.choice(list(ARITY)) args=[rng.choice([-2147483648,-1,0,1,7,9,11,16,17,31,32,33,255,256,2147483647]) for _ in range(ARITY[verb])] if index%2: s.cli(verb+(' '+' '.join(map(str,args)) if args else '')+('\n' if index%3 else ''),slot) else: s.op(verb,args,slot) if index%8==0: s.dump(slot) expected_codes={ 'seed':{'OK','RANGE','BUSY'},'fork':{'OK','RANGE','MISSING','ZOMBIE','EXISTS','BUSY'}, 'sid':{'OK','RANGE','MISSING','ZOMBIE','DENIED'}, 'pg':{'OK','RANGE','MISSING','ZOMBIE','NOT_CHILD','CROSS_SESSION','DENIED','NO_GROUP'}, 'exit':{'OK','RANGE','MISSING','ZOMBIE'},'reap':{'OK','RANGE','MISSING','ZOMBIE','NOT_CHILD','RUNNING'}, 'proc':{'OK','RANGE','MISSING'},'group':{'OK','RANGE','MISSING'},'session':{'OK','RANGE','MISSING'},'stats':{'OK'},'all':{'OK'}} assert s.api_codes==expected_codes, ('API codes',s.api_codes) assert s.cli_codes==expected_codes, ('CLI codes',s.cli_codes) assert len(s.endpoint_guards)==56 and len(s.range_guards)==112 return s, exact+'\nreap 7 9\nexit 7 3\n' HARNESS = r'''#include "identity.hpp" #include #include #include #include #include #include #include using namespace identity; namespace { struct Punctuation : std::numpunct { char do_thousands_sep() const override { return '_'; } std::string do_grouping() const override { return "\3"; } }; void process(const Process& r) { std::cout << "P " << static_cast(r.code) << ' ' << r.pid << ' ' << r.ppid << ' ' << r.pgid << ' ' << r.sid << ' ' << int(r.live) << ' ' << r.status << ' ' << int(r.group_leader) << ' ' << int(r.session_leader) << '\n'; } void group(const Group& r) { std::cout << "G " << static_cast(r.code) << ' ' << r.id << ' ' << r.sid << ' ' << r.members << ' ' << int(r.leader_live) << ' ' << r.mask << '\n'; } void session(const Session& r) { std::cout << "S " << static_cast(r.code) << ' ' << r.id << ' ' << r.groups << ' ' << r.members << ' ' << int(r.leader_live) << ' ' << r.mask << '\n'; } void stats(const Stats& r) { std::cout << "T " << r.tracked << ' ' << r.live << ' ' << r.zombies << ' ' << r.groups << ' ' << r.sessions << ' ' << r.births << ' ' << r.exits << ' ' << r.reaps << '\n'; } int hex_digit(char c) { return c<='9' ? c-'0' : c-'a'+10; } std::string decode(const std::string& hex) { if (hex=="-") return {}; std::string data; for (std::size_t i=0;i,3> ledgers; for (auto& ledger:ledgers) ledger.reset(new Ledger); std::string line; while (std::getline(std::cin,line)) { std::istringstream input(line); char command;int slot;input>>command>>slot; if (command=='N') { ledgers[slot].reset(new Ledger);continue; } Ledger& ledger=*ledgers[slot]; if (command=='C') { std::string bytes;input>>bytes; std::istringstream stream(decode(bytes)); std::ostringstream output; output.imbue(std::locale(std::locale::classic(),new Punctuation)); output << std::hex << std::showbase << std::showpos << std::uppercase << std::boolalpha << std::setfill('~') << std::setw(19); CliResult result=run_cli(ledger,stream,output); std::string actual=output.str(); std::cout<<"C "<>verb; int a=0,b=0,c=0; if (verb=="stats") { stats(ledger.stats());continue; } if (verb=="all") { auto records=ledger.snapshot(); std::cout<<"A "<>a; if (verb=="proc") { process(ledger.inspect(a));continue; } if (verb=="group") { group(ledger.group(a));continue; } if (verb=="session") { session(ledger.session(a));continue; } Result result{}; if (verb=="seed") result=ledger.seed(a); if (verb=="sid") result=ledger.setsid(a); if (verb=="fork") { input>>b;result=ledger.fork_process(a,b); } if (verb=="pg") { input>>b>>c;result=ledger.setpgid(a,b,c); } if (verb=="exit") { input>>b;result=ledger.exit_process(a,b); } if (verb=="reap") { input>>b;result=ledger.reap(a,b); } std::cout<<"R "<(result.code)<<' '<