Реализация вложенных функций - PullRequest
Новая
       6

Реализация вложенных функций

26 голосов
/ 18 ноября 2011

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

Хотя, конечно, нетрудно реализовать прямые вызовы вложенных функций путем передачи указателя контекста в качестве скрытого аргумента, gcc также позволяетвзять указатель на вложенную функцию и передать этот указатель произвольной другой функции, которая в свою очередь может вызвать вложенную функцию контекста.Поскольку функция, которая вызывает вложенную функцию, имеет только тип вложенной функции для вызова, она, очевидно, не может передавать указатель контекста.

Я знаю, что другие языки, такие как Haskell, имеют более сложное соглашение о вызовахразрешить частичное приложение для поддержки таких вещей, но я не вижу способа сделать это на C. Как это можно реализовать?

Вот небольшой пример случая, который иллюстрирует проблему: 

int foo(int x,int(*f)(int,int(*)(void))) {
  int counter = 0;
  int g(void) { return counter++; }

  return f(x,g);
}

Эта функция вызывает функцию, которая вызывает функцию, которая возвращает счетчик из контекста и одновременно увеличивает его.

1 Ответ

23 голосов
/ 18 ноября 2011

GCC использует то, что называется батут.

Информация: http://gcc.gnu.org/onlinedocs/gccint/Trampolines.html

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

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

Разрез батута:

Вот пример вложенной функции в расширенном C GCC: 

void func(int (*param)(int));

void outer(int x)
{
    int nested(int y)
    {
        // If x is not used somewhere in here,
        // then the function will be "lifted" into
        // a normal, non-nested function.
        return x + y;
    }
    func(nested);
}

Это очень просто, поэтому мы можем увидеть, как это работает. Вот итоговая сборка outer, за вычетом некоторых вещей: 

subq    $40, %rsp
movl    $nested.1594, %edx
movl    %edi, (%rsp)
leaq    4(%rsp), %rdi
movw    $-17599, 4(%rsp)
movq    %rsp, 8(%rdi)
movl    %edx, 2(%rdi)
movw    $-17847, 6(%rdi)
movw    $-183, 16(%rdi)
movb    $-29, 18(%rdi)
call    func
addq    $40, %rsp
ret

Вы заметите, что большая часть того, что он делает, записывает регистры и константы в стек. Мы можем проследить и обнаружить, что в SP + 4 он размещает 19-байтовый объект со следующими данными (в синтаксисе GAS): 

.word -17599
.int $nested.1594
.word -17847
.quad %rsp
.word -183
.byte -29

Это достаточно просто запустить через дизассемблер. Предположим, что $nested.1594 равно 0x01234567 и %rsp равно 0x0123456789abcdef. Результирующая разборка, предоставленная objdump, составляет: 

   0:   41 bb 67 45 23 01       mov    $0x1234567,%r11d
   6:   49 ba ef cd ab 89 67    mov    $0x123456789abcdef,%r10
   d:   45 23 01 
  10:   49 ff e3                rex.WB jmpq   *%r11

Итак, батут загружает указатель стека внешней функции в %r10 и переходит к телу вложенной функции. Тело вложенной функции выглядит так: 

movl    (%r10), %eax
addl    %edi, %eax
ret

Как видите, вложенная функция использует %r10 для доступа к переменным внешней функции.

Конечно, довольно глупо, что батут на больше , чем сама вложенная функция. Вы могли бы легко сделать лучше. Но не очень многие люди используют эту функцию, и таким образом батут может оставаться одного размера (19 байт) независимо от размера вложенной функции.

Заключительное примечание. В нижней части сборки имеется окончательная директива: 

.section        .note.GNU-stack,"x",@progbits

Указывает компоновщику пометить стек как исполняемый.

...