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

Jak mówi aluser w Ten wątek na forum :

Twój proces ma region pamięci, od adresu x do adresu y, nazywa się sterta. Wszystkie Twoje dane malloc ' d żyją w tym obszarze. malloc() przechowuje pewną strukturę danych, powiedzmy listę, wszystkich wolnych fragmentów miejsce w klasyfikacji generalnej. Kiedy dzwonisz do malloca, przegląda listę dla kawałek, który jest wystarczająco duży dla Ciebie, zwraca do niego wskaźnik i rejestruje fakt, że nie jest już wolny, jak również jak duży jest. Gdy wywołujesz free () z tym samym wskaźnikiem, free() wyświetla jak duże ten fragment jest i dodaje go z powrotem do listy wolnych fragmentów(). Jeśli wywołanie malloc () i nie może znaleźć wystarczająco dużego kawałka w stercie, to używa syscall brk () do zwiększenia sterty, tzn. zwiększenia adresu y i powoduje, że wszystkie adresy pomiędzy Starym y a nowym y są poprawne pamięć. brk () musi być syscall; nie ma sposobu, aby zrobić to samo całkowicie z przestrzeni użytkownika.

Malloc () jest systemem / kompilatorem zależny więc trudno dać konkretną odpowiedź. Zasadniczo jednak śledzi, jaka pamięć jest przydzielona i w zależności od tego, jak to robi, twoje połączenia do free mogą się nie powieść lub odnieść sukces.

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

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

1. pobranie bloku 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. gdy pojawia się wywołanie malloc, następuje odwołanie do listy, która wskazuje na bloki o odpowiedniej wielkości.
4. Ten blok jest zwracany, a nagłówki i stopki są aktualizowane odpowiednio.

Ochrona pamięci ma ziarnistość stron i wymaga interakcji jądra

Twój przykładowy kod zasadniczo pyta, dlaczego przykładowy program nie jest pułapką, 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 nią .. bez egzekwowania .. dowolne wielkości bloków, które często są znacznie mniejsze niż strony.

Pamięć może być usunięta z programu tylko w jednostkach stron, a nawet to jest mało prawdopodobne, aby być przestrzegane.

Calloc(3) i malloc(3) oddziałują z jądrem w celu uzyskania pamięci, jeśli to konieczne. Jednak większość implementacji free(3) nie zwraca pamięci do jądra¹, po prostu dodają go do wolnej listy, którą calloc() i malloc () skonsultują później w celu ponownego użycia wydanych bloków.

Nawet gdyby funkcja free() chciała zwrócić pamięć do systemu, potrzebowałaby co najmniej jednej sąsiadującej strony pamięci, aby jądro faktycznie chroniło region, więc zwolnienie małego bloku prowadziłoby do zmiany ochrony tylko wtedy, gdy byłby to ostatni mały blok na stronie.

Więc twój blok jest tam, siedzi na wolnej liście. Prawie zawsze możesz uzyskać dostęp do niego i pobliskiej pamięci, tak jakby była nadal przydzielona. C kompiluje bezpośrednio do kodu maszynowego i bez specjalnych uzgodnień debugowania nie ma kontroli rozsądku na ładunkach i magazynach. Teraz, jeśli spróbujesz uzyskać dostęp do wolnego bloku, zachowanie jest niezdefiniowane przez standard w celu nie stawiaj nieuzasadnionych wymagań implementatorom bibliotek. Jeśli spróbujesz uzyskać dostęp do wolnej pamięci lub meory poza przydzielonym blokiem, są różne rzeczy, które mogą pójść nie tak:

• czasami alokatory utrzymują oddzielne bloki pamięci, czasami używają nagłówka, który przydzielają tuż przed lub po bloku (chyba" stopka"), ale mogą chcieć użyć pamięci wewnątrz bloku w celu utrzymania wolnej listy połączonej ze sobą. Jeśli tak, twój odczyt bloku jest OK, ale jego zawartość może ulec zmianie, a zapis do bloku może spowodować niewłaściwe zachowanie lub awarię alokatora.
• naturalnie, Twój blok może zostać przydzielony w przyszłości, a wtedy prawdopodobnie zostanie nadpisany przez Twój kod lub procedurę biblioteczną lub z zerami przez calloc ().
• jeśli blok zostanie przeniesiony, może również zmienić jego rozmiar, w którym to przypadku kolejne linki lub inicjalizacja zostaną zapisane w różnych miejscach.
• oczywiście można odwołać się do tak daleko od Zakres, że przekroczysz granicę jednego z segmentów znanych z jądra Twojego programu i w tym jednym przypadku będziesz pułapką.

Teoria działania

^{1. Fakt, że bardzo niewiele implementacji free () próbuje powrót pamięci do systemu nie musi być spowodowany zwalnianiem się implementatorów. Interakcja z jądrem jest znacznie wolniejsza niż zwykłe wykonywanie kodu biblioteki, a korzyści byłyby niewielkie. Większość programów ma stały lub zwiększający się ślad pamięci, więc czas spędzony na analizowaniu sterty w poszukiwaniu pamięci zwrotnej byłby całkowicie zmarnowany. Inne powody obejmują fakt, że wewnętrzna fragmentacja sprawia, że bloki wyrównane do strony prawdopodobnie nie istnieją i jest prawdopodobne, że zwracanie block fragmentuje bloki po obu stronach. Wreszcie, kilka programów, które zwracają duże ilości pamięci, prawdopodobnie ominie malloc () i i tak po prostu przydzieli i zwolni strony.}

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

Kiedy przydzielasz 4 bajty, na przykład, malloc daje wskaźnik do 4 bajtów. Może nie zdajesz sobie sprawy, że pamięć 8-12 bajtów przed twoje 4 bajty są używane przez malloc do tworzenia łańcucha całej przydzielonej pamięci. Kiedy dzwonisz za darmo, zabiera twój wskaźnik, tworzy kopie zapasowe tam, gdzie są jego Dane i na tym działa.

Kiedy zwalniasz pamięć, malloc zdejmuje ten blok pamięci z łańcucha... i może, ale nie musi, przywró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 zachowa pamięć ( ponieważ ma inne rzeczy przydzielone w tej stronie, lub dla jakiejś optymalizacji), wtedy dostęp będzie działał. Nadal jest źle, ale może się udać.

DISCLAIMER: to, co opisałem, jest powszechną implementacją malloc, ale bynajmniej nie jedyną możliwą.

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

Połączenie do free może się zawiesić lub nie. Pamięć " po " 4 bajtach alokacji może być używana do czegoś innego przez implementację C lub C++. Jeśli jest używany do czegoś innego, to bazgranie na nim spowoduje, że to "coś innego" pójdzie nie tak, ale jeśli nie jest używany do niczego innego, może się zdarzyć, że ujdzie ci to na sucho. "Getting away with "może brzmieć dobrze, ale w rzeczywistości jest źle, ponieważ oznacza to, że Twój kod będzie działał dobrze, ale w przyszłości możesz nie ujść mu na sucho.

Z alokatorem pamięci w stylu debugowania, może się okazać, że została tam zapisana specjalna wartość straży, a free sprawdza ją i panikuje, jeśli jej nie znajdzie.

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

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

Jak działa malloc() i free() zależy od użytej biblioteki runtime. Ogólnie rzecz biorąc, malloc() przydziela stertę (blok pamięci) z systemu operacyjnego. Każde żądanie malloc() przydziela małą część tej pamięci zwracając wskaźnik do wywołującego. Procedury alokacji pamięci będą musiały przechowywać dodatkowe informacje o bloku przydzielonej pamięci, aby móc śledzić używaną i wolną pamięć na stercie. Informacja ta jest często przechowywana w kilku bajtach tuż przed wskaźnik zwracany przez malloc () i może być połączoną listą bloków pamięci.

Zapisując obok bloku pamięci przydzielonego przez malloc() najprawdopodobniej zniszczysz część informacji księgowych następnego bloku, który może być pozostałym nieużywanym blokiem pamięci.

Jednym z miejsc, w którym 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 uzyskać naruszenie dostępu, gdy próbujesz zapis do nieistniejącej pamięci.

To nie ma nic wspólnego z malloc i free. Twój program wykazuje nieokreślone zachowanie po skopiowaniu łańcucha-może się zawiesić w tym momencie lub w dowolnym momencie później. Byłoby to prawdą, nawet jeśli nigdy nie użyłeś malloc i free, i przydzieliłeś tablicę znaków na stosie lub statycznie.

Malloc i free są zależne od implementacji. Typowa implementacja polega na partycjonowaniu dostępnej pamięci do "wolnej listy" - połączonej listy dostępnych bloków pamięci. Wiele implementacji sztucznie dzieli go na małe i duże obiekty. Darmowe bloki zaczynają się od informacji o tym, jak duży jest blok pamięci i gdzie jest następny, itp.

