Методы синхронизации и блокировки в Linux ядре

> ??? Аллах акбар, система капут! Интересно, а как вы выключаете устройство, прерывания остаются включенными? :)

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

> А если используется один и тот же список (например tcp retransmit очередь), который нужно обрабатывать для каждого полученного пакета (tcp ack например) - пакеты добавляются из process context, а удаляются из обработчика прерываний - без запрета прерываний в process context у вас мгновенно случится deadlock или race condition на smp.

Если говорить непосредственно о TCP, то этот протокол крутится в отдельном потоке (нити_. Сверху ему приходят сообщения от userspace, снизу приходят сообщения от потока (нити) IP.

TCP пакеты упорядочены по времени retransmita. Когда приходит ack, пакет удаляется из очереди и освобождается. Кстати, TCP тоже совмещает вход для запросов сверху и пакетов от IP слоя.

На событие приёма ставится таймаут retransnmition пакета, который первый в очереди (а они отсортированы по возрастанию).

Если за случился таймаут, то есть не пришёл ack, то осуществляется повторная передача или, если счетчик retransnmition обнулился, дропанье пакета с соответсвующей сигнализацией в юзерспейс.

В ситуации, когда когда вместо ack пришёл новый запрос от юзерспейса, например запись или чтение в другой сокет. Разница таймаута ack для первого пакета в очереди - пересчитыватся. Но это очень быстрая операция. И только для первого пакета в очереди.

Не, так нельзя. Я сейчас все профессиональные секреты и Knoow How открою и чего мне тогда делать? :)

> Т.е. 3 переключения контекста. Наверное они еще и на разных уровнях защиты живут (userspace на 3, сервисы на 1, само ядро наверное на 0), т.е. вы намеренно в 3 (!) раза ухудшили производительность.

Насколько я знаю, уровни защиты в L4 не используются. Их с успехом заменяет страничная виртуальная память.

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

В нормальном случае - Сервис 1 и Сервис 2 в одном контексте. Т.е. выходит то же, что и в Linux/Windows.

Ничего не мешает поместить Сервис 1, Сервис 2 и пользовательское приложение в одно адресное пространство. Даже алгоритм работы меня не нужно. Только оперирование адресными пространствами. Сомневаюсь, что кто-нить перебить быстродействие системы при такой организации.

> Далее, завершение чтения блока сигнализируется прерыванием ide контроллера, как и кем это прерывание будет обработано?

Это прерывание обрабатывает исключительно сервис IDE контроллера. Более того, сервис IDE контроллера ничего не знает об очереди блоков. Он тупо читает/пишет блоки. Хотете реализовать схему лифта для минимизации движения головки винта? Не проблема. Создавайте сервис /dev/hda_cached поверх /dev/hda. Саиое интересно, что такой сервис будет являться фильтром в чистом виде, то есть его можно воткнуть между файловой системой и серсивом IDE контроллера. Причём, без правки хоть одной строчки кода в файловой системе. Сервис "лифта" снаружи выглядит точно так же, как и сервис IDE контроллера.

Интеллектуальные беседы на моём ЛОРе? Нет пути!

Я сожалею, что у меня из предложений выпадают целые слова. :(

>Насколько я знаю, уровни защиты в L4 не используются. Их с успехом заменяет страничная виртуальная память.

Т.е. userspace крутится в нулевом кольце? :)))

>Если говорить непосредственно о TCP, то этот протокол крутится в отдельном потоке (нити_. Сверху ему приходят сообщения от userspace, снизу приходят сообщения от потока (нити) IP.

Ога, и как они синхронизируются, если случается одновременная запись и прерывание (сразу после начала добавления элемента в список или в любой другой "неподходящий" момент?), в котором обрабатывается ack и удаляется пакет? Без выключения прерываний говорите? :)

Эта система неработоспособна. Даже если забыть о ее скорости. Даже если забыть, что нет никакого разделения процессов между собой (раз они все в одном кольце).

В морг :)

>> Далее, завершение чтения блока сигнализируется прерыванием ide контроллера, как и кем это прерывание будет обработано?

>Это прерывание обрабатывает исключительно сервис IDE контроллера. Более того, сервис IDE контроллера ничего не знает об очереди блоков.

У вас 2 клиента, каждый читает с диска - два запроса в очереди (один в ide контроллере, один ждет), если контроллер поддерживает много дескрипторов (а наверняка так и есть), то увеличиваем число клиентов до того момента, как свободных дескрипторов не остается.

Итак, сервис ide контроллера имеет очередь запросов от различных пользователей, с одной стороны пользователи, с другой аппаратное прерывание, сигнализирующее о готовности блока...

> Т.е. userspace крутится в нулевом кольце? :)))

