Repository: getsentry/sentry-python

Issue:
LRUCache.__copy__ is unsound
### How do you use Sentry?

Sentry Saas (sentry.io)

### Version

latest git revision

### Steps to Reproduce

unfortunately I haven't completely narrowed down a "minimal" reproduction but I originally found this from reading the implementation and tracing the output -- attached is a script and data which produces a crash due to a particular ordering of copys and sets.

the root cause of the problem is that `__copy__` is incorrect as written -- it shallow copies the internal datastructures which incorrectly pollutes newly created caches

in the ~best case this produces incorrect values poisoning the parent copy:

```pycon
>>> cache1 = LRUCache(max_size=2)
>>> cache1.set(1, True)
>>> cache2 = cache1.__copy__()
>>> cache2.set(1, False)
>>> cache1.get(1)
False
```

at worst case it causes crashes (see attached data)

```python3
from sentry_sdk._lru_cache import LRUCache


def main() -> int:
    caches = {}

    with open('lru_cache.log') as f:
        for line in f:
            line = line.replace(': ', ' ')

            match line.split():
                case [cid, '__init__']:
                    caches[cid] = LRUCache(max_size=100)
                case [cid, 'set', k, *v]:
                    caches[cid].set(k, ' '.join(v))
                case [cid, '__copy__', '->', cid2]:
                    caches[cid2] = caches[cid].__copy__()
                case unreachable:
                    raise AssertionError(unreachable)


if __name__ == '__main__':
    raise SystemExit(main())
```

