O królu RAM-ie i rycerzach kontekstu

Krótki przewodnik po pamięciach
„RAM, jaki jest, każdy widzi”.
ks. Benedykt RAM-owski

RAM retrospekcja

Parafrazując stwierdzenie zaczerpnięte z XVIII-wiecznej encyklopedii, RAM, jaki jest, każdy widzi. Na dodatek każdy, kto napisał choć kawałek kodu z użyciem jednej zmiennej, może śmiało powiedzieć, że wie o RAM-ie tyle, ile mu potrzeba. Jednak, jak pokazuje praktyka projektowa, nie zawsze jest to prawda.

Zrozumienie wewnętrznych podziałów tego wydawałoby się spójnego obszaru oraz mechanizmów nim rządzących pozwoli nam:

• zaplanować i przydzielić wystarczająco duży obszar stosu potrzebny dla naszej aplikacji
• diagnozować i debugować typowe problemy związane z błędną inicjalizacją bądź przepełnieniem któregoś z obszarów
• zastosować kilka programistycznych sztuczek, celem ograniczenia użycia pamięci RAM

W ramach tego artykułu zwrócimy większą uwagę na kwestię kontekstu oraz jego wpływu na zajętość stosu w urządzeniach wbudowanych.

Stos, sterta, dane statyczne

Ogólnie, pamięć RAM możemy podzielić na 3 zasadnicze obszary:

• Stos (stack) – obszar, w którym przechowywane są wszystkie zmienne lokalne oraz odkładany jest kontekst przy wywoływaniu funkcji lub przerwania. Stos zwykle umieszcza się na końcu pamięci RAM i rośnie on w kierunku malejących adresów, czyli graficznie w dół
• Stertę (heap) – jest to obszar, do którego trafiają wszystkie zmienne dynamicznie zaalokowane za pomocą polecenia malloc(). Od stosu oddziela go pas (ziemi) pamięci niczyjej
• Obszar danych statycznych – położony przy najniższych adresach RAM-u zawiera w sobie wszelkie dane globalne, przechowywane w naszym programie, np. wszystkie zmienne czy struktury globalne oraz zmienne statyczne.
  Słowem – wszystkie te wartości, która mają przetrwać między wywołaniami funkcji. Wielkość obszaru danych statycznych jest ustalana na etapie kompilacji i stała przez cały czas działania programu.
  Obszar ten dzieli się dodatkowo na dwa podobszary:
  • .bss
  • .data

W dalszych rozważaniach skupimy się głównie na stosie. Jest to bowiem ten obszar, którego rozmiar potrafi zmieniać się w szerokim zakresie i który może przysporzyć nieoczekiwanych problemów.

Stos

Stos jest kolejką typu LIFO (Last-In-First-Out). Ostatni element odłożony na stosie jest pierwszym elementem, który możemy z tego stosu zdjąć. Odkładanie wartości na stosie przypomina układanie książek na stole, płasko jedna na drugiej. Pamiętając jednocześnie o kierunku, w którym wspomniany już stos rośnie, chyba powinniśmy jednak porównać odkładanie na nim danych do próby odłożenia książki na suficie.

Zasadniczo na stos odkładamy dane żyjące krótko, przechowywane w pamięci na potrzeby tych kilku milisekund, kiedy wywoływana jest konkretna funkcja, która dodatkowo woła jeszcze jedną bądź kilka innych funkcji. Nad położeniem wierzchołka stosu czuwa dedykowany rejestr sprzętowy (SFR) zwany wskaźnikiem stosu.

Wskaźnik stosu

Wskaźnik stosu przechowuje aktualny adres wierzchołka stosu. Jest to więc pierwszy adres, spod którego nastąpi odczyt ze stosu za pośrednictwem instrukcji pop. Kolejny adres po adresie wskaźnika stosu będzie pierwszym, pod który wykonany zostanie zapis za pośrednictwem instrukcji push.
Wskaźnik stosu jest swoistą zakładką w książce – pozwala m.in. na szybkie odszukanie kontekstu funkcji wołającej podczas powrotu z funkcji wołanej.

Kontekst i skok do funkcji

Wołając funkcję z dowolnego miejsca w programie, ładujemy argumenty do rejestrów procesora bądź wrzucamy je na stos. Następnie wykonujemy skok pod adres początku wywoływanej funkcji. Po wykonaniu określonego przez wywołaną funkcję zadania, programu musi powrócić do miejsca, z którego nastąpił skok. Powinniśmy więc jakoś zapamiętać adres tego miejsca, aby później łatwo do niego wrócić.

