1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21 /*
22 * Copyright 2010 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25
26 /*
27 * XXX This stuff should be in usr/src/common, to be shared by boot
28 * code, kernel DR, and busra stuff.
29 *
30 * NOTE: We are only using the next-> link. The prev-> link is
31 * not used in the implementation.
32 */
33 #include <sys/types.h>
34 #include <sys/memlist.h>
35 #include <sys/kmem.h>
36 #include <sys/cmn_err.h>
37 #include <sys/pci_impl.h>
38 #include <sys/debug.h>
39
40 extern int pci_boot_debug;
41 #define dprintf if (pci_boot_debug) printf
42
43 void
memlist_dump(struct memlist * listp)44 memlist_dump(struct memlist *listp)
45 {
46 dprintf("memlist 0x%p content", (void *)listp);
47 while (listp) {
48 dprintf("(0x%x%x, 0x%x%x)",
49 (int)(listp->ml_address >> 32), (int)listp->ml_address,
50 (int)(listp->ml_size >> 32), (int)listp->ml_size);
51 listp = listp->ml_next;
52 }
53 }
54
55 struct memlist *
memlist_alloc()56 memlist_alloc()
57 {
58 return ((struct memlist *)kmem_zalloc(sizeof (struct memlist),
59 KM_SLEEP));
60 }
61
62 void
memlist_free(struct memlist * buf)63 memlist_free(struct memlist *buf)
64 {
65 kmem_free(buf, sizeof (struct memlist));
66 }
67
68 void
memlist_free_all(struct memlist ** list)69 memlist_free_all(struct memlist **list)
70 {
71 struct memlist *next, *buf;
72
73 next = *list;
74 while (next) {
75 buf = next;
76 next = buf->ml_next;
77 kmem_free(buf, sizeof (struct memlist));
78 }
79 *list = 0;
80 }
81
82 /* insert in the order of addresses */
83 void
memlist_insert(struct memlist ** listp,uint64_t addr,uint64_t size)84 memlist_insert(struct memlist **listp, uint64_t addr, uint64_t size)
85 {
86 int merge_left, merge_right;
87 struct memlist *entry;
88 struct memlist *prev = 0, *next;
89
90 /* find the location in list */
91 next = *listp;
92 while (next && next->ml_address <= addr) {
93 /*
94 * Drop if this entry already exists, in whole
95 * or in part
96 */
97 if (next->ml_address <= addr &&
98 next->ml_address + next->ml_size >= addr + size) {
99 /* next already contains this entire element; drop */
100 return;
101 }
102
103 /* Is this a "grow block size" request? */
104 if (next->ml_address == addr) {
105 break;
106 }
107 prev = next;
108 next = prev->ml_next;
109 }
110
111 merge_left = (prev && addr == prev->ml_address + prev->ml_size);
112 merge_right = (next && addr + size == next->ml_address);
113 if (merge_left && merge_right) {
114 prev->ml_size += size + next->ml_size;
115 prev->ml_next = next->ml_next;
116 memlist_free(next);
117 return;
118 }
119
120 if (merge_left) {
121 prev->ml_size += size;
122 return;
123 }
124
125 if (merge_right) {
126 next->ml_address = addr;
127 next->ml_size += size;
128 return;
129 }
130
131 entry = memlist_alloc();
132 entry->ml_address = addr;
133 entry->ml_size = size;
134 if (prev == 0) {
135 entry->ml_next = *listp;
136 *listp = entry;
137 } else {
138 entry->ml_next = next;
139 prev->ml_next = entry;
140 }
141 }
142
143 /*
144 * Delete memlist entries, assuming list sorted by address
145 */
146
147 #define MIN(a, b) ((a) < (b) ? (a) : (b))
148 #define MAX(a, b) ((a) > (b) ? (a) : (b))
149 #define IN_RANGE(a, b, e) ((a) >= (b) && (a) <= (e))
150
151 int
memlist_remove(struct memlist ** listp,uint64_t addr,uint64_t size)152 memlist_remove(struct memlist **listp, uint64_t addr, uint64_t size)
153 {
154 struct memlist *prev = 0;
155 struct memlist *chunk;
156 uint64_t rem_begin, rem_end;
157 uint64_t chunk_begin, chunk_end;
158 int begin_in_chunk, end_in_chunk;
159
160
161 /* ignore removal of zero-length item */
162 if (size == 0)
163 return (0);
164
165 /* also inherently ignore a zero-length list */
166 rem_begin = addr;
167 rem_end = addr + size - 1;
168 chunk = *listp;
169 while (chunk) {
170 chunk_begin = chunk->ml_address;
171 chunk_end = chunk->ml_address + chunk->ml_size - 1;
172 begin_in_chunk = IN_RANGE(rem_begin, chunk_begin, chunk_end);
173 end_in_chunk = IN_RANGE(rem_end, chunk_begin, chunk_end);
174
175 if (rem_begin <= chunk_begin && rem_end >= chunk_end) {
176 struct memlist *delete_chunk;
177
178 /* spans entire chunk - delete chunk */
179 delete_chunk = chunk;
180 if (prev == 0)
181 chunk = *listp = chunk->ml_next;
182 else
183 chunk = prev->ml_next = chunk->ml_next;
184
185 memlist_free(delete_chunk);
186 /* skip to start of while-loop */
187 continue;
188 } else if (begin_in_chunk && end_in_chunk &&
189 chunk_begin != rem_begin && chunk_end != rem_end) {
190 struct memlist *new;
191 /* split chunk */
192 new = memlist_alloc();
193 new->ml_address = rem_end + 1;
194 new->ml_size = chunk_end - new->ml_address + 1;
195 chunk->ml_size = rem_begin - chunk_begin;
196 new->ml_next = chunk->ml_next;
197 chunk->ml_next = new;
198 /* done - break out of while-loop */
199 break;
200 } else if (begin_in_chunk || end_in_chunk) {
201 /* trim chunk */
202 chunk->ml_size -= MIN(chunk_end, rem_end) -
203 MAX(chunk_begin, rem_begin) + 1;
204 if (rem_begin <= chunk_begin) {
205 chunk->ml_address = rem_end + 1;
206 break;
207 }
208 /* fall-through to next chunk */
209 }
210 prev = chunk;
211 chunk = chunk->ml_next;
212 }
213
214 return (0);
215 }
216
217 /*
218 * find and claim a memory chunk of given size, first fit
219 */
220 uint64_t
memlist_find(struct memlist ** listp,uint64_t size,int align)221 memlist_find(struct memlist **listp, uint64_t size, int align)
222 {
223 uint64_t delta, total_size;
224 uint64_t paddr;
225 struct memlist *prev = 0, *next;
226
227 /* find the chunk with sufficient size */
228 next = *listp;
229 while (next) {
230 delta = next->ml_address & ((align != 0) ? (align - 1) : 0);
231 if (delta != 0)
232 total_size = size + align - delta;
233 else
234 total_size = size; /* the addr is already aligned */
235 if (next->ml_size >= total_size)
236 break;
237 prev = next;
238 next = prev->ml_next;
239 }
240
241 if (next == 0)
242 return (0); /* Not found */
243
244 paddr = next->ml_address;
245 if (delta)
246 paddr += align - delta;
247 (void) memlist_remove(listp, paddr, size);
248
249 return (paddr);
250 }
251
252 /*
253 * find and claim a memory chunk of given size, starting
254 * at a specified address
255 */
256 uint64_t
memlist_find_with_startaddr(struct memlist ** listp,uint64_t address,uint64_t size,int align)257 memlist_find_with_startaddr(struct memlist **listp, uint64_t address,
258 uint64_t size, int align)
259 {
260 uint64_t delta, total_size;
261 uint64_t paddr;
262 struct memlist *next;
263
264 /* find the chunk starting at 'address' */
265 next = *listp;
266 while (next && (next->ml_address != address)) {
267 next = next->ml_next;
268 }
269 if (next == 0)
270 return (0); /* Not found */
271
272 delta = next->ml_address & ((align != 0) ? (align - 1) : 0);
273 if (delta != 0)
274 total_size = size + align - delta;
275 else
276 total_size = size; /* the addr is already aligned */
277 if (next->ml_size < total_size)
278 return (0); /* unsufficient size */
279
280 paddr = next->ml_address;
281 if (delta)
282 paddr += align - delta;
283 (void) memlist_remove(listp, paddr, size);
284
285 return (paddr);
286 }
287
288 /*
289 * Subsume memlist src into memlist dest
290 */
291 void
memlist_subsume(struct memlist ** src,struct memlist ** dest)292 memlist_subsume(struct memlist **src, struct memlist **dest)
293 {
294 struct memlist *head, *prev;
295
296 head = *src;
297 while (head) {
298 memlist_insert(dest, head->ml_address, head->ml_size);
299 prev = head;
300 head = head->ml_next;
301 memlist_free(prev);
302 }
303 *src = 0;
304 }
305
306 /*
307 * Merge memlist src into memlist dest; don't destroy src
308 */
309 void
memlist_merge(struct memlist ** src,struct memlist ** dest)310 memlist_merge(struct memlist **src, struct memlist **dest)
311 {
312 struct memlist *p;
313
314 p = *src;
315 while (p) {
316 memlist_insert(dest, p->ml_address, p->ml_size);
317 p = p->ml_next;
318 }
319 }
320
321 /*
322 * Make a copy of memlist
323 */
324 struct memlist *
memlist_dup(struct memlist * listp)325 memlist_dup(struct memlist *listp)
326 {
327 struct memlist *head = 0, *prev = 0;
328
329 while (listp) {
330 struct memlist *entry = memlist_alloc();
331 entry->ml_address = listp->ml_address;
332 entry->ml_size = listp->ml_size;
333 entry->ml_next = 0;
334 if (prev)
335 prev->ml_next = entry;
336 else
337 head = entry;
338 prev = entry;
339 listp = listp->ml_next;
340 }
341
342 return (head);
343 }
344
345 int
memlist_count(struct memlist * listp)346 memlist_count(struct memlist *listp)
347 {
348 int count = 0;
349 while (listp) {
350 count++;
351 listp = listp->ml_next;
352 }
353
354 return (count);
355 }
356