8.8 Used algorithm

Algorithm described here is implemented in convert() function. The algorithm consists of the following phases.

• The first phase - initialization

  Registred all imported and exported partition and also all given free space. Hence all of these lay on one virtual device and look as intervals, this simplyfies addressing.

  Consequently is created tree intended to represent knowledge about (current) location of blocks of exported partitions. This allows adressing the virtual device in its destination state. We need functions for converting these two types of addressing and its implementation needs this tree representation.

  This tree contains information about data in blocks and allows searching for unused blocks (also for used, bad etc.)

• The second phase - Building exported filesystems

  In this phase are all exported filesystems built. Each exported filesystem is created empty at first and all files are copied from source imported filesystem, important note is that this process doesn't modify any imported filesystems because pieces of exported filesystems are stored in unused blocks like temporary free space, unused blocks in imported filesystems or blocks in exported partition outside all imported partitions.

  In addition copying files is virtual only because there isn't reason to make copies of file. Exported filesystem tells where the file should be created (relatively to beginning of this exported partition). If it is possible there may be prefered the original location because of optimalization reasons. And now GConv arranges that block of such file is piece of exported partition.

  Note that this part doesn't modify any imported partition therefore abort doesn't cause any problem.

• The third phase - Generating permutating program

  This phase prepares permutating program for the next phase and stores it into unused blocks. The program is a sequence of couples of blocks which may be swapped. Program is stored with Run-Length encoding to minimize the size of representation.

  Note that blocks of this program can be moved by previous any previous swaps. Therefore the generator considers this to correct read of next piece of program.

• The fourth phase - Crazy permutating blocks

  This phase is implementation of swapping machine. This machine is simple to eliminate possible bugs in this critical section. And it is designed for pertient future support of journalling. The main task is to read swapping program and apply this swaps.

  This part is critical and you shouldn't interrupt it. Illegal interruption can cause lose your data stored in imported/exported partitions.