source: trunk/src/win32k/misc/malloc.c@ 1122

Last change on this file since 1122 was 847, checked in by bird, 26 years ago

Initial checkin of Win32k. (not tested & pe2lx not up-to-date!)
File size: 16.3 KB
Line 
1/* $Id: malloc.c,v 1.1 1999-09-06 02:20:02 bird Exp $
2 *
3 * Heap.
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 knut st. osmundsen
9 *
10 */
11
12
13/******************************************************************************
14* Defined macros and constants
15******************************************************************************/
16#ifdef DEBUG
17 #define DEBUG_ALLOC
18#endif
19
20#define SIGNATURE 0xBEEFFEEB
21#define CB_HDR (sizeof(MEMBLOCK) - 1) /* size of MEMBLOCK header (in bytes) */
22#define PNEXT_BLOCK(a) ((PMEMBLOCK)((unsigned)(a) + CB_HDR + (a)->cbSize))
23
24#define INCL_DOS
25#define INCL_DOSERRORS
26#ifdef RING0
27#define INCL_NOAPI
28#else
29#define INCL_DOSMEMMGR
30#endif
31
32/******************************************************************************
33* Headerfiles
34******************************************************************************/
35#include <os2.h>
36
37#include "log.h"
38#include "dev32hlp.h"
39#include "asmutils.h"
40#include "malloc.h"
41#include "memory.h"
42
43
44/******************************************************************************
45* Structs and Typedefs
46******************************************************************************/
47typedef struct _MEMBLOCK /* MB */
48{
49#ifdef DEBUG_ALLOC
50 unsigned long ulSignature; /* should be SIGNATURE (0xBEEFFEEB) */
51#endif
52 unsigned cbSize; /* size of user space (achBlock)*/
53 struct _MEMBLOCK *pNext;
54 unsigned char achUserData[1];
55} MEMBLOCK, *PMEMBLOCK;
56
57
58/******************************************************************************
59* Global data
60******************************************************************************/
61static PMEMBLOCK pUsed; /* pointer to the used memblock chain. */
62static PMEMBLOCK pFree; /* pointer to the free memblock chain. */
63static unsigned cbFree; /* bytes of free user memory in the heap.*/
64unsigned _uHeapMinPtr; /* heap pointers are greater or equal to this.*/
65unsigned _uHeapMaxPtr; /* heap pointers are less than this. */
66
67/******************************************************************************
68* Internal functions
69******************************************************************************/
70static void insertUsed(PMEMBLOCK pMemblock);
71static void insertFree(PMEMBLOCK pMemblock);
72static PMEMBLOCK getFreeMemblock(unsigned cbUserSize);
73static PMEMBLOCK findBlock(PMEMBLOCK pMemblock, void *pvUser, int fWithin);
74
75
76/**
77 * Inserts a memblock into the used chain
78 * @param pMemblock Pointer to memblock which is to inserted.
79 * @remark Sorts on address.
80 */
81static void insertUsed(PMEMBLOCK pMemblock)
82{
83 if (pUsed == NULL || pUsed > pMemblock)
84 {
85 pMemblock->pNext = pUsed;
86 pUsed = pMemblock;
87 }
88 else
89 {
90 PMEMBLOCK pMb = pUsed;
91 while (pMb->pNext != NULL && pMb->pNext < pMemblock)
92 pMb = pMb->pNext;
93
94 pMemblock->pNext = pMb->pNext;
95 pMb->pNext= pMemblock;
96 }
97}
98
99
100/**
101 * Inserts a memblock into the free chain.
102 * Merges blocks adjecent blocks.
103 * @param pMemblock Pointer to memblock to insert into the free list.
104 * @remark Sorts on address.
105 */
106static void insertFree(PMEMBLOCK pMemblock)
107{
108 cbFree += pMemblock->cbSize;
109 if (pMemblock < pFree || pFree == NULL)
110 {
111 /* test for merge with 2nd block */
112 if (pFree != NULL && PNEXT_BLOCK(pMemblock) == pFree)
113 {
114 cbFree += pMemblock->cbSize + CB_HDR;
115 pFree->cbSize += CB_HDR;
116 #ifdef DEBUG_ALLOC
117 pMemblock->ulSignature = 0xF0EEEE0F;
118 #endif
119 }
120 else
121 {
122 pMemblock->pNext = pFree;
123 pFree = pMemblock;
124
125 }
126 }
127 else
128 {
129 PMEMBLOCK pMb = pFree;
130 while (pMb->pNext != NULL && pMb->pNext < pMemblock)
131 pMb = pMb->pNext;
132
133 /* test for merge with left block */
134 if (PNEXT_BLOCK(pMb) == pMemblock)
135 {
136 pMb->cbSize += CB_HDR + pMemblock->cbSize;
137 cbFree += CB_HDR;
138 #ifdef DEBUG_ALLOC
139 pMemblock->ulSignature = 0xF0EEEE0F;
140 #endif
141 pMemblock = pMb;
142 }
143 else
144 {
145 pMemblock->pNext = pMb->pNext;
146 pMb->pNext = pMemblock;
147 }
148
149 /* test for merge with right block */
150 if (PNEXT_BLOCK(pMemblock) == pMemblock->pNext && pMemblock->pNext != NULL)
151 {
152 pMemblock->cbSize += CB_HDR + pMemblock->pNext->cbSize;
153 cbFree += CB_HDR;
154 #ifdef DEBUG_ALLOC
155 pMemblock->pNext->ulSignature = 0xF0EEEE0F;
156 #endif
157 pMemblock->pNext = pMemblock->pNext->pNext;
158 }
159 }
160}
161
162
163/**
164 * Finds a free block at the requested size.
165 * @returns Pointer to block (not in free list any longer).
166 * @param cbUserSize Bytes the user have requested.
167 * @sketch cbUserSize is aligned to nearest 4 bytes.
168 *
169 *
170 */
171static PMEMBLOCK getFreeMemblock(unsigned cbUserSize)
172{
173 PMEMBLOCK pBestFit = NULL;
174 PMEMBLOCK pBestFitPrev = NULL;
175 PMEMBLOCK pCur = pFree;
176 PMEMBLOCK pPrev = NULL;
177
178 cbUserSize = (cbUserSize + 3) & ~3;
179
180 /* search for block */
181 while (pCur != NULL)
182 {
183 /* check for perfect match first */
184 if (pCur->cbSize == cbUserSize)
185 break;
186 /* TODO: The following test may need to be adjusted later. */
187 else if (pCur->cbSize >= cbUserSize
188 && (pBestFit == NULL || pCur->cbSize < pBestFit->cbSize)
189 )
190 {
191 pBestFit = pCur;
192 pBestFitPrev = pPrev;
193 }
194
195 /* next */
196 pPrev = pCur;
197 pCur = pCur->pNext;
198 }
199
200 /* link out block */
201 if (pCur != NULL)
202 { /* prefect match */
203 if (pPrev != NULL)
204 pPrev->pNext = pCur->pNext;
205 else
206 pFree = pCur->pNext;
207
208 cbFree -= cbUserSize;
209 }
210 else if (pBestFit != NULL)
211 { /* best fit */
212 /* two cases 1) split block. 2) block is too small to be splitted. */
213 if (pBestFit->cbSize > cbUserSize + CB_HDR)
214 {
215 pCur = (PMEMBLOCK)((unsigned)pBestFit + pBestFit->cbSize - cbUserSize);
216 #ifdef DEBUG_ALLOC
217 pCur->ulSignature = SIGNATURE;
218 #endif
219 pCur->cbSize = cbUserSize;
220 pBestFit->cbSize -= cbUserSize + CB_HDR;
221
222 cbFree -= cbUserSize + CB_HDR;
223 }
224 else
225 {
226 if (pBestFitPrev != NULL)
227 pBestFitPrev->pNext = pBestFit->pNext;
228 else
229 pFree = pBestFit->pNext;
230 pCur = pBestFit;
231
232 cbFree -= pCur->cbSize;
233 }
234 }
235
236 return pCur;
237}
238
239
240/**
241 * Finds a memory block starting the search at pMemblock.
242 * @returns Pointer to memblock if found.
243 * @param pMemblock Start node.
244 * @param pvUser User pointer to find the block to.
245 * @param fWithin When this flag is set, the pointer may point anywhere within the block.
246 */
247static PMEMBLOCK findBlock(PMEMBLOCK pMemblock, void *pvUser, int fWithin)
248{
249 if (pvUser != NULL && pMemblock != NULL)
250 {
251 if (fWithin)
252 while (pMemblock != NULL &&
253 !(pvUser >= (void*)pMemblock && pvUser < (void*)PNEXT_BLOCK(pMemblock))
254 )
255 pMemblock = pMemblock->pNext;
256 else
257 {
258 pvUser = (void*)((unsigned)pvUser - CB_HDR);
259 while (pMemblock != NULL && pvUser != (void*)pMemblock)
260 pMemblock = pMemblock->pNext;
261 }
262 }
263 else
264 pMemblock = NULL;
265
266 return pMemblock;
267}
268
269
270/**
271 * Initiate the heap "subsystem".
272 * @returns 0 on success, not 0 on error.
273 * @param cbSize Heapsize in bytes.
274 */
275int heapInit(unsigned cbSize)
276{
277 pUsed = NULL;
278
279 #if RING0
280 pFree = D32Hlp_VMAlloc(VMDHA_SWAP | VMDHA_USEHIGHMEM, cbSize, ~0UL);
281 #else
282 if (DosAllocMem(&pFree, cbSize, PAG_COMMIT | PAG_READ | PAG_WRITE) != 0)
283 pFree = NULL
284 #endif
285 if (pFree == NULL)
286 {
287 kprintf(("unable to allocate heap memory.\n"));
288 Int3();
289 return -1;
290 }
291
292 #ifdef DEBUG_ALLOC
293 pFree->ulSignature = SIGNATURE;
294 #endif
295 pFree->cbSize = cbSize - CB_HDR;
296 pFree->pNext = NULL;
297 cbFree = pFree->cbSize;
298
299 _uHeapMinPtr = (unsigned)pFree + CB_HDR;
300 _uHeapMaxPtr = (unsigned)pFree + cbSize;
301
302 #ifdef DEBUG_ALLOC
303 if (!_heap_check())
304 {
305 /* error! */
306 kprintf(("%s: _heap_check failed!\n", "heapInit"));
307 Int3();
308 return -2;
309 }
310 #endif
311 return 0;
312}
313
314
315/**
316 * malloc - allocates a given amount of memory.
317 * @returns Pointer to allocated memory.
318 * NULL if out of memory. (Or memory to fragmented.)
319 * @param cbSize Bytes user requests us to allocate. This is aligned
320 * to four bytes.
321 */
322void * malloc(unsigned cbSize)
323{
324 void *pvRet = NULL;
325 #ifdef DEBUG_ALLOC
326 if (!_heap_check())
327 {
328 kprintf(("%s: _heap_check failed!\n", "malloc"));
329 return NULL;
330 }
331 #endif
332
333 if (cbSize != 0)
334 {
335 PMEMBLOCK pMemblock = getFreeMemblock(cbSize);
336 if (pMemblock != NULL)
337 {
338 insertUsed(pMemblock);
339 pvRet = &pMemblock->achUserData[0];
340 }
341 }
342 else
343 {
344 /* error! */
345 kprintf(("%s: error cbSize = 0\n", "malloc"));
346 }
347
348 return pvRet;
349}
350
351
352/**
353 * Reallocate a heapblock.
354 * @returns Pointer to new heapblock.
355 * @param pv Pointer to the block to realloc.
356 * @param cbNew The new block size.
357 */
358void *realloc(void *pv, unsigned cbNew)
359{
360 PMEMBLOCK pMemblock;
361 pMemblock = findBlock(pUsed, pv, FALSE);
362 if (pMemblock != NULL)
363 {
364 void *pvRet;
365
366 cbNew = (cbNew + 3) & ~3;
367 if (cbNew <= pMemblock->cbSize)
368 { /* shrink block */
369 pvRet = pv;
370 if (cbNew + CB_HDR < pMemblock->cbSize)
371 { /* split block */
372 PMEMBLOCK pNewBlock = (PMEMBLOCK)((unsigned)pMemblock + CB_HDR + cbNew);
373 #ifdef DEBUG_ALLOC
374 pNewBlock->ulSignature = SIGNATURE;
375 #endif
376 pNewBlock->cbSize = pMemblock->cbSize - cbNew - CB_HDR;
377 pNewBlock->pNext = NULL;
378 pMemblock->cbSize = cbNew;
379 insertFree(pNewBlock);
380 }
381 }
382 else
383 { /* expand block */
384 pvRet = malloc(cbNew);
385 if (pvRet != NULL)
386 memcpy(pvRet, pv, pMemblock->cbSize);
387 }
388
389 }
390 return NULL;
391}
392
393
394/**
395 * Frees a block.
396 * @param pv User pointer.
397 */
398void free(void *pv)
399{
400 #ifdef DEBUG_ALLOC
401 if (!_heap_check())
402 {
403 kprintf(("free: _heap_check failed!\n"));
404 return;
405 }
406 #endif
407
408 if (pv != NULL)
409 {
410 PMEMBLOCK pCur = pUsed;
411 PMEMBLOCK pPrev = NULL;
412 pv = (void*)((int)pv - CB_HDR);
413
414 while (pCur != NULL &&
415 #ifdef DEBUG_ALLOC /* pointer within block */
416 !(pv >= (void*)pCur && (void*)((unsigned)pv + CB_HDR) < (void*)PNEXT_BLOCK(pCur))
417 #else
418 pv != (void*)pCur
419 #endif
420 )
421 {
422 pPrev = pCur;
423 pCur = pCur->pNext;
424 }
425
426 if (pCur != NULL)
427 {
428 if (pv == pCur)
429 {
430 if (pPrev != NULL)
431 pPrev->pNext = pCur->pNext;
432 else
433 pUsed = pCur->pNext;
434
435 insertFree(pCur);
436
437 #ifdef DEBUG_ALLOC
438 if (!_heap_check())
439 kprintf(("%s: _heap_check failed 3!\n", "free"));
440 #endif
441 }
442 else
443 kprintf(("free: pv is not pointing to start of block.\n"));
444 }
445 else
446 kprintf(("free: heap block not found!\n"));
447 }
448 else
449 kprintf(("free: Free received a NULL pointer!\n"));
450}
451
452
453/**
454 * Gets the size of a block.
455 * @returns Bytes in a block.
456 */
457unsigned _msize(void *pv)
458{
459 PMEMBLOCK pBlock;
460 #ifdef DEBUG_ALLOC
461 if (!_heap_check())
462 kprintf(("_msize: _heap_check failed!\n"));
463 #endif
464 pBlock = findBlock(pUsed, pv, FALSE);
465 return pBlock != NULL ? pBlock->cbSize : 0;
466}
467
468
469/**
470 * Checks if pv is a valid heappointer.
471 * @returns 1 if valid. 0 if invalid.
472 * @param pv User data pointer.
473 */
474int _validptr(void *pv)
475{
476 PMEMBLOCK pBlock;
477
478 #ifdef DEBUG_ALLOC
479 if (!_heap_check())
480 kprintf(("_validptr: _heap_check failed!\n"));
481 #endif
482
483 pBlock = findBlock(pUsed, pv, TRUE);
484 return pBlock != NULL;
485}
486
487
488/**
489 * Checks that the dataaera made up by pv and cbSize valid with in the heap.
490 * @returns 1 if valid. 0 if invalid.
491 * @param pv User data pointer.
492 * @param cbSize Size of data which has to be valid.
493 */
494int _validptr2(void *pv, unsigned cbSize)
495{
496 PMEMBLOCK pBlock;
497
498 #ifdef DEBUG_ALLOC
499 if (!_heap_check())
500 kprintf(("_validptr: _heap_check failed!\n"));
501 #endif
502
503 pBlock = findBlock(pUsed, pv, TRUE);
504 return pBlock != NULL ? (pBlock->cbSize - ((unsigned)pv - (unsigned)pBlock - CB_HDR)) >= cbSize : FALSE;
505}
506
507
508/**
509 * Get amount of free memory (in bytes)
510 * @returns Amount of free memory (in bytes).
511 * @remark Note that this amount is of all free memory blocks and
512 * that these blocks are fragmented.
513 * You'll probably not be able to allocate a single block
514 * of the returned size.
515 */
516unsigned _memfree(void)
517{
518 #ifdef DEBUG_ALLOC
519 if (!_heap_check())
520 kprintf(("_memfree: _heap_check failed!\n"));
521 #endif
522 return cbFree;
523}
524
525
526/**
527 * Checks heap integrety.
528 * @returns TRUE when ok.
529 * FALSE on error.
530 * NULL if out of memory. (Or memory to fragmented.)
531 */
532int _heap_check(void)
533{
534 #ifdef DEBUG_ALLOC
535 PMEMBLOCK pCurFree = pFree;
536 PMEMBLOCK pCurUsed = pUsed;
537
538 while (pCurFree != NULL || pCurUsed != NULL)
539 {
540 /** @sketch:
541 * check signatures and for lost memory.
542 *
543 * three cases:
544 * 1) pCurUsed adjecent to pCurUsed->pNext
545 * 2) pCurUsed adjecent to pCurFree
546 * 3) pCurFree adjecent to pCurFree->pNext
547 * 4) pCurFree adjecent to pCurUsed
548 * 5) pCurUsed is the last block
549 * 6) pCurFree is the last block
550 */
551 #if 0
552 if (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurUsed->pNext) /* 1.*/
553 ;
554 else if (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurFree) /* 2.*/
555 ;
556 else if (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurFree->pNext) /* 3.*/
557 ;
558 else if (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurUsed) /* 4.*/
559 ;
560 else if (pCurUsed != NULL && pCurFree == NULL && pCurUsed->pNext == NULL) /* 5.*/
561 ;
562 else if (pCurFree != NULL && pCurUsed == NULL && pCurFree->pNext == NULL) /* 6.*/
563 ;
564 else
565 #else
566 if (!( (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurUsed->pNext) /* 1.*/
567 || (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurFree) /* 2.*/
568 || (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurFree->pNext) /* 3.*/
569 || (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurUsed) /* 4.*/
570 || (pCurUsed != NULL && pCurFree == NULL && pCurUsed->pNext == NULL) /* 5.*/
571 || (pCurFree != NULL && pCurUsed == NULL && pCurFree->pNext == NULL) /* 6.*/
572 )
573 )
574 #endif
575 {
576 /* error hole */
577 kprintf(("_heap_check: internal error - memory hole!\n"));
578 return FALSE;
579 }
580
581 /* check signature and advance to the next block */
582 if (pCurUsed != NULL && (pCurFree == NULL || pCurUsed < pCurFree))
583 {
584 if (pCurUsed->ulSignature != SIGNATURE)
585 return FALSE;
586 pCurUsed = pCurUsed->pNext;
587 }
588 else
589 {
590 if (pCurFree->ulSignature != SIGNATURE)
591 return FALSE;
592 pCurFree = pCurFree->pNext;
593 }
594 }
595 #endif
596 return TRUE;
597}
598
599
Note: See TracBrowser for help on using the repository browser.