| | |     .---._____
  .-----.   |          |
--|o    |---| littlefs |
--|     |---|          |
  '-----'   '----------'
   | | |

               .--------.
               |  root  |
               |        |
               |        |
               '--------'
               .-'    '-.
              v          v
         .--------.  .--------. |  |  | B  |
|---|---|---|
|  |  |   |  | 
|  |  |   |  |
| '--------' '--------'|
|. -'    '-.  . -'    '-.|
|v         v  v         |
|.--------. .--------.|
| C       | D       |
|         |        |
|         |        |
|'--------' '--------'|

                                                             v
.--------.--------.--------.--------.--------.--------.--------.--------.|
        C        | new B  | new A  |                 |   A    |   B    |
                       |        |        |->               |        |        |
                       |        |        |                 |        |        |
'--------'--------'--------'--------'--------'--------'--------'--------'|

Файловые системы журналирования прекрасны и элегантны. С помощью контрольной суммы мы можем легко обнаружить потерю питания и вернуться к предыдущему состоянию, игнорируя неудачные добавления. И если этого было недостаточно, их циклическая природа означает, что файловые системы журналирования идеально распределяют износ по хранилищу.

Основным недостатком является производительность. Если мы посмотрим на сборку мусора, процесс очистки устаревших данных из конца журнала, я ещё не видел чисто файловой системы журналирования, которая не имела бы одной из этих двух затрат:

1. O(n²) время выполнения
2. O(n) оперативная память

SPIFFS здесь представляет особый интерес, поскольку он использует тот факт, что повторные программы для флэш-памяти NOR являются атомарными и маскирующими. Это очень изящное решение, однако оно ограничивает тип поддерживаемого хранилища.

3. Возможно, наиболее распространённым типом файловой системы является журналируемая файловая система — потомок, возникающий при объединении блочной файловой системы с файловой системой журналирования. ext4 и NTFS являются хорошими примерами. Здесь мы берём обычную блочную файловую систему и добавляем ограниченный журнал, где отмечаем каждое изменение перед его выполнением.

Этот тип файловой системы берёт лучшее из обоих миров. Производительность может быть такой же быстрой, как у блочной файловой системы (хотя обновление журнала имеет небольшую стоимость), а атомарные обновления журнала позволяют файловой системе восстанавливаться в случае потери питания.

К сожалению, у журналируемых файловых систем есть пара проблем. Они довольно сложны, так как фактически работают две файловые системы параллельно, что приводит к увеличению размера кода. Также они не предлагают защиты от износа из-за тесной связи между расположением хранилища и данными.

4. Последнее, но... Не в последнюю очередь у нас есть файловые системы с копированием при записи (COW), такие как btrfs и ZFS. Они очень похожи на другие блочные файловые системы, но вместо обновления блока на месте все обновления выполняются путём создания копии с изменениями и замены любых ссылок на старый блок нашим новым блоком. Это рекурсивно продвигает все наши проблемы вверх, пока мы не достигнем корня нашей файловой системы, который часто хранится в очень маленьком журнале.

           .--------.                  .--------.
           |  root  |       write      |new root|
           |        |        ==>       |        |
           |        |                  |        |
           '--------'                  '--------'
           .-'    '-.                    |    '-.
          |  .-------|------------------'        v
          v v        v                       .--------.
     .--------.  .--------.                  | new B  |
     |   A    |  |   B    |                  |        |
     |        |  |        |                  |        |
     |        |  |        |                  '--------'
     '--------'  '--------'                  .-'    |
     .-'         .-'    '-.    .------------|------'
    |           |          |  |             v
    v           v          v  v        .--------.

Файловые системы COW интересны. Они предлагают производительность, аналогичную производительности блочных файловых систем, при этом им удаётся выполнять атомарные обновления без хранения изменений данных непосредственно в журнале. Они даже разъединяют место хранения данных, что создаёт возможность для выравнивания износа.

Ну, почти. Неограниченное движение обновлений вверх вызывает некоторые проблемы. Поскольку обновления в файловой системе COW не останавливаются, пока не достигнут корня, обновление может каскадно привести к большему количеству операций записи, чем потребовалось бы для исходных данных. Кроме того, движение вверх фокусирует эти операции записи в блоке, который может износиться гораздо раньше, чем остальная часть файловой системы.

