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