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