Cache random purge when dir is overflowing

[scw00]

As @oknet point out, It might always purge the same url when dir is overflowing. It should be random to purge dir's in freelist_clean.

[oknet]

As @scw00 point out, there is a Lagain infinite loop within dir_insert and dir_overwrite if the bucket is full and the freelist is empty.

int
dir_insert(const CacheKey *key, Vol *d, Dir *to_part)
{
...snip...
Lagain:
  // get from this row first
  e = b;
  if (dir_is_empty(e)) {
    goto Lfill;
  }
  for (l = 1; l < DIR_DEPTH; l++) {
    e = dir_bucket_row(b, l);
    if (dir_is_empty(e)) {
      unlink_from_freelist(e, s, d);
      goto Llink;
    }
  }
  // get one from the freelist
  e = freelist_pop(s, d);
  if (!e) {
    goto Lagain;
  }
...snip...
}

When the freelist is empty, freelist_pop calls freelist_clean to release at least one entry and return nullptr.

inline Dir *
freelist_pop(int s, Vol *d)
{
  Dir *seg = d->dir_segment(s);
  Dir *e   = dir_from_offset(d->header->freelist[s], seg);
  if (!e) {
    freelist_clean(s, d);
    return nullptr;
  }
...snip...
}

The freelist_clean traverses all entries in the segment to find head and earliest Dir.
The 1st, 11th, 21th, 31th, etc...(every 10) Dirs will be erased.

For a URL,

• It has a unique CacheKey,
• And the Bucket is selected by CacheKey to store a Dir object.
• Therefore it always stores its Dir to a specific Bucket.

The URL may have a high cache miss rate if the Dir stores in the 1st Entry.

IMO, It is better to randomize the starting position.

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. Marking it stale to flag it for further consideration by the community.