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 } else {
149 ASSERT3P(*curmemlistp, ==, NULL);
150 *curmemlistp = new;
151 }
152 }
153
154 void
memlist_del(struct memlist * memlistp,struct memlist ** curmemlistp)155 memlist_del(struct memlist *memlistp,
156 struct memlist **curmemlistp)
157 {
158 #ifdef DEBUG
159 /*
160 * Check that the memlist is on the list.
161 */
162 struct memlist *mlp;
163
164 for (mlp = *curmemlistp; mlp != NULL; mlp = mlp->ml_next)
165 if (mlp == memlistp)
166 break;
167 ASSERT(mlp == memlistp);
168 #endif /* DEBUG */
169 if (*curmemlistp == memlistp) {
170 ASSERT(memlistp->ml_prev == NULL);
171 *curmemlistp = memlistp->ml_next;
172 }
173 if (memlistp->ml_prev != NULL) {
174 ASSERT(memlistp->ml_prev->ml_next == memlistp);
175 memlistp->ml_prev->ml_next = memlistp->ml_next;
176 }
177 if (memlistp->ml_next != NULL) {
178 ASSERT(memlistp->ml_next->ml_prev == memlistp);
179 memlistp->ml_next->ml_prev = memlistp->ml_prev;
180 }
181 }
182
183 struct memlist *
memlist_find(struct memlist * mlp,uint64_t address)184 memlist_find(struct memlist *mlp, uint64_t address)
185 {
186 for (; mlp != NULL; mlp = mlp->ml_next)
187 if (address >= mlp->ml_address &&
188 address < (mlp->ml_address + mlp->ml_size))
189 break;
190 return (mlp);
191 }
192
193 /*
194 * Add a span to a memlist.
195 * Return:
196 * MEML_SPANOP_OK if OK.
197 * MEML_SPANOP_ESPAN if part or all of span already exists
198 * MEML_SPANOP_EALLOC for allocation failure
199 */
200 int
memlist_add_span(uint64_t address,uint64_t bytes,struct memlist ** curmemlistp)201 memlist_add_span(
202 uint64_t address,
203 uint64_t bytes,
204 struct memlist **curmemlistp)
205 {
206 struct memlist *dst;
207 struct memlist *prev, *next;
208
209 /*
210 * allocate a new struct memlist
211 */
212
213 dst = memlist_get_one();
214
215 if (dst == NULL) {
216 return (MEML_SPANOP_EALLOC);
217 }
218
219 dst->ml_address = address;
220 dst->ml_size = bytes;
221
222 /*
223 * First insert.
224 */
225 if (*curmemlistp == NULL) {
226 dst->ml_prev = NULL;
227 dst->ml_next = NULL;
228 *curmemlistp = dst;
229 return (MEML_SPANOP_OK);
230 }
231
232 /*
233 * Insert into sorted list.
234 */
235 for (prev = NULL, next = *curmemlistp; next != NULL;
236 prev = next, next = next->ml_next) {
237 if (address > (next->ml_address + next->ml_size))
238 continue;
239
240 /*
241 * Else insert here.
242 */
243
244 /*
245 * Prepend to next.
246 */
247 if ((address + bytes) == next->ml_address) {
248 memlist_free_one(dst);
249
250 next->ml_address = address;
251 next->ml_size += bytes;
252
253 return (MEML_SPANOP_OK);
254 }
255
256 /*
257 * Append to next.
258 */
259 if (address == (next->ml_address + next->ml_size)) {
260 memlist_free_one(dst);
261
262 if (next->ml_next) {
263 /*
264 * don't overlap with next->ml_next
265 */
266 if ((address + bytes) >
267 next->ml_next->ml_address) {
268 return (MEML_SPANOP_ESPAN);
269 }
270 /*
271 * Concatenate next and next->ml_next
272 */
273 if ((address + bytes) ==
274 next->ml_next->ml_address) {
275 struct memlist *mlp = next->ml_next;
276
277 if (next == *curmemlistp)
278 *curmemlistp = next->ml_next;
279
280 mlp->ml_address = next->ml_address;
281 mlp->ml_size += next->ml_size;
282 mlp->ml_size += bytes;
283
284 if (next->ml_prev)
285 next->ml_prev->ml_next = mlp;
286 mlp->ml_prev = next->ml_prev;
287
288 memlist_free_one(next);
289 return (MEML_SPANOP_OK);
290 }
291 }
292
293 next->ml_size += bytes;
294
295 return (MEML_SPANOP_OK);
296 }
297
298 /* don't overlap with next */
299 if ((address + bytes) > next->ml_address) {
300 memlist_free_one(dst);
301 return (MEML_SPANOP_ESPAN);
302 }
303
304 /*
305 * Insert before next.
306 */
307 dst->ml_prev = prev;
308 dst->ml_next = next;
309 next->ml_prev = dst;
310 if (prev == NULL) {
311 *curmemlistp = dst;
312 } else {
313 prev->ml_next = dst;
314 }
315 return (MEML_SPANOP_OK);
316 }
317
318 /*
319 * End of list, prev is valid and next is NULL.
320 */
321 prev->ml_next = dst;
322 dst->ml_prev = prev;
323 dst->ml_next = NULL;
324
325 return (MEML_SPANOP_OK);
326 }
327
328 /*
329 * Delete a span from a memlist.
330 * Return:
331 * MEML_SPANOP_OK if OK.
332 * MEML_SPANOP_ESPAN if part or all of span does not exist
333 * MEML_SPANOP_EALLOC for allocation failure
334 */
335 int
memlist_delete_span(uint64_t address,uint64_t bytes,struct memlist ** curmemlistp)336 memlist_delete_span(
337 uint64_t address,
338 uint64_t bytes,
339 struct memlist **curmemlistp)
340 {
341 struct memlist *dst, *next;
342
343 /*
344 * Find element containing address.
345 */
346 for (next = *curmemlistp; next != NULL; next = next->ml_next) {
347 if ((address >= next->ml_address) &&
348 (address < next->ml_address + next->ml_size))
349 break;
350 }
351
352 /*
353 * If start address not in list.
354 */
355 if (next == NULL) {
356 return (MEML_SPANOP_ESPAN);
357 }
358
359 /*
360 * Error if size goes off end of this struct memlist.
361 */
362 if (address + bytes > next->ml_address + next->ml_size) {
363 return (MEML_SPANOP_ESPAN);
364 }
365
366 /*
367 * Span at beginning of struct memlist.
368 */
369 if (address == next->ml_address) {
370 /*
371 * If start & size match, delete from list.
372 */
373 if (bytes == next->ml_size) {
374 if (next == *curmemlistp)
375 *curmemlistp = next->ml_next;
376 if (next->ml_prev != NULL)
377 next->ml_prev->ml_next = next->ml_next;
378 if (next->ml_next != NULL)
379 next->ml_next->ml_prev = next->ml_prev;
380
381 memlist_free_one(next);
382 } else {
383 /*
384 * Increment start address by bytes.
385 */
386 next->ml_address += bytes;
387 next->ml_size -= bytes;
388 }
389 return (MEML_SPANOP_OK);
390 }
391
392 /*
393 * Span at end of struct memlist.
394 */
395 if (address + bytes == next->ml_address + next->ml_size) {
396 /*
397 * decrement size by bytes
398 */
399 next->ml_size -= bytes;
400 return (MEML_SPANOP_OK);
401 }
402
403 /*
404 * Delete a span in the middle of the struct memlist.
405 */
406 {
407 /*
408 * create a new struct memlist
409 */
410 dst = memlist_get_one();
411
412 if (dst == NULL) {
413 return (MEML_SPANOP_EALLOC);
414 }
415
416 /*
417 * Existing struct memlist gets address
418 * and size up to start of span.
419 */
420 dst->ml_address = address + bytes;
421 dst->ml_size =
422 (next->ml_address + next->ml_size) - dst->ml_address;
423 next->ml_size = address - next->ml_address;
424
425 /*
426 * New struct memlist gets address starting
427 * after span, until end.
428 */
429
430 /*
431 * link in new memlist after old
432 */
433 dst->ml_next = next->ml_next;
434 dst->ml_prev = next;
435
436 if (next->ml_next != NULL)
437 next->ml_next->ml_prev = dst;
438 next->ml_next = dst;
439 }
440 return (MEML_SPANOP_OK);
441 }
442