Аллока реализация

Question

Как реализовать alloca () с использованием встроенного ассемблера x86 в таких языках, как D, C и C ++? Я хочу создать слегка измененную версию, но сначала мне нужно узнать, как реализована стандартная версия. Чтение разборки из компиляторов не помогает, потому что они выполняют так много оптимизаций, и я просто хочу каноническую форму.

Редактировать: Я предполагаю, что самое сложное в том, что я хочу, чтобы у этого был нормальный синтаксис вызова функции, то есть использование голой функции или чего-то подобного, чтобы она выглядела как обычная alloca ().

Редактировать # 2: Ах, черт возьми, вы можете предположить, что мы не опускаем указатель кадра.

Answer 1

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

sub esp, <size>

, что, к сожалению, только половина картины. Да, это "выделит место в стеке", но есть несколько ошибок.

1. , если компилятор выпустил код который ссылается на другие переменные относительно esp вместо ebp (типично, если вы компилируете без указатель кадра). Тогда те ссылки должны быть скорректированы. Даже с указателями фреймов компиляторы делают это иногда.

2. что более важно, по определению, пространство, выделенное с помощью alloca, должно быть "освобожден" при выходе из функции.

Самое важное - это точка № 2. Потому что вам нужен компилятор для генерации кода для симметричного добавления <size> к esp в каждой точке выхода функции.

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

EDIT:

Фактически, в glibc (реализация libc в GNU). Реализация alloca просто так:

#ifdef  __GNUC__
# define __alloca(size) __builtin_alloca (size)
#endif /* GCC.  */

EDIT:

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

EDIT:

Итак, я немного поэкспериментировал с такими вещами:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define __alloca(p, N) \
    do { \
        __asm__ __volatile__( \
        "sub %1, %%esp \n" \
        "mov %%esp, %0  \n" \
         : "=m"(p) \
         : "i"(N) \
         : "esp"); \
    } while(0)

int func() {
    char *p;
    __alloca(p, 100);
    memset(p, 0, 100);
    strcpy(p, "hello world\n");
    printf("%s\n", p);
}

int main() {
    func();
}

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

Вот результирующий ASM:

8048454: push   ebp
8048455: mov    ebp,esp
8048457: sub    esp,0x28
804845a: sub    esp,0x64                      ; <- this and the line below are our "alloc"
804845d: mov    DWORD PTR [ebp-0x4],esp
8048460: mov    eax,DWORD PTR [ebp-0x4]
8048463: mov    DWORD PTR [esp+0x8],0x64      ; <- whoops! compiler still referencing via esp
804846b: mov    DWORD PTR [esp+0x4],0x0       ; <- whoops! compiler still referencing via esp
8048473: mov    DWORD PTR [esp],eax           ; <- whoops! compiler still referencing via esp           
8048476: call   8048338 <memset@plt>
804847b: mov    eax,DWORD PTR [ebp-0x4]
804847e: mov    DWORD PTR [esp+0x8],0xd       ; <- whoops! compiler still referencing via esp
8048486: mov    DWORD PTR [esp+0x4],0x80485a8 ; <- whoops! compiler still referencing via esp
804848e: mov    DWORD PTR [esp],eax           ; <- whoops! compiler still referencing via esp
8048491: call   8048358 <memcpy@plt>
8048496: mov    eax,DWORD PTR [ebp-0x4]
8048499: mov    DWORD PTR [esp],eax           ; <- whoops! compiler still referencing via esp
804849c: call   8048368 <puts@plt>
80484a1: leave
80484a2: ret

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

Answer 2

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

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

Answer 3

Стандарты C и C ++ не указывают, что alloca() должен использовать стек, потому что alloca() не соответствует стандартам C или C ++ (или POSIX в этом отношении) & sup1;.

Компилятор может также реализовать alloca(), используя кучу. Например, компилятор ARM RealView (RVCT) alloca() использует malloc() для выделения буфера (, на который ссылается их сайт ), а также заставляет компилятор выдавать код, который освобождает буфер, когда функция возвращается. Это не требует игры с указателем стека, но все же требует поддержки компилятора.

Microsoft Visual C ++ имеет функцию _malloca(), которая использует кучу, если в стеке недостаточно места, но требует, чтобы вызывающая сторона использовала _freea(), в отличие от _alloca(), что не нуждается / не хочет явного освобождения.

(Имея в своем распоряжении деструкторы C ++, вы можете выполнять очистку без поддержки компилятора, но вы не можете объявлять локальные переменные внутри произвольного выражения, поэтому я не думаю, что вы могли бы написать макрос alloca(), который использует RAII Опять же, очевидно, вы не можете использовать alloca() в некоторых выражениях (например, параметры функции ) в любом случае.)

& ПОД1; Да, законно написать alloca(), который просто вызывает system("/usr/games/nethack").

Answer 4

Для языка программирования D исходный код для alloca () поставляется с download . Как это работает, довольно хорошо прокомментировано. Для dmd1 это находится в /dmd/src/phobos/internal/alloca.d. Для dmd2 это находится в /dmd/src/druntime/src/compiler/dmd/alloca.d.

Answer 5

Продолжение Стиль прохождения Аллока

Массив переменной длины в чистый ISO C ++ . Реализация концепции.

Использование

void foo(unsigned n)
{
    cps_alloca<Payload>(n,[](Payload *first,Payload *last)
    {
        fill(first,last,something);
    });
}

Основная идея

template<typename T,unsigned N,typename F>
auto cps_alloca_static(F &&f) -> decltype(f(nullptr,nullptr))
{
    T data[N];
    return f(&data[0],&data[0]+N);
}

template<typename T,typename F>
auto cps_alloca_dynamic(unsigned n,F &&f) -> decltype(f(nullptr,nullptr))
{
    vector<T> data(n);
    return f(&data[0],&data[0]+n);
}

template<typename T,typename F>
auto cps_alloca(unsigned n,F &&f) -> decltype(f(nullptr,nullptr))
{
    switch(n)
    {
        case 1: return cps_alloca_static<T,1>(f);
        case 2: return cps_alloca_static<T,2>(f);
        case 3: return cps_alloca_static<T,3>(f);
        case 4: return cps_alloca_static<T,4>(f);
        case 0: return f(nullptr,nullptr);
        default: return cps_alloca_dynamic<T>(n,f);
    }; // mpl::for_each / array / index pack / recursive bsearch / etc variacion
}

LIVE DEMO

cps_alloca на github

Answer 6

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

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

sub esp, XXX

Принимая во внимание, что XXX - количество байтов для покрытия

Edit:
Если вы хотите взглянуть на реализацию (и вы используете MSVC), посмотрите alloca16.asm и chkstk.asm.
Код в первом файле в основном выравнивает желаемый размер выделения с 16-байтовой границей. Код во втором файле фактически обходит все страницы, которые принадлежат новой области стека, и касается их. Это может вызвать исключения PAGE_GAURD, которые используются ОС для увеличения стека.

Answer 7

Если вы не можете использовать массивы переменной длины c99, вы можете использовать составное литеральное приведение к пустому указателю.

#define ALLOCA(sz) ((void*)((char[sz]){0}))

Это также работает для -ansi (как расширение gcc) и даже когда это аргумент функции;

some_func(&useful_return, ALLOCA(sizeof(struct useless_return)));

Недостатком является то, что при компиляции как c ++ g ++> 4.6 выдаст ошибку : при получении адреса временного массива ... clang и icc не жалуются, хотя

Answer 8

Вы можете просмотреть исходные коды компилятора C с открытым исходным кодом, например Open Watcom , и найти его самостоятельно

Answer 9

То, что мы хотим сделать, это что-то вроде этого:

void* alloca(size_t size) {
    <sp> -= size;
    return <sp>;
}

В сборке (Visual Studio 2017, 64bit) это выглядит так:

;alloca.asm

_TEXT SEGMENT
    PUBLIC alloca
    alloca PROC
        sub rsp, rcx ;<sp> -= size
        mov rax, rsp ;return <sp>;
        ret
    alloca ENDP
_TEXT ENDS

END

К сожалению, наш указатель возврата - последний элемент в стеке, и мы не хотим его перезаписывать. Дополнительно нам нужно позаботиться о выравнивании, т.е. раунд размер до кратного 8. Итак, мы должны сделать это:

;alloca.asm

_TEXT SEGMENT
    PUBLIC alloca
    alloca PROC
        ;round up to multiple of 8
        mov rax, rcx
        mov rbx, 8
        xor rdx, rdx
        div rbx
        sub rbx, rdx
        mov rax, rbx
        mov rbx, 8
        xor rdx, rdx
        div rbx
        add rcx, rdx

        ;increase stack pointer
        pop rbx
        sub rsp, rcx
        mov rax, rsp
        push rbx
        ret
    alloca ENDP
_TEXT ENDS

END

Answer 10

Рекомендую инструкцию "вводить". Доступно на 286 и более новых процессорах ( может было доступно и на 186, я не помню, на первый взгляд, но они не были широко доступны в любом случае).