git.gag.com Git - debian/pforth/blob - csrc/pf_mem.c

   1 /* @(#) pf_mem.c 98/01/26 1.3 */
   2 /***************************************************************
   3 ** Memory allocator for systems that don't have real one.
   4 ** This might be useful when bringing up a new computer with no OS.
   5 **
   6 ** For PForth based on 'C'
   7 **
   8 ** Author: Phil Burk
   9 ** Copyright 1994 3DO, Phil Burk, Larry Polansky, Devid Rosenboom
  10 **
  11 ** The pForth software code is dedicated to the public domain,
  12 ** and any third party may reproduce, distribute and modify
  13 ** the pForth software code or any derivative works thereof
  14 ** without any compensation or license.  The pForth software
  15 ** code is provided on an "as is" basis without any warranty
  16 ** of any kind, including, without limitation, the implied
  17 ** warranties of merchantability and fitness for a particular
  18 ** purpose and their equivalents under the laws of any jurisdiction.
  19 **
  20 ****************************************************************
  21 **
  22 ***************************************************************/
  23
  24 #include "pf_all.h"
  25
  26
  27 #ifdef PF_NO_MALLOC
  28
  29 static char  *gMemPoolPtr;
  30 static uint32 gMemPoolSize;
  31
  32 /* CUSTOM: Make the memory pool bigger if you want. */
  33 #ifndef PF_MEM_POOL_SIZE
  34         #define PF_MEM_POOL_SIZE (0x100000)
  35 #endif
  36
  37 #define PF_MEM_BLOCK_SIZE (16)
  38
  39 #ifndef PF_MALLOC_ADDRESS
  40         static char MemoryPool[PF_MEM_POOL_SIZE];
  41         #define PF_MALLOC_ADDRESS MemoryPool
  42 #endif
  43
  44 /**********************************************************
  45 ** Doubly Linked List Tools
  46 **********************************************************/
  47
  48 typedef struct DoublyLinkedListNode
  49 {
  50         struct DoublyLinkedListNode *dlln_Next;
  51         struct DoublyLinkedListNode *dlln_Previous;
  52 } DoublyLinkedListNode;
  53
  54 typedef struct DoublyLinkedList
  55 {
  56         struct DoublyLinkedListNode *dll_First;
  57         struct DoublyLinkedListNode *dll_Null;
  58         struct DoublyLinkedListNode *dll_Last;
  59 } DoublyLinkedList;
  60
  61 #define dllPreviousNode(n) ((n)->dlln_Previous)
  62 #define dllNextNode(n) ((n)->dlln_Next)
  63
  64 void dllSetupList( DoublyLinkedList *dll )
  65 {
  66         dll->dll_First = (DoublyLinkedListNode *) &(dll->dll_Null);
  67         dll->dll_Null = (DoublyLinkedListNode *) NULL;
  68         dll->dll_Last = (DoublyLinkedListNode *) &(dll->dll_First);
  69 }
  70
  71 void dllLinkNodes( DoublyLinkedListNode *Node0, DoublyLinkedListNode *Node1 )
  72 {
  73         Node0->dlln_Next = Node1;
  74         Node1->dlln_Previous = Node0;
  75 }
  76
  77 void dllInsertNodeBefore( DoublyLinkedListNode *NewNodePtr,
  78         DoublyLinkedListNode *NodeInListPtr )
  79 {
  80         DoublyLinkedListNode *NodePreviousPtr = dllPreviousNode( NodeInListPtr );
  81         dllLinkNodes( NodePreviousPtr, NewNodePtr );
  82         dllLinkNodes( NewNodePtr, NodeInListPtr );
  83 }
  84
  85 void dllInsertNodeAfter( DoublyLinkedListNode *NewNodePtr,
  86         DoublyLinkedListNode *NodeInListPtr )
  87 {
  88         DoublyLinkedListNode *NodeNextPtr = dllNextNode( NodeInListPtr );
  89         dllLinkNodes( NodeInListPtr, NewNodePtr );
  90         dllLinkNodes( NewNodePtr, NodeNextPtr );
  91 }
  92
  93 void dllDumpNode( DoublyLinkedListNode *NodePtr )
  94 {
  95         TOUCH(NodePtr);
  96         DBUG(("  0x%x -> (0x%x) -> 0x%x\n",
  97                 dllPreviousNode( NodePtr ), NodePtr,
  98                 dllNextNode( NodePtr ) ));
  99 }
 100
 101 int32 dllCheckNode( DoublyLinkedListNode *NodePtr )
 102 {
 103         if( (NodePtr->dlln_Next->dlln_Previous != NodePtr) ||
 104             (NodePtr->dlln_Previous->dlln_Next != NodePtr))
 105         {
 106                 ERR("dllCheckNode: Bad Node!\n");
 107                 dllDumpNode( dllPreviousNode( NodePtr ) );
 108                 dllDumpNode( NodePtr );
 109                 dllDumpNode( dllNextNode( NodePtr ) );
 110                 return -1;
 111         }
 112         else
 113         {
 114                 return 0;
 115         }
 116 }
 117 void dllRemoveNode( DoublyLinkedListNode *NodePtr )
 118 {
 119         if( dllCheckNode( NodePtr ) == 0 )
 120         {
 121                 dllLinkNodes( dllPreviousNode( NodePtr ), dllNextNode( NodePtr ) );
 122         }
 123 }
 124
 125 void dllAddNodeToHead( DoublyLinkedList *ListPtr, DoublyLinkedListNode *NewNodePtr )
 126 {
 127         dllInsertNodeBefore( NewNodePtr, ListPtr->dll_First );
 128 }
 129
 130 void dllAddNodeToTail( DoublyLinkedList *ListPtr, DoublyLinkedListNode *NewNodePtr )
 131 {
 132         dllInsertNodeAfter( NewNodePtr, ListPtr->dll_Last );
 133 }
 134
 135 #define dllIsNodeInList( n ) (!((n)->dlln_Next == NULL) )
 136 #define dllIsLastNode( n ) ((n)->dlln_Next->dll_nNext == NULL )
 137 #define dllIsListEmpty( l ) ((l)->dll_First == ((DoublyLinkedListNode *) &((l)->dll_Null)) )
 138 #define dllFirstNode( l ) ((l)->dll_First)
 139
 140 static DoublyLinkedList gMemList;
 141 static int32 gIfMemListInit;
 142
 143 typedef struct MemListNode
 144 {
 145         DoublyLinkedListNode  mln_Node;
 146         int32                 mln_Size;
 147 } MemListNode;
 148
 149 #ifdef PF_DEBUG
 150 /***************************************************************
 151 ** Dump memory list.
 152 */
 153 void maDumpList( void )
 154 {
 155         MemListNode *mln;
 156
 157         MSG("PForth MemList\n");
 158
 159         for( mln = (MemListNode *) dllFirstNode( &gMemList );
 160              dllIsNodeInList( (DoublyLinkedListNode *) mln);
 161                  mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) )
 162         {
 163                 MSG("  Node at = 0x"); ffDotHex(mln);
 164                 MSG_NUM_H(", size = 0x", mln->mln_Size);
 165         }
 166 }
 167 #endif
 168
 169
 170 /***************************************************************
 171 ** Free mem of any size.
 172 */
 173 static void pfFreeRawMem( char *Mem, int32 NumBytes )
 174 {
 175         MemListNode *mln, *FreeNode;
 176         MemListNode *AdjacentLower = NULL;
 177         MemListNode *AdjacentHigher = NULL;
 178         MemListNode *NextBiggest = NULL;
 179
 180 /* Allocate in whole blocks of 16 bytes */
 181         DBUG(("\npfFreeRawMem( 0x%x, 0x%x )\n", Mem, NumBytes ));
 182         NumBytes = (NumBytes + PF_MEM_BLOCK_SIZE - 1) & ~(PF_MEM_BLOCK_SIZE - 1);
 183         DBUG(("\npfFreeRawMem: Align NumBytes to 0x%x\n", NumBytes ));
 184
 185 /* Check memory alignment. */
 186         if( ( ((int32)Mem) & (PF_MEM_BLOCK_SIZE - 1)) != 0)
 187         {
 188                 MSG_NUM_H("pfFreeRawMem: misaligned Mem = 0x", (int32) Mem );
 189                 return;
 190         }
 191
 192 /* Scan list from low to high looking for various nodes. */
 193         for( mln = (MemListNode *) dllFirstNode( &gMemList );
 194              dllIsNodeInList( (DoublyLinkedListNode *) mln);
 195                  mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) )
 196         {
 197                 if( (((char *) mln) + mln->mln_Size) == Mem )
 198                 {
 199                         AdjacentLower = mln;
 200                 }
 201                 else if( ((char *) mln) == ( Mem + NumBytes ))
 202                 {
 203                         AdjacentHigher = mln;
 204                 }
 205 /* is this the next biggest node. */
 206                 else if( (NextBiggest == NULL) && (mln->mln_Size >= NumBytes) )
 207                 {
 208                         NextBiggest = mln;
 209                 }
 210         }
 211
 212 /* Check to see if we can merge nodes. */
 213         if( AdjacentHigher )
 214         {
 215 DBUG((" Merge (0x%x) -> 0x%x\n", Mem, AdjacentHigher ));
 216                 NumBytes += AdjacentHigher->mln_Size;
 217                 dllRemoveNode( (DoublyLinkedListNode *) AdjacentHigher );
 218         }
 219         if( AdjacentLower )
 220         {
 221 DBUG((" Merge 0x%x -> (0x%x)\n", AdjacentLower, Mem ));
 222                 AdjacentLower->mln_Size += NumBytes;
 223         }
 224         else
 225         {
 226 DBUG((" Link before 0x%x\n", NextBiggest ));
 227                 FreeNode = (MemListNode *) Mem;
 228                 FreeNode->mln_Size = NumBytes;
 229                 if( NextBiggest == NULL )
 230                 {
 231 /* Nothing bigger so add to end of list. */
 232                         dllAddNodeToTail( &gMemList, (DoublyLinkedListNode *) FreeNode );
 233                 }
 234                 else
 235                 {
 236 /* Add this node before the next biggest one we found. */
 237                         dllInsertNodeBefore( (DoublyLinkedListNode *) FreeNode,
 238                                 (DoublyLinkedListNode *) NextBiggest );
 239                 }
 240         }
 241
 242 /*      maDumpList(); */
 243 }
 244
 245
 246
 247 /***************************************************************
 248 ** Setup memory list. Initialize allocator.
 249 */
 250 void pfInitMemAllocator( void *addr, uint32 poolSize )
 251 {
 252         char *AlignedMemory;
 253         int32 AlignedSize;
 254
 255 /* Set globals. */
 256         gMemPoolPtr = addr;
 257         gMemPoolSize = poolSize;
 258
 259         dllSetupList( &gMemList );
 260         gIfMemListInit = TRUE;
 261
 262 /* Adjust to next highest aligned memory location. */
 263         AlignedMemory = (char *) ((((int32)gMemPoolPtr) + PF_MEM_BLOCK_SIZE - 1) &
 264                           ~(PF_MEM_BLOCK_SIZE - 1));
 265
 266 /* Adjust size to reflect aligned memory. */
 267         AlignedSize = gMemPoolSize - (AlignedMemory - gMemPoolPtr);
 268
 269 /* Align size of pool. */
 270         AlignedSize = AlignedSize & ~(PF_MEM_BLOCK_SIZE - 1);
 271
 272 /* Free to pool. */
 273         pfFreeRawMem( AlignedMemory, AlignedSize );
 274
 275 }
 276
 277 /***************************************************************
 278 ** Allocate mem from list of free nodes.
 279 */
 280 static char *pfAllocRawMem( int32 NumBytes )
 281 {
 282         char *Mem = NULL;
 283         MemListNode *mln;
 284
 285         if( NumBytes <= 0 ) return NULL;
 286
 287         if( gIfMemListInit == 0 ) pfInitMemAllocator( PF_MALLOC_ADDRESS, PF_MEM_POOL_SIZE );
 288
 289 /* Allocate in whole blocks of 16 bytes */
 290         NumBytes = (NumBytes + PF_MEM_BLOCK_SIZE - 1) & ~(PF_MEM_BLOCK_SIZE - 1);
 291
 292         DBUG(("\npfAllocRawMem( 0x%x )\n", NumBytes ));
 293
 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 ) )
 298         {
 299                 if( mln->mln_Size >= NumBytes )
 300                 {
 301                         int32 RemSize;
 302
 303                         Mem = (char *) mln;
 304
 305 /* Remove this node from list. */
 306                         dllRemoveNode( (DoublyLinkedListNode *) mln );
 307
 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 )
 311                         {
 312                                 pfFreeRawMem( (Mem + NumBytes), RemSize );
 313                         }
 314                         break;
 315                 }
 316
 317         }
 318 /*      maDumpList(); */
 319         DBUG(("Allocate mem at 0x%x.\n", Mem ));
 320         return Mem;
 321 }
 322
 323 /***************************************************************
 324 ** Keep mem size at first cell.
 325 */
 326 char *pfAllocMem( int32 NumBytes )
 327 {
 328         int32 *IntMem;
 329
 330         if( NumBytes <= 0 ) return NULL;
 331
 332 /* Allocate an extra cell for size. */
 333         NumBytes += sizeof(int32);
 334
 335         IntMem = (int32 *)pfAllocRawMem( NumBytes );
 336
 337         if( IntMem != NULL ) *IntMem++ = NumBytes;
 338
 339         return (char *) IntMem;
 340 }
 341
 342 /***************************************************************
 343 ** Free mem with mem size at first cell.
 344 */
 345 void pfFreeMem( void *Mem )
 346 {
 347         int32 *IntMem;
 348         int32 NumBytes;
 349
 350         if( Mem == NULL ) return;
 351
 352 /* Allocate an extra cell for size. */
 353         IntMem = (int32 *) Mem;
 354         IntMem--;
 355         NumBytes = *IntMem;
 356
 357         pfFreeRawMem( (char *) IntMem, NumBytes );
 358
 359 }
 360
 361 #endif /* PF_NO_MALLOC */