8000 gh-112075: Lock when inserting into shared keys · DinoV/cpython@01e9517 · GitHub
[go: up one dir, main page]
Skip to content

Commit 01e9517

Browse files
colesburyDinoV
colesbury
authored and
DinoV
committed
pythongh-112075: Lock when inserting into shared keys
1 parent 9ab26e8 commit 01e9517

File tree

1 file changed

+113
-188
lines changed

1 file changed

+113
-188
lines changed

‎Objects/dictobject.c

Lines changed: 113 additions & 188 deletions
Original file line numberDiff line numberDiff line change
@@ -1680,31 +1680,6 @@ insertion_resize(PyInterpreterState *interp, PyDictObject *mp, int unicode)
16801680
return dictresize(interp, mp, calculate_log2_keysize(GROWTH_RATE(mp)), unicode);
16811681
}
16821682

1683-
static Py_ssize_t
1684-
insert_into_splitdictkeys(PyDictKeysObject *keys, PyObject *name, Py_hash_t hash)
1685-
{
1686-
assert(PyUnicode_CheckExact(name));
1687-
ASSERT_KEYS_LOCKED(keys);
1688-
1689-
Py_ssize_t ix = unicodekeys_lookup_unicode(keys, name, hash);
1690-
if (ix == DKIX_EMPTY) {
1691-
if (keys->dk_usable <= 0) {
1692-
return DKIX_EMPTY;
1693-
}
1694-
/* Insert into new slot. */
1695-
keys->dk_version = 0;
1696-
Py_ssize_t hashpos = find_empty_slot(keys, hash);
1697-
ix = keys->dk_nentries;
1698-
PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(keys)[ix];
1699-
dictkeys_set_index(keys, hashpos, ix);
1700-
assert(ep->me_key == NULL);
1701-
ep->me_key = Py_NewRef(name);
1702-
E864 split_keys_entry_added(keys);
1703-
}
1704-
assert (ix < SHARED_KEYS_MAX_SIZE);
1705-
return ix;
1706-
}
1707-
17081683
static inline int
17091684
insert_combined_dict(PyInterpreterState *interp, PyDictObject *mp,
17101685
Py_hash_t hash, PyObject *key, PyObject *value)
@@ -1738,76 +1713,57 @@ insert_combined_dict(PyInterpreterState *interp, PyDictObject *mp,
17381713
return 0;
17391714
}
17401715

