1 # A sketch of Mu-style handles or kinda-safe pointers, that add a modicum of
  2 # checking to dynamically allocated memory.
  3 #
  4 # This approach avoids using 'allocate' directly in favor of two primitives:
  5 #   - 'new', which allocates some space (the 'payload'), stores the address
  6 #     along with an opaque 'alloc id' in a 'handle', and prepends the same
  7 #     alloc id to the payload.
  8 #   - 'lookup', which checks that the alloc id at the start of a handle matches
  9 #     the alloc id at the start of the payload before returning the address.
 10 #
 11 # Layout of a handle:
 12 #   offset 0: alloc id
 13 #   offset 4: address
 14 #
 15 # To run (from the subx directory):
 16 #   $ ./subx translate *.subx apps/handle.subx -o apps/handle
 17 #   $ ./subx run apps/handle
 18 # Expected result is a hard abort:
 19 #   ........lookup failed
 20 # (This file is a prototype, so the tests in this file aren't real tests. Don't
 21 # expect to run anything in the same process after they've completed.)
 22 
 23 == code
 24 #   instruction                     effective address                                                   register    displacement    immediate
 25 # . op          subop               mod             rm32          base        index         scale       r32
 26 # . 1-3 bytes   3 bits              2 bits          3 bits        3 bits      3 bits        2 bits      2 bits      0/1/2/4 bytes   0/1/2/4 bytes
 27 
 28 # main:
 29     e8/call  run-tests/disp32  # 'run-tests' is a function created automatically by SubX. It calls all functions that start with 'test-'.
 30     # syscall(exit, Num-test-failures)
 31     8b/copy                         0/mod/indirect  5/rm32/.disp32            .             .           3/r32/EBX   Num-test-failures/disp32          # copy *Num-test-failures to EBX
 32     b8/copy-to-EAX  1/imm32/exit
 33     cd/syscall  0x80/imm8
 34 
 35 new:  # ad : (address allocation-descriptor), n : int, out : (address handle)
 36     # . prolog
 37     55/push-EBP
 38     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
 39     # . save registers
 40     50/push-EAX
 41     51/push-ECX
 42     52/push-EDX
 43     # ECX = n+4
 44     8b/copy                         1/mod/*+disp8   5/rm32/EBP    .           .             .           1/r32/ECX   0xc/disp8       .                 # copy *(EBP+12) to ECX
 45     81          0/subop/add         3/mod/direct    1/rm32/ECX    .           .             .           .           .               4/imm32           # add to ECX
 46     # EAX = allocate(ad, ECX)
 47     # . . push args
 48     51/push-ECX
 49     ff          6/subop/push        1/mod/*+disp8   5/rm32/EBP    .           .             .           .           8/disp8         .                 # push *(EBP+8)
 50     # . . call
 51     e8/call  allocate/disp32
 52     # . . discard args
 53     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add to ESP
 54     # EDX = out
 55     8b/copy                         1/mod/*+disp8   5/rm32/EBP    .           .             .           2/r32/EDX   0x10/disp8      .                 # copy *(EBP+16) to EDX
 56     # out->address = EAX
 57     89/copy                         1/mod/*+disp8   2/rm32/EDX    .           .             .           0/r32/EAX   4/disp8         .                 # copy EAX to *(EDX+4)
 58     # if (EAX == 0) out->alloc_id = 0, return
 59     81          7/subop/compare     3/mod/direct    0/rm32/EAX    .           .             .           .           .               0/imm32           # compare EAX
 60     75/jump-if-not-equal  $new:continue/disp8
 61     c7          0/subop/copy        0/mod/indirect  2/rm32/EDX    .           .             .           .           .               0/imm32           # copy to *EDX
 62     eb/jump  $new:end/disp8
 63 $new:continue:
 64     # otherwise:
 65     # ECX = *Next-alloc-id
 66     8b/copy                         0/mod/indirect  5/rm32/.disp32            .             .           1/r32/ECX   Next-alloc-id/disp32              # copy *Next-alloc-id to ECX
 67     # *EAX = *Next-alloc-id/ECX
 68     89/copy                         0/mod/indirect  0/rm32/EAX    .           .             .           1/r32/ECX   .               .                 # copy ECX to *EAX
 69     # out->alloc_id = *Next-alloc-id
 70     89/copy                         0/mod/indirect  2/rm32/EDX    .           .             .           1/r32/ECX   .               .                 # copy ECX to *EDX
 71     # increment *Next-alloc-id
 72     ff          0/subop/increment   0/mod/indirect  5/rm32/.disp32            .             .           .           Next-alloc-id/disp32              # increment *Next-alloc-id
 73 $new:end:
 74     # . restore registers
 75     5a/pop-to-EDX
 76     59/pop-to-ECX
 77     58/pop-to-EAX
 78     # . epilog
 79     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
 80     5d/pop-to-EBP
 81     c3/return
 82 
 83 test-new:
 84     # . prolog
 85     55/push-EBP
 86     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
 87     # *Next-alloc-id = 0x34
 88     c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .     Next-alloc-id/disp32  0x34/imm32        # copy to *Next-alloc-id
 89     # var handle/ECX = {0, 0}
 90     68/push  0/imm32/address
 91     68/push  0/imm32/alloc-id
 92     89/copy                         3/mod/direct    1/rm32/ECX    .           .             .           4/r32/ESP   .               .                 # copy ESP to ECX
 93     # new(Heap, 2, handle/ECX)
 94     # . . push args
 95     51/push-ECX
 96     68/push  2/imm32/size
 97     68/push  Heap/imm32
 98     # . . call
 99     e8/call  new/disp32
100     # . . discard args
101     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
102     # check-ints-equal(handle->alloc_id, 0x34, msg)
103     # . . push args
104     68/push  "F - test-new: alloc id of handle"/imm32
105     68/push  0x34/imm32
106     ff          6/subop/push        0/mod/indirect  1/rm32/ECX    .           .             .           .           .               .                 # push *ECX
107     # . . call
108     e8/call  check-ints-equal/disp32
109     # . . discard args
110     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
111     # check-ints-equal(*handle->address, 0x34, msg)
112     # . . push args
113     68/push  "F - test-new: alloc id of payload"/imm32
114     68/push  0x34/imm32
115     8b/copy                         1/mod/*+disp8   1/rm32/ECX    .           .             .           2/r32/EDX   4/disp8         .                 # copy *(ECX+4) to EDX
116     ff          6/subop/push        0/mod/indirect  2/rm32/EDX    .           .             .           .           .               .                 # push *EDX
117     # . . call
118     e8/call  check-ints-equal/disp32
119     # . . discard args
120     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
121     # check-ints-equal(*Next-alloc-id, 0x35)
122     # . . push args
123     68/push  "F - test-new: next alloc id"/imm32
124     68/push  0x35/imm32
125     ff          6/subop/push        0/mod/indirect  5/rm32/.disp32            .             .           .           Next-alloc-id/disp32              # copy to *Next-alloc-id
126     # . . call
127     e8/call  check-ints-equal/disp32
128     # . . discard args
129     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
130     # clean up
131     # . *Next-alloc-id = 1
132     c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .     Next-alloc-id/disp32  1/imm32           # copy to *Next-alloc-id
133     # . epilog
134     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
135     5d/pop-to-EBP
136     c3/return
137 
138 test-new-failure:
139     # . prolog
140     55/push-EBP
141     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
142     # . *Next-alloc-id = 0x34
143     c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .           Next-alloc-id/disp32  0x34/imm32  # copy to *Next-alloc-id
144     # define an allocation-descriptor with no space left
145     # . var ad/EAX : (address allocation-descriptor) = {0x10, 0x10}
146     68/push  0x10/imm32/limit
147     68/push  0x10/imm32/curr
148     89/copy                         3/mod/direct    0/rm32/EAX    .           .             .           4/r32/ESP   .               .                 # copy ESP to EAX
149     # . var handle/ECX = {random, random}
150     68/push  1234/imm32/address
151     68/push  5678/imm32/alloc-id
152     89/copy                         3/mod/direct    1/rm32/ECX    .           .             .           4/r32/ESP   .               .                 # copy ESP to ECX
153     # try to allocate
154     # . new(ad, 2, handle/ECX)
155     # . . push args
156     51/push-ECX
157     68/push  2/imm32/size
158     50/push-EAX
159     # . . call
160     e8/call  new/disp32
161     # . . discard args
162     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
163     # handle should be cleared
164     # . check-ints-equal(handle->alloc_id, 0, msg)
165     # . . push args
166     68/push  "F - test-new-failure: alloc id of handle"/imm32
167     68/push  0/imm32
168     ff          6/subop/push        0/mod/indirect  1/rm32/ECX    .           .             .           .           .               .                 # push *ECX
169     # . . call
170     e8/call  check-ints-equal/disp32
171     # . . discard args
172     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
173     # . check-ints-equal(handle->address, 0, msg)
174     # . . push args
175     68/push  "F - test-new-failure: address of handle"/imm32
176     68/push  0/imm32
177     ff          6/subop/push        1/mod/*+disp8   1/rm32/ECX    .           .             .           .           4/disp8         .                 # push *(ECX+4)
178     # . . call
179     e8/call  check-ints-equal/disp32
180     # . . discard args
181     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
182     # Next-alloc-id should be unmodified
183     # . check-ints-equal(*Next-alloc-id, 0x34)
184     # . . push args
185     68/push  "F - test-new-failure: next alloc id"/imm32
186     68/push  0x34/imm32
187     ff          6/subop/push        0/mod/indirect  5/rm32/.disp32            .             .           .           Next-alloc-id/disp32              # copy to *Next-alloc-id
188     # . . call
189     e8/call  check-ints-equal/disp32
190     # . . discard args
191     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
192     # clean up
193     # . *Next-alloc-id = 1
194     c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .     Next-alloc-id/disp32  1/imm32           # copy to *Next-alloc-id
195     # . epilog
196     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
197     5d/pop-to-EBP
198     c3/return
199 
200 lookup:  # h : (handle T) -> EAX : (address T)
201     # . prolog
202     55/push-EBP
203     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
204     # - as a proof of concept for future inlining, uses no general-purpose registers besides the output (EAX)
205     # EAX = handle
206     8b/copy                         1/mod/*+disp8   5/rm32/EBP    .           .             .           0/r32/EAX   8/disp8         .                 # copy *(EBP+8) to EAX
207     # - inline {
208     # push handle->address
209     ff          6/subop/push        1/mod/*+disp8   1/rm32/ECX    .           .             .           .           4/disp8         .                 # push *(EAX+4)
210     # EAX = handle->alloc_id
211     8b/copy                         0/mod/indirect  0/rm32/EAX    .           .             .           .           .               .                 # copy *EAX to EAX
212     # if (EAX != *ESP) abort
213     39/compare                      0/mod/indirect  4/rm32/sib    4/base/ESP  4/index/none  .           0/r32/EAX   .               .                 # compare *ESP and EAX
214     75/jump-if-not-equal  $lookup:fail/disp8
215     # return ESP+4
216     58/pop-to-EAX
217     05/add-to-EAX  4/imm32
218     # - }
219     # . epilog
220     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
221     5d/pop-to-EBP
222     c3/return
223 $lookup:fail:
224     # . _write(2/stderr, msg)
225     # . . push args
226     68/push  "lookup failed"/imm32
227     68/push  2/imm32/stderr
228     # . . call
229     e8/call  _write/disp32
230     # . . discard args
231     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add to ESP
232     # . syscall(exit, 1)
233     bb/copy-to-EBX  1/imm32/exit-status
234     b8/copy-to-EAX  1/imm32/exit
235     cd/syscall  0x80/imm8
236 
237 test-lookup-success:
238     # . prolog
239     55/push-EBP
240     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
241     # . save registers
242     # var handle/ECX = {0, 0}
243     68/push  0/imm32/address
244     68/push  0/imm32/alloc-id
245     89/copy                         3/mod/direct    1/rm32/ECX    .           .             .           4/r32/ESP   .               .                 # copy ESP to ECX
246     # var old_top/EDX = Heap->curr
247     8b/copy                         0/mod/indirect  5/rm32/.disp32            .             .           2/r32/EDX   Heap/disp32     .                 # copy *Heap to EDX
248     # new(Heap, 2, handle)
249     # . . push args
250     51/push-ECX
251     68/push  2/imm32/size
252     68/push  Heap/imm32
253     # . . call
254     e8/call  new/disp32
255     # . . discard args
256     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
257     # EAX = lookup(handle)
258     # . . push args
259     51/push-ECX
260     # . . call
261     e8/call  lookup/disp32
262     # . . discard args
263     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add to ESP
264     # EAX contains old top of Heap, except skipping the alloc id in the payload
265     # . check-ints-equal(EAX, old_top+4, msg)
266     # . . push args
267     68/push  "F - test-lookup-success"/imm32
268     81          0/subop/add         3/mod/direct    2/rm32/EDX    .           .             .           .           .               4/imm32           # add to EDX
269     52/push-EDX
270     50/push-EAX
271     # . . call
272     e8/call  check-ints-equal/disp32
273     # . . discard args
274     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
275     # clean up
276     # . *Next-alloc-id = 1
277     c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .     Next-alloc-id/disp32  1/imm32           # copy to *Next-alloc-id
278     # . restore registers
279     5a/pop-to-EDX
280     59/pop-to-ECX
281     # . epilog
282     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
283     5d/pop-to-EBP
284     c3/return
285 
286 test-lookup-failure:
287     # . prolog
288     55/push-EBP
289     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
290     # . save registers
291     50/push-EAX
292     51/push-ECX
293     52/push-EDX
294     # var h1/ECX = {0, 0}
295     68/push  0/imm32/address
296     68/push  0/imm32/alloc-id
297     89/copy                         3/mod/direct    1/rm32/ECX    .           .             .           4/r32/ESP   .               .                 # copy ESP to ECX
298     # var old_top/EBX = Heap->curr
299     8b/copy                         0/mod/indirect  5/rm32/.disp32            .             .           3/r32/EBX   Heap/disp32     .                 # copy *Heap to EBX
300     # first allocation, to h1
301     # . new(Heap, 2, h1)
302     # . . push args
303     51/push-ECX
304     68/push  2/imm32/size
305     68/push  Heap/imm32
306     # . . call
307     e8/call  new/disp32
308     # . . discard args
309     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
310     # reset Heap->curr to mimic reclamation
311     89/copy                         0/mod/indirect  5/rm32/.disp32            .             .           3/r32/EBX   Heap/disp32     .                 # copy EBX to *Heap
312     # second allocation that returns the same address as the first
313     # var h2/EDX = {0, 0}
314     68/push  0/imm32/address
315     68/push  0/imm32/alloc-id
316     89/copy                         3/mod/direct    2/rm32/EDX    .           .             .           4/r32/ESP   .               .                 # copy ESP to EDX
317     # . new(Heap, 2, h2)
318     # . . push args
319     52/push-EDX
320     68/push  2/imm32/size
321     68/push  Heap/imm32
322     # . . call
323     e8/call  new/disp32
324     # . . discard args
325     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
326     # check-ints-equal(h1->address, h2->address, msg)
327     # . . push args
328     68/push  "F - test-lookup-failure"/imm32
329     ff          6/subop/push        1/mod/*+disp8   2/rm32/ECX    .           .             .           .           4/disp8         .                 # push *(EDX+4)
330     ff          6/subop/push        1/mod/*+disp8   1/rm32/ECX    .           .             .           .           4/disp8         .                 # push *(ECX+4)
331     # . . call
332     e8/call  check-ints-equal/disp32
333     # . . discard args
334     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
335     # lookup(h1) should crash
336     # . . push args
337     51/push-ECX
338     # . . call
339     e8/call  lookup/disp32
340     # should never get past this point
341     # . . discard args
342     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add to ESP
343     # clean up
344     # . *Next-alloc-id = 1
345     c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .     Next-alloc-id/disp32  1/imm32           # copy to *Next-alloc-id
346     # . restore registers
347     5a/pop-to-EDX
348     59/pop-to-ECX
349     58/pop-to-EAX
350     # . epilog
351     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
352     5d/pop-to-EBP
353     c3/return
354 
355 == data
356 
357 # Monotonically increasing counter for calls to 'new'
358 Next-alloc-id:
359     01 00 00 00  # 1
360 
361 # . . vim:nowrap:textwidth=0