1 This is ../info/internals.info, produced by makeinfo version 4.0b from
2 internals/internals.texi.
4 INFO-DIR-SECTION XEmacs Editor
6 * Internals: (internals). XEmacs Internals Manual.
9 Copyright (C) 1992 - 1996 Ben Wing. Copyright (C) 1996, 1997 Sun
10 Microsystems. Copyright (C) 1994 - 1998 Free Software Foundation.
11 Copyright (C) 1994, 1995 Board of Trustees, University of Illinois.
13 Permission is granted to make and distribute verbatim copies of this
14 manual provided the copyright notice and this permission notice are
15 preserved on all copies.
17 Permission is granted to copy and distribute modified versions of
18 this manual under the conditions for verbatim copying, provided that the
19 entire resulting derived work is distributed under the terms of a
20 permission notice identical to this one.
22 Permission is granted to copy and distribute translations of this
23 manual into another language, under the above conditions for modified
24 versions, except that this permission notice may be stated in a
25 translation approved by the Foundation.
27 Permission is granted to copy and distribute modified versions of
28 this manual under the conditions for verbatim copying, provided also
29 that the section entitled "GNU General Public License" is included
30 exactly as in the original, and provided that the entire resulting
31 derived work is distributed under the terms of a permission notice
32 identical to this one.
34 Permission is granted to copy and distribute translations of this
35 manual into another language, under the above conditions for modified
36 versions, except that the section entitled "GNU General Public License"
37 may be included in a translation approved by the Free Software
38 Foundation instead of in the original English.
41 File: internals.info, Node: gc_sweep, Next: sweep_lcrecords_1, Prev: mark_object, Up: Garbage Collection - Step by Step
46 The job of this function is to free all unmarked records from
47 memory. As we know, there are different types of objects implemented
48 and managed, and consequently different ways to free them from memory.
49 *Note Introduction to Allocation::.
51 We start with all objects stored through `lcrecords'. All bulkier
52 objects are allocated and handled using that scheme of `lcrecords'.
53 Each object is `malloc'ed separately instead of placing it in one of
54 the contiguous frob blocks. All types that are currently stored using
55 `lcrecords''s `alloc_lcrecord' and `make_lcrecord_list' are the types:
56 vectors, buffers, char-table, char-table-entry, console, weak-list,
57 database, device, ldap, hash-table, command-builder, extent-auxiliary,
58 extent-info, face, coding-system, frame, image-instance, glyph,
59 popup-data, gui-item, keymap, charset, color_instance, font_instance,
60 opaque, opaque-list, process, range-table, specifier,
61 symbol-value-buffer-local, symbol-value-lisp-magic,
62 symbol-value-varalias, toolbar-button, tooltalk-message,
63 tooltalk-pattern, window, and window-configuration. We take care of
64 them in the fist place in order to be able to handle and to finalize
65 items stored in them more easily. The function `sweep_lcrecords_1' as
66 described below is doing the whole job for us. For a description about
67 the internals: *Note lrecords::.
69 Our next candidates are the other objects that behave quite
70 differently than everything else: the strings. They consists of two
71 parts, a fixed-size portion (`struct Lisp_String') holding the string's
72 length, its property list and a pointer to the second part, and the
73 actual string data, which is stored in string-chars blocks comparable to
74 frob blocks. In this block, the data is not only freed, but also a
75 compression of holes is made, i.e. all strings are relocated together.
76 *Note String::. This compacting phase is performed by the function
77 `compact_string_chars', the actual sweeping by the function
78 `sweep_strings' is described below.
80 After that, the other types are swept step by step using functions
81 `sweep_conses', `sweep_bit_vectors_1', `sweep_compiled_functions',
82 `sweep_floats', `sweep_symbols', `sweep_extents', `sweep_markers' and
83 `sweep_extents'. They are the fixed-size types cons, floats,
84 compiled-functions, symbol, marker, extent, and event stored in
85 so-called "frob blocks", and therefore we can basically do the same on
86 every type objects, using the same macros, especially defined only to
87 handle everything with respect to fixed-size blocks. The only fixed-size
88 type that is not handled here are the fixed-size portion of strings,
89 because we took special care of them earlier.
91 The only big exceptions are bit vectors stored differently and
92 therefore treated differently by the function `sweep_bit_vectors_1'
95 At first, we need some brief information about how these fixed-size
96 types are managed in general, in order to understand how the sweeping
97 is done. They have all a fixed size, and are therefore stored in big
98 blocks of memory - allocated at once - that can hold a certain amount
99 of objects of one type. The macro `DECLARE_FIXED_TYPE_ALLOC' creates
100 the suitable structures for every type. More precisely, we have the
101 block struct (holding a pointer to the previous block `prev' and the
102 objects in `block[]'), a pointer to current block
103 (`current_..._block)') and its last index (`current_..._block_index'),
104 and a pointer to the free list that will be created. Also a macro
105 `FIXED_TYPE_FROM_BLOCK' plus some related macros exists that are used
106 to obtain a new object, either from the free list
107 `ALLOCATE_FIXED_TYPE_1' if there is an unused object of that type
108 stored or by allocating a completely new block using
109 `ALLOCATE_FIXED_TYPE_FROM_BLOCK'.
111 The rest works as follows: all of them define a macro `UNMARK_...'
112 that is used to unmark the object. They define a macro
113 `ADDITIONAL_FREE_...' that defines additional work that has to be done
114 when converting an object from in use to not in use (so far, only
115 markers use it in order to unchain them). Then, they all call the macro
116 `SWEEP_FIXED_TYPE_BLOCK' instantiated with their type name and their
119 This call in particular does the following: we go over all blocks
120 starting with the current moving towards the oldest. For each block,
121 we look at every object in it. If the object already freed (checked
122 with `FREE_STRUCT_P' using the first pointer of the object), or if it is
123 set to read only (`C_READONLY_RECORD_HEADER_P', nothing must be done.
124 If it is unmarked (checked with `MARKED_RECORD_HEADER_P'), it is put in
125 the free list and set free (using the macro `FREE_FIXED_TYPE',
126 otherwise it stays in the block, but is unmarked (by `UNMARK_...').
127 While going through one block, we note if the whole block is empty. If
128 so, the whole block is freed (using `xfree') and the free list state is
129 set to the state it had before handling this block.
132 File: internals.info, Node: sweep_lcrecords_1, Next: compact_string_chars, Prev: gc_sweep, Up: Garbage Collection - Step by Step
137 After nullifying the complete lcrecord statistics, we go over all
138 lcrecords two separate times. They are all chained together in a list
139 with a head called `all_lcrecords'.
141 The first loop calls for each object its `finalizer' method, but only
142 in the case that it is not read only (`C_READONLY_RECORD_HEADER_P)', it
143 is not already marked (`MARKED_RECORD_HEADER_P'), it is not already in
144 a free list (list of freed objects, field `free') and finally it owns a
147 The second loop actually frees the appropriate objects again by
148 iterating through the whole list. In case an object is read only or
149 marked, it has to persist, otherwise it is manually freed by calling
150 `xfree'. During this loop, the lcrecord statistics are kept up to date
151 by calling `tick_lcrecord_stats' with the right arguments,
154 File: internals.info, Node: compact_string_chars, Next: sweep_strings, Prev: sweep_lcrecords_1, Up: Garbage Collection - Step by Step
156 `compact_string_chars'
157 ----------------------
159 The purpose of this function is to compact all the data parts of the
160 strings that are held in so-called `string_chars_block', i.e. the
161 strings that do not exceed a certain maximal length.
163 The procedure with which this is done is as follows. We are keeping
164 two positions in the `string_chars_block's using two pointer/integer
165 pairs, namely `from_sb'/`from_pos' and `to_sb'/`to_pos'. They stand for
166 the actual positions, from where to where, to copy the actually handled
169 While going over all chained `string_char_block's and their held
170 strings, staring at `first_string_chars_block', both pointers are
171 advanced and eventually a string is copied from `from_sb' to `to_sb',
172 depending on the status of the pointed at strings.
174 More precisely, we can distinguish between the following actions.
175 * The string at `from_sb''s position could be marked as free, which
176 is indicated by an invalid pointer to the pointer that should
177 point back to the fixed size string object, and which is checked by
178 `FREE_STRUCT_P'. In this case, the `from_sb'/`from_pos' is
179 advanced to the next string, and nothing has to be copied.
181 * Also, if a string object itself is unmarked, nothing has to be
182 copied. We likewise advance the `from_sb'/`from_pos' pair as
185 * In all other cases, we have a marked string at hand. The string
186 data must be moved from the from-position to the to-position. In
187 case there is not enough space in the actual `to_sb'-block, we
188 advance this pointer to the beginning of the next block before
189 copying. In case the from and to positions are different, we
190 perform the actual copying using the library function `memmove'.
192 After compacting, the pointer to the current `string_chars_block',
193 sitting in `current_string_chars_block', is reset on the last block to
194 which we moved a string, i.e. `to_block', and all remaining blocks (we
195 know that they just carry garbage) are explicitly `xfree'd.
198 File: internals.info, Node: sweep_strings, Next: sweep_bit_vectors_1, Prev: compact_string_chars, Up: Garbage Collection - Step by Step
203 The sweeping for the fixed sized string objects is essentially
204 exactly the same as it is for all other fixed size types. As before,
205 the freeing into the suitable free list is done by using the macro
206 `SWEEP_FIXED_SIZE_BLOCK' after defining the right macros
207 `UNMARK_string' and `ADDITIONAL_FREE_string'. These two definitions are
208 a little bit special compared to the ones used for the other fixed size
211 `UNMARK_string' is defined the same way except some additional code
212 used for updating the bookkeeping information.
214 For strings, `ADDITIONAL_FREE_string' has to do something in
215 addition: in case, the string was not allocated in a
216 `string_chars_block' because it exceeded the maximal length, and
217 therefore it was `malloc'ed separately, we know also `xfree' it
221 File: internals.info, Node: sweep_bit_vectors_1, Prev: sweep_strings, Up: Garbage Collection - Step by Step
223 `sweep_bit_vectors_1'
224 ---------------------
226 Bit vectors are also one of the rare types that are `malloc'ed
227 individually. Consequently, while sweeping, all further needless bit
228 vectors must be freed by hand. This is done, as one might imagine, the
229 expected way: since they are all registered in a list called
230 `all_bit_vectors', all elements of that list are traversed, all
231 unmarked bit vectors are unlinked by calling `xfree' and all of them
232 become unmarked. In addition, the bookkeeping information used for
233 garbage collector's output purposes is updated.
236 File: internals.info, Node: Integers and Characters, Next: Allocation from Frob Blocks, Prev: Garbage Collection - Step by Step, Up: Allocation of Objects in XEmacs Lisp
238 Integers and Characters
239 =======================
241 Integer and character Lisp objects are created from integers using
242 the macros `XSETINT()' and `XSETCHAR()' or the equivalent functions
243 `make_int()' and `make_char()'. (These are actually macros on most
244 systems.) These functions basically just do some moving of bits
245 around, since the integral value of the object is stored directly in
248 `XSETINT()' and the like will truncate values given to them that are
249 too big; i.e. you won't get the value you expected but the tag bits
250 will at least be correct.
253 File: internals.info, Node: Allocation from Frob Blocks, Next: lrecords, Prev: Integers and Characters, Up: Allocation of Objects in XEmacs Lisp
255 Allocation from Frob Blocks
256 ===========================
258 The uninitialized memory required by a `Lisp_Object' of a particular
259 type is allocated using `ALLOCATE_FIXED_TYPE()'. This only occurs
260 inside of the lowest-level object-creating functions in `alloc.c':
261 `Fcons()', `make_float()', `Fmake_byte_code()', `Fmake_symbol()',
262 `allocate_extent()', `allocate_event()', `Fmake_marker()', and
263 `make_uninit_string()'. The idea is that, for each type, there are a
264 number of frob blocks (each 2K in size); each frob block is divided up
265 into object-sized chunks. Each frob block will have some of these
266 chunks that are currently assigned to objects, and perhaps some that are
267 free. (If a frob block has nothing but free chunks, it is freed at the
268 end of the garbage collection cycle.) The free chunks are stored in a
269 free list, which is chained by storing a pointer in the first four bytes
270 of the chunk. (Except for the free chunks at the end of the last frob
271 block, which are handled using an index which points past the end of the
272 last-allocated chunk in the last frob block.) `ALLOCATE_FIXED_TYPE()'
273 first tries to retrieve a chunk from the free list; if that fails, it
274 calls `ALLOCATE_FIXED_TYPE_FROM_BLOCK()', which looks at the end of the
275 last frob block for space, and creates a new frob block if there is
276 none. (There are actually two versions of these macros, one of which is
277 more defensive but less efficient and is used for error-checking.)
280 File: internals.info, Node: lrecords, Next: Low-level allocation, Prev: Allocation from Frob Blocks, Up: Allocation of Objects in XEmacs Lisp
287 All lrecords have at the beginning of their structure a `struct
288 lrecord_header'. This just contains a type number and some flags,
289 including the mark bit. All builtin type numbers are defined as
290 constants in `enum lrecord_type', to allow the compiler to generate
291 more efficient code for `TYPEP'. The type number, thru the
292 `lrecord_implementation_table', gives access to a `struct
293 lrecord_implementation', which is a structure containing method pointers
294 and such. There is one of these for each type, and it is a global,
295 constant, statically-declared structure that is declared in the
296 `DEFINE_LRECORD_IMPLEMENTATION()' macro.
298 Simple lrecords (of type (b) above) just have a `struct
299 lrecord_header' at their beginning. lcrecords, however, actually have a
300 `struct lcrecord_header'. This, in turn, has a `struct lrecord_header'
301 at its beginning, so sanity is preserved; but it also has a pointer
302 used to chain all lcrecords together, and a special ID field used to
303 distinguish one lcrecord from another. (This field is used only for
304 debugging and could be removed, but the space gain is not significant.)
306 Simple lrecords are created using `ALLOCATE_FIXED_TYPE()', just like
307 for other frob blocks. The only change is that the implementation
308 pointer must be initialized correctly. (The implementation structure for
309 an lrecord, or rather the pointer to it, is named `lrecord_float',
310 `lrecord_extent', `lrecord_buffer', etc.)
312 lcrecords are created using `alloc_lcrecord()'. This takes a size
313 to allocate and an implementation pointer. (The size needs to be passed
314 because some lcrecords, such as window configurations, are of variable
315 size.) This basically just `malloc()'s the storage, initializes the
316 `struct lcrecord_header', and chains the lcrecord onto the head of the
317 list of all lcrecords, which is stored in the variable `all_lcrecords'.
318 The calls to `alloc_lcrecord()' generally occur in the lowest-level
319 allocation function for each lrecord type.
321 Whenever you create an lrecord, you need to call either
322 `DEFINE_LRECORD_IMPLEMENTATION()' or
323 `DEFINE_LRECORD_SEQUENCE_IMPLEMENTATION()'. This needs to be specified
324 in a `.c' file, at the top level. What this actually does is define
325 and initialize the implementation structure for the lrecord. (And
326 possibly declares a function `error_check_foo()' that implements the
327 `XFOO()' macro when error-checking is enabled.) The arguments to the
328 macros are the actual type name (this is used to construct the C
329 variable name of the lrecord implementation structure and related
330 structures using the `##' macro concatenation operator), a string that
331 names the type on the Lisp level (this may not be the same as the C
332 type name; typically, the C type name has underscores, while the Lisp
333 string has dashes), various method pointers, and the name of the C
334 structure that contains the object. The methods are used to
335 encapsulate type-specific information about the object, such as how to
336 print it or mark it for garbage collection, so that it's easy to add
337 new object types without having to add a specific case for each new
338 type in a bunch of different places.
340 The difference between `DEFINE_LRECORD_IMPLEMENTATION()' and
341 `DEFINE_LRECORD_SEQUENCE_IMPLEMENTATION()' is that the former is used
342 for fixed-size object types and the latter is for variable-size object
343 types. Most object types are fixed-size; some complex types, however
344 (e.g. window configurations), are variable-size. Variable-size object
345 types have an extra method, which is called to determine the actual
346 size of a particular object of that type. (Currently this is only used
347 for keeping allocation statistics.)
349 For the purpose of keeping allocation statistics, the allocation
350 engine keeps a list of all the different types that exist. Note that,
351 since `DEFINE_LRECORD_IMPLEMENTATION()' is a macro that is specified at
352 top-level, there is no way for it to initialize the global data
353 structures containing type information, like
354 `lrecord_implementations_table'. For this reason a call to
355 `INIT_LRECORD_IMPLEMENTATION' must be added to the same source file
356 containing `DEFINE_LRECORD_IMPLEMENTATION', but instead of to the top
357 level, to one of the init functions, typically `syms_of_FOO.c'.
358 `INIT_LRECORD_IMPLEMENTATION' must be called before an object of this
361 The type number is also used to index into an array holding the
362 number of objects of each type and the total memory allocated for
363 objects of that type. The statistics in this array are computed during
364 the sweep stage. These statistics are returned by the call to
367 Note that for every type defined with a `DEFINE_LRECORD_*()' macro,
368 there needs to be a `DECLARE_LRECORD_IMPLEMENTATION()' somewhere in a
369 `.h' file, and this `.h' file needs to be included by `inline.c'.
371 Furthermore, there should generally be a set of `XFOOBAR()',
372 `FOOBARP()', etc. macros in a `.h' (or occasionally `.c') file. To
373 create one of these, copy an existing model and modify as necessary.
375 *Please note:* If you define an lrecord in an external
376 dynamically-loaded module, you must use `DECLARE_EXTERNAL_LRECORD',
377 `DEFINE_EXTERNAL_LRECORD_IMPLEMENTATION', and
378 `DEFINE_EXTERNAL_LRECORD_SEQUENCE_IMPLEMENTATION' instead of the
379 non-EXTERNAL forms. These macros will dynamically add new type numbers
380 to the global enum that records them, whereas the non-EXTERNAL forms
381 assume that the programmer has already inserted the correct type numbers
382 into the enum's code at compile-time.
384 The various methods in the lrecord implementation structure are:
386 1. A "mark" method. This is called during the marking stage and
387 passed a function pointer (usually the `mark_object()' function),
388 which is used to mark an object. All Lisp objects that are
389 contained within the object need to be marked by applying this
390 function to them. The mark method should also return a Lisp
391 object, which should be either `nil' or an object to mark. (This
392 can be used in lieu of calling `mark_object()' on the object, to
393 reduce the recursion depth, and consequently should be the most
394 heavily nested sub-object, such as a long list.)
396 *Please note:* When the mark method is called, garbage collection
397 is in progress, and special precautions need to be taken when
398 accessing objects; see section (B) above.
400 If your mark method does not need to do anything, it can be `NULL'.
402 2. A "print" method. This is called to create a printed
403 representation of the object, whenever `princ', `prin1', or the
404 like is called. It is passed the object, a stream to which the
405 output is to be directed, and an `escapeflag' which indicates
406 whether the object's printed representation should be "escaped" so
407 that it is readable. (This corresponds to the difference between
408 `princ' and `prin1'.) Basically, "escaped" means that strings will
409 have quotes around them and confusing characters in the strings
410 such as quotes, backslashes, and newlines will be backslashed; and
411 that special care will be taken to make symbols print in a
412 readable fashion (e.g. symbols that look like numbers will be
413 backslashed). Other readable objects should perhaps pass
414 `escapeflag' on when sub-objects are printed, so that readability
415 is preserved when necessary (or if not, always pass in a 1 for
416 `escapeflag'). Non-readable objects should in general ignore
417 `escapeflag', except that some use it as an indication that more
418 verbose output should be given.
420 Sub-objects are printed using `print_internal()', which takes
421 exactly the same arguments as are passed to the print method.
423 Literal C strings should be printed using `write_c_string()', or
424 `write_string_1()' for non-null-terminated strings.
426 Functions that do not have a readable representation should check
427 the `print_readably' flag and signal an error if it is set.
429 If you specify NULL for the print method, the
430 `default_object_printer()' will be used.
432 3. A "finalize" method. This is called at the beginning of the sweep
433 stage on lcrecords that are about to be freed, and should be used
434 to perform any extra object cleanup. This typically involves
435 freeing any extra `malloc()'ed memory associated with the object,
436 releasing any operating-system and window-system resources
437 associated with the object (e.g. pixmaps, fonts), etc.
439 The finalize method can be NULL if nothing needs to be done.
441 WARNING #1: The finalize method is also called at the end of the
442 dump phase; this time with the for_disksave parameter set to
443 non-zero. The object is _not_ about to disappear, so you have to
444 make sure to _not_ free any extra `malloc()'ed memory if you're
445 going to need it later. (Also, signal an error if there are any
446 operating-system and window-system resources here, because they
449 Finalize methods should, as a rule, set to zero any pointers after
450 they've been freed, and check to make sure pointers are not zero
451 before freeing. Although I'm pretty sure that finalize methods
452 are not called twice on the same object (except for the
453 `for_disksave' proviso), we've gotten nastily burned in some cases
456 WARNING #2: The finalize method is _only_ called for lcrecords,
457 _not_ for simply lrecords. If you need a finalize method for
458 simple lrecords, you have to stick it in the
459 `ADDITIONAL_FREE_foo()' macro in `alloc.c'.
461 WARNING #3: Things are in an _extremely_ bizarre state when
462 `ADDITIONAL_FREE_foo()' is called, so you have to be incredibly
463 careful when writing one of these functions. See the comment in
464 `gc_sweep()'. If you ever have to add one of these, consider
465 using an lcrecord or dealing with the problem in a different
468 4. An "equal" method. This compares the two objects for similarity,
469 when `equal' is called. It should compare the contents of the
470 objects in some reasonable fashion. It is passed the two objects
471 and a "depth" value, which is used to catch circular objects. To
472 compare sub-Lisp-objects, call `internal_equal()' and bump the
473 depth value by one. If this value gets too high, a
474 `circular-object' error will be signaled.
476 If this is NULL, objects are `equal' only when they are `eq', i.e.
479 5. A "hash" method. This is used to hash objects when they are to be
480 compared with `equal'. The rule here is that if two objects are
481 `equal', they _must_ hash to the same value; i.e. your hash
482 function should use some subset of the sub-fields of the object
483 that are compared in the "equal" method. If you specify this
484 method as `NULL', the object's pointer will be used as the hash,
485 which will _fail_ if the object has an `equal' method, so don't do
488 To hash a sub-Lisp-object, call `internal_hash()'. Bump the depth
489 by one, just like in the "equal" method.
491 To convert a Lisp object directly into a hash value (using its
492 pointer), use `LISP_HASH()'. This is what happens when the hash
495 To hash two or more values together into a single value, use
496 `HASH2()', `HASH3()', `HASH4()', etc.
498 6. "getprop", "putprop", "remprop", and "plist" methods. These are
499 used for object types that have properties. I don't feel like
500 documenting them here. If you create one of these objects, you
501 have to use different macros to define them, i.e.
502 `DEFINE_LRECORD_IMPLEMENTATION_WITH_PROPS()' or
503 `DEFINE_LRECORD_SEQUENCE_IMPLEMENTATION_WITH_PROPS()'.
505 7. A "size_in_bytes" method, when the object is of variable-size.
506 (i.e. declared with a `_SEQUENCE_IMPLEMENTATION' macro.) This
507 should simply return the object's size in bytes, exactly as you
508 might expect. For an example, see the methods for window
509 configurations and opaques.
512 File: internals.info, Node: Low-level allocation, Next: Cons, Prev: lrecords, Up: Allocation of Objects in XEmacs Lisp
517 Memory that you want to allocate directly should be allocated using
518 `xmalloc()' rather than `malloc()'. This implements error-checking on
519 the return value, and once upon a time did some more vital stuff (i.e.
520 `BLOCK_INPUT', which is no longer necessary). Free using `xfree()',
521 and realloc using `xrealloc()'. Note that `xmalloc()' will do a
522 non-local exit if the memory can't be allocated. (Many functions,
523 however, do not expect this, and thus XEmacs will likely crash if this
524 happens. *This is a bug.* If you can, you should strive to make your
525 function handle this OK. However, it's difficult in the general
526 circumstance, perhaps requiring extra unwind-protects and such.)
528 Note that XEmacs provides two separate replacements for the standard
529 `malloc()' library function. These are called "old GNU malloc"
530 (`malloc.c') and "new GNU malloc" (`gmalloc.c'), respectively. New GNU
531 malloc is better in pretty much every way than old GNU malloc, and
532 should be used if possible. (It used to be that on some systems, the
533 old one worked but the new one didn't. I think this was due
534 specifically to a bug in SunOS, which the new one now works around; so
535 I don't think the old one ever has to be used any more.) The primary
536 difference between both of these mallocs and the standard system malloc
537 is that they are much faster, at the expense of increased space. The
538 basic idea is that memory is allocated in fixed chunks of powers of
539 two. This allows for basically constant malloc time, since the various
540 chunks can just be kept on a number of free lists. (The standard system
541 malloc typically allocates arbitrary-sized chunks and has to spend some
542 time, sometimes a significant amount of time, walking the heap looking
543 for a free block to use and cleaning things up.) The new GNU malloc
544 improves on things by allocating large objects in chunks of 4096 bytes
545 rather than in ever larger powers of two, which results in ever larger
546 wastage. There is a slight speed loss here, but it's of doubtful
549 NOTE: Apparently there is a third-generation GNU malloc that is
550 significantly better than the new GNU malloc, and should probably be
553 There is also the relocating allocator, `ralloc.c'. This actually
554 moves blocks of memory around so that the `sbrk()' pointer shrunk and
555 virtual memory released back to the system. On some systems, this is a
556 big win. On all systems, it causes a noticeable (and sometimes huge)
557 speed penalty, so I turn it off by default. `ralloc.c' only works with
558 the new GNU malloc in `gmalloc.c'. There are also two versions of
559 `ralloc.c', one that uses `mmap()' rather than block copies to move
560 data around. This purports to be faster, although that depends on the
561 amount of data that would have had to be block copied and the
562 system-call overhead for `mmap()'. I don't know exactly how this
563 works, except that the relocating-allocation routines are pretty much
564 used only for the memory allocated for a buffer, which is the biggest
565 consumer of space, esp. of space that may get freed later.
567 Note that the GNU mallocs have some "memory warning" facilities.
568 XEmacs taps into them and issues a warning through the standard warning
569 system, when memory gets to 75%, 85%, and 95% full. (On some systems,
570 the memory warnings are not functional.)
572 Allocated memory that is going to be used to make a Lisp object is
573 created using `allocate_lisp_storage()'. This just calls `xmalloc()'.
574 It used to verify that the pointer to the memory can fit into a Lisp
575 word, before the current Lisp object representation was introduced.
576 `allocate_lisp_storage()' is called by `alloc_lcrecord()',
577 `ALLOCATE_FIXED_TYPE()', and the vector and bit-vector creation
578 routines. These routines also call `INCREMENT_CONS_COUNTER()' at the
579 appropriate times; this keeps statistics on how much memory is
580 allocated, so that garbage-collection can be invoked when the threshold
584 File: internals.info, Node: Cons, Next: Vector, Prev: Low-level allocation, Up: Allocation of Objects in XEmacs Lisp
589 Conses are allocated in standard frob blocks. The only thing to
590 note is that conses can be explicitly freed using `free_cons()' and
591 associated functions `free_list()' and `free_alist()'. This
592 immediately puts the conses onto the cons free list, and decrements the
593 statistics on memory allocation appropriately. This is used to good
594 effect by some extremely commonly-used code, to avoid generating extra
595 objects and thereby triggering GC sooner. However, you have to be
596 _extremely_ careful when doing this. If you mess this up, you will get
597 BADLY BURNED, and it has happened before.
600 File: internals.info, Node: Vector, Next: Bit Vector, Prev: Cons, Up: Allocation of Objects in XEmacs Lisp
605 As mentioned above, each vector is `malloc()'ed individually, and
606 all are threaded through the variable `all_vectors'. Vectors are
607 marked strangely during garbage collection, by kludging the size field.
608 Note that the `struct Lisp_Vector' is declared with its `contents'
609 field being a _stretchy_ array of one element. It is actually
610 `malloc()'ed with the right size, however, and access to any element
611 through the `contents' array works fine.
614 File: internals.info, Node: Bit Vector, Next: Symbol, Prev: Vector, Up: Allocation of Objects in XEmacs Lisp
619 Bit vectors work exactly like vectors, except for more complicated
620 code to access an individual bit, and except for the fact that bit
621 vectors are lrecords while vectors are not. (The only difference here is
622 that there's an lrecord implementation pointer at the beginning and the
623 tag field in bit vector Lisp words is "lrecord" rather than "vector".)
626 File: internals.info, Node: Symbol, Next: Marker, Prev: Bit Vector, Up: Allocation of Objects in XEmacs Lisp
631 Symbols are also allocated in frob blocks. Symbols in the awful
632 horrible obarray structure are chained through their `next' field.
634 Remember that `intern' looks up a symbol in an obarray, creating one
638 File: internals.info, Node: Marker, Next: String, Prev: Symbol, Up: Allocation of Objects in XEmacs Lisp
643 Markers are allocated in frob blocks, as usual. They are kept in a
644 buffer unordered, but in a doubly-linked list so that they can easily
645 be removed. (Formerly this was a singly-linked list, but in some cases
646 garbage collection took an extraordinarily long time due to the O(N^2)
647 time required to remove lots of markers from a buffer.) Markers are
648 removed from a buffer in the finalize stage, in
649 `ADDITIONAL_FREE_marker()'.
652 File: internals.info, Node: String, Next: Compiled Function, Prev: Marker, Up: Allocation of Objects in XEmacs Lisp
657 As mentioned above, strings are a special case. A string is
658 logically two parts, a fixed-size object (containing the length,
659 property list, and a pointer to the actual data), and the actual data
660 in the string. The fixed-size object is a `struct Lisp_String' and is
661 allocated in frob blocks, as usual. The actual data is stored in
662 special "string-chars blocks", which are 8K blocks of memory.
663 Currently-allocated strings are simply laid end to end in these
664 string-chars blocks, with a pointer back to the `struct Lisp_String'
665 stored before each string in the string-chars block. When a new string
666 needs to be allocated, the remaining space at the end of the last
667 string-chars block is used if there's enough, and a new string-chars
668 block is created otherwise.
670 There are never any holes in the string-chars blocks due to the
671 string compaction and relocation that happens at the end of garbage
672 collection. During the sweep stage of garbage collection, when objects
673 are reclaimed, the garbage collector goes through all string-chars
674 blocks, looking for unused strings. Each chunk of string data is
675 preceded by a pointer to the corresponding `struct Lisp_String', which
676 indicates both whether the string is used and how big the string is,
677 i.e. how to get to the next chunk of string data. Holes are compressed
678 by block-copying the next string into the empty space and relocating the
679 pointer stored in the corresponding `struct Lisp_String'. *This means
680 you have to be careful with strings in your code.* See the section
683 Note that there is one situation not handled: a string that is too
684 big to fit into a string-chars block. Such strings, called "big
685 strings", are all `malloc()'ed as their own block. (#### Although it
686 would make more sense for the threshold for big strings to be somewhat
687 lower, e.g. 1/2 or 1/4 the size of a string-chars block. It seems that
688 this was indeed the case formerly--indeed, the threshold was set at
689 1/8--but Mly forgot about this when rewriting things for 19.8.)
691 Note also that the string data in string-chars blocks is padded as
692 necessary so that proper alignment constraints on the `struct
693 Lisp_String' back pointers are maintained.
695 Finally, strings can be resized. This happens in Mule when a
696 character is substituted with a different-length character, or during
697 modeline frobbing. (You could also export this to Lisp, but it's not
698 done so currently.) Resizing a string is a potentially tricky process.
699 If the change is small enough that the padding can absorb it, nothing
700 other than a simple memory move needs to be done. Keep in mind,
701 however, that the string can't shrink too much because the offset to the
702 next string in the string-chars block is computed by looking at the
703 length and rounding to the nearest multiple of four or eight. If the
704 string would shrink or expand beyond the correct padding, new string
705 data needs to be allocated at the end of the last string-chars block and
706 the data moved appropriately. This leaves some dead string data, which
707 is marked by putting a special marker of 0xFFFFFFFF in the `struct
708 Lisp_String' pointer before the data (there's no real `struct
709 Lisp_String' to point to and relocate), and storing the size of the dead
710 string data (which would normally be obtained from the now-non-existent
711 `struct Lisp_String') at the beginning of the dead string data gap.
712 The string compactor recognizes this special 0xFFFFFFFF marker and
713 handles it correctly.
716 File: internals.info, Node: Compiled Function, Prev: String, Up: Allocation of Objects in XEmacs Lisp
724 File: internals.info, Node: Dumping, Next: Events and the Event Loop, Prev: Allocation of Objects in XEmacs Lisp, Up: Top
729 What is dumping and its justification
730 =====================================
732 The C code of XEmacs is just a Lisp engine with a lot of built-in
733 primitives useful for writing an editor. The editor itself is written
734 mostly in Lisp, and represents around 100K lines of code. Loading and
735 executing the initialization of all this code takes a bit a time (five
736 to ten times the usual startup time of current xemacs) and requires
737 having all the lisp source files around. Having to reload them each
738 time the editor is started would not be acceptable.
740 The traditional solution to this problem is called dumping: the build
741 process first creates the lisp engine under the name `temacs', then
742 runs it until it has finished loading and initializing all the lisp
743 code, and eventually creates a new executable called `xemacs' including
744 both the object code in `temacs' and all the contents of the memory
745 after the initialization.
747 This solution, while working, has a huge problem: the creation of the
748 new executable from the actual contents of memory is an extremely
749 system-specific process, quite error-prone, and which interferes with a
750 lot of system libraries (like malloc). It is even getting worse
751 nowadays with libraries using constructors which are automatically
752 called when the program is started (even before main()) which tend to
753 crash when they are called multiple times, once before dumping and once
754 after (IRIX 6.x libz.so pulls in some C++ image libraries thru
755 dependencies which have this problem). Writing the dumper is also one
756 of the most difficult parts of porting XEmacs to a new operating system.
757 Basically, `dumping' is an operation that is just not officially
758 supported on many operating systems.
760 The aim of the portable dumper is to solve the same problem as the
761 system-specific dumper, that is to be able to reload quickly, using only
762 a small number of files, the fully initialized lisp part of the editor,
763 without any system-specific hacks.
768 * Data descriptions::
774 File: internals.info, Node: Overview, Next: Data descriptions, Prev: Dumping, Up: Dumping
779 The portable dumping system has to:
781 1. At dump time, write all initialized, non-quickly-rebuildable data
782 to a file [Note: currently named `xemacs.dmp', but the name will
783 change], along with all informations needed for the reloading.
785 2. When starting xemacs, reload the dump file, relocate it to its new
786 starting address if needed, and reinitialize all pointers to this
787 data. Also, rebuild all the quickly rebuildable data.
790 File: internals.info, Node: Data descriptions, Next: Dumping phase, Prev: Overview, Up: Dumping
795 The more complex task of the dumper is to be able to write lisp
796 objects (lrecords) and C structs to disk and reload them at a different
797 address, updating all the pointers they include in the process. This
798 is done by using external data descriptions that give information about
799 the layout of the structures in memory.
801 The specification of these descriptions is in lrecord.h. A
802 description of an lrecord is an array of struct lrecord_description.
803 Each of these structs include a type, an offset in the structure and
804 some optional parameters depending on the type. For instance, here is
805 the string description:
807 static const struct lrecord_description string_description[] = {
808 { XD_BYTECOUNT, offsetof (Lisp_String, size) },
809 { XD_OPAQUE_DATA_PTR, offsetof (Lisp_String, data), XD_INDIRECT(0, 1) },
810 { XD_LISP_OBJECT, offsetof (Lisp_String, plist) },
814 The first line indicates a member of type Bytecount, which is used by
815 the next, indirect directive. The second means "there is a pointer to
816 some opaque data in the field `data'". The length of said data is
817 given by the expression `XD_INDIRECT(0, 1)', which means "the value in
818 the 0th line of the description (welcome to C) plus one". The third
819 line means "there is a Lisp_Object member `plist' in the Lisp_String
820 structure". `XD_END' then ends the description.
822 This gives us all the information we need to move around what is
823 pointed to by a structure (C or lrecord) and, by transitivity,
824 everything that it points to. The only missing information for dumping
825 is the size of the structure. For lrecords, this is part of the
826 lrecord_implementation, so we don't need to duplicate it. For C
827 structures we use a struct struct_description, which includes a size
828 field and a pointer to an associated array of lrecord_description.
831 File: internals.info, Node: Dumping phase, Next: Reloading phase, Prev: Data descriptions, Up: Dumping
836 Dumping is done by calling the function pdump() (in dumper.c) which
837 is invoked from Fdump_emacs (in emacs.c). This function performs a
843 * Address allocation::
849 File: internals.info, Node: Object inventory, Next: Address allocation, Prev: Dumping phase, Up: Dumping phase
854 The first task is to build the list of the objects to dump. This
861 We end up with one `pdump_entry_list_elmt' per object group (arrays
862 of C structs are kept together) which includes a pointer to the first
863 object of the group, the per-object size and the count of objects in the
864 group, along with some other information which is initialized later.
866 These entries are linked together in `pdump_entry_list' structures
867 and can be enumerated thru either:
869 1. the `pdump_object_table', an array of `pdump_entry_list', one per
870 lrecord type, indexed by type number.
872 2. the `pdump_opaque_data_list', used for the opaque data which does
873 not include pointers, and hence does not need descriptions.
875 3. the `pdump_struct_table', which is a vector of
876 `struct_description'/`pdump_entry_list' pairs, used for non-opaque
879 This uses a marking strategy similar to the garbage collector. Some
882 1. We do not use the mark bit (which does not exist for C structures
883 anyway); we use a big hash table instead.
885 2. We do not use the mark function of lrecords but instead rely on the
886 external descriptions. This happens essentially because we need to
887 follow pointers to C structures and opaque data in addition to
890 This is done by `pdump_register_object()', which handles Lisp_Object
891 variables, and `pdump_register_struct()' which handles C structures,
892 which both delegate the description management to
893 `pdump_register_sub()'.
895 The hash table doubles as a map object to pdump_entry_list_elmt (i.e.
896 allows us to look up a pdump_entry_list_elmt with the object it points
897 to). Entries are added with `pdump_add_entry()' and looked up with
898 `pdump_get_entry()'. There is no need for entry removal. The hash
899 value is computed quite simply from the object pointer by
902 The roots for the marking are:
904 1. the `staticpro''ed variables (there is a special
905 `staticpro_nodump()' call for protected variables we do not want
908 2. the variables registered via `dump_add_root_object' (`staticpro()'
909 is equivalent to `staticpro_nodump()' + `dump_add_root_object()').
911 3. the variables registered via `dump_add_root_struct_ptr', each of
912 which points to a C structure.
914 This does not include the GCPRO'ed variables, the specbinds, the
915 catchtags, the backlist, the redisplay or the profiling info, since we
916 do not want to rebuild the actual chain of lisp calls which end up to
917 the dump-emacs call, only the global variables.
919 Weak lists and weak hash tables are dumped as if they were their
920 non-weak equivalent (without changing their type, of course). This has
921 not yet been a problem.
924 File: internals.info, Node: Address allocation, Next: The header, Prev: Object inventory, Up: Dumping phase
929 The next step is to allocate the offsets of each of the objects in
930 the final dump file. This is done by `pdump_allocate_offset()' which
931 is called indirectly by `pdump_scan_by_alignment()'.
933 The strategy to deal with alignment problems uses these facts:
935 1. real world alignment requirements are powers of two.
937 2. the C compiler is required to adjust the size of a struct so that
938 you can have an array of them next to each other. This means you
939 can have an upper bound of the alignment requirements of a given
940 structure by looking at which power of two its size is a multiple.
942 3. the non-variant part of variable size lrecords has an alignment
945 Hence, for each lrecord type, C struct type or opaque data block the
946 alignment requirement is computed as a power of two, with a minimum of
947 2^2 for lrecords. `pdump_scan_by_alignment()' then scans all the
948 `pdump_entry_list_elmt''s, the ones with the highest requirements
949 first. This ensures the best packing.
951 The maximum alignment requirement we take into account is 2^8.
953 `pdump_allocate_offset()' only has to do a linear allocation,
954 starting at offset 256 (this leaves room for the header and keeps the
958 File: internals.info, Node: The header, Next: Data dumping, Prev: Address allocation, Up: Dumping phase
963 The next step creates the file and writes a header with a signature
964 and some random information in it. The `reloc_address' field, which
965 indicates at which address the file should be loaded if we want to avoid
966 post-reload relocation, is set to 0. It then seeks to offset 256 (base
967 offset for the objects).
970 File: internals.info, Node: Data dumping, Next: Pointers dumping, Prev: The header, Up: Dumping phase
975 The data is dumped in the same order as the addresses were allocated
976 by `pdump_dump_data()', called from `pdump_scan_by_alignment()'. This
977 function copies the data to a temporary buffer, relocates all pointers
978 in the object to the addresses allocated in step Address Allocation,
979 and writes it to the file. Using the same order means that, if we are
980 careful with lrecords whose size is not a multiple of 4, we are ensured
981 that the object is always written at the offset in the file allocated
982 in step Address Allocation.
985 File: internals.info, Node: Pointers dumping, Prev: Data dumping, Up: Dumping phase
990 A bunch of tables needed to reassign properly the global pointers are
991 then written. They are:
993 1. the pdump_root_struct_ptrs dynarr
995 2. the pdump_opaques dynarr
997 3. a vector of all the offsets to the objects in the file that
998 include a description (for faster relocation at reload time)
1000 4. the pdump_root_objects and pdump_weak_object_chains dynarrs.
1002 For each of the dynarrs we write both the pointer to the variables
1003 and the relocated offset of the object they point to. Since these
1004 variables are global, the pointers are still valid when restarting the
1005 program and are used to regenerate the global pointers.
1007 The `pdump_weak_object_chains' dynarr is a special case. The
1008 variables it points to are the head of weak linked lists of lisp objects
1009 of the same type. Not all objects of this list are dumped so the
1010 relocated pointer we associate with them points to the first dumped
1011 object of the list, or Qnil if none is available. This is also the
1012 reason why they are not used as roots for the purpose of object
1015 Some very important information like the `staticpros' and
1016 `lrecord_implementations_table' are handled indirectly using
1017 `dump_add_opaque' or `dump_add_root_struct_ptr'.
1019 This is the end of the dumping part.
1022 File: internals.info, Node: Reloading phase, Next: Remaining issues, Prev: Dumping phase, Up: Dumping
1030 The file is mmap'ed in memory (which ensures a PAGESIZE alignment, at
1031 least 4096), or if mmap is unavailable or fails, a 256-bytes aligned
1032 malloc is done and the file is loaded.
1034 Some variables are reinitialized from the values found in the header.
1036 The difference between the actual loading address and the
1037 reloc_address is computed and will be used for all the relocations.
1039 Putting back the pdump_opaques
1040 ------------------------------
1042 The memory contents are restored in the obvious and trivial way.
1044 Putting back the pdump_root_struct_ptrs
1045 ---------------------------------------
1047 The variables pointed to by pdump_root_struct_ptrs in the dump phase
1048 are reset to the right relocated object addresses.
1053 All the objects are relocated using their description and their
1054 offset by `pdump_reloc_one'. This step is unnecessary if the
1055 reloc_address is equal to the file loading address.
1057 Putting back the pdump_root_objects and pdump_weak_object_chains
1058 ----------------------------------------------------------------
1060 Same as Putting back the pdump_root_struct_ptrs.
1062 Reorganize the hash tables
1063 --------------------------
1065 Since some of the hash values in the lisp hash tables are
1066 address-dependent, their layout is now wrong. So we go through each of
1067 them and have them resorted by calling `pdump_reorganize_hash_table'.
1070 File: internals.info, Node: Remaining issues, Prev: Reloading phase, Up: Dumping
1075 The build process will have to start a post-dump xemacs, ask it the
1076 loading address (which will, hopefully, be always the same between
1077 different xemacs invocations) and relocate the file to the new address.
1078 This way the object relocation phase will not have to be done, which
1079 means no writes in the objects and that, because of the use of mmap, the
1080 dumped data will be shared between all the xemacs running on the
1083 Some executable signature will be necessary to ensure that a given
1084 dump file is really associated with a given executable, or random
1085 crashes will occur. Maybe a random number set at compile or configure
1086 time thru a define. This will also allow for having
1087 differently-compiled xemacsen on the same system (mule and no-mule
1090 The DOC file contents should probably end up in the dump file.
projects / chise / xemacs-chise.git- / blob