1 /* Copyright (C) 1995, 2000 Aladdin Enterprises. All rights reserved. 2 3 This software is provided AS-IS with no warranty, either express or 4 implied. 5 6 This software is distributed under license and may not be copied, 7 modified or distributed except as expressly authorized under the terms 8 of the license contained in the file LICENSE in this distribution. 9 10 For more information about licensing, please refer to 11 http://www.ghostscript.com/licensing/. For information on 12 commercial licensing, go to http://www.artifex.com/licensing/ or 13 contact Artifex Software, Inc., 101 Lucas Valley Road #110, 14 San Rafael, CA 94903, U.S.A., +1(415)492-9861. 15 */ 16 17 /* $Id: gxalloc.h,v 1.12 2005/10/12 10:45:21 leonardo Exp $ */ 18 /* Structure definitions for standard allocator */ 19 /* Requires gsmemory.h, gsstruct.h */ 20 21 #ifndef gxalloc_INCLUDED 22 # define gxalloc_INCLUDED 23 24 #ifndef gs_ref_memory_DEFINED 25 # define gs_ref_memory_DEFINED 26 typedef struct gs_ref_memory_s gs_ref_memory_t; 27 #endif 28 29 #include "gsalloc.h" 30 #include "gxobj.h" 31 32 /* ================ Chunks ================ */ 33 34 /* 35 * We obtain memory from the operating system in `chunks'. A chunk 36 * may hold only a single large object (or string), or it may hold 37 * many objects (allocated from the bottom up, always aligned) 38 * and strings (allocated from the top down, not aligned). 39 */ 40 41 /* 42 * Refs are allocated in the bottom-up section, along with struct objects. 43 * In order to keep the overhead for refs small, we make consecutive 44 * blocks of refs into a single allocator object of type st_refs. 45 * To do this, we remember the start of the current ref object (if any), 46 * and the end of the last block of allocated refs. As long as 47 * the latter is equal to the top of the allocated area, we can add 48 * more refs to the current object; otherwise, we have to start a new one. 49 * We assume that sizeof(ref) % obj_align_mod == 0; this means that if we 50 * ever have to pad a block of refs, we never add as much as one entire ref. 51 */ 52 53 /* 54 * When we do a save, we create a new 'inner' chunk out of the remaining 55 * space in the currently active chunk. Inner chunks must not be freed 56 * by a restore. 57 * 58 * The garbage collector implements relocation for refs by scanning 59 * forward to a free object. Because of this, every ref object must end 60 * with a dummy ref that can hold the relocation for the last block. 61 * In order to put a reasonable upper bound on the scanning time, we 62 * limit the length of the objects that contain runs of refs. 63 */ 64 #define max_size_st_refs (50 * sizeof(ref)) 65 66 /* 67 * Strings carry some additional overhead for use by the GC. 68 * At the top of the chunk is a table of relocation values for 69 * 16N-character blocks of strings, where N is sizeof(uint). 70 * This table is aligned, by adding padding above it if necessary. 71 * Just below it is a mark table for the strings. This table is also aligned, 72 * to improve GC performance. The actual string data start below 73 * the mark table. These tables are not needed for a chunk that holds 74 * a single large (non-string) object, but they are needed for all other 75 * chunks, including chunks created to hold a single large string. 76 */ 77 78 /* 79 * Define the unit of data manipulation for marking strings. 80 */ 81 typedef uint string_mark_unit; 82 83 #define log2_sizeof_string_mark_unit arch_log2_sizeof_int 84 /* 85 * Define the quantum of relocation for strings, which determines 86 * the quantum for reserving space. This value must be a power of 2, 87 * must be at least sizeof(string_mark_unit) * 8, and (because of the 88 * unrolled loops in igcstr.c) currently must be equal to either 32 or 64. 89 */ 90 typedef uint string_reloc_offset; 91 92 #define log2_string_data_quantum (arch_log2_sizeof_int + 4) 93 #define string_data_quantum (1 << log2_string_data_quantum) 94 /* 95 * Define the quantum for reserving string space, including data, 96 * marks, and relocation. 97 */ 98 #define string_space_quantum\ 99 (string_data_quantum + (string_data_quantum / 8) +\ 100 sizeof(string_reloc_offset)) 101 /* 102 * Compute the amount of space needed for a chunk that holds only 103 * a string of a given size. 104 */ 105 #define string_chunk_space(nbytes)\ 106 (((nbytes) + (string_data_quantum - 1)) / string_data_quantum *\ 107 string_space_quantum) 108 /* 109 * Compute the number of string space quanta in a given amount of storage. 110 */ 111 #define string_space_quanta(spacebytes)\ 112 ((spacebytes) / string_space_quantum) 113 /* 114 * Compute the size of string marks for a given number of quanta. 115 */ 116 #define string_quanta_mark_size(nquanta)\ 117 ((nquanta) * (string_data_quantum / 8)) 118 /* 119 * Compute the size of the string freelists for a chunk. 120 */ 121 #define STRING_FREELIST_SPACE(cp)\ 122 (((cp->climit - csbase(cp) + 255) >> 8) * sizeof(*cp->sfree1)) 123 124 /* 125 * To allow the garbage collector to combine chunks, we store in the 126 * head of each chunk the address to which its contents will be moved. 127 */ 128 /*typedef struct chunk_head_s chunk_head_t; *//* in gxobj.h */ 129 130 /* Structure for a chunk. */ 131 typedef struct chunk_s chunk_t; 132 struct chunk_s { 133 chunk_head_t *chead; /* chunk head, bottom of chunk; */ 134 /* csbase is an alias for chead */ 135 #define csbase(cp) ((byte *)(cp)->chead) 136 /* Note that allocation takes place both from the bottom up */ 137 /* (aligned objects) and from the top down (strings). */ 138 byte *cbase; /* bottom of chunk data area */ 139 byte *int_freed_top; /* top of most recent internal free area */ 140 /* in chunk (which may no longer be free), */ 141 /* used to decide when to consolidate */ 142 /* trailing free space in allocated area */ 143 byte *cbot; /* bottom of free area */ 144 /* (top of aligned objects) */ 145 obj_header_t *rcur; /* current refs object, 0 if none */ 146 byte *rtop; /* top of rcur */ 147 byte *ctop; /* top of free area */ 148 /* (bottom of strings) */ 149 byte *climit; /* top of strings */ 150 byte *cend; /* top of chunk */ 151 chunk_t *cprev; /* chain chunks together, */ 152 chunk_t *cnext; /* sorted by address */ 153 chunk_t *outer; /* the chunk of which this is */ 154 /* an inner chunk, if any */ 155 uint inner_count; /* number of chunks of which this is */ 156 /* the outer chunk, if any */ 157 bool has_refs; /* true if any refs in chunk */ 158 /* 159 * Free lists for single bytes in blocks of 1 to 2*N-1 bytes, one per 160 * 256 bytes in [csbase..climit), where N is sizeof(uint). The chain 161 * pointer is a (1-byte) self-relative offset, terminated by a 0; 162 * obviously, the chain is sorted by increasing address. The free list 163 * pointers themselves are offsets relative to csbase. 164 * 165 * Note that these lists overlay the GC relocation table, and that 166 * sizeof(*sfree1) / 256 must be less than sizeof(string_reloc_offset) / 167 * string_data_quantum (as real numbers). 168 */ 169 #define SFREE_NB 4 /* # of bytes for values on sfree list */ 170 uint *sfree1; 171 /* 172 * Free list for blocks of >= 2*N bytes. Each block begins 173 * with a N-byte size and a N-byte next block pointer, 174 * both big-endian. This too is sorted in increasing address order. 175 */ 176 uint sfree; 177 /* The remaining members are for the GC. */ 178 byte *odest; /* destination for objects */ 179 byte *smark; /* mark bits for strings */ 180 uint smark_size; 181 byte *sbase; /* base for computing smark offsets */ 182 string_reloc_offset *sreloc; /* relocation for string blocks */ 183 byte *sdest; /* destination for (top of) strings */ 184 byte *rescan_bot; /* bottom of rescanning range if */ 185 /* the GC mark stack overflows */ 186 byte *rescan_top; /* top of range ditto */ 187 }; 188 189 /* The chunk descriptor is exported only for isave.c. */ 190 extern_st(st_chunk); 191 #define public_st_chunk() /* in ialloc.c */\ 192 gs_public_st_ptrs2(st_chunk, chunk_t, "chunk_t",\ 193 chunk_enum_ptrs, chunk_reloc_ptrs, cprev, cnext) 194 195 /* 196 * Macros for scanning a chunk linearly, with the following schema: 197 * SCAN_CHUNK_OBJECTS(cp) << declares pre, size >> 198 * << code for all objects -- size not set yet >> 199 * DO_ALL 200 * << code for all objects -- size is set >> 201 * END_OBJECTS_SCAN 202 * 203 * NB on error END_OBJECTS_SCAN calls gs_abort in debug systems. 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_NO_ABORT\ 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((const gs_memory_t *)NULL);*/ \ 229 }\ 230 } 231 #else 232 # define END_OBJECTS_SCAN END_OBJECTS_SCAN_NO_ABORT 233 #endif 234 235 /* Initialize a chunk. */ 236 /* This is exported for save/restore. */ 237 void alloc_init_chunk(chunk_t *, byte *, byte *, bool, chunk_t *); 238 239 /* Initialize the string freelists in a chunk. */ 240 void alloc_init_free_strings(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(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(gs_ref_memory_t * mem); 265 266 /* Reopen the current chunk after a GC. */ 267 void alloc_open_chunk(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(chunk_t *, gs_ref_memory_t *); 272 void alloc_unlink_chunk(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(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 uint chunk_size; 337 uint large_size; /* min size to give large object */ 338 /* its own chunk: must be */ 339 /* 1 mod obj_align_mod */ 340 uint space; /* a_local, a_global, a_system */ 341 # if IGC_PTR_STABILITY_CHECK 342 unsigned space_id:3; /* r_space_bits + 1 bit for "instability". */ 343 # endif 344 /* Callers can change the following dynamically */ 345 /* (through a procedural interface). */ 346 gs_memory_gc_status_t gc_status; 347 /* The following are updated dynamically. */ 348 bool is_controlled; /* if true, this allocator doesn't manage */ 349 /* its own chunks */ 350 ulong limit; /* signal a VMerror when total */ 351 /* allocated exceeds this */ 352 chunk_t *cfirst; /* head of chunk list */ 353 chunk_t *clast; /* tail of chunk list */ 354 chunk_t cc; /* current chunk */ 355 chunk_t *pcc; /* where to store cc */ 356 chunk_locator_t cfreed; /* chunk where last object freed */ 357 ulong allocated; /* total size of all chunks */ 358 /* allocated at this save level */ 359 long inherited; /* chunks allocated at outer save */ 360 /* levels that should be counted */ 361 /* towards the GC threshold */ 362 /* (may be negative, but allocated + */ 363 /* inherited >= 0 always) */ 364 ulong gc_allocated; /* value of (allocated + */ 365 /* previous_status.allocated) after last GC */ 366 struct lost_ { /* space freed and 'lost' (not put on a */ 367 /* freelist) */ 368 ulong objects; 369 ulong refs; 370 ulong strings; 371 } lost; 372 /* 373 * The following are for the interpreter's convenience: the 374 * library initializes them as indicated and then never touches them. 375 */ 376 int save_level; /* # of saves with non-zero id */ 377 uint new_mask; /* l_new or 0 (default) */ 378 uint test_mask; /* l_new or ~0 (default) */ 379 stream *streams; /* streams allocated at current level */ 380 ref *names_array; /* system_names or user_names, if needed */ 381 /* Garbage collector information */ 382 gs_gc_root_t *roots; /* roots for GC */ 383 /* Sharing / saved state information */ 384 int num_contexts; /* # of contexts sharing this VM */ 385 struct alloc_change_s *changes; 386 struct alloc_save_s *saved; 387 long total_scanned; 388 struct alloc_save_s *reloc_saved; /* for GC */ 389 gs_memory_status_t previous_status; /* total allocated & used */ 390 /* in outer save levels */ 391 uint largest_free_size; /* largest (aligned) size on large block list */ 392 /* We put the freelists last to keep the scalar offsets small. */ 393 obj_header_t *freelists[num_freelists]; 394 }; 395 396 /* The descriptor for gs_ref_memory_t is exported only for */ 397 /* the alloc_save_t subclass; otherwise, it should be private. */ 398 extern_st(st_ref_memory); 399 #define public_st_ref_memory() /* in gsalloc.c */\ 400 gs_public_st_composite(st_ref_memory, gs_ref_memory_t,\ 401 "gs_ref_memory", ref_memory_enum_ptrs, ref_memory_reloc_ptrs) 402 #define st_ref_memory_max_ptrs 4 /* streams, names_array, changes, saved */ 403 404 /* Define the procedures for the standard allocator. */ 405 /* We export this for subclasses. */ 406 extern const gs_memory_procs_t gs_ref_memory_procs; 407 408 /* 409 * Scan the chunks of an allocator: 410 * SCAN_MEM_CHUNKS(mem, cp) 411 * << code to process chunk cp >> 412 * END_CHUNKS_SCAN 413 */ 414 #define SCAN_MEM_CHUNKS(mem, cp)\ 415 { chunk_t *cp = (mem)->cfirst;\ 416 for ( ; cp != 0; cp = cp->cnext )\ 417 { 418 #define END_CHUNKS_SCAN\ 419 }\ 420 } 421 422 /* ================ Debugging ================ */ 423 424 #ifdef DEBUG 425 426 /* 427 * Define the options for a memory dump. These may be or'ed together. 428 */ 429 typedef enum { 430 dump_do_default = 0, /* pro forma */ 431 dump_do_strings = 1, 432 dump_do_type_addresses = 2, 433 dump_do_no_types = 4, 434 dump_do_pointers = 8, 435 dump_do_pointed_strings = 16, /* only if do_pointers also set */ 436 dump_do_contents = 32, 437 dump_do_marks = 64 438 } dump_options_t; 439 440 /* 441 * Define all the parameters controlling what gets dumped. 442 */ 443 typedef struct dump_control_s { 444 dump_options_t options; 445 const byte *bottom; 446 const byte *top; 447 } dump_control_t; 448 449 /* Define the two most useful dump control structures. */ 450 extern const dump_control_t dump_control_default; 451 extern const dump_control_t dump_control_all; 452 453 /* ------ Procedures ------ */ 454 455 /* Print one object with the given options. */ 456 /* Relevant options: type_addresses, no_types, pointers, pointed_strings, */ 457 /* contents. */ 458 void debug_print_object(const gs_memory_t *mem, const void *obj, const dump_control_t * control); 459 460 /* Print the contents of a chunk with the given options. */ 461 /* Relevant options: all. */ 462 void debug_dump_chunk(const gs_memory_t *mem, const chunk_t * cp, const dump_control_t * control); 463 void debug_print_chunk(const gs_memory_t *mem, const chunk_t * cp); /* default options */ 464 465 /* Print the contents of all chunks managed by an allocator. */ 466 /* Relevant options: all. */ 467 void debug_dump_memory(const gs_ref_memory_t *mem, 468 const dump_control_t *control); 469 470 /* Find all the objects that contain a given pointer. */ 471 void debug_find_pointers(const gs_ref_memory_t *mem, const void *target); 472 473 #endif /* DEBUG */ 474 475 #endif /* gxalloc_INCLUDED */ 476