473,327 Members | 1,920 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,327 software developers and data experts.

size_t or int for malloc-type functions?

Rcently I posted code in this group, to help a user
that asked to know how he could find out the size of
a block allocated with malloc.

As always when I post something, the same group
of people started to try to find possible errors,
a harmless passtime they seem to enjoy.

One of their remarks was that I used "int" instead of
"size_t" for the input of my allocator function.

As I explained, I prefer a signed type to the
unsigned size_t because small negative number will be
confused with huge integers when interpreted as unsigned.

I researched a bit the subject, and I found a type

ssize_t

The name is defined for instance in
http://www.delorie.com/gnu/docs/glibc/libc_239.html

Data Type: ssize_t
This data type is used to represent the sizes of blocks that can be
read or written in a single operation. It is similar to size_t, but must
be a signed type.

Another reference to this type appears in:
http://bochs.sourceforge.net/cgi-bin...dent?i=ssize_t
with
#define ssize_t long

This concern with the usage of an unsigned type that can be
easily lead to errors (of course only for people that do
make errors like me...) is also expressed in the document
ISO/IEC JTC1 SC22 WG14 N1135 :
"Specification for Safer, More Secure C Library Functions"
where they propose:

Extremely large object sizes are frequently a sign that an object’s size
was calculated incorrectly. For example, negative numbers appear as very
large positive numbers when converted to an unsigned type like size_t.

Also, some implementations do not support objects as large as the
maximum value that can be represented by type size_t.

For those reasons, it is sometimes beneficial to restrict the range of
object sizes to detect programming errors.

They propose having an unsigned rsize_t, but a macro RSIZE_MAX that
would limit the range of the object size.

I post this to document why having an "int" as an argument to a
malloc-type function is not such a bad idea.

Your opinion may differ.

jacob
Dec 31 '06
318 12642
jacob navia wrote:
A programmer is a human, and human make errors. This discussion
is not designed for people that do not make errors. It is for
people that want to discuss how can we build safety into software
in such a waythat the consequences of errors are limited, for instance
a malloc that diagnoses a bogus argument returns NULL instead of
crashing the software.
The real problem is how do you diagnose bogus arguments without making
unwarranted assumptions and severely restricting *everyone* at *every
call* to malloc so that you can save people from a pretty rare mistake?
I think you're focusing on solving the problem at the wrong place. It
should be either a behavior adjustment as some have suggested or a
correctness tool outside of malloc that can toss a warning during
compilation. Neither one is a great solution, and I would favor the
former because it doesn't encourage reliance on tools.

Jan 2 '07 #51
jacob navia wrote:
>
.... snip ...
>
Suppose:
struct S {
unsigned n;
double d;
double data[8192];
};

I want to allocate 65520 objects of size 65 552 bytes each.

If you do that in a 32 bit system what you obtain?
i=65520, i*sizeof(*p)=4,294,967,040 as signed number = -256

WE OBTAIN A NEGATIVE NUMBER.
Very simple. We detect the 'unsigned overflow' by:

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

--
Merry Christmas, Happy Hanukah, Happy New Year
Joyeux Noel, Bonne Annee.
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Jan 2 '07 #52
Richard Heathfield wrote:
Richard Tobin said:
>Richard Heathfield <rj*@see.sig.invalidwrote:
<snip>
>>So we have size_t * size_t - how, precisely, will that produce a
negative number when passed to a function taking size_t as an
argument?

Well obviously it won't.

Quite so.
>But the idea was to protect against programmers who make mistakes,
and as we all know not all programmers use that idiom.

The fix, then, is obvious.
>As I said, I don't think the proposal would do much good, but
surely you can see what the idea was?

It appeared to be an attempt to introduce the additional risk of
overflow to the existing risk of specifying an allocation amount
other than the amount actually required. No, I don't see why this
would be of benefit.
What this has brought home to me is that calloc should be included
in the nmalloc package, so that the same maximum size criterion
will be applied. I.E:

void *ncalloc(size_t nmemb, size_t size) {
size_t sz;
void *p;

sz = nmemb * size;
if ((sz < nmemb) || (sz < size)) return NULL;
if (p = nmalloc(sz)) memset(p, 0, sz);
return p;
}

Since nmalloc drives a 0 size up to 1, this leaves a problem for
nmemb or size being zero. I don't know whether it is worth
worrying about. I am also having qualms about the overflow test.
There doesn't seem to be a SIZE_T_MAX in limits.h. I am worrying
about something like "p = calloc(7, (SIZE_T_MAX/4 + 1));".

cross-posted to c.std.c to see if there is any opinion on this.

--
Merry Christmas, Happy Hanukah, Happy New Year
Joyeux Noel, Bonne Annee.
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Jan 2 '07 #53
On Mon, 1 Jan 2007 18:59:04 -0600, jacob navia wrote
(in article <45***********************@news.orange.fr>):
Randy Howard a écrit :
>I'll take a stab it. The proposal is to arbitrarily chop the available
address in space, for those rare cases in which someone wishes to
malloc an amount of memory /larger/ than the available address space on
the processor. I.e., they want a boatload of RAM, so restrict them to
less than half of that they need to make things "safer". That has BS
written all over it, imo.

Not at all. Please just see what the proposal really was
before going to answer to phantasy proposals.

