Меню

Паскаль ошибка переполнения стека

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

Unit stroka;
Interface
Function MoveEnd(s:string; t:byte):string;
Function MyPos(s1,s2:string):integer;
Function WordN(s:string):string;
Function CountWord(s:string):integer;
Function SovPad(s1,s2:string):boolean;
 
Implementation
 
Function MoveEnd(s:string; t:byte):string;
Var n,j,i:byte;
     numb:array[1..20] of byte;
     zn: set of char;
     s1:array [1..20] of string;
Begin
zn:=['.',',',' ',';',':'];
if not (s[length(s)] in zn)
then
s:=s+' ';
n:=length(s);
j:=1;
for i:=1 to n do
begin
  s1[j]:=s1[j]+s[i];
   if s[i] in zn then
   begin
   numb[j]:=i-length(s[j])+1;
   inc(j);
   end;
end;
dec(j);
Delete(s,numb[t],length(s1[t]));
s:=s+s1[t];
MoveEnd:=s;
end;
 
Function MyPos(s1,s2:string):integer;
begin
MyPos:=pos(s1,s2);
end;
 
 
Function WordN(s:string):string;
Var wn: array[1..100] of string;
    w:string;
    i,j,q,len:integer;
Begin
New(len);
len:=length(s);
i:=1;
while i<=len do
begin
if (UpCase(s[i]) >= 'a') and (Upcase(s[i]) <='z') then
begin
w:=UpCase(s[i]);
i:=i+1;
    while (i <= len) and ((Upcase(s[i]) >= 'a') and (Upcase(s[i]) <= 'z')) do
    begin
    w:=w+Upcase(s[i]);
    i:=i+1;
    end;
       j:=1;
       while (j<=q) and (w<>wn[j]) do
           j:=j+1;
       if j>q then
      begin
            q:=q+1;
            wn[q]:=w;
      end
  else
  i:=i+1;
WordN:=wn[i];
end;
end;
end;
 
 
Function CountWord(s:string):integer;
Var i,kol,len:integer;
begin
kol:=0;
len:=length(s);
s:=s+'';
for i:=1 to len do
begin
if s[i]='' then
kol:=kol+1;
end;
CountWord:=kol;
end;
 
 Function SovPad(s1,s2:string):boolean;
Var i,j:integer;
Begin
  for j:=1 to length(s1) do
  for i:=1 to length(s2) do
    begin
      if not (s1[i] in ['a'..'z','A'..'Z']) then delete(s1,i,1);
      if not (s2[i] in ['a'..'z','A'..'Z']) then delete(s2,i,1);
    end;
if length(s1)<>length(s2) then SovPad:=false else
   for i:=1 to length(s1) do
     if upcase(s1[i])<>upcase(s2[i]) then SovPad:=false;
     end;
      end.
 
[size="1"][color="grey"][I]Добавлено через 44 секунды[/I][/color][/size]
А вот программа, пока не готовая до конца...
 
 
Program Text;
Uses stroka;
Var s,s1,s2:string;
      k,i,p: integer;
Begin
writeln('Vvedite stroku: ');
readln(s);
k:=1;
s1:=MoveEnd(s,k);
p:=CountWord(s);
i:=p;
s2:=WordN(s);
writeln('resultat: ',s1);
end.
Источник

Приложения написанные на Free Pascal могут генерировать ошибку времени выполнения (Run Time Error) когда в программе обнаруживаются определённые аварийные состояния . Этот документ содержит список возможных ошибок и описание их возможных причин.

1 Invalid function number (Неправильный номер функции)

Была попытка неправильного вызова системной функции.

2 File not found (Файл не найден)

Генерируется при попытке перенаименования, стирания или открытия несуществующего файла.

3 Path not found (Путь(директория) не найден)

Генерируется файловой системой когда путь не существует или неправелен.
Также генерируется при попытке получить доступ к несуществующему файлу.

