From e9f53dc8a56ddca0855213da4355f39a69306c07 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 19 Oct 2026 00:40:55 +0100 Subject: 027's 4f-4: loops nested to any depth: the load counts a module's deepest nesting (nesting), a run keeping PURE_MODULE_NESTING (8) on its stack as before and a module nesting deeper running in the executor that calls, its loops in its app's room (PureApp.deep, grown to it), so run()'s hot path is as it was; the JIT compiles modules nesting 8 at most; a function's nesting counted without a cap (u32), its frame sized to it; unit test: 40 loops nested, run to their end (2^20 rounds) and stopped by the work budget (2^40), 8 still on the stack; counts: b42 against b41 with batches BFS -0.12%, without BFS +0.09%, the rest within 0.001%; the bank's queries (s41 and s42 in turns, six each) in_credit +1.04%, per_branch +0.60%, ranks +0.36%, the rest within 0.01% (their spread: the bank has no functions, so none runs the changed executor, and s42's in_credit is within s41's own earlier six); 008 and 027 --- core/module-jit.c | 4 +++- core/module-run.h | 2 +- core/module.c | 56 +++++++++++++++++++++++++++++++++++++++++++++--------- core/module.h | 8 +++++++- core/test-module.c | 33 ++++++++++++++++++++++++-------- 5 files changed, 83 insertions(+), 20 deletions(-) (limited to 'core') diff --git a/core/module-jit.c b/core/module-jit.c index 8208095..bd04361 100644 --- a/core/module-jit.c +++ b/core/module-jit.c @@ -5788,7 +5788,9 @@ struct PureJit *pure_jit_make(const PureModule *m) { const char *enabled = getenv("PURE_JIT"); /* What it makes keeps its lists' and states' sets in a word each: a module of more states runs in the executor * alone (027's 4f-2). */ - if ((enabled && !strcmp(enabled, "0")) || !m->height || !m->code_count || m->states > JIT_STATES) return NULL; + if ((enabled && !strcmp(enabled, "0")) || !m->height || !m->code_count || m->states > JIT_STATES || + m->nesting > PURE_MODULE_NESTING) /* (its loops' tables hold PURE_MODULE_NESTING) */ + return NULL; Made *made = NULL; size_t count = 0, room = 0; bool ok = true; diff --git a/core/module-run.h b/core/module-run.h index cff3f71..e79aa59 100644 --- a/core/module-run.h +++ b/core/module-run.h @@ -135,7 +135,7 @@ typedef struct { PureFault kind; /* a fault's */ PureResult status; /* what refused or stopped it */ uint32_t fault_pc; /* the instruction that faulted or refused */ - Loop *loops; /* PURE_MODULE_NESTING of them, apart: a walk points into its loop */ + Loop *loops; /* the module's nesting of them (PURE_MODULE_NESTING on the stack, more the app's), apart: a walk points into its loop */ /* The run of a tree compiled code read an item from last (pure_run_item): * the list as it was (its version), its positions and each field's cells. */ struct { const PureList *list; uint64_t version; size_t start, count; const void *columns[16]; } run; diff --git a/core/module.c b/core/module.c index 3d38966..71a0a25 100644 --- a/core/module.c +++ b/core/module.c @@ -581,7 +581,6 @@ PURE_COLD static const char *verify_code(const PureModule *m, PureBlock block, i if (op->op == PURE_OP_LIST_REMOVE && walking(walked, walks, arg) && (int)arg != row) REFUSE("remove from a list an outer walk walks"); if (nest && op->op == PURE_OP_REPLY) REFUSE("reply inside a loop"); - if (nest == PURE_MODULE_NESTING && (op->op == PURE_OP_EACH || op->op == PURE_OP_LOOP)) REFUSE("loops nested deeper than 8"); if (op->op == PURE_OP_BREAK && !nest) REFUSE("break outside a loop"); if (op->op == PURE_OP_BREAK && height) REFUSE("break with values on the stack"); if (op->op == PURE_OP_ITEM_SET && m->state_key[list_of(arg)] == item_field(arg) + 1) @@ -1513,6 +1512,20 @@ PURE_COLD static void range_code(PureModule *m, PureBlock block, int input) { } } +/* How deep the loops of m's verified code nest (its blocks apart, each loop's within its own); UINT32_MAX without room. */ +static uint32_t nesting_of(const PureModule *m) { + uint32_t *ends = malloc(((size_t)m->code_count + 1) * sizeof(*ends)), depth = 0, most = 0; + if (!ends) return UINT32_MAX; + for (uint32_t pc = 0; pc < m->code_count; ++pc) { + while (depth && pc >= ends[depth - 1]) --depth; + if (m->code[pc].op != PURE_OP_EACH && m->code[pc].op != PURE_OP_LOOP) continue; + ends[depth++] = pc + 1 + (m->code[pc].arg >> 16); + if (depth > most) most = depth; + } + free(ends); + return most; +} + /* A name and its place among those of one namespace, in order of name and then of place. */ typedef struct { const char *name; size_t index; } Named; static int by_name(const void *a, const void *b) { @@ -1527,13 +1540,14 @@ static void states_add(uint64_t *set, uint32_t state) { set[state >> 6] |= UINT6 /* What a function's code names (027's 2c), read before it is verified (its arguments bounded here): the event's lists, * the registers and the values held by name each call has its own of, the lists not an event's it changes, its locals * and how deep its loops nest; the functions it calls (calls, a bit each). */ -PURE_COLD static void function_names(PureModule *m, uint32_t fn, uint64_t *calls) { +PURE_COLD static bool function_names(PureModule *m, uint32_t fn, uint64_t *calls) { PureFunction *f = &m->function[fn]; uint64_t *lists = m->function_lists + (size_t)fn * m->state_words, *registers = m->function_registers + (size_t)fn * m->state_words, *changes = m->function_changes + (size_t)fn * m->state_words; - uint32_t end = f->code.start + f->code.length, ends[PURE_MODULE_NESTING]; + if (f->code.start > m->code_count || f->code.length > m->code_count - f->code.start) return true; /* refused as it is verified */ + uint32_t end = f->code.start + f->code.length, *ends = malloc(((size_t)f->code.length + 1) * sizeof(*ends)); unsigned depth = 0; - if (f->code.start > m->code_count || f->code.length > m->code_count - f->code.start) return; /* refused as it is verified */ + if (!ends) return false; for (uint32_t pc = f->code.start; pc < end; ++pc) { const PureOp *op = &m->code[pc]; uint32_t arg = op->arg, list = UINT32_MAX; @@ -1551,9 +1565,9 @@ PURE_COLD static void function_names(PureModule *m, uint32_t fn, uint64_t *calls case PURE_OP_ITEM_GET: case PURE_OP_ITEM_SET: case PURE_OP_APPEND_IN: list = list_of(arg); break; case PURE_OP_EACH: case PURE_OP_FOLD: case PURE_OP_LOOP: case PURE_OP_LOCAL_LOAD: case PURE_OP_LOCAL_STORE: if (op->op == PURE_OP_EACH || op->op == PURE_OP_FOLD) list = arg >> 8 & 0xFF; - if ((op->op == PURE_OP_EACH || op->op == PURE_OP_LOOP) && depth < PURE_MODULE_NESTING) { + if (op->op == PURE_OP_EACH || op->op == PURE_OP_LOOP) { /* (a loop an instruction at least: depth within ends) */ ends[depth++] = pc + 1 + (arg >> 16); - if (depth > f->nesting) f->nesting = (uint8_t)depth; + if (depth > f->nesting) f->nesting = depth; } if (op->op == PURE_OP_EACH || op->op == PURE_OP_FOLD) break; if ((arg & 0xFF) < PURE_MODULE_LOCALS && (arg & 0xFF) >= f->locals) f->locals = (uint8_t)((arg & 0xFF) + 1); @@ -1565,6 +1579,8 @@ PURE_COLD static void function_names(PureModule *m, uint32_t fn, uint64_t *calls } if (event_list_state(m, list)) states_add(bound_list(m, list) ? registers : lists, list); } + free(ends); + return true; } PURE_COLD PureResult pure_module_read(const char *path, PureModule *out, char *error, size_t error_size) { @@ -2082,7 +2098,11 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule } /* What each function names, and the lists it changes with those the functions it calls change (until none adds). */ uint64_t calls[PURE_MODULE_FUNCTIONS] = {0}; - for (uint32_t i = 0; i < out->functions; ++i) function_names(out, i, &calls[i]); + for (uint32_t i = 0; i < out->functions; ++i) + if (!function_names(out, i, &calls[i])) { + result = PURE_ALLOCATION; + REFUSE("out of memory", i); + } for (bool more = out->functions > 0; more;) { more = false; for (uint32_t i = 0; i < out->functions; ++i) @@ -2233,7 +2253,13 @@ PURE_COLD PureResult pure_module_load(const void *bytes, size_t size, PureModule for (uint32_t i = 0; i < out->views; ++i) for (uint32_t pc = out->view_code[i].start; pc < out->view_code[i].start + out->view_code[i].length; ++pc) if (out->code[pc].op == PURE_OP_KEPT_GET) out->view_body[i] = true; - out->runner = out->calls ? 2 : out->batches ? 1 : 0; + /* How deep its loops nest (027's 4f-4): past what a run keeps on its stack, its blocks run in the executor that calls, + * its loops in its app's room. */ + if ((out->nesting = nesting_of(out)) == UINT32_MAX) { + result = PURE_ALLOCATION; + REFUSE("out of memory", 0); + } + out->runner = out->calls || out->nesting > PURE_MODULE_NESTING ? 2 : out->batches ? 1 : 0; out->jit = pure_jit_make(out); /* none: the executor runs it all */ return PURE_OK; refused: @@ -4829,10 +4855,21 @@ static __attribute__((noinline, cold)) void unwind_calls(Frame *frame, Call *top /* The executor's run of a block of a module with functions (027's 2c): run_batches' steps and batches, and calls: a * CALL opens its function's frame and its block runs on in this loop, a RETURN closes it. Its own copy of the steps, * as run_batches is. */ +/* Room for a run's loops nested deeper than PURE_MODULE_NESTING (027's 4f-4): the app's, grown to nesting; NULL without. */ +static __attribute__((cold, noinline)) Loop *deep_loops(PureApp *app, uint32_t nesting) { + if (app->deep_room < nesting) { + Loop *grown = realloc(app->deep, nesting * sizeof(*grown)); + if (!grown) return NULL; + app->deep = grown, app->deep_room = nesting; + } + return app->deep; +} + static __attribute__((noinline, aligned(64))) PureResult run_calls(const PureModule *m, PureValue *values, PureBlock block, Event *ev, Slot *result) { Slot stack[PURE_MODULE_STACK]; - Loop loops[PURE_MODULE_NESTING]; + Loop few[PURE_MODULE_NESTING], *loops = m->nesting > PURE_MODULE_NESTING ? deep_loops(ev->app, m->nesting) : few; + if (!loops) return PURE_ALLOCATION; Frame frame; open_frame(&frame, m, values, block, ev, stack, loops); Call *top = NULL; @@ -5161,6 +5198,7 @@ void pure_app_stop(PureApp *app) { pure_draft_close(app->stored_values); free(app->carried); free(app->by_input); + free(app->deep); pure_draft_close(app->stored_links); pure_draft_close(app->stored_seq); pure_save_close_start(app); diff --git a/core/module.h b/core/module.h index 26259fe..8a84ddb 100644 --- a/core/module.h +++ b/core/module.h @@ -194,6 +194,8 @@ enum { PURE_FOLD_SLICED = 0x80, PURE_EACH_SLICED = 1 }; * Loops (LOOP and EACH) nest 8 deep. Within a walk, code that a loop runs * may change the items of any list but not add to or remove from a list an * outer walk walks; the innermost walk may remove from its own. */ +/* PURE_MODULE_NESTING: the loops nested that a run keeps on its stack; a module nesting deeper (027's 4f-4) runs in the + * executor that calls, its loops in its app's room (PureApp.deep). */ enum { PURE_LOOP_INTEGER = 256, PURE_MODULE_NESTING = 8 }; /* What a unit (an event, or a view's evaluation) may run when its app sets * no work budget (pure_app_work), and what an event may hold for what it @@ -331,7 +333,8 @@ typedef struct { uint16_t first; uint8_t params, results; uint32_t held; - uint8_t height, locals, nesting; + uint8_t height, locals; + uint32_t nesting; } PureFunction; typedef struct { char name[PURE_MODULE_NAME]; uint8_t type; uint16_t rows; uint32_t offset; } PureField; typedef struct { @@ -441,6 +444,7 @@ typedef struct { uint8_t *signature_type; uint16_t *signature_record; bool calls; /* it has functions: its blocks run in the executor that calls (module.c) */ + uint32_t nesting; /* its loops' deepest nesting (set at load) */ } PureModule; /* Whether a state of m is transient (PURE_STATE_TRANSIENT). */ @@ -623,6 +627,8 @@ typedef struct { struct { unsigned char **blocks; size_t *sizes; unsigned count, at; size_t used; } calls; struct PureSpare { PureList **lists; unsigned count, capacity; } *spare; PureValue *pending; /* the values an event works on until it ends */ + void *deep; /* a run's loops, a module nesting past PURE_MODULE_NESTING's (its nesting of them) */ + uint32_t deep_room; PureVersion *marked_texts; /* where the event running began: each text's version, each stored list's journal, */ size_t *marked_lists; /* Each input's: its last number sent and as saved, and where the event running began; one block (by_input) for diff --git a/core/test-module.c b/core/test-module.c index 5bd1c8b..cb8e228 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -7100,14 +7100,17 @@ static void loops(void) { deep[3 * d + 1] = (O){C, 0, 1}; deep[3 * d + 2] = (O){LOOP, BODY(0, 26 - 3 * d - 3), 0}; } - O deeper[9 * 3 + 2]; - for (unsigned d = 0; d < 9; ++d) { + enum { DEEPER = 40 }; /* nested past what a run keeps on its stack (027's 4f-4): its app's room */ + O deeper[DEEPER * 3 + 4]; + for (unsigned d = 0; d < DEEPER; ++d) { deeper[3 * d] = (O){C, 0, 0}; - deeper[3 * d + 1] = (O){C, 0, 1}; - deeper[3 * d + 2] = (O){LOOP, BODY(0, 29 - 3 * d - 3), 0}; + deeper[3 * d + 1] = (O){C, 0, 2}; /* each twice: the innermost 2^40 times past any budget, so its first fault */ + deeper[3 * d + 2] = (O){LOOP, BODY(0, DEEPER * 3 + 4 - 3 * d - 3), 0}; } - deeper[27] = (O){C, 0, 1}; - deeper[28] = (O){ST, S_, 0}; + deeper[3 * DEEPER] = (O){PURE_OP_LOAD, S_, 0}; + deeper[3 * DEEPER + 1] = (O){C, 0, 1}; + deeper[3 * DEEPER + 2] = (O){PURE_OP_ADD, 0, 0}; + deeper[3 * DEEPER + 3] = (O){ST, S_, 0}; const struct { const O *code; size_t count; const char *why; } refused[] = { {outside, LEN(outside), "break outside a loop"}, {valued, LEN(valued), "break with values on the stack"}, @@ -7116,7 +7119,6 @@ static void loops(void) { {flagged, LEN(flagged), "no such state"}, {two_ways, LEN(two_ways), "local used as two things"}, {into_outer, LEN(into_outer), "insert into the list walked"}, - {deeper, LEN(deeper), "loops nested deeper than 8"}, }; for (size_t i = 0; i < LEN(refused); ++i) { H one[] = {{1, 0, (uint32_t)refused[i].count}}; @@ -7136,7 +7138,22 @@ static void loops(void) { nested.no = LEN(deep); nested.h = eight; nested.nh = 1; - CHECK(load(nested, &module_b) == PURE_OK); /* eight deep is allowed */ + CHECK(load(nested, &module_b) == PURE_OK && module_b.nesting == 8 && module_b.runner != 2); /* on the stack */ + H forty[] = {{1, 0, LEN(deeper)}}; + nested.o = deeper, nested.no = LEN(deeper), nested.h = forty; + CHECK(load(nested, &module_b) == PURE_OK && module_b.nesting == DEEPER && module_b.runner == 2 && !module_b.jit); + PureApp deep_app; + CHECK(pure_app_start(&deep_app, &module_b, (PureData){0}) == PURE_OK); + pure_app_work(&deep_app, 100000); /* (2^40 rounds would never end) */ + CHECK(press(&deep_app, 0) == PURE_LIMIT && deep_app.fault == PURE_FAULT_WORK && deep_app.values[S_].num == 0); + pure_app_work(&deep_app, 0); + pure_app_stop(&deep_app); + for (unsigned d = 0; d < DEEPER; ++d) deeper[3 * d + 1] = (O){C, 0, d % 2 ? 1 : 2}; /* 2^20 rounds */ + CHECK(load(nested, &module_b) == PURE_OK && pure_app_start(&deep_app, &module_b, (PureData){0}) == PURE_OK); + pure_app_work(&deep_app, UINT64_C(1) << 40); + CHECK(press(&deep_app, 0) == PURE_OK && deep_app.values[S_].num == 1 << 20 && press(&deep_app, 0) == PURE_OK && + deep_app.values[S_].num == 2 << 20); + pure_app_stop(&deep_app); pure_module_release(&module_b); pure_module_release(&module_a); #undef BODY -- cgit v1.2.3