Add host-FD reverse map to eliminate O(n) scans in close and sendfile paths

[jserv]

Problem

forward_close() calls kbox_fd_table_find_by_host_fd() which linearly scans
low_fds[1024] + entries[4096] = 5120 slots every time the tracee closes a
shadow FD by its host number. After the lookup, a second full scan checks
whether any remaining entries reference the same LKL FD before closing it on the
LKL side. The same linear scan is used by forward_sendfile() to resolve
shadow-backed in_fd arguments.

For workloads with many open files (e.g. a build system with hundreds of
concurrent FDs), these O(n) scans add measurable overhead to every close and
sendfile operation.

Proposed Changes

1. Host-FD to virtual-FD hash map: add a secondary index mapping host FD
   numbers to their virtual FD slot. Maintain it in kbox_fd_table_insert(),
   kbox_fd_table_insert_at(), and kbox_fd_table_remove(). Lookup becomes
   O(1) amortized.
2. Per-LKL-FD refcount: track how many virtual FD entries reference each
   LKL FD. Decrement on remove; only close the LKL FD when the refcount
   reaches zero. Eliminates the second full scan entirely.
3. Scope: both data structures are internal to fd-table.c and do not
   affect the public API. The hash map can be a simple open-addressing table
   since host FD numbers are small integers.

Considerations

• The supervisor is single-threaded, so no locking overhead for the new
  structures.
• Host FD numbers are bounded by RLIMIT_NOFILE (65536), so the hash table
  can be sized statically or with a small power-of-two allocation.
• The refcount must handle dup2/dup3 correctly: overwriting an existing entry
  must decrement the old LKL FD's refcount before incrementing the new one.
• Shadow FDs (memfds) use host FD numbers directly in the tracee, making
  the reverse map essential for correct close semantics.

References

• src/fd-table.c: kbox_fd_table_find_by_host_fd(), linear scan
• src/seccomp-dispatch.c: forward_close() double-scan pattern,
  forward_sendfile() host FD resolution
• include/kbox/fd-table.h: public FD table API

[ChuWeiChang]

approach

Add an flat array struct host_to_vfd_entry host_to_vfd_map[RLIMIT_NOFILE] to struct kbox_fd_table
The entry structure will contain:

• long vfd for the $O(1)$ reverse lookup
• int ref_count to track references

With a 16-byte aligned struct, this introduces 1.0 MB static memory. It is possible to reduce this by using a 2-level sparse map, but I opted for a flat array to ensure $O(1)$ performance and avoid malloc().

testing:

1. correctness of mapping and ref_count after creating, removing , updating and closing.

[jserv]

With a 16-byte aligned struct, this introduces 1.0 MB static memory. It is possible to reduce this by using a 2-level sparse map, but I opted for a flat array to ensure O ( 1 ) performance and avoid malloc().

Append test cases for $O(1)$ characteristics as well.

[jserv]

