Почему ошибки stackoverflow хаотичны?

Question

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

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

void recursive(unsigned int rec); 

int main(void) 
{ 
    recursive(1); 
    return 0; 
} 

void recursive(unsigned int rec) { 
    printf("%u\n", rec); 
    recursive(rec + 1); 
} 

Что может быть причины этого хаотического поведения?

Я использую fedora (16GiB ram, размер стека 8192) и скомпилирован с использованием cc без каких-либо опций.

EDIT

• Я знаю, что эта программа будет бросать StackOverflow
• Я знаю, что позволяет некоторые оптимизации компилятора изменит свое поведение и что программа достигнет целочисленного переполнения.
• Я знаю, что это неопределенное поведение, цель этого вопроса состоит в том, чтобы понять/получить обзор конкретных внутренних правил поведения, которые могут объяснить то, что мы там наблюдаем.

Вопрос более, учитывая, что на Linux нить размер стека фиксирован и определяется ulimit -s, что будет влиять на доступный размер стека, так что StackOverflow не всегда происходит на той же глубине вызова?

EDIT 2 @BlueMoon всегда видит один и тот же выход на его CentOS, в то время как на моем Fedora, со стеком 8M, я вижу различные выходы (последний напечатанный целочисленные 261892 или 261845, или 261826, или ...)

Answer 1

Изменение Printf вызов:

printf("%u %p\n", rec, &rec); 

Это заставляет GCC поставить запись в стек и дает вам свой адрес, который является хорошим показателем того, что происходит с указателем стека.

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

261958 0x7fff82d2878c 
261778 0x7fffc85f379c 
261816 0x7fff4139c78c 
261926 0x7fff192bb79c 

Прежде всего следует отметить, что адрес стека всегда заканчивается 78c или 79c. Почему это? Мы должны сбой при пересечении границы страницы, длина страниц составляет 0x1000 байт, и каждая функция ест 0x20 байт стека, поэтому адрес должен заканчиваться 00X или 01X. Но, глядя на это ближе, мы сбой в libc. Таким образом, переполнение стека происходит где-то внутри libc, из этого можно заключить, что вызов printf и всего остального, который он вызывает, требует, по крайней мере, 0x78c = 1932 (возможно, плюс X * 4096) байт стека для работы.

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

1 0x7fff8c4c13ac 
1 0x7fff0a88f33c 
1 0x7fff8d02fc2c 
1 0x7fffbc74fd9c 

Позиция стека в памяти рандомизирована. Это делается для предотвращения эксплойтов с полным переполнением буфера. Но так как выделения памяти, особенно на этом уровне, могут выполняться только в нескольких страницах (4096 байт), все начальные указатели стека будут выровнены в 0x1000. Это уменьшило бы количество случайных бит в рандомизированном адресе стека, поэтому добавляется дополнительная случайность, просто теряя случайное количество байтов в верхней части стека.

В операционной системе может учитываться только объем используемой памяти, включая ограничение на стек, на целых страницах. Поэтому, даже если стек начинается с случайного адреса, последний доступный адрес в стеке всегда будет адресом, заканчивающимся на 0xfff.

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

Answer 2

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

Answer 3

Ваша программа работает бесконечно, так как в вашей рекурсивной функции нет базового условия. Стек будет непрерывно расти по каждому вызову функции и приведет к переполнению стека.
Если бы это было tail-recursion оптимизация (с опцией -O2), то переполнение стека произойдет точно. Он вызывает неопределенное поведение.

Что повлияет на доступный размер стека, чтобы поток stackoverflow не всегда происходил при одной и той же глубине вызова?

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

Answer 4

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

Answer 5

Приведенный выше код может вызвать два вопроса:

• переполнения стека.
• Целое переполнение.

Stack Overflow: Когда рекурсивная функция вызывается, все его переменной надевается на call stack включая его return адрес. Поскольку нет базового условия, которое завершит рекурсию , а память стека будет ограничена, стек будет исчерпан в результате Исключение стека. Стек вызовов может состоять из ограниченного количества адресного пространства, часто определяемого в начале программы. Размер стеки вызовов зависит от многих факторов, в том числе на языке программирования , архитектуры машины, Многопоточностью и количество доступной памяти . Когда программа пытается использовать больше места, чем доступно в стеке вызовов (то есть, когда он пытается получить доступ к памяти за пределами границ стека вызовов, что по сути является переполнением буфера), стек считается переполнением, что обычно приводит к крах программы.

Обратите внимание: каждый раз, когда функция выходит/возвращает, все переменные, помещенные в стек этой функцией, освобождаются (то есть удаляются). После освобождения переменной стека эта область памяти становится доступной для других переменных стека. Но для рекурсивной функции обратный адрес все еще находится в стеке, пока рекурсия не завершится. Кроме того, автоматические локальные переменные выделяются как один блок, а указатель стека продвигается достаточно далеко, чтобы учесть сумму их размеров. Вас может заинтересовать Recursive Stack in C.

Целочисленное переполнение: Как каждый рекурсивный вызов recursive() шагом rec по 1, есть шанс, что Целочисленное переполнение может произойти. Для этого у вас должна быть огромная память стека, поскольку диапазон целых чисел без знака: от 0 до 4 294 967 295. См. Ссылку here.

Answer 6

Ваш рекурсивный вызов не обязательно будет приводить к неопределенному поведению из-за stackoverflow (но из-за переполнения целых чисел) на практике. Оптимизирующий компилятор может просто превратить ваш компилятор в бесконечный «петля» с командой перехода:

void recursive(int rec) { 
    loop: 
    printf("%i\n", rec); 
    rec++; 
    goto loop; 
} 

Заметим, что это будет вызывать неопределенное поведение, так как это происходит переполнение rec (подпись переполнения ИНТ UB) , Например, если rec имеет неподписанный int, например, тогда код действителен и теоретически должен работать вечно.

Answer 7

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

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

Однако по соображениям безопасности стек не всегда находится в одном месте. Address Space Layout Randomisation гарантирует, что база расположения стека варьируется между вызовами программы. Это означает, что программа может выполнять больше (или меньше) рекурсий до того, как вершина стека попадет в нечто недоступное, как программный код.

Это мое предположение о том, что происходит, во всяком случае.