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     # . epilog
235     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
236     5d/pop-to-EBP
237     c3/return
238 
239 $lookup:abort:
240     # . _write(2/stderr, msg)
241     # . . push args
242     68/push  "lookup failed\n"/imm32
243     68/push  2/imm32/stderr
244     # . . call
245     e8/call  _write/disp32
246     # . . discard args
247     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add to ESP
248     # . syscall(exit, 1)
249     bb/copy-to-EBX  1/imm32/exit-status
250     b8/copy-to-EAX  1/imm32/exit
251     cd/syscall  0x80/imm8
252 
253 test-lookup-success:
254     # . prolog
255     55/push-EBP
256     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
257     # . save registers
258     # var heap/EBX : (address allocation-descriptor) = {0, 0}
259     68/push  0/imm32/limit
260     68/push  0/imm32/curr
261     89/copy                         3/mod/direct    3/rm32/EBX    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBX
262     # heap = new-segment(512)
263     # . . push args
264     53/push-EBX
265     68/push  0x200/imm32
266     # . . call
267     e8/call  new-segment/disp32
268     # . . discard args
269     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add to ESP
270     # var handle/ECX = {0, 0}
271     68/push  0/imm32/address
272     68/push  0/imm32/alloc-id
273     89/copy                         3/mod/direct    1/rm32/ECX    .           .             .           4/r32/ESP   .               .                 # copy ESP to ECX
274     # var old_top/EDX = heap->curr
275     8b/copy                         0/mod/indirect  3/rm32/EBX    .           .             .           2/r32/EDX   .               .                 # copy *EBX to EDX
276     # new(heap, 2, handle)
277     # . . push args
278     51/push-ECX
279     68/push  2/imm32/size
280     53/push-EBX
281     # . . call
282     e8/call  new/disp32
283     # . . discard args
284     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
285     # EAX = lookup(handle)
286     # . . push args
287     51/push-ECX
288     # . . call
289     e8/call  lookup/disp32
290     # . . discard args
291     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add to ESP
292     # EAX contains old top of heap, except skipping the alloc id in the payload
293     # . check-ints-equal(EAX, old_top+4, msg)
294     # . . push args
295     68/push  "F - test-lookup-success"/imm32
296     81          0/subop/add         3/mod/direct    2/rm32/EDX    .           .             .           .           .               4/imm32           # add to EDX
297     52/push-EDX
298     50/push-EAX
299     # . . call
300     e8/call  check-ints-equal/disp32
301     # . . discard args
302     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
303     # clean up
304     # . *Next-alloc-id = 1
305     c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .     Next-alloc-id/disp32  1/imm32           # copy to *Next-alloc-id
306     # write(2/stderr, "lookup succeeded\n")
307     # . . push args
308     68/push  "lookup succeeded\n"/imm32
309     68/push  2/imm32/stderr
310     # . . call
311     e8/call  write/disp32
312     # . . discard args
313     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add to ESP
314     # . restore registers
315     5a/pop-to-EDX
316     59/pop-to-ECX
317     # . epilog
318     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
319     5d/pop-to-EBP
320     c3/return
321 
322 test-lookup-failure:
323     # . prolog
324     55/push-EBP
325     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
326     # var heap/ESI : (address allocation-descriptor) = {0, 0}
327     68/push  0/imm32/limit
328     68/push  0/imm32/curr
329     89/copy                         3/mod/direct    6/rm32/ESI    .           .             .           4/r32/ESP   .               .                 # copy ESP to ESI
330     # heap = new-segment(512)
331     # . . push args
332     56/push-ESI
333     68/push  0x200/imm32
334     # . . call
335     e8/call  new-segment/disp32
336     # . . discard args
337     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add to ESP
338     # var h1/ECX = {0, 0}
339     68/push  0/imm32/address
340     68/push  0/imm32/alloc-id
341     89/copy                         3/mod/direct    1/rm32/ECX    .           .             .           4/r32/ESP   .               .                 # copy ESP to ECX
342     # var old_top/EBX = heap->curr
343     8b/copy                         0/mod/indirect  6/rm32/ESI    .           .             .           3/r32/EBX   .               .                 # copy *ESI to EBX
344     # first allocation, to h1
345     # . new(heap, 2, h1)
346     # . . push args
347     51/push-ECX
348     68/push  2/imm32/size
349     56/push-ESI
350     # . . call
351     e8/call  new/disp32
352     # . . discard args
353     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
354     # reset heap->curr to mimic reclamation
355     89/copy                         0/mod/indirect  6/rm32/ESI    .           .             .           3/r32/EBX   .               .                 # copy EBX to *ESI
356     # second allocation that returns the same address as the first
357     # var h2/EDX = {0, 0}
358     68/push  0/imm32/address
359     68/push  0/imm32/alloc-id
360     89/copy                         3/mod/direct    2/rm32/EDX    .           .             .           4/r32/ESP   .               .                 # copy ESP to EDX
361     # . new(heap, 2, h2)
362     # . . push args
363     52/push-EDX
364     68/push  2/imm32/size
365     56/push-ESI
366     # . . call
367     e8/call  new/disp32
368     # . . discard args
369     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
370     # check-ints-equal(h1->address, h2->address, msg)
371     # . . push args
372     68/push  "F - test-lookup-failure"/imm32
373     ff          6/subop/push        1/mod/*+disp8   2/rm32/ECX    .           .             .           .           4/disp8         .                 # push *(EDX+4)
374     ff          6/subop/push        1/mod/*+disp8   1/rm32/ECX    .           .             .           .           4/disp8         .                 # push *(ECX+4)
375     # . . call
376     e8/call  check-ints-equal/disp32
377     # . . discard args
378     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
379     # lookup(h1) should crash
380     # . . push args
381     51/push-ECX
382     # . . call
383     e8/call  lookup/disp32
384     # should never get past this point
385     # . . discard args
386     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add to ESP
387     # clean up
388     # . *Next-alloc-id = 1
389     c7          0/subop/copy        0/mod/indirect  5/rm32/.disp32            .             .           .     Next-alloc-id/disp32  1/imm32           # copy to *Next-alloc-id
390     # . epilog
391     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
392     5d/pop-to-EBP
393     c3/return
394 
395 == data
396 
397 # Monotonically increasing counter for calls to 'new'
398 Next-alloc-id:
399     1/imm32
400 
401 # . . vim:nowrap:textwidth=0