malloc and maximum size

[V.Subramanian, India]

This question is only for understanding purpose.

I am using RedHat Linux kenel 2.6.9 on Intel Pentium D dual core
processor.

The malloc function takes size_t type argument. I am using gcc 3.4.3
implementation. Under this implementation, in stdint.h, SIZE_MAX is
defined as follows:
# define SIZE_MAX (4294967295U)

SIZE_MAX, defined in stdint.h, is the largest value that can be
represented in type size_t. However when I pass SIZE_MAX as the
argument to malloc, it is unable to allocate SIZE_MAX bytes of memory.
In fact, malloc allocates much much less memory.

Here is the complete program max_size_to_malloc.c

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

int main()
{
size_t count = 0;

do
{
const size_t size = SIZE_MAX - count;

char* p = malloc(size);

if (p)
{
fprintf(stderr,
"%u - %u : ",
SIZE_MAX,
count);

fprintf(stderr,
"Allocated %u bytes of memory\n",
size);
free(p);
p = NULL;
return EXIT_SUCCESS;
}

} while (++count);
}

This program compiles fine with gcc 3.4.3 as
gcc -std=c99 -pedantic -Wall -Wextra max_size_to_malloc.c

and produces the following output(after quite some time):
4294967295 - 1365266451 : Allocated 2929700844 bytes of memory

What is the reason for allocating this much less memory while the
parameter type of malloc is size_t ?

Normally what factor drives the maximum size of a single chunk of
memory allocated by malloc ?

Please explain.

Thanks
V.Subramanian

 

[James Kuyper]

This question is only for understanding purpose.

I am using RedHat Linux kenel 2.6.9 on Intel Pentium D dual core
processor.

The malloc function takes size_t type argument. I am using gcc 3.4.3
implementation. Under this implementation, in stdint.h, SIZE_MAX is
defined as follows:
# define SIZE_MAX (4294967295U)

SIZE_MAX, defined in stdint.h, is the largest value that can be
represented in type size_t. However when I pass SIZE_MAX as the
argument to malloc, it is unable to allocate SIZE_MAX bytes of memory.
In fact, malloc allocates much much less memory.

This is entirely normal. The implementation chose size_t to be big
enough for all of the purposes it needs to be useful for - primarily the
type of sizeof expressions, and for dynamic memory allocations, but
there's many other ways the standard library uses it.

The type chosen for size_t must be an unsigned type big enough to hold
the largest number that could reasonably be used for any of those
purposes; but keep in mind that most platforms nowadays provide hardware
support only for integers of 8, 16, 32, or 64 bytes (and not necessarily
all of those on any given machine); types of other sizes could be
implemented by software emulation, but would be very inefficient. The
maximum amount of memory allocatable by malloc() could be as small as
65536 bytes, and still be large enough to require size_t to be a 32-bit
type.
Moral: don't assume that you can allocate as much as SIZE_MAX bytes; the
actual maximum could be a LOT less.

Here is the complete program max_size_to_malloc.c

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

int main()
{
size_t count = 0;

do
{
const size_t size = SIZE_MAX - count;

char* p = malloc(size);

if (p)
{
fprintf(stderr,
"%u - %u : ",
SIZE_MAX,
count);

fprintf(stderr,
"Allocated %u bytes of memory\n",
size);
free(p);
p = NULL;
return EXIT_SUCCESS;
}

} while (++count);

Keeping separate track of count and size serves little purpose. I'd
recommend dropping count, dropping the first fprintf() call, and
replacing the do-while() loop with

for(size_t size = SIZE_MAX; size; size--)

Also, setting p=NULL is pretty pointless when the lifetime of 'p' will
end almost immediately after you do so. For precisely that reason, a
decently optimizing compiler will simply ignore that statement, but it's
better to simply not write it in the first place. In fact, I normally
try to arrange that pointer variables are free()d immediately before
their lifetime ends, so I won't have to worry about them being misused.

}

This program compiles fine with gcc 3.4.3 as
gcc -std=c99 -pedantic -Wall -Wextra max_size_to_malloc.c

and produces the following output(after quite some time):
4294967295 - 1365266451 : Allocated 2929700844 bytes of memory

