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 /* 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 40 extern int pci_boot_debug; 41 #define dprintf if (pci_boot_debug) printf 42 43 void 44 memlist_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->address >> 32), (int)listp->address, 50 (int)(listp->size >> 32), (int)listp->size); 51 listp = listp->next; 52 } 53 } 54 55 struct memlist * 56 memlist_alloc() 57 { 58 return ((struct memlist *)kmem_zalloc(sizeof (struct memlist), 59 KM_SLEEP)); 60 } 61 62 void 63 memlist_free(struct memlist *buf) 64 { 65 kmem_free(buf, sizeof (struct memlist)); 66 } 67 68 void 69 memlist_free_all(struct memlist **list) 70 { 71 struct memlist *next, *buf; 72 73 next = *list; 74 while (next) { 75 buf = next; 76 next = buf->next; 77 kmem_free(buf, sizeof (struct memlist)); 78 } 79 *list = 0; 80 } 81 82 /* insert in the order of addresses */ 83 void 84 memlist_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->address < addr) { 93 prev = next; 94 next = prev->next; 95 } 96 97 merge_left = (prev && addr == prev->address + prev->size); 98 merge_right = (next && addr + size == next->address); 99 if (merge_left && merge_right) { 100 prev->size += size + next->size; 101 prev->next = next->next; 102 memlist_free(next); 103 return; 104 } 105 106 if (merge_left) { 107 prev->size += size; 108 return; 109 } 110 111 if (merge_right) { 112 next->address = addr; 113 next->size += size; 114 return; 115 } 116 117 entry = memlist_alloc(); 118 entry->address = addr; 119 entry->size = size; 120 if (prev == 0) { 121 entry->next = *listp; 122 *listp = entry; 123 } else { 124 entry->next = next; 125 prev->next = entry; 126 } 127 } 128 129 /* 130 * Delete memlist entries, assuming list sorted by address 131 */ 132 133 #define MIN(a, b) ((a) < (b) ? (a) : (b)) 134 #define MAX(a, b) ((a) > (b) ? (a) : (b)) 135 #define IN_RANGE(a, b, e) ((a) >= (b) && (a) <= (e)) 136 137 int 138 memlist_remove(struct memlist **listp, uint64_t addr, uint64_t size) 139 { 140 struct memlist *prev = 0; 141 struct memlist *chunk; 142 uint64_t rem_begin, rem_end; 143 uint64_t chunk_begin, chunk_end; 144 int begin_in_chunk, end_in_chunk; 145 146 147 /* ignore removal of zero-length item */ 148 if (size == 0) 149 return (0); 150 151 /* also inherently ignore a zero-length list */ 152 rem_begin = addr; 153 rem_end = addr + size - 1; 154 chunk = *listp; 155 while (chunk) { 156 chunk_begin = chunk->address; 157 chunk_end = chunk->address + chunk->size - 1; 158 begin_in_chunk = IN_RANGE(rem_begin, chunk_begin, chunk_end); 159 end_in_chunk = IN_RANGE(rem_end, chunk_begin, chunk_end); 160 161 if (rem_begin <= chunk_begin && rem_end >= chunk_end) { 162 struct memlist *delete_chunk; 163 164 /* spans entire chunk - delete chunk */ 165 delete_chunk = chunk; 166 if (prev == 0) 167 chunk = *listp = chunk->next; 168 else 169 chunk = prev->next = chunk->next; 170 171 memlist_free(delete_chunk); 172 /* skip to start of while-loop */ 173 continue; 174 } else if (begin_in_chunk && end_in_chunk && 175 chunk_begin != rem_begin && chunk_end != rem_end) { 176 struct memlist *new; 177 /* split chunk */ 178 new = memlist_alloc(); 179 new->address = rem_end + 1; 180 new->size = chunk_end - new->address + 1; 181 chunk->size = rem_begin - chunk_begin; 182 new->next = chunk->next; 183 chunk->next = new; 184 /* done - break out of while-loop */ 185 break; 186 } else if (begin_in_chunk || end_in_chunk) { 187 /* trim chunk */ 188 chunk->size -= MIN(chunk_end, rem_end) - 189 MAX(chunk_begin, rem_begin) + 1; 190 if (rem_begin <= chunk_begin) { 191 chunk->address = rem_end + 1; 192 break; 193 } 194 /* fall-through to next chunk */ 195 } 196 prev = chunk; 197 chunk = chunk->next; 198 } 199 200 return (0); 201 } 202 203 /* 204 * find and claim a memory chunk of given size, first fit 205 */ 206 uint64_t 207 memlist_find(struct memlist **listp, uint64_t size, int align) 208 { 209 uint64_t delta, total_size; 210 uint64_t paddr; 211 struct memlist *prev = 0, *next; 212 213 /* find the chunk with sufficient size */ 214 next = *listp; 215 while (next) { 216 delta = next->address & ((align != 0) ? (align - 1) : 0); 217 if (delta != 0) 218 total_size = size + align - delta; 219 else 220 total_size = size; /* the addr is already aligned */ 221 if (next->size >= total_size) 222 break; 223 prev = next; 224 next = prev->next; 225 } 226 227 if (next == 0) 228 return (0); /* Not found */ 229 230 paddr = next->address; 231 if (delta) 232 paddr += align - delta; 233 (void) memlist_remove(listp, paddr, size); 234 235 return (paddr); 236 } 237 238 /* 239 * find and claim a memory chunk of given size, starting 240 * at a specified address 241 */ 242 uint64_t 243 memlist_find_with_startaddr(struct memlist **listp, uint64_t address, 244 uint64_t size, int align) 245 { 246 uint64_t delta, total_size; 247 uint64_t paddr; 248 struct memlist *next; 249 250 /* find the chunk starting at 'address' */ 251 next = *listp; 252 while (next && (next->address != address)) { 253 next = next->next; 254 } 255 if (next == 0) 256 return (0); /* Not found */ 257 258 delta = next->address & ((align != 0) ? (align - 1) : 0); 259 if (delta != 0) 260 total_size = size + align - delta; 261 else 262 total_size = size; /* the addr is already aligned */ 263 if (next->size < total_size) 264 return (0); /* unsufficient size */ 265 266 paddr = next->address; 267 if (delta) 268 paddr += align - delta; 269 (void) memlist_remove(listp, paddr, size); 270 271 return (paddr); 272 } 273 274 /* 275 * Merge memlist src into memlist dest 276 */ 277 void 278 memlist_merge(struct memlist **src, struct memlist **dest) 279 { 280 struct memlist *head, *prev; 281 282 head = *src; 283 while (head) { 284 memlist_insert(dest, head->address, head->size); 285 prev = head; 286 head = head->next; 287 memlist_free(prev); 288 } 289 *src = 0; 290 } 291 292 /* 293 * Make a copy of memlist 294 */ 295 struct memlist * 296 memlist_dup(struct memlist *listp) 297 { 298 struct memlist *head = 0, *prev = 0; 299 300 while (listp) { 301 struct memlist *entry = memlist_alloc(); 302 entry->address = listp->address; 303 entry->size = listp->size; 304 entry->next = 0; 305 if (prev) 306 prev->next = entry; 307 else 308 head = entry; 309 prev = entry; 310 listp = listp->next; 311 } 312 313 return (head); 314 } 315 316 int 317 memlist_count(struct memlist *listp) 318 { 319 int count = 0; 320 while (listp) { 321 count++; 322 listp = listp->next; 323 } 324 325 return (count); 326 } 327