kernel/os/memlist_new.c

   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 }