4 Too many open files (Слишком много файлов открыто)

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

5 File access denied (В доступе к файлу — отказано)

Было запрешено получение доступа к файлу. Эта ошибка может произойти по нескольким причинам:

  • При попытке открыть файл, предназначенный только для чтения или в деиствительности являющиёся директорией, для записи.

  • В данный момент занят или заблокирован другим процессом.

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

  • При попытке чтения из файла, открытого только для записи.

  • При попытке записи в файл, открытый только для чтения.

  • При попытке удалить директорию или файл, когда это не возможно.

  • При неимении прав на доступ к данному файлу.

6 Invalid file handle (Неправильный хэндл файла)

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

12 Invalid file access code (Неправильные ключи доступа к файлу)

Генерируется когда процедуры reset или rewrite вызываются с неправильным параметром FileMode.

15 Invalid drive number (Неправильный номер диска)

Генерируется когда в функции Getdir или ChDir был передан неправильный номер диска.

16 Cannot remove current directory (Невозможно удалить текущую директорию)

Генерируется при попытке удалить текущую директорию.

17 Cannot rename across drives (Можно переименовывать файлы только в пределах одного диска)

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

100 Disk read error (Ошибка чтения с диска)

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

101 Disk write error (Ошибка записи на диск)

Генерируется когда Вы пытаетесь записать данные на переполненый диск.

102 File not assigned (Файл не определён)

Генерируется функциями Reset, Rewrite, Append, Rename и Erase, При передаче в них файловой переменной, для которой не была выполнена функция AssignFile.

103 File not open (Файл не открыт)

Генерируется следующими функциями : Close, Read, Write, Seek, EOf, FilePos, FileSize, Flush, BlockRead, и BlockWrite если файл не был открыт.

104 File not open for input (Файл не открыт для чтения)

Генерируется функциями Read, BlockRead, Eof, Eoln, SeekEof и SeekEoln если файл не был открыт при помощи Reset.

105 File not open for output (Файл не открыт для записи)

Генерируется функцией write если текстовый файл не был открыт при помощи Rewrite.

106 Invalid numeric format(Неправильный числовой формат)

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

150 Disk is write-protected (Диск защищён от записи)

(Критическая ошибка)

151 Bad drive request struct length (Неправильная длина структуры запроса)

(Критическая ошибка)

152 Drive not ready (Устройство не готово)

(Критическая ошибка)

154 CRC error in data (Ошибка контрольной суммы в данных)

(Критическая ошибка)

156 Disk seek error (Ошибка низкоуровнего поиска на диске)

(Критическая ошибка)

157 Unknown media type (Неизвестный тип …)

(Критическая ошибка)

158 Sector Not Found (Сектор не найден)

(Критическая ошибка)

159 Printer out of paper (Нет бумаги в принтере)

(Критическая ошибка)

160 Device write fault (Сбой записи устройства)

(Критическая ошибка)

161 Device read fault (Сбой чтения устройства)

(Критическая ошибка)

162 Hardware failure (Сбой железа)

(Критическая ошибка)

200 Division by zero (Деление на ноль)

Приложение пыталось разделить число на ноль.

201 Range check error (Ошибка проверки границ)

Если вы компилировали прогамму с включённой провереой границ, Вы можете получить эту ошибку в следующих случаях:

  1. Массив был вызван с индексом, выходящим за декларированые пределы.

  2. Попытка присвоить значение переменной, выходящее за декларированые границы (для instance и enumerated типов).

202 Stack overflow error (Переполнение стека)

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

203 Heap overflow error (Переполнение кучи)

Размер кучи превысил максимально возможный размер. Генерируется при попытке выделить память непосредственно функциями New, GetMem и ReallocMem, или когда экземпляр класса или объекта создаётся и памяти не достаточно. Пожалуйста учтите что, по умолчанию, Free Pascal поддерживает увеличение кучи, то есть, если необходимо, будет произведена попытка её увеличения. Как бы то ни было, если размер кучи превысил максимально допустимый системой и
железом, то Вы получите эту ошибку.

