From: Rémi Bernon rbernon@codeweavers.com
This implements the reduced fragmentation from the heap frontend, by carving smaller blocks out of larger allocated blocks.
The super block and each sub-block are all flagged with BLOCK_FLAG_LFH.
The super-block (struct group) uses a standard struct block header, as well as a list entry to be linked in free list, and a free bit map to track free sub-blocks.
Sub-blocks reference their super block through the base_offset, instead of the subheap, using the block size as radix. --- dlls/kernel32/tests/heap.c | 19 +-- dlls/ntdll/heap.c | 274 +++++++++++++++++++++++++++++++++++-- 2 files changed, 270 insertions(+), 23 deletions(-)
diff --git a/dlls/kernel32/tests/heap.c b/dlls/kernel32/tests/heap.c index ed84441efe0..b3c3dc1eebc 100644 --- a/dlls/kernel32/tests/heap.c +++ b/dlls/kernel32/tests/heap.c @@ -1042,6 +1042,7 @@ static void test_HeapCreate(void) for (i = 1; i < count - 2; i++) { if (entries[i].wFlags != PROCESS_HEAP_ENTRY_BUSY) continue; + todo_wine /* Wine currently reports the LFH group as a single block */ ok( entries[i].cbData == 0x18 + 2 * sizeof(void *), "got cbData %#lx\n", entries[i].cbData ); ok( entries[i].cbOverhead == 0x8, "got cbOverhead %#x\n", entries[i].cbOverhead ); } @@ -1667,9 +1668,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 +1684,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 +1830,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 +1845,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 +2403,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 +2419,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 +2511,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 4b1d9dfea20..e3800cad6af 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_LFH 0x08 /* block is handled by the LFH frontend */ #define BLOCK_FLAG_USER_INFO 0x10 /* user flags up to 0xf0 */ #define BLOCK_FLAG_USER_MASK 0xf0
@@ -227,13 +228,15 @@ C_ASSERT( BLOCK_SIZE_CATEGORY_COUNT <= 256 ); C_ASSERT( BLOCK_SIZE_MEDIUM_STEP + 3 * BLOCK_ALIGN <= FIELD_MAX( struct block, tail_size ) );
/* a category of heap blocks of a certain size */ - struct category { /* counters for LFH activation */ volatile LONG blocks_alive; volatile LONG blocks_total; volatile BOOL enabled; + + /* list of groups with free blocks */ + struct list groups; };
struct heap @@ -776,19 +779,22 @@ static inline BOOL subheap_decommit( const struct heap *heap, SUBHEAP *subheap,
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;
valgrind_make_writable( block, sizeof(*entry) ); block_set_type( block, BLOCK_TYPE_FREE ); - block_set_base( block, subheap_base( subheap ) ); block_set_flags( block, ~0, BLOCK_FLAG_FREE ); block_set_size( block, block_size );
- /* If debugging, erase the freed block content */ - - if (end > commit_end) end = commit_end; - if (end > (char *)(entry + 1)) mark_block_free( entry + 1, end - (char *)(entry + 1), flags ); + if (!subheap) /* LFH block initialization, just clear its data */ + mark_block_free( entry + 1, (char *)block + block_size - (char *)(entry + 1), flags ); + else + { + const char *end = (char *)block + block_size, *commit_end; + block_set_base( block, subheap_base( subheap ) ); + if (end > (commit_end = subheap_commit_end( subheap ))) 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 ) @@ -1104,7 +1110,9 @@ 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 ((next = next_block( subheap, block )) && + /* LFH blocks do not use BLOCK_FLAG_PREV_FREE or back pointer */ + !(block_get_flags( block ) & BLOCK_FLAG_LFH)) { if (!(block_get_flags( next ) & BLOCK_FLAG_PREV_FREE)) err = "invalid next block flags"; @@ -1154,7 +1162,10 @@ static BOOL validate_used_block( const struct heap *heap, const SUBHEAP *subheap err = "invalid block size"; else if (block->tail_size > block_get_size( block ) - sizeof(*block)) err = "invalid block unused size"; - else if ((next = next_block( subheap, block )) && (block_get_flags( next ) & BLOCK_FLAG_PREV_FREE)) + else if ((next = next_block( subheap, block )) && + (block_get_flags( next ) & BLOCK_FLAG_PREV_FREE) && + /* LFH blocks do not use BLOCK_FLAG_PREV_FREE or back pointer */ + !(block_get_flags( block ) & BLOCK_FLAG_LFH)) err = "invalid next block flags"; else if (block_get_flags( block ) & BLOCK_FLAG_PREV_FREE) { @@ -1291,6 +1302,16 @@ static inline struct block *unsafe_block_from_ptr( struct heap *heap, ULONG flag
if ((ULONG_PTR)ptr % BLOCK_ALIGN) err = "invalid ptr alignment"; + else if (block_get_flags( block ) & BLOCK_FLAG_LFH) + { + /* LFH blocks base points to the group, not the subheap */ + if (block_get_type( block ) == BLOCK_TYPE_DEAD) + err = "delayed freed block"; + else if (block_get_type( block ) == BLOCK_TYPE_FREE) + err = "already freed block"; + else if (block_get_type( block ) != BLOCK_TYPE_USED) + err = "invalid block type"; + } else if ((subheap = block_get_subheap( heap, block )) >= (SUBHEAP *)block) err = "invalid base offset"; else if (block_get_type( block ) == BLOCK_TYPE_USED) @@ -1493,6 +1514,8 @@ HANDLE WINAPI RtlCreateHeap( ULONG flags, void *addr, SIZE_T total_size, SIZE_T SIZE_T size = sizeof(struct category) * BLOCK_SIZE_CATEGORY_COUNT; NtAllocateVirtualMemory( NtCurrentProcess(), (void *)&heap->categories, 0, &size, MEM_COMMIT, PAGE_READWRITE ); + for (i = 0; i < BLOCK_SIZE_CATEGORY_COUNT; ++i) + list_init( &heap->categories[i].groups ); }
/* link it into the per-process heap list */ @@ -1642,10 +1665,170 @@ static NTSTATUS heap_allocate_block( struct heap *heap, ULONG flags, SIZE_T bloc return STATUS_SUCCESS; }
+/* Low Fragmentation Heap frontend */ + +/* header for every LFH block group */ + +struct DECLSPEC_ALIGN(BLOCK_ALIGN) group +{ + struct block block; + struct list entry; + /* one bit for each free block and the highest bit as unlinked flag */ + LONG free_bits; +}; + +#define GROUP_FLAG_FREE (1u << (sizeof(((struct group *)0)->free_bits) * 8 - 1)) + +static inline UINT block_get_group_index( const struct block *block ) +{ + return block->base_offset; +} + +static inline struct group *block_get_group( const struct block *block ) +{ + SIZE_T block_size = block_get_size( block ); + void *blocks = (char *)block - block_get_group_index( block ) * block_size; + return (struct group *)blocks - 1; +} + +static inline void block_set_group( struct block *block, SIZE_T block_size, const struct group *group ) +{ + const char *blocks = (char *)(group + 1); + block->base_offset = ((char *)block - blocks) / block_size; +} + +static inline struct block *group_get_block( struct group *group, SIZE_T block_size, UINT index ) +{ + char *blocks = (char *)(group + 1); + return (struct block *)(blocks + index * block_size); +} + +/* lookup a free block using the group free_bits, the current thread must own the group */ +static inline LONG group_find_free_block( struct group *group, SIZE_T block_size, struct block **block ) +{ +#if defined(__GNUC__) && ((__GNUC__ > 3) || ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 3))) + int i = __builtin_ffs( group->free_bits ) - 1; +#else + int i = sizeof(group->free_bits) * 8; + while (i--) if (group->free_bits & (1 << i)) break; +#endif + /* we remove the group from the free list once all its blocks are used, i will never be -1 */ + *block = group_get_block( group, block_size, i ); + return group->free_bits &= ~(1 << i); +} + +/* allocate a new group block using non-LFH allocation, returns a group owned by current thread */ +static struct group *group_allocate( struct heap *heap, ULONG flags, SIZE_T block_size, struct category *category ) +{ + SIZE_T i, size, group_size; + struct group *group; + NTSTATUS status; + char *ptr; + + size = sizeof(*group) + sizeof(group->free_bits) * 8 * block_size - sizeof(struct block); + group_size = heap_get_block_size( heap, flags, size ); + + if (group_size >= HEAP_MIN_LARGE_BLOCK_SIZE) + status = heap_allocate_large( heap, flags & ~HEAP_ZERO_MEMORY, group_size, size, (void **)&ptr ); + else + status = heap_allocate_block( heap, flags & ~HEAP_ZERO_MEMORY, group_size, size, (void **)&ptr ); + + if (status) return NULL; + + group = CONTAINING_RECORD( (struct block *)ptr - 1, struct group, block ); + block_set_flags( &group->block, 0, BLOCK_FLAG_LFH ); + group->free_bits = ~0; + + for (i = 0; i < sizeof(group->free_bits) * 8; ++i) + { + struct block *block = group_get_block( group, block_size, i ); + block_init_free( block, flags, NULL, block_size ); + block_set_flags( block, 0, BLOCK_FLAG_LFH ); + block_set_group( block, block_size, group ); + } + + return group; +} + +/* release a fully freed group to the non-LFH subheap, group must be owned by current thread */ +static NTSTATUS group_release( struct heap *heap, ULONG flags, struct category *category, struct group *group ) +{ + NTSTATUS status; + + block_set_flags( &group->block, BLOCK_FLAG_LFH, 0 ); + + if (block_get_flags( &group->block ) & BLOCK_FLAG_LARGE) + status = heap_free_large( heap, flags, &group->block ); + else + status = heap_free_block( heap, flags, &group->block ); + + return status; +} + +/* acquire a group from the category, thread takes ownership of a shared group or allocates a new one */ +static struct group *heap_acquire_category_group( struct heap *heap, ULONG flags, SIZE_T block_size, + struct category *category ) +{ + struct group *group; + struct list *entry; + + if (!(entry = list_head( &category->groups ))) + group = group_allocate( heap, flags, block_size, category ); + else + { + group = LIST_ENTRY( entry, struct group, entry ); + list_remove( &group->entry ); + } + + return group; +} + +/* release a thread owned and fully freed group to the category shared group, or free its memory */ +static NTSTATUS heap_release_category_group( struct heap *heap, ULONG flags, struct category *category, + struct group *group ) +{ + NTSTATUS status = STATUS_SUCCESS; + + /* try re-using the block group instead of releasing it */ + if (list_empty( &category->groups )) + list_add_tail( &category->groups, &group->entry ); + else + status = group_release( heap, flags, category, group ); + + return status; +} + +static struct block *find_free_block_lfh( struct heap *heap, ULONG flags, SIZE_T block_size, + struct category *category ) +{ + struct block *block; + struct group *group; + + /* acquire a group, the thread will own it and no other thread can clear free bits. + * some other thread might still set the free bits if they are freeing blocks. + */ + if (!(group = heap_acquire_category_group( heap, flags, block_size, category ))) return NULL; + + /* serialize with heap_free_block_lfh: atomically set GROUP_FLAG_FREE when the free bits are all 0. */ + if (group_find_free_block( group, block_size, &block )) + group->free_bits &= ~GROUP_FLAG_FREE; + else if (!group->free_bits) + group->free_bits = GROUP_FLAG_FREE; + + /* if GROUP_FLAG_FREE was set, thread released its ownership. */ + if (group->free_bits & GROUP_FLAG_FREE) return block; + + /* otherwise there is still some free blocks, put the group back into the category */ + list_add_tail( &category->groups, &group->entry ); + + return block; +} + static NTSTATUS heap_allocate_block_lfh( struct heap *heap, ULONG flags, SIZE_T block_size, SIZE_T size, void **ret ) { struct category *category, *last = heap->categories + BLOCK_SIZE_CATEGORY_COUNT - 1; + struct block *block;
category = heap->categories + BLOCK_SIZE_CATEGORY( block_size ); if (!heap->categories || category == last) return STATUS_UNSUCCESSFUL; @@ -1661,7 +1844,53 @@ static NTSTATUS heap_allocate_block_lfh( struct heap *heap, ULONG flags, SIZE_T return STATUS_UNSUCCESSFUL; }
- return STATUS_NOT_IMPLEMENTED; + block_size = BLOCK_CATEGORY_SIZE( BLOCK_SIZE_CATEGORY( block_size ) ); + + heap_lock( heap, flags ); + if ((block = find_free_block_lfh( heap, flags, block_size, category ))) + { + block_set_type( block, BLOCK_TYPE_USED ); + block_set_flags( block, ~BLOCK_FLAG_LFH, BLOCK_USER_FLAGS( flags ) ); + block_set_size( block, block_size ); + block->tail_size = block_size - sizeof(*block) - size; + initialize_block( block, 0, size, flags ); + mark_block_tail( block, flags ); + *ret = block + 1; + } + heap_unlock( heap, flags ); + + return block ? STATUS_SUCCESS : STATUS_NO_MEMORY; +} + +static NTSTATUS heap_free_block_lfh( struct heap *heap, ULONG flags, struct block *block ) +{ + struct category *category, *last = heap->categories + BLOCK_SIZE_CATEGORY_COUNT - 1; + SIZE_T i, block_size = block_get_size( block ); + struct group *group = block_get_group( block ); + NTSTATUS status = STATUS_SUCCESS; + + if (!(block_get_flags( block ) & BLOCK_FLAG_LFH)) return STATUS_UNSUCCESSFUL; + + category = heap->categories + BLOCK_SIZE_CATEGORY( block_size ); + if (category == last) return STATUS_UNSUCCESSFUL; + + heap_lock( heap, flags ); + + i = block_get_group_index( block ); + block_init_free( block, flags, NULL, block_size ); + block_set_flags( block, 0, BLOCK_FLAG_LFH ); + block_set_group( block, block_size, group ); + + /* if this was the last used block in a group and GROUP_FLAG_FREE was set */ + if ((group->free_bits |= (1 << i)) == ~0) + { + /* thread now owns the group, and can release it to its category */ + status = heap_release_category_group( heap, flags, category, group ); + } + + heap_unlock( heap, flags ); + + return status; }
/*********************************************************************** @@ -1727,6 +1956,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 (!heap_free_block_lfh( heap, heap_flags, block )) + status = STATUS_SUCCESS; else { SIZE_T block_size = block_get_size( block ); @@ -1747,10 +1978,10 @@ BOOLEAN WINAPI DECLSPEC_HOTPATCH RtlFreeHeap( HANDLE handle, ULONG flags, void * static NTSTATUS heap_resize_block( struct heap *heap, ULONG flags, struct block *block, SIZE_T block_size, SIZE_T size, SIZE_T *old_size, void **ret ) { - SUBHEAP *subheap = block_get_subheap( heap, block ); SIZE_T old_category, old_block_size; struct entry *entry; struct block *next; + SUBHEAP *subheap;
if (block_get_flags( block ) & BLOCK_FLAG_LARGE) { @@ -1779,8 +2010,29 @@ 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 (block_get_flags( block ) & BLOCK_FLAG_LFH) + { + /* as native LFH does it with different block size: refuse to resize even though we could */ + 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; + + heap_lock( heap, flags ); + + block_set_flags( block, BLOCK_FLAG_USER_MASK & ~BLOCK_FLAG_USER_INFO, BLOCK_USER_FLAGS( flags ) ); + block->tail_size = old_block_size - sizeof(*block) - size; + initialize_block( block, *old_size, size, flags ); + mark_block_tail( block, flags ); + + heap_unlock( heap, flags ); + + *ret = block + 1; + return STATUS_SUCCESS; + } + heap_lock( heap, flags );
+ subheap = block_get_subheap( heap, block ); + if (block_size > old_block_size) { if (!(next = next_block( subheap, block )) || !(block_get_flags( next ) & BLOCK_FLAG_FREE) ||