Apakah "struct hack" secara teknis merupakan perilaku yang tidak terdefinisi?

111

Apa yang saya tanyakan adalah trik terkenal "anggota terakhir dari struct memiliki panjang variabel". Ini berjalan seperti ini:

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

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

Karena cara struct diletakkan dalam memori, kami dapat melapisi struct di atas blok yang lebih besar dari yang diperlukan dan memperlakukan anggota terakhir seolah-olah lebih besar dari yang 1 charditentukan.

Jadi pertanyaannya adalah: Apakah teknik ini secara teknis merupakan perilaku yang tidak terdefinisi? . Saya berharap begitu, tetapi penasaran apa yang dikatakan standar tentang ini.

PS: Saya mengetahui pendekatan C99 untuk ini, saya ingin jawaban menempel secara khusus pada versi trik seperti yang tercantum di atas.

Evan Teran
sumber
33
Ini sepertinya pertanyaan yang cukup jelas, masuk akal, dan di atas segalanya bisa dijawab . Tidak melihat alasan penutupan suara.
cHao
2
Jika Anda memperkenalkan kompilator "ansi c" yang tidak mendukung peretasan struct, sebagian besar pemrogram c yang saya tahu tidak akan menerima bahwa kompiler Anda "bekerja dengan benar". Meskipun demikian, mereka akan menerima pembacaan standar yang ketat. Panitia hanya melewatkan satu hal itu.
dmckee --- ex-moderator anak kucing
4
@james Hack tersebut bekerja dengan memallocing objek yang cukup besar untuk array yang Anda maksud, meskipun telah menyatakan array minimal. Jadi Anda mengakses memori yang dialokasikan di luar definisi yang ketat dari struct. Menulis melewati alokasi Anda adalah kesalahan yang tidak dapat dibantah, tetapi itu berbeda dengan menulis dalam alokasi Anda tetapi di luar "struct".
dmckee --- mantan moderator anak kucing
2
@ James: Malloc besar sangat penting di sini. Ini memastikan bahwa ada memori --- memori dengan alamat resmi dan dan 'dimiliki' oleh struktur (yaitu ilegal bagi entitas lain untuk menggunakannya) --- melewati akhir nominal struktur. Perhatikan bahwa ini berarti Anda tidak dapat menggunakan peretasan struct pada variabel otomatis: mereka harus dialokasikan secara dinamis.
dmckee --- mantan moderator anak kucing
5
@detly: Lebih mudah mengalokasikan / membatalkan alokasi satu hal daripada mengalokasikan / membatalkan alokasi dua hal, terutama karena yang terakhir memiliki dua cara gagal yang perlu Anda tangani. Ini lebih penting bagi saya daripada penghematan biaya / kecepatan marjinal.
jamesdlin

Jawaban:

52

Seperti yang dikatakan C FAQ :

Tidak jelas apakah itu legal atau portabel, tetapi cukup populer.

dan:

... interpretasi resmi menganggap bahwa ini tidak sepenuhnya sesuai dengan Standar C, meskipun tampaknya berfungsi di bawah semua implementasi yang diketahui. (Kompiler yang memeriksa batas array dengan hati-hati mungkin mengeluarkan peringatan.)

Alasan di balik bit 'yang benar-benar sesuai' ada dalam spesifikasi, bagian J.2 Perilaku tidak terdefinisi, yang mencakup dalam daftar perilaku yang tidak ditentukan:

  • Sebuah subskrip array berada di luar jangkauan, bahkan jika sebuah objek tampaknya dapat diakses dengan subskrip yang diberikan (seperti dalam ekspresi lvalue yang a[1][7]diberikan deklarasi int a[4][5]) (6.5.6).

Paragraf 8 dari Bagian 6.5.6 Operator aditif memiliki penyebutan lain bahwa akses di luar batas array yang ditentukan tidak ditentukan:

Jika kedua operan penunjuk dan hasil menunjuk ke elemen dari objek larik yang sama, atau melewati elemen terakhir dari objek larik, evaluasi tidak akan menghasilkan luapan; jika tidak, perilaku tidak terdefinisi.

Carl Norum
sumber
1
Dalam kode OP, p->stidak pernah digunakan sebagai array. Ini diteruskan ke strcpy, dalam hal ini meluruh ke dataran char *, yang kebetulan mengarah ke objek yang secara hukum dapat ditafsirkan sebagai char [100];di dalam objek yang dialokasikan.
R .. GitHub STOP HELPING ICE
3
Mungkin cara lain untuk melihat ini adalah bahwa bahasa tersebut dapat membatasi cara Anda mengakses variabel array yang sebenarnya seperti yang dijelaskan dalam J.2, tetapi tidak ada cara dapat membuat batasan seperti itu untuk objek yang dialokasikan malloc, ketika Anda hanya mengonversi yang dikembalikan void *ke pointer ke [sebuah struct berisi] sebuah array. Masih valid untuk mengakses bagian mana pun dari objek yang dialokasikan menggunakan penunjuk ke char(atau lebih disukai unsigned char).
R .. GitHub STOP HELPING ICE
@R. - Saya dapat melihat bagaimana J2 mungkin tidak mencakup ini, tetapi bukankah itu juga tercakup dalam 6.5.6?
detly
1
Tentu bisa! Informasi jenis dan ukuran dapat disematkan di setiap penunjuk, dan aritmatika penunjuk yang salah dapat dibuat untuk menjebak - lihat misalnya CCured . Pada tingkat yang lebih filosofis, tidak masalah apakah tidak ada implementasi yang bisa menangkap Anda, itu masih perilaku yang tidak terdefinisi (ada, iirc, kasus perilaku tidak terdefinisi yang akan membutuhkan ramalan agar Masalah Menghentikan untuk diselesaikan - itulah sebabnya mengapa mereka tidak ditentukan).
zwol
4
Objek tersebut bukan objek larik jadi 6.5.6 tidak relevan. Objek adalah blok memori yang dialokasikan oleh malloc. Cari "objek" dalam standar sebelum Anda mengeluarkan bs.
R .. GitHub STOP HELPING ICE
34

Saya percaya bahwa secara teknis ini adalah perilaku yang tidak terdefinisi. Standar (bisa dibilang) tidak membahasnya secara langsung, jadi itu termasuk di bawah "atau dengan menghilangkan definisi eksplisit apa pun dari perilaku." klausa (§4 / 2 dari C99, §3.16 / 2 dari C89) yang mengatakan itu perilaku yang tidak ditentukan.

"Bisa dibilang" di atas bergantung pada definisi operator langganan array. Secara khusus, ia mengatakan: "Ekspresi postfix diikuti dengan ekspresi dalam tanda kurung siku [] adalah penunjukan objek array yang disubscripsikan." (C89, §6.3.2.1 / 2).

Anda dapat berargumen bahwa "objek array" sedang dilanggar di sini (karena Anda berlangganan di luar rentang objek array yang ditentukan), dalam hal ini perilakunya (sedikit lebih) secara eksplisit tidak ditentukan, bukan hanya tidak terdefinisi milik tidak ada yang cukup mendefinisikannya.

Secara teori, saya dapat membayangkan kompiler yang melakukan pemeriksaan batas-batas array dan (misalnya) akan membatalkan program ketika / jika Anda mencoba menggunakan subskrip di luar jangkauan. Faktanya, saya tidak tahu tentang hal seperti itu, dan mengingat popularitas gaya kode ini, bahkan jika kompiler mencoba menerapkan langganan dalam beberapa keadaan, sulit untuk membayangkan bahwa ada orang yang tahan melakukannya di situasi ini.

Jerry Coffin
sumber
2
Saya juga bisa membayangkan kompiler yang mungkin memutuskan bahwa jika sebuah array kebetulan berukuran 1, maka arr[x] = y;mungkin akan ditulis ulang sebagai arr[0] = y;; untuk larik berukuran 2, arr[i] = 4;mungkin akan ditulis ulang sebagai i ? arr[1] = 4 : arr[0] = 4; Meskipun saya belum pernah melihat kompilator melakukan pengoptimalan seperti itu, pada beberapa sistem tertanam mereka bisa sangat produktif. Pada PIC18x, menggunakan tipe data 8-bit, kode untuk pernyataan pertama adalah enam belas byte, yang kedua, dua atau empat, dan yang ketiga, delapan atau dua belas. Bukan pengoptimalan yang buruk jika legal.
supercat
Jika standar mendefinisikan akses array di luar batas array sebagai perilaku tidak terdefinisi, maka struct hack juga. Namun, jika standar mendefinisikan akses array sebagai gula sintaksis untuk aritmatika penunjuk ( a[2] == a + 2), itu tidak. Jika saya benar, semua standar C mendefinisikan akses array sebagai penunjuk aritmatik.
yyny
13

Ya, ini adalah perilaku yang tidak ditentukan.

Laporan Cacat Bahasa C # 051 memberikan jawaban pasti untuk pertanyaan ini:

Ungkapan itu, meski umum, tidak sepenuhnya selaras

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

Dalam dokumen C99 Rationale, C Committee menambahkan:

Validitas konstruksi ini selalu dipertanyakan. Menanggapi satu Laporan Cacat, Komite memutuskan bahwa itu adalah perilaku yang tidak ditentukan karena larik p-> item hanya berisi satu item, terlepas dari apakah ruang tersebut ada.

ouah
sumber
2
1 untuk menemukan ini, tetapi saya masih mengklaim itu kontradiktif. Dua penunjuk ke objek yang sama (dalam hal ini, byte yang diberikan) adalah sama, dan satu penunjuk ke itu (penunjuk ke dalam larik representasi dari seluruh objek yang diperoleh malloc) valid sebagai tambahan, jadi bagaimana penunjuk identik, diperoleh melalui rute lain, apakah tidak valid dalam penambahan? Bahkan jika mereka ingin mengklaimnya sebagai UB, itu tidak berarti apa-apa, karena secara komputasi tidak ada cara implementasi untuk membedakan antara penggunaan yang didefinisikan dengan baik dan penggunaan yang seharusnya tidak ditentukan.
R .. GitHub STOP HELPING ICE
Sayang sekali compiler C mulai melarang deklarasi array dengan panjang-nol; jika bukan karena larangan itu, banyak kompiler tidak perlu melakukan penanganan khusus untuk membuatnya berfungsi sebagaimana mestinya, tetapi masih dapat menggunakan kode kasus khusus untuk larik elemen tunggal (mis. jika *fooberisi array elemen tunggal boz, ekspresi foo->boz[biz()*391]=9;dapat disederhanakan sebagai biz(),foo->boz[0]=9;). Sayangnya, array nol elemen penolakan compiler berarti banyak kode yang menggunakan array elemen tunggal, dan akan rusak oleh pengoptimalan itu.
supercat
11

Cara tertentu untuk melakukannya tidak secara eksplisit didefinisikan dalam standar C mana pun, tetapi C99 menyertakan "struct hack" sebagai bagian dari bahasa. Di C99, anggota terakhir dari sebuah struct dapat berupa "anggota array fleksibel", dideklarasikan sebagai char foo[](dengan tipe apa pun yang Anda inginkan sebagai gantinya char).

Membuang
sumber
Untuk menjadi bertele-tele, itu bukan peretasan struct. Peretasan struct menggunakan array dengan ukuran tetap, bukan anggota array yang fleksibel. Peretasan struct adalah apa yang ditanyakan dan UB. Anggota susunan yang fleksibel sepertinya merupakan upaya untuk menenangkan jenis orang yang terlihat di utas ini yang mengeluh tentang fakta itu.
underscore_d
7

Ini bukan perilaku yang tidak terdefinisi , terlepas dari apa yang dikatakan seseorang, resmi atau tidak , karena itu ditentukan oleh standar. p->s, kecuali jika digunakan sebagai nilai l, mengevaluasi ke penunjuk yang identik dengan (char *)p + offsetof(struct T, s). Secara khusus, ini adalah charpenunjuk yang valid di dalam objek malloc'd, dan ada 100 (atau lebih, tergantung pada pertimbangan penyelarasan) alamat berturut-turut segera mengikutinya yang juga valid sebagai charobjek di dalam objek yang dialokasikan. Fakta bahwa pointer diturunkan dengan menggunakan ->bukannya secara eksplisit menambahkan offset ke pointer yang dikembalikan oleh malloc, cast to char *, tidak relevan.

Secara teknis, p->s[0]adalah elemen tunggal dari chararray di dalam struct, beberapa elemen berikutnya (misalnya p->s[1]melalui p->s[3]) kemungkinan besar padding byte di dalam struct, yang dapat rusak jika Anda melakukan penugasan ke struct secara keseluruhan tetapi tidak jika Anda hanya mengakses individu anggota, dan elemen lainnya adalah ruang tambahan dalam objek yang dialokasikan yang dapat Anda gunakan secara bebas sesuka Anda, selama Anda mematuhi persyaratan penyelarasan (dan chartidak memiliki persyaratan penyelarasan).

Jika Anda khawatir bahwa kemungkinan tumpang tindih dengan byte padding di struct mungkin entah bagaimana memanggil setan hidung, Anda dapat menghindari ini dengan mengganti 1in [1]dengan nilai yang memastikan bahwa tidak ada padding di akhir struct. Cara sederhana namun boros untuk melakukan ini adalah dengan membuat struct dengan anggota yang identik kecuali tidak ada larik di akhir, dan digunakan s[sizeof struct that_other_struct];untuk larik. Kemudian, p->s[i]secara jelas didefinisikan sebagai elemen dari array di struct untuk i<sizeof struct that_other_structdan sebagai objek char di alamat setelah akhir dari struct untuk i>=sizeof struct that_other_struct.

Sunting: Sebenarnya, dalam trik di atas untuk mendapatkan ukuran yang tepat, Anda mungkin juga perlu meletakkan gabungan yang berisi setiap tipe sederhana sebelum larik, untuk memastikan bahwa larik itu sendiri dimulai dengan perataan maksimal daripada di tengah padding elemen lain . Sekali lagi, saya tidak percaya semua ini perlu, tapi saya menawarkannya untuk pengacara bahasa paling paranoid di luar sana.

Sunting 2: Tumpang tindih dengan padding byte jelas bukan masalah, karena bagian lain dari standar. C mensyaratkan bahwa jika dua struct setuju dalam urutan awal elemen mereka, elemen awal yang sama dapat diakses melalui penunjuk ke salah satu tipe. Akibatnya, jika sebuah struct identik dengan struct Ttetapi dengan larik akhir yang lebih besar dideklarasikan, elemen s[0]tersebut harus bertepatan dengan elemen s[0]di struct T, dan keberadaan elemen tambahan ini tidak dapat mempengaruhi atau dipengaruhi dengan mengakses elemen umum dari struct yang lebih besar. menggunakan penunjuk ke struct T.