## littlefs

Так что же делает littlefs?

Если мы посмотрим на существующие файловые системы, есть два интересных шаблона проектирования, которые выделяются, но каждый имеет свой собственный набор проблем. Ведение журнала обеспечивает независимую атомарность, но имеет плохую производительность во время выполнения. А структуры данных COW, которые хорошо работают, продвигают проблему атомарности вверх.

Можем ли мы обойти эти ограничения?

Рассмотрим ведение журнала. Оно имеет либо квадратичную сложность по времени выполнения O(n²), либо линейную по объёму используемой памяти O(n). Мы не можем избежать этих затрат, *но* если мы установим верхний предел размера, мы, по крайней мере, сможем предотвратить превращение теоретической стоимости в проблему. Это опирается на суперсекретный хакерский приём в информатике, где вы можете притвориться, что любая алгоритмическая сложность равна O(1), ограничив ввод.

В случае структур данных COW мы можем попробовать немного изменить определение. Допустим, наша структура COW копируется не после одной записи, а после *n* записей. Это не меняет большинство свойств COW (при условии, что вы можете писать атомарно!), но это предотвращает движение износа вверх. Этот вид копирования при ограниченном количестве записей (CObW) всё ещё фокусирует износ, но на каждом уровне мы делим распространение износа на *n*. При достаточно большом *n* (> коэффициент ветвления) распространение износа больше не является проблемой.

Видите, к чему это ведёт? Ведение журнала и COW по отдельности являются несовершенными решениями и имеют недостатки, ограничивающие их полезность. Но если мы объединим их, они смогут взаимно решить проблемы друг друга.

Это идея, лежащая в основе littlefs. На уровне субблоков littlefs состоит из небольших двухблочных журналов, которые обеспечивают атомарное обновление метаданных в любом месте файловой системы. На уровне суперблока littlefs представляет собой дерево блоков CObW, которое можно выселить по требованию. Есть ещё некоторые незначительные проблемы. Небольшие логи могут быть дорогими с точки зрения хранения, в худшем случае небольшой лог стоит в 4 раза больше, чем размер исходных данных.

Структуры CObW требуют эффективного распределителя блоков, поскольку выделение происходит при каждой записи. И всё ещё остаётся проблема поддержания постоянного использования оперативной памяти.

## Пары метаданных

Пары метаданных — это основа littlefs. Это небольшие двухблочные логи, которые позволяют выполнять атомарные обновления в любом месте файловой системы.

Почему два блока? Ну, логи работают путём добавления записей в кольцевой буфер, хранящийся на диске. Но помните, что у флэш-памяти ограниченная детализация записи. Мы можем постепенно программировать новые данные на стёртые блоки, но нам нужно стирать целый блок за раз. Это означает, что для того, чтобы наш кольцевой буфер работал, нам нужно больше одного блока.

Мы могли бы сделать наши логи больше двух блоков, но следующая задача — как мы храним ссылки на эти логи? Поскольку сами блоки стираются во время записи, использовать структуру данных для отслеживания этих блоков сложно. Простое решение здесь — хранить адреса двух блоков для каждой пары метаданных. У этого есть дополнительное преимущество: мы можем независимо изменять блоки в паре метаданных и не уменьшаем детализацию наших блоков для других операций.

Чтобы определить, какой блок метаданных самый последний, мы сохраняем счётчик ревизий, который сравниваем, используя арифметику последовательностей (очень удобно для избежания проблем с целочисленным переполнением). Удобно, что этот счётчик ревизий также даёт нам примерное представление о том, сколько стираний произошло в блоке.

Атомарность (один из видов устойчивости к потере питания) требует двух составляющих: избыточности и обнаружения ошибок. Обнаружение ошибок может быть обеспечено контрольной суммой, и в случае littlefs мы используем 32-битный CRC (циклический избыточный код).

Поддержание избыточности, с другой стороны, требует нескольких этапов.

