Какие ошибки могут возникнуть при использовании стека

Стек (или магазин) — структура данных в программировании, работающая по принципу магазина с патронами: последний помещеннный в него объект, обрабатывается первым.

Приработе со стекам часто приходится сталкиваться с двумя типичными ошибками: переполненем стека и опустошением стека.

Переполнение стека (stack overflow) — одна из типичных ошибок при работе со стеком, состоящая в попытке добавить в стек элемент, когда память, отведенная для хранения стека полностью занята.

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

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

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

Опустошение стека (stack underflow) — другая типичная ошибка при работе со стеком, состоящая в попытке извлечь значение пустого стека.

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

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

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

Чтобы избегать ошибок при работе со стеком нужно следовать двум правилам.

1. При реализации операций со стеком всегда проверять, не приведет ли затребованное действие к переполнению или опустошению стека. Если нарушение обнаружено, то выдавать соответствующую диагностику и отказывать в выполнении операции.

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

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

Дополнительно в базе данных Генона: 

• Что такое стек в программировании?
• Для чего используются указатели в программировании?

Ссылки по теме:

• cyberforum.ru — реализация стека на С++ с использованием исключений 
• ru.wikipedia.org — Википедия: Переполнение буфера
• codenet.ru — рассматривается уязвимость Windows за счет использования переполнения стека  
• sdteam.com — статья «Переполнения стека»
• xakep.ru — статья «Переполнение буфера в стеке», Хакер, №2, 2003

To describe this, first let us understand how local variables and objects are stored.

Local variable are stored on the stack:

If you looked at the image you should be able to understand how things are working.

When a function call is invoked by a Java application, a stack frame is allocated on the call stack. The stack frame contains the parameters of the invoked method, its local parameters, and the return address of the method. The return address denotes the execution point from which, the program execution shall continue after the invoked method returns. If there is no space for a new stack frame then, the StackOverflowError is thrown by the Java Virtual Machine (JVM).

The most common case that can possibly exhaust a Java application’s stack is recursion. In recursion, a method invokes itself during its execution. Recursion is considered as a powerful general-purpose programming technique, but it must be used with caution, to avoid StackOverflowError.

An example of throwing a StackOverflowError is shown below:

StackOverflowErrorExample.java:

public class StackOverflowErrorExample {

    public static void recursivePrint(int num) {
        System.out.println("Number: " + num);
        if (num == 0)
            return;
        else
            recursivePrint(++num);
        }

    public static void main(String[] args) {
        StackOverflowErrorExample.recursivePrint(1);
    }
}

In this example, we define a recursive method, called recursivePrint that prints an integer and then, calls itself, with the next successive integer as an argument. The recursion ends until we pass in 0 as a parameter. However, in our example, we passed in the parameter from 1 and its increasing followers, consequently, the recursion will never terminate.

A sample execution, using the -Xss1M flag that specifies the size of the thread stack to equal to 1 MB, is shown below:

Number: 1
Number: 2
Number: 3
...
Number: 6262
Number: 6263
Number: 6264
Number: 6265
Number: 6266
Exception in thread "main" java.lang.StackOverflowError
        at java.io.PrintStream.write(PrintStream.java:480)
        at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
        at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
        at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
        at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
        at java.io.PrintStream.write(PrintStream.java:527)
        at java.io.PrintStream.print(PrintStream.java:669)
        at java.io.PrintStream.println(PrintStream.java:806)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:4)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        ...

Depending on the JVM’s initial configuration, the results may differ, but eventually the StackOverflowError shall be thrown. This example is a very good example of how recursion can cause problems, if not implemented with caution.

How to deal with the StackOverflowError

1. The simplest solution is to carefully inspect the stack trace and
   detect the repeating pattern of line numbers. These line numbers
   indicate the code being recursively called. Once you detect these
   lines, you must carefully inspect your code and understand why the
   recursion never terminates.

2. If you have verified that the recursion
   is implemented correctly, you can increase the stack’s size, in
   order to allow a larger number of invocations. Depending on the Java
   Virtual Machine (JVM) installed, the default thread stack size may
   equal to either 512 KB, or 1 MB. You can increase the thread stack
   size using the -Xss flag. This flag can be specified either via the
   project’s configuration, or via the command line. The format of the
   -Xss argument is:
   -Xss<size>[g|G|m|M|k|K]

To describe this, first let us understand how local variables and objects are stored.

Local variable are stored on the stack:

If you looked at the image you should be able to understand how things are working.

When a function call is invoked by a Java application, a stack frame is allocated on the call stack. The stack frame contains the parameters of the invoked method, its local parameters, and the return address of the method. The return address denotes the execution point from which, the program execution shall continue after the invoked method returns. If there is no space for a new stack frame then, the StackOverflowError is thrown by the Java Virtual Machine (JVM).

The most common case that can possibly exhaust a Java application’s stack is recursion. In recursion, a method invokes itself during its execution. Recursion is considered as a powerful general-purpose programming technique, but it must be used with caution, to avoid StackOverflowError.

An example of throwing a StackOverflowError is shown below:

StackOverflowErrorExample.java:

public class StackOverflowErrorExample {

    public static void recursivePrint(int num) {
        System.out.println("Number: " + num);
        if (num == 0)
            return;
        else
            recursivePrint(++num);
        }

    public static void main(String[] args) {
        StackOverflowErrorExample.recursivePrint(1);
    }
}

In this example, we define a recursive method, called recursivePrint that prints an integer and then, calls itself, with the next successive integer as an argument. The recursion ends until we pass in 0 as a parameter. However, in our example, we passed in the parameter from 1 and its increasing followers, consequently, the recursion will never terminate.

A sample execution, using the -Xss1M flag that specifies the size of the thread stack to equal to 1 MB, is shown below:

Number: 1
Number: 2
Number: 3
...
Number: 6262
Number: 6263
Number: 6264
Number: 6265
Number: 6266
Exception in thread "main" java.lang.StackOverflowError
        at java.io.PrintStream.write(PrintStream.java:480)
        at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
        at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
        at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
        at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
        at java.io.PrintStream.write(PrintStream.java:527)
        at java.io.PrintStream.print(PrintStream.java:669)
        at java.io.PrintStream.println(PrintStream.java:806)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:4)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        ...

Depending on the JVM’s initial configuration, the results may differ, but eventually the StackOverflowError shall be thrown. This example is a very good example of how recursion can cause problems, if not implemented with caution.

How to deal with the StackOverflowError

1. The simplest solution is to carefully inspect the stack trace and
   detect the repeating pattern of line numbers. These line numbers
   indicate the code being recursively called. Once you detect these
   lines, you must carefully inspect your code and understand why the
   recursion never terminates.

2. If you have verified that the recursion
   is implemented correctly, you can increase the stack’s size, in
   order to allow a larger number of invocations. Depending on the Java
   Virtual Machine (JVM) installed, the default thread stack size may
   equal to either 512 KB, or 1 MB. You can increase the thread stack
   size using the -Xss flag. This flag can be specified either via the
   project’s configuration, or via the command line. The format of the
   -Xss argument is:
   -Xss<size>[g|G|m|M|k|K]

Переполнение стека

• Определение
• Стек программы
• Последствия ошибки
• Причины ошибки
• Примеры
• Итог
• Библиографический список

Определение

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

Стек программы

Стек программы — это специальная области памяти, организованная по принципу очереди LIFO (Last in, first out — последним пришел, первым ушел). Название «стек» произошло из-за аналогии принципа его построения со стопкой (англ. stack) тарелок — можно класть тарелки друг на друга (метод добавления в стек, «заталкивание», «push»), а затем забирать их, начиная с верхней (метод получения значения из стека, «выталкивание», «pop»). Стек программы также называют стек вызовов, стек выполнения, машинным стеком (чтобы не путать его со «стеком» — абстрактной структурой данных).

Для чего нужен стек? Он позволяет удобно организовать вызов подпрограмм. При вызове функция получает некоторые аргументы; также она должна где-то хранить свои локальные переменные. Кроме того, надо учесть, что одна функция может вызвать другую функцию, которой тоже надо передавать параметры и хранить свои переменные. Используя стек, при передаче параметров нужно просто положить их в стек, тогда вызываемая функция сможет их оттуда «вытолкнуть» и использовать. Локальные переменные тоже можно хранить там же — в начале своего кода функция выделяет часть памяти стека, при возврате управления — очищает и освобождает. Программисты на высокоуровневых языках обычно не задумываются о таких вещах — весь необходимый рутинный код за них генерирует компилятор.

Последствия ошибки

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

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

