1 This is ../info/internals.info, produced by makeinfo version 4.0 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 The various methods in the lrecord implementation structure are:
377 1. A "mark" method. This is called during the marking stage and
378 passed a function pointer (usually the `mark_object()' function),
379 which is used to mark an object. All Lisp objects that are
380 contained within the object need to be marked by applying this
381 function to them. The mark method should also return a Lisp
382 object, which should be either nil or an object to mark. (This can
383 be used in lieu of calling `mark_object()' on the object, to
384 reduce the recursion depth, and consequently should be the most
385 heavily nested sub-object, such as a long list.)
387 *Please note:* When the mark method is called, garbage collection
388 is in progress, and special precautions need to be taken when
389 accessing objects; see section (B) above.
391 If your mark method does not need to do anything, it can be `NULL'.
393 2. A "print" method. This is called to create a printed
394 representation of the object, whenever `princ', `prin1', or the
395 like is called. It is passed the object, a stream to which the
396 output is to be directed, and an `escapeflag' which indicates
397 whether the object's printed representation should be "escaped" so
398 that it is readable. (This corresponds to the difference between
399 `princ' and `prin1'.) Basically, "escaped" means that strings will
400 have quotes around them and confusing characters in the strings
401 such as quotes, backslashes, and newlines will be backslashed; and
402 that special care will be taken to make symbols print in a
403 readable fashion (e.g. symbols that look like numbers will be
404 backslashed). Other readable objects should perhaps pass
405 `escapeflag' on when sub-objects are printed, so that readability
406 is preserved when necessary (or if not, always pass in a 1 for
407 `escapeflag'). Non-readable objects should in general ignore
408 `escapeflag', except that some use it as an indication that more
409 verbose output should be given.
411 Sub-objects are printed using `print_internal()', which takes
412 exactly the same arguments as are passed to the print method.
414 Literal C strings should be printed using `write_c_string()', or
415 `write_string_1()' for non-null-terminated strings.
417 Functions that do not have a readable representation should check
418 the `print_readably' flag and signal an error if it is set.
420 If you specify NULL for the print method, the
421 `default_object_printer()' will be used.
423 3. A "finalize" method. This is called at the beginning of the sweep
424 stage on lcrecords that are about to be freed, and should be used
425 to perform any extra object cleanup. This typically involves
426 freeing any extra `malloc()'ed memory associated with the object,
427 releasing any operating-system and window-system resources
428 associated with the object (e.g. pixmaps, fonts), etc.
430 The finalize method can be NULL if nothing needs to be done.
432 WARNING #1: The finalize method is also called at the end of the
433 dump phase; this time with the for_disksave parameter set to
434 non-zero. The object is _not_ about to disappear, so you have to
435 make sure to _not_ free any extra `malloc()'ed memory if you're
436 going to need it later. (Also, signal an error if there are any
437 operating-system and window-system resources here, because they
440 Finalize methods should, as a rule, set to zero any pointers after
441 they've been freed, and check to make sure pointers are not zero
442 before freeing. Although I'm pretty sure that finalize methods
443 are not called twice on the same object (except for the
444 `for_disksave' proviso), we've gotten nastily burned in some cases
447 WARNING #2: The finalize method is _only_ called for lcrecords,
448 _not_ for simply lrecords. If you need a finalize method for
449 simple lrecords, you have to stick it in the
450 `ADDITIONAL_FREE_foo()' macro in `alloc.c'.
452 WARNING #3: Things are in an _extremely_ bizarre state when
453 `ADDITIONAL_FREE_foo()' is called, so you have to be incredibly
454 careful when writing one of these functions. See the comment in
455 `gc_sweep()'. If you ever have to add one of these, consider
456 using an lcrecord or dealing with the problem in a different
459 4. An "equal" method. This compares the two objects for similarity,
460 when `equal' is called. It should compare the contents of the
461 objects in some reasonable fashion. It is passed the two objects
462 and a "depth" value, which is used to catch circular objects. To
463 compare sub-Lisp-objects, call `internal_equal()' and bump the
464 depth value by one. If this value gets too high, a
465 `circular-object' error will be signaled.
467 If this is NULL, objects are `equal' only when they are `eq', i.e.
470 5. A "hash" method. This is used to hash objects when they are to be
471 compared with `equal'. The rule here is that if two objects are
472 `equal', they _must_ hash to the same value; i.e. your hash
473 function should use some subset of the sub-fields of the object
474 that are compared in the "equal" method. If you specify this
475 method as `NULL', the object's pointer will be used as the hash,
476 which will _fail_ if the object has an `equal' method, so don't do
479 To hash a sub-Lisp-object, call `internal_hash()'. Bump the depth
480 by one, just like in the "equal" method.
482 To convert a Lisp object directly into a hash value (using its
483 pointer), use `LISP_HASH()'. This is what happens when the hash
486 To hash two or more values together into a single value, use
487 `HASH2()', `HASH3()', `HASH4()', etc.
489 6. "getprop", "putprop", "remprop", and "plist" methods. These are
490 used for object types that have properties. I don't feel like
491 documenting them here. If you create one of these objects, you
492 have to use different macros to define them, i.e.
493 `DEFINE_LRECORD_IMPLEMENTATION_WITH_PROPS()' or
494 `DEFINE_LRECORD_SEQUENCE_IMPLEMENTATION_WITH_PROPS()'.
496 7. A "size_in_bytes" method, when the object is of variable-size.
497 (i.e. declared with a `_SEQUENCE_IMPLEMENTATION' macro.) This
498 should simply return the object's size in bytes, exactly as you
499 might expect. For an example, see the methods for window
500 configurations and opaques.
503 File: internals.info, Node: Low-level allocation, Next: Cons, Prev: lrecords, Up: Allocation of Objects in XEmacs Lisp
508 Memory that you want to allocate directly should be allocated using
509 `xmalloc()' rather than `malloc()'. This implements error-checking on
510 the return value, and once upon a time did some more vital stuff (i.e.
511 `BLOCK_INPUT', which is no longer necessary). Free using `xfree()',
512 and realloc using `xrealloc()'. Note that `xmalloc()' will do a
513 non-local exit if the memory can't be allocated. (Many functions,
514 however, do not expect this, and thus XEmacs will likely crash if this
515 happens. *This is a bug.* If you can, you should strive to make your
516 function handle this OK. However, it's difficult in the general
517 circumstance, perhaps requiring extra unwind-protects and such.)
519 Note that XEmacs provides two separate replacements for the standard
520 `malloc()' library function. These are called "old GNU malloc"
521 (`malloc.c') and "new GNU malloc" (`gmalloc.c'), respectively. New GNU
522 malloc is better in pretty much every way than old GNU malloc, and
523 should be used if possible. (It used to be that on some systems, the
524 old one worked but the new one didn't. I think this was due
525 specifically to a bug in SunOS, which the new one now works around; so
526 I don't think the old one ever has to be used any more.) The primary
527 difference between both of these mallocs and the standard system malloc
528 is that they are much faster, at the expense of increased space. The
529 basic idea is that memory is allocated in fixed chunks of powers of
530 two. This allows for basically constant malloc time, since the various
531 chunks can just be kept on a number of free lists. (The standard system
532 malloc typically allocates arbitrary-sized chunks and has to spend some
533 time, sometimes a significant amount of time, walking the heap looking
534 for a free block to use and cleaning things up.) The new GNU malloc
535 improves on things by allocating large objects in chunks of 4096 bytes
536 rather than in ever larger powers of two, which results in ever larger
537 wastage. There is a slight speed loss here, but it's of doubtful
540 NOTE: Apparently there is a third-generation GNU malloc that is
541 significantly better than the new GNU malloc, and should probably be
544 There is also the relocating allocator, `ralloc.c'. This actually
545 moves blocks of memory around so that the `sbrk()' pointer shrunk and
546 virtual memory released back to the system. On some systems, this is a
547 big win. On all systems, it causes a noticeable (and sometimes huge)
548 speed penalty, so I turn it off by default. `ralloc.c' only works with
549 the new GNU malloc in `gmalloc.c'. There are also two versions of
550 `ralloc.c', one that uses `mmap()' rather than block copies to move
551 data around. This purports to be faster, although that depends on the
552 amount of data that would have had to be block copied and the
553 system-call overhead for `mmap()'. I don't know exactly how this
554 works, except that the relocating-allocation routines are pretty much
555 used only for the memory allocated for a buffer, which is the biggest
556 consumer of space, esp. of space that may get freed later.
558 Note that the GNU mallocs have some "memory warning" facilities.
559 XEmacs taps into them and issues a warning through the standard warning
560 system, when memory gets to 75%, 85%, and 95% full. (On some systems,
561 the memory warnings are not functional.)
563 Allocated memory that is going to be used to make a Lisp object is
564 created using `allocate_lisp_storage()'. This just calls `xmalloc()'.
565 It used to verify that the pointer to the memory can fit into a Lisp
566 word, before the current Lisp object representation was introduced.
567 `allocate_lisp_storage()' is called by `alloc_lcrecord()',
568 `ALLOCATE_FIXED_TYPE()', and the vector and bit-vector creation
569 routines. These routines also call `INCREMENT_CONS_COUNTER()' at the
570 appropriate times; this keeps statistics on how much memory is
571 allocated, so that garbage-collection can be invoked when the threshold
575 File: internals.info, Node: Cons, Next: Vector, Prev: Low-level allocation, Up: Allocation of Objects in XEmacs Lisp
580 Conses are allocated in standard frob blocks. The only thing to
581 note is that conses can be explicitly freed using `free_cons()' and
582 associated functions `free_list()' and `free_alist()'. This
583 immediately puts the conses onto the cons free list, and decrements the
584 statistics on memory allocation appropriately. This is used to good
585 effect by some extremely commonly-used code, to avoid generating extra
586 objects and thereby triggering GC sooner. However, you have to be
587 _extremely_ careful when doing this. If you mess this up, you will get
588 BADLY BURNED, and it has happened before.
591 File: internals.info, Node: Vector, Next: Bit Vector, Prev: Cons, Up: Allocation of Objects in XEmacs Lisp
596 As mentioned above, each vector is `malloc()'ed individually, and
597 all are threaded through the variable `all_vectors'. Vectors are
598 marked strangely during garbage collection, by kludging the size field.
599 Note that the `struct Lisp_Vector' is declared with its `contents'
600 field being a _stretchy_ array of one element. It is actually
601 `malloc()'ed with the right size, however, and access to any element
602 through the `contents' array works fine.
605 File: internals.info, Node: Bit Vector, Next: Symbol, Prev: Vector, Up: Allocation of Objects in XEmacs Lisp
610 Bit vectors work exactly like vectors, except for more complicated
611 code to access an individual bit, and except for the fact that bit
612 vectors are lrecords while vectors are not. (The only difference here is
613 that there's an lrecord implementation pointer at the beginning and the
614 tag field in bit vector Lisp words is "lrecord" rather than "vector".)
617 File: internals.info, Node: Symbol, Next: Marker, Prev: Bit Vector, Up: Allocation of Objects in XEmacs Lisp
622 Symbols are also allocated in frob blocks. Symbols in the awful
623 horrible obarray structure are chained through their `next' field.
625 Remember that `intern' looks up a symbol in an obarray, creating one
629 File: internals.info, Node: Marker, Next: String, Prev: Symbol, Up: Allocation of Objects in XEmacs Lisp
634 Markers are allocated in frob blocks, as usual. They are kept in a
635 buffer unordered, but in a doubly-linked list so that they can easily
636 be removed. (Formerly this was a singly-linked list, but in some cases
637 garbage collection took an extraordinarily long time due to the O(N^2)
638 time required to remove lots of markers from a buffer.) Markers are
639 removed from a buffer in the finalize stage, in
640 `ADDITIONAL_FREE_marker()'.
643 File: internals.info, Node: String, Next: Compiled Function, Prev: Marker, Up: Allocation of Objects in XEmacs Lisp
648 As mentioned above, strings are a special case. A string is
649 logically two parts, a fixed-size object (containing the length,
650 property list, and a pointer to the actual data), and the actual data
651 in the string. The fixed-size object is a `struct Lisp_String' and is
652 allocated in frob blocks, as usual. The actual data is stored in
653 special "string-chars blocks", which are 8K blocks of memory.
654 Currently-allocated strings are simply laid end to end in these
655 string-chars blocks, with a pointer back to the `struct Lisp_String'
656 stored before each string in the string-chars block. When a new string
657 needs to be allocated, the remaining space at the end of the last
658 string-chars block is used if there's enough, and a new string-chars
659 block is created otherwise.
661 There are never any holes in the string-chars blocks due to the
662 string compaction and relocation that happens at the end of garbage
663 collection. During the sweep stage of garbage collection, when objects
664 are reclaimed, the garbage collector goes through all string-chars
665 blocks, looking for unused strings. Each chunk of string data is
666 preceded by a pointer to the corresponding `struct Lisp_String', which
667 indicates both whether the string is used and how big the string is,
668 i.e. how to get to the next chunk of string data. Holes are compressed
669 by block-copying the next string into the empty space and relocating the
670 pointer stored in the corresponding `struct Lisp_String'. *This means
671 you have to be careful with strings in your code.* See the section
674 Note that there is one situation not handled: a string that is too
675 big to fit into a string-chars block. Such strings, called "big
676 strings", are all `malloc()'ed as their own block. (#### Although it
677 would make more sense for the threshold for big strings to be somewhat
678 lower, e.g. 1/2 or 1/4 the size of a string-chars block. It seems that
679 this was indeed the case formerly--indeed, the threshold was set at
680 1/8--but Mly forgot about this when rewriting things for 19.8.)
682 Note also that the string data in string-chars blocks is padded as
683 necessary so that proper alignment constraints on the `struct
684 Lisp_String' back pointers are maintained.
686 Finally, strings can be resized. This happens in Mule when a
687 character is substituted with a different-length character, or during
688 modeline frobbing. (You could also export this to Lisp, but it's not
689 done so currently.) Resizing a string is a potentially tricky process.
690 If the change is small enough that the padding can absorb it, nothing
691 other than a simple memory move needs to be done. Keep in mind,
692 however, that the string can't shrink too much because the offset to the
693 next string in the string-chars block is computed by looking at the
694 length and rounding to the nearest multiple of four or eight. If the
695 string would shrink or expand beyond the correct padding, new string
696 data needs to be allocated at the end of the last string-chars block and
697 the data moved appropriately. This leaves some dead string data, which
698 is marked by putting a special marker of 0xFFFFFFFF in the `struct
699 Lisp_String' pointer before the data (there's no real `struct
700 Lisp_String' to point to and relocate), and storing the size of the dead
701 string data (which would normally be obtained from the now-non-existent
702 `struct Lisp_String') at the beginning of the dead string data gap.
703 The string compactor recognizes this special 0xFFFFFFFF marker and
704 handles it correctly.
707 File: internals.info, Node: Compiled Function, Prev: String, Up: Allocation of Objects in XEmacs Lisp
715 File: internals.info, Node: Dumping, Next: Events and the Event Loop, Prev: Allocation of Objects in XEmacs Lisp, Up: Top
720 What is dumping and its justification
721 =====================================
723 The C code of XEmacs is just a Lisp engine with a lot of built-in
724 primitives useful for writing an editor. The editor itself is written
725 mostly in Lisp, and represents around 100K lines of code. Loading and
726 executing the initialization of all this code takes a bit a time (five
727 to ten times the usual startup time of current xemacs) and requires
728 having all the lisp source files around. Having to reload them each
729 time the editor is started would not be acceptable.
731 The traditional solution to this problem is called dumping: the build
732 process first creates the lisp engine under the name `temacs', then
733 runs it until it has finished loading and initializing all the lisp
734 code, and eventually creates a new executable called `xemacs' including
735 both the object code in `temacs' and all the contents of the memory
736 after the initialization.
738 This solution, while working, has a huge problem: the creation of the
739 new executable from the actual contents of memory is an extremely
740 system-specific process, quite error-prone, and which interferes with a
741 lot of system libraries (like malloc). It is even getting worse
742 nowadays with libraries using constructors which are automatically
743 called when the program is started (even before main()) which tend to
744 crash when they are called multiple times, once before dumping and once
745 after (IRIX 6.x libz.so pulls in some C++ image libraries thru
746 dependencies which have this problem). Writing the dumper is also one
747 of the most difficult parts of porting XEmacs to a new operating system.
748 Basically, `dumping' is an operation that is just not officially
749 supported on many operating systems.
751 The aim of the portable dumper is to solve the same problem as the
752 system-specific dumper, that is to be able to reload quickly, using only
753 a small number of files, the fully initialized lisp part of the editor,
754 without any system-specific hacks.
759 * Data descriptions::
765 File: internals.info, Node: Overview, Next: Data descriptions, Prev: Dumping, Up: Dumping
770 The portable dumping system has to:
772 1. At dump time, write all initialized, non-quickly-rebuildable data
773 to a file [Note: currently named `xemacs.dmp', but the name will
774 change], along with all informations needed for the reloading.
776 2. When starting xemacs, reload the dump file, relocate it to its new
777 starting address if needed, and reinitialize all pointers to this
778 data. Also, rebuild all the quickly rebuildable data.
781 File: internals.info, Node: Data descriptions, Next: Dumping phase, Prev: Overview, Up: Dumping
786 The more complex task of the dumper is to be able to write lisp
787 objects (lrecords) and C structs to disk and reload them at a different
788 address, updating all the pointers they include in the process. This
789 is done by using external data descriptions that give information about
790 the layout of the structures in memory.
792 The specification of these descriptions is in lrecord.h. A
793 description of an lrecord is an array of struct lrecord_description.
794 Each of these structs include a type, an offset in the structure and
795 some optional parameters depending on the type. For instance, here is
796 the string description:
798 static const struct lrecord_description string_description[] = {
799 { XD_BYTECOUNT, offsetof (Lisp_String, size) },
800 { XD_OPAQUE_DATA_PTR, offsetof (Lisp_String, data), XD_INDIRECT(0, 1) },
801 { XD_LISP_OBJECT, offsetof (Lisp_String, plist) },
805 The first line indicates a member of type Bytecount, which is used by
806 the next, indirect directive. The second means "there is a pointer to
807 some opaque data in the field `data'". The length of said data is
808 given by the expression `XD_INDIRECT(0, 1)', which means "the value in
809 the 0th line of the description (welcome to C) plus one". The third
810 line means "there is a Lisp_Object member `plist' in the Lisp_String
811 structure". `XD_END' then ends the description.
813 This gives us all the information we need to move around what is
814 pointed to by a structure (C or lrecord) and, by transitivity,
815 everything that it points to. The only missing information for dumping
816 is the size of the structure. For lrecords, this is part of the
817 lrecord_implementation, so we don't need to duplicate it. For C
818 structures we use a struct struct_description, which includes a size
819 field and a pointer to an associated array of lrecord_description.
822 File: internals.info, Node: Dumping phase, Next: Reloading phase, Prev: Data descriptions, Up: Dumping
827 Dumping is done by calling the function pdump() (in dumper.c) which
828 is invoked from Fdump_emacs (in emacs.c). This function performs a
834 * Address allocation::
840 File: internals.info, Node: Object inventory, Next: Address allocation, Prev: Dumping phase, Up: Dumping phase
845 The first task is to build the list of the objects to dump. This
852 We end up with one `pdump_entry_list_elmt' per object group (arrays
853 of C structs are kept together) which includes a pointer to the first
854 object of the group, the per-object size and the count of objects in the
855 group, along with some other information which is initialized later.
857 These entries are linked together in `pdump_entry_list' structures
858 and can be enumerated thru either:
860 1. the `pdump_object_table', an array of `pdump_entry_list', one per
861 lrecord type, indexed by type number.
863 2. the `pdump_opaque_data_list', used for the opaque data which does
864 not include pointers, and hence does not need descriptions.
866 3. the `pdump_struct_table', which is a vector of
867 `struct_description'/`pdump_entry_list' pairs, used for non-opaque
870 This uses a marking strategy similar to the garbage collector. Some
873 1. We do not use the mark bit (which does not exist for C structures
874 anyway), we use a big hash table instead.
876 2. We do not use the mark function of lrecords but instead rely on the
877 external descriptions. This happens essentially because we need to
878 follow pointers to C structures and opaque data in addition to
881 This is done by `pdump_register_object', which handles Lisp_Object
882 variables, and pdump_register_struct which handles C structures, which
883 both delegate the description management to pdump_register_sub.
885 The hash table doubles as a map object to pdump_entry_list_elmt (i.e.
886 allows us to look up a pdump_entry_list_elmt with the object it points
887 to). Entries are added with `pdump_add_entry()' and looked up with
888 `pdump_get_entry()'. There is no need for entry removal. The hash
889 value is computed quite basically from the object pointer by
892 The roots for the marking are:
894 1. the `staticpro''ed variables (there is a special
895 `staticpro_nodump()' call for protected variables we do not want
898 2. the `pdump_wire''d variables (`staticpro' is equivalent to
899 `staticpro_nodump()' + `pdump_wire()').
901 3. the `dumpstruct''ed variables, which points to C structures.
903 This does not include the GCPRO'ed variables, the specbinds, the
904 catchtags, the backlist, the redisplay or the profiling info, since we
905 do not want to rebuild the actual chain of lisp calls which end up to
906 the dump-emacs call, only the global variables.
908 Weak lists and weak hash tables are dumped as if they were their
909 non-weak equivalent (without changing their type, of course). This has
910 not yet been a problem.
913 File: internals.info, Node: Address allocation, Next: The header, Prev: Object inventory, Up: Dumping phase
918 The next step is to allocate the offsets of each of the objects in
919 the final dump file. This is done by `pdump_allocate_offset()' which
920 is called indirectly by `pdump_scan_by_alignment()'.
922 The strategy to deal with alignment problems uses these facts:
924 1. real world alignment requirements are powers of two.
926 2. the C compiler is required to adjust the size of a struct so that
927 you can have an array of them next to each other. This means you
928 can have a upper bound of the alignment requirements of a given
929 structure by looking at which power of two its size is a multiple.
931 3. the non-variant part of variable size lrecords has an alignment
934 Hence, for each lrecord type, C struct type or opaque data block the
935 alignment requirement is computed as a power of two, with a minimum of
936 2^2 for lrecords. `pdump_scan_by_alignment()' then scans all the
937 `pdump_entry_list_elmt''s, the ones with the highest requirements
938 first. This ensures the best packing.
940 The maximum alignment requirement we take into account is 2^8.
942 `pdump_allocate_offset()' only has to do a linear allocation,
943 starting at offset 256 (this leaves room for the header and keep the
947 File: internals.info, Node: The header, Next: Data dumping, Prev: Address allocation, Up: Dumping phase
952 The next step creates the file and writes a header with a signature
953 and some random informations in it (number of staticpro, number of
954 assigned lrecord types, etc...). The reloc_address field, which
955 indicates at which address the file should be loaded if we want to
956 avoid post-reload relocation, is set to 0. It then seeks to offset 256
957 (base offset for the objects).
960 File: internals.info, Node: Data dumping, Next: Pointers dumping, Prev: The header, Up: Dumping phase
965 The data is dumped in the same order as the addresses were allocated
966 by `pdump_dump_data()', called from `pdump_scan_by_alignment()'. This
967 function copies the data to a temporary buffer, relocates all pointers
968 in the object to the addresses allocated in step Address Allocation,
969 and writes it to the file. Using the same order means that, if we are
970 careful with lrecords whose size is not a multiple of 4, we are ensured
971 that the object is always written at the offset in the file allocated
972 in step Address Allocation.
975 File: internals.info, Node: Pointers dumping, Prev: Data dumping, Up: Dumping phase
980 A bunch of tables needed to reassign properly the global pointers are
981 then written. They are:
983 1. the staticpro array
985 2. the dumpstruct array
987 3. the lrecord_implementation_table array
989 4. a vector of all the offsets to the objects in the file that
990 include a description (for faster relocation at reload time)
992 5. the pdump_wired and pdump_wired_list arrays
994 For each of the arrays we write both the pointer to the variables and
995 the relocated offset of the object they point to. Since these variables
996 are global, the pointers are still valid when restarting the program and
997 are used to regenerate the global pointers.
999 The `pdump_wired_list' array is a special case. The variables it
1000 points to are the head of weak linked lists of lisp objects of the same
1001 type. Not all objects of this list are dumped so the relocated pointer
1002 we associate with them points to the first dumped object of the list, or
1003 Qnil if none is available. This is also the reason why they are not
1004 used as roots for the purpose of object enumeration.
1006 This is the end of the dumping part.
1009 File: internals.info, Node: Reloading phase, Next: Remaining issues, Prev: Dumping phase, Up: Dumping
1017 The file is mmap'ed in memory (which ensures a PAGESIZE alignment, at
1018 least 4096), or if mmap is unavailable or fails, a 256-bytes aligned
1019 malloc is done and the file is loaded.
1021 Some variables are reinitialized from the values found in the header.
1023 The difference between the actual loading address and the
1024 reloc_address is computed and will be used for all the relocations.
1026 Putting back the staticvec
1027 --------------------------
1029 The staticvec array is memcpy'd from the file and the variables it
1030 points to are reset to the relocated objects addresses.
1032 Putting back the dumpstructed variables
1033 ---------------------------------------
1035 The variables pointed to by dumpstruct in the dump phase are reset to
1036 the right relocated object addresses.
1038 lrecord_implementations_table
1039 -----------------------------
1041 The lrecord_implementations_table is reset to its dump time state and
1042 the right lrecord_type_index values are put in.
1047 All the objects are relocated using their description and their
1048 offset by `pdump_reloc_one'. This step is unnecessary if the
1049 reloc_address is equal to the file loading address.
1051 Putting back the pdump_wire and pdump_wire_list variables
1052 ---------------------------------------------------------
1054 Same as Putting back the dumpstructed variables.
1056 Reorganize the hash tables
1057 --------------------------
1059 Since some of the hash values in the lisp hash tables are
1060 address-dependent, their layout is now wrong. So we go through each of
1061 them and have them resorted by calling `pdump_reorganize_hash_table'.
1064 File: internals.info, Node: Remaining issues, Prev: Reloading phase, Up: Dumping
1069 The build process will have to start a post-dump xemacs, ask it the
1070 loading address (which will, hopefully, be always the same between
1071 different xemacs invocations) and relocate the file to the new address.
1072 This way the object relocation phase will not have to be done, which
1073 means no writes in the objects and that, because of the use of mmap, the
1074 dumped data will be shared between all the xemacs running on the
1077 Some executable signature will be necessary to ensure that a given
1078 dump file is really associated with a given executable, or random
1079 crashes will occur. Maybe a random number set at compile or configure
1080 time thru a define. This will also allow for having
1081 differently-compiled xemacsen on the same system (mule and no-mule
1084 The DOC file contents should probably end up in the dump file.
1087 File: internals.info, Node: Events and the Event Loop, Next: Evaluation; Stack Frames; Bindings, Prev: Dumping, Up: Top
1089 Events and the Event Loop
1090 *************************
1094 * Introduction to Events::
1096 * Specifics of the Event Gathering Mechanism::
1097 * Specifics About the Emacs Event::
1098 * The Event Stream Callback Routines::
1099 * Other Event Loop Functions::
1100 * Converting Events::
1101 * Dispatching Events; The Command Builder::
projects / chise / xemacs-chise.git- / blob