Skip to content

Commit d896dfc

Browse files
colesburycolesbury
committed
dict: make dict thread-safe
1 parent f7b87a0 commit d896dfc

20 files changed

Lines changed: 1623 additions & 764 deletions

‎Doc/data/stable_abi.dat‎

Lines changed: 3 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎Include/cpython/dictobject.h‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,10 @@ typedef struct {
2626
If ma_values is not NULL, the table is split:
2727
keys are stored in ma_keys and values are stored in ma_values */
2828
PyDictValues *ma_values;
29+
30+
PyMutex ma_mutex;
31+
32+
uint8_t ma_maybe_shared;
2933
} PyDictObject;
3034

3135
PyAPI_FUNC(PyObject *) _PyDict_GetItem_KnownHash(PyObject *mp, PyObject *key,
@@ -36,12 +40,15 @@ PyAPI_FUNC(PyObject *) _PyDict_GetItemIdWithError(PyObject *dp,
3640
PyAPI_FUNC(PyObject *) _PyDict_GetItemStringWithError(PyObject *, const char *);
3741
PyAPI_FUNC(PyObject *) PyDict_SetDefault(
3842
PyObject *mp, PyObject *key, PyObject *defaultobj);
43+
PyAPI_FUNC(PyObject *) _PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj,
44+
int incref, int *is_insert);
3945
PyAPI_FUNC(int) _PyDict_SetItem_KnownHash(PyObject *mp, PyObject *key,
4046
PyObject *item, Py_hash_t hash);
4147
PyAPI_FUNC(int) _PyDict_DelItem_KnownHash(PyObject *mp, PyObject *key,
4248
Py_hash_t hash);
4349
PyAPI_FUNC(int) _PyDict_DelItemIf(PyObject *mp, PyObject *key,
44-
int (*predicate)(PyObject *value));
50+
int (*predicate)(PyObject *value, void *data),
51+
void *data);
4552
PyAPI_FUNC(int) _PyDict_Next(
4653
PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, Py_hash_t *hash);
4754

‎Include/cpython/pystate.h‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -106,6 +106,10 @@ typedef struct _stack_chunk {
106106
PyObject * data[1]; /* Variable sized */
107107
} _PyStackChunk;
108108