Kiedy malloc, blok jest pobierany z wolnej listy. Po uwolnieniu blok zostaje ponownie umieszczony na wolnej liście. Są szanse, gdy nadpisujesz koniec wskaźnika, piszesz na nagłówku bloku na wolnej liście. Gdy zwalniasz pamięć, funkcja free() próbuje spojrzeć na następny blok i prawdopodobnie kończy się uderzeniem wskaźnika, który powoduje błąd magistrali.

Cóż to zależy od implementacji alokatora pamięci i systemu operacyjnego.

W systemie windows na przykład proces może poprosić o stronę lub więcej pamięci RAM. Następnie system operacyjny przypisuje te strony do procesu. Nie jest to jednak pamięć przypisana do aplikacji. Alokator pamięci CRT zaznaczy pamięć jako przylegający blok "dostępny". Alokator pamięci CRT zostanie następnie uruchomiony przez listę wolnych bloków i znajdzie najmniejszy możliwy blok, z którego może korzystać. Następnie będzie to trwało jako wiele z tego bloku, jak potrzebuje i dodać go do listy "przydzielonych". Dołączony do głowicy rzeczywistej alokacji pamięci będzie nagłówek. Nagłówek ten będzie zawierał różne informacje (może na przykład zawierać następny i poprzedni przypisany blok w celu utworzenia połączonej listy. Będzie najprawdopodobniej zawierać wielkość przydziału).

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

To nie jest prosty problem. Część alokatora systemu operacyjnego jest całkowicie poza Twoją kontrolą. Polecam przeczytać coś takiego jak Doug Lea Malloc (DLMalloc), aby zrozumieć, jak działa dość szybki alokator.

Edit: twoja awaria będzie spowodowana tym, że pisząc większe od nadpisanej alokacji następny nagłówek pamięci. W ten sposób, kiedy zwalnia, staje się bardzo zdezorientowany, co dokładnie jest free ' ingiem i jak połączyć się z następującym blokiem. Nie zawsze może to spowodować awarię od razu na wolności. Później może spowodować awarię. Ogólnie należy unikać nadpisywania pamięci!

Twój program zawiesza się, 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, możesz się rozbić, jeśli nie problem może pozostać ukryty przez długi czas i wrócić i ugryźć cię później.

Jeśli chodzi o malloc / darmową implementację-całe książki są poświęcone temu tematowi. Zasadniczo alokator pobrałby większe ilości pamięci z systemu operacyjnego i zarządzałby nimi za Ciebie. Niektóre z problemów, które alokator musi rozwiązać, to:

• Jak Pobierz nową pamięć
• jak go przechowywać - (lista lub inna struktura, wiele list dla fragmentów pamięci o różnej wielkości itd.)
• Co zrobić, jeśli użytkownik zażąda więcej pamięci niż obecnie dostępna (zażądać więcej pamięci z systemu operacyjnego, dołączyć niektóre z istniejących bloków, jak dokładnie je dołączyć, ... )
• co zrobić, gdy użytkownik zwolni pamięć
• debug allocators może dać ci większy fragment, o który prosiłeś i wypełnić go wzorem bajtów, gdy zwolnisz pamięć alokator może sprawdzić, czy zapisany jest poza blokiem (co prawdopodobnie dzieje się w Twoim przypadku) ...

Trudno powiedzieć, ponieważ rzeczywiste zachowanie jest różne między różnymi kompilatorami/środowiskami uruchomieniowymi. Nawet wersje debug/release zachowują się inaczej. Wersje debugujące VS2005 wstawiają znaczniki między przydziałami w celu wykrycia uszkodzeń pamięci, więc zamiast awarii, będą sprawdzane w funkcji free ().

Ważne jest również, aby zdać sobie sprawę, że po prostu przesunięcie wskaźnika przerwania programu za pomocą brk i sbrk w rzeczywistości nie przydziela Pamięci, tylko ustawia przestrzeń adresową. Na przykład w Linuksie pamięć będzie "wspierana" przez rzeczywiste fizyczne strony, gdy dostęp do tego zakresu adresów jest dostępny, co spowoduje błąd strony i ostatecznie doprowadzi do wywołania jądra do alokatora stron w celu uzyskania strony wspierającej.