Чтобы быть совсем точным, следует отметить, что подобное описание событий верно лишь для компиляторов, компилирующих в «родной» (native) код. В управляемых языках у виртуальной машины есть свой стек для управляемых программ, за состоянием которого гораздо проще следить, и можно даже позволить себе при возникновении переполнения передать программе исключение. В языках Си и Си++ на подобную «роскошь» рассчитывать не приходится.

Причины ошибки

Что же может привести к такой неприятной ситуации? Исходя из описанного выше механизма, один из вариантов — слишком большое число вложенных вызовов функций. Особенно вероятен такой вариант развития событий при использовании рекурсии. Бесконечная рекурсия (при отсутствии механизма «ленивых» вычислений) прерывается именно таким образом, в отличие от бесконечного цикла, который иногда имеет полезное применение. Впрочем, при небольшом объеме памяти, отведенной под стек (что, например, характерно для микроконтроллеров), достаточно может быть и простой последовательности вызовов.

Другой вариант — локальные переменные, требующие большого количества памяти. Заводить локальный массив из миллиона элементов, или миллион локальных переменных (мало ли что бывает) — не самая лучшая идея. Даже один вызов такой «жадной» функции легко может вызвать переполнение стека. Для получения больших объемов данных лучше воспользоваться механизмами динамической памяти, которая позволит обработать ошибку её нехватки.

Однако динамическая память является довольно медленной в плане выделения и освобождения (поскольку этим занимается операционная система), кроме того, при прямом доступе приходится вручную выделять её и освобождать. Память же в стеке выделяется очень быстро (по сути, надо лишь изменить значение одного регистра), кроме того, у объектов, выделенных в стеке, автоматически вызываются деструкторы при возврате управления функцией и очистке стека. Разумеется, тут же возникает желание получить память из стека. Поэтому третий путь к переполнению — самостоятельное выделение в стеке памяти программистом. Специально для этой цели библиотека языка Си предоставляет функцию alloca. Интересно заметить, что если у функции для выделения динамической памяти malloc есть свой «близнец» для её освобождения free, то у функции alloca его нет — память освобождается автоматически после возврата управления функцией. Возможно, это только осложняет ситуацию — ведь до выхода из функции освободить память не получится. Даже несмотря на то, что согласно man-странице «функция alloca зависит от машины и компилятора; во многих системах ее реализация проблематична и содержит много ошибок; ее использование очень несерьезно и не одобряется» — она все равно используется.

Примеры

В качестве примера рассмотрим код для рекурсивного поиска файлов, расположенный на MSDN:

void DirSearch(String* sDir)
 {
     try
     {
         // Find the subfolders in the folder that is passed in.
         String* d[] = Directory::GetDirectories(sDir);
         int numDirs = d->get_Length();
         
         for (int i=0; i < numDirs; i++)
         {
             // Find all the files in the subfolder.
             String* f[] = Directory::GetFiles(d[i],textBox1->Text);
             int numFiles = f->get_Length();

             for (int j=0; j < numFiles; j++)
             {
                 listBox1->Items->Add(f[j]);
             }
             DirSearch(d[i]);
         }
     }
     catch (System::Exception* e)
     {
         MessageBox::Show(e->Message);
     }
 }

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

Пример второго подхода, взятый из вопроса «Почему происходит переполнение стека?» с сайта под названием Stack Overflow (сайт является сборником вопросов и ответов на любые программистские темы, а не только по переполнению стека, как может показаться):

#define W 1000
#define H 1000
#define MAX 100000 
//...
int main()
{
    int image[W*H];
    float dtr[W*H];
    initImg(image,dtr);
    return 0;
}

Как видно, в функции main выделяется память в стеке под массивы типов int и float по миллиону элементов каждый, что в сумме дает чуть менее 8 мегабайт. Если учесть, что по умолчанию Visual C++ резервирует под стек лишь 1 мегабайт, то ответ становится очевидным.

А вот пример, взятый из GitHub-репозитория проекта Flash-плеера Lightspark:

DefineSoundTag::DefineSoundTag(/* ... */)
{
    // ...
    unsigned int soundDataLength = h.getLength()-7;
    unsigned char *tmp = (unsigned char *)alloca(soundDataLength);
    // ...
}

Можно надеятся, что h.getLength()-7 не будет слишком большим числом, чтобы на следующей строчке не произошло переполнения. Но стоит ли сэкономленное на выделении памяти время «потенциального» вылета программы?

Итог

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

Библиографический список

• Э. Таненбаум. Архитектура компьютера.
• Wikipedia. Stack Overflow.
• man 3 alloca.
• MSDN. How to recursively search folders by using Visual C++.
• Stack Overflow. Stack Overflow C++.
• GitHub. Lightspark — «tags.cpp».

Присылаем лучшие статьи раз в месяц

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

Читатели наших статей, посвященных разработке 64-битных приложений, часто упрекают нас в отсутствии обоснованности описываемых проблем. А именно, что мы не приводим примеры ошибок в реальных приложениях.

Я решил собрать примеры различных типов ошибок, которые мы сами обнаружили в реальных программах, о которых прочитали в интернете или о которых нам сообщили пользователи PVS-Studio. Итак, предлагаю вашему вниманию статью, представляющую собой коллекцию из 30 примеров 64-битных ошибок на языке Си и Си++.

Продолжение статьи >>

Введение

Наша компания ООО «Системы программной верификации» занимается разработкой специализированного статического анализатора Viva64 выявляющего 64-битные ошибки в коде приложений на языке Си/Си++. В ходе этой работы наша коллекция примеров 64-битных дефектов постоянно пополняется, и мы решили собрать в этой статье наиболее интересные на наш взгляд ошибки. В статье приводятся примеры как взятые непосредственно из кода реальных приложений, так и составленные синтетически на основе реального кода, так как в нем они слишком «растянуты».

Статья только демонстрирует различные виды 64-битных ошибок и не описывает методов их обнаружения и профилактики. Вы можете подробно познакомиться с методами диагностики и исправления дефектов в 64-битных программах, обратившись к следующим ресурсам:

1. Курс по разработке 64-битных приложений на языке Си/Си++ [1];
2. Что такое size_t и ptrdiff_t [2];
3. 20 ловушек переноса Си++ — кода на 64-битную платформу [3];
4. Учебное пособие по PVS-Studio [4];
5. 64-битный конь, который умеет считать [5].

Также вы можете познакомиться с демонстрационной версией инструмента PVS-Studio, в состав которой входит статический анализатор кода Viva64, выявляющий практически все описанные в статье ошибки. Демонстрационная версия доступна для скачивания по адресу: http://www.viva64.com/ru/pvs-studio/download/.

Пример 1. Переполнение буфера

struct STRUCT_1
{
  int *a;
};

struct STRUCT_2
{
  int x;
};
...
STRUCT_1 Abcd;
STRUCT_2 Qwer;
memset(&Abcd, 0, sizeof(Abcd));
memset(&Qwer, 0, sizeof(Abcd));

В программе объявлены два объекта типа STRUCT_1 и STRUCT_2, которые перед началом использования необходимо очистить (инициализировать все поля нулями). Реализуя инициализацию, программист решил скопировать похожу строчку и заменил в ней «&Abcd» на «&Qwer». Но при этом он забыл заменить «sizeof(Abcd)» на «sizeof(Qwer)».По удачному стечению обстоятельств размер структур STRUCT_1 и STRUCT_2 совпадал в 32-битной системе и код корректно работал долгое время.

При переносе кода на 64-битную систему размер структуры Abcd увеличился и как следствие возникла ошибка переполнения буфера (см. рисунок 1).

Рисунок 1 — Схематичное пояснение примера переполнения буфера

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

Пример 2. Лишние приведения типов

char *buffer;
char *curr_pos;
int length;
...
while( (*(curr_pos++) != 0x0a) && 
       ((UINT)curr_pos - (UINT)buffer < (UINT)length) );

Код плох, но это реальный код. Его задача состоит в поиске конца строки, обозначенного символом 0x0A. Код не будет работать со строками длиннее INT_MAX символов, так как переменная length имеет тип int. Однако нас интересует другая ошибка, поэтому будем считать, что программа работает с небольшим буфером и использование типа int корректно.

Проблема в том, что в 64-битной системе указатели buffer и curr_pos могут лежать за пределами первых 4 гигабайт адресного пространства. В этом случае явное приведение указателей к типу UINT отбросит значащие биты, и работа алгоритма будет нарушена (см. рисунок 2).

Рисунок 2 — Некорректны вычисления при поиске терминального символа

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

while(curr_pos - buffer < length && *curr_pos != 'r')
  curr_pos++;

Пример 3. Некорректные #ifdef

Часто в программах с длинной историей можно встретить участки кода, обернутые в конструкции #ifdef — -#else — #endif. При переносе программ на новую архитектуру, некорректно написанные условия могут привести к компиляции не тех фрагментов кода, как это планировалось разработчиками в прошлом (см. рисунок 3). Пример:

#ifdef _WIN32 // Win32 code
  cout << "This is Win32" << endl;
#else         // Win16 code
  cout << "This is Win16" << endl;
#endif

//Альтернативный некорректный вариант:
#ifdef _WIN16 // Win16 code
  cout << "This is Win16" << endl;
#else         // Win32 code
  cout << "This is Win32" << endl;
#endif

Рисунок 3 — Два варианта — это слишком мало

Полагаться на вариант #else в подобных ситуациях опасно. Лучше явно рассмотреть поведение для каждого случая (см. рисунок 4), а в ветку #else поместить сообщение об ошибке компиляции:

#if   defined _M_X64 // Win64 code (Intel 64)
  cout << "This is Win64" << endl;
#elif defined _WIN32 // Win32 code
  cout << "This is Win32" << endl;
#elif defined _WIN16 // Win16 code
  cout << "This is Win16" << endl;
#else
  static_assert(false, "Неизвестная платформа");
#endif

Рисунок 4 — Проверяются все возможные пути компиляции

Пример 4. Путаница с int и int*

В старых программах, особенно на Си, не редки фрагменты кода, где указатель хранят в типе int. Однако иногда это делается не умышленно, а скорее по невнимательности. Рассмотрим пример, содержащий путаницу, возникшую с использованием типа int и указателем на тип int:

int GlobalInt = 1;

void GetValue(int **x)
{
  *x = &GlobalInt;
}

void SetValue(int *x)
{
  GlobalInt = *x;
}

...
int XX;
GetValue((int **)&XX);
SetValue((int *)XX); 

В данном примере переменная XX используется в качестве буфера для хранения указателя. Этот код будет корректно работать в тех 32-битных системах, где размер указателя совпадает с размером типа int. В 64-битном системе этот код некорректен и вызов

GetValue((int **)&XX);

приведет к порче 4 байт памяти рядом с переменной XX (см. рисунок 5).

Рисунок 5 — Порча памяти рядом с переменной XX

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

Исправление ошибки элементарно и заключается в выборе правильного типа для переменной XX. При этом перестает быть необходимым явное приведение типа:

int *XX;
GetValue(&XX);
SetValue(XX);

Пример 5. Использование устаревших функций

Ряд API-функций, хотя и оставлен для совместимости, представляет собой опасность при разработке 64-битных приложений. Классическим примером является использование таких функций как SetWindowLong и GetWindowLong. В программах можно встретить код, подобный следующему:

SetWindowLong(window, 0, (LONG)this);
...
Win32Window* this_window = (Win32Window*)GetWindowLong(window, 0);

Программиста, некогда написавшего этот код, не в чем упрекнуть. В ходе разработки, лет 5-10 назад, программист, опираясь на свой опыт и MSDN, составил код совершенно корректный с точки зрения 32-битвной системы Windows. Прототип этих функций выглядит следующим образом:

LONG WINAPI SetWindowLong(HWND hWnd, int nIndex, LONG dwNewLong);
LONG WINAPI GetWindowLong(HWND hWnd, int nIndex);

То, что указатель явно приводится к типу LONG также оправдано, поскольку размер указателя и типа LONG совпадают в Win32 системах. Но думаю понятно, что при перекомпиляции программы в 64-битном варианте, данные приведения типа могут послужить причиной падения или неверной работы приложения.

Неприятность ошибки заключается в ее нерегулярном или даже крайне редком проявлении. Произойдет ошибка или нет, зависит от того, в какой области памяти создан объект, на который указывает указатель «this». Если объект создается в младших 4 гигабайтах адресного пространства, то 64-битная программа может корректно функционировать. Ошибка неожиданно может проявить себя через большой промежуток времени, когда из-за выделения памяти, объекты начнут создаваться за пределами первых четырех гигабайт.

В 64-битной системе использовать функции SetWindowLong/GetWindowLong можно только в том случае, если программа действительно сохраняет некие значения типа LONG, int, bool и подобные им. Если необходимо работать с указателями, то следует использовать расширенные варианты функций: SetWindowLongPtr/GetWindowLongPtr. Хотя, пожалуй, следует порекомендовать в любом случае использовать новые функции, чтобы не спровоцировать в будущем новых ошибок.

Примеры с функциями SetWindowLong и GetWindowLong являются классическими и приводятся практически во всех статьях посвященных разработке 64-битных приложений. Однако следует учесть, что этими функциями дело не ограничивается. Обратите внимания на: SetClassLong, GetClassLong, GetFileSize, EnumProcessModules, GlobalMemoryStatus (см. рисунок 6).

Рисунок 6 — Таблица с именами некоторых устаревших и современных функций

Пример 6. Обрезание значений при неявном приведении типов

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

bool Find(const ArrayOfStrings &arrStr)
{
  ArrayOfStrings::const_iterator it;
  for (it = arrStr.begin(); it != arrStr.end(); ++it)
  {
    unsigned n = it->find("ABC"); // Truncation
    if (n != string::npos)
      return true;
  }
  return false;
};

Приведенная функция ищет текст «ABC» в массиве строк и возвращает true, в случае если хотя бы одна строка содержит последовательность «ABC». При компиляции 64-битной версии кода, эта функция всегда будет возвращать true.

Константа «string::npos» в 64-битной системе имеет значение 0xFFFFFFFFFFFFFFFF типа size_t. При помещение этого значения в переменную «n» типа unsigned, происходит его обрезание до 0xFFFFFFFF. В результате условие » n != string::npos» всегда истинно, так как 0xFFFFFFFFFFFFFFFF не равно 0xFFFFFFFF (см. рисунок 7).

Рисунок 7 — Схематичное пояснение ошибки обрезания значения

Исправление элементарно, достаточно прислушаться к предупреждениям компилятора:

for (auto it = arrStr.begin(); it != arrStr.end(); ++it)
{
  auto n = it->find("ABC");
  if (n != string::npos)
    return true;
}
return false;

Пример 7. Необъявленные функции в Си

Несмотря на годы, программы или части программ, написанные на языке Си, остаются живее всех живых. Код этих программ гораздо более предрасположен к 64-битным ошибкам из-за менее строгих правил контроля типов в языке Си.

В языке Си можно использовать функции без их предварительного объявления. Проанализируем связанный с этим интересный пример 64-битной ошибки. Для начала рассмотрим корректный вариант кода, в котором происходит выделение и использование трех массивов размером по гигабайту каждый:

#include <stdlib.h>

void test()
{
  const size_t Gbyte = 1024 * 1024 * 1024;
  size_t i;
  char *Pointers[3];

  // Allocate
  for (i = 0; i != 3; ++i)
    Pointers[i] = (char *)malloc(Gbyte);

  // Use
  for (i = 0; i != 3; ++i)
    Pointers[i][0] = 1;

  // Free
  for (i = 0; i != 3; ++i)
    free(Pointers[i]);
}

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

Теперь удалим или закомментируем строчку «#include <stdlib.h>». Код по-прежнему будет собираться, но при запуске программы произойдет ее аварийное завершение. Если заголовочный файл «stdlib.h» не подключен, компилятор языка Си считает, что функция malloc вернет тип int. Первые два выделения памяти, скорее всего, пройдут успешно. При третьем обращении функция malloc вернет адрес массива за пределами первых 2-х гигабайт. Поскольку компилятор считает, что результат работы функции имеет тип int, он неверно интерпретирует результат и сохраняет в массиве Pointers некорректное значение указателя.

Рассмотрим ассемблерный код, генерируемый компилятором Visual C++ для 64-битной Debug версии. Вначале приводится корректный код, который будет сгенерирован, когда присутствует объявление функции malloc (подключен файл «stdlib.h»):

Pointers[i] = (char *)malloc(Gbyte);
mov   rcx,qword ptr [Gbyte]
call  qword ptr [__imp_malloc (14000A518h)]
mov    rcx,qword ptr [i]
mov    qword ptr Pointers[rcx*8],rax

Теперь рассмотрим вариант некорректного кода, когда отсутствует объявление функции malloc:

Pointers[i] = (char *)malloc(Gbyte);
mov    rcx,qword ptr [Gbyte]
call   malloc (1400011A6h)
cdqe
mov    rcx,qword ptr [i]
mov    qword ptr Pointers[rcx*8],rax

Обратите внимание на наличие инструкции CDQE (Convert doubleword to quadword). Компилятор посчитал, что результат содержится в регистре eax и расширил его до 64-битного значения, чтобы записать в массив Pointers. Соответственно старшие биты регистра rax будут потеряны. Если даже адрес выделенной памяти лежит в пределах первых четырех гигабайт, в случае, когда старший бит регистра eax равен 1 мы все равно получим некорректный результат. Например, адрес 0x81000000 превратится в 0xFFFFFFFF81000000.

