新一代操作系统的构想

当一堆机器通过puppet、pssh这样的软件在管理的时候,你真想,如果它们共同运行一个操作系统,由那个操作系统统一替你协调这些机器该多好,而这个操作系统不能是openstack那种以机器(运行Linux、Windows这样的操作系统的环境)为单位的,而应该是以我的“程序”为单位的。软件架构,不能太过离散。

日志、定时器事件、用户、安装包……为什么不统一规划呢?以前的OS是面向单机的,现在的OS是面向群集的,这可能就是Elastos该出手的地方。

 | 877 views | 0 comments | 2 flags | 

Linux容器演变历程与未来发展前景

http://cloud.51cto.com/art/201602/505113.htm

 

Linux容器作为一类操作系统层面的虚拟化技术成果,旨在立足于单一Linux主机交付多套隔离性Linux环境。与虚拟机不同,容器系统并不需要运行特定的访客操作系统。相反,容器共享同一套主机操作系统内核,同时利用访客操作系统的系统库以交付必要的系统功能。由于无需借助于专门的操作系统,因此容器在启动速度上要远远优于虚拟机。

图片来源:Docker有限公司

容器能够利用Namespaces、Apparmor、SELinux配置、chroot以及CGroups等Linux内核功能,从而交付一套类似于虚拟机的隔离性环境。Linux安全模块能够确保来自容器的主机设备与内核访问行为受到妥善管理,从而避免入侵活动的发生。除此之外,容器还能够通过其主机操作系统运行多种不同Linux发行版——只要各类操作系统拥有同样的底层CPU架构要求。

总体而言,容器技术提供了一种立足于各类Linux发行版的容器镜像创建方式,同时利用API进行容器生命周期管理,通过客户端工具实现与该API的交互,进而提供快照以及不同容器主机之间容器实例迁移等能力。

容器技术发展历程

以下为从维基百科以及其它信息源处收集到的容器发展历程总结:

1979年 — chroot

容器技术的概念可以追溯到1979年的UNIX chroot。这是一套“UNIX操作系统”系统,旨在将其root目录及其它子目录变更至文件系统内的新位置,且只接受特定进程的访问。这项功能的设计目的在于为每个进程提供一套隔离化磁盘空间。1982年其被添加至BSD当中。

2000年 — FreeBSD Jails

FreeBSD Jails是由Derrick T. Woolworth于2000年在FreeBSD研发协会中构建而成的早期容器技术之一。这是一套“操作系统”系统,与chroot的定位类似,不过其中包含有其它进程沙箱机制以对文件系统、用户及网络等资源进行隔离。通过这种方式,它能够为每个Jail、定制化软件安装包乃至配置方案等提供一个对应的IP地址。

2001年 — Linux VServer

Linux VServer属于另一种jail机制,其能够被用于保护计算机系统之上各分区资源的安全(包括文件系统、CPU时间、网络地址以及内存等)。每个分区被称为一套安全背景(security context),而其中的虚拟化系统则被称为一套虚拟私有服务器。

2004年 — Solaris容器

Solaris容器诞生之时面向x86与SPARC系统架构,其最初亮相于2004年2月的Solaris 10 Build 51 beta当中,随后于2005年正式登陆Solaris 10的完整版本。Solaris容器相当于将系统资源控制与由分区提供的边界加以结合。各分区立足于单一操作系统实例之内以完全隔离的虚拟服务器形式运行。

2005年 — OpenVZ

OpenVZ与Solaris容器非常相似,且使用安装有补丁的Linux内核以实现虚拟化、隔离能力、资源管理以及检查点交付。每套OpenVZ容器拥有一套隔离化文件系统、用户与用户群组、一套进程树、网络、设备以及IPC对象。

2006年 — Process容器

Process容器于2006年由谷歌公司推出,旨在对一整套进程集合中的资源使用量(包括CPU、内存、磁盘I/O以及网络等等)加以限制、分配与隔离。此后其被更名为Control Groups(即控制组),从而避免其中的“容器”字眼与Linux内核2.6.24中的另一术语出现冲突。这表明了谷歌公司率先重视容器技术的敏锐眼光以及为其做出的突出贡献。

2007年 — Control Groups

正如上文所提及,Control Groups也就是谷歌实现的cgroups,其于2007年被添加至Linux内核当中。

2008年 — LXC

LXC指代的是Linux Containers,其也是第一套完整的Linux容器管理实现方案。其功能通过cgroups以及Linux namespaces实现。LXC通过liblxc库进行交付,并提供可与Python3、Python2、Lua、Go、Ruby以及Haskell等语言相对接的API。相较于其它容器技术,LXC能够在无需任何额外补丁的前提下运行在原版Linux内核之上。目前LXC项目由Canonical有限公司负责赞助及托管。

2011年 — Warden

Warden由CloudFoundry公司于2011年所建立,其利用LXC作为初始阶段,随后又将其替换为自家实现方案。与LXC不同,Warden并不会与Linux紧密耦合。相反,其能够运行在任意能够提供多种隔离环境方式的操作系统之上。Warden以后台进程方式运行并提供API以实现容器管理。感兴趣的朋友可以点击此处与此处了解更多与Warden相关的细节信息(英文原文)。

2013年 — LMCTFY

Lmctfy代表的是“Let Me Contain That For You(帮你实现容器化)”。它其实属于谷歌容器技术堆栈的开源版本,负责提供Linux应用程序容器。谷歌公司在该项目的起步阶段宣称其能够提供值得信赖的性能表现、高资源利用率、共享资源机制、充裕的发展空间以及趋近于零的额外资源消耗。Kubernetes目前所使用的cAdvisor工具最初就来源于lmctfy项目。2013年10月lmctfy的首个版本正式推出,谷歌公司在2015年决定将lmctfy的核心概念与抽象机制转化为libcontainer。在失去了主干之后,如今lmctfy已经失去一切积极的发展势头。

Libcontainer项目最初由Docker公司建立,如今已经被归入开放容器基金会的管辖范畴。

2013年 — Docker

截至2016年1月,Docker是目前最具人气且应用最为广泛的容器管理系统。Docker项目最初是由一家名为dotCloud的平台即服务厂商所打造,其后该公司更名为Docker。与Warden类似,Docker同样在起步阶段使用LXC,而后利用自己的libcontainer库将其替换下来。与其它容器平台不同,Docker引入了一整套与容器管理相关的生态系统。其中包括一套高效的分层式容器镜像模型、一套全局及本地容器注册表、一个精简化REST API以及一套命令行界面等等。在后期发展阶段,Docker公司还构建起一套名为Docker Swarm的容器集群管理解决方案。

2014年 — Rocket

Rocket最初由CoreOS开发而成,专门用于解决部分Docker当中存在的缺陷。CoreOS方面也提到,他们当初的开发目标是在安全性与生产要求满足能力上超越Docker。更重要的是,其基于App Container规范并使其成为一项更为开放的标准。除了Rocket之外,CoreOS还开发出了多种其它与容器相关的产品,且已经被Docker与Kubernetes所使用:CoreOS操作系统、etcd以及flannel。

2016年 — Windows容器

微软公司也已经于2015年采取初步举措,希望将容器支持能力添加到微软Windows Server操作系统当中,而这项旨在帮助Windows应用实现容器化的项目被称为Windows容器(Windows Containers)。其即将随微软的Windows Server 2016一同推出。在这硕方案当中,Docker能够以原生方式在Windows平台上运行容器,而无需运行虚拟机或者多层Docker(早期Docker需要利用Linux虚拟机才能与Windows系统相对接)。

容器之发展愿景

截至目前(2016年1月),整个技术行业已经越来越多地将软件应用程序部署基础由虚拟机转移向容器。之所以出现这种趋势,一大重要原因在于容器能够提供远优于虚拟机的灵活性与使用成本。谷歌公司多年来一直在利用Borg and Omega容器集群管理平台等容器技术以实现各类谷歌应用的规模化运行。更重要的是,谷歌公司还通过实现cgroups以及参与libcontainer项目等方式为容器技术的发展做出了突出贡献。谷歌方面在过去几年当中已经利用容器技术实现了可观的性能提升、资源利用率改善以及整体执行效率优化。就在最近,微软公司这位从未将任何操作系统层级虚拟化机制引入Windows平台的软件巨头亦快速在Windows Server上实现了原生容器支持能力。

Docker、Rocket以及其它容器平台都无法运行在生产环境中的单一主机之上,这是因为它们都存在着单点故障隐患。尽管一整套容器集合能够运行在单一主机上,然而一旦该主机发生故障,所有运行于其上的容器也将全面瘫痪。谷歌公司在这方面抢先一步,凭借从Borg项目中积累到的经验打造出名为Kubernetes的开源容器集群管理系统。Docker公司也针对这一难题开发出了Docker Swarm解决方案。目前,这些解决方案尚处于早期发展阶段,而且可能还需要数月甚至一年才能真正具备完整的功能集,从而以稳定及广泛的方式被引入容器行业的生产环境当中。

微服务则是另一项突破性技术成果,而不仅仅是一套利用容器机制实现自身部署的软件架构。虽然微服务的概念算不上什么新鲜事物,但这种Web服务的轻量化实现机制确实能够提供远超过标准Web服务的启动速度。之所以能够实现这项目标,是因为其将一整套功能单元以打包方式(可能包括单一服务/API方法)整合在一项服务当中,再将服务嵌入一套轻量化Web服务器二进制文件。

考虑到以上背景信息,我们可以预测在未来几年当中,容器技术将逐步取代虚拟机甚至能够在一定程度上彻底占据其适用环境。去年,我曾经帮助多家企业立足于POC层级部署基于容器的解决方案。当时他们几乎还都不想把容器引入生产环境。然而这种状况可能随着容器集群管理系统的逐步成熟而快速得到扭转。

原文标题:The History of Linux Containers from chroot to the Future

【51CTO.com独家译稿,合作站点转载请注明来源】

 | 91 views | 0 comments | 0 flags | 

计算机科学中的最严重错误,造成十亿美元损失

http://blog.jobbole.com/93667/

在 1965 年有人提出了这个计算机科学中最糟糕的错误,该错误比 Windows 的反斜线更加丑陋、比 === 更加怪异、比 PHP 更加常见、比 CORS 更加不幸、比 Java 泛型更加令人失望、比 XMLHttpRequest 更加反复无常、比 C 预处理器更加难以理解、比 MongoDB 更加容易出现碎片问题、比 UTF-16 更加令人遗憾。

“我把 Null 引用称为自己的十亿美元错误。它的发明是在1965 年,那时我用一个面向对象语言( ALGOL W )设计了第一个全面的引用类型系统。我的目的是确保所有引用的使用都是绝对安全的,编译器会自动进行检查。但是我未能抵御住诱惑,加入了Null引用,仅仅是因为实现起来非常容易。它导致了数不清的错误、漏洞和系统崩溃,可能在之后 40 年中造成了十亿美元的损失。近年来,大家开始使用各种程序分析程序,比如微软的 PREfix 和 PREfast 来检查引用,如果存在为非 Null 的风险时就提出警告。更新的程序设计语言比如 Spec# 已经引入了非 Null 引用的声明。这正是我在1965年拒绝的解决方案。” —— 《Null References: The Billion Dollar Mistake》托尼·霍尔(Tony Hoare),图灵奖得主

为纪念 Hoare 先生的 null 错误五十周年,这篇文章将会解释何为 null、为什么它这么可怕以及如何避免。

NULL 怎么了?

简单来说:NULL 是一个不是值的值。那么问题来了。

这个问题已经在有史以来最流行的语言中恶化,而它现在有很多名字:NULL、nil、null、None、Nothing、Nil 和 nullptr。每种语言都有自己的细微差别。

NULL 导致的问题,有一些只涉及某种特定的语言,而另一些则是普遍存在的;少量只是某个问题的不同方面。

NULL…

  1. 颠覆类型
  2. 是凌乱的
  3. 是一个特例
  4. 使 API 变得糟糕
  5. 使错误的语言决策更加恶化
  6. 难以调试
  7. 是不可组合的

1. NULL 颠覆类型

静态类型语言不需要实际去执行程序,就可以检查程序中类型的使用,并且提供一定的程序行为保证。

例如,在 Java 中,如果我编写 x.toUppercase(),编译器会检查 x 的类型。如果 x 是一个String,那么类型检查成功;如果 x 是一个 Socket,那么类型检查失败。

在编写庞大的、复杂的软件时,静态类型检查是一个强大的工具。但是对于 Java,这些很棒的编译时检查存在一个致命缺陷:任何引用都可以是 null,而调用一个 null 对象的方法会产生一个 NullPointerException。所以,

  • toUppercase() 可以被任意 String 对象调用。除非 String 是 null。
  • read() 可以被任意 InputStream 对象调用。除非 InputStream 是 null。
  • toString() 可以被任意 Object 对象调用。除非 Object 是 null。

Java 不是唯一引起这个问题的语言;很多其它的类型系统也有同样的缺点,当然包括 AGOL W 语言。

在这些语言中,NULL 超出了类型检查的范围。它悄悄地越过类型检查,等待运行时,最后一下子释放出一大批错误。NULL 什么也不是,同时又什么都是。

2. NULL 是凌乱的

在很多情况下 null 是没有意义的。不幸的是,如果一种语言允许任何东西为 null,好吧,那么任何东西都可以是 null。

Java 程序员冒着患腕管综合症的风险写下

1
2
if (str == null || str.equals("")) {
}

而在 C# 中添加 String.IsNullOrEmpty 是一个常见的语法

1
2
if (string.IsNullOrEmpty(str)) {
}

真可恶!

每次你写代码,将 null 字符串和空字符串混为一谈时,Guava 团队都要哭了。– Google Guava

