projects / reactos.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Initial revision
[reactos.git] / reactos / lib / kernel32 / mem / heap.c
1 /*
2 * kernel/heap.c
3 * Copyright (C) 1996, Onno Hovers, All rights reserved
4 *
5 * This software is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public License as
7 * published by the Free Software Foundation; either version 2 of the
8 * License, or (at your option) any later version.
9 *
10 * This software is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public
16 * License along with this software; see the file COPYING.LIB. If
17 * not, write to the Free Software Foundation, Inc., 675 Mass Ave,
18 * Cambridge, MA 02139, USA.
19 *
20 * Win32 heap functions (HeapXXX).
21 *
22 */
23
24 /*
25 * Adapted for the ReactOS system libraries by David Welch (welch@mcmail.com)
26 * Put the type definitions of the heap in a seperate header. Boudewijn Dekker
27 */
28
29 #include <kernel32/heap.h>
30
31 static HEAP_BUCKET __HeapDefaultBuckets[]=
32 {
33 { NULL, 16, 18, 504 },
34 { NULL, 24, 30, 1016 },
35 { NULL, 32, 24, 1016 },
36 { NULL, 48, 17, 1016 },
37 { NULL, 64, 27, 2040 },
38 { NULL, 96, 19, 2040 },
39 { NULL, 128, 29, 4088 },
40 { NULL, 256, 15, 4088 },
41 };
42
43
44 static BOOL __HeapCommit(PHEAP pheap, LPVOID start, LPVOID end);
45 static BOOL __HeapDecommit(PHEAP pheap, LPVOID start, LPVOID end);
46 static LPVOID __HeapAlloc(PHEAP pheap, ULONG flags, ULONG size, ULONG tag);
47 static VOID __HeapFreeRest(PHEAP pheap, PHEAP_BLOCK pfree, ULONG allocsize,
48 ULONG newsize);
49 static LPVOID __HeapReAlloc(PHEAP pheap, ULONG flags, LPVOID pold, ULONG size);
50 static BOOL __HeapFree(PHEAP pheap, ULONG flags, LPVOID pmem);
51 static PHEAP_SUBALLOC __HeapAllocSub(PHEAP pheap, PHEAP_BUCKET pbucket);
52 static LPVOID __HeapAllocFragment(PHEAP pheap, ULONG flags, ULONG size);
53 static LPVOID __HeapReAllocFragment(PHEAP pheap, ULONG flags,
54 LPVOID pold, ULONG size);
55 static BOOL __HeapFreeFragment(PHEAP pheap, ULONG flags, LPVOID ptr);
56 static PHEAP __HeapPrepare(LPVOID base, ULONG minsize, ULONG maxsize,
57 ULONG flags);
58
59
60
61 /*********************************************************************
62 * __HeapCommit *
63 * *
64 * commits a range of memory in the heap *
65 *********************************************************************/
66 static BOOL __HeapCommit(PHEAP pheap, LPVOID start, LPVOID end)
67 {
68 dprintf("__HeapCommit( 0x%lX, 0x%lX, 0x%lX)\n",
69 (ULONG) pheap, (ULONG) start, (ULONG) end);
70 #ifdef NOT
71 __VirtualDump();
72 #endif
73 if(end >= pheap->LastBlock)
74 pheap->LastBlock=end;
75 return __VirtualCommit(start, end-start, PAGE_READWRITE);
76 }
77
78 /*********************************************************************
79 * __HeapDecommit *
80 * *
81 * decommits a range of memory in the heap *
82 *********************************************************************/
83 static BOOL __HeapDecommit(PHEAP pheap, LPVOID start, LPVOID end)
84 {
85 dprintf("__HeapDecommit( 0x%lX, 0x%lX, 0x%lX)\n",
86 (ULONG) pheap, (ULONG) start, (ULONG) end);
87 #ifdef NOT
88 __VirtualDump();
89 #endif
90 if((end >= pheap->LastBlock)&&(start<= pheap->LastBlock))
91 pheap->LastBlock=start;
92 return __VirtualDecommit(start, end-start );
93 }
94
95 /*********************************************************************
96 * __HeapAlloc *
97 * *
98 * allocates a range of memory from the heap *
99 *********************************************************************/
100 static LPVOID __HeapAlloc(PHEAP pheap, ULONG flags, ULONG size, ULONG tag)
101 {
102 PHEAP_BLOCK pfree;
103 PHEAP_BLOCK palloc;
104 PHEAP_BLOCK pnext;
105 LPVOID commitstart;
106 LPVOID commitend;
107 ULONG freesize;
108 ULONG allocsize;
109
110 pfree=&(pheap->Start);
111 allocsize=SIZE_ROUND(size);
112 freesize=HEAP_SIZE(pfree);
113 /* look for a free region of memory: simple First Fit */
114 while( HEAP_ISALLOC(pfree) || ( freesize<allocsize ))
115 {
116 pfree=HEAP_NEXT(pfree);
117 if((LPVOID) pfree>=pheap->End)
118 return __ErrorReturnNull(ERROR_OUTOFMEMORY);
119 freesize=HEAP_SIZE(pfree);
120 }
121 palloc=pfree;
122
123 if(freesize>allocsize)
124 {
125 /* commit necessary memory */
126 commitstart=(LPVOID) ROUNDDOWN((ULONG) palloc+HEAP_ADMIN_SIZE,PAGESIZE);
127 commitend =(LPVOID) ROUNDUP ((ULONG) palloc+
128 allocsize+2*HEAP_ADMIN_SIZE, PAGESIZE);
129 if(commitstart<commitend)
130 if(!__HeapCommit(pheap, commitstart, commitend))
131 return __ErrorReturnNull(ERROR_OUTOFMEMORY);
132
133 /* split this block in two */
134 pfree= (LPVOID) palloc+ HEAP_ADMIN_SIZE + allocsize;
135
136 /* update admin */
137 pfree->Size =(freesize-allocsize-HEAP_ADMIN_SIZE) | HEAP_FREE_TAG;
138 pfree->PrevSize=(LPVOID)pfree-(LPVOID)palloc;
139
140 pnext=HEAP_NEXT(pfree);
141 if((LPVOID) pnext < pheap->End )
142 pnext->PrevSize=freesize-allocsize;
143 }
144 else
145 {
146 /* commit necessary memory */
147 commitstart=(LPVOID) ROUNDDOWN((ULONG) palloc+HEAP_ADMIN_SIZE, PAGESIZE);
148 commitend =(LPVOID) ROUNDUP((ULONG) palloc+HEAP_ADMIN_SIZE +allocsize,
149 PAGESIZE);
150 if(commitstart<commitend)
151 if(!__HeapCommit(pheap, commitstart, commitend))
152 return __ErrorReturnNull(ERROR_OUTOFMEMORY);
153 }
154 /* update our administration */
155 palloc->Size= size | tag;
156 if((flags | pheap->Flags)& HEAP_ZERO_MEMORY)
157 memset((LPVOID)palloc+HEAP_ADMIN_SIZE, 0, allocsize);
158 return (LPVOID)palloc+HEAP_ADMIN_SIZE;
159 }
160
161 /*********************************************************************
162 * __HeapFreeRest *
163 * *
164 * used by realloc to free a part of the heap *
165 *********************************************************************/
166 static VOID __HeapFreeRest(PHEAP pheap, PHEAP_BLOCK pfree,
167 ULONG allocsize, ULONG newsize)
168 {
169 PHEAP_BLOCK pnext;
170
171 if(allocsize==newsize)
172 {
173 pfree->PrevSize=allocsize+HEAP_ADMIN_SIZE;
174 return;
175 }
176
177 pfree->Size = (allocsize-newsize-HEAP_ADMIN_SIZE) | HEAP_FREE_TAG;
178 pfree->PrevSize = newsize+HEAP_ADMIN_SIZE;
179
180 pnext=HEAP_NEXT(pfree);
181 /* if there is a free region of memory after us, join it */
182 if(((LPVOID) pnext< pheap->End)&& HEAP_ISFREE(pnext))
183 {
184 pfree->Size = (HEAP_SIZE(pfree)+HEAP_SIZE(pnext) + HEAP_ADMIN_SIZE) |
185 HEAP_FREE_TAG;
186
187 pnext->Size=0;
188 pnext->PrevSize=0;
189 }
190
191 pnext=HEAP_NEXT(pfree);
192 if((LPVOID) pnext< pheap->End)
193 pnext->PrevSize=(LPVOID)pnext-(LPVOID)pfree;
194 }
195
196 /*********************************************************************
197 * __HeapReAlloc *
198 * *
199 * reallocates a range of memory from the heap *
200 *********************************************************************/
201
202 static LPVOID __HeapReAlloc(PHEAP pheap, ULONG flags, LPVOID pold, DWORD size)
203 {
204 PHEAP_BLOCK prealloc=(PHEAP_BLOCK)((LPVOID)pold-HEAP_ADMIN_SIZE);
205 PHEAP_BLOCK pnext;
206 LPVOID pmem;
207 LPVOID commitstart;
208 LPVOID commitend;
209 ULONG allocsize;
210 ULONG newsize;
211 ULONG oldsize;
212
213 /* check that this is a valid allocated block */
214 if(!HEAP_ISALLOC(prealloc))
215 return __ErrorReturnNull(ERROR_INVALID_PARAMETER);
216
217 allocsize = HEAP_RSIZE(prealloc);
218 newsize = SIZE_ROUND(size);
219 /*
220 * cases: size=0 free memory
221 * [ size<HEAP_FRAGMENT_THRESHOLD realloc ]
222 * newsize<previous size free rest
223 * newsize=previous size nop
224 * newsize>previous size try to merge
225 * else realloc
226 */
227 if(size==0)
228 {
229 dprintf("__HeapReAlloc: freeing memory\n");
230 __HeapFree(pheap, flags, pold);
231 return NULL;
232 }
233 #ifdef NOT
234 else if(size < HEAP_FRAGMENT_THRESHOLD)
235 {
236 /* alloc a new fragment */
237 pmem=__HeapAllocFragment(pheap, flags, size);
238 if(pmem)
239 memcpy(pmem, pold, size);
240 return pmem;
241 }
242 #endif
243 else if(newsize < allocsize )
244 {
245 dprintf("__HeapReAlloc: shrinking memory\n");
246 /* free remaining region of memory */
247 prealloc->Size=size | HEAP_NORMAL_TAG;
248 pnext=HEAP_NEXT(prealloc);
249 __HeapFreeRest(pheap, pnext, allocsize, newsize);
250
251 /* decommit unnecessary memory */
252 commitstart=(LPVOID) ROUNDUP((ULONG) pnext+HEAP_ADMIN_SIZE ,PAGESIZE);
253 commitend =(LPVOID) ROUNDDOWN((ULONG) pnext+HEAP_ADMIN_SIZE+
254 HEAP_SIZE(pnext), PAGESIZE);
255 if(commitstart<commitend)
256 __HeapDecommit(pheap, commitstart, commitend);
257 return pold;
258 }
259 else if(newsize == allocsize )
260 {
261 dprintf("__HeapReAlloc: no changes\n");
262 /* nothing to do */
263 prealloc->Size= size | HEAP_NORMAL_TAG;
264 return pold;
265 }
266 else if(newsize > allocsize)
267 {
268 /* try to merge */
269 pnext=HEAP_NEXT(prealloc);
270
271 if(((LPVOID) pnext< pheap->End)&& HEAP_ISFREE(pnext) &&
272 (HEAP_SIZE(pnext) + HEAP_ADMIN_SIZE >=newsize-allocsize))
273 {
274 dprintf("__HeapReAlloc: joining memory\n");
275 oldsize=HEAP_SIZE(prealloc);
276 prealloc->Size=size | HEAP_NORMAL_TAG;
277
278 /* commit new memory if necessary */
279 commitstart=(LPVOID) ROUNDDOWN((ULONG) pnext+HEAP_ADMIN_SIZE,
280 PAGESIZE);
281 commitend =(LPVOID) ROUNDUP((ULONG) pnext+newsize-allocsize+
282 HEAP_ADMIN_SIZE, PAGESIZE);
283 if(commitstart<commitend)
284 if(!__HeapCommit(pheap, commitstart, commitend))
285 return __ErrorReturnNull(ERROR_OUTOFMEMORY);
286
287 __HeapFreeRest(pheap, HEAP_NEXT(prealloc),
288 allocsize+HEAP_ADMIN_SIZE+HEAP_SIZE(pnext), newsize);
289
290 if((flags|pheap->Flags)&HEAP_ZERO_MEMORY)
291 memset(pold+oldsize, 0, size-oldsize);
292 return pold;
293 }
294 else
295 {
296 if((flags&HEAP_REALLOC_IN_PLACE_ONLY)==0)
297 {
298 dprintf("__HeapReAlloc: allocating new memory\n");
299 /* alloc a new piece of memory */
300 oldsize=HEAP_SIZE(prealloc);
301 pmem=__HeapAlloc(pheap, flags, size, HEAP_NORMAL_TAG);
302 if(pmem)
303 memcpy(pmem, pold, oldsize);
304 if((flags|pheap->Flags)&HEAP_ZERO_MEMORY)
305 memset(pmem + oldsize, 0, size-oldsize);
306 __HeapFree(pheap, flags, pold);
307 return pmem;
308 }
309 else
310 return __ErrorReturnNull(ERROR_OUTOFMEMORY);
311 }
312 }
313 return NULL;
314 }
315
316 /*********************************************************************
317 * __HeapFree *
318 * *
319 * frees a range of memory from the heap *
320 *********************************************************************/
321
322 static BOOL __HeapFree(PHEAP pheap, ULONG flags, LPVOID ptr)
323 {
324 PHEAP_BLOCK pfree=(PHEAP_BLOCK)((LPVOID)ptr-HEAP_ADMIN_SIZE);
325 PHEAP_BLOCK pprev;
326 PHEAP_BLOCK pnext;
327 LPVOID decommitstart;
328 LPVOID decommitend;
329
330 /* check that this is a valid allocated block */
331 if(!HEAP_ISALLOC(pfree))
332 return FALSE;
333
334 pfree->Size = HEAP_RSIZE(pfree) | HEAP_FREE_TAG;
335
336 /* if there is a free region of memory before us, join it */
337 pprev=HEAP_PREV(pfree);
338 pnext=HEAP_NEXT(pfree);
339 if((pprev!=pfree) && HEAP_ISFREE(pprev))
340 {
341 pprev->Size = (HEAP_SIZE(pprev)+HEAP_SIZE(pfree) + HEAP_ADMIN_SIZE) |
342 HEAP_FREE_TAG;
343 if((LPVOID) pnext<pheap->End)
344 pnext->PrevSize=(LPVOID)pnext-(LPVOID)pprev;
345
346 pfree->Size=0;
347 pfree->PrevSize=0;
348 pfree=pprev;
349 }
350 /* if there is a free region of memory after us, join it */
351 if(((LPVOID) pnext< pheap->End)&& HEAP_ISFREE(pnext))
352 {
353 pfree->Size = (HEAP_SIZE(pfree)+HEAP_SIZE(pnext) + HEAP_ADMIN_SIZE) |
354 HEAP_FREE_TAG;
355
356 pnext->Size=0;
357 pnext->PrevSize=0;
358
359 pnext=HEAP_NEXT(pfree);
360 if((LPVOID) pnext< pheap->End)
361 pnext->PrevSize=(LPVOID)pnext-(LPVOID)pfree;
362 }
363
364 /* decommit unnecessary memory */
365 decommitstart=(LPVOID) ROUNDUP((ULONG) pfree+HEAP_ADMIN_SIZE ,PAGESIZE);
366 decommitend =(LPVOID) ROUNDDOWN((ULONG) pfree+HEAP_ADMIN_SIZE+
367 HEAP_SIZE(pfree), PAGESIZE);
368 if(decommitstart<decommitend)
369 __HeapDecommit(pheap, decommitstart, decommitend);
370
371 return TRUE;
372 }
373
374 /*********************************************************************
375 * __HeapAllocSub *
376 * *
377 * allocates a range of memory that is used to allocate small *
378 * fragments *
379 *********************************************************************/
380 PHEAP_SUBALLOC __HeapAllocSub(PHEAP pheap, PHEAP_BUCKET pbucket)
381 {
382 INT i;
383 INT add;
384 PHEAP_SUBALLOC psub;
385 PHEAP_FRAGMENT pprev;
386 PHEAP_FRAGMENT pnext;
387 PHEAP_FRAGMENT palloc;
388
389 psub=(PHEAP_SUBALLOC) __HeapAlloc(pheap, 0, pbucket->TotalSize,
390 HEAP_SUB_TAG);
391 if(!psub)
392 return __ErrorReturnNull(ERROR_OUTOFMEMORY);
393
394 /* initialize suballoc */
395 palloc=(PHEAP_FRAGMENT) ((LPVOID)psub + sizeof(HEAP_SUBALLOC));
396 psub->FirstFree=palloc;
397 psub->NumberFree=pbucket->Number;
398 psub->Bitmap=0;
399 psub->Next=pbucket->FirstFree;
400 psub->Prev=NULL;
401 psub->Bucket=pbucket;
402 pbucket->FirstFree=psub;
403
404 /* initialize free fragments */
405 add=pbucket->Size+HEAP_FRAG_ADMIN_SIZE;
406 pprev=NULL;
407 for(i=0;i<pbucket->Number;i++)
408 {
409 pnext=(PHEAP_FRAGMENT)((LPVOID)palloc+add);
410 palloc->Magic=HEAP_FRAG_MAGIC;
411 palloc->Number=i;
412 palloc->Size=pbucket->Size;
413 palloc->Sub=psub;
414 palloc->FreeNext=pnext;
415 palloc->FreePrev=pprev;
416 pprev=palloc;
417 palloc=pnext;
418 }
419 pprev->FreeNext=NULL;
420 return psub;
421 }
422
423 /*********************************************************************
424 * __HeapAllocFragment *
425 * *
426 * allocates a small fragment of memory from the heap *
427 *********************************************************************/
428 static LPVOID __HeapAllocFragment(PHEAP pheap, ULONG flags, ULONG size )
429 {
430 PHEAP_BUCKET pbucket;
431 PHEAP_SUBALLOC psub;
432 PHEAP_FRAGMENT palloc;
433 INT nalloc;
434
435 /* get bucket size */
436 pbucket=pheap->Bucket;
437 while(size>pbucket->Size)
438 {
439 pbucket++;
440 }
441 /* get suballoc */
442 psub = pbucket->FirstFree;
443 if(!psub)
444 psub = __HeapAllocSub(pheap, pbucket);
445 if(!psub)
446 return NULL;
447
448 /* do our bookkeeping */
449 palloc = psub->FirstFree;
450 psub->FirstFree = palloc->FreeNext;
451 nalloc = palloc->Number;
452 psub->NumberFree--;
453 psub->Bitmap|=(1<<nalloc);
454
455 /* advance freelist */
456 if(!psub->NumberFree)
457 pbucket->FirstFree=psub->Next;
458
459 /* initialize allocated block */
460 palloc->Magic=HEAP_FRAG_MAGIC;
461 palloc->Size=size;
462
463 if((flags|pheap->Flags)&HEAP_ZERO_MEMORY)
464 memset((LPVOID)palloc+HEAP_FRAG_ADMIN_SIZE, 0, pbucket->Size);
465 return (LPVOID) palloc+HEAP_FRAG_ADMIN_SIZE;
466 }
467
468 /*********************************************************************
469 * __HeapReAllocFragment *
470 * *
471 * reallocates a small fragment of memory *
472 *********************************************************************/
473 static LPVOID __HeapReAllocFragment(PHEAP pheap, ULONG flags,
474 LPVOID pold, ULONG size )
475 {
476 PHEAP_BUCKET pbucket;
477 PHEAP_SUBALLOC psub;
478 PHEAP_FRAGMENT pfrag=(PHEAP_FRAGMENT)
479 ((LPVOID)pold-HEAP_FRAG_ADMIN_SIZE);
480 LPVOID pmem;
481
482 /* sanity checks */
483 if(pfrag->Magic!=HEAP_FRAG_MAGIC)
484 return __ErrorReturnNull(ERROR_INVALID_PARAMETER);
485
486 /* get bucket size */
487 psub=pfrag->Sub;
488 pbucket=psub->Bucket;
489 if(size<=pbucket->Size)
490 {
491 pfrag->Size=size;
492 return pold;
493 }
494 else
495 {
496 if((flags&HEAP_REALLOC_IN_PLACE_ONLY)==0)
497 {
498 /* alloc a new piece of memory */
499 if(size>HEAP_FRAGMENT_THRESHOLD)
500 pmem=__HeapAlloc(pheap, flags, size, HEAP_NORMAL_TAG);
501 else
502 pmem=__HeapAllocFragment(pheap, flags, size);
503
504 if(pmem)
505 memcpy(pmem, pold, size);
506 if((flags|pheap->Flags)&HEAP_ZERO_MEMORY)
507 memset(pmem+pfrag->Size, 0, size-pfrag->Size);
508
509 __HeapFreeFragment(pheap, flags, pold);
510 return pmem;
511 }
512 }
513 return NULL;
514 }
515
516 /*********************************************************************
517 * __HeapFreeFragment *
518 * *
519 * frees a small fragment of memory *
520 *********************************************************************/
521 static BOOL __HeapFreeFragment(PHEAP pheap, ULONG flags, LPVOID pfree )
522 {
523 PHEAP_BUCKET pbucket;
524 PHEAP_SUBALLOC psub;
525 PHEAP_FRAGMENT pfrag=(PHEAP_FRAGMENT)
526 ((LPVOID)pfree-HEAP_FRAG_ADMIN_SIZE);
527 INT nalloc;
528
529 /* sanity checks */
530 if(pfrag->Magic!=HEAP_FRAG_MAGIC)
531 return __ErrorReturnFalse(ERROR_INVALID_PARAMETER);
532
533 /* get bucket size */
534 psub=pfrag->Sub;
535 pbucket=psub->Bucket;
536
537 nalloc=pfrag->Number;
538 if((psub->Bitmap&(1<<nalloc))==0)
539 return __ErrorReturnFalse(ERROR_INVALID_PARAMETER);
540 psub->NumberFree++;
541 if(psub->NumberFree==pbucket->Number)
542 {
543 /* free suballoc */
544 if(psub==pbucket->FirstFree)
545 pbucket->FirstFree=psub->Next;
546 if(psub->Prev)
547 psub->Prev->Next=psub->Next;
548 if(psub->Next)
549 psub->Next->Prev=psub->Prev;
550 if(!__HeapFree(pheap, flags, psub))
551 return FALSE;
552 }
553 else
554 {
555 /* free fragment */
556 psub->Bitmap&= ~(1<<nalloc);
557
558 if(psub->FirstFree)
559 {
560 pfrag->FreeNext = psub->FirstFree;
561 pfrag->FreePrev = NULL;
562 psub->FirstFree->FreePrev = pfrag;
563 psub->FirstFree = pfrag;
564 }
565 else
566 {
567 psub->FirstFree=pfrag;
568 pfrag->FreePrev=NULL;
569 pfrag->FreeNext=NULL;
570 }
571 }
572 return TRUE;
573 }
574
575 /*********************************************************************
576 * __HeapPrepare *
577 * *
578 * Fills in all the data structures of a heap *
579 *********************************************************************/
580 PHEAP __HeapPrepare(LPVOID base, ULONG minsize, ULONG maxsize, ULONG flags)
581 {
582 PHEAP pheap=(PHEAP) base;
583
584 pheap->Magic=MAGIC_HEAP;
585 pheap->End= ((LPVOID)pheap)+minsize;
586 pheap->Flags=flags;
587 pheap->LastBlock=(LPVOID)pheap + PAGESIZE;
588 memcpy(pheap->Bucket,__HeapDefaultBuckets,sizeof(__HeapDefaultBuckets));
589 if(__ProcessHeap)
590 {
591 pheap->NextHeap=__ProcessHeap->NextHeap;
592 __ProcessHeap->NextHeap=pheap;
593 }
594 else
595 {
596 pheap->NextHeap=0;
597 __ProcessHeap=pheap;
598 }
599 InitializeCriticalSection(&(pheap->Synchronize));
600 pheap->Start.Size= (minsize-sizeof(HEAP))|HEAP_FREE_TAG;
601 pheap->Start.PrevSize =0;
602
603 return pheap;
604 }
605
606 /*********************************************************************
607 * __HeapInit *
608 * *
609 * Called by __VirtualInit to initialize the default process heap *
610 *********************************************************************/
611
612 VOID WINAPI __HeapInit(LPVOID base, ULONG minsize, ULONG maxsize)
613 {
614 mmap(base, PAGESIZE, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE,
615 __DevZero, 0);
616
617 __HeapPrepare(base, minsize, maxsize, 0);
618 }
619
620
621 /*********************************************************************
622 * HeapCreate -- KERNEL32 *
623 *********************************************************************/
624
625 HANDLE WINAPI HeapCreate(ULONG flags, ULONG minsize, ULONG maxsize)
626 {
627 PHEAP pheap;
628
629 aprintf("HeapCreate( 0x%lX, 0x%lX, 0x%lX )\n", flags, minsize, maxsize);
630
631 pheap = __VirtualReserve(NULL, minsize, PAGE_READWRITE | MEM_TOP_DOWN);
632 __VirtualCommit(pheap, PAGESIZE, PAGE_READWRITE);
633 __VirtualDump();
634 return (HANDLE) __HeapPrepare(pheap, minsize, maxsize, flags);
635 }
636
637 /*********************************************************************
638 * HeapDestroy -- KERNEL32 *
639 *********************************************************************/
640 BOOL WINAPI HeapDestroy(HANDLE hheap)
641 {
642 PHEAP pheap=(PHEAP) hheap;
643
644 aprintf("HeapDestroy( 0x%lX )\n", (ULONG) hheap );
645
646 if(pheap->Magic!=MAGIC_HEAP)
647 return __ErrorReturnFalse(ERROR_INVALID_PARAMETER);
648
649 DeleteCriticalSection(&(pheap->Synchronize));
650 __VirtualRelease(pheap);
651
652 return TRUE;
653 }
654
655 /*********************************************************************
656 * HeapAlloc -- KERNEL32 *
657 *********************************************************************/
658 LPVOID WINAPI HeapAlloc(HANDLE hheap, ULONG flags, ULONG size)
659 {
660 PHEAP pheap=hheap;
661 LPVOID retval;
662
663 aprintf("HeapAlloc( 0x%lX, 0x%lX, 0x%lX )\n",
664 (ULONG) hheap, flags, (ULONG) size );
665 #ifdef NOT
666 HeapValidate(hheap, 0, 0);
667 #endif
668 if(( flags | pheap->Flags) & HEAP_NO_SERIALIZE )
669 EnterCriticalSection(&(pheap->Synchronize));
670
671 if(size>HEAP_FRAGMENT_THRESHOLD)
672 retval=__HeapAlloc(pheap, flags, size, HEAP_NORMAL_TAG);
673 else
674 retval=__HeapAllocFragment(pheap, flags, size);
675
676 if( (flags | pheap->Flags) & HEAP_NO_SERIALIZE )
677 LeaveCriticalSection(&(pheap->Synchronize));
678
679 aprintf("HeapAlloc returns 0x%lX\n", (ULONG) retval);
680 return retval;
681
682 }
683
684 /*********************************************************************
685 * HeapReAlloc -- KERNEL32 *
686 *********************************************************************/
687 LPVOID WINAPI HeapReAlloc(HANDLE hheap, ULONG flags, LPVOID ptr, ULONG size)
688 {
689 PHEAP pheap=hheap;
690 PHEAP_BLOCK pfree=((PHEAP_BLOCK)ptr-1);
691 LPVOID retval;
692
693 aprintf("HeapReAlloc( 0x%lX, 0x%lX, 0x%lX, 0x%lX )\n",
694 (ULONG) hheap, flags, (ULONG) ptr, size );
695 #ifdef NOT
696 HeapValidate(hheap, 0, 0);
697 #endif
698 if(( flags | pheap->Flags) & HEAP_NO_SERIALIZE )
699 EnterCriticalSection(&(pheap->Synchronize));
700
701 if(HEAP_ISNORMAL(pfree))
702 retval=__HeapReAlloc(pheap, flags, ptr, size);
703 else if(HEAP_ISFRAG(pfree))
704 retval=__HeapReAllocFragment(pheap, flags, ptr, size);
705 else
706 retval=__ErrorReturnNull(ERROR_INVALID_PARAMETER);
707
708 if( (flags| pheap->Flags) & HEAP_NO_SERIALIZE )
709 LeaveCriticalSection(&(pheap->Synchronize));
710
711 return retval;
712 }
713
714 /*********************************************************************
715 * HeapFree -- KERNEL32 *
716 *********************************************************************/
717 BOOL WINAPI HeapFree(HANDLE hheap, ULONG flags, LPVOID ptr)
718 {
719 PHEAP pheap=hheap;
720 PHEAP_BLOCK pfree=(PHEAP_BLOCK)((LPVOID)ptr-HEAP_ADMIN_SIZE);
721 BOOL retval;
722
723 aprintf("HeapFree( 0x%lX, 0x%lX, 0x%lX )\n",
724 (ULONG) hheap, flags, (ULONG) ptr );
725 #ifdef NOT
726 HeapValidate(hheap, 0, 0);
727 #endif
728 if(( flags | pheap->Flags) & HEAP_NO_SERIALIZE )
729 EnterCriticalSection(&(pheap->Synchronize));
730
731 if(HEAP_ISNORMAL(pfree))
732 retval=__HeapFree(pheap, flags, ptr);
733 else if(HEAP_ISFRAG(pfree))
734 retval=__HeapFreeFragment(pheap, flags, ptr);
735 else
736 retval=__ErrorReturnFalse(ERROR_INVALID_PARAMETER);
737
738 if( (flags| pheap->Flags) & HEAP_NO_SERIALIZE )
739 LeaveCriticalSection(&(pheap->Synchronize));
740
741 return retval;
742 }
743
744 /*********************************************************************
745 * GetProcessHeap -- KERNEL32 *
746 *********************************************************************/
747 HANDLE WINAPI GetProcessHeap(VOID)
748 {
749 aprintf("GetProcessHeap()\n");
750 return (HANDLE) __ProcessHeap;
751 }
752
753 /********************************************************************
754 * GetProcessHeaps -- KERNEL32 *
755 * *
756 * NOTE in Win95 this function is not implemented and just returns *
757 * ERROR_CALL_NOT_IMPLEMENTED *
758 ********************************************************************/
759 DWORD WINAPI GetProcessHeaps(DWORD maxheaps, PHANDLE phandles )
760 {
761 DWORD retval;
762 PHEAP pheap;
763
764 aprintf("GetProcessHeaps( %u, 0x%lX )\n", maxheaps, (ULONG) phandles );
765
766 pheap=__ProcessHeap;
767 retval=0;
768 while((pheap)&&(maxheaps))
769 {
770 *phandles=pheap;
771 phandles++;
772 maxheaps--;
773 retval++;
774 pheap=pheap->NextHeap;
775 }
776 while(pheap)
777 {
778 retval++;
779 pheap=pheap->NextHeap;
780 }
781
782
783 return retval;
784 }
785
786 /*********************************************************************
787 * HeapLock -- KERNEL32 *
788 *********************************************************************/
789
790 BOOL WINAPI HeapLock(HANDLE hheap)
791 {
792 PHEAP pheap=hheap;
793
794 aprintf("HeapLock( 0x%lX )\n", (ULONG) hheap );
795
796 EnterCriticalSection(&(pheap->Synchronize));
797 return TRUE;
798 }
799
800 /*********************************************************************
801 * HeapUnlock -- KERNEL32 *
802 *********************************************************************/
803
804 BOOL WINAPI HeapUnlock(HANDLE hheap)
805 {
806 PHEAP pheap=hheap;
807
808 aprintf("HeapUnlock( 0x%lX )\n", (ULONG) hheap );
809
810 LeaveCriticalSection(&(pheap->Synchronize));
811 return TRUE;
812 }
813
814 /*********************************************************************
815 * HeapCompact -- KERNEL32 *
816 * *
817 * NT uses this function to compact moveable blocks and other things *
818 * Here it does not compact, but it finds the largest free region *
819 *********************************************************************/
820
821 UINT HeapCompact(HANDLE hheap, DWORD flags)
822 {
823 PHEAP pheap=hheap;
824 PHEAP_BLOCK pfree;
825 ULONG freesize;
826 ULONG largestfree;
827
828 if(( flags | pheap->Flags) & HEAP_NO_SERIALIZE )
829 EnterCriticalSection(&(pheap->Synchronize));
830
831 pfree=&(pheap->Start);
832 /* look for the largest free region of memory */
833 largestfree=0;
834 do
835 {
836 freesize=HEAP_SIZE(pfree);
837 if(HEAP_ISFREE(pfree) && freesize>largestfree)
838 largestfree=freesize;
839
840 pfree=HEAP_NEXT(pfree);
841 }
842 while( (LPVOID)pfree < pheap->End );
843
844 if( (flags| pheap->Flags) & HEAP_NO_SERIALIZE )
845 LeaveCriticalSection(&(pheap->Synchronize));
846
847 return largestfree;
848 }
849
850 /*********************************************************************
851 * HeapSize -- KERNEL32 *
852 *********************************************************************/
853 DWORD WINAPI HeapSize(HANDLE hheap, DWORD flags, LPCVOID pmem)
854 {
855 PHEAP pheap=(PHEAP) hheap;
856 PHEAP_BLOCK palloc=((PHEAP_BLOCK)pmem-1);
857 DWORD retval=0;
858
859 aprintf("HeapSize( 0x%lX, 0x%lX, 0x%lX )\n",
860 (ULONG) hheap, flags, (ULONG) pmem );
861
862 if(pheap->Magic!=MAGIC_HEAP)
863 { SetLastError(ERROR_INVALID_PARAMETER); return 0; }
864
865 if(( flags | pheap->Flags) & HEAP_NO_SERIALIZE )
866 EnterCriticalSection(&(pheap->Synchronize));
867
868 if((pmem> (LPVOID)pheap)&&(pmem < pheap->End))
869 {
870 if(HEAP_ISALLOC(palloc))
871 retval=HEAP_SIZE(palloc); /* normal allocation */
872 else if(HEAP_ISFRAG(palloc))
873 retval=HEAP_FRAG_SIZE(palloc); /* fragment */
874 else
875 { SetLastError(ERROR_INVALID_PARAMETER); retval = -1; }
876 }
877
878 if( (flags| pheap->Flags) & HEAP_NO_SERIALIZE )
879 LeaveCriticalSection(&(pheap->Synchronize));
880
881 return retval;
882 }
883
884 /*********************************************************************
885 * HeapValidate -- KERNEL32 *
886 * *
887 * NOTE: only implemented in NT *
888 *********************************************************************/
889 BOOL WINAPI HeapValidate(HANDLE hheap, DWORD flags, LPCVOID pmem)
890 {
891 PHEAP pheap=(PHEAP)hheap;
892 PHEAP_BLOCK pcheck;
893 PHEAP_BLOCK pprev;
894 PHEAP_BLOCK pnext;
895 PHEAP_SUBALLOC psub;
896 PHEAP_FRAGMENT pfrag;
897 PHEAP_FRAGMENT pnextfrag;
898 PHEAP_FRAGMENT pprevfrag;
899 PHEAP_BUCKET pbucket;
900 INT i;
901 INT number;
902 INT add;
903
904 if(( flags | pheap->Flags) & HEAP_NO_SERIALIZE )
905 EnterCriticalSection(&(pheap->Synchronize));
906
907 if(pmem==NULL)
908 {
909 pcheck=&(pheap->Start);
910 pprev=NULL;
911 /* verify all blocks */
912 do
913 {
914 pnext=HEAP_NEXT(pcheck);
915 if((pprev)&&(HEAP_PREV(pcheck)!=pprev))
916 {
917 dprintf("HeapValidate: linked list invalid, region 0x%lX,"
918 " previous region 0x%lX, list says 0x%lX\n",
919 (ULONG)pcheck, (ULONG)pprev, (ULONG) HEAP_PREV(pcheck));
920 return FALSE;
921 }
922 if(HEAP_ISSUB(pcheck))
923 {
924
925 /* check fragments */
926 psub=(PHEAP_SUBALLOC) ((PHEAP_BLOCK)pcheck+1);
927 pbucket=psub->Bucket;
928 pfrag=(PHEAP_FRAGMENT) ((LPVOID)psub + sizeof(HEAP_SUBALLOC));
929
930 if(psub->NumberFree>pbucket->Number)
931 return FALSE;
932
933 add=pbucket->Size+HEAP_FRAG_ADMIN_SIZE;
934 pprevfrag=NULL;
935 number=0;
936 for(i=0;i<pbucket->Number;i++)
937 {
938 pnextfrag=(PHEAP_FRAGMENT)((LPVOID)pfrag+add);
939 if(pfrag->Magic!=HEAP_FRAG_MAGIC)
940 {
941 dprintf("HeapValidate: fragment %d magic invalid, region 0x%lX,"
942 " previous region 0x%lX\n", i, (ULONG)pcheck, (ULONG)pprev);
943 return FALSE;
944 }
945 if(pfrag->Number!=i)
946 {
947 dprintf("HeapValidate: fragment %d number invalid, region 0x%lX,"
948 " previous region 0x%lX\n", i, (ULONG)pcheck, (ULONG)pprev);
949 return FALSE;
950 }
951 if((psub->Bitmap&(1<<i))==0)
952 number++;
953 if(pfrag->Sub!=psub)
954 {
955 dprintf("HeapValidate: fragment %d suballoc invalid, region 0x%lX,"
956 " previous region 0x%lX\n", i, (ULONG)pcheck, (ULONG)pprev);
957 return FALSE;
958 }
959 pprevfrag=pfrag;
960 pfrag=pnextfrag;
961 }
962 if(number!=psub->NumberFree)
963 {
964 dprintf("HeapValidate: invalid number of free fragments, region 0x%lX,"
965 " previous region 0x%lX\n", (ULONG)pcheck, (ULONG)pprev);
966 return FALSE;
967 }
968 dprintf("HeapValidate: [0x%08lX-0x%08lX] suballocated,"
969 " bucket size=%d, bitmap=0x%08lX\n",
970 (ULONG) pcheck, (ULONG) pnext, pbucket->Size, psub->Bitmap);
971 }
972 else if(HEAP_ISFREE(pcheck))
973 {
974 if(HEAP_RSIZE(pcheck)!=HEAP_SIZE(pcheck))
975 {
976 dprintf("HeapValidate: invalid size of free region 0x%lX,"
977 " previous region 0x%lX\n",
978 (ULONG) pcheck, (ULONG) pprev);
979 return FALSE;
980 }
981 dprintf("HeapValidate: [0x%08lX-0x%08lX] free\n",
982 (ULONG) pcheck, (ULONG) pnext );
983 }
984 else if(HEAP_ISNORMAL(pcheck))
985 {
986 dprintf("HeapValidate: [0x%08lX-0x%08lX] allocated\n",
987 (ULONG) pcheck, (ULONG) pnext );
988 }
989 else
990 {
991 dprintf("HeapValidate: invalid tag %x, region 0x%lX,"
992 " previous region 0x%lX\n", pcheck->Size>>28,
993 (ULONG)pcheck, (ULONG)pprev);
994 return FALSE;
995 }
996 pprev=pcheck;
997 pcheck=HEAP_NEXT(pcheck);
998 }
999 while( (LPVOID)pcheck < pheap->End );
1000 }
1001
1002 if( (flags| pheap->Flags) & HEAP_NO_SERIALIZE )
1003 LeaveCriticalSection(&(pheap->Synchronize));
1004
1005 return TRUE;
1006 }
1007
A free Windows-compatible Operating System