mmap/mmap.c

   1 /* Mmap management. */
   2 /*
   3  *  GRUB  --  GRand Unified Bootloader
   4  *  Copyright (C) 2009  Free Software Foundation, Inc.
   5  *
   6  *  GRUB is free software: you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation, either version 3 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  GRUB is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 #include <grub/machine/memory.h>
  21 #include <grub/memory.h>
  22 #include <grub/err.h>
  23 #include <grub/misc.h>
  24 #include <grub/mm.h>
  25 #include <grub/command.h>
  26 #include <grub/dl.h>
  27
  28 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
  29
  30 struct grub_mmap_region *grub_mmap_overlays = 0;
  31 static int curhandle = 1;
  32
  33 #endif
  34
  35 grub_err_t
  36 grub_mmap_iterate (int NESTED_FUNC_ATTR (*hook) (grub_uint64_t,
  37                                                  grub_uint64_t, grub_uint32_t))
  38 {
  39
  40   /* This function resolves overlapping regions and sorts the memory map.
  41      It uses scanline (sweeping) algorithm.
  42   */
  43   /* If same page is used by multiple types it's resolved
  44      according to priority:
  45      1 - free memory
  46      2 - memory usable by firmware-aware code
  47      3 - unusable memory
  48      4 - a range deliberately empty
  49   */
  50   int priority[GRUB_MACHINE_MEMORY_MAX_TYPE + 2] =
  51     {
  52 #ifdef GRUB_MACHINE_MEMORY_AVAILABLE
  53       [GRUB_MACHINE_MEMORY_AVAILABLE] = 1,
  54 #endif
  55 #ifdef GRUB_MACHINE_MEMORY_RESERVED
  56       [GRUB_MACHINE_MEMORY_RESERVED] = 3,
  57 #endif
  58 #ifdef GRUB_MACHINE_MEMORY_ACPI
  59       [GRUB_MACHINE_MEMORY_ACPI] = 2,
  60 #endif
  61 #ifdef GRUB_MACHINE_MEMORY_CODE
  62       [GRUB_MACHINE_MEMORY_CODE] = 3,
  63 #endif
  64 #ifdef GRUB_MACHINE_MEMORY_NVS
  65       [GRUB_MACHINE_MEMORY_NVS] = 3,
  66 #endif
  67       [GRUB_MACHINE_MEMORY_HOLE] = 4,
  68     };
  69
  70   int i, k, done;
  71
  72   /* Scanline events. */
  73   struct grub_mmap_scan
  74   {
  75     /* At which memory address. */
  76     grub_uint64_t pos;
  77     /* 0 = region starts, 1 = region ends. */
  78     int type;
  79     /* Which type of memory region? */
  80     int memtype;
  81   };
  82   struct grub_mmap_scan *scanline_events;
  83   struct grub_mmap_scan t;
  84
  85   /* Previous scanline event. */
  86   grub_uint64_t lastaddr;
  87   int lasttype;
  88   /* Current scanline event. */
  89   int curtype;
  90   /* How many regions of given type overlap at current location? */
  91   int present[GRUB_MACHINE_MEMORY_MAX_TYPE + 2];
  92   /* Number of mmap chunks. */
  93   int mmap_num;
  94
  95 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
  96   struct grub_mmap_region *cur;
  97 #endif
  98
  99   auto int NESTED_FUNC_ATTR count_hook (grub_uint64_t, grub_uint64_t,
 100                                         grub_uint32_t);
 101   int NESTED_FUNC_ATTR count_hook (grub_uint64_t addr __attribute__ ((unused)),
 102                                    grub_uint64_t size __attribute__ ((unused)),
 103                                    grub_uint32_t type __attribute__ ((unused)))
 104   {
 105     mmap_num++;
 106     return 0;
 107   }
 108
 109   auto int NESTED_FUNC_ATTR fill_hook (grub_uint64_t, grub_uint64_t,
 110                                         grub_uint32_t);
 111   int NESTED_FUNC_ATTR fill_hook (grub_uint64_t addr,
 112                                   grub_uint64_t size,
 113                                   grub_uint32_t type)
 114   {
 115     scanline_events[i].pos = addr;
 116     scanline_events[i].type = 0;
 117     if (type <= GRUB_MACHINE_MEMORY_MAX_TYPE && priority[type])
 118       scanline_events[i].memtype = type;
 119     else
 120       {
 121         grub_dprintf ("mmap", "Unknown memory type %d. Assuming unusable\n",
 122                       type);
 123         scanline_events[i].memtype = GRUB_MACHINE_MEMORY_RESERVED;
 124       }
 125     i++;
 126
 127     scanline_events[i].pos = addr + size;
 128     scanline_events[i].type = 1;
 129     scanline_events[i].memtype = scanline_events[i - 1].memtype;
 130     i++;
 131
 132     return 0;
 133   }
 134
 135   mmap_num = 0;
 136
 137 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 138   for (cur = grub_mmap_overlays; cur; cur = cur->next)
 139     mmap_num++;
 140 #endif
 141
 142   grub_machine_mmap_iterate (count_hook);
 143
 144   /* Initialize variables. */
 145   grub_memset (present, 0, sizeof (present));
 146   scanline_events = (struct grub_mmap_scan *)
 147     grub_malloc (sizeof (struct grub_mmap_scan) * 2 * mmap_num);
 148
 149   if (! scanline_events)
 150     {
 151       return grub_error (GRUB_ERR_OUT_OF_MEMORY,
 152                          "couldn't allocate space for new memory map");
 153     }
 154
 155   i = 0;
 156 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 157   /* Register scanline events. */
 158   for (cur = grub_mmap_overlays; cur; cur = cur->next)
 159     {
 160       scanline_events[i].pos = cur->start;
 161       scanline_events[i].type = 0;
 162       if (cur->type == GRUB_MACHINE_MEMORY_HOLE
 163           || (cur->type >= 0 && cur->type <= GRUB_MACHINE_MEMORY_MAX_TYPE
 164               && priority[cur->type]))
 165         scanline_events[i].memtype = cur->type;
 166       else
 167         scanline_events[i].memtype = GRUB_MACHINE_MEMORY_RESERVED;
 168       i++;
 169
 170       scanline_events[i].pos = cur->end;
 171       scanline_events[i].type = 1;
 172       scanline_events[i].memtype = scanline_events[i - 1].memtype;
 173       i++;
 174     }
 175 #endif /* ! GRUB_MMAP_REGISTER_BY_FIRMWARE */
 176
 177   grub_machine_mmap_iterate (fill_hook);
 178
 179   /* Primitive bubble sort. It has complexity O(n^2) but since we're
 180      unlikely to have more than 100 chunks it's probably one of the
 181      fastest for one purpose. */
 182   done = 1;
 183   while (done)
 184     {
 185       done = 0;
 186       for (i = 0; i < 2 * mmap_num - 1; i++)
 187         if (scanline_events[i + 1].pos < scanline_events[i].pos
 188             || (scanline_events[i + 1].pos == scanline_events[i].pos
 189                 && scanline_events[i + 1].type == 0
 190                 && scanline_events[i].type == 1))
 191           {
 192             t = scanline_events[i + 1];
 193             scanline_events[i + 1] = scanline_events[i];
 194             scanline_events[i] = t;
 195             done = 1;
 196           }
 197     }
 198
 199   lastaddr = scanline_events[0].pos;
 200   lasttype = scanline_events[0].memtype;
 201   for (i = 0; i < 2 * mmap_num; i++)
 202     {
 203       /* Process event. */
 204       if (scanline_events[i].type)
 205         present[scanline_events[i].memtype]--;
 206       else
 207         present[scanline_events[i].memtype]++;
 208
 209       /* Determine current region type. */
 210       curtype = -1;
 211       for (k = 0; k <= GRUB_MACHINE_MEMORY_MAX_TYPE + 1; k++)
 212         if (present[k] && (curtype == -1 || priority[k] > priority[curtype]))
 213           curtype = k;
 214
 215       /* Announce region to the hook if necessary. */
 216       if ((curtype == -1 || curtype != lasttype)
 217           && lastaddr != scanline_events[i].pos
 218           && lasttype != -1
 219           && lasttype != GRUB_MACHINE_MEMORY_HOLE
 220           && hook (lastaddr, scanline_events[i].pos - lastaddr, lasttype))
 221         {
 222           grub_free (scanline_events);
 223           return GRUB_ERR_NONE;
 224         }
 225
 226       /* Update last values if necessary. */
 227       if (curtype == -1 || curtype != lasttype)
 228         {
 229           lasttype = curtype;
 230           lastaddr = scanline_events[i].pos;
 231         }
 232     }
 233
 234   grub_free (scanline_events);
 235   return GRUB_ERR_NONE;
 236 }
 237
 238 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 239 int
 240 grub_mmap_register (grub_uint64_t start, grub_uint64_t size, int type)
 241 {
 242   struct grub_mmap_region *cur;
 243
 244   grub_dprintf ("mmap", "registering\n");
 245
 246   cur = (struct grub_mmap_region *)
 247     grub_malloc (sizeof (struct grub_mmap_region));
 248   if (! cur)
 249     {
 250       grub_error (GRUB_ERR_OUT_OF_MEMORY,
 251                   "couldn't allocate memory map overlay");
 252       return 0;
 253     }
 254
 255   cur->next = grub_mmap_overlays;
 256   cur->start = start;
 257   cur->end = start + size;
 258   cur->type = type;
 259   cur->handle = curhandle++;
 260   grub_mmap_overlays = cur;
 261
 262   if (grub_machine_mmap_register (start, size, type, curhandle))
 263     {
 264       grub_mmap_overlays = cur->next;
 265       grub_free (cur);
 266       return 0;
 267     }
 268
 269   return cur->handle;
 270 }
 271
 272 grub_err_t
 273 grub_mmap_unregister (int handle)
 274 {
 275   struct grub_mmap_region *cur, *prev;
 276
 277   for (cur = grub_mmap_overlays, prev = 0; cur; prev= cur, cur = cur->next)
 278     if (handle == cur->handle)
 279       {
 280         grub_err_t err;
 281         if ((err = grub_machine_mmap_unregister (handle)))
 282           return err;
 283
 284         if (prev)
 285           prev->next = cur->next;
 286         else
 287           grub_mmap_overlays = cur->next;
 288         grub_free (cur);
 289         return GRUB_ERR_NONE;
 290       }
 291   return grub_error (GRUB_ERR_BAD_ARGUMENT, "mmap overlay not found");
 292 }
 293
 294 #endif /* ! GRUB_MMAP_REGISTER_BY_FIRMWARE */
 295
 296 #define CHUNK_SIZE      0x400
 297
 298 static inline grub_uint64_t
 299 fill_mask (grub_uint64_t addr, grub_uint64_t mask, grub_uint64_t iterator)
 300 {
 301   int i, j;
 302   grub_uint64_t ret = (addr & mask);
 303
 304   /* Find first fixed bit. */
 305   for (i = 0; i < 64; i++)
 306     if ((mask & (1ULL << i)) != 0)
 307       break;
 308   j = 0;
 309   for (; i < 64; i++)
 310     if ((mask & (1ULL << i)) == 0)
 311       {
 312         if ((iterator & (1ULL << j)) != 0)
 313           ret |= 1ULL << i;
 314         j++;
 315       }
 316   return ret;
 317 }
 318
 319 static grub_err_t
 320 grub_cmd_badram (grub_command_t cmd __attribute__ ((unused)),
 321                  int argc, char **args)
 322 {
 323   char * str;
 324   grub_uint64_t badaddr, badmask;
 325
 326   auto int NESTED_FUNC_ATTR hook (grub_uint64_t, grub_uint64_t, grub_uint32_t);
 327   int NESTED_FUNC_ATTR hook (grub_uint64_t addr,
 328                              grub_uint64_t size,
 329                              grub_uint32_t type __attribute__ ((unused)))
 330   {
 331     grub_uint64_t iterator, low, high, cur;
 332     int tail, var;
 333     int i;
 334     grub_dprintf ("badram", "hook %llx+%llx\n", (unsigned long long) addr,
 335                   (unsigned long long) size);
 336
 337     /* How many trailing zeros? */
 338     for (tail = 0; ! (badmask & (1ULL << tail)); tail++);
 339
 340     /* How many zeros in mask? */
 341     var = 0;
 342     for (i = 0; i < 64; i++)
 343       if (! (badmask & (1ULL << i)))
 344         var++;
 345
 346     if (fill_mask (badaddr, badmask, 0) >= addr)
 347       iterator = 0;
 348     else
 349       {
 350         low = 0;
 351         high = ~0ULL;
 352         /* Find starting value. Keep low and high such that
 353            fill_mask (low) < addr and fill_mask (high) >= addr;
 354         */
 355         while (high - low > 1)
 356           {
 357             cur = (low + high) / 2;
 358             if (fill_mask (badaddr, badmask, cur) >= addr)
 359               high = cur;
 360             else
 361               low = cur;
 362           }
 363         iterator = high;
 364       }
 365
 366     for (; iterator < (1ULL << (var - tail))
 367            && (cur = fill_mask (badaddr, badmask, iterator)) < addr + size;
 368          iterator++)
 369       {
 370         grub_dprintf ("badram", "%llx (size %llx) is a badram range\n",
 371                       (long long) cur, (long long) (1ULL << tail) - 1);
 372         grub_mmap_register (cur, (1ULL << tail) - 1, GRUB_MACHINE_MEMORY_HOLE);
 373       }
 374     return 0;
 375   }
 376
 377   if (argc != 1)
 378     return grub_error (GRUB_ERR_BAD_ARGUMENT, "badram string required");
 379
 380   grub_dprintf ("badram", "executing badram\n");
 381
 382   str = args[0];
 383
 384   while (1)
 385     {
 386       /* Parse address and mask.  */
 387       badaddr = grub_strtoull (str, &str, 16);
 388       if (*str == ',')
 389         str++;
 390       badmask = grub_strtoull (str, &str, 16);
 391       if (*str == ',')
 392         str++;
 393
 394       if (grub_errno == GRUB_ERR_BAD_NUMBER)
 395         {
 396           grub_errno = 0;
 397           return GRUB_ERR_NONE;
 398         }
 399
 400       /* When part of a page is tainted, we discard the whole of it.  There's
 401          no point in providing sub-page chunks.  */
 402       badmask &= ~(CHUNK_SIZE - 1);
 403
 404       grub_dprintf ("badram", "badram %llx:%llx\n",
 405                     (unsigned long long) badaddr, (unsigned long long) badmask);
 406
 407       grub_mmap_iterate (hook);
 408     }
 409 }
 410
 411 static grub_command_t cmd;
 412
 413 \f
 414 GRUB_MOD_INIT(mmap)
 415 {
 416   cmd = grub_register_command ("badram", grub_cmd_badram,
 417                                "badram ADDR1,MASK1[,ADDR2,MASK2[,...]]",
 418                                "declare memory regions as badram");
 419 }
 420
 421 GRUB_MOD_FINI(mmap)
 422 {
 423   grub_unregister_command (cmd);
 424 }
 425