C
Christopher Benson-Manica
Some recent posts got me thinking about how one might have dealt with
simplistic malloc() implementations which might return NULL for a 64K
request but might accept two 32K requests or four 16K requests. (I'm
assuming, perhaps incorrectly, that quality modern implementations
will coalesce free space as necessary and if possible to satisfy
requests.) I came up with the following (compilable but untested)
first cut at code to try a combination of smaller allocations:
#include <stdlib.h>
#define MAX_SUBCHUNKS 4
/* Functions for accessing individual chunk members omitted */
struct chunk {
void *data[MAX_SUBCHUNKS];
int num_subchunks;
/* Needed by chunk accessors to correctly calculate which subchunk a
* requested member will be in, given that the division of members
* in subchunks is done in a known way, as below */
size_t nmemb;
size_t size;
};
struct chunk *allocate_chunk( struct chunk *chunk, size_t nmemb, size_t size ) {
size_t idx, jdx;
int succeeded;
chunk->nmemb=nmemb;
chunk->size=size;
for( idx=0; idx < MAX_SUBCHUNKS; idx++ ) {
chunk->num_subchunks=idx+1;
succeeded=1;
for( jdx=0; jdx < idx; jdx++ ) {
size_t num_members=nmemb/(idx+1)+( nmemb%(idx+1)>jdx ? 1 : 0 );
if( (chunk->data[jdx]=malloc(num_members)) == NULL ) {
succeeded=0;
break;
}
}
if( !succeeded ) { /* One of the suballocations failed - free all
existing allocated space */
for( jdx=0; jdx < idx; jdx++ ) {
if( chunk->data[jdx] != NULL ) {
free( chunk->data[jdx] );
}
else {
break;
}
}
continue; /* Try again with more subchunks */
}
return chunk;
}
return NULL; /* Couldn't allocate memory in any combination of
subchunks */
}
int main(void) {
return 0;
}
Were (are?) there implementations where this strategy (or something
along the same lines but undoubtedly more sophisticated) might have
been required to work around a malloc() that was too silly to work out
the details for itself?
This question gives rise to another point - a function that allows the
user to query the malloc() implementation and determine the maximum
number of objects with a given size that it will accept an allocation
request for would really be handy. I wouldn't think that such a
function would be difficult for the malloc() implementor to provide,
assuming that the caller accepts the obvious performance penalty.
This would allow code that needs a substantial but arbitrary amount of
space to easily ask malloc(), "How much space can I have? Ok, that's
enough, give me all of it." Was such a function considered? (I can
take this followup question to comp.std.c if need be.)
simplistic malloc() implementations which might return NULL for a 64K
request but might accept two 32K requests or four 16K requests. (I'm
assuming, perhaps incorrectly, that quality modern implementations
will coalesce free space as necessary and if possible to satisfy
requests.) I came up with the following (compilable but untested)
first cut at code to try a combination of smaller allocations:
#include <stdlib.h>
#define MAX_SUBCHUNKS 4
/* Functions for accessing individual chunk members omitted */
struct chunk {
void *data[MAX_SUBCHUNKS];
int num_subchunks;
/* Needed by chunk accessors to correctly calculate which subchunk a
* requested member will be in, given that the division of members
* in subchunks is done in a known way, as below */
size_t nmemb;
size_t size;
};
struct chunk *allocate_chunk( struct chunk *chunk, size_t nmemb, size_t size ) {
size_t idx, jdx;
int succeeded;
chunk->nmemb=nmemb;
chunk->size=size;
for( idx=0; idx < MAX_SUBCHUNKS; idx++ ) {
chunk->num_subchunks=idx+1;
succeeded=1;
for( jdx=0; jdx < idx; jdx++ ) {
size_t num_members=nmemb/(idx+1)+( nmemb%(idx+1)>jdx ? 1 : 0 );
if( (chunk->data[jdx]=malloc(num_members)) == NULL ) {
succeeded=0;
break;
}
}
if( !succeeded ) { /* One of the suballocations failed - free all
existing allocated space */
for( jdx=0; jdx < idx; jdx++ ) {
if( chunk->data[jdx] != NULL ) {
free( chunk->data[jdx] );
}
else {
break;
}
}
continue; /* Try again with more subchunks */
}
return chunk;
}
return NULL; /* Couldn't allocate memory in any combination of
subchunks */
}
int main(void) {
return 0;
}
Were (are?) there implementations where this strategy (or something
along the same lines but undoubtedly more sophisticated) might have
been required to work around a malloc() that was too silly to work out
the details for itself?
This question gives rise to another point - a function that allows the
user to query the malloc() implementation and determine the maximum
number of objects with a given size that it will accept an allocation
request for would really be handy. I wouldn't think that such a
function would be difficult for the malloc() implementor to provide,
assuming that the caller accepts the obvious performance penalty.
This would allow code that needs a substantial but arbitrary amount of
space to easily ask malloc(), "How much space can I have? Ok, that's
enough, give me all of it." Was such a function considered? (I can
take this followup question to comp.std.c if need be.)