The proposal was discussing the idea of using a signed
type to avoid problems with small negative numbers
that get translated into huge unsigned ones.

THAT was the reason.
There was a typo (brain fart) in my original quoted above, which was to
read "chop the address space in half"...

Well, that's exactly what your proposal does. No thank you. size_t
exists for a very good reason. I am willing to take the risk that if
if I manage to somehow attempt to compute a value that is larger than
size_t variables can hold that problems will occur. That is far and
away better than chopping the range of mallocs in half for a but of
questionable safety.
After this discussion, and after the remarks of Mr Plauger
I am not so sure that that proposal was actually a very good
idea.
I agree.
The problem is in this discussions, that everybody is trying to
discuss in such an emotional way, that acknowledging
something in your "adversary" argumentation is seen as
an equivalent of "surrender"...
The only one exhibiting any obvious sign of emotionalism is you. I
have no idea why.
Look at you, deforming the proposal in such a way that
it is completely NUTS. Of course THEN it is easy to
say:

IT IS NUTS!!!
Well, sorry. It pretty much matches the actual /results/ of what your
proposed to the letter. Maybe not the intent, but that's what comes of
it. And those results are nuts. You seem to recognize that yourself
now, so kudos to you.
The argument of Mr Plauger that convinces me is that anyway
a multiplication error like the one I signaled to heathfield
will ANYWAY cause havoc even if we put the signed type in
the argument to malloc, so it is actually not a good idea at all.
bingo.
>If the programmer knows how to ask for that much memory, but can't
figure out how to make sure he doesn't ask for more than will fit in
size_t, he needs to be writing DOS .bat files instead, where he can do
less damage. Or maybe he should just go off and write his own pseudo-C
compiler instead.

A programmer is a human, and human make errors.
Yes, and when they do, they debug their programs and attempt to make
those errors go away. Here's a dirty little secret for you: Computers
make errors too. They are not even digital on the inside, contrary to
popular mythology. They're little confused layers upon layers of
antennae that pick up noise and xtalk and do /not/ always put out the
correct 0/1 result for a given set of inputs. Google for "Simultaneous
Switching Output Noise" for a good example of one of the more hairy
forms of this problem. they're analog devices that sometimes do a good
job of simulating a binary computer.
This discussion is not designed for people that do not make errors.
No doubt, since I've been searching for several decades for such a
person, and have yet to find one.
It is for
people that want to discuss how can we build safety into software
in such a waythat the consequences of errors are limited, for instance
a malloc that diagnoses a bogus argument returns NULL instead of
crashing the software.
malloc() can not, and will not read minds. It will not know if you
really /meant/ to try and malloc() 2GB+40K of RAM, or if it was an
accident. All it needs to do is malloc that amount, or return NULL.
It's up to you to decide what to do afterward. Even better, you would
know the range of size_t on your platform and check your numbers
/before/ you call malloc. Plenty of people like to use malloc wrapper
functions, this seems like a candidate for such a thing if you want to
make programming safer, not hacking on the libc implementation.

--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

Jan 2 '07 #54
Keith Thompson said:
Richard Heathfield <rj*@see.sig.invalidwrites:
>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.
which is
IMHO less important than the actual behavior of integer types.
Again, this is made very clear by the Standard.
Multiplication of two values of type size_t (or of any unsigned
integer type) can yield a mathematical result that cannot be
represented as a value of type size_t.
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.
The standard does not call
this "overflow", but in my opinion "overflow" *would* be a valid term
for it.
Much as I respect your opinion, it does not take precedence over the
terminology used by the Standard.
The point is this: If a result of an unsigned multiplication cannot be
represented, the result is reduced modulo 2**N (where the maximum
value of the type is 2**N-1 -- "**" denotes exponentiation). If the
result of a signed multiplication cannot be represented, the behavior
is undefined.
It is true that introducing signed ints into the mix exposes the process of
dynamically allocating memory to yet another risk of undefined behaviour,
yes - and since this is supposedly all about protecting the ignorant or
careless programmer from his mistakes, I'm not convinced that giving him
another way of screwing up constitutes protecting him.
Using an unsigned type as the parameter of malloc() means that a
larger range of arguments can be used than if it took the
corresponding signed type. This can be significant for systems with a
16-bit size_t that can allocate more than 32767 bytes, or for systems
with a 32-bit size-t that can allocate more than 2147483647 bytes.
Right.
jacob's argument is that using a signed type for the parameter of a
malloc-like function is beneficial, supposedly because if a user
incorrectly passes a very large value as the argument, it is likely to
wrap around to a negative value, which can be detected as an error.
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).

<snip>

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Jan 2 '07 #55
CBFalconer wrote:
Richard Heathfield wrote:
Richard Tobin said:
Richard Heathfield <rj*@see.sig.invalidwrote:
<snip>
>So we have size_t * size_t - how, precisely, will that produce a
negative number when passed to a function taking size_t as an
argument?

Well obviously it won't.
Quite so.
But the idea was to protect against programmers who make mistakes,
and as we all know not all programmers use that idiom.
The fix, then, is obvious.
As I said, I don't think the proposal would do much good, but
surely you can see what the idea was?
It appeared to be an attempt to introduce the additional risk of
overflow to the existing risk of specifying an allocation amount
other than the amount actually required. No, I don't see why this
would be of benefit.

