Posts tagged ‘C/C++’

Stos wywołań funkcji

2008-06-13 13:42

Jedną z bardziej przydatnych informacji podczas znajdowania przyczyn błędów wykonania jest śledzenie stosu (stack trace; właściwie to nie ma dobrego polskiego tłumaczenia, jak zwykle zresztą :]). Dzięki niemu możemy mieć informacje o kolejnych wywołaniach funkcji, które doprowadziły błędu wykonania. Zwykle stack trace jest dostępny z poziomu złapanego obiektu wyjątku – np. poprzez właściwość System.Exception.StackTrace w .NET czy metody java.lang.Throwable.get/printStackTrace w Javie.

Standardowa klasa exception w C++ nie posiada podobnej funkcjonalności, bo w tym języku stos nie jest automatycznie śledzony. Przy pewnym wysiłku możemy aczkolwiek zapewnić sobie podobną funkcjonalność – chociażby tak:

  1. typedef std::list<std::string> StackTrace;
  2.  
  3. class Trace
  4. {
  5.     private:
  6.         static StackTrace ms_Trace;
  7.  
  8.     public:
  9.         Trace(const std::string& item) { ms_Trace.push_back (item); }
  10.         ~Trace()    { ms_Trace.pop_back(); }
  11.  
  12.     friend const StackTrace& GetStackTrace()    { return ms_Trace; }
  13. };
  14. StackTrace Trace::ms_Trace;    // inicjalizacja pola statycznego (w .cpp)
  15.  
  16. // makro (dla Visual C++)
  17. #define GUARD Trace __trace(__FUNCTION__ " [" __FILE__ ", line " __LINE__ "]")

Przechowujemy po prostu globalną listę z danymi wszystkich wywoływanych funkcji. Elementy do niej dodawane są przy wejściu w każdą funkcję, która na początku ma makro GUARD:

  1. int Foo() { GUARD; /* ... */ }

zaś zdejmowane wtedy, gdy pomocniczy obiekt typu Trace wyjdzie poza swój lokalny zasięg – czyli po opuszczeniu funkcji. To sprawia, że na liście mamy zawsze informacje o wszystkich wywołaniach funkcji prowadzących do aktualnego miejsca (jakie one są, zależy od kompilatora; użyte wyżej makro __FUNCTION__ nie jest na przykład standardową częścią C++). Tworząc obiekt wyjątku, możemy więc zapisać kopię tej listy, by można ją było odczytać w bloku catch i wyświetlić.
Rozwiązanie nie jest oczywiście bardzo ładne, bo wymaga dodatkowej linijki w każdej funkcji. Zdaje się jednak, że nie ma żadnego sposobu, by tę niedogodność wyeliminować. Ja przynajmniej takiego nie znam :)

Tags: , , ,
Author: Xion, posted under Programming » 11 comments

Kontenery haszujące w Visual C++

2008-06-11 21:10

W standardowej bibliotece pojemników (STL) języka C++ jest póki co poważny brak. Nie ma mianowicie kontenerów opierających się na mechanizmie haszowania (hashing), znanego też pod mniej jednoznaczną nazwą mieszania. Mówiąc zupełnie najprościej, takie pojemniki są pewnym uogólnieniem zwykłych tablic, które nie są jednak indeksowane liczbami całkowitymi, a kluczami dowolnego typu. Klucze te są jednak wpierw przepuszczane przez pewną funkcję (funkcję haszującą) i dopiero wynik używany jest do znalezienia wartości, z którą ów klucz jest związany. Istnieje też kilka metod rozwiązywania problemu kolizji, gdy kilka kluczy zostanie odwzorowanych na to samo miejsce w tablicy.
Zaletą haszowania jest szybkość: średnio dostęp do wartości związanej z danym kluczem jest wykonywanym w czasie stałym. Tak, stałym, czyli O(1). Jakkolwiek można być pesymistą i przewidywać, że przy odpowiednio złośliwym doborze kluczy czas ten urośnie do liniowego (O(n), ale w praktyce tablice haszujące zachowują się świetnie. No a to jest przecież najważniejsze :)

