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, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 #pragma ident "%Z%%M% %I% %E% SMI" 28 29 #include <sys/types.h> 30 #include <sys/cmn_err.h> 31 #include <sys/mutex.h> 32 #include <sys/param.h> /* for NULL */ 33 #include <sys/debug.h> 34 #include <sys/memlist.h> 35 #include <sys/memlist_impl.h> 36 37 static struct memlist *memlist_freelist; 38 static uint_t memlist_freelist_count; 39 static kmutex_t memlist_freelist_mutex; 40 41 /* 42 * Caller must test for NULL return. 43 */ 44 struct memlist * 45 memlist_get_one(void) 46 { 47 struct memlist *mlp; 48 49 mutex_enter(&memlist_freelist_mutex); 50 mlp = memlist_freelist; 51 if (mlp != NULL) { 52 memlist_freelist = mlp->next; 53 memlist_freelist_count--; 54 } 55 mutex_exit(&memlist_freelist_mutex); 56 57 return (mlp); 58 } 59 60 void 61 memlist_free_one(struct memlist *mlp) 62 { 63 ASSERT(mlp != NULL); 64 65 mutex_enter(&memlist_freelist_mutex); 66 mlp->next = memlist_freelist; 67 memlist_freelist = mlp; 68 memlist_freelist_count++; 69 mutex_exit(&memlist_freelist_mutex); 70 } 71 72 void 73 memlist_free_list(struct memlist *mlp) 74 { 75 struct memlist *mlendp; 76 uint_t count; 77 78 if (mlp == NULL) { 79 return; 80 } 81 82 count = 1; 83 for (mlendp = mlp; mlendp->next != NULL; mlendp = mlendp->next) 84 count++; 85 mutex_enter(&memlist_freelist_mutex); 86 mlendp->next = memlist_freelist; 87 memlist_freelist = mlp; 88 memlist_freelist_count += count; 89 mutex_exit(&memlist_freelist_mutex); 90 } 91 92 void 93 memlist_free_block(caddr_t base, size_t bytes) 94 { 95 struct memlist *mlp, *mlendp; 96 uint_t count; 97 98 count = bytes / sizeof (struct memlist); 99 if (count == 0) 100 return; 101 102 mlp = (struct memlist *)base; 103 mlendp = &mlp[count - 1]; 104 for (; mlp != mlendp; mlp++) 105 mlp->next = mlp + 1; 106 mlendp->next = NULL; 107 mlp = (struct memlist *)base; 108 mutex_enter(&memlist_freelist_mutex); 109 mlendp->next = memlist_freelist; 110 memlist_freelist = mlp; 111 memlist_freelist_count += count; 112 mutex_exit(&memlist_freelist_mutex); 113 } 114 115 /* 116 * Insert into a sorted memory list. 117 * new = new element to insert 118 * curmemlistp = memory list to which to add segment. 119 */ 120 void 121 memlist_insert( 122 struct memlist *new, 123 struct memlist **curmemlistp) 124 { 125 struct memlist *cur, *last; 126 uint64_t start, end; 127 128 start = new->address; 129 end = start + new->size; 130 last = NULL; 131 for (cur = *curmemlistp; cur; cur = cur->next) { 132 last = cur; 133 if (cur->address >= end) { 134 new->next = cur; 135 new->prev = cur->prev; 136 cur->prev = new; 137 if (cur == *curmemlistp) 138 *curmemlistp = new; 139 else 140 new->prev->next = new; 141 return; 142 } 143 if (cur->address + cur->size > start) 144 panic("munged memory list = 0x%p\n", 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