What this has brought home to me is that calloc should be included
in the nmalloc package, so that the same maximum size criterion
will be applied. I.E:

void *ncalloc(size_t nmemb, size_t size) {
size_t sz;
void *p;

sz = nmemb * size;
if ((sz < nmemb) || (sz < size)) return NULL;
if (p = nmalloc(sz)) memset(p, 0, sz);
return p;
}

Since nmalloc drives a 0 size up to 1, this leaves a problem for
nmemb or size being zero. I don't know whether it is worth
worrying about.
If nmalloc() and ncalloc() are to be used as replacements for or
implementations of malloc() and calloc(), keep in mind that whether
malloc(0) returns NULL is implementation-defined. I don't believe there
is anything preventing the implementation from defining that malloc(0)
and calloc(0, 0) are different from calloc(1, 0) and calloc(0, 1) in
this regard, but this would need to be documented accurately. I believe
it's very easy to avoid this problem by simply replacing your check
with:
if ((sz < nmemb) && (sz < size))
but I may be overlooking something.
I am also having qualms about the overflow test.
There doesn't seem to be a SIZE_T_MAX in limits.h.
There's SIZE_MAX, but even without it, you could convert -1 to size_t.
I am worrying
about something like "p = calloc(7, (SIZE_T_MAX/4 + 1));".

cross-posted to c.std.c to see if there is any opinion on this.
Jan 2 '07 #56
Harald van Dijk wrote:
I believe
it's very easy to avoid this problem by simply replacing your check
with:
if ((sz < nmemb) && (sz < size))
but I may be overlooking something.
I was, of course. Sorry, and please don't do that, it won't work.

Jan 2 '07 #57
Harald van D?k wrote:
CBFalconer wrote:
.... snip ...
>>
What this has brought home to me is that calloc should be included
in the nmalloc package, so that the same maximum size criterion
will be applied. I.E:

void *ncalloc(size_t nmemb, size_t size) {
size_t sz;
void *p;

sz = nmemb * size;
if ((sz < nmemb) || (sz < size)) return NULL;
if (p = nmalloc(sz)) memset(p, 0, sz);
return p;
}

Since nmalloc drives a 0 size up to 1, this leaves a problem for
nmemb or size being zero. I don't know whether it is worth
worrying about.

I am also having qualms about the overflow test.
There doesn't seem to be a SIZE_T_MAX in limits.h.

There's SIZE_MAX, but even without it, you could convert -1 to size_t.
>I am worrying
about something like "p = calloc(7, (SIZE_T_MAX/4 + 1));".

cross-posted to c.std.c to see if there is any opinion on this.

If nmalloc() and ncalloc() are to be used as replacements for or
implementations of malloc() and calloc(), keep in mind that whether
malloc(0) returns NULL is implementation-defined. I don't believe there
is anything preventing the implementation from defining that malloc(0)
and calloc(0, 0) are different from calloc(1, 0) and calloc(0, 1) in
this regard, but this would need to be documented accurately. I believe
it's very easy to avoid this problem by simply replacing your check
with:
if ((sz < nmemb) && (sz < size))
but I may be overlooking something.
I think the test detects a zero field already. The problem is that
that is legitimate, and so it should procede to nmalloc, which
handles the zero allocation test already. The test should probably
be:

if ((nmemb && size) && (sz < nmemb) || (sz < size)) return NULL;

but that doesn't handle the calloc call case I mentioned above.

--
Merry Christmas, Happy Hanukah, Happy New Year
Joyeux Noel, Bonne Annee.
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Jan 2 '07 #58
CBFalconer wrote:
We detect the 'unsigned overflow' by:

if (((n = a * b) < a || (n < b)) overflow()
else alliswell(n);
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 */;

--
Peter

Jan 2 '07 #59
av
On Mon, 01 Jan 2007 21:41:50 +0000, Mark McIntyre wrote:
>On Mon, 01 Jan 2007 20:01:54 +0100, in comp.lang.c , jacob navia
<ja***@jacob.remcomp.frwrote:
>>Clark S. Cox III a écrit :
>>>
Oh, don't take my post the wrong way; just because I corrected a single
factual error in his post, I still agree with him; and disagree with you.

His majesty is always right, no matter how much nonsense
he says.

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;
Jan 2 '07 #60
av
On Tue, 02 Jan 2007 03:32:59 +0000, Richard Heathfield wrote:
>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....
Jan 2 '07 #61
av said:
On Tue, 02 Jan 2007 03:32:59 +0000, Richard Heathfield wrote:
>>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?
No.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Jan 2 '07 #62
av
On Tue, 02 Jan 2007 10:10:36 +0100, av wrote:
>"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
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Jan 2 '07 #63
av said:

<snip>
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.

<snip>
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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Jan 2 '07 #64
av
On Tue, 02 Jan 2007 10:57:22 +0100, av wrote:
>On Tue, 02 Jan 2007 10:10:36 +0100, av wrote:
>>"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;
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
Jan 2 '07 #65
Richard Heathfield <rj*@see.sig.invalidwrites:
Keith Thompson said:
>Richard Heathfield <rj*@see.sig.invalidwrites:
>>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.
>which is
IMHO less important than the actual behavior of integer types.

Again, this is made very clear by the Standard.
Yes, of course.
>Multiplication of two values of type size_t (or of any unsigned
integer type) can yield a mathematical result that cannot be
represented as a value of type size_t.

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.
>The standard does not call
this "overflow", but in my opinion "overflow" *would* be a valid term
for it.

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]
>jacob's argument is that using a signed type for the parameter of a
malloc-like function is beneficial, supposedly because if a user
incorrectly passes a very large value as the argument, it is likely to
wrap around to a negative value, which can be detected as an error.

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 (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jan 2 '07 #66
CBFalconer <cb********@yahoo.comwrites:
[...]
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).

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jan 2 '07 #67
Keith Thompson said:
Richard Heathfield <rj*@see.sig.invalidwrites:
>Keith Thompson said:
<snip>
>
>>Multiplication of two values of type size_t (or of any unsigned
integer type) can yield a mathematical result that cannot be
represented as a value of type size_t.

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.
There are more things in mathematics, Horatio... and I'm sure I need not
complete the misquote for you. :-)

