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