1. Если наш блок не заполнен и размер программы достаточно мал, чтобы позволить нам добавить больше записей, мы можем просто добавить записи в журнал. Поскольку мы не перезаписываем исходные записи (помните, что переписывание флэш-памяти требует стирания), у нас всё ещё есть исходные записи, если мы потеряем питание во время добавления.

   Обратите внимание, что littlefs не поддерживает контрольную сумму для каждой записи. Многие файловые системы ведения журналов делают это, но это ограничивает то, что вы можете обновить за одну атомарную операцию. Вместо этого мы можем группировать несколько записей в коммит, который имеет общую контрольную сумму. Это позволяет нам обновлять несколько несвязанных частей метаданных, пока они находятся в одной паре метаданных.

2. Если наш блок полон записей, нам нужно как-то удалить устаревшие записи, чтобы освободить место для новых. Этот процесс называется сборкой мусора, но поскольку littlefs имеет несколько сборщиков мусора... **Есть ещё одна сложность, которая возникает при работе с небольшими логами.**

Амортизированная стоимость времени сборки мусора зависит не только от единовременных затрат (O(n²) для littlefs), но и от того, как часто происходит сборка мусора.

Рассмотрим два крайних случая:
1. Лог пуст, сборка мусора происходит один раз каждые n обновлений.
2. Лог полон, сборка мусора происходит **при каждом** обновлении.

Очевидно, что нам нужно быть более агрессивными, чем ждать, пока наша пара метаданных заполнится. По мере приближения пары метаданных к заполнению частота уплотнений растёт очень быстро.

Рассматривая проблему в общем виде, рассмотрим лог с n байтами для каждой записи, d динамическими записями (записи, которые устаревают во время сборки мусора) и s статическими записями (записями, которые необходимо скопировать во время сборки мусора). Если мы посмотрим на амортизированную сложность времени обновления этого лога, то получим следующую формулу:

cost = n + n (s / d+1).

Если мы позволим r быть отношением статического пространства к размеру нашего лога в байтах, мы найдём альтернативное представление количества статических и динамических записей:

s = r (размер/n);
d = (1 - r) (размер/n).

Подставляя их вместо d и s, получаем красивую формулу стоимости обновления записи с учётом степени заполнения лога:

cost = n + n (r (размер/n) / ((1-r) (размер/n) + 1)).

Предполагая, что размер записи составляет 100 байт в 4 КБ логе, мы можем построить график, используя размер записи, чтобы найти мультипликативную стоимость:

График стоимости обновления пары метаданных.

Таким образом, при использовании на 50% мы видим среднюю стоимость в 2 раза за обновление, а при использовании на 75% — уже в среднем в 4 раза за обновление.

Чтобы избежать такого экспоненциального роста, вместо ожидания заполнения нашей пары метаданных мы разделяем пару метаданных, когда превышаем предел в 50%. Мы делаем это лениво, ожидая, пока нам не понадобится уплотнить, прежде чем проверять, вписываемся ли мы в наш 50%-ный лимит. Это ограничивает накладные расходы сборки мусора до 2x стоимости времени выполнения, давая нам амортизированную сложность времени выполнения O(1).

**Если мы рассмотрим пары метаданных и связанные списки пар метаданных на высоком уровне, у них будет довольно хорошая стоимость времени выполнения.**

Предполагая n пар метаданных, каждая из которых содержит m записей метаданных, стоимость поиска конкретной записи имеет наихудшую сложность времени выполнения O(nm). Для обновления конкретной записи наихудшая сложность равна O(nm²), с амортизированной сложностью всего O(nm).

Однако разделение на 50% означает, что в лучшем случае наши пары метаданных будут заполнены только на 1/2. Если мы включим накладные расходы второго блока в нашу пару метаданных, каждая запись метаданных будет иметь эффективную стоимость хранения в 4 раза больше исходного размера. Я полагаю, пользователи были бы недовольны, если бы обнаружили, что могут использовать только четверть своего... **Пропускные списки CTZ**

Пары метаданных обеспечивают эффективное атомарное обновление, но для хранения основной части данных нам нужен отдельный механизм.

**Пропускные списки CTZ** 

Пары метаданных предоставляют эффективный механизм атомарного обновления, но, к сожалению, имеют высокую стоимость хранения. Однако мы можем обойти эту стоимость, используя пары метаданных только для хранения ссылок на более плотные структуры данных с копированием при записи (COW).

Структуры данных с копированием при записи, также называемые чисто функциональными структурами данных, представляют собой категорию структур данных, в которых базовые элементы являются неизменяемыми. Для внесения изменений в данные необходимо создать новые элементы, содержащие копию обновлённых данных, и заменить все ссылки ссылками на новые элементы. Как правило, производительность структуры данных COW зависит от того, сколько старых элементов можно повторно использовать после замены частей данных.

