Первая публикация 10.02.2015
Some notes on commands quality
Введение
В предыдущей статье [1] было рассказано о технологии получения дисассемблированного текста ядра операционной системы Windows-XP образца 2013 года. Такой текст потребовался для анализа и корректировки кода ядра, что позволило изменить политику планирования потоков в Windows и выполнить одну конкретную задачу с уменьшением времени отклика операционной системы.
После решения этой задачи я напоследок просто «полистал» текст ядра, особо не вникая, что именно делается в том или ином участке кода. Хотелось посмотреть, какие приемы локальной (т.е. в пределах 1-2 команд) оптимизации применяет использованный для создания ядра транслятор. Или, может быть, несколько трансляторов, если ядро собрано из нескольких отдельных частей. Сознаюсь, главная цель была в поиске таких приемов генерации кода, которые я не догадался использовать в своем трансляторе [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
Здесь команда загрузки EAX может начать исполняться до окончания выполнения предыдущей команды сравнения.
Эти и другие многочисленные примеры подтверждают, что используемые для создания кода ядра трансляторы пытаются генерировать команды оптимальным способом.
Недостатки кода
Однако наряду с эффективно сформированными командами встречаются вещи, которые, мягко говоря, далеко не оптимальны.
Первое, что бросается в глаза – это странное выравнивание подпрограмм. Я понимаю смысл такого выравнивания в уменьшении числа обращений к памяти при чтении команд подпрограммы. Поскольку в процессор считывается сразу целая кэш-строка кодов, выгодно расположить команды начала подпрограммы с начала такой строки и, тем самым, избежать, по крайней мере, одной «лишней» подкачки кодов. Выравнивание обычно идет командами 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, сначала выполняются бессмысленные команды.
Во многих местах ядра происходит обращение к 2-х байтовым объектам, например:
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
Недостаток здесь в том, что у транслятора не хватило «смелости» всегда читать эти объекты в 4-х байтовые регистры, т.е. сделать код короче из-за исключения префиксов в командах чтения (даже оставляя префиксы в командах умножения и сравнения):
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
Это тем более удивительно, что иногда обработка 2-х байтового объекта идет без префикса 66, например:
407F3D 668B442424…….MOV….AX,[ESP]+24
407F42 C1E004…………….SHL……EAX,4
Чтение всех 2-х байтных объектов как 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), а отдача могла бы получиться заметной буквально на планетарном уровне.
Литература
- Караваев Д.Ю. Об уменьшении времени отклика в Windows
- Караваев Д.Ю. К вопросу о совершенствовании языка программирования. RSDN Magazine #4, 2011
Автор публикации
