Podpisane przepełnienie w C ++ i niezdefiniowane zachowanie (UB)


56

Zastanawiam się nad użyciem kodu takiego jak poniżej

int result = 0;
int factor = 1;
for (...) {
    result = ...
    factor *= 10;
}
return result;

Jeśli pętla jest iterowana w nczasie, to factorjest mnożona przez 10dokładnie nrazy. Jednak factorjest on używany tylko po pomnożeniu przez 10łączną liczbę n-1razy. Jeśli założymy, że factornigdy nie przepełnia się z wyjątkiem ostatniej iteracji pętli, ale może przepełniać się podczas ostatniej iteracji pętli, to czy taki kod powinien być akceptowalny? W takim przypadku wartość factorprawdopodobnie nigdy nie zostanie wykorzystana po wystąpieniu przepełnienia.

Mam debatę na temat tego, czy taki kod powinien zostać zaakceptowany. Byłoby możliwe umieszczenie mnożenia wewnątrz instrukcji if i po prostu nie rób mnożenia na ostatniej iteracji pętli, gdy może ona przepełnić. Minusem jest to, że zaśmieca kod i dodaje niepotrzebną gałąź, która musiałaby sprawdzić na wszystkich poprzednich iteracjach pętli. Mógłbym również wykonać iterację raz na raz i powtórzyć treść pętli raz po pętli, to jeszcze bardziej komplikuje kod.

Właściwy kod, o którym mowa, jest wykorzystywany w ciasnej pętli wewnętrznej, która pochłania dużą część całkowitego czasu procesora w aplikacji graficznej w czasie rzeczywistym.


5
Głosuję za zamknięciem tego pytania jako nie na temat, ponieważ powinno ono znajdować się na codereview.stackexchange.com, a nie tutaj.
Kevin Anderson

31
@KevinAnderson, nie jest tutaj poprawny, ponieważ przykładowy kod ma zostać naprawiony, a nie tylko ulepszony.
Batszeba

1
@harold Są cholernie blisko.
Wyścigi lekkości na orbicie

1
@LightnessRaceswithMonica: autorzy standardu zamierzali i oczekiwali, że implementacje przeznaczone dla różnych platform i celów rozszerzą semantykę dostępną dla programistów poprzez znaczące przetwarzanie różnych działań w sposób użyteczny dla tych platform i celów, niezależnie od tego, czy standard tego wymaga, czy nie, a także stwierdził, że nie chcą poniżać nieprzenośnego kodu. Zatem podobieństwo między pytaniami zależy od tego, które implementacje muszą obsługiwać.
supercat

2
@ superuper Dla zachowań zdefiniowanych dla implementacji, a jeśli wiesz, że twój zestaw narzędzi ma jakieś rozszerzenie, którego możesz użyć (i nie zależy ci na przenośności), w porządku. Dla UB? Wątpliwy.
Wyścigi lekkości na orbicie

Odpowiedzi:


51

Kompilatory zakładają, że poprawny program C ++ nie zawiera UB. Rozważ na przykład:

if (x == nullptr) {
    *x = 3;
} else {
    *x = 5;
}

Jeśli x == nullptrto, wyrejestrowanie go i przypisanie wartości to UB. Dlatego jedynym sposobem, w jaki może to zakończyć się prawidłowym programem, jest moment x == nullptr, w którym nigdy nie da się uzyskać wartości true, a kompilator może założyć, że zgodnie z zasadą jakby, powyższe jest równoważne:

*x = 5;

Teraz w twoim kodzie

int result = 0;
int factor = 1;
for (...) {      // Loop until factor overflows but not more
   result = ...
   factor *= 10;
}
return result;

Ostatnie zwielokrotnienie factornie może nastąpić w prawidłowym programie (podpisany przepełnienie jest niezdefiniowany). Stąd też przypisanie do resultnie może się zdarzyć. Ponieważ nie ma możliwości rozgałęzienia przed ostatnią iteracją, poprzednia iteracja nie może się zdarzyć. W końcu część kodu, która jest poprawna (tj. Nigdy nie zdarza się niezdefiniowane zachowanie) to:

// nothing :(

6
„Niezdefiniowane zachowanie” to wyrażenie, które często słyszymy w odpowiedziach SO, bez wyraźnego wyjaśnienia, w jaki sposób może wpłynąć na program jako całość. Ta odpowiedź sprawia, że ​​wszystko jest o wiele wyraźniejsze.
Gilles-Philippe Paillé

