Kernel/arch/x86_64/mm_phys.c

   1 /*
   2  * Acess2 x86_64 Port
   3  *
   4  * Physical Memory Manager
   5  */
   6 #define DEBUG   0
   7 #include <acess.h>
   8 #include <mboot.h>
   9 #include <mm_virt.h>
  10
  11 enum eMMPhys_Ranges
  12 {
  13         MM_PHYS_16BIT,  // Does anything need this?
  14         MM_PHYS_20BIT,  // Real-Mode
  15         MM_PHYS_24BIT,  // ISA DMA
  16         MM_PHYS_32BIT,  // x86 Hardware
  17         MM_PHYS_MAX,    // Doesn't care
  18         NUM_MM_PHYS_RANGES
  19 };
  20
  21 // === IMPORTS ===
  22 extern char     gKernelBase[];
  23 extern char     gKernelEnd[];
  24
  25 // === PROTOTYPES ===
  26 void    MM_InitPhys_Multiboot(tMBoot_Info *MBoot);
  27 tPAddr  MM_AllocPhysRange(int Num, int Bits);
  28 tPAddr  MM_AllocPhys(void);
  29 void    MM_RefPhys(tPAddr PAddr);
  30 void    MM_DerefPhys(tPAddr PAddr);
  31  int    MM_int_GetRangeID( tPAddr Addr );
  32
  33 // === GLOBALS ===
  34 tMutex  glPhysicalPages;
  35 Uint64  *gaSuperBitmap = (void*)MM_PAGE_SUPBMP; // 1 bit = 64 Pages, 16 MiB Per Word
  36 Uint64  *gaMainBitmap = (void*)MM_PAGE_BITMAP;  // 1 bit = 1 Page, 256 KiB per Word
  37 Uint64  *gaMultiBitmap = (void*)MM_PAGE_DBLBMP; // Each bit means that the page is being used multiple times
  38 Uint32  *gaiPageReferences = (void*)MM_PAGE_COUNTS;     // Reference Counts
  39 tPAddr  giFirstFreePage;        // First possibly free page
  40 Uint64  giPhysRangeFree[NUM_MM_PHYS_RANGES];    // Number of free pages in each range
  41 Uint64  giPhysRangeFirst[NUM_MM_PHYS_RANGES];   // First free page in each range
  42 Uint64  giPhysRangeLast[NUM_MM_PHYS_RANGES];    // Last free page in each range
  43 Uint64  giMaxPhysPage = 0;      // Maximum Physical page
  44 // Only used in init, allows the init code to provide pages for use by
  45 // the allocator before the bitmaps exist.
  46 // 3 entries because the are three calls to MM_AllocPhys in MM_Map
  47 #define NUM_STATIC_ALLOC        3
  48 tPAddr  gaiStaticAllocPages[NUM_STATIC_ALLOC] = {0};
  49
  50 // === CODE ===
  51 /**
  52  * \brief Initialise the physical memory map using a Multiboot 1 map
  53  */
  54 void MM_InitPhys_Multiboot(tMBoot_Info *MBoot)
  55 {
  56         tMBoot_MMapEnt  *mmapStart;
  57         tMBoot_MMapEnt  *ent;
  58         Uint64  maxAddr = 0;
  59          int    numPages, superPages;
  60          int    i;
  61         Uint64  base, size;
  62         tVAddr  vaddr;
  63         tPAddr  paddr, firstFreePage;
  64
  65         ENTER("pMBoot=%p", MBoot);
  66
  67         // Scan the physical memory map
  68         // Looking for the top of physical memory
  69         mmapStart = (void *)( KERNEL_BASE | MBoot->MMapAddr );
  70         LOG("mmapStart = %p", mmapStart);
  71         ent = mmapStart;
  72         while( (Uint)ent < (Uint)mmapStart + MBoot->MMapLength )
  73         {
  74                 // Adjust for the size of the entry
  75                 ent->Size += 4;
  76                 LOG("ent={Type:%i,Base:0x%x,Length:%x",
  77                         ent->Type, ent->Base, ent->Length);
  78
  79                 // If entry is RAM and is above `maxAddr`, change `maxAddr`
  80                 if(ent->Type == 1 && ent->Base + ent->Length > maxAddr)
  81                         maxAddr = ent->Base + ent->Length;
  82
  83                 // Go to next entry
  84                 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size );
  85         }
  86
  87         // Did we find a valid end?
  88         if(maxAddr == 0) {
  89                 // No, darn, let's just use the HighMem hack
  90                 giMaxPhysPage = (MBoot->HighMem >> 2) + 256;    // HighMem is a kByte value
  91         }
  92         else {
  93                 // Goodie, goodie gumdrops
  94                 giMaxPhysPage = maxAddr >> 12;
  95         }
  96         LOG("giMaxPhysPage = 0x%x", giMaxPhysPage);
  97
  98         // Find a contigous section of memory to hold it in
  99         // - Starting from the end of the kernel
 100         // - We also need a region for the super bitmap
 101         superPages = ((giMaxPhysPage+64*8-1)/(64*8) + 0xFFF) >> 12;
 102         numPages = (giMaxPhysPage + 7) / 8;
 103         numPages = (numPages + 0xFFF) >> 12;
 104         LOG("numPages = %i, superPages = %i", numPages, superPages);
 105         if(maxAddr == 0)
 106         {
 107                  int    todo = numPages*2 + superPages;
 108                 // Ok, naieve allocation, just put it after the kernel
 109                 // - Allocated Bitmap
 110                 vaddr = MM_PAGE_BITMAP;
 111                 paddr = (tPAddr)&gKernelEnd - KERNEL_BASE;
 112                 while(todo )
 113                 {
 114                         // Allocate statics
 115                         for( i = 0; i < NUM_STATIC_ALLOC; i++) {
 116                                 if(gaiStaticAllocPages[i] != 0) continue;
 117                                 gaiStaticAllocPages[i] = paddr;
 118                                 paddr += 0x1000;
 119                         }
 120
 121                         MM_Map(vaddr, paddr);
 122                         vaddr += 0x1000;
 123                         paddr += 0x1000;
 124
 125                         todo --;
 126
 127                         if( todo == numPages + superPages )
 128                                 vaddr = MM_PAGE_DBLBMP;
 129                         if( todo == superPages )
 130                                 vaddr = MM_PAGE_SUPBMP;
 131                 }
 132         }
 133         // Scan for a nice range
 134         else
 135         {
 136                  int    todo = numPages*2 + superPages;
 137                 paddr = 0;
 138                 vaddr = MM_PAGE_BITMAP;
 139                 // Scan!
 140                 for(
 141                         ent = mmapStart;
 142                         (Uint)ent < (Uint)mmapStart + MBoot->MMapLength;
 143                         ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size )
 144                         )
 145                 {
 146                          int    avail;
 147
 148                         // RAM only please
 149                         if( ent->Type != 1 )
 150                                 continue;
 151
 152                         // Let's not put it below the kernel, shall we?
 153                         if( ent->Base + ent->Size < (tPAddr)&gKernelBase )
 154                                 continue;
 155
 156                         LOG("%x <= %x && %x > %x",
 157                                 ent->Base, (tPAddr)&gKernelBase,
 158                                 ent->Base + ent->Size, (tPAddr)&gKernelEnd - KERNEL_BASE
 159                                 );
 160                         // Check if the kernel is in this range
 161                         if( ent->Base <= (tPAddr)&gKernelBase
 162                         && ent->Base + ent->Length > (tPAddr)&gKernelEnd - KERNEL_BASE )
 163                         {
 164                                 avail = ent->Length >> 12;
 165                                 avail -= ((tPAddr)&gKernelEnd - KERNEL_BASE - ent->Base) >> 12;
 166                                 paddr = (tPAddr)&gKernelEnd - KERNEL_BASE;
 167                         }
 168                         // No? then we can use all of the block
 169                         else
 170                         {
 171                                 avail = ent->Length >> 12;
 172                                 paddr = ent->Base;
 173                         }
 174
 175                         Log(" MM_InitPhys_Multiboot: paddr=0x%x, avail=%i", paddr, avail);
 176
 177                         // Map
 178                         while( todo && avail --)
 179                         {
 180                                 // Static Allocations
 181                                 for( i = 0; i < NUM_STATIC_ALLOC && avail; i++) {
 182                                         if(gaiStaticAllocPages[i] != 0) continue;
 183                                         gaiStaticAllocPages[i] = paddr;
 184                                         paddr += 0x1000;
 185                                         avail --;
 186                                 }
 187                                 if(!avail)      break;
 188
 189                                 // Map
 190                                 MM_Map(vaddr, paddr);
 191                                 todo --;
 192                                 vaddr += 0x1000;
 193                                 paddr += 0x1000;
 194
 195                                 // Alter the destination address when needed
 196                                 if(todo == superPages+numPages)
 197                                         vaddr = MM_PAGE_DBLBMP;
 198                                 if(todo == superPages)
 199                                         vaddr = MM_PAGE_SUPBMP;
 200                         }
 201
 202                         // Fast quit if there's nothing left to allocate
 203                         if( !todo )             break;
 204                 }
 205         }
 206         // Save the current value of paddr to simplify the allocation later
 207         firstFreePage = paddr;
 208
 209         LOG("Clearing multi bitmap");
 210         // Fill the bitmaps
 211         memset(gaMultiBitmap, 0, (numPages<<12)/8);
 212         // - initialise to one, then clear the avaliable areas
 213         memset(gaMainBitmap, -1, (numPages<<12)/8);
 214         memset(gaSuperBitmap, -1, (numPages<<12)/(8*64));
 215         LOG("Setting main bitmap");
 216         // - Clear all Type=1 areas
 217         LOG("Clearing valid regions");
 218         for(
 219                 ent = mmapStart;
 220                 (Uint)ent < (Uint)mmapStart + MBoot->MMapLength;
 221                 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size )
 222                 )
 223         {
 224                 // Check if the type is RAM
 225                 if(ent->Type != 1)      continue;
 226
 227                 // Main bitmap
 228                 base = ent->Base >> 12;
 229                 size = ent->Size >> 12;
 230
 231                 if(base & 63) {
 232                         Uint64  val = -1LL << (base & 63);
 233                         gaMainBitmap[base / 64] &= ~val;
 234                         size -= (base & 63);
 235                         base += 64 - (base & 63);
 236                 }
 237                 memset( &gaMainBitmap[base / 64], 0, size/8 );
 238                 if( size & 7 ) {
 239                         Uint64  val = -1LL << (size & 7);
 240                         val <<= (size/8)&7;
 241                         gaMainBitmap[base / 64] &= ~val;
 242                 }
 243
 244                 // Super Bitmap
 245                 base = ent->Base >> 12;
 246                 size = ent->Size >> 12;
 247                 size = (size + (base & 63) + 63) >> 6;
 248                 base = base >> 6;
 249                 if(base & 63) {
 250                         Uint64  val = -1LL << (base & 63);
 251                         gaSuperBitmap[base / 64] &= ~val;
 252                         size -= (base & 63);
 253                         base += 64 - (base & 63);
 254                 }
 255         }
 256
 257         // Reference the used pages
 258         base = (tPAddr)&gKernelBase >> 12;
 259         size = firstFreePage >> 12;
 260         memset( &gaMainBitmap[base / 64], -1, size/8 );
 261         if( size & 7 ) {
 262                 Uint64  val = -1LL << (size & 7);
 263                 val <<= (size/8)&7;
 264                 gaMainBitmap[base / 64] |= val;
 265         }
 266
 267         // Free the unused static allocs
 268         for( i = 0; i < NUM_STATIC_ALLOC; i++) {
 269                 if(gaiStaticAllocPages[i] != 0)
 270                         continue;
 271                 gaMainBitmap[ gaiStaticAllocPages[i] >> (12+6) ]
 272                         &= ~(1LL << ((gaiStaticAllocPages[i]>>12)&63));
 273         }
 274
 275         // Fill the super bitmap
 276         LOG("Filling super bitmap");
 277         memset(gaSuperBitmap, 0, superPages<<12);
 278         for( base = 0; base < (size+63)/64; base ++)
 279         {
 280                 if( gaMainBitmap[ base ] + 1 == 0 )
 281                         gaSuperBitmap[ base/64 ] |= 1LL << (base&63);
 282         }
 283
 284         // Set free page counts
 285         for( base = 1; base < giMaxPhysPage; base ++ )
 286         {
 287                  int    rangeID;
 288                 // Skip allocated
 289                 if( gaMainBitmap[ base >> 6 ] & (1LL << (base&63))  )   continue;
 290
 291                 // Get range ID
 292                 rangeID = MM_int_GetRangeID( base << 12 );
 293
 294                 // Increment free page count
 295                 giPhysRangeFree[ rangeID ] ++;
 296
 297                 // Check for first free page in range
 298                 if(giPhysRangeFirst[ rangeID ] == 0)
 299                         giPhysRangeFirst[ rangeID ] = base;
 300                 // Set last (when the last free page is reached, this won't be
 301                 // updated anymore, hence will be correct)
 302                 giPhysRangeLast[ rangeID ] = base;
 303         }
 304
 305         LEAVE('-');
 306 }
 307
 308 /**
 309  * \brief Allocate a contiguous range of physical pages with a maximum
 310  *        bit size of \a MaxBits
 311  * \param Pages Number of pages to allocate
 312  * \param MaxBits       Maximum size of the physical address
 313  * \note If \a MaxBits is <= 0, any sized address is used (with preference
 314  *       to higher addresses)
 315  */
 316 tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
 317 {
 318         tPAddr  addr, ret;
 319          int    rangeID;
 320          int    nFree = 0, i;
 321
 322         ENTER("iPages iBits", Pages, MaxBits);
 323
 324         if( MaxBits <= 0 || MaxBits >= 64 )     // Speedup for the common case
 325                 rangeID = MM_PHYS_MAX;
 326         else
 327                 rangeID = MM_int_GetRangeID( (1LL << MaxBits) - 1 );
 328
 329         LOG("rangeID = %i", rangeID);
 330
 331         Mutex_Acquire(&glPhysicalPages);
 332
 333         // Check if the range actually has any free pages
 334         while(giPhysRangeFree[rangeID] == 0 && rangeID)
 335                 rangeID --;
 336
 337         LOG("rangeID = %i", rangeID);
 338
 339         // What the? Oh, man. No free pages
 340         if(giPhysRangeFree[rangeID] == 0) {
 341                 Mutex_Release(&glPhysicalPages);
 342                 // TODO: Page out
 343                 // ATM. Just Warning
 344                 Warning(" MM_AllocPhysRange: Out of free pages");
 345                 Log_Warning("Arch",
 346                         "Out of memory (unable to fulfil request for %i pages), zero remaining",
 347                         Pages
 348                         );
 349                 LEAVE('i', 0);
 350                 return 0;
 351         }
 352
 353         // Check if there is enough in the range
 354         if(giPhysRangeFree[rangeID] >= Pages)
 355         {
 356                 LOG("{%i,0x%x -> 0x%x}",
 357                         giPhysRangeFree[rangeID],
 358                         giPhysRangeFirst[rangeID], giPhysRangeLast[rangeID]
 359                         );
 360                 // Do a cheap scan, scanning upwards from the first free page in
 361                 // the range
 362                 nFree = 0;
 363                 addr = giPhysRangeFirst[ rangeID ];
 364                 while( addr <= giPhysRangeLast[ rangeID ] )
 365                 {
 366                         //Log(" MM_AllocPhysRange: addr = 0x%x", addr);
 367                         // Check the super bitmap
 368                         if( gaSuperBitmap[addr >> (6+6)] + 1 == 0 ) {
 369                                 LOG("nFree = %i = 0 (super) (0x%x)", nFree, addr);
 370                                 nFree = 0;
 371                                 addr += 1LL << (6+6);
 372                                 addr &= ~0xFFF; // (1LL << 6+6) - 1
 373                                 continue;
 374                         }
 375                         // Check page block (64 pages)
 376                         if( gaMainBitmap[addr >> 6] + 1 == 0) {
 377                                 LOG("nFree = %i = 0 (main) (0x%x)", nFree, addr);
 378                                 nFree = 0;
 379                                 addr += 1LL << (6);
 380                                 addr &= ~0x3F;
 381                                 continue;
 382                         }
 383                         // Check individual page
 384                         if( gaMainBitmap[addr >> 6] & (1LL << (addr & 63)) ) {
 385                                 LOG("nFree = %i = 0 (page) (0x%x)", nFree, addr);
 386                                 nFree = 0;
 387                                 addr ++;
 388                                 continue;
 389                         }
 390                         nFree ++;
 391                         addr ++;
 392                         LOG("nFree(%i) == %i (0x%x)", nFree, Pages, addr);
 393                         if(nFree == Num)
 394                                 break;
 395                 }
 396                 LOG("nFree = %i", nFree);
 397                 // If we don't find a contiguous block, nFree will not be equal
 398                 // to Num, so we set it to zero and do the expensive lookup.
 399                 if(nFree != Pages)      nFree = 0;
 400         }
 401
 402         if( !nFree )
 403         {
 404                 // Oops. ok, let's do an expensive check (scan down the list
 405                 // until a free range is found)
 406                 nFree = 1;
 407                 addr = giPhysRangeLast[ rangeID ];
 408                 // TODO
 409                 Mutex_Release(&glPhysicalPages);
 410                 // TODO: Page out
 411                 // ATM. Just Warning
 412                 Warning(" MM_AllocPhysRange: Out of memory (unable to fulfil request for %i pages)", Num);
 413                 Log_Warning("Arch",
 414                         "Out of memory (unable to fulfil request for %i pages)",
 415                         Num
 416                         );
 417                 LEAVE('i', 0);
 418                 return 0;
 419         }
 420         LOG("nFree = %i, addr = 0x%08x", nFree, addr);
 421
 422         // Mark pages as allocated
 423         addr -= Pages;
 424         for( i = 0; i < Pages; i++, addr++ )
 425         {
 426                 gaMainBitmap[addr >> 6] |= 1LL << (addr & 63);
 427                 rangeID = MM_int_GetRangeID(addr << 12);
 428                 giPhysRangeFree[ rangeID ] --;
 429                 LOG("%x == %x", addr, giPhysRangeFirst[ rangeID ]);
 430                 if(addr == giPhysRangeFirst[ rangeID ])
 431                         giPhysRangeFirst[ rangeID ] += 1;
 432         }
 433         ret = addr;     // Save the return address
 434
 435         // Update super bitmap
 436         Pages += addr & (64-1);
 437         addr &= ~(64-1);
 438         Pages = (Pages + (64-1)) & ~(64-1);
 439         for( i = 0; i < Pages/64; i++ )
 440         {
 441                 if( gaMainBitmap[ addr >> 6 ] + 1 == 0 )
 442                         gaSuperBitmap[addr>>12] |= 1LL << ((addr >> 6) & 63);
 443         }
 444
 445         Mutex_Release(&glPhysicalPages);
 446         LEAVE('x', ret << 12);
 447         return ret << 12;
 448 }
 449
 450 /**
 451  * \brief Allocate a single physical page, with no preference as to address
 452  *        size.
 453  */
 454 tPAddr MM_AllocPhys(void)
 455 {
 456          int    i;
 457
 458         // Hack to allow allocation during setup
 459         for(i = 0; i < NUM_STATIC_ALLOC; i++) {
 460                 if( gaiStaticAllocPages[i] ) {
 461                         tPAddr  ret = gaiStaticAllocPages[i];
 462                         gaiStaticAllocPages[i] = 0;
 463                         Log("MM_AllocPhys: Return %x, static alloc %i", ret, i);
 464                         return ret;
 465                 }
 466         }
 467
 468         return MM_AllocPhysRange(1, -1);
 469 }
 470
 471 /**
 472  * \brief Reference a physical page
 473  */
 474 void MM_RefPhys(tPAddr PAddr)
 475 {
 476         Uint64  page = PAddr >> 12;
 477
 478         if( PAddr >> 12 > giMaxPhysPage )       return ;
 479
 480         if( gaMainBitmap[ page >> 6 ] & (1LL << (page&63)) )
 481         {
 482                 // Reference again
 483                 gaMultiBitmap[ page >> 6 ] |= 1LL << (page&63);
 484                 gaiPageReferences[ page ] ++;
 485         }
 486         else
 487         {
 488                 // Allocate
 489                 gaMainBitmap[page >> 6] |= 1LL << (page&63);
 490                 if( gaMainBitmap[page >> 6 ] + 1 == 0 )
 491                         gaSuperBitmap[page>> 12] |= 1LL << ((page >> 6) & 63);
 492         }
 493 }
 494
 495 /**
 496  * \brief Dereference a physical page
 497  */
 498 void MM_DerefPhys(tPAddr PAddr)
 499 {
 500         Uint64  page = PAddr >> 12;
 501
 502         if( PAddr >> 12 > giMaxPhysPage )       return ;
 503
 504         if( gaMultiBitmap[ page >> 6 ] & (1LL << (page&63)) ) {
 505                 gaiPageReferences[ page ] --;
 506                 if( gaiPageReferences[ page ] == 1 )
 507                         gaMultiBitmap[ page >> 6 ] &= ~(1LL << (page&63));
 508                 if( gaiPageReferences[ page ] == 0 )
 509                         gaMainBitmap[ page >> 6 ] &= ~(1LL << (page&63));
 510         }
 511         else
 512                 gaMainBitmap[ page >> 6 ] &= ~(1LL << (page&63));
 513
 514         // Update the free counts if the page was freed
 515         if( !(gaMainBitmap[ page >> 6 ] & (1LL << (page&63))) )
 516         {
 517                  int    rangeID;
 518                 rangeID = MM_int_GetRangeID( PAddr );
 519                 giPhysRangeFree[ rangeID ] ++;
 520                 if( giPhysRangeFirst[rangeID] > page )
 521                         giPhysRangeFirst[rangeID] = page;
 522                 if( giPhysRangeLast[rangeID] < page )
 523                         giPhysRangeLast[rangeID] = page;
 524         }
 525
 526         // If the bitmap entry is not -1, unset the bit in the super bitmap
 527         if(gaMainBitmap[ page >> 6 ] + 1 != 0 ) {
 528                 gaSuperBitmap[page >> 12] &= ~(1LL << ((page >> 6) & 63));
 529         }
 530 }
 531
 532 /**
 533  * \brief Takes a physical address and returns the ID of its range
 534  * \param Addr  Physical address of page
 535  * \return Range ID from eMMPhys_Ranges
 536  */
 537 int MM_int_GetRangeID( tPAddr Addr )
 538 {
 539         if(Addr >> 32)
 540                 return MM_PHYS_MAX;
 541         else if(Addr >> 24)
 542                 return MM_PHYS_32BIT;
 543         else if(Addr >> 20)
 544                 return MM_PHYS_24BIT;
 545         else if(Addr >> 16)
 546                 return MM_PHYS_20BIT;
 547         else
 548                 return MM_PHYS_16BIT;
 549 }