Не совсем так. Правильней будет сказать что часть ядра крутится в юзерспейсе. Т.е. если мы передаём сообщение от потока к потоку, которые находятся в одной адресном пространстве, входа в нулевое кольцо может и не быть. Если память мне не изменяет, то есть только два кольца 0 и 3. Но это зависит от платформы. А чем Вас страничная защита не устраивает?

> Ога, и как они синхронизируются, если случается одновременная запись и прерывание (сразу после начала добавления элемента в список или в любой другой "неподходящий" момент?), в котором обрабатывается ack и удаляется пакет? Без выключения прерываний говорите? :)

Я терпеливый. Щас покажу.

while ( true )
{
   L4_ThreadId_t tid;
   L4_MsgTag_t   tag;

   tag = L4_Wait( L4_TimePeriod( tmout ), &tid );
   if( L4_IpcFiled(tag) )
   {
     // За период tmout не получили ни одного сообщения.
     // Обрабатываем первый TCP пакет в очереди
     сontinue
   }
   if( L4_ThreadNo(tid) > mac+irq_number )
   {
     // Получили запрос на запись/чтение от IP слоя, Смотрим, чего ему надо
     switch( L4_Label(tag) )
     {
       case WriteEtherentFramу:
         // тут всё понятно.
         break;
       case ReadyToReadReceiveEtherentFrame:
         // тут тоже всё понятно.
         break;
       default:
          // По-видимому чужой запрос или неподдерживаемый протокол.
          break;
     }
  
   }
   else
   {
     // Полчили прерывание. Проверяем статус прерывания сетевой карты
     // в зависимости от статуса выполняем обработку прерывания
     // Затем подтверждаем прерывание.
   }
}

Вот и всё! Одновременно может прийти только одно из трёх событий - таймаут, запрос или прерывание. Где тут пересечение? Где?

> Эта система неработоспособна. Даже если забыть о ее скорости. Даже если забыть, что нет никакого разделения процессов между собой (раз они все в одном кольце).

Эта система реально работает. Система реально работает. Реально работает. Работает.

s/mac\+irq_number/max_irq_number

> Итак, сервис ide контроллера имеет очередь запросов от различных пользователей, с одной стороны пользователи, с другой аппаратное прерывание, сигнализирующее о готовности блока...

Выше шаблон - там наглядно всё показано.

ide от ethernet будет отличаться меткой сообщения, которая берётся при помощи L4_Label(tag).

s/L4_IpcFiled/L4_IpcFailed/

> Даже если забыть, что нет никакого разделения процессов между собой (раз они все в одном кольце).

Погуглите на предмет address space.
Одно кольцо никак не значит что нет разделения процессов.
Именно адресные пространства отличают процесс от потока(нити).

> Чего тут спорить? Есть у тебя две нити и два процессора. Одна посылает сообщение второй, тем самым пробуждая её. Даже если ты отдашь остаток кванта второй нити, первая тут же снова встанет на исполнение (в предположении, что у нее есть чем занятся), так как второму процессору делать нечего, и она тут же может поставить ещё одно сообщение, а вторая нить в это время сообщение вынимает...

Вы о фьютексах?

http://kerneldump.110mb.com/dokuwiki/doku.php?id=wiki:futexes_are_tricky_p1

на русском

> Но это уровень микроядра. В идеале это должно быть реализовано аппаратно на уровне микропроцессора. А в ядре защёлки не нужны.

Видимо, в данном треде неблюдается тотальное взимонепонимание и несогласованность терминологии.

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

Я вообще плохо понимаю концепцию "ядро" в контексте микроядерного подхода.

> Одно кольцо никак не значит что нет разделения процессов.

Одно кольцо - это значит, что любое приложение может обойти страничную защиту (при желании или случайно). Вряд ли разработчики L4 настолько ламеры, что позволят userspace работать в нулевом кольце :)

> У меня, пожалуй, не хватит слов, чтобы спеть песню, посвящённую реалтайму на синхронных сообщениях. С точностью до такта процессора. Это элементарно. Но я бы хотел эту идею запатентовать

Молодой человек, пристройтесь в конец длинной очереди из достойных и заслуженных людей. Ну или хотя бы почитайте о CSP, Occam и Ada ;)

> Видимо, в данном треде неблюдается тотальное взимонепонимание и несогласованность терминологии.

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

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

> Я вообще плохо понимаю концепцию "ядро" в контексте микроядерного подхода.

Никогда не задумывался об этом. Предлагаю "ядром" считать "L4 roottask" и совокупность сервисов, которые обеспечивают POSIX функциональность.

> Одно кольцо - это значит, что любое приложение может обойти страничную
> защиту (при желании или случайно). 

