0%

上一篇提到过,第二级 alloc 在分配大于 128 bytes 的时候,直接使用第一级 alloc,如果小于 128 bytes 才采用内存池的方式进行内存分配。

分配过程是这样的,每次分配一大块内存,存到一个 free list 中,下次 client 若再有相同大小的内存要求,就直接从这个 free list 中划出,内存释放时,则直接回收到对应的 list 中。为了管理的方便,实际分配的大小都被调整为 8 的倍数,所以有 16 个 free lists,分别为 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128 bytes。例如需要 20 bytes,将会被自动调整为 24 bytes。free lists 的结构如下

1
2
3
4
5
6
7
8
9
10
11
enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN

union _Obj {
union _Obj* _M_free_list_link;
char _M_client_data[1]; /* The client sees this. */
};

private:
static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];

为了节省内存使用,使用 union 结构,这个设计很巧妙,每一个元素(内存区域对象)即可以当作下一个元素的指针,例如后面代码中的 result -> _M_free_list_link,也可以当作该元素的值,例如 *__my_free_list。整个 free lists 的结构便是一串使用后者的元素构成的节点,每个节点的值是使用前者构成的单向链表的首地址。

首先来看 allocate 的过程

Read more »

在分析了对象的构建和析构之后,我们接着看对象构建所基于的内存空间是如何分配和释放的。这一功能是由 stl_alloc 提供的。之前提到过 allocate,在 SGI STL 中是不使用的,因为其只是对 new 和 delete 进行了简单的封装,并且加上了这段代码

1
set_new_handler(0);

这个函数用来指定如果内存分配失败时的 callback 函数,定义如下

1
2
typedef void (*new_handler)();
new_handler set_new_handler(new_handler p) throw();

使用时参数传入 NULL(0) 则表示卸除 new_handler,也就意味着如果 ::operator new 分配内存失败,则会抛出 std::bad_alloc 类型的异常。

Read more »

在做单元测试过程中,经常需要对被测程序的一些函数实现 stub,下面三个文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// product.c
#include <stdio.h>
void lib_pro()
{
printf("I'm in lib\n");
}
// user.c
int main(int argc, char *argv[])
{
lib_pro();
return 0;
}
// stub.c
#include <stdio.h>
void lib_pro()
{
printf("I am in fake lib\n");
}

product.c 为产品代码提供 lib_pro 函数,user.c 为使用者,可以当作 UT 测试函数,stub.c 提供 lib_pro 函数的另一个定义。

通常,为了使用 stub,需要在测试时将 user.c 产生的 user.o 和 stub.c 产生的 stub.o 链接在一起,这样,每当要给某一个文件加 stub 时,都需要替换链接,有没有什么办法可以自动进行这一工作,如果有 stub,就链接 stub,如果没有,就链接产品代码。

当然有,

Read more »

使用 Emacs 大概也有大半年了,越用越觉得它的强大,始终都有惊喜,每次看到一个功能,心中想:Emacs 可以吗?答案真的往往会是 Yes!

1
2
3
4
(defun factorial (n)
(if (<= n 1)
1
(* n (factorial (- n 1)))))

上面这种充满括号的奇怪的语言叫 Lisp,它是仅次于 Fortran 的最老的高级程序设计语言,名称来源于 LISt Processing,它有两个方言,分别是 Common Lisp 和 Scheme。 Emacs lisp (elisp) 来源于 Common Lisp。使用 Emacs,如果不能自己打造适合自己的功能,虽然仍然可以享受 Emacs 带来的流畅和便利,但却会与另一种乐趣失之交臂,这篇文章简要叙述 elisp 的基本概念和语法。

Hello World

1
(message "Hello, World!")
Read more »

C++中,我们熟悉的对象的创建和释放过程如下:

1
2
3
4
5
6
7
8
9
class Thing
{
...
};

...

Thing *pt = new Thing;
delete pt;

代码中 new 完成两部分动作,1. 调用 ::operator new 分配对象所占内存空间,2. 调用 Thing 构造函数初始化对象内容。delete 也完成两部分动作,1. 调用析构函数清除对象内容,2. 调用 ::operator delete 释放内存空间。

STL 将这两部分动作分离了开来,内存分配由 alloc:allocate() 负责,释放由 alloc:deallocate() 负责,对象构造和析构依次由 ::contruct()::destroy() 负责。

具体实现位于 stl_alloc.h, stl_contruct.h, stl_uninitialized.h 中,stl_alloc.h 负责内存分配,stl_contruct.h 负责对象构建和析构,stl_uninitialized.h 提供一系列全局函数来进行内存填充 (fill) 和拷贝 (copy)。其实 alloc 并不符合标准规范,而应该是 allocator,位于 stl_defalloc.h 中。

Read more »

1
2
3
4
5
6
7
template <class Iterator, class T>
Iterator find(Iterator first, Iterator last, const T& value)
{
while (first != last && *first != value)
++first;
return first;
}

上面是 C++ 中一个普通的模板函数,调用的时候直接将特定类型变量当参数传入就行,这段程序运用了 Generic Programming(泛型编程/GP)。

GP 要求函数尽量一般化,假设参数可适用于任何范畴,那么函数 find 到底有多一般化?

输入条件,对于类型 Iterator,首先能够以 operator “*” 来操作提取其指向区域的值,并且可以用 operator “++” 来移至下一个 Iterator 对象…

为了表示输入条件,假定 Iterator 必须是一个 iterator,在这个地方 iterator 没有其他意思,只是我们定义出来的一个概念,用来指定一组描述某个类型的条件。

Read more »

印度官方旅游广告词是 Incredible India!

不管之前怎么看待这个国家,身临其境总是会想起这句话,当然语调的不同可以表述截然相反的感受。

Read more »

Paging

Paging unit 用来将 linear address 转换为 physical address,为了高效,linear address 按照一定的长度被分为若干组,称为 pages,并且,内存也被分为各个定长的 page frame (physical pages),page 和 page frame 的长度是一样的,前者表示一块数据,它可以储存在 page frame 或者硬盘中。

在 paging unit 开始工作之前,kernel 先初始化 page tables,这是一个用来映射 linear address 到 physical address 的表。

Linear address 由三部分组成:

  • Directory,10 bits
  • Table,10 bits
  • Offset,12 bits
Read more »

这一个系列将会详细的介绍 Linux kernel 内存管理机制。

使用特定内存地址就可以访问某一块内存单元,为了实现有效的寻址,操作系统将一系列繁琐的操作隐藏了起来,内存地址按照不同的抽象层次分为如下三种:

  1. Logical address: 标识运算符或者程序指令的地址,由段号 (segment selector) 和偏移量 (offset) 组成。
  2. Linear address: 32位的无符号整型数,可以用来表示最大4GB地址空间。
  3. Physical address:内存物理单元的地址。

CPU 控制单元通过 Segmentation Unit 将 Logical address 转换为 Linear address,而后,再通过 paging unit 将 linear address 转换为 physical address,至此,特定地址的访问行为完成。

Segmentation Unit

Read more »