mm_phys.c

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