Пример 8. Останки динозавров в больших и старых программах

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

Рисунок 8 — Раскопки динозавра

Есть атавизмы связанные и с 64-битностью. Вернее атавизмы, препятствующие работе современного 64-битного кода. Рассмотрим пример:

// beyond this, assume a programming error
#define MAX_ALLOCATION 0xc0000000 

void *malloc_zone_calloc(malloc_zone_t *zone,
  size_t num_items, size_t size)
{
  void *ptr;
  ...

  if (((unsigned)num_items >= MAX_ALLOCATION) ||
      ((unsigned)size >= MAX_ALLOCATION) ||
      ((long long)size * num_items >=
       (long long) MAX_ALLOCATION))
  {  
    fprintf(stderr,
      "*** malloc_zone_calloc[%d]: arguments too large: %d,%dn",
      getpid(), (unsigned)num_items, (unsigned)size);
    return NULL;
  }
  ptr = zone->calloc(zone, num_items, size);
  ...
  return ptr;
}

Во-первых, код функции содержит проверку на допустимые размеры выделяемой памяти, являющиеся странными для 64-битной системы. А во-вторых, выдаваемое диагностическое сообщение будет некорректно, поскольку если мы попросим выделить память под 4 400 000 000 элементов, из-за явного приведения типа к unsigned, нам будет выдано странное сообщение о невозможности выделения памяти всего лишь для 105 032 704 элементов.

Пример 9. Виртуальные функции

Одним из красивых примеров 64-битных ошибок является использование неверных типов аргументов в объявлениях виртуальных функций. Причем обычно это не чья-то неаккуратность, а просто «несчастный случай», где нет виноватых, но есть ошибка. Рассмотрим следующую ситуацию.

С незапамятных времен в библиотеке MFC есть класс CWinApp, в котором имеется функция WinHelp:

class CWinApp {
  ...
  virtual void WinHelp(DWORD dwData, UINT nCmd);
};

Для показа собственной справки в пользовательском приложении необходимо было эту функцию перекрыть:

class CSampleApp : public CWinApp {
  ...
  virtual void WinHelp(DWORD dwData, UINT nCmd);
};

И все было прекрасно до тех пор, пока не появились 64-битные системы. Разработчикам MFC пришлось поменять интерфейс функции WinHelp (и некоторых других функций) так:

class CWinApp {
  ...
  virtual void WinHelp(DWORD_PTR dwData, UINT nCmd);
};

В 32-битном режиме типы DWORD_PTR и DWORD совпадали, а вот в 64-битном нет. Естественно разработчики пользовательского приложения также должны сменить тип на DWORD_PTR, но чтобы это сделать, про это необходимо в начале узнать. В результате в 64-битной программе возникает ошибка, так как функция WinHelp в пользовательском классе не вызывается (см. рисунок 9).

Рисунок 9 — Ошибка, связанная с виртуальными функциями

Пример 10. Магические числа в качестве параметров

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

Рисунок 10 — Магические числа опасные для 64-битных программ

Продемонстрируем пример работы с функцией CreateFileMapping, встретившийся в одной из CAD-систем:

HANDLE hFileMapping = CreateFileMapping(
  (HANDLE) 0xFFFFFFFF,
  NULL,
  PAGE_READWRITE,
  dwMaximumSizeHigh,
  dwMaximumSizeLow,
  name);

Вместо корректной зарезервированной константы INVALID_HANDLE_VALUE используется число 0xFFFFFFFF. Это некорректно в Win64 программе, где константа INVALID_HANDLE_VALUE принимает значение 0xFFFFFFFFFFFFFFFF. Правильным вариантом вызова функции будет:

HANDLE hFileMapping = CreateFileMapping(
  INVALID_HANDLE_VALUE,
  NULL,
  PAGE_READWRITE,
  dwMaximumSizeHigh,
  dwMaximumSizeLow,
  name);

Примечание. Некоторые считают, что значение 0xFFFFFFFF при расширении до указателя превращается в 0xFFFFFFFFFFFFFFFF. Это не так. Согласно правилам языка Си/Си++ значение 0xFFFFFFFF имеет тип «unsigned int», так как не может быть представлено типом «int». Соответственно, расширяясь до 64-битного типа, значение 0xFFFFFFFFu превращается в 0x00000000FFFFFFFFu. А вот если написать так (size_t)(-1), то мы получим ожидаемое 0xFFFFFFFFFFFFFFFF. Здесь «int» вначале расширяется до «ptrdiff_t», а затем превращается в «size_t».

Пример 11. Магические константы, обозначающие размер

Другой частой ошибкой является использование магических чисел для задания размера объекта. Рассмотрим пример выделения и обнуления буфера:

size_t count = 500;
size_t *values = new size_t[count];
// Будет заполнена только часть буфера
memset(values, 0, count * 4);

В данном случае в 64-битной системе выделяется больше памяти, чем затем заполняется нулевыми значениями (см. рисунок 11). Ошибка заключается в предположении, что размер типа size_t всегда равен четырем байтам.

Рисунок 11 — Заполнение только части массива

Корректный вариант:

size_t count = 500;
size_t *values = new size_t[count];
memset(values, 0, count * sizeof(values[0]));

Схожие ошибки можно встретить при вычислении размеров выделяемой памяти или сериализации данных.

Пример 12. Переполнение стека

Во многих случаях 64-битная программа потребляет больше памяти и стека. Выделение большего количества памяти в куче опасности не представляет, так как этого вида памяти 64-битной программе доступно во много раз больше, чем 32-битной. А вот увеличение используемой стековой памяти может привести к его неожиданному переполнению (stack overflow).

Механизм использования стека отличается в различных операционных системах и компиляторах. Мы рассмотрим особенность использования стека в коде Win64 приложений, построенных компилятором Visual C++.

При разработке соглашений по вызовам (calling conventions) в Win64 системах решили положить конец существованию различных вариантов вызова функций. В Win32 существовал целый ряд соглашений о вызове: stdcall, cdecl, fastcall, thiscall и так далее. В Win64 только одно «родное» соглашение по вызовам. Модификаторы подобные __cdecl компилятором игнорируются.

Соглашение по вызовам на платформе x86-64 похоже на соглашение fastcall, существующее в x86. В x64-соглашении первые четыре целочисленных аргумента (слева направо) передаются в 64-битных регистрах, выбранных специально для этой цели:

RCX: 1-й целочисленный аргумент
RDX: 2-й целочисленный аргумент
R8: 3-й целочисленный аргумент
R9: 4-й целочисленный аргумент

Остальные целочисленные аргументы передаются через стек. Указатель «this» считается целочисленным аргументом, поэтому он всегда помещается в регистр RCX. Если передаются значения с плавающей точкой, то первые четыре из них передаются в регистрах XMM0-XMM3, а последующие — через стек.

Хотя аргументы могут быть переданы в регистрах, компилятор все равно резервирует для них место в стеке, уменьшая значение регистра RSP (указателя стека). Как минимум, каждая функция должна резервировать в стеке 32 байта (четыре 64-битных значения, соответствующие регистрам RCX, RDX, R8, R9). Это пространство в стеке позволяет легко сохранить содержимое переданных в функцию регистров в стеке. От вызываемой функции не требуется сбрасывать в стек входные параметры, переданные через регистры, но резервирование места в стеке при необходимости позволяет это сделать. Если передается более четырех целочисленных параметров, в стеке резервируется соответствующее дополнительное пространство.

Описанная особенность приводит к существенному возрастанию скорости поглощения стека. Даже если функция не имеет параметров, то от стека все равно будет «откушено» 32 байта, которые затем никак не используются. Смысл использования такого неэкономного механизма связан в унификации и упрощение отладки.

Обратим внимание еще на один момент. Указатель стека RSP должен перед очередным вызовом функции быть выровнен по границе 16 байт. Таким образом, суммарный размер используемого стека при вызове в 64-битном коде функции без параметров составляет 48 байт: 8 (адрес возврата) + 8 (выравнивание) + 32 (резерв для аргументов).

Неужели все так плохо? Нет. Не следует забывать, что большее количество регистров имеющихся в распоряжении 64-битного компилятора, позволяют построить более эффективный код и не резервировать в стеке память под некоторые локальные переменные функций. Таким образом, в ряде случаев 64-битный вариант функции использует меньше стека, чем 32-битный вариант. Более подробно этот вопрос и различные примеры рассматриваются в статье «Причины, по которым 64-битные программы требуют больше стековой памяти».

