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 #include <sys/types.h> 27 #include <sys/cmn_err.h> 28 #include <sys/mutex.h> 29 #include <sys/param.h> /* for NULL */ 30 #include <sys/debug.h> 31 #include <sys/memlist.h> 32 #include <sys/memlist_impl.h> 33 34 static struct memlist *memlist_freelist; 35 static uint_t memlist_freelist_count; 36 static kmutex_t memlist_freelist_mutex; 37 38 /* 39 * Caller must test for NULL return. 40 */ 41 struct memlist * 42 memlist_get_one(void) 43 { 44 struct memlist *mlp; 45 46 mutex_enter(&memlist_freelist_mutex); 47 mlp = memlist_freelist; 48 if (mlp != NULL) { 49 memlist_freelist = mlp->ml_next; 50 memlist_freelist_count--; 51 } 52 mutex_exit(&memlist_freelist_mutex); 53 54 return (mlp); 55 } 56 57 void 58 memlist_free_one(struct memlist *mlp) 59 { 60 ASSERT(mlp != NULL); 61 62 mutex_enter(&memlist_freelist_mutex); 63 mlp->ml_next = memlist_freelist; 64 memlist_freelist = mlp; 65 memlist_freelist_count++; 66 mutex_exit(&memlist_freelist_mutex); 67 } 68 69 void 70 memlist_free_list(struct memlist *mlp) 71 { 72 struct memlist *mlendp; 73 uint_t count; 74 75 if (mlp == NULL) { 76 return; 77 } 78 79 count = 1; 80 for (mlendp = mlp; mlendp->ml_next != NULL; mlendp = mlendp->ml_next) 81 count++; 82 mutex_enter(&memlist_freelist_mutex); 83 mlendp->ml_next = memlist_freelist; 84 memlist_freelist = mlp; 85 memlist_freelist_count += count; 86 mutex_exit(&memlist_freelist_mutex); 87 } 88 89 void 90 memlist_free_block(caddr_t base, size_t bytes) 91 { 92 struct memlist *mlp, *mlendp; 93 uint_t count; 94 95 count = bytes / sizeof (struct memlist); 96 if (count == 0) 97 return; 98 99 mlp = (struct memlist *)base; 100 mlendp = &mlp[count - 1]; 101 for (; mlp != mlendp; mlp++) 102 mlp->ml_next = mlp + 1; 103 mlendp->ml_next = NULL; 104 mlp = (struct memlist *)base; 105 mutex_enter(&memlist_freelist_mutex); 106 mlendp->ml_next = memlist_freelist; 107 memlist_freelist = mlp; 108 memlist_freelist_count += count; 109 mutex_exit(&memlist_freelist_mutex); 110 } 111 112 /* 113 * Insert into a sorted memory list. 114 * new = new element to insert 115 * curmemlistp = memory list to which to add segment. 116 */ 117 void 118 memlist_insert( 119 struct memlist *new, 120 struct memlist **curmemlistp) 121 { 122 struct memlist *cur, *last; 123 uint64_t start, end; 124 125 start = new->ml_address; 126 end = start + new->ml_size; 127 last = NULL; 128 for (cur = *curmemlistp; cur; cur = cur->ml_next) { 129 last = cur; 130 if (cur->ml_address >= end) { 131 new->ml_next = cur; 132 new->ml_prev = cur->ml_prev; 133 cur->ml_prev = new; 134 if (cur == *curmemlistp) 135 *curmemlistp = new; 136 else 137 new->ml_prev->ml_next = new; 138 return; 139 } 140 if (cur->ml_address + cur->ml_size > start) 141 panic("munged memory list = 0x%p\n", 142 (void *)curmemlistp); 143 } 144 new->ml_next = NULL; 145 new->ml_prev = last; 146 if (last != NULL) 147 last->ml_next = new; 148 } 149 150 void 151 memlist_del(struct memlist *memlistp, 152 struct memlist **curmemlistp) 153 { 154 #ifdef DEBUG 155 /* 156 * Check that the memlist is on the list. 157 */ 158 struct memlist *mlp; 159 160 for (mlp = *curmemlistp; mlp != NULL; mlp = mlp->ml_next) 161 if (mlp == memlistp) 162 break; 163 ASSERT(mlp == memlistp); 164 #endif /* DEBUG */ 165 if (*curmemlistp == memlistp) { 166 ASSERT(memlistp->ml_prev == NULL); 167 *curmemlistp = memlistp->ml_next; 168 } 169 if (memlistp->ml_prev != NULL) { 170 ASSERT(memlistp->ml_prev->ml_next == memlistp); 171 memlistp->ml_prev->ml_next = memlistp->ml_next; 172 } 173 if (memlistp->ml_next != NULL) { 174 ASSERT(memlistp->ml_next->ml_prev == memlistp); 175 memlistp->ml_next->ml_prev = memlistp->ml_prev; 176 } 177 } 178 179 struct memlist * 180 memlist_find(struct memlist *mlp, uint64_t address) 181 { 182 for (; mlp != NULL; mlp = mlp->ml_next) 183 if (address >= mlp->ml_address && 184 address < (mlp->ml_address + mlp->ml_size)) 185 break; 186 return (mlp); 187 } 188 189 /* 190 * Add a span to a memlist. 191 * Return: 192 * MEML_SPANOP_OK if OK. 193 * MEML_SPANOP_ESPAN if part or all of span already exists 194 * MEML_SPANOP_EALLOC for allocation failure 195 */ 196 int 197 memlist_add_span( 198 uint64_t address, 199 uint64_t bytes, 200 struct memlist **curmemlistp) 201 { 202 struct memlist *dst; 203 struct memlist *prev, *next; 204 205 /* 206 * allocate a new struct memlist 207 */ 208 209 dst = memlist_get_one(); 210 211 if (dst == NULL) { 212 return (MEML_SPANOP_EALLOC); 213 } 214 215 dst->ml_address = address; 216 dst->ml_size = bytes; 217 218 /* 219 * First insert. 220 */ 221 if (*curmemlistp == NULL) { 222 dst->ml_prev = NULL; 223 dst->ml_next = NULL; 224 *curmemlistp = dst; 225 return (MEML_SPANOP_OK); 226 } 227 228 /* 229 * Insert into sorted list. 230 */ 231 for (prev = NULL, next = *curmemlistp; next != NULL; 232 prev = next, next = next->ml_next) { 233 if (address > (next->ml_address + next->ml_size)) 234 continue; 235 236 /* 237 * Else insert here. 238 */ 239 240 /* 241 * Prepend to next. 242 */ 243 if ((address + bytes) == next->ml_address) { 244 memlist_free_one(dst); 245 246 next->ml_address = address; 247 next->ml_size += bytes; 248 249 return (MEML_SPANOP_OK); 250 } 251 252 /* 253 * Append to next. 254 */ 255 if (address == (next->ml_address + next->ml_size)) { 256 memlist_free_one(dst); 257 258 if (next->ml_next) { 259 /* 260 * don't overlap with next->ml_next 261 */ 262 if ((address + bytes) > 263 next->ml_next->ml_address) { 264 return (MEML_SPANOP_ESPAN); 265 } 266 /* 267 * Concatenate next and next->ml_next 268 */ 269 if ((address + bytes) == 270 next->ml_next->ml_address) { 271 struct memlist *mlp = next->ml_next; 272 273 if (next == *curmemlistp) 274 *curmemlistp = next->ml_next; 275 276 mlp->ml_address = next->ml_address; 277 mlp->ml_size += next->ml_size; 278 mlp->ml_size += bytes; 279 280 if (next->ml_prev) 281 next->ml_prev->ml_next = mlp; 282 mlp->ml_prev = next->ml_prev; 283 284 memlist_free_one(next); 285 return (MEML_SPANOP_OK); 286 } 287 } 288 289 next->ml_size += bytes; 290 291 return (MEML_SPANOP_OK); 292 } 293 294 /* don't overlap with next */ 295 if ((address + bytes) > next->ml_address) { 296 memlist_free_one(dst); 297 return (MEML_SPANOP_ESPAN); 298 } 299 300 /* 301 * Insert before next. 302 */ 303 dst->ml_prev = prev; 304 dst->ml_next = next; 305 next->ml_prev = dst; 306 if (prev == NULL) { 307 *curmemlistp = dst; 308 } else { 309 prev->ml_next = dst; 310 } 311 return (MEML_SPANOP_OK); 312 } 313 314 /* 315 * End of list, prev is valid and next is NULL. 316 */ 317 prev->ml_next = dst; 318 dst->ml_prev = prev; 319 dst->ml_next = NULL; 320 321 return (MEML_SPANOP_OK); 322 } 323 324 /* 325 * Delete a span from a memlist. 326 * Return: 327 * MEML_SPANOP_OK if OK. 328 * MEML_SPANOP_ESPAN if part or all of span does not exist 329 * MEML_SPANOP_EALLOC for allocation failure 330 */ 331 int 332 memlist_delete_span( 333 uint64_t address, 334 uint64_t bytes, 335 struct memlist **curmemlistp) 336 { 337 struct memlist *dst, *next; 338 339 /* 340 * Find element containing address. 341 */ 342 for (next = *curmemlistp; next != NULL; next = next->ml_next) { 343 if ((address >= next->ml_address) && 344 (address < next->ml_address + next->ml_size)) 345 break; 346 } 347 348 /* 349 * If start address not in list. 350 */ 351 if (next == NULL) { 352 return (MEML_SPANOP_ESPAN); 353 } 354 355 /* 356 * Error if size goes off end of this struct memlist. 357 */ 358 if (address + bytes > next->ml_address + next->ml_size) { 359 return (MEML_SPANOP_ESPAN); 360 } 361 362 /* 363 * Span at beginning of struct memlist. 364 */ 365 if (address == next->ml_address) { 366 /* 367 * If start & size match, delete from list. 368 */ 369 if (bytes == next->ml_size) { 370 if (next == *curmemlistp) 371 *curmemlistp = next->ml_next; 372 if (next->ml_prev != NULL) 373 next->ml_prev->ml_next = next->ml_next; 374 if (next->ml_next != NULL) 375 next->ml_next->ml_prev = next->ml_prev; 376 377 memlist_free_one(next); 378 } else { 379 /* 380 * Increment start address by bytes. 381 */ 382 next->ml_address += bytes; 383 next->ml_size -= bytes; 384 } 385 return (MEML_SPANOP_OK); 386 } 387 388 /* 389 * Span at end of struct memlist. 390 */ 391 if (address + bytes == next->ml_address + next->ml_size) { 392 /* 393 * decrement size by bytes 394 */ 395 next->ml_size -= bytes; 396 return (MEML_SPANOP_OK); 397 } 398 399 /* 400 * Delete a span in the middle of the struct memlist. 401 */ 402 { 403 /* 404 * create a new struct memlist 405 */ 406 dst = memlist_get_one(); 407 408 if (dst == NULL) { 409 return (MEML_SPANOP_EALLOC); 410 } 411 412 /* 413 * Existing struct memlist gets address 414 * and size up to start of span. 415 */ 416 dst->ml_address = address + bytes; 417 dst->ml_size = 418 (next->ml_address + next->ml_size) - dst->ml_address; 419 next->ml_size = address - next->ml_address; 420 421 /* 422 * New struct memlist gets address starting 423 * after span, until end. 424 */ 425 426 /* 427 * link in new memlist after old 428 */ 429 dst->ml_next = next->ml_next; 430 dst->ml_prev = next; 431 432 if (next->ml_next != NULL) 433 next->ml_next->ml_prev = dst; 434 next->ml_next = dst; 435 } 436 return (MEML_SPANOP_OK); 437 } 438