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

Commit 002ca04

Browse files
colesburyDinoV
colesbury
authored and
DinoV
committed
gh-112075: Lock when inserting into shared keys
1 parent 1272d68 commit 002ca04

File tree

1 file changed

+113
-190
lines changed

1 file changed

+113
-190
lines changed

‎Objects/dictobject.c

Lines changed: 113 additions & 190 deletions
< 57AE /tr>
Original file line numberDiff line numberDiff line change
@@ -1681,31 +1681,6 10000 @@ insertion_resize(PyInterpreterState *interp, PyDictObject *mp, int unicode)
16811681
return dictresize(interp, mp, calculate_log2_keysize(GROWTH_RATE(mp)), unicode);
16821682
}
16831683

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

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

1753-
PyDictKeysObject *keys = mp->ma_keys;
1754-
LOCK_KEYS(keys);
17551723

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

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

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

18141770
/*
@@ -1831,64 +1787,55 @@ insertdict(PyInterpreterState *interp, PyDictObject *mp,
18311787
assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL);
18321788
}
18331789

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

18381809
MAINTAIN_TRACKING(mp, key, value);
18391810

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

1869-
#ifdef Py_GIL_DISABLED
1870-
insert_on_split_race:
1871-
#endif
18721827
if (old_value != value) {
18731828
uint64_t new_version = _PyDict_NotifyEvent(
18741829
interp, PyDict_EVENT_MODIFIED, mp, key, value);
1875-
if (_PyDict_HasSplitTable(mp)) {
1876-
STORE_SPLIT_VALUE(mp, ix, value);
1877-
if (old_value == NULL) {
1878-
_PyDictValues_AddToInsertionOrder(mp->ma_values, ix);
1879-
mp->ma_used++;
1880-
}
1830+
assert(old_value != NULL);
1831+
assert(!_PyDict_HasSplitTable(mp));
1832+
if (DK_IS_UNICODE(mp->ma_keys)) {
1833+
PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[ix];
1834+
STORE_VALUE(ep, value);
18811835
}
18821836
else {
1883-
assert(old_value != NULL);
1884-
if (DK_IS_UNICODE(mp->ma_keys)) {
1885-
PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[ix];
1886-
STORE_VALUE(ep, value);
1887-
}
1888-
else {
1889-
PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix];
1890-
STORE_VALUE(ep, value);
1891-
}
1837+
PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix];
1838+
STORE_VALUE(ep, value);
18921839
}
18931840
mp->ma_version_tag = new_version;
18941841
}
@@ -4297,6 +4244,29 @@ dict_setdefault_ref_lock_held(PyObject *d, PyObject *key, PyObject *default_valu
42974244
}
42984245
}
42994246

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

43084278
if (ix == DKIX_EMPTY) {
4279+
assert(!_PyDict_HasSplitTable(mp));
4280+
uint64_t new_version = _PyDict_NotifyEvent(
4281+
interp, PyDict_EVENT_ADDED, mp, key, default_value);
4282+
mp->ma_keys->dk_version = 0;
43094283
value = default_value;
43104284

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

43454293
MAINTAIN_TRACKING(mp, key, value);
43464294
mp->ma_used++;
4347-
assert(mp->ma_keys->dk_usable >= 0);
4348-
ASSERT_CONSISTENT(mp);
4349-
if (result) {
4350-
*result = incref_result ? Py_NewRef(value) : value;
4351-
}
4352-
return 0;
4353-
}
4354-
4355-
#ifdef Py_GIL_DISABLED
4356-
insert_on_split_race:
4357-
#endif
4358-
if (value == NULL) {
4359-
uint64_t new_version;
4360-
new_version = _PyDict_NotifyEvent(
4361-
interp, PyDict_EVENT_ADDED, mp, key, default_value);
4362-
value = default_value;
4363-
assert(_PyDict_HasSplitTable(mp));
4364-
assert(mp->ma_values->values[ix] == NULL);
4365-
MAINTAIN_TRACKING(mp, key, value);
4366-
STORE_SPLIT_VALUE(mp, ix, Py_NewRef(value));
4367-
_PyDictValues_AddToInsertionOrder(mp->ma_values, ix);
4368-
mp->ma_used++;
43694295
mp->ma_version_tag = new_version;
4296+
assert(mp->ma_keys->dk_usable >= 0);
43704297
ASSERT_CONSISTENT(mp);
43714298
if (result) {
43724299
*result = incref_result ? Py_NewRef(value) : value;
43734300
}
43744301
return 0;
43754302
}
43764303

4304+
assert(value != NULL);
43774305
ASSERT_CONSISTENT(mp);
43784306
if (result) {
43794307
*result = incref_result ? Py_NewRef(value) : value;
43804308
}
43814309
return 1;
4310+
4311+
error:
4312+
if (result) {
4313+
*result = NULL;
4314+
}
4315+
return -1;
43824316
}
43834317

43844318
int
@@ -6833,18 +6767,7 @@ store_instance_attr_lock_held(PyObject *obj, PyDictValues *values,
68336767
assert(hash != -1);
68346768
}
68356769

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

68496772
#ifdef Py_STATS
68506773
if (ix == DKIX_EMPTY) {

0 commit comments

Comments
 (0)
0