-
Notifications
You must be signed in to change notification settings - Fork 11
Add host-FD reverse map to eliminate O(n) scans in close and sendfile paths #38
Copy link
Copy link
Open
Description
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
- Host-FD to virtual-FD hash map: add a secondary index mapping host FD
numbers to their virtual FD slot. Maintain it inkbox_fd_table_insert(),
kbox_fd_table_insert_at(), andkbox_fd_table_remove(). Lookup becomes
O(1) amortized. - 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. - Scope: both data structures are internal to
fd-table.cand 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 scansrc/seccomp-dispatch.c:forward_close()double-scan pattern,
forward_sendfile()host FD resolutioninclude/kbox/fd-table.h: public FD table API
Reactions are currently unavailable
Metadata
Metadata
Assignees
Labels
No labels