设计模式-工厂模式

工厂模式如果细分的话可以分为工厂方法,简单工厂模式和抽象工厂模式,本文对其进行一一介绍。

简单工厂模式

首先先举一个例子
需求:创建一个按钮,在不同的系统上有不同的风格.
分析,如果不用模式:

1
2
3
4
5
6
7
8
9
10
11
12
class Draw {
public function drawButton($type)
{
if($type == 'mac') {
button = new MacButton();
} else($type == 'win') {
button = new WimButton();
}

button->draw();
}
}

可以看出,这段代码也很简洁,但是我们只考虑了两种系统,当增加系统时(比如ubuntu ,centos, redhat等) 我们就会不停的添加判断分之:

1
2
3
4
5
6
7
8
if($type == 'mac') {
button = new MacButton();
} else($type == 'win') {
button = new WinButton();
} else ($type == 'ubuntu') {
...
}
...

这个条件语句就会变的不可控。为了使代码看起来更简洁,并且添加分类更容易可以进行如下改造:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Draw {
public function drawButton($type)
{
button = ButtonFactory::create($type);
button->draw();
}
}
class ButtonFactory(){
static public function create($type) {
if($type == 'mac') {
button = new MacButton();
} else($type == 'win') {
button = new WinButton();
} else ($type == 'ubuntu') {
...
}
return button;
}
}

新增了一个ButtonFactory类,负责创建button对象使对象的创建和使用进行了分离。其实PHP还可以这么写:

1
2
3
4
5
class ButtonFactory(){
static public function create($type) {
button = new $type."Button"();
}
}

用UML类图表示他们之间的关系,就是这样的:

ButtonFactory是工厂类,负责创建所需的产品类。Button时产品类,WinButton等继承Button。 Draw 是调用的类用到了工厂和产品类,与它们是关联的关系。

工厂方法

需求:还是上面的需求,随着操作系统类型的增加,我们会发现这个工厂类还是需要修改和维护,这也很容易冗余而产生问题。这时工厂方法应运而生。先看UML图:

工厂方法是针对每一种产品提供一个工厂类。通过不同的工厂实例来创建不同的产品实例。这种进一步抽象化的结果,使这种工厂方法模式可以用来允许系统在不修改具体工厂角色的情况下引进新的系统,这一特点无疑使得工厂方法模式具有超过简单工厂模式的优越性。
代码事例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class ButtonFactory {
abstruct public static function create();
}
class WinButtonFactory {
public static function create() {
return new WinButton();
}
}
class MacButtonFactory {
public static function create() {
return new MacButton();
}
}
class Button() {
abstruct public function draw();
}

class WinButton extends Button{
public function draw() {
echo "draw win button";
}
}
class MacButton extends Button{
public function draw() {
echo "draw mac button";
}
}

class Draw {
winButton = WinButtonFactory::create();
WinButton->draw();
macButton = MacButtonFactory::create();
MacButton->draw();
}

但是工厂方法存在一个问题,那就是我们如果事先不知道会需要哪一种类,需要根据情况来选择。那就又回到了第一种情况:

1
2
3
4
5
6
7
8
9
class Draw {
if($type == "win") {
$button = WinButtonFactory::create();
} else if ($type == "mac") {
$button = MacButtonFactory::create();
}
...
button->draw();
}

这时候就需要综合简单工厂和工厂方法两种模式,做出一个混合体:再创建一个简单工厂类,用来根据参数调用工厂方法创建对象。

抽象工厂

现在需求又复杂化了: 这次不光要创建按钮,还要画边框(border),画输入框(input)。
让我们再来仔细分析一下需求: 要完成一个画图的程序,这个程序要适应不同的操作系统,这个程序又有许多种元素需要画(比如按钮,边框,输入框)。这里需要注意的是,以前按钮只是一个函数,现在需要多个调用。
“工厂”是创建产品(对象)的地方,其目的是将产品的创建与产品的使用分离。抽象工厂模式的目的,是将若干抽象产品的接口与不同主题产品的具体实现分离开。这样就能在增加新的具体工厂的时候,不用修改引用抽象工厂的客户端代码。

总结

  • 简单工厂模式: 把创建对象的方法进行封装,使其使用和创建进行分离.但是每增加一个类型都要修改工厂类.
  • 工厂方法: 对每个对象创建都建立一个工厂类,当有类型增加时只需要再创建一个工厂类,不需要修改原来的代码。但是当不确定使用的工厂是哪个时,需要结合简单工厂进行选择。
  • 抽象工厂: 每个类型出了本身是一个类外,其要完成的功能比较复杂,是多个类的组合。这时就要对每个使用到的类都进行抽象,根据使用类的不同进行选择,其实是工厂方法的复杂版本。

UML类图详解

类图(the class diagram)是UML中很重要的一种静态试图,主要用途是在系统设计环节,描述各个类之间的关系。

类的表示方法

有面向对象知识的人都知道,类是一类事物的抽象。它封装了数据和行为。在UML中类的表示如下:

顶部是类的名字,中间是类的属性,底部是类的方法。

类成员

UML提供机制,以代表类的成员,如属性和方法,对他们的其他信息。
指定一个类成员的可见性(即任何属性或方法)有下列符号,必须摆在各成员的名字之前。

1
2
3
4
5
6
+         公共
- 私有
# 受保护
~ 包
/ 继承
下划线 静态

类之间的关系

类图主要是表现各个类之间的关系,他们的关系以及表示方式如下:

外部链接

继承

继承是面向对象最基本的特性,这个就不再说了,这个设计一般没有什么争议性。关系图如下:

实现

实现,是指类(class)实现一个接口(interface)的功能,接口有关的定义在PHP里参见文档对象接口。相当于C++里的抽象类。关系图如下:

依赖

依赖关系(Dependency)可以简单的理解为一个类A使用到了另一个类B,而这种使用关系是具有偶然性、临时性的、非常弱的,但是B类的变化会影响到A;表现在代码层面,为类B作为参数被类A在某个method方法中使用;用带燕尾箭头的虚线表示。

关联

一个关联(Association)代表一个家族的联系。
关联可以命名,并结束一个关联可以饰以角色名称,所有权指标,多重性,可视性,以及其他属性,如相互关联和有方向的关联。语义上是两个类、或者类与接口之间一种强依赖关系,是一种长期的稳定的关系;表现在代码层面,为被关联类以类属性的形式出现在关联类中,也可能是关联类引用了一个类 型为被关联类的全局变量;目前定义有五种不同类型的关联。双向(Bi-directional)和单向(uni-directional)的关联是最常见的。
下图中展示的关联类A引用了一个类型为被关联类B的全局变量(A关联B);

在比如人(person)与杂志(magazine)是一种关联(双向):

学生与课程的关系(通过注册关联起来):

聚合

聚合(Aggregate)是表示整体与部分的一类特殊的关联关系,是“弱”的包含(has a)关系,成分类别可以不依靠聚合类别而单独存在,可以具有各自的生命周期,部分可以属于多个整体对象,也可以为多个整体对象共享。例如,池塘与(池塘中的)鸭子。再例如教授与课程就是一种聚合关系。聚集可能不涉及两个以上的类别。图形以空心的菱形与实线来表示。

上面举的例子是家庭和孩子,家庭是整体,孩子是不分,家庭和孩子都是独立的,但是孩子又是家庭的一部分。

组成

组成(Composition)关系,是一类“强”的整体与部分的包含关(contains a)系。成分类别必须依靠合成类别而存在。整体与部分是不可分的,整体的生命周期结束也就意味着部分的生命周期结束。合成类别完全拥有成分类别,负责创建、销毁成分类别。例如汽车与化油器,又例如公司与公司部门就是一种组成关系。图形以实心的菱形与实线表示。

上面举的例子是人与大脑的关系,大脑是人的组成部分,谁也离不开谁。

参考文献:
1. UML类图关系(泛化 、继承、实现、依赖、关联、聚合、组合)
2. 类别图-维基百科

GDB使用手册

在学习C语言和学习源代码的过程中为了了解代码的运行过程,必须要DEBUG。GDB是一个不错的选择,有着强大的功能和成熟的技术。本博客记录GDB的各种使用方法,以便进行不断的学习总结。

coreseek使用手册

产生文本摘要和高亮

函数原型:

function BuildExcerpts ( $docs, $index, $words, $opts=array() )

相关文档:

(官方文档)
该函数用来产生文档片段(摘要)。连接到searchd,要求它从指定文档中产生片段(摘要),对命中词高亮,并返回结果。

  • $docs为包含各文档内容的数组。必须把需要高亮的文本内容以数组的形式传入到函数中,最后输出的是标红后的文本摘要数组。
  • $index为包含索引名字的字符串。给定索引的不同设置(例如字符集、形态学、词形等方面的设置)会被使用。
  • $words为包含需要高亮的关键字的字符串。它们会按索引的设置被处理。例如,如果英语取词干(stemming)在索引中被设置为允许,那么即使关键词是“shoe”,“shoes”这个词也会被高亮。从版本0.9.9-rc1开始,关键字可以包含通配符,与查询支持的star-syntax类似。
  • $opts为包含其他可选的高亮参数的hash表:

    • "before_match":在匹配的关键字前面插入的字符串。从版本 1.10-beta开始,可以在该字符串中使用%PASSAGE_ID%宏。该宏会被替换为当前片段的递增值。递增值的起始值默认为1,但是可以通过
    • "start_passage_id"设置覆盖。在多文档中调用时,%PASSAGE_ID%会在每篇文档中重新开始。默认为”“。
    • "after_match":在匹配的关键字后面插入的字符串。从版本1.10-beta开始,可以在该字符串中使用%PASSAGE_ID%宏。默认为 ““。
    • "chunk_separator":在摘要块(段落)之间插入的字符串。默认为” … “.
    • "limit":摘要最多包含的符号(码点)数。整数,默认为256。
    • "around":每个关键词块左右选取的词的数目。整数,默认为 5.
    • "exact_phrase":是否仅高亮精确匹配的整个查询词组,而不是单独的关键词。布尔值,默认为false.
    • "single_passage":是否仅抽取最佳的一个区块。布尔值,默认为false.
    • "use_boundaries":是否跨越由phrase_boundary选项设置的词组边界符。布尔型,默认为false.
    • "weight_order":对于抽取出的段落,要么根据相关度排序(权重下降),要么根据出现在文档中的顺序(位置递增)。布尔型,默认是false.
    • "query_mode":版本1.10-beta新增。设置将$words当作 扩展查询语法的查询处理,还是当做普通的文本字符串处理(默认行为)。例如,在查询模式时,(“one two” | “three four”)仅高亮和包含每个片段中出现”one two” 或 “three four” 的地方及相邻的部分。而在默认模式时, 每个单独出现”one”, “two”, “three”, 或 “four”的地方都会高亮。布尔型,默认是false。
    • "force_all_words":版本1.10-beta新增. 忽略摘要的长度限制直至包含所有的词汇。布尔型,默认为false.
    • "limit_passages":版本1.10-beta新增. 限制摘要中可以包含的最大区块数。整数值,默认为 0 (不限制).
    • "limit_words":版本1.10-beta新增. 限制摘要中可以包含的最大词汇数。整数值,默认为 0 (不限制).
    • "start_passage_id":版本1.10-beta新增. 设置 %PASSAGE_ID% 宏的起始值 (在before_match, after_match 字符串中检查和应用). 整数值,默认为1.
    • "load_files":版本1.10-beta新增. 设置是否将$docs作为摘要抽取来源的数据(默认行为),或者将其当做文件名。从版本2.0.1-beta开始,如果该标志启用,每个请求将创建最多dist_threads个工作线程进行并发处理。布尔型,默认为false.
    • "html_strip_mode":版本1.10-beta新增. HTML标签剥离模式设置。默认为”index”,表示使用index的设置。可以使用的其他值为”none”和”strip”,用于强制跳过或者应用剥离,而不管索引如何设置的。还可以使用”retain”,表示保留HTMK标签并防止高亮时打断标签。”retain”模式仅用于需要高亮整篇文档,并且不能设置限制片段的大小。字符型,可用值为”none”,”strip”,”index”或者”retain”。
    • "allow_empty":版本1.10-beta新增. 允许无法产生摘要时将空字符串作为高亮结果返回 (没有关键字匹配或者不符合片段限制。). 默认情况下,原始文本的开头会被返回而不是空字符串。布尔型,默认为false.
    • "passage_boundary":版本2.0.1-beta新增. 确保区块不跨越句子,段落或者zone区域(仅当每个索引的设置启用时有效)。字符型,可用值为 “sentence”, “paragraph”, 或者 “zone”.”emit_zones”:版本2.0.1-beta新增. 在每个区块前使用区域对应的HTML标签来封闭区域。布尔型,魔默认为false。

      摘要提取算法倾向于提取更好的片段(与关键词完全匹配),然后是不在摘要中但是包含了关键词的片段。 通常情况下,它会尝试高亮查询的最佳匹配,并且在限制条件下尽可能的高亮查询中的所有关键词。 如果文档没有匹配查询,默认情况下将根据限制条件返回文档的头部。从版本1.10-beta开始,可以通过设置allow_empty属性位true以返回空的片段来替代默认方式。
      失败时返回false。成功时返回包含有片段(摘要)字符串的数组。

使用方法

代码片段:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
<?php
//...略
include("SphinxClient.php");
class test{


protected function make_words_highLight($source,$kw){


$cll = new SphinxClient ();
$opts = array
(
"before_match" => "<span style='color:red'>",
"after_match" => "</span>",
"chunk_separator" => " ... ",
"limit" => 10,
"around" => 6,
);
$index = "test1";
return $cll->BuildExcerpts($source,$index,$kw,$opts);
}


//test
public function test(){
$content = array("北京是中华人民共和国的首都","中国的首都是北京,2008奥运会就在这里举办的","京东老板刘强东");
$qsKey = "北京 东";
$contentArr = $this->make_words_highLight($content,$qsKey);
print_r($contentArr);die;
}
}

$m = new test();
$m->test();

?>
//输出结果
Array
(
[0] => <span style='color:red'>北京</span>是中华人民共和国 ...
[1] => ... 首都是<span style='color:red'>北京</span>,2008 ...
[2] => 京东老板刘强<span style='color:red'>东</span>
)

mmseg 同义词/复合分词处理

文档(官方文档)

mmseg 3.2.13版本开始,提供了类似复合分词的处理方式,供coreseek进行调用。
其基本使用状况为:

  • 词库包含:南京西路、南京、西路(注意,一定要加入生成uni.lib的词库中)
  • 索引时:文本中的“南京西路”会被同时索引为以上三者查
  • 查询时:输入南京西路,可以直接匹配南京西路,而不匹配南京或者西路;输入南京或者西路,也可以搜索到南京西路

用法:

  1. 处理unigram.txt(在mmseg3/etc目录下)将词库加入,利用命令mmseg -u unigram.txt 生成新的词库unigram.txt.uni,用新的词库替代老词库mv unigram.txt.uni uni.lib(ps:被替换的同义词必须加入词库中,例如想让一个没有的词测试映射同义词南京西路则需要南京西路在词库中,测试不需要加入).
  2. 生成同义词库文件mmseg-3.2.13源代码/script/build_thesaurus.py unigram.txt > thesaurus.txt(默认的同义词库,可自己修改).
    thesaurus.txt文件的格式如下:

    1
    2
    3
    4
    南京西路
    -南京,西路,
    张三丰
    -太极宗师,武当祖师,
  3. 生成同义词词典:mmseg -t thesaurus.txt. 将thesaurus.lib放到uni.lib同一目录

  4. 停止索引服务searchd,重新建立索引,然后启动searchd (ps : 如果只是加入了新的同义词映射,没有修改词表的话不需要重启服务,只需重建索引即可)
  5. coreseek索引和搜索时,会自动进行复合分词处理。搜索南京西路时都能将搜索南京西路的结果匹配到

csapp chapter8:异常控制流

程序运行的顺序是根据程序计数器(PC)的值而定的,PC从一个地址到另一个地址的过渡称为控制转移(control transfer),这样的控制转移序列叫做处理器的控制流(flow of control或 control flow)。一般如果PC是按照顺序地址进行过渡的,控制流是一个平滑的序列,但是有些情况下PC是来回跳转的,这些突变称为异常控制流(Exceptional Control Flow 简称EFC),EFC发生在计算机系统的各个层次。本章主要分析这种异常控制流。

异常

异常(exception)就是控制流中的突变,用来响应处理器状态中的某些变化。
下面通过一个图来理解异常.

可以看到程序在执行到 \(I_{curr}\) 时发生了一个异常,导致程序从原来该执行 \(I_{next}\) ,变为了执行异常处理, 在执行完异常出理由程序后有下面三种可能:

  • 处理程序将控制返回给当前指令\(I_{curr}\), 即当事件发生时正在执行的命令。
  • 处理程序将控制权返回给\(I_{next}\), 即如果没有发生异常将会执行的下一条指令。
  • 处理程序终止被中断的程序。

在任何情况下,当处理器检测到有事件发生时,它就会通过一张异常表的跳转表,进行一个间接过程调用(异常),到一个专门设计用来处理这类事件的操作系统子程序(异常处理程序(exception handler))。

异常处理

系统为每个异常的类型都分配了一个唯一的非负整数的异常号(exception number), 每个异常处理号都对应了一个异常处理程序,这些异常处理程序有些是处理器设计者分配的,有些事操作系统内核的设计者分配的,前者主要包括被零除,缺页,存储器访问违例、断点以及算术溢出,后者主要包括系统调用和来自外部I/O设备的信号。
在系统启动时,操作系统分配和初始化一张称为异常表的跳转表,如下:

这个图显示了如何利用根据异常号来找异常处理程序,并执行。

异常与过程调用的区别

  • 异常调用时,在跳转处理器之前,处理器将返回地址压入栈中。返回地址是根据异常的类型而定的,可能是当前指令的地址,也可能是下一条指令的地址。过程调用一般入栈的是下一条指令的地址。
  • 处理器把一些额外的处理器状态压到栈里,当处理程序返回时,重新开始被中断的程序会需要这些状态。
  • 如果控制从一个用户程序转移到内核,那么所有的这些项目都被压入内核栈中,而不是压到用户栈中。
  • 异常处理程序运行在内核模式下。这意味着它们对所有的系统资源具有完全的访问权限。

异常的类别:

  • 中断:当前指令执行完后,会发现中断引脚的电压高了,就从系统总线读取处理程序。这种异常一般都是由外部的设备引起的,跟处理程序之间没有必然的联系,所以是异步的。下面的都是程序运行过程中自己有意或无意的引起的,所以事同步的行为。
  • 陷阱:是一个有意的异常,是执行一条指令引起的,引起异常的指令一般都是系统调用函数(如fork, single, exit, waitpid等),这些函数调用使程序从用户模式切换到了内核模式。
  • 故障:故障是由程序运行中的错误造成的,它能够被捕获并被故障处理程序修正。这种故障如缺页异常等。
  • 终止:这种异常一般是指不会恢复的致命错误。通常是一些硬件错误。
类别 原因 异步/同步 返回行为
中断 来自I/O设备的信号 异步 总是返回到下一条指令
陷阱 有意的异常 同步 总是返回到下一条指令
故障 潜在可恢复的错误 同步 可能返回当前指令
终止 不可恢复的错误 同步 不会返回

csapp chapter7:链接

链接(linking)是将各种代码和数据部分收集起来并组合成为一个单一文件的过程,这个文件可以被加载(或拷贝)到存储器并执行。链接可以执行于编译时(compile time),也就是在源代码被翻译成为机器代码时;也可以执行于加载时(load time),也就是在程序被加载器(loader)加载到存储器并执行时;甚至执行于运行时(rum time),由应用程序来执行。

链接器使得分离编译(separate compilation)成为可能。本章将讨论从传统静态链接到加载时的共享库的动态链接,以及到运行时的共享库的动态链接。

编译器驱动程序

通过一个例子来说明一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# main.c
void swap();
int buf[2] = {1, 2};
int main()
{
swap();
return 0;
}

# swap.c
extern int buf[];
int *bufp0 = &uf[0];
int *bufp1;

void swap()
{
int temp;
bufp1 = &buf[1];
temp = *bufp0;
*bufp0 = *bufp1;
*bufp1 = temp;
}

大多数系统提供编译驱动程序(compiler driver),它代表用户在需要时调用语言预处理器,编译器,汇编器和链接器。
运行gcc main.c swap.c -o p命令都发生了什么?

  1. 预处理器先将main.cswap.c翻译成一个ASCII码的中间文件main.iswap.i
  2. C编译器将main.iswap.i翻译成ASCII汇编语言文件main.sswap.s
  3. 汇编器将main,sswap.s翻译成可重定定位的目标文件main.oswap.o
  4. 连接器程序ld将main.oswap.o以及一些必要的系统目标文件组合起来,创建可执行目标文件p

生产了可执行文件,可以通过过./p来运行,这是由外壳调用操作系统一个叫做加载器的函数,它拷贝可执行文件p中的代码和数据到存储器,然后将控制转移到这个程序的开头。

本章主要讲的是第4步的内容。

静态链接

将一组可重定位目标文件和命令行参数作为输入,生成一个完全链接的可以加载和运行的可执行目标文件作为输出。完成这种功能的是静态连接器,为了构造可执行文件,连接器必须完成两个主要任务:

  • 符号解析(symbol resolution):目标文件定义和引用符号。符号解析的目的是将每个符号引用刚好和一个符号定义联系起来。
  • 重定位(relocation):编译器和汇编器生成从地址0开始的代码和数据节。链接器通过把每个符号定义与一个存储器位置联系起来,然后修改所有对这些符号的引用,使得它们指向这个存储器位置,从而重定为这些节。

