Request

[Spiros Bousbouras]

Spiros Bousbouras a écrit :

where sizeof(void *) == sizeof(size_t) == 4 and CHAR_BIT is 8

Since calloc returns pointer to void I can see why
sizeof(void *) is relevant but I still don't see the
connection between sizeof(size_t) and what calloc
returns or allocates.

 

[jacob navia]

user923005 a écrit :

That is either 8 GB user space or 32 GB, not 3 GB. I suggest you read
again -- this time with comprehension enabled... Here is a quote from
that page that you may find helpful:
"SQL Server 2000 Enterprise Edition introduces support for the use of
Microsoft Windows 2000 Address Windowing Extensions (AWE) to address
approximately 8 GB of memory for instances that run on Microsoft
Windows 2000 Advanced Server, and approximately 32 GB for instances
that run on Microsoft Windows 2000 Datacenter."

P.S.
These operating systems are 32 bits.

So what?

I do not talk about SQL server!

I am talking about calloc, quite a different beast.

Maybe SQL server can allocate a lot of memory but
this is not relevant to calloc I am sure.

There are lots of ways to do it.

No. If you mean using segmented 32:48 bit pointers they
are no longer 32 bit!

I mentioned one above that uses 32 bit addressing lines and yet can
address 32 GB or RAM. The way it does it is with memory models at the
low level. Just like back in the bad old days when MS-DOS programmers
had to model with large, medium or small memory models because of 16
bit addressing, in a similar way you can use 32 bit segments and
offsets to address (potentially) 64 GB of RAM or any other scheme you
like.

But those aren't 32 bit pointers but 48 bit pointers.

Your test has no merit that I can imagine. OK
Systems that will allocate 2^64 pages of ram could return a failure
result if the user space is less than 4GB. So what have we learned
from your code? Nothing.

OK

Thanks for your input

 

[Richard Tobin]

BTW, there are definitely 32 bit systems that will allocate memory in
excess of 32 bits. For example:

There are many 32-bit systems that allow more than 2^32 bytes of
memory to be used, but none that I know of that allow a block that big
to be accessed through calls to C standard allocation functions.

http://support.microsoft.com/kb/274750

And as far as I can see, this is not a counter-example.

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

Obviously if that were the case, pointers would have to be larger than
32 bits. Even if Jacob is not precise, he obviously means systems
with 32-bit pointers. Constantly attacking for imprecision, when he's
trying to make a serious point about faulty implementations, seems
pointless.

-- Richard

 

[jacob navia]

Richard Tobin a écrit :

There are many 32-bit systems that allow more than 2^32 bytes of
memory to be used, but none that I know of that allow a block that big
to be accessed through calls to C standard allocation functions.




And as far as I can see, this is not a counter-example.

SQL server surely doesn't use calloc for allocating 32GB of
RAM, since it needs 48 bit pointers (16:32 pointers with
a segmented architecture like in the msdos days of 16:16)

Obviously if that were the case, pointers would have to be larger than
32 bits. Even if Jacob is not precise, he obviously means systems
with 32-bit pointers. Constantly attacking for imprecision, when he's
trying to make a serious point about faulty implementations, seems
pointless.

Thanks. this is precisely what I meant.

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

 

[Spiros Bousbouras]

Spiros Bousbouras a écrit :

if size_t is 32 bits, it would be highly surprising that
an allocator returns an object of size 33 bits at least.

You are just saying here that such a system *could* exist.
This doesn't make it any more real.

OK. In those hypothetical systems my test would fail.

But how do you know that the systems that you tried
are not one of those "hypothetical" systems ?

because if an object of size > 4GB could exist, sizeof
(that returns a size_t) would not work.

You could not declare an array which has size > 4GB
but it doesn't necessarily impose restrictions on what
calloc can return. But I agree it would be surprising.

You can't be bothered to be honest?

I hope you mean

To be honest, I can't be bothered...

I meant "I can't be bothered , to be honest , ..."
;-)

BUG!!!!


Excuse me but what calloc does is not measured. I just
test the result. If it is the system's fault or whatever
this is not relevant.

This answers my second point but not my first , that your
test doesn't tell you for sure how much memory has been
allocated.

 

[Spiros Bousbouras]

Obviously if that were the case, pointers would have to be larger than
32 bits. Even if Jacob is not precise, he obviously means systems
with 32-bit pointers. Constantly attacking for imprecision, when he's
trying to make a serious point about faulty implementations, seems
pointless.

Well it wasn't obvious to me from his first post. Even
if some people here were out to get him, so to speak, he
could still try to offer them less possibilities by being
precise and clear.

 

[Richard Tobin]

Maybe people with other compilers/implementations
would compile this program and send the results?

