Intel MP & cache coherence (продолжение)

> > очень может быть. но. вы не знаете наверное, когда этот mov начнет
> > выполняться, даже на pentium'ах есть write buffers. причем здесь
>
> пусть запись ведется через выход на шину lock xchg..., а чтение - через mov.
> Тогда имеет место атомарность (при условии выровненных данных

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

я только говорил про порядок, в котором эти изменения будут видеть
другие процессоры.

> > нет, совершенно точно не только по этой причине. порядок передачи
> > данных может изменить и шина
>
> Для выровненных данных порядок не может измениться, тк все данные
> передаются в одной шинной транзакции

если говорить конкретно про intel - очень может быть, я не знаю.
я ведь писал, что i386, кажется, strong ordered. что же касается
других архитектур, то это может происходить, но - опять-таки - не
знаю точно.

но. дело же не только в том, в каком порядке эти данные окажутся в
микросхеме памяти. дело еще и в том, в каком порядке они придут к
другому процессору.

говоря "совершенно точно", я имел в виду следующее:

CPU0:
        to_be_printed = 100;
        wmb();
        please_print = 1;

CPU1:
        if (please_print) {
                rmb();
                printf("%d", to_be_printed);
        }

для корректной работы необходимы оба барьера, это я знаю точно.
даже на intel процессор без барьера может прочитать сначала
to_be_printed, а потом please_print.

и дело не только в переупорядочивание кода самим процессором.
насколько я знаю, процессор может зашедулить сначала чтение
mem1, потом mem2, и второй результат получить раньше (про
cache сейчас не говорим).

но я не знаю, возможно ли такое на pentium. если вы скажете,
что нет - я поверю.

еще раз повторю, я в этом не слишком хорошо разбираюсь.

> я только говорил про порядок, в котором эти изменения будут видеть
> другие процессоры.

порядок, и _когда_ эти изменения будут видны.

опять же, если вы скажете, что в случае intel
после завершения xchg() обычный mov на другом
процессоре гарантированно вернет новое значения,
я могу поверить вам на слово. но, насколько я
знаю, вообще говоря, это не так.

а просто запись без asm("lock") - точно не гарантирует,
даже на intel, с чего и начался разговор :)

>секунду. атомарность записи (для выровненных данных) всегда имеет место быть

да

>разве только компилятор из вредности станет запмсывать слово побайтно.

Угу. Я просто уточнил к тому, что натурально выровненные данные - не особый случай, а очень даже общий и невозможно корректным способом получить невыровненные данные, к тому, что можно a priori данные считать выровненными.

>я только говорил про порядок, в котором эти изменения будут видеть другие процессоры.

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

>если говорить конкретно про intel - очень может быть, я не знаю. >я ведь писал, что i386, кажется, strong ordered. что же касается >других архитектур, то это может происходить, но - опять-таки - не >знаю точно.

Тут опять речь про барьеры, а не когерентность кеша. :)

>опять же, если вы скажете, что в случае intel
>после завершения xchg() обычный mov на другом
>процессоре гарантированно вернет новое значения,
>я могу поверить вам на слово. но, насколько я
>знаю, вообще говоря, это не так.

Просто я процесс представляю таким образом (под данными понимаются натурально выровненные данные):

есть n процессоров, на которых ведутся вычисления и используется
общая кешированная память (write back), любое операция по изменению данных влечет за собой изменение ячейки кеша (тут Вы справедливо отметили, что есть еще FIFO буферы, так что сие изменение происходит с точностью до буферизации), операция по изменению ячейки кеша выводит операцию на snoop bus(удаляет cache alias на других процессорах).

write buffering портит всю концепцию поддержки когерентности, посему приходится синхронно выпихивать весь FIFO на шину (для чего как раз годится изменение под префиксом lock, можно было бы делать lock mov, но у intel нет lock mov, посему xchg lock).

>а просто запись без asm("lock") - точно не гарантирует,
>даже на intel, с чего и начался разговор :

