docs/develop/kernel/swap_file_support

   1                                                 Haiku swap file support
   2
   3 This article describes how to use swap file in Haiku and how the swap system
   4 works.
   5
   6 1.  How to use a swap file?
   7
   8         Like BeOS, Haiku uses "/var/swap" as default swap file. It is created
   9 during the boot process and its size is twice the size of physical memory by
  10 default. You can change its size through the VirtualMemory preference
  11 application and your settings will take effect after restarting the system.
  12
  13         The default swap file "/var/swap" may not satisfy your need. Haiku allows
  14 adding/removing a swap file dynamically. (This is *NOT* implemented yet, since
  15 I do not know how to add bin commands "swapon" and "swapoff" in the system.
  16 It needs to be done in the future.)
  17
  18 2.  How swap system works?
  19
  20         The virtual memory subsystem of Haiku is very similar to that of FreeBSD,
  21 therefore our swap system implementation is borrowed from FreeBSD.
  22
  23         A swap system has two main functions: (1) maintain a map between anonymous
  24 pages and swap space, so we can page in/out when needed. (2) manage the
  25 allocation/deallocation of swap space. Let's see how these are implemented in
  26 Haiku.
  27
  28         In order to maintain a map between pages and swap space, we need to record
  29 the pages' swap address somewhere. Here we use swap blocks. A "swap_block"
  30 structure contains swap address information for 32 (value of SWAP_BLOCK_PAGES)
  31 consecutive pages from a same cache. So whenever we look for a page in swap
  32 files, we should get the swap block for it. But how to get the swap block?
  33 Here we use hash table. All swap blocks in the system are arranged into a global
  34 hash table. The hash table uses a cache's address and page index in this cache
  35 as hash key.
  36
  37         Here is an example.     Suppose a page has been paged out to swap space and now
  38 its cache wants to page it in. It works as follows: look up the swap hash table
  39 using address of the cache and page index as hash key, if successful, we get
  40 the swap block containing the this page's swap address. Then search the swap
  41 block to get the exact swap address of this page. After that, we can read the
  42 page from swap file using vfs functions.
  43
  44         I draw a picture and hope it could help you understand the above words. If
  45 the pic becomes a mess on your computer, please set the tab width of your text
  46 editor to 4.
  47
  48                     ___________________________________________________________
  49     sSwapHashTable  |__________|___NULL___|___NULL___|___________|____NULL____|
  50                              |                                 |
  51                                                  |                                 |
  52                       ___V___                           ___V___
  53         swap_block   /----|__0__|                  /--------|__5__|
  54                  |    |__3__|--------\         |    /---|__6__|
  55                          |    |_..._|        |         |    |   |_..._|
  56                      |    |__2__|----\   |         |    |   |__20_|--------------->
  57                  |               |   |         |    |
  58                      |  _____________V___V_________V____V_________________________
  59         swap_file    `->|slot|slot|slot|slot|slot|slot|slot|slot|slot|slot|....|
  60                         |_0__|_1__|_2__|_3__|_4__|_5__|_6__|_7__|_8__|_9__|____|__
  61
  62
  63         The swap system also manages allocation/deallocation of swap space.     In our
  64 implementation, each swap file is divided into page-sized slots(called "swap
  65 pages") and a swap file can be seen as an array of many swap pages(see the
  66 above picture). Swap page is the unit for swap space allocation/deallocation
  67 and we use swap page index (slot index) as swap space address instead of offset.
  68 All the swap pages in the system are given a unified address and we leave one
  69 page gap between two swap files. (e.g. there are 3 swap files in the system,
  70 each has 100 swap pages, the address range(to be exact, page index) for each
  71 swap file is: 0-99, 101-200, 202-301) Why leave a page gap between swap files?
  72 Because in this way, we can easily tell if two adjacent pages are in a same
  73 swap file. (See the code in VMAnonymousCache::Read()).
  74
  75         The efficiency of the FreeBSD swap system lies in a special data structure:
  76 radix bitmap(i.e. bitmap using radix tree for hinting.) It can operate well no
  77 matter how much fragmentation there is and no matter how large a bitmap is
  78 used. I have ported the radix bitmap structure to Haiku, so our swap system
  79 will have a good performance. More information on radix bitmap, please look
  80 at the source code.
  81
  82         Swap space allocation takes place when we swap anonymous pages out.
  83 In order to make the allocation less probable to fail, anonymous cache will
  84 reserve swap space when it is initialized. If there is not enough swap space
  85 left, physical memory will be reserved. Swap space deallocation happens when
  86 available swap space is low. The page daemon will scan a number of pages and
  87 if the scanned page has swap space assigned, its swap space will be freed.
  88
  89 3.  Acknowledgement
  90
  91         Special thanks to my mentor Ingo. He is a knowledged person and always
  92 gives me encouragement. Without his consistent and illuminating instructions,
  93 this project would not have reached its present status.
  94
  95         If you find bugs or have suggestions for swap system, you can contact me
  96 via upczhsh@163.com. Thanks in advance.
  97
  98                                                                Zhao Shuai
  99                                                             upczhsh@163.com
 100                                                                2008-08-21