README.txt

   1 'Ancient' module for OCaml
   2 ----------------------------------------------------------------------
   3
   4 What does this module do?
   5 ----------------------------------------------------------------------
   6
   7 This module allows you to use in-memory data structures which are
   8 larger than available memory and so are kept in swap.  If you try this
   9 in normal OCaml code, you'll find that the machine quickly descends
  10 into thrashing as the garbage collector repeatedly iterates over
  11 swapped memory structures.  This module lets you break that
  12 limitation.  Of course the module doesn't work by magic :-) If your
  13 program tries to access these large structures, they still need to be
  14 swapped back in, but it is suitable for large, sparsely accessed
  15 structures.
  16
  17 Secondly, this module allows you to share those structures between
  18 processes.  In this mode, the structures are backed by a disk file,
  19 and any process that has read/write access that disk file can map that
  20 file in and see the structures.
  21
  22 To understand what this module really does, you need to know a little
  23 bit of background about the OCaml garbage collector (GC).  OCaml's GC
  24 has two heaps, called the minor and major heaps.  The minor heap is
  25 used for short-term storage of small objects which are usually created
  26 and then quickly become unreachable.  Any objects which persist longer
  27 (or objects which are very big to start with) get moved into the major
  28 heap.  Objects in the major heap are assumed to be around for some
  29 time, and the major heap is GC'd more slowly.
  30
  31 This module adds a third heap, called the "ancient heap", which is
  32 never checked by the GC.  Objects must be moved into ancient manually,
  33 using a process called "marking".  Once an object is in the ancient
  34 heap, memory allocation is handled manually.  In particular objects in
  35 the ancient heap may need to be manually deallocated.  The ancient
  36 heap may either exist as ordinary memory, or may be backed by a file,
  37 which is how shared structures are possible.
  38
  39 Structures which are moved into ancient must be treated as STRICTLY
  40 NON-MUTABLE.  If an ancient structure is changed in any way then it
  41 may cause a crash.
  42
  43 There are some limitations which apply to ancient data structures.
  44 See the section "Shortcomings & bugs" below.
  45
  46 This module is most useful on 64 bit architectures where large address
  47 spaces are the norm.  We have successfully used it with a 38 GB
  48 address space backed by a file and shared between processes.
  49
  50 API
  51 ----------------------------------------------------------------------
  52
  53 Please see file ancient.mli .
  54
  55 Compiling
  56 ----------------------------------------------------------------------
  57
  58   cd mmalloc && ./configure
  59   make
  60
  61 Make sure you run this command before running any program which
  62 uses the Ancient module:
  63
  64   ulimit -s unlimited
  65
  66 Example
  67 ----------------------------------------------------------------------
  68
  69 XXX Note the example code is really stupid, and fails for large
  70 dictionaries.  See bug (10) below.
  71
  72 Run:
  73
  74   ulimit -s unlimited
  75   wordsfile=/usr/share/dict/words
  76   baseaddr=0x440000000000               # System specific - see below.
  77   ./test_ancient_dict_write.opt $wordsfile dictionary.data $baseaddr
  78   ./test_ancient_dict_verify.opt $wordsfile dictionary.data
  79   ./test_ancient_dict_read.opt dictionary.data
  80
  81 (You can run several instances of test_ancient_dict_read.opt on the
  82 same machine to demonstrate sharing).
  83
  84 Shortcomings & bugs
  85 ----------------------------------------------------------------------
  86
  87 (0) Stack overflows are common when marking/sharing large structures
  88 because we use a recursive algorithm to visit the structures.  If you
  89 get random segfaults during marking/sharing, then try this before
  90 running your program:
  91
  92   ulimit -s unlimited
  93
  94 (1) Ad-hoc polymorphic primitives (structural equality, marshalling
  95 and hashing) do not work on ancient data structures, meaning that you
  96 will need to provide your own comparison and hashing functions.  For
  97 more details see Xavier Leroy's response here:
  98
  99 http://caml.inria.fr/pub/ml-archives/caml-list/2006/09/977818689f4ceb2178c592453df7a343.en.html
 100
 101 (2) Ancient.attach suggests setting a baseaddr parameter for newly
 102 created files (it has no effect when attaching existing files).  We
 103 strongly recommend this because in our tests we found that mmap would
 104 locate the memory segment inappropriately -- the basic problem is that
 105 because the file starts off with zero length, mmap thinks it can place
 106 it anywhere in memory and often does not leave it room to grow upwards
 107 without overwriting later memory mappings.  Unfortunately this
 108 introduces an unwanted architecture dependency in all programs which
 109 use the Ancient module with shared files, and it also requires
 110 programmers to guess at a good base address which will be valid in the
 111 future.  There are no other good solutions we have found --
 112 preallocating the file is tricky with the current mmalloc code.
 113
 114 (3) The current code requires you to first of all create the large
 115 data structures on the regular OCaml heap, then mark them as ancient,
 116 effectively copying them out of the OCaml heap, then garbage collect
 117 the (hopefully unreferenced) structures on the OCaml heap.  In other
 118 words, you need to have all the memory available as physical memory.
 119 The way to avoid this is to mark structures as ancient incrementally
 120 as they are created, or in chunks, whatever works for you.
 121
 122 We typically use Ancient to deal with web server logfiles, and in this
 123 case loading one file of data into memory and marking it as ancient
 124 before moving on to the next file works for us.
 125
 126 (4) Why do ancient structures need to be read-only / not mutated?  The
 127 reason is that you might create a new OCaml heap structure and point
 128 the ancient structure at this heap structure.  The heap structure has
 129 no apparent incoming pointers (the GC will not by its very nature
 130 check the ancient structure for pointers), and so the heap structure
 131 gets garbage collected.  At this point the ancient structure has a
 132 dangling pointer, which will usually result in some form of crash.
 133 Note that the restriction here is on creating pointers from ancient
 134 data to OCaml heap data.  In theory it should be possible to modify
 135 ancient data to point to other ancient data, but we have not tried
 136 this.
 137
 138 (5) [Limit on number of keys -- issue fixed]
 139
 140 (6) [Advanced topic] The _mark function in ancient_c.c makes no
 141 attempt to arrange the data structures in memory / on disk in a way
 142 which optimises them for access.  The worst example is when you have
 143 an array of large structures, where only a few fields in the structure
 144 will be accessed.  Typically these will end up on disk as:
 145
 146   array of N pointers
 147   structure 1
 148   field A
 149   field B
 150     ...
 151   field Z
 152   structure 2
 153   field A
 154   field B
 155     ...
 156   field Z
 157   structure 3
 158   field A
 159   field B
 160     ...
 161   field Z
 162    ...
 163    ...
 164    ...
 165   structure N
 166   field A
 167   field B
 168     ...
 169   field Z
 170
 171 If you then iterate accessing only fields A, you end up swapping the
 172 whole lot back into memory.  A better arrangement would have been:
 173
 174   array of N pointers
 175   structure 1
 176   structure 2
 177   structure 3
 178     ...
 179   structure N
 180   field A from structure 1
 181   field A from structure 2
 182   field A from structure 3
 183     ...
 184   field A from structure N
 185   field B from structure 1
 186   field B from structure 2
 187     etc.
 188
 189 which avoids loading unused fields at all.  In some circumstances we
 190 have shown that this could make a huge difference to performance, but
 191 we are not sure how to implement this cleanly in the current library.
 192
 193 [Update: I have fixed issue 6 manually for my Weblogs example and
 194 confirmed that it does make a huge difference to performance, although
 195 at considerable extra code complexity.  Interested people can see the
 196 weblogs library, file import_weblogs_ancient.ml.in].
 197
 198 (7) [Advanced topic] Certain techniques such as Address Space
 199 Randomisation (http://lwn.net/Articles/121845/) are probably not
 200 compatible with the Ancient module and shared files.  Because the
 201 ancient data structures contain real pointers, these pointers would be
 202 invalidated if the shared file was not mapped in at precisely the same
 203 base address in all processes which are sharing the file.
 204
 205 One solution might be to use private mappings and a list of fixups.
 206 In fact, the code actually builds a list of fixups currently while
 207 marking, because it needs to deal with precisely this issue (during
 208 marking, memory is allocated with realloc which might move the memory
 209 segment, thus real pointers cannot be stored while marking, but need
 210 to be fixed up afterwards).  The list of fixups would need to be
 211 stored alongside the memory segment (currently it is discarded after
 212 marking), and the file would need to be mapped in using MAP_PRIVATE
 213 (see below).
 214
 215 A possible problem with this is that because OCaml objects tend to be
 216 small and contain a lot of pointers, it is likely that fixing up the
 217 pointers would result in every page in the memory segment becoming
 218 dirty, which would basically cancel out any benefit of using shared
 219 mappings in the first place.  However it is likely that some users of
 220 this module have large amounts of opaque data and few pointers, and
 221 for them this would be worthwhile.
 222
 223 (8) Currently mmalloc is implemented so that the file is mapped in
 224 PROT_READ|PROT_WRITE and MAP_SHARED.  Ancient data structures are
 225 supposed to be immutable so strictly speaking write access shouldn't
 226 be required.  It may be worthwhile modifying mmalloc to allow
 227 read-only mappings, and private mappings.
 228
 229 (9) The library assumes that every OCaml object is at least one word
 230 long.  This seemed like a good assumption up until I found that
 231 zero-length arrays are valid zero word objects.  At the moment you
 232 cannot mark structures which contain zero-length arrays -- you will
 233 get an assert-failure in the _mark function.
 234
 235 Possibly there are other types of OCaml structure which are zero word
 236 objects and also cannot be marked.  I'm not sure what these will be:
 237 for example empty strings are stored as one word OCaml objects, so
 238 they are OK.
 239
 240 The solution to this bug is non-trivial.
 241
 242 (10) Example code is very stupid.  It fails with large dictionaries,
 243 eg. the one with nearly 500,000 words found in Fedora.
 244
 245 (11) In function 'mark', the "// Ran out of memory.  Recover and throw
 246 an exception." codepath actually fails if you use it - segfaulting
 247 inside do_restore.
 248
 249 Authors
 250 ----------------------------------------------------------------------
 251
 252 Primary code was written by Richard W.M. Jones <rich at annexia.org>
 253 with help from Markus Mottl, Martin Jambon, and invaluable advice from
 254 Xavier Leroy and Damien Doligez.
 255
 256 mmalloc was written by Mike Haertel and Fred Fish.
 257
 258 License
 259 ----------------------------------------------------------------------
 260
 261 The module is licensed under the LGPL + OCaml linking exception.  This
 262 module includes mmalloc which was originally distributed with gdb
 263 (although it has since been removed), and that code was distributed
 264 under the plain LGPL.
 265
 266 Latest version
 267 ----------------------------------------------------------------------
 268
 269 The latest version can be found on the website:
 270 http://merjis.com/developers/ancient