Title: gh-123471: Make itertools.product and itertools.combinations thread-safe by eendebakpt · Pull Request #132814 · python/cpython · GitHub
Open Graph Title: gh-123471: Make itertools.product and itertools.combinations thread-safe by eendebakpt · Pull Request #132814 · python/cpython
X Title: gh-123471: Make itertools.product and itertools.combinations thread-safe by eendebakpt · Pull Request #132814 · python/cpython
Description: We make concurrent iteration over itertools.combinations and itertools.product thread safe in the free-threading build. The original combinations_next is renamed to combinations_next_with_lock_held and combinations_next is now calling combinations_next_with_lock_held with a lock (similar for itertools.product) We use a lock because it is easy to implement and avoids quite a bit of complexity (we have two pieces of mutable state to deal with: op->indices and op->result). Issues that can occur without the locks: On initialization of the results structure the op->result can be overwritten, resulting in memory leaks cpython/Modules/itertoolsmodule.c Line 2342 in a4ea80d PyTuple_SET_ITEM(result, i, elem); The increment of op->indices[i] at https://github.com/python/cpython/blob/main/Modules/itertoolsmodule.c#L2379 is not safe. It can go out-of-bounds since the check is done earlier. This can lead to a segfault The refcount check for re-use of the result tuple https://github.com/python/cpython/blob/main/Modules/itertoolsmodule.c#L2346 is not valid in the FT build. Not sure whether this leads to crashes, but it will result in memory leaks. Updating the indices is not atomic itertoolsmodule.c#L2380-L2381. Non-atomic updates can lead to out-of-bounds issues. The tests in this PR trigger some of these issues, although some are not visible (e.g. the memory leak), and it typically requires more iterations to result in a segfault. On my system > 2000 iterations gives a very high probability of triggering a segfault. The number of iterations is set much lower to keep the duration of the test < 0.1 second. Performance with the locks is about 5% less for a single-thread (see the corresponding issue). I refactored the tests to avoid duplicated code. Currently combinations and product are in the test, but cwr and permutations have the same style and could be added as well (in a followup PR). Could we do this without a full lock? It depends a bit on the iterator. For product we could make the rollover check safe by changing indices[i] == PyTuple_GET_SIZE(pool) into indices[i] >= PyTuple_GET_SIZE(pool) and use atomic operations in all operations dealing with op->indices or op->result. That would still leave memory leaks, but these are not crashes. And determining whether this actually safe (not crashing) requires some very careful reviews. Issue: gh-123471
Open Graph Description: We make concurrent iteration over itertools.combinations and itertools.product thread safe in the free-threading build. The original combinations_next is renamed to combinations_next_with_lock_hel...
X Description: We make concurrent iteration over itertools.combinations and itertools.product thread safe in the free-threading build. The original combinations_next is renamed to combinations_next_with_lock_hel...
Opengraph URL: https://github.com/python/cpython/pull/132814
X: @github
Domain: github.com
| route-pattern | /:user_id/:repository/pull/:id/files(.:format) |
| route-controller | pull_requests |
| route-action | files |
| fetch-nonce | v2:98141f5a-b726-785c-f8e4-c391c8a6be1e |
| current-catalog-service-hash | ae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b |
| request-id | A372:A6212:1EBF799:2C745D3:6A58DD29 |
| html-safe-nonce | 63190ef5e3c829f5b3031a0615724fc4938a09310f63664ff84c4af503db628d |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJBMzcyOkE2MjEyOjFFQkY3OTk6MkM3NDVEMzo2QTU4REQyOSIsInZpc2l0b3JfaWQiOiI3Nzg3MTQzMzYyOTI3NzEzNTc3IiwicmVnaW9uX2VkZ2UiOiJpYWQiLCJyZWdpb25fcmVuZGVyIjoiaWFkIn0= |
| visitor-hmac | 6ec33cfe93641a3857707a2e325cd56aee1b0a11acefc471dfdbd5e9a36f75e3 |
| hovercard-subject-tag | pull_request:2474538597 |
| github-keyboard-shortcuts | repository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/python/cpython/pull/132814/files |
| twitter:image | https://avatars.githubusercontent.com/u/883786?s=400&v=4 |
| twitter:card | summary_large_image |
| og:image | https://avatars.githubusercontent.com/u/883786?s=400&v=4 |
| og:image:alt | We make concurrent iteration over itertools.combinations and itertools.product thread safe in the free-threading build. The original combinations_next is renamed to combinations_next_with_lock_hel... |
| og:site_name | GitHub |
| og:type | object |
| hostname | github.com |
| expected-hostname | github.com |
| None | 5f2a0c7865178af3d91dd9f13b0cdfc3c73a2529c873d2780bb4c01271a57ec6 |
| turbo-cache-control | no-preview |
| diff-view | unified |
| go-import | github.com/python/cpython git https://github.com/python/cpython.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 81598961 |
| octolytics-dimension-repository_nwo | python/cpython |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 81598961 |
| octolytics-dimension-repository_network_root_nwo | python/cpython |
| turbo-body-classes | logged-out env-production page-responsive full-width |
| disable-turbo | true |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 8aae7b8d6caacacf5c66eaeb2702d8dc88d85b4a |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
Links:
Viewport: width=device-width