W STL nie ma jednak kontenerów używających haszowania. Mimo to wiele kompilatorów oferuje je we własnym zakresie. I tak nasz ulubiony Visual C++ udostępnia dwa “półstandardowe” nagłówki: hash_set i hash_map. Zawierają one klasy (multi)map oraz (multi)zbiorów, z wierzchu wyglądających właściwie identycznie jak zwykłe mapy i zbiory (std::map i std::set) z STL. Klasy te nazywają się hash_set, hash_map, itp., i celem zachowania zgodności ze standardem C++ umieszczone są nie w przestrzeni std, lecz stdext.

O istnieniu tych klas warto pamiętać, gdy tworzymy kod kluczowy pod względem wydajności. W programowaniu gier często są to na przykład przeróżne menedżery zasobów, które odwzorowują pewne identyfikatory (np. łańcuchy znaków) na obiekty w rodzaju modeli, tekstur, próbek dźwiękowych, itd. Szybkość działania przechowujących je pojemników może być ważna i warto poszukać alternatyw dla standardowej klasy map (która przecież teoretycznie “wyciąga” tylko O(logn) dla wyszukiwania). Jeśli przy okazji martwimy się przenośnością na inne kompilatory niż VC++ lub zgodnością ze standardem, to możemy spróbować przełączania między zwykłymi a haszującymi pojemnikami, np. tak:

  1. #if defined(_MSC_VER) && !defined(STANDARD_COMPLIANCE)
  2.     typedef stdext::hash_map<std::string, Object*> ResourceManagerMap;
  3. #else
  4.     typedef std::map<std::string, Object*> ResourceManagerMap;
  5. #endif

Naturalnie ‘kod niezależny od kontenera’ to dość często utopia, ale przy korzystaniu tylko z prostych operacji typu wstawianie-usuwanie-wyszukiwanie nie powinniśmy napotkać większych problemów.

Tags: , , ,
Author: Xion, posted under Uncategorized » 3 comments

Statyczne składowe i takież konstruktory

2008-06-04 23:30

Wiadomo, że konstruktor to specjalna metoda, która jest wywoływana przy tworzeniu nowego obiektu i ma za zadanie go zainicjalizować. Okazuje się, że w innej wersji “konstruktor” (albo coś, co go przypomina) może służyć do inicjalizacji nie obiektu, lecz samej klasy. A co takiego ma klasa, że należy czasem zadbać o jej prawidłową inicjalizację? Ano chociażby składowe statyczne – wspólne dla wszystkich obiektów.
W C# możemy sobie zdefiniować statyczny konstruktor, który może się tym zająć – jak również (niemal) czymkolwiek innym. Taki konstruktor, podobnie jak zwykły ma postać metody o tej samej co klasa nazwie, lecz jest opatrzony modyfikatorem static. Zostaje on wywołany przed stworzeniem pierwszego obiektu klasy lub próbą dostępu do jakiejkolwiek składowej statycznej. Całkiem praktyczne, prawda?
Coś podobnego ma również Java, a zwie się to oryginalnie ‘statycznym inicjalizatorem’. W odróżnieniu od wariantu z C#, inicjalizator ten jest wywoływany wcześniej – już w momencie załadowania klasy przez maszynę wirtualną. Właściwie jednak nie ma to wielkiego znaczenia, bo efekt jest analogiczny: jeśli ów inicjalizator ma zrobić coś przed pierwszym użyciem klasy, na pewno zostanie to zrobione. Jego kod pisze się w definicji klasy, w bloku otoczonym nawiasami klamrowymi i opatrzonym – a jakże – słówkiem static.

A jak pod tym względem wypada C++? No cóż, jak zwykle blado :) Kruczkiem standardu jest fakt, że wszelkie składowe statyczne klas mają niezdefiniowaną kolejność inicjalizacji, jeśli są przypisane do odrębnych modułów (plików .cpp). Jeśli więc takie składowe zależą od siebie, to wynikiem mogą być tylko kłopoty.
Poradzić na to można dwojako – zależnie od tego, którą zaletę statycznych konstruktorów chcemy wykorzystać. Jeżeli na przykład chcemy, aby jakaś zmienna statyczna lub globalna była zainicjowana niezależnie od tego, gdzie i kiedy chcemy ją użyć, najlepiej uczynić ją lokalną statyczną zmienną w funkcji:

  1. Foo& GetFoo() { static Foo foo; return foo; }

