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