2 * Dynamic memory allocation.
3 * Copyright (c) 1998 New Generation Software (NGS) Oy
5 * Author: Markku Rossi <mtr@ngs.fi>
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Library General Public
11 * License as published by the Free Software Foundation; either
12 * version 2 of the License, or (at your option) any later version.
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Library General Public License for more details.
19 * You should have received a copy of the GNU Library General Public
20 * License along with this library; if not, write to the Free
21 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
26 * $Source: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/kjs/src/heap.c,v $
33 * Types and definitions.
37 #define BLOCK_SIZE (63 * 1024)
39 #define BLOCK_SIZE (100 * 1024)
43 * The size of the minimum block that can be allocated from the heap.
44 * The block must be big enought to hold one pointer that is used when
45 * then block is entered to the freelist.
47 #define MIN_ALLOC (sizeof (void *))
50 #define MAGIC 0xfe109abe
54 * Prototypes for static functions.
57 static inline unsigned int
58 list (unsigned int size
)
60 unsigned int list
= 0;
68 if (list
>= JS_NUM_HEAP_FREELISTS
)
69 list
= JS_NUM_HEAP_FREELISTS
- 1;
76 delete_destroyable (JSHeapMemoryBlock
*b
)
78 JSHeapDestroyable
*destroyable
79 = (JSHeapDestroyable
*) ((unsigned char *) b
80 + sizeof (JSHeapMemoryBlock
));
82 if (destroyable
->destroy
)
83 (*destroyable
->destroy
) (destroyable
);
88 sweep (JSVirtualMachine
*vm
)
91 unsigned long bytes_in_use
= 0;
93 unsigned int freelist
;
95 for (i
= 0; i
< JS_NUM_HEAP_FREELISTS
; i
++)
96 vm
->heap_freelists
[i
] = NULL
;
98 vm
->gc
.bytes_free
= 0;
99 vm
->gc
.bytes_allocated
= 0;
101 for (hb
= vm
->heap
; hb
; hb
= hb
->next
)
103 JSHeapMemoryBlock
*b
, *e
, *bnext
;
105 b
= (JSHeapMemoryBlock
*) ((unsigned char *) hb
+ sizeof (JSHeapBlock
));
106 e
= (JSHeapMemoryBlock
*) ((unsigned char *) hb
+ sizeof (JSHeapBlock
)
108 for (; b
< e
; b
= bnext
)
111 assert (b
->magic
== MAGIC
);
113 bnext
= (JSHeapMemoryBlock
*) ((unsigned char *) b
114 + sizeof (JSHeapMemoryBlock
)
119 bytes_in_use
+= b
->size
;
121 vm
->gc
.bytes_allocated
= b
->size
;
125 if (b
->flag_destroyable
)
126 delete_destroyable (b
);
128 /* Pack consecutive free blocks to one big block. */
129 while (bnext
< e
&& bnext
->flag_mark
== 0)
132 assert (bnext
->magic
== MAGIC
);
134 if (bnext
->flag_destroyable
)
135 delete_destroyable (bnext
);
137 b
->size
+= bnext
->size
+ sizeof (JSHeapMemoryBlock
);
138 bnext
= (JSHeapMemoryBlock
*) ((unsigned char *) bnext
139 + sizeof (JSHeapMemoryBlock
)
143 JS_HEAP_MEMORY_BLOCK_CLEAR_FLAGS (b
);
145 /* Link it to the freelist. */
146 freelist
= list (b
->size
);
148 ((JSHeapFreelistBlock
*) b
)->next
= vm
->heap_freelists
[freelist
];
149 vm
->heap_freelists
[freelist
] = b
;
150 vm
->gc
.bytes_free
+= b
->size
;
164 js_vm_alloc (JSVirtualMachine
*vm
, unsigned int size
)
166 JSHeapMemoryBlock
*b
, *prev
;
167 unsigned int alloc_size
;
169 unsigned int to_alloc
;
170 unsigned int freelist
;
173 /* Round it up to the next pow of two. */
174 for (alloc_size
= MIN_ALLOC
; alloc_size
< size
; alloc_size
*= 2)
179 /* Take first block from the freelist that is big enough for us. */
180 for (freelist
= list (alloc_size
); freelist
< JS_NUM_HEAP_FREELISTS
;
182 for (prev
= NULL
, b
= vm
->heap_freelists
[freelist
]; b
;
183 prev
= b
, b
= ((JSHeapFreelistBlock
*) b
)->next
)
184 if (b
->size
>= alloc_size
)
186 /* Ok, take this one. */
188 ((JSHeapFreelistBlock
*) prev
)->next
189 = ((JSHeapFreelistBlock
*) b
)->next
;
191 vm
->heap_freelists
[freelist
] = ((JSHeapFreelistBlock
*) b
)->next
;
193 if (b
->size
> alloc_size
+ sizeof (JSHeapMemoryBlock
) + MIN_ALLOC
)
195 JSHeapMemoryBlock
*nb
;
197 /* We can split it. */
198 nb
= ((JSHeapMemoryBlock
*)
200 + sizeof (JSHeapMemoryBlock
) + alloc_size
));
205 JS_HEAP_MEMORY_BLOCK_CLEAR_FLAGS (nb
);
206 nb
->size
= b
->size
- sizeof (JSHeapMemoryBlock
) - alloc_size
;
208 vm
->gc
.bytes_free
-= sizeof (JSHeapMemoryBlock
);
210 freelist
= list (nb
->size
);
211 ((JSHeapFreelistBlock
*) nb
)->next
212 = vm
->heap_freelists
[freelist
];
213 vm
->heap_freelists
[freelist
] = nb
;
215 b
->size
= alloc_size
;
218 JS_HEAP_MEMORY_BLOCK_CLEAR_FLAGS (b
);
219 vm
->gc
.bytes_free
-= b
->size
;
220 vm
->gc
.bytes_allocated
+= b
->size
;
222 return (unsigned char *) b
+ sizeof (JSHeapMemoryBlock
);
225 /* Must allocate new blocks to the freelist. */
227 if (alloc_size
> (BLOCK_SIZE
228 - sizeof (JSHeapBlock
)
229 - sizeof (JSHeapMemoryBlock
)))
230 to_alloc
= alloc_size
+ sizeof (JSHeapBlock
) + sizeof (JSHeapMemoryBlock
);
232 to_alloc
= BLOCK_SIZE
;
237 "VM: heap: malloc(%u): needed=%u, size=%lu, free=%lu, allocated=%lu%s",
238 to_alloc
, alloc_size
, vm
->heap_size
, vm
->gc
.bytes_free
,
239 vm
->gc
.bytes_allocated
,
241 js_iostream_write (vm
->s_stderr
, buf
, strlen (buf
));
244 hb
= js_malloc (vm
, to_alloc
);
246 vm
->heap_size
+= to_alloc
;
249 hb
->size
= to_alloc
- sizeof (JSHeapBlock
);
251 /* Link it to the freelist. */
252 b
= (JSHeapMemoryBlock
*) ((unsigned char *) hb
+ sizeof (JSHeapBlock
));
257 JS_HEAP_MEMORY_BLOCK_CLEAR_FLAGS (b
);
258 b
->size
= hb
->size
- sizeof (JSHeapMemoryBlock
);
260 freelist
= list (b
->size
);
262 ((JSHeapFreelistBlock
*) b
)->next
= vm
->heap_freelists
[freelist
];
263 vm
->heap_freelists
[freelist
] = b
;
265 vm
->gc
.bytes_free
+= b
->size
;
275 js_vm_alloc_destroyable (JSVirtualMachine
*vm
, unsigned int size
)
278 JSHeapMemoryBlock
*b
;
280 bi
= js_vm_alloc (vm
, size
);
281 memset (bi
, 0, size
);
283 b
= (JSHeapMemoryBlock
*) (bi
- sizeof (JSHeapMemoryBlock
));
284 b
->flag_destroyable
= 1;
291 js_vm_realloc (JSVirtualMachine
*vm
, void *ptr
, unsigned int new_size
)
293 JSHeapMemoryBlock
*b
;
297 return js_vm_alloc (vm
, new_size
);
299 /* Can be use the old block? */
301 b
= (JSHeapMemoryBlock
*) ((unsigned char *) ptr
302 - sizeof (JSHeapMemoryBlock
));
305 assert (b
->magic
== MAGIC
);
308 if (b
->size
>= new_size
)
312 /* No we can't. Must allocate a new one. */
313 nptr
= js_vm_alloc (vm
, new_size
);
314 memcpy (nptr
, ptr
, b
->size
< new_size
? b
->size
: new_size
);
316 js_vm_free (vm
, ptr
);
323 js_vm_free (JSVirtualMachine
*vm
, void *ptr
)
325 JSHeapMemoryBlock
*b
;
326 unsigned int freelist
;
328 b
= (JSHeapMemoryBlock
*) ((unsigned char *) ptr
329 - sizeof (JSHeapMemoryBlock
));
332 assert (b
->magic
== MAGIC
);
335 freelist
= list (b
->size
);
337 ((JSHeapFreelistBlock
*) b
)->next
= vm
->heap_freelists
[freelist
];
338 vm
->heap_freelists
[freelist
] = b
;
339 vm
->gc
.bytes_free
+= b
->size
;
342 * We could try to compact the heap, but we left it to the garbage
349 js_vm_mark_ptr (void *ptr
)
351 JSHeapMemoryBlock
*b
;
356 b
= (JSHeapMemoryBlock
*) ((unsigned char *) ptr
357 - sizeof (JSHeapMemoryBlock
));
359 assert (b
->magic
== MAGIC
);
372 js_vm_is_marked_ptr (void *ptr
)
374 JSHeapMemoryBlock
*b
;
379 b
= (JSHeapMemoryBlock
*) ((unsigned char *) ptr
380 - sizeof (JSHeapMemoryBlock
));
382 assert (b
->magic
== MAGIC
);
393 js_vm_mark (JSNode
*n
)
412 js_vm_mark_ptr (n
->u
.vstring
);
413 if (!n
->u
.vstring
->staticp
)
414 js_vm_mark_ptr (n
->u
.vstring
->data
);
416 js_vm_object_mark (n
->u
.vstring
->prototype
);
420 js_vm_object_mark (n
->u
.vobject
);
424 if (js_vm_mark_ptr (n
->u
.varray
))
426 js_vm_mark_ptr (n
->u
.varray
->data
);
428 for (i
= 0; i
< n
->u
.varray
->length
; i
++)
429 js_vm_mark (&n
->u
.varray
->data
[i
]);
431 js_vm_object_mark (n
->u
.varray
->prototype
);
436 if (js_vm_mark_ptr (n
->u
.vbuiltin
))
438 js_vm_mark_ptr (n
->u
.vbuiltin
->info
);
440 js_vm_object_mark (n
->u
.vbuiltin
->info
->prototype
);
441 js_vm_object_mark (n
->u
.vbuiltin
->prototype
);
443 if (n
->u
.vbuiltin
->info
->mark_proc
)
444 (*n
->u
.vbuiltin
->info
->mark_proc
) (
446 n
->u
.vbuiltin
->instance_context
);
451 js_vm_mark_ptr (n
->u
.vfunction
);
452 js_vm_mark_ptr (n
->u
.vfunction
->implementation
);
453 js_vm_object_mark (n
->u
.vfunction
->prototype
);
461 js_vm_garbage_collect (JSVirtualMachine
*vm
, JSNode
*fp
, JSNode
*sp
)
464 unsigned long bytes_in_use
;
468 clock_t after_mark_clock
;
469 clock_t after_sweep_clock
;
475 "VM: heap: garbage collect: num_consts=%u, num_globals=%u%s",
476 vm
->num_consts
, vm
->num_globals
,
478 js_iostream_write (vm
->s_stderr
, buf
, strlen (buf
));
486 start_clock
= clock ();
489 /* Mark all constants. */
490 for (i
= 0; i
< vm
->num_consts
; i
++)
491 js_vm_mark (&vm
->consts
[i
]);
493 /* Mark all globals. */
494 for (i
= 0; i
< vm
->num_globals
; i
++)
495 js_vm_mark (&vm
->globals
[i
]);
497 /* Mark the buitin-infos of the core objects. */
498 for (i
= 0; i
<= JS_IPTR
; i
++)
499 js_vm_mark_ptr (vm
->prim
[i
]);
505 /* Use brute force and mark the whole stack. */
506 for (sp
++; sp
< vm
->stack
+ vm
->stack_size
; sp
++)
508 if (sp
->type
== JS_IPTR
)
510 /* Handle the stack frames here. */
512 /* Skip the return address. */
515 /* Possible with-chain. */
518 JSUIntAlign
*uip
= sp
->u
.iptr
;
519 JSUIntAlign ui
= *uip
;
522 /* Mark the with-chain block. */
523 js_vm_mark_ptr (uip
);
525 /* Mark the objects in the with-chain. */
526 wp
= (JSNode
*) ((unsigned char *) uip
+ sizeof (JSUIntAlign
));
528 for (i
= 0; i
< ui
; i
++)
534 /* Skip the args_fix. */
538 * And now we point to the old_fp. We skip it too at the
543 /* Mark this stack item. */
547 /* Sweep all blocks and collect free nodes to the freelist. */
550 after_mark_clock
= clock ();
553 bytes_in_use
= sweep (vm
);
556 after_sweep_clock
= clock ();
561 sprintf (buf
, "VM: heap: bytes_in_use=%lu, bytes_free=%lu%s",
562 bytes_in_use
, vm
->gc
.bytes_free
,
564 js_iostream_write (vm
->s_stderr
, buf
, strlen (buf
));
570 sprintf (buf
, "VM: heap: mark_time=%.4f, sweep_time=%.4f%s",
571 (double) (after_mark_clock
- start_clock
) / CLOCKS_PER_SEC
,
572 (double) (after_sweep_clock
- after_mark_clock
)
575 js_iostream_write (vm
->s_stderr
, buf
, strlen (buf
));
582 js_vm_clear_heap (JSVirtualMachine
*vm
)
584 /* Just sweep without marking. */