[PATCH 0/15] MR1628: Draft: ntdll: Implement Low Fragmentation Heap.

List overview All Threads

newer

older

[PATCH 0/3] MR1631: wineusb.sys:...

[PATCH 0/1] MR1627: winevulkan:...

Rémi Bernon (＠rbernon)

1 Dec 2022 1 Dec '22

12:05 p.m.

Not completely sure if it's worth having for 8.0, but opening this to share the target I'm trying to reach.

-- https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Show replies by date

Rémi Bernon

1 Dec 1 Dec

12:05 p.m.

New subject: [PATCH 01/15] ntdll: Split heap region memory allocation to allocate_region helper.

From: Rémi Bernon rbernon@codeweavers.com

--- dlls/ntdll/heap.c | 58 +++++++++++++++++++++++++++-------------------- 1 file changed, 34 insertions(+), 24 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index 1de9fe6a4b6..af95e78d7e9 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -832,22 +832,44 @@ static inline void shrink_used_block( struct heap *heap, ULONG flags, struct blo }

+static NTSTATUS allocate_region( ULONG flags, SIZE_T *commit_size, SIZE_T *reserve_size, void **addr ) +{ + NTSTATUS status; + + if (!(flags & HEAP_GROWABLE)) return STATUS_NO_MEMORY; + + if (reserve_size) *commit_size = min( *commit_size, *reserve_size ); + *addr = NULL; + + /* allocate the memory block */ + if (reserve_size && *reserve_size != *commit_size && + (status = NtAllocateVirtualMemory( NtCurrentProcess(), addr, 0, reserve_size, MEM_RESERVE, + get_protection_type( flags ) ))) + { + WARN( "Could not allocate %#Ix bytes, status %#lx\n", *reserve_size, status ); + return status; + } + if ((status = NtAllocateVirtualMemory( NtCurrentProcess(), addr, 0, commit_size, MEM_COMMIT, + get_protection_type( flags ) ))) + { + WARN( "Could not commit %#Ix bytes, status %#lx\n", *commit_size, status ); + return status; + } + + return status; +} + + static NTSTATUS heap_allocate_large( struct heap *heap, ULONG flags, SIZE_T block_size, SIZE_T size, void **ret ) { ARENA_LARGE *arena; SIZE_T total_size = ROUND_SIZE( sizeof(*arena) + size, REGION_ALIGN - 1 ); - LPVOID address = NULL; struct block *block; + void *address;

- if (!(flags & HEAP_GROWABLE)) return STATUS_NO_MEMORY; if (total_size < size) return STATUS_NO_MEMORY; /* overflow */ - if (NtAllocateVirtualMemory( NtCurrentProcess(), &address, 0, &total_size, MEM_COMMIT, - get_protection_type( heap->flags ) )) - { - WARN( "Could not allocate block for %#Ix bytes\n", size ); - return STATUS_NO_MEMORY; - } + if (allocate_region( flags, &total_size, NULL, &address )) return STATUS_NO_MEMORY;

arena = address; block = &arena->block; @@ -937,24 +959,12 @@ static SUBHEAP *HEAP_CreateSubHeap( struct heap **heap_ptr, LPVOID address, DWOR

if (!address) { - if (!commitSize) commitSize = REGION_ALIGN; - totalSize = min( totalSize, 0xffff0000 ); /* don't allow a heap larger than 4GB */ - if (totalSize < commitSize) totalSize = commitSize; - commitSize = min( totalSize, (SIZE_T)ROUND_ADDR( commitSize + REGION_ALIGN - 1, REGION_ALIGN - 1 ) ); + commitSize = ROUND_SIZE( max( commitSize, REGION_ALIGN ), REGION_ALIGN - 1 ); + totalSize = min( max( commitSize, totalSize ), 0xffff0000 ); /* don't allow a heap larger than 4GB */

/* allocate the memory block */ - if (NtAllocateVirtualMemory( NtCurrentProcess(), &address, 0, &totalSize, MEM_RESERVE, - get_protection_type( flags ) )) - { - WARN( "Could not allocate %#Ix bytes\n", totalSize ); - return NULL; - } - if (NtAllocateVirtualMemory( NtCurrentProcess(), &address, 0, &commitSize, MEM_COMMIT, - get_protection_type( flags ) )) - { - WARN( "Could not commit %#Ix bytes for sub-heap %p\n", commitSize, address ); - return NULL; - } + if (!heap) flags |= HEAP_GROWABLE; + if (allocate_region( flags, &commitSize, &totalSize, &address )) return NULL; }

if (heap)

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:05 p.m.

New subject: [PATCH 02/15] ntdll: Move heap allocation and initialization into RtlCreateHeap.

From: Rémi Bernon rbernon@codeweavers.com

And rename HEAP_CreateSubHeap to create_subheap. --- dlls/ntdll/heap.c | 154 ++++++++++++++++++++-------------------------- 1 file changed, 68 insertions(+), 86 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index af95e78d7e9..21ae5996dfd 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -945,90 +945,23 @@ static BOOL validate_large_block( const struct heap *heap, const struct block *b return !err; }

-/*********************************************************************** - * HEAP_CreateSubHeap - */ -static SUBHEAP *HEAP_CreateSubHeap( struct heap **heap_ptr, LPVOID address, DWORD flags, - SIZE_T commitSize, SIZE_T totalSize ) + +static SUBHEAP *create_subheap( struct heap *heap, DWORD flags, SIZE_T commit_size, SIZE_T total_size ) { - struct heap *heap = *heap_ptr; - struct entry *pEntry; SIZE_T block_size; SUBHEAP *subheap; - unsigned int i; - - if (!address) - { - commitSize = ROUND_SIZE( max( commitSize, REGION_ALIGN ), REGION_ALIGN - 1 ); - totalSize = min( max( commitSize, totalSize ), 0xffff0000 ); /* don't allow a heap larger than 4GB */ - - /* allocate the memory block */ - if (!heap) flags |= HEAP_GROWABLE; - if (allocate_region( flags, &commitSize, &totalSize, &address )) return NULL; - } - - if (heap) - { - /* If this is a secondary subheap, insert it into list */ - - subheap = address; - subheap_set_bounds( subheap, (char *)address + commitSize, (char *)address + totalSize ); - list_add_head( &heap->subheap_list, &subheap->entry ); - } - else - { - /* If this is a primary subheap, initialize main heap */

- heap = address; - heap->ffeeffee = 0xffeeffee; - heap->auto_flags = (flags & HEAP_GROWABLE); - heap->flags = (flags & ~HEAP_SHARED); - heap->magic = HEAP_MAGIC; - heap->grow_size = max( HEAP_DEF_SIZE, totalSize ); - heap->min_size = commitSize; - list_init( &heap->subheap_list ); - list_init( &heap->large_list ); + commit_size = ROUND_SIZE( max( commit_size, REGION_ALIGN ), REGION_ALIGN - 1 ); + total_size = min( max( commit_size, total_size ), 0xffff0000 ); /* don't allow a heap larger than 4GB */

- subheap = &heap->subheap; - subheap_set_bounds( subheap, (char *)address + commitSize, (char *)address + totalSize ); - list_add_head( &heap->subheap_list, &subheap->entry ); + if (allocate_region( flags, &commit_size, &total_size, (void **)&subheap )) return NULL;

- /* Build the free lists */ - - list_init( &heap->free_lists[0].entry ); - for (i = 0, pEntry = heap->free_lists; i < HEAP_NB_FREE_LISTS; i++, pEntry++) - { - block_set_flags( &pEntry->block, ~0, BLOCK_FLAG_FREE_LINK ); - block_set_size( &pEntry->block, 0 ); - block_set_type( &pEntry->block, BLOCK_TYPE_FREE ); - block_set_base( &pEntry->block, heap ); - if (i) list_add_after( &pEntry[-1].entry, &pEntry->entry ); - } - - /* Initialize critical section */ - - if (!process_heap) /* do it by hand to avoid memory allocations */ - { - heap->cs.DebugInfo = &process_heap_cs_debug; - heap->cs.LockCount = -1; - heap->cs.RecursionCount = 0; - heap->cs.OwningThread = 0; - heap->cs.LockSemaphore = 0; - heap->cs.SpinCount = 0; - process_heap_cs_debug.CriticalSection = &heap->cs; - } - else - { - RtlInitializeCriticalSection( &heap->cs ); - heap->cs.DebugInfo->Spare[0] = (DWORD_PTR)(__FILE__ ": heap.cs"); - } - } + subheap_set_bounds( subheap, (char *)subheap + commit_size, (char *)subheap + total_size ); + list_add_head( &heap->subheap_list, &subheap->entry );

- block_size = subheap_size( subheap ) - subheap_overhead( subheap ); - block_size &= ~(BLOCK_ALIGN - 1); + block_size = (SIZE_T)ROUND_ADDR( subheap_size( subheap ) - subheap_overhead( subheap ), BLOCK_ALIGN - 1 ); create_free_block( heap, flags, subheap, first_block( subheap ), block_size );

- *heap_ptr = heap; return subheap; }

@@ -1068,8 +1001,7 @@ static struct block *find_free_block( struct heap *heap, ULONG flags, SIZE_T blo total_size = sizeof(SUBHEAP) + block_size + sizeof(struct entry); if (total_size < block_size) return NULL; /* overflow */

- if ((subheap = HEAP_CreateSubHeap( &heap, NULL, flags, total_size, - max( heap->grow_size, total_size ) ))) + if ((subheap = create_subheap( heap, flags, total_size, max( heap->grow_size, total_size ) ))) { if (heap->grow_size <= HEAP_MAX_FREE_BLOCK_SIZE / 2) heap->grow_size *= 2; } @@ -1077,8 +1009,7 @@ static struct block *find_free_block( struct heap *heap, ULONG flags, SIZE_T blo { if (heap->grow_size <= total_size || heap->grow_size <= 4 * 1024 * 1024) return NULL; heap->grow_size /= 2; - subheap = HEAP_CreateSubHeap( &heap, NULL, flags, total_size, - max( heap->grow_size, total_size ) ); + subheap = create_subheap( heap, flags, total_size, max( heap->grow_size, total_size ) ); }

TRACE( "created new sub-heap %p of %#Ix bytes for heap %p\n", subheap, subheap_size( subheap ), heap ); @@ -1399,20 +1330,71 @@ static void heap_set_debug_flags( HANDLE handle ) * Success: A HANDLE to the newly created heap. * Failure: a NULL HANDLE. */ -HANDLE WINAPI RtlCreateHeap( ULONG flags, PVOID addr, SIZE_T totalSize, SIZE_T commitSize, - PVOID unknown, PRTL_HEAP_DEFINITION definition ) +HANDLE WINAPI RtlCreateHeap( ULONG flags, void *addr, SIZE_T total_size, SIZE_T commit_size, + void *unknown, RTL_HEAP_DEFINITION *definition ) { - struct heap *heap = NULL; + struct entry *entry; + struct heap *heap; + SIZE_T block_size; SUBHEAP *subheap; + unsigned int i;

- /* Allocate the heap block */ + TRACE( "flags %#lx, addr %p, total_size %#Ix, commit_size %#Ix, unknown %p, definition %p\n", + flags, addr, total_size, commit_size, unknown, definition );

flags &= ~(HEAP_TAIL_CHECKING_ENABLED|HEAP_FREE_CHECKING_ENABLED); if (process_heap) flags |= HEAP_PRIVATE; - if (!process_heap || !totalSize || (flags & HEAP_SHARED)) flags |= HEAP_GROWABLE; - if (!totalSize) totalSize = HEAP_DEF_SIZE; + if (!process_heap || !total_size || (flags & HEAP_SHARED)) flags |= HEAP_GROWABLE; + if (!total_size) total_size = HEAP_DEF_SIZE; + + if (!(heap = addr)) + { + commit_size = ROUND_SIZE( max( commit_size, REGION_ALIGN ), REGION_ALIGN - 1 ); + total_size = min( max( commit_size, total_size ), 0xffff0000 ); /* don't allow a heap larger than 4GB */ + if (allocate_region( flags | HEAP_GROWABLE, &commit_size, &total_size, (void **)&heap )) return 0; + } + + heap->ffeeffee = 0xffeeffee; + heap->auto_flags = (flags & HEAP_GROWABLE); + heap->flags = (flags & ~HEAP_SHARED); + heap->magic = HEAP_MAGIC; + heap->grow_size = max( HEAP_DEF_SIZE, total_size ); + heap->min_size = commit_size; + list_init( &heap->subheap_list ); + list_init( &heap->large_list );

- if (!(subheap = HEAP_CreateSubHeap( &heap, addr, flags, commitSize, totalSize ))) return 0; + subheap = &heap->subheap; + subheap_set_bounds( subheap, (char *)heap + commit_size, (char *)heap + total_size ); + list_add_head( &heap->subheap_list, &subheap->entry ); + + list_init( &heap->free_lists[0].entry ); + for (i = 0, entry = heap->free_lists; i < HEAP_NB_FREE_LISTS; i++, entry++) + { + block_set_flags( &entry->block, ~0, BLOCK_FLAG_FREE_LINK ); + block_set_size( &entry->block, 0 ); + block_set_type( &entry->block, BLOCK_TYPE_FREE ); + block_set_base( &entry->block, heap ); + if (i) list_add_after( &entry[-1].entry, &entry->entry ); + } + + if (!process_heap) /* do it by hand to avoid memory allocations */ + { + heap->cs.DebugInfo = &process_heap_cs_debug; + heap->cs.LockCount = -1; + heap->cs.RecursionCount = 0; + heap->cs.OwningThread = 0; + heap->cs.LockSemaphore = 0; + heap->cs.SpinCount = 0; + process_heap_cs_debug.CriticalSection = &heap->cs; + } + else + { + RtlInitializeCriticalSection( &heap->cs ); + heap->cs.DebugInfo->Spare[0] = (DWORD_PTR)(__FILE__ ": heap.cs"); + } + + block_size = (SIZE_T)ROUND_ADDR( subheap_size( subheap ) - subheap_overhead( subheap ), BLOCK_ALIGN - 1 ); + create_free_block( heap, flags, subheap, first_block( subheap ), block_size );

heap_set_debug_flags( heap );

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:05 p.m.

New subject: [PATCH 03/15] ntdll: Clear BLOCK_FLAG_PREV_FREE flag out of shrink_used_block.

From: Rémi Bernon rbernon@codeweavers.com

--- dlls/ntdll/heap.c | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index 21ae5996dfd..2039f51f3ab 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -824,10 +824,8 @@ static inline void shrink_used_block( struct heap *heap, ULONG flags, struct blo } else { - struct block *next; block_set_size( block, old_block_size ); block->tail_size = old_block_size - sizeof(*block) - size; - if ((next = next_block( subheap, block ))) block_set_flags( next, BLOCK_FLAG_PREV_FREE, 0 ); } }

@@ -1511,14 +1509,16 @@ static SIZE_T heap_get_block_size( const struct heap *heap, ULONG flags, SIZE_T

static NTSTATUS heap_allocate_block( struct heap *heap, ULONG flags, SIZE_T block_size, SIZE_T size, void **ret ) { + struct block *block, *next; SIZE_T old_block_size; - struct block *block; + SUBHEAP *subheap;

/* Locate a suitable free block */

if (!(block = find_free_block( heap, flags, block_size ))) return STATUS_NO_MEMORY; /* read the free block size, changing block type or flags may alter it */ old_block_size = block_get_size( block ); + subheap = block_get_subheap( heap, block );

block_set_type( block, BLOCK_TYPE_USED ); block_set_flags( block, ~0, BLOCK_USER_FLAGS( flags ) ); @@ -1526,6 +1526,8 @@ static NTSTATUS heap_allocate_block( struct heap *heap, ULONG flags, SIZE_T bloc initialize_block( block, 0, size, flags ); mark_block_tail( block, flags );

+ if ((next = next_block( subheap, block ))) block_set_flags( next, BLOCK_FLAG_PREV_FREE, 0 ); + *ret = block + 1; return STATUS_SUCCESS; } @@ -1653,10 +1655,11 @@ static NTSTATUS heap_resize_block( struct heap *heap, ULONG flags, struct block valgrind_notify_resize( block + 1, *old_size, size ); block_set_flags( block, BLOCK_FLAG_USER_MASK & ~BLOCK_FLAG_USER_INFO, BLOCK_USER_FLAGS( flags ) ); shrink_used_block( heap, flags, block, old_block_size, block_size, size ); - initialize_block( block, *old_size, size, flags ); mark_block_tail( block, flags );

+ if ((next = next_block( subheap, block ))) block_set_flags( next, BLOCK_FLAG_PREV_FREE, 0 ); + heap_unlock( heap, flags );

*ret = block + 1;

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:05 p.m.

New subject: [PATCH 04/15] ntdll: Split heap blocks before creating or resizing used block.

From: Rémi Bernon rbernon@codeweavers.com

--- dlls/ntdll/heap.c | 25 ++++++++++++++----------- 1 file changed, 14 insertions(+), 11 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index 2039f51f3ab..84f171f449c 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -811,22 +811,19 @@ static NTSTATUS heap_free_block( struct heap *heap, ULONG flags, struct block *b }

-static inline void shrink_used_block( struct heap *heap, ULONG flags, struct block *block, - SIZE_T old_block_size, SIZE_T block_size, SIZE_T size ) +static struct block *split_block( struct heap *heap, ULONG flags, struct block *block, + SIZE_T old_block_size, SIZE_T block_size ) { SUBHEAP *subheap = block_get_subheap( heap, block );

if (old_block_size >= block_size + HEAP_MIN_BLOCK_SIZE) { block_set_size( block, block_size ); - block->tail_size = block_size - sizeof(*block) - size; - create_free_block( heap, flags, subheap, next_block( subheap, block ), old_block_size - block_size ); - } - else - { - block_set_size( block, old_block_size ); - block->tail_size = old_block_size - sizeof(*block) - size; + return next_block( subheap, block ); } + + block_set_size( block, old_block_size ); + return NULL; }

@@ -1520,9 +1517,12 @@ static NTSTATUS heap_allocate_block( struct heap *heap, ULONG flags, SIZE_T bloc old_block_size = block_get_size( block ); subheap = block_get_subheap( heap, block );

+ if ((next = split_block( heap, flags, block, old_block_size, block_size ))) + create_free_block( heap, flags, subheap, next, old_block_size - block_size ); + block_set_type( block, BLOCK_TYPE_USED ); block_set_flags( block, ~0, BLOCK_USER_FLAGS( flags ) ); - shrink_used_block( heap, flags, block, old_block_size, block_size, size ); + block->tail_size = block_get_size( block ) - sizeof(*block) - size; initialize_block( block, 0, size, flags ); mark_block_tail( block, flags );

@@ -1652,9 +1652,12 @@ static NTSTATUS heap_resize_block( struct heap *heap, ULONG flags, struct block old_block_size += block_get_size( next ); }

+ if ((next = split_block( heap, flags, block, old_block_size, block_size ))) + create_free_block( heap, flags, subheap, next, old_block_size - block_size ); + valgrind_notify_resize( block + 1, *old_size, size ); block_set_flags( block, BLOCK_FLAG_USER_MASK & ~BLOCK_FLAG_USER_INFO, BLOCK_USER_FLAGS( flags ) ); - shrink_used_block( heap, flags, block, old_block_size, block_size, size ); + block->tail_size = block_get_size( block ) - sizeof(*block) - size; initialize_block( block, *old_size, size, flags ); mark_block_tail( block, flags );

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:05 p.m.

New subject: [PATCH 05/15] ntdll: Merge prev and next free heap blocks in heap_free_block.

From: Rémi Bernon rbernon@codeweavers.com

As create_free_block is only called in other places where it is not possible to have a free block either before or after. --- dlls/ntdll/heap.c | 50 +++++++++++++++++++++-------------------------- 1 file changed, 22 insertions(+), 28 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index 84f171f449c..411ea2a0c53 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -725,16 +725,6 @@ static void create_free_block( struct heap *heap, ULONG flags, SUBHEAP *subheap, if (end > commit_end) end = commit_end; if (end > (char *)(entry + 1)) mark_block_free( entry + 1, end - (char *)(entry + 1), flags );

- if ((next = next_block( subheap, block )) && (block_get_flags( next ) & BLOCK_FLAG_FREE)) - { - /* merge with the next block if it is free */ - struct entry *next_entry = (struct entry *)next; - list_remove( &next_entry->entry ); - block_size += block_get_size( next ); - block_set_size( block, block_size ); - mark_block_free( next_entry, sizeof(*next_entry), flags ); - } - if ((next = next_block( subheap, block ))) { /* set the next block PREV_FREE flag and back pointer */ @@ -772,40 +762,44 @@ static struct block *heap_delay_free( struct heap *heap, ULONG flags, struct blo

static NTSTATUS heap_free_block( struct heap *heap, ULONG flags, struct block *block ) { + SUBHEAP *subheap = block_get_subheap( heap, block ); + SIZE_T block_size = block_get_size( block ); struct entry *entry; - SIZE_T block_size; - SUBHEAP *subheap; + struct block *next; + + if ((next = next_block( subheap, block )) && (block_get_flags( next ) & BLOCK_FLAG_FREE)) + { + /* merge with next block if it is free */ + entry = (struct entry *)next; + block_size += block_get_size( &entry->block ); + list_remove( &entry->entry ); + next = next_block( subheap, next ); + }

- block_size = block_get_size( block ); if (block_get_flags( block ) & BLOCK_FLAG_PREV_FREE) { /* merge with previous block if it is free */ - block = *((struct block **)block - 1); - block_size += block_get_size( block ); - entry = (struct entry *)block; + entry = *((struct entry **)block - 1); + block_size += block_get_size( &entry->block ); list_remove( &entry->entry ); + block = &entry->block; } - else entry = (struct entry *)block;

- subheap = block_get_subheap( heap, block ); - create_free_block( heap, flags, subheap, block, block_size ); - if (next_block( subheap, block )) return STATUS_SUCCESS; /* not the last block */ - - if (block == first_block( subheap ) && subheap != &heap->subheap) + if (block == first_block( subheap ) && !next && subheap != &heap->subheap) { /* free the subheap if it's empty and not the main one */ void *addr = subheap_base( subheap ); SIZE_T size = 0;

- list_remove( &entry->entry ); list_remove( &subheap->entry ); NtFreeVirtualMemory( NtCurrentProcess(), &addr, &size, MEM_RELEASE ); + return STATUS_SUCCESS; } - else - { - /* keep room for a full committed block as hysteresis */ - subheap_decommit( heap, subheap, (char *)(entry + 1) + REGION_ALIGN ); - } + + create_free_block( heap, flags, subheap, block, block_size ); + + /* keep room for a full committed block as hysteresis */ + if (!next) subheap_decommit( heap, subheap, (char *)((struct entry *)block + 1) + REGION_ALIGN );

return STATUS_SUCCESS; }

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:05 p.m.

New subject: [PATCH 06/15] ntdll: Split create_free_block into block_init_free / insert_free_block.

From: Rémi Bernon rbernon@codeweavers.com

--- dlls/ntdll/heap.c | 31 ++++++++++++++++++++++--------- 1 file changed, 22 insertions(+), 9 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index 411ea2a0c53..b0b2695065e 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -707,12 +707,10 @@ static inline BOOL subheap_decommit( const struct heap *heap, SUBHEAP *subheap, return TRUE; }

- -static void create_free_block( struct heap *heap, ULONG flags, SUBHEAP *subheap, struct block *block, SIZE_T block_size ) +static void block_init_free( struct block *block, ULONG flags, SUBHEAP *subheap, SIZE_T block_size ) { const char *end = (char *)block + block_size, *commit_end = subheap_commit_end( subheap ); - struct entry *entry = (struct entry *)block, *list; - struct block *next; + struct entry *entry = (struct entry *)block;

valgrind_make_writable( block, sizeof(*entry) ); block_set_type( block, BLOCK_TYPE_FREE ); @@ -724,6 +722,12 @@ static void create_free_block( struct heap *heap, ULONG flags, SUBHEAP *subheap,

if (end > commit_end) end = commit_end; if (end > (char *)(entry + 1)) mark_block_free( entry + 1, end - (char *)(entry + 1), flags ); +} + +static void insert_free_block( struct heap *heap, ULONG flags, SUBHEAP *subheap, struct block *block ) +{ + struct entry *entry = (struct entry *)block, *list; + struct block *next;

if ((next = next_block( subheap, block ))) { @@ -796,7 +800,8 @@ static NTSTATUS heap_free_block( struct heap *heap, ULONG flags, struct block *b return STATUS_SUCCESS; }

- create_free_block( heap, flags, subheap, block, block_size ); + block_init_free( block, flags, subheap, block_size ); + insert_free_block( heap, flags, subheap, block );

/* keep room for a full committed block as hysteresis */ if (!next) subheap_decommit( heap, subheap, (char *)((struct entry *)block + 1) + REGION_ALIGN ); @@ -949,7 +954,8 @@ static SUBHEAP *create_subheap( struct heap *heap, DWORD flags, SIZE_T commit_si list_add_head( &heap->subheap_list, &subheap->entry );

block_size = (SIZE_T)ROUND_ADDR( subheap_size( subheap ) - subheap_overhead( subheap ), BLOCK_ALIGN - 1 ); - create_free_block( heap, flags, subheap, first_block( subheap ), block_size ); + block_init_free( first_block( subheap ), flags, subheap, block_size ); + insert_free_block( heap, flags, subheap, first_block( subheap ) );

return subheap; } @@ -1383,7 +1389,8 @@ HANDLE WINAPI RtlCreateHeap( ULONG flags, void *addr, SIZE_T total_size, SIZE_T }

heap_set_debug_flags( heap );

@@ -1512,7 +1519,10 @@ static NTSTATUS heap_allocate_block( struct heap *heap, ULONG flags, SIZE_T bloc subheap = block_get_subheap( heap, block );

if ((next = split_block( heap, flags, block, old_block_size, block_size ))) - create_free_block( heap, flags, subheap, next, old_block_size - block_size ); + { + block_init_free( next, flags, subheap, old_block_size - block_size ); + insert_free_block( heap, flags, subheap, next ); + }

block_set_type( block, BLOCK_TYPE_USED ); block_set_flags( block, ~0, BLOCK_USER_FLAGS( flags ) ); @@ -1647,7 +1657,10 @@ static NTSTATUS heap_resize_block( struct heap *heap, ULONG flags, struct block }

valgrind_notify_resize( block + 1, *old_size, size ); block_set_flags( block, BLOCK_FLAG_USER_MASK & ~BLOCK_FLAG_USER_INFO, BLOCK_USER_FLAGS( flags ) );

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:05 p.m.

New subject: [PATCH 07/15] ntdll: Move the insertion of the first block out of create_subheap.

From: Rémi Bernon rbernon@codeweavers.com

--- dlls/ntdll/heap.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index b0b2695065e..7cc849749d8 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -955,7 +955,6 @@ static SUBHEAP *create_subheap( struct heap *heap, DWORD flags, SIZE_T commit_si

block_size = (SIZE_T)ROUND_ADDR( subheap_size( subheap ) - subheap_overhead( subheap ), BLOCK_ALIGN - 1 ); block_init_free( first_block( subheap ), flags, subheap, block_size ); - insert_free_block( heap, flags, subheap, first_block( subheap ) );

return subheap; } @@ -1009,9 +1008,7 @@ static struct block *find_free_block( struct heap *heap, ULONG flags, SIZE_T blo

TRACE( "created new sub-heap %p of %#Ix bytes for heap %p\n", subheap, subheap_size( subheap ), heap );

- entry = first_block( subheap ); - list_remove( &entry->entry ); - return &entry->block; + return first_block( subheap ); }

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:05 p.m.

New subject: [PATCH 08/15] ntdll: Implement HeapCompatibilityInformation.

From: Rémi Bernon rbernon@codeweavers.com

--- dlls/kernel32/tests/heap.c | 10 ------- dlls/ntdll/heap.c | 56 ++++++++++++++++++++++++++++++++------ 2 files changed, 47 insertions(+), 19 deletions(-)

diff --git a/dlls/kernel32/tests/heap.c b/dlls/kernel32/tests/heap.c index a81cb1b7a15..29faf8c902e 100644 --- a/dlls/kernel32/tests/heap.c +++ b/dlls/kernel32/tests/heap.c @@ -827,11 +827,8 @@ static void test_HeapCreate(void) size = 0; SetLastError( 0xdeadbeef ); ret = pHeapQueryInformation( 0, HeapCompatibilityInformation, &compat_info, sizeof(compat_info), &size ); - todo_wine ok( !ret, "HeapQueryInformation succeeded\n" ); - todo_wine ok( GetLastError() == ERROR_NOACCESS, "got error %lu\n", GetLastError() ); - todo_wine ok( size == 0, "got size %Iu\n", size );

size = 0; @@ -871,7 +868,6 @@ static void test_HeapCreate(void) ok( ret, "HeapSetInformation failed, error %lu\n", GetLastError() ); ret = pHeapQueryInformation( heap, HeapCompatibilityInformation, &compat_info, sizeof(compat_info), &size ); ok( ret, "HeapQueryInformation failed, error %lu\n", GetLastError() ); - todo_wine ok( compat_info == 2, "got HeapCompatibilityInformation %lu\n", compat_info );

/* cannot be undone */ @@ -879,20 +875,15 @@ static void test_HeapCreate(void) compat_info = 0; SetLastError( 0xdeadbeef ); ret = pHeapSetInformation( heap, HeapCompatibilityInformation, &compat_info, sizeof(compat_info) ); - todo_wine ok( !ret, "HeapSetInformation succeeded\n" ); - todo_wine ok( GetLastError() == ERROR_GEN_FAILURE, "got error %lu\n", GetLastError() ); compat_info = 1; SetLastError( 0xdeadbeef ); ret = pHeapSetInformation( heap, HeapCompatibilityInformation, &compat_info, sizeof(compat_info) ); - todo_wine ok( !ret, "HeapSetInformation succeeded\n" ); - todo_wine ok( GetLastError() == ERROR_GEN_FAILURE, "got error %lu\n", GetLastError() ); ret = pHeapQueryInformation( heap, HeapCompatibilityInformation, &compat_info, sizeof(compat_info), &size ); ok( ret, "HeapQueryInformation failed, error %lu\n", GetLastError() ); - todo_wine ok( compat_info == 2, "got HeapCompatibilityInformation %lu\n", compat_info );

ret = HeapDestroy( heap ); @@ -931,7 +922,6 @@ static void test_HeapCreate(void) ok( ret, "HeapSetInformation failed, error %lu\n", GetLastError() ); ret = pHeapQueryInformation( heap, HeapCompatibilityInformation, &compat_info, sizeof(compat_info), &size ); ok( ret, "HeapQueryInformation failed, error %lu\n", GetLastError() ); - todo_wine ok( compat_info == 2, "got HeapCompatibilityInformation %lu\n", compat_info );

for (i = 0; i < 0x11; i++) ptrs[i] = pHeapAlloc( heap, 0, 24 + 2 * sizeof(void *) ); diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index 7cc849749d8..c821ce38f7b 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -39,6 +39,13 @@

WINE_DEFAULT_DEBUG_CHANNEL(heap);

+/* HeapCompatibilityInformation values */ + +#define HEAP_STD 0 +#define HEAP_LAL 1 +#define HEAP_LFH 2 + + /* undocumented RtlWalkHeap structure */

struct rtl_heap_entry @@ -194,6 +201,7 @@ struct heap DWORD force_flags; /* 0044/0074 */ /* end of the Windows 10 compatible struct layout */

+ LONG compat_info; /* HeapCompatibilityInformation / heap frontend type */ struct list entry; /* Entry in process heap list */ struct list subheap_list; /* Sub-heap list */ struct list large_list; /* Large blocks list */ @@ -1349,6 +1357,7 @@ HANDLE WINAPI RtlCreateHeap( ULONG flags, void *addr, SIZE_T total_size, SIZE_T heap->ffeeffee = 0xffeeffee; heap->auto_flags = (flags & HEAP_GROWABLE); heap->flags = (flags & ~HEAP_SHARED); + heap->compat_info = HEAP_STD; heap->magic = HEAP_MAGIC; heap->grow_size = max( HEAP_DEF_SIZE, total_size ); heap->min_size = commit_size; @@ -2009,21 +2018,24 @@ ULONG WINAPI RtlGetProcessHeaps( ULONG count, HANDLE *heaps ) * RtlQueryHeapInformation (NTDLL.@) */ NTSTATUS WINAPI RtlQueryHeapInformation( HANDLE handle, HEAP_INFORMATION_CLASS info_class, - void *info, SIZE_T size_in, PSIZE_T size_out ) + void *info, SIZE_T size_in, SIZE_T *size_out ) { + struct heap *heap; + ULONG flags; + + TRACE( "handle %p, info_class %u, info %p, size_in %Iu, size_out %p.\n", handle, info_class, info, size_in, size_out ); + switch (info_class) { case HeapCompatibilityInformation: + if (!(heap = unsafe_heap_from_handle( handle, 0, &flags ))) return STATUS_ACCESS_VIOLATION; if (size_out) *size_out = sizeof(ULONG); - - if (size_in < sizeof(ULONG)) - return STATUS_BUFFER_TOO_SMALL; - - *(ULONG *)info = 0; /* standard heap */ + if (size_in < sizeof(ULONG)) return STATUS_BUFFER_TOO_SMALL; + *(ULONG *)info = heap->compat_info; return STATUS_SUCCESS;

default: - FIXME("Unknown heap information class %u\n", info_class); + FIXME( "HEAP_INFORMATION_CLASS %u not implemented!\n", info_class ); return STATUS_INVALID_INFO_CLASS; } } @@ -2033,8 +2045,34 @@ NTSTATUS WINAPI RtlQueryHeapInformation( HANDLE handle, HEAP_INFORMATION_CLASS i */ NTSTATUS WINAPI RtlSetHeapInformation( HANDLE handle, HEAP_INFORMATION_CLASS info_class, void *info, SIZE_T size ) { - FIXME( "handle %p, info_class %d, info %p, size %Id stub!\n", handle, info_class, info, size ); - return STATUS_SUCCESS; + struct heap *heap; + ULONG flags; + + TRACE( "handle %p, info_class %u, info %p, size %Iu.\n", handle, info_class, info, size ); + + switch (info_class) + { + case HeapCompatibilityInformation: + { + ULONG compat_info; + + if (size < sizeof(ULONG)) return STATUS_BUFFER_TOO_SMALL; + if (!(heap = unsafe_heap_from_handle( handle, 0, &flags ))) return STATUS_INVALID_HANDLE; + + compat_info = *(ULONG *)info; + if (compat_info != HEAP_STD && compat_info != HEAP_LFH) + { + FIXME( "HeapCompatibilityInformation %lu not implemented!\n", compat_info ); + return STATUS_UNSUCCESSFUL; + } + if (InterlockedCompareExchange( &heap->compat_info, compat_info, HEAP_STD )) return STATUS_UNSUCCESSFUL; + return STATUS_SUCCESS; + } + + default: + FIXME( "HEAP_INFORMATION_CLASS %u not implemented!\n", info_class ); + return STATUS_SUCCESS; + } }

/***********************************************************************

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:05 p.m.

New subject: [PATCH 09/15] ntdll: Count allocations and automatically enable LFH.

From: Rémi Bernon rbernon@codeweavers.com

--- dlls/kernel32/tests/heap.c | 2 -- dlls/ntdll/heap.c | 49 +++++++++++++++++++++++++++++++++++++- 2 files changed, 48 insertions(+), 3 deletions(-)

diff --git a/dlls/kernel32/tests/heap.c b/dlls/kernel32/tests/heap.c index 29faf8c902e..ed84441efe0 100644 --- a/dlls/kernel32/tests/heap.c +++ b/dlls/kernel32/tests/heap.c @@ -904,7 +904,6 @@ static void test_HeapCreate(void)

ret = pHeapQueryInformation( heap, HeapCompatibilityInformation, &compat_info, sizeof(compat_info), &size ); ok( ret, "HeapQueryInformation failed, error %lu\n", GetLastError() ); - todo_wine ok( compat_info == 2, "got HeapCompatibilityInformation %lu\n", compat_info );

ret = HeapDestroy( heap ); @@ -1195,7 +1194,6 @@ static void test_HeapCreate(void)

/* locking is serialized */ diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index c821ce38f7b..a92c0bbacd0 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -149,6 +149,27 @@ C_ASSERT( sizeof(ARENA_LARGE) == 4 * BLOCK_ALIGN ); C_ASSERT( sizeof(struct block) <= HEAP_MIN_BLOCK_SIZE ); C_ASSERT( sizeof(struct entry) <= HEAP_MIN_BLOCK_SIZE );

+/* block size categories for LFH */ + +#define BLOCK_SIZE_SMALL_MAX (16 * HEAP_MIN_BLOCK_SIZE) +#define BLOCK_SIZE_MEDIUM_STEP (12 * BLOCK_ALIGN) +#define BLOCK_SIZE_CATEGORY_SMALL(size) (((size) - HEAP_MIN_BLOCK_SIZE) / BLOCK_ALIGN) +#define BLOCK_SIZE_CATEGORY_MEDIUM(size) (BLOCK_SIZE_CATEGORY_SMALL(BLOCK_SIZE_SMALL_MAX) + ((size) - (BLOCK_SIZE_SMALL_MAX)) / BLOCK_SIZE_MEDIUM_STEP) +#define BLOCK_SIZE_CATEGORY(size) (((size) >= BLOCK_SIZE_SMALL_MAX) ? BLOCK_SIZE_CATEGORY_MEDIUM(size) : BLOCK_SIZE_CATEGORY_SMALL(size)) +#define BLOCK_SIZE_CATEGORY_COUNT BLOCK_SIZE_CATEGORY(0x400 * BLOCK_ALIGN) +#define BLOCK_SIZE_MEDIUM_MIN (BLOCK_SIZE_SMALL_MAX + BLOCK_SIZE_MEDIUM_STEP - BLOCK_ALIGN) + +#define BLOCK_CATEGORY_SIZE(category) (category >= BLOCK_SIZE_CATEGORY_MEDIUM(BLOCK_SIZE_SMALL_MAX) \ + ? (BLOCK_SIZE_MEDIUM_MIN + (category - BLOCK_SIZE_CATEGORY_MEDIUM(BLOCK_SIZE_SMALL_MAX)) * BLOCK_SIZE_MEDIUM_STEP) \ + : (HEAP_MIN_BLOCK_SIZE + category * BLOCK_ALIGN)) + +C_ASSERT( BLOCK_SIZE_CATEGORY(HEAP_MIN_BLOCK_SIZE) == 0 ); +C_ASSERT( BLOCK_SIZE_CATEGORY_SMALL(BLOCK_SIZE_SMALL_MAX - 1) == 44 ); +C_ASSERT( BLOCK_SIZE_CATEGORY_MEDIUM(BLOCK_SIZE_SMALL_MAX) == 45 ); +C_ASSERT( BLOCK_SIZE_CATEGORY_COUNT == 126 ); + +/* difference between block classes must fit into block tail_size */ +C_ASSERT( BLOCK_CATEGORY_SIZE(126) - BLOCK_CATEGORY_SIZE(125) <= FIELD_MAX( struct block, tail_size ) ); /* used block size is coded into block_size */ #define HEAP_MAX_USED_BLOCK_SIZE (FIELD_MAX( struct block, block_size ) * BLOCK_ALIGN) /* free block size is coded into block_size + tail_size */ @@ -201,6 +222,7 @@ struct heap DWORD force_flags; /* 0044/0074 */ /* end of the Windows 10 compatible struct layout */

+ volatile BYTE stats[BLOCK_SIZE_CATEGORY_COUNT]; /* Stats counter for LFH activation */ LONG compat_info; /* HeapCompatibilityInformation / heap frontend type */ struct list entry; /* Entry in process heap list */ struct list subheap_list; /* Sub-heap list */ @@ -774,11 +796,13 @@ static struct block *heap_delay_free( struct heap *heap, ULONG flags, struct blo

static NTSTATUS heap_free_block( struct heap *heap, ULONG flags, struct block *block ) { + SIZE_T block_size = block_get_size( block ), category = BLOCK_SIZE_CATEGORY(block_size); SUBHEAP *subheap = block_get_subheap( heap, block ); - SIZE_T block_size = block_get_size( block ); struct entry *entry; struct block *next;

+ if (category < ARRAY_SIZE(heap->stats) && heap->stats[category] <= 0x10) heap->stats[category]--; + if ((next = next_block( subheap, block )) && (block_get_flags( next ) & BLOCK_FLAG_FREE)) { /* merge with next block if it is free */ @@ -1511,6 +1535,27 @@ static SIZE_T heap_get_block_size( const struct heap *heap, ULONG flags, SIZE_T return block_size; }

+static NTSTATUS heap_allocate_block_lfh( struct heap *heap, ULONG flags, SIZE_T block_size, + SIZE_T size, void **ret ) +{ + SIZE_T category = BLOCK_SIZE_CATEGORY( block_size ); + + if (category >= ARRAY_SIZE(heap->stats)) return STATUS_UNSUCCESSFUL; + if (heap->stats[category] <= 0x10) + { + heap->stats[category]++; + return STATUS_UNSUCCESSFUL; + } + if (heap->compat_info != HEAP_LFH) + { + ULONG info = HEAP_LFH; + RtlSetHeapInformation( heap, HeapCompatibilityInformation, &info, sizeof(info) ); + return STATUS_UNSUCCESSFUL; + } + + return STATUS_NOT_CAPABLE; +} + static NTSTATUS heap_allocate_block( struct heap *heap, ULONG flags, SIZE_T block_size, SIZE_T size, void **ret ) { struct block *block, *next; @@ -1559,6 +1604,8 @@ void *WINAPI DECLSPEC_HOTPATCH RtlAllocateHeap( HANDLE handle, ULONG flags, SIZE status = STATUS_NO_MEMORY; else if (block_size >= HEAP_MIN_LARGE_BLOCK_SIZE) status = heap_allocate_large( heap, heap_flags, block_size, size, &ptr ); + else if (!heap_allocate_block_lfh( heap, heap_flags, block_size, size, &ptr )) + status = STATUS_SUCCESS; else { heap_lock( heap, heap_flags );

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:05 p.m.

New subject: [PATCH 10/15] ntdll: Introduce a new heap free_list_init helper.

From: Rémi Bernon rbernon@codeweavers.com

--- dlls/ntdll/heap.c | 26 ++++++++++++++++++-------- 1 file changed, 18 insertions(+), 8 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index a92c0bbacd0..d80b939d6b7 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -502,7 +502,7 @@ static inline struct entry *find_free_list( struct heap *heap, SIZE_T block_size

if (block_size <= HEAP_MAX_SMALL_FREE_LIST) i = (block_size - HEAP_MIN_BLOCK_SIZE) / BLOCK_ALIGN; - else for (i = HEAP_NB_SMALL_FREE_LISTS; i < HEAP_NB_FREE_LISTS - 1; i++) + else for (i = HEAP_NB_SMALL_FREE_LISTS; i < ARRAY_SIZE(heap->free_lists) - 1; i++) if (block_size <= free_list_sizes[i - HEAP_NB_SMALL_FREE_LISTS]) break;

list = heap->free_lists + i; @@ -510,6 +510,15 @@ static inline struct entry *find_free_list( struct heap *heap, SIZE_T block_size return list; }

+static void free_list_init( struct entry *entry ) +{ + list_init( &entry->entry ); + block_set_flags( &entry->block, ~0, BLOCK_FLAG_FREE_LINK ); + block_set_size( &entry->block, 0 ); + block_set_base( &entry->block, &entry ); + block_set_type( &entry->block, BLOCK_TYPE_FREE ); +} + /* get the memory protection type to use for a given heap */ static inline ULONG get_protection_type( DWORD flags ) { @@ -565,10 +574,13 @@ static void heap_dump( const struct heap *heap ) TRACE( " next %p\n", LIST_ENTRY( heap->entry.next, struct heap, entry ) );

TRACE( " free_lists: %p\n", heap->free_lists ); - for (i = 0; i < HEAP_NB_FREE_LISTS; i++) + for (i = 0; i < ARRAY_SIZE(heap->free_lists); i++) + { TRACE( " %p: size %#8Ix, prev %p, next %p\n", heap->free_lists + i, get_free_list_block_size( i ), LIST_ENTRY( heap->free_lists[i].entry.prev, struct entry, entry ), LIST_ENTRY( heap->free_lists[i].entry.next, struct entry, entry ) ); + } +

TRACE( " subheaps: %p\n", &heap->subheap_list ); LIST_FOR_EACH_ENTRY( subheap, &heap->subheap_list, SUBHEAP, entry ) @@ -1050,7 +1062,9 @@ static BOOL is_valid_free_block( const struct heap *heap, const struct block *bl unsigned int i;

if ((subheap = find_subheap( heap, block, FALSE ))) return TRUE; - for (i = 0; i < HEAP_NB_FREE_LISTS; i++) if (block == &heap->free_lists[i].block) return TRUE; + for (i = 0; i < ARRAY_SIZE(heap->free_lists); i++) + if (block == &heap->free_lists[i].block) return TRUE; + return FALSE; }

@@ -1392,13 +1406,9 @@ HANDLE WINAPI RtlCreateHeap( ULONG flags, void *addr, SIZE_T total_size, SIZE_T subheap_set_bounds( subheap, (char *)heap + commit_size, (char *)heap + total_size ); list_add_head( &heap->subheap_list, &subheap->entry );

- list_init( &heap->free_lists[0].entry ); for (i = 0, entry = heap->free_lists; i < HEAP_NB_FREE_LISTS; i++, entry++) { - block_set_flags( &entry->block, ~0, BLOCK_FLAG_FREE_LINK ); - block_set_size( &entry->block, 0 ); - block_set_type( &entry->block, BLOCK_TYPE_FREE ); - block_set_base( &entry->block, heap ); + free_list_init( entry ); if (i) list_add_after( &entry[-1].entry, &entry->entry ); }

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:06 p.m.

New subject: [PATCH 11/15] ntdll: Introduce a new heap block_init_used helper.

From: Rémi Bernon rbernon@codeweavers.com

--- dlls/ntdll/heap.c | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index d80b939d6b7..38350cb38cd 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -749,6 +749,15 @@ static inline BOOL subheap_decommit( const struct heap *heap, SUBHEAP *subheap, return TRUE; }

+static void block_init_used( struct block *block, ULONG flags, SIZE_T size ) +{ + block_set_type( block, BLOCK_TYPE_USED ); + block_set_flags( block, 0, BLOCK_USER_FLAGS( flags ) ); + block->tail_size = block_get_size( block ) - sizeof(*block) - size; + initialize_block( block, 0, size, flags ); + mark_block_tail( block, flags ); +} + static void block_init_free( struct block *block, ULONG flags, SUBHEAP *subheap, SIZE_T block_size ) { const char *end = (char *)block + block_size, *commit_end = subheap_commit_end( subheap ); @@ -1585,11 +1594,7 @@ static NTSTATUS heap_allocate_block( struct heap *heap, ULONG flags, SIZE_T bloc insert_free_block( heap, flags, subheap, next ); }

- block_set_type( block, BLOCK_TYPE_USED ); - block_set_flags( block, ~0, BLOCK_USER_FLAGS( flags ) ); - block->tail_size = block_get_size( block ) - sizeof(*block) - size; - initialize_block( block, 0, size, flags ); - mark_block_tail( block, flags ); + block_init_used( block, flags, size );

if ((next = next_block( subheap, block ))) block_set_flags( next, BLOCK_FLAG_PREV_FREE, 0 );

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:06 p.m.

New subject: [PATCH 12/15] ntdll: Introduce a new subheap thread affinity field.

From: Rémi Bernon rbernon@codeweavers.com

To associate a subheap with a specific thread that will be its only user. Other threads may only defer the block free of subheap with a different affinity, through locking and defer list. --- dlls/ntdll/heap.c | 46 ++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 38 insertions(+), 8 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index 38350cb38cd..6b2a3baa28c 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -198,7 +198,9 @@ static const SIZE_T free_list_sizes[] =

typedef struct DECLSPEC_ALIGN(BLOCK_ALIGN) tagSUBHEAP { - SIZE_T __pad[sizeof(SIZE_T) / sizeof(DWORD)]; + SIZE_T __pad[sizeof(SIZE_T) / sizeof(DWORD) - 1]; + volatile WORD affinity; + WORD used_blocks; SIZE_T block_size; SIZE_T data_size; struct list entry; @@ -350,6 +352,21 @@ static void subheap_set_bounds( SUBHEAP *subheap, char *commit_end, char *end ) subheap->data_size = commit_end - (char *)(subheap + 1); }

+static void subheap_set_affinity( SUBHEAP *subheap, WORD affinity ) +{ + subheap->affinity = affinity; +} + +static inline WORD subheap_get_affinity( const SUBHEAP *subheap ) +{ + return subheap->affinity; +} + +static inline WORD block_get_affinity( const struct heap *heap, const struct block *block ) +{ + return subheap_get_affinity( block_get_subheap( heap, block ) ); +} + static inline void *first_block( const SUBHEAP *subheap ) { return (void *)&subheap->block; @@ -585,11 +602,12 @@ static void heap_dump( const struct heap *heap ) TRACE( " subheaps: %p\n", &heap->subheap_list ); LIST_FOR_EACH_ENTRY( subheap, &heap->subheap_list, SUBHEAP, entry ) { - SIZE_T free_size = 0, used_size = 0, overhead = 0; + SIZE_T free_size = 0, used_size = 0, overhead = 0, affinity = subheap_get_affinity( subheap ); const char *base = subheap_base( subheap );

TRACE( " %p: base %p first %p last %p end %p\n", subheap, base, first_block( subheap ), last_block( subheap ), base + subheap_size( subheap ) ); + if (affinity) TRACE( " affinity %#Ix\n", affinity );

if (!check_subheap( subheap )) return;

@@ -993,7 +1011,7 @@ static BOOL validate_large_block( const struct heap *heap, const struct block *b }

-static SUBHEAP *create_subheap( struct heap *heap, DWORD flags, SIZE_T commit_size, SIZE_T total_size ) +static SUBHEAP *create_subheap( struct heap *heap, DWORD flags, WORD affinity, SIZE_T commit_size, SIZE_T total_size ) { SIZE_T block_size; SUBHEAP *subheap; @@ -1003,6 +1021,7 @@ static SUBHEAP *create_subheap( struct heap *heap, DWORD flags, SIZE_T commit_si

if (allocate_region( flags, &commit_size, &total_size, (void **)&subheap )) return NULL;

+ subheap_set_affinity( subheap, affinity ); subheap_set_bounds( subheap, (char *)subheap + commit_size, (char *)subheap + total_size ); list_add_head( &heap->subheap_list, &subheap->entry );

@@ -1048,7 +1067,7 @@ static struct block *find_free_block( struct heap *heap, ULONG flags, SIZE_T blo total_size = sizeof(SUBHEAP) + block_size + sizeof(struct entry); if (total_size < block_size) return NULL; /* overflow */

- if ((subheap = create_subheap( heap, flags, total_size, max( heap->grow_size, total_size ) ))) + if ((subheap = create_subheap( heap, flags, 0, total_size, max( heap->grow_size, total_size ) ))) { if (heap->grow_size <= HEAP_MAX_FREE_BLOCK_SIZE / 2) heap->grow_size *= 2; } @@ -1056,7 +1075,7 @@ static struct block *find_free_block( struct heap *heap, ULONG flags, SIZE_T blo { if (heap->grow_size <= total_size || heap->grow_size <= 4 * 1024 * 1024) return NULL; heap->grow_size /= 2; - subheap = create_subheap( heap, flags, total_size, max( heap->grow_size, total_size ) ); + subheap = create_subheap( heap, flags, 0, total_size, max( heap->grow_size, total_size ) ); }

TRACE( "created new sub-heap %p of %#Ix bytes for heap %p\n", subheap, subheap_size( subheap ), heap ); @@ -1100,7 +1119,7 @@ static BOOL validate_free_block( const struct heap *heap, const SUBHEAP *subheap err = "invalid previous free block pointer"; else if (!(block_get_flags( prev ) & BLOCK_FLAG_FREE) || block_get_type( prev ) != BLOCK_TYPE_FREE) err = "invalid previous free block header"; - else if ((next = next_block( subheap, block ))) + else if (!(block_get_affinity( heap, block )) && (next = next_block( subheap, block ))) { if (!(block_get_flags( next ) & BLOCK_FLAG_PREV_FREE)) err = "invalid next block flags"; @@ -1206,12 +1225,19 @@ static BOOL heap_validate_ptr( const struct heap *heap, const void *ptr )

static BOOL heap_validate( const struct heap *heap ) { + DWORD affinity = NtCurrentTeb()->HeapVirtualAffinity, block_affinity; const ARENA_LARGE *large_arena; const struct block *block; const SUBHEAP *subheap;

LIST_FOR_EACH_ENTRY( subheap, &heap->subheap_list, SUBHEAP, entry ) { + if ((block_affinity = subheap_get_affinity( subheap )) && block_affinity != affinity) + { + TRACE( "Skipping subheap %p with affinity %#lx\n", subheap, block_affinity ); + continue; + } + if (!check_subheap( subheap )) { ERR( "heap %p, subheap %p corrupted sizes\n", heap, subheap ); @@ -1943,7 +1969,8 @@ static NTSTATUS heap_walk_blocks( const struct heap *heap, const SUBHEAP *subhea entry->cbData = commit_end - (char *)entry->lpData - 4 * BLOCK_ALIGN; entry->cbOverhead = 2 * BLOCK_ALIGN; entry->iRegionIndex = 0; - entry->wFlags = 0; + if (subheap_get_affinity( subheap )) entry->wFlags = RTL_HEAP_ENTRY_LFH; + else entry->wFlags = 0; } else { @@ -1951,7 +1978,9 @@ static NTSTATUS heap_walk_blocks( const struct heap *heap, const SUBHEAP *subhea entry->cbData = block_get_size( block ) - block_get_overhead( block ); entry->cbOverhead = block_get_overhead( block ); entry->iRegionIndex = 0; - entry->wFlags = RTL_HEAP_ENTRY_COMMITTED|RTL_HEAP_ENTRY_BLOCK|RTL_HEAP_ENTRY_BUSY; + entry->wFlags = RTL_HEAP_ENTRY_BUSY; + if (subheap_get_affinity( subheap )) entry->wFlags |= RTL_HEAP_ENTRY_LFH; + else entry->wFlags |= RTL_HEAP_ENTRY_COMMITTED|RTL_HEAP_ENTRY_BLOCK; }

return STATUS_SUCCESS; @@ -1997,6 +2026,7 @@ static NTSTATUS heap_walk( const struct heap *heap, struct rtl_heap_entry *entry entry->cbOverhead = 0; entry->iRegionIndex = 0; entry->wFlags = RTL_HEAP_ENTRY_REGION; + if (subheap_get_affinity( subheap )) entry->wFlags |= RTL_HEAP_ENTRY_LFH; entry->Region.dwCommittedSize = (char *)subheap_commit_end( subheap ) - base; entry->Region.dwUnCommittedSize = subheap_size( subheap ) - entry->Region.dwCommittedSize; entry->Region.lpFirstBlock = base + entry->cbData;

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:06 p.m.

New subject: [PATCH 13/15] ntdll: Introduce a new BLOCK_FLAG_SPLIT heap block flag.

From: Rémi Bernon rbernon@codeweavers.com

To avoid coalescing free LFH blocks until their owning thread is detached. --- dlls/ntdll/heap.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index 6b2a3baa28c..93629ab6b49 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -101,6 +101,7 @@ C_ASSERT( sizeof(struct block) == 8 ); #define BLOCK_FLAG_PREV_FREE 0x02 #define BLOCK_FLAG_FREE_LINK 0x03 #define BLOCK_FLAG_LARGE 0x04 +#define BLOCK_FLAG_SPLIT 0x08 /* block is split and must not be coalesced */ #define BLOCK_FLAG_USER_INFO 0x10 /* user flags up to 0xf0 */ #define BLOCK_FLAG_USER_MASK 0xf0

@@ -770,7 +771,7 @@ static inline BOOL subheap_decommit( const struct heap *heap, SUBHEAP *subheap, static void block_init_used( struct block *block, ULONG flags, SIZE_T size ) { block_set_type( block, BLOCK_TYPE_USED ); - block_set_flags( block, 0, BLOCK_USER_FLAGS( flags ) ); + block_set_flags( block, ~BLOCK_FLAG_SPLIT, BLOCK_USER_FLAGS( flags ) ); block->tail_size = block_get_size( block ) - sizeof(*block) - size; initialize_block( block, 0, size, flags ); mark_block_tail( block, flags ); @@ -842,7 +843,8 @@ static NTSTATUS heap_free_block( struct heap *heap, ULONG flags, struct block *b

if (category < ARRAY_SIZE(heap->stats) && heap->stats[category] <= 0x10) heap->stats[category]--;

- if ((next = next_block( subheap, block )) && (block_get_flags( next ) & BLOCK_FLAG_FREE)) + if ((next = next_block( subheap, block )) && (block_get_flags( next ) & BLOCK_FLAG_FREE) && + !(block_get_flags( next ) & BLOCK_FLAG_SPLIT)) { /* merge with next block if it is free */ entry = (struct entry *)next;

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:06 p.m.

New subject: [PATCH 14/15] ntdll: Introduce per-thread free lists for heap blocks.

From: Rémi Bernon rbernon@codeweavers.com

--- dlls/ntdll/heap.c | 112 ++++++++++++++++++++++++++++++++++++++-- dlls/ntdll/loader.c | 2 + dlls/ntdll/ntdll_misc.h | 1 + 3 files changed, 112 insertions(+), 3 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index 93629ab6b49..d8e0064fe94 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -213,6 +213,17 @@ typedef struct DECLSPEC_ALIGN(BLOCK_ALIGN) tagSUBHEAP C_ASSERT( sizeof(SUBHEAP) == offsetof(SUBHEAP, block) + sizeof(struct block) ); C_ASSERT( sizeof(SUBHEAP) == 4 * BLOCK_ALIGN );

+struct heap_thread_data +{ + struct entry free_lists[BLOCK_SIZE_CATEGORY_COUNT]; + /* requires heap lock to access */ + struct entry defer_list; + volatile BOOL has_defer; +}; + +/* affinity to tid mapping array, defines the amount of supported concurrent threads */ +static volatile LONG thread_data_tid[64]; + struct heap { /* win32/win64 */ DWORD_PTR unknown1[2]; /* 0000/0000 */ @@ -225,6 +236,7 @@ struct heap DWORD force_flags; /* 0044/0074 */ /* end of the Windows 10 compatible struct layout */

+ struct heap_thread_data *tls; /* Thread local storage data */ volatile BYTE stats[BLOCK_SIZE_CATEGORY_COUNT]; /* Stats counter for LFH activation */ LONG compat_info; /* HeapCompatibilityInformation / heap frontend type */ struct list entry; /* Entry in process heap list */ @@ -586,7 +598,7 @@ static void heap_dump( const struct heap *heap ) const struct block *block; const ARENA_LARGE *large; const SUBHEAP *subheap; - unsigned int i; + unsigned int i, j;

TRACE( "heap: %p\n", heap ); TRACE( " next %p\n", LIST_ENTRY( heap->entry.next, struct heap, entry ) ); @@ -599,6 +611,24 @@ static void heap_dump( const struct heap *heap ) LIST_ENTRY( heap->free_lists[i].entry.next, struct entry, entry ) ); }

+ if (heap->tls) for (i = 0; i < ARRAY_SIZE(thread_data_tid); ++i) + { + struct heap_thread_data *thread_data = heap->tls + i; + if (!thread_data_tid[i]) continue; + TRACE( " index %#x thread %04lx:\n", i, thread_data_tid[i] ); + + for (j = 0; j < ARRAY_SIZE(thread_data->free_lists); j++) + { + if (list_empty( &thread_data->free_lists[j].entry )) continue; + TRACE( " %p: size %8Ix, prev %p, next %p\n", thread_data->free_lists + j, HEAP_MIN_BLOCK_SIZE + j * BLOCK_ALIGN, + LIST_ENTRY( thread_data->free_lists[j].entry.prev, struct entry, entry ), + LIST_ENTRY( thread_data->free_lists[j].entry.next, struct entry, entry ) ); + } + + TRACE( " %p: pending, prev %p, next %p\n", &thread_data->defer_list, + LIST_ENTRY( thread_data->defer_list.entry.prev, struct entry, entry ), + LIST_ENTRY( thread_data->defer_list.entry.next, struct entry, entry ) ); + }

TRACE( " subheaps: %p\n", &heap->subheap_list ); LIST_FOR_EACH_ENTRY( subheap, &heap->subheap_list, SUBHEAP, entry ) @@ -608,7 +638,7 @@ static void heap_dump( const struct heap *heap )

TRACE( " %p: base %p first %p last %p end %p\n", subheap, base, first_block( subheap ), last_block( subheap ), base + subheap_size( subheap ) ); - if (affinity) TRACE( " affinity %#Ix\n", affinity ); + if (affinity) TRACE( " affinity %#Ix, thread %04lx\n", affinity, thread_data_tid[affinity - 1] );

if (!check_subheap( subheap )) return;

@@ -1013,6 +1043,65 @@ static BOOL validate_large_block( const struct heap *heap, const struct block *b }

+static struct heap_thread_data *alloc_thread_data_block( struct heap *heap ) +{ + struct heap_thread_data *thread_data_block = NULL; + SIZE_T size, i, j; + + size = sizeof(*thread_data_block) * ARRAY_SIZE(thread_data_tid); + if (NtAllocateVirtualMemory( NtCurrentProcess(), (void *)&thread_data_block, 0, &size, + MEM_COMMIT, PAGE_READWRITE )) return NULL; + + for (i = 0; i < ARRAY_SIZE(thread_data_tid); ++i) + { + struct heap_thread_data *thread_data = thread_data_block + i; + for (j = 0; j < ARRAY_SIZE(thread_data->free_lists); ++j) + free_list_init( &thread_data->free_lists[j] ); + free_list_init( &thread_data->defer_list ); + } + + return thread_data_block; +} + +static DWORD next_thread_data_index(void) +{ + LONG index, tid = GetCurrentThreadId(); + + for (index = ARRAY_SIZE(thread_data_tid) - 1; index >= 0; index--) + if (!InterlockedCompareExchange( thread_data_tid + index, tid, 0 )) + break; + + NtCurrentTeb()->HeapVirtualAffinity = index + 1; + return index; +} + +void heap_thread_detach(void) +{ + DWORD index = NtCurrentTeb()->HeapVirtualAffinity - 1; + if (index >= ARRAY_SIZE(thread_data_tid)) return; + InterlockedExchange( thread_data_tid + index, 0 ); +} + +static struct heap_thread_data *heap_get_thread_data( struct heap *heap ) +{ + DWORD index = NtCurrentTeb()->HeapVirtualAffinity - 1; + + if (!process_heap || heap->compat_info != HEAP_LFH) return NULL; + if (index >= ARRAY_SIZE(thread_data_tid)) index = next_thread_data_index(); + if (index >= ARRAY_SIZE(thread_data_tid)) return NULL; + + if (!heap->tls) + { + RtlLockHeap( heap ); + if (!heap->tls) heap->tls = alloc_thread_data_block( heap ); + RtlUnlockHeap( heap ); + } + + if (!heap->tls) return NULL; + return heap->tls + index; +} + + static SUBHEAP *create_subheap( struct heap *heap, DWORD flags, WORD affinity, SIZE_T commit_size, SIZE_T total_size ) { SIZE_T block_size; @@ -1089,11 +1178,20 @@ static struct block *find_free_block( struct heap *heap, ULONG flags, SIZE_T blo static BOOL is_valid_free_block( const struct heap *heap, const struct block *block ) { const SUBHEAP *subheap; - unsigned int i; + unsigned int i, j;

if ((subheap = find_subheap( heap, block, FALSE ))) return TRUE; for (i = 0; i < ARRAY_SIZE(heap->free_lists); i++) if (block == &heap->free_lists[i].block) return TRUE; + if (!heap->tls) return FALSE; + + for (i = 0; i < ARRAY_SIZE(thread_data_tid); ++i) + { + struct heap_thread_data *thread_data = heap->tls + i; + if (block == &thread_data->defer_list.block) return TRUE; + for (j = 0; j < ARRAY_SIZE(thread_data->free_lists); ++j) + if (block == &thread_data->free_lists[j].block) return TRUE; + }

return FALSE; } @@ -1556,6 +1654,12 @@ HANDLE WINAPI RtlDestroyHeap( HANDLE handle ) NtFreeVirtualMemory( NtCurrentProcess(), &addr, &size, MEM_RELEASE ); } valgrind_notify_free_all( &heap->subheap ); + if (heap->tls) + { + size = 0; + addr = heap->tls; + NtFreeVirtualMemory( NtCurrentProcess(), &addr, &size, MEM_RELEASE ); + } size = 0; addr = heap; NtFreeVirtualMemory( NtCurrentProcess(), &addr, &size, MEM_RELEASE ); @@ -1586,6 +1690,7 @@ static NTSTATUS heap_allocate_block_lfh( struct heap *heap, ULONG flags, SIZE_T SIZE_T size, void **ret ) { SIZE_T category = BLOCK_SIZE_CATEGORY( block_size ); + struct heap_thread_data *thread_data;

if (category >= ARRAY_SIZE(heap->stats)) return STATUS_UNSUCCESSFUL; if (heap->stats[category] <= 0x10) @@ -1599,6 +1704,7 @@ static NTSTATUS heap_allocate_block_lfh( struct heap *heap, ULONG flags, SIZE_T RtlSetHeapInformation( heap, HeapCompatibilityInformation, &info, sizeof(info) ); return STATUS_UNSUCCESSFUL; } + if (!(thread_data = heap_get_thread_data( heap ))) return STATUS_UNSUCCESSFUL;

return STATUS_NOT_CAPABLE; } diff --git a/dlls/ntdll/loader.c b/dlls/ntdll/loader.c index 682fda9ed15..8677ad3b41d 100644 --- a/dlls/ntdll/loader.c +++ b/dlls/ntdll/loader.c @@ -3727,6 +3727,8 @@ void WINAPI LdrShutdownThread(void) /* don't call DbgUiGetThreadDebugObject as some apps hook it and terminate if called */ if (NtCurrentTeb()->DbgSsReserved[1]) NtClose( NtCurrentTeb()->DbgSsReserved[1] ); RtlFreeThreadActivationContextStack(); + + heap_thread_detach(); }

diff --git a/dlls/ntdll/ntdll_misc.h b/dlls/ntdll/ntdll_misc.h index d1a7790991b..f6b77b79cde 100644 --- a/dlls/ntdll/ntdll_misc.h +++ b/dlls/ntdll/ntdll_misc.h @@ -127,5 +127,6 @@ static inline void ascii_to_unicode( WCHAR *dst, const char *src, size_t len )

/* FLS data */ extern TEB_FLS_DATA *fls_alloc_data(void) DECLSPEC_HIDDEN; +extern void heap_thread_detach(void) DECLSPEC_HIDDEN;

#endif

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Rémi Bernon

12:06 p.m.

New subject: [PATCH 15/15] ntdll: Implement Low Fragmentation Heap.

From: Rémi Bernon rbernon@codeweavers.com

--- dlls/kernel32/tests/heap.c | 27 +---- dlls/ntdll/heap.c | 225 ++++++++++++++++++++++++++++++++++++- 2 files changed, 229 insertions(+), 23 deletions(-)

diff --git a/dlls/kernel32/tests/heap.c b/dlls/kernel32/tests/heap.c index ed84441efe0..04d38e4bd21 100644 --- a/dlls/kernel32/tests/heap.c +++ b/dlls/kernel32/tests/heap.c @@ -953,7 +953,6 @@ static void test_HeapCreate(void) SetLastError( 0xdeadbeef ); while ((ret = HeapWalk( heap, &entry ))) entries[count++] = entry; ok( GetLastError() == ERROR_NO_MORE_ITEMS, "got error %lu\n", GetLastError() ); - todo_wine ok( count > 24, "got count %lu\n", count ); if (count < 2) count = 2;

@@ -966,7 +965,6 @@ static void test_HeapCreate(void)

for (i = 0; i < 0x12; i++) { - todo_wine ok( entries[4 + i].wFlags == 0, "got wFlags %#x\n", entries[4 + i].wFlags ); todo_wine ok( entries[4 + i].cbData == 0x20, "got cbData %#lx\n", entries[4 + i].cbData ); @@ -985,7 +983,6 @@ static void test_HeapCreate(void) rtl_entry.lpData = NULL; SetLastError( 0xdeadbeef ); while (!RtlWalkHeap( heap, &rtl_entry )) rtl_entries[count++] = rtl_entry; - todo_wine ok( count > 24, "got count %lu\n", count ); if (count < 2) count = 2;

@@ -1028,7 +1025,6 @@ static void test_HeapCreate(void) SetLastError( 0xdeadbeef ); while ((ret = HeapWalk( heap, &entry ))) entries[count++] = entry; ok( GetLastError() == ERROR_NO_MORE_ITEMS, "got error %lu\n", GetLastError() ); - todo_wine ok( count > 24, "got count %lu\n", count ); if (count < 2) count = 2;

@@ -1057,7 +1053,6 @@ static void test_HeapCreate(void) rtl_entry.lpData = NULL; SetLastError( 0xdeadbeef ); while (!RtlWalkHeap( heap, &rtl_entry )) rtl_entries[count++] = rtl_entry; - todo_wine ok( count > 24, "got count %lu\n", count ); if (count < 2) count = 2;

@@ -1071,11 +1066,8 @@ static void test_HeapCreate(void) if (!entries[i].wFlags) ok( rtl_entries[i].wFlags == 0 || rtl_entries[i].wFlags == RTL_HEAP_ENTRY_LFH, "got wFlags %#x\n", rtl_entries[i].wFlags ); else if (entries[i].wFlags & PROCESS_HEAP_ENTRY_BUSY) - { - todo_wine ok( rtl_entries[i].wFlags == (RTL_HEAP_ENTRY_LFH|RTL_HEAP_ENTRY_BUSY) || broken(rtl_entries[i].wFlags == 1) /* win7 */, "got wFlags %#x\n", rtl_entries[i].wFlags ); - } else if (entries[i].wFlags & PROCESS_HEAP_UNCOMMITTED_RANGE) ok( rtl_entries[i].wFlags == RTL_HEAP_ENTRY_UNCOMMITTED || broken(rtl_entries[i].wFlags == 0x100) /* win7 */, "got wFlags %#x\n", rtl_entries[i].wFlags ); @@ -1220,7 +1212,6 @@ static void test_HeapCreate(void) thread_params.flags = 0; SetEvent( thread_params.start_event ); res = WaitForSingleObject( thread_params.ready_event, 100 ); - todo_wine ok( !res, "WaitForSingleObject returned %#lx, error %lu\n", res, GetLastError() ); ret = HeapUnlock( heap ); ok( ret, "HeapUnlock failed, error %lu\n", GetLastError() ); @@ -1667,9 +1658,7 @@ static void test_GlobalAlloc(void) ok( size == small_size, "GlobalSize returned %Iu\n", size ); SetLastError( 0xdeadbeef ); tmp_mem = GlobalReAlloc( mem, small_size, 0 ); - todo_wine ok( !tmp_mem, "GlobalReAlloc succeeded\n" ); - todo_wine ok( GetLastError() == ERROR_NOT_ENOUGH_MEMORY, "got error %lu\n", GetLastError() ); if (tmp_mem) mem = tmp_mem; tmp_mem = GlobalReAlloc( mem, 1024 * 1024, GMEM_MODIFY ); @@ -1685,7 +1674,6 @@ static void test_GlobalAlloc(void) ok( !!mem, "GlobalAlloc failed, error %lu\n", GetLastError() ); tmp_mem = GlobalReAlloc( mem, small_size + 1, GMEM_MOVEABLE ); ok( !!tmp_mem, "GlobalReAlloc failed, error %lu\n", GetLastError() ); - todo_wine ok( tmp_mem != mem, "GlobalReAlloc didn't relocate memory\n" ); ptr = GlobalLock( tmp_mem ); ok( !!ptr, "GlobalLock failed, error %lu\n", GetLastError() ); @@ -1832,8 +1820,8 @@ static void test_GlobalAlloc(void) { ok( !is_mem_entry( tmp_mem ), "unexpected moveable %p\n", tmp_mem ); if (flags == GMEM_MODIFY) ok( tmp_mem == mem, "GlobalReAlloc returned %p\n", tmp_mem ); - else if (flags != GMEM_MOVEABLE) todo_wine_if(!flags) ok( !tmp_mem, "GlobalReAlloc succeeded\n" ); - else todo_wine ok( tmp_mem != mem, "GlobalReAlloc returned %p\n", tmp_mem ); + else if (flags != GMEM_MOVEABLE) ok( !tmp_mem, "GlobalReAlloc succeeded\n" ); + else ok( tmp_mem != mem, "GlobalReAlloc returned %p\n", tmp_mem ); } else { @@ -1847,7 +1835,7 @@ static void test_GlobalAlloc(void)

size = GlobalSize( mem ); if (flags == GMEM_MOVEABLE) ok( size == 0 || broken( size == 1 ) /* w7 */, "GlobalSize returned %Iu\n", size ); - else todo_wine_if(!flags) ok( size == small_size, "GlobalSize returned %Iu\n", size ); + else ok( size == small_size, "GlobalSize returned %Iu\n", size );

mem = GlobalFree( mem ); ok( !mem, "GlobalFree failed, error %lu\n", GetLastError() ); @@ -2405,9 +2393,7 @@ static void test_LocalAlloc(void) ok( size == small_size, "LocalSize returned %Iu\n", size ); SetLastError( 0xdeadbeef ); tmp_mem = LocalReAlloc( mem, small_size, 0 ); - todo_wine ok( !tmp_mem, "LocalReAlloc succeeded\n" ); - todo_wine ok( GetLastError() == ERROR_NOT_ENOUGH_MEMORY, "got error %lu\n", GetLastError() ); if (tmp_mem) mem = tmp_mem; tmp_mem = LocalReAlloc( mem, 1024 * 1024, LMEM_MODIFY ); @@ -2423,7 +2409,6 @@ static void test_LocalAlloc(void) ok( !!mem, "LocalAlloc failed, error %lu\n", GetLastError() ); tmp_mem = LocalReAlloc( mem, small_size + 1, LMEM_MOVEABLE ); ok( !!tmp_mem, "LocalReAlloc failed, error %lu\n", GetLastError() ); - todo_wine ok( tmp_mem != mem, "LocalReAlloc didn't relocate memory\n" ); ptr = LocalLock( tmp_mem ); ok( !!ptr, "LocalLock failed, error %lu\n", GetLastError() ); @@ -2516,13 +2501,13 @@ static void test_LocalAlloc(void) tmp_mem = LocalReAlloc( mem, 0, flags ); ok( !is_mem_entry( tmp_mem ), "unexpected moveable %p\n", tmp_mem ); if (flags & LMEM_MODIFY) ok( tmp_mem == mem, "LocalReAlloc returned %p\n", tmp_mem ); - else if (flags != LMEM_MOVEABLE) todo_wine_if(!flags) ok( !tmp_mem, "LocalReAlloc succeeded\n" ); - else todo_wine ok( tmp_mem != mem, "LocalReAlloc returned %p\n", tmp_mem ); + else if (flags != LMEM_MOVEABLE) ok( !tmp_mem, "LocalReAlloc succeeded\n" ); + else ok( tmp_mem != mem, "LocalReAlloc returned %p\n", tmp_mem ); if (tmp_mem) mem = tmp_mem;

size = LocalSize( mem ); if (flags == LMEM_MOVEABLE) ok( size == 0 || broken( size == 1 ) /* w7 */, "LocalSize returned %Iu\n", size ); - else todo_wine_if(!flags) ok( size == small_size, "LocalSize returned %Iu\n", size ); + else ok( size == small_size, "LocalSize returned %Iu\n", size );

mem = LocalFree( mem ); ok( !mem, "LocalFree failed, error %lu\n", GetLastError() ); diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c index d8e0064fe94..e88ace3ea90 100644 --- a/dlls/ntdll/heap.c +++ b/dlls/ntdll/heap.c @@ -1075,10 +1075,50 @@ static DWORD next_thread_data_index(void) return index; }

+/* release thread blocks to the main heap free lists, clearing the subheap affinity and split flags */ +static void heap_release_blocks_lfh( struct heap *heap ) +{ + struct block *block; + SUBHEAP *subheap; + + LIST_FOR_EACH_ENTRY( subheap, &heap->subheap_list, SUBHEAP, entry ) + { + if (subheap_get_affinity( subheap ) != NtCurrentTeb()->HeapVirtualAffinity) continue; + for (block = first_block( subheap ); block; block = next_block( subheap, block )) + { + /* remove the flag one block at a time, so that heap_free_block only merges with the previous blocks */ + block_set_flags( block, ~BLOCK_FLAG_SPLIT, 0 ); + if (block_get_flags( block ) & BLOCK_FLAG_FREE) + { + struct entry *entry = CONTAINING_RECORD( block, struct entry, block ); + list_remove( &entry->entry ); + heap_free_block( heap, 0, block ); + } + } + subheap_set_affinity( subheap, 0 ); + } +} + void heap_thread_detach(void) { + struct heap *heap; + DWORD index = NtCurrentTeb()->HeapVirtualAffinity - 1; if (index >= ARRAY_SIZE(thread_data_tid)) return; + + heap_lock( process_heap, 0 ); + + LIST_FOR_EACH_ENTRY( heap, &process_heap->entry, struct heap, entry ) + { + heap_lock( heap, 0 ); + heap_release_blocks_lfh( heap ); + heap_unlock( heap, 0 ); + } + + heap_release_blocks_lfh( process_heap ); + + heap_unlock( process_heap, 0 ); + InterlockedExchange( thread_data_tid + index, 0 ); }

@@ -1114,11 +1154,14 @@ static SUBHEAP *create_subheap( struct heap *heap, DWORD flags, WORD affinity, S

subheap_set_affinity( subheap, affinity ); subheap_set_bounds( subheap, (char *)subheap + commit_size, (char *)subheap + total_size ); - list_add_head( &heap->subheap_list, &subheap->entry );

block_size = (SIZE_T)ROUND_ADDR( subheap_size( subheap ) - subheap_overhead( subheap ), BLOCK_ALIGN - 1 ); block_init_free( first_block( subheap ), flags, subheap, block_size );

+ heap_lock( heap, 0 ); + list_add_tail( &heap->subheap_list, &subheap->entry ); + heap_unlock( heap, 0 ); + return subheap; }

@@ -1686,11 +1729,128 @@ static SIZE_T heap_get_block_size( const struct heap *heap, ULONG flags, SIZE_T return block_size; }

+static void insert_free_block_lfh( struct heap *heap, struct entry *entry, struct heap_thread_data *thread_data ) +{ + SIZE_T block_size = block_get_size( &entry->block ), category = BLOCK_SIZE_CATEGORY( block_size ); + struct entry *free_list = thread_data->free_lists + category; + SUBHEAP *subheap = block_get_subheap( heap, &entry->block ); + + list_add_head( &free_list->entry, &entry->entry ); + if (!--subheap->used_blocks) + { + void *addr = subheap_base( subheap ); + struct block *block; + SIZE_T size = 0; + + for (block = first_block( subheap ); block; block = next_block( subheap, block )) + { + entry = (struct entry *)block; + list_remove( &entry->entry ); + } + + heap_lock( heap, 0 ); + list_remove( &subheap->entry ); + heap_unlock( heap, 0 ); + + NtFreeVirtualMemory( NtCurrentProcess(), &addr, &size, MEM_RELEASE ); + } +} + +static void flush_defer_list( struct heap *heap, ULONG flags, struct heap_thread_data *thread_data ) +{ + struct list pending = LIST_INIT( pending ); + struct entry *entry, *next; + + if (!thread_data->has_defer) return; + + heap_lock( heap, flags ); + list_move_tail( &pending, &thread_data->defer_list.entry ); + thread_data->has_defer = FALSE; + heap_unlock( heap, flags ); + + LIST_FOR_EACH_ENTRY_SAFE( entry, next, &pending, struct entry, entry ) + { + list_remove( &entry->entry ); + insert_free_block_lfh( heap, entry, thread_data ); + } +} + +static void split_block_lfh( struct heap *heap, ULONG flags, struct block *block, SIZE_T block_size, struct entry *free_list ) +{ + SIZE_T i, old_block_size = block_get_size( block ), count = min( 16, old_block_size / block_size ); + SUBHEAP *subheap = block_get_subheap( heap, block ); + struct entry *entry; + + if (!subheap_commit( heap, subheap, block, count * block_size )) return; + + for (i = 0; i < count; ++i) + { + block_init_free( block, flags, subheap, block_size ); + block_set_flags( block, 0, BLOCK_FLAG_SPLIT ); + old_block_size -= block_size; + + entry = (struct entry *)block; + if (i) list_add_head( &free_list->entry, &entry->entry ); + + block = next_block( subheap, block ); + } + + if ((entry = (struct entry *)block)) + { + block_init_free( block, flags, subheap, old_block_size ); + /* only if large enough to carve more blocks from it */ + if (old_block_size < block_size) list_init( &entry->entry ); + else list_add_tail( &free_list->entry, &entry->entry ); + } + + /* consider releasing the region after we've split it entirely */ + if (old_block_size < block_size || !block) + subheap->used_blocks--; +} + +static struct block *find_free_block_lfh( struct heap *heap, ULONG flags, SIZE_T category, + struct heap_thread_data *thread_data ) +{ + SIZE_T block_size = BLOCK_CATEGORY_SIZE(category), commit_size, total_size; + WORD affinity = NtCurrentTeb()->HeapVirtualAffinity; + struct entry *entry, *free_list; + struct list *ptr; + SUBHEAP *subheap; + + free_list = thread_data->free_lists + category; + commit_size = sizeof(*subheap) + 16 * block_size + sizeof(*entry); + total_size = sizeof(*subheap) + 1024 * block_size + sizeof(*entry); + + if ((ptr = list_head( &free_list->entry ))) + { + entry = LIST_ENTRY( ptr, struct entry, entry ); + list_remove( &entry->entry ); + subheap = block_get_subheap( heap, &entry->block ); + } + else if (!(flags & HEAP_GROWABLE)) + return NULL; + else if (!(subheap = create_subheap( heap, flags, affinity, commit_size, total_size ))) + return NULL; + else + { + TRACE( "created new sub-heap %p of %#Ix bytes for heap %p\n", subheap, subheap_size( subheap ), heap ); + subheap->used_blocks = 1; /* consider releasing the region after we've split it entirely */ + entry = first_block( subheap ); + } + + if (!(block_get_flags( &entry->block ) & BLOCK_FLAG_SPLIT)) + split_block_lfh( heap, flags, &entry->block, block_size, free_list ); + + subheap->used_blocks++; + return &entry->block; +} + static NTSTATUS heap_allocate_block_lfh( struct heap *heap, ULONG flags, SIZE_T block_size, SIZE_T size, void **ret ) { SIZE_T category = BLOCK_SIZE_CATEGORY( block_size ); struct heap_thread_data *thread_data; + struct block *block;

if (category >= ARRAY_SIZE(heap->stats)) return STATUS_UNSUCCESSFUL; if (heap->stats[category] <= 0x10) @@ -1706,7 +1866,12 @@ static NTSTATUS heap_allocate_block_lfh( struct heap *heap, ULONG flags, SIZE_T } if (!(thread_data = heap_get_thread_data( heap ))) return STATUS_UNSUCCESSFUL;

- return STATUS_NOT_CAPABLE; + if (!(block = find_free_block_lfh( heap, flags, category, thread_data ))) return STATUS_NO_MEMORY; + block_init_used( block, flags, size ); + flush_defer_list( heap, flags, thread_data ); + + *ret = block + 1; + return STATUS_SUCCESS; }

static NTSTATUS heap_allocate_block( struct heap *heap, ULONG flags, SIZE_T block_size, SIZE_T size, void **ret ) @@ -1769,6 +1934,40 @@ void *WINAPI DECLSPEC_HOTPATCH RtlAllocateHeap( HANDLE handle, ULONG flags, SIZE return ptr; }

+static NTSTATUS heap_free_block_lfh( struct heap *heap, ULONG flags, struct block *block, WORD block_affinity ) +{ + SIZE_T block_size = block_get_size( block ), category = BLOCK_SIZE_CATEGORY( block_size ); + ULONG affinity = NtCurrentTeb()->HeapVirtualAffinity; + SUBHEAP *subheap = block_get_subheap( heap, block ); + struct entry *entry = (struct entry *)block; + struct heap_thread_data *thread_data; + + valgrind_make_writable( &block, sizeof(*entry) ); + block_set_type( block, BLOCK_TYPE_FREE ); + block_set_flags( block, ~BLOCK_FLAG_SPLIT, BLOCK_FLAG_FREE ); + block_set_base( block, subheap_base( subheap ) ); + block_set_size( block, BLOCK_CATEGORY_SIZE(category) ); + mark_block_free( block + 1, BLOCK_CATEGORY_SIZE(category) - sizeof(*block), flags ); + + if (block_affinity == affinity) thread_data = heap_get_thread_data( heap ); + else + { + heap_lock( heap, flags ); + /* the subheap affinity may be reset to zero when the owner thread is detached */ + if ((block_affinity = block_get_affinity( heap, block ))) + { + list_add_tail( &heap->tls[block_affinity - 1].defer_list.entry, &entry->entry ); + heap->tls[block_affinity - 1].has_defer = TRUE; + } + heap_unlock( heap, flags ); + return block_affinity ? STATUS_SUCCESS : STATUS_NOT_CAPABLE; + } + + insert_free_block_lfh( heap, entry, thread_data ); + flush_defer_list( heap, flags, thread_data ); + + return STATUS_SUCCESS; +}

/*********************************************************************** * RtlFreeHeap (NTDLL.@) @@ -1779,6 +1978,7 @@ BOOLEAN WINAPI DECLSPEC_HOTPATCH RtlFreeHeap( HANDLE handle, ULONG flags, void * struct heap *heap; ULONG heap_flags; NTSTATUS status; + WORD affinity;

if (!ptr) return TRUE;

@@ -1792,6 +1992,8 @@ BOOLEAN WINAPI DECLSPEC_HOTPATCH RtlFreeHeap( HANDLE handle, ULONG flags, void * status = heap_free_large( heap, heap_flags, block ); else if (!(block = heap_delay_free( heap, heap_flags, block ))) status = STATUS_SUCCESS; + else if ((affinity = block_get_affinity( heap, block ))) + status = heap_free_block_lfh( heap, heap_flags, block, affinity ); else { heap_lock( heap, heap_flags ); @@ -1811,6 +2013,7 @@ static NTSTATUS heap_resize_block( struct heap *heap, ULONG flags, struct block SIZE_T old_block_size; struct entry *entry; struct block *next; + WORD affinity;

if (block_get_flags( block ) & BLOCK_FLAG_LARGE) { @@ -1838,6 +2041,24 @@ static NTSTATUS heap_resize_block( struct heap *heap, ULONG flags, struct block

if (block_size >= HEAP_MIN_LARGE_BLOCK_SIZE) return STATUS_NO_MEMORY; /* growing small block to large block */

+ if ((affinity = block_get_affinity( heap, block ))) + { + if (affinity != NtCurrentTeb()->HeapVirtualAffinity) return STATUS_NO_MEMORY; /* resizing block owned by another thread */ + + /* as native LFH does it, different block size even though we could resize */ + if (ROUND_SIZE( *old_size, BLOCK_ALIGN - 1) != ROUND_SIZE( size, BLOCK_ALIGN - 1)) return STATUS_NO_MEMORY; + if (size >= *old_size) return STATUS_NO_MEMORY; + + valgrind_notify_resize( block + 1, *old_size, size ); + block_set_flags( block, BLOCK_FLAG_USER_MASK, BLOCK_USER_FLAGS( flags ) ); + block->tail_size = block_get_size( block ) - sizeof(*block) - size; + initialize_block( block, *old_size, size, flags ); + mark_block_tail( block, flags ); + + *ret = block + 1; + return STATUS_SUCCESS; + } + heap_lock( heap, flags );

if (block_size > old_block_size)

-- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/1628

Marvin

12:35 p.m.

New subject: [PATCH 15/15] ntdll: Implement Low Fragmentation Heap.

Hi,

It looks like your patch introduced the new failures shown below. Please investigate and fix them before resubmitting your patch. If they are not new, fixing them anyway would help a lot. Otherwise please ask for the known failures list to be updated.

The tests also ran into some preexisting test failures. If you know how to fix them that would be helpful. See the TestBot job for the details:

The full results can be found at: https://testbot.winehq.org/JobDetails.pl?Key=127062

Your paranoid android.

=== debian11 (32 bit report) ===

comctl32: dpa.c:216: Test failed: ret=1 error=0 dpa.c:216: Test failed: ret=1 error=1411 Unhandled exception: page fault on read access to 0x00000028 in 32-bit code (0x7bc27080). Unhandled exception: page fault on read access to 0x00000018 in 32-bit code (0x7bc27080).

mshtml: script.c:920: Test failed: L"/index.html?0:storage: got 'add-at-end' enumerating" script.c:920: Test failed: L"/index.html?0:storage: enum did 5 iterations" script.c:920: Test failed: L"/index.html?5:storage: got 'add-at-end' enumerating" script.c:920: Test failed: L"/index.html?5:storage: enum did 5 iterations" script.c:920: Test failed: L"/index.html?5:storage: got 'add-at-end' enumerating" script.c:920: Test failed: L"/index.html?5:storage: enum did 5 iterations" script.c:920: Test failed: L"/index.html?7:storage: got 'add-at-end' enumerating" script.c:920: Test failed: L"/index.html?7:storage: enum did 5 iterations" script.c:920: Test failed: L"/index.html?8:storage: got 'add-at-end' enumerating" script.c:920: Test failed: L"/index.html?8:storage: enum did 5 iterations" script.c:920: Test failed: L"/index.html?9:storage: got 'add-at-end' enumerating" script.c:920: Test failed: L"/index.html?9:storage: enum did 5 iterations" script.c:920: Test failed: L"/index.html?10:storage: got 'add-at-end' enumerating" script.c:920: Test failed: L"/index.html?10:storage: enum did 5 iterations" script.c:920: Test failed: L"/index.html?11:storage: got 'add-at-end' enumerating" script.c:920: Test failed: L"/index.html?11:storage: enum did 5 iterations" script.c:920: Test failed: L"/index.html?11:storage: got 'add-at-end' enumerating" script.c:920: Test failed: L"/index.html?11:storage: enum did 5 iterations"

mstask: Unhandled exception: page fault on read access to 0x00000018 in 32-bit code (0x7bc27080). Unhandled exception: page fault on read access to 0x00000018 in 32-bit code (0x7bc27080). Unhandled exception: page fault on read access to 0x00000018 in 32-bit code (0x7bc27080).

schtasks.exe: schtasks.c:188: Test failed: r = 3221225477 schtasks.c:193: Test failed: r = 3221225477 schtasks.c:198: Test failed: r = 3221225477 schtasks.c:201: Test failed: r = 3221225477 schtasks.c:204: Test failed: r = 3221225477 schtasks.c:209: Test failed: r = 3221225477 schtasks.c:212: Test failed: r = 3221225477 schtasks.c:215: Test failed: r = 3221225477 schtasks.c:218: Test failed: r = 3221225477 schtasks.c:224: Test failed: r = 3221225477

taskschd: Unhandled exception: page fault on read access to 0x00000048 in 32-bit code (0x7bc27080).

=== debian11b (32 bit WoW report) ===

kernel32: heap: Timeout

797

Age (days ago)

797

Last active (days ago)

wine-gitlab@winehq.org

16 comments

3 participants

tags (0)

participants (3)

Marvin
Rémi Bernon
Rémi Bernon (＠rbernon)