Skąd darmo wie, ile kosztuje?

W programowaniu C możesz przekazać dowolny wskaźnik, który ci się podoba, jako argument do zwolnienia, skąd on zna wielkość przydzielonej pamięci do zwolnienia? Ilekroć przekazuję wskaźnik do jakiejś funkcji, muszę również przekazać rozmiar (tj. Tablica 10 elementów musi otrzymać 10 jako parametr, aby znać rozmiar tablicy), ale nie muszę przekazywać rozmiaru do darmowa funkcja. Dlaczego nie i czy mogę korzystać z tej samej techniki we własnych funkcjach, aby uchronić się przed koniecznością korzystania z dodatkowej zmiennej długości tablicy?

Kiedy dzwonisz malloc(), określasz ilość pamięci do przydzielenia. Rzeczywista ilość używanej pamięci jest nieco większa i zawiera dodatkowe informacje, które rejestrują (przynajmniej), jak duży jest blok. Nie możesz (wiarygodnie) uzyskać dostępu do tych innych informacji - i nie powinieneś :-).

Kiedy dzwonisz free(), po prostu patrzy na dodatkowe informacje, aby dowiedzieć się, jak duży jest blok.

Większość implementacji funkcji alokacji pamięci C będzie przechowywać informacje rozliczeniowe dla każdego bloku, w linii lub osobno.

Jednym typowym sposobem (w linii) jest faktyczne przydzielenie zarówno nagłówka, jak i pamięci, o którą prosiłeś, uzupełnionych do pewnego minimalnego rozmiaru. Na przykład, jeśli poprosiłeś o 20 bajtów, system może przydzielić blok 48-bajtowy:

• 16-bajtowy nagłówek zawierający rozmiar, specjalny znacznik, sumę kontrolną, wskaźniki do następnego / poprzedniego bloku i tak dalej.
• 32-bajtowy obszar danych (20 bajtów uzupełniono do wielokrotności 16).

Adres podany następnie jest adresem obszaru danych. Następnie, kiedy zwolnisz blok, freepo prostu weźmie podany adres i, zakładając, że nie upchnąłeś tego adresu lub pamięci wokół niego, sprawdź informacje księgowe bezpośrednio przed nim. Graficznie byłoby to następująco:

 ____ The allocated block ____
/                             \
+--------+--------------------+
| Header | Your data area ... |
+--------+--------------------+
          ^
          |
          +-- The address you are given

Należy pamiętać, że rozmiar nagłówka i wypełnienia są całkowicie zdefiniowane dla implementacji (właściwie cała rzecz jest zdefiniowana dla implementacji ^(a), ale powszechna jest opcja rozliczania w linii).

Sumy kontrolne i specjalne znaczniki, które istnieją w informacjach księgowych, są często przyczyną błędów, takich jak „uszkodzona arena pamięci” lub „podwójne zwolnienie”, jeśli je zastąpisz lub zwolnisz dwukrotnie.

Wypełnianie (aby zwiększyć efektywność alokacji) sprawia, że ​​czasami możesz pisać trochę poza końcem żądanego miejsca bez powodowania problemów (nadal nie rób tego, jest to niezdefiniowane zachowanie i tylko dlatego, że czasami działa, nie robi tego oznacza to, że można to zrobić).

^(a) Napisałem implementacje mallocsystemów wbudowanych, w których masz 128 bajtów bez względu na to, o co prosiłeś (był to rozmiar największej struktury w systemie), zakładając, że poprosiłeś o 128 bajtów lub mniej (prośby o więcej byłyby zostać spełniony z wartością NULL zwracaną). Bardzo prosta maska ​​bitowa (tj. Nie w linii) została użyta do podjęcia decyzji, czy porcja 128-bajtowa została przydzielona, ​​czy nie.

Inne, które opracowałem, miały różne pule dla fragmentów 16-bajtowych, fragmentów 64-bajtowych, fragmentów 256-bajtowych i 1K, ponownie za pomocą maski bitowej, aby zdecydować, które bloki zostały użyte lub dostępne.

Obie te opcje pozwoliły zmniejszyć obciążenie informacji księgowych oraz zwiększyć szybkość malloci free(nie trzeba łączyć sąsiednich bloków podczas uwalniania), szczególnie ważne w środowisku, w którym pracowaliśmy.

Z comp.lang.clisty najczęściej zadawanych pytań: Skąd darmo wie, ile bajtów do uwolnienia?

