[PATCH 0/6] MR100: ntdll: More heap code cleanup.

[PATCH 1/6] ntdll: Mask block flags when computing HEAP_InsertFreeBlock size.

[Rémi Bernon]

From: Rémi Bernon

Signed-off-by: Rémi Bernon 
---
 dlls/ntdll/heap.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index 6e64d0d7dfb..8706b0f7774 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -586,7 +586,8 @@ static HEAP *HEAP_GetPtr(
  */
 static inline void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena, BOOL last )
 {
-    FREE_LIST_ENTRY *pEntry = heap->freeList + get_freelist_index( pArena->size + sizeof(*pArena) );
+    SIZE_T block_size = (pArena->size & ARENA_SIZE_MASK) + sizeof(*pArena);
+    FREE_LIST_ENTRY *pEntry = heap->freeList + get_freelist_index( block_size );
     if (last)
     {
         /* insert at end of free list, i.e. before the next free list entry */

[PATCH 2/6] ntdll: Set ARENA_FLAG_FREE flag in HEAP_CreateFreeBlock.

[Rémi Bernon]

From: Rémi Bernon

Signed-off-by: Rémi Bernon 
---
 dlls/ntdll/heap.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index 8706b0f7774..89c32fe4fa9 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -600,7 +600,6 @@ static inline void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena, BOOL la
         /* insert at head of free list */
         list_add_after( &pEntry->arena.entry, &pArena->entry );
     }
-    pArena->size |= ARENA_FLAG_FREE;
 }

@@ -726,7 +725,7 @@ static void HEAP_CreateFreeBlock( SUBHEAP *subheap, void *ptr, SIZE_T size )

/* Last, insert the new block into the free list */

-    pFree->size = size - sizeof(*pFree);
+    pFree->size = (size - sizeof(*pFree)) | ARENA_FLAG_FREE;
     HEAP_InsertFreeBlock( subheap->heap, pFree, last );
 }

[PATCH 3/6] ntdll: Move the main subheap after the free lists.

[Rémi Bernon]

From: Rémi Bernon

Signed-off-by: Rémi Bernon 
---
 dlls/ntdll/heap.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index 89c32fe4fa9..4425b0cd91e 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -186,7 +186,6 @@ typedef struct tagHEAP
     /* end of the Windows 10 compatible struct layout */

BOOL             shared;        /* System shared heap */
-    SUBHEAP          subheap;       /* First sub-heap */
     struct list      entry;         /* Entry in process heap list */
     struct list      subheap_list;  /* Sub-heap list */
     struct list      large_list;    /* Large blocks list */
@@ -195,7 +194,8 @@ typedef struct tagHEAP
     DWORD            pending_pos;   /* Position in pending free requests ring */
     ARENA_INUSE    **pending_free;  /* Ring buffer for pending free requests */
     RTL_CRITICAL_SECTION cs;
-    FREE_LIST_ENTRY *freeList;      /* Free lists */
+    FREE_LIST_ENTRY  freeList[HEAP_NB_FREE_LISTS];
+    SUBHEAP          subheap;
 } HEAP;

#define HEAP_MAGIC       ((DWORD)('H' | ('E'<<8) | ('A'<<16) | ('P'<<24)))
@@ -1008,8 +1008,6 @@ static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, LPVOID address, DWORD flags,

/* Build the free lists */

