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 } else { 149 ASSERT3P(*curmemlistp, ==, NULL); 150 *curmemlistp = new; 151 } 152 } 153 154 void 155 memlist_del(struct memlist *memlistp, 156 struct memlist **curmemlistp) 157 { 158 #ifdef DEBUG 159 /* 160 * Check that the memlist is on the list. 161 */ 162 struct memlist *mlp; 163 164 for (mlp = *curmemlistp; mlp != NULL; mlp = mlp->ml_next) 165 if (mlp == memlistp) 166 break; 167 ASSERT(mlp == memlistp); 168 #endif /* DEBUG */ 169 if (*curmemlistp == memlistp) { 170 ASSERT(memlistp->ml_prev == NULL); 171 *curmemlistp = memlistp->ml_next; 172 } 173 if (memlistp->ml_prev != NULL) { 174 ASSERT(memlistp->ml_prev->ml_next == memlistp); 175 memlistp->ml_prev->ml_next = memlistp->ml_next; 176 } 177 if (memlistp->ml_next != NULL) { 178 ASSERT(memlistp->ml_next->ml_prev == memlistp); 179 memlistp->ml_next->ml_prev = memlistp->ml_prev; 180 } 181 } 182 183 struct memlist * 184 memlist_find(struct memlist *mlp, uint64_t address) 185 { 186 for (; mlp != NULL; mlp = mlp->ml_next) 187 if (address >= mlp->ml_address && 188 address < (mlp->ml_address + mlp->ml_size)) 189 break; 190 return (mlp); 191 } 192 193 /* 194 * Add a span to a memlist. 195 * Return: 196 * MEML_SPANOP_OK if OK. 197 * MEML_SPANOP_ESPAN if part or all of span already exists 198 * MEML_SPANOP_EALLOC for allocation failure 199 */ 200 int 201 memlist_add_span( 202 uint64_t address, 203 uint64_t bytes, 204 struct memlist **curmemlistp) 205 { 206 struct memlist *dst; 207 struct memlist *prev, *next; 208 209 /* 210 * allocate a new struct memlist 211 */ 212 213 dst = memlist_get_one(); 214 215 if (dst == NULL) { 216 return (MEML_SPANOP_EALLOC); 217 } 218 219 dst->ml_address = address; 220 dst->ml_size = bytes; 221 222 /* 223 * First insert. 224 */ 225 if (*curmemlistp == NULL) { 226 dst->ml_prev = NULL; 227 dst->ml_next = NULL; 228 *curmemlistp = dst; 229 return (MEML_SPANOP_OK); 230 } 231 232 /* 233 * Insert into sorted list. 234 */ 235 for (prev = NULL, next = *curmemlistp; next != NULL; 236 prev = next, next = next->ml_next) { 237 if (address > (next->ml_address + next->ml_size)) 238 continue; 239 240 /* 241 * Else insert here. 242 */ 243 244 /* 245 * Prepend to next. 246 */ 247 if ((address + bytes) == next->ml_address) { 248 memlist_free_one(dst); 249 250 next->ml_address = address; 251 next->ml_size += bytes; 252 253 return (MEML_SPANOP_OK); 254 } 255 256 /* 257 * Append to next. 258 */ 259 if (address == (next->ml_address + next->ml_size)) { 260 memlist_free_one(dst); 261 262 if (next->ml_next) { 263 /* 264 * don't overlap with next->ml_next 265 */ 266 if ((address + bytes) > 267 next->ml_next->ml_address) { 268 return (MEML_SPANOP_ESPAN); 269 } 270 /* 271 * Concatenate next and next->ml_next 272 */ 273 if ((address + bytes) == 274 next->ml_next->ml_address) { 275 struct memlist *mlp = next->ml_next; 276 277 if (next == *curmemlistp) 278 *curmemlistp = next->ml_next; 279 280 mlp->ml_address = next->ml_address; 281 mlp->ml_size += next->ml_size; 282 mlp->ml_size += bytes; 283 284 if (next->ml_prev) 285 next->ml_prev->ml_next = mlp; 286 mlp->ml_prev = next->ml_prev; 287 288 memlist_free_one(next); 289 return (MEML_SPANOP_OK); 290 } 291 } 292 293 next->ml_size += bytes; 294 295 return (MEML_SPANOP_OK); 296 } 297 298 /* don't overlap with next */ 299 if ((address + bytes) > next->ml_address) { 300 memlist_free_one(dst); 301 return (MEML_SPANOP_ESPAN); 302 } 303 304 /* 305 * Insert before next. 306 */ 307 dst->ml_prev = prev; 308 dst->ml_next = next; 309 next->ml_prev = dst; 310 if (prev == NULL) { 311 *curmemlistp = dst; 312 } else { 313 prev->ml_next = dst; 314 } 315 return (MEML_SPANOP_OK); 316 } 317 318 /* 319 * End of list, prev is valid and next is NULL. 320 */ 321 prev->ml_next = dst; 322 dst->ml_prev = prev; 323 dst->ml_next = NULL; 324 325 return (MEML_SPANOP_OK); 326 } 327 328 /* 329 * Delete a span from a memlist. 330 * Return: 331 * MEML_SPANOP_OK if OK. 332 * MEML_SPANOP_ESPAN if part or all of span does not exist 333 * MEML_SPANOP_EALLOC for allocation failure 334 */ 335 int 336 memlist_delete_span( 337 uint64_t address, 338 uint64_t bytes, 339 struct memlist **curmemlistp) 340 { 341 struct memlist *dst, *next; 342 343 /* 344 * Find element containing address. 345 */ 346 for (next = *curmemlistp; next != NULL; next = next->ml_next) { 347 if ((address >= next->ml_address) && 348 (address < next->ml_address + next->ml_size)) 349 break; 350 } 351 352 /* 353 * If start address not in list. 354 */ 355 if (next == NULL) { 356 return (MEML_SPANOP_ESPAN); 357 } 358 359 /* 360 * Error if size goes off end of this struct memlist. 361 */ 362 if (address + bytes > next->ml_address + next->ml_size) { 363 return (MEML_SPANOP_ESPAN); 364 } 365 366 /* 367 * Span at beginning of struct memlist. 368 */ 369 if (address == next->ml_address) { 370 /* 371 * If start & size match, delete from list. 372 */ 373 if (bytes == next->ml_size) { 374 if (next == *curmemlistp) 375 *curmemlistp = next->ml_next; 376 if (next->ml_prev != NULL) 377 next->ml_prev->ml_next = next->ml_next; 378 if (next->ml_next != NULL) 379 next->ml_next->ml_prev = next->ml_prev; 380 381 memlist_free_one(next); 382 } else { 383 /* 384 * Increment start address by bytes. 385 */ 386 next->ml_address += bytes; 387 next->ml_size -= bytes; 388 } 389 return (MEML_SPANOP_OK); 390 } 391 392 /* 393 * Span at end of struct memlist. 394 */ 395 if (address + bytes == next->ml_address + next->ml_size) { 396 /* 397 * decrement size by bytes 398 */ 399 next->ml_size -= bytes; 400 return (MEML_SPANOP_OK); 401 } 402 403 /* 404 * Delete a span in the middle of the struct memlist. 405 */ 406 { 407 /* 408 * create a new struct memlist 409 */ 410 dst = memlist_get_one(); 411 412 if (dst == NULL) { 413 return (MEML_SPANOP_EALLOC); 414 } 415 416 /* 417 * Existing struct memlist gets address 418 * and size up to start of span. 419 */ 420 dst->ml_address = address + bytes; 421 dst->ml_size = 422 (next->ml_address + next->ml_size) - dst->ml_address; 423 next->ml_size = address - next->ml_address; 424 425 /* 426 * New struct memlist gets address starting 427 * after span, until end. 428 */ 429 430 /* 431 * link in new memlist after old 432 */ 433 dst->ml_next = next->ml_next; 434 dst->ml_prev = next; 435 436 if (next->ml_next != NULL) 437 next->ml_next->ml_prev = dst; 438 next->ml_next = dst; 439 } 440 return (MEML_SPANOP_OK); 441 } 442