<snip>
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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Jan 2 '07 #68
av
On Tue, 02 Jan 2007 10:03:34 +0000, Richard Heathfield wrote:
>av said:
<snip>
>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.
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
><snip>
>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.
the problem of overvflow definited above where it should be not be in
the calculation
Jan 2 '07 #69
av said:
On Tue, 02 Jan 2007 10:03:34 +0000, Richard Heathfield wrote:
>>
As has been explained ad nauseam, no overflow occurs.

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.
>><snip>
>>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.

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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Jan 2 '07 #70
jacob navia wrote:
P.J. Plauger a écrit :
>That may be your experience, but mine has been that 16-bit systems
often have >32KB of memory. Anything that interferes with handling
all of memory in one go is sure to cause trouble, sooner or later.

Yes. You are right in this point. For 16 bit systems the
lost of 32K of addressing space is quite a hit. Specially
if you do have the full 64K.
You may even have more than 64K, for example on MS-DOS you can have 10
of the 64K regions for a total of 640K. An int is -32768 to 32767 and
size_t is 0 to 65535. Pointers must be more than 16 bits of course if
they can refer to allocations inside separate regions. Each of these
allocations may take up nearly the full 64K maximum object size.

#include <stdio.h>
#include <stdlib.h>

#define N 10

int main(void)
{
char *p[N];
int i;
for(i = 0; i < N; i++) p[i] = malloc(60000);
for(i = 0; i < N; i++) printf("%p\n", (void*)p[i]);
return 0;
}

This program attempts to malloc 10 blocks of 60000 bytes, and prints out
the pointers. On a 640K MS-DOS system in 'large' or 'huge' memory model
where pointers are 32 bits in a segment:offset format, it outputs
something like:

10C4:0008
1F6B:0008
2E12:0008
3CB9:0008
4B60:0008
5A07:0008
68AE:0008
7755:0008
85FC:0008
0000:0000

The last allocation failed, since the 10th block is unavailable for
malloc's use; it probably contains the program's code, stack, etc.

However on a 'small' or 'medium' memory model where pointers are just 16
bits, it outputs:

0B24
0000
0000
0000
0000
0000
0000
0000
0000
0000

Indicating that only the first allocation succeeded. Memory outside of
the first 64K is unavailable since 16-bit pointers cannot address it.

--
Simon.
Jan 2 '07 #71
Richard Heathfield <rj*@see.sig.invalidwrites:
Keith Thompson said:
>Richard Heathfield <rj*@see.sig.invalidwrites:
>>Keith Thompson said:

<snip>
>>
>>>Multiplication of two values of type size_t (or of any unsigned
integer type) can yield a mathematical result that cannot be
represented as a value of type size_t.

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.

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. 8-)}
<snip>
>But the problem, if any, is in the evaluation of X * Y itself.

"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 (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jan 2 '07 #72
Richard Heathfield <rj*@see.sig.invalidwrites:
[...]
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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jan 2 '07 #73
Keith Thompson said:

<snip>
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. 8-)}
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
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Jan 2 '07 #74
Keith Thompson said:
Richard Heathfield <rj*@see.sig.invalidwrites:
[...]
>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.
Clumsy of me. Thank you for the correction.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Jan 2 '07 #75
In article <Ho*********************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:
>av said:
>On Tue, 02 Jan 2007 03:32:59 +0000, Richard Heathfield wrote:
>>>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?

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.

Jan 2 '07 #76
Kenny McCormack wrote:
In article <Ho*********************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:
av said:
On Tue, 02 Jan 2007 03:32:59 +0000, Richard Heathfield wrote:
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?
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.
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.

Jan 2 '07 #77
Richard Heathfield wrote:
av said:

<snip>
>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.

<snip>
>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.
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.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
Jan 2 '07 #78
Peter Nilsson wrote:
CBFalconer wrote:
>We detect the 'unsigned overflow' by:

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

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.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
Jan 2 '07 #79
ku****@wizard.net a écrit :
Kenny McCormack wrote:
>>In article <Ho*********************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:
>>>av said:
On Tue, 02 Jan 2007 03:32:59 +0000, Richard Heathfield wrote:

>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?

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.


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
Jan 2 '07 #80
jacob navia said:

<snip>
Who cares about rings?
Anyone who cares about how unsigned integer arithmetic works in C.
We are speaking about overflow in a well defined
context.
Overflow doesn't occur with unsigned integer types in C. We covered that.
Yes, the C standard defines the behavior
for overflow, and overflow then, it is defined
for unsigned integers.
No, overflow *doesn't happen* for unsigned integers.
This doesn't mean that it
doesn't happen or that this "ring" stuff is meaningful.
Yes, it does.
Or are you implying that

65521 x 65552 is 65296 and NOT 4295032592
It's implementation-defined. The result of multiplying two unsigned types
together depends on their values and the width of the type.

<snip>
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!
What you call nonsense is in fact good sense. Using calloc is almost always
the wrong thing, since calloc writes 0 to every byte in the allocated
block, which is hardly ever the right thing to do. (If all-bits-zero meant
NULL for pointers and 0.0 for floating point values, that would be a
different matter, but they don't so it isn't.) Furthermore, if n is an
unsigned type (as it should be, in my opinion), n * sizeof *p can't
overflow so there is nothing for calloc to test.
The bug I am referring to is when you multiply
65521 * 65552 --65 296
If you can meaningfully allocate 65521*65552 bytes in a single aggregate
object, then sizeof has to be able to report the size of such an object,
which means size_t has to be at least 33 bits, which means the "bug" you
refer to doesn't occur. If size_t is no more than 32 bits, it doesn't make
sense to try to allocate an aggregate object 2^32-1 bytes in size.
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.
As a matter of fact, it will give you at least the number of bytes you
requested (if it gives you any bytes at all). It is not malloc's fault if
you have misinterpreted unsigned integer arithmetic.
Even when heathfield says a patently insane stuff he is
"the guru" and people here will justify his ramblings.
If what I say is insane, it should be easy to disprove. But you've never
managed it yet.
I am well aware of what the standard says for overflow.
Then you will understand that to use a signed type instead of an unsigned
type as an argument to malloc is to introduce the potential for undefined
behaviour without solving the problem you were setting out to solve, and is
therefore a bad idea.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Jan 2 '07 #81
Richard Heathfield a écrit :
>
>>The bug I am referring to is when you multiply
65521 * 65552 --65 296


If you can meaningfully allocate 65521*65552 bytes in a single aggregate
object, then sizeof has to be able to report the size of such an object,
which means size_t has to be at least 33 bits, which means the "bug" you
refer to doesn't occur. If size_t is no more than 32 bits, it doesn't make
sense to try to allocate an aggregate object 2^32-1 bytes in size.

C'MON HEATHFIELD
can you STOP IT???????

BUGS NEVER MAKE SENSE!!!

THAT'S WHY THEY ARE BUGS!!!!

Your "reasoning" is

Patient: Doctor doctor, each time I move my leg I have an horrible
pain!!!

Doctor Heathfield: Well, do not move it then!!!

The whole point is precisely that an overflow bug can occur
in your "idiom" and to avoid it there are two solutions:

1) Call calloc(n,size);
2) If you do not want to use calloc because of the wasted
micro-micro seconds in zeroing the memory you write your own.

For example:
With 32 bit ints, and 64 bit long longs ( a common configuration)
you write:

void *mycalloc(size_t n, size_t s)
{
long long m = (long long)s * (long long) n;
if (m>>32)
return 0;
return malloc((size_t)m);
}

The test (m>>32) just tests the upper 32 bits. Obviously
more sophisticated tests are possible.
Jan 2 '07 #82

jacob navia wrote:

[snip]
>
His majesty is always right, no matter how much nonsense
he says.
There is no way to obtain a negative size_t.

Of course not. It is an unsigned number. The whole point is that
when you have

void fn(unsigned arg);

and you write:

fn(-3);

an implicit cast from signed to unsigned is done,
what in all implementations I know leads to no
machine code, but just a change in the way the bits
of the argument are interpreted.

Obviously this is a simplification of a real situation
when the values are not explicitely gibve like in the
example above.

Unsigned types don't overflow.

This is nonsense. Why I obtain

65521 * 65552 --65296 ????

You (and heathfield) are just playing with words. That
overflow is defined for unsigned numbers within C doesn't
mean that the result is mathematically VALID, or that is
the expected result.
Just because the result isn't what's expected doesn't mean the
operation is mathematically invalid.
The whole point of my argumentation is that the "idiom"

result = malloc(n * sizeof *p);

is a dangerous construct.
This is like arguing that wearing a seatbelt is always dangerous
because you could potentially become trapped in a burning car after a
wreck. Weakness in one corner case *does not* translate to "dangerous"
in general. The benefit of using the idiom far outweighs the potential
risk.

There are two ways to deal with this problem. One method would be to
perform a basic sanity check against an unsigned wraparound *before*
calling malloc(); it shouldn't be hard to create a wrapper function
that takes an element size and count and returns NULL (and potentially
sets errno) if the requested block is too large:

int *x = sane_malloc(sizeof *x, count);
if (!x)
{
if (errno == EMEMRQST) // or code of your choice
{
// memory request exceeds size_t
}
}

