$ головоломка для мыщъх'а

3EFF10 call d,ds:[eax] - хе - а ведь отладчик именно так и выдаст команду, префикс ds спрячется

Я тоже по памяти писал 2 пример - ошибся с esp
Ок ждем новых "# головоломка от мыщъх'а" - а то давненько не было. Ну а тут постараюсь(емся) добавлять в обратном направлении.

 

за "упоминание" автора вопроса в http://conference.hackinthebox.org/hitbsecconf2008kl/materials/D2T1%20-%20Kris%20Kaspersky%20-%20Remote%20Code%20Execution%20Through%20Intel%20CPU%20Bugs.pdf
стр 24 отдельное спасибо.

Ну вот еще одна загадка
Реализация спинлока из мануалов интела:

Код (Text):

1. Get_Lock:
2.             MOV EAX, 1
3.             XCHG EAX, A     ; Try to get lock
4.             CMP EAX, 0  ; Test if successful
5.             JNE Spin_Loop
6. Critical_Section:
7.             <critical section code>
8.             MOV A, 0    ; Release lock
9.             JMP Continue
10. Spin_Loop:
11.             PAUSE  ; Short delay
12.             CMP 0, A  ; Check if lock is free
13.             JNE Spin_Loop
14.             JMP Get_Lock
15. Continue:
16.  
17.  
18. p. 7-40 IA-32 Intel® Architecture Software Developer’s ManualVolume 3: System Programming Guide

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

 

Кроме отсутствия сериализации ошибок не видно.

 

asmfan

Что ты под этим подразумеваешь - где конкретно ошибки?

 

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

 

не знаю, где вы такой код достали. Intel рекомендует конструкцию test-test&set lock:

Код (Text):

1.             "spin_lock:"                
2.             "cmp    dword ptr [edx], 0"
3.             "je     try_lock"          
4.             "pause"                    
5.             "jmp    spin_lock"          
6.             "try_lock:"                
7.             "mov    eax, 1"            
8.             "xchg   eax, [edx]"        
9.             "xor    al, 1"

типа того.

На выходе - 1 = заблокировали, 0 - нет.

 

SadKo

Я же подписал:
p. 7-40 IA-32 Intel® Architecture Software Developer’s ManualVolume 3: System Programming Guide

 

asmfan

В примере ведь не приведено конкретных действий, т.е. <critical section code> по определению не содержит ошибок. Т.е. это здесь не при чем.

 

PROFi, ваши мануалы слегка outdated и код нынче выглядит чуть по-другому, но суть та же, что и у SadKo.
Если ошибка есть, то гда она?
П.С. можно написать правильный ответ внизу страницы перевёрнутыми буквами.

 

На ум приходит только то, что если А не была инициализирована нулем, то программа свалится в бесконечный цикл.

 

Я вижу тут только одну ошибку: если арбитр шины сделан нечестно, то оба ядра процессора могут впасть в dead lock при попытке блокировки ресурса. Ситуация такая: есть ресурс, который надо достаточно часто блокировать. И две задачи, запущенные на каждом ядре. В реальной ситуации синхронного выполнения задач добиться нереально, а на эмуляторах типа bochs - вполне возможно (там выполняется по команде на ядро за один такт). В результате имеем, что один поток постоянно блокирует ресурс, по каким-то причинам обламывается (ждёт данных от второго, помещённых в этот ресурс), в это время ресурс пытается лочить второй, чтобы поместить данные, и тоже обламывается. Первый поток освобождает ресурс (уже после того, как второй обломался), а второй никогда не получает доступа к нему (потому что блокировка всегда приходится на момент, когда ресурс заблокирован первым потоком). Всё, кернел впадает в дедлок.

 

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

 

PROFi
Вы ведь не об атомарности xchg говорите? Потому как asmfan уже упомянул, что атомарность соблюдена.
Сюда же первое:

И насчёт выравнивания:

 

