Jaka jest potrzeba tablicy z zerowymi elementami?

122

W kodzie jądra Linuksa znalazłem następującą rzecz, której nie mogę zrozumieć.

 struct bts_action {
         u16 type;
         u16 size;
         u8 data[0];
 } __attribute__ ((packed));

Kod jest tutaj: http://lxr.free-electrons.com/source/include/linux/ti_wilink_st.h

Jaka jest potrzeba i cel tablicy danych bez elementów?

Jeegar Patel
źródło
Nie jestem pewien, czy powinny istnieć tablice o zerowej długości lub znacznik struct-hack ...
hippietrail
@hippietrail, ponieważ często gdy ktoś pyta, czym jest ta struktura, nie wie, że jest nazywana „elastycznym składnikiem tablicy”. Gdyby tak było, z łatwością mogliby znaleźć odpowiedź. Ponieważ tego nie robią, nie mogą oznaczyć pytania jako takiego. Dlatego nie mamy takiego tagu.
Shahbaz
10
Głosuj, aby ponownie otworzyć. Zgadzam się, że to nie był duplikat, ponieważ żaden z pozostałych postów nie dotyczy kombinacji niestandardowego "hackowania struktury" o zerowej długości i dobrze zdefiniowanego elementu tablicy C99 z elastycznym elementem. Myślę też, że dla społeczności programistów C zawsze korzystne jest rzucenie światła na niejasny kod z jądra Linuksa. Głównie dlatego, że wiele osób ma wrażenie, że jądro Linuksa jest rodzajem najnowocześniejszego kodu w C. z nieznanych powodów. Podczas gdy w rzeczywistości jest to straszny bałagan zalany niestandardowymi exploitami, których nigdy nie należy uważać za jakiś kanon C.
Lundin
5
To nie jest duplikat - nie pierwszy raz widziałem, jak ktoś niepotrzebnie zamykał pytanie. Myślę też, że to pytanie dodaje do bazy wiedzy SO.
Aniket Inge

Odpowiedzi:

139

Jest to sposób na posiadanie zmiennych rozmiarów danych bez konieczności dwukrotnego wywoływania malloc( kmallocw tym przypadku). Używałbyś tego w ten sposób:

struct bts_action *var = kmalloc(sizeof(*var) + extra, GFP_KERNEL);

Kiedyś to nie było standardowe i zostało uznane za włamanie (jak powiedział Aniket), ale tak było ustandaryzowane w C99 . Standardowy format to teraz:

struct bts_action {
     u16 type;
     u16 size;
     u8 data[];
} __attribute__ ((packed)); /* Note: the __attribute__ is irrelevant here */

Zwróć uwagę, że nie wspominasz o żadnym rozmiarze dla data pola. Zauważ również, że ta specjalna zmienna może pojawić się tylko na końcu struktury.


W C99 ta sprawa jest wyjaśniona w 6.7.2.1.16 (moje wyróżnienie):

W szczególnym przypadku ostatni element struktury z więcej niż jednym nazwanym elementem może mieć niekompletny typ tablicy; nazywa się to elastycznym składnikiem tablicy. W większości sytuacji elastyczny element tablicy jest ignorowany. W szczególności rozmiar struktury jest taki, jakby elastyczny element tablicy został pominięty, z wyjątkiem tego, że może on mieć więcej końcowego wypełnienia niż sugerowałoby to pominięcie. Jednak gdy. (lub ->) operator ma lewy operand, który jest (wskaźnikiem do) strukturą z elastycznym składnikiem tablicy i prawy operand nazywa ten element, zachowuje się tak, jakby ten element członkowski został zastąpiony najdłuższą tablicą (z tym samym typem elementu ), które nie spowodowałyby, że struktura byłaby większa niż obiekt, do którego uzyskiwany jest dostęp; przesunięcie tablicy powinno pozostać przesunięciem elastycznego elementu tablicy, nawet jeśli różni się od przesunięcia tablicy zastępczej. Gdyby ta tablica nie miała elementów,

Innymi słowy, jeśli masz:

struct something
{
    /* other variables */
    char data[];
}

struct something *var = malloc(sizeof(*var) + extra);

Możesz uzyskać dostęp var->datado indeksów w formacie [0, extra). Zauważ, że sizeof(struct something)poda rozmiar uwzględniający tylko inne zmienne, tj. Daje datarozmiar 0.


Ciekawe może być również odnotowanie, w jaki sposób norma faktycznie podaje przykłady malloctakiej konstrukcji (6.7.2.1.17):

struct s { int n; double d[]; };

int m = /* some value */;
struct s *p = malloc(sizeof (struct s) + sizeof (double [m]));

Kolejną interesującą notą według standardu w tej samej lokalizacji jest (wyróżnienie moje):

