[OSy] pointer arithmetics overflow

[Marek Vasut]

On Wednesday 23 February 2011 00:56:14 Adam Hraska wrote:
> 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.

Jestli to chapu dobre, tak staci rict, ze BFU muze alokovat treba minimalne 2 
bajty (a ne jeden bajt) ... pak adresu, kterou BFU zada, podelit dvema (nebo 
kolik je minimalni zvolena alokacni jednotka) a pocitat s tim. Pak uz zadnej 
overflow nenastane, ne ?
> 
> 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
> 
> _______________________________________________
> OSy mailing list
> OSy at d3s.mff.cuni.cz
> https://d3s.mff.cuni.cz/mailman/listinfo/osy