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 */ 29struct e820range ranges[MAXRANGES]; 30int nranges; 31 32void e820map_init(void) 33{ 34 memset(ranges, 0, sizeof(ranges)); 35 nranges = 1; 36 ranges[1].type = -1U; 37} 38 39static 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 54void 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