Предсказать, будет потреблять 64-битная программа больше стека или меньше невозможно. В силу того, что Win64-программа может использовать в 2-3 раза больше стековой памяти, необходимо подстраховаться и изменить настройку проекта, отвечающую за размер резервируемого стека. Выберите в настройках проекта параметр Stack Reserve Size (ключ /STACK:reserve) и увеличьте размер резервируемого стека в три раза. По умолчанию этот размер составляет 1 мегабайт.

Пример 13. Функция с переменным количеством аргументов и переполнение буфера

Хотя использование функций с переменным количеством аргументов, таких как printf, scanf считается в Си++ плохим стилем, они по прежнему широко используются. Эти функции создают множество проблем при переносе приложений на другие системы, в том числе и на 64-битные системы. Рассмотрим пример:

int x;
char buf[9];

sprintf(buf, «%p», &x);
Автор кода не учел, что размер указателя в будущем может составить более 32 бит. В результате на 64-битной архитектуре данный код приведет к переполнению буфера (см. рисунок 12). Эту ошибку вполне можно отнести к использованию магического числа ‘9’, но в реальном приложении переполнение буфера может возникнуть и без магических чисел.

Рисунок 12 — Переполнение буфера при работе с функцией sprintf

Варианты исправления данного кода различны. Рациональнее всего провести рефакторинг кода с целью избавиться от использования опасных функций. Например, можно заменить printf на cout, а sprintf на boost::format или std::stringstream.

Примечание. Эту рекомендацию часто критикуют разработчики под Linux, аргументируя тем, что gcc проверяет соответствие строки форматирования фактическим параметрам, передаваемым, например, в функцию printf. И, следовательно, использование printf безопасно. Однако они забывают, что строка форматирования может передаваться из другой части программы, загружаться из ресурсов. Другими словами, в реальной программе строка форматирования редко присутствует в явном виде в коде, и, соответственно, компилятор не может ее проверить. Если же разработчик использует Visual Studio 2005/2008/2010, то он не сможет получить предупреждение на код вида void *p = 0; printf(«%x», p); даже используя ключи /W4 и /Wall.

Пример 14. Функция с переменным количеством аргументов и неверный формат

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

const char *invalidFormat = "%u";
size_t value = SIZE_MAX;

// Будет распечатано неверное значение
printf(invalidFormat, value);

В других случаях ошибка в строке форматирования будет критична. Рассмотрим пример, основанный на реализации подсистемы UNDO/REDO в одной из программ:

// Здесь указатели сохранялись в виде строки
int *p1, *p2;
....
char str[128];
sprintf(str, "%X %X", p1, p2);

// В другой функции данная строка
// обрабатывалась следующим образом:
void foo(char *str)
{
  int *p1, *p2;
  sscanf(str, "%X %X", &p1, &p2);
  // Результат - некорректное значение указателей p1 и p2.
  ...
}

Формат «%X» не предназначен для работы с указателями и как следствие подобный код некорректен сточки зрения 64-битных систем. В 32-битных системах он вполне работоспособен, хотя и не красив.

Пример 15. Хранение в double целочисленных значений

Нам не приходилось самим встречать подобную ошибку. Вероятно, это ошибка редка, но вполне реальна.
Тип double, имеет размер 64-бита, и совместим со стандартом IEEE-754 на 32-битных и 64-битных системах. Некоторые программисты используют тип double для хранения и работы с целочисленными типами:

size_t a = size_t(-1);
double b = a;
--a;
--b;
size_t c = b; // x86: a == c
              // x64: a != c

Данный пример еще можно пытаться оправдывать на 32-битной системе, так как тип double имеет 52 значащих бита и способен без потерь хранить 32-битное целое значение. Но при попытке сохранить в double 64-битное целое число точное значение может быть потеряно (см. рисунок 13).

Рисунок 13 — Количество значащих битов в типах size_t и double

Вторая часть статьи.

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

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

[Краткое введение в стек и кучу]

Описание в этой статье сосредоточено на разработке надежного стека и кучи: как минимизировать стек и кучу безопасным способом.

Настольные компьютерные системы (компьютеры PC) и встраиваемые системы одинаково страдают от общих ошибок в дизайне стека и кучи, однако полностью отличаются друг от друга в реализации многих других аспектов. Один пример различий в этих рабочих условиях — размер доступной памяти. Windows и Linux по умолчанию используют 1 и 8 мегабайт пространства под стек; этот размер даже может увеличиваться. Размер кучи ограничен только доступной физической памятью и/или размером файла подкачки. Встраиваемые системы, с другой стороны, имеют очень ограниченный размер по ресурсам памяти, особенно когда это память RAM. Несомненно здесь требуется минимизировать стек и кучу, чтобы уложиться в ограничения по памяти для этого рабочего окружения. Большинство малых встраиваемых систем не имеют механизма виртуальной памяти; выделения стека, кучи и глобальных данных (т. е. переменных, буферов TCP/IP, USB и т. д.) статические, и это происходит в момент сборки приложения.

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

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

Переполнение выделенных данных может произойти в трех областях хранения данных; глобальные переменные (global), стек (stack) и куча (heap). Запись в массивы с превышением индекса или запись по адресу в указателе может привести к выходу за пределы памяти, выделенной для объекта (в таком случае могут быть испорчены другие важные данные). Некоторые попытки доступа к массиву могут быть проверены статическим анализом, например самим компилятором или чекером MISRA C:

int array[32];
array[35] = 0x1234;

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

int* p = malloc(32 * sizeof(int)); 
p += 35;

*p = 0x1234;

Долгое время методы перехвата ошибок переполнения объектов были доступны для десктоп-систем (можно назвать некоторые из них: Purify, Insure++, Valgrind). Эти средства встраивали в код приложения специальные проверки обращений к памяти во время выполнения программы. Это происходит ценой снижения скорости выполнения кода приложения и увеличения размера кода, так что такой метод не может быть полезным для малых встраиваемых систем.

Stack. Стек это область памяти, где программа сохраняет, к примеру, следующие данные:

• Локальные переменные
• Адреса возврата из подпрограмм
• Аргументы функции
• Временные ячейки памяти, используемые компилятором
• Контекст прерываний

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

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

Рис. 1. Ситуация переполнения стека.

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

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

Heap. Куча это то место, где размещена подсистема динамического выделения памяти (не путайте в данном контексте динамическую память с DRAM и SDRAM!). Динамическая память и куча может во многих случаях быть необязательной для применения во встраиваемых системах (может рассматриваться как опция). Динамическая память делает возможным использование одной и той же памяти совместно разными частями программы (имеется в виду не одновременное использование). Когда один модуль больше не нуждается в своей выделенной памяти, он просто возвращает её в общий пул кучи, после чего она может повторно использоваться каким-то другим модулем. Операциями выделения и освобождения памяти заведует специальная библиотека управления динамической памяти, предоставляющая функции наподобие malloc, calloc, realloc и free [] на языке C. Язык C++ использует библиотеку динамической памяти в операторах new и delete. Кучу также могут использовать сторонние библиотеки кода и операционные системы реального времени (RTOS []). Обычно куча одна, но их может быть и несколько. Некоторые особо продвинутые библиотеки даже могут использовать свои функции для обслуживания динамической памяти. 

Типичные примеры данных, которые размещаются в куче:

• Объекты текущих данных
• Объекты C++, время жизни которых управляются операторами new/delete
• Контейнеры STL C++
• Исключения C++

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

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

Другой аспект использования кучи в том, что производительность кода реального времени с данными в куче становится неопределенным. Время выделения памяти зависит от таких факторов, как предыдущие выделения и освобождения памяти, наличие в куче «дырок» и от эффективности уборщика мусора. Когда разработчик учитывает каждый цикл выполнения кода для обеспечения прогнозируемого поведения в реальном времени, интенсивные выделения/освобождения памяти могут стать недопустимыми.

Общие рекомендации в этой статье касаются в основном минимизации размера кучи в малых встраиваемых системах.

[Разработка надежного стека]

Другие типы инструментов, у которых есть необходимая информация для вычисления максимального требования к стеку, это компилятор и линкер. Эта функциональность доступна для среды разработки IAR Embedded Workbench for ARM. Мы рассмотрим некоторые методы, которые можно использовать для оценки требований к размеру стека.

Различные методы установки размера стека. Один из способов вычисления глубины стека — использование адреса текущего указателя стека. Это можно реализовать получением адреса аргумента функции или её локальной переменной. Если это сделать в начале функции main и для каждой из функций, на которую у Вас есть подозрение а большое использование стека, то Вы можете вычислить размер стека, который нужен приложению. Ниже приведен пример, где мы предполагаем, что стек растет от старших адресов памяти к младшим (так организован стек у большинства процессоров, в том числе MCS51, ARM, 8080):

char *highStack, *lowStack;

