116 static const uint16_t kt_zone_cfg[] = {
428 __options_decl(kalloc_type_variant_t, uint16_t, {
447 TUNABLE(uint16_t, kt_var_heaps, "kt_var_heaps",
449 TUNABLE(uint16_t, kt_fixed_zones, "kt_fixed_zones",
451 TUNABLE(uint16_t, kt_var_ptr_heaps, "kt_var_ptr_heaps", 2);
480 static uint16_t kt_freq_list[MAX_K_ZONE(kt_zone_cfg)];
482 static uint16_t kt_freq_list_total[MAX_K_ZONE(kt_zone_cfg)];
485 	uint16_t nzones;
486 	uint16_t idx;
500 #define KT_GET_HASH(flags) (uint16_t)((flags & KT_HASH) >> 16)
510 static inline uint16_t
513 	return (uint16_t) (kt_size >> KALLOC_TYPE_IDX_SHIFT);  in kalloc_type_get_idx()
517 kalloc_type_set_idx(uint32_t kt_size, uint16_t idx)  in kalloc_type_set_idx()
539 	uint16_t idx = kalloc_type_dlut[INDEX_ZDLUT(size)];  in kalloc_type_idx_for_size()
1122 	const uint16_t idxA = kalloc_type_get_idx(ktA->kt_size);  in kalloc_type_cmp_fixed()
1123 	const uint16_t idxB = kalloc_type_get_idx(ktB->kt_size);  in kalloc_type_cmp_fixed()
1174 static uint16_t *
1176 	uint16_t           *kt_skip_list_start,  in kalloc_type_create_iterators_fixed()
1179 	uint16_t *kt_skip_list = kt_skip_list_start;  in kalloc_type_create_iterators_fixed()
1180 	uint16_t p_idx = UINT16_MAX; /* previous size idx */  in kalloc_type_create_iterators_fixed()
1181 	uint16_t c_idx = 0; /* current size idx */  in kalloc_type_create_iterators_fixed()
1182 	uint16_t unique_sig = 0;  in kalloc_type_create_iterators_fixed()
1183 	uint16_t total_sig = 0;  in kalloc_type_create_iterators_fixed()
1192 	for (uint16_t i = 0; i < count; i++) {  in kalloc_type_create_iterators_fixed()
1268 	*kt_skip_list = (uint16_t) count;  in kalloc_type_create_iterators_fixed()
1306 static uint16_t
1308 	uint16_t            freq_list[MAX_K_ZONE(kt_zone_cfg)],  in kalloc_type_distribute_budget()
1309 	uint16_t            kt_zones[MAX_K_ZONE(kt_zone_cfg)],  in kalloc_type_distribute_budget()
1310 	uint16_t            zone_budget,  in kalloc_type_distribute_budget()
1311 	uint16_t            min_zones_per_size)  in kalloc_type_distribute_budget()
1313 	uint16_t total_sig = 0;  in kalloc_type_distribute_budget()
1314 	uint16_t min_sig = 0;  in kalloc_type_distribute_budget()
1315 	uint16_t assigned_zones = 0;  in kalloc_type_distribute_budget()
1316 	uint16_t remaining_zones = zone_budget;  in kalloc_type_distribute_budget()
1317 	uint16_t modulo = 0;  in kalloc_type_distribute_budget()
1319 	for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {  in kalloc_type_distribute_budget()
1320 		uint16_t sig_freq = freq_list[i];  in kalloc_type_distribute_budget()
1321 		uint16_t min_zones = min_zones_per_size;  in kalloc_type_distribute_budget()
1338 	for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {  in kalloc_type_distribute_budget()
1339 		uint16_t freq = freq_list[i];  in kalloc_type_distribute_budget()
1345 		uint16_t n_zones = (uint16_t) numer / total_sig;  in kalloc_type_distribute_budget()
1361 			uint16_t extra_zones = n_zones + min_zones_per_size - freq;  in kalloc_type_distribute_budget()
1389 	uint16_t            freq_total_list[MAX_K_ZONE(kt_zone_cfg)],  in kalloc_type_redistribute_budget()
1390 	uint16_t            kt_zones[MAX_K_ZONE(kt_zone_cfg)])  in kalloc_type_redistribute_budget()
1392 	uint16_t count = 0, cur_count = 0;  in kalloc_type_redistribute_budget()
1394 	uint16_t top_zone_total = 0;  in kalloc_type_redistribute_budget()
1396 	for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {  in kalloc_type_redistribute_budget()
1397 		uint16_t zones = kt_zones[i];  in kalloc_type_redistribute_budget()
1414 	for (uint16_t i = 0; i < 3; i++) {  in kalloc_type_redistribute_budget()
1423 	for (uint16_t i = 0; i < 3; i++) {  in kalloc_type_redistribute_budget()
1424 		uint16_t zone_borrow = (sorted_zones[i].nzones * count) / top_zone_total;  in kalloc_type_redistribute_budget()
1425 		uint16_t zone_available = kt_zones[sorted_zones[i].idx];  in kalloc_type_redistribute_budget()
1434 	for (uint16_t i = 0; i < 3; i++) {  in kalloc_type_redistribute_budget()
1442 	for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {  in kalloc_type_redistribute_budget()
1451 static uint16_t
1453 	uint16_t            freq_list[MAX_K_ZONE(kt_zone_cfg)],  in kalloc_type_apply_policy()
1454 	uint16_t            freq_total_list[MAX_K_ZONE(kt_zone_cfg)],  in kalloc_type_apply_policy()
1455 	uint16_t            kt_zones_sig[MAX_K_ZONE(kt_zone_cfg)],  in kalloc_type_apply_policy()
1456 	uint16_t            kt_zones_type[MAX_K_ZONE(kt_zone_cfg)],  in kalloc_type_apply_policy()
1457 	uint16_t            zone_budget)  in kalloc_type_apply_policy()
1459 	uint16_t zbudget_sig = (uint16_t) ((7 * zone_budget) / 10);  in kalloc_type_apply_policy()
1460 	uint16_t zbudget_type = zone_budget - zbudget_sig;  in kalloc_type_apply_policy()
1461 	uint16_t wasted_zones = 0;  in kalloc_type_apply_policy()
1465 		uint16_t current_zones = os_atomic_load(&num_zones, relaxed);  in kalloc_type_apply_policy()
1483 		for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {  in kalloc_type_apply_policy()
1499 	uint16_t            kt_zones,  in kalloc_type_create_zone_for_size()
1506 	for (uint16_t i = 0; i < kt_zones; i++) {  in kalloc_type_create_zone_for_size()
1536 static uint16_t
1538 	uint16_t            zones_total_type,  in kalloc_type_zones_for_type()
1539 	uint16_t            unique_types,  in kalloc_type_zones_for_type()
1540 	uint16_t            total_types,  in kalloc_type_zones_for_type()
1543 	uint16_t zones_for_type = 0, n_mod = 0;  in kalloc_type_zones_for_type()
1571 static uint16_t
1575 	uint16_t               *kt_skip_list)  in kalloc_type_build_skip_list()
1579 	uint16_t i = 0, idx = 0;  in kalloc_type_build_skip_list()
1608 	uint16_t            n_zones,  in kalloc_type_init_sig_eq()
1611 	for (uint16_t i = 0; i < n_zones; i++) {  in kalloc_type_init_sig_eq()
1620 static uint16_t
1625 	uint16_t            zones_total_type,  in kalloc_type_distribute_zone_for_type()
1626 	uint16_t            total_types,  in kalloc_type_distribute_zone_for_type()
1627 	uint16_t           *kt_skip_list,  in kalloc_type_distribute_zone_for_type()
1629 	uint16_t            type_zones_start,  in kalloc_type_distribute_zone_for_type()
1633 	uint16_t count = 0, n_zones = 0;  in kalloc_type_distribute_zone_for_type()
1634 	uint16_t *shuffle_buf = NULL;  in kalloc_type_distribute_zone_for_type()
1670 	for (uint16_t i = 0; i < count; i++) {  in kalloc_type_distribute_zone_for_type()
1671 		uint16_t zidx = i % n_zones, shuffled_zidx = 0;  in kalloc_type_distribute_zone_for_type()
1672 		uint16_t type_start = kt_skip_list[i];  in kalloc_type_distribute_zone_for_type()
1674 		uint16_t type_end = kt_skip_list[i + 1];  in kalloc_type_distribute_zone_for_type()
1694 	uint16_t           *kt_skip_list_start,  in kalloc_type_create_zones_fixed()
1695 	uint16_t           *kt_shuffle_buf)  in kalloc_type_create_zones_fixed()
1697 	uint16_t *kt_skip_list = kt_skip_list_start;  in kalloc_type_create_zones_fixed()
1698 	uint16_t p_j = 0;  in kalloc_type_create_zones_fixed()
1699 	uint16_t kt_zones_sig[MAX_K_ZONE(kt_zone_cfg)] = {};  in kalloc_type_create_zones_fixed()
1700 	uint16_t kt_zones_type[MAX_K_ZONE(kt_zone_cfg)] = {};  in kalloc_type_create_zones_fixed()
1703 	    (vm_address_t) kt_buffer) / sizeof(uint16_t);  in kalloc_type_create_zones_fixed()
1712 	for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {  in kalloc_type_create_zones_fixed()
1713 		uint16_t n_unique_sig = kt_freq_list[i];  in kalloc_type_create_zones_fixed()
1715 		uint16_t n_zones_sig = kt_zones_sig[i];  in kalloc_type_create_zones_fixed()
1716 		uint16_t n_zones_type = kt_zones_type[i];  in kalloc_type_create_zones_fixed()
1717 		uint16_t total_types = kt_freq_list_total[i];  in kalloc_type_create_zones_fixed()
1718 		uint16_t type_zones_used = 0;  in kalloc_type_create_zones_fixed()
1745 		for (uint16_t j = 0; j < n_zones_sig; j++) {  in kalloc_type_create_zones_fixed()
1751 		for (uint16_t j = 0; j < n_unique_sig; j++) {  in kalloc_type_create_zones_fixed()
1755 			uint16_t shuffle_idx = kt_shuffle_buf[j];  in kalloc_type_create_zones_fixed()
1756 			uint16_t cur = kt_skip_list[shuffle_idx + p_j];  in kalloc_type_create_zones_fixed()
1757 			uint16_t end = kt_skip_list[shuffle_idx + p_j + 1];  in kalloc_type_create_zones_fixed()
1789 	vm_size_t sig_slist_size = (size_t) kt_count * sizeof(uint16_t);  in kalloc_type_view_init_fixed()
1805 	uint16_t *kt_skip_list_start = (uint16_t *)(kt_buffer + kt_count);  in kalloc_type_view_init_fixed()
1806 	uint16_t *kt_shuffle_buf = kalloc_type_create_iterators_fixed(  in kalloc_type_view_init_fixed()
1886 	uint16_t *shuffle_buf;  in kalloc_type_view_init_var()
1887 	uint16_t fixed_heaps = KT_VAR__FIRST_FLEXIBLE_HEAP - 1;  in kalloc_type_view_init_var()
1888 	uint16_t flex_heap_count = kt_var_heaps - fixed_heaps - 1;  in kalloc_type_view_init_var()
1892 	uint16_t split_heap = kmem_get_random16(flex_heap_count - 1);  in kalloc_type_view_init_var()
1928 	shuffle_buf = (uint16_t *)(kt_skip_list_start + unique_sig + 1);  in kalloc_type_view_init_var()
2027 kalloc_guard(vm_tag_t tag, uint16_t type_hash, const void *owner)  in kalloc_guard()
2225 	uint16_t              kt_hash,  in kalloc_large()
2387 	uint16_t kt_hash;  in kalloc_ext()
2400 		kt_hash = (uint16_t) KT_GET_HASH(kt_view->kt_flags);  in kalloc_ext()
2884 	uint16_t              kt_hash,  in krealloc_large()
3002 	uint16_t kt_hash = 0;  in krealloc_ext()
3206 	uint16_t idx;  in kheap_init_var()
3214 	kheap->kh_type_hash = (uint16_t) kalloc_hash_adjust(  in kheap_init_var()
3358 	for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {  in kalloc_type_feature_on()
3383 	uint16_t zone_budget = (uint16_t) in;  in kalloc_type_test_policy()
3384 	uint16_t max_bucket_freq = 25;  in kalloc_type_test_policy()
3385 	uint16_t freq_list[MAX_K_ZONE(kt_zone_cfg)] = {};  in kalloc_type_test_policy()
3386 	uint16_t freq_total_list[MAX_K_ZONE(kt_zone_cfg)] = {};  in kalloc_type_test_policy()
3387 	uint16_t zones_per_sig[MAX_K_ZONE(kt_zone_cfg)] = {};  in kalloc_type_test_policy()
3388 	uint16_t zones_per_type[MAX_K_ZONE(kt_zone_cfg)] = {};  in kalloc_type_test_policy()
3389 	uint16_t random[MAX_K_ZONE(kt_zone_cfg) * 2];  in kalloc_type_test_policy()
3390 	uint16_t wasted_zone_budget = 0, total_types = 0;  in kalloc_type_test_policy()
3391 	uint16_t n_zones = 0, n_zones_cal = 0;  in kalloc_type_test_policy()
3401 	for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {  in kalloc_type_test_policy()
3402 		uint16_t r1 = (random[2 * i] % max_bucket_freq) + 1;  in kalloc_type_test_policy()
3403 		uint16_t r2 = (random[2 * i + 1] % max_bucket_freq) + 1;  in kalloc_type_test_policy()
3412 	for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {  in kalloc_type_test_policy()
3418 	for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {  in kalloc_type_test_policy()
3419 		uint16_t n_zones_for_type = kalloc_type_zones_for_type(n_zones,  in kalloc_type_test_policy()
3477 	for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {  in run_kalloc_type_test()