Dzisiejsza architektura komputerów oparta jest o stos (stack). Widujemy często terminy takie jak stack overflow, buffer overflow, segmentation fault, czy architektura Von Neumanna. W tym artykule omówimy stos, jego wykorzystanie oraz zaimplementujemy drobne programy utrwalające jego zrozumienie.
Stos
LIFO
Stos to struktura danych, na którą możemy odkładać dane i dane z niej pobierać. Jest to kolejka LIFO (last in, first out). Cokolwiek wchodzi jako ostatnie, jest pierwszym do pobrania. Na stosie operujemy jedynie na ostatnim elemencie. PUSH i POP. Nie możemy sięgać wgłąb stosu. Dydaktycy często używają analogii stosu talerzy: odkładamy talerz na stos (PUSH), pobieramy od góry (POP). Próba pobrania talerza ze środka spowodowałaby "wywrotkę".
Stos w komputerze
W komputerach stos to pamięć, na którą odkładamy instrukcje do wykonania przez procesor. Procesor pobiera kolejne instrukcje ze stosu i kolejno wykonuje. Istotą i konsekwencją architektury Von Neumanna jest to, że na stosie umieszczamy zarówno instrukcje, jak i dane. W komputerach wszystko jest liczbą, dane mają swoje rozmiary. Jeśli w programie nie dopilnujemy tych rozmiarów, to może się zdarzyć, że procesor zdejmie ze stosu dane, które nie są instukcjami. Jeśli wykorzystując błąd programisty udałoby się nam podstawić w miejsce tych danych własne instrukcje, to moglibyśmy przejąć sterowanie programem. Tak działają często exploity.
Procesor porusza się po stosie przechowując we własnym zakresie różne pomocnicze wskaźniki (np. stack pointer, base pointer). Kiedy wywołujemy funkcję, to na stos trafiają jej argumenty oraz instrukcja wywołania/skoku do adresu tej funkcji. Procesor zbiera te dane kolejno, aż w końcu trafia na instrukcję, którą wykonuje. Dlatego domyślne/opcjonalne argumenty w językach programowania umieszczamy w prototypach funkcji na końcu (z prawej strony). Stos to struktura, której operacje w "naturalny" sposób odwracają sekwencję. Zademonstrujmy to najpierw na liście w Python:
>>> L = []
>>> L = []
>>> L.append(0) # PUSH
>>> L.append(1) # PUSH
>>> L.append(2) # PUSH
>>> L
[0, 1, 2]
>>> L.pop() # POP
2
>>> L.pop() # POP
1
>>> L.pop() # POP
0
Lepszym zobrazowaniem tego byłoby list comprehension z użyciem while, ale niestety nie jest to możliwe w Python.
>>> L = [0, 1, 2, 3]
>>> [L.pop() while L]
File "<stdin>", line 1
[L.pop() while L]
^
SyntaxError: invalid syntax
W każdym razie - operacje PUSH/POP w naturalny sposób odwracają kolejność elementów.
Stos a pamięć
W komputerach pamięć jest zorganizowana jako stos (stack) oraz jako sterta (heap). Stos to - jak wyżej omówiliśmy - dane i instrukcje w kolejności do wykonania. Stos ma jednak ograniczoną pojemność, systemy operacyjne limitują też rozmiar stosu do wykorzystania przez program.
$ ulimit -a | grep stack
stack size (kbytes, -s) 8192
$ ulimit -s
8192
Jeśli przetwarzamy dane wielkich rozmiarów (np. plik/blok o rozmianie 1GB), to nie chcemy (często nie możemy) umieścić go na stosie. Umieszczamy takie dane w pamięci na stercie (alokacja, new, malloc()), a system zwraca nam wskaźnik/adres na miejsce, w którym te dane się zaczynają. Rozmiar musimy śledzić samodzielnie, system mówi jedynie "gdzie", a nie "ile".
Do przekazywania takich bloków używamy wtedy wskaźników (☞ "tam jest, po tym adresem mieszka"), bądź referencji &data. Wskaźnik to liczba przechowująca adres pamięci, a referencja to właśnie adres pamięci (np. tego bloku o rozmiarze 1GB). Adres można przechować w zmiennej typu wskaźnikowego. Na stosie umieszczana jest zatem tylko liczba (adres), w funkcji ją przejmujemy i spod adresu reprezentowanego przez tę liczbę dostajemy się do danych (dereferencja wskaźnika (*ptr)).
Stack overflow
Każdy program ma swój stos ograniczony rozmiarowo. Jeśli będziemy na stos odkładać bez przerwy dane, stos będzie przyrastał, a w efekcie przekroczymy dozwolony rozmiar. System zakończy wtedy nasz program i zgłosi błąd naruszenia pamięci. Najprostszy przykład w shellu (poniżej szczegółowe wyjaśnienie):
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
Co widzimy:
- tworzę plik z aktualną datą - linia 1
- listuję plik (
/bin/ls) - linia 2 - wypisuję zawartość pliku (
/bin/cat) - linia 4 - ograniczam stos do 8 kilobajtów (
ulimit- shell builtin) - linia 6 - próbuję wylistować bieżący katalog,
/bin/lsprzekracza stos, system przerywa program (SIGSEGV, "Segmentation fault") - program
/bin/catwciąż się wykonuje - widocznie tak mało zasobów potrzebuje - linia 9 - ograniczam stos do 2 kilobajtów - linia 11
- sprawdzam
/bin/cati teraz już nie mógł się wykonać - linia 13
Przykład: rlimit (Python)
Możemy to samo wykonać w Python, ale szczegółowego omówienia dokonamy poniżej na kodzie w języku C:
>>> import os
>>> import resource
>>> os.system("/bin/ls")
file.txt stackoverflow stackoverflow.c
0
>>> resource.setrlimit(resource.RLIMIT_STACK, (2, 2))
>>> os.system("/bin/ls")
-1
>>> resource.setrlimit(resource.RLIMIT_STACK, (1234567890, 1234567890))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: not allowed to raise maximum limit
Przykład: rlimit (C)
A teraz zdam się na język C. Pozwoli nam to zobaczyć przy okazji wyżej wspomniane wskaźniki. To jest blog o programowaniu, odpalam C, uwaga:
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 | |
Co robi ten kod?
W pierwszych trzech liniach dołączam nagłówki funkcji, z których będę korzystał w programie. sys/resource.h potrzebuję by móc ustawić i odczytać limit zasobów (tutaj stosu).
W liniach 6-10 definiuję funkcję, która otrzyma wskaźnik na obiekt struktury, w której są liczby informujące o limicie. Funkcja je jedynie wypisuje. Nie może ich zmieniać, gdyż wskaźnik jest const (przekazany obiekt jest read-only).
W funkcji main() odbieram argumenty i przypisuję pierwszy argument do zmiennej stack_size konwertując napis na liczbę (ascii to int). To samo robimy w Python przy użyciu argparse. Następnie tworzę obiekt typu (klasy/struktury) rlimit (linia 16) i podstawiam stack_size jako limit (linie 17 - 18).
W linii 20 przekazuję systemowi limity do ustawienia. Przekazuję tutaj właśnie adres mojego obiektu (&my_limits), który funkcja setrlimit (int setrlimit(int resource, const struct rlimit *rlim))
odbiera przez wskaźnik. Jako zasób, którego limity ustawiam, przekazuję RLIMIT_STACK. Można zmieniać inne limity (coredumpsize, segmentu na dane, liczby otwartych plików, itd.).
W linii 21 pobieram ustawiony limit, a jako miejsce, do którego system ma wpisać mi te liczby ustawionych limitów, przekazuję mój obiekt. Funkcja getrlimit ma prototyp int getrlimit(int resource, struct rlimit *rlim), zatem przekazaną w drugim argumencie strukturę może zmieniać (nie ma tam const).
W linii 23 wywołuję tę własną funkcję my_function() i przekazuję adres tego obiektu my_limits, w którym przed chwilą system umieścił aktualne limity stosu (RLIMIT_STACK). Funkcja ta jedynie wypisuje ustawiony limit stosu.
Mając ustawione już limity próbuję wywołać systemową komendę /bin/ls, która ma wylistować zawartość katalogu, w którym program został uruchomiony.
Kod umieściłem w pliku o nazwie stackoverflow.c.
Kompiluję, uruchamiam, patrzymy:
$ cc stackoverflow.c -o stackoverflow -Wall -Werror
$ ./stackoverflow 128
Soft: 128
Hard: 128
OK? 0
Nie udało się - stos ma ograniczony rozmiar. Spróbujmy z wielkim rozmiarem stosu.
$ ./stackoverflow 123456789
Soft: 123456789
Hard: 123456789
file.txt stackoverflow stackoverflow.c
OK? 1
Kiedy stos był ograniczony do 128 kilobajtów, wywołanie /bin/ls nie powiodło się. System "zabił" ten program wysyłając sygnał SIGSEGV (to samo co komenda: kill -11 $PID, czy kill -SIGSEGV $PID).
Kiedy jednak stos jest wystarczająco pojemny, to program /bin/ls się wykonuje poprawnie. Na terminalu pojawił się wynik komendy /bin/ls i widzimy zawartość katalogu: wcześniejszy file.txt, plik z kodem stackoverlow.c oraz sam plik programu wykonywalnego, który właśnie analizujemy: stackoverflow.
Stos a języki programowania
Zdecydowana większość języków programowania jest oparta właśnie o stos. Istnieją pewne implementacje języków stackless, ale nie będziemy w to wnikać. Zostajemy przy Python i C.
O samych podstawach "jak to działa" krótko wspomniałem już tutaj. Teraz to wizualizujemy.
Python:
>>> def func_a(x):
... return func_b(x)
...
>>> def func_b(x):
... return x ** 2
...
>>> func_a(7)
49
>>> import dis
>>> dis.__doc__
'Disassembler of Python byte code into mnemonics.'
>>> dis.dis(func_a)
2 0 LOAD_GLOBAL 0 (func_b)
2 LOAD_FAST 0 (x)
4 CALL_FUNCTION 1
6 RETURN_VALUE
>>> dis.dis(func_b)
2 0 LOAD_FAST 0 (x)
2 LOAD_CONST 1 (2)
4 BINARY_POWER
6 RETURN_VALUE
Mamy dwie funkcje: func_a, func_b. Pierwsza przyjmuje argument, a następnie zwraca wynik wywołania tej drugiej, której przekazuje otrzymany argument. Ta druga odbiera ten argument i zwraca w wyniku kwadrat wartości.
Funkcja func_a otrzymała liczbę 7, wywołała func_b(7), która zwróciła 7 ** 2, czyli 49.
Niżej widzimy import modułu dis, który potrafi pokazać nam kolejne instrukcje jakie wykonuje Python. Te mnemoniki to to samo, co w assemblerze ADD, MOV, JMP, itd. Python implementuje zatem swój "assembler" podstawowych instrukcji, które umieszczane są na stosie, a interpreter je po kolei wykonuje. Interpreter to po prostu maszyna operująca na stosie, podobnie jak robi to procesor. Przypomnieć należy w tym miejscu jedynie, że "programowaniem rządzi prawo abstrakcji".
W listingu pierszej funkcji (func_a) widzimy załadowanie zmiennej x (LOAD_FAST), następnie CALL_FUNCTION, a za nim RETURN_VALUE. Ten CALL_FUNCTION to właśnie wywołanie funkcji (skok do adresu pamięci, gdzie znajdują się instrukcje tejże funkcji (kod ciała funkcji)).
Analogia w C:
int func_a(int x);
int func_b(int x);
int func_a(int x)
{
return func_b(x);
}
int func_b(int x)
{
return x * x;
}
int main()
{
return (func_a(7) != 49);
}
Tutaj jednak nie mamy interpretera, dlatego w return umieściłem porównanie wyniku func_a, aby program zwrócił 0 kiedy wartość jest równa 49, a w przeciwnym razie niech wyjdzie z kodem błędu. Wynik func_a(7) ma być po prostu równy 49.
Kompiluję, uruchamiam, patrzymy.
$ cc example.c -o example -Wall -Werror
$ ./example
$ echo $?
0
$? to ten kod wyjścia programu, dzięki któremu system wie czy program wykonał się poprawnie. 0 oznacza, że nie było błędu. Teraz disassembly i od razu tłumaczymy:
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 | |
Kluczowe fragmenty podświetliłem. Te dziwne %rbp, %edi, %eax to rejestry procesora. Takie komórki, gdzie procesor umieszcza liczby (tutaj kolejno: "base pointer", "extended destination index", "extended accumulator"). One mogą się dzielić na mniejsze (np. eax na ah i al - accumulator high, accumulator low, połowa bitów "starszych" w ah, młodsze w al). Prześledźmy jednak wykonanie mniej szczegółowo.
Funkcja main() ustawia wartość na 0x7 (siódemka), wywołuje func_a (call, linia 9), które jest pod adresem 0x1129. Kiedy func_a się kończy, to program porównuje wynik z liczbą 49 - instrukcja cmp (linia 10). Do akumulatora trafia wynik tego porównania (linia 12), a nastęnie main() zwraca wynik (ret - linia 14).
Funkcja func_a() (linie 17 - 26): ustawia adres powrotu (push %rbp, taki prolog funkcji), odbiera argumenty, a w linii 24 wywołuje func_b(). Dalej widzimy leave - to epilog funkcji, tam jest kilka operacji - m.in. przywracanie adresu dokąd mamy wrócić (return), a za nim sam ret.
Funkcja func_b() (linie 29 - 36): najpierw prolog funkcji i odebranie argumentu. Następnie widzimy imul (mnożenie). Wartość naszej zmiennej x znajduje się w akumulatorze, a zatem mnożenie to: "pomnóż tę liczbę z eax razy tyle ile jest w eax". Znowu epilog i return.
Te instrukcje push/pop/mov/imul/ret (itd.) to instrukcje procesora. Każda z nich ma swój rozmiar. Te dziwolągi a'la 0x000000001140, to adresy - odległości /offset/ od początku startu bloku kodu. Jeśli się pomieszają, to procesor zacznie wykonywać niespodziewane rzeczy. Ale po to mamy właśnie typy danych, żeby się "nie rozjechało". Różne procesory mają różne zestawy instrukcji, różne ich rozmiary. Tym jakie instrukcje należy wygenerować na dany procesor zajmuje się kompilator. On "wie" jaka to architektura maszyny, generuje assembler (te mnemoniki), a następnie uruchamia kompilator assemblera, który już zamienia te wygodne mnemoniki na liczby (kod maszynowy). Można wrócić do tego, co już wyżej linkowałem, czyli tutaj.
Stos a rekurencja
Funkcje to "podprogramy" (niektóre języki nazywają je "subrutynami" /np. Perl/). Wywoływane podprogramy tworzą ramki stosu - stąd prolog i epilog. Nie wchodząc w szczegóły - każdy call dodaje na stos, a return powoduje zwinięcie tego stosu o całość instrukcji, które call umieścił na stosie. W przypadku funkcji rekurencyjnych można zobrazować to w ten sposób (tutaj bez zwijania stosu, prezentujemy błąd):
>>> def my_func_r(depth):
... print("." * depth, "hello")
... return my_func_r(depth + 1)
I wykonanie. Dla przejrzystości ustawiam limit rekursji.
>>> import sys
>>> sys.setrecursionlimit(16)
>>> my_func_r(0)
hello
. hello
.. hello
... hello
.... hello
..... hello
...... hello
....... hello
........ hello
......... hello
.......... hello
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 3, in my_func_r
File "<stdin>", line 3, in my_func_r
File "<stdin>", line 3, in my_func_r
[Previous line repeated 8 more times]
File "<stdin>", line 2, in my_func_r
RecursionError: maximum recursion depth exceeded while calling a Python object
Jeśli wykonywalibyśmy bez przerwy kolejne wywołania (call), to interpreter nie miałby już miejsca na stosie na odkładanie adresów powrotu z call. Dlatego też Python implementuje limit dla rekursji. Bez tego limitu brakłoby miejsca na stosie, a winnym byłby sam Python. System zabiłby proces samego interpretera Python. Python zatem śledzi nasze rekurencyjne wywołania, a kiedy osiągniemy limit zagnieżdzenia, przerywa funkcję i zgłasza wyjątek RecursionError.
Popatrzmy zatem na język, który nas nie będzie pilnował i ograniczał. Skoro chcemy spowodować stack overflow, to komputer ma nam na to pozwolić. To my rządzimy, kalkulator tylko liczy.
Odpalam C, uwaga.
void my_func()
{
my_func(); /* recursion */
}
int main()
{
my_func();
}
Kompiluję, uruchamiam, patrzymy:
$ cc recursion.c -o recursion
$ ./recursion
Segmentation fault
Nie mamy się nad czym rozwodzić. Program został zabity. Nie będę uruchamiał krokowego śledzenia w debuggerze, możemy jednak spowodować, aby przy "crashu" system zrzucił do pliku na dysku obraz tego, co było w pamięci wraz z całym stosem wykonania. Przy okazji widzimy ustawienie innego limitu (to też rlimit).
$ ulimit -c unlimited
$ ./recursion
Segmentation fault (core dumped)
System przerwał program i zrzucił na dysk obraz pamięci tego procesu.
Uruchamiam debugger, ładuję program oraz obraz pamięci, patrzymy co się wydarzyło ("post mortem"):
$ gdb -q ./recursion ./core.dev.lan.recursion.1640274803
Reading symbols from ./recursion...
(No debugging symbols found in ./recursion)
[New LWP 1726222]
Core was generated by './recursion'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0 0x000055d997b8b132 in my_func ()
(gdb) bt
#0 0x000055d997b8b132 in my_func ()
#1 0x000055d997b8b137 in my_func ()
#2 0x000055d997b8b137 in my_func ()
#3 0x000055d997b8b137 in my_func ()
#4 0x000055d997b8b137 in my_func ()
#5 0x000055d997b8b137 in my_func ()
[..]
#523165 0x000055d997b8b137 in my_func ()
#523166 0x000055d997b8b137 in my_func ()
#523167 0x000055d997b8b137 in my_func ()
#523168 0x000055d997b8b148 in main ()
Wywołań my_func() było ponad pół miliona. Wtedy nastąpiło przepełnienie stosu, a system operacyjny przerwał program nie dając mu żadnej szansy na cokolwiek. Sygnałem zakończenia był SIGSEGV:
Program terminated with signal SIGSEGV, Segmentation fault.
Ten sygnał wprawdzie da się przechwycić, ale niespecjalnie jest jak go obsłużyć. Nie będziemy omawiać tutaj sygnałów synchronicznych, asynchronicznych i restartowania wywołań systemowych. Przyjmujemy zatem, że
jeśli przekroczymy stos, to nasz program zostanie siłowo zakończony bez względu na to, cóż tak ważnego robił...
Stack overflow. SpaceX wybucha.
Przykłady wykorzystania stosu
Przyzwyczajeni jesteśmy do notacji infiksowej: 2 + 2. Operator dodawania występuje pomiędzy operandami. Istnieją jeszcze: notacja prefiksowa oraz postfiksowa. Ta pierwsza była używana przez polskiego logika i matematyka - czyli filozofa - Jana Łukasiewicza. Notacja ta (prefiksowa) ma operator z przodu, a za nim występują argumenty. Notacja ta nosi nazwę notacji polskiej. Istnieje też "odwrotna notacja polska" (RPN - Reverse Polish Notation), która jest notacją postfiksową, a zatem operator występuje na końcu. W przypadku notacji polskiej i odwrotnej notacji polskiej od razu zauważymy stos.
Przykład notacji prefiksowej:
$ clisp -q
[1]> (+ 1 2 3 4)
10
[2]> (+ 1 2 3 4 5 6 (+ 7 8))
36
[3]> (* 2 (+ 1 2 3))
12
Ma to zatem postać, którą można rozpisać na funkcje. Powyższe przykłady to odpowiednio:
[1]: add(1, 2, 3, 4)
[2]: add(1, 2, 3, 4, 5, 6, add(8 ,7))
[3]: mul(2, add(1, 2, 3))
Nazwa funkcji, argumenty. Ewaluacja od wewnątrz. Ot, cała filozofia. Proste i piękne, trzeba to przyznać.
Programowalna maszyna stosowa (Python)
Skoro już wiemy tyle o stosie to możemy napisać sobie program maszyny stosowej... kalkulator oparty o stos. A może nawet rozwiniemy go szybko do kalkulatora programowalnego z pamięcią ("odpowiednikiem" sterty).
Potrzebujemy listę/kolejkę na elementy, możliwość wykonywania PUSH i POP, a reszta to już zwykła arytmetyka.
Zacznijmy od stosu. Możemy użyć listy, ale żeby było czytelniej - opakowuję listę w osobnej klasie Stack:
class Stack:
def __init__(self, maxsize=8):
self.maxsize = maxsize
self._stack = []
def push(self, instr):
assert len(self._stack) < self.maxsize, "Stack overflow"
self._stack.append(instr)
def pop(self):
return self._stack.pop()
def __bool__(self):
return bool(self._stack)
Można ograniczyć rozmiar stosu, jest push, jest pop, a operator rzutowania typu na typ bool pozwoli nam sprawdzić później czy stos jest pusty. Moglibyśmy mieć np. metodę "size()" zamiast __bool__(), ale operatory też niech nas nie dziwią.
Teraz kod maszyny. Ja zaimplementuję prosty interpreter, który umie wykonywać jedynie podstawowe operacje arytmetyczne. Kod można napisać znacznie krócej, ale rozpisuję tutaj operacje na kaskadę warunków if/else.
class Interpreter:
def __init__(self, stack_maxsize=8):
self.accu = None
self.stack = Stack(stack_maxsize)
self.stack_maxsize = stack_maxsize
def reset(self):
self.accu = None
self.stack = Stack(self.stack_maxsize)
def _execute(self, instr):
op, *arguments = instr.split()
op = op.upper()
arguments = list(map(float, arguments))
if op in ["RESET", "RST", "CLEAR", "CL"]:
self.reset()
return
if op == "PUSH":
self.stack.push(arguments[0])
elif op == "POP":
return self.stack.pop(arguments[0])
elif op == "INSPECT":
return list(self.stack._stack)
elif op in ["+", "ADD"]:
self.accu = (0 if self.accu is None else self.accu)
if not self.stack:
self.accu += self.accu
else:
while self.stack:
self.accu += self.stack.pop()
return self.accu
elif op in ["-", "SUB"]:
self.accu = (0 if self.accu is None else self.accu)
if not self.stack:
self.accu -= self.accu
else:
while self.stack:
self.accu -= self.stack.pop()
return self.accu
elif op in ["*", "MUL"]:
self.accu = (1 if self.accu is None else self.accu)
if not self.stack:
self.accu *= self.accu
else:
while self.stack:
self.accu *= self.stack.pop()
return self.accu
elif op in ["/", "DIV"]:
self.accu = (0 if self.accu is None else self.accu)
if not self.stack:
self.accu /= self.accu
else:
while self.stack:
self.accu /= self.stack.pop()
return self.accu
else:
try:
self.stack.push(float(op))
except ValueError:
raise Exception("Unsupported operation: %s" % op)
def run(self):
print(self.__class__.__name__)
print("Ctrl-C to exit.")
while True:
try:
instruction = input("> ")
if not instruction:
continue
result = self._execute(instruction)
if result is not None:
print(result)
except KeyboardInterrupt:
return
except Exception as e:
print("ERROR", e)
if __name__ == "__main__":
interpreter = Interpreter(8)
interpreter.run()
Kod w repozytorium git.
Przy inicjalizacji tworzę obiekt stosu. Interpreter posiada również zmienną accu, w której będą gromadzone bieżące wyniki. Metoda _execute() przetwarza podane instrukcje:
RESET,RST,CLEAR,CL- powodują wyzerowanie akumulatora oraz reinicjalizację stosuPUSH- odkłada jeden element na stosPOP- zdejmuje ze stosu jeden elementINSPECT- wyświetla elementy odłożne na stosieADD- dodawanieSUB- odejmowanieMUL- mnożenieDIV- dzielenie
Podczas wykonywania operacji arytmetycznych wartości ze stosu są zdejmowane.
Akumulator początkowo ustawiam na None, a przed każdą operacją sprawdzam czy coś jest na stosie.
W przypadku mnożenia - kiedy stos jest pusty - początkową wartość akumulatora ustawiam na 1. Dla pozostałych operacji ustawiam w takim przypadku 0.
Metoda run() to najzwyklejsza pętla while, która czeka na wpisanie instrukcji, a później zleca ich wykonanie.
Demo
Uruchamiam program:
$ python machine.py
Interpreter
Ctrl-C to exit.
> inspect
[]
> push 2
> push 3
> inspect
[2.0, 3.0]
> add
5.0
> inspect
[]
> *
25.0
> mul
625.0
> 10
> *
6250.0
> 2
> 3
> 4
> *
150000.0
> 111
> 222
> inspect
[111.0, 222.0]
> reset
> inspect
[]
> 2
> 2
> +
4.0
> 3
> -
1.0
>
Ot, filozofia. Problem wydaje się banalny, a jednak jest w nim kilka niuansów. Najpewniej zauważymy je dopiero implementując samodzielnie taki program, do czego zdecydowanie zachęcam.
Programowalna maszyna z pamięcią (Python)
Napiszę teraz podobny program. Pominę już tutaj kwestię stosu i dla zwięzłości zaimplementuję mini interpreter, który będzie zapamiętywał wartości zmiennych, a podczas wykonywania operacji będzie się do tej pamięci odwoływał . Kod moich programów będzie wyglądał tak:
SET X 5
SET Y 7
MUL X Y ; 35
ADD X Y ; 12
Implementacja samego interpretera jest tutaj dosyć prosta. Posiłkuję się dodatkowo modułem operator, który zapewni mi zwięzłe wykonanie odpowiednich operacji arytmetycznych.
Kod programu:
import operator
class Interpreter:
def __init__(self):
self.memory = {}
def run(self):
while True:
try:
instr = input("> ")
if not instr:
continue
op, A, *B = instr.split()
op = op.upper()
ops = {
"ADD": operator.add,
"SUB": operator.sub,
"MUL": operator.mul,
"DIV": operator.truediv,
}
if op == "GET":
assert A in self.memory, "No such variable: %s" % A
return self.memory[A]
elif op == "SET":
self.memory[A] = float(B[0])
else:
assert op in ops, "Invalid operation: %s" % op
A = float(self.memory[A])
B = float(self.memory[B[0]])
print(ops[op](A, B))
except KeyboardInterrupt:
return
except Exception as e:
print("ERROR", e)
if __name__ == "__main__":
Interpreter().run()
Pamięć tego interpretera to słownik. Każda operacja musi mieć przynajmniej jeden argument. GET używa tylko pierwszego. SET ustawia zmienną w pamięci. Reszta operacji to podstawowe operacje arytmetyczne.
Oczywiście - pomijam tutaj wszelki error handling oraz nie dbam o poprawność wprowadzanych danych. W tej chwili przykładowo nie sprawdzam czy nazwa zmiennej nie jest liczbą. Nic nie stoi na przeszkodzie, by w linii komend tego interpretera wprowadzić dane, które nie mają sensu, np. SET 7 9. Sprowadzam to do użytecznego minimum.
Demo
$ python memmachine.py
> SET X 5
> SET Y 7
> ADD X Y
12.0
> MUL X Y
35.0
> SUB X Y
-2.0
> DIV X Y
0.7142857142857143
> GET foo
ERROR No such variable: foo
> SET foo 5
> SET bar 7
> ADD foo bar
12.0
Stos, procesy, wątki
Wątków nie będziemy tutaj analizować, to temat głęboki i będzie miał swoją dedykowaną serię artykułów, ale zadać można jednak teraz krótkie pytanie:
- jeśli "modelowy" procesor wykonuje instrukcje programu po kolei, to jak to się dzieje, że programy wykonują się jednocześnie?
Procesor wykonuje programy "po kawałku". Jeśli musi wykonywać więcej niż jeden program "jednocześnie", to tak naprawdę wszystkie programy wykonują się po kilka instrukcji. System operacyjny ma "scheduler" (mechanizm zarządzający procesami według ich priorytetów, generowanego obciążenia, aktualnie wykonywanych operacji, itd). Scheduler wyznacza kolejne programy, które mają otrzymać pewien przedział czasu procesora. Procesor wykonuje fragment kodu danego programu, a następnie odkłada stan systemu (rejestry/itp.) do cache. Przywraca stan rejestrów wcześniej uruchomionego programu i wykonuje znów fragment kodu tego programu.
Zatem na "modelowym procesorze" z jednym rdzeniem i bez żadnych dodatkowych mechanizmów - jednoczesne wykonanie programów jest złudzeniem/symulacją. Wykonują się one "turami", ale dzieje się to na tyle szybko, że tego nie zauważamy.
Stos w procesie, stosy w wątkach.
Uruchomione programy to procesy w systemie. Zmiana procesu aktualnie wykonywanego - ze wszystkimi mechanizami cache/synchronizacji - nazywamy zmianą kontekstu (context switch). Tak samo na modelowym procesorze będzie działo się w przypadku programu, który działa w wielu wątkach, a wątki te wykonują się "jednocześnie".
Wątki to też procesy (mają swój PID /identyfikator w systemie/, można im wysłać sygnał, nadać ograniczenia zasobów), mają swoje stosy, jednak od samych procesów różnią się przede wszystkim tym, że współdzielą obszar pamięci całego procesu (wiele wątków działa w obszarze pamięci głównego procesu, w którym zostały stworzone).
Osobne procesy nie mogą uzyskiwać dostępu do obszarów pamięci innych procesów, natomiast wątki "widzą" i mają dostęp do tego samego obszaru (w ramach programu, w którym zostały uruchomione). Wątki mają swoje stosy, ale na tych stosach są adresy tych samych - współdzielonych - obszarów pamięci.
Stąd istnieje konieczność synchronizacji dostępu do danych (tylko jeden pisze w danym czasie, reszta czeka). W Pythonie nie ma to takiego znaczenia, gdyż Python implementuje globalną blokadę (GIL). To jednak temat na inny artykuł. Niemniej, działanie komputerów jakich używamy - tych w architekturze Von Neumanna - oparte jest właśnie o stos. Sama architektura dzieli się oczywiście na jednostkę arytmetyczno-logiczną, pamięć, i pozostałe komponenty. Link do Wikipedii podawałem już na samym wstępie.
Podsumowanie
Ze stosem wiąże się wiele innych zagadnień, a wiele złożonych algorytmów korzysta z tego mechanizmu, np. Algorytm Fleury'ego.
W samych językach programowania mamy np. wyjątki. Wyjątek to taki wielki skok (longjmp) przez cały rozwinięty stos. W obsłudze wyjątków (try/catch) mamy najczęściej dostęp do tego stosu (backtrace). Podobnież w debuggerach - zapewne najczęściej używaną komendą w debugerze jest "backtrace".
Chciałbym jednak zwrócić ponownie uwagę na fakt, że w architekturze dzisiejszych komputerów kod (instrukcje) i dane są umieszczane na jednym stosie. Jeśli pomieszamy instrukcje z danymi, procesor zacznie interpretować dane jako instrukcje (ostatecznie wszystko jest liczbą). Otrzymamy wtedy albo błędne wyniki, program zrobi coś głupiego, albo nie będzie w ogóle działał. Jeśli program w sposób nieprzewidziany daje błędne wyniki, to jest w zasadzie gorszy niż taki, który w ogóle się nie uruchamia.
Inną konsekwencją tej architektury są problemy rzutujące na bezpieczeństwo danych i systemów. Wiele osób w dzisiejszym świecie sprzecza się o wyższość takiego, czy innego języka programowania nad innymi. Przeważnie winą obarcza się język C. Jednak to nie C jest winne sytuacji, a architektura maszyny. Pod C jest jeszcze assembler, a pod nim już same liczby. Jeśli pominiemy wszystkie warstwy abstrakcji i dotrzemy do kodu maszynowego, to tam po prostu nasza własna błędna kalkulacja może być źródłem błędu - bez udziału translatorów/kompilatorów. Oczywiście - należy dopingować wszelkie starania w kierunku ulepszania języków programowania i narzędzi - aby były bezpieczniejsze, sprawniejsze, wydajniejsze, łatwiejsze. Niestety, jedynym narzędziem jakim dysponujemy jest abstrakcja, budowanie z tego co już mamy. Wszystko ma swoje zastosowania i historię. Na koniec więc pytanie: jak zademonstrować przepełnienie stosu w języku, który jest "memory safe" (nie uciekając się do prymitywu)?