syslinux/memdisk/e820func.c

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