3 * - Physical memory manager
10 #include <semaphore.h>
11 #include <debug_hooks.h>
14 #define TRACE_ALLOCS 0 // Print trace messages on AllocPhys/DerefPhys
16 static const int addrClasses[] = {0,16,20,24,32,64};
17 static const int numAddrClasses = sizeof(addrClasses)/sizeof(addrClasses[0]);
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);
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
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]))
41 void MM_Install(int NPMemRanges, tPMemMapEnt *PMemRanges)
45 // --- Find largest address
46 for( Uint i = 0; i < NPMemRanges; i ++ )
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)
52 if(ent->Start + ent->Length > maxAddr)
53 maxAddr = ent->Start + ent->Length;
54 giTotalMemorySize += ent->Length >> 12;
57 LOG("giTotalMemorySize = %lli KiB", giTotalMemorySize*4);
58 LOG("maxAddr = 0x%X", maxAddr);
61 if( maxAddr > (1ULL << 32) ) {
62 maxAddr = (1ULL << 32);
65 giPageCount = maxAddr >> 12;
66 giLastPossibleFree = giPageCount - 1;
67 memsetd(gaPageBitmap, 0xFFFFFFFF, giPageCount/32);
69 // Set up allocateable space
70 for( Uint i = 0; i < NPMemRanges; i ++ )
72 tPMemMapEnt *ent = &PMemRanges[i];
73 if( ent->Type == PMEMTYPE_FREE )
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) )
80 // Clip lengths to 32-bit address space
81 if( startpg + pgcount > (1<<20) )
82 pgcount = (1<<20) - startpg;
84 while( startpg % 32 && pgcount ) {
85 gaPageBitmap[startpg/32] &= ~(1U << (startpg%32));
89 memsetd( &gaPageBitmap[startpg/32], 0, pgcount/32 );
90 startpg += pgcount - pgcount%32;
91 pgcount -= pgcount - pgcount%32;
93 gaPageBitmap[startpg/32] &= ~(1U << (startpg%32));
98 else if( ent->Type == PMEMTYPE_USED )
101 giPhysAlloc += ent->Length / PAGE_SIZE;
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 ++ )
109 if( gaPageBitmap[i] + 1 == 0 ) {
110 gaSuperBitmap[i/32] |= (1 << i%32);
114 gaPageReferences = (void*)MM_REFCOUNT_BASE;
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)
122 void MM_DumpStatistics(void)
125 for( i = 1; i < numAddrClasses; i ++ )
127 int first = (i == 1 ? 0 : (1UL << (addrClasses[i-1] - 12)));
128 int last = (1UL << (addrClasses[i] - 12)) - 1;
133 if( last > giPageCount )
136 int total = last - first + 1;
138 for( pg = first; pg < last; pg ++ )
140 if( !MM_GetPhysAddr(&gaPageReferences[pg]) || gaPageReferences[pg] == 0 ) {
144 totalRefs += gaPageReferences[pg];
145 if(gaPageReferences[pg] > 1)
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
155 if( last == giPageCount )
158 Log_Log("MMPhys", "%lli/%lli total pages used, 0 - %i possible free range",
159 giPhysAlloc, giTotalMemorySize, giLastPossibleFree);
163 * \fn tPAddr MM_AllocPhys(void)
164 * \brief Allocates a physical page from the general pool
166 tPAddr MM_AllocPhys(void)
173 Mutex_Acquire( &glPhysAlloc );
179 for( i = numAddrClasses; i -- > 1; )
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 )
186 // Last possible free page is in the range
187 if( last > giLastPossibleFree )
188 last = giLastPossibleFree;
191 for( indx = first; indx < last; )
193 if( gaSuperBitmap[indx>>10] == -1 ) {
198 if( gaPageBitmap[indx>>5] == -1 ) {
203 if( gaPageBitmap[indx>>5] & (1 << (indx&31)) ) {
209 if( indx < last ) break;
211 giLastPossibleFree = first; // Well, we couldn't find any in this range
214 if( i <= 1 ) indx = -1;
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);
226 if( indx > 0xFFFFF ) {
227 Panic("The fuck? Too many pages! (indx = 0x%x)", indx);
230 if( indx >= giPageCount ) {
231 Mutex_Release( &glPhysAlloc );
232 Log_Error("PMem", "MM_AllocPhys - indx(%i) > giPageCount(%i)", indx, giPageCount);
238 if( MM_GetPhysAddr( &gaPageReferences[indx] ) )
239 gaPageReferences[indx] = 1;
240 gaPageBitmap[ indx>>5 ] |= 1 << (indx&31);
248 if(gaPageBitmap[ indx>>5 ] == -1) {
249 gaSuperBitmap[indx>>10] |= 1 << ((indx>>5)&31);
253 Mutex_Release( &glPhysAlloc );
258 Log_Debug("PMem", "MM_AllocPhys: RETURN %P (%i free)", ret, giPageCount-giPhysAlloc);
259 Proc_PrintBacktrace();
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
271 tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
276 ENTER("iPages iMaxBits", Pages, MaxBits);
283 if(MaxBits > PHYS_BITS) MaxBits = PHYS_BITS;
286 Mutex_Acquire( &glPhysAlloc );
288 // Set up search state
289 if( giLastPossibleFree > ((tPAddr)1 << (MaxBits-12)) ) {
290 sidx = (tPAddr)1 << (MaxBits-12);
293 sidx = giLastPossibleFree;
298 // Check if the gap is large enough
305 if( gaPageBitmap[idx] == -1 ) {
311 if( gaPageBitmap[idx] & (1 << sidx) ) {
313 if(sidx < 0) { sidx = 31; idx --; }
321 // Check if it is a free range
322 for( i = 0; i < Pages; i++ )
325 if( gaPageBitmap[idx] & (1 << sidx) )
329 if(sidx < 0) { sidx = 31; idx --; }
337 // Check if an address was found
339 Mutex_Release( &glPhysAlloc );
340 Warning("MM_AllocPhysRange - OUT OF MEMORY (Called by %p)", __builtin_return_address(0));
346 for( i = 0; i < Pages; i++ )
348 if( MM_GetPhysAddr( &gaPageReferences[idx*32+sidx] ) )
349 gaPageReferences[idx*32+sidx] = 1;
350 gaPageBitmap[ idx ] |= 1 << sidx;
353 if(sidx == 32) { sidx = 0; idx ++; }
357 ret = (idx << 17) | (sidx << 12);
360 if(gaPageBitmap[ idx ] == -1) gaSuperBitmap[idx/32] |= 1 << (idx%32);
363 Mutex_Release( &glPhysAlloc );
367 Log_Debug("PMem", "MM_AllocPhysRange: RETURN 0x%llx-0x%llx (%i free)",
368 ret, ret + (1<<Pages)-1, giPageCount-giPhysAlloc);
374 * \fn void MM_RefPhys(tPAddr PAddr)
376 void MM_RefPhys(tPAddr PAddr)
381 // We don't care about non-ram pages
382 if(PAddr >= giPageCount) return;
385 Mutex_Acquire( &glPhysAlloc );
387 // Reference the page
388 if( gaPageReferences )
390 if( MM_GetPhysAddr( &gaPageReferences[PAddr] ) == 0 )
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 )
398 Log_KernelPanic("PMem",
399 "MM_RefPhys: Out of physical memory allocating info for %X",
404 Mutex_Acquire( &glPhysAlloc );
405 // TODO: Solve race condition. (see below)
406 // [1] See unallocated
417 // Populate (clobbering)
419 // Fill references from allocated bitmap
420 for( int i = 0; i < 1024; i ++ )
422 gaPageReferences[base + i] = (gaPageBitmap[(base+i)/32] & (1 << (base+i)%32)) ? 1 : 0;
425 gaPageReferences[ PAddr ] ++;
428 // If not already used
429 if( !(gaPageBitmap[ PAddr / 32 ] & 1 << (PAddr&31)) ) {
432 gaPageBitmap[ PAddr / 32 ] |= 1 << (PAddr&31);
436 if(gaPageBitmap[ PAddr / 32 ] == -1)
437 gaSuperBitmap[PAddr/1024] |= 1 << ((PAddr/32)&31);
440 Mutex_Release( &glPhysAlloc );
444 * \fn void MM_DerefPhys(tPAddr PAddr)
445 * \brief Dereferences a physical page
447 void MM_DerefPhys(tPAddr PAddr)
452 // We don't care about non-ram pages
453 if(PAddr >= giPageCount) return;
455 // Check if it is freed
456 if( !(gaPageBitmap[PAddr / 32] & (1 << PAddr%32)) ) {
457 Log_Warning("MMVirt", "MM_DerefPhys - Non-referenced memory dereferenced");
462 Mutex_Acquire( &glPhysAlloc );
464 if( giLastPossibleFree < PAddr )
465 giLastPossibleFree = PAddr;
468 if( !MM_GetPhysAddr( &gaPageReferences[PAddr] ) || (-- gaPageReferences[PAddr]) == 0 )
471 Log_Debug("PMem", "MM_DerefPhys: Free'd %P (%i free)", PAddr<<12, giPageCount-giPhysAlloc);
472 Proc_PrintBacktrace();
474 //LOG("Freed 0x%x by %p\n", PAddr<<12, __builtin_return_address(0));
476 gaPageBitmap[ PAddr / 32 ] &= ~(1 << (PAddr&31));
477 if(gaPageBitmap[ PAddr / 32 ] == 0)
478 gaSuperBitmap[ PAddr >> 10 ] &= ~(1 << ((PAddr >> 5)&31));
480 if( MM_GetPhysAddr( &gaPageNodes[PAddr] ) )
482 gaPageNodes[PAddr] = NULL;
483 // TODO: Free Node Page when fully unused
488 Mutex_Release( &glPhysAlloc );
492 * \fn int MM_GetRefCount(tPAddr Addr)
494 int MM_GetRefCount(tPAddr PAddr)
499 // We don't care about non-ram pages
500 if(PAddr >= giPageCount) return -1;
502 if( MM_GetPhysAddr( &gaPageReferences[PAddr] ) == 0 )
503 return (gaPageBitmap[PAddr / 32] & (1 << PAddr%32)) ? 1 : 0;
505 // Check if it is freed
506 return gaPageReferences[ PAddr ];
509 int MM_SetPageNode(tPAddr PAddr, void *Node)
511 if( MM_GetRefCount(PAddr) == 0 ) return 1;
515 void *page_ptr = (void*)( (tVAddr)&gaPageNodes[PAddr] & ~(PAGE_SIZE-1) );
517 if( !MM_GetPhysAddr( page_ptr ) )
519 if( !MM_Allocate( page_ptr ) ) {
520 Log_Warning("PMem", "Unable to allocate Node page");
523 memset( page_ptr, 0, PAGE_SIZE );
526 gaPageNodes[PAddr] = Node;
527 // Log("gaPageNodes[0x%x] = %p", PAddr, Node);
531 int MM_GetPageNode(tPAddr PAddr, void **Node)
533 if( MM_GetRefCount(PAddr) == 0 ) return 1;
536 if( !MM_GetPhysAddr( &gaPageNodes[PAddr] ) ) {
540 *Node = gaPageNodes[PAddr];