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