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