Jak działają malloc () i free ()?

Chcę wiedzieć jak malloci freepracować.

int main() {
    unsigned char *p = (unsigned char*)malloc(4*sizeof(unsigned char));
    memset(p,0,4);
    strcpy((char*)p,"abcdabcd"); // **deliberately storing 8bytes**
    cout << p;
    free(p); // Obvious Crash, but I need how it works and why crash.
    cout << p;
    return 0;
}

Byłbym naprawdę wdzięczny, gdyby odpowiedź była dogłębnie na poziomie pamięci, jeśli to możliwe.

OK, niektóre odpowiedzi na temat malloc zostały już opublikowane.

Bardziej interesującą częścią jest to, w jaki sposób działa swobodnie (iw tym kierunku można również lepiej zrozumieć malloc).

W wielu implementacjach malloc / free, free zwykle nie zwraca pamięci do systemu operacyjnego (a przynajmniej tylko w rzadkich przypadkach). Powodem jest to, że dostaniesz luki w stosie, a zatem może się zdarzyć, że po prostu uzupełnisz swoją 2 lub 4 GB pamięci wirtualnej lukami. Należy tego unikać, ponieważ gdy tylko pamięć wirtualna zostanie ukończona, będziesz mieć naprawdę duże problemy. Innym powodem jest to, że system operacyjny może obsługiwać tylko te fragmenty pamięci, które mają określony rozmiar i wyrównanie. Mówiąc konkretnie: normalnie system operacyjny obsługuje tylko bloki, które może obsłużyć menedżer pamięci wirtualnej (najczęściej wielokrotności 512 bajtów, np. 4KB).

Zwrócenie 40 bajtów do systemu operacyjnego po prostu nie zadziała. Co robi free?

Wolny umieści blok pamięci na swojej własnej liście wolnych bloków. Zwykle próbuje także połączyć ze sobą sąsiednie bloki w przestrzeni adresowej. Lista wolnych bloków jest po prostu okrągłą listą fragmentów pamięci, które na początku zawierają pewne dane administracyjne. Jest to również powód, dla którego zarządzanie bardzo małymi elementami pamięci za pomocą standardowego malloc / free nie jest wydajne. Każda porcja pamięci wymaga dodatkowych danych, a przy mniejszych rozmiarach dochodzi do większej fragmentacji.

Bezpłatna lista jest także pierwszym miejscem, na które Malloc patrzy, gdy potrzebna jest nowa porcja pamięci. Jest skanowany przed wywołaniem nowej pamięci z systemu operacyjnego. Po znalezieniu fragmentu większego niż potrzebna pamięć jest on dzielony na dwie części. Jeden jest zwracany do osoby dzwoniącej, drugi z powrotem do wolnej listy.

Istnieje wiele różnych optymalizacji tego standardowego zachowania (na przykład w przypadku małych fragmentów pamięci). Ale ponieważ malloc i free muszą być tak uniwersalne, standardowe zachowanie jest zawsze rezerwą, gdy alternatywy nie są użyteczne. Istnieją również optymalizacje w obsłudze wolnej listy - na przykład przechowywanie porcji na listach posortowanych według rozmiarów. Ale wszystkie optymalizacje mają również swoje własne ograniczenia.

Dlaczego kod ulega awarii:

Powodem jest to, że pisząc 9 znaków (nie zapomnij końcowego bajtu zerowego) w obszarze o wielkości 4 znaków, prawdopodobnie nadpiszesz dane administracyjne przechowywane dla innej części pamięci znajdującej się „za” częścią danych ( ponieważ te dane są najczęściej przechowywane „przed” fragmentami pamięci). Gdy wolny, a następnie próbuje umieścić swoją część na bezpłatnej liście, może dotknąć tych danych administracyjnych, a zatem potknąć się o nadpisany wskaźnik. Spowoduje to awarię systemu.

To raczej pełne wdzięku zachowanie. Widziałem również sytuacje, w których niekontrolowany wskaźnik gdzieś nadpisał dane na liście wolnej pamięci, a system nie od razu się zawiesił, ale niektóre podprogramy później. Nawet w systemie o średniej złożoności takie problemy mogą być bardzo trudne do debugowania! W jednym przypadku, w który byłem zaangażowany, zajęło nam (większa grupa programistów) kilka dni, aby znaleźć przyczynę awarii - ponieważ była ona w zupełnie innym miejscu niż wskazane przez zrzut pamięci. To jest jak bomba zegarowa. Wiesz, twój następny „bezpłatny” lub „malloc” się zawiesi, ale nie wiesz dlaczego!