Sytuacja komplikuje się, jeżeli wywołana przez nas funkcja wywołała kolejną, kolejna kolejną i tak dalej. Na dobrą sprawę, powinniśmy zachować wszystkie adresy, spod których nastąpiło wywołanie każdej z funkcji we wspomnianym łańcuchu. Dodatkowo, z każdą funkcją w chwili wywołania kolejnej, związany jest pewien stan programu lub procesora, reprezentowany przez zawartość rejestrów CPU.
Z chwilą powrotu z funkcji wołanej do funkcji wołającej powinniśmy ten stan rejestrów odtworzyć.

I tutaj przychodzi nam z pomocą wspomniany wcześniej stos. Na nim bowiem zachowujemy (odkładamy):

• zawartość rejestrów ogólnego przeznaczenia
• rejestr statusu (SR)
• aktualną wartość wskaźnika stosu (SP)
• aktualną wartość licznika programu (PC)
• wspomniany wcześniej adres powrotu (LR)

Wymienione wyżej dane, zgrupowane w logiczną strukturę, nazywamy kontekstem. Jest on odkładany na stos w momencie wywołania funkcji bądź wywołania procedury obsługi przerwania.

Kontekstowa pułapka

Mechanizm odkładania i ściągania kontekstu ze stosu pozwolił nam na łatwe i uporządkowane przeskakiwanie między kolejnymi funkcjami, zachowując i odtwarzając przy tym stan programu po każdym skoku. Wszelkie istotne dane są bowiem bezpiecznie zachowane na stosie i odtwarzane podczas powrotów z kolejnych funkcji. Jednak wraz ze wzrostem skomplikowania naszego programu możemy natknąć się na szereg niespodzianek, które zaowocują nieoczekiwanym resetem i nie będą wcale łatwe do odtworzenia i debugowania.

Wywołanie głęboko zagnieżdżonych funkcji

Skoro każde wywołanie funkcji powoduje odłożenie na stosie – lekko licząc – ośmiu rejestrów (ilość odłożonych rejestrów różni się w zależności od konkretnego rdzenia), to, zależnie od ich wielkości, pamięć RAM zostanie uszczuplona o 8 do 32 bajtów.

Jeżeli więc wywołana przez nas funkcja wywoła kolejną, ta następną i jeszcze kolejną aż do, powiedzmy, siedmiu razy, może się okazać, że lekką ręką „wydaliśmy” siedmiokrotność wielkości kontekstu. Przy założeniu, że pojedynczy rejestr ma 4 bajty, sumarycznie będą to 224 bajty. I te 224 bajty zajęliśmy (a może raczej zmarnowaliśmy?) jedynie na potrzeby zachowania kontekstów poszczególnych funkcji, nie przechowując przy tym żadnych danych przetwarzanych przez nasz program.

Jeżeli szczęśliwie mamy do czynienia z platformą, dysponującą setkami kB, a nawet MB pamięci RAM, skutki utracenia 224 bajtów będą niezauważalne. Jednak w przypadku mikrokontrolera, dysponującego kilkunastoma kB pamięci RAM, należy uważać na tego typu nieplanowane i często niewidoczne gołym okiem „wydatki”.

Wyobraźmy sobie bowiem sytuację, w której wywołanie ciągu wielokrotnie zagnieżdżonych funkcji zostanie wywłaszczone przez przerwanie sygnalizujące na przykład odebranie danej po interfejsie szeregowym. Wtedy na stos zostanie odłożony kolejny kontekst. Jeżeli dodatkowo (o zgrozo) wołamy z procedury obsługi przerwania jeszcze kilka zagnieżdżonych funkcji, wówczas może dojść do nieoczekiwanego spotkania nadmiernie spuchniętego stosu ze stertą. Skończyć się to może na wiele sposobów:

• nadpisaniem zawartości sterty przez stos
• wygenerowaniem wyjątku
• resetem platformy

Mówiąc obrazowo – program może „niespodziewanie przewrócić się na twarz” natychmiast lub przy okazji kolejnej interakcji ze stertą. Na dodatek będzie to trudne do odtworzenia, gdyż wymagać będzie pojawienia się wspomnianego już przerwania przy dokładnie identycznym wypełnieniu stosu!