int main(int argc, char *argv[])
{
   highStack = (char *)&argc; 
   // ... 
   printf("Текущее использование стека (глубина): %dn", highStack - lowStack); 
}

// Самая "подозрительная" функция на предмет углубления в стек:

void deepest_stack_path_function(void) 
{ 
   int a; 
   lowStack = (char *)&a;
   // ... 
}

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

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

Есть вариант этого метода — периодически делать выборку значения указателя стека внутри прерывания таймера, срабатывающего с достаточно высокой частотой. Частота прерываний таймера должна быть максимально возможной, пока она не начинает влиять на производительность реального времени приложения. Типичные частоты могут быть в диапазоне 10..250 кГц. Достоинство этого метода — не нужно вручную искать функцию с самым глубоким использованием стека. Также можно определять использование стека функциями обработки прерывания (ISR), если эта функция обработчика прерывания может вытеснять другие прерывания. Однако следует учитывать, что функции ISR обычно выполняются очень быстро, и анализирующая функция прерывания может пропустить короткий вызов одного из других прерываний.

void sampling_timer_interrupt_handler(void) 
{
   char* currentStack;
   int a;
   currentStack = (char *)&a;
   if (currentStack < lowStack) lowStack = currentStack;
}

Защитная зона стека (stack guard zone). Защитная зона стека это область памяти, размещенная непосредственно ниже стека, где стек оставляет следы, если происходит его переполнение. Этот метод всегда реализуется в настольных (больших) системах, где операционная система может быть просто настроена для детектирования ошибок защиты памяти в ситуациях переполнения стека. На малых встраиваемых системах без блока управления памятью (Memory Management Unit, MMU) защитная зона все еще может быть организована таким же способом, и это будет довольно полезно. Чтобы такая зона была достаточно эффективной, она должна иметь подходящий размер, чтобы поймать записи в эту защитную зону.

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

Самый лучший метод защитной зоны может быть реализован, если MCU оборудован (аппаратным) блоком защиты памяти (memory protection unit, MPU или MMU). В этом случае MPU может быть настроен таким образом, чтобы он срабатывал на записи в защитную зону. Если произошел такого рода недопустимый доступ, будет срабатывать исключение (exception), и обработчик исключения может записать или вывести в лог информацию о том, что произошло. Эту информацию можно будет впоследствии проанализировать.

Рис. 2. Стек с защитной (guard) зоной.

Заполнение области стека известными данными. Одна из техник определения переполнения стека — заполнить все пространство стека заранее известной маской, например байтами 0xCD, перед тем, как приложение начнет свое выполнение. Всякий раз, когда приложение останавливается (например, с помощью отладчика), область памяти стека можно просмотреть в области его конца. В используемой области стека 0xCD не присутствует, потому что туда записывались адреса возврата и значения различных локально используемых регистров и переменных. Если в области стека не найдено значений маски (0xCD), то это означает, что стек переполнился.

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

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

Рис. 3. Окно стека в среде разработки IAR Embedded Workbench.

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

Обычно компилятор будет генерировать эту информацию для каждой функции языка C, но в некоторых ситуациях Вы должны сами предоставить для системы информацию, относящуюся к стеку. Например, если в приложении присутствуют косвенные вызовы функций, indirect call (с использованием указателей на функции), то Вы должны предоставить список возможных функций, которые могут быть вызваны из каждой вызываемой функции. Вы можете сделать это с помощью директив pragma в файле исходного кода, или с помощью отдельного файла для управления использования стека (stack usage control file) в процессе линковки.

void foo(int i)
{

#pragma calls = fun1, fun2, fun3 
   func_arr[i](); 
}

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

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

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

Рис. 4. Результат вычисленного линкером максимального использования стека.

[Надежный дизайн кучи]

Где тут можно сделать ошибку? Недооценка использования кучи может привести к ошибке при вызове malloc(), т. е. требуемая область памяти не будет выделена. Эту ситуацию можно очень просто отследить программно, проверяя результат вызова функции malloc(). Если она вернет NULL, то значит память не была выделена, но тогда может быть слишком поздно (если это произошло в рабочем изделии у заказчика). Это серьезная ситуация, поскольку в большинстве встраиваемых систем нет подходящего способа восстановления из ошибки по нехватке памяти в куче; есть только один доступный подходящий способ — перезапустить приложение. Переоценка использования кучи необходима из-за динамической природы работы кучи, однако слишком большое выделение памяти для кучи только впустую потратит ценные ресурсы памяти.

При использовании кучи могут произойти две другие ошибки:

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

Перед тем, как продолжить, давайте вспомним API выделения динамической памяти.

void* malloc(size_t size);

Функция malloc делает следующее:

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

Описание работы функции free:

• Освобождает область памяти (ранее выделенный блок), на которую указывает аргумент p.
• Требует в качестве аргумента достоверного значения указателя p, которое было ранее получено из вызова malloc(), calloc() или realloc().
• Следует избегать нескольких вызовов free(p) для одного и того же значения p (после первого вызова free указатель p становится недостоверным).

void* calloc(size_t nelem, size_t elsize);

Функция calloc работает подобно malloc(), но с тем отличием, что очищает выделенный блок памяти.

void* realloc(void* p, size_t size);

Описание работы функции realloc:

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

В C++ следующие встроенные операторы языка используют динамическую память кучи:

• Оператор new, работающий подобно malloc().
• new[].
• Оператор delete, работающий подобно free().
• delete[].

Имеется несколько вариантов реализации аллокатора динамической памяти. Наиболее часто сегодня используется Dlmalloc (Doug Lea’s Memory Allocator). Dlmalloc можно найти в Linux, а также во многих инструментах (библиотеках) разработки для встраиваемых систем. Dlmalloc свободно доступна для бесплатного использования (помещена в public domain).

Внутренняя структура кучи вкрапляется данными, выделенными приложением. Если приложение запишет память вне выделенных данных, то оно может легко нарушить внутреннюю связанную структуру кучи.

Рис. 5 дает некий упрощенный вид на то, как различные структуры данных окружают выделенные пользовательские данные (user data). Становится очевидным, что любая запись в область вне пользовательских данных серьезно повредит кучу.

Рис. 5. Окружение служебными данными выделенного из кучи блока для пользовательских данных.

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

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

• Ошибки инициализации

Не инициализированные глобальные данные всегда инициализируются нулями. Хорошо известный факт, что можно легко забыть о том, что вызовы malloc(), realloc() и оператор new языка C++ ничего подобного не делают, т. е. выделенная область данных заполнена мусором. Однако есть специальный вариант malloc(), носящий имя calloc(), который инициализирует нулями выделенный блок для данных. Оператор C++ new вызовет соответствующий конструктор, где следует гарантировать, что все элементы данных сконструированного (выделенного из кучи) объекта будут правильно инициализированы.

• Неправильное разделение скаляров и массивов

На языке C++ есть разные операторы для скаляров и массивов: new и delete применяются для выделения и освобождения скаляров, и new[] и delete[] применяются для массивов.

• Запись в уже освобожденную память

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

• Отсутствие проверки возвращенных значений

Все вызовы malloc(), realloc() и calloc() возвратят указатель NULL, чтобы показать отсутствие свободной памяти (неудачное выделение блока памяти, out of memory). Настольные системы сгенерируют события отказа памяти (memory fault) и нехватки памяти (out-of-memory), так что эти ситуации просто отследить еще в процессе разработки. Встраиваемые системы могут быть устроены по-другому: по адресу 0 у них может быть память программ FLASH, и в них могут происходить больше других тонких ошибок. Если в Вашем MCU есть блок защиты памяти (memory protection unit, MPU), то следует сконфигурировать его таким образом, чтобы генерировались ошибки доступа к памяти при попытке доступа во FLASH и другие критические области (ОЗУ, где находится исполняемый код, защитная область стека и т. п.).

• Освобождение несколько раз одного и того же блока памяти

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

• Запись вне выделенной области

Это также повредит внутренние структуры аллокатора памяти, и такую ситуацию сложно определить и исправить.

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

Рис. 6. Выделение памяти тестовой оберткой MyMalloc.

Здесь поле «magic number» перед данными (user data) используется для детектирования повреждения и будет проверен, когда память будет освобождаться. Поле size, находящееся ниже пользовательских данных, используется оберткой для free() (функция MyFree), чтобы найти «magic number». Пример оберток, показанный ниже, использует 8 байт дополнительной нагрузки на одно выделение памяти, что вполне допустимо для большинства приложений. Этот пример также показывает, как глобально переопределить (override) операторы new и delete языка C++. Пример перехватит только ошибки такого рода, что вся выделенная память не была соответственно освобождена в какой-то момент времени. Для некоторых приложений такая проверка может не потребоваться. В этом случае обертка должна вести список всех выделений памяти, и периодически проверять все выделения, записанные в этом списке. Дополнительная нагрузка реализации этого может быть не такая большая, как это может показаться на первый взгляд, поскольку встраиваемые системы обычно не очень интенсивно используют динамическую память, сохраняя размер списка выделений в разумных пределах.