zakładając, że wywołanie malloc powiedzie się, obiekt wskazywany przez p zachowuje się w większości przypadków tak, jakby p zostało zadeklarowane jako:

struct { int n; double d[m]; } *p;

(istnieją okoliczności, w których ta równoważność jest zerwana; w szczególności przesunięcia elementu d mogą nie być takie same ).

Shahbaz
źródło
Aby było jasne, oryginalny kod w pytaniu nadal nie jest standardowy w C99 (ani C11) i nadal byłby uważany za włamanie. Standaryzacja C99 musi pomijać powiązaną tablicę.
MM
Co [0, extra)?
SS Anne
36

W rzeczywistości jest to hack dla GCC ( C90 ).

Nazywa się to również hackowaniem struktury .

Więc następnym razem powiedziałbym:

struct bts_action *bts = malloc(sizeof(struct bts_action) + sizeof(char)*100);

Będzie to równoznaczne z powiedzeniem:

struct bts_action{
    u16 type;
    u16 size;
    u8 data[100];
};

Mogę stworzyć dowolną liczbę takich obiektów strukturalnych.

Aniket Inge
źródło
7

Chodzi o to, aby umożliwić umieszczenie tablicy o zmiennej wielkości na końcu struktury. Przypuszczalnie bts_actionjest to pakiet danych z nagłówkiem o stałym rozmiarze ( pola typei size) i składową o zmiennej wielkości data. Deklarując ją jako tablicę o długości 0, można ją indeksować tak jak każdą inną tablicę. Następnie przydzieliłbyś bts_actionstrukturę, powiedzmy o datarozmiarze 1024 bajtów , na przykład:

size_t size = 1024;
struct bts_action* action = (struct bts_action*)malloc(sizeof(struct bts_action) + size);

Zobacz także: http://c2.com/cgi/wiki?StructHack

sheu
źródło
2
@Aniket: Nie jestem do końca pewien, skąd wziął się ten pomysł.
sheu
w C ++ tak, w C, niepotrzebne.
amc
2
@sheu, wynika to z tego, że Twój styl pisania mallocsprawia, że ​​wielokrotnie się powtarzasz i jeśli kiedykolwiek rodzaj actionzmian, to musisz to wielokrotnie poprawiać. Porównaj dla siebie poniższe dwa, a będziesz wiedział: struct some_thing *variable = (struct some_thing *)malloc(10 * sizeof(struct some_thing));vs. struct some_thing *variable = malloc(10 * sizeof(*variable));Drugi jest krótszy, czystszy i wyraźnie łatwiejszy do zmiany.
Shahbaz,
5

Kod jest nieprawidłowy C ( zobacz to ). Jądro Linuksa, z oczywistych powodów, nie przejmuje się w najmniejszym stopniu przenośnością, więc wykorzystuje mnóstwo niestandardowego kodu.

To, co robią, to niestandardowe rozszerzenie GCC o rozmiarze tablicy 0. Napisałby program zgodny ze standardem u8 data[];i oznaczałoby to dokładnie to samo. Autorzy jądra Linuksa najwyraźniej uwielbiają robić rzeczy niepotrzebnie skomplikowane i niestandardowe, jeśli pojawi się taka opcja.

W starszych standardach C kończenie struktury pustą tablicą było nazywane „hackowaniem struktury”. Inni już wyjaśnili jego cel w innych odpowiedziach. Struct hack, w standardzie C90, był niezdefiniowanym zachowaniem i może powodować awarie, głównie dlatego, że kompilator C może dodać dowolną liczbę bajtów wypełniających na końcu struktury. Takie bajty wypełniające mogą kolidować z danymi, które próbowałeś „włamać” na końcu struktury.

GCC wcześnie wprowadziło niestandardowe rozszerzenie, aby zmienić to zachowanie z niezdefiniowanego na dobrze zdefiniowane. Standard C99 dostosował następnie tę koncepcję i każdy nowoczesny program w języku C może więc bez ryzyka korzystać z tej funkcji. Jest znany jako elastyczny element tablicy w C99 / C11.

