source: trunk/src/win32k/misc/rmalloc_avl.c

Last change on this file was 6295, checked in by bird, 24 years ago

Added 16 bytes safety in release.
File size: 46.8 KB
Line 
1/* $Id: rmalloc_avl.c,v 1.7 2001-07-10 16:39:51 bird Exp $
2 *
3 * Resident Heap - AVL.
4 *
5 * Note: This heap does very little checking on input.
6 * Use with care! We're running at Ring-0!
7 *
8 * Copyright (c) 1999-2000 knut st. osmundsen
9 *
10 * Project Odin Software License can be found in LICENSE.TXT
11 *
12 */
13
14
15/*******************************************************************************
16* Defined Constants And Macros *
17*******************************************************************************/
18#pragma info(notrd)
19#ifdef DEBUG
20 #define DEBUG_ALLOC
21 #undef ALLWAYS_HEAPCHECK
22 #undef SOMETIMES_HEAPCHECK
23#endif
24
25#define HEAPANCHOR_SIGNATURE 0xBEEFFEEB
26#define MEMBLOCK_SIGNATURE 0xFEEBBEEF
27
28
29/*#define CB_HDR (sizeof(MEMBLOCK) - 1) /* size of MEMBLOCK header (in bytes) */
30#define CB_HDR ((int)&(((PMEMBLOCK)0)->achUserData[0]))
31#define PNEXT_BLOCK(a) ((PMEMBLOCK)((unsigned)(a) + CB_HDR + (a)->cbSize))
32#define MEMBLOCKFREE_FROM_FREESIZENODE(a) \
33 ((PMEMBLOCKFREE)((unsigned)(a) - CB_HDR + 4))
34#define BLOCKSIZE (1024*256) /* 256KB */
35#define ALIGNMENT 4
36
37#define INCL_DOS
38#define INCL_DOSERRORS
39#ifdef RING0
40 #define INCL_NOAPI
41#else
42 #define INCL_DOSMEMMGR
43#endif
44
45/******************************************************************************
46* Headerfiles
47******************************************************************************/
48#include <os2.h>
49#include "devSegDf.h" /* Win32k segment definitions. */
50#ifdef RING0
51 #include "dev32hlp.h"
52#endif
53#include "asmutils.h"
54#include "log.h"
55#include "rmalloc.h"
56#include "dev32.h"
57#include "avl.h"
58#include "macros.h"
59#include <memory.h>
60
61
62/*******************************************************************************
63* Structures and Typedefs *
64*******************************************************************************/
65#pragma pack(1)
66typedef struct _MEMBLOCK /* MB */
67{
68 AVLNODECORE core;
69 #ifdef DEBUG_ALLOC
70 unsigned long ulSignature; /* Contains MEMBLOCK_SIGNATURE (0xFEEBBEEF) */
71 #endif
72 unsigned cbSize; /* Size of user space (achBlock)*/
73 unsigned char achUserData[1]; /* User data */
74} MEMBLOCK, *PMEMBLOCK;
75
76typedef struct _MEMBLOCKFREE /* MBF */
77{
78 AVLNODECORE core;
79 #ifdef DEBUG_ALLOC
80 unsigned long ulSignature; /* Contains MEMBLOCK_SIGNATURE (0xFEEBBEEF) */
81 #endif
82 AVLNODECORE coreFree; /* AVLNode core for the tree sorted on address */
83 struct _MEMBLOCKFREE *pmbfNext; /* Pointer to list of blocks with the same size */
84} MEMBLOCKFREE, *PMEMBLOCKFREE;
85#pragma pack()
86
87typedef struct _HeapAnchor /* HA */
88{
89 #ifdef DEBUG_ALLOC
90 unsigned long ulSignature; /* Contains HEAPANCHOR_SIGNATURE */
91 #endif
92 unsigned cbSize; /* Total amount of memory in this block. */
93 struct _HeapAnchor *pNext; /* Pointer to the next anchor block. */
94 struct _HeapAnchor *pPrev; /* Pointer to the previous anchor block. */
95 PMEMBLOCK pmbFree; /* Pointer to the used-memblock chain. */
96 PAVLNODECORE pcoreFreeSize; /* Pointer to free-size-tree. */
97 unsigned cbFree; /* Amount of free memory. */
98 PMEMBLOCK pmbUsed; /* Pointer to the used-memblock chain. */
99 unsigned cbUsed; /* Amount of used memory. */
100
101} HEAPANCHOR, *PHEAPANCHOR;
102
103
104typedef struct _SubHeaps_Callback_param
105{
106 unsigned cb;
107 unsigned c;
108} SUBHEAPS_CALLBACK_PARAM, *PSUBHEAPS_CALLBACK_PARAM;
109
110
111typedef struct _Allocated_Callback_param
112{
113 unsigned cb; /* Number of bytes of user data to dump. */
114 unsigned cbAllocated;
115 unsigned cBlocks;
116} ALLOCATED_CALLBACK_PARAM, *PALLOCATED_CALLBACK_PARAM;
117
118/******************************************************************************
119* Global data
120******************************************************************************/
121static PHEAPANCHOR phaFirst; /* Pointer to the first anchor block.*/
122static PHEAPANCHOR phaLast; /* Pointer to the last anchor block.*/
123unsigned cbResHeapMax; /* Maximum amount of memory used by the heap. */
124
125#ifndef RING0
126char fResInited; /* init flag */
127#endif
128
129
130/******************************************************************************
131* Internal functions
132******************************************************************************/
133static void resInsertUsed(PHEAPANCHOR pha, PMEMBLOCK pmb);
134static void resRemoveFromFreeSize(PHEAPANCHOR pha, PMEMBLOCKFREE pmbf);
135static void resInsertIntoFreeSize(PHEAPANCHOR pha, PMEMBLOCKFREE pmbf);
136static void resInsertFree(PHEAPANCHOR pha, PMEMBLOCK pmb);
137static PMEMBLOCK resGetFreeMemblock(PHEAPANCHOR *ppha, unsigned cbUserSize);
138static PMEMBLOCK resFindUsedBlock(PHEAPANCHOR *ppha, void *pvUser);
139static PMEMBLOCK resFindWithinUsedBlock(PHEAPANCHOR *ppha, void *pvUser);
140#ifdef DEBUG_ALLOC
141static int resCheckAVLTree(PMEMBLOCK pmb);
142static int resCheckAVLTreeFree(PAVLNODECORE pNode);
143#endif
144static unsigned _res_dump_subheaps_callback(PMEMBLOCK pmb, PSUBHEAPS_CALLBACK_PARAM pCb);
145static unsigned _res_dump_allocated_callback(PMEMBLOCK pmb, PALLOCATED_CALLBACK_PARAM pParam);
146
147
148/**
149 * Inserts a memblock into the used chain.
150 * @param pha Pointer to the heap anchor which the block is to be inserted into.
151 * @param pmb Pointer to memblock to insert into the free list.
152 * @remark Sorts on address.
153 */
154static void resInsertUsed(PHEAPANCHOR pha, PMEMBLOCK pmb)
155{
156 pha->cbUsed += pmb->cbSize;
157 pmb->core.Key = (AVLKEY)pmb;
158 AVLInsert((PPAVLNODECORE)&pha->pmbUsed, (PAVLNODECORE)pmb);
159}
160
161
162/**
163 * Remove a given memblockfree from the free-size-tree.
164 */
165static void resRemoveFromFreeSize(PHEAPANCHOR pha, PMEMBLOCKFREE pmbf)
166{
167 PMEMBLOCKFREE pmbfParent;
168 PMEMBLOCKFREE pmbfTmp;
169
170 pmbfTmp = (PMEMBLOCKFREE)AVLGetWithParent(&pha->pcoreFreeSize,
171 (PPAVLNODECORE)SSToDS(&pmbfParent),
172 pmbf->coreFree.Key);
173 if (pmbfTmp != NULL)
174 {
175 pmbfTmp = MEMBLOCKFREE_FROM_FREESIZENODE(pmbfTmp);
176 if (pmbfTmp != pmbf)
177 {
178 PMEMBLOCKFREE pmbfPrev;
179 do
180 {
181 pmbfPrev = pmbfTmp;
182 pmbfTmp = pmbfTmp->pmbfNext;
183 } while (pmbfTmp != NULL && pmbfTmp != pmbf);
184
185 if (pmbfTmp != NULL)
186 pmbfPrev->pmbfNext = pmbfTmp->pmbfNext;
187 else
188 kprintf(("resRemoveFromFreeSize: internal heap error, pmbf not in list.\n"));
189 }
190 else
191 { /* pmbf is first in the list */
192 if (pmbfTmp->pmbfNext == NULL)
193 { /* no list - no other nodes of this size: simply remove it. */
194 AVLRemove(&pha->pcoreFreeSize, pmbf->coreFree.Key);
195 }
196 else
197 { /* other nodes of this size: replace pmbf with the first node in the chain. */
198 memcpy((void*)&pmbfTmp->pmbfNext->coreFree, (void*)&pmbfTmp->coreFree, sizeof(pmbfTmp->coreFree));
199 if (pmbfParent != NULL)
200 {
201 pmbfParent = MEMBLOCKFREE_FROM_FREESIZENODE(pmbfParent);
202 if (pmbfTmp->coreFree.Key < pmbfParent->coreFree.Key)
203 pmbfParent->coreFree.pLeft = &pmbf->pmbfNext->coreFree;
204 else
205 pmbfParent->coreFree.pRight = &pmbf->pmbfNext->coreFree;
206 }
207 else
208 pha->pcoreFreeSize = &pmbf->pmbfNext->coreFree;
209 }
210 }
211 }
212 else
213 kprintf(("resRemoveFromFreeSize: internal heap error, free-node not in free-size tree.\n"));
214}
215
216
217/**
218 * Inserts a block into the free-size-tree.
219 */
220static void resInsertIntoFreeSize(PHEAPANCHOR pha, PMEMBLOCKFREE pmbf)
221{
222 PMEMBLOCKFREE pmbfTmp;
223
224 pmbfTmp = (PMEMBLOCKFREE)AVLGet(&pha->pcoreFreeSize, pmbf->coreFree.Key);
225 if (pmbfTmp != NULL)
226 {
227 pmbfTmp = MEMBLOCKFREE_FROM_FREESIZENODE(pmbfTmp);
228 while (pmbfTmp->pmbfNext != NULL && pmbfTmp->pmbfNext > pmbf)
229 pmbfTmp = pmbfTmp->pmbfNext;
230
231 pmbf->pmbfNext = pmbfTmp->pmbfNext;
232 pmbfTmp->pmbfNext = pmbf;
233 }
234 else
235 {
236 pmbf->pmbfNext = NULL;
237 AVLInsert(&pha->pcoreFreeSize, &pmbf->coreFree);
238 }
239}
240
241
242/**
243 * Inserts a memblock into the free chain.
244 * Merges blocks adjecent blocks.
245 * @param pha Pointer to the heap anchor which the block is to be inserted into.
246 * @param pmb Pointer to memblock to insert into the free list.
247 * @remark Sorts on address.
248 */
249static void resInsertFree(PHEAPANCHOR pha, PMEMBLOCK pmb)
250{
251 PMEMBLOCKFREE pmbf = (PMEMBLOCKFREE)pmb;
252 PMEMBLOCKFREE pmbfRight;
253 PMEMBLOCKFREE pmbfRightParent;
254 PMEMBLOCKFREE pmbfLeft;
255
256 pha->cbFree += pmb->cbSize;
257
258 /*
259 * Get both right and left to determin which case we have here.
260 * Four cases are possible:
261 * 1 - insert no merge.
262 * 2 - insert left merge.
263 * 3 - insert right merge.
264 * 4 - insert both left and right merge.
265 */
266 pmbfRight = (PMEMBLOCKFREE)AVLGetWithParent((PPAVLNODECORE)&pha->pmbFree,
267 (PPAVLNODECORE)SSToDS(&pmbfRightParent),
268 (AVLKEY)PNEXT_BLOCK(pmb));
269 pmbfLeft = (PMEMBLOCKFREE)AVLGetBestFit((PPAVLNODECORE)&pha->pmbFree,
270 (AVLKEY)pmbf, FALSE);
271 if (pmbfLeft != NULL && (PMEMBLOCKFREE)PNEXT_BLOCK((PMEMBLOCK)pmbfLeft) != pmbf)
272 pmbfLeft = NULL;
273
274 if (pmbfLeft == NULL && pmbfRight == NULL)
275 { /* 1 - insert no merge */
276 pmbf->core.Key = (AVLKEY)pmbf;
277 AVLInsert((PPAVLNODECORE)&pha->pmbFree, (PAVLNODECORE)pmbf);
278 resInsertIntoFreeSize(pha, pmbf);
279 }
280 else if (pmbfLeft != NULL && pmbfRight == NULL)
281 { /* 2 - insert left merge: just add pmbf to pmbfLeft. */
282 resRemoveFromFreeSize(pha, pmbfLeft);
283 pmbfLeft->coreFree.Key += CB_HDR + pmbf->coreFree.Key;
284 pha->cbFree += CB_HDR;
285 resInsertIntoFreeSize(pha, pmbfLeft);
286 }
287 else if (pmbfLeft == NULL && pmbfRight != NULL)
288 { /* 3 - insert right merge: replace pmbfRight with pmbf in the pmbfFree tree; */
289 resRemoveFromFreeSize(pha, pmbfRight);
290 memcpy((void*)&pmbf->core, (void*)&pmbfRight->core, sizeof(pmbf->core));
291 pmbf->core.Key = (AVLKEY)pmbf;
292 pmbf->coreFree.Key += CB_HDR + pmbfRight->coreFree.Key;
293 pha->cbFree += CB_HDR;
294 resInsertIntoFreeSize(pha, pmbf);
295 if (pmbfRightParent != NULL)
296 {
297 if (pmbf < pmbfRightParent)
298 pmbfRightParent->core.pLeft = (PAVLNODECORE)pmbf;
299 else
300 pmbfRightParent->core.pRight = (PAVLNODECORE)pmbf;
301 }
302 else
303 pha->pmbFree = (PMEMBLOCK)pmbf;
304 }
305 else
306 { /* 4 -insert both left and right merge */
307 if (AVLRemove((PPAVLNODECORE)&pha->pmbFree, (AVLKEY)pmbfRight) != (PAVLNODECORE)pmbfRight)
308 {
309 kprintf(("resInsertFree: AVLRemove on pmbfRight failed.\n"));
310 return;
311 }
312 resRemoveFromFreeSize(pha, pmbfLeft);
313 resRemoveFromFreeSize(pha, pmbfRight);
314 pmbfLeft->coreFree.Key += CB_HDR*2 + pmbf->coreFree.Key + pmbfRight->coreFree.Key;
315 pha->cbFree += CB_HDR*2;
316 resInsertIntoFreeSize(pha, pmbfLeft);
317 }
318}
319
320
321/**
322 * Finds a free block at the requested size.
323 * @returns Pointer to block (not in free list any longer).
324 * @param ppha Upon return the pointer pointed to contains the heap
325 * anchor which the memory block was allocated from.
326 * @param cbUserSize Bytes the user have requested.
327 * @sketch cbUserSize is aligned to nearest 4 bytes.
328 * ...
329 *
330 */
331static PMEMBLOCK resGetFreeMemblock(PHEAPANCHOR *ppha, unsigned cbUserSize)
332{
333 unsigned cbBlockSize;
334 unsigned cbTotalSize = 0;
335
336 #ifdef DEBUG
337 cbUserSize = MAX(ALIGN(cbUserSize, ALIGNMENT), sizeof(MEMBLOCKFREE) - CB_HDR);
338 #else
339 cbUserSize = MAX(ALIGN(cbUserSize + 16, ALIGNMENT), sizeof(MEMBLOCKFREE) - CB_HDR); /* add 16 bytes for safety... */
340 #endif
341
342 *ppha = phaFirst;
343 while (*ppha != NULL)
344 {
345 if ((*ppha)->cbFree >= cbUserSize + CB_HDR)
346 {
347 PMEMBLOCKFREE pmbf;
348
349 pmbf = (PMEMBLOCKFREE)AVLGetBestFit(&(*ppha)->pcoreFreeSize, cbUserSize, TRUE);
350 if (pmbf != NULL)
351 {
352 pmbf = MEMBLOCKFREE_FROM_FREESIZENODE(pmbf);
353 resRemoveFromFreeSize(*ppha, pmbf);
354 (*ppha)->cbFree -= pmbf->coreFree.Key;
355
356 /* pmbf is now the block which we are to return, but do we have to split it? */
357 if (pmbf->coreFree.Key > sizeof(MEMBLOCKFREE) + cbUserSize)
358 {
359 PMEMBLOCKFREE pmbfTmp = pmbf;
360 pmbf = (PMEMBLOCKFREE)((unsigned)pmbfTmp + pmbfTmp->coreFree.Key - cbUserSize);
361 #ifdef DEBUG_ALLOC
362 pmbf->ulSignature = MEMBLOCK_SIGNATURE;
363 #endif
364 pmbfTmp->coreFree.Key -= CB_HDR + cbUserSize;
365 pmbf->coreFree.Key = cbUserSize;
366 (*ppha)->cbFree += pmbfTmp->coreFree.Key;
367 resInsertIntoFreeSize(*ppha, pmbfTmp);
368 }
369 else
370 {
371 PMEMBLOCKFREE pmbfTmp = (PMEMBLOCKFREE)AVLRemove((PPAVLNODECORE)&(*ppha)->pmbFree, (AVLKEY)pmbf);
372 if (pmbfTmp != pmbf)
373 {
374 kprintf(("resGetFreeMemblock: Internal heap error - failed to Remove best fit block!\n"));
375 return NULL;
376 }
377 }
378 return (PMEMBLOCK)pmbf;
379 }
380 }
381
382 cbTotalSize += (*ppha)->cbSize;
383
384 /* next heap anchor */
385 *ppha = (*ppha)->pNext;
386 }
387
388
389 /*
390 * Add a new heap anchor?
391 */
392 cbBlockSize = ALIGN(cbUserSize + CB_HDR * 2, BLOCKSIZE);
393 if (cbResHeapMax >= cbTotalSize + cbBlockSize)
394 {
395 #ifdef RING0
396 *ppha = D32Hlp_VMAlloc(0UL, cbBlockSize, ~0UL);
397 #else
398 if (DosAllocMem((void*)ppha, cbBlockSize, PAG_COMMIT | PAG_READ | PAG_WRITE) != 0)
399 *ppha = NULL;
400 #endif
401
402 if (*ppha != NULL)
403 {
404 register PHEAPANCHOR pha = *ppha;
405 PMEMBLOCK pmb;
406 memset(pha, 0, sizeof(*pha));
407
408 /* anchor block */
409 #ifdef DEBUG_ALLOC
410 pha->ulSignature = HEAPANCHOR_SIGNATURE;
411 #endif
412 pha->cbSize = cbBlockSize;
413
414 /* free memblock */
415 pmb = (PMEMBLOCK)((unsigned)pha + sizeof(*pha));
416 #ifdef DEBUG_ALLOC
417 pmb->ulSignature = MEMBLOCK_SIGNATURE;
418 #endif
419 pmb->cbSize = cbBlockSize - sizeof(*pha) - CB_HDR * 2 - cbUserSize;
420 resInsertFree(pha, pmb);
421
422 /* used memblock */
423 pmb = (PMEMBLOCK)((unsigned)pha + cbBlockSize - cbUserSize - CB_HDR);
424 #ifdef DEBUG_ALLOC
425 pmb->ulSignature = MEMBLOCK_SIGNATURE;
426 #endif
427 pmb->cbSize = cbUserSize;
428
429 /* insert into list */
430 pha->pPrev = phaLast;
431 pha->pNext = NULL;
432 if (phaLast == NULL) /* Might never happen but just in case it does. */
433 phaLast = phaFirst = pha;
434 else
435 phaLast->pNext = pha;
436 phaLast = pha;
437
438 return pmb;
439 }
440 else
441 kprintf(("resGetFreeMemblock: Unable to allocate heap memory.\n"));
442 }
443 else
444 {
445 kprintf(("resGetFreeMemblock: Allocation failed, limit reached. \n"
446 " %d(=cbResHeapMax) < %d(=cbTotalSize) + %d(=cbBlockSize)\n",
447 cbResHeapMax, cbTotalSize, cbBlockSize));
448 }
449
450 return NULL;
451}
452
453
454/**
455 * Finds a used memory block.
456 * @returns Pointer to memblock if found.
457 * @param ppha Pointer to pointer to heap anchor block the returned memblock is located in. (output)
458 * NULL is allowed.
459 * @param pvUser User pointer to find the block to.
460 */
461static PMEMBLOCK resFindUsedBlock(PHEAPANCHOR *ppha, void *pvUser)
462{
463 if (pvUser != NULL)
464 {
465 register PHEAPANCHOR pha = phaFirst;
466 while (pha != NULL
467 && !((unsigned)pvUser > (unsigned)pha
468 && (unsigned)pvUser < (unsigned)pha + pha->cbSize))
469 pha = pha->pNext;
470
471 if (ppha != NULL)
472 *ppha = pha;
473 if (pha != NULL)
474 {
475 register PMEMBLOCK pmb;
476 #ifdef DEBUG_ALLOC
477 if (pha->ulSignature != HEAPANCHOR_SIGNATURE)
478 {
479 kprintf(("resFindUsedBlock: Invalid heapanchor signature.\n"));
480 return NULL;
481 }
482 #endif
483 pmb = (PMEMBLOCK)AVLGet((PPAVLNODECORE)&pha->pmbUsed, (AVLKEY)((unsigned)pvUser - CB_HDR));
484 #ifdef DEBUG_ALLOC
485 if (pmb != NULL && pmb->ulSignature != MEMBLOCK_SIGNATURE)
486 {
487 kprintf(("resFindUsedBlock: Invalid memblock signature.\n"));
488 pmb = NULL;
489 }
490 #endif
491 return pmb;
492 }
493 }
494
495 return NULL;
496}
497
498
499/**
500 * Finds a used memory block from a pointer into the userdata.
501 * @returns Pointer to memblock if found.
502 * @param ppha Pointer to pointer to heap anchor block the returned memblock is located in. (output)
503 * NULL is allowed.
504 * @param pvUser User pointer to find the block to.
505 */
506static PMEMBLOCK resFindWithinUsedBlock(PHEAPANCHOR *ppha, void *pvUser)
507{
508 register PHEAPANCHOR pha = phaFirst;
509
510 while (pha != NULL
511 && !((unsigned)pvUser > (unsigned)pha
512 && (unsigned)pvUser < (unsigned)pha + pha->cbSize))
513 pha = pha->pNext;
514
515 if (ppha != NULL)
516 *ppha = pha;
517 if (pha != NULL)
518 {
519 PMEMBLOCK pmb;
520
521 #ifdef DEBUG_ALLOC
522 if (pha->ulSignature != HEAPANCHOR_SIGNATURE)
523 {
524 kprintf(("resFindWithinUsedBlock: Invalid heapanchor signature.\n"));
525 return NULL;
526 }
527 #endif
528
529
530 pmb = (PMEMBLOCK)AVLGetBestFit((PPAVLNODECORE)&pha->pmbUsed,
531 (AVLKEY)pvUser, TRUE);
532 if (pmb != NULL
533 && (unsigned)pmb + pmb->cbSize + CB_HDR > (unsigned)pvUser
534 && (unsigned)pmb + CB_HDR <= (unsigned)pvUser
535 )
536 {
537 #ifdef DEBUG_ALLOC
538 if (pmb->ulSignature != MEMBLOCK_SIGNATURE)
539 {
540 kprintf(("resFindWithinUsedBlock: Invalid memblock signature.\n"));
541 pmb = NULL;
542 }
543 #endif
544 return pmb;
545 }
546 }
547
548 return NULL;
549}
550
551
552/**
553 * Initiate the heap "subsystem".
554 * @returns 0 on success, not 0 on error.
555 * @param cbSizeInit The initial size of the heap in bytes.
556 * @param cbSizeMax Maximum heapsize in bytes.
557 */
558int resHeapInit(unsigned cbSizeInit, unsigned cbSizeMax)
559{
560 unsigned cbSize = MAX(BLOCKSIZE, cbSizeInit);
561 PMEMBLOCK pmb;
562
563 cbResHeapMax = cbSizeMax;
564
565 #ifdef RING0
566 phaFirst = D32Hlp_VMAlloc(0UL, cbSize, ~0UL);
567 #else
568 if (DosAllocMem((void*)&phaFirst, cbSize, PAG_COMMIT | PAG_READ | PAG_WRITE) != 0)
569 phaFirst = NULL;
570 #endif
571 if (phaFirst == NULL)
572 {
573 kprintf(("unable to allocate heap memory.\n"));
574 Int3();
575 return -1;
576 }
577
578 #ifdef DEBUG_ALLOC
579 phaFirst->ulSignature = HEAPANCHOR_SIGNATURE;
580 #endif
581 phaFirst->cbSize = cbSize;
582 phaFirst->pNext = NULL;
583 phaFirst->pPrev = NULL;
584 phaFirst->pmbFree = NULL;
585 phaFirst->pcoreFreeSize = NULL;
586 phaFirst->cbFree = 0;
587 phaFirst->pmbUsed = NULL;
588 phaFirst->cbUsed = 0UL;
589 phaLast = phaFirst;
590
591 pmb = (PMEMBLOCK)((unsigned)phaFirst+sizeof(*phaFirst));
592 pmb->cbSize = cbSize - sizeof(*phaFirst) - CB_HDR;
593 #ifdef DEBUG_ALLOC
594 pmb->ulSignature = MEMBLOCK_SIGNATURE;
595 #endif
596 resInsertFree(phaFirst, pmb);
597
598 #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
599 if (!_res_heap_check())
600 { /* error! */
601 kprintf(("resHeapInit: _res_heap_check failed!\n"));
602 #ifdef DEBUG
603 Int3();
604 #endif
605 return -2;
606 }
607 #endif
608 #ifndef RING0
609 fResInited = TRUE;
610 #endif
611 return 0;
612}
613
614
615/**
616 * malloc - allocates a given amount of memory.
617 * @returns Pointer to allocated memory.
618 * NULL if out of memory. (Or memory to fragmented.)
619 * @param cbSize Bytes user requests us to allocate. This is aligned
620 * to four bytes.
621 */
622void * rmalloc(unsigned cbSize)
623{
624 #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
625 if (!_res_heap_check())
626 {
627 kprintf(("rmalloc: _res_heap_check failed!\n"));
628 return NULL;
629 }
630 #endif
631
632 if (cbSize != 0)
633 {
634 PHEAPANCHOR pha;
635 PMEMBLOCK pmb = resGetFreeMemblock(SSToDS(&pha), cbSize);
636 if (pmb != NULL)
637 {
638 resInsertUsed(pha, pmb);
639 return &pmb->achUserData[0];
640 }
641 }
642 else
643 kprintf(("rmalloc: error cbSize = 0\n"));
644
645 return NULL;
646}
647
648
649/**
650 * Reallocate a heapblock.
651 * @returns Pointer to new heapblock.
652 * @param pv Pointer to the block to realloc.
653 * If pv is NULL, this call is equal to malloc.
654 * @param cbNew The new block size.
655 */
656void *rrealloc(void *pv, unsigned cbNew)
657{
658 PMEMBLOCK pmb;
659 PHEAPANCHOR pha;
660
661 #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
662 if (!_res_heap_check())
663 {
664 kprintf(("rrealloc: _res_heap_check failed!\n"));
665 return NULL;
666 }
667 #endif
668 pmb = resFindUsedBlock(SSToDS(&pha), pv);
669 if (pmb != NULL)
670 {
671 void *pvRet;
672
673 cbNew = MAX(ALIGN(cbNew, ALIGNMENT), sizeof(MEMBLOCKFREE) - CB_HDR);
674 if (cbNew <= pmb->cbSize)
675 { /* shrink block */
676 pvRet = pv;
677 if (cbNew + sizeof(MEMBLOCKFREE) <= pmb->cbSize)
678 { /* split block */
679 PMEMBLOCKFREE pmbfNew = (PMEMBLOCKFREE)((unsigned)pmb + CB_HDR + cbNew);
680 #ifdef DEBUG_ALLOC
681 pmbfNew->ulSignature = MEMBLOCK_SIGNATURE;
682 #endif
683 pha->cbUsed -= pmb->cbSize - cbNew;
684 pmbfNew->coreFree.Key = pmb->cbSize - cbNew - CB_HDR;
685 pmb->cbSize = cbNew;
686 resInsertFree(pha, (PMEMBLOCK)pmbfNew);
687 #ifdef ALLWAYS_HEAPCHECK
688 if (!_res_heap_check())
689 {
690 kprintf(("rrealloc: _res_heap_check failed!\n"));
691 return NULL;
692 }
693 #endif
694 }
695 }
696 else
697 { /* expand block - this code may be optimized... */
698 #if 0
699 pvRet = rmalloc(cbNew);
700 if (pvRet != NULL)
701 {
702 memcpy(pvRet, pv, pmb->cbSize);
703 rfree(pv);
704 }
705 #else
706 /* optimized FIXME! */
707 PMEMBLOCKFREE pmbfRightParent;
708 PMEMBLOCKFREE pmbfRight = (PMEMBLOCKFREE)AVLGetWithParent((PPAVLNODECORE)&pha->pmbFree,
709 (PPAVLNODECORE)SSToDS(&pmbfRightParent),
710 (AVLKEY)PNEXT_BLOCK(pmb));
711 if (pmbfRight != NULL && pmbfRight->coreFree.Key + pmb->cbSize + CB_HDR >= cbNew)
712 {
713 pvRet = pv;
714 /* split the free block? */
715 if (pmbfRight->coreFree.Key + pmb->cbSize + CB_HDR - sizeof(MEMBLOCKFREE) >= cbNew)
716 {
717 unsigned cb = pmbfRight->coreFree.Key;
718 PMEMBLOCKFREE pmbfNew = (PMEMBLOCKFREE)((unsigned)pmb + CB_HDR + cbNew);
719 resRemoveFromFreeSize(pha, pmbfRight);
720 pmbfNew->coreFree.Key = cb + pmb->cbSize - cbNew;
721 memmove((void*)&pmbfNew->core, (void*)&pmbfRight->core, sizeof(pmbfNew->core));
722 pmbfNew->core.Key = (AVLKEY)pmbfNew;
723 #ifdef DEBUG_ALLOC
724 pmbfNew->ulSignature = MEMBLOCK_SIGNATURE;
725 #endif
726 if (pmbfRightParent != NULL)
727 {
728 if (pmbfNew < pmbfRightParent)
729 pmbfRightParent->core.pLeft = &pmbfNew->core;
730 else
731 pmbfRightParent->core.pRight = &pmbfNew->core;
732 }
733 else
734 pha->pmbFree = (PMEMBLOCK)pmbfNew;
735
736 resInsertIntoFreeSize(pha, pmbfNew);
737 pha->cbUsed += cbNew - pmb->cbSize;
738 pha->cbFree -= cb - pmbfNew->coreFree.Key;
739 pmb->cbSize = cbNew;
740 }
741 else
742 {
743 if (AVLRemove((PPAVLNODECORE)&pha->pmbFree, (AVLKEY)pmbfRight) != (PAVLNODECORE)pmbfRight)
744 {
745 kprintf(("rrealloc: AVLRemove failed for pmbfRight - hmm!\n"));
746 return NULL;
747 }
748 resRemoveFromFreeSize(pha, pmbfRight);
749 pmb->cbSize += pmbfRight->coreFree.Key + CB_HDR;
750 pha->cbFree -= pmbfRight->coreFree.Key;
751 pha->cbUsed += pmbfRight->coreFree.Key + CB_HDR;
752 }
753
754 }
755 else
756 { /* worst case: allocate a new block, copy data and free the old block. */
757 pvRet = rmalloc(cbNew);
758 if (pvRet != NULL)
759 {
760 memcpy(pvRet, pv, pmb->cbSize);
761 rfree(pv);
762 }
763 }
764 #endif
765 }
766 return pvRet;
767 }
768 else
769 {
770 if (pv == NULL)
771 return rmalloc(cbNew);
772 kprintf(("rrealloc: invalid user pointer, pv=0x%08x\n", pv));
773 }
774 return NULL;
775}
776
777
778/**
779 * Frees a block.
780 * @param pv User pointer.
781 */
782void rfree(void *pv)
783{
784 #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
785 if (!_res_heap_check())
786 {
787 kprintf(("rfree: _res_heap_check failed!\n"));
788 return;
789 }
790 #endif
791
792 if (pv != NULL)
793 {
794 PHEAPANCHOR pha = phaFirst;
795
796 while (pha != NULL
797 && !((unsigned)pv > (unsigned)pha
798 && (unsigned)pv < (unsigned)pha + pha->cbSize))
799 pha = pha->pNext;
800
801 if (pha != NULL)
802 {
803 PMEMBLOCK pmb = (PMEMBLOCK)AVLRemove((PPAVLNODECORE)&pha->pmbUsed,
804 (AVLKEY)((unsigned)pv - CB_HDR));
805 if (pmb != NULL)
806 {
807 pha->cbUsed -= pmb->cbSize;
808 resInsertFree(pha, pmb);
809 }
810 else
811 kprintf(("rfree: heap block not found!\n"));
812 }
813 else
814 kprintf(("rfree: heap block not within the large blocks!\n"));
815 }
816 else
817 kprintf(("rfree: Free received a NULL pointer!\n"));
818}
819
820
821/**
822 * Gets the size of a block.
823 * @returns Bytes in a block.
824 */
825unsigned _res_msize(void *pv)
826{
827 PHEAPANCHOR pha;
828 PMEMBLOCK pmb;
829
830 #ifdef ALLWAYS_HEAPCHECK
831 if (!_res_heap_check())
832 kprintf(("_res_msize: _res_heap_check failed!\n"));
833 #endif
834
835 pmb = resFindUsedBlock(SSToDS(&pha), pv);
836 return pmb != NULL ? pmb->cbSize : 0;
837}
838
839
840/**
841 * Checks if pv is a valid heappointer.
842 * @returns 1 if valid. 0 if invalid.
843 * @param pv User data pointer.
844 */
845int _res_validptr(void *pv)
846{
847 PMEMBLOCK pmb;
848
849 #ifdef ALLWAYS_HEAPCHECK
850 if (!_res_heap_check())
851 kprintf(("_res_validptr: _res_heap_check failed!\n"));
852 #endif
853
854 pmb = resFindWithinUsedBlock(NULL, pv);
855 return pmb != NULL;
856}
857
858
859/**
860 * Checks that the dataaera made up by pv and cbSize valid with in the heap.
861 * @returns 1 if valid. 0 if invalid.
862 * @param pv User data pointer.
863 * @param cbSize Size of data which has to be valid.
864 */
865int _res_validptr2(void *pv, unsigned cbSize)
866{
867 PMEMBLOCK pmb;
868
869 #ifdef ALLWAYS_HEAPCHECK
870 if (!_res_heap_check())
871 kprintf(("_res_validptr: _res_heap_check failed!\n"));
872 #endif
873
874 pmb = resFindWithinUsedBlock(NULL, pv);
875 return pmb != NULL ? (pmb->cbSize - ((unsigned)pv - (unsigned)pmb - CB_HDR)) >= cbSize : FALSE;
876}
877
878
879/**
880 * Get amount of free memory (in bytes)
881 * @returns Amount of free memory (in bytes).
882 * @remark Note that this amount is of all free memory blocks and
883 * that these blocks are fragmented.
884 * You'll probably not be able to allocate a single block
885 * of the returned size.
886 */
887unsigned _res_memfree(void)
888{
889 PHEAPANCHOR pha = phaFirst;
890 unsigned cb;
891
892 #ifdef ALLWAYS_HEAPCHECK
893 if (!_res_heap_check())
894 kprintf(("_res_memfree: _res_heap_check failed!\n"));
895 #endif
896
897 for (cb = 0; pha != NULL; pha = pha->pNext)
898 cb += pha->cbFree;
899
900 return cb;
901}
902
903
904/**
905 * Get amount of used memory (in bytes)
906 * @returns Amount of used memory (in bytes).
907 */
908unsigned _res_memused(void)
909{
910 PHEAPANCHOR pha = phaFirst;
911 unsigned cb;
912
913 #ifdef ALLWAYS_HEAPCHECK
914 if (!_res_heap_check())
915 kprintf(("_res_memused: _res_heap_check failed!\n"));
916 #endif
917
918 for (cb = 0; pha != NULL; pha = pha->pNext)
919 cb += pha->cbUsed;
920
921 return cb;
922}
923
924
925/**
926 * Collects the heap state.
927 * @returns 0 on success.
928 * -1 on error.
929 * @param pState Pointer to a RES_HEAPSTATE structure which is
930 * filled upon successful return.
931 */
932int _res_state(PHEAPSTATE pState)
933{
934 PHEAPANCHOR pha;
935
936 #ifdef ALLWAYS_HEAPCHECK
937 if (!_res_heap_check())
938 {
939 kprintf(("_res_state: _res_heap_check failed!\n"));
940 return -1;
941 }
942 #endif
943
944 if (pState == NULL)
945 return -1;
946
947 /*
948 * Loop thru all the anchor blocks and all memory blocks
949 * building the stats.
950 */
951 memset(pState, 0, sizeof(HEAPSTATE));
952 for (pha = phaFirst; pha != NULL; pha = pha->pNext)
953 {
954 AVLENUMDATA EnumData;
955 PAVLENUMDATA pEnumData = SSToDS(&EnumData);
956 PMEMBLOCK pmb;
957
958 /* count of free blocks */
959 pmb = (PMEMBLOCK)AVLBeginEnumTree((PPAVLNODECORE)&pha->pmbFree, pEnumData, TRUE);
960 while (pmb)
961 {
962 pState->cBlocksFree++;
963 pmb = (PMEMBLOCK)AVLGetNextNode(pEnumData);
964 }
965
966 /* count of used blocks */
967 pmb = (PMEMBLOCK)AVLBeginEnumTree((PPAVLNODECORE)&pha->pmbUsed, pEnumData, TRUE);
968 while (pmb)
969 {
970 pState->cBlocksUsed++;
971 pmb = (PMEMBLOCK)AVLGetNextNode(pEnumData);
972 }
973
974 /* sizes */
975 pState->cbHeapSize += pha->cbSize;
976 pState->cbHeapFree += pha->cbFree;
977 pState->cbHeapUsed += pha->cbUsed;
978 }
979
980 return 0;
981}
982
983
984/**
985 * Checks heap integrety.
986 * @returns TRUE when ok.
987 * FALSE on error.
988 * NULL if out of memory. (Or memory to fragmented.)
989 */
990int _res_heap_check(void)
991{
992#ifdef DEBUG_ALLOC
993 PHEAPANCHOR pha = phaFirst;
994 PHEAPANCHOR phaPrev = NULL;
995
996
997 while (pha != NULL)
998 {
999 AVLENUMDATA FreeEnumData;
1000 AVLENUMDATA UsedEnumData;
1001 PMEMBLOCK pmbFree = (PMEMBLOCK)AVLBeginEnumTree((PPAVLNODECORE)&pha->pmbFree,
1002 SSToDS(&FreeEnumData), TRUE);
1003 PMEMBLOCK pmbFreeNext = (PMEMBLOCK)AVLGetNextNode(SSToDS(&FreeEnumData));
1004 PMEMBLOCK pmbUsed = (PMEMBLOCK)AVLBeginEnumTree((PPAVLNODECORE)&pha->pmbUsed,
1005 SSToDS(&UsedEnumData), TRUE);
1006 PMEMBLOCK pmbUsedNext = (PMEMBLOCK)AVLGetNextNode(SSToDS(&UsedEnumData));
1007 PMEMBLOCK pmbLast = NULL;
1008 unsigned cbFree = 0;
1009 unsigned cbUsed = 0;
1010 unsigned cbSize = sizeof(*pha);
1011
1012 /*
1013 * Check the heap anchor.
1014 */
1015 if (pha->ulSignature != HEAPANCHOR_SIGNATURE)
1016 {
1017 kprintf(("_res_heap_check: invalid signature for pha=0x%08x\n", pha));
1018 Int3();
1019 return FALSE;
1020 }
1021
1022 if (pha->cbFree + pha->cbUsed >= pha->cbSize || pha->cbSize == 0)
1023 {
1024 kprintf(("_res_heap_check: cbFree + cbUsed >= cbSize for pha=0x%08x\n", pha));
1025 Int3();
1026 return FALSE;
1027 }
1028
1029 if (pha->pPrev != phaPrev)
1030 {
1031 kprintf(("_res_heap_check: error in heap anchor chain.\n"));
1032 Int3();
1033 return FALSE;
1034 }
1035
1036 if ((unsigned)MINNOTNULL(pmbFree, pmbUsed) != (unsigned)(pha+1))
1037 {
1038 kprintf(("_res_heap_check: The first free/used block don't start at start of memory\n"
1039 " block. pmbFree=0x%08x, pmbUsed=0x%08x, pha+1=0x%08x\n",
1040 pmbFree, pmbUsed, pha+1));
1041 Int3();
1042 return FALSE;
1043 }
1044
1045 /*
1046 * Check the tree AVL-trees - !extra debug test!
1047 */
1048 if (resCheckAVLTree(pha->pmbUsed) != 0)
1049 {
1050 kprintf(("_res_heap_check: the Used tree is invalid.\n"));
1051 Int3();
1052 return FALSE;
1053 }
1054 if (resCheckAVLTree(pha->pmbFree) != 0)
1055 {
1056 kprintf(("_res_heap_check: the Free tree is invalid.\n"));
1057 Int3();
1058 return FALSE;
1059 }
1060 if (resCheckAVLTreeFree(pha->pcoreFreeSize) != 0)
1061 {
1062 kprintf(("_res_heap_check: the free-size tree is invalid.\n"));
1063 Int3();
1064 return FALSE;
1065 }
1066
1067 /*
1068 * Check the lists
1069 */
1070 while (pmbFree != NULL || pmbUsed != NULL)
1071 {
1072 /** @sketch:
1073 * Check signatures and for lost memory.
1074 *
1075 * three cases:
1076 * 1) pmbUsed adjecent to pmbUsed->pNext
1077 * 2) pmbUsed adjecent to pmbFree
1078 * 3) pmbFree adjecent to pmbFree->pNext
1079 * 4) pmbFree adjecent to pmbUsed
1080 * 5) pmbUsed is the last block
1081 * 6) pmbFree is the last block
1082 */
1083 if (!( (pmbUsed != NULL && PNEXT_BLOCK(pmbUsed) == pmbUsedNext) /* 1.*/
1084 || (pmbUsed != NULL && PNEXT_BLOCK(pmbUsed) == pmbFree) /* 2.*/
1085 || (pmbFree != NULL && PNEXT_BLOCK(pmbFree) == pmbFreeNext) /* 3.*/
1086 || (pmbFree != NULL && PNEXT_BLOCK(pmbFree) == pmbUsed) /* 4.*/
1087 || (pmbUsed != NULL && pmbFree == NULL && pmbUsedNext == NULL) /* 5.*/
1088 || (pmbFree != NULL && pmbUsed == NULL && pmbFreeNext == NULL) /* 6.*/
1089 )
1090 )
1091 {
1092 /* error hole */
1093 kprintf(("_res_heap_check: internal error - memory hole!\n"));
1094 Int3();
1095 return FALSE;
1096 }
1097
1098 /* check signature and advance to the next block */
1099 if (pmbUsed != NULL && (pmbFree == NULL || pmbUsed < pmbFree))
1100 {
1101 cbSize += CB_HDR + pmbUsed->cbSize;
1102 cbUsed += pmbUsed->cbSize;
1103 if (pmbUsed->ulSignature != MEMBLOCK_SIGNATURE)
1104 {
1105 kprintf(("_res_heap_check: invalid signature on used block, pmbUsed=0x%08x\n", pmbUsed));
1106 Int3();
1107 return FALSE;
1108 }
1109 if (pmbUsed->cbSize < sizeof(MEMBLOCKFREE) - CB_HDR)
1110 {
1111 kprintf(("_res_heap_check: internal error - cbSize is to small! (used), cbSize=%d\n", pmbUsed->cbSize));
1112 Int3();
1113 return FALSE;
1114 }
1115 pmbLast = pmbUsed;
1116 pmbUsed = pmbUsedNext;
1117 pmbUsedNext = (PMEMBLOCK)AVLGetNextNode(SSToDS(&UsedEnumData));
1118 }
1119 else
1120 {
1121 PMEMBLOCKFREE pmbf = (PMEMBLOCKFREE)AVLGet(&pha->pcoreFreeSize, pmbFree->cbSize);
1122 if (pmbf != NULL)
1123 {
1124 pmbf = MEMBLOCKFREE_FROM_FREESIZENODE(pmbf);
1125 while (pmbf != NULL && pmbf != (PMEMBLOCKFREE)pmbFree)
1126 pmbf = pmbf->pmbfNext;
1127 if (pmbf == NULL)
1128 {
1129 kprintf(("_res_heap_check: pmbFree=0x%08 is not found in the free-size-tree.\n", pmbFree));
1130 Int3();
1131 return FALSE;
1132 }
1133 }
1134 else
1135 {
1136 kprintf(("_res_heap_check: pmbFree=0x%08 is not found in the free-size-tree.\n", pmbFree));
1137 Int3();
1138 return FALSE;
1139 }
1140
1141 cbSize += CB_HDR + pmbFree->cbSize;
1142 cbFree += pmbFree->cbSize;
1143 if (pmbFree->ulSignature != MEMBLOCK_SIGNATURE)
1144 {
1145 kprintf(("_res_heap_check: invalid signature on free block, pmbUsed=0x%08x\n", pmbFree));
1146 Int3();
1147 return FALSE;
1148 }
1149 if (pmbFree->cbSize < sizeof(MEMBLOCKFREE) - CB_HDR)
1150 {
1151 kprintf(("_res_heap_check: internal error - cbSize is to small! (free), cbSize=%d\n", pmbFree->cbSize));
1152 Int3();
1153 return FALSE;
1154 }
1155 pmbLast = pmbFree;
1156 pmbFree = pmbFreeNext;
1157 pmbFreeNext = (PMEMBLOCK)AVLGetNextNode(SSToDS(&FreeEnumData));
1158 }
1159 }
1160
1161
1162 /*
1163 * Check the cbFree and cbUsed.
1164 */
1165 if (cbFree != pha->cbFree)
1166 {
1167 kprintf(("_res_heap_check: cbFree(%d) != pha->cbFree(%d)\n", cbFree, pha->cbFree));
1168 Int3();
1169 return FALSE;
1170 }
1171
1172 if (cbUsed != pha->cbUsed)
1173 {
1174 kprintf(("_res_heap_check: cbUsed(%d) != pha->cbUsed(%d)\n", cbUsed, pha->cbUsed));
1175 Int3();
1176 return FALSE;
1177 }
1178
1179 if (cbSize != pha->cbSize)
1180 {
1181 kprintf(("_res_heap_check: cbTotal(%d) != pha->cbSize(%d)\n", cbSize, pha->cbSize));
1182 Int3();
1183 return FALSE;
1184 }
1185 /*
1186 * Check right most node.
1187 */
1188 if (pmbLast == NULL || (unsigned)pha + pha->cbSize != (unsigned)PNEXT_BLOCK(pmbLast))
1189 {
1190 kprintf(("_res_heap_check: The last free/used block dont end at the end of memory block.\n"
1191 " pmbLast(end)=0x%08x, pha+pha->cbSize=0x%08x\n",
1192 pmbLast != NULL ? PNEXT_BLOCK(pmbLast) : NULL, (unsigned)pha + pha->cbSize));
1193 Int3();
1194 return FALSE;
1195 }
1196
1197
1198 /*
1199 * Next heap anchor
1200 */
1201 phaPrev = pha;
1202 pha = pha->pNext;
1203 }
1204
1205 /* check that end of chain is phaLast */
1206 if (phaPrev != phaLast)
1207 {
1208 kprintf(("_res_heap_check: internal error - heap anchor chain didn't end on phaLast\n"));
1209 Int3();
1210 return FALSE;
1211 }
1212
1213#endif
1214
1215 return TRUE;
1216}
1217
1218
1219#ifdef DEBUG_ALLOC
1220/**
1221 * Check the integrity of the a Free/Used AVL tree where Key == node pointer.
1222 */
1223static int resCheckAVLTree(PMEMBLOCK pmb)
1224{
1225 if (pmb == NULL)
1226 return 0;
1227 if (pmb->core.Key != (AVLKEY)pmb)
1228 {
1229 kprintf(("resCheckAVLTree: Invalid Key!\n"));
1230 Int3();
1231 return -1;
1232 }
1233 if (pmb->core.Key % ALIGNMENT != 0)
1234 {
1235 kprintf(("resCheckAVLTree: Data is not correctly aligned, uData=0x%08x\n", pmb->core.Key));
1236 Int3();
1237 return -1;
1238 }
1239 if (pmb->core.pLeft != NULL && (pmb->core.pLeft < (PAVLNODECORE)0x10000 || pmb->core.Key <= (AVLKEY)pmb->core.pLeft))
1240 {
1241 kprintf(("resCheckAVLTree: Invalid pLeft!\n"));
1242 Int3();
1243 return -1;
1244 }
1245 if (pmb->core.pRight != NULL && (pmb->core.pRight < (PAVLNODECORE)0x10000 || pmb->core.Key >= (AVLKEY)pmb->core.pRight))
1246 {
1247 kprintf(("resCheckAVLTree: Invalid pRight!\n"));
1248 Int3();
1249 return -1;
1250 }
1251 if (pmb->core.pLeft != NULL && resCheckAVLTree((PMEMBLOCK)pmb->core.pLeft) != 0)
1252 return -1;
1253 if (pmb->core.pRight != NULL && resCheckAVLTree((PMEMBLOCK)pmb->core.pRight) != 0)
1254 return -1;
1255 return 0;
1256}
1257
1258
1259/**
1260 * Check the integrity of the a Free/Used AVL tree where Key == node pointer.
1261 */
1262static int resCheckAVLTreeFree(PAVLNODECORE pNode)
1263{
1264 PMEMBLOCKFREE pmbf;
1265 if (pNode == NULL)
1266 return 0;
1267 if (pNode->Key < 4 || (pNode->Key % ALIGNMENT) != 0)
1268 {
1269 kprintf(("resCheckAVLTreeFree: Invalid Key! 0x%08x\n", pNode->Key));
1270 Int3();
1271 return -1;
1272 }
1273 if (pNode->pLeft != NULL && (pNode->pLeft < (PAVLNODECORE)0x10000 || pNode->Key <= pNode->pLeft->Key))
1274 {
1275 kprintf(("resCheckAVLTreeFree: Invalid pLeft!\n"));
1276 Int3();
1277 return -1;
1278 }
1279 if (pNode->pRight != NULL && (pNode->pRight < (PAVLNODECORE)0x10000 || pNode->Key >= pNode->pRight->Key))
1280 {
1281 kprintf(("resCheckAVLTreeFree: Invalid pRight!\n"));
1282 Int3();
1283 return -1;
1284 }
1285 pmbf = MEMBLOCKFREE_FROM_FREESIZENODE(pNode);
1286 if (pmbf->pmbfNext != NULL && pmbf->pmbfNext < (PMEMBLOCKFREE)0x10000)
1287 {
1288 kprintf(("resCheckAVLTreeFree: invalid pmbfNext pointer, pmbfNext=0x%08x\n", pmbf->pmbfNext));
1289 Int3();
1290 return -1;
1291 }
1292 while (pmbf->pmbfNext != NULL)
1293 {
1294 if (pmbf->pmbfNext < (PMEMBLOCKFREE)0x10000)
1295 {
1296 kprintf(("resCheckAVLTreeFree: invalid pmbfNext pointer, pmbfNext=0x%08x\n", pmbf->pmbfNext));
1297 Int3();
1298 return -1;
1299 }
1300 if (pmbf->coreFree.Key != pNode->Key)
1301 {
1302 kprintf(("resCheckAVLTreeFree: invalid key, pmbf->coreFree.Key=%d, pNode->Key=%d\n", pmbf->coreFree.Key, pNode->Key));
1303 Int3();
1304 return -1;
1305 }
1306 /* next */
1307 pmbf = pmbf->pmbfNext;
1308 }
1309
1310 if (pNode->pLeft != NULL && resCheckAVLTreeFree(pNode->pLeft) != 0)
1311 return -1;
1312 if (pNode->pRight != NULL && resCheckAVLTreeFree(pNode->pRight) != 0)
1313 return -1;
1314 return 0;
1315}
1316#endif
1317
1318
1319/**
1320 * Frees unused heapanchors.
1321 */
1322void _res_heapmin(void)
1323{
1324 PHEAPANCHOR pha = phaLast;
1325
1326 while (pha != NULL && pha != phaFirst)
1327 {
1328 if (pha->cbUsed == 0)
1329 {
1330 APIRET rc;
1331 PHEAPANCHOR phaToBeFreed = pha;
1332 if (pha->pPrev != NULL)
1333 pha->pPrev->pNext = pha->pNext;
1334 else
1335 phaFirst = pha->pPrev->pNext;
1336 if (pha->pNext != NULL)
1337 pha->pNext->pPrev = pha->pPrev;
1338 else
1339 phaLast = pha->pPrev;
1340 pha = pha->pPrev;
1341
1342 /* free heap */
1343 #ifdef RING0
1344 rc = D32Hlp_VMFree(phaToBeFreed);
1345 #else
1346 rc = DosFreeMem(phaToBeFreed);
1347 #endif
1348 if (rc != NO_ERROR)
1349 kprintf(("_res_heapmin: DosFreeMem/D32Help_VMFree failed for pha=0x%08x, rc = %d\n",
1350 pha, rc));
1351 }
1352 else
1353 pha = pha->pPrev;
1354 }
1355}
1356
1357
1358/**
1359 * Dumps a summary of the subheaps (heapanchor chain).
1360 */
1361void _res_dump_subheaps(void)
1362{
1363 PHEAPANCHOR pha;
1364 int i;
1365 unsigned cbTotalFree;
1366 unsigned cTotalFree;
1367 unsigned cbTotalUsed;
1368 unsigned cTotalUsed;
1369
1370 kprintf(("------------------------------------\n"
1371 "- Dumping subheap blocks (summary) -\n"
1372 "------------------------------------\n"
1373 ));
1374
1375 i = 0;
1376 cTotalFree = 0;
1377 cTotalUsed = 0;
1378 cbTotalFree = 0;
1379 cbTotalUsed = 0;
1380 pha = phaFirst;
1381 while (pha != NULL)
1382 {
1383 SUBHEAPS_CALLBACK_PARAM FreeParam = {0, 0};
1384 SUBHEAPS_CALLBACK_PARAM UsedParam = {0, 0};
1385
1386 AVLDoWithAll((PPAVLNODECORE)&pha->pmbUsed, 1,
1387 (PAVLCALLBACK)_res_dump_subheaps_callback, SSToDS(&UsedParam));
1388 AVLDoWithAll((PPAVLNODECORE)&pha->pmbFree, 1,
1389 (PAVLCALLBACK)_res_dump_subheaps_callback, SSToDS(&FreeParam));
1390
1391 kprintf(("HeapAnchor %2d addr=0x%08x cbSize=%6d cbFree=%6d cbUsed=%6d cUsed=%4d cFree=%d\n",
1392 i, pha, pha->cbSize, pha->cbFree, pha->cbUsed, UsedParam.c, FreeParam.c));
1393
1394 cTotalFree += FreeParam.c;
1395 cbTotalFree += FreeParam.cb;
1396 cTotalUsed += UsedParam.c;
1397 cbTotalUsed += UsedParam.cb;
1398
1399 /* next */
1400 pha = pha->pNext;
1401 i++;
1402 }
1403
1404 kprintf(("-----------------------------------------------------------------------------\n"
1405 " Free=%d #Free=%d AverageFree=%d Used=%d #Used=%d AverageUsed=%d\n"
1406 "-----------------------------------------------------------------------------\n",
1407 cbTotalFree, cTotalFree, cTotalFree > 0 ? cbTotalFree / cTotalFree : 0,
1408 cbTotalUsed, cTotalUsed, cTotalUsed > 0 ? cbTotalUsed / cTotalUsed : 0
1409 ));
1410}
1411
1412
1413
1414/**
1415 * Callbackfunction used by _res_dump_subheaps to summarize a tree.
1416 */
1417static unsigned _res_dump_subheaps_callback(PMEMBLOCK pmb, PSUBHEAPS_CALLBACK_PARAM pParam)
1418{
1419 pParam->cb += pmb->cbSize;
1420 pParam->c++;
1421 return 0;
1422}
1423
1424
1425/**
1426 * Dumps all allocated memory.
1427 */
1428void _res_dump_allocated(unsigned cb)
1429{
1430 PHEAPANCHOR pha;
1431 ALLOCATED_CALLBACK_PARAM Param = {cb, 0, 0};
1432
1433 kprintf(("----------------------------\n"
1434 "- Dumping allocated blocks -\n"
1435 "----------------------------\n"));
1436
1437 pha = phaFirst;
1438 while (pha != NULL)
1439 {
1440 /* iterate thru tree using callback */
1441 AVLDoWithAll((PPAVLNODECORE)&pha->pmbUsed, TRUE,
1442 (PAVLCALLBACK)_res_dump_allocated_callback, SSToDS(&Param));
1443
1444 /* next */
1445 pha = pha->pNext;
1446 }
1447
1448 kprintf((
1449 "---------------------------------------------\n"
1450 " #Blocks=%6d Allocated=%9d (bytes)\n"
1451 "---------------------------------------------\n",
1452 Param.cBlocks, Param.cbAllocated
1453 ));
1454}
1455
1456/**
1457 * Callback function which dumps a node, and update statistics.
1458 */
1459static unsigned _res_dump_allocated_callback(PMEMBLOCK pmb, PALLOCATED_CALLBACK_PARAM pParam)
1460{
1461 int i;
1462
1463 pParam->cBlocks++;
1464 pParam->cbAllocated += pmb->cbSize;
1465
1466 kprintf(("pvUserData=0x%08x cbSize=%6d\n",
1467 &pmb->achUserData[0], pmb->cbSize
1468 ));
1469 /* dump cb of the block */
1470 i = 0;
1471 while (i < pParam->cb)
1472 {
1473 int j;
1474
1475 /* hex */
1476 j = 0;
1477 while (j < 16)
1478 {
1479 if (j+i < pParam->cb && j+i < pmb->cbSize)
1480 kprintf((" %02x", pmb->achUserData[j+i]));
1481 else
1482 kprintf((" "));
1483 if (j == 7)
1484 kprintf((" -"));
1485 j++;
1486 }
1487
1488 /* ascii */
1489 j = 0;
1490 kprintf((" "));
1491 while (j < 16 && j+i < pmb->cbSize && j+i < pParam->cb)
1492 {
1493 kprintf(("%c", pmb->achUserData[j+i] < 0x20 ? '.' : pmb->achUserData[j+i]));
1494 j++;
1495 }
1496 kprintf(("\n"));
1497 i += j;
1498 }
1499
1500 return 0;
1501}
1502
Note: See TracBrowser for help on using the repository browser.