У littlefs есть несколько требований к структурам COW. Они должны быть эффективными для чтения и записи, но самое главное — они должны быть проходимы с постоянным объёмом оперативной памяти. В частности, это исключает B-деревья, которые нельзя пройти с постоянным объёмом ОЗУ, и B+-деревья, которые невозможно обновить операциями COW.

Итак, что мы можем сделать? Сначала рассмотрим хранение файлов в простом связанном списке COW. Добавление блока, который является основой для записи файлов, означает, что нам нужно обновить последний блок, чтобы он указывал на наш новый блок. Это требует операции COW, а значит, нам нужно обновить предпоследний блок, затем третий с конца и так далее, пока мы не скопируем весь файл.

Чтобы избежать полной копии при добавлении, мы можем хранить данные в обратном порядке. Добавление блоков просто требует добавления нового блока, и никакие другие блоки обновлять не нужно. Если мы обновим блок в середине, нам всё равно придётся скопировать следующие блоки, но мы сможем повторно использовать любые блоки перед ним. Поскольку большинство операций записи в файлы линейны, эта конструкция предполагает, что добавление является наиболее распространённым типом обновления данных.

Однако у обратного связанного списка есть довольно очевидная проблема. Перебор файла по порядку имеет временную сложность O(n²). Квадратичное время выполнения только для чтения файла! Это ужасно.

К счастью, мы можем добиться большего. Вместо односвязного списка littlefs использует многоуровневый связанный список, часто называемый пропускным списком. Однако, в отличие от наиболее распространённого типа пропускных списков, пропускные списки littlefs строго детерминированы и основаны на некоторых интересных свойствах инструкции подсчёта конечных нулей (CTZ).

Правила, которым следуют пропускные списки CTZ, заключаются в том, что для каждого n-го блока, где n делится на 2^i, этот блок содержит указатель на блок n-2^i. Это означает, что каждый блок содержит от 1 до log₂n указателей, которые пропускают разные предшествующие элементы пропускного списка.

Название происходит от интенсивного использования инструкции CTZ, которая позволяет нам эффективно вычислять степени двойки. Для данного блока n этот блок содержит ctz(n)+1 указателей. |--|        |--|        |  |        |
'--------'  '--------'  '--------'  '--------'  '--------'  '--------'

.--------.  .--------.  .--------.  .--------.  .--------.  .--------.
| данные 0 |  | данные 1 |<-| данные 2 |  | данные 3 |  | данные 4 |<-| данные 5 |
|        |  |        |  |        |<-|        |--|        |  |        |
|        |  |        |  |        |  |        |  |        |  |        |
'--------'  '--------'  '--------'  '--------'  '--------'  '--------'

.--------.  .--------.  .--------.  .--------.  .--------.  .--------.
| данные 0 |  | данные 1 |  | данные 2 |  | данные 3 |  | данные 4 |<-| данные 5 |
|        |  |        |  |        |  |        |  |        |  |        |
|        |<-|        |--|        |--|        |--|        |  |        |
'--------'  '--------'  '--------'  '--------'  '--------'  '--------'

.----.----.----.----.----.----.----.----.----.----.----.----.
| A  |    |root| C  | B  |         | D  |    | E  |         |
|    |    |    |    |    |         |    |    |    |         |
'----'----'----'----'----'----'----'----'----'----'----'----'
  1    0    1    1    1    0    0    1    0    1    0    0
 \---------------------------+----------------------------/
                             v
               bitmap: 0xb94 (0b101110010100)

boot...         lookahead:
                fs blocks: fffff9fffffffffeffffffffffff0000
scanning...     lookahead: fffff9ff
                fs blocks: fffff9fffffffffeffffffffffff0000
alloc = 21      lookahead: fffffdff
                fs blocks: fffffdfffffffffeffffffffffff0000
alloc = 22      lookahead: ffffffff
                fs blocks: fffffffffffffffeffffffffffff0000
scanning...     lookahead:         fffffffe
                fs blocks: fffffffffffffffeffffffffffff0000