Jeśli z kolei musimy mieć pewność, że przed stworzeniem obiektu naszej klasy zostaną wykonane jakieś dodatkowe czynności, to możemy to częściowo osiągnąć za pomocą statycznej flagi:

  1. class Foo
  2. {
  3.     public:
  4.         Foo()
  5.         {
  6.             if (!ms_bInitialized)
  7.             {
  8.                   // (czynności konieczne przed użyciem klasy)
  9.                   ms_bInitialized = true;
  10.             }
  11.         }
  12. };
  13. Foo::ms_bInitialized = false;

Niezależnie jednak od tego, co jest nam akurat potrzebne, nie powinniśmy nigdy zapominać o rozważeniu zależności między składowymi statycznymi klas i/lub zmiennymi globalnymi w naszym kodzie, jeśli chcemy uniknąć niezdefiniowanego zachowania. Bo wtedy po prostu wszystko się zdarzyć może :]

Tags: , , , ,
Author: Xion, posted under Programming » 3 comments

Struktury danych nieobecne w .NET

2008-05-31 16:00

Programując z użyciem platformy .NET można niekiedy mieć wrażenie, że jest w niej niemal wszystko. Oczywiście takie przekonanie jest nietrwałe: wystarczy bowiem znaleźć coś, co być w niej mogłoby (a zwłaszcza coś, co występuje w innych, podobnych bibliotekach), a czego jednak nie ma. Nietrudno zauważyć, że takich rzeczy jest mimo wszystko większość – bo w sumie nie może być przecież inaczej :)
Niektóre braki są aczkolwiek bardziej dotkliwe niż inne. Należą do nich chociażby luki w systemie kolekcji obiektów, czyli – mówiąc ogólniej – wszelkiego rodzaju struktur danych. W .NET brakuje bowiem takich rzeczy jak:

Niektóre pojemniki w .NET 2.0
Niedużo tego…
  • Zbiory. Wprawdzie niemal każdy pojemnik zawiera metodę Contains o wiadomym przeznaczeniu, jednak tylko kontenery słownikowe sprawdzają unikalność umieszczanych w nich obiektów. Te zaś zasadniczo służą do czegoś innego: mapowania jednych obiektów na inne. Brakuje więc zwykłej, prostej klasy Set z operacjami dodawania, usuwania i wyszukiwania elementów – odpowiednika std::set z STL.
  • Kolejki priorytetowe (priority queues). Tutaj znowu można je symulować przy pomocy klas typu SortedDictionary, które jednak nie są zasadniczo do tego przeznaczone. Kolejka priorytetowa powinna mieć przecież niemal identyczny interfejs do zwykłej kolejki FIFO (czyli głównie metody Push i Pop), bo różnica polega wyłącznie na porządku zwracanych elementów, określonym przez ich porównania.
  • Kolekcje zbiorów rozłącznych (disjoint sets). Te dość specyficzne struktury danych są przydatne wtedy, gdy musimy szybko zorganizować kolekcję obiektów w osobne podgrupy wedle jakichś kryteriów. Można to oczywiście zrobić za pomocą dowolnych pojemników, tyle że będzie to nieefektywne. Dedykowana implementacja z użyciem wydajnych algorytmów (tzw. łączenia według rangi i kompresji ścieżek) byłaby znacznie bardziej na miejscu.
  • Grafy. Wprawdzie grafy nie są aż tak często wykorzystywane, ale nie da się ukryć, że czasami ich użycie jest konieczne. Na pewno nie zaszkodziłoby posiadanie ich jako wbudowanego feature‘a w każdej bibliotece struktur danych. Zwłaszcza z gotowym zestawem podstawowych algorytmów grafowych.

Tę listę można by oczywiście ciągnąć bardzo długo, ale zdecydowałem się ograniczyć do tych czterech rzeczy z dwóch powodów. Po pierwsze, przynajmniej raz zdarzyło się, że potrzebowałem którejś z wymienionych tutaj struktur w .NET i byłem zmuszony poradzić sobie we własnym zakresie. Po drugie, bez problemu można podać przykłady innych bibliotek, języków czy środowisk, gdzie jedna z nich, większość lub nawet wszystkie są obecne. Najlepszym przykładem jest C++ (z STL) uzupełniony o bibliotekę Boost, który pod względem struktur danych prezentuje się w tej postaci naprawdę potężnie.
Nie widzę więc specjalnych usprawiedliwień dla faktu, że w .NET lista standardowych struktur prezentuje się nadzwyczaj skromnie. Może więc zamiast dodawać w nowych wersjach platformy kolejne wątpliwej jakości “usprawnienia” – jak wyrażenia lambda wbudowane w C# czy zabawki typu LINQ – programiści Microsoftu zajęliby się raczej zaniedbanymi dotąd podstawami?…

Tags: , , ,
Author: Xion, posted under Programming » 3 comments

Tej funkcji brakuje ‘n’

2008-05-29 15:01

W dzisiejszych niebezpiecznych czasach niemal każdy program może stać się przedmiotem ataku, za pomocą którego można – jak to się zwykło mówić w żargonie speców od bezpieczeństwa – “wykonać dowolny kod” (execute arbitrary code). Chyba najbardziej znanym exploitem tego typu jest przepełnienie bufora (buffer overflow), które w najprostszym wypadku może dotyczyć na przykład takiej sytuacji jak poniższa:

  1. int some_function()
  2. {
  3.     char buf[BUF_SIZE];
  4.     do_something_and_give_results (buf, ...);
  5. }

Gdy bowiem bufor rezyduje na stosie, a jakaś funkcja przypadkowo “wyjedzie” poza jego zakres, możliwe jest nadpisanie innej części stosu. Jedną z nich może być odkładany przy wywołaniu każdej funkcji adres powrotu. Po zakończeniu działania kodu funkcji, adres ten jest zdejmowany ze stosu i program skacze pod uzyskane w ten sposób miejsce w pamięci. Dzięki temu wykonanie programu może wrócić do miejsca tuż za wywołaniem funkcji i kontynuować działanie. Jeśli jednak ów adres zostanie nadpisany przez exploit, możemy w rezultacie skoczyć pod zupełnie inny adres i wykonać dowolny – potencjalnie szkodliwy – kod.

Dlatego też nie należy nigdy ślepo zakładać, że przekazywane nam tablice będą zawsze wystarczająco duże na pomieszczenie rezultatów funkcji. Powinniśmy na to zwrócić baczną uwagę zwłaszcza wtedy, gdy mamy zapisać w buforze dane pochodzące z zewnątrz – z pliku, sieci, od użytkownika, itd. Pisząc funkcje operujące na buforach będących tablicami w C, powinniśmy więc zawsze dodawać do nich jeszcze jeden parametr: rozmiar przekazywanego bufora. Oczywiście nalezy potem dbać, aby go nie przekroczyć.
A co z już istniejącymi funkcjami C, jak sprintf, strcpy, gets?… Wszystkie aktualne dokumentacje do kompilatorów, w których funkcje te występują (MSDN, linuksowy man, itp.), solidnie przestrzegają przed potencjalnym przepełnieniem bufora, które może być skutkiem ich używania. Zwykle też podawane są bezpieczne alternatywy, do których przekazuje się rozmiar bufora: w Visual C++ są one oznaczone końcówką _s (np. sprintf_s), a w GNU GCC dodatkową literką n w nazwie (np. snprintf). To ich właśnie należy używać, jeśli występuje potencjalna możliwość przepełnienia bufora.

Wyjątkiem jest gets, której to… nie powinniśmy w ogóle używać :) Co ciekawe, tylko MSDN wspomina o jej bezpiecznym odpowiedniku (gets_s). Pod GCC funkcji gets po prostu permanentnie brakuje n ;-]

Tags: , ,
Author: Xion, posted under Programming » 5 comments

Artykuł o odśmiecaniu pamięci w C++

2008-05-23 13:52

W przypływie weny twórczej zrealizowałem pomysł na artykuł, który dotąd znajdował się na szczycie kolejki priorytetowej takich pomysłów. Opisuje on, jak można uzupełnić język C++ o prosty mechanizm odśmiecacza pamięci (garbage collector – GC), czyli modułu zajmującego się automatycznym zwalnianiem nieużywanych obiektów. Osoby programujące choć przez chwilę w Javie czy .NET wiedzą, że obecność GC jest bardzo wygodna, lecz dopóki nie powstanie standard C++0x, w naszym ulubionym języku programowania mechanizm nie będzie domyślnie obecny.

