Re: [Lzip-bug] Version 0.1 of plzip released

[Ersek Laszlo]

On 07 Dec 2009, John Reiser wrote:

> On 12/07/2009 12:07 AM, Tino Lange wrote:
>>> plzip.cc:601: warning: comparison is always false due to limited
>>> range of data type
>>> main.cc:1101: warning: comparison is always false due to limited
>>> range of data type
>> Are they serious? 
>
> Yes, they are true bugs.
> Using "(size_t)-1" instead of INT32_MAX or INT64_MAX (from <stdint.h>)
> is an outright error.

Hi, I wrote llzip. I'm not trying to hijack this thread, but since the
code in question is from llzip-0.03, and consequently, lbzip2, I'd like
to add a few notes.


>>> main.cc:1101: warning: comparison is always false due to limited
>>> range of data type

This is not a bug. I'll use the line numbers as present in plzip-0.1.

   1091   long max_worker = sysconf(_SC_THREAD_THREADS_MAX);
   1092   if (-1L == max_worker) {
   1093     max_worker = LONG_MAX;
   1094   }
   1095   if (UINT_MAX < (long unsigned)max_worker) {
   1096     max_worker = UINT_MAX;
   1097   }
   1098   if (UINT_MAX / blf < (unsigned)max_worker) {
   1099     max_worker = UINT_MAX / blf;
   1100   }
   1101   if ((size_t)-1 / sizeof(pthread_t) < (unsigned)max_worker) {
   1102     max_worker = (size_t)-1 / sizeof(pthread_t);
   1103   }

This part of code establishes an absolute upper limit on the number of
worker threads. It does not guarantee that the established limit will
be actually usable as the number of started worker threads (lack of
resources etc), but it does make sure that any later operation on the
number of worker threads does not overflow. The value of max_worker can
only decrease, starting with line 1095, and the safety of any
conditional itself is provided for by the earlier parts.

-o-

The number of worker threads, as specified by the user, will be stored
as an unsigned integer. Since UINT_MAX must be at least 4G-1 on SUSv2,
see [0], that seems to be quite enough. It is unsigned because a
negative number of threads is nonsensical. Furthermore, anything below
the rank of "int" would result in ever-repeating integer promotions,
thus no "short unsigned".

    746 struct Opts
    747 {
    748   unsigned num_worker;  /* Start this many worker threads. */
    751 };

Thus we have criterion C1: the number of worker threads will be stored
as an unsigned int in the end, after the configuration phase has
terminated.

-o-

   1091   long max_worker = sysconf(_SC_THREAD_THREADS_MAX);
   1092   if (-1L == max_worker) {
   1093     max_worker = LONG_MAX;
   1094   }

It makes no sense to accept any higher value for the number of worker
threads than the system tells beforehand it will be able to create.
We're inclined to use PTHREAD_THREADS_MAX from <limits.h>, but SUSv2
says we should rather query sysconf() -- see [0] again. So we query
sysconf(), see [1].

sysconf() returns a long int. It may even return -1L "[i]f the variable
corresponding to /name/ is associated with functionality that is not
supported by the system". I'm wary of broken sysconf() implementations,
so I don't give up immediately when sysconf() returns -1L. (And the
sysconf() parameter _SC_THREAD_THREADS_MAX is obviously not an invalid
name.) If I happen to meet such a broken sysconf() implementation, I
start out with the least restrictive value that could be returned by
sysconf() anyway, that is, LONG_MAX. Furthermore, the value returned by
sysconf() is not a promise that the system will be able to create that
many threads. It's only telling us that the system will *not* be able
to create *more* threads than the number returned -- which also allows
the system to fail to create much less threads. Thus it's perfectly
reasonable for a SUSv2-conformant system to return LONG_MAX, if it has
no predefined fixed limit. See again the definition of
PTHREAD_THREADS_MAX.

Thus we start out with criterion C0: the initial value for the maximum
number of worker threads will be represented as a long int, coming from
sysconf().

-o-

   1095   if (UINT_MAX < (long unsigned)max_worker) {
   1096     max_worker = UINT_MAX;
   1097   }

C1 is established here, independently from the platform's
characteristics.

Note that the comparison in line 1095 is safe, max_worker is a
non-negative long at that point (LONG_MAX at most). UINT_MAX is
implicitly converted to long unsigned from unsigned before the
comparison; from the C standard:

    if both operands have signed integer types or both have unsigned
    integer types, the operand with the type of lesser integer
    conversion rank is converted to the type of the operand with
    greater rank.

... and from <limits.h>, section "Numerical Limits":

    except for CHAR_BIT, DBL_DIG, DBL_MAX, FLT_DIG, FLT_MAX, LONG_BIT,
    WORD_BIT and MB_LEN_MAX, the symbolic names will be defined as
    expressions of the correct type.

... thus UINT_MAX is of type unsigned.

If the expression on line 1095 evaluates to true, with max_worker being
at most LONG_MAX, then the assignment on line 1096 is safe -- UINT_MAX
can be converted to long in that case.

For example, instantiating the above for ILP32 platforms (see [2]),
UINT_MAX is greater than (long unsigned)LONG_MAX, thus line 1096 is
impossible to reach. On LP64 platforms, it will be reached if sysconf()
returned -1L or anything greater than UINT_MAX for whatever reason.
(And LP64 may be selected by "lfs.sh", at least in llzip.)

-o-

   1098   if (UINT_MAX / blf < (unsigned)max_worker) {
   1099     max_worker = UINT_MAX / blf;
   1100   }

The number of input slots is determined by multiplying the number of
worker threads by a constant "backlog factor", so that any worker
thread is able to have blf blocks buffered up for it by the splitter.
This number, calculated by lines

    754 static const unsigned blf = 3u;

   1195   unsigned num_slot = opts.num_worker * blf;

is stored as an unsigned value. We must not overflow the num_slot
variable, therefore we clamp max_worker at "UINT_MAX / blf" if
necessary. At this point we ensure C2: the number of worker threads can
be multiplied by blf and it won't overflow an unsigned int.

The expression on line 1098 is safe. All sub-expressions are of type
unsigned. max_worker itself is long, but due to C1 ensured above, we
can safely cast it to unsigned.

-o-

   1101   if ((size_t)-1 / sizeof(pthread_t) < (unsigned)max_worker) {
   1102     max_worker = (size_t)-1 / sizeof(pthread_t);
   1103   }

We will allocate an array of thread identifiers: for each worker thread
one identifier. It makes no sense to allow the user to specify a higher
number than we can allocate thread identifiers for in a continuous
array. malloc() expects a size_t argument, and we're going to produce
that argument by multiplication.

We establish C3 here: the number of worker threads, multiplied by
sizeof(pthread_t), shall not overflow a size_t variable.

[3] states:

    size_t
        Unsigned integral type of the result of the sizeof operator. 

The expression on line 1101 is safe.

- If size_t has no lower conversion rank than "unsigned", then we have
at most an implicit conversion (widening) between unsigned types before
the comparison.

- If, for whatever reason, size_t happens to have a lesser conversion
rank thank "unsigned", it is either promoted to unsigned (in which case
we're done) or to a non-negative "int" (if int's range allows wrt. to
size_t's range). In that case, that "int" is converted to "unsigned"
for the comparison's sake, and we're done.

Note that at this point max_workers still has type long, but due to the
previous checks, it can be safely cast to unsigned.

Line 1102, depending on line 1101's evaluation to 1, only decreases the
value of max_worker, thus it is safe.

On an ILP32 platform, this section may have a clamping effect: line
1102 may be executed. Suppose sysconf() returns LONG_MAX
(2,147,483,647). max_worker will be first decreased to UINT_MAX / 3 =
1,431,655,765 in line 1099, then to UINT_MAX / 4 = 1,073,741,823 in
line 1102.

OTOH, on an LP64 platform you'll get

>>> main.cc:1101: warning: comparison is always false due to limited
>>> range of data type

which describes a situation that is all of
- valid,
- harmless,
- intended by me.

It simply means that on an LP64 platform, establishing C3 requires no
clamping *in any case*.

Later on, this is how we rely on C3 in plzip.cc:

    569   pthread_t *worker;

    613   assert(0u < num_worker);
    614   assert((size_t)-1 / sizeof *worker >= num_worker);
    615   worker = (pthread_t *)xalloc(num_worker * sizeof *worker);

(Mixing unsigned and size_t is safe, see the discussion of line 1101 at
C3.)

About the same is going on around plzip.cc:601.

-o-

> Using "(size_t)-1" instead of INT32_MAX or INT64_MAX (from <stdint.h>)
> is an outright error.

Now I believe I am able to refute this. First, as lines 1101-1103 clamp
the product to an unsigned maximum, "fixing" them with INT*_MAX is out
of question. Second, (size_t)-1 is just fine, because we aim at
malloc()'s argument with the product, and also because unsigned
overflow is completely valid and well defined. (size_t)-1 is *exacly*
"SIZE_MAX", except there is no such symbolic constant / macro (and so
conditional compilation by way of the preprocessor is out of question).

Of course I could have written UINT_MAX in place of (size_t)-1, but
that could pessimize the code -- probably with no real effect -- on
platforms where unsigned int is 32-bit wide and size_t is 64-bit wide,
and more importantly, it wouldn't communicate my intent. ... Albeit
judging after your post, it's not communicated this way either.

Still, you cannot possibly expect me to write down all this litany in
comments, for twenty lines of code. Conversely, I can and do very well
expect you to peruse SUSv2 and the C standards / rationales before
calling my code erroneous.

Integer conversions are a bitch. Hard to note, source of security bugs.
Get familiar with them. I may be irrationally and even inconsistently
over-defensive, but that's the better side to err on.

When I program, I design and prove what I need to in order to get the
app stuff done, then I bang out the code with an eye distributed over
SUSv2, integer promotions and conversions, sequence points, operator
associativity and precedence, etc. The process is slow as hell, but C
is not a toy.

At any point of your program, you should be able to tell the range of
your integer variables accessed there, the size of your strings, the
ownership of your malloc()'d areas, etc. If you do floating point
(which I'm not insane enough to), add error bounds to the mix.

Cheers,
lacos
self-important jerk, sorry :(


[0] http://www.opengroup.org/onlinepubs/007908775/xsh/limits.h.html
[1] http://www.opengroup.org/onlinepubs/007908775/xsh/sysconf.html
[2] http://www.unix.org/whitepapers/64bit.html
[3] http://www.opengroup.org/onlinepubs/007908775/xsh/stddef.h.html