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

Last change on this file was 2511, checked in by bird, 26 years ago

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