alloc = 63      lookahead:         ffffffff
                fs blocks: ffffffffffffffffffffffffffff0000
scanning...     lookahead:         ffffffff
                fs blocks: ffffffffffffffffffffffffffff0000
scanning...     lookahead:                 ffffffff
                fs blocks: ffffffffffffffffffffffffffff0000
scanning...     lookahead:                         ffff0000
                fs blocks: ffffffffffffffffffffffffffff0000
alloc = 112     lookahead:                         ffff8000
                fs blocks: ffffffffffffffffffffffffffff8000

   .----------------.
  .|    revision    |
  ||----------------|
  ||    A name      |
  ||   A skiplist  -----.
  ||----------------|   |  \
  ||    B name      |   |  +- metadata
  ||   B skiplist  ---. |  |  4x8 bytes
  ||----------------| | |  /  32 bytes
  ||    checksum    | | |
  ||----------------| | |
  ||       |        | | |
  ||       v        | | |
  |'----------------' | |
  '----------------'  | |
     .----------------' |
    v                   v

            .--------.
           .| root   |
           ||        |
           ||        |
           |'--------'
           '---|--|-'
            .-'    '-------------------------.
           v                                  v
      .--------.        .--------.        .--------.
     .| dir A  |------->| dir A  |       .| dir B  |
     ||        |       ||        |       ||        |
     ||        |       ||        |       ||        |
     |'--------'       |'--------'       |'--------'
     '---|--|-'        '----|---'        '---|--|-'
      .-'    '-.            |             .-'    '-.
     v          v           v            v          v
.--------.  .--------.  .--------.  .--------.  .--------.
| file C |  | file D |  | file E |  | file F |  | file G |
|        |  |        |  |        |  |        |  |        |
|        |  |        |  |        |  |        |  |        |
'--------'  '--------'  '--------'  '--------'  '--------'

            .--------.
           .| root   |-.
           ||        | |
   .-------||        |-'
   |       |'--------'
   |       '---|--|-'
   |        .-'    '-------------------------.
   |       v                                  v
   |  .--------.        .--------.        .--------.
   '->| dir A  |------->| dir A  |------->| dir B  |
     ||        |       ||        |       ||        |
     ||        |       ||        |       ||        |
     |'--------'       |'--------'       |'--------'
     '---|--|-'        '----|---'        '---|--|-'
      .-'    '-.            |             .-'    '-.
     v          v           v            v          v
.--------.  .--------.  .--------.  .--------.  .--------.
| file C |  | file D |  | file E |  | file F |  | file G |
|        |  |        |  |        |  |        |  |        |
|        |  |        |  |        |  |        |  |        |
'--------'  '--------'  '--------'  '--------'  '--------'

         .--------.
        .| root   |-.
        ||        | |
.-------||        |-'
|       |'--------'
|       '---|--|-'
|        .-'    '-.
|       v          v
|  .--------.  .--------.
'->| dir A  |->| dir C  |
  ||        | ||        |
  ||        | ||        |
  |'--------' |'--------'
  '--------'  '--------'

выделение dir B
=>
         .--------.
        .| root   |-.
        ||        | |
.-------||        |-'
|       |'--------'
|       '---|--|-'
|        .-'    '-.
|       v          v
|  .--------.    .--------.
'->| dir A  |--->| dir C  |
  ||        | .->|        |
  ||        | | ||        |
  |'--------' | |'--------'
  '--------'  | '--------'
              |
   .--------. |
  .| dir B  |-'
  ||        |
  ||        |
  |'--------'
  '--------'