Честно говоря, с этим вопросом не разбирался. L4 работает на множестве процессоров:     
    * Alpha (21164, 21264)
    * AMD64 (Opteron 242, Simics)
    * ARM (SA1100, XScale, ARM925T)
    * IA32 (Pentium and higher)
    * IA64 (Itanium1, Itanium2, Ski)
    * MIPS 64bit (R4000, R5000)
    * PowerPC 32bit (IBM 750)
    * PowerPC 64bit (Power3, Power4)

Не уверен, что все они поддерживают понятие колец защиты.
Интересно, каким образом Вы запишите/прочитаете память, чья страница не 
отображена в адресное пространство потока (нити)?

> Вряд ли разработчики L4 настолько ламеры, что позволят userspace работать в нулевом кольце :)

Хе-хе. Я совершенно доверяю разработчикам L4. В особенности команде L4Ka.

> Молодой человек, пристройтесь в конец длинной очереди из достойных и заслуженных людей. Ну или хотя бы почитайте о CSP, Occam и Ada ;)

Надеюсь, одно другого не исключает? :)

В любом случае, спасибо.

Я немного упорядочил поток сознания, который вылил в эту тему.

Если кто заинтересовался, вот пример с подробнейшими комментариями - http://mandrykin.livejournal.com/2819.html

>Эта система реально работает. Система реально работает. Реально работает. Работает.

Так вы даже не показали ни одной очереди - как раз там все блокировки и происходят, с выключением прерываний и т.п.

Кстати, вы еще и удалили немало кода (например откуда берется tag).

>Не уверен, что все они поддерживают понятие колец защиты.

Просто называется это по разному, но поддерживают все.

>Интересно, каким образом Вы запишите/прочитаете память, чья страница не отображена в адресное пространство потока (нити)?

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

>> Вряд ли разработчики L4 настолько ламеры, что позволят userspace работать в нулевом кольце :)

>Хе-хе. Я совершенно доверяю разработчикам L4. В особенности команде L4Ka.

Я бы не удивился, что там все работает на 0 кольце - это не в L4 необходимом самому приложению делать преобразования адресов?

>Одно кольцо никак не значит что нет разделения процессов. Именно адресные пространства отличают процесс от потока(нити).

Хмм, так кто же переключает адресные пространства? Это привилегированная операция, стало быть что-то на более низком уровне защиты, следовательно есть специальное ядро.

Или действительно все процессы в L4 крутятся в нулевом кольце и могут лезть в память друг друга.

>Если память мне не изменяет, то есть только два кольца 0 и 3.

По-разному, например на x86 есть несколько колец, xen использует это для разделения гостей. На x86_64 (и то только в новых процессорах) только 2 кольца, но есть аппаратный тег для страниц (один бит для guest/host).

> Так вы даже не показали ни одной очереди - как раз там все блокировки и происходят, с выключением прерываний и т.п

Вы имеете в вижу в примере из ЖЖ? Если да, то посмотрите в сторону функций write_data_to_device( &msg ), read_from_device( &msg ), handle_interrupt(). Которые управляют сразу двумя (!) очередями. Очередь приёма и очередь передачи.

> Кстати, вы еще и удалили немало кода (например откуда берется tag).

Я не удалил не строчки кода. Просто, вместо copy'n'paste из проекта, набирал этот пример прям здесь.

> Простите, а кто переключает адресное пространство? Если приложение на том же уровне защиты, то значит и текущее приложение может изменить. Если на более низком уровне, значит вот вам и ядро, которому нужно отключение прерываний и т.п.

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

> Хмм, так кто же переключает адресные пространства? Это привилегированная операция, стало быть что-то на более низком уровне защиты, следовательно есть специальное ядро.

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

Кстати, для архитектуры x86 существует понятие small address space. Честно говоря, я так и не разобрался, что это означает, возможно что все процессы в одном кольце с микроядром. Но мне это не интересно.

> откуда берется tag

tag это переменная типа L4_MsgTat_t

Вот так он определён в файле message.h из userspace L4Ka:

/*
 * Message tag
 */

typedef union {
    L4_Word_t	raw;
    struct {
#if defined(L4_BIG_ENDIAN)
	L4_Word_t	label:16 __PLUS32;
	L4_Word_t	flags:4;
	L4_Word_t	t:6;
	L4_Word_t	u:6;
#else
	L4_Word_t	u:6;
	L4_Word_t	t:6;
	L4_Word_t	flags:4;
	L4_Word_t	label:16 __PLUS32;
#endif
    } X;
} L4_MsgTag_t;

