==> src/sched_place.c <==1/* sched.rs: Input, Explain, order, members_of_at, Books, rows, sorted_ok, place, group_choice,
2 * group_score. */
3#include "mesh/sched_place.h"
4#include "mesh/mt.h"
5
6#include <math.h>
7#include <stdlib.h>
8#include <string.h>
9
10static uint32_t div_ceil(uint32_t a, uint32_t b) { return a / b + (a % b != 0); }
11
12/* ---- explain */
13
14static int row_order(const msp_row *a, const msp_row *b) {
15 if (a->ok && b->ok) {
16 if (b->score.total > a->score.total) return 1;
17 if (b->score.total < a->score.total) return -1;
18 return a->k < b->k ? -1 : a->k > b->k;
19 }
20 if (a->ok) return -1;
21 if (b->ok) return 1;
22 return a->k < b->k ? -1 : a->k > b->k;
23}
24
25char *msp_explain_text(const msp_explain *e) {
26 mt_buf b = {0};
27 char *on = e->chosen.some ? ml_text(&e->chosen.l) : NULL;
28 if (on) mt_printf(&b, "program %s on %s: %s\n needs %s\n", e->program, on, e->summary, e->needs);
29 else mt_printf(&b, "program %s on every eligible member: %s\n needs %s\n", e->program, e->summary, e->needs);
30 free(on);
31 /* A stable sort of the rows: feasible first, best score first, then by id. */
32 size_t n = e->nrows;
33 const msp_row **r = mt_alloc((n ? n : 1) * sizeof *r);
34 for (size_t i = 0; i < n; i++) r[i] = &e->rows[i];
35 for (size_t i = 1; i < n; i++)
36 for (size_t j = i; j > 0 && row_order(r[j - 1], r[j]) > 0; j--) {
37 const msp_row *t = r[j - 1];
38 r[j - 1] = r[j];
39 r[j] = t;
40 }
41 for (size_t i = 0; i < n; i++) {
42 bool chosen = ml_opt_has_or_all(&e->chosen, r[i]->k) && r[i]->ok;
43 if (r[i]->ok) {
44 char *x = msc_explain(&r[i]->score);
45 mt_printf(&b, " system %u %s score %s\n", r[i]->k, chosen ? "chosen " : "feasible", x);
46 free(x);
47 } else mt_printf(&b, " system %u rejected %s\n", r[i]->k, r[i]->why);
48 }
49 free(r);
50 return mt_take(&b);
51}
52
53bool msp_score_of(const msp_explain *e, uint32_t k, double *score) {
54 for (size_t i = 0; i < e->nrows; i++)
55 if (e->rows[i].k == k) {
56 if (!e->rows[i].ok) return false;
57 *score = e->rows[i].score.total;
58 return true;
59 }
60 return false;
61}
62
63void msp_rows_free(msp_row *rows, size_t n) {
64 for (size_t i = 0; i < n; i++) free(rows[i].why);
65 free(rows);
66}
67
68void msp_explain_free(msp_explain *e) {
69 free(e->program);
70 free(e->needs);
71 free(e->summary);
72 msp_rows_free(e->rows, e->nrows);
73 ml_opt_free(&e->chosen);
74 *e = (msp_explain){0};
75}
76
77void msp_explains_free(msp_explains *e) {
78 for (size_t i = 0; i < e->n; i++) msp_explain_free(&e->v[i]);
79 free(e->v);
80 *e = (msp_explains){0};
81}
82
83const msp_explain *msp_explains_get(const msp_explains *e, const char *program) {
84 for (size_t i = 0; i < e->n; i++)
85 if (strcmp(e->v[i].program, program) == 0) return &e->v[i];
86 return NULL;
87}
88
89/* ---- order */
90
91typedef struct {
92 int64_t neg_priority;
93 uint32_t depth;
94 const char *name;
95} okey;
96
97static int okey_cmp(const void *a, const void *b) {
98 const okey *x = a, *y = b;
99 if (x->neg_priority != y->neg_priority) return x->neg_priority < y->neg_priority ? -1 : 1;
100 if (x->depth != y->depth) return x->depth < y->depth ? -1 : 1;
101 return strcmp(x->name, y->name);
102}
103
104mt_strs msp_order(const mfd_doc *doc) {
105 okey *k = mt_alloc((doc->nprogs ? doc->nprogs : 1) * sizeof *k);
106 for (size_t i = 0; i < doc->nprogs; i++) {
107 uint32_t depth = 0;
108 const char *cur = doc->pname[i];
109 mt_strs seen = {0};
110 for (;;) {
111 const mfd_prog *p = mfd_prog_get(doc, cur);
112 if (!p || !p->needs.colocate_with) break;
113 const char *a = p->needs.colocate_with;
114 if (!mfd_prog_get(doc, a) || mt_strs_has(&seen, a)) break;
115 mt_push(&seen, a);
116 depth++;
117 cur = a;
118 }
119 mt_strs_free(&seen);
120 k[i] = (okey){-(int64_t)doc->prog[i].needs.priority, depth, doc->pname[i]};
121 }
122 qsort(k, doc->nprogs, sizeof *k, okey_cmp);
123 mt_strs out = {0};
124 for (size_t i = 0; i < doc->nprogs; i++) mt_push(&out, k[i].name);
125 free(k);
126 return out;
127}
128
129ml_list msp_members_of_at(const ml_opt *at, const msm_member *ms, size_t nms, const mesh_needs *n) {
130 if (at->some) return ml_clone(&at->l);
131 ml_list l = {0};
132 for (size_t i = 0; i < nms; i++)
133 if (msc_eligible(&ms[i], n)) ml_push(&l, ms[i].id);
134 return l;
135}
136
137/* ---- books */
138
139msp_books msp_books_new(size_t n) {
140 size_t c = n ? n : 1;
141 return (msp_books){n, mt_alloc(c * sizeof(uint32_t)), mt_alloc(c * sizeof(uint32_t)), mt_alloc(c * sizeof(uint32_t)), mt_alloc(c * sizeof(uint32_t)),
142 mt_alloc(c * sizeof(float))};
143}
144
145void msp_books_free(msp_books *b) {
146 free(b->placed), free(b->mem), free(b->view_kb), free(b->nnew), free(b->cpu);
147 *b = (msp_books){0};
148}
149
150void msp_books_add(msp_books *b, uint32_t k, const mesh_needs *n) {
151 if (k >= b->n) return;
152 b->placed[k] += 1;
153 b->cpu[k] += n->cpu;
154 b->mem[k] += n->mem_mb;
155}
156
157/* A placement made in this pass on a member that does not hold it yet: its view and slot. */
158static void books_add_new(msp_books *b, uint32_t k, const mesh_needs *n) {
159 if (k >= b->n) return;
160 b->view_kb[k] += div_ceil(n->view_bytes, 1024);
161 b->nnew[k] += 1;
162}
163
164static uint32_t books_max(const msp_books *b) {
165 uint32_t m = 0;
166 for (size_t i = 0; i < b->n; i++)
167 if (b->placed[i] > m) m = b->placed[i];
168 return m;
169}
170
171/* The reservations fit (the budget is the member's CPUs and RAM less the reserve), and the view and
172 * a slot (a member that holds it already has both). */
173static bool books_fits(const msp_books *b, const msm_member *m, const mesh_needs *n, const msw_weights *w, bool current, char **err) {
174 uint32_t i = m->id;
175 if (!current && m->heap_kb > 0) {
176 uint32_t want = div_ceil(n->view_bytes, 1024) + b->view_kb[i];
177 if (want > m->heap_kb) {
178 char *extra = b->view_kb[i] > 0 ? mt_fmt(" (%u KiB placed there in this pass)", b->view_kb[i]) : mt_strdup("");
179 *err = mt_fmt("view heap: %u KiB wanted, its largest free run is %u KiB%s", div_ceil(n->view_bytes, 1024), m->heap_kb, extra);
180 free(extra);
181 return false;
182 }
183 if (m->slots_free <= b->nnew[i]) {
184 *err = mt_fmt("no free program slot (%u free)", m->slots_free);
185 return false;
186 }
187 }
188 float cpu = current ? b->cpu[i] - n->cpu : b->cpu[i];
189 uint32_t mem = current ? (b->mem[i] > n->mem_mb ? b->mem[i] - n->mem_mb : 0) : b->mem[i];
190 if (n->cpu > 0.0f) {
191 float budget = (float)m->cpus * (1.0f - w->reserve);
192 if (cpu + n->cpu > budget + 1e-6f) {
193 *err = mt_fmt("cpu %.2f: %.2f of %.2f cores reserved (%u CPUs less %.0f %%)", (double)n->cpu, (double)cpu, (double)budget, m->cpus, (double)(w->reserve * 100.0f));
194 return false;
195 }
196 }
197 if (n->mem_mb > 0) {
198 uint32_t budget = (uint32_t)((float)m->ram_mb * (1.0f - w->reserve));
199 if (mem + n->mem_mb > budget) {
200 *err = mt_fmt("mem_mb %u: %u of %u MiB reserved", n->mem_mb, mem, budget);
201 return false;
202 }
203 }
204 return true;
205}
206
207static mof32 best_task_us(const msm_perfs *perf, const char *name, uint64_t hash) {
208 size_t lo, hi;
209 msm_perfs_range(perf, name, &lo, &hi);
210 mof32 best = mof32_none();
211 for (size_t i = lo; i < hi; i++) {
212 const msm_perf *p = &perf->perf[i];
213 if (p->hash != hash || !p->task_us.some || !(p->task_us.v > 0.0f)) continue;
214 best = best.some ? mof32_some(fminf(best.v, p->task_us.v)) : p->task_us;
215 }
216 return best;
217}
218
219/* The CPU a program uses: measured where it runs (the most of its replicas), else its reservation. */
220static float own_cpu(const msm_perfs *perf, const char *name, uint64_t hash, const mesh_needs *n) {
221 size_t lo, hi;
222 msm_perfs_range(perf, name, &lo, &hi);
223 float c = n->cpu;
224 for (size_t i = lo; i < hi; i++)
225 if (perf->perf[i].hash == hash && perf->perf[i].run) c = fmaxf(c, perf->perf[i].cpu);
226 return c;
227}
228
229void msp_rows(const msp_input *in, const char *name, const ml_list *current, const msp_books *books, const ml_list *anchor, msp_row **rows, size_t *nrows) {
230 const mfd_prog *p = mfd_prog_get(in->doc, name);
231 const mesh_needs *n = &p->needs;
232 mof32 best = best_task_us(in->perf, name, p->hash);
233 float own = own_cpu(in->perf, name, p->hash, n);
234 uint32_t maxp = books_max(books);
235 msp_row *r = mt_alloc((in->nmembers ? in->nmembers : 1) * sizeof *r);
236 for (size_t i = 0; i < in->nmembers; i++) {
237 const msm_member *m = &in->members[i];
238 bool cur = ml_has(current, m->id);
239 char exec[16], *err = NULL;
240 r[i].k = m->id;
241 r[i].why = NULL;
242 r[i].ok = false;
243 if (!msc_filter(m, n, exec, &err)) {
244 r[i].why = err;
245 continue;
246 }
247 const char *f = ms_get(&m->fails, name);
248 if (f) {
249 r[i].why = mt_fmt("failed here: %s", f);
250 continue;
251 }
252 if (!books_fits(books, m, n, in->w, cur, &err)) {
253 r[i].why = err;
254 continue;
255 }
256 if (anchor && !ml_has(anchor, m->id)) {
257 r[i].why = mt_fmt("colocate_with %s: not there", n->colocate_with ? n->colocate_with : "?");
258 continue;
259 }
260 const msm_perf *here = msm_perfs_get(in->perf, name, m->id);
261 if (here && here->hash != p->hash) here = NULL;
262 uint32_t placed = books->placed[m->id] > (uint32_t)cur ? books->placed[m->id] - (uint32_t)cur : 0;
263 msc_cx cx = {.w = in->w, .current = cur, .here = here, .best_task_us = best, .own_cpu = own, .placed = placed, .max_placed = maxp};
264 r[i].ok = true;
265 r[i].score = msc_score_terms(m, n, &cx);
266 }
267 *rows = r;
268 *nrows = in->nmembers;
269}
270
271size_t msp_sorted_ok(const msp_row *rows, size_t n, uint32_t *ks, double *totals) {
272 size_t c = 0;
273 for (size_t i = 0; i < n; i++)
274 if (rows[i].ok) {
275 /* insertion, stable: best total first, then the lower id */
276 size_t j = c++;
277 while (j > 0 && (totals[j - 1] < rows[i].score.total || (totals[j - 1] == rows[i].score.total && ks[j - 1] > rows[i].k))) {
278 ks[j] = ks[j - 1];
279 totals[j] = totals[j - 1];
280 j--;
281 }
282 ks[j] = rows[i].k;
283 totals[j] = rows[i].score.total;
284 }
285 return c;
286}
287
288/* ---- place */
289
290static bool row_valid(const msp_row *r, size_t n, uint32_t k) {
291 for (size_t i = 0; i < n; i++)
292 if (r[i].k == k && r[i].ok) return true;
293 return false;
294}
295
296static bool grace(const msp_input *in, uint32_t k) {
297 return k < in->nmembers && !in->members[k].up && in->members[k].down_ms < in->w->replace_ms;
298}
299
300static double score_or(const msp_explain *e, uint32_t k, double d) {
301 double s;
302 return msp_score_of(e, k, &s) ? s : d;
303}
304
305mfd_doc msp_place(const msp_input *in, mt_strs *changes, msp_explains *explains) {
306 mfd_doc doc = mfd_doc_clone(in->doc);
307 *changes = (mt_strs){0};
308 *explains = (msp_explains){0};
309 msp_books books = msp_books_new(in->nmembers);
310 const msm_member *ms = in->members;
311 size_t nms = in->nmembers;
312 mt_strs ord = msp_order(in->doc);
313 for (size_t oi = 0; oi < ord.n; oi++) {
314 const char *name = ord.v[oi];
315 mfd_prog p = mfd_prog_clone(mfd_prog_get(&doc, name));
316 const mesh_needs *n = &p.needs;
317 /* Where it runs now (a new program with replicas N: nowhere yet). */
318 ml_list cur = (!p.at.some && !n->replicas.all && !n->colocate_with) ? (ml_list){0} : msp_members_of_at(&p.at, ms, nms, n);
319 /* Colocated: the anchor's members (an anchor not in the document: no constraint). */
320 bool has_anchor = false;
321 ml_list anchor = {0};
322 if (n->colocate_with) {
323 const mfd_prog *a = mfd_prog_get(&doc, n->colocate_with);
324 if (a) {
325 has_anchor = true;
326 anchor = msp_members_of_at(&a->at, ms, nms, &a->needs);
327 }
328 }
329 msp_input view = {&doc, ms, nms, in->perf, in->w};
330 msp_row *r;
331 size_t nr;
332 msp_rows(&view, name, &cur, &books, has_anchor ? &anchor : NULL, &r, &nr);
333 msp_explain ex = {mt_strdup(name), msn_summary(n), NULL, NULL, 0, ml_opt_clone(&p.at)};
334 ex.rows = mt_alloc((nr ? nr : 1) * sizeof *ex.rows);
335 for (size_t i = 0; i < nr; i++) ex.rows[i] = (msp_row){r[i].k, r[i].ok, r[i].score, r[i].why ? mt_strdup(r[i].why) : NULL};
336 ex.nrows = nr;
337 uint32_t *ok_k = mt_alloc((nr ? nr : 1) * sizeof *ok_k);
338 double *ok_s = mt_alloc((nr ? nr : 1) * sizeof *ok_s);
339 size_t nok = msp_sorted_ok(r, nr, ok_k, ok_s);
340 ml_opt want = ml_opt_clone(&p.at);
341 char *why = mt_strdup(p.why);
342 /* A pin of a program colocated with another (the anchor) is not applied: it would split the pair. */
343 const ml_opt *pin = p.pin.some && !has_anchor ? &p.pin : NULL;
344 if (p.has_from) {
345 ex.summary = mt_fmt("migrating from system %u (the leader runs it)", p.from);
346 } else if (pin) {
347 bool moving = false;
348 if (p.at.some && !ml_eq(&p.at.l, &pin->l) && p.at.l.n && n->migrate == MESH_MIGRATE_STATE) {
349 moving = true;
350 for (size_t i = 0; i < p.at.l.n; i++)
351 if (p.at.l.v[i] >= nms || !ms[p.at.l.v[i]].up) moving = false;
352 }
353 char *pl = ml_text(&pin->l);
354 if (moving) ex.summary = mt_fmt("pinned by the operator to %s: the leader migrates it there (with its view)", pl);
355 else {
356 ml_opt_free(&want);
357 want = ml_opt_clone(pin);
358 free(why);
359 why = mt_fmt("pinned by the operator to %s", pl);
360 ex.summary = mt_strdup(why);
361 }
362 free(pl);
363 } else if (n->lockstep) {
364 ml_opt_free(&want);
365 ex.summary = mt_strdup("the lockstep program: loaded on every eligible member; its group's members run it");
366 } else if (has_anchor) {
367 ml_list v = {0}, lost = {0};
368 for (size_t i = 0; i < anchor.n; i++) {
369 uint32_t k = anchor.v[i];
370 bool valid = row_valid(r, nr, k), g = grace(in, k);
371 if (valid || (g && p.at.some && ml_has(&p.at.l, k))) ml_push(&v, k);
372 if (!valid && !g) ml_push(&lost, k);
373 }
374 char *al = ml_text(&anchor), *ll = ml_text(&lost);
375 char *extra = lost.n ? mt_fmt("; cannot run on %s", ll) : mt_strdup("");
376 ex.summary = mt_fmt("colocated with %s (on %s)%s", n->colocate_with, al, extra);
377 free(al), free(ll), free(extra);
378 if (!(p.at.some && ml_eq(&p.at.l, &v))) {
379 free(why);
380 why = mt_strdup(ex.summary);
381 }
382 ml_opt_free(&want);
383 want = (ml_opt){true, v};
384 ml_free(&lost);
385 } else if (n->replicas.all) {
386 ml_opt_free(&want);
387 ex.summary = mt_fmt("replicas all: on the %zu eligible member(s)", nok);
388 } else {
389 uint32_t k = n->replicas.n;
390 ml_list keep = {0}, dropped = {0}, added = {0};
391 if (p.at.some)
392 for (size_t i = 0; i < p.at.l.n; i++) {
393 uint32_t m = p.at.l.v[i];
394 if (row_valid(r, nr, m) || grace(in, m)) ml_push(&keep, m);
395 }
396 if (p.at.some)
397 for (size_t i = 0; i < p.at.l.n; i++)
398 if (!ml_has(&keep, p.at.l.v[i])) ml_push(&dropped, p.at.l.v[i]);
399 /* Too many: the lowest scores go (ties: the higher id). */
400 while (keep.n > k) {
401 size_t w = 0;
402 for (size_t i = 1; i < keep.n; i++) {
403 double si = score_or(&ex, keep.v[i], -1.0), sw = score_or(&ex, keep.v[w], -1.0);
404 if (si < sw || (si == sw && keep.v[w] < keep.v[i])) w = i;
405 }
406 ml_remove_value(&keep, keep.v[w]);
407 }
408 for (size_t i = 0; i < nok && keep.n < k; i++)
409 if (!ml_has(&keep, ok_k[i])) ml_push(&keep, ok_k[i]), ml_push(&added, ok_k[i]);
410 ml_sort(&keep);
411 mt_buf s = {0};
412 if (!keep.n) {
413 mt_strs rej = {0};
414 for (size_t i = 0; i < nr; i++)
415 if (!r[i].ok) mt_push_own(&rej, mt_fmt("system %u: %s", r[i].k, r[i].why));
416 char *j = mt_join(&rej, "; ");
417 mt_printf(&s, "unplaced: no member fits (%s)", j);
418 free(j);
419 mt_strs_free(&rej);
420 } else {
421 mt_printf(&s, "replicas %u: ", k);
422 for (size_t i = 0; i < keep.n; i++) mt_printf(&s, i ? ", system %u %.3f" : "system %u %.3f", keep.v[i], score_or(&ex, keep.v[i], 0.0));
423 for (size_t i = 0; i < nok; i++)
424 if (!ml_has(&keep, ok_k[i])) {
425 mt_printf(&s, "; next system %u %.3f", ok_k[i], ok_s[i]);
426 break;
427 }
428 if (dropped.n) {
429 char *dl = ml_text(&dropped);
430 mt_printf(&s, "; replaced %s (gone or no longer fits)", dl);
431 free(dl);
432 }
433 if (keep.n < k) mt_printf(&s, "; only %zu of %u placed", keep.n, k);
434 }
435 ex.summary = mt_take(&s);
436 if (!(p.at.some && ml_eq(&p.at.l, &keep)) || added.n) {
437 free(why);
438 why = mt_strdup(ex.summary);
439 }
440 ml_opt_free(&want);
441 want = (ml_opt){true, keep};
442 ml_free(&dropped), ml_free(&added);
443 }
444 ml_list on = msp_members_of_at(&want, ms, nms, n);
445 for (size_t i = 0; i < on.n; i++)
446 if (on.v[i] < nms) {
447 msp_books_add(&books, on.v[i], n);
448 if (!ml_has(&cur, on.v[i])) books_add_new(&books, on.v[i], n);
449 }
450 ml_free(&on);
451 ml_opt_free(&ex.chosen);
452 ex.chosen = ml_opt_clone(&want);
453 mfd_prog *e = mfd_prog_get(&doc, name);
454 if (!ml_opt_eq(&want, &p.at)) {
455 char *a = ml_at_word(&p.at), *b = ml_at_word(&want);
456 mt_push_own(changes, mt_fmt("%s: %s -> %s (%s)", name, a, b, why));
457 free(a), free(b);
458 ml_opt_free(&e->at);
459 e->at = want;
460 want = ml_none();
461 mt_set(&e->why, why);
462 } else if (strcmp(why, p.why) != 0) {
463 mt_set(&e->why, why);
464 }
465 ml_opt_free(&want);
466 free(why);
467 free(ok_k), free(ok_s);
468 msp_rows_free(r, nr);
469 ml_free(&cur), ml_free(&anchor);
470 mfd_prog_free(&p);
471 explains->v = mt_realloc(explains->v, (explains->n + 1) * sizeof *explains->v);
472 explains->v[explains->n++] = ex;
473 }
474 mt_strs_free(&ord);
475 msp_books_free(&books);
476 return doc;
477}
478
479/* ---- groups */
480
481/* The mean RTT in ms from member k to the chosen ones (those it has a figure for). */
482static mof32 mean_rtt_ms(const msm_member *ms, size_t nms, uint32_t k, const uint32_t *to, size_t nto) {
483 if (k >= nms) return mof32_none();
484 float sum = -0.0f;
485 size_t c = 0;
486 for (size_t i = 0; i < nto; i++) {
487 mof32 r = msm_rtt_to(&ms[k], to[i]);
488 if (r.some) sum += r.v, c++;
489 }
490 if (!c) return mof32_none();
491 return mof32_some(sum / (float)c / 1e3f);
492}
493
494bool msp_group_choice(const msp_input *in, const mfd_group *g, ml_list *members, char **why) {
495 const mfd_prog *p = mfd_prog_get(in->doc, g->program);
496 if (!p) return false;
497 const mesh_needs *n = &p->needs;
498 mof32 best = best_task_us(in->perf, g->program, p->hash);
499 size_t nc = 0;
500 uint32_t *ck = mt_alloc((in->nmembers ? in->nmembers : 1) * sizeof *ck);
501 double *cs = mt_alloc((in->nmembers ? in->nmembers : 1) * sizeof *cs);
502 for (size_t i = 0; i < in->nmembers; i++) {
503 const msm_member *m = &in->members[i];
504 if (!msc_eligible(m, n) || ms_get(&m->fails, g->program)) continue;
505 bool match = n->ngroup_members == 0;
506 for (size_t t = 0; t < n->ngroup_members; t++)
507 if (msn_term_matches(&n->group_members[t], m)) match = true;
508 if (!match) continue;
509 const msm_perf *here = msm_perfs_get(in->perf, g->program, m->id);
510 if (here && here->hash != p->hash) here = NULL;
511 msc_cx cx = {.w = in->w, .current = ml_has(&g->members, m->id), .here = here, .best_task_us = best};
512 ck[nc] = m->id;
513 cs[nc++] = msc_score_terms(m, n, &cx).total;
514 }
515 if (!nc) {
516 free(ck), free(cs);
517 return false;
518 }
519 size_t size = n->group_size == 0 ? nc : (n->group_size < nc ? n->group_size : nc);
520 /* left: the candidates by score, best first (ties: the lower id). */
521 for (size_t i = 1; i < nc; i++)
522 for (size_t j = i; j > 0 && (cs[j - 1] < cs[j] || (cs[j - 1] == cs[j] && ck[j - 1] > ck[j])); j--) {
523 uint32_t tk = ck[j - 1];
524 double ts = cs[j - 1];
525 ck[j - 1] = ck[j], cs[j - 1] = cs[j];
526 ck[j] = tk, cs[j] = ts;
527 }
528 uint32_t chosen_k[64];
529 double chosen_s[64];
530 size_t nch = 0, nleft = nc;
531 chosen_k[nch] = ck[0], chosen_s[nch++] = cs[0];
532 memmove(ck, ck + 1, (nleft - 1) * sizeof *ck);
533 memmove(cs, cs + 1, (nleft - 1) * sizeof *cs);
534 nleft--;
535 while (nch < size) {
536 /* The next member: its score plus the RTT term to those chosen (ties: the lower id). */
537 size_t bi = 0;
538 double bv = 0;
539 for (size_t i = 0; i < nleft; i++) {
540 mof32 r = mean_rtt_ms(in->members, in->nmembers, ck[i], chosen_k, nch);
541 double x = (double)(r.some ? r.v : 0.0f) / 2.0;
542 double v = cs[i] + in->w->rtt * (1.0 - (x < 0 ? 0 : x > 1 ? 1 : x));
543 if (i == 0 || v > bv || (v == bv && ck[i] < ck[bi])) bi = i, bv = v;
544 }
545 chosen_k[nch] = ck[bi], chosen_s[nch++] = cs[bi];
546 memmove(ck + bi, ck + bi + 1, (nleft - bi - 1) * sizeof *ck);
547 memmove(cs + bi, cs + bi + 1, (nleft - bi - 1) * sizeof *cs);
548 nleft--;
549 }
550 *members = ml_of(chosen_k, nch);
551 ml_sort(members);
552 mt_buf b = {0};
553 mt_printf(&b, "%zu of %zu eligible (", nch, nc);
554 for (size_t i = 0; i < nch; i++) mt_printf(&b, i ? ", system %u %.3f" : "system %u %.3f", chosen_k[i], chosen_s[i]);
555 mt_putc(&b, ')');
556 if (n->group_size > 0) mt_printf(&b, "; group_size %u", n->group_size);
557 *why = mt_take(&b);
558 free(ck), free(cs);
559 return true;
560}
561
562double msp_group_score(const msp_input *in, const mfd_group *g, const ml_list *members) {
563 const mfd_prog *p = mfd_prog_get(in->doc, g->program);
564 if (!p) return 0.0;
565 /* Rust's float sum starts at -0.0 (an empty group scores -0.0, printed "-0.000"). */
566 double sum = -0.0;
567 for (size_t i = 0; i < members->n; i++) {
568 uint32_t k = members->v[i];
569 if (k >= in->nmembers || !msc_eligible(&in->members[k], &p->needs)) continue;
570 msc_cx cx = msc_cx_simple(in->w, msm_perfs_get(in->perf, g->program, in->members[k].id));
571 sum += msc_score_terms(&in->members[k], &p->needs, &cx).total;
572 }
573 return sum;
574}