Są to jedne z najgorszych problemów C / C ++ i jeden z powodów, dla których wskaźniki mogą być tak problematyczne.

Jak mówi aluser w tym wątku na forum :

Twój proces ma region pamięci, od adresu x do adresu y, zwany stertą. Wszystkie twoje dane malloc'd żyją w tym obszarze. malloc () utrzymuje pewną strukturę danych, powiedzmy listę, wszystkich wolnych fragmentów miejsca na stercie. Kiedy wywołujesz Malloc, przegląda listę kawałka, który jest dla ciebie wystarczająco duży, zwraca do niego wskaźnik i zapisuje fakt, że nie jest już wolny, a także jego wielkość. Kiedy wywołujesz free () z tym samym wskaźnikiem, free () sprawdza, jak duży jest ten fragment i dodaje go z powrotem do listy wolnych fragmentów (). Jeśli wywołasz funkcję malloc () i nie może ona znaleźć wystarczająco dużej porcji w stercie, używa syscall brk () do zwiększenia stosu, tj. Zwiększa adres y i powoduje, że wszystkie adresy między starym y a nowym y być ważną pamięcią. brk () musi być syscall;

malloc () jest zależny od systemu / kompilatora, więc trudno jest podać konkretną odpowiedź. Zasadniczo jednak śledzi, jaka pamięć jest przydzielona i w zależności od tego, jak to robi, aby twoje połączenia na wolne mogły zakończyć się niepowodzeniem lub powodzeniem.

malloc() and free() don't work the same way on every O/S.

Jedna implementacja malloc / free wykonuje następujące czynności:

1. Uzyskaj blok pamięci z systemu operacyjnego poprzez sbrk () (wywołanie Unix).
2. Utwórz nagłówek i stopkę wokół tego bloku pamięci z pewnymi informacjami, takimi jak rozmiar, uprawnienia i gdzie znajduje się następny i poprzedni blok.
3. Kiedy pojawia się wezwanie do malloc, pojawia się lista, która wskazuje na bloki o odpowiednim rozmiarze.
4. Blok ten jest następnie zwracany, a nagłówki i stopki są odpowiednio aktualizowane.

Ochrona pamięci ma szczegółowość strony i wymagałaby interakcji jądra

Twój przykładowy kod zasadniczo pyta, dlaczego przykładowy program nie pułapkuje, a odpowiedź jest taka, że ​​ochrona pamięci jest funkcją jądra i dotyczy tylko całych stron, podczas gdy alokator pamięci jest funkcją biblioteki i zarządza… bez wymuszania… arbitralnie bloki wielkości, które często są znacznie mniejsze niż strony.

Pamięć można usunąć z programu tylko w jednostkach stron, a nawet to jest mało prawdopodobne.

calloc (3) i malloc (3) wchodzą w interakcje z jądrem, aby w razie potrzeby uzyskać pamięć. Ale większość implementacji free (3) nie zwraca pamięci do jądra ¹ , po prostu dodaje ją do wolnej listy, z którą później sprawdzą się calloc () i malloc () w celu ponownego wykorzystania zwolnionych bloków.

Nawet jeśli free () chciałby zwrócić pamięć do systemu, potrzebowałby co najmniej jednej ciągłej strony pamięci, aby jądro faktycznie chroniło region, więc zwolnienie małego bloku doprowadziłoby do zmiany ochrony, gdyby było ostatni mały blok na stronie.

Więc twój blok jest tam, siedząc na darmowej liście. Prawie zawsze możesz uzyskać do niego dostęp i pamięć znajdującą się w pobliżu, tak jakby nadal była przydzielona. C kompiluje bezpośrednio do kodu maszynowego i bez specjalnych ustaleń dotyczących debugowania nie ma kontroli poprawności ładunków i magazynów. Teraz, jeśli spróbujesz uzyskać dostęp do wolnego bloku, zachowanie nie jest zdefiniowane przez standard, aby nie stawiać nieuzasadnionych wymagań implementatorom bibliotek. Jeśli spróbujesz uzyskać dostęp do uwolnionej pamięci lub pamięci poza przydzielonym blokiem, mogą wystąpić różne rzeczy:

• Czasami alokatorzy utrzymują oddzielne bloki pamięci, czasem używają nagłówka, który przydzielają tuż przed lub po (chyba „stopka”) twojego bloku, ale po prostu mogą chcieć użyć pamięci w bloku w celu utrzymania wolnej listy połączone ze sobą. Jeśli tak, odczytanie bloku jest prawidłowe, ale jego zawartość może ulec zmianie, a zapisanie w bloku prawdopodobnie spowoduje nieprawidłowe działanie lub awarię programu przydzielającego.
• Oczywiście twój blok może zostać przydzielony w przyszłości, a następnie prawdopodobnie zostanie zastąpiony przez kod lub procedurę biblioteczną lub zerami przez calloc ().
• Jeśli blok zostanie ponownie przydzielony, może również zostać zmieniony jego rozmiar, w którym to przypadku w różnych miejscach zostanie zapisanych jeszcze więcej linków lub inicjalizacji.
• Oczywiście możesz odwoływać się tak daleko poza zasięgiem, że przekraczasz granicę jednego z segmentów znanych jądrze twojego programu, aw tym jednym przypadku pułapkę.

teoria operacji

Tak więc, pracując wstecz od twojego przykładu do ogólnej teorii, malloc (3) pobiera pamięć z jądra, kiedy tego potrzebuje, i zazwyczaj w jednostkach stron. Strony te są podzielone lub skonsolidowane zgodnie z wymogami programu. Malloc i free współpracują przy prowadzeniu katalogu. W miarę możliwości łączą sąsiednie wolne bloki, aby móc zapewnić duże bloki. Katalog może, ale nie musi, obejmować wykorzystanie pamięci w zwolnionych blokach do utworzenia listy połączonej. (Alternatywa jest nieco bardziej przyjazna dla pamięci współużytkowanej i przyjazna dla stronicowania, i obejmuje przydzielanie pamięci specjalnie dla katalogu.) Malloc i free mają niewielką, jeśli w ogóle, możliwość wymuszenia dostępu do poszczególnych bloków, nawet gdy specjalny i opcjonalny kod debugowania jest wkompilowany w program.

^{1. Fakt, że bardzo niewiele implementacji free () próbuje zwrócić pamięć do systemu, niekoniecznie wynika z opóźnień implementatorów. Interakcja z jądrem jest znacznie wolniejsza niż zwykłe wykonywanie kodu biblioteki, a korzyść byłaby niewielka. Większość programów ma stan ustalony lub zwiększa się pamięć, więc czas spędzony na analizie sterty w poszukiwaniu pamięci zwrotnej zostałby całkowicie zmarnowany. Inne powody to fakt, że fragmentacja wewnętrzna powoduje, że bloki wyrównane do strony prawdopodobnie nie istnieją, i jest prawdopodobne, że zwrócenie bloku spowoduje fragmentację bloków na obie strony. Wreszcie, kilka programów, które zwracają duże ilości pamięci, prawdopodobnie ominie malloc () i po prostu przydzieli i zwolni strony.}

Teoretycznie malloc pobiera pamięć z systemu operacyjnego dla tej aplikacji. Ponieważ jednak możesz chcieć tylko 4 bajty, a system operacyjny musi działać na stronach (często 4k), malloc robi coś więcej. Pobiera stronę i umieszcza tam własne informacje, dzięki czemu może śledzić to, co przydzieliłeś i uwolniłeś z tej strony.

Na przykład przy przydzielaniu 4 bajtów malloc daje wskaźnik do 4 bajtów. Być może nie zdajesz sobie sprawy z tego, że pamięć 8-12 bajtów przed twoimi 4 bajtami jest używana przez malloc do utworzenia łańcucha całej przydzielonej pamięci. Kiedy dzwonisz za darmo, bierze wskaźnik, tworzy kopię zapasową tam, gdzie są dane i działa na tym.