-        heap->freeList = (FREE_LIST_ENTRY *)((char *)heap + subheap->headerSize);
-        subheap->headerSize += HEAP_NB_FREE_LISTS * sizeof(FREE_LIST_ENTRY);
         list_init( &heap->freeList[0].arena.entry );
         for (i = 0, pEntry = heap->freeList; i < HEAP_NB_FREE_LISTS; i++, pEntry++)
         {

[PATCH 3/6] ntdll: Move the main subheap after the free lists.

[Marvin]

Hi,

While running your changed tests, I think I found new failures.
Being a bot and all I'm not very good at pattern recognition, so I might be
wrong, but could you please double-check?

Full results can be found at:
https://testbot.winehq.org/JobDetails.pl?Key=115140

Your paranoid android.

=== debian11 (64 bit WoW report) ===

ntdll:
env.c:461: Test failed: wrong end ptr 000000000003196C/0000000000031970

[PATCH 4/6] ntdll: Return an entry pointer when looking for a free list.

[Rémi Bernon]

From: Rémi Bernon

Signed-off-by: Rémi Bernon 
---
 dlls/ntdll/heap.c | 25 +++++++++++++------------
 1 file changed, 13 insertions(+), 12 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index 4425b0cd91e..55eb6a328fd 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -401,16 +401,19 @@ static void notify_free_all( SUBHEAP *subheap )

/* locate a free list entry of the appropriate size */
 /* size is the size of the whole block including the arena header */
-static inline unsigned int get_freelist_index( SIZE_T size )
+static inline struct entry *find_free_list( HEAP *heap, SIZE_T size, BOOL last )
 {
+    FREE_LIST_ENTRY *list, *end = heap->freeList + ARRAY_SIZE(heap->freeList);
     unsigned int i;

if (size <= HEAP_MAX_SMALL_FREE_LIST)
-        return (size - HEAP_MIN_ARENA_SIZE) / ALIGNMENT;
-
-    for (i = HEAP_NB_SMALL_FREE_LISTS; i < HEAP_NB_FREE_LISTS - 1; i++)
+        i = (size - HEAP_MIN_ARENA_SIZE) / ALIGNMENT;
+    else for (i = HEAP_NB_SMALL_FREE_LISTS; i < HEAP_NB_FREE_LISTS - 1; i++)
         if (size <= HEAP_freeListSizes[i - HEAP_NB_SMALL_FREE_LISTS]) break;
-    return i;
+
+    list = heap->freeList + i;
+    if (last && ++list == end) list = heap->freeList;
+    return &list->arena;
 }

/* get the memory protection type to use for a given heap */
@@ -587,18 +590,16 @@ static HEAP *HEAP_GetPtr(
 static inline void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena, BOOL last )
 {
     SIZE_T block_size = (pArena->size & ARENA_SIZE_MASK) + sizeof(*pArena);
-    FREE_LIST_ENTRY *pEntry = heap->freeList + get_freelist_index( block_size );
+    struct entry *list = find_free_list( heap, block_size, last );
     if (last)
     {
         /* insert at end of free list, i.e. before the next free list entry */
-        pEntry++;
-        if (pEntry == &heap->freeList[HEAP_NB_FREE_LISTS]) pEntry = heap->freeList;
-        list_add_before( &pEntry->arena.entry, &pArena->entry );
+        list_add_before( &list->entry, &pArena->entry );
     }
     else
     {
         /* insert at head of free list */
-        list_add_after( &pEntry->arena.entry, &pArena->entry );
+        list_add_after( &list->entry, &pArena->entry );
     }
 }

@@ -1065,14 +1066,14 @@ static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, LPVOID address, DWORD flags,
  */
 static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T data_size, SUBHEAP **ppSubHeap )
 {
+    struct entry *entry = find_free_list( heap, data_size + sizeof(ARENA_INUSE), FALSE );
     SUBHEAP *subheap;
     struct list *ptr;
     SIZE_T total_size;
-    FREE_LIST_ENTRY *pEntry = heap->freeList + get_freelist_index( data_size + sizeof(ARENA_INUSE) );

/* Find a suitable free list, and in it find a block large enough */

-    ptr = &pEntry->arena.entry;
+    ptr = &entry->entry;
     while ((ptr = list_next( &heap->freeList[0].arena.entry, ptr )))
     {
         ARENA_FREE *pArena = LIST_ENTRY( ptr, ARENA_FREE, entry );

[PATCH 4/6] ntdll: Return an entry pointer when looking for a free list.

[Marvin]

Hi,

While running your changed tests, I think I found new failures.
Being a bot and all I'm not very good at pattern recognition, so I might be
wrong, but could you please double-check?

Full results can be found at:
https://testbot.winehq.org/JobDetails.pl?Key=115141

Your paranoid android.

=== debian11 (64 bit WoW report) ===

ntdll:
env.c:461: Test failed: wrong end ptr 000000000003196C/0000000000031970

[PATCH 5/6] ntdll: Remove entries from the free list in HEAP_FindFreeBlock.

[Rémi Bernon]

From: Rémi Bernon

Signed-off-by: Rémi Bernon 
---
 dlls/ntdll/heap.c | 17 ++++++++---------
 1 file changed, 8 insertions(+), 9 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index 55eb6a328fd..472f8f11adc 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -1067,23 +1067,24 @@ static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, LPVOID address, DWORD flags,
 static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T data_size, SUBHEAP **ppSubHeap )
 {
     struct entry *entry = find_free_list( heap, data_size + sizeof(ARENA_INUSE), FALSE );
+    SIZE_T total_size, arena_size;
+    ARENA_FREE *pArena;
     SUBHEAP *subheap;
     struct list *ptr;
-    SIZE_T total_size;

/* Find a suitable free list, and in it find a block large enough */

ptr = &entry->entry;
     while ((ptr = list_next( &heap->freeList[0].arena.entry, ptr )))
     {
-        ARENA_FREE *pArena = LIST_ENTRY( ptr, ARENA_FREE, entry );
-        SIZE_T arena_size = (pArena->size & ARENA_SIZE_MASK) +
-                            sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
+        pArena = LIST_ENTRY( ptr, ARENA_FREE, entry );
+        arena_size = (pArena->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
         if (arena_size >= data_size)
         {
             subheap = find_subheap( heap, (struct block *)pArena, FALSE );
             if (!HEAP_Commit( subheap, (ARENA_INUSE *)pArena, data_size )) return NULL;
             *ppSubHeap = subheap;
+            list_remove( &pArena->entry );
             return pArena;
         }
     }
@@ -1120,7 +1121,9 @@ static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T data_size, SUBHEAP **p
           subheap, subheap->size, heap );

*ppSubHeap = subheap;
-    return (ARENA_FREE *)((char *)subheap->base + subheap->headerSize);
+    pArena = (ARENA_FREE *)((char *)subheap->base + subheap->headerSize);
+    list_remove( &pArena->entry );
+    return pArena;
 }

@@ -1553,10 +1556,6 @@ static NTSTATUS heap_allocate( HEAP *heap, ULONG flags, SIZE_T size, void **ret

if (!(entry = HEAP_FindFreeBlock( heap, data_size, &subheap ))) return STATUS_NO_MEMORY;

-    /* Remove the arena from the free list */
-
-    list_remove( &entry->entry );
-
     /* Build the in-use arena */

block = (struct block *)entry;

[PATCH 5/6] ntdll: Remove entries from the free list in HEAP_FindFreeBlock.

[Marvin]

Hi,

While running your changed tests, I think I found new failures.
Being a bot and all I'm not very good at pattern recognition, so I might be
wrong, but could you please double-check?

Full results can be found at:
https://testbot.winehq.org/JobDetails.pl?Key=115142

Your paranoid android.

=== debian11 (64 bit WoW report) ===

ntdll:
env.c:461: Test failed: wrong end ptr 000000000003196C/0000000000031970

[PATCH 6/6] ntdll: Cleanup HEAP_FindFreeBlock and rename it to find_free_block.

[Rémi Bernon]

From: Rémi Bernon

Returning a struct block pointer directly.

Signed-off-by: Rémi Bernon 
---
 dlls/ntdll/heap.c | 57 +++++++++++++++++------------------------------
 1 file changed, 20 insertions(+), 37 deletions(-)

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index 472f8f11adc..96bb0d0c027 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -1058,34 +1058,24 @@ static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, LPVOID address, DWORD flags,
 }

-/***********************************************************************
- *           HEAP_FindFreeBlock
- *
- * Find a free block at least as large as the requested size, and make sure
- * the requested size is committed.
- */
-static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T data_size, SUBHEAP **ppSubHeap )
+static struct block *find_free_block( HEAP *heap, SIZE_T data_size, SUBHEAP **subheap )
 {
-    struct entry *entry = find_free_list( heap, data_size + sizeof(ARENA_INUSE), FALSE );
+    struct list *ptr = &find_free_list( heap, data_size + sizeof(ARENA_INUSE), FALSE )->entry;
     SIZE_T total_size, arena_size;
-    ARENA_FREE *pArena;
-    SUBHEAP *subheap;
-    struct list *ptr;
+    struct entry *entry;

/* Find a suitable free list, and in it find a block large enough */

-    ptr = &entry->entry;
     while ((ptr = list_next( &heap->freeList[0].arena.entry, ptr )))
     {
-        pArena = LIST_ENTRY( ptr, ARENA_FREE, entry );
-        arena_size = (pArena->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
+        entry = LIST_ENTRY( ptr, struct entry, entry );
+        arena_size = (entry->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
         if (arena_size >= data_size)
         {
-            subheap = find_subheap( heap, (struct block *)pArena, FALSE );
-            if (!HEAP_Commit( subheap, (ARENA_INUSE *)pArena, data_size )) return NULL;
-            *ppSubHeap = subheap;
-            list_remove( &pArena->entry );
-            return pArena;
+            *subheap = find_subheap( heap, (struct block *)entry, FALSE );
+            if (!HEAP_Commit( *subheap, (struct block *)entry, data_size )) return NULL;
+            list_remove( &entry->entry );
+            return (struct block *)entry;
         }
     }

@@ -1104,26 +1094,24 @@ static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T data_size, SUBHEAP **p
     total_size = data_size + ROUND_SIZE(sizeof(SUBHEAP)) + sizeof(ARENA_INUSE) + sizeof(ARENA_FREE);
     if (total_size < data_size) return NULL;  /* overflow */

-    if ((subheap = HEAP_CreateSubHeap( heap, NULL, heap->flags, total_size,
-                                       max( heap->grow_size, total_size ) )))
+    if ((*subheap = HEAP_CreateSubHeap( heap, NULL, heap->flags, total_size,
+                                        max( heap->grow_size, total_size ) )))
     {
         if (heap->grow_size < 128 * 1024 * 1024) heap->grow_size *= 2;
     }
-    else while (!subheap)  /* shrink the grow size again if we are running out of space */
+    else while (!*subheap)  /* shrink the grow size again if we are running out of space */
     {
         if (heap->grow_size <= total_size || heap->grow_size <= 4 * 1024 * 1024) return NULL;
         heap->grow_size /= 2;
-        subheap = HEAP_CreateSubHeap( heap, NULL, heap->flags, total_size,
-                                      max( heap->grow_size, total_size ) );
+        *subheap = HEAP_CreateSubHeap( heap, NULL, heap->flags, total_size,
+                                       max( heap->grow_size, total_size ) );
     }

-    TRACE("created new sub-heap %p of %08lx bytes for heap %p\n",
-          subheap, subheap->size, heap );
+    TRACE( "created new sub-heap %p of %08lx bytes for heap %p\n", *subheap, subheap_size( *subheap ), heap );

-    *ppSubHeap = subheap;
-    pArena = (ARENA_FREE *)((char *)subheap->base + subheap->headerSize);
-    list_remove( &pArena->entry );
-    return pArena;
+    entry = first_block( *subheap );
+    list_remove( &entry->entry );
+    return (struct block *)entry;
 }

@@ -1538,7 +1526,6 @@ HANDLE WINAPI RtlDestroyHeap( HANDLE heap )
 static NTSTATUS heap_allocate( HEAP *heap, ULONG flags, SIZE_T size, void **ret )
 {
     struct block *block;
-    struct entry *entry;
     SIZE_T data_size;
     SUBHEAP *subheap;

@@ -1554,15 +1541,11 @@ static NTSTATUS heap_allocate( HEAP *heap, ULONG flags, SIZE_T size, void **ret

/* Locate a suitable free block */

-    if (!(entry = HEAP_FindFreeBlock( heap, data_size, &subheap ))) return STATUS_NO_MEMORY;
-
-    /* Build the in-use arena */
-
-    block = (struct block *)entry;
+    if (!(block = find_free_block( heap, data_size, &subheap ))) return STATUS_NO_MEMORY;

/* in-use arena is smaller than free arena,
      * so we have to add the difference to the size */
-    block->size  = (block->size & ~ARENA_FLAG_FREE) + sizeof(*entry) - sizeof(*block);
+    block->size  = (block->size & ~ARENA_FLAG_FREE) + sizeof(struct entry) - sizeof(*block);
     block->magic = ARENA_INUSE_MAGIC;

/* Shrink the block */

[PATCH 6/6] ntdll: Cleanup HEAP_FindFreeBlock and rename it to find_free_block.

[Marvin]

Hi,

While running your changed tests, I think I found new failures.
Being a bot and all I'm not very good at pattern recognition, so I might be
wrong, but could you please double-check?

Full results can be found at:
https://testbot.winehq.org/JobDetails.pl?Key=115143

Your paranoid android.

=== debian11 (64 bit WoW report) ===

ntdll:
env.c:461: Test failed: wrong end ptr 000000000003196C/0000000000031970