Z powyższego rysunku odczytać możemy:

• lewa strona: wypełnienie stosu praktycznie na styk, brak widocznych problemów
• prawa strona: przepełnienie stosu wywołanie przerwaniem, które pojawiło się nieszczęśliwie akurat w momencie skrajnego wypełnienia stosu

Wczesne wykrywanie problemu

W teorii monitorowanie ilości zajętej pamięci na stosie nie jest trudne. Na dobrą sprawę potrzebna jest do tego znajomość 3 elementów:

• adresu początku stosu
• maksymalnego rozmiaru stosu
• wartości aktualnego wskaźnika stosu

Porównując adres początku stosu do poziomu minimum i adres odpowiadający maksymalnemu rozmiarowi stosu do poziomu maksimum, możemy śmiało powiedzieć, że wartość wskaźnika stosu powinna leżeć pomiędzy nimi. Im bliżej minimum tym lepiej.

Jednak jest to zbyt duże uproszczenie problemu. Zajętość stosu zmienia się bowiem bardzo dynamicznie i obliczenie jego aktualnego użycia powie nam niewiele. Dużo bardziej powinna nas interesować maksymalna zajętość stosu, czyli moment w którym:

• wywołana jest największa ilość zagnieżdżonych funkcji
• wszystkie funkcje odłożyły już na stos swoje zmienne lokalne
• pojawiło się najbardziej pamięciożerne przerwanie

I dokładnie w tym momencie musimy odczytać wartość wskaźnika stosu. Prawda, że proste?

Zamiast polować na ten moment, lepiej posłużyć się jednym z kilku dostępnych sposobów i mechanizmów.

Zanim jednak do nich przejdziemy, podzielmy dostępny obszar stosu na trzy podobszary:

• największy, którego zajęcie uznajemy za normalne w trakcie działania naszego programu
• obszar marginesu bezpieczeństwa, w którym oczekujemy ostrzeżenia o jego przekroczeniu, ale jednocześnie nie wymaga to z naszej strony żadnej reakcji
• obszar krytyczny, którego zajęcie będzie dla nas znakiem poważnych problemów i wymagana jest z naszej strony niezwłoczna reakcja

Należy zaznaczyć, że czerwony alarm powinien zostać podniesiony, zanim nastąpi przepełnienie stosu. Fragment kodu obsługujący wygenerowane przerwanie lub funkcje obsługujące wspomniany alarm również potrzebują tych kilkunastu bajtów stosu, aby się poprawnie wykonać. Z tego powodu alarmowanie w momencie, gdy zapisany został ostatni wolny bajt stosu, jest alarmowaniem spóźnionym.

MMU/MPU

Rozbudowane platformy dysponują jednostką zarządzania lub ochrony pamięci (MMU/MPU), w której możemy określić obszary, pod które zapis jest zabroniony. Upraszczając nieco – konfiguracja MMU/MPU polega na podaniu trzech parametrów dla pojedynczego, chronionego obszaru:

• adres początku
• rozmiar
• dozwolony typ dostępu (zapis, odczyt, wykonywanie kodu)

W efekcie, gdy nastąpi zapis pod którykolwiek z adresów należących do wcześniej zdefiniowanego obszaru, wygenerowany zostanie wyjątek procesora. Takich obszarów możemy zwykle zdefiniować kilka. Dokładna ich liczba zależy od procesora i zastosowanego MMU/MPU.

W momencie wygenerowania wyjątku pozostaje jeszcze kwestia określenia, który z chronionych obszarów został naruszony. W zależności od konkretnego procesora możemy to odczytać z rejestrów MMU/MPU lub rejestrów przechowujących stan pamięci lub szyny danych (np. bus fault address register w procesorach rodziny STM32).

Zapisywanie wzorca na stosie

Dzięki wypełnieniu przypisanej do stosu pamięci znanym i stałym wzorcem (patternem), możemy bezbłędnie ocenić, jak daleko obszar stosu został zapisany w szczytowym momencie jego zajętości. Kolejne, odkładane na stos dane będą bowiem niszczyć zapisany wcześniej wzorzec.

Analizując powyższą grafikę od lewej do prawej możemy zauważyć następujący proces: od niewielkiego zajęcia stosu, przez znaczne zajęcie stosu, po ponownie wolny stos. Co istotne – raz nadpisany fragment wzorca znika na zawsze.

