处理天真的malloc（）实现 [英] Dealing with naive malloc() implementations
问题描述
最近的一些帖子让我想到了如何处理
简单的malloc（）实现，这些实现可能会为64K
请求返回NULL但可能接受两个32K请求或四个16K请求。 （我是
假设，也许是错误的，质量现代的实现
将根据需要合并可用空间，如果可能的话，满足
请求。）我想出了以下内容（可编译但未经测试）
首先减少代码以尝试组合较小的分配：
#include< stdlib .h>
#define MAX_SUBCHUNKS 4
/ *用于访问单个块成员的函数省略* /
struct chunk {
void * data [MAX_SUBCHUNKS];
int num_subchunks;
/ *块访问器需要正确计算哪个子块a
*请求的成员将在，因为子块中的成员分区
*以已知的方式完成，如下所示* /
size_t nmemb;
size_t size;
};
struct chunk * allocate_chunk（struct chunk * chunk，size_t nmemb，size_t尺寸）{
size_t idx，jdx;
int成功;
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）{
成功= 0;
休息;
}
}
如果（！成功）{/ *其中一个子分配失败 - 免费全部
现有分配空间* /
jdx = 0; jdx< idx; jdx ++）{
if（chunk-> data [jdx]！= NULL）{
free（chunk-> data [jdx]）;
}
else {
break;
}
}
继续; / *再尝试使用更多子块* /
}
返回块;
}
返回NULL; / *无法以任何组合分配内存
子块* /
}
int main（void）{
返回0;
}
是否（是？）实施此策略（或其他内容
沿着相同的路线，但无疑更复杂）可能需要
来解决一个太愚蠢的malloc（）来解决这个问题
其自身的细节？
这个问题引出了另一个问题 - 一个允许
用户查询malloc（）实现并确定最大值的函数
具有给定大小的对象数量，它将接受分配
请求真的很方便。我不认为这样的一个
函数对于malloc（）实现者来说很难提供，假设调用者接受明显的性能损失，那么
。 />
这将允许需要大量但任意数量的
空间的代码轻松询问malloc（），我可以拥有多少空间？好的，那就足够了，给我所有的全部。是否考虑过这样的功能？ （如果需要，我可以
将这个后续问题带到comp.std.c。）
-
C. Benson Manica |我*应该*知道我在说什么 - 如果我
cbmanica（at）gmail.com |不，我需要知道。火焰欢迎。
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.)
--
C. Benson Manica | I *should* know what I''m talking about - if I
cbmanica(at)gmail.com | don''t, I need to know. Flames welcome.
推荐答案
Christopher Benson-Manica< at *** @ faeroes.freeshell.orgwrote：
Christopher Benson-Manica <at***@faeroes.freeshell.orgwrote:
（相当冗长的帖子）
(a rather lengthy post)
struct chunk * allocate_chunk（struct chunk * chunk，size_t nmemb，size_t size）{
struct chunk *allocate_chunk( struct chunk *chunk, size_t nmemb, size_t size ) {
（snip）
(snip)
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）{
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 ) {
if（（chunk-> data [jdx] = malloc（num_members * size）） == NULL）{
嗯，笨蛋。我真的希望自己设法犯错，因为* b $ b至少是微妙的，所以*我*看不到它们。
-
C. Benson Manica |我*应该*知道我在说什么 - 如果我
cbmanica（at）gmail.com |不，我需要知道。火焰欢迎。
if( (chunk->data[jdx]=malloc(num_members*size)) == NULL ) {
Well, darn. I was really hoping I had managed to make mistakes that
were at least subtle enough so that *I* couldn''t see them.
--
C. Benson Manica | I *should* know what I''m talking about - if I
cbmanica(at)gmail.com | don''t, I need to know. Flames welcome.
Christopher Benson-Manica写于05/09/07 10:15，：
Christopher Benson-Manica wrote On 05/09/07 10:15,:
[...模拟具有多个小分配的大型分配
和accessor函数...代码剪断（仅检查了
简短...）
是否（是？）实现了这种策略（或者某些东西） />
沿着相同的路线，但无疑更复杂）可能需要
来解决一个太愚蠢的malloc（）来解决问题
自己的详细信息？
[... simulate large allocation with multiple small allocations
and "accessor" functions ... code snipped (and examined only
briefly ...]
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?
一个伙伴系统malloc（二进制，斐波那契，无论如何）
如果他们不会合并相邻的免费区域不是好友。
力求其他类型效率的实现
（例如，多线程环境中的最小锁争用）
可能推迟合并相邻的免费区域，直到星星
是正确的。
即使免费区域积极合并，也可以
仍然是碎片问题.JM Robson表明，当内存为
时，
碎片会导致分配失败三分之二被占用，即使只有两种尺寸的分配来了
。 （参见Knuth TAOCP第2.5节练习
36到38.）
结论：不需要假设愚蠢。 malloc to
进行细分大额分配。
A "buddy system" malloc (binary, Fibonacci, whatever)
will not coalesce adjacent free areas if they are not buddies.
Implementations that strive for other kinds of efficiencies
(e.g., minimal lock contention in multi-threaded environments)
might postpone coalescing adjacent free areas until the stars
are right.
Even if free areas are coalesced aggressively, there can
still be fragmentation problems. J.M. Robson showed that
fragmentation can cause allocation failure when memory is
only about two-thirds occupied, even if the allocations come
in only two sizes. (See Knuth TAOCP section 2.5 exercises
36 through 38.)
Conclusion: One need not presume a "silly" malloc to
make subdividing large allocations worth while.
这个问题引出了另一个问题 - 一个允许
的功能
用户查询malloc（）实现并确定具有给定大小的最大
对象数量，它将接受分配
请求将真的是便利。我不认为这样的一个
函数对于malloc（）实现者来说很难提供，假设调用者接受明显的性能损失，那么
。 />
这将允许需要大量但任意数量的
空间的代码轻松询问malloc（），我可以拥有多少空间？好的，那就足够了，给我所有的全部。是否考虑过这样的功能？ （我可以
如果需要，可以将这个后续问题带到comp.std.c。）
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.)
我不知道这样的设施在标准化辩论中被认为是
。
...但在PPOE我做了相当大的工作量
在一个更精心设计的内存管理器上提供了一个与b $ b相关的功能（对于它管理的一些内存池）。
它回答了类似的多大可以realloc（）
制作这样一个区域而不需要重新定位它的
内容？在将我们的产品移植到其第一个64位平台的第一个平台上的过程中，我发现这个功能花费了大量的时间并开始寻找方法。 />
加快速度。
问题发生在有问题的区域是
的结束时分配的内存：在一个64位系统上有一个不可思议的大量未使用的虚拟内存
在该区域之后，并且整个系统正在搅拌/>
试图弄清楚它能找到多少交换。
似乎没有一个明显的方法来回答这个问题
，效率可接受。所以我把我的注意力从缓慢的功能和呼叫者转移到了
;什么用途？
他们得到了答案？罗！只有大约一半
a打打电话，他们都做了类似
if（fragSize（ptr）> = what_i_need）
do_this（）;
其他
do_that（）;
所以我放弃了麻烦的功能和
将其替换为类似将realloc（）需要
重新定位该区域，如果要求将其扩展到这样的那样
a size？，这更易于处理。所有来电者
如果（canReallocInPlace（ptr，what_i_need））
do_this（）;
其他
do_that（）;
....这是附近一个美好的一天。
这个啰嗦的轶事的一点是，我有一些理由怀疑我能用什么最有用的
空间的用处有"？;即使您可以提出要求，也请按照给我所有这一切来支付
。似乎是一个危险的下一步，一个
可能会导致几乎立即内存耗尽
导致失败或性能不佳（想想以后
malloc（）调用所有返回NULL，fopen（）失败或
只产生无缓冲的I / O流，等等）。这是一个乍一看似乎很有趣的问题但是
我不太确定它会变得有用。
相关问题我可以有N个字节吗？完全是另一个
的问题 - 而且C库已经提供了
回答它的方法。
canReallocInPlace（）是不是图书馆的一部分，并且
这些内容可能是一个有用的补充。
可能不适合多线程程序，但
（当你得到答案时，它可能已经过时了。）
-
Er ********* @sun.com
" Christopher Benson-Manica" < at *** @ faeroes.freeshell.orgwrote in message
news：f1 ********** @ chessie.cirr.com ...
"Christopher Benson-Manica" <at***@faeroes.freeshell.orgwrote in message
news:f1**********@chessie.cirr.com...
最近的一些帖子让我想到了如何处理
简单的malloc（）实现，这些实现可能会为64K返回NULL
请求但可能接受两个32K请求或四个16K请求。 （我是
假设，也许是错误的，质量现代的实现
将根据需要合并可用空间，如果可能的话，满足
请求。）我想出了以下内容（可编译但未经测试）
首先减少代码以尝试组合较小的分配：
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:
（ ...）
(...)
是否（是？）实现了这种策略（或者什么东西
沿着相同的路线，但无疑更复杂）可能需要
来解决一个太愚蠢的malloc（）问题
的详细信息？
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?
在我的分配器中，具有给定粒度的块的空闲状态是
保存在单独的位数组中。 Free只需设置适当数量的
位并返回，而malloc扫描数组，查找
所需的相邻位数设置。
使用了几个具有不同粒度的竞技场，因此没有分配
需要超过32位。您可以在我的网站上查看代码：
www.geocities.com/malbrain 。
这个问题引出了另一个问题 - 一个允许
用户查询malloc（）实现的函数确定具有给定大小的最大
对象数量，它将接受分配
请求真的很方便。
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.
欢迎您添加适当的位扫描仪来确定这些来自竞技场的
数量。
karl m
You''re welcome to add an appropriate bit scanner to determine these
quantities from the arenas.
karl m
这篇关于处理天真的malloc（）实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
