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

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