Request

[Spiros Bousbouras]

jacob navia wrote:

No, this is impossible in 32 bit size_t systems!!!

Why? The calloc() call has two parameters. There is no reason
that the total allocation cannot exceed the value of a size_t.

Yes there is. Fragment follows:

#define N 65600
#define M 65530

long n, m;
char *p;

if (p = calloc(N, M)
for (n = N; n, n--)
for (m = M; m, m--)
if (p[n * m]) puts("BUG")
puts("OK");

if N*M exceed (size_t) -1, I would submit that the program probably
already exhibits undefined behavior.

Why would that be ?

 

[Spiros Bousbouras]

Spiros Bousbouras said:



"Fewer", my dear chap - "fewer".

What's wrong with "less" ?

 

[Ian Collins]

What's wrong with "less" ?

"fewer" is used with plural nouns (fewer boxes, fewer possibilities),
"less" refers to an amount (less productive, less motivation).

 

[christian.bau]

Relying on undocumented (at best) behavior seems a bit strange to me.
I guess that {for instance} passing two (size_t)-1 values into calloc()
will result in undefined behavior. I guess that calloc() could
conceivably be clever enough to catch it, but I am very sure that it
would not be portable.

C99 Final Draft says: "The calloc function allocates space for an array
of nmemb objects, each of whose size is size.The space is initialized
to all bits zero. " and later "The calloc function returns either a
null pointer or a pointer to the allocated space."

There is no mention there of any problems in the calculation of nmemb *
size. calloc should either allocate space for nmemb objects and return
a pointer to those objects, or return a null pointer. That
specification is quite clear, and I wouldn't accept any excuses if it
is not followed. If I pass for example nmemb = 0x10001, and size =
0x10001, and in the C implementation that I use 0x10001 * 0x10001 ==
0x20001 (which is quite common), then it should be obvious that
allocating 0x20001 bytes will not give enough space for 0x10001 objects
of 0x10001 bytes, and a calloc implementation doing this would be just
plain broken.

The spec says "nmemb objects, each of whose size is size", not "nmemb *
size bytes".

That said, I wouldn't be surprised by the occasional broken C library
implementation.

 

[christian.bau]

There's no *absolute* reason why calloc() can't allocate more than
SIZE_MAX bytes. n and m could be of some type bigger than size_t.
(Array indexing and pointer arithmetic aren't defined in terms of
size_t.)

However, each byte of the allocated object must have a distinct
address, so (ignoring padding bits) char* would have to be bigger than
size_t. I believe this would be legal but silly.

Implementations where sizeof (char *) == 4, and sizeof (size_t) == 2,
have been quite common in the past. On an 80386 processor, an
implementation with char* = 48 bits and size_t = 32 bits wouldn't have
been completely unreasonable (I have never seen one myself).

 

[Mark McIntyre]

I'll take a guess: your point is that calloc should check
whether the multiplication (if that's what it does) yields
a value so big that the system cannot possibly have that
much memory.

My issue with this idea is that there /is/ no such value. I have a
machine in the office with 128GB memory. I have on on order with 1TB
memory. The only possible way malloc() could check the reqested size
was too large would be to use a system-specific call to ask the OS how
much was free, and compare that to the original request. Any sort of
check based on just looking at the request would be incorrect. And
yes, this machine is capable of running 32-bit apps, even Windows apps
for that matter.

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Mark McIntyre]

Spiros Bousbouras a écrit :
My objective is to

1) make a list of all the buggy systems

All buggy systems, in all respects, or just those which have a
specific bug? If the latter, please explain carefully what this bug
is.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Mark McIntyre]

So the central question is:

If some code contains a call of the form calloc(n,m)
where n*m > 2**( sizeof(void*) * CHAR_BIT) then is it
the obligation of the calloc implementation to detect
this and return NULL ?

If the answer to the question is yes then you can say
that the implementations which don't do it are buggy.

I disagree. Provided the system can actually allocate the requested
memory, why is it a bug to do so?

write something like calloc(n,m) where n*m >= 2**31
on a 32 bits system , alarm bells would start to ring

absolutely!
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Spiros Bousbouras]

My issue with this idea is that there /is/ no such value. I have a
machine in the office with 128GB memory. I have on on order with 1TB
memory. The only possible way malloc() could check the reqested size
was too large would be to use a system-specific call to ask the OS how
much was free, and compare that to the original request.

Indeed. Do you see anything wrong with such an approach ?

 

[Mark McIntyre]

SQL server surely doesn't use calloc for allocating 32GB of
RAM,

I guess we'd need to ask Microsoft instead of guessing.

This doesn't actually follow. I can envisage a segmented architecture
which solved this problem.

sizeof returns a size_t. If an object larger than 4GB
could exist then size_t can't be 32 bits.