204 Invalid pointer operation (Непрваильная операция с указателем)

Будет сгенерирована при вызове функций Dispose или Freemem с неправильным указателем (чаще всего, Nil)

205 Floating point overflow (Максимальная границы числа с плавающей точкой)

Вы попытались использовать или создать слишком большое число с плавающей точкой.

206 Floating point underflow (Минимальная граница числа с плавающей точкой)

Вы попытались использовать или создать слишком маленькое число с плавающей точкой.

207 Invalid floating point operation (Неправильная операция над числами с плавающей точкой)

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

210 Object not initialized (Объект не инициализирован)

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

211 Call to abstract method (Попытка вызова абстрактного метода)

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

212 Stream registration error (Ошибка регистрации потока)

Генерируется когда неправильный тип регистрируется в модуле objects.

213 Collection index out of range (Индекс элемента коллекции выходит за допустимые границы)

Генерируется когда Вы попытались обратиться к элементу коллекции с выходящим за допустимые границы индексом (модуль objects).

214 Collection overflow error (Переполнение коллекции)

Размер коллекции превысил максимально допустимый размер, а Вы попытались добавить новый элемент (модуль objects).

215 Arithmetic overflow error (Арифметическое переполнение)

Эта ошибка генерируется когда результат операции превысил допустимые границы. В отличие to Turbo Pascal, эта ошибка генерируется только для 32-bit и 64-bit арифметических переполнений. Это происходит согласно тому, что все операнды конвертируются в 32-bit или 64-bit, до того как производить вычисления.

216 General Protection fault (GP Ошибка защиты памяти)

Приложение попыталось обратиться к недопустимому участку памяти. Это может быть вызвано следующими причинами:

  1. Попытка получить разуказатель для nil.

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

217 Unhandled exception occurred (Произошо неизвестное исключение)

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

219 Invalid typecast (Неправильное приведение типов)

Генерируется когда недопустимое приведение типов производится над классом используя оператор as. Эта ошибка также генерируется, когда объект или класс приводится к недопустимому объекту или классу, и виртуальный метод этого объекта или класса вызывается. Эта последняя ошибка детектируется только с использованием опции -CR компилятора.

227 Assertion failed error (Сбой утверждения)

Утверждение провалено, и процедурная переменная AssertErrorProc не была уcтановлена.

Источник

The following code for implementing AVL-tree insertion & deletion gives error #202 (stack overflow).

Source code looks like this:

program Avl_generator; uses Crt;

type p_Avl = ^Avl_node;
 Avl_node = record
 key: integer;
 l, r, par: p_Avl; {pointers to left child, right child, parent}
 bal, h: integer {balance factor, height}
 end;

procedure init(var root: p_Avl); begin new(root); root:=nil end;

function get_height(var n: p_Avl): integer;
begin
  if(n=nil) then get_height:=-1 else get_height:=n^.h;
end;

procedure reheight(var n: p_Avl); {refresh the height variable}
begin
  if(n<>nil) then
  begin
    if(get_height(n^.r)>get_height(n^.l)) then n^.h:=1+get_height(n^.r)
      else n^.h:=1+get_height(n^.l);
  end;
end;

procedure set_balance(var n: p_Avl); begin reheight(n); n^.bal:=get_height(n^.r)-get_height(n^.l); end; {refresh the balance factor}

function rotate_l(var a: p_Avl): p_Avl; {left rotation, a is pivot}
var b: p_Avl;
begin
  b := a^.r;
  b^.par := a^.par;
  a^.r := b^.l;
  if(a^.r<>nil) then a^.r^.par := a;
  b^.l := a;
  a^.par := b;
  if(b^.par<>nil) then
    if(b^.par^.r=a) then b^.par^.r := b
      else b^.par^.l := b;
  set_balance(a); set_balance(b);
  rotate_l := b;
