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

Тема в разделе "WASM.HEAP", создана пользователем PROFi, 28 сен 2008.

  1. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    3EFF10 call d,ds:[eax] - хе - а ведь отладчик именно так и выдаст команду, префикс ds спрячется

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

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    за "упоминание" автора вопроса в 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
    Вообще очень хорошая реалиация спинлока с учетом производительности.
    Собственно понятно, что код актуален для многопроцессорной системы, но здесь есть ошибка, которая проявится при определенном условии. Где она?
     
  3. asmfan

    asmfan New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2006
    Сообщения:
    1.004
    Адрес:
    Abaddon
    Кроме отсутствия сериализации ошибок не видно.
     
  4. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    asmfan

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

    asmfan New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2006
    Сообщения:
    1.004
    Адрес:
    Abaddon
    сериализация действий в кр.секц. перед освобождением лока. Остальное там вроде прально. атомарность е.
     
  6. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.599
    Адрес:
    г. Санкт-Петербург
    не знаю, где вы такой код достали. 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 - нет.
     
  7. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    SadKo
    Я же подписал:
    p. 7-40 IA-32 Intel® Architecture Software Developer’s ManualVolume 3: System Programming Guide
     
  8. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    asmfan
    В примере ведь не приведено конкретных действий, т.е. <critical section code> по определению не содержит ошибок. Т.е. это здесь не при чем.
     
  9. asmfan

    asmfan New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2006
    Сообщения:
    1.004
    Адрес:
    Abaddon
    PROFi, ваши мануалы слегка outdated и код нынче выглядит чуть по-другому, но суть та же, что и у SadKo.
    Если ошибка есть, то гда она?
    П.С. можно написать правильный ответ внизу страницы перевёрнутыми буквами.
     
  10. zorro

    zorro New Member

    Публикаций:
    0
    Регистрация:
    8 ноя 2008
    Сообщения:
    33
    На ум приходит только то, что если А не была инициализирована нулем, то программа свалится в бесконечный цикл.
     
  11. SadKo

    SadKo Владимир Садовников

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

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    Ок. Тогда ближе к теме - переменная A может использоваться несколькими потоками одновременно. Теперь первая подсказка - а что будет если A не будет выровнена на границу двойного слова (в примере выравнивание не проверяется).
     
  13. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    PROFi
    Вы ведь не об атомарности xchg говорите? Потому как asmfan уже упомянул, что атомарность соблюдена.
    Сюда же первое:
    И насчёт выравнивания:
     
  14. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    PROFi
    Так ведь инструкция xchg автоматически блокирует шину если один из операндов находится в памяти. Поэтому, даже если запись значения будет длиться несколько циклов шины, она все равно будет заблокирована и второе ядро/процессор не смогут прочитать некорректные данные.
     
  15. PROFi

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    Mika0x65 - Нет ошибка не в инструкции xchg. ;)

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

    SadKo Владимир Садовников

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

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    - на все ли?

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

    Код (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
    Да я в самом начале упомянул, что это:
     
  18. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    PROFi
    Вы проигнорировали цитату о выравнивании из 33-го поста. Согласно этой цитате mov A,0 будет атомарной, даже если A не выравнена на четырёхбайтную границу.
    Кстати... чуть не забыл :)
    В примере ведь не приведен адрес, по которому располагается A, т.е. в этом по определению нет ошибки. :)
     
  19. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    Странно как-то, или я не понял. Даже если там будет 0xFF, 0xFF00 и т.д. -- мы же все равно весь dword сравниваем с 0, а не только часть. Если 0х0 -- true, а !0x0 -- false, то все в порядке как раз.

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

    PROFi New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2003
    Сообщения:
    690
    l_inc

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

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