Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit b811432

Browse filesBrowse files
colesburycolesbury
committed
gh-115103: Delay reuse of mimalloc pages that store PyObjects
1 parent d336146 commit b811432
Copy full SHA for b811432

File tree

Expand file treeCollapse file tree

9 files changed

+211
-16
lines changed
Filter options
Expand file treeCollapse file tree

9 files changed

+211
-16
lines changed

‎Include/internal/mimalloc/mimalloc/types.h

Copy file name to clipboardExpand all lines: Include/internal/mimalloc/mimalloc/types.h
+8-1Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -311,6 +311,7 @@ typedef struct mi_page_s {
311311
uint32_t slice_offset; // distance from the actual page data slice (0 if a page)
312312
uint8_t is_committed : 1; // `true` if the page virtual memory is committed
313313
uint8_t is_zero_init : 1; // `true` if the page was initially zero initialized
314+
uint8_t delay_free : 1; // delay page freeing using qsbr
314315
uint8_t tag : 4; // tag from the owning heap
315316
uint8_t debug_offset; // number of bytes to preserve when filling freed or uninitialized memory
316317

@@ -336,8 +337,13 @@ typedef struct mi_page_s {
336337
struct mi_page_s* next; // next page owned by this thread with the same `block_size`
337338
struct mi_page_s* prev; // previous page owned by this thread with the same `block_size`
338339

340+
#ifdef Py_GIL_DISABLED
341+
struct llist_node qsbr_node;
342+
uint64_t qsbr_goal;
343+
#endif
344+
339345
// 64-bit 9 words, 32-bit 12 words, (+2 for secure)
340-
#if MI_INTPTR_SIZE==8
346+
#if MI_INTPTR_SIZE==8 && !defined(Py_GIL_DISABLED)
341347
uintptr_t padding[1];
342348
#endif
343349
} mi_page_t;
@@ -555,6 +561,7 @@ struct mi_heap_s {
555561
bool no_reclaim; // `true` if this heap should not reclaim abandoned pages
556562
uint8_t tag; // custom identifier for this heap
557563
uint8_t debug_offset; // number of bytes to preserve when filling freed or uninitialized memory
564+
bool page_delay_free; // should freeing pages be delayed
558565
};
559566

560567

‎Include/internal/pycore_mimalloc.h

Copy file name to clipboardExpand all lines: Include/internal/pycore_mimalloc.h
+1Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,7 @@ struct _mimalloc_thread_state {
4848
mi_heap_t *current_object_heap;
4949
mi_heap_t heaps[_Py_MIMALLOC_HEAP_COUNT];
5050
mi_tld_t tld;
51+
struct llist_node page_list;
5152
};
5253
#endif
5354

‎Include/internal/pycore_qsbr.h

Copy file name to clipboardExpand all lines: Include/internal/pycore_qsbr.h
+15Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,12 @@ extern "C" {
2929
#define QSBR_INITIAL 1
3030
#define QSBR_INCR 2
3131

32+
// Wrap-around safe comparison. This is a holdover from the FreeBSD
33+
// implementation, which uses 32-bit sequence numbers. We currently use 64-bit
34+
// sequence numbers, so wrap-around is unlikely.
35+
#define QSBR_LT(a, b) ((int64_t)((a)-(b)) < 0)
36+
#define QSBR_LEQ(a, b) ((int64_t)((a)-(b)) <= 0)
37+
3238
struct _qsbr_shared;
3339
struct _PyThreadStateImpl; // forward declare to avoid circular dependency
3440

@@ -89,6 +95,15 @@ _Py_qsbr_quiescent_state(struct _qsbr_thread_state *qsbr)
8995
_Py_atomic_store_uint64_release(&qsbr->seq, seq);
9096
}
9197

98+
// Have the read sequences advanced to the given goal? Like `_Py_qsbr_poll()`,
99+
// but does not perform a scan of threads.
100+
static inline bool
101+
_Py_qbsr_goal_reached(struct _qsbr_thread_state *qsbr, uint64_t goal)
102+
{
103+
uint64_t rd_seq = _Py_atomic_load_uint64(&qsbr->shared->rd_seq);
104+
return QSBR_LEQ(goal, rd_seq);
105+
}
106+
92107
// Advance the write sequence and return the new goal. This should be called
93108
// after data is removed. The returned goal is used with `_Py_qsbr_poll()` to
94109
// determine when it is safe to reclaim (free) the memory.

‎Objects/mimalloc/heap.c

Copy file name to clipboardExpand all lines: Objects/mimalloc/heap.c
+8-1Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -98,7 +98,10 @@ static bool mi_heap_page_collect(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_t
9898
if (mi_page_all_free(page)) {
9999
// no more used blocks, free the page.
100100
// note: this will free retired pages as well.
101-
_mi_page_free(page, pq, collect >= MI_FORCE);
101+
bool freed = _PyMem_mi_page_maybe_free(page, pq, collect >= MI_FORCE);
102+
if (!freed && collect == MI_ABANDON) {
103+
_mi_page_abandon(page, pq);
104+
}
102105
}
103106
else if (collect == MI_ABANDON) {
104107
// still used blocks but the thread is done; abandon the page
@@ -153,6 +156,9 @@ static void mi_heap_collect_ex(mi_heap_t* heap, mi_collect_t collect)
153156
// collect retired pages
154157
_mi_heap_collect_retired(heap, force);
155158

159+
// free pages that were delayed with QSBR
160+
_PyMem_mi_heap_collect_qsbr(heap);
161+
156162
// collect all pages owned by this thread
157163
mi_heap_visit_pages(heap, &mi_heap_page_collect, &collect, NULL);
158164
mi_assert_internal( collect != MI_ABANDON || mi_atomic_load_ptr_acquire(mi_block_t,&heap->thread_delayed_free) == NULL );
@@ -634,6 +640,7 @@ bool _mi_heap_area_visit_blocks(const mi_heap_area_t* area, mi_page_t *page, mi_
634640
typedef bool (mi_heap_area_visit_fun)(const mi_heap_t* heap, const mi_heap_area_ex_t* area, void* arg);
635641

636642
void _mi_heap_area_init(mi_heap_area_t* area, mi_page_t* page) {
643+
_PyMem_mi_page_clear_qsbr(page);
637644
_mi_page_free_collect(page,true);
638645
const size_t bsize = mi_page_block_size(page);
639646
const size_t ubsize = mi_page_usable_block_size(page);

‎Objects/mimalloc/page.c

Copy file name to clipboardExpand all lines: Objects/mimalloc/page.c
+29-2Lines changed: 29 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -225,6 +225,9 @@ void _mi_page_free_collect(mi_page_t* page, bool force) {
225225

226226
// and the local free list
227227
if (page->local_free != NULL) {
228+
// any previous QSBR goals are no longer valid because we reused the page
229+
_PyMem_mi_page_clear_qsbr(page);
230+
228231
if mi_likely(page->free == NULL) {
229232
// usual case
230233
page->free = page->local_free;
@@ -267,6 +270,9 @@ void _mi_page_reclaim(mi_heap_t* heap, mi_page_t* page) {
267270
// TODO: push on full queue immediately if it is full?
268271
mi_page_queue_t* pq = mi_page_queue(heap, mi_page_block_size(page));
269272
mi_page_queue_push(heap, pq, page);
273+
274+
_PyMem_mi_page_reclaimed(page);
275+
270276
mi_assert_expensive(_mi_page_is_valid(page));
271277
}
272278

@@ -383,6 +389,13 @@ void _mi_page_abandon(mi_page_t* page, mi_page_queue_t* pq) {
383389

384390
mi_heap_t* pheap = mi_page_heap(page);
385391

392+
#ifdef Py_GIL_DISABLED
393+
if (page->qsbr_node.next != NULL) {
394+
// remove from QSBR queue, but keep the goal
395+
llist_remove(&page->qsbr_node);
396+
}
397+
#endif
398+
386399
// remove from our page list
387400
mi_segments_tld_t* segments_tld = &pheap->tld->segments;
388401
mi_page_queue_remove(pq, page);
@@ -417,6 +430,11 @@ void _mi_page_free(mi_page_t* page, mi_page_queue_t* pq, bool force) {
417430

418431
mi_heap_t* heap = mi_page_heap(page);
419432

433+
#ifdef Py_GIL_DISABLED
434+
mi_assert_internal(page->qsbr_goal == 0);
435+
mi_assert_internal(page->qsbr_node.next == NULL);
436+
#endif
437+
420438
// remove from the page list
421439
// (no need to do _mi_heap_delayed_free first as all blocks are already free)
422440
mi_segments_tld_t* segments_tld = &heap->tld->segments;
@@ -465,7 +483,7 @@ void _mi_page_retire(mi_page_t* page) mi_attr_noexcept {
465483
return; // dont't free after all
466484
}
467485
}
468-
_mi_page_free(page, pq, false);
486+
_PyMem_mi_page_maybe_free(page, pq, false);
469487
}
470488

471489
// free retired pages: we don't need to look at the entire queues
@@ -480,7 +498,7 @@ void _mi_heap_collect_retired(mi_heap_t* heap, bool force) {
480498
if (mi_page_all_free(page)) {
481499
page->retire_expire--;
482500
if (force || page->retire_expire == 0) {
483-
_mi_page_free(pq->first, pq, force);
501+
_PyMem_mi_page_maybe_free(page, pq, false);
484502
}
485503
else {
486504
// keep retired, update min/max
@@ -661,6 +679,7 @@ static void mi_page_init(mi_heap_t* heap, mi_page_t* page, size_t block_size, mi
661679
// set fields
662680
mi_page_set_heap(page, heap);
663681
page->tag = heap->tag;
682+
page->delay_free = heap->page_delay_free;
664683
page->debug_offset = heap->debug_offset;
665684
page->xblock_size = (block_size < MI_HUGE_BLOCK_SIZE ? (uint32_t)block_size : MI_HUGE_BLOCK_SIZE); // initialize before _mi_segment_page_start
666685
size_t page_size;
@@ -691,6 +710,10 @@ static void mi_page_init(mi_heap_t* heap, mi_page_t* page, size_t block_size, mi
691710
mi_assert_internal(page->xthread_free == 0);
692711
mi_assert_internal(page->next == NULL);
693712
mi_assert_internal(page->prev == NULL);
713+
#ifdef Py_GIL_DISABLED
714+
mi_assert_internal(page->qsbr_goal == 0);
715+
mi_assert_internal(page->qsbr_node.next == NULL);
716+
#endif
694717
mi_assert_internal(page->retire_expire == 0);
695718
mi_assert_internal(!mi_page_has_aligned(page));
696719
#if (MI_PADDING || MI_ENCODE_FREELIST)
@@ -750,6 +773,7 @@ static mi_page_t* mi_page_queue_find_free_ex(mi_heap_t* heap, mi_page_queue_t* p
750773
mi_heap_stat_counter_increase(heap, searches, count);
751774

752775
if (page == NULL) {
776+
_PyMem_mi_heap_collect_qsbr(heap); // some pages might be safe to free now
753777
_mi_heap_collect_retired(heap, false); // perhaps make a page available?
754778
page = mi_page_fresh(heap, pq);
755779
if (page == NULL && first_try) {
@@ -760,6 +784,7 @@ static mi_page_t* mi_page_queue_find_free_ex(mi_heap_t* heap, mi_page_queue_t* p
760784
else {
761785
mi_assert(pq->first == page);
762786
page->retire_expire = 0;
787+
_PyMem_mi_page_clear_qsbr(page);
763788
}
764789
mi_assert_internal(page == NULL || mi_page_immediate_available(page));
765790
return page;
@@ -785,6 +810,7 @@ static inline mi_page_t* mi_find_free_page(mi_heap_t* heap, size_t size) {
785810

786811
if (mi_page_immediate_available(page)) {
787812
page->retire_expire = 0;
813+
_PyMem_mi_page_clear_qsbr(page);
788814
return page; // fast path
789815
}
790816
}
@@ -878,6 +904,7 @@ static mi_page_t* mi_find_page(mi_heap_t* heap, size_t size, size_t huge_alignme
878904
return NULL;
879905
}
880906
else {
907+
_PyMem_mi_heap_collect_qsbr(heap);
881908
return mi_large_huge_page_alloc(heap,size,huge_alignment);
882909
}
883910
}

‎Objects/mimalloc/segment.c

Copy file name to clipboardExpand all lines: Objects/mimalloc/segment.c
+6-2Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -982,6 +982,10 @@ static mi_slice_t* mi_segment_page_clear(mi_page_t* page, mi_segments_tld_t* tld
982982
mi_assert_internal(mi_page_all_free(page));
983983
mi_segment_t* segment = _mi_ptr_segment(page);
984984
mi_assert_internal(segment->used > 0);
985+
#ifdef Py_GIL_DISABLED
986+
mi_assert_internal(page->qsbr_goal == 0);
987+
mi_assert_internal(page->qsbr_node.next == NULL);
988+
#endif
985989

986990
size_t inuse = page->capacity * mi_page_block_size(page);
987991
_mi_stat_decrease(&tld->stats->page_committed, inuse);
@@ -1270,7 +1274,7 @@ static bool mi_segment_check_free(mi_segment_t* segment, size_t slices_needed, s
12701274
// ensure used count is up to date and collect potential concurrent frees
12711275
mi_page_t* const page = mi_slice_to_page(slice);
12721276
_mi_page_free_collect(page, false);
1273-
if (mi_page_all_free(page)) {
1277+
if (mi_page_all_free(page) && _PyMem_mi_page_is_safe_to_free(page)) {
12741278
// if this page is all free now, free it without adding to any queues (yet)
12751279
mi_assert_internal(page->next == NULL && page->prev==NULL);
12761280
_mi_stat_decrease(&tld->stats->pages_abandoned, 1);
@@ -1344,7 +1348,7 @@ static mi_segment_t* mi_segment_reclaim(mi_segment_t* segment, mi_heap_t* heap,
13441348
mi_page_set_heap(page, target_heap);
13451349
_mi_page_use_delayed_free(page, MI_USE_DELAYED_FREE, true); // override never (after heap is set)
13461350
_mi_page_free_collect(page, false); // ensure used count is up to date
1347-
if (mi_page_all_free(page)) {
1351+
if (mi_page_all_free(page) && _PyMem_mi_page_is_safe_to_free(page)) {
13481352
// if everything free by now, free the page
13491353
slice = mi_segment_page_clear(page, tld); // set slice again due to coalesceing
13501354
}

‎Objects/obmalloc.c

Copy file name to clipboardExpand all lines: Objects/obmalloc.c
+135Lines changed: 135 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,12 @@
1212
#include <stdlib.h> // malloc()
1313
#include <stdbool.h>
1414
#ifdef WITH_MIMALLOC
15+
// Forward declarations of functions used in our mimalloc modifications
16+
static void _PyMem_mi_page_clear_qsbr(mi_page_t *page);
17+
static bool _PyMem_mi_page_is_safe_to_free(mi_page_t *page);
18+
static bool _PyMem_mi_page_maybe_free(mi_page_t *page, mi_page_queue_t *pq, bool force);
19+
static void _PyMem_mi_page_reclaimed(mi_page_t *page);
20+
static void _PyMem_mi_heap_collect_qsbr(mi_heap_t *heap);
1521
# include "pycore_mimalloc.h"
1622
# include "mimalloc/static.c"
1723
# include "mimalloc/internal.h" // for stats
@@ -86,6 +92,135 @@ _PyMem_RawFree(void *Py_UNUSED(ctx), void *ptr)
8692

8793
#ifdef WITH_MIMALLOC
8894

95+
static void
96+
_PyMem_mi_page_clear_qsbr(mi_page_t *page)
97+
{
98+
#ifdef Py_GIL_DISABLED
99+
// Clear the QSBR goal and remove the page from the QSBR linked list.
100+
page->qsbr_goal = 0;
101+
if (page->qsbr_node.next != NULL) {
102+
llist_remove(&page->qsbr_node);
103+
}
104+
#endif
105+
}
106+
107+
// Is the empty page safe to free? It's safe if there was a QSBR goal set and
108+
// the goal has been reached.
109+
static bool
110+
_PyMem_mi_page_is_safe_to_free(mi_page_t *page)
111+
{
112+
assert(mi_page_all_free(page));
113+
#ifdef Py_GIL_DISABLED
114+
if (page->delay_free) {
115+
if (page->qsbr_goal == 0) {
116+
// No QSBR goal set, so we can't safely free the page yet.
117+
return false;
118+
}
119+
_PyThreadStateImpl *tstate = (_PyThreadStateImpl *)_PyThreadState_GET();
120+
if (tstate == NULL) {
121+
return false;
122+
}
123+
if (!_Py_qbsr_goal_reached(tstate->qsbr, page->qsbr_goal)) {
124+
return false;
125+
}
126+
_PyMem_mi_page_clear_qsbr(page);
127+
return true;
128+
}
129+
#endif
130+
return true;
131+
}
132+
133+
#ifdef Py_GIL_DISABLED
134+
// Enqueue a page to be freed later when it's safe to do so (using QSBR).
135+
// Note that we may still allocate from the page.
136+
static void
137+
enqueue_page_qsbr(mi_page_t *page, bool reclaimed)
138+
{
139+
assert(mi_page_all_free(page));
140+
assert(reclaimed || page->qsbr_goal == 0);
141+
142+
_PyThreadStateImpl *tstate = (_PyThreadStateImpl *)PyThreadState_GET();
143+
page->retire_expire = 0;
144+
145+
// The goal may be set if we are reclaiming an empty abandoned page
146+
if (page->qsbr_goal == 0) {
147+
page->qsbr_goal = _Py_qsbr_deferred_advance(tstate->qsbr);
148+
}
149+
150+
llist_insert_tail(&tstate->mimalloc.page_list, &page->qsbr_node);
151+
}
152+
#endif
153+
154+
static bool
155+
_PyMem_mi_page_maybe_free(mi_page_t *page, mi_page_queue_t *pq, bool force)
156+
{
157+
#ifdef Py_GIL_DISABLED
158+
if (!_PyMem_mi_page_is_safe_to_free(page)) {
159+
// The page may already be in the QSBR linked list if we allocated from
160+
// it after all blocks were freed.
161+
if (page->qsbr_node.next != NULL) {
162+
llist_remove(&page->qsbr_node);
163+
page->qsbr_goal = 0;
164+
}
165+
enqueue_page_qsbr(page, false);
166+
return false;
167+
}
168+
#endif
169+
_mi_page_free(page, pq, force);
170+
return true;
171+
}
172+
173+
static void
174+
_PyMem_mi_page_reclaimed(mi_page_t *page)
175+
{
176+
#ifdef Py_GIL_DISABLED
177+
assert(page->qsbr_node.next == NULL);
178+
if (page->qsbr_goal != 0) {
179+
if (mi_page_all_free(page)) {
180+
enqueue_page_qsbr(page, true);
181+
}
182+
else {
183+
page->qsbr_goal = 0;
184+
}
185+
}
186+
#endif
187+
}
188+
189+
static void
190+
_PyMem_mi_heap_collect_qsbr(mi_heap_t *heap)
191+
{
192+
#ifdef Py_GIL_DISABLED
193+
if (!heap->page_delay_free) {
194+
return;
195+
}
196+
197+
_PyThreadStateImpl *tstate = (_PyThreadStateImpl *)_PyThreadState_GET();
198+
struct llist_node *head = &tstate->mimalloc.page_list;
199+
if (llist_empty(head)) {
200+
return;
201+
}
202+
203+
struct llist_node *node;
204+
llist_for_each_safe(node, head) {
205+
mi_page_t *page = llist_data(node, mi_page_t, qsbr_node);
206+
if (!mi_page_all_free(page)) {
207+
// We allocated from this page some point after the delayed free
208+
page->qsbr_goal = 0;
209+
llist_remove(node);
210+
continue;
211+
}
212+
213+
if (!_Py_qsbr_poll(tstate->qsbr, page->qsbr_goal)) {
214+
return;
215+
}
216+
217+
page->qsbr_goal = 0;
218+
llist_remove(node);
219+
_mi_page_free(page, mi_page_queue_of(page), false);
220+
}
221+
#endif
222+
}
223+
89224
void *
90225
_PyMem_MiMalloc(void *ctx, size_t size)
91226
{

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.