Czy „struct hack” jest technicznie niezdefiniowanym zachowaniem?


111

Pytam o dobrze znaną sztuczkę „ostatni element struktury ma zmienną długość”. To wygląda mniej więcej tak:

struct T {
    int len;
    char s[1];
};

struct T *p = malloc(sizeof(struct T) + 100);
p->len = 100;
strcpy(p->s, "hello world");

Ze względu na sposób, w jaki struktura jest umieszczona w pamięci, możemy nałożyć strukturę na większy niż to konieczne blok i traktować ostatni element tak, jakby był większy niż 1 charokreślony.

Zatem pytanie brzmi: czy ta technika jest technicznie niezdefiniowanym zachowaniem? . Spodziewałbym się, że tak, ale byłem ciekawy, co mówi o tym norma.

PS: Zdaję sobie sprawę z podejścia C99 do tego, chciałbym, aby odpowiedzi dotyczyły konkretnie wersji sztuczki wymienionej powyżej.


33
Wydaje się, że jest to całkiem jasne, rozsądne i przede wszystkim pytanie, na które można odpowiedzieć . Nie widząc powodu bliskiego głosowania.
cHao

2
Jeśli wprowadziłeś kompilator "ansi c", który nie obsługiwał hackowania struktury, większość programistów c, których znam, nie zaakceptowałaby, że twój kompilator "działał poprawnie". Pomimo tego, że zaakceptowaliby ścisłą lekturę normy. Komitet po prostu przeoczył jeden z nich.
dmckee --- kociak ex-moderator

4
@james Hack polega na umieszczeniu obiektu dostatecznie dużego dla tablicy, o której mowa, pomimo zadeklarowania minimalnej tablicy. Więc uzyskujesz dostęp do przydzielonej pamięci poza ścisłą definicją struktury. Pisanie poza przydziałem jest bezspornym błędem, ale różni się to od pisania w alokacji, ale poza „strukturą”.
dmckee --- ex-moderator kitten,

2
@James: Ogromny malloc ma tutaj kluczowe znaczenie. Zapewnia, że ​​istnieje pamięć --- pamięć z legalnym adresem i „będąca własnością” struktury (tj. Używanie jej przez jakąkolwiek inną jednostkę jest nielegalne) --- poza nominalnym końcem struktury. Zauważ, że oznacza to, że nie możesz użyć hackowania struktury na zmiennych automatycznych: muszą one być przydzielane dynamicznie.
dmckee --- kociak ex-moderator

5
@detly: łatwiej jest przydzielić / zwolnić jedną rzecz niż przydzielić / cofnąć przydział dwóch rzeczy, zwłaszcza, że ​​ta ostatnia ma dwa sposoby niepowodzenia, z którymi musisz sobie poradzić. Ma to dla mnie większe znaczenie niż krańcowe oszczędności kosztów / szybkości.
jamesdlin

Odpowiedzi:


52

Jak mówi C FAQ :

Nie jest jasne, czy jest to legalne czy przenośne, ale jest dość popularne.

i:

... oficjalna interpretacja uznała, że ​​nie jest on ściśle zgodny ze standardem C, chociaż wydaje się, że działa we wszystkich znanych implementacjach. (Kompilatory, które dokładnie sprawdzają granice tablic, mogą generować ostrzeżenia).

Uzasadnienie bitu `` ściśle zgodnego '' znajduje się w specyfikacji, sekcja J.2 Niezdefiniowane zachowanie , która obejmuje listę niezdefiniowanych zachowań:

  • Indeks tablicy jest poza zakresem, nawet jeśli obiekt jest pozornie dostępny z podanym indeksem (jak w wyrażeniu l-wartości a[1][7]podanym w deklaracji int a[4][5]) (6.5.6).

Paragraf 8 w sekcji 6.5.6 Operatory addytywne wspominają jeszcze o tym, że dostęp poza zdefiniowanymi granicami tablicy jest niezdefiniowany:

Jeżeli zarówno operand wskaźnika, jak i wynik wskazują na elementy tego samego obiektu tablicy lub jeden za ostatnim elementem obiektu tablicy, ocena nie powinna powodować przepełnienia; w przeciwnym razie zachowanie jest niezdefiniowane.


1
W kodzie OP p->snigdy nie jest używany jako tablica. Jest przekazywany do strcpy, w którym to przypadku rozpada się na zwykłą char *, co zdarza się wskazywać obiekt, który można zgodnie z prawem zinterpretować jako char [100];wewnątrz przydzielonego obiektu.
R .. GitHub STOP HELPING ICE

3
Być może innym sposobem spojrzenia na to jest to, że język mógłby ograniczyć sposób uzyskiwania dostępu do rzeczywistych zmiennych tablicowych, jak opisano w J.2, ale nie ma możliwości wprowadzenia takich ograniczeń dla obiektu przydzielonego przez malloc, gdy po prostu przekonwertowałeś zwracane void *do wskaźnika do [struktury zawierającej] tablicę. Nadal ważne jest, aby uzyskać dostęp do dowolnej części przydzielonego obiektu za pomocą wskaźnika do char(lub najlepiej unsigned char).
R .. GitHub STOP HELPING ICE

@R. - Widzę, że J2 może tego nie pokryć, ale czy nie jest to również objęte 6.5.6?
detly

1
Jasne, że tak! Informacje o typie i rozmiarze mogą być osadzone w każdym wskaźniku, a każda błędna arytmetyka wskaźnika mogłaby być wtedy pułapka - patrz np . CCured . Na poziomie bardziej filozoficznym nie ma znaczenia, czy żadna możliwa implementacja nie mogłaby cię złapać, jest to nadal niezdefiniowane zachowanie (iirc, istnieją przypadki niezdefiniowanego zachowania, które wymagałoby wyroczni, aby rozwiązać Problem z zatrzymaniem - i właśnie dlatego są nieokreślone).
zwol

4
Obiekt nie jest tablicą, więc 6.5.6 jest nieistotny. Obiekt jest blokiem pamięci przydzielonym przez malloc. Wyszukaj "obiekt" w standardzie, zanim wyrzucisz bs.
R .. GitHub STOP HELPING ICE

34

Uważam, że technicznie jest to niezdefiniowane zachowanie. Norma (prawdopodobnie) nie odnosi się do tego bezpośrednio, więc wchodzi w zakres „lub przez pominięcie jakiejkolwiek wyraźnej definicji zachowania”. klauzula (§4/2 z C99, §3.16 / 2 z C89), która mówi, że jest to niezdefiniowane zachowanie.

„Prawdopodobnie” powyżej zależy od definicji operatora indeksowania tablicy. W szczególności mówi: „Wyrażenie porostkowe, po którym następuje wyrażenie w nawiasach kwadratowych [], to indeksowane oznaczenie obiektu tablicy”. (C89, §6.3.2.1 / 2).

Możesz argumentować, że naruszane jest tutaj "obiektu tablicy" (ponieważ indeksujesz poza zdefiniowanym zakresem obiektu tablicy), w którym to przypadku zachowanie jest (odrobinę bardziej) jawnie niezdefiniowane, a nie tylko niezdefiniowane dzięki uprzejmości niczego, co ją definiuje.

Teoretycznie mogę sobie wyobrazić kompilator, który sprawdza granice tablicy i (na przykład) przerwałby program, jeśli / jeśli spróbujesz użyć indeksu spoza zakresu. W rzeczywistości nie wiem, czy coś takiego istnieje, a biorąc pod uwagę popularność tego stylu kodu, nawet jeśli kompilator próbował w pewnych okolicznościach wymusić indeksy dolne, trudno sobie wyobrazić, aby ktokolwiek mógł to znieść w ta sytuacja.


