path: root/Documentation/power/tuxonice-internals.txt

		   TuxOnIce 4.0 Internal Documentation.
			Updated to 23 March 2015

(Please note that incremental image support mentioned in this document is work
in progress. This document may need updating prior to the actual release of
4.0!)

1.  Introduction.

    TuxOnIce 4.0 is an addition to the Linux Kernel, designed to
    allow the user to quickly shutdown and quickly boot a computer, without
    needing to close documents or programs. It is equivalent to the
    hibernate facility in some laptops. This implementation, however,
    requires no special BIOS or hardware support.

    The code in these files is based upon the original implementation
    prepared by Gabor Kuti and additional work by Pavel Machek and a
    host of others. This code has been substantially reworked by Nigel
    Cunningham, again with the help and testing of many others, not the
    least of whom are Bernard Blackham and Michael Frank. At its heart,
    however, the operation is essentially the same as Gabor's version.

2.  Overview of operation.

    The basic sequence of operations is as follows:

	a. Quiesce all other activity.
	b. Ensure enough memory and storage space are available, and attempt
	   to free memory/storage if necessary.
	c. Allocate the required memory and storage space.
	d. Write the image.
	e. Power down.

    There are a number of complicating factors which mean that things are
    not as simple as the above would imply, however...

    o The activity of each process must be stopped at a point where it will
    not be holding locks necessary for saving the image, or unexpectedly
    restart operations due to something like a timeout and thereby make
    our image inconsistent.

    o It is desirous that we sync outstanding I/O to disk before calculating
    image statistics. This reduces corruption if one should suspend but
    then not resume, and also makes later parts of the operation safer (see
    below).

    o We need to get as close as we can to an atomic copy of the data.
    Inconsistencies in the image will result in inconsistent memory contents at
    resume time, and thus in instability of the system and/or file system
    corruption. This would appear to imply a maximum image size of one half of
    the amount of RAM, but we have a solution... (again, below).

    o In 2.6 and later, we choose to play nicely with the other suspend-to-disk
    implementations.

3.  Detailed description of internals.

    a. Quiescing activity.

    Safely quiescing the system is achieved using three separate but related
    aspects.

    First, we use the vanilla kerne's support for freezing processes. This code
    is based on the observation that the vast majority of processes don't need
    to run during suspend. They can be 'frozen'. The kernel therefore
    implements a refrigerator routine, which processes enter and in which they
    remain until the cycle is complete. Processes enter the refrigerator via
    try_to_freeze() invocations at appropriate places.  A process cannot be
    frozen in any old place. It must not be holding locks that will be needed
    for writing the image or freezing other processes. For this reason,
    userspace processes generally enter the refrigerator via the signal
    handling code, and kernel threads at the place in their event loops where
    they drop locks and yield to other processes or sleep. The task of freezing
    processes is complicated by the fact that there can be interdependencies
    between processes. Freezing process A before process B may mean that
    process B cannot be frozen, because it stops at waiting for process A
    rather than in the refrigerator. This issue is seen where userspace waits
    on freezeable kernel threads or fuse filesystem threads. To address this
    issue, we implement the following algorithm for quiescing activity:

	- Freeze filesystems (including fuse - userspace programs starting
		new requests are immediately frozen; programs already running
		requests complete their work before being frozen in the next
		step)
	- Freeze userspace
	- Thaw filesystems (this is safe now that userspace is frozen and no
		fuse requests are outstanding).
	- Invoke sys_sync (noop on fuse).
	- Freeze filesystems
	- Freeze kernel threads

    If we need to free memory, we thaw kernel threads and filesystems, but not
    userspace. We can then free caches without worrying about deadlocks due to
    swap files being on frozen filesystems or such like.

    b. Ensure enough memory & storage are available.

    We have a number of constraints to meet in order to be able to successfully
    suspend and resume.

    First, the image will be written in two parts, described below. One of
    these parts needs to have an atomic copy made, which of course implies a
    maximum size of one half of the amount of system memory. The other part
    ('pageset') is not atomically copied, and can therefore be as large or
    small as desired.

    Second, we have constraints on the amount of storage available. In these
    calculations, we may also consider any compression that will be done. The
    cryptoapi module allows the user to configure an expected compression ratio.

    Third, the user can specify an arbitrary limit on the image size, in
    megabytes. This limit is treated as a soft limit, so that we don't fail the
    attempt to suspend if we cannot meet this constraint.

    c. Allocate the required memory and storage space.

    Having done the initial freeze, we determine whether the above constraints
    are met, and seek to allocate the metadata for the image. If the constraints
    are not met, or we fail to allocate the required space for the metadata, we
    seek to free the amount of memory that we calculate is needed and try again.
    We allow up to four iterations of this loop before aborting the cycle. If
    we do fail, it should only be because of a bug in TuxOnIce's calculations
    or the vanilla kernel code for freeing memory.

    These steps are merged together in the prepare_image function, found in
    prepare_image.c. The functions are merged because of the cyclical nature
    of the problem of calculating how much memory and storage is needed. Since
    the data structures containing the information about the image must
    themselves take memory and use storage, the amount of memory and storage
    required changes as we prepare the image. Since the changes are not large,
    only one or two iterations will be required to achieve a solution.

    The recursive nature of the algorithm is miminised by keeping user space
    frozen while preparing the image, and by the fact that our records of which
    pages are to be saved and which pageset they are saved in use bitmaps (so
    that changes in number or fragmentation of the pages to be saved don't
    feedback via changes in the amount of memory needed for metadata). The
    recursiveness is thus limited to any extra slab pages allocated to store the
    extents that record storage used, and the effects of seeking to free memory.

    d. Write the image.

    We previously mentioned the need to create an atomic copy of the data, and
    the half-of-memory limitation that is implied in this. This limitation is
    circumvented by dividing the memory to be saved into two parts, called
    pagesets.

    Pageset2 contains most of the page cache - the pages on the active and
    inactive LRU lists that aren't needed or modified while TuxOnIce is
    running, so they can be safely written without an atomic copy. They are
    therefore saved first and reloaded last. While saving these pages,
    TuxOnIce carefully ensures that the work of writing the pages doesn't make
    the image inconsistent. With the support for Kernel (Video) Mode Setting
    going into the kernel at the time of writing, we need to check for pages
    on the LRU that are used by KMS, and exclude them from pageset2. They are
    atomically copied as part of pageset 1.

    Once pageset2 has been saved, we prepare to do the atomic copy of remaining
    memory. As part of the preparation, we power down drivers, thereby providing
    them with the opportunity to have their state recorded in the image. The
    amount of memory allocated by drivers for this is usually negligible, but if
    DRI is in use, video drivers may require significants amounts. Ideally we
    would be able to query drivers while preparing the image as to the amount of
    memory they will need. Unfortunately no such mechanism exists at the time of
    writing. For this reason, TuxOnIce allows the user to set an
    'extra_pages_allowance', which is used to seek to ensure sufficient memory
    is available for drivers at this point. TuxOnIce also lets the user set this
    value to 0. In this case, a test driver suspend is done while preparing the
    image, and the difference (plus a margin) used instead. TuxOnIce will also
    automatically restart the hibernation process (twice at most) if it finds
    that the extra pages allowance is not sufficient. It will then use what was
    actually needed (plus a margin, again). Failure to hibernate should thus
    be an extremely rare occurence.

    Having suspended the drivers, we save the CPU context before making an
    atomic copy of pageset1, resuming the drivers and saving the atomic copy.
    After saving the two pagesets, we just need to save our metadata before
    powering down.

    As we mentioned earlier, the contents of pageset2 pages aren't needed once
    they've been saved. We therefore use them as the destination of our atomic
    copy. In the unlikely event that pageset1 is larger, extra pages are
    allocated while the image is being prepared. This is normally only a real
    possibility when the system has just been booted and the page cache is
    small.

    This is where we need to be careful about syncing, however. Pageset2 will
    probably contain filesystem meta data. If this is overwritten with pageset1
    and then a sync occurs, the filesystem will be corrupted - at least until
    resume time and another sync of the restored data. Since there is a
    possibility that the user might not resume or (may it never be!) that
    TuxOnIce might oops, we do our utmost to avoid syncing filesystems after
    copying pageset1.

    e. Incremental images

    TuxOnIce 4.0 introduces a new incremental image mode which changes things a
    little. When incremental images are enabled, we save a 'normal' image the
    first time we hibernate. One resume however, we do not free the image or
    the associated storage. Instead, it is retained until the next attempt at
    hibernating and a mechanism is enabled which is used to track which pages
    of memory are modified between the two cycles. The modified pages can then
    be added to the existing image, rather than unmodified pages being saved
    again unnecessarily.

    Incremental image support is available in 64 bit Linux only, due to the
    requirement for extra page flags.

    This support is accomplished in the following way:

    1) Tracking of pages.

    The tracking of changed pages is accomplished using the page fault
    mechanism. When we reach a point at which we want to start tracking
    changes, most pages are marked read-only and also flagged as being
    read-only because of this support. Since this cannot happen for every page
    of RAM, some are marked as untracked and always treated as modified whn
    preparing an incremental iamge. When a process attempts to modify a page
    that is marked read-only in this way, a page fault occurs, with TuxOnIce
    code marking the page writable and dirty before allowing the write to
    continue. In this way, the effect of incremental images on performance is
    minimised - a page only causes a fault once. Small modifications to the
    page allocator further reduce the number of faults that occur - free pages
    are not tracked; they are made writable and marked as dirty as part of
    being allocated.

    2) Saving the incremental image / atomicity.

    The page fault mechanism is also used to improve the means by which
    atomicity of the image is acheived. When it is time to do an atomic copy,
    the flags for pages are reset, with the result being that it is no longer
    necessary for us to do an atomic of pageset1. Instead, we normally write
    the uncopied pages to disk. When an attempt is made to modify a page that
    has not yet been saved, the page-fault mechanism makes a copy of the page
    prior to allowing the write. This copy is then written to disk. Likewise,
    on resume, if a process attempts to write to a page that has been read
    while the rest of the image is still being loaded, a copy of that page is
    made prior to the write being allowed. At the end of loading the image,
    modified pages can thus be restored to their 'atomic copy' contents prior
    to restarting normal operation. We also mark pages that are yet to be read
    as invalid PFNs, so that we can capture as a bug any attempt by a
    half-restored kernel to access a page that hasn't yet been reloaded.

    f. Power down.

    Powering down uses standard kernel routines. TuxOnIce supports powering down
    using the ACPI S3, S4 and S5 methods or the kernel's non-ACPI power-off.
    Supporting suspend to ram (S3) as a power off option might sound strange,
    but it allows the user to quickly get their system up and running again if
    the battery doesn't run out (we just need to re-read the overwritten pages)
    and if the battery does run out (or the user removes power), they can still
    resume.

