Context Navigation

source: GPL/branches/uniaud32-2.1.x/lib32/malloc.cpp@ 504

Last change on this file since 504 was 504, checked in by David Azarewicz, 15 years ago
Bring branch up-to-date with trunk
File size: 20.7 KB

Line
1	/* $Id: malloc.cpp,v 1.1.1.1 2003/07/02 13:57:02 eleph Exp $ */
2
3	/* SCCSID = %W% %E% */
4	/****************************************************************************
5	* *
6	* Copyright (c) IBM Corporation 1994 - 1997. *
7	* *
8	* The following IBM OS/2 source code is provided to you solely for the *
9	* the purpose of assisting you in your development of OS/2 device drivers. *
10	* You may use this code in accordance with the IBM License Agreement *
11	* provided in the IBM Device Driver Source Kit for OS/2. *
12	* *
13	****************************************************************************/
14	/**@internal %W%
15	* Implementation of the driver's built in memory management.
16	* @version %I%
17	* @context
18	* Unless otherwise noted, all interfaces are Ring-3 and Ring-0, 16-bit,
19	* kernel stack.
20	* @notes
21	* @history
22	* 01-Jul-95 Timur Tabi Creation
23	*/
24
25	#include <os2.h>
26	#include <string.h> // memcpy(), memset()
27	#include <stdio.h>
28	#include <dbgos2.h>
29
30	#include <devhelp.h>
31	#ifdef KEE
32	#include <kee.h>
33	#endif
34	#include "malloc.h"
35
36	#if !defined(min)
37	#define min(a,b) (((a) < (b)) ? (a) : (b))
38	#endif
39
40	#define SIGNATURE 0xBEEFDEAD // "DeadBeef" when view in hex in word order.
41
42	#pragma pack(4)
43	typedef struct _MEMBLOCK {
44	ULONG ulSignature;
45	ULONG ulSize;
46	struct _MEMBLOCK NEAR *pmbNext;
47	#ifdef DEBUGHEAP
48	char NEAR *pszFile;
49	ULONG ulLine;
50	#endif
51	char achBlock[4];
52	} MEMBLOCK, NEAR *PMEMBLOCK;
53	#pragma pack()
54
55	#define HDR_SIZE ( sizeof(MEMBLOCK) - 4 )
56
57	// We won't leave a hole in memory any smaller than MIN_FragSize.
58	#define MIN_FragSize 4
59
60	//--- Global Variables used to manage the heap:
61	//
62	PMEMBLOCK pmbUsed = 0; // Points to head of list of allocated memory blocks.
63	// Newly allocated blocks are inserted into head of list.
64	PMEMBLOCK pmbFree = 0; // Points to head of list of available memory blocks.
65	unsigned uMemFree = 0; // N bytes available for allocation.
66	LINEAR acHeap = NULL;
67
68	ULONG ulnAlloc = 0; // Current number of allocated blocks.
69	ULONG ulcAlloc = 0; // Total memory in allocated blocks incl. headers.
70	ULONG ulnAllocCalls = 0; // Cumulative total, number of malloc() calls.
71	ULONG ulnFree = 0; // Current number of free blocks.
72	ULONG ulcFree = 0; // Total memory in free blocks incl. headers.
73	ULONG ulnFreeCalls = 0; // Cumulative total, number of free() calls.
74	ULONG ulnCompact = 0; // Num of times we've joined two adjacent free
75	// blocks into a single larger block.
76	ULONG ulcTotalHeap = HEAP_SIZE;
77
78
79	#pragma off (unreferenced)
80
81	//--- Heap methods:
82
83	//*****************************************************************************
84	//*****************************************************************************
85	void dumpheap(void)
86	{
87	SHORT sI;
88	PMEMBLOCK pmb;
89	ULONG ulSize;
90
91	ulSize = 0;
92	pmb=pmbUsed;
93	dprintf(("HEAP:Heap Dump acHeap=%lx Used=%p Free=%p\n", (void __far *)acHeap, pmbUsed, pmbFree));
94	dprintf((" Used blocks\n"));
95	for (sI=0; sI<10; sI++) {
96	dprintf((" pmb=%p, length=%lx\n",(void __far *) pmb, pmb->ulSize));
97	ulSize+=pmb->ulSize;
98	pmb=pmb->pmbNext;
99	if (!pmb) break;
100	}
101	dprintf((" Total used = %lx\n", ulSize));
102
103	ulSize=0;
104	pmb=pmbFree;
105	dprintf((" Free blocks\n"));
106	for (sI=0; sI<50; sI++) {
107	dprintf((" pmb=%p, length=%lx\n",(void __far *) pmb, pmb->ulSize));
108	ulSize+=pmb->ulSize;
109	pmb=pmb->pmbNext;
110	if (!pmb) break;
111	}
112	dprintf((" Total free = %lx\n", ulSize));
113	}
114	//*****************************************************************************
115	//*****************************************************************************
116
117	//*****************************************************************************
118	//*****************************************************************************
119	SHORT SignatureCheck ( PMEMBLOCK p, PSZ idText )
120	{
121	short sGoodPointer;
122
123	// Set bGoodPointer to indicate whether or not 'p' points within heap.
124	sGoodPointer = ((LINEAR)p >= (acHeap))
125	&& ((LINEAR)p <= (( acHeap) + HEAP_SIZE)) ;
126	//### heap might have less than HEAP_SIZE bytes
127
128	// Check for correct signature.
129	if (sGoodPointer) sGoodPointer = (p->ulSignature == SIGNATURE) && p->ulSize < HEAP_SIZE;
130
131	if (!sGoodPointer) {
132	dprintf(("SignatureCheck: Bad pointer %p %s\n", p, idText));
133	DebugInt3();
134	}
135	return sGoodPointer;
136	}
137	//*****************************************************************************
138	//*****************************************************************************
139	void HeapCheck ( PSZ idText )
140	{
141	PMEMBLOCK p;
142	for ( ulnAlloc = 0, ulcAlloc = 0, p = pmbUsed; p; p = p->pmbNext ) {
143	++ulnAlloc;
144	ulcAlloc += p->ulSize + HDR_SIZE;
145	SignatureCheck( p,(PSZ) "HeapCheck() Used list" );
146	if (p == p->pmbNext) {
147	dprintf(("HeapCheck: used %p points to itself\n", p));
148	DebugInt3();
149	}
150	}
151	for ( ulnFree = 0, ulcFree = 0, p = pmbFree; p; p = p->pmbNext ) {
152	++ulnFree;
153	ulcFree += p->ulSize + HDR_SIZE;
154	SignatureCheck( p,(PSZ) "HeapCheck() Free list" );
155	if (p == p->pmbNext) {
156	dprintf(("HeapCheck: free %p points to itself\n", p));
157	DebugInt3();
158	}
159	}
160	if (ulcAlloc + ulcFree != ulcTotalHeap) {
161	dprintf(("HeapCheck: Alloc+Free != Total\n"));
162	//dumpheap();
163	DebugInt3();
164	}
165	}
166
167	//*****************************************************************************
168	//*****************************************************************************
169
170	// Threshold for creating a new free block.
171	#define MIN_Leftover (HDR_SIZE + MIN_FragSize)
172
173	/*
174	Formats the back part of an existing free MEMBLOCK as a new, smaller
175	"Free" MEMBLOCK. Doesn't update Global vbls (caller responsibility).
176	IN: pmbOldFree - pointer to existing memory block.
177	uSize - offset, which won't be included in new allocation.
178	it's assumed HDR is not included in uSize.
179	OUT: pointer to new free MEMBLOCK, is a new block of free memory,
180	is created at pmbOldFree + uRequest. The memory block header
181	in both the new block and the old block are properly initialized
182	on return, but we don't update the Free list or Allocated list.
183	OUT: NULL if the new free memory block is smaller than the
184	framentation threshold.
185
186	The fragmentation consideration comes into play when we find a block that's
187	big enough to hold the requested memory, but not big enough for the leftover
188	part to be useful as another free block.
189
190	_______________________free block_______________________________________
191	\| free \| \|
192	\| block \| space available \|
193	\| header \| (pmbFree->uSize bytes long) \|
194	\|(HDR_SIZE \| \|
195	\|__bytes)__\|_____________________________________________________________\|
196
197	<-- HDR --> <------------------------- l -------------------------------->
198
199	Must either be allocated in total, or must become:
200
201	_______________________used block_______________________________________
202	\| used \| \| free \| \|
203	\| block \| space allocated \| block \| space \|
204	\| header \| == uSize (following DWORD align't) \| header \| available \|
205	\|(HDR_SIZE \| (pmbUsed->uSize bytes long) \|(HDR_SIZE \| \|
206	\|__bytes)__\|_____________________________________\|__bytes)__\|____________\|
207
208	<-- HDR --> <-------------- n ------------------><-- HDR --> <--- m ----->
209
210	To be split into an allocated and a new, smaller free block, 'm' must be at
211	least MIN_FragSize bytes long.
212
213	Everything should remain 4 byte aligned since the HDR_SIZE, MIN_FragSize,
214	and the space allocated (after we munge it) are all multiples of 4.
215
216	This means that in order for a free block to be chosen, one of the following
217	equation must hold
218
219	Case 1: n <= l < (n + HDR + MIN_FragSize)
220	Here, we'll allocate the entire block. This makes the block somewhat
221	larger than the request, but prevents some degree of fragmentation.
222
223	Case 2: (n + HDR + MIN_FragSize) <= l
224	We split the block into an allocated part to satisfy the allocation request,
225	and a free block which can be allocated in a subsequent request.
226
227	@internal pmbAllocateBlock
228	* Update all data structures for allocation of one memory block. It's
229	* assumed, on entry, that the block is large enough for the requested
230	* allocation.
231	* @param PMEMBLOCK pmb - the current memory block on the Free list to
232	* allocate.
233	* @param USHORT uRequest - size of the memory request to fill, not counting
234	* memory block header.
235	* @param PMEMBLOCK pmbPrev - the memory block which precedes the block being
236	* allocated in the Free list. NULL if no predecessor (ie, pmb is pointed to
237	* by ::pmbFree).
238	* @return PMEMBLOCK - pointer to the data part of the allocated memory block,
239	* suitable for return to malloc() caller.
240	*/
241	void NEAR *npvAllocateBlock( PMEMBLOCK pmb, ULONG ulRequest, PMEMBLOCK pmbPrev )
242	{
243
244	//pmb points to the selected block.
245	//pmbPrev points to the block prior to the selected block, NULL if pmbFree.
246	PMEMBLOCK pmbOldNext; // Original free block that follows the block being allocated.
247	PMEMBLOCK pmbNewFree; // Leftover free memory from the allocated block.
248
249	// Split this block into an allocated + free part if it's big enough.
250	pmbNewFree = 0;
251	if (pmb->ulSize >= (ulRequest + MIN_Leftover)) {
252	// We've got enough leftover to make a new free block.
253
254	/* create the new free block */
255	pmbNewFree = (PMEMBLOCK) ((char __near *) pmb + HDR_SIZE + ulRequest );
256	pmbNewFree->ulSignature = SIGNATURE;
257	pmbNewFree->ulSize = pmb->ulSize - (ulRequest + HDR_SIZE);
258	pmbNewFree->pmbNext = pmb->pmbNext;
259
260	// Update the size of the original free block that was passed in.
261	pmb->ulSize -= (pmbNewFree->ulSize + HDR_SIZE);
262	}
263
264	// Update global memory counter.
265	uMemFree -= (pmb->ulSize + HDR_SIZE);
266
267	// Add this block into the front of the Allocated list.
268	pmbOldNext = pmb->pmbNext;
269	pmb->pmbNext = pmbUsed;
270	pmbUsed = pmb;
271
272	// Remove the new allocation from the Free list.
273	if (pmbNewFree) { // If we split off a new free block
274	pmbNewFree->pmbNext = pmbOldNext; // If we're not at head of Free list
275	if (pmbPrev) pmbPrev->pmbNext = pmbNewFree;
276	else pmbFree = pmbNewFree;
277	} else { // We allocated the entire free block.
278	if (pmbPrev) pmbPrev->pmbNext = pmbOldNext; // If we're not at head of Free list
279	else pmbFree = pmbOldNext;
280	}
281
282	return (void NEAR *) pmb->achBlock;
283	}
284
285
286	/* malloc()
287	This function searches the list of free blocks until it finds one big enough
288	to hold the amount of memory requested, which is passed in uSize. The uSize
289	request is sized up for:
290	- a memory block header
291	- four byte alignment
292	- minimum fragmentation
293
294	See helper function make_new_free() for discussion of fragmentation handling.
295	*/
296
297	#ifdef DEBUGHEAP
298	void NEAR malloc(ULONG ulSize, const char filename, int lineno)
299	#else
300	void NEAR *malloc( ULONG ulSize )
301	#endif
302	{
303	ULONG ulRequest; // Request size after alignment.
304	PMEMBLOCK pmb, pmbPrev; // Use to walk free lists.
305	void NEAR *npvReturn; // Return value.
306	ULONG ulCpuFlags;
307
308	//dprintf(("malloc(). size: %d", ulSize));
309	if(acHeap == NULL) return 0;
310	if (!ulSize \|\| ulSize > HEAP_SIZE) {
311	DebugInt3();
312	return 0;
313	}
314
315	ulCpuFlags = DevPushfCli();
316	npvReturn = 0;
317	++ulnAllocCalls; // Diagnostics.
318	HeapCheck((PSZ) "malloc() entry" );
319
320	ulRequest = (ulSize + 3) & -4; // Force DWORD alignment.
321
322	for (pmbPrev=NULL, pmb=pmbFree; pmb; pmbPrev=pmb, pmb=pmb->pmbNext) {
323	if (pmb->ulSize >= ulRequest) {
324	npvReturn = npvAllocateBlock(pmb, ulRequest, pmbPrev);
325	break;
326	}
327	}
328
329	if (npvReturn) {
330	#ifdef DEBUGHEAP
331	PMEMBLOCK pBlock = (PMEMBLOCK) (((PUCHAR) npvReturn) - HDR_SIZE);
332
333	pBlock->pszFile = (char *)filename;
334	pBlock->ulLine = lineno;
335	#endif
336	SignatureCheck( (PMEMBLOCK) (((PUCHAR) npvReturn) - HDR_SIZE), (PSZ) "malloc() exit, allocated block" );
337	} else {
338	dprintf(("malloc(): out of memory"));
339	DebugInt3();
340	}
341
342	HeapCheck((PSZ) "malloc() exit" );
343	DevPopf(ulCpuFlags);
344	return npvReturn;
345	}
346
347	/* void compact(void)
348	This function compacts the free blocks together. This function is a
349	companion to free(), and thus the algorithm is tailored to how free()
350	works. Change the algorithm in free(), and you'll have to change this
351	function too.
352
353	When free() frees a block, it sets the head of the free list, pmbFree, to
354	point to it. Then the newly freed block points to whatever the old pmbFree
355	pointed to. In other words, each new free block is added to the head of
356	the free list.
357
358	If compact() is always called after a block is freed, then it can be
359	guaranteed that the free list is always compacted (i.e. you won't find
360	two adjacent free blocks anywhere in the heap) _before_ each call to free().
361	Therefore, the newly freed block can be located in only one of the
362	following positions:
363	1. Not adjacent to any other free blocks (compacting not necessary)
364	2. Physically before another free block
365	3. Physically after another free block
366	4. Between two free blocks (i.e. the block occupies the entire space
367	between two free blocks)
368
369	Since the newly freed block is the first in the free list, compact()
370	starts with the second block in the list (i.e. pmbFree->pmbNext).
371	Each free block is then compared with the newly freed block for
372	adjacency. If a given block is located before the new block, then it
373	can't possibly be also located after, and vice versa. Hence, the
374	"else if" statement in the middle of the loop.
375
376	Also, the newly freed block can only be adjacent to at most two other
377	blocks. Therefore, the operation of combining two adjacent free blocks can
378	only happen at most twice. The variable ulnFreed counts the number of times
379	two blocks are combined. The function exits if ulnFreed reaches two. ulnFreed
380	is initially 0.
381
382	Helper macro after() takes a PMEMBLOCK (call it pmb) as a parameter,
383	and calculates where an adjacent free block would exist if it were
384	physically located after pmb.
385
386	Helper function remove() removes an element from the free list.
387	*/
388
389	#define after(pmb) ((PMEMBLOCK) ((char *) pmb + pmb->ulSize + HDR_SIZE))
390
391	void remove(PMEMBLOCK pmb)
392	{
393	PMEMBLOCK pmbPrev;
394
395	if (pmb == pmbFree) {
396	pmbFree = pmbFree->pmbNext;
397	return;
398	}
399
400	for (pmbPrev=pmbFree; pmbPrev; pmbPrev=pmbPrev->pmbNext) {
401	if (pmbPrev->pmbNext == pmb) {
402	pmbPrev->pmbNext = pmb->pmbNext;
403	return;
404	}
405	}
406	}
407	//*****************************************************************************
408	//*****************************************************************************
409	void compact(void)
410	{
411	PMEMBLOCK pmb;
412	SHORT sFreed;
413
414	sFreed = 0;
415	for (pmb=pmbFree->pmbNext; pmb; pmb=pmb->pmbNext) {
416	if (after(pmb) == pmbFree) {
417	// ddprintf("HEAP: compact found pointer %p (size=%ui) before pmbFree %p\n", (void __far ) pmb, pmb->uSize, (void __far ) pmbFree);
418	pmb->ulSize += HDR_SIZE + pmbFree->ulSize;
419	remove(pmbFree);
420	if (++sFreed == 2) break;
421	} else if (after(pmbFree) == pmb) {
422	// ddprintf("HEAP: compact found pointer %p (size=%ui) after pmbFree %p\n", (void __far ) pmb, pmb->uSize, (void __far ) pmbFree);
423	pmbFree->ulSize += HDR_SIZE + pmb->ulSize;
424	remove(pmb);
425	if (++sFreed == 2) break;
426	}
427	}
428
429	ulnCompact += sFreed;
430	}
431	//*****************************************************************************
432	//*****************************************************************************
433	#ifdef DEBUGHEAP
434	void free(void NEAR pvBlock, const char filename, int lineno)
435	#else
436	void free(void NEAR *pvBlock)
437	#endif
438	{
439	PMEMBLOCK pmb,pmbPrev,pmbBlock;
440	ULONG ulCpuFlags;
441
442	if(acHeap == NULL) {
443	DebugInt3();
444	return;
445	}
446
447	++ulnFreeCalls;
448	if (!pvBlock) return; // support freeing of NULL
449
450	ulCpuFlags = DevPushfCli();
451	pmbBlock=(PMEMBLOCK) ((char NEAR *) pvBlock - HDR_SIZE);
452
453	SignatureCheck( pmbBlock,(PSZ) "free() entry, Block to be freed" );
454	HeapCheck((PSZ) "free() entry" );
455
456	uMemFree += pmbBlock->ulSize + HDR_SIZE;
457
458	/* find the block on the used chain */
459	for (pmbPrev=NULL, pmb=pmbUsed; pmb; pmbPrev=pmb, pmb=pmb->pmbNext) {
460	if (pmb == pmbBlock) { /* found the block */
461	if (pmbPrev) { /* it is in the middle of the chain */
462	pmbPrev->pmbNext = pmb->pmbNext; /* delete this block from the chain */
463	} else { /* it is the first block on the used list */
464	pmbUsed = pmbUsed->pmbNext; // the 2nd block is now the head
465	}
466	pmbBlock->pmbNext = pmbFree; /* This block is now free, so it points to the first free block */
467	pmbFree = pmbBlock; /* This is now the first free block */
468	break;
469	}
470	}
471	if (pmb == 0) {
472	dprintf(("free: block not found %x\n", pmb));
473	DebugInt3();
474	}
475	compact();
476
477	HeapCheck((PSZ) "free() exit" );
478	DevPopf(ulCpuFlags);
479	}
480	//*****************************************************************************
481	//*****************************************************************************
482	unsigned _memfree(void)
483	{
484	return uMemFree;
485	}
486	//*****************************************************************************
487	//*****************************************************************************
488	/**@internal _msize
489	*/
490	unsigned _msize(void NEAR *pvBlock)
491	{
492	PMEMBLOCK pmb;
493
494	if (!pvBlock)
495	return 0;
496
497	pmb = (PMEMBLOCK) ((char NEAR *) pvBlock - HDR_SIZE);
498
499	return pmb->ulSize;
500	}
501
502
503	#ifdef DEBUGHEAP
504	void NEAR realloc(void NEAR pvBlock, ULONG ulLength, const char *filename, int lineno)
505	#else
506	void NEAR realloc(void NEAR pvBlock, ULONG ulLength)
507	#endif
508	{
509	void NEAR *pv;
510
511	if (!pvBlock) // if ptr is null, alloc block
512	#ifdef DEBUGHEAP
513	return malloc(ulLength, filename, lineno);
514	#else
515	return malloc(ulLength);
516	#endif
517
518	if (!ulLength) { // if length is 0, free block
519	#ifdef DEBUGHEAP
520	free(pvBlock, filename, lineno);
521	#else
522	free(pvBlock);
523	#endif
524	return 0;
525	}
526
527	#ifdef DEBUGHEAP
528	pv = malloc(ulLength, filename, lineno); // attempt to allocate the new block
529	#else
530	pv = malloc(ulLength); // attempt to allocate the new block
531	#endif
532	if (!pv) // can't do it?
533	return 0; // just fail. Version 2 will try harder
534
535	memcpy(pv, pvBlock, min( _msize(pvBlock), ulLength));
536
537	#ifdef DEBUGHEAP
538	free(pvBlock, filename, lineno);
539	#else
540	free(pvBlock);
541	#endif
542	return pv;
543	}
544	//*****************************************************************************
545	//*****************************************************************************
546	BOOL IsHeapAddr(ULONG addr)
547	{
548	int bGoodPointer;
549
550	bGoodPointer = ((LINEAR)addr >= acHeap)
551	&& ((LINEAR)addr <= (acHeap + HEAP_SIZE)) ;
552
553	return bGoodPointer;
554	}
555	//*****************************************************************************
556	extern "C" APIRET VMAlloc(ULONG size, ULONG flags, LINEAR *pAddr) ;
557	//*****************************************************************************
558	ULONG HeapInit(ULONG ulSize)
559	{
560	LINEAR addr;
561	SHORT sel;
562
563	if (!ulSize) ulSize = DEFAULT_HEAP;
564
565	if (ulSize > HEAP_SIZE) ulSize = HEAP_SIZE;
566
567	if(VMAlloc(ulSize, VMDHA_FIXED, &addr)) {
568	DebugInt3();
569	return 0;
570	}
571	acHeap = addr;
572	//dprintf(("HeapInit(): addr: %x", acHeap));
573
574	pmbFree = (PMEMBLOCK) acHeap;
575	pmbFree->ulSize = ulSize - HDR_SIZE;
576	pmbFree->ulSignature = SIGNATURE;
577	pmbFree->pmbNext = 0;
578	uMemFree = pmbFree->ulSize;
579	return pmbFree->ulSize;
580	}
581	//*****************************************************************************
582	//*****************************************************************************

Note: See TracBrowser for help on using the repository browser.

Download in other formats: