Динамическое связывание в Windows и Linux

Перевод Александр Тимаков

В этой статье обсуждается концепция разделяемых библиотек как в Windows так и  Linux,  представляется  обзор различных структур данных, чтобы объяснить, как работает динамическое связывание (linking) в этих системах. Документ будет полезен для разработчиков, заинтересованных в обеспечении безопасности, нуждающихся в высокой скорости динамического связывания, и предполагает наличие некоторых предварительных знаний о процессе динамического связывания.

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

 Статические и динамические библиотеки.

Библиотека представляет собой набор подпрограм, который позволяет коду этих подпрограм использоваться в виде отдельных модулей. Исполняемые файлы и библиотеки создают взаимные ссылки в процессе т.н. «линковки» или связывания, который осуществляется редактором связей (linker).

В первом приближении, библиотеки можно разделить на статические и динамические.

Статические библиотеки являются набором объектных файлов и традиционно имеют расширение «.а» в UNIX-подобных ОС и «.lib» в Windows. Когда программа связывается со статической библиотекой, машинный код из объектных файлов для каждой используемой программой функции библиотеки копируется из библиотеки в конечный исполняемый файл.

В отличие от статических, в динамических библиотеках код библиотеки не прикрепляется к исполняемому файлу в время связывания. В зависимости от того когда и как осуществляется привязка подпрограмм по адресам, процесс связывания можно разделить на предварительное связывание, связывание на этапе загрузки, неявное связывание во время запуска и явное связывание во время запуска (prelinking, load time linking, implicit run-time linking,explicit run-time linking).

 Адресно-независимый код (Win32 DLL и «.so»)

Адресно-независимый код (Position Independent Code, PIC) может быть скопирован в любое место памяти без изменения и затем выполнен, в отличие от релоцируемого кода, который требует специальной обработки редактором связей, чтобы выполняться в нужном месте памяти.

Библиотеки Win32 DLL не являются адресно-независимыми. Им нужна обработка на этапе загрузки, за исключением случаев, когда фиксированное смещение, с которым библиотека была собрана не используется на момент загрузки. Смещения на один адрес могут быть разделены между процессами, но если различные процессы имеют конфликтующие между собой пространства памяти, загрузчик вынужден генерировать несколько копий библиотеки в памяти. Когда Windows-загрузчик загружает DLL в память, он открывает файл библиотеки и пытается записать код по предпочитаемому библиотекой базовому адресу. Если с данными страницами памяти уже работали, диспетчер страниц (paging system) обнаружит, что данные страницы уже присутствуют в памяти. В этом случае диспетчер просто отобразит эти страницы для нового процесса, так как перемещение по предпочтительному адресу уже было сделано загрузчиком. В противном случае необходимая страница загружается с диска.

Если же предпочитаемое библиотекой адресное пространство недоступно, загрузчик помещает страницы в свободное пространство памяти. В этом случае данный сегмент памяти помечается как COW (copy-on-write), хотя ранее он был помечен как read+executable. Это происходит потому, что загрузчик вынужден выполнять правку кода в процессе перемещения, что делает необходимым сохранять страницу в файл подкачки.

В Linux эта проблема решена использованием PIC (Position Independent Code, адресно-независимый код). Разделяемые объекты в Linux обычно содержат PIC который который не влечет за собой необходимость перемещать библиотеку во время загрузки. Все сегменты кода могу быть разделены между процессами, использующими одну библиотеку и могут быть загружены/выгружены в файловую систему (файл подкачки, прим. перевод.). В архитектуре x86 не существует простого пути адресации данных относительно к текущему расположению, так как все переходы и вызовы являются командно-зависимыми. Таким образом все ссылки на статические глобальные объекты будут перенаправлены через таблицу, извесную как Global Offset Table (GOT, «глобальная таблица смещений»).

 Динамическое связывание в Linux.

 Структуры данных в ELF

Так как эта статья посвящена не формату ELF, мы будем обсуждать только тот небольшой объём структур данных, которые затрагивают наше обсуждение. Для динамического связывания, редактор связей ELF использует 2 процессорно-зависимые таблицы, глобальную таблицу смещений (GOT) и PLT (Procedure Linkage Table, «таблица связывания для процедур»).

 Глобальная таблица смещений (Global Offset Table).

Редакторы связей ELF поддерживают адресно-независимый код через глобальную таблицу смещений в каждой разделяемой библитеке. Эта таблица содержит абсолютные адреса для всех статических данных используемых программой. Адрес самой таблицы обычно содержится в регистре EBX и является относительным адресом для участка кода, который на неё ссылается.

 Таблица связывания процедур (Procedure Linkage Table).

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

Кроме использования упомянутыхтаблиц, редактор связей обращается к структуре .dynsym, которая содержит все импортированные и экспортированные символы файла, .dynstr, содержащей именованные строки для этих сиволов, и к .hash, которая содержит хэш-таблицу, которую редактор связей при загрузке может использовать для быстрого поиска символов, в также к .dynamic, которая в свою очередь является упорядоченным списком значений и указателей. 

В секции .dynamic, важными для нас типами являются:

DT_NEEDED: Элемент содержит смещение в таблице строк оканчивающихся на NULL, строки содержат названия необходимых библиотек. Это смещение является индексом для записей в таблице DT_STRTAB.

DT_HASH: Элемент содержит смещение для хэш-таблицы символов на которую указывает DT_SYMTAB.

DT_STRTAB: адрес таблицы строк.

DT_SYMTAB: адрес таблицы симвлов.

 Хэш-таблица символов

nBuckets //no of bucket entries
nChains   //no of chain entries
bucket[]
chain[]

Оба массива Buckets и Chain содержат индексы таблицы символов. Для символа, который требуется найти, вычисляется хэш-функция и хэш %nBuckets используется как индекс для массива bucket[]. Элемент из bucket[] содержит индекс symindx как для массива chain[] так и для таблицы символов. Если элемент таблицы символов не подходит, происходит выборка следующего элемента таблицы символов с таким же значением хэш-функции с использованием индекса, полученного из chain[symindex].

Как это работает

В Linux редактор динамических связей ld.so сам по себе является разделяемой библиотекой ELF. В начале старта программы система отображает ld.so в часть адресного пространства и запускает его инициализационный код. Основная точка входа для загрузчика определена в dl_main(elf/rtld.c). Редактор связей переопределяет ссылки на свои собственные процедуры которые необходимы для последующей загрузки чего бы то ни было ещё.

Динамический сегмент файла ELF (на который указывает значение из заголовка программы) содержит указатель на таблицу символов (DT_STRTAB) и на записи в DT_NEEDED, каждое из этих значений содержит смещение в таблице строк, которая содержит имена необходимых для работы библиотек. Таким образом для исполняемого файла редактор связей создаёт список, содержащий библиотеки, подлежащие загрузке.

У нас есть два метода для того, чтобы указать объекты, которые нужно загрузить предварительно: через переменную окружения LD_PRELOAD или через файл /etc/ld.so.preload. Последний может быть использован когда из соображений безопасности вы не используете переменные окружения. Загрузчик добавляет к указанному нами списку предварительной загрузки библиотеки DT_NEEDED (из заголовка файла – прим. перев.).

Для каждой записи в получившемся списке редактор связей ищет файл, содержащий нужную библиотеку. Когда таковой найден, редактор считывает ELF-заголовок, чтобы найти заголовок программы, который указывает на динамический сегмент. Затем редактор отображает библиотеку в адресное пространство процесса. Для динамического сегмента он добавляет таблицу символов библиотеки в цепочку символьных таблиц, и, если у данной библиотеки есть зависимости от других библиотек, добавляет их в спискок для последующей загрузки. Для полноты картины отметим, что для каждой библиотеки создаётся структрура ( 'struct' ) link_map и добавляется в общий список для связанных объектов.

Редактор связей держит в памяти список уже связанных (“linked”) библиотек для каждого файла (с типом записи списка struct link_map, описанным параметром dl_loaded в struct rtld_global). Редактор использует хэш-таблицу (DT_HASH) представленную в ELF-файле чтобы ускорить процедуру поиска символов.

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

Переменная LD_BIND_NOW определяет поведение редактора при создании динамических связей. Если переменная задана, редактор обрабатывает записи в таблице связывания процедур (PLT) (эти записи имеют тип R_386_JMP_SLOT) в процессе загрузки. В противном случае редактор будет делать т.н. “lazy linking” (“связывание по запросу”), т.е. адреса конкретной процедуры не вычисляются до тех пор, пока не производится её вызов.

Обзор процедуры связывания по запросу.

В этой главе мы проследим, как на этапе загрузки будут обработаны функции, включённые в разделяемую библиотеку libtest.so. Исполняемый файл, дизассемблированный при помощи gdb, был создан с использованием связанной адресно-независимой библиотеки libtest.so.

