From 395b3ffbebb4656fdc5096887bc1ca7df5180da3 Mon Sep 17 00:00:00 2001 From: Kartik Agaram Date: Sun, 30 Dec 2018 01:30:56 -0800 Subject: 4894 Done with kinda-safe pointers. In a real compiler the fast path of 'lookup' would ideally get inlined. Excluding procedure-call overhead, the current implementation consumes 2 registers besides the input, and requires 9 instructions (2 push, 2 load, compare, jump, increment, 2 pop). That's large enough that inlining may become a trade-off. Even if we somehow magically had the registers already loaded and available, we'd still need 4 instructions (1 pointer dereference, compare, jump and increment). The price of safety. --- subx/apps/handle | Bin 7639 -> 7954 bytes subx/apps/handle.subx | 160 ++++++++++++++++++++++++++++++++++++++++++++++++++ subx/test_apps | 10 ++++ 3 files changed, 170 insertions(+) (limited to 'subx') diff --git a/subx/apps/handle b/subx/apps/handle index ea73b522..1e2c0e28 100644 Binary files a/subx/apps/handle and b/subx/apps/handle differ diff --git a/subx/apps/handle.subx b/subx/apps/handle.subx index eda89945..406794a6 100644 --- a/subx/apps/handle.subx +++ b/subx/apps/handle.subx @@ -11,6 +11,12 @@ # Layout of a handle: # offset 0: alloc id # offset 4: address +# +# To run (from the subx directory): +# $ ./subx translate *.subx apps/handle.subx -o apps/handle +# $ ./subx run apps/handle +# Expected result is a hard abort: +# ........lookup failed == code # instruction effective address register displacement immediate @@ -202,6 +208,160 @@ test-new-failure: 5d/pop-to-EBP c3/return +lookup: # h : (handle T) -> EAX : (address T) + # . prolog + 55/push-EBP + 89/copy 3/mod/direct 5/rm32/EBP . . . 4/r32/ESP . . # copy ESP to EBP + # . save registers + 51/push-ECX + 52/push-EDX + # ECX = handle + 8b/copy 1/mod/*+disp8 5/rm32/EBP . . . 1/r32/ECX 8/disp8 . # copy *(EBP+8) to ECX + # EDX = handle->alloc_id + 8b/copy 0/mod/indirect 1/rm32/ECX . . . 2/r32/EDX . . # copy *ECX to EDX + # EAX = handle->address + 8b/copy 1/mod/*+disp8 1/rm32/ECX . . . 0/r32/EAX 4/disp8 . # copy *(ECX+4) to EAX + # if (*EAX == EDX) return + 39/compare 0/mod/indirect 0/rm32/EAX . . . 2/r32/EDX . . # compare *EAX and EDX + 74/jump-if-equal $lookup:success/disp8 + # otherwise print a message and exit + # hard-coded abort just to minimize args and simplify calls + # TODO: emit stack trace, etc. + # . _write(2/stderr, msg) + # . . push args + 68/push "lookup failed"/imm32 + 68/push 2/imm32/stderr + # . . call + e8/call _write/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 8/imm32 # add to ESP + # . syscall(exit, 1) + bb/copy-to-EBX 1/imm32/exit-status + b8/copy-to-EAX 1/imm32/exit + cd/syscall 0x80/imm8 +$lookup:success: + # increment past payload alloc id + 05/add-to-EAX 4/imm32 + # . restore registers + 5a/pop-to-EDX + 59/pop-to-ECX + # . epilog + 89/copy 3/mod/direct 4/rm32/ESP . . . 5/r32/EBP . . # copy EBP to ESP + 5d/pop-to-EBP + c3/return + +test-lookup-success: + # . prolog + 55/push-EBP + 89/copy 3/mod/direct 5/rm32/EBP . . . 4/r32/ESP . . # copy ESP to EBP + # . save registers + # var handle/ECX = {0, 0} + 68/push 0/imm32/address + 68/push 0/imm32/alloc-id + 89/copy 3/mod/direct 1/rm32/ECX . . . 4/r32/ESP . . # copy ESP to ECX + # var ad/EAX : (address allocation-descriptor) = {0x0b000000, 0x0b000010} + 68/push 0x0b000010/imm32/limit + 68/push 0x0b000000/imm32/curr + 89/copy 3/mod/direct 0/rm32/EAX . . . 4/r32/ESP . . # copy ESP to EAX + # new(ad, 2, handle) + # . . push args + 51/push-ECX + 68/push 2/imm32/size + 50/push-EAX + # . . call + e8/call new/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP + # EAX = lookup(handle) + # . . push args + 51/push-ECX + # . . call + e8/call lookup/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 4/imm32 # add to ESP + # EAX contains old ad->address, after skipping the alloc id in the payload + # . check-ints-equal(EAX, 0x0b000004, msg) + # . . push args + 68/push "F - test-lookup-success"/imm32 + 68/push 0x0b000004/imm32 + 50/push-EAX + # . . call + e8/call check-ints-equal/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP + # clean up + # . *Next-alloc-id = 1 + c7 0/subop/copy 0/mod/direct 0/rm32/EAX . . . . . 1/imm32 # copy to *EAX + # . restore registers + 5a/pop-to-EDX + 59/pop-to-ECX + # . epilog + 89/copy 3/mod/direct 4/rm32/ESP . . . 5/r32/EBP . . # copy EBP to ESP + 5d/pop-to-EBP + c3/return + +test-lookup-failure: + # . prolog + 55/push-EBP + 89/copy 3/mod/direct 5/rm32/EBP . . . 4/r32/ESP . . # copy ESP to EBP + # . save registers + 50/push-EAX + 51/push-ECX + 52/push-EDX + # var h1/ECX = {0, 0} + 68/push 0/imm32/address + 68/push 0/imm32/alloc-id + 89/copy 3/mod/direct 1/rm32/ECX . . . 4/r32/ESP . . # copy ESP to ECX + # var ad/EAX : (address allocation-descriptor) = {0x0b000000, 0x0b000010} + 68/push 0x0b000010/imm32/limit + 68/push 0x0b000000/imm32/curr + 89/copy 3/mod/direct 0/rm32/EAX . . . 4/r32/ESP . . # copy ESP to EAX + # first allocation, to h1 + # . new(ad, 2, h1) + # . . push args + 51/push-ECX + 68/push 2/imm32/size + 50/push-EAX + # . . call + e8/call new/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP + # reset ad->curr to mimic reclamation + c7 0/subop/copy 0/mod/indirect 0/rm32/EAX . . . . . 0x0b000000/imm32 # copy to *EAX + # second allocation that returns the same address as the first + # var h2/EDX = {0, 0} + 68/push 0/imm32/address + 68/push 0/imm32/alloc-id + 89/copy 3/mod/direct 2/rm32/EDX . . . 4/r32/ESP . . # copy ESP to EDX + # . new(ad, 2, h2) + # . . push args + 52/push-EDX + 68/push 2/imm32/size + 50/push-EAX + # . . call + e8/call new/disp32 + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 0xc/imm32 # add to ESP + # lookup(h1) should crash + # . . push args + 51/push-ECX + # . . call + e8/call lookup/disp32 + # should never get past this point + # . . discard args + 81 0/subop/add 3/mod/direct 4/rm32/ESP . . . . . 4/imm32 # add to ESP + # clean up + # . *Next-alloc-id = 1 + c7 0/subop/copy 0/mod/direct 0/rm32/EAX . . . . . 1/imm32 # copy to *EAX + # . restore registers + 5a/pop-to-EDX + 59/pop-to-ECX + 58/pop-to-EAX + # . epilog + 89/copy 3/mod/direct 4/rm32/ESP . . . 5/r32/EBP . . # copy EBP to ESP + 5d/pop-to-EBP + c3/return + == data # Monotonically increasing counter for calls to 'new' diff --git a/subx/test_apps b/subx/test_apps index 4de0ce06..62df1fe4 100755 --- a/subx/test_apps +++ b/subx/test_apps @@ -126,6 +126,16 @@ CFLAGS=-g ./subx translate examples/ex12.subx -o examples/ex12 CFLAGS=-g ./subx run examples/ex12 # final byte of mmap'd address is well-nigh guaranteed to be 0 test `uname` = 'Linux' && examples/ex12 +echo handle +CFLAGS=-g ./subx translate *.subx apps/handle.subx -o apps/handle +[ "$1" != record ] && git diff --quiet apps/handle +CFLAGS=-g ./subx run apps/handle 2>&1 |grep -q 'lookup failed' +echo +test `uname` = 'Linux' && { + apps/handle test 2>&1 |grep -q 'lookup failed' + echo +} + echo factorial CFLAGS=-g ./subx translate *.subx apps/factorial.subx -o apps/factorial [ "$1" != record ] && git diff --quiet apps/factorial -- cgit 1.4.1-2-gfad0