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
40extern int pci_boot_debug;
41#define	dprintf if (pci_boot_debug) printf
42
43void
44memlist_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
55struct memlist *
56memlist_alloc()
57{
58	return ((struct memlist *)kmem_zalloc(sizeof (struct memlist),
59	    KM_SLEEP));
60}
61
62void
63memlist_free(struct memlist *buf)
64{
65	kmem_free(buf, sizeof (struct memlist));
66}
67
68void
69memlist_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 */
83void
84memlist_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
151int
152memlist_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 */
220uint64_t
221memlist_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 */
256uint64_t
257memlist_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 */
291void
292memlist_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 */
309void
310memlist_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 */
324struct memlist *
325memlist_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
345int
346memlist_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