2
Mogę również wyobrazić sobie kompilator, który mógłby zdecydować, że jeśli tablica miałaby rozmiar 1, to arr[x] = y;mogłaby zostać przepisana jako arr[0] = y;; dla tablicy o rozmiarze 2, arr[i] = 4;może zostać przepisane jako i ? arr[1] = 4 : arr[0] = 4; Chociaż nigdy nie widziałem kompilatora wykonującego takie optymalizacje, w niektórych systemach wbudowanych mogą one być bardzo produktywne. Na PIC18x, używającym 8-bitowych typów danych, kod pierwszej instrukcji miałby szesnaście bajtów, drugi - dwa lub cztery, a trzeci - osiem lub dwanaście. Niezła optymalizacja, jeśli jest legalna.
supercat

Jeśli standard definiuje dostęp do tablicy poza granicami tablicy jako niezdefiniowane zachowanie, to hack strukturalny również jest. Jeśli jednak standard definiuje dostęp do tablicy jako cukier składniowy dla arytmetyki wskaźników ( a[2] == a + 2), to tak nie jest. Jeśli mam rację, wszystkie standardy C definiują dostęp do tablicy jako arytmatykę wskaźnika.
yyny,

13

Tak, jest to niezdefiniowane zachowanie.

Raport dotyczący defektów języka C nr 051 zawiera ostateczną odpowiedź na to pytanie:

Idiom, choć powszechny, nie jest ściśle zgodny

http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_051.html

W dokumencie uzasadnienia C99 komisja C dodaje:

Wiarygodność tej konstrukcji zawsze była wątpliwa. W odpowiedzi na jeden raport o usterkach Komitet uznał, że jest to nieokreślone zachowanie, ponieważ tablica p-> items zawiera tylko jedną pozycję, niezależnie od tego, czy istnieje przestrzeń.


2
+1 za znalezienie tego, ale nadal twierdzę, że jest to sprzeczne. Dwa wskaźniki do tego samego obiektu (w tym przypadku danego bajtu) są równe, a jeden wskaźnik do niego (wskaźnik do tablicy reprezentacji całego obiektu uzyskanego przez malloc) jest ważny w dodatku, więc jak można identyczny wskaźnik, uzyskane inną drogą, być nieważne w dodatku? Nawet jeśli chcą twierdzić, że jest to UB, to jest to bez znaczenia, ponieważ nie ma obliczeniowego sposobu, aby implementacja rozróżniła dobrze zdefiniowane użycie od rzekomo niezdefiniowanego użycia.
R .. GitHub STOP HELPING ICE

Szkoda, że ​​kompilatory C zaczęły zabraniać deklarowania tablic o zerowej długości; gdyby nie ten zakaz, wielu kompilatorów nie musiałoby wykonywać żadnych specjalnych czynności, aby działały tak, jak „powinny”, ale nadal byłyby w stanie kodować w specjalnych przypadkach dla tablic jednoelementowych (np. gdyby *foozawierały tablicy jednoelementowej boz, wyrażenie foo->boz[biz()*391]=9;można uprościć jako biz(),foo->boz[0]=9;). Niestety, odrzucanie przez kompilatory tablic zerowych oznacza, że ​​wiele kodu używa zamiast tego tablic jednoelementowych i zostanie zepsuty przez tę optymalizację.
supercat

11

Ten konkretny sposób robienia tego nie jest wyraźnie zdefiniowany w żadnym standardzie C, ale C99 zawiera „struct hack” jako część języka. W C99, ostatni element struktury może być „elastycznym składnikiem tablicy”, zadeklarowanym jako char foo[](z dowolnym typem, który chcesz zastąpić char).


Aby być pedantycznym, to nie jest hack strukturalny. Struct hack używa tablicy o stałym rozmiarze, a nie elastycznego elementu tablicy. Struct hack jest tym, o co pytano i to UB. Elastyczne składowe tablicy wydają się po prostu próbą uspokojenia ludzi, którzy widzieli w tym wątku narzekających na ten fakt.
underscore_d

7

