4 * Physical Memory Manager
13 MM_PHYS_16BIT, // Does anything need this?
14 MM_PHYS_20BIT, // Real-Mode
15 MM_PHYS_24BIT, // ISA DMA
16 MM_PHYS_32BIT, // x86 Hardware
17 MM_PHYS_MAX, // Doesn't care
22 extern char gKernelBase[];
23 extern char gKernelEnd[];
26 void MM_InitPhys_Multiboot(tMBoot_Info *MBoot);
27 //tPAddr MM_AllocPhysRange(int Num, int Bits);
28 //tPAddr MM_AllocPhys(void);
29 //void MM_RefPhys(tPAddr PAddr);
30 //void MM_DerefPhys(tPAddr PAddr);
31 int MM_int_GetRangeID( tPAddr Addr );
34 tMutex glPhysicalPages;
35 Uint64 *gaSuperBitmap = (void*)MM_PAGE_SUPBMP; // 1 bit = 64 Pages, 16 MiB per Word
36 Uint64 *gaMainBitmap = (void*)MM_PAGE_BITMAP; // 1 bit = 1 Page, 256 KiB per Word
37 Uint64 *gaMultiBitmap = (void*)MM_PAGE_DBLBMP; // Each bit means that the page is being used multiple times
38 Uint32 *gaiPageReferences = (void*)MM_PAGE_COUNTS; // Reference Counts
39 void **gapPageNodes = (void*)MM_PAGE_NODES; // Reference Counts
40 tPAddr giFirstFreePage; // First possibly free page
41 Uint64 giPhysRangeFree[NUM_MM_PHYS_RANGES]; // Number of free pages in each range
42 Uint64 giPhysRangeFirst[NUM_MM_PHYS_RANGES]; // First free page in each range
43 Uint64 giPhysRangeLast[NUM_MM_PHYS_RANGES]; // Last free page in each range
44 Uint64 giMaxPhysPage = 0; // Maximum Physical page
45 // Only used in init, allows the init code to provide pages for use by
46 // the allocator before the bitmaps exist.
47 // 3 entries because the are three calls to MM_AllocPhys in MM_Map
48 #define NUM_STATIC_ALLOC 3
49 tPAddr gaiStaticAllocPages[NUM_STATIC_ALLOC] = {0};
53 * \brief Initialise the physical memory map using a Multiboot 1 map
55 void MM_InitPhys_Multiboot(tMBoot_Info *MBoot)
57 tMBoot_MMapEnt *mmapStart;
60 int numPages, superPages;
64 tPAddr paddr, firstFreePage;
66 ENTER("pMBoot=%p", MBoot);
68 // Scan the physical memory map
69 // Looking for the top of physical memory
70 mmapStart = (void *)( KERNEL_BASE | MBoot->MMapAddr );
71 LOG("mmapStart = %p", mmapStart);
73 while( (Uint)ent < (Uint)mmapStart + MBoot->MMapLength )
75 // Adjust for the size of the entry
77 LOG("ent={Type:%i,Base:0x%x,Length:%x",
78 ent->Type, ent->Base, ent->Length);
80 // If entry is RAM and is above `maxAddr`, change `maxAddr`
81 if(ent->Type == 1 && ent->Base + ent->Length > maxAddr)
82 maxAddr = ent->Base + ent->Length;
85 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size );
88 // Did we find a valid end?
90 // No, darn, let's just use the HighMem hack
91 giMaxPhysPage = (MBoot->HighMem >> 2) + 256; // HighMem is a kByte value
94 // Goodie, goodie gumdrops
95 giMaxPhysPage = maxAddr >> 12;
97 LOG("giMaxPhysPage = 0x%x", giMaxPhysPage);
99 // Find a contigous section of memory to hold it in
100 // - Starting from the end of the kernel
101 // - We also need a region for the super bitmap
102 superPages = ((giMaxPhysPage+64*8-1)/(64*8) + 0xFFF) >> 12;
103 numPages = (giMaxPhysPage + 7) / 8;
104 numPages = (numPages + 0xFFF) >> 12;
105 LOG("numPages = %i, superPages = %i", numPages, superPages);
108 int todo = numPages*2 + superPages;
109 // Ok, naieve allocation, just put it after the kernel
110 // - Allocated Bitmap
111 vaddr = MM_PAGE_BITMAP;
112 paddr = (tPAddr)&gKernelEnd - KERNEL_BASE;
116 for( i = 0; i < NUM_STATIC_ALLOC; i++) {
117 if(gaiStaticAllocPages[i] != 0) continue;
118 gaiStaticAllocPages[i] = paddr;
122 MM_Map(vaddr, paddr);
128 if( todo == numPages + superPages )
129 vaddr = MM_PAGE_DBLBMP;
130 if( todo == superPages )
131 vaddr = MM_PAGE_SUPBMP;
134 // Scan for a nice range
137 int todo = numPages*2 + superPages;
139 vaddr = MM_PAGE_BITMAP;
143 (Uint)ent < (Uint)mmapStart + MBoot->MMapLength;
144 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size )
153 // Let's not put it below the kernel, shall we?
154 if( ent->Base + ent->Size < (tPAddr)&gKernelBase )
157 LOG("%x <= %x && %x > %x",
158 ent->Base, (tPAddr)&gKernelBase,
159 ent->Base + ent->Size, (tPAddr)&gKernelEnd - KERNEL_BASE
161 // Check if the kernel is in this range
162 if( ent->Base <= (tPAddr)&gKernelBase
163 && ent->Base + ent->Length > (tPAddr)&gKernelEnd - KERNEL_BASE )
165 avail = ent->Length >> 12;
166 avail -= ((tPAddr)&gKernelEnd - KERNEL_BASE - ent->Base) >> 12;
167 paddr = (tPAddr)&gKernelEnd - KERNEL_BASE;
169 // No? then we can use all of the block
172 avail = ent->Length >> 12;
176 Log(" MM_InitPhys_Multiboot: paddr=0x%x, avail=%i", paddr, avail);
179 while( todo && avail --)
181 // Static Allocations
182 for( i = 0; i < NUM_STATIC_ALLOC && avail; i++) {
183 if(gaiStaticAllocPages[i] != 0) continue;
184 gaiStaticAllocPages[i] = paddr;
191 MM_Map(vaddr, paddr);
196 // Alter the destination address when needed
197 if(todo == superPages+numPages)
198 vaddr = MM_PAGE_DBLBMP;
199 if(todo == superPages)
200 vaddr = MM_PAGE_SUPBMP;
203 // Fast quit if there's nothing left to allocate
207 // Save the current value of paddr to simplify the allocation later
208 firstFreePage = paddr;
210 LOG("Clearing multi bitmap");
212 memset(gaMultiBitmap, 0, (numPages<<12)/8);
213 // - initialise to one, then clear the avaliable areas
214 memset(gaMainBitmap, -1, (numPages<<12)/8);
215 memset(gaSuperBitmap, -1, (numPages<<12)/(8*64));
216 LOG("Setting main bitmap");
217 // - Clear all Type=1 areas
218 LOG("Clearing valid regions");
221 (Uint)ent < (Uint)mmapStart + MBoot->MMapLength;
222 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size )
225 // Check if the type is RAM
226 if(ent->Type != 1) continue;
229 base = ent->Base >> 12;
230 size = ent->Size >> 12;
233 Uint64 val = -1LL << (base & 63);
234 gaMainBitmap[base / 64] &= ~val;
236 base += 64 - (base & 63);
238 memset( &gaMainBitmap[base / 64], 0, size/8 );
240 Uint64 val = -1LL << (size & 7);
242 gaMainBitmap[base / 64] &= ~val;
246 base = ent->Base >> 12;
247 size = ent->Size >> 12;
248 size = (size + (base & 63) + 63) >> 6;
251 Uint64 val = -1LL << (base & 63);
252 gaSuperBitmap[base / 64] &= ~val;
253 // size -= (base & 63);
254 // base += 64 - (base & 63);
258 // Reference the used pages
259 base = (tPAddr)&gKernelBase >> 12;
260 size = firstFreePage >> 12;
261 memset( &gaMainBitmap[base / 64], -1, size/8 );
263 Uint64 val = -1LL << (size & 7);
265 gaMainBitmap[base / 64] |= val;
268 // Free the unused static allocs
269 for( i = 0; i < NUM_STATIC_ALLOC; i++) {
270 if(gaiStaticAllocPages[i] != 0)
272 gaMainBitmap[ gaiStaticAllocPages[i] >> (12+6) ]
273 &= ~(1LL << ((gaiStaticAllocPages[i]>>12)&63));
276 // Fill the super bitmap
277 LOG("Filling super bitmap");
278 memset(gaSuperBitmap, 0, superPages<<12);
279 for( base = 0; base < (size+63)/64; base ++)
281 if( gaMainBitmap[ base ] + 1 == 0 )
282 gaSuperBitmap[ base/64 ] |= 1LL << (base&63);
285 // Set free page counts
286 for( base = 1; base < giMaxPhysPage; base ++ )
290 if( gaMainBitmap[ base >> 6 ] & (1LL << (base&63)) ) continue;
293 rangeID = MM_int_GetRangeID( base << 12 );
295 // Increment free page count
296 giPhysRangeFree[ rangeID ] ++;
298 // Check for first free page in range
299 if(giPhysRangeFirst[ rangeID ] == 0)
300 giPhysRangeFirst[ rangeID ] = base;
301 // Set last (when the last free page is reached, this won't be
302 // updated anymore, hence will be correct)
303 giPhysRangeLast[ rangeID ] = base;
310 * \brief Allocate a contiguous range of physical pages with a maximum
311 * bit size of \a MaxBits
312 * \param Pages Number of pages to allocate
313 * \param MaxBits Maximum size of the physical address
314 * \note If \a MaxBits is <= 0, any sized address is used (with preference
315 * to higher addresses)
317 tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
323 ENTER("iPages iBits", Pages, MaxBits);
325 if( MaxBits <= 0 || MaxBits >= 64 ) // Speedup for the common case
326 rangeID = MM_PHYS_MAX;
328 rangeID = MM_int_GetRangeID( (1LL << MaxBits) - 1 );
330 LOG("rangeID = %i", rangeID);
332 Mutex_Acquire(&glPhysicalPages);
334 // Check if the range actually has any free pages
335 while(giPhysRangeFree[rangeID] == 0 && rangeID)
338 LOG("rangeID = %i", rangeID);
340 // What the? Oh, man. No free pages
341 if(giPhysRangeFree[rangeID] == 0) {
342 Mutex_Release(&glPhysicalPages);
345 Warning(" MM_AllocPhysRange: Out of free pages");
347 "Out of memory (unable to fulfil request for %i pages), zero remaining",
354 // Check if there is enough in the range
355 if(giPhysRangeFree[rangeID] >= Pages)
357 LOG("{%i,0x%x -> 0x%x}",
358 giPhysRangeFree[rangeID],
359 giPhysRangeFirst[rangeID], giPhysRangeLast[rangeID]
361 // Do a cheap scan, scanning upwards from the first free page in
364 addr = giPhysRangeFirst[ rangeID ];
365 while( addr <= giPhysRangeLast[ rangeID ] )
367 //Log(" MM_AllocPhysRange: addr = 0x%x", addr);
368 // Check the super bitmap
369 if( gaSuperBitmap[addr >> (6+6)] + 1 == 0 ) {
370 LOG("nFree = %i = 0 (super) (0x%x)", nFree, addr);
372 addr += 1LL << (6+6);
373 addr &= ~0xFFF; // (1LL << 6+6) - 1
376 // Check page block (64 pages)
377 if( gaMainBitmap[addr >> 6] + 1 == 0) {
378 LOG("nFree = %i = 0 (main) (0x%x)", nFree, addr);
384 // Check individual page
385 if( gaMainBitmap[addr >> 6] & (1LL << (addr & 63)) ) {
386 LOG("nFree = %i = 0 (page) (0x%x)", nFree, addr);
393 LOG("nFree(%i) == %i (0x%x)", nFree, Pages, addr);
397 LOG("nFree = %i", nFree);
398 // If we don't find a contiguous block, nFree will not be equal
399 // to Num, so we set it to zero and do the expensive lookup.
400 if(nFree != Pages) nFree = 0;
405 // Oops. ok, let's do an expensive check (scan down the list
406 // until a free range is found)
408 // addr = giPhysRangeLast[ rangeID ];
409 // TODO: Expensive Check
410 Mutex_Release(&glPhysicalPages);
413 Warning(" MM_AllocPhysRange: Out of memory (unable to fulfil request for %i pages)", Pages);
415 "Out of memory (unable to fulfil request for %i pages)",
421 LOG("nFree = %i, addr = 0x%08x", nFree, addr);
423 // Mark pages as allocated
425 for( i = 0; i < Pages; i++, addr++ )
427 gaMainBitmap[addr >> 6] |= 1LL << (addr & 63);
428 rangeID = MM_int_GetRangeID(addr << 12);
429 giPhysRangeFree[ rangeID ] --;
430 LOG("%x == %x", addr, giPhysRangeFirst[ rangeID ]);
431 if(addr == giPhysRangeFirst[ rangeID ])
432 giPhysRangeFirst[ rangeID ] += 1;
434 ret = addr; // Save the return address
436 // Update super bitmap
437 Pages += addr & (64-1);
439 Pages = (Pages + (64-1)) & ~(64-1);
440 for( i = 0; i < Pages/64; i++ )
442 if( gaMainBitmap[ addr >> 6 ] + 1 == 0 )
443 gaSuperBitmap[addr>>12] |= 1LL << ((addr >> 6) & 63);
446 Mutex_Release(&glPhysicalPages);
447 LEAVE('x', ret << 12);
452 * \brief Allocate a single physical page, with no preference as to address
455 tPAddr MM_AllocPhys(void)
459 // Hack to allow allocation during setup
460 for(i = 0; i < NUM_STATIC_ALLOC; i++) {
461 if( gaiStaticAllocPages[i] ) {
462 tPAddr ret = gaiStaticAllocPages[i];
463 gaiStaticAllocPages[i] = 0;
464 Log("MM_AllocPhys: Return %P, static alloc %i", ret, i);
469 return MM_AllocPhysRange(1, -1);
473 * \brief Reference a physical page
475 void MM_RefPhys(tPAddr PAddr)
477 Uint64 page = PAddr >> 12;
479 if( PAddr >> 12 > giMaxPhysPage ) return ;
481 if( gaMainBitmap[ page >> 6 ] & (1LL << (page&63)) )
484 gaMultiBitmap[ page >> 6 ] |= 1LL << (page&63);
485 if( !MM_GetPhysAddr( ((tVAddr)&gaiPageReferences[ page ]) & ~0xFFF ) ) {
486 if( !MM_Allocate( ((tVAddr)&gaiPageReferences[ page ]) & ~0xFFF ) ) {
487 Log_Error("Arch", "Out of memory when allocating reference count page");
491 gaiPageReferences[ page ] ++;
496 gaMainBitmap[page >> 6] |= 1LL << (page&63);
497 if( gaMainBitmap[page >> 6 ] + 1 == 0 )
498 gaSuperBitmap[page>> 12] |= 1LL << ((page >> 6) & 63);
503 * \brief Dereference a physical page
505 void MM_DerefPhys(tPAddr PAddr)
507 Uint64 page = PAddr >> 12;
509 if( PAddr >> 12 > giMaxPhysPage ) return ;
511 if( gaMultiBitmap[ page >> 6 ] & (1LL << (page&63)) ) {
512 gaiPageReferences[ page ] --;
513 if( gaiPageReferences[ page ] == 1 )
514 gaMultiBitmap[ page >> 6 ] &= ~(1LL << (page&63));
515 if( gaiPageReferences[ page ] == 0 )
516 gaMainBitmap[ page >> 6 ] &= ~(1LL << (page&63));
519 gaMainBitmap[ page >> 6 ] &= ~(1LL << (page&63));
521 // Update the free counts if the page was freed
522 if( !(gaMainBitmap[ page >> 6 ] & (1LL << (page&63))) )
525 rangeID = MM_int_GetRangeID( PAddr );
526 giPhysRangeFree[ rangeID ] ++;
527 if( giPhysRangeFirst[rangeID] > page )
528 giPhysRangeFirst[rangeID] = page;
529 if( giPhysRangeLast[rangeID] < page )
530 giPhysRangeLast[rangeID] = page;
533 // If the bitmap entry is not -1, unset the bit in the super bitmap
534 if(gaMainBitmap[ page >> 6 ] + 1 != 0 ) {
535 gaSuperBitmap[page >> 12] &= ~(1LL << ((page >> 6) & 63));
539 int MM_GetRefCount( tPAddr PAddr )
543 if( PAddr >> 12 > giMaxPhysPage ) return 0;
545 if( gaMultiBitmap[ PAddr >> 6 ] & (1LL << (PAddr&63)) ) {
546 return gaiPageReferences[PAddr];
549 if( gaMainBitmap[ PAddr >> 6 ] & (1LL << (PAddr&63)) )
557 * \brief Takes a physical address and returns the ID of its range
558 * \param Addr Physical address of page
559 * \return Range ID from eMMPhys_Ranges
561 int MM_int_GetRangeID( tPAddr Addr )
566 return MM_PHYS_32BIT;
568 return MM_PHYS_24BIT;
570 return MM_PHYS_20BIT;
572 return MM_PHYS_16BIT;
575 int MM_SetPageNode(tPAddr PAddr, void *Node)
577 tPAddr page = PAddr >> 12;
578 tVAddr node_page = ((tVAddr)&gapPageNodes[page]) & ~(PAGE_SIZE-1);
580 // if( !MM_GetRefCount(PAddr) ) return 1;
582 if( !MM_GetPhysAddr(node_page) ) {
583 if( !MM_Allocate(node_page) )
585 memset( (void*)node_page, 0, PAGE_SIZE );
588 gapPageNodes[page] = Node;
592 int MM_GetPageNode(tPAddr PAddr, void **Node)
594 // if( !MM_GetRefCount(PAddr) ) return 1;
597 if( !MM_GetPhysAddr( (tVAddr)&gapPageNodes[PAddr] ) ) {
602 *Node = gapPageNodes[PAddr];