已分配内存的簿记元数据 [英] Book-keeping metadata for allocated memory

问题描述

请阅读以下示例。对不起，我不能把它缩小，

但这很简单。


当客户端代码调用newThingy（）时，它类似于malloc：

客户端获取一个指向一大块内存的指针，它可以用于它自己的

目的。

但是在库上方面，我希望能够为我分发的每个内存块做一些簿记

。我想要一些隐藏的东西。元数据

（我保留在struct Container中）与每个内存关联

块我从newThingy（）返回。


_problem_位于findContainer（）中。它以线性时间运行。我会像恒定时间那样获得
。我不想搜索包含已分配内存的Container

。我该怎么办？


#include< stdio.h>

#include< stddef.h>

＃ include< malloc.h>

#include< assert.h>


/ *" library"代码* /


typedef struct Container_

{

int foo;

int bar;

void * thingy;

struct Container_ * next;


}容器;


Container * list = NULL;


void * newThingy（size_t size）

{

void * thingy;

容器*容器;


thingy = malloc（大小）;

断言（thingy）;


container =（Container *）malloc（sizeof（Container））;

断言（容器）;


container-> foo = 42;

container-> bar = 3;

container-> thingy = thingy;


container-> next = list;

list = container;


return thingy;

}


Container * findContainer（void * thingy）

{

容器*容器;


for（container = list; container; container） = container-> next）

{

if（container-> thingy = = thingy）

返回容器;

}


返回NULL;

}


void doSomething（void * thingy）

{

Container * container = findContainer（thingy）;

断言（容器）;


/ *做点什么* /

printf（"％d \ n"，container-> foo）;

}


/ *" client"代码* /


typedef struct

{

int无论如何;

浮点东西;

} ClientThingy1;


typedef struct

{

char dontask;

int * whocares;

} ClientThingy2;


int main（无效）

{

ClientThingy1 * thingy1 = newThingy（sizeof（ClientThingy1））;

ClientThingy2 * thingy2 = newThingy（sizeof（ClientThingy2））;


doSomething（thingy1）;

doSomething（thingy2）;


返回0;

}


我是考虑到为容器和东西分配内存的一些东西

，如：


容器*容器= malloc（sizeof（容器）+尺寸）;


然后返回类似


return（container + sizeof（Container））;


然后findContainer（）会变成恒定时间，例如：


Container * fi ndContainer（void * thingy）

{

返回thingy - sizeof（容器）;

}


但这是否可移植且定义明确？还是有其他解决方案吗？


/ David

解决方案

< pi ************ @ gmail.com>在留言中写道

news：11 ********************** @ u72g2000cwu.googlegr oups.com ...

请阅读以下示例。对不起，我不能把它缩小，
但很简单。

当客户端代码调用newThingy（）时，它类似于malloc：
但是在库上。方面，我希望能够为我分发的每个内存块做一些簿记。我想要一些隐藏的东西。元数据
（我保留在struct Container中）与我从newThingy（）返回的每个内存块相关联。

_problem_位于findContainer（）中。它以线性时间运行。我会像往常一样。我不想搜索包含已分配内存的Container
。我该怎么办？

< snip>但这是便携式和明确定义的吗？或者还有其他解决方案吗？

您需要的是一种将thingy'的void *映射到元数据的方法

容器*。我可能会设置一个数组和一个数字哈希函数。

哈希函数会将一个thingy void *转换为一个唯一的整数，它可以将
用作数组的索引。数组将是Container *的。当您分配Container'时，您使用thingy'的void *调用散列函数，并且

将Container *存储在数组中。当你需要解除分配一个容器时，你需要使用thingy'的void *来调用hash函数，并从数组中调用
的ret *。散列函数的实现可能也可能不容易。

Rod Pemberton

PS。了解今天的线性时间和常数时间......

>

你需要的是一种映射东西的空虚的方法*到您的元数据'
容器*。

True。我自己考虑过哈希，但我希望有一个更简单的解决方案，例如我提出的解决方案。

。我只是不知道

该解决方案是否便携且定义明确。


/ David

pi ************ @ gmail。 com 写道：

你需要的是一种将thingy'的void *映射到你的元数据'
容器*的方法。

True。我自己考虑过哈希，但我希望有一个更简单的解决方案，比如我提出的解决方案。我只是不知道该解决方案是否便携且定义明确。

提出便携式设备有一些困难
哈希函数。您可以尝试将指针转换为

整数（uintptr_t，如果你已经得到它）并散列整数，

但是转换是实现定义的并且需要不是

有用。您可以检查指针'

表示的各个字节，并从中获取哈希值，但这需要（1）所有指针''比特是值比特。或者

，该实现给出了任何填充位。一致的

值，以及（2）每个指针只有一个表示

或者实现一直只使用一个

可能的表示作为规范的。


另一种非便携的可能性是使用基于比较 -

的数据结构，如跳过列表或AVL树，使用

指针值本身作为搜索键。

这种方法的不可移植性是关系运算符<，< =，> =，>

没有在任意指针上定义，但仅限于指向单个数组的
元素的指针。尽管如此，许多系统实际上确实通过比较随机而给出了有意义的结果。指针，如果你愿意将自己限制在这样的系统中，那就是
- 不是太多了很多限制，也许 - 这可能是一种可接受的方法。 br />
它比散列的优势在于你不仅可以轻松找到你要搜索的项目，还可以找到它的邻居（如果有的话），

内存管理包中经常需要的操作。


无论你选择什么，请注意虽然方法是

可能适用于许多系统它实际上不是由标准保证的，而且可能存在失败的系统。例如，如果你使用散列方法，请准备为不同的系统插入不同的b / b
哈希以适应当地的特点。

如果在可能的情况下，写一个完整性检查程序，试图测试你所依赖的非便携假设;这个程序可能

