Limit stosu

10

Niedawno przetestowałem limit stosu na trzech urządzeniach z różnymi systemami operacyjnymi (przez limit rozumiem maksymalną liczbę poziomów, jaką może mieć stos), i zauważyłem, że za każdym razem, gdy osiągam 2 ^ 16 poziomów, daje mi to błąd przepełnienia, a gdy wstawię 2 ^ 16-1, działa poprawnie.

Więc moje pytanie brzmi - czy to prawda? Czy stos ma z definicji maksymalny limit 2 ^ 16-1, czy zależy to od systemu operacyjnego?

Anonim
źródło
5
here i mean by limit the maximum number of levels that can the stack havejaki jest poziom
tkausl
3
Jak to testujesz? Czy używasz 2-bajtowych (dword) jako danych wejściowych?
pro3carp3
6
Jakiego języka programowania używasz? Tak ostry limit przy stałej liczbie wskazuje, że jest to celowe ograniczenie przez środowisko wykonawcze specyficzne dla języka, a nie przez rozmiar stosu przydzielonego przez system operacyjny. Na przykład wydaje się, że python domyślnie wymusza limit 1000, aby zapobiec trafieniu prawdziwego przepełnienia stosu (odzyskiwanie po przepełnieniu stosu jest trudne)
CodesInChaos

Odpowiedzi:

20

Jest silnie specyficzny dla systemu operacyjnego (i specyficzny dla komputera), aw niektórych systemach operacyjnych masz kilka sposobów na skonfigurowanie (a nawet zwiększenie) limitu. Jest nawet specyficzny dla kompilatora (lub specyficzny dla implementacji twojego języka programowania), ponieważ niektóre kompilatory (w tym najnowszy GCC dla pewnego ograniczonego rodzaju kodu C) są w stanie zoptymalizować niektóre wywołania tail .

(niektóre specyfikacje języka programowania wymagają optymalizacji połączeń ogonowych, np. R5RS )

Nie jestem pewien, czy twoje pytanie ma sens (a na pewno nie limit 2 16 ). Na moim komputerze z systemem Linux (Debian / Sid / x86-64, jądro Linux 4.9, 32 GB pamięci RAM, Intel i5-4690S) mogę mieć stos wywołań do 8 megabajtów (i mógłbym zwiększyć ten limit, jeśli naprawdę chciałbym ).

Wielowątkowość i ASLR sprawiają, że twoje pytanie jest znacznie bardziej złożone . Zobacz np. Pthread_attr_setstack (3) . Przeczytaj także o podzielonych stosach (często używanych przez implementacje Go ) oraz o stylu przekazywania kontynuacji . Zobacz także odpowiedź.

Za to, co jest warte, wypróbowałem następujący kod C99 (a także C11):

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

void recfun(int x, int d) {
  printf("start recfun x=%d d=%d\n", x, d);
  fflush(NULL);
  if (d>0)
    recfun(x+1, d-1);
  printf("end recfun x=%d d=%d\n", x, d);
}

int main(int argc, char**argv) {
  int md = argc>1?atoi(argv[1]):10000;
  printf ("start md=%d\n", md);
  recfun(0, md);
  printf("end md=%d clock=%ld µs\n", md, clock());
}    
// eof recur.c

i mogłem uruchomić ten recurprogram (skompilowany z GCC 6 as gcc -Wall -O recur.c -o recur) jako recur 161000 (znacznie powyżej limitu 2 16 ). Z recur 256000tym też działało. Z recur 456000awarią (z przepełnieniem stosu dla poziomu x=272057). Nie mam cierpliwości do innych testów. Wypróbuj to na swoim komputerze. Nie zapomnij poprosić o optymalizację.

Zasadą (dla komputerów stacjonarnych, laptopów, tabletów) może być utrzymywanie stosu połączeń poniżej jednego megabajta.

Przekazując również -fstack-usage do gcc , otrzymuję następujący recur.suplik (liczby są w bajtach, zgodnie z intuicją mojego stosu 8 Mb; nie zapomnij mainramki wywołania, a co ważniejsze, początkowego układu stosu, instalowanego przez jądro podczas wykonywania exec (2) ) ..., dla crt0 ):

 recur.c:5:10:recfun    32  static
 recur.c:13:9:main  16  static

PS. Moje Arduino ma Atmega328 z zaledwie 2 KB pamięci RAM, więc na pewno nie będzie tak wiele. Wydaje mi się, że tylko kilkaset ramek stosu jest co najwyżej praktycznie możliwe na Arduinos.

Basile Starynkevitch
źródło
3

Rozmiar stosu dla głównego wątku procesu Windows jest ustawiany przez konsolidator. Domyślnie jest to 1 MB, ale można go zmienić za pomocą przełącznika / STACK. Wątki utworzone później mogą korzystać z parametru dwStackSize funkcji CreateThread.

Więc ... jeśli testujesz różne systemy operacyjne Windows, wszystkie mają ten sam domyślny rozmiar stosu od co najmniej NT4.0.

Eric
źródło