PROFi
Так ведь инструкция xchg автоматически блокирует шину если один из операндов находится в памяти. Поэтому, даже если запись значения будет длиться несколько циклов шины, она все равно будет заблокирована и второе ядро/процессор не смогут прочитать некорректные данные.

 

Mika0x65 - Нет ошибка не в инструкции xchg.

Вторая подсказка - если такой код был написан на си, к примеру, то PREfast ругался бы на ...

 

Основная функция блокировки ложится на xchg, поэтому на всё остальное можно спокойно забить. Проверка при помощи cmp - это только прелюдия к блокировке, чтобы исключить лишние блокировки шины и выполнить pause, которая по-другому интерпретируется на p6 (для ускорения функций блокировок).

 

- на все ли?

Ок - приведу еще раз код:

Код (Text):

1. Get_Lock:
2.             MOV EAX, 1
3.             XCHG EAX, A     ; Try to get lock
4.             CMP EAX, 0  ; Test if successful
5.             JNE Spin_Loop
6. Critical_Section:
7.             <critical section code>
8.             MOV A, 0    ; Release lock
9.             JMP Continue
10. Spin_Loop:
11.             PAUSE  ; Short delay
12.             CMP 0, A  ; Check if lock is free
13.             JNE Spin_Loop
14.             JMP Get_Lock
15. Continue:
16.  
17.  
18. p. 7-40 IA-32 Intel® Architecture Software Developer’s ManualVolume 3: System Programming Guide

PREFAst ругается на то, что к переменной A обращаются в нескольких местах без лока шины. другими словами если есть переменная к которой идет обращение из нескольких потоков, причем без синхронизации - т.е. сама переменная и является синхронизацией, то во всех местах где идет инициализация переменной префаст требует чтобы исспользовались Interlocked функции.

Вот конкретно здесь по адресу А заносится 0 или 1, но реально 0 - это FALSE, не 0 - TRUE. Т.е. что касается нуля - то тут обязательно его использование, а что касается 1, то тут вполне может быть, к примеру, 0FFFFFFFFh - и если алгоритм спинлока коректен, то он должен отработать правильно и в этом случае.

а теперь присмотримся к инструкции MOV A, 0 ; Release lock

маленькая выдержка из правил:

Т.е. если А не выровнен, то MOV A, 0 ; Release lock будет обращатся к шине 2 раза, чтобы записать туда 0.

В конкретном случае пусть речь идет о 2х процессорах. На первом началось исполнение MOV A, 0 и комманда обратилась один раз к шине и обнулила часть байт памяти, но в этот момент 2й процессор захватывает шину в комманде XCHG EAX, A ; Try to get lock,

, то и в этом случае реально получить значение в памяти 000FFFFFFh или 00000FFFFh или 0000000FFh, со всеми вытекающими последсвиями.

PS: Т.о. в указанном примере имеется ошибка алгоритма реализации спинлока, который при определенных условиях (см. выше

) может приводить к ошибке в работе кода. PREFast от MS предупреждает о таких ошибках в реализации кода.

SadKo

Да я в самом начале упомянул, что это:

 

PROFi
Вы проигнорировали цитату о выравнивании из 33-го поста. Согласно этой цитате mov A,0 будет атомарной, даже если A не выравнена на четырёхбайтную границу.
Кстати... чуть не забыл

В примере ведь не приведен адрес, по которому располагается A, т.е. в этом по определению нет ошибки.

 

Странно как-то, или я не понял. Даже если там будет 0xFF, 0xFF00 и т.д. -- мы же все равно весь dword сравниваем с 0, а не только часть. Если 0х0 -- true, а !0x0 -- false, то все в порядке как раз.

+'mov [A], 0x0' все равно выполняется в конце критической секции, так что вреда от того, что второй поток попадет в критическую секцию чуть ранше не будет. Хотя это и небрежно выглядит.

 

l_inc

Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line
А вы ее видимо неправильно поняли. А если не поместится в кэш линии?

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