B
Barry Schwarz
As long as malloc doesn't fail,
calloc(a,b) = memset(malloc(a*b),0,a*b)
As long as malloc doesn't fail,
calloc(a,b) = memset(malloc(a*b),0,a*b)
L
lawrence.jones
Barry Schwarz said:
And a*b doesn't overflow,
B
Barry Schwarz
Unsigned arithmetic cannot overflow.
Given the wording in 7.20.3.1, where the allocated space constitutes a
single array, I have no idea what happens when the arithmetic product
a*b exceeds the value of SIZE_MAX. Under such conditions I believe
calloc should fail and return NULL but the memset expression above is
under no such obligation.
J
James Kuyper
calloc(a,b) must either return a pointer to enough memory to store 'a'
objects, each of size 'b' bytes, or a null pointer. If the mathematical
product of a*b is greater than SIZE_MAX, then (size_t)(a*b) bytes will
not be sufficient to meet that requirement - but the requirement still
holds. Therefore, calloc(a,b) must either return a null pointer, or
allocate sufficient memory by some mechanism other than malloc(a*b).
B
Barry Schwarz
That is not what the standard 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." Note the additional
requirement that the entire allocated space be considered a single
array. size_t must be able to hold the size in bytes of the largest
possible object, including aggregates such as arrays. When a*b is
mathematically larger then SIZE_MAX, a "successful" call to calloc
would violate this requirement. Therefore, calloc should be required
to return NULL in this case, which is what I said in the part you
snipped.
J
Jens Gustedt
Am 16.05.2012 05:38, schrieb Barry Schwarz:
I can't find any text in the standard about size_t that requires
this. The only requirement is that the type must be able to hold the
value of the sizeof operator. This restricts the possible size only
for objects to which that operator applies, in particular it
constrains the possible size of VLA (as a function of the size of the
base type).
But since objects allocated by the "alloc" family of functions are not
subject to the sizeof operator, this restriction doesn't seem to
apply. To me, the only implicit bound for calloc seems to be
(SIZE_MAX + 1)*(SIZE_MAX + 1)-1
Jens
I can't find any text in the standard about size_t that requires
this. The only requirement is that the type must be able to hold the
value of the sizeof operator. This restricts the possible size only
for objects to which that operator applies, in particular it
constrains the possible size of VLA (as a function of the size of the
base type).
But since objects allocated by the "alloc" family of functions are not
subject to the sizeof operator, this restriction doesn't seem to
apply. To me, the only implicit bound for calloc seems to be
(SIZE_MAX + 1)*(SIZE_MAX + 1)-1
Jens
J
James Kuyper
Citation, please?
"sizeof(type)" must yield the size of the specified type, "sizeof
expression" must yield the size of the type of the specified
expression(6.5.3.4p2), and in either case that value must be have the
type size_t (6.5.3.4p5). This does NOT add up to the requirement you state.
Consider an implementation with the following characteristics:
1. It rejects all code that specifies any type with a size greater than
SIZE_MAX, as exceeding that implementation's limits. If it were not
permissible for a conforming implementation to reject such code, every
implementation would be rendered non-conforming by it's inability to
yield the required results for the expression sizeof(char[SIZE_MAX][2]).
2. calloc(a,b) can, at least for some values of a and b, return a
non-null pointer which points at an array of a objects of size b, even
if such an array requires more than SIZE_MAX bytes.
It follows that on such an implementation, it's not possible to write an
expression of the form sizeof(object) that would be required by the
standard to yield the size of the array pointed at by the value returned
by such a call to calloc(). Any such expression would necessarily
require casting that pointer to point at a type with a size larger than
SIZE_MAX, and as such would be rejected by that compiler.
What requirement of the standard would be violated by such an
implementation?
Let me explain that more specifically. If you can declare a pointer p
such that
p = calloc(a,b);
size_t size = sizeof(*p);
would violate the requirements of 6.5.3.4 if calloc() returned a
non-null pointer for a*b>SIZE_MAX, then it would ALSO violate those
requirements if calloc() returned a null pointer. That's because the
value of sizeof(*p) depends only upon the type of 'p', not the value of
p. Therefore, you cannot use 6.5.3.4 to derive a requirement that
calloc() return a null pointer.
B
Barry Schwarz
K&R II, page 135, a stand-alone unindented paragraph approximately 1/3
of the way down the page: "C provides a compile-time unary operator
called sizeof that can be used to compute the size of any object."
J
James Kuyper
K&R II is not authoritative. The C standard is. K&R II often says things
less precisely than the standard. Please cite a corresponding
requirement from the standard. n1570.pdf
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf> is the last
publicly available draft of the current standard, and is authoritative
enough for this discussion.
Also note that the words you cite from K&R II are not, in themselves,
sufficient to support your position. "can be used to compute" doesn't
require that the computation be carried out using size_t. If it were in
fact an authoritative requirement, it would not impose a constraint on
SIZE_MAX; it only indirectly constrains either UINTMAX_MAX or LDBL_MAX,
whichever is larger. For example:
char (*)p[SIZE_MAX] = calloc(2, SIZE_MAX);
long double size = 2.0L*sizeof *p;
In that code, sizeof was indeed used to calculate the size of the object
(unless calloc() failed, in which case there is no object, but the size
calculation is unaffected by that fact).
B
Barry Schwarz
Yes. And it's also been superceded by at least two standards. It
just happens to be the clearest description of what the inventors of
the language intended. And percentage wise, very little has actually
been superceded.
Regardless of how the computation is carried out, the result must fit
in a size_t.
There is no requirement that size_t be the widest possible unsigned
type. Surely SIZE_MAX cannot exceed UINTMAX_MAX. I don't understand
how UINTMAX_MAX enters into this discussion.
While it is not very likely, it is possible for SIZE_MAX to exceed
LDBL_MAX (1E37 bytes is a large object and size_t would need to be in
excess of 120 bits). In that case, the implicit conversion in your
multiplication invokes undefined behavior (6.3.1.4-2). But there are
lots of sound mathematical expressions which cannot be performed in "C
arithmetic" due to these kinds of constraints.
My only assertion was that since the result of calloc(a,b) is to be
treated as a single array, calloc should fail if a*b mathematically
exceeds SIZE_MAX. I didn't address whether SIZE_MAX could be
converted to a real floating type or any other integer type (though it
seems obvious it should be convertible to a uintmax_t).
The wording is unchanged in n1570.
T
Tim Rentsch
Barry Schwarz said:
The Standard does not impose such a requirement, either for regular
objects or for those dynamically allocated. Certainly it is
typically true, and normally implementations enforce it for regular
objects whose size is known at compile time, but neither of those
conditions is necessary for an implementation to be conforming.
J
James Kuyper
[Note: corrected typo in Subject: header]
Citation, please?
Because uintmax_t and long double are the types whose limits determine
what "... sizeof ... can be used to compute ...", not size_t. That's
because the term "compute" is sufficiently vague to allow for a sizeof
expression that is no more than a sub-expression of an enclosing
expression with a result that is of some type other than size_t. The
maximum value that can be represented by such an enclosing expression is
either UINTMAX_MAX or LDBL_MAX, whichever is larger (almost certainly
LDBL_MAX). As long as the size can be correctly computed in one of those
types, with the sizeof operator playing some role somewhere in the
computation, then a hypothetical requirement that "... sizeof ... can be
used to compute the size of any object." would be satisfied.
For a hypothetical future version of the standard where there was, in
fact, a requirement that "... sizeof ... can be used to compute the size
of any object.", the existence of such a requirement would imply that a
conforming implementation of C where calloc(2,SIZE_MAX) returns a
non-null pointer must have either UINTMAX_MAX OR LDBL_MAX >= the size of
the object created by that call. Therefore, you could write:
if(p)
{
#if UINTMAX_MAX/2 >= SIZE_MAX
uintmax_t size = 2LL * sizeof *p;
#else
long double size = 2.0L * sizeof *p;
#endif
// do something with size.
}
....
An assertion for which you've provided no citations from the standard,
nor any arguments based upon such citations. Even the citation you have
provided from K&R II fails to specify any such requirement.
I wasn't talking about converting the size to another type; I was
talking about calculating the size in another type, because SIZE_MAX was
too small to be used for such calculations. Because such calculations
can be performed, a requirement that the computation be possible does
not greatly constrain the value of SIZE_MAX.
That was really intended as a kind of joke. Perhaps I should have
inserted a smiley, but I thought that it was neither sufficiently funny
nor sufficiently obscure to require a smiley. I guess I was wrong on
that second part. All I was trying to do was point out that "... can be
used to compute ..." is too vague a phrase to be used in a specification
that would mean what you wanted it to mean.
The wording of what? All of the citations from the standard so far have
been made by me, and none of them are worded in such a way as to
conflict with the implementation I described.
Citation, please?
Because uintmax_t and long double are the types whose limits determine
what "... sizeof ... can be used to compute ...", not size_t. That's
because the term "compute" is sufficiently vague to allow for a sizeof
expression that is no more than a sub-expression of an enclosing
expression with a result that is of some type other than size_t. The
maximum value that can be represented by such an enclosing expression is
either UINTMAX_MAX or LDBL_MAX, whichever is larger (almost certainly
LDBL_MAX). As long as the size can be correctly computed in one of those
types, with the sizeof operator playing some role somewhere in the
computation, then a hypothetical requirement that "... sizeof ... can be
used to compute the size of any object." would be satisfied.
For a hypothetical future version of the standard where there was, in
fact, a requirement that "... sizeof ... can be used to compute the size
of any object.", the existence of such a requirement would imply that a
conforming implementation of C where calloc(2,SIZE_MAX) returns a
non-null pointer must have either UINTMAX_MAX OR LDBL_MAX >= the size of
the object created by that call. Therefore, you could write:
if(p)
{
#if UINTMAX_MAX/2 >= SIZE_MAX
uintmax_t size = 2LL * sizeof *p;
#else
long double size = 2.0L * sizeof *p;
#endif
// do something with size.
}
....
An assertion for which you've provided no citations from the standard,
nor any arguments based upon such citations. Even the citation you have
provided from K&R II fails to specify any such requirement.
I wasn't talking about converting the size to another type; I was
talking about calculating the size in another type, because SIZE_MAX was
too small to be used for such calculations. Because such calculations
can be performed, a requirement that the computation be possible does
not greatly constrain the value of SIZE_MAX.
That was really intended as a kind of joke. Perhaps I should have
inserted a smiley, but I thought that it was neither sufficiently funny
nor sufficiently obscure to require a smiley. I guess I was wrong on
that second part. All I was trying to do was point out that "... can be
used to compute ..." is too vague a phrase to be used in a specification
that would mean what you wanted it to mean.
The wording of what? All of the citations from the standard so far have
been made by me, and none of them are worded in such a way as to
conflict with the implementation I described.
B
Barry Schwarz
Unless I misread your original response, which has been snipped beyond
recognition above, the result in question was the evaluation of the
sizeof operator. Is there some debate about the type of this
evaluation?
snip
I'll agree to disagree.
So my quote from 7.20.3.1 wasn't from the standard? OK, I confess. I
actually copied it from n1256.
We can disagree on whether I'm interpreting it correctly but I did
provide it. You even quoted it back to me in your message of 15 May
at 2303Z. Looking at snipped quotes in a response is not a good way
to remember who said what
J
James Kuyper
No, the result in question was the calculation of "... the size of any
object." The text saying so was yours, not mine, and it has survived all
snipping.
No, there's a debate about whether that type is required to be capable
of holding "the size of any object". I contend it's only required to
hold the size of types, whether or not there's an object of that type.
Passing a type to sizeof, either directly or through an expression of
that type, whose size cannot be represented in size_t, renders the
behavior undefined by reason of a lack of definition (or more precisely,
by reason of an internally contradictory definition of the behavior).
I'd prefer an explanation of your disagreement, over a bald statement of it.
Sorry, I missed the fact that you did cite that section, probably due to
it's lack of relevance.
The implementation I described conforms to the requirements of 7.20.3.1;
the (unspecified) value of SIZE_MAX is, indeed, as required by 7.20.3.1,
"the limit of size_t".
What I've repeatedly challenged you to provide is one or more citations
that say, directly or indirectly, that SIZE_MAX is the limit on the size
of objects. If they say it only indirectly, they should be accompanied
by an argument explaining how that conclusion may be derived from those
citations. All you've been doing is saying that this must be the case,
without addressing my arguments, or presenting any of your own.
I'll give you some help:
7.19p2 describes size_t: "the unsigned integer type of the result of the
sizeof operator". It does not describe it as a type with sufficient
range to store the size of any object.
6.5.3.4p2 specifies that "The sizeof operator yields the size (in bytes)
of its operand, which may be an expression or the parenthesized name of
a type. The size is determined from the type of the operand". It does
not say that arbitrary expressions which have not been passed to
sizeof() must have types small enough that sizeof() could express the
size of those types.
It does say that only the type of the expression is relevant in
determining the value yielded by "sizeof expression". Therefore, if
"sizeof expression" causes problems with 6.5.3.4p2, the problems are due
to the type of the expression, and can be fixed by changing that type;
they don't have anything to do with the value of that expression,
whether or not it is an lvalue expression referring to an actual object.
Those problems can therefore neither be avoided by having calloc()
return a null pointer value, nor caused by calloc() returning a non-null
pointer value. 6.5.3.4p2 therefore cannot constrain calloc() to return a
null pointer.
We can disagree on whether I'm interpreting it correctly but I did
provide it. You even quoted it back to me in your message of 15 May
at 2303Z. Looking at snipped quotes in a response is not a good way
to remember who said what
Neither is looking at unsnipped quotes, when they get as long as they
would be if I'd failed to snip them.
T
Tim Rentsch
Barry Schwarz said:
Consider the following conforming program:
#include <stdio.h>
int
main(){
unsigned k;
unsigned long long n;
for( k = 0; k < 20; k++ ){
n = sizeof (char [k][ (size_t)-1 / 17 ]);
printf( "k: %3u n: %40llu\n", k, n );
}
return 0;
}
The type (char [k][ (size_t)-1 / 17 ]) corresponds to what we
might expect from a calling calloc( k, (size_t)-1 / 17 ) , eg,
we might have
char (*a)[(size_t)-1 / 17] = calloc( k, (size_t)-1 / 17 );
and then use a[j] to access individual characters of the
allocated memory returned by calloc().
Question: could a conforming implementation define calloc()
in such a way that the allocation
char (*a)[(size_t)-1 / 17] = calloc( k, (size_t)-1 / 17 );
works for k == 100, ie, a non-null pointer is returned, and
the amount of memory allocated is sufficiently large to hold
an array of type (char[k][(size_t)-1 / 17]), and accesses to
the array using
a[j]
with 0 <= i < k, and 0 <= j < (size_t)-1 / 17, will all work?
My answer to this question is Yes. And that answer is consistent
with the existence and observed behavior of the conforming program
shown above.
T
Tim Rentsch
James Kuyper said:
Which is it? Does the Standard require sizeof to produce a value
that must fit in a size_t, or is the behavior of sizeof undefined in
some cases? They can't both be true. I don't see any text in the
Standard that requires that the result of doing a sizeof must fit in
a size_t, only that the type of the result is size_t.
Actually the behavior in such cases is explicitly undefined under
the provisions 6.5 p5.
L
lawrence.jones
Tim Rentsch said:
Previous discussions have, I think, reached concensus that there are two
valid ways to resolve the apparent contradiction: An implementation is
free to disallow declarations (including abstract ones) that would
specify a size that is too big to fit in a size_t. An implementation is
also free to accept such declarations and declare that the behavior of
sizeof is undefined in that case. Both lead to completely consistent
readings of the standard and the committee has not felt compelled to
bless one over the other.
T
Tim Rentsch
I would expect that implementations are always free to reject any
program that has a type whose size is known to be > 65535, for
exceeding a minimum environmental limit, whether sizeof is used
or not. Certainly such a program cannot be strictly conforming,
as it is reasonable to expect any implementation with SIZE_MAX
equal to 65535 normally would reject it. Still, the Standard
doesn't require rejection of programs whose types are too large.
Moreover, it is not always possible to determine at compile time
if the size of a type will exceed SIZE_MAX, because of variable
length arrays. If sizeof is used on such a type that is overly
large, the result is not in the range of representable values
for its type, that is, this would be an /exceptional condition/
as defined in 6.5 p5, and so is explicitly undefined behavior.
Ergo I don't think there is any contradiction. The Standard
allows but does not require an implementation to reject programs
known to have overly large types; any sizeof's done on overly
large types that may arise otherwise fall under 6.5 p5, and hence
are undefined behavior.