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