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