| |
Home • About Us • A-Z Index • Search * Contact Us • Register • Login • Press • ShopThe Open Brand -- Problem Reporting and Interpretations System |
|
Problem Report 1272 Details
Show help | Quick Search | Submit a Test Suite Support Request | Click here to view your privileges
This page provides all information on Problem Report 1272.
Report 1272 Actions
Problem Report Number 1272 Submitter's Classification Test Suite problem State Resolved Resolution Test Suite Deficiency (TSD) Problem Resolution ID TSD.X.0554 Raised 1970-01-01 08:00 Updated 2003-03-13 08:00 Published 1999-01-29 08:00 Product Standard Internationalised System Calls and Libraries Extended (UNIX 95) Certification Program The Open Brand certification program Test Suite VSU version 4.1.1 Test Identification CAPIbase/fstrdup 2 Problem Summary TSD4U.00264 This IR claims that malloc() may fail even if a larger size piece of memory is available. Problem Text
Following examination by our experts in this functional area we
can provide the following analysis. This was originally filed
as a Testsuite Support Request.
The "randomness" is due to how many variables there are in the
environment.
We were able to faithfully duplicate the problem with a certain
environment but fiddling with the environment in other ways
caused the failure to go away.
To explain what's happening, let us recap the test in
question:
1. Set the break space limit to 4000K bytes.
2. Allocate chunks of 16K bytes until malloc() fails.
3. Allocate chunks of 1 byte until malloc() fails.
4. free() the last successful 16K chunk.
5. strdup() a 51 (including the nul) byte string.
6. attempt to malloc() 16K bytes expecting failure.
7. restore the break space limit.
Now, what's happening depends on the test framework's use of
malloc() and realloc() before the above testing starts. This
code twice calls tet_putenv(). This results in a malloc() for
the first added variable and a realloc() for the second one.
If the environment starts with an even number of variables
(and the ones added by the framework are not already present),
then the realloc() ends up reusing the same space since the
alignment padding added to the first allocation has enough
space for the additional pointer needed for the realloc() call.
In this case, the test approach works because no memory was
ever free()d and thus the strdup() had to use a piece of the
just free()d 16K bytes.
However, if the incoming environment starts with an odd number
of variable, the realloc(), assuming that the environment is
small enough, will return a different block, leaving a nice-
sized free block in the arena, one quite big enough for the
strdup() to use.
But this free block is too small for malloc()'s approach for
"small blocks" like the 1 byte allocations used in step 3 above.
This is because these small blocks must be allocated in larger
groups. This free block isn't big enough for even the group of
mimimum-sized allocations attempted in step 3.
By changing step 3 in the test code from
while (malloc(1) != NULL)
;
to
{size_t sz = strlen(known)+1; do { while (malloc(sz)); }
while (--sz);}
[where known is the string soon to be passed to strdup()], we
guarantee that we've used up all the allocation space from the
smallest sizes up to the size neede for the strdup(). With
this fix, the test should not be able to fail.
The subtle flaws of this test are that the only allocations
that matter are those that take place during the test and that
a loop on malloc(1) must consume any remaining free space in
the arena. With our generalizing of the "consume the rest of
the free space" loop to step down from the length of the string
to 1, we get a virtual guarantee that the following strdup()
*must* use part of the just-free()d 16K byte block on our
implementation.
Reviewing the malloc definition in ISO C and UNIX95/98 along with
RLIMIT_DATA just in UNIX95/98 we can see the definitions do not
address the internals of how malloc handles space allocation
and what a programmer should expect in predicting what allocation
actually is done beyond knowing null will be returned and ENOMEM is
set when the request cannot be satisfied. The change suggested
above will improve the test strategy we feel.
We would like to claim a TSD against this test.
The following was the response from the Testsuite Developers to
the support request details above:-
> ... it seems to me you are saying that...
>
> In some cases to your malloc algorithm returns a NULL when space
> is still available. The reason for this being that the space available
> is being held for more efficient allocation in a later request.
>
> If this is not true then please let me know and I will send you
> another email digging into the details of your original mail.
>
> If this is the true then I believe we disagree with you about the TSD.
>
> In our opinion malloc(1) should work so long as 1 byte of memory
> is left to allocate. (Actually 1 byte available on a suitably
> aligned boundary). In order to agree otherwise we would have
> to have you file an IR, which we would disagree with, then get
> a base resolution supporting your opinion.
Further discussion within our company we believe the testsuite
developer does identify the reason for our request. The opinion
stated though for rejecting the TSD is in our opinion incorrect.
We believe the C committee would be arguing that it is
entirely up to the implementation how space is allocated by
malloc() and friends. There is no requirement on fragmentation
(or lack thereof); no requirement on using all the underlying
space potentially available from the OS, assuming there is even
an OS at all; no requirement that it ever has to allocate any
space at all. And, therefore, you cannot assert that just
because malloc() returns null for size "n" that it cannot succeed
for size "2n", for example.
Taking it to POSIX and TOG, we bring in UNIX semantics. This
gives us some requirements regarding the notion of break space
and process limits, but these really don't have much affect on
the lack of requirements listed above. Essentially, we have
at the extreme cases of the above purely issues regarding
"quality of implementation". The marketplace will not permit
a completely nonfunctional malloc(), but a malloc() that has
run out of break space that chooses not to allocate any more
1 byte allocations, even though it might be able to satisfy a
60 byte allocation is not such an issue. Even if it were, it
is still a quality of implementation issue, not a lack of
conformance to any standards.
Moreover, the test in hand isn't testing whether malloc() is
doing a good job of using all the available break space, it's
simply trying to verify that strdup() acts like it use malloc(),
and it happens that our implementation, in certain test
circumstances, manages to find a better fit for the strdup()
space--still using malloc()--than the just free()d 16K chunk.
What it takes to get this test to work with our implementation
is to be sure to drain all the block sizes up to the size of
the strdup() request.
Refering again directly to the "opinion" stated by the Testsuite
Developers we can see no such requirement. A valid implementation
can, if it wants, refuse to allocate any space at all. Such an
implementation is not reasonable and would not survive, but it
meets all the specifications of the associated standards.
Implementations can reject allocation requests at a whim. Again,
it isn't likely that the marketplace would support such an
implementation.
However, most modern malloc() implementations these days put much
more structure behind the APIs than that used in the classic UNIX
implementations. In practice, very small blocks get special
handling. One standard approach is to allocate more than one of
these at a time, another is to round up small allocations to a
minimum size. These can end up "wasting" space in different ways,
but one cannot assume that allocations of 1 byte must consume all
the remaining break space.
However, the test in hand isn't testing the efficiency or general
behavior of malloc(); it's testing whether strdup() acts like it
calls malloc(). Since there isn't any direct way to do this, the
test (reasonably enough) says that I should be able allocate all
of the break space, open one hole in the space, do the strdup(),
and expect that a part of that hole must be consumed doing the
strdup().
Because the test operates this way, the test takes on the
responsibility to be sure that all other places that the strdup()
could possibly use have been allocated before opening the one hole.
Given a very reasonable implementation (such as ours) which uses
special case handling for small allocations (such as 1 byte), it
is possible that there is enough space for a modest strdup() to
succeed even though we cannot allocate any 1 byte blocks. Of
course, for any reasonable implementation, this case can only
happen when break space is essentially entirely consumed.
Thus, the test must at least also attempt allocations of strlen()+1
byte to be sure that there is no existing holes in the break space
that could otherwise be used for the strdup().
Test Output
TEST CASE: strdup
TEST PURPOSE #2
The pointer returned by a call to char *strdup(const
char *s1) shall be accepted by free().
PREP: Set heap size
PREP: Allocate remaining heap space
PREP: Free some memory up for strdup()
PREP: Call strdup(str)
TEST: strdup used space freed by malloc()
and thus can be freed with free()
ERROR: malloc() did not fail
Expected = NULL, Received 0x8435ee8
2 FAILReview Information
Review Type TSMA Review Start Date null Completed null Status Complete Review Recommendation No Resolution Given Review Response
We recommend this request be refused. We believe the test is correct.
The standard states the following for malloc:
The malloc() function allocates unused space for an object
whose size in bytes is specified by size and whose value is
indeterminate.
In the situation where 1-byte is being requested, the submitter says
essentially that compact-size pieces of memory have been exhausted even
though mid-size or even large-size pieces still exist.
In this situation, we believe that a request should be upgraded to any
available size in order to fulfill the request, rather than denying
the request. Unused space is available.
If a program requests memory, it needs the space, or else it will
fail, and the program will abort. Saving the mid-size or large-size
pieces for a better fit situation does not help situations that are
close to running out of memory.
Review Type SA Review Start Date null Completed null Status Complete Review Resolution No Resolution Given Review Conclusion
We recommend that this request be forwarded to the Base Working Group
for a 14 day anonymous review.
Review Type Expert Group Review Start Date null Completed null Status Complete Review Resolution No Resolution Given Review Conclusion
The Base WG recommends the request be granted. The wording in the C,
POSIX and X/Open documentation does not say that there is no memory but
that there is insufficient storage space to honor the request.
Many older and perfectly acceptable malloc implementations use the
tree and arena method to allocate storage. In this mechanism allocation
trees are asigned to an arena of allocation for 16K and 1 byte. Later
they try for a 51 byte arena. Many implementations operate with a
16 byte arena for the 1 byte mallocs and a 16K byte arena for the 16K
mallocs. The test does a reasonable attempt to fill these two arenas.
Many implementations will try to place the 51 byte strdup() into a 64
byte arena. If the test or the operating system on behalf of the test
process has already created the 64 byte arena, it will not use any of
the freed 16K area. Also if the arena's are allocated in 32k or larger
arenas just freeing one 16K arena will not allow for it to be subdivided.
This mechanism will disrupt the test without proving the assertion in
relation to the strdup() and is commonly used with memory wastefull but
high performance malloc() implementations. With none of the Standards
or Specifications stating how malloc() will function internally the
assumptions made by this test about the operation of the strdup function
may be common but are not requirements.
Also the Standards and Specifications only require that the address be
one that can be passed to free(). They place no requirement that free()
only releases memory in the malloc() memory pool. We can argue the
usefulness of multiple memory pools but the Standards and Specifications
do not preclude it.
Review Type SA Review Start Date null Completed null Status Complete Review Resolution Test Suite Deficiency (TSD) Review Conclusion
This is an agreed Test Suite Deficiency.
Problem Reporting System Options:
- View Report 1272
- List All PRs
- Search Reports
- Email the System Administrator
- View the The Open Brand Interpretations Database User Manual
Contact the Certification Authority