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
 110         rval = array_init(array, itemsize, nitems);
 111         require_noerr(rval, finish);
 112
 113         dstpool = STAILQ_FIRST(&array->pools);
 114         require_action(dstpool, finish, rval=KERN_FAILURE);
 115
 116         STAILQ_FOREACH_SAFE(srcpool, &srcpools, entries, tmp) {
 117             memcpy(dstpool->buffer + offset, srcpool->buffer, srcpool_capacity);
 118             offset += srcpool_capacity;
 119
 120             STAILQ_REMOVE(&srcpools, srcpool, kxld_array_pool, entries);
 121             pool_destroy(srcpool, srcpool_capacity);
 122         }
 123
 124     }
 125
 126     rval = KERN_SUCCESS;
 127 finish:
 128     if (rval) kxld_array_deinit(array);
 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     array->itemsize = itemsize;
 144
 145     pool = STAILQ_FIRST(&array->pools);
 146     if (pool) {
 147         require_action(itemsize * nitems < array->pool_capacity,
 148             finish, rval=KERN_FAILURE);
 149         require_action(array->npools == 1, finish, rval=KERN_FAILURE);
 150         bzero(pool->buffer, array->pool_capacity);
 151     } else {
 152         array->pool_capacity = round_page(array->itemsize * nitems);
 153
 154         pool = pool_create(array->pool_capacity);
 155         require_action(pool, finish, rval=KERN_RESOURCE_SHORTAGE);
 156         STAILQ_INSERT_HEAD(&array->pools, pool, entries);
 157     }
 158     pool->nitems = nitems;
 159
 160     array->pool_maxitems = (u_int) (array->pool_capacity / array->itemsize);
 161     array->maxitems = array->pool_maxitems;
 162     array->nitems = nitems;
 163     array->npools = 1;
 164
 165     rval = KERN_SUCCESS;
 166 finish:
 167     return rval;
 168 }
 169
 170 /*******************************************************************************
 171 *******************************************************************************/
 172 static KXLDArrayPool *
 173 pool_create(size_t capacity)
 174 {
 175     KXLDArrayPool *pool = NULL, *rval = NULL;
 176
 177     pool = kxld_alloc(sizeof(*pool));
 178     require(pool, finish);
 179
 180     pool->buffer = kxld_page_alloc(capacity);
 181     require(pool->buffer, finish);
 182     bzero(pool->buffer, capacity);
 183
 184     rval = pool;
 185     pool = NULL;
 186
 187 finish:
 188     if (pool) pool_destroy(pool, capacity);
 189     return rval;
 190 }
 191
 192 /*******************************************************************************
 193 *******************************************************************************/
 194 static void
 195 pool_destroy(KXLDArrayPool *pool, size_t capacity)
 196 {
 197     if (pool) {
 198         if (pool->buffer) kxld_page_free(pool->buffer, capacity);
 199         kxld_free(pool, sizeof(*pool));
 200     }
 201 }
 202
 203 /*******************************************************************************
 204 *******************************************************************************/
 205 kern_return_t
 206 kxld_array_copy(KXLDArray *dstarray, const KXLDArray *srcarray)
 207 {
 208     kern_return_t rval = KERN_FAILURE;
 209     KXLDArrayPool *dstpool = NULL, *srcpool = NULL;
 210     u_long needed_capacity = 0;
 211     u_long current_capacity = 0;
 212     u_long copysize = 0;
 213     u_long offset = 0;
 214
 215     check(dstarray);
 216     check(srcarray);
 217
 218     /* When copying array, we only want to copy to an array with a single
 219      * pool.  If the array has more than one pool or the array is too small,
 220      * we destroy the array and build it from scratch for the copy.
 221      */
 222     needed_capacity = round_page(srcarray->nitems * srcarray->itemsize);
 223     current_capacity = dstarray->npools * dstarray->pool_capacity;
 224     if (dstarray->npools > 1 || needed_capacity > current_capacity) {
 225         kxld_array_deinit(dstarray);
 226     }
 227
 228     rval = array_init(dstarray, srcarray->itemsize, srcarray->nitems);
 229     require_noerr(rval, finish);
 230
 231     dstpool = STAILQ_FIRST(&dstarray->pools);
 232     require_action(dstpool, finish, rval=KERN_FAILURE);
 233
 234     /* Copy the data from the source pools to the single destination pool. */
 235     STAILQ_FOREACH(srcpool, &srcarray->pools, entries) {
 236         copysize = srcpool->nitems * srcarray->itemsize;
 237         memcpy(dstpool->buffer + offset, srcpool->buffer, copysize);
 238         offset += copysize;
 239     }
 240
 241     rval = KERN_SUCCESS;
 242 finish:
 243     return rval;
 244 }
 245
 246 /*******************************************************************************
 247 *******************************************************************************/
 248 void
 249 kxld_array_reset(KXLDArray *array)
 250 {
 251     KXLDArrayPool *pool = NULL;
 252
 253     if (array) {
 254         STAILQ_FOREACH(pool, &array->pools, entries) {
 255             pool->nitems = 0;
 256         }
 257         array->nitems = 0;
 258     }
 259 }
 260
 261 /*******************************************************************************
 262 *******************************************************************************/
 263 void
 264 kxld_array_clear(KXLDArray *array)
 265 {
 266     KXLDArrayPool *pool = NULL;
 267
 268     if (array) {
 269         kxld_array_reset(array);
 270         STAILQ_FOREACH(pool, &array->pools, entries) {
 271             bzero(pool->buffer, array->pool_capacity);
 272         }
 273     }
 274 }
 275
 276 /*******************************************************************************
 277 *******************************************************************************/
 278 void
 279 kxld_array_deinit(KXLDArray *array)
 280 {
 281     KXLDArrayPool *pool = NULL, *tmp = NULL;
 282
 283     if (array) {
 284         STAILQ_FOREACH_SAFE(pool, &array->pools, entries, tmp) {
 285             STAILQ_REMOVE(&array->pools, pool, kxld_array_pool, entries);
 286             pool_destroy(pool, array->pool_capacity);
 287         }
 288         bzero(array, sizeof(*array));
 289     }
 290 }
 291
 292 /*******************************************************************************
 293 *******************************************************************************/
 294 void *
 295 kxld_array_get_item(const KXLDArray *array, u_int idx)
 296 {
 297     KXLDArrayPool *pool = NULL;
 298     void *item = NULL;
 299
 300     check(array);
 301
 302     if (idx >= array->nitems) goto finish;
 303
 304     STAILQ_FOREACH(pool, &array->pools, entries) {
 305         if (idx < pool->nitems) {
 306             item = (void *) (pool->buffer + (array->itemsize * idx));
 307             break;
 308         }
 309
 310         idx -= array->pool_maxitems;
 311     }
 312
 313 finish:
 314     return item;
 315 }
 316
 317 /*******************************************************************************
 318 *******************************************************************************/
 319 void *
 320 kxld_array_get_slot(const KXLDArray *array, u_int idx)
 321 {
 322     KXLDArrayPool *pool = NULL;
 323     void *item = NULL;
 324
 325     check(array);
 326
 327     if (idx >= array->maxitems) goto finish;
 328
 329     STAILQ_FOREACH(pool, &array->pools, entries) {
 330         if (idx < array->pool_maxitems) {
 331             item = (void *) (pool->buffer + (array->itemsize * idx));
 332             break;
 333         }
 334
 335         idx -= array->pool_maxitems;
 336     }
 337
 338 finish:
 339     return item;
 340 }
 341
 342 /*******************************************************************************
 343 *******************************************************************************/
 344 kern_return_t
 345 kxld_array_get_index(const KXLDArray *array, const void *item, u_int *_idx)
 346 {
 347     kern_return_t rval = KERN_FAILURE;
 348     KXLDArrayPool *pool = NULL;
 349     u_long diff = 0;
 350     u_int idx = 0;
 351     u_int base_idx = 0;
 352     const u_char *it;
 353
 354     check(array);
 355     check(item);
 356     check(_idx);
 357
 358     it = item;
 359
 360     STAILQ_FOREACH(pool, &array->pools, entries) {
 361         if (pool->buffer <= it && it < pool->buffer + array->pool_capacity) {
 362             diff = it - pool->buffer;
 363             idx = (u_int) (diff / array->itemsize);
 364
 365             idx += base_idx;
 366             *_idx = idx;
 367
 368             rval = KERN_SUCCESS;
 369             goto finish;
 370         }
 371
 372         base_idx += array->pool_maxitems;
 373     }
 374
 375     rval = KERN_FAILURE;
 376 finish:
 377     return rval;
 378 }
 379
 380 /*******************************************************************************
 381 *******************************************************************************/
 382 kern_return_t
 383 kxld_array_resize(KXLDArray *array, u_int nitems)
 384 {
 385     kern_return_t rval = KERN_FAILURE;
 386     KXLDArrayPool *pool = NULL;
 387
 388     /* Grow the list of pools until we have enough to fit all of the entries */
 389
 390     while (nitems > array->maxitems) {
 391         pool = pool_create(array->pool_capacity);
 392         require_action(pool, finish, rval=KERN_FAILURE);
 393
 394         STAILQ_INSERT_TAIL(&array->pools, pool, entries);
 395
 396         array->maxitems += array->pool_maxitems;
 397         array->npools += 1;
 398     }
 399
 400     nitems = reinit_pools(array, nitems);
 401     require_action(nitems == 0, finish, rval=KERN_FAILURE);
 402
 403     rval = KERN_SUCCESS;
 404 finish:
 405     return rval;
 406 }
 407
 408 /*******************************************************************************
 409 * Sets the number of items for the array and each pool.  Returns zero if there
 410 * is enough space for all items, and the number of additional items needed
 411 * if there is not enough space.
 412 *******************************************************************************/
 413 static u_int
 414 reinit_pools(KXLDArray *array, u_int nitems)
 415 {
 416     KXLDArrayPool *pool = NULL;
 417     u_int pool_nitems = 0;
 418
 419     /* Set the number of items for each pool */
 420
 421     pool_nitems = nitems;
 422     STAILQ_FOREACH(pool, &array->pools, entries) {
 423         if (pool_nitems > array->pool_maxitems) {
 424             pool->nitems = array->pool_maxitems;
 425             pool_nitems -= array->pool_maxitems;
 426         } else {
 427             pool->nitems = pool_nitems;
 428             pool_nitems = 0;
 429         }
 430     }
 431     array->nitems = nitems;
 432
 433     return pool_nitems;
 434 }
 435
 436 /*******************************************************************************
 437 *******************************************************************************/
 438 kern_return_t
 439 kxld_array_remove(KXLDArray *array, u_int idx)
 440 {
 441     kern_return_t rval = KERN_FAILURE;
 442     KXLDArrayPool *pool = NULL;
 443     u_char *dst = NULL;
 444     u_char *src = NULL;
 445     u_int nitems = 0;
 446
 447     check(array);
 448
 449     if (idx >= array->nitems) {
 450         rval = KERN_SUCCESS;
 451         goto finish;
 452     }
 453
 454     /* We only support removing an item if all the items are contained in a
 455      * single pool (for now).
 456      */
 457     require_action(array->npools < 2 || array->nitems < array->pool_maxitems,
 458         finish, rval=KERN_NOT_SUPPORTED);
 459
 460     pool = STAILQ_FIRST(&array->pools);
 461     require_action(pool, finish, rval=KERN_FAILURE);
 462
 463     dst = pool->buffer;
 464     dst += idx * array->itemsize;
 465
 466     src = pool->buffer;
 467     src += ((idx + 1) * array->itemsize);
 468
 469     nitems = pool->nitems - idx - 1;
 470     memmove(dst, src, array->itemsize * nitems);
 471
 472     --pool->nitems;
 473     --array->nitems;
 474
 475     dst = pool->buffer;
 476     dst += pool->nitems * array->itemsize;
 477     bzero(dst, array->itemsize);
 478
 479     rval = KERN_SUCCESS;
 480 finish:
 481     return rval;
 482 }
 483