The reverse-map + refcount work landed in 000015c (merged via #51): host_to_vfd[65536] gives O(1) lookup with a MULTI sentinel for dup2/dup3, and lkl_fd_refs[] replaces the second linear scan in forward_close(). End-to-end win on real aarch64: open+close 119.76us -> 47.52us (-60.3%), and kbox_fd_table_find_by_host_fd is off the perf top chart.

Keeping this open because a second-pass review surfaced two unfinished optimizations and one consistency gap, alongside @ChuWeiChang's original testing plan.

Code gaps in 000015c

1. MULTI sentinel is sticky forever. rev_host_set() at src/fd-table.c:112 unconditionally re-assigns KBOX_HOST_VFD_MULTI when cur is neither NONE nor the incoming vfd, so a slot that ever entered MULTI cannot downgrade. The in-code comment at 85-89 claims "a future set overwrites it" -- that path does not exist. Once a transient dup2 poisons host_to_vfd[h], any recycled host_fd on that number permanently falls back to the linear scan. Correctness is preserved; only throughput degrades. Fix: on rev_host_clear, fall back to a bounded scan to detect sole remaining holder and downgrade.

2. forward_dup2 / forward_dup3 / cleanup_replaced_fd_tracking still do O(n) sibling scans. At src/seccomp-dispatch.c:2674, :2835, :2963 the shadow-socket cleanup paths still walk all three ranges after kbox_fd_table_remove(). These are the exact loops the refcount was supposed to replace -- only forward_close() at :2046 got converted. Fix: replace each with kbox_fd_table_lkl_ref_count(ctx->fd_table, shadow_lkl) == 0.

3. Direct negative-sentinel writes bypass rev_host_clear(). At src/seccomp-dispatch.c:1174 and :1617 the lazy-shadow promotion paths assign KBOX_FD_LOCAL_ONLY_SHADOW / KBOX_FD_HOST_SAME_FD_SHADOW directly. If the entry previously held a positive host_fd, the reverse map stays pointed at vfd. The forward-check in find_by_host_fd keeps lookups correct, but when the host kernel recycles that fd number a later set_host_fd sees the stale hit and immediately poisons the slot to MULTI, compounding issue 1. Fix: call rev_host_clear(t, entry->host_fd, vfd) before writing the sentinel.

Validation notes

• lkl_ref_inc saturation at UINT16_MAX is unreachable: max refs per lkl_fd is bounded by KBOX_FD_TABLE_CAPACITY = 36864 < 65535.
• insert_at-over-live-slot is correct: lkl_ref_dec + rev_host_clear happen before init_live_entry (this path fixed a latent leak the pre-patch code had).
• Out-of-range guards on rev_host_* / lkl_ref_* are correct; the linear-scan fallback in kbox_fd_table_lkl_ref_count is reachable for lkl_fd >= KBOX_LKL_FD_REFMAX.

Test suite gaps (extends @ChuWeiChang's plan)

What 000015c added in tests/unit/test-fd-table.c is shallow:

• test_fd_table_find_by_host_fd_duplicate_holder_survives -- MULTI sentinel + scan-order tie-break
• test_fd_table_find_by_host_fd_requires_api -- direct entry->host_fd writes are intentionally not findable

Gaps to close:

1. Refcount lifecycle. Walk the full state machine -- insert, set_host_fd, insert_at over a live slot, remove, close_cloexec_entry -- and assert kbox_fd_table_lkl_ref_count(lkl_fd) at every step. Load-bearing for forward_close()'s shadow-socket path; an off-by-one here silently leaks LKL FDs.

2. MULTI downgrade regression test. Once the sticky-MULTI fix lands, drive a host_fd through single -> MULTI -> single and assert host_to_vfd[h] returns to a non-sentinel vfd. Without this, the fix silently regresses as a perf cliff.

3. O(1) characteristic test. Populate the table to N in {64, 256, 1024, 4096, 16384}, time lookups of a known-present and a known-absent host_fd, and assert the per-lookup cost ratio across N stays under ~2x. Release-only (ASAN skews numbers), behind KBOX_PERF_TESTS=1 so make check-unit stays deterministic.

4. Reverse-map / refcount consistency fuzzer. Drive insert / insert_at / set_host_fd / remove / close_cloexec_entry with a randomized op stream against a shadow oracle and assert (a) find_by_host_fd(h) matches, (b) lkl_fd_refs[k] matches, (c) teardown zeros both arrays.

5. forward_sendfile() coverage. Sendfile rides the same find_by_host_fd() and gets the speedup for free, but no integration test exercises a shadow in_fd through sendfile after the refactor. Add one to tests/guest/.

Consolidation: items 1, 2, 4 belong together in a single test-fd-table-refcount.c (or extension of test-fd-table.c). Item 3 lives behind the perf gate. Item 5 is a one-off under tests/guest/.

Closing once the three code gaps and five test gaps are in.