Home | History | Annotate | Download | only in memdisk 
      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 }
    108