R .. GitHub STOP HELPING ICE
sumber
4
Anda benar bahwa sifat aritmatika pointer tidak relevan, tetapi Anda salah tentang akses di luar ukuran array yang dinyatakan. Lihat N1494 (draf C1x publik terbaru) bagian 6.5.6 paragraf 8 - Anda bahkan tidak diizinkan untuk melakukan penambahan yang mengambil pointer lebih dari satu elemen melewati ukuran yang dinyatakan dari array, dan Anda tidak dapat membatalkannya bahkan jika itu hanya satu elemen masa lalu.
zwol
1
@Zack: itu benar jika objeknya adalah array. Tidak benar jika objek tersebut adalah objek yang dialokasikan mallocyang diakses sebagai array atau jika itu adalah struct yang lebih besar yang diakses melalui pointer ke struct yang lebih kecil yang elemennya merupakan subset awal dari elemen dari struct yang lebih besar, antara lain kasus.
R .. GitHub STOP HELPING ICE
6
+1 Jika malloctidak mengalokasikan kisaran memori yang dapat diakses dengan aritmatika pointer, apa gunanya? Dan jika p->s[1]ini didefinisikan oleh standar sebagai sintaksis gula untuk pointer aritmetika, maka jawaban ini hanya menegaskan kembali bahwa mallocberguna. Apa yang tersisa untuk didiskusikan? :)
Daniel Earwicker
3
Anda dapat berargumen bahwa itu didefinisikan dengan baik sebanyak yang Anda suka, tetapi itu tidak mengubah fakta bahwa tidak. Standar sangat jelas tentang akses di luar batas-batas array, dan batas dari array ini adalah 1. Sesederhana itu.
Balapan Ringan di Orbit
3
@R .., menurut saya, asumsi Anda bahwa dua petunjuk yang membandingkan sama pasti berperilaku sama adalah salah. Pertimbangkan int m[1]; int n[1]; if(m+1 == n) m[1] = 0;dengan asumsi ifcabang sudah dimasukkan. Ini adalah UB (dan tidak dijamin akan dimulai n) sesuai 6.5.6 p8 (kalimat terakhir), saat saya membacanya. Terkait: 6.5.9 hal6 dengan catatan kaki 109. (Referensi untuk C11 n1570.) [...]
mafso
7

Ya, ini adalah perilaku yang secara teknis tidak ditentukan.

Perhatikan, setidaknya ada tiga cara untuk menerapkan "struct hack":

(1) Mendeklarasikan trailing array dengan ukuran 0 (cara paling "populer" di kode lama). Ini jelas UB, karena deklarasi larik ukuran nol selalu ilegal di C. Bahkan jika dikompilasi, bahasa tersebut tidak menjamin tentang perilaku kode yang melanggar batasan.

(2) Menyatakan array dengan ukuran legal minimal - 1 (kasus Anda). Dalam hal ini setiap upaya untuk mengambil pointer ke p->s[0]dan menggunakannya untuk aritmatika pointer yang melampaui p->s[1]perilaku tidak terdefinisi. Misalnya, implementasi debugging diizinkan untuk menghasilkan pointer khusus dengan informasi rentang yang disematkan, yang akan menjebak setiap kali Anda mencoba membuat pointer di luar p->s[1].

(3) Mendeklarasikan array dengan ukuran "sangat besar" seperti 10000, misalnya. Idenya adalah bahwa ukuran yang dinyatakan seharusnya lebih besar dari apa pun yang mungkin Anda butuhkan dalam praktik aktual. Metode ini gratis di UB terkait dengan jangkauan akses array. Namun, dalam praktiknya, tentunya kita akan selalu mengalokasikan jumlah memori yang lebih kecil (hanya sebanyak yang benar-benar dibutuhkan). Saya tidak yakin tentang legalitas ini, yaitu saya bertanya-tanya seberapa legal mengalokasikan lebih sedikit memori untuk objek daripada ukuran objek yang dinyatakan (dengan asumsi kita tidak pernah mengakses anggota "non-dialokasikan").

