--- /dev/null
+/*
+ * 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 <string.h>
+
+#if KERNEL
+ #include <mach/vm_param.h>
+#else
+ #include <mach/mach_init.h>
+#endif
+
+#define DEBUG_ASSERT_COMPONENT_NAME_STRING "kxld"
+#include <AssertMacros.h>
+
+#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;
+}
+
projects / apple / xnu.git / blobdiff