Jakie są powody, dla których powłoka bash nie ostrzega przed przepełnieniem arytmetycznym itp.?

9

Istnieją ograniczenia dotyczące arytmetycznych możliwości oceny bashpowłoki. Podręcznik zwięźle opisuje ten aspekt arytmetyki powłoki, ale stwierdza :

Oceny dokonuje się w liczbach całkowitych o stałej szerokości bez sprawdzania przepełnienia, chociaż dzielenie przez 0 jest zatrzymywane i oznaczane jako błąd. Operatory i ich pierwszeństwo, asocjatywność i wartości są takie same jak w języku C.

Która liczba całkowita o stałej szerokości, do której się odnosi, tak naprawdę dotyczy tego, który typ danych jest używany (i szczegóły, dlaczego jest to poza tym), ale wartość graniczna jest wyrażana /usr/include/limits.hw następujący sposób:

#  if __WORDSIZE == 64
#   define ULONG_MAX     18446744073709551615UL
#  ifdef __USE_ISOC99
#  define LLONG_MAX       9223372036854775807LL
#  define ULLONG_MAX    18446744073709551615ULL

A kiedy już to wiesz, możesz potwierdzić ten stan faktyczny w następujący sposób:

# getconf -a | grep 'long'
LONG_BIT                           64
ULONG_MAX                          18446744073709551615

Jest to liczba całkowita 64-bitowa, co przekłada się bezpośrednio na powłokę w kontekście obliczeń arytmetycznych:

# echo $(((2**63)-1)); echo $((2**63)); echo $(((2**63)+1)); echo $((2**64))
9223372036854775807        //the practical usable limit for your everyday use
-9223372036854775808       //you're that much "away" from 2^64
-9223372036854775807     
0
# echo $((9223372036854775808+9223372036854775807))
-1

Tak więc między 2 63 a 2 64 -1 otrzymasz ujemne liczby całkowite pokazujące, jak daleko od ULONG_MAX jesteś 1 . Gdy ocena osiąga ten limit i przepełnia się, w jakiejkolwiek kolejności, nie pojawia się żadne ostrzeżenie, a ta część oceny jest resetowana do zera, co może dawać pewne nietypowe zachowanie z czymś takim, jak na przykład potęgowanie prawostronne :

echo $((6**6**6))                      0   // 6^46656 overflows to 0
echo $((6**6**6**6))                   1   // 6^(6^46656) = 6^0 = 1
echo $((6**6**6**6**6))                6   // 6^(6(6^46656)) = 6^(6^0) = 6^1
echo $((6**6**6**6**6**6))         46656   // 6^(6^(6^(6^46656))) = 6^6
echo $((6**6**6**6**6**6**6))          0   // = 6^6^6^1 = 0
...

Używanie sh -c 'command'niczego nie zmienia, więc muszę założyć, że jest to normalne i zgodne wyjście. Teraz, gdy myślę, że mam podstawową, ale konkretną wiedzę na temat zakresu arytmetycznego i limitu oraz co to znaczy w powłoce do oceny wyrażeń, pomyślałem, że mogę szybko zerknąć, jakie typy danych używają inne oprogramowanie w systemie Linux. Użyłem niektórych bashźródeł, które musiałem uzupełnić do wprowadzenia tego polecenia:

{ shopt -s globstar; for i in /path/to/source_bash-4.2/include/**/*.h /usr/include/**/*.h; do grep -HE '\b(([UL])|(UL)|())LONG|\bFLOAT|\bDOUBLE|\bINT' $i; done; } | grep -iE 'bash.*max'

bash-4.2/include/typemax.h:#    define LLONG_MAX   TYPE_MAXIMUM(long long int)
bash-4.2/include/typemax.h:#    define ULLONG_MAX  TYPE_MAXIMUM(unsigned long long int)
bash-4.2/include/typemax.h:#    define INT_MAX     TYPE_MAXIMUM(int)

