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