目标文件

目标文件可以分为三种形式:

  • 可重定位目标文件。包含二进制代码和数据,其形式可以在编译时与其他可重定位目标文件合并起来,创建一个可执行目标文件。
  • 可执行目标文件 包含二进制代码和数据,其形式可以被直接拷贝到存储器链接并执行。
  • 共享目标文件:一种特殊类型的可重定位目标文件,可以在加载或者运行时被动态地加载到存储器这并连接。

可重定位目标文件

一个典型的可重定位目标文件(ELF)的格式如下:

  • ELF头:包含生成该文件的系统的字的大小和字节顺序,以及帮助连接器分析和解释的目标文件的信息。
  • .text: 已编译程序的机器代码
  • .rodata: 只读数据,比如printf语句中的格式串和开关语句的跳转表
  • .data: 已初始化的全局C变量。局部C变量在运行时保存在栈中。
  • .bass: 未初始化的全局C变量。它仅仅是一个占位符,不占用磁盘空间。
  • .symtab: 一个符号表。它存放在程序中定义和引用的函数和全局变量的信息。
  • .rel.text: 一个.text节中位置的列表,当连接器把这个目标文件和其他文件结合时,需要修改这些位置。
  • .rel.data: 被模块引用或定义的任何全局变量和重定位信息。
  • .debug: 一个调试符号表。
  • .line: 原始C源程序中的行号和.text节中机器指令之间的映射。
  • .strtab:一个字符串表,其内容包括.symtab和.debug节中的符号表,及节头部中的节名字。
    其中,每个部分都称为节**

符号和符号表(.symtab)

链接器的上下文中有三种不同的符号:

  • 由m定义并能被其他模块引用的全局符号。对应C语言中具有文件作用域并具有外部链接的变量
  • 由其他模块定义并被模块m引用的全局符号。对应C语言中的变量与上面一样,并在本文件中用external声明
  • 只被模块m定义和引用的本地符号。对应C语言中具有文件作用域但是具有内部链接的变量,如被static声明的全局变量。

符号表包含一个数组,每个元素的结构如下:

1
2
3
4
5
6
7
8
9
typedef struct {
int name; //字符串表(strtab)中的字节偏移。
int value; //符号地址,是距定义目标的节的起始位置的偏移。对可执行文件来说是一个绝对运行时地址。
int size; //目标大小
int type:4, //是变量或者函数
binding:4; //表示是本地的还是全局的
char reserved; //保留的
char section; //表示符号和目标文件的某个节相关联,也就是这个符号在那个节中
} Elf_Symbol;

看一下main.o的符号表中最后三个条目:

Num(name): Value Size Type Bind Ot Ndx(section) Name
8: 0(偏移为0) 8(8字节大小) OBJECT(变量对象) GLOBAL(全局的符号) 0 3(表示第三个节.data) buf(符号名)
9: 0(偏移为0) 17(17字节大小) FUNC(函数对象) GLOBAL(全局的符号) 0 1(表示第一个节.text) main(符号名)
10: 0 0 NOTYPE GLOBAL 0 UND(表示外部符号引用) swap(符号名)

这个地方有点晕,因为前面说第一个是自己偏移,下面这个变成了name, 最有一个是符号名Name,但是上面结构中并没有说有这个字段, 表格中和结构中的字段写法不一样,实在是太难理解~
总而言之,符号表就是对每个符号的信息描述,这个符号表什么时候用呢?符号解析的时候。

符号解析

链接器对多个可重定位目标文件进行解析的时候,读取每个文件的符号表,然后根据符号表的信息,与这个符号在代码中的确定的定义联系起来,目的是为了把所有的符号都合并在一起,形成一个完整的符号表,再加上其他信息,就变成了可执行文件。

这个过程在这里详细介绍一下,因为这里设计的链接器最核心的部分:如何变成可执行文件。

链接器如何解析多重定义的全局符号

把符号分为强和弱。对于函数和已初始化的全局变量是强符号, 对于未初始化的变量是弱符号。unix链接器使用下面的规则来处理多重定义的符号:

  • 不允许有多个强符号
  • 如果一个强符号和多个弱符号,那么选择强符号。
  • 如果有多个弱符号,那么从这些弱符号中任意选择一个。

重定位

一旦链接器完成了符号解析这一步,它就把代码中的每个符号引用和确定的一个符号定义(即它的一个输入目标模块中的一个符号表条目)联系起来。链接器根据输入目标模块中的代码节和数据节的确切大小,就可以开始重定位了:

  • 重定位节和符号定义:链接器将所有相同类型的节合并为同一类型的新的聚合节。然后链接器将运行时存储器地址赋给新的聚合节,赋给输入模块定义的每个节,以及赋给输入模块定义的每个符号。当这一步完成时,程序中的每个指令和全局变量都有唯一的运行时存储器地址了。
  • 重定位节中的符号引用。在这一步中,链接器修改代码节和数据节中对每个符号的引用,使得它们指向正确的运行时地址。为了执行这一步,链接器严重依赖称为重定位条目的可重定位目标模块中的数据结构。

重定位条目

由于汇编器生成目标模块时,并不知道数据和代码最终将存放在存储器中的什么位置,所以,无论何时汇编器遇到对最终位置未知的目标引用,它就会生成一个重定位条目,告诉链接器将目标文件合成可执行文件时如何修改这个引用。
代码的重定位条目放在.rel.text中。已初始化的数据重定位条目放在.rel.data中。