Насчет буферизация Вы были абсолютно правы! Трудно не признать... до сего момента я думал о некой целостности концепции cache coherence в Intel MP, но тем не менее речь шла не столько о самой методике поддержки когерентности, сколько о ее существовании (в котором Вы усомнились для Intel).

Вернее, не синхронизации кеша, а возможности синхронного-согласованного представления данных на всех процессорах(с точностью до такта).

> Тут опять речь про барьеры, а не когерентность кеша. :)

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

> Просто я процесс представляю таким образом

наверное, так оно и есть. хотя знать это полезно, но, в общем-то
и необязательно, можно просто полагаться на правильность реализации
барьеров в system.h.

а вот чего я никак не могу понять, это как связан spin_unlock()
и барьеры. вроде бы, unlock в каком-то смысле является partial
barrier, но что это означает, я не имею представления.

Murr, Вы случайно (или специально :) не знаете?

idle:

насчет spin - вопрос интересный.
Ну логически понятно, что обращение к защищенному спином коду не должно на уровне executive unit переупорядочиваться с кодом взятия самого спина, аналогично unlock. Теоретически взятие и отпускание spin-lock должны быть и барьерами (rw); почему в DocBook они названы partial - непонятно.

Если верить Гуку, то префикс lock вызывает FIFO flush на Intel, соответственно и spin_lock и spin_unlock на Intel являются как минимум write barriers. Возможно, lock на шине вызывает еще какие-то действия со стороны остальных процессоров так, что он является и read barrier.

Все ёто очень интересно и в связи с нашим code cleaning надо понять, что же реально творится в SMP (хотя бы для IA-32 и Оптеронов)...

> Теоретически взятие и отпускание spin-lock должны
> быть и барьерами

вот как бы и нет. я припоминаю (вроде бы :), что не один
раз встречал патчи, где добавлялся барьер после unlock()
с комментарием, что unlock не достаточно.

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

мог бы ясно сформулировать вопрос по английски - спросил
бы на lkml.

кстати, помнится как-то некий Andrew Morton утержал, что
он уже давно прекратил всякие попытки понять memory
barriers, это немного утешает :)

Попробую сейчас выкачать manuals по Alpha и IA-32 и полистать вечером, может что-то прояснится. :)

>вот как бы и нет. я припоминаю (вроде бы :), что не один >раз встречал патчи, где добавлялся барьер после unlock() >с комментарием, что unlock не достаточно.

Мммм... тогда имеет место большая проблема с Linux kernel, т.к. ето полностью дискредитирует концепцию spin-блокировки в том смысле в котором она везде описана.

Еще варианты - посмотреть в DDK/2000 source, что пишет MS на тему спина и барьеров, ну и во фрюниксах. На диске есть еще несколько proprietary юниксов, но они, к сожалению, не поддерживают SMP.

> вот как бы и нет. я припоминаю (вроде бы :), что не один
> раз встречал патчи, где добавлялся барьер после unlock()

вот, например:
http://linux.bkbits.net:8080/linux-2.5/gnupatch@418aac44xNhoSaqW3Ln-qJqA9k8Hew

> Попробую сейчас выкачать manuals по Alpha и IA-32

только вряд ли там будет что-то про то, что обещает linux
реализация spin lock.

зато, может, сможете мне обьяснить read_barrier_depends() !
то есть, я способен понять комментарий в system.h, но
не могу представить, что должен делать процессор такого,
чтобы этот read_barrier_depends() был бы не nop.

> Мммм... тогда имеет место большая проблема с Linux kernel,
> т.к. ето полностью дискредитирует концепцию spin-блокировки

да ладно :) я, признаться, вообще не знал, что существует
какое-то общее определение. но даже если оно в linux и
отличается, в чем проблема? лишь бы правильно использовалось

>вот, например:
http://linux.bkbits.net:8080/linux-2.5/gnupatch@418aac44xNhoSaqW3Ln-qJqA9k8Hew

