by Logo Technical Blog – Future Processing
14.08.2019
Realizacja Garbage Collectora dla systemu wbudowanego_

Garbage Collector – śmieciarz, sprzątacz nieużywanych obiektów w pamięci. Chyba nie trzeba bliżej przedstawiać tej idei, tak bardzo rozpowszechnionej w najpopularniejszych językach programowania. Ten artykuł nie jest skierowany do osób piszących w Javie, C#, Pythonie i innych językach, które takowy mechanizm sprzątania zaalokowanej pamięci posiadają. Nie będzie to też przepis na porzucenie dotychczasowych praktyk ręcznego, świadomego alokowania i zwalniania pamięci.

Choć w mojej pracy posługuję się językiem C, przedstawione w niniejszym artykule rozwiązania mogą przydać się także osobom piszącym w innych językach. Ponadto artykuł może okazać się ciekawy także dla osób, które nie potrzebują implementować GC w swoich projektach, a jedynie poznać, jak Garbage Collector może działać, jak za jego pomocą szukać wycieków pamięci i co ta wiedza może wnieść do codziennej pracy.

UWAGA: Kod użyty w przykładach nie odpowiada w 100% składni języka C i nie da się go skompilować w takiej formie, w jakiej jest przedstawiony.

Pamięć

Na początek parę słów o pamięci operacyjnej i jej podziale, bo to ją mamy zamiar sprzątać. Pamięć operacyjna nie jest monolitem, a wskaźniki zdefiniowane w różnych jej obszarach mogą wymagać od sprzątacza specjalnego traktowania. Przyjrzyjmy się zatem, z czym możemy mieć do czynienia.

Zero initialized (ZI)

Tutaj trzymane są zmienne globalne, które przy starcie programu inicjalizowane są wartością 0. Zmienne w tym miejscu mogą być modyfikowane, więc trzeba będzie przyjrzeć się ich wartościom.

Read only

Część ROMu, miejsce na stałe (np. znakowe). Nie ma potrzeby zaglądania do pamięci stałej, gdyż nie może tu trafić nic dynamicznego.

Read/Write

Obszar zmiennych zainicjalizowanych konkretnymi wartościami, kopiowany z ROMu i możliwy do modyfikowania. Będziemy mieli go na względzie.

Stacks

Stos, a jakże. Może być ich kilka w systemie. Każdy wątek może mieć swój własny stos, który będzie trzeba przeszukać pod kątem zaalokowanej pamięci dynamicznej. Stosy dla wątków same w sobie także mogą być rezerwowane dynamicznie i zostaną utworzone na stercie, więc mogą zostać przeszukane razem z innymi blokami w ramach czyszczenia sterty. Trzeba jednak uważać, aby taki blok przeszukać tylko do aktualnej pozycji wierzchołka stosu (dzięki temu unikniemy błędnego oznaczenia bloków jako „używane” przez wskaźniki znajdujące się poza stosem).

Heap

Sterta, pamięć dynamicznie alokowana. Na tym obszarze powstają pamięci zaalokowane w czasie wykonania programu. Zanim zwolnimy któryś z bloków, musimy przeszukać go pod kątem odnośników do bloków pamięci. W moim przypadku występują 2 rodzaje sterty: sterta na „małe” i „duże” bloki. Trzeba to mieć na względzie podczas przeszukiwania pamięci.

Dynamiczna alokacja pamięci

Aby umożliwić naszemu śmieciarzowi poprawną pracę, przy alokowaniu pamięci musimy zadbać o dodanie pewnych informacji. Dzięki nim będziemy w ogóle w stanie przeszukiwać stertę naszego programu oraz oznaczać bloki pamięci przeznaczone do usunięcia.
W tym momencie zakładam, iż operacje alokacji i zwalniania pamięci są dostępne dla programisty. Dla uproszczenia będę posługiwał się nazwami malloc oraz free odpowiednio dla tych dwóch operacji, niezależnie od tego, czy tak jak w moim przypadku mamy do czynienia z językiem C i biblioteką stdlib, czy posługujemy się samodzielnie napisanymi funkcjami przeznaczonymi dokładnie do tego samego zadania.

Krok 1 – nagłówek bloku pamięci

W pierwszej kolejności musimy opatrzeć alokowany blok pamięci nagłówkiem, który będzie przechowywał niezbędne dane potrzebne do pracy z blokiem.

struct Header
{
   size_t         Size;      /* Rozmiar bloku                  */
   Header        *Prev,      /* Lista bloków                   */
                 *Next;
   int            IsUsed;    /* Znacznik użycia                */
   int            IsScanned; /* Znacznik przeglądania          */   

};