Nie jest to zachowanie nieokreślone , niezależnie od tego, co mówi ktoś, urzędnik lub w inny sposób , ponieważ jest zdefiniowane przez standard. p->s, z wyjątkiem sytuacji, gdy jest używany jako lwartość, jest obliczany na wskaźnik identyczny z (char *)p + offsetof(struct T, s). W szczególności jest to prawidłowy charwskaźnik wewnątrz obiektu malloc, i istnieje 100 (lub więcej, zależnie od kwestii wyrównania) kolejnych adresów bezpośrednio po nim, które są również prawidłowe jako charobiekty wewnątrz przydzielonego obiektu. Fakt, że wskaźnik został wyprowadzony przy użyciu ->zamiast jawnego dodawania przesunięcia do wskaźnika zwróconego przez malloc, rzutowany do char *, jest nieistotny.

Technicznie rzecz biorąc, p->s[0]jest to pojedynczy element chartablicy wewnątrz struktury, kilka następnych elementów (np. p->s[1]Through p->s[3]) prawdopodobnie wypełnia bajty wewnątrz struktury, które mogą zostać uszkodzone, jeśli wykonasz przypisanie do struktury jako całości, ale nie jeśli uzyskasz dostęp tylko do poszczególnych członków, a pozostałe elementy to dodatkowe miejsce w przydzielonym obiekcie, z którego możesz dowolnie korzystać, o ile spełniasz wymagania dotyczące wyrównania (i charnie masz żadnych wymagań dotyczących wyrównania).

Jeśli obawiasz się, że możliwość nakładania się na bajty wypełniające w strukturze może w jakiś sposób wywołać demony nosowe, możesz tego uniknąć, zastępując 1in [1]wartością, która zapewnia, że ​​na końcu struktury nie ma wypełnienia. Prostym, ale marnotrawnym sposobem byłoby utworzenie struktury z identycznymi składowymi, z wyjątkiem braku tablicy na końcu, i użycie s[sizeof struct that_other_struct];jej jako tablicy. Następnie p->s[i]jest jasno zdefiniowany jako element tablicy w strukturze for i<sizeof struct that_other_structi jako obiekt char pod adresem następującym po końcu struktury for i>=sizeof struct that_other_struct.

Edycja: W rzeczywistości, w powyższej sztuczce, aby uzyskać odpowiedni rozmiar, może być również konieczne umieszczenie unii zawierającej każdy prosty typ przed tablicą, aby upewnić się, że sama tablica zaczyna się od maksymalnego wyrównania, a nie w środku wypełnienia innego elementu . Ponownie, nie uważam, aby to wszystko było konieczne, ale oferuję to dla najbardziej paranoicznych prawników językowych.

Edycja 2: Nakładanie się bajtów wypełniających zdecydowanie nie stanowi problemu, ze względu na inną część standardu. C wymaga, aby jeśli dwie struktury zgadzały się w początkowym podciągu ich elementów, dostęp do wspólnych elementów początkowych można uzyskać za pomocą wskaźnika do dowolnego typu. W konsekwencji, gdyby struct Tzadeklarowano strukturę identyczną z, ale z większą tablicą końcową, element s[0]musiałby pokrywać się z elementem s[0]in struct T, a obecność tych dodatkowych elementów nie mogłaby wpływać ani na nią nie wpływać dostęp do wspólnych elementów większej struktury używając wskaźnika do struct T.


4
Masz rację, że natura arytmetyki wskaźnika jest nieistotna, ale mylisz się co do dostępu poza zadeklarowany rozmiar tablicy. Zobacz N1494 (najnowsza publiczna wersja robocza C1x) sekcja 6.5.6 akapit 8 - nie możesz nawet robić dodawania, które zabiera wskaźnik więcej niż jeden element za zadeklarowany rozmiar tablicy i nie możesz go wyłuskać, nawet jeśli to tylko jeden element przeszłości.
zwol