Дык тут вообще нет ничего про spin-блокировки, обычный memory barrier (может чуть более оптимальный из-за того, что заточен под конкретную операцию).

>только вряд ли там будет что-то про то, что обещает linux
>реализация spin lock.

Должно зато стать понятнее, что именно нужно делать, чтобы все было как хочется и что именно делают примитивы по синхронизации в Linux.

>да ладно :) я, признаться, вообще не знал, что существует
>какое-то общее определение. но даже если оно в linux и
>отличается, в чем проблема? лишь бы правильно использовалось

Дык во всех книжках (в том числе и по Linux kernel) spin блокировка определяется как critical section. Если там что-то может переупорядочиваться, то какой нафиг тут critical section? :)

> Дык тут вообще нет ничего про spin-блокировки, обычный memory barrier

нет, смотрите комментарий:
> #   The spin_unlock() in rotate_reclaimable_page() is not a sufficient memory
> #   barrier.

и сам патч:
        if (!TestClearPageReclaim(page) || rotate_reclaimable_page(page)) {
-               smp_mb__after_clear_bit();
        }
+       smp_mb__after_clear_bit();
        wake_up_page(page, PG_writeback);

rotate_reclaimable_page() делает spin_unock и возвращает 0,
до этого патча в этом случае не было барьера перед wakeup().

> всех книжках (в том числе и по Linux kernel) spin блокировка определяется
> как critical section Если там что-то может переупорядочиваться, то какой
> нафиг тут critical section? :)

вот такое, у нас, дяденька, хреновое лето :)

но ведь там, я думаю, не написано, что при выходе из критической секции
все pending stores должны завершиться?

>но ведь там, я думаю, не написано, что при выходе из критической секции >все pending stores должны завершиться?

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

В Windows, как я вижу в DDK, поступили грамотно - все примитивы синхронизации (в т.ч. spin-блокировка) подразумевают memory barriers.

Торвальдс опять отличился, мля.

Да и не только в Windows, в BSD MD-код тоже не виден пользователю. Только в Linux все кишки торчат наружу... :-/

прошу прощения что влезаю в вашу бесседу
но у меня такой насущный вопрос

int var;
rwb();
var++;
wmb();

будут ли при таком коде все процессора
гарантированно видеть изменение переменной ?
если планировщик заберет управление у процесcа
после var++; достаточно ли rmb();
для того чтобы процесор на котором выполняется
эта операция увидел изменение ?
и вобще атомарна ли операция var++ или var = xxx ?
сорри за несколько муторное изложение вопросов...

idle:

Еще такой момент по поводу спина и барьеров если спин не подразумевает write barrier, то получается, что в конце практической каждой критической spin-секции нужно ставить самому барьер (ведь основная задача спина - не что иное, как защищенный доступ на изменение shared data), но тем не менее в коде Linux барьеры - достаточно редкое явление.

anonymous:

Должны видеть (если в реализации барьеров для твоей платформы не допущено ошибок).

А сама операция ++ неатомарна.

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

Так, переупорядочивать код доступа может компилятор (тут можно бороться с помощью объявлений volatile), может процессор (тут - барьеры). При етом еще непонятно как видны одни и те же данные в любой момент на каждом процессоре в MP конфигурации между барьерами (ведь на том же IA32 при обращении к невыровненным данным генерируется несколько шинных запросов, неясно на всех ли архитектурах атомарно обновление выровненных данных).

В твоем примере ты решил проблему с порядком кода (еще желательно переменную объявить volatile), но в промежутке между барьерами у тебя, вообще говоря, при обращении к твоей переменной возможны самые разные варианты (например, классический race condition при изменении твоей переменной или во время обновления на втором процессоре может быть вообще виден мусор в переменной - на IA32 такое возможно для невыровненной переменной, посколько новое значение будет записано в нескольких шинных транзакциях).