Kiedy zwalniasz pamięć, malloc usuwa blok pamięci z łańcucha ... i może zwrócić tę pamięć do systemu operacyjnego. Jeśli tak się stanie, dostęp do tej pamięci prawdopodobnie się nie powiedzie, ponieważ system operacyjny odbierze ci uprawnienia dostępu do tej lokalizacji. Jeśli malloc zachowuje pamięć (ponieważ ma inne rzeczy przydzielone na tej stronie lub dla pewnej optymalizacji), dostęp będzie działał. To nadal źle, ale może działać.

ZASTRZEŻENIE: To, co opisałem, jest powszechną implementacją malloc, ale w żadnym wypadku nie jedyną możliwą.

Twoja linia strcpy próbuje zapisać 9 bajtów, a nie 8, z powodu terminatora NUL. Wywołuje niezdefiniowane zachowanie.

Połączenie za darmo może zawieść lub nie. Pamięć „po” 4 bajtach alokacji może zostać wykorzystana na coś innego w implementacji C lub C ++. Jeśli zostanie wykorzystany do czegoś innego, wówczas bazgroły na nim spowoduje, że to „coś innego” pójdzie nie tak, ale jeśli nie zostanie użyte do niczego innego, może się zdarzyć, że ci się uda. „Ucieczka od tego” może zabrzmieć dobrze, ale w rzeczywistości jest złe, ponieważ oznacza, że ​​kod będzie działał poprawnie, ale w przyszłości może się nie udać.

W przypadku mechanizmu przydzielania pamięci w stylu debugowania może się okazać, że została tam zapisana specjalna wartość ochronna oraz że bezpłatne sprawdzanie tej wartości i panika, jeśli jej nie znajdzie.

W przeciwnym razie może się okazać, że kolejne 5 bajtów zawiera część węzła łącza należącą do innego bloku pamięci, który nie został jeszcze przydzielony. Uwolnienie bloku może wiązać się z dodaniem go do listy dostępnych bloków, a ponieważ nabazgrałeś w węźle listy, operacja ta może spowodować odłożenie wskaźnika o niepoprawnej wartości, powodując awarię.

Wszystko zależy od alokatora pamięci - różne implementacje używają różnych mechanizmów.

Sposób działania malloc () i free () zależy od użytej biblioteki wykonawczej. Ogólnie rzecz biorąc, malloc () przydziela stertę (blok pamięci) z systemu operacyjnego. Każde żądanie do malloc () następnie przydziela niewielką część tej pamięci, zwracając wskaźnik do dzwoniącego. Procedury alokacji pamięci będą musiały przechowywać dodatkowe informacje na temat przydzielonego bloku pamięci, aby móc śledzić zużytą i wolną pamięć na stercie. Informacje te są często przechowywane w kilku bajtach tuż przed wskaźnikiem zwróconym przez malloc () i może być połączoną listą bloków pamięci.

Pisząc obok bloku pamięci przydzielonego przez malloc () najprawdopodobniej zniszczysz niektóre informacje księgowe następnego bloku, który może być pozostałym nieużywanym blokiem pamięci.

Jednym z miejsc, w których program może również ulec awarii, jest kopiowanie zbyt wielu znaków do bufora. Jeśli dodatkowe znaki znajdują się poza stertą, możesz dostać naruszenie zasad dostępu podczas próby zapisu w nieistniejącej pamięci.

To nie ma nic wspólnego z Malloc i za darmo. Twój program wykazuje niezdefiniowane zachowanie po skopiowaniu łańcucha - może ulec awarii w tym momencie lub w dowolnym późniejszym momencie. Byłoby to prawdą, nawet jeśli nigdy nie używałeś malloc i free i przypisałeś tablicę char na stosie lub statycznie.

Malloc i free są zależne od implementacji. Typowa implementacja obejmuje podział dostępnej pamięci na „wolną listę” - połączoną listę dostępnych bloków pamięci. Wiele implementacji sztucznie dzieli go na małe i duże obiekty. Bezpłatne bloki zaczynają się od informacji o tym, jak duży jest blok pamięci i gdzie jest następny itd.

Kiedy malloc, blok jest wyciągany z bezpłatnej listy. Po zwolnieniu blok jest ponownie umieszczany na liście wolnych. Możliwe, że po zastąpieniu końca wskaźnika piszesz w nagłówku bloku na liście swobodnej. Kiedy zwolnisz pamięć, free () próbuje spojrzeć na następny blok i prawdopodobnie trafia we wskaźnik, który powoduje błąd magistrali.

