grub-core/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/memory.h>
  21 #include <grub/machine/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 #include <grub/i18n.h>
  28
  29 GRUB_MOD_LICENSE ("GPLv3+");
  30
  31 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
  32
  33 struct grub_mmap_region *grub_mmap_overlays = 0;
  34 static int curhandle = 1;
  35
  36 #endif
  37
  38 grub_err_t
  39 grub_mmap_iterate (grub_memory_hook_t hook)
  40 {
  41
  42   /* This function resolves overlapping regions and sorts the memory map.
  43      It uses scanline (sweeping) algorithm.
  44   */
  45   /* If same page is used by multiple types it's resolved
  46      according to priority:
  47      1 - free memory
  48      2 - memory usable by firmware-aware code
  49      3 - unusable memory
  50      4 - a range deliberately empty
  51   */
  52   int priority[] =
  53     {
  54       [GRUB_MEMORY_AVAILABLE] = 1,
  55       [GRUB_MEMORY_RESERVED] = 3,
  56       [GRUB_MEMORY_ACPI] = 2,
  57       [GRUB_MEMORY_CODE] = 3,
  58       [GRUB_MEMORY_NVS] = 3,
  59       [GRUB_MEMORY_HOLE] = 4,
  60     };
  61
  62   int i, done;
  63
  64   /* Scanline events. */
  65   struct grub_mmap_scan
  66   {
  67     /* At which memory address. */
  68     grub_uint64_t pos;
  69     /* 0 = region starts, 1 = region ends. */
  70     int type;
  71     /* Which type of memory region? */
  72     int memtype;
  73   };
  74   struct grub_mmap_scan *scanline_events;
  75   struct grub_mmap_scan t;
  76
  77   /* Previous scanline event. */
  78   grub_uint64_t lastaddr;
  79   int lasttype;
  80   /* Current scanline event. */
  81   int curtype;
  82   /* How many regions of given type overlap at current location? */
  83   int present[ARRAY_SIZE (priority)];
  84   /* Number of mmap chunks. */
  85   int mmap_num;
  86
  87 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
  88   struct grub_mmap_region *cur;
  89 #endif
  90
  91   auto int NESTED_FUNC_ATTR count_hook (grub_uint64_t, grub_uint64_t,
  92                                         grub_uint32_t);
  93   int NESTED_FUNC_ATTR count_hook (grub_uint64_t addr __attribute__ ((unused)),
  94                                    grub_uint64_t size __attribute__ ((unused)),
  95                                    grub_memory_type_t type __attribute__ ((unused)))
  96   {
  97     mmap_num++;
  98     return 0;
  99   }
 100
 101   auto int NESTED_FUNC_ATTR fill_hook (grub_uint64_t, grub_uint64_t,
 102                                         grub_uint32_t);
 103   int NESTED_FUNC_ATTR fill_hook (grub_uint64_t addr,
 104                                   grub_uint64_t size,
 105                                   grub_memory_type_t type)
 106   {
 107     scanline_events[i].pos = addr;
 108     scanline_events[i].type = 0;
 109     if (type < ARRAY_SIZE (priority) && priority[type])
 110       scanline_events[i].memtype = type;
 111     else
 112       {
 113         grub_dprintf ("mmap", "Unknown memory type %d. Assuming unusable\n",
 114                       type);
 115         scanline_events[i].memtype = GRUB_MEMORY_RESERVED;
 116       }
 117     i++;
 118
 119     scanline_events[i].pos = addr + size;
 120     scanline_events[i].type = 1;
 121     scanline_events[i].memtype = scanline_events[i - 1].memtype;
 122     i++;
 123
 124     return 0;
 125   }
 126
 127   mmap_num = 0;
 128
 129 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 130   for (cur = grub_mmap_overlays; cur; cur = cur->next)
 131     mmap_num++;
 132 #endif
 133
 134   grub_machine_mmap_iterate (count_hook);
 135
 136   /* Initialize variables. */
 137   grub_memset (present, 0, sizeof (present));
 138   scanline_events = (struct grub_mmap_scan *)
 139     grub_malloc (sizeof (struct grub_mmap_scan) * 2 * mmap_num);
 140
 141   if (! scanline_events)
 142     {
 143       return grub_error (GRUB_ERR_OUT_OF_MEMORY,
 144                          "couldn't allocate space for new memory map");
 145     }
 146
 147   i = 0;
 148 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 149   /* Register scanline events. */
 150   for (cur = grub_mmap_overlays; cur; cur = cur->next)
 151     {
 152       scanline_events[i].pos = cur->start;
 153       scanline_events[i].type = 0;
 154       if (cur->type < ARRAY_SIZE (priority) && priority[cur->type])
 155         scanline_events[i].memtype = cur->type;
 156       else
 157         scanline_events[i].memtype = GRUB_MEMORY_RESERVED;
 158       i++;
 159
 160       scanline_events[i].pos = cur->end;
 161       scanline_events[i].type = 1;
 162       scanline_events[i].memtype = scanline_events[i - 1].memtype;
 163       i++;
 164     }
 165 #endif /* ! GRUB_MMAP_REGISTER_BY_FIRMWARE */
 166
 167   grub_machine_mmap_iterate (fill_hook);
 168
 169   /* Primitive bubble sort. It has complexity O(n^2) but since we're
 170      unlikely to have more than 100 chunks it's probably one of the
 171      fastest for one purpose. */
 172   done = 1;
 173   while (done)
 174     {
 175       done = 0;
 176       for (i = 0; i < 2 * mmap_num - 1; i++)
 177         if (scanline_events[i + 1].pos < scanline_events[i].pos
 178             || (scanline_events[i + 1].pos == scanline_events[i].pos
 179                 && scanline_events[i + 1].type == 0
 180                 && scanline_events[i].type == 1))
 181           {
 182             t = scanline_events[i + 1];
 183             scanline_events[i + 1] = scanline_events[i];
 184             scanline_events[i] = t;
 185             done = 1;
 186           }
 187     }
 188
 189   lastaddr = scanline_events[0].pos;
 190   lasttype = scanline_events[0].memtype;
 191   for (i = 0; i < 2 * mmap_num; i++)
 192     {
 193       unsigned k;
 194       /* Process event. */
 195       if (scanline_events[i].type)
 196         present[scanline_events[i].memtype]--;
 197       else
 198         present[scanline_events[i].memtype]++;
 199
 200       /* Determine current region type. */
 201       curtype = -1;
 202       for (k = 0; k < ARRAY_SIZE (priority); k++)
 203         if (present[k] && (curtype == -1 || priority[k] > priority[curtype]))
 204           curtype = k;
 205
 206       /* Announce region to the hook if necessary. */
 207       if ((curtype == -1 || curtype != lasttype)
 208           && lastaddr != scanline_events[i].pos
 209           && lasttype != -1
 210           && lasttype != GRUB_MEMORY_HOLE
 211           && hook (lastaddr, scanline_events[i].pos - lastaddr, lasttype))
 212         {
 213           grub_free (scanline_events);
 214           return GRUB_ERR_NONE;
 215         }
 216
 217       /* Update last values if necessary. */
 218       if (curtype == -1 || curtype != lasttype)
 219         {
 220           lasttype = curtype;
 221           lastaddr = scanline_events[i].pos;
 222         }
 223     }
 224
 225   grub_free (scanline_events);
 226   return GRUB_ERR_NONE;
 227 }
 228
 229 #ifndef GRUB_MMAP_REGISTER_BY_FIRMWARE
 230 int
 231 grub_mmap_register (grub_uint64_t start, grub_uint64_t size, int type)
 232 {
 233   struct grub_mmap_region *cur;
 234
 235   grub_dprintf ("mmap", "registering\n");
 236
 237   cur = (struct grub_mmap_region *)
 238     grub_malloc (sizeof (struct grub_mmap_region));
 239   if (! cur)
 240     {
 241       grub_error (GRUB_ERR_OUT_OF_MEMORY,
 242                   "couldn't allocate memory map overlay");
 243       return 0;
 244     }
 245
 246   cur->next = grub_mmap_overlays;
 247   cur->start = start;
 248   cur->end = start + size;
 249   cur->type = type;
 250   cur->handle = curhandle++;
 251   grub_mmap_overlays = cur;
 252
 253   if (grub_machine_mmap_register (start, size, type, curhandle))
 254     {
 255       grub_mmap_overlays = cur->next;
 256       grub_free (cur);
 257       return 0;
 258     }
 259
 260   return cur->handle;
 261 }
 262
 263 grub_err_t
 264 grub_mmap_unregister (int handle)
 265 {
 266   struct grub_mmap_region *cur, *prev;
 267
 268   for (cur = grub_mmap_overlays, prev = 0; cur; prev= cur, cur = cur->next)
 269     if (handle == cur->handle)
 270       {
 271         grub_err_t err;
 272         if ((err = grub_machine_mmap_unregister (handle)))
 273           return err;
 274
 275         if (prev)
 276           prev->next = cur->next;
 277         else
 278           grub_mmap_overlays = cur->next;
 279         grub_free (cur);
 280         return GRUB_ERR_NONE;
 281       }
 282   return grub_error (GRUB_ERR_BAD_ARGUMENT, "mmap overlay not found");
 283 }
 284
 285 #endif /* ! GRUB_MMAP_REGISTER_BY_FIRMWARE */
 286
 287 #define CHUNK_SIZE      0x400
 288
 289 static inline grub_uint64_t
 290 fill_mask (grub_uint64_t addr, grub_uint64_t mask, grub_uint64_t iterator)
 291 {
 292   int i, j;
 293   grub_uint64_t ret = (addr & mask);
 294
 295   /* Find first fixed bit. */
 296   for (i = 0; i < 64; i++)
 297     if ((mask & (1ULL << i)) != 0)
 298       break;
 299   j = 0;
 300   for (; i < 64; i++)
 301     if ((mask & (1ULL << i)) == 0)
 302       {
 303         if ((iterator & (1ULL << j)) != 0)
 304           ret |= 1ULL << i;
 305         j++;
 306       }
 307   return ret;
 308 }
 309
 310 static grub_err_t
 311 grub_cmd_badram (grub_command_t cmd __attribute__ ((unused)),
 312                  int argc, char **args)
 313 {
 314   char * str;
 315   grub_uint64_t badaddr, badmask;
 316
 317   auto int NESTED_FUNC_ATTR hook (grub_uint64_t, grub_uint64_t,
 318                                  grub_memory_type_t);
 319   int NESTED_FUNC_ATTR hook (grub_uint64_t addr,
 320                              grub_uint64_t size,
 321                              grub_memory_type_t type __attribute__ ((unused)))
 322   {
 323     grub_uint64_t iterator, low, high, cur;
 324     int tail, var;
 325     int i;
 326     grub_dprintf ("badram", "hook %llx+%llx\n", (unsigned long long) addr,
 327                   (unsigned long long) size);
 328
 329     /* How many trailing zeros? */
 330     for (tail = 0; ! (badmask & (1ULL << tail)); tail++);
 331
 332     /* How many zeros in mask? */
 333     var = 0;
 334     for (i = 0; i < 64; i++)
 335       if (! (badmask & (1ULL << i)))
 336         var++;
 337
 338     if (fill_mask (badaddr, badmask, 0) >= addr)
 339       iterator = 0;
 340     else
 341       {
 342         low = 0;
 343         high = ~0ULL;
 344         /* Find starting value. Keep low and high such that
 345            fill_mask (low) < addr and fill_mask (high) >= addr;
 346         */
 347         while (high - low > 1)
 348           {
 349             cur = (low + high) / 2;
 350             if (fill_mask (badaddr, badmask, cur) >= addr)
 351               high = cur;
 352             else
 353               low = cur;
 354           }
 355         iterator = high;
 356       }
 357
 358     for (; iterator < (1ULL << (var - tail))
 359            && (cur = fill_mask (badaddr, badmask, iterator)) < addr + size;
 360          iterator++)
 361       {
 362         grub_dprintf ("badram", "%llx (size %llx) is a badram range\n",
 363                       (unsigned long long) cur, (1ULL << tail));
 364         grub_mmap_register (cur, (1ULL << tail), GRUB_MEMORY_HOLE);
 365       }
 366     return 0;
 367   }
 368
 369   if (argc != 1)
 370     return grub_error (GRUB_ERR_BAD_ARGUMENT, "badram string required");
 371
 372   grub_dprintf ("badram", "executing badram\n");
 373
 374   str = args[0];
 375
 376   while (1)
 377     {
 378       /* Parse address and mask.  */
 379       badaddr = grub_strtoull (str, &str, 16);
 380       if (*str == ',')
 381         str++;
 382       badmask = grub_strtoull (str, &str, 16);
 383       if (*str == ',')
 384         str++;
 385
 386       if (grub_errno == GRUB_ERR_BAD_NUMBER)
 387         {
 388           grub_errno = 0;
 389           return GRUB_ERR_NONE;
 390         }
 391
 392       /* When part of a page is tainted, we discard the whole of it.  There's
 393          no point in providing sub-page chunks.  */
 394       badmask &= ~(CHUNK_SIZE - 1);
 395
 396       grub_dprintf ("badram", "badram %llx:%llx\n",
 397                     (unsigned long long) badaddr, (unsigned long long) badmask);
 398
 399       grub_mmap_iterate (hook);
 400     }
 401 }
 402
 403 static grub_uint64_t
 404 parsemem (const char *str)
 405 {
 406   grub_uint64_t ret;
 407   char *ptr;
 408
 409   ret = grub_strtoul (str, &ptr, 0);
 410
 411   switch (*ptr)
 412     {
 413     case 'K':
 414       return ret << 10;
 415     case 'M':
 416       return ret << 20;
 417     case 'G':
 418       return ret << 30;
 419     case 'T':
 420       return ret << 40;
 421     }
 422   return ret;
 423 }
 424
 425 static grub_err_t
 426 grub_cmd_cutmem (grub_command_t cmd __attribute__ ((unused)),
 427                  int argc, char **args)
 428 {
 429   grub_uint64_t from, to;
 430
 431   auto int NESTED_FUNC_ATTR hook (grub_uint64_t, grub_uint64_t,
 432                                  grub_memory_type_t);
 433   int NESTED_FUNC_ATTR hook (grub_uint64_t addr,
 434                              grub_uint64_t size,
 435                              grub_memory_type_t type __attribute__ ((unused)))
 436   {
 437     grub_uint64_t end = addr + size;
 438
 439     if (addr <= from)
 440       addr = from;
 441     if (end >= to)
 442       end = to;
 443
 444     if (end <= addr)
 445       return 0;
 446
 447     grub_mmap_register (addr, end - addr, GRUB_MEMORY_HOLE);
 448     return 0;
 449   }
 450
 451   if (argc != 2)
 452     return grub_error (GRUB_ERR_BAD_ARGUMENT, "argements required");
 453
 454   from = parsemem (args[0]);
 455   if (grub_errno)
 456     return grub_errno;
 457
 458   to = parsemem (args[1]);
 459   if (grub_errno)
 460     return grub_errno;
 461
 462   grub_mmap_iterate (hook);
 463
 464   return GRUB_ERR_NONE;
 465 }
 466
 467 static grub_command_t cmd, cmd_cut;
 468
 469 \f
 470 GRUB_MOD_INIT(mmap)
 471 {
 472   cmd = grub_register_command ("badram", grub_cmd_badram,
 473                                N_("ADDR1,MASK1[,ADDR2,MASK2[,...]]"),
 474                                N_("Declare memory regions as badram."));
 475   cmd_cut = grub_register_command ("cutmem", grub_cmd_cutmem,
 476                                    N_("FROM[K|M|G] TO[K|M|G]"),
 477                                    N_("Remove any memory regions in specified range."));
 478
 479 }
 480
 481 GRUB_MOD_FINI(mmap)
 482 {
 483   grub_unregister_command (cmd);
 484   grub_unregister_command (cmd_cut);
 485 }
 486