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 #include <sys/types.h>
27 #include <sys/cmn_err.h>
28 #include <sys/mutex.h>
29 #include <sys/param.h> /* for NULL */
30 #include <sys/debug.h>
31 #include <sys/memlist.h>
32 #include <sys/memlist_impl.h>
33
34 static struct memlist *memlist_freelist;
35 static uint_t memlist_freelist_count;
36 static kmutex_t memlist_freelist_mutex;
37
38 /*
39 * Caller must test for NULL return.
40 */
41 struct memlist *
memlist_get_one(void)42 memlist_get_one(void)
43 {
44 struct memlist *mlp;
45
46 mutex_enter(&memlist_freelist_mutex);
47 mlp = memlist_freelist;
48 if (mlp != NULL) {
49 memlist_freelist = mlp->ml_next;
50 memlist_freelist_count--;
51 }
52 mutex_exit(&memlist_freelist_mutex);
53
54 return (mlp);
55 }
56
57 void
memlist_free_one(struct memlist * mlp)58 memlist_free_one(struct memlist *mlp)
59 {
60 ASSERT(mlp != NULL);
61
62 mutex_enter(&memlist_freelist_mutex);
63 mlp->ml_next = memlist_freelist;
64 memlist_freelist = mlp;
65 memlist_freelist_count++;
66 mutex_exit(&memlist_freelist_mutex);
67 }
68
69 void
memlist_free_list(struct memlist * mlp)70 memlist_free_list(struct memlist *mlp)
71 {
72 struct memlist *mlendp;
73 uint_t count;
74
75 if (mlp == NULL) {
76 return;
77 }
78
79 count = 1;
80 for (mlendp = mlp; mlendp->ml_next != NULL; mlendp = mlendp->ml_next)
81 count++;
82 mutex_enter(&memlist_freelist_mutex);
83 mlendp->ml_next = memlist_freelist;
84 memlist_freelist = mlp;
85 memlist_freelist_count += count;
86 mutex_exit(&memlist_freelist_mutex);
87 }
88
89 void
memlist_free_block(caddr_t base,size_t bytes)90 memlist_free_block(caddr_t base, size_t bytes)
91 {
92 struct memlist *mlp, *mlendp;
93 uint_t count;
94
95 count = bytes / sizeof (struct memlist);
96 if (count == 0)
97 return;
98
99 mlp = (struct memlist *)base;
100 mlendp = &mlp[count - 1];
101 for (; mlp != mlendp; mlp++)
102 mlp->ml_next = mlp + 1;
103 mlendp->ml_next = NULL;
104 mlp = (struct memlist *)base;
105 mutex_enter(&memlist_freelist_mutex);
106 mlendp->ml_next = memlist_freelist;
107 memlist_freelist = mlp;
108 memlist_freelist_count += count;
109 mutex_exit(&memlist_freelist_mutex);
110 }
111
112 /*
113 * Insert into a sorted memory list.
114 * new = new element to insert
115 * curmemlistp = memory list to which to add segment.
116 */
117 void
memlist_insert(struct memlist * new,struct memlist ** curmemlistp)118 memlist_insert(
119 struct memlist *new,
120 struct memlist **curmemlistp)
121 {
122 struct memlist *cur, *last;
123 uint64_t start, end;
124
125 start = new->ml_address;
126 end = start + new->ml_size;
127 last = NULL;
128 for (cur = *curmemlistp; cur; cur = cur->ml_next) {
129 last = cur;
130 if (cur->ml_address >= end) {
131 new->ml_next = cur;
132 new->ml_prev = cur->ml_prev;
133 cur->ml_prev = new;
134 if (cur == *curmemlistp)
135 *curmemlistp = new;
136 else
137 new->ml_prev->ml_next = new;
138 return;
139 }
140 if (cur->ml_address + cur->ml_size > start)
141 panic("munged memory list = 0x%p\n",
142 (void *)curmemlistp);
143 }
144 new->ml_next = NULL;
145 new->ml_prev = last;
146 if (last != NULL)
147 last->ml_next = new;
148 }
149
150 void
memlist_del(struct memlist * memlistp,struct memlist ** curmemlistp)151 memlist_del(struct memlist *memlistp,
152 struct memlist **curmemlistp)
153 {
154 #ifdef DEBUG
155 /*
156 * Check that the memlist is on the list.
157 */
158 struct memlist *mlp;
159
160 for (mlp = *curmemlistp; mlp != NULL; mlp = mlp->ml_next)
161 if (mlp == memlistp)
162 break;
163 ASSERT(mlp == memlistp);
164 #endif /* DEBUG */
165 if (*curmemlistp == memlistp) {
166 ASSERT(memlistp->ml_prev == NULL);
167 *curmemlistp = memlistp->ml_next;
168 }
169 if (memlistp->ml_prev != NULL) {
170 ASSERT(memlistp->ml_prev->ml_next == memlistp);
171 memlistp->ml_prev->ml_next = memlistp->ml_next;
172 }
173 if (memlistp->ml_next != NULL) {
174 ASSERT(memlistp->ml_next->ml_prev == memlistp);
175 memlistp->ml_next->ml_prev = memlistp->ml_prev;
176 }
177 }
178
179 struct memlist *
memlist_find(struct memlist * mlp,uint64_t address)180 memlist_find(struct memlist *mlp, uint64_t address)
181 {
182 for (; mlp != NULL; mlp = mlp->ml_next)
183 if (address >= mlp->ml_address &&
184 address < (mlp->ml_address + mlp->ml_size))
185 break;
186 return (mlp);
187 }
188
189 /*
190 * Add a span to a memlist.
191 * Return:
192 * MEML_SPANOP_OK if OK.
193 * MEML_SPANOP_ESPAN if part or all of span already exists
194 * MEML_SPANOP_EALLOC for allocation failure
195 */
196 int
memlist_add_span(uint64_t address,uint64_t bytes,struct memlist ** curmemlistp)197 memlist_add_span(
198 uint64_t address,
199 uint64_t bytes,
200 struct memlist **curmemlistp)
201 {
202 struct memlist *dst;
203 struct memlist *prev, *next;
204
205 /*
206 * allocate a new struct memlist
207 */
208
209 dst = memlist_get_one();
210
211 if (dst == NULL) {
212 return (MEML_SPANOP_EALLOC);
213 }
214
215 dst->ml_address = address;
216 dst->ml_size = bytes;
217
218 /*
219 * First insert.
220 */
221 if (*curmemlistp == NULL) {
222 dst->ml_prev = NULL;
223 dst->ml_next = NULL;
224 *curmemlistp = dst;
225 return (MEML_SPANOP_OK);
226 }
227
228 /*
229 * Insert into sorted list.
230 */
231 for (prev = NULL, next = *curmemlistp; next != NULL;
232 prev = next, next = next->ml_next) {
233 if (address > (next->ml_address + next->ml_size))
234 continue;
235
236 /*
237 * Else insert here.
238 */
239
240 /*
241 * Prepend to next.
242 */
243 if ((address + bytes) == next->ml_address) {
244 memlist_free_one(dst);
245
246 next->ml_address = address;
247 next->ml_size += bytes;
248
249 return (MEML_SPANOP_OK);
250 }
251
252 /*
253 * Append to next.
254 */
255 if (address == (next->ml_address + next->ml_size)) {
256 memlist_free_one(dst);
257
258 if (next->ml_next) {
259 /*
260 * don't overlap with next->ml_next
261 */
262 if ((address + bytes) >
263 next->ml_next->ml_address) {
264 return (MEML_SPANOP_ESPAN);
265 }
266 /*
267 * Concatenate next and next->ml_next
268 */
269 if ((address + bytes) ==
270 next->ml_next->ml_address) {
271 struct memlist *mlp = next->ml_next;
272
273 if (next == *curmemlistp)
274 *curmemlistp = next->ml_next;
275
276 mlp->ml_address = next->ml_address;
277 mlp->ml_size += next->ml_size;
278 mlp->ml_size += bytes;
279
280 if (next->ml_prev)
281 next->ml_prev->ml_next = mlp;
282 mlp->ml_prev = next->ml_prev;
283
284 memlist_free_one(next);
285 return (MEML_SPANOP_OK);
286 }
287 }
288
289 next->ml_size += bytes;
290
291 return (MEML_SPANOP_OK);
292 }
293
294 /* don't overlap with next */
295 if ((address + bytes) > next->ml_address) {
296 memlist_free_one(dst);
297 return (MEML_SPANOP_ESPAN);
298 }
299
300 /*
301 * Insert before next.
302 */
303 dst->ml_prev = prev;
304 dst->ml_next = next;
305 next->ml_prev = dst;
306 if (prev == NULL) {
307 *curmemlistp = dst;
308 } else {
309 prev->ml_next = dst;
310 }
311 return (MEML_SPANOP_OK);
312 }
313
314 /*
315 * End of list, prev is valid and next is NULL.
316 */
317 prev->ml_next = dst;
318 dst->ml_prev = prev;
319 dst->ml_next = NULL;
320
321 return (MEML_SPANOP_OK);
322 }
323
324 /*
325 * Delete a span from a memlist.
326 * Return:
327 * MEML_SPANOP_OK if OK.
328 * MEML_SPANOP_ESPAN if part or all of span does not exist
329 * MEML_SPANOP_EALLOC for allocation failure
330 */
331 int
memlist_delete_span(uint64_t address,uint64_t bytes,struct memlist ** curmemlistp)332 memlist_delete_span(
333 uint64_t address,
334 uint64_t bytes,
335 struct memlist **curmemlistp)
336 {
337 struct memlist *dst, *next;
338
339 /*
340 * Find element containing address.
341 */
342 for (next = *curmemlistp; next != NULL; next = next->ml_next) {
343 if ((address >= next->ml_address) &&
344 (address < next->ml_address + next->ml_size))
345 break;
346 }
347
348 /*
349 * If start address not in list.
350 */
351 if (next == NULL) {
352 return (MEML_SPANOP_ESPAN);
353 }
354
355 /*
356 * Error if size goes off end of this struct memlist.
357 */
358 if (address + bytes > next->ml_address + next->ml_size) {
359 return (MEML_SPANOP_ESPAN);
360 }
361
362 /*
363 * Span at beginning of struct memlist.
364 */
365 if (address == next->ml_address) {
366 /*
367 * If start & size match, delete from list.
368 */
369 if (bytes == next->ml_size) {
370 if (next == *curmemlistp)
371 *curmemlistp = next->ml_next;
372 if (next->ml_prev != NULL)
373 next->ml_prev->ml_next = next->ml_next;
374 if (next->ml_next != NULL)
375 next->ml_next->ml_prev = next->ml_prev;
376
377 memlist_free_one(next);
378 } else {
379 /*
380 * Increment start address by bytes.
381 */
382 next->ml_address += bytes;
383 next->ml_size -= bytes;
384 }
385 return (MEML_SPANOP_OK);
386 }
387
388 /*
389 * Span at end of struct memlist.
390 */
391 if (address + bytes == next->ml_address + next->ml_size) {
392 /*
393 * decrement size by bytes
394 */
395 next->ml_size -= bytes;
396 return (MEML_SPANOP_OK);
397 }
398
399 /*
400 * Delete a span in the middle of the struct memlist.
401 */
402 {
403 /*
404 * create a new struct memlist
405 */
406 dst = memlist_get_one();
407
408 if (dst == NULL) {
409 return (MEML_SPANOP_EALLOC);
410 }
411
412 /*
413 * Existing struct memlist gets address
414 * and size up to start of span.
415 */
416 dst->ml_address = address + bytes;
417 dst->ml_size =
418 (next->ml_address + next->ml_size) - dst->ml_address;
419 next->ml_size = address - next->ml_address;
420
421 /*
422 * New struct memlist gets address starting
423 * after span, until end.
424 */
425
426 /*
427 * link in new memlist after old
428 */
429 dst->ml_next = next->ml_next;
430 dst->ml_prev = next;
431
432 if (next->ml_next != NULL)
433 next->ml_next->ml_prev = dst;
434 next->ml_next = dst;
435 }
436 return (MEML_SPANOP_OK);
437 }
438