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