4 * Physical Memory Manager
11 #include <debug_hooks.h>
17 MM_PHYS_16BIT, // Does anything need this?
18 MM_PHYS_20BIT, // Real-Mode
19 MM_PHYS_24BIT, // ISA DMA
20 MM_PHYS_32BIT, // x86 Hardware
21 MM_PHYS_MAX, // Doesn't care
26 extern char gKernelBase[];
27 extern char gKernelEnd[];
30 //void MM_InitPhys(int NPMemRanges, tPMemMapEnt *PMemRanges);
31 //tPAddr MM_AllocPhysRange(int Num, int Bits);
32 //tPAddr MM_AllocPhys(void);
33 //void MM_RefPhys(tPAddr PAddr);
34 //void MM_DerefPhys(tPAddr PAddr);
35 int MM_int_GetRangeID( tPAddr Addr );
38 #define PAGE_ALLOC_TEST(__page) (gaMainBitmap[(__page)>>6] & (1ULL << ((__page)&63)))
39 #define PAGE_ALLOC_SET(__page) do{gaMainBitmap[(__page)>>6] |= (1ULL << ((__page)&63));}while(0)
40 #define PAGE_ALLOC_CLEAR(__page) do{gaMainBitmap[(__page)>>6] &= ~(1ULL << ((__page)&63));}while(0)
41 //#define PAGE_MULTIREF_TEST(__page) (gaMultiBitmap[(__page)>>6] & (1ULL << ((__page)&63)))
42 //#define PAGE_MULTIREF_SET(__page) do{gaMultiBitmap[(__page)>>6] |= 1ULL << ((__page)&63);}while(0)
43 //#define PAGE_MULTIREF_CLEAR(__page) do{gaMultiBitmap[(__page)>>6] &= ~(1ULL << ((__page)&63));}while(0)
46 tMutex glPhysicalPages;
47 Uint64 *gaSuperBitmap = (void*)MM_PAGE_SUPBMP; // 1 bit = 64 Pages, 16 MiB per Word
48 Uint64 *gaMainBitmap = (void*)MM_PAGE_BITMAP; // 1 bit = 1 Page, 256 KiB per Word
49 Uint64 *gaMultiBitmap = (void*)MM_PAGE_DBLBMP; // Each bit means that the page is being used multiple times
50 Uint32 *gaiPageReferences = (void*)MM_PAGE_COUNTS; // Reference Counts
51 void **gapPageNodes = (void*)MM_PAGE_NODES; // Reference Counts
52 tPAddr giFirstFreePage; // First possibly free page
53 Uint64 giPhysRangeFree[NUM_MM_PHYS_RANGES]; // Number of free pages in each range
54 Uint64 giPhysRangeFirst[NUM_MM_PHYS_RANGES]; // First free page in each range
55 Uint64 giPhysRangeLast[NUM_MM_PHYS_RANGES]; // Last free page in each range
56 Uint64 giMaxPhysPage = 0; // Maximum Physical page
57 Uint64 giTotalMemorySize = 0;
58 // Only used in init, allows the init code to provide pages for use by
59 // the allocator before the bitmaps exist.
60 // 3 entries because the are three calls to MM_AllocPhys in MM_Map
61 #define NUM_STATIC_ALLOC 3
62 tPAddr gaiStaticAllocPages[NUM_STATIC_ALLOC] = {0};
66 * \brief Initialise the physical memory map using a Multiboot 1 map
68 void MM_InitPhys(int NPMemRanges, tPMemMapEnt *PMemRanges)
71 int numPages, superPages;
77 ENTER("iNPMemRanges pPMemRanges",
78 NPMemRanges, PMemRanges);
80 // Scan the physical memory map
81 // Looking for the top of physical memory
82 for( i = 0; i < NPMemRanges; i ++ )
84 tPMemMapEnt *ent = &PMemRanges[i];
85 // Adjust for the size of the entry
86 LOG("%i: ent={Type:%i,Base:0x%x,Length:%x}", i, ent->Type, ent->Start, ent->Length);
88 // If entry is RAM and is above `maxAddr`, change `maxAddr`
89 if(ent->Type == PMEMTYPE_FREE || ent->Type == PMEMTYPE_USED )
91 if( ent->Start + ent->Length > maxAddr)
92 maxAddr = ent->Start + ent->Length;
93 giTotalMemorySize += ent->Length >> 12;
97 giMaxPhysPage = maxAddr >> 12;
98 LOG("giMaxPhysPage = 0x%x", giMaxPhysPage);
100 // Get counts of pages needed for basic structures
101 superPages = ((giMaxPhysPage+64*8-1)/(64*8) + 0xFFF) >> 12;
102 numPages = ((giMaxPhysPage+7)/8 + 0xFFF) >> 12; // bytes to hold bitmap, divided up to nearest page
103 LOG("numPages = %i, superPages = %i", numPages, superPages);
105 // --- Allocate Bitmaps ---
106 int todo = numPages*2 + superPages;
107 int mapent = NPMemRanges-1;
108 vaddr = MM_PAGE_BITMAP;
112 while(PMemRanges[mapent].Type != PMEMTYPE_FREE && mapent != -1)
115 paddr = PMemRanges[mapent].Start;
117 // OOM During init, bad thing
118 Log_KernelPanic("PMem", "Out of memory during init");
122 // Ensure that the static allocation pool has pages
123 for( i = 0; i < NUM_STATIC_ALLOC; i++)
125 if(gaiStaticAllocPages[i] == 0)
127 gaiStaticAllocPages[i] = paddr;
128 // break to ensure we update the address correctly
133 if( i == NUM_STATIC_ALLOC )
136 MM_Map((void*)vaddr, paddr);
139 // Update virtual pointer
141 if( todo == numPages + superPages )
142 vaddr = MM_PAGE_DBLBMP;
143 if( todo == superPages )
144 vaddr = MM_PAGE_SUPBMP;
147 // Update physical pointer
148 // (underflows are detected at the top of the loop)
150 if( paddr - PMemRanges[mapent].Start > PMemRanges[mapent].Length )
153 // NOTE: This hides some actually valid memory, but since the pmm
154 // structures have an "infinite" lifetime, this is of no concequence.
155 PMemRanges[mapent].Start += 0x1000;
156 PMemRanges[mapent].Length -= 0x1000;
160 PMemMap_DumpBlocks(PMemRanges, NPMemRanges);
162 // Save the current value of paddr to simplify the allocation later
163 giFirstFreePage = paddr;
165 LOG("Clearing multi bitmap");
166 // Fill the bitmaps (set most to "allocated")
167 memset(gaMultiBitmap, 0, numPages<<12);
168 memset(gaMainBitmap, 255, numPages<<12);
169 // - Clear all Type=1 areas
170 LOG("Clearing valid regions");
171 for( i = 0; i < NPMemRanges; i ++ )
173 tPMemMapEnt *ent = &PMemRanges[i];
174 // Check if the type is RAM
175 if(ent->Type != PMEMTYPE_FREE) continue;
178 base = ent->Start >> 12;
179 size = ent->Length >> 12;
181 LOG("%i: base=%x, size=%x", i, base, size);
182 if( base % 64 + size < 64 )
184 Uint64 bits = (1ULL << size) - 1;
186 gaMainBitmap[base / 64] &= ~bits;
193 Uint64 bits = (1ULL << (base & 63)) - 1;
194 gaMainBitmap[base / 64] &= bits;
196 size -= 64 - base % 64;
197 base += 64 - base % 64;
199 LOG("%i: base=%x, size=%x", i, base, size);
200 memset( &gaMainBitmap[base / 64], 0, (size/64)*8 );
201 base += size & ~(64-1);
202 size -= size & ~(64-1);
203 LOG("%i: base=%x, size=%x", i, base, size);
206 // Unset lower bits (hence the bitwise not)
207 Uint64 val = (1ULL << (size & 63)) - 1;
208 gaMainBitmap[base / 64] &= ~val;
213 // Free the unused static allocs
214 LOG("Freeing unused static allocations");
215 for( i = 0; i < NUM_STATIC_ALLOC; i++)
217 if(gaiStaticAllocPages[i] == 0)
219 gaMainBitmap[ gaiStaticAllocPages[i] >> (12+6) ]
220 &= ~(1LL << ((gaiStaticAllocPages[i]>>12)&63));
221 gaiStaticAllocPages[i] = 0;
225 // Fill the super bitmap
226 LOG("Filling super bitmap");
227 memset(gaSuperBitmap, 0, superPages<<12);
228 int nsuperbits = giMaxPhysPage / 64; // 64 pages per bit
229 for( i = 0; i < (nsuperbits+63)/64; i ++)
231 if( gaMainBitmap[ i ] + 1 == 0 )
232 gaSuperBitmap[ i/64 ] |= 1ULL << (i % 64);
235 // Set free page counts for each address class
236 for( base = 1; base < giMaxPhysPage; base ++ )
240 if( gaMainBitmap[ base >> 6 ] & (1LL << (base&63)) ) continue;
243 rangeID = MM_int_GetRangeID( base << 12 );
245 // Increment free page count
246 giPhysRangeFree[ rangeID ] ++;
248 // Check for first free page in range
249 if(giPhysRangeFirst[ rangeID ] == 0)
250 giPhysRangeFirst[ rangeID ] = base;
251 // Set last (when the last free page is reached, this won't be
252 // updated anymore, hence will be correct)
253 giPhysRangeLast[ rangeID ] = base;
259 void MM_DumpStatistics(void)
261 // TODO: Statistics for x86_64 PMM
262 Log_Warning("PMem", "TODO: Dump statistics");
266 * \brief Allocate a contiguous range of physical pages with a maximum
267 * bit size of \a MaxBits
268 * \param Pages Number of pages to allocate
269 * \param MaxBits Maximum size of the physical address
270 * \note If \a MaxBits is <= 0, any sized address is used (with preference
271 * to higher addresses)
273 tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
279 ENTER("iPages iBits", Pages, MaxBits);
281 if( MaxBits <= 0 || MaxBits >= 64 ) // Speedup for the common case
282 rangeID = MM_PHYS_MAX;
284 rangeID = MM_int_GetRangeID( (1LL << MaxBits) - 1 );
286 LOG("rangeID = %i", rangeID);
288 Mutex_Acquire(&glPhysicalPages);
290 // Check if the range actually has any free pages
291 while(giPhysRangeFree[rangeID] == 0 && rangeID)
294 LOG("rangeID = %i", rangeID);
296 // What the? Oh, man. No free pages
297 if(giPhysRangeFree[rangeID] == 0) {
298 Mutex_Release(&glPhysicalPages);
301 Warning(" MM_AllocPhysRange: Out of free pages");
303 "Out of memory (unable to fulfil request for %i pages), zero remaining",
310 // Check if there is enough in the range
311 if(giPhysRangeFree[rangeID] >= Pages)
313 LOG("{%i,0x%x -> 0x%x}",
314 giPhysRangeFree[rangeID],
315 giPhysRangeFirst[rangeID], giPhysRangeLast[rangeID]
317 // Do a cheap scan, scanning upwards from the first free page in
320 addr = giPhysRangeFirst[ rangeID ];
321 while( addr <= giPhysRangeLast[ rangeID ] )
323 //Log(" MM_AllocPhysRange: addr = 0x%x", addr);
324 // Check the super bitmap
325 if( gaSuperBitmap[addr >> (6+6)] + 1 == 0 ) {
326 LOG("nFree = %i = 0 (super) (0x%x)", nFree, addr);
328 addr += 1LL << (6+6);
329 addr &= ~0xFFF; // (1LL << 6+6) - 1
332 // Check page block (64 pages)
333 if( gaMainBitmap[addr >> 6] + 1 == 0) {
334 LOG("nFree = %i = 0 (main) (0x%x)", nFree, addr);
340 // Check individual page
341 if( gaMainBitmap[addr >> 6] & (1LL << (addr & 63)) ) {
342 LOG("nFree = %i = 0 (page) (0x%x)", nFree, addr);
349 LOG("nFree(%i) == %i (0x%x)", nFree, Pages, addr);
353 LOG("nFree = %i", nFree);
354 // If we don't find a contiguous block, nFree will not be equal
355 // to Num, so we set it to zero and do the expensive lookup.
356 if(nFree != Pages) nFree = 0;
361 // Oops. ok, let's do an expensive check (scan down the list
362 // until a free range is found)
364 // addr = giPhysRangeLast[ rangeID ];
365 // TODO: Expensive Check
366 Mutex_Release(&glPhysicalPages);
369 Warning(" MM_AllocPhysRange: Out of memory (unable to fulfil request for %i pages)", Pages);
371 "Out of memory (unable to fulfil request for %i pages)",
377 LOG("nFree = %i, addr = 0x%08x", nFree, addr);
379 // Mark pages as allocated
381 for( i = 0; i < Pages; i++, addr++ )
383 gaMainBitmap[addr >> 6] |= 1LL << (addr & 63);
384 if( MM_GetPhysAddr( &gaiPageReferences[addr] ) )
385 gaiPageReferences[addr] = 1;
386 // Log("page %P refcount = %i", MM_GetRefCount(addr<<12));
387 rangeID = MM_int_GetRangeID(addr << 12);
388 giPhysRangeFree[ rangeID ] --;
389 LOG("%x == %x", addr, giPhysRangeFirst[ rangeID ]);
390 if(addr == giPhysRangeFirst[ rangeID ])
391 giPhysRangeFirst[ rangeID ] += 1;
394 ret = addr; // Save the return address
396 // Update super bitmap
397 Pages += addr & (64-1);
399 Pages = (Pages + (64-1)) & ~(64-1);
400 for( i = 0; i < Pages/64; i++ )
402 if( gaMainBitmap[ addr >> 6 ] + 1 == 0 )
403 gaSuperBitmap[addr>>12] |= 1LL << ((addr >> 6) & 63);
406 Mutex_Release(&glPhysicalPages);
408 Log("MM_AllocPhysRange: ret = %P (Ref %i)", ret << 12, MM_GetRefCount(ret<<12));
410 LEAVE('x', ret << 12);
415 * \brief Allocate a single physical page, with no preference as to address
418 tPAddr MM_AllocPhys(void)
422 // Hack to allow allocation during setup
423 for(i = 0; i < NUM_STATIC_ALLOC; i++) {
424 if( gaiStaticAllocPages[i] ) {
425 tPAddr ret = gaiStaticAllocPages[i];
426 gaiStaticAllocPages[i] = 0;
427 Log("MM_AllocPhys: Return %P, static alloc %i", ret, i);
432 return MM_AllocPhysRange(1, -1);
436 * \brief Reference a physical page
438 void MM_RefPhys(tPAddr PAddr)
440 Uint64 page = PAddr >> 12;
442 if( page > giMaxPhysPage ) return ;
444 if( PAGE_ALLOC_TEST(page) )
446 tVAddr ref_base = ((tVAddr)&gaiPageReferences[ page ]) & ~0xFFF;
447 // Allocate reference page
448 if( !MM_GetPhysAddr(&gaiPageReferences[page]) )
450 const int pages_per_refpage = PAGE_SIZE/sizeof(gaiPageReferences[0]);
452 int page_base = page / pages_per_refpage * pages_per_refpage;
453 if( !MM_Allocate( (void*)ref_base ) ) {
454 Log_Error("PMem", "Out of memory when allocating reference count page");
458 Log("Allocated references for %P-%P", page_base << 12, (page_base+pages_per_refpage)<<12);
459 for( i = 0; i < pages_per_refpage; i ++ ) {
460 int pg = page_base + i;
461 gaiPageReferences[pg] = !!PAGE_ALLOC_TEST(pg);
464 gaiPageReferences[page] ++;
469 PAGE_ALLOC_SET(page);
470 if( gaMainBitmap[page >> 6] + 1 == 0 )
471 gaSuperBitmap[page>> 12] |= 1LL << ((page >> 6) & 63);
472 if( MM_GetPhysAddr( &gaiPageReferences[page] ) )
473 gaiPageReferences[page] = 1;
477 Log("MM_RefPhys: %P referenced (%i)", page << 12, MM_GetRefCount(page << 12));
482 * \brief Dereference a physical page
484 void MM_DerefPhys(tPAddr PAddr)
486 Uint64 page = PAddr >> 12;
488 if( PAddr >> 12 > giMaxPhysPage ) return ;
490 if( MM_GetPhysAddr( &gaiPageReferences[page] ) )
492 gaiPageReferences[ page ] --;
493 if( gaiPageReferences[ page ] == 0 )
494 PAGE_ALLOC_CLEAR(page);
497 PAGE_ALLOC_CLEAR(page);
499 // Update the free counts if the page was freed
500 if( !PAGE_ALLOC_TEST(page) )
503 rangeID = MM_int_GetRangeID( PAddr );
504 giPhysRangeFree[ rangeID ] ++;
505 if( giPhysRangeFirst[rangeID] > page )
506 giPhysRangeFirst[rangeID] = page;
507 if( giPhysRangeLast[rangeID] < page )
508 giPhysRangeLast[rangeID] = page;
511 // If the bitmap entry is not -1, unset the bit in the super bitmap
512 if(gaMainBitmap[ page >> 6 ] + 1 != 0 ) {
513 gaSuperBitmap[page >> 12] &= ~(1LL << ((page >> 6) & 63));
517 Log("Page %P dereferenced (%i)", page << 12, MM_GetRefCount(page << 12));
521 int MM_GetRefCount( tPAddr PAddr )
525 if( PAddr > giMaxPhysPage ) return 0;
527 if( MM_GetPhysAddr( &gaiPageReferences[PAddr] ) ) {
528 return gaiPageReferences[PAddr];
531 if( PAGE_ALLOC_TEST(PAddr) )
539 * \brief Takes a physical address and returns the ID of its range
540 * \param Addr Physical address of page
541 * \return Range ID from eMMPhys_Ranges
543 int MM_int_GetRangeID( tPAddr Addr )
548 return MM_PHYS_32BIT;
550 return MM_PHYS_24BIT;
552 return MM_PHYS_20BIT;
554 return MM_PHYS_16BIT;
557 int MM_SetPageNode(tPAddr PAddr, void *Node)
559 tPAddr page = PAddr >> 12;
560 void *node_page = (void*)( ((tVAddr)&gapPageNodes[page]) & ~(PAGE_SIZE-1) );
562 // if( !MM_GetRefCount(PAddr) ) return 1;
564 if( !MM_GetPhysAddr(node_page) ) {
565 if( !MM_Allocate(node_page) )
567 memset( node_page, 0, PAGE_SIZE );
570 gapPageNodes[page] = Node;
574 int MM_GetPageNode(tPAddr PAddr, void **Node)
576 // if( !MM_GetRefCount(PAddr) ) return 1;
579 if( !MM_GetPhysAddr( &gapPageNodes[PAddr] ) ) {
584 *Node = gapPageNodes[PAddr];