Переезд (вычисления)

Не путать с перенумерацией .

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

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

Сегментация

Объектные файлы сегментированы на различные сегменты или типы разделов памяти. Примеры типов сегментов включают сегмент кода (.text) , сегмент инициализированных данных (.data) , сегмент неинициализированных данных (.bss) или другие, установленные программистом, такие как общие сегменты или именованные статические сегменты.

Таблица переездов

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

В некоторых архитектурах исправление, которое пересекает определенные границы (например, границу сегмента) или не выравнивается по границе слова, является незаконным и помечается компоновщиком как ошибка.

DOS и 16-битная Windows

Дальние указатели ( 32-битные указатели с сегментом :offset, используемые для адресации 20-битного размером 640 КБ пространства памяти , доступного для DOS программ ), которые указывают на код или данные в исполняемом файле DOS ( EXE ), не имеют абсолютных сегментов, поскольку Фактический адрес кода/данных зависит от того, где программа загружена в память, и это неизвестно, пока программа не загружена.

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

32-битная Windows

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

Как для DLL , так и для EXE-файлов, которые выбирают рандомизацию расположения адресного пространства (ASLR), эксплойтов метод предотвращения , представленный в Windows Vista , таблицы перемещения снова становятся обязательными из-за возможности того, что двоичный файл может быть динамически перемещен перед выполнением, даже если они по-прежнему являются первыми, что загружаются в виртуальное адресное пространство.

64-битная Windows

При запуске собственных 64-битных двоичных файлов в Windows Vista и более поздних версиях ASLR является обязательным. , поэтому разделы перемещения не могут быть пропущены компилятором.

Unix-подобные системы

Формат исполняемых файлов и линкуемых файлов (ELF) и формат разделяемых библиотек, используемые большинством Unix-подобных систем, позволяют определить несколько типов перемещения.

Процедура переезда

Компоновщик считывает информацию о сегментах и ​​таблицы перемещения в объектных файлах и выполняет перемещение следующим образом:

• объединение всех сегментов общего типа в один сегмент этого типа
• назначение уникальных адресов времени выполнения каждому разделу и каждому символу, присвоение всему коду (функциям) и данным (глобальным переменным) уникальных адресов времени выполнения.
• обращение к таблице перемещения для изменения ссылки на символы так, чтобы они указывали на правильные адреса времени выполнения.

Пример

В следующем примере используется Кнута Дональда архитектура MIX и язык ассемблера MIXAL. Принципы одинаковы для любой архитектуры, хотя детали могут меняться.

• (A) Программа SUBR компилируется для создания объектного файла (B), представленного как машинным кодом, так и ассемблером. Компилятор может запустить скомпилированный код в произвольном месте, часто в месте 1, как показано. Ячейка 13 содержит машинный код инструкции перехода к оператору ST в ячейке 5.
• (C) Если SUBR позже будет связан с другим кодом, он может быть сохранен в месте, отличном от 1. В этом примере компоновщик помещает его в ячейку 120. Адрес в инструкции перехода, который сейчас находится в ячейке 133, должен быть перемещен. чтобы указать на новое местоположение кода для оператора ST , теперь это 125. [1 61, показанный в инструкции, является представлением машинного кода MIX 125].
• (D) Когда программа загружается в память для запуска, она может быть загружена в другом месте, отличном от того, которое назначено компоновщиком. В этом примере показано, что SUBR теперь находится в позиции 300. Адрес в инструкции перехода, который теперь находится в позиции 313, необходимо снова переместить, чтобы он указывал на обновленную позицию ST , 305. [4 49 — машинное представление 305 в MIX].

См. также

• Линкер (вычисления)
• Библиотека (вычисления)
• Объектный файл
• Предварительное связывание
• Статическая библиотека
• Самостоятельный переезд
• Независимый от позиции код (PIC)
• Перебазирование
• Сбор мусора
• Pointer swizzling — ленивая форма модификации указателя.
• Формат перемещаемого объектного модуля

Дальнейшее чтение

