xref: /illumos-gate/usr/src/uts/intel/io/pci/pci_memlist.c (revision 4702be99a7621a425e53a63af8ae0ff7fe973b31)
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  * Copyright 2020 OmniOS Community Edition (OmniOSce) Association.
26  * Copyright 2024 Oxide Computer Company
27  */
28 
29 /*
30  * XXX This stuff should be in usr/src/common, to be shared by boot
31  * code, kernel DR, and busra stuff.
32  *
33  * NOTE: We are only using the next-> link. The prev-> link is
34  *	not used in the implementation.
35  */
36 #include <sys/types.h>
37 #include <sys/memlist.h>
38 #include <sys/kmem.h>
39 #include <sys/cmn_err.h>
40 #include <sys/pci_impl.h>
41 #include <sys/debug.h>
42 
43 int pci_memlist_debug;
44 #define	dprintf if (pci_memlist_debug) printf
45 
46 void
pci_memlist_dump(struct memlist * listp)47 pci_memlist_dump(struct memlist *listp)
48 {
49 	dprintf("memlist 0x%p content: ", (void *)listp);
50 	while (listp) {
51 		dprintf("(0x%lx, 0x%lx) ",
52 		    listp->ml_address, listp->ml_size);
53 		listp = listp->ml_next;
54 	}
55 	dprintf("\n");
56 }
57 
58 struct memlist *
pci_memlist_alloc()59 pci_memlist_alloc()
60 {
61 	return ((struct memlist *)kmem_zalloc(sizeof (struct memlist),
62 	    KM_SLEEP));
63 }
64 
65 void
pci_memlist_free(struct memlist * buf)66 pci_memlist_free(struct memlist *buf)
67 {
68 	kmem_free(buf, sizeof (struct memlist));
69 }
70 
71 void
pci_memlist_free_all(struct memlist ** list)72 pci_memlist_free_all(struct memlist **list)
73 {
74 	struct memlist  *next, *buf;
75 
76 	next = *list;
77 	while (next) {
78 		buf = next;
79 		next = buf->ml_next;
80 		kmem_free(buf, sizeof (struct memlist));
81 	}
82 	*list = 0;
83 }
84 
85 /* insert in the order of addresses */
86 void
pci_memlist_insert(struct memlist ** listp,uint64_t addr,uint64_t size)87 pci_memlist_insert(struct memlist **listp, uint64_t addr, uint64_t size)
88 {
89 	int merge_left, merge_right;
90 	struct memlist *entry;
91 	struct memlist *prev = 0, *next;
92 
93 	/* find the location in list */
94 	next = *listp;
95 	while (next && next->ml_address <= addr) {
96 		/*
97 		 * Drop if this entry already exists, in whole
98 		 * or in part
99 		 */
100 		if (next->ml_address <= addr &&
101 		    next->ml_address + next->ml_size >= addr + size) {
102 			/* next already contains this entire element; drop */
103 			return;
104 		}
105 
106 		/* Is this a "grow block size" request? */
107 		if (next->ml_address == addr) {
108 			break;
109 		}
110 		prev = next;
111 		next = prev->ml_next;
112 	}
113 
114 	merge_left = (prev && addr == prev->ml_address + prev->ml_size);
115 	merge_right = (next && addr + size == next->ml_address);
116 	if (merge_left && merge_right) {
117 		prev->ml_size += size + next->ml_size;
118 		prev->ml_next = next->ml_next;
119 		pci_memlist_free(next);
120 		return;
121 	}
122 
123 	if (merge_left) {
124 		prev->ml_size += size;
125 		return;
126 	}
127 
128 	if (merge_right) {
129 		next->ml_address = addr;
130 		next->ml_size += size;
131 		return;
132 	}
133 
134 	entry = pci_memlist_alloc();
135 	entry->ml_address = addr;
136 	entry->ml_size = size;
137 	if (prev == 0) {
138 		entry->ml_next = *listp;
139 		*listp = entry;
140 	} else {
141 		entry->ml_next = next;
142 		prev->ml_next = entry;
143 	}
144 }
145 
146 /*
147  * Delete memlist entries, assuming list sorted by address
148  */
149 
150 #define	MIN(a, b)	((a) < (b) ? (a) : (b))
151 #define	MAX(a, b)	((a) > (b) ? (a) : (b))
152 #define	IN_RANGE(a, b, e) ((a) >= (b) && (a) <= (e))
153 
154 int
pci_memlist_remove(struct memlist ** listp,uint64_t addr,uint64_t size)155 pci_memlist_remove(struct memlist **listp, uint64_t addr, uint64_t size)
156 {
157 	struct memlist *prev = 0;
158 	struct memlist *chunk;
159 	uint64_t rem_begin, rem_end;
160 	uint64_t chunk_begin, chunk_end;
161 	int begin_in_chunk, end_in_chunk;
162 
163 
164 	/* ignore removal of zero-length item */
165 	if (size == 0)
166 		return (0);
167 
168 	/* also inherently ignore a zero-length list */
169 	rem_begin = addr;
170 	rem_end = addr + size - 1;
171 	chunk = *listp;
172 	while (chunk) {
173 		chunk_begin = chunk->ml_address;
174 		chunk_end = chunk->ml_address + chunk->ml_size - 1;
175 		begin_in_chunk = IN_RANGE(rem_begin, chunk_begin, chunk_end);
176 		end_in_chunk = IN_RANGE(rem_end, chunk_begin, chunk_end);
177 
178 		if (rem_begin <= chunk_begin && rem_end >= chunk_end) {
179 			struct memlist *delete_chunk;
180 
181 			/* spans entire chunk - delete chunk */
182 			delete_chunk = chunk;
183 			if (prev == 0)
184 				chunk = *listp = chunk->ml_next;
185 			else
186 				chunk = prev->ml_next = chunk->ml_next;
187 
188 			pci_memlist_free(delete_chunk);
189 			/* skip to start of while-loop */
190 			continue;
191 		} else if (begin_in_chunk && end_in_chunk &&
192 		    chunk_begin != rem_begin && chunk_end != rem_end) {
193 			struct memlist *new;
194 			/* split chunk */
195 			new = pci_memlist_alloc();
196 			new->ml_address = rem_end + 1;
197 			new->ml_size = chunk_end - new->ml_address + 1;
198 			chunk->ml_size = rem_begin - chunk_begin;
199 			new->ml_next = chunk->ml_next;
200 			chunk->ml_next = new;
201 			/* done - break out of while-loop */
202 			break;
203 		} else if (begin_in_chunk || end_in_chunk) {
204 			/* trim chunk */
205 			chunk->ml_size -= MIN(chunk_end, rem_end) -
206 			    MAX(chunk_begin, rem_begin) + 1;
207 			if (rem_begin <= chunk_begin) {
208 				chunk->ml_address = rem_end + 1;
209 				break;
210 			}
211 			/* fall-through to next chunk */
212 		}
213 		prev = chunk;
214 		chunk = chunk->ml_next;
215 	}
216 
217 	return (0);
218 }
219 
220 /*
221  * find and claim a memory chunk of given size, first fit
222  */
223 uint64_t
pci_memlist_find(struct memlist ** listp,uint64_t size,int align)224 pci_memlist_find(struct memlist **listp, uint64_t size, int align)
225 {
226 	uint64_t delta, total_size;
227 	uint64_t paddr;
228 	struct memlist *prev = 0, *next;
229 
230 	/* find the chunk with sufficient size */
231 	next = *listp;
232 	while (next) {
233 		delta = next->ml_address & ((align != 0) ? (align - 1) : 0);
234 		if (delta != 0)
235 			total_size = size + align - delta;
236 		else
237 			total_size = size; /* the addr is already aligned */
238 		if (next->ml_size >= total_size)
239 			break;
240 		prev = next;
241 		next = prev->ml_next;
242 	}
243 
244 	if (next == 0)
245 		return (0);	/* Not found */
246 
247 	paddr = next->ml_address;
248 	if (delta)
249 		paddr += align - delta;
250 	(void) pci_memlist_remove(listp, paddr, size);
251 
252 	return (paddr);
253 }
254 
255 /*
256  * find and claim a memory chunk of given size, starting
257  * at a specified address
258  */
259 uint64_t
pci_memlist_find_with_startaddr(struct memlist ** listp,uint64_t address,uint64_t size,int align)260 pci_memlist_find_with_startaddr(struct memlist **listp, uint64_t address,
261     uint64_t size, int align)
262 {
263 	uint64_t delta, total_size;
264 	uint64_t paddr;
265 	struct memlist *next;
266 
267 	/* find the chunk starting at 'address' */
268 	next = *listp;
269 	while (next && (next->ml_address != address)) {
270 		next = next->ml_next;
271 	}
272 	if (next == 0)
273 		return (0);	/* Not found */
274 
275 	delta = next->ml_address & ((align != 0) ? (align - 1) : 0);
276 	if (delta != 0)
277 		total_size = size + align - delta;
278 	else
279 		total_size = size;	/* the addr is already aligned */
280 	if (next->ml_size < total_size)
281 		return (0);	/* unsufficient size */
282 
283 	paddr = next->ml_address;
284 	if (delta)
285 		paddr += align - delta;
286 	(void) pci_memlist_remove(listp, paddr, size);
287 
288 	return (paddr);
289 }
290 
291 /*
292  * Subsume memlist src into memlist dest
293  */
294 void
pci_memlist_subsume(struct memlist ** src,struct memlist ** dest)295 pci_memlist_subsume(struct memlist **src, struct memlist **dest)
296 {
297 	struct memlist *head, *prev;
298 
299 	head = *src;
300 	while (head) {
301 		pci_memlist_insert(dest, head->ml_address, head->ml_size);
302 		prev = head;
303 		head = head->ml_next;
304 		pci_memlist_free(prev);
305 	}
306 	*src = 0;
307 }
308 
309 /*
310  * Merge memlist src into memlist dest; don't destroy src
311  */
312 void
pci_memlist_merge(struct memlist ** src,struct memlist ** dest)313 pci_memlist_merge(struct memlist **src, struct memlist **dest)
314 {
315 	struct memlist *p;
316 
317 	p = *src;
318 	while (p) {
319 		pci_memlist_insert(dest, p->ml_address, p->ml_size);
320 		p = p->ml_next;
321 	}
322 }
323 
324 /*
325  * Make a copy of memlist
326  */
327 struct memlist *
pci_memlist_dup(struct memlist * listp)328 pci_memlist_dup(struct memlist *listp)
329 {
330 	struct memlist *head = 0, *prev = 0;
331 
332 	while (listp) {
333 		struct memlist *entry = pci_memlist_alloc();
334 		entry->ml_address = listp->ml_address;
335 		entry->ml_size = listp->ml_size;
336 		entry->ml_next = 0;
337 		if (prev)
338 			prev->ml_next = entry;
339 		else
340 			head = entry;
341 		prev = entry;
342 		listp = listp->ml_next;
343 	}
344 
345 	return (head);
346 }
347 
348 int
pci_memlist_count(struct memlist * listp)349 pci_memlist_count(struct memlist *listp)
350 {
351 	int count = 0;
352 	while (listp) {
353 		count++;
354 		listp = listp->ml_next;
355 	}
356 
357 	return (count);
358 }
359