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