Мое мнение заключается в том, что все критические секции должны скрывать все подобные архитектурные нюансы. То есть человек понимает, что при обращении к shared data нужно использовать критическую секцию (как на чтение - так и на запись) - и в секции реализованы и атомарность доступа к блоку с данными на уровне компилятора и процессора и все барьеры и всё-всё-всё... Барьеры и прочая глупость должны всплывать при написании сильно оптимизированного для платформы кода, в Linux же ето, похоже, essential.

> Барьеры и прочая глупость должны всплывать при написании > сильно оптимизированного для платформы кода, в Linux же ето, > похоже, essential.

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

пример. есть __set_task_state(), и есть set_task_state(), то же самое, но с барьером. и есть куча ошибок, связанных с использованием первого вместо второго. стоила ли овчинка выделки? я не знаю, но барьеры действетельно очень дороги.

а сравнивать с BSD кодом вообще неинтересно, вот когда они будут поддерживать SMP в той же степени, тогда и можно будет посмотреть.

_лично_ я бы предпочел более простое и маленькое ядро, уж больно быстрые компьтеры сейчас. и пусть бы оно работало на 10% медленнее, но меня что-то не спрашивают :)

это был не anonymous

idle:

все же насчет pending writes вне критических секций. Правильно ли я понял, что, например, drivers/char/n_tty.c:n_tty_receive_buf (пример с балды) может в режиме real_raw в той же критической секции на другом процессоре получить старое (необновленное предыдущим n_tty_receive_buf) значение read_head и read_cnt?

> все же насчет pending writes вне критических секций.

это я, блин, опять фигню спорол. то, что остаются pending writes,
это не проблема, даже явный wmb() не гарантирует, что они будут
flushed. это если говорить вообще, не имея в виду, например
pentium.

wmb() означает, что любая запись _после_ этого примитива попадет
в ram не раньше, чем любая запись _до_ него.

> Правильно ли я понял, что, например, drivers/char/n_tty.c:n_tty_receive_buf
> (пример с балды) может в режиме real_raw в той же критической секции на другом
> процессоре получить старое (необновленное предыдущим n_tty_receive_buf)
> значение read_head и read_cnt?

здесь все должно быть корректно, иначе в linux вообще ничего бы
не работало. lock()/unlock() должны правильно защищать изменение
данных _внутри_ критической секции. иными словами, вот такой код
должен работать правильно:

int var;
spinlock_t lock;

void inc_var(void)
{
        spin_lock(&lock);
        ++var;
        spin_unlock(&lock);
}

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

то, что spin_unlock() "is not a sufficient memory barrier" я
понимаю следующим образом: если у нас есть чтение _после_
spin_unlock(), оно может выполниться раньше, чем завершится
критическая секция.

то есть вот такой код, например, неправильный:

int condition;
wait_queue_head_t* Q;

my_sleep()
{
        current->state = TASK_INTERRUPTIBLE;
        add_wait_queue(Q, ...); // lock()+unlock()

        // ЗДЕСЬ НУЖЕН БАРЬЕР! mb()

        if (!condition) schedule();

        current->state = TASK_RUNNING;
        remove_wait_queue(&wq, &__wait);
}

my_wake()
{
        condition = 1;
        mb();
        if (waitqueue_active(&Q)
                wake_up(&Q);
}

                                имеем:
my_sleep() на CPU_0:                            my_wake() на CPU_1

во время добавления процесса в очередь
процессор спекулятивно читает condition == 0.
add_wait_queue() делает unlock()
                                                condition = 1;
                                                изменения в Q здесь еще не видны,
                                                wake_up не вызывается.
вызывается schedule(), и событие пропущено.


если бы там был mb(), то либо CPU_0 увидит condition == 1,
после того, как my_wake() сделает свой mb(), либо CPU_1 увидит
добавление процесса в очередь.

> на сегодняшний день мое понимание таково

только вот я не уверен в его правильности, забыл добавить :)