1 /*
2 * Copyright (c) 1996 Paul Mackerras <paulus@cs.anu.edu.au>
3 * Changes to accomodate Power Macintoshes.
4 * Cort Dougan <cort@cs.nmt.edu>
5 * Rewrites.
6 * Grant Erickson <grant@lcse.umn.edu>
7 * General rework and split from mm/init.c.
8 *
9 * Module name: mem_pieces.c
10 *
11 * Description:
12 * Routines and data structures for manipulating and representing
13 * phyiscal memory extents (i.e. address/length pairs).
14 *
15 */
16
17 #include <linux/config.h>
18 #include <linux/kernel.h>
19 #include <linux/stddef.h>
20 #include <linux/blk.h>
21 #include <linux/init.h>
22
23 #include "mem_pieces.h"
24
25 extern struct mem_pieces phys_avail;
26
27 static void mem_pieces_print(struct mem_pieces *);
28
29 /*
30 * Scan a region for a piece of a given size with the required alignment.
31 */
32 void __init *
mem_pieces_find(unsigned int size,unsigned int align)33 mem_pieces_find(unsigned int size, unsigned int align)
34 {
35 int i;
36 unsigned a, e;
37 struct mem_pieces *mp = &phys_avail;
38
39 for (i = 0; i < mp->n_regions; ++i) {
40 a = mp->regions[i].address;
41 e = a + mp->regions[i].size;
42 a = (a + align - 1) & -align;
43 if (a + size <= e) {
44 mem_pieces_remove(mp, a, size, 1);
45 return __va(a);
46 }
47 }
48 panic("Couldn't find %u bytes at %u alignment\n", size, align);
49
50 return NULL;
51 }
52
53 /*
54 * Remove some memory from an array of pieces
55 */
56 void __init
mem_pieces_remove(struct mem_pieces * mp,unsigned int start,unsigned int size,int must_exist)57 mem_pieces_remove(struct mem_pieces *mp, unsigned int start, unsigned int size,
58 int must_exist)
59 {
60 int i, j;
61 unsigned int end, rs, re;
62 struct reg_property *rp;
63
64 end = start + size;
65 for (i = 0, rp = mp->regions; i < mp->n_regions; ++i, ++rp) {
66 if (end > rp->address && start < rp->address + rp->size)
67 break;
68 }
69 if (i >= mp->n_regions) {
70 if (must_exist)
71 printk("mem_pieces_remove: [%x,%x) not in any region\n",
72 start, end);
73 return;
74 }
75 for (; i < mp->n_regions && end > rp->address; ++i, ++rp) {
76 rs = rp->address;
77 re = rs + rp->size;
78 if (must_exist && (start < rs || end > re)) {
79 printk("mem_pieces_remove: bad overlap [%x,%x) with",
80 start, end);
81 mem_pieces_print(mp);
82 must_exist = 0;
83 }
84 if (start > rs) {
85 rp->size = start - rs;
86 if (end < re) {
87 /* need to split this entry */
88 if (mp->n_regions >= MEM_PIECES_MAX)
89 panic("eek... mem_pieces overflow");
90 for (j = mp->n_regions; j > i + 1; --j)
91 mp->regions[j] = mp->regions[j-1];
92 ++mp->n_regions;
93 rp[1].address = end;
94 rp[1].size = re - end;
95 }
96 } else {
97 if (end < re) {
98 rp->address = end;
99 rp->size = re - end;
100 } else {
101 /* need to delete this entry */
102 for (j = i; j < mp->n_regions - 1; ++j)
103 mp->regions[j] = mp->regions[j+1];
104 --mp->n_regions;
105 --i;
106 --rp;
107 }
108 }
109 }
110 }
111
112 static void __init
mem_pieces_print(struct mem_pieces * mp)113 mem_pieces_print(struct mem_pieces *mp)
114 {
115 int i;
116
117 for (i = 0; i < mp->n_regions; ++i)
118 printk(" [%x, %x)", mp->regions[i].address,
119 mp->regions[i].address + mp->regions[i].size);
120 printk("\n");
121 }
122
123 #if defined(CONFIG_APUS) || defined(CONFIG_ALL_PPC)
124 /*
125 * Add some memory to an array of pieces
126 */
127 void __init
mem_pieces_append(struct mem_pieces * mp,unsigned int start,unsigned int size)128 mem_pieces_append(struct mem_pieces *mp, unsigned int start, unsigned int size)
129 {
130 struct reg_property *rp;
131
132 if (mp->n_regions >= MEM_PIECES_MAX)
133 return;
134 rp = &mp->regions[mp->n_regions++];
135 rp->address = start;
136 rp->size = size;
137 }
138 #endif /* CONFIG_APUS || CONFIG_ALL_PPC */
139
140 void __init
mem_pieces_sort(struct mem_pieces * mp)141 mem_pieces_sort(struct mem_pieces *mp)
142 {
143 unsigned long a, s;
144 int i, j;
145
146 for (i = 1; i < mp->n_regions; ++i) {
147 a = mp->regions[i].address;
148 s = mp->regions[i].size;
149 for (j = i - 1; j >= 0; --j) {
150 if (a >= mp->regions[j].address)
151 break;
152 mp->regions[j+1] = mp->regions[j];
153 }
154 mp->regions[j+1].address = a;
155 mp->regions[j+1].size = s;
156 }
157 }
158
159 void __init
mem_pieces_coalesce(struct mem_pieces * mp)160 mem_pieces_coalesce(struct mem_pieces *mp)
161 {
162 unsigned long a, s, ns;
163 int i, j, d;
164
165 d = 0;
166 for (i = 0; i < mp->n_regions; i = j) {
167 a = mp->regions[i].address;
168 s = mp->regions[i].size;
169 for (j = i + 1; j < mp->n_regions
170 && mp->regions[j].address - a <= s; ++j) {
171 ns = mp->regions[j].address + mp->regions[j].size - a;
172 if (ns > s)
173 s = ns;
174 }
175 mp->regions[d].address = a;
176 mp->regions[d].size = s;
177 ++d;
178 }
179 mp->n_regions = d;
180 }
181