Skip to content

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

@jserv

Description

@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

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions