Skip to content

gh-112087: Make list_{slice, ass_slice, subscript} to be threadsafe #116233

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
corona10 merged 12 commits into from
Mar 5, 2024
Merged

gh-112087: Make list_{slice, ass_slice, subscript} to be threadsafe #116233

Changes from 2 commits
Commits
Show all changes
12 commits
Select commit Hold shift + click to select a range
d9ffc53
gh-112087: Make list_{slice, ass_slice, subscript} to be threadsafe
corona10 Mar 2, 2024
cab2d99
Remove unnecessary atomic operations
corona10 Mar 4, 2024
8b0120d
Update
corona10 Mar 4, 2024
1e19253
Address code review
corona10 Mar 5, 2024
c25ca79
nit
corona10 Mar 5, 2024
1ed3329
Change name
corona10 Mar 5, 2024
033c141
Fix
corona10 Mar 5, 2024
12529a8
Remove inline
corona10 Mar 5, 2024
3335211
fix
corona10 Mar 5, 2024
11b3017
Address code review
corona10 Mar 5, 2024
9ac76ca
Address code review
corona10 Mar 5, 2024
6c037d4
Add test case
corona10 Mar 5, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
155 changes: 95 additions & 60 deletions Objects/listobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -514,30 +514,33 @@ list_item(PyObject *aa, Py_ssize_t i)
return item;
}

static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
Comment thread
colesbury marked this conversation as resolved.
static inline PyObject *
list_slice_impl(PyListObject *a, Py_ssize_t ilow, Py_ssize_t len)
Comment thread
corona10 marked this conversation as resolved.
Outdated
{
PyListObject *np;
PyObject **src, **dest;
Py_ssize_t i, len;
len = ihigh - ilow;
if (len <= 0) {
return PyList_New(0);
}
np = (PyListObject *) list_new_prealloc(len);
if (np == NULL)
PyListObject *np = (PyListObject *) list_new_prealloc(len);
if (np == NULL) {
return NULL;

src = a->ob_item + ilow;
dest = np->ob_item;
for (i = 0; i < len; i++) {
}
PyObject **src = a->ob_item + ilow;
PyObject **dest = np->ob_item;
for (Py_ssize_t i = 0; i < len; i++) {
PyObject *v = src[i];
dest[i] = Py_NewRef(v);
}
Py_SET_SIZE(np, len);
return (PyObject *)np;
}

static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
Py_ssize_t len = ihigh - ilow;
if (len <= 0) {
return PyList_New(0);
}
return list_slice_impl(a, ilow, len);
}

