xref: /xnu-10002.1.13/osfmk/kern/compact_id.c (revision 1031c584a5e37aff177559b9f69dbd3c8c3fd30a)

/*
 * Copyright (c) 2022 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 <kern/compact_id.h>
#include <kern/locks.h>
#include <kern/thread.h>

static LCK_GRP_DECLARE(compact_id_lck_grp, "compact_id");

#define compact_id_table_sleep(table) \
	lck_mtx_sleep_with_inheritor(&(table)->cidt_lock, \
	    LCK_SLEEP_DEFAULT, (event_t)(table), (table)->cidt_allocator, \
	    THREAD_UNINT, TIMEOUT_WAIT_FOREVER)
#define compact_id_table_wake(table) \
	wakeup_all_with_inheritor((event_t)(table), THREAD_AWAKENED)

static inline uint32_t
compact_id_prev_max(uint32_t idx)
{
	/*
	 * |BASE|BASE|2BASE|4BASE|...|2^(index-2)BASE|2^(index-1)BASE|
	 *   0    1     2     3          index - 1        index
	 *
	 * the maximum number of values that can be stored on all
	 * entries previous to table_index is:
	 * CTID_BASE_TABLE * 2^(table_index - 1)
	 * for table_index greater then 0.
	 */
	return idx ? COMPACT_ID_COUNT_BASE << (idx - 1) : 0;
}

static uint32_t
compact_id_slab_size(uint32_t table_index)
{
	if (table_index == 0) {
		return COMPACT_ID_COUNT_BASE;
	}
	return COMPACT_ID_COUNT_BASE << (table_index - 1);
}

static uint32_t
compact_id_slab_index(compact_id_t cid)
{
	/*
	 * The first 2 entries have size COMPACT_ID_COUNT_BASE,
	 * all others have size COMPACT_ID_COUNT_BASE * 2^(i - 1).
	 *
	 * If you get the the number of the most significant 0s
	 * on COMPACT_ID_COUNT_BASE and you subtract how many there
	 * are in cidt, you get the index in the table.
	 */
	cid |= COMPACT_ID_COUNT_BASE - 1;
	return __builtin_clz(COMPACT_ID_COUNT_BASE) - __builtin_clz(cid) + 1;
}

void
compact_id_table_init(compact_id_table_t table)
{
	/* lck_group_init knows about what this function does */
	lck_mtx_init(&table->cidt_lock, &compact_id_lck_grp, LCK_ATTR_NULL);
}

void **
compact_id_resolve(compact_id_table_t table, compact_id_t cid)
{
	return table->cidt_array[compact_id_slab_index(cid)] + cid;
}

__attribute__((noinline))
static void
compact_id_table_grow(compact_id_table_t table, uint32_t idx)
{
	uint32_t size;

	/*
	 * Let's check if is someone is already
	 * allocating memory.
	 */
	if (table->cidt_allocator != NULL) {
		table->cidt_waiters = true;
		compact_id_table_sleep(table);
		return;
	}

	/*
	 * We need to allocate more memory.
	 * Let's unlock and notify
	 * other thread who is allocating.
	 */
	table->cidt_allocator = current_thread();
	compact_id_table_unlock(table);

	size = compact_id_slab_size(idx);
	table->cidt_bitmap[idx] = zalloc_permanent(BITMAP_SIZE(size), ZALIGN(bitmap_t));
	table->cidt_array[idx]  = zalloc_permanent(size * sizeof(thread_t), ZALIGN_PTR);
	/*
	 * Note: because we expect lookups to be common,
	 *       cidt_array isn't the real array but shifted
	 *       so that dereferencing it with the compact ID
	 *       works for any slab.
	 */
	table->cidt_array[idx] -= compact_id_prev_max(idx);
	bitmap_full(table->cidt_bitmap[idx], size);

	compact_id_table_lock(table);
	assert(table->cidt_allocator == current_thread());
	table->cidt_allocator = NULL;
	if (table->cidt_waiters) {
		table->cidt_waiters = false;
		compact_id_table_wake(table);
	}
}

compact_id_t
compact_id_get_locked(
	compact_id_table_t      table,
	compact_id_t            limit,
	void                   *value)
{
	compact_id_t cid;
	uint32_t slab_size;
	uint32_t idx = 0;
	int bit_index;

again:
	idx = compact_id_slab_index(table->cidt_first_free);
	for (; idx < COMPACT_ID_SLAB_COUNT; idx++) {
		bitmap_t *map = table->cidt_bitmap[idx];
		void    **arr = table->cidt_array[idx];

		if (arr == NULL) {
			compact_id_table_grow(table, idx);
			goto again;
		}

		slab_size = compact_id_slab_size(idx);
		bit_index = bitmap_lsb_first(map, slab_size);
		if (bit_index >= 0) {
			cid = compact_id_prev_max(idx) + bit_index;
			if (cid > limit) {
				break;
			}

			table->cidt_count++;
			table->cidt_first_free = cid + 1;
			bitmap_clear(map, bit_index);
			assert(arr[cid] == NULL);
			arr[cid] = value;
			return cid;
		}
	}

	panic("table %p ran out of compact IDs", table);
}

compact_id_t
compact_id_get(
	compact_id_table_t      table,
	compact_id_t            limit,
	void                   *value)
{
	compact_id_t cid;

	compact_id_table_lock(table);
	cid = compact_id_get_locked(table, limit, value);
	compact_id_table_unlock(table);
	return cid;
}

void *
compact_id_put(compact_id_table_t table, compact_id_t cid)
{
	uint32_t  idx = compact_id_slab_index(cid);
	bitmap_t *map = table->cidt_bitmap[idx];
	void    **arr = table->cidt_array[idx];
	void *value;

	compact_id_table_lock(table);
	value = arr[cid];
	arr[cid] = NULL;
	bitmap_set(map, cid - compact_id_prev_max(idx));
	if (cid < table->cidt_first_free) {
		table->cidt_first_free = cid;
	}
	table->cidt_count--;
	compact_id_table_unlock(table);

	return value;
}

void
compact_id_for_each(
	compact_id_table_t      table,
	uint32_t                stride,
	bool                  (^cb)(void *v))
{
	const uint64_t pause_init = stride;
	uint64_t pause = pause_init;

	compact_id_table_lock(table);
	for (uint32_t sidx = 0; sidx < COMPACT_ID_SLAB_COUNT; sidx++) {
		void    **arr = table->cidt_array[sidx];
		uint32_t  size = compact_id_slab_size(sidx);
		uint32_t  prev = compact_id_prev_max(sidx);

		if (arr == NULL) {
			break;
		}
		for (compact_id_t cid = prev; cid < prev + size; cid++) {
			if (arr[cid] == NULL) {
				continue;
			}
			if (!cb(arr[cid])) {
				break;
			}
			if (pause-- == 0) {
				compact_id_table_unlock(table);
				pause = pause_init;
				compact_id_table_lock(table);
			}
		}
	}
	compact_id_table_unlock(table);
}

void
compact_id_table_lock(compact_id_table_t table)
{
	lck_mtx_lock(&table->cidt_lock);
}

void
compact_id_table_unlock(compact_id_table_t table)
{
	lck_mtx_unlock(&table->cidt_lock);
}