И на Солнце есть пятна

в 2:11, , рубрики: windows, ассемблер, Компиляторы, оптимизация, реверс-инжиниринг, системное программирование, Совершенный код
И на Солнце есть пятна - 1

Введение

В предыдущей заметке «Планировщик Windows? Это очень просто» было рассказано о технологии получения дизассемблированного текста ядра операционной системы Windows XP образца 2013 года. Такой текст потребовался для анализа и корректировки кода ядра, что позволило изменить политику планирования потоков в Windows и выполнить одну конкретную задачу с уменьшением времени отклика операционной системы.

После решения этой задачи я напоследок просто «полистал» текст ядра, особо не вникая, что именно делается в том или ином участке кода. Хотелось посмотреть, какие приемы локальной (т.е. в пределах 1-2 команд) оптимизации применяет использованный для создания ядра транслятор. Или, может быть, несколько трансляторов, если ядро собрано из нескольких отдельных частей. Сознаюсь, главная цель была в поиске таких приемов генерации кода, которые я не догадался использовать в своем трансляторе.

Поскольку Windows является, наверное, самой дорогой программой в мире по затратам на разработку и сопровождение, уровень качества кода ее ядра должен бы быть одним из самых высоких. Именно поэтому было интересно посмотреть, как устроен код с точки зрения эффективности отдельных команд. Однако я увидел не совсем то, что ожидал и поэтому решил поделиться несколькими соображениями. Для иллюстрации ниже приведены фрагменты дизассемблированного кода ядра Windows XP сборки от 4 июля 2013 года.

Хотя Windows XP и Windows 7 уже, так сказать, «сняты с вооружения», на мой взгляд, изучение даже неподдерживаемых программ имеет смысл. Ядро Windows XP сопровождалось и развивалось около 10 лет. Поэтому на основании анализа кода можно, например, даже прогнозировать пути дальнейшего развития системы. Замечу также, что различия в коде ядер различных версий Windows не так велики как различия некоторых других компонентов.

Оптимизация команд

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

Например, транслятор заменяет умножение на степень двойки командой сдвига:

40AD14 0FB74018             MOVZX  EAX,W PTR [EAX]+18
40AD18 8B4904               MOV    ECX,[ECX]+4
40AD1B C1E005               SHL    EAX,5

Широко используется загрузка константы в регистр через пару команд обращения к стеку:

40AD5B 6A0A                 PUSH   0A
40AD5D 59                   POP    ECX

Я считаю такую пару командой MOVSX ECX,0AH (которая на самом деле не существует, но если бы была, то эффект она давала бы такой же).

Остроумно реализовано громоздкое вычисление адресации, например, вот быстрое умножение индекса на 12:

4038E8 8D0C76               LEA    ECX,[ESI+ESI*2]
4038EB 837C8F0400           CMP    D PTR [EDI+ECX*4]+4,0

Сплошь и рядом используется приемы, которые уменьшают зависимость соседних команд и, тем самым, ускоряют работу конвейера процессора и уменьшают число переходов:

4050F8 F7410406000000       TEST   D PTR [ECX]+4,6
4050FF B801000000           MOV    EAX,1
405104 7512                 JNZ    405118

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

Недостатки кода

Однако наряду с эффективно сформированными командами встречаются вещи, которые, мягко говоря, далеко не оптимальны.

Первое, что бросается в глаза – это странное выравнивание подпрограмм. Я понимаю смысл такого выравнивания в уменьшении числа обращений к памяти при чтении команд подпрограммы. Поскольку в процессор считывается сразу целая кэш-строка кодов, выгодно расположить команды начала подпрограммы с начала такой строки и, тем самым, избежать, по крайней мере, одной «лишней» подкачки кодов. Выравнивание обычно идет командами NOP или иногда INT 3.

Но посмотрите, например, на один из бесчисленных фрагментов ядра:

4025AA 90                   NOP
4025AB 90                   NOP
4025AC 90                   NOP
4025AD 90                   NOP
4025AE 90                   NOP
4025AF 8BFF                 MOV    EDI,EDI
4025B1 55                   PUSH   EBP

Здесь, как и в сотнях других подобных мест, выравнивание превратилось в свою противоположность, и подпрограмма начинается из-за команд NOP как раз НЕ с адреса, кратного 16 или хотя бы 4, а сами команды NOP стали просто бессмысленным раздуванием кода. Такое впечатление, что где-то в одном месте в ядре выравнивание «съехало» и далее везде дает противоположный эффект.

Причем, чтобы увидеть это, вовсе не требуется дизассемблировать код, достаточно любой подходящей утилитой посмотреть таблицу экспорта ядра NTOSKRNL.EXE. Там полно, например, нечетных (т.е. явно никак не выровненных) адресов входов.

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

40A661 8B4D0C               MOV    ECX,[EBP]+0C
40A664 85C9                 TEST   ECX,ECX
40A666 0F840989FFFF         JJE    402F75

Однако в том месте выполняется всего пара команд, и управление возвращается, так сказать, «обратно»:

402F75 8BCE                 MOV    ECX,ESI
402F77 E8EB260000           CALL   405667
402F7C E9FB760000           JMP    40A67C

и подобных «прыжков» огромное количество. Сначала я решил, что это отражение конструкций типа try-catch, но возможно это и случаи единственного обращения к подпрограмме, где транслятор убирает команды CALL и RET и ставит вместо них «длинный» условный и безусловный переходы. При этом код становится на 3 байта длиннее по сравнению с суммой команд короткого условного перехода, вызова и возврата. Разумеется, нет здесь и никакого выравнивания.

Встречаются и такие конструкции:

IoFreeIrp:
414012 8BFF                 MOV    EDI,EDI
414014 55                   PUSH   EBP
414015 8BEC                 MOV    EBP,ESP
414017 5D                   POP    EBP
414018 FF258C474800         JMP    D PTR [0048478C]
…
IoAllocateIrp:
41406D 8BFF                 MOV    EDI,EDI
41406F 55                   PUSH   EBP
414070 8BEC                 MOV    EBP,ESP
414072 5D                   POP    EBP
414073 FF2588474800         JMP    D PTR [00484788]

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

Возможно, в исходном тексте находится какой-то закомментированный фрагмент и это дает такой эффект. Возможно, это было сделано для каких-то отладочных остановок. Но как бы то не было, каждый раз, когда происходит обращение к подпрограммам IoAllocateIrp и IoFreeIrp, сначала выполняются бессмысленные команды.

Во многих местах ядра происходит обращение к двухбайтовым объектам, например:

409378 668B4564             MOV    AX,[EBP]+64
40937C 6683E0FC             AND    AX,FFFC
409380 668B4A04             MOV    CX,[EDX]+4
409384 6683E1FC             AND    CX,FFFC
409388 663BC8               CMP    CX,AX
40938B 7547                 JNZ    4093D4

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

409378 8B4564               MOV    EAX,[EBP]+64
40937B 83E0FC               AND    AX,FFFC
40937F 8B4A04               MOV    ECX,[EDX]+4
409382 6683E1FC             AND    CX,FFFC
409386 663BC8               CMP    CX,AX
409389 7545                 JNZ    4093D4

Это тем более удивительно, что иногда обработка двухбайтового объекта идет без префикса 66, например:

407F3D 668B442424           MOV    AX,[ESP]+24
407F42 C1E004               SHL    EAX,4

Чтение всех двухбайтовых объектов как четырехбайтовых позволяет существенно сократить код.

К тому же, напомню, к 32-х разрядным процессорам подходит все-таки не 32, а только 30 адресных линий. Тем самым, из памяти физически не может читаться менее 4 байт за раз. Две младших адресных линии используются только внутри самого процессора для выбора нужных байт из числа 4 считанных. Так, что физически все равно читается 4 байта, даже когда требуется достать только два.

Еще один существенный недостаток кода – большое число пересылок регистров. Например, типичный фрагмент:

40FAE0 64A120000000         MOV    EAX,FS:[00000020]
40FAE6 8BF8                 MOV    EDI,EAX
40FAE8 8BB748050000         MOV    ESI,[EDI]+548
40FAEE FF460C               INC    D PTR [ESI]+0C
40FAF1 8BCE                 MOV    ECX,ESI
40FAF3 E87FA7FFFF           CALL   40A277 ;ExInterlockedPopEntrySList
40FAF8 85C0                 TEST   EAX,EAX
40FAFA 0F84843A0000         JJE    413584