To zależy od implementacji alokatora pamięci i systemu operacyjnego.

Na przykład w systemie Windows proces może poprosić o stronę lub więcej pamięci RAM. System operacyjny następnie przypisuje te strony do procesu. Nie jest to jednak pamięć przydzielona twojej aplikacji. Przydział pamięci CRT oznaczy pamięć jako ciągły „dostępny” blok. Następnie alokator pamięci CRT przejdzie przez listę wolnych bloków i znajdzie najmniejszy możliwy blok, którego może użyć. Następnie zajmie tyle bloków, ile potrzebuje i doda je do listy „przydzielonych”. Do nagłówka faktycznej alokacji pamięci zostanie dołączony nagłówek. Ten nagłówek będzie zawierał różne bity informacji (może na przykład zawierać następny i poprzedni przydzielony blok, aby utworzyć połączoną listę. Najprawdopodobniej będzie zawierał rozmiar przydziału).

Free usunie następnie nagłówek i doda go z powrotem do listy wolnej pamięci. Jeśli tworzy większy blok z otaczającymi go wolnymi blokami, zostaną one dodane razem, aby dać większy blok. Jeśli cała strona jest już wolna, program przydzielający najprawdopodobniej zwróci stronę do systemu operacyjnego.

To nie jest prosty problem. Część alokatora systemu operacyjnego jest całkowicie poza twoją kontrolą. Polecam przeczytanie czegoś takiego jak Malloc Douga Lei (DLMalloc), aby zrozumieć, jak działa dość szybki alokator.

Edycja: Twoja awaria będzie spowodowana faktem, że pisząc większy niż przydział, nadpisałeś następny nagłówek pamięci. W ten sposób, kiedy się uwolni, staje się bardzo zdezorientowane co do tego, czym dokładnie jest uwolnienie i jak połączyć się w następujący blok. Nie zawsze może to spowodować awarię natychmiast. Może to później spowodować awarię. Ogólnie rzecz biorąc, unikaj nadpisywania pamięci!

Twój program ulega awarii, ponieważ używał pamięci, która nie należy do ciebie. Może być używany przez kogoś innego lub nie - jeśli masz szczęście, rozbijesz się, jeśli nie, problem może pozostać ukryty przez długi czas i wrócić i ugryźć cię później.

Jeśli chodzi o wdrożenie malloc / free - całe książki poświęcone są temu tematowi. Zasadniczo program przydzielający pobierałby większe fragmenty pamięci z systemu operacyjnego i zarządzałby nimi za Ciebie. Niektóre problemy, które musi rozwiązać alokator, to:

• Jak zdobyć nową pamięć
• Jak go przechowywać - (lista lub inna struktura, wiele list dla fragmentów pamięci o różnych rozmiarach itd.)
• Co zrobić, jeśli użytkownik zażąda więcej pamięci niż obecnie dostępna (zażądaj więcej pamięci od systemu operacyjnego, dołącz do niektórych istniejących bloków, jak dokładnie je połączyć, ...)
• Co zrobić, gdy użytkownik zwolni pamięć
• Przydzielanie debugowania może dać ci większą część, o którą prosiłeś i wypełnienie jej wzorem bajtów, gdy zwolnisz pamięć, może sprawdzić, czy napisał poza blokiem (co prawdopodobnie dzieje się w twoim przypadku) ...

Trudno powiedzieć, ponieważ rzeczywiste zachowanie różni się w zależności od kompilatora / środowiska wykonawczego. Nawet kompilacje debugowania / wydawania mają inne zachowanie. Debugowanie kompilacji VS2005 wstawi znaczniki między przydziałami w celu wykrycia uszkodzenia pamięci, więc zamiast awarii, zapewni w free ().

Ważne jest również, aby zdawać sobie sprawę, że po prostu przesuwanie wskaźnika przerwania programu brki sbrknie przydział pamięci, po prostu konfiguruje przestrzeń adresową. Na przykład w systemie Linux pamięć będzie „wspierana” przez rzeczywiste strony fizyczne, gdy ten zakres adresów zostanie osiągnięty, co spowoduje błąd strony i ostatecznie doprowadzi do wywołania jądra przez program przydzielający strony w celu uzyskania strony pomocniczej.