Как x86_x64 адресует память

в 13:05, , рубрики: miran, x86_x64, адресация памяти, Алгоритмы, Блог компании Дата-центр «Миран», Компьютерное железо, память, Программирование, Процессоры

Сегодня я собираюсь поговорить про адресацию памяти: один, казалось бы, небольшой, и тем не менее удивительно непростой элемент семантики команд архитектуры х86_64. В особенности хочется поговорить про команду mov и то, как через только одну эту команду х86_64 пользователю становятся доступны различные методы адресации памяти.

Я не буду говорить про остальные затрагивающие память команды (то есть, благодаря CISC, почти все остальные), команды которые пишут массивные фрагменты памяти (это о тебе, fxsave), или иные касающиеся темы вопросы (модели кода, независящий от адреса код, и бинарная релокация). Я также не буду затрагивать исторические режимы адресации или режимы, которые активны при работе процессора x86_64 не в 64-битном режиме (т.е. любые отличные от long mode с 64-битным кодом).

Некоторые ограничения

Несмотря на кошмарное наследие кодирования команд х86_64, а может и благодаря ему, у адресации памяти есть некоторые ограничения.

Начнем с хорошего:

  • На достаточно высоком уровне в архитектуре х86_64 есть всего два режима адресации.
  • Все регистры в обоих режимах адресации должны быть строго одинакового размера. Другими словами, мы не можем странным образом смешивать 64, 32 и 16-битные регистры и получать актуальный адрес — в кодировании х86_64 для подобного маневра попросту нет места.


В остальном все не столь радужно:

  • Один из этих двух режимов адресации все еще абсурдно сложен.
  • Регистры должны быть одинакового размера, но не обязаны быть той же разрядности что и режим процессора. Например, если мы добавим в нашем кодировании префикс байт (0x67), мы можем пользоваться 32-битными регистрами вместо 64-битных.

Адресация “Scale-Index-Base-Displacement”

Я не имею представления как назвать этот режим, поэтому называю его “Scale-Index-Base-Displacement”. Насколько я понимаю, ни Intel, ни AMD вообще не воспринимают его как единый режим и вместо этого упоминают в виде типичного набора связных режимов с широким диапазоном различных методов кодирования.

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

  • Scale: 2-битный коэффициент константы, обычно равный 1, 2, 4 или 8.
  • Index: Любой регистр общего назначения (rax, rbx, &c).
  • Base: Любой регистр общего назначения.
  • Displacement: Интегральный сдвиг. Обычно даже в 64-битном режиме он ограничен 32 битами, но с использованием некоторых методов кодирования может быть и 64-битным. Мы об этом еще поговорим.

Эти четыре параметра можно объединить в несколько различных комбинаций, полный список в порядке увеличения сложности можно увидеть ниже:

  • Displacement
  • Base
  • Base + Index
  • Base + Displacement
  • Base + Index + Displacement
  • Base + (Index * Scale)
  • (Index * Scale) + Displacement
  • Base + (Index * Scale) + Displacement

Давайте разберем каждую комбинацию по порядку.

Displacement

Это, пожалуй, самый простой механизм адресации в семье х86: displacement обрабатывается как абсолютный адрес памяти, и сам по себе, к несчастью, совершенно бесполезен в архитектуре х86_64. Помните, мы говорили, что displacement почти всегда ограничен 32 битами? Так как абсолютный адрес в х86_64 это 64 бита (на самом деле 48, но это неважно), он попросту не поместится в displacement, однако в виде исключения можно использовать 64-битный displacement с регистром a*.

Синтаксис Intel:

; store the qword at 0x00000000000000ff into rax
mov rax, [0xff]
; store the dword at 0x00000000000000ff into eax
mov eax, [0xff]
; store the word at 0x00000000000000ff into ax
mov ax, [0xff]
; store the byte at 0x00000000000000ff into al
mov al, [0xff]

gas (GNU ассемблер) и в 32, и в 64-битном режимах ссылается на них как на movabs.

Зачем мне (или моему компилятору) пользоваться этим режимом?

Для начала, из-за моделей кода, не имеющих отношения к данному посту. Подробнее по теме можно прочесть в замечательном посте Eli Bendersky по ссылке.

А теперь по делу: у большинства программ есть как минимум несколько статичных адресов, которые определяются в compile-time, аналогично глобальным переменным. Например, результатом следующей тривиальной программы:

extern long var;

void f(long x) { var = x; }

…будет:

f:
        mov     rax, rdi
        movabs  QWORD PTR [var], rax
        ret

(Посмотреть на Godbolt.)

Base

Адресация через регистр base добавляет еще один уровень неопределенности поверх абсолютной адресации: вместо использования закодированного в поле displacement команды абсолютного адреса, адрес загружается из указанного регистра общего пользования (Причем любого такого регистра! Ура!)