PyObject *
PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
Expand Down Expand Up @@ -584,13 +587,13 @@ list_concat_lock_held(PyListObject *a, PyListObject *b)
dest = np->ob_item;
for (i = 0; i < Py_SIZE(a); i++) {
PyObject *v = src[i];
FT_ATOMIC_STORE_PTR_RELAXED(dest[i], Py_NewRef(v));
Comment thread
corona10 marked this conversation as resolved.
dest[i] = Py_NewRef(v);
}
src = b->ob_item;
dest = np->ob_item + Py_SIZE(a);
for (i = 0; i < Py_SIZE(b); i++) {
PyObject *v = src[i];
FT_ATOMIC_STORE_PTR_RELAXED(dest[i], Py_NewRef(v));
dest[i] = Py_NewRef(v);
}
Py_SET_SIZE(np, size);
return (PyObject *)np;
Expand Down Expand Up @@ -636,15 +639,15 @@ list_repeat_lock_held(PyListObject *a, Py_ssize_t n)
_Py_RefcntAdd(elem, n);
PyObject **dest_end = dest + output_size;
while (dest < dest_end) {
FT_ATOMIC_STORE_PTR_RELAXED(*dest++, elem);
*dest++ = elem;
Comment thread
corona10 marked this conversation as resolved.
}
}
else {
PyObject **src = a->ob_item;
PyObject **src_end = src + input_size;
while (src < src_end) {
_Py_RefcntAdd(*src, n);
FT_ATOMIC_STORE_PTR_RELAXED(*dest++, *src++);
*dest++ = *src++;
}

_Py_memory_repeat((char *)np->ob_item, sizeof(PyObject *)*output_size,
Expand Down Expand Up @@ -718,7 +721,7 @@ list_clear_slot(PyObject *self)
* guaranteed the call cannot fail.
*/
static int
list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
list_ass_slice_impl(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
{
/* Because [X]DECREF can recursively invoke list operations on
this list, we must postpone all [X]DECREF activity until
Expand All @@ -741,15 +744,6 @@ list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
if (v == NULL)
n = 0;
else {
if (a == b) {
/* Special case "a[i:j] = a" -- copy b first */
v = list_slice(b, 0, Py_SIZE(b));
if (v == NULL)
return result;
result = list_ass_slice(a, ilow, ihigh, v);
Py_DECREF(v);
return result;
}
v_as_SF = PySequence_Fast(v, "can only assign an iterable");
if(v_as_SF == NULL)
goto Error;
Expand Down Expand Up @@ -823,6 +817,34 @@ list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
#undef b
}

static int
list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
{
int ret;
if (a == (PyListObject *)v) {
Py_BEGIN_CRITICAL_SECTION(a);
Py_ssize_t n = PyList_GET_SIZE(a);
PyObject *copy = list_slice_impl(a, 0, n);
if (copy == NULL) {
return -1;
}
ret = list_ass_slice_impl(a, ilow, ihigh, copy);
Py_DECREF(copy);
Py_END_CRITICAL_SECTION();
}
else if (v != NULL && PyList_CheckExact(v)) {
Py_BEGIN_CRITICAL_SECTION2(a, v);
ret = list_ass_slice_impl(a, ilow, ihigh, v);
Py_END_CRITICAL_SECTION2();
}
else {
Py_BEGIN_CRITICAL_SECTION(a);
ret = list_ass_slice_impl(a, ilow, ihigh, v);
Py_END_CRITICAL_SECTION();
}
return ret;
}

int
PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
{
Expand Down Expand Up @@ -2884,8 +2906,7 @@ list_remove_impl(PyListObject *self, PyObject *value)
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
Py_DECREF(obj);
if (cmp > 0) {
if (list_ass_slice(self, i, i+1,
(PyObject *)NULL) == 0)
if (list_ass_slice_impl(self, i, i+1, NULL) == 0)
Py_RETURN_NONE;
return NULL;
}
Expand Down Expand Up @@ -3085,6 +3106,47 @@ static PySequenceMethods list_as_sequence = {
list_inplace_repeat, /* sq_inplace_repeat */
};

static PyObject *
list_slice_step_lock_held(PyListObject *a, Py_ssize_t start, Py_ssize_t step, Py_ssize_t len)
{
PyObject *obj = list_new_prealloc(len);
if (obj == NULL) {
return NULL;
}
PyListObject *np = (PyListObject *)obj;
size_t cur;
Py_ssize_t i;
PyObject **src = a->ob_item;
PyObject **dest = np->ob_item;
for (cur = start, i = 0; i < len;
cur += (size_t)step, i++) {
PyObject *v = src[cur];
FT_ATOMIC_STORE_PTR_RELAXED(dest[i], Py_NewRef(v));
}
Py_SET_SIZE(np, len);
return (PyObject *)np;
}

static PyObject *
list_slice_wrap(PyListObject *aa, Py_ssize_t start, Py_ssize_t stop, Py_ssize_t step)
{
PyObject *res = NULL;
PyListObject *a = (PyListObject *)aa;
Comment thread
corona10 marked this conversation as resolved.
Outdated
Py_BEGIN_CRITICAL_SECTION(a);
Py_ssize_t len = PySlice_AdjustIndices(Py_SIZE(a), &start, &stop, step);
if (len <= 0) {
res = PyList_New(0);
}
else if (step == 1) {
res = list_slice_impl(a, start, len);
}
else {
res = list_slice_step_lock_held(a, start, step, len);
}
Py_END_CRITICAL_SECTION();
return res;
}

static PyObject *
list_subscript(PyObject* _self, PyObject* item)
{
Expand All @@ -3099,38 +3161,11 @@ list_subscript(PyObject* _self, PyObject* item)
return list_item((PyObject *)self, i);
}
else if (PySlice_Check(item)) {
Py_ssize_t start, stop, step, slicelength, i;
size_t cur;
PyObject* result;
PyObject* it;
PyObject **src, **dest;

Py_ssize_t start, stop, step;
if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
return NULL;
}
slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
step);

if (slicelength <= 0) {
return PyList_New(0);
}
else if (step == 1) {
return list_slice(self, start, stop);
}
else {
result = list_new_prealloc(slicelength);
if (!result) return NULL;

src = self->ob_item;
dest = ((PyListObject *)result)->ob_item;
for (cur = start, i = 0; i < slicelength;
cur += (size_t)step, i++) {
it = Py_NewRef(src[cur]);
dest[i] = it;
}
Py_SET_SIZE(result, slicelength);
return result;
}
return list_slice_wrap(self, start, stop, step);
}
else {
PyErr_Format(PyExc_TypeError,
Expand Down