==> src/place_mode.c <==1/* place.rs: Assign, Mode, Target, Role and their rules. */
2#include "mesh/place_mode.h"
3#include "mesh/abi/base.h"
4#include "mesh/parse.h"
5#include "mesh/rust_fmt.h"
6#include "mesh/mt.h"
7
8#include <stdlib.h>
9#include <string.h>
10
11uint32_t mpm_bits(uint32_t n) { return n >= 32 ? UINT32_MAX : (1u << n) - 1; }
12
13mpm_assign mpm_assign_new(const uint32_t *of, size_t n) {
14 mpm_assign a;
15 a.fanout = (uint32_t)n;
16 memset(a.of, MESH_PART_NONE, sizeof a.of);
17 for (size_t b = 0; b < n && b < MESH_PLACE_PARTS_MAX; b++) a.of[b] = (uint8_t)of[b];
18 return a;
19}
20
21uint32_t mpm_owner(const mpm_assign *a) { return a->of[0]; }
22
23uint32_t mpm_mask_of(const mpm_assign *a, uint32_t sys) {
24 uint32_t m = 0;
25 for (uint32_t b = 0; b < a->fanout; b++)
26 if (a->of[b] == sys) m |= 1u << b;
27 return m;
28}
29
30uint32_t mpm_members(const mpm_assign *a) {
31 uint32_t m = 0;
32 for (uint32_t b = 0; b < a->fanout; b++) m |= 1u << a->of[b];
33 return m;
34}
35
36char *mpm_list(const mpm_assign *a) {
37 mt_buf b = {0};
38 for (uint32_t i = 0; i < a->fanout; i++) mt_printf(&b, i ? ",%u" : "%u", a->of[i]);
39 return mt_take(&b);
40}
41
42mpm_assign mpm_counts(const uint32_t *sys, const uint32_t *count, size_t n) {
43 uint32_t of[MESH_PLACE_PARTS_MAX];
44 size_t k = 0;
45 for (size_t i = 0; i < n; i++)
46 for (uint32_t j = 0; j < count[i] && k < MESH_PLACE_PARTS_MAX; j++) of[k++] = sys[i];
47 return mpm_assign_new(of, k);
48}
49
50mpm_assign mpm_even(const uint32_t *systems, size_t n, uint32_t fanout) {
51 uint32_t k = (uint32_t)n < fanout ? (uint32_t)n : fanout;
52 if (k < 1) k = 1;
53 uint32_t count[MESH_PLACE_PARTS_MAX];
54 for (uint32_t i = 0; i < k; i++) count[i] = fanout / k + (i < fanout % k);
55 return mpm_counts(systems, count, k);
56}
57
58mpm_assign mpm_auto(const uint32_t *sys, const uint32_t *ns, size_t n, uint32_t fanout) {
59 uint64_t sum = 0, known = 0;
60 for (size_t i = 0; i < n; i++)
61 if (ns[i] > 0) sum += ns[i], known++;
62 uint64_t fill = known ? sum / known : 1;
63 uint64_t t[MESH_PLACE_PARTS_MAX];
64 uint32_t count[MESH_PLACE_PARTS_MAX] = {0};
65 for (size_t i = 0; i < n; i++) t[i] = ns[i] > 0 ? ns[i] : fill;
66 for (uint32_t p = 0; p < fanout; p++) {
67 size_t best = 0;
68 for (size_t i = 1; i < n; i++) {
69 uint64_t ki = (count[i] + 1ull) * t[i], kb = (count[best] + 1ull) * t[best];
70 if (ki < kb || (ki == kb && sys[i] < sys[best])) best = i;
71 }
72 count[best]++;
73 }
74 size_t fastest = n;
75 for (size_t i = 0; i < n; i++)
76 if (count[i] > 0 && (fastest == n || t[i] < t[fastest] || (t[i] == t[fastest] && sys[i] < sys[fastest]))) fastest = i;
77 uint32_t os[MESH_PLACE_PARTS_MAX], oc[MESH_PLACE_PARTS_MAX];
78 size_t k = 0;
79 os[k] = sys[fastest], oc[k++] = count[fastest];
80 for (size_t i = 0; i < n; i++)
81 if (i != fastest && count[i] > 0) os[k] = sys[i], oc[k++] = count[i];
82 return mpm_counts(os, oc, k);
83}
84
85bool mpm_assign_eq(const mpm_assign *a, const mpm_assign *b) { return a->fanout == b->fanout && memcmp(a->of, b->of, sizeof a->of) == 0; }
86
87static bool check(const mpm_assign *a, uint32_t n, char **err) {
88 if (a->fanout == 0 || a->fanout > MESH_PLACE_PARTS_MAX) {
89 *err = mt_fmt("split of %u parts", a->fanout);
90 return false;
91 }
92 for (uint32_t b = 0; b < a->fanout; b++)
93 if (a->of[b] >= n) {
94 *err = mt_fmt("split: part %u to system %u, the cluster has systems 0..%u", b, a->of[b], n - 1);
95 return false;
96 }
97 return true;
98}
99
100mpm_mode mpm_local(void) { return (mpm_mode){.kind = MPM_LOCAL}; }
101mpm_mode mpm_pin(uint32_t k) { return (mpm_mode){.kind = MPM_PIN, .pin = k}; }
102mpm_mode mpm_split(mpm_assign a) { return (mpm_mode){.kind = MPM_SPLIT, .a = a}; }
103
104bool mpm_mode_eq(const mpm_mode *a, const mpm_mode *b) {
105 if (a->kind != b->kind) return false;
106 if (a->kind == MPM_PIN) return a->pin == b->pin;
107 if (a->kind == MPM_SPLIT) return mpm_assign_eq(&a->a, &b->a);
108 return true;
109}
110
111bool mpm_target_eq(const mpm_target *a, const mpm_target *b) {
112 if (a->is_auto != b->is_auto) return false;
113 return a->is_auto ? a->auto_mask == b->auto_mask : mpm_mode_eq(&a->mode, &b->mode);
114}
115
116static char *usage(char *const *words, size_t nwords, uint32_t n) {
117 mt_strs w = {0};
118 for (size_t i = 0; i < nwords; i++) mt_push(&w, words[i]);
119 char *j = mt_join(&w, " ");
120 char *q = rf_debug_str(j);
121 char *e = mt_fmt("usage: place <name> [local | pin 0..%u | split [auto | a,b,.. | a:parts,b:parts,..]], not %s", n - 1, q);
122 free(j), free(q);
123 mt_strs_free(&w);
124 return e;
125}
126
127static bool sys_word(const char *w, uint32_t n, uint32_t *k, char **err) {
128 if (mp_u32(w, k) && *k < n) return true;
129 char *q = rf_debug_str(w);
130 *err = mt_fmt("%s: not a system of this cluster (0..%u)", q, n - 1);
131 free(q);
132 return false;
133}
134
135static bool split_spec(const char *spec, uint32_t n, uint32_t fanout, mpm_target *out, char **err, char *const *words, size_t nwords) {
136 mt_strs items = mt_split(spec, ',');
137 bool colon = false, ok = false;
138 for (size_t i = 0; i < items.n; i++)
139 if (strchr(items.v[i], ':')) colon = true;
140 uint32_t ks[64], ps[64];
141 size_t c = 0;
142 if (items.n > 64) {
143 *err = mt_fmt("split %s: %zu systems for %u parts", spec, items.n, fanout);
144 goto done;
145 }
146 if (colon) {
147 for (size_t i = 0; i < items.n; i++) {
148 char *k, *p;
149 if (!mt_split_once(items.v[i], ':', &k, &p)) {
150 *err = usage(words, nwords, n);
151 goto done;
152 }
153 uint32_t parts;
154 bool pok = mp_u32(p, &parts);
155 if (!pok || parts == 0) {
156 char *q = rf_debug_str(items.v[i]);
157 *err = mt_fmt(pok ? "%s: at least one part" : "%s: system:parts", q);
158 free(q), free(k), free(p);
159 goto done;
160 }
161 uint32_t s;
162 bool sok = sys_word(k, n, &s, err);
163 free(k), free(p);
164 if (!sok) goto done;
165 ks[c] = s, ps[c++] = parts;
166 }
167 uint32_t total = 0;
168 for (size_t i = 0; i < c; i++) total += ps[i];
169 if (total != fanout) {
170 *err = mt_fmt("split %s: %u parts, the program has %u", spec, total, fanout);
171 goto done;
172 }
173 for (size_t i = 1; i < c; i++)
174 for (size_t j = 0; j < i; j++)
175 if (ks[j] == ks[i]) {
176 *err = mt_fmt("split %s: a system twice", spec);
177 goto done;
178 }
179 *out = (mpm_target){.mode = mpm_split(mpm_counts(ks, ps, c))};
180 ok = true;
181 } else {
182 for (size_t i = 0; i < items.n; i++) {
183 if (!sys_word(items.v[i], n, &ks[c], err)) goto done;
184 c++;
185 }
186 if (c == fanout) *out = (mpm_target){.mode = mpm_split(mpm_assign_new(ks, c))};
187 else if (c > fanout) {
188 *err = mt_fmt("split %s: %zu systems for %u parts", spec, c, fanout);
189 goto done;
190 } else {
191 for (size_t i = 1; i < c; i++)
192 for (size_t j = 0; j < i; j++)
193 if (ks[j] == ks[i]) {
194 *err = mt_fmt("split %s: a system twice (list %u systems to give one per part)", spec, fanout);
195 goto done;
196 }
197 *out = (mpm_target){.mode = mpm_split(mpm_even(ks, c, fanout))};
198 }
199 ok = true;
200 }
201done:
202 mt_strs_free(&items);
203 return ok;
204}
205
206bool mpm_parse(char *const *words, size_t nwords, uint32_t n, uint32_t fanout, mpm_target *out, char **err) {
207 if (nwords == 1 && strcmp(words[0], "local") == 0) return *out = (mpm_target){.mode = mpm_local()}, true;
208 if (nwords == 2 && strcmp(words[0], "pin") == 0) {
209 uint32_t k;
210 if (!sys_word(words[1], n, &k, err)) return false;
211 return *out = (mpm_target){.mode = mpm_pin(k)}, true;
212 }
213 if (nwords == 1 && strcmp(words[0], "split") == 0) {
214 uint32_t all[MESH_PLACE_PARTS_MAX];
215 for (uint32_t k = 0; k < n && k < MESH_PLACE_PARTS_MAX; k++) all[k] = k;
216 return *out = (mpm_target){.mode = mpm_split(mpm_even(all, n, fanout))}, true;
217 }
218 if (nwords == 2 && strcmp(words[0], "split") == 0 && strcmp(words[1], "auto") == 0) return *out = (mpm_target){.is_auto = true, .auto_mask = mpm_bits(n)}, true;
219 if (nwords == 2 && strcmp(words[0], "split") == 0) return split_spec(words[1], n, fanout, out, err, words, nwords);
220 *err = usage(words, nwords, n);
221 return false;
222}
223
224void mpm_code(const mpm_mode *m, uint32_t *code, uint32_t *sys) {
225 switch (m->kind) {
226 case MPM_LOCAL: *code = MESH_PLACE_LOCAL, *sys = 0; break;
227 case MPM_PIN: *code = MESH_PLACE_PIN, *sys = m->pin; break;
228 default: *code = MESH_PLACE_SPLIT, *sys = mpm_owner(&m->a);
229 }
230}
231
232void mpm_assign_bytes(const mpm_mode *m, uint8_t out[MESH_PLACE_PARTS_MAX]) {
233 if (m->kind == MPM_SPLIT) memcpy(out, m->a.of, MESH_PLACE_PARTS_MAX);
234 else memset(out, MESH_PART_NONE, MESH_PLACE_PARTS_MAX);
235}
236
237bool mpm_from_code(uint32_t code, uint32_t sys, const uint8_t *assign, size_t n, mpm_mode *out, char **err) {
238 if (code == MESH_PLACE_LOCAL) return *out = mpm_local(), true;
239 if (code == MESH_PLACE_PIN && sys < MESH_MAX_SYSTEMS) return *out = mpm_pin(sys), true;
240 if (code == MESH_PLACE_SPLIT) {
241 size_t fanout = n;
242 for (size_t i = 0; i < n; i++)
243 if (assign[i] == MESH_PART_NONE) {
244 fanout = i;
245 break;
246 }
247 uint32_t of[MESH_PLACE_PARTS_MAX];
248 for (size_t i = 0; i < fanout && i < MESH_PLACE_PARTS_MAX; i++) of[i] = assign[i];
249 mpm_assign a = mpm_assign_new(of, fanout);
250 if (!check(&a, MESH_MAX_SYSTEMS, err)) return false;
251 for (size_t i = fanout; i < n; i++)
252 if (assign[i] != MESH_PART_NONE) {
253 *err = mt_strdup("split: a gap in the assignment");
254 return false;
255 }
256 if (mpm_owner(&a) != sys) {
257 *err = mt_fmt("split: owner %u, part 0 is system %u's", sys, mpm_owner(&a));
258 return false;
259 }
260 *out = mpm_split(a);
261 return true;
262 }
263 *err = mt_fmt("bad placement %u/%u", code, sys);
264 return false;
265}
266
267char *mpm_label(const mpm_mode *m) {
268 if (m->kind == MPM_LOCAL) return mt_strdup("local");
269 if (m->kind == MPM_PIN) return mt_fmt("pin %u", m->pin);
270 char *l = mpm_list(&m->a), *s = mt_fmt("split %s", l);
271 free(l);
272 return s;
273}
274
275bool mpm_allowed(const mpm_mode *m, uint32_t cap, char **err) {
276 if (cap == MESH_PLACE_CAP_NONE) {
277 *err = mt_strdup("declares no `place` in its manifest");
278 return false;
279 }
280 if (m->kind == MPM_SPLIT && cap == MESH_PLACE_CAP_PIN) {
281 *err = mt_strdup("declares place = \"pin\" only (no split)");
282 return false;
283 }
284 return true;
285}
286
287bool mpm_fits(const mpm_mode *m, uint32_t n, uint32_t fanout, char **err) {
288 if (m->kind == MPM_LOCAL) return true;
289 if (m->kind == MPM_PIN) {
290 if (m->pin < n) return true;
291 *err = mt_fmt("pin %u: the cluster has systems 0..%u", m->pin, n - 1);
292 return false;
293 }
294 if (m->a.fanout != fanout) {
295 *err = mt_fmt("split of %u parts, the program has %u", m->a.fanout, fanout);
296 return false;
297 }
298 return check(&m->a, n, err);
299}
300
301mpm_role mpm_role_of(const mpm_mode *m, uint32_t me) {
302 switch (m->kind) {
303 case MPM_LOCAL: return MPM_ROLE_LOCAL;
304 case MPM_PIN: return m->pin == me ? MPM_ROLE_RUNNER : MPM_ROLE_MIRROR;
305 default:
306 if (mpm_owner(&m->a) == me) return MPM_ROLE_OWNER;
307 return mpm_mask_of(&m->a, me) ? MPM_ROLE_FOLLOWER : MPM_ROLE_MIRROR;
308 }
309}
310
311bool mpm_runs(mpm_role r) { return r != MPM_ROLE_MIRROR; }
312
313uint32_t mpm_input_to(const mpm_mode *m, uint32_t me) {
314 return m->kind == MPM_LOCAL ? me : m->kind == MPM_PIN ? m->pin : mpm_owner(&m->a);
315}
316
317uint32_t mpm_parts_of(const mpm_mode *m, uint32_t sys, uint32_t fanout) {
318 if (m->kind == MPM_LOCAL) return 0;
319 if (m->kind == MPM_PIN) return m->pin == sys ? mpm_bits(fanout) : 0;
320 return mpm_mask_of(&m->a, sys);
321}
322
323uint32_t mpm_authority(const mpm_mode *from, const mpm_mode *to) {
324 if (from->kind == MPM_PIN) return from->pin;
325 if (from->kind == MPM_SPLIT) return mpm_owner(&from->a);
326 if (to->kind == MPM_PIN) return to->pin;
327 if (to->kind == MPM_SPLIT) return mpm_owner(&to->a);
328 return 0;
329}