Jaki jest kierunek wzrostu stosów w większości nowoczesnych systemów?

102

Przygotowuję materiały szkoleniowe w języku C i chcę, aby moje przykłady pasowały do ​​typowego modelu stosu.

W jakim kierunku rozwija się stos C w systemach Linux, Windows, Mac OSX (PPC i x86), Solaris i najnowszych Uniksach?

Uri
źródło
3
A why downwards version: stackoverflow.com/questions/2035568/…
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功 Kwietnia

Odpowiedzi:

147

Wzrost stosu zwykle nie zależy od samego systemu operacyjnego, ale od procesora, na którym działa. Na przykład Solaris działa na platformie x86 i SPARC. Mac OSX (jak wspomniałeś) działa na PPC i x86. Linux działa na wszystkim, od mojego wielkiego honkin 'System Z w pracy po słaby mały zegarek na rękę .

Jeśli procesor zapewnia jakiś wybór, konwencja ABI / wywoływania używana przez system operacyjny określa, jakiego wyboru należy dokonać, jeśli chcesz, aby kod wywoływał kod innych osób.

Procesory i ich kierunek to:

  • x86: w dół.
  • SPARC: do wyboru. Standardowy ABI wykorzystuje down.
  • PPC: chyba w dół.
  • System z: na połączonej liście nie żartuję (ale nadal nie działa, przynajmniej dla zLinux).
  • ARM: do wyboru, ale Thumb2 ma kompaktowe kodowanie tylko dla dołu (LDMIA = przyrost po, STMDB = spadek przed).
  • 6502: dół (ale tylko 256 bajtów).
  • RCA 1802A: w dowolny sposób, z zastrzeżeniem implementacji SCRT.
  • PDP11: w dół.
  • 8051: w górę.

Pokazując mój wiek w tych ostatnich, 1802 był chipem używanym do kontrolowania wczesnych wahadłowców (podejrzewam, że wyczuwając, czy drzwi były otwarte, na podstawie mocy obliczeniowej, którą miał :-) i mojego drugiego komputera, COMX-35 ( po moim ZX80 ).

Szczegóły PDP11 zebrane stąd , 8051 szczegółów stąd .

Architektura SPARC wykorzystuje model rejestru przesuwnego okna. Widoczne architektonicznie szczegóły obejmują również okrągły bufor okien rejestrów, które są prawidłowe i przechowywane w pamięci podręcznej, z pułapkami, gdy przepełnia / niedomaga. Zobacz tutaj po szczegóły. Jak wyjaśnia podręcznik SPARCv8, instrukcje SAVE i RESTORE są jak instrukcje ADD plus obracanie okna rejestru. Użycie dodatniej stałej zamiast zwykłej ujemnej dałoby stos rosnący w górę.

Wspomniana wcześniej technika SCRT jest inną - 1802 używał niektórych lub szesnastu 16-bitowych rejestrów dla SCRT (standardowa technika wywołania i powrotu). Jednym z nich był licznik programu, możesz użyć dowolnego rejestru jako komputera z SEP Rninstrukcją. Jeden był wskaźnikiem stosu, a dwa były zawsze ustawione tak, aby wskazywały na adres kodu SCRT, jeden dla wywołania, jeden dla powrotu. Żaden rejestr nie był traktowany w szczególny sposób. Pamiętaj, że te szczegóły pochodzą z pamięci, mogą nie być całkowicie poprawne.

Na przykład, jeśli R3 był komputerem PC, R4 był adresem wywołania SCRT, R5 był adresem zwrotnym SCRT, a R2 był „stosem” (cudzysłowy, tak jak jest to zaimplementowane w oprogramowaniu), SEP R4ustawiłoby R4 jako komputer i uruchomił SCRT kod połączenia.

Następnie zapisałby R3 na "stosie" R2 (myślę, że R6 był używany do przechowywania tymczasowego), dostosowując go w górę lub w dół, przechwytywał dwa bajty następujące po R3, ładował je do R3, a następnie robił SEP R3i działał pod nowym adresem.

Aby powrócić, SEP R5wyciągnąłby stary adres ze stosu R2, dodałby do niego dwa (aby pominąć bajty adresu wywołania), załadowałby go do R3 i SEP R3rozpoczął wykonywanie poprzedniego kodu.

