Bug: purgeStale sometimes gets stuck in an infinite loop

[javiergonzalezGenially]

We found out that since we updated to v7 sometimes lru-cache would get stuck inside the purgeStale function

(lame) test

const LRU = require("lru-cache");

const sleep = (m) => new Promise((r) => setTimeout(r, m));
jest.setTimeout(50000);

it("works", async () => {
  const expirationTime = 1;
  const accessCache = new LRU({
    max: 66000,
    ttl: expirationTime,
    ttlResolution: 100,
    updateAgeOnGet: true,
  });
  console.log("start");

  for (let i = 0; i < 600; i++) {
    // console.log(i);
    await sleep(10);
    const rnd = Math.random() * 3;
    const v = i % 10;

    if (rnd < 1) {
      accessCache.set(v, v);
    } else if (rnd < 2) {
      accessCache.get(v);
    } else {
      console.log("purge start");
      accessCache.purgeStale();
      console.log("purge end");
    }
  }

  console.log("end");
});

you will see it gets stuck in purge start

The solution seems to be to make the purgeStale function "cache" the items to delete and delete it after the rindexes iteration, or else it may get stuck in an infinite iteration

purgeStale () {
  const toDelete = [];
  for (const i of this.rindexes({ allowStale: true })) {
    if (this.isStale(i)) {
      toDelete.push(this.keyList[i]);
    }
  }

  toDelete.forEach(k => this.delete(k));

  return toDelete.length > 0
}

[sheepa]

I can confirm this bug.

[isaacs]

Ahh, yes, because delete changes the linked list order. Good catch and root cause. Will fix shortly.

[isaacs]

fixed on 7.4.3 by accident, on 7.4.4 on purpose 😬

[isaacs]

backported to other 7.x versions

[palashkulsh]

im not able to get my head around why infinite loop leads to infinite getpid syscalls as shown nodejs/node#42277 . any ideas?

[isaacs]

@palashkulsh Idk, you'd have to ask them. LRUCache doesn't do any getpid() calls.