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