Cykliczne sprawdzanie, jak daleko wzorzec został nadpisany, pozwoli nam określić maksymalną zajętość stosu w dłuższym okresie działania naszego programu. W przypadku systemów jednowątkowych jest to wystarczająca metryka, pozwalająca określić doświadczalnie (in vivo), jak duży obszar stosu jest wymagany na potrzeby konkretnej aplikacji.

W przypadku systemów wielowątkowych metoda wzorca może nas zaprowadzić na manowce. Temat przybliżę w kolejnym artykule dotyczącym stosu.

Jak duży powinien być obszar stosu?

Ciężko jest podać jednoznaczną odpowiedź na pytanie, jak duży obszar RAM-u należy przeznaczyć na stos. W idealnym świecie moglibyśmy odpowiedzieć – tak duży, jak tylko się da. W większości realnych przypadków nie mamy takiej możliwości. Dodatkową trudnością jest konieczność nieco arbitralnego określenia tej wielkości przed napisaniem pierwszej linii kodu.

Możemy posiłkować się wartością procentową bądź obliczyć w sposób przybliżony potrzebną ilość stosu biorąc pod uwagę:

• ilość działających jednocześnie wątków
  • systemy jednowątkowe wymagają mniejszego stosu od wielowątkowych
• dostępną ilość RAM-u w procesorze
  • przykładowo przy 10 kB dostępnego RAM-u, poświęcenie 30% na stos wydaje się wartością rozsądną, pamiętając przy tym, aby nie pisać kodu zawierającego wielokrotnie zagnieżdżone funkcje
  • w przypadku platformy wyposażonej w 128 kB RAM-u ustawienie wielkości stosu na 30% może się okazać rozrzutnością, szczególnie jeżeli uruchamiany na niej program jest prosty
• złożoność naszego programu
  • nawet rozbudowany program, będący kombinacją funkcjonalności opartych o proste moduły, jak np. GPIO, RTC, UART czy implementującego prosty protokół szeregowy, wymaga zdecydowanie mniej stosu od mniej rozbudowanego programu wykorzystującego stos TCP/IP, biblioteki graficzne do obsługi wyświetlacza dotykowego czy biblioteki kryptograficzne
• konieczność użycia zewnętrznych bibliotek
  • nie mamy bowiem wpływu na ilość zagnieżdżeń funkcji oraz generalnie użycie zasobów przez bibliotekę
  • w dokumentacji od biblioteki powinniśmy znaleźć informację na temat oczekiwanej zajętości stosu (tzw. footprint)
• szacowaną ilość zagnieżdżeń funkcji

Jeżeli już kompletnie nie wiemy, jaką wartość przyjąć – przydzielmy 30% dostępnej pamięci, a następnie dokonajmy pomiaru maksymalnej zajętości stosu i zaktualizujmy przyjętą wartość, zachowując 10-20% marginesu bezpieczeństwa.

Wielkość wspomnianego marginesu powinna być tym większa, im bardziej odpowiedzialne zadanie będzie wykonywało nasze urządzenie. Nieoczekiwany, wynikający z przepełnienia stosu, reset domowego nawilżacza powietrza podczas zmiany ustawień głęboko w menu nie będzie czymś strasznym. Inaczej jednak będzie to wyglądało np. w przypadku sterownika obrabiarki numerycznej – tutaj może dojść do zaburzenia procesu produkcji, co przełoży się na realne straty finansowe.

Dodatkowym czynnikiem decydującym o wielkości wspomnianego marginesu, powinna być możliwość (lub niemożność) wykonania łatwej aktualizacji oprogramowania urządzenia u klienta lub w polu.

Podsumowanie

O RAM-ie i jego obszarach można spokojnie napisać opasłą książkę oraz obronić doktorat i habilitację naukową. Zadaniem praktyków jest jednak zrozumieć go na tyle, aby móc efektywnie i zarazem bezpiecznie z niego korzystać. Na nieostrożnego i nieświadomego programistę czyha tam bowiem wiele pułapek – jedną z nich przybliżyłem w ramach tego artykułu.

Zachęcam wszystkich czytających do przyjrzenia się ustawieniom skryptów linkera w swoich projektach, ze szczególnym naciskiem na położenie oraz rozmiar obszarów stosu oraz sterty.

.223rem