1
Może to być nawet „użyteczna optymalizacja”, jeśli funkcja jest wywoływana tylko dla celów INT_MAX >= 10000000000, z inną funkcją wywoływaną w przypadku, gdy INT_MAXjest mniejsza.
R .. GitHub ZATRZYMAJ LOD

2
@ Gilles-PhilippePaillé Są chwile, w których chciałbym przykleić post na ten temat. Benign Data Races jest jednym z moich ulubionych, jeśli chodzi o uchwycenie tego, jak paskudne mogą być. Jest też świetny raport o błędach w MySQL, którego nie mogę znaleźć ponownie - sprawdzenie przepełnienia bufora, które przypadkowo wywołało UB. Konkretna wersja konkretnego kompilatora po prostu zakładała, że ​​UB nigdy nie występuje, i zoptymalizowała całą kontrolę przepełnienia.
Cort Ammon

1
@SolomonSlow: Główne sytuacje, w których UB jest kontrowersyjny, to te, w których części standardu i dokumentacji implementacji opisują zachowanie niektórych działań, ale inna część standardu charakteryzuje go jako UB. Powszechną praktyką przed napisaniem Standardu było, aby autorzy kompilatora w znaczący sposób przetwarzali takie działania, z wyjątkiem sytuacji, gdy ich klienci skorzystaliby na tym, że zrobili coś innego, i nie sądzę, aby autorzy Standardu kiedykolwiek wyobrażali sobie, że autorzy kompilatora zrobiliby cokolwiek innego. .
supercat

2
@ Gilles-PhilippePaillé: Co każdy programista C powinien wiedzieć o nieokreślonym zachowaniu z bloga LLVM, jest również dobry. Wyjaśnia, w jaki sposób na przykład przepełnienie liczby całkowitej przez UB może pozwolić kompilatorom udowodnić, że i <= npętle są zawsze nieskończone, jak i<npętle. I promuj int ido szerokości wskaźnika w pętli zamiast ponawiać znak, aby możliwe było indeksowanie tablicy zawijania do pierwszych elementów tablicy 4G.
Peter Cordes,

34

Zachowanie intprzepełnienia jest niezdefiniowane.

Nie ma znaczenia, czy czytasz factorpoza ciałem pętli; jeśli do tego czasu się przepełniło, to zachowanie kodu na, po i nieco paradoksalnie, zanim przepełnienie jest niezdefiniowane.

Jednym z problemów, które mogą pojawić się przy utrzymywaniu tego kodu, jest to, że kompilatory stają się coraz bardziej agresywne, jeśli chodzi o optymalizację. W szczególności rozwijają nawyk, w którym zakładają, że niezdefiniowane zachowanie nigdy się nie zdarza. W tym celu mogą forcałkowicie usunąć pętlę.

Czy nie możesz użyć unsignedtypu, factorchociaż musisz martwić się niechcianą konwersją intna unsignedw wyrażeniach zawierających oba?


12
@nicomp; Dlaczego nie?
Batszeba

12
@ Gilles-PhilippePaillé: Czy moja odpowiedź nie mówi, że jest problematyczna? Moje zdanie wstępne niekoniecznie dotyczy OP, ale szerszej społeczności I factorjest „używane” w zadaniu z powrotem do siebie.
Batszeba

8
@ Gilles-PhilippePaillé, a ta odpowiedź wyjaśnia, dlaczego jest problematyczna
idclev 463035818,

1
@Bathsheba Masz rację, źle zrozumiałem twoją odpowiedź.
Gilles-Philippe Paillé

4
Jako przykład niezdefiniowanego zachowania, gdy ten kod zostanie skompilowany z włączonymi kontrolami środowiska wykonawczego, zakończy się zamiast zwracać wynik. Kod, który wymaga ode mnie wyłączenia funkcji diagnostycznych w celu pracy, jest uszkodzony.
Simon Richter

23

Rozważanie optymalizatorów w świecie rzeczywistym może być wnikliwe. Rozwijanie pętli jest znaną techniką. Podstawową ideą rozwijania pętli op jest to

for (int i = 0; i != 3; ++i)
    foo()

może być lepiej zaimplementowany za kulisami

 foo()
 foo()
 foo()

Jest to łatwy przypadek ze stałym ograniczeniem. Ale współczesne kompilatory mogą to zrobić również dla zmiennych zmiennych:

for (int i = 0; i != N; ++i)
   foo();

staje się

__RELATIVE_JUMP(3-N)
foo();
foo();
foo();

Oczywiście działa to tylko wtedy, gdy kompilator wie, że N <= 3. I tu wracamy do pierwotnego pytania. Ponieważ kompilator wie, że podpisane przepełnienie nie występuje , wie, że pętla może wykonać maksymalnie 9 razy na architekturze 32-bitowej. 10^10 > 2^32. Może zatem rozwinąć pętlę iteracyjną 9. Ale zamierzonym maksimum było 10 iteracji! .

