Этюды для программистов

26. Пища для УМа, или... СВЯЗЫВАЮЩИЙ ЗАГРУЗЧИК

В большинстве систем загрузчики находятся на положении пасынков. Их не любят пользователи, считая просто лишним препятствием на пути к вожделенному ответу. Они не нравятся и разработчикам компиляторов, поскольку являются составной частью системы (а вы считаете, что это не так?). Не по душе они и системным программистам, которые видят в них не более чем еще одно вспомогательное средство. Разве только коммерческие директора питают слабость к загрузчику за то, что он расходует так много машинного времени (и денег). Тем не менее, написав загрузчик для УМ-1, вы убедитесь, что его создание — очень стоящая задача.

Загрузчик УМ представляет собой довольно стандартный настраивающий загрузчик, предназначенный для работы с языком Мини (гл. 27) и ЭВМ УМ-1 (гл. 25). Основные функции загрузчика УМ связаны с интерпретацией перемещаемого языка загрузки, обработкой достаточно сложных таблиц символов и регистрацией ошибок в ходе загрузки. Программы на языке Мини могут состоять из независимо скомпилированных программных сегментов, и загрузчик УМ обеспечивает проверку соответствия типов величин, общих для нескольких сегментов, и библиотечный поиск для сборки полных программ. Кроме того, перемещаемый язык загрузки позволяет настолько просто генерировать команды перехода вперед, что компиляторы могут быть не двух-, а однопроходными. Многие находящиеся в эксплуатации загрузчики предусматривают еще более сложную обработку, однако такая обработка требует весьма развитой системы ввода/вывода и поэтому неприемлема для этюда. Не исключено, что вы не сможете до конца прочувствовать загрузчик УМ (как сильные, так и слабые его стороны), пока не сконструируете компилятор или же специально не изучите загрузчики по литературе.

На вход загрузчика УМ поступают программный файл и библиотечный файл, причем каждый из них может состоять из некоторого числа модулей. Если же позволяет система, то программа или библиотека могут состоять более чем из одного файла. Загружены должны быть в первую очередь все модули программы, а модули из библиотечного файла загружаются, лишь если они соответствуют первичным ссылкам. К концу загрузки должен определиться ровно один начальный адрес программы, иначе фиксируется фатальная ошибка загрузки. В результате работы загрузчика получается файл абсолютной загрузки, который описывался в гл. 25. Загрузчик УМ содержит как счетчик абсолютного размещения (САР), так и счетчик относительного размещения (СОР). Перед началом загрузки САР устанавливается на адрес 40₁₆. Всякий раз, когда начинается очередной модуль, САР настраивается на ближайшую свободную границу слова, а СОР обнуляется [52]. После того как загружен последний модуль, САР а последний раз продвигается к границе слова, следующего за верхней точкой модуля, и употребляется для определения значения абсолютного внешнего символа Максимальный Адрес.

Перемещаемый язык загрузки состоит из набора команд загрузки, длиной восемь битов каждая. Команды записываются с помощью кодировок переменной длины, при этом отдельные параметры могут оказаться запрятанными в самих командах. Остальные параметры могут быть переменной длины, а употребляемые в командах выражения допускаются любой сложности. Все имена должны быть декларированы до их использования; описанные однажды, они везде ниже заменяются на их порядковые номера с целью уменьшения размера загрузочного модуля. Поскольку модули должны генерироваться однопроходным компилятором Мини, их размер в явном виде не указан. Поэтому загрузчик УМ должен следить за маркером конца, который позволит установить размер модуля. Внешние имена, встречающиеся в текущем модуле, должны быть описаны раньше всех других спецификаций загрузки. После того как все модули обработаны, из таблицы символов необходимо исключить все внутренние имена, глобальные символы сохранить и проделать соответствующие манипуляции с картой загрузки. Для целей диагностики можно ввести специальные символы, употребляемые только в карте загрузки. Загрузчик УМ в состоянии проверять типы внешних процедур и их аргументов.

Записи в модуле загрузки представляют собой цепочки внешних литер переменной длины. В качестве литер используются либо шестнадцатеричные цифры, которые воспринимаются группами и образуют целые величины, либо литеры, почерпнутые из набора ASCII для УМ-1, которые представляют сами себя[53]. Первые шесть литер записи всегда связаны с ее физической структурой и неизменно располагаются в одном и том же формате. Позиция 1 содержит литеру 1, если данная запись — последняя в модуле, и 0 — во всех остальных случаях. В позициях 2—4 определяется трехзначный шестнадцатеричный порядковый номер записи в модуле — самая первая запись имеет номер 000. Нарушение порядка номеров записей является нефатальной ошибкой. Когда в модуле набирается 1000 записей, порядковый номер продолжается с 000. В позициях 5 и 6 указывается шестнадцатеричная длина записи. Эта длина включает в себя первые шесть литер и лежит, следовательно, между 07 и FF. Содержательная информация записи располагается во второй ее части, непосредственно примыкающей к постоянной шапке, и состоит из последовательности логических элементов загрузки. Логические элементы загрузки на границах физической записи могут произвольно прерываться.

