Прошлая эффективность не гарантирует будущих результатов
Прежде чем перейти к сути нашего сегодняшнего повествования, несколько замечаний. Во-первых, я извиняюсь за отсутствие новых постов в последние три недели; я был невероятно занят добавлением новых возможностей в семантический анализатор языка C# проекта Roslyn. Подробности об этом в следующем посте. Во-вторых, обратите внимание на страничку с блогами, посвященную инструментам разработки (Developer Tools blog aggregation page – En.); это отличная стартовая точка для получения массы полезной информации, и большая часть из нее фиолетовая. Доказательство! (En.)
Хорошо, раз мы расправились с метаинформацией о блогах, переходим к вопросу, который мне недавно задали:
При компиляции дважды одной и той же программы на языке C#, будет ли получен один и тот же двоичный результат?
Нет.
Ну, это был очень простой пост. Хотя некоторые дополнительные сведения наверняка будут полезны.
А почему?
Ну, по своей сути, язык – это не что иное, как набор строк (возможно бесконечный) (*); строка является корректной программой, если она входит в этот набор, в противном случае – программа не корректна. Компилятор – это программа, которая принимает строку, определяет, является ли она корректной с точки зрения некоторого языка, и если она корректна, то выдает эквивалентную (**) корректную строку на другом языке. Например, компилятор языка C# принимает входную строку, которая хранится в файле “.cs” и выдает на выходе программу, написанную на языке MSIL. Конечно существует масса деталей; компилятор языка C# генерирует MSIL в «переносимом исполняемом» (portable executable) формате, а не в формате, предназначенном для человека. И компилятор языка C# также принимает на вход программы в двоичном формате в виде дополнительных сборок. Но на базовом уровне, компилятор языка C# делает для вас следующее: принимает код, написанный на языке C#, анализирует его корректность и генерирует эквивалентную программу в PE (Portable Executable) формате.
Любая программа на языке C# имеет множество эквивалентных программ на языке MSIL; самым простым примером может служить добавление любого количества nop-инструкций (“no operation”) в любом месте программы. Глупым примером можем служить добавление любого проверяемого кода по любому недостижимому пути исполнения! Более интересным примером является очень частая ситуация, когда компилятор должен «создавать» уникальные имена для таких конструкций, как анонимные методы, анонимные типы, поля классов-замыканий (closure classes) и т.п. Давайте рассмотрим эти уникальные имена более подробно.
Когда компилятору для чего-то нужно создать уникальное имя, то его базовой стратегией является создание шаблона имени, которое не при каких условиях не может быть корректным, поскольку содержит символы, корректные для идентификаторов в языке MSIL, но некорректные с точки зрения языка C#. Затем в этот шаблон вставляются дополнительные строки, например имя текущего метода, после чего в конец имени добавляется числовое значение. Точный шаблон имени я описал в одном из ответов на StackOverflow; обратите внимание, что это деталь реализации компилятора, и мы думаем изменить его в будущем. (Некоторые люди жалуются, что имена слишком длинные и занимают слишком много места в таблицах метаданных; мы можем сделать их значительно короче). Основная мысль заключается в том, что уникальность гарантируется путем увеличения счетчика, с помощью которого гарантировать такую уникальность довольно просто. С практической точки зрения мы едва ли столкнемся с неуникальностью идентификаторов; их уникальность должна быть обеспечена только в пределах одной сборки и ни одна сборка не будет содержать более двух миллиардов идентификаторов, сгенерированных компилятором.
Это означает, что реальное значение идентификаторов, сгенерированных компилятором, определяется порядком анализа конкретного фрагмента кода, во время которого требуется генерация уникального идентификатора. Мы не даем никаких гарантий относительно того, что этот порядок детерминирован. Исторически, он был практически детерминирован; раньше анализатор компилятора C# был однопоточным, и, при анализе дважды одного и того же списка файлов, анализ файлов происходил в одном и том же порядке, и все типы в программе анализировались тоже в одном порядке (***). Но обратите внимание на следующие допущения:
Во-первых, мы предполагаем, что каждый раз мы будем анализировать один и тот же список файлов в одном и том же порядке. Но в некоторых случаях этим занимается операционная система. Когда вы пишите: “csc *.cs”, порядок, в котором операционная система возвращает результирующий список файлов, является деталью реализации операционной системы; компилятор не сортирует этот список.
Во-вторых, мы предполагаем, что анализатор компилятора является однопоточным; не существует требования к тому, чтобы он был однопоточным, и, на самом деле, мы уже пробовали сделать его многопоточным в прошлом и, скорее всего, попробуем это сделать еще раз. Анализ больших программ является отличным примером задач «чрезвычайного параллелизма» (embarrassingly parallel). Как только структура программы (все типы, методы, поля и т.д.) становятся известными, тогда тело каждого метода может анализироваться параллельно; содержимое тела одного метода никак не влияет на анализ тела другого метода. Но как только компилятор станет многопоточным, ни о каком детерминированном порядке анализа файлов речи уже быть не может, а значит мы не cможем гарантировать того, что две разные компиляции приведут к генерации одних и тех же идентификаторов.
Да, все это очень интересно, вот почему я пишу обо всем об этом. Я мог бы перейти сразу к сути: компилятор языка C# по определению никогда не выдает один и тот же результат дважды. Компилятор языка C# в каждую сборку после ее компиляции вставляет вновь сгенерированный GUID, гарантируя тем самым неидентичность двух сборок. Вот цитата из спецификации CLI:
Колонка Mvid должна указывать на уникальный GUID […], идентифицирующий экземпляр данного модуля. […] Mvid должен генерироваться каждый раз для каждого модуля […] Хотя сама среда исполнения не использует Mvid, другие инструменты (такие как отладчики […]) используют тот факт, что Mvid практически всегда являются уникальными.
Вот так вот; спецификация среды исполнения требует, чтобы каждый модуль (сборка содержитодин или более модулей) содержал уникальный идентификатор.
Более того: давайте не забывать о том, что IL-код не является исполняемым; еще один компилятор преобразует IL-код в машинный код. JIT-компилятор тоже не гарантирует того, что компиляция одного и того же кода дважды приведет к одинаковому машинному коду; JIT-компилятор может использовать всю доступную информацию во время исполнения для оптимизации генерируемого кода по размеру, скорости, для упрощения отладки и т.п., как ему захочется.
Если компилятор генерирует корректный код, то какая разница, генерирует ли он в точности идентичный код дважды или нет?
У первого пользователя, который задал мне вопрос о детерминированности компиляции, был очень интересный сценарий. Этот пользователь работал в отрасли, где код проверяется правительственными органами. Правительство хотело получить от него исходный код и результирующий исполняемый файл, который будет загружаться в процессор. Инспекторы хотели провести обзор безопасности исходного кода, прежде чем разрешить использование устройств с данными процессорами. Конечно же, очевидной атакой ненадежного поставщика является рассогласование исходного кода с результирующим двоичным результатом; исходный код надежен, а двоичный код – враждебен.
Инспекторы собирались скомпилировать исходный код и затем провести побитовое сравнение двоичного кода, который, как вы знаете, для языка C# будет гарантировано отличаться.
Я дал следующий совет: поскольку инспекторы в любом случае будут компилировать исходный код для сравнения, то пусть они получат лишь исходный код, и вернут результирующий двоичный код обратно его компании. Это гарантирует инспекторам, что двоичный код полностью соответствует исходному, поскольку они сами его получили.
Я так понимаю, что мой совет проигнорировали и остановились на сравнении разницы двоичного кода, проверяя, что отличия заключаются лишь в колонке Mvid, упомянутой ранее. Конечно же, я предостерег их, что они используют недокументированную и абсолютно не сопровождаемую возможность компилятора. Мы не даем никаких гарантий относительно того, что это поведение компилятора не изменится. Или в более общем случае: компилятор языка C# не предназначен для работы в качестве компонента системы безопасности, так что не нужно его использовать таким образом.
(*) И строка, конечно же, является конечной, упорядоченной последовательностью символов некоторого алфавита.
(**) Что именно делает программу на одном языке «эквивалентной» программе на другом языке является другим вопросом, который мы сейчас полностью проигнорируем.
(***) Подробности довольно интересны; по сути, мы анализируем файл один за другим, создавая дерево «высокоуровневых» элементов: пространств имен, типов, методов и т.п. Получив это дерево, мы итерируем по нему, получая, таким образом, частичную упорядоченность. Наша цель – искать элементы в определенном порядке (если он существует), который гарантирует, что механизм генерации метаданных никогда не будет генерировать метаданные в «неверном» порядке; мы хотим, чтобы метаданные базового типа генерировались до метаданных производного, и чтобы метаданные внешнего класса генерировались до метаданных внутреннего класса. Существует код, для которого эти требования невыполнимы; в этом случае производительность генератора метаданных существенно снижается. Так что у нас есть законный интерес гарантировать, что мы нашли правильный порядок перебора всех типов в программе.
Comments
- Anonymous
August 24, 2012
Интересно, как всегда. Побольше бы таких статей. Спасибо!