ifInstrukcje mają więcej danych wyjściowych i mogę wyszukiwać polecenia takie jak awkitp. Zauważyłem, że użyte wyrażenie regularne nie łapie niczego na temat narzędzi o dowolnej precyzji, takich jak bci dc.


pytania

  1. Jaki jest powód, aby nie ostrzegać cię (podobnie jak w awkprzypadku oceny 2 ^ 1024), gdy twoja arytmetyczna przepełnia się? Dlaczego ujemne liczby całkowite między 2 63 a 2 64 -1 są narażone na końcowy użytkownik, gdy coś ocenia?
  2. Czytałem gdzieś, że jakiś smak UNIXa może interaktywnie zmienić ULONG_MAX? Czy ktoś o tym słyszał?
  3. Jeśli ktoś dowolnie zmieni wartość maksimum liczby całkowitej bez znaku w limits.h, a następnie przekompiluje bash, czego możemy się spodziewać?

Uwaga

1. Chciałem lepiej zilustrować to, co zobaczyłem, ponieważ jest to bardzo prosta sprawa empiryczna. Zauważyłem, że:

  • (a) Każda ocena, która daje <2 ^ 63-1, jest poprawna
  • (b) Każda ocena, która daje => 2 ^ 63 do 2 ^ 64 daje ujemną liczbę całkowitą:
    • Zakres tej liczby całkowitej wynosi od x do y. x = -9223372036854775808 iy = 0.

Biorąc to pod uwagę, ocenę podobną do (b) można wyrazić jako 2 ^ 63-1 plus coś w obrębie x..y. Na przykład, jeśli jesteśmy dosłownie poproszeni o ocenę (2 ^ 63-1) +100 002 (ale może być dowolną liczbą mniejszą niż w (a)), otrzymujemy -9223372036854675807. Podaję tylko oczywiste, ale chyba oznacza to, że dwa następujące wyrażenia:

  • (2 ^ 63-1) + 100 002 ORAZ;
  • (2 ^ 63-1) + (LLONG_MAX - {za co daje nam powłoka ((2 ^ 63-1) + 100 002), czyli -9223372036854675807}) cóż, używając dodatnich wartości, które mamy;
    • (2 ^ 63-1) + (9223372036854775807 - 9223372036854675807 = 100 000)
    • = 9223372036854775807 + 100 000

są naprawdę bardzo blisko. Drugie wyrażenie to „2” oprócz (2 ^ 63-1) + 100 002, czyli tego, co oceniamy. Mam na myśli to, że otrzymujesz ujemne liczby całkowite pokazujące, jak daleko jesteś od 2 ^ 64. Mam na myśli te ujemne liczby całkowite i znajomość granic, no cóż, nie można zakończyć oceny w zakresie x..y w powłoce bash, ale można to zrobić gdzie indziej - dane są użyteczne do 2 ^ 64 w tym sensie (mógłbym dodać na papierze lub użyj go w bc). Poza tym jednak zachowanie jest podobne do 6 ^ 6 ^ 6, ponieważ limit został osiągnięty, jak opisano poniżej w Q ...


