Подтвердить что ты не робот

Внедрение Alloca

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

sub esp, <size>

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

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

  • что более важно, по определению, пространство, выделенное alloca, должно быть "освобождается", когда функция завершается.

Большая - точка № 2. Поскольку вам нужен компилятор для испускания кода, чтобы симметрично добавить <size> в esp в каждую точку выхода функции.

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

EDIT:

Фактически, в glibc (реализация GNU libc). Реализация 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 <[email protected]>
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 <[email protected]>
8048496: mov    eax,DWORD PTR [ebp-0x4]
8048499: mov    DWORD PTR [esp],eax           ; <- whoops! compiler still referencing via esp
804849c: call   8048368 <[email protected]>
80484a1: leave
80484a2: ret

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

Ответ 2

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

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

Ответ 3

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

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

sub esp, XXX

В то время как XXX - это количество байтов для allcoate

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

Ответ 4

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

Ответ 5

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

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

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

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

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

Ответ 6

Продолжение стиля прохождения Alloca

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

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

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

Ответ 7

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

Ответ 8

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

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

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

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

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

Ответ 9

Alloca легко, вы просто перемещаете указатель стека вверх; затем сгенерировать все чтение/запись, чтобы указать на этот новый блок

sub esp, 4

Ответ 10

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

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

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

;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

Ответ 11

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