https://github.com/akkartik/mu/blob/master/subx/069allocate.subx
  1 # Helper to dynamically allocate memory on the heap.
  2 #
  3 # We'd like to be able to write tests for functions that allocate memory,
  4 # making assertions on the precise addresses used. To achieve this we'll pass
  5 # in an *allocation descriptor* to allocate from.
  6 #
  7 # Allocation descriptors are also useful outside of tests. Assembly and machine
  8 # code are of necessity unsafe languages, and one of the most insidious kinds
  9 # of bugs unsafe languages expose us to are dangling pointers to memory that
 10 # has been freed and potentially even reused for something totally different.
 11 # To reduce the odds of such "use after free" errors, SubX programs tend to not
 12 # reclaim and reuse dynamically allocated memory. (Running out of memory is far
 13 # easier to debug.) Long-running programs that want to reuse memory are mostly
 14 # on their own to be careful. However, they do get one bit of help: they can
 15 # carve out chunks of memory and then allocate from them manually using this
 16 # very same 'allocate' helper. They just need a new allocation descriptor for
 17 # their book-keeping.
 18 
 19 == data
 20 
 21 # The 'global' allocation descriptor. Pass this into 'allocate' to claim a
 22 # hitherto unused bit of memory.
 23 Heap:
 24     Start-of-heap/imm32  # curr
 25     0x0b000000/imm32  # limit; keep sync'd with DATA_SEGMENT + SEGMENT_ALIGNMENT
 26 
 27 == code
 28 #   instruction                     effective address                                                   register    displacement    immediate
 29 # . op          subop               mod             rm32          base        index         scale       r32
 30 # . 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
 31 
 32 # Claim the next 'n' bytes of memory starting at ad->curr and update ad->curr.
 33 # If there isn't enough memory before ad->limit, return 0 and leave 'ad' unmodified.
 34 allocate:  # ad : (address allocation-descriptor), n : int -> address-or-null/EAX
 35     # . prolog
 36     55/push-EBP
 37     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
 38     # . save registers
 39     51/push-ECX
 40     52/push-EDX
 41     # ECX = ad
 42     8b/copy                         1/mod/*+disp8   5/rm32/EBP    .           .             .           1/r32/ECX   8/disp8         .                 # copy *(EBP+8) to ECX
 43     # save ad->curr
 44     8b/copy                         0/mod/indirect  1/rm32/ECX    .           .             .           0/r32/EAX   .               .                 # copy *ECX to EAX
 45     # check if there's enough space
 46     # . EDX = ad->curr + n
 47     89/copy                         3/mod/direct    2/rm32/EDX    .           .             .           0/r32/EAX   .               .                 # copy EAX to EDX
 48     03/add                          1/mod/*+disp8   5/rm32/EBP    .           .             .           2/r32/EDX   0xc/disp8       .                 # add *(EBP+12) to EDX
 49     3b/compare                      1/mod/*+disp8   1/rm32/ECX    .           .             .           2/r32/EDX   4/disp8         .                 # compare EDX with *(ECX+4)
 50     7c/jump-if-lesser  $allocate:commit/disp8
 51     # return null if not
 52     b8/copy-to-EAX  0/imm32
 53     eb/jump  $allocate:end/disp8
 54 $allocate:commit:
 55     # update ad->curr
 56     89/copy                         0/mod/indirect  1/rm32/ECX    .           .             .           2/r32/EDX   .               .                 # copy EDX to *ECX
 57 $allocate:end:
 58     # . restore registers
 59     5a/pop-to-EDX
 60     59/pop-to-ECX
 61     # . epilog
 62     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
 63     5d/pop-to-EBP
 64     c3/return
 65 
 66 test-allocate-success:
 67     # . prolog
 68     55/push-EBP
 69     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
 70     # var ad/ECX : (address allocation-descriptor) = {11, 15}
 71     68/push  0xf/imm32/limit
 72     68/push  0xb/imm32/curr
 73     89/copy                         3/mod/direct    1/rm32/ECX    .           .             .           4/r32/ESP   .               .                 # copy ESP to ECX
 74     # EAX = allocate(ad, 3)
 75     # . . push args
 76     68/push  3/imm32
 77     51/push-ECX
 78     # . . call
 79     e8/call  allocate/disp32
 80     # . . discard args
 81     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add to ESP
 82     # check-ints-equal(EAX, 11, msg)
 83     # . . push args
 84     68/push  "F - test-allocate-success: returns current pointer of allocation descriptor"/imm32
 85     68/push  0xb/imm32
 86     50/push-EAX
 87     # . . call
 88     e8/call  check-ints-equal/disp32
 89     # . . discard args
 90     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
 91     # check-ints-equal(ad->curr, 14, msg)
 92     # . . push args
 93     68/push  "F - test-allocate-success: updates allocation descriptor"/imm32
 94     68/push  0xe/imm32
 95     ff          6/subop/push        0/mod/indirect  1/rm32/ECX    .           .             .           .           .               .                 # push *ECX
 96     # . . call
 97     e8/call  check-ints-equal/disp32
 98     # . . discard args
 99     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
100     # . epilog
101     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
102     5d/pop-to-EBP
103     c3/return
104 
105 test-allocate-failure:
106     # . prolog
107     55/push-EBP
108     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
109     # var ad/ECX : (address allocation-descriptor) = {11, 15}
110     68/push  0xf/imm32/limit
111     68/push  0xb/imm32/curr
112     89/copy                         3/mod/direct    1/rm32/ECX    .           .             .           4/r32/ESP   .               .                 # copy ESP to ECX
113     # EAX = allocate(ad, 6)
114     # . . push args
115     68/push  6/imm32
116     51/push-ECX
117     # . . call
118     e8/call  allocate/disp32
119     # . . discard args
120     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add to ESP
121     # check-ints-equal(EAX, 0, msg)
122     # . . push args
123     68/push  "F - test-allocate-failure: returns null"/imm32
124     68/push  0/imm32
125     50/push-EAX
126     # . . call
127     e8/call  check-ints-equal/disp32
128     # . . discard args
129     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
130     # no change to ad->curr
131     # . check-ints-equal(ad->curr, 11)
132     # . . push args
133     68/push  "F - test-allocate-failure: updates allocation descriptor"/imm32
134     68/push  0xb/imm32
135     ff          6/subop/push        0/mod/indirect  1/rm32/ECX    .           .             .           .           .               .                 # push *ECX
136     # . . call
137     e8/call  check-ints-equal/disp32
138     # . . discard args
139     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add to ESP
140     # . epilog
141     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
142     5d/pop-to-EBP
143     c3/return
144 
145 # helper: create a nested allocation descriptor (useful for tests)
146 allocate-region:  # ad : (address allocation-descriptor), n : int -> new-ad : (address allocation-descriptor)
147     # . prolog
148     55/push-EBP
149     89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
150     # . save registers
151     51/push-ECX
152     # EAX = allocate(ad, n)
153     # . . push args
154     ff          6/subop/push        1/mod/*+disp8   5/rm32/EBP    .           .             .           .           0xc/disp8       .                 # push *(EBP+12)
155     ff          6/subop/push        1/mod/*+disp8   5/rm32/EBP    .           .             .           .           8/disp8         .                 # push *(EBP+8)
156     # . . call
157     e8/call  allocate/disp32
158     # . . discard args
159     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add to ESP
160     # if (EAX == 0) abort
161     81          7/subop/compare     3/mod/direct    0/rm32/EAX    .           .             .           .           .               0/imm32           # compare EAX
162     74/jump-if-equal  $allocate-region:abort/disp8
163     # earmark 8 bytes at the start for a new allocation descriptor
164     # . *EAX = EAX + 8
165     89/copy                         3/mod/direct    1/rm32/ECX    .           .             .           0/r32/EAX   .               .                 # copy EAX to ECX
166     81          0/subop/add         3/mod/direct    1/rm32/ECX    .           .             .           .           .               8/imm32           # add to ECX
167     89/copy                         0/mod/indirect  0/rm32/EAX    .           .             .           1/r32/ECX   .               .                 # copy ECX to *EAX
168     # . *(EAX+4) = EAX + n
169     89/copy                         3/mod/direct    1/rm32/ECX    .           .             .           0/r32/EAX   .               .                 # copy EAX to ECX
170     03/add                          1/mod/*+disp8   5/rm32/EBP    .           .             .           1/r32/ECX   0xc/disp8       .                 # add *(EBP+12) to ECX
171     89/copy                         1/mod/*+disp8   0/rm32/EAX    .           .             .           1/r32/ECX   4/disp8         .                 # copy ECX to *(EAX+4)
172     # . restore registers
173     59/pop-to-ECX
174     # . epilog
175     89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
176     5d/pop-to-EBP
177     c3/return
178 
179 # We could create a more general '$abort' jump target, but then we'd need to do
180 # a conditional jump followed by loading the error message and an unconditional
181 # jump. Or we'd need to unconditionally load the error message before a
182 # conditional jump, even if it's unused the vast majority of the time. This way
183 # we bloat a potentially cold segment in RAM so we can abort with a single
184 # instruction.
185 $allocate-region:abort:
186     # . _write(2/stderr, error)
187     # . . push args
188     68/push  "allocate-region: failed to allocate"/imm32
189     68/push  2/imm32/stderr
190     # . . call
191     e8/call  _write/disp32
192     # . . discard args
193     81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add to ESP
194     # . syscall(exit, 1)
195     bb/copy-to-EBX  1/imm32
196     b8/copy-to-EAX  1/imm32/exit
197     cd/syscall  0x80/imm8
198     # never gets here
199 
200 # . . vim:nowrap:textwidth=0