1
@Zack: to prawda, jeśli obiekt jest tablicą. Nie jest prawdą, jeśli obiekt jest obiektem przydzielonym, przez mallocktóry jest uzyskiwany dostęp jako tablica, lub jeśli jest to większa struktura, do której można uzyskać dostęp za pośrednictwem wskaźnika do mniejszej struktury, której elementy są między innymi początkowym podzbiorem elementów większej struktury przypadkach.
R .. GitHub STOP HELPING ICE

6
+1 Jeśli mallocnie przydzieli zakresu pamięci, do którego można uzyskać dostęp za pomocą arytmetyki wskaźników, jaki by to był pożytek? A jeśli p->s[1]jest zdefiniowany przez standard jako cukier syntaktyczny dla arytmetyki wskaźnikowej, to ta odpowiedź po prostu potwierdza, że mallocjest użyteczna. Co zostało do omówienia? :)
Daniel Earwicker

3
Możesz argumentować, że jest dobrze zdefiniowany tak bardzo, jak chcesz, ale to nie zmienia faktu, że tak nie jest. Standard jest bardzo jasny, jeśli chodzi o dostęp poza granice tablicy, a granica tej tablicy jest 1. To jest właśnie takie proste.
Wyścigi lekkości na orbicie

3
@R .. myślę, że twoje założenie, że dwa wskaźniki porównujące równe sobie muszą zachowywać się tak samo, jest błędne. Rozważ int m[1]; int n[1]; if(m+1 == n) m[1] = 0;założenie, że ifwpisano gałąź. To jest UB (i nie gwarantuje się zainicjowania n) zgodnie z 6.5.6 p8 (ostatnie zdanie), tak jak to czytałem. Związane z: 6.5.9 p6 z przypisem 109. (Odniesienia do C11 n1570.) [...]
mafso

7

Tak, jest to technicznie niezdefiniowane zachowanie.

Zwróć uwagę, że istnieją co najmniej trzy sposoby implementacji „struct hack”:

(1) Zadeklarowanie końcowej tablicy o rozmiarze 0 (najbardziej „popularny” sposób w starszym kodzie). Jest to oczywiście UB, ponieważ deklaracje tablic o rozmiarze zerowym są zawsze nielegalne w C. Nawet jeśli się kompiluje, język nie gwarantuje zachowania jakiegokolwiek kodu naruszającego ograniczenia.

(2) Deklarowanie tablicy o minimalnym dozwolonym rozmiarze - 1 (Twój przypadek). W tym przypadku każda próba wzięcia wskaźnika p->s[0]i użycia go do arytmetyki wskaźników, która wykracza poza p->s[1]to, jest zachowaniem niezdefiniowanym. Na przykład implementacja debugowania może tworzyć specjalny wskaźnik z osadzonymi informacjami o zakresie, który będzie przechwytywał za każdym razem, gdy spróbujesz utworzyć wskaźnik poza p->s[1].

(3) Zadeklarowanie tablicy o „bardzo dużym” rozmiarze , na przykład 10000. Chodzi o to, że deklarowany rozmiar powinien być większy niż cokolwiek, czego możesz potrzebować w praktyce. Ta metoda jest wolna od UB w odniesieniu do zakresu dostępu do tablicy. Jednak w praktyce oczywiście zawsze będziemy alokować mniejszą ilość pamięci (tylko tyle, ile naprawdę potrzeba). Nie jestem pewien co do legalności tego, tj. Zastanawiam się, jak legalne jest przydzielanie mniejszej ilości pamięci dla obiektu niż zadeklarowany rozmiar obiektu (zakładając, że nigdy nie uzyskamy dostępu do „nieprzydzielonych” elementów członkowskich).


1
W (2) s[1]nie jest niezdefiniowanym zachowaniem. To to samo *(s+1), co, czyli to samo co *((char *)p + offsetof(struct T, s) + 1), które jest prawidłowym wskaźnikiem do a charw przydzielonym obiekcie.
R .. GitHub STOP HELPING ICE