Początkowo bardzo trudno zawinąć głowę po całym kodzie opartym na stosie 6502/6809 / z80, ale nadal jest elegancki w stylu uderzania głową o ścianę. Jedną z największych cech sprzedaży chipa był również pełen zestaw 16 16-bitowych rejestrów, mimo że natychmiast straciłeś 7 z nich (5 dla SCRT, dwa dla DMA i przerwań z pamięci). Ach, triumf marketingu nad rzeczywistością :-)

System z jest właściwie dość podobny, używając swoich rejestrów R14 i R15 do wywołania / powrotu.

paxdiablo
źródło
3
Aby dodać do listy, ARM może rosnąć w dowolnym kierunku, ale może być ustawiony na jeden lub drugi przez określoną implementację krzemu (lub można go pozostawić do wyboru przez oprogramowanie). Nieliczni, z którymi miałem do czynienia, zawsze byli w trybie dorastania.
Michael Burr
1
W małym fragmencie świata ARM, który widziałem do tej pory (ARM7TDMI), stos jest całkowicie obsługiwany w oprogramowaniu. Adresy zwrotne są przechowywane w rejestrze, który jest zapisywany przez oprogramowanie w razie potrzeby, a instrukcje przed / po inkrementacji / dekrementacji umożliwiają umieszczenie tego i innych rzeczy na stosie w dowolnym kierunku.
starblue
1
Jeden HPPA, stos urósł! Dość rzadki wśród stosunkowo nowoczesnych architektur.
tml
2
Dla ciekawskich, oto dobre źródło informacji o tym, jak działa stos w systemie z / OS: www-03.ibm.com/systems/resources/Stack+and+Heap.pdf
Dillon Cower
1
Dzięki @paxdiablo za zrozumienie. Czasami ludzie traktują to jako osobistą zniewagę, kiedy robisz taki komentarz, zwłaszcza gdy jest to starszy. Wiem tylko, że jest różnica, ponieważ w przeszłości popełniłem ten sam błąd. Dbać.
CasaDeRobison
23

W C ++ (przystosowanym do C) stack.cc :

static int
find_stack_direction ()
{
    static char *addr = 0;
    auto char dummy;
    if (addr == 0)
    {
        addr = &dummy;
        return find_stack_direction ();
    }
    else
    {
        return ((&dummy > addr) ? 1 : -1);
    }
}
jfs
źródło
14
Wow, minęło dużo czasu, odkąd widziałem słowo kluczowe „auto”.
paxdiablo
9
(& dummy> addr) jest niezdefiniowane. Wynik podania dwóch wskaźników do operatora relacyjnego jest definiowany tylko wtedy, gdy dwa wskaźniki wskazują na tę samą tablicę lub strukturę.
sigjuice
2
Próba zbadania układu własnego stosu - coś, czego C / C ++ w ogóle nie określa - jest „nie do przenoszenia”, więc nie przejmowałbym się tym. Wygląda jednak na to, że ta funkcja będzie działać poprawnie tylko raz.
ephemient
9
Nie ma potrzeby używania staticdo tego celu. Zamiast tego możesz przekazać adres jako argument do wywołania rekurencyjnego.
R .. GitHub ZATRZYMAJ SIĘ NA LODZIE
5
Dodatkowo, za pomocą static, jeśli to nazwać więcej niż jeden raz, kolejne połączenia może nie ...
Christopher Dodd
7

Zaletą zmniejszania się jest to, że w starszych systemach stos znajdował się zazwyczaj na szczycie pamięci. Programy zazwyczaj zapełniają pamięć zaczynając od dołu, więc ten rodzaj zarządzania pamięcią zminimalizował potrzebę mierzenia i umieszczania dna stosu w rozsądnym miejscu.

poseł.
źródło
3
To nie „zaleta”, tak naprawdę tautologia.
Markiz Lorne
1
To nie jest tautologia. Chodzi o to, aby dwa rosnące obszary pamięci nie przeszkadzały (chyba że pamięć i tak jest pełna), jak wskazał @valenok.
YvesgereY
6

Stos rośnie na x86 (zdefiniowany przez architekturę, wskaźnik stosu przyrostów pop, dekrementy wypychania).

