memdisk/e820func.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 2001-2008 H. Peter Anvin - All Rights Reserved
   4  *
   5  *   This program is free software; you can redistribute it and/or modify
   6  *   it under the terms of the GNU General Public License as published by
   7  *   the Free Software Foundation, Inc., 53 Temple Place Ste 330,
   8  *   Boston MA 02111-1307, USA; either version 2 of the License, or
   9  *   (at your option) any later version; incorporated herein by reference.
  10  *
  11  * ----------------------------------------------------------------------- */
  12
  13 /*
  14  * e820func.c
  15  *
  16  * E820 range database manager
  17  */
  18
  19 #include <stdint.h>
  20 #ifdef TEST
  21 #include <string.h>
  22 #else
  23 #include "memdisk.h"            /* For memset() */
  24 #endif
  25 #include "e820.h"
  26
  27 #define MAXRANGES       1024
  28 /* All of memory starts out as one range of "indeterminate" type */
  29 struct e820range ranges[MAXRANGES];
  30 int nranges;
  31
  32 void e820map_init(void)
  33 {
  34     memset(ranges, 0, sizeof(ranges));
  35     nranges = 1;
  36     ranges[1].type = -1U;
  37 }
  38
  39 static void insertrange_at(int where, uint64_t start, uint32_t type)
  40 {
  41     int i;
  42
  43     for (i = nranges; i > where; i--)
  44         ranges[i] = ranges[i - 1];
  45
  46     ranges[where].start = start;
  47     ranges[where].type = type;
  48
  49     nranges++;
  50     ranges[nranges].start = 0ULL;
  51     ranges[nranges].type = -1U;
  52 }
  53
  54 void insertrange(uint64_t start, uint64_t len, uint32_t type)
  55 {
  56     uint64_t last;
  57     uint32_t oldtype;
  58     int i, j;
  59
  60     /* Remove this to make len == 0 mean all of memory */
  61     if (len == 0)
  62         return;                 /* Nothing to insert */
  63
  64     last = start + len - 1;     /* May roll over */
  65
  66     i = 0;
  67     oldtype = -2U;
  68     while (start > ranges[i].start && ranges[i].type != -1U) {
  69         oldtype = ranges[i].type;
  70         i++;
  71     }
  72
  73     /* Consider the replacement policy.  This current one is "overwrite." */
  74
  75     if (start < ranges[i].start || ranges[i].type == -1U)
  76         insertrange_at(i++, start, type);
  77
  78     while (i == 0 || last > ranges[i].start - 1) {
  79         oldtype = ranges[i].type;
  80         ranges[i].type = type;
  81         i++;
  82     }
  83
  84     if (last < ranges[i].start - 1)
  85         insertrange_at(i, last + 1, oldtype);
  86
  87     /* Now the map is correct, but quite possibly not optimal.  Scan the
  88        map for ranges which are redundant and remove them. */
  89     i = j = 1;
  90     oldtype = ranges[0].type;
  91     while (i < nranges) {
  92         if (ranges[i].type == oldtype) {
  93             i++;
  94         } else {
  95             oldtype = ranges[i].type;
  96             if (i != j)
  97                 ranges[j] = ranges[i];
  98             i++;
  99             j++;
 100         }
 101     }
 102
 103     if (i != j) {
 104         ranges[j] = ranges[i];  /* Termination sentinel copy */
 105         nranges -= (i - j);
 106     }
 107 }