Route D (real fixes in embedded open-source projects) keeps producing the hard tasks: of 64 measured so far, 15 are HARD and 4 MEDIUM, mostly because Qwen exhausts its context in the larger real workspaces. This adds CANopen SRDO and ASCII timing, FreeRTOS DHCP, lwIP MQTT fragments, printf extremal exponents, Zephyr packet buffers and heatshrink (HARD), plus lwjson, RFM9x, SFUD and nanopb proto3 (MEDIUM). From batch 27 (spec-dense implementation tasks) come one HARD and one MEDIUM; that batch is winding down after 30 tasks gave 1 HARD and 3 MEDIUM. Each task comes from the commit Qwen measured, its digest matches, and it is still present at the batch branch head. Agent timeouts stay excluded: a pyserial attempt timed out on Qwen's own blocking read yet graded PASS. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
240 lines
10 KiB
Python
240 lines
10 KiB
Python
"""Independent FIFO packet oracle; candidate code only executes in subprocesses."""
|
|
from collections import deque
|
|
from pathlib import Path
|
|
import random
|
|
import subprocess
|
|
import sys
|
|
import tempfile
|
|
|
|
ROOT = Path(__file__).resolve().parent
|
|
PUBLIC_FILES = (
|
|
'lib/os/mpsc_pbuf.c', 'include/zephyr/sys/mpsc_pbuf.h',
|
|
'include/zephyr/sys/mpsc_packet.h', 'include/zephyr/kernel.h', 'host_port.c',
|
|
)
|
|
|
|
|
|
def packet(n, ident):
|
|
return [n, ident] + [(ident * 1009 + i * 37) & 0xffffffff for i in range(1, n)]
|
|
|
|
|
|
class PacketQueue:
|
|
"""Application packets and consumer leases, without ring indices or flags.
|
|
|
|
Actual drop observations remove complete oldest eligible packets;
|
|
the oracle checks every byte and then verifies admission against capacity.
|
|
Scheduled consumer observations are processed when present, so a solution
|
|
which reclaims empty padding without waiting is also accepted.
|
|
"""
|
|
def __init__(self, capacity, overwrite):
|
|
self.capacity = capacity
|
|
self.overwrite = overwrite
|
|
self.ready = deque()
|
|
self.reserved = {}
|
|
self.held = None
|
|
self.scheduled = 0
|
|
|
|
def used(self):
|
|
items = list(self.ready) + list(self.reserved.values())
|
|
if self.held is not None:
|
|
items.append(self.held)
|
|
return sum(p[0] for p in items)
|
|
|
|
def claim(self):
|
|
return self.ready.popleft() if self.ready else None
|
|
|
|
@staticmethod
|
|
def view(event, value):
|
|
return event + ' ' + ('0' if value is None else '1 ' + ' '.join(map(str, value)))
|
|
|
|
def verify(self, operation, lines):
|
|
fields = operation['command'].split()
|
|
kind = fields[0]
|
|
# A semaphore callback is a separately scheduled public consumer action.
|
|
# Its occurrence is not required for an empty logical queue.
|
|
ordinary = []
|
|
scheduled_packet = None
|
|
for line in lines:
|
|
if line.startswith('scheduled '):
|
|
if not self.scheduled:
|
|
raise ValueError('unscheduled consumer action')
|
|
scheduled_packet = self.claim()
|
|
if line != self.view('scheduled', scheduled_packet):
|
|
raise ValueError('scheduled consumer data/order')
|
|
if self.scheduled == 1 and scheduled_packet is not None:
|
|
raise ValueError('claim-only schedule requires empty queue')
|
|
self.scheduled = 0
|
|
elif line.startswith('scheduled_free '):
|
|
if scheduled_packet is None or line != 'scheduled_free 1':
|
|
raise ValueError('scheduled release without packet')
|
|
scheduled_packet = None
|
|
elif line.startswith('drop '):
|
|
if not self.overwrite or kind not in ('P', 'A') or not self.ready:
|
|
raise ValueError('unexpected drop')
|
|
if line != self.view('drop', self.ready.popleft()):
|
|
raise ValueError('drop data/order')
|
|
else:
|
|
ordinary.append(line)
|
|
if scheduled_packet is not None:
|
|
raise ValueError('scheduled consumer did not release packet')
|
|
wanted = []
|
|
if kind in ('P', 'A'):
|
|
if kind == 'P':
|
|
n, ident, wait = map(int, fields[1:])
|
|
slot = None
|
|
else:
|
|
slot, n, ident = map(int, fields[1:])
|
|
success = n <= self.capacity and self.used() + n <= self.capacity
|
|
wanted = ['alloc %d %d' % (ident, success)]
|
|
if success:
|
|
value = packet(n, ident)
|
|
if slot is None:
|
|
self.ready.append(value)
|
|
else:
|
|
self.reserved[slot] = value
|
|
elif kind == 'C':
|
|
value = self.reserved.pop(int(fields[1]), None)
|
|
wanted = ['commit %d' % (value is not None)]
|
|
if value is not None:
|
|
self.ready.append(value)
|
|
elif kind == 'T':
|
|
self.held = self.claim()
|
|
wanted = [self.view('claim', self.held)]
|
|
elif kind == 'V':
|
|
wanted = [self.view('held', self.held)]
|
|
elif kind == 'F':
|
|
wanted = ['free %d' % (self.held is not None)]
|
|
self.held = None
|
|
elif kind == 'E':
|
|
wanted = [self.view('consume', self.claim())]
|
|
elif kind == 'S':
|
|
self.scheduled = int(fields[1])
|
|
elif kind == 'Q':
|
|
wanted = ['pending %d' % bool(self.ready)]
|
|
if ordinary != wanted:
|
|
raise ValueError('packet API observation mismatch')
|
|
|
|
|
|
def cases():
|
|
rng = random.Random(0xC06A71)
|
|
next_id = rng.randrange(30, 400)
|
|
def p(n, wait=0):
|
|
nonlocal next_id
|
|
next_id += rng.randrange(1, 10)
|
|
return dict(command='P %d %d %d' % (n, next_id, wait))
|
|
def a(slot, n):
|
|
nonlocal next_id
|
|
next_id += rng.randrange(1, 10)
|
|
return dict(command='A %d %d %d' % (slot, n, next_id))
|
|
def op(s):
|
|
return dict(command=s)
|
|
result = []
|
|
for n in (12, 15, 16, 23, 32, 63, 64):
|
|
# The held packet leaves fewer words than the requested new packet.
|
|
h = n - 3
|
|
result.append((n, 1, [p(h), op('T'), op('V'), p(5), op('V'),
|
|
op('F'), op('E'), p(5), op('E'), op('E'), op('Q')]))
|
|
# After one packet is consumed, the empty tail cannot hold the next one.
|
|
# A producer may reclaim that tail itself or dispatch the scheduled claim.
|
|
h = n // 2 + 1
|
|
result.append((n, 0, [p(h), op('E'), op('S 1'), p(h+1, 7),
|
|
op('E'), op('E'), op('Q')]))
|
|
# Full storage, no overwrite: scheduled claim/free releases one packet.
|
|
left = n // 2
|
|
right = n - left
|
|
result.append((n, 0, [p(left), p(right), op('Q'), op('S 2'),
|
|
p(left, 9), op('E'), op('E'), op('E'), op('Q')]))
|
|
result.append((n, 0, [p(n), p(1), p(n+1), op('E'), op('E'),
|
|
p(1), op('E'), op('E'), op('Q')]))
|
|
# Ordinary wrap, with room in the head to hold the complete next packet.
|
|
result.append((n, 0, [p(n-2), op('E'), p(n//2), op('E'),
|
|
p(1), op('E'), op('E'), op('Q')]))
|
|
# Reservations are unpublished until committed, then preserve FIFO order.
|
|
result.append((n, 0, [a(0, 2), op('E'), a(1, 3), op('C 0'), op('C 1'),
|
|
op('Q'), op('E'), op('E'), op('E'), op('Q')]))
|
|
# A consumer lease and queued packets compete for a large new packet.
|
|
# Any observed drops must be complete oldest packets, never the lease.
|
|
result.append((24, 1, [p(6), op('T'), p(6), p(6), p(12),
|
|
op('V'), op('F'), op('E'), op('E'), op('Q')]))
|
|
# An entirely full queue, with no lease, requires reclamation to admit more.
|
|
result.append((16, 1, [p(4), p(4), p(4), p(4), p(4),
|
|
op('E'), op('E'), op('E'), op('E'), op('E'), op('Q')]))
|
|
# Different legal starting positions can reclaim one or two old packets.
|
|
# The oracle follows FIFO drop observations, rather than a fixed count.
|
|
result.append((16, 1, [p(3), p(5), p(4), p(6), op('E'), op('E'),
|
|
op('E'), op('E'), op('E'), op('Q')]))
|
|
for n in (31, 64):
|
|
stream = []
|
|
for _ in range(96):
|
|
stream.extend([p(rng.randrange(1, n + 1)), op('E')])
|
|
stream.extend([op('E'), op('Q')])
|
|
result.append((n, 0, stream))
|
|
return result
|
|
|
|
|
|
def verify_output(size, overwrite, operations, output):
|
|
groups = []
|
|
current = None
|
|
for line in output.splitlines():
|
|
if line == 'begin %d' % len(groups) and current is None:
|
|
current = []
|
|
elif line == 'end' and current is not None:
|
|
groups.append(current)
|
|
current = None
|
|
elif current is not None:
|
|
current.append(line)
|
|
else:
|
|
raise ValueError('malformed observer stream')
|
|
if current is not None or len(groups) != len(operations):
|
|
raise ValueError('incomplete observer stream')
|
|
model = PacketQueue(size, overwrite)
|
|
for operation, lines in zip(operations, groups):
|
|
model.verify(operation, lines)
|
|
|
|
|
|
def main():
|
|
candidate = Path(sys.argv[1])
|
|
# Read all trusted material and the declared candidate before child execution.
|
|
material = {name: ((candidate if name == 'lib/os/mpsc_pbuf.c' else ROOT / 'support') / name).read_bytes()
|
|
for name in PUBLIC_FILES}
|
|
material['observer.c'] = (ROOT / 'harness.c').read_bytes()
|
|
work = Path(tempfile.mkdtemp(prefix='packet-buffer-grade-'))
|
|
for name, data in material.items():
|
|
path = work / name
|
|
path.parent.mkdir(parents=True, exist_ok=True)
|
|
path.write_bytes(data)
|
|
executable = str(work / 'observer')
|
|
plans = []
|
|
for size, overwrite, operations in cases():
|
|
data = '%d %d\n' % (size, overwrite)
|
|
data += '\n'.join(op['command'] for op in operations) + '\n'
|
|
plans.append((size, overwrite, operations,
|
|
['timeout', '--signal=KILL', '3s', executable], data))
|
|
build_argv = ['timeout', '--signal=KILL', '20s', 'gcc',
|
|
'-std=c11', '-O0', '-Wall', '-Wextra',
|
|
'-I' + str(work / 'include'), str(work / 'lib/os/mpsc_pbuf.c'),
|
|
str(work / 'host_port.c'), str(work / 'observer.c'), '-o', executable]
|
|
# All source, cases, inputs and argv exist before the first compiler.
|
|
# Subsequently the parent never accesses scratch files; its unique container
|
|
# reclaims mkdtemp storage without root following candidate-created paths.
|
|
build = subprocess.run(build_argv, capture_output=True, text=True, timeout=25)
|
|
if build.returncode:
|
|
raise ValueError('candidate build failed')
|
|
for case_index, (size, overwrite, operations, argv, data) in enumerate(plans):
|
|
child = subprocess.run(argv, input=data, capture_output=True,
|
|
text=True, timeout=6)
|
|
if child.returncode:
|
|
raise ValueError('candidate process failed')
|
|
try:
|
|
verify_output(size, overwrite, operations, child.stdout)
|
|
except ValueError as error:
|
|
raise ValueError("case %d: %s" % (case_index, error)) from error
|
|
print('PASS')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
try:
|
|
main()
|
|
except (ValueError, OSError, subprocess.SubprocessError) as error:
|
|
print('FAIL: ' + str(error))
|
|
sys.exit(1)
|