From 8704dc7896c9ff790f6146c7e3b97d8d87805fb1 Mon Sep 17 00:00:00 2001
From: Stefan Nordhausen <nordhausen@linux-z4v3.site>
Date: Mon, 16 Jan 2012 13:22:14 +0100
Subject: If self.invalidate deletes an entry at just the wrong time, the "del
 data[oldkey]" in put() could raise KeyError. Using pop() prevents this and
 has the side effect that the "if... :" is not needed any more.

---
 repoze/lru/__init__.py | 74 +++++++++++++++++++++++++++++++++-----------------
 1 file changed, 49 insertions(+), 25 deletions(-)

diff --git a/repoze/lru/__init__.py b/repoze/lru/__init__.py
index 11532ce..d3aa5ba 100644
--- a/repoze/lru/__init__.py
+++ b/repoze/lru/__init__.py
@@ -26,11 +26,17 @@ class LRUCache(object):
     def clear(self):
         self.lock.acquire()
         try:
+            # If really clear()ing a full cache, clean up self.data first to
+            # give garbage collection a chance to reduce memorey usage.
+            # Instantiating "[_marker] * size" will temporarily have 2 lists
+            # in memory -> high peak memory usage for tiny amount of time.
+            # With self.data already clear, that peak should not exceed what
+            # we normally use.
+            self.data = {}
             size = self.size
             self.clock_keys = [_marker] * size
             self.clock_refs = [False] * size
             self.hand = 0
-            self.data = {}
         finally:
             self.lock.release()
 
@@ -43,40 +49,48 @@ class LRUCache(object):
         return val
 
     def put(self, key, val, _marker=_marker):
-        hand = self.hand
+        # These do not change or they are just references, no need for locking.
         maxpos = self.maxpos
         clock_refs = self.clock_refs
         clock_keys = self.clock_keys
         data = self.data
         lock = self.lock
 
-        entry = self.data.get(key)
-        if entry is not None:
-            lock.acquire()
-            try:
-                # We already have key. Only make sure data is up to date and to
-                # remember that it was used.
+        lock.acquire()
+        try:
+            entry = data.get(key)
+            if entry is not None:
+                # We already have key. Only make sure data is up to date and
+                # to remember that it was used.
                 pos, old_val = entry
                 if old_val is not val:
                     data[key] = (pos, val)
                 self.clock_refs[pos] = True
                 return
-            finally:
-                lock.release()
+            # else: key is not yet in cache. Search place to insert it.
 
-        while 1:
-            ref = clock_refs[hand]
-            if ref == True:
-                clock_refs[hand] = False
-                hand = hand + 1
-                if hand > maxpos:
-                    hand = 0
-            else:
-                lock.acquire()
-                try:
+            hand = self.hand
+            count = 0
+            max_count = 107
+            while 1:
+                ref = clock_refs[hand]
+                if ref == True:
+                    clock_refs[hand] = False
+                    hand += 1
+                    if hand > maxpos:
+                        hand = 0
+
+                    count += 1
+                    if count >= max_count:
+                        # We have been searching long enough. Force eviction of
+                        # next entry, no matter what its status is.
+                        clock_refs[hand] = False
+                else:
                     oldkey = clock_keys[hand]
-                    if oldkey in data:
-                        del data[oldkey]
+                    # Maybe oldkey was not in self.data to begin with. If it
+                    # was, self.invalidate() in another thread might have
+                    # already removed it. del() would raise KeyError, so pop().
+                    data.pop(oldkey, None)
                     clock_keys[hand] = key
                     clock_refs[hand] = True
                     data[key] = (hand, val)
@@ -84,9 +98,19 @@ class LRUCache(object):
                     if hand > maxpos:
                         hand = 0
                     self.hand = hand
-                finally:
-                    lock.release()
-                break
+                    break
+        finally:
+            lock.release()
+
+    def invalidate(self, key):
+        """Remove key from the cache"""
+        # pop with default arg will not raise KeyError
+        entry = self.data.pop(key, _marker)
+        if entry is not _marker:
+            # We have no lock, but worst thing that can happen is that we
+            # set another key's entry to False.
+            self.clock_refs[entry[0]] = False
+        # else: key was not in cache. Nothing to do.
 
 class lru_cache(object):
     """ Decorator for LRU-cached function """
-- 
cgit v1.2.1