README.txt

   1 'Ancient' module for OCaml
   2 ----------------------------------------------------------------------
   3 $Id: README.txt,v 1.1 2006-10-06 15:03:47 rich Exp $
   4
   5 What does this module do?
   6 ----------------------------------------------------------------------
   7
   8 This module allows you to use in-memory data structures which are
   9 larger than available memory and so are kept in swap.  If you try this
  10 in normal OCaml code, you'll find that the machine quickly descends
  11 into thrashing as the garbage collector repeatedly iterates over
  12 swapped memory structures.  This module lets you break that
  13 limitation.  Of course the module doesn't work by magic :-) If your
  14 program tries to access these large structures, they still need to be
  15 swapped back in, but it is suitable for large, sparsely accessed
  16 structures.
  17
  18 Secondly, this module allows you to share those structures between
  19 processes.  In this mode, the structures are backed by a disk file,
  20 and any process that has read/write access that disk file can map that
  21 file in and see the structures.
  22
  23 To understand what this module really does, you need to know a little
  24 bit of background about the OCaml garbage collector (GC).  OCaml's GC
  25 has two heaps, called the minor and major heaps.  The minor heap is
  26 used for short-term storage of small objects which are usually created
  27 and then quickly become unreachable.  Any objects which persist longer
  28 (or objects which are very big to start with) get moved into the major
  29 heap.  Objects in the major heap are assumed to be around for some
  30 time, and the major heap is GC'd more slowly.
  31
  32 This module adds a third heap, called the "ancient heap", which is
  33 never checked by the GC.  Objects must be moved into ancient manually,
  34 using a process called "marking".  Once an object is in the ancient
  35 heap, memory allocation is handled manually.  In particular objects in
  36 the ancient heap may need to be manually deallocated.  The ancient
  37 heap may either exist as ordinary memory, or may be backed by a file,
  38 which is how shared structures are possible.
  39
  40 Structures which are moved into ancient must be treated as STRICTLY
  41 NON-MUTABLE.  If an ancient structure is changed in any way then it
  42 may cause a crash.
  43
  44 There are some limitations which apply to ancient data structures.
  45 See the section "Shortcomings & bugs" below.
  46
  47 This module is most useful on 64 bit architectures where large address
  48 spaces are the norm.  We have successfully used it with a 38 GB
  49 address space backed by a file and shared between processes.
  50
  51 API
  52 ----------------------------------------------------------------------
  53
  54 Please see file ancient.mli .
  55
  56 Compiling
  57 ----------------------------------------------------------------------
  58
  59   cd mmalloc && ./configure
  60   make
  61
  62 Make sure you run this command before running any program which
  63 uses the Ancient module:
  64
  65   ulimit -s unlimited
  66
  67 Example
  68 ----------------------------------------------------------------------
  69
  70 Run:
  71
  72   ulimit -s unlimited
  73   wordsfile=/usr/share/dict/words
  74   baseaddr=0x440000000000               # System specific - see below.
  75   ./test_ancient_dict_write.opt $wordsfile dictionary.data $baseaddr
  76   ./test_ancient_dict_verify.opt $wordsfile dictionary.data
  77   ./test_ancient_dict_read.opt dictionary.data
  78
  79 (You can run several instances of test_ancient_dict_read.opt on the
  80 same machine to demonstrate sharing).
  81
  82 Shortcomings & bugs
  83 ----------------------------------------------------------------------
  84
  85 (0) Stack overflows are common when marking/sharing large structures
  86 because we use a recursive algorithm to visit the structures.  If you
  87 get random segfaults during marking/sharing, then try this before
  88 running your program:
  89
  90   ulimit -s unlimited
  91
  92 (1) Ad-hoc polymorphic primitives (structural equality, marshalling
  93 and hashing) do not work on ancient data structures, meaning that you
  94 will need to provide your own comparison and hashing functions.  For
  95 more details see Xavier Leroy's response here:
  96
  97 http://caml.inria.fr/pub/ml-archives/caml-list/2006/09/977818689f4ceb2178c592453df7a343.en.html
  98
  99 (2) Ancient.attach suggests setting a baseaddr parameter for newly
 100 created files (it has no effect when attaching existing files).  We
 101 strongly recommend this because in our tests we found that mmap would
 102 locate the memory segment inappropriately -- the basic problem is that
 103 because the file starts off with zero length, mmap thinks it can place
 104 it anywhere in memory and often does not leave it room to grow upwards
 105 without overwriting later memory mappings.  Unfortunately this
 106 introduces an unwanted architecture dependency in all programs which
 107 use the Ancient module with shared files, and it also requires
 108 programmers to guess at a good base address which will be valid in the
 109 future.  There are no other good solutions we have found --
 110 preallocating the file is tricky with the current mmalloc code.
 111
 112 (3) The current code requires you to first of all create the large
 113 data structures on the regular OCaml heap, then mark them as ancient,
 114 effectively copying them out of the OCaml heap, then garbage collect
 115 the (hopefully unreferenced) structures on the OCaml heap.  In other
 116 words, you need to have all the memory available as physical memory.
 117 The way to avoid this is to mark structures as ancient incrementally
 118 as they are created, or in chunks, whatever works for you.
 119
 120 We typically use Ancient to deal with web server logfiles, and in this
 121 case loading one file of data into memory and marking it as ancient
 122 before moving on to the next file works for us.
 123
 124 (4) Why do ancient structures need to be read-only / not mutated?  The
 125 reason is that you might create a new OCaml heap structure and point
 126 the ancient structure at this heap structure.  The heap structure has
 127 no apparent incoming pointers (the GC will not by its very nature
 128 check the ancient structure for pointers), and so the heap structure
 129 gets garbage collected.  At this point the ancient structure has a
 130 dangling pointer, which will usually result in some form of crash.
 131 Note that the restriction here is on creating pointers from ancient
 132 data to OCaml heap data.  In theory it should be possible to modify
 133 ancient data to point to other ancient data, but we have not tried
 134 this.
 135
 136 (5) You can store more than just one compound object per backing file
 137 by supplying a key to Ancient.share and Ancient.get.  The keys are
 138 integers in the range [0..1023].  The upper limit is hard coded into
 139 the mmalloc library.  This hard coded upper limit is a bug which
 140 should be fixed.
 141
 142 (6) [Advanced topic] The _mark function in ancient_c.c makes no
 143 attempt to arrange the data structures in memory / on disk in a way
 144 which optimises them for access.  The worst example is when you have
 145 an array of large structures, where only a few fields in the structure
 146 will be accessed.  Typically these will end up on disk as:
 147
 148   array of N pointers
 149   structure 1
 150   field A
 151   field B
 152     ...
 153   field Z
 154   structure 2
 155   field A
 156   field B
 157     ...
 158   field Z
 159   structure 3
 160   field A
 161   field B
 162     ...
 163   field Z
 164    ...
 165    ...
 166    ...
 167   structure N
 168   field A
 169   field B
 170     ...
 171   field Z
 172
 173 If you then iterate accessing only fields A, you end up swapping the
 174 whole lot back into memory.  A better arrangement would have been:
 175
 176   array of N pointers
 177   structure 1
 178   structure 2
 179   structure 3
 180     ...
 181   structure N
 182   field A from structure 1
 183   field A from structure 2
 184   field A from structure 3
 185     ...
 186   field A from structure N
 187   field B from structure 1
 188   field B from structure 2
 189     etc.
 190
 191 which avoids loading unused fields at all.  In some circumstances we
 192 have shown that this could make a huge difference to performance, but
 193 we are not sure how to implement this cleanly in the current library.
 194
 195 Authors
 196 ----------------------------------------------------------------------
 197
 198 Primary code was written by Richard W.M. Jones <rich at annexia.org>
 199 with help from Markus Mottl, Martin Jambon, and invaluable advice from
 200 Xavier Leroy and Damien Doligez.
 201
 202 mmalloc was written by Mike Haertel and Fred Fish.
 203
 204 License
 205 ----------------------------------------------------------------------
 206
 207 The module is licensed under the LGPL + OCaml linking exception.  This
 208 module includes mmalloc which was originally distributed with gdb
 209 (although it has since been removed), and that code was distributed
 210 under the plain LGPL.
 211
 212 Latest version
 213 ----------------------------------------------------------------------
 214
 215 The latest version can be found on the website:
 216 http://merjis.com/developers/ancient