4 * Physical Memory Manager
12 MM_PHYS_16BIT, // Does anything need this?
13 MM_PHYS_20BIT, // Real-Mode
14 MM_PHYS_24BIT, // ISA DMA
15 MM_PHYS_32BIT, // x86 Hardware
16 MM_PHYS_MAX, // Doesn't care
21 extern void gKernelBase;
22 extern void gKernelEnd;
25 void MM_InitPhys_Multiboot(tMBoot_Info *MBoot);
26 tPAddr MM_AllocPhysRange(int Num, int Bits);
27 tPAddr MM_AllocPhys(void);
28 void MM_RefPhys(tPAddr PAddr);
29 void MM_DerefPhys(tPAddr PAddr);
30 int MM_int_GetRangeID( tPAddr Addr );
33 tSpinlock glPhysicalPages;
34 Uint64 *gaSuperBitmap; // 1 bit = 64 Pages, 16 MiB Per Word
35 Uint64 *gaMainBitmap; // 1 bit = 1 Page, 256 KiB per Word
36 Uint64 *gaMultiBitmap; // Each bit means that the page is being used multiple times
37 Uint32 *gaiPageReferences = (void*)MM_PAGE_COUNTS; // Reference Counts
38 tPAddr giFirstFreePage; // First possibly free page
39 Uint64 giPhysRangeFree[NUM_MM_PHYS_RANGES]; // Number of free pages in each range
40 Uint64 giPhysRangeFirst[NUM_MM_PHYS_RANGES]; // First free page in each range
41 Uint64 giPhysRangeLast[NUM_MM_PHYS_RANGES]; // Last free page in each range
42 Uint64 giMaxPhysPage = 0; // Maximum Physical page
43 // Only used in init, allows the init code to provide pages for use by
44 // the allocator before the bitmaps exist.
45 // 3 entries because the are three calls to MM_AllocPhys in MM_Map
46 #define NUM_STATIC_ALLOC 3
47 tPAddr gaiStaticAllocPages[NUM_STATIC_ALLOC] = {0};
51 * \brief Initialise the physical memory map using a Multiboot 1 map
53 void MM_InitPhys_Multiboot(tMBoot_Info *MBoot)
55 tMBoot_MMapEnt *mmapStart;
58 int numPages, superPages;
62 tPAddr paddr, firstFreePage;
64 Log("MM_InitPhys_Multiboot: (MBoot=%p)", MBoot);
66 // Scan the physical memory map
67 // Looking for the top of physical memory
68 mmapStart = (void *)( KERNEL_BASE | MBoot->MMapAddr );
69 Log(" MM_InitPhys_Multiboot: mmapStart = %p", mmapStart);
71 while( (Uint)ent < (Uint)mmapStart + MBoot->MMapLength )
73 // Adjust for the size of the entry
75 Log(" MM_InitPhys_Multiboot: ent={Type:%i,Base:0x%x,Length:%x",
76 ent->Type, ent->Base, ent->Length);
78 // If entry is RAM and is above `maxAddr`, change `maxAddr`
79 if(ent->Type == 1 && ent->Base + ent->Length > maxAddr)
80 maxAddr = ent->Base + ent->Length;
83 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size );
86 // Did we find a valid end?
88 // No, darn, let's just use the HighMem hack
89 giMaxPhysPage = (MBoot->HighMem >> 2) + 256; // HighMem is a kByte value
92 // Goodie, goodie gumdrops
93 giMaxPhysPage = maxAddr >> 12;
95 Log(" MM_InitPhys_Multiboot: giMaxPhysPage = 0x%x", giMaxPhysPage);
97 // Find a contigous section of memory to hold it in
98 // - Starting from the end of the kernel
99 // - We also need a region for the super bitmap
100 superPages = ((giMaxPhysPage+64*8-1)/(64*8) + 0xFFF) >> 12;
101 numPages = (giMaxPhysPage + 7) / 8;
102 numPages = (numPages + 0xFFF) >> 12;
103 Log(" MM_InitPhys_Multiboot: numPages = %i, superPages = %i",
104 numPages, superPages);
107 int todo = numPages*2 + superPages;
108 // Ok, naieve allocation, just put it after the kernel
109 // - Allocated Bitmap
110 vaddr = MM_PAGE_BITMAP;
111 paddr = (tPAddr)&gKernelEnd - KERNEL_BASE;
115 for( i = 0; i < NUM_STATIC_ALLOC; i++) {
116 if(gaiStaticAllocPages[i] != 0) continue;
117 gaiStaticAllocPages[i] = paddr;
121 MM_Map(vaddr, paddr);
127 if( todo == numPages + superPages )
128 vaddr = MM_PAGE_DBLBMP;
129 if( todo == superPages )
130 vaddr = MM_PAGE_SUPBMP;
133 // Scan for a nice range
136 int todo = numPages*2 + superPages;
138 vaddr = MM_PAGE_BITMAP;
142 (Uint)ent < (Uint)mmapStart + MBoot->MMapLength;
143 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size )
152 // Let's not put it below the kernel, shall we?
153 if( ent->Base + ent->Size < (tPAddr)&gKernelBase )
156 Log(" MM_InitPhys_Multiboot: %x <= %x && %x > %x",
157 ent->Base, (tPAddr)&gKernelBase,
158 ent->Base + ent->Size, (tPAddr)&gKernelEnd - KERNEL_BASE
160 // Check if the kernel is in this range
161 if( ent->Base <= (tPAddr)&gKernelBase
162 && ent->Base + ent->Length > (tPAddr)&gKernelEnd - KERNEL_BASE )
164 avail = ent->Length >> 12;
165 avail -= ((tPAddr)&gKernelEnd - KERNEL_BASE - ent->Base) >> 12;
166 paddr = (tPAddr)&gKernelEnd - KERNEL_BASE;
168 // No? then we can use all of the block
171 avail = ent->Length >> 12;
175 Log(" MM_InitPhys_Multiboot: paddr=0x%x, avail=%i", paddr, avail);
178 while( todo && avail --)
180 // Static Allocations
181 for( i = 0; i < NUM_STATIC_ALLOC && avail; i++) {
182 if(gaiStaticAllocPages[i] != 0) continue;
183 gaiStaticAllocPages[i] = paddr;
190 MM_Map(vaddr, paddr);
195 // Alter the destination address when needed
196 if(todo == superPages+numPages)
197 vaddr = MM_PAGE_DBLBMP;
198 if(todo == superPages)
199 vaddr = MM_PAGE_SUPBMP;
202 // Fast quit if there's nothing left to allocate
206 // Save the current value of paddr to simplify the allocation later
207 firstFreePage = paddr;
209 Log(" MM_InitPhys_Multiboot: Clearing multi bitmap");
211 memset(gaMultiBitmap, 0, numPages<<12);
212 // - initialise to one, then clear the avaliable areas
213 memset(gaMainBitmap, -1, numPages<<12);
214 Log(" MM_InitPhys_Multiboot: Setting main bitmap");
215 // - Clear all Type=1 areas
216 Log(" MM_InitPhys_Multiboot: Clearing valid regions");
219 (Uint)ent < (Uint)mmapStart + MBoot->MMapLength;
220 ent = (tMBoot_MMapEnt *)( (Uint)ent + ent->Size )
223 // Check if the type is RAM
224 if(ent->Type != 1) continue;
227 base = ent->Base >> 12;
228 size = ent->Size >> 12;
231 Uint64 val = -1 << (base & 63);
232 gaMainBitmap[base / 64] &= ~val;
234 base += 64 - (base & 63);
236 memset( &gaMainBitmap[base / 64], 0, size/8 );
238 Uint64 val = -1 << (size & 7);
240 gaMainBitmap[base / 64] &= ~val;
244 base = ent->Base >> 12;
245 size = ent->Size >> 12;
246 size = (size + (base & 63) + 63) >> 6;
249 Uint64 val = -1 << (base & 63);
250 gaSuperBitmap[base / 64] &= ~val;
252 base += 64 - (base & 63);
256 // Reference the used pages
257 base = (tPAddr)&gKernelBase >> 12;
258 size = firstFreePage >> 12;
259 memset( &gaMainBitmap[base / 64], -1, size/8 );
261 Uint64 val = -1 << (size & 7);
263 gaMainBitmap[base / 64] |= val;
266 // Free the unused static allocs
267 for( i = 0; i < NUM_STATIC_ALLOC; i++) {
268 if(gaiStaticAllocPages[i] != 0)
270 gaMainBitmap[ gaiStaticAllocPages[i] >> (12+6) ]
271 &= ~(1 << ((gaiStaticAllocPages[i]>>12)&63));
274 // Fill the super bitmap
275 Log(" MM_InitPhys_Multiboot: Filling super bitmap");
276 memset(gaSuperBitmap, 0, superPages<<12);
277 for( base = 0; base < (size+63)/64; base ++)
279 if( gaMainBitmap[ base ] == -1 )
280 gaSuperBitmap[ base/64 ] |= 1 << (base&63);
283 // Set free page counts
284 for( base = 1; base < giMaxPhysPage; base ++ )
288 if( gaMainBitmap[ base >> 6 ] & (1 << (base&63)) ) continue;
291 rangeID = MM_int_GetRangeID( base << 12 );
293 // Increment free page count
294 giPhysRangeFree[ rangeID ] ++;
296 // Check for first free page in range
297 if(giPhysRangeFirst[ rangeID ] == 0)
298 giPhysRangeFirst[ rangeID ] = base;
299 // Set last (when the last free page is reached, this won't be
300 // updated anymore, hence will be correct)
301 giPhysRangeLast[ rangeID ] = base;
306 * \brief Allocate a contiguous range of physical pages with a maximum
307 * bit size of \a Bits
308 * \param Num Number of pages to allocate
309 * \param Bits Maximum size of the physical address
310 * \note If \a Bits is <= 0, any sized address is used (with preference
311 * to higher addresses)
313 tPAddr MM_AllocPhysRange(int Num, int Bits)
319 Log("MM_AllocPhysRange: (Num=%i,Bits=%i)", Num, Bits);
321 if( Bits <= 0 || Bits >= 64 ) // Speedup for the common case
322 rangeID = MM_PHYS_MAX;
324 rangeID = MM_int_GetRangeID( (1 << Bits) -1 );
326 Log(" MM_AllocPhysRange: rangeID = %i", rangeID);
328 LOCK(&glPhysicalPages);
329 Log(" MM_AllocPhysRange: i has lock");
331 // Check if the range actually has any free pages
332 while(giPhysRangeFree[rangeID] == 0 && rangeID)
335 Log(" MM_AllocPhysRange: rangeID = %i", rangeID);
337 // What the? Oh, man. No free pages
338 if(giPhysRangeFree[rangeID] == 0) {
339 RELEASE(&glPhysicalPages);
342 Warning(" MM_AllocPhysRange: Out of free pages");
344 "Out of memory (unable to fulfil request for %i pages), zero remaining",
350 // Check if there is enough in the range
351 if(giPhysRangeFree[rangeID] >= Num)
353 Log(" MM_AllocPhysRange: {%i,0x%x -> 0x%x}",
354 giPhysRangeFree[rangeID],
355 giPhysRangeFirst[rangeID], giPhysRangeLast[rangeID]
357 // Do a cheap scan, scanning upwards from the first free page in
360 addr = giPhysRangeFirst[ rangeID ];
361 while( addr <= giPhysRangeLast[ rangeID ] )
363 //Log(" MM_AllocPhysRange: addr = 0x%x", addr);
364 // Check the super bitmap
365 if( gaSuperBitmap[addr >> (6+6)] == -1 ) {
366 Log(" MM_AllocPhysRange: nFree = %i = 0 (super) (0x%x)", nFree, addr);
369 addr &= (1 << (6+6)) - 1;
372 // Check page block (64 pages)
373 if( gaSuperBitmap[addr >> (6+6)] & (1 << (addr>>6)&63)) {
374 Log(" MM_AllocPhysRange: nFree = %i = 0 (main) (0x%x)", nFree, addr);
377 addr &= (1 << (12+6)) - 1;
380 // Check individual page
381 if( gaMainBitmap[addr >> 6] & (1 << (addr & 63)) ) {
382 Log(" MM_AllocPhysRange: nFree = %i = 0 (page) (0x%x)", nFree, addr);
389 Log(" MM_AllocPhysRange: nFree(%i) == %i (0x%x)", nFree, Num, addr);
393 Log(" MM_AllocPhysRange: nFree = %i", nFree);
394 // If we don't find a contiguous block, nFree will not be equal
395 // to Num, so we set it to zero and do the expensive lookup.
396 if(nFree != Num) nFree = 0;
401 // Oops. ok, let's do an expensive check (scan down the list
402 // until a free range is found)
404 addr = giPhysRangeLast[ rangeID ];
406 RELEASE(&glPhysicalPages);
409 Warning(" MM_AllocPhysRange: Out of memory (unable to fulfil request for %i pages)", Num);
411 "Out of memory (unable to fulfil request for %i pages)",
416 Log(" MM_AllocPhysRange: nFree = %i, addr = 0x%08x", nFree, addr);
418 // Mark pages as allocated
420 for( i = 0; i < Num; i++ )
422 gaMainBitmap[addr >> 6] |= 1 << (addr & 63);
423 rangeID = MM_int_GetRangeID(addr);
424 giPhysRangeFree[ rangeID ] --;
427 // Update super bitmap
428 Num += addr & (64-1);
430 Num = (Num + (64-1)) & ~(64-1);
431 for( i = 0; i < Num/64; i++ )
433 if( gaMainBitmap[ addr >> 6 ] == -1 )
434 gaSuperBitmap[addr>>12] |= 1 << ((addr >> 6) & 64);
437 RELEASE(&glPhysicalPages);
438 Log("MM_AllocPhysRange: RETURN %x", addr << 12);
443 * \brief Allocate a single physical page, with no preference as to address
446 tPAddr MM_AllocPhys(void)
450 // Hack to allow allocation during setup
451 for(i = 0; i < NUM_STATIC_ALLOC; i++) {
452 if( gaiStaticAllocPages[i] ) {
453 tPAddr ret = gaiStaticAllocPages[i];
454 gaiStaticAllocPages[i] = 0;
455 Log("MM_AllocPhys: Return %x, static alloc %i", ret, i);
460 return MM_AllocPhysRange(1, -1);
464 * \brief Reference a physical page
466 void MM_RefPhys(tPAddr PAddr)
468 Uint64 page = PAddr >> 12;
470 if( PAddr >> 12 > giMaxPhysPage ) return ;
472 if( gaMainBitmap[ page >> 6 ] & (1 << (page&63)) )
475 gaMultiBitmap[ page >> 6 ] |= 1 << (page&63);
476 gaiPageReferences[ page ] ++;
481 gaMainBitmap[page >> 6] |= 1 << (page&63);
482 if( gaMainBitmap[page >> 6 ] == -1 )
483 gaSuperBitmap[page>> 12] |= 1 << ((page >> 6) & 63);
488 * \brief Dereference a physical page
490 void MM_DerefPhys(tPAddr PAddr)
492 Uint64 page = PAddr >> 12;
494 if( PAddr >> 12 > giMaxPhysPage ) return ;
496 if( gaMultiBitmap[ page >> 6 ] & (1 << (page&63)) ) {
497 gaiPageReferences[ page ] --;
498 if( gaiPageReferences[ page ] == 1 )
499 gaMultiBitmap[ page >> 6 ] &= ~(1 << (page&63));
500 if( gaiPageReferences[ page ] == 0 )
501 gaMainBitmap[ page >> 6 ] &= ~(1 << (page&63));
504 gaMainBitmap[ page >> 6 ] &= ~(1 << (page&63));
506 // TODO: Update free counts
507 if( !(gaMainBitmap[ page >> 6 ] & (1 << (page&63))) )
510 rangeID = MM_int_GetRangeID( PAddr );
511 giPhysRangeFree[ rangeID ] ++;
514 if(gaMainBitmap[ page >> 6 ] == 0) {
515 gaSuperBitmap[page >> 12] &= ~(1 << ((page >> 6) & 63));
520 * \brief Takes a physical address and returns the ID of its range
521 * \param Addr Physical address of page
522 * \return Range ID from eMMPhys_Ranges
524 int MM_int_GetRangeID( tPAddr Addr )
529 return MM_PHYS_32BIT;
531 return MM_PHYS_24BIT;
533 return MM_PHYS_20BIT;
535 return MM_PHYS_16BIT;