Skip to content

overlay_lookup() degrades to O(bucket_count) once the table fills #19

Description

@congwang-mk

overlay_lookup() (daxfs/overlay.c:92) only stops early when it finds a FREE bucket:

for (i = 0; i < ovl->bucket_count; i++) {
        u32 probe = (idx + i) & ovl->bucket_mask;
        ...
        if (DAXFS_OVL_STATE(sk) == DAXFS_OVL_FREE)
                return NULL;    /* Empty slot - key doesn't exist */
        ...
}
return NULL;    /* Table full, not found */

Once the table has no free buckets left, every lookup that misses scans all bucket_count entries before giving up. overlay_insert() has the same shape.

This is self-inflicted rather than a rare edge case: filling the table is exactly what writing a large file does, since each overlay page consumes one bucket. Past that point every new page costs a full-table scan, so the write path goes quadratic in the number of pages. daxfs_statfs() already reports capacity as min(pool_pages, bucket_count), so the table filling is an expected operating point, not a corrupt state.

Not straightforward to fix. Bounding the probe window the way the pcache does (PCACHE_PROBE_LEN) would cap the scan, but the probe policy is part of the on-image contract: two hosts using different probe limits would disagree about where a key lives, so it cannot be changed unilaterally without a format version bump.

Possible directions:

  • bound the probe window and version the format
  • keep a free-bucket count in the overlay header and fail fast when it hits zero
  • report -ENOSPC earlier, at a load factor below 100%, so the degenerate region is never entered

Found during the review in #15. Not a correctness bug; performance only.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions