libkern/kxld/kxld_array.c

   1 /*
   2  * Copyright (c) 2008 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 #include <string.h>
  29
  30 #if KERNEL
  31     #include <mach/vm_param.h>
  32 #else
  33     #include <mach/mach_init.h>
  34 #endif
  35
  36 #define DEBUG_ASSERT_COMPONENT_NAME_STRING "kxld"
  37 #include <AssertMacros.h>
  38
  39 #include "kxld_array.h"
  40 #include "kxld_util.h"
  41
  42 static kern_return_t array_init(KXLDArray *array, size_t itemsize, u_int nitems);
  43 static KXLDArrayPool * pool_create(size_t capacity);
  44 static void pool_destroy(KXLDArrayPool *pool, size_t capacity);
  45 static u_int reinit_pools(KXLDArray *array, u_int nitems);
  46
  47 /*******************************************************************************
  48 *******************************************************************************/
  49 kern_return_t
  50 kxld_array_init(KXLDArray *array, size_t itemsize, u_int nitems)
  51 {
  52         kern_return_t rval = KERN_FAILURE;
  53         KXLDArrayPool *dstpool = NULL, *srcpool = NULL, *tmp = NULL;
  54         KXLDArrayHead srcpools = STAILQ_HEAD_INITIALIZER(srcpools);
  55         size_t srcpool_capacity = 0;
  56         u_long offset = 0;
  57
  58         check(array);
  59
  60         if (!nitems) {
  61                 kxld_array_reset(array);
  62                 rval = KERN_SUCCESS;
  63                 goto finish;
  64         }
  65
  66         require_action(itemsize, finish, rval = KERN_INVALID_ARGUMENT);
  67
  68         /* If the array has some pools, we need to see if there is enough space in
  69          * those pools to accomodate the requested size array.  If there isn't
  70          * enough space, we save the existing pools to a temporary STAILQ and zero
  71          * out the array structure.  This will cause a new pool of sufficient size
  72          * to be created, and we then copy the data from the old pools into the new
  73          * pool.
  74          */
  75         if (array->npools) {
  76                 /* Update the array's maxitems based on the new itemsize */
  77                 array->pool_maxitems = (u_int) (array->pool_capacity / itemsize);
  78                 array->maxitems = 0;
  79                 STAILQ_FOREACH(srcpool, &array->pools, entries) {
  80                         array->maxitems += array->pool_maxitems;
  81                 }
  82
  83                 /* If there's not enough space, save the pools to a temporary STAILQ
  84                  * and zero out the array structure.  Otherwise, rescan the pools to
  85                  * update their internal nitems counts.
  86                  */
  87                 if (array->maxitems < nitems) {
  88                         STAILQ_FOREACH_SAFE(srcpool, &array->pools, entries, tmp) {
  89                                 STAILQ_REMOVE(&array->pools, srcpool, kxld_array_pool, entries);
  90                                 STAILQ_INSERT_TAIL(&srcpools, srcpool, entries);
  91                         }
  92                         srcpool_capacity = array->pool_capacity;
  93                         bzero(array, sizeof(*array));
  94                 } else {
  95                         nitems = reinit_pools(array, nitems);
  96                         require_action(nitems == 0, finish, rval = KERN_FAILURE);
  97                 }
  98         }
  99
 100         array->itemsize = itemsize;
 101
 102         /* If array->maxitems is zero, it means we are either rebuilding an array
 103          * that was too small, or we're initializing an array for the first time.
 104          * In either case, we need to set up a pool of the requested size, and
 105          * if we're rebuilding an old array, we'll also copy the data from the old
 106          * pools into the new pool.
 107          */
 108         if (array->maxitems == 0) {
 109                 rval = array_init(array, itemsize, nitems);
 110                 require_noerr(rval, finish);
 111
 112                 dstpool = STAILQ_FIRST(&array->pools);
 113                 require_action(dstpool, finish, rval = KERN_FAILURE);
 114
 115                 STAILQ_FOREACH_SAFE(srcpool, &srcpools, entries, tmp) {
 116                         memcpy(dstpool->buffer + offset, srcpool->buffer, srcpool_capacity);
 117                         offset += srcpool_capacity;
 118
 119                         STAILQ_REMOVE(&srcpools, srcpool, kxld_array_pool, entries);
 120                         pool_destroy(srcpool, srcpool_capacity);
 121                 }
 122         }
 123
 124         rval = KERN_SUCCESS;
 125 finish:
 126         if (rval) {
 127                 kxld_array_deinit(array);
 128         }
 129         return rval;
 130 }
 131
 132 /*******************************************************************************
 133 * This may only be called to initialize (or reinitialize) an array with exactly
 134 * zero or one pool.  Calling this on an array with more than one pool is an
 135 * error.
 136 *******************************************************************************/
 137 static kern_return_t
 138 array_init(KXLDArray *array, size_t itemsize, u_int nitems)
 139 {
 140         kern_return_t rval = KERN_FAILURE;
 141         KXLDArrayPool *pool = NULL;
 142
 143         require_action(itemsize, finish, rval = KERN_INVALID_ARGUMENT);
 144         require_action(array->npools < 2, finish, rval = KERN_INVALID_ARGUMENT);
 145
 146         array->itemsize = itemsize;
 147
 148         pool = STAILQ_FIRST(&array->pools);
 149         if (pool) {
 150                 require_action(itemsize * nitems < array->pool_capacity,
 151                     finish, rval = KERN_FAILURE);
 152                 require_action(array->npools == 1, finish, rval = KERN_FAILURE);
 153                 bzero(pool->buffer, array->pool_capacity);
 154         } else {
 155                 array->pool_capacity = round_page(array->itemsize * nitems);
 156
 157                 pool = pool_create(array->pool_capacity);
 158                 require_action(pool, finish, rval = KERN_RESOURCE_SHORTAGE);
 159                 STAILQ_INSERT_HEAD(&array->pools, pool, entries);
 160         }
 161         pool->nitems = nitems;
 162
 163         array->pool_maxitems = (u_int) (array->pool_capacity / array->itemsize);
 164         array->maxitems = array->pool_maxitems;
 165         array->nitems = nitems;
 166         array->npools = 1;
 167
 168         rval = KERN_SUCCESS;
 169 finish:
 170         return rval;
 171 }
 172
 173 /*******************************************************************************
 174 *******************************************************************************/
 175 static KXLDArrayPool *
 176 pool_create(size_t capacity)
 177 {
 178         KXLDArrayPool *pool = NULL, *rval = NULL;
 179
 180         pool = kxld_calloc(sizeof(*pool));
 181         require(pool, finish);
 182
 183         pool->buffer = kxld_page_alloc(capacity);
 184         require(pool->buffer, finish);
 185
 186         rval = pool;
 187         pool = NULL;
 188
 189 finish:
 190         if (pool) {
 191                 pool_destroy(pool, capacity);
 192         }
 193         return rval;
 194 }
 195
 196 /*******************************************************************************
 197 *******************************************************************************/
 198 static void
 199 pool_destroy(KXLDArrayPool *pool, size_t capacity)
 200 {
 201         if (pool) {
 202                 if (pool->buffer) {
 203                         kxld_page_free(pool->buffer, capacity);
 204                 }
 205                 kxld_free(pool, sizeof(*pool));
 206         }
 207 }
 208
 209 /*******************************************************************************
 210 *******************************************************************************/
 211 kern_return_t
 212 kxld_array_copy(KXLDArray *dstarray, const KXLDArray *srcarray)
 213 {
 214         kern_return_t rval = KERN_FAILURE;
 215         KXLDArrayPool *dstpool = NULL, *srcpool = NULL;
 216         u_long needed_capacity = 0;
 217         u_long current_capacity = 0;
 218         u_long copysize = 0;
 219         u_long offset = 0;
 220
 221         check(dstarray);
 222         check(srcarray);
 223
 224         /* When copying array, we only want to copy to an array with a single
 225          * pool.  If the array has more than one pool or the array is too small,
 226          * we destroy the array and build it from scratch for the copy.
 227          */
 228         needed_capacity = round_page(srcarray->nitems * srcarray->itemsize);
 229         current_capacity = dstarray->npools * dstarray->pool_capacity;
 230         if (dstarray->npools > 1 || needed_capacity > current_capacity) {
 231                 kxld_array_deinit(dstarray);
 232         }
 233
 234         rval = array_init(dstarray, srcarray->itemsize, srcarray->nitems);
 235         require_noerr(rval, finish);
 236
 237         dstpool = STAILQ_FIRST(&dstarray->pools);
 238         require_action(dstpool, finish, rval = KERN_FAILURE);
 239
 240         /* Copy the data from the source pools to the single destination pool. */
 241         STAILQ_FOREACH(srcpool, &srcarray->pools, entries) {
 242                 copysize = srcpool->nitems * srcarray->itemsize;
 243                 memcpy(dstpool->buffer + offset, srcpool->buffer, copysize);
 244                 offset += copysize;
 245         }
 246
 247         rval = KERN_SUCCESS;
 248 finish:
 249         return rval;
 250 }
 251
 252 /*******************************************************************************
 253 *******************************************************************************/
 254 void
 255 kxld_array_reset(KXLDArray *array)
 256 {
 257         KXLDArrayPool *pool = NULL;
 258
 259         if (array) {
 260                 STAILQ_FOREACH(pool, &array->pools, entries) {
 261                         pool->nitems = 0;
 262                 }
 263                 array->nitems = 0;
 264         }
 265 }
 266
 267 /*******************************************************************************
 268 *******************************************************************************/
 269 void
 270 kxld_array_clear(KXLDArray *array)
 271 {
 272         KXLDArrayPool *pool = NULL;
 273
 274         if (array) {
 275                 kxld_array_reset(array);
 276                 STAILQ_FOREACH(pool, &array->pools, entries) {
 277                         bzero(pool->buffer, array->pool_capacity);
 278                 }
 279         }
 280 }
 281
 282 /*******************************************************************************
 283 *******************************************************************************/
 284 void
 285 kxld_array_deinit(KXLDArray *array)
 286 {
 287         KXLDArrayPool *pool = NULL, *tmp = NULL;
 288
 289         if (array) {
 290                 STAILQ_FOREACH_SAFE(pool, &array->pools, entries, tmp) {
 291                         STAILQ_REMOVE(&array->pools, pool, kxld_array_pool, entries);
 292                         pool_destroy(pool, array->pool_capacity);
 293                 }
 294                 bzero(array, sizeof(*array));
 295         }
 296 }
 297
 298 /*******************************************************************************
 299 *******************************************************************************/
 300 void *
 301 kxld_array_get_item(const KXLDArray *array, u_int idx)
 302 {
 303         KXLDArrayPool *pool = NULL;
 304         void *item = NULL;
 305
 306         check(array);
 307
 308         if (idx >= array->nitems) {
 309                 goto finish;
 310         }
 311
 312         STAILQ_FOREACH(pool, &array->pools, entries) {
 313                 if (idx < pool->nitems) {
 314                         item = (void *) (pool->buffer + (array->itemsize * idx));
 315                         break;
 316                 }
 317
 318                 idx -= array->pool_maxitems;
 319         }
 320
 321 finish:
 322         return item;
 323 }
 324
 325 /*******************************************************************************
 326 *******************************************************************************/
 327 void *
 328 kxld_array_get_slot(const KXLDArray *array, u_int idx)
 329 {
 330         KXLDArrayPool *pool = NULL;
 331         void *item = NULL;
 332
 333         check(array);
 334
 335         if (idx >= array->maxitems) {
 336                 goto finish;
 337         }
 338
 339         STAILQ_FOREACH(pool, &array->pools, entries) {
 340                 if (idx < array->pool_maxitems) {
 341                         item = (void *) (pool->buffer + (array->itemsize * idx));
 342                         break;
 343                 }
 344
 345                 idx -= array->pool_maxitems;
 346         }
 347
 348 finish:
 349         return item;
 350 }
 351
 352 /*******************************************************************************
 353 *******************************************************************************/
 354 kern_return_t
 355 kxld_array_get_index(const KXLDArray *array, const void *item, u_int *_idx)
 356 {
 357         kern_return_t rval = KERN_FAILURE;
 358         KXLDArrayPool *pool = NULL;
 359         u_long diff = 0;
 360         u_int idx = 0;
 361         u_int base_idx = 0;
 362         const u_char *it;
 363
 364         check(array);
 365         check(item);
 366         check(_idx);
 367
 368         it = item;
 369
 370         STAILQ_FOREACH(pool, &array->pools, entries) {
 371                 if (pool->buffer <= it && it < pool->buffer + array->pool_capacity) {
 372                         diff = it - pool->buffer;
 373                         idx = (u_int) (diff / array->itemsize);
 374
 375                         idx += base_idx;
 376                         *_idx = idx;
 377
 378                         rval = KERN_SUCCESS;
 379                         goto finish;
 380                 }
 381
 382                 base_idx += array->pool_maxitems;
 383         }
 384
 385         rval = KERN_FAILURE;
 386 finish:
 387         return rval;
 388 }
 389
 390 /*******************************************************************************
 391 *******************************************************************************/
 392 kern_return_t
 393 kxld_array_resize(KXLDArray *array, u_int nitems)
 394 {
 395         kern_return_t rval = KERN_FAILURE;
 396         KXLDArrayPool *pool = NULL;
 397
 398         /* Grow the list of pools until we have enough to fit all of the entries */
 399
 400         while (nitems > array->maxitems) {
 401                 pool = pool_create(array->pool_capacity);
 402                 require_action(pool, finish, rval = KERN_FAILURE);
 403
 404                 STAILQ_INSERT_TAIL(&array->pools, pool, entries);
 405
 406                 array->maxitems += array->pool_maxitems;
 407                 array->npools += 1;
 408         }
 409
 410         nitems = reinit_pools(array, nitems);
 411         require_action(nitems == 0, finish, rval = KERN_FAILURE);
 412
 413         rval = KERN_SUCCESS;
 414 finish:
 415         return rval;
 416 }
 417
 418 /*******************************************************************************
 419 * Sets the number of items for the array and each pool.  Returns zero if there
 420 * is enough space for all items, and the number of additional items needed
 421 * if there is not enough space.
 422 *******************************************************************************/
 423 static u_int
 424 reinit_pools(KXLDArray *array, u_int nitems)
 425 {
 426         KXLDArrayPool *pool = NULL;
 427         u_int pool_nitems = 0;
 428
 429         /* Set the number of items for each pool */
 430
 431         pool_nitems = nitems;
 432         STAILQ_FOREACH(pool, &array->pools, entries) {
 433                 if (pool_nitems > array->pool_maxitems) {
 434                         pool->nitems = array->pool_maxitems;
 435                         pool_nitems -= array->pool_maxitems;
 436                 } else {
 437                         pool->nitems = pool_nitems;
 438                         pool_nitems = 0;
 439                 }
 440         }
 441         array->nitems = nitems;
 442
 443         return pool_nitems;
 444 }
 445
 446 /*******************************************************************************
 447 *******************************************************************************/
 448 kern_return_t
 449 kxld_array_remove(KXLDArray *array, u_int idx)
 450 {
 451         kern_return_t rval = KERN_FAILURE;
 452         KXLDArrayPool *pool = NULL;
 453         u_char *dst = NULL;
 454         u_char *src = NULL;
 455         u_int nitems = 0;
 456
 457         check(array);
 458
 459         if (idx >= array->nitems) {
 460                 rval = KERN_SUCCESS;
 461                 goto finish;
 462         }
 463
 464         /* We only support removing an item if all the items are contained in a
 465          * single pool (for now).
 466          */
 467         require_action(array->npools < 2 || array->nitems < array->pool_maxitems,
 468             finish, rval = KERN_NOT_SUPPORTED);
 469
 470         pool = STAILQ_FIRST(&array->pools);
 471         require_action(pool, finish, rval = KERN_FAILURE);
 472
 473         dst = pool->buffer;
 474         dst += idx * array->itemsize;
 475
 476         src = pool->buffer;
 477         src += ((idx + 1) * array->itemsize);
 478
 479         nitems = pool->nitems - idx - 1;
 480         memmove(dst, src, array->itemsize * nitems);
 481
 482         --pool->nitems;
 483         --array->nitems;
 484
 485         dst = pool->buffer;
 486         dst += pool->nitems * array->itemsize;
 487         bzero(dst, array->itemsize);
 488
 489         rval = KERN_SUCCESS;
 490 finish:
 491         return rval;
 492 }