Another method is to hack malloc() to take a signed argument and pray
that every system it's implemented on treats signed integer overflow in
the same useful manner.

I know which method I'd prefer.
Use

result = calloc(n, sizeof(*p))

and ensure your implementation of calloc doesn't have the bug!

A signed argument to malloc makes absolutely no sense.

It would catch the overflow in some cases above, as I explained in
my post.
So, basically, you're willing to trade the illusion of safety in one
corner case for cutting your usable address space in half.
>
You ropinion may be different, but it would be helpful if you
tried to advance an argument, just saying
"makes no sense"

makes no sense to anyone but you.
It makes no sense to me, either. You think you're protecting a
programmer from shooting himself in the foot, but in reality you're
just giving him extra bullets. Now he can call malloc() with an
invalid size request *by design*.

Jan 2 '07 #83
In article <i_*********************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:
>jacob navia said:

<snip>
>Who cares about rings?

Anyone who cares about how unsigned integer arithmetic works in C.
Found those WMDs yet?

Jan 2 '07 #84
CBFalconer <cb********@yahoo.comwrites:
What this has brought home to me is that calloc should be included
in the nmalloc package, so that the same maximum size criterion
will be applied. I.E:

void *ncalloc(size_t nmemb, size_t size) {
size_t sz;
void *p;

sz = nmemb * size;
if ((sz < nmemb) || (sz < size)) return NULL;
if (p = nmalloc(sz)) memset(p, 0, sz);
return p;
}
<snip>
I am also having qualms about the overflow test.
I think it is wrong about 1/3 of the time. I.e. there are many cases
where the multiplication wraps round but where the reduced result (sz)
is not less than one or other of multipliers.

P J Plauger recently posted a division-based test. I don't know of a
simple test for a multiplication that will overflow that does not use
division. The fact that no one has posted one so far suggests that
there isn't one but I look forward to being wrong about that :-)

--
Ben.
Jan 2 '07 #85
jacob navia said:
Richard Heathfield a écrit :
>>
>>>The bug I am referring to is when you multiply
65521 * 65552 --65 296


If you can meaningfully allocate 65521*65552 bytes in a single aggregate
object, then sizeof has to be able to report the size of such an object,
which means size_t has to be at least 33 bits, which means the "bug" you
refer to doesn't occur. If size_t is no more than 32 bits, it doesn't
make sense to try to allocate an aggregate object 2^32-1 bytes in size.

C'MON HEATHFIELD
can you STOP IT???????
Stop what? Being right?
The whole point is precisely that an overflow bug can occur
in your "idiom"
No, it can't, as I have explained several times. Until you have done the
necessary research that enables you to understand this, there is little
point in my attempting to address your other misconceptions.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Jan 2 '07 #86
CBFalconer wrote:
Harald van D?k wrote:
CBFalconer wrote:
... snip ...
>
What this has brought home to me is that calloc should be included
in the nmalloc package, so that the same maximum size criterion
will be applied. I.E:

void *ncalloc(size_t nmemb, size_t size) {
size_t sz;
void *p;

sz = nmemb * size;
if ((sz < nmemb) || (sz < size)) return NULL;
if (p = nmalloc(sz)) memset(p, 0, sz);
return p;
}

Since nmalloc drives a 0 size up to 1, this leaves a problem for
nmemb or size being zero. I don't know whether it is worth
worrying about.

I am also having qualms about the overflow test.
There doesn't seem to be a SIZE_T_MAX in limits.h.
There's SIZE_MAX, but even without it, you could convert -1 to size_t.
I am worrying
about something like "p = calloc(7, (SIZE_T_MAX/4 + 1));".

cross-posted to c.std.c to see if there is any opinion on this.
If nmalloc() and ncalloc() are to be used as replacements for or
implementations of malloc() and calloc(), keep in mind that whether
malloc(0) returns NULL is implementation-defined. I don't believe there
is anything preventing the implementation from defining that malloc(0)
and calloc(0, 0) are different from calloc(1, 0) and calloc(0, 1) in
this regard, but this would need to be documented accurately. I believe
it's very easy to avoid this problem by simply replacing your check
with:
if ((sz < nmemb) && (sz < size))
but I may be overlooking something.

I think the test detects a zero field already.
Not consistently. If both nmemb and size are zero, then sz < nmemb is
false, and sz < size is also false, so ncalloc returns nmalloc(0). If
only one of nmemb or size is zero, then ncalloc returns NULL.

Jan 2 '07 #87
av
On Tue, 02 Jan 2007 16:55:55 +0100, jacob navia wrote:
>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.
the "behavior of unsigned C arithmetic" mod 2^n is ok.
but for normal calculation could be well have some flag in the data
position for see if there are errors in overflow for that data
>jacob
Jan 2 '07 #88
jacob navia wrote:
ku****@wizard.net 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?
Rings are the mathematical construct that correspond to the way in
which the C standard defines arithmetic for unsigned types. If you
don't care about C unsigned arithmetic, then you don't need to worry
about rings. You don't have to actually know the term; so long as you
understand what modulo means you've got enough of the concept for
practical purposes. But when you imply that modular arithmetic involves
adjusting the mathematical result, rather than actually BEING the
mathematical result, it implies that there's a deficiency in your
mathematical knowledge that you might want to correct (or not - your
choice). Granted, the mathematical terminology isn't of great practical
importance outside of mathematics. However, when you see someone using
it, I'd recommend delaying any criticism of that terminology until
you've mastered it yourself.
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
No, it defines the behavior in such a way that overflow never happens,
and says so explicitly.
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
Correct: that is precisely the case when, as in this case,
multiplication is defined modulo 65536.
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???
Don't forget mathematicians, who also have a broader understanding of
the concept of multiplication that you do.

