1 /*
2 * Copyright (c) 2024 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
29 #include <stdint.h>
30
31 #include <os/atomic_private.h>
32 #include <kern/processor.h>
33
34 #include <kern/sched_common.h>
35
36 #if __AMP__
37
38 SECURITY_READ_ONLY_LATE(uint8_t) sched_num_psets = UINT8_MAX;
39 static_assert(MAX_PSETS < UINT8_MAX, "UINT8_MAX is used as a sentinel to indicate sched_num_psets is not initialized.");
40
41 void
sched_pset_search_order_compute(sched_pset_search_order_t * search_order_out,sched_pset_search_order_sort_data_t * datas,size_t num_datas,sched_pset_search_order_sort_cmpfunc_t cmp)42 sched_pset_search_order_compute(sched_pset_search_order_t *search_order_out,
43 sched_pset_search_order_sort_data_t *datas, size_t num_datas,
44 sched_pset_search_order_sort_cmpfunc_t cmp)
45 {
46 qsort(datas, num_datas, sizeof(sched_pset_search_order_sort_data_t), cmp);
47 sched_pset_search_order_t search_order;
48 for (int i = 0; i < num_datas; i++) {
49 search_order.spso_search_order[i] = datas[i].spsosd_dst_pset_id;
50 }
51 for (int i = (int)num_datas; i < sched_num_psets - 1; i++) {
52 /*
53 * If fewer sort datas were passed in than the number of psets minus
54 * 1 (AKA the maximum length of a pset search order), then mark the
55 * remaining slots at the end with an invalid pset id.
56 */
57 search_order.spso_search_order[i] = PSET_ID_INVALID;
58 }
59 os_atomic_store_wide(&search_order_out->spso_packed, search_order.spso_packed, relaxed);
60 }
61
62 void
sched_pset_search_order_init(processor_set_t src_pset,sched_pset_search_order_t * search_order_out)63 sched_pset_search_order_init(processor_set_t src_pset, sched_pset_search_order_t *search_order_out)
64 {
65 pset_id_t other_pset_id = 0;
66 sched_pset_search_order_t spill_order;
67 for (int i = 0; i < MAX_PSETS - 1; i++, other_pset_id++) {
68 if (i < sched_num_psets - 1) {
69 if (other_pset_id == src_pset->pset_id) {
70 /* Exclude the source pset */
71 other_pset_id++;
72 }
73 assert3u(other_pset_id, <, sched_num_psets);
74 spill_order.spso_search_order[i] = other_pset_id;
75 } else {
76 /* Mark unneeded slots with an invalid id, as they should not be accessed */
77 spill_order.spso_search_order[i] = PSET_ID_INVALID;
78 }
79 }
80 os_atomic_store_wide(&search_order_out->spso_packed, spill_order.spso_packed, relaxed);
81 }
82
83 static bool
sched_iterate_psets_ordered_reversed(processor_set_t starting_pset,uint64_t candidate_map,sched_pset_iterate_state_t * istate)84 sched_iterate_psets_ordered_reversed(processor_set_t starting_pset,
85 uint64_t candidate_map, sched_pset_iterate_state_t *istate)
86 {
87 assert3u(istate->spis_options, &, SCHED_PSET_ITERATE_STATE_OPTIONS_REVERSE);
88 while ((istate->spis_search_index < sched_num_psets)) {
89 int pset_id;
90 if (istate->spis_search_index == -1) {
91 /* In case search order does not include all psets, count how many it does have. */
92 istate->spis_valid_len = 0;
93 while ((istate->spis_cached_search_order.spso_search_order[istate->spis_valid_len] != PSET_ID_INVALID)
94 && (istate->spis_valid_len <= (sched_num_psets - 2))) {
95 istate->spis_valid_len++;
96 }
97 istate->spis_search_index++;
98 }
99 if (istate->spis_search_index == istate->spis_valid_len) {
100 /* Return starting_pset last */
101 pset_id = starting_pset->pset_id;
102 } else {
103 int index = istate->spis_valid_len - 1 - istate->spis_search_index;
104 assert3s(index, >=, 0);
105 pset_id = istate->spis_cached_search_order.spso_search_order[index];
106 assert3s(pset_id, !=, PSET_ID_INVALID);
107 assert3u(pset_id, !=, starting_pset->pset_id);
108 }
109 istate->spis_search_index++;
110 if (bit_test(candidate_map, pset_id)) {
111 istate->spis_pset_id = (pset_id_t)pset_id;
112 return true;
113 }
114 }
115 istate->spis_pset_id = PSET_ID_INVALID;
116 return false;
117 }
118
119 bool
sched_iterate_psets_ordered(processor_set_t starting_pset,sched_pset_search_order_t * search_order,uint64_t candidate_map,sched_pset_iterate_state_t * istate)120 sched_iterate_psets_ordered(processor_set_t starting_pset, sched_pset_search_order_t *search_order,
121 uint64_t candidate_map, sched_pset_iterate_state_t *istate)
122 {
123 if (candidate_map == 0) {
124 istate->spis_pset_id = PSET_ID_INVALID;
125 return false;
126 }
127 if (istate->spis_search_index == -1) {
128 istate->spis_cached_search_order =
129 (sched_pset_search_order_t)os_atomic_load_wide(&search_order->spso_packed, relaxed);
130 }
131 bool reverse = (istate->spis_options & SCHED_PSET_ITERATE_STATE_OPTIONS_REVERSE);
132 if (reverse) {
133 return sched_iterate_psets_ordered_reversed(starting_pset, candidate_map, istate);
134 } else {
135 while (istate->spis_search_index < sched_num_psets - 1) {
136 int pset_id;
137 if (istate->spis_search_index == -1) {
138 pset_id = starting_pset->pset_id;
139 } else {
140 int index = istate->spis_search_index;
141 assert3s(index, >=, 0);
142 pset_id = istate->spis_cached_search_order.spso_search_order[index];
143 if (pset_id == PSET_ID_INVALID) {
144 /* The given search order does not include all psets */
145 break;
146 }
147 assert3u(pset_id, !=, starting_pset->pset_id);
148 }
149 istate->spis_search_index++;
150 if (bit_test(candidate_map, pset_id)) {
151 istate->spis_pset_id = (pset_id_t)pset_id;
152 return true;
153 }
154 }
155 istate->spis_pset_id = PSET_ID_INVALID;
156 return false;
157 }
158 }
159
160 #endif /* __AMP__ */
161