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