4 * Physical Memory Manager
15 MM_PHYS_16BIT, // Does anything need this?
16 MM_PHYS_20BIT, // Real-Mode
17 MM_PHYS_24BIT, // ISA DMA
18 MM_PHYS_32BIT, // x86 Hardware
19 MM_PHYS_MAX, // Doesn't care
24 extern char gKernelBase[];
25 extern char gKernelEnd[];
28 void MM_InitPhys_Multiboot(tMBoot_Info *MBoot);
29 //tPAddr MM_AllocPhysRange(int Num, int Bits);
30 //tPAddr MM_AllocPhys(void);
31 //void MM_RefPhys(tPAddr PAddr);
32 //void MM_DerefPhys(tPAddr PAddr);
33 int MM_int_GetRangeID( tPAddr Addr );
36 #define PAGE_ALLOC_TEST(__page) (gaMainBitmap[(__page)>>6] & (1ULL << ((__page)&63)))
37 #define PAGE_ALLOC_SET(__page) do{gaMainBitmap[(__page)>>6] |= (1ULL << ((__page)&63));}while(0)
38 #define PAGE_ALLOC_CLEAR(__page) do{gaMainBitmap[(__page)>>6] &= ~(1ULL << ((__page)&63));}while(0)
39 //#define PAGE_MULTIREF_TEST(__page) (gaMultiBitmap[(__page)>>6] & (1ULL << ((__page)&63)))
40 //#define PAGE_MULTIREF_SET(__page) do{gaMultiBitmap[(__page)>>6] |= 1ULL << ((__page)&63);}while(0)
41 //#define PAGE_MULTIREF_CLEAR(__page) do{gaMultiBitmap[(__page)>>6] &= ~(1ULL << ((__page)&63));}while(0)
44 tMutex glPhysicalPages;
45 Uint64 *gaSuperBitmap = (void*)MM_PAGE_SUPBMP; // 1 bit = 64 Pages, 16 MiB per Word
46 Uint64 *gaMainBitmap = (void*)MM_PAGE_BITMAP; // 1 bit = 1 Page, 256 KiB per Word
47 Uint64 *gaMultiBitmap = (void*)MM_PAGE_DBLBMP; // Each bit means that the page is being used multiple times
48 Uint32 *gaiPageReferences = (void*)MM_PAGE_COUNTS; // Reference Counts
49 void **gapPageNodes = (void*)MM_PAGE_NODES; // Reference Counts
50 tPAddr giFirstFreePage; // First possibly free page
51 Uint64 giPhysRangeFree[NUM_MM_PHYS_RANGES]; // Number of free pages in each range
52 Uint64 giPhysRangeFirst[NUM_MM_PHYS_RANGES]; // First free page in each range
53 Uint64 giPhysRangeLast[NUM_MM_PHYS_RANGES]; // Last free page in each range
54 Uint64 giMaxPhysPage = 0; // Maximum Physical page
55 // Only used in init, allows the init code to provide pages for use by
56 // the allocator before the bitmaps exist.
57 // 3 entries because the are three calls to MM_AllocPhys in MM_Map
58 #define NUM_STATIC_ALLOC 3
59 tPAddr gaiStaticAllocPages[NUM_STATIC_ALLOC] = {0};
63 * \brief Initialise the physical memory map using a Multiboot 1 map
65 void MM_InitPhys_Multiboot(tMBoot_Info *MBoot)
67 tMBoot_MMapEnt *mmapStart;
70 int numPages, superPages;
74 tPAddr paddr, firstFreePage;
76 ENTER("pMBoot=%p", MBoot);
78 // Scan the physical memory map
79 // Looking for the top of physical memory
80 mmapStart = (void *)( KERNEL_BASE | MBoot->MMapAddr );
81 LOG("mmapStart = %p", mmapStart);
83 while( (Uint)ent < (Uint)mmapStart + MBoot->MMapLength )
85 // Adjust for the size of the entry
87 LOG("ent={Type:%i,Base:0x%x,Length:%x",
88 ent->Type, ent->Base, ent->Length);
90 // If entry is RAM and is above `maxAddr`, change `maxAddr`
91 if(ent->Type == 1 && ent->Base + ent->Length > maxAddr)
92 maxAddr = ent->Base + ent->Length;
95 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size );
98 // Did we find a valid end?
100 // No, darn, let's just use the HighMem hack
101 giMaxPhysPage = (MBoot->HighMem >> 2) + 256; // HighMem is a kByte value
104 // Goodie, goodie gumdrops
105 giMaxPhysPage = maxAddr >> 12;
107 LOG("giMaxPhysPage = 0x%x", giMaxPhysPage);
109 // Find a contigous section of memory to hold it in
110 // - Starting from the end of the kernel
111 // - We also need a region for the super bitmap
112 superPages = ((giMaxPhysPage+64*8-1)/(64*8) + 0xFFF) >> 12;
113 numPages = (giMaxPhysPage + 7) / 8;
114 numPages = (numPages + 0xFFF) >> 12;
115 LOG("numPages = %i, superPages = %i", numPages, superPages);
118 int todo = numPages*2 + superPages;
119 // Ok, naieve allocation, just put it after the kernel
120 // - Allocated Bitmap
121 vaddr = MM_PAGE_BITMAP;
122 paddr = (tPAddr)&gKernelEnd - KERNEL_BASE;
126 for( i = 0; i < NUM_STATIC_ALLOC; i++) {
127 if(gaiStaticAllocPages[i] != 0) continue;
128 gaiStaticAllocPages[i] = paddr;
132 MM_Map(vaddr, paddr);
138 if( todo == numPages + superPages )
139 vaddr = MM_PAGE_DBLBMP;
140 if( todo == superPages )
141 vaddr = MM_PAGE_SUPBMP;
144 // Scan for a nice range
147 int todo = numPages*2 + superPages;
149 vaddr = MM_PAGE_BITMAP;
153 (Uint)ent < (Uint)mmapStart + MBoot->MMapLength;
154 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size )
163 // Let's not put it below the kernel, shall we?
164 if( ent->Base + ent->Size < (tPAddr)&gKernelBase )
167 LOG("%x <= %x && %x > %x",
168 ent->Base, (tPAddr)&gKernelBase,
169 ent->Base + ent->Size, (tPAddr)&gKernelEnd - KERNEL_BASE
171 // Check if the kernel is in this range
172 if( ent->Base <= (tPAddr)&gKernelBase
173 && ent->Base + ent->Length > (tPAddr)&gKernelEnd - KERNEL_BASE )
175 avail = ent->Length >> 12;
176 avail -= ((tPAddr)&gKernelEnd - KERNEL_BASE - ent->Base) >> 12;
177 paddr = (tPAddr)&gKernelEnd - KERNEL_BASE;
179 // No? then we can use all of the block
182 avail = ent->Length >> 12;
186 Log("MM_InitPhys_Multiboot: paddr=0x%x, avail=0x%x pg", paddr, avail);
189 while( todo && avail --)
191 // Static Allocations
192 for( i = 0; i < NUM_STATIC_ALLOC && avail; i++) {
193 if(gaiStaticAllocPages[i] != 0) continue;
194 gaiStaticAllocPages[i] = paddr;
201 MM_Map(vaddr, paddr);
206 // Alter the destination address when needed
207 if(todo == superPages+numPages)
208 vaddr = MM_PAGE_DBLBMP;
209 if(todo == superPages)
210 vaddr = MM_PAGE_SUPBMP;
213 // Fast quit if there's nothing left to allocate
217 // Save the current value of paddr to simplify the allocation later
218 firstFreePage = paddr;
220 LOG("Clearing multi bitmap");
222 memset(gaMultiBitmap, 0, (numPages<<12)/8);
223 // - initialise to one, then clear the avaliable areas
224 memset(gaMainBitmap, -1, (numPages<<12)/8);
225 memset(gaSuperBitmap, -1, (numPages<<12)/(8*64));
226 LOG("Setting main bitmap");
227 // - Clear all Type=1 areas
228 LOG("Clearing valid regions");
231 (Uint)ent < (Uint)mmapStart + MBoot->MMapLength;
232 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size )
235 // Check if the type is RAM
236 if(ent->Type != 1) continue;
239 base = ent->Base >> 12;
240 size = ent->Size >> 12;
243 Uint64 val = -1LL << (base & 63);
244 gaMainBitmap[base / 64] &= ~val;
246 base += 64 - (base & 63);
248 memset( &gaMainBitmap[base / 64], 0, size/8 );
250 Uint64 val = -1LL << (size & 7);
252 gaMainBitmap[base / 64] &= ~val;
256 base = ent->Base >> 12;
257 size = ent->Size >> 12;
258 size = (size + (base & 63) + 63) >> 6;
261 Uint64 val = -1LL << (base & 63);
262 gaSuperBitmap[base / 64] &= ~val;
263 // size -= (base & 63);
264 // base += 64 - (base & 63);
268 // Reference the used pages
269 base = (tPAddr)&gKernelBase >> 12;
270 size = firstFreePage >> 12;
271 memset( &gaMainBitmap[base / 64], -1, size/8 );
273 Uint64 val = -1LL << (size & 7);
275 gaMainBitmap[base / 64] |= val;
278 // Free the unused static allocs
279 for( i = 0; i < NUM_STATIC_ALLOC; i++) {
280 if(gaiStaticAllocPages[i] != 0)
282 gaMainBitmap[ gaiStaticAllocPages[i] >> (12+6) ]
283 &= ~(1LL << ((gaiStaticAllocPages[i]>>12)&63));
286 // Fill the super bitmap
287 LOG("Filling super bitmap");
288 memset(gaSuperBitmap, 0, superPages<<12);
289 for( base = 0; base < (size+63)/64; base ++)
291 if( gaMainBitmap[ base ] + 1 == 0 )
292 gaSuperBitmap[ base/64 ] |= 1LL << (base&63);
295 // Set free page counts
296 for( base = 1; base < giMaxPhysPage; base ++ )
300 if( gaMainBitmap[ base >> 6 ] & (1LL << (base&63)) ) continue;
303 rangeID = MM_int_GetRangeID( base << 12 );
305 // Increment free page count
306 giPhysRangeFree[ rangeID ] ++;
308 // Check for first free page in range
309 if(giPhysRangeFirst[ rangeID ] == 0)
310 giPhysRangeFirst[ rangeID ] = base;
311 // Set last (when the last free page is reached, this won't be
312 // updated anymore, hence will be correct)
313 giPhysRangeLast[ rangeID ] = base;
320 * \brief Allocate a contiguous range of physical pages with a maximum
321 * bit size of \a MaxBits
322 * \param Pages Number of pages to allocate
323 * \param MaxBits Maximum size of the physical address
324 * \note If \a MaxBits is <= 0, any sized address is used (with preference
325 * to higher addresses)
327 tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
333 ENTER("iPages iBits", Pages, MaxBits);
335 if( MaxBits <= 0 || MaxBits >= 64 ) // Speedup for the common case
336 rangeID = MM_PHYS_MAX;
338 rangeID = MM_int_GetRangeID( (1LL << MaxBits) - 1 );
340 LOG("rangeID = %i", rangeID);
342 Mutex_Acquire(&glPhysicalPages);
344 // Check if the range actually has any free pages
345 while(giPhysRangeFree[rangeID] == 0 && rangeID)
348 LOG("rangeID = %i", rangeID);
350 // What the? Oh, man. No free pages
351 if(giPhysRangeFree[rangeID] == 0) {
352 Mutex_Release(&glPhysicalPages);
355 Warning(" MM_AllocPhysRange: Out of free pages");
357 "Out of memory (unable to fulfil request for %i pages), zero remaining",
364 // Check if there is enough in the range
365 if(giPhysRangeFree[rangeID] >= Pages)
367 LOG("{%i,0x%x -> 0x%x}",
368 giPhysRangeFree[rangeID],
369 giPhysRangeFirst[rangeID], giPhysRangeLast[rangeID]
371 // Do a cheap scan, scanning upwards from the first free page in
374 addr = giPhysRangeFirst[ rangeID ];
375 while( addr <= giPhysRangeLast[ rangeID ] )
377 //Log(" MM_AllocPhysRange: addr = 0x%x", addr);
378 // Check the super bitmap
379 if( gaSuperBitmap[addr >> (6+6)] + 1 == 0 ) {
380 LOG("nFree = %i = 0 (super) (0x%x)", nFree, addr);
382 addr += 1LL << (6+6);
383 addr &= ~0xFFF; // (1LL << 6+6) - 1
386 // Check page block (64 pages)
387 if( gaMainBitmap[addr >> 6] + 1 == 0) {
388 LOG("nFree = %i = 0 (main) (0x%x)", nFree, addr);
394 // Check individual page
395 if( gaMainBitmap[addr >> 6] & (1LL << (addr & 63)) ) {
396 LOG("nFree = %i = 0 (page) (0x%x)", nFree, addr);
403 LOG("nFree(%i) == %i (0x%x)", nFree, Pages, addr);
407 LOG("nFree = %i", nFree);
408 // If we don't find a contiguous block, nFree will not be equal
409 // to Num, so we set it to zero and do the expensive lookup.
410 if(nFree != Pages) nFree = 0;
415 // Oops. ok, let's do an expensive check (scan down the list
416 // until a free range is found)
418 // addr = giPhysRangeLast[ rangeID ];
419 // TODO: Expensive Check
420 Mutex_Release(&glPhysicalPages);
423 Warning(" MM_AllocPhysRange: Out of memory (unable to fulfil request for %i pages)", Pages);
425 "Out of memory (unable to fulfil request for %i pages)",
431 LOG("nFree = %i, addr = 0x%08x", nFree, addr);
433 // Mark pages as allocated
435 for( i = 0; i < Pages; i++, addr++ )
437 gaMainBitmap[addr >> 6] |= 1LL << (addr & 63);
438 if( MM_GetPhysAddr( (tVAddr)&gaiPageReferences[addr] ) )
439 gaiPageReferences[addr] = 1;
440 // Log("page %P refcount = %i", MM_GetRefCount(addr<<12));
441 rangeID = MM_int_GetRangeID(addr << 12);
442 giPhysRangeFree[ rangeID ] --;
443 LOG("%x == %x", addr, giPhysRangeFirst[ rangeID ]);
444 if(addr == giPhysRangeFirst[ rangeID ])
445 giPhysRangeFirst[ rangeID ] += 1;
448 ret = addr; // Save the return address
450 // Update super bitmap
451 Pages += addr & (64-1);
453 Pages = (Pages + (64-1)) & ~(64-1);
454 for( i = 0; i < Pages/64; i++ )
456 if( gaMainBitmap[ addr >> 6 ] + 1 == 0 )
457 gaSuperBitmap[addr>>12] |= 1LL << ((addr >> 6) & 63);
460 Mutex_Release(&glPhysicalPages);
462 Log("MM_AllocPhysRange: ret = %P (Ref %i)", ret << 12, MM_GetRefCount(ret<<12));
464 LEAVE('x', ret << 12);
469 * \brief Allocate a single physical page, with no preference as to address
472 tPAddr MM_AllocPhys(void)
476 // Hack to allow allocation during setup
477 for(i = 0; i < NUM_STATIC_ALLOC; i++) {
478 if( gaiStaticAllocPages[i] ) {
479 tPAddr ret = gaiStaticAllocPages[i];
480 gaiStaticAllocPages[i] = 0;
481 Log("MM_AllocPhys: Return %P, static alloc %i", ret, i);
486 return MM_AllocPhysRange(1, -1);
490 * \brief Reference a physical page
492 void MM_RefPhys(tPAddr PAddr)
494 Uint64 page = PAddr >> 12;
496 if( page > giMaxPhysPage ) return ;
498 if( PAGE_ALLOC_TEST(page) )
500 tVAddr ref_base = ((tVAddr)&gaiPageReferences[ page ]) & ~0xFFF;
501 // Allocate reference page
502 if( !MM_GetPhysAddr(ref_base) )
504 const int pages_per_refpage = PAGE_SIZE/sizeof(gaiPageReferences[0]);
506 int page_base = page / pages_per_refpage * pages_per_refpage;
507 if( !MM_Allocate( ref_base ) ) {
508 Log_Error("Arch", "Out of memory when allocating reference count page");
512 Log("Allocated references for %P-%P", page_base << 12, (page_base+pages_per_refpage)<<12);
513 for( i = 0; i < pages_per_refpage; i ++ ) {
514 int pg = page_base + i;
515 gaiPageReferences[pg] = !!PAGE_ALLOC_TEST(pg);
518 gaiPageReferences[page] ++;
523 PAGE_ALLOC_SET(page);
524 if( gaMainBitmap[page >> 6] + 1 == 0 )
525 gaSuperBitmap[page>> 12] |= 1LL << ((page >> 6) & 63);
526 if( MM_GetPhysAddr( (tVAddr)&gaiPageReferences[page] ) )
527 gaiPageReferences[page] = 1;
531 Log("MM_RefPhys: %P referenced (%i)", page << 12, MM_GetRefCount(page << 12));
536 * \brief Dereference a physical page
538 void MM_DerefPhys(tPAddr PAddr)
540 Uint64 page = PAddr >> 12;
542 if( PAddr >> 12 > giMaxPhysPage ) return ;
544 if( MM_GetPhysAddr( (tVAddr) &gaiPageReferences[page] ) )
546 gaiPageReferences[ page ] --;
547 if( gaiPageReferences[ page ] == 0 )
548 PAGE_ALLOC_CLEAR(page);
551 PAGE_ALLOC_CLEAR(page);
553 // Update the free counts if the page was freed
554 if( !PAGE_ALLOC_TEST(page) )
557 rangeID = MM_int_GetRangeID( PAddr );
558 giPhysRangeFree[ rangeID ] ++;
559 if( giPhysRangeFirst[rangeID] > page )
560 giPhysRangeFirst[rangeID] = page;
561 if( giPhysRangeLast[rangeID] < page )
562 giPhysRangeLast[rangeID] = page;
565 // If the bitmap entry is not -1, unset the bit in the super bitmap
566 if(gaMainBitmap[ page >> 6 ] + 1 != 0 ) {
567 gaSuperBitmap[page >> 12] &= ~(1LL << ((page >> 6) & 63));
571 Log("Page %P dereferenced (%i)", page << 12, MM_GetRefCount(page << 12));
575 int MM_GetRefCount( tPAddr PAddr )
579 if( PAddr > giMaxPhysPage ) return 0;
581 if( MM_GetPhysAddr( (tVAddr)&gaiPageReferences[PAddr] ) ) {
582 return gaiPageReferences[PAddr];
585 if( PAGE_ALLOC_TEST(PAddr) )
593 * \brief Takes a physical address and returns the ID of its range
594 * \param Addr Physical address of page
595 * \return Range ID from eMMPhys_Ranges
597 int MM_int_GetRangeID( tPAddr Addr )
602 return MM_PHYS_32BIT;
604 return MM_PHYS_24BIT;
606 return MM_PHYS_20BIT;
608 return MM_PHYS_16BIT;
611 int MM_SetPageNode(tPAddr PAddr, void *Node)
613 tPAddr page = PAddr >> 12;
614 tVAddr node_page = ((tVAddr)&gapPageNodes[page]) & ~(PAGE_SIZE-1);
616 // if( !MM_GetRefCount(PAddr) ) return 1;
618 if( !MM_GetPhysAddr(node_page) ) {
619 if( !MM_Allocate(node_page) )
621 memset( (void*)node_page, 0, PAGE_SIZE );
624 gapPageNodes[page] = Node;
628 int MM_GetPageNode(tPAddr PAddr, void **Node)
630 // if( !MM_GetRefCount(PAddr) ) return 1;
633 if( !MM_GetPhysAddr( (tVAddr)&gapPageNodes[PAddr] ) ) {
638 *Node = gapPageNodes[PAddr];