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 * 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 extern int pci_boot_debug; 44 #define dprintf if (pci_boot_debug) printf 45 46 void 47 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 * 59 memlist_alloc() 60 { 61 return ((struct memlist *)kmem_zalloc(sizeof (struct memlist), 62 KM_SLEEP)); 63 } 64 65 void 66 memlist_free(struct memlist *buf) 67 { 68 kmem_free(buf, sizeof (struct memlist)); 69 } 70 71 void 72 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 87 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 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 = 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 155 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 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 = 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 224 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) 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 260 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) memlist_remove(listp, paddr, size); 287 288 return (paddr); 289 } 290 291 /* 292 * Subsume memlist src into memlist dest 293 */ 294 void 295 memlist_subsume(struct memlist **src, struct memlist **dest) 296 { 297 struct memlist *head, *prev; 298 299 head = *src; 300 while (head) { 301 memlist_insert(dest, head->ml_address, head->ml_size); 302 prev = head; 303 head = head->ml_next; 304 memlist_free(prev); 305 } 306 *src = 0; 307 } 308 309 /* 310 * Merge memlist src into memlist dest; don't destroy src 311 */ 312 void 313 memlist_merge(struct memlist **src, struct memlist **dest) 314 { 315 struct memlist *p; 316 317 p = *src; 318 while (p) { 319 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 * 328 memlist_dup(struct memlist *listp) 329 { 330 struct memlist *head = 0, *prev = 0; 331 332 while (listp) { 333 struct memlist *entry = 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 349 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