Oryginalna odpowiedź
{
void *mem = malloc(1024+16);
void *ptr = ((char *)mem+16) & ~ 0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);
}
Naprawiono odpowiedź
{
void *mem = malloc(1024+15);
void *ptr = ((uintptr_t)mem+15) & ~ (uintptr_t)0x0F;
memset_16aligned(ptr, 0, 1024);
free(mem);
}
Wyjaśnienie zgodnie z prośbą
Pierwszym krokiem jest przydzielenie wystarczającej ilości wolnego miejsca, na wszelki wypadek. Ponieważ pamięć musi być wyrównana do 16 bajtów (co oznacza, że początkowy adres bajtu musi być wielokrotnością 16), dodanie 16 dodatkowych bajtów gwarantuje, że mamy wystarczająco dużo miejsca. Gdzieś w pierwszych 16 bajtach znajduje się 16-bajtowy wyrównany wskaźnik. (Należy pamiętać, że malloc()ma powrócić wskaźnik, który jest dostatecznie dobrze wyrównany dla dowolnego . Celów, jednak sens „każdy” jest przede wszystkim na takie rzeczy jak podstawowe typy - long, double, long double, long long., A wskaźniki do obiektów i wskaźniki do funkcji Kiedy jesteś robiąc bardziej wyspecjalizowane rzeczy, np. grając z systemami graficznymi, mogą wymagać bardziej rygorystycznego dostosowania niż reszta systemu - stąd takie pytania i odpowiedzi).
Następnym krokiem jest konwersja wskaźnika pustki na wskaźnik char; Niezależnie od GCC, nie powinieneś wykonywać arytmetyki wskaźnika na pustych wskaźnikach (a GCC ma opcje ostrzegania, aby poinformować cię, gdy nadużyjesz). Następnie dodaj 16 do wskaźnika początkowego. Załóżmy, że malloc()zwrócił ci niemożliwie źle ustawiony wskaźnik: 0x800001. Dodanie 16 daje 0x800011. Teraz chcę zaokrąglić w dół do granicy 16 bajtów - więc chcę zresetować ostatnie 4 bity na 0. 0x0F ma ostatnie 4 bity ustawione na jeden; dlatego ~0x0Fma wszystkie bity ustawione na jeden oprócz ostatnich czterech. Po dodaniu 0x800011 otrzymujemy 0x800010. Możesz iterować po innych odsunięciach i zobaczyć, że działa ta sama arytmetyka.
Ostatnim krokiem free()jest proste: zawsze i tylko, powrót do free()wartości, która z jednej malloc(), calloc()lub realloc()zwrócone do siebie - nic innego nie jest katastrofą. Podałeś poprawnie, memaby zachować tę wartość - dziękuję. Bezpłatny wydaje to.
Wreszcie, jeśli wiesz o wewnętrznych mallocelementach pakietu systemu , możesz zgadywać, że może on zwrócić 16-bajtowe dane (lub może być 8-bajtowe). Jeśli byłby wyrównany do 16 bajtów, nie musiałbyś mrugać z wartościami. Jest to jednak podejrzane i nieprzenośne - inne mallocpakiety mają różne minimalne wyrównania, a zatem zakładanie jednej rzeczy, gdy robi coś innego, prowadziłoby do zrzutów rdzenia. W szerokich granicach to rozwiązanie jest przenośne.
Ktoś inny wymieniony posix_memalign()jako inny sposób na uzyskanie wyrównanej pamięci; nie jest to dostępne wszędzie, ale często można je wdrożyć, wykorzystując to jako podstawę. Zauważ, że wygodnie było, aby wyrównanie miało moc 2; inne dopasowania są bardziej chaotyczne.
Jeszcze jeden komentarz - ten kod nie sprawdza, czy alokacja się powiodła.
Poprawka
Programista Windows zauważył, że nie można wykonywać operacji maskowania bitów na wskaźnikach, i rzeczywiście GCC (testowane 3.4.6 i 4.3.1) tak narzeka. Tak więc następuje poprawiona wersja kodu podstawowego - przekonwertowana na program główny. Jak już wspomniano, mogłem również dodać tylko 15 zamiast 16. Używam, uintptr_todkąd C99 jest wystarczająco długi, aby był dostępny na większości platform. Gdyby nie do użycia PRIXPTRw printf()instrukcjach, wystarczyłoby użyć #include <stdint.h>zamiast #include <inttypes.h>. [Ten kod zawiera poprawkę wskazaną przez CR , która przypominała punkt, który Bill K po raz pierwszy przedstawił kilka lat temu, a który udało mi się przeoczyć do tej pory.]
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void memset_16aligned(void *space, char byte, size_t nbytes)
{
assert((nbytes & 0x0F) == 0);
assert(((uintptr_t)space & 0x0F) == 0);
memset(space, byte, nbytes); // Not a custom implementation of memset()
}
int main(void)
{
void *mem = malloc(1024+15);
void *ptr = (void *)(((uintptr_t)mem+15) & ~ (uintptr_t)0x0F);
printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
memset_16aligned(ptr, 0, 1024);
free(mem);
return(0);
}
A oto wersja nieco bardziej uogólniona, która będzie działać dla rozmiarów o sile 2:
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void memset_16aligned(void *space, char byte, size_t nbytes)
{
assert((nbytes & 0x0F) == 0);
assert(((uintptr_t)space & 0x0F) == 0);
memset(space, byte, nbytes); // Not a custom implementation of memset()
}
static void test_mask(size_t align)
{
uintptr_t mask = ~(uintptr_t)(align - 1);
void *mem = malloc(1024+align-1);
void *ptr = (void *)(((uintptr_t)mem+align-1) & mask);
assert((align & (align - 1)) == 0);
printf("0x%08" PRIXPTR ", 0x%08" PRIXPTR "\n", (uintptr_t)mem, (uintptr_t)ptr);
memset_16aligned(ptr, 0, 1024);
free(mem);
}
int main(void)
{
test_mask(16);
test_mask(32);
test_mask(64);
test_mask(128);
return(0);
}
Aby przekształcić test_mask()w funkcję alokacji ogólnego przeznaczenia, pojedyncza wartość zwrotna z alokatora musiałaby zakodować adres wydania, jak wskazało kilka osób w swoich odpowiedziach.
Problemy z ankieterami
Uri skomentował: Może mam dziś rano problem ze zrozumieniem czytania, ale jeśli pytanie z wywiadu wyraźnie mówi: „Jak byś przydzielił 1024 bajty pamięci” i wyraźnie przydzielisz więcej. Czy nie byłaby to automatyczna porażka ankietera?
Moja odpowiedź nie pasuje do komentarza złożonego z 300 znaków ...
To chyba zależy. Myślę, że większość ludzi (w tym ja) przyjęła pytanie w znaczeniu „Jak byś przydzielił przestrzeń, w której można przechowywać 1024 bajty danych, a adres podstawowy to wielokrotność 16 bajtów”. Jeśli ankieter naprawdę miał na myśli, jak można przydzielić 1024 bajty (tylko) i ustawić 16 bajtów na wyrównanie, wówczas opcje są bardziej ograniczone.
- Oczywiście jedną z możliwości jest przydzielenie 1024 bajtów, a następnie nadanie temu adresowi „traktowania wyrównania”; problem z tym podejściem polega na tym, że rzeczywista dostępna przestrzeń nie jest właściwie określona (przestrzeń użyteczna wynosi od 1008 do 1024 bajtów, ale nie był dostępny żaden mechanizm określania, który rozmiar), co czyni ją mniej niż użyteczną.
- Inną możliwością jest zapisanie pełnego alokatora pamięci i upewnienie się, że zwracany blok 1024-bajtowy jest odpowiednio wyrównany. W takim przypadku prawdopodobnie wykonasz operację dość podobną do tego, co zrobiło proponowane rozwiązanie, ale ukryjesz ją w alokatorze.
Jeśli jednak ankieter oczekiwałby jednej z tych odpowiedzi, spodziewałbym się, że rozpozna, że to rozwiązanie odpowiada na ściśle powiązane pytanie, a następnie ponownie sformułuje swoje pytanie, aby skierować rozmowę we właściwym kierunku. (Ponadto, jeśli ankieter stałby się naprawdę niespokojny, to nie chciałbym pracy; jeśli odpowiedź na niewystarczająco precyzyjne wymaganie zostanie zestrzelona w płomieniach bez korekty, to ankieter nie jest kimś, dla kogo można bezpiecznie pracować).
Świat się rozwija
Tytuł pytania zmienił się ostatnio. Było Rozwiązać wyrównanie pamięci w C pytanie wywiad, które stumped mnie . Zmieniony tytuł ( Jak przydzielić wyrównaną pamięć tylko przy użyciu biblioteki standardowej? ) Wymaga nieco zmienionej odpowiedzi - ten dodatek ją zawiera.
Dodano funkcję C11 (ISO / IEC 9899: 2011) aligned_alloc():
7.22.3.1 aligned_allocFunkcja
Streszczenie
#include <stdlib.h>
void *aligned_alloc(size_t alignment, size_t size);
Opis przestrzeń przydziela funkcyjne dla obiektu, który jest określony przez dopasowanie , której wielkość jest określona , a którego wartość jest nieokreślona. Wartość powinna być poprawnym dopasowaniem popartym wdrożeniem, a wartość będzie całkowitą wielokrotnością .
aligned_allocalignmentsizealignmentsizealignment
Zwraca
The aligned_alloczwraca albo wskaźnik NULL lub wskaźnik do przydzielonej przestrzeni.
POSIX definiuje posix_memalign():
#include <stdlib.h>
int posix_memalign(void **memptr, size_t alignment, size_t size);
OPIS
posix_memalign()Funkcja powinna przydzielić sizebajtów wyrównane do granicy określonej przez alignment, i zwraca wskaźnik do przydzielonej pamięci w memptr. Wartość alignmentbędzie potęgą dwóch wielokrotności sizeof(void *).
Po pomyślnym zakończeniu wartość wskazywana przez memptrbędzie wielokrotnością alignment.
Jeśli wielkość żądanego miejsca wynosi 0, zachowanie jest zdefiniowane w implementacji; zwracana wartość memptrto wskaźnik zerowy lub wskaźnik niepowtarzalny.
free()Funkcja powinna cofnąć przydział pamięci, który został wcześniej przydzielony przez posix_memalign().
WARTOŚĆ ZWRACANA
Po pomyślnym zakończeniu posix_memalign()zwraca zero; w przeciwnym razie zwracany jest numer błędu w celu wskazania błędu.
Można użyć jednego lub obu z nich, aby odpowiedzieć na pytanie teraz, ale tylko funkcja POSIX była opcją, gdy pierwotnie udzielono odpowiedzi na pytanie.
Za kulisami nowa funkcja pamięci wyrównanej wykonuje dokładnie to samo zadanie, co przedstawione w pytaniu, z tym wyjątkiem, że ma możliwość łatwiejszego wymuszenia wyrównania i śledzenia wewnętrznego początku wyrównanej pamięci, aby kod nie mam do czynienia szczególnie - zwalnia pamięć zwróconą przez użytą funkcję alokacji.