KernelLand/Kernel/pmemmap.c

   1 /*
   2  * Acess2 Kernel
   3  * - By John Hodge (thePowersGang)
   4  *
   5  * pmemmap.c
   6  * - Physical memory map manipulation
   7  */
   8 #define DEBUG   0
   9 #include <acess.h>
  10 #include <pmemmap.h>
  11
  12 // === CODE ===
  13 void PMemMap_DumpBlocks(tPMemMapEnt *map, int NEnts)
  14 {
  15         for( int i = 0; i < NEnts; i ++ )
  16         {
  17                 Log_Debug("PMemMap", "%i: %i 0x%02x %08llx+%llx",
  18                         i, map[i].Type, map[i].NUMADomain,
  19                         map[i].Start, map[i].Length
  20                         );
  21         }
  22 }
  23
  24 int PMemMap_SplitBlock(tPMemMapEnt *map, int NEnts, int MaxEnts, int Block, Uint64 Offset)
  25 {
  26         LOG("Splitting %i (%llx+%llx) at %llx", Block, map[Block].Start, map[Block].Length, Offset);
  27
  28         Uint64 _len = map[Block].Length;
  29         map[Block].Length = Offset;
  30         if( NEnts == MaxEnts ) {
  31                 // out of space
  32                 return NEnts;
  33         }
  34         if( Block < NEnts ) {
  35                 LOG("Moving %i entries from %i to %i", (NEnts - Block-1), Block+1, Block);
  36                 memmove(&map[Block+2], &map[Block+1], (NEnts - Block)*sizeof(map[0]));
  37         }
  38         Block ++;
  39         NEnts ++;
  40
  41         // New (free) block
  42         map[Block].Start  = map[Block-1].Start + Offset;
  43         map[Block].Length = _len - Offset;
  44         map[Block].Type = map[Block-1].Type;
  45         map[Block].NUMADomain = map[Block-1].NUMADomain;
  46         LOG("- New %i %02x %llx+%llx", map[Block].Type, map[Block].NUMADomain, map[Block].Start, map[Block].Length);
  47
  48         return NEnts;
  49 }
  50
  51 int PMemMap_CompactMap(tPMemMapEnt *map, int NEnts, int MaxEnts)
  52 {
  53         for( int i = 1; i < NEnts; i ++ )
  54         {
  55                 // Check if the ranges are contiguous
  56                 if( map[i-1].Start + map[i-1].Length < map[i].Start )
  57                         continue ;
  58                 // Check if the type is the same
  59                 if( map[i-1].Type != map[i].Type )
  60                         continue ;
  61                 // Check if the NUMA Domains are the same
  62                 if( map[i-1].NUMADomain != map[i].NUMADomain )
  63                         continue ;
  64
  65                 // Ok, they should be together
  66                 map[i-1].Length += map[i].Length;
  67                 memmove(&map[i], &map[i+1], (NEnts - (i+1))*sizeof(map[0]));
  68                 LOG("Joined %i and %i into %llx+%llx", i-1, i, map[i-1].Start, map[i-1].Length);
  69
  70                 // Counteract the i++ in the loop iterator
  71                 i --;
  72                 NEnts --;
  73         }
  74         return NEnts;
  75 }
  76
  77 int PMemMap_ValidateMap(tPMemMapEnt *map, int NEnts, int MaxEnts)
  78 {
  79         // Sort the pmem map
  80          int     bNeedsSort = 0;
  81         for( int i = 1; i < NEnts; i ++ )
  82         {
  83                 if( map[i-1].Start > map[i].Start ) {
  84                         bNeedsSort = 1;
  85                         break;
  86                 }
  87         }
  88         if( bNeedsSort )
  89         {
  90                 // Use a selection/swap sort
  91                 for( int i = 0; i < NEnts; i ++ )
  92                 {
  93                         int sel = i;
  94                         for( int j = i+1; j < NEnts; j ++ )
  95                         {
  96                                 if( map[j].Start < map[sel].Start )
  97                                         sel = j;
  98                         }
  99                         if( sel != i ) {
 100                                 LOG("Swapping %i and %i", i, sel);
 101                                 LOG(" - %llx+%llx", map[i].Start, map[i].Length);
 102                                 LOG(" - %llx+%llx", map[sel].Start, map[sel].Length);
 103                                 tPMemMapEnt tmp = map[i];
 104                                 map[i] = map[sel];
 105                                 map[sel] = tmp;
 106                         }
 107                 }
 108         }
 109
 110         // Ensure that the map has no overlaps
 111         for( int i = 1; i < NEnts; i ++ )
 112         {
 113                 if( map[i-1].Start + map[i-1].Length <= map[i].Start )
 114                         continue ;
 115                 // Oops, overlap!
 116                 Log_Notice("Arch", "Map ranges %llx+%llx and %llx+%llx overlap",
 117                         map[i-1].Start, map[i-1].Length,
 118                         map[i].Start,   map[i].Length
 119                         );
 120         }
 121
 122         NEnts = PMemMap_CompactMap(map, NEnts, MaxEnts);
 123         return NEnts;
 124 }
 125
 126
 127 int PMemMap_MarkRangeUsed(tPMemMapEnt *map, int NEnts, int MaxEnts, Uint64 Base, Uint64 Size)
 128 {
 129          int    first;
 130
 131         Size = (Size + 0xFFF) & ~0xFFF;
 132         Base = Base & ~0xFFF;
 133
 134         first = -1;
 135         for( int i = 0; i < NEnts; i ++ )
 136         {
 137                 if( map[i].Start + map[i].Length > Base ) {
 138                         first = i;
 139                         break;
 140                 }
 141         }
 142         if( first == -1 ) {
 143                 // Not in map
 144                 LOG("%llx+%llx not in map (past end)", Base, Size);
 145                 return NEnts;
 146         }
 147
 148         if( map[first].Start > Base ) {
 149                 // Not in map
 150                 LOG("%llx+%llx not in map (in hole)", Base, Size);
 151                 return NEnts;
 152         }
 153
 154         // Detect single
 155         if( map[first].Start <= Base && Base + Size <= map[first].Start + map[first].Length )
 156         {
 157                 // Split before
 158                 if( map[first].Start < Base )
 159                 {
 160                         if( NEnts == MaxEnts ) {
 161                                 // out of space... oops
 162                                 return NEnts;
 163                         }
 164                         NEnts = PMemMap_SplitBlock(map, NEnts, MaxEnts, first, Base - map[first].Start);
 165                         first ++;
 166                 }
 167
 168                 // map[first].Start == Base
 169                 // Split after
 170                 if( map[first].Length > Size )
 171                 {
 172                         if( NEnts == MaxEnts ) {
 173                                 // out of space
 174                                 return NEnts;
 175                         }
 176                         NEnts = PMemMap_SplitBlock(map, NEnts, MaxEnts, first, Size);
 177                 }
 178
 179                 // map[first] is now exactly the block
 180                 map[first].Type = PMEMTYPE_USED;
 181
 182                 return PMemMap_CompactMap(map, NEnts, MaxEnts);
 183         }
 184         else
 185         {
 186                 // Wait... this should never happen, right?
 187                 Log_Notice("Arch", "Module %llx+%llx overlaps two or more ranges",
 188                         Base, Size);
 189                 PMemMap_DumpBlocks(map, NEnts);
 190                 // TODO: Error?
 191                 return NEnts;
 192         }
 193 }
 194
 195
 196