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 #include "memdisk.h"            /* For memset() */
  21 #include "e820.h"
  22
  23 #define MAXRANGES       1024
  24 /* All of memory starts out as one range of "indeterminate" type */
  25 struct e820range ranges[MAXRANGES];
  26 int nranges;
  27
  28
  29 void e820map_init(void)
  30 {
  31   memset(ranges, 0, sizeof(ranges));
  32   nranges = 1;
  33   ranges[1].type = -1;
  34 }
  35
  36 static void insertrange_at(int where, uint64_t start, uint32_t type)
  37 {
  38   int i;
  39
  40   for ( i = nranges ; i > where ; i-- )
  41     ranges[i] = ranges[i-1];
  42
  43   ranges[where].start = start;
  44   ranges[where].type  = type;
  45
  46   nranges++;
  47   ranges[nranges].start = 0ULL;
  48   ranges[nranges].type  = (uint32_t)-1;
  49 }
  50
  51 void insertrange(uint64_t start, uint64_t len, uint32_t type)
  52 {
  53   uint64_t last;
  54   uint32_t oldtype;
  55   int i, j;
  56
  57   /* Remove this to make len == 0 mean all of memory */
  58   if ( len == 0 )
  59     return;                     /* Nothing to insert */
  60
  61   last = start+len-1;           /* May roll over */
  62
  63   i = 0;
  64   oldtype = -2;
  65   while ( start > ranges[i].start && ranges[i].type != -1 ) {
  66     oldtype = ranges[i].type;
  67     i++;
  68   }
  69
  70   /* Consider the replacement policy.  This current one is "overwrite." */
  71
  72   if ( start < ranges[i].start || ranges[i].type == -1 )
  73     insertrange_at(i++, start, type);
  74
  75   while ( i == 0 || last > ranges[i].start-1 ) {
  76     oldtype = ranges[i].type;
  77     ranges[i].type = type;
  78     i++;
  79   }
  80
  81   if ( last < ranges[i].start-1 )
  82     insertrange_at(i, last+1, oldtype);
  83
  84   /* Now the map is correct, but quite possibly not optimal.  Scan the
  85      map for ranges which are redundant and remove them. */
  86   i = j = 1;
  87   oldtype = ranges[0].type;
  88   while ( i < nranges ) {
  89     if ( ranges[i].type == oldtype ) {
  90       i++;
  91     } else {
  92       oldtype = ranges[i].type;
  93       if ( i != j )
  94         ranges[j] = ranges[i];
  95       i++; j++;
  96     }
  97   }
  98
  99   if ( i != j ) {
 100     ranges[j] = ranges[i];      /* Termination sentinel copy */
 101     nranges -= (i-j);
 102   }
 103 }