module: access-path-implementation synopsis: Experimenting with a more complex simulated runtime. author: Paul Howard Copyright: Original Code is Copyright (c) 1995-2004 Functional Objects, Inc. All rights reserved. License: Functional Objects Library Public License Version 1.0 Dual-license: GNU Lesser General Public License Warranty: Distributed WITHOUT WARRANTY OF ANY KIND ///// THE INSTRUCTION SET define constant $CALL = 1000; // define constant $RET = 1001; define constant $LINK = 1002; define constant $SPAWN = 1003; // define constant $END = 1004; define constant $NOP = 1005; define constant $STOPCODE = 1006; // define constant $LOCALASSIGN = 1008; // define constant $GLOBALASSIGN = 1009; // define constant $LDA = 1010; define constant $JREL = 1011; define constant $JRELNZ = 1012; define constant $DECA = 1013; define constant $INCA = 1014; define constant $PUSHA = 1015; define constant $POPA = 1016; define method I(x) (x * 4) + 1 end method; define method C(x) (as(, x) * 4) + 2 end method; ///// // The memory, innit! define constant $memory-size = 2000; define constant $stack-size = 50; define class () slot contents :: = make(, size: $memory-size, fill: $NOP); slot breakpointed? :: = #[]; slot code-segment-start :: = 0; slot data-segment-start :: = 0; slot next-stack-position :: = $memory-size - 1; slot stack-size :: = $stack-size; slot dump-pointer :: = 0; end class; ///// // Models the context of a running thread. define class () slot eip :: , required-init-keyword: start-routine:; slot name :: , init-value: "Un-named Thread", init-keyword: name:; slot still-alive? :: = #t; slot zero-flag :: = #f; slot esp :: = 0; slot ebp :: = 0; slot eax :: = 0; slot ebx :: = 0; slot current-unwind-protect :: = 0; slot suspend-count :: = 0; end class; ///// // Describes lexical/argument variables. define class () slot name :: , required-init-keyword: name:; slot offset :: , required-init-keyword: offset:; end class; ///// // Is pushed onto a queue when generated by the application. The // access-path function "wait-for-stop-reason" pops this queue. define class () slot stop-reason-code :: , required-init-keyword: code:; slot related-simulation-object, init-value: #f, init-keyword: simulated-object:; slot signalling-thread :: , required-init-keyword: thread:; slot address :: , init-value: 0, init-keyword: address:; end class; ///// // Provides enough information to "call" a function, and set // up its stack frame. define class () slot symbolic-name :: , required-init-keyword: name:; slot compiled-address :: = 0; // Needs fixup // The first instruction in most functions will be $LINK, // a one "byte" instruction, but we might as well allow it // to be different. slot debug-start-offset :: , init-value: 1, init-keyword: debug-start-offset:; slot debug-end-offset :: = 0; // Needs fixup slot code-vector :: , required-init-keyword: code-vector:; slot arguments :: , required-init-keyword: arguments:; slot lexicals :: , required-init-keyword: lexicals:; slot line-offset-pairs :: , init-value: #[], init-keyword: known-locations:; slot source-filename :: = "UNKNOWN", init-keyword: file:; slot source-linenumber :: = 0, init-keyword: line:; end class; ///// // Models a variable. define class () slot symbolic-name :: , required-init-keyword: name:; slot dumped-address :: = 0; slot mode :: , init-value: #"static", init-keyword: mode:; slot representation :: , init-value: #[], init-keyword: representation:; end class; ///// // A mapping for code/source locators within a file. define class () slot filename :: , required-init-keyword: filename:; slot line-address-pairs :: = make(); end class; ///// // A mapping for code/source locators in the simulated runtime. define class () slot number-of-files :: , init-value: 0, init-keyword: file-count:; slot file-information :: = make(, size: 0); end class; ///// // The simulated runtime. define class () slot memory :: = make(); slot debug-info :: , init-value: #[]; slot source-map :: ; slot threads :: = make(, size: 0); slot new-threads :: = make(, size: 0); slot stop-reason-queue :: = make(); end class; // ************************************************************************ // ******************************* RUNTIME ******************************** // ************************************************************************ ///// MACHINE-CYCLE // Steps all threads through one instruction. define method machine-cycle (sim :: ) => () let threads-stepped = 0; for (thread in sim.threads) if (thread.still-alive?) unless (thread.suspend-count < 0) fetch-execute(sim, thread); end unless; threads-stepped := threads-stepped + 1; end if; end for; if (size(sim.new-threads) > 0) sim.threads := concatenate!(sim.threads, sim.new-threads); sim.new-threads := make(, size: 0); end if; /* if (threads-stepped == 0) push(sim.stop-reason-queue, make(, code: $exit-process, thread: sim.threads[0], address: sim.threads[0].eip)) end if; */ end method; ///// FETCH-EXECUTE // Steps the thread through one instruction, queueing a stop-reason // if necessary. define method fetch-execute (sim :: , thread :: ) => () let bp-state = element(sim.memory.breakpointed?, thread.eip, default: #"clear"); if (bp-state == #"break") push(sim.stop-reason-queue, make(, code: $breakpoint-exception, thread: thread, address: thread.eip)); sim.memory.breakpointed?[thread.eip] := #"replace"; else if (bp-state == #"replace") sim.memory.breakpointed?[thread.eip] := #"break"; end if; let opcode = sim.memory.contents[thread.eip]; thread.eip := thread.eip + 1; select(opcode) $CALL => let addr = sim.memory.contents[thread.eip]; thread.eip := thread.eip + 1; thread.esp := thread.esp - 1; sim.memory.contents[thread.esp] := thread.eip; thread.eip := addr; // format-out ("-- CALL %d\n", addr); $RET => // Callee pops args and lexicals thread.esp := thread.ebp + 1; thread.ebp := sim.memory.contents[thread.ebp]; let ret-addr = sim.memory.contents[thread.esp]; thread.esp := thread.esp + 1; thread.eip := ret-addr; // format-out("-- RET\n"); $LOCALASSIGN => let offset = sim.memory.contents[thread.eip]; thread.eip := thread.eip + 1; let val = sim.memory.contents[thread.eip]; thread.eip := thread.eip + 1; sim.memory.contents[thread.ebp + offset] := val; // format-out("-- LOCALASSIGN %d %d\n", thread.ebp + offset, val); $GLOBALASSIGN => let dest = sim.memory.contents[thread.eip]; thread.eip := thread.eip + 1; let val = sim.memory.contents[thread.eip]; thread.eip := thread.eip + 1; sim.memory.contents[dest] := val; // format-out("-- GLOBALASSIGN %d %d\n", dest, val); $LINK => let function-description = map-eip-to-function(sim, thread.eip - 1); thread.esp := thread.esp - 1; sim.memory.contents[thread.esp] := thread.ebp; thread.ebp := thread.esp; // Now create enough space for lexicals and args. thread.esp := thread.esp - (size(function-description.arguments) + size(function-description.lexicals)); // format-out("-- LINK\n"); $SPAWN => let newthread = make(, start-routine: sim.memory.contents[thread.eip]); newthread.esp := sim.memory.next-stack-position; sim.memory.next-stack-position := sim.memory.next-stack-position - sim.memory.stack-size; thread.eip := thread.eip + 1; push(sim.stop-reason-queue, make(, thread: newthread, code: $create-thread, address: thread.eip - 2)); sim.new-threads := add!(sim.new-threads, newthread); // format-out("-- SPAWN %d\n", newthread.eip); $END => // Find out if we're the last living thread. If we are, push // the exit-process-stop-reason rather than exit-thread-stop-reason let live-thread-count = 0; for (t in sim.threads) if (t.still-alive?) live-thread-count := live-thread-count + 1; end if end for; for (t in sim.new-threads) if (t.still-alive?) live-thread-count := live-thread-count + 1; end if end for; if (live-thread-count < 2) push(sim.stop-reason-queue, make(, thread: thread, code: $exit-process, address: thread.eip - 1)); else push(sim.stop-reason-queue, make(, thread: thread, code: $exit-thread, address: thread.eip - 1)); end if; thread.still-alive? := #f; // format-out("-- END\n"); $JREL => let offset = sim.memory.contents[thread.eip]; thread.eip := thread.eip + 1; thread.eip := thread.eip + offset; // format-out("-- JREL %d\n", offset); $JRELNZ => let offset = sim.memory.contents[thread.eip]; thread.eip := thread.eip + 1; if (~thread.zero-flag) thread.zero-flag := #f; thread.eip := thread.eip + offset; end if; // format-out("-- JRELNZ %d\n", offset); $INCA => thread.eax := thread.eax + 1; unless(thread.eax == 0) thread.zero-flag := #f end unless; // format-out("-- INCA\n"); $PUSHA => thread.esp := thread.esp - 1; sim.memory.contents[thread.esp] := thread.eax; unless(thread.eax == 0) thread.zero-flag := #f end unless; // format-out("-- PUSHA\n"); $POPA => thread.eax := sim.memory.contents[thread.esp]; thread.esp := thread.esp + 1; unless(thread.eax == 0) thread.zero-flag := #f end unless; // format-out("-- POPA\n"); $DECA => thread.eax := thread.eax - 1; if (thread.eax == 0) thread.zero-flag := #t; end if; // format-out("-- DECA\n"); $LDA => thread.eax := sim.memory.contents[thread.eip]; thread.eip := thread.eip + 1; unless(thread.eax == 0) thread.zero-flag := #f end unless; // format-out("-- LDA %d\n", thread.eax); $NOP => thread.still-alive? := thread.still-alive?; // Do _something_ !! // format-out("-- NOP\n"); $STOPCODE => let stopcode = sim.memory.contents[thread.eip]; thread.eip := thread.eip + 1; push(sim.stop-reason-queue, make(, thread: thread, code: stopcode, address: thread.eip - 2)); // format-out("-- STOPCODE %d\n", stopcode); end select end if end method; // *********************************************************************** // **************** INJECTING DATA INTO THE SIMULATION ******************* // *********************************************************************** ///// DUMP-VALUE // Injects a value into the simulation. define method dump-value (sim :: , value) => () sim.memory.contents[sim.memory.dump-pointer] := value; sim.memory.dump-pointer := sim.memory.dump-pointer + 1; end method; ///// ALIGN // Aligns the dump address to a 4-byte boundary for the next dump. // (Instances of objects must be 4-byte aligned). define method align (sim :: ) => () let (div, rem) = truncate (sim.memory.dump-pointer, 4); if (rem > 0) sim.memory.dump-pointer := sim.memory.dump-pointer + (4 - rem); end if end method; ///// BEGIN-CODE-SEGMENT // Signals that the code segment starts here. define method begin-code-segment (sim :: ) => () sim.memory.code-segment-start := sim.memory.dump-pointer; end method; ///// BEGIN-DATA-SEGMENT // Signals that the data segment starts here. define method begin-data-segment (sim :: ) => () sim.memory.data-segment-start := sim.memory.dump-pointer; end method; ///// END-OF-DUMP // Signals that we've finished dumping. define method end-of-dump (sim :: ) => () end method; ///// START-OF-DUMP // Signals that we're starting dumping. define method start-of-dump (sim :: ) => () end method; ///// RESET-RUNTIME // Puts the simulation into a "reset" and ready-to-go state. define method reset-runtime (sim :: ) => () sim.memory.next-stack-position := $memory-size - 1; sim.memory.breakpointed? := make(, size: sim.memory.data-segment-start, fill: #"clear"); let primary-thread = make(, start-routine: 0); primary-thread.esp := sim.memory.next-stack-position; sim.memory.next-stack-position := sim.memory.next-stack-position - $stack-size; sim.threads := make(, size: 0); sim.threads := add!(sim.threads, primary-thread); sim.new-threads := make(, size: 0); sim.stop-reason-queue := make(); push(sim.stop-reason-queue, make(, code: $create-process, thread: primary-thread, address: 0)); end method; ///// FIXUP-ADDRESSES // Goes through the memory code and data segments, and any // entries which aren't integers are assumed to point to // or // instances. The memory locations are overwritten with the // compiled addresses of these symbols. define method fixup-addresses (sim :: ) => () let i = sim.memory.code-segment-start; while (i < sim.memory.dump-pointer) if (instance?(sim.memory.contents[i], )) sim.memory.contents[i] := sim.memory.contents[i].compiled-address; elseif (instance?(sim.memory.contents[i], )) sim.memory.contents[i] := sim.memory.contents[i].dumped-address; end if; i := i + 1; end while end method; ///// LINK-SIMULATION // Assuming that the vector of debug-info has been installed, builds // the runtime simulation define method link-simulation (sim :: ) => () let i = 0; local method dump-functions () let sym = sim.debug-info[i]; while (instance?(sym, )) align(sim); sym.compiled-address := sim.memory.dump-pointer; for (x in sym.code-vector) dump-value(sim, x); end for; i := i + 1; sym := element(sim.debug-info, i, default: #f); end while; end method, method dump-variables () let sym = sim.debug-info[i]; while (instance?(sym, )) align(sim); sym.dumped-address := sim.memory.dump-pointer; for (x in sym.representation) dump-value(sim, x); end for; i := i + 1; sym := element(sim.debug-info, i, default: #f); end while; end method; start-of-dump(sim); begin-code-segment(sim); dump-functions(); begin-data-segment(sim); dump-variables(); end-of-dump(sim); fixup-addresses(sim); end method; ///// MAP-EIP-TO-FUNCTION // Given a program counter, returns the // whose definition straddles that address. define method map-eip-to-function (sim :: , addr :: ) => (_ :: ) let i = 0; let sz = size(sim.debug-info); let found = #f; let candidate = sim.debug-info[i]; while ((~found) & (instance?(candidate, ))) if ((candidate.compiled-address <= addr) & (addr < (candidate.compiled-address + size(candidate.code-vector)))) found := #t; else i := i + 1; candidate := sim.debug-info[i]; end if end while; candidate; end method; // *********************************************************************** // ********************* DESCRIBING THE SIMULATION *********************** // *********************************************************************** ///// GENERATE-RUNTIME-VECTOR // This throws out a vector of debug-info, which is resolved into the // the runtime and fixed-up by a fake "linking" process. If I have // this right, it should be possible to alter the simulation _just_ // by altering this function. The one proviso is that certain // symbols (eg KLmm_wrapperGYdylanVdylanW) must exist // in order for anything sensible to happen. define method generate-runtime-vector () => (_ :: ) let SIMRT!-wrapper = make(, name: "KLmm_wrapperGYdylanVdylanW", representation: vector(#f)); SIMRT!-wrapper.representation[0] := SIMRT!-wrapper; let SIMRT!-wrapper = make(, name: "KLclassGYdylanVdylanW", representation: vector(SIMRT!-wrapper, #f)); let SIMRT! = make(, name: "KLclassGYinternalVdylan", representation: vector(SIMRT!-wrapper)); SIMRT!-wrapper.representation[1] := SIMRT!; let SIMRT! = make(, name: "KLbyte_stringGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLbyte_stringGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLsimple_object_vectorGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLsimple_object_vectorGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLpairGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLpairGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLbooleanGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLbooleanGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLgeneric_functionGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLgeneric_functionGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLmethodGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLmethodGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLslot_methodGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLslot_methodGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLcomplex_methodGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLcomplex_methodGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLsymbolGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLsymbolGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLopen_classGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLopen_classGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLsealed_classGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLsealed_classGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLinstance_slot_descriptorGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLinstance_slot_descriptorGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLrepeated_slot_descriptorGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLrepeated_slot_descriptorGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT! = make(, name: "KLempty_listGYinternalVdylan"); let SIMRT!-wrapper = make(, name: "KLempty_listGYdylanVdylanW", representation: vector(SIMRT!-wrapper, SIMRT!)); let SIMRT!%empty-list = make(, name: "KPempty_listYinternalVdylan", representation: vector(SIMRT!-wrapper)); let SIMRT!%empty-vector = make(, name: "KPempty_vectorYinternalVdylan", representation: vector(SIMRT!-wrapper, I(0))); let SIMRT!%true = make(, name: "KPtrueYinternalVdylan", representation: vector(SIMRT!-wrapper)); let SIMRT!%false = make(, name: "KPfalseYinternalVdylan", representation: vector(SIMRT!-wrapper)); let poo-slot = make(, name: "poo_slotYdummymodVdummylib", representation: vector(SIMRT!-wrapper, SIMRT!%empty-list)); let pants-slot = make(, name: "pants_slotYdummymodVdummylib", representation: vector(SIMRT!-wrapper, SIMRT!%empty-list)); let poo-descriptor = make(, name: "d_poo_slotYdummymodVdummylib", representation: vector(SIMRT!-wrapper, poo-slot)); let pants-descriptor = make(, name: "d_pants_slotYdummymodVdummylib", representation: vector(SIMRT!-wrapper, pants-slot)); let ph-descriptors = make(, name: "dv_ph_classYdummymodVdummylib", representation: vector(SIMRT!-wrapper, I(2), poo-descriptor, pants-descriptor)); let ph-class = make(, name: "Lph_classGYdummymodVdummylib", representation: vector(SIMRT!-wrapper, ph-descriptors, SIMRT!%false)); let ph-wrapper = make(, name: "KLph_classGYdummymodVdummylibW", representation: vector(SIMRT!-wrapper, ph-class)); let ph1 = make(, name: "ph1YdummymodVdummylib", representation: vector(ph-wrapper, I(5), I(10))); let func = make(, name: "KfuncYdummymodVdummylib", arguments: #["x", "y", "z"], lexicals: #["pants_M1"], file: "dummy-source.pseudodylan", line: 15, known-locations: vector(pair(0, 0), pair(1, 1), pair(3, 4), pair(4, 7), pair(5, 10), pair(6, 14)), code-vector: vector($LINK, $LOCALASSIGN, -1, I(1), $LOCALASSIGN, -2, ph1, $LOCALASSIGN, -3, I(3), $LOCALASSIGN, -4, I(4), $NOP, $STOPCODE, $access-violation, $RET)); let second-thread = make(, name: "Ksecond_threadYdummymodVdummylib", arguments: #[], lexicals: #[], file: "dummy-source.pseudodylan", line: 32, known-locations: vector(pair(0, 0), pair(1, 1), pair(2, 3), pair(3, 5), pair(4, 10)), code-vector: vector($LINK, $CALL, func, $CALL, func, $CALL, func, $NOP, $NOP, $NOP, $END)); let recursive-function = make(, name: "Krecursive_functionYdummymodVdummylib", arguments: #[], lexicals: #["thingy_M1"], file: "dummy-source.pseudodylan", line: 27, known-locations: vector(pair(0, 0), pair(1, 1), pair(2, 8), pair(3, 10)), code-vector: vector($LINK, $LOCALASSIGN, -1, ph1, $DECA, $JRELNZ, 1, $RET, $CALL, 0, // Needs fixup - position 9 in the vector $RET)); recursive-function.code-vector[9] := recursive-function; let kick-off-recursion = make(, name: "Kkick_off_recursionYdummymodVdummylib", arguments: #[], lexicals: #[], file: "dummy-source.pseudodylan", line: 23, known-locations: vector(pair(0, 0), pair(1, 3), pair(2, 5)), code-vector: vector($LINK, $LDA, 5, $CALL, recursive-function, $RET)); let main = make(, name: "KmainYdummymodVdummylib", arguments: #[], lexicals: #[], file: "dummy-source.pseudodylan", line: 38, known-locations: vector(pair(0, 0), pair(1, 4), pair(2, 6), pair(3, 10), pair(4, 12)), code-vector: vector($LINK, $LDA, 3, $PUSHA, $CALL, func, $SPAWN, second-thread, $POPA, $DECA, $JRELNZ, -9, $CALL, kick-off-recursion, $END)); // ***************************** FIXUPS ******************************* SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); SIMRT!.representation := vector(SIMRT!-wrapper, SIMRT!%empty-vector, SIMRT!%false); // ******************************************************************** // Splurt out a complete list of functions and objects to go into // the runtime. // All functions must precede all non-functions. // The first function in this vector is the entry point. vector(main, func, second-thread, kick-off-recursion, recursive-function, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!-wrapper, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!, SIMRT!%empty-list, SIMRT!%empty-vector, SIMRT!%true, SIMRT!%false, poo-slot, pants-slot, poo-descriptor, pants-descriptor, ph-descriptors, ph-class, ph-wrapper, ph1); end method;