Może się zdarzyć, że otrzymasz skok względny do instrukcji asemblacji (9-N) o wartości N = 10, czyli przesunięcie -1, które jest samą instrukcją skoku. Ups Jest to doskonale poprawna optymalizacja pętli dla dobrze zdefiniowanego C ++, ale podany przykład zamienia się w ciasną nieskończoną pętlę.


9

Każde podpisane przepełnienie liczb całkowitych powoduje niezdefiniowane zachowanie, niezależnie od tego, czy przepełniona wartość jest lub może zostać odczytana.

Może w twoim przypadku użycia możesz podnieść pierwszą iterację z pętli, obracając ją

int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
    result += n + factor;
    factor *= 10;
}
// factor "is" 10^10 > INT_MAX, UB

zaangażowany w to

int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
    factor *= 10;
    result += n + factor;
}
// factor is 10^9 < INT_MAX

Po włączeniu optymalizacji kompilator może rozwinąć drugą pętlę powyżej w jeden skok warunkowy.


6
Może to być nieco zbyt techniczne, ale „podpisane przepełnienie jest niezdefiniowanym zachowaniem” jest nadmiernie uproszczone. Formalnie zachowanie programu z podpisanym przepełnieniem jest niezdefiniowane. Oznacza to, że standard nie mówi, co robi ten program. Nie chodzi tylko o to, że coś jest nie tak z przepełnionym wynikiem; coś jest nie tak z całym programem.
Pete Becker

Uczciwa obserwacja, poprawiłem swoją odpowiedź.
elbrunovsky

Lub prościej, obierz ostatnią iterację i usuń zmarłychfactor *= 10;
Peter Cordes

9

To jest UB; w terminologii ISO C ++ całe zachowanie całego programu jest całkowicie nieokreślone dla wykonania, które ostatecznie uderza w UB. Klasycznym przykładem jest to, o ile chodzi o standard C ++, może sprawić, że demony wylecą z twojego nosa. (Odradzam stosowanie implementacji, w której demony nosowe są realną możliwością). Zobacz inne odpowiedzi, aby uzyskać więcej informacji.

Kompilatory mogą „powodować problemy” w czasie kompilacji dla ścieżek wykonywania, które widzą, co prowadzi do UB widocznego w czasie kompilacji, np. Zakładając, że te podstawowe bloki nigdy nie zostaną osiągnięte.

Zobacz także Co każdy programista C powinien wiedzieć o nieokreślonym zachowaniu (blog LLVM). Jak wyjaśniono tam, przepełnienie sygnatury UB pozwala kompilatorom udowodnić, że for(... i <= n ...)pętle nie są pętlami nieskończonymi, nawet dla nieznanych n. Pozwala im także „promować” liczniki pętli int do szerokości wskaźnika zamiast powtarzania rozszerzenia znaku. (Tak więc konsekwencją UB w takim przypadku może być dostęp poza niskimi elementami 64k lub 4G tablicy, jeśli spodziewałeś się podpisanego zawijania iw jego zakresie wartości.)

W niektórych przypadkach kompilatory będą wysyłały niedozwolone instrukcje, takie jak x86, ud2dla bloku, który prawdopodobnie spowoduje UB, jeśli kiedykolwiek zostanie wykonany. (Należy pamiętać, że funkcja może nigdy nie zostać wywołana, więc kompilatory nie mogą generalnie szaleć i łamać innych funkcji, a nawet możliwych ścieżek przez funkcję, która nie uderza w UB, tj. Kod maszynowy, do którego kompiluje, musi nadal działać dla wszystkie dane wejściowe, które nie prowadzą do UB.)


Prawdopodobnie najbardziej wydajnym rozwiązaniem jest ręczne oderwanie ostatniej iteracji, aby factor*=10uniknąć niepotrzebnych .

int result = 0;
int factor = 1;
for (... i < n-1) {   // stop 1 iteration early
    result = ...
    factor *= 10;
}
 result = ...      // another copy of the loop body, using the last factor
 //   factor *= 10;    // and optimize away this dead operation.
return result;

Lub jeśli ciało pętli jest duże, rozważ użycie po prostu typu bez znaku dla factor. Następnie możesz pozwolić, aby niepodpisane zwielokrotniło się, a po prostu wykona dobrze zdefiniowane zawijanie do pewnej potęgi 2 (liczba bitów wartości w typie bez znaku).

