4 * Physical Memory Manager
16 MM_PHYS_16BIT, // Does anything need this?
17 MM_PHYS_20BIT, // Real-Mode
18 MM_PHYS_24BIT, // ISA DMA
19 MM_PHYS_32BIT, // x86 Hardware
20 MM_PHYS_MAX, // Doesn't care
25 extern char gKernelBase[];
26 extern char gKernelEnd[];
29 //void MM_InitPhys(int NPMemRanges, tPMemMapEnt *PMemRanges);
30 //tPAddr MM_AllocPhysRange(int Num, int Bits);
31 //tPAddr MM_AllocPhys(void);
32 //void MM_RefPhys(tPAddr PAddr);
33 //void MM_DerefPhys(tPAddr PAddr);
34 int MM_int_GetRangeID( tPAddr Addr );
37 #define PAGE_ALLOC_TEST(__page) (gaMainBitmap[(__page)>>6] & (1ULL << ((__page)&63)))
38 #define PAGE_ALLOC_SET(__page) do{gaMainBitmap[(__page)>>6] |= (1ULL << ((__page)&63));}while(0)
39 #define PAGE_ALLOC_CLEAR(__page) do{gaMainBitmap[(__page)>>6] &= ~(1ULL << ((__page)&63));}while(0)
40 //#define PAGE_MULTIREF_TEST(__page) (gaMultiBitmap[(__page)>>6] & (1ULL << ((__page)&63)))
41 //#define PAGE_MULTIREF_SET(__page) do{gaMultiBitmap[(__page)>>6] |= 1ULL << ((__page)&63);}while(0)
42 //#define PAGE_MULTIREF_CLEAR(__page) do{gaMultiBitmap[(__page)>>6] &= ~(1ULL << ((__page)&63));}while(0)
45 tMutex glPhysicalPages;
46 Uint64 *gaSuperBitmap = (void*)MM_PAGE_SUPBMP; // 1 bit = 64 Pages, 16 MiB per Word
47 Uint64 *gaMainBitmap = (void*)MM_PAGE_BITMAP; // 1 bit = 1 Page, 256 KiB per Word
48 Uint64 *gaMultiBitmap = (void*)MM_PAGE_DBLBMP; // Each bit means that the page is being used multiple times
49 Uint32 *gaiPageReferences = (void*)MM_PAGE_COUNTS; // Reference Counts
50 void **gapPageNodes = (void*)MM_PAGE_NODES; // Reference Counts
51 tPAddr giFirstFreePage; // First possibly free page
52 Uint64 giPhysRangeFree[NUM_MM_PHYS_RANGES]; // Number of free pages in each range
53 Uint64 giPhysRangeFirst[NUM_MM_PHYS_RANGES]; // First free page in each range
54 Uint64 giPhysRangeLast[NUM_MM_PHYS_RANGES]; // Last free page in each range
55 Uint64 giMaxPhysPage = 0; // Maximum Physical page
56 Uint64 giTotalMemorySize = 0;
57 // Only used in init, allows the init code to provide pages for use by
58 // the allocator before the bitmaps exist.
59 // 3 entries because the are three calls to MM_AllocPhys in MM_Map
60 #define NUM_STATIC_ALLOC 3
61 tPAddr gaiStaticAllocPages[NUM_STATIC_ALLOC] = {0};
65 * \brief Initialise the physical memory map using a Multiboot 1 map
67 void MM_InitPhys(int NPMemRanges, tPMemMapEnt *PMemRanges)
70 int numPages, superPages;
74 tPAddr paddr, firstFreePage;
76 ENTER("iNPMemRanges pPMemRanges",
77 NPMemRanges, PMemRanges);
79 // Scan the physical memory map
80 // Looking for the top of physical memory
81 for( i = 0; i < NPMemRanges; i ++ )
83 tPMemMapEnt *ent = &PMemRanges[i];
84 // Adjust for the size of the entry
85 LOG("%i: ent={Type:%i,Base:0x%x,Length:%x}", i, ent->Type, ent->Start, ent->Length);
87 // If entry is RAM and is above `maxAddr`, change `maxAddr`
88 if(ent->Type == PMEMTYPE_FREE || ent->Type == PMEMTYPE_USED )
90 if( ent->Start + ent->Length > maxAddr)
91 maxAddr = ent->Start + ent->Length;
92 giTotalMemorySize += ent->Length >> 12;
96 giMaxPhysPage = maxAddr >> 12;
97 LOG("giMaxPhysPage = 0x%x", giMaxPhysPage);
99 // Get counts of pages needed for basic structures
100 superPages = ((giMaxPhysPage+64*8-1)/(64*8) + 0xFFF) >> 12;
101 numPages = ((giMaxPhysPage+7)/8 + 0xFFF) >> 12; // bytes to hold bitmap, divided up to nearest page
102 LOG("numPages = %i, superPages = %i", numPages, superPages);
104 // --- Allocate Bitmaps ---
105 int todo = numPages*2 + superPages;
106 int mapent = NPMemRanges-1;
107 vaddr = MM_PAGE_BITMAP;
111 while(PMemRanges[mapent].Type != PMEMTYPE_FREE && mapent != -1)
114 paddr = PMemRanges[mapent].Start;
116 // OOM During init, bad thing
117 Log_KernelPanic("PMem", "Out of memory during init");
121 // Ensure that the static allocation pool has pages
122 for( i = 0; i < NUM_STATIC_ALLOC; i++)
124 if(gaiStaticAllocPages[i] == 0)
126 gaiStaticAllocPages[i] = paddr;
127 // break to ensure we update the address correctly
132 if( i == NUM_STATIC_ALLOC )
135 MM_Map(vaddr, paddr);
138 // Update virtual pointer
140 if( todo == numPages + superPages )
141 vaddr = MM_PAGE_DBLBMP;
142 if( todo == superPages )
143 vaddr = MM_PAGE_SUPBMP;
146 // Update physical pointer
147 // (underflows are detected at the top of the loop)
149 if( paddr - PMemRanges[mapent].Start > PMemRanges[mapent].Length )
152 // NOTE: This hides some actually valid memory, but since the pmm
153 // structures have an "infinite" lifetime, this is of no concequence.
154 PMemRanges[mapent].Start += 0x1000;
155 PMemRanges[mapent].Length -= 0x1000;
159 PMemMap_DumpBlocks(PMemRanges, NPMemRanges);
161 // Save the current value of paddr to simplify the allocation later
162 firstFreePage = paddr;
164 LOG("Clearing multi bitmap");
165 // Fill the bitmaps (set most to "allocated")
166 memset(gaMultiBitmap, 0, numPages<<12);
167 memset(gaMainBitmap, 255, numPages<<12);
168 // - Clear all Type=1 areas
169 LOG("Clearing valid regions");
170 for( i = 0; i < NPMemRanges; i ++ )
172 tPMemMapEnt *ent = &PMemRanges[i];
173 // Check if the type is RAM
174 if(ent->Type != PMEMTYPE_FREE) continue;
177 base = ent->Start >> 12;
178 size = ent->Length >> 12;
180 LOG("%i: base=%x, size=%x", i, base, size);
181 if( base % 64 + size < 64 )
183 Uint64 bits = (1ULL << size) - 1;
185 gaMainBitmap[base / 64] &= ~bits;
192 Uint64 bits = (1ULL << (base & 63)) - 1;
193 gaMainBitmap[base / 64] &= bits;
195 size -= 64 - base % 64;
196 base += 64 - base % 64;
198 LOG("%i: base=%x, size=%x", i, base, size);
199 memset( &gaMainBitmap[base / 64], 0, (size/64)*8 );
200 base += size & ~(64-1);
201 size -= size & ~(64-1);
202 LOG("%i: base=%x, size=%x", i, base, size);
205 // Unset lower bits (hence the bitwise not)
206 Uint64 val = (1ULL << (size & 63)) - 1;
207 gaMainBitmap[base / 64] &= ~val;
212 // Free the unused static allocs
213 LOG("Freeing unused static allocations");
214 for( i = 0; i < NUM_STATIC_ALLOC; i++)
216 if(gaiStaticAllocPages[i] == 0)
218 gaMainBitmap[ gaiStaticAllocPages[i] >> (12+6) ]
219 &= ~(1LL << ((gaiStaticAllocPages[i]>>12)&63));
220 gaiStaticAllocPages[i] = 0;
224 // Fill the super bitmap
225 LOG("Filling super bitmap");
226 memset(gaSuperBitmap, 0, superPages<<12);
227 int nsuperbits = giMaxPhysPage / 64; // 64 pages per bit
228 for( i = 0; i < (nsuperbits+63)/64; i ++)
230 if( gaMainBitmap[ i ] + 1 == 0 )
231 gaSuperBitmap[ i/64 ] |= 1ULL << (i % 64);
234 // Set free page counts for each address class
235 for( base = 1; base < giMaxPhysPage; base ++ )
239 if( gaMainBitmap[ base >> 6 ] & (1LL << (base&63)) ) continue;
242 rangeID = MM_int_GetRangeID( base << 12 );
244 // Increment free page count
245 giPhysRangeFree[ rangeID ] ++;
247 // Check for first free page in range
248 if(giPhysRangeFirst[ rangeID ] == 0)
249 giPhysRangeFirst[ rangeID ] = base;
250 // Set last (when the last free page is reached, this won't be
251 // updated anymore, hence will be correct)
252 giPhysRangeLast[ rangeID ] = base;
258 void MM_DumpStatistics(void)
260 // TODO: Statistics for x86_64 PMM
264 * \brief Allocate a contiguous range of physical pages with a maximum
265 * bit size of \a MaxBits
266 * \param Pages Number of pages to allocate
267 * \param MaxBits Maximum size of the physical address
268 * \note If \a MaxBits is <= 0, any sized address is used (with preference
269 * to higher addresses)
271 tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
277 ENTER("iPages iBits", Pages, MaxBits);
279 if( MaxBits <= 0 || MaxBits >= 64 ) // Speedup for the common case
280 rangeID = MM_PHYS_MAX;
282 rangeID = MM_int_GetRangeID( (1LL << MaxBits) - 1 );
284 LOG("rangeID = %i", rangeID);
286 Mutex_Acquire(&glPhysicalPages);
288 // Check if the range actually has any free pages
289 while(giPhysRangeFree[rangeID] == 0 && rangeID)
292 LOG("rangeID = %i", rangeID);
294 // What the? Oh, man. No free pages
295 if(giPhysRangeFree[rangeID] == 0) {
296 Mutex_Release(&glPhysicalPages);
299 Warning(" MM_AllocPhysRange: Out of free pages");
301 "Out of memory (unable to fulfil request for %i pages), zero remaining",
308 // Check if there is enough in the range
309 if(giPhysRangeFree[rangeID] >= Pages)
311 LOG("{%i,0x%x -> 0x%x}",
312 giPhysRangeFree[rangeID],
313 giPhysRangeFirst[rangeID], giPhysRangeLast[rangeID]
315 // Do a cheap scan, scanning upwards from the first free page in
318 addr = giPhysRangeFirst[ rangeID ];
319 while( addr <= giPhysRangeLast[ rangeID ] )
321 //Log(" MM_AllocPhysRange: addr = 0x%x", addr);
322 // Check the super bitmap
323 if( gaSuperBitmap[addr >> (6+6)] + 1 == 0 ) {
324 LOG("nFree = %i = 0 (super) (0x%x)", nFree, addr);
326 addr += 1LL << (6+6);
327 addr &= ~0xFFF; // (1LL << 6+6) - 1
330 // Check page block (64 pages)
331 if( gaMainBitmap[addr >> 6] + 1 == 0) {
332 LOG("nFree = %i = 0 (main) (0x%x)", nFree, addr);
338 // Check individual page
339 if( gaMainBitmap[addr >> 6] & (1LL << (addr & 63)) ) {
340 LOG("nFree = %i = 0 (page) (0x%x)", nFree, addr);
347 LOG("nFree(%i) == %i (0x%x)", nFree, Pages, addr);
351 LOG("nFree = %i", nFree);
352 // If we don't find a contiguous block, nFree will not be equal
353 // to Num, so we set it to zero and do the expensive lookup.
354 if(nFree != Pages) nFree = 0;
359 // Oops. ok, let's do an expensive check (scan down the list
360 // until a free range is found)
362 // addr = giPhysRangeLast[ rangeID ];
363 // TODO: Expensive Check
364 Mutex_Release(&glPhysicalPages);
367 Warning(" MM_AllocPhysRange: Out of memory (unable to fulfil request for %i pages)", Pages);
369 "Out of memory (unable to fulfil request for %i pages)",
375 LOG("nFree = %i, addr = 0x%08x", nFree, addr);
377 // Mark pages as allocated
379 for( i = 0; i < Pages; i++, addr++ )
381 gaMainBitmap[addr >> 6] |= 1LL << (addr & 63);
382 if( MM_GetPhysAddr( &gaiPageReferences[addr] ) )
383 gaiPageReferences[addr] = 1;
384 // Log("page %P refcount = %i", MM_GetRefCount(addr<<12));
385 rangeID = MM_int_GetRangeID(addr << 12);
386 giPhysRangeFree[ rangeID ] --;
387 LOG("%x == %x", addr, giPhysRangeFirst[ rangeID ]);
388 if(addr == giPhysRangeFirst[ rangeID ])
389 giPhysRangeFirst[ rangeID ] += 1;
392 ret = addr; // Save the return address
394 // Update super bitmap
395 Pages += addr & (64-1);
397 Pages = (Pages + (64-1)) & ~(64-1);
398 for( i = 0; i < Pages/64; i++ )
400 if( gaMainBitmap[ addr >> 6 ] + 1 == 0 )
401 gaSuperBitmap[addr>>12] |= 1LL << ((addr >> 6) & 63);
404 Mutex_Release(&glPhysicalPages);
406 Log("MM_AllocPhysRange: ret = %P (Ref %i)", ret << 12, MM_GetRefCount(ret<<12));
408 LEAVE('x', ret << 12);
413 * \brief Allocate a single physical page, with no preference as to address
416 tPAddr MM_AllocPhys(void)
420 // Hack to allow allocation during setup
421 for(i = 0; i < NUM_STATIC_ALLOC; i++) {
422 if( gaiStaticAllocPages[i] ) {
423 tPAddr ret = gaiStaticAllocPages[i];
424 gaiStaticAllocPages[i] = 0;
425 Log("MM_AllocPhys: Return %P, static alloc %i", ret, i);
430 return MM_AllocPhysRange(1, -1);
434 * \brief Reference a physical page
436 void MM_RefPhys(tPAddr PAddr)
438 Uint64 page = PAddr >> 12;
440 if( page > giMaxPhysPage ) return ;
442 if( PAGE_ALLOC_TEST(page) )
444 tVAddr ref_base = ((tVAddr)&gaiPageReferences[ page ]) & ~0xFFF;
445 // Allocate reference page
446 if( !MM_GetPhysAddr(&gaiPageReferences[page]) )
448 const int pages_per_refpage = PAGE_SIZE/sizeof(gaiPageReferences[0]);
450 int page_base = page / pages_per_refpage * pages_per_refpage;
451 if( !MM_Allocate( ref_base ) ) {
452 Log_Error("Arch", "Out of memory when allocating reference count page");
456 Log("Allocated references for %P-%P", page_base << 12, (page_base+pages_per_refpage)<<12);
457 for( i = 0; i < pages_per_refpage; i ++ ) {
458 int pg = page_base + i;
459 gaiPageReferences[pg] = !!PAGE_ALLOC_TEST(pg);
462 gaiPageReferences[page] ++;
467 PAGE_ALLOC_SET(page);
468 if( gaMainBitmap[page >> 6] + 1 == 0 )
469 gaSuperBitmap[page>> 12] |= 1LL << ((page >> 6) & 63);
470 if( MM_GetPhysAddr( &gaiPageReferences[page] ) )
471 gaiPageReferences[page] = 1;
475 Log("MM_RefPhys: %P referenced (%i)", page << 12, MM_GetRefCount(page << 12));
480 * \brief Dereference a physical page
482 void MM_DerefPhys(tPAddr PAddr)
484 Uint64 page = PAddr >> 12;
486 if( PAddr >> 12 > giMaxPhysPage ) return ;
488 if( MM_GetPhysAddr( &gaiPageReferences[page] ) )
490 gaiPageReferences[ page ] --;
491 if( gaiPageReferences[ page ] == 0 )
492 PAGE_ALLOC_CLEAR(page);
495 PAGE_ALLOC_CLEAR(page);
497 // Update the free counts if the page was freed
498 if( !PAGE_ALLOC_TEST(page) )
501 rangeID = MM_int_GetRangeID( PAddr );
502 giPhysRangeFree[ rangeID ] ++;
503 if( giPhysRangeFirst[rangeID] > page )
504 giPhysRangeFirst[rangeID] = page;
505 if( giPhysRangeLast[rangeID] < page )
506 giPhysRangeLast[rangeID] = page;
509 // If the bitmap entry is not -1, unset the bit in the super bitmap
510 if(gaMainBitmap[ page >> 6 ] + 1 != 0 ) {
511 gaSuperBitmap[page >> 12] &= ~(1LL << ((page >> 6) & 63));
515 Log("Page %P dereferenced (%i)", page << 12, MM_GetRefCount(page << 12));
519 int MM_GetRefCount( tPAddr PAddr )
523 if( PAddr > giMaxPhysPage ) return 0;
525 if( MM_GetPhysAddr( &gaiPageReferences[PAddr] ) ) {
526 return gaiPageReferences[PAddr];
529 if( PAGE_ALLOC_TEST(PAddr) )
537 * \brief Takes a physical address and returns the ID of its range
538 * \param Addr Physical address of page
539 * \return Range ID from eMMPhys_Ranges
541 int MM_int_GetRangeID( tPAddr Addr )
546 return MM_PHYS_32BIT;
548 return MM_PHYS_24BIT;
550 return MM_PHYS_20BIT;
552 return MM_PHYS_16BIT;
555 int MM_SetPageNode(tPAddr PAddr, void *Node)
557 tPAddr page = PAddr >> 12;
558 tVAddr node_page = ((tVAddr)&gapPageNodes[page]) & ~(PAGE_SIZE-1);
560 // if( !MM_GetRefCount(PAddr) ) return 1;
562 if( !MM_GetPhysAddr((void*)node_page) ) {
563 if( !MM_Allocate(node_page) )
565 memset( (void*)node_page, 0, PAGE_SIZE );
568 gapPageNodes[page] = Node;
572 int MM_GetPageNode(tPAddr PAddr, void **Node)
574 // if( !MM_GetRefCount(PAddr) ) return 1;
577 if( !MM_GetPhysAddr( &gapPageNodes[PAddr] ) ) {
582 *Node = gapPageNodes[PAddr];