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
34static struct memlist *memlist_freelist;
35static uint_t memlist_freelist_count;
36static kmutex_t memlist_freelist_mutex;
37
38/*
39 * Caller must test for NULL return.
40 */
41struct memlist *
42memlist_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
57void
58memlist_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
69void
70memlist_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
89void
90memlist_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 */
117void
118memlist_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
150void
151memlist_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
179struct memlist *
180memlist_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 */
196int
197memlist_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 */
331int
332memlist_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