end;

function rotate_r(var a: p_Avl): p_Avl; {right rotation, a is pivot}
var b: p_Avl;
begin
  b := a^.l;
  b^.par := a^.par;
  a^.l := b^.r;
  if(a^.l<>nil) then a^.l^.par := a;
  b^.r := a;
  a^.par := b;
  if(b^.par<>nil) then
    if(b^.par^.r=a) then b^.par^.r := b
      else b^.par^.l := b;
  set_balance(a); set_balance(b);
  rotate_r := b;
end;

function rotate_l_r(var a: p_Avl): p_Avl; {left & right rotation, a is pivot}
begin
  a^.l := rotate_l(a^.l);
  rotate_l_r := rotate_r(a);
end;

function rotate_r_l(var a: p_Avl): p_Avl; {right & left rotation, a is pivot}
begin
  a^.r := rotate_r(a^.r);
  rotate_r_l := rotate_l(a);
end;

procedure rebalance(var root: p_Avl; var n: p_Avl); {refresh balance factors and see if sub-trees need rotating}
begin
  set_balance(n);
  if(n^.bal=-2) then
  begin
    if(get_height(n^.l^.l)>=get_height(n^.l^.r)) then n:=rotate_r(n)
      else n:=rotate_l_r(n);
  end
  else if(n^.bal=2) then
  begin
    if(get_height(n^.r^.r)>=get_height(n^.r^.l)) then n:=rotate_l(n)
      else n:=rotate_r_l(n);
  end;
  if(n^.par<>nil) then rebalance(root, n^.par) else root:=n; {recursion here}
end;

procedure insert(var root: p_Avl; what: integer);
var found: boolean;
  pre_tmp, tmp: p_Avl;
begin
  found:=false; tmp:=root; pre_tmp:= nil;
  while(tmp<>nil) and not found do
    if(tmp^.key=what) then found:=true
      else if(tmp^.key>what) then begin pre_tmp:=tmp; tmp:=tmp^.l end
      else begin pre_tmp:=tmp; tmp:=tmp^.r end;

  if not found then
  begin
    new(tmp); tmp^.key:=what;
    tmp^.l:=nil; tmp^.r:=nil; tmp^.par:=pre_tmp; tmp^.h:=0; tmp^.bal:=0;
    if(pre_tmp=nil) then root:=tmp
      else
      begin
        if(pre_tmp^.key>what) then pre_tmp^.l:=tmp else pre_tmp^.r:=tmp;
        rebalance(root, pre_tmp);
      end;
  end;
end;

procedure delete(var root: p_Avl; what: integer);
var found: boolean;
  tmp, pre_tmp, act, pre_act: p_Avl;
begin
  found:=false; tmp:=root; pre_tmp:=nil;
  while(tmp<>nil) and not found do
  begin
    if(tmp^.key=what) then found:=true
      else if(tmp^.key>what) then
        begin pre_tmp:=tmp; tmp:=tmp^.l end
      else
        begin pre_tmp:=tmp; tmp:=tmp^.r end;
    if found then
      if(tmp^.l=nil) then
      begin
        if(pre_tmp=nil) then root:=tmp^.r
          else if(pre_tmp^.key>what) then pre_tmp^.l:=tmp^.r
          else pre_tmp^.r:=tmp^.r;
        dispose(tmp); rebalance(root,pre_tmp);
      end else if(tmp^.r=nil) then
      begin
        if(pre_tmp=nil) then root:=tmp^.l
          else if(pre_tmp^.key>what) then pre_tmp^.l:=tmp^.l
          else begin pre_tmp^.r:=tmp^.l end;
        dispose(tmp); rebalance(root,pre_tmp);
      end else
      begin
        act:=tmp^.l; pre_act:=nil;
        while(act^.r<>nil) do begin pre_act:=act; act:=act^.r end;
        tmp^.key:=act^.key;
        if(pre_act=nil) then begin tmp^.l:=act^.l; dispose(act); rebalance(root,tmp) end
          else begin pre_act^.r:=act^.l; dispose(act); rebalance(root,pre_act) end;
      end;
  end;