Najbardziej interesującym polem struktury jest pole IsUsed. Jest to wartość określająca, co zrobić z danym blokiem: zostawić bądź sprzątnąć. Pole IsScanned posłuży do zabezpieczenia się przed podwójnym sprawdzaniem bloku. Będzie to bardzo ważne do pracy ze stosami, które skanujemy tylko do aktualnej ich długości (brak tej flagi powodowałby sprawdzenie całej zaalokowanej dla stosu pamięci w fazie skanowania sterty – a więc możliwość oznaczenia wielu fałszywych użyć). Poza tym zyskujemy odrobinę na wydajności.
UWAGA!
Rozmiar nagłówka musi być wielokrotnością rozmiaru adresu w danym systemie (4 bajty w moim przypadku), aby uniknąć późniejszego uwzględniania wyrównania pamięci operacyjnej w operacjach na blokach.

Krok 2 – rejestr zaalokowanych bloków pamięci

Lista wszystkich zaalokowanych bloków jest konieczna do przeszukania pamięci pod kątem istniejących do niej odwołań.

Nie zagłębiając się w szczegóły implementacyjne założymy, że lista udostępnia następujący interfejs:

Header* Mem_GetHead();	        /* Pobierz początek listy                  */
void    Mem_AddBlock(Header* h);  /* Dodaj blok do listy                     */
void    Mem_Remove(Header* h);    /* Usuń blok z listy                       */

Krok 3 – obudowanie funkcji alokującej pamięć

W tym akapicie malloc i free traktujemy jako standardowe, nieprzeciążone funkcje alokowania pamięci na stercie. W tym momencie warto zadbać o synchronizację między-wątkową dla implementowanych operacji. Użycie LOCK i UNLOCK tylko sygnalizuje miejsca, w których zaczyna i kończy się chroniony kod.

void* myMalloc(size_t size)
{
   LOCK();
   Header* header = malloc(sizeof(*header) + size);
   char* data = ((char*)header) + sizeof(*header);
   header->Size = size;
   Mem_AddBlock(header);
   UNLOCK();
   return data;
}
void justFree(void* ptr)
{
   Header* header = (Header*)(ptr - sizeof(*header));
   free(header);
   Mem_Remove(header);
}

void myFree(void* ptr)
{
   LOCK();
   justFree(ptr);
   UNLOCK();
}

Krok 4 – zasłonięcie standardowego malloca

#undef malloc
#define malloc(x) myMalloc(x)
#undef free
#define free(x) myFree(x)

Przeglądanie pamięci (rdzeń implementacji)

Najpierw podsumujmy: mamy już struktury oraz funkcje odpowiedzialne za alokowanie i zwalnianie pamięci oraz prowadzenie rejestru zarezerwowanych bloków. Wykorzystamy je teraz, aby przeglądnąć pamięć w poszukiwaniu nieużywanych bloków, które nadają się do sprzątnięcia.

Algorytm, jakim będziemy się posługiwać, będzie składał się z następujących czynności:

  1. Oznacz wszystkie bloki w rejestrze jako nieużywane.
  2. Dla każdego obszaru pamięci:
    1. Ustaw wskaźnik na początek obszaru.
    2. Porównaj wartość wskaźnika ze wszystkimi blokami z rejestru:
      • Oznacz te bloki, dla których wartość wskaźnika jest równa adresowi początku bloku przesuniętemu o rozmiar nagłówka jako używane.
    3. Przesuń wskaźnik o odległość odpowiadającą rozmiarowi wskaźnika.
    4. Powtarzaj, aż zostanie przeglądnięty cały obszar pamięci.

Podczas przeszukiwania pamięci korzystamy ze specyfiki wyrównywania pamięci operacyjnej. Mianowicie możemy założyć, że sensowne wskaźniki (takie, które faktycznie mogły zostać zwrócone przez naszą funkcję alokującą) będą zawsze miały wartość podzielną przez rozmiar adresu. Np. 0x02000000, 0x02000004, ale już nie 0x02000002.

Napiszemy funkcje:

void MarkAllUnused(void);                     /* Inicjalizacja */
void SearchMemory_Heap();                     /* Przeglądnięcie sterty */	
void SearchMemory(startPrt, endPtr);          /* Przeglądnięcie obszaru */  

Funkcja oznaczająca wszystkie bloki jako nieużywane jest trywialna:

void MarkAllUnused(void)
{
   Header* block = Mem_GetHead();

   while(NULL != block)
   {
      block->IsUsed = FALSE;
      block->IsScanned = FALSE;
      block = block->Next;
   }
}

Funkcja przeszukująca pojedynczy blok (parametr size potrzebny do sprawdzenia stosów tylko do zadanej długości). Ustawiona zostaje również wspomniana wcześniej flaga IsScanned służąca do uniknięcia sprawdzenia bloku jeszcze raz przy sprawdzaniu całej sterty:

void SearchMemory_Block(struct Header* block, size_t size)
{
   unsigned char* ptr = (unsigned char*)(block) + sizeof(*block);
   SearchMemory(ptr, ptr + size);
   block->IsScanned = TRUE;
}

Funkcja przeszukująca stertę (przejście wszystkich bloków w poszukiwaniu dynamicznie zaalokowanej pamięci):

void SearchMemory_Heap(void)
{
   struct Header* block = Mem_GetHead();
   while(NULL != block)
   {
      if(!block->IsScanned)
      {
         SearchMemory_Block(block, block->Size);
      }
      block = block->Next;
   }
}

Funkcja przeszukująca obszar pamięci będzie przyjmować adres początkowy oraz adres końcowy danego obszaru (zakładam, że znamy adresy początku –heapStart–i końca stosu–heapEnd):

void SearchMemory(unsigned char* startPrt, unsigned char* endPtr)
{
   //Ustaw wskaźnik na początek obszaru
   unsigned int* ptr = (unsigned int*)startPrt;
   unsigned char* ptrVal;
   unsigned char* realBlockPtr;
   Header* h;

   while((unsigned char*)ptr <= endPtr)
   { 
      //Odczytaj wartość pod wkaźnikiem 
      ptrVal = (unsigned char*)(*ptr);
      //Sprawdź, czy wartość wskaźnika pokazuje na stertę (optymalizujemy 
      //niepotrzebne przeszukiwanie bloków) 
      if((ptrVal > heapStart) && (ptrVal <= heapEnd)) 
      {
         //Przeglądnij wszystkie bloki 
         h = Mem_GetHead(); 
         while(0 != h) 
         {
            if(!h->IsUsed)
            {
               realBlockPtr = (unsigned char*)(h) + sizeof(Header);
               if(ptrVal == realBlockPtr)
               {
                  //Wartość pod wskaźnikiem odpowiada adresowi bloku -> 
                  //  oznaczamy jako użyty
                  h->IsUsed = TRUE;
                  break;
               }
            }
            h = h->Next;
         }
      }

      //Przesuń wskaźnik o odległość odpowiadającą rozmiarowi wskaźnika
      ptr += 1;
   }
}

Sprzątanie

Napiszemy teraz funkcję, która przejrzy wszystkie bloki oraz zwolni te nieużywane oraz główną funkcję sprzątającą. Struktura GarbageInfo agreguje informacje o sprzątanych danych.

void Collect(GarbageInfo* info)
{
   Header* block = Mem_GetHead();
   Header* prev = NULL;

   while(NULL != block)
   {
      if(!block->IsUsed)
      {
         prev = block->Prev;
         info->freedBytes += block->Size;
         info->freedBlocks += 1;

         //Zwolnienie pamięci bez blokowania
         justFree((unsigned char*)block + sizeof(Header));

         if(prev)
         {
            block = prev->Next;  
         }
         else
         {
            //Jeśli zwolniona została głowa listy, wracamy na nową głowę
            block = Mem_GetHead();
         }
      }
      else
      {
         block = block->Next;
      }
   }
}

Na samym końcu uzupełnimy kod o funkcję, która zostanie wywołana w celu odpalenia całego procesu sprzątania nieużytków. W tym momencie zakładamy, że funkcje pobierające adresy poszczególnych obszarów pamięci są zdefiniowane gdzieś w kodzie (GetStackBlock, GetStackCurrentSize, GetZeroInitializedStart, GetZeroInitializedEnd, GetReadWriteStart oraz GetReadWriteEnd).

int CollectGarbage(void)
{
   GarbageInfo info = {0};

   LOCK();

   //1 - Inicjalizacja
   MarkAllUnused();
   //2 – Stosy
   foreach(stack in stacks)
   {
      SearchMemory_Block(GetStackBlock(stack), GetStackCurrentSize(stack));
   }
   //3 – Zero Initialized
   SearchMemory(GetZeroInitializedStart(), GetZeroInitializedEnd());
   //4 – Read Write
   SearchMemory(GetReadWriteStart(), GetReadWriteEnd());
   //5 – Sterta
   SearchHeapMemory_Heap();
   //6 - Zwolnienie
   Collect(&info);

   UNLOCK();

   return info.freedBytes;
}

Zastosowanie

Oczywiście można by poświęcić ten paragraf na opis efektywnego sposobu na cykliczne wykonywanie sprzątania pamięci, wyzwalania Garbage Collectora jako następstwo szczególnych zdarzeń w programie, ale w tym artykule skupimy się tylko na dwóch praktycznych zastosowaniach.

Tropienie wycieków

