Персистентная ОС: ничто не блокируется

    Это — статья-вопрос. У меня нет идеального ответа на то, что здесь будет описано. Какой-то есть, но насколько он удачен — неочевидно.

    Статья касается одной из концептуальных проблем ОС Фантом, ну или любой другой системы, в которой есть персистентная и «волатильная» составляющие.

    Для понимания сути проблемы стоит прочесть одну из предыдущих статей — про персистентную оперативную память.

    Краткая постановка проблемы: В силу того, что прикладная программа в ОС Фантом персистентна (не перезапускается при перезагрузке), а ядро — нет (перезапускается при перезагрузке и может быть изменено между запусками), в такой системе нельзя делать блокирующие системные вызовы. Обычным способом.

    Действительно: если прикладная программа сделает вызов в ядро и в таком состоянии мы сделаем снапшот, то совершенно непонятно, как такой снапшот восстанавливать. Ядро снапшотом не фотографируется, записывается и восстанавливается только память прикладных программ. Непонятно, где она там в ядре была. Непонятно, в правильное ли, вообще, место в ядре указывает фактическая точка входа. Непонятно, какие объекты прикладного уровня ядро трогало и создало для себя.

    Отдельно непонятно, насколько в таком состоянии можно делать снапшот — не трогает ли ядро объекты как раз когда мы их записываем на диск.

    Для начала опишем интерфейсы для доступа по данным между ядром и объектной средой.

    Объектная среда имеет интерфейс в ядро в виде встроенных классов — аналог native в Java. Эти классы реализованы в ядре в виде функций Си, которые соответствуют методам. Блокироваться такие функции не могут — обязаны вернуться ASAP, и пока они исполняются — снапшоты невозможны. Этого достаточно для простых методов типа window.paintLine() или string.concat(), но не более того.

    Банальный пример (исходник):

    static int si_string_8_substring(struct pvm_object me, struct data_area_4_thread *tc )
    {
        DEBUG_INFO;
        ASSERT_STRING(me);
        struct data_area_4_string *meda = pvm_object_da( me, string );
    
        int n_param = POP_ISTACK;
        CHECK_PARAM_COUNT(n_param, 2);
    
        int parmlen = POP_INT();
        int index = POP_INT();
    
        if( index < 0 || index >= meda->length )
            SYSCALL_THROW_STRING( "string.substring index is out of bounds" );
    
        int len = meda->length - index;
        if( parmlen < len ) len = parmlen;
    
        if( len < 0 )
            SYSCALL_THROW_STRING( "string.substring length is negative" );
    
        SYSCALL_RETURN(pvm_create_string_object_binary( (char *)meda->data + index, len ));
    }
    


    Если содержимое обычного объекта — только ссылки, то internal class object содержит произвольную структуру данных, недоступную виртуальной машине через обычные инструкции, но доступную внутри методов, написанных на си — struct data_area_4_string, в данном примере.

    Очевидно, что такие методы могут работать со структурами данных ядра, если добудут доступ к ним. Но обратное неверно — ссылку на себя они оставить в ядре не могут. Вернее, могут, но с некоторыми «но».

    Их два.

    Во-первых, нужно, чтобы сборщик мусора знал, что некоторый объект доступен из ядра и не «собрал» его, даже если ссылки из объектного мира кончились.

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

    Что касается сборщика мусора, то это реализуется вот каким способом. В корневом объекте объектной среды присутствует, среди других объектов, так называемый restart list — простой список объектов. Любой объект internal класса может в него добавиться:

    void pvm_add_object_to_restart_list( pvm_object_t o );
    void pvm_remove_object_from_restart_list( pvm_object_t o );
    


    Нахождение в таком списке (а любой объект, с которым работает ядро, должен в нём быть) обслуживает две задачи. Во-первых, гарантирует наличие ссылки на объект «от имени ядра» — эта ссылка помешает GC убить объект, даже если про него все другие объекты забудут.

    Во-вторых, решается вот какая проблема. Предположим, мы сделали объект «устройство», поработали с ним, он попал в снапшот, после чего систему перезагрузили через reset. При рестарте ядра оно должно как-то узнать о проблеме и либо восстановить связь такого объекта с ядром, либо сообщить ему, что всё — оживить его не получается. (Например, если соответствующее устройство вынули из компьютера.)

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

    (См. root.h)

    Хорошо, но мало. Всё же, наверное, мы хотим каким-то образом из объектной среды сделать read() и дождаться результата. Без блокировки прямого вызова из нити виртуальной машины внутри инструкции.

    Я рассматривал три варианта реализации.

    1. Промежуточная остановка: блокирующий системный вызов состоит из пары: инициирующего и считывающего вызовов. Между ними, на границе инструкции, виртуальная машина блокируется. Если случается снапшот и рестарт — машина рестартует со второй инструкции и получает явный отказ.
    2. Коллбек: по окончании выполнения длинной операции объектная среда получает обратный вызов из ядра.
    3. Псевдо-окончание операции: Блокирующий вызов работает именно как блокирующий вызов — уходит в ядро и там ожидает сколь угодно долго. Но перед этим вызов делает вид, что завершился — кладёт на стек нулевую ссылку, как если бы в реализации было написано return null;, а по окончании работы снимает этот null и заменяет фактическим результатом.


    Сейчас реализован последний способ. Остальные два я счёл крайне неудобными в применении.

    Он тоже неидеален — лучше бы, конечно, рестартовать запрос при рестарте ядра, а не выдавать отказ. В принципе, это тоже реализуемо.

    Объясню более подробно, почему всё это важно.

    Виртуальная машина (интерпретатор) работает в цикле, исполняя инструкцию за инструкцией. При рестарте ядра виртуальные машины рестартуют — ядро пробегает все объекты типа .internal.thread и запускает их. В том состоянии, в котором они были на момент запуска ядра.

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

    (Куда прилетает управление после рестарта)

    Соответственно, если мы блокируем нить интерпретатора (или JIT-кода, неважно), нужно, чтобы состояние было целостным — обязательно на границе инструкции, и всё, что важно для объектной среды — лежит в персистентной памяти.

    (Полный код: Функция, которая реализует блокирующий вызов)

    Что для этого делается.

    Для начала, сделаем вид, что инструкция виртуальной машины исполнилась. То есть — прочитала со стека параметры и положила на стек «ошибочный» код возврата, null. Если мы попадём в снапшот и потом будем убиты, именно это будет итогом работы инструкции в сохранённом состоянии виртуальной машины.

        int n_param = POP_ISTACK;
        CHECK_PARAM_COUNT(n_param, 2); // Кидает exception, если не 2 параметра
    
        int nmethod = POP_INT();
        pvm_object_t arg = POP_ARG;
    
        // push zero to obj stack
        pvm_ostack_push( tc->_ostack, pvm_create_null_object() ); 
    


    Дальше мы почти что вольны делать что хотим. Почти.

    Дело в том, что для формирования снапшота код подсистемы виртуальной памяти останавливает все нити виртуальных машин, и проверяет, что они остановились. Если он как раз сейчас это делает или будет делать позже — скажем ему, что мы как будто бы остановились — мы же действительно перестали выполнять код виртуальной машины. Да — и перед всем этим скажем интерпретатору, чтобы все свои закешированные переменные положил обратно в объекты, в которых они должны лежать (save_fast_acc). Заодно проверим, нет ли, вообще, запроса на останов виртуальных машин (шатдаун) — если есть, то исполним его.

        pvm_exec_save_fast_acc(tc); // Before snap
    
        if(phantom_virtual_machine_stop_request)
            hal_exit_kernel_thread();
    
        hal_mutex_lock( &interlock_mutex );
    
        phantom_virtual_machine_threads_stopped++;
        phantom_virtual_machine_threads_blocked++;
        hal_cond_broadcast( &phantom_snap_wait_4_vm_enter );
    
        hal_mutex_unlock( &interlock_mutex );
    


    Выполним сам запрос. По окончании освободим переменную (ссылку на аргумент).

        // now do syscall - can block
        pvm_object_t ret = syscall_worker( this, tc, nmethod, arg );
        ref_dec_o( arg );
    


    Сообщим подсистеме снапшотов, что мы закончили свои дела и хотим снова уйти в интерпретатор. Если она возражает (идёт снапшот) — поспим, пока она нас не разбудит.

        hal_mutex_lock( &interlock_mutex );
    
        if(phantom_virtual_machine_snap_request)
            hal_cond_wait( &phantom_vm_wait_4_snap, &interlock_mutex );
    
        phantom_virtual_machine_threads_stopped--;
        phantom_virtual_machine_threads_blocked--;
    
        hal_cond_broadcast( &phantom_snap_wait_4_vm_leave );
    
        hal_mutex_unlock( &interlock_mutex );
    


    Всё сделано, снимем со стека виртуальной машины фейковое возвращаемое значение, запишем реальное.

        // pop zero from obj stack
        pvm_ostack_pop( tc->_ostack );
        // push ret val to obj stack
        pvm_ostack_push( tc->_ostack, ret );
    


    В целом, эта реализация работает. Но в ней есть тонкая ошибка. Система генерации снапшотов проверяет не только что все нити уснули перед формированием снапшота, но и что все они проснулись. Нетрудно видеть, что если какая-то нить заблокируется навечно, то она же навечно остановит и снапшоты (потому что не «проснётся»).

    Попытка решить эту проблему в лоб (посчитать количество заблокированных нитей и учесть при подсчёте остановленных/запущенных) не привела к успеху: целостность объектного стейта нарушается.

    Возможно, в решении есть подводные камни, которые я пока не вижу.

    На сём я пока прекращаю дозволенные речи и иду пить чай. :)

    Комментарии 18

      +6
      … А еще можно сделать модную нынче стейтлесс асинхронность.
      Хочешь прочитать кусок файла — сделай read (да чего уж там, сразу get) запрос по ури вида /path/to/file?start=xxx&len=yyy и жди ответа асинхронно (внутре либы это не обязательно делать через колбэки; epoll рулит тащемта и в смысле организации кода по типу горутин, и в смысле производительности).
      При воскрешении снэпшота запрос read/get запрос тупо повторяется, если он не был завершен в прошлый раз. И да, write (put) и delete — тоже идемпотентные, т.е. их можно повторять. Проблемы — только с new (post). Но для таких вещей — транзакции.
      На выходе получаем систему, в которой работающие треды можно прозрачно перебрасывать между серверами например, для балансировки нагрузки, отказоустойчивости и всего такого.
      Ну это так, мысли в слух.
        0
        Нуда, давайте навяжем на все новомодные REST, сделаем GUI на HTML и прочие приблуды, а потом будем просить пользователя купить новомодный i7 с 8 физическими ядрами.
          +1
          Синтаксис запроса вторичен. Конечно, никто не будет парсить URI на системных вызовах. А в остальном — всё верно там написано.
        +1
        Такие мысли меня тоже посещают.
        • НЛО прилетело и опубликовало эту надпись здесь
            +2
            Старый добрый Fluke с неблокирующимися системными вызовами: https://www.usenix.org/legacy/events/osdi99/full_papers/lepreau/lepreau.pdf, плюс еще и ядерных стеков не надо.
              +1
              Ядерные стеки-то — чёрт с ними, а в остальном — да, очень перекликается. Спасибо.

              (Кстати, интересное пересечение — нулевая версия ядра фантома использовала в качестве базы oskit, на котором и fluke базировался.)
              0
              Немного не в тему, но меня давно мучает вопрос про таймауты. Как организуется с ними работа в Фантоме. К примеру, я делаю чтение с жесткого диска. После запроса данных с жёсткого диска, но до их полного получения машина засыпает. Допустим, после пробуждения, стейтлесс асинхронность и транзакции позлят продолжить чтение файла с того места где программа остановилась. С точки зрения программы прошли доли секунды (вернее, несколько инструкций процессора), но если взять таймаут как разницу времени, то он может оказаться достаточно большим, чтобы решить, что в процессе чтения данных есть проблемы.
              Как предполагается отличать проблемный (долгий) таймаут, от таймаута выспавшейся программы?
                +1
                Все объекты прикладного уровня, имеющие отношения с ядром при рестарте получают уведомление о случившемся, соответственно — могут принять его во внимание, чтобы отличить эти два случая. См. restart_list выше.
                0
                Просто коментарий: не лучше ли было на прикладном уровне реализовать принцип «let it fault»? То есть сделать некое подобие контекста транзакции для доступа к системным ресурсам (ядру). Вне контекста ресурсы недоступны. При изменении ядра или перезапуске системы данные программы восстанавливаются, однако ресурсы, задействованные транзакцией, становатся невалидными и при следующем доступе по хендлу генерируют исключение. Вся транзакция откатывается на момент начала и прозрачно рестартует: снова запрашиваются ресурсы и выполняются необходимые операции.
                  0
                  По-моему, весь этот геморрой связан исключительно с тем, что формирование снапшотов и вызовы в ядро могут пересекаться по времени. Как будто бы, корень проблемы именно в этом. Но неужели это так уж необходимо? Можно было бы делать все системные вызовы таким образом, чтобы они не сразу выполнялись, а сначала происходила проверка «далеко ли до следующего снапшота?» Если следующий снапшот ещё не скоро, то вызов уходит в ядро и к моменту снапшота уже успевает вернуться. Если же следующий снапшот уже идёт или вот-вот начнётся, то системный вызов просто шедулится на время «сразу после снапшота». Думаю, все и так понимают, что системные вызовы — это такая вещь, которая быстро не делается. Ну, подумаешь, придётся программе несколько лишних миллисекунд подождать в том случае, если она сделала свой вызов в неудачное для системы время. Это не смертельно.
                    0
                    Системный вызов чтения байта с клавиатуры может быть заблокирован на месяц. Когда я в отпуске. :)
                      0
                      Так это же основная фича персистентной ОС. Я имею в виду то, что время для программ останавливается. Разве нет? Если между системным вызовом чтения с клавиатуры и возвратом из него пользователь успел побывать в отпуске, то вряд ли программе в качестве результата вызова нужен код той клавиши, которую пользователь нажал до отпуска.
                        0
                        «формирование снапшотов и вызовы в ядро могут пересекаться по времени.» — это вызов в ядро. Если он будет блокировать снапшоты, то они не будут происходить месяц.
                          0
                          Кто он? И зачем ему блокировать снапшоты? Наоборот, снапшоты должны блокировать всех.
                            0
                            «Действительно: если прикладная программа сделает вызов в ядро и в таком состоянии мы сделаем снапшот, то совершенно непонятно, как такой снапшот восстанавливать.»
                              0
                              Всё верно. Я именно об этом и говорю. Хорошо бы делать снапшоты не во время выполнения вызовов в ядро со стороны прикладных программ, а строго между такими вызовами. В тех случаях, когда программа делает вызов не вовремя, исполнение этого вызова можно просто откладывать. Вопрос только в том, почему так не сделано изначально. Наверняка, не просто так. Видимо, возможность выполнять системные вызовы, не откладывая, имеет какое-то принципиальное значение. К сожалению, я не понимаю, почему это так важно.
                                0
                                Если вызов длится месяц, то «строго между вызовами» — это «через месяц».

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое