И на Солнце есть пятна
Введение
В предыдущей заметке «Планировщик 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), а отдача могла бы получиться заметной буквально на планетарном уровне.