1741-
// Performs an insert into a split dictionary when the key is not already
1742-
// present. Returns 0 on success, -1 on error, and 1 if a race occured and
1743-
// the key got added by another thread. Consumes key and value references
1744-
// if the key and value are successfully inserted.
1745-
static inline int
1746-
insert_split_dict(PyInterpreterState *interp, PyDictObject *mp,
1747-
Py_hash_t hash, PyObject *key, PyObject *value,
1748-
Py_ssize_t *ix, PyObject **result)
1716+
static int
1717+
insert_split_key(PyDictKeysObject *keys, PyObject *key, Py_hash_t hash)
17491718
{
1750-
ASSERT_DICT_LOCKED(mp);
1719+
assert(PyUnicode_CheckExact(key));
1720+
Py_ssize_t ix;
17511721

1752-
PyDictKeysObject *keys = mp->ma_keys;
1753-
LOCK_KEYS(keys);
17541722

17551723
#ifdef Py_GIL_DISABLED
1756-
PyObject *existing_value;
1757-
// We could have raced between our lookup before and the insert,
1758-
// so we need to lookup again with the keys locked
1759-
*ix = splitdict_lookup_keys_lock_held(mp, key, hash,
1760-
&existing_value);
1761-
if (*ix >= 0) {
1762-
UNLOCK_KEYS(keys);
1763-
*result = existing_value;
1764-
// There was a race with someone else inserting the key, the
1765-
// caller needs to handle it as they may not want to replace
1766-
// the existing value.
1767-
return 1;
1724+
ix = unicodekeys_lookup_unicode_threadsafe(keys, key, hash);
1725+
if (ix >= 0) {
1726+
return ix;
17681727
}
17691728
#endif
17701729

1771-
uint64_t new_version = _PyDict_NotifyEvent(
1772-
interp, PyDict_EVENT_ADDED, mp, key, value);
1773-
keys->dk_version = 0;
1774-
if (keys->dk_usable <= 0) {
1775-
/* Need to resize. */
1776-
UNLOCK_KEYS(keys);
1777-
int ins = insertion_resize(interp, mp, 1);
1778-
if (ins < 0) {
1779-
return -1;
1780-
}
1781-
assert(!_PyDict_HasSplitTable(mp));
1782-
if (insert_combined_dict(interp, mp, hash, key, value) < 0) {
1783-
*result = NULL;
1784-
return -1;
1785-
}
1730+
LOCK_KEYS(keys);
1731+
ix = unicodekeys_lookup_unicode(keys, key, hash);
1732+
if (ix == DKIX_EMPTY && keys->dk_usable > 0) {
1733+
// Insert into new slot
1734+
keys->dk_version = 0;
1735+
Py_ssize_t hashpos = find_empty_slot(keys, hash);
1736+
ix = keys->dk_nentries;
1737+
dictkeys_set_index(keys, hashpos, ix);
1738+
PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(keys)[ix];
1739+
STORE_SHARED_KEY(ep->me_key, Py_NewRef(key));
1740+
split_keys_entry_added(keys);
1741+
}
1742+
assert (ix < SHARED_KEYS_MAX_SIZE);
1743+
UNLOCK_KEYS(keys);
1744+
return ix;
1745+
}
17861746

1787-
*result = value;
1747+
static void
1748+
insert_split_value(PyInterpreterState *interp, PyDictObject *mp, PyObject *key, PyObject *value, Py_ssize_t ix)
1749+
{
1750+
assert(PyUnicode_CheckExact(key));
1751+
MAINTAIN_TRACKING(mp, key, value);
1752+
PyObject *old_value = mp->ma_values->values[ix];
1753+
if (old_value == NULL) {
1754+
uint64_t new_version = _PyDict_NotifyEvent(interp, PyDict_EVENT_ADDED, mp, key, value);
1755+
STORE_SPLIT_VALUE(mp, ix, Py_NewRef(value));
1756+
_PyDictValues_AddToInsertionOrder(mp->ma_values, ix);
1757+
mp->ma_used++;
17881758
mp->ma_version_tag = new_version;
1789-
return 0;
17901759
}
1791-
1792-
Py_ssize_t hashpos = find_empty_slot(keys, hash);
1793-
dictkeys_set_index(keys, hashpos, keys->dk_nentries);
1794-
1795-
PyDictUnicodeEntry *ep;
1796-
ep = &DK_UNICODE_ENTRIES(keys)[keys->dk_nentries];
1797-
STORE_SHARED_KEY(ep->me_key, key);
1798-
1799-
Py_ssize_t index = keys->dk_nentries;
1800-
_PyDictValues_AddToInsertionOrder(mp->ma_values, index);
1801-
assert (mp->ma_values->values[index] == NULL);
1802-
STORE_SPLIT_VALUE(mp, index, value);
1803-
1804-
split_keys_entry_added(keys);
1805-
assert(keys->dk_usable >= 0);
1806-
1807-
UNLOCK_KEYS(keys);
1808-
*result = value;
1809-
mp->ma_version_tag = new_version;
1810-
return 0;
1760+
else {
1761+
uint64_t new_version = _PyDict_NotifyEvent(interp, PyDict_EVENT_MODIFIED, mp, key, value);
1762+
STORE_SPLIT_VALUE(mp, ix, Py_NewRef(value));
1763+
mp->ma_version_tag = new_version;
1764+
Py_DECREF(old_value);
1765+
}
1766+
ASSERT_CONSISTENT(mp);
18111767
}
18121768

18131769
/*
@@ -1830,62 +1786,55 @@ insertdict(PyInterpreterState *interp, PyDictObject *mp,
18301786
assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL);
18311787
}
18321788

1789+
if (_PyDict_HasSplitTable(mp)) {
1790+
Py_ssize_t ix = insert_split_key(mp->ma_keys, key, hash);
1791+
if (ix != DKIX_EMPTY) {
1792+
insert_split_value(interp, mp, key, value, ix);
1793+
Py_DECREF(key);
1794+
Py_DECREF(value);
1795+
return 0;
1796+
}
1797+
1798+
/* No space in shared keys. Resize and continue below. */
1799+
if (insertion_resize(interp, mp, 1) < 0) {
1800+
goto Fail;
1801+
}
1802+
}
1803+
18331804
Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &old_value);
18341805
if (ix == DKIX_ERROR)
18351806
goto Fail;
18361807

18371808
MAINTAIN_TRACKING(mp, key, value);
18381809