źródło
5
Domyślam się, że uzasadnienie sprowadza się do tego, że „skorupa nie jest właściwym narzędziem do matematyki”. Nie jest do tego przeznaczony i nie próbuje z wdziękiem sobie z tym radzić, jak pokazujesz. Do diabła, większość pocisków nie radzi sobie nawet z pływakami!
terdon
@terdon Chociaż sposób, w jaki powłoka radzi sobie z liczbami w tym przypadku, jest dokładnie taki sam, jak każdy język wysokiego poziomu, o jakim kiedykolwiek słyszałem. Typy liczb całkowitych mają stały rozmiar i mogą ulec przepełnieniu.
goldilocks
@terdon Rzeczywiście, kiedy to badałem, od momentu, gdy Q ^ 6 ^ 6 QI zdałem sobie z tego sprawę. Zgadłem również, że powodem, dla którego nie mogłem znaleźć dużo treści, było to, że miało to związek z C, a nawet C99. Ponieważ nie jestem ani programistą, ani informatykiem, muszę pogodzić się z całą wiedzą, która stanowi podstawę tych założeń. Z pewnością ktoś, kto wymaga arbitralnej precyzji, wie o typie danych, ale oczywiście nie jestem tą osobą :) (ale zauważyłem zachowanie awk @ 2 ^ 53 + 1, tj. Zmiennoprzecinkowe; po prostu precyzja i wewnętrzne vs. drukowanie itp. Jest poza mną !).
1
Jeśli chcesz pracować z dużymi liczbami w powłoce, użyj bcnp $num=$(echo 6^6^6 | bc). : Niestety bcwstawia podział wiersza, więc musisz num=$(echo $num | sed 's/\\\s//g')później; jeśli zrobisz to w potoku, istnieją rzeczywiste znaki nowej linii, które są niezręczne w przypadku sed, chociaż num=$(echo 6^6^3 | bc | perl -pne 's/\\\s//g')działa. W obu przypadkach masz teraz liczbę całkowitą, której można użyć, np num2=$(echo "$num * 2" | bc).
goldilocks
1
... Ktoś tutaj wskazał, że możesz wyłączyć tę funkcję podziału linii bcprzez ustawienie BC_LINE_LENGTH=0.
goldilocks

Odpowiedzi:

11

Tak więc między 2 ^ 63 a 2 ^ 64-1 otrzymasz ujemne liczby całkowite pokazujące, jak daleko jesteś od ULONG_MAX.

Nie. Jak to wymyśliłeś? Według własnego przykładu maksimum to:

> max=$((2**63 - 1)); echo $max
9223372036854775807

Jeśli „przepełnienie” oznaczało „masz ujemne liczby całkowite pokazujące, jak daleko jesteś od ULONG_MAX”, to jeśli dodamy do tego jedną, czy nie powinniśmy otrzymać -1? Lecz:

> echo $(($max + 1))
-9223372036854775808

Być może masz na myśli liczbę, którą możesz dodać, $maxaby uzyskać ujemną różnicę, ponieważ:

> echo $(($max + 1 + $max))
-1

Ale tak naprawdę nie jest to prawdą:

> echo $(($max + 2 + $max))
0

Wynika to z faktu, że system używa uzupełnienia do dwóch do implementacji podpisanych liczb całkowitych. 1 Wartość wynikająca z przepełnienia NIE jest próbą zapewnienia różnicy, ujemnej różnicy itp. Jest to dosłownie wynik obcięcia wartości do ograniczonej liczby bitów, a następnie interpretacji jej jako liczby całkowitej ze znakiem uzupełnienia do dwóch . Na przykład powodem $(($max + 1 + $max))jest -1, ponieważ najwyższą wartością w uzupełnieniu do dwóch są wszystkie ustawione bity z wyjątkiem najwyższego bitu (który wskazuje ujemny); dodanie ich razem oznacza w zasadzie przeniesienie wszystkich bitów w lewo, więc otrzymujesz (jeśli rozmiar miałby 16 bitów, a nie 64):

11111111 11111110

Bit wysoki (znak) jest teraz ustawiony, ponieważ został przeniesiony w dodatku. Jeśli dodasz do tego jeszcze jeden (00000000 00000001), wtedy masz ustawione wszystkie bity , które w uzupełnieniu dwóch wynoszą -1.

Myślę, że częściowo odpowiada to na drugą połowę pierwszego pytania - „Dlaczego ujemne liczby całkowite ... są narażone na ryzyko dla użytkownika końcowego?”. Po pierwsze, ponieważ jest to poprawna wartość zgodnie z regułami liczb uzupełniających dwójki 64-bitowej. Jest to konwencjonalna praktyka większości (innych) języków programowania wysokiego poziomu ogólnego przeznaczenia (nie mogę wymyślić takiego, który tego nie robi), więc bashprzestrzega konwencji. Która jest również odpowiedzią na pierwszą część pierwszego pytania - „Jakie jest uzasadnienie?”: Jest to norma w specyfikacji języków programowania.