Implementacja malloc / free zapamiętuje rozmiar każdego bloku, ponieważ jest on przydzielany, więc nie trzeba przypominać mu o wielkości podczas zwalniania. (Zazwyczaj rozmiar jest zapisywany w sąsiedztwie przydzielonego bloku, dlatego rzeczy zwykle się psują, jeśli granice przydzielonego bloku są nawet nieco przekroczone)

Ta odpowiedź została przeniesiona z Skąd free () wie, ile pamięci należy zwolnić? gdzie najwidoczniej nie udało mi się odpowiedzieć na pozornie zdublowane pytanie. Ta odpowiedź powinna zatem odnosić się do tego duplikatu:

W przypadku mallocalokatora sterty przechowuje mapowanie oryginalnego zwróconego wskaźnika na odpowiednie szczegóły potrzebne do freepóźniejszego wczytania pamięci. Zazwyczaj obejmuje to przechowywanie wielkości obszaru pamięci w dowolnej formie odpowiedniej dla używanego alokatora, na przykład rozmiaru surowego lub węzła w drzewie binarnym używanym do śledzenia przydziałów lub liczby używanych „jednostek” pamięci.

freenie zawiedzie, jeśli „zmienisz nazwę” wskaźnika lub powielisz go w jakikolwiek sposób. Nie jest to jednak liczone odniesienie i tylko pierwszy freebędzie poprawny. Dodatkowe frees to błędy „podwójnego bezpłatnego”.

Próba freedowolnego wskaźnika o wartości innej niż zwracana przez poprzednie mallocs, a jak dotąd niewyleczona, jest błędem. Nie można częściowo zwolnić regionów pamięci zwróconych malloc.

W powiązanej notatce Biblioteka GLib ma funkcje alokacji pamięci, które nie zapisują niejawnego rozmiaru - a następnie przekazujesz parametr size, aby zwolnić. Może to wyeliminować część kosztów ogólnych.

malloc()i free()są zależne od systemu / kompilatora, więc trudno jest podać konkretną odpowiedź.

Więcej informacji na temat tego drugiego pytania .

Menedżer sterty przechowywał gdzieś pamięć należącą do przydzielonego bloku, gdy została wywołana malloc.

Sam go nigdy nie wdrożyłem, ale myślę, że pamięć bezpośrednio przed przydzielonym blokiem może zawierać meta informacje.

Oryginalną techniką było przydzielenie nieco większego bloku i zapisanie rozmiaru na początku, a następnie przekazanie aplikacji pozostałej części bloga. Dodatkowa przestrzeń zawiera rozmiar i ewentualnie linki do połączenia wolnych bloków w celu ponownego użycia.

Istnieją jednak pewne problemy z tymi sztuczkami, takie jak słaba pamięć podręczna i zachowanie zarządzania pamięcią. Używanie pamięci bezpośrednio w bloku ma tendencję do niepotrzebnego tworzenia stron, a także tworzy brudne strony, które komplikują udostępnianie i kopiowanie przy zapisie.

Tak więc bardziej zaawansowaną techniką jest prowadzenie osobnego katalogu. Opracowano także podejścia egzotyczne, w których obszary pamięci wykorzystują tę samą moc dwóch rozmiarów.

Ogólnie rzecz biorąc, odpowiedź brzmi: oddzielna struktura danych jest przypisana do zachowania stanu.

Aby odpowiedzieć na drugą połowę pytania: tak, możesz, a dość powszechny wzór w C jest następujący:

typedef struct {
    size_t numElements
    int elements[1]; /* but enough space malloced for numElements at runtime */
} IntArray_t;

#define SIZE 10
IntArray_t* myArray = malloc(sizeof(intArray_t) + SIZE * sizeof(int));
myArray->numElements = SIZE;

Kiedy nazywamy malloc, po prostu zużywa więcej bajtów od jego wymagań. To bardziej bajtowe zużycie zawiera informacje, takie jak suma kontrolna, rozmiar i inne dodatkowe informacje. Kiedy dzwonimy za darmo w tym czasie, bezpośrednio przechodzimy do tych dodatkowych informacji, w których znajduje się adres, a także znajduje się informacja o tym, ile bloków będzie wolne.

aby odpowiedzieć na drugie pytanie, tak, możesz (w pewnym sensie) skorzystać z tej samej techniki, jak malloc() po prostu przypisując pierwszą komórkę w każdej tablicy do rozmiaru tablicy. która pozwala wysłać tablicę bez wysyłania argumentu o dodatkowym rozmiarze.