18391810
if (ix == DKIX_EMPTY) {
1840-
if (!_PyDict_HasSplitTable(mp)) {
1841-
uint64_t new_version = _PyDict_NotifyEvent(
1842-
interp, PyDict_EVENT_ADDED, mp, key, value);
1843-
/* Insert into new slot. */
1844-
mp->ma_keys->dk_version = 0;
1845-
if (insert_combined_dict(interp, mp, hash, key, value) < 0) {
1846-
goto Fail;
1847-
}
1848-
mp->ma_version_tag = new_version;
1849-
}
1850-
else {
1851-
int res = insert_split_dict(interp, mp, hash, key,
1852-
value, &ix, &old_value);
1853-
if (res < 0) {
1854-
return -1;
1855-
}
1856-
#ifdef Py_GIL_DISABLED
1857-
else if (res == 1) {
1858-
goto insert_on_split_race;
1859-
}
1860-
#endif
1811+
assert(!_PyDict_HasSplitTable(mp));
1812+
uint64_t new_version = _PyDict_NotifyEv 57AE ent(
1813+
interp, PyDict_EVENT_ADDED, mp, key, value);
1814+
/* Insert into new slot. */
1815+
mp->ma_keys->dk_version = 0;
1816+
assert(old_value == NULL);
1817+
if (insert_combined_dict(interp, mp, hash, key, value) < 0) {
1818+
goto Fail;
18611819
}
1862-
1820+
mp->ma_version_tag = new_version;
18631821
mp->ma_used++;
18641822
ASSERT_CONSISTENT(mp);
18651823
return 0;
18661824
}
18671825

1868-
#ifdef Py_GIL_DISABLED
1869-
insert_on_split_race:
1870-
#endif
18711826
if (old_value != value) {
18721827
uint64_t new_version = _PyDict_NotifyEvent(
18731828
interp, PyDict_EVENT_MODIFIED, mp, key, value);
1874-
if (_PyDict_HasSplitTable(mp)) {
1875-
STORE_SPLIT_VALUE(mp, ix, value);
1876-
if (old_value == NULL) {
1877-
_PyDictValues_AddToInsertionOrder(mp->ma_values, ix);
1878-
mp->ma_used++;
1879-
}
1829+
assert(old_value != NULL);
1830+
assert(!_PyDict_HasSplitTable(mp));
1831+
if (DK_IS_UNICODE(mp->ma_keys)) {
1832+
PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[ix];
1833+
STORE_VALUE(ep, value);
18801834
}
18811835
else {
1882-
assert(old_value != NULL);
1883-
if (DK_IS_UNICODE(mp->ma_keys)) {
1884-
DK_UNICODE_ENTRIES(mp->ma_keys)[ix].me_value = value;
1885-
}
1886-
else {
1887-
DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
1888-
}
1836+
PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix];
1837+
STORE_VALUE(ep, value);
18891838
}
18901839
mp->ma_version_tag = new_version;
18911840
}
@@ -4294,6 +4243,29 @@ dict_setdefault_ref_lock_held(PyObject *d, PyObject *key, PyObject *default_valu
42944243
}
42954244
}
42964245