This doesn't follow either. Just because your tape measure stops at 5
metres, doesn't mean things longer than this can't exist. It does
however mean that a Standard C app cannot measure them accurately.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Richard Tobin]

You wouldn't be able to copy large objects with memcpy(), but that
doesn't prove that it's not legal.


Yes, but no-one suggests that that conforms to the C standard.

Is it similar? On systems that provide far/near pointers, isn't
size_t big enough to cover all possible objects? (I don't know; I've
never used such a system.)[/QUOTE]

Good point, I don't know either.

-- Richard

 

[jacob navia]

christian.bau a écrit :

user923005 wrote:




C99 Final Draft says: "The calloc function allocates space for an array
of nmemb objects, each of whose size is size.The space is initialized
to all bits zero. " and later "The calloc function returns either a
null pointer or a pointer to the allocated space."

There is no mention there of any problems in the calculation of nmemb *
size. calloc should either allocate space for nmemb objects and return
a pointer to those objects, or return a null pointer. That
specification is quite clear, and I wouldn't accept any excuses if it
is not followed. If I pass for example nmemb = 0x10001, and size =
0x10001, and in the C implementation that I use 0x10001 * 0x10001 ==
0x20001 (which is quite common), then it should be obvious that
allocating 0x20001 bytes will not give enough space for 0x10001 objects
of 0x10001 bytes, and a calloc implementation doing this would be just
plain broken.

The spec says "nmemb objects, each of whose size is size", not "nmemb *
size bytes".

That said, I wouldn't be surprised by the occasional broken C library
implementation.

This is my whole point!

And if you care to see the list, there are implementations like that

 

[Richard Tobin]

[/QUOTE]

This doesn't actually follow. I can envisage a segmented architecture
which solved this problem.

A 32-bit pointer can only distinguish 2^32 different values. A
pointer that can point to all the bytes in an object bigger than 2^32
bytes[1] must therefore have more than 32 bits. In a segmented
architecture that allowed objects spanning segments, the segment would
have to be encoded as part of the C pointer, and the pointer would
still have to be bigger than 32 bits.

[1] 2^32-1 if you want to be able to address the byte past the end.

-- Richard

 

[Mark McIntyre]

Indeed. Do you see anything wrong with such an approach ?

No, and indeed thats what I'd expect calloc to do - check if it could
allocate the requested memory, and return NULL if not. This is after
all what its /required/ to do. How it does it is of course
implementation specific.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Cesar Rabak]

Mark McIntyre escreveu:

My issue with this idea is that there /is/ no such value. I have a
machine in the office with 128GB memory. I have on on order with 1TB
memory. The only possible way malloc() could check the reqested size
was too large would be to use a system-specific call to ask the OS how
much was free, and compare that to the original request.

I cannot see this scheme to see daylight: in order to do this, the
application would need to lock all other apps requests to memory to be
sure the reduction is due its request and not somone's (sum of) request.

 

[Spiros Bousbouras]

I disagree. Provided the system can actually allocate the requested
memory, why is it a bug to do so?

When I wrote "the obligation" I meant according to
the standard. By definition if an implementation does
not do what the standard says it should , then it's
buggy.

If your point was that you see no reason for the standard
to make such a requirement then the reply to that has
been covered more or less already: if a void* does not
have enough bits to be able to refer to any byte in the
allocated memory then the standard is violated.

I feel pretty sure now that an implementation of calloc
should be able to detect this and return NULL.

 

[CBFalconer]

"fewer" is used with plural nouns (fewer boxes, fewer
possibilities), "less" refers to an amount (less productive,
less motivation).

Besides which, it just grates on an educated English speaker.

 

[CBFalconer]

user923005 wrote:
jacob navia wrote:

No, this is impossible in 32 bit size_t systems!!!

Why? The calloc() call has two parameters. There is no reason
that the total allocation cannot exceed the value of a size_t.

Yes there is. Fragment follows:

#define N 65600
#define M 65530

long n, m;
char *p;

if (p = calloc(N, M)
for (n = N; n, n--)
for (m = M; m, m--)
if (p[n * m]) puts("BUG")
puts("OK");

if N*M exceed (size_t) -1, I would submit that the program
probably already exhibits undefined behavior.

Why would that be ?

He's right. The longs should have been unsigned longs.

 

[jacob navia]

Mark McIntyre a écrit :

I guess we'd need to ask Microsoft instead of guessing.




This doesn't actually follow. I can envisage a segmented architecture
which solved this problem.

Excuse me but then the pointer is bigger than 32 bits!!!

 

[Joe Wright]

"fewer" is used with plural nouns (fewer boxes, fewer possibilities),
"less" refers to an amount (less productive, less motivation).

Yes. Fewer ice cubes, less ice, etc.