Назначение тега - хранить информацию о сообщение и его статус
приёма/передачи сообщения. Тег однозначно описывает формат сообщения.
Более подробную информацию о теги и сообщениях смотрите в спецификации
L4: http://l4ka.org/projects/pistachio/l4-x2-r5.pdf

> Оно не умерло?

Оно ещё переживёт Linux, Windows и нас с вами.

>Тут надо сильно постараться в момент дизайна системы. Блокировки разруливаются конечными автоматами. Причём, разруливаются легко и красиво.

звучит очень убедительно! я верю, саду цвесть. гуру, зарони искру света божьега во тьму сортира действительности.

особенно хорошо в качестве документации читать вот это "разруливаются легко и красиво", даже схемы не надо прилагать и кода на C. верую!

> звучит очень убедительно! я верю, саду цвесть. гуру, зарони искру света божьега во тьму сортира действительности.

> особенно хорошо в качестве документации читать вот это "разруливаются легко и красиво", даже схемы не надо прилагать и кода на C. верую!

Я бы понял, если бы этот пост появился в начале обсуждения. Но после всего сказанного...

>Я бы понял, если бы этот пост появился в начале обсуждения. Но после всего сказанного...

Вы так и не написали автомат работы списка без блокировок. Так что коментарий уместен.

>tag это переменная типа L4_MsgTat_t

Вопрос был не в том, что это такое, а как он передается и откуда берется. А берется он после добавления пакета в очередь в обработчике прерываний (с выключенными прерываниями кстати), с блокировкой. Откуда затем он удаляется и передается в написанную функцию. Так что, показав кусок кода, вырвав его из контекста, вы ничего не доказали.

В микроядре так же есть spin-блокировки, так же выключаются прерывания, только дополнительно в несколько раз ухудшена производительность.

> Вы так и не написали автомат работы списка без блокировок. Так что коментарий уместен.

write_data_to_device( &msg ) - вставляет пакет в хвост списка передачи

read_from_device( &msg ) - выбирает пакет из головы списка приёма

handle_interrupt() - анализирует, чем вызвано прерывание
в случае, если прерывание вызвано приёмом пакета из устройства,
то пакет добавляется в хвост списка, приёма.
в случае, когда прерывание вызвано готовностью устройства к передаче,
пакет добавляется, выбирается пакет из головы списка передачи.

           _блокировки обеспечиваются микроядром_

Необходимость использовать функции pthread_mutex_lock, 
EnterCriticalSection и запрета прерываний отпадает полностью.

> Вопрос был не в том, что это такое, а как он передается и откуда берется.

Tag - это результат работы IPC. Его значение возвращает микроядро, после передачи/приёма сообщения.

> А берется он после добавления пакета в очередь в обработчике прерываний (с выключенными прерываниями кстати), с блокировкой. Откуда затем он удаляется и передается в написанную функцию.

О какой очереди Вы говорите? Очереди сообщений - это более высокий уровень абстракции.

> Так что, показав кусок кода, вырвав его из контекста, вы ничего не доказали.

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

> В микроядре так же есть spin-блокировки, так же выключаются прерывания, только дополнительно в несколько раз ухудшена производительность.

На счёт spin-блокировок ничего не скажу, может и есть, может и нет. Только вот на счёт ухудшения производительности я привык больше доверять своим глазам, чем общепринятым заблуждениям.

>write_data_to_device( &msg ) - вставляет пакет в хвост списка передачи

:)) вы, похоже, вообще не разбираетесь в коде, извините :)

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

Пример из ядра Linux: вы бы сказали, что функция skb_queue_tail() добавляет пакет в очередь. Это так, но на самом деле эта функция выключает прерывания, работает со списком, обновляет различные статистические переменные и т.п. Она вызывается как из прерывания (softirq), так и из process context, поэтому она обязана выключать прерывания.

Хотя в вашем linux аналоги скорее будут sys_send() и sys_recv() :)

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

Да, для вызова read_from_device() не нудны блокировки, просто потому, что они есть внутри. Точно так же как для sys_recv().

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

Вы действительно считаете, что 20 строк кода, это "шаблон, на основе которого можно написать _любой_ драйвер _любого_ устройства"?

Попробуйте как-нибудь, о результатах потом расскажите. Будет очень интересно посмотреть на дрйвер сетевого адаптера, написанного по этому "шаблону" :)

> Попробуйте как-нибудь, о результатах потом расскажите. Будет очень интересно посмотреть на дрйвер сетевого адаптера, написанного по этому "шаблону" :)

http://www.osrc.info/plugins/forum/forum_viewtopic.php?3777

> Вы действительно считаете, что 20 строк кода, это "шаблон, на основе которого можно написать _любой_ драйвер _любого_ устройства"?

Я это _знаю_.

   http://community.livejournal.com/l4os/