W mojej pracy Garbage Collector służy do jednej rzeczy: szukania wycieków pamięci. Podstawowa funkcja śmieciarza, jaką jest sprzątanie „niedbale zarządzanej pamięci”, jest zbyt obciążająca dla systemu, na którym pracuję. Stąd też jedynym rozsądnym zastosowaniem jest diagnozowanie wycieków pamięci.
Wyciek pamięci to nic innego jak niezwolniona pamięć, do której nie ma już odwołania, co oznacza, że zaalokowany blok nie zostanie oznaczony jako używany. Jeśli taki blok posiadałby informację, w którym miejscu programu został utworzony mielibyśmy świetną wskazówkę do tego, gdzie wprowadzić poprawki. I tak też się dzieje! W dalszej części dodamy niezbędne informacje do bloków pamięci, aby uczynić z naszego śmieciarza wspaniałe narzędzie do debugowania kodu.

Wentyl bezpieczeństwa

Drugie z zastosowań, które chcieliśmy wdrożyć, to używanie Garbage Collectora jako swoistego „destruktora” lub wentylu bezpieczeństwa. Już wyjaśniam. Nasz system „chodzi spać”, co wiąże się z tym, że chwilę zanim przejdzie w stan czuwania wiele zmiennych jest zerowanych (wskaźniki ustawiane są na NULL) bez uprzedniego sprawdzania, na co wskazywały i czy czasem nie trzeba tego zwolnić. Jak łatwo się domyślić, nie jest to dobra praktyka, choć prawdopodobnie bierze się z tego, iż maszyna po wyjściu ze stanu czuwania resetuje całą pamięć operacyjną (ZI, RW, Heap), więc problem z niezwolnioną pamięcią nie zachodzi. Co innego, gdy maszyna uruchamiana jest ponownie bez przejścia w stan czuwania. Wtedy wyzerowane wskaźniki mogą prowadzić do wycieków pamięci.
Tak, złą praktyką jest pozostawienie tego faktu i zasypanie problemu wprowadzeniem Garbage Collectora. Jednakże może się okazać, że koszt jego wprowadzenia jest dużo niższy niż naprawienie wszystkich wycieków rozsianych po kodzie.
Sytuacje takie należy oceniać indywidualnie i osobiście nie polecam takiego podejścia. Rozważaliśmy tego rodzaju użycie w naszym projekcie, ale ostatecznie z niego zrezygnowaliśmy. Przytaczam je w tym artykule raczej jako odrębne spojrzenie na zagadnienie sprzątania pamięci.

Rozszerzenie o informacje debugowe

Dobrym pomysłem może okazać się rozszerzenie naszego sprzątacza o informację o dokładnym miejscu w kodzie, w którym nastąpiło zarezerwowanie danego bloku pamięci. To bardzo przydatna rzecz w przypadku tropienia wycieków pamięci. Jak można to zrobić? Na przykład rozszerzając listę argumentów funkcji myMalloc o plik i numer linii oraz dodając odpowiednie informowanie o zwalnianym bloku w funkcji Collect.

Modyfikacja Header (zakładam, że ścieżka do pliku to stała znakowa):

struct Header
{
   size_t         Size;   /* Rozmiar bloku                  */
   struct Header *Prev,   /* Lista bloków                   */
                 *Next;
   int            IsUsed;    /* Znacznik użycia                */
   int            IsScanned; /* Znacznik przeglądania          */
   unsigned long  Line;   /* Numer linii wywołania malloca  */
   unsigned char* File;   /* Plik źródłowy                  */
};
Modyfikacja myMalloc:
void* myMalloc(size_t size, const char *file, unsigned long line)
{
   LOCK();
   Header* header = malloc(sizeof(*header) + size);
   char* data = ((char*)header) + sizeof(*header);
   header->Size = size;
   header->Line = line;
   header->File = file;
   Mem_AddBlock(header);
   UNLOCK();
   return data;
}
#undef malloc
#define malloc(x) myMalloc(x, __FILE__, __LINE__)

__FILE__oraz __LINE__ to specjalne dyrektywy wstawiające w miejsca użycia odpowiednio ścieżkę do pliku oraz numer linii.

Modyfikację funkcji Collect należy dopasować pod własne potrzeby używając do logowania pól Line oraz File ze struktury Header.

Podsumowanie

W ramach niniejszego artykuły pokazane zostało w jaki sposób można zaimplementować prosty Garbage Collector dla systemu wbudowanego oraz opatrzeć go w przydatne informacje. Wiedza ta może przede wszystkim posłużyć jako inspiracja do napisania lub użycia Garbage Collectora w projektach czytelników.

Bibliografia

https://www.geeksforgeeks.org/mark-and-sweep-garbage-collection-algorithm/, Dostęp 2.01.2019

Related Posts

Comments

Cookies

This website stores cookies on your computer. These cookies are used to improve our website and provide more personalized services to you, both on this website and through other media. To find out more about the cookies we use, see our Cookies policy.