1 /* Copyright (C) 1995, 2000 artofcode LLC. All rights reserved. 2 3 This program is free software; you can redistribute it and/or modify it 4 under the terms of the GNU General Public License as published by the 5 Free Software Foundation; either version 2 of the License, or (at your 6 option) any later version. 7 8 This program is distributed in the hope that it will be useful, but 9 WITHOUT ANY WARRANTY; without even the implied warranty of 10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 11 General Public License for more details. 12 13 You should have received a copy of the GNU General Public License along 14 with this program; if not, write to the Free Software Foundation, Inc., 15 59 Temple Place, Suite 330, Boston, MA, 02111-1307. 16 17 */ 18 19 /*$Id: gxalloc.h,v 1.6.2.1.2.1 2003/01/17 00:49:03 giles Exp $ */ 20 /* Structure definitions for standard allocator */ 21 /* Requires gsmemory.h, gsstruct.h */ 22 23 #ifndef gxalloc_INCLUDED 24 # define gxalloc_INCLUDED 25 26 #ifndef gs_ref_memory_DEFINED 27 # define gs_ref_memory_DEFINED 28 typedef struct gs_ref_memory_s gs_ref_memory_t; 29 #endif 30 31 #include "gsalloc.h" 32 #include "gxobj.h" 33 34 /* ================ Chunks ================ */ 35 36 /* 37 * We obtain memory from the operating system in `chunks'. A chunk 38 * may hold only a single large object (or string), or it may hold 39 * many objects (allocated from the bottom up, always aligned) 40 * and strings (allocated from the top down, not aligned). 41 */ 42 43 /* 44 * Refs are allocated in the bottom-up section, along with struct objects. 45 * In order to keep the overhead for refs small, we make consecutive 46 * blocks of refs into a single allocator object of type st_refs. 47 * To do this, we remember the start of the current ref object (if any), 48 * and the end of the last block of allocated refs. As long as 49 * the latter is equal to the top of the allocated area, we can add 50 * more refs to the current object; otherwise, we have to start a new one. 51 * We assume that sizeof(ref) % obj_align_mod == 0; this means that if we 52 * ever have to pad a block of refs, we never add as much as one entire ref. 53 */ 54 55 /* 56 * When we do a save, we create a new 'inner' chunk out of the remaining 57 * space in the currently active chunk. Inner chunks must not be freed 58 * by a restore. 59 * 60 * The garbage collector implements relocation for refs by scanning 61 * forward to a free object. Because of this, every ref object must end 62 * with a dummy ref that can hold the relocation for the last block. 63 * In order to put a reasonable upper bound on the scanning time, we 64 * limit the length of the objects that contain runs of refs. 65 */ 66 #define max_size_st_refs (50 * sizeof(ref)) 67 68 /* 69 * Strings carry some additional overhead for use by the GC. 70 * At the top of the chunk is a table of relocation values for 71 * 16N-character blocks of strings, where N is sizeof(uint). 72 * This table is aligned, by adding padding above it if necessary. 73 * Just below it is a mark table for the strings. This table is also aligned, 74 * to improve GC performance. The actual string data start below 75 * the mark table. These tables are not needed for a chunk that holds 76 * a single large (non-string) object, but they are needed for all other 77 * chunks, including chunks created to hold a single large string. 78 */ 79 80 /* 81 * Define the unit of data manipulation for marking strings. 82 */ 83 typedef uint string_mark_unit; 84 85 #define log2_sizeof_string_mark_unit arch_log2_sizeof_int 86 /* 87 * Define the quantum of relocation for strings, which determines 88 * the quantum for reserving space. This value must be a power of 2, 89 * must be at least sizeof(string_mark_unit) * 8, and (because of the 90 * unrolled loops in igcstr.c) currently must be equal to either 32 or 64. 91 */ 92 typedef uint string_reloc_offset; 93 94 #define log2_string_data_quantum (arch_log2_sizeof_int + 4) 95 #define string_data_quantum (1 << log2_string_data_quantum) 96 /* 97 * Define the quantum for reserving string space, including data, 98 * marks, and relocation. 99 */ 100 #define string_space_quantum\ 101 (string_data_quantum + (string_data_quantum / 8) +\ 102 sizeof(string_reloc_offset)) 103 /* 104 * Compute the amount of space needed for a chunk that holds only 105 * a string of a given size. 106 */ 107 #define string_chunk_space(nbytes)\ 108 (((nbytes) + (string_data_quantum - 1)) / string_data_quantum *\ 109 string_space_quantum) 110 /* 111 * Compute the number of string space quanta in a given amount of storage. 112 */ 113 #define string_space_quanta(spacebytes)\ 114 ((spacebytes) / string_space_quantum) 115 /* 116 * Compute the size of string marks for a given number of quanta. 117 */ 118 #define string_quanta_mark_size(nquanta)\ 119 ((nquanta) * (string_data_quantum / 8)) 120 /* 121 * Compute the size of the string freelists for a chunk. 122 */ 123 #define STRING_FREELIST_SPACE(cp)\ 124 (((cp->climit - csbase(cp) + 255) >> 8) * sizeof(*cp->sfree1)) 125 126 /* 127 * To allow the garbage collector to combine chunks, we store in the 128 * head of each chunk the address to which its contents will be moved. 129 */ 130 /*typedef struct chunk_head_s chunk_head_t; *//* in gxobj.h */ 131 132 /* Structure for a chunk. */ 133 typedef struct chunk_s chunk_t; 134 struct chunk_s { 135 chunk_head_t *chead; /* chunk head, bottom of chunk; */ 136 /* csbase is an alias for chead */ 137 #define csbase(cp) ((byte *)(cp)->chead) 138 /* Note that allocation takes place both from the bottom up */ 139 /* (aligned objects) and from the top down (strings). */ 140 byte *cbase; /* bottom of chunk data area */ 141 byte *int_freed_top; /* top of most recent internal free area */ 142 /* in chunk (which may no longer be free), */ 143 /* used to decide when to consolidate */ 144 /* trailing free space in allocated area */ 145 byte *cbot; /* bottom of free area */ 146 /* (top of aligned objects) */ 147 obj_header_t *rcur; /* current refs object, 0 if none */ 148 byte *rtop; /* top of rcur */ 149 byte *ctop; /* top of free area */ 150 /* (bottom of strings) */ 151 byte *climit; /* top of strings */ 152 byte *cend; /* top of chunk */ 153 chunk_t *cprev; /* chain chunks together, */ 154 chunk_t *cnext; /* sorted by address */ 155 chunk_t *outer; /* the chunk of which this is */ 156 /* an inner chunk, if any */ 157 uint inner_count; /* number of chunks of which this is */ 158 /* the outer chunk, if any */ 159 bool has_refs; /* true if any refs in chunk */ 160 /* 161 * Free lists for single bytes in blocks of 1 to 2*N-1 bytes, one per 162 * 256 bytes in [csbase..climit), where N is sizeof(uint). The chain 163 * pointer is a (1-byte) self-relative offset, terminated by a 0; 164 * obviously, the chain is sorted by increasing address. The free list 165 * pointers themselves are offsets relative to csbase. 166 * 167 * Note that these lists overlay the GC relocation table, and that 168 * sizeof(*sfree1) / 256 must be less than sizeof(string_reloc_offset) / 169 * string_data_quantum (as real numbers). 170 */ 171 #define SFREE_NB 4 /* # of bytes for values on sfree list */ 172 uint *sfree1; 173 /* 174 * Free list for blocks of >= 2*N bytes. Each block begins 175 * with a N-byte size and a N-byte next block pointer, 176 * both big-endian. This too is sorted in increasing address order. 177 */ 178 uint sfree; 179 /* The remaining members are for the GC. */ 180 byte *odest; /* destination for objects */ 181 byte *smark; /* mark bits for strings */ 182 uint smark_size; 183 byte *sbase; /* base for computing smark offsets */ 184 string_reloc_offset *sreloc; /* relocation for string blocks */ 185 byte *sdest; /* destination for (top of) strings */ 186 byte *rescan_bot; /* bottom of rescanning range if */ 187 /* the GC mark stack overflows */ 188 byte *rescan_top; /* top of range ditto */ 189 }; 190 191 /* The chunk descriptor is exported only for isave.c. */ 192 extern_st(st_chunk); 193 #define public_st_chunk() /* in ialloc.c */\ 194 gs_public_st_ptrs2(st_chunk, chunk_t, "chunk_t",\ 195 chunk_enum_ptrs, chunk_reloc_ptrs, cprev, cnext) 196 197 /* 198 * Macros for scanning a chunk linearly, with the following schema: 199 * SCAN_CHUNK_OBJECTS(cp) << declares pre, size >> 200 * << code for all objects -- size not set yet >> 201 * DO_ALL 202 * << code for all objects -- size is set >> 203 * END_OBJECTS_SCAN 204 */ 205 #define SCAN_CHUNK_OBJECTS(cp)\ 206 { obj_header_t *pre = (obj_header_t *)((cp)->cbase);\ 207 obj_header_t *end = (obj_header_t *)((cp)->cbot);\ 208 uint size;\ 209 \ 210 for ( ; pre < end;\ 211 pre = (obj_header_t *)((char *)pre + obj_size_round(size))\ 212 )\ 213 { 214 #define DO_ALL\ 215 size = pre_obj_contents_size(pre);\ 216 { 217 #define END_OBJECTS_SCAN_INCOMPLETE\ 218 }\ 219 }\ 220 } 221 #ifdef DEBUG 222 # define END_OBJECTS_SCAN\ 223 }\ 224 }\ 225 if ( pre != end )\ 226 { lprintf2("Chunk parsing error, 0x%lx != 0x%lx\n",\ 227 (ulong)pre, (ulong)end);\ 228 gs_abort();\ 229 }\ 230 } 231 #else 232 # define END_OBJECTS_SCAN END_OBJECTS_SCAN_INCOMPLETE 233 #endif 234 235 /* Initialize a chunk. */ 236 /* This is exported for save/restore. */ 237 void alloc_init_chunk(P5(chunk_t *, byte *, byte *, bool, chunk_t *)); 238 239 /* Initialize the string freelists in a chunk. */ 240 void alloc_init_free_strings(P1(chunk_t *)); 241 242 /* Find the chunk for a pointer. */ 243 /* Note that ptr_is_within_chunk returns true even if the pointer */ 244 /* is in an inner chunk of the chunk being tested. */ 245 #define ptr_is_within_chunk(ptr, cp)\ 246 PTR_BETWEEN((const byte *)(ptr), (cp)->cbase, (cp)->cend) 247 #define ptr_is_in_inner_chunk(ptr, cp)\ 248 ((cp)->inner_count != 0 &&\ 249 PTR_BETWEEN((const byte *)(ptr), (cp)->cbot, (cp)->ctop)) 250 #define ptr_is_in_chunk(ptr, cp)\ 251 (ptr_is_within_chunk(ptr, cp) && !ptr_is_in_inner_chunk(ptr, cp)) 252 typedef struct chunk_locator_s { 253 const gs_ref_memory_t *memory; /* for head & tail of chain */ 254 chunk_t *cp; /* one-element cache */ 255 } chunk_locator_t; 256 bool chunk_locate_ptr(P2(const void *, chunk_locator_t *)); 257 258 #define chunk_locate(ptr, clp)\ 259 (((clp)->cp != 0 && ptr_is_in_chunk(ptr, (clp)->cp)) ||\ 260 chunk_locate_ptr(ptr, clp)) 261 262 /* Close up the current chunk. */ 263 /* This is exported for save/restore and for the GC. */ 264 void alloc_close_chunk(P1(gs_ref_memory_t * mem)); 265 266 /* Reopen the current chunk after a GC. */ 267 void alloc_open_chunk(P1(gs_ref_memory_t * mem)); 268 269 /* Insert or remove a chunk in the address-ordered chain. */ 270 /* These are exported for the GC. */ 271 void alloc_link_chunk(P2(chunk_t *, gs_ref_memory_t *)); 272 void alloc_unlink_chunk(P2(chunk_t *, gs_ref_memory_t *)); 273 274 /* Free a chunk. This is exported for save/restore and for the GC. */ 275 void alloc_free_chunk(P2(chunk_t *, gs_ref_memory_t *)); 276 277 /* Print a chunk debugging message. */ 278 /* Unfortunately, the ANSI C preprocessor doesn't allow us to */ 279 /* define the list of variables being printed as a macro. */ 280 #define dprintf_chunk_format\ 281 "%s 0x%lx (0x%lx..0x%lx, 0x%lx..0x%lx..0x%lx)\n" 282 #define dprintf_chunk(msg, cp)\ 283 dprintf7(dprintf_chunk_format,\ 284 msg, (ulong)(cp), (ulong)(cp)->cbase, (ulong)(cp)->cbot,\ 285 (ulong)(cp)->ctop, (ulong)(cp)->climit, (ulong)(cp)->cend) 286 #define if_debug_chunk(c, msg, cp)\ 287 if_debug7(c, dprintf_chunk_format,\ 288 msg, (ulong)(cp), (ulong)(cp)->cbase, (ulong)(cp)->cbot,\ 289 (ulong)(cp)->ctop, (ulong)(cp)->climit, (ulong)(cp)->cend) 290 291 /* ================ Allocator state ================ */ 292 293 /* Structures for save/restore (not defined here). */ 294 struct alloc_save_s; 295 struct alloc_change_s; 296 297 /* Stream structure, only needed for the streams member of the state. */ 298 #ifndef stream_DEFINED 299 # define stream_DEFINED 300 typedef struct stream_s stream; 301 #endif 302 303 /* 304 * Ref (PostScript object) type, only needed for the binary_token_names 305 * member of the state. This really shouldn't be visible at this level at 306 * all: we include it here only to avoid splitting gs_ref_memory_t two 307 * levels, which would be architecturally better but would involve too much 308 * work at this point. 309 */ 310 #ifndef ref_DEFINED 311 typedef struct ref_s ref; 312 # define ref_DEFINED 313 #endif 314 315 /* 316 * Define the number of freelists. The index in the freelist array 317 * is the ceiling of the size of the object contents (i.e., not including 318 * the header) divided by obj_align_mod. There is an extra entry used to 319 * keep a list of all free blocks > max_freelist_size. 320 */ 321 #define max_freelist_size 800 /* big enough for gstate & contents */ 322 #define num_small_freelists\ 323 ((max_freelist_size + obj_align_mod - 1) / obj_align_mod + 1) 324 #define num_freelists (num_small_freelists + 1) 325 326 /* 327 * Define the index of the freelist containing all free blocks > 328 * max_freelist_size. 329 */ 330 #define LARGE_FREELIST_INDEX num_small_freelists 331 332 /* Define the memory manager subclass for this allocator. */ 333 struct gs_ref_memory_s { 334 /* The following are set at initialization time. */ 335 gs_memory_common; 336 gs_raw_memory_t *parent; /* for allocating chunks */ 337 uint chunk_size; 338 uint large_size; /* min size to give large object */ 339 /* its own chunk: must be */ 340 /* 1 mod obj_align_mod */ 341 uint space; /* a_local, a_global, a_system */ 342 /* Callers can change the following dynamically */ 343 /* (through a procedural interface). */ 344 gs_memory_gc_status_t gc_status; 345 /* The following are updated dynamically. */ 346 bool is_controlled; /* if true, this allocator doesn't manage */ 347 /* its own chunks */ 348 ulong limit; /* signal a VMerror when total */ 349 /* allocated exceeds this */ 350 chunk_t *cfirst; /* head of chunk list */ 351 chunk_t *clast; /* tail of chunk list */ 352 chunk_t cc; /* current chunk */ 353 chunk_t *pcc; /* where to store cc */ 354 chunk_locator_t cfreed; /* chunk where last object freed */ 355 ulong allocated; /* total size of all chunks */ 356 /* allocated at this save level */ 357 long inherited; /* chunks allocated at outer save */ 358 /* levels that should be counted */ 359 /* towards the GC threshold */ 360 /* (may be negative, but allocated + */ 361 /* inherited >= 0 always) */ 362 ulong gc_allocated; /* value of (allocated + */ 363 /* previous_status.allocated) after last GC */ 364 struct lost_ { /* space freed and 'lost' (not put on a */ 365 /* freelist) */ 366 ulong objects; 367 ulong refs; 368 ulong strings; 369 } lost; 370 /* 371 * The following are for the interpreter's convenience: the 372 * library initializes them as indicated and then never touches them. 373 */ 374 int save_level; /* # of saves with non-zero id */ 375 uint new_mask; /* l_new or 0 (default) */ 376 uint test_mask; /* l_new or ~0 (default) */ 377 stream *streams; /* streams allocated at current level */ 378 ref *names_array; /* system_names or user_names, if needed */ 379 /* Garbage collector information */ 380 gs_gc_root_t *roots; /* roots for GC */ 381 /* Sharing / saved state information */ 382 int num_contexts; /* # of contexts sharing this VM */ 383 struct alloc_change_s *changes; 384 struct alloc_save_s *saved; 385 long total_scanned; 386 struct alloc_save_s *reloc_saved; /* for GC */ 387 gs_memory_status_t previous_status; /* total allocated & used */ 388 /* in outer save levels */ 389 uint largest_free_size; /* largest (aligned) size on large block list */ 390 /* We put the freelists last to keep the scalar offsets small. */ 391 obj_header_t *freelists[num_freelists]; 392 }; 393 394 /* The descriptor for gs_ref_memory_t is exported only for */ 395 /* the alloc_save_t subclass; otherwise, it should be private. */ 396 extern_st(st_ref_memory); 397 #define public_st_ref_memory() /* in gsalloc.c */\ 398 gs_public_st_composite(st_ref_memory, gs_ref_memory_t,\ 399 "gs_ref_memory", ref_memory_enum_ptrs, ref_memory_reloc_ptrs) 400 #define st_ref_memory_max_ptrs 4 /* streams, names_array, changes, saved */ 401 402 /* Define the procedures for the standard allocator. */ 403 /* We export this for subclasses. */ 404 extern const gs_memory_procs_t gs_ref_memory_procs; 405 406 /* 407 * Scan the chunks of an allocator: 408 * SCAN_MEM_CHUNKS(mem, cp) 409 * << code to process chunk cp >> 410 * END_CHUNKS_SCAN 411 */ 412 #define SCAN_MEM_CHUNKS(mem, cp)\ 413 { chunk_t *cp = (mem)->cfirst;\ 414 for ( ; cp != 0; cp = cp->cnext )\ 415 { 416 #define END_CHUNKS_SCAN\ 417 }\ 418 } 419 420 /* ================ Debugging ================ */ 421 422 #ifdef DEBUG 423 424 /* 425 * Define the options for a memory dump. These may be or'ed together. 426 */ 427 typedef enum { 428 dump_do_default = 0, /* pro forma */ 429 dump_do_strings = 1, 430 dump_do_type_addresses = 2, 431 dump_do_no_types = 4, 432 dump_do_pointers = 8, 433 dump_do_pointed_strings = 16, /* only if do_pointers also set */ 434 dump_do_contents = 32, 435 dump_do_marks = 64 436 } dump_options_t; 437 438 /* 439 * Define all the parameters controlling what gets dumped. 440 */ 441 typedef struct dump_control_s { 442 dump_options_t options; 443 const byte *bottom; 444 const byte *top; 445 } dump_control_t; 446 447 /* Define the two most useful dump control structures. */ 448 extern const dump_control_t dump_control_default; 449 extern const dump_control_t dump_control_all; 450 451 /* ------ Procedures ------ */ 452 453 /* Print one object with the given options. */ 454 /* Relevant options: type_addresses, no_types, pointers, pointed_strings, */ 455 /* contents. */ 456 void debug_print_object(P2(const void *obj, const dump_control_t * control)); 457 458 /* Print the contents of a chunk with the given options. */ 459 /* Relevant options: all. */ 460 void debug_dump_chunk(P2(const chunk_t * cp, const dump_control_t * control)); 461 void debug_print_chunk(P1(const chunk_t * cp)); /* default options */ 462 463 /* Print the contents of all chunks managed by an allocator. */ 464 /* Relevant options: all. */ 465 void debug_dump_memory(P2(const gs_ref_memory_t * mem, 466 const dump_control_t * control)); 467 468 /* Find all the objects that contain a given pointer. */ 469 void debug_find_pointers(P2(const gs_ref_memory_t *mem, const void *target)); 470 471 #endif /* DEBUG */ 472 473 #endif /* gxalloc_INCLUDED */ 474