What is the reason for allocating this much less memory while the
parameter type of malloc is size_t ?

Normally what factor drives the maximum size of a single chunk of
memory allocated by malloc ?

Memory fragmentation can make the maximum size of a single allocatable
chunk of memory be MUCH smaller than the total amount of memory
available for allocation.

 

[Nobody]

What is the reason for allocating this much less memory while the
parameter type of malloc is size_t ?

Normally what factor drives the maximum size of a single chunk of
memory allocated by malloc ?

Availability.

In order to allocate a chunk of N bytes, there must be an unused N-byte
chunk of contiguous address space available, and sufficient storage
(physical RAM or swap) available to "back" it (i.e. to remember whatever
is stored in it).

 

[James Kuyper]

On 10/14/2011 11:10 AM, Lowell Gilbert wrote:
....

Does SIZE_MAX have to be the largest value representable in a size_t?
The standard just says that it's the "maximum value" for the type,

What distinction do you see between "largest value representable" if a
type and "maximum value" for a type? The phrases seem synonymous to me.

 

[Ike Naar]

Just because a function takes an argument of a particular type does
not mean that all possible values of that type will be valid. For
example, providing memcpy() with a third argument of 0 invokes
undefined behavior.

7.21.1 seems to explicitly allow memcpy's third argument to be zero:

7.21.1 String function conventions

2 Where an argument declared as size_t n specifies the length of
the array for a function, n can have the value zero on a call
to that function.

Where is it stated the behaviour is undefined?

 

[Jens Thoms Toerring]

This question is only for understanding purpose.

I am using RedHat Linux kenel 2.6.9 on Intel Pentium D dual core
processor.

The malloc function takes size_t type argument. I am using gcc 3.4.3
implementation. Under this implementation, in stdint.h, SIZE_MAX is
defined as follows:
# define SIZE_MAX (4294967295U)

SIZE_MAX, defined in stdint.h, is the largest value that can be
represented in type size_t. However when I pass SIZE_MAX as the
argument to malloc, it is unable to allocate SIZE_MAX bytes of memory.
In fact, malloc allocates much much less memory.

As other's already have pointed out the simple reason for
the result you obtained.

Thus I just want to comment on the lines like

fprintf(stderr,
"%u - %u : ",
SIZE_MAX,
count);