Рисунок 1. Исходный код, дизассемблированный gdb.

Давайте начнём трассировку с инструкции вызова, показанной на рисунке 1.

Адрес, указанный в инструкции является записью в таблице связывания процедур (PLT). Первые 4 записи в PLT (из которых последние 2 зарезервированы) одинаковы для всех вызовов процедур. Остальные сгруппированы в блоки по 3 записи, один блок на каждую процедуру. Это показано на рисунке 2.

Рисунок 2. Несколько записей в начале таблицы связывания процедур (PLT).

Рисунок 3. Глобальная таблица смещений (GOT) считанная с диска.

Инструкция состоит из перехода по адресу, указанному в глобальной таблице смещений *(GOT+0x14), который в свою очередь указывает на запись в PLT  с адресом 0x80483aa (как показано на Рисунке 2).

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

Рисунок 4. Объект в таблице смещений (длина 8 байт).

Как видно на Рисунке 4, размер записи в таблице перемещний (RELSZ) составляет 8 байт. Смещение на 0x10 даёт на третью запись в таблице .rel.plt, которое является записью смещения для 'm'. Смещение внутри таблицы даёт нам соответствующий адрес в глобальной таблице смещений, который должен быть обновлён.

Потом выполнение кода передаётся по адресу заданному в первой записи в таблице связывания процедур (PLT), которая является общей для всех вызовов.

Рисунок 5. Точка останова (breakpoint).

По записи в PLT опять делается переход по адресу GOT+8. Загрузчик в время загрузки обновил значения по адресам GOT+4 и GOT+8 (которые, как видно на Рисунке 3, ранее были равны 0х000000). Сейчас GOT+8 (0x4000bcb0) указывает на адрес, который занят библиотекой ld-2.3.2.0 (редактор динамический связей), см. Рисунок 6.

 

Рисунок 6. Адрес отображённый редактором динамических связей.

Посколько процедура, проведённая редактором динамических связей, вычленила значение символа с использованием таблицы во время загрузки и сохранила адрес вызова подпрограммы (0x400177db) в глобальной таблице смещений (0x804963c) (Рисунок 5), все последующие вызовы подпрограммы будут совершаться напрямую по её адресу.

Подробнее о динамическом редакторе связей ld.so

Вернемся к записям в глобальной таблице смещений (GOT). Как мы уже видели, по GOT+8 содежит адрес процедуры редактора связей ответственной за разрешение символов. По адресу GOT+4 загрузчик поместил указатель на структуру struc link_map, определённую в include/link.h. Глобальная таблица смещений заполняется процедурой elf_machine_runtime_setup определённой в dl-machine.h.

Рассмотрим её поподробнее:

Struct link_map
{
    ElfW(Addr) l_addr;		/* Base address shared object is loaded at.  */
    char *l_name;		/* Absolute file name object was found in.  */
    ElfW(Dyn) *l_ld;		/* Dynamic section of the shared object.  */
    struct link_map *l_next, *l_prev; /* Chain of loaded objects.  */

   /* All following members are internal to the dynamic linker.
       They may change without notice.  */

/* Indexed pointers to dynamic section.*/
    ElfW(Dyn) *l_info[DT_NUM + DT_THISPROCNUM + DT_VERSIONTAGNUM
		     + DT_EXTRANUM + DT_VALNUM + DT_ADDRNUM];
    const ElfW(Phdr) *l_phdr;	/* Pointer to program header table in core.  */
    ElfW(Addr) l_entry;		/* Entry point location.  */
    ElfW(Half) l_phnum;		/* Number of program header entries.  */
    ElfW(Half) l_ldnum;	/* Number of dynamic segment entries.  */

    /* Array of DT_NEEDED dependencies and their dependencies, in
       dependency order for symbol lookup (with and without
       duplicates).  There is no entry before the dependencies have
       been loaded.  */
    struct r_scope_elem l_searchlist;

   
 /* Symbol hash table.  */
    Elf_Symndx l_nbuckets;
    const Elf_Symndx *l_buckets, *l_chain;

В тот момент, когда происходит выполнение процедуры разрешения символов, в стеке у нас находятся адрес списка  связей и необходимое смещение. Смещение, которое обсуждалось нами выше, даёт нам индекс в таблице символов для нужного символа и  соответсвующий адрес в глобальной таблице смещений, по которому должен быть записан вычисленный адрес. Адрес для разрешения символов (GOT+8) указывает на объект ELF_MACHINE_RUNTIME_TRAMPOLINE.

Взглянем на ELF_MACHINE_RUNTIME_TRAMPOLINE, определённый в dl-machine.h. В данном коде сохраняются регистры и делается вызов функции fixup():

movl 16(%esp), %edx	# Copy args pushed by PLT in register.  Note
movl 12(%esp), %eax	# that `fixup' takes its parameters in regs.
call fixup		# Call resolver.

В свою очередь функция fixup определена в dl-runtime.c. Массив l_info заданный в внутри структуры struct link_map содержит индексированные указатели на динамическую секцию.

const ElfW(Sym) *const symtab

    = (const void *) D_PTR (l, l_info[DT_SYMTAB]);

const char *strtab = (const void *) D_PTR (l, l_info[DT_STRTAB]);

const PLTREL *const reloc

    = (const void *) (D_PTR (l, l_info[DT_JMPREL]) + reloc_offset);

Из l_info при выполнении кода извлекаются указатели на таблицу символов и таблицу смещений. Адрес необходимого смещения вычисляется путем прибавления к адресу начала таблицы необходимого смещения в таблице:

const ElfW(Sym) *const symtab
    = (const void *) D_PTR (l, l_info[DT_SYMTAB]);
const char *strtab = (const void *) D_PTR (l, l_info[DT_STRTAB]);

const PLTREL *const reloc
    = (const void *) (D_PTR (l, l_info[DT_JMPREL]) + reloc_offset);

Из reloc->r_info получим индекс уже для таблицы символов чтобы, используя его, получить информацию из таблицы (reloc->r_offset+1->l_addr).

Функция fixup() вызывает _dl_lookup_symbol() для каждой записи в массиве библиотек. Массив содержит элементы типа r_scope_elem для библиотек, и составляет часть общего поля поиска. Эта структура заполняется во время загрузки.

struct r_scope_elem
{
  /* Array of maps for the scope.  */
  struct link_map **r_list;
  /* Number of entries in the scope.  */
  unsigned int r_nlist;
};

do_lookup определена в FCT в файле do-loopup.h. Взглянем на эту процедуру так, как буд-то бы она была написана на обычном английском языке:

Do_lookup algorithm()  // алгоритм do_loopup
{
// для всех объектов link_map, полученных через scope->r_list выполнить:
do{ 
//получить адрес таблицы символов через link_map->l_info 
    

   // получить адрес таблицы строк через link_map->l_info 
    

   // найти соответствующее значение элемента хэша в объектах таблицы символов 
    

   //используя хэш полученный из названия элемента при помощи _dl_lookup_symbol() 
    

   // используя индексные записи в хэше chain, link_map->l_chain
Do{ 
Lookup the symbol table entry using the index.
Compare the symbol name with (strtab + sym->st_name). 
If found, return the symbol table entry with the link_map structure; 
}
}

Вернёмся к fixup():

/*link_map ->l_addr points to the base load address */

value = link_map->l_addr + sym->st_value

/* Finally, fix up the plt itself.  */

return elf_machine_fixup_plt (l, result, reloc, rel_addr, value);

Возвращаясь к dl-machine.h, она восстанавливает сохранённые регистры:

xchgl %eax, (%esp)	# Get %eax contents and store function address.
ret $8			# Jump to function address.

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

Подводя итоги первой части

В этой части мы обсудили использование динамического связывания для Linux и Windows, останавливаяясь преимущественно на Linux. Во второй части мы поближе рассмотрим этот процесс в Windows в этом же ключе, упомянем “lazy linking” (“связывание по запросу”) и Delay Load Helper, а затем попробуем ускорить процесс связывания в обоих системах. Оставайтесь на связи.

Ссылки

1. Linkers and Loaders by John Levine.
2. Glibc-2.3.3 source code.
3. Prelink by Jakub Jelinek, RedHat Inc
4. Inside Windows An In-Depth look into the Portable Executable File format, part2
5. The MSDN Library
6. UNIX Man pages

Об авторах

Reji Thomas инженер-разработчик из команды Symnatec Corp. Среди его интересов математические науки, компьютерная безопасность, компиляторы, создание финансовых моделей. Bhasker Reddy также привлчён к разработке ПО для Symantec Corp.; В круг его интересов входят компиляторы, системное программирование и теория операционных систем.