diff options
Diffstat (limited to 'contrib/tools/python3/Objects/dictobject.c')
| -rw-r--r-- | contrib/tools/python3/Objects/dictobject.c | 4249 |
1 files changed, 2961 insertions, 1288 deletions
diff --git a/contrib/tools/python3/Objects/dictobject.c b/contrib/tools/python3/Objects/dictobject.c index 7337e290e89..843ece535be 100644 --- a/contrib/tools/python3/Objects/dictobject.c +++ b/contrib/tools/python3/Objects/dictobject.c @@ -21,6 +21,7 @@ layout: | dk_log2_size | | dk_log2_index_bytes | | dk_kind | +| dk_version | | dk_usable | | dk_nentries | +---------------------+ @@ -55,7 +56,7 @@ The DictObject can be in one of two forms. Either: A combined table: ma_values == NULL, dk_refcnt == 1. - Values are stored in the me_value field of the PyDictKeysObject. + Values are stored in the me_value field of the PyDictKeyEntry. Or: A split table: ma_values != NULL, dk_refcnt >= 1 @@ -80,6 +81,8 @@ DK_ENTRIES(keys)[index] if index >= 0): Active upon key insertion. Dummy slots cannot be made Unused again else the probe sequence in case of collision would have no way to know they were once active. + In free-threaded builds dummy slots are not re-used to allow lock-free + lookups to proceed safely. 4. Pending. index >= 0, key != NULL, and value == NULL (split only) Not yet inserted in split-table. @@ -113,15 +116,20 @@ As a consequence of this, split keys have a maximum size of 16. #define PyDict_MINSIZE 8 #include "Python.h" -#include "pycore_bitutils.h" // _Py_bit_length -#include "pycore_call.h" // _PyObject_CallNoArgs() -#include "pycore_code.h" // stats -#include "pycore_dict.h" // PyDictKeysObject -#include "pycore_gc.h" // _PyObject_GC_IS_TRACKED() -#include "pycore_object.h" // _PyObject_GC_TRACK() -#include "pycore_pyerrors.h" // _PyErr_GetRaisedException() -#include "pycore_pystate.h" // _PyThreadState_GET() -#include "stringlib/eq.h" // unicode_eq() +#include "pycore_bitutils.h" // _Py_bit_length +#include "pycore_call.h" // _PyObject_CallNoArgs() +#include "pycore_ceval.h" // _PyEval_GetBuiltin() +#include "pycore_code.h" // stats +#include "pycore_critical_section.h" // Py_BEGIN_CRITICAL_SECTION, Py_END_CRITICAL_SECTION +#include "pycore_dict.h" // export _PyDict_SizeOf() +#include "pycore_freelist.h" // _PyFreeListState_GET() +#include "pycore_gc.h" // _PyObject_GC_IS_TRACKED() +#include "pycore_object.h" // _PyObject_GC_TRACK(), _PyDebugAllocatorStats() +#include "pycore_pyatomic_ft_wrappers.h" // FT_ATOMIC_LOAD_SSIZE_RELAXED +#include "pycore_pyerrors.h" // _PyErr_GetRaisedException() +#include "pycore_pystate.h" // _PyThreadState_GET() +#include "pycore_setobject.h" // _PySet_NextEntry() +#include "stringlib/eq.h" // unicode_eq() #include <stdbool.h> @@ -138,6 +146,143 @@ To avoid slowing down lookups on a near-full table, we resize the table when it's USABLE_FRACTION (currently two-thirds) full. */ +#ifdef Py_GIL_DISABLED + +static inline void +ASSERT_DICT_LOCKED(PyObject *op) +{ + _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(op); +} +#define ASSERT_DICT_LOCKED(op) ASSERT_DICT_LOCKED(_Py_CAST(PyObject*, op)) +#define ASSERT_WORLD_STOPPED_OR_DICT_LOCKED(op) \ + if (!_PyInterpreterState_GET()->stoptheworld.world_stopped) { \ + ASSERT_DICT_LOCKED(op); \ + } +#define ASSERT_WORLD_STOPPED_OR_OBJ_LOCKED(op) \ + if (!_PyInterpreterState_GET()->stoptheworld.world_stopped) { \ + _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(op); \ + } + +#define IS_DICT_SHARED(mp) _PyObject_GC_IS_SHARED(mp) +#define SET_DICT_SHARED(mp) _PyObject_GC_SET_SHARED(mp) +#define LOAD_INDEX(keys, size, idx) _Py_atomic_load_int##size##_relaxed(&((const int##size##_t*)keys->dk_indices)[idx]); +#define STORE_INDEX(keys, size, idx, value) _Py_atomic_store_int##size##_relaxed(&((int##size##_t*)keys->dk_indices)[idx], (int##size##_t)value); +#define ASSERT_OWNED_OR_SHARED(mp) \ + assert(_Py_IsOwnedByCurrentThread((PyObject *)mp) || IS_DICT_SHARED(mp)); + +#define LOCK_KEYS_IF_SPLIT(keys, kind) \ + if (kind == DICT_KEYS_SPLIT) { \ + LOCK_KEYS(keys); \ + } + +#define UNLOCK_KEYS_IF_SPLIT(keys, kind) \ + if (kind == DICT_KEYS_SPLIT) { \ + UNLOCK_KEYS(keys); \ + } + +static inline Py_ssize_t +load_keys_nentries(PyDictObject *mp) +{ + PyDictKeysObject *keys = _Py_atomic_load_ptr(&mp->ma_keys); + return _Py_atomic_load_ssize(&keys->dk_nentries); +} + +static inline void +set_keys(PyDictObject *mp, PyDictKeysObject *keys) +{ + ASSERT_OWNED_OR_SHARED(mp); + _Py_atomic_store_ptr_release(&mp->ma_keys, keys); +} + +static inline void +set_values(PyDictObject *mp, PyDictValues *values) +{ + ASSERT_OWNED_OR_SHARED(mp); + _Py_atomic_store_ptr_release(&mp->ma_values, values); +} + +#define LOCK_KEYS(keys) PyMutex_LockFlags(&keys->dk_mutex, _Py_LOCK_DONT_DETACH) +#define UNLOCK_KEYS(keys) PyMutex_Unlock(&keys->dk_mutex) + +#define ASSERT_KEYS_LOCKED(keys) assert(PyMutex_IsLocked(&keys->dk_mutex)) +#define LOAD_SHARED_KEY(key) _Py_atomic_load_ptr_acquire(&key) +#define STORE_SHARED_KEY(key, value) _Py_atomic_store_ptr_release(&key, value) +// Inc refs the keys object, giving the previous value +#define INCREF_KEYS(dk) _Py_atomic_add_ssize(&dk->dk_refcnt, 1) +// Dec refs the keys object, giving the previous value +#define DECREF_KEYS(dk) _Py_atomic_add_ssize(&dk->dk_refcnt, -1) +#define LOAD_KEYS_NENTRIES(keys) _Py_atomic_load_ssize_relaxed(&keys->dk_nentries) + +#define INCREF_KEYS_FT(dk) dictkeys_incref(dk) +#define DECREF_KEYS_FT(dk, shared) dictkeys_decref(_PyInterpreterState_GET(), dk, shared) + +static inline void split_keys_entry_added(PyDictKeysObject *keys) +{ + ASSERT_KEYS_LOCKED(keys); + + // We increase before we decrease so we never get too small of a value + // when we're racing with reads + _Py_atomic_store_ssize_relaxed(&keys->dk_nentries, keys->dk_nentries + 1); + _Py_atomic_store_ssize_release(&keys->dk_usable, keys->dk_usable - 1); +} + +#else /* Py_GIL_DISABLED */ + +#define ASSERT_DICT_LOCKED(op) +#define ASSERT_WORLD_STOPPED_OR_DICT_LOCKED(op) +#define ASSERT_WORLD_STOPPED_OR_OBJ_LOCKED(op) +#define LOCK_KEYS(keys) +#define UNLOCK_KEYS(keys) +#define ASSERT_KEYS_LOCKED(keys) +#define LOAD_SHARED_KEY(key) key +#define STORE_SHARED_KEY(key, value) key = value +#define INCREF_KEYS(dk) dk->dk_refcnt++ +#define DECREF_KEYS(dk) dk->dk_refcnt-- +#define LOAD_KEYS_NENTRIES(keys) keys->dk_nentries +#define INCREF_KEYS_FT(dk) +#define DECREF_KEYS_FT(dk, shared) +#define LOCK_KEYS_IF_SPLIT(keys, kind) +#define UNLOCK_KEYS_IF_SPLIT(keys, kind) +#define IS_DICT_SHARED(mp) (false) +#define SET_DICT_SHARED(mp) +#define LOAD_INDEX(keys, size, idx) ((const int##size##_t*)(keys->dk_indices))[idx] +#define STORE_INDEX(keys, size, idx, value) ((int##size##_t*)(keys->dk_indices))[idx] = (int##size##_t)value + +static inline void split_keys_entry_added(PyDictKeysObject *keys) +{ + keys->dk_usable--; + keys->dk_nentries++; +} + +static inline void +set_keys(PyDictObject *mp, PyDictKeysObject *keys) +{ + mp->ma_keys = keys; +} + +static inline void +set_values(PyDictObject *mp, PyDictValues *values) +{ + mp->ma_values = values; +} + +static inline Py_ssize_t +load_keys_nentries(PyDictObject *mp) +{ + return mp->ma_keys->dk_nentries; +} + + +#endif + +#define STORE_KEY(ep, key) FT_ATOMIC_STORE_PTR_RELEASE((ep)->me_key, key) +#define STORE_VALUE(ep, value) FT_ATOMIC_STORE_PTR_RELEASE((ep)->me_value, value) +#define STORE_SPLIT_VALUE(mp, idx, value) FT_ATOMIC_STORE_PTR_RELEASE(mp->ma_values->values[idx], value) +#define STORE_HASH(ep, hash) FT_ATOMIC_STORE_SSIZE_RELAXED((ep)->me_hash, hash) +#define STORE_KEYS_USABLE(keys, usable) FT_ATOMIC_STORE_SSIZE_RELAXED(keys->dk_usable, usable) +#define STORE_KEYS_NENTRIES(keys, nentries) FT_ATOMIC_STORE_SSIZE_RELAXED(keys->dk_nentries, nentries) +#define STORE_USED(mp, used) FT_ATOMIC_STORE_SSIZE_RELAXED(mp->ma_used, used) + #define PERTURB_SHIFT 5 /* @@ -235,45 +380,56 @@ equally good collision statistics, needed less code & used less memory. static int dictresize(PyInterpreterState *interp, PyDictObject *mp, uint8_t log_newsize, int unicode); -static PyObject* dict_iter(PyDictObject *dict); +static PyObject* dict_iter(PyObject *dict); + +static int +setitem_lock_held(PyDictObject *mp, PyObject *key, PyObject *value); +static int +dict_setdefault_ref_lock_held(PyObject *d, PyObject *key, PyObject *default_value, + PyObject **result, int incref_result); + +#ifndef NDEBUG +static int _PyObject_InlineValuesConsistencyCheck(PyObject *obj); +#endif #include "clinic/dictobject.c.h" -#if PyDict_MAXFREELIST > 0 -static struct _Py_dict_state * -get_dict_state(PyInterpreterState *interp) +#ifdef WITH_FREELISTS +static struct _Py_dict_freelist * +get_dict_freelist(void) +{ + struct _Py_object_freelists *freelists = _Py_object_freelists_GET(); + return &freelists->dicts; +} + +static struct _Py_dictkeys_freelist * +get_dictkeys_freelist(void) { - return &interp->dict_state; + struct _Py_object_freelists *freelists = _Py_object_freelists_GET(); + return &freelists->dictkeys; } #endif void -_PyDict_ClearFreeList(PyInterpreterState *interp) +_PyDict_ClearFreeList(struct _Py_object_freelists *freelists, int is_finalization) { -#if PyDict_MAXFREELIST > 0 - struct _Py_dict_state *state = &interp->dict_state; - while (state->numfree) { - PyDictObject *op = state->free_list[--state->numfree]; +#ifdef WITH_FREELISTS + struct _Py_dict_freelist *freelist = &freelists->dicts; + while (freelist->numfree > 0) { + PyDictObject *op = freelist->items[--freelist->numfree]; assert(PyDict_CheckExact(op)); PyObject_GC_Del(op); } - while (state->keys_numfree) { - PyObject_Free(state->keys_free_list[--state->keys_numfree]); + struct _Py_dictkeys_freelist *keys_freelist = &freelists->dictkeys; + while (keys_freelist->numfree > 0) { + PyMem_Free(keys_freelist->items[--keys_freelist->numfree]); + } + if (is_finalization) { + freelist->numfree = -1; + keys_freelist->numfree = -1; } -#endif -} - - -void -_PyDict_Fini(PyInterpreterState *interp) -{ - _PyDict_ClearFreeList(interp); -#if defined(Py_DEBUG) && PyDict_MAXFREELIST > 0 - struct _Py_dict_state *state = &interp->dict_state; - state->numfree = -1; - state->keys_numfree = -1; #endif } @@ -281,24 +437,26 @@ static inline Py_hash_t unicode_get_hash(PyObject *o) { assert(PyUnicode_CheckExact(o)); - return _PyASCIIObject_CAST(o)->hash; + return FT_ATOMIC_LOAD_SSIZE_RELAXED(_PyASCIIObject_CAST(o)->hash); } /* Print summary info about the state of the optimized allocator */ void _PyDict_DebugMallocStats(FILE *out) { -#if PyDict_MAXFREELIST > 0 - PyInterpreterState *interp = _PyInterpreterState_GET(); - struct _Py_dict_state *state = get_dict_state(interp); +#ifdef WITH_FREELISTS + struct _Py_dict_freelist *dict_freelist = get_dict_freelist(); _PyDebugAllocatorStats(out, "free PyDictObject", - state->numfree, sizeof(PyDictObject)); + dict_freelist->numfree, sizeof(PyDictObject)); + struct _Py_dictkeys_freelist *dictkeys_freelist = get_dictkeys_freelist(); + _PyDebugAllocatorStats(out, "free PyDictKeysObject", + dictkeys_freelist->numfree, sizeof(PyDictKeysObject)); #endif } #define DK_MASK(dk) (DK_SIZE(dk)-1) -static void free_keys_object(PyInterpreterState *interp, PyDictKeysObject *keys); +static void free_keys_object(PyDictKeysObject *keys, bool use_qsbr); /* PyDictKeysObject has refcounts like PyObject does, so we have the following two functions to mirror what Py_INCREF() and Py_DECREF() do. @@ -310,27 +468,43 @@ static void free_keys_object(PyInterpreterState *interp, PyDictKeysObject *keys) static inline void dictkeys_incref(PyDictKeysObject *dk) { - if (dk->dk_refcnt == _Py_IMMORTAL_REFCNT) { + if (FT_ATOMIC_LOAD_SSIZE_RELAXED(dk->dk_refcnt) == _Py_IMMORTAL_REFCNT) { return; } #ifdef Py_REF_DEBUG - _Py_IncRefTotal(_PyInterpreterState_GET()); + _Py_IncRefTotal(_PyThreadState_GET()); #endif - dk->dk_refcnt++; + INCREF_KEYS(dk); } static inline void -dictkeys_decref(PyInterpreterState *interp, PyDictKeysObject *dk) +dictkeys_decref(PyInterpreterState *interp, PyDictKeysObject *dk, bool use_qsbr) { - if (dk->dk_refcnt == _Py_IMMORTAL_REFCNT) { + if (FT_ATOMIC_LOAD_SSIZE_RELAXED(dk->dk_refcnt) == _Py_IMMORTAL_REFCNT) { return; } - assert(dk->dk_refcnt > 0); + assert(FT_ATOMIC_LOAD_SSIZE(dk->dk_refcnt) > 0); #ifdef Py_REF_DEBUG - _Py_DecRefTotal(_PyInterpreterState_GET()); + _Py_DecRefTotal(_PyThreadState_GET()); #endif - if (--dk->dk_refcnt == 0) { - free_keys_object(interp, dk); + if (DECREF_KEYS(dk) == 1) { + if (DK_IS_UNICODE(dk)) { + PyDictUnicodeEntry *entries = DK_UNICODE_ENTRIES(dk); + Py_ssize_t i, n; + for (i = 0, n = dk->dk_nentries; i < n; i++) { + Py_XDECREF(entries[i].me_key); + Py_XDECREF(entries[i].me_value); + } + } + else { + PyDictKeyEntry *entries = DK_ENTRIES(dk); + Py_ssize_t i, n; + for (i = 0, n = dk->dk_nentries; i < n; i++) { + Py_XDECREF(entries[i].me_key); + Py_XDECREF(entries[i].me_value); + } + } + free_keys_object(dk, use_qsbr); } } @@ -342,22 +516,18 @@ dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i) Py_ssize_t ix; if (log2size < 8) { - const int8_t *indices = (const int8_t*)(keys->dk_indices); - ix = indices[i]; + ix = LOAD_INDEX(keys, 8, i); } else if (log2size < 16) { - const int16_t *indices = (const int16_t*)(keys->dk_indices); - ix = indices[i]; + ix = LOAD_INDEX(keys, 16, i); } #if SIZEOF_VOID_P > 4 else if (log2size >= 32) { - const int64_t *indices = (const int64_t*)(keys->dk_indices); - ix = indices[i]; + ix = LOAD_INDEX(keys, 64, i); } #endif else { - const int32_t *indices = (const int32_t*)(keys->dk_indices); - ix = indices[i]; + ix = LOAD_INDEX(keys, 32, i); } assert(ix >= DKIX_DUMMY); return ix; @@ -373,25 +543,21 @@ dictkeys_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix) assert(keys->dk_version == 0); if (log2size < 8) { - int8_t *indices = (int8_t*)(keys->dk_indices); assert(ix <= 0x7f); - indices[i] = (char)ix; + STORE_INDEX(keys, 8, i, ix); } else if (log2size < 16) { - int16_t *indices = (int16_t*)(keys->dk_indices); assert(ix <= 0x7fff); - indices[i] = (int16_t)ix; + STORE_INDEX(keys, 16, i, ix); } #if SIZEOF_VOID_P > 4 else if (log2size >= 32) { - int64_t *indices = (int64_t*)(keys->dk_indices); - indices[i] = ix; + STORE_INDEX(keys, 64, i, ix); } #endif else { - int32_t *indices = (int32_t*)(keys->dk_indices); assert(ix <= 0x7fffffff); - indices[i] = (int32_t)ix; + STORE_INDEX(keys, 32, i, ix); } } @@ -414,13 +580,13 @@ static inline uint8_t calculate_log2_keysize(Py_ssize_t minsize) { #if SIZEOF_LONG == SIZEOF_SIZE_T - minsize = (minsize | PyDict_MINSIZE) - 1; - return _Py_bit_length(minsize | (PyDict_MINSIZE-1)); + minsize = Py_MAX(minsize, PyDict_MINSIZE); + return _Py_bit_length(minsize - 1); #elif defined(_MSC_VER) - // On 64bit Windows, sizeof(long) == 4. - minsize = (minsize | PyDict_MINSIZE) - 1; + // On 64bit Windows, sizeof(long) == 4. We cannot use _Py_bit_length. + minsize = Py_MAX(minsize, PyDict_MINSIZE); unsigned long msb; - _BitScanReverse64(&msb, (uint64_t)minsize); + _BitScanReverse64(&msb, (uint64_t)minsize - 1); return (uint8_t)(msb + 1); #else uint8_t log2_size; @@ -467,6 +633,9 @@ static PyDictKeysObject empty_keys_struct = { 0, /* dk_log2_size */ 3, /* dk_log2_index_bytes */ DICT_KEYS_UNICODE, /* dk_kind */ +#ifdef Py_GIL_DISABLED + {0}, /* dk_mutex */ +#endif 1, /* dk_version */ 0, /* dk_usable (immutable) */ 0, /* dk_nentries */ @@ -489,8 +658,9 @@ static inline int get_index_from_order(PyDictObject *mp, Py_ssize_t i) { assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE); - assert(i < (((char *)mp->ma_values)[-2])); - return ((char *)mp->ma_values)[-3-i]; + assert(i < mp->ma_values->size); + uint8_t *array = get_insertion_order_array(mp->ma_values); + return array[i]; } #ifdef DEBUG_PYDICT @@ -513,6 +683,8 @@ dump_entries(PyDictKeysObject *dk) int _PyDict_CheckConsistency(PyObject *op, int check_content) { + ASSERT_WORLD_STOPPED_OR_DICT_LOCKED(op); + #define CHECK(expr) \ do { if (!(expr)) { _PyObject_ASSERT_FAILED_MSG(op, Py_STRINGIFY(expr)); } } while (0) @@ -524,10 +696,15 @@ _PyDict_CheckConsistency(PyObject *op, int check_content) int splitted = _PyDict_HasSplitTable(mp); Py_ssize_t usable = USABLE_FRACTION(DK_SIZE(keys)); + // In the free-threaded build, shared keys may be concurrently modified, + // so use atomic loads. + Py_ssize_t dk_usable = FT_ATOMIC_LOAD_SSIZE_ACQUIRE(keys->dk_usable); + Py_ssize_t dk_nentries = FT_ATOMIC_LOAD_SSIZE_ACQUIRE(keys->dk_nentries); + CHECK(0 <= mp->ma_used && mp->ma_used <= usable); - CHECK(0 <= keys->dk_usable && keys->dk_usable <= usable); - CHECK(0 <= keys->dk_nentries && keys->dk_nentries <= usable); - CHECK(keys->dk_usable + keys->dk_nentries <= usable); + CHECK(0 <= dk_usable && dk_usable <= usable); + CHECK(0 <= dk_nentries && dk_nentries <= usable); + CHECK(dk_usable + dk_nentries <= usable); if (!splitted) { /* combined table */ @@ -537,9 +714,14 @@ _PyDict_CheckConsistency(PyObject *op, int check_content) else { CHECK(keys->dk_kind == DICT_KEYS_SPLIT); CHECK(mp->ma_used <= SHARED_KEYS_MAX_SIZE); + if (mp->ma_values->embedded) { + CHECK(mp->ma_values->embedded == 1); + CHECK(mp->ma_values->valid == 1); + } } if (check_content) { + LOCK_KEYS_IF_SPLIT(keys, keys->dk_kind); for (Py_ssize_t i=0; i < DK_SIZE(keys); i++) { Py_ssize_t ix = dictkeys_get_index(keys, i); CHECK(DKIX_DUMMY <= ix && ix <= usable); @@ -595,6 +777,7 @@ _PyDict_CheckConsistency(PyObject *op, int check_content) CHECK(mp->ma_values->values[index] != NULL); } } + UNLOCK_KEYS_IF_SPLIT(keys, keys->dk_kind); } return 1; @@ -628,34 +811,33 @@ new_keys_object(PyInterpreterState *interp, uint8_t log2_size, bool unicode) log2_bytes = log2_size + 2; } -#if PyDict_MAXFREELIST > 0 - struct _Py_dict_state *state = get_dict_state(interp); -#ifdef Py_DEBUG - // new_keys_object() must not be called after _PyDict_Fini() - assert(state->keys_numfree != -1); -#endif - if (log2_size == PyDict_LOG_MINSIZE && unicode && state->keys_numfree > 0) { - dk = state->keys_free_list[--state->keys_numfree]; +#ifdef WITH_FREELISTS + struct _Py_dictkeys_freelist *freelist = get_dictkeys_freelist(); + if (log2_size == PyDict_LOG_MINSIZE && unicode && freelist->numfree > 0) { + dk = freelist->items[--freelist->numfree]; OBJECT_STAT_INC(from_freelist); } else #endif { - dk = PyObject_Malloc(sizeof(PyDictKeysObject) - + ((size_t)1 << log2_bytes) - + entry_size * usable); + dk = PyMem_Malloc(sizeof(PyDictKeysObject) + + ((size_t)1 << log2_bytes) + + entry_size * usable); if (dk == NULL) { PyErr_NoMemory(); return NULL; } } #ifdef Py_REF_DEBUG - _Py_IncRefTotal(_PyInterpreterState_GET()); + _Py_IncRefTotal(_PyThreadState_GET()); #endif dk->dk_refcnt = 1; dk->dk_log2_size = log2_size; dk->dk_log2_index_bytes = log2_bytes; dk->dk_kind = unicode ? DICT_KEYS_UNICODE : DICT_KEYS_GENERAL; +#ifdef Py_GIL_DISABLED + dk->dk_mutex = (PyMutex){0}; +#endif dk->dk_nentries = 0; dk->dk_usable = usable; dk->dk_version = 0; @@ -665,63 +847,66 @@ new_keys_object(PyInterpreterState *interp, uint8_t log2_size, bool unicode) } static void -free_keys_object(PyInterpreterState *interp, PyDictKeysObject *keys) +free_keys_object(PyDictKeysObject *keys, bool use_qsbr) { - assert(keys != Py_EMPTY_KEYS); - if (DK_IS_UNICODE(keys)) { - PyDictUnicodeEntry *entries = DK_UNICODE_ENTRIES(keys); - Py_ssize_t i, n; - for (i = 0, n = keys->dk_nentries; i < n; i++) { - Py_XDECREF(entries[i].me_key); - Py_XDECREF(entries[i].me_value); - } - } - else { - PyDictKeyEntry *entries = DK_ENTRIES(keys); - Py_ssize_t i, n; - for (i = 0, n = keys->dk_nentries; i < n; i++) { - Py_XDECREF(entries[i].me_key); - Py_XDECREF(entries[i].me_value); - } +#ifdef Py_GIL_DISABLED + if (use_qsbr) { + _PyMem_FreeDelayed(keys, _PyDict_KeysSize(keys)); + return; } -#if PyDict_MAXFREELIST > 0 - struct _Py_dict_state *state = get_dict_state(interp); -#ifdef Py_DEBUG - // free_keys_object() must not be called after _PyDict_Fini() - assert(state->keys_numfree != -1); #endif +#ifdef WITH_FREELISTS + struct _Py_dictkeys_freelist *freelist = get_dictkeys_freelist(); if (DK_LOG_SIZE(keys) == PyDict_LOG_MINSIZE - && state->keys_numfree < PyDict_MAXFREELIST + && freelist->numfree < PyDict_MAXFREELIST + && freelist->numfree >= 0 && DK_IS_UNICODE(keys)) { - state->keys_free_list[state->keys_numfree++] = keys; + freelist->items[freelist->numfree++] = keys; OBJECT_STAT_INC(to_freelist); return; } #endif - PyObject_Free(keys); + PyMem_Free(keys); } +static size_t +values_size_from_count(size_t count) +{ + assert(count >= 1); + size_t suffix_size = _Py_SIZE_ROUND_UP(count, sizeof(PyObject *)); + assert(suffix_size < 128); + assert(suffix_size % sizeof(PyObject *) == 0); + return (count + 1) * sizeof(PyObject *) + suffix_size; +} + +#define CACHED_KEYS(tp) (((PyHeapTypeObject*)tp)->ht_cached_keys) + static inline PyDictValues* new_values(size_t size) { - assert(size >= 1); - size_t prefix_size = _Py_SIZE_ROUND_UP(size+2, sizeof(PyObject *)); - assert(prefix_size < 256); - size_t n = prefix_size + size * sizeof(PyObject *); - uint8_t *mem = PyMem_Malloc(n); - if (mem == NULL) { + size_t n = values_size_from_count(size); + PyDictValues *res = (PyDictValues *)PyMem_Malloc(n); + if (res == NULL) { return NULL; } - assert(prefix_size % sizeof(PyObject *) == 0); - mem[prefix_size-1] = (uint8_t)prefix_size; - return (PyDictValues*)(mem + prefix_size); + res->embedded = 0; + res->size = 0; + assert(size < 256); + res->capacity = (uint8_t)size; + return res; } static inline void -free_values(PyDictValues *values) +free_values(PyDictValues *values, bool use_qsbr) { - int prefix_size = ((uint8_t *)values)[-1]; - PyMem_Free(((char *)values)-prefix_size); + assert(values->embedded == 0); +#ifdef Py_GIL_DISABLED + if (use_qsbr) { + _PyMem_FreeDelayed(values, values_size_from_count(values->capacity)); + return; + } +#endif + PyMem_Free(values); } /* Consumes a reference to the keys object */ @@ -732,14 +917,10 @@ new_dict(PyInterpreterState *interp, { PyDictObject *mp; assert(keys != NULL); -#if PyDict_MAXFREELIST > 0 - struct _Py_dict_state *state = get_dict_state(interp); -#ifdef Py_DEBUG - // new_dict() must not be called after _PyDict_Fini() - assert(state->numfree != -1); -#endif - if (state->numfree) { - mp = state->free_list[--state->numfree]; +#ifdef WITH_FREELISTS + struct _Py_dict_freelist *freelist = get_dict_freelist(); + if (freelist->numfree > 0) { + mp = freelist->items[--freelist->numfree]; assert (mp != NULL); assert (Py_IS_TYPE(mp, &PyDict_Type)); OBJECT_STAT_INC(from_freelist); @@ -750,9 +931,9 @@ new_dict(PyInterpreterState *interp, { mp = PyObject_GC_New(PyDictObject, &PyDict_Type); if (mp == NULL) { - dictkeys_decref(interp, keys); + dictkeys_decref(interp, keys, false); if (free_values_on_failure) { - free_values(values); + free_values(values, false); } return NULL; } @@ -765,23 +946,15 @@ new_dict(PyInterpreterState *interp, return (PyObject *)mp; } -static inline size_t -shared_keys_usable_size(PyDictKeysObject *keys) -{ - return (size_t)keys->dk_nentries + (size_t)keys->dk_usable; -} - -/* Consumes a reference to the keys object */ static PyObject * new_dict_with_shared_keys(PyInterpreterState *interp, PyDictKeysObject *keys) { size_t size = shared_keys_usable_size(keys); PyDictValues *values = new_values(size); if (values == NULL) { - dictkeys_decref(interp, keys); return PyErr_NoMemory(); } - ((char *)values)[-2] = 0; + dictkeys_incref(keys); for (size_t i = 0; i < size; i++) { values->values[i] = NULL; } @@ -793,13 +966,15 @@ static PyDictKeysObject * clone_combined_dict_keys(PyDictObject *orig) { assert(PyDict_Check(orig)); - assert(Py_TYPE(orig)->tp_iter == (getiterfunc)dict_iter); + assert(Py_TYPE(orig)->tp_iter == dict_iter); assert(orig->ma_values == NULL); assert(orig->ma_keys != Py_EMPTY_KEYS); assert(orig->ma_keys->dk_refcnt == 1); + ASSERT_DICT_LOCKED(orig); + size_t keys_size = _PyDict_KeysSize(orig->ma_keys); - PyDictKeysObject *keys = PyObject_Malloc(keys_size); + PyDictKeysObject *keys = PyMem_Malloc(keys_size); if (keys == NULL) { PyErr_NoMemory(); return NULL; @@ -841,7 +1016,7 @@ clone_combined_dict_keys(PyDictObject *orig) we have it now; calling dictkeys_incref would be an error as keys->dk_refcnt is already set to 1 (after memcpy). */ #ifdef Py_REF_DEBUG - _Py_IncRefTotal(_PyInterpreterState_GET()); + _Py_IncRefTotal(_PyThreadState_GET()); #endif return keys; } @@ -876,11 +1051,11 @@ lookdict_index(PyDictKeysObject *k, Py_hash_t hash, Py_ssize_t index) Py_UNREACHABLE(); } -// Search non-Unicode key from Unicode table -static Py_ssize_t -unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash) +static inline Py_ALWAYS_INLINE Py_ssize_t +do_lookup(PyDictObject *mp, PyDictKeysObject *dk, PyObject *key, Py_hash_t hash, + int (*check_lookup)(PyDictObject *, PyDictKeysObject *, void *, Py_ssize_t ix, PyObject *key, Py_hash_t)) { - PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk); + void *ep0 = _DK_ENTRIES(dk); size_t mask = DK_MASK(dk); size_t perturb = hash; size_t i = (size_t)hash & mask; @@ -888,73 +1063,26 @@ unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key for (;;) { ix = dictkeys_get_index(dk, i); if (ix >= 0) { - PyDictUnicodeEntry *ep = &ep0[ix]; - assert(ep->me_key != NULL); - assert(PyUnicode_CheckExact(ep->me_key)); - if (ep->me_key == key) { + int cmp = check_lookup(mp, dk, ep0, ix, key, hash); + if (cmp < 0) { + return cmp; + } else if (cmp) { return ix; } - if (unicode_get_hash(ep->me_key) == hash) { - PyObject *startkey = ep->me_key; - Py_INCREF(startkey); - int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); - Py_DECREF(startkey); - if (cmp < 0) { - return DKIX_ERROR; - } - if (dk == mp->ma_keys && ep->me_key == startkey) { - if (cmp > 0) { - return ix; - } - } - else { - /* The dict was mutated, restart */ - return DKIX_KEY_CHANGED; - } - } } else if (ix == DKIX_EMPTY) { return DKIX_EMPTY; } perturb >>= PERTURB_SHIFT; i = mask & (i*5 + perturb + 1); - } - Py_UNREACHABLE(); -} -// Search Unicode key from Unicode table. -static Py_ssize_t _Py_HOT_FUNCTION -unicodekeys_lookup_unicode(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash) -{ - PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk); - size_t mask = DK_MASK(dk); - size_t perturb = hash; - size_t i = (size_t)hash & mask; - Py_ssize_t ix; - for (;;) { - ix = dictkeys_get_index(dk, i); - if (ix >= 0) { - PyDictUnicodeEntry *ep = &ep0[ix]; - assert(ep->me_key != NULL); - assert(PyUnicode_CheckExact(ep->me_key)); - if (ep->me_key == key || - (unicode_get_hash(ep->me_key) == hash && unicode_eq(ep->me_key, key))) { - return ix; - } - } - else if (ix == DKIX_EMPTY) { - return DKIX_EMPTY; - } - perturb >>= PERTURB_SHIFT; - i = mask & (i*5 + perturb + 1); // Manual loop unrolling ix = dictkeys_get_index(dk, i); if (ix >= 0) { - PyDictUnicodeEntry *ep = &ep0[ix]; - assert(ep->me_key != NULL); - assert(PyUnicode_CheckExact(ep->me_key)); - if (ep->me_key == key || - (unicode_get_hash(ep->me_key) == hash && unicode_eq(ep->me_key, key))) { + int cmp = check_lookup(mp, dk, ep0, ix, key, hash); + if (cmp < 0) { + return cmp; + } else if (cmp) { return ix; } } @@ -967,49 +1095,125 @@ unicodekeys_lookup_unicode(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash) Py_UNREACHABLE(); } -// Search key from Generic table. +static inline int +compare_unicode_generic(PyDictObject *mp, PyDictKeysObject *dk, + void *ep0, Py_ssize_t ix, PyObject *key, Py_hash_t hash) +{ + PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix]; + assert(ep->me_key != NULL); + assert(PyUnicode_CheckExact(ep->me_key)); + assert(!PyUnicode_CheckExact(key)); + + if (unicode_get_hash(ep->me_key) == hash) { + PyObject *startkey = ep->me_key; + Py_INCREF(startkey); + int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); + Py_DECREF(startkey); + if (cmp < 0) { + return DKIX_ERROR; + } + if (dk == mp->ma_keys && ep->me_key == startkey) { + return cmp; + } + else { + /* The dict was mutated, restart */ + return DKIX_KEY_CHANGED; + } + } + return 0; +} + +// Search non-Unicode key from Unicode table static Py_ssize_t -dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash) +unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash) { - PyDictKeyEntry *ep0 = DK_ENTRIES(dk); - size_t mask = DK_MASK(dk); - size_t perturb = hash; - size_t i = (size_t)hash & mask; - Py_ssize_t ix; - for (;;) { - ix = dictkeys_get_index(dk, i); - if (ix >= 0) { - PyDictKeyEntry *ep = &ep0[ix]; - assert(ep->me_key != NULL); - if (ep->me_key == key) { - return ix; - } - if (ep->me_hash == hash) { - PyObject *startkey = ep->me_key; - Py_INCREF(startkey); - int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); - Py_DECREF(startkey); - if (cmp < 0) { - return DKIX_ERROR; - } - if (dk == mp->ma_keys && ep->me_key == startkey) { - if (cmp > 0) { - return ix; - } - } - else { - /* The dict was mutated, restart */ - return DKIX_KEY_CHANGED; - } - } + return do_lookup(mp, dk, key, hash, compare_unicode_generic); +} + +static inline int +compare_unicode_unicode(PyDictObject *mp, PyDictKeysObject *dk, + void *ep0, Py_ssize_t ix, PyObject *key, Py_hash_t hash) +{ + PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix]; + PyObject *ep_key = FT_ATOMIC_LOAD_PTR_RELAXED(ep->me_key); + assert(ep_key != NULL); + assert(PyUnicode_CheckExact(ep_key)); + if (ep_key == key || + (unicode_get_hash(ep_key) == hash && unicode_eq(ep_key, key))) { + return 1; + } + return 0; +} + +static Py_ssize_t _Py_HOT_FUNCTION +unicodekeys_lookup_unicode(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash) +{ + return do_lookup(NULL, dk, key, hash, compare_unicode_unicode); +} + +static inline int +compare_generic(PyDictObject *mp, PyDictKeysObject *dk, + void *ep0, Py_ssize_t ix, PyObject *key, Py_hash_t hash) +{ + PyDictKeyEntry *ep = &((PyDictKeyEntry *)ep0)[ix]; + assert(ep->me_key != NULL); + if (ep->me_key == key) { + return 1; + } + if (ep->me_hash == hash) { + PyObject *startkey = ep->me_key; + Py_INCREF(startkey); + int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); + Py_DECREF(startkey); + if (cmp < 0) { + return DKIX_ERROR; } - else if (ix == DKIX_EMPTY) { - return DKIX_EMPTY; + if (dk == mp->ma_keys && ep->me_key == startkey) { + return cmp; + } + else { + /* The dict was mutated, restart */ + return DKIX_KEY_CHANGED; } - perturb >>= PERTURB_SHIFT; - i = mask & (i*5 + perturb + 1); } - Py_UNREACHABLE(); + return 0; +} + +static Py_ssize_t +dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash) +{ + return do_lookup(mp, dk, key, hash, compare_generic); +} + +#ifdef Py_GIL_DISABLED + +static Py_ssize_t +unicodekeys_lookup_unicode_threadsafe(PyDictKeysObject* dk, PyObject *key, + Py_hash_t hash); + +#endif + +static Py_ssize_t +unicodekeys_lookup_split(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash) +{ + Py_ssize_t ix; + assert(dk->dk_kind == DICT_KEYS_SPLIT); + assert(PyUnicode_CheckExact(key)); + +#ifdef Py_GIL_DISABLED + // A split dictionaries keys can be mutated by other dictionaries + // but if we have a unicode key we can avoid locking the shared + // keys. + ix = unicodekeys_lookup_unicode_threadsafe(dk, key, hash); + if (ix == DKIX_KEY_CHANGED) { + LOCK_KEYS(dk); + ix = unicodekeys_lookup_unicode(dk, key, hash); + UNLOCK_KEYS(dk); + } +#else + ix = unicodekeys_lookup_unicode(dk, key, hash); +#endif + return ix; } /* Lookup a string in a (all unicode) dict keys. @@ -1036,6 +1240,25 @@ _PyDictKeys_StringLookup(PyDictKeysObject* dk, PyObject *key) return unicodekeys_lookup_unicode(dk, key, hash); } +/* Like _PyDictKeys_StringLookup() but only works on split keys. Note + * that in free-threaded builds this locks the keys object as required. + */ +Py_ssize_t +_PyDictKeys_StringLookupSplit(PyDictKeysObject* dk, PyObject *key) +{ + assert(dk->dk_kind == DICT_KEYS_SPLIT); + assert(PyUnicode_CheckExact(key)); + Py_hash_t hash = unicode_get_hash(key); + if (hash == -1) { + hash = PyUnicode_Type.tp_hash(key); + if (hash == -1) { + PyErr_Clear(); + return DKIX_ERROR; + } + } + return unicodekeys_lookup_split(dk, key, hash); +} + /* The basic lookup function used by all operations. This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. @@ -1058,16 +1281,40 @@ _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **valu DictKeysKind kind; Py_ssize_t ix; + _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(mp); start: dk = mp->ma_keys; kind = dk->dk_kind; if (kind != DICT_KEYS_GENERAL) { if (PyUnicode_CheckExact(key)) { +#ifdef Py_GIL_DISABLED + if (kind == DICT_KEYS_SPLIT) { + // A split dictionaries keys can be mutated by other + // dictionaries but if we have a unicode key we can avoid + // locking the shared keys. + ix = unicodekeys_lookup_unicode_threadsafe(dk, key, hash); + if (ix == DKIX_KEY_CHANGED) { + LOCK_KEYS(dk); + ix = unicodekeys_lookup_unicode(dk, key, hash); + UNLOCK_KEYS(dk); + } + } + else { + ix = unicodekeys_lookup_unicode(dk, key, hash); + } +#else ix = unicodekeys_lookup_unicode(dk, key, hash); +#endif } else { + INCREF_KEYS_FT(dk); + LOCK_KEYS_IF_SPLIT(dk, kind); + ix = unicodekeys_lookup_generic(mp, dk, key, hash); + + UNLOCK_KEYS_IF_SPLIT(dk, kind); + DECREF_KEYS_FT(dk, IS_DICT_SHARED(mp)); if (ix == DKIX_KEY_CHANGED) { goto start; } @@ -1101,6 +1348,270 @@ start: return ix; } +#ifdef Py_GIL_DISABLED +static inline void +ensure_shared_on_read(PyDictObject *mp) +{ + if (!_Py_IsOwnedByCurrentThread((PyObject *)mp) && !IS_DICT_SHARED(mp)) { + // The first time we access a dict from a non-owning thread we mark it + // as shared. This ensures that a concurrent resize operation will + // delay freeing the old keys or values using QSBR, which is necessary + // to safely allow concurrent reads without locking... + Py_BEGIN_CRITICAL_SECTION(mp); + if (!IS_DICT_SHARED(mp)) { + SET_DICT_SHARED(mp); + } + Py_END_CRITICAL_SECTION(); + } +} +#endif + +static inline void +ensure_shared_on_resize(PyDictObject *mp) +{ +#ifdef Py_GIL_DISABLED + _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(mp); + + if (!_Py_IsOwnedByCurrentThread((PyObject *)mp) && !IS_DICT_SHARED(mp)) { + // We are writing to the dict from another thread that owns + // it and we haven't marked it as shared which will ensure + // that when we re-size ma_keys or ma_values that we will + // free using QSBR. We need to lock the dictionary to + // contend with writes from the owning thread, mark it as + // shared, and then we can continue with lock-free reads. + // Technically this is a little heavy handed, we could just + // free the individual old keys / old-values using qsbr + SET_DICT_SHARED(mp); + } +#endif +} + +#ifdef Py_GIL_DISABLED + +static inline Py_ALWAYS_INLINE int +compare_unicode_generic_threadsafe(PyDictObject *mp, PyDictKeysObject *dk, + void *ep0, Py_ssize_t ix, PyObject *key, Py_hash_t hash) +{ + PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix]; + PyObject *startkey = _Py_atomic_load_ptr_relaxed(&ep->me_key); + assert(startkey == NULL || PyUnicode_CheckExact(ep->me_key)); + assert(!PyUnicode_CheckExact(key)); + + if (startkey != NULL) { + if (!_Py_TryIncrefCompare(&ep->me_key, startkey)) { + return DKIX_KEY_CHANGED; + } + + if (unicode_get_hash(startkey) == hash) { + int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); + Py_DECREF(startkey); + if (cmp < 0) { + return DKIX_ERROR; + } + if (dk == _Py_atomic_load_ptr_relaxed(&mp->ma_keys) && + startkey == _Py_atomic_load_ptr_relaxed(&ep->me_key)) { + return cmp; + } + else { + /* The dict was mutated, restart */ + return DKIX_KEY_CHANGED; + } + } + else { + Py_DECREF(startkey); + } + } + return 0; +} + +// Search non-Unicode key from Unicode table +static Py_ssize_t +unicodekeys_lookup_generic_threadsafe(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash) +{ + return do_lookup(mp, dk, key, hash, compare_unicode_generic_threadsafe); +} + +static inline Py_ALWAYS_INLINE int +compare_unicode_unicode_threadsafe(PyDictObject *mp, PyDictKeysObject *dk, + void *ep0, Py_ssize_t ix, PyObject *key, Py_hash_t hash) +{ + PyDictUnicodeEntry *ep = &((PyDictUnicodeEntry *)ep0)[ix]; + PyObject *startkey = _Py_atomic_load_ptr_relaxed(&ep->me_key); + assert(startkey == NULL || PyUnicode_CheckExact(startkey)); + if (startkey == key) { + return 1; + } + if (startkey != NULL) { + if (_Py_IsImmortal(startkey)) { + return unicode_get_hash(startkey) == hash && unicode_eq(startkey, key); + } + else { + if (!_Py_TryIncrefCompare(&ep->me_key, startkey)) { + return DKIX_KEY_CHANGED; + } + if (unicode_get_hash(startkey) == hash && unicode_eq(startkey, key)) { + Py_DECREF(startkey); + return 1; + } + Py_DECREF(startkey); + } + } + return 0; +} + +static Py_ssize_t _Py_HOT_FUNCTION +unicodekeys_lookup_unicode_threadsafe(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash) +{ + return do_lookup(NULL, dk, key, hash, compare_unicode_unicode_threadsafe); +} + +static inline Py_ALWAYS_INLINE int +compare_generic_threadsafe(PyDictObject *mp, PyDictKeysObject *dk, + void *ep0, Py_ssize_t ix, PyObject *key, Py_hash_t hash) +{ + PyDictKeyEntry *ep = &((PyDictKeyEntry *)ep0)[ix]; + PyObject *startkey = _Py_atomic_load_ptr_relaxed(&ep->me_key); + if (startkey == key) { + return 1; + } + Py_ssize_t ep_hash = _Py_atomic_load_ssize_relaxed(&ep->me_hash); + if (ep_hash == hash) { + if (startkey == NULL || !_Py_TryIncrefCompare(&ep->me_key, startkey)) { + return DKIX_KEY_CHANGED; + } + int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); + Py_DECREF(startkey); + if (cmp < 0) { + return DKIX_ERROR; + } + if (dk == _Py_atomic_load_ptr_relaxed(&mp->ma_keys) && + startkey == _Py_atomic_load_ptr_relaxed(&ep->me_key)) { + return cmp; + } + else { + /* The dict was mutated, restart */ + return DKIX_KEY_CHANGED; + } + } + return 0; +} + +static Py_ssize_t +dictkeys_generic_lookup_threadsafe(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash) +{ + return do_lookup(mp, dk, key, hash, compare_generic_threadsafe); +} + +Py_ssize_t +_Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr) +{ + PyDictKeysObject *dk; + DictKeysKind kind; + Py_ssize_t ix; + PyObject *value; + + ensure_shared_on_read(mp); + + dk = _Py_atomic_load_ptr(&mp->ma_keys); + kind = dk->dk_kind; + + if (kind != DICT_KEYS_GENERAL) { + if (PyUnicode_CheckExact(key)) { + ix = unicodekeys_lookup_unicode_threadsafe(dk, key, hash); + } + else { + ix = unicodekeys_lookup_generic_threadsafe(mp, dk, key, hash); + } + if (ix == DKIX_KEY_CHANGED) { + goto read_failed; + } + + if (ix >= 0) { + if (kind == DICT_KEYS_SPLIT) { + PyDictValues *values = _Py_atomic_load_ptr(&mp->ma_values); + if (values == NULL) + goto read_failed; + + uint8_t capacity = _Py_atomic_load_uint8_relaxed(&values->capacity); + if (ix >= (Py_ssize_t)capacity) + goto read_failed; + + value = _Py_TryXGetRef(&values->values[ix]); + if (value == NULL) + goto read_failed; + + if (values != _Py_atomic_load_ptr(&mp->ma_values)) { + Py_DECREF(value); + goto read_failed; + } + } + else { + value = _Py_TryXGetRef(&DK_UNICODE_ENTRIES(dk)[ix].me_value); + if (value == NULL) { + goto read_failed; + } + + if (dk != _Py_atomic_load_ptr(&mp->ma_keys)) { + Py_DECREF(value); + goto read_failed; + } + } + } + else { + value = NULL; + } + } + else { + ix = dictkeys_generic_lookup_threadsafe(mp, dk, key, hash); + if (ix == DKIX_KEY_CHANGED) { + goto read_failed; + } + if (ix >= 0) { + value = _Py_TryXGetRef(&DK_ENTRIES(dk)[ix].me_value); + if (value == NULL) + goto read_failed; + + if (dk != _Py_atomic_load_ptr(&mp->ma_keys)) { + Py_DECREF(value); + goto read_failed; + } + } + else { + value = NULL; + } + } + + *value_addr = value; + return ix; + +read_failed: + // In addition to the normal races of the dict being modified the _Py_TryXGetRef + // can all fail if they don't yet have a shared ref count. That can happen here + // or in the *_lookup_* helper. In that case we need to take the lock to avoid + // mutation and do a normal incref which will make them shared. + Py_BEGIN_CRITICAL_SECTION(mp); + ix = _Py_dict_lookup(mp, key, hash, &value); + *value_addr = value; + if (value != NULL) { + assert(ix >= 0); + _Py_NewRefWithLock(value); + } + Py_END_CRITICAL_SECTION(); + return ix; +} + +#else // Py_GIL_DISABLED + +Py_ssize_t +_Py_dict_lookup_threadsafe(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr) +{ + Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, value_addr); + Py_XNewRef(*value_addr); + return ix; +} + +#endif + int _PyDict_HasOnlyStringKeys(PyObject *dict) { @@ -1133,10 +1644,13 @@ _PyDict_MaybeUntrack(PyObject *op) PyObject *value; Py_ssize_t i, numentries; + ASSERT_WORLD_STOPPED_OR_DICT_LOCKED(op); + if (!PyDict_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op)) return; mp = (PyDictObject *) op; + ASSERT_CONSISTENT(mp); numentries = mp->ma_keys->dk_nentries; if (_PyDict_HasSplitTable(mp)) { for (i = 0; i < numentries; i++) { @@ -1171,10 +1685,19 @@ _PyDict_MaybeUntrack(PyObject *op) _PyObject_GC_UNTRACK(op); } +static inline int +is_unusable_slot(Py_ssize_t ix) +{ +#ifdef Py_GIL_DISABLED + return ix >= 0 || ix == DKIX_DUMMY; +#else + return ix >= 0; +#endif +} + /* Internal function to find slot for an item from its hash when it is known that the key is not present in the dict. - - The dict must be combined. */ + */ static Py_ssize_t find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash) { @@ -1183,7 +1706,7 @@ find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash) const size_t mask = DK_MASK(keys); size_t i = hash & mask; Py_ssize_t ix = dictkeys_get_index(keys, i); - for (size_t perturb = hash; ix >= 0;) { + for (size_t perturb = hash; is_unusable_slot(ix);) { perturb >>= PERTURB_SHIFT; i = (i*5 + perturb + 1) & mask; ix = dictkeys_get_index(keys, i); @@ -1197,38 +1720,108 @@ insertion_resize(PyInterpreterState *interp, PyDictObject *mp, int unicode) return dictresize(interp, mp, calculate_log2_keysize(GROWTH_RATE(mp)), unicode); } -static Py_ssize_t -insert_into_dictkeys(PyDictKeysObject *keys, PyObject *name) +static inline int +insert_combined_dict(PyInterpreterState *interp, PyDictObject *mp, + Py_hash_t hash, PyObject *key, PyObject *value) { - assert(PyUnicode_CheckExact(name)); - Py_hash_t hash = unicode_get_hash(name); - if (hash == -1) { - hash = PyUnicode_Type.tp_hash(name); - if (hash == -1) { - PyErr_Clear(); - return DKIX_EMPTY; - } + // gh-140551: If dict was cleared in _Py_dict_lookup, + // we have to resize one more time to force general key kind. + if (DK_IS_UNICODE(mp->ma_keys) && !PyUnicode_CheckExact(key)) { + if (insertion_resize(interp, mp, 0) < 0) + return -1; + assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL); } - Py_ssize_t ix = unicodekeys_lookup_unicode(keys, name, hash); - if (ix == DKIX_EMPTY) { - if (keys->dk_usable <= 0) { - return DKIX_EMPTY; + + if (mp->ma_keys->dk_usable <= 0) { + /* Need to resize. */ + if (insertion_resize(interp, mp, 1) < 0) { + return -1; } - /* Insert into new slot. */ + } + + uint64_t new_version = _PyDict_NotifyEvent( + interp, PyDict_EVENT_ADDED, mp, key, value); + mp->ma_keys->dk_version = 0; + + Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash); + dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries); + + if (DK_IS_UNICODE(mp->ma_keys)) { + PyDictUnicodeEntry *ep; + ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries]; + STORE_KEY(ep, key); + STORE_VALUE(ep, value); + } + else { + PyDictKeyEntry *ep; + ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries]; + STORE_KEY(ep, key); + STORE_VALUE(ep, value); + STORE_HASH(ep, hash); + } + mp->ma_version_tag = new_version; + STORE_KEYS_USABLE(mp->ma_keys, mp->ma_keys->dk_usable - 1); + STORE_KEYS_NENTRIES(mp->ma_keys, mp->ma_keys->dk_nentries + 1); + assert(mp->ma_keys->dk_usable >= 0); + return 0; +} + +static Py_ssize_t +insert_split_key(PyDictKeysObject *keys, PyObject *key, Py_hash_t hash) +{ + assert(PyUnicode_CheckExact(key)); + Py_ssize_t ix; + + +#ifdef Py_GIL_DISABLED + ix = unicodekeys_lookup_unicode_threadsafe(keys, key, hash); + if (ix >= 0) { + return ix; + } +#endif + + LOCK_KEYS(keys); + ix = unicodekeys_lookup_unicode(keys, key, hash); + if (ix == DKIX_EMPTY && keys->dk_usable > 0) { + // Insert into new slot keys->dk_version = 0; Py_ssize_t hashpos = find_empty_slot(keys, hash); ix = keys->dk_nentries; - PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(keys)[ix]; dictkeys_set_index(keys, hashpos, ix); - assert(ep->me_key == NULL); - ep->me_key = Py_NewRef(name); - keys->dk_usable--; - keys->dk_nentries++; + PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(keys)[ix]; + STORE_SHARED_KEY(ep->me_key, Py_NewRef(key)); + split_keys_entry_added(keys); } assert (ix < SHARED_KEYS_MAX_SIZE); + UNLOCK_KEYS(keys); return ix; } +static void +insert_split_value(PyInterpreterState *interp, PyDictObject *mp, PyObject *key, PyObject *value, Py_ssize_t ix) +{ + assert(PyUnicode_CheckExact(key)); + ASSERT_DICT_LOCKED(mp); + MAINTAIN_TRACKING(mp, key, value); + PyObject *old_value = mp->ma_values->values[ix]; + if (old_value == NULL) { + uint64_t new_version = _PyDict_NotifyEvent(interp, PyDict_EVENT_ADDED, mp, key, value); + STORE_SPLIT_VALUE(mp, ix, Py_NewRef(value)); + _PyDictValues_AddToInsertionOrder(mp->ma_values, ix); + STORE_USED(mp, mp->ma_used + 1); + mp->ma_version_tag = new_version; + } + else { + uint64_t new_version = _PyDict_NotifyEvent(interp, PyDict_EVENT_MODIFIED, mp, key, value); + STORE_SPLIT_VALUE(mp, ix, Py_NewRef(value)); + mp->ma_version_tag = new_version; + // old_value should be DECREFed after GC track checking is done, if not, it could raise a segmentation fault, + // when dict only holds the strong reference to value in ep->me_value. + Py_DECREF(old_value); + } + ASSERT_CONSISTENT(mp); +} + /* Internal routine to insert a new item into the table. Used both by the internal resize routine and by the public insert routine. @@ -1239,62 +1832,42 @@ static int insertdict(PyInterpreterState *interp, PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value) { - PyObject *old_value; - - if (DK_IS_UNICODE(mp->ma_keys) && !PyUnicode_CheckExact(key)) { - if (insertion_resize(interp, mp, 0) < 0) - goto Fail; - assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL); - } + PyObject *old_value = NULL; + Py_ssize_t ix; - Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &old_value); - if (ix == DKIX_ERROR) - goto Fail; + ASSERT_DICT_LOCKED(mp); MAINTAIN_TRACKING(mp, key, value); - if (ix == DKIX_EMPTY) { - assert(old_value == NULL); - if (mp->ma_keys->dk_usable <= 0) { - /* Need to resize. */ - if (insertion_resize(interp, mp, 1) < 0) - goto Fail; + if (_PyDict_HasSplitTable(mp) && PyUnicode_CheckExact(key)) { + ix = insert_split_key(mp->ma_keys, key, hash); + if (ix != DKIX_EMPTY) { + insert_split_value(interp, mp, key, value, ix); + Py_DECREF(key); + Py_DECREF(value); + return 0; } + // No space in shared keys. Go to insert_combined_dict() below. + } + else { + ix = _Py_dict_lookup(mp, key, hash, &old_value); + if (ix == DKIX_ERROR) + goto Fail; - uint64_t new_version = _PyDict_NotifyEvent( - interp, PyDict_EVENT_ADDED, mp, key, value); - /* Insert into new slot. */ - mp->ma_keys->dk_version = 0; - - Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash); - dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries); + } - if (DK_IS_UNICODE(mp->ma_keys)) { - PyDictUnicodeEntry *ep; - ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries]; - ep->me_key = key; - if (mp->ma_values) { - Py_ssize_t index = mp->ma_keys->dk_nentries; - _PyDictValues_AddToInsertionOrder(mp->ma_values, index); - assert (mp->ma_values->values[index] == NULL); - mp->ma_values->values[index] = value; - } - else { - ep->me_value = value; - } - } - else { - PyDictKeyEntry *ep; - ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries]; - ep->me_key = key; - ep->me_hash = hash; - ep->me_value = value; + if (old_value == NULL) { + // insert_combined_dict() will convert from non DICT_KEYS_GENERAL table + // into DICT_KEYS_GENERAL table if key is not Unicode. + // We don't convert it before _Py_dict_lookup because non-Unicode key + // may change generic table into Unicode table. + // + // NOTE: ix may not be DKIX_EMPTY because split table may have key + // without value. + if (insert_combined_dict(interp, mp, hash, key, value) < 0) { + goto Fail; } - mp->ma_used++; - mp->ma_version_tag = new_version; - mp->ma_keys->dk_usable--; - mp->ma_keys->dk_nentries++; - assert(mp->ma_keys->dk_usable >= 0); + STORE_USED(mp, mp->ma_used + 1); ASSERT_CONSISTENT(mp); return 0; } @@ -1302,22 +1875,20 @@ insertdict(PyInterpreterState *interp, PyDictObject *mp, if (old_value != value) { uint64_t new_version = _PyDict_NotifyEvent( interp, PyDict_EVENT_MODIFIED, mp, key, value); - if (_PyDict_HasSplitTable(mp)) { - mp->ma_values->values[ix] = value; - if (old_value == NULL) { - _PyDictValues_AddToInsertionOrder(mp->ma_values, ix); - mp->ma_used++; - } - } - else { - assert(old_value != NULL); - if (DK_IS_UNICODE(mp->ma_keys)) { - DK_UNICODE_ENTRIES(mp->ma_keys)[ix].me_value = value; + assert(old_value != NULL); + if (DK_IS_UNICODE(mp->ma_keys)) { + if (_PyDict_HasSplitTable(mp)) { + STORE_SPLIT_VALUE(mp, ix, value); } else { - DK_ENTRIES(mp->ma_keys)[ix].me_value = value; + PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[ix]; + STORE_VALUE(ep, value); } } + else { + PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix]; + STORE_VALUE(ep, value); + } mp->ma_version_tag = new_version; } Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */ @@ -1331,13 +1902,14 @@ Fail: return -1; } -// Same to insertdict but specialized for ma_keys = Py_EMPTY_KEYS. +// Same as insertdict but specialized for ma_keys == Py_EMPTY_KEYS. // Consumes key and value references. static int insert_to_emptydict(PyInterpreterState *interp, PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value) { assert(mp->ma_keys == Py_EMPTY_KEYS); + ASSERT_DICT_LOCKED(mp); int unicode = PyUnicode_CheckExact(key); PyDictKeysObject *newkeys = new_keys_object( @@ -1351,28 +1923,33 @@ insert_to_emptydict(PyInterpreterState *interp, PyDictObject *mp, interp, PyDict_EVENT_ADDED, mp, key, value); /* We don't decref Py_EMPTY_KEYS here because it is immortal. */ - mp->ma_keys = newkeys; - mp->ma_values = NULL; + assert(mp->ma_values == NULL); MAINTAIN_TRACKING(mp, key, value); size_t hashpos = (size_t)hash & (PyDict_MINSIZE-1); - dictkeys_set_index(mp->ma_keys, hashpos, 0); + dictkeys_set_index(newkeys, hashpos, 0); if (unicode) { - PyDictUnicodeEntry *ep = DK_UNICODE_ENTRIES(mp->ma_keys); + PyDictUnicodeEntry *ep = DK_UNICODE_ENTRIES(newkeys); ep->me_key = key; - ep->me_value = value; + STORE_VALUE(ep, value); } else { - PyDictKeyEntry *ep = DK_ENTRIES(mp->ma_keys); + PyDictKeyEntry *ep = DK_ENTRIES(newkeys); ep->me_key = key; ep->me_hash = hash; - ep->me_value = value; + STORE_VALUE(ep, value); } - mp->ma_used++; + STORE_USED(mp, mp->ma_used + 1); mp->ma_version_tag = new_version; - mp->ma_keys->dk_usable--; - mp->ma_keys->dk_nentries++; + newkeys->dk_usable--; + newkeys->dk_nentries++; + // We store the keys last so no one can see them in a partially inconsistent + // state so that we don't need to switch the keys to being shared yet for + // the case where we're inserting from the non-owner thread. We don't use + // set_keys here because the transition from empty to non-empty is safe + // as the empty keys will never be freed. + FT_ATOMIC_STORE_PTR_RELEASE(mp->ma_keys, newkeys); return 0; } @@ -1417,7 +1994,7 @@ actually be smaller than the old one. If a table is split (its keys and hashes are shared, its values are not), then the values are temporarily copied into the table, it is resized as a combined table, then the me_value slots in the old table are NULLed out. -After resizing a table is always combined. +After resizing, a table is always combined. This function supports: - Unicode split -> Unicode combined or Generic @@ -1428,9 +2005,11 @@ static int dictresize(PyInterpreterState *interp, PyDictObject *mp, uint8_t log2_newsize, int unicode) { - PyDictKeysObject *oldkeys; + PyDictKeysObject *oldkeys, *newkeys; PyDictValues *oldvalues; + ASSERT_DICT_LOCKED(mp); + if (log2_newsize >= SIZEOF_SIZE_T*8) { PyErr_NoMemory(); return -1; @@ -1444,30 +2023,31 @@ dictresize(PyInterpreterState *interp, PyDictObject *mp, unicode = 0; } + ensure_shared_on_resize(mp); /* NOTE: Current odict checks mp->ma_keys to detect resize happen. * So we can't reuse oldkeys even if oldkeys->dk_size == newsize. * TODO: Try reusing oldkeys when reimplement odict. */ /* Allocate a new table. */ - mp->ma_keys = new_keys_object(interp, log2_newsize, unicode); - if (mp->ma_keys == NULL) { - mp->ma_keys = oldkeys; + newkeys = new_keys_object(interp, log2_newsize, unicode); + if (newkeys == NULL) { return -1; } // New table must be large enough. - assert(mp->ma_keys->dk_usable >= mp->ma_used); + assert(newkeys->dk_usable >= mp->ma_used); Py_ssize_t numentries = mp->ma_used; if (oldvalues != NULL) { - PyDictUnicodeEntry *oldentries = DK_UNICODE_ENTRIES(oldkeys); + LOCK_KEYS(oldkeys); + PyDictUnicodeEntry *oldentries = DK_UNICODE_ENTRIES(oldkeys); /* Convert split table into new combined table. * We must incref keys; we can transfer values. */ - if (mp->ma_keys->dk_kind == DICT_KEYS_GENERAL) { + if (newkeys->dk_kind == DICT_KEYS_GENERAL) { // split -> generic - PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys); + PyDictKeyEntry *newentries = DK_ENTRIES(newkeys); for (Py_ssize_t i = 0; i < numentries; i++) { int index = get_index_from_order(mp, i); @@ -1477,10 +2057,10 @@ dictresize(PyInterpreterState *interp, PyDictObject *mp, newentries[i].me_hash = unicode_get_hash(ep->me_key); newentries[i].me_value = oldvalues->values[index]; } - build_indices_generic(mp->ma_keys, newentries, numentries); + build_indices_generic(newkeys, newentries, numentries); } else { // split -> combined unicode - PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(mp->ma_keys); + PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(newkeys); for (Py_ssize_t i = 0; i < numentries; i++) { int index = get_index_from_order(mp, i); @@ -1489,18 +2069,27 @@ dictresize(PyInterpreterState *interp, PyDictObject *mp, newentries[i].me_key = Py_NewRef(ep->me_key); newentries[i].me_value = oldvalues->values[index]; } - build_indices_unicode(mp->ma_keys, newentries, numentries); + build_indices_unicode(newkeys, newentries, numentries); + } + UNLOCK_KEYS(oldkeys); + set_keys(mp, newkeys); + dictkeys_decref(interp, oldkeys, IS_DICT_SHARED(mp)); + set_values(mp, NULL); + if (oldvalues->embedded) { + assert(oldvalues->embedded == 1); + assert(oldvalues->valid == 1); + FT_ATOMIC_STORE_UINT8(oldvalues->valid, 0); + } + else { + free_values(oldvalues, IS_DICT_SHARED(mp)); } - dictkeys_decref(interp, oldkeys); - mp->ma_values = NULL; - free_values(oldvalues); } else { // oldkeys is combined. if (oldkeys->dk_kind == DICT_KEYS_GENERAL) { // generic -> generic - assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL); + assert(newkeys->dk_kind == DICT_KEYS_GENERAL); PyDictKeyEntry *oldentries = DK_ENTRIES(oldkeys); - PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys); + PyDictKeyEntry *newentries = DK_ENTRIES(newkeys); if (oldkeys->dk_nentries == numentries) { memcpy(newentries, oldentries, numentries * sizeof(PyDictKeyEntry)); } @@ -1512,12 +2101,12 @@ dictresize(PyInterpreterState *interp, PyDictObject *mp, newentries[i] = *ep++; } } - build_indices_generic(mp->ma_keys, newentries, numentries); + build_indices_generic(newkeys, newentries, numentries); } else { // oldkeys is combined unicode PyDictUnicodeEntry *oldentries = DK_UNICODE_ENTRIES(oldkeys); if (unicode) { // combined unicode -> combined unicode - PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(mp->ma_keys); + PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(newkeys); if (oldkeys->dk_nentries == numentries && mp->ma_keys->dk_kind == DICT_KEYS_UNICODE) { memcpy(newentries, oldentries, numentries * sizeof(PyDictUnicodeEntry)); } @@ -1529,10 +2118,10 @@ dictresize(PyInterpreterState *interp, PyDictObject *mp, newentries[i] = *ep++; } } - build_indices_unicode(mp->ma_keys, newentries, numentries); + build_indices_unicode(newkeys, newentries, numentries); } else { // combined unicode -> generic - PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys); + PyDictKeyEntry *newentries = DK_ENTRIES(newkeys); PyDictUnicodeEntry *ep = oldentries; for (Py_ssize_t i = 0; i < numentries; i++) { while (ep->me_value == NULL) @@ -1542,41 +2131,24 @@ dictresize(PyInterpreterState *interp, PyDictObject *mp, newentries[i].me_value = ep->me_value; ep++; } - build_indices_generic(mp->ma_keys, newentries, numentries); + build_indices_generic(newkeys, newentries, numentries); } } - // We can not use free_keys_object here because key's reference - // are moved already. + set_keys(mp, newkeys); + if (oldkeys != Py_EMPTY_KEYS) { #ifdef Py_REF_DEBUG - _Py_DecRefTotal(_PyInterpreterState_GET()); + _Py_DecRefTotal(_PyThreadState_GET()); #endif assert(oldkeys->dk_kind != DICT_KEYS_SPLIT); assert(oldkeys->dk_refcnt == 1); -#if PyDict_MAXFREELIST > 0 - struct _Py_dict_state *state = get_dict_state(interp); -#ifdef Py_DEBUG - // dictresize() must not be called after _PyDict_Fini() - assert(state->keys_numfree != -1); -#endif - if (DK_LOG_SIZE(oldkeys) == PyDict_LOG_MINSIZE && - DK_IS_UNICODE(oldkeys) && - state->keys_numfree < PyDict_MAXFREELIST) - { - state->keys_free_list[state->keys_numfree++] = oldkeys; - OBJECT_STAT_INC(to_freelist); - } - else -#endif - { - PyObject_Free(oldkeys); - } + free_keys_object(oldkeys, IS_DICT_SHARED(mp)); } } - mp->ma_keys->dk_usable -= numentries; - mp->ma_keys->dk_nentries = numentries; + STORE_KEYS_USABLE(mp->ma_keys, mp->ma_keys->dk_usable - numentries); + STORE_KEYS_NENTRIES(mp->ma_keys, numentries); ASSERT_CONSISTENT(mp); return 0; } @@ -1644,7 +2216,7 @@ _PyDict_FromItems(PyObject *const *keys, Py_ssize_t keys_offset, for (Py_ssize_t i = 0; i < length; i++) { PyObject *key = *ks; PyObject *value = *vs; - if (PyDict_SetItem(dict, key, value) < 0) { + if (setitem_lock_held((PyDictObject *)dict, key, value) < 0) { Py_DECREF(dict); return NULL; } @@ -1665,21 +2237,18 @@ _PyDict_FromItems(PyObject *const *keys, Py_ssize_t keys_offset, * function hits a stack-depth error, which can cause this to return NULL * even if the key is present. */ -PyObject * -PyDict_GetItem(PyObject *op, PyObject *key) +static PyObject * +dict_getitem(PyObject *op, PyObject *key, const char *warnmsg) { if (!PyDict_Check(op)) { return NULL; } PyDictObject *mp = (PyDictObject *)op; - Py_hash_t hash; - if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) { - PyErr_Clear(); - return NULL; - } + Py_hash_t hash = _PyObject_HashFast(key); + if (hash == -1) { + PyErr_FormatUnraisable(warnmsg); + return NULL; } PyThreadState *tstate = _PyThreadState_GET(); @@ -1693,31 +2262,44 @@ PyDict_GetItem(PyObject *op, PyObject *key) PyObject *value; Py_ssize_t ix; (void)ix; - PyObject *exc = _PyErr_GetRaisedException(tstate); +#ifdef Py_GIL_DISABLED + ix = _Py_dict_lookup_threadsafe(mp, key, hash, &value); + Py_XDECREF(value); +#else ix = _Py_dict_lookup(mp, key, hash, &value); +#endif /* Ignore any exception raised by the lookup */ + PyObject *exc2 = _PyErr_Occurred(tstate); + if (exc2 && !PyErr_GivenExceptionMatches(exc2, PyExc_KeyError)) { + PyErr_FormatUnraisable(warnmsg); + } _PyErr_SetRaisedException(tstate, exc); - assert(ix >= 0 || value == NULL); - return value; + return value; // borrowed reference +} + +PyObject * +PyDict_GetItem(PyObject *op, PyObject *key) +{ + return dict_getitem(op, key, + "Exception ignored in PyDict_GetItem(); consider using " + "PyDict_GetItemRef() or PyDict_GetItemWithError()"); } Py_ssize_t _PyDict_LookupIndex(PyDictObject *mp, PyObject *key) { + // TODO: Thread safety PyObject *value; assert(PyDict_CheckExact((PyObject*)mp)); assert(PyUnicode_CheckExact(key)); - Py_hash_t hash = unicode_get_hash(key); + Py_hash_t hash = _PyObject_HashFast(key); if (hash == -1) { - hash = PyObject_Hash(key); - if (hash == -1) { - return -1; - } + return -1; } return _Py_dict_lookup(mp, key, hash, &value); @@ -1739,9 +2321,112 @@ _PyDict_GetItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash) return NULL; } +#ifdef Py_GIL_DISABLED + ix = _Py_dict_lookup_threadsafe(mp, key, hash, &value); + Py_XDECREF(value); +#else ix = _Py_dict_lookup(mp, key, hash, &value); +#endif assert(ix >= 0 || value == NULL); - return value; + return value; // borrowed reference +} + +/* Gets an item and provides a new reference if the value is present. + * Returns 1 if the key is present, 0 if the key is missing, and -1 if an + * exception occurred. +*/ +int +_PyDict_GetItemRef_KnownHash_LockHeld(PyDictObject *op, PyObject *key, + Py_hash_t hash, PyObject **result) +{ + PyObject *value; + Py_ssize_t ix = _Py_dict_lookup(op, key, hash, &value); + assert(ix >= 0 || value == NULL); + if (ix == DKIX_ERROR) { + *result = NULL; + return -1; + } + if (value == NULL) { + *result = NULL; + return 0; // missing key + } + *result = Py_NewRef(value); + return 1; // key is present +} + +/* Gets an item and provides a new reference if the value is present. + * Returns 1 if the key is present, 0 if the key is missing, and -1 if an + * exception occurred. +*/ +int +_PyDict_GetItemRef_KnownHash(PyDictObject *op, PyObject *key, Py_hash_t hash, PyObject **result) +{ + PyObject *value; +#ifdef Py_GIL_DISABLED + Py_ssize_t ix = _Py_dict_lookup_threadsafe(op, key, hash, &value); +#else + Py_ssize_t ix = _Py_dict_lookup(op, key, hash, &value); +#endif + assert(ix >= 0 || value == NULL); + if (ix == DKIX_ERROR) { + *result = NULL; + return -1; + } + if (value == NULL) { + *result = NULL; + return 0; // missing key + } +#ifdef Py_GIL_DISABLED + *result = value; +#else + *result = Py_NewRef(value); +#endif + return 1; // key is present +} + +int +PyDict_GetItemRef(PyObject *op, PyObject *key, PyObject **result) +{ + if (!PyDict_Check(op)) { + PyErr_BadInternalCall(); + *result = NULL; + return -1; + } + + Py_hash_t hash = _PyObject_HashFast(key); + if (hash == -1) { + *result = NULL; + return -1; + } + + return _PyDict_GetItemRef_KnownHash((PyDictObject *)op, key, hash, result); +} + +int +_PyDict_GetItemRef_Unicode_LockHeld(PyDictObject *op, PyObject *key, PyObject **result) +{ + ASSERT_DICT_LOCKED(op); + assert(PyUnicode_CheckExact(key)); + + Py_hash_t hash = _PyObject_HashFast(key); + if (hash == -1) { + *result = NULL; + return -1; + } + + PyObject *value; + Py_ssize_t ix = _Py_dict_lookup(op, key, hash, &value); + assert(ix >= 0 || value == NULL); + if (ix == DKIX_ERROR) { + *result = NULL; + return -1; + } + if (value == NULL) { + *result = NULL; + return 0; // missing key + } + *result = Py_NewRef(value); + return 1; // key is present } /* Variant of PyDict_GetItem() that doesn't suppress exceptions. @@ -1760,17 +2445,19 @@ PyDict_GetItemWithError(PyObject *op, PyObject *key) PyErr_BadInternalCall(); return NULL; } - if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) - { - hash = PyObject_Hash(key); - if (hash == -1) { - return NULL; - } + hash = _PyObject_HashFast(key); + if (hash == -1) { + return NULL; } +#ifdef Py_GIL_DISABLED + ix = _Py_dict_lookup_threadsafe(mp, key, hash, &value); + Py_XDECREF(value); +#else ix = _Py_dict_lookup(mp, key, hash, &value); +#endif assert(ix >= 0 || value == NULL); - return value; + return value; // borrowed reference } PyObject * @@ -1781,7 +2468,7 @@ _PyDict_GetItemWithError(PyObject *dp, PyObject *kv) if (hash == -1) { return NULL; } - return _PyDict_GetItem_KnownHash(dp, kv, hash); + return _PyDict_GetItem_KnownHash(dp, kv, hash); // borrowed reference } PyObject * @@ -1793,7 +2480,7 @@ _PyDict_GetItemIdWithError(PyObject *dp, _Py_Identifier *key) return NULL; Py_hash_t hash = unicode_get_hash(kv); assert (hash != -1); /* interned strings have their hash value initialised */ - return _PyDict_GetItem_KnownHash(dp, kv, hash); + return _PyDict_GetItem_KnownHash(dp, kv, hash); // borrowed reference } PyObject * @@ -1818,6 +2505,8 @@ _PyDict_GetItemStringWithError(PyObject *v, const char *key) * Raise an exception and return NULL if an error occurred (ex: computing the * key hash failed, key comparison failed, ...). Return NULL if the key doesn't * exist. Return the value if the key exists. + * + * Returns a new reference. */ PyObject * _PyDict_LoadGlobal(PyDictObject *globals, PyDictObject *builtins, PyObject *key) @@ -1826,42 +2515,42 @@ _PyDict_LoadGlobal(PyDictObject *globals, PyDictObject *builtins, PyObject *key) Py_hash_t hash; PyObject *value; - if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) - return NULL; + hash = _PyObject_HashFast(key); + if (hash == -1) { + return NULL; } /* namespace 1: globals */ - ix = _Py_dict_lookup(globals, key, hash, &value); + ix = _Py_dict_lookup_threadsafe(globals, key, hash, &value); if (ix == DKIX_ERROR) return NULL; if (ix != DKIX_EMPTY && value != NULL) return value; /* namespace 2: builtins */ - ix = _Py_dict_lookup(builtins, key, hash, &value); + ix = _Py_dict_lookup_threadsafe(builtins, key, hash, &value); assert(ix >= 0 || value == NULL); return value; } /* Consumes references to key and value */ -int -_PyDict_SetItem_Take2(PyDictObject *mp, PyObject *key, PyObject *value) +static int +setitem_take2_lock_held(PyDictObject *mp, PyObject *key, PyObject *value) { + ASSERT_DICT_LOCKED(mp); + assert(key); assert(value); assert(PyDict_Check(mp)); - Py_hash_t hash; - if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) { - Py_DECREF(key); - Py_DECREF(value); - return -1; - } + Py_hash_t hash = _PyObject_HashFast(key); + if (hash == -1) { + Py_DECREF(key); + Py_DECREF(value); + return -1; } + PyInterpreterState *interp = _PyInterpreterState_GET(); + if (mp->ma_keys == Py_EMPTY_KEYS) { return insert_to_emptydict(interp, mp, key, hash, value); } @@ -1869,6 +2558,16 @@ _PyDict_SetItem_Take2(PyDictObject *mp, PyObject *key, PyObject *value) return insertdict(interp, mp, key, hash, value); } +int +_PyDict_SetItem_Take2(PyDictObject *mp, PyObject *key, PyObject *value) +{ + int res; + Py_BEGIN_CRITICAL_SECTION(mp); + res = setitem_take2_lock_held(mp, key, value); + Py_END_CRITICAL_SECTION(); + return res; +} + /* CAUTION: PyDict_SetItem() must guarantee that it won't resize the * dictionary if it's merely replacing the value for an existing key. * This means that it's safe to loop over a dictionary with PyDict_Next() @@ -1888,12 +2587,32 @@ PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value) Py_NewRef(key), Py_NewRef(value)); } +static int +setitem_lock_held(PyDictObject *mp, PyObject *key, PyObject *value) +{ + assert(key); + assert(value); + return setitem_take2_lock_held(mp, + Py_NewRef(key), Py_NewRef(value)); +} + + int -_PyDict_SetItem_KnownHash(PyObject *op, PyObject *key, PyObject *value, - Py_hash_t hash) +_PyDict_SetItem_KnownHash_LockHeld(PyDictObject *mp, PyObject *key, PyObject *value, + Py_hash_t hash) { - PyDictObject *mp; + PyInterpreterState *interp = _PyInterpreterState_GET(); + if (mp->ma_keys == Py_EMPTY_KEYS) { + return insert_to_emptydict(interp, mp, Py_NewRef(key), hash, Py_NewRef(value)); + } + /* insertdict() handles any resizing that might be necessary */ + return insertdict(interp, mp, Py_NewRef(key), hash, Py_NewRef(value)); +} +int +_PyDict_SetItem_KnownHash(PyObject *op, PyObject *key, PyObject *value, + Py_hash_t hash) +{ if (!PyDict_Check(op)) { PyErr_BadInternalCall(); return -1; @@ -1901,46 +2620,48 @@ _PyDict_SetItem_KnownHash(PyObject *op, PyObject *key, PyObject *value, assert(key); assert(value); assert(hash != -1); - mp = (PyDictObject *)op; - PyInterpreterState *interp = _PyInterpreterState_GET(); - if (mp->ma_keys == Py_EMPTY_KEYS) { - return insert_to_emptydict(interp, mp, Py_NewRef(key), hash, Py_NewRef(value)); - } - /* insertdict() handles any resizing that might be necessary */ - return insertdict(interp, mp, Py_NewRef(key), hash, Py_NewRef(value)); + int res; + Py_BEGIN_CRITICAL_SECTION(op); + res = _PyDict_SetItem_KnownHash_LockHeld((PyDictObject *)op, key, value, hash); + Py_END_CRITICAL_SECTION(); + return res; } static void delete_index_from_values(PyDictValues *values, Py_ssize_t ix) { - uint8_t *size_ptr = ((uint8_t *)values)-2; - int size = *size_ptr; + uint8_t *array = get_insertion_order_array(values); + int size = values->size; + assert(size <= values->capacity); int i; - for (i = 1; size_ptr[-i] != ix; i++) { - assert(i <= size); + for (i = 0; array[i] != ix; i++) { + assert(i < size); } - assert(i <= size); + assert(i < size); + size--; for (; i < size; i++) { - size_ptr[-i] = size_ptr[-i-1]; + array[i] = array[i+1]; } - *size_ptr = size -1; + values->size = size; } -static int +static void delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix, PyObject *old_value, uint64_t new_version) { PyObject *old_key; + ASSERT_DICT_LOCKED(mp); + Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix); assert(hashpos >= 0); - mp->ma_used--; + STORE_USED(mp, mp->ma_used - 1); mp->ma_version_tag = new_version; - if (mp->ma_values) { + if (_PyDict_HasSplitTable(mp)) { assert(old_value == mp->ma_values->values[ix]); - mp->ma_values->values[ix] = NULL; + STORE_SPLIT_VALUE(mp, ix, NULL); assert(ix < SHARED_KEYS_MAX_SIZE); /* Update order */ delete_index_from_values(mp->ma_values, ix); @@ -1952,40 +2673,37 @@ delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix, if (DK_IS_UNICODE(mp->ma_keys)) { PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[ix]; old_key = ep->me_key; - ep->me_key = NULL; - ep->me_value = NULL; + STORE_KEY(ep, NULL); + STORE_VALUE(ep, NULL); } else { PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix]; old_key = ep->me_key; - ep->me_key = NULL; - ep->me_value = NULL; - ep->me_hash = 0; + STORE_KEY(ep, NULL); + STORE_VALUE(ep, NULL); + STORE_HASH(ep, 0); } Py_DECREF(old_key); } Py_DECREF(old_value); ASSERT_CONSISTENT(mp); - return 0; } int PyDict_DelItem(PyObject *op, PyObject *key) { - Py_hash_t hash; assert(key); - if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) - return -1; + Py_hash_t hash = _PyObject_HashFast(key); + if (hash == -1) { + return -1; } return _PyDict_DelItem_KnownHash(op, key, hash); } -int -_PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash) +static int +delitem_knownhash_lock_held(PyObject *op, PyObject *key, Py_hash_t hash) { Py_ssize_t ix; PyDictObject *mp; @@ -1995,6 +2713,9 @@ _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash) PyErr_BadInternalCall(); return -1; } + + ASSERT_DICT_LOCKED(op); + assert(key); assert(hash != -1); mp = (PyDictObject *)op; @@ -2009,66 +2730,103 @@ _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash) PyInterpreterState *interp = _PyInterpreterState_GET(); uint64_t new_version = _PyDict_NotifyEvent( interp, PyDict_EVENT_DELETED, mp, key, NULL); - return delitem_common(mp, hash, ix, old_value, new_version); + delitem_common(mp, hash, ix, old_value, new_version); + return 0; } -/* This function promises that the predicate -> deletion sequence is atomic - * (i.e. protected by the GIL), assuming the predicate itself doesn't - * release the GIL. - */ int -_PyDict_DelItemIf(PyObject *op, PyObject *key, - int (*predicate)(PyObject *value)) +_PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash) { - Py_ssize_t hashpos, ix; + int res; + Py_BEGIN_CRITICAL_SECTION(op); + res = delitem_knownhash_lock_held(op, key, hash); + Py_END_CRITICAL_SECTION(); + return res; +} + +static int +delitemif_lock_held(PyObject *op, PyObject *key, + int (*predicate)(PyObject *value, void *arg), + void *arg) +{ + Py_ssize_t ix; PyDictObject *mp; Py_hash_t hash; PyObject *old_value; int res; - if (!PyDict_Check(op)) { - PyErr_BadInternalCall(); - return -1; - } + ASSERT_DICT_LOCKED(op); + assert(key); hash = PyObject_Hash(key); if (hash == -1) return -1; mp = (PyDictObject *)op; ix = _Py_dict_lookup(mp, key, hash, &old_value); - if (ix == DKIX_ERROR) + if (ix == DKIX_ERROR) { return -1; + } if (ix == DKIX_EMPTY || old_value == NULL) { - _PyErr_SetKeyError(key); - return -1; + return 0; } - res = predicate(old_value); + res = predicate(old_value, arg); if (res == -1) return -1; - hashpos = lookdict_index(mp->ma_keys, hash, ix); - assert(hashpos >= 0); - if (res > 0) { PyInterpreterState *interp = _PyInterpreterState_GET(); uint64_t new_version = _PyDict_NotifyEvent( interp, PyDict_EVENT_DELETED, mp, key, NULL); - return delitem_common(mp, hashpos, ix, old_value, new_version); + delitem_common(mp, hash, ix, old_value, new_version); + return 1; } else { return 0; } } +/* This function promises that the predicate -> deletion sequence is atomic + * (i.e. protected by the GIL or the per-dict mutex in free threaded builds), + * assuming the predicate itself doesn't release the GIL (or cause re-entrancy + * which would release the per-dict mutex) + */ +int +_PyDict_DelItemIf(PyObject *op, PyObject *key, + int (*predicate)(PyObject *value, void *arg), + void *arg) +{ + assert(PyDict_Check(op)); + int res; + Py_BEGIN_CRITICAL_SECTION(op); + res = delitemif_lock_held(op, key, predicate, arg); + Py_END_CRITICAL_SECTION(); + return res; +} +static void +clear_embedded_values(PyDictValues *values, Py_ssize_t nentries) +{ + PyObject *refs[SHARED_KEYS_MAX_SIZE]; + assert(nentries <= SHARED_KEYS_MAX_SIZE); + for (Py_ssize_t i = 0; i < nentries; i++) { + refs[i] = values->values[i]; + values->values[i] = NULL; + } + values->size = 0; + for (Py_ssize_t i = 0; i < nentries; i++) { + Py_XDECREF(refs[i]); + } +} -void -PyDict_Clear(PyObject *op) +static void +clear_lock_held(PyObject *op) { PyDictObject *mp; PyDictKeysObject *oldkeys; PyDictValues *oldvalues; Py_ssize_t i, n; + ASSERT_DICT_LOCKED(op); + if (!PyDict_Check(op)) return; mp = ((PyDictObject *)op); @@ -2081,26 +2839,39 @@ PyDict_Clear(PyObject *op) PyInterpreterState *interp = _PyInterpreterState_GET(); uint64_t new_version = _PyDict_NotifyEvent( interp, PyDict_EVENT_CLEARED, mp, NULL, NULL); - dictkeys_incref(Py_EMPTY_KEYS); - mp->ma_keys = Py_EMPTY_KEYS; - mp->ma_values = NULL; - mp->ma_used = 0; + // We don't inc ref empty keys because they're immortal + ensure_shared_on_resize(mp); mp->ma_version_tag = new_version; - /* ...then clear the keys and values */ - if (oldvalues != NULL) { - n = oldkeys->dk_nentries; - for (i = 0; i < n; i++) - Py_CLEAR(oldvalues->values[i]); - free_values(oldvalues); - dictkeys_decref(interp, oldkeys); + STORE_USED(mp, 0); + if (oldvalues == NULL) { + set_keys(mp, Py_EMPTY_KEYS); + assert(oldkeys->dk_refcnt == 1); + dictkeys_decref(interp, oldkeys, IS_DICT_SHARED(mp)); + } + else if (oldvalues->embedded) { + clear_embedded_values(oldvalues, oldkeys->dk_nentries); } else { - assert(oldkeys->dk_refcnt == 1); - dictkeys_decref(interp, oldkeys); + set_values(mp, NULL); + set_keys(mp, Py_EMPTY_KEYS); + n = oldkeys->dk_nentries; + for (i = 0; i < n; i++) { + Py_CLEAR(oldvalues->values[i]); + } + free_values(oldvalues, IS_DICT_SHARED(mp)); + dictkeys_decref(interp, oldkeys, false); } ASSERT_CONSISTENT(mp); } +void +PyDict_Clear(PyObject *op) +{ + Py_BEGIN_CRITICAL_SECTION(op); + clear_lock_held(op); + Py_END_CRITICAL_SECTION(); +} + /* Internal version of PyDict_Next that returns a hash value in addition * to the key and value. * Return 1 on success, return 0 when the reached the end of the dictionary @@ -2117,16 +2888,16 @@ _PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, if (!PyDict_Check(op)) return 0; + mp = (PyDictObject *)op; i = *ppos; - if (mp->ma_values) { + if (_PyDict_HasSplitTable(mp)) { assert(mp->ma_used <= SHARED_KEYS_MAX_SIZE); if (i < 0 || i >= mp->ma_used) return 0; int index = get_index_from_order(mp, i); value = mp->ma_values->values[index]; - - key = DK_UNICODE_ENTRIES(mp->ma_keys)[index].me_key; + key = LOAD_SHARED_KEY(DK_UNICODE_ENTRIES(mp->ma_keys)[index].me_key); hash = unicode_get_hash(key); assert(value != NULL); } @@ -2193,62 +2964,179 @@ PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue) return _PyDict_Next(op, ppos, pkey, pvalue, NULL); } + /* Internal version of dict.pop(). */ -PyObject * -_PyDict_Pop_KnownHash(PyObject *dict, PyObject *key, Py_hash_t hash, PyObject *deflt) +int +_PyDict_Pop_KnownHash(PyDictObject *mp, PyObject *key, Py_hash_t hash, + PyObject **result) { - Py_ssize_t ix; - PyObject *old_value; - PyDictObject *mp; - PyInterpreterState *interp = _PyInterpreterState_GET(); + assert(PyDict_Check(mp)); - assert(PyDict_Check(dict)); - mp = (PyDictObject *)dict; + ASSERT_DICT_LOCKED(mp); if (mp->ma_used == 0) { - if (deflt) { - return Py_NewRef(deflt); + if (result) { + *result = NULL; } - _PyErr_SetKeyError(key); - return NULL; + return 0; } - ix = _Py_dict_lookup(mp, key, hash, &old_value); - if (ix == DKIX_ERROR) - return NULL; + + PyObject *old_value; + Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &old_value); + if (ix == DKIX_ERROR) { + if (result) { + *result = NULL; + } + return -1; + } + if (ix == DKIX_EMPTY || old_value == NULL) { - if (deflt) { - return Py_NewRef(deflt); + if (result) { + *result = NULL; } - _PyErr_SetKeyError(key); - return NULL; + return 0; } + assert(old_value != NULL); + PyInterpreterState *interp = _PyInterpreterState_GET(); uint64_t new_version = _PyDict_NotifyEvent( interp, PyDict_EVENT_DELETED, mp, key, NULL); delitem_common(mp, hash, ix, Py_NewRef(old_value), new_version); ASSERT_CONSISTENT(mp); - return old_value; + if (result) { + *result = old_value; + } + else { + Py_DECREF(old_value); + } + return 1; +} + +static int +pop_lock_held(PyObject *op, PyObject *key, PyObject **result) +{ + ASSERT_DICT_LOCKED(op); + + if (!PyDict_Check(op)) { + if (result) { + *result = NULL; + } + PyErr_BadInternalCall(); + return -1; + } + PyDictObject *dict = (PyDictObject *)op; + + if (dict->ma_used == 0) { + if (result) { + *result = NULL; + } + return 0; + } + + Py_hash_t hash = _PyObject_HashFast(key); + if (hash == -1) { + if (result) { + *result = NULL; + } + return -1; + } + return _PyDict_Pop_KnownHash(dict, key, hash, result); +} + +int +PyDict_Pop(PyObject *op, PyObject *key, PyObject **result) +{ + int err; + Py_BEGIN_CRITICAL_SECTION(op); + err = pop_lock_held(op, key, result); + Py_END_CRITICAL_SECTION(); + + return err; +} + + +int +PyDict_PopString(PyObject *op, const char *key, PyObject **result) +{ + PyObject *key_obj = PyUnicode_FromString(key); + if (key_obj == NULL) { + if (result != NULL) { + *result = NULL; + } + return -1; + } + + int res = PyDict_Pop(op, key_obj, result); + Py_DECREF(key_obj); + return res; } + PyObject * -_PyDict_Pop(PyObject *dict, PyObject *key, PyObject *deflt) +_PyDict_Pop(PyObject *dict, PyObject *key, PyObject *default_value) +{ + PyObject *result; + if (PyDict_Pop(dict, key, &result) == 0) { + if (default_value != NULL) { + return Py_NewRef(default_value); + } + _PyErr_SetKeyError(key); + return NULL; + } + return result; +} + +static PyDictObject * +dict_dict_fromkeys(PyInterpreterState *interp, PyDictObject *mp, + PyObject *iterable, PyObject *value) { + PyObject *oldvalue; + Py_ssize_t pos = 0; + PyObject *key; Py_hash_t hash; + int unicode = DK_IS_UNICODE(((PyDictObject*)iterable)->ma_keys); + uint8_t new_size = Py_MAX( + estimate_log2_keysize(PyDict_GET_SIZE(iterable)), + DK_LOG_SIZE(mp->ma_keys)); + if (dictresize(interp, mp, new_size, unicode)) { + Py_DECREF(mp); + return NULL; + } - if (((PyDictObject *)dict)->ma_used == 0) { - if (deflt) { - return Py_NewRef(deflt); + while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) { + if (insertdict(interp, mp, + Py_NewRef(key), hash, Py_NewRef(value))) { + Py_DECREF(mp); + return NULL; } - _PyErr_SetKeyError(key); + } + return mp; +} + +static PyDictObject * +dict_set_fromkeys(PyInterpreterState *interp, PyDictObject *mp, + PyObject *iterable, PyObject *value) +{ + Py_ssize_t pos = 0; + PyObject *key; + Py_hash_t hash; + uint8_t new_size = Py_MAX( + estimate_log2_keysize(PySet_GET_SIZE(iterable)), + DK_LOG_SIZE(mp->ma_keys)); + if (dictresize(interp, mp, new_size, 0)) { + Py_DECREF(mp); return NULL; } - if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) + + _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(iterable); + while (_PySet_NextEntryRef(iterable, &pos, &key, &hash)) { + if (insertdict(interp, mp, key, hash, Py_NewRef(value))) { + Py_DECREF(mp); return NULL; + } } - return _PyDict_Pop_KnownHash(dict, key, hash, deflt); + return mp; } /* Internal version of dict.from_keys(). It is subclass-friendly. */ @@ -2265,49 +3153,22 @@ _PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value) if (d == NULL) return NULL; - if (PyDict_CheckExact(d) && ((PyDictObject *)d)->ma_used == 0) { + + if (PyDict_CheckExact(d)) { if (PyDict_CheckExact(iterable)) { PyDictObject *mp = (PyDictObject *)d; - PyObject *oldvalue; - Py_ssize_t pos = 0; - PyObject *key; - Py_hash_t hash; - - int unicode = DK_IS_UNICODE(((PyDictObject*)iterable)->ma_keys); - if (dictresize(interp, mp, - estimate_log2_keysize(PyDict_GET_SIZE(iterable)), - unicode)) { - Py_DECREF(d); - return NULL; - } - while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) { - if (insertdict(interp, mp, - Py_NewRef(key), hash, Py_NewRef(value))) { - Py_DECREF(d); - return NULL; - } - } + Py_BEGIN_CRITICAL_SECTION2(d, iterable); + d = (PyObject *)dict_dict_fromkeys(interp, mp, iterable, value); + Py_END_CRITICAL_SECTION2(); return d; } - if (PyAnySet_CheckExact(iterable)) { + else if (PyAnySet_CheckExact(iterable)) { PyDictObject *mp = (PyDictObject *)d; - Py_ssize_t pos = 0; - PyObject *key; - Py_hash_t hash; - - if (dictresize(interp, mp, - estimate_log2_keysize(PySet_GET_SIZE(iterable)), 0)) { - Py_DECREF(d); - return NULL; - } - while (_PySet_NextEntry(iterable, &pos, &key, &hash)) { - if (insertdict(interp, mp, Py_NewRef(key), hash, Py_NewRef(value))) { - Py_DECREF(d); - return NULL; - } - } + Py_BEGIN_CRITICAL_SECTION2(d, iterable); + d = (PyObject *)dict_set_fromkeys(interp, mp, iterable, value); + Py_END_CRITICAL_SECTION2(); return d; } } @@ -2319,12 +3180,17 @@ _PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value) } if (PyDict_CheckExact(d)) { + Py_BEGIN_CRITICAL_SECTION(d); while ((key = PyIter_Next(it)) != NULL) { - status = PyDict_SetItem(d, key, value); + status = setitem_lock_held((PyDictObject *)d, key, value); Py_DECREF(key); - if (status < 0) - goto Fail; + if (status < 0) { + assert(PyErr_Occurred()); + goto dict_iter_exit; + } } +dict_iter_exit:; + Py_END_CRITICAL_SECTION(); } else { while ((key = PyIter_Next(it)) != NULL) { status = PyObject_SetItem(d, key, value); @@ -2348,17 +3214,15 @@ Fail: /* Methods */ static void -dict_dealloc(PyDictObject *mp) +dict_dealloc(PyObject *self) { + PyDictObject *mp = (PyDictObject *)self; PyInterpreterState *interp = _PyInterpreterState_GET(); - assert(Py_REFCNT(mp) == 0); - Py_SET_REFCNT(mp, 1); + _PyObject_ResurrectStart(self); _PyDict_NotifyEvent(interp, PyDict_EVENT_DEALLOCATED, mp, NULL, NULL); - if (Py_REFCNT(mp) > 1) { - Py_SET_REFCNT(mp, Py_REFCNT(mp) - 1); + if (_PyObject_ResurrectEnd(self)) { return; } - Py_SET_REFCNT(mp, 0); PyDictValues *values = mp->ma_values; PyDictKeysObject *keys = mp->ma_keys; Py_ssize_t i, n; @@ -2367,24 +3231,23 @@ dict_dealloc(PyDictObject *mp) PyObject_GC_UnTrack(mp); Py_TRASHCAN_BEGIN(mp, dict_dealloc) if (values != NULL) { - for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) { - Py_XDECREF(values->values[i]); + if (values->embedded == 0) { + for (i = 0, n = values->capacity; i < n; i++) { + Py_XDECREF(values->values[i]); + } + free_values(values, false); } - free_values(values); - dictkeys_decref(interp, keys); + dictkeys_decref(interp, keys, false); } else if (keys != NULL) { assert(keys->dk_refcnt == 1 || keys == Py_EMPTY_KEYS); - dictkeys_decref(interp, keys); + dictkeys_decref(interp, keys, false); } -#if PyDict_MAXFREELIST > 0 - struct _Py_dict_state *state = get_dict_state(interp); -#ifdef Py_DEBUG - // new_dict() must not be called after _PyDict_Fini() - assert(state->numfree != -1); -#endif - if (state->numfree < PyDict_MAXFREELIST && Py_IS_TYPE(mp, &PyDict_Type)) { - state->free_list[state->numfree++] = mp; +#ifdef WITH_FREELISTS + struct _Py_dict_freelist *freelist = get_dict_freelist(); + if (freelist->numfree < PyDict_MAXFREELIST && freelist->numfree >=0 && + Py_IS_TYPE(mp, &PyDict_Type)) { + freelist->items[freelist->numfree++] = mp; OBJECT_STAT_INC(to_freelist); } else @@ -2397,13 +3260,16 @@ dict_dealloc(PyDictObject *mp) static PyObject * -dict_repr(PyDictObject *mp) +dict_repr_lock_held(PyObject *self) { + PyDictObject *mp = (PyDictObject *)self; Py_ssize_t i; PyObject *key = NULL, *value = NULL; _PyUnicodeWriter writer; int first; + ASSERT_DICT_LOCKED(mp); + i = Py_ReprEnter((PyObject *)mp); if (i != 0) { return i > 0 ? PyUnicode_FromString("{...}") : NULL; @@ -2426,7 +3292,7 @@ dict_repr(PyDictObject *mp) Note that repr may mutate the dict. */ i = 0; first = 1; - while (PyDict_Next((PyObject *)mp, &i, &key, &value)) { + while (_PyDict_Next((PyObject *)mp, &i, &key, &value, NULL)) { PyObject *s; int res; @@ -2479,25 +3345,35 @@ error: return NULL; } +static PyObject * +dict_repr(PyObject *self) +{ + PyObject *res; + Py_BEGIN_CRITICAL_SECTION(self); + res = dict_repr_lock_held(self); + Py_END_CRITICAL_SECTION(); + return res; +} + static Py_ssize_t -dict_length(PyDictObject *mp) +dict_length(PyObject *self) { - return mp->ma_used; + return FT_ATOMIC_LOAD_SSIZE_RELAXED(((PyDictObject *)self)->ma_used); } static PyObject * -dict_subscript(PyDictObject *mp, PyObject *key) +dict_subscript(PyObject *self, PyObject *key) { + PyDictObject *mp = (PyDictObject *)self; Py_ssize_t ix; Py_hash_t hash; PyObject *value; - if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) - return NULL; + hash = _PyObject_HashFast(key); + if (hash == -1) { + return NULL; } - ix = _Py_dict_lookup(mp, key, hash, &value); + ix = _Py_dict_lookup_threadsafe(mp, key, hash, &value); if (ix == DKIX_ERROR) return NULL; if (ix == DKIX_EMPTY || value == NULL) { @@ -2517,27 +3393,34 @@ dict_subscript(PyDictObject *mp, PyObject *key) _PyErr_SetKeyError(key); return NULL; } - return Py_NewRef(value); + return value; } static int -dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w) +dict_ass_sub(PyObject *mp, PyObject *v, PyObject *w) { if (w == NULL) - return PyDict_DelItem((PyObject *)mp, v); + return PyDict_DelItem(mp, v); else - return PyDict_SetItem((PyObject *)mp, v, w); + return PyDict_SetItem(mp, v, w); } static PyMappingMethods dict_as_mapping = { - (lenfunc)dict_length, /*mp_length*/ - (binaryfunc)dict_subscript, /*mp_subscript*/ - (objobjargproc)dict_ass_sub, /*mp_ass_subscript*/ + dict_length, /*mp_length*/ + dict_subscript, /*mp_subscript*/ + dict_ass_sub, /*mp_ass_subscript*/ }; static PyObject * -dict_keys(PyDictObject *mp) +keys_lock_held(PyObject *dict) { + ASSERT_DICT_LOCKED(dict); + + if (dict == NULL || !PyDict_Check(dict)) { + PyErr_BadInternalCall(); + return NULL; + } + PyDictObject *mp = (PyDictObject *)dict; PyObject *v; Py_ssize_t n; @@ -2566,9 +3449,27 @@ dict_keys(PyDictObject *mp) return v; } +PyObject * +PyDict_Keys(PyObject *dict) +{ + PyObject *res; + Py_BEGIN_CRITICAL_SECTION(dict); + res = keys_lock_held(dict); + Py_END_CRITICAL_SECTION(); + + return res; +} + static PyObject * -dict_values(PyDictObject *mp) +values_lock_held(PyObject *dict) { + ASSERT_DICT_LOCKED(dict); + + if (dict == NULL || !PyDict_Check(dict)) { + PyErr_BadInternalCall(); + return NULL; + } + PyDictObject *mp = (PyDictObject *)dict; PyObject *v; Py_ssize_t n; @@ -2597,9 +3498,26 @@ dict_values(PyDictObject *mp) return v; } +PyObject * +PyDict_Values(PyObject *dict) +{ + PyObject *res; + Py_BEGIN_CRITICAL_SECTION(dict); + res = values_lock_held(dict); + Py_END_CRITICAL_SECTION(); + return res; +} + static PyObject * -dict_items(PyDictObject *mp) +items_lock_held(PyObject *dict) { + ASSERT_DICT_LOCKED(dict); + + if (dict == NULL || !PyDict_Check(dict)) { + PyErr_BadInternalCall(); + return NULL; + } + PyDictObject *mp = (PyDictObject *)dict; PyObject *v; Py_ssize_t i, n; PyObject *item; @@ -2643,6 +3561,17 @@ dict_items(PyDictObject *mp) return v; } +PyObject * +PyDict_Items(PyObject *dict) +{ + PyObject *res; + Py_BEGIN_CRITICAL_SECTION(dict); + res = items_lock_held(dict); + Py_END_CRITICAL_SECTION(); + + return res; +} + /*[clinic input] @classmethod dict.fromkeys @@ -2667,12 +3596,11 @@ dict_update_arg(PyObject *self, PyObject *arg) if (PyDict_CheckExact(arg)) { return PyDict_Merge(self, arg, 1); } - PyObject *func; - if (_PyObject_LookupAttr(arg, &_Py_ID(keys), &func) < 0) { + int has_keys = PyObject_HasAttrWithError(arg, &_Py_ID(keys)); + if (has_keys < 0) { return -1; } - if (func != NULL) { - Py_DECREF(func); + if (has_keys) { return PyDict_Merge(self, arg, 1); } return PyDict_MergeFromSeq2(self, arg, 1); @@ -2722,8 +3650,8 @@ dict_update(PyObject *self, PyObject *args, PyObject *kwds) producing iterable objects of length 2. */ -int -PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override) +static int +merge_from_seq2_lock_held(PyObject *d, PyObject *seq2, int override) { PyObject *it; /* iter(seq2) */ Py_ssize_t i; /* index into seq2 of current element */ @@ -2775,14 +3703,14 @@ PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override) Py_INCREF(key); Py_INCREF(value); if (override) { - if (PyDict_SetItem(d, key, value) < 0) { + if (setitem_lock_held((PyDictObject *)d, key, value) < 0) { Py_DECREF(key); Py_DECREF(value); goto Fail; } } else { - if (PyDict_SetDefault(d, key, value) == NULL) { + if (dict_setdefault_ref_lock_held(d, key, value, NULL, 0) < 0) { Py_DECREF(key); Py_DECREF(value); goto Fail; @@ -2807,140 +3735,169 @@ Return: return Py_SAFE_DOWNCAST(i, Py_ssize_t, int); } -static int -dict_merge(PyInterpreterState *interp, PyObject *a, PyObject *b, int override) +int +PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override) { - PyDictObject *mp, *other; - - assert(0 <= override && override <= 2); + int res; + Py_BEGIN_CRITICAL_SECTION(d); + res = merge_from_seq2_lock_held(d, seq2, override); + Py_END_CRITICAL_SECTION(); - /* We accept for the argument either a concrete dictionary object, - * or an abstract "mapping" object. For the former, we can do - * things quite efficiently. For the latter, we only require that - * PyMapping_Keys() and PyObject_GetItem() be supported. - */ - if (a == NULL || !PyDict_Check(a) || b == NULL) { - PyErr_BadInternalCall(); - return -1; - } - mp = (PyDictObject*)a; - if (PyDict_Check(b) && (Py_TYPE(b)->tp_iter == (getiterfunc)dict_iter)) { - other = (PyDictObject*)b; - if (other == mp || other->ma_used == 0) - /* a.update(a) or a.update({}); nothing to do */ - return 0; - if (mp->ma_used == 0) { - /* Since the target dict is empty, PyDict_GetItem() - * always returns NULL. Setting override to 1 - * skips the unnecessary test. - */ - override = 1; - PyDictKeysObject *okeys = other->ma_keys; + return res; +} - // If other is clean, combined, and just allocated, just clone it. - if (other->ma_values == NULL && - other->ma_used == okeys->dk_nentries && - (DK_LOG_SIZE(okeys) == PyDict_LOG_MINSIZE || - USABLE_FRACTION(DK_SIZE(okeys)/2) < other->ma_used)) { - uint64_t new_version = _PyDict_NotifyEvent( - interp, PyDict_EVENT_CLONED, mp, b, NULL); - PyDictKeysObject *keys = clone_combined_dict_keys(other); - if (keys == NULL) { - return -1; - } +static int +dict_dict_merge(PyInterpreterState *interp, PyDictObject *mp, PyDictObject *other, int override) +{ + ASSERT_DICT_LOCKED(mp); + ASSERT_DICT_LOCKED(other); - dictkeys_decref(interp, mp->ma_keys); - mp->ma_keys = keys; - if (mp->ma_values != NULL) { - free_values(mp->ma_values); - mp->ma_values = NULL; - } + if (other == mp || other->ma_used == 0) + /* a.update(a) or a.update({}); nothing to do */ + return 0; + if (mp->ma_used == 0) { + /* Since the target dict is empty, PyDict_GetItem() + * always returns NULL. Setting override to 1 + * skips the unnecessary test. + */ + override = 1; + PyDictKeysObject *okeys = other->ma_keys; - mp->ma_used = other->ma_used; - mp->ma_version_tag = new_version; - ASSERT_CONSISTENT(mp); + // If other is clean, combined, and just allocated, just clone it. + if (mp->ma_values == NULL && + other->ma_values == NULL && + other->ma_used == okeys->dk_nentries && + (DK_LOG_SIZE(okeys) == PyDict_LOG_MINSIZE || + USABLE_FRACTION(DK_SIZE(okeys)/2) < other->ma_used) + ) { + uint64_t new_version = _PyDict_NotifyEvent( + interp, PyDict_EVENT_CLONED, mp, (PyObject *)other, NULL); + PyDictKeysObject *keys = clone_combined_dict_keys(other); + if (keys == NULL) + return -1; - if (_PyObject_GC_IS_TRACKED(other) && !_PyObject_GC_IS_TRACKED(mp)) { - /* Maintain tracking. */ - _PyObject_GC_TRACK(mp); - } + ensure_shared_on_resize(mp); + dictkeys_decref(interp, mp->ma_keys, IS_DICT_SHARED(mp)); + set_keys(mp, keys); + STORE_USED(mp, other->ma_used); + mp->ma_version_tag = new_version; + ASSERT_CONSISTENT(mp); - return 0; + if (_PyObject_GC_IS_TRACKED(other) && !_PyObject_GC_IS_TRACKED(mp)) { + /* Maintain tracking. */ + _PyObject_GC_TRACK(mp); } + + return 0; } - /* Do one big resize at the start, rather than - * incrementally resizing as we insert new items. Expect - * that there will be no (or few) overlapping keys. - */ - if (USABLE_FRACTION(DK_SIZE(mp->ma_keys)) < other->ma_used) { - int unicode = DK_IS_UNICODE(other->ma_keys); - if (dictresize(interp, mp, - estimate_log2_keysize(mp->ma_used + other->ma_used), - unicode)) { - return -1; - } + } + /* Do one big resize at the start, rather than + * incrementally resizing as we insert new items. Expect + * that there will be no (or few) overlapping keys. + */ + if (USABLE_FRACTION(DK_SIZE(mp->ma_keys)) < other->ma_used) { + int unicode = DK_IS_UNICODE(other->ma_keys); + if (dictresize(interp, mp, + estimate_log2_keysize(mp->ma_used + other->ma_used), + unicode)) { + return -1; } + } - Py_ssize_t orig_size = other->ma_keys->dk_nentries; - Py_ssize_t pos = 0; - Py_hash_t hash; - PyObject *key, *value; + Py_ssize_t orig_size = other->ma_used; + Py_ssize_t pos = 0; + Py_hash_t hash; + PyObject *key, *value; - while (_PyDict_Next((PyObject*)other, &pos, &key, &value, &hash)) { - int err = 0; - Py_INCREF(key); - Py_INCREF(value); - if (override == 1) { + while (_PyDict_Next((PyObject*)other, &pos, &key, &value, &hash)) { + int err = 0; + Py_INCREF(key); + Py_INCREF(value); + if (override == 1) { + err = insertdict(interp, mp, + Py_NewRef(key), hash, Py_NewRef(value)); + } + else { + err = _PyDict_Contains_KnownHash((PyObject *)mp, key, hash); + if (err == 0) { err = insertdict(interp, mp, - Py_NewRef(key), hash, Py_NewRef(value)); + Py_NewRef(key), hash, Py_NewRef(value)); } - else { - err = _PyDict_Contains_KnownHash(a, key, hash); - if (err == 0) { - err = insertdict(interp, mp, - Py_NewRef(key), hash, Py_NewRef(value)); - } - else if (err > 0) { - if (override != 0) { - _PyErr_SetKeyError(key); - Py_DECREF(value); - Py_DECREF(key); - return -1; - } - err = 0; + else if (err > 0) { + if (override != 0) { + _PyErr_SetKeyError(key); + Py_DECREF(value); + Py_DECREF(key); + return -1; } + err = 0; } - Py_DECREF(value); - Py_DECREF(key); - if (err != 0) - return -1; + } + Py_DECREF(value); + Py_DECREF(key); + if (err != 0) + return -1; - if (orig_size != other->ma_keys->dk_nentries) { - PyErr_SetString(PyExc_RuntimeError, - "dict mutated during update"); - return -1; - } + if (orig_size != other->ma_used) { + PyErr_SetString(PyExc_RuntimeError, + "dict mutated during update"); + return -1; } } + return 0; +} + +static int +dict_merge(PyInterpreterState *interp, PyObject *a, PyObject *b, int override) +{ + PyDictObject *mp, *other; + + assert(0 <= override && override <= 2); + + /* We accept for the argument either a concrete dictionary object, + * or an abstract "mapping" object. For the former, we can do + * things quite efficiently. For the latter, we only require that + * PyMapping_Keys() and PyObject_GetItem() be supported. + */ + if (a == NULL || !PyDict_Check(a) || b == NULL) { + PyErr_BadInternalCall(); + return -1; + } + mp = (PyDictObject*)a; + int res = 0; + if (PyDict_Check(b) && (Py_TYPE(b)->tp_iter == dict_iter)) { + other = (PyDictObject*)b; + int res; + Py_BEGIN_CRITICAL_SECTION2(a, b); + res = dict_dict_merge(interp, (PyDictObject *)a, other, override); + ASSERT_CONSISTENT(a); + Py_END_CRITICAL_SECTION2(); + return res; + } else { /* Do it the generic, slower way */ + Py_BEGIN_CRITICAL_SECTION(a); PyObject *keys = PyMapping_Keys(b); PyObject *iter; PyObject *key, *value; int status; - if (keys == NULL) + if (keys == NULL) { /* Docstring says this is equivalent to E.keys() so * if E doesn't have a .keys() method we want * AttributeError to percolate up. Might as well * do the same for any other error. */ - return -1; + res = -1; + goto slow_exit; + } iter = PyObject_GetIter(keys); Py_DECREF(keys); - if (iter == NULL) - return -1; + if (iter == NULL) { + res = -1; + goto slow_exit; + } for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) { if (override != 1) { @@ -2955,30 +3912,39 @@ dict_merge(PyInterpreterState *interp, PyObject *a, PyObject *b, int override) } Py_DECREF(key); Py_DECREF(iter); - return -1; + res = -1; + goto slow_exit; } } value = PyObject_GetItem(b, key); if (value == NULL) { Py_DECREF(iter); Py_DECREF(key); - return -1; + res = -1; + goto slow_exit; } - status = PyDict_SetItem(a, key, value); + status = setitem_lock_held(mp, key, value); Py_DECREF(key); Py_DECREF(value); if (status < 0) { Py_DECREF(iter); + res = -1; + goto slow_exit; return -1; } } Py_DECREF(iter); - if (PyErr_Occurred()) + if (PyErr_Occurred()) { /* Iterator completed, via error */ - return -1; + res = -1; + goto slow_exit; + } + +slow_exit: + ASSERT_CONSISTENT(a); + Py_END_CRITICAL_SECTION(); + return res; } - ASSERT_CONSISTENT(a); - return 0; } int @@ -3003,23 +3969,48 @@ _PyDict_MergeEx(PyObject *a, PyObject *b, int override) return dict_merge(interp, a, b, override); } +/*[clinic input] +dict.copy + +Return a shallow copy of the dict. +[clinic start generated code]*/ + static PyObject * -dict_copy(PyDictObject *mp, PyObject *Py_UNUSED(ignored)) +dict_copy_impl(PyDictObject *self) +/*[clinic end generated code: output=ffb782cf970a5c39 input=73935f042b639de4]*/ { - return PyDict_Copy((PyObject*)mp); + return PyDict_Copy((PyObject *)self); } -PyObject * -PyDict_Copy(PyObject *o) +/* Copies the values, but does not change the reference + * counts of the objects in the array. + * Return NULL, but does *not* set an exception on failure */ +static PyDictValues * +copy_values(PyDictValues *values) +{ + PyDictValues *newvalues = new_values(values->capacity); + if (newvalues == NULL) { + return NULL; + } + newvalues->size = values->size; + uint8_t *values_order = get_insertion_order_array(values); + uint8_t *new_values_order = get_insertion_order_array(newvalues); + memcpy(new_values_order, values_order, values->capacity); + for (int i = 0; i < values->capacity; i++) { + newvalues->values[i] = values->values[i]; + } + assert(newvalues->embedded == 0); + return newvalues; +} + +static PyObject * +copy_lock_held(PyObject *o) { PyObject *copy; PyDictObject *mp; PyInterpreterState *interp = _PyInterpreterState_GET(); - if (o == NULL || !PyDict_Check(o)) { - PyErr_BadInternalCall(); - return NULL; - } + ASSERT_DICT_LOCKED(o); mp = (PyDictObject *)o; if (mp->ma_used == 0) { @@ -3029,32 +4020,29 @@ PyDict_Copy(PyObject *o) if (_PyDict_HasSplitTable(mp)) { PyDictObject *split_copy; - size_t size = shared_keys_usable_size(mp->ma_keys); - PyDictValues *newvalues = new_values(size); - if (newvalues == NULL) + PyDictValues *newvalues = copy_values(mp->ma_values); + if (newvalues == NULL) { return PyErr_NoMemory(); + } split_copy = PyObject_GC_New(PyDictObject, &PyDict_Type); if (split_copy == NULL) { - free_values(newvalues); + free_values(newvalues, false); return NULL; } - size_t prefix_size = ((uint8_t *)newvalues)[-1]; - memcpy(((char *)newvalues)-prefix_size, ((char *)mp->ma_values)-prefix_size, prefix_size-1); + for (size_t i = 0; i < newvalues->capacity; i++) { + Py_XINCREF(newvalues->values[i]); + } split_copy->ma_values = newvalues; split_copy->ma_keys = mp->ma_keys; split_copy->ma_used = mp->ma_used; split_copy->ma_version_tag = DICT_NEXT_VERSION(interp); dictkeys_incref(mp->ma_keys); - for (size_t i = 0; i < size; i++) { - PyObject *value = mp->ma_values->values[i]; - split_copy->ma_values->values[i] = Py_XNewRef(value); - } if (_PyObject_GC_IS_TRACKED(mp)) _PyObject_GC_TRACK(split_copy); return (PyObject *)split_copy; } - if (Py_TYPE(mp)->tp_iter == (getiterfunc)dict_iter && + if (Py_TYPE(mp)->tp_iter == dict_iter && mp->ma_values == NULL && (mp->ma_used >= (mp->ma_keys->dk_nentries * 2) / 3)) { @@ -3102,44 +4090,31 @@ PyDict_Copy(PyObject *o) return NULL; } -Py_ssize_t -PyDict_Size(PyObject *mp) -{ - if (mp == NULL || !PyDict_Check(mp)) { - PyErr_BadInternalCall(); - return -1; - } - return ((PyDictObject *)mp)->ma_used; -} - PyObject * -PyDict_Keys(PyObject *mp) +PyDict_Copy(PyObject *o) { - if (mp == NULL || !PyDict_Check(mp)) { + if (o == NULL || !PyDict_Check(o)) { PyErr_BadInternalCall(); return NULL; } - return dict_keys((PyDictObject *)mp); -} -PyObject * -PyDict_Values(PyObject *mp) -{ - if (mp == NULL || !PyDict_Check(mp)) { - PyErr_BadInternalCall(); - return NULL; - } - return dict_values((PyDictObject *)mp); + PyObject *res; + Py_BEGIN_CRITICAL_SECTION(o); + + res = copy_lock_held(o); + + Py_END_CRITICAL_SECTION(); + return res; } -PyObject * -PyDict_Items(PyObject *mp) +Py_ssize_t +PyDict_Size(PyObject *mp) { if (mp == NULL || !PyDict_Check(mp)) { PyErr_BadInternalCall(); - return NULL; + return -1; } - return dict_items((PyDictObject *)mp); + return FT_ATOMIC_LOAD_SSIZE_RELAXED(((PyDictObject *)mp)->ma_used); } /* Return 1 if dicts equal, 0 if not, -1 if error. @@ -3147,15 +4122,18 @@ PyDict_Items(PyObject *mp) * Uses only Py_EQ comparison. */ static int -dict_equal(PyDictObject *a, PyDictObject *b) +dict_equal_lock_held(PyDictObject *a, PyDictObject *b) { Py_ssize_t i; + ASSERT_DICT_LOCKED(a); + ASSERT_DICT_LOCKED(b); + if (a->ma_used != b->ma_used) /* can't be equal if # of entries differ */ return 0; /* Same # of entries -- check all of 'em. Exit early on any diff. */ - for (i = 0; i < a->ma_keys->dk_nentries; i++) { + for (i = 0; i < LOAD_KEYS_NENTRIES(a->ma_keys); i++) { PyObject *key, *aval; Py_hash_t hash; if (DK_IS_UNICODE(a->ma_keys)) { @@ -3165,7 +4143,7 @@ dict_equal(PyDictObject *a, PyDictObject *b) continue; } hash = unicode_get_hash(key); - if (a->ma_values) + if (_PyDict_HasSplitTable(a)) aval = a->ma_values->values[i]; else aval = ep->me_value; @@ -3205,6 +4183,17 @@ dict_equal(PyDictObject *a, PyDictObject *b) return 1; } +static int +dict_equal(PyDictObject *a, PyDictObject *b) +{ + int res; + Py_BEGIN_CRITICAL_SECTION2(a, b); + res = dict_equal_lock_held(a, b); + Py_END_CRITICAL_SECTION2(); + + return res; +} + static PyObject * dict_richcompare(PyObject *v, PyObject *w, int op) { @@ -3240,25 +4229,18 @@ static PyObject * dict___contains__(PyDictObject *self, PyObject *key) /*[clinic end generated code: output=a3d03db709ed6e6b input=fe1cb42ad831e820]*/ { - register PyDictObject *mp = self; - Py_hash_t hash; - Py_ssize_t ix; - PyObject *value; - - if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) - return NULL; - } - ix = _Py_dict_lookup(mp, key, hash, &value); - if (ix == DKIX_ERROR) + int contains = PyDict_Contains((PyObject *)self, key); + if (contains < 0) { return NULL; - if (ix == DKIX_EMPTY || value == NULL) - Py_RETURN_FALSE; - Py_RETURN_TRUE; + } + if (contains) { + Py_RETURN_TRUE; + } + Py_RETURN_FALSE; } /*[clinic input] +@critical_section dict.get key: object @@ -3270,121 +4252,147 @@ Return the value for key if key is in the dictionary, else default. static PyObject * dict_get_impl(PyDictObject *self, PyObject *key, PyObject *default_value) -/*[clinic end generated code: output=bba707729dee05bf input=279ddb5790b6b107]*/ +/*[clinic end generated code: output=bba707729dee05bf input=a631d3f18f584c60]*/ { PyObject *val = NULL; Py_hash_t hash; Py_ssize_t ix; - if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) - return NULL; + hash = _PyObject_HashFast(key); + if (hash == -1) { + return NULL; } - ix = _Py_dict_lookup(self, key, hash, &val); + ix = _Py_dict_lookup_threadsafe(self, key, hash, &val); if (ix == DKIX_ERROR) return NULL; if (ix == DKIX_EMPTY || val == NULL) { - val = default_value; + val = Py_NewRef(default_value); } - return Py_NewRef(val); + return val; } -PyObject * -PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj) +static int +dict_setdefault_ref_lock_held(PyObject *d, PyObject *key, PyObject *default_value, + PyObject **result, int incref_result) { PyDictObject *mp = (PyDictObject *)d; PyObject *value; Py_hash_t hash; + Py_ssize_t ix; PyInterpreterState *interp = _PyInterpreterState_GET(); + ASSERT_DICT_LOCKED(d); + if (!PyDict_Check(d)) { PyErr_BadInternalCall(); - return NULL; + if (result) { + *result = NULL; + } + return -1; } - if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) - return NULL; + hash = _PyObject_HashFast(key); + if (hash == -1) { + if (result) { + *result = NULL; + } + return -1; } if (mp->ma_keys == Py_EMPTY_KEYS) { if (insert_to_emptydict(interp, mp, Py_NewRef(key), hash, - Py_NewRef(defaultobj)) < 0) { - return NULL; + Py_NewRef(default_value)) < 0) { + if (result) { + *result = NULL; + } + return -1; } - return defaultobj; - } - - if (!PyUnicode_CheckExact(key) && DK_IS_UNICODE(mp->ma_keys)) { - if (insertion_resize(interp, mp, 0) < 0) { - return NULL; + if (result) { + *result = incref_result ? Py_NewRef(default_value) : default_value; } + return 0; } - Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &value); - if (ix == DKIX_ERROR) - return NULL; - - if (ix == DKIX_EMPTY) { - value = defaultobj; - if (mp->ma_keys->dk_usable <= 0) { - if (insertion_resize(interp, mp, 1) < 0) { - return NULL; + if (_PyDict_HasSplitTable(mp) && PyUnicode_CheckExact(key)) { + ix = insert_split_key(mp->ma_keys, key, hash); + if (ix != DKIX_EMPTY) { + PyObject *value = mp->ma_values->values[ix]; + int already_present = value != NULL; + if (!already_present) { + insert_split_value(interp, mp, key, default_value, ix); + value = default_value; } - } - uint64_t new_version = _PyDict_NotifyEvent( - interp, PyDict_EVENT_ADDED, mp, key, defaultobj); - mp->ma_keys->dk_version = 0; - Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash); - dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries); - if (DK_IS_UNICODE(mp->ma_keys)) { - assert(PyUnicode_CheckExact(key)); - PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries]; - ep->me_key = Py_NewRef(key); - if (_PyDict_HasSplitTable(mp)) { - Py_ssize_t index = (int)mp->ma_keys->dk_nentries; - assert(index < SHARED_KEYS_MAX_SIZE); - assert(mp->ma_values->values[index] == NULL); - mp->ma_values->values[index] = Py_NewRef(value); - _PyDictValues_AddToInsertionOrder(mp->ma_values, index); + if (result) { + *result = incref_result ? Py_NewRef(value) : value; } - else { - ep->me_value = Py_NewRef(value); + return already_present; + } + // No space in shared keys. Go to insert_combined_dict() below. + } + else { + ix = _Py_dict_lookup(mp, key, hash, &value); + if (ix == DKIX_ERROR) { + if (result) { + *result = NULL; } + return -1; } - else { - PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries]; - ep->me_key = Py_NewRef(key); - ep->me_hash = hash; - ep->me_value = Py_NewRef(value); + } + + if (ix == DKIX_EMPTY) { + value = default_value; + + // See comment to this function in insertdict. + if (insert_combined_dict(interp, mp, hash, Py_NewRef(key), Py_NewRef(value)) < 0) { + Py_DECREF(key); + Py_DECREF(value); + if (result) { + *result = NULL; + } + return -1; } + MAINTAIN_TRACKING(mp, key, value); - mp->ma_used++; - mp->ma_version_tag = new_version; - mp->ma_keys->dk_usable--; - mp->ma_keys->dk_nentries++; + STORE_USED(mp, mp->ma_used + 1); assert(mp->ma_keys->dk_usable >= 0); - } - else if (value == NULL) { - uint64_t new_version = _PyDict_NotifyEvent( - interp, PyDict_EVENT_ADDED, mp, key, defaultobj); - value = defaultobj; - assert(_PyDict_HasSplitTable(mp)); - assert(mp->ma_values->values[ix] == NULL); - MAINTAIN_TRACKING(mp, key, value); - mp->ma_values->values[ix] = Py_NewRef(value); - _PyDictValues_AddToInsertionOrder(mp->ma_values, ix); - mp->ma_used++; - mp->ma_version_tag = new_version; + ASSERT_CONSISTENT(mp); + if (result) { + *result = incref_result ? Py_NewRef(value) : value; + } + return 0; } + assert(value != NULL); ASSERT_CONSISTENT(mp); - return value; + if (result) { + *result = incref_result ? Py_NewRef(value) : value; + } + return 1; +} + +int +PyDict_SetDefaultRef(PyObject *d, PyObject *key, PyObject *default_value, + PyObject **result) +{ + int res; + Py_BEGIN_CRITICAL_SECTION(d); + res = dict_setdefault_ref_lock_held(d, key, default_value, result, 1); + Py_END_CRITICAL_SECTION(); + return res; +} + +PyObject * +PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj) +{ + PyObject *result; + Py_BEGIN_CRITICAL_SECTION(d); + dict_setdefault_ref_lock_held(d, key, defaultobj, &result, 0); + Py_END_CRITICAL_SECTION(); + return result; } /*[clinic input] +@critical_section dict.setdefault key: object @@ -3399,18 +4407,25 @@ Return the value for key if key is in the dictionary, else default. static PyObject * dict_setdefault_impl(PyDictObject *self, PyObject *key, PyObject *default_value) -/*[clinic end generated code: output=f8c1101ebf69e220 input=0f063756e815fd9d]*/ +/*[clinic end generated code: output=f8c1101ebf69e220 input=9237af9a0a224302]*/ { PyObject *val; - - val = PyDict_SetDefault((PyObject *)self, key, default_value); - return Py_XNewRef(val); + dict_setdefault_ref_lock_held((PyObject *)self, key, default_value, &val, 1); + return val; } + +/*[clinic input] +dict.clear + +Remove all items from the dict. +[clinic start generated code]*/ + static PyObject * -dict_clear(PyDictObject *mp, PyObject *Py_UNUSED(ignored)) +dict_clear_impl(PyDictObject *self) +/*[clinic end generated code: output=5139a830df00830a input=0bf729baba97a4c2]*/ { - PyDict_Clear((PyObject *)mp); + PyDict_Clear((PyObject *)self); Py_RETURN_NONE; } @@ -3435,6 +4450,7 @@ dict_pop_impl(PyDictObject *self, PyObject *key, PyObject *default_value) } /*[clinic input] +@critical_section dict.popitem Remove and return a (key, value) pair as a 2-tuple. @@ -3445,13 +4461,15 @@ Raises KeyError if the dict is empty. static PyObject * dict_popitem_impl(PyDictObject *self) -/*[clinic end generated code: output=e65fcb04420d230d input=1c38a49f21f64941]*/ +/*[clinic end generated code: output=e65fcb04420d230d input=ef28b4da5f0f762e]*/ { Py_ssize_t i, j; PyObject *res; uint64_t new_version; PyInterpreterState *interp = _PyInterpreterState_GET(); + ASSERT_DICT_LOCKED(self); + /* Allocate the result tuple before checking the size. Believe it * or not, this allocation could trigger a garbage collection which * could empty the dict, so if we checked the size first and that @@ -3470,8 +4488,8 @@ dict_popitem_impl(PyDictObject *self) return NULL; } /* Convert split table to combined table */ - if (self->ma_keys->dk_kind == DICT_KEYS_SPLIT) { - if (dictresize(interp, self, DK_LOG_SIZE(self->ma_keys), 1)) { + if (_PyDict_HasSplitTable(self)) { + if (dictresize(interp, self, DK_LOG_SIZE(self->ma_keys), 1) < 0) { Py_DECREF(res); return NULL; } @@ -3494,8 +4512,8 @@ dict_popitem_impl(PyDictObject *self) interp, PyDict_EVENT_DELETED, self, key, NULL); hash = unicode_get_hash(key); value = ep0[i].me_value; - ep0[i].me_key = NULL; - ep0[i].me_value = NULL; + STORE_KEY(&ep0[i], NULL); + STORE_VALUE(&ep0[i], NULL); } else { PyDictKeyEntry *ep0 = DK_ENTRIES(self->ma_keys); @@ -3510,9 +4528,9 @@ dict_popitem_impl(PyDictObject *self) interp, PyDict_EVENT_DELETED, self, key, NULL); hash = ep0[i].me_hash; value = ep0[i].me_value; - ep0[i].me_key = NULL; - ep0[i].me_hash = -1; - ep0[i].me_value = NULL; + STORE_KEY(&ep0[i], NULL); + STORE_HASH(&ep0[i], -1); + STORE_VALUE(&ep0[i], NULL); } j = lookdict_index(self->ma_keys, hash, i); @@ -3523,8 +4541,8 @@ dict_popitem_impl(PyDictObject *self) PyTuple_SET_ITEM(res, 0, key); PyTuple_SET_ITEM(res, 1, value); /* We can't dk_usable++ since there is DKIX_DUMMY in indices */ - self->ma_keys->dk_nentries = i; - self->ma_used--; + STORE_KEYS_NENTRIES(self->ma_keys, i); + STORE_USED(self, self->ma_used - 1); self->ma_version_tag = new_version; ASSERT_CONSISTENT(self); return res; @@ -3538,7 +4556,7 @@ dict_traverse(PyObject *op, visitproc visit, void *arg) Py_ssize_t i, n = keys->dk_nentries; if (DK_IS_UNICODE(keys)) { - if (mp->ma_values != NULL) { + if (_PyDict_HasSplitTable(mp)) { for (i = 0; i < n; i++) { Py_VISIT(mp->ma_values->values[i]); } @@ -3571,11 +4589,11 @@ dict_tp_clear(PyObject *op) static PyObject *dictiter_new(PyDictObject *, PyTypeObject *); -Py_ssize_t -_PyDict_SizeOf(PyDictObject *mp) +static Py_ssize_t +sizeof_lock_held(PyDictObject *mp) { size_t res = _PyObject_SIZE(Py_TYPE(mp)); - if (mp->ma_values) { + if (_PyDict_HasSplitTable(mp)) { res += shared_keys_usable_size(mp->ma_keys) * sizeof(PyObject*); } /* If the dictionary is split, the keys portion is accounted-for @@ -3587,6 +4605,17 @@ _PyDict_SizeOf(PyDictObject *mp) return (Py_ssize_t)res; } +Py_ssize_t +_PyDict_SizeOf(PyDictObject *mp) +{ + Py_ssize_t res; + Py_BEGIN_CRITICAL_SECTION(mp); + res = sizeof_lock_held(mp); + Py_END_CRITICAL_SECTION(); + + return res; +} + size_t _PyDict_KeysSize(PyDictKeysObject *keys) { @@ -3598,10 +4627,17 @@ _PyDict_KeysSize(PyDictKeysObject *keys) return size; } +/*[clinic input] +dict.__sizeof__ + +Return the size of the dict in memory, in bytes. +[clinic start generated code]*/ + static PyObject * -dict_sizeof(PyDictObject *mp, PyObject *Py_UNUSED(ignored)) +dict___sizeof___impl(PyDictObject *self) +/*[clinic end generated code: output=44279379b3824bda input=4fec4ddfc44a4d1a]*/ { - return PyLong_FromSsize_t(_PyDict_SizeOf(mp)); + return PyLong_FromSsize_t(_PyDict_SizeOf(self)); } static PyObject * @@ -3633,56 +4669,31 @@ dict_ior(PyObject *self, PyObject *other) PyDoc_STRVAR(getitem__doc__, "__getitem__($self, key, /)\n--\n\nReturn self[key]."); -PyDoc_STRVAR(sizeof__doc__, -"D.__sizeof__() -> size of D in memory, in bytes"); - PyDoc_STRVAR(update__doc__, "D.update([E, ]**F) -> None. Update D from mapping/iterable E and F.\n\ If E is present and has a .keys() method, then does: for k in E.keys(): D[k] = E[k]\n\ If E is present and lacks a .keys() method, then does: for k, v in E: D[k] = v\n\ In either case, this is followed by: for k in F: D[k] = F[k]"); -PyDoc_STRVAR(clear__doc__, -"D.clear() -> None. Remove all items from D."); - -PyDoc_STRVAR(copy__doc__, -"D.copy() -> a shallow copy of D"); - /* Forward */ -static PyObject *dictkeys_new(PyObject *, PyObject *); -static PyObject *dictitems_new(PyObject *, PyObject *); -static PyObject *dictvalues_new(PyObject *, PyObject *); - -PyDoc_STRVAR(keys__doc__, - "D.keys() -> a set-like object providing a view on D's keys"); -PyDoc_STRVAR(items__doc__, - "D.items() -> a set-like object providing a view on D's items"); -PyDoc_STRVAR(values__doc__, - "D.values() -> an object providing a view on D's values"); static PyMethodDef mapp_methods[] = { DICT___CONTAINS___METHODDEF - {"__getitem__", _PyCFunction_CAST(dict_subscript), METH_O | METH_COEXIST, + {"__getitem__", dict_subscript, METH_O | METH_COEXIST, getitem__doc__}, - {"__sizeof__", _PyCFunction_CAST(dict_sizeof), METH_NOARGS, - sizeof__doc__}, + DICT___SIZEOF___METHODDEF DICT_GET_METHODDEF DICT_SETDEFAULT_METHODDEF DICT_POP_METHODDEF DICT_POPITEM_METHODDEF - {"keys", dictkeys_new, METH_NOARGS, - keys__doc__}, - {"items", dictitems_new, METH_NOARGS, - items__doc__}, - {"values", dictvalues_new, METH_NOARGS, - values__doc__}, + DICT_KEYS_METHODDEF + DICT_ITEMS_METHODDEF + DICT_VALUES_METHODDEF {"update", _PyCFunction_CAST(dict_update), METH_VARARGS | METH_KEYWORDS, update__doc__}, DICT_FROMKEYS_METHODDEF - {"clear", (PyCFunction)dict_clear, METH_NOARGS, - clear__doc__}, - {"copy", (PyCFunction)dict_copy, METH_NOARGS, - copy__doc__}, + DICT_CLEAR_METHODDEF + DICT_COPY_METHODDEF DICT___REVERSED___METHODDEF {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")}, {NULL, NULL} /* sentinel */ @@ -3692,20 +4703,25 @@ static PyMethodDef mapp_methods[] = { int PyDict_Contains(PyObject *op, PyObject *key) { - Py_hash_t hash; - Py_ssize_t ix; - PyDictObject *mp = (PyDictObject *)op; - PyObject *value; + Py_hash_t hash = _PyObject_HashFast(key); - if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) - return -1; + if (hash == -1) { + return -1; } - ix = _Py_dict_lookup(mp, key, hash, &value); - if (ix == DKIX_ERROR) + + return _PyDict_Contains_KnownHash(op, key, hash); +} + +int +PyDict_ContainsString(PyObject *op, const char *key) +{ + PyObject *key_obj = PyUnicode_FromString(key); + if (key_obj == NULL) { return -1; - return (ix != DKIX_EMPTY && value != NULL); + } + int res = PyDict_Contains(op, key_obj); + Py_DECREF(key_obj); + return res; } /* Internal version of PyDict_Contains used when the hash value is already known */ @@ -3716,10 +4732,20 @@ _PyDict_Contains_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash) PyObject *value; Py_ssize_t ix; +#ifdef Py_GIL_DISABLED + ix = _Py_dict_lookup_threadsafe(mp, key, hash, &value); +#else ix = _Py_dict_lookup(mp, key, hash, &value); +#endif if (ix == DKIX_ERROR) return -1; - return (ix != DKIX_EMPTY && value != NULL); + if (ix != DKIX_EMPTY && value != NULL) { +#ifdef Py_GIL_DISABLED + Py_DECREF(value); +#endif + return 1; + } + return 0; } int @@ -3824,8 +4850,9 @@ dict_vectorcall(PyObject *type, PyObject * const*args, } static PyObject * -dict_iter(PyDictObject *dict) +dict_iter(PyObject *self) { + PyDictObject *dict = (PyDictObject *)self; return dictiter_new(dict, &PyDictIterKey_Type); } @@ -3845,12 +4872,12 @@ PyTypeObject PyDict_Type = { "dict", sizeof(PyDictObject), 0, - (destructor)dict_dealloc, /* tp_dealloc */ + dict_dealloc, /* tp_dealloc */ 0, /* tp_vectorcall_offset */ 0, /* tp_getattr */ 0, /* tp_setattr */ 0, /* tp_as_async */ - (reprfunc)dict_repr, /* tp_repr */ + dict_repr, /* tp_repr */ &dict_as_number, /* tp_as_number */ &dict_as_sequence, /* tp_as_sequence */ &dict_as_mapping, /* tp_as_mapping */ @@ -3868,7 +4895,7 @@ PyTypeObject PyDict_Type = { dict_tp_clear, /* tp_clear */ dict_richcompare, /* tp_richcompare */ 0, /* tp_weaklistoffset */ - (getiterfunc)dict_iter, /* tp_iter */ + dict_iter, /* tp_iter */ 0, /* tp_iternext */ mapp_methods, /* tp_methods */ 0, /* tp_members */ @@ -3893,12 +4920,29 @@ PyDict_GetItemString(PyObject *v, const char *key) PyObject *kv, *rv; kv = PyUnicode_FromString(key); if (kv == NULL) { - PyErr_Clear(); + PyErr_FormatUnraisable( + "Exception ignored in PyDict_GetItemString(); consider using " + "PyDict_GetItemRefString()"); return NULL; } - rv = PyDict_GetItem(v, kv); + rv = dict_getitem(v, kv, + "Exception ignored in PyDict_GetItemString(); consider using " + "PyDict_GetItemRefString()"); Py_DECREF(kv); - return rv; + return rv; // borrowed reference +} + +int +PyDict_GetItemStringRef(PyObject *v, const char *key, PyObject **result) +{ + PyObject *key_obj = PyUnicode_FromString(key); + if (key_obj == NULL) { + *result = NULL; + return -1; + } + int res = PyDict_GetItemRef(v, key_obj, result); + Py_DECREF(key_obj); + return res; } int @@ -3962,22 +5006,24 @@ typedef struct { static PyObject * dictiter_new(PyDictObject *dict, PyTypeObject *itertype) { + Py_ssize_t used; dictiterobject *di; di = PyObject_GC_New(dictiterobject, itertype); if (di == NULL) { return NULL; } di->di_dict = (PyDictObject*)Py_NewRef(dict); - di->di_used = dict->ma_used; - di->len = dict->ma_used; + used = FT_ATOMIC_LOAD_SSIZE_RELAXED(dict->ma_used); + di->di_used = used; + di->len = used; if (itertype == &PyDictRevIterKey_Type || itertype == &PyDictRevIterItem_Type || itertype == &PyDictRevIterValue_Type) { - if (dict->ma_values) { - di->di_pos = dict->ma_used - 1; + if (_PyDict_HasSplitTable(dict)) { + di->di_pos = used - 1; } else { - di->di_pos = dict->ma_keys->dk_nentries - 1; + di->di_pos = load_keys_nentries(dict) - 1; } } else { @@ -3999,8 +5045,9 @@ dictiter_new(PyDictObject *dict, PyTypeObject *itertype) } static void -dictiter_dealloc(dictiterobject *di) +dictiter_dealloc(PyObject *self) { + dictiterobject *di = (dictiterobject *)self; /* bpo-31095: UnTrack is needed before calling any callbacks */ _PyObject_GC_UNTRACK(di); Py_XDECREF(di->di_dict); @@ -4009,19 +5056,21 @@ dictiter_dealloc(dictiterobject *di) } static int -dictiter_traverse(dictiterobject *di, visitproc visit, void *arg) +dictiter_traverse(PyObject *self, visitproc visit, void *arg) { + dictiterobject *di = (dictiterobject *)self; Py_VISIT(di->di_dict); Py_VISIT(di->di_result); return 0; } static PyObject * -dictiter_len(dictiterobject *di, PyObject *Py_UNUSED(ignored)) +dictiter_len(PyObject *self, PyObject *Py_UNUSED(ignored)) { + dictiterobject *di = (dictiterobject *)self; Py_ssize_t len = 0; - if (di->di_dict != NULL && di->di_used == di->di_dict->ma_used) - len = di->len; + if (di->di_dict != NULL && di->di_used == FT_ATOMIC_LOAD_SSIZE_RELAXED(di->di_dict->ma_used)) + len = FT_ATOMIC_LOAD_SSIZE_RELAXED(di->len); return PyLong_FromSize_t(len); } @@ -4029,29 +5078,36 @@ PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); static PyObject * -dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored)); +dictiter_reduce(PyObject *di, PyObject *Py_UNUSED(ignored)); PyDoc_STRVAR(reduce_doc, "Return state information for pickling."); static PyMethodDef dictiter_methods[] = { - {"__length_hint__", _PyCFunction_CAST(dictiter_len), METH_NOARGS, + {"__length_hint__", dictiter_len, METH_NOARGS, length_hint_doc}, - {"__reduce__", _PyCFunction_CAST(dictiter_reduce), METH_NOARGS, + {"__reduce__", dictiter_reduce, METH_NOARGS, reduce_doc}, {NULL, NULL} /* sentinel */ }; +#ifdef Py_GIL_DISABLED + +static int +dictiter_iternext_threadsafe(PyDictObject *d, PyObject *self, + PyObject **out_key, PyObject **out_value); + +#else /* Py_GIL_DISABLED */ + static PyObject* -dictiter_iternextkey(dictiterobject *di) +dictiter_iternextkey_lock_held(PyDictObject *d, PyObject *self) { + dictiterobject *di = (dictiterobject *)self; PyObject *key; Py_ssize_t i; PyDictKeysObject *k; - PyDictObject *d = di->di_dict; - if (d == NULL) - return NULL; assert (PyDict_Check(d)); + ASSERT_DICT_LOCKED(d); if (di->di_used != d->ma_used) { PyErr_SetString(PyExc_RuntimeError, @@ -4063,11 +5119,11 @@ dictiter_iternextkey(dictiterobject *di) i = di->di_pos; k = d->ma_keys; assert(i >= 0); - if (d->ma_values) { + if (_PyDict_HasSplitTable(d)) { if (i >= d->ma_used) goto fail; int index = get_index_from_order(d, i); - key = DK_UNICODE_ENTRIES(k)[index].me_key; + key = LOAD_SHARED_KEY(DK_UNICODE_ENTRIES(k)[index].me_key); assert(d->ma_values->values[index] != NULL); } else { @@ -4109,13 +5165,36 @@ fail: return NULL; } +#endif /* Py_GIL_DISABLED */ + +static PyObject* +dictiter_iternextkey(PyObject *self) +{ + dictiterobject *di = (dictiterobject *)self; + PyDictObject *d = di->di_dict; + + if (d == NULL) + return NULL; + + PyObject *value; +#ifdef Py_GIL_DISABLED + if (dictiter_iternext_threadsafe(d, self, &value, NULL) < 0) { + value = NULL; + } +#else + value = dictiter_iternextkey_lock_held(d, self); +#endif + + return value; +} + PyTypeObject PyDictIterKey_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "dict_keyiterator", /* tp_name */ sizeof(dictiterobject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ - (destructor)dictiter_dealloc, /* tp_dealloc */ + dictiter_dealloc, /* tp_dealloc */ 0, /* tp_vectorcall_offset */ 0, /* tp_getattr */ 0, /* tp_setattr */ @@ -4132,26 +5211,27 @@ PyTypeObject PyDictIterKey_Type = { 0, /* tp_as_buffer */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 0, /* tp_doc */ - (traverseproc)dictiter_traverse, /* tp_traverse */ + dictiter_traverse, /* tp_traverse */ 0, /* tp_clear */ 0, /* tp_richcompare */ 0, /* tp_weaklistoffset */ PyObject_SelfIter, /* tp_iter */ - (iternextfunc)dictiter_iternextkey, /* tp_iternext */ + dictiter_iternextkey, /* tp_iternext */ dictiter_methods, /* tp_methods */ 0, }; +#ifndef Py_GIL_DISABLED + static PyObject * -dictiter_iternextvalue(dictiterobject *di) +dictiter_iternextvalue_lock_held(PyDictObject *d, PyObject *self) { + dictiterobject *di = (dictiterobject *)self; PyObject *value; Py_ssize_t i; - PyDictObject *d = di->di_dict; - if (d == NULL) - return NULL; assert (PyDict_Check(d)); + ASSERT_DICT_LOCKED(d); if (di->di_used != d->ma_used) { PyErr_SetString(PyExc_RuntimeError, @@ -4162,7 +5242,7 @@ dictiter_iternextvalue(dictiterobject *di) i = di->di_pos; assert(i >= 0); - if (d->ma_values) { + if (_PyDict_HasSplitTable(d)) { if (i >= d->ma_used) goto fail; int index = get_index_from_order(d, i); @@ -4208,13 +5288,36 @@ fail: return NULL; } +#endif /* Py_GIL_DISABLED */ + +static PyObject * +dictiter_iternextvalue(PyObject *self) +{ + dictiterobject *di = (dictiterobject *)self; + PyDictObject *d = di->di_dict; + + if (d == NULL) + return NULL; + + PyObject *value; +#ifdef Py_GIL_DISABLED + if (dictiter_iternext_threadsafe(d, self, NULL, &value) < 0) { + value = NULL; + } +#else + value = dictiter_iternextvalue_lock_held(d, self); +#endif + + return value; +} + PyTypeObject PyDictIterValue_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "dict_valueiterator", /* tp_name */ sizeof(dictiterobject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ - (destructor)dictiter_dealloc, /* tp_dealloc */ + dictiter_dealloc, /* tp_dealloc */ 0, /* tp_vectorcall_offset */ 0, /* tp_getattr */ 0, /* tp_setattr */ @@ -4231,41 +5334,42 @@ PyTypeObject PyDictIterValue_Type = { 0, /* tp_as_buffer */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */ 0, /* tp_doc */ - (traverseproc)dictiter_traverse, /* tp_traverse */ + dictiter_traverse, /* tp_traverse */ 0, /* tp_clear */ 0, /* tp_richcompare */ 0, /* tp_weaklistoffset */ PyObject_SelfIter, /* tp_iter */ - (iternextfunc)dictiter_iternextvalue, /* tp_iternext */ + dictiter_iternextvalue, /* tp_iternext */ dictiter_methods, /* tp_methods */ 0, }; -static PyObject * -dictiter_iternextitem(dictiterobject *di) +static int +dictiter_iternextitem_lock_held(PyDictObject *d, PyObject *self, + PyObject **out_key, PyObject **out_value) { - PyObject *key, *value, *result; + dictiterobject *di = (dictiterobject *)self; + PyObject *key, *value; Py_ssize_t i; - PyDictObject *d = di->di_dict; - if (d == NULL) - return NULL; assert (PyDict_Check(d)); + ASSERT_DICT_LOCKED(d); if (di->di_used != d->ma_used) { PyErr_SetString(PyExc_RuntimeError, "dictionary changed size during iteration"); di->di_used = -1; /* Make this state sticky */ - return NULL; + return -1; } - i = di->di_pos; + i = FT_ATOMIC_LOAD_SSIZE_RELAXED(di->di_pos); + assert(i >= 0); - if (d->ma_values) { + if (_PyDict_HasSplitTable(d)) { if (i >= d->ma_used) goto fail; int index = get_index_from_order(d, i); - key = DK_UNICODE_ENTRIES(d->ma_keys)[index].me_key; + key = LOAD_SHARED_KEY(DK_UNICODE_ENTRIES(d->ma_keys)[index].me_key); value = d->ma_values->values[index]; assert(value != NULL); } @@ -4302,33 +5406,222 @@ dictiter_iternextitem(dictiterobject *di) } di->di_pos = i+1; di->len--; - result = di->di_result; - if (Py_REFCNT(result) == 1) { - PyObject *oldkey = PyTuple_GET_ITEM(result, 0); - PyObject *oldvalue = PyTuple_GET_ITEM(result, 1); - PyTuple_SET_ITEM(result, 0, Py_NewRef(key)); - PyTuple_SET_ITEM(result, 1, Py_NewRef(value)); - Py_INCREF(result); - Py_DECREF(oldkey); - Py_DECREF(oldvalue); - // bpo-42536: The GC may have untracked this result tuple. Since we're - // recycling it, make sure it's tracked again: - if (!_PyObject_GC_IS_TRACKED(result)) { - _PyObject_GC_TRACK(result); + if (out_key != NULL) { + *out_key = Py_NewRef(key); + } + if (out_value != NULL) { + *out_value = Py_NewRef(value); + } + return 0; + +fail: + di->di_dict = NULL; + Py_DECREF(d); + return -1; +} + +#ifdef Py_GIL_DISABLED + +// Grabs the key and/or value from the provided locations and if successful +// returns them with an increased reference count. If either one is unsucessful +// nothing is incref'd and returns -1. +static int +acquire_key_value(PyObject **key_loc, PyObject *value, PyObject **value_loc, + PyObject **out_key, PyObject **out_value) +{ + if (out_key) { + *out_key = _Py_TryXGetRef(key_loc); + if (*out_key == NULL) { + return -1; + } + } + + if (out_value) { + if (!_Py_TryIncrefCompare(value_loc, value)) { + if (out_key) { + Py_DECREF(*out_key); + } + return -1; + } + *out_value = value; + } + + return 0; +} + +static int +dictiter_iternext_threadsafe(PyDictObject *d, PyObject *self, + PyObject **out_key, PyObject **out_value) +{ + int res; + dictiterobject *di = (dictiterobject *)self; + Py_ssize_t i; + PyDictKeysObject *k; + + assert (PyDict_Check(d)); + + if (di->di_used != _Py_atomic_load_ssize_relaxed(&d->ma_used)) { + PyErr_SetString(PyExc_RuntimeError, + "dictionary changed size during iteration"); + di->di_used = -1; /* Make this state sticky */ + return -1; + } + + ensure_shared_on_read(d); + + i = _Py_atomic_load_ssize_relaxed(&di->di_pos); + k = _Py_atomic_load_ptr_relaxed(&d->ma_keys); + assert(i >= 0); + if (_PyDict_HasSplitTable(d)) { + PyDictValues *values = _Py_atomic_load_ptr_relaxed(&d->ma_values); + if (values == NULL) { + goto concurrent_modification; + } + + Py_ssize_t used = (Py_ssize_t)_Py_atomic_load_uint8(&values->size); + if (i >= used) { + goto fail; + } + + // We're racing against writes to the order from delete_index_from_values, but + // single threaded can suffer from concurrent modification to those as well and + // can have either duplicated or skipped attributes, so we strive to do no better + // here. + int index = get_index_from_order(d, i); + PyObject *value = _Py_atomic_load_ptr(&values->values[index]); + if (acquire_key_value(&DK_UNICODE_ENTRIES(k)[index].me_key, value, + &values->values[index], out_key, out_value) < 0) { + goto try_locked; } } else { - result = PyTuple_New(2); - if (result == NULL) - return NULL; - PyTuple_SET_ITEM(result, 0, Py_NewRef(key)); - PyTuple_SET_ITEM(result, 1, Py_NewRef(value)); + Py_ssize_t n = _Py_atomic_load_ssize_relaxed(&k->dk_nentries); + if (DK_IS_UNICODE(k)) { + PyDictUnicodeEntry *entry_ptr = &DK_UNICODE_ENTRIES(k)[i]; + PyObject *value; + while (i < n && + (value = _Py_atomic_load_ptr(&entry_ptr->me_value)) == NULL) { + entry_ptr++; + i++; + } + if (i >= n) + goto fail; + + if (acquire_key_value(&entry_ptr->me_key, value, + &entry_ptr->me_value, out_key, out_value) < 0) { + goto try_locked; + } + } + else { + PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i]; + PyObject *value; + while (i < n && + (value = _Py_atomic_load_ptr(&entry_ptr->me_value)) == NULL) { + entry_ptr++; + i++; + } + + if (i >= n) + goto fail; + + if (acquire_key_value(&entry_ptr->me_key, value, + &entry_ptr->me_value, out_key, out_value) < 0) { + goto try_locked; + } + } } - return result; + // We found an element (key), but did not expect it + Py_ssize_t len; + if ((len = _Py_atomic_load_ssize_relaxed(&di->len)) == 0) { + goto concurrent_modification; + } + + _Py_atomic_store_ssize_relaxed(&di->di_pos, i + 1); + _Py_atomic_store_ssize_relaxed(&di->len, len - 1); + return 0; + +concurrent_modification: + PyErr_SetString(PyExc_RuntimeError, + "dictionary keys changed during iteration"); fail: di->di_dict = NULL; Py_DECREF(d); + return -1; + +try_locked: + Py_BEGIN_CRITICAL_SECTION(d); + res = dictiter_iternextitem_lock_held(d, self, out_key, out_value); + Py_END_CRITICAL_SECTION(); + return res; +} + +#endif + +static bool +has_unique_reference(PyObject *op) +{ +#ifdef Py_GIL_DISABLED + return (_Py_IsOwnedByCurrentThread(op) && + op->ob_ref_local == 1 && + _Py_atomic_load_ssize_relaxed(&op->ob_ref_shared) == 0); +#else + return Py_REFCNT(op) == 1; +#endif +} + +static bool +acquire_iter_result(PyObject *result) +{ + if (has_unique_reference(result)) { + Py_INCREF(result); + return true; + } + return false; +} + +static PyObject * +dictiter_iternextitem(PyObject *self) +{ + dictiterobject *di = (dictiterobject *)self; + PyDictObject *d = di->di_dict; + + if (d == NULL) + return NULL; + + PyObject *key, *value; +#ifdef Py_GIL_DISABLED + if (dictiter_iternext_threadsafe(d, self, &key, &value) == 0) { +#else + if (dictiter_iternextitem_lock_held(d, self, &key, &value) == 0) { + +#endif + PyObject *result = di->di_result; + if (acquire_iter_result(result)) { + PyObject *oldkey = PyTuple_GET_ITEM(result, 0); + PyObject *oldvalue = PyTuple_GET_ITEM(result, 1); + PyTuple_SET_ITEM(result, 0, key); + PyTuple_SET_ITEM(result, 1, value); + Py_DECREF(oldkey); + Py_DECREF(oldvalue); + // bpo-42536: The GC may have untracked this result tuple. Since we're + // recycling it, make sure it's tracked again: + if (!_PyObject_GC_IS_TRACKED(result)) { + _PyObject_GC_TRACK(result); + } + } + else { + result = PyTuple_New(2); + if (result == NULL) { + Py_DECREF(key); + Py_DECREF(value); + return NULL; + } + PyTuple_SET_ITEM(result, 0, key); + PyTuple_SET_ITEM(result, 1, value); + } + return result; + } return NULL; } @@ -4338,7 +5631,7 @@ PyTypeObject PyDictIterItem_Type = { sizeof(dictiterobject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ - (destructor)dictiter_dealloc, /* tp_dealloc */ + dictiter_dealloc, /* tp_dealloc */ 0, /* tp_vectorcall_offset */ 0, /* tp_getattr */ 0, /* tp_setattr */ @@ -4355,12 +5648,12 @@ PyTypeObject PyDictIterItem_Type = { 0, /* tp_as_buffer */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 0, /* tp_doc */ - (traverseproc)dictiter_traverse, /* tp_traverse */ + dictiter_traverse, /* tp_traverse */ 0, /* tp_clear */ 0, /* tp_richcompare */ 0, /* tp_weaklistoffset */ PyObject_SelfIter, /* tp_iter */ - (iternextfunc)dictiter_iternextitem, /* tp_iternext */ + dictiter_iternextitem, /* tp_iternext */ dictiter_methods, /* tp_methods */ 0, }; @@ -4369,14 +5662,12 @@ PyTypeObject PyDictIterItem_Type = { /* dictreviter */ static PyObject * -dictreviter_iternext(dictiterobject *di) +dictreviter_iter_lock_held(PyDictObject *d, PyObject *self) { - PyDictObject *d = di->di_dict; + dictiterobject *di = (dictiterobject *)self; - if (d == NULL) { - return NULL; - } assert (PyDict_Check(d)); + ASSERT_DICT_LOCKED(d); if (di->di_used != d->ma_used) { PyErr_SetString(PyExc_RuntimeError, @@ -4392,9 +5683,9 @@ dictreviter_iternext(dictiterobject *di) if (i < 0) { goto fail; } - if (d->ma_values) { + if (_PyDict_HasSplitTable(d)) { int index = get_index_from_order(d, i); - key = DK_UNICODE_ENTRIES(k)[index].me_key; + key = LOAD_SHARED_KEY(DK_UNICODE_ENTRIES(k)[index].me_key); value = d->ma_values->values[index]; assert (value != NULL); } @@ -4467,15 +5758,32 @@ fail: return NULL; } +static PyObject * +dictreviter_iternext(PyObject *self) +{ + dictiterobject *di = (dictiterobject *)self; + PyDictObject *d = di->di_dict; + + if (d == NULL) + return NULL; + + PyObject *value; + Py_BEGIN_CRITICAL_SECTION(d); + value = dictreviter_iter_lock_held(d, self); + Py_END_CRITICAL_SECTION(); + + return value; +} + PyTypeObject PyDictRevIterKey_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "dict_reversekeyiterator", sizeof(dictiterobject), - .tp_dealloc = (destructor)dictiter_dealloc, + .tp_dealloc = dictiter_dealloc, .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, - .tp_traverse = (traverseproc)dictiter_traverse, + .tp_traverse = dictiter_traverse, .tp_iter = PyObject_SelfIter, - .tp_iternext = (iternextfunc)dictreviter_iternext, + .tp_iternext = dictreviter_iternext, .tp_methods = dictiter_methods }; @@ -4495,8 +5803,9 @@ dict___reversed___impl(PyDictObject *self) } static PyObject * -dictiter_reduce(dictiterobject *di, PyObject *Py_UNUSED(ignored)) +dictiter_reduce(PyObject *self, PyObject *Py_UNUSED(ignored)) { + dictiterobject *di = (dictiterobject *)self; /* copy the iterator state */ dictiterobject tmp = *di; Py_XINCREF(tmp.di_dict); @@ -4512,11 +5821,11 @@ PyTypeObject PyDictRevIterItem_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "dict_reverseitemiterator", sizeof(dictiterobject), - .tp_dealloc = (destructor)dictiter_dealloc, + .tp_dealloc = dictiter_dealloc, .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, - .tp_traverse = (traverseproc)dictiter_traverse, + .tp_traverse = dictiter_traverse, .tp_iter = PyObject_SelfIter, - .tp_iternext = (iternextfunc)dictreviter_iternext, + .tp_iternext = dictreviter_iternext, .tp_methods = dictiter_methods }; @@ -4524,11 +5833,11 @@ PyTypeObject PyDictRevIterValue_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "dict_reversevalueiterator", sizeof(dictiterobject), - .tp_dealloc = (destructor)dictiter_dealloc, + .tp_dealloc = dictiter_dealloc, .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, - .tp_traverse = (traverseproc)dictiter_traverse, + .tp_traverse = dictiter_traverse, .tp_iter = PyObject_SelfIter, - .tp_iternext = (iternextfunc)dictreviter_iternext, + .tp_iternext = dictreviter_iternext, .tp_methods = dictiter_methods }; @@ -4539,8 +5848,9 @@ PyTypeObject PyDictRevIterValue_Type = { /* The instance lay-out is the same for all three; but the type differs. */ static void -dictview_dealloc(_PyDictViewObject *dv) +dictview_dealloc(PyObject *self) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; /* bpo-31095: UnTrack is needed before calling any callbacks */ _PyObject_GC_UNTRACK(dv); Py_XDECREF(dv->dv_dict); @@ -4548,18 +5858,20 @@ dictview_dealloc(_PyDictViewObject *dv) } static int -dictview_traverse(_PyDictViewObject *dv, visitproc visit, void *arg) +dictview_traverse(PyObject *self, visitproc visit, void *arg) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; Py_VISIT(dv->dv_dict); return 0; } static Py_ssize_t -dictview_len(_PyDictViewObject *dv) +dictview_len(PyObject *self) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; Py_ssize_t len = 0; if (dv->dv_dict != NULL) - len = dv->dv_dict->ma_used; + len = FT_ATOMIC_LOAD_SSIZE_RELAXED(dv->dv_dict->ma_used); return len; } @@ -4598,7 +5910,7 @@ dictview_mapping(PyObject *view, void *Py_UNUSED(ignored)) { static PyGetSetDef dictview_getset[] = { {"mapping", dictview_mapping, (setter)NULL, - "dictionary that this view refers to", NULL}, + PyDoc_STR("dictionary that this view refers to"), NULL}, {0} }; @@ -4696,8 +6008,9 @@ dictview_richcompare(PyObject *self, PyObject *other, int op) } static PyObject * -dictview_repr(_PyDictViewObject *dv) +dictview_repr(PyObject *self) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; PyObject *seq; PyObject *result = NULL; Py_ssize_t rc; @@ -4721,8 +6034,9 @@ Done: /*** dict_keys ***/ static PyObject * -dictkeys_iter(_PyDictViewObject *dv) +dictkeys_iter(PyObject *self) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; if (dv->dv_dict == NULL) { Py_RETURN_NONE; } @@ -4730,22 +6044,23 @@ dictkeys_iter(_PyDictViewObject *dv) } static int -dictkeys_contains(_PyDictViewObject *dv, PyObject *obj) +dictkeys_contains(PyObject *self, PyObject *obj) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; if (dv->dv_dict == NULL) return 0; return PyDict_Contains((PyObject *)dv->dv_dict, obj); } static PySequenceMethods dictkeys_as_sequence = { - (lenfunc)dictview_len, /* sq_length */ + dictview_len, /* sq_length */ 0, /* sq_concat */ 0, /* sq_repeat */ 0, /* sq_item */ 0, /* sq_slice */ 0, /* sq_ass_item */ 0, /* sq_ass_slice */ - (objobjproc)dictkeys_contains, /* sq_contains */ + dictkeys_contains, /* sq_contains */ }; // Create a set object from dictviews object. @@ -4785,7 +6100,7 @@ dictviews_sub(PyObject *self, PyObject *other) } static int -dictitems_contains(_PyDictViewObject *dv, PyObject *obj); +dictitems_contains(PyObject *dv, PyObject *obj); PyObject * _PyDictView_Intersect(PyObject* self, PyObject *other) @@ -4795,7 +6110,7 @@ _PyDictView_Intersect(PyObject* self, PyObject *other) PyObject *key; Py_ssize_t len_self; int rv; - int (*dict_contains)(_PyDictViewObject *, PyObject *); + objobjproc dict_contains; /* Python interpreter swaps parameters when dict view is on right side of & */ @@ -4805,7 +6120,7 @@ _PyDictView_Intersect(PyObject* self, PyObject *other) self = tmp; } - len_self = dictview_len((_PyDictViewObject *)self); + len_self = dictview_len(self); /* if other is a set and self is smaller than other, reuse set intersection logic */ @@ -4817,7 +6132,7 @@ _PyDictView_Intersect(PyObject* self, PyObject *other) /* if other is another dict view, and it is bigger than self, swap them */ if (PyDictViewSet_Check(other)) { - Py_ssize_t len_other = dictview_len((_PyDictViewObject *)other); + Py_ssize_t len_other = dictview_len(other); if (len_other > len_self) { PyObject *tmp = other; other = self; @@ -4847,7 +6162,7 @@ _PyDictView_Intersect(PyObject* self, PyObject *other) } while ((key = PyIter_Next(it)) != NULL) { - rv = dict_contains((_PyDictViewObject *)self, key); + rv = dict_contains(self, key); if (rv < 0) { goto error; } @@ -4888,14 +6203,12 @@ dictviews_or(PyObject* self, PyObject *other) } static PyObject * -dictitems_xor(PyObject *self, PyObject *other) +dictitems_xor_lock_held(PyObject *d1, PyObject *d2) { - assert(PyDictItems_Check(self)); - assert(PyDictItems_Check(other)); - PyObject *d1 = (PyObject *)((_PyDictViewObject *)self)->dv_dict; - PyObject *d2 = (PyObject *)((_PyDictViewObject *)other)->dv_dict; + ASSERT_DICT_LOCKED(d1); + ASSERT_DICT_LOCKED(d2); - PyObject *temp_dict = PyDict_Copy(d1); + PyObject *temp_dict = copy_lock_held(d1); if (temp_dict == NULL) { return NULL; } @@ -4973,6 +6286,22 @@ error: return NULL; } +static PyObject * +dictitems_xor(PyObject *self, PyObject *other) +{ + assert(PyDictItems_Check(self)); + assert(PyDictItems_Check(other)); + PyObject *d1 = (PyObject *)((_PyDictViewObject *)self)->dv_dict; + PyObject *d2 = (PyObject *)((_PyDictViewObject *)other)->dv_dict; + + PyObject *res; + Py_BEGIN_CRITICAL_SECTION2(d1, d2); + res = dictitems_xor_lock_held(d1, d2); + Py_END_CRITICAL_SECTION2(); + + return res; +} + static PyObject* dictviews_xor(PyObject* self, PyObject *other) { @@ -5021,7 +6350,7 @@ dictviews_isdisjoint(PyObject *self, PyObject *other) PyObject *item = NULL; if (self == other) { - if (dictview_len((_PyDictViewObject *)self) == 0) + if (dictview_len(self) == 0) Py_RETURN_TRUE; else Py_RETURN_FALSE; @@ -5030,7 +6359,7 @@ dictviews_isdisjoint(PyObject *self, PyObject *other) /* Iterate over the shorter object (only if other is a set, * because PySequence_Contains may be expensive otherwise): */ if (PyAnySet_Check(other) || PyDictViewSet_Check(other)) { - Py_ssize_t len_self = dictview_len((_PyDictViewObject *)self); + Py_ssize_t len_self = dictview_len(self); Py_ssize_t len_other = PyObject_Size(other); if (len_other == -1) return NULL; @@ -5068,15 +6397,15 @@ dictviews_isdisjoint(PyObject *self, PyObject *other) PyDoc_STRVAR(isdisjoint_doc, "Return True if the view and the given iterable have a null intersection."); -static PyObject* dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)); +static PyObject* dictkeys_reversed(PyObject *dv, PyObject *Py_UNUSED(ignored)); PyDoc_STRVAR(reversed_keys_doc, "Return a reverse iterator over the dict keys."); static PyMethodDef dictkeys_methods[] = { - {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O, + {"isdisjoint", dictviews_isdisjoint, METH_O, isdisjoint_doc}, - {"__reversed__", _PyCFunction_CAST(dictkeys_reversed), METH_NOARGS, + {"__reversed__", dictkeys_reversed, METH_NOARGS, reversed_keys_doc}, {NULL, NULL} /* sentinel */ }; @@ -5087,12 +6416,12 @@ PyTypeObject PyDictKeys_Type = { sizeof(_PyDictViewObject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ - (destructor)dictview_dealloc, /* tp_dealloc */ + dictview_dealloc, /* tp_dealloc */ 0, /* tp_vectorcall_offset */ 0, /* tp_getattr */ 0, /* tp_setattr */ 0, /* tp_as_async */ - (reprfunc)dictview_repr, /* tp_repr */ + dictview_repr, /* tp_repr */ &dictviews_as_number, /* tp_as_number */ &dictkeys_as_sequence, /* tp_as_sequence */ 0, /* tp_as_mapping */ @@ -5104,25 +6433,33 @@ PyTypeObject PyDictKeys_Type = { 0, /* tp_as_buffer */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 0, /* tp_doc */ - (traverseproc)dictview_traverse, /* tp_traverse */ + dictview_traverse, /* tp_traverse */ 0, /* tp_clear */ dictview_richcompare, /* tp_richcompare */ 0, /* tp_weaklistoffset */ - (getiterfunc)dictkeys_iter, /* tp_iter */ + dictkeys_iter, /* tp_iter */ 0, /* tp_iternext */ dictkeys_methods, /* tp_methods */ .tp_getset = dictview_getset, }; +/*[clinic input] +dict.keys + +Return a set-like object providing a view on the dict's keys. +[clinic start generated code]*/ + static PyObject * -dictkeys_new(PyObject *dict, PyObject *Py_UNUSED(ignored)) +dict_keys_impl(PyDictObject *self) +/*[clinic end generated code: output=aac2830c62990358 input=42f48a7a771212a7]*/ { - return _PyDictView_New(dict, &PyDictKeys_Type); + return _PyDictView_New((PyObject *)self, &PyDictKeys_Type); } static PyObject * -dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) +dictkeys_reversed(PyObject *self, PyObject *Py_UNUSED(ignored)) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; if (dv->dv_dict == NULL) { Py_RETURN_NONE; } @@ -5132,8 +6469,9 @@ dictkeys_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) /*** dict_items ***/ static PyObject * -dictitems_iter(_PyDictViewObject *dv) +dictitems_iter(PyObject *self) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; if (dv->dv_dict == NULL) { Py_RETURN_NONE; } @@ -5141,8 +6479,9 @@ dictitems_iter(_PyDictViewObject *dv) } static int -dictitems_contains(_PyDictViewObject *dv, PyObject *obj) +dictitems_contains(PyObject *self, PyObject *obj) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; int result; PyObject *key, *value, *found; if (dv->dv_dict == NULL) @@ -5151,38 +6490,34 @@ dictitems_contains(_PyDictViewObject *dv, PyObject *obj) return 0; key = PyTuple_GET_ITEM(obj, 0); value = PyTuple_GET_ITEM(obj, 1); - found = PyDict_GetItemWithError((PyObject *)dv->dv_dict, key); - if (found == NULL) { - if (PyErr_Occurred()) - return -1; - return 0; + result = PyDict_GetItemRef((PyObject *)dv->dv_dict, key, &found); + if (result == 1) { + result = PyObject_RichCompareBool(found, value, Py_EQ); + Py_DECREF(found); } - Py_INCREF(found); - result = PyObject_RichCompareBool(found, value, Py_EQ); - Py_DECREF(found); return result; } static PySequenceMethods dictitems_as_sequence = { - (lenfunc)dictview_len, /* sq_length */ + dictview_len, /* sq_length */ 0, /* sq_concat */ 0, /* sq_repeat */ 0, /* sq_item */ 0, /* sq_slice */ 0, /* sq_ass_item */ 0, /* sq_ass_slice */ - (objobjproc)dictitems_contains, /* sq_contains */ + dictitems_contains, /* sq_contains */ }; -static PyObject* dictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)); +static PyObject* dictitems_reversed(PyObject *dv, PyObject *Py_UNUSED(ignored)); PyDoc_STRVAR(reversed_items_doc, "Return a reverse iterator over the dict items."); static PyMethodDef dictitems_methods[] = { - {"isdisjoint", (PyCFunction)dictviews_isdisjoint, METH_O, + {"isdisjoint", dictviews_isdisjoint, METH_O, isdisjoint_doc}, - {"__reversed__", (PyCFunction)dictitems_reversed, METH_NOARGS, + {"__reversed__", dictitems_reversed, METH_NOARGS, reversed_items_doc}, {NULL, NULL} /* sentinel */ }; @@ -5193,12 +6528,12 @@ PyTypeObject PyDictItems_Type = { sizeof(_PyDictViewObject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ - (destructor)dictview_dealloc, /* tp_dealloc */ + dictview_dealloc, /* tp_dealloc */ 0, /* tp_vectorcall_offset */ 0, /* tp_getattr */ 0, /* tp_setattr */ 0, /* tp_as_async */ - (reprfunc)dictview_repr, /* tp_repr */ + dictview_repr, /* tp_repr */ &dictviews_as_number, /* tp_as_number */ &dictitems_as_sequence, /* tp_as_sequence */ 0, /* tp_as_mapping */ @@ -5210,25 +6545,33 @@ PyTypeObject PyDictItems_Type = { 0, /* tp_as_buffer */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 0, /* tp_doc */ - (traverseproc)dictview_traverse, /* tp_traverse */ + dictview_traverse, /* tp_traverse */ 0, /* tp_clear */ dictview_richcompare, /* tp_richcompare */ 0, /* tp_weaklistoffset */ - (getiterfunc)dictitems_iter, /* tp_iter */ + dictitems_iter, /* tp_iter */ 0, /* tp_iternext */ dictitems_methods, /* tp_methods */ .tp_getset = dictview_getset, }; +/*[clinic input] +dict.items + +Return a set-like object providing a view on the dict's items. +[clinic start generated code]*/ + static PyObject * -dictitems_new(PyObject *dict, PyObject *Py_UNUSED(ignored)) +dict_items_impl(PyDictObject *self) +/*[clinic end generated code: output=88c7db7150c7909a input=87c822872eb71f5a]*/ { - return _PyDictView_New(dict, &PyDictItems_Type); + return _PyDictView_New((PyObject *)self, &PyDictItems_Type); } static PyObject * -dictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) +dictitems_reversed(PyObject *self, PyObject *Py_UNUSED(ignored)) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; if (dv->dv_dict == NULL) { Py_RETURN_NONE; } @@ -5238,8 +6581,9 @@ dictitems_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) /*** dict_values ***/ static PyObject * -dictvalues_iter(_PyDictViewObject *dv) +dictvalues_iter(PyObject *self) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; if (dv->dv_dict == NULL) { Py_RETURN_NONE; } @@ -5247,7 +6591,7 @@ dictvalues_iter(_PyDictViewObject *dv) } static PySequenceMethods dictvalues_as_sequence = { - (lenfunc)dictview_len, /* sq_length */ + dictview_len, /* sq_length */ 0, /* sq_concat */ 0, /* sq_repeat */ 0, /* sq_item */ @@ -5257,13 +6601,13 @@ static PySequenceMethods dictvalues_as_sequence = { (objobjproc)0, /* sq_contains */ }; -static PyObject* dictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)); +static PyObject* dictvalues_reversed(PyObject *dv, PyObject *Py_UNUSED(ignored)); PyDoc_STRVAR(reversed_values_doc, "Return a reverse iterator over the dict values."); static PyMethodDef dictvalues_methods[] = { - {"__reversed__", (PyCFunction)dictvalues_reversed, METH_NOARGS, + {"__reversed__", dictvalues_reversed, METH_NOARGS, reversed_values_doc}, {NULL, NULL} /* sentinel */ }; @@ -5274,12 +6618,12 @@ PyTypeObject PyDictValues_Type = { sizeof(_PyDictViewObject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ - (destructor)dictview_dealloc, /* tp_dealloc */ + dictview_dealloc, /* tp_dealloc */ 0, /* tp_vectorcall_offset */ 0, /* tp_getattr */ 0, /* tp_setattr */ 0, /* tp_as_async */ - (reprfunc)dictview_repr, /* tp_repr */ + dictview_repr, /* tp_repr */ 0, /* tp_as_number */ &dictvalues_as_sequence, /* tp_as_sequence */ 0, /* tp_as_mapping */ @@ -5291,25 +6635,33 @@ PyTypeObject PyDictValues_Type = { 0, /* tp_as_buffer */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 0, /* tp_doc */ - (traverseproc)dictview_traverse, /* tp_traverse */ + dictview_traverse, /* tp_traverse */ 0, /* tp_clear */ 0, /* tp_richcompare */ 0, /* tp_weaklistoffset */ - (getiterfunc)dictvalues_iter, /* tp_iter */ + dictvalues_iter, /* tp_iter */ 0, /* tp_iternext */ dictvalues_methods, /* tp_methods */ .tp_getset = dictview_getset, }; +/*[clinic input] +dict.values + +Return an object providing a view on the dict's values. +[clinic start generated code]*/ + static PyObject * -dictvalues_new(PyObject *dict, PyObject *Py_UNUSED(ignored)) +dict_values_impl(PyDictObject *self) +/*[clinic end generated code: output=ce9f2e9e8a959dd4 input=b46944f85493b230]*/ { - return _PyDictView_New(dict, &PyDictValues_Type); + return _PyDictView_New((PyObject *)self, &PyDictValues_Type); } static PyObject * -dictvalues_reversed(_PyDictViewObject *dv, PyObject *Py_UNUSED(ignored)) +dictvalues_reversed(PyObject *self, PyObject *Py_UNUSED(ignored)) { + _PyDictViewObject *dv = (_PyDictViewObject *)self; if (dv->dv_dict == NULL) { Py_RETURN_NONE; } @@ -5337,63 +6689,43 @@ _PyDict_NewKeysForClass(void) return keys; } -#define CACHED_KEYS(tp) (((PyHeapTypeObject*)tp)->ht_cached_keys) - -static int -init_inline_values(PyObject *obj, PyTypeObject *tp) +void +_PyObject_InitInlineValues(PyObject *obj, PyTypeObject *tp) { assert(tp->tp_flags & Py_TPFLAGS_HEAPTYPE); - // assert(type->tp_dictoffset > 0); -- TO DO Update this assert. + assert(tp->tp_flags & Py_TPFLAGS_INLINE_VALUES); assert(tp->tp_flags & Py_TPFLAGS_MANAGED_DICT); PyDictKeysObject *keys = CACHED_KEYS(tp); assert(keys != NULL); + OBJECT_STAT_INC(inline_values); +#ifdef Py_GIL_DISABLED + Py_ssize_t usable = _Py_atomic_load_ssize_relaxed(&keys->dk_usable); + if (usable > 1) { + LOCK_KEYS(keys); + if (keys->dk_usable > 1) { + _Py_atomic_store_ssize(&keys->dk_usable, keys->dk_usable - 1); + } + UNLOCK_KEYS(keys); + } +#else if (keys->dk_usable > 1) { keys->dk_usable--; } +#endif size_t size = shared_keys_usable_size(keys); - PyDictValues *values = new_values(size); - if (values == NULL) { - PyErr_NoMemory(); - return -1; - } - assert(((uint8_t *)values)[-1] >= (size + 2)); - ((uint8_t *)values)[-2] = 0; + PyDictValues *values = _PyObject_InlineValues(obj); + assert(size < 256); + values->capacity = (uint8_t)size; + values->size = 0; + values->embedded = 1; + values->valid = 1; for (size_t i = 0; i < size; i++) { values->values[i] = NULL; } - _PyDictOrValues_SetValues(_PyObject_DictOrValuesPointer(obj), values); - return 0; -} - -int -_PyObject_InitializeDict(PyObject *obj) -{ - PyInterpreterState *interp = _PyInterpreterState_GET(); - PyTypeObject *tp = Py_TYPE(obj); - if (tp->tp_dictoffset == 0) { - return 0; - } - if (tp->tp_flags & Py_TPFLAGS_MANAGED_DICT) { - OBJECT_STAT_INC(new_values); - return init_inline_values(obj, tp); - } - PyObject *dict; - if (_PyType_HasFeature(tp, Py_TPFLAGS_HEAPTYPE) && CACHED_KEYS(tp)) { - dictkeys_incref(CACHED_KEYS(tp)); - dict = new_dict_with_shared_keys(interp, CACHED_KEYS(tp)); - } - else { - dict = PyDict_New(); - } - if (dict == NULL) { - return -1; - } - PyObject **dictptr = _PyObject_ComputedDictPointer(obj); - *dictptr = dict; - return 0; + _PyObject_ManagedDictPointer(obj)->dict = NULL; } -static PyObject * +static PyDictObject * make_dict_from_instance_attributes(PyInterpreterState *interp, PyDictKeysObject *keys, PyDictValues *values) { @@ -5408,82 +6740,245 @@ make_dict_from_instance_attributes(PyInterpreterState *interp, track += _PyObject_GC_MAY_BE_TRACKED(val); } } - PyObject *res = new_dict(interp, keys, values, used, 0); + PyDictObject *res = (PyDictObject *)new_dict(interp, keys, values, used, 0); if (track && res) { _PyObject_GC_TRACK(res); } return res; } -PyObject * -_PyObject_MakeDictFromInstanceAttributes(PyObject *obj, PyDictValues *values) +PyDictObject * +_PyObject_MaterializeManagedDict_LockHeld(PyObject *obj) { - PyInterpreterState *interp = _PyInterpreterState_GET(); - PyDictKeysObject *keys = CACHED_KEYS(Py_TYPE(obj)); + ASSERT_WORLD_STOPPED_OR_OBJ_LOCKED(obj); + OBJECT_STAT_INC(dict_materialized_on_request); - return make_dict_from_instance_attributes(interp, keys, values); + + PyDictValues *values = _PyObject_InlineValues(obj); + PyDictObject *dict; + if (values->valid) { + PyInterpreterState *interp = _PyInterpreterState_GET(); + PyDictKeysObject *keys = CACHED_KEYS(Py_TYPE(obj)); + dict = make_dict_from_instance_attributes(interp, keys, values); + } + else { + dict = (PyDictObject *)PyDict_New(); + } + FT_ATOMIC_STORE_PTR_RELEASE(_PyObject_ManagedDictPointer(obj)->dict, + dict); + return dict; +} + +PyDictObject * +_PyObject_MaterializeManagedDict(PyObject *obj) +{ + PyDictObject *dict = _PyObject_GetManagedDict(obj); + if (dict != NULL) { + return dict; + } + + Py_BEGIN_CRITICAL_SECTION(obj); + +#ifdef Py_GIL_DISABLED + dict = _PyObject_GetManagedDict(obj); + if (dict != NULL) { + // We raced with another thread creating the dict + goto exit; + } +#endif + dict = _PyObject_MaterializeManagedDict_LockHeld(obj); + +#ifdef Py_GIL_DISABLED +exit: +#endif + Py_END_CRITICAL_SECTION(); + return dict; } int -_PyObject_StoreInstanceAttribute(PyObject *obj, PyDictValues *values, +_PyDict_SetItem_LockHeld(PyDictObject *dict, PyObject *name, PyObject *value) +{ + if (value == NULL) { + Py_hash_t hash = _PyObject_HashFast(name); + if (hash == -1) { + return -1; + } + return delitem_knownhash_lock_held((PyObject *)dict, name, hash); + } else { + return setitem_lock_held(dict, name, value); + } +} + +// Called with either the object's lock or the dict's lock held +// depending on whether or not a dict has been materialized for +// the object. +static int +store_instance_attr_lock_held(PyObject *obj, PyDictValues *values, PyObject *name, PyObject *value) { - PyInterpreterState *interp = _PyInterpreterState_GET(); PyDictKeysObject *keys = CACHED_KEYS(Py_TYPE(obj)); assert(keys != NULL); assert(values != NULL); - assert(Py_TYPE(obj)->tp_flags & Py_TPFLAGS_MANAGED_DICT); + assert(Py_TYPE(obj)->tp_flags & Py_TPFLAGS_INLINE_VALUES); Py_ssize_t ix = DKIX_EMPTY; + PyDictObject *dict = _PyObject_GetManagedDict(obj); + assert(dict == NULL || ((PyDictObject *)dict)->ma_values == values); if (PyUnicode_CheckExact(name)) { - ix = insert_into_dictkeys(keys, name); - } - if (ix == DKIX_EMPTY) { + Py_hash_t hash = unicode_get_hash(name); + if (hash == -1) { + hash = PyUnicode_Type.tp_hash(name); + assert(hash != -1); + } + + ix = insert_split_key(keys, name, hash); + #ifdef Py_STATS - if (PyUnicode_CheckExact(name)) { - if (shared_keys_usable_size(keys) == SHARED_KEYS_MAX_SIZE) { - OBJECT_STAT_INC(dict_materialized_too_big); + if (ix == DKIX_EMPTY) { + if (PyUnicode_CheckExact(name)) { + if (shared_keys_usable_size(keys) == SHARED_KEYS_MAX_SIZE) { + OBJECT_STAT_INC(dict_materialized_too_big); + } + else { + OBJECT_STAT_INC(dict_materialized_new_key); + } } else { - OBJECT_STAT_INC(dict_materialized_new_key); + OBJECT_STAT_INC(dict_materialized_str_subclass); } } - else { - OBJECT_STAT_INC(dict_materialized_str_subclass); - } #endif - PyObject *dict = make_dict_from_instance_attributes( - interp, keys, values); + } + + if (ix == DKIX_EMPTY) { + int res; if (dict == NULL) { - return -1; - } - _PyObject_DictOrValuesPointer(obj)->dict = dict; - if (value == NULL) { - return PyDict_DelItem(dict, name); - } - else { - return PyDict_SetItem(dict, name, value); + // Make the dict but don't publish it in the object + // so that no one else will see it. + dict = make_dict_from_instance_attributes(PyInterpreterState_Get(), keys, values); + if (dict == NULL || + _PyDict_SetItem_LockHeld(dict, name, value) < 0) { + Py_XDECREF(dict); + return -1; + } + + FT_ATOMIC_STORE_PTR_RELEASE(_PyObject_ManagedDictPointer(obj)->dict, + (PyDictObject *)dict); + return 0; } + + _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(dict); + + res = _PyDict_SetItem_LockHeld(dict, name, value); + return res; } + PyObject *old_value = values->values[ix]; - values->values[ix] = Py_XNewRef(value); - if (old_value == NULL) { - if (value == NULL) { - PyErr_Format(PyExc_AttributeError, - "'%.100s' object has no attribute '%U'", - Py_TYPE(obj)->tp_name, name); - return -1; + if (old_value == NULL && value == NULL) { + PyErr_Format(PyExc_AttributeError, + "'%.100s' object has no attribute '%U'", + Py_TYPE(obj)->tp_name, name); + return -1; + } + + if (dict) { + PyInterpreterState *interp = _PyInterpreterState_GET(); + PyDict_WatchEvent event = (old_value == NULL ? PyDict_EVENT_ADDED : + value == NULL ? PyDict_EVENT_DELETED : + PyDict_EVENT_MODIFIED); + _PyDict_NotifyEvent(interp, event, dict, name, value); + if (value) { + MAINTAIN_TRACKING(dict, name, value); } + } + + FT_ATOMIC_STORE_PTR_RELEASE(values->values[ix], Py_XNewRef(value)); + + if (old_value == NULL) { _PyDictValues_AddToInsertionOrder(values, ix); + if (dict) { + assert(dict->ma_values == values); + STORE_USED(dict, dict->ma_used + 1); + } } else { if (value == NULL) { delete_index_from_values(values, ix); + if (dict) { + assert(dict->ma_values == values); + STORE_USED(dict, dict->ma_used - 1); + } } Py_DECREF(old_value); } return 0; } +static inline int +store_instance_attr_dict(PyObject *obj, PyDictObject *dict, PyObject *name, PyObject *value) +{ + PyDictValues *values = _PyObject_InlineValues(obj); + int res; + Py_BEGIN_CRITICAL_SECTION(dict); + if (dict->ma_values == values) { + res = store_instance_attr_lock_held(obj, values, name, value); + } + else { + res = _PyDict_SetItem_LockHeld(dict, name, value); + } + Py_END_CRITICAL_SECTION(); + return res; +} + +int +_PyObject_StoreInstanceAttribute(PyObject *obj, PyObject *name, PyObject *value) +{ + PyDictValues *values = _PyObject_InlineValues(obj); + if (!FT_ATOMIC_LOAD_UINT8(values->valid)) { + PyDictObject *dict = _PyObject_GetManagedDict(obj); + if (dict == NULL) { + dict = (PyDictObject *)PyObject_GenericGetDict(obj, NULL); + if (dict == NULL) { + return -1; + } + int res = store_instance_attr_dict(obj, dict, name, value); + Py_DECREF(dict); + return res; + } + return store_instance_attr_dict(obj, dict, name, value); + } + +#ifdef Py_GIL_DISABLED + // We have a valid inline values, at least for now... There are two potential + // races with having the values become invalid. One is the dictionary + // being detached from the object. The other is if someone is inserting + // into the dictionary directly and therefore causing it to resize. + // + // If we haven't materialized the dictionary yet we lock on the object, which + // will also be used to prevent the dictionary from being materialized while + // we're doing the insertion. If we race and the dictionary gets created + // then we'll need to release the object lock and lock the dictionary to + // prevent resizing. + PyDictObject *dict = _PyObject_GetManagedDict(obj); + if (dict == NULL) { + int res; + Py_BEGIN_CRITICAL_SECTION(obj); + dict = _PyObject_GetManagedDict(obj); + + if (dict == NULL) { + res = store_instance_attr_lock_held(obj, values, name, value); + } + Py_END_CRITICAL_SECTION(); + + if (dict == NULL) { + return res; + } + } + return store_instance_attr_dict(obj, dict, name, value); +#else + return store_instance_attr_lock_held(obj, values, name, value); +#endif +} + /* Sanity check for managed dicts */ #if 0 #define CHECK(val) assert(val); if (!(val)) { return 0; } @@ -5493,9 +6988,9 @@ _PyObject_ManagedDictValidityCheck(PyObject *obj) { PyTypeObject *tp = Py_TYPE(obj); CHECK(tp->tp_flags & Py_TPFLAGS_MANAGED_DICT); - PyDictOrValues *dorv_ptr = _PyObject_DictOrValuesPointer(obj); - if (_PyDictOrValues_IsValues(*dorv_ptr)) { - PyDictValues *values = _PyDictOrValues_GetValues(*dorv_ptr); + PyManagedDictPointer *managed_dict = _PyObject_ManagedDictPointer(obj); + if (_PyManagedDictPointer_IsValues(*managed_dict)) { + PyDictValues *values = _PyManagedDictPointer_GetValues(*managed_dict); int size = ((uint8_t *)values)[-2]; int count = 0; PyDictKeysObject *keys = CACHED_KEYS(tp); @@ -5507,27 +7002,87 @@ _PyObject_ManagedDictValidityCheck(PyObject *obj) CHECK(size == count); } else { - if (dorv_ptr->dict != NULL) { - CHECK(PyDict_Check(dorv_ptr->dict)); + if (managed_dict->dict != NULL) { + CHECK(PyDict_Check(managed_dict->dict)); } } return 1; } #endif -PyObject * -_PyObject_GetInstanceAttribute(PyObject *obj, PyDictValues *values, - PyObject *name) +// Attempts to get an instance attribute from the inline values. Returns true +// if successful, or false if the caller needs to lookup in the dictionary. +bool +_PyObject_TryGetInstanceAttribute(PyObject *obj, PyObject *name, PyObject **attr) { assert(PyUnicode_CheckExact(name)); + PyDictValues *values = _PyObject_InlineValues(obj); + if (!FT_ATOMIC_LOAD_UINT8(values->valid)) { + return false; + } + PyDictKeysObject *keys = CACHED_KEYS(Py_TYPE(obj)); assert(keys != NULL); - Py_ssize_t ix = _PyDictKeys_StringLookup(keys, name); + Py_ssize_t ix = _PyDictKeys_StringLookupSplit(keys, name); if (ix == DKIX_EMPTY) { - return NULL; + *attr = NULL; + return true; } + +#ifdef Py_GIL_DISABLED + PyObject *value = _Py_atomic_load_ptr_acquire(&values->values[ix]); + if (value == NULL || _Py_TryIncrefCompare(&values->values[ix], value)) { + *attr = value; + return true; + } + + PyDictObject *dict = _PyObject_GetManagedDict(obj); + if (dict == NULL) { + // No dict, lock the object to prevent one from being + // materialized... + bool success = false; + Py_BEGIN_CRITICAL_SECTION(obj); + + dict = _PyObject_GetManagedDict(obj); + if (dict == NULL) { + // Still no dict, we can read from the values + assert(values->valid); + value = values->values[ix]; + *attr = _Py_XNewRefWithLock(value); + success = true; + } + + Py_END_CRITICAL_SECTION(); + + if (success) { + return true; + } + } + + // We have a dictionary, we'll need to lock it to prevent + // the values from being resized. + assert(dict != NULL); + + bool success; + Py_BEGIN_CRITICAL_SECTION(dict); + + if (dict->ma_values == values && FT_ATOMIC_LOAD_UINT8(values->valid)) { + value = _Py_atomic_load_ptr_relaxed(&values->values[ix]); + *attr = _Py_XNewRefWithLock(value); + success = true; + } else { + // Caller needs to lookup from the dictionary + success = false; + } + + Py_END_CRITICAL_SECTION(); + + return success; +#else PyObject *value = values->values[ix]; - return Py_XNewRef(value); + *attr = Py_XNewRef(value); + return true; +#endif } int @@ -5537,121 +7092,257 @@ _PyObject_IsInstanceDictEmpty(PyObject *obj) if (tp->tp_dictoffset == 0) { return 1; } - PyObject *dict; - if (tp->tp_flags & Py_TPFLAGS_MANAGED_DICT) { - PyDictOrValues dorv = *_PyObject_DictOrValuesPointer(obj); - if (_PyDictOrValues_IsValues(dorv)) { + PyDictObject *dict; + if (tp->tp_flags & Py_TPFLAGS_INLINE_VALUES) { + PyDictValues *values = _PyObject_InlineValues(obj); + if (FT_ATOMIC_LOAD_UINT8(values->valid)) { PyDictKeysObject *keys = CACHED_KEYS(tp); for (Py_ssize_t i = 0; i < keys->dk_nentries; i++) { - if (_PyDictOrValues_GetValues(dorv)->values[i] != NULL) { + if (FT_ATOMIC_LOAD_PTR_RELAXED(values->values[i]) != NULL) { return 0; } } return 1; } - dict = _PyDictOrValues_GetDict(dorv); + dict = _PyObject_GetManagedDict(obj); + } + else if (tp->tp_flags & Py_TPFLAGS_MANAGED_DICT) { + dict = _PyObject_GetManagedDict(obj); } else { PyObject **dictptr = _PyObject_ComputedDictPointer(obj); - dict = *dictptr; + dict = (PyDictObject *)*dictptr; } if (dict == NULL) { return 1; } - return ((PyDictObject *)dict)->ma_used == 0; + return FT_ATOMIC_LOAD_SSIZE_RELAXED(((PyDictObject *)dict)->ma_used) == 0; } -void -_PyObject_FreeInstanceAttributes(PyObject *self) +int +PyObject_VisitManagedDict(PyObject *obj, visitproc visit, void *arg) { - PyTypeObject *tp = Py_TYPE(self); - assert(Py_TYPE(self)->tp_flags & Py_TPFLAGS_MANAGED_DICT); - PyDictOrValues dorv = *_PyObject_DictOrValuesPointer(self); - if (!_PyDictOrValues_IsValues(dorv)) { - return; + PyTypeObject *tp = Py_TYPE(obj); + if((tp->tp_flags & Py_TPFLAGS_MANAGED_DICT) == 0) { + return 0; } - PyDictValues *values = _PyDictOrValues_GetValues(dorv); - PyDictKeysObject *keys = CACHED_KEYS(tp); - for (Py_ssize_t i = 0; i < keys->dk_nentries; i++) { - Py_XDECREF(values->values[i]); + PyDictObject *dict = _PyObject_ManagedDictPointer(obj)->dict; + if (dict != NULL) { + // GH-130327: If there's a managed dictionary available, we should + // *always* traverse it. The dict is responsible for traversing the + // inline values if it points to them. + Py_VISIT(dict); + } + else if (tp->tp_flags & Py_TPFLAGS_INLINE_VALUES) { + PyDictValues *values = _PyObject_InlineValues(obj); + if (values->valid) { + for (Py_ssize_t i = 0; i < values->capacity; i++) { + Py_VISIT(values->values[i]); + } + } + } + return 0; +} + +static void +set_dict_inline_values(PyObject *obj, PyDictObject *new_dict) +{ + _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(obj); + + PyDictValues *values = _PyObject_InlineValues(obj); + + Py_XINCREF(new_dict); + FT_ATOMIC_STORE_PTR(_PyObject_ManagedDictPointer(obj)->dict, new_dict); + + if (values->valid) { + FT_ATOMIC_STORE_UINT8(values->valid, 0); + for (Py_ssize_t i = 0; i < values->capacity; i++) { + Py_CLEAR(values->values[i]); + } } - free_values(values); } int -_PyObject_VisitManagedDict(PyObject *obj, visitproc visit, void *arg) +_PyObject_SetManagedDict(PyObject *obj, PyObject *new_dict) { + assert(Py_TYPE(obj)->tp_flags & Py_TPFLAGS_MANAGED_DICT); + assert(_PyObject_InlineValuesConsistencyCheck(obj)); + int err = 0; PyTypeObject *tp = Py_TYPE(obj); - if((tp->tp_flags & Py_TPFLAGS_MANAGED_DICT) == 0) { - return 0; - } - assert(tp->tp_dictoffset); - PyDictOrValues dorv = *_PyObject_DictOrValuesPointer(obj); - if (_PyDictOrValues_IsValues(dorv)) { - PyDictValues *values = _PyDictOrValues_GetValues(dorv); - PyDictKeysObject *keys = CACHED_KEYS(tp); - for (Py_ssize_t i = 0; i < keys->dk_nentries; i++) { - Py_VISIT(values->values[i]); + if (tp->tp_flags & Py_TPFLAGS_INLINE_VALUES) { + PyDictObject *dict = _PyObject_GetManagedDict(obj); + if (dict == NULL) { +#ifdef Py_GIL_DISABLED + Py_BEGIN_CRITICAL_SECTION(obj); + + dict = _PyObject_ManagedDictPointer(obj)->dict; + if (dict == NULL) { + set_dict_inline_values(obj, (PyDictObject *)new_dict); + } + + Py_END_CRITICAL_SECTION(); + + if (dict == NULL) { + return 0; + } +#else + set_dict_inline_values(obj, (PyDictObject *)new_dict); + return 0; +#endif + } + + Py_BEGIN_CRITICAL_SECTION2(dict, obj); + + // We've locked dict, but the actual dict could have changed + // since we locked it. + dict = _PyObject_ManagedDictPointer(obj)->dict; + err = _PyDict_DetachFromObject(dict, obj); + if (err == 0) { + FT_ATOMIC_STORE_PTR(_PyObject_ManagedDictPointer(obj)->dict, + (PyDictObject *)Py_XNewRef(new_dict)); + } + Py_END_CRITICAL_SECTION2(); + + if (err == 0) { + Py_XDECREF(dict); } } else { - PyObject *dict = _PyDictOrValues_GetDict(dorv); - Py_VISIT(dict); + PyDictObject *dict; + + Py_BEGIN_CRITICAL_SECTION(obj); + + dict = _PyObject_ManagedDictPointer(obj)->dict; + + FT_ATOMIC_STORE_PTR(_PyObject_ManagedDictPointer(obj)->dict, + (PyDictObject *)Py_XNewRef(new_dict)); + + Py_END_CRITICAL_SECTION(); + + Py_XDECREF(dict); } - return 0; + assert(_PyObject_InlineValuesConsistencyCheck(obj)); + return err; } void -_PyObject_ClearManagedDict(PyObject *obj) +PyObject_ClearManagedDict(PyObject *obj) { - PyTypeObject *tp = Py_TYPE(obj); - if((tp->tp_flags & Py_TPFLAGS_MANAGED_DICT) == 0) { - return; + if (_PyObject_SetManagedDict(obj, NULL) < 0) { + PyErr_WriteUnraisable(NULL); } - PyDictOrValues *dorv_ptr = _PyObject_DictOrValuesPointer(obj); - if (_PyDictOrValues_IsValues(*dorv_ptr)) { - PyDictValues *values = _PyDictOrValues_GetValues(*dorv_ptr); - PyDictKeysObject *keys = CACHED_KEYS(tp); - for (Py_ssize_t i = 0; i < keys->dk_nentries; i++) { - Py_CLEAR(values->values[i]); +} + +int +_PyDict_DetachFromObject(PyDictObject *mp, PyObject *obj) +{ + ASSERT_WORLD_STOPPED_OR_OBJ_LOCKED(obj); + assert(_PyObject_ManagedDictPointer(obj)->dict == mp); + assert(_PyObject_InlineValuesConsistencyCheck(obj)); + + if (FT_ATOMIC_LOAD_PTR_RELAXED(mp->ma_values) != _PyObject_InlineValues(obj)) { + return 0; + } + + // We could be called with an unlocked dict when the caller knows the + // values are already detached, so we assert after inline values check. + ASSERT_WORLD_STOPPED_OR_OBJ_LOCKED(mp); + assert(mp->ma_values->embedded == 1); + assert(mp->ma_values->valid == 1); + assert(Py_TYPE(obj)->tp_flags & Py_TPFLAGS_INLINE_VALUES); + + PyDictValues *values = copy_values(mp->ma_values); + + if (values == NULL) { + /* Out of memory. Clear the dict */ + PyInterpreterState *interp = _PyInterpreterState_GET(); + PyDictKeysObject *oldkeys = mp->ma_keys; + set_keys(mp, Py_EMPTY_KEYS); + dictkeys_decref(interp, oldkeys, IS_DICT_SHARED(mp)); + STORE_USED(mp, 0); + PyErr_NoMemory(); + return -1; + } + mp->ma_values = values; + + FT_ATOMIC_STORE_UINT8(_PyObject_InlineValues(obj)->valid, 0); + + assert(_PyObject_InlineValuesConsistencyCheck(obj)); + ASSERT_CONSISTENT(mp); + return 0; +} + +static inline PyObject * +ensure_managed_dict(PyObject *obj) +{ + PyDictObject *dict = _PyObject_GetManagedDict(obj); + if (dict == NULL) { + PyTypeObject *tp = Py_TYPE(obj); + if ((tp->tp_flags & Py_TPFLAGS_INLINE_VALUES) && + FT_ATOMIC_LOAD_UINT8(_PyObject_InlineValues(obj)->valid)) { + dict = _PyObject_MaterializeManagedDict(obj); + } + else { +#ifdef Py_GIL_DISABLED + // Check again that we're not racing with someone else creating the dict + Py_BEGIN_CRITICAL_SECTION(obj); + dict = _PyObject_GetManagedDict(obj); + if (dict != NULL) { + goto done; + } +#endif + dict = (PyDictObject *)new_dict_with_shared_keys(_PyInterpreterState_GET(), + CACHED_KEYS(tp)); + FT_ATOMIC_STORE_PTR_RELEASE(_PyObject_ManagedDictPointer(obj)->dict, + (PyDictObject *)dict); + +#ifdef Py_GIL_DISABLED +done: + Py_END_CRITICAL_SECTION(); +#endif } - dorv_ptr->dict = NULL; - free_values(values); } - else { - PyObject *dict = dorv_ptr->dict; - if (dict) { - dorv_ptr->dict = NULL; - Py_DECREF(dict); + return (PyObject *)dict; +} + +static inline PyObject * +ensure_nonmanaged_dict(PyObject *obj, PyObject **dictptr) +{ + PyDictKeysObject *cached; + + PyObject *dict = FT_ATOMIC_LOAD_PTR_ACQUIRE(*dictptr); + if (dict == NULL) { +#ifdef Py_GIL_DISABLED + Py_BEGIN_CRITICAL_SECTION(obj); + dict = *dictptr; + if (dict != NULL) { + goto done; } +#endif + PyTypeObject *tp = Py_TYPE(obj); + if (_PyType_HasFeature(tp, Py_TPFLAGS_HEAPTYPE) && (cached = CACHED_KEYS(tp))) { + PyInterpreterState *interp = _PyInterpreterState_GET(); + assert(!_PyType_HasFeature(tp, Py_TPFLAGS_INLINE_VALUES)); + dict = new_dict_with_shared_keys(interp, cached); + } + else { + dict = PyDict_New(); + } + FT_ATOMIC_STORE_PTR_RELEASE(*dictptr, dict); +#ifdef Py_GIL_DISABLED +done: + Py_END_CRITICAL_SECTION(); +#endif } + return dict; } PyObject * PyObject_GenericGetDict(PyObject *obj, void *context) { - PyObject *dict; - PyInterpreterState *interp = _PyInterpreterState_GET(); PyTypeObject *tp = Py_TYPE(obj); if (_PyType_HasFeature(tp, Py_TPFLAGS_MANAGED_DICT)) { - PyDictOrValues *dorv_ptr = _PyObject_DictOrValuesPointer(obj); - if (_PyDictOrValues_IsValues(*dorv_ptr)) { - PyDictValues *values = _PyDictOrValues_GetValues(*dorv_ptr); - OBJECT_STAT_INC(dict_materialized_on_request); - dict = make_dict_from_instance_attributes( - interp, CACHED_KEYS(tp), values); - if (dict != NULL) { - dorv_ptr->dict = dict; - } - } - else { - dict = _PyDictOrValues_GetDict(*dorv_ptr); - if (dict == NULL) { - dictkeys_incref(CACHED_KEYS(tp)); - dict = new_dict_with_shared_keys(interp, CACHED_KEYS(tp)); - dorv_ptr->dict = dict; - } - } + return Py_XNewRef(ensure_managed_dict(obj)); } else { PyObject **dictptr = _PyObject_ComputedDictPointer(obj); @@ -5660,63 +7351,28 @@ PyObject_GenericGetDict(PyObject *obj, void *context) "This object has no __dict__"); return NULL; } - dict = *dictptr; - if (dict == NULL) { - PyTypeObject *tp = Py_TYPE(obj); - if (_PyType_HasFeature(tp, Py_TPFLAGS_HEAPTYPE) && CACHED_KEYS(tp)) { - dictkeys_incref(CACHED_KEYS(tp)); - *dictptr = dict = new_dict_with_shared_keys( - interp, CACHED_KEYS(tp)); - } - else { - *dictptr = dict = PyDict_New(); - } - } + + return Py_XNewRef(ensure_nonmanaged_dict(obj, dictptr)); } - return Py_XNewRef(dict); } int -_PyObjectDict_SetItem(PyTypeObject *tp, PyObject **dictptr, +_PyObjectDict_SetItem(PyTypeObject *tp, PyObject *obj, PyObject **dictptr, PyObject *key, PyObject *value) { PyObject *dict; int res; - PyDictKeysObject *cached; - PyInterpreterState *interp = _PyInterpreterState_GET(); assert(dictptr != NULL); - if ((tp->tp_flags & Py_TPFLAGS_HEAPTYPE) && (cached = CACHED_KEYS(tp))) { - assert(dictptr != NULL); - dict = *dictptr; - if (dict == NULL) { - dictkeys_incref(cached); - dict = new_dict_with_shared_keys(interp, cached); - if (dict == NULL) - return -1; - *dictptr = dict; - } - if (value == NULL) { - res = PyDict_DelItem(dict, key); - } - else { - res = PyDict_SetItem(dict, key, value); - } - } else { - dict = *dictptr; - if (dict == NULL) { - dict = PyDict_New(); - if (dict == NULL) - return -1; - *dictptr = dict; - } - if (value == NULL) { - res = PyDict_DelItem(dict, key); - } else { - res = PyDict_SetItem(dict, key, value); - } + dict = ensure_nonmanaged_dict(obj, dictptr); + if (dict == NULL) { + return -1; } + + Py_BEGIN_CRITICAL_SECTION(dict); + res = _PyDict_SetItem_LockHeld((PyDictObject *)dict, key, value); ASSERT_CONSISTENT(dict); + Py_END_CRITICAL_SECTION(); return res; } @@ -5724,7 +7380,7 @@ void _PyDictKeys_DecRef(PyDictKeysObject *keys) { PyInterpreterState *interp = _PyInterpreterState_GET(); - dictkeys_decref(interp, keys); + dictkeys_decref(interp, keys, false); } uint32_t _PyDictKeys_GetVersionForCurrentState(PyInterpreterState *interp, @@ -5790,7 +7446,8 @@ PyDict_AddWatcher(PyDict_WatchCallback callback) { PyInterpreterState *interp = _PyInterpreterState_GET(); - for (int i = 0; i < DICT_MAX_WATCHERS; i++) { + /* Start at 2, as 0 and 1 are reserved for CPython */ + for (int i = 2; i < DICT_MAX_WATCHERS; i++) { if (!interp->dict_state.watchers[i]) { interp->dict_state.watchers[i] = callback; return i; @@ -5840,16 +7497,32 @@ _PyDict_SendEvent(int watcher_bits, // unraisablehook keep a reference to it, so we don't pass the // dict as context, just an informative string message. Dict // repr can call arbitrary code, so we invent a simpler version. - PyObject *context = PyUnicode_FromFormat( - "%s watcher callback for <dict at %p>", + PyErr_FormatUnraisable( + "Exception ignored in %s watcher callback for <dict at %p>", dict_event_name(event), mp); - if (context == NULL) { - context = Py_NewRef(Py_None); - } - PyErr_WriteUnraisable(context); - Py_DECREF(context); } } watcher_bits >>= 1; } } + +#ifndef NDEBUG +static int +_PyObject_InlineValuesConsistencyCheck(PyObject *obj) +{ + if ((Py_TYPE(obj)->tp_flags & Py_TPFLAGS_INLINE_VALUES) == 0) { + return 1; + } + assert(Py_TYPE(obj)->tp_flags & Py_TPFLAGS_MANAGED_DICT); + PyDictObject *dict = _PyObject_GetManagedDict(obj); + if (dict == NULL) { + return 1; + } + if (dict->ma_values == _PyObject_InlineValues(obj) || + _PyObject_InlineValues(obj)->valid == 0) { + return 1; + } + assert(0); + return 0; +} +#endif |