задачки про стек (программистское)

[avva]

(эта запись будет интересна программистам, знающим C, и сочувствующим)

Две задачки - первая старая и известная, вторую только что придумал.

1. Напишите код на C, который определяет, в какую сторону растет стек на машине, где его запустили - вверх или вниз.

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

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

Комментарии скрывать не буду. Очень рекомендую подумать самому перед тем, как смотреть на решения там.

Comments

[psilogic.livejournal.com]

1. Объявить авто-переменную, узнать адрес, вызвать функцию, в ней объявить еще одну авто-переменную, узнать адрес, сравнить адреса.

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

[avva.livejournal.com]

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

[pargentum.livejournal.com]

Первая задача достаточно проста.

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

[avva.livejournal.com]

Да, это верно. Давайте предположим, что все аргументы передаются через стек. Update: думаю, что на практике это можно навязать с помощью volatile.

[brewbuilder.livejournal.com]

Вторая вообще не загадка, поскольку может быть
только один вариант (догадайтесь почему)

[brewbuilder.livejournal.com]

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

[avva.livejournal.com]

http://www.google.com/search?hl=en&q=stdcall

[avva.livejournal.com]

да, а "очищает" я имел в виду от аргументов, а не локальных переменных - добавил это в условие, чтобы не было неясности.

[kcmamu.livejournal.com]

А разве невозможны архитектура и компилятор, обходящиеся вообще без стека?

[avva.livejournal.com]

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

[cmm.livejournal.com]

1. ну понятно
2. единственное что приходит в голову — это проверить работает ли хвостовая рекурсия для функций с постоянным количеством аргументов.  если работает, значит функции чистят за собой сами; если нет, то либо копилятор не фонтан, либо чистит зовущий. :)

[mgar.livejournal.com]

1 - элементарно,

2 - делаем следующим образом. Первым делом пишем две функции - первая возвращает current stack (адрес локальной переменной), вторая - dummy function без параметров.

Теперь делаем так - запоминаем current stack, затем вызываем dummy, которую кастингом приводим к функции с одним параметром. Затем снова вызываем current stack. Если оба раза стэк одинаков = мы его и чистим. Если стэк вырос - мы положились на вызываемую функцию.

Теперь осталось только подчистить за собой стек во втором случае.

(Метод не чистый, потому что посередине у нас есть участок кода, где стек не валидный, и теопретически это может нас грохнуть, но по идее там ничего нам из стека не надо...)

PS. А по идее, обе функции - current stack и dummy - могут быть одной и той же.

[avva.livejournal.com]

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

То решение, которое я сам придумал, выглядит почти идентично вашему (и его тоже можно критиковать, конечно):

1. пишем две функции, к-е ничего не делают, void onearg(int dummy) и void zeroarg(void).

2. в основной функции объявлем локальный массив int indicator[3] и обнуляем.

3. приводим zeroarg к типу onearg и вызываем; если стек чистит функция, то наш стек сейчас испорчен на один int.

4. пишем indicator[1] = 1. Если наш стек испорчен, это на самом деле записывается в indicator[0] или indicator[2] (в зависимости от того, куда растет стек :) ).

5. приводм onearg к типу zeroarg и вызываем; если стек был испорчен, это его чистит.

6. проверяем, где у нас в массиве indicator записалась единичка.

[pargentum.livejournal.com]

http://avva.livejournal.com/2137625.html?thread=64932121#t64932121 (механизм передачи переменного числа аргументов в стеке при чистке стека вызываемой функцией).

[(Anonymous)]

2. При вызове сишной функции (то есть такой, которая объявлена без pascal, inline, fastcall и т. д.) стек всегда очищает вызывающий. Иначе бы вот такой (законный) код

int f(...) { return 0; }

int main() { f(1); f(1, 2); f(1, 2, 3); return 0; }

нельзя было бы корректно откомпилировать.

[avva.livejournal.com]

pascal, fastcall, stdcall - все они не делают C-шную функцию не-C-шной. Они просто меняют соглашение вызова. Это соглашение не является частью стандарта языка. Насчет переменного числа аргументов см. объяснение выше.

[jney.livejournal.com]

#2

int global_var;
void *p_i;

main () {
int i;
p_i = &i;
f ();
}

f () {
return global_var/0;
}

перед returnom обычный компилятор уже откатит стек. Дальше реализовать exception handler, и из него сравнить адрес своей локальной переменной и p_i.

[pargentum.livejournal.com]

Целая куча нетривиальных предположений
1. Что деление произойдет после отката стека (например у gcc 4.1.2 это не так, только что попробовал).
2. Что ваша операционная система/платформа позволяет вешать обработчики на деление на 0.
3. Что эти обработчики зовутся на том же стеке.

[a_p]

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

[avva.livejournal.com]

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

[dimrub.livejournal.com]

1.

int foo()
{
int a;
return (int)(&a);
}

// 1 - down, 0 - up
int determine_stack_direction()
{
int a;
return ( (int)(&a) - foo() > 0 );
}

[(Anonymous)]

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

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

если считать, что все у нас традиционно, написать такой код легко, в комментах уже все подробно изучено. интересно, можно ли написать standards-compliant код, который бы это делал (хотя бы одну из задач). я почти уверен, что нет, но вдруг?

[psilogic.livejournal.com]

#include <stdio.h>
#include <setjmp.h>

typedef void (__cdecl * cdecl_function_with_param_t)(int param);
typedef void (__stdcall * stdcall_function_with_param_t)(int param);

void __cdecl cdecl_function(int param)
{
	printf("In cdecl_function: %d\n", param);
	return;
}

