X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/e2fac8b15b12a7979f72090454d850e612fc5b13..b0d623f7f2ae71ed96e60569f61f9a9a27016e80:/libkern/kxld/kxld_array.c diff --git a/libkern/kxld/kxld_array.c b/libkern/kxld/kxld_array.c new file mode 100644 index 000000000..b04a6045a --- /dev/null +++ b/libkern/kxld/kxld_array.c @@ -0,0 +1,483 @@ +/* + * Copyright (c) 2008 Apple Inc. All rights reserved. + * + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ + * + * This file contains Original Code and/or Modifications of Original Code + * as defined in and that are subject to the Apple Public Source License + * Version 2.0 (the 'License'). You may not use this file except in + * compliance with the License. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * unlawful or unlicensed copies of an Apple operating system, or to + * circumvent, violate, or enable the circumvention or violation of, any + * terms of an Apple operating system software license agreement. + * + * Please obtain a copy of the License at + * http://www.opensource.apple.com/apsl/ and read it before using this file. + * + * The Original Code and all software distributed under the License are + * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, + * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. + * Please see the License for the specific language governing rights and + * limitations under the License. + * + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ + */ +#include + +#if KERNEL + #include +#else + #include +#endif + +#define DEBUG_ASSERT_COMPONENT_NAME_STRING "kxld" +#include + +#include "kxld_array.h" +#include "kxld_util.h" + +static kern_return_t array_init(KXLDArray *array, size_t itemsize, u_int nitems); +static KXLDArrayPool * pool_create(size_t capacity); +static void pool_destroy(KXLDArrayPool *pool, size_t capacity); +static u_int reinit_pools(KXLDArray *array, u_int nitems); + +/******************************************************************************* +*******************************************************************************/ +kern_return_t +kxld_array_init(KXLDArray *array, size_t itemsize, u_int nitems) +{ + kern_return_t rval = KERN_FAILURE; + KXLDArrayPool *dstpool = NULL, *srcpool = NULL, *tmp = NULL; + KXLDArrayHead srcpools = STAILQ_HEAD_INITIALIZER(srcpools); + size_t srcpool_capacity = 0; + u_long offset = 0; + + check(array); + + if (!nitems) { + kxld_array_reset(array); + rval = KERN_SUCCESS; + goto finish; + } + + require_action(itemsize, finish, rval=KERN_INVALID_ARGUMENT); + + /* If the array has some pools, we need to see if there is enough space in + * those pools to accomodate the requested size array. If there isn't + * enough space, we save the existing pools to a temporary STAILQ and zero + * out the array structure. This will cause a new pool of sufficient size + * to be created, and we then copy the data from the old pools into the new + * pool. + */ + if (array->npools) { + /* Update the array's maxitems based on the new itemsize */ + array->pool_maxitems = (u_int) (array->pool_capacity / itemsize); + array->maxitems = 0; + STAILQ_FOREACH(srcpool, &array->pools, entries) { + array->maxitems += array->pool_maxitems; + } + + /* If there's not enough space, save the pools to a temporary STAILQ + * and zero out the array structure. Otherwise, rescan the pools to + * update their internal nitems counts. + */ + if (array->maxitems < nitems) { + STAILQ_FOREACH_SAFE(srcpool, &array->pools, entries, tmp) { + STAILQ_INSERT_TAIL(&srcpools, srcpool, entries); + STAILQ_REMOVE(&array->pools, srcpool, kxld_array_pool, entries); + } + srcpool_capacity = array->pool_capacity; + bzero(array, sizeof(*array)); + } else { + nitems = reinit_pools(array, nitems); + require_action(nitems == 0, finish, rval=KERN_FAILURE); + } + } + + array->itemsize = itemsize; + + /* If array->maxitems is zero, it means we are either rebuilding an array + * that was too small, or we're initializing an array for the first time. + * In either case, we need to set up a pool of the requested size, and + * if we're rebuilding an old array, we'll also copy the data from the old + * pools into the new pool. + */ + if (array->maxitems == 0) { + + rval = array_init(array, itemsize, nitems); + require_noerr(rval, finish); + + dstpool = STAILQ_FIRST(&array->pools); + require_action(dstpool, finish, rval=KERN_FAILURE); + + STAILQ_FOREACH_SAFE(srcpool, &srcpools, entries, tmp) { + memcpy(dstpool->buffer + offset, srcpool->buffer, srcpool_capacity); + offset += srcpool_capacity; + + STAILQ_REMOVE(&srcpools, srcpool, kxld_array_pool, entries); + pool_destroy(srcpool, srcpool_capacity); + } + + } + + rval = KERN_SUCCESS; +finish: + if (rval) kxld_array_deinit(array); + return rval; +} + +/******************************************************************************* +* This may only be called to initialize (or reinitialize) an array with exactly +* zero or one pool. Calling this on an array with more than one pool is an +* error. +*******************************************************************************/ +static kern_return_t +array_init(KXLDArray *array, size_t itemsize, u_int nitems) +{ + kern_return_t rval = KERN_FAILURE; + KXLDArrayPool *pool = NULL; + + array->itemsize = itemsize; + + pool = STAILQ_FIRST(&array->pools); + if (pool) { + require_action(itemsize * nitems < array->pool_capacity, + finish, rval=KERN_FAILURE); + require_action(array->npools == 1, finish, rval=KERN_FAILURE); + bzero(pool->buffer, array->pool_capacity); + } else { + array->pool_capacity = round_page(array->itemsize * nitems); + + pool = pool_create(array->pool_capacity); + require_action(pool, finish, rval=KERN_RESOURCE_SHORTAGE); + STAILQ_INSERT_HEAD(&array->pools, pool, entries); + } + pool->nitems = nitems; + + array->pool_maxitems = (u_int) (array->pool_capacity / array->itemsize); + array->maxitems = array->pool_maxitems; + array->nitems = nitems; + array->npools = 1; + + rval = KERN_SUCCESS; +finish: + return rval; +} + +/******************************************************************************* +*******************************************************************************/ +static KXLDArrayPool * +pool_create(size_t capacity) +{ + KXLDArrayPool *pool = NULL, *rval = NULL; + + pool = kxld_alloc(sizeof(*pool)); + require(pool, finish); + + pool->buffer = kxld_page_alloc(capacity); + require(pool->buffer, finish); + bzero(pool->buffer, capacity); + + rval = pool; + pool = NULL; + +finish: + if (pool) pool_destroy(pool, capacity); + return rval; +} + +/******************************************************************************* +*******************************************************************************/ +static void +pool_destroy(KXLDArrayPool *pool, size_t capacity) +{ + if (pool) { + if (pool->buffer) kxld_page_free(pool->buffer, capacity); + kxld_free(pool, sizeof(*pool)); + } +} + +/******************************************************************************* +*******************************************************************************/ +kern_return_t +kxld_array_copy(KXLDArray *dstarray, const KXLDArray *srcarray) +{ + kern_return_t rval = KERN_FAILURE; + KXLDArrayPool *dstpool = NULL, *srcpool = NULL; + u_long needed_capacity = 0; + u_long current_capacity = 0; + u_long copysize = 0; + u_long offset = 0; + + check(dstarray); + check(srcarray); + + /* When copying array, we only want to copy to an array with a single + * pool. If the array has more than one pool or the array is too small, + * we destroy the array and build it from scratch for the copy. + */ + needed_capacity = round_page(srcarray->nitems * srcarray->itemsize); + current_capacity = dstarray->npools * dstarray->pool_capacity; + if (dstarray->npools > 1 || needed_capacity > current_capacity) { + kxld_array_deinit(dstarray); + } + + rval = array_init(dstarray, srcarray->itemsize, srcarray->nitems); + require_noerr(rval, finish); + + dstpool = STAILQ_FIRST(&dstarray->pools); + require_action(dstpool, finish, rval=KERN_FAILURE); + + /* Copy the data from the source pools to the single destination pool. */ + STAILQ_FOREACH(srcpool, &srcarray->pools, entries) { + copysize = srcpool->nitems * srcarray->itemsize; + memcpy(dstpool->buffer + offset, srcpool->buffer, copysize); + offset += copysize; + } + + rval = KERN_SUCCESS; +finish: + return rval; +} + +/******************************************************************************* +*******************************************************************************/ +void +kxld_array_reset(KXLDArray *array) +{ + KXLDArrayPool *pool = NULL; + + if (array) { + STAILQ_FOREACH(pool, &array->pools, entries) { + pool->nitems = 0; + } + array->nitems = 0; + } +} + +/******************************************************************************* +*******************************************************************************/ +void +kxld_array_clear(KXLDArray *array) +{ + KXLDArrayPool *pool = NULL; + + if (array) { + kxld_array_reset(array); + STAILQ_FOREACH(pool, &array->pools, entries) { + bzero(pool->buffer, array->pool_capacity); + } + } +} + +/******************************************************************************* +*******************************************************************************/ +void +kxld_array_deinit(KXLDArray *array) +{ + KXLDArrayPool *pool = NULL, *tmp = NULL; + + if (array) { + STAILQ_FOREACH_SAFE(pool, &array->pools, entries, tmp) { + STAILQ_REMOVE(&array->pools, pool, kxld_array_pool, entries); + pool_destroy(pool, array->pool_capacity); + } + bzero(array, sizeof(*array)); + } +} + +/******************************************************************************* +*******************************************************************************/ +void * +kxld_array_get_item(const KXLDArray *array, u_int idx) +{ + KXLDArrayPool *pool = NULL; + void *item = NULL; + + check(array); + + if (idx >= array->nitems) goto finish; + + STAILQ_FOREACH(pool, &array->pools, entries) { + if (idx < pool->nitems) { + item = (void *) (pool->buffer + (array->itemsize * idx)); + break; + } + + idx -= array->pool_maxitems; + } + +finish: + return item; +} + +/******************************************************************************* +*******************************************************************************/ +void * +kxld_array_get_slot(const KXLDArray *array, u_int idx) +{ + KXLDArrayPool *pool = NULL; + void *item = NULL; + + check(array); + + if (idx >= array->maxitems) goto finish; + + STAILQ_FOREACH(pool, &array->pools, entries) { + if (idx < array->pool_maxitems) { + item = (void *) (pool->buffer + (array->itemsize * idx)); + break; + } + + idx -= array->pool_maxitems; + } + +finish: + return item; +} + +/******************************************************************************* +*******************************************************************************/ +kern_return_t +kxld_array_get_index(const KXLDArray *array, const void *item, u_int *_idx) +{ + kern_return_t rval = KERN_FAILURE; + KXLDArrayPool *pool = NULL; + u_long diff = 0; + u_int idx = 0; + u_int base_idx = 0; + const u_char *it; + + check(array); + check(item); + check(_idx); + + it = item; + + STAILQ_FOREACH(pool, &array->pools, entries) { + if (pool->buffer <= it && it < pool->buffer + array->pool_capacity) { + diff = it - pool->buffer; + idx = (u_int) (diff / array->itemsize); + + idx += base_idx; + *_idx = idx; + + rval = KERN_SUCCESS; + goto finish; + } + + base_idx += array->pool_maxitems; + } + + rval = KERN_FAILURE; +finish: + return rval; +} + +/******************************************************************************* +*******************************************************************************/ +kern_return_t +kxld_array_resize(KXLDArray *array, u_int nitems) +{ + kern_return_t rval = KERN_FAILURE; + KXLDArrayPool *pool = NULL; + + /* Grow the list of pools until we have enough to fit all of the entries */ + + while (nitems > array->maxitems) { + pool = pool_create(array->pool_capacity); + require_action(pool, finish, rval=KERN_FAILURE); + + STAILQ_INSERT_TAIL(&array->pools, pool, entries); + + array->maxitems += array->pool_maxitems; + array->npools += 1; + } + + nitems = reinit_pools(array, nitems); + require_action(nitems == 0, finish, rval=KERN_FAILURE); + + rval = KERN_SUCCESS; +finish: + return rval; +} + +/******************************************************************************* +* Sets the number of items for the array and each pool. Returns zero if there +* is enough space for all items, and the number of additional items needed +* if there is not enough space. +*******************************************************************************/ +static u_int +reinit_pools(KXLDArray *array, u_int nitems) +{ + KXLDArrayPool *pool = NULL; + u_int pool_nitems = 0; + + /* Set the number of items for each pool */ + + pool_nitems = nitems; + STAILQ_FOREACH(pool, &array->pools, entries) { + if (pool_nitems > array->pool_maxitems) { + pool->nitems = array->pool_maxitems; + pool_nitems -= array->pool_maxitems; + } else { + pool->nitems = pool_nitems; + pool_nitems = 0; + } + } + array->nitems = nitems; + + return pool_nitems; +} + +/******************************************************************************* +*******************************************************************************/ +kern_return_t +kxld_array_remove(KXLDArray *array, u_int idx) +{ + kern_return_t rval = KERN_FAILURE; + KXLDArrayPool *pool = NULL; + u_char *dst = NULL; + u_char *src = NULL; + u_int nitems = 0; + + check(array); + + if (idx >= array->nitems) { + rval = KERN_SUCCESS; + goto finish; + } + + /* We only support removing an item if all the items are contained in a + * single pool (for now). + */ + require_action(array->npools < 2 || array->nitems < array->pool_maxitems, + finish, rval=KERN_NOT_SUPPORTED); + + pool = STAILQ_FIRST(&array->pools); + require_action(pool, finish, rval=KERN_FAILURE); + + dst = pool->buffer; + dst += idx * array->itemsize; + + src = pool->buffer; + src += ((idx + 1) * array->itemsize); + + nitems = pool->nitems - idx - 1; + memmove(dst, src, array->itemsize * nitems); + + --pool->nitems; + --array->nitems; + + dst = pool->buffer; + dst += pool->nitems * array->itemsize; + bzero(dst, array->itemsize); + + rval = KERN_SUCCESS; +finish: + return rval; +} +