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 /* 29 * XXX This stuff should be in usr/src/common, to be shared by boot 30 * code, kernel DR, and busra stuff. 31 * 32 * NOTE: We are only using the next-> link. The prev-> link is 33 * not used in the implementation. 34 */ 35 #include <sys/types.h> 36 #include <sys/memlist.h> 37 #include <sys/kmem.h> 38 #include <sys/cmn_err.h> 39 #include <sys/pci_impl.h> 40 #include <sys/debug.h> 41 42 extern int pci_boot_debug; 43 #define dprintf if (pci_boot_debug) printf 44 45 void 46 memlist_dump(struct memlist *listp) 47 { 48 dprintf("memlist 0x%p content", (void *)listp); 49 while (listp) { 50 dprintf("(0x%x%x, 0x%x%x)", 51 (int)(listp->address >> 32), (int)listp->address, 52 (int)(listp->size >> 32), (int)listp->size); 53 listp = listp->next; 54 } 55 } 56 57 struct memlist * 58 memlist_alloc() 59 { 60 return ((struct memlist *)kmem_zalloc(sizeof (struct memlist), 61 KM_SLEEP)); 62 } 63 64 void 65 memlist_free(struct memlist *buf) 66 { 67 kmem_free(buf, sizeof (struct memlist)); 68 } 69 70 void 71 memlist_free_all(struct memlist **list) 72 { 73 struct memlist *next, *buf; 74 75 next = *list; 76 while (next) { 77 buf = next; 78 next = buf->next; 79 kmem_free(buf, sizeof (struct memlist)); 80 } 81 *list = 0; 82 } 83 84 /* insert in the order of addresses */ 85 void 86 memlist_insert(struct memlist **listp, uint64_t addr, uint64_t size) 87 { 88 int merge_left, merge_right; 89 struct memlist *entry; 90 struct memlist *prev = 0, *next; 91 92 /* find the location in list */ 93 next = *listp; 94 while (next && next->address < addr) { 95 prev = next; 96 next = prev->next; 97 } 98 99 merge_left = (prev && addr == prev->address + prev->size); 100 merge_right = (next && addr + size == next->address); 101 if (merge_left && merge_right) { 102 prev->size += size + next->size; 103 prev->next = next->next; 104 memlist_free(next); 105 return; 106 } 107 108 if (merge_left) { 109 prev->size += size; 110 return; 111 } 112 113 if (merge_right) { 114 next->address = addr; 115 next->size += size; 116 return; 117 } 118 119 entry = memlist_alloc(); 120 entry->address = addr; 121 entry->size = size; 122 if (prev == 0) { 123 entry->next = *listp; 124 *listp = entry; 125 } else { 126 entry->next = next; 127 prev->next = entry; 128 } 129 } 130 131 /* 132 * Delete memory chunks, assuming list sorted by address 133 */ 134 int 135 memlist_remove(struct memlist **listp, uint64_t addr, uint64_t size) 136 { 137 struct memlist *entry; 138 struct memlist *prev = 0, *next; 139 140 /* a remove can't be done on an empty list */ 141 ASSERT(*listp); 142 143 /* find the location in list */ 144 next = *listp; 145 while (next && (next->address + next->size < addr)) { 146 prev = next; 147 next = prev->next; 148 } 149 150 if (next == 0 || (addr < next->address)) { 151 dprintf("memlist_remove: addr 0x%x%x, size 0x%x%x" 152 " not contained in list\n", 153 (int)(addr >> 32), (int)addr, 154 (int)(size >> 32), (int)size); 155 memlist_dump(*listp); 156 return (-1); 157 } 158 159 if (addr > next->address) { 160 uint64_t oldsize = next->size; 161 next->size = addr - next->address; 162 if ((next->address + oldsize) > (addr + size)) { 163 entry = memlist_alloc(); 164 entry->address = addr + size; 165 entry->size = next->address + oldsize - addr - size; 166 entry->next = next->next; 167 next->next = entry; 168 } 169 } else if ((next->address + next->size) > (addr + size)) { 170 /* addr == next->address */ 171 next->address = addr + size; 172 next->size -= size; 173 } else { 174 /* the entire chunk is deleted */ 175 if (prev == 0) { 176 *listp = next->next; 177 } else { 178 prev->next = next->next; 179 } 180 memlist_free(next); 181 } 182 return (0); 183 } 184 185 /* 186 * find and claim a memory chunk of given size, first fit 187 */ 188 uint64_t 189 memlist_find(struct memlist **listp, uint64_t size, int align) 190 { 191 uint64_t delta, total_size; 192 uint64_t paddr; 193 struct memlist *prev = 0, *next; 194 195 /* find the chunk with sufficient size */ 196 next = *listp; 197 while (next) { 198 delta = next->address & ((align != 0) ? (align - 1) : 0); 199 if (delta != 0) 200 total_size = size + align - delta; 201 else 202 total_size = size; /* the addr is already aligned */ 203 if (next->size >= total_size) 204 break; 205 prev = next; 206 next = prev->next; 207 } 208 209 if (next == 0) 210 return (0); /* Not found */ 211 212 paddr = next->address; 213 if (delta) 214 paddr += align - delta; 215 (void) memlist_remove(listp, paddr, size); 216 217 return (paddr); 218 } 219 220 /* 221 * find and claim a memory chunk of given size, starting 222 * at a specified address 223 */ 224 uint64_t 225 memlist_find_with_startaddr(struct memlist **listp, uint64_t address, 226 uint64_t size, int align) 227 { 228 uint64_t delta, total_size; 229 uint64_t paddr; 230 struct memlist *next; 231 232 /* find the chunk starting at 'address' */ 233 next = *listp; 234 while (next && (next->address != address)) { 235 next = next->next; 236 } 237 if (next == 0) 238 return (0); /* Not found */ 239 240 delta = next->address & ((align != 0) ? (align - 1) : 0); 241 if (delta != 0) 242 total_size = size + align - delta; 243 else 244 total_size = size; /* the addr is already aligned */ 245 if (next->size < total_size) 246 return (0); /* unsufficient size */ 247 248 paddr = next->address; 249 if (delta) 250 paddr += align - delta; 251 (void) memlist_remove(listp, paddr, size); 252 253 return (paddr); 254 } 255 256 /* 257 * Merge memlist src into memlist dest 258 */ 259 void 260 memlist_merge(struct memlist **src, struct memlist **dest) 261 { 262 struct memlist *head, *prev; 263 264 head = *src; 265 while (head) { 266 memlist_insert(dest, head->address, head->size); 267 prev = head; 268 head = head->next; 269 memlist_free(prev); 270 } 271 *src = 0; 272 } 273 274 /* 275 * Make a copy of memlist 276 */ 277 struct memlist * 278 memlist_dup(struct memlist *listp) 279 { 280 struct memlist *head = 0, *prev = 0; 281 282 while (listp) { 283 struct memlist *entry = memlist_alloc(); 284 entry->address = listp->address; 285 entry->size = listp->size; 286 entry->next = 0; 287 if (prev) 288 prev->next = entry; 289 else 290 head = entry; 291 prev = entry; 292 listp = listp->next; 293 } 294 295 return (head); 296 } 297 298 int 299 memlist_count(struct memlist *listp) 300 { 301 int count = 0; 302 while (listp) { 303 count++; 304 listp = listp->next; 305 } 306 307 return (count); 308 } 309