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         #endif
 227
 228         #if USE_SUPER_BITMAP
 229         // Update super bitmap
 230         Pages += addr & (32-1);
 231         addr &= ~(32-1);
 232         Pages = (Pages + (32-1)) & ~(32-1);
 233         for( i = 0; i < Pages/32; i++ )
 234         {
 235                 if( gaPageBitmaps[ addr / 32 ] + 1 == 0 )
 236                         gaSuperBitmap[addr / (32*32)] |= 1LL << ((addr / 32) & 31);
 237         }
 238         #endif
 239
 240         Mutex_Release(&glPhysicalPages);
 241         LEAVE('x', ret << 12);
 242         return ret << 12;
 243 }
 244
 245 /**
 246  * \brief Allocate a single physical page, with no preference as to address size.
 247  */
 248 tPAddr MM_AllocPhys(void)
 249 {
 250          int    i;
 251
 252         if( !gbPMM_Init )
 253         {
 254                 // Hack to allow allocation during setup
 255                 for(i = 0; i < NUM_STATIC_ALLOC; i++) {
 256                         if( gaiStaticAllocPages[i] ) {
 257                                 tPAddr  ret = gaiStaticAllocPages[i];
 258                                 gaiStaticAllocPages[i] = 0;
 259                                 Log("MM_AllocPhys: Return %x, static alloc %i", ret, i);
 260                                 return ret;
 261                         }
 262                 }
 263
 264                 tPAddr  ret = 0;
 265                 for( ret = 0; ret < giMaxPhysPage; ret ++ )
 266                 {
 267                         if( !MM_GetPhysAddr( (tVAddr)&gaPageBitmaps[ret/32] ) ) {
 268                                 ret += PAGE_SIZE*8;
 269                                 continue ;
 270                         }
 271                         if( gaPageBitmaps[ret/32] == 0 ) {
 272                                 ret += 32-1;
 273                                 continue ;
 274                         }
 275                         if( gaPageBitmaps[ret/32] & (1 << (ret&31)) ) {
 276                                 gaPageBitmaps[ret/32] &= ~(1 << (ret&31));
 277                                 return ret * PAGE_SIZE;
 278                         }
 279                 }
 280                 Log_Error("PMM", "MM_AllocPhys failed duing init");
 281                 return 0;
 282         }
 283         #if TRACE_ALLOCS
 284         Log("AllocPhys by %p", __builtin_return_address(0));
 285         #endif
 286
 287         return MM_AllocPhysRange(1, -1);
 288 }
 289
 290 /**
 291  * \brief Reference a physical page
 292  */
 293 void MM_RefPhys(tPAddr PAddr)
 294 {
 295         tPAddr  page = PAddr / PAGE_SIZE;
 296         tVAddr  refpage = (tVAddr)&gaiPageReferences[page] & ~(PAGE_SIZE-1);
 297
 298         if( page >= giMaxPhysPage )     return ;
 299
 300         if( PAGE_BITMAP_FREE(page) )
 301         {
 302                 // Allocate
 303                 PAGE_BITMAP_SETUSED(page);
 304                 #if USE_SUPER_BITMAP
 305                 if( gaPageBitmaps[page / 32] == 0 )
 306                         gaSuperBitmap[page / (32*32)] &= ~(1LL << ((page / 32) & 31));
 307                 #endif
 308                 if( MM_GetPhysAddr( refpage ) )
 309                         gaiPageReferences[page] = 1;
 310         }
 311         else
 312         {
 313                 // Reference again
 314                 if( !MM_GetPhysAddr( refpage ) )
 315                 {
 316                          int    pages_per_page, basepage, i;
 317                         if( MM_Allocate(refpage) == 0 ) {
 318                                 // Out of memory, can this be resolved?
 319                                 // TODO: Reclaim memory
 320                                 Log_Error("PMM", "Out of memory (MM_RefPhys)");
 321                                 return ;
 322                         }
 323                         pages_per_page = PAGE_SIZE/sizeof(*gaiPageReferences);
 324                         basepage = page & ~(pages_per_page-1);
 325                         for( i = 0; i < pages_per_page; i ++ ) {
 326                                 if( PAGE_BITMAP_FREE(basepage+i) )
 327                                         gaiPageReferences[basepage+i] = 0;
 328                                 else
 329                                         gaiPageReferences[basepage+i] = 1;
 330                         }
 331                         gaiPageReferences[page] = 2;
 332                 }
 333                 else
 334                         gaiPageReferences[ page ] ++;
 335         }
 336 }
 337
 338 int MM_GetRefCount(tPAddr PAddr)
 339 {
 340         PAddr >>= 12;
 341         if( MM_GetPhysAddr( (tVAddr)&gaiPageReferences[PAddr] ) ) {
 342                 return gaiPageReferences[PAddr];
 343         }
 344
 345         if( gaPageBitmaps[ PAddr / 32 ] & (1LL << (PAddr&31)) ) {
 346                 return 1;
 347         }
 348
 349         return 0;
 350 }
 351
 352 /**
 353  * \brief Dereference a physical page
 354  */
 355 void MM_DerefPhys(tPAddr PAddr)
 356 {
 357         Uint64  page = PAddr >> 12;
 358
 359         if( PAddr >> 12 > giMaxPhysPage )       return ;
 360
 361         ENTER("PPAddr", PAddr);
 362
 363         if( MM_GetPhysAddr( (tVAddr)&gaiPageReferences[page] ) )
 364         {
 365                 if( gaiPageReferences[page] > 0 )
 366                         gaiPageReferences[ page ] --;
 367                 if( gaiPageReferences[ page ] == 0 ) {
 368                         gaPageBitmaps[ page / 32 ] |= 1 << (page&31);
 369                         // TODO: Catch when all pages in this range have been dereferenced
 370                 }
 371         }
 372         else
 373                 gaPageBitmaps[ page / 32 ] |= 1 << (page&31);
 374         // Clear node if needed
 375         if( MM_GetPhysAddr( (tVAddr)&gapPageNodes[page] ) ) {
 376                 gapPageNodes[page] = NULL;
 377                 // TODO: Catch when all pages in this range are not using nodes
 378         }
 379
 380         // Update the free counts if the page was freed
 381         if( gaPageBitmaps[ page / 32 ] & (1LL << (page&31)) )
 382         {
 383                 giPhysNumFree ++;
 384                 if( giPhysFirstFree == -1 || giPhysFirstFree > page )
 385                         giPhysFirstFree = page;
 386                 if( giPhysLastFree < page )
 387                         giPhysLastFree = page;
 388         }
 389
 390         #if USE_SUPER_BITMAP
 391         // If the bitmap entry is not zero, set the bit free in the super bitmap
 392         if(gaPageBitmaps[ page / 32 ] != 0 ) {
 393                 gaSuperBitmap[page / (32*32)] |= 1LL << ((page / 32) & 31);
 394         }
 395         #endif
 396         LEAVE('-');
 397 }
 398
 399 int MM_SetPageNode(tPAddr PAddr, void *Node)
 400 {
 401         tPAddr  page = PAddr >> 12;
 402         tVAddr  node_page = ((tVAddr)&gapPageNodes[page]) & ~(PAGE_SIZE-1);
 403
 404         if( !MM_GetRefCount(PAddr) )    return 1;
 405
 406         if( !MM_GetPhysAddr(node_page) ) {
 407                 if( !MM_Allocate(node_page) )
 408                         return -1;
 409                 memset( (void*)node_page, 0, PAGE_SIZE );
 410         }
 411
 412         gapPageNodes[page] = Node;
 413         return 0;
 414 }
 415
 416 int MM_GetPageNode(tPAddr PAddr, void **Node)
 417 {
 418         if( !MM_GetRefCount(PAddr) )    return 1;
 419         PAddr >>= 12;
 420
 421         if( !MM_GetPhysAddr( (tVAddr)&gapPageNodes[PAddr] ) ) {
 422                 *Node = NULL;
 423                 return 0;
 424         }
 425
 426         *Node = gapPageNodes[PAddr];
 427         return 0;
 428 }
 429