KernelLand/Kernel/arch/x86/mm_phys.c

   1 /*
   2  * Acess2
   3  * - Physical memory manager
   4  */
   5 #define DEBUG   0
   6 #include <acess.h>
   7 #include <mboot.h>
   8 #include <mm_virt.h>
   9
  10 //#define USE_STACK     1
  11 #define TRACE_ALLOCS    0       // Print trace messages on AllocPhys/DerefPhys
  12
  13 static const int addrClasses[] = {0,16,20,24,32,64};
  14 static const int numAddrClasses = sizeof(addrClasses)/sizeof(addrClasses[0]);
  15
  16 // === IMPORTS ===
  17 extern char     gKernelEnd[];
  18 extern void     Proc_PrintBacktrace(void);
  19
  20 // === PROTOTYPES ===
  21 void    MM_Install(tMBoot_Info *MBoot);
  22 //tPAddr        MM_AllocPhys(void);
  23 //tPAddr        MM_AllocPhysRange(int Pages, int MaxBits);
  24 //void  MM_RefPhys(tPAddr PAddr);
  25 //void  MM_DerefPhys(tPAddr PAddr);
  26 // int  MM_GetRefCount(tPAddr PAddr);
  27
  28 // === GLOBALS ===
  29 tMutex  glPhysAlloc;
  30 Uint64  giPhysAlloc = 0;        // Number of allocated pages
  31 Uint64  giPageCount = 0;        // Total number of pages
  32 Uint64  giLastPossibleFree = 0; // Last possible free page (before all pages are used)
  33 Uint64  giTotalMemorySize = 0;  // Total number of allocatable pages
  34
  35 Uint32  gaSuperBitmap[1024];    // Blocks of 1024 Pages
  36 Uint32  gaPageBitmap[1024*1024/32];     // Individual pages
  37  int    *gaPageReferences;
  38 void    **gaPageNodes = (void*)MM_PAGENODE_BASE;
  39 #define REFENT_PER_PAGE (0x1000/sizeof(gaPageReferences[0]))
  40
  41 // === CODE ===
  42 void MM_Install(tMBoot_Info *MBoot)
  43 {
  44         Uint    kernelPages, num;
  45         Uint    i;
  46         Uint64  maxAddr = 0;
  47         tMBoot_Module   *mods;
  48         tMBoot_MMapEnt  *ent;
  49
  50         // --- Find largest address
  51         MBoot->MMapAddr |= KERNEL_BASE;
  52         ent = (void *)( MBoot->MMapAddr );
  53         while( (Uint)ent < MBoot->MMapAddr + MBoot->MMapLength )
  54         {
  55                 // Adjust for size
  56                 ent->Size += 4;
  57
  58                 // If entry is RAM and is above `maxAddr`, change `maxAddr`
  59                 if(ent->Type == 1)
  60                 {
  61                         if(ent->Base + ent->Length > maxAddr)
  62                                 maxAddr = ent->Base + ent->Length;
  63                         giTotalMemorySize += ent->Length >> 12;
  64                 }
  65                 // Go to next entry
  66                 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size );
  67         }
  68
  69         if(maxAddr == 0) {
  70                 giPageCount = (MBoot->HighMem >> 2) + 256;      // HighMem is a kByte value
  71         }
  72         else {
  73                 giPageCount = maxAddr >> 12;
  74         }
  75         giLastPossibleFree = giPageCount - 1;
  76
  77         memsetd(gaPageBitmap, 0xFFFFFFFF, giPageCount/32);
  78
  79         // Set up allocateable space
  80         ent = (void *)( MBoot->MMapAddr );
  81         while( (Uint)ent < MBoot->MMapAddr + MBoot->MMapLength )
  82         {
  83                 memsetd( &gaPageBitmap[ent->Base/(4096*32)], 0, ent->Length/(4096*32) );
  84                 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size );
  85         }
  86
  87         // Get used page count (Kernel)
  88         kernelPages = (Uint)&gKernelEnd - KERNEL_BASE - 0x100000;
  89         kernelPages += 0xFFF;   // Page Align
  90         kernelPages >>= 12;
  91         giPhysAlloc += kernelPages;     // Add to used count
  92
  93         // Fill page bitmap
  94         num = kernelPages/32;
  95         memsetd( &gaPageBitmap[0x100000/(4096*32)], -1, num );
  96         gaPageBitmap[ 0x100000/(4096*32) + num ] = (1 << (kernelPages & 31)) - 1;
  97
  98         // Fill Superpage bitmap
  99         num = kernelPages/(32*32);
 100         memsetd( &gaSuperBitmap[0x100000/(4096*32*32)], -1, num );
 101         gaSuperBitmap[ 0x100000/(4096*32*32) + num ] = (1 << ((kernelPages / 32) & 31)) - 1;
 102
 103         // Mark Multiboot's pages as taken
 104         // - Structure
 105         MM_RefPhys( (Uint)MBoot - KERNEL_BASE );
 106         // - Module List
 107         for(i = (MBoot->ModuleCount*sizeof(tMBoot_Module)+0xFFF)>12; i--; )
 108                 MM_RefPhys( MBoot->Modules + (i << 12) );
 109         // - Modules
 110         mods = (void*)(MBoot->Modules + KERNEL_BASE);
 111         for(i = 0; i < MBoot->ModuleCount; i++)
 112         {
 113                 num = (mods[i].End - mods[i].Start + 0xFFF) >> 12;
 114                 while(num--)
 115                         MM_RefPhys( (mods[i].Start & ~0xFFF) + (num<<12) );
 116         }
 117
 118         gaPageReferences = (void*)MM_REFCOUNT_BASE;
 119
 120         Log_Log("PMem", "Physical memory set up (%lli pages of ~%lli MiB used)",
 121                 giPhysAlloc, (giTotalMemorySize*4)/1024
 122                 );
 123 }
 124
 125 void MM_DumpStatistics(void)
 126 {
 127          int    i, pg;
 128         for( i = 1; i < numAddrClasses; i ++ )
 129         {
 130                  int    first = (i == 1 ? 0 : (1UL << (addrClasses[i-1] - 12)));
 131                  int    last  = (1UL << (addrClasses[i] - 12)) - 1;
 132                  int    nFree = 0;
 133                  int    nMultiRef = 0;
 134                  int    totalRefs = 0;
 135
 136                 if( last > giPageCount )
 137                         last = giPageCount;
 138
 139                  int    total = last - first + 1;
 140
 141                 for( pg = first; pg < last; pg ++ )
 142                 {
 143                         if( !MM_GetPhysAddr(&gaPageReferences[pg]) || gaPageReferences[pg] == 0 ) {
 144                                 nFree ++;
 145                                 continue ;
 146                         }
 147                         totalRefs += gaPageReferences[pg];
 148                         if(gaPageReferences[pg] > 1)
 149                                 nMultiRef ++;
 150                 }
 151
 152                  int    nUsed = (total - nFree);
 153                 Log_Log("MMPhys", "%ipbit - %i/%i used, %i reused, %i average reference count",
 154                         addrClasses[i], nUsed, total, nMultiRef,
 155                         nMultiRef ? (totalRefs-(nUsed - nMultiRef)) / nMultiRef : 0
 156                         );
 157
 158                 if( last == giPageCount )
 159                         break;
 160         }
 161         Log_Log("MMPhys", "%lli/%lli total pages used, 0 - %i possible free range",
 162                 giPhysAlloc, giTotalMemorySize, giLastPossibleFree);
 163 }
 164
 165 /**
 166  * \fn tPAddr MM_AllocPhys(void)
 167  * \brief Allocates a physical page from the general pool
 168  */
 169 tPAddr MM_AllocPhys(void)
 170 {
 171         // int  a, b, c;
 172          int    indx = -1;
 173         tPAddr  ret;
 174
 175         ENTER("");
 176
 177         Mutex_Acquire( &glPhysAlloc );
 178
 179         // Classful scan
 180         #if 1
 181         {
 182          int    i;
 183          int    first, last;
 184         for( i = numAddrClasses; i -- > 1; )
 185         {
 186                 first = 1UL << (addrClasses[i-1] - 12);
 187                 last = (1UL << (addrClasses[i] - 12)) - 1;
 188                 // Range is above the last free page
 189                 if( first > giLastPossibleFree )
 190                         continue;
 191                 // Last possible free page is in the range
 192                 if( last > giLastPossibleFree )
 193                         last = giLastPossibleFree;
 194
 195                 // Scan the range
 196                 for( indx = first; indx < last; )
 197                 {
 198                         if( gaSuperBitmap[indx>>10] == -1 ) {
 199                                 indx += 1024;
 200                                 continue;
 201                         }
 202
 203                         if( gaPageBitmap[indx>>5] == -1 ) {
 204                                 indx += 32;
 205                                 continue;
 206                         }
 207
 208                         if( gaPageBitmap[indx>>5] & (1 << (indx&31)) ) {
 209                                 indx ++;
 210                                 continue;
 211                         }
 212                         break;
 213                 }
 214                 if( indx < last )       break;
 215
 216                 giLastPossibleFree = first;     // Well, we couldn't find any in this range
 217         }
 218         // Out of memory?
 219         if( i <= 1 )    indx = -1;
 220         }
 221         #elif 0
 222         // Find free page
 223         // Scan downwards
 224         LOG("giLastPossibleFree = %i", giLastPossibleFree);
 225         for( indx = giLastPossibleFree; indx >= 0; )
 226         {
 227                 if( gaSuperBitmap[indx>>10] == -1 ) {
 228                         indx -= 1024;
 229                         continue;
 230                 }
 231
 232                 if( gaPageBitmap[indx>>5] == -1 ) {
 233                         indx -= 32;
 234                         continue;
 235                 }
 236
 237                 if( gaPageBitmap[indx>>5] & (1 << (indx&31)) ) {
 238                         indx --;
 239                         continue;
 240                 }
 241                 break;
 242         }
 243         if( indx >= 0 )
 244                 giLastPossibleFree = indx;
 245         LOG("indx = %i", indx);
 246         #else
 247         c = giLastPossibleFree % 32;
 248         b = (giLastPossibleFree / 32) % 32;
 249         a = giLastPossibleFree / 1024;
 250
 251         LOG("a=%i,b=%i,c=%i", a, b, c);
 252         for( ; gaSuperBitmap[a] == -1 && a >= 0; a-- );
 253         if(a < 0) {
 254                 Mutex_Release( &glPhysAlloc );
 255                 Warning("MM_AllocPhys - OUT OF MEMORY (Called by %p) - %lli/%lli used",
 256                         __builtin_return_address(0), giPhysAlloc, giPageCount);
 257                 LEAVE('i', 0);
 258                 return 0;
 259         }
 260         for( ; gaSuperBitmap[a] & (1<<b); b-- );
 261         for( ; gaPageBitmap[a*32+b] & (1<<c); c-- );
 262         LOG("a=%i,b=%i,c=%i", a, b, c);
 263         indx = (a << 10) | (b << 5) | c;
 264         if( indx >= 0 )
 265                 giLastPossibleFree = indx;
 266         #endif
 267
 268         if( indx < 0 ) {
 269                 Mutex_Release( &glPhysAlloc );
 270                 Warning("MM_AllocPhys - OUT OF MEMORY (Called by %p) - %lli/%lli used (indx = %x)",
 271                         __builtin_return_address(0), giPhysAlloc, giPageCount, indx);
 272                 Log_Debug("PMem", "giLastPossibleFree = %lli", giLastPossibleFree);
 273                 LEAVE('i', 0);
 274                 return 0;
 275         }
 276
 277         if( indx > 0xFFFFF ) {
 278                 Panic("The fuck? Too many pages! (indx = 0x%x)", indx);
 279         }
 280
 281         if( indx >= giPageCount ) {
 282                 Mutex_Release( &glPhysAlloc );
 283                 Log_Error("PMem", "MM_AllocPhys - indx(%i) > giPageCount(%i)", indx, giPageCount);
 284                 LEAVE('i', 0);
 285                 return 0;
 286         }
 287
 288         // Mark page used
 289         if( MM_GetPhysAddr( (tVAddr)&gaPageReferences[indx] ) )
 290                 gaPageReferences[indx] = 1;
 291         gaPageBitmap[ indx>>5 ] |= 1 << (indx&31);
 292
 293         giPhysAlloc ++;
 294
 295         // Get address
 296         ret = indx << 12;
 297
 298         // Mark used block
 299         if(gaPageBitmap[ indx>>5 ] == -1) {
 300                 gaSuperBitmap[indx>>10] |= 1 << ((indx>>5)&31);
 301         }
 302
 303         // Release Spinlock
 304         Mutex_Release( &glPhysAlloc );
 305
 306         LEAVE('X', ret);
 307         #if TRACE_ALLOCS
 308         if( now() > 4000 ) {
 309         Log_Debug("PMem", "MM_AllocPhys: RETURN %P (%i free)", ret, giPageCount-giPhysAlloc);
 310         Proc_PrintBacktrace();
 311         }
 312         #endif
 313         return ret;
 314 }
 315
 316 /**
 317  * \fn tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
 318  * \brief Allocate a range of physical pages
 319  * \param Pages Number of pages to allocate
 320  * \param MaxBits       Maximum number of address bits to use
 321  */
 322 tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
 323 {
 324          int    a, b;
 325          int    i, idx, sidx;
 326         tPAddr  ret;
 327
 328         ENTER("iPages iMaxBits", Pages, MaxBits);
 329
 330         // Sanity Checks
 331         if(MaxBits < 0) {
 332                 LEAVE('i', 0);
 333                 return 0;
 334         }
 335         if(MaxBits > PHYS_BITS) MaxBits = PHYS_BITS;
 336
 337         // Lock
 338         Mutex_Acquire( &glPhysAlloc );
 339
 340         // Set up search state
 341         if( giLastPossibleFree > ((tPAddr)1 << (MaxBits-12)) ) {
 342                 sidx = (tPAddr)1 << (MaxBits-12);
 343         }
 344         else {
 345                 sidx = giLastPossibleFree;
 346         }
 347         idx = sidx / 32;
 348         sidx %= 32;
 349         b = idx % 32;
 350         a = idx / 32;
 351
 352         #if 0
 353         LOG("a=%i, b=%i, idx=%i, sidx=%i", a, b, idx, sidx);
 354
 355         // Find free page
 356         for( ; gaSuperBitmap[a] == -1 && a --; )        b = 31;
 357         if(a < 0) {
 358                 Mutex_Release( &glPhysAlloc );
 359                 Warning("MM_AllocPhysRange - OUT OF MEMORY (Called by %p)", __builtin_return_address(0));
 360                 LEAVE('i', 0);
 361                 return 0;
 362         }
 363         LOG("a = %i", a);
 364         for( ; gaSuperBitmap[a] & (1 << b); b-- )       sidx = 31;
 365         LOG("b = %i", b);
 366         idx = a * 32 + b;
 367         for( ; gaPageBitmap[idx] & (1 << sidx); sidx-- )
 368                 LOG("gaPageBitmap[%i] = 0x%08x", idx, gaPageBitmap[idx]);
 369
 370         LOG("idx = %i, sidx = %i", idx, sidx);
 371         #else
 372
 373         #endif
 374
 375         // Check if the gap is large enough
 376         while( idx >= 0 )
 377         {
 378                 // Find a free page
 379                 for( ; ; )
 380                 {
 381                         // Bulk Skip
 382                         if( gaPageBitmap[idx] == -1 ) {
 383                                 idx --;
 384                                 sidx = 31;
 385                                 continue;
 386                         }
 387
 388                         if( gaPageBitmap[idx] & (1 << sidx) ) {
 389                                 sidx --;
 390                                 if(sidx < 0) {  sidx = 31;      idx --; }
 391                                 if(idx < 0)     break;
 392                                 continue;
 393                         }
 394                         break;
 395                 }
 396                 if( idx < 0 )   break;
 397
 398                 // Check if it is a free range
 399                 for( i = 0; i < Pages; i++ )
 400                 {
 401                         // Used page? break
 402                         if( gaPageBitmap[idx] & (1 << sidx) )
 403                                 break;
 404
 405                         sidx --;
 406                         if(sidx < 0) {  sidx = 31;      idx --; }
 407                         if(idx < 0)     break;
 408                 }
 409
 410                 if( i == Pages )
 411                         break;
 412         }
 413
 414         // Check if an address was found
 415         if( idx < 0 ) {
 416                 Mutex_Release( &glPhysAlloc );
 417                 Warning("MM_AllocPhysRange - OUT OF MEMORY (Called by %p)", __builtin_return_address(0));
 418                 LEAVE('i', 0);
 419                 return 0;
 420         }
 421
 422         // Mark pages used
 423         for( i = 0; i < Pages; i++ )
 424         {
 425                 if( MM_GetPhysAddr( (tVAddr)&gaPageReferences[idx*32+sidx] ) )
 426                         gaPageReferences[idx*32+sidx] = 1;
 427                 gaPageBitmap[ idx ] |= 1 << sidx;
 428                 sidx ++;
 429                 giPhysAlloc ++;
 430                 if(sidx == 32) { sidx = 0;      idx ++; }
 431         }
 432
 433         // Get address
 434         ret = (idx << 17) | (sidx << 12);
 435
 436         // Mark used block
 437         if(gaPageBitmap[ idx ] == -1)   gaSuperBitmap[idx/32] |= 1 << (idx%32);
 438
 439         // Release Spinlock
 440         Mutex_Release( &glPhysAlloc );
 441
 442         LEAVE('X', ret);
 443         #if TRACE_ALLOCS
 444         Log_Debug("PMem", "MM_AllocPhysRange: RETURN 0x%llx-0x%llx (%i free)",
 445                 ret, ret + (1<<Pages)-1, giPageCount-giPhysAlloc);
 446         #endif
 447         return ret;
 448 }
 449
 450 /**
 451  * \fn void MM_RefPhys(tPAddr PAddr)
 452  */
 453 void MM_RefPhys(tPAddr PAddr)
 454 {
 455         // Get page number
 456         PAddr >>= 12;
 457
 458         // We don't care about non-ram pages
 459         if(PAddr >= giPageCount)        return;
 460
 461         // Lock Structures
 462         Mutex_Acquire( &glPhysAlloc );
 463
 464         // Reference the page
 465         if( gaPageReferences )
 466         {
 467                 if( MM_GetPhysAddr( (tVAddr)&gaPageReferences[PAddr] ) == 0 )
 468                 {
 469                          int    i, base;
 470                         tVAddr  addr = ((tVAddr)&gaPageReferences[PAddr]) & ~0xFFF;
 471 //                      Log_Debug("PMem", "MM_RefPhys: Allocating info for %X", PAddr);
 472                         Mutex_Release( &glPhysAlloc );
 473                         if( MM_Allocate( addr ) == 0 ) {
 474                                 Log_KernelPanic("PMem",
 475                                         "MM_RefPhys: Out of physical memory allocating info for %X",
 476                                         PAddr*PAGE_SIZE
 477                                         );
 478                         }
 479                         Mutex_Acquire( &glPhysAlloc );
 480
 481                         base = PAddr & ~(1024-1);
 482                         for( i = 0; i < 1024; i ++ ) {
 483                                 gaPageReferences[base + i] = (gaPageBitmap[(base+i)/32] & (1 << (base+i)%32)) ? 1 : 0;
 484                         }
 485                 }
 486                 gaPageReferences[ PAddr ] ++;
 487         }
 488
 489         // If not already used
 490         if( !(gaPageBitmap[ PAddr / 32 ] & 1 << (PAddr&31)) ) {
 491                 giPhysAlloc ++;
 492                 // Mark as used
 493                 gaPageBitmap[ PAddr / 32 ] |= 1 << (PAddr&31);
 494         }
 495
 496         // Mark used block
 497         if(gaPageBitmap[ PAddr / 32 ] == -1)
 498                 gaSuperBitmap[PAddr/1024] |= 1 << ((PAddr/32)&31);
 499
 500         // Release Spinlock
 501         Mutex_Release( &glPhysAlloc );
 502 }
 503
 504 /**
 505  * \fn void MM_DerefPhys(tPAddr PAddr)
 506  * \brief Dereferences a physical page
 507  */
 508 void MM_DerefPhys(tPAddr PAddr)
 509 {
 510         // Get page number
 511         PAddr >>= 12;
 512
 513         // We don't care about non-ram pages
 514         if(PAddr >= giPageCount)        return;
 515
 516         // Check if it is freed
 517         if( !(gaPageBitmap[PAddr / 32] & (1 << PAddr%32)) ) {
 518                 Log_Warning("MMVirt", "MM_DerefPhys - Non-referenced memory dereferenced");
 519                 return;
 520         }
 521
 522         // Lock Structures
 523         Mutex_Acquire( &glPhysAlloc );
 524
 525         if( giLastPossibleFree < PAddr )
 526                 giLastPossibleFree = PAddr;
 527
 528         // Dereference
 529         if( !MM_GetPhysAddr( (tVAddr)&gaPageReferences[PAddr] ) || (-- gaPageReferences[PAddr]) == 0 )
 530         {
 531                 #if TRACE_ALLOCS
 532                 Log_Debug("PMem", "MM_DerefPhys: Free'd %P (%i free)", PAddr<<12, giPageCount-giPhysAlloc);
 533                 Proc_PrintBacktrace();
 534                 #endif
 535                 //LOG("Freed 0x%x by %p\n", PAddr<<12, __builtin_return_address(0));
 536                 giPhysAlloc --;
 537                 gaPageBitmap[ PAddr / 32 ] &= ~(1 << (PAddr&31));
 538                 if(gaPageBitmap[ PAddr / 32 ] == 0)
 539                         gaSuperBitmap[ PAddr >> 10 ] &= ~(1 << ((PAddr >> 5)&31));
 540
 541                 if( MM_GetPhysAddr( (tVAddr) &gaPageNodes[PAddr] ) )
 542                 {
 543                         gaPageNodes[PAddr] = NULL;
 544                         // TODO: Free Node Page when fully unused
 545                 }
 546         }
 547
 548         // Release spinlock
 549         Mutex_Release( &glPhysAlloc );
 550 }
 551
 552 /**
 553  * \fn int MM_GetRefCount(tPAddr Addr)
 554  */
 555 int MM_GetRefCount(tPAddr PAddr)
 556 {
 557         // Get page number
 558         PAddr >>= 12;
 559
 560         // We don't care about non-ram pages
 561         if(PAddr >= giPageCount)        return -1;
 562
 563         if( MM_GetPhysAddr( (tVAddr)&gaPageReferences[PAddr] ) == 0 )
 564                 return (gaPageBitmap[PAddr / 32] & (1 << PAddr%32)) ? 1 : 0;
 565
 566         // Check if it is freed
 567         return gaPageReferences[ PAddr ];
 568 }
 569
 570 int MM_SetPageNode(tPAddr PAddr, void *Node)
 571 {
 572         tVAddr  block_addr;
 573
 574         if( MM_GetRefCount(PAddr) == 0 )        return 1;
 575
 576         PAddr /= PAGE_SIZE;
 577
 578         block_addr = (tVAddr) &gaPageNodes[PAddr];
 579         block_addr &= ~(PAGE_SIZE-1);
 580
 581         if( !MM_GetPhysAddr( block_addr ) )
 582         {
 583                 if( !MM_Allocate( block_addr ) ) {
 584                         Log_Warning("PMem", "Unable to allocate Node page");
 585                         return -1;
 586                 }
 587                 memset( (void*)block_addr, 0, PAGE_SIZE );
 588         }
 589
 590         gaPageNodes[PAddr] = Node;
 591 //      Log("gaPageNodes[0x%x] = %p", PAddr, Node);
 592         return 0;
 593 }
 594
 595 int MM_GetPageNode(tPAddr PAddr, void **Node)
 596 {
 597         if( MM_GetRefCount(PAddr) == 0 )        return 1;
 598
 599         PAddr /= PAGE_SIZE;
 600         if( !MM_GetPhysAddr( (tVAddr) &gaPageNodes[PAddr] ) ) {
 601                 *Node = NULL;
 602                 return 0;
 603         }
 604         *Node = gaPageNodes[PAddr];
 605         return 0;
 606 }
 607