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

Last change on this file since 1508 was 1467, checked in by bird, 26 years ago

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