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 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 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