+
+@node Dumping, Events and the Event Loop, Allocation of Objects in XEmacs Lisp, Top
+@chapter Dumping
+@cindex dumping
+
+@section What is dumping and its justification
+@cindex dumping and its justification, what is
+
+The C code of XEmacs is just a Lisp engine with a lot of built-in
+primitives useful for writing an editor. The editor itself is written
+mostly in Lisp, and represents around 100K lines of code. Loading and
+executing the initialization of all this code takes a bit a time (five
+to ten times the usual startup time of current xemacs) and requires
+having all the lisp source files around. Having to reload them each
+time the editor is started would not be acceptable.
+
+The traditional solution to this problem is called dumping: the build
+process first creates the lisp engine under the name @file{temacs}, then
+runs it until it has finished loading and initializing all the lisp
+code, and eventually creates a new executable called @file{xemacs}
+including both the object code in @file{temacs} and all the contents of
+the memory after the initialization.
+
+This solution, while working, has a huge problem: the creation of the
+new executable from the actual contents of memory is an extremely
+system-specific process, quite error-prone, and which interferes with a
+lot of system libraries (like malloc). It is even getting worse
+nowadays with libraries using constructors which are automatically
+called when the program is started (even before main()) which tend to
+crash when they are called multiple times, once before dumping and once
+after (IRIX 6.x libz.so pulls in some C++ image libraries thru
+dependencies which have this problem). Writing the dumper is also one
+of the most difficult parts of porting XEmacs to a new operating system.
+Basically, `dumping' is an operation that is just not officially
+supported on many operating systems.
+
+The aim of the portable dumper is to solve the same problem as the
+system-specific dumper, that is to be able to reload quickly, using only
+a small number of files, the fully initialized lisp part of the editor,
+without any system-specific hacks.
+
+@menu
+* Overview::
+* Data descriptions::
+* Dumping phase::
+* Reloading phase::
+* Remaining issues::
+@end menu
+
+@node Overview
+@section Overview
+@cindex dumping overview
+
+The portable dumping system has to:
+
+@enumerate
+@item
+At dump time, write all initialized, non-quickly-rebuildable data to a
+file [Note: currently named @file{xemacs.dmp}, but the name will
+change], along with all informations needed for the reloading.
+
+@item
+When starting xemacs, reload the dump file, relocate it to its new
+starting address if needed, and reinitialize all pointers to this
+data. Also, rebuild all the quickly rebuildable data.
+@end enumerate
+
+@node Data descriptions
+@section Data descriptions
+@cindex dumping data descriptions
+
+The more complex task of the dumper is to be able to write lisp objects
+(lrecords) and C structs to disk and reload them at a different address,
+updating all the pointers they include in the process. This is done by
+using external data descriptions that give information about the layout
+of the structures in memory.
+
+The specification of these descriptions is in lrecord.h. A description
+of an lrecord is an array of struct lrecord_description. Each of these
+structs include a type, an offset in the structure and some optional
+parameters depending on the type. For instance, here is the string
+description:
+
+@example
+static const struct lrecord_description string_description[] = @{
+ @{ XD_BYTECOUNT, offsetof (Lisp_String, size) @},
+ @{ XD_OPAQUE_DATA_PTR, offsetof (Lisp_String, data), XD_INDIRECT(0, 1) @},
+ @{ XD_LISP_OBJECT, offsetof (Lisp_String, plist) @},
+ @{ XD_END @}
+@};
+@end example
+
+The first line indicates a member of type Bytecount, which is used by
+the next, indirect directive. The second means "there is a pointer to
+some opaque data in the field @code{data}". The length of said data is
+given by the expression @code{XD_INDIRECT(0, 1)}, which means "the value
+in the 0th line of the description (welcome to C) plus one". The third
+line means "there is a Lisp_Object member @code{plist} in the Lisp_String
+structure". @code{XD_END} then ends the description.
+
+This gives us all the information we need to move around what is pointed
+to by a structure (C or lrecord) and, by transitivity, everything that
+it points to. The only missing information for dumping is the size of
+the structure. For lrecords, this is part of the
+lrecord_implementation, so we don't need to duplicate it. For C
+structures we use a struct struct_description, which includes a size
+field and a pointer to an associated array of lrecord_description.
+
+@node Dumping phase
+@section Dumping phase
+@cindex dumping phase
+
+Dumping is done by calling the function pdump() (in dumper.c) which is
+invoked from Fdump_emacs (in emacs.c). This function performs a number
+of tasks.
+
+@menu
+* Object inventory::
+* Address allocation::
+* The header::
+* Data dumping::
+* Pointers dumping::
+@end menu
+
+@node Object inventory
+@subsection Object inventory
+@cindex dumping object inventory
+
+The first task is to build the list of the objects to dump. This
+includes:
+
+@itemize @bullet
+@item lisp objects
+@item C structures
+@end itemize
+
+We end up with one @code{pdump_entry_list_elmt} per object group (arrays
+of C structs are kept together) which includes a pointer to the first
+object of the group, the per-object size and the count of objects in the
+group, along with some other information which is initialized later.
+
+These entries are linked together in @code{pdump_entry_list} structures
+and can be enumerated thru either:
+
+@enumerate
+@item
+the @code{pdump_object_table}, an array of @code{pdump_entry_list}, one
+per lrecord type, indexed by type number.
+
+@item
+the @code{pdump_opaque_data_list}, used for the opaque data which does
+not include pointers, and hence does not need descriptions.
+
+@item
+the @code{pdump_struct_table}, which is a vector of
+@code{struct_description}/@code{pdump_entry_list} pairs, used for
+non-opaque C structures.
+@end enumerate
+
+This uses a marking strategy similar to the garbage collector. Some
+differences though:
+
+@enumerate
+@item
+We do not use the mark bit (which does not exist for C structures
+anyway); we use a big hash table instead.
+
+@item
+We do not use the mark function of lrecords but instead rely on the
+external descriptions. This happens essentially because we need to
+follow pointers to C structures and opaque data in addition to
+Lisp_Object members.
+@end enumerate
+
+This is done by @code{pdump_register_object()}, which handles Lisp_Object
+variables, and @code{pdump_register_struct()} which handles C structures,
+which both delegate the description management to @code{pdump_register_sub()}.
+
+The hash table doubles as a map object to pdump_entry_list_elmt (i.e.
+allows us to look up a pdump_entry_list_elmt with the object it points
+to). Entries are added with @code{pdump_add_entry()} and looked up with
+@code{pdump_get_entry()}. There is no need for entry removal. The hash
+value is computed quite simply from the object pointer by
+@code{pdump_make_hash()}.
+
+The roots for the marking are:
+
+@enumerate
+@item
+the @code{staticpro}'ed variables (there is a special @code{staticpro_nodump()}
+call for protected variables we do not want to dump).
+
+@item
+the variables registered via @code{dump_add_root_object}
+(@code{staticpro()} is equivalent to @code{staticpro_nodump()} +
+@code{dump_add_root_object()}).
+
+@item
+the variables registered via @code{dump_add_root_struct_ptr}, each of
+which points to a C structure.
+@end enumerate
+
+This does not include the GCPRO'ed variables, the specbinds, the
+catchtags, the backlist, the redisplay or the profiling info, since we
+do not want to rebuild the actual chain of lisp calls which end up to
+the dump-emacs call, only the global variables.
+
+Weak lists and weak hash tables are dumped as if they were their
+non-weak equivalent (without changing their type, of course). This has
+not yet been a problem.
+
+@node Address allocation
+@subsection Address allocation
+@cindex dumping address allocation
+
+
+The next step is to allocate the offsets of each of the objects in the
+final dump file. This is done by @code{pdump_allocate_offset()} which
+is called indirectly by @code{pdump_scan_by_alignment()}.
+
+The strategy to deal with alignment problems uses these facts:
+
+@enumerate
+@item
+real world alignment requirements are powers of two.
+
+@item
+the C compiler is required to adjust the size of a struct so that you
+can have an array of them next to each other. This means you can have an
+upper bound of the alignment requirements of a given structure by
+looking at which power of two its size is a multiple.
+
+@item
+the non-variant part of variable size lrecords has an alignment
+requirement of 4.
+@end enumerate
+
+Hence, for each lrecord type, C struct type or opaque data block the
+alignment requirement is computed as a power of two, with a minimum of
+2^2 for lrecords. @code{pdump_scan_by_alignment()} then scans all the
+@code{pdump_entry_list_elmt}'s, the ones with the highest requirements
+first. This ensures the best packing.
+
+The maximum alignment requirement we take into account is 2^8.
+
+@code{pdump_allocate_offset()} only has to do a linear allocation,
+starting at offset 256 (this leaves room for the header and keeps the
+alignments happy).
+
+@node The header
+@subsection The header
+@cindex dumping, the header
+
+The next step creates the file and writes a header with a signature and
+some random information in it. The @code{reloc_address} field, which
+indicates at which address the file should be loaded if we want to avoid
+post-reload relocation, is set to 0. It then seeks to offset 256 (base
+offset for the objects).
+
+@node Data dumping
+@subsection Data dumping
+@cindex data dumping
+@cindex dumping, data
+
+The data is dumped in the same order as the addresses were allocated by
+@code{pdump_dump_data()}, called from @code{pdump_scan_by_alignment()}.
+This function copies the data to a temporary buffer, relocates all
+pointers in the object to the addresses allocated in step Address
+Allocation, and writes it to the file. Using the same order means that,
+if we are careful with lrecords whose size is not a multiple of 4, we
+are ensured that the object is always written at the offset in the file
+allocated in step Address Allocation.
+
+@node Pointers dumping
+@subsection Pointers dumping
+@cindex pointers dumping
+@cindex dumping, pointers
+
+A bunch of tables needed to reassign properly the global pointers are
+then written. They are:
+
+@enumerate
+@item
+the pdump_root_struct_ptrs dynarr
+@item
+the pdump_opaques dynarr
+@item
+a vector of all the offsets to the objects in the file that include a
+description (for faster relocation at reload time)
+@item
+the pdump_root_objects and pdump_weak_object_chains dynarrs.
+@end enumerate
+
+For each of the dynarrs we write both the pointer to the variables and
+the relocated offset of the object they point to. Since these variables
+are global, the pointers are still valid when restarting the program and
+are used to regenerate the global pointers.
+
+The @code{pdump_weak_object_chains} dynarr is a special case. The
+variables it points to are the head of weak linked lists of lisp objects
+of the same type. Not all objects of this list are dumped so the
+relocated pointer we associate with them points to the first dumped
+object of the list, or Qnil if none is available. This is also the
+reason why they are not used as roots for the purpose of object
+enumeration.
+
+Some very important information like the @code{staticpros} and
+@code{lrecord_implementations_table} are handled indirectly using
+@code{dump_add_opaque} or @code{dump_add_root_struct_ptr}.
+
+This is the end of the dumping part.
+
+@node Reloading phase
+@section Reloading phase
+@cindex reloading phase
+@cindex dumping, reloading phase
+
+@subsection File loading
+@cindex dumping, file loading
+
+The file is mmap'ed in memory (which ensures a PAGESIZE alignment, at
+least 4096), or if mmap is unavailable or fails, a 256-bytes aligned
+malloc is done and the file is loaded.
+
+Some variables are reinitialized from the values found in the header.
+
+The difference between the actual loading address and the reloc_address
+is computed and will be used for all the relocations.
+
+
+@subsection Putting back the pdump_opaques
+@cindex dumping, putting back the pdump_opaques
+
+The memory contents are restored in the obvious and trivial way.
+
+
+@subsection Putting back the pdump_root_struct_ptrs
+@cindex dumping, putting back the pdump_root_struct_ptrs
+
+The variables pointed to by pdump_root_struct_ptrs in the dump phase are
+reset to the right relocated object addresses.
+
+
+@subsection Object relocation
+@cindex dumping, object relocation
+
+All the objects are relocated using their description and their offset
+by @code{pdump_reloc_one}. This step is unnecessary if the
+reloc_address is equal to the file loading address.
+
+
+@subsection Putting back the pdump_root_objects and pdump_weak_object_chains
+@cindex dumping, putting back the pdump_root_objects and pdump_weak_object_chains
+
+Same as Putting back the pdump_root_struct_ptrs.
+
+
+@subsection Reorganize the hash tables
+@cindex dumping, reorganize the hash tables
+
+Since some of the hash values in the lisp hash tables are
+address-dependent, their layout is now wrong. So we go through each of
+them and have them resorted by calling @code{pdump_reorganize_hash_table}.
+
+@node Remaining issues
+@section Remaining issues
+@cindex dumping, remaining issues
+
+The build process will have to start a post-dump xemacs, ask it the
+loading address (which will, hopefully, be always the same between
+different xemacs invocations) and relocate the file to the new address.
+This way the object relocation phase will not have to be done, which
+means no writes in the objects and that, because of the use of mmap, the
+dumped data will be shared between all the xemacs running on the
+computer.
+
+Some executable signature will be necessary to ensure that a given dump
+file is really associated with a given executable, or random crashes
+will occur. Maybe a random number set at compile or configure time thru
+a define. This will also allow for having differently-compiled xemacsen
+on the same system (mule and no-mule comes to mind).
+
+The DOC file contents should probably end up in the dump file.
+
+
+@node Events and the Event Loop, Evaluation; Stack Frames; Bindings, Dumping, Top