Эта неопределенность позволяет нам проводить абсолютную адресацию с произвольным регистром назначения по следующему шаблону:

; store the immediate (not displacement) into rbx
mov rbx, 0xacabacabacabacab

; store the qword at the address stored in rbx into rcx
mov rcx, [rbx]

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

Зачем мне (или моему компилятору) пользоваться этим режимом?

Затем что порой после очередной операции мы уже посчитали адрес и хотим им воспользоваться.

Разобрав вариант в displacement, мы можем найти хороший пример такого приема:

mov rax, qword ptr [rax]

Base + Index

Эта комбинация аналогична регистру base за тем исключением, что мы добавляем значение регистра index. Пример:

; store the qword in rcx into the memory address computed
; as the sum of the values in rax and rbx
mov [rax + rbx], rcx

Зачем мне (или моему компилятору) пользоваться этим режимом?

Найти подходящий пример для такого режима оказалось для меня непростой задачей, поэтому мои коллеги, конечно же, сразу же подобрали один:

int foo(char * buf, int index) {
  return buf[index];
}

Результат:

push    rbp
mov     rbp, rsp
mov     qword ptr [rbp - 8], rdi
mov     dword ptr [rbp - 12], esi
mov     rax, qword ptr [rbp - 8]  ; rax is buf
movsxd  rcx, dword ptr [rbp - 12] ; rcx is index
movsx   eax, byte ptr [rax + rcx] ; store buf[index] into eax
pop     rbp
ret

(Посмотреть на Godbolt.)

Оглядываясь назад, мы можем заметить очевидное: в случаях, когда ни стартовый адрес массива, ни сдвиг в массив не зафиксированы в compile-time, Base + Index идеально подходит для моделирования доступов к массиву.

Base + Displacement

Больше неопределенности! Если вы еще не догадались, подсчет актуального адреса и регистром base, и полем displacement соответствует двум следующим операциям:

  1. Мы загружаем значение из регистра base
  2. Мы добавляем загруженное значение к значению поля displacement

Затем мы берем полученную сумму за фактический адрес. Пример:

; add 0xcafe to the value stored in rax
; then, store the qword at the computed address into rbx
mov rbx, [rax + 0xcafe]

Зачем мне (или моему компилятору) пользоваться этим режимом?

Некоторые режимы адресации, как мы уже видели на примере Base + Index, естественным образом отображают семантику С-подобных массивов. Base + Displacement можно рассматривать в таком же ключе, но со стороны структурной семантики: регистр base содержит адрес к началу структуры, а поле displacement содержит фиксированный сдвиг в эту структуру. Пример:

struct foo {
    long a;
    long b;
};

long bar(struct foo *foobar) {
    return foobar->b;
}

Результат:

push    rbp
mov     rbp, rsp
mov     qword ptr [rbp - 8], rdi
mov     rax, qword ptr [rbp - 8] ; rax is foobar
mov     rax, qword ptr [rax + 8] ; rax + 8 is foobar->b; store back into rax
pop     rbp
ret

(Посмотреть на Godbolt.)

Если задуматься о конструкции и планировке стека в начале каждой функции как о самостоятельной структуре, пример выше становится очевиден: доступы вида [rbp - N] это по сути stack->objN.

Base + Index + Displacement

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

Как в примере выше, но с еще одним регистром, результат будет выглядеть следующим образом:

; add 0xcafe to the values stores in rax and rcx
; then, store the qword at the computer address into rbx
mov rbx, [rax + rcx + 0xcafe]

Зачем мне (или моему компилятору) пользоваться этим режимом?

Base + Index + Displacement естественным образом моделирует доступ к структуре внутри массива, точно так же как Base + Displacement естественным образом моделирует доступ к структуре, а Base + Index естественным образом моделирует доступ к массиву.

Не без труда, но с помощью -O1 мне удалось заставить clang скомпилировать пример в Godbolt:

struct foo {
    long a;
    long b;
};

long square(struct foo foos[], long i) {
    struct foo x = foos[i];
    return x.b;
}

Краткий результат:

shl     rsi, 4
mov     rax, qword ptr [rdi + rsi + 8] ; rdi is foos, rsi is i, 8 is the field offset
ret

(Посмотреть на Godbolt.)

Base + (Index * Scale)

Наше первое умножение!

Поле scale похоже на поле displacement тем, что они оба являются закодированным в нашу команду коэффициентом константы, однако scale, в отличие от displacement, сильно ограничен: так как его диапазон составляет всего два бита, значения у scale может быть всего четыре: 1, 2, 4 или 8.

Как можно догадаться из названия, поле scale используется для скалирования, т.е. умножения, другого поля на себя. Если говорить точнее, оно всегда скалирует регистр index, и не может без него использоваться.

Зачем мне (или моему компилятору) пользоваться этим режимом?