You're using the '%u' format specifier for a size_t type.
'%u' is meant for unsigned ints. You might get away with
this on your machine when 'size_t' is actually typedef'ed
(or '#define'-ed) to 'unsigned int' but that's not some-
thing you should get used to rely on. E.g. on my machine
SIZE_MAX is 18446744073709551615 and that's much too large
for an unsigned int (UINT_MAX is 4294967295 here and I thus
get compiler warnings). You should, if available, always
use the '%zu' format specifier (introduced in C99) or, if
you are not sure it's available, cast size_t values to the
largest available unsigned int type (at least 'unsigned
long int') and use the appropriate format specifier to be
reasonably sure that what you get printed out is correct.

Regards, Jens

 

[Stephen Sprunk]

SIZE_MAX, defined in stdint.h, is the largest value that can be
represented in type size_t. However when I pass SIZE_MAX as the
argument to malloc, it is unable to allocate SIZE_MAX bytes of memory.

size_t must be capable of representing the size of the largest object
the implementation can create.

That does _not_ mean the implementation must be capable of creating an
object the size of the largest value a size_t can represent.

Those are two very different things.

In fact, malloc allocates much much less memory.

Here is the complete program max_size_to_malloc.c
...
This program compiles fine with gcc 3.4.3 as
gcc -std=c99 -pedantic -Wall -Wextra max_size_to_malloc.c

and produces the following output(after quite some time):
4294967295 - 1365266451 : Allocated 2929700844 bytes of memory

What is the reason for allocating this much less memory while the
parameter type of malloc is size_t ?

Maybe your system didn't have any contiguous blocks of memory larger
than 2,929,700,844 bytes available at the time of your test.

Normally what factor drives the maximum size of a single chunk of
memory allocated by malloc ?

There are other things in memory (eg. your program, the stack, any
objects in the heap, OS services, libraries your program is linked to,
etc.), so at least some of it will not be available for you to allocate
for your own purposes; how much will vary.

Available memory is often fragmented (because those things above are
located in different places in memory), so the largest object you can
allocate will be limited to the largest _contiguous_ block.

Also, there may be administrative policy limiting the amount of memory
any program can allocate to below what is technically possible.

S

 

[Keith Thompson]

On 14-Oct-11 08:31, V.Subramanian, India wrote: [...]

Here is the complete program max_size_to_malloc.c
...
This program compiles fine with gcc 3.4.3 as
gcc -std=c99 -pedantic -Wall -Wextra max_size_to_malloc.c

and produces the following output(after quite some time):
4294967295 - 1365266451 : Allocated 2929700844 bytes of memory

What is the reason for allocating this much less memory while the
parameter type of malloc is size_t ?

Maybe your system didn't have any contiguous blocks of memory larger
than 2,929,700,844 bytes available at the time of your test.

And quite possibly it didn't have that much. On Linux systems,
a malloc() call can appear to succeed, but not actually allocate
memory, just address space. Things can go bad later when you try
to access the apparently allocated memory.

 

[James Kuyper]

Certainly there's no difference in *most* cases.

For size_t, the type is just defined as the output type for sizeof,
which is defined in turn as yielding the size of its operand. So I can
see an argument that the "maximum value" of a size_t could be viewed as
the largest value that sizeof could possibly yield on the particular
implementation.

Well, the maximum value returnable by sizeof has to be the same as the
maximum value representable by size_t:

sizeof(char[(size_t)-1]) == (size_t)(-1)

It has been argued that, since it's not possible for the standard's
specifications for the value and type of sizeof(char[SIZE_MAX][2]) to be
simultaneously satisfied, an implementation is free, among other
possibilities, to treat it as having a value that is larger than
SIZE_MAX. Personally, I think such code should be rejected, but it's not
clear that the standard requires, or even allows, it to be rejected.

However, there's no possible basis that I'm aware of for rejecting
sizeof(char[(size_t)-1]).

... Of course, that can be (and, indeed, often is) smaller
than a size_t could represent.

With respect to your claim "often is" - can you cite any implementation
where the equality expression given above is NOT true?

 

[Richard Damon]

Certainly there's no difference in *most* cases.

For size_t, the type is just defined as the output type for sizeof,
which is defined in turn as yielding the size of its operand. So I can
see an argument that the "maximum value" of a size_t could be viewed as
the largest value that sizeof could possibly yield on the particular
implementation. Of course, that can be (and, indeed, often is) smaller
than a size_t could represent.

It is quite possible for an architecture to have a smaller value of
SIZE_MAX than the maximum value that could be placed inside of a size_t.

Take a machine that represents addresses as an 8 bit "Segment" and a 24
bit "Offset" which via some mapping registers get mapped into memory. 24
bits is a big enough offset, that the implementation may decide not to
implement "huge" pointers for objects, thus the largest an object could
be would be 2^24 bytes, but size_t may well be a 32 bit integer.

 

[Jens Thoms Toerring]

On 14-Oct-11 08:31, V.Subramanian, India wrote: [...]

Here is the complete program max_size_to_malloc.c
...
This program compiles fine with gcc 3.4.3 as
gcc -std=c99 -pedantic -Wall -Wextra max_size_to_malloc.c

and produces the following output(after quite some time):
4294967295 - 1365266451 : Allocated 2929700844 bytes of memory

What is the reason for allocating this much less memory while the
parameter type of malloc is size_t ?

Maybe your system didn't have any contiguous blocks of memory larger
than 2,929,700,844 bytes available at the time of your test.

And quite possibly it didn't have that much. On Linux systems,
a malloc() call can appear to succeed, but not actually allocate
memory, just address space. Things can go bad later when you try
to access the apparently allocated memory.

Depending on the settings for memory overcommitment...

Regards, Jens

 

[James Kuyper]

On 10/14/2011 11:10 AM, Lowell Gilbert wrote:
...
Does SIZE_MAX have to be the largest value representable in a size_t?
The standard just says that it's the "maximum value" for the type,

What distinction do you see between "largest value representable" if a
type and "maximum value" for a type? The phrases seem synonymous to me.

Certainly there's no difference in *most* cases.

For size_t, the type is just defined as the output type for sizeof,
which is defined in turn as yielding the size of its operand. So I can
see an argument that the "maximum value" of a size_t could be viewed as
the largest value that sizeof could possibly yield on the particular
implementation.

Well, the maximum value returnable by sizeof has to be the same as the
maximum value representable by size_t:

sizeof(char[(size_t)-1]) == (size_t)(-1)

Assuming I understand what you're getting at, you're begging the
question here. [But the expression doesn't make sense to me, so
the assumption may well be wrong.]

I had not intended to beg the question. Per 6.3.1.3p2, (size_t)(-1) is
precisely "the maximum value that can be represented" as a size_t.

char[(size_t)(-1)] is an array type whose size in bytes is (size_t)(-1).
sizeof(char[(size_t)(-1)]) must therefore yield a value which is
(size_t)(-1). Therefore, the largest value that sizeof could possibly
yield must be (size_t)(-1), the same as the maximum representable value.

....

However, there's no possible basis that I'm aware of for rejecting
sizeof(char[(size_t)-1]).

I assume you mean SIZE_MAX rather than (size_t),

No, in don't mean SIZE_MAX, since I was trying to address your claim
that it can be less than maximum representable value. I didn't mean
(size_t), either, which is no more than a parenthesized type - I presume
that was an editing error? I meant (size_t)(-1), which is guaranteed by
the standard to be the maximum representable value.

... in which case I agree.
But that doesn't mean SIZE_MAX has to be the largest value a size_t can
hold, if there are other limits on how big an object can be.

The key point is that sizeof acts on types, not objects. Even when you
write "sizeof expression", and expression is an lvalue referring to an
object, it doesn't look into the expression to determine which object it
refers to; it just looks at the type of the expression. It doesn't care
whether or not there's any actual object of that type. sizeof(int) ==
sizeof *(int*)0, even though the standard prohibits (int*)0 from
pointing at any actual object.

I think you're misreading my claim. There certainly are systems with
architectural limitations on how big an object can be, well short of
what fits in a size_t.

And sizeof(char[(size_t)(-1)]) exceeds none of those limitations,
because it doesn't cause the creation of any object of the specified type.

For example, the machine I'm posting from has 32-bit words, from which
it gets a 4-gigabyte range for its size_t. However, the operating
system reserves some of the address space, so no program can ever have
more than 3 gigabytes. As a result, sizeof can *never* return more than
3 gigabytes.

Not even sizeof(char[3500000000])? For an implementation where
(size_t)(-1) is 4294967295, what gives that implementation permission to
do anything with that expression other than yield a value of
(size_t)3500000000? The implementation is free to issue a diagnostic, of
course, but not to reject the code.

... This prompted me to wonder whether it would be legitimate
for the system's SIZE_MAX to be 3 gigabytes.

Am I making more sense now?

Not yet. You seem to have missed the point I was making, while I think I
understand yours perfectly. Is my point clearer now?

 

[James Kuyper]

On 10/14/2011 04:17 PM, Richard Damon wrote:
....

It is quite possible for an architecture to have a smaller value of
SIZE_MAX than the maximum value that could be placed inside of a size_t.

How does that satisfy the requirement that
"The following object-like macros227) specify the minimum and maximum
limits of integer types corresponding to types defined in other standard
headers." (7.18.3p1)?

If there were a value larger than SIZE_MAX that could be stored in
size_t, then SIZE_MAX would not be the "maximum limit" for that type.

Take a machine that represents addresses as an 8 bit "Segment" and a 24
bit "Offset" which via some mapping registers get mapped into memory. 24
bits is a big enough offset, that the implementation may decide not to
implement "huge" pointers for objects, thus the largest an object could
be would be 2^24 bytes, but size_t may well be a 32 bit integer.

In which case, the limit on size_t is 2^32-1, not 2^24-1.
sizeof(lvalue_referring_to_actual_object) might not be able to exceed
2^24-1, but sizeof(type) could, and so could sizeof(*(type*)0).

If you're talking about an implementation where size_t is a 24-bit
unsigned integer implemented using 24 value bits and 8 padding bits,
then SIZE_MAX could be be 0xFFFFFFFFFFFFF. However, that requires that
emulation of a 24-bit type be performed correctly: (size_t)(-1) has to
be SIZE_MAX, and size_t_expression & 0xFFFF000000000000 must always be 0
for any expression of type size_t. Those 8 padding bits must be
accessible only by type punning with unsigned char, or by expressions
with undefined behavior.

 

[Ike Naar]

char[(size_t)(-1)] is an array type whose size in bytes is (size_t)(-1).
sizeof(char[(size_t)(-1)]) must therefore yield a value which is
(size_t)(-1). Therefore, the largest value that sizeof could possibly
yield must be (size_t)(-1), the same as the maximum representable value.

Then the behaviour of gcc 4.1.3 on NetBSD 5.1.0 comes as a surprise:
apparently it does not consider char[(size_t)(-1)] a valid array type.

$ cat a.c
#include <stddef.h>
size_t f(void)
{
return sizeof(char[(size_t)(-1)]);
}
$ gcc -c -ansi -pedantic a.c
a.c: In function 'f':
a.c:4: error: size of array 'type name' is too large

Interestingly, it compiles without errors if the array is halved,
i.e. when the type is changed to char[(size_t)(-1) / 2] .

 

[James Kuyper]

char[(size_t)(-1)] is an array type whose size in bytes is (size_t)(-1).
sizeof(char[(size_t)(-1)]) must therefore yield a value which is
(size_t)(-1). Therefore, the largest value that sizeof could possibly
yield must be (size_t)(-1), the same as the maximum representable value.

Then the behaviour of gcc 4.1.3 on NetBSD 5.1.0 comes as a surprise:
apparently it does not consider char[(size_t)(-1)] a valid array type.

$ cat a.c
#include <stddef.h>
size_t f(void)
{
return sizeof(char[(size_t)(-1)]);
}
$ gcc -c -ansi -pedantic a.c
a.c: In function 'f':
a.c:4: error: size of array 'type name' is too large

Annoying - but I'm not surprised that there's disagreement about this.
SIZE_MAX seems to be one of the more controversial issues about C, and
it really shouldn't be.

Interestingly, it compiles without errors if the array is halved,
i.e. when the type is changed to char[(size_t)(-1) / 2] .

 

[Keith Thompson]

Not even sizeof(char[3500000000])? For an implementation where
(size_t)(-1) is 4294967295, what gives that implementation permission to
do anything with that expression other than yield a value of
(size_t)3500000000? The implementation is free to issue a diagnostic, of
course, but not to reject the code.

Interesting. For the following program:

#include <stdio.h>
int main(void) {
printf("%zu\n", sizeof (char[(size_t)-1]));
return 0;
}

"gcc -std=c99" rejects it with an error message:

c.c: In function ‘main’:
c.c:3:5: error: size of unnamed array is too large

Change the array size to (size_t)-1/2 and it compiles and prints
"2147483647". Change it to (size_t)-1/2+1 and it rejects it with the
same error message.

Does this make "gcc -std=c99" non-conforming?

 

[Keith Thompson]

On 10/14/2011 04:17 PM, Richard Damon wrote:
...

How does that satisfy the requirement that
"The following object-like macros227) specify the minimum and maximum
limits of integer types corresponding to types defined in other standard
headers." (7.18.3p1)?

If there were a value larger than SIZE_MAX that could be stored in
size_t, then SIZE_MAX would not be the "maximum limit" for that type.

Agreed. SIZE_MAX is the maximum limit of the type, not of the values
that the sizeof operator can yield.

[...]

If you're talking about an implementation where size_t is a 24-bit
unsigned integer implemented using 24 value bits and 8 padding bits,
then SIZE_MAX could be be 0xFFFFFFFFFFFFF.

Do you mean 0xFFFFFF?

 

[Keith Thompson]

Not even sizeof(char[3500000000])? For an implementation where
(size_t)(-1) is 4294967295, what gives that implementation permission to
do anything with that expression other than yield a value of
(size_t)3500000000? The implementation is free to issue a diagnostic, of
course, but not to reject the code.

Okay, I see where you're going with this; the fact that the
implementation can't instantiate the type doesn't keep it from
recognizing that type. What I'm not getting (and I have, indeed,
looked in the standard) is what *requires* the implementation to
accept the "sizeof(char[3500000000])". I'm sure the implementation
*can* accept it, and I suspect that most will, but I haven't found
such a requirement. Your question about what gives it permission is
backwards; the implementation doesn't need permission if it hasn't
been required to do otherwise.