end;

var Avl_tree: p_Avl;
begin
  init(Avl_tree);
  insert(Avl_tree,1);
  insert(Avl_tree,2);
  insert(Avl_tree,3);
  insert(Avl_tree,4);
  insert(Avl_tree,5);
  writeln(get_path(Avl_tree, 5));
  repeat until KeyPressed;
end.

This compiles fine (Turbo Pascal 7.0). When I run the code, though, the error occurs in the rotate_l procedure which is called after the third insertion (whereupon balance factor of the root node =2.

I checked some Java & C++ implementations and the rotation methods there seemed quite similar to mine, therefore I don’t know where the problem is..?

Источник

The following code for implementing AVL-tree insertion & deletion gives error #202 (stack overflow).

Source code looks like this:

program Avl_generator; uses Crt;

type p_Avl = ^Avl_node;
 Avl_node = record
 key: integer;
 l, r, par: p_Avl; {pointers to left child, right child, parent}
 bal, h: integer {balance factor, height}
 end;

procedure init(var root: p_Avl); begin new(root); root:=nil end;

function get_height(var n: p_Avl): integer;
begin
  if(n=nil) then get_height:=-1 else get_height:=n^.h;
end;

procedure reheight(var n: p_Avl); {refresh the height variable}
begin
  if(n<>nil) then
  begin
    if(get_height(n^.r)>get_height(n^.l)) then n^.h:=1+get_height(n^.r)
      else n^.h:=1+get_height(n^.l);
  end;
end;

procedure set_balance(var n: p_Avl); begin reheight(n); n^.bal:=get_height(n^.r)-get_height(n^.l); end; {refresh the balance factor}

function rotate_l(var a: p_Avl): p_Avl; {left rotation, a is pivot}
var b: p_Avl;
begin
  b := a^.r;
  b^.par := a^.par;
  a^.r := b^.l;
  if(a^.r<>nil) then a^.r^.par := a;
  b^.l := a;
  a^.par := b;
  if(b^.par<>nil) then
    if(b^.par^.r=a) then b^.par^.r := b
      else b^.par^.l := b;
  set_balance(a); set_balance(b);
  rotate_l := b;
end;

function rotate_r(var a: p_Avl): p_Avl; {right rotation, a is pivot}
var b: p_Avl;
begin
  b := a^.l;
  b^.par := a^.par;
  a^.l := b^.r;
  if(a^.l<>nil) then a^.l^.par := a;
  b^.r := a;
  a^.par := b;
  if(b^.par<>nil) then
    if(b^.par^.r=a) then b^.par^.r := b
      else b^.par^.l := b;
  set_balance(a); set_balance(b);
  rotate_r := b;
end;

function rotate_l_r(var a: p_Avl): p_Avl; {left & right rotation, a is pivot}
begin
  a^.l := rotate_l(a^.l);
  rotate_l_r := rotate_r(a);
end;

function rotate_r_l(var a: p_Avl): p_Avl; {right & left rotation, a is pivot}
begin
  a^.r := rotate_r(a^.r);
  rotate_r_l := rotate_l(a);
end;

procedure rebalance(var root: p_Avl; var n: p_Avl); {refresh balance factors and see if sub-trees need rotating}
begin
  set_balance(n);
  if(n^.bal=-2) then
  begin
    if(get_height(n^.l^.l)>=get_height(n^.l^.r)) then n:=rotate_r(n)
      else n:=rotate_l_r(n);
  end
  else if(n^.bal=2) then
  begin
    if(get_height(n^.r^.r)>=get_height(n^.r^.l)) then n:=rotate_l(n)
      else n:=rotate_r_l(n);
  end;
  if(n^.par<>nil) then rebalance(root, n^.par) else root:=n; {recursion here}
end;

procedure insert(var root: p_Avl; what: integer);
var found: boolean;
  pre_tmp, tmp: p_Avl;
begin
  found:=false; tmp:=root; pre_tmp:= nil;
  while(tmp<>nil) and not found do
    if(tmp^.key=what) then found:=true
      else if(tmp^.key>what) then begin pre_tmp:=tmp; tmp:=tmp^.l end
      else begin pre_tmp:=tmp; tmp:=tmp^.r end;

  if not found then
  begin
    new(tmp); tmp^.key:=what;
    tmp^.l:=nil; tmp^.r:=nil; tmp^.par:=pre_tmp; tmp^.h:=0; tmp^.bal:=0;
    if(pre_tmp=nil) then root:=tmp
      else
      begin
        if(pre_tmp^.key>what) then pre_tmp^.l:=tmp else pre_tmp^.r:=tmp;
        rebalance(root, pre_tmp);
      end;
  end;
end;

procedure delete(var root: p_Avl; what: integer);
var found: boolean;
  tmp, pre_tmp, act, pre_act: p_Avl;
begin
  found:=false; tmp:=root; pre_tmp:=nil;
  while(tmp<>nil) and not found do
  begin
    if(tmp^.key=what) then found:=true
      else if(tmp^.key>what) then
        begin pre_tmp:=tmp; tmp:=tmp^.l end
      else
        begin pre_tmp:=tmp; tmp:=tmp^.r end;
    if found then
      if(tmp^.l=nil) then
      begin
        if(pre_tmp=nil) then root:=tmp^.r
          else if(pre_tmp^.key>what) then pre_tmp^.l:=tmp^.r
          else pre_tmp^.r:=tmp^.r;
        dispose(tmp); rebalance(root,pre_tmp);
      end else if(tmp^.r=nil) then
      begin
        if(pre_tmp=nil) then root:=tmp^.l
          else if(pre_tmp^.key>what) then pre_tmp^.l:=tmp^.l
          else begin pre_tmp^.r:=tmp^.l end;
        dispose(tmp); rebalance(root,pre_tmp);
      end else
      begin
        act:=tmp^.l; pre_act:=nil;
        while(act^.r<>nil) do begin pre_act:=act; act:=act^.r end;
        tmp^.key:=act^.key;
        if(pre_act=nil) then begin tmp^.l:=act^.l; dispose(act); rebalance(root,tmp) end
          else begin pre_act^.r:=act^.l; dispose(act); rebalance(root,pre_act) end;
      end;
  end;
end;

var Avl_tree: p_Avl;
begin
  init(Avl_tree);
  insert(Avl_tree,1);
  insert(Avl_tree,2);
  insert(Avl_tree,3);
  insert(Avl_tree,4);
  insert(Avl_tree,5);
  writeln(get_path(Avl_tree, 5));
  repeat until KeyPressed;
end.

This compiles fine (Turbo Pascal 7.0). When I run the code, though, the error occurs in the rotate_l procedure which is called after the third insertion (whereupon balance factor of the root node =2.

I checked some Java & C++ implementations and the rotation methods there seemed quite similar to mine, therefore I don’t know where the problem is..?

Источник

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

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

Определение

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

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

Стек программы — это специальная области памяти, организованная по принципу очереди 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».

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

Источник

0 0 голоса
Рейтинг статьи
Подписаться
Уведомить о
guest

0 комментариев
Старые
Новые Популярные
Межтекстовые Отзывы
Посмотреть все комментарии

А вот еще интересные материалы:

  • Яшка сломя голову остановился исправьте ошибки
  • Ясность цели позволяет целеустремленно добиваться намеченного исправьте ошибки
  • Ясность цели позволяет целеустремленно добиваться намеченного где ошибка
  • Паскаль ошибка ожидалось описание или begin
  • Паскаль ошибка ожидалось имя переменной

    • ➤