https://github.com/akkartik/mu/blob/master/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 # A default allocation descriptor for programs to use.
 22 Heap:  # allocation-descriptor
 23   # curr
 24   0/imm32
 25   # limit
 26   0/imm32
 27 
 28 # a reasonable default
 29 Heap-size:  # int
 30   0x400000/imm32/4MB
 31 
 32 == code
 33 #   instruction                     effective address                                                   register    displacement    immediate
 34 # . op          subop               mod             rm32          base        index         scale       r32
 35 # . 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
 36 
 37 # Let's start initializing the default allocation descriptor.
 38 
 39 Entry:
 40     # initialize heap
 41     # . Heap = new-segment(Heap-size)
 42     # . . push args
 43     68/push  Heap/imm32
 44     ff          6/subop/push        0/mod/indirect  5/rm32/.disp32            .             .           .           Heap-size/disp32                  # push *Heap-size
 45     # . . call
 46     e8/call  new-segment/disp32
 47     # . . discard args
 48     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               8/imm32           # add to esp
 49 
 50     e8/call  run-tests/disp32  # 'run-tests' is a function created automatically by SubX. It calls all functions that start with 'test-'.
 51 $array-equal-main:end:
 52     # syscall(exit, Num-test-failures)
 53     8b/copy                         0/mod/indirect  5/rm32/.disp32            .             .           3/r32/ebx   Num-test-failures/disp32          # copy *Num-test-failures to ebx
 54     b8/copy-to-eax  1/imm32/exit
 55     cd/syscall  0x80/imm8
 56 
 57 # Claim the next 'n' bytes of memory starting at ad->curr and update ad->curr.
 58 # Abort if there isn't enough memory in 'ad'.
 59 allocate:  # ad: (addr allocation-descriptor), n: int -> address-or-null/eax: (addr _)
 60     # . prologue
 61     55/push-ebp
 62     89/copy                         3/mod/direct    5/rm32/ebp    .           .             .           4/r32/esp   .               .                 # copy esp to ebp
 63     # . save registers
 64     51/push-ecx
 65     52/push-edx
 66     # ecx = ad
 67     8b/copy                         1/mod/*+disp8   5/rm32/ebp    .           .             .           1/r32/ecx   8/disp8         .                 # copy *(ebp+8) to ecx
 68     # save ad->curr
 69     8b/copy                         0/mod/indirect  1/rm32/ecx    .           .             .           0/r32/eax   .               .                 # copy *ecx to eax
 70     # check if there's enough space
 71     # . edx = ad->curr + n
 72     89/copy                         3/mod/direct    2/rm32/edx    .           .             .           0/r32/eax   .               .                 # copy eax to edx
 73     03/add                          1/mod/*+disp8   5/rm32/ebp    .           .             .           2/r32/edx   0xc/disp8       .                 # add *(ebp+12) to edx
 74     3b/compare                      1/mod/*+disp8   1/rm32/ecx    .           .             .           2/r32/edx   4/disp8         .                 # compare edx with *(ecx+4)
 75     73/jump-if->=-signed  $allocate:abort/disp8
 76 $allocate:commit:
 77     # update ad->curr
 78     89/copy                         0/mod/indirect  1/rm32/ecx    .           .             .           2/r32/edx   .               .                 # copy edx to *ecx
 79 $allocate:end:
 80     # . restore registers
 81     5a/pop-to-edx
 82     59/pop-to-ecx
 83     # . epilogue
 84     89/copy                         3/mod/direct    4/rm32/esp    .           .             .           5/r32/ebp   .               .                 # copy ebp to esp
 85     5d/pop-to-ebp
 86     c3/return
 87 
 88 $allocate:abort:
 89     # . _write(2/stderr, error)
 90     # . . push args
 91     68/push  "allocate: failed to allocate\n"/imm32
 92     68/push  2/imm32/stderr
 93     # . . call
 94     e8/call  _write/disp32
 95     # . . discard args
 96     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               8/imm32           # add to esp
 97     # . syscall(exit, 1)
 98     bb/copy-to-ebx  1/imm32
 99     b8/copy-to-eax  1/imm32/exit
100     cd/syscall  0x80/imm8
101     # never gets here
102 
103 test-allocate-success:
104     # . prologue
105     55/push-ebp
106     89/copy                         3/mod/direct    5/rm32/ebp    .           .             .           4/r32/esp   .               .                 # copy esp to ebp
107     # var ad/ecx: allocation-descriptor = {11, 15}
108     68/push  0xf/imm32/limit
109     68/push  0xb/imm32/curr
110     89/copy                         3/mod/direct    1/rm32/ecx    .           .             .           4/r32/esp   .               .                 # copy esp to ecx
111     # var eax: (handle byte) = allocate(ad, 3)
112     # . . push args
113     68/push  3/imm32
114     51/push-ecx
115     # . . call
116     e8/call  allocate/disp32
117     # . . discard args
118     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               8/imm32           # add to esp
119     # check-ints-equal(eax, 11, msg)
120     # . . push args
121     68/push  "F - test-allocate-success: returns current pointer of allocation descriptor"/imm32
122     68/push  0xb/imm32
123     50/push-eax
124     # . . call
125     e8/call  check-ints-equal/disp32
126     # . . discard args
127     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               0xc/imm32         # add to esp
128     # check-ints-equal(ad->curr, 14, msg)
129     # . . push args
130     68/push  "F - test-allocate-success: updates allocation descriptor"/imm32
131     68/push  0xe/imm32
132     ff          6/subop/push        0/mod/indirect  1/rm32/ecx    .           .             .           .           .               .                 # push *ecx
133     # . . call
134     e8/call  check-ints-equal/disp32
135     # . . discard args
136     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               0xc/imm32         # add to esp
137     # . epilogue
138     89/copy                         3/mod/direct    4/rm32/esp    .           .             .           5/r32/ebp   .               .                 # copy ebp to esp
139     5d/pop-to-ebp
140     c3/return
141 
142 _pending-test-allocate-failure:
143     # . prologue
144     55/push-ebp
145     89/copy                         3/mod/direct    5/rm32/ebp    .           .             .           4/r32/esp   .               .                 # copy esp to ebp
146     # var ad/ecx: allocation-descriptor = {11, 15}
147     68/push  0xf/imm32/limit
148     68/push  0xb/imm32/curr
149     89/copy                         3/mod/direct    1/rm32/ecx    .           .             .           4/r32/esp   .               .                 # copy esp to ecx
150     # var eax: (handle byte) = allocate(ad, 6)
151     # . . push args
152     68/push  6/imm32
153     51/push-ecx
154     # . . call
155     e8/call  allocate/disp32
156     # . . discard args
157     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               8/imm32           # add to esp
158     # check-ints-equal(eax, 0, msg)
159     # . . push args
160     68/push  "F - test-allocate-failure: returns null"/imm32
161     68/push  0/imm32
162     50/push-eax
163     # . . call
164     e8/call  check-ints-equal/disp32
165     # . . discard args
166     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               0xc/imm32         # add to esp
167     # no change to ad->curr
168     # . check-ints-equal(ad->curr, 11)
169     # . . push args
170     68/push  "F - test-allocate-failure: updates allocation descriptor"/imm32
171     68/push  0xb/imm32
172     ff          6/subop/push        0/mod/indirect  1/rm32/ecx    .           .             .           .           .               .                 # push *ecx
173     # . . call
174     e8/call  check-ints-equal/disp32
175     # . . discard args
176     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               0xc/imm32         # add to esp
177     # . epilogue
178     89/copy                         3/mod/direct    4/rm32/esp    .           .             .           5/r32/ebp   .               .                 # copy ebp to esp
179     5d/pop-to-ebp
180     c3/return
181 
182 # helper: create a nested allocation descriptor (useful for tests)
183 allocate-region:  # ad: (addr allocation-descriptor), n: int -> new-ad: (handle allocation-descriptor)
184     # . prologue
185     55/push-ebp
186     89/copy                         3/mod/direct    5/rm32/ebp    .           .             .           4/r32/esp   .               .                 # copy esp to ebp
187     # . save registers
188     51/push-ecx
189     # eax = allocate(ad, n)
190     # . . push args
191     ff          6/subop/push        1/mod/*+disp8   5/rm32/ebp    .           .             .           .           0xc/disp8       .                 # push *(ebp+12)
192     ff          6/subop/push        1/mod/*+disp8   5/rm32/ebp    .           .             .           .           8/disp8         .                 # push *(ebp+8)
193     # . . call
194     e8/call  allocate/disp32
195     # . . discard args
196     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               8/imm32           # add to esp
197     # if (eax == 0) abort
198     3d/compare-eax-and  0/imm32
199     74/jump-if-=  $allocate-region:abort/disp8
200     # earmark 8 bytes at the start for a new allocation descriptor
201     # . *eax = eax + 8
202     89/copy                         3/mod/direct    1/rm32/ecx    .           .             .           0/r32/eax   .               .                 # copy eax to ecx
203     81          0/subop/add         3/mod/direct    1/rm32/ecx    .           .             .           .           .               8/imm32           # add to ecx
204     89/copy                         0/mod/indirect  0/rm32/eax    .           .             .           1/r32/ecx   .               .                 # copy ecx to *eax
205     # . *(eax+4) = eax + n
206     89/copy                         3/mod/direct    1/rm32/ecx    .           .             .           0/r32/eax   .               .                 # copy eax to ecx
207     03/add                          1/mod/*+disp8   5/rm32/ebp    .           .             .           1/r32/ecx   0xc/disp8       .                 # add *(ebp+12) to ecx
208     89/copy                         1/mod/*+disp8   0/rm32/eax    .           .             .           1/r32/ecx   4/disp8         .                 # copy ecx to *(eax+4)
209     # . restore registers
210     59/pop-to-ecx
211     # . epilogue
212     89/copy                         3/mod/direct    4/rm32/esp    .           .             .           5/r32/ebp   .               .                 # copy ebp to esp
213     5d/pop-to-ebp
214     c3/return
215 
216 # We could create a more general '$abort' jump target, but then we'd need to do
217 # a conditional jump followed by loading the error message and an unconditional
218 # jump. Or we'd need to unconditionally load the error message before a
219 # conditional jump, even if it's unused the vast majority of the time. This way
220 # we bloat a potentially cold segment in RAM so we can abort with a single
221 # instruction.
222 $allocate-region:abort:
223     # . _write(2/stderr, error)
224     # . . push args
225     68/push  "allocate-region: failed to allocate\n"/imm32
226     68/push  2/imm32/stderr
227     # . . call
228     e8/call  _write/disp32
229     # . . discard args
230     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               8/imm32           # add to esp
231     # . syscall(exit, 1)
232     bb/copy-to-ebx  1/imm32
233     b8/copy-to-eax  1/imm32/exit
234     cd/syscall  0x80/imm8
235     # never gets here
236 
237 # Claim the next 'n+4' bytes of memory and initialize the first 4 to n.
238 # Abort if there isn't enough memory in 'ad'.
239 allocate-array:  # ad: (addr allocation-descriptor), n: int -> result/eax: (addr _)
240     # . prologue
241     55/push-ebp
242     89/copy                         3/mod/direct    5/rm32/ebp    .           .             .           4/r32/esp   .               .                 # copy esp to ebp
243     # . save registers
244     51/push-ecx
245     52/push-edx
246     # ecx = n
247     8b/copy                         1/mod/*+disp8   5/rm32/ebp    .           .             .           1/r32/ecx   0xc/disp8       .                 # copy *(ebp+12) to ecx
248     # var size/edx: int = n+4
249     8d/copy-address                 1/mod/*+disp8   1/rm32/ecx    .           .             .           2/r32/edx   4/disp8         .                 # copy ecx+4 to edx
250     # result = allocate(ad, size)
251     # . . push args
252     52/push-edx
253     ff          6/subop/push        1/mod/*+disp8   5/rm32/ebp    .           .             .           .           8/disp8         .                 # push *(ebp+8)
254     # . . call
255     e8/call  allocate/disp32
256     # . . discard args
257     81          0/subop/add         3/mod/direct    4/rm32/esp    .           .             .           .           .               8/imm32           # add to esp
258     # *result = n
259     89/copy                         0/mod/indirect  0/rm32/eax    .           .             .           1/r32/ecx   .               .                 # copy ecx to *eax
260 $allocate-array:end:
261     # . restore registers
262     5a/pop-to-edx
263     59/pop-to-ecx
264     # . epilogue
265     89/copy                         3/mod/direct    4/rm32/esp    .           .             .           5/r32/ebp   .               .                 # copy ebp to esp
266     5d/pop-to-ebp
267     c3/return
268 
269 # . . vim:nowrap:textwidth=0