1
2
3
4
5
typedef struct{
int offset; //偏移位置
in symbol:24, //指向引用的节
type:8; //重定位类型
}Elf32_Rel;

重定位类型有11种,没种的实现方式不一样,这里只介绍两种最基本的:

  • R_386_PC32: 使用一个32位PC(程序计数器)相对地址的引用。当CPU执行一条使用PC相对寻址的指令时,它就将在指令中编码的32位值加上PC的当前运行值,得到有效地址
  • R_386_32: 重定位一个使用32位绝地地址的引用。通过绝对寻址,CPU直接使用在指令种编码 的32位值作为有效地址,不需要进一步修改。

通过反汇编可执行文件,我们可看到重定位后的.text节的内容。

可执行目标文件

已经知道链接器将多个目标模块合并成一个可执行目标文件的。我们的C程序已经从ASCII码转化成了一个二进制文件,且这个二进制文件包含加载程序到存储器并运行它所需的所有信息。下图是一个典型的ELF可执行文件中的各类信息。

由于可执行文件是完全链接的(已被重定位),所以它不再需要.rel节。我们发现还多了一个.init节,这个节定义了一个小函数,叫做_init,程序的初始化代码会调用它。

csapp chapter6:存储器层次结构

存储器系统(memory system)是一个具有不同容量、成本和访问时间的存储设备的层次结构。程序如何利用存储器的特性提高性能呢?这将是本章主要探讨的内容。

存储技术

计算机的的成功很大程度上源自于存储技术的巨大进步。下面这幅图是存储器的层次结构:

从上到下,存储的速度越慢,容量越大。
关于存储器内部是实现方式这就不介绍了,重点介绍一下计算机存储器的运行方式。
存储器层次结构的中心思想,对于每个k层,位于k层的更快更小的存储设备作为位于k+1层的跟大更慢的存储设备的缓存。也就是说层次结构中的k层的数据都是来自k+1层的。数据在每层之间的传送是以块大小为传送单元的。不同层之间的块大小可以不一样。程序运行过程中,对存储器的运用分为两种情况:

  • 缓存命中: 当程序需要数据时,最先从最高的层开始查找,如果没有找到了所需的数据,就是缓存命中。
  • 缓存不命中: 当所需的数据从当前层没有找到,就叫缓存不命中。这时候就会从下一层开始查找,直到找到所需的数据为止。当找到所需的数据后,数据会再次经过上面的层,把找到的数据保存到上面的层中,这时就要覆盖上面层的数据,如何覆盖,这涉及到替换策略,不再详述。

通过上面存储器的使用方式,可以看出,要想提高程序的性能,就必须利用时间局部性空间局部性

  • 时间局部性: 如果一个数据被加载到了最上层,那么如果连续多次调用这个数据就不需要去其他层寻找,减少了数据寻找和写缓存的过程,大大提高到了利用效率。
  • 空间局部性: 但一个数被加载的最上层时,由于数据时以块大小进行传递的,所以这个数据相邻的地址数据也会被传递,所以如果这时候访问相邻的数据话,很有可能就在这一层,而不需要去其他层寻找数据,也大大提高了利用率。

下面通过一个程序来说明一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int sum1(int a[M][N])
{
int i, j, sum = 0;

for(i = 0; i < M; i++)
for(j = 0; j < N; j++)
sum += a[i][j];
return sum;
}

int sum2(int a[M][N])
{
int i, j, sum = 0;

for(j = 0; j < M; j++)
for(i = 0; i < N; i++)
sum += a[i][j];
return sum;
}

对于sum1和sum2两个程序都时求一个二纬数组的和,唯一不同的是循环变量,也就是数组的下标顺序不一样。对于sum1,由于二纬数组是顺序存储的,而求和的时候也是按照递增的地址顺序求和的,这很好的利用了空间局部性这个原理,而sum2,同样是求和,但是二维数组的顺序并不是顺序访问的,又跳跃,所以每次访问的地址不是连续的,没有很好的利用空间局部性的原理,效率要低很多。
另一方面,两个程序的循环的过程中都使用了一个auto变量sum,每次循环都访问这个变量的值,这很好的利用了时间局部性原理。

中文搜索引擎coreseek的安装使用

项目中原来使用的是solr,由于solr是java写的,团队中没有java的经验,并且原来维护的人离职了,所以改用sphinx search来做项目的内部检索服务,由于中文的特殊性,我们选择了coreseek这个基于sphinx的中文搜索引擎。但是好像这个好久没人维护了~一直停留在了4.1beta版本~

下载解压

源码下载地址oreseek-3.1-beta.tar.gz;
解压下载的文件,进入目录cd coreseek-4.1-beta;

安装中文分词库mmseg

  • cd mmseg-3.2.14/
  • ./bootstrap
  • ./configure --prefix=/usr/local/mmseg3
  • make && make install

如果你幸运的话,这时候会提示错误:

1
2
3
4
 
css/SynonymsDict.cpp:94: 错误:在 {} 内将‘239’从‘int’转换为较窄的类型‘char’
css/SynonymsDict.cpp:94: 错误:在 {} 内将‘187’从‘int’转换为较窄的类型‘char’
css/SynonymsDict.cpp:94: 错误:在 {} 内将‘191’从‘int’转换为较窄的类型‘char’

可能是编译器的要求太严格导致的,只有更改源码了:
将rc/css/SynonymsDict.cpp文件94行的代码char txtHead[3] = {239,187,191};改为如下的形式
1
2
3
4
char txtHead[3] = {}; 
txtHead[0] = (char)239;
txtHead[1] = (char)187;
txtHead[2] = (char)191;