#include < stdint.h>

#include < stdlib.h>

#define MAGIC_NUMBER 0xefdcba98

uint32_t myMallocMaxMem;

void* MyMalloc(size_t bytes)
{
   uint8_t *p, *p_end;
   static uint8_t* mLow = (uint8_t*)0xffffffff; /* самый малый адрес, возвращенный

                                                   вызовом malloc() */
   static uint8_t* mHigh;     /* самый большой адрес + data, возвращенный malloc() */
   bytes = (bytes + 3) & ~3;  /* гарантирует выравнивание для magic number */
   p = (uint8_t*)malloc(bytes + 8); /* учет области 2x32-бит для size и magic number */
   if (p == NULL)
   {
      abort(); /* ошибка нехватки памяти, out of memory */
   }
   *((uint32_t*)p) = bytes; /* запомнить размер size */
   *((uint32_t*)(p + 4 + bytes)) = MAGIC_NUMBER; /* записать magic number после

                                                    пользовательского выделения */
   /* Грубый метод оценки максимального используемого размера

      с момента запуска приложения. */
   if (p < mLow) mLow = p;
   p_end = p + bytes + 8;
   if (p_end > mHigh) mHigh = p_end;
   myMallocMaxMem = mHigh - mLow;
   return p + 4; /* выделяемая область начинается после size */
}

void MyFree(void* vp)
{
   uint8_t* p = (uint8_t*)vp - 4;
   int bytes = *((uint32_t*)p);
   /* Проверка, что magic number не был поврежден: */
   if (*((uint32_t*)(p + 4 + bytes)) != MAGIC_NUMBER)
   {
      abort(); /* Ошибка: переполнение данных или освобождение блока

                  памяти, который уже был освобожден */
   }
   *((uint32_t*)(p + 4 + bytes)) = 0; /* удаление magic number, чтобы можно было

                                         обнаружить ошибочно-повторное освобождение

                                         блока памяти */
   free(p);
}

#ifdef __cplusplus

// Глобальное переназначение операторов new, delete, new[] и delete[].

void* operator new (size_t bytes) { return MyMalloc(bytes); }

void operator delete (void *p) { MyFree(p); }

#endif

Как установить размер кучи. Итак, как можно определить требуемый минимальный размер кучи для приложения? Из-за того, что может произойти фрагментация памяти в процессе повторяющихся циклов освобождения и выделения памяти, ответ на этот вопрос нетривиален. Рекомендуется запустить тест системы при условиях, когда динамическая память будет использоваться по максимуму. Важно выполнить этот тест несколько раз, чтобы проанализировать переход от малого использования памяти кучи к интенсивному, и оценить её возможную фрагментацию. Когда тесты будут завершены, максимальный уровень выделения памяти в куче сравнивают с реально используемым размером кучи. Реальный размер кучи выставляют, добавляя от 25% до 100% к максимально определенному задействованному размеру кучи, в зависимости от того, как устроено приложение.

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

Для встраиваемых систем, которые не эмулируют sbrk() (а среда разработки IAR Embedded Workbench как раз относится к таким встраиваемым системам), обычно для аллокатора памяти предоставляют память кучи одним куском. В таком случае вызов malloc_max_footprint() становится бесполезным; он просто вернет размер всей кучи. Одним из решений может быть вызов mallinfo() после каждого вызова malloc(), например в обертке функции, описанной раннее, и получить обзор общего выделенного пространства (mallinfo->uordblks). Функция mallinfo() выполняет довольно интенсивные вычисления, так что её использование может повлиять на производительность системы. Лучший метод — записывать максимальные расстояния между выделенными областями памяти. Это просто осуществить, и показано в примере обертки; максимальное значение записывается в переменной myMallocMaxMem. Этот метод будет работать, когда куча предоставлена в одном непрерывной (не состоящей из отдельных кусков) области памяти.

[Стек и куча в IAR 4.41]

В этой старой версии IAR распределение памяти задается в файле *.xcl, который настраивается в опциях проекта (Options… -> Linker -> закладка Config -> Linker command file). Стек начинается от старших (самых больших) адресов памяти и растет к нижним (самым малым адресам), навстречу к функциям __ramfunc и глобальным переменным. Вот пример настройки в XCL-файле, когда кучи нет, и определен только стек размера 400 байт:

//*************************************************************************
// Сегменты стека и кучи.
//*************************************************************************
-D_CSTACK_SIZE=(100*4)
-D_IRQ_STACK_SIZE=(3*8*4)
-D_HEAP_SIZE=0

Если в проекте определена куча, то она находится сразу за локальными переменными, и растет навстречу стеку. Вот другой пример, где определена куча размера 0x3C50 и стек размера 0x1D00:

-D_CSTACK_SIZE=(1D00)
-D_IRQ_STACK_SIZE=(3*8*4)
-D_HEAP_SIZE=3C50

Вот так может выглядеть карта памяти RAM микроконтроллера AT91SAM7X256 для второго примера:

Определить, насколько корректно заданы размер кучи и размер стека, можно с помощью заполнения области кучи и стека заранее известным значением байта. Например, всю память кучи можно заполнить байтом 0xaa, а всю свободную память стека можно заполнить байтом 0xbb. Это целесообразно делать в функции void AT91F_LowLevelInit(void), которая находится в модуле Cstartup_SAM7.c. Пример такого заполнения:

void AT91F_LowLevelInit(void)
{
   ...
   
   //Заполнение кучи известным значением 0xAA:

   #define HEAP_BEGIN 0x0020A344                //взято из map-файла PImain.map

   #define HEAP_SIZE  0x3C50                    //взято из map-файла PImain.map
   memset((void*)HEAP_BEGIN, 0xAA, HEAP_SIZE);
   //Заполнение стека известным значением 0xBB:

   #define STACK_BEGIN (HEAP_BEGIN+HEAP_SIZE)   //стек начинается сразу за кучей

   #define STACK_SIZE  0x1D00-0x0100)           //взято из файла at91SAM7X256_FLASH.xcl
                                                //с отступом 0x0100 байт от конца памяти
   memset((void*)STACK_BEGIN, 0xBB, STACK_SIZE);
}

Как узнать значения HEAP_BEGIN, HEAP_SIZE, STACK_BEGIN, STACK_SIZE. HEAP_BEGIN задает самый младший адрес области памяти кучи, а константа HEAP_SIZE задает размер заполняемой области. Значение HEAP_BEGIN можно узнать опытным путем в отладчике по адресу первого выделенного блока (через malloc или new), или если заглянуть в конец map-файла, раздел «SEGMENTS IN ADDRESS ORDER», там будет указаны начало и конец кучи, пример (параметры кучи выделены жирным шрифтом):

                ****************************************
                *                                      *
                *      SEGMENTS IN ADDRESS ORDER       *
                *                                      *
                ****************************************
SEGMENT              SPACE    START ADDRESS   END ADDRESS     SIZE  TYPE  ALIGN
=======              =====    =============   ===========     ====  ====  =====
ICODE                              00001000 - 0000111B         11C   rel    2
CODE                               0000111C - 0000C5C7        B4AC   rel    2
INITTAB                            0000C5C8 - 0000C5EB          24   rel    2
DATA_ID                            0000C5EC - 00014B6F        8584   rel    2
DATA_C                             00014B70 - 0001651F        19B0   rel    2
CODE_ID                            00016520 - 000169A7         488   rel    2
?FILL1                             000169A8 - 0003FFFF       29658   rel    0
CODE_I                             00200050 - 002004D7         488   rel    2
DATA_I                             002004D8 - 00208A5B        8584   rel    2
DATA_Z                             00208A5C - 0020A33D        18E2   rel    2
DATA_N                             0020A340 - 0020A343           4   rel    2

HEAP                               0020A344 - 0020DF93        3C50   rel    2
INTRAMEND_REMAP                         00210000                     rel    2 

HEAP_SIZE можно узнать из файла XCL в параметре HEAP_SIZE, или из того же map-файла, см. параметр SIZE таблицы выше.

STACK_BEGIN задает самый младший адрес области памяти стека, а STACK_SIZE задает размер заполняемой области. Значение STACK_BEGIN равно следующему за кучей адресу, а STACK_SIZE выбирается таким образом, чтобы заполнение памяти байтом 0xBB гарантированно не перекрыло содержимое стека, действующее в настоящий момент.