Z drugiej strony jestem prawie pewien, że (3) to niezdefiniowane zachowanie. Za każdym razem, gdy wykonujesz jakąkolwiek operację, która zależy od takiej struktury znajdującej się pod tym adresem, kompilator może wygenerować kod maszynowy, który czyta z dowolnej części struktury. Może to być bezużyteczne lub może być funkcją bezpieczeństwa do ścisłego sprawdzania alokacji, ale nie ma powodu, dla którego implementacja nie mogłaby tego zrobić.
R .. GitHub STOP HELPING ICE

R: Jeśli zadeklarowano, że tablica ma rozmiar (nie jest to tylko foo[]cukier syntaktyczny *foo), wówczas każdy dostęp poza mniejszym z zadeklarowanego rozmiaru i przydzielony rozmiar to UB, niezależnie od tego, jak wykonano arytmetykę wskaźnika.
zwol

1
@Zack, mylisz się w kilku sprawach. foo[]w strukturze nie jest cukrem syntaktycznym *foo; jest to elastyczny element tablicy C99. Co do reszty, zobacz moją odpowiedź i komentarze do innych odpowiedzi.
R .. GitHub STOP HELPING ICE

6
Problem polega na tym, że niektórzy członkowie komitetu desperacko chcą, aby ten „hack” był UB, ponieważ wyobrażają sobie jakąś bajkową krainę, w której implementacja C mogłaby wymusić granice wskaźnika. Jednak na lepsze lub gorsze byłoby to sprzeczne z innymi częściami standardu - rzeczy takie jak możliwość porównania wskaźników dla równości (jeśli granice zostałyby zakodowane w samym wskaźniku) lub wymóg, aby każdy obiekt był dostępny za pośrednictwem wyimaginowanej nałożonej unsigned char [sizeof object]tablicy . Podtrzymuję moje twierdzenie, że „hack” elementu elastycznej tablicy dla wersji sprzed C99 ma dobrze zdefiniowane zachowanie.
R .. GitHub STOP HELPING ICE

3

Standard jest całkiem jasny, że nie możesz uzyskać dostępu do rzeczy poza końcem tablicy. (i przechodzenie przez wskaźniki nie pomaga, ponieważ nie możesz nawet zwiększać wskaźników poza jeden po końcu tablicy).

I za „pracę w praktyce”. Widziałem, jak optymalizator gcc / g ++ używa tej części standardu, generując w ten sposób niewłaściwy kod, gdy spełnia ten nieprawidłowy C.


czy możesz podać przykład?
Tal

1

Jeśli kompilator akceptuje coś takiego jak

typedef struct {
  int len;
  char dat [];
};

Myślę, że jest całkiem jasne, że musi być gotowy do zaakceptowania indeksu dolnego „dat” poza jego długością. Z drugiej strony, jeśli ktoś koduje coś takiego:

typedef struct {
  int cokolwiek;
  char dat [1];
} MY_STRUCT;

a później uzyskuje dostęp do somestruct-> dat [x]; Nie sądzę, aby kompilator był zobowiązany do używania kodu obliczającego adresy, który będzie działał z dużymi wartościami x. Myślę, że gdyby ktoś chciał być naprawdę bezpieczny, właściwy paradygmat byłby bardziej następujący:

# zdefiniować LARGEST_DAT_SIZE 0xF000
typedef struct {
  int cokolwiek;
  char dat [LARGEST_DAT_SIZE];
} MY_STRUCT;

a następnie wykonaj malloc (sizeof (MYSTRUCT) -LARGEST_DAT_SIZE + pożądana_długość_tablicy) bajtów (pamiętając, że jeśli pożądana_długość_tablicy jest większa niż LARGEST_DAT_SIZE, wyniki mogą być nieokreślone).

Nawiasem mówiąc, myślę, że decyzja o zakazaniu tablic o zerowej długości była niefortunna (niektóre starsze dialekty, takie jak Turbo C, obsługują ją), ponieważ tablicę o zerowej długości można uznać za znak, że kompilator musi wygenerować kod, który będzie działał z większymi indeksami .

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.