В отличие от массива структур из предыдущих примеров, Base + (Index * Scale), кроме всего прочего, естественным образом моделирует доступ к массиву указателей. Пример:

struct foo {
    long a;
    long b;
};

long bar(struct foo *foos[], long i) {
    struct foo *x = foos[i];
    return x->b;
}

Результат:

mov     rax, qword ptr [rdi + 8*rsi] ; rdi is foos, rsi is i, 8 is the scale (pointer-sized!)
mov     rax, qword ptr [rax + 8]
ret

(Посмотреть на Godbolt.)

(Index * Scale) + Displacement

Почти как на примере выше, эта комбинация без лишних сложностей меняет регистр base на поле displacement.

Зачем мне (или моему компилятору) пользоваться этим режимом?

(Index * Scale) + Displacement естественным образом моделирует особый случай доступа к массиву: когда массив можно статически (т.е. глобально) адресовать, а размер элементов можно вычислить через scale. Пример:

int tbl[10];

int foo(int i) {
    return tbl[i];
}

Результат:

movsxd  rax, edi
mov     eax, dword ptr [4*rax + tbl] ; rax is i, 4 is the scale (sizeof(int) == 4)
ret

(Посмотреть на Godbolt.)

Base + (Index * Scale) + Displacement

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

Зачем мне (или моему компилятору) пользоваться этим режимом?

Base + (Index * Scale) + Displacement естественным образом моделирует доступ к двумерному массиву. Пример:

long tbl[10][10];

long foo(long i, long j) {
    return tbl[i][j];
}

Результат:

lea     rax, [rdi + 4*rdi]
shl     rax, 4
mov     rax, qword ptr [rax + 8*rsi + tbl]
ret

(Посмотреть на Godbolt.)

RIP-относительная адресация

Выше мы описали режим адресации, который почти идентичен своему историческому эквиваленту в х86_32, и отличается в первую очередь использованием 64-битных регистров GPR, и порой 64-битными смещениями. Однако главным отличием является добавление абсолютно нового режима адресации под названием «RIP-относительная» (RIP-relative) адресация.

Почему этот режим называется RIP-относительным? Потому что он кодирует смещение относительно значения регистра RIP (в особенности RIP не текущей, а следующей команды). Обычно это выражается уже знакомым нам синтаксисом [Base + Displacement], вот только вместо GPR регистром base теперь является rip. Пример:

mov rax, [rip + 16]

Зачем мне (или моему компилятору) пользоваться этим режимом?

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

Пример компиляции с использованием -O1 и -fpic:

long tbl[10];

int foo(int i) {
    return tbl[i];
}

Для него в архитектуре х86_64 нам потребуются всего два mov:

foo:
        mov     rax, qword ptr [rip + tbl@GOTPCREL]
        mov     rax, qword ptr [rax + 8*rdi]
        ret

Однако в архитектуре х86_32 нам их потребуется три, плюс шаблоны:

foo:
        call    .L0$pb
.L0$pb:
        pop     eax
.Ltmp0:
        add     eax, offset _GLOBAL_OFFSET_TABLE_+(.Ltmp0-.L0$pb)
        mov     ecx, dword ptr [esp + 4]
        mov     eax, dword ptr [eax + tbl@GOT]
        mov     eax, dword ptr [eax + 4*ecx]
        ret

Напоследок: сегментация

Архитектура х86_64 убрала всю сегментацию, но только почти. Благодаря плоскому адресному пространству регистры сегментов более не требуются, но местами все еще проявляются:

  • Linux (точнее glibc) использует fs в пользовательском пространстве для доступа к настраиваемым ядром сегментам TLS. Спецификацию этих сегментов можно обнаружить в per-CPU конфигурации GDT (ссылка). Если предположить что ничего в glibc (или любой вашей libc) не использует gs, вы можете свободно им пользоваться.
  • В пространстве ядра Linux использует gs для хранения основного адреса региона per-CPU переменной. Мы можем наблюдать это в определении макроса PER_CPU_VAR (ссылка):
    #define PER_CPU_VAR(var)  %__percpu_seg:var
  • В х86_64 определение растет:
    %gs:var

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

Кстати, вот пример локально-поточной переменной:

int __thread x = 0;

int foo(void) {
    int *y = &x;
    return *y;
}

Результат:

push    rbp
mov     rbp, rsp
mov     rax, qword ptr fs:[0]    ; grab the base address of the thread-local storage area
lea     rax, [rax + x@TPOFF]     ; calculate the effective address of x within the TLS
mov     qword ptr [rbp - 8], rax ; store the address of x into y
mov     rax, qword ptr [rbp - 8]
mov     eax, dword ptr [rax]
pop     rbp
ret

(Прочесть на Godbolt.)

Автор: Дата-центр "Миран"

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js