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 <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          int    i, pg;
 125         for( i = 1; i < numAddrClasses; i ++ )
 126         {
 127                  int    first = (i == 1 ? 0 : (1UL << (addrClasses[i-1] - 12)));
 128                  int    last  = (1UL << (addrClasses[i] - 12)) - 1;
 129                  int    nFree = 0;
 130                  int    nMultiRef = 0;
 131                  int    totalRefs = 0;
 132
 133                 if( last > giPageCount )
 134                         last = giPageCount;
 135
 136                  int    total = last - first + 1;
 137
 138                 for( pg = first; pg < last; pg ++ )
 139                 {
 140                         if( !MM_GetPhysAddr(&gaPageReferences[pg]) || gaPageReferences[pg] == 0 ) {
 141                                 nFree ++;
 142                                 continue ;
 143                         }
 144                         totalRefs += gaPageReferences[pg];
 145                         if(gaPageReferences[pg] > 1)
 146                                 nMultiRef ++;
 147                 }
 148
 149                  int    nUsed = (total - nFree);
 150                 Log_Log("MMPhys", "%ipbit - %i/%i used, %i reused, %i average reference count",
 151                         addrClasses[i], nUsed, total, nMultiRef,
 152                         nMultiRef ? (totalRefs-(nUsed - nMultiRef)) / nMultiRef : 0
 153                         );
 154
 155                 if( last == giPageCount )
 156                         break;
 157         }
 158         Log_Log("MMPhys", "%lli/%lli total pages used, 0 - %i possible free range",
 159                 giPhysAlloc, giTotalMemorySize, giLastPossibleFree);
 160 }
 161
 162 /**
 163  * \fn tPAddr MM_AllocPhys(void)
 164  * \brief Allocates a physical page from the general pool
 165  */
 166 tPAddr MM_AllocPhys(void)
 167 {
 168          int    indx = -1;
 169         tPAddr  ret;
 170
 171         ENTER("");
 172
 173         Mutex_Acquire( &glPhysAlloc );
 174
 175         // Classful scan
 176         {
 177          int    i;
 178          int    first, last;
 179         for( i = numAddrClasses; i -- > 1; )
 180         {
 181                 first = 1UL << (addrClasses[i-1] - 12);
 182                 last = (1UL << (addrClasses[i] - 12)) - 1;
 183                 // Range is above the last free page
 184                 if( first > giLastPossibleFree )
 185                         continue;
 186                 // Last possible free page is in the range
 187                 if( last > giLastPossibleFree )
 188                         last = giLastPossibleFree;
 189
 190                 // Scan the range
 191                 for( indx = first; indx < last; )
 192                 {
 193                         if( gaSuperBitmap[indx>>10] == -1 ) {
 194                                 indx += 1024;
 195                                 continue;
 196                         }
 197
 198                         if( gaPageBitmap[indx>>5] == -1 ) {
 199                                 indx += 32;
 200                                 continue;
 201                         }
 202
 203                         if( gaPageBitmap[indx>>5] & (1 << (indx&31)) ) {
 204                                 indx ++;
 205                                 continue;
 206                         }
 207                         break;
 208                 }
 209                 if( indx < last )       break;
 210
 211                 giLastPossibleFree = first;     // Well, we couldn't find any in this range
 212         }
 213         // Out of memory?
 214         if( i <= 1 )    indx = -1;
 215         }
 216
 217         if( indx < 0 ) {
 218                 Mutex_Release( &glPhysAlloc );
 219                 Warning("MM_AllocPhys - OUT OF MEMORY (Called by %p) - %lli/%lli used (indx = %x)",
 220                         __builtin_return_address(0), giPhysAlloc, giPageCount, indx);
 221                 Log_Debug("PMem", "giLastPossibleFree = %lli", giLastPossibleFree);
 222                 LEAVE('i', 0);
 223                 return 0;
 224         }
 225
 226         if( indx > 0xFFFFF ) {
 227                 Panic("The fuck? Too many pages! (indx = 0x%x)", indx);
 228         }
 229
 230         if( indx >= giPageCount ) {
 231                 Mutex_Release( &glPhysAlloc );
 232                 Log_Error("PMem", "MM_AllocPhys - indx(%i) > giPageCount(%i)", indx, giPageCount);
 233                 LEAVE('i', 0);
 234                 return 0;
 235         }
 236
 237         // Mark page used
 238         if( MM_GetPhysAddr( &gaPageReferences[indx] ) )
 239                 gaPageReferences[indx] = 1;
 240         gaPageBitmap[ indx>>5 ] |= 1 << (indx&31);
 241
 242         giPhysAlloc ++;
 243
 244         // Get address
 245         ret = indx << 12;
 246
 247         // Mark used block
 248         if(gaPageBitmap[ indx>>5 ] == -1) {
 249                 gaSuperBitmap[indx>>10] |= 1 << ((indx>>5)&31);
 250         }
 251
 252         // Release Spinlock
 253         Mutex_Release( &glPhysAlloc );
 254         LEAVE('P', ret);
 255
 256         #if TRACE_ALLOCS
 257         if( now() > 4000 ) {
 258         Log_Debug("PMem", "MM_AllocPhys: RETURN %P (%i free)", ret, giPageCount-giPhysAlloc);
 259         Proc_PrintBacktrace();
 260         }
 261         #endif
 262         return ret;
 263 }
 264
 265 /**
 266  * \fn tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
 267  * \brief Allocate a range of physical pages
 268  * \param Pages Number of pages to allocate
 269  * \param MaxBits       Maximum number of address bits to use
 270  */
 271 tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
 272 {
 273          int    i, idx, sidx;
 274         tPAddr  ret;
 275
 276         ENTER("iPages iMaxBits", Pages, MaxBits);
 277
 278         // Sanity Checks
 279         if(MaxBits < 0) {
 280                 LEAVE('i', 0);
 281                 return 0;
 282         }
 283         if(MaxBits > PHYS_BITS) MaxBits = PHYS_BITS;
 284
 285         // Lock
 286         Mutex_Acquire( &glPhysAlloc );
 287
 288         // Set up search state
 289         if( giLastPossibleFree > ((tPAddr)1 << (MaxBits-12)) ) {
 290                 sidx = (tPAddr)1 << (MaxBits-12);
 291         }
 292         else {
 293                 sidx = giLastPossibleFree;
 294         }
 295         idx = sidx / 32;
 296         sidx %= 32;
 297
 298         // Check if the gap is large enough
 299         while( idx >= 0 )
 300         {
 301                 // Find a free page
 302                 for( ; ; )
 303                 {
 304                         // Bulk Skip
 305                         if( gaPageBitmap[idx] == -1 ) {
 306                                 idx --;
 307                                 sidx = 31;
 308                                 continue;
 309                         }
 310
 311                         if( gaPageBitmap[idx] & (1 << sidx) ) {
 312                                 sidx --;
 313                                 if(sidx < 0) {  sidx = 31;      idx --; }
 314                                 if(idx < 0)     break;
 315                                 continue;
 316                         }
 317                         break;
 318                 }
 319                 if( idx < 0 )   break;
 320
 321                 // Check if it is a free range
 322                 for( i = 0; i < Pages; i++ )
 323                 {
 324                         // Used page? break
 325                         if( gaPageBitmap[idx] & (1 << sidx) )
 326                                 break;
 327
 328                         sidx --;
 329                         if(sidx < 0) {  sidx = 31;      idx --; }
 330                         if(idx < 0)     break;
 331                 }
 332
 333                 if( i == Pages )
 334                         break;
 335         }
 336
 337         // Check if an address was found
 338         if( idx < 0 ) {
 339                 Mutex_Release( &glPhysAlloc );
 340                 Warning("MM_AllocPhysRange - OUT OF MEMORY (Called by %p)", __builtin_return_address(0));
 341                 LEAVE('i', 0);
 342                 return 0;
 343         }
 344
 345         // Mark pages used
 346         for( i = 0; i < Pages; i++ )
 347         {
 348                 if( MM_GetPhysAddr( &gaPageReferences[idx*32+sidx] ) )
 349                         gaPageReferences[idx*32+sidx] = 1;
 350                 gaPageBitmap[ idx ] |= 1 << sidx;
 351                 sidx ++;
 352                 giPhysAlloc ++;
 353                 if(sidx == 32) { sidx = 0;      idx ++; }
 354         }
 355
 356         // Get address
 357         ret = (idx << 17) | (sidx << 12);
 358
 359         // Mark used block
 360         if(gaPageBitmap[ idx ] == -1)   gaSuperBitmap[idx/32] |= 1 << (idx%32);
 361
 362         // Release Spinlock
 363         Mutex_Release( &glPhysAlloc );
 364
 365         LEAVE('X', ret);
 366         #if TRACE_ALLOCS
 367         Log_Debug("PMem", "MM_AllocPhysRange: RETURN 0x%llx-0x%llx (%i free)",
 368                 ret, ret + (1<<Pages)-1, giPageCount-giPhysAlloc);
 369         #endif
 370         return ret;
 371 }
 372
 373 /**
 374  * \fn void MM_RefPhys(tPAddr PAddr)
 375  */
 376 void MM_RefPhys(tPAddr PAddr)
 377 {
 378         // Get page number
 379         PAddr >>= 12;
 380
 381         // We don't care about non-ram pages
 382         if(PAddr >= giPageCount)        return;
 383
 384         // Lock Structures
 385         Mutex_Acquire( &glPhysAlloc );
 386
 387         // Reference the page
 388         if( gaPageReferences )
 389         {
 390                 if( MM_GetPhysAddr( &gaPageReferences[PAddr] ) == 0 )
 391                 {
 392                         Uint base = PAddr & ~(1024-1);
 393                         Mutex_Release( &glPhysAlloc );
 394                         // No infinite recursion, AllocPhys doesn't need the reference array
 395                         // TODO: Race condition? (racy on populating)
 396                         if( MM_Allocate( &gaPageReferences[base] ) == 0 )
 397                         {
 398                                 Log_KernelPanic("PMem",
 399                                         "MM_RefPhys: Out of physical memory allocating info for %X",
 400                                         PAddr*PAGE_SIZE
 401                                         );
 402                                 for(;;);
 403                         }
 404                         Mutex_Acquire( &glPhysAlloc );
 405                         // TODO: Solve race condition. (see below)
 406                         // [1] See unallocated
 407                         //     Release lock
 408                         // [2] Acquire lock
 409                         //     See unallocated
 410                         //     Release lock
 411                         //     Allocate
 412                         // [1] Allocate
 413                         //     Acquire lock
 414                         //     Populate
 415                         //     Release lock
 416                         // [2] Acquire lock
 417                         //     Populate (clobbering)
 418
 419                         // Fill references from allocated bitmap
 420                         for( int i = 0; i < 1024; i ++ )
 421                         {
 422                                 gaPageReferences[base + i] = (gaPageBitmap[(base+i)/32] & (1 << (base+i)%32)) ? 1 : 0;
 423                         }
 424                 }
 425                 gaPageReferences[ PAddr ] ++;
 426         }
 427
 428         // If not already used
 429         if( !(gaPageBitmap[ PAddr / 32 ] & 1 << (PAddr&31)) ) {
 430                 giPhysAlloc ++;
 431                 // Mark as used
 432                 gaPageBitmap[ PAddr / 32 ] |= 1 << (PAddr&31);
 433         }
 434
 435         // Mark used block
 436         if(gaPageBitmap[ PAddr / 32 ] == -1)
 437                 gaSuperBitmap[PAddr/1024] |= 1 << ((PAddr/32)&31);
 438
 439         // Release Spinlock
 440         Mutex_Release( &glPhysAlloc );
 441 }
 442
 443 /**
 444  * \fn void MM_DerefPhys(tPAddr PAddr)
 445  * \brief Dereferences a physical page
 446  */
 447 void MM_DerefPhys(tPAddr PAddr)
 448 {
 449         // Get page number
 450         PAddr >>= 12;
 451
 452         // We don't care about non-ram pages
 453         if(PAddr >= giPageCount)        return;
 454
 455         // Check if it is freed
 456         if( !(gaPageBitmap[PAddr / 32] & (1 << PAddr%32)) ) {
 457                 Log_Warning("MMVirt", "MM_DerefPhys - Non-referenced memory dereferenced");
 458                 return;
 459         }
 460
 461         // Lock Structures
 462         Mutex_Acquire( &glPhysAlloc );
 463
 464         if( giLastPossibleFree < PAddr )
 465                 giLastPossibleFree = PAddr;
 466
 467         // Dereference
 468         if( !MM_GetPhysAddr( &gaPageReferences[PAddr] ) || (-- gaPageReferences[PAddr]) == 0 )
 469         {
 470                 #if TRACE_ALLOCS
 471                 Log_Debug("PMem", "MM_DerefPhys: Free'd %P (%i free)", PAddr<<12, giPageCount-giPhysAlloc);
 472                 Proc_PrintBacktrace();
 473                 #endif
 474                 //LOG("Freed 0x%x by %p\n", PAddr<<12, __builtin_return_address(0));
 475                 giPhysAlloc --;
 476                 gaPageBitmap[ PAddr / 32 ] &= ~(1 << (PAddr&31));
 477                 if(gaPageBitmap[ PAddr / 32 ] == 0)
 478                         gaSuperBitmap[ PAddr >> 10 ] &= ~(1 << ((PAddr >> 5)&31));
 479
 480                 if( MM_GetPhysAddr( &gaPageNodes[PAddr] ) )
 481                 {
 482                         gaPageNodes[PAddr] = NULL;
 483                         // TODO: Free Node Page when fully unused
 484                 }
 485         }
 486
 487         // Release spinlock
 488         Mutex_Release( &glPhysAlloc );
 489 }
 490
 491 /**
 492  * \fn int MM_GetRefCount(tPAddr Addr)
 493  */
 494 int MM_GetRefCount(tPAddr PAddr)
 495 {
 496         // Get page number
 497         PAddr >>= 12;
 498
 499         // We don't care about non-ram pages
 500         if(PAddr >= giPageCount)        return -1;
 501
 502         if( MM_GetPhysAddr( &gaPageReferences[PAddr] ) == 0 )
 503                 return (gaPageBitmap[PAddr / 32] & (1 << PAddr%32)) ? 1 : 0;
 504
 505         // Check if it is freed
 506         return gaPageReferences[ PAddr ];
 507 }
 508
 509 int MM_SetPageNode(tPAddr PAddr, void *Node)
 510 {
 511         if( MM_GetRefCount(PAddr) == 0 )        return 1;
 512
 513         PAddr /= PAGE_SIZE;
 514
 515         void *page_ptr = (void*)( (tVAddr)&gaPageNodes[PAddr] & ~(PAGE_SIZE-1) );
 516
 517         if( !MM_GetPhysAddr( page_ptr ) )
 518         {
 519                 if( !MM_Allocate( page_ptr ) ) {
 520                         Log_Warning("PMem", "Unable to allocate Node page");
 521                         return -1;
 522                 }
 523                 memset( page_ptr, 0, PAGE_SIZE );
 524         }
 525
 526         gaPageNodes[PAddr] = Node;
 527 //      Log("gaPageNodes[0x%x] = %p", PAddr, Node);
 528         return 0;
 529 }
 530
 531 int MM_GetPageNode(tPAddr PAddr, void **Node)
 532 {
 533         if( MM_GetRefCount(PAddr) == 0 )        return 1;
 534
 535         PAddr /= PAGE_SIZE;
 536         if( !MM_GetPhysAddr( &gaPageNodes[PAddr] ) ) {
 537                 *Node = NULL;
 538                 return 0;
 539         }
 540         *Node = gaPageNodes[PAddr];
 541         return 0;
 542 }
 543