甚至建议您使用哪种替代哈希方法

应该使用。


-

Eric Sosman
es*****@acm-dot-org.inva 盖子

Please read the example below. I''m sorry I couldn''t make it smaller,
but it is pretty simple.

When client code is calling newThingy(), it is similar to malloc: the
client gets a pointer to a chunk of memory that it can use for it''s own
purposes.

But on the "library" side, I want to be able to do some book-keeping
for each memory block that I hand out. I want some "hidden" meta-data
(that I keep in struct Container) to be associated with each memory
block that I return from newThingy().

The _problem_ lies in findContainer(). It runs in linear time. I would
like constant time. I would like not having to search for the Container
containing the allocated memory. What do I do?

#include <stdio.h>
#include <stddef.h>
#include <malloc.h>
#include <assert.h>

/* "library" code */

typedef struct Container_
{
int foo;
int bar;
void* thingy;
struct Container_* next;

} Container;

Container* list = NULL;

void* newThingy(size_t size)
{
void* thingy;
Container* container;

thingy = malloc(size);
assert(thingy);

container = (Container*) malloc(sizeof(Container));
assert(container);

container->foo = 42;
container->bar = 3;
container->thingy = thingy;

container->next = list;
list = container;

return thingy;
}

Container* findContainer(void* thingy)
{
Container* container;

for (container = list; container; container = container->next)
{
if (container->thingy == thingy)
return container;
}

return NULL;
}

void doSomething(void* thingy)
{
Container* container = findContainer(thingy);
assert(container);

/* do something */
printf("%d\n", container->foo);
}

/* "client" code */

typedef struct
{
int whatever;
float something;
} ClientThingy1;

typedef struct
{
char dontask;
int* whocares;
} ClientThingy2;

int main(void)
{
ClientThingy1* thingy1 = newThingy(sizeof(ClientThingy1));
ClientThingy2* thingy2 = newThingy(sizeof(ClientThingy2));

doSomething(thingy1);
doSomething(thingy2);

return 0;
}

I was considering something along the lines of allocating the memory
for Container and thingy in one go, like:

Container* container = malloc(sizeof(Container) + size);

and then return something like

return (container + sizeof(Container));

and then findContainer() would become constant time, something like:

Container* findContainer(void* thingy)
{
return thingy - sizeof(Container);
}

But is that portable and well-defined? Or are there other solutions?

/David

解决方案

<pi************@gmail.com> wrote in message
news:11**********************@u72g2000cwu.googlegr oups.com...

Please read the example below. I''m sorry I couldn''t make it smaller,
but it is pretty simple.

When client code is calling newThingy(), it is similar to malloc: the
client gets a pointer to a chunk of memory that it can use for it''s own
purposes.

But on the "library" side, I want to be able to do some book-keeping
for each memory block that I hand out. I want some "hidden" meta-data
(that I keep in struct Container) to be associated with each memory
block that I return from newThingy().

The _problem_ lies in findContainer(). It runs in linear time. I would
like constant time. I would like not having to search for the Container
containing the allocated memory. What do I do?
<snip> But is that portable and well-defined? Or are there other solutions?

What you need is a method to map thingy''s void* to your metadata''s
Container*. I''d probably setup an array and a numeric hash function. The
hash function would convert a thingy void* to a unique integer which could
be used as an index into an array. The array would be of Container* ''s. As
you allocate Container''s, you call the hash function with thingy''s void* and
store the Container* in the array. When you need to deallocate a Container,
you call the hash function with thingy''s void * and retreive Container* from
the array. The implementation of the hash function may or may not be easy.
Rod Pemberton
PS. Learned what linear time and constant time are today...

>

What you need is a method to map thingy''s void* to your metadata''s
Container*.

True. I considered the hashing myself, but I was hoping that there was
a simpler solution such as the one I presented. I just don''t know if
that solution is portable and well-defined.

/David

pi************@gmail.com wrote:

What you need is a method to map thingy''s void* to your metadata''s
Container*.

True. I considered the hashing myself, but I was hoping that there was
a simpler solution such as the one I presented. I just don''t know if
that solution is portable and well-defined.

There are some difficulties in coming up with a portable
hash function. You could try converting the pointer to an
integer (uintptr_t, if you''ve got it) and hashing the integer,
but the conversion is implementation-defined and need not be
useful. You could inspect the individual bytes of a pointer''s
representation and derive a hash value from them, but this
requires (1) that all the pointer''s bits be "value bits" or
that the implementation gives any "padding bits" consistent
values, and (2) that each pointer have just one representation
or that the implementation consistently uses just one of the
possible representations as "canonical."

Another non-portable possibility would be to use a comparison-
based data structure like a skip list or AVL tree, using the
pointer value itself as the search key. The non-portability in
this approach is that the relational operators <, <=, >=, > are
not defined on arbitrary pointers, but only on pointers to
elements of a single array. Nonetheless, many systems actually
do give meaningful results from comparing "random" pointers, and
if you''re willing to restrict yourself to such systems -- not too
great a restriction, perhaps -- this may be an acceptable approach.
Its advantage over hashing is that you can easily find not only
the item you''re searching for, but also its neighbors (if any),
an operation one often needs in memory management packages.

Whatever you choose, be aware that although the method is
likely to work on many systems it is not actually guaranteed by
the Standard and there may be systems where it will fail. If you
use a hashing method, for example, be prepared to plug in different
hashes for different systems to accommodate local peculiarities.
If at all possible, write a sanity-checking program that tries to
test the non-portable assumptions you rely on; this program might
even suggest which of several alternative hashing methods you
should use.

--
Eric Sosman
es*****@acm-dot-org.invalid

这篇关于已分配内存的簿记元数据的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！