вставка dir B в связанный список
``` Создание «осиротевшего» элемента:

Добавление каталога В в родительский каталог:

Удаление каталога:

               .--------.
              .| root   |-.
              ||        | |
.-------------||        |-'
|             |'--------'
|             '--|-|-|-'
|        .------'  |  '-------.
|       v          v           v
|  .--------.  .--------.  .--------.
'->| dir A  |->| dir B  |->| dir C  |
  ||        | ||        | ||        |
  ||        | ||        | ||        |
  |'--------' |'--------' |'--------'
  '--------'  '--------'  '--------'

remove dir B from parent directory, creating an orphan
=>
         .--------.
        .| root   |-.
        ||        | |
.-------||        |-'
|       |'--------'
|       '---|--|-'
|        .-'    '-------------.
|       v                      v
|  .--------.  .--------.  .--------.
'->| dir A  |->| dir B  |->| dir C  |
  ||        | || orphan!| ||        |
  ||        | ||        | ||        |
  |'--------' |'--------' |'--------'
  '--------'  '--------'  '--------'

In addition to normal directory tree operations, we can use orphans to evict
blocks in a metadata pair when the block goes bad or exceeds its allocated
erases. If we lose power while evicting a metadata block we may end up with
a situation where the filesystem references the replacement block while the
threaded linked-list still contains the evicted block. We call this a
half-orphan.

           .--------.
          .| root   |-.
          ||        | |

Попытка записи в каталог В:

Если бы у нас было какое-то глобальное состояние, мы могли бы также сохранить флаг и избегать поиска потерянных объектов, если бы не знали, что были специально прерваны во время манипуляции с деревом каталогов (предзнаменование!).

**Проблема перемещения**

У нас есть ещё одна проблема: проблема перемещения. Сформулировать проблему просто:

Как атомарно переместить файл между двумя каталогами?

В littlefs мы можем атомарно фиксировать каталоги, но мы не можем создать атомарную фиксацию, охватывающую несколько каталогов. Файловая система должна пройти как минимум через два различных состояния, чтобы завершить перемещение.

Что ещё хуже, перемещение файлов является распространённой формой синхронизации для файловых систем. Поскольку файловая система разработана для потери питания, важно правильно реализовать атомарное перемещение.

Итак, что мы можем сделать?

— Мы определённо не можем просто позволить потере питания привести к дублированию или потере файлов. Это может легко нарушить код пользователей и проявится только в крайних случаях. Мы могли позволить себе быть небрежными со связанным списком с потоками, потому что он не предназначен для пользователей, и мы можем обрабатывать угловые случаи внутри.

— Некоторые файловые системы распространяют операции COW вверх по дереву, пока не будет найден общий родитель. К сожалению, это плохо взаимодействует с нашим связанным деревом и возвращает проблему распространения износа вверх.

— В предыдущей версии littlefs мы пытались решить эту проблему, перемещаясь туда-сюда между источником и местом назначения, отмечая и снимая пометку с файла как перемещаемого, чтобы сделать перемещение атомарным с точки зрения пользователя. Это работало, но не очень хорошо. Поиск неудачных перемещений был дорогостоящим и требовал уникального идентификатора для каждого файла.

В конце концов, решение проблемы перемещения потребовало создания нового механизма совместного использования. **Глобальное состояние**

В littlefs глобальное состояние привело к появлению механизма, который называется «глобальное состояние».

Глобальное состояние — это небольшой набор состояний, которые можно обновить из любой пары метаданных. Объединение глобального состояния с возможностью обновления нескольких записей в одной фиксации даёт нам мощный инструмент для создания сложных атомарных операций.

Как работает глобальное состояние?

Глобальное состояние существует как набор дельт, распределённых по парам метаданных в файловой системе. Фактическое глобальное состояние можно построить из этих дельт путём применения операции XOR ко всем дельтам в файловой системе.

Чтобы обновить глобальное состояние из пары метаданных, мы берём известное глобальное состояние и применяем операцию XOR к нему, нашим изменениям и любой существующей дельте в паре метаданных. Фиксация этой новой дельты в паре метаданных фиксирует изменения в глобальном состоянии файловой системы.

Для повышения эффективности мы всегда храним копию глобального состояния в оперативной памяти. Нам нужно только перебрать наши пары метаданных и построить глобальное состояние, когда файловая система смонтирована.

Возможно, вы заметили, что глобальное состояние очень затратно. Мы храним копию в оперативной памяти и дельту в неограниченном количестве пар метаданных. Даже если мы сбросим глобальное состояние до его начального значения, мы не сможем легко очистить дельты на диске. По этой причине очень важно, чтобы мы сохраняли размер глобального состояния ограниченным и чрезвычайно малым. Но даже при строгом бюджете глобальное состояние невероятно ценно.

Теперь мы можем решить проблему перемещения. Мы можем создать глобальное состояние, описывающее наше перемещение атомарно с созданием нового файла, и мы можем очистить это состояние перемещения атомарно с удалением старого файла. |
   '--------'

begin move, add reference in dir C, change gstate to have move
=>
               .--------.    gstate = moving file D in dir A (m1)
              .| root   |-.
              ||        | |
.-------------||        |-'
|             |'--------'
|             '--|-|-|-'
|        .------'  |  '-------.
|       v          v           v
|  .--------.  .--------.  .--------.
'->| dir A  |->| dir B  |->| dir C  |
  ||        | ||        | || gdelta |
  ||        | ||        | || =m1    |
  |'--------' |'--------' |'--------'
  '----|---'  '--------'  '----|---'
       |     .----------------'
       v    v
     .--------.
     | file D |
     |        |
     |        |
     '--------'

complete move, remove reference in dir A, change gstate to no move
=>
               .--------.    gstate = no move (m1^~m1)
              .| root   |-.
              ||        | |
.-------------||        |-'
|             |'--------'
|             '--|-|-|-'
|        .------'  |  '-------.
|       v          v           v
|  .--------.  .--------.  .--------.
'->| dir A  |->| dir B  |->| dir C  |
  || gdelta | ||        | || gdelta |
  || =~m1   | ||        | || =m1    |
  |'--------' |'--------' |'--------'
  '--------'  '--------'  '----|---'
                               v
                           .--------.
                           | file D |
                           |        |
                           |        |
                           '--------'

                 .--------.    gstate = moving file D in dir A (m1)
                .| root   |-.             ^
                ||        |------------> xor
.---------------||        |-'             ^
|               |'--------'               |
|               '--|-|-|-'                |
|        .--------'  |  '---------.       |
|       |            |             |      |
|       |     .----------> xor --------> xor
|       v     |      v      ^      v      ^
|  .--------. |  .--------. |  .--------. |
'->| dir A  |-|->| dir B  |-|->| dir C  | |
  ||        |-' ||        |-' || gdelta |-'
  ||        |   ||        |   || =m1    |
  |'--------'   |'--------'   |'--------'
  '----|---'    '--------'    '----|---'
       |     .---------------------'
       v    v
     .--------.
     | file D |
     |        |
     |        |
     '--------'

               .--------.    gstate = no move (m1^~m1)
              .| root   |-.
              ||        | |
.-------------||        |-'
|             |'--------'
|             '--|-|-|-'
|        .------'  |  '-------.
|       v          v           v
|  .--------.  .--------.  .--------.
'->| dir A  |->| dir B  |->| dir C  |
  || gdelta | ||        | || gdelta |
  || =~m1   | ||        | || =m1    |
  |'--------' |'--------' |'--------'
  '--------'  '--------'  '----|---'
                               v
                           .--------.
                           | file D |
                           |        |
                           |        |
                           '--------'

begin move, add reference in dir C, change gstate to have move
=>
                .--------.    gstate = moving dir B in root (m1^~m1^m2)
               .| root   |-.
               ||        | |
.--------------||        |-'
|              |'--------'
|              '--|-|-|-'
|        .-------'  |  '----------.
|       v           |              v
|  .--------.       |          .--------.
'->| dir A  |-.     |       .->| dir C  |
  || gdelta | |     |       | || gdelta |
  || =~m1   | |     |       | || =m1^m2 | |'--------' |     |       | |'--------'
  '--------'  |     |       | '---|--|-'
              |     |    .-------'   |
              |     v   v   |        v
              |  .--------. |    .--------.
              '->| dir B  |-'    | file D |
                ||        |      |        |
                ||        |      |        |
                |'--------'      '--------'
                '--------'

Complete move, remove reference in root, change gstate to no move
=>
             .--------.    gstate = no move (m1^~m1^m2^~m2)
            .| root   |-.
            || gdelta | |
.-----------|| =~m2   |-'
|           |'--------'
|           '---|--|-'
|        .-----'    '-----.
|       v                  v
|  .--------.          .--------.
'->| dir A  |-.     .->| dir C  |
  || gdelta | |     | || gdelta |
  || =~m1   | |     '-|| =m1^m2 |-------.
  |'--------' |       |'--------'       |
  '--------'  |       '---|--|-'        |
              |        .-'    '-.       |
              |       v          v      |
              |  .--------.  .--------. |
              '->| dir B  |--| file D |-'
                ||        |  |        |
                ||        |  |        |
                |'--------'  '--------'
                '--------'