4.  Data Structures.

    TuxOnIce uses three main structures to store its metadata and configuration
    information:

    a) Pageflags bitmaps.

    TuxOnIce records which pages will be in pageset1, pageset2, the destination
    of the atomic copy and the source of the atomically restored image using
    bitmaps. The code used is that written for swsusp, with small improvements
    to match TuxOnIce's requirements.

    The pageset1 bitmap is thus easily stored in the image header for use at
    resume time.

    As mentioned above, using bitmaps also means that the amount of memory and
    storage required for recording the above information is constant. This
    greatly simplifies the work of preparing the image. In earlier versions of
    TuxOnIce, extents were used to record which pages would be stored. In that
    case, however, eating memory could result in greater fragmentation of the
    lists of pages, which in turn required more memory to store the extents and
    more storage in the image header. These could in turn require further
    freeing of memory, and another iteration. All of this complexity is removed
    by having bitmaps.

    Bitmaps also make a lot of sense because TuxOnIce only ever iterates
    through the lists. There is therefore no cost to not being able to find the
    nth page in order 0 time. We only need to worry about the cost of finding
    the n+1th page, given the location of the nth page. Bitwise optimisations
    help here.

    b) Extents for block data.

    TuxOnIce supports writing the image to multiple block devices. In the case
    of swap, multiple partitions and/or files may be in use, and we happily use
    them all (with the exception of compcache pages, which we allocate but do
    not use). This use of multiple block devices is accomplished as follows:

    Whatever the actual source of the allocated storage, the destination of the
    image can be viewed in terms of one or more block devices, and on each
    device, a list of sectors. To simplify matters, we only use contiguous,
    PAGE_SIZE aligned sectors, like the swap code does.

    Since sector numbers on each bdev may well not start at 0, it makes much
    more sense to use extents here. Contiguous ranges of pages can thus be
    represented in the extents by contiguous values.

    Variations in block size are taken account of in transforming this data
    into the parameters for bio submission.

    We can thus implement a layer of abstraction wherein the core of TuxOnIce
    doesn't have to worry about which device we're currently writing to or
    where in the device we are. It simply requests that the next page in the
    pageset or header be written, leaving the details to this lower layer.
    The lower layer remembers where in the sequence of devices and blocks each
    pageset starts. The header always starts at the beginning of the allocated
    storage.

    So extents are:

    struct extent {
      unsigned long minimum, maximum;
      struct extent *next;
    }

    These are combined into chains of extents for a device:

    struct extent_chain {
      int size; /* size of the extent ie sum (max-min+1) */
      int allocs, frees;
      char *name;
      struct extent *first, *last_touched;
    };

    For each bdev, we need to store a little more info (simplified definition):

    struct toi_bdev_info {
       struct block_device *bdev;

       char uuid[17];
       dev_t dev_t;
       int bmap_shift;
       int blocks_per_page;
    };

    The uuid is the main means used to identify the device in the storage
    image. This means we can cope with the dev_t representation of a device
    changing between saving the image and restoring it, as may happen on some
    bioses or in the LVM case.

    bmap_shift and blocks_per_page apply the effects of variations in blocks
    per page settings for the filesystem and underlying bdev. For most
    filesystems, these are the same, but for xfs, they can have independant
    values.

    Combining these two structures together, we have everything we need to
    record what devices and what blocks on each device are being used to
    store the image, and to submit i/o using bio_submit.

    The last elements in the picture are a means of recording how the storage
    is being used.

    We do this first and foremost by implementing a layer of abstraction on
    top of the devices and extent chains which allows us to view however many
    devices there might be as one long storage tape, with a single 'head' that
    tracks a 'current position' on the tape:

    struct extent_iterate_state {
      struct extent_chain *chains;
      int num_chains;
      int current_chain;
      struct extent *current_extent;
      unsigned long current_offset;
    };

    That is, *chains points to an array of size num_chains of extent chains.
    For the filewriter, this is always a single chain. For the swapwriter, the
    array is of size MAX_SWAPFILES.

    current_chain, current_extent and current_offset thus point to the current
    index in the chains array (and into a matching array of struct
    suspend_bdev_info), the current extent in that chain (to optimise access),
    and the current value in the offset.

    The image is divided into three parts:
    - The header
    - Pageset 1
    - Pageset 2

    The header always starts at the first device and first block. We know its
    size before we begin to save the image because we carefully account for
    everything that will be stored in it.

    The second pageset (LRU) is stored first. It begins on the next page after
    the end of the header.

    The first pageset is stored second. It's start location is only known once
    pageset2 has been saved, since pageset2 may be compressed as it is written.
    This location is thus recorded at the end of saving pageset2. It is page
    aligned also.

    Since this information is needed at resume time, and the location of extents
    in memory will differ at resume time, this needs to be stored in a portable
    way:

    struct extent_iterate_saved_state {
        int chain_num;
        int extent_num;
        unsigned long offset;
    };

    We can thus implement a layer of abstraction wherein the core of TuxOnIce
    doesn't have to worry about which device we're currently writing to or
    where in the device we are. It simply requests that the next page in the
    pageset or header be written, leaving the details to this layer, and
    invokes the routines to remember and restore the position, without having
    to worry about the details of how the data is arranged on disk or such like.

    c) Modules

    One aim in designing TuxOnIce was to make it flexible. We wanted to allow
    for the implementation of different methods of transforming a page to be
    written to disk and different methods of getting the pages stored.

    In early versions (the betas and perhaps Suspend1), compression support was
    inlined in the image writing code, and the data structures and code for
    managing swap were intertwined with the rest of the code. A number of people
    had expressed interest in implementing image encryption, and alternative
    methods of storing the image.

    In order to achieve this, TuxOnIce was given a modular design.

    A module is a single file which encapsulates the functionality needed
    to transform a pageset of data (encryption or compression, for example),
    or to write the pageset to a device. The former type of module is called
    a 'page-transformer', the later a 'writer'.

    Modules are linked together in pipeline fashion. There may be zero or more
    page transformers in a pipeline, and there is always exactly one writer.
    The pipeline follows this pattern:

		---------------------------------
		|          TuxOnIce Core        |
		---------------------------------
				|
				|
		---------------------------------
		|	Page transformer 1	|
		---------------------------------
				|
				|
		---------------------------------
		|	Page transformer 2	|
		---------------------------------
				|
				|
		---------------------------------
		|            Writer		|
		---------------------------------

    During the writing of an image, the core code feeds pages one at a time
    to the first module. This module performs whatever transformations it
    implements on the incoming data, completely consuming the incoming data and
    feeding output in a similar manner to the next module.

    All routines are SMP safe, and the final result of the transformations is
    written with an index (provided by the core) and size of the output by the
    writer. As a result, we can have multithreaded I/O without needing to
    worry about the sequence in which pages are written (or read).

    During reading, the pipeline works in the reverse direction. The core code
    calls the first module with the address of a buffer which should be filled.
    (Note that the buffer size is always PAGE_SIZE at this time). This module
    will in turn request data from the next module and so on down until the
    writer is made to read from the stored image.

    Part of definition of the structure of a module thus looks like this:

        int (*rw_init) (int rw, int stream_number);
        int (*rw_cleanup) (int rw);
        int (*write_chunk) (struct page *buffer_page);
        int (*read_chunk) (struct page *buffer_page, int sync);

    It should be noted that the _cleanup routine may be called before the
    full stream of data has been read or written. While writing the image,
    the user may (depending upon settings) choose to abort suspending, and
    if we are in the midst of writing the last portion of the image, a portion
    of the second pageset may be reread. This may also happen if an error
    occurs and we seek to abort the process of writing the image.

    The modular design is also useful in a number of other ways. It provides
    a means where by we can add support for:

    - providing overall initialisation and cleanup routines;
    - serialising configuration information in the image header;
    - providing debugging information to the user;
    - determining memory and image storage requirements;
    - dis/enabling components at run-time;
    - configuring the module (see below);

    ...and routines for writers specific to their work:
    - Parsing a resume= location;
    - Determining whether an image exists;
    - Marking a resume as having been attempted;
    - Invalidating an image;

    Since some parts of the core - the user interface and storage manager
    support - have use for some of these functions, they are registered as
    'miscellaneous' modules as well.

    d) Sysfs data structures.

    This brings us naturally to support for configuring TuxOnIce. We desired to
    provide a way to make TuxOnIce as flexible and configurable as possible.
    The user shouldn't have to reboot just because they want to now hibernate to
    a file instead of a partition, for example.

    To accomplish this, TuxOnIce implements a very generic means whereby the
    core and modules can register new sysfs entries. All TuxOnIce entries use
    a single _store and _show routine, both of which are found in
    tuxonice_sysfs.c in the kernel/power directory. These routines handle the
    most common operations - getting and setting the values of bits, integers,
    longs, unsigned longs and strings in one place, and allow overrides for
    customised get and set options as well as side-effect routines for all
    reads and writes.

    When combined with some simple macros, a new sysfs entry can then be defined
    in just a couple of lines:

        SYSFS_INT("progress_granularity", SYSFS_RW, &progress_granularity, 1,
                        2048, 0, NULL),

    This defines a sysfs entry named "progress_granularity" which is rw and
    allows the user to access an integer stored at &progress_granularity, giving
    it a value between 1 and 2048 inclusive.

    Sysfs entries are registered under /sys/power/tuxonice, and entries for
    modules are located in a subdirectory named after the module.