Skip to content

Commit c439b6f

Browse files
committed
avoid seq scan in lru; try a set
1 parent 84b7735 commit c439b6f

2 files changed

Lines changed: 33 additions & 28 deletions

File tree

‎Modules/_remote_debugging/_remote_debugging.h‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -263,20 +263,20 @@ typedef struct {
263263
} RemoteReadPrefetch;
264264

265265
#if defined(__APPLE__) && TARGET_OS_OSX
266-
#define MAX_ALIAS_PAGES 256
266+
#define ALIAS_CACHE_SETS 64
267+
#define ALIAS_CACHE_WAYS 2
267268
#define ALIAS_PROBE_MASK 0x3ff
268269

269270
typedef struct {
270271
uintptr_t remote_page_base;
271272
mach_vm_address_t local_page_base;
272273
mach_vm_size_t size;
273-
uint64_t access_seq;
274274
int valid;
275275
} AliasPageEntry;
276276

277277
typedef struct {
278-
AliasPageEntry pages[MAX_ALIAS_PAGES];
279-
uint64_t access_seq;
278+
AliasPageEntry pages[ALIAS_CACHE_SETS][ALIAS_CACHE_WAYS];
279+
uint8_t victim[ALIAS_CACHE_SETS];
280280
uint64_t target_start_tvsec;
281281
uint32_t probe_counter;
282282
int disabled;

‎Modules/_remote_debugging/alias_read.c‎

Lines changed: 29 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -34,14 +34,22 @@ alias_deallocate_entry(AliasPageEntry *entry)
3434
memset(entry, 0, sizeof(*entry));
3535
}
3636

37+
static size_t
38+
alias_set_index(RemoteUnwinderObject *unwinder, uintptr_t page_base)
39+
{
40+
size_t page_size = (size_t)unwinder->handle.page_size;
41+
uintptr_t page_index = page_base >> __builtin_ctzll(page_size);
42+
return (size_t)(page_index & (ALIAS_CACHE_SETS - 1));
43+
}
44+
3745
static AliasPageEntry *
3846
alias_find_entry(RemoteUnwinderObject *unwinder, uintptr_t page_base)
3947
{
4048
AliasReadCache *cache = &unwinder->alias_cache;
41-
for (int i = 0; i < MAX_ALIAS_PAGES; i++) {
42-
AliasPageEntry *entry = &cache->pages[i];
43-
if (entry->valid && entry->remote_page_base == page_base) {
44-
return entry;
49+
AliasPageEntry *ways = cache->pages[alias_set_index(unwinder, page_base)];
50+
for (int w = 0; w < ALIAS_CACHE_WAYS; w++) {
51+
if (ways[w].valid && ways[w].remote_page_base == page_base) {
52+
return &ways[w];
4553
}
4654
}
4755
return NULL;
@@ -51,8 +59,10 @@ void
5159
_Py_RemoteDebug_AliasCacheClear(RemoteUnwinderObject *unwinder)
5260
{
5361
AliasReadCache *cache = &unwinder->alias_cache;
54-
for (int i = 0; i < MAX_ALIAS_PAGES; i++) {
55-
alias_deallocate_entry(&cache->pages[i]);
62+
for (size_t s = 0; s < ALIAS_CACHE_SETS; s++) {
63+
for (int w = 0; w < ALIAS_CACHE_WAYS; w++) {
64+
alias_deallocate_entry(&cache->pages[s][w]);
65+
}
5666
}
5767
}
5868

@@ -70,8 +80,8 @@ _Py_RemoteDebug_AliasCacheInvalidatePage(RemoteUnwinderObject *unwinder,
7080
{
7181
size_t page_size = (size_t)unwinder->handle.page_size;
7282
uintptr_t page_base = remote_addr & ~(uintptr_t)(page_size - 1);
73-
AliasPageEntry *entry;
74-
while ((entry = alias_find_entry(unwinder, page_base)) != NULL) {
83+
AliasPageEntry *entry = alias_find_entry(unwinder, page_base);
84+
if (entry != NULL) {
7585
alias_deallocate_entry(entry);
7686
}
7787
}
@@ -118,25 +128,23 @@ alias_maybe_probe_identity(RemoteUnwinderObject *unwinder)
118128
}
119129

120130
static AliasPageEntry *
121-
alias_alloc_entry(RemoteUnwinderObject *unwinder)
131+
alias_alloc_entry(RemoteUnwinderObject *unwinder, uintptr_t page_base)
122132
{
123133
AliasReadCache *cache = &unwinder->alias_cache;
124-
AliasPageEntry *oldest = NULL;
134+
size_t set = alias_set_index(unwinder, page_base);
135+
AliasPageEntry *ways = cache->pages[set];
125136

126-
for (int i = 0; i < MAX_ALIAS_PAGES; i++) {
127-
AliasPageEntry *entry = &cache->pages[i];
128-
if (!entry->valid) {
129-
return entry;
130-
}
131-
if (oldest == NULL || entry->access_seq < oldest->access_seq) {
132-
oldest = entry;
137+
for (int w = 0; w < ALIAS_CACHE_WAYS; w++) {
138+
if (!ways[w].valid) {
139+
return &ways[w];
133140
}
134141
}
135142

136-
assert(oldest != NULL);
137-
alias_deallocate_entry(oldest);
143+
uint8_t victim = cache->victim[set];
144+
cache->victim[set] = (uint8_t)((victim + 1) % ALIAS_CACHE_WAYS);
145+
alias_deallocate_entry(&ways[victim]);
138146
STATS_INC(unwinder, alias_evictions);
139-
return oldest;
147+
return &ways[victim];
140148
}
141149

142150
static int
@@ -183,19 +191,17 @@ alias_remap_page(RemoteUnwinderObject *unwinder,
183191
uintptr_t page_base,
184192
AliasPageEntry **entry_out)
185193
{
186-
AliasReadCache *cache = &unwinder->alias_cache;
187194
mach_vm_address_t local_addr = 0;
188195
if (alias_map_readonly_page(unwinder, page_base, &local_addr) < 0) {
189196
STATS_INC(unwinder, alias_remap_failures);
190197
alias_disable_runtime(unwinder);
191198
return -1;
192199
}
193200

194-
AliasPageEntry *entry = alias_alloc_entry(unwinder);
201+
AliasPageEntry *entry = alias_alloc_entry(unwinder, page_base);
195202
entry->remote_page_base = page_base;
196203
entry->local_page_base = local_addr;
197204
entry->size = (mach_vm_size_t)unwinder->handle.page_size;
198-
entry->access_seq = ++cache->access_seq;
199205
entry->valid = 1;
200206

201207
*entry_out = entry;
@@ -231,7 +237,6 @@ _Py_RemoteDebug_AliasedRead(RemoteUnwinderObject *unwinder,
231237
return _Py_RemoteDebug_ReadRemoteMemory(
232238
&unwinder->handle, remote_addr, len, dst);
233239
}
234-
entry->access_seq = ++cache->access_seq;
235240
memcpy(dst, (const char *)entry->local_page_base + offset, len);
236241
STATS_INC(unwinder, alias_hits);
237242
return 0;

0 commit comments

Comments
 (0)