W artykule opisuję, jak można to naprawić, pisząc własną, prostą implementację odśmiecacza pamięci w C++. Zainteresowanych zapraszam do lektury – mam nadzieję, że warto :)

Tags:
Author: Xion, posted under Website » Comments Off on Artykuł o odśmiecaniu pamięci w C++

Cztery rodzaje operatora new

2008-05-20 21:04

Do alokowania pamięci (albo raczej: tworzenia obiektów na stercie) służy w C++ operator o wiele mówiącej nazwie new. Chociaż jest on powszechnie znany i nieustannie używany przez każdego programistę C++, pewni nie wszyscy wiedzą, że występuje on nie w jednej, ale aż w czterech odmianach, z których każda różni się sposobem wywołania!
Oto krótki przegląd:

  • “Zwykły” operator new (co obejmuje też formę tablicową new[]) jest oczywiście najbardziej znany i najczęściej stosowany. Warto pamiętać, że zazwyczaj robi on dwie rzeczy: oprócz alokacji pamięci wywołuje też konstruktor dla tworzonego obiektu (lub obiektów w tablicy), któremu możemy też podać parametry.
  • Przeciążony operator new zmienia natomiast swoje zachowanie tylko w zakresie tej pierwszej czynności, czyli samej alokacji. Ciekawostką jest to, że możemy wyposażyć go (tj. sam operator new) w dodatkowe parametry – czyli przeciążyć go w pełnym znaczeniu tego słowa! Typowym przykładem, jaki się tutaj zwykle przytacza, jest następująca funkcja:
    1. void* operator new (size_t bytes, char fill)
    2. {
    3.     // alokacja z wypełnieniem podanym wzorcem
    4.     char* p = ::new char[bytes];
    5.     for (size_t i = 0; i < bytes; ++i) p&#91;i] = fill;
    6.     return p;
    7. }&#91;/cpp]
    8. która tworzy przeciążoną wersję operatora <code>new</code>, wypełniającą świeżo zaalokowaną pamięć podanym wzorcem:
    9. [cpp]char* ptr = new('X') char[10];  // alokuje tablicę charów wypełnioną X-ami

    Naturalnie możliwe są bardziej przydatne zastosowania. Jeśli mamy na przykład kilka rozłącznych ze sobą stert, to możemy tak napisać operator new, by poprzez dodatkowy argument pozwalał decydować o tym, którą z nich chcemy w danym przypadku wybrać.

  • new nierzucający wyjątków. Domyślnie alokacja za pomocą new rzuca wyjątek std::badalloc, jeżeli operacja się nie powiodła (zwykle z powodu braku pamięci). To zachowanie – wymagające do poprawnej obsługi bloku try-catch może nam się nie podobać, ale na szczęście można je zmienić. Wystarczy użyć wersji new z dodatkowym parametrem std::nothrow:
    1. int* pEnormousArray = new(std::nothrow) int[0xffffffff]; // "tylko" 4GB :)

    Wymaga to jeszcze dołączenia standardowego pliku nagłówkowego o wielce trafnej nazwie new.

  • Ostatni rodzaj zwie się placement new, co nie ma żadnego specjalnie dobrego tłumaczenia na język polski. Użycie tego operatora wymaga podania wskaźnika na już zaalokowany kawałek pamięci. Działanie operatora new ogranicza się wtedy do skonstruowania obiektu w tym właśnie miejscu, na które pokazuje przekazany wskaźnik. Tak więc w tym przypadku new tak naprawdę niczego nie alokuje; jest to po prostu najzupełniej legalny sposób na wywołanie konstruktora bez robienia czegokolwiek innego. Jakkolwiek może to się wydawać przydatne, zdecydowanie odradzam korzystania z tego mechanizmu w sposób nieprzemyślany, bo można przy tym popełnić “ciekawe” błędy.

Mamy więc aż cztery różne warianty new, ale raczej nie powinno to rodzić dylematów w rodzaju “Który z nich wybrać?”. W praktyce i tak nieczęsto zachodzi potrzeba skorzystania z któregokolwiek poza pierwszym. Co nie znaczy rzecz jasna, że nie warto znać pozostałych – podobnie jak całej masy innych kruczków języka C++ :]

Tags: , ,
Author: Xion, posted under Programming » 4 comments
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.