1 /***************************************************************
2 ** Memory allocator for systems that don't have real one.
3 ** This might be useful when bringing up a new computer with no OS.
5 ** For PForth based on 'C'
8 ** Copyright 1994 3DO, Phil Burk, Larry Polansky, David Rosenboom
10 ** Permission to use, copy, modify, and/or distribute this
11 ** software for any purpose with or without fee is hereby granted.
13 ** THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
14 ** WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
15 ** WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL
16 ** THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
17 ** CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING
18 ** FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF
19 ** CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
20 ** OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
22 ****************************************************************
24 ***************************************************************/
31 static char *gMemPoolPtr;
32 static ucell_t gMemPoolSize;
34 /* CUSTOM: Make the memory pool bigger if you want. */
35 #ifndef PF_MEM_POOL_SIZE
36 #define PF_MEM_POOL_SIZE (0x100000)
39 #define PF_MEM_BLOCK_SIZE (16)
41 #ifndef PF_MALLOC_ADDRESS
42 static char MemoryPool[PF_MEM_POOL_SIZE];
43 #define PF_MALLOC_ADDRESS MemoryPool
46 /**********************************************************
47 ** Doubly Linked List Tools
48 **********************************************************/
50 typedef struct DoublyLinkedListNode_s
52 struct DoublyLinkedListNode_s *dlln_Next;
53 struct DoublyLinkedListNode_s *dlln_Previous;
54 } DoublyLinkedListNode;
56 typedef struct DoublyLinkedList_s
58 DoublyLinkedListNode *dll_First;
59 DoublyLinkedListNode *dll_Null;
60 DoublyLinkedListNode *dll_Last;
63 #define dllPreviousNode(n) ((n)->dlln_Previous)
64 #define dllNextNode(n) ((n)->dlln_Next)
66 void dllSetupList( DoublyLinkedList *dll )
68 dll->dll_First = &(dll->dll_Null);
69 dll->dll_Null = (DoublyLinkedListNode *) NULL;
70 dll->dll_Last = &(dll->dll_First);
73 void dllLinkNodes( DoublyLinkedListNode *Node0, DoublyLinkedListNode *Node1 )
75 Node0->dlln_Next = Node1;
76 Node1->dlln_Previous = Node0;
79 void dllInsertNodeBefore( DoublyLinkedListNode *NewNodePtr,
80 DoublyLinkedListNode *NodeInListPtr )
82 DoublyLinkedListNode *NodePreviousPtr = dllPreviousNode( NodeInListPtr );
83 dllLinkNodes( NodePreviousPtr, NewNodePtr );
84 dllLinkNodes( NewNodePtr, NodeInListPtr );
87 void dllInsertNodeAfter( DoublyLinkedListNode *NewNodePtr,
88 DoublyLinkedListNode *NodeInListPtr )
90 DoublyLinkedListNode *NodeNextPtr = dllNextNode( NodeInListPtr );
91 dllLinkNodes( NodeInListPtr, NewNodePtr );
92 dllLinkNodes( NewNodePtr, NodeNextPtr );
95 void dllDumpNode( DoublyLinkedListNode *NodePtr )
98 DBUG((" 0x%x -> (0x%x) -> 0x%x\n",
99 dllPreviousNode( NodePtr ), NodePtr,
100 dllNextNode( NodePtr ) ));
103 cell_t dllCheckNode( DoublyLinkedListNode *NodePtr )
105 if( (NodePtr->dlln_Next->dlln_Previous != NodePtr) ||
106 (NodePtr->dlln_Previous->dlln_Next != NodePtr))
108 ERR("dllCheckNode: Bad Node!\n");
109 dllDumpNode( dllPreviousNode( NodePtr ) );
110 dllDumpNode( NodePtr );
111 dllDumpNode( dllNextNode( NodePtr ) );
119 void dllRemoveNode( DoublyLinkedListNode *NodePtr )
121 if( dllCheckNode( NodePtr ) == 0 )
123 dllLinkNodes( dllPreviousNode( NodePtr ), dllNextNode( NodePtr ) );
127 void dllAddNodeToHead( DoublyLinkedList *ListPtr, DoublyLinkedListNode *NewNodePtr )
129 dllInsertNodeBefore( NewNodePtr, ListPtr->dll_First );
132 void dllAddNodeToTail( DoublyLinkedList *ListPtr, DoublyLinkedListNode *NewNodePtr )
134 dllInsertNodeAfter( NewNodePtr, ListPtr->dll_Last );
137 #define dllIsNodeInList( n ) (!((n)->dlln_Next == NULL) )
138 #define dllIsLastNode( n ) ((n)->dlln_Next->dll_nNext == NULL )
139 #define dllIsListEmpty( l ) ((l)->dll_First == ((DoublyLinkedListNode *) &((l)->dll_Null)) )
140 #define dllFirstNode( l ) ((l)->dll_First)
142 static DoublyLinkedList gMemList;
144 typedef struct MemListNode
146 DoublyLinkedListNode mln_Node;
151 /***************************************************************
154 void maDumpList( void )
158 MSG("PForth MemList\n");
160 for( mln = (MemListNode *) dllFirstNode( &gMemList );
161 dllIsNodeInList( (DoublyLinkedListNode *) mln);
162 mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) )
164 MSG(" Node at = 0x"); ffDotHex(mln);
165 MSG_NUM_H(", size = 0x", mln->mln_Size);
171 /***************************************************************
172 ** Free mem of any size.
174 static void pfFreeRawMem( char *Mem, cell_t NumBytes )
176 MemListNode *mln, *FreeNode;
177 MemListNode *AdjacentLower = NULL;
178 MemListNode *AdjacentHigher = NULL;
179 MemListNode *NextBiggest = NULL;
181 /* Allocate in whole blocks of 16 bytes */
182 DBUG(("\npfFreeRawMem( 0x%x, 0x%x )\n", Mem, NumBytes ));
183 NumBytes = (NumBytes + PF_MEM_BLOCK_SIZE - 1) & ~(PF_MEM_BLOCK_SIZE - 1);
184 DBUG(("\npfFreeRawMem: Align NumBytes to 0x%x\n", NumBytes ));
186 /* Check memory alignment. */
187 if( ( ((cell_t)Mem) & (PF_MEM_BLOCK_SIZE - 1)) != 0)
189 MSG_NUM_H("pfFreeRawMem: misaligned Mem = 0x", (cell_t) Mem );
193 /* Scan list from low to high looking for various nodes. */
194 for( mln = (MemListNode *) dllFirstNode( &gMemList );
195 dllIsNodeInList( (DoublyLinkedListNode *) mln);
196 mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) )
198 if( (((char *) mln) + mln->mln_Size) == Mem )
202 else if( ((char *) mln) == ( Mem + NumBytes ))
204 AdjacentHigher = mln;
206 /* is this the next biggest node. */
207 else if( (NextBiggest == NULL) && (mln->mln_Size >= NumBytes) )
213 /* Check to see if we can merge nodes. */
216 DBUG((" Merge (0x%x) -> 0x%x\n", Mem, AdjacentHigher ));
217 NumBytes += AdjacentHigher->mln_Size;
218 dllRemoveNode( (DoublyLinkedListNode *) AdjacentHigher );
222 DBUG((" Merge 0x%x -> (0x%x)\n", AdjacentLower, Mem ));
223 AdjacentLower->mln_Size += NumBytes;
227 DBUG((" Link before 0x%x\n", NextBiggest ));
228 FreeNode = (MemListNode *) Mem;
229 FreeNode->mln_Size = NumBytes;
230 if( NextBiggest == NULL )
232 /* Nothing bigger so add to end of list. */
233 dllAddNodeToTail( &gMemList, (DoublyLinkedListNode *) FreeNode );
237 /* Add this node before the next biggest one we found. */
238 dllInsertNodeBefore( (DoublyLinkedListNode *) FreeNode,
239 (DoublyLinkedListNode *) NextBiggest );
248 /***************************************************************
249 ** Setup memory list. Initialize allocator.
251 static void pfInitMemBlock( void *addr, ucell_t poolSize )
256 pfDebugMessage("pfInitMemBlock()\n");
259 gMemPoolSize = poolSize;
261 dllSetupList( &gMemList );
263 /* Adjust to next highest aligned memory location. */
264 AlignedMemory = (char *) ((((cell_t)gMemPoolPtr) + PF_MEM_BLOCK_SIZE - 1) &
265 ~(PF_MEM_BLOCK_SIZE - 1));
267 /* Adjust size to reflect aligned memory. */
268 AlignedSize = gMemPoolSize - (AlignedMemory - gMemPoolPtr);
270 /* Align size of pool. */
271 AlignedSize = AlignedSize & ~(PF_MEM_BLOCK_SIZE - 1);
274 pfFreeRawMem( AlignedMemory, AlignedSize );
278 /***************************************************************
279 ** Allocate mem from list of free nodes.
281 static char *pfAllocRawMem( cell_t NumBytes )
285 pfDebugMessage("pfAllocRawMem()\n");
287 if( NumBytes <= 0 ) return NULL;
289 /* Allocate in whole blocks of 16 bytes */
290 NumBytes = (NumBytes + PF_MEM_BLOCK_SIZE - 1) & ~(PF_MEM_BLOCK_SIZE - 1);
292 DBUG(("\npfAllocRawMem( 0x%x )\n", NumBytes ));
294 /* Scan list from low to high until we find a node big enough. */
295 for( mln = (MemListNode *) dllFirstNode( &gMemList );
296 dllIsNodeInList( (DoublyLinkedListNode *) mln);
297 mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) )
299 if( mln->mln_Size >= NumBytes )
305 /* Remove this node from list. */
306 dllRemoveNode( (DoublyLinkedListNode *) mln );
308 /* Is there enough left in block to make it worth splitting? */
309 RemSize = mln->mln_Size - NumBytes;
310 if( RemSize >= PF_MEM_BLOCK_SIZE )
312 pfFreeRawMem( (Mem + NumBytes), RemSize );
319 DBUG(("Allocate mem at 0x%x.\n", Mem ));
323 /***************************************************************
324 ** Keep mem size at first cell.
326 char *pfAllocMem( cell_t NumBytes )
330 if( NumBytes <= 0 ) return NULL;
332 /* Allocate an extra cell for size. */
333 NumBytes += sizeof(cell_t);
335 IntMem = (cell_t *)pfAllocRawMem( NumBytes );
337 if( IntMem != NULL ) *IntMem++ = NumBytes;
339 return (char *) IntMem;
342 /***************************************************************
343 ** Free mem with mem size at first cell.
345 void pfFreeMem( void *Mem )
350 if( Mem == NULL ) return;
352 /* Allocate an extra cell for size. */
353 IntMem = (cell_t *) Mem;
357 pfFreeRawMem( (char *) IntMem, NumBytes );
361 void pfInitMemoryAllocator( void )
363 pfInitMemBlock( PF_MALLOC_ADDRESS, PF_MEM_POOL_SIZE );
365 #else /* PF_NO_MALLOC */
367 int not_an_empty_file; /* Stops nasty compiler warnings when PF_NO_MALLOC not defined. */
369 #endif /* PF_NO_MALLOC */