109+
typedef struct _Py_dict_thread_state {
110+
uint64_t dict_version;
111+
} _Py_dict_thread_state;
112+
109113
struct mi_heap_s;
110114
typedef struct mi_heap_s mi_heap_t;
111115
typedef struct _PyEventRc _PyEventRc;
@@ -150,6 +154,8 @@ struct _ts {
150154
* or most recently, executing _PyEval_EvalFrameDefault. */
151155
_PyCFrame *cframe;
152156

157+
_Py_dict_thread_state dict_state;
158+
153159
/* The thread will not stop for GC or other stop-the-world requests.
154160
* Used for *short* critical sections that to prevent deadlocks between
155161
* finalizers and stopped threads. */

‎Include/dictobject.h‎

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,9 @@ PyAPI_DATA(PyTypeObject) PyDict_Type;
1919
#define PyDict_CheckExact(op) Py_IS_TYPE((op), &PyDict_Type)
2020

2121
PyAPI_FUNC(PyObject *) PyDict_New(void);
22+
PyAPI_FUNC(PyObject *) PyDict_FetchItem(PyObject *mp, PyObject *key);
23+
PyAPI_FUNC(PyObject *) PyDict_FetchItemString(PyObject *dp, const char *key);
24+
PyAPI_FUNC(PyObject *) PyDict_FetchItemWithError(PyObject *mp, PyObject *key);
2225
PyAPI_FUNC(PyObject *) PyDict_GetItem(PyObject *mp, PyObject *key);
2326
PyAPI_FUNC(PyObject *) PyDict_GetItemWithError(PyObject *mp, PyObject *key);
2427
PyAPI_FUNC(int) PyDict_SetItem(PyObject *mp, PyObject *key, PyObject *item);
@@ -67,9 +70,9 @@ PyAPI_DATA(PyTypeObject) PyDictKeys_Type;
6770
PyAPI_DATA(PyTypeObject) PyDictValues_Type;
6871
PyAPI_DATA(PyTypeObject) PyDictItems_Type;
6972

70-
#define PyDictKeys_Check(op) PyObject_TypeCheck((op), &PyDictKeys_Type)
71-
#define PyDictValues_Check(op) PyObject_TypeCheck((op), &PyDictValues_Type)
72-
#define PyDictItems_Check(op) PyObject_TypeCheck((op), &PyDictItems_Type)
73+
#define PyDictKeys_Check(op) Py_IS_TYPE((op), &PyDictKeys_Type)
74+
#define PyDictValues_Check(op) Py_IS_TYPE((op), &PyDictValues_Type)
75+
#define PyDictItems_Check(op) Py_IS_TYPE((op), &PyDictItems_Type)
7376
/* This excludes Values, since they are not sets. */
7477
# define PyDictViewSet_Check(op) \
7578
(PyDictKeys_Check(op) || PyDictItems_Check(op))

‎Include/internal/pycore_dict.h‎

Lines changed: 34 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@ extern "C" {
1111

1212
#include "pycore_dict_state.h"
1313
#include "pycore_runtime.h" // _PyRuntime
14+
#include "pycore_pystate.h" // _PyThreadState_GET()
1415

1516

1617
/* runtime lifecycle */
@@ -22,9 +23,9 @@ extern void _PyDict_Fini(PyInterpreterState *interp);
2223

2324
typedef struct {
2425
/* Cached hash code of me_key. */
25-
Py_hash_t me_hash;
2626
PyObject *me_key;
2727
PyObject *me_value; /* This field is only meaningful for combined tables */
28+
Py_hash_t me_hash;
2829
} PyDictKeyEntry;
2930

3031
typedef struct {
@@ -64,12 +65,13 @@ extern PyObject *_PyDict_Pop_KnownHash(PyObject *, PyObject *, Py_hash_t, PyObje
6465
typedef enum {
6566
DICT_KEYS_GENERAL = 0,
6667
DICT_KEYS_UNICODE = 1,
67-
DICT_KEYS_SPLIT = 2
68+
DICT_KEYS_SPLIT = 2,
6869
} DictKeysKind;
6970

7071
/* See dictobject.c for actual layout of DictKeysObject */
7172
struct _dictkeysobject {
72-
Py_ssize_t dk_refcnt;
73+
/* Mutex to prevent concurrent modification of shared keys. */
74+
_PyMutex dk_mutex;
7375

7476
/* Size of the hash table (dk_indices). It must be a power of 2. */
7577
uint8_t dk_log2_size;
@@ -108,6 +110,13 @@ struct _dictkeysobject {
108110
see the DK_ENTRIES() macro */
109111
};
110112

113+
typedef struct PyDictSharedKeysObject {
114+
uint8_t tracked;
115+
uint8_t marked;
116+
struct PyDictSharedKeysObject *next;
117+
struct _dictkeysobject keys;
118+
} PyDictSharedKeysObject;
119+
111120
/* This must be no more than 250, for the prefix size to fit in one byte. */
112121
#define SHARED_KEYS_MAX_SIZE 30
113122
#define NEXT_LOG2_SHARED_KEYS_MAX_SIZE 6
@@ -142,14 +151,31 @@ static inline PyDictUnicodeEntry* DK_UNICODE_ENTRIES(PyDictKeysObject *dk) {
142151
assert(dk->dk_kind != DICT_KEYS_GENERAL);
143152
return (PyDictUnicodeEntry*)_DK_ENTRIES(dk);
144153
}
154+
static inline PyDictSharedKeysObject* DK_AS_SPLIT(PyDictKeysObject *dk) {
155+
assert(dk->dk_kind == DICT_KEYS_SPLIT);
156+
char *mem = (char *)dk - offsetof(PyDictSharedKeysObject, keys);
157+
return (PyDictSharedKeysObject *)mem;
158+
}
145159

146160
#define DK_IS_UNICODE(dk) ((dk)->dk_kind != DICT_KEYS_GENERAL)
147161

148162
#define DICT_VERSION_INCREMENT (1 << DICT_MAX_WATCHERS)
163+
#define DICT_GLOBAL_VERSION_INCREMENT (DICT_VERSION_INCREMENT * 256)
149164
#define DICT_VERSION_MASK (DICT_VERSION_INCREMENT - 1)
150165

151-
#define DICT_NEXT_VERSION() \
152-
(_PyRuntime.dict_state.global_version += DICT_VERSION_INCREMENT)
166+
static inline uint64_t
167+
_PyDict_NextVersion(PyThreadState *tstate)
168+
{
169+
uint64_t version = tstate->dict_state.dict_version;
170+
if (version % DICT_GLOBAL_VERSION_INCREMENT == 0) {
171+
version = _Py_atomic_add_uint64(
172+
&_PyRuntime.dict_state.global_version,
173+
DICT_GLOBAL_VERSION_INCREMENT);
174+
}
175+
version += DICT_VERSION_INCREMENT;
176+
tstate->dict_state.dict_version = version;
177+
return version;
178+
}
153179

154180
void
155181
_PyDict_SendEvent(int watcher_bits,
@@ -167,9 +193,9 @@ _PyDict_NotifyEvent(PyDict_WatchEvent event,
167193
int watcher_bits = mp->ma_version_tag & DICT_VERSION_MASK;
168194
if (watcher_bits) {
169195
_PyDict_SendEvent(watcher_bits, event, mp, key, value);
170-
return DICT_NEXT_VERSION() | watcher_bits;
196+
return _PyDict_NextVersion(_PyThreadState_GET()) | watcher_bits;
171197
}
172-
return DICT_NEXT_VERSION();
198+
return _PyDict_NextVersion(_PyThreadState_GET());
173199
}
174200

175201
extern PyObject *_PyObject_MakeDictFromInstanceAttributes(PyObject *obj, PyDictValues *values);
@@ -184,7 +210,7 @@ _PyDictValues_AddToInsertionOrder(PyDictValues *values, Py_ssize_t ix)
184210
assert(ix < SHARED_KEYS_MAX_SIZE);
185211
uint8_t *size_ptr = ((uint8_t *)values)-2;
186212
int size = *size_ptr;
187-
assert(size+2 < ((uint8_t *)values)[-1]);
213+
assert(size < ((uint8_t *)values)[-1]);
188214
size++;
189215
size_ptr[-size] = (uint8_t)ix;
190216
*size_ptr = size;

‎Include/internal/pycore_dict_state.h‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,8 @@ struct _Py_dict_runtime_state {
2929

3030
#define DICT_MAX_WATCHERS 8
3131

32+
typedef struct PyDictSharedKeysObject PyDictSharedKeysObject;
33+
3234
struct _Py_dict_state {
3335
#if PyDict_MAXFREELIST > 0
3436
/* Dictionary reuse scheme to save calls to malloc and free */
@@ -38,6 +40,8 @@ struct _Py_dict_state {
3840
int keys_numfree;
3941
#endif
4042
PyDict_WatchCallback watchers[DICT_MAX_WATCHERS];
43+
/* shared keys from deallocated types (i.e., potentially dead) */
44+
PyDictSharedKeysObject *tracked_shared_keys;
4145
};
4246

4347

‎Include/internal/pycore_object.h‎

Lines changed: 51 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -489,17 +489,25 @@ _PyObject_DictOrValuesPointer(PyObject *obj)
489489
return (PyDictOrValues *)((char *)obj + MANAGED_DICT_OFFSET);
490490
}
491491

492+
static inline PyDictOrValues
493+
_PyObject_DictOrValues(PyObject *obj)
494+
{
495+
PyDictOrValues dorv;
496+
dorv.values = _Py_atomic_load_ptr_relaxed(_PyObject_DictOrValuesPointer(obj));
497+
return dorv;
498+
}
499+
492500
static inline int
493501
_PyDictOrValues_IsValues(PyDictOrValues dorv)
494502
{
495-
return ((uintptr_t)dorv.values) & 1;
503+
return ((uintptr_t)dorv.values & 4) != 0;
496504
}
497505

498506
static inline PyDictValues *
499507
_PyDictOrValues_GetValues(PyDictOrValues dorv)
500508
{
501509
assert(_PyDictOrValues_IsValues(dorv));
502-
return (PyDictValues *)(dorv.values + 1);
510+
return (PyDictValues *)((uintptr_t)dorv.values & ~7);
503511
}
504512

505513
static inline PyObject *
@@ -512,7 +520,47 @@ _PyDictOrValues_GetDict(PyDictOrValues dorv)
512520
static inline void
513521
_PyDictOrValues_SetValues(PyDictOrValues *ptr, PyDictValues *values)
514522
{
515-
ptr->values = ((char *)values) - 1;
523+
ptr->values = ((char *)values) + 4;
524+
}
525+
526+
extern PyDictValues*
527+
_PyDictValues_LockSlow(PyDictOrValues *dorv_ptr);
528+
529+
extern void
530+
_PyDictValues_UnlockSlow(PyDictOrValues *dorv_ptr);
531+
532+
extern void
533+
_PyDictValues_UnlockDict(PyDictOrValues *dorv_ptr, PyObject *dict);
534+
535+
static inline PyDictValues *
536+
_PyDictValues_Lock(PyDictOrValues *dorv_ptr)
537+
{
538+
PyDictOrValues dorv;
539+
dorv.values = _Py_atomic_load_ptr_relaxed(dorv_ptr);
540+
if (!_PyDictOrValues_IsValues(dorv)) {
541+
return NULL;
542+
}
543+
uintptr_t v = (uintptr_t)dorv.values;
544+
if ((v & LOCKED) == UNLOCKED) {
545+
if (_Py_atomic_compare_exchange_ptr(dorv_ptr, dorv.values, dorv.values + LOCKED)) {
546+
return _PyDictOrValues_GetValues(dorv);
547+
}
548+
}
549+
return _PyDictValues_LockSlow(dorv_ptr);
550+
}
551+
552+
static inline void
553+
_PyDictValues_Unlock(PyDictOrValues *dorv_ptr)
554+
{
555+
char *values = _Py_atomic_load_ptr_relaxed(&dorv_ptr->values);
556+
uintptr_t v = (uintptr_t)values;
557+
assert((v & LOCKED));
558+
if ((v & HAS_PARKED) == 0) {
559+
if (_Py_atomic_compare_exchange_ptr(dorv_ptr, values, values - LOCKED)) {
560+
return;
561+
}
562+
}
563+
_PyDictValues_UnlockSlow(dorv_ptr);
516564
}
517565

518566
extern PyObject ** _PyObject_ComputedDictPointer(PyObject *);

‎Lib/test/support/__init__.py‎

Lines changed: 16 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1822,19 +1822,23 @@ def _check_tracemalloc():
18221822

18231823

18241824
def check_free_after_iterating(test, iter, cls, args=()):
1825-
class A(cls):
1826-
def __del__(self):
1827-
nonlocal done
1828-
done = True
1829-
try:
1830-
next(it)
1831-
except StopIteration:
1832-
pass
1833-
18341825
done = False
1835-
it = iter(A(*args))
1836-
# Issue 26494: Shouldn't crash
1837-
test.assertRaises(StopIteration, next, it)
1826+
1827+
def wrapper():
1828+
class A(cls):
1829+
def __del__(self):
1830+
nonlocal done
1831+
done = True
1832+
try:
1833+
next(it)
1834+
except StopIteration:
1835+
pass
1836+
1837+
it = iter(A(*args))
1838+
# Issue 26494: Shouldn't crash
1839+
test.assertRaises(StopIteration, next, it)
1840+
1841+
wrapper()
18381842
# The sequence should be deallocated just after the end of iterating
18391843
gc_collect()
18401844
test.assertTrue(done)

‎Lib/test/test_stable_abi_ctypes.py‎

Lines changed: 3 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎Misc/stable_abi.toml‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2225,6 +2225,15 @@
22252225
added = '3.12'
22262226
abi_only = true
22272227

2228+
# New reference versions of existing APIs
2229+
2230+
[function.PyDict_FetchItem]
2231+
added = '3.12'
2232+
[function.PyDict_FetchItemString]
2233+
added = '3.12'
2234+
[function.PyDict_FetchItemWithError]
2235+
added = '3.12'
2236+
22282237
# Support for Stable ABI in debug builds
22292238

22302239
[function._Py_NegativeRefcount]

0 commit comments

Comments
 (0)