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