Логический элемент загрузки начинается с двух шестнадцатеричных цифр, идентифицирующих операцию загрузки, за которой следуют, если необходимо, параметры. Числовые параметры передаются всегда цепочкой шестнадцатеричных цифр такой длины, которая необходима для представления числа. Имена начинаются с поля счетчика из двух шестнадцатеричных цифр, за которым следуют фактические литеры имени — в количестве, указанном в счетчике. Таким образом, элемент 682C04Fool представляет собой операцию 68 — описание внешней ссылки с коротким номером символа 2С и именем Fool состоящим из четырех литер. Если параметром служит выражение, оно содержит собственные операции и может быть сколь угодно длинным. Заметим, что для задания одной внутренней литеры берутся две внешние шестнадцатеричные цифры.

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

Загрузка абсолютная 0000сссс Данные

Поле счетчика сссс содержит уменьшенное на единицу количество внутренних литер данных, подлежащих загрузке. Остальная часть элемента состоит из числовых данных, которые требуется загрузить без смещения с текущим САР. К счетчикам САР и СОР прибавляется длина загруженного объекта.

Загрузка слова со смещением 00010000 Данные

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

Загрузка выражения 000110ww Выражение

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

Загрузка относительно символа 0001010l Символ Данные

Счетчики размещения настраиваются на ближайшую границу четного байта, если они уже на нее не установлены. Загружается восемь цифр данных. К двум младшим байтам данных в памяти прибавляется значение символа, номер которого указан в первом аргументе. Номер символа содержит две цифры, если I=0, и четыре цифры, если l=1. Смещение должно задаваться перемещаемым символом, но само значение его может быть еще не определено.

Выражения, которые должны во время загрузки получить численные значения, вычисляются с использованием 32-разрядного сумматора, снабженного признаком типа (или абсолютного, или относительного). Цепочка элементов загрузки, определяющих загружаемое выражение, может быть произвольной длины и во всех случаях оканчивается признаком конца выражения. В выражении могут употребляться лишь те символы, значения которых уже определены, и только в допустимых сочетаниях типов в соответствии с табл. 26.1. Последняя приведенная в таблице комбинация возможна лишь при условии, что оба элемента располагаются в текущем модуле. В исходном состоянии сумматор, как правило, равен абсолютному нулю.

Арифметическая операция 0010lsot Операнд

Если бит о равен нулю, производится операция сложения; в противном случае — операция вычитания.

Таблица 26.1. Допустимые комбинации типов операндов

Если бит s равен нулю, операнд представляет собой константу, и тогда бит t указывает на то, является ли константа абсолютной (t = 0) или относительной (t = 1). В противном случае (s = 1) операнд представляет собой номер символа. Бит l указывает на то, содержит ли операнд две (l = 0) или четыре (l = 1) цифры. Операция выполняется, и значение соответствующего типа помещается на сумматор.

Установка СОР на сумматор 00110000 Нет

Текущее содержимое сумматора игнорируется, и в него помещается величина относительного типа, равная текущему значению СОР.

Конец выражения 00110001 Нет

Текущее выражение окончено, при этом на сумматоре находится его значение.

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

Определение внешнего символа 010lt000 Номер Выражение

Внешнему символу, номер которого задается первым аргументом, присваивается значение второго аргумента. Номер символа состоит из двух цифр при l = 0 или четырех цифр в противном случае. Если бит t равен 0, то символ абсолютный, в противном случае — относительный. Типы определяющего выражения и уже занесенного в таблицу символа (тип символа задается параметром t) должны совпадать. Во время определения любые ссылки на символ должны быть заполнены.

Определение символа в карте 0100t001 Имя Выражение

Выражение, представленное вторым аргументом, вычисляется и приписывается символу, имя которого указано в первом аргументе, для последующего помещения в карту загрузки. Если t = 0, то тип символа абсолютный, в противном случае — относительный.

Определение ссылки вперед 010lt01h Номер Выражение

Ссылке вперед, номер которой указан в первом аргументе, ставится в соответствие выражение, приведенное во втором аргументе. При l = 0 номер ссылки состоит из двух цифр, в противном случае — из четырех. Символ является абсолютным, если t = 0, и относительным в противном случае. Если h = 0, то ссылка вперед сохраняется в таблице символов, в противном случае после данного определения ссылка исключается из таблицы.

Описание внешней ссылки 011lt00p Номер Имя