Jan 2 '07 #89
On Tue, 2 Jan 2007 05:09:13 -0600, Keith Thompson wrote
(in article <ln************@nuthaus.mib.org>):
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.
Yeah, I said that yesterday. It didn't take hold though.

Common sense doesn't count when you are coding to protect those without
common sense. That's the best way I can think of to describe what
Navia has been up to lately.
--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

Jan 2 '07 #90
P.J. Plauger wrote:
The problem with int is that it throws away half the address space.
This is a *big* issue with 16-bit address spaces, but of course
such machines are largely relegated to embedded systems, and small
ones at that. Nevertheless, I regularly need to deal with objects
bigger than half the address space even today, perhaps because I
write so much systems code. So I find the choice of slicing the
address space in half arbitrary and potentially dangerous.
There are machines where int is 32 bits, and size_t is 64 bit. I am
sure I have used machines with 16 bit ints that could allocate objects
of a few hundred KB successfully in old DOS times.

(Question: What is the largest amount of data anyone here has
successfully allocated using malloc () and used? Just curious).

Jan 2 '07 #91
Kenny McCormack wrote:
In article <45***********************@free.teranews.com>,
Stephen Sprunk <st*****@sprunk.orgwrote:
...
Most implementors, however, take the position that it's more important
to give people the freedom to do unexpected things than to treat them
like idiots who need adult supervision. Insulting your customers is not
a sustainable business practice.

Seems to work just fine for MS. But then again, they're not "most
implementors", I suppose. They're insignificant.
In practice, many, perhaps most implementations cannot successfully
allocate anywhere near (size_t) -1 bytes.

First, if for example size_t = 32 bits, then it is likely that the OS
cannot allocate objects greater than 2^32 bytes, and the implementation
of malloc couldn't handle OS objects greater than that. malloc usually
has a few bytes of overhead, so malloc ((size_t) -1) won't succeed
anyway.

If size_t is 64 bits, there is no way malloc ((size_t) -1) could
succeed. And most 32 bit systems have limit at 3GB or 3.5GB. Something
like malloc ((size_t) -100) could only succeed on a system where size_t
is much smaller than the actual address space, for example 32 bits with
64 bit pointers.

Jan 2 '07 #92
On Tue, 2 Jan 2007 15:33:50 -0600, christian.bau wrote
(in article <11**********************@a3g2000cwd.googlegroups. com>):
P.J. Plauger wrote:
>The problem with int is that it throws away half the address space.
This is a *big* issue with 16-bit address spaces, but of course
such machines are largely relegated to embedded systems, and small
ones at that. Nevertheless, I regularly need to deal with objects
bigger than half the address space even today, perhaps because I
write so much systems code. So I find the choice of slicing the
address space in half arbitrary and potentially dangerous.

There are machines where int is 32 bits, and size_t is 64 bit. I am
sure I have used machines with 16 bit ints that could allocate objects
of a few hundred KB successfully in old DOS times.

(Question: What is the largest amount of data anyone here has
successfully allocated using malloc () and used? Just curious).
I don't recall keeping score, or trying to set a record, but I've
written code for memory testing of systems with 64GB of RAM (AMD64 and
EM64t systems) and have malloc'd (successfully) over 8GB in a single
chunk, I'm fairly sure. I don't have one in front of me with that much
memory right now, or I'd do some experiments.

--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

Jan 2 '07 #93
On Tue, 2 Jan 2007 15:49:03 -0600, christian.bau wrote
(in article <11**********************@k21g2000cwa.googlegroups .com>):
Kenny McCormack wrote:
>In article <45***********************@free.teranews.com>,
Stephen Sprunk <st*****@sprunk.orgwrote:
...
>>Most implementors, however, take the position that it's more important
to give people the freedom to do unexpected things than to treat them
like idiots who need adult supervision. Insulting your customers is not
a sustainable business practice.

Seems to work just fine for MS. But then again, they're not "most
implementors", I suppose. They're insignificant.

In practice, many, perhaps most implementations cannot successfully
allocate anywhere near (size_t) -1 bytes.
That may very well be true. However, it doesn't really matter, as
malloc() will return the appropriate response for those cases. :-)
And most 32 bit systems have limit at 3GB or 3.5GB.
Actually it's usually 2GB, due to splitting of address space between
the kernel and user space. Some go as high as 3GB with special boot
options. However, there are hacks (outside of malloc) that allow for
what Intel calls "Physical Address Extension" (PAE) to allow systems
with Intel 32-bit processors to see memory above 4GB, sort of like the
old extended/expanded memory hacks in the DOS days. Again,
proprietary, and different APIs to use the memory from what standard C
supports.


--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

Jan 2 '07 #94
CBFalconer wrote:
What this has brought home to me is that calloc should be included
in the nmalloc package, so that the same maximum size criterion
will be applied. I.E:

void *ncalloc(size_t nmemb, size_t size) {
size_t sz;
void *p;

sz = nmemb * size;
if ((sz < nmemb) || (sz < size)) return NULL;
if (p = nmalloc(sz)) memset(p, 0, sz);
return p;
}
Just wanted to say: This will not catch many problems. For example on a
32 bit system, nmemb = 0x10001, size = 0x10001, sz = 0x20001.

Jan 2 '07 #95
christian.bau a écrit :
CBFalconer wrote:
>>What this has brought home to me is that calloc should be included
in the nmalloc package, so that the same maximum size criterion
will be applied. I.E:

void *ncalloc(size_t nmemb, size_t size) {
size_t sz;
void *p;

sz = nmemb * size;
if ((sz < nmemb) || (sz < size)) return NULL;
if (p = nmalloc(sz)) memset(p, 0, sz);
return p;
}


Just wanted to say: This will not catch many problems. For example on a
32 bit system, nmemb = 0x10001, size = 0x10001, sz = 0x20001.
lcc-win32 uses this:

void *calloc(size_t n,size_t s)
{
long long siz = (long long)n * (long long)s;
void *result;
if (siz>>32)
return 0;
result = malloc((size_t)siz);
if (result)
memset(result,0,(size_t)siz);
return result;
}
sizeof(long long)=8*8
sizeof(size_t)=4*8
Jan 2 '07 #96
Mark McIntyre wrote:
If the argument is unsigned, you can't pass a -ve value to it.
"argument" means the value passed in. In this code:

#include <stdlib.h>
int foo() { malloc(-1); }

the argument to malloc is the value -1 (of type int).

The type "size_t" w.r.t. malloc is known as the "formal parameter type"
(often the word 'formal' is dropped for convenience's sake).

Jan 2 '07 #97
Richard Heathfield wrote:
>
No, you don't get overflow with unsigned types.
Actually you do. However, the behaviour on overflow is well-defined.

I suppose you could quibble about the exact meaning of the word
'overflow', but it is clear what Navia's meaning is and it serves no
purpose to pretend he is saying something other than what he is.

Jan 2 '07 #98
Richard Heathfield wrote:
On any given implementation, either size_t is big enough to store 65521 *
65552 or it isn't. If it is, there is no issue. And if it is not, your
request is meaningless, since you're asking for an object bigger than the
system can provide.
Firstly, systems might exist where you can allocate more memory
than SIZE_MAX.

That aside, wouldn't it be more sensible behaviour for malloc to
return NULL or take some other action when you try request an
object bigger than the system can provide, rather than returning
a smaller object than requested? I think this is Navia's point.

Jan 2 '07 #99
"Old Wolf" <ol*****@inspire.net.nzwrites:
Richard Heathfield wrote:
>>
No, you don't get overflow with unsigned types.

Actually you do. However, the behaviour on overflow is well-defined.
C99 6.2.5p9 makes it pretty clear that the Standard takes Richard's
point of view:

A computation involving unsigned operands can never
overflow, [...]
--
"The fact that there is a holy war doesn't mean that one of the sides
doesn't suck - usually both do..."
--Alexander Viro
Jan 2 '07 #100

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: Adam Warner | last post by:
Hi all! When dealing with dynamically adjusted objects are you ever concerned that you'll double the requested size of the object and overflow size_t so that the requested size e.g. becomes...
34
by: Alawna | last post by:
Hi, i was reading a chapter about c pointers in "c++builder complete reference" and it is said there that malloc returns a pointer to the start of the memory allocated but i see the prototype of...
40
by: Confused User | last post by:
I am curious what the origins of size_t are. I see that it is usually typedef'd to be the native integer size of a particular machine. I also see that routines like strncpy(char *t, const char *s,...
18
by: rayw | last post by:
I used to believe that size_t was something to do with integral types, and the std. Something along the lines of .. a char is 8 bits, a int >= a char a long >= int
12
by: Alex Vinokur | last post by:
Why was the size_t type defined in compilers in addition to unsigned int/long? When/why should one use size_t? Alex Vinokur email: alex DOT vinokur AT gmail DOT com...
20
by: ramasubramanian.rahul | last post by:
hi folks i have a peculiar problem. i have to allocate more than size_t consequtive bytes on a system . after i do a malloc .. i am unable to do a realloc because it takes size_t as a new size...
13
by: sam_cit | last post by:
Hi Everyone, I was looking at the function prototype of malloc() function in stdlib.h and i found that to be, void *malloc(size_t size); so what is size_t is it a pre-defined typedef to...
73
by: Yevgen Muntyan | last post by:
Hey, I was reading C99 Rationale, and it has the following two QUIET CHANGE paragraphs: 6.5.3.4: "With the introduction of the long long and extended integer types, the sizeof operator may...
409
by: jacob navia | last post by:
I am trying to compile as much code in 64 bit mode as possible to test the 64 bit version of lcc-win. The problem appears now that size_t is now 64 bits. Fine. It has to be since there are...
21
by: pereges | last post by:
For eg : struct mesh { size_t nvert; /* number of vertices */ size_t ntri; /* number of triangles */ ..... }; The reason I want to use size_t is because I've read that it is
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.