Его можно было бы короче записать так:

40FAE0 648B3D20000000       MOV    EDI,FS:[00000020]
40FAE7 8B8F48050000         MOV    ECX,[EDI]+548
40FAED FF410C               INC    D PTR [ECX]+0C
40FAF0 E87DA7FFFF           CALL   40A277 ;ExInterlockedPopEntrySList
40FAF5 85C0                 TEST   EAX,EAX
40FAF7 0F84823A0000         JJE    413584

Не пересылая каждый раз данные сначала в регистры EAX и ESI.

Может возникнуть резонный вопрос, а причем здесь вообще ядро Windows? Ведь код генерирует транслятор. Используя специальные тесты можно и без ядра посмотреть, насколько хорошо он это делает. И что собственно предлагает автор? Перетранслировать Windows другими средствами из-за нескольких неэффективных команд? Или исправить транслятор?

Для большинства программ практически значимый результат от совершенствования кода бывает редко. Допустим, имеется программа, которая проводит расчет за минуту. Допустим, потратив час, ее ускорили на 10%. Тогда только примерно через 600 прогонов общий выигрыш от работы улучшенной версии достигнет того же часа и компенсирует затраченное время. Если и не требуется запускать программу более 600 раз, улучшение не оправдает затраты.

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

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

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

Разве сделано все возможное? Сразу вспоминается исторический анекдот, когда на уверения: «поверьте, делается все возможное» один государственный деятель раздраженно заметил: «а я вас не ограничиваю, делайте и невозможное». Применительно к данному случаю: если невозможно улучшить транслятор, так доработайте результат трансляции другими инструментами, но добейтесь улучшения качества.

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

Технология улучшения кода

Какова может быть технология улучшения кода? С моей точки зрения менять технологию разработки и компилирования Windows уже поздно – слишком много усилий потрачено на отработку и тестирование.

А вот выделить хотя бы одного программиста для анализа конечного результата (т.е. конечного кода) – вполне возможно. Особенно, если учесть, что общее число разработчиков Windows (как уверяют) около 5 тысяч. И этот один (из почти целой пехотной дивизии программистов!) мог бы дизассемблировать самые важные части операционной системы, подобно тому, как, например, за несколько дней это сделал я, проанализировать код и дать свои рекомендации по повышению его эффективности.

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

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

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

Например, в фрагменте:

411AC8 64A120000000         MOV    EAX,FS:[00000020]
411ACE 8BF8                 MOV    EDI,EAX
411AD0 64A124010000         MOV    EAX,FS:[00000124]
411AD6 33C9                 XOR    ECX,ECX

можно гарантированно без последствий заменить первую команду MOV EAX,… на MOV EDI,… и исключить лишнюю пересылку MOV EDI,EAX, поскольку уже в следующей команде EAX принимает новое значение и его старое значение никак не может быть использовано далее. При этом в ядре нет команд перехода на адрес 411ACE (что также легко проверить), а, значит, никакой ошибки от прямой пересылки в другой регистр не может быть в принципе.

Другое дело, вот такой фрагмент:

412D09 8B06                 MOV    EAX,[ESI]
412D0B 57                   PUSH   EDI
412D0C 8BF8                 MOV    EDI,EAX
412D0E C1EF0C               SHR    EDI,0C
412D11 BBFF0F0000           MOV    EBX,00000FFF
412D16 0F8423010000         JJE    412E3F

Здесь менять пересылку регистров опасно, поскольку управление куда-то передается (по адресу 412E3F) и транслятор далее может использовать имеющееся значение в EAX. Анализ так ли это или нет, уже достаточно сложен и не может быть выполнен формально и простыми средствами как в предыдущем случае.

Заключение

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

С другой стороны, в огромной команде Microsoft, по-видимому, не нашлось сотрудников, которые взяли бы на себя регулярный анализ качества конечного результата – собственно кодов операционной системы. Поэтому в коде ядра Windows XP, которое сопровождалось не менее 10 лет, осталось много мест, которые хорошо было бы улучшить.

Совершенствование кода принципиально возможно даже без изменения самих процессов разработки и компиляции операционной системы. Один из таких способов – это дизассемблирование, анализ, внесение изменений и трансляция дизассемблерного текста обратно в EXE-файл.

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

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

Автор: Dukarav

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js