7a28940fd9466a871fcdded12e508bca5bf65d88
[tpg/acess2.git] / mm_phys.c
1 /*
2  * Acess2
3  * - Physical memory manager
4  */
5 #define DEBUG   0
6 #include <acess.h>
7 #include <mm_virt.h>
8 #include <pmemmap.h>
9 #include <hal_proc.h>
10 #include <semaphore.h>
11 #include <debug_hooks.h>
12
13 //#define USE_STACK     1
14 #define TRACE_ALLOCS    0       // Print trace messages on AllocPhys/DerefPhys
15
16 static const int addrClasses[] = {0,16,20,24,32,64};
17 static const int numAddrClasses = sizeof(addrClasses)/sizeof(addrClasses[0]);
18
19 // === PROTOTYPES ===
20 void    MM_Install(int NPMemRanges, tPMemMapEnt *PMemRanges);
21 //tPAddr        MM_AllocPhys(void);
22 //tPAddr        MM_AllocPhysRange(int Pages, int MaxBits);
23 //void  MM_RefPhys(tPAddr PAddr);
24 //void  MM_DerefPhys(tPAddr PAddr);
25 // int  MM_GetRefCount(tPAddr PAddr);
26
27 // === GLOBALS ===
28 tMutex  glPhysAlloc;
29 Uint64  giPhysAlloc = 0;        // Number of allocated pages
30 Uint64  giPageCount = 0;        // Total number of pages
31 Uint64  giLastPossibleFree = 0; // Last possible free page (before all pages are used)
32 Uint64  giTotalMemorySize = 0;  // Total number of allocatable pages
33
34 Uint32  gaSuperBitmap[1024];    // Blocks of 1024 Pages
35 Uint32  gaPageBitmap[1024*1024/32];     // Individual pages
36  int    *gaPageReferences;
37 void    **gaPageNodes = (void*)MM_PAGENODE_BASE;
38 #define REFENT_PER_PAGE (0x1000/sizeof(gaPageReferences[0]))
39
40 // === CODE ===
41 void MM_Install(int NPMemRanges, tPMemMapEnt *PMemRanges)
42 {
43         Uint64  maxAddr = 0;
44         
45         // --- Find largest address
46         for( Uint i = 0; i < NPMemRanges; i ++ )
47         {
48                 tPMemMapEnt     *ent = &PMemRanges[i];
49                 // If entry is RAM and is above `maxAddr`, change `maxAddr`
50                 if(ent->Type == PMEMTYPE_FREE || ent->Type == PMEMTYPE_USED)
51                 {
52                         if(ent->Start + ent->Length > maxAddr)
53                                 maxAddr = ent->Start + ent->Length;
54                         giTotalMemorySize += ent->Length >> 12;
55                 }
56         }
57         LOG("giTotalMemorySize = %lli KiB", giTotalMemorySize*4);
58         LOG("maxAddr = 0x%X", maxAddr);
59         
60         // Clip to 32-bits
61         if( maxAddr > (1ULL << 32) ) {
62                 maxAddr = (1ULL << 32);
63         }
64         
65         giPageCount = maxAddr >> 12;
66         giLastPossibleFree = giPageCount - 1;
67         memsetd(gaPageBitmap, 0xFFFFFFFF, giPageCount/32);
68         
69         // Set up allocateable space
70         for( Uint i = 0; i < NPMemRanges; i ++ )
71         {
72                 tPMemMapEnt *ent = &PMemRanges[i];
73                 if( ent->Type == PMEMTYPE_FREE )
74                 {
75                         Uint64  startpg = ent->Start / PAGE_SIZE;
76                         Uint64  pgcount = ent->Length / PAGE_SIZE;
77                         // Ignore start addresses >32 bits
78                         if( startpg > (1 << 20) )
79                                 continue ;
80                         // Clip lengths to 32-bit address space
81                         if( startpg + pgcount > (1<<20) )
82                                 pgcount = (1<<20) - startpg;
83                         
84                         while( startpg % 32 && pgcount ) {
85                                 gaPageBitmap[startpg/32] &= ~(1U << (startpg%32));
86                                 startpg ++;
87                                 pgcount --;
88                         }
89                         memsetd( &gaPageBitmap[startpg/32], 0, pgcount/32 );
90                         startpg += pgcount - pgcount%32;
91                         pgcount -= pgcount - pgcount%32;
92                         while(pgcount) {
93                                 gaPageBitmap[startpg/32] &= ~(1U << (startpg%32));
94                                 startpg ++;
95                                 pgcount --;
96                         }
97                 }
98                 else if( ent->Type == PMEMTYPE_USED )
99                 {
100                         // TODO: Clip?
101                         giPhysAlloc += ent->Length / PAGE_SIZE;
102                 }
103         }
104
105         // Fill Superpage bitmap
106         // - A set bit means that there are no free pages in this block of 32
107         for( Uint i = 0; i < (giPageCount+31)/32; i ++ )
108         {
109                 if( gaPageBitmap[i] + 1 == 0 ) {
110                         gaSuperBitmap[i/32] |= (1 << i%32);
111                 }
112         }
113         
114         gaPageReferences = (void*)MM_REFCOUNT_BASE;
115
116         Log_Debug("PMem", "maxAddr = %P", maxAddr);
117         Log_Log("PMem", "Physical memory set up (%lli pages of ~%lli MiB used)",
118                 giPhysAlloc, (giTotalMemorySize*PAGE_SIZE)/(1024*1024)
119                 );
120 }
121
122 void MM_DumpStatistics(void)
123 {
124         for( int i = 1; i < numAddrClasses; i ++ )
125         {
126                 const int       first = (i == 1 ? 0 : (1UL << (addrClasses[i-1] - 12)));
127                 const int       last  = MIN( (1UL << (addrClasses[i] - 12)) - 1, giPageCount );
128                 const int       total = last - first + 1;
129                 
130                  int    nFree = 0;
131                  int    nMultiRef = 0;
132                  int    totalRefs = 0;
133                 bool    refpage_valid = !!MM_GetPhysAddr(&gaPageReferences[first]);
134                 
135                 for( Uint pg = first; pg < last; pg ++ )
136                 {
137                         // Free chunk
138                         if( gaPageBitmap[pg/32] == 0 )
139                         {
140                                 int count = 32 - pg%32;
141                                 nFree += count;
142                                 pg += count - 1;
143                                 continue ;
144                         }
145                         
146                         // Single free
147                         if( !(gaPageBitmap[pg/32] & (1 << pg%32)) )
148                         {
149                                 nFree ++;
150                                 continue ;
151                         }
152                         
153                         // Check if reference page is valid
154                         if( pg % (PAGE_SIZE/sizeof(gaPageReferences[0])) == 0 ) {
155                                 refpage_valid = !!MM_GetPhysAddr(&gaPageReferences[pg]);
156                         }
157                         
158                         // 
159                         if( refpage_valid && gaPageReferences[pg] > 1 ) {
160                                 totalRefs += gaPageReferences[pg];
161                                 nMultiRef ++;
162                         }
163                         else
164                                 totalRefs ++;
165                 }
166                 
167                  int    nUsed = (total - nFree);
168                 Log_Log("MMPhys", "%ipbit - %i/%i used, %i reused, %i average reference count",
169                         addrClasses[i], nUsed, total, nMultiRef,
170                         nMultiRef ? (totalRefs-(nUsed - nMultiRef)) / nMultiRef : 0
171                         );
172                 // TODO: Calculate fragentation of physical memory.
173                 // > Somehow support defragmenting?
174                 
175                 if( last == giPageCount )
176                         break;
177         }
178         Log_Log("MMPhys", "%lli/%lli total pages used, 0 - %i possible free range",
179                 giPhysAlloc, giTotalMemorySize, giLastPossibleFree);
180         
181          int    startpage = 0;
182          int    last_refcnt = 0;
183         void    *last_node = NULL;
184         for( int pg = 0; pg < giPageCount; pg ++ )
185         {
186                 bool    output = 0;
187                  int    refcount = 0;
188                 void    *node = NULL;
189                 if( !(gaPageBitmap[pg/32] & (1 << pg%32)) )
190                 {
191                         // free
192                         output = 1;
193                 }
194                 else
195                 {
196                         refcount = MM_GetPhysAddr(&gaPageReferences[pg]) ? gaPageReferences[pg] : 1;
197                         node = MM_GetPhysAddr(&gaPageNodes[pg]) ? gaPageNodes[pg] : NULL;
198                         
199                         if( last_refcnt != refcount || last_node != node )
200                                 output = 1;
201                 }
202                 if( output || pg == giPageCount-1 )
203                 {
204                         if( last_refcnt > 0 )
205                                 Debug("0x%4x+%i: node=%p refcount=%i", pg-startpage, last_node, last_refcnt);
206                         startpage = pg;
207                 }
208                 last_refcnt = refcount;
209                 last_node = node;
210         }
211 }
212
213 /**
214  * \fn tPAddr MM_AllocPhys(void)
215  * \brief Allocates a physical page from the general pool
216  */
217 tPAddr MM_AllocPhys(void)
218 {
219          int    indx = -1;
220         tPAddr  ret;
221         
222         ENTER("");
223         
224         Mutex_Acquire( &glPhysAlloc );
225         
226         // Classful scan
227         {
228          int    i;
229          int    first, last;
230         for( i = numAddrClasses; i -- > 1; )
231         {
232                 first = 1UL << (addrClasses[i-1] - 12);
233                 last = (1UL << (addrClasses[i] - 12)) - 1;
234                 // Range is above the last free page
235                 if( first > giLastPossibleFree )
236                         continue;
237                 // Last possible free page is in the range
238                 if( last > giLastPossibleFree )
239                         last = giLastPossibleFree;
240                         
241                 // Scan the range
242                 for( indx = first; indx < last; )
243                 {
244                         if( gaSuperBitmap[indx>>10] == -1 ) {
245                                 indx += 1024;
246                                 continue;
247                         }
248                         
249                         if( gaPageBitmap[indx>>5] == -1 ) {
250                                 indx += 32;
251                                 continue;
252                         }
253                         
254                         if( gaPageBitmap[indx>>5] & (1 << (indx&31)) ) {
255                                 indx ++;
256                                 continue;
257                         }
258                         break;
259                 }
260                 if( indx < last )       break;
261                 
262                 giLastPossibleFree = first;     // Well, we couldn't find any in this range
263         }
264         // Out of memory?
265         if( i <= 1 )    indx = -1;
266         }
267         
268         if( indx < 0 ) {
269                 Mutex_Release( &glPhysAlloc );
270                 Warning("MM_AllocPhys - OUT OF MEMORY (Called by %p) - %lli/%lli used (indx = %x)",
271                         __builtin_return_address(0), giPhysAlloc, giPageCount, indx);
272                 Log_Debug("PMem", "giLastPossibleFree = %lli", giLastPossibleFree);
273                 LEAVE('i', 0);
274                 return 0;
275         }
276         
277         if( indx > 0xFFFFF ) {
278                 Panic("The fuck? Too many pages! (indx = 0x%x)", indx);
279         }
280         
281         if( indx >= giPageCount ) {
282                 Mutex_Release( &glPhysAlloc );
283                 Log_Error("PMem", "MM_AllocPhys - indx(%i) > giPageCount(%i)", indx, giPageCount);
284                 LEAVE('i', 0);
285                 return 0;
286         }
287         
288         // Mark page used
289         if( MM_GetPhysAddr( &gaPageReferences[indx] ) )
290                 gaPageReferences[indx] = 1;
291         gaPageBitmap[ indx>>5 ] |= 1 << (indx&31);
292         
293         giPhysAlloc ++;
294         
295         // Get address
296         ret = indx << 12;
297         
298         // Mark used block
299         if(gaPageBitmap[ indx>>5 ] == -1) {
300                 gaSuperBitmap[indx>>10] |= 1 << ((indx>>5)&31);
301         }
302
303         // Release Spinlock
304         Mutex_Release( &glPhysAlloc );
305         LEAVE('P', ret);
306
307         #if TRACE_ALLOCS
308         if( now() > 4000 ) {
309         Log_Debug("PMem", "MM_AllocPhys: RETURN %P (%i free)", ret, giPageCount-giPhysAlloc);
310         Proc_PrintBacktrace();
311         }
312         #endif
313         return ret;
314 }
315
316 /**
317  * \fn tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
318  * \brief Allocate a range of physical pages
319  * \param Pages Number of pages to allocate
320  * \param MaxBits       Maximum number of address bits to use
321  */
322 tPAddr MM_AllocPhysRange(int Pages, int MaxBits)
323 {
324          int    i, idx, sidx;
325         tPAddr  ret;
326         
327         ENTER("iPages iMaxBits", Pages, MaxBits);
328         
329         // Sanity Checks
330         if(MaxBits < 0) {
331                 LEAVE('i', 0);
332                 return 0;
333         }
334         if(MaxBits > PHYS_BITS) MaxBits = PHYS_BITS;
335         
336         // Lock
337         Mutex_Acquire( &glPhysAlloc );
338         
339         // Set up search state
340         if( giLastPossibleFree > ((tPAddr)1 << (MaxBits-12)) ) {
341                 sidx = (tPAddr)1 << (MaxBits-12);
342         }
343         else {
344                 sidx = giLastPossibleFree;
345         }
346         idx = sidx / 32;
347         sidx %= 32;
348         
349         // Check if the gap is large enough
350         while( idx >= 0 )
351         {
352                 // Find a free page
353                 for( ; ; )
354                 {
355                         // Bulk Skip
356                         if( gaPageBitmap[idx] == -1 ) {
357                                 idx --;
358                                 sidx = 31;
359                                 continue;
360                         }
361                         
362                         if( gaPageBitmap[idx] & (1 << sidx) ) {
363                                 sidx --;
364                                 if(sidx < 0) {  sidx = 31;      idx --; }
365                                 if(idx < 0)     break;
366                                 continue;
367                         }
368                         break;
369                 }
370                 if( idx < 0 )   break;
371                 
372                 // Check if it is a free range
373                 for( i = 0; i < Pages; i++ )
374                 {
375                         // Used page? break
376                         if( gaPageBitmap[idx] & (1 << sidx) )
377                                 break;
378                         
379                         sidx --;
380                         if(sidx < 0) {  sidx = 31;      idx --; }
381                         if(idx < 0)     break;
382                 }
383                 
384                 if( i == Pages )
385                         break;
386         }
387         
388         // Check if an address was found
389         if( idx < 0 ) {
390                 Mutex_Release( &glPhysAlloc );
391                 Warning("MM_AllocPhysRange - OUT OF MEMORY (Called by %p)", __builtin_return_address(0));
392                 LEAVE('i', 0);
393                 return 0;
394         }
395         
396         // Mark pages used
397         for( i = 0; i < Pages; i++ )
398         {
399                 if( MM_GetPhysAddr( &gaPageReferences[idx*32+sidx] ) )
400                         gaPageReferences[idx*32+sidx] = 1;
401                 gaPageBitmap[ idx ] |= 1 << sidx;
402                 sidx ++;
403                 giPhysAlloc ++;
404                 if(sidx == 32) { sidx = 0;      idx ++; }
405         }
406         
407         // Get address
408         ret = (idx << 17) | (sidx << 12);
409         
410         // Mark used block
411         if(gaPageBitmap[ idx ] == -1)   gaSuperBitmap[idx/32] |= 1 << (idx%32);
412
413         // Release Spinlock
414         Mutex_Release( &glPhysAlloc );
415         
416         LEAVE('X', ret);
417         #if TRACE_ALLOCS
418         Log_Debug("PMem", "MM_AllocPhysRange: RETURN 0x%llx-0x%llx (%i free)",
419                 ret, ret + (1<<Pages)-1, giPageCount-giPhysAlloc);
420         #endif
421         return ret;
422 }
423
424 /**
425  * \fn void MM_RefPhys(tPAddr PAddr)
426  */
427 void MM_RefPhys(tPAddr PAddr)
428 {
429         // Get page number
430         PAddr >>= 12;
431
432         //if( PAddr == 0x15FA000/PAGE_SIZE )    Debug("%p refed %P", __builtin_return_address(0), PAddr*PAGE_SIZE);
433
434         // We don't care about non-ram pages
435         if(PAddr >= giPageCount)        return;
436         
437         // Lock Structures
438         Mutex_Acquire( &glPhysAlloc );
439         
440         // Reference the page
441         if( gaPageReferences )
442         {
443                 if( MM_GetPhysAddr( &gaPageReferences[PAddr] ) == 0 )
444                 {
445                         Uint base = PAddr & ~(1024-1);
446                         Mutex_Release( &glPhysAlloc );
447                         // No infinite recursion, AllocPhys doesn't need the reference array
448                         // TODO: Race condition? (racy on populating)
449                         if( MM_Allocate( &gaPageReferences[base] ) == 0 )
450                         {
451                                 Log_KernelPanic("PMem",
452                                         "MM_RefPhys: Out of physical memory allocating info for %X",
453                                         PAddr*PAGE_SIZE
454                                         );
455                                 for(;;);
456                         }
457                         Mutex_Acquire( &glPhysAlloc );
458                         // TODO: Solve race condition. (see below)
459                         // [1] See unallocated
460                         //     Release lock
461                         // [2] Acquire lock
462                         //     See unallocated
463                         //     Release lock
464                         //     Allocate
465                         // [1] Allocate
466                         //     Acquire lock
467                         //     Populate
468                         //     Release lock
469                         // [2] Acquire lock
470                         //     Populate (clobbering)
471                         
472                         // Fill references from allocated bitmap
473                         for( int i = 0; i < 1024; i ++ )
474                         {
475                                 gaPageReferences[base + i] = (gaPageBitmap[(base+i)/32] & (1 << (base+i)%32)) ? 1 : 0;
476                         }
477                 }
478                 gaPageReferences[ PAddr ] ++;
479         }
480
481         // If not already used
482         if( !(gaPageBitmap[ PAddr / 32 ] & 1 << (PAddr&31)) ) {
483                 giPhysAlloc ++;
484                 // Mark as used
485                 gaPageBitmap[ PAddr / 32 ] |= 1 << (PAddr&31);
486         }
487         
488         // Mark used block
489         if(gaPageBitmap[ PAddr / 32 ] == -1)
490                 gaSuperBitmap[PAddr/1024] |= 1 << ((PAddr/32)&31);
491         
492         // Release Spinlock
493         Mutex_Release( &glPhysAlloc );
494 }
495
496 /**
497  * \fn void MM_DerefPhys(tPAddr PAddr)
498  * \brief Dereferences a physical page
499  */
500 void MM_DerefPhys(tPAddr PAddr)
501 {
502         // Get page number
503         PAddr >>= 12;
504
505         //if( PAddr == 0x196000/PAGE_SIZE )     Debug("%p derefed %P", __builtin_return_address(0), PAddr*PAGE_SIZE);
506
507         // We don't care about non-ram pages
508         if(PAddr >= giPageCount)        return;
509         
510         // Check if it is freed
511         if( !(gaPageBitmap[PAddr / 32] & (1 << PAddr%32)) ) {
512                 Log_Warning("MMVirt", "MM_DerefPhys - Non-referenced memory (%P) dereferenced",
513                         PAddr * PAGE_SIZE);
514                 Proc_PrintBacktrace();
515                 return;
516         }
517         
518         // Lock Structures
519         Mutex_Acquire( &glPhysAlloc );
520         
521         if( giLastPossibleFree < PAddr )
522                 giLastPossibleFree = PAddr;
523
524         // Dereference
525         if( !MM_GetPhysAddr( &gaPageReferences[PAddr] ) || (-- gaPageReferences[PAddr]) == 0 )
526         {
527                 #if TRACE_ALLOCS
528                 Log_Debug("PMem", "MM_DerefPhys: Free'd %P (%i free)", PAddr<<12, giPageCount-giPhysAlloc);
529                 Proc_PrintBacktrace();
530                 #endif
531                 //LOG("Freed 0x%x by %p\n", PAddr<<12, __builtin_return_address(0));
532                 giPhysAlloc --;
533                 gaPageBitmap[ PAddr / 32 ] &= ~(1 << (PAddr&31));
534                 if(gaPageBitmap[ PAddr / 32 ] == 0)
535                         gaSuperBitmap[ PAddr >> 10 ] &= ~(1 << ((PAddr >> 5)&31));
536
537                 if( MM_GetPhysAddr( &gaPageNodes[PAddr] ) )
538                 {
539                         gaPageNodes[PAddr] = NULL;
540                         // TODO: Free Node Page when fully unused
541                 }
542         }
543
544         // Release spinlock
545         Mutex_Release( &glPhysAlloc );
546 }
547
548 /**
549  * \fn int MM_GetRefCount(tPAddr Addr)
550  */
551 int MM_GetRefCount(tPAddr PAddr)
552 {
553         // Get page number
554         PAddr >>= 12;
555
556         // We don't care about non-ram pages
557         if(PAddr >= giPageCount)        return -1;
558
559         if( MM_GetPhysAddr( &gaPageReferences[PAddr] ) == 0 )
560                 return (gaPageBitmap[PAddr / 32] & (1 << PAddr%32)) ? 1 : 0;
561         
562         // Check if it is freed
563         return gaPageReferences[ PAddr ];
564 }
565
566 int MM_SetPageNode(tPAddr PAddr, void *Node)
567 {
568         if( MM_GetRefCount(PAddr) == 0 )        return 1;
569          
570         PAddr /= PAGE_SIZE;
571
572         void *page_ptr = (void*)( (tVAddr)&gaPageNodes[PAddr] & ~(PAGE_SIZE-1) );
573         
574         if( !MM_GetPhysAddr( page_ptr ) )
575         {
576                 if( !MM_Allocate( page_ptr ) ) {
577                         Log_Warning("PMem", "Unable to allocate Node page");
578                         return -1;
579                 }
580                 memset( page_ptr, 0, PAGE_SIZE );
581         }
582
583         gaPageNodes[PAddr] = Node;
584 //      Log("gaPageNodes[0x%x] = %p", PAddr, Node);
585         return 0;
586 }
587
588 int MM_GetPageNode(tPAddr PAddr, void **Node)
589 {
590         if( MM_GetRefCount(PAddr) == 0 )        return 1;
591         
592         PAddr /= PAGE_SIZE;
593         if( !MM_GetPhysAddr( &gaPageNodes[PAddr] ) ) {
594                 *Node = NULL;
595                 return 0;
596         }
597         *Node = gaPageNodes[PAddr];
598         return 0;
599 }
600

UCC git Repository :: git.ucc.asn.au