4246+
if (_PyDict_HasSplitTable(mp)) {
4247+
Py_ssize_t ix = insert_split_key(mp->ma_keys, key, hash);
4248+
if (ix != DKIX_EMPTY) {
4249+
PyObject *value = mp->ma_values->values[ix];
4250+
int already_present = value != NULL;
4251+
if (!already_present) {
4252+
insert_split_value(interp, mp, key, default_value, ix);
4253+
value = default_value;
4254+
}
4255+
if (result) {
4256+
*result = incref_result ? Py_NewRef(value) : value;
4257+
}
4258+
return already_present;
4259+
}
4260+
4261+
/* No space in shared keys. Resize and continue below. */
4262+
if (insertion_resize(interp, mp, 1) < 0) {
4263+
goto error;
4264+
}
4265+
}
4266+
4267+
assert(!_PyDict_HasSplitTable(mp));
4268+
42974269
Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &value);
42984270
if (ix == DKIX_ERROR) {
42994271
if (result) {
@@ -4303,79 +4275,43 @@ dict_setdefault_ref_lock_held(PyObject *d, PyObject *key, PyObject *default_valu
43034275
}
43044276

43054277
if (ix == DKIX_EMPTY) {
4278+
assert(!_PyDict_HasSplitTable(mp));
4279+
uint64_t new_version = _PyDict_NotifyEvent(
4280+
interp, PyDict_EVENT_ADDED, mp, key, default_value);
4281+
mp->ma_keys->dk_version = 0;
43064282
value = default_value;
43074283

4308-
if (!_PyDict_HasSplitTable(mp)) {
4309-
uint64_t new_version = _PyDict_NotifyEvent(
4310-
interp, PyDict_EVENT_ADDED, mp, key, default_value);
4311-
mp->ma_keys->dk_version = 0;
4312-
if (insert_combined_dict(interp, mp, hash, Py_NewRef(key), Py_NewRef(value)) < 0) {
4313-
Py_DECREF(key);
4314-
Py_DECREF(value);
4315-
if (result) {
4316-
*result = NULL;
4317-
}
4318-
return -1;
4319-
}
4320-
mp->ma_version_tag = new_version;
4321-
}
4322-
else {
4323-
int res = insert_split_dict(interp, mp, hash, Py_NewRef(key),
4324-
Py_NewRef(default_value), &ix, &value);
4325-
if (res) {
4326-
Py_DECREF(key);
4327-
Py_DECREF(value);
4328-
if (res < 0) {
4329-
if (result) {
4330-
*result = NULL;
4331-
}
4332-
return -1;
4333-
}
4334-
4335-
#ifdef Py_GIL_DISABLED
4336-
// Raced with another thread inserting
4337-
goto insert_on_split_race;
4338-
#endif
4284+
if (insert_combined_dict(interp, mp, hash, Py_NewRef(key), Py_NewRef(value)) < 0) {
4285+
Py_DECREF(key);
4286+
Py_DECREF(value);
4287+
if (result) {
4288+
*result = NULL;
43394289
}
43404290
}
43414291

43424292
MAINTAIN_TRACKING(mp, key, value);
43434293
mp->ma_used++;
4344-
assert(mp->ma_keys->dk_usable >= 0);
4345-
ASSERT_CONSISTENT(mp);
4346-
if (result) {
4347-
*result = incref_result ? Py_NewRef(value) : value;
4348-
}
4349-
return 0;
4350-
}
4351-
4352-
#ifdef Py_GIL_DISABLED
4353-
insert_on_split_race:
4354-
#endif
4355-
if (value == NULL) {
4356-
uint64_t new_version;
4357-
new_version = _PyDict_NotifyEvent(
4358-
interp, PyDict_EVENT_ADDED, mp, key, default_value);
4359-
value = default_value;
4360-
assert(_PyDict_HasSplitTable(mp));
4361-
assert(mp->ma_values->values[ix] == NULL);
4362-
MAINTAIN_TRACKING(mp, key, value);
4363-
STORE_SPLIT_VALUE(mp, ix, Py_NewRef(value));
4364-
_PyDictValues_AddToInsertionOrder(mp->ma_values, ix);
4365-
mp->ma_used++;
43664294
mp->ma_version_tag = new_version;
4295+
assert(mp->ma_keys->dk_usable >= 0);
43674296
ASSERT_CONSISTENT(mp);
43684297
if (result) {
43694298
*result = incref_result ? Py_NewRef(value) : value;
43704299
}
43714300
return 0;
43724301
}
43734302

4303+
assert(value != NULL);
43744304
ASSERT_CONSISTENT(mp);
43754305
if (result) {
43764306
*result = incref_result ? Py_NewRef(value) : value;
43774307
}
43784308
return 1;
4309+
4310+
error:
4311+
if (result) {
4312+
*result = NULL;
4313+
}
4314+
return -1;
43794315
}
43804316

43814317
int
@@ -6830,18 +6766,7 @@ store_instance_attr_lock_held(PyObject *obj, PyDictValues *values,
68306766
assert(hash != -1);
68316767
}
68326768

6833-
#ifdef Py_GIL_DISABLED
6834-
// Try a thread-safe lookup to see if the index is already allocated
6835-
ix = unicodekeys_lookup_unicode_threadsafe(keys, name, hash);
6836-
if (ix == DKIX_EMPTY || ix == DKIX_KEY_CHANGED) {
6837-
// Lock keys and do insert
6838-
LOCK_KEYS(keys);
6839-
ix = insert_into_splitdictkeys(keys, name, hash);
6840-
UNLOCK_KEYS(keys);
6841-
}
6842-
#else
6843-
ix = insert_into_splitdictkeys(keys, name, hash);
6844-
#endif
6769+
ix = insert_split_key(keys, name, hash);
68456770

68466771
#ifdef Py_STATS
68476772
if (ix == DKIX_EMPTY) {

0 commit comments

Comments
 (0)
0