Jest to w porządku, nawet jeśli używasz go z podpisanymi typami, szczególnie jeśli konwersja niepodpisana-> podpisana nigdy się nie przepełnia.

Konwersja między niepodpisanym a 2-znakowym uzupełnieniem jest bezpłatna (taki sam wzór bitowy dla wszystkich wartości); zawijanie modulo dla int -> unsigned określone przez standard C ++ upraszcza po prostu użycie tego samego wzorca bitowego, w przeciwieństwie do uzupełnienia lub znaku / wielkości.

I niepodpisany-> podpisany jest podobnie trywialny, chociaż jest zdefiniowany implementacyjnie dla wartości większych niż INT_MAX. Jeśli nie używasz ogromnego niepodpisanego wyniku z ostatniej iteracji, nie masz się czym martwić. Ale jeśli tak, zobacz Czy konwersja z niepodpisanego do podpisanego jest niezdefiniowana? . Przypadek „nie pasuje” jest zdefiniowany w implementacji , co oznacza, że ​​implementacja musi wybrać pewne zachowanie; rozsądne po prostu obcinają (jeśli to konieczne) niepodpisany wzorzec bitów i używają go jako podpisanego, ponieważ działa to dla wartości w zakresie w ten sam sposób bez dodatkowej pracy. I zdecydowanie nie jest to UB. Tak duże wartości bez znaku mogą stać się liczbami całkowitymi ze znakiem ujemnym. np. po int x = u; gcc i clang nie optymalizujx>=0jak zawsze są prawdziwe, nawet bez -fwrapv, ponieważ określają zachowanie.


2
Nie rozumiem tutaj przegłosowania. Głównie chciałem napisać o oderwaniu ostatniej iteracji. Aby jednak odpowiedzieć na to pytanie, zebrałem kilka punktów na temat tego, jak Grok UB. Zobacz inne odpowiedzi, aby uzyskać więcej informacji.
Peter Cordes,

5

Jeśli możesz tolerować kilka dodatkowych instrukcji montażu w pętli, zamiast

int factor = 1;
for (int j = 0; j < n; ++j) {
    ...
    factor *= 10;
}

Możesz pisać:

int factor = 0;
for (...) {
    factor = 10 * factor + !factor;
    ...
}

aby uniknąć ostatniego pomnożenia. !factornie wprowadzi oddziału:

    xor     ebx, ebx
L1:                       
    xor     eax, eax              
    test    ebx, ebx              
    lea     edx, [rbx+rbx*4]      
    sete    al    
    add     ebp, 1                
    lea     ebx, [rax+rdx*2]      
    mov     edi, ebx              
    call    consume(int)          
    cmp     r12d, ebp             
    jne     .L1                   

Ten kod

int factor = 0;
for (...) {
    factor = factor ? 10 * factor : 1;
    ...
}

powoduje również montaż bez rozgałęzień po optymalizacji:

    mov     ebx, 1
    jmp     .L1                   
.L2:                               
    lea     ebx, [rbx+rbx*4]       
    add     ebx, ebx
.L1:
    mov     edi, ebx
    add     ebp, 1
    call    consume(int)
    cmp     r12d, ebp
    jne     .L2

(Kompilowany z GCC 8.3.0 -O3)


1
Łatwiej jest po prostu oderwać ostatnią iterację, chyba że korpus pętli jest duży. Jest to sprytny hack, ale factornieznacznie zwiększa opóźnienie łańcucha zależności przenoszonej przez pętlę . Czy nie: kiedy kompiluje do 2x LEA to prawie tak samo skuteczny jak LEA + dodaj do zrobienia f *= 10jak f*5*2, z testopóźnieniami ukryte przez pierwszy LEA. Ale wewnątrz pętli kosztuje to więcej, więc może wystąpić negatywny wpływ na przepustowość (lub przynajmniej problem związany z łatwym przeszukiwaniem)
Peter Cordes

4

Nie pokazałeś, co jest w nawiasach foroświadczenia, ale założę, że jest to coś takiego:

for (int n = 0; n < 10; ++n) {
    result = ...
    factor *= 10;
}

Możesz po prostu przenieść przyrost licznika i sprawdzić zakończenie pętli do ciała:

for (int n = 0; ; ) {
    result = ...
    if (++n >= 10) break;
    factor *= 10;
}

Liczba instrukcji montażu w pętli pozostanie taka sama.

Zainspirowany prezentacją Andrei Alexandrescu „Speed ​​Is Found In The Minds of People”.


2

Rozważ funkcję:

unsigned mul_mod_65536(unsigned short a, unsigned short b)
{
  return (a*b) & 0xFFFFu;
}