После запуска программы в рабочий режим устанавливают условия, при котором должно наблюдаться максимальное использование стека и кучи. Дают программе некоторое время поработать, после чего останавливают отладчик, и после этого в дампе памяти можно увидеть, насколько далеко продвинулось заполнение стека и кучи. Те места, которые еще свободны, будут заполнены байтами 0xAA и 0xBB для кучи и стека соответственно. Ниже на скриншоте показано, как может выглядеть память кучи и стека. Видно, что выделение памяти в куче подошло к своему пределу, дополнительное выделение памяти в куче может привести к переходу на область стека:

[Ссылки]

1. Mastering stack and heap for system reliability site:iar.com.
2. Nigel Jones, blog posts at embeddedgurus.com, 2007 and 2009.
3. John Regehr «Say no to stack overflow», EE Times Design, 2004.
4. Carnegie Mellon University, «Secure Coding in C and C++, Module 4, Dynamic Memory Management», 2010.
5. FreeRTOS: использование стека и проверка стека на переполнение.
6. FreeRTOS: практическое применение, часть 6 (устранение проблем).
7. FreeRTOS, STM32: отладка ошибок и исключений.
8. IAR C-SPY: предупреждение о переполнении стека.
9. Использование стека в IAR и файлы управления стеком.
10. Cortex: отдельный стек для ISR.

Информатика. 11 класс. Углубленный уровень. В 2 ч. Поляков К.Ю., Еремин Е.А. § 42. Стек, очередь, дек

Вопросы и задания

1. Что такое стек? Какие операции со стеком разрешены?
2. Как используется системный стек при выполнении программ?
3. Какие ошибки могут возникнуть при использовании стека?
4. В каких случаях можно использовать обычный массив для моделирования стека?
5. Как построить стек на основе динамического массива?
6. Почему при передаче стека в подпрограммы, приведённые в параграфе, соответствующий параметр должен быть изменяемым?
7. Что такое очередь? Какие операции она допускает?
8. Приведите примеры задач, в которых можно использовать очередь.

Подготовьте сообщение
а) «Моделирование стека и очереди в языке Си»
б) «Моделирование стека и очереди в языке Python»
в) «Моделирование очереди с помощью стеков»
г) «Очередь с приоритетом»

Задача

1. Напишите программу, которая «переворачивает» массив, записанный в файл, с помощью стека. Размер массива неизвестен. Все операции со стеком вынесите в отдельный модуль.

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

3. Напишите программу, которая проверяет правильность скобочного выражения с четырьмя видами скобок: (), [], {} и <>. Все операции со стеком вынесите в отдельный модуль.

*4. Найдите в литературе или в Интернете алгоритм перевода арифметического выражения из инфиксной формы в постфиксную и напишите программу, которая решает эту задачу.

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

*6. Перепишите программу из задачи 5 — используйте статический массив для организации очереди. Считайте, что в очереди может быть не более 100 элементов. Предусмотрите обработку ошибки «очередь переполнена».

*7. Напишите программу решения задачи о заливке области, помечая при этом точки, добавленные в очередь, чтобы не добавлять их повторно. В чём преимущества и недостатки такого алгоритма?

В программном обеспечении переполнение стека происходит, если указатель стека вызовов превышает границу стека . Стек вызовов может состоять из ограниченного объема адресного пространства , часто определяемого при запуске программы. Размер стека вызовов зависит от многих факторов, включая язык программирования, архитектуру компьютера, многопоточность и объем доступной памяти. Когда программа пытается использовать больше места, чем доступно в стеке вызовов (то есть, когда она пытается получить доступ к памяти за пределами стека вызовов, что по существу является переполнением буфера ), считается, что стек переполняется , что обычно приводит к ошибке. сбой программы. ^[1]

Причины

Бесконечная рекурсия

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

Пример бесконечной рекурсии в C .

интервал фу () {  

     вернуть фу (); 
}

Функция foo , когда она вызывается, продолжает вызывать себя, каждый раз выделяя дополнительное пространство в стеке, пока стек не переполнится, что приведет к ошибке сегментации . ^[2] Однако некоторые компиляторы реализуют оптимизацию хвостовых вызовов , позволяя выполнять бесконечную рекурсию определенного вида — хвостовую рекурсию — без переполнения стека. Это работает, потому что вызовы хвостовой рекурсии не занимают дополнительного места в стеке. ^[3]

Некоторые параметры компилятора C позволяют оптимизировать хвостовой вызов ; например, компиляция приведенной выше простой программы с использованием gcc с -O1приведет к ошибке сегментации, но не при использовании -O2или -O3, поскольку эти уровни оптимизации подразумевают параметр -foptimize-sibling-callsкомпилятора. ^[4] Другие языки, такие как Scheme , требуют, чтобы все реализации включали хвостовую рекурсию как часть языкового стандарта. ^[5]

Очень глубокая рекурсия

Рекурсивная функция, которая теоретически завершается, но на практике вызывает переполнение буфера стека вызовов, может быть исправлена ​​путем преобразования рекурсии в цикл и сохранения аргументов функции в явном стеке (вместо неявного использования стека вызовов). Это всегда возможно, потому что класс примитивно-рекурсивных функций эквивалентен классу вычислимых функций LOOP. Рассмотрим этот пример в C++ -подобном псевдокоде:

недействительная функция ( аргумент ) {   

  если ( условие ) 
    функция ( аргумент . следующий ); 

}

стек . нажать ( аргумент );
в то время как ( ! стек . пустой ()) 
{
  аргумент = стек . поп ();  
  если ( условие ) 
    стек . нажать ( аргумент . следующий );
}

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

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

int pow ( int base , int exp ) {     
    если ( ехр > 0 )   
        Возвращение базы * POW ( основание , ехр - 1 );      
    еще
        вернуть 1 ; 
}

int pow ( int base , int exp ) {     
    Возвращение pow_accum ( базовая , ехр , 1 );   
}

int pow_accum ( int base , int exp , int accum ) {       
    если ( ехр > 0 )   
        Возвращение pow_accum ( базовая , ехр - 1 , Accum * основание );       
    еще
        возврат аккума ; 
}

Обе pow(base, exp)приведенные выше функции вычисляют эквивалентный результат, однако функция слева может вызвать переполнение стека, поскольку для этой функции невозможна оптимизация хвостового вызова. Во время выполнения стек для этих функций будет выглядеть так:

пау ( 5 , 4 ) 
5 * пау ( 5 , 3 )   
5 * ( 5 * пау ( 5 , 2 ))     
5 * ( 5 * ( 5 * пау ( 5 , 1 )))       
5 * ( 5 * ( 5 * ( 5 * пау ( 5 , 0 ))))         
5 * ( 5 * ( 5 * ( 5 * 1 )))        
625

пау ( 5 , 4 ) 
pow_accum ( 5 , 4 , 1 )  
pow_accum ( 5 , 3 , 5 )  
pow_accum ( 5 , 2 , 25 )  
pow_accum ( 5 , 1 , 125 )  
pow_accum ( 5 , 0 , 625 )  
625

Обратите внимание, что функция слева должна хранить в своем стеке expряд целых чисел, которые будут умножены, когда рекурсия завершится и функция вернет 1. Напротив, функция справа должна хранить только 3 целых числа в любой момент времени и вычисляет промежуточный результат, который передается следующему вызову. Поскольку никакая другая информация за пределами текущего вызова функции не должна храниться, оптимизатор хвостовой рекурсии может «отбрасывать» предыдущие кадры стека, устраняя возможность переполнения стека.

Очень большие переменные стека

Другая основная причина переполнения стека возникает из-за попытки выделить в стеке больше памяти, чем может поместиться, например, путем создания переменных локального массива, которые слишком велики. По этой причине некоторые авторы рекомендуют, чтобы массивы размером более нескольких килобайт выделялись динамически, а не как локальная переменная. ^[6]

Пример очень большой переменной стека в C :

интервал фу () {  

     двойной х [ 1048576 ]; 
}

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

Переполнение стека усугубляется всем, что уменьшает эффективный размер стека данной программы. Например, та же программа, запущенная без нескольких потоков, может работать нормально, но как только многопоточность будет включена, программа рухнет. Это связано с тем, что большинство программ с потоками имеют меньше места в стеке на поток, чем программы без поддержки потоков. Поскольку ядра, как правило, многопоточные, людям, плохо знакомым с разработкой ядра , обычно не рекомендуется использовать рекурсивные алгоритмы или большие буферы стека. ^[7]

Смотрите также

• Переполнение буфера
• Стек вызовов
• Переполнение кучи
• Переполнение буфера стека
• Двойная ошибка

Ссылки

Внешние ссылки

• Причины, по которым 64-битным программам требуется больше стековой памяти