1 /***************************************************************
\r
2 ** Memory allocator for systems that don't have real one.
\r
3 ** This might be useful when bringing up a new computer with no OS.
\r
5 ** For PForth based on 'C'
\r
8 ** Copyright 1994 3DO, Phil Burk, Larry Polansky, David Rosenboom
\r
10 ** The pForth software code is dedicated to the public domain,
\r
11 ** and any third party may reproduce, distribute and modify
\r
12 ** the pForth software code or any derivative works thereof
\r
13 ** without any compensation or license. The pForth software
\r
14 ** code is provided on an "as is" basis without any warranty
\r
15 ** of any kind, including, without limitation, the implied
\r
16 ** warranties of merchantability and fitness for a particular
\r
17 ** purpose and their equivalents under the laws of any jurisdiction.
\r
19 ****************************************************************
\r
21 ***************************************************************/
\r
28 static char *gMemPoolPtr;
\r
29 static uint32 gMemPoolSize;
\r
31 /* CUSTOM: Make the memory pool bigger if you want. */
\r
32 #ifndef PF_MEM_POOL_SIZE
\r
33 #define PF_MEM_POOL_SIZE (0x100000)
\r
36 #define PF_MEM_BLOCK_SIZE (16)
\r
38 #ifndef PF_MALLOC_ADDRESS
\r
39 static char MemoryPool[PF_MEM_POOL_SIZE];
\r
40 #define PF_MALLOC_ADDRESS MemoryPool
\r
43 /**********************************************************
\r
44 ** Doubly Linked List Tools
\r
45 **********************************************************/
\r
47 typedef struct DoublyLinkedListNode_s
\r
49 struct DoublyLinkedListNode_s *dlln_Next;
\r
50 struct DoublyLinkedListNode_s *dlln_Previous;
\r
51 } DoublyLinkedListNode;
\r
53 typedef struct DoublyLinkedList_s
\r
55 DoublyLinkedListNode *dll_First;
\r
56 DoublyLinkedListNode *dll_Null;
\r
57 DoublyLinkedListNode *dll_Last;
\r
60 #define dllPreviousNode(n) ((n)->dlln_Previous)
\r
61 #define dllNextNode(n) ((n)->dlln_Next)
\r
63 void dllSetupList( DoublyLinkedList *dll )
\r
65 dll->dll_First = &(dll->dll_Null);
\r
66 dll->dll_Null = (DoublyLinkedListNode *) NULL;
\r
67 dll->dll_Last = &(dll->dll_First);
\r
70 void dllLinkNodes( DoublyLinkedListNode *Node0, DoublyLinkedListNode *Node1 )
\r
72 Node0->dlln_Next = Node1;
\r
73 Node1->dlln_Previous = Node0;
\r
76 void dllInsertNodeBefore( DoublyLinkedListNode *NewNodePtr,
\r
77 DoublyLinkedListNode *NodeInListPtr )
\r
79 DoublyLinkedListNode *NodePreviousPtr = dllPreviousNode( NodeInListPtr );
\r
80 dllLinkNodes( NodePreviousPtr, NewNodePtr );
\r
81 dllLinkNodes( NewNodePtr, NodeInListPtr );
\r
84 void dllInsertNodeAfter( DoublyLinkedListNode *NewNodePtr,
\r
85 DoublyLinkedListNode *NodeInListPtr )
\r
87 DoublyLinkedListNode *NodeNextPtr = dllNextNode( NodeInListPtr );
\r
88 dllLinkNodes( NodeInListPtr, NewNodePtr );
\r
89 dllLinkNodes( NewNodePtr, NodeNextPtr );
\r
92 void dllDumpNode( DoublyLinkedListNode *NodePtr )
\r
95 DBUG((" 0x%x -> (0x%x) -> 0x%x\n",
\r
96 dllPreviousNode( NodePtr ), NodePtr,
\r
97 dllNextNode( NodePtr ) ));
\r
100 int32 dllCheckNode( DoublyLinkedListNode *NodePtr )
\r
102 if( (NodePtr->dlln_Next->dlln_Previous != NodePtr) ||
\r
103 (NodePtr->dlln_Previous->dlln_Next != NodePtr))
\r
105 ERR("dllCheckNode: Bad Node!\n");
\r
106 dllDumpNode( dllPreviousNode( NodePtr ) );
\r
107 dllDumpNode( NodePtr );
\r
108 dllDumpNode( dllNextNode( NodePtr ) );
\r
116 void dllRemoveNode( DoublyLinkedListNode *NodePtr )
\r
118 if( dllCheckNode( NodePtr ) == 0 )
\r
120 dllLinkNodes( dllPreviousNode( NodePtr ), dllNextNode( NodePtr ) );
\r
124 void dllAddNodeToHead( DoublyLinkedList *ListPtr, DoublyLinkedListNode *NewNodePtr )
\r
126 dllInsertNodeBefore( NewNodePtr, ListPtr->dll_First );
\r
129 void dllAddNodeToTail( DoublyLinkedList *ListPtr, DoublyLinkedListNode *NewNodePtr )
\r
131 dllInsertNodeAfter( NewNodePtr, ListPtr->dll_Last );
\r
134 #define dllIsNodeInList( n ) (!((n)->dlln_Next == NULL) )
\r
135 #define dllIsLastNode( n ) ((n)->dlln_Next->dll_nNext == NULL )
\r
136 #define dllIsListEmpty( l ) ((l)->dll_First == ((DoublyLinkedListNode *) &((l)->dll_Null)) )
\r
137 #define dllFirstNode( l ) ((l)->dll_First)
\r
139 static DoublyLinkedList gMemList;
\r
141 typedef struct MemListNode
\r
143 DoublyLinkedListNode mln_Node;
\r
148 /***************************************************************
\r
149 ** Dump memory list.
\r
151 void maDumpList( void )
\r
155 MSG("PForth MemList\n");
\r
157 for( mln = (MemListNode *) dllFirstNode( &gMemList );
\r
158 dllIsNodeInList( (DoublyLinkedListNode *) mln);
\r
159 mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) )
\r
161 MSG(" Node at = 0x"); ffDotHex(mln);
\r
162 MSG_NUM_H(", size = 0x", mln->mln_Size);
\r
168 /***************************************************************
\r
169 ** Free mem of any size.
\r
171 static void pfFreeRawMem( char *Mem, int32 NumBytes )
\r
173 MemListNode *mln, *FreeNode;
\r
174 MemListNode *AdjacentLower = NULL;
\r
175 MemListNode *AdjacentHigher = NULL;
\r
176 MemListNode *NextBiggest = NULL;
\r
178 /* Allocate in whole blocks of 16 bytes */
\r
179 DBUG(("\npfFreeRawMem( 0x%x, 0x%x )\n", Mem, NumBytes ));
\r
180 NumBytes = (NumBytes + PF_MEM_BLOCK_SIZE - 1) & ~(PF_MEM_BLOCK_SIZE - 1);
\r
181 DBUG(("\npfFreeRawMem: Align NumBytes to 0x%x\n", NumBytes ));
\r
183 /* Check memory alignment. */
\r
184 if( ( ((int32)Mem) & (PF_MEM_BLOCK_SIZE - 1)) != 0)
\r
186 MSG_NUM_H("pfFreeRawMem: misaligned Mem = 0x", (int32) Mem );
\r
190 /* Scan list from low to high looking for various nodes. */
\r
191 for( mln = (MemListNode *) dllFirstNode( &gMemList );
\r
192 dllIsNodeInList( (DoublyLinkedListNode *) mln);
\r
193 mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) )
\r
195 if( (((char *) mln) + mln->mln_Size) == Mem )
\r
197 AdjacentLower = mln;
\r
199 else if( ((char *) mln) == ( Mem + NumBytes ))
\r
201 AdjacentHigher = mln;
\r
203 /* is this the next biggest node. */
\r
204 else if( (NextBiggest == NULL) && (mln->mln_Size >= NumBytes) )
\r
210 /* Check to see if we can merge nodes. */
\r
211 if( AdjacentHigher )
\r
213 DBUG((" Merge (0x%x) -> 0x%x\n", Mem, AdjacentHigher ));
\r
214 NumBytes += AdjacentHigher->mln_Size;
\r
215 dllRemoveNode( (DoublyLinkedListNode *) AdjacentHigher );
\r
217 if( AdjacentLower )
\r
219 DBUG((" Merge 0x%x -> (0x%x)\n", AdjacentLower, Mem ));
\r
220 AdjacentLower->mln_Size += NumBytes;
\r
224 DBUG((" Link before 0x%x\n", NextBiggest ));
\r
225 FreeNode = (MemListNode *) Mem;
\r
226 FreeNode->mln_Size = NumBytes;
\r
227 if( NextBiggest == NULL )
\r
229 /* Nothing bigger so add to end of list. */
\r
230 dllAddNodeToTail( &gMemList, (DoublyLinkedListNode *) FreeNode );
\r
234 /* Add this node before the next biggest one we found. */
\r
235 dllInsertNodeBefore( (DoublyLinkedListNode *) FreeNode,
\r
236 (DoublyLinkedListNode *) NextBiggest );
\r
240 /* maDumpList(); */
\r
245 /***************************************************************
\r
246 ** Setup memory list. Initialize allocator.
\r
248 static void pfInitMemBlock( void *addr, uint32 poolSize )
\r
250 char *AlignedMemory;
\r
253 pfDebugMessage("pfInitMemBlock()\n");
\r
255 gMemPoolPtr = addr;
\r
256 gMemPoolSize = poolSize;
\r
258 dllSetupList( &gMemList );
\r
260 /* Adjust to next highest aligned memory location. */
\r
261 AlignedMemory = (char *) ((((int32)gMemPoolPtr) + PF_MEM_BLOCK_SIZE - 1) &
\r
262 ~(PF_MEM_BLOCK_SIZE - 1));
\r
264 /* Adjust size to reflect aligned memory. */
\r
265 AlignedSize = gMemPoolSize - (AlignedMemory - gMemPoolPtr);
\r
267 /* Align size of pool. */
\r
268 AlignedSize = AlignedSize & ~(PF_MEM_BLOCK_SIZE - 1);
\r
270 /* Free to pool. */
\r
271 pfFreeRawMem( AlignedMemory, AlignedSize );
\r
275 /***************************************************************
\r
276 ** Allocate mem from list of free nodes.
\r
278 static char *pfAllocRawMem( int32 NumBytes )
\r
282 pfDebugMessage("pfAllocRawMem()\n");
\r
284 if( NumBytes <= 0 ) return NULL;
\r
286 /* Allocate in whole blocks of 16 bytes */
\r
287 NumBytes = (NumBytes + PF_MEM_BLOCK_SIZE - 1) & ~(PF_MEM_BLOCK_SIZE - 1);
\r
289 DBUG(("\npfAllocRawMem( 0x%x )\n", NumBytes ));
\r
291 /* Scan list from low to high until we find a node big enough. */
\r
292 for( mln = (MemListNode *) dllFirstNode( &gMemList );
\r
293 dllIsNodeInList( (DoublyLinkedListNode *) mln);
\r
294 mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) )
\r
296 if( mln->mln_Size >= NumBytes )
\r
300 Mem = (char *) mln;
\r
302 /* Remove this node from list. */
\r
303 dllRemoveNode( (DoublyLinkedListNode *) mln );
\r
305 /* Is there enough left in block to make it worth splitting? */
\r
306 RemSize = mln->mln_Size - NumBytes;
\r
307 if( RemSize >= PF_MEM_BLOCK_SIZE )
\r
309 pfFreeRawMem( (Mem + NumBytes), RemSize );
\r
315 /* maDumpList(); */
\r
316 DBUG(("Allocate mem at 0x%x.\n", Mem ));
\r
320 /***************************************************************
\r
321 ** Keep mem size at first cell.
\r
323 char *pfAllocMem( int32 NumBytes )
\r
327 if( NumBytes <= 0 ) return NULL;
\r
329 /* Allocate an extra cell for size. */
\r
330 NumBytes += sizeof(int32);
\r
332 IntMem = (int32 *)pfAllocRawMem( NumBytes );
\r
334 if( IntMem != NULL ) *IntMem++ = NumBytes;
\r
336 return (char *) IntMem;
\r
339 /***************************************************************
\r
340 ** Free mem with mem size at first cell.
\r
342 void pfFreeMem( void *Mem )
\r
347 if( Mem == NULL ) return;
\r
349 /* Allocate an extra cell for size. */
\r
350 IntMem = (int32 *) Mem;
\r
352 NumBytes = *IntMem;
\r
354 pfFreeRawMem( (char *) IntMem, NumBytes );
\r
358 void pfInitMemoryAllocator( void )
\r
360 pfInitMemBlock( PF_MALLOC_ADDRESS, PF_MEM_POOL_SIZE );
\r
362 #else /* PF_NO_MALLOC */
\r
364 int not_an_empty_file; /* Stops nasty compiler warnings when PF_NO_MALLOC not defined. */
\r
366 #endif /* PF_NO_MALLOC */
\r