Zgodnie z opublikowanym przesłanki, by oczekiwać autorzy standardu, że jeśli funkcja ta była wywoływana na (np) w banalnej 32-bitowego komputera z argumentami 0xC000 i 0xC000, promowanie operandy o *celu signed intspowoduje obliczenie uzyskując -0x10000000 , które po przekształceniu unsigneddałyby 0x90000000u- taką samą odpowiedź, jak gdyby się unsigned shortpromowały unsigned. Niemniej jednak gcc czasami zoptymalizuje tę funkcję w sposób, który zachowywałby się bezsensownie, gdyby nastąpiło przepełnienie. Każdy kod, w którym pewna kombinacja danych wejściowych może spowodować przepełnienie, musi być przetwarzany z -fwrapvopcją, chyba że dopuszczalne jest zezwolenie twórcom celowo zniekształconych danych wejściowych na wykonanie dowolnego wybranego przez siebie kodu.


1

Dlaczego nie to:

int result = 0;
int factor = 10;
for (...) {
    factor *= 10;
    result = ...
}
return result;

To nie uruchamia ...korpusu pętli dla factor = 1lub factor = 10, tylko 100 i więcej. Będziesz musiał obrać pierwszą iterację i zacząć od początku, factor = 1jeśli chcesz, aby to zadziałało.
Peter Cordes,

1

Istnieje wiele różnych twarzy niezdefiniowanego zachowania, a to, co jest dopuszczalne, zależy od użycia.

ciasna pętla wewnętrzna, która pochłania dużą część całkowitego czasu procesora w aplikacji graficznej w czasie rzeczywistym

To samo w sobie jest trochę niezwykłe, ale niech tak będzie ... jeśli tak rzeczywiście jest, to UB najprawdopodobniej mieści się w sferze „dopuszczalnej, dopuszczalnej” . Programowanie graficzne jest znane z hacków i brzydkich rzeczy. Tak długo, jak „działa” i nie trwa dłużej niż 16,6 ms, aby utworzyć ramkę, zwykle nikogo to nie obchodzi. Ale pamiętaj, co to znaczy wywołać UB.

Po pierwsze, jest standard. Z tego punktu widzenia nie ma o czym dyskutować i nie ma sposobu na uzasadnienie, twój kod jest po prostu nieprawidłowy. Nie ma ifs ani kiedy, to po prostu nie jest poprawny kod. Równie dobrze możesz powiedzieć, że jest to środkowy palec z twojego punktu widzenia, a 95-99% czasu i tak będziesz gotowy.

Następnie jest strona sprzętowa. Istnieją rzadkie, dziwne architektury, w których jest to problem. Mówię „niezwykłe, dziwne”, ponieważ w przypadku jednej architektury, która stanowi 80% wszystkich komputerów (lub dwóch architektur, które razem stanowią 95% wszystkich komputerów) przepełnienie to „tak, cokolwiek, nie przejmuj się” rzecz na poziomie sprzętowym. Na pewno dostajesz śmieci (choć nadal przewidywalne), ale nic złego się nie dzieje.
To nie jestw przypadku każdej architektury, możesz bardzo dobrze dostać pułapkę na przepełnienie (choć patrząc na to, jak mówisz o aplikacji graficznej, szanse na bycie na tak dziwnej architekturze są raczej niewielkie). Czy przenośność stanowi problem? Jeśli tak, możesz wstrzymać się od głosu.

Na koniec jest strona kompilatora / optymalizatora. Jednym z powodów, dla których przepełnienie jest niezdefiniowane, jest to, że po prostu pozostawienie go w tym miejscu było najłatwiejsze, aby poradzić sobie ze sprzętem. Ale innym powodem jest to, że na przykład x+1jest gwarantowane , aby zawsze być większy niż x, a kompilator / optymalizator może wykorzystać tę wiedzę. Teraz, dla wcześniej wspomnianego przypadku, kompilatory rzeczywiście działają w ten sposób i po prostu usuwają kompletne bloki (kilka lat temu istniał exploit na Linuksa, który był oparty na tym, że kompilator usunął martwy kod weryfikacyjny właśnie z tego powodu).
W twoim przypadku poważnie wątpiłbym, że kompilator wykonuje specjalne, nieparzyste optymalizacje. Co jednak wiesz, co ja wiem. W razie wątpliwości wypróbuj to. Jeśli to działa, możesz iść.

(I w końcu, oczywiście jest audyt kodu, być może będziesz musiał tracić czas na omawianie tego z audytorem, jeśli masz pecha.)

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.