Michael
źródło
5

W MIPS i wielu nowoczesnych architekturach RISC (takich jak PowerPC, RISC-V, SPARC ...) nie ma instrukcji pushi popinstrukcji. Te operacje są jawnie wykonywane przez ręczne dostosowanie wskaźnika stosu, a następnie załadowanie / zapisanie wartości w stosunku do dostosowanego wskaźnika. Wszystkie rejestry (z wyjątkiem rejestru zerowego) mają zastosowanie ogólne, więc teoretycznie każdy rejestr może być wskaźnikiem stosu, a stos może rosnąć w dowolnym kierunku, jaki chce programista

To powiedziawszy, stos zwykle rośnie w większości architektur, prawdopodobnie w celu uniknięcia przypadku, gdy stos i dane programu lub dane sterty rosną i kolidują ze sobą. Jest też świetne powody adresowania, o których wspomina odpowiedź sh- . Kilka przykładów: MIPS ABI rośnie w dół i używa $29(AKA $sp) jako wskaźnika stosu, RISC-V ABI również rośnie w dół i używa x2 jako wskaźnika stosu

W Intel 8051 stos rośnie, prawdopodobnie dlatego, że przestrzeń pamięci jest tak mała (128 bajtów w oryginalnej wersji), że nie ma sterty i nie trzeba umieszczać stosu na wierzchu, aby był oddzielony od rosnącej sterty od spodu

Więcej informacji na temat wykorzystania stosu w różnych architekturach można znaleźć pod adresem https://en.wikipedia.org/wiki/Calling_convention

Zobacz też

phuclv
źródło
2

Tylko mały dodatek do innych odpowiedzi, które z tego, co widzę, nie poruszyły tego punktu:

Gdy stos rośnie w dół, wszystkie adresy w stosie mają dodatnie przesunięcie względem wskaźnika stosu. Nie ma potrzeby stosowania ujemnych przesunięć, ponieważ wskazywałyby one tylko na niewykorzystane miejsce na stosie. Upraszcza to dostęp do lokalizacji stosu, gdy procesor obsługuje adresowanie względne w stosie.

Wiele procesorów ma instrukcje, które pozwalają na dostęp z przesunięciem tylko dodatnim względem jakiegoś rejestru. Jest wśród nich wiele współczesnych architektur, a także kilka starych. Na przykład ARM Thumb ABI zapewnia dostęp względny do stosu z dodatnim przesunięciem zakodowanym w pojedynczym 16-bitowym słowie instrukcji.

Gdyby stos rósł w górę, wszystkie przydatne przesunięcia względem wskaźnika stosu byłyby ujemne, co jest mniej intuicyjne i mniej wygodne. Jest to również sprzeczne z innymi zastosowaniami adresowania względnego rejestrów, na przykład do uzyskiwania dostępu do pól struktury.

sh-
źródło
2

W większości systemów stos rośnie, a mój artykuł na https://gist.github.com/cpq/8598782 wyjaśnia, DLACZEGO rośnie. To proste: jak rozmieścić dwa rosnące bloki pamięci (sterta i stos) w stałej porcji pamięci? Najlepszym rozwiązaniem jest umieszczenie ich na przeciwnych końcach i pozwolenie, aby rosły ku sobie.

valenok
źródło
to wydaje się teraz martwe :(
Ven
@Ven - I can get to it
Brett Holman
1

Rośnie, ponieważ pamięć przydzielona programowi ma „stałe dane”, czyli kod samego programu na dole, a następnie stertę w środku. Potrzebujesz innego stałego punktu, z którego będziesz odnosić się do stosu, dzięki czemu pozostaniesz na szczycie. Oznacza to, że stos rośnie, aż potencjalnie przylega do obiektów na stercie.

Kai
źródło
0

To makro powinno wykryć to w czasie wykonywania bez UB:

#define stk_grows_up_eh() stk_grows_up__(&(char){0})
_Bool stk_grows_up__(char *ParentsLocal);

__attribute((__noinline__))
_Bool stk_grows_up__(char *ParentsLocal) { 
    return (uintptr_t)ParentsLocal < (uintptr_t)&ParentsLocal;
}
PSkocik
źródło