?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Converted the heap free lists to standard lists.
[wine.git] / dlls / ntdll / heap.c
blob1a38e95d2e26e8ec29c861abfd25a51fbb1da5ce
1 /*
2 * Win32 heap functions
3 *
4 * Copyright 1996 Alexandre Julliard
5 * Copyright 1998 Ulrich Weigand
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21
22 #include "config.h"
23
24 #include <assert.h>
25 #include <stdlib.h>
26 #include <stdarg.h>
27 #include <stdio.h>
28 #include <string.h>
29 #ifdef HAVE_VALGRIND_MEMCHECK_H
30 #include <valgrind/memcheck.h>
31 #endif
32
33 #define NONAMELESSUNION
34 #define NONAMELESSSTRUCT
35 #include "ntstatus.h"
36 #include "windef.h"
37 #include "winternl.h"
38 #include "winnt.h"
39 #include "winternl.h"
40 #include "wine/list.h"
41 #include "wine/debug.h"
42 #include "wine/server.h"
43
44 WINE_DEFAULT_DEBUG_CHANNEL(heap);
45
46 /* Note: the heap data structures are based on what Pietrek describes in his
47 * book 'Windows 95 System Programming Secrets'. The layout is not exactly
48 * the same, but could be easily adapted if it turns out some programs
49 * require it.
50 */
51
52 /* FIXME: use SIZE_T for 'size' structure members, but we need to make sure
53 * that there is no unaligned accesses to structure fields.
54 */
55
56 typedef struct tagARENA_INUSE
57 {
58 DWORD size; /* Block size; must be the first field */
59 DWORD magic : 27; /* Magic number */
60 DWORD unused_bytes : 5; /* Number of bytes in the block not used by user data (max value is HEAP_MIN_BLOCK_SIZE+ALIGNMENT) */
61 } ARENA_INUSE;
62
63 typedef struct tagARENA_FREE
64 {
65 DWORD size; /* Block size; must be the first field */
66 DWORD magic; /* Magic number */
67 struct list entry; /* Entry in free list */
68 } ARENA_FREE;
69
70 #define ARENA_FLAG_FREE 0x00000001 /* flags OR'ed with arena size */
71 #define ARENA_FLAG_PREV_FREE 0x00000002
72 #define ARENA_SIZE_MASK (~3)
73 #define ARENA_INUSE_MAGIC 0x4455355 /* Value for arena 'magic' field */
74 #define ARENA_FREE_MAGIC 0x45455246 /* Value for arena 'magic' field */
75
76 #define ARENA_INUSE_FILLER 0x55
77 #define ARENA_FREE_FILLER 0xaa
78
79 #define ALIGNMENT 8 /* everything is aligned on 8 byte boundaries */
80 #define ROUND_SIZE(size) (((size) + ALIGNMENT - 1) & ~(ALIGNMENT-1))
81
82 #define QUIET 1 /* Suppress messages */
83 #define NOISY 0 /* Report all errors */
84
85 #define HEAP_NB_FREE_LISTS 4 /* Number of free lists */
86
87 /* Max size of the blocks on the free lists */
88 static const DWORD HEAP_freeListSizes[HEAP_NB_FREE_LISTS] =
89 {
90 0x20, 0x80, 0x200, ~0UL
91 };
92
93 typedef struct
94 {
95 DWORD size;
96 ARENA_FREE arena;
97 } FREE_LIST_ENTRY;
98
99 struct tagHEAP;
100
101 typedef struct tagSUBHEAP
102 {
103 DWORD size; /* Size of the whole sub-heap */
104 DWORD commitSize; /* Committed size of the sub-heap */
105 DWORD headerSize; /* Size of the heap header */
106 struct tagSUBHEAP *next; /* Next sub-heap */
107 struct tagHEAP *heap; /* Main heap structure */
108 DWORD magic; /* Magic number */
109 } SUBHEAP;
110
111 #define SUBHEAP_MAGIC ((DWORD)('S' | ('U'<<8) | ('B'<<16) | ('H'<<24)))
112
113 typedef struct tagHEAP
114 {
115 SUBHEAP subheap; /* First sub-heap */
116 struct tagHEAP *next; /* Next heap for this process */
117 RTL_CRITICAL_SECTION critSection; /* Critical section for serialization */
118 FREE_LIST_ENTRY freeList[HEAP_NB_FREE_LISTS]; /* Free lists */
119 DWORD flags; /* Heap flags */
120 DWORD magic; /* Magic number */
121 } HEAP;
122
123 #define HEAP_MAGIC ((DWORD)('H' | ('E'<<8) | ('A'<<16) | ('P'<<24)))
124
125 #define HEAP_DEF_SIZE 0x110000 /* Default heap size = 1Mb + 64Kb */
126 #define HEAP_MIN_BLOCK_SIZE (8+sizeof(ARENA_FREE)) /* Min. heap block size */
127 #define COMMIT_MASK 0xffff /* bitmask for commit/decommit granularity */
128
129 static HANDLE processHeap; /* main process heap */
130
131 static HEAP *firstHeap; /* head of secondary heaps list */
132
133 static BOOL HEAP_IsRealArena( HEAP *heapPtr, DWORD flags, LPCVOID block, BOOL quiet );
134
135 /* mark a block of memory as free for debugging purposes */
136 static inline void mark_block_free( void *ptr, SIZE_T size )
137 {
138 if (TRACE_ON(heap)) memset( ptr, ARENA_FREE_FILLER, size );
139 #ifdef VALGRIND_MAKE_NOACCESS
140 VALGRIND_DISCARD( VALGRIND_MAKE_NOACCESS( ptr, size ));
141 #endif
142 }
143
144 /* mark a block of memory as initialized for debugging purposes */
145 static inline void mark_block_initialized( void *ptr, SIZE_T size )
146 {
147 #ifdef VALGRIND_MAKE_READABLE
148 VALGRIND_DISCARD( VALGRIND_MAKE_READABLE( ptr, size ));
149 #endif
150 }
151
152 /* mark a block of memory as uninitialized for debugging purposes */
153 static inline void mark_block_uninitialized( void *ptr, SIZE_T size )
154 {
155 #ifdef VALGRIND_MAKE_WRITABLE
156 VALGRIND_DISCARD( VALGRIND_MAKE_WRITABLE( ptr, size ));
157 #endif
158 if (TRACE_ON(heap))
159 {
160 memset( ptr, ARENA_INUSE_FILLER, size );
161 #ifdef VALGRIND_MAKE_WRITABLE
162 /* make it uninitialized to valgrind again */
163 VALGRIND_DISCARD( VALGRIND_MAKE_WRITABLE( ptr, size ));
164 #endif
165 }
166 }
167
168 /* clear contents of a block of memory */
169 static inline void clear_block( void *ptr, SIZE_T size )
170 {
171 mark_block_initialized( ptr, size );
172 memset( ptr, 0, size );
173 }
174
175 static RTL_CRITICAL_SECTION_DEBUG process_heap_critsect_debug =
176 {
177 0, 0, NULL, /* will be set later */
178 { &process_heap_critsect_debug.ProcessLocksList, &process_heap_critsect_debug.ProcessLocksList },
179 0, 0, { 0, (DWORD)(__FILE__ ": main process heap section") }
180 };
181
182
183 /***********************************************************************
184 * HEAP_Dump
185 */
186 static void HEAP_Dump( HEAP *heap )
187 {
188 int i;
189 SUBHEAP *subheap;
190 char *ptr;
191
192 DPRINTF( "Heap: %p\n", heap );
193 DPRINTF( "Next: %p Sub-heaps: %p", heap->next, &heap->subheap );
194 subheap = &heap->subheap;
195 while (subheap->next)
196 {
197 DPRINTF( " -> %p", subheap->next );
198 subheap = subheap->next;
199 }
200
201 DPRINTF( "\nFree lists:\n Block Stat Size Id\n" );
202 for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
203 DPRINTF( "%p free %08lx prev=%p next=%p\n",
204 &heap->freeList[i].arena, heap->freeList[i].size,
205 LIST_ENTRY( heap->freeList[i].arena.entry.prev, ARENA_FREE, entry ),
206 LIST_ENTRY( heap->freeList[i].arena.entry.next, ARENA_FREE, entry ));
207
208 subheap = &heap->subheap;
209 while (subheap)
210 {
211 SIZE_T freeSize = 0, usedSize = 0, arenaSize = subheap->headerSize;
212 DPRINTF( "\n\nSub-heap %p: size=%08lx committed=%08lx\n",
213 subheap, subheap->size, subheap->commitSize );
214
215 DPRINTF( "\n Block Stat Size Id\n" );
216 ptr = (char*)subheap + subheap->headerSize;
217 while (ptr < (char *)subheap + subheap->size)
218 {
219 if (*(DWORD *)ptr & ARENA_FLAG_FREE)
220 {
221 ARENA_FREE *pArena = (ARENA_FREE *)ptr;
222 DPRINTF( "%p free %08lx prev=%p next=%p\n",
223 pArena, pArena->size & ARENA_SIZE_MASK,
224 LIST_ENTRY( pArena->entry.prev, ARENA_FREE, entry ),
225 LIST_ENTRY( pArena->entry.next, ARENA_FREE, entry ) );
226 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
227 arenaSize += sizeof(ARENA_FREE);
228 freeSize += pArena->size & ARENA_SIZE_MASK;
229 }
230 else if (*(DWORD *)ptr & ARENA_FLAG_PREV_FREE)
231 {
232 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
233 DPRINTF( "%p Used %08lx back=%08lx\n",
234 pArena, pArena->size & ARENA_SIZE_MASK, *((DWORD *)pArena - 1) );
235 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
236 arenaSize += sizeof(ARENA_INUSE);
237 usedSize += pArena->size & ARENA_SIZE_MASK;
238 }
239 else
240 {
241 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
242 DPRINTF( "%p used %08lx\n", pArena, pArena->size & ARENA_SIZE_MASK );
243 ptr += sizeof(*pArena) + (pArena->size & ARENA_SIZE_MASK);
244 arenaSize += sizeof(ARENA_INUSE);
245 usedSize += pArena->size & ARENA_SIZE_MASK;
246 }
247 }
248 DPRINTF( "\nTotal: Size=%08lx Committed=%08lx Free=%08lx Used=%08lx Arenas=%08lx (%ld%%)\n\n",
249 subheap->size, subheap->commitSize, freeSize, usedSize,
250 arenaSize, (arenaSize * 100) / subheap->size );
251 subheap = subheap->next;
252 }
253 }
254
255
256 static void HEAP_DumpEntry( LPPROCESS_HEAP_ENTRY entry )
257 {
258 WORD rem_flags;
259 TRACE( "Dumping entry %p\n", entry );
260 TRACE( "lpData\t\t: %p\n", entry->lpData );
261 TRACE( "cbData\t\t: %08lx\n", entry->cbData);
262 TRACE( "cbOverhead\t: %08x\n", entry->cbOverhead);
263 TRACE( "iRegionIndex\t: %08x\n", entry->iRegionIndex);
264 TRACE( "WFlags\t\t: ");
265 if (entry->wFlags & PROCESS_HEAP_REGION)
266 TRACE( "PROCESS_HEAP_REGION ");
267 if (entry->wFlags & PROCESS_HEAP_UNCOMMITTED_RANGE)
268 TRACE( "PROCESS_HEAP_UNCOMMITTED_RANGE ");
269 if (entry->wFlags & PROCESS_HEAP_ENTRY_BUSY)
270 TRACE( "PROCESS_HEAP_ENTRY_BUSY ");
271 if (entry->wFlags & PROCESS_HEAP_ENTRY_MOVEABLE)
272 TRACE( "PROCESS_HEAP_ENTRY_MOVEABLE ");
273 if (entry->wFlags & PROCESS_HEAP_ENTRY_DDESHARE)
274 TRACE( "PROCESS_HEAP_ENTRY_DDESHARE ");
275 rem_flags = entry->wFlags &
276 ~(PROCESS_HEAP_REGION | PROCESS_HEAP_UNCOMMITTED_RANGE |
277 PROCESS_HEAP_ENTRY_BUSY | PROCESS_HEAP_ENTRY_MOVEABLE|
278 PROCESS_HEAP_ENTRY_DDESHARE);
279 if (rem_flags)
280 TRACE( "Unknown %08x", rem_flags);
281 TRACE( "\n");
282 if ((entry->wFlags & PROCESS_HEAP_ENTRY_BUSY )
283 && (entry->wFlags & PROCESS_HEAP_ENTRY_MOVEABLE))
284 {
285 /* Treat as block */
286 TRACE( "BLOCK->hMem\t\t:%p\n", entry->u.Block.hMem);
287 }
288 if (entry->wFlags & PROCESS_HEAP_REGION)
289 {
290 TRACE( "Region.dwCommittedSize\t:%08lx\n",entry->u.Region.dwCommittedSize);
291 TRACE( "Region.dwUnCommittedSize\t:%08lx\n",entry->u.Region.dwUnCommittedSize);
292 TRACE( "Region.lpFirstBlock\t:%p\n",entry->u.Region.lpFirstBlock);
293 TRACE( "Region.lpLastBlock\t:%p\n",entry->u.Region.lpLastBlock);
294 }
295 }
296
297 /***********************************************************************
298 * HEAP_GetPtr
299 * RETURNS
300 * Pointer to the heap
301 * NULL: Failure
302 */
303 static HEAP *HEAP_GetPtr(
304 HANDLE heap /* [in] Handle to the heap */
305 ) {
306 HEAP *heapPtr = (HEAP *)heap;
307 if (!heapPtr || (heapPtr->magic != HEAP_MAGIC))
308 {
309 ERR("Invalid heap %p!\n", heap );
310 return NULL;
311 }
312 if (TRACE_ON(heap) && !HEAP_IsRealArena( heapPtr, 0, NULL, NOISY ))
313 {
314 HEAP_Dump( heapPtr );
315 assert( FALSE );
316 return NULL;
317 }
318 return heapPtr;
319 }
320
321
322 /***********************************************************************
323 * HEAP_InsertFreeBlock
324 *
325 * Insert a free block into the free list.
326 */
327 static inline void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena, BOOL last )
328 {
329 FREE_LIST_ENTRY *pEntry = heap->freeList;
330 while (pEntry->size < pArena->size) pEntry++;
331 if (last)
332 {
333 /* insert at end of free list, i.e. before the next free list entry */
334 pEntry++;
335 if (pEntry == &heap->freeList[HEAP_NB_FREE_LISTS]) pEntry = heap->freeList;
336 list_add_before( &pEntry->arena.entry, &pArena->entry );
337 }
338 else
339 {
340 /* insert at head of free list */
341 list_add_after( &pEntry->arena.entry, &pArena->entry );
342 }
343 pArena->size |= ARENA_FLAG_FREE;
344 }
345
346
347 /***********************************************************************
348 * HEAP_FindSubHeap
349 * Find the sub-heap containing a given address.
350 *
351 * RETURNS
352 * Pointer: Success
353 * NULL: Failure
354 */
355 static SUBHEAP *HEAP_FindSubHeap(
356 const HEAP *heap, /* [in] Heap pointer */
357 LPCVOID ptr /* [in] Address */
358 ) {
359 const SUBHEAP *sub = &heap->subheap;
360 while (sub)
361 {
362 if (((const char *)ptr >= (const char *)sub) &&
363 ((const char *)ptr < (const char *)sub + sub->size)) return (SUBHEAP*)sub;
364 sub = sub->next;
365 }
366 return NULL;
367 }
368
369
370 /***********************************************************************
371 * HEAP_Commit
372 *
373 * Make sure the heap storage is committed up to (not including) ptr.
374 */
375 static inline BOOL HEAP_Commit( SUBHEAP *subheap, void *ptr )
376 {
377 SIZE_T size = (SIZE_T)((char *)ptr - (char *)subheap);
378 size = (size + COMMIT_MASK) & ~COMMIT_MASK;
379 if (size > subheap->size) size = subheap->size;
380 if (size <= subheap->commitSize) return TRUE;
381 size -= subheap->commitSize;
382 ptr = (char *)subheap + subheap->commitSize;
383 if (NtAllocateVirtualMemory( NtCurrentProcess(), &ptr, 0,
384 &size, MEM_COMMIT, PAGE_READWRITE ))
385 {
386 WARN("Could not commit %08lx bytes at %p for heap %p\n",
387 size, ptr, subheap->heap );
388 return FALSE;
389 }
390 subheap->commitSize += size;
391 return TRUE;
392 }
393
394
395 /***********************************************************************
396 * HEAP_Decommit
397 *
398 * If possible, decommit the heap storage from (including) 'ptr'.
399 */
400 static inline BOOL HEAP_Decommit( SUBHEAP *subheap, void *ptr )
401 {
402 void *addr;
403 SIZE_T decommit_size;
404 SIZE_T size = (char *)ptr - (char *)subheap;
405
406 /* round to next block and add one full block */
407 size = ((size + COMMIT_MASK) & ~COMMIT_MASK) + COMMIT_MASK + 1;
408 if (size >= subheap->commitSize) return TRUE;
409 decommit_size = subheap->commitSize - size;
410 addr = (char *)subheap + size;
411
412 if (NtFreeVirtualMemory( NtCurrentProcess(), &addr, &decommit_size, MEM_DECOMMIT ))
413 {
414 WARN("Could not decommit %08lx bytes at %p for heap %p\n",
415 decommit_size, (char *)subheap + size, subheap->heap );
416 return FALSE;
417 }
418 subheap->commitSize -= decommit_size;
419 return TRUE;
420 }
421
422
423 /***********************************************************************
424 * HEAP_CreateFreeBlock
425 *
426 * Create a free block at a specified address. 'size' is the size of the
427 * whole block, including the new arena.
428 */
429 static void HEAP_CreateFreeBlock( SUBHEAP *subheap, void *ptr, SIZE_T size )
430 {
431 ARENA_FREE *pFree;
432 char *pEnd;
433 BOOL last;
434
435 /* Create a free arena */
436 mark_block_uninitialized( ptr, sizeof( ARENA_FREE ) );
437 pFree = (ARENA_FREE *)ptr;
438 pFree->magic = ARENA_FREE_MAGIC;
439
440 /* If debugging, erase the freed block content */
441
442 pEnd = (char *)ptr + size;
443 if (pEnd > (char *)subheap + subheap->commitSize) pEnd = (char *)subheap + subheap->commitSize;
444 if (pEnd > (char *)(pFree + 1)) mark_block_free( pFree + 1, pEnd - (char *)(pFree + 1) );
445
446 /* Check if next block is free also */
447
448 if (((char *)ptr + size < (char *)subheap + subheap->size) &&
449 (*(DWORD *)((char *)ptr + size) & ARENA_FLAG_FREE))
450 {
451 /* Remove the next arena from the free list */
452 ARENA_FREE *pNext = (ARENA_FREE *)((char *)ptr + size);
453 list_remove( &pNext->entry );
454 size += (pNext->size & ARENA_SIZE_MASK) + sizeof(*pNext);
455 mark_block_free( pNext, sizeof(ARENA_FREE) );
456 }
457
458 /* Set the next block PREV_FREE flag and pointer */
459
460 last = ((char *)ptr + size >= (char *)subheap + subheap->size);
461 if (!last)
462 {
463 DWORD *pNext = (DWORD *)((char *)ptr + size);
464 *pNext |= ARENA_FLAG_PREV_FREE;
465 mark_block_initialized( pNext - 1, sizeof( ARENA_FREE * ) );
466 *(ARENA_FREE **)(pNext - 1) = pFree;
467 }
468
469 /* Last, insert the new block into the free list */
470
471 pFree->size = size - sizeof(*pFree);
472 HEAP_InsertFreeBlock( subheap->heap, pFree, last );
473 }
474
475
476 /***********************************************************************
477 * HEAP_MakeInUseBlockFree
478 *
479 * Turn an in-use block into a free block. Can also decommit the end of
480 * the heap, and possibly even free the sub-heap altogether.
481 */
482 static void HEAP_MakeInUseBlockFree( SUBHEAP *subheap, ARENA_INUSE *pArena )
483 {
484 ARENA_FREE *pFree;
485 SIZE_T size = (pArena->size & ARENA_SIZE_MASK) + sizeof(*pArena);
486
487 /* Check if we can merge with previous block */
488
489 if (pArena->size & ARENA_FLAG_PREV_FREE)
490 {
491 pFree = *((ARENA_FREE **)pArena - 1);
492 size += (pFree->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE);
493 /* Remove it from the free list */
494 list_remove( &pFree->entry );
495 }
496 else pFree = (ARENA_FREE *)pArena;
497
498 /* Create a free block */
499
500 HEAP_CreateFreeBlock( subheap, pFree, size );
501 size = (pFree->size & ARENA_SIZE_MASK) + sizeof(ARENA_FREE);
502 if ((char *)pFree + size < (char *)subheap + subheap->size)
503 return; /* Not the last block, so nothing more to do */
504
505 /* Free the whole sub-heap if it's empty and not the original one */
506
507 if (((char *)pFree == (char *)subheap + subheap->headerSize) &&
508 (subheap != &subheap->heap->subheap))
509 {
510 SIZE_T size = 0;
511 SUBHEAP *pPrev = &subheap->heap->subheap;
512 /* Remove the free block from the list */
513 list_remove( &pFree->entry );
514 /* Remove the subheap from the list */
515 while (pPrev && (pPrev->next != subheap)) pPrev = pPrev->next;
516 if (pPrev) pPrev->next = subheap->next;
517 /* Free the memory */
518 subheap->magic = 0;
519 NtFreeVirtualMemory( NtCurrentProcess(), (void **)&subheap, &size, MEM_RELEASE );
520 return;
521 }
522
523 /* Decommit the end of the heap */
524
525 if (!(subheap->heap->flags & HEAP_SHARED)) HEAP_Decommit( subheap, pFree + 1 );
526 }
527
528
529 /***********************************************************************
530 * HEAP_ShrinkBlock
531 *
532 * Shrink an in-use block.
533 */
534 static void HEAP_ShrinkBlock(SUBHEAP *subheap, ARENA_INUSE *pArena, SIZE_T size)
535 {
536 if ((pArena->size & ARENA_SIZE_MASK) >= size + HEAP_MIN_BLOCK_SIZE)
537 {
538 HEAP_CreateFreeBlock( subheap, (char *)(pArena + 1) + size,
539 (pArena->size & ARENA_SIZE_MASK) - size );
540 /* assign size plus previous arena flags */
541 pArena->size = size | (pArena->size & ~ARENA_SIZE_MASK);
542 }
543 else
544 {
545 /* Turn off PREV_FREE flag in next block */
546 char *pNext = (char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK);
547 if (pNext < (char *)subheap + subheap->size)
548 *(DWORD *)pNext &= ~ARENA_FLAG_PREV_FREE;
549 }
550 }
551
552 /***********************************************************************
553 * HEAP_InitSubHeap
554 */
555 static BOOL HEAP_InitSubHeap( HEAP *heap, LPVOID address, DWORD flags,
556 SIZE_T commitSize, SIZE_T totalSize )
557 {
558 SUBHEAP *subheap;
559 FREE_LIST_ENTRY *pEntry;
560 int i;
561
562 /* Commit memory */
563
564 if (flags & HEAP_SHARED)
565 commitSize = totalSize; /* always commit everything in a shared heap */
566 if (NtAllocateVirtualMemory( NtCurrentProcess(), &address, 0,
567 &commitSize, MEM_COMMIT, PAGE_READWRITE ))
568 {
569 WARN("Could not commit %08lx bytes for sub-heap %p\n", commitSize, address );
570 return FALSE;
571 }
572
573 /* Fill the sub-heap structure */
574
575 subheap = (SUBHEAP *)address;
576 subheap->heap = heap;
577 subheap->size = totalSize;
578 subheap->commitSize = commitSize;
579 subheap->magic = SUBHEAP_MAGIC;
580
581 if ( subheap != (SUBHEAP *)heap )
582 {
583 /* If this is a secondary subheap, insert it into list */
584
585 subheap->headerSize = ROUND_SIZE( sizeof(SUBHEAP) );
586 subheap->next = heap->subheap.next;
587 heap->subheap.next = subheap;
588 }
589 else
590 {
591 /* If this is a primary subheap, initialize main heap */
592
593 subheap->headerSize = ROUND_SIZE( sizeof(HEAP) );
594 subheap->next = NULL;
595 heap->next = NULL;
596 heap->flags = flags;
597 heap->magic = HEAP_MAGIC;
598
599 /* Build the free lists */
600
601 list_init( &heap->freeList[0].arena.entry );
602 for (i = 0, pEntry = heap->freeList; i < HEAP_NB_FREE_LISTS; i++, pEntry++)
603 {
604 pEntry->size = HEAP_freeListSizes[i];
605 pEntry->arena.size = 0 | ARENA_FLAG_FREE;
606 pEntry->arena.magic = ARENA_FREE_MAGIC;
607 if (i) list_add_after( &pEntry[-1].arena.entry, &pEntry->arena.entry );
608 }
609
610 /* Initialize critical section */
611
612 if (!processHeap) /* do it by hand to avoid memory allocations */
613 {
614 heap->critSection.DebugInfo = &process_heap_critsect_debug;
615 heap->critSection.LockCount = -1;
616 heap->critSection.RecursionCount = 0;
617 heap->critSection.OwningThread = 0;
618 heap->critSection.LockSemaphore = 0;
619 heap->critSection.SpinCount = 0;
620 process_heap_critsect_debug.CriticalSection = &heap->critSection;
621 }
622 else RtlInitializeCriticalSection( &heap->critSection );
623
624 if (flags & HEAP_SHARED)
625 {
626 /* let's assume that only one thread at a time will try to do this */
627 HANDLE sem = heap->critSection.LockSemaphore;
628 if (!sem) NtCreateSemaphore( &sem, SEMAPHORE_ALL_ACCESS, NULL, 0, 1 );
629
630 NtDuplicateObject( NtCurrentProcess(), sem, NtCurrentProcess(), &sem, 0, 0,
631 DUP_HANDLE_MAKE_GLOBAL | DUP_HANDLE_SAME_ACCESS | DUP_HANDLE_CLOSE_SOURCE );
632 heap->critSection.LockSemaphore = sem;
633 }
634 }
635
636 /* Create the first free block */
637
638 HEAP_CreateFreeBlock( subheap, (LPBYTE)subheap + subheap->headerSize,
639 subheap->size - subheap->headerSize );
640
641 return TRUE;
642 }
643
644 /***********************************************************************
645 * HEAP_CreateSubHeap
646 *
647 * Create a sub-heap of the given size.
648 * If heap == NULL, creates a main heap.
649 */
650 static SUBHEAP *HEAP_CreateSubHeap( HEAP *heap, void *base, DWORD flags,
651 SIZE_T commitSize, SIZE_T totalSize )
652 {
653 LPVOID address = base;
654
655 /* round-up sizes on a 64K boundary */
656 totalSize = (totalSize + 0xffff) & 0xffff0000;
657 commitSize = (commitSize + 0xffff) & 0xffff0000;
658 if (!commitSize) commitSize = 0x10000;
659 if (totalSize < commitSize) totalSize = commitSize;
660
661 if (!address)
662 {
663 /* allocate the memory block */
664 if (NtAllocateVirtualMemory( NtCurrentProcess(), &address, 0, &totalSize,
665 MEM_RESERVE, PAGE_READWRITE ))
666 {
667 WARN("Could not allocate %08lx bytes\n", totalSize );
668 return NULL;
669 }
670 }
671
672 /* Initialize subheap */
673
674 if (!HEAP_InitSubHeap( heap ? heap : (HEAP *)address,
675 address, flags, commitSize, totalSize ))
676 {
677 SIZE_T size = 0;
678 if (!base) NtFreeVirtualMemory( NtCurrentProcess(), &address, &size, MEM_RELEASE );
679 return NULL;
680 }
681
682 return (SUBHEAP *)address;
683 }
684
685
686 /***********************************************************************
687 * HEAP_FindFreeBlock
688 *
689 * Find a free block at least as large as the requested size, and make sure
690 * the requested size is committed.
691 */
692 static ARENA_FREE *HEAP_FindFreeBlock( HEAP *heap, SIZE_T size,
693 SUBHEAP **ppSubHeap )
694 {
695 SUBHEAP *subheap;
696 struct list *ptr;
697 FREE_LIST_ENTRY *pEntry = heap->freeList;
698
699 /* Find a suitable free list, and in it find a block large enough */
700
701 while (pEntry->size < size) pEntry++;
702 ptr = &pEntry->arena.entry;
703 while ((ptr = list_next( &heap->freeList[0].arena.entry, ptr )))
704 {
705 ARENA_FREE *pArena = LIST_ENTRY( ptr, ARENA_FREE, entry );
706 SIZE_T arena_size = (pArena->size & ARENA_SIZE_MASK) +
707 sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
708 if (arena_size >= size)
709 {
710 subheap = HEAP_FindSubHeap( heap, pArena );
711 if (!HEAP_Commit( subheap, (char *)pArena + sizeof(ARENA_INUSE)
712 + size + HEAP_MIN_BLOCK_SIZE))
713 return NULL;
714 *ppSubHeap = subheap;
715 return pArena;
716 }
717 }
718
719 /* If no block was found, attempt to grow the heap */
720
721 if (!(heap->flags & HEAP_GROWABLE))
722 {
723 WARN("Not enough space in heap %p for %08lx bytes\n", heap, size );
724 return NULL;
725 }
726 /* make sure that we have a big enough size *committed* to fit another
727 * last free arena in !
728 * So just one heap struct, one first free arena which will eventually
729 * get inuse, and HEAP_MIN_BLOCK_SIZE for the second free arena that
730 * might get assigned all remaining free space in HEAP_ShrinkBlock() */
731 size += ROUND_SIZE(sizeof(SUBHEAP)) + sizeof(ARENA_INUSE) + HEAP_MIN_BLOCK_SIZE;
732 if (!(subheap = HEAP_CreateSubHeap( heap, NULL, heap->flags, size,
733 max( HEAP_DEF_SIZE, size ) )))
734 return NULL;
735
736 TRACE("created new sub-heap %p of %08lx bytes for heap %p\n",
737 subheap, size, heap );
738
739 *ppSubHeap = subheap;
740 return (ARENA_FREE *)(subheap + 1);
741 }
742
743
744 /***********************************************************************
745 * HEAP_IsValidArenaPtr
746 *
747 * Check that the pointer is inside the range possible for arenas.
748 */
749 static BOOL HEAP_IsValidArenaPtr( const HEAP *heap, const void *ptr )
750 {
751 int i;
752 const SUBHEAP *subheap = HEAP_FindSubHeap( heap, ptr );
753 if (!subheap) return FALSE;
754 if ((const char *)ptr >= (const char *)subheap + subheap->headerSize) return TRUE;
755 if (subheap != &heap->subheap) return FALSE;
756 for (i = 0; i < HEAP_NB_FREE_LISTS; i++)
757 if (ptr == (const void *)&heap->freeList[i].arena) return TRUE;
758 return FALSE;
759 }
760
761
762 /***********************************************************************
763 * HEAP_ValidateFreeArena
764 */
765 static BOOL HEAP_ValidateFreeArena( SUBHEAP *subheap, ARENA_FREE *pArena )
766 {
767 ARENA_FREE *prev, *next;
768 char *heapEnd = (char *)subheap + subheap->size;
769
770 /* Check for unaligned pointers */
771 if ( (ULONG_PTR)pArena % ALIGNMENT != 0 )
772 {
773 ERR("Heap %p: unaligned arena pointer %p\n", subheap->heap, pArena );
774 return FALSE;
775 }
776
777 /* Check magic number */
778 if (pArena->magic != ARENA_FREE_MAGIC)
779 {
780 ERR("Heap %p: invalid free arena magic for %p\n", subheap->heap, pArena );
781 return FALSE;
782 }
783 /* Check size flags */
784 if (!(pArena->size & ARENA_FLAG_FREE) ||
785 (pArena->size & ARENA_FLAG_PREV_FREE))
786 {
787 ERR("Heap %p: bad flags %08lx for free arena %p\n",
788 subheap->heap, pArena->size & ~ARENA_SIZE_MASK, pArena );
789 return FALSE;
790 }
791 /* Check arena size */
792 if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
793 {
794 ERR("Heap %p: bad size %08lx for free arena %p\n",
795 subheap->heap, pArena->size & ARENA_SIZE_MASK, pArena );
796 return FALSE;
797 }
798 /* Check that next pointer is valid */
799 next = LIST_ENTRY( pArena->entry.next, ARENA_FREE, entry );
800 if (!HEAP_IsValidArenaPtr( subheap->heap, next ))
801 {
802 ERR("Heap %p: bad next ptr %p for arena %p\n",
803 subheap->heap, next, pArena );
804 return FALSE;
805 }
806 /* Check that next arena is free */
807 if (!(next->size & ARENA_FLAG_FREE) || (next->magic != ARENA_FREE_MAGIC))
808 {
809 ERR("Heap %p: next arena %p invalid for %p\n",
810 subheap->heap, next, pArena );
811 return FALSE;
812 }
813 /* Check that prev pointer is valid */
814 prev = LIST_ENTRY( pArena->entry.prev, ARENA_FREE, entry );
815 if (!HEAP_IsValidArenaPtr( subheap->heap, prev ))
816 {
817 ERR("Heap %p: bad prev ptr %p for arena %p\n",
818 subheap->heap, prev, pArena );
819 return FALSE;
820 }
821 /* Check that prev arena is free */
822 if (!(prev->size & ARENA_FLAG_FREE) || (prev->magic != ARENA_FREE_MAGIC))
823 {
824 /* this often means that the prev arena got overwritten
825 * by a memory write before that prev arena */
826 ERR("Heap %p: prev arena %p invalid for %p\n",
827 subheap->heap, prev, pArena );
828 return FALSE;
829 }
830 /* Check that next block has PREV_FREE flag */
831 if ((char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd)
832 {
833 if (!(*(DWORD *)((char *)(pArena + 1) +
834 (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
835 {
836 ERR("Heap %p: free arena %p next block has no PREV_FREE flag\n",
837 subheap->heap, pArena );
838 return FALSE;
839 }
840 /* Check next block back pointer */
841 if (*((ARENA_FREE **)((char *)(pArena + 1) +
842 (pArena->size & ARENA_SIZE_MASK)) - 1) != pArena)
843 {
844 ERR("Heap %p: arena %p has wrong back ptr %08lx\n",
845 subheap->heap, pArena,
846 *((DWORD *)((char *)(pArena+1) + (pArena->size & ARENA_SIZE_MASK)) - 1));
847 return FALSE;
848 }
849 }
850 return TRUE;
851 }
852
853
854 /***********************************************************************
855 * HEAP_ValidateInUseArena
856 */
857 static BOOL HEAP_ValidateInUseArena( const SUBHEAP *subheap, const ARENA_INUSE *pArena, BOOL quiet )
858 {
859 const char *heapEnd = (const char *)subheap + subheap->size;
860
861 /* Check for unaligned pointers */
862 if ( (ULONG_PTR)pArena % ALIGNMENT != 0 )
863 {
864 if ( quiet == NOISY )
865 {
866 ERR( "Heap %p: unaligned arena pointer %p\n", subheap->heap, pArena );
867 if ( TRACE_ON(heap) )
868 HEAP_Dump( subheap->heap );
869 }
870 else if ( WARN_ON(heap) )
871 {
872 WARN( "Heap %p: unaligned arena pointer %p\n", subheap->heap, pArena );
873 if ( TRACE_ON(heap) )
874 HEAP_Dump( subheap->heap );
875 }
876 return FALSE;
877 }
878
879 /* Check magic number */
880 if (pArena->magic != ARENA_INUSE_MAGIC)
881 {
882 if (quiet == NOISY) {
883 ERR("Heap %p: invalid in-use arena magic for %p\n", subheap->heap, pArena );
884 if (TRACE_ON(heap))
885 HEAP_Dump( subheap->heap );
886 } else if (WARN_ON(heap)) {
887 WARN("Heap %p: invalid in-use arena magic for %p\n", subheap->heap, pArena );
888 if (TRACE_ON(heap))
889 HEAP_Dump( subheap->heap );
890 }
891 return FALSE;
892 }
893 /* Check size flags */
894 if (pArena->size & ARENA_FLAG_FREE)
895 {
896 ERR("Heap %p: bad flags %08lx for in-use arena %p\n",
897 subheap->heap, pArena->size & ~ARENA_SIZE_MASK, pArena );
898 return FALSE;
899 }
900 /* Check arena size */
901 if ((const char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) > heapEnd)
902 {
903 ERR("Heap %p: bad size %08lx for in-use arena %p\n",
904 subheap->heap, pArena->size & ARENA_SIZE_MASK, pArena );
905 return FALSE;
906 }
907 /* Check next arena PREV_FREE flag */
908 if (((const char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK) < heapEnd) &&
909 (*(const DWORD *)((const char *)(pArena + 1) + (pArena->size & ARENA_SIZE_MASK)) & ARENA_FLAG_PREV_FREE))
910 {
911 ERR("Heap %p: in-use arena %p next block has PREV_FREE flag\n",
912 subheap->heap, pArena );
913 return FALSE;
914 }
915 /* Check prev free arena */
916 if (pArena->size & ARENA_FLAG_PREV_FREE)
917 {
918 const ARENA_FREE *pPrev = *((const ARENA_FREE * const*)pArena - 1);
919 /* Check prev pointer */
920 if (!HEAP_IsValidArenaPtr( subheap->heap, pPrev ))
921 {
922 ERR("Heap %p: bad back ptr %p for arena %p\n",
923 subheap->heap, pPrev, pArena );
924 return FALSE;
925 }
926 /* Check that prev arena is free */
927 if (!(pPrev->size & ARENA_FLAG_FREE) ||
928 (pPrev->magic != ARENA_FREE_MAGIC))
929 {
930 ERR("Heap %p: prev arena %p invalid for in-use %p\n",
931 subheap->heap, pPrev, pArena );
932 return FALSE;
933 }
934 /* Check that prev arena is really the previous block */
935 if ((const char *)(pPrev + 1) + (pPrev->size & ARENA_SIZE_MASK) != (const char *)pArena)
936 {
937 ERR("Heap %p: prev arena %p is not prev for in-use %p\n",
938 subheap->heap, pPrev, pArena );
939 return FALSE;
940 }
941 }
942 return TRUE;
943 }
944
945
946 /***********************************************************************
947 * HEAP_IsRealArena [Internal]
948 * Validates a block is a valid arena.
949 *
950 * RETURNS
951 * TRUE: Success
952 * FALSE: Failure
953 */
954 static BOOL HEAP_IsRealArena( HEAP *heapPtr, /* [in] ptr to the heap */
955 DWORD flags, /* [in] Bit flags that control access during operation */
956 LPCVOID block, /* [in] Optional pointer to memory block to validate */
957 BOOL quiet ) /* [in] Flag - if true, HEAP_ValidateInUseArena
958 * does not complain */
959 {
960 SUBHEAP *subheap;
961 BOOL ret = TRUE;
962
963 if (!heapPtr || (heapPtr->magic != HEAP_MAGIC))
964 {
965 ERR("Invalid heap %p!\n", heapPtr );
966 return FALSE;
967 }
968
969 flags &= HEAP_NO_SERIALIZE;
970 flags |= heapPtr->flags;
971 /* calling HeapLock may result in infinite recursion, so do the critsect directly */
972 if (!(flags & HEAP_NO_SERIALIZE))
973 RtlEnterCriticalSection( &heapPtr->critSection );
974
975 if (block)
976 {
977 /* Only check this single memory block */
978
979 if (!(subheap = HEAP_FindSubHeap( heapPtr, block )) ||
980 ((const char *)block < (char *)subheap + subheap->headerSize
981 + sizeof(ARENA_INUSE)))
982 {
983 if (quiet == NOISY)
984 ERR("Heap %p: block %p is not inside heap\n", heapPtr, block );
985 else if (WARN_ON(heap))
986 WARN("Heap %p: block %p is not inside heap\n", heapPtr, block );
987 ret = FALSE;
988 } else
989 ret = HEAP_ValidateInUseArena( subheap, (const ARENA_INUSE *)block - 1, quiet );
990
991 if (!(flags & HEAP_NO_SERIALIZE))
992 RtlLeaveCriticalSection( &heapPtr->critSection );
993 return ret;
994 }
995
996 subheap = &heapPtr->subheap;
997 while (subheap && ret)
998 {
999 char *ptr = (char *)subheap + subheap->headerSize;
1000 while (ptr < (char *)subheap + subheap->size)
1001 {
1002 if (*(DWORD *)ptr & ARENA_FLAG_FREE)
1003 {
1004 if (!HEAP_ValidateFreeArena( subheap, (ARENA_FREE *)ptr )) {
1005 ret = FALSE;
1006 break;
1007 }
1008 ptr += sizeof(ARENA_FREE) + (*(DWORD *)ptr & ARENA_SIZE_MASK);
1009 }
1010 else
1011 {
1012 if (!HEAP_ValidateInUseArena( subheap, (ARENA_INUSE *)ptr, NOISY )) {
1013 ret = FALSE;
1014 break;
1015 }
1016 ptr += sizeof(ARENA_INUSE) + (*(DWORD *)ptr & ARENA_SIZE_MASK);
1017 }
1018 }
1019 subheap = subheap->next;
1020 }
1021
1022 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1023 return ret;
1024 }
1025
1026
1027 /***********************************************************************
1028 * RtlCreateHeap (NTDLL.@)
1029 *
1030 * Create a new Heap.
1031 *
1032 * PARAMS
1033 * flags [I] HEAP_ flags from "winnt.h"
1034 * addr [I] Desired base address
1035 * totalSize [I] Total size of the heap, or 0 for a growable heap
1036 * commitSize [I] Amount of heap space to commit
1037 * unknown [I] Not yet understood
1038 * definition [I] Heap definition
1039 *
1040 * RETURNS
1041 * Success: A HANDLE to the newly created heap.
1042 * Failure: a NULL HANDLE.
1043 */
1044 HANDLE WINAPI RtlCreateHeap( ULONG flags, PVOID addr, SIZE_T totalSize, SIZE_T commitSize,
1045 PVOID unknown, PRTL_HEAP_DEFINITION definition )
1046 {
1047 SUBHEAP *subheap;
1048
1049 /* Allocate the heap block */
1050
1051 if (!totalSize)
1052 {
1053 totalSize = HEAP_DEF_SIZE;
1054 flags |= HEAP_GROWABLE;
1055 }
1056
1057 if (!(subheap = HEAP_CreateSubHeap( NULL, addr, flags, commitSize, totalSize ))) return 0;
1058
1059 /* link it into the per-process heap list */
1060 if (processHeap)
1061 {
1062 HEAP *heapPtr = subheap->heap;
1063 RtlLockHeap( processHeap );
1064 heapPtr->next = firstHeap;
1065 firstHeap = heapPtr;
1066 RtlUnlockHeap( processHeap );
1067 }
1068 else processHeap = subheap->heap; /* assume the first heap we create is the process main heap */
1069
1070 return (HANDLE)subheap;
1071 }
1072
1073
1074 /***********************************************************************
1075 * RtlDestroyHeap (NTDLL.@)
1076 *
1077 * Destroy a Heap created with RtlCreateHeap().
1078 *
1079 * PARAMS
1080 * heap [I] Heap to destroy.
1081 *
1082 * RETURNS
1083 * Success: A NULL HANDLE, if heap is NULL or it was destroyed
1084 * Failure: The Heap handle, if heap is the process heap.
1085 */
1086 HANDLE WINAPI RtlDestroyHeap( HANDLE heap )
1087 {
1088 HEAP *heapPtr = HEAP_GetPtr( heap );
1089 SUBHEAP *subheap;
1090
1091 TRACE("%p\n", heap );
1092 if (!heapPtr) return heap;
1093
1094 if (heap == processHeap) return heap; /* cannot delete the main process heap */
1095 else /* remove it from the per-process list */
1096 {
1097 HEAP **pptr;
1098 RtlLockHeap( processHeap );
1099 pptr = &firstHeap;
1100 while (*pptr && *pptr != heapPtr) pptr = &(*pptr)->next;
1101 if (*pptr) *pptr = (*pptr)->next;
1102 RtlUnlockHeap( processHeap );
1103 }
1104
1105 RtlDeleteCriticalSection( &heapPtr->critSection );
1106 subheap = &heapPtr->subheap;
1107 while (subheap)
1108 {
1109 SUBHEAP *next = subheap->next;
1110 SIZE_T size = 0;
1111 void *addr = subheap;
1112 NtFreeVirtualMemory( NtCurrentProcess(), &addr, &size, MEM_RELEASE );
1113 subheap = next;
1114 }
1115 return 0;
1116 }
1117
1118
1119 /***********************************************************************
1120 * RtlAllocateHeap (NTDLL.@)
1121 *
1122 * Allocate a memory block from a Heap.
1123 *
1124 * PARAMS
1125 * heap [I] Heap to allocate block from
1126 * flags [I] HEAP_ flags from "winnt.h"
1127 * size [I] Size of the memory block to allocate
1128 *
1129 * RETURNS
1130 * Success: A pointer to the newly allocated block
1131 * Failure: NULL.
1132 *
1133 * NOTES
1134 * This call does not SetLastError().
1135 */
1136 PVOID WINAPI RtlAllocateHeap( HANDLE heap, ULONG flags, SIZE_T size )
1137 {
1138 ARENA_FREE *pArena;
1139 ARENA_INUSE *pInUse;
1140 SUBHEAP *subheap;
1141 HEAP *heapPtr = HEAP_GetPtr( heap );
1142 SIZE_T rounded_size;
1143
1144 /* Validate the parameters */
1145
1146 if (!heapPtr) return NULL;
1147 flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY;
1148 flags |= heapPtr->flags;
1149 rounded_size = ROUND_SIZE(size);
1150 if (rounded_size < HEAP_MIN_BLOCK_SIZE) rounded_size = HEAP_MIN_BLOCK_SIZE;
1151
1152 if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterCriticalSection( &heapPtr->critSection );
1153 /* Locate a suitable free block */
1154
1155 if (!(pArena = HEAP_FindFreeBlock( heapPtr, rounded_size, &subheap )))
1156 {
1157 TRACE("(%p,%08lx,%08lx): returning NULL\n",
1158 heap, flags, size );
1159 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1160 if (flags & HEAP_GENERATE_EXCEPTIONS) RtlRaiseStatus( STATUS_NO_MEMORY );
1161 return NULL;
1162 }
1163
1164 /* Remove the arena from the free list */
1165
1166 list_remove( &pArena->entry );
1167
1168 /* Build the in-use arena */
1169
1170 pInUse = (ARENA_INUSE *)pArena;
1171
1172 /* in-use arena is smaller than free arena,
1173 * so we have to add the difference to the size */
1174 pInUse->size = (pInUse->size & ~ARENA_FLAG_FREE) + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
1175 pInUse->magic = ARENA_INUSE_MAGIC;
1176
1177 /* Shrink the block */
1178
1179 HEAP_ShrinkBlock( subheap, pInUse, rounded_size );
1180 pInUse->unused_bytes = (pInUse->size & ARENA_SIZE_MASK) - size;
1181
1182 if (flags & HEAP_ZERO_MEMORY)
1183 clear_block( pInUse + 1, pInUse->size & ARENA_SIZE_MASK );
1184 else
1185 mark_block_uninitialized( pInUse + 1, pInUse->size & ARENA_SIZE_MASK );
1186
1187 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1188
1189 TRACE("(%p,%08lx,%08lx): returning %p\n", heap, flags, size, pInUse + 1 );
1190 return (LPVOID)(pInUse + 1);
1191 }
1192
1193
1194 /***********************************************************************
1195 * RtlFreeHeap (NTDLL.@)
1196 *
1197 * Free a memory block allocated with RtlAllocateHeap().
1198 *
1199 * PARAMS
1200 * heap [I] Heap that block was allocated from
1201 * flags [I] HEAP_ flags from "winnt.h"
1202 * ptr [I] Block to free
1203 *
1204 * RETURNS
1205 * Success: TRUE, if ptr is NULL or was freed successfully.
1206 * Failure: FALSE.
1207 */
1208 BOOLEAN WINAPI RtlFreeHeap( HANDLE heap, ULONG flags, PVOID ptr )
1209 {
1210 ARENA_INUSE *pInUse;
1211 SUBHEAP *subheap;
1212 HEAP *heapPtr;
1213
1214 /* Validate the parameters */
1215
1216 if (!ptr) return TRUE; /* freeing a NULL ptr isn't an error in Win2k */
1217
1218 heapPtr = HEAP_GetPtr( heap );
1219 if (!heapPtr)
1220 {
1221 RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1222 return FALSE;
1223 }
1224
1225 flags &= HEAP_NO_SERIALIZE;
1226 flags |= heapPtr->flags;
1227 if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterCriticalSection( &heapPtr->critSection );
1228 if (!HEAP_IsRealArena( heapPtr, HEAP_NO_SERIALIZE, ptr, QUIET ))
1229 {
1230 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1231 RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_PARAMETER );
1232 TRACE("(%p,%08lx,%p): returning FALSE\n", heap, flags, ptr );
1233 return FALSE;
1234 }
1235
1236 /* Turn the block into a free block */
1237
1238 pInUse = (ARENA_INUSE *)ptr - 1;
1239 subheap = HEAP_FindSubHeap( heapPtr, pInUse );
1240 HEAP_MakeInUseBlockFree( subheap, pInUse );
1241
1242 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1243
1244 TRACE("(%p,%08lx,%p): returning TRUE\n", heap, flags, ptr );
1245 return TRUE;
1246 }
1247
1248
1249 /***********************************************************************
1250 * RtlReAllocateHeap (NTDLL.@)
1251 *
1252 * Change the size of a memory block allocated with RtlAllocateHeap().
1253 *
1254 * PARAMS
1255 * heap [I] Heap that block was allocated from
1256 * flags [I] HEAP_ flags from "winnt.h"
1257 * ptr [I] Block to resize
1258 * size [I] Size of the memory block to allocate
1259 *
1260 * RETURNS
1261 * Success: A pointer to the resized block (which may be different).
1262 * Failure: NULL.
1263 */
1264 PVOID WINAPI RtlReAllocateHeap( HANDLE heap, ULONG flags, PVOID ptr, SIZE_T size )
1265 {
1266 ARENA_INUSE *pArena;
1267 HEAP *heapPtr;
1268 SUBHEAP *subheap;
1269 SIZE_T oldSize, rounded_size;
1270
1271 if (!ptr) return NULL;
1272 if (!(heapPtr = HEAP_GetPtr( heap )))
1273 {
1274 RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1275 return NULL;
1276 }
1277
1278 /* Validate the parameters */
1279
1280 flags &= HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_ZERO_MEMORY |
1281 HEAP_REALLOC_IN_PLACE_ONLY;
1282 flags |= heapPtr->flags;
1283 rounded_size = ROUND_SIZE(size);
1284 if (rounded_size < HEAP_MIN_BLOCK_SIZE) rounded_size = HEAP_MIN_BLOCK_SIZE;
1285
1286 if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterCriticalSection( &heapPtr->critSection );
1287 if (!HEAP_IsRealArena( heapPtr, HEAP_NO_SERIALIZE, ptr, QUIET ))
1288 {
1289 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1290 RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_PARAMETER );
1291 TRACE("(%p,%08lx,%p,%08lx): returning NULL\n", heap, flags, ptr, size );
1292 return NULL;
1293 }
1294
1295 /* Check if we need to grow the block */
1296
1297 pArena = (ARENA_INUSE *)ptr - 1;
1298 subheap = HEAP_FindSubHeap( heapPtr, pArena );
1299 oldSize = (pArena->size & ARENA_SIZE_MASK);
1300 if (rounded_size > oldSize)
1301 {
1302 char *pNext = (char *)(pArena + 1) + oldSize;
1303 if ((pNext < (char *)subheap + subheap->size) &&
1304 (*(DWORD *)pNext & ARENA_FLAG_FREE) &&
1305 (oldSize + (*(DWORD *)pNext & ARENA_SIZE_MASK) + sizeof(ARENA_FREE) >= rounded_size))
1306 {
1307 /* The next block is free and large enough */
1308 ARENA_FREE *pFree = (ARENA_FREE *)pNext;
1309 list_remove( &pFree->entry );
1310 pArena->size += (pFree->size & ARENA_SIZE_MASK) + sizeof(*pFree);
1311 if (!HEAP_Commit( subheap, (char *)pArena + sizeof(ARENA_INUSE)
1312 + rounded_size + HEAP_MIN_BLOCK_SIZE))
1313 {
1314 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1315 if (flags & HEAP_GENERATE_EXCEPTIONS) RtlRaiseStatus( STATUS_NO_MEMORY );
1316 RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_NO_MEMORY );
1317 return NULL;
1318 }
1319 HEAP_ShrinkBlock( subheap, pArena, rounded_size );
1320 }
1321 else /* Do it the hard way */
1322 {
1323 ARENA_FREE *pNew;
1324 ARENA_INUSE *pInUse;
1325 SUBHEAP *newsubheap;
1326
1327 if ((flags & HEAP_REALLOC_IN_PLACE_ONLY) ||
1328 !(pNew = HEAP_FindFreeBlock( heapPtr, rounded_size, &newsubheap )))
1329 {
1330 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1331 if (flags & HEAP_GENERATE_EXCEPTIONS) RtlRaiseStatus( STATUS_NO_MEMORY );
1332 RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_NO_MEMORY );
1333 return NULL;
1334 }
1335
1336 /* Build the in-use arena */
1337
1338 list_remove( &pNew->entry );
1339 pInUse = (ARENA_INUSE *)pNew;
1340 pInUse->size = (pInUse->size & ~ARENA_FLAG_FREE)
1341 + sizeof(ARENA_FREE) - sizeof(ARENA_INUSE);
1342 pInUse->magic = ARENA_INUSE_MAGIC;
1343 HEAP_ShrinkBlock( newsubheap, pInUse, rounded_size );
1344 mark_block_initialized( pInUse + 1, oldSize );
1345 memcpy( pInUse + 1, pArena + 1, oldSize );
1346
1347 /* Free the previous block */
1348
1349 HEAP_MakeInUseBlockFree( subheap, pArena );
1350 subheap = newsubheap;
1351 pArena = pInUse;
1352 }
1353 }
1354 else HEAP_ShrinkBlock( subheap, pArena, rounded_size ); /* Shrink the block */
1355
1356 pArena->unused_bytes = (pArena->size & ARENA_SIZE_MASK) - size;
1357
1358 /* Clear the extra bytes if needed */
1359
1360 if (rounded_size > oldSize)
1361 {
1362 if (flags & HEAP_ZERO_MEMORY)
1363 clear_block( (char *)(pArena + 1) + oldSize,
1364 (pArena->size & ARENA_SIZE_MASK) - oldSize );
1365 else
1366 mark_block_uninitialized( (char *)(pArena + 1) + oldSize,
1367 (pArena->size & ARENA_SIZE_MASK) - oldSize );
1368 }
1369
1370 /* Return the new arena */
1371
1372 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1373
1374 TRACE("(%p,%08lx,%p,%08lx): returning %p\n", heap, flags, ptr, size, pArena + 1 );
1375 return (LPVOID)(pArena + 1);
1376 }
1377
1378
1379 /***********************************************************************
1380 * RtlCompactHeap (NTDLL.@)
1381 *
1382 * Compact the free space in a Heap.
1383 *
1384 * PARAMS
1385 * heap [I] Heap that block was allocated from
1386 * flags [I] HEAP_ flags from "winnt.h"
1387 *
1388 * RETURNS
1389 * The number of bytes compacted.
1390 *
1391 * NOTES
1392 * This function is a harmless stub.
1393 */
1394 ULONG WINAPI RtlCompactHeap( HANDLE heap, ULONG flags )
1395 {
1396 FIXME( "stub\n" );
1397 return 0;
1398 }
1399
1400
1401 /***********************************************************************
1402 * RtlLockHeap (NTDLL.@)
1403 *
1404 * Lock a Heap.
1405 *
1406 * PARAMS
1407 * heap [I] Heap to lock
1408 *
1409 * RETURNS
1410 * Success: TRUE. The Heap is locked.
1411 * Failure: FALSE, if heap is invalid.
1412 */
1413 BOOLEAN WINAPI RtlLockHeap( HANDLE heap )
1414 {
1415 HEAP *heapPtr = HEAP_GetPtr( heap );
1416 if (!heapPtr) return FALSE;
1417 RtlEnterCriticalSection( &heapPtr->critSection );
1418 return TRUE;
1419 }
1420
1421
1422 /***********************************************************************
1423 * RtlUnlockHeap (NTDLL.@)
1424 *
1425 * Unlock a Heap.
1426 *
1427 * PARAMS
1428 * heap [I] Heap to unlock
1429 *
1430 * RETURNS
1431 * Success: TRUE. The Heap is unlocked.
1432 * Failure: FALSE, if heap is invalid.
1433 */
1434 BOOLEAN WINAPI RtlUnlockHeap( HANDLE heap )
1435 {
1436 HEAP *heapPtr = HEAP_GetPtr( heap );
1437 if (!heapPtr) return FALSE;
1438 RtlLeaveCriticalSection( &heapPtr->critSection );
1439 return TRUE;
1440 }
1441
1442
1443 /***********************************************************************
1444 * RtlSizeHeap (NTDLL.@)
1445 *
1446 * Get the actual size of a memory block allocated from a Heap.
1447 *
1448 * PARAMS
1449 * heap [I] Heap that block was allocated from
1450 * flags [I] HEAP_ flags from "winnt.h"
1451 * ptr [I] Block to get the size of
1452 *
1453 * RETURNS
1454 * Success: The size of the block.
1455 * Failure: -1, heap or ptr are invalid.
1456 *
1457 * NOTES
1458 * The size may be bigger than what was passed to RtlAllocateHeap().
1459 */
1460 SIZE_T WINAPI RtlSizeHeap( HANDLE heap, ULONG flags, PVOID ptr )
1461 {
1462 SIZE_T ret;
1463 HEAP *heapPtr = HEAP_GetPtr( heap );
1464
1465 if (!heapPtr)
1466 {
1467 RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_HANDLE );
1468 return ~0UL;
1469 }
1470 flags &= HEAP_NO_SERIALIZE;
1471 flags |= heapPtr->flags;
1472 if (!(flags & HEAP_NO_SERIALIZE)) RtlEnterCriticalSection( &heapPtr->critSection );
1473 if (!HEAP_IsRealArena( heapPtr, HEAP_NO_SERIALIZE, ptr, QUIET ))
1474 {
1475 RtlSetLastWin32ErrorAndNtStatusFromNtStatus( STATUS_INVALID_PARAMETER );
1476 ret = ~0UL;
1477 }
1478 else
1479 {
1480 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr - 1;
1481 ret = (pArena->size & ARENA_SIZE_MASK) - pArena->unused_bytes;
1482 }
1483 if (!(flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1484
1485 TRACE("(%p,%08lx,%p): returning %08lx\n", heap, flags, ptr, ret );
1486 return ret;
1487 }
1488
1489
1490 /***********************************************************************
1491 * RtlValidateHeap (NTDLL.@)
1492 *
1493 * Determine if a block is a valid allocation from a heap.
1494 *
1495 * PARAMS
1496 * heap [I] Heap that block was allocated from
1497 * flags [I] HEAP_ flags from "winnt.h"
1498 * ptr [I] Block to check
1499 *
1500 * RETURNS
1501 * Success: TRUE. The block was allocated from heap.
1502 * Failure: FALSE, if heap is invalid or ptr was not allocated from it.
1503 */
1504 BOOLEAN WINAPI RtlValidateHeap( HANDLE heap, ULONG flags, LPCVOID ptr )
1505 {
1506 HEAP *heapPtr = HEAP_GetPtr( heap );
1507 if (!heapPtr) return FALSE;
1508 return HEAP_IsRealArena( heapPtr, flags, ptr, QUIET );
1509 }
1510
1511
1512 /***********************************************************************
1513 * RtlWalkHeap (NTDLL.@)
1514 *
1515 * FIXME
1516 * The PROCESS_HEAP_ENTRY flag values seem different between this
1517 * function and HeapWalk(). To be checked.
1518 */
1519 NTSTATUS WINAPI RtlWalkHeap( HANDLE heap, PVOID entry_ptr )
1520 {
1521 LPPROCESS_HEAP_ENTRY entry = entry_ptr; /* FIXME */
1522 HEAP *heapPtr = HEAP_GetPtr(heap);
1523 SUBHEAP *sub, *currentheap = NULL;
1524 NTSTATUS ret;
1525 char *ptr;
1526 int region_index = 0;
1527
1528 if (!heapPtr || !entry) return STATUS_INVALID_PARAMETER;
1529
1530 if (!(heapPtr->flags & HEAP_NO_SERIALIZE)) RtlEnterCriticalSection( &heapPtr->critSection );
1531
1532 /* set ptr to the next arena to be examined */
1533
1534 if (!entry->lpData) /* first call (init) ? */
1535 {
1536 TRACE("begin walking of heap %p.\n", heap);
1537 currentheap = &heapPtr->subheap;
1538 ptr = (char*)currentheap + currentheap->headerSize;
1539 }
1540 else
1541 {
1542 ptr = entry->lpData;
1543 sub = &heapPtr->subheap;
1544 while (sub)
1545 {
1546 if (((char *)ptr >= (char *)sub) &&
1547 ((char *)ptr < (char *)sub + sub->size))
1548 {
1549 currentheap = sub;
1550 break;
1551 }
1552 sub = sub->next;
1553 region_index++;
1554 }
1555 if (currentheap == NULL)
1556 {
1557 ERR("no matching subheap found, shouldn't happen !\n");
1558 ret = STATUS_NO_MORE_ENTRIES;
1559 goto HW_end;
1560 }
1561
1562 ptr += entry->cbData; /* point to next arena */
1563 if (ptr > (char *)currentheap + currentheap->size - 1)
1564 { /* proceed with next subheap */
1565 if (!(currentheap = currentheap->next))
1566 { /* successfully finished */
1567 TRACE("end reached.\n");
1568 ret = STATUS_NO_MORE_ENTRIES;
1569 goto HW_end;
1570 }
1571 ptr = (char*)currentheap + currentheap->headerSize;
1572 }
1573 }
1574
1575 entry->wFlags = 0;
1576 if (*(DWORD *)ptr & ARENA_FLAG_FREE)
1577 {
1578 ARENA_FREE *pArena = (ARENA_FREE *)ptr;
1579
1580 /*TRACE("free, magic: %04x\n", pArena->magic);*/
1581
1582 entry->lpData = pArena + 1;
1583 entry->cbData = pArena->size & ARENA_SIZE_MASK;
1584 entry->cbOverhead = sizeof(ARENA_FREE);
1585 entry->wFlags = PROCESS_HEAP_UNCOMMITTED_RANGE;
1586 }
1587 else
1588 {
1589 ARENA_INUSE *pArena = (ARENA_INUSE *)ptr;
1590
1591 /*TRACE("busy, magic: %04x\n", pArena->magic);*/
1592
1593 entry->lpData = pArena + 1;
1594 entry->cbData = pArena->size & ARENA_SIZE_MASK;
1595 entry->cbOverhead = sizeof(ARENA_INUSE);
1596 entry->wFlags = PROCESS_HEAP_ENTRY_BUSY;
1597 /* FIXME: can't handle PROCESS_HEAP_ENTRY_MOVEABLE
1598 and PROCESS_HEAP_ENTRY_DDESHARE yet */
1599 }
1600
1601 entry->iRegionIndex = region_index;
1602
1603 /* first element of heap ? */
1604 if (ptr == (char *)(currentheap + currentheap->headerSize))
1605 {
1606 entry->wFlags |= PROCESS_HEAP_REGION;
1607 entry->u.Region.dwCommittedSize = currentheap->commitSize;
1608 entry->u.Region.dwUnCommittedSize =
1609 currentheap->size - currentheap->commitSize;
1610 entry->u.Region.lpFirstBlock = /* first valid block */
1611 currentheap + currentheap->headerSize;
1612 entry->u.Region.lpLastBlock = /* first invalid block */
1613 currentheap + currentheap->size;
1614 }
1615 ret = STATUS_SUCCESS;
1616 if (TRACE_ON(heap)) HEAP_DumpEntry(entry);
1617
1618 HW_end:
1619 if (!(heapPtr->flags & HEAP_NO_SERIALIZE)) RtlLeaveCriticalSection( &heapPtr->critSection );
1620 return ret;
1621 }
1622
1623
1624 /***********************************************************************
1625 * RtlGetProcessHeaps (NTDLL.@)
1626 *
1627 * Get the Heaps belonging to the current process.
1628 *
1629 * PARAMS
1630 * count [I] size of heaps
1631 * heaps [O] Destination array for heap HANDLE's
1632 *
1633 * RETURNS
1634 * Success: The number of Heaps allocated by the process.
1635 * Failure: 0.
1636 */
1637 ULONG WINAPI RtlGetProcessHeaps( ULONG count, HANDLE *heaps )
1638 {
1639 ULONG total;
1640 HEAP *ptr;
1641
1642 if (!processHeap) return 0; /* should never happen */
1643 total = 1; /* main heap */
1644 RtlLockHeap( processHeap );
1645 for (ptr = firstHeap; ptr; ptr = ptr->next) total++;
1646 if (total <= count)
1647 {
1648 *heaps++ = (HANDLE)processHeap;
1649 for (ptr = firstHeap; ptr; ptr = ptr->next) *heaps++ = (HANDLE)ptr;
1650 }
1651 RtlUnlockHeap( processHeap );
1652 return total;
1653 }
Windows API implementation