Kernel/include/tpl_mm_phys_bitmap.h

   1 /*
   2  * Acess2 Core
   3  *
   4  * include/tpl_mm_phys_bitmap.h
   5  * Physical Memory Manager Template
   6  */
   7 #define DEBUG   0
   8
   9 /*
  10  * Bitmap Edition
  11  *
  12  * Uses 4.125+PtrSize bytes per page
  13  */
  14
  15 #define MM_PAGE_REFCOUNTS       MM_PMM_BASE
  16 #define MM_PAGE_NODES   (MM_PMM_BASE+(MM_MAXPHYSPAGE*sizeof(Uint32)))
  17 #define MM_PAGE_BITMAP  (MM_PAGE_NODES+(MM_MAXPHYSPAGE*sizeof(void*)))
  18
  19 // === PROTOTYPES ===
  20 //void  MM_InitPhys_Multiboot(tMBoot_Info *MBoot);
  21 //tPAddr        MM_AllocPhysRange(int Num, int Bits);
  22 //tPAddr        MM_AllocPhys(void);
  23 //void  MM_RefPhys(tPAddr PAddr);
  24 //void  MM_DerefPhys(tPAddr PAddr);
  25  int    MM_int_GetRangeID( tPAddr Addr );
  26  int    MM_int_GetMapEntry( void *Data, int Index, tPAddr *Start, tPAddr *Length );
  27 void    MM_Tpl_InitPhys(int MaxRAMPage, void *MemoryMap);
  28
  29 // === GLOBALS ===
  30 tMutex  glPhysicalPages;
  31 void    **gapPageNodes = (void*)MM_PAGE_NODES;  //!< Associated VFS Node for each page
  32 Uint32  *gaiPageReferences = (void*)MM_PAGE_REFCOUNTS;  // Reference Counts
  33 Uint32  *gaPageBitmaps = (void*)MM_PAGE_BITMAP; // Used bitmap (1 == avail)
  34 Uint64  giMaxPhysPage = 0;      // Maximum Physical page
  35  int    gbPMM_Init = 0;
  36  int    gaiPhysRangeFirstFree[MM_NUM_RANGES];
  37  int    gaiPhysRangeLastFree[MM_NUM_RANGES];
  38  int    gaiPhysRangeNumFree[MM_NUM_RANGES];
  39
  40 // === CODE ===
  41 /**
  42  * \brief Initialise the physical memory manager with a passed memory map
  43  */
  44 void MM_Tpl_InitPhys(int MaxRAMPage, void *MemoryMap)
  45 {
  46          int    mapIndex = 0;
  47         tPAddr  rangeStart, rangeLen;
  48
  49         if( MM_PAGE_BITMAP + (MM_MAXPHYSPAGE/8) > MM_PMM_END ) {
  50                 Log_KernelPanic("PMM", "Config Error, PMM cannot fit data in allocated range");
  51         }
  52
  53         giMaxPhysPage = MaxRAMPage;
  54
  55         while( MM_int_GetMapEntry(MemoryMap, mapIndex++, &rangeStart, &rangeLen) )
  56         {
  57                 tVAddr  bitmap_page;
  58                 rangeStart /= PAGE_SIZE;
  59                 rangeLen /= PAGE_SIZE;
  60
  61                 bitmap_page = (tVAddr)&gaPageBitmaps[rangeStart/32];
  62                 bitmap_page &= ~(PAGE_SIZE-1);
  63
  64                 // Only need to allocate bitmaps
  65                 if( !MM_GetPhysAddr( bitmap_page ) ) {
  66                         if( MM_Allocate( bitmap_page ) ) {
  67                                 Log_KernelPanic("PMM", "Out of memory during init, this is bad");
  68                                 return ;
  69                         }
  70                         memset( (void*)bitmap_page, 0, rangeStart/8 & ~(PAGE_SIZE-1) );
  71                 }
  72
  73                 // Align to 32 pages
  74                 for( ; (rangeStart & 31) && rangeLen > 0; rangeStart++, rangeLen-- ) {
  75                         gaPageBitmaps[rangeStart / 32] |= 1 << (rangeStart&31);
  76                 }
  77                 // Mark blocks of 32 as avail
  78                 for( ; rangeLen > 31; rangeStart += 32, rangeLen -= 32 ) {
  79                         gaPageBitmaps[rangeStart / 32] = -1;
  80                 }
  81                 // Mark the tail
  82                 for( ; rangeLen > 0; rangeStart ++, rangeLen -- ) {
  83                         gaPageBitmaps[rangeStart / 32] |= 1 << (rangeStart&31);
  84                 }
  85         }
  86
  87         gbPMM_Init = 1;
  88
  89         LEAVE('-');
  90 }
  91
  92 /**
  93  * \brief Allocate a contiguous range of physical pages with a maximum
  94  *        bit size of \a MaxBits
  95  * \param Pages Number of pages to allocate
  96  * \param MaxBits       Maximum size of the physical address
  97  * \note If \a MaxBits is <= 0, any sized address is used (with preference
  98  *       to higher addresses)
  99  */
 100 tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
 101 {
 102         tPAddr  addr, ret;
 103          int    rangeID;
 104          int    nFree = 0, i;
 105
 106         ENTER("iPages iBits", Pages, MaxBits);
 107
 108         // Get range ID
 109         if( MaxBits <= 0 || MaxBits >= 64 )     // Speedup for the common case
 110                 rangeID = MM_RANGE_MAX;
 111         else
 112                 rangeID = MM_int_GetRangeID( (1LL << MaxBits) - 1 );
 113
 114         Mutex_Acquire(&glPhysicalPages);
 115
 116         // Check if the range actually has any free pages
 117         while(gaiPhysRangeNumFree[rangeID] == 0 && rangeID)
 118                 rangeID --;
 119
 120         LOG("rangeID = %i", rangeID);
 121
 122         // Check if there is enough in the range
 123         if(gaiPhysRangeNumFree[rangeID] >= Pages)
 124         {
 125                 LOG("{%i,0x%x -> 0x%x}",
 126                         giPhysRangeFree[rangeID],
 127                         giPhysRangeFirst[rangeID], giPhysRangeLast[rangeID]
 128                         );
 129                 // Do a cheap scan, scanning upwards from the first free page in
 130                 // the range
 131                 nFree = 0;
 132                 addr = gaiPhysRangeFirstFree[ rangeID ];
 133                 while( addr <= gaiPhysRangeLastFree[ rangeID ] )
 134                 {
 135                         #if USE_SUPER_BITMAP
 136                         // Check the super bitmap
 137                         if( gaSuperBitmap[addr / (32*32)] == 0 )
 138                         {
 139                                 LOG("nFree = %i = 0 (super) (0x%x)", nFree, addr);
 140                                 nFree = 0;
 141                                 addr += 1LL << (6+6);
 142                                 addr &= ~0xFFF; // (1LL << 6+6) - 1
 143                                 continue;
 144                         }
 145                         #endif
 146                         // Check page block (32 pages)
 147                         if( gaPageBitmaps[addr / 32] == 0) {
 148                                 LOG("nFree = %i = 0 (main) (0x%x)", nFree, addr);
 149                                 nFree = 0;
 150                                 addr += 1LL << (6);
 151                                 addr &= ~0x3F;
 152                                 continue;
 153                         }
 154                         // Check individual page
 155                         if( !(gaPageBitmaps[addr / 32] & (1LL << (addr & 31))) )
 156                         {
 157                                 LOG("nFree = %i = 0 (page) (0x%x)", nFree, addr);
 158                                 nFree = 0;
 159                                 addr ++;
 160                                 continue;
 161                         }
 162                         nFree ++;
 163                         addr ++;
 164                         LOG("nFree(%i) == %i (0x%x)", nFree, Pages, addr);
 165                         if(nFree == Pages)
 166                                 break;
 167                 }
 168                 LOG("nFree = %i", nFree);
 169                 // If we don't find a contiguous block, nFree will not be equal
 170                 // to Num, so we set it to zero and do the expensive lookup.
 171                 if(nFree != Pages)      nFree = 0;
 172         }
 173
 174         if( !nFree )
 175         {
 176                 // Oops. ok, let's do an expensive check (scan down the list
 177                 // until a free range is found)
 178                 nFree = 1;
 179                 addr = gaiPhysRangeLastFree[ rangeID ];
 180                 // TODO
 181                 Mutex_Release(&glPhysicalPages);
 182                 // TODO: Page out
 183                 // ATM. Just Warning
 184                 Warning(" MM_AllocPhysRange: Out of memory (unable to fulfil request for %i pages)", Pages);
 185                 Log_Warning("PMM",
 186                         "Out of memory (unable to fulfil request for %i pages)",
 187                         Pages
 188                         );
 189                 LEAVE('i', 0);
 190                 return 0;
 191         }
 192         LOG("nFree = %i, addr = 0x%08x", nFree, addr);
 193
 194         // Mark pages as allocated
 195         addr -= Pages;
 196         for( i = 0; i < Pages; i++, addr++ )
 197         {
 198                 // Mark as used
 199                 gaPageBitmaps[addr / 32] &= ~(1 << (addr & 31));
 200                 // Maintain first possible free
 201                 rangeID = MM_int_GetRangeID(addr * PAGE_SIZE);
 202                 gaiPhysRangeNumFree[ rangeID ] --;
 203                 if(addr == gaiPhysRangeFirstFree[ rangeID ])
 204                         gaiPhysRangeFirstFree[ rangeID ] += 1;
 205
 206                 // Mark as referenced if the reference count page is valid
 207                 if(MM_GetPhysAddr( (tVAddr)&gaiPageReferences[addr] )) {
 208                         gaiPageReferences[addr] = 1;
 209                 }
 210         }
 211         ret = addr;     // Save the return address
 212
 213         #if USE_SUPER_BITMAP
 214         // Update super bitmap
 215         Pages += addr & (32-1);
 216         addr &= ~(32-1);
 217         Pages = (Pages + (32-1)) & ~(32-1);
 218         for( i = 0; i < Pages/32; i++ )
 219         {
 220                 if( gaPageBitmaps[ addr / 32 ] + 1 == 0 )
 221                         gaSuperBitmap[addr / (32*32)] |= 1LL << ((addr / 32) & 31);
 222         }
 223         #endif
 224
 225         Mutex_Release(&glPhysicalPages);
 226         LEAVE('x', ret << 12);
 227         return ret << 12;
 228 }
 229
 230 /**
 231  * \brief Allocate a single physical page, with no preference as to address size.
 232  */
 233 tPAddr MM_AllocPhys(void)
 234 {
 235          int    i;
 236
 237         if( !gbPMM_Init )
 238         {
 239                 // Hack to allow allocation during setup
 240                 for(i = 0; i < NUM_STATIC_ALLOC; i++) {
 241                         if( gaiStaticAllocPages[i] ) {
 242                                 tPAddr  ret = gaiStaticAllocPages[i];
 243                                 gaiStaticAllocPages[i] = 0;
 244                                 Log("MM_AllocPhys: Return %x, static alloc %i", ret, i);
 245                                 return ret;
 246                         }
 247                 }
 248
 249                 tPAddr  ret = 0;
 250                 for( ret = 0; ret < giMaxPhysPage; ret ++ )
 251                 {
 252                         if( !MM_GetPhysAddr( (tVAddr)&gaPageBitmaps[ret/32] ) ) {
 253                                 ret += PAGE_SIZE*8;
 254                                 continue ;
 255                         }
 256                         if( gaPageBitmaps[ret/32] == 0 ) {
 257                                 ret += 32-1;
 258                                 continue ;
 259                         }
 260                         if( gaPageBitmaps[ret/32] & (1 << (ret&31)) ) {
 261                                 gaPageBitmaps[ret/32] &= ~(1 << (ret&31));
 262                                 return ret * PAGE_SIZE;
 263                         }
 264                 }
 265                 Log_Error("PMM", "MM_AllocPhys failed duing init");
 266                 return 0;
 267         }
 268
 269         return MM_AllocPhysRange(1, -1);
 270 }
 271
 272 /**
 273  * \brief Reference a physical page
 274  */
 275 void MM_RefPhys(tPAddr PAddr)
 276 {
 277         tPAddr  page = PAddr / PAGE_SIZE;
 278
 279         if( page >= giMaxPhysPage )     return ;
 280
 281         if( gaPageBitmaps[ page / 32 ] & (1LL << (page&31)) )
 282         {
 283                 // Allocate
 284                 gaPageBitmaps[page / 32] &= ~(1LL << (page&31));
 285                 #if USE_SUPER_BITMAP
 286                 if( gaPageBitmaps[page / 32] == 0 )
 287                         gaSuperBitmap[page / (32*32)] &= ~(1LL << ((page / 32) & 31));
 288                 #endif
 289         }
 290         else
 291         {
 292                 tVAddr  refpage = (tVAddr)&gaiPageReferences[page] & ~(PAGE_SIZE-1);
 293                 // Reference again
 294                 if( !MM_GetPhysAddr( refpage ) )
 295                 {
 296                         if( MM_Allocate(refpage) == 0 ) {
 297                                 // Out of memory, can this be resolved?
 298                                 // TODO: Reclaim memory
 299                                 Log_Error("PMM", "Out of memory (MM_RefPhys)");
 300                                 return ;
 301                         }
 302                         memset((void*)refpage, 0, PAGE_SIZE);
 303                         gaiPageReferences[page] = 2;
 304                 }
 305                 else
 306                         gaiPageReferences[ page ] ++;
 307         }
 308 }
 309
 310 /**
 311  * \brief Dereference a physical page
 312  */
 313 void MM_DerefPhys(tPAddr PAddr)
 314 {
 315         Uint64  page = PAddr >> 12;
 316
 317         if( PAddr >> 12 > giMaxPhysPage )       return ;
 318
 319         if( MM_GetPhysAddr( (tVAddr)&gaiPageReferences[page] ) )
 320         {
 321                 if( gaiPageReferences[page] > 0 )
 322                         gaiPageReferences[ page ] --;
 323                 if( gaiPageReferences[ page ] == 0 ) {
 324                         gaPageBitmaps[ page / 32 ] |= 1 << (page&31);
 325                         // TODO: Catch when all pages in this range have been dereferenced
 326                 }
 327         }
 328         else
 329                 gaPageBitmaps[ page / 32 ] |= 1 << (page&31);
 330         // Clear node if needed
 331         if( MM_GetPhysAddr( (tVAddr)&gapPageNodes[page] ) ) {
 332                 gapPageNodes[page] = NULL;
 333                 // TODO: Catch when all pages in this range are not using nodes
 334         }
 335
 336         // Update the free counts if the page was freed
 337         if( gaPageBitmaps[ page / 32 ] & (1LL << (page&31)) )
 338         {
 339                  int    rangeID;
 340                 rangeID = MM_int_GetRangeID( PAddr );
 341                 gaiPhysRangeNumFree[ rangeID ] ++;
 342                 if( gaiPhysRangeFirstFree[rangeID] > page )
 343                         gaiPhysRangeFirstFree[rangeID] = page;
 344                 if( gaiPhysRangeLastFree[rangeID] < page )
 345                         gaiPhysRangeLastFree[rangeID] = page;
 346         }
 347
 348         #if USE_SUPER_BITMAP
 349         // If the bitmap entry is not zero, set the bit free in the super bitmap
 350         if(gaPageBitmaps[ page / 32 ] != 0 ) {
 351                 gaSuperBitmap[page / (32*32)] |= 1LL << ((page / 32) & 31);
 352         }
 353         #endif
 354 }
 355