WRT drugie pytanie, nie słyszałem o systemach, które interaktywnie zmieniają ULONG_MAX.

Jeśli ktoś dowolnie zmieni wartość maksimum liczby całkowitej bez znaku w limitach. H, a następnie przekompiluje bash, czego możemy się spodziewać?

Nie miałoby to żadnego znaczenia dla sposobu, w jaki wyłania się arytmetyka, ponieważ nie jest to arbitralna wartość używana do konfiguracji systemu - jest to wartość wygody, która przechowuje niezmienną stałą odzwierciedlającą sprzęt. Analogicznie możesz zmienić definicję c na 55 mil na godzinę, ale prędkość światła nadal będzie wynosić 186 000 mil na sekundę. c nie jest liczbą używaną do konfigurowania wszechświata - jest to dedukcja na temat natury wszechświata.

ULONG_MAX jest dokładnie taki sam. Jest on wydedukowany / obliczony na podstawie charakteru liczb N-bitowych. Zmiana tej wartości limits.hbyłaby bardzo złym pomysłem, gdyby ta stała była używana gdzieś, zakładając, że ma ona reprezentować rzeczywistość systemu .

I nie możesz zmienić rzeczywistości narzuconej przez twój sprzęt.


1. Nie sądzę, że to (sposób przedstawienia liczb całkowitych) jest w rzeczywistości gwarantowane bash, ponieważ zależy to od podstawowej biblioteki C, a standardowy C nie gwarantuje tego. Jest to jednak używane na większości normalnych współczesnych komputerów.

Złotowłosa
źródło
Jestem bardzo wdzięczna! Pogodzenie się ze słoniem w pokoju i myślenie. Tak, w pierwszej części chodzi głównie o słowa. Zaktualizowałem swoje Q, aby pokazać, co miałem na myśli. Zbadam, dlaczego uzupełnienie do dwóch opisuje część tego, co widziałem, a twoja odpowiedź jest nieoceniona w zrozumieniu tego! Jeśli chodzi o UNIX Q jest zaniepokojony muszę mieć misread coś o ARG_MAX z AIX tutaj . Twoje zdrowie!
1
W rzeczywistości możesz użyć uzupełnienia do dwóch, aby określić wartość, jeśli masz pewność , że mieścisz się w zakresie> 2 * $max, jak to opisano. Moje punkty to 1) to nie jest cel, 2) upewnij się, że rozumiesz, jeśli chcesz to zrobić, 3) nie jest to bardzo przydatne ze względu na bardzo ograniczone zastosowanie, 4) zgodnie z przypisem nie jest faktycznie zagwarantowane, że system użyj uzupełnienia do dwóch. Krótko mówiąc, próba wykorzystania tego w kodzie programu byłaby uważana za bardzo złą praktykę. Istnieją biblioteki / moduły „dużej liczby” (dla powłok w POSIX-ie bc) - użyj ich, jeśli potrzebujesz.
Złotowłosa
Dopiero niedawno obejrzałem coś, co wykorzystało ich uzupełnienie do wdrożenia ALU z 4-bitowym sumatorem binarnym z układem szybkiego przenoszenia; było nawet porównanie z uzupełnieniem (aby zobaczyć, jak było). Twoje wyjaśnienie odegrało kluczową rolę w tym, że mogłem nazwać i połączyć to, co tu widziałem, z tym, co omawiano w tych filmach , zwiększając szansę, że naprawdę mogę pojąć wszystkie implikacje, gdy wszystko się pojawi. Dzięki jeszcze raz! Twoje zdrowie!