I don't think James is going at it backwards. I will now argue both
sides of this.

What (arguably) requires the implementation to accept
"sizeof(char[3500000000])" is the same thing that requires it to
accept "sizeof(char[10])", namely the sections discussing the sizeof
operator, the char type, integer constants, and array types.

C99 5.2.4.1 discusses translation limits (127 nesting levels of blocks,
63 nesting levels of conditional inclusion, etc.). It requires an
implementation to accept 65535 bytes in an object, but that doesn't
apply to the above expression, since it doesn't refer to an object.

On the other hand, 5.2.4.1 doesn't even say that an implementation
must always accept 65535 bytes in an object. It says:

The implementation shall be able to translate and execute at least
one program that contains at least one instance of every one of the
following limits:

followed by a list of limits. By rejecting "sizeof(char[3500000000])",
gcc isn't violating any requirement in 5.2.4.1; presumably it does
translate and execute that one program (which doesn't include an
instance of "sizeof(char[3500000000])".

Presumably an implementation may legitimately reject a program violating
some limit not listed in 5.2.4.1, such as a trillion-line translation
unit. So I *think* that rejecting any program referring to a type
bigger than 2**31 bytes is permitted. But I'm not 100% certain.

 

[Richard Damon]

What (arguably) requires the implementation to accept
"sizeof(char[3500000000])" is the same thing that requires it to
accept "sizeof(char[10])", namely the sections discussing the sizeof
operator, the char type, integer constants, and array types.

Why should the compiler be forced to allow the definition of a type that
defines an object bigger than is allowed??

Note that all valid object sizes must fit within a size_t, but that
doesn't mean that all values of size_t must be valid object sizes. If
you look at the hardware architecture I posted earlier, on such a
machine an array of chars with more than 2^24 elements could justifiable
be rejected as not a valid object. (I will admit that I goofed and
forgot that SIZE_MAX specified the limit on the *type* size_t and not
the limit of sizeof).

The compiler limits section does establish a lower limit for the size
that the compiler could decide is flat out "too big", but that is much
smaller than is being discussed here.

 

[Keith Thompson]

What (arguably) requires the implementation to accept
"sizeof(char[3500000000])" is the same thing that requires it to
accept "sizeof(char[10])", namely the sections discussing the sizeof
operator, the char type, integer constants, and array types.

Why should the compiler be forced to allow the definition of a type that
defines an object bigger than is allowed??

Why should the compiler be forced to allow *anythihg*?

As I tried to make clear in the part of my article that you snipped,
I'm not at all sure whether rejecting "sizeof(char[3500000000])"
makes a compiler non-conforming or not. I think the strongest
argument is simply that the standard's treatment of translation
limits is incomplete (and it would be impractical to make it
complete).

Note that all valid object sizes must fit within a size_t,

I'm not convinced of that.

Here's my counterargument. "sizeof", like "+", is an operator, If
x and y are of type int, then "x + y" yields a result of type int;
that doesn't imply that int must be big enough to hold the result
of adding any two int values. Similarly, the fact that "sizeof
(some_type)" is of type size_t doesn't imply that size_t must be
big enough to hold the result of "sizeof (some_type)" for all types.

In particular, I can argue that a conforming compiler can permit

typedef char[2 * SIZE_MAX] way_too_big;

while rejecting (or having undefined behavior for) an attempt to
evaluate "sizeof (way_too_big)".

In practice, any *sane* implementation should make its size_t
type big enough to hold the size of any type or object that it
can support, and will reject the above declaration of way_too_big.
But implementations are not required to be sane.

Similarly, a sane implementation will always have calloc(SIZE_MAX,
2) return NULL, but a conforming implementation could actually
allocate the object.

On the other hand, if the standard were amended (or even interpreted)
to say that no object can exceed SIZE_MAX bytes, I wouldn't complain.

[snip]