Символ с именем, указанным в аргументе, и номером, приведенным в первом аргументе, декларируется как ссылка на внешний символ другого модуля. Если l = 0, номер символа состоит из двух цифр, в противном случае — из четырех. При t = 0 тип символа абсолютный, в противном случае — относительный. Равенство р = 0 означает, что ссылка первична и ее надлежит отыскать и заполнить; в противном случае ссылка вторична, и ее необходимо заполнять, лишь если символ определяется по другой причине.

Описание ссылки вперед 011lt010 Номер

Декларируется ссылка вперед на символ, номер которого указан в аргументе. Если l = 0, номер содержит две цифры, в противном случае — четыре. При t=0 символ абсолютный, в противном случае — относительный.

Описание внешнего имени 011lt011 Номер Имя

Символ с номером и именем, указанными соответственно в первом и втором аргументах, декларируется в качестве внешнего символа, который будет определен в данном модуле. Описания внешних имен должны располагаться в самом начале модуля. Если l = 0, то номер символа содержит две цифры, в противном случае — четыре. При t = 0 тип символа абсолютный, в противном случае — относительный.

Определение типов процедуры 011l0100 Номер N Тип1...ТипN

С символом, номер которого указан в первом аргументе, соотносится цепочка типов, длина которой задается двумя литерами второго аргумента. Если I = 0, то номер символа состоит из двух цифр, в противном случае — из четырех. Каждый тип представляется одной литерой. Чтобы определить символ, он должен быть уже описан в этом разделе как внешний. Данная команда, как и последующая, может употребляться компилятором Мини для проверки правильности количества и типов аргументов внешних процедур. В компиляторе необходимо установить способ представления возможных типов аргументов в виде целых чисел, которого надо придерживаться при всех трансляциях.

Проверка типов процедуры 011l0101 Номер N Тип1...ТипN

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

Установка начального адреса 10010000 Выражение

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

Установка на четный адрес 10100000

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

Установка на адрес слова 10110000

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

Установка счетчиков размещения 11000000 Выражение

Оба счетчика размещения принимают значение выражения, которое должно быть относительным и неотрицательным. Не забудьте, что САР—начало=СОР.

Пустая команда 11010000

Невыполняемая команда. Может встречаться в выражениях.

Конец модуля 11111111

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

Для того чтобы разъяснить некоторые из введенных понятий, приведем образец программы на языке ассемблера УМ-1 и ее модуль загрузки, сгенерированный гипотетическим ассемблером,

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

Тема. Сконструируйте загрузчик УМ. На его вход должна поступать последовательность перемещаемых объектных файлов, а на выходе — как файл абсолютной загрузки, так и карта загрузки. Непременно сигнализируйте об ошибках загрузки. Необходимо, чтобы карта загрузки была отсортирована как по именам, так и по адресам. Содержащиеся в карте символы должны включать в себя внешние символы и ссылки, а также другие определенные символы. Кроме того, укажите размер каждого модуля.

Указания исполнителю. В большинстве загрузчиков время расходуется на два вида работ: организацию ввода/вывода и обработку таблицы символов. Очевидно, что коль скоро считывается и записывается большой объем информации, существует нижний предел времени, затрачиваемого на ввод/вывод. Тем не менее, в данной работе упор должен делаться, во всяком случае, не на технику совершенствования ввода/вывода, да и язык высокого уровня, видимо, не очень-то способствует этому. А вот работу с таблицей символов, если ее тщательно продумать, улучшить можно. Поэтому надо так спланировать загрузчик, чтобы можно было легко подключать и отключать разные программы обработки таблиц символов. Напишите простую программу управления таблицами, отладьте загрузчик полностью, а потом попытайтесь совершенствовать операции с символами.

Накопленный опыт показывает, что работу по подготовке тестирующих программ надо начинать пораньше. Перевод языка ассемблера в модуль загрузки оказывается труднее, чем может показаться. Не исключено, что вам захочется применить ассемблер для УМ-1, предлагавшийся в гл. 25 в качестве средства отладки. Постарайтесь воспользоваться каждой командой, по крайней мере, один раз.

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

Длительность исполнения. Одному исполнителю на шесть недель; двоим или троим — на 3 недели. Каждый участник должен сделать одну тестовую программу в перемещаемом объектном коде.

Баррон (Barron D. W.). Assemblers and Loaders. Macdonald, London, 196& [Имеется перевод: Баррон Д. Ассемблеры и загрузчики. — М.: Мир, 1974.]

Прессер, Уайт (Presser L., White J. R.). Linkers and Loaders, Comput Surveys, 4, 3, pp. 149—167, 1972.

Книга Баррона представляет собой элементарное введение в ассемблеры и загрузчики. Описанный в ней загрузчик близок к нашему и вместе с тем рассмотрен более подробно. Прессер и Уайт описывают систему, применяемую на IBM 360. Поскольку в системе 360 исключено перемещение, чего нельзя сказать о других системах, основное внимание уделяется связыванию программ