]>
Commit | Line | Data |
---|---|---|
4ed6552f KG |
1 | /* |
2 | * Procedures for maintaining information about logical memory blocks. | |
3 | * | |
4 | * Peter Bergner, IBM Corp. June 2001. | |
5 | * Copyright (C) 2001 Peter Bergner. | |
6 | * | |
7 | * This program is free software; you can redistribute it and/or | |
8 | * modify it under the terms of the GNU General Public License | |
9 | * as published by the Free Software Foundation; either version | |
10 | * 2 of the License, or (at your option) any later version. | |
11 | */ | |
12 | ||
13 | #include <common.h> | |
14 | #include <lmb.h> | |
15 | ||
16 | #define LMB_ALLOC_ANYWHERE 0 | |
17 | ||
18 | void lmb_dump_all(struct lmb *lmb) | |
19 | { | |
20 | #ifdef DEBUG | |
21 | unsigned long i; | |
22 | ||
23 | debug("lmb_dump_all:\n"); | |
24 | debug(" memory.cnt = 0x%lx\n", lmb->memory.cnt); | |
391fd93a BB |
25 | debug(" memory.size = 0x%llx\n", |
26 | (unsigned long long)lmb->memory.size); | |
4ed6552f | 27 | for (i=0; i < lmb->memory.cnt ;i++) { |
391fd93a | 28 | debug(" memory.reg[0x%x].base = 0x%llx\n", i, |
4ed6552f | 29 | lmb->memory.region[i].base); |
391fd93a | 30 | debug(" .size = 0x%llx\n", |
4ed6552f KG |
31 | lmb->memory.region[i].size); |
32 | } | |
33 | ||
34 | debug("\n reserved.cnt = 0x%lx\n", lmb->reserved.cnt); | |
391fd93a | 35 | debug(" reserved.size = 0x%llx\n", lmb->reserved.size); |
4ed6552f | 36 | for (i=0; i < lmb->reserved.cnt ;i++) { |
391fd93a | 37 | debug(" reserved.reg[0x%x].base = 0x%llx\n", i, |
4ed6552f | 38 | lmb->reserved.region[i].base); |
391fd93a | 39 | debug(" .size = 0x%llx\n", |
4ed6552f KG |
40 | lmb->reserved.region[i].size); |
41 | } | |
42 | #endif /* DEBUG */ | |
43 | } | |
44 | ||
391fd93a BB |
45 | static long lmb_addrs_overlap(phys_addr_t base1, |
46 | phys_size_t size1, phys_addr_t base2, phys_size_t size2) | |
4ed6552f KG |
47 | { |
48 | return ((base1 < (base2+size2)) && (base2 < (base1+size1))); | |
49 | } | |
50 | ||
391fd93a BB |
51 | static long lmb_addrs_adjacent(phys_addr_t base1, phys_size_t size1, |
52 | phys_addr_t base2, phys_size_t size2) | |
4ed6552f KG |
53 | { |
54 | if (base2 == base1 + size1) | |
55 | return 1; | |
56 | else if (base1 == base2 + size2) | |
57 | return -1; | |
58 | ||
59 | return 0; | |
60 | } | |
61 | ||
62 | static long lmb_regions_adjacent(struct lmb_region *rgn, | |
63 | unsigned long r1, unsigned long r2) | |
64 | { | |
391fd93a BB |
65 | phys_addr_t base1 = rgn->region[r1].base; |
66 | phys_size_t size1 = rgn->region[r1].size; | |
67 | phys_addr_t base2 = rgn->region[r2].base; | |
68 | phys_size_t size2 = rgn->region[r2].size; | |
4ed6552f KG |
69 | |
70 | return lmb_addrs_adjacent(base1, size1, base2, size2); | |
71 | } | |
72 | ||
73 | static void lmb_remove_region(struct lmb_region *rgn, unsigned long r) | |
74 | { | |
75 | unsigned long i; | |
76 | ||
77 | for (i = r; i < rgn->cnt - 1; i++) { | |
78 | rgn->region[i].base = rgn->region[i + 1].base; | |
79 | rgn->region[i].size = rgn->region[i + 1].size; | |
80 | } | |
81 | rgn->cnt--; | |
82 | } | |
83 | ||
84 | /* Assumption: base addr of region 1 < base addr of region 2 */ | |
85 | static void lmb_coalesce_regions(struct lmb_region *rgn, | |
86 | unsigned long r1, unsigned long r2) | |
87 | { | |
88 | rgn->region[r1].size += rgn->region[r2].size; | |
89 | lmb_remove_region(rgn, r2); | |
90 | } | |
91 | ||
92 | void lmb_init(struct lmb *lmb) | |
93 | { | |
94 | /* Create a dummy zero size LMB which will get coalesced away later. | |
95 | * This simplifies the lmb_add() code below... | |
96 | */ | |
97 | lmb->memory.region[0].base = 0; | |
98 | lmb->memory.region[0].size = 0; | |
99 | lmb->memory.cnt = 1; | |
100 | lmb->memory.size = 0; | |
101 | ||
102 | /* Ditto. */ | |
103 | lmb->reserved.region[0].base = 0; | |
104 | lmb->reserved.region[0].size = 0; | |
105 | lmb->reserved.cnt = 1; | |
106 | lmb->reserved.size = 0; | |
107 | } | |
108 | ||
109 | /* This routine called with relocation disabled. */ | |
391fd93a | 110 | static long lmb_add_region(struct lmb_region *rgn, phys_addr_t base, phys_size_t size) |
4ed6552f KG |
111 | { |
112 | unsigned long coalesced = 0; | |
113 | long adjacent, i; | |
114 | ||
115 | if ((rgn->cnt == 1) && (rgn->region[0].size == 0)) { | |
116 | rgn->region[0].base = base; | |
117 | rgn->region[0].size = size; | |
118 | return 0; | |
119 | } | |
120 | ||
121 | /* First try and coalesce this LMB with another. */ | |
122 | for (i=0; i < rgn->cnt; i++) { | |
391fd93a BB |
123 | phys_addr_t rgnbase = rgn->region[i].base; |
124 | phys_size_t rgnsize = rgn->region[i].size; | |
4ed6552f KG |
125 | |
126 | if ((rgnbase == base) && (rgnsize == size)) | |
127 | /* Already have this region, so we're done */ | |
128 | return 0; | |
129 | ||
130 | adjacent = lmb_addrs_adjacent(base,size,rgnbase,rgnsize); | |
131 | if ( adjacent > 0 ) { | |
132 | rgn->region[i].base -= size; | |
133 | rgn->region[i].size += size; | |
134 | coalesced++; | |
135 | break; | |
136 | } | |
137 | else if ( adjacent < 0 ) { | |
138 | rgn->region[i].size += size; | |
139 | coalesced++; | |
140 | break; | |
141 | } | |
142 | } | |
143 | ||
144 | if ((i < rgn->cnt-1) && lmb_regions_adjacent(rgn, i, i+1) ) { | |
145 | lmb_coalesce_regions(rgn, i, i+1); | |
146 | coalesced++; | |
147 | } | |
148 | ||
149 | if (coalesced) | |
150 | return coalesced; | |
151 | if (rgn->cnt >= MAX_LMB_REGIONS) | |
152 | return -1; | |
153 | ||
154 | /* Couldn't coalesce the LMB, so add it to the sorted table. */ | |
155 | for (i = rgn->cnt-1; i >= 0; i--) { | |
156 | if (base < rgn->region[i].base) { | |
157 | rgn->region[i+1].base = rgn->region[i].base; | |
158 | rgn->region[i+1].size = rgn->region[i].size; | |
159 | } else { | |
160 | rgn->region[i+1].base = base; | |
161 | rgn->region[i+1].size = size; | |
162 | break; | |
163 | } | |
164 | } | |
165 | ||
166 | if (base < rgn->region[0].base) { | |
167 | rgn->region[0].base = base; | |
168 | rgn->region[0].size = size; | |
169 | } | |
170 | ||
171 | rgn->cnt++; | |
172 | ||
173 | return 0; | |
174 | } | |
175 | ||
176 | /* This routine may be called with relocation disabled. */ | |
391fd93a | 177 | long lmb_add(struct lmb *lmb, phys_addr_t base, phys_size_t size) |
4ed6552f KG |
178 | { |
179 | struct lmb_region *_rgn = &(lmb->memory); | |
180 | ||
181 | return lmb_add_region(_rgn, base, size); | |
182 | } | |
183 | ||
98874ff3 | 184 | long lmb_free(struct lmb *lmb, phys_addr_t base, phys_size_t size) |
63796c4e AF |
185 | { |
186 | struct lmb_region *rgn = &(lmb->reserved); | |
98874ff3 AF |
187 | phys_addr_t rgnbegin, rgnend; |
188 | phys_addr_t end = base + size; | |
63796c4e AF |
189 | int i; |
190 | ||
191 | rgnbegin = rgnend = 0; /* supress gcc warnings */ | |
192 | ||
193 | /* Find the region where (base, size) belongs to */ | |
194 | for (i=0; i < rgn->cnt; i++) { | |
195 | rgnbegin = rgn->region[i].base; | |
196 | rgnend = rgnbegin + rgn->region[i].size; | |
197 | ||
198 | if ((rgnbegin <= base) && (end <= rgnend)) | |
199 | break; | |
200 | } | |
201 | ||
202 | /* Didn't find the region */ | |
203 | if (i == rgn->cnt) | |
204 | return -1; | |
205 | ||
206 | /* Check to see if we are removing entire region */ | |
207 | if ((rgnbegin == base) && (rgnend == end)) { | |
208 | lmb_remove_region(rgn, i); | |
209 | return 0; | |
210 | } | |
211 | ||
212 | /* Check to see if region is matching at the front */ | |
213 | if (rgnbegin == base) { | |
214 | rgn->region[i].base = end; | |
215 | rgn->region[i].size -= size; | |
216 | return 0; | |
217 | } | |
218 | ||
219 | /* Check to see if the region is matching at the end */ | |
220 | if (rgnend == end) { | |
221 | rgn->region[i].size -= size; | |
222 | return 0; | |
223 | } | |
224 | ||
225 | /* | |
226 | * We need to split the entry - adjust the current one to the | |
227 | * beginging of the hole and add the region after hole. | |
228 | */ | |
229 | rgn->region[i].size = base - rgn->region[i].base; | |
230 | return lmb_add_region(rgn, end, rgnend - end); | |
231 | } | |
232 | ||
391fd93a | 233 | long lmb_reserve(struct lmb *lmb, phys_addr_t base, phys_size_t size) |
4ed6552f KG |
234 | { |
235 | struct lmb_region *_rgn = &(lmb->reserved); | |
236 | ||
237 | return lmb_add_region(_rgn, base, size); | |
238 | } | |
239 | ||
391fd93a BB |
240 | long lmb_overlaps_region(struct lmb_region *rgn, phys_addr_t base, |
241 | phys_size_t size) | |
4ed6552f KG |
242 | { |
243 | unsigned long i; | |
244 | ||
245 | for (i=0; i < rgn->cnt; i++) { | |
391fd93a BB |
246 | phys_addr_t rgnbase = rgn->region[i].base; |
247 | phys_size_t rgnsize = rgn->region[i].size; | |
4ed6552f KG |
248 | if ( lmb_addrs_overlap(base,size,rgnbase,rgnsize) ) { |
249 | break; | |
250 | } | |
251 | } | |
252 | ||
253 | return (i < rgn->cnt) ? i : -1; | |
254 | } | |
255 | ||
391fd93a | 256 | phys_addr_t lmb_alloc(struct lmb *lmb, phys_size_t size, ulong align) |
4ed6552f KG |
257 | { |
258 | return lmb_alloc_base(lmb, size, align, LMB_ALLOC_ANYWHERE); | |
259 | } | |
260 | ||
391fd93a | 261 | phys_addr_t lmb_alloc_base(struct lmb *lmb, phys_size_t size, ulong align, phys_addr_t max_addr) |
4ed6552f | 262 | { |
391fd93a | 263 | phys_addr_t alloc; |
4ed6552f KG |
264 | |
265 | alloc = __lmb_alloc_base(lmb, size, align, max_addr); | |
266 | ||
267 | if (alloc == 0) | |
268 | printf("ERROR: Failed to allocate 0x%lx bytes below 0x%lx.\n", | |
269 | size, max_addr); | |
270 | ||
271 | return alloc; | |
272 | } | |
273 | ||
391fd93a | 274 | static phys_addr_t lmb_align_down(phys_addr_t addr, phys_size_t size) |
4ed6552f KG |
275 | { |
276 | return addr & ~(size - 1); | |
277 | } | |
278 | ||
391fd93a | 279 | static phys_addr_t lmb_align_up(phys_addr_t addr, ulong size) |
4ed6552f KG |
280 | { |
281 | return (addr + (size - 1)) & ~(size - 1); | |
282 | } | |
283 | ||
391fd93a | 284 | phys_addr_t __lmb_alloc_base(struct lmb *lmb, phys_size_t size, ulong align, phys_addr_t max_addr) |
4ed6552f KG |
285 | { |
286 | long i, j; | |
391fd93a | 287 | phys_addr_t base = 0; |
7570a994 | 288 | phys_addr_t res_base; |
4ed6552f KG |
289 | |
290 | for (i = lmb->memory.cnt-1; i >= 0; i--) { | |
391fd93a BB |
291 | phys_addr_t lmbbase = lmb->memory.region[i].base; |
292 | phys_size_t lmbsize = lmb->memory.region[i].size; | |
4ed6552f | 293 | |
7570a994 AF |
294 | if (lmbsize < size) |
295 | continue; | |
4ed6552f KG |
296 | if (max_addr == LMB_ALLOC_ANYWHERE) |
297 | base = lmb_align_down(lmbbase + lmbsize - size, align); | |
298 | else if (lmbbase < max_addr) { | |
299 | base = min(lmbbase + lmbsize, max_addr); | |
300 | base = lmb_align_down(base - size, align); | |
301 | } else | |
302 | continue; | |
303 | ||
7570a994 AF |
304 | while (base && lmbbase <= base) { |
305 | j = lmb_overlaps_region(&lmb->reserved, base, size); | |
306 | if (j < 0) { | |
307 | /* This area isn't reserved, take it */ | |
308 | if (lmb_add_region(&lmb->reserved, base, | |
309 | lmb_align_up(size, | |
310 | align)) < 0) | |
311 | return 0; | |
312 | return base; | |
313 | } | |
314 | res_base = lmb->reserved.region[j].base; | |
315 | if (res_base < size) | |
316 | break; | |
317 | base = lmb_align_down(res_base - size, align); | |
318 | } | |
4ed6552f | 319 | } |
7570a994 | 320 | return 0; |
4ed6552f KG |
321 | } |
322 | ||
391fd93a | 323 | int lmb_is_reserved(struct lmb *lmb, phys_addr_t addr) |
4ed6552f KG |
324 | { |
325 | int i; | |
326 | ||
327 | for (i = 0; i < lmb->reserved.cnt; i++) { | |
391fd93a | 328 | phys_addr_t upper = lmb->reserved.region[i].base + |
4ed6552f KG |
329 | lmb->reserved.region[i].size - 1; |
330 | if ((addr >= lmb->reserved.region[i].base) && (addr <= upper)) | |
331 | return 1; | |
332 | } | |
333 | return 0; | |
334 | } |