[OSy] pointer arithmetics overflow

[Adam Hraska]

Dobry den,

zaujimalo by ma, ako zapisat v standardnom C pripadne
C++ test, ktory overi, ze volna oblast zacinajuca
na "freeStart" a dlha "freeSize" byte-ov nezasahuje
do naalokovanej oblasti zacinajucej na "nextStart".
Vieme pritom, ze freeStart < nextStart. freeStart
i freeSize urcuje uzivatel.

Tato uloha sa vyskytla pri implementacii fcii vma_map
s VF_VA_USER. Problemom je napisat test bez pointer
arithmetic overflow.

Diagram situacie:

+----------------+ ... +------
| <- freeSize -> |     ` nextStart
` freeStart


1) Prvy pokus:

bool isOk(char *freeStart, size_t freeSize, char *nextStart)
{
	ASSERT(freeStart < nextStart);
	if(freeStart + freeSize <= nextStart){
		// Free sa zmesti pred oblast nextStart.
		return true;
	}
	else{
		// Free oblast koliduje s nextStart.
		return false;
	}
}

Tento fragment ma problem, ze freeStart + freeSize
moze overflow-nut pointer, co je podla standardu
undefined behavior [1] a v praxi fatalna chyba.


2) Pokus s overflow testom:

if(freeStart + freeSize < freeStart){
	return (freeStart + freeSize <= nextStart);
}
else{
	// Koliduje!
	return false;
}

V tomto fragmente sa najprv pokusame overit, ci nedojde
k pointer overflow. Bohuzial, pri teste na pointer
overflow sposobujeme samotny overflow. Standard jasne
specifikuje, ze pointer overflow je undefined behavior
a v praxi gcc uvedeny test kompletne odstrani ako sucast
optimalizacie.


3) Rozdiel pointerov.

if(freeSize <= nextStart - freeStart){
	// Free sa zmesti pred nextStart.
	return true;
}
else{
	// Koliduje!
	return false;
}

K ziadnemu pointer overflowu tentokrat nedochadza.
Bohuzial, rozdiel pointerov je podla standardu typu
ptrdiff_t, co je signed integer typ [2]. Podla [3] je
overflow signed integer-u implementation-defined.
Nemozeme sa teda spolahnut, ze prekladac vygeneruje
vhodny kod pre situaciu: INT_MAX < nextStart - freeStart.


4) Pseudo-riesenie.
V nasom kerneli sme sa nakoniec rozhodli pre variantu
(3), kedze v praxi prekladac pocita i signed arithmetics
v two's complement, ktory sa vhodne konvertuje na unsigned
size_t pri porovnani s freeSize. Dalej sme sa poistili
flagmi -fwrapv a -fno-strict-overflow [4].

Zaver
-----
Zaujimalo by ma, ako sa dari realnym OS vyriesit tuto
elementarnu operaciu bez vyuzivania nestandardneho
chovania prekladaca (napr. flagov).

Dakujem.

S pozdravom

Adam Hraska

PS: Uvedomujem si, ze na MIPS je najvacsi segment
velky INT_MAX + 1, a tak by stacilo najprv testovat,
ci sa vobec volna oblast cela zmesti do segmentu.
Tento pristup vsak nemozno aplikovat na architekturach,
kde mozu mat segmenty vyrazne vacsiu velkost (napr.
x86).

[1] c++98.std.expr.add 5.7.5
[2] c++98.std.expr.add 5.7.6
[3] c++98.std.conv.intergral 4.7.3
[4] http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html