说得好。但是当你的类型系统(例如,Java 或者 C#)到处都允许 NULL 时,你就不能可靠地排除 NULL 的可能性,并且不可避免的会在某个地方混淆。

null 无处不在的可能性造成了这样一个问题,Java 8 添加了 @NonNull 标注,尝试着在它的类型系统中以追溯方式解决这个缺陷。

3. NULL 是一个特例

考虑到 NULL 不是一个值却又起到一个值的作用,NULL 自然地成为各种特别处理方法的课题。

指针

例如,请看下面的 C++ 代码:

1
2
3
char c = 'A';
char *myChar = &c;
std::cout << *myChar << std::endl;

myChar 是一个 char *,意味着它是一个指针——即,将一个内存地址保存到一个 char中。编译器会对此进行检验。因此,下面的代码是无效的:

1
2
char *myChar = 123; // compile error
std::cout << *myChar << std::endl;

因为 123 不保证是一个 char 的地址,所以编译失败。无论如何,如果我们将数字改为0(在 C++ 中 0 是 NULL),那么可以编译通过:

1
2
char *myChar = 0;
std::cout << *myChar << std::endl; // runtime error

和 123 一样,NULL 实际上不是一个 char 的地址。但是这次编译器还是允许它编译通过,因为 0(NULL)是一个特例。

字符串

还有另一个特例,即发生在 C 语言中以 NULL 结尾的字符串。这与其它的例子有点不同,因为这里没有指针或者引用。但是不是一个值却又起到一个值的作用这个思想还在,此处以不是一个 char 却起到一个 char 的形式存在。

一个 C 字符串是一连串的字节,并且以 NUL (0) 字节结尾。

C-string

因此,C 字符串的每个字符可以是 256 个字节中的任意一个,除了 0(即 NUL 字符)。这不仅使得字符串长度成为一个线性时间的运算;甚至更糟糕,它意味着 C 字符串不能用于 ASCII 或者扩展的 ASCII。相反,它们只能用于不常用的 ASCIIZ。

单个 NUL 字符的例外已经导致无数的错误:API 的怪异行为、安全漏洞和缓冲区溢出。

NULL 是 C 字符串中最糟糕的错误;更确切地说,以 NUL 结尾的字符串是最昂贵的一字节错误

4. NULL 使 API 变得糟糕

下一个例子,我们将会踏上旅程前往动态类型语言的王国,在那里 NULL 将再一次证明它是一个可怕的错误。

键值存储

假设我们创建一个 Ruby 类充当一个键值存储。这可能是一个缓存、一个用于键值数据库的接口等等。我们将会创建简单通用的 API:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Store
    ##
    # associate key with value
    #
    def set(key, value)
        ...
    end
    ##
    # get value associated with key, or return nil if there is no such key
    #
    def get(key)
        ...
    end
end

我们可以想象在很多语言中类似的类(Python、JavaScript、Java、C# 等)。

现在假设我们的程序有一个慢的或者占用大量资源的方法,来找到某个人的电话号码——可能通过连通一个网络服务。

为了提高性能,我们将会使用本地存储作为缓存,将一个人名映射到他的电话号码上。

1
2
3
4
store = Store.new()
store.set('Bob', '801-555-5555')
store.get('Bob') # returns '801-555-5555', which is Bob’s number
store.get('Alice') # returns nil, since it does not have Alice

然而,一些人没有电话号码(即他们的电话号码是 nil)。我们仍然会缓存那些信息,所以我们不需要在后面重新填充那些信息。

1
2
3
store = Store.new()
store.set('Ted', nil) # Ted has no phone number
store.get('Ted') # returns nil, since Ted does not have a phone number

但是现在意味着我们的结果模棱两可!它可能表示:

  1. 这个人不存在于缓存中(Alice)
  2. 这个人存在于缓存中,但是没有电话号码(Tom)

一种情形要求昂贵的重新计算,另一种需要即时的答复。但是我们的代码不够精密来区分这两种情况。

在实际的代码中,像这样的情况经常会以复杂且不易察觉的方式出现。因此,简单通用的 API 可以马上变成特例,迷惑了 null 凌乱行为的来源。

用一个 contains() 方法来修补 Store 类可能会有帮助。但是这引入重复的查找,导致降低性能和竞争条件。

双重麻烦

JavaScript 有相同的问题,但是发生在每个单一的对象

如果一个对象的属性不存在,JS 会返回一个值来表示该对象缺少属性。JavaScript 的设计人员已经选择了此值为 null。

然而他们担心的是当属性存在并且该属性被设为 null 的情况。“有才”的是,JavaScript 添加了 undefined 来区分值为 null 的属性和不存在的属性。

但是如果属性存在,并且它的值被设为 undefined,将会怎样?奇怪的是,JavaScript 在这里停住了,没有提供“超级 undefined”。

JavaScript 提出了不仅一种,而是两种形式的 NULL。

5. NULL 使错误的语言决策更加恶化

Java 默默地在引用和主要类型之间转换。加上 null,事情变得更加奇怪。

例如,下面的代码编译不过:

1
int x = null; // compile error

这段代码则编译通过:

1
2
Integer i = null;
int x = i; // runtime error

虽然当该代码运行时会报出 NullPointerException 的错误。

成员方法调用 null 是够糟糕的;当你从未见过该方法被调用时更糟糕。

6. NULL 难以调试

来解释 NULL 是多么的麻烦,C++ 是一个很好的例子。调用成员函数指向一个 NULL 指针不一定会导致程序崩溃。更糟糕的是:它可能会导致程序崩溃。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
struct Foo {
    int x;
    void bar() {
        std::cout << "La la la" << std::endl;
    }
    void baz() {
        std::cout << x << std::endl;
    }
};
int main() {
    Foo *foo = NULL;
    foo->bar(); // okay
    foo->baz(); // crash
}

当我用 gcc 编译上述代码时,第一个调用是成功的;第二个则是失败的。

为什么?foo->bar() 在编译时是已知的,所以编译器避免一个运行时虚表查找,并将它转换成一个静态调用,类似 Foo_bar(foo),以此为第一个参数。由于 bar 没有间接引用 NULL 指针,所以它成功运行。但是 baz 有引用 NULL 指针,所以导致一个段错误。

但是解设我们将 bar 变成虚函数。这意味着它的实现可能会被一个子类重写。

1
2
3
...
virtual void bar() {
...

作为一个虚函数,foo->bar() 为 foo 的运行时类型做虚表查找,以防 bar() 被重写。由于foo 是 NULL,现在的程序会在 foo->bar() 这句崩溃,这全都是因为我们把该函数变成虚函数了。

1
2
3
4
5
int main() {
    Foo *foo = NULL;
    foo->bar(); // crash
    foo->baz();
}

NULL 已经使得 main 函数的程序员调试这段代码变得非常困难和不直观。

的确,在 C++ 标准中没有定义引用 NULL,所以技术上我们不应该对发生的任何情况感到惊讶。还有,这是一个非病态的、常见的、十分简单的、真实的例子,这个例子是在实践中 NULL 变化无常的众多例子中的一个。

7. NULL 是不可组合的

程序语言是围绕着可组合性构建的:即将一个抽象应用到另一个抽象的能力。这可能是任何语言、库、框架、模型、API 或者设计模式的一个最重要的特征:正交地使用其它特征的能力。

实际上,可组合性确实是很多这类问题背后的基本问题。例如,Store API 返回 nil 给不存在的值与存储 nil 给不存在的电话号码之间不具有可组合性。

C# 用 Nullable 来处理一些关于 NULL 的问题。你可以在类型中包括可选性(为空性)。

1
2
3
int a = 1;     // integer
int? b = 2;    // optional integer that exists
int? c = null; // optional integer that does not exist

但是这造成一个严重的缺陷,那就是 Nullable 不能应用于任何的 T。它仅仅能应用于非空的 T。例如,它不会使 Store 的问题得到任何改善。

  1. 首先 string 可以是空的;你不能创建一个不可空的 string
  2. 即使 string 是不可空的,以此创建 string?可能吧,但是你仍然无法消除目前情况的歧义。没有 string??

解决方案

NULL 变得如此普遍以至于很多人认为它是有必要的。NULL 在很多低级和高级语言中已经出现很久了,它似乎是必不可少的,像整数运算或者 I/O 一样。

不是这样的!你可以拥有一个不带 NULL 的完整的程序语言。NULL 的问题是一个非数值的值、一个哨兵、一个集中到其它一切的特例。

相反,我们需要一个实体来包含一些信息,这些信息是关于(1)它是否包含一个值和(2)已包含的值,如果存在已包含的值的话。并且这个实体应该可以“包含”任意类型。这是 Haskell 的 Maybe、Java 的 Optional、Swift 的 Optional 等的思想。

例如,在 Scala 中,Some[T] 保存一个 T 类型的值。None 没有值。这两个都是 Option[T]的子类型,这两个子类型可能保存了一个值,也可能没有值。

不熟悉 Maybes/Options 的读者可能会想我们已经把一种没有的形式(NULL)替代为另一种没有的形式(None)。但是这有一个不同点——不易察觉,但是至关重要。

在一种静态类型语言中,你不能通过替代 None 为任意值来绕过类型系统。None 只能用在我们期望一个 Option 出现的地方。可选性显式地表现于类型中。

而在动态类型语言中,你不能混淆 Maybes/Options 和已包含值的用法。

让我们回到先前的 Store,但是这次可能使用 ruby。如果存在一个值,则 Store 类返回带有值的 Some,否则反回 None。对于电话号码,Some 是一个电话号码,None 代表没有电话号码。因此有两级的存在/不存在:外部的 Maybe 表示存在于 Store 中;内部的 Maybe 表示那个名字对应的电话号码。我们已经成功组合了多个 Maybe,这是我们无法用 nil 做到的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
cache = Store.new()
cache.set('Bob', Some('801-555-5555'))
cache.set('Tom', None())
bob_phone = cache.get('Bob')
bob_phone.is_some # true, Bob is in cache
bob_phone.get.is_some # true, Bob has a phone number
bob_phone.get.get # '801-555-5555'
alice_phone = cache.get('Alice')
alice_phone.is_some # false, Alice is not in cache
tom_phone = cache.get('Tom')
tom_phone.is_some # true, Tom is in cache
tom_phone.get.is_some #false, Tom does not have a phone number

本质的区别是不再有 NULL 和其它任何类型之间的联合——静态地类型化或者动态地假设,不再有一个存在的值和不存在的值之间的联合。

使用 Maybes/Options

让我们继续讨论更多没有 NULL 的代码。假设在 Java 8+ 中,我们有一个整数,它可能存在,也可能不存在,并且如果它存在,我们就把它打印出来。

1
2
3
4
Optional<Integer> option = ...
if (option.isPresent()) {
   doubled = System.out.println(option.get());
}

这样很好。但是大多数的 Maybe/Optional 实现,包括 Java,支持一种更好的实用方法:

1
2
option.ifPresent(x -> System.out.println(x));
// or option.ifPresent(System.out::println)

不仅因为这种实用的方法更加简洁,而且它也更加安全。需要记住如果该值不存在,那么 option.get() 会产生一个错误。在早些时候的例子中,get() 受到一个 if 保护。在这个例子中,ifPresent() 完全省却了我们对 get() 的需要。它使得代码明显地没有 bug,而不是没有明显的 bug。

Options 可以被认为是一个最大值为 1 的集合。例如,如果存在值,那么我们可以将该值乘以 2,否则让它空着。

1
option.map(x -> 2 * x)

我们可以可选地执行一个运算,该运算返回一个可选的值,并且使结果趋于“扁平化”。

1
option.flatMap(x -> methodReturningOptional(x))

如果 none 存在,我们可以提供一个默认的值:

1
option.orElseGet(5)

总的来说,Maybe/Option 真正的价值是

  1. 降低关于值存在和不存在的不安全的假设
  2. 更容易安全地操作可选的数据
  3. 显式地声明任何不安全的存在假设(例如,.get() 方法)

不要 NULL!

NULL 是一个可怕的设计缺陷,一种持续不断地、不可估量的痛苦。只有很少语言设法避免它的可怕。

如果你确实选择了一种带 NULL 的语言,那么至少要有意识地在你自己的代码中避免这种不快,并使用等效的 Maybe/Option

常用语言中的 NULL:

“分数”是根据下面的标准来定的:

编辑

评分

对于上述表格的“评分”不要太认真。真正的问题是总结各种语言 NULL 的状态和介绍 NULL 的替代品,并不是为了把常用的语言分等级。

部分语言的信息已经被修正过。出于运行时兼容性的原因,一些语言会有某种 null 指针,但是它们对于语言自身并没有实际的用处。

  • 例子:Haskell 的 Foreign.Ptr.nullPtr 被用于 FFI(Foreign Function Interface),给 Haskell 编组值和从 Haskell 中编组值。
  • 例子:Swift 的 UnsafePointer 必须与 unsafeUnwrap 或者 ! 一起使用。
  • 反例:Scala,尽管习惯性地避免 null,仍然与 Java 一样对待 null,以增强互操作。val x: String = null

什么时候 NULL 是 OK 的?

值得说明的是,当减少 CPU 周期时,一个大小一致的特殊值,像 0 或者 NULL 可以很有用,用代码质量换取性能。当这真正重要的时候,它对于那些低级语言很方便,像 C,但是它真应该离开那里。

真正的问题

NULL 更加常见的问题是哨兵值:这些值与其它值一样,但是有着完全不同的含义。从 indexOf 返回一个整数的索引或者整数 -1 是一个很好的示例。以 NULL 结尾的字符串是另一个例子。这篇文章主要关注 NULL,给出它的普遍性和真实的影响,但是正如 Sauron 仅仅是 Morgoth 的仆人,NULL 也仅仅是基本的哨兵问题的一种形式。

 | 282 views | 0 comments | 0 flags | 

推荐!国外程序员整理的 C++ 资源大全

http://blog.jobbole.com/78901/

关于 C++ 框架、库和资源的一些汇总列表,由 fffaraz 发起和维护。

内容包括:标准库、Web应用框架、人工智能、数据库、图片处理、机器学习、日志、代码分析等。

 

标准库

C++标准库,包括了STL容器,算法和函数等。

 

框架

C++通用框架和库

  • Apache C++ Standard Library:是一系列算法,容器,迭代器和其他基本组件的集合
  • ASL :Adobe源代码库提供了同行的评审和可移植的C++源代码库。
  • Boost :大量通用C++库的集合。
  • BDE :来自于彭博资讯实验室的开发环境。
  • Cinder:提供专业品质创造性编码的开源开发社区。
  • Cxxomfort:轻量级的,只包含头文件的库,将C++ 11的一些新特性移植到C++03中。
  • Dlib:使用契约式编程和现代C++科技设计的通用的跨平台的C++库。
  • EASTL :EA-STL公共部分
  • ffead-cpp :企业应用程序开发框架
  • Folly:由Facebook开发和使用的开源C++库
  • JUCE :包罗万象的C++类库,用于开发跨平台软件
  • libPhenom:用于构建高性能和高度可扩展性系统的事件框架。
  • LibSourcey :用于实时的视频流和高性能网络应用程序的C++11 evented IO
  • LibU : C语言写的多平台工具库
  • Loki :C++库的设计,包括常见的设计模式和习语的实现。
  • MiLi :只含头文件的小型C++库
  • openFrameworks :开发C++工具包,用于创意性编码。
  • Qt :跨平台的应用程序和用户界面框架
  • Reason :跨平台的框架,使开发者能够更容易地使用Java,.Net和Python,同时也满足了他们对C++性能和优势的需求。
  • ROOT :具备所有功能的一系列面向对象的框架,能够非常高效地处理和分析大量的数据,为欧洲原子能研究机构所用。
  • STLport:是STL具有代表性的版本
  • STXXL:用于额外的大型数据集的标准模板库。
  • Ultimate++ :C++跨平台快速应用程序开发框架
  • Windows Template Library:用于开发Windows应用程序和UI组件的C++库
  • Yomm11 :C++11的开放multi-methods.

 

人工智能

  • btsk :游戏行为树启动器工具
  • Evolving Objects:基于模板的,ANSI C++演化计算库,能够帮助你非常快速地编写出自己的随机优化算法。
  • Neu:C++11框架,编程语言集,用于创建人工智能应用程序的多用途软件系统。

 

异步事件循环

  • Boost.Asio:用于网络和底层I/O编程的跨平台的C++库。
  • libev :功能齐全,高性能的时间循环,轻微地仿效libevent,但是不再像libevent一样有局限性,也修复了它的一些bug。
  • libevent :事件通知库
  • libuv :跨平台异步I/O。

 

音频

音频,声音,音乐,数字化音乐库

  • FMOD :易于使用的跨平台的音频引擎和音频内容的游戏创作工具。
  • Maximilian :C++音频和音乐数字信号处理库
  • OpenAL :开源音频库—跨平台的音频API
  • Opus:一个完全开放的,免版税的,高度通用的音频编解码器
  • Speex:免费编解码器,为Opus所废弃
  • Tonic: C++易用和高效的音频合成
  • Vorbis: Ogg Vorbis是一种完全开放的,非专有的,免版税的通用压缩音频格式。

 

生态学

生物信息,基因组学和生物技术

  • libsequence:用于表示和分析群体遗传学数据的C++库。
  • SeqAn:专注于生物数据序列分析的算法和数据结构。
  • Vcflib :用于解析和处理VCF文件的C++库
  • Wham:直接把联想测试应用到BAM文件的基因结构变异。

 

压缩

压缩和归档库

  • bzip2:一个完全免费,免费专利和高质量的数据压缩
  • doboz:能够快速解压缩的压缩库
  • PhysicsFS:对各种归档提供抽象访问的库,主要用于视频游戏,设计灵感部分来自于Quake3的文件子系统。
  • KArchive:用于创建,读写和操作文件档案(例如zip和 tar)的库,它通过QIODevice的一系列子类,使用gzip格式,提供了透明的压缩和解压缩的数据。
  • LZ4 :非常快速的压缩算法
  • LZHAM :无损压缩数据库,压缩比率跟LZMA接近,但是解压缩速度却要快得多。
  • LZMA :7z格式默认和通用的压缩方法。
  • LZMAT :及其快速的实时无损数据压缩库
  • miniz:单一的C源文件,紧缩/膨胀压缩库,使用zlib兼容API,ZIP归档读写,PNG写方式。
  • Minizip:Zlib最新bug修复,支持PKWARE磁盘跨越,AES加密和IO缓冲。
  • Snappy :快速压缩和解压缩
  • ZLib :非常紧凑的数据流压缩库
  • ZZIPlib:提供ZIP归档的读权限。

 

并发性

并发执行和多线程

  • Boost.Compute :用于OpenCL的C++GPU计算库
  • Bolt :针对GPU进行优化的C++模板库
  • C++React :用于C++11的反应性编程库
  • Intel TBB :Intel线程构件块
  • Libclsph:基于OpenCL的GPU加速SPH流体仿真库
  • OpenCL :并行编程的异构系统的开放标准
  • OpenMP:OpenMP API
  • Thrust :类似于C++标准模板库的并行算法库
  • HPX :用于任何规模的并行和分布式应用程序的通用C++运行时系统
  • VexCL :用于OpenCL/CUDA 的C++向量表达式模板库。

 

容器

  • C++ B-tree :基于B树数据结构,实现命令内存容器的模板库
  • Hashmaps: C++中开放寻址哈希表算法的实现

 

密码学

  • Bcrypt :一个跨平台的文件加密工具,加密文件可以移植到所有可支持的操作系统和处理器中。
  • BeeCrypt
  • Botan: C++加密库
  • Crypto++:一个有关加密方案的免费的C++库
  • GnuPG: OpenPGP标准的完整实现
  • GnuTLS :实现了SSL,TLS和DTLS协议的安全通信库
  • Libgcrypt
  • libmcrypt
  • LibreSSL:免费的SSL/TLS协议,属于2014 OpenSSL的一个分支
  • LibTomCrypt:一个非常全面的,模块化的,可移植的加密工具
  • libsodium:基于NaCI的加密库,固执己见,容易使用
  • Nettle 底层的加密库
  • OpenSSL : 一个强大的,商用的,功能齐全的,开放源代码的加密库。
  • Tiny AES128 in C :用C实现的一个小巧,可移植的实现了AES128ESB的加密算法

 

数据库

数据库,SQL服务器,ODBC驱动程序和工具

  • hiberlite :用于Sqlite3的C++对象关系映射
  • Hiredis: 用于Redis数据库的很简单的C客户端库
  • LevelDB: 快速键值存储库
  • LMDB:符合数据库四大基本元素的嵌入键值存储
  • MySQL++:封装了MySql的C API的C++ 包装器
  • RocksDB:来自Facebook的嵌入键值的快速存储
  • SQLite:一个完全嵌入式的,功能齐全的关系数据库,只有几百KB,可以正确包含到你的项目中。

 

调试

调试库, 内存和资源泄露检测,单元测试

  • Boost.Test:Boost测试库
  • Catch:一个很时尚的,C++原生的框架,只包含头文件,用于单元测试,测试驱动开发和行为驱动开发。
  • CppUnit:由JUnit移植过来的C++测试框架
  • CTest:CMake测试驱动程序
  • googletest:谷歌C++测试框架
  • ig-debugheap:用于跟踪内存错误的多平台调试堆
  • libtap:用C语言编写测试
  • MemTrack —用于C++跟踪内存分配
  • microprofile- 跨平台的网络试图分析器
  • minUnit :使用C写的迷你单元测试框架,只使用了两个宏
  • Remotery:用于web视图的单一C文件分析器
  • UnitTest++:轻量级的C++单元测试框架

 

游戏引擎

  • Cocos2d-x :一个跨平台框架,用于构建2D游戏,互动图书,演示和其他图形应用程序。
  • Grit :社区项目,用于构建一个免费的游戏引擎,实现开放的世界3D游戏。
  • Irrlicht :C++语言编写的开源高性能的实时#D引擎
  • Polycode:C++实现的用于创建游戏的开源框架(与Lua绑定)。

 

图形用户界面

  • CEGUI : 很灵活的跨平台GUI库
  • FLTK :快速,轻量级的跨平台的C++GUI工具包。
  • GTK+: 用于创建图形用户界面的跨平台工具包
  • gtkmm :用于受欢迎的GUI库GTK+的官方C++接口。
  • imgui:拥有最小依赖关系的立即模式图形用户界面
  • libRocket :libRocket 是一个C++ HTML/CSS 游戏接口中间件
  • MyGUI :快速,灵活,简单的GUI
  • Ncurses:终端用户界面
  • QCustomPlot :没有更多依赖关系的Qt绘图控件
  • Qwt :用户与技术应用的Qt 控件
  • QwtPlot3D :功能丰富的基于Qt/OpenGL的C++编程库,本质上提供了一群3D控件
  • OtterUI :OtterUI 是用于嵌入式系统和互动娱乐软件的用户界面开发解决方案
  • PDCurses 包含源代码和预编译库的公共图形函数库
  • wxWidgets C++库,允许开发人员使用一个代码库可以为widows, Mac OS X,Linux和其他平台创建应用程序

 

图形

  • bgfx:跨平台的渲染库
  • Cairo:支持多种输出设备的2D图形库
  • Horde3D 一个小型的3D渲染和动画引擎
  • magnum C++11和OpenGL 2D/3D 图形引擎
  • Ogre 3D 用C++编写的一个面向场景,实时,灵活的3D渲染引擎(并非游戏引擎)
  • OpenSceneGraph 具有高性能的开源3D图形工具包
  • Panda3D 用于3D渲染和游戏开发的框架,用Python和C++编写。
  • Skia 用于绘制文字,图形和图像的完整的2D图形库
  • urho3d 跨平台的渲染和游戏引擎。

 

图像处理

  • Boost.GIL:通用图像库
  • CImg :用于图像处理的小型开源C++工具包
  • CxImage :用于加载,保存,显示和转换的图像处理和转换库,可以处理的图片格式包括 BMP, JPEG, GIF, PNG, TIFF, MNG, ICO, PCX, TGA, WMF, WBMP, JBG, J2K。
  • FreeImage :开源库,支持现在多媒体应用所需的通用图片格式和其他格式。
  • GDCM:Grassroots DICOM 库
  • ITK:跨平台的开源图像分析系统
  • Magick++:ImageMagick程序的C++接口
  • MagickWnd:ImageMagick程序的C++接口
  • OpenCV : 开源计算机视觉类库
  • tesseract-ocr:OCR引擎
  • VIGRA :用于图像分析通用C++计算机视觉库
  • VTK :用于3D计算机图形学,图像处理和可视化的开源免费软件系统。

 

国际化

  • gettext :GNU `gettext’
  • IBM ICU:提供Unicode 和全球化支持的C、C++ 和Java库
  • libiconv :用于不同字符编码之间的编码转换库

 

Jason

  • frozen : C/C++的Jason解析生成器
  • Jansson :进行编解码和处理Jason数据的C语言库
  • jbson :C++14中构建和迭代BSON data,和Json 文档的库
  • JeayeSON:非常健全的C++ JSON库,只包含头文件
  • JSON++ : C++ JSON 解析器
  • json-parser:用可移植的ANSI C编写的JSON解析器,占用内存非常少
  • json11 :一个迷你的C++11 JSON库
  • jute :非常简单的C++ JSON解析器
  • ibjson:C语言中的JSON解析和打印库,很容易和任何模型集成。
  • libjson:轻量级的JSON库
  • PicoJSON:C++中JSON解析序列化,只包含头文件
  • qt-json :用于JSON数据和 QVariant层次间的相互解析的简单类
  • QJson:将JSON数据映射到QVariant对象的基于Qt的库
  • RapidJSON: 用于C++的快速JSON 解析生成器,包含SAX和DOM两种风格的API
  • YAJL :C语言中快速流JSON解析库

 

日志

  • Boost.Log :设计非常模块化,并且具有扩展性
  • easyloggingpp:C++日志库,只包含单一的头文件。
  • Log4cpp :一系列C++类库,灵活添加日志到文件,系统日志,IDSA和其他地方。
  • templog:轻量级C++库,可以添加日志到你的C++应用程序中

 

机器学习

  • Caffe :快速的神经网络框架
  • CCV :以C语言为核心的现代计算机视觉库
  • mlpack :可扩展的C++机器学习库
  • OpenCV:开源计算机视觉库
  • Recommender:使用协同过滤进行产品推荐/建议的C语言库。
  • SHOGUN:Shogun 机器学习工具
  • sofia-ml :用于机器学习的快速增量算法套件

 

数学

  • Armadillo :高质量的C++线性代数库,速度和易用性做到了很好的平衡。语法和MatlAB很相似
  • blaze:高性能的C++数学库,用于密集和稀疏算法。
  • ceres-solver :来自谷歌的C++库,用于建模和解决大型复杂非线性最小平方问题。
  • CGal: 高效,可靠的集合算法集合
  • cml :用于游戏和图形的免费C++数学库
  • Eigen :高级C++模板头文件库,包括线性代数,矩阵,向量操作,数值解决和其他相关的算法。
  • GMTL:数学图形模板库是一组广泛实现基本图形的工具。
  • GMP:用于个高精度计算的C/C++库,处理有符号整数,有理数和浮点数。

 

多媒体

  • GStreamer :构建媒体处理组件图形的库
  • LIVE555 Streaming Media :使用开放标准协议(RTP/RTCP, RTSP, SIP) 的多媒体流库
  • libVLC :libVLC (VLC SDK)媒体框架
  • QtAv:基于Qt和FFmpeg的多媒体播放框架,能够帮助你轻而易举地编写出一个播放器
  • SDL :简单直控媒体层
  • SFML :快速,简单的多媒体库

 

网络

  • ACE:C++面向对象网络变成工具包
  • Boost.Asio:用于网络和底层I/O编程的跨平台的C++库
  • Casablanca:C++ REST SDK
  • cpp-netlib:高级网络编程的开源库集合
  • Dyad.c:C语言的异步网络
  • libcurl :多协议文件传输库
  • Mongoose:非常轻量级的网络服务器
  • Muduo :用于Linux多线程服务器的C++非阻塞网络库
  • net_skeleton :C/C++的TCP 客户端/服务器库
  • nope.c :基于C语言的超轻型软件平台,用于可扩展的服务器端和网络应用。 对于C编程人员,可以考虑node.js
  • Onion :C语言HTTP服务器库,其设计为轻量级,易使用。
  • POCO:用于构建网络和基于互联网应用程序的C++类库,可以运行在桌面,服务器,移动和嵌入式系统。
  • RakNet:为游戏开发人员提供的跨平台的开源C++网络引擎。
  • Tuf o :用于Qt之上的C++构建的异步Web框架。
  • WebSocket++ :基于C++/Boost Aiso的websocket 客户端/服务器库
  • ZeroMQ :高速,模块化的异步通信库

 

物理学

动力学仿真引擎

  • Box2D:2D的游戏物理引擎。
  • Bullet :3D的游戏物理引擎。
  • Chipmunk :快速,轻量级的2D游戏物理库
  • LiquidFun:2D的游戏物理引擎
  • ODE :开放动力学引擎-开源,高性能库,模拟刚体动力学。
  • ofxBox2d:Box2D开源框架包装器。
  • Simbody :高性能C++多体动力学/物理库,模拟关节生物力学和机械系统,像车辆,机器人和人体骨骼。

 

机器人学

  • MOOS-IvP :一组开源C++模块,提供机器人平台的自主权,尤其是自主的海洋车辆。
  • MRPT:移动机器人编程工具包
  • PCL :点云库是一个独立的,大规模的开放项目,用于2D/3D图像和点云处理。
  • Robotics Library (RL): 一个独立的C++库,包括机器人动力学,运动规划和控制。
  • RobWork:一组C++库的集合,用于机器人系统的仿真和控制。
  • ROS :机器人操作系统,提供了一些库和工具帮助软件开发人员创建机器人应用程序。

 

科学计算

  • FFTW :用一维或者多维计算DFT的C语言库。
  • GSL:GNU科学库。

 

脚本

  • ChaiScript :用于C++的易于使用的嵌入式脚本语言。
  • Lua :用于配置文件和基本应用程序脚本的小型快速脚本引擎。
  • luacxx:用于创建Lua绑定的C++ 11 API
  • SWIG :一个可以让你的C++代码链接到JavaScript,Perl,PHP,Python,Tcl和Ruby的包装器/接口生成器
  • V7:嵌入式的JavaScript 引擎。
  • V8 :谷歌的快速JavaScript引擎,可以被嵌入到任何C++应用程序中。

 

序列化

  • Cap’n Proto :快速数据交换格式和RPC系统。
  • cereal :C++11 序列化库
  • FlatBuffers :内存高效的序列化库
  • MessagePack :C/C++的高效二进制序列化库,例如 JSON
  • protobuf :协议缓冲,谷歌的数据交换格式。
  • protobuf-c :C语言的协议缓冲实现
  • SimpleBinaryEncoding:用于低延迟应用程序的对二进制格式的应用程序信息的编码和解码。
  • Thrift :高效的跨语言IPC/RPC,用于C++,Java,Python,PHP,C#和其它多种语言中,最初由Twitter开发。

 

视频

  • libvpx :VP8/VP9编码解码SDK
  • FFmpeg :一个完整的,跨平台的解决方案,用于记录,转换视频和音频流。
  • libde265 :开放的h.265视频编解码器的实现。
  • OpenH264:开源H.364 编解码器。
  • Theora :免费开源的视频压缩格式。

 

虚拟机

  • CarpVM:C中有趣的VM,让我们一起来看看这个。
  • MicroPython :旨在实现单片机上Python3.x的实现
  • TinyVM:用纯粹的ANSI C编写的小型,快速,轻量级的虚拟机。

 

Web应用框架

  • Civetweb :提供易于使用,强大的,C/C++嵌入式Web服务器,带有可选的CGI,SSL和Lua支持。
  • CppCMS :免费高性能的Web开发框架(不是 CMS).
  • Crow :一个C++微型web框架(灵感来自于Python Flask)
  • Kore :使用C语言开发的用于web应用程序的超快速和灵活的web服务器/框架。
  • libOnion:轻量级的库,帮助你使用C编程语言创建web服务器。
  • QDjango:使用C++编写的,基于Qt库的web框架,试图效仿Django API,因此得此名。
  • Wt :开发Web应用的C++库。

 

XML

XML就是个垃圾,xml的解析很烦人,对于计算机它也是个灾难。这种糟糕的东西完全没有存在的理由了。-Linus Torvalds

  • Expat :用C语言编写的xml解析库
  • Libxml2 :Gnome的xml C解析器和工具包
  • libxml++ :C++的xml解析器
  • PugiXML :用于C++的,支持XPath的轻量级,简单快速的XML解析器。
  • RapidXml :试图创建最快速的XML解析器,同时保持易用性,可移植性和合理的W3C兼容性。
  • TinyXML :简单小型的C++XML解析器,可以很容易地集成到其它项目中。
  • TinyXML2:简单快速的C++CML解析器,可以很容易集成到其它项目中。
  • TinyXML++:TinyXML的一个全新的接口,使用了C++的许多许多优势,模板,异常和更好的异常处理。
  • Xerces-C++ :用可移植的C++的子集编写的XML验证解析器。

 

多项混杂

一些有用的库或者工具,但是不适合上面的分类,或者还没有分类。

  • C++ Format :C++的小型,安全和快速格式化库
  • casacore :从aips++ 派生的一系列C++核心库
  • cxx-prettyprint:用于C++容器的打印库
  • DynaPDF :易于使用的PDF生成库
  • gcc-poison :帮助开发人员禁止应用程序中的不安全的C/C++函数的简单的头文件。
  • googlemock:编写和使用C++模拟类的库
  • HTTP Parser :C的http请求/响应解析器
  • libcpuid :用于x86 CPU检测盒特征提取的小型C库
  • libevil :许可证管理器
  • libusb:允许移动访问USB设备的通用USB库
  • PCRE:正则表达式C库,灵感来自于Perl中正则表达式的功能。
  • Remote Call Framework :C++的进程间通信框架。
  • Scintilla :开源的代码编辑控件
  • Serial Communication Library :C++语言编写的跨平台,串口库。
  • SDS:C的简单动态字符串库
  • SLDR :超轻的DNS解析器
  • SLRE: 超轻的正则表达式库
  • Stage :移动机器人模拟器
  • VarTypes:C++/Qt4功能丰富,面向对象的管理变量的框架。
  • ZBar:‘条形码扫描器’库,可以扫描照片,图片和视频流中的条形码,并返回结果。
  • CppVerbalExpressions :易于使用的C++正则表达式
  • QtVerbalExpressions:基于C++ VerbalExpressions 库的Qt库
  • PHP-CPP:使用C++来构建PHP扩展的库
  • Better String :C的另一个字符串库,功能更丰富,但是没有缓冲溢出问题,还包含了一个C++包装器。

 

软件

用于创建开发环境的软件

编译器

C/C++编译器列表

  • Clang :由苹果公司开发的
  • GCC:GNU编译器集合
  • Intel C++ Compiler :由英特尔公司开发
  • LLVM :模块化和可重用编译器和工具链技术的集合
  • Microsoft Visual C++ :MSVC,由微软公司开发
  • Open WatCom :Watcom,C,C++和Fortran交叉编译器和工具
  • TCC :轻量级的C语言编译器

 

在线编译器

在线C/C++编译器列表

  • codepad :在线编译器/解释器,一个简单的协作工具
  • CodeTwist:一个简单的在线编译器/解释器,你可以粘贴的C,C++或者Java代码,在线执行并查看结果
  • coliru :在线编译器/shell, 支持各种C++编译器
  • Compiler Explorer:交互式编译器,可以进行汇编输出
  • CompileOnline:Linux上在线编译和执行C++程序
  • Ideone :一个在线编译器和调试工具,允许你在线编译源代码并执行,支持60多种编程语言。

 

调试器

C/C++调试器列表

 

集成开发环境(IDE)

C/C++集成开发环境列表

  • AppCode :构建与JetBrains’ IntelliJ IDEA 平台上的用于Objective-C,C,C++,Java和Java开发的集成开发环境
  • CLion:来自JetBrains的跨平台的C/C++的集成开发环境
  • Code::Blocks :免费C,C++和Fortran的集成开发环境
  • CodeLite :另一个跨平台的免费的C/C++集成开发环境
  • Dev-C++:可移植的C/C++/C++11集成开发环境
  • Eclipse CDT:基于Eclipse平台的功能齐全的C和C++集成开发环境
  • Geany :轻量级的快速,跨平台的集成开发环境。
  • IBM VisualAge :来自IBM的家庭计算机集成开发环境。
  • Irony-mode:由libclang驱动的用于Emacs的C/C++微模式
  • KDevelop:免费开源集成开发环境
  • Microsoft Visual Studio :来自微软的集成开发环境
  • NetBeans :主要用于Java开发的的集成开发环境,也支持其他语言,尤其是PHP,C/C++和HTML5。
  • Qt Creator:跨平台的C++,Javascript和QML集成开发环境,也是Qt SDK的一部分。
  • rtags:C/C++的客户端服务器索引,用于 跟基于clang的emacs的集成
  • Xcode :由苹果公司开发
  • YouCompleteMe:一个用于Vim的根据你敲的代码快速模糊搜索并进行代码补全的引擎。

 

构建系统

  • Bear :用于为clang工具生成编译数据库的工具
  • Biicode:基于文件的简单依赖管理器。
  • CMake :跨平台的免费开源软件用于管理软件使用独立编译的方法进行构建的过程。
  • CPM:基于CMake和Git的C++包管理器
  • FASTBuild:高性能,开源的构建系统,支持高度可扩展性的编译,缓冲和网络分布。
  • Ninja :专注于速度的小型构建系统
  • Scons :使用Python scipt 配置的软件构建工具
  • tundra :高性能的代码构建系统,甚至对于非常大型的软件项目,也能提供最好的增量构建次数。
  • tup:基于文件的构建系统,用于后台监控变化的文件。

 

静态代码分析

提高质量,减少瑕疵的代码分析工具列表

 | 257 views | 0 comments | 0 flags | 

在数学的海洋中飘荡

https://dahuasky.wordpress.com/2009/01/22/%E5%9C%A8%E6%95%B0%E5%AD%A6%E7%9A%84%E6%B5%B7%E6%B4%8B%E4%B8%AD%E9%A3%98%E8%8D%A1/

 

在数学的海洋中飘荡

在过去的一年中,我一直在数学的海洋中游荡,research进展不多,对于数学世界的阅历算是有了一些长进。

为什么要深入数学的世界

作为计算机的学生,我没有任何企图要成为一个数学家。我学习数学的目的,是要想爬上巨人的肩膀,希望站在更高的高度,能把我自己研究的东西看得更深广一些。说起来,我在刚来这个学校的时候,并没有预料到我将会有一个深入数学的旅程。我的导师最初希望我去做的题目,是对appearance和motion建立一个unified的model。这个题目在当今Computer Vision中百花齐放的世界中并没有任何特别的地方。事实上,使用各种Graphical Model把各种东西联合在一起framework,在近年的论文中并不少见。

我不否认现在广泛流行的Graphical Model是对复杂现象建模的有力工具,但是,我认为它不是panacea,并不能取代对于所研究的问题的深入的钻研。如果统计学习包治百病,那么很多“下游”的学科也就没有存在的必要了。事实上,开始的时候,我也是和Vision中很多人一样,想着去做一个Graphical Model——我的导师指出,这样的做法只是重复一些标准的流程,并没有很大的价值。经过很长时间的反复,另外一个路径慢慢被确立下来——我们相信,一个图像是通过大量“原子”的某种空间分布构成的,原子群的运动形成了动态的可视过程。微观意义下的单个原子运动,和宏观意义下的整体分布的变换存在着深刻的联系——这需要我们去发掘。

在深入探索这个题目的过程中,遇到了很多很多的问题,如何描述一个一般的运动过程,如何建立一个稳定并且广泛适用的原子表达,如何刻画微观运动和宏观分布变换的联系,还有很多。在这个过程中,我发现了两个事情:

  • 我原有的数学基础已经远远不能适应我对这些问题的深入研究。
  • 在数学中,有很多思想和工具,是非常适合解决这些问题的,只是没有被很多的应用科学的研究者重视。

于是,我决心开始深入数学这个浩瀚大海,希望在我再次走出来的时候,我已经有了更强大的武器去面对这些问题的挑战。

我的游历并没有结束,我的视野相比于这个博大精深的世界的依旧显得非常狭窄。在这里,我只是说说,在我的眼中,数学如何一步步从初级向高级发展,更高级别的数学对于具体应用究竟有何好处。

 

集合论:现代数学的共同基础

现代数学有数不清的分支,但是,它们都有一个共同的基础——集合论——因为它,数学这个庞大的家族有个共同的语言。集合论中有一些最基本的概念:集合(set),关系(relation),函数(function),等价(equivalence),是在其它数学分支的语言中几乎必然存在的。对于这些简单概念的理解,是进一步学些别的数学的基础。我相信,理工科大学生对于这些都不会陌生。

不过,有一个很重要的东西就不见得那么家喻户晓了——那就是“选择公理”(Axiom of Choice)。这个公理的意思是“任意的一群非空集合,一定可以从每个集合中各拿出一个元素。”——似乎是显然得不能再显然的命题。不过,这个貌似平常的公理却能演绎出一些比较奇怪的结论,比如巴拿赫-塔斯基分球定理——“一个球,能分成五个部分,对它们进行一系列刚性变换(平移旋转)后,能组合成两个一样大小的球”。正因为这些完全有悖常识的结论,导致数学界曾经在相当长时间里对于是否接受它有着激烈争论。现在,主流数学家对于它应该是基本接受的,因为很多数学分支的重要定理都依赖于它。在我们后面要回说到的学科里面,下面的定理依赖于选择公理:

  1. 拓扑学:Baire Category Theorem
  2. 实分析(测度理论):Lebesgue 不可测集的存在性
  3. 泛函分析四个主要定理:Hahn-Banach Extension Theorem, Banach-Steinhaus Theorem (Uniform boundedness principle), Open Mapping Theorem, Closed Graph Theorem

在集合论的基础上,现代数学有两大家族:分析(Analysis)和代数(Algebra)。至于其它的,比如几何和概率论,在古典数学时代,它们是和代数并列的,但是它们的现代版本则基本是建立在分析或者代数的基础上,因此从现代意义说,它们和分析与代数并不是平行的关系。

分析:在极限基础上建立的宏伟大厦

微积分:分析的古典时代——从牛顿到柯西

先说说分析(Analysis)吧,它是从微积分(Caculus)发展起来的——这也是有些微积分教材名字叫“数学分析”的原因。不过,分析的范畴远不只是这些,我们在大学一年级学习的微积分只能算是对古典分析的入门。分析研究的对象很多,包括导数(derivatives),积分(integral),微分方程(differential equation),还有级数(infinite series)——这些基本的概念,在初等的微积分里面都有介绍。如果说有一个思想贯穿其中,那就是极限——这是整个分析(不仅仅是微积分)的灵魂。

一个很多人都听说过的故事,就是牛顿(Newton)和莱布尼茨(Leibniz)关于微积分发明权的争论。事实上,在他们的时代,很多微积分的工具开始运用在科学和工程之中,但是,微积分的基础并没有真正建立。那个长时间一直解释不清楚的“无穷小量”的幽灵,困扰了数学界一百多年的时间——这就是“第二次数学危机”。直到柯西用数列极限的观点重新建立了微积分的基本概念,这门学科才开始有了一个比较坚实的基础。直到今天,整个分析的大厦还是建立在极限的基石之上。

柯西(Cauchy)为分析的发展提供了一种严密的语言,但是他并没有解决微积分的全部问题。在19世纪的时候,分析的世界仍然有着一些挥之不去的乌云。而其中最重要的一个没有解决的是“函数是否可积的问题”。我们在现在的微积分课本中学到的那种通过“无限分割区间,取矩阵面积和的极限”的积分,是大约在1850年由黎曼(Riemann)提出的,叫做黎曼积分。但是,什么函数存在黎曼积分呢(黎曼可积)?数学家们很早就证明了,定义在闭区间内的连续函数是黎曼可积的。可是,这样的结果并不令人满意,工程师们需要对分段连续函数的函数积分。

实分析:在实数理论和测度理论上建立起现代分析

在19世纪中后期,不连续函数的可积性问题一直是分析的重要课题。对于定义在闭区间上的黎曼积分的研究发现,可积性的关键在于“不连续的点足够少”。只有有限处不连续的函数是可积的,可是很多有数学家们构造出很多在无限处不连续的可积函数。显然,在衡量点集大小的时候,有限和无限并不是一种合适的标准。在探讨“点集大小”这个问题的过程中,数学家发现实数轴——这个他们曾经以为已经充分理解的东西——有着许多他们没有想到的特性。在极限思想的支持下,实数理论在这个时候被建立起来,它的标志是对实数完备性进行刻画的几条等价的定理(确界定理,区间套定理,柯西收敛定理,Bolzano-Weierstrass Theorem和Heine-Borel Theorem等等)——这些定理明确表达出实数和有理数的根本区别:完备性(很不严格的说,就是对极限运算封闭)。随着对实数认识的深入,如何测量“点集大小”的问题也取得了突破,勒贝格创造性地把关于集合的代数,和Outer content(就是“外测度”的一个雏形)的概念结合起来,建立了测度理论(Measure Theory),并且进一步建立了以测度为基础的积分——勒贝格(Lebesgue Integral)。在这个新的积分概念的支持下,可积性问题变得一目了然。

上面说到的实数理论,测度理论和勒贝格积分,构成了我们现在称为实分析(Real Analysis)的数学分支,有些书也叫实变函数论。对于应用科学来说,实分析似乎没有古典微积分那么“实用”——很难直接基于它得到什么算法。而且,它要解决的某些“难题”——比如处处不连续的函数,或者处处连续而处处不可微的函数——在工程师的眼中,并不现实。但是,我认为,它并不是一种纯数学概念游戏,它的现实意义在于为许多现代的应用数学分支提供坚实的基础。下面,我仅仅列举几条它的用处:

  1. 黎曼可积的函数空间不是完备的,但是勒贝格可积的函数空间是完备的。简单的说,一个黎曼可积的函数列收敛到的那个函数不一定是黎曼可积的,但是勒贝格可积的函数列必定收敛到一个勒贝格可积的函数。在泛函分析,还有逼近理论中,经常需要讨论“函数的极限”,或者“函数的级数”,如果用黎曼积分的概念,这种讨论几乎不可想像。我们有时看一些paper中提到Lp函数空间,就是基于勒贝格积分。
  2. 勒贝格积分是傅立叶变换(这东西在工程中到处都是)的基础。很多关于信号处理的初等教材,可能绕过了勒贝格积分,直接讲点面对实用的东西而不谈它的数学基础,但是,对于深层次的研究问题——特别是希望在理论中能做一些工作——这并不是总能绕过去。
  3. 在下面,我们还会看到,测度理论是现代概率论的基础。

拓扑学:分析从实数轴推广到一般空间——现代分析的抽象基础

随着实数理论的建立,大家开始把极限和连续推广到更一般的地方的分析。事实上,很多基于实数的概念和定理并不是实数特有的。很多特性可以抽象出来,推广到更一般的空间里面。对于实数轴的推广,促成了点集拓扑学(Point-set Topology)的建立。很多原来只存在于实数中的概念,被提取出来,进行一般性的讨论。在拓扑学里面,有4个C构成了它的核心:

  1. Closed set(闭集合)。在现代的拓扑学的公理化体系中,开集和闭集是最基本的概念。一切从此引申。这两个概念是开区间和闭区间的推广,它们的根本地位,并不是一开始就被认识到的。经过相当长的时间,人们才认识到:开集的概念是连续性的基础,而闭集对极限运算封闭——而极限正是分析的根基。
  2. Continuous function (连续函数)。连续函数在微积分里面有个用epsilon-delta语言给出的定义,在拓扑学中它的定义是“开集的原像是开集的函数”。第二个定义和第一个是等价的,只是用更抽象的语言进行了改写。我个人认为,它的第三个(等价)定义才从根本上揭示连续函数的本质——“连续函数是保持极限运算的函数”——比如y是数列x1, x2, x3, … 的极限, 那么如果 f 是连续函数,那么 f(y) 就是 f(x1), f(x2), f(x3), …的极限。连续函数的重要性,可以从别的分支学科中进行类比。比如群论中,基础的运算是“乘法”,对于群,最重要的映射叫“同态映射”——保持“乘法”的映射。在分析中,基础运算是“极限”,因此连续函数在分析中的地位,和同态映射在代数中的地位是相当的。
  3. Connected set (连通集合)。比它略为窄一点的概念叫(Path connected),就是集合中任意两点都存在连续路径相连——可能是一般人理解的概念。一般意义下的连通概念稍微抽象一些。在我看来,连通性有两个重要的用场:一个是用于证明一般的中值定理(Intermediate Value Theorem),还有就是代数拓扑,拓扑群论和李群论中讨论根本群(Fundamental Group)的阶。
  4. Compact set(紧集)。Compactness似乎在初等微积分里面没有专门出现,不过有几条实数上的定理和它其实是有关系的。比如,“有界数列必然存在收敛子列”——用compactness的语言来说就是——“实数空间中有界闭集是紧的”。它在拓扑学中的一般定义是一个听上去比较抽象的东西——“紧集的任意开覆盖存在有限子覆盖”。这个定义在讨论拓扑学的定理时很方便,它在很多时候能帮助实现从无限到有限的转换。对于分析来说,用得更多的是它的另一种形式——“紧集中的数列必存在收敛子列”——它体现了分析中最重要的“极限”。Compactness在现代分析中运用极广,无法尽述。微积分中的两个重要定理:极值定理(Extreme Value Theory),和一致收敛定理(Uniform Convergence Theorem)就可以借助它推广到一般的形式。

从某种意义上说,点集拓扑学可以看成是关于“极限”的一般理论,它抽象于实数理论,它的概念成为几乎所有现代分析学科的通用语言,也是整个现代分析的根基所在。

微分几何:流形上的分析——在拓扑空间上引入微分结构

拓扑学把极限的概念推广到一般的拓扑空间,但这不是故事的结束,而仅仅是开始。在微积分里面,极限之后我们有微分,求导,积分。这些东西也可以推广到拓扑空间,在拓扑学的基础上建立起来——这就是微分几何。从教学上说,微分几何的教材,有两种不同的类型,一种是建立在古典微机分的基础上的“古典微分几何”,主要是关于二维和三维空间中的一些几何量的计算,比如曲率。还有一种是建立在现代拓扑学的基础上,这里姑且称为“现代微分几何”——它的核心概念就是“流形”(manifold)——就是在拓扑空间的基础上加了一套可以进行微分运算的结构。现代微分几何是一门非常丰富的学科。比如一般流形上的微分的定义就比传统的微分丰富,我自己就见过三种从不同角度给出的等价定义——这一方面让事情变得复杂一些,但是另外一个方面它给了同一个概念的不同理解,往往在解决问题时会引出不同的思路。除了推广微积分的概念以外,还引入了很多新概念:tangent space, cotangent space, push forward, pull back, fibre bundle, flow, immersion, submersion 等等。

近些年,流形在machine learning似乎相当时髦。但是,坦率地说,要弄懂一些基本的流形算法, 甚至“创造”一些流形算法,并不需要多少微分几何的基础。对我的研究来说,微分几何最重要的应用就是建立在它之上的另外一个分支:李群和李代数——这是数学中两大家族分析和代数的一个漂亮的联姻。分析和代数的另外一处重要的结合则是泛函分析,以及在其基础上的调和分析。

 

代数:一个抽象的世界

关于抽象代数

回过头来,再说说另一个大家族——代数。

如果说古典微积分是分析的入门,那么现代代数的入门点则是两个部分:线性代数(linear algebra)和基础的抽象代数(abstract algebra)——据说国内一些教材称之为近世代数。

代数——名称上研究的似乎是数,在我看来,主要研究的是运算规则。一门代数,其实都是从某种具体的运算体系中抽象出一些基本规则,建立一个公理体系,然后在这基础上进行研究。一个集合再加上一套运算规则,就构成一个代数结构。在主要的代数结构中,最简单的是群(Group)——它只有一种符合结合率的可逆运算,通常叫“乘法”。如果,这种运算也符合交换率,那么就叫阿贝尔群(Abelian Group)。如果有两种运算,一种叫加法,满足交换率和结合率,一种叫乘法,满足结合率,它们之间满足分配率,这种丰富一点的结构叫做环(Ring),如果环上的乘法满足交换率,就叫可交换环(Commutative Ring)。如果,一个环的加法和乘法具有了所有的良好性质,那么就成为一个域(Field)。基于域,我们可以建立一种新的结构,能进行加法和数乘,就构成了线性代数(Linear algebra)。

代数的好处在于,它只关心运算规则的演绎,而不管参与运算的对象。只要定义恰当,完全可以让一只猫乘一只狗得到一头猪:-)。基于抽象运算规则得到的所有定理完全可以运用于上面说的猫狗乘法。当然,在实际运用中,我们还是希望用它干点有意义的事情。学过抽象代数的都知道,基于几条最简单的规则,比如结合律,就能导出非常多的重要结论——这些结论可以应用到一切满足这些简单规则的地方——这是代数的威力所在,我们不再需要为每一个具体领域重新建立这么多的定理。

抽象代数有在一些基础定理的基础上,进一步的研究往往分为两个流派:研究有限的离散代数结构(比如有限群和有限域),这部分内容通常用于数论,编码,和整数方程这些地方;另外一个流派是研究连续的代数结构,通常和拓扑与分析联系在一起(比如拓扑群,李群)。我在学习中的focus主要是后者。

线性代数:“线性”的基础地位

对于做Learning, vision, optimization或者statistics的人来说,接触最多的莫过于线性代数——这也是我们在大学低年级就开始学习的。线性代数,包括建立在它基础上的各种学科,最核心的两个概念是向量空间和线性变换。线性变换在线性代数中的地位,和连续函数在分析中的地位,或者同态映射在群论中的地位是一样的——它是保持基础运算(加法和数乘)的映射。

在learning中有这样的一种倾向——鄙视线性算法,标榜非线性。也许在很多场合下面,我们需要非线性来描述复杂的现实世界,但是无论什么时候,线性都是具有根本地位的。没有线性的基础,就不可能存在所谓的非线性推广。我们常用的非线性化的方法包括流形和kernelization,这两者都需要在某个阶段回归线性。流形需要在每个局部建立和线性空间的映射,通过把许多局部线性空间连接起来形成非线性;而kernerlization则是通过置换内积结构把原线性空间“非线性”地映射到另外一个线性空间,再进行线性空间中所能进行的操作。而在分析领域,线性的运算更是无处不在,微分,积分,傅立叶变换,拉普拉斯变换,还有统计中的均值,通通都是线性的。

泛函分析:从有限维向无限维迈进

在大学中学习的线性代数,它的简单主要因为它是在有限维空间进行的,因为有限,我们无须借助于太多的分析手段。但是,有限维空间并不能有效地表达我们的世界——最重要的,函数构成了线性空间,可是它是无限维的。对函数进行的最重要的运算都在无限维空间进行,比如傅立叶变换和小波分析。这表明了,为了研究函数(或者说连续信号),我们需要打破有限维空间的束缚,走入无限维的函数空间——这里面的第一步,就是泛函分析。

泛函分析(Functional Analysis)是研究的是一般的线性空间,包括有限维和无限维,但是很多东西在有限维下显得很trivial,真正的困难往往在无限维的时候出现。在泛函分析中,空间中的元素还是叫向量,但是线性变换通常会叫作“算子”(operator)。除了加法和数乘,这里进一步加入了一些运算,比如加入范数去表达“向量的长度”或者“元素的距离”,这样的空间叫做“赋范线性空间”(normed space),再进一步的,可以加入内积运算,这样的空间叫“内积空间”(Inner product space)。

大家发现,当进入无限维的时间时,很多老的观念不再适用了,一切都需要重新审视。

  1. 所有的有限维空间都是完备的(柯西序列收敛),很多无限维空间却是不完备的(比如闭区间上的连续函数)。在这里,完备的空间有特殊的名称:完备的赋范空间叫巴拿赫空间(Banach space),完备的内积空间叫希尔伯特空间(Hilbert space)。
  2. 在有限维空间中空间和它的对偶空间的是完全同构的,而在无限维空间中,它们存在微妙的差别。
  3. 在有限维空间中,所有线性变换(矩阵)都是有界变换,而在无限维,很多算子是无界的(unbounded),最重要的一个例子是给函数求导。
  4. 在有限维空间中,一切有界闭集都是紧的,比如单位球。而在所有的无限维空间中,单位球都不是紧的——也就是说,可以在单位球内撒入无限个点,而不出现一个极限点。
  5. 在有限维空间中,线性变换(矩阵)的谱相当于全部的特征值,在无限维空间中,算子的谱的结构比这个复杂得多,除了特征值组成的点谱(point spectrum),还有approximate point spectrum和residual spectrum。虽然复杂,但是,也更为有趣。由此形成了一个相当丰富的分支——算子谱论(Spectrum theory)。
  6. 在有限维空间中,任何一点对任何一个子空间总存在投影,而在无限维空间中,这就不一定了,具有这种良好特性的子空间有个专门的名称切比雪夫空间(Chebyshev space)。这个概念是现代逼近理论的基础(approximation theory)。函数空间的逼近理论在Learning中应该有着非常重要的作用,但是现在看到的运用现代逼近理论的文章并不多。

继续往前:巴拿赫代数,调和分析,和李代数

基本的泛函分析继续往前走,有两个重要的方向。第一个是巴拿赫代数(Banach Algebra),它就是在巴拿赫空间(完备的内积空间)的基础上引入乘法(这不同于数乘)。比如矩阵——它除了加法和数乘,还能做乘法——这就构成了一个巴拿赫代数。除此以外,值域完备的有界算子,平方可积函数,都能构成巴拿赫代数。巴拿赫代数是泛函分析的抽象,很多对于有界算子导出的结论,还有算子谱论中的许多定理,它们不仅仅对算子适用,它们其实可以从一般的巴拿赫代数中得到,并且应用在算子以外的地方。巴拿赫代数让你站在更高的高度看待泛函分析中的结论,但是,我对它在实际问题中能比泛函分析能多带来什么东西还有待思考。

最能把泛函分析和实际问题在一起的另一个重要方向是调和分析(Harmonic Analysis)。我在这里列举它的两个个子领域,傅立叶分析和小波分析,我想这已经能说明它的实际价值。它研究的最核心的问题就是怎么用基函数去逼近和构造一个函数。它研究的是函数空间的问题,不可避免的必须以泛函分析为基础。除了傅立叶和小波,调和分析还研究一些很有用的函数空间,比如Hardy space,Sobolev space,这些空间有很多很好的性质,在工程中和物理学中都有很重要的应用。对于vision来说,调和分析在信号的表达,图像的构造,都是非常有用的工具。

当分析和线性代数走在一起,产生了泛函分析和调和分析;当分析和群论走在一起,我们就有了李群(Lie Group)和李代数(Lie Algebra)。它们给连续群上的元素赋予了代数结构。我一直认为这是一门非常漂亮的数学:在一个体系中,拓扑,微分和代数走到了一起。在一定条件下,通过李群和李代数的联系,它让几何变换的结合变成了线性运算,让子群化为线性子空间,这样就为Learning中许多重要的模型和算法的引入到对几何运动的建模创造了必要的条件。因此,我们相信李群和李代数对于vision有着重要意义,只不过学习它的道路可能会很艰辛,在它之前需要学习很多别的数学。

 

现代概率论:在现代分析基础上再生 

最后,再简单说说很多Learning的研究者特别关心的数学分支:概率论。自从Kolmogorov在上世纪30年代把测度引入概率论以来,测度理论就成为现代概率论的基础。在这里,概率定义为测度,随机变量定义为可测函数,条件随机变量定义为可测函数在某个函数空间的投影,均值则是可测函数对于概率测度的积分。值得注意的是,很多的现代观点,开始以泛函分析的思路看待概率论的基础概念,随机变量构成了一个向量空间,而带符号概率测度则构成了它的对偶空间,其中一方施加于对方就形成均值。角度虽然不一样,不过这两种方式殊途同归,形成的基础是等价的。

在现代概率论的基础上,许多传统的分支得到了极大丰富,最有代表性的包括鞅论(Martingale)——由研究赌博引发的理论,现在主要用于金融(这里可以看出赌博和金融的理论联系,:-P),布朗运动(Brownian Motion)——连续随机过程的基础,以及在此基础上建立的随机分析(Stochastic Calculus),包括随机积分(对随机过程的路径进行积分,其中比较有代表性的叫伊藤积分(Ito Integral)),和随机微分方程。对于连续几何运用建立概率模型以及对分布的变换的研究离不开这些方面的知识。

 

终于写完了——也谢谢你把这么长的文章看完,希望其中的一些内容对你是有帮助的。

 | 347 views | 0 comments | 0 flags | 

【转】Linux虚拟地址空间布局

http://www.cnblogs.com/clover-toeic/p/3754433.html

 

在多任务操作系统中,每个进程都运行在属于自己的内存沙盘中。这个沙盘就是虚拟地址空间(Virtual Address Space),在32位模式下它是一个4GB的内存地址块。在Linux系统中, 内核进程和用户进程所占的虚拟内存比例是1:3,而Windows系统为2:2(通过设置Large-Address-Aware Executables标志也可为1:3)。这并不意味着内核使用那么多物理内存,仅表示它可支配这部分地址空间,根据需要将其映射到物理内存。

虚拟地址通过页表(Page Table)映射到物理内存,页表由操作系统维护并被处理器引用。内核空间在页表中拥有较高特权级,因此用户态程序试图访问这些页时会导致一个页错误(page fault)。在Linux中,内核空间是持续存在的,并且在所有进程中都映射到同样的物理内存。内核代码和数据总是可寻址,随时准备处理中断和系统调用。与此相反,用户模式地址空间的映射随进程切换的发生而不断变化。

Linux进程在虚拟内存中的标准内存段布局如下图所示:

其中,用户地址空间中的蓝色条带对应于映射到物理内存的不同内存段,灰白区域表示未映射的部分。这些段只是简单的内存地址范围,与Intel处理器的段没有关系。

上图中Random stack offset和Random mmap offset等随机值意在防止恶意程序。Linux通过对栈、内存映射段、堆的起始地址加上随机偏移量来打乱布局,以免恶意程序通过计算访问栈、库函数等地址。execve(2)负责为进程代码段和数据段建立映射,真正将代码段和数据段的内容读入内存是由系统的缺页异常处理程序按需完成的。另外,execve(2)还会将BSS段清零。

用户进程部分分段存储内容如下表所示(按地址递减顺序):

名称

存储内容

局部变量、函数参数、返回地址等

动态分配的内存

BSS段

未初始化或初值为0的全局变量和静态局部变量

数据段

已初始化且初值非0的全局变量和静态局部变量

代码段

可执行代码、字符串字面值、只读变量

在将应用程序加载到内存空间执行时,操作系统负责代码段、数据段和BSS段的加载,并在内存中为这些段分配空间。栈也由操作系统分配和管理;堆由程序员自己管理,即显式地申请和释放空间。

BSS段、数据段和代码段是可执行程序编译时的分段,运行时还需要栈和堆。

 

以下详细介绍各个分段的含义。

 

1 内核空间

内核总是驻留在内存中,是操作系统的一部分。内核空间为内核保留,不允许应用程序读写该区域的内容或直接调用内核代码定义的函数。

 

2 栈(stack)

栈又称堆栈,由编译器自动分配释放,行为类似数据结构中的栈(先进后出)。堆栈主要有三个用途:

  • 为函数内部声明的非静态局部变量(C语言中称“自动变量”)提供存储空间。
  • 记录函数调用过程相关的维护性信息,称为栈帧(Stack Frame)或过程活动记录(Procedure Activation Record)。它包括函数返回地址,不适合装入寄存器的函数参数及一些寄存器值的保存。除递归调用外,堆栈并非必需。因为编译时可获知局部变量,参数和返回地址所需空间,并将其分配于BSS段。
  • 临时存储区,用于暂存长算术表达式部分计算结果或alloca()函数分配的栈内内存。

持续地重用栈空间有助于使活跃的栈内存保持在CPU缓存中,从而加速访问。进程中的每个线程都有属于自己的栈。向栈中不断压入数据时,若超出其容量就会耗尽栈对应的内存区域,从而触发一个页错误。此时若栈的大小低于堆栈最大值RLIMIT_STACK(通常是8M),则栈会动态增长,程序继续运行。映射的栈区扩展到所需大小后,不再收缩。

Linux中ulimit -s命令可查看和设置堆栈最大值,当程序使用的堆栈超过该值时, 发生栈溢出(Stack Overflow),程序收到一个段错误(Segmentation Fault)。注意,调高堆栈容量可能会增加内存开销和启动时间。

堆栈既可向下增长(向内存低地址)也可向上增长, 这依赖于具体的实现。本文所述堆栈向下增长。

堆栈的大小在运行时由内核动态调整。

 

3 内存映射段(mmap)

此处,内核将硬盘文件的内容直接映射到内存, 任何应用程序都可通过Linux的mmap()系统调用或Windows的CreateFileMapping()/MapViewOfFile()请求这种映射。内存映射是一种方便高效的文件I/O方式, 因而被用于装载动态共享库。用户也可创建匿名内存映射,该映射没有对应的文件, 可用于存放程序数据。在 Linux中,若通过malloc()请求一大块内存,C运行库将创建一个匿名内存映射,而不使用堆内存。”大块” 意味着比阈值 MMAP_THRESHOLD还大,缺省为128KB,可通过mallopt()调整。

该区域用于映射可执行文件用到的动态链接库。在Linux 2.4版本中,若可执行文件依赖共享库,则系统会为这些动态库在从0×40000000开始的地址分配相应空间,并在程序装载时将其载入到该空间。在Linux 2.6内核中,共享库的起始地址被往上移动至更靠近栈区的位置。

从进程地址空间的布局可以看到,在有共享库的情况下,留给堆的可用空间还有两处:一处是从.bss段到0×40000000,约不到1GB的空间;另一处是从共享库到栈之间的空间,约不到2GB。这两块空间大小取决于栈、共享库的大小和数量。这样来看,是否应用程序可申请的最大堆空间只有2GB?事实上,这与Linux内核版本有关。在上面给出的进程地址空间经典布局图中,共享库的装载地址为0×40000000,这实际上是Linux kernel 2.6版本之前的情况了,在2.6版本里,共享库的装载地址已经被挪到靠近栈的位置,即位于0xBFxxxxxx附近,因此,此时的堆范围就不会被共享库分割成2个“碎片”,故kernel 2.6的32位Linux系统中,malloc申请的最大内存理论值在2.9GB左右。

 

4 堆(heap)

堆用于存放进程运行时动态分配的内存段,可动态扩张或缩减。堆中内容是匿名的,不能按名字直接访问,只能通过指针间接访问。当进程调用malloc(C)/new(C++)等函数分配内存时,新分配的内存动态添加到堆上(扩张);当调用free(C)/delete(C++)等函数释放内存时,被释放的内存从堆中剔除(缩减) 。

分配的堆内存是经过字节对齐的空间,以适合原子操作。堆管理器通过链表管理每个申请的内存,由于堆申请和释放是无序的,最终会产生内存碎片。堆内存一般由应用程序分配释放,回收的内存可供重新使用。若程序员不释放,程序结束时操作系统可能会自动回收。

堆的末端由break指针标识,当堆管理器需要更多内存时,可通过系统调用brk()和sbrk()来移动break指针以扩张堆,一般由系统自动调用。

使用堆时经常出现两种问题:1) 释放或改写仍在使用的内存(“内存破坏”);2)未释放不再使用的内存(“内存泄漏”)。当释放次数少于申请次数时,可能已造成内存泄漏。泄漏的内存往往比忘记释放的数据结构更大,因为所分配的内存通常会圆整为下个大于申请数量的2的幂次(如申请212B,会圆整为256B)。

注意,堆不同于数据结构中的”堆”,其行为类似链表。

【扩展阅读】栈和堆的区别

管理方式:栈由编译器自动管理;堆由程序员控制,使用方便,但易产生内存泄露。

生长方向:栈向低地址扩展(即”向下生长”),是连续的内存区域;堆向高地址扩展(即”向上生长”),是不连续的内存区域。这是由于系统用链表来存储空闲内存地址,自然不连续,而链表从低地址向高地址遍历。

空间大小:栈顶地址和栈的最大容量由系统预先规定(通常默认2M或10M);堆的大小则受限于计算机系统中有效的虚拟内存,32位Linux系统中堆内存可达2.9G空间。

存储内容:栈在函数调用时,首先压入主调函数中下条指令(函数调用语句的下条可执行语句)的地址,然后是函数实参,然后是被调函数的局部变量。本次调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的指令地址,程序由该点继续运行下条可执行语句。堆通常在头部用一个字节存放其大小,堆用于存储生存期与函数调用无关的数据,具体内容由程序员安排。

分配方式:栈可静态分配或动态分配。静态分配由编译器完成,如局部变量的分配。动态分配由alloca函数在栈上申请空间,用完后自动释放。堆只能动态分配且手工释放。

分配效率:栈由计算机底层提供支持:分配专门的寄存器存放栈地址,压栈出栈由专门的指令执行,因此效率较高。堆由函数库提供,机制复杂,效率比栈低得多。Windows系统中VirtualAlloc可直接在进程地址空间中分配一块内存,快速且灵活。

分配后系统响应:只要栈剩余空间大于所申请空间,系统将为程序提供内存,否则报告异常提示栈溢出。

操作系统为堆维护一个记录空闲内存地址的链表。当系统收到程序的内存分配申请时,会遍历该链表寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点空间分配给程序。若无足够大小的空间(可能由于内存碎片太多),有可能调用系统功能去增加程序数据段的内存空间,以便有机会分到足够大小的内存,然后进行返回。,大多数系统会在该内存空间首地址处记录本次分配的内存大小,供后续的释放函数(如free/delete)正确释放本内存空间。

此外,由于找到的堆结点大小不一定正好等于申请的大小,系统会自动将多余的部分重新放入空闲链表中。

碎片问题:栈不会存在碎片问题,因为栈是先进后出的队列,内存块弹出栈之前,在其上面的后进的栈内容已弹出。而频繁申请释放操作会造成堆内存空间的不连续,从而造成大量碎片,使程序效率降低。

可见,堆容易造成内存碎片;由于没有专门的系统支持,效率很低;由于可能引发用户态和内核态切换,内存申请的代价更为昂贵。所以栈在程序中应用最广泛,函数调用也利用栈来完成,调用过程中的参数、返回地址、栈基指针和局部变量等都采用栈的方式存放。所以,建议尽量使用栈,仅在分配大量或大块内存空间时使用堆。

使用栈和堆时应避免越界发生,否则可能程序崩溃或破坏程序堆、栈结构,产生意想不到的后果。

 

5 BSS段

BSS(Block Started by Symbol)段中通常存放程序中以下符号:

  • 未初始化的全局变量和静态局部变量
  • 初始值为0的全局变量和静态局部变量(依赖于编译器实现)
  • 未定义且初值不为0的符号(该初值即common block的大小)

C语言中,未显式初始化的静态分配变量被初始化为0(算术类型)或空指针(指针类型)。由于程序加载时,BSS会被操作系统清零,所以未赋初值或初值为0的全局变量都在BSS中。BSS段仅为未初始化的静态分配变量预留位置,在目标文件中并不占据空间,这样可减少目标文件体积。但程序运行时需为变量分配内存空间,故目标文件必须记录所有未初始化的静态分配变量大小总和(通过start_bss和end_bss地址写入机器代码)。当加载器(loader)加载程序时,将为BSS段分配的内存初始化为0。在嵌入式软件中,进入main()函数之前BSS段被C运行时系统映射到初始化为全零的内存(效率较高)。

注意,尽管均放置于BSS段,但初值为0的全局变量是强符号,而未初始化的全局变量是弱符号。若其他地方已定义同名的强符号(初值可能非0),则弱符号与之链接时不会引起重定义错误,但运行时的初值可能并非期望值(会被强符号覆盖)。因此,定义全局变量时,若只有本文件使用,则尽量使用static关键字修饰;否则需要为全局变量定义赋初值(哪怕0值),保证该变量为强符号,以便链接时发现变量名冲突,而不是被未知值覆盖。

某些编译器将未初始化的全局变量保存在common段,链接时再将其放入BSS段。在编译阶段可通过-fno-common选项来禁止将未初始化的全局变量放入common段。

此外,由于目标文件不含BSS段,故程序烧入存储器(Flash)后BSS段地址空间内容未知。U-Boot启动过程中将U-Boot的Stage2代码(通常位于lib_xxxx/board.c文件)搬迁(拷贝)到SDRAM空间后必须人为添加清零BSS段的代码,而不可依赖于Stage2代码中变量定义时赋0值。

【扩展阅读】BSS历史

BSS(Block Started by Symbol,以符号开始的块)一词最初是UA-SAP汇编器(United Aircraft Symbolic Assembly Program)中的伪指令,用于为符号预留一块内存空间。该汇编器由美国联合航空公司于20世纪50年代中期为IBM 704大型机所开发。

后来该词被作为关键字引入到了IBM 709和7090/94机型上的标准汇编器FAP(Fortran Assembly Program),用于定义符号并且为该符号预留指定字数的未初始化空间块。

在采用段式内存管理的架构中(如Intel 80×86系统),BSS段通常指用来存放程序中未初始化全局变量的一块内存区域,该段变量只有名称和大小却没有值。程序开始时由系统初始化清零。

BSS段不包含数据,仅维护开始和结束地址,以便内存能在运行时被有效地清零。BSS所需的运行时空间由目标文件记录,但BSS并不占用目标文件内的实际空间,即BSS节段应用程序的二进制映象文件中并不存在。

6 数据段(Data)

数据段通常用于存放程序中已初始化且初值不为0的全局变量和静态局部变量。数据段属于静态内存分配(静态存储区),可读可写。

数据段保存在目标文件中(在嵌入式系统里一般固化在镜像文件中),其内容由程序初始化。例如,对于全局变量int gVar = 10,必须在目标文件数据段中保存10这个数据,然后在程序加载时复制到相应的内存。

数据段与BSS段的区别如下:

1) BSS段不占用物理文件尺寸,但占用内存空间;数据段占用物理文件,也占用内存空间。

对于大型数组如int ar0[10000] = {1, 2, 3, …}和int ar1[10000],ar1放在BSS段,只记录共有10000*4个字节需要初始化为0,而不是像ar0那样记录每个数据1、2、3…,此时BSS为目标文件所节省的磁盘空间相当可观。

2) 当程序读取数据段的数据时,系统会出发缺页故障,从而分配相应的物理内存;当程序读取BSS段的数据时,内核会将其转到一个全零页面,不会发生缺页故障,也不会为其分配相应的物理内存。

运行时数据段和BSS段的整个区段通常称为数据区。某些资料中“数据段”指代数据段 + BSS段 + 堆。

7 代码段(text)

代码段也称正文段或文本段,通常用于存放程序执行代码(即CPU执行的机器指令)。一般C语言执行语句都编译成机器代码保存在代码段。通常代码段是可共享的,因此频繁执行的程序只需要在内存中拥有一份拷贝即可。代码段通常属于只读,以防止其他程序意外地修改其指令(对该段的写操作将导致段错误)。某些架构也允许代码段为可写,即允许修改程序。

代码段指令根据程序设计流程依次执行,对于顺序指令,只会执行一次(每个进程);若有反复,则需使用跳转指令;若进行递归,则需要借助栈来实现。

代码段指令中包括操作码和操作对象(或对象地址引用)。若操作对象是立即数(具体数值),将直接包含在代码中;若是局部数据,将在栈区分配空间,然后引用该数据地址;若位于BSS段和数据段,同样引用该数据地址。

代码段最容易受优化措施影响。

8 保留区

位于虚拟地址空间的最低部分,未赋予物理地址。任何对它的引用都是非法的,用于捕捉使用空指针和小整型值指针引用内存的异常情况。

它并不是一个单一的内存区域,而是对地址空间中受到操作系统保护而禁止用户进程访问的地址区域的总称。大多数操作系统中,极小的地址通常都是不允许访问的,如NULL。C语言将无效指针赋值为0也是出于这种考虑,因为0地址上正常情况下不会存放有效的可访问数据。

在32位X86架构的Linux系统中,用户进程可执行程序一般从虚拟地址空间0×08048000开始加载。该加载地址由ELF文件头决定,可通过自定义链接器脚本覆盖链接器默认配置,进而修改加载地址。0×08048000以下的地址空间通常由C动态链接库、动态加载器ld.so和内核VDSO(内核提供的虚拟共享库)等占用。通过使用mmap系统调用,可访问0×08048000以下的地址空间。

通过cat /proc/self/maps命令查看加载表如下:

【扩展阅读】分段的好处

进程运行过程中,代码指令根据流程依次执行,只需访问一次(当然跳转和递归可能使代码执行多次);而数据(数据段和BSS段)通常需要访问多次,因此单独开辟空间以方便访问和节约空间。具体解释如下:

当程序被装载后,数据和指令分别映射到两个虚存区域。数据区对于进程而言可读写,而指令区对于进程只读。两区的权限可分别设置为可读写和只读。以防止程序指令被有意或无意地改写。

现代CPU具有极为强大的缓存(Cache)体系,程序必须尽量提高缓存命中率。指令区和数据区的分离有利于提高程序的局部性。现代CPU一般数据缓存和指令缓存分离,故程序的指令和数据分开存放有利于提高CPU缓存命中率。

当系统中运行多个该程序的副本时,其指令相同,故内存中只须保存一份该程序的指令部分。若系统中运行数百进程,通过共享指令将节省大量空间(尤其对于有动态链接的系统)。其他只读数据如程序里的图标、图片、文本等资源也可共享。而每个副本进程的数据区域不同,它们是进程私有的。

此外,临时数据及需要再次使用的代码在运行时放入栈区中,生命周期短。全局数据和静态数据可能在整个程序执行过程中都需要访问,因此单独存储管理。堆区由用户自由分配,以便管理。

 | 961 views | 0 comments | 0 flags | 

【转】实时操作系统Vxworks与通用操作系统Linux的比较+实模式等三种模式 DMA

http://blog.chinaunix.net/uid-26404477-id-3343987.html

一个好的实时操作系统需要具备以下功能(必须但非充分):

*多任务和可抢占的;

*任务具有优先级;

*操作系统具备支持可预测的任务同步机制;

*支持多任务间的通信;

*操作系统具备消除优先级转置的机制;

*存储器优化管理(含ROM的管理);

*操作系统的(中断延迟、任务切换、驱动程序延迟等)行为是可知的可预测的。这是指在
全负载的情形下,最坏反应时间可知;

*实时时钟服务;

*中断管理服务。

实时操作系统所遵循的最重要的设计原则是: 采用各种算法和策略,始终保证系统行为的可预测性。可预测性是指在系统运行的任何时刻,在任何 情况下,实时操作系统的资源调配策略都能为争夺资源(包括CPU、内存、网络带宽等)的多个实时任务合理地分配资源,使每个实时任务的实时性要求都能得到 满足。与通用操作系统不同,实时操作系统注重的不是系统的平均表现,而是要求每个实时任务在最坏情况下都要满足其实时性要求,也就是说,实时操作系统注重 的是个体表现,更准确地讲是个体最坏情况表现。

实时系统最关键的部分是实时多任务内核。它的基本功能包括多任务管理、定时器管理、
存储器管理、资源管理、事件管理、系统管理、消息管理、队列管理、信号量管理等。这
些管理功能是通过内核服务函数形式交给用户调用的,也就是实时操作系统的API。

================vxworks和linux的比较===========================

vxWorks       Linux
 

 

内核

结构

 

微内核,

内核只提供

了基本的服

务,如:任

务管理,内

存管理,中

断处理等

   内核    【Monolithic】,

除了基本的

服务,内核

还包括文件

系统,网络

协议

 

运行

模式

应用程序运

行在“实模

式”下,无

用户模式和

内核模式之

采用“保护

模式”,用

户进程、线

程运行在用

户模式下,

内核线程运

行于内核模

内存

访问

和内

存保

内核采用

存储管理方

式,所有任

务运行于同

一物理地址

空间,用户

程序直接操

作物理地

址,不能直

接地提供内

存保护,不

能防止错误

蔓延

内核采用虚

拟存储管理

方式,用户

具有独立的

地址空间

,用户进程

只能访问本

进程的虚拟

空间,提供

了内存保

护,可以防

止错误蔓延

执行

单元

 

 

 

任务

 

 

 

 

进程、线程
请求

内核

服务

方式

 

 

函数调用

更快

系统调用

,更安全

 

 

硬实时 软实时

关于各种周期 http://lionwq.spaces.eepw.com.cn/articles/article/item/17638

时钟周期

时钟周期也称为振荡周期,定义为时钟脉冲的倒数(时钟周期就是单片机外接晶振的倒数,例如12M的晶振,它的时钟周期就是1/12us),是计算机中的最基本的、最小的时间单位。
在一个时钟周期内,CPU仅完成一个最基本的动作。时钟脉冲是计算机的基本工作脉冲,控制着计算机的工作节奏。时钟频率越高,工作速度就越快。

8051单片机把一个时钟周期定义为一个节拍(用P表示),二个节拍定义为一个状态周期(用S表示)。

机器周期

计算机中,常把一条指令的执行过程划分为若干个阶段,每一个阶段完成一项工作。每一项工作称为一个基本操作,完成一个基本操作所需要的时间称为机器周期。8051系列单片机的一个机器周期由6个S周期(状态周期)组成。 一个S周期=2个节拍(P),所以8051单片机的一个机器周期=6个状态周期=12个时钟周期。

例如外接24M晶振的单片机,他的一个机器周期=12/24M 秒;

指令周期

执行一条指令所需要的时间,一般由若干个机器周期组成。指令不同,所需的机器周期也不同。

硬实时与软实时之间最关键的差别在于,软实时只能提供统计意义上的实时。例如,有的应用要求系统在95%的情况下都会确保在规定的时间内完成某个动作,而不一定要求100%。

SYS_CLK_RATE是1000,那么就是1ms。。如果是60那么就大约是16.67ms。。。【我们的设备就是60】通常来讲,vxWorks手册建议不要将时钟率设得太高,否则它就由硬实时变得趋向于软实时了。。因为过高的时钟率使得内核调度频繁进入,可能导致一些低优先级的硬件中断不能得到及时响应。

============================

嵌入式实时系统中采用的操作系统称为嵌入式实时操作系统,它既是嵌入式操作系统,又是实时操作系统。

作为一种嵌入式操作系统,它具有嵌入 式软件共有的可裁剪、低资源、占用、低功耗等特点; 而作为一种实时操作系统,它与通用操作系统(如Windows、Unix、Linux等)相比有很大的 差别,下面我们通过比较这两种操作系统之间的差距来描述实时操作系统的主要特点。

最常用的操作系统是通用操作系统,通用操作系统是由分时操作系统发展而来,大部分都支持多用户和多进程,负责管理众多的进程并为它们分配系统资源。

分时操作系统的基本设计原则是:尽量缩短系统的平均响应时间并提高系统的吞吐率,在单位时间内为尽可能多的用户请求提供服务。由此可以看出,分时操作系统注重平均表现性能,不注重个体表现性能。如对于整个系统来说,注重所有任务的平均响应时间而不关心单个任务的响应时间,对于单个任务来说,注重每次执行的平均响 应时间而不关心某次特定执行的响应时间。

通用操作系统中采用的很多策略和技巧都体现出了这种设计原则,如虚存管理机制中由于采用LRU等页替换算法,使得 大部分的访存需求能够快速地通过物理内存完成,只有很小一部分的访存需求需要通过调页完成,但从总体上来看,平均访存时间与不采用虚存技术相比没有很大的提高,同时又获得了虚空间可以远大于物理内存容量等好处,因此虚存技术在通用操作系统中得到了十分广泛的应用。

而对于实时操作系统,前面已经提到,它除了要满足应用的功能需求以外,更重要的是还要满足应用提出的实时性要求,而组成一个应用的众多实时任务对于实时性 的要求是各不相同的,此外实时任务之间可能还会有一些复杂的关联和同步关系,如执行顺序限制、共享资源的互斥访问要求等,这就为系统实时性的保证带来了很 大的困难。

由于实时操作系统与通用操作系统的基本设计原则差别很大,因此在很多资源调度策略的选择上以及操作系统实现的方法上两者都具有较大的差异,这些差异主要体现在以下几点:

(1)任务调度策略:

通用操作系统中的任务调度策略一般采用基于优先级的抢先式调度策略,对于优先级相同的进程则采用时间片轮转调度方式,用户进程可以通过系统调用动态地调整自己的优先级,操作系统可根据情况调整某些进程的优先级。

实时操作系统中的任务调度策略目前使用最广泛的主要可分为两种,一种是静态表驱动方式,另一种是固定优先级抢先式调度方式。

静态表驱动方式是指在系统运行前工程师根据各任务的实时要求用手工的方式或在辅助工具的帮助下生成一张任务的运行时间表,这张时间表与列车的运行时刻表类 似,指明了各任务的起始运行时间以及运行长度,运行时间表一旦生成就不再变化了,在运行时调度器只需根据这张表在指定的时刻启动相应的任务理即可。静态表 驱动方式的主要优点是:

·运行时间表是在系统运行前生成的,因此可以采用较复杂的搜索算法找到较优的调度方案:1

·运行时调度器开销较小;·系统具有非常好的可预测性,实时性验证也比较方便;

这种方式主要缺点是不灵活,需求一旦发生变化,就要重新生成整个运行时量间表。由于具有非常好的可预测性,这种方式主要用于航空航天、军事等对系统的实时性要求十分严格的领域。

固定优先级抢先式调度方式则与通用操作系统中采用的基于优先级的调度方式基本类似,但在固定优先级抢先式调度方方式中,进程的优先级是固定不变革的,并且 该优先级是在运行前通过某种优先级分配策略来指定的。这种方式的优缺点与静太表驱动方式的优缺点正好完全相反,它主要应用于一些较简单、较独立的嵌入式系 统,但随着调度理论的不断成熟和完善,这种方式也会逐渐在一些对实时性要求十分严格的领域中得到应用。目前市场上大部分的实时操作系统采用的都是这种调度 方式。

(2)内存管理:

关于虚存管理机制在上面已经进行了一些分析。为解决虚存给系统带来的不可预测性,实时操作系统一般采用如下两种方式:

·在原有虚存管理机制的基础上增加页面锁功能,用户可将关键页面锁定在内存中,从而不会被swap程序将该页面交换出内存。这种方式的优点是既得到了虚存 管理机制为软件开发带来的好处,又提高了系统的可预测性。缺点是由于TLB等机制的也是按照注重平均表现的原则进行的,因此系统的可预测性并不能完全得到 保障;

·采用静态内存划分的方式,为每个实时任务划分固定的内存区域。这种方式的优点是系统具有较好的可预测性,缺点是灵活性不够好,任务对存储器的需求一旦有变化就需要重新对内存进行划分,此外虚存管理机制所带来的好处也丧失了。

目前市场上的实时操作系统一般都采用第一种管理方式。

(3)中断处理:

在通用操作系统中,大部分外部中断都是开启的,中断处理一般由设备驱动程序来完成。由于通用操作系统中的用户进程一般都没有实时性要求,而中断处理程序直接跟硬件设备交互,可能有实时性要求,因此中断处理程序的优先级被设定为高于任何用户进程。

但对于实时操作系统采用上述的中断处理机制是不合适的。首先,外部中断是环境向实时操作系统进行的输入,它的频度是与环境变化的速率相关的,而与实时操作 系统无关。如果外部中断产生的频度不可预测,则一个实时任务在运行时被中断处理程序阻塞的时间开销也是不可预测的,从而使任务的实时性得不到保证;如果外 部中断产生的频度中可预测的,一旦某外部中断产生的频度超出其预测值(如硬件故障产生的虚假中断信号或预测值本身有误)就可能会破坏整个系统的可预测性口 其次,实时控制系统中的各用户进程一般都有实时性要求,因此中断处理程序优先级高于所有用户进程的优先级分配方式是不合适的。

一种较适合实时操作系统的中断处理方式为:除时钟中断外,屏蔽所有其它中断,中断处理程序变为周期性的轮询操作。采用这种方式的主要好处是充分保证了系统 的可预测性,主要缺点是对环境变化的响应可能不如上述矿断处理方式快。另外轮询操作在一定程度上降低了CPU的有效利用率。另一种可行的方式是:对于采用 轮询方式无法满足需求的外部事件,采用中断方式,其它时间仍然采用轮询方式。但此时中断处理程序与所以其它任务一样拥有优先级,调度器根据优先级对处于就 绪态的任务和中断处理程序统一进行处理器调度。这种方式使外部事件的响应速度加快避免了上述中断方式带来第二个问题,但第一个问题依然存在。

此外为提高时钟中断响应时间的可预测性,实时操作系统应尽可能少地屏蔽中断。

(4)共享资源的互斥访问:

通用操作系统一般采用信号量机制来解决共享资源的互斥访问问题。

对于实时操作系统,如果任务调度采用静态表驱动方式,共享资源的互斥访问问题在生成运行时间表时已经考虑到了,在运行时无需再考虑。如果任务调度采用基于 优先级的方式,则传统的信号量机制在系统运行时很容易造成优先级倒置问题,即当一个高优先级任务通过信号量机制访问共享资源时,该信号量已被一低优先级任 务占有,而这个低优先级任务在访问共享资源时可能又被其它一些中等优先级的任务抢先,因此造成高优先级任务被许多具有较低优先级的任务阻塞,实时性难以得 到保证。因此在实时操作系统中,往往对传统的信号量机制进行了一些扩展,引入了如优先级继承协议、优先级顶置协议等机制,较好地解决了优先级倒置的问题。

(5)系统调用以及系统内部操作的时间开销:

进程通过系统调用得到操作系统提供的服务,操作系统通过内部操作(加上下文切换等)来完成一些内部管理工作。为保证系统的可预测性,实时操作系统中的所有 系统调用以及系统内部操作的时间开销都应是有界的,并且该界限是一个具体的量化数值。而在通用操作系统中对这些时间开销则未做如此限制。

(6)系统的可重入性:

在通用操作系统中,核心态系统调用往往是不可重入的,当一低优先级任务调用核心态系统调用时,在该时间段内到达的高优先级任务必须等到低优先级的系统调用完成才能获得CPU,这就降低了系统的可预测性。因此,实时操作系统型中的核心态系统调用往往设计为可重入的。

(7)辅助工具:

实时操作系统额外提供了一些辅助工具,如实时任务在最坏情况下的执行时间估算工具、系统的实时性验证工具等,可帮助工程师进行系统的实时性验证工作。

此外,实时操作系统对系统硬件设计也提出了一些要求,如:

DMA 相关:

DMA是一种数据交换协议,主要作用是在无需CPU参与的情况下将数据在内存与其它外部设备间进行交换。 DMA最常用的一种实现方式被称为周期窃取(Cycle Stealing)方式,即首先遇过总线仲裁协议与CPU竞争总线控制权,在获得控制权后再根据用户预设的操作指令进行数据交换。由于这种周期窃取方式会 给用户任务带来不可预测的额外阻塞开销,所以实时操作系统往往要求系统设计时不采用DMA或采取一些可预测性更好DMA实现方式,如Time-slice method等。
[《深入理解计算机系统》第六章403页讲的不错。]
·Cache

Cache的主要作用是采用容量相对较小的快速存储部件来弥补高性能CPU与相对来说性能较低的存储器之间的性能差异,由于它可以使系统的平均表现性能得到大幅提高,因此在硬件设计中得到了极为广泛的应用。

但实时操作系统注重的不是平均表现性能,而是个体最坏情况表现,因此在对系统进行实时性验证时必须考虑实时任务运行的最坏情况,即每次访存都没有命中 Cache情况下的运行时间,所以在利用辅助工具估算实时任务在最坏情况下的执行时间,应将系统中所有的Cache功能暂时关闭,在系统实际运行时再将 Cache功能激活。除此以外,另一种较极端的做法则是在硬件设计中完全不采用Cache技术。

注1:何为嵌入式系统嵌入式系统是指将应用程序和操作系统与计算机硬件集成在一起的系统。简单的说就是系统的应用软件与系统的硬件一体化,类似与BIOS的工作万式。这种系统具育软件代码小,高度自动化,响应速度快等特点,特别适合于要求实时的和多任务的体系。

注2:实时多任务操作系统实时多任务操作系统(Real Time Operating System〉是根据操作系统的工作特性而言的。实时是指物理进程的真实时间。实地操作系统是指真奇实时性,能支持实时撞制系统工作的操作系统。真首要任 务是调度一切可利用的资源完成实时控制任务,真次才着眼于提高计算机系统的使用烈率,这种系统的重要特点是要满意对时间的限制和要求。

三种工作模式

80386处理器有3种工作模式:实模式、保护模式和虚拟86模式。实模式和虚拟86模式是为了和8086处理器兼容而设置的。在实模式 下,80386处理器就相当于一个快速的8086处理器。

保护模式是80386处理器的主要工作模式。在此方式下,80386可以寻址4GB的地址空间,同时,保护模式提供了80386先进的多任务、内存分页管理和优先级保护等机制。为了在保护模式下继续提供和8086处理器的兼 容,80386又设计了一种虚拟86模式,以便可以在保护模式的多任务条件下,有的任务运行32位程序,有的任务运行MS-DOS程序。在虚拟86模式 下,同样支持任务切换、内存分页管理和优先级,但内存的寻址方式和8086相同,也是可以寻址1MB的空间。

由此可 见,80386处理器的3种工作模式各有特点且相互联系。实模式是80386处理器工作的基础,这时80386当做一个快速的8086处理器工作。在实模 式下可以通过指令切换到保护模式,也可以从保护模式退回到实模式。虚拟86模式则以保护模式为基础,在保护模式和虚拟86模式之间可以互相切换,但不能从实模式直接进入虚拟86模式或从虚拟86模式直接退到实模式。 【实模式<->虚拟85】

 

实模式:寻址采用和8086相同的16位段和偏移量,最大寻址空间1MB(原因:20位的地址总线, 因此,也就有了以下行为:由段寄存器的内容乘以 16当做基地址,加上段内的偏移地址形成最终的物理地址,这时候它的32位地址线只使用了低20位。具体来参考http://blog.chinaunix.net/space.php?uid=20791902&do=blog&id=291989),最大分段64KB。可以使用32位指令。32位的x86 CPU用做高速的8086。

保护模式:寻址采用32位段和偏移量,最大寻址空间4GB,最大分段4GB (Pentium Pre及以后为64GB)。在保护模式下CPU可以进入虚拟8086方式,这是在保护模式下的实模式程序运行环境。

 

保护模式同实模式的根本区别是进程内存受保护与否。可寻址空间的区别只是这一原因的果。实模式将整个物理内存看成分段的区域,程序代码和数据位 于不同 区域,系统程序和用户程序没有区别对待,而且每一个指针都是指向”实在”的物理地址。这样一来,用户程序的一个指针如果指向了系统程序区域或其他用户程序 区域,并改变了值,那么对于这个被修改的系统程序或用户程序,其后果就很可能是灾难性的。为了克服这种低劣的内存管理方式,处理器厂商开发出保护模式。这 样,物理内存地址不能直接被程序访问,程序内部的地址(虚拟地址)要由操作系统转化为物理地址去访问,程序对此一无所知。
至此,进程(这时 我们可以称程序 为进程了)有了严格的边界,任何其他进程根本没有办法访问不属于自己的物理内存区域,甚至在自己的虚拟地址范围内也不是可以任意访问的,因为有一些虚拟区域已经被放进一些公共系统运行库。这些区域也不能随便修改,若修改就会有: SIGSEGV(linux 段错误);非法内存访问对话框(windows 对话框)。
CPU启动环境为16位实模式,之后可以切换到保护模式。但从保护模式无法切换回实模式。

1.   实模式 【寻址都是物理地址】

80386处理器被复位或加电的时候 以实模式启动。这时候处理器中的各寄存器以实模式的初始化值工作。80386处理器在实模式下的存储器寻址方式和8086是一样的。 在实模式下,80386处理器不能对内存进行分页管 理,所以指令寻址的地址就是内存中实际的物理地址。在实模式下,所有的段都是可以读、写和执行的。

实模式下80386不支持优先级,所 有的指令相当于工作在特权级(优先级0),所以它可以执行所有特权指令,包括读写控制寄存器CR0等。实际上,80386就是通过在实模式下初始化控制寄 存器,GDTR,LDTR,IDTR与TR等管理寄存器以及页表,然后再通过加载CR0使其中的保护模式使能位置位而进入保护模式的。实模式下不支持硬件 上的多任务切换。

实模式下的中断处理方式和8086处理器相同,也用中断向量表来定位中断服务程序地址。中断向量表的结构也和8086处理器一样,每4个字节组成一个中断向量,其中包括两个字节的段地址和两个字节的偏移地址。

从 编程的角度看,除了可以访问80386新增的一些寄存器外,实模式的80386处理器和8086有什么进步呢?其实最大的好处是可以使用80386的32 位寄存器,用32位的寄存器进行编程可以使计算程序更加简捷,加快了执行速度。比如在8086时代用16位寄存器来完成32位的乘法和除法时,要进行的步 骤实在是太多了,于是考试时出这一类的题目就成了老师们的最爱,所以那时候当学生做梦都想着让寄存器的位数快快长,现在梦想终于成真了,用32位寄存器一 条指令就可以完成(问题是老师们也发现了这个投机取巧的办法,为了达到让学生们基础扎实的目的,也把题目换成了64位的乘法和除法,所以现在晚上做的梦换 成了寄存器忽然长到了64位);其次,80386中增加的两个辅助段寄存器FS和GS在实模式下也可以使用,这样,同时可以访问的段达到了6个而不必考虑 重新装入的问题;最后,很多80386的新增指令也使一些原来不很方便的操作得以简化,如80386中可以使用下述指令进行数组访问:

mov   cx,[eax   +   ebx   *   2   +   数组基地址]

这 相当于把数组中下标为eax和ebx的项目放入cx中;ebx   *   2中的2可以是1,2,4或8,这样就可以支持8位到64位的数组。而在8086处理器中,实现相同的功能要进行一次乘法和两次加法。另外,pushad 和popad指令可以一次把所有8个通用寄存器的值压入或从堆栈中弹出,比起用下面的指令分别将8个寄存器入栈要快了很多:

push         eax

push         ebx

pop   ebx

pop   eax

当然,使用了这些新指令的程序是无法拿回到8086处理器上去执行的,因为这些指令的编码在8086处理器上是未定义的。

2.   保护模式

当 80386工作在保护模式下的时候,它的所有功能都是可用的。这时80386所有的32根地址线都可供寻址,物理寻址空间高达4   GB。在保护模式下,支持内存分页机制,提供了对虚拟内存的良好支持。虽然与8086可寻址的1   MB物理地址空间相比,80386可寻址的物理地址空间可谓很大,但实际的微机系统不可能安装如此大的物理内存。所以,为了运行大型程序和真正实现多任 务,虚拟内存是一种必需的技术。

保护模式下80386支持多任务,可以依靠硬件仅在一条指令中实现任务切换。任务环境的保护工作是由处 理器自动完成的。在保护模式下,80386处理器还支持优先级机制,不同的程序可以运行在不同的优先级上。优先级一共分0~3   4个级别,操作系统运行在最高的优先级0上,应用程序则运行在比较低的级别上;配合良好的检查机制后,既可以在任务间实现数据的安全共享也可以很好地隔离 各个任务。从实模式切换到保护模式是通过修改控制寄存器CR0的控制位PE(位0)来实现的。在这之前还需要建立保护模式必需的一些数据表,如全局描述符 表GDT和中断描述符表IDT等。

DOS操作系统运行于实模式下,而Windows操作系统运行于保护模式下。

3.   虚拟86模式

虚 拟86模式是为了在保护模式下执行8086程序而设置的。虽然80386处理器已经提供了实模式来兼容8086程序,但这时8086程序实际上只是运行得 快了一点,对CPU的资源还是独占的。在保护模式的多任务环境下运行这些程序时,它们中的很多指令和保护模式环境格格不入,如段寻址方式、对中断的处理和 I/O操作的特权问题等。为了在保护模式下工作而丢弃这些程序的代价是巨大的。设想一下,如果Windows或80386处理器推出的时候宣布不能运行以 前的MS-DOS程序,那么就等于放弃了一个巨大的软件库,Windows以及80386处理器可能就会落得和苹果机一样的下场,这是Microsoft 和Intel都不愿看到的。所以,80386处理器又设计了一个虚拟86模式。

虚拟86模式是以任务形式在保护模式上执行的,在 80386上可以同时支持由多个真正的80386任务和虚拟86模式构成的任务。在虚拟86模式下,80386支持任务切换和内存分页。在Windows 操作系统中,有一部分程序专门用来管理虚拟86模式的任务,称为虚拟86管理程序。

既然虚拟86模式以保护模式为基础,它的工作方式实 际上是实模式和保护模式的混合。为了和8086程序的寻址方式兼容,虚拟86模式采用和8086一样的寻址方式,即用段寄存器乘以16当做基址再配合偏移 地址形成线性地址,寻址空间为1   MB。但显然多个虚拟86任务不能同时使用同一位置的1   MB地址空间,否则会引起冲突。操作系统利用分页机制将不同虚拟86任务的地址空间映射到不同的物理地址上去,这样每个虚拟86任务看起来都认为自己在使 用0~1   MB的地址空间。

8086代码中有相当一部分指令在保护模式下属于特权指令,如屏蔽中断的cli和中断返回指令iret 等。这些指令在8086程序中是合法的。如果不让这些指令执行,8086代码就无法工作。为了解决这个问题,虚拟86管理程序采用模拟的方法来完成这些指 令。这些特权指令执行的时候引起了保护异常。虚拟86管理程序在异常处理程序中检查产生异常的指令,如果是中断指令,则从虚拟86任务的中断向量表中取出 中断处理程序的入口地址,并将控制转移过去;如果是危及操作系统的指令,如cli等,则简单地忽略这些指令,在异常处理程序返回的时候直接返回到下一条指 令。通过这些措施,8086程序既可以正常地运行下去,在执行这些指令的时候又觉察不到已经被虚拟86管理程序做了手脚。MS-DOS应用程序在     Windows操作系统中就是这样工作的。

——————————————————————————————————————————————————

什么是保护模式
自从1969年推出第一个微处理器以来,Intel处理器就在不断地更新换代,从8086、8088、80286,到 80386、80486、奔腾、奔腾Ⅱ、奔腾4等,其体系结构也在不断变化。80386以后,提供了一些新的功能,弥补了8086的一些缺陷。这其中包括 内存保护、多任务及使用640KB以上的内存等,并仍然保持和8086家族的兼容性。也就是说80386仍然具备了8086和80286的所有功能,但是 在功能上有了很大的增强。早期的处理器是工作在实模式之下的,80286以后引入了保护模式,而在80386以后保护模式又进行了很大的改进。在 80386中,保护模式为程序员提供了更好的保护,提供了更多的内存。事实上,保护模式的目的不是为了保护程序,而是要保护程序以外的所有程序(包括操作 系统)。
简言之,保护模式是处理器的一种最自然的模式。在这种模式下,处理器的所有指令及体系结构的所有特色都是可用的,并且能够达到最高的性能。
保护模式和实模式
从 表面上看,保护模式和实模式并没有太大的区别,二者都使用了内存段、中断和设备驱动来处理硬件,但二者有很多不同之处。我们知道,在实模式中内存被划分成 段,每个段的大小为64KB,而这样的段地址可以用16位来表示。内存段的处理是通过和段寄存器相关联的内部机制来处理的,这些段寄存器(CS、DS、 SS和ES)的内容形成了物理地址的一部分。具体来说,最终的物理地址是由16位的段地址和16位的段内偏移地址组成的。用公式表示为:
物理地址=左移4位的段地址+偏移地址。
在 保护模式下,段是通过一系列被称之为”描述符表”的表所定义的。段寄存器存储的是指向这些表的指针。用于定义内存段的表有两种:全局描述符表(GDT)和 局部描述符表(LDT)。GDT是一个段描述符数组,其中包含所有应用程序都可以使用的基本描述符。在实模式中,段长是固定的(为64KB),而在保护模 式中,段长是可变的,其最大可达4GB。LDT也是段描述符的一个数组。与GDT不同,LDT是一个段,其中存放的是局部的、不需要全局共享的段描述符。 每一个操作系统都必须定义一个GDT,而每一个正在运行的任务都会有一个相应的LDT。每一个描述符的长度是8个字节,格式如图3所示。当段寄存器被加载 的时候,段基地址就会从相应的表入口获得。描述符的内容会被存储在一个程序员不可见的影像寄存器(shadow register)之中,以便下一次同一个段可以使用该信息而不用每次都到表中提取。物理地址由16位或者32位的偏移加上影像寄存器中的基址组成。实模 式和保护模式的不同可以从图1和图2中很清楚地看出来。
此外,还有一个中断描述符表(IDT)。这些中断描述符会告诉处理器到那里可以找到中断处理程序。和实模式一样,每一个中断都有一个入口,但是这些入口的格式却完全不同。因为在切换到保护模式的过程中没有使用到IDT,所以在此就不多做介绍了。
进入保护模式
80386 有4个32位控制寄存器,名字分别为CR0、CR1、CR2和CR3。CR1是保留在未来处理器中使用的,在80386中没有定义。CR0包含系统的控制 标志,用于控制处理器的操作模式和状态。CR2和CR3是用于控制分页机制的。在此,我们关注的是CR0寄存器的PE位控制,它负责实模式和保护模式之间 的切换。当PE=1时,说明处理器运行于保护模式之下,其采用的段机制和前面所述的相应内容对应。如果PE=0,那么处理器就工作在实模式之下。
切换到保护模式,实际就是把PE位置为1。为了把系统切换到保护模式,还要做一些其它的事情。程序必须要对系统的段寄存器和控制寄存器进行初始化。把PE位置1后,还要执行跳转指令。过程简述如下:
1.创建GDT表;
2.通过置PE位为1进入保护模式;
3.执行跳转以清除在实模式下读取的任何指令。
实模式下,cpu指令访问的地址就是物理地址,形式为:段寄存器:偏移
在保护模式下,cpu可以使用分段机制和分页机制。
分段机制下使用的地址就是逻辑地址,形式为:段选择子:偏移
分页机制下使用的地址就是线性地址,形式为:0xXXXXXXXX
无论是逻辑地址还是线性地址,都要被cpu映射成物理地址。
保护模式下必须采用分段机制。在此基础上可采用分页机制。
逻辑地址被转化为线性地址,如果采用分页机制,则该线性地址通过分页机制被映射成物理地址。如果不采用分页机制,则该线性地址就是物理地址。
实模式下的物理地址只能访问1M以下空间,而保护模式下的物理地址可以访问所有32位空间。并且要注意,物理内存空间只是物理地址空间的一个部分而已。

 | 852 views | 0 comments | 0 flags | 

【转】arm交叉编译器gnueabi、none-eabi、arm-eabi、gnueabihf、gnueabi区别

命名规则

交叉编译工具链的命名规则为:arch [-vendor] [-os] [-(gnu)eabi]

  • arch - 体系架构,如ARM,MIPS
  • vendor - 工具链提供商
  • os - 目标操作系统
  • eabi - 嵌入式应用二进制接口(Embedded Application Binary Interface)

根据对操作系统的支持与否,ARM GCC可分为支持和不支持操作系统,如

  • arm-none-eabi:这个是没有操作系统的,自然不可能支持那些跟操作系统关系密切的函数,比如fork(2)。他使用的是newlib这个专用于嵌入式系统的C库。
  • arm-none-linux-eabi:用于Linux的,使用Glibc

 

 实例

1、arm-none-eabi-gcc

(ARM architecture,no vendor,not target an operating system,complies with the ARM EABI)
用于编译 ARM 架构的裸机系统(包括 ARM Linux 的 boot、kernel,不适用编译 Linux 应用 Application),一般适合 ARM7、Cortex-M 和 Cortex-R 内核的芯片使用,所以不支持那些跟操作系统关系密切的函数,比如fork(2),他使用的是 newlib 这个专用于嵌入式系统的C库。

2、arm-none-linux-gnueabi-gcc

(ARM architecture, no vendor, creates binaries that run on the Linux operating system, and uses the GNU EABI)

主要用于基于ARM架构的Linux系统,可用于编译 ARM 架构的 u-boot、Linux内核、linux应用等。arm-none-linux-gnueabi基于GCC,使用Glibc库,经过 Codesourcery 公司优化过推出的编译器。arm-none-linux-gnueabi-xxx 交叉编译工具的浮点运算非常优秀。一般ARM9、ARM11、Cortex-A 内核,带有 Linux 操作系统的会用到。

3、arm-eabi-gcc

Android ARM 编译器。

4、armcc

ARM 公司推出的编译工具,功能和 arm-none-eabi 类似,可以编译裸机程序(u-boot、kernel),但是不能编译 Linux 应用程序。armcc一般和ARM开发工具一起,Keil MDK、ADS、RVDS和DS-5中的编译器都是armcc,所以 armcc 编译器都是收费的(爱国版除外,呵呵~~)。

5、arm-none-uclinuxeabi-gcc 和 arm-none-symbianelf-gcc

arm-none-uclinuxeabi 用于uCLinux,使用Glibc。

arm-none-symbianelf 用于symbian,没用过,不知道C库是什么 。

 

Codesourcery

Codesourcery推出的产品叫Sourcery G++ Lite Edition,其中基于command-line的编译器是免费的,在官网上可以下载,而其中包含的IDE和debug 工具是收费的,当然也有30天试用版本的。

目前CodeSourcery已经由明导国际(Mentor Graphics)收购,所以原本的网站风格已经全部变为 Mentor 样式,但是 Sourcery G++ Lite Edition 同样可以注册后免费下载。

Codesourcery一直是在做ARM目标 GCC 的开发和优化,它的ARM GCC在目前在市场上非常优秀,很多 patch 可能还没被gcc接受,所以还是应该直接用它的(而且他提供Windows下[mingw交叉编译的]和Linux下的二进制版本,比较方便;如果不是很有时间和兴趣,不建议下载 src 源码包自己编译,很麻烦,Codesourcery给的shell脚本很多时候根本没办法直接用,得自行提取关键的部分手工执行,又费精力又费时间,如果想知道细节,其实不用自己编译一遍,看看他是用什么步骤构建的即可,如果你对交叉编译器感兴趣的话。

ABI 和 EABI

ABI:二进制应用程序接口(Application Binary Interface (ABI) for the ARM Architecture)。在计算机中,应用二进制接口描述了应用程序(或者其他类型)和操作系统之间或其他应用程序的低级接口。

EABI:嵌入式ABI。嵌入式应用二进制接口指定了文件格式、数据类型、寄存器使用、堆积组织优化和在一个嵌入式软件中的参数的标准约定。开发者使用自己的汇编语言也可以使用 EABI 作为与兼容的编译器生成的汇编语言的接口。

两者主要区别是,ABI是计算机上的,EABI是嵌入式平台上(如ARM,MIPS等)。

 

arm-linux-gnueabi-gcc 和 arm-linux-gnueabihf-gcc

两个交叉编译器分别适用于 armel 和 armhf 两个不同的架构,armel 和 armhf 这两种架构在对待浮点运算采取了不同的策略(有 fpu 的 arm 才能支持这两种浮点运算策略)。

其实这两个交叉编译器只不过是 gcc 的选项 -mfloat-abi 的默认值不同。gcc 的选项 -mfloat-abi 有三种值 soft、softfp、hard(其中后两者都要求 arm 里有 fpu 浮点运算单元,soft 与后两者是兼容的,但 softfp 和 hard 两种模式互不兼容):
soft: 不用fpu进行浮点计算,即使有fpu浮点运算单元也不用,而是使用软件模式。
softfp: armel架构(对应的编译器为 arm-linux-gnueabi-gcc )采用的默认值,用fpu计算,但是传参数用普通寄存器传,这样中断的时候,只需要保存普通寄存器,中断负荷小,但是参数需要转换成浮点的再计算。
hard: armhf架构(对应的编译器 arm-linux-gnueabihf-gcc )采用的默认值,用fpu计算,传参数也用fpu中的浮点寄存器传,省去了转换,性能最好,但是中断负荷高。

把以下测试使用的C文件内容保存成 mfloat.c:
#include <stdio.h>
int main(void)
{
double a,b,c;
a = 23.543;
b = 323.234;
c = b/a;
printf(“the 13/2 = %f\n”, c);
printf(“hello world !\n”);
return 0;
}

1、使用 arm-linux-gnueabihf-gcc 编译,使用“-v”选项以获取更详细的信息:
# arm-linux-gnueabihf-gcc -v mfloat.c
COLLECT_GCC_OPTIONS=’-v’ ‘-march=armv7-a’ ‘-mfloat-abi=hard’ ‘-mfpu=vfpv3-d16′ ‘-mthumb’
-mfloat-abi=hard

可看出使用hard硬件浮点模式。

2、使用 arm-linux-gnueabi-gcc 编译:
# arm-linux-gnueabi-gcc -v mfloat.c
COLLECT_GCC_OPTIONS=’-v’ ‘-march=armv7-a’ ‘-mfloat-abi=softfp’ ‘-mfpu=vfpv3-d16′ ‘-mthumb’
-mfloat-abi=softfp

可看出使用softfp模式。

 

交叉编译工具

参考资料

  1. 交叉编译器 arm-linux-gnueabi 和 arm-linux-gnueabihf 的区别:http://www.cnblogs.com/xiaotlili/p/3306100.html
  2. arm-none-linux-gnueabi,arm-none-eabi 与arm-eabi 区别:http://blog.csdn.net/mantis_1984/article/details/21049273
  3. What’s the difference between arm-linux- / arm-none-linux-gnueabi- / arm-fsl-linux-gnueabi- in LTIB?https://community.freescale.com/thread/313490

文章来自VeryARM:http://www.veryarm.com/296.html,转载请保留。

 | 836 views | 0 comments | 0 flags | 

【转】嵌入式系统 Boot Loader 技术内幕

http://www.ibm.com/developerworks/cn/linux/l-btloader/

1. 引言

在专用的嵌入式板子运行 GNU/Linux 系统已经变得越来越流行。一个嵌入式 Linux 系统从软件的角度看通常可以分为四个层次:

1. 引导加载程序。包括固化在固件(firmware)中的 boot 代码(可选),和 Boot Loader 两大部分。

2. Linux 内核。特定于嵌入式板子的定制内核以及内核的启动参数。

3. 文件系统。包括根文件系统和建立于 Flash 内存设备之上文件系统。通常用 ram disk 来作为 root fs。

4. 用户应用程序。特定于用户的应用程序。有时在用户应用程序和内核层之间可能还会包括一个嵌入式图形用户界面。常用的嵌入式 GUI 有:MicroWindows 和 MiniGUI 懂。

引导加载程序是系统加电后运行的第一段软件代码。回忆一下 PC 的体系结构我们可以知道,PC 机中的引导加载程序由 BIOS(其本质就是一段固件程序)和位于硬盘 MBR 中的 OS Boot Loader(比如,LILO 和 GRUB 等)一起组成。BIOS 在完成硬件检测和资源分配后,将硬盘 MBR 中的 Boot Loader 读到系统的 RAM 中,然后将控制权交给 OS Boot Loader。Boot Loader 的主要运行任务就是将内核映象从硬盘上读到 RAM 中,然后跳转到内核的入口点去运行,也即开始启动操作系统。

而在嵌入式系统中,通常并没有像 BIOS 那样的固件程序(注,有的嵌入式 CPU 也会内嵌一段短小的启动程序),因此整个系统的加载启动任务就完全由 Boot Loader 来完成。比如在一个基于 ARM7TDMI core 的嵌入式系统中,系统在上电或复位时通常都从地址 0×00000000 处开始执行,而在这个地址处安排的通常就是系统的 Boot Loader 程序。

本文将从 Boot Loader 的概念、Boot Loader 的主要任务、Boot Loader 的框架结构以及 Boot Loader 的安装等四个方面来讨论嵌入式系统的 Boot Loader。

回页首

2. Boot Loader 的概念

简单地说,Boot Loader 就是在操作系统内核运行之前运行的一段小程序。通过这段小程序,我们可以初始化硬件设备、建立内存空间的映射图,从而将系统的软硬件环境带到一个合适的状态,以便为最终调用操作系统内核准备好正确的环境。

通常,Boot Loader 是严重地依赖于硬件而实现的,特别是在嵌入式世界。因此,在嵌入式世界里建立一个通用的 Boot Loader 几乎是不可能的。尽管如此,我们仍然可以对 Boot Loader 归纳出一些通用的概念来,以指导用户特定的 Boot Loader 设计与实现。

1. Boot Loader 所支持的 CPU 和嵌入式板

每种不同的 CPU 体系结构都有不同的 Boot Loader。有些 Boot Loader 也支持多种体系结构的 CPU,比如 U-Boot 就同时支持 ARM 体系结构和MIPS 体系结构。除了依赖于 CPU 的体系结构外,Boot Loader 实际上也依赖于具体的嵌入式板级设备的配置。这也就是说,对于两块不同的嵌入式板而言,即使它们是基于同一种 CPU 而构建的,要想让运行在一块板子上的 Boot Loader 程序也能运行在另一块板子上,通常也都需要修改 Boot Loader 的源程序。

2. Boot Loader 的安装媒介(Installation Medium)

系统加电或复位后,所有的 CPU 通常都从某个由 CPU 制造商预先安排的地址上取指令。比如,基于 ARM7TDMI core 的 CPU 在复位时通常都从地址 0×00000000 取它的第一条指令。而基于 CPU 构建的嵌入式系统通常都有某种类型的固态存储设备(比如:ROM、EEPROM 或 FLASH 等)被映射到这个预先安排的地址上。因此在系统加电后,CPU 将首先执行 Boot Loader 程序。

下图1就是一个同时装有 Boot Loader、内核的启动参数、内核映像和根文件系统映像的固态存储设备的典型空间分配结构图。

图1 固态存储设备的典型空间分配结构

图1 固态存储设备的典型空间分配结构

3. 用来控制 Boot Loader 的设备或机制

主机和目标机之间一般通过串口建立连接,Boot Loader 软件在执行时通常会通过串口来进行 I/O,比如:输出打印信息到串口,从串口读取用户控制字符等。

4. Boot Loader 的启动过程是单阶段(Single Stage)还是多阶段(Multi-Stage)

通常多阶段的 Boot Loader 能提供更为复杂的功能,以及更好的可移植性。从固态存储设备上启动的 Boot Loader 大多都是 2 阶段的启动过程,也即启动过程可以分为 stage 1 和 stage 2 两部分。而至于在 stage 1 和 stage 2 具体完成哪些任务将在下面讨论。

5. Boot Loader 的操作模式 (Operation Mode)

大多数 Boot Loader 都包含两种不同的操作模式:”启动加载”模式和”下载”模式,这种区别仅对于开发人员才有意义。但从最终用户的角度看,Boot Loader 的作用就是用来加载操作系统,而并不存在所谓的启动加载模式与下载工作模式的区别。

启动加载(Boot loading)模式:这种模式也称为”自主”(Autonomous)模式。也即 Boot Loader 从目标机上的某个固态存储设备上将操作系统加载到 RAM 中运行,整个过程并没有用户的介入。这种模式是 Boot Loader 的正常工作模式,因此在嵌入式产品发布的时侯,Boot Loader 显然必须工作在这种模式下。

下载(Downloading)模式:在这种模式下,目标机上的 Boot Loader 将通过串口连接或网络连接等通信手段从主机(Host)下载文件,比如:下载内核映像和根文件系统映像等。从主机下载的文件通常首先被 Boot Loader 保存到目标机的 RAM 中,然后再被 Boot Loader 写到目标机上的FLASH 类固态存储设备中。Boot Loader 的这种模式通常在第一次安装内核与根文件系统时被使用;此外,以后的系统更新也会使用 Boot Loader 的这种工作模式。工作于这种模式下的 Boot Loader 通常都会向它的终端用户提供一个简单的命令行接口。

像 Blob 或 U-Boot 等这样功能强大的 Boot Loader 通常同时支持这两种工作模式,而且允许用户在这两种工作模式之间进行切换。比如,Blob 在启动时处于正常的启动加载模式,但是它会延时 10 秒等待终端用户按下任意键而将 blob 切换到下载模式。如果在 10 秒内没有用户按键,则 blob 继续启动 Linux 内核。

6. BootLoader 与主机之间进行文件传输所用的通信设备及协议

最常见的情况就是,目标机上的 Boot Loader 通过串口与主机之间进行文件传输,传输协议通常是 xmodem/ymodem/zmodem 协议中的一种。但是,串口传输的速度是有限的,因此通过以太网连接并借助 TFTP 协议来下载文件是个更好的选择。

此外,在论及这个话题时,主机方所用的软件也要考虑。比如,在通过以太网连接和 TFTP 协议来下载文件时,主机方必须有一个软件用来的提供 TFTP 服务。

在讨论了 BootLoader 的上述概念后,下面我们来具体看看 BootLoader 的应该完成哪些任务。

3. Boot Loader 的主要任务与典型结构框架

在继续本节的讨论之前,首先我们做一个假定,那就是:假定内核映像与根文件系统映像都被加载到 RAM 中运行。之所以提出这样一个假设前提是因为,在嵌入式系统中内核映像与根文件系统映像也可以直接在 ROM 或 Flash 这样的固态存储设备中直接运行。但这种做法无疑是以运行速度的牺牲为代价的。

从操作系统的角度看,Boot Loader 的总目标就是正确地调用内核来执行。

另外,由于 Boot Loader 的实现依赖于 CPU 的体系结构,因此大多数 Boot Loader 都分为 stage1 和 stage2 两大部分。依赖于 CPU 体系结构的代码,比如设备初始化代码等,通常都放在 stage1 中,而且通常都用汇编语言来实现,以达到短小精悍的目的。而 stage2 则通常用C语言来实现,这样可以实现给复杂的功能,而且代码会具有更好的可读性和可移植性。

Boot Loader 的 stage1 通常包括以下步骤(以执行的先后顺序):

  • 硬件设备初始化。
  • 为加载 Boot Loader 的 stage2 准备 RAM 空间。
  • 拷贝 Boot Loader 的 stage2 到 RAM 空间中。
  • 设置好堆栈。
  • 跳转到 stage2 的 C 入口点。

Boot Loader 的 stage2 通常包括以下步骤(以执行的先后顺序):

  • 初始化本阶段要使用到的硬件设备。
  • 检测系统内存映射(memory map)。
  • 将 kernel 映像和根文件系统映像从 flash 上读到 RAM 空间中。
  • 为内核设置启动参数。
  • 调用内核。

3.1 Boot Loader 的 stage1

3.1.1 基本的硬件初始化

这是 Boot Loader 一开始就执行的操作,其目的是为 stage2 的执行以及随后的 kernel 的执行准备好一些基本的硬件环境。它通常包括以下步骤(以执行的先后顺序):

1. 屏蔽所有的中断。为中断提供服务通常是 OS 设备驱动程序的责任,因此在 Boot Loader 的执行全过程中可以不必响应任何中断。中断屏蔽可以通过写 CPU 的中断屏蔽寄存器或状态寄存器(比如 ARM 的 CPSR 寄存器)来完成。

2. 设置 CPU 的速度和时钟频率。

3. RAM 初始化。包括正确地设置系统的内存控制器的功能寄存器以及各内存库控制寄存器等。

4. 初始化 LED。典型地,通过 GPIO 来驱动 LED,其目的是表明系统的状态是 OK 还是 Error。如果板子上没有 LED,那么也可以通过初始化 UART 向串口打印 Boot Loader 的 Logo 字符信息来完成这一点。

5. 关闭 CPU 内部指令/数据 cache。

3.1.2 为加载 stage2 准备 RAM 空间

为了获得更快的执行速度,通常把 stage2 加载到 RAM 空间中来执行,因此必须为加载 Boot Loader 的 stage2 准备好一段可用的 RAM 空间范围。

由于 stage2 通常是 C 语言执行代码,因此在考虑空间大小时,除了 stage2 可执行映象的大小外,还必须把堆栈空间也考虑进来。此外,空间大小最好是 memory page 大小(通常是 4KB)的倍数。一般而言,1M 的 RAM 空间已经足够了。具体的地址范围可以任意安排,比如 blob 就将它的 stage2 可执行映像安排到从系统 RAM 起始地址 0xc0200000 开始的 1M 空间内执行。但是,将 stage2 安排到整个 RAM 空间的最顶 1MB(也即(RamEnd-1MB) – RamEnd)是一种值得推荐的方法。

为了后面的叙述方便,这里把所安排的 RAM 空间范围的大小记为:stage2_size(字节),把起始地址和终止地址分别记为:stage2_start 和 stage2_end(这两个地址均以 4 字节边界对齐)。因此:

stage2_end=stage2_start+stage2_size

另外,还必须确保所安排的地址范围的的确确是可读写的 RAM 空间,因此,必须对你所安排的地址范围进行测试。具体的测试方法可以采用类似于 blob 的方法,也即:以 memory page 为被测试单位,测试每个 memory page 开始的两个字是否是可读写的。为了后面叙述的方便,我们记这个检测算法为:test_mempage,其具体步骤如下:

1. 先保存 memory page 一开始两个字的内容。

2. 向这两个字中写入任意的数字。比如:向第一个字写入 0×55,第 2 个字写入 0xaa。

3. 然后,立即将这两个字的内容读回。显然,我们读到的内容应该分别是 0×55 和 0xaa。如果不是,则说明这个 memory page 所占据的地址范围不是一段有效的 RAM 空间。

4. 再向这两个字中写入任意的数字。比如:向第一个字写入 0xaa,第 2 个字中写入 0×55。

5. 然后,立即将这两个字的内容立即读回。显然,我们读到的内容应该分别是 0xaa 和 0×55。如果不是,则说明这个 memory page 所占据的地址范围不是一段有效的 RAM 空间。

6. 恢复这两个字的原始内容。测试完毕。

为了得到一段干净的 RAM 空间范围,我们也可以将所安排的 RAM 空间范围进行清零操作。

3.1.3 拷贝 stage2 到 RAM 中

拷贝时要确定两点:(1) stage2 的可执行映象在固态存储设备的存放起始地址和终止地址;(2) RAM 空间的起始地址。

3.1.4 设置堆栈指针 sp

堆栈指针的设置是为了执行 C 语言代码作好准备。通常我们可以把 sp 的值设置为(stage2_end-4),也即在 3.1.2 节所安排的那个 1MB 的 RAM 空间的最顶端(堆栈向下生长)。

此外,在设置堆栈指针 sp 之前,也可以关闭 led 灯,以提示用户我们准备跳转到 stage2。

经过上述这些执行步骤后,系统的物理内存布局应该如下图2所示。

3.1.5 跳转到 stage2 的 C 入口点

在上述一切都就绪后,就可以跳转到 Boot Loader 的 stage2 去执行了。比如,在 ARM 系统中,这可以通过修改 PC 寄存器为合适的地址来实现。

图2 bootloader 的 stage2 可执行映象刚被拷贝到 RAM 空间时的系统内存布局

图2 bootloader 的 stage2 可执行映象刚被拷贝到 RAM 空间时的系统内存布局

3.2 Boot Loader 的 stage2

正如前面所说,stage2 的代码通常用 C 语言来实现,以便于实现更复杂的功能和取得更好的代码可读性和可移植性。但是与普通 C 语言应用程序不同的是,在编译和链接 boot loader 这样的程序时,我们不能使用 glibc 库中的任何支持函数。其原因是显而易见的。这就给我们带来一个问题,那就是从那里跳转进 main() 函数呢?直接把 main() 函数的起始地址作为整个 stage2 执行映像的入口点或许是最直接的想法。但是这样做有两个缺点:1)无法通过main() 函数传递函数参数;2)无法处理 main() 函数返回的情况。一种更为巧妙的方法是利用 trampoline(弹簧床)的概念。也即,用汇编语言写一段trampoline 小程序,并将这段 trampoline 小程序来作为 stage2 可执行映象的执行入口点。然后我们可以在 trampoline 汇编小程序中用 CPU 跳转指令跳入 main() 函数中去执行;而当 main() 函数返回时,CPU 执行路径显然再次回到我们的 trampoline 程序。简而言之,这种方法的思想就是:用这段 trampoline 小程序来作为 main() 函数的外部包裹(external wrapper)。

下面给出一个简单的 trampoline 程序示例(来自blob):

.text
.globl _trampoline
_trampoline:
	bl	main
	/* if main ever returns we just call it again */
	b	_trampoline

可以看出,当 main() 函数返回后,我们又用一条跳转指令重新执行 trampoline 程序――当然也就重新执行 main() 函数,这也就是 trampoline(弹簧床)一词的意思所在。

3.2.1初始化本阶段要使用到的硬件设备

这通常包括:(1)初始化至少一个串口,以便和终端用户进行 I/O 输出信息;(2)初始化计时器等。

在初始化这些设备之前,也可以重新把 LED 灯点亮,以表明我们已经进入 main() 函数执行。

设备初始化完成后,可以输出一些打印信息,程序名字字符串、版本号等。

3.2.2 检测系统的内存映射(memory map)

所谓内存映射就是指在整个 4GB 物理地址空间中有哪些地址范围被分配用来寻址系统的 RAM 单元。比如,在 SA-1100 CPU 中,从 0xC000,0000 开始的 512M 地址空间被用作系统的 RAM 地址空间,而在 Samsung S3C44B0X CPU 中,从 0x0c00,0000 到 0×1000,0000 之间的 64M 地址空间被用作系统的 RAM 地址空间。虽然 CPU 通常预留出一大段足够的地址空间给系统 RAM,但是在搭建具体的嵌入式系统时却不一定会实现 CPU 预留的全部 RAM 地址空间。也就是说,具体的嵌入式系统往往只把 CPU 预留的全部 RAM 地址空间中的一部分映射到 RAM 单元上,而让剩下的那部分预留 RAM 地址空间处于未使用状态。 由于上述这个事实,因此 Boot Loader 的 stage2 必须在它想干点什么 (比如,将存储在 flash 上的内核映像读到 RAM 空间中) 之前检测整个系统的内存映射情况,也即它必须知道 CPU 预留的全部 RAM 地址空间中的哪些被真正映射到 RAM 地址单元,哪些是处于 “unused” 状态的。

(1) 内存映射的描述

可以用如下数据结构来描述 RAM 地址空间中的一段连续(continuous)的地址范围:

typedef struct memory_area_struct {
	u32 start; /* the base address of the memory region */
	u32 size; /* the byte number of the memory region */
	int used;
} memory_area_t;

这段 RAM 地址空间中的连续地址范围可以处于两种状态之一:(1)used=1,则说明这段连续的地址范围已被实现,也即真正地被映射到 RAM 单元上。(2)used=0,则说明这段连续的地址范围并未被系统所实现,而是处于未使用状态。

基于上述 memory_area_t 数据结构,整个 CPU 预留的 RAM 地址空间可以用一个 memory_area_t 类型的数组来表示,如下所示:

memory_area_t memory_map[NUM_MEM_AREAS] = {
	[0 ... (NUM_MEM_AREAS - 1)] = {
		.start = 0,
		.size = 0,
		.used = 0
	},
};

(2) 内存映射的检测

下面我们给出一个可用来检测整个 RAM 地址空间内存映射情况的简单而有效的算法:

/* 数组初始化 */
for(i = 0; i < NUM_MEM_AREAS; i++)
	memory_map[i].used = 0;
/* first write a 0 to all memory locations */
for(addr = MEM_START; addr < MEM_END; addr += PAGE_SIZE)
	* (u32 *)addr = 0;
for(i = 0, addr = MEM_START; addr < MEM_END; addr += PAGE_SIZE) {
     /*
      * 检测从基地址 MEM_START+i*PAGE_SIZE 开始,大小为
* PAGE_SIZE 的地址空间是否是有效的RAM地址空间。
      */
     调用3.1.2节中的算法test_mempage();
     if ( current memory page isnot a valid ram page) {
		/* no RAM here */
		if(memory_map[i].used )
			i++;
		continue;
	}

	/*
	 * 当前页已经是一个被映射到 RAM 的有效地址范围
	 * 但是还要看看当前页是否只是 4GB 地址空间中某个地址页的别名?
	 */
	if(* (u32 *)addr != 0) { /* alias? */
		/* 这个内存页是 4GB 地址空间中某个地址页的别名 */
		if ( memory_map[i].used )
			i++;
		continue;
	}

	/*
	 * 当前页已经是一个被映射到 RAM 的有效地址范围
	 * 而且它也不是 4GB 地址空间中某个地址页的别名。
	 */
	if (memory_map[i].used == 0) {
		memory_map[i].start = addr;
		memory_map[i].size = PAGE_SIZE;
		memory_map[i].used = 1;
	} else {
		memory_map[i].size += PAGE_SIZE;
	}
} /* end of for (…) */

在用上述算法检测完系统的内存映射情况后,Boot Loader 也可以将内存映射的详细信息打印到串口。

3.2.3 加载内核映像和根文件系统映像

(1) 规划内存占用的布局

这里包括两个方面:(1)内核映像所占用的内存范围;(2)根文件系统所占用的内存范围。在规划内存占用的布局时,主要考虑基地址和映像的大小两个方面。

对于内核映像,一般将其拷贝到从(MEM_START+0×8000) 这个基地址开始的大约1MB大小的内存范围内(嵌入式 Linux 的内核一般都不操过 1MB)。为什么要把从 MEM_START 到 MEM_START+0×8000 这段 32KB 大小的内存空出来呢?这是因为 Linux 内核要在这段内存中放置一些全局数据结构,如:启动参数和内核页表等信息。

而对于根文件系统映像,则一般将其拷贝到 MEM_START+0×0010,0000 开始的地方。如果用 Ramdisk 作为根文件系统映像,则其解压后的大小一般是1MB。

(2)从 Flash 上拷贝

由于像 ARM 这样的嵌入式 CPU 通常都是在统一的内存地址空间中寻址 Flash 等固态存储设备的,因此从 Flash 上读取数据与从 RAM 单元中读取数据并没有什么不同。用一个简单的循环就可以完成从 Flash 设备上拷贝映像的工作:

while(count) {
	*dest++ = *src++; /* they are all aligned with word boundary */
	count -= 4; /* byte number */
};

3.2.4 设置内核的启动参数

应该说,在将内核映像和根文件系统映像拷贝到 RAM 空间中后,就可以准备启动 Linux 内核了。但是在调用内核之前,应该作一步准备工作,即:设置 Linux 内核的启动参数。

Linux 2.4.x 以后的内核都期望以标记列表(tagged list)的形式来传递启动参数。启动参数标记列表以标记 ATAG_CORE 开始,以标记 ATAG_NONE 结束。每个标记由标识被传递参数的 tag_header 结构以及随后的参数值数据结构来组成。数据结构 tag 和 tag_header 定义在 Linux 内核源码的include/asm/setup.h 头文件中:

/* The list ends with an ATAG_NONE node. */
#define ATAG_NONE	0x00000000
struct tag_header {
	u32 size; /* 注意,这里size是字数为单位的 */
	u32 tag;
};
……
struct tag {
	struct tag_header hdr;
	union {
		struct tag_core		core;
		struct tag_mem32	mem;
		struct tag_videotext	videotext;
		struct tag_ramdisk	ramdisk;
		struct tag_initrd	initrd;
		struct tag_serialnr	serialnr;
		struct tag_revision	revision;
		struct tag_videolfb	videolfb;
		struct tag_cmdline	cmdline;
		/*
		 * Acorn specific
		 */
		struct tag_acorn	acorn;
		/*
		 * DC21285 specific
		 */
		struct tag_memclk	memclk;
	} u;
};

在嵌入式 Linux 系统中,通常需要由 Boot Loader 设置的常见启动参数有:ATAG_CORE、ATAG_MEM、ATAG_CMDLINE、ATAG_RAMDISK、ATAG_INITRD等。

比如,设置 ATAG_CORE 的代码如下:

params = (struct tag *)BOOT_PARAMS;
	params->hdr.tag = ATAG_CORE;
	params->hdr.size = tag_size(tag_core);
	params->u.core.flags = 0;
	params->u.core.pagesize = 0;
	params->u.core.rootdev = 0;
	params = tag_next(params);

其中,BOOT_PARAMS 表示内核启动参数在内存中的起始基地址,指针 params 是一个 struct tag 类型的指针。宏 tag_next() 将以指向当前标记的指针为参数,计算紧临当前标记的下一个标记的起始地址。注意,内核的根文件系统所在的设备ID就是在这里设置的。

下面是设置内存映射情况的示例代码:

for(i = 0; i < NUM_MEM_AREAS; i++) {
		if(memory_map[i].used) {
			params->hdr.tag = ATAG_MEM;
			params->hdr.size = tag_size(tag_mem32);
			params->u.mem.start = memory_map[i].start;
			params->u.mem.size = memory_map[i].size;

			params = tag_next(params);
		}
}

可以看出,在 memory_map[]数组中,每一个有效的内存段都对应一个 ATAG_MEM 参数标记。

Linux 内核在启动时可以以命令行参数的形式来接收信息,利用这一点我们可以向内核提供那些内核不能自己检测的硬件参数信息,或者重载(override)内核自己检测到的信息。比如,我们用这样一个命令行参数字符串”console=ttyS0,115200n8″来通知内核以 ttyS0 作为控制台,且串口采用 “115200bps、无奇偶校验、8位数据位”这样的设置。下面是一段设置调用内核命令行参数字符串的示例代码:

char *p;
	/* eat leading white space */
	for(p = commandline; *p == ' '; p++)
		;
	/* skip non-existent command lines so the kernel will still
    * use its default command line.
	 */
	if(*p == '\0')
		return;
	params->hdr.tag = ATAG_CMDLINE;
	params->hdr.size = (sizeof(struct tag_header) + strlen(p) + 1 + 4) >> 2;
	strcpy(params->u.cmdline.cmdline, p);
	params = tag_next(params);

请注意在上述代码中,设置 tag_header 的大小时,必须包括字符串的终止符’\0′,此外还要将字节数向上圆整4个字节,因为 tag_header 结构中的size 成员表示的是字数。

下面是设置 ATAG_INITRD 的示例代码,它告诉内核在 RAM 中的什么地方可以找到 initrd 映象(压缩格式)以及它的大小:

	params->hdr.tag = ATAG_INITRD2;
	params->hdr.size = tag_size(tag_initrd);

	params->u.initrd.start = RAMDISK_RAM_BASE;
	params->u.initrd.size = INITRD_LEN;

	params = tag_next(params);

下面是设置 ATAG_RAMDISK 的示例代码,它告诉内核解压后的 Ramdisk 有多大(单位是KB):

params->hdr.tag = ATAG_RAMDISK;
params->hdr.size = tag_size(tag_ramdisk);

params->u.ramdisk.start = 0;
params->u.ramdisk.size = RAMDISK_SIZE; /* 请注意,单位是KB */
params->u.ramdisk.flags = 1; /* automatically load ramdisk */

params = tag_next(params);

最后,设置 ATAG_NONE 标记,结束整个启动参数列表:

static void setup_end_tag(void)
{
	params->hdr.tag = ATAG_NONE;
	params->hdr.size = 0;
}

3.2.5 调用内核

Boot Loader 调用 Linux 内核的方法是直接跳转到内核的第一条指令处,也即直接跳转到 MEM_START+0×8000 地址处。在跳转时,下列条件要满足:

1. CPU 寄存器的设置:

  • R0=0;
  • R1=机器类型 ID;关于 Machine Type Number,可以参见 linux/arch/arm/tools/mach-types。
  • R2=启动参数标记列表在 RAM 中起始基地址;

2. CPU 模式:

  • 必须禁止中断(IRQs和FIQs);
  • CPU 必须 SVC 模式;

3. Cache 和 MMU 的设置:

  • MMU 必须关闭;
  • 指令 Cache 可以打开也可以关闭;
  • 数据 Cache 必须关闭;

如果用 C 语言,可以像下列示例代码这样来调用内核:

void (*theKernel)(int zero, int arch, u32 params_addr) =
  (void (*)(int, int, u32))KERNEL_RAM_BASE;
……
theKernel(0, ARCH_NUMBER, (u32) kernel_params_start);

注意,theKernel()函数调用应该永远不返回的。如果这个调用返回,则说明出错。

回页首

4. 关于串口终端

在 boot loader 程序的设计与实现中,没有什么能够比从串口终端正确地收到打印信息能更令人激动了。此外,向串口终端打印信息也是一个非常重要而又有效的调试手段。但是,我们经常会碰到串口终端显示乱码或根本没有显示的问题。造成这个问题主要有两种原因:(1) boot loader 对串口的初始化设置不正确。(2) 运行在 host 端的终端仿真程序对串口的设置不正确,这包括:波特率、奇偶校验、数据位和停止位等方面的设置。

此外,有时也会碰到这样的问题,那就是:在 boot loader 的运行过程中我们可以正确地向串口终端输出信息,但当 boot loader 启动内核后却无法看到内核的启动输出信息。对这一问题的原因可以从以下几个方面来考虑:

(1) 首先请确认你的内核在编译时配置了对串口终端的支持,并配置了正确的串口驱动程序。

(2) 你的 boot loader 对串口的初始化设置可能会和内核对串口的初始化设置不一致。此外,对于诸如 s3c44b0x 这样的 CPU,CPU 时钟频率的设置也会影响串口,因此如果 boot loader 和内核对其 CPU 时钟频率的设置不一致,也会使串口终端无法正确显示信息。

(3) 最后,还要确认 boot loader 所用的内核基地址必须和内核映像在编译时所用的运行基地址一致,尤其是对于 uClinux 而言。假设你的内核映像在编译时用的基地址是 0xc0008000,但你的 boot loader 却将它加载到 0xc0010000 处去执行,那么内核映像当然不能正确地执行了。

5. 结束语

Boot Loader 的设计与实现是一个非常复杂的过程。如果不能从串口收到那激动人心的”uncompressing linux……………… done, booting the kernel……”内核启动信息,恐怕谁也不能说:”嗨,我的 boot loader 已经成功地转起来了!”。

 | 612 views | 0 comments | 0 flags | 

PLT and GOT – the key to code sharing and dynamic libraries

https://www.technovelty.org//linux/plt-and-got-the-key-to-code-sharing-and-dynamic-libraries.html

(this post was going to be about something else, but after getting this far, I think it stands on its own as an introduction to dynamic linking)

The shared library is an integral part of a modern system, but often the mechanisms behind the implementation are less well understood. There are, of course, many guides to this sort of thing. Hopefully this adds another perspective that resonates with someone.

Let’s start at the beginning — - relocations are entries in binaries that are left to be filled in later — at link time by the toolchain linker or at runtime by the dynamic linker. A relocation in a binary is a descriptor which essentially says “determine the value of X, and put that value into the binary at offset Y” — each relocation has a specific type, defined in the ABI documentation, which describes exactly how “determine the value of” is actually determined.

Here’s the simplest example:

$ cat a.c
extern int foo;

int function(void) {
    return foo;
}
$ gcc -c a.c
$ readelf --relocs ./a.o

Relocation section '.rel.text' at offset 0x2dc contains 1 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
00000004  00000801 R_386_32          00000000   foo

The value of foo is not known at the time you make a.o, so the compiler leaves behind a relocation (of type R_386_32) which is saying “in the final binary, patch the value at offset 0×4 in this object file with the address of symbol foo“. If you take a look at the output, you can see at offset 0×4 there are 4-bytes of zeros just waiting for a real address:

$ objdump --disassemble ./a.o

./a.o:     file format elf32-i386

Disassembly of section .text:

00000000 <function>:
   0:    55         push   %ebp
   1:    89 e5                  mov    %esp,%ebp
   3:    a1 00 00 00 00         mov    0x0,%eax
   8:    5d                     pop    %ebp
   9:    c3                     ret

That’s link time; if you build another object file with a value of foo and build that into a final executable, the relocation can go away. But there is a whole bunch of stuff for a fully linked executable or shared-library that just can’t be resolved until runtime. The major reason, as I shall try to explain, is position-independent code (PIC). When you look at an executable file, you’ll notice it has a fixed load address

$ readelf --headers /bin/ls
[...]
ELF Header:
[...]
  Entry point address:               0x8049bb0

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
[...]
  LOAD           0x000000 0x08048000 0x08048000 0x16f88 0x16f88 R E 0x1000
  LOAD           0x016f88 0x0805ff88 0x0805ff88 0x01543 0x01543 RW  0x1000

This is not position-independent. The code section (with permissions R E; i.e. read and execute) must be loaded at virtual address 0x08048000, and the data section (RW) must be loaded above that at exactly 0x0805ff88.

This is fine for an executable, because each time you start a new process (fork and exec) you have your own fresh address space. Thus it is a considerable time saving to pre-calculate addresses from and have them fixed in the final output (you can make position-independent executables, but that’s another story).

This is not fine for a shared library (.so). The whole point of a shared library is that applications pick-and-choose random permutations of libraries to achieve what they want. If your shared library is built to only work when loaded at one particular address everything may be fine — until another library comes along that was built also using that address. The problem is actually somewhat tractable — you can just enumerate every single shared library on the system and assign them all unique address ranges, ensuring that whatever combinations of library are loaded they never overlap. This is essentially whatprelinking does (although that is a hint, rather than a fixed, required address base). Apart from being a maintenance nightmare, with 32-bit systems you rapidly start to run out of address-space if you try to give every possible library a unique location. Thus when you examine a shared library, they do not specify a particular base address to be loaded at:

$ readelf --headers /lib/libc.so.6
Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
[...]
  LOAD           0x000000 0x00000000 0x00000000 0x236ac 0x236ac R E 0x1000
  LOAD           0x023edc 0x00024edc 0x00024edc 0x0015c 0x001a4 RW  0x1000

Shared libraries also have a second goal — code sharing. If a hundred processes use a shared library, it makes no sense to have 100 copies of the code in memory taking up space. If the code is completely read-only, and hence never, ever, modified, then every process can share the same code. However, we have the constraint that the shared library must still have a unqiue data instance in each process. While it would be possible to put the library data anywhere we want at runtime, this would require leaving behind relocations to patch the code and inform it where to actually find the data — destroying the always read-only property of the code and thus sharability. As you can see from the above headers, the solution is that the read-write data section is always put at a known offset from the code section of the library. This way, via the magic of virtual-memory, every process sees its own data section but can share the unmodified code. All that is needed to access data is some simple maths; address of thing I want = my current address + known fixed offset.

Well, simple maths is all relative! “My current address” may or may not be easy to find. Consider the following:

$ cat test.c
static int foo = 100;

int function(void) {
    return foo;
}
$ gcc -fPIC -shared -o libtest.so test.c

So foo will be in data, at a fixed offset from the code in function, and all we need to do is find it! On amd64, this is quite easy, check the disassembly:

000000000000056c <function>:
 56c:        55         push   %rbp
 56d:        48 89 e5               mov    %rsp,%rbp
 570:        8b 05 b2 02 20 00      mov    0x2002b2(%rip),%eax        # 200828 <foo>
 576:        5d                     pop    %rbp

This says “put the value at offset 0x2002b2 from the current instruction pointer (%rip) into %eax. That’s it — we know the data is at that fixed offset so we’re done. i386, on the other hand, doesn’t have the ability to offset from the current instruction pointer. Some trickery is required there:

0000040c <function>:
 40c:    55         push   %ebp
 40d:    89 e5                  mov    %esp,%ebp
 40f:    e8 0e 00 00 00         call   422 <__i686.get_pc_thunk.cx>
 414:    81 c1 5c 11 00 00      add    $0x115c,%ecx
 41a:    8b 81 18 00 00 00      mov    0x18(%ecx),%eax
 420:    5d                     pop    %ebp
 421:    c3                     ret

00000422 <__i686.get_pc_thunk.cx>:
 422:    8b 0c 24       mov    (%esp),%ecx
 425:    c3                     ret

The magic here is __i686.get_pc_thunk.cx. The architecture does not let us get the current instruction address, but we can get a known fixed address — the value __i686.get_pc_thunk.cx pushes into cx is the return value from the call, i.e in this case 0x414. Then we can do the maths for the add instruction; 0x115c + 0x414 = 0x1570, the final move goes 0x18 bytes past that to 0x1588 … checking the disassembly

00001588 <global>:
    1588:       64 00 00                add    %al,%fs:(%eax)

i.e., the value 100 in decimal, stored in the data section.

We are getting closer, but there are still some issues to deal with. If a shared library can be loaded at any address, then how does an executable, or other shared library, know how to access data or call functions in it? We could, theoretically, load the library and patch up any data references or calls into that library; however as just described this would destroy code-sharability. As we know, all problems can be solved with a layer of indirection, in this case called global offset table or GOT.

Consider the following library:

$ cat test.c
extern int foo;

int function(void) {
    return foo;
}
$ gcc -shared -fPIC -o libtest.so test.c

Note this looks exactly like before, but in this case the foo is extern; presumably provided by some other library. Let’s take a closer look at how this works, on amd64:

$ objdump --disassemble libtest.so
[...]
00000000000005ac <function>:
 5ac:        55         push   %rbp
 5ad:        48 89 e5               mov    %rsp,%rbp
 5b0:        48 8b 05 71 02 20 00   mov    0x200271(%rip),%rax        # 200828 <_DYNAMIC+0x1a0>
 5b7:        8b 00                  mov    (%rax),%eax
 5b9:        5d                     pop    %rbp
 5ba:        c3                     retq

$ readelf --sections libtest.so
Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
[...]
  [20] .got              PROGBITS         0000000000200818  00000818
       0000000000000020  0000000000000008  WA       0     0     8

$ readelf --relocs libtest.so
Relocation section '.rela.dyn' at offset 0x418 contains 5 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
[...]
000000200828  000400000006 R_X86_64_GLOB_DAT 0000000000000000 foo + 0

The disassembly shows that the value to be returned is loaded from an offset of 0x200271 from the current %rip; i.e. 0x0200828. Looking at the section headers, we see that this is part of the .got section. When we examine the relocations, we see aR_X86_64_GLOB_DAT relocation that says “find the value of symbol foo and put it into address 0x200828.

So, when this library is loaded, the dynamic loader will examine the relocation, go and find the value of foo and patch the .gotentry as required. When it comes time for the code loads to load that value, it will point to the right place and everything just works; without having to modify any code values and thus destroy code sharability.

This handles data, but what about function calls? The indirection used here is called a procedure linkage table or PLT. Code does not call an external function directly, but only via a PLT stub. Let’s examine this:

$ cat test.c
int foo(void);

int function(void) {
    return foo();
}
$ gcc -shared -fPIC -o libtest.so test.c

$ objdump --disassemble libtest.so
[...]
00000000000005bc <function>:
 5bc:        55         push   %rbp
 5bd:        48 89 e5               mov    %rsp,%rbp
 5c0:        e8 0b ff ff ff         callq  4d0 <foo@plt>
 5c5:        5d                     pop    %rbp

$ objdump --disassemble-all libtest.so
00000000000004d0 <foo@plt>:
 4d0:   ff 25 82 03 20 00       jmpq   *0x200382(%rip)        # 200858 <_GLOBAL_OFFSET_TABLE_+0x18>
 4d6:   68 00 00 00 00          pushq  $0x0
 4db:   e9 e0 ff ff ff          jmpq   4c0 <_init+0x18>

$ readelf --relocs libtest.so
Relocation section '.rela.plt' at offset 0x478 contains 2 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000200858  000400000007 R_X86_64_JUMP_SLO 0000000000000000 foo + 0

So, we see that function makes a call to code at 0x4d0. Disassembling this, we see an interesting call, we jump to the value stored in 0x200382 past the current %rip (i.e. 0x200858), which we can then see the relocation for — the symbol foo.

It is interesting to keep following this through; let’s look at the initial value that is jumped to:

$ objdump --disassemble-all libtest.so

Disassembly of section .got.plt:

0000000000200840 <.got.plt>:
  200840:       98                      cwtl
  200841:       06                      (bad)
  200842:       20 00                   and    %al,(%rax)
        ...
  200858:       d6                      (bad)
  200859:       04 00                   add    $0x0,%al
  20085b:       00 00                   add    %al,(%rax)
  20085d:       00 00                   add    %al,(%rax)
  20085f:       00 e6                   add    %ah,%dh
  200861:       04 00                   add    $0x0,%al
  200863:       00 00                   add    %al,(%rax)
  200865:       00 00                   add    %al,(%rax)
        ...

Unscrambling 0x200858 we see its initial value is 0x4d6 — i.e. the next instruction! Which then pushes the value 0 and jumps to0x4c0. Looking at that code we can see it pushes a value from the GOT, and then jumps to a second value in the GOT:

00000000000004c0 <foo@plt-0x10>:
 4c0:   ff 35 82 03 20 00       pushq  0x200382(%rip)        # 200848 <_GLOBAL_OFFSET_TABLE_+0x8>
 4c6:   ff 25 84 03 20 00       jmpq   *0x200384(%rip)        # 200850 <_GLOBAL_OFFSET_TABLE_+0x10>
 4cc:   0f 1f 40 00             nopl   0x0(%rax)

What’s going on here? What’s actually happening is lazy binding — by convention when the dynamic linker loads a library, it will put an identifier and resolution function into known places in the GOT. Therefore, what happens is roughly this: on the first call of a function, it falls through to call the default stub, which loads the identifier and calls into the dynamic linker, which at that point has enough information to figure out “hey, this libtest.so is trying to find the function foo“. It will go ahead and find it, and then patch the address into the GOT such that the next time the original PLT entry is called, it will load the actual address of the function, rather than the lookup stub. Ingenious!

Out of this indirection falls another handy thing — the ability to modify the symbol binding order. LD_PRELOAD, for example, simply tells the dynamic loader it should insert a library as first to be looked-up for symbols; therefore when the above binding happens if the preloaded library declares a foo, it will be chosen over any other one provided.

In summary — code should be read-only always, and to make it so that you can still access data from other libraries and call external functions these accesses are indirected through a GOT and PLT which live at compile-time known offsets.

In a future post I’ll discuss some of the security issues around this implementation, but that post won’t make sense unless I can refer back to this one :)

 | 625 views | 0 comments | 0 flags | 

[Pthread] Linux中的线程同步机制 — Futex

http://blog.csdn.net/Javadino/article/details/2891385

引子
在编译2.6内核的时候,你会在编译选项中看到[*] Enable futex support这一项,上网查,有的资料会告诉你”不选这个内核不一定能正确的运行使用glibc的程序”,那futex是什么?和glibc又有什么关系呢?

1. 什么是Futex
Futex是Fast Userspace muTexes的缩写,由Hubertus Franke, Matthew Kirkwood, Ingo Molnar and Rusty Russell共同设计完成。几位都是linux领域的专家,其中可能Ingo Molnar大家更熟悉一些,毕竟是O(1)调度器和CFS的实现者。

Futex按英文翻译过来就是快速用户空间互斥体。其设计思想其实不难理解,在传统的Unix系统中,System V IPC(inter process communication),如 semaphores, msgqueues, sockets还有文件锁机制(flock())等进程间同步机制都是对一个内核对象操作来完成的,这个内核对象对要同步的进程都是可见的,其提供了共享的状态信息和原子操作。当进程间要同步的时候必须要通过系统调用(如semop())在内核中完成。可是经研究发现,很多同步是无竞争的,即某个进程进入互斥区,到再从某个互斥区出来这段时间,常常是没有进程也要进这个互斥区或者请求同一同步变量的。但是在这种情况下,这个进程也要陷入内核去看看有没有人和它竞争,退出的时侯还要陷入内核去看看有没有进程等待在同一同步变量上。这些不必要的系统调用(或者说内核陷入)造成了大量的性能开销。为了解决这个问题,Futex就应运而生,Futex是一种用户态和内核态混合的同步机制。首先,同步的进程间通过mmap共享一段内存,futex变量就位于这段共享的内存中且操作是原子的,当进程尝试进入互斥区或者退出互斥区的时候,先去查看共享内存中的futex变量,如果没有竞争发生,则只修改futex,而不用再执行系统调用了。当通过访问futex变量告诉进程有竞争发生,则还是得执行系统调用去完成相应的处理(wait 或者 wake up)。简单的说,futex就是通过在用户态的检查,如果了解到没有竞争就不用陷入内核了,大大提高了low-contention时候的效率。Linux从2.5.7开始支持Futex。

2. Futex系统调用
Futex是一种用户态和内核态混合机制,所以需要两个部分合作完成,linux上提供了sys_futex系统调用,对进程竞争情况下的同步处理提供支持。
其原型和系统调用号为
#include <linux/futex.h>
#include <sys/time.h>
int futex (int *uaddr, int op, int val, const struct timespec *timeout,int *uaddr2, int val3);
#define __NR_futex              240

虽然参数有点长,其实常用的就是前面三个,后面的timeout大家都能理解,其他的也常被ignore。
uaddr就是用户态下共享内存的地址,里面存放的是一个对齐的整型计数器。
op存放着操作类型。定义的有5中,这里我简单的介绍一下两种,剩下的感兴趣的自己去man futex
FUTEX_WAIT: 原子性的检查uaddr中计数器的值是否为val,如果是则让进程休眠,直到FUTEX_WAKE或者超时(time-out)。也就是把进程挂到uaddr相对应的等待队列上去。
FUTEX_WAKE: 最多唤醒val个等待在uaddr上进程。

可见FUTEX_WAIT和FUTEX_WAKE只是用来挂起或者唤醒进程,当然这部分工作也只能在内核态下完成。有些人尝试着直接使用futex系统调用来实现进程同步,并寄希望获得futex的性能优势,这是有问题的。应该区分futex同步机制和futex系统调用。futex同步机制还包括用户态下的操作,我们将在下节提到。

3. Futex同步机制
所有的futex同步操作都应该从用户空间开始,首先创建一个futex同步变量,也就是位于共享内存的一个整型计数器。
当进程尝试持有锁或者要进入互斥区的时候,对futex执行”down”操作,即原子性的给futex同步变量减1。如果同步变量变为0,则没有竞争发生,进程照常执行。如果同步变量是个负数,则意味着有竞争发生,需要调用futex系统调用的futex_wait操作休眠当前进程。
当进程释放锁或者要离开互斥区的时候,对futex进行”up”操作,即原子性的给futex同步变量加1。如果同步变量由0变成1,则没有竞争发生,进程照常执行。如果加之前同步变量是负数,则意味着有竞争发生,需要调用futex系统调用的futex_wake操作唤醒一个或者多个等待进程。

这里的原子性加减通常是用CAS(Compare and Swap)完成的,与平台相关。CAS的基本形式是:CAS(addr,old,new),当addr中存放的值等于old时,用new对其替换。在x86平台上有专门的一条指令来完成它: cmpxchg。

可见: futex是从用户态开始,由用户态和核心态协调完成的。

4. 进/线程利用futex同步
进程或者线程都可以利用futex来进行同步。
对于线程,情况比较简单,因为线程共享虚拟内存空间,虚拟地址就可以唯一的标识出futex变量,即线程用同样的虚拟地址来访问futex变量。
对于进程,情况相对复杂,因为进程有独立的虚拟内存空间,只有通过mmap()让它们共享一段地址空间来使用futex变量。每个进程用来访问futex的虚拟地址可以是不一样的,只要系统知道所有的这些虚拟地址都映射到同一个物理内存地址,并用物理内存地址来唯一标识futex变量。

小结:
1. Futex变量的特征:1)位于共享的用户空间中 2)是一个32位的整型 3)对它的操作是原子的
2. Futex在程序low-contention的时候能获得比传统同步机制更好的性能。
3. 不要直接使用Futex系统调用。
4. Futex同步机制可以用于进程间同步,也可以用于线程间同步。

那么应该如何使用Futex,它和glibc又有什么关系呢?下次继续。

在linux中进行多线程开发,同步是不可回避的一个问题。在POSIX标准中定义了三种线程同步机制: Mutexes(互斥量), Condition Variables(条件变量)和POSIX Semaphores(信号量)。NPTL基本上实现了POSIX,而glibc又使用NPTL作为自己的线程库。因此glibc中包含了这三种同步机制的实现(当然还包括其他的同步机制,如APUE里提到的读写锁)。

Glibc中常用的线程同步方式举例:

Semaphore:
变量定义:    sem_t sem;
初始化:      sem_init(&sem,0,1);
进入加锁:     sem_wait(&sem);
退出解锁:     sem_post(&sem);

Mutex:
变量定义:    pthread_mutex_t mut;
初始化:      pthread_mutex_init(&mut,NULL);
进入加锁:     pthread_mutex_lock(&mut);
退出解锁:     pthread_mutex_unlock(&mut);

这些用于同步的函数和futex有什么关系?下面让我们来看一看:
以Semaphores为例,
进入互斥区的时候,会执行sem_wait(sem_t *sem),sem_wait的实现如下:
int sem_wait (sem_t *sem)
{
int *futex = (int *) sem;
if (atomic_decrement_if_positive (futex) > 0)
return 0;
int   err = lll_futex_wait (futex, 0);
return -1;
)
atomic_decrement_if_positive()的语义就是如果传入参数是正数就将其原子性的减一并立即返回。如果信号量为正,在Semaphores的语义中意味着没有竞争发生,如果没有竞争,就给信号量减一后直接返回了。

如果传入参数不是正数,即意味着有竞争,调用lll_futex_wait(futex,0),lll_futex_wait是个宏,展开后为:
#define lll_futex_wait(futex, val) /
({                                          /

__asm __volatile (LLL_EBX_LOAD                          /
LLL_ENTER_KERNEL                          /
LLL_EBX_LOAD                          /
: “=a” (__status)                          /
: “0″ (SYS_futex), LLL_EBX_REG (futex), “S” (0),          /
“c” (FUTEX_WAIT), “d” (_val),                  /
“i” (offsetof (tcbhead_t, sysinfo))              /
: “memory”);                          /
…                                      /
})
可以看到当发生竞争的时候,sem_wait会调用SYS_futex系统调用,并在val=0的时候执行FUTEX_WAIT,让当前线程休眠。

从这个例子我们可以看出,在Semaphores的实现过程中使用了futex,不仅仅是说其使用了futex系统调用(再重申一遍只使用futex系统调用是不够的),而是整个建立在futex机制上,包括用户态下的操作和核心态下的操作。其实对于其他glibc的同步机制来说也是一样,都采纳了futex作为其基础。所以才会在futex的manual中说:对于大多数程序员不需要直接使用futexes,取而代之的是依靠建立在futex之上的系统库,如NPTL线程库(most programmers will in fact not be using futexes directly but instead rely on system libraries built on them, such as the NPTL pthreads implementation)。所以才会有如果在编译内核的时候不 Enable futex support,就”不一定能正确的运行使用Glibc的程序”。

小结:
1. Glibc中的所提供的线程同步方式,如大家所熟知的Mutex,Semaphore等,大多都构造于futex之上了,除了特殊情况,大家没必要再去实现自己的futex同步原语。
2. 大家要做的事情,似乎就是按futex的manual中所说得那样: 正确的使用Glibc所提供的同步方式,并在使用它们的过程中,意识到它们是利用futex机制和linux配合完成同步操作就可以了。

如果只是阅读理解,到这里也就够了,不过我们需要用实际行动印证一下,我们的理解是否正确。在实际使用过程中还遇到什么样的问题? 下次继续。

上回说到Glibc中(NPTL)的线程同步方式如Mutex,Semaphore等都使用了futex作为其基础。那么实际使用是什么样子,又会碰到什么问题呢?
先来看一个使用semaphore同步的例子。

sem_t sem_a;
void *task1();

int main(void){
int ret=0;
pthread_t thrd1;
sem_init(&sem_a,0,1);
ret=pthread_create(&thrd1,NULL,task1,NULL); //创建子线程
pthread_join(thrd1,NULL); //等待子线程结束
}

void *task1()
{
int sval = 0;
sem_wait(&sem_a); //持有信号量
sleep(5); //do_nothing
sem_getvalue(&sem_a,&sval);
printf(“sem value = %d/n”,sval);
sem_post(&sem_a); //释放信号量
}

程序很简单,我们在主线程(执行main的线程)中创建了一个线程,并用join等待其结束。在子线程中,先持有信号量,然后休息一会儿,再释放信号量,结束。
因为这段代码中只有一个线程使用信号量,也就是没有线程间竞争发生,按照futex的理论,因为没有竞争,所以所有的锁操作都将在用户态中完成,而不会执行系统调用而陷入内核。我们用strace来跟踪一下这段程序的执行过程中所发生的系统调用:

20533 futex(0xb7db1be8, FUTEX_WAIT, 20534, NULL <unfinished …>
20534 futex(0×8049870, FUTEX_WAKE, 1)   = 0
20533 <… futex resumed> )             = 0

20533是main线程的id,20534是其子线程的id。出乎我们意料之外的是这段程序还是发生了两次futex系统调用,我们来分析一下这分别是什么原因造成的。

1. 出人意料的”sem_post()”
20534 futex(0×8049870, FUTEX_WAKE, 1)   = 0
子线程还是执行了FUTEX_WAKE的系统调用,就是在sem_post(&sem_a);的时候,请求内核唤醒一个等待在sem_a上的线程,其返回值是0,表示现在并没有线程等待在sem_a(这是当然的,因为就这么一个线程在使用sem_a),这次futex系统调用白做了。这似乎和futex的理论有些出入,我们再来看一下sem_post的实现。
int sem_post (sem_t *sem)
{
int *futex = (int *) sem;
int nr = atomic_increment_val (futex);
int err = lll_futex_wake (futex, nr);
return 0;
}
我们看到,Glibc在实现sem_post的时候给futex原子性的加上1后,不管futex的值是什么,都执行了lll_futex_wake(),即futex(FUTEX_WAKE)系统调用。
在第二部分中(见前文),我们分析了sem_wait的实现,当没有竞争的时候是不会有futex调用的,现在看来真的是这样,但是在sem_post的时候,无论有无竞争,都会调用sys_futex(),为什么会这样呢?我觉得应该结合semaphore的语义来理解。在semaphore的语义中,sem_wait()的意思是:”挂起当前进程,直到semaphore的值为非0,它会原子性的减少semaphore计数值。” 我们可以看到,semaphore中是通过0或者非0来判断阻塞或者非阻塞线程。即无论有多少线程在竞争这把锁,只要使用了semaphore,semaphore的值都会是0。这样,当线程推出互斥区,执行sem_post(),释放semaphore的时候,将其值由0改1,并不知道是否有线程阻塞在这个semaphore上,所以只好不管怎么样都执行futex(uaddr, FUTEX_WAKE, 1)尝试着唤醒一个进程。而相反的,当sem_wait(),如果semaphore由1变0,则意味着没有竞争发生,所以不必去执行futex系统调用。我们假设一下,如果抛开这个语义,如果允许semaphore值为负,则也可以在sem_post()的时候,实现futex机制。

2. 半路杀出的”pthread_join()”
那另一个futex系统调用是怎么造成的呢? 是因为pthread_join();
在Glibc中,pthread_join也是用futex系统调用实现的。程序中的pthread_join(thrd1,NULL); 就对应着
20533 futex(0xb7db1be8, FUTEX_WAIT, 20534, NULL <unfinished …>
很好解释,主线程要等待子线程(id号20534上)结束的时候,调用futex(FUTEX_WAIT),并把var参数设置为要等待的子线程号(20534),然后等待在一个地址为0xb7db1be8的futex变量上。当子线程结束后,系统会负责把主线程唤醒。于是主线程就
20533 <… futex resumed> )             = 0
恢复运行了。
要注意的是,如果在执行pthread_join()的时候,要join的线程已经结束了,就不会再调用futex()阻塞当前进程了。

3. 更多的竞争。
我们把上面的程序稍微改改:
在main函数中:
int main(void){

sem_init(&sem_a,0,1);
ret=pthread_create(&thrd1,NULL,task1,NULL);
ret=pthread_create(&thrd2,NULL,task1,NULL);
ret=pthread_create(&thrd3,NULL,task1,NULL);
ret=pthread_create(&thrd4,NULL,task1,NULL);
pthread_join(thrd1,NULL);
pthread_join(thrd2,NULL);
pthread_join(thrd3,NULL);
pthread_join(thrd4,NULL);

}

这样就有更的线程参与sem_a的争夺了。我们来分析一下,这样的程序会发生多少次futex系统调用。
1) sem_wait()
第一个进入的线程不会调用futex,而其他的线程因为要阻塞而调用,因此sem_wait会造成3次futex(FUTEX_WAIT)调用。
2) sem_post()
所有线程都会在sem_post的时候调用futex, 因此会造成4次futex(FUTEX_WAKE)调用。
3) pthread_join()
别忘了还有pthread_join(),我们是按thread1, thread2, thread3, thread4这样来join的,但是线程的调度存在着随机性。如果thread1最后被调度,则只有thread1这一次futex调用,所以pthread_join()造成的futex调用在1-4次之间。(虽然不是必然的,但是4次更常见一些)
所以这段程序至多会造成3+4+4=11次futex系统调用,用strace跟踪,验证了我们的想法。
19710 futex(0xb7df1be8, FUTEX_WAIT, 19711, NULL <unfinished …>
19712 futex(0×8049910, FUTEX_WAIT, 0, NULL <unfinished …>
19713 futex(0×8049910, FUTEX_WAIT, 0, NULL <unfinished …>
19714 futex(0×8049910, FUTEX_WAIT, 0, NULL <unfinished …>
19711 futex(0×8049910, FUTEX_WAKE, 1 <unfinished …>
19710 futex(0xb75f0be8, FUTEX_WAIT, 19712, NULL <unfinished …>
19712 futex(0×8049910, FUTEX_WAKE, 1 <unfinished …>
19710 futex(0xb6defbe8, FUTEX_WAIT, 19713, NULL <unfinished …>
19713 futex(0×8049910, FUTEX_WAKE, 1 <unfinished …>
19710 futex(0xb65eebe8, FUTEX_WAIT, 19714, NULL <unfinished …>
19714 futex(0×8049910, FUTEX_WAKE, 1)   = 0
(19710是主线程,19711,19712,19713,19714是4个子线程)

4. 更多的问题
事情到这里就结束了吗? 如果我们把semaphore换成Mutex试试。你会发现当自始自终没有竞争的时候,mutex会完全符合futex机制,不管是lock还是unlock都不会调用futex系统调用。有竞争的时候,第一次pthread_mutex_lock的时候不会调用futex调用,看起来还正常。但是最后一次pthread_mutex_unlock的时候,虽然已经没有线程在等待mutex了,可还是会调用futex(FUTEX_WAKE)。这又是什么原因造成的呢?留给感兴趣的同学去分析吧。

小结:
1. 虽然semaphore,mutex等同步方式构建在futex同步机制之上。然而受其语义等的限制,并没有完全按futex最初的设计实现。
2. pthread_join()等函数也是调用futex来实现的。
3. 不同的同步方式都有其不同的语义,不同的性能特征,适合于不同的场景。我们在使用过程中要知道他们的共性,也得了解它们之间的差异。这样才能更好的理解多线程场景,写出更高质量的多线程程序。

至此futex的学习就告一段落了,希望对大家有所帮助。

 | 1,310 views | 0 comments | 0 flags |