P**********c
发帖数: 3417 | 1 16.9 Write an aligned malloc & free function that takes number of bytes and
aligned byte (which is always power of 2)
Example
align_malloc(1000, 128) will return a memory address that is a multiple of
128 and that points to memory of size 1000 bytes.
aligned_free() will free memory allocated by align_malloc.
答案：
void* aligned_malloc(size_t required bytes, size_t alignment){
void* p1; //original block
void** p2; //aligned block
int offset = alignment-1+sizeof(void*);
if ((p1 = (void*)malloc(required_bytes+offset))==NULL) {
return NULL;
}
p2=(void**) (((size_t)(p1)+offset) & ~(alignment-1));
p2[-1]=p1;
return p2;
}
void aligned_free(void* p){
free(((void**)p)[-1];
}
感觉书上讲的不是很清楚。有人能详细讲一下那个offset怎么算出来的吗。还有任何数
& ~(alignment-1) 之后都是alignment的倍数了吧。p2是定义成void**, 返回的时候
变成void*, free的时候又被cast成void**, 用意是什么。 |
t**r
发帖数: 3428 | 2 两个* 是相当于C++里的& 传引用。
用指针给指针复制，必须这么做。
关于地址，我看书了。条目1的解释还算可以，我读了3遍。明白了 不妨再读读他那个
讲解
感觉先是打出富裕分配空间，然后再找合适的抵制 |
P**********c
发帖数: 3417 | 3 能解释下
p2 = (void**) (((size_t)(p1)+offset) & ~(alignment-1))
这句吗？前面的code基本上是说申请大小是
required_byes+offset大小的memory, p1指向这块memory.
我能理解这句把p2 转化成了alignment的倍数。保留了高位，把alignment之后的bit都设成0。但是这样p2指向的还是required_bytes大小的memory吗？
感觉p1+offset指向的才是required_bytes大小的memory啊。&之后还是吗？
还有p2[-1]，这种情况下是p2前面多少byte？
【在 t**r 的大作中提到】
: 两个* 是相当于C++里的& 传引用。
: 用指针给指针复制，必须这么做。
: 关于地址，我看书了。条目1的解释还算可以，我读了3遍。明白了 不妨再读读他那个
: 讲解
: 感觉先是打出富裕分配空间，然后再找合适的抵制
|
c****p
发帖数: 6474 | 4 &(p2[-1])=p2 - sizeof(void *);
都设成0。但是这样p2指向的还是required_bytes大小的memory吗？
【在 P**********c 的大作中提到】
: 能解释下
: p2 = (void**) (((size_t)(p1)+offset) & ~(alignment-1))
: 这句吗？前面的code基本上是说申请大小是
: required_byes+offset大小的memory, p1指向这块memory.
: 我能理解这句把p2 转化成了alignment的倍数。保留了高位，把alignment之后的bit都设成0。但是这样p2指向的还是required_bytes大小的memory吗？
: 感觉p1+offset指向的才是required_bytes大小的memory啊。&之后还是吗？
: 还有p2[-1]，这种情况下是p2前面多少byte？
|
d*******l
发帖数: 338 | 5 我不敢说完全明白，但有点感觉，谈谈我得想法。
就像上面说的，为了保证能返回一个对齐的地址且有足够的空间，需要打出一些富裕。
多少富裕足够呢？就是代码里的offset。我记得在OS课上老师提到过这种做法，好像叫
container，就是比实际需要多分配空间，把中间开始的某个地址返回，前面的地方存
放些信息。
下面说说offset怎么来的。假设我们用malloc分配了一段空间，起始地址是p1。此时我
们想得到一个对齐的地址，最直接的做法就是& ~(alignment-1)，这样低位清0，结果
就是对齐的。但这样做的结果相当于把原地址减去了一个[0, alignment-1]的数，也就
是低位被减掉了。得到的新地址的开始的一部分就是未分配的。代码中对p2进行这个操
作，得到的结果是p2=p1+offset-x，x就是在对齐过程中被减掉的数，可以看出p2>=p1+
1，这就保证了对齐之后的地址也是分配过的。
再说说p2[-1]=p1的作用。上面说的container方法有一个需要注意的就是free的时候，
如果直接free alloc返回的那个地址，其实是有问题的，因为那个是最初分配空间的中
间的某个地址。所以要有个机制记录原始分配空间的开始位置。代码里的做法是把p1放
在返回值p2之前一个位置。这样不会影响对p2之后地址的操作，在free的时候也能很容
易找到应该free的地址。这也解释了为什么p2要定义成void **，这样p2[-1]=p1这样的
写法才是合法的。但其实p2的意义就是一个地址，所以返回的时候不用特别处理。这样
定义我觉得就是为了方便，如果p2是void *，那可能就要写成这样：
void ** p3 = (void **)(p2-4);
*p3 = p1;
反正目的就是把p1的值放在p2之前的那个位置。这也解释了为什么offset = alignment
-1+sizeof(void*);里的sizeof(void*)。要把p1的位置也给留出来。
free的时候其实可以写做两步：
void ** p3 = (void**)(p-4);
free(*p3);
其实((void**)p)[-1]的值就是alloc里面的p1。p转化为void **还是为了可以直接写p[
-1]这种写法。
欢迎指正。
and
【在 P**********c 的大作中提到】
: 16.9 Write an aligned malloc & free function that takes number of bytes and
: aligned byte (which is always power of 2)
: Example
: align_malloc(1000, 128) will return a memory address that is a multiple of
: 128 and that points to memory of size 1000 bytes.
: aligned_free() will free memory allocated by align_malloc.
: 答案：
: void* aligned_malloc(size_t required bytes, size_t alignment){
: void* p1; //original block
: void** p2; //aligned block
|
c****p
发帖数: 6474 | 6 差不多就是这样吧
p1+
【在 d*******l 的大作中提到】
: 我不敢说完全明白，但有点感觉，谈谈我得想法。
: 就像上面说的，为了保证能返回一个对齐的地址且有足够的空间，需要打出一些富裕。
: 多少富裕足够呢？就是代码里的offset。我记得在OS课上老师提到过这种做法，好像叫
: container，就是比实际需要多分配空间，把中间开始的某个地址返回，前面的地方存
: 放些信息。
: 下面说说offset怎么来的。假设我们用malloc分配了一段空间，起始地址是p1。此时我
: 们想得到一个对齐的地址，最直接的做法就是& ~(alignment-1)，这样低位清0，结果
: 就是对齐的。但这样做的结果相当于把原地址减去了一个[0, alignment-1]的数，也就
: 是低位被减掉了。得到的新地址的开始的一部分就是未分配的。代码中对p2进行这个操
: 作，得到的结果是p2=p1+offset-x，x就是在对齐过程中被减掉的数，可以看出p2>=p1+
|
P**********c
发帖数: 3417 | 7 非常感谢。
仔细看了一遍，有一点还是不太懂，就是p1+offset-x, x可以是0～alignment-1, 怎么能保证这个指的是required_bytes呢？只能保证它指的是>=required_bytes吧。
p1+
【在 d*******l 的大作中提到】
: 我不敢说完全明白，但有点感觉，谈谈我得想法。
: 就像上面说的，为了保证能返回一个对齐的地址且有足够的空间，需要打出一些富裕。
: 多少富裕足够呢？就是代码里的offset。我记得在OS课上老师提到过这种做法，好像叫
: container，就是比实际需要多分配空间，把中间开始的某个地址返回，前面的地方存
: 放些信息。
: 下面说说offset怎么来的。假设我们用malloc分配了一段空间，起始地址是p1。此时我
: 们想得到一个对齐的地址，最直接的做法就是& ~(alignment-1)，这样低位清0，结果
: 就是对齐的。但这样做的结果相当于把原地址减去了一个[0, alignment-1]的数，也就
: 是低位被减掉了。得到的新地址的开始的一部分就是未分配的。代码中对p2进行这个操
: 作，得到的结果是p2=p1+offset-x，x就是在对齐过程中被减掉的数，可以看出p2>=p1+
|
c****p
发帖数: 6474 | 8 后面不是与alignmemt - 1相与把低位置0了么
么能保证这个指的是required_bytes呢？只能保证它指的是>=required_bytes吧。
【在 P**********c 的大作中提到】
: 非常感谢。
: 仔细看了一遍，有一点还是不太懂，就是p1+offset-x, x可以是0～alignment-1, 怎么能保证这个指的是required_bytes呢？只能保证它指的是>=required_bytes吧。
:
: p1+
|
P**********c
发帖数: 3417 | 9 底位抵0是为了让它变成alignment的倍数，但是就是因为低位抵0，它减掉了一个x，x的范围是［0, alignment-1], 我觉得在减掉x之前，它刚好指向一片required_bytes的memory。减掉x之后，它指向的是一片required_bytes+x的memory.
【在 c****p 的大作中提到】
: 后面不是与alignmemt - 1相与把低位置0了么
:
: 么能保证这个指的是required_bytes呢？只能保证它指的是>=required_bytes吧。
|
c****p
发帖数: 6474 | 10 多开是安全的，少开是不安全的
x的范围是［0, alignment-1], 我觉得在减掉x之前，它刚好指向一片required_bytes
的memory。减掉x之后，它指向的是一片required_bytes+x的memory.
【在 P**********c 的大作中提到】
: 底位抵0是为了让它变成alignment的倍数，但是就是因为低位抵0，它减掉了一个x，x的范围是［0, alignment-1], 我觉得在减掉x之前，它刚好指向一片required_bytes的memory。减掉x之后，它指向的是一片required_bytes+x的memory.
|
d*******l
发帖数: 338 | 11 你的意思是分配的空间并非正好是required_bytes，我觉得你说的是对的。
不过这应该不是问题，用户需要required_bytes，只要保证他确实有这么多可用就行。
多余的那些最多损失些内存的利用率。这应该是可以接受的行为。
事实上操作系统中的内存管理往往也不是分配正好的吧？有人了解的话可以说说是怎么
操作的。
x的范围是［0, alignment-1], 我觉得在减掉x之前，它刚好指向一片required_bytes
的memory。减掉x之后，它指向的是一片required_bytes+x的memory.
【在 P**********c 的大作中提到】
: 底位抵0是为了让它变成alignment的倍数，但是就是因为低位抵0，它减掉了一个x，x的范围是［0, alignment-1], 我觉得在减掉x之前，它刚好指向一片required_bytes的memory。减掉x之后，它指向的是一片required_bytes+x的memory.
|
M**A
发帖数: 78 | 12 总结各位评论，欢迎拍砖。
题目
align_malloc(1000, 128) will return a memory address that is a multiple of
128 and that points to memory of size 1000 bytes.
aligned_free() will free memory allocated by align_malloc.
解答
int offset = alignment-1+sizeof(void*);//分配空间给a memory address that is
a multiple of 128
这个offset的空间用来存放memory address，就是*p1 that points to memory of
size 1000 bytes
p1 = (void*)malloc(required_bytes+offset)) //分配空间给memory of size 1000
bytes+memory address that is a multiple of
128， required_bytes=1000 ，alignment = 128
p2=(void**) (((size_t)(p1)+offset) & ~(alignment-1));//用指针给指针复制,将
memory address that is a multiple of
128设置为0，就是说，分配给a memory address that is a multiple of 128的空间设
置为0
p2[-1]=p1;//将p1指针存放在分配给a memory address that is a multiple of 128的
空间，就是说，设置为0的空间存放p1指针
free(((void**)p)[-1];//p就是p2，可看成free(((void**)p2)[-1]; 将p1指针指向的
memory of size 1000 bytes释放 |
h**********8
发帖数: 267 | |