再次运行make && make install会发现又出现了错误提示:
1
2
3
4
5
 
mmseg_main.cpp: In function ‘int segment(const char*, css::Segmenter*)’:
mmseg_main.cpp:254: 错误:在 {} 内将‘239’从‘int’转换为较窄的类型‘char’
mmseg_main.cpp:254: 错误:在 {} 内将‘187’从‘int’转换为较窄的类型‘char’
mmseg_main.cpp:254: 错误:在 {} 内将‘191’从‘int’转换为较窄的类型‘char’

同样的办法修改src/mmseg_main.cpp文件的254行char txtHead[3] = {239,187,191};为:
1
2
3
4
char txtHead[3] = {}; 
txtHead[0] = (char)239;
txtHead[1] = (char)187;
txtHead[2] = (char)191;

再次运行make && make install,终于成功了~
到这里mmseg就算安装成功了

安装coreseek

  • cd csft-4.1/
  • sh buildconf.sh
  • ./configure --prefix=/usr/local/coreseek --without-unixodbc --with-mmseg --with-mmseg-includes=/usr/local/mmseg3/include/mmseg/ --with-mmseg-libs=/usr/local/mmseg3/lib/ --with-mysql
  • make && make install

测试mmseg分词,coreseek搜索(需要预先设置好字符集为zh_CN.UTF-8,确保正确显示中文)

1
2
3
4
5
$ cd testpack
$ cat var/test/test.xml #此时应该正确显示中文
$ /usr/local/mmseg3/bin/mmseg -d /usr/local/mmseg3/etc var/test/test.xml
$ /usr/local/coreseek/bin/indexer -c etc/csft.conf --all
$ /usr/local/coreseek/bin/search -c etc/csft.conf 网络搜索

上面是官方文档给的,需要说明的是,csft.conf是由sphinx.conf.dist复制而来的,里面的关于mysql的配置,自己按照实际情况修改。

C语言:可变参数函数

函数一般的参数都是固定的,但是有些时候我们需要让函数的参数是可变的,为了满足这个需求,C语言提供了库函数stdarg.h来满足要求。

可变参数参数简介

使用方法

可变参数函数的使用要求比较严谨,必须按照下面的方法进行使用:

  1. 在函数原型中使用省略号。
  2. 在函数定义中创建一个va_list类型的变量。
  3. 用宏将改变量初始化为一个参数列表。
  4. 用宏访问这个参数列表。
  5. 用宏完成清理工作。

函数原型

1
2
3
4
void f1(int n, ...); //合法
int f2(int n, const char *s, ...); //合法
char f3(char c1, ..., char c2); //无效,省略号必须是最后一个参量
doubel f3(); //无效,没有任何参量

程序举例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# include <stdio.h>
# include <stdarg.h>

double sum(int , ...);
void printSth(int, const char *, ...);

int main(void)
{
double s, t;

s = sum(3, 1.1, 2.5, 13.3);
t = sum(6, 1.1, 2.1, 13.1, 4.1, 5.1, 6.1);
u = sum(6, 1.1, 2.1, 13.1, 4.1, 5.1, 6.1);
printf("return value for "
"sum(3, 1.1, 2.5, 13.3): %g\n",s);
printf("return value for "
"sum(6, 1.1, 2.1, 13.1, 4.1, 5.1, 6.1) %g\n", t);

return 0;
}


double sum(int lim, ...)
{
va_list ap; //声明用户存放参数的变量
double tot = 0;
int i;
va_start(ap, lim); //把ap初始化为参数列表
for(i = 0; i < lim; i++)
tot += va_arg(ap, double); //访问参数列表中的每一个项目
va_end(ap); //清理工作
return tot;
}

程序分析

  • 具有可变参数的函数sum的第一个参数是表示一共有多少个不确定的参数,在调用的时候传递。这个参数主要是高数var_arg能够取多少次传递的参数。
  • 函数va_start()第一个参数是va_list类型的,第二个参数是这个函数确定的参数中最有一个参数,var_start()函数的作用就是把最有一个确定参数后面的所有不确定参数做一个参数列表存储到va_list类型的变量中。
  • 函数va_arg的目的是从未知参数列表中取出参数,每次调用取一个,按照参数顺序取。第一个参数是存储参数列表的变量,第二个参数标识要去的参数的类型,类型决定了要从内存栈中读取多少位。
  • 函数va_end函数主要是做清理工作,主要是释放动态分配的用于存放参数的内存。

运用

我在学了《C Primer Plus》这本书之后打算看看redis源码的时候发现redis的源码中,所有的系统log的记录都是通过这中函数来实现的:

1
2
3
4
5
6
7
8
9
10
11
12
void redisLog(int level, const char *fmt, ...) {
va_list ap;
char msg[REDIS_MAX_LOGMSG_LEN];

if ((level&0xff) < server.verbosity) return;

va_start(ap, fmt);
vsnprintf(msg, sizeof(msg), fmt, ap);
va_end(ap);

redisLogRaw(level,msg);
}

linux shell 编程之语法学习

shell语法跟一般类C的语法有些相识,但是却有很多独特的地方,如果不能够好好理解这些语法特性,难免在编写shell脚本的过程中会遇到很多令人难以察觉的,头疼的问题。细节决定成败,这篇博客就根据我自己的学习过程做一下总结吧。

独特的开头