To my surprise, it has the bug on MacOS X Tiger with gcc 4.0.1 (x86)
and 4.0.0 (ppc). It also has the bug on Dragonfly 1.2 with gcc 2.95,
but that's a rather out-of-date system. It behaves correctly on
FreeBSD 6.1 x86 with gcc 3.4.4. I have a vague recollection of seeing
discussions about fixing this very problem in *BSD within the last
year or so.

In all cases I think the version of gcc is irrelevant; rather it is
the version of the C library that matter and the OS version determines
that. (The situation is likely to be more complicated for Linux,
where I believe people mix and match kernel and glibc versions.) All
these systems have sizeof(char *) == 4, sizeof(size_t) == 4, and
CHAR_BIT == 8.

-- Richard

 

[Richard Tobin]

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

To be pedantic, that doesn't quite follow. You can't apply sizeof to
the block returned by calloc(). I'm not sure whether you can legally
have a system in which calloc() can return an object with more bytes
than size_t can count.

-- Richard

 

[Spiros Bousbouras]

P.S.
I forgot to spell out clearly the objective of this tests.

My objective is to

1) make a list of all the buggy systems that
is here in clc and everybody can see.

2) Make people aware of this bug in their implementations.
(if any)

Ok , now we're getting somewhere.

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.

From the practical point of view , if I ever needed to

write something like calloc(n,m) where n*m >= 2**31
on a 32 bits system , alarm bells would start to ring
in my mind and I would wonder if it would work. I
would probably write some small test programme to
see if the allocation would succeed. I'm far from infallible
but my view is that a competent C programmer should
be alert to such issues and not rely on protection from
the calloc implementation *even* if the standard demands
that calloc detects this sort of thing. That's because this
is the kind of thing that an implementor can get wrong.
So I would write a test programme which not only tests
that the allocation succeeded but also assign some random
values to the allocated memory and make sure that everything
went ok.

 

[Keith Thompson]

But this is a well known tactic.

Since I present the code, I do the effort of making all those
measurements, it is so easy to just sit by and say

"A system with 32 bit size_t could allocate more than 4GB
memory. A system like that COULD exist."

So WHAT?

Can you please tell me where that system is????

If not, just do not participate. Thanks for your
correction. A system where this test gives a false
positive COULD exist. It is conceivable.

So you acknowledge that a false positive could exist, but when someone
points it out you ask him not to participate in the discussion.

Try being just a little bit less arrogant.

 

[user923005]

Well it wasn't obvious to me from his first post. Even
if some people here were out to get him, so to speak, he
could still try to offer them less possibilities by being
precise and clear.

His code does not demonstrate anything useful.
For instance, it does not show how big a size_t can be or how large of
an allocation is possible or anything of the sort.

Imagine the following:
void *p =calloc(128000, 128000);

Suppose that under the cover, the allocation created an array of 128000
void pointers.
Then, it allocated 128000 separate 128000 byte objects and pointed
those pointers to the objects.
Then it memset each of the 128000 distinct 128000 byte objects with
zero.
We do not need greater than 4GB to cover the stride of the pointer
list.
We do not need greater than 4 GB for any individual object.
Would that implementation be conforming?

We might also use a hash map to associate pointers and allocated ram.

We might allocate in blocksizes of more than one byte. We could use
(for instance) 16 byte pages and still address 4GB*16 bytes with an
unsigned 32 bit integer.

We have lots of 64 bit computers here where I work. I can calloc()
more than 4 GB as su, but if I log on as some other user, I cannot
allocate more than (e.g.) 100 MB. What would his program tell you?

I don't think it shows what he thinks it shows and if it did the way he
thinks it should it still woudn't.

IMO-YMMV.

 

[David T. Ashley]

As a consequence of a heavy discussion in another thread,
I wrote this program:
#include <stdlib.h>
int main(void)
{
char *p=calloc(65521,65552);
if (p)
printf("BUG!!!!\n");
}

My system (Red Hat Enterprise Linux 4.X with all errata applied) reports no
bug. The details are below.

Please note that I have subtly modified your test program by adding an
"else" clause. I don't think you'll object.

It isn't immediately clear to me why the call has to fail. 2^16 * 2^16 is
2^32 (4 gigabytes). My system has more virtual memory than that.

Dave.
----------

[nouser@pamc ~]$ cat test2.c
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
char *p=calloc(65521,65552);
if (p)
printf("BUG!!!!\n");
else
printf("NO BUG!!!!\n");
}
[nouser@pamc ~]$ gcc test2.c
[nouser@pamc ~]$ ./a.out
NO BUG!!!!
[nouser@pamc ~]$ rpm -q -a|grep gcc
gcc-c++-3.4.6-3
gcc-objc-3.4.6-3
gcc-3.4.6-3
gcc-java-3.4.6-3
compat-gcc-32-3.2.3-47.3
libgcc-3.4.6-3
gcc-gnat-3.4.6-3
compat-libgcc-296-2.96-132.7.2
gcc-g77-3.4.6-3
[nouser@pamc ~]$

 

[Keith Thompson]