Lundin
źródło
3
Wątpię, czy „jądro Linuksa nie zajmuje się przenośnością”. Może chodziło Ci o przenośność na inne kompilatory? Prawdą jest, że jest dość spleciony z funkcjami gcc.
Shahbaz
3
Niemniej jednak uważam, że ten konkretny fragment kodu nie jest kodem głównego nurtu i prawdopodobnie został pominięty, ponieważ jego autor nie zwrócił na niego większej uwagi. Licencja mówi o niektórych sterownikach instrumentów texas, więc jest mało prawdopodobne, że rdzenni programiści jądra zwrócili na to uwagę. Jestem prawie pewien, że programiści jądra stale aktualizują stary kod zgodnie z nowymi standardami lub nowymi optymalizacjami. Jest po prostu zbyt duży, aby mieć pewność, że wszystko zostanie zaktualizowane!
Shahbaz
1
@Shahbaz W „oczywistej” części miałem na myśli przenośność na inne systemy operacyjne, co oczywiście nie miałoby żadnego sensu. Ale wydaje się, że nie obchodzi ich też przenośność na inne kompilatory, używali tak wielu rozszerzeń GCC, że Linux prawdopodobnie nigdy nie zostanie przeniesiony na inny kompilator.
Lundin
3
@Shahbaz Jeśli chodzi o wszystko, co jest oznaczone jako Texas Instruments, sami TI są znani z tworzenia najbardziej bezużytecznego, gównianego, naiwnego kodu C, jakie kiedykolwiek widziano, w swoich notatkach do aplikacji dla różnych układów TI. Jeśli kod pochodzi z TI, wszystkie zakłady dotyczące możliwości interpretacji czegoś użytecznego są wyłączone.
Lundin
4
To prawda, że ​​linux i gcc są nierozłączne. Jądro Linuksa jest również dość trudne do zrozumienia (głównie dlatego, że system operacyjny i tak jest skomplikowany). Chodziło mi jednak o to, że nie jest miło powiedzieć „Autorzy jądra Linuksa najwyraźniej uwielbiają robić rzeczy niepotrzebnie skomplikowane i niestandardowe, jeśli taka opcja się ujawni” z powodu złej praktyki kodowania strony trzeciej .
Shahbaz
1

Innym zastosowaniem tablicy o zerowej długości jest nazwana etykieta wewnątrz struktury, aby pomóc w sprawdzaniu przesunięcia struktury w czasie kompilacji.

Załóżmy, że masz kilka dużych definicji struktur (obejmujących wiele linii pamięci podręcznej), które chcesz mieć pewność, że są wyrównane do granicy linii pamięci podręcznej zarówno na początku, jak iw środku, gdzie przecina granicę.

struct example_large_s
{
    u32 first; // align to CL
    u32 data;
    ....
    u64 *second;  // align to second CL after the first one
    ....
};

W kodzie możesz zadeklarować je używając rozszerzeń GCC takich jak:

__attribute__((aligned(CACHE_LINE_BYTES)))

Ale nadal chcesz się upewnić, że jest to wymuszane w czasie wykonywania.

ASSERT (offsetof (example_large_s, first) == 0);
ASSERT (offsetof (example_large_s, second) == CACHE_LINE_BYTES);

To działałoby dla pojedynczej struktury, ale byłoby trudno objąć wiele struktur, z których każda ma inną nazwę elementu członkowskiego do wyrównania. Najprawdopodobniej otrzymasz kod podobny do poniższego, w którym musisz znaleźć nazwy pierwszego członka każdej struktury:

assert (offsetof (one_struct,     <name_of_first_member>) == 0);
assert (offsetof (one_struct,     <name_of_second_member>) == CACHE_LINE_BYTES);
assert (offsetof (another_struct, <name_of_first_member>) == 0);
assert (offsetof (another_struct, <name_of_second_member>) == CACHE_LINE_BYTES);

Zamiast iść w ten sposób, możesz zadeklarować w strukturze tablicę o zerowej długości, działającą jako nazwana etykieta ze spójną nazwą, ale nie zajmującą żadnej spacji.

#define CACHE_LINE_ALIGN_MARK(mark) u8 mark[0] __attribute__((aligned(CACHE_LINE_BYTES)))
struct example_large_s
{
    CACHE_LINE_ALIGN_MARK (cacheline0);
    u32 first; // align to CL
    u32 data;
    ....
    CACHE_LINE_ALIGN_MARK (cacheline1);
    u64 *second;  // align to second CL after the first one
    ....
};

Wtedy kod asercji środowiska uruchomieniowego byłby znacznie łatwiejszy w utrzymaniu:

assert (offsetof (one_struct,     cacheline0) == 0);
assert (offsetof (one_struct,     cacheline1) == CACHE_LINE_BYTES);
assert (offsetof (another_struct, cacheline0) == 0);
assert (offsetof (another_struct, cacheline1) == CACHE_LINE_BYTES);
Wei Shen
źródło
Ciekawy pomysł. Tylko uwaga, że ​​tablice o długości 0 nie są dozwolone przez standard, więc jest to kwestia specyficzna dla kompilatora. Ponadto dobrym pomysłem może być zacytowanie definicji zachowania tablic o długości 0 w definicji struktury z gcc, przynajmniej po to, aby pokazać, czy może ona wprowadzić dopełnienie przed deklaracją, czy po niej.
Shahbaz