[lru_cache.log](https://github.com/user-attachments/files/18014834/lru_cache.log)

cc @cmanallen -- introduced in dd1117d63fd690d502b32c263e9e970b682fa280


### Expected Result

should not crash, should not have internal data integrity problems

### Actual Result

the script eventually crashes with:

```console
$ ./venvnew/bin/python3 t3.py 
Traceback (most recent call last):
  File "/Users/asottile/workspace/sentry/t3.py", line 23, in <module>
    raise SystemExit(main())
                     ^^^^^^
  File "/Users/asottile/workspace/sentry/t3.py", line 15, in main
    caches[cid].set(k, ' '.join(v))
  File "/Users/asottile/workspace/sentry/venvnew/lib/python3.12/site-packages/sentry_sdk/_lru_cache.py", line 132, in set
    del self.cache[old_key]
        ~~~~~~~~~~^^^^^^^^^
KeyError: 'organizations:continuous-profiling-beta'
```

Discussion:
codecov[bot]: ## [Codecov](https://app.codecov.io/gh/getsentry/sentry-python/pull/3883?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getsentry) Report
Attention: Patch coverage is `93.10345%` with `2 lines` in your changes missing coverage. Please review.
> Project coverage is 79.84%. Comparing base [(`8ced660`)](https://app.codecov.io/gh/getsentry/sentry-python/commit/8ced6609e6fcc95855f43cf9fc1d94b59836b57f?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getsentry) to head [(`f98f6a9`)](https://app.codecov.io/gh/getsentry/sentry-python/commit/f98f6a977c1d36d10ffa4e7acbe8a0c7ffc72e7e?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getsentry).

:white_check_mark: All tests successful. No failed tests found.

| [Files with missing lines](https://app.codecov.io/gh/getsentry/sentry-python/pull/3883?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getsentry) | Patch % | Lines |
|---|---|---|
| [sentry\_sdk/\_lru\_cache.py](https://app.codecov.io/gh/getsentry/sentry-python/pull/3883?src=pr&el=tree&filepath=sentry_sdk%2F_lru_cache.py&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getsentry#diff-c2VudHJ5X3Nkay9fbHJ1X2NhY2hlLnB5) | 93.10% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/getsentry/sentry-python/pull/3883?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getsentry) |

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##           master    #3883      +/-   ##
==========================================
- Coverage   79.91%   79.84%   -0.08%     
==========================================
  Files         139      139              
  Lines       15458    15429      -29     
  Branches     2625     2624       -1     
==========================================
- Hits        12353    12319      -34     
- Misses       2232     2241       +9     
+ Partials      873      869       -4     
```

| [Files with missing lines](https://app.codecov.io/gh/getsentry/sentry-python/pull/3883?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getsentry) | Coverage Δ | |
|---|---|---|
| [sentry\_sdk/\_lru\_cache.py](https://app.codecov.io/gh/getsentry/sentry-python/pull/3883?src=pr&el=tree&filepath=sentry_sdk%2F_lru_cache.py&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getsentry#diff-c2VudHJ5X3Nkay9fbHJ1X2NhY2hlLnB5) | `94.87% <93.10%> (-5.13%)` | :arrow_down: |

... and [5 files with indirect coverage changes](https://app.codecov.io/gh/getsentry/sentry-python/pull/3883/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=getsentry)

</details>

Patch:
diff --git a/sentry_sdk/_lru_cache.py b/sentry_sdk/_lru_cache.py
index 825c7735..09eae27d 100644
--- a/sentry_sdk/_lru_cache.py
+++ b/sentry_sdk/_lru_cache.py
@@ -1,181 +1,56 @@
-"""
-A fork of Python 3.6's stdlib lru_cache (found in Python's 'cpython/Lib/functools.py')
-adapted into a data structure for single threaded uses.
+from typing import TYPE_CHECKING
 
-https://github.com/python/cpython/blob/v3.6.12/Lib/functools.py
+if TYPE_CHECKING:
+    from typing import Any
 
 
-Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
-2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Python Software Foundation;
-
-All Rights Reserved
-
-
-PYTHON SOFTWARE FOUNDATION LICENSE VERSION 2
---------------------------------------------
-
-1. This LICENSE AGREEMENT is between the Python Software Foundation
-("PSF"), and the Individual or Organization ("Licensee") accessing and
-otherwise using this software ("Python") in source or binary form and
-its associated documentation.
-
-2. Subject to the terms and conditions of this License Agreement, PSF hereby
-grants Licensee a nonexclusive, royalty-free, world-wide license to reproduce,
-analyze, test, perform and/or display publicly, prepare derivative works,
-distribute, and otherwise use Python alone or in any derivative version,
-provided, however, that PSF's License Agreement and PSF's notice of copyright,
-i.e., "Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
-2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Python Software Foundation;
-All Rights Reserved" are retained in Python alone or in any derivative version
-prepared by Licensee.
-
-3. In the event Licensee prepares a derivative work that is based on
-or incorporates Python or any part thereof, and wants to make
-the derivative work available to others as provided herein, then
-Licensee hereby agrees to include in any such work a brief summary of
-the changes made to Python.
-
-4. PSF is making Python available to Licensee on an "AS IS"
-basis.  PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR
-IMPLIED.  BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND
-DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS
-FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON WILL NOT
-INFRINGE ANY THIRD PARTY RIGHTS.
-
-5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON
-FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS
-A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON,
-OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF.
-
-6. This License Agreement will automatically terminate upon a material
-breach of its terms and conditions.
-
-7. Nothing in this License Agreement shall be deemed to create any
-relationship of agency, partnership, or joint venture between PSF and
-Licensee.  This License Agreement does not grant permission to use PSF
-trademarks or trade name in a trademark sense to endorse or promote
-products or services of Licensee, or any third party.
-
-8. By copying, installing or otherwise using Python, Licensee
-agrees to be bound by the terms and conditions of this License
-Agreement.
-
-"""
-
-from copy import copy, deepcopy
-
-SENTINEL = object()
-
-
-# aliases to the entries in a node
-PREV = 0
-NEXT = 1
-KEY = 2
-VALUE = 3
+_SENTINEL = object()
 
 
 class LRUCache:
     def __init__(self, max_size):
-        assert max_size > 0
-
+        # type: (int) -> None
+        if max_size <= 0:
+            raise AssertionError(f"invalid max_size: {max_size}")
         self.max_size = max_size
-        self.full = False
-
-        self.cache = {}
-
-        # root of the circularly linked list to keep track of
-        # the least recently used key
-        self.root = []  # type: ignore
-        # the node looks like [PREV, NEXT, KEY, VALUE]
-        self.root[:] = [self.root, self.root, None, None]
-
+        self._data = {}  # type: dict[Any, Any]
         self.hits = self.misses = 0
+        self.full = False
 
     def __copy__(self):
-        cache = LRUCache(self.max_size)
-        cache.full = self.full
-        cache.cache = copy(self.cache)
-        cache.root = deepcopy(self.root)
-        return cache
+        # type: () -> LRUCache
+        new = LRUCache(max_size=self.max_size)
+        new.hits = self.hits
+        new.misses = self.misses
+        new.full = self.full
+        new._data = self._data.copy()
+        return new
 
     def set(self, key, value):
-        link = self.cache.get(key, SENTINEL)
-
-        if link is not SENTINEL:
-            # have to move the node to the front of the linked list
-            link_prev, link_next, _key, _value = link
-
-            # first remove the node from the lsnked list
-            link_prev[NEXT] = link_next
-            link_next[PREV] = link_prev
-
-            # insert the node between the root and the last
-            last = self.root[PREV]
-            last[NEXT] = self.root[PREV] = link
-            link[PREV] = last
-            link[NEXT] = self.root
-
-            # update the value
-            link[VALUE] = value
-
+        # type: (Any, Any) -> None
+        current = self._data.pop(key, _SENTINEL)
+        if current is not _SENTINEL:
+            self._data[key] = value
         elif self.full:
-            # reuse the root node, so update its key/value
-            old_root = self.root
-            old_root[KEY] = key
-            old_root[VALUE] = value
-
-            self.root = old_root[NEXT]
-            old_key = self.root[KEY]
-
-            self.root[KEY] = self.root[VALUE] = None
-
-            del self.cache[old_key]
-
-            self.cache[key] = old_root
-
+            self._data.pop(next(iter(self._data)))
+            self._data[key] = value
         else:
-            # insert new node after last
-            last = self.root[PREV]
-            link = [last, self.root, key, value]
-            last[NEXT] = self.root[PREV] = self.cache[key] = link
-            self.full = len(self.cache) >= self.max_size
+            self._data[key] = value
+        self.full = len(self._data) >= self.max_size
 
     def get(self, key, default=None):
-        link = self.cache.get(key, SENTINEL)
-
-        if link is SENTINEL:
+        # type: (Any, Any) -> Any
+        try:
+            ret = self._data.pop(key)
+        except KeyError:
             self.misses += 1
-            return default
-
-        # have to move the node to the front of the linked list
-        link_prev, link_next, _key, _value = link
-
-        # first remove the node from the lsnked list
-        link_prev[NEXT] = link_next
-        link_next[PREV] = link_prev
-
-        # insert the node between the root and the last
-        last = self.root[PREV]
-        last[NEXT] = self.root[PREV] = link
-        link[PREV] = last
-        link[NEXT] = self.root
-
-        self.hits += 1
+            ret = default
+        else:
+            self.hits += 1
+            self._data[key] = ret
 
-        return link[VALUE]
+        return ret
 
     def get_all(self):
-        nodes = []
-        node = self.root[NEXT]
-
-        # To ensure the loop always terminates we iterate to the maximum
-        # size of the LRU cache.
-        for _ in range(self.max_size):
-            # The cache may not be full. We exit early if we've wrapped
-            # around to the head.
-            if node is self.root:
-                break
-            nodes.append((node[KEY], node[VALUE]))
-            node = node[NEXT]
-
-        return nodes
+        # type: () -> list[tuple[Any, Any]]
+        return list(self._data.items())


Test patch:
diff --git a/tests/test_lru_cache.py b/tests/test_lru_cache.py
index cab9bbc7..1a54ed83 100644
--- a/tests/test_lru_cache.py
+++ b/tests/test_lru_cache.py
@@ -1,5 +1,5 @@
 import pytest
-from copy import copy
+from copy import copy, deepcopy
 
 from sentry_sdk._lru_cache import LRUCache
 
@@ -76,3 +76,38 @@ def test_cache_copy():
     cache.get(1)
     assert copied.get_all() == [(1, 1), (2, 2), (3, 3)]
     assert cache.get_all() == [(2, 2), (3, 3), (1, 1)]
+
+
+def test_cache_deepcopy():
+    cache = LRUCache(3)
+    cache.set(0, 0)
+    cache.set(1, 1)
+
+    copied = deepcopy(cache)
+    cache.set(2, 2)
+    cache.set(3, 3)
+    assert copied.get_all() == [(0, 0), (1, 1)]
+    assert cache.get_all() == [(1, 1), (2, 2), (3, 3)]
+
+    copied = deepcopy(cache)
+    cache.get(1)
+    assert copied.get_all() == [(1, 1), (2, 2), (3, 3)]
+    assert cache.get_all() == [(2, 2), (3, 3), (1, 1)]
+
+
+def test_cache_pollution():
+    cache1 = LRUCache(max_size=2)
+    cache1.set(1, True)
+    cache2 = copy(cache1)
+    cache2.set(1, False)
+    assert cache1.get(1) is True
+    assert cache2.get(1) is False
+
+
+def test_cache_pollution_deepcopy():
+    cache1 = LRUCache(max_size=2)
+    cache1.set(1, True)
+    cache2 = deepcopy(cache1)
+    cache2.set(1, False)
+    assert cache1.get(1) is True
+    assert cache2.get(1) is False
diff --git a/tests/test_scope.py b/tests/test_scope.py
index a03eb07a..9b16dc43 100644
--- a/tests/test_scope.py
+++ b/tests/test_scope.py
@@ -43,6 +43,28 @@ def test_all_slots_copied():
         assert getattr(scope_copy, attr) == getattr(scope, attr)
 
 
+def test_scope_flags_copy():
+    # Assert forking creates a deepcopy of the flag buffer. The new
+    # scope is free to mutate without consequence to the old scope. The
+    # old scope is free to mutate without consequence to the new scope.
+    old_scope = Scope()
+    old_scope.flags.set("a", True)
+
+    new_scope = old_scope.fork()
+    new_scope.flags.set("a", False)
+    old_scope.flags.set("b", True)
+    new_scope.flags.set("c", True)
+
+    assert old_scope.flags.get() == [
+        {"flag": "a", "result": True},
+        {"flag": "b", "result": True},
+    ]
+    assert new_scope.flags.get() == [
+        {"flag": "a", "result": False},
+        {"flag": "c", "result": True},
+    ]
+
+
 def test_merging(sentry_init, capture_events):
     sentry_init()