1 /******************************** -*- C -*- **************************** 2 * 3 * Object Table declarations. 4 * 5 * 6 ***********************************************************************/ 7 8 /*********************************************************************** 9 * 10 * Copyright 1988,89,90,91,92,94,95,99,2000,2001,2002,2006,2007,2008,2009 11 * Free Software Foundation, Inc. 12 * Written by Steve Byrne. 13 * 14 * This file is part of GNU Smalltalk. 15 * 16 * GNU Smalltalk is free software; you can redistribute it and/or modify it 17 * under the terms of the GNU General Public License as published by the Free 18 * Software Foundation; either version 2, or (at your option) any later 19 * version. 20 * 21 * Linking GNU Smalltalk statically or dynamically with other modules is 22 * making a combined work based on GNU Smalltalk. Thus, the terms and 23 * conditions of the GNU General Public License cover the whole 24 * combination. 25 * 26 * In addition, as a special exception, the Free Software Foundation 27 * give you permission to combine GNU Smalltalk with free software 28 * programs or libraries that are released under the GNU LGPL and with 29 * independent programs running under the GNU Smalltalk virtual machine. 30 * 31 * You may copy and distribute such a system following the terms of the 32 * GNU GPL for GNU Smalltalk and the licenses of the other code 33 * concerned, provided that you include the source code of that other 34 * code when and as the GNU GPL requires distribution of source code. 35 * 36 * Note that people who make modified versions of GNU Smalltalk are not 37 * obligated to grant this special exception for their modified 38 * versions; it is their choice whether to do so. The GNU General 39 * Public License gives permission to release a modified version without 40 * this exception; this exception also makes it possible to release a 41 * modified version which carries forward this exception. 42 * 43 * GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT 44 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 45 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 46 * more details. 47 * 48 * You should have received a copy of the GNU General Public License along with 49 * GNU Smalltalk; see the file COPYING. If not, write to the Free Software 50 * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 51 * 52 ***********************************************************************/ 53 54 55 56 #ifndef GST_OOP_H 57 #define GST_OOP_H 58 59 /* Define this flag to disable blacking of grey pages (that is, the 60 entire oldspace is scanned to look for reachable newspace objects). 61 This is also necessary to run valgrind on GNU Smalltalk. */ 62 /* #define NO_SIGSEGV_HANDLING */ 63 64 /* ... but always define it if libsigsegv does not support this platform. */ 65 #if !defined HAVE_SIGSEGV_RECOVERY || !(HAVE_SIGSEGV_RECOVERY-0) 66 #define NO_SIGSEGV_HANDLING 67 #endif 68 69 #define NUM_CHAR_OBJECTS 256 70 #define NUM_BUILTIN_OBJECTS 3 71 #define FIRST_OOP_INDEX (-NUM_CHAR_OBJECTS-NUM_BUILTIN_OBJECTS) 72 #define CHAR_OBJECT_BASE FIRST_OOP_INDEX 73 #define BUILTIN_OBJECT_BASE (-NUM_BUILTIN_OBJECTS) 74 75 /* The number of OOPs in the system. This is exclusive of Character, 76 True, False, and UndefinedObject (nil) oops, which are 77 built-ins. */ 78 #define INITIAL_OOP_TABLE_SIZE (1024 * 128 + BUILTIN_OBJECT_BASE) 79 #define MAX_OOP_TABLE_SIZE (1 << 23) 80 81 /* The number of free OOPs under which we trigger GCs. 0 is not 82 enough because _gst_scavenge might still need some oops in 83 empty_context_stack!!! */ 84 #define LOW_WATER_OOP_THRESHOLD (1024 * 2) 85 86 #define SMALLTALK_OOP_INDEX 0 87 #define PROCESSOR_OOP_INDEX 1 88 #define SYM_TABLE_OOP_INDEX 2 89 #define NIL_OOP_INDEX (BUILTIN_OBJECT_BASE + 0) 90 #define TRUE_OOP_INDEX (BUILTIN_OBJECT_BASE + 1) 91 #define FALSE_OOP_INDEX (BUILTIN_OBJECT_BASE + 2) 92 93 /* Given a number of bytes "x", return the number of 32 bit words 94 needed to represent that object, rounded up to the nearest 32 bit 95 word boundary. */ 96 #define ROUNDED_WORDS(x) \ 97 (((x) + sizeof(long) - 1) / sizeof(long)) 98 99 /* Given a number of bytes "x", round it up to the next multiple of 100 sizeof (long). */ 101 #define ROUNDED_BYTES(x) \ 102 (((x) + sizeof(long) - 1) & ~(sizeof(long) - 1)) 103 104 struct gst_character 105 { 106 OBJ_HEADER; 107 OOP charVal; 108 }; 109 110 struct gst_undefined_object 111 { 112 OBJ_HEADER; 113 }; 114 115 struct gst_boolean 116 { 117 OBJ_HEADER; 118 OOP booleanValue; 119 }; 120 121 typedef struct gst_object_memory 122 { 123 OBJ_HEADER; 124 OOP bytesPerOOP, bytesPerOTE, 125 edenSize, survSpaceSize, oldSpaceSize, fixedSpaceSize, 126 edenUsedBytes, survSpaceUsedBytes, oldSpaceUsedBytes, 127 fixedSpaceUsedBytes, rememberedTableEntries, 128 numScavenges, numGlobalGCs, numCompactions, numGrowths, 129 numOldOOPs, numFixedOOPs, numWeakOOPs, numOTEs, numFreeOTEs, 130 timeBetweenScavenges, timeBetweenGlobalGCs, timeBetweenGrowths, 131 timeToScavenge, timeToCollect, timeToCompact, 132 reclaimedBytesPerScavenge, tenuredBytesPerScavenge, 133 reclaimedBytesPerGlobalGC, reclaimedPercentPerScavenge, 134 allocFailures, allocMatches, allocSplits, allocProbes; 135 } *gst_object_memory; 136 137 typedef unsigned long inc_ptr; 138 139 /* Garbage collector data structures */ 140 141 typedef struct page_tree 142 { 143 rb_node_t rb; 144 OOP *base; 145 } 146 page_tree; 147 148 typedef struct weak_area_tree 149 { 150 rb_node_t rb; 151 OOP oop; /* Weak OOP */ 152 } 153 weak_area_tree; 154 155 typedef struct new_space { 156 OOP *minPtr; /* points to lowest addr in heap */ 157 OOP *maxPtr; /* points to highest addr in heap */ 158 OOP *allocPtr; /* new space ptr, starts low, goes up */ 159 unsigned long totalSize; /* allocated size */ 160 } new_space; 161 162 typedef struct surv_space { 163 OOP *tenurePtr; /* points to oldest object */ 164 OOP *allocPtr; /* points to past newest object */ 165 OOP *minPtr; /* points to lowest addr in heap */ 166 OOP *maxPtr; /* points to highest addr in heap */ 167 OOP *topPtr; /* points to highest used addr in heap */ 168 int allocated; /* bytes allocated in the last scavenge */ 169 int filled; /* bytes currently used */ 170 int totalSize; /* allocated size */ 171 } surv_space; 172 173 typedef struct grey_area_node { 174 struct grey_area_node *next; 175 OOP *base; 176 int n; 177 OOP oop; 178 } grey_area_node; 179 180 typedef struct grey_area_list { 181 grey_area_node *head, *tail; 182 } grey_area_list; 183 184 typedef struct cheney_scan_state { 185 OOP *queue_at; /* Next scanned object in queue */ 186 OOP *at; /* Base of currently scanned object */ 187 OOP current; /* Currently scanned object */ 188 } cheney_scan_state; 189 190 struct mark_queue 191 { 192 OOP *firstOOP, *endOOP; 193 }; 194 195 struct memory_space 196 { 197 heap_data *old, *fixed; 198 struct new_space eden; 199 struct surv_space surv[2], tenuring_queue; 200 201 struct mark_queue *markQueue, *lastMarkQueue; 202 203 /* The current state of the copying collector's scan phase. */ 204 struct cheney_scan_state scan; 205 206 /* The object table. This contains a pointer to the object, and some flag 207 bits indicating whether the object is read-only, reachable and/or pooled. 208 Some of the bits indicate the difference between the allocated length 209 (stored in the object itself), and the real length, because variable 210 byte objects may not be an even multiple of sizeof(PTR). */ 211 struct oop_s *ot, *ot_base; 212 213 /* The number of OOPs in the free list and in the full OOP 214 table. num_free_oops is only correct after a GC! */ 215 int num_free_oops, ot_size; 216 217 /* The root set of the scavenger. This includes pages in oldspace that 218 were written to, and objects that had to be tenured before they were 219 scanned. */ 220 grey_area_list grey_pages, grey_areas; 221 int rememberedTableEntries; 222 223 /* A list of areas used by weak objects. */ 224 weak_area_tree *weak_areas; 225 226 /* These are the pointer to the first allocated OOP since the last 227 completed incremental GC pass, to the last low OOP considered by 228 the incremental sweeper, to the first high OOP not considered by 229 the incremental sweeper. */ 230 OOP last_allocated_oop, last_swept_oop, next_oop_to_sweep; 231 232 /* The active survivor space */ 233 struct surv_space *active_half; 234 235 /* The beginning and end of the area mmap-ed directly from the image. */ 236 OOP *loaded_base, *loaded_end; 237 238 /* The OOP flag corresponding to the active survivor space */ 239 int active_flag; 240 241 /* The OOP flag corresponding to the inactive survivor space. */ 242 int live_flags; 243 244 /* These hold onto the object incubator's state */ 245 OOP *inc_base, *inc_ptr, *inc_end; 246 247 /* Objects that are at least this big (in bytes) are allocated outside 248 the main heap, hoping to provide more locality of reference between 249 small objects. */ 250 size_t big_object_threshold; 251 252 /* If there is this much space used after a oldspace collection, we need to 253 grow the object heap by _gst_space_grow_rate % next time we 254 do a collection, so that the storage gets copied into the new, larger 255 area. */ 256 int grow_threshold_percent; 257 258 /* Grow the object heap by this percentage when the amount of space 259 used exceeds _gst_grow_threshold_percent. */ 260 int space_grow_rate; 261 262 /* Some statistics are computed using exponential smoothing. The smoothing 263 factor is stored here. */ 264 double factor; 265 266 /* Here are the stats. */ 267 int numScavenges, numGlobalGCs, numCompactions, numGrowths; 268 int numOldOOPs, numFixedOOPs, numWeakOOPs; 269 270 double timeBetweenScavenges, timeBetweenGlobalGCs, timeBetweenGrowths; 271 double timeToScavenge, timeToCollect, timeToCompact; 272 double reclaimedBytesPerScavenge, 273 tenuredBytesPerScavenge, reclaimedBytesPerGlobalGC, 274 reclaimedPercentPerScavenge; 275 }; 276 277 /* This is true to show a message whenever a GC happens. */ 278 extern int _gst_gc_message 279 ATTRIBUTE_HIDDEN; 280 281 /* This is true in the middle of a GC. */ 282 extern int _gst_gc_running 283 ATTRIBUTE_HIDDEN; 284 285 /* Finds and returns an instance of the class CLASS_OOP. Returns "nil" 286 if there are no instances present. */ 287 extern OOP _gst_find_an_instance (OOP class_oop) 288 ATTRIBUTE_PURE 289 ATTRIBUTE_HIDDEN; 290 291 /* Execute a two-way become operation between OOP1 and OOP2. */ 292 extern void _gst_swap_objects (OOP oop1, 293 OOP oop2) 294 ATTRIBUTE_HIDDEN; 295 296 /* Flip the two survivor spaces. Starting from the root set, move eden 297 objects to survivor space, tenuring objects when the top of the space 298 is hit. Then tell the incremental sweeper not to sweep old objects. */ 299 extern void _gst_scavenge (void) 300 ATTRIBUTE_HIDDEN; 301 302 /* Mark the old objects. Starting from the root set, 303 recursively mark objects as reachable, and tell the incremental 304 sweeper to sweep unreachable objects. Decide whether the heap should 305 be compacted or even grown, so that allocating NEXT_ALLOCATION bytes 306 leaves it empty enough. */ 307 extern void _gst_global_gc (int next_allocation) 308 ATTRIBUTE_HIDDEN; 309 310 /* Mark, sweep & compact the old objects. */ 311 extern void _gst_global_compact (void) 312 ATTRIBUTE_HIDDEN; 313 314 /* Sweep a bunch of old objects, return whether there are more. */ 315 extern mst_Boolean _gst_incremental_gc_step (void) 316 ATTRIBUTE_HIDDEN; 317 318 /* The incremental collector has done its job. Update statistics, 319 and if it was also sweeping old objects, make it consider all 320 objects as alive. */ 321 extern void _gst_finished_incremental_gc (void) 322 ATTRIBUTE_HIDDEN; 323 324 /* Finish the incremental sweep phase of the GC. */ 325 extern void _gst_finish_incremental_gc (void) 326 ATTRIBUTE_HIDDEN; 327 328 /* Move all the object in survivor space to old space. */ 329 extern void _gst_tenure_all_survivors () 330 ATTRIBUTE_HIDDEN; 331 332 /* Initialize the memory allocator. The memory space is allocated, 333 and the various garbage collection flags are set to their initial 334 values. */ 335 extern void _gst_init_mem_default () 336 ATTRIBUTE_HIDDEN; 337 338 /* Initialize the memory allocator. The memory space is allocated, 339 and the various garbage collection flags are set to the given 340 values. */ 341 extern void _gst_init_mem (size_t eden, size_t survivor, size_t old, 342 size_t big_threshold, int grow_threshold_percent, 343 int space_grow_rate) 344 ATTRIBUTE_HIDDEN; 345 346 /* Initialize an OOP table of SIZE bytes, trying at the given address if 347 possible. Initially, all the OOPs are on the free list so that's 348 just how we initialize them. We do as much initialization as we can, 349 but we're called before classses are defined, so things that have 350 definite classes must wait until the classes are defined. */ 351 extern void _gst_init_oop_table (PTR address, size_t size) 352 ATTRIBUTE_HIDDEN; 353 354 /* Dump the entire contents of the OOP table. Mainly for debugging 355 purposes. */ 356 extern void _gst_dump_oop_table () 357 ATTRIBUTE_HIDDEN; 358 359 /* The almost-depth-first copying collector. If survivor space is 360 full, tenuring of the oldest object is invoked (in a circular fashion). 361 362 This function does not copy children of weak objects, for obvious 363 reasons. */ 364 extern void _gst_copy_an_oop (OOP oop) 365 ATTRIBUTE_HIDDEN; 366 367 /* Mark the objects pointed to by the list of pointers to OOPs at CUROOP 368 (included) and finishing at ATENDOOP (excluded). */ 369 extern void _gst_mark_oop_range (OOP * curOOP, 370 OOP * atEndOOP) 371 ATTRIBUTE_HIDDEN; 372 373 /* Copy the objects pointed to by the list of pointers to OOPs at CUROOP 374 (included) and finishing at ATENDOOP (excluded). */ 375 extern void _gst_copy_oop_range (OOP * curOOP, 376 OOP * atEndOOP) 377 ATTRIBUTE_HIDDEN; 378 379 /* Grey the pointers pointed to by the list of pointers to OOPs at FROM 380 (included) and for SIZE bytes. */ 381 extern void _gst_grey_oop_range (PTR from, 382 size_t size) 383 ATTRIBUTE_HIDDEN; 384 385 /* Mark OOP and the pointers pointed by that. */ 386 extern void _gst_mark_an_oop_internal (OOP oop) 387 ATTRIBUTE_HIDDEN; 388 389 /* Fully initialize the builtin objects, possible after the respective 390 classes have been created. */ 391 extern void _gst_init_builtin_objects_classes (void) 392 ATTRIBUTE_HIDDEN; 393 394 /* Create the registry of incubated objects. */ 395 extern void _gst_inc_init_registry (void) 396 ATTRIBUTE_HIDDEN; 397 398 /* Grow the registry of incubated objects when it is full. */ 399 extern void _gst_inc_grow_registry (void) 400 ATTRIBUTE_HIDDEN; 401 402 /* Allocate and return space for an object of SIZE bytes. This 403 basically means moving the allocation pointer for the current space 404 up by SIZE bytes, and, if there isn't enough space left, flipping 405 the garbage collector after memory is compacted. The space is 406 merely allocated; it is not initialized. 407 408 The pointer to the object data is returned, the OOP is 409 stored in P_OOP. */ 410 extern gst_object _gst_alloc_obj (size_t size, 411 OOP *p_oop) 412 ATTRIBUTE_HIDDEN; 413 414 /* Allocate and return space for an object of SIZE words, without 415 creating an OOP. This is a special operation that is only needed 416 at bootstrap time, so it does not care about garbage collection. */ 417 extern gst_object _gst_alloc_words (size_t size) 418 ATTRIBUTE_HIDDEN; 419 420 /* Grows the allocated memory to SPACESIZE bytes, if it's not there 421 already. 422 the memory could not be allocated. Should be called after the 423 sweep has occurred so that things are contiguous. Ensures that the 424 OOP table pointers are fixed up to point to the new objects. */ 425 extern void _gst_grow_memory_to (size_t size) 426 ATTRIBUTE_HIDDEN; 427 428 /* Grow the OOP table to NEWSIZE pointers and initialize the newly 429 created pointers. */ 430 extern mst_Boolean _gst_realloc_oop_table (size_t newSize) 431 ATTRIBUTE_HIDDEN; 432 433 /* Move OOP to oldspace. */ 434 extern void _gst_tenure_oop (OOP oop) 435 ATTRIBUTE_HIDDEN; 436 437 /* Move OOP to fixedspace. */ 438 extern void _gst_make_oop_fixed (OOP oop) 439 ATTRIBUTE_HIDDEN; 440 441 /* Make OOP a weak object. */ 442 extern void _gst_make_oop_weak (OOP oop) 443 ATTRIBUTE_HIDDEN; 444 445 /* Make OOP a non-weak object. */ 446 extern void _gst_make_oop_non_weak (OOP oop) 447 ATTRIBUTE_HIDDEN; 448 449 /* Clear the OOP data related to OOP */ 450 extern void _gst_sweep_oop (OOP oop) 451 ATTRIBUTE_HIDDEN; 452 453 /* Set the fields of the given ObjectMemory object */ 454 extern void _gst_update_object_memory_oop (OOP oop) 455 ATTRIBUTE_HIDDEN; 456 457 /* This variable represents information about the memory space. _gst_mem 458 holds the required information: basically the pointer to the base and 459 top of the space, and the pointers into it for allocation and copying. */ 460 extern struct memory_space _gst_mem 461 ATTRIBUTE_HIDDEN; 462 463 #endif /* GST_OOP_H */ 464