void __stdcall stdcall_function(int param)
{
	printf("In stdcall_function: %d\n", param);
	return;
}


static jmp_buf jbuf;
static int was_cleared;
static int *stack_approximation;
#define MAGIC_NUMBER 0x1234ABDC

static int *get_stack_pointer_approximation()
{
	int var= 1;
	return &var;
}

static void call_and_jump(void *func_address, int param)
{
	//save stack pointer
	stack_approximation= get_stack_pointer_approximation();
	//try call function as stdcall: do not clear stack after
	((stdcall_function_with_param_t)func_address)(param);
	//was stack cleared or not?
	was_cleared= stack_approximation == get_stack_pointer_approximation();
	//correct stack clean up
	longjmp(jbuf, 1);
}

static void check_function(void *func_address, char *func_name, int param)
{
	printf("Function '%s':\n", func_name);
	
	//save stack
	if (0 == setjmp(jbuf))
		call_and_jump(func_address, param);
	else
	{
		if (was_cleared)
			printf("This was stdcall function\n");
		else
			printf("This was cdecl function\n");
	}
	
}

int main()
{
	printf("Test function call scheme:\n");
	check_function(cdecl_function, "cdecl_function", 1);
	check_function(stdcall_function, "stdcall_function", 2);

	//wait Enter
	getchar();
}

Листинг:

Test function call scheme:
Function 'cdecl_function':
In cdecl_function: 1
This was cdecl function
Function 'stdcall_function':
In stdcall_function: 2
This was stdcall function

[psilogic.livejournal.com]

Еще можно в get_stack_pointer_approximation использовать для var тип не int, а массив int var[1000] и что-нибудь с ним поделать, чтобы гарантировать, что для хранения var не будет использован регистр.

[spamsink.livejournal.com]

2. Two words: frame pointer.

[ygam.livejournal.com]

А что в этом сложного?

#include <stdio.h>

int *p1;
int *p2;

void f2()
{
int i;
p2 = &i;
}

void f1()
{
int j;
p1 = &j;
f2();
}

int main()
{
f1();
printf ("Stack grows %s", p1<p2 ? "up" : "down"); } На второй вопрос отвечу отдельным комментарием.

[avva.livejournal.com]

А кто говорил, что сложно?

[prosto-tak.livejournal.com]

А теперь задача повышенной трудности - то же самое на Jave...

[http://users.livejournal.com/_iga/]

1. В наборе команд JVM отсутствуют инструкции для получения содержимого указателя стека, все операции со стеком ведутся абстрактно - push/pop.

Because the Java virtual machine stack is never manipulated directly except to push and pop frames, frames may be heap allocated. The memory for a Java virtual machine stack does not need to be contiguous.

Поэтому вопрос бессмысленный.

2. При вызове метода создаётся новый фрейм, где лежат аргументы и локальные переменные. Текущий фрейм уничтожается инструкцией return (http://java.sun.com/docs/books/jvms/second_edition/html/Instructions2.doc12.html). Так что можно считать, что стек очищает вызываемая функция, хотя она это делает неявно.

[sobaker.livejournal.com]

Если успеете увидеть коммент до того момента, как автор откроет ответы - возможно, Вам будет интересна маленькая задачка - http://t-gra.livejournal.com/203649.html

[avva.livejournal.com]

Спасибо. Милая, но довольно простенькая, кажется.

[kapla55.livejournal.com]

К сожалению только сегодня увидел ваши задачки. С первой задачей все ясно, а вот по второй все соображения откровенно удручают. В том числе автора блога.

1. В стандарте С ничего про передачу параметров на стеке нет, и по этому естественно что только используя implementation independent features решить задачу невозможно.

2. Все решали задачу в предположении что речь идет об архитектуре X86. (В PowerPC, к примеру имеется много регистров и от 8 до 16 первых параметров передаюстя в регистрах). Однако предполагать X86 для данной задачи весьма странно, поскольку если мы знаем что речь идет о X86, то мы сразу же стнаем все calling conventions которые предопределены в X86 ABI - стандарт, который в том числе определяет как передаюстя параметры в регистрах и на стеке и кто отвечает за выделение и освобождение стека.

3. Далее - поедположим вам как-то удалось довести компилятор до состояния когда он начал передавать параметры на стеке. (Хотя это не тривиально - volatile не поможет, а varargs функции все равно в соответствии с ABI первые N параметров передают на стеке. N зависит от архитектуры).
А кто вам вообще сказал, что память на стеке под параметры будет выделяться непосредственно перед вызовом функции и освобождаться сразу по возвращении?
Гораздо логичнее предположить (и в большинстве случаев именно так и происходит) что функция в прологе выделит одним большим куском достаточно памяти под все свои автоматические переменные и под параметры передаваемые на стеке так чтобы места было достаточно для самого "большого" вызова. И соответсвенно освобождаться все это пространство на стеке буде не сразу после вызова подфункции, а в конце - в эпилоге.

Короче, на мой взгляд, задача неудачная. Показывающая что автор не понимает как устроены современные ABI не только на PowerPC, но и на X86.

Вот небольшой пример для x86:
1 int
2 foo (void)
3 {
4 bar1 (1, 2, 3);
5 bar2 (1, 2, 3, 4);
6 }
И соответсвующий ассемблерный код сгенерированный gcc:

gcc -S -O2 x.c && vim -R x.s
foo:
pushl %ebp
movl %esp, %ebp
subl $24, %esp
movl $3, 8(%esp)
movl $2, 4(%esp)
movl $1, (%esp)
call bar1
movl $4, 12(%esp)
movl $3, 8(%esp)
movl $2, 4(%esp)
movl $1, (%esp)
call bar2
leave
ret