diff options
Diffstat (limited to 'src/core/stack.h')
| -rw-r--r-- | src/core/stack.h | 112 |
1 files changed, 112 insertions, 0 deletions
diff --git a/src/core/stack.h b/src/core/stack.h new file mode 100644 index 0000000..49f347c --- /dev/null +++ b/src/core/stack.h @@ -0,0 +1,112 @@ +/* growing operand and return stacks share the runtime's buddy allocator. + allocation here cannot call vm code or collect: an overflowing return stack + has no room for an allocator call. the runtime registers its allocator and + stack globals once the heap is ready. addresses are vm word indices. */ +#ifndef TINYVM_STACK_H +#define TINYVM_STACK_H + +static Cell stack_control; +enum { + SC_FRAME_FLOOR, SC_FRAME_TOP, SC_FRAME_GUARD, + SC_DATA_LOW, SC_DATA_TOP, SC_DATA_NODE, + SC_RETURN_LOW, SC_RETURN_TOP, SC_RETURN_NODE, + SC_FREE, SC_STOP, SC_BUMP, SC_MAX, SC_HOLD_LOW, SC_HOLD_HIGH, SC_CUT, SC_GC_ACTIVE, SC_COUNT +}; + +/* the including core supplies stack_memory_grow and refreshes m if it moves. */ +static Cell stack_get(int slot) { Cell p = m[stack_control + slot]; return inmem(p) ? m[p] : 0; } +static void stack_set(int slot, Cell value) { Cell p = m[stack_control + slot]; if (inmem(p)) m[p] = value; } +static int stack_register(Cell control) +{ + int i; + if (control <= 0 || !inmem(control + SC_COUNT - 1)) return 0; + for (i = 0; i < SC_COUNT; i++) if (!inmem(m[control + i])) return 0; + if (!inmem(m[control + SC_FREE] + 31)) return 0; + stack_control = control; + return 1; +} +static void stack_push(Cell b, int k) +{ + Cell list = m[stack_control + SC_FREE], head; + if (k < 3 || k >= 31 || b < 0 || !inmem(b + 6) || list < 0 || !inmem(list + k)) return; + head = m[list + k]; + if (head && (head < 0 || !inmem(head + 6))) return; + m[b] = (Cell)1 << k; m[b + 1] = (Cell)k << 16; m[b + 2] = 0; + m[b + 3] = 0; m[b + 4] = 0; m[b + 5] = head; m[b + 6] = 0; + if (head) m[head + 6] = b; + m[list + k] = b; +} +static int stack_heap_grow(int k) +{ + Cell old = stack_get(SC_STOP), h = old - HEAP_LO, block = (Cell)1 << k; + Cell need = ((h + block - 1) / block + 1) * block, size = h * 2, off, part; + int c; + if (h <= 0 || (h & 7) || !HEAP_GROW || !stack_get(SC_MAX) || stack_get(SC_CUT) || stack_get(SC_HOLD_HIGH)) return 0; + if (size < need) size = need; + if (HEAP_LO + size > 0x7fffffff || !stack_memory_grow((UCell)(HEAP_LO + size))) { + size = need; + if (HEAP_LO + size > 0x7fffffff || !stack_memory_grow((UCell)(HEAP_LO + size))) return 0; + } + stack_set(SC_STOP, HEAP_LO + size); stack_set(SC_BUMP, HEAP_LO + size); + stack_set(SC_MAX, HEAP_LO + size); + off = h; + while (off < size) { + part = 8; c = 3; + while (part * 2 <= size - off && !(off % (part * 2))) { part *= 2; c++; } + stack_push(HEAP_LO + off, c); off += part; + } + return 1; +} +static Cell stack_allocate(Cell words) +{ + Cell list, b, next, other, p, i; + int k = 3, j, grown = 0; + if (!stack_control || words < 0 || words > 0x3ffffffa) return 0; + while (((Cell)1 << k) < words + 5) k++; + for (;;) { + list = m[stack_control + SC_FREE]; j = k; + if (list < 0 || !inmem(list + 31)) return 0; + while (j < 31 && !m[list + j]) j++; + if (j == 31) { + if (grown || !stack_heap_grow(k)) return 0; + grown = 1; continue; + } + b = m[list + j]; + if (b < 0 || !inmem(b + ((Cell)1 << j) - 1) || m[b] != ((Cell)1 << j) || (m[b + 1] & 65535)) return 0; + next = m[b + 5]; m[list + j] = next; + if (next) { if (!inmem(next + 6)) return 0; m[next + 6] = 0; } + while (j > k) { j--; other = b + ((Cell)1 << j); stack_push(other, j); } + if (stack_get(SC_HOLD_HIGH) && b < stack_get(SC_HOLD_HIGH) && b + ((Cell)1 << k) > stack_get(SC_HOLD_LOW)) { + m[b] = (Cell)1 << k; m[b + 1] = ((Cell)k << 16) | 2; + m[b + 2] = 0; m[b + 5] = 0; m[b + 6] = 0; continue; + } + p = b + 5; + m[b] = (Cell)1 << k; m[b + 1] = ((Cell)k << 16) | 1 | 512 | 1024 | (stack_get(SC_GC_ACTIVE) ? 2 : 0); + m[b + 2] = p ^ 0x2B7E1516; m[b + 3] = 0; m[b + 4] = -words - 1; + for (i = p; i < b + ((Cell)1 << k); i++) m[i] = 0; + return p; + } +} +static Cell stack_expand(int is_return, Cell minimum, Cell *sp, Cell *rp) +{ + int low_slot = is_return ? SC_RETURN_LOW : SC_DATA_LOW, top_slot = low_slot + 1, node_slot = low_slot + 2; + Cell low, top, capacity, used, node, oldnode, i, source; + if (!stack_control) return -1; + low = stack_get(low_slot); top = stack_get(top_slot); capacity = top - low; + used = is_return ? *rp - low : top - *sp; + if (capacity <= 0 || used < 0 || used > capacity + (is_return ? 8 : 0) || minimum < 0 || minimum > 0x3ffffff0) return -1; + if (minimum <= capacity) return capacity; + if (minimum < capacity * 2) minimum = capacity * 2; + node = stack_allocate(minimum + 16); + if (!node) return -1; + source = is_return ? low : *sp; + for (i = 0; i < used; i++) m[node + (is_return ? i : minimum - used + i)] = m[source + i]; + oldnode = stack_get(node_slot); + stack_set(low_slot, node); stack_set(top_slot, node + minimum); stack_set(node_slot, node); + if (is_return) *rp = node + used; else *sp = node + minimum - used; + if (oldnode >= 5 && inmem(oldnode - 4)) stack_push(oldnode - 5, (int)((m[oldnode - 4] >> 16) & 31)); + return minimum; +} +static Cell stack_data_limit(void) { return stack_control ? stack_get(SC_DATA_LOW) + 1100 : DSLIM; } +static Cell stack_return_limit(void) { return stack_control ? stack_get(SC_RETURN_TOP) : RSLIM; } +#endif |