-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathheap.c
481 lines (392 loc) · 13 KB
/
heap.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
//
// NanoVM, a tiny java VM for the Atmel AVR family
// Copyright (C) 2005 by Till Harbaum <[email protected]>
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
//
// This file contains the heap. It can be requested to
// create/delete objects on the heap and does some
// simple garbage collection.
//
// The heap is being used top-to-bottom allowing the
// virtual machines stack to grow inside the heap from bottom to
// top
//
#include "config.h"
#include <string.h>
#include <stdio.h>
#include "error.h"
#include "heap.h"
#include "stack.h"
#include "vm.h"
uint8_t heap[HEAPSIZE];
uint16_t heap_base = 0;
typedef struct {
heap_id_t id;
uint16_t len; // actually 15 bits for the len and 1 bit for the fieldref flag
} PACKED heap_t;
#define HEAP_ID_FREE 0
#define HEAP_LEN_MASK 0x7FFF
#define HEAP_FIELDREF_MASK 0x8000
#ifdef NVM_USE_HEAP_IDMAP
// A heap id map must not be larger than 256 elements meaning a limit of 2048
// heap elements. Each heap element consists of the header (heap_t) and the
// actual data which makes up at least 1 byte. Limiting the heap size to 10kB
// makes sure that are always heap ids available.
#if HEAPSIZE > 10240
#error The maximum heap size is 10kB when using a heap id map.
#endif
uint8_t heap_idmap[(HEAPSIZE/(sizeof(heap_t)+1))/8];
const uint8_t heap_idmap_mask[8] = {0x01, 0x02, 0x04, 0x08,
0x10, 0x20, 0x40, 0x80};
#endif
// return the real heap base (where memory can be "stolen"
// from
uint8_t *heap_get_base(void) {
return heap;
}
#ifdef NVM_USE_MEMCPY_UP
// a version of memcpy that can only copy overlapping chunks
// if the target address is higher
void heap_memcpy_up(uint8_t *dst, uint8_t *src, uint16_t len) {
dst += len; src += len;
while(len--) *--dst = *--src;
}
#endif
// make some sanity checks on the heap in order to detect
// heap corruption as early as possible
void heap_check(void) {
uint16_t current = heap_base;
heap_t *h = (heap_t*)&heap[current];
uint16_t len;
if(h->id != HEAP_ID_FREE) {
DEBUGF("heap_check(): start element not free element\n");
error(ERROR_HEAP_CORRUPTED);
}
// (no HEAP_LEN_MASK required for free chunk)
current += h->len + sizeof(heap_t);
while(current < sizeof(heap)) {
h = (heap_t*)&heap[current];
len = h->len & HEAP_LEN_MASK;
if(len > sizeof(heap)) {
DEBUGF("heap_check(): single chunk too big\n");
//heap_show();
error(ERROR_HEAP_ILLEGAL_CHUNK_SIZE);
}
if(len + sizeof(heap_t) > sizeof(heap) - current) {
DEBUGF("heap_check(): total size error\n");
//heap_show();
error(ERROR_HEAP_CORRUPTED);
}
current += len + sizeof(heap_t);
}
if(current != sizeof(heap)) {
DEBUGF("heap_check(): heap sum mismatch\n");
//heap_show();
error(ERROR_HEAP_CORRUPTED);
}
}
// search for chunk with id in heap and return chunk header
// address
heap_t *heap_search(heap_id_t id) {
uint16_t current = heap_base;
while(current < sizeof(heap)) {
heap_t *h = (heap_t*)&heap[current];
if(h->id == id) return h;
current += (h->len & HEAP_LEN_MASK) + sizeof(heap_t);
}
return NULL;
}
#ifdef NVM_USE_HEAP_IDMAP
void heap_init_ids(void) {
memset(heap_idmap, 0, sizeof(heap_idmap));
heap_idmap[0] = 0x01; // mark HEAP_ID_FREE
}
void heap_mark_id(heap_id_t id) {
DEBUGF(" heap_mark_id(id=0x%04x)\n", id);
heap_idmap[id/8] |= heap_idmap_mask[id%8];
}
uint8_t heap_id_marked(heap_id_t id) {
return heap_idmap[id/8] & heap_idmap_mask[id%8];
}
heap_id_t heap_new_id(void) {
uint8_t byte,bit;
for(byte=0;;byte++) {
if(heap_idmap[byte] != 0xFF)
for(bit=0;;bit++)
if(!(heap_idmap[byte] & heap_idmap_mask[bit])) {
heap_idmap[byte] |= heap_idmap_mask[bit];
return byte*8+bit;
}
// check failure here before incrementing
// to allow for id maps with 256 elements
if(byte == sizeof(heap_idmap)-1)
return 0;
}
}
// in some cases, references to heap objects may be inside
// other heap objects. this currently happens only when
// a class is instanciated and this class contains fields.
// the heap element created by the constructor is marked with
// the fieldref bit and it is searched for references during
// garbage collections
void heap_mark_child_ids(void) {
bool_t again;
do {
uint16_t current = heap_base;
again = FALSE;
DEBUGF("heap_mark_child_ids(): starting heap walk\n");
while(current < sizeof(heap)) {
heap_t *h = (heap_t*)&heap[current];
// check for elements with the fieldref flag
if(h->len & HEAP_FIELDREF_MASK && heap_id_marked(h->id)) {
uint8_t fields = (uint8_t)((h->len & HEAP_LEN_MASK) / sizeof(nvm_ref_t));
uint8_t i;
// check all fields in the heap element
DEBUGF("- checking id 0x%04x\n", h->id);
for(i=0;i<fields;i++) {
nvm_ref_t ref = ((nvm_ref_t*)(h+1))[i];
// mark heap element only if field actually references
// a heap element and that wasn't already marked before
if((ref & NVM_TYPE_MASK) == NVM_TYPE_HEAP &&
!heap_id_marked(ref & ~NVM_TYPE_MASK)) {
heap_mark_id(ref & ~NVM_TYPE_MASK);
// we could check here if any of the newly marked heap elements
// has the fieldref flag set but doing would require walking the
// heap for every single one (!) so it's cheaper to just do the
// walk here again as soon as we newly marked any heap elements
again = TRUE;
}
}
}
current += (h->len & HEAP_LEN_MASK) + sizeof(heap_t);
}
} while(again);
}
#else // NVM_USE_HEAP_IDMAP
heap_id_t heap_new_id(void) {
heap_id_t id;
for(id=1;id;id++)
if(heap_search(id) == NULL)
return id;
return 0;
}
// in some cases, references to heap objects may be inside
// other heap objects. this currently happens only when
// a class is instanciated and this class contains fields.
// the heap element created by the constructor is marked with
// the fieldref bit and it is searched for references during
// garbage collections
bool_t heap_fieldref(heap_id_t id) {
nvm_ref_t id16 = id | NVM_TYPE_HEAP;
uint16_t current = heap_base;
// walk through the entire heap
while(current < sizeof(heap)) {
heap_t *h = (heap_t*)&heap[current];
// check for entries with the fieldref flag
if(h->len & HEAP_FIELDREF_MASK) {
uint8_t entries = (uint8_t)((h->len & HEAP_LEN_MASK) / sizeof(nvm_ref_t));
uint8_t i;
// check all entries in the heap element for
// the reference we are searching for
for(i=0;i<entries;i++) {
if(((nvm_ref_t*)(h+1))[i] == id16)
return TRUE;
}
}
current += (h->len & HEAP_LEN_MASK) + sizeof(heap_t);
}
return FALSE;
}
#endif // NVM_USE_HEAP_IDMAP
bool_t heap_alloc_internal(heap_id_t id, bool_t fieldref, uint16_t size) {
uint16_t req = size + sizeof(heap_t); // total mem required
// search for free block
heap_t *h = (heap_t*)&heap[heap_base];
// (no HEAP_LEN_MASK required for free chunk)
if(h->len >= req) {
// reduce the size of the free chunk
// (no HEAP_LEN_MASK required for free chunk)
h->len -= req;
// and create the new chunk behind this one
// (no HEAP_LEN_MASK required for free chunk)
h = (heap_t*)&heap[heap_base + sizeof(heap_t) + h->len];
h->id = id;
h->len = fieldref ? size | HEAP_FIELDREF_MASK : size & HEAP_LEN_MASK;
// fill memory with zero
uint8_t *ptr = (void*)(h+1);
while(size--)
*ptr++ = 0;
return TRUE;
}
DEBUGF("heap_alloc_internal(%d): out of memory\n", size);
return FALSE;
}
heap_id_t heap_alloc(bool_t fieldref, uint16_t size) {
heap_id_t id = heap_new_id();
DEBUGF("heap_alloc(size=%d) -> id=0x%04x\n", size, id);
if(!id) error(ERROR_HEAP_OUT_OF_IDS);
if(!heap_alloc_internal(id, fieldref, size)) {
heap_garbage_collect();
// we need to reallocate heap id, gc. threw away the old one...
id = heap_new_id();
if(!id) error(ERROR_HEAP_OUT_OF_IDS);
if(!heap_alloc_internal(id, fieldref, size))
error(ERROR_HEAP_OUT_OF_MEMORY);
DEBUGF("heap_alloc(size=%d) -> id=0x%04x successfull after gc\n",
size, id);
}
return id;
}
void heap_realloc(heap_id_t id, uint16_t size) {
heap_t *h, *h_new;
DEBUGF("heap_realloc(id=0x%04x, size=%d)\n", id, size);
// check free mem and call garbage collection if required
h = (heap_t*)&heap[heap_base];
// (no HEAP_LEN_MASK required for free chunk)
if(h->len < size + sizeof(heap_t))
heap_garbage_collect();
// get info on old chunk
h = heap_search(id);
// allocate space for bigger one
if(!heap_alloc_internal(id, h->len & HEAP_FIELDREF_MASK ? TRUE : FALSE, size))
error(ERROR_HEAP_OUT_OF_MEMORY);
h_new = heap_search(id);
memcpy(h_new+1, h+1, h->len & HEAP_LEN_MASK);
// this chunk is not immediately available for new allocation
// but it will be removed by the garbage collection next time
h->id = HEAP_ID_FREE;
}
uint16_t heap_get_len(heap_id_t id) {
heap_t *h = heap_search(id);
if(!h) error(ERROR_HEAP_CHUNK_DOES_NOT_EXIST);
return h->len & HEAP_LEN_MASK;
}
void *heap_get_addr(heap_id_t id) {
heap_t *h = heap_search(id);
if(!h) error(ERROR_HEAP_CHUNK_DOES_NOT_EXIST);
return h+1;
}
void heap_init(void) {
heap_t *h;
DEBUGF("heap_init()\n");
// just one big free block
h = (heap_t*)&heap[0];
h->id = HEAP_ID_FREE;
// (no HEAP_LEN_MASK required for free chunk)
h->len = sizeof(heap) - sizeof(heap_t);
#ifdef NVM_USE_HEAP_IDMAP
heap_init_ids();
#endif
}
// walk through the heap, check for every object
// if it's still being used and remove it if not
void heap_garbage_collect(void) {
uint16_t current = heap_base;
heap_t *h;
// (no HEAP_LEN_MASK required for free chunk)
DEBUGF("heap_garbage_collect() free space before: %d\n", ((heap_t*)&heap[heap_base])->len);
#ifdef NVM_USE_HEAP_IDMAP
heap_init_ids();
stack_mark_heap_root_ids();
heap_mark_child_ids();
#endif
// set current to stack-top
// walk through the entire heap
while(current < sizeof(heap)) {
uint16_t len;
h = (heap_t*)&heap[current];
len = (h->len & HEAP_LEN_MASK) + sizeof(heap_t);
// found an entry
if(h->id != HEAP_ID_FREE) {
// check if it's still used
#ifdef NVM_USE_HEAP_IDMAP
if(!heap_id_marked(h->id)) {
#else
if((!stack_heap_id_in_use(h->id))&&(!heap_fieldref(h->id))) {
#endif
// it is not used, remove it
DEBUGF("HEAP: removing unused object with id 0x%04x (len %d)\n",
h->id, len);
// move everything before to the top
#ifdef NVM_USE_MEMCPY_UP
heap_memcpy_up(heap+heap_base+len, heap+heap_base, current-heap_base);
#else
memmove(heap+heap_base+len, heap+heap_base, current-heap_base);
#endif
// add freed mem to free chunk
h = (heap_t*)&heap[heap_base];
// (no HEAP_LEN_MASK required for free chunk)
h->len += len;
}
}
current += len;
}
if(current != sizeof(heap)) {
DEBUGF("heap_garbage_collect(): total size error\n");
error(ERROR_HEAP_CORRUPTED);
}
// (no HEAP_LEN_MASK required for free chunk)
DEBUGF("heap_garbage_collect() free space after: %d\n", ((heap_t*)&heap[heap_base])->len);
}
// "steal" some bytes from the bottom of the heap (where
// the free chunk is)
void heap_steal(uint16_t bytes) {
heap_t *h = (heap_t*)&heap[heap_base];
uint16_t len;
DEBUGF("HEAP: request to steal %d bytes\n", bytes);
if(h->id != HEAP_ID_FREE) {
DEBUGF("heap_steal(%d): start element not free element\n", bytes);
error(ERROR_HEAP_CORRUPTED);
}
// try to make space if necessary
// (no HEAP_LEN_MASK required for free chunk)
len = h->len;
if(len < bytes)
heap_garbage_collect();
// (no HEAP_LEN_MASK required for free chunk)
len = h->len;
if(len < bytes)
error(ERROR_HEAP_OUT_OF_STACK_MEMORY);
// finally steal ...
heap_base += bytes;
h = (heap_t*)&heap[heap_base];
h->id = HEAP_ID_FREE;
// (no HEAP_LEN_MASK required for free chunk)
h->len = len - bytes;
}
// someone wants us to give some bytes back :-)
void heap_unsteal(uint16_t bytes) {
heap_t *h = (heap_t*)&heap[heap_base];
uint16_t len;
if(h->id != HEAP_ID_FREE) {
DEBUGF("heap_unsteal(%d): start element not free element\n", bytes);
error(ERROR_HEAP_CORRUPTED);
}
DEBUGF("HEAP: request to unsteal %d bytes\n", bytes);
if(heap_base < bytes) {
DEBUGF("stack underrun by %d bytes\n", bytes - heap_base);
error(ERROR_HEAP_STACK_UNDERRUN);
}
// finally unsteal ...
// (no HEAP_LEN_MASK required for free chunk)
len = h->len;
heap_base -= bytes;
h = (heap_t*)&heap[heap_base];
h->id = HEAP_ID_FREE;
// (no HEAP_LEN_MASK required for free chunk)
h->len = len + bytes;
}