[PATCH] server: Use a free list for unallocated object handles.
The Legend of Heroes: Trails of Cold Steel III suffers from an application bug, where it tries to wait on a handle after closing it. Because of the usage patterns of the game and the way Wine allocates handles, the handle is usually reused by a separate object, which is effectively never signaled, resulting in a hang. This patch changes our handle allocation strategy to resemble Windows, and in the process makes the race much less likely, although still theoretically possible. Wine-Bug: https://bugs.winehq.org/show_bug.cgi?id=52461 Signed-off-by: Zebediah Figura <zfigura(a)codeweavers.com> --- A more detailed explanation of the bug can be found in the linked bug report. server/handle.c | 125 +++++++++++++++++++++++++----------------------- 1 file changed, 65 insertions(+), 60 deletions(-) diff --git a/server/handle.c b/server/handle.c index bc692b8ebeb..75b1f7969df 100644 --- a/server/handle.c +++ b/server/handle.c @@ -41,8 +41,13 @@ struct handle_entry { - struct object *ptr; /* object */ - unsigned int access; /* access rights */ + union + { + struct object *ptr; /* object */ + struct handle_entry *next; /* next free entry */ + } u; + unsigned int access; /* access rights */ + int used; /* is the entry currently in use? */ }; struct handle_table @@ -51,8 +56,8 @@ struct handle_table struct process *process; /* process owning this table */ int count; /* number of allocated entries */ int last; /* last used entry */ - int free; /* first entry that may be free */ struct handle_entry *entries; /* handle entries */ + struct handle_entry *freelist; /* head of free list */ }; static struct handle_table *global_table; @@ -157,11 +162,11 @@ static void handle_table_dump( struct object *obj, int verbose ) entry = table->entries; for (i = 0; i <= table->last; i++, entry++) { - if (!entry->ptr) continue; + if (!entry->used) continue; fprintf( stderr, " %04x: %p %08x ", - index_to_handle(i), entry->ptr, entry->access ); - dump_object_name( entry->ptr ); - entry->ptr->ops->dump( entry->ptr, 0 ); + index_to_handle(i), entry->u.ptr, entry->access ); + dump_object_name( entry->u.ptr ); + entry->u.ptr->ops->dump( entry->u.ptr, 0 ); } } @@ -176,12 +181,14 @@ static void handle_table_destroy( struct object *obj ) for (i = 0, entry = table->entries; i <= table->last; i++, entry++) { - struct object *obj = entry->ptr; - entry->ptr = NULL; - if (obj) + if (entry->used) { + struct object *obj = entry->u.ptr; if (table->process) obj->ops->close_handle( obj, table->process, index_to_handle(i) ); + entry->used = 0; + entry->u.next = table->freelist; + table->freelist = entry; release_object_from_handle( obj ); } } @@ -208,7 +215,7 @@ struct handle_table *alloc_handle_table( struct process *process, int count ) table->process = process; table->count = count; table->last = -1; - table->free = 0; + table->freelist = NULL; if ((table->entries = mem_alloc( count * sizeof(*table->entries) ))) return table; release_object( table ); return NULL; @@ -234,21 +241,23 @@ static int grow_handle_table( struct handle_table *table ) /* allocate the first free entry in the handle table */ static obj_handle_t alloc_entry( struct handle_table *table, void *obj, unsigned int access ) { - struct handle_entry *entry = table->entries + table->free; - int i; + struct handle_entry *entry; - for (i = table->free; i <= table->last; i++, entry++) if (!entry->ptr) goto found; - if (i >= table->count) + if (table->freelist) { - if (!grow_handle_table( table )) return 0; - entry = table->entries + i; /* the entries may have moved */ + entry = table->freelist; + table->freelist = entry->u.next; } - table->last = i; - found: - table->free = i + 1; - entry->ptr = grab_object_for_handle( obj ); + else + { + if (table->last + 1 >= table->count && !grow_handle_table( table )) return 0; + entry = &table->entries[++table->last]; + } + + entry->used = 1; + entry->u.ptr = grab_object_for_handle( obj ); entry->access = access; - return index_to_handle(i); + return index_to_handle( entry - table->entries ); } /* allocate a handle for an object, incrementing its refcount */ @@ -327,31 +336,10 @@ static struct handle_entry *get_handle( struct process *process, obj_handle_t ha if (index < 0) return NULL; if (index > table->last) return NULL; entry = table->entries + index; - if (!entry->ptr) return NULL; + if (!entry->used) return NULL; return entry; } -/* attempt to shrink a table */ -static void shrink_handle_table( struct handle_table *table ) -{ - struct handle_entry *entry = table->entries + table->last; - struct handle_entry *new_entries; - int count = table->count; - - while (table->last >= 0) - { - if (entry->ptr) break; - table->last--; - entry--; - } - if (table->last >= count / 4) return; /* no need to shrink */ - if (count < MIN_HANDLE_ENTRIES * 2) return; /* too small to shrink */ - count /= 2; - if (!(new_entries = realloc( table->entries, count * sizeof(*new_entries) ))) return; - table->count = count; - table->entries = new_entries; -} - static void inherit_handle( struct process *parent, const obj_handle_t handle, struct handle_table *table ) { struct handle_entry *dst, *src; @@ -362,8 +350,9 @@ static void inherit_handle( struct process *parent, const obj_handle_t handle, s src = get_handle( parent, handle ); if (!src || !(src->access & RESERVED_INHERIT)) return; index = handle_to_index( handle ); - if (dst[index].ptr) return; - grab_object_for_handle( src->ptr ); + if (dst[index].used) return; + + grab_object_for_handle( src->u.ptr ); dst[index] = *src; table->last = max( table->last, index ); } @@ -397,6 +386,18 @@ struct handle_table *copy_handle_table( struct process *process, struct process { inherit_handle( parent, std_handles[i], table ); } + + /* iterate in reverse so that low values are allocated first */ + for (i = table->last; i >= 0; --i) + { + struct handle_entry *entry = &table->entries[i]; + + if (!entry->used) + { + entry->u.next = table->freelist; + table->freelist = entry; + } + } } else { @@ -406,14 +407,16 @@ struct handle_table *copy_handle_table( struct process *process, struct process memcpy( ptr, parent_table->entries, (table->last + 1) * sizeof(struct handle_entry) ); for (i = 0; i <= table->last; i++, ptr++) { - if (!ptr->ptr) continue; - if (ptr->access & RESERVED_INHERIT) grab_object_for_handle( ptr->ptr ); - else ptr->ptr = NULL; /* don't inherit this entry */ + if (ptr->used && (ptr->access & RESERVED_INHERIT)) grab_object_for_handle( ptr->u.ptr ); + else + { + ptr->used = 0; + ptr->u.next = table->freelist; + table->freelist = ptr; + } } } } - /* attempt to shrink the table */ - shrink_handle_table( table ); return table; } @@ -426,12 +429,14 @@ unsigned int close_handle( struct process *process, obj_handle_t handle ) if (!(entry = get_handle( process, handle ))) return STATUS_INVALID_HANDLE; if (entry->access & RESERVED_CLOSE_PROTECT) return STATUS_HANDLE_NOT_CLOSABLE; - obj = entry->ptr; + obj = entry->u.ptr; if (!obj->ops->close_handle( obj, process, handle )) return STATUS_HANDLE_NOT_CLOSABLE; - entry->ptr = NULL; + table = handle_is_global(handle) ? global_table : process->handles; - if (entry < table->entries + table->free) table->free = entry - table->entries; - if (entry == table->entries + table->last) shrink_handle_table( table ); + entry->used = 0; + entry->u.next = table->freelist; + table->freelist = entry; + release_object_from_handle( obj ); return STATUS_SUCCESS; } @@ -471,7 +476,7 @@ struct object *get_handle_obj( struct process *process, obj_handle_t handle, set_error( STATUS_INVALID_HANDLE ); return NULL; } - obj = entry->ptr; + obj = entry->u.ptr; if (ops && (obj->ops != ops)) { set_error( STATUS_OBJECT_TYPE_MISMATCH ); /* not the right type */ @@ -513,8 +518,8 @@ obj_handle_t find_inherited_handle( struct process *process, const struct object for (i = 0, ptr = table->entries; i <= table->last; i++, ptr++) { - if (!ptr->ptr) continue; - if (ptr->ptr->ops != ops) continue; + if (!ptr->used) continue; + if (ptr->u.ptr->ops != ops) continue; if (ptr->access & RESERVED_INHERIT) return index_to_handle(i); } return 0; @@ -825,7 +830,7 @@ static int enum_handles( struct process *process, void *user ) for (i = 0, entry = table->entries; i <= table->last; i++, entry++) { - if (!entry->ptr) continue; + if (!entry->used) continue; if (!info->handle) { info->count++; @@ -836,7 +841,7 @@ static int enum_handles( struct process *process, void *user ) handle->owner = process->id; handle->handle = index_to_handle(i); handle->access = entry->access & ~RESERVED_ALL; - handle->type = entry->ptr->ops->type->index; + handle->type = entry->u.ptr->ops->type->index; handle->attributes = 0; if (entry->access & RESERVED_INHERIT) handle->attributes |= OBJ_INHERIT; if (entry->access & RESERVED_CLOSE_PROTECT) handle->attributes |= OBJ_PROTECT_CLOSE; -- 2.34.1
Zebediah Figura <zfigura(a)codeweavers.com> writes:
The Legend of Heroes: Trails of Cold Steel III suffers from an application bug, where it tries to wait on a handle after closing it. Because of the usage patterns of the game and the way Wine allocates handles, the handle is usually reused by a separate object, which is effectively never signaled, resulting in a hang.
This patch changes our handle allocation strategy to resemble Windows, and in the process makes the race much less likely, although still theoretically possible.
Some tests would be nice. -- Alexandre Julliard julliard(a)winehq.org
On 2/1/22 13:54, Alexandre Julliard wrote:
Zebediah Figura <zfigura(a)codeweavers.com> writes:
The Legend of Heroes: Trails of Cold Steel III suffers from an application bug, where it tries to wait on a handle after closing it. Because of the usage patterns of the game and the way Wine allocates handles, the handle is usually reused by a separate object, which is effectively never signaled, resulting in a hang.
This patch changes our handle allocation strategy to resemble Windows, and in the process makes the race much less likely, although still theoretically possible.
Some tests would be nice.
That may be difficult. When I was testing this manually I ran into hiccups due to some background thread in the process opening or closing handles.
On 2/1/22 14:56, Zebediah Figura wrote:
On 2/1/22 13:54, Alexandre Julliard wrote:
Zebediah Figura <zfigura(a)codeweavers.com> writes:
The Legend of Heroes: Trails of Cold Steel III suffers from an application bug, where it tries to wait on a handle after closing it. Because of the usage patterns of the game and the way Wine allocates handles, the handle is usually reused by a separate object, which is effectively never signaled, resulting in a hang.
This patch changes our handle allocation strategy to resemble Windows, and in the process makes the race much less likely, although still theoretically possible.
Some tests would be nice.
That may be difficult. When I was testing this manually I ran into hiccups due to some background thread in the process opening or closing handles.
I tried writing tests for this along the following lines: allocate a large number of handles, close them all, then allocate the same number and check that they're allocated in the reverse order. Sometimes (depending on timing, and perhaps also Windows version?) the tests pass with flying colours. But sometimes they fail, and fail quite randomly at that. Sometimes it's clear that one or two handles were allocated out of order, as if another thread allocated and/or freed them, but sometimes it seems like hundreds are. Perhaps that's evidence that Windows isn't quite using a free list for handle allocation the way this patch has it, but the fact that it at least sometimes passes makes me think it is.
On 2/15/22 16:15, Zebediah Figura wrote:
On 2/1/22 14:56, Zebediah Figura wrote:
On 2/1/22 13:54, Alexandre Julliard wrote:
Zebediah Figura <zfigura(a)codeweavers.com> writes:
The Legend of Heroes: Trails of Cold Steel III suffers from an application bug, where it tries to wait on a handle after closing it. Because of the usage patterns of the game and the way Wine allocates handles, the handle is usually reused by a separate object, which is effectively never signaled, resulting in a hang.
This patch changes our handle allocation strategy to resemble Windows, and in the process makes the race much less likely, although still theoretically possible.
Some tests would be nice.
That may be difficult. When I was testing this manually I ran into hiccups due to some background thread in the process opening or closing handles.
I tried writing tests for this along the following lines: allocate a large number of handles, close them all, then allocate the same number and check that they're allocated in the reverse order.
Sometimes (depending on timing, and perhaps also Windows version?) the tests pass with flying colours. But sometimes they fail, and fail quite randomly at that. Sometimes it's clear that one or two handles were allocated out of order, as if another thread allocated and/or freed them, but sometimes it seems like hundreds are. Perhaps that's evidence that Windows isn't quite using a free list for handle allocation the way this patch has it, but the fact that it at least sometimes passes makes me think it is.
I accidentally hit send before I was done writing... Anyway, I'm not sure what else to do here. I could drop the patch since it's not fully clear it's correct and it doesn't even make the described race impossible, but it doesn't seem likely that there's a more correct solution, or that it's going to be easily found if so. I guess I could also write tests that allocate and close a single handle in a loop, and test that it's "usually" the same handle, within some tolerance. That doesn't seem particularly helpful, though; there are many ways to pass that test (e.g. our current implementation will). Or perhaps you had ideas for tests already in mind that aren't occurring to me?
participants (2)
-
Alexandre Julliard -
Zebediah Figura