Ok , now we're getting somewhere.

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 won't try to speak for jacob, but there is a valid point that's
similar to what he's talking about.

I'll use the same notation I introduced here recently: an expression
enclosed in "<<" and ">>" is intended to be interpreted as if all
operations were performed over the full infinite set of integers, with
no overflow or wraparound.

If some code contains a call of the form calloc(n, m), then the system
should either successfully allocate <<n*m>> bytes or return a null
pointer.

If <<n*m>> exceeds SIZE_MAX, and the system is actually able to
allocate that many bytes, that's ok.

There is a bug that some systems seem to have, where calloc()
internally multiplies its two parameters yielding a result of type
size_t, and ignores the possibility that the result could wrap around.
On such systems, for certain values of n and m, a call calloc(n, m)
might successfully allocate <<(n * m) % SIZE_MAX>> bytes, which is
less than <<n * m>>.

jacob's test program (in either version) does not detect this bug with
100% reliability, but if it reports "BUG!!!!" on a given system, it's
probably a good idea to investigate further.

There's a related potential bug, where something like
p = malloc(COUNT * sizeof *p);
can successfully allocate fewer bytes than intended, but in this case
the bug is in the user code; there's not really anything the malloc()
implementation can do about it.

 

[David T. Ashley]

It isn't immediately clear to me why the call has to fail. 2^16 * 2^16 is
2^32 (4 gigabytes). My system has more virtual memory than that.

Well, just out of curiousity, I tried it out to see what the largest
approximate value is. Results below.

54135^2 is going to be on the order of 2.5G. That is a pretty fair hunk of
memory.

---------

[nouser@pamc ~]$ cat test3.c
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
char *p;
int i;

for (i=65535; i>0; i--)
{
if (p = calloc(i,i))
{
printf("%d is apparently the largest integer that will succeed.\n",
i);
break;
}
}
}
[nouser@pamc ~]$ gcc test3.c
[nouser@pamc ~]$ ./a.out
54135 is apparently the largest integer that will succeed.
[nouser@pamc ~]$

 

[Keith Thompson]

To be pedantic, that doesn't quite follow. You can't apply sizeof to
the block returned by calloc().
Agreed.

I'm not sure whether you can legally
have a system in which calloc() can return an object with more bytes
than size_t can count.

I think you can, but such a system would have to have pointers bigger
than size_t. calloc() allocates an object; each byte of that object
must have a unique address of type char* or void*. Making size_t
smaller than void* is probably legal, but I can't think of a good
reason to do it (perhaps the DS9K does this).

 

[Keith Thompson]

Imagine the following:
void *p =calloc(128000, 128000);

Suppose that under the cover, the allocation created an array of 128000
void pointers.
Then, it allocated 128000 separate 128000 byte objects and pointed
those pointers to the objects.
Then it memset each of the 128000 distinct 128000 byte objects with
zero.
We do not need greater than 4GB to cover the stride of the pointer
list.
We do not need greater than 4 GB for any individual object.
Would that implementation be conforming?

I don't believe so. calloc() must allocate a single contiguous object
(which happens to be an array object). Each byte of this object (or
equivalently, each byte of each element of the array) must have a
unique address.

 

[Nelu]

I think you can, but such a system would have to have pointers bigger
than size_t. calloc() allocates an object; each byte of that object
must have a unique address of type char* or void*. Making size_t
smaller than void* is probably legal, but I can't think of a good
reason to do it (perhaps the DS9K does this).

Isn't this similar with the far/near pointers from Turbo C?

 

[Richard Heathfield]

Spiros Bousbouras said:

Even
if some people here were out to get him, so to speak, he
could still try to offer them less possibilities by being
precise and clear.

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

 

[Keith Thompson]

My system (Red Hat Enterprise Linux 4.X with all errata applied) reports no
bug. The details are below.

Please note that I have subtly modified your test program by adding an
"else" clause. I don't think you'll object.

It isn't immediately clear to me why the call has to fail. 2^16 * 2^16 is
2^32 (4 gigabytes). My system has more virtual memory than that.

Really? Is it a 64-bit system? jacob's test program is intended to
apply only to systems with 32-bit size_t.

If your system has more than 4 gigabytes of virtual memory, but only a
32-bit size_t, that might cause some problems. (Or it might not, if
no single object can be bigger than 4 gigabytes.)

 

[user923005]

Seems to me a simpler test might be:

size_t count; /* for calloc() count, eventually */
size_t size; /* for calloc() object size, eventually */
/* the square root of the biggest size_t is a hint that we may be over
the edge */
const size_t sqrtstm = (size_t)sqrt(double(size_t(-1)));

....
if (count > sqrtstm || size > sqrtstm)
{
double dcount = count;
double dsize = size;
double dproduct = dcount * dsize;
if (dproduct > ((size_t)-1))
{
raise_bloody_heck();
}
}

or something of that ilk.
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.