I’ve been messing around with a bunch of rpi low-level tutorials (see asm64/main.s) and have come to a few conclusions and immediate direction changes:
- I should move to a 64-bit architecture; much of what I liked about ARMv7 is gone in v8 and it’s easier to find sbcs with the v8 instruction set, and only more so in the future.
- I should target a very specific board
- If I’m going to be doing any real work with a board plugged in, I need to get a serial bootloader figured out
- bootboot (rpi3/4) can receive an initrd over serial, including the kernel
- a gdbstub can also load kernels, and might be part of the bootleader
To that end, I’ve bought a couple of rpi zero 2 ws, which are pretty rad, and should soon have my uart-usb cable.
- boot sequence
- videocore does it’s thing and eventually brings up the arm core
- bootloader
- based on
bootboot - sets the machine up in a consistent state, and loads the initrd/monitor
- based on
- monitor
- sets up monitor/debugger on uart0
- runs under hypervisor mode, which gives it extra access
- has it’s own set of exception vectors
- debugger
- a breakpoint is
- (address of code, original instruction)
- and then replace the original instruction with
hyp #dbg-breakinstruction
- single stepping:
- using the actual debugger extensions, you can feed instructions to the processor
- but you could also do it by
- using the actual debugger extensions, you can feed instructions to the processor
- arm debugging extensions has registers for breakpoints and watchpoints,
- but I’m not sure how it plays with modes
- a breakpoint is
- loader
- can load/run elf files
- can act kinda like ftp for the initrd
- being able to send files to the initrd over uart means being able to debug dynamic code
- especially once we’re using the virtual machine for things, need to be able to send over new bytecode
- implies that it understands the filesystem
- monitor looks for sys/core.elf in initrd and runs it
- hypervisor exceptions get back to the monitor
- kernel8.img is loaded and booted by the firmware
- kernel8.img is based on
bootboot, which preconfigures the host into a known state and loads an initrd - initrd comes from host from SD card or over serial
- initrd is a tarfile, containing some kernel.elf
- bootboot finds the kernel, loads it per elf, and jumps into it
- kernel8.img is based on
- two stacks; data and control
- data stack is used for processing, and is also the nursery gc
- control stack is frames
- calling a function means copying it’s frame to the control stack
- arguments are on the stack, constants are in the frame
- interesting papers re: prompt application for delimited control (manipulation of the control stack)
- most of oleg kiselyov’s delemited continuations section
- this guy’s website is fascinating
- also this tutorial on shift/reset, also by oleg kiselyov
- theory and practice of first-class prompts
- paper from Matthias Felleisen which is exactly what it sounds like
- lots of other papers seem to reference this 𝓕 term
An 𝓕-application transforms the current control state into a functional abstr&ion, which we call continuation.
- compiler and runtime support for compiler marks
- paper from the racket guys re: adding marks (prompts? kinda?) to racket continuations
- Adding Delimited and Composable Control to a Production Programming Environment
- writeup of original PLT scheme adding
controlandshiftwhile not screwing upcall/ccanddynamic-wind
- writeup of original PLT scheme adding
- a monadic framework for delimited continuations
- kent dybvig + simon payton jones
- the introduction is amazing, and they introduce the set of four operators I’m going to include in the VM
newPromptprompts are first class, and distinctpushPrompttakes a prompt, and delimits the contination of it’s body at that promptwithSubContIt captures a portion of the current continuation back to but not including the activation of pushPrompt with prompt p, aborts the current continuation back to and including the activation of pushPrompt, and invokes f, passing it an abstract value representing the captured subcontinuation.
If more than one activation of pushPrompt with prompt p is still active, the most recent enclosing activation, i.e., the one that delimits the smallest subcontinuation, is selected.
pushSubContevaluates its first operand to yield a subcontinuation k, then evaluates its second operand in a continuation that composes k with the current continuation.
- still need to understand more the finer details around -/+F-/+, in terms of where the abort is.
- I have a pretty good intuition re:
call/ccbut that’s only one particular composition of operatorswithCont e = withSubCont p0 (λk.pushPrompt p0 (e k)) where: p0 = the top level prompt around the whole program callcc = λf.withCont (λk.pushSubCont k (f (reifyA k))) where: reifyA k = λv.abort (pushSubCont k v) abort e = withCont (λ .e) - specifically, “abort” vs. “resume” isn’t clear to me
- a lot is based on where prompts are placed (in the continuation chain) and where they’re left after resumption
- I have a pretty good intuition re:
- most of oleg kiselyov’s delemited continuations section
in the interest of getting some ideas figured out in an actual bytecode interpreter, I’ve got the vary bare bones of an interpreter loop written for GNU as in main.s
- little endian means that the low byte of a word is at the low address
- as such, a pointer of #x0F006543 will be stored in memory
- #x43 #x65 #x00 #x0F
- pointers must be 4-byte aligned, ie. bottom two bits zero, ie. a multiple of 4
- 0, 4, 8, c, 10, 14, 18, 1c, 20, etc.
most of the instructions deal with the top word of the stack, possibly mutating and replacing
- that means pop/act/push is really common
- SO, if we instead keep the top of the stack in a dedicated register, we get rid of a bunch of paired memory accesses
bytecode format has the opportunity to make a big difference in overhead, since shifting shit around in order to figure out the next instruction is kind of hard on ARM
- if a bytecode is a 32bit word:
- opcodes are native register sized
- importantly: inline data is also word aligned
- in memory:
tttttt00 dddddddd dddddddd dddddddd
- big payload, if immediates have a byte-wide type, immediates can be encoded directly
- but it’s really really wasteful of space if we’re not efficiently using the payload
- for easy dispatch, opcodes should be multiples of 4
- means that the opcode can be an index without clearing the bottom bits
ldr rop, [rpc], #4 ldr pc, [pc, rop, lsl #24]
- means that the opcode can be an index without clearing the bottom bits
- opcodes are native register sized
- probably worth thinking about a 16bit opcode format, since there are half-word instructions in arm
a dump of bookmarks and recent tabs related to the project (I’m cleaning out dead bookmarks)
- implementation of newsqueak - rob pike (pdf)
- jonesforth/jonesforth.S at master · nornagon/jonesforth
- Bootstrapping a minimal Forth from scratch. : Forth
- Moving Forth: Part 1
- Thinking Forth
- Memory Management 1 on Bona Fide OS Developer
- zen/multiboot.zig at master · AndreaOrru/zen
- sqrt57/x86-scheme: Implementation of Scheme programming language in assembly
- sasm/src/sasm/arch/x64.sls at master · ktakashi/sasm
- zkeme80/src/assembler.scm at master · siraben/zkeme80
- A Tiny x86 Assembler Written in Scheme
- Erlang’s Internal Data Representation - Detail oriented
- Tumble Forth
- What If We Don’t Pop the Stack? The Return of 2nd-Class Values - xhebraj-ecoop22.pdf
- Emergent Technologies Inc. – Security Kernel
- mergesort for linked lists – Tony Finch
- Cheney on the M.T.A.
- How to compile with continuations
- ACM OOPS Messenger 4, 4 (Oct 1993), 2-27
- A Compact and Extensible Portable Scheme VM - OLearyFeeleyMOREVMS23.pdf
- Memory (Debugging with GDB)
- Memory Instructions: Load and Store (Part 4) | Azeria Labs
- BaseMax/AwesomeInterpreter: The Big list of the github, open-source interpreters.
- lisp.c/bytecode_interpreter.c at master · arkanis/lisp.c
- rm-hull/byok: A bare-metal x86 Forth interpreter & compiler
- Call-site optimization for Common Lisp - call-site-optimization.pdf
- STklos/src/vm.c at master · egallesio/STklos
- What About the Integer Numbers? Fast Arithmetic with Tagged Integers - A Plea for Hardware Support - Microsoft Research
- Raspberry Pi 3 B+ - DEV-14643 - SparkFun Electronics
- Bitwise Operations (Guile Reference Manual)
- raspberry-pi-os/src/lesson01/src at master · s-matyukevich/raspberry-pi-os
- How can I examine the stack frame with GDB? - Stack Overflow
- fast bytecode number representations - Kagi Search
- start with bytecode calculator:
- immediates
- constants
- jumps
- arithmetic
xxxxxx00 <- pointer 00000001 <- fixnum 00000010 <- fixnum check bit 11111011 <- void 11111101 <- true 11111110 <- false 11111111 <- undefined
32bit word 6 bit opcode, (8 bit, but bottom two must be zeros) 24 bit payload
doing it this way makes the opcode a valid 4-byte aligned index
which means dispatch is easy (ldr pc, [pc, opcode, lsl #24])
- #x00
op_halt - halts
- #x01
op_push_immediate - pushes a typed immediate; the bottom byte is the immediate tag true, false, nil, void, etc.
- #x02
op_push_fixnum - pushes the pushes the 24bit payload, as an immediate fixnum
- data structures we’ll need:
- lock and mutex
- growable vector (persistent, see clojure stuff)
- ring buffer
- trie (or something similar, for interning keywords)
- hashtable
- set (order doesnt matter, if efficiency is possible)
- utf8 strings
- possibly as btrees if fast random-access is required
- bignums, rationals
- really simple, doesn’t need to be gmp level
- byte buffer (with alignment, and maybe packed struct access)
- won’t need, but would be neat:
- computable reals; ie. pi = infinite repeated fraction that returns approximations within a given precision
- https://github.com/stylewarning/computable-reals
- how are pattern matching and the specializer search done during generic function dispatch
different? what would it look like if “generic functions” were conceptually about adding branches
to some
match-casesomewhere?- comment from Rich Hickey on a blog post which explains some of his reasoning behind going with multi-methods vs. pattern matching basically comes down to open/closed; pattern matching usually expects all cases to be present (closed), comes with destructuring, and exhaustiveness checking
- “as I don’t think than one makes the other redundant”
- call-site optimization in common lisp this is interesting; basically, instead of trying to
optimize at the caller, where there’s lots of info about the callsite but nothing about the
function (which has to be looked up, and might be a generic function dispatch), do an
unconditional jump to a trampoline, which computes an efficient argument parsing / dispatch
function and caches it by callsite.
trouble happens when needing to invalidate the various caches; maybe there’s something there with the class-stamps written about in AGS ‘94 (optimizing multi-method dispatch with compressed tables)
excellent documentation for the STklos virtual machine
https://github.com/egallesio/STklos/blob/master/src/vm.c
- struct vm-thread
- pc
- index or pointer into bytecode
- fp
- frame pointer; stack of activation records; ie, control stack
- sp
- stack pointer; ie, data stack
- stack
- the actual stack, one per thread
- val
- register for the current value
- vals
- register for multiple return values
- r1,r2
- two extra registers
- env
- the current environment
- current_module
- the current module
- iport, oport, eport
- the current input/output/error ports
- scheme_thread
- the scheme thread object associated with this vm thread
- macros for run vm
#define PREP_CALL() do { SCM fp_save = vm->fp; vm->sp -= ACTIVATION_RECORD_SIZE vm->fp = vm->sp; save_fp(vm->fp) = fp_save; save_proc(vm->fp) = false; save_info(vm->fp) = false; } #define RET_CALL() do { vm->sp += ACTIVATION_RECORD_SIZE vm->env = save_env(vm->fp) vm->pc = save_pc(vm->fp) vm->consts = save_consts(vm->fp) vm->fp = save_fp(vm->fp) } #define PUSH_ENV(nargs, func, next_env) do { boxed_type(vm->sp) = tc_frame frame_length(vm->sp) = nargs frame_next(vm->sp) = next_env frame_owner(vm->sp) = func } #define CALL_CLOSURE(func) do { vm->pc = CLOSURE_BCODE(func) vm->consts = CLOSURE_CONST(func) vm->env = vm->sp }
/* * VM LOCKING * For optimization, some opcode/operand pairs get patched on the fly, * and replaced by another operation. It's important that the two * reads (opcode and operand) happen atomically. If not, we can get this * situation: * 1) Thread A reads opcode at [n] * 2) Thread B suspends thread A, changes opcode at [n] and operand * at [n+1] * 3) Thread A resumes, reads new operand at [n+1], which does not * match the old opcode. * * To avoid this situation, and avoid a global lock around each * operation, we can do this: * 1) When we jump into one of the to-be-optimized opcodes, obtain * the global lock. * 2) In case we hit the race condition (2, above), re-fetch and * dispatch the current operand. We will either: * 3a) Re-dispatch to the same (to-be-optimized) opcode. Go ahead * and optimize, then release lock. * 3b) We hit the race condition, and are dispatched to the new * operand. Release the global lock and process the operation. * * We need to patch the opcode last, otherwise: * 1) Thread A obtains lock * 2) Modifies opcode at [n] * 3) Thread B interrupts thread A. Reads new opcode at [n], old * operand at [n+1] * 4) Thread A resumes, updates operand at [n+1], releases lock */
- run vm
with apologies to the fact that there’s
#defineswitches to swap between computed gotos and a switch, statement, I’m just going to transcribe as if it’s the switch. details aren’t super important here.loop: op = fetch_next // debug // statistics switch op: case nop: NEXT // why a register and not onto the stack? case im_false : { vm->val = false; NEXT1 } case im_true : { vm->val = true; NEXT1 } case im_nil : { vm->val = nil; NEXT1 } case im_minus1 : { vm->val = -1; NEXT1 } case im_zero : { vm->val = 0; NEXT1 } case im_one : { vm->val = +1; NEXT1 } case im_void : { vm->val = void; NEXT1 } case small_int : { vm->val = make_int(fetch_next()); next1 } case constant : { vm->val = fetch_const(); next1 } case false_push { push(false); next } case true_push { push(true); next } case nil_push { push(nil); next } case minus1_push { push(-1); next } case zero_push { push(0); next } case one_push { push(+1); next } case void_push { push(void); next } case int_push { push(make_int(fetch_next())); next } case constant_push { push(fetch_constant()); next } // interesting in that they patch the original callsite after lookup case push_global_ref case global_ref: lock_and_restart // code lock for self-modifying code orig_opcode = vm->pc[-1] orig-operand = fetch_const() if (orig_opcode == PUSH_GLOBAL_REF) push(vm->val) vm->val = vm_lookup(orig_operand, vm->env, &ref, false) if (!ref) release_lock; error: unbound variable vm->pc[-1] = global_var_index(ref) vm->pc[-2] = (orig_opcode == GLOBAL_REF) ? UGLOBAL_REF : PUSH_UGLOBAL_REF release_lock next1 case push_uglobal_ref: push(vm->val) fallthrough to uglobal_ref case uglobal_ref: release_possible_lock // because of optimization, we may get redispatched here vm->val = fetch_global() next1 case global_ref_push: lock_and_restart orig_operand = fetch_const() res = lookup(orig_operand, vm->env, &ref, FALSE) if (!ref) release_lock error: unbound variable push(res) // patch back code (we've already looked it up) vm->pc[-1] = global_var_index(ref); vm->pc[-2] = UGLOBAL_REF_PUSH; release_lock; next1 case uglobal_ref_push: release_possible_lock // because of optimization, we may get redispatched here push(fetch_global()) next1 case push_gref_invoke: case gref_invoke: lock_and_restart; orig_opcode = vm->pc[-1] orig_operand = fetch_const() if (orig_opcode == PUSH_GREF_INVOKE) push(vm->val) vm->val = lookup(orig_operand, vm->env, &ref, FALSE) if (!ref) release lock error: unbound variable nargs = fetch_next() vm->pc[-2] = global_var_index(ref); vm->pc[-3] = ugref_invoke || push_ugref_invoke release_lock tailp = false goto funcall case push_ugref_invoke push(vm->val) fallthrough to ugref_invoke case ugref_invoke: release_possible_lock // because of optimization, we may get redispatched here vm->val = fetch_global() nargs = fetch_next(); tailp = false goto funcall case push_gref_tail_inv case gref_tail_invoke lock_and_restart orig_opcode = vm->pc[-1] orig_operand = fetch_const() if (orig_opcode == PUSH_REF_TAIL_INV) push(vm->val); vm->val = lookup(orig_operand, vm->env, &ref, FALSE); if (!ref) release_lock error: unbound variable nargs = fetch_next() vm->pc[-2] = global_var_index(ref); vm->pc[-3] = ugref_invoke || push_ugref_invoke release_lock tailp = true goto funcall case push_ugref_tail_inv push(vm->val) fallthrough to ugref_tail_invoke case ugref_tail_invoke: release_possible_lock // because of optimization, we may get redispatched here vm->val = fetch_global() nargs = fetch_next(); tailp = true goto funcall case local_ref0 { vm->val = frame_local(vm->env, 0); next1 } case local_ref1 { vm->val = frame_local(vm->env, 1); next1 } case local_ref2 { vm->val = frame_local(vm->env, 2); next1 } case local_ref3 { vm->val = frame_local(vm->env, 3); next1 } case local_ref4 { vm->val = frame_local(vm->env, 4); next1 } case local_refn { vm->val = frame_local(vm->env, fetch_next()); next1 } // local sets that do the same thing, but case deep_local_refn { /* STklos organizes local environments as this: each level has a maximum of 256 variables. Both the level and the address of local variables are encoded in a single 16-bit integer, as "256v1+v2". For example, 2*256 + 03 = 0x0203. The first byte, 0x02, identifies the level, and the second byte, 0x03, identifies the variable. */ e = vm->env; for level = first_byte(info); level; level-- e = frame_next(e); vm->val = frame_local(e, second_byte(info)) next1; } case deep_loc_ref_far { // arg is a cons, inefficient, but rare info = fetch_cons() typecheck_cons e = vm->env; for (level = int_val(car(info)); level; level--) e = frame_next(e) vm->val = frame_local(e, int_val(cdr(info))) next1 } case deep_loc_ref_push { e = vm->env; for level = first_byte(info); level; level-- e = frame_next(e); push(vm->val = frame_local(e, second_byte(info))) next1; } case(local_ref0_push) { push(frame_local(vm->env, 0)); next1;} case(local_ref1_push) { push(frame_local(vm->env, 1)); next1;} case(local_ref2_push) { push(frame_local(vm->env, 2)); next1;} case(local_ref3_push) { push(frame_local(vm->env, 3)); next1;} case(local_ref4_push) { push(frame_local(vm->env, 4)); next1;} case global_set { lock_and_restart orig_operand = fetch_const() lookup(orig_operand, vm->env, &ref, FALSE) if (!ref) release_lock error: unbound variable check_mutable vm_global_set(ref, vm->val) // patch for next time (avoiding lookups) vm->pc[-1] = global_var_index(ref) vm->pc[-2] = uglobal_set if (closure?(vm->val) && closure_name(vm->val) == false) { // handles (set! foo (lambda () ...))) so the lambda has the name <foo> closure_name(vm->val) = orig_operand } release_lock next } case uglobal_set { release_possible_lock fetch_global() = vm->val; next0; } /// case goto { offset = fetch_next() vm->pc += offset; next } // case jump_true // case jump_void // case jump_null case jump_false { offset = fetch_next() if (vm->val == false) vm->pc += offset next } // case jump_numeq: _numeq2(pop(), vm->val) // case jump_numlt: _numlt2(pop(), vm->val) // case jump_numle: _numle2(pop(), vm->val) // case jump_numgt: _numgt2(pop(), vm->val) // case jump_numge: _numge2(pop(), vm->val) case jump_numdiff { offset = fetch_next() if (!_numeq2(pop(), vm->val)) vm->pc += offset; next } // case jump_not_eqv: _eqv(pop(), vm->val) == false) // case jump_not_equal: _equal(pop(), vm->val) == false) case jump_not_eq { offset = fetch_next() if (pop() != vm->val) vm->pc += offset; next; } /// case define_symbol var = fetch_const() define_variable(var, vm->val, vm->env); if (closure?(vm->val) && closure_name(vm->val) == false) closure_name(vm->val) = var; vm->val = void; vm->vals[1] = var; vm->valc = 2 next; case set_current_mod vm->env = vm->val select_module(vm->val); next0; case pop: vm->val = pop(); next1 case push: push(vm->val); next1 case create_closure // pc[0] = offset, pc[1] = arity, pc[2+] = bytecode vm->env = clone_env(vm->env, vm) vm->val = make_closure(vm->pc+2, vm->pc[0]-1, vm->pc[1], vm->constants, vm->env) vm->pc += vm->pc[0] + 1 next1 case create_closure_far // closure, but with a pc[0] that's a long constant offset = look_const() typecheck_offset vm->env = clone_env(vm->env, vm) vm->val = make_closure(vm->pc+2, intval(offset)-1, vm->pc[1], vm->constants, vm->env) vm->pc = intval(offset) + 1 next1 case prepare_call { prep_call(); next; } case return { ret_call(); next; } case invoke nargs = fetch_next() tailp = false goto funcall case tail_invoke nargs = fetch_next() tailp = true goto funcall case push_prepare_call: push(vm->val); prep_call(); next; case enter_let_star: nargs = fetch_next(); // more or less prep_call, nargs * push, enter_let prep_call(); vm->sp -= nargs + frame push_env(nargs, vm->val, vm->env) vm->env = vm->sp next case enter_let: nargs = fetch_next // push a new env onto the stack, no new activation record vm->sp -= (sizeof(frame) - sizeof(scm)) / sizeof(scm) push_env(nargs, vm->val, vm->env) vm->env = vm->sp next case leave_let: vm->sp = vm->fp + ACT_RECORD_SIZE vm->env = frame_next(vm->env) vm->fp = ACT_SAVE_FP(vm->fp) next; case enter_tail_let_star: nargs = fetch_next(); // more or less prep_call, nargs * push, enter_let prep_call(); vm->sp -= nargs goto enter_tail_let_inner case enter_tail_let: nargs = fetch_next enter_tail_let_inner: old_fp = save_fp(vm->fp) if (is_in_stack?(vm->env)) { if (nargs) memmove((vm->env) - nargs, vm->sp, nargs * sizeof(SCM)) vm->fp = old_fp // push a new env onto the stack vm->sp = vm->env - nargs - (sizeof env) } else { if (nargs) memmove((vm->env) - nargs, vm->sp, nargs * sizeof(SCM)) vm->fp = old_fp vm->sp = vm->fp - nargs - (sizeof env) } push_env(nargs, vm->val, vm->env) vm->env = vm->sp next case formals case docstring case procname case source item = fetch_const typecheck val is a closure closure_plist(vm->val) = key_set(closure_plist(vm->val), key_type, item) next case call_location save_info(vm->fp) = cons(pop(), makeint(fetch_next())) next1 case inscheme: vm->val = symb_in_scheme(vm->val) next1 // inlined funcs inadd2, insub2, inmul2, indiv2 // small ints fxadd2, fxsub2, fxmul2, fxdiv2 // fixnum vref, sref, aref funcall: switch type(vm->val) case tc_instance if (puregeneric? vm->val) argv = vm->sp + sargs - 1 methods = compute_applicable_methods(vm->val, nargs, argv, false) if (!methods) vm->val = void && return; nm = make_next_method(vm->val, nargs, argv, methods); vm->val = inst_slot(car(methods), s_procedure) set_next_method(vm->val, nm); else // pure generic args = listify_top(nargs, vm) push(vm->val) push(args) vm->val = lookup(intern("apply-generic"), vm->current_module, &gf, false) nargs = 2 goto funcall // fallthrough to closure case tc_closure: nargs = adjust_arity(vm->val, nargs, vm) if (tailp) // tail call, reuse the frame old_fp = act_save_fp(vm->fp) if (nargs) memmov(old_fp-nargs, vm->sp, nargs * sizeof(scm)) vm->fp = old_fp vm->sp = push new env onto stack push_env(nargs, vm->val, closure_env(vm->val)) else // tail vm->sp = push new env onte stack push_env(nargs, vm->val, closure_env(vm->val)) act_save_env(vm->fp) = vm->env act_save_pc(vm->fp) = vm->pc act_save_constants(vm->fp) = vm->constants act_save_proc(vm->fp) = vm->val call_closure(vm->val) goto end_funcall case tc_next_method: methods = NEXT_METHOD_METHODS(vm->val); // build up the funcall to the nextmethod, with the next-methods list popped goto funcall case tc_apply: // move the arguments down in the stack // then unfold the last argument into the stack // then funcall case tc_subr0: call_prim0(vm->val, ()); break; case tc_subr1: call_prim1(vm->val, (vm->sp[0])); break // tc_subr2 // tc_subr3, 4, 5 // tc_subr01 (effectively subr1, with a default null if 0 given) // tc_subr12, 23, 34 // var args case tc_vsubr: call_primv(vm->val, (nargs, vm->sp + nargs - 1)) // callable setters case tc_parameter: if nargs == 0: vm->val = get_paramater(vm->val)
- vm implements an event loop
- run some bytecode & wait for events
- scheduler and ability to run multiple parallel loops = preemptive os scheduling
- one loop per core; one loop designated system loop (so kernel can assume single core)
- “preemptive” at the bytecode instruction level
- maybe we don’t need a timer, because bytecode dispatch and garbage collection give natural fine-grained preemption points
- interrupts push priority messages to the kernel loop for dispatch
- watchdog timer interrupts to make sure we’re proceeding
- vm implements the MOP!
- bytecodes for stack/heap gc + buffer/page management
- the vm should handle physical memory
- what does virtual memory look like in this system?
- on the one hand, we’re going for lexical capabilities rather than memory protection
- on the other, the ability to map pages is really important for crash/swap/persistance etc
- bytecodes for lexical environment get/set (local, upvalue, thread (dynamic), global)
- bytecodes for closure management (create, call)
- bytecodes for delimited continuations
- the vm doesn’t have indefinite continuations, only prompt/return or something like that
- the os supplies the continuation representing the process caller, which is effectively indefinite to the process
- bytecodes for generic methods (create, dispatch, add impl)
- this is where subtyping and equality exist
- dispatch is lexical! the methods have to be visible in our scope
- otherwise, there’s no way to make a fully private closure
- so there can’t be like a global table for dispatch
- bytecodes for event loop
- push current time, ticks, ip, etc.
- dispatch on task
- task -> queue
- message -> system
- bytecodes for allowing direct machine access
- hal (registers, low-level io access, etc)
- bytecodes to run arbitrary asm blocks
- careful with this, since there’s no timer based preemption
- is it really reified all the way down if the vm isn’t flexible?
- maybe a bytecode to add new bytecodes
assembletakes a module body, outputs an<asm-module>- module body syntax:
(import (some module name) ...):: makes the comptime environment available(import prefix (some module name))):: import + allows references to module scoped labels under prefix(export label ...):: makes this label visible externally (module-scoped)(code (args) ...):: creates a code section (args are link args)(data (args) ...):: creates a data section (args are link args)(zeros (args) ...):: creates a data section with only zeroed reservations
(import (miriam asm prelude)) (import vm/ (miriam vm)) (entry main) (export utility-a utility-b some-data-table) (define (comptime-func arg) (do something)) (define comptime-data (something-something)) (data (label some-data-table) (resv ,(data->bytevector comptime-data) (resv "something something something")) (zeros (label some-results-table) (resz 16 mb)) (pseudo (special-ret) `((mov pc lr))) (code (block main (:naked) (mov r0 #x34) (mov r1 #x12) (bl some-func) (b ?nz vm/alloc-cons) (special-ret)) (block utility-a (:ccall) (mov r0 #56) (ret)) (block utility-b (:ccall) (...)) ;; not exported, hence private ;; (ie. the code is compiled into the code section, but the label is invisible) (block utility-c (:naked) (...))) - module output:
(<asm-module> (section code #vu8(...)) (section data #vu8(...)) (section zero size) (link (module section) (module section)) (reloc (reloc-type (module name) label patch-at) (reloc-type (module name) label patch-at) (reloc-type (module name) label patch-at)) (exports (label section offset) (label section offset)))
- module body syntax:
- linking the final executable image:
- topological sort dependencies, and figure out runtime offsets
- in order of dependencies:
- write out module’s bytestream
- fixup any outstanding relocations
Certainly! Having more than one data section in an ARM assembler module can be quite useful in several scenarios:
- **Segmentation of Different Data Types**: You might want to separate different types of data. For instance, one section could be dedicated to initialized data (`.data`), another for uninitialized data (`.bss`), and yet another for read-only data (`.rodata`). This helps in organizing data logically and can also assist in memory management.
- **Memory Access Control**: Different data sections can have different memory access properties. For example, you might want a data section that is read-only (to store constants or configuration data) and another that is writable (for mutable data). This can enhance security and prevent accidental modification of critical data.
- **Efficiency in Loading and Memory Usage**: Separating data into different sections allows for more efficient loading and memory usage. Data that is not required immediately (or rarely accessed) can be loaded or paged in as needed, reducing the initial memory footprint.
- **Optimization for Cache Usage**: By grouping frequently accessed data together in one section and less frequently accessed data in another, you can optimize for cache usage. This is because data that is accessed together is more likely to be loaded in the cache together, reducing cache misses.
- **Linker Script Control**: In complex projects, especially those involving multiple libraries or modules, having multiple data sections gives you finer control in linker scripts. You can allocate different sections to different memory regions or perform other advanced memory management tasks.
- **Debugging and Profiling**: Having separate data sections can aid in debugging and profiling. For instance, you can easily monitor the access patterns and modifications to different sections, helping identify bugs or performance bottlenecks related to data usage.
- **Support for Special Hardware Requirements**: Some embedded systems or special-purpose hardware might have specific requirements for data storage (like aligning certain data types to specific memory boundaries). Multiple data sections can help meet these hardware-specific requirements.
- **Modularity and Maintenance**: In large applications, different modules or components might manage their own data. Having separate data sections for each module can make the code more modular and easier to maintain.
- **Conditional Compilation**: In some scenarios, you might want to include or exclude certain data based on compile-time options. Having multiple sections can make this process cleaner and more manageable.
- **Memory Protection and Security**: If the operating system or environment supports it, different data sections can be assigned different protection levels (like non-executable, no-write, etc.), enhancing the overall security of the application.
In summary, multiple data sections in an ARM assembler module can provide benefits in terms of organization, efficiency, security, and flexibility. The specific use cases would depend on the requirements and complexity of the project you’re working on.
– ChatGPT, in response to “I’m writing an assembler for arm as a hobby project, and I’m trying to figure a use-case for having more than one data section in a module; can you think of any?”
with the ability to “descope” labels (refer to the same name at a higher scope explicitly), we’re
able to do some nifty pseudo macros without running into label naming conflicts.
next is to really dig into the COMFY core stuff that sassy uses, which, surprise is based on an H. Baker paper: a comfortable set of control primitives for asm programming
(pseudo (delay reg count)
`((mov ,reg ,count)
(scope
(subs ,reg ,reg 1)
(b ?ne $enter))))
(pseudo (if cond then else)
`((scope
(scope
(b ,(condition-invert cond) $exit)
,@then
(b $exit^)))
,@else))
(pseudo (when cond . then)
`(scope
(b ,(condition-invert cond) $exit)
,@then))
(pseudo (while test cond . then)
`(scope
,test
(b ,(condition-invert cond) $exit)
,@then
(b $enter)))
;; ---
(block main ()
(bl some-function-that-sets-flags)
(when ?ne
(delay r9 150)))
;; --- expands to:
(block main ()
(bl some-function-that-sets-flags)
(b ?eq $exit) ;; scoped to the when, +10 or whatever
(mov r9 150)
(subs r9 r9 1)
(b ?ne $enter)) ;; scoped to the deloy, -4
there’s a simple emacs major mode for “miriam scheme” now, which automatically sets up some of the indentation for macros and syntax highlighting for the assembler.
I’ll probably break it up into “miriam-scheme” and “miriam-asm” modes, since I’ll want to not have
the highlighting on pseudo and the like in the scheme code, but for now it’s pretty nice.
– blog post idea: how to do that?
For now, everything is just nicely setup in the .dir-locals.el file; just opening a file in the
project in emacs will prompt and then apply everything.
If it’s ever a necessity to export it, it’ll need more clean up.
I’m realizing, reading examples of getting various peripherals up, that I need a linker.
- I need some kind of serializable output format (elf but s-expr)
- I need some kind of “module” system in the assembler, so that I can collect modules and layout them out
- I want to be able to <import>, rather than <include>
- a module has assemble-time parts, and run-time parts
- assemble-time: pseudos, definitions, relocation/link-instructions?
- run-time: actual code blocks, data sections
- a value is a (little-endian) 32-bit word
- a value can be either an immediate or an object
- an object is a pointer to an objects header word
- an immediate is any 32-bit word that is non-zero in the low two bits
ergo, “unaligned pointers” represent immediates
constraints:
- we can only mask-test 8-bits at a time with arm instructions
type xxxxxx00 <- pointer 00000001 <- fixnum 00000010 <- fixnum check bit 11111101 <- true 11111110 <- false 11111111 <- void
gc info type size 76543210 FEDCBA98 76543210 FEDCBA98 ggggtttt ssssssss ssssssss ssssssss g7 = forwarded? g6 = special? (skipped by gc) g5 = align? (align based on size) g3 = t = type s = size (in words if align?)
turns out these are thumb only
some instructions not to forget about:
- cbnz, cbz
- compare and branch on nonzero/zero
cbz rn, label==cmp rn, 0; b ?eq labelcbnz rn, label==cmp rn, 0; b ?ne label
- tbb, tbh
- test and branch byte/half-word
- causes a PC-relative forward branch from a table of single-byte or half-word offsets
general outline of the runtime system, based on a bunch of reading that I’ve been doing:
- cps conversion + cheney/mta style garbage collection
- the stack is the nursery of the garbage collectior
- “heap allocation” is pushing to the stack
- when the stack hits the end of it’s page, minor GC
- this will scan the stack page, copy out objects to the old-space
- then trash the stack page and teturn a new one, with
- heap allocation is simply pushing to the stack
- limit the stack size to a page
- when a requested allocation hits the page boundary, minor GC
- this will scan the stack page, copy out objects to some other pages, and then reset the stack pointer
- with CPS this is straightforwardish
immutable first, like clojure
- it makes reasoning about things easier
- see this good paper on object identity, which makes good cases for “everything is an immutable value, including the reference to a mutable box”.
- h. baker: ‘infant mortality’ and generational garbage collection
- h. baker: cons should not cons it’s arguments; lazy alloc
- h. baker: cons should not cons it’s arguments pt 2; cheny on the mta
- chicken internals: the garbage collector
- chicken internals: object representation
- maclisp – the basic hackery (bibop collection, 100% different than chicken, referenced)
- a. appel: runtime tags aren’t necessary
these are brilliant papers on utilizing the stack for the nursery of a generational garbage collector the chicken paper in particular, since I’m much better at reading code examples
h. baker’s papers are really really good you guys.
completely unrelated, it sucks that scheme doesn’t have symbol macros.
I think miriam should have a few CL and clojure features added; the language can drift some scheme, absolutely.
- keywords! basically symbols, but can’t be used in a calling position
- especially if we end up doing symbol macros for things like generalized
set!, we need a simpler type than a symbol- a
keywordis an interned string, which has pointer equality and is guaranteed to match - a
symbolis a record, comprised of a keyword and attribute slots forset!,get!, possibly a metatable, etc.
- a
- especially if we end up doing symbol macros for things like generalized
- drop the syntactic tower and just use unhygenic macros
- use
0xrather than#xfor number syntaxes- that frees up the
#for user-defined reader macros
- that frees up the
- reader macros, such that we can define arbitrary new
#something()syntaxes- ie. regex
#/\d+/, timestamps#t<1985-02-01T00:00:00.000000+06:00>, xml#xml<foo><bar /></foo>etc. - these should probably support unquote, ie.
#xml<foo type=,attr>,(gen-content)</foo>
- ie. regex
- some kind of generic method/multiple dispatch on user-provided predicates, rather than just
case-lambda- this is basically clos, or the
metatablestuff from lua, metaclasses in ruby, prototypes from javascript - generalized
set!, with symbol macros allowing for deeply nested sets- that lets us create arbitrary “setters” for meta-functions
- ie.
(set! (set-handler 'accessor) set-accessor!), which might allow(set! (accessor x) value)
- similarly, a generalized get! - ie.
(get object key)- corresponds to luaindexmetamethod - does this extend to
make, ie generalized constructors? - generic
read,writeanddisplay- anything interesting to read here re: haskell optics, etc?
- can we specialize these at compile time?
- method combiner in clos is cool:
- you can specify on a generic function that, rather than only calling the most specific, you
can use a different operator; ie.
(defgeneric foo (obj) (:method-combination list))would run all applicable methods and bundle values into a list; imaginefold,beginetc. as combination operators
- you can specify on a generic function that, rather than only calling the most specific, you
can use a different operator; ie.
- a lot of this is reminiscent of the ruby class hierarchy as well
prependappendmodules for overrides?
- this is basically clos, or the
- string interpolation (cheeky:
"is a reader macro which compiles to a series ofstring:appendcalls)
you could think of the dotted record syntax like an expansion of the get! macro:
(list p.x p.y) -> (list (get! p x) (get! p y)) -> (list (p-get-x p) (p-get-y p)) (set! p.x 42) -> (set! (get! p x) 42) -> (set! (p-get-x p) 42) (p.something 50) -> ((get! p something) 50) -> (p-something 50)
part of the reason I keep reaching for relatively inefficient cons and alists is that (asm-context
asm) is almost as bad as (cadr asm) in terms of code-reading density; I’d much rather
asm.context.
see cl21 (unofficial proposal for cleanup of commonlisp)
^as a reader macro to give short lambdas(map ^(+ 1 %) some-list)
- some kind of automatic currying, possibly with a reader macro to defend against accidental calls
- this may be less frustrating with the above macro
cleaned up the assembler a good bit; mostly encapsulating the context that gets passed around the
assembler functions; I may switch these all to take them implicitly, actually, since I moved
assemble into being a function, rather than syntax.
additionally, started in on a really simple driver, pulling code from a file, rather than directly inline.
as I’m starting to think about global variables, I’m reading about how ELF does relocation for ARM, and it’s much more complicated than what I’m doing:
- me:
- when a relocation is needed, store the form
- when a relocation is resolved, reassemble the form at the point, and replace
- elf:
- when a relocation is needed, record the exact form of relocation
- when relocation is resolved, the instruction at the offset is extracted, and reencoded by the instruction
- relocation types (skipping thumb)
R_ARM_PC24, (b #imm24), pcrelative, “bits 0-23 signed offset in units of 4-byte words”R_ARM_PC13, (ldr r #imm13) “bits 0-11 unsigned offset, bit 13 encodes sign (0 = -, 1 = +)”R_ARM_ABS12, LDR/STR immR_ARM_SWI24, (swi #imm24)- explicitly sized, unencoded relocations
R_ARM_ABS32, any 32-bit word, (probably data sections?)R_ARM_REL32, any 32-bit wordR_ARM_ABS16, any 16-bit halfword (probably data sections?)R_ARM_ABS8, any 8-bit byteR_ARM_SBREL32, any 32-bit word, relative to the section boundary
pros of the elf way:
- don’t have to have the assembler present to relocate
- relocations can work at program load time, rather than assembly time (dynamic loader)
as such, I’m going to convert to this model; the instructions will encode relocations as tuples like
(label fillptr (reloc-type args)), and relocation time can use the reloc-type to do the actual
in-place patching.
elf is pretty set on various posixy things, I don’t need that, I can just marshal to external reps
(%compiled-module (export . (exported exported2 exported3)) (import . ((module name defun) ...) (code . #vu8(0 0 0 ....) (reloc . ((label offset (reloc-type arg)) ...)
then “execution” is, like on linux, the composing of the modules into a memory space and jumping into it
(define) and (pseudo) seem like they’re working!
Also, I read an interesting blog post positing an arm emulator as a unit testing framework; basically:
(block some-function (:callconv)
(do
(some)
(stuff)))
(test
;; memory pseudo signals the emulator to place the values in memory
(memory #x1200 (word #x22334455))
;; non-test are executed
(bl some-function)
;; assert pseudo signals to do the tests on the emulated cpu
(assert (reg-eq? pc lr))
(assert (memory-eq? #x4032 #\h)))
The `test` blocks are normally ignored by the assembler, but when running in “test” mode, insert breakpoint calls, and then assert the state of an emulated cpu + memory.
Interesting idea, and it would only require a somewhat minimal cpu emulation, because we don’t need all the various devices, only the cpu and the ability to control the visible memory.
See: https://mos.datatra.sh/guide/unit-testing.html
well, this is cool!!
- run assembler test, it outputs a binary file
- at byte 512 is #xAA55, which is signal that this is a boot sector
- qemu-system-arm -machine raspi1b -kernel a.out -s -S
- eabi-arm-none-gdb
- target remote localhost:1234
- layout asm
- si
it booted! kinda!
scopesis a stack of symbols- ’() means the top-level
- the car of the stack is the current scope
labelsis an alist of alists((label . ((scope-sym . offset) (scope-sym . offset))))
push-label- adds a label at the current offset to the current scope
push-reloc- adds a relocation entry, which includes the current stack of scopes
fixup-relociterates through the saved stack of scopes, looking for a label that matches both the scope and symbol name.since top-level labels are stored with the empty scope as a key, they’re naturally included in the search
(label foo)
(some-instruction)
(block name ()
(some-instruction)
(bl ?q $exit)
(some-instruction)
(bl ?q $enter))
(some-instruction)
(bl foo)At the high level, there’s the assembler syntax itself:
(assemble
;; opcodes are instruction mnemonics
(mov r1 (r2 lsl 2))
(adcs r1 r3 r2)
;; unquote and unquote-splice access the compile-time environment
(mov r1 (r2 lsl ,(name 1 2)))
;; labels capture the current offset
(label name)
;; blocks are labels with bodies that may use some block-specific syntax
;; $enter is a virtual label for just before the block prologue (flags) (more or less synonym for the block name)
;; $start is a virtual label for just after the block prologue (flags) (for tail-cails)
;; $end is a virtual label for just before the block epilogue (flags) (for early exit)
;; $exit is a virtual label for just after the block epilogue (flags) (for data offsets, maybe)
(block name ()
(mov r1 (r2 lsl 2))
(adcs r1 r3 r2))
;; definitions are valid at compile-time
(define (name a1 a2)
(some-calc a1 (ulation a2)))
;; you can import definitions from elsewhere as well
(import (miriam asm prelude))
;; pseudos syntactically modify the opcode forms
;; and run in the compile-time environment (macros)
(pseudo (movi rd value)
(movw rd ,(b& value #xFFFF))
(movt rd ,(b>> value 16))))(org #x1000)
(entry _start)
(extern sys-exit)
(pseudo (movimm32 reg imm)
(if/let ((imm (u/s-word imm)))
`((movw ,reg ,(b& imm #xFFFF))
(movt ,reg ,(b>> imm 16) (lsl 16))))
(syntax-error "expected imm to be a u/s-word"))
(procedure _start (naked)
(ldr r0 instr)
(ldr r1 outstr)
(mov r3 0)
(movimm32 instr)
(block
(ldrb r2, (r0 ++), #1)
(cmp r2 0)
(b ?eq $end)
(cmp r2 r3)
(b ?eq $start)
(strb r2 (r1 ++) #1)
(mov r3 r2)
(b $start))
(bl null-write)
(bl sys-exit))
(procedure null-write ()
(block
(ldrb r1 r0) ; load the byte from the string
(cmp r1 0) ; if we've hit the null-terminator, bail
(b ?eq $end)
(add r0 r0 #1) ; otherwise, incr the pointer and loop
(b $start))
(ldr r2 sp -4) ; get the stored input address into r2
(sub r1 r0 r2) ; calculate length
(ret))
(data ()
(instr (res "I just want this thiiiing to woooork!"))
(outstr (res (bytes 128))))