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 42static kern_return_t array_init(KXLDArray *array, size_t itemsize, u_int nitems); 43static KXLDArrayPool * pool_create(size_t capacity); 44static void pool_destroy(KXLDArrayPool *pool, size_t capacity); 45static u_int reinit_pools(KXLDArray *array, u_int nitems); 46 47/******************************************************************************* 48*******************************************************************************/ 49kern_return_t 50kxld_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; 127finish: 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*******************************************************************************/ 137static kern_return_t 138array_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; 169finish: 170 return rval; 171} 172 173/******************************************************************************* 174*******************************************************************************/ 175static KXLDArrayPool * 176pool_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 190finish: 191 if (pool) pool_destroy(pool, capacity); 192 return rval; 193} 194 195/******************************************************************************* 196*******************************************************************************/ 197static void 198pool_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*******************************************************************************/ 208kern_return_t 209kxld_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; 245finish: 246 return rval; 247} 248 249/******************************************************************************* 250*******************************************************************************/ 251void 252kxld_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*******************************************************************************/ 266void 267kxld_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*******************************************************************************/ 281void 282kxld_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*******************************************************************************/ 297void * 298kxld_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 316finish: 317 return item; 318} 319 320/******************************************************************************* 321*******************************************************************************/ 322void * 323kxld_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 341finish: 342 return item; 343} 344 345/******************************************************************************* 346*******************************************************************************/ 347kern_return_t 348kxld_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; 379finish: 380 return rval; 381} 382 383/******************************************************************************* 384*******************************************************************************/ 385kern_return_t 386kxld_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; 407finish: 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*******************************************************************************/ 416static u_int 417reinit_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*******************************************************************************/ 441kern_return_t 442kxld_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; 483finish: 484 return rval; 485} 486 487