• Джонсон, Гленн (21 декабря 1975 г.) [13 ноября 1975 г.]. 11/34 Тест базовой логики управления памятью . Корпорация цифрового оборудования (DEC). MAINDEC-11-DFKTA-AD . Проверено 19 августа 2017 г.
• Форманяк, Питер Г.; Лейтч, Дэвид (июль 1977 г.). «Предлагаемый стандарт программного обеспечения микропроцессора» . BYTE — журнал малых систем . Технический форум. Том. 2, нет. 7. Питерборо, Нью-Гэмпшир, США: Byte Publications, Inc., стр. 34, 62–63. ковчег:/13960/t32245485 . Проверено 6 декабря 2021 г. (3 страницы) (Примечание. Описывает перемещаемый шестнадцатеричный формат от Mostek .)
• Огдин, Кэрол Энн; Колвин, Нил; Питтман, Том; Табб, Филип (ноябрь 1977 г.). «Перемещаемые форматы объектного кода» . BYTE — журнал малых систем . Технический форум. Том. 2, нет. 11. Питерборо, Нью-Гэмпшир, США: Byte Publications, Inc., стр. 198–205. ковчег:/13960/t59c88b4h, ковчег:/13960/t3kw76j24 . Проверено 6 декабря 2021 г. (8 страниц) (Примечание. Описывает перемещаемый шестнадцатеричный формат с помощью TDL .)
• Килдалл, Гэри Арлен (февраль 1978 г.) [1976]. «Простой метод статического перемещения абсолютного машинного кода» . Журнал доктора Добба по компьютерной гимнастике и ортодонтии . 3 (2). Народная компьютерная компания : 10–13 (66–69). ISBN  0-8104-5490-4 . #22 ковчег:/13960/t8hf1g21p . Проверено 19 августа 2017 г. [4] [5] [6] . Первоначально представлено по адресу: Килдалл, Гэри Арлен (1977) [22–24 ноября 1976 г.]. «Простой метод статического перемещения абсолютного машинного кода». Написано в Военно-морской аспирантуре , Монтерей, Калифорния, США. В Титусе, Гарольд А. (ред.). Отчет конференции: Десятая ежегодная конференция Asilomar по схемам, системам и компьютерам: доклады представлены 22–24 ноября 1976 г. Конференция Asilomar по сигналам, системам и компьютерам . Отель и конференц-центр Asilomar, Пасифик-Гроув, Калифорния, США: Western Periodicals Company. стр. 420–424. ISSN   1058-6393 . Проверено 6 декабря 2021 г. (609 страниц). (Этот метод «изменения размера», называемый перемещением границ страницы , можно было применить статически к CP/M-80 образу диска с помощью MOVCPM для того, чтобы максимизировать TPA для запуска программ. Он также использовался динамически CP/ отладчика M Инструмент динамической отладки (DDT) для перемещения в более высокий уровень памяти. Тот же подход был независимо разработан Брюсом Х. Ван Наттой из IMS Associates для создания перемещаемого кода PL/M . в качестве перемещения границ абзаца такими другой вариант этого метода позже использовался динамически HMA, самоперемещающимися TSR как KEYB , SHARE и NLSFUNC в DR DOS 6.0 и выше. Гораздо более сложный и детализированный метод на уровне байтов, основанный на несколько похожем подходе, был независимо задуман и реализован Матиасом Р. Полом и Акселем К. Фринке для их динамического устранения мертвого кода , чтобы динамически минимизировать влияние резидентных драйверов и TSR во время выполнения ( типа FreeKEYB)).
• Моссип, Ричард Х. (сентябрь – октябрь 1980 г.). Написано в Блумингдейле, Нью-Джерси, США. «Перемещаемый код» (PDF) . С-100 Микросистемы . Том. 1, нет. 5. Маунтинсайд и Спрингфилд, Нью-Джерси, США: Libes, Inc., стр. 54–55. ISSN   0199-7955 . ковчег:/13960/s2cfgkmxcwg. ковчег:/13960/s2qdm1t01nr. Архивировано (PDF) из оригинала 27 ноября 2023 г. Проверено 27 ноября 2023 г. [7] [8] (2 страницы) (Примечание. Описывает перемещение границ страниц и перемещение ассемблеров.)
• Хюитт, Роберт; Юбэнкс, Гордон ; Роландер, Томас «Том» Алан ; Лоус, Дэвид; Мишель, Ховард Э.; Халла, Брайан; Уортон, Джон Харрисон ; Берг, Брайан; Су, Вейлянь; Килдалл, Скотт ; Кампе, Билл (25 апреля 2014 г.). Лоус, Дэвид (ред.). «Наследие Гэри Килдалла: посвящение вехе CP / M IEEE» (PDF) (видеотранскрипция). Пасифик-Гроув, Калифорния, США: Музей истории компьютеров . Справочный номер CHM: X7170.2014. Архивировано (PDF) из оригинала 27 декабря 2014 г. Проверено 19 января 2020 г. […] Закономерности: […] «динамическое перемещение» ОС. Можете ли вы рассказать нам, что это такое и почему это важно? […] Юбэнкс : […] то, что сделал Гэри […] было […] ошеломляющим. […] Я помню тот день, когда в школе он прибежал в лабораторию и сказал: «Я придумал, как переехать». Он воспользовался тем фактом, что единственным байтом всегда был байт старшего порядка . И поэтому он создал растровое изображение . […] не имело значения, сколько памяти было у компьютера, операционную систему всегда можно было переместить в верхнюю память. Следовательно, вы можете коммерциализировать это […] на машинах с разным объемом памяти. […] вы не можете продавать 64K CP/M и 47K CP/M. Было бы просто смешно проводить жесткую компиляцию адресов. Итак, Гэри понял это однажды ночью, возможно, посреди ночи, думая о каком-то кодировании, и это действительно сделало возможным коммерциализацию CP/M. Я действительно думаю, что без этого переезда это была бы очень сложная проблема. Им показалось бы сложным заставить людей покупать его, и если бы вы добавили больше памяти, вам пришлось бы покупать другую операционную систему. […] Intel […] поменяла местами байты , верно, для адресов памяти. Но они всегда находились в одном и том же месте, поэтому можно было переместить его на границу в 256 байт , если быть точным. Таким образом, вы всегда можете переместить его, используя лишь растровое изображение того, где эти […] Законы: Определенно, самое красноречивое объяснение динамического перемещения, которое я когда-либо получал […] [9] [10] (33 страницы)
• Дорогой Экхард! Массенбах, Томас (1987). «CP/M 2 учится. Расширения модульной системы также для «старого» CP/M». c't - журнал по компьютерным технологиям (часть 1) (на немецком языке). 1987 (1). Хейзе Верлаг : 124–135; Дорогой Экхард! Массенбах, Томас (1987). «CP/M 2 учится. Расширения модульной системы также для «старого» CP/M». c't - журнал по компьютерным технологиям (часть 2) (на немецком языке). 1987 (2). Хейзе Верлаг : 78–85; Хак, Алекс (09 октября 2016 г.). «RSM для CP/M 2.2» . Домашний компьютер DDR (на немецком языке). Архивировано из оригинала 25 ноября 2016 г. Проверено 25 ноября 2016 г.
• Гузис, Чарльз «Чак» П. (16 марта 2015 г.). «Re: Программирование на языке ассемблера CP/M» . Винтажный компьютерный форум . Жанр: КП/М и МП/М. Архивировано из оригинала 01 февраля 2020 г. Проверено 01 февраля 2020 г. […] Вы когда-нибудь задумывались, как работает MOVCPM ? Поскольку BDOS и CCP находятся в верхней памяти, над пользовательским приложением, адреса необходимо менять каждый раз при изменении размера системной памяти. Теперь это требует перемещения адресов в 8080 коде , поскольку относительная адресация не является частью аппаратного обеспечения. Как это сделать, не реализовав полноценное перемещение ассемблера и загрузчика? На самом деле это довольно умно, и MP/M даже использует эту схему для создания файлов с возможностью перемещения по страницам. Вы просто ассемблируете исходную программу дважды , причем второе начало ассемблера на 100H (256 байт) выше первого. Затем два двоичных изображения сравниваются, байт за байтом, и создается карта , в которой пары байтов различаются по значению ровно на 100H. Результатом является список мест, в которых необходимо изменить значение перемещения, если необходимо переместить местоположение программы в памяти. MP/M называет этот тип файла PRL (перемещаемая страница), но я не знаю, придумал ли CP/M 2.2 имя для него. […]
• Гузис, Чарльз «Чак» П. (29 июля 2015 г.). «Re: Как работает MOVCPM.COM?» . Винтажный компьютерный форум . Жанр: КП/М и МП/М. Архивировано из оригинала 01 февраля 2020 г. Проверено 01 февраля 2020 г. […] MOVCPM использует ранний тип формата PRL. По сути, CP/M собирается дважды; второй раз — смещение 100H байт. Два двоичных файла сравниваются и создается растровое изображение . Установленный бит означает, что старший байт адреса должен быть скорректирован. Байты адреса младшего порядка не затрагиваются; следовательно, «перемещаемый файл страницы». Каждый байт растрового изображения соответствует 8 байтам двоичных данных. […] Итак, все, что нужно переместить в MOVCPM, — это часть изображения и его растровое изображение перемещения. […]
• Гузис, Чарльз «Чак» П. (08 ноября 2016 г.). «Re: Безопасно ли использовать RST 28h в программах сборки CP/M?» . Винтажный компьютерный форум . Жанр: КП/М и МП/М. Архивировано из оригинала 01 февраля 2020 г. Проверено 01 февраля 2020 г. […] Я упоминал файлы PRL и то, как они изначально появились в MOVCPM , но стали неотъемлемой частью MP/M и CP/M 3.0 . Но файлы PRL используют битовую карту , в которой каждый бит соответствует ячейке памяти; один бит указывает, что смещение перемещения страницы должно быть добавлено к соответствующей ячейке памяти. Если у вас очень мало абсолютных ссылок на память (в отличие от относительных), вы можете использовать список указателей (2 байта на ссылку), а не растровое изображение. Это маловероятно для кода 8080 , в котором нет относительных переходов, но может иметь значение для кода Z80 . Чтобы быстро это выяснить, нужно дважды ассемблировать программу; второе время смещено на 100H, затем сравните два двоичных файла. Преимущество перемещения во время выполнения состоит в том, что вам не придется нести штраф за код, который пытается обойти проблему перемещения — никаких «хитростей»; просто напишите прямой код. […]
• Рот, Ричард Л. (февраль 1978 г.) [1977]. «Переезд – это не просто программы перемещения» . Журнал доктора Добба по компьютерной гимнастике и ортодонтии . 3 (2). Риджфилд, Калифорния, США: People's Computer Company : 14–20 (70–76). ISBN  0-8104-5490-4 . № 22. Архивировано из оригинала 20 апреля 2019 г. Проверено 19 апреля 2019 г.
• Калингарт, Питер (1979) [1978-11-05]. «8.2.2 Перемещение погрузчика». Написано в Университете Северной Каролины в Чапел-Хилл . В Горовице, Эллис (ред.). Ассемблер, компилятор и трансляция программ . Серия «Разработка компьютерного программного обеспечения» (1-е издание, 1-е изд.). Потомак, Мэриленд, США: Computer Science Press, Inc., стр. 237–241 . ISBN  0-914894-23-4 . ISSN   0888-2088 . LCCN   78-21905 . Проверено 20 марта 2020 г. (2+xiv+270+6 страниц)
• Формат файла Microsoft OBJ . Microsoft , Служба поддержки продуктов. Примечание по применению SS0288. Архивировано из оригинала 9 сентября 2017 г. Проверено 21 августа 2017 г.
• Таненбаум, Эндрю Стюарт ; Бос, Герберт (2015). Современные операционные системы (4-е изд.). Pearson Education Inc. ISBN  978-0-13359162-0 .
• Эллиотт, Джон К. (5 июня 2012 г.) [02 января 2000 г.]. «Формат файла PRL» . seasip.info . Архивировано из оригинала 26 января 2020 г. Проверено 26 января 2020 г. […] Файл PRL — это перемещаемый двоичный файл, используемый MP/M и CP/M Plus для различных модулей, кроме файлов .COM . Этот формат файла также используется для файлов FID на Amstrad PCW . Существует несколько форматов файлов, в которых используются версии PRL: SPR (системный PRL), RSP (резидентный системный процесс). LINK-80 также может создавать файлы OVL ( оверлеи ), которые имеют заголовок PRL, но не подлежат перемещению. Драйверы GSX имеют формат PRL; то же самое относится и к резидентным системным расширениям (.RSX). […] [11]
• Эллиотт, Джон К. (5 июня 2012 г.) [02 января 2000 г.]. «Формат Microsoft REL» . seasip.info . Архивировано из оригинала 26 января 2020 г. Проверено 26 января 2020 г. […] Формат REL создается Microsoft M80 и Digital Research RMAC . […]
• фейлипу (05 сентября 2018 г.) [02 сентября 2018 г.]. «Поддержка PRL, исполняемый файл с возможностью перемещения по страницам для MP/M» . z88dk . Архивировано из оригинала 01 февраля 2020 г. Проверено 26 января 2020 г. […] Из собранных файлов Microsoft .REL компоновщик должен сгенерировать исполняемый файл формата .PRL для MP/M . Формат .PRL по сути представляет собой файл .COM с некоторой дополнительной информацией, позволяющей переместить программу и ее данные на любую страницу. Как выглядит файл .PRL? Первые байты — это размер программы, за которым следует источник программы по адресу 0x0100. После программы добавляется побитовая маска, позволяющая системе MP/M знать, какие байты в программе необходимо изменить при перемещении программы. Как компоновщик делает это, не разбирая все приложение? Заранее программа связана с двумя разными источниками 0x0100 и 0x0200 из объектов .REL. Хитрость компоновщика заключается в том, чтобы просто распознать, какие байты в двух версиях исполняемого файла различаются. Эти байты затем записываются в битовую маску, хранящуюся после исполняемого файла, и окончательная программа .PRL рассчитана на запуск с адреса 0x0100 плюс смещение страницы. Тот же трюк проделывается и с исполняемыми файлами .RSP и .SPR, за исключением того, что оба этих формата не используют смещение и запускаются с 0x0000 плюс смещение их страницы. […]
• Братья, Хардин (апрель 1983 г.). «Понимание перемещаемого кода» . 80 микро . Следующий шаг (39). 1001001, Inc .: 38 , 40, 42, 45. ISSN   0744-7868 . Проверено 6 февраля 2020 г. [12] [13]
• Братья, Хардин (апрель 1985 г.). «Перемещаемые программы: бродяги микрокомпьютеров» . 80 микро . Следующий шаг (63). CW Communications/Peterborough, Inc .: 98 , 100, 102–103. ISSN   0744-7868 . Проверено 6 февраля 2020 г. [14] [15]
• Сейдж, Джей (май – июнь 1988 г.). Карлсон, Арт (ред.). «ZCPR 3.4 — Программы типа 4» . Компьютерный журнал (TCJ) — Программирование, поддержка пользователей, приложения . ЗЦПР3 Уголок (32). Водопад Колумбия, Монтана, США: 10–17 [ 15–16 ]. ISSN   0748-9331 . ковчег:/13960/t1wd4v943 . Проверено 29 ноября 2021 г. [16] [17]
• Митчелл, Бриджер (июль – август 1988 г.). Карлсон, Арт (ред.). «Z3PLUS и перемещение — информация о ZCPR3PLUS и о том, как написать самоперемещающийся код Z80» . Компьютерный журнал (TCJ) — Программирование, поддержка пользователей, приложения . Продвинутый CP/M (33). Водопад Колумбия, Монтана, США: 9–15 . ISSN   0748-9331 . ковчег:/13960/t36121780 . Проверено 9 февраля 2020 г. [18] [19]
• Сейдж, Джей (сентябрь – октябрь 1988 г.). Карлсон, Арт (ред.). «Подробнее о перемещаемом коде, файлах PRL, ZCPR34 и программах типа 4» . Компьютерный журнал (TCJ) — Программирование, поддержка пользователей, приложения . ЗЦПР3 Уголок (34). Водопад Колумбия, Монтана, США: 20–25 . ISSN   0748-9331 . ковчег:/13960/t0ks7pc39 . Проверено 9 февраля 2020 г. [20] [21] [22]
• Сейдж, Джей (январь – февраль 1992 г.). Карлсон, Арт; МакИвен, Крис (ред.). «Десять лет ЗКПР» . Компьютерный журнал (TCJ) — Программирование, поддержка пользователей, приложения . Уголок Z-системы (54). С. Плейнфилд, Нью-Джерси, США: Socrates Press: 3–7 . ISSN   0748-9331 . ковчег:/13960/t89g6n689 . Проверено 29 ноября 2021 г. [23] [24] [25]
• Сейдж, Джей (май – июнь 1992 г.) [март – июнь 1992 г.]. Карлсон, Арт; МакИвен, Крис (ред.). «Программы типа 3 и типа 4» . Компьютерный журнал (TCJ) — Программирование, поддержка пользователей, приложения . Уголок Z-системы - Некоторые новые применения программ типа 4 (55). С. Плейнфилд, Нью-Джерси, США: Socrates Press: 13–19 . ISSN   0748-9331 . ковчег:/13960/t4dn54d22 . Проверено 29 ноября 2021 г. [26] [27]
• Ганссл, Джек (февраль 1992 г.). «Написание перемещаемого кода. Некоторый встроенный код должен выполняться более чем по одному адресу» . Программирование встраиваемых систем . Группа Ganssle – Совершенствование искусства создания встраиваемых систем / TGG. Архивировано из оригинала 18 июля 2019 г. Проверено 20 февраля 2020 г.