Guarantee monotonic timestamps in rewritten PCAP output

[sophie-cluml]

Background

The compressed-scenario pipeline's CI check verifies a structural invariant on the generated bundle's PCAP (net/*.pcap): packet timestamps must be monotonically non-decreasing. That is, reading records in capture order (their order within the file), no packet's timestamp may be smaller than the previous packet's.

The current PCAP timestamp rewriter (rewrite_timestamps in the pcap module) behaves as follows:

• It walks the file's records in capture order.
• It converts each record's real timestamp to the logical timeline and overwrites only the timestamp bytes in place.
• There is no step that reorders records or enforces monotonicity of the output.

As a result, the monotonicity of the output depends entirely on the assumption that the captured input is already monotonic.

Problem

Captures are produced by a tcpdump sidecar on a bridge interface. Due to bridge/kernel timestamping, two adjacent packets can be recorded with timestamps that regress by a few hundred µs up to a few ms. When such a small regression is present in the input, the rewriter does not correct it, so the output PCAP can become non-monotonic, in which case the compressed-pipeline check fails.

This failure depends on capture timing, so it is flaky. In particular, any change that slightly shifts activity scheduling/execution timing (e.g. a runtime/async-related dependency update) can surface this latent problem and fail CI. This actually happened on a dependency-bump PR (#85), where this check failed (the CI run). The key line from the failing log:

FAIL: packet 578 timestamp 2026-05-03T04:20:52.034496+00:00 regresses after previous 2026-05-03T04:20:52.038528+00:00

In other words, the root cause is not an incompatibility in any particular dependency, but a design gap: the rewriter does not guarantee monotonicity of its output.

Goal

Deterministically guarantee that the rewritten PCAP's packet timestamps are always monotonically non-decreasing, regardless of ordering jitter in the captured input.

Requirements (functional)

• For complete (non-truncated) input, output a valid microsecond-resolution PCAP. (Truncated input follows the existing tolerance; see the truncated-tail preservation item under "Preserve existing behavior".)
• The only things allowed to change are record ordering and each record's 8-byte timestamp field. incl_len, orig_len, and packet payloads must never be altered.
• All records must be preserved, including non-IPv4 records (ARP, IPv6, LLDP, etc.). No record may be dropped or reinterpreted during reassembly.
• Preserve existing behavior:
  • Reject nanosecond-resolution PCAP and pcapng input with distinct errors.
  • When the final record is truncated, preserve the truncated tail bytes verbatim.
  • Replace the file atomically.
  • Continue returning the maximum rewritten logical timestamp (used upstream to aggregate meta.actual_end).
  • Keep the info message for timestamps outside the logical window.
• Behave identically for little-endian and big-endian captures.
• (Intended behavior change) Previously, an identity mapping guaranteed byte-identical output unconditionally; under the new behavior, a non-monotonic input causes records to be reordered, so that unconditional guarantee no longer holds. This is intentional. Byte-identity now holds exactly when the rewritten timestamps are already non-decreasing — which an identity mapping over an already-monotonic capture still satisfies, so that case remains byte-identical (see the corresponding item under "Testing requirements"). The rewriter function's doc comment (which currently states the output is "byte-identical to the input except for the eight rewritten timestamp bytes") must be updated accordingly.

Ordering / determinism constraints

• The output order must be a stable sort by the rewritten logical timestamp.
  • Records with the same logical timestamp must keep their original capture order (for determinism and minimal reordering).
  • Do not use an unstable sort: it makes no contract to preserve the relative order of equal-key (same logical timestamp) records.
• The sort key must be the microsecond value actually written into the record (ts_sec * 1_000_000 + ts_usec), not the full-precision logical timestamp. The logical timestamp can carry a sub-microsecond remainder that is truncated on write, so keying on it would let two records the output file shows as simultaneous be ordered by a tail that is not present on disk. Keying on the written value keeps "same sort key" and "same bytes in the file" the same predicate, so the tie-preservation rule above is observable in the output.

Implementation guide (follow this approach)

1. Keep the current raw byte walk (do not route through the IPv4 parsing path — this preserves non-IPv4 records).
2. For each record, overwrite only the timestamp field, leaving the rest of the record untouched. The rewrite may be done in place in the single file buffer; there is no need to copy each record slice (16-byte record header + payload) into its own buffer.
3. Collect, for each rewritten record, its sort key paired with a way to locate its bytes — e.g. a (timestamp, record_bytes) pair, or a (timestamp, start, end) byte range into the in-place-rewritten buffer. The range form avoids one copy per record and yields the same output.
4. Stable-sort this buffer by the sort key defined under "Ordering / determinism constraints".
5. Reassemble the output file: original global header + records in sorted order + the preserved truncated tail bytes (if any). Reassembly may be skipped when the collected keys are already non-decreasing, since it would reproduce the buffer byte for byte; this is a pure optimization and must not change the output.
6. Compute the existing side outputs (max logical timestamp, out-of-window info message) during the walk, as before. Both are order-independent, so reordering does not affect them.

Do not (anti-patterns)

• Do not work around this by sorting the capture file before rewriting; the sort key must be the post-rewrite logical timestamp.
• Do not avoid it by changing tcpdump options or the capture method; capture jitter cannot be fully eliminated, and the rewriter must own the invariant at a single deterministic point.
• Do not make it pass by relaxing/removing the CI check; the check enforces a legitimate invariant of the artifact.

Testing requirements

• Add a unit test that constructs an input where a later record (in capture order) has a timestamp earlier than the preceding record, and verifies the rewritten result is monotonically non-decreasing.
• Include records with equal logical timestamps to also lock in that original order is preserved on ties (stable sort).
  • Note that a three-record tie case cannot distinguish a stable sort from an unstable one: sort_unstable_by_key falls back to insertion sort — which happens to be stable — for short slices. Locking in stability requires a tie-heavy input long enough to reach the pattern-defeating quicksort path.
• Confirm existing rewriter behavior still holds: byte-identity for an already-monotonic identity input, truncated-tail tolerance, endianness preservation, max-timestamp return, non-IPv4 record passthrough, and the various input-rejection cases.
  • Non-IPv4 preservation must be asserted on the raw bytes, since the pcap reader drops non-IPv4 records and therefore cannot observe them.
  • Both truncation shapes are worth covering: a partial trailing record header, and a complete 16-byte header whose payload is cut short.

Acceptance criteria

• The compressed-pipeline PCAP monotonicity check passes deterministically, regardless of capture jitter.
• New and existing unit tests pass.
• cargo fmt and cargo clippy (no warnings) pass.

Non-goals

• Changing capture (tcpdump) configuration.
• Changing the time-compression (real→logical) mapping formula.
• Changing the semantics of the CI check.

[sophie-cluml]

Let me work on this issue with agentcoop; I am self-assigning.