Semut
sumber
1
Dalam (2), s[1]bukan perilaku tidak terdefinisi. Ini sama dengan *(s+1), yang sama dengan *((char *)p + offsetof(struct T, s) + 1), yang merupakan penunjuk yang valid ke chardalam objek yang dialokasikan.
R .. GitHub STOP HELPING ICE
Di sisi lain, saya hampir yakin (3) adalah perilaku yang tidak terdefinisi. Setiap kali Anda melakukan operasi apa pun yang bergantung pada struct yang berada di alamat itu, kompiler bebas untuk menghasilkan kode mesin yang membaca dari bagian manapun dari struct. Bisa jadi tidak berguna, atau bisa jadi fitur keamanan untuk pemeriksaan alokasi yang ketat, tetapi tidak ada alasan implementasi tidak bisa melakukannya.
R .. GitHub STOP HELPING ICE
R: Jika sebuah array dideklarasikan memiliki ukuran (bukan hanya foo[]gula sintaksis untuk *foo), maka akses apa pun di luar yang lebih kecil dari ukuran yang dinyatakan dan ukuran yang dialokasikan adalah UB, terlepas dari bagaimana aritmatika pointer dilakukan.
zwol
1
@ Zack, Anda salah dalam beberapa hal. foo[]di struct bukanlah gula sintaksis untuk *foo; ini adalah anggota array fleksibel C99. Selebihnya, simak jawaban dan komentar saya di jawaban lainnya.
R .. GitHub STOP HELPING ICE
6
Masalahnya adalah bahwa beberapa anggota panitia sangat menginginkan "hack" ini menjadi UB, karena mereka membayangkan beberapa negeri dongeng di mana implementasi C dapat memberlakukan batasan penunjuk. Untuk lebih baik atau lebih buruk, bagaimanapun, melakukan hal itu akan bertentangan dengan bagian lain dari standar - hal-hal seperti kemampuan untuk membandingkan pointer untuk persamaan (jika batas dikodekan dalam penunjuk itu sendiri) atau persyaratan bahwa objek apa pun dapat diakses melalui unsigned char [sizeof object]larik hamparan imajiner . Saya mendukung klaim saya bahwa anggota array fleksibel "hack" untuk pra-C99 memiliki perilaku yang terdefinisi dengan baik.
R .. GitHub STOP HELPING ICE
3

Standar cukup jelas bahwa Anda tidak dapat mengakses hal-hal di samping akhir larik. (dan melalui pointer tidak membantu, karena Anda tidak diizinkan untuk menambah bahkan pointer melewati satu setelah akhir array).

Dan untuk "bekerja dalam praktek". Saya telah melihat pengoptimal gcc / g ++ menggunakan bagian standar ini sehingga menghasilkan kode yang salah saat memenuhi C yang tidak valid ini.

Bernhard R. Link
sumber
dapatkah anda memberi contoh?
Tal
1

Jika kompiler menerima sesuatu seperti

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

Saya pikir cukup jelas bahwa itu harus siap menerima subskrip pada 'dat' di luar panjangnya. Di sisi lain, jika seseorang membuat kode seperti:

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

dan kemudian mengakses somestruct-> dat [x]; Saya tidak akan berpikir compiler berkewajiban untuk menggunakan kode alamat-komputasi yang akan bekerja dengan nilai x yang besar. Saya pikir jika seseorang ingin benar-benar aman, paradigma yang tepat akan lebih seperti:

#tentukan LARGEST_DAT_SIZE 0xF000
typedef struct {
  int apapun;
  char dat [LARGEST_DAT_SIZE];
} MY_STRUCT;

dan kemudian lakukan malloc sebesar (sizeof (MYSTRUCT) -LARGEST_DAT_SIZE + dikehendaki_array_length) byte (ingat bahwa jika diinginkan_array_length lebih besar dari LARGEST_DAT_SIZE, hasilnya mungkin tidak ditentukan).

Kebetulan, saya pikir keputusan untuk melarang array dengan panjang nol adalah keputusan yang tidak menguntungkan (beberapa dialek lama seperti Turbo C mendukungnya) karena array dengan panjang nol dapat dianggap sebagai tanda bahwa kompiler harus menghasilkan kode yang akan bekerja dengan indeks yang lebih besar .

supercat
sumber