一般的脚本语言都有一个基本表示自己是何方神圣的开头,比如php语言的<?php, jsp语言的<%jsp。shell也有自己独特的开头。比如#! /bin/bash, 不过跟其他语言表示自己的语言名称不一样,这里的开头表明shell要指明使用那个解释器。因为shell有很多标准,每个标准的解释器对shell的理解是不一样的,所有你写的shell脚本很可能是其他解释器不认识的内容,所以需要指明你自己使用哪个解释器。这里要注意的是如果写了#! /bin/sh 表明使用的是当前系统默认的解释器。

ps小贴士:

  1. #!一定要写在脚本第一行才能生效, 否则视为注释行, 不起任何作用
  2. 这一行是会被执行的,如果写其他命令如#! /bin/more 则会执行相应的命令

执行shell脚本的方法

shell执行的方式不同,其与运行的远离也不同,参考Shell如何执行命令这篇文章,进行介绍一下:
首先有一个脚本script.sh,内容如下:

1
2
3
4
# ! /bin/sh

cd ..
ls

执行这个脚本的方法有两种:

  • $ ./script.sh
  • $ sh ./script.sh

但其实第一种方法会转化为第二种方法,比如如果用第一种方法执行脚本,实际上会转化为:/bin/sh ./script.sh。接下来就调用shell子进程来执行脚本了,在脚本执行的所有都是针对子进程的,不会对父进程产生影响,这点可以参考博客中举的例子。

ps小贴士:

  1. 第一种方式执行脚本需要这个脚本具有可执行的权限, 第二种则不需要

变量的表示

Bash变量像一般的脚本语言一样,不区分变量类型,本质上Bash变量都是字符串。

变量替换

变量的名字就是变量保存值的地方,引用变量的值就叫变量替换。我们用$+变量名称来表示变量替换。下面几种情况变量不带$:

  • 变量被声明: variable
  • 变量被赋值: variable=12
  • 变量被unset: unset variable
  • 变量被export: export variable=23

弱引用(部分引用):双引号(“”)括起来的变量。这种引用变量替换不会被阻止。
强引用(全引用):单引号(’’)括起来的变量。替换被阻止,解释为字符串。

ps: $variable其实是${variable}的简写形式,但是有些时候简写形式不能够满足变量的更多特性(比如参数替换),这时候就要用全写形式了。

变量赋值:

变量赋值的方式也有多种:

  1. 使用赋值操作:=(注意等号两边不能有空白,否则就是视为条件判断了)赋值.a=12
  2. 使用let赋值.let a=2
  3. for循环中赋值(伪赋值).for a in \seq 100``

特殊的变量类型

  • 位置参数: 命令行运行脚本可以传递参数,而脚本接受参数可以通过位置参数来获取。
    • $0:代表脚本名称
    • $1:表示第一个传递的参数(依次类推, 但是$10开始需要需要用${10}来获取)
    • $#:表示参数的个数

条件判断

条件判断格式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#  1 一般的格式
if 条件
then
...
else
...
fi

# 2 两条语句写到一行是,语句间要用分号隔开
if 条件; then
...
else
...
fi

# 3 多个条件判断
if 条件
then
...
elif 条件
...
fi

# 4 嵌套条件判断
if 条件
then
if 条件
then
...
fi
fi

条件格式:

  1. [ ... ] : [是一个内建命令,其作用就是后面的表达式退出状态码为0则条件为真。
  2. [[ ... ]]: [[是一个关键字,其作用就是和上面相同,但是其表达式的解释不同。
  3. (( ... )): 测试条件是一个算术表达式,表达式的结果为非零时条件为真。
  4. 一般命令: 可跟一般的shell命令,命令的退出状态码为测试条件。

ps: [][[]]的区别:
[是一个内建命令, 其后面跟的是一般命令的参数和选项,比如[ 1 -lt 2]可以认为1和2是参数,-lt是一个选项。但是 [ 1 && 2 ]则不正确,因为 &&不是一个有效的参数或者选项。
[[是一个关键字,可以正确解释&&, 是一个更加通用的结构。

循环

循环的方式主要有以下几种:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 1 基本结构
for arg in [list]
do
commands...
done

# 2 使用$@(即位置参数)
for arg
do
commands...
done

# 3 使用命令替换[list]
for arg in `command`
do
commands...
done

# 4 使用C风格
for ((a=1; a <= LIMIT ; a++))
do
commands...
done

# 5 while
while [condition] #与条件判断的condition一样
do
commands...
done

# 6 until 类似于C的do...while
until [condition]
do
commands...
done

# 7 嵌套循环与控制
for a in [list]
do
for b in [list]
do
for c in [list]
do
break 2 #带层参数:退出从本层算,往外到第二层的循环
done
for d in [list]
do
continue #不带层参数:继续本层的循环
done
break #不带层参数:退出本层循环
done
done

分支

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# case 
case "$variable" in
$condition1 ) command...;;
$condition2 ) command...;;
...
$conditionn ) command...;;
*) command ...;; #相当于default
esac

# select 介于for和case之间的一个if语句
select variable [in list] #满足条件则执行下面的命令, 不写后面的则跟for一样,取$@
do
commands...
done

函数

函数定义的两种方式:

1
2
3
4
5
6
7
8
9
function function_name {
$1 #位置参数作为传递的参数
$2
command...
}

function_name {
command...
}

函数调用

1
function_name $arg1 $arg2

ps:

  1. 函数调用之前必须先定义

结语

到这里一个shell的基本架构有了,但是shell学习才刚刚开始,以后陆续有文章就shell的某个点进行深入探讨~