> It was discussed before, and there is a closed issue.

That is a non-answer.  The above patch is correct and achieves an essential goal of the lru_cache to save space when possible (avoid an unnecessary extra tuple per entry).   Also, please apply the other patch to eliminate the unnecessary double lookup in lru_cache_extricate_link().   Please also fix the naming problem, "extricate" -> "extract".

> It may be unintentionally. In any case, this is a case that should be very rare.

Please just fix the bug.  That code path incorrectly refreshes an old-key that has not been called recently.  It fails to add the new key that was just called.  It leaves an orphan link causing an unnecessary downstream check for root!=next to guard for the broken invariants.  It leaves the full variable set when the cache is not longer full (missing link).

FWIW, one principal use case for lru_cache() is to support dynamic programming in recursive functions.  So a "call within a call" should not be regarded as "rare".

> Seems the comment was placed at wrong place.

Not just that.  The relevant code was omitted.  It is important to check to see if the new key has already been added by the user_function().  The knowledge of whether that key is present is stale after the user function call.  Please follow the pure python code in this regard.