size_t or int for malloc-type functions?

[av]

No, truth is always right, no matter how much nonsense people try to
conceal it behind.

"experimental truth" or "pragmatic truth" is better than just "truth"

i begin to think size_t can lead to bugs for the overflow allowance
(integer overflow for c library functions arguments is not good)
and the functions in the standard that use it are wrong because it is
sufficient an overflow in their arguments for doing ugly errors
that is difficult to find because are only for some value its argumet

in the other side, if a function use int
i can see if the arg is ok with the instruction
if(paremater<0) return error;

 

[av]

No, it cannot. Unsigned integer arithmetic is clearly described as being
performed modulo (2 to the power of the number of value bits in the type);
in other words, the unsigned integers representable by the type form a
ring. Mathematically, the multiplication of two integers in a ring yields
another integer in that ring. So, when you multiply two values of size_t
(which are indeed in such a ring, with 2 to the power of b elements where b
is the number of value bits in a size_t), you get another value in the
ring, so it must be representable in a size_t.

are you joking?




if there is an "unsigned overflow" (if you can not follow me, the
value that "c" has in each instruction "c=a*b;" or "c=a+3;"
size_t a=-1, b=2, c=a*b;
c=a+3;
)

if that "unsigned overflow" happen to the parameter of some function
that use "size_t" is error.


that error is difficult to find because
it is find only for some values of "a","b", "c" but people in
bugtraq appear to know these values )

first to speak do you know how many errors of that kind there are in
bugtraq?

ha yes you don't do errors....

 

[Richard Heathfield]

av said:

are you joking?

No.

 

[av]

"experimental truth" or "pragmatic truth" is better than just "truth"

i begin to think size_t can lead to bugs for the overflow allowance
(integer overflow for c library functions arguments is not good)
and the functions in the standard that use it are wrong because it is
sufficient an overflow in their arguments for doing ugly errors
that is difficult to find because are only for some value its argumet

in the other side, if a function use int
i can see if the arg is ok with the instruction
if(paremater<0) return error;

it should be good to do some new type

struct NewSize_t_{
int ovf;
size_t n;
};

typedef NewSize_t_ NewSize_t;

with +-*/ defined on NewSize_t
and use it like parameter for function that now use size_t

if some overflow occur "ovf==1" and the function know parameter is not
ok
but that unsigned type above could be useful for all others
calculation that has not need overflows

i think it is possible to change size_t to that struct
and use the oveflow flag for see all is ok

and this resolve to the root the problem
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

 

[Richard Heathfield]

av said:

it should be good to do some new type

struct NewSize_t_{
int ovf;
size_t n;
};

typedef NewSize_t_ NewSize_t;

with +-*/ defined on NewSize_t
and use it like parameter for function that now use size_t

if some overflow occur

As has been explained ad nauseam, no overflow occurs.

and this resolve to the root the problem

What problem? I don't see one that can't be solved much more simply by
behavioural change than by adding a new type to the language and then
waiting 20 years for it to get implemented across the board.

 

[av]

it should be good to do some new type

struct NewSize_t_{
int ovf;
size_t n;
};

typedef NewSize_t_ NewSize_t;

in other words i say

struct size_t_{
unsigned n;
int ovf;
};

typedef size_t_ size_t;

with +-*/ defined on size_t
and use it like parameter for functions
if some overflow occur "ovf==1" and the function know parameter is not
ok
but that unsigned type above could be useful for all others
calculation that has not need overflows
if there is a complex calculation i can see if there is some overflow
in the result

 

[Keith Thompson]

Keith Thompson said:

jacob navia said: [...]
what is clearly not
enough space to store 65521 objects of size 65552
each. You are free to call that "multiplication that
doesn't overflow".

The Standard says it doesn't overflow, and therefore it doesn't overflow
(unless the Standard is wrong, which is something you can take up with
ISO if you like, but I don't rate your chances).

[...]

You're both arguing about the meaning of the word "overflow",

No, there is no argument here. The Standard is quite clear on the matter.
That Mr Navia cannot understand this does not mean that the matter is open
to dispute; it merely means that he cannot understand it.

I think when jacob talks about "overflow" of unsigned multiplication,
he's referring to an operation that, if it were carried out using true
mathematical integers, would yield a result that cannot be represented
in the unsigned type. (C, as we all know, deals with this by reducing
the mathematical result modulo 2**N.) I think that the fact that the
standard doesn't refer to this as "overflow" can lead to some
confusion.

Again, this is made very clear by the Standard.

Yes, of course.

No, it cannot.

Yes, it can, but I probably didn't state it clearly enough.

What I meant by "mathematical result" is the result of the
multiplication viewed as an operation on the infinite set of
mathematical integers. For example, suppose we're dealing with a
16-bit unsigned int. 1000U * 1000U yields a "mathematical result" of
1000000 (which is reduced modulo 65536 to 16960U).

Unsigned integer arithmetic is clearly described as being
performed modulo (2 to the power of the number of value bits in the type);
in other words, the unsigned integers representable by the type form a
ring. Mathematically, the multiplication of two integers in a ring yields
another integer in that ring. So, when you multiply two values of size_t
(which are indeed in such a ring, with 2 to the power of b elements where b
is the number of value bits in a size_t), you get another value in the
ring, so it must be representable in a size_t.

Right.

But the standard *could* have called this "overflow". It could have
said that an unsigned operation that "overflows" causes the result to
be reduced modulo 2**N. And this would have described exactly the
same language.

The standard says this isn't overflow, but referring to it as overflow
isn't entirely nonsensical; it's merely inconsistent with the wording
of the standard.

I'm trying to interpret what jacob has written. One of my goals is to
encourage him to be more careful with terminology.

Much as I respect your opinion, it does not take precedence over the
terminology used by the Standard.

Of course not. Probably writing "would have been" rather than "would
be" would have expressed my meaning more clearly.

[snip]

I agree that that is his argument, but I cannot see that it has any merit,
since there is no way for the compiler to distinguish between a user who
accidentally makes a large memory request (because his program is broken)
and a user who deliberately makes a large memory request (because he needs
lots of memory).

Agreed. Having a function detect errors is a good thing, but it
should do so only when it knows better than I do (more generally,
better than the caller) what's an error and what isn't.

The problem is that malloc(X * Y) very likely does not behave properly
if the result of X * Y does not match what I call the "mathematical
result" of X * Y. But the problem, if any, is in the evaluation of
X * Y itself. It can't be avoided in malloc(), because by then it's
too late.

 

[Keith Thompson]

Very simple. We detect the 'unsigned overflow' by:

if (((n = a * b) < a || (n < b)) overflow()
else alliswell(n);

Not necessarily. Consider 16-bit unsigned int, a == 20000, b ==
20000. a * b is 400000000; reducing modulo 2**16 yields 33792, which
is greater than both a and b. It also fails if exactly one of a or b
is zero.

I think your method works for addition, but not for multiplication.

I *think* that checking whether n / a == b will work (but it's likely
to be more expensive).

 

[Richard Heathfield]

Keith Thompson said:

Yes, it can, but I probably didn't state it clearly enough.

What I meant by "mathematical result" is the result of the
multiplication viewed as an operation on the infinite set of
mathematical integers.

There are more things in mathematics, Horatio... and I'm sure I need not
complete the misquote for you.

But the problem, if any, is in the evaluation of X * Y itself.

"If any" being the key words there.

It can't be avoided in malloc(), because by then it's too late.

Agreed.

 

[av]

av said:


As has been explained ad nauseam, no overflow occurs.

then i do for you the definition for overflow that i see

you have 3 unsigned integers type variabiles
of XXbits of name "a" "b" "c" in the computer
than you do c= b (operation) a; in the computer
where operation is + or - or *
in the computer

than you immagine that have 3 signed integers type variabiles in math
(do you know the set of natural number N? and the set Z of signed
integers?)
bb=b,aa=a,cc in Z
and do the same in Z
cc= bb (operation) aa;
where operation is + or - or *

if cc==c no overflow occurs
if cc!=c integer overflow occurs

What problem? I don't see one that can't be solved much more simply by
behavioural change than by adding a new type to the language and then
waiting 20 years for it to get implemented across the board.

the problem of overvflow definited above where it should be not be in
the calculation

 

[Richard Heathfield]

av said:

then i do for you the definition for overflow that i see

Your definition of overflow is neither here nor there. It is the Standard's
definition that matters.

you have 3 unsigned integers type variabiles
of XXbits of name "a" "b" "c" in the computer
than you do c= b (operation) a; in the computer
where operation is + or - or *
in the computer

than you immagine that have 3 signed integers type variabiles in math
(do you know the set of natural number N? and the set Z of signed
integers?)

Yes. Z is irrelevant here. Unsigned arithmetic takes place in a finite
subset of N - a ring of 2^b elements with values 0 to 2^b - 1 (where b is
the number of value bits in the type). All addition and multiplication
operations between any two values of that type give another result that is
within the ring. No overflow occurs.

bb=b,aa=a,cc in Z
and do the same in Z
cc= bb (operation) aa;
where operation is + or - or *

if cc==c no overflow occurs
if cc!=c integer overflow occurs

Not so.

the problem of overvflow definited above where it should be not be in
the calculation

No overflow occurs in unsigned arithmetic. See 3.1.2.5 of C90, or 6.2.5(9)
of C99.

 

[Keith Thompson]

Keith Thompson said:

There are more things in mathematics, Horatio... and I'm sure I need not
complete the misquote for you.

Good point. I probably should have nailed down what I meant by
"mathematical result" sooner, and/or used a different phrase.

However, note that C99 6.2.5p9 says:

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting
unsigned integer type is reduced modulo the number that is one
greater than the largest value that can be represented by the
resulting type.

The word "result" here can only refer to what I've been calling the
"mathematical result". You're complaining about my lack of precision,
but the standard's wording here is no more precise than mine. }

"If any" being the key words there.

[...]

In the following, an expression enclosed in << and >> is to be
interpreted as being evaluated over the entire infinite set of
integers.

If X and Y are values of type size_t, a call malloc(X * Y) will
attempt to allocate <<(X * Y) % (SIZE_MAX+1)>> bytes. If this is not
equal to <<X * Y>>, then the result is affected by what the standard
doesn't call "overflow" (let's call it "wraparound"). This is the
behavior clearly specified by the standard, but I can't think of any
circumstances in which it's the *desired* behavior. It's almost
certainly a logical error.

If I write malloc(X * Y), it's because I *want* to allocate <<X * Y>>
bytes. The result of the multiplication will be silently reduced
whether I want it to be or not. The only real solution, given the
language as it currently exists, is to be very careful not to let this
kind of logical error occur in the first place (because the language
is of no help in diagnosing it if I'm not sufficiently careful). This
is non-trivial. A more general solution might be to modify the
language so that cases where X * Y wraps around can be detected, but
that's not going to happen any time soon, if ever.

Somebody (jacob, I think) suggested using calloc(X, Y) rather than
malloc(X * Y), assuming that calloc() correctly detects wraparound on
the multiplication. I disagree with this for two reasons. First,
it's already been pointed out that not all implementations of calloc()
get this right. Second, zeroing the allocated memory is likely to be
wasteful.

If this is a concern, you can write a wrapper around malloc() that
takes two arguments (as calloc() does) and checks whether the result
wraps around. Something like this (obviously untested):

void *malloc_wrapper(size_t x, size_t y)
{
if (/* x*y wraps around */) {
return NULL;
}
else {
return malloc(x * y);
}
}

Implementing the wraparound test is left as an exercise.

 

[Keith Thompson]

No overflow occurs in unsigned arithmetic. See 3.1.2.5 of C90, or 6.2.5(9)
of C99.

Quibble: You mean 3.1.2.5 of C89 (the original ANSI standard); in C90,
the nearly identical ISO standard, it's 6.1.2.5.

 

[Richard Heathfield]

Keith Thompson said:

However, note that C99 6.2.5p9 says:

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting
unsigned integer type is reduced modulo the number that is one
greater than the largest value that can be represented by the
resulting type.

The word "result" here can only refer to what I've been calling the
"mathematical result". You're complaining about my lack of precision,
but the standard's wording here is no more precise than mine. }

I'll sue them later. Moving on...

If X and Y are values of type size_t, a call malloc(X * Y) will
attempt to allocate <<(X * Y) % (SIZE_MAX+1)>> bytes. If this is not
equal to <<X * Y>>, then the result is affected by what the standard
doesn't call "overflow" (let's call it "wraparound"). This is the
behavior clearly specified by the standard, but I can't think of any
circumstances in which it's the *desired* behavior. It's almost
certainly a logical error.

The error is the programmer's, not the language's, fault: trying to allocate
memory for a single object of a size greater than the maximum value that a
size_t can store is just silly.

If I write malloc(X * Y), it's because I *want* to allocate <<X * Y>>
bytes. The result of the multiplication will be silently reduced
whether I want it to be or not.

Correct. But this is only a problem if allocating X * Y bytes does not make
sense within the context of the system you are using, in which case you
shouldn't do it in the first place.

<snip>

 

[Richard Heathfield]

Keith Thompson said:

Quibble: You mean 3.1.2.5 of C89 (the original ANSI standard); in C90,
the nearly identical ISO standard, it's 6.1.2.5.

Clumsy of me. Thank you for the correction.

 

[Kenny McCormack]

av said:


No.

The truly scary thing is that after reading RH's drivel for a while, you
begin to realize, that like his mentor Dubya, he *actually* believes the
claptrap he's spewing! I mean, seriously, like Dubya, he's not lying!

And *that*, my friends, is the true definition of scary.

 

[CBFalconer]

av said:



As has been explained ad nauseam, no overflow occurs.



What problem? I don't see one that can't be solved much more
simply by behavioural change than by adding a new type to the
language and then waiting 20 years for it to get implemented
across the board.

for example:

size_t overflow(size_t x, size_t y) {
size_t xmax, ymax, szmax = -1;

if (xmax && ymax) {
xmax = szmax / ymax; ymax = szmax / xmax;
if ((x > xmax) || (y > ymax) return 0;
return x * y;
}
return 0;
}

assuming 0 is a suitable result for an overflow.

Besides which av is a troll.

 

[CBFalconer]

No. Say UINT_MAX is 65535, observe that 257 * 257 == 65536 + 513.

The simple test for whether two size_t variables can be multiplied
is...

if (a <= ((size_t) -1) / b)
/* good */;
else
/* bad */;

You're right, and I corrected (over corrected) it in a post a few
minutes ago.

 

[kuyper]

The truly scary thing is that after reading RH's drivel for a while, you
begin to realize, that like his mentor Dubya, he *actually* believes the
claptrap he's spewing! I mean, seriously, like Dubya, he's not lying!

And *that*, my friends, is the true definition of scary.

It's not claptrap, unlike what Dubya is spewing, and I would therefore
certainly hope he's sufficiently intelligent and mathematically
well-educated to believe it. I'd recommend reading up on the
mathematical concept of rings before you claim otherwise.

 

[jacob navia]

(e-mail address removed) a écrit :

It's not claptrap, unlike what Dubya is spewing, and I would therefore
certainly hope he's sufficiently intelligent and mathematically
well-educated to believe it. I'd recommend reading up on the
mathematical concept of rings before you claim otherwise.

Who cares about rings?

We are speaking about overflow in a well defined
context. Yes, the C standard defines the behavior
for overflow, and overflow then, it is defined
for unsigned integers. This doesn't mean that it
doesn't happen or that this "ring" stuff is meaningful.

Or are you implying that

65521 x 65552 is 65296 and NOT 4295032592

????

With that 'x' I mean multiplication as is
understood by all people in this planet except
C buffs that know more about C standards than about
software engineering and mathematics???

What the standard is doing is merely accepting
overflow after the fact, and "defining" multiplication
by unsigned integers as an operation within a ring of
integers.

This "meaning" to multiplication is maybe OK for justifying
the behavior of C, but it is nothing else than
describing what an overflow DOES in most machines!

The nonsense of heathfield becomes worst given the context where
he is saying that we should go on using this construct:

malloc (n * sizeof *p)

to allocate memory instead of using calloc that should test
for overflow!

The bug I am referring to is when you multiply
65521 * 65552 --> 65 296

Since malloc doesn't see anything wrong it will succeed,
giving you a piece of RAM that it is NOT as long as you
would think it is, but several orders of magnitude SMALLER.

Even when heathfield says a patently insane stuff he is
"the guru" and people here will justify his ramblings.

I am well aware of what the standard says for overflow.
I studied the question when I implemented (as the only C
compiler in existence) an OVERFLOW CHECK feature that
would trap on overflow. And I did it only for signed
integers to remain compatible with the standard.

Nevertheless this behavior of unsigned C arithmetic is
sureley NEVER CORRECT and I have never seen a useful
program that relies on this behavior for something useful.

jacob