【转载】64位和32位的寄存器和汇编的比较

转载于http://blog.csdn.net/qq_29343201/article/details/51278798

%image_alt%

64位(新增)汇编指令的不同

%image_alt%

mov指令和push pop扩展了movq系列的mov和pushq以及popq用来操作quad word。

注意:movabsq不是32位的扩展,是纯新增的指令。用来将一个64位的字面值直接存到一个64位寄存器中。因为movq只能将32位的值存入,所以新增了这样一条指令。

%image_alt%

%image_alt%

顺带提一个小问题,64位的汇编代码在ret之前可能会加一句rep,这里的rep没有实际意义,只是出于amd处理器的原因,避免jmp所到达的地方直接就是ret,这样会使得处理器运行更快一些。

过程(函数)调用的不同

  • 参数通过寄存器传递(见前文)
  • callq 在栈里存放一个8位的返回地址
  • 许多函数不再有栈帧,只有无法将所有本地变量放在寄存器里的才会在栈上分配空间。
  • 函数可以获取到栈至多128字节的空间。这样函数就可以在不更改栈指针的情况下在栈上存储信息(也就是说,可以提前用rsp以下的128字节空间,这段空间被称为red zone,在x86-64里,时刻可用)
  • 不再有栈帧指针。现在栈的位置和栈指针相关。大多数函数在调用的一开始就分配全部所需栈空间,之后保持栈指针不改变。
  • 一些寄存器被设计成为被调用者-存储的寄存器。这些必须在需要改变他们值的时候存储他们并且之后恢复他们。

    参数传递的不同

  • 6个寄存器用来传递参数(见前文)
  • 剩下的寄存器按照之前的方式传递(不过是与rsp相关了,ebp不再作为栈帧指针,并且从rsp开始第7个参数,rsp+8开始第8个,以此类推)
  • 调用时,rsp向下移动8位(存入返回地址),寄存器参数无影响,第7个及之后的参数现在则是从rsp+8开始第7个,rsp+16开始第8个,以此类推

栈帧的不同

很多情况下不再需要栈帧,比如在没有调用别的函数,且寄存器足以存储参数,那么就只需要存储返回地址即可。
需要栈帧的情况:

  • 本地变量太多,寄存器不够
  • 一些本地变量是数组或结构体
  • 函数使用了取地址操作符来计算一个本地变量的地址
  • 函数必须用栈传送一些参数给另外一个函数
  • 函数需要保存一些由被调用者存储的寄存器的状态(以便于恢复)

但是现在的栈帧经常是固定大小的,在函数调用的最开始就被设定,在整个调用期间,栈顶指针保持不变,这样就可以通过对其再加上偏移量来对相应的值进行操作,于是EBP就不再需要作为栈帧指针了。

虽然很多时候我们认为没有“栈帧”,但是每次函数调用都一定有一个返回地址被压栈,我们可以也认为这一个地址就是一个“栈帧”,因为它也保存了调用者的状态。

 

转载于http://blog.csdn.net/qq_29343201/article/details/51278798

64位ASM教程参考:

http://cs.lmu.edu/~ray/notes/nasmtutorial/

http://asmtutor.com/#lesson1

https://cs.nyu.edu/courses/fall11/CSCI-GA.2130-001/x64-intro.pdf

发表在 未分类 | 【转载】64位和32位的寄存器和汇编的比较已关闭评论

gdb调试coredump文件函数名总是一堆问号的问题

问题描述:已经在编译选项中加入了-g,但是查看coredump文件时,函数名还是一堆问号,使用的命令为:gdb -c core

解决方案:由于gdb -c core这样的使用在有些系统下支持不是很好,所以推荐用如下两种方法:

1)gdb exe
(gdb) core-file core

2)gdb -c core
(gdb) file exe

而其中第二种方法在某些系统上也是不好用的,所以就用第一种即可。

发表在 gdb | 标签为 | gdb调试coredump文件函数名总是一堆问号的问题已关闭评论

【转】打开tcp_tw_recycle引起的一个问题

今天普空说了一个问题就是如果设置了tcp_tw_recycle ,那么如果客户端是NAT出来的,那么就可能会出现连接被直接rst的情况。然后我google了下,在内核列表也有人说了这个问题 https://lkml.org/lkml/2008/11/15/67

The big problem is that both are incompatible with NAT. So if you
ever talk to any NATed clients don’t use it.


源码之前了无秘密,我们来看代码,为什么会出现这种问题,我这里是3.4.4的内核。核心代码是在tcp_v4_conn_request中,这个函数是什么时候被调用呢,是当listen socket收到syn包的时候被调用。直接来看涉及到tw_recycle的代码:

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
#define TCP_PAWS_MSL    60      /* Per-host timestamps are invalidated
                     * after this time. It should be equal
                     * (or greater than) TCP_TIMEWAIT_LEN
                     * to provide reliability equal to one
                     * provided by timewait state.
                     */
#define TCP_PAWS_WINDOW 1       /* Replay window for per-host
                     * timestamps. It must be less than
                     * minimal timewait lifetime.
        /* VJ's idea. We save last timestamp seen
         * from the destination in peer table, when entering
         * state TIME-WAIT, and check against it before
         * accepting new connection request.
         *
         * If "isn" is not zero, this request hit alive
         * timewait bucket, so that all the necessary checks
         * are made in the function processing timewait state.
         */
        if (tmp_opt.saw_tstamp &&
            tcp_death_row.sysctl_tw_recycle &&
            (dst = inet_csk_route_req(sk, &fl4, req)) != NULL &&
            fl4.daddr == saddr &&
            (peer = rt_get_peer((struct rtable *)dst, fl4.daddr)) != NULL) {
            inet_peer_refcheck(peer);
            if ((u32)get_seconds() - peer->tcp_ts_stamp < TCP_PAWS_MSL &&
                (s32)(peer->tcp_ts - req->ts_recent) >
                            TCP_PAWS_WINDOW) {
                NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_PAWSPASSIVEREJECTED);
                goto drop_and_release;
            }
        }

可以看到当满足下面所有的条件时,这个syn包将会被丢弃,然后释放相关内存,并发送rst。
1 tcp的option有 time stamp字段.
2 tcp_tw_recycle有设置。
3 在路由表中是否存在完全相同的流(如果打开了xfrm的话,还要比较端口,默认xfrm应该是打开的),如果存在则直接返回.
4 并且数据包的源地址和新请求的源地址相同.
5 根据路由表以及源地址能够查找到保存的peer(这个可以看我以前的blog,也就是保存了一些连接统计信息).
6 当前时间(接收到syn)比最后一次的时间(time stamp)小于60秒.
7 已经存在peer的最近一次时间戳要大于当前请求进来的时间戳.

从上面可以看到,上面的条件中1/2都是 server端可以控制的,而其他的条件,都是很容易就满足的,因此我们举个例子。

如果客户端是NAT出来的,并且我们server端有打开tcp_tw_recycle ,并且time stamp也没有关闭,那么假设第一个连接进来,然后关闭,此时这个句柄处于time wait状态,然后很快(小于60秒)又一个客户端(相同的源地址,如果打开了xfrm还要相同的端口号)发一个syn包,此时linux内核就会认为这个数据包异常的,因此就会丢掉这个包,并发送rst。

而现在大部分的客户端都是NAT出来的,因此建议tw_recycle还是关闭,或者说server段关闭掉time stamp(/proc/sys/net/ipv4/tcp_timestamps).

发表在 内核 | 【转】打开tcp_tw_recycle引起的一个问题已关闭评论

【转】jQuery诞生记-原理与机制

by zhangxinxu from http://www.zhangxinxu.com
本文地址:http://www.zhangxinxu.com/wordpress/?p=3520

一、看似偶然的东西实际是必然会发生的

我大学时候在图书馆翻过一本很破旧的书,讲生物理论的,主要内容就是探讨生命的产生是偶然还是必然。里面很多亚里士多德都看不懂的公式计算什么的,还有模拟原始地球环境出现了有机物的实验什么的 。总之,书论述的观点是:“在当时的地球环境下,生命的产生是必然的!” 无数次机会的偶然条件、无数次化合物的相遇反应等必定会产生有机物,再有N多偶然,有机物必然形成了有机体……

这种理论类似于,你是个过马路非常小心的人,且你万寿无疆,除了怕被汽车撞。给你100万年的寿命,你最后必然还是被车撞死。

如果以这种理论来看jQuery的出现,结论也应该是必然的

二、需求、动力、发展、事物产生与jQuery的诞生

刀削面机器人

一个成熟的东西显然不是一口气就出来的,所谓“一铲子挖不了一口井”,我想jQuery的原作者再天才,也是循序渐进过来的,如何个循序渐进法,我想,很有可能就是需求驱动而产生的,好比上图刀削面机器人,据说现在已经第八代了!

1. gelElementById太长了
页面上有个按钮,还有个图片,我想点击按钮图片隐藏,如下HTML:

<button id="button">点击我</button>
<img id="image" src="xxx.jpg">

于是,我的脚本可能就这样:

var button = document.getElementById("button")
    , image = document.getElementById("image")

button.onclick = function() {
    image.style.display = "none";
};

有何问题?人几乎都是天生的“懒惰者”,document.getElementById名称长且重复出现,好像到了公司发现卡没带又回家重新拿卡的感觉,我希望越简单越好。恩, 我很喜欢钱,$这个符号我很喜欢,我打算改造一番,简化我的工作:

var $ = function(id) {
    return document.getElementById(id);
};

<span style="color: #cd0000;">$("button")</span>.onclick = function() {
    <span style="color: #cd0000;">$("image")</span>.style.display = "none";
};

这里的$()就是最简单的包装器,只是返回的是原生的DOM对象。

2. 我需要一个简洁的暗号,就像“芝麻开门”
后来页面复杂了,点击一个按钮,有2张图片要隐藏。

$("button").onclick = function() {
    $("image1").style.display = "none";
    $("image2").style.display = "none";
};

好像又看见长长的重复的东西,xxx.style.display = "none", 为什么每次开门都要从包里找到钥匙、对准插口插进去、还要左扭扭右扭扭呢?一次还好,天天经常老是这样怎受得了。设想,要是有个芝麻开门的暗号就好了,“open开”,声音识别,门自动开了,多省心。

这里每次隐藏都要xxx.style.display = "none", 比每天拿钥匙开门还要烦,我希望有一个快捷的方式,例如,“hide隐”,语句识别,元素自动隐藏,多省心。

就是要变成下面的效果:

$("button").onclick = function() {
    $("image1")<span style="color: #cd0000;">.hide()</span>;
    $("image2")<span style="color: #cd0000;">.hide()</span>;
};

3. 如何识别“芝麻开门”的暗号
$("image1")本质是个DOM元素,$("image1").hide()也就是在DOM元素上扩展一个hide方法,调用即隐藏。

哦,扩展,立马想到了JS中的prototype原型。//zxx: 老板,现在满大街什么菜最便宜。老板:原型啊,都泛滥了!

<span style="color: #cd0000;">HTMLElement.prototype</span>.hide = function() {
    this.style.display = "none";
};

上面代码的demo地址应该不会被人看到吧……

虽然在身体上钻了个窟窿插进入了一个方法,毕竟浏览器有有效果啊,切肤之痛就不算什么了。但是,我们是在泱泱天朝,很多IE6~IE8老顽固,这些老东西不认识HTMLElement,对于HTMLElement自残扩展之法根本理解不了,而这些老家伙掌管了半壁江山。唉,面对现实,元素直接扩展是行不通了。

因此,由于兼容性,我们需要想其他扩展方法。

4. 条条大路通罗马,此处不留爷,自有留爷处
虽IE6~IE8不识HTMLElement原型扩展,但是,Function的原型扩展其认识啊。管不管用,暂时不得而知,先随便搞个简单的试试呗~

var F = function() {};
F.prototype.hide = function() {
    this?.style.display = "none";
};

new F().hide();    <span style="color: green;">// 这个实现隐藏?</span>

本文至少还有一半的内容,但是,全文的最难点就在这里的,对new F()的认识和理解。

上面的代码,new F()您可以看做是this?.style这里的this. 您可能会跳起来抢答道:“那new F()return值 = DOM元素不就完事OK啦!—— this.style.hide = new F().style.hide = DOM.style.hide”!

很傻很天真

只要new表达式之后的constructor返回(return)一个引用对象(数组,对象,函数等),都将覆盖new创建的匿名对象,如果返回(return)一个原始类型(无return时其实为return原始类型undefined),那么就返回new创建的匿名对象。

上面的引用来自这里。什么意思呢?说白了就是,new F()如果没有返回值(Undefined类型),或返回值是5种基本型(Undefined类型、Null类型、Boolean类型、Number类型、String类型)之一,则new F()我们可以看成是原型扩展方法中的this; 如果返回是是数组啊、对象啊什么的,则返回值就是这些对象本身,此时new F() ≠ this

举例说明:

var F = function(id) {
    return document.getElementById(id);
};

new F("image1") == document.getElementById("image1");    <span style="color: green;">// true 说明看上去返回DOM对象,实际确实就是DOM对象</span>
var F = function(id) {
    return id;
};

new F("image1") == "image1";    <span style="color: green;">// false 说明看上去返回字符串值,实际并不是字符串</span>

回到上面天真的想法。要想使用prototype.hide方法中的this, 偶们就不能让F函数有乱七八糟的返回值。

因此,new F()直接返回DOM是不可取的,但我们可以借助this间接调用。比方说:

var F = function(id) {
    <span style="color: #cd0000;">this.element</span> = document.getElementById(id);
};
F.prototype.hide = function() {
    <span style="color: #cd0000;">this.element.style.display</span> = "none";
};

new F("image").hide();    <span style="color: green;">// 看你还不隐藏</span>

上面代码的demo地址应该不会被人看到吧……

5. 我不喜欢太暴露
F()中的this.element实际上将element这个属性直接暴露在了new F("image")上!

new F("image").hasOwnProperty("element");    <span style="color: green;">// true</span>

直接暴露的属性

太暴露了,我不喜欢~~
太暴露

如何隐藏?代码如下:

var F = function(id) {
    return this.getElementById(id);
};
F.prototype.getElementById = function(id) {
    <span style="color: #cd0000;">this.element</span> = document.getElementById(id);
    return <span style="color: #cd0000;">this</span>;
};
F.prototype.hide = function() {
    this.element.style.display = "none";
};

new F("image").hide();    <span style="color: green;">// 看你还不隐藏</span>

元素获取方法放在prototype上,通过F()执行。你可能会奇怪了,你刚明明说“new F()直接返回DOM是不可取的”,怎么现在又有return呢?大家务必擦亮眼睛,F.prototype.getElementById的返回值是this,也就是new F()的返回值是this. 形象点就是new F("image")出了一拳,又反弹到自己脸上了。

于是乎,现在就没有直接暴露的API了。

上面代码的demo地址应该不会被人看到吧……

6. 我不喜欢new, 我喜欢$
new F("image")这种写法我好不喜欢,我喜欢$, 我就是喜欢$, 我要换掉。

好吧,把new什么什么藏在$方法中把~

var $ = function(id) {
    return new F(id);
};

于是,上面的图片隐藏的直接执行代码就是:

$("image").hide();

上面代码的demo地址应该不会被人看到吧……

IE6浏览器也是支持的哦!是不是已经有些jQuery的样子啦!

7. 你怎么就一种姿势啊,人家都腻了诶
循序渐进到现在,都是拿id来举例的,实际应用,我们可能要使用类名啊,标签名啊什么的,现在,为了接下来的继续,有必要支持多个“姿势”。

在IE8+浏览器中,我们有选择器API,document.querySelectordocument.querySelectorAll,前者返回唯一Node,后者为NodeList集合。大统一起见,我们使用后者。于是,就有:

var F = function(selector, context) {
    return this.getNodeList(selector, context);
};
F.prototype.getNodeList = function(selector, context) {
    context = context || document;
    this.element = context.<span style="color: #cd0000;">querySelectorAll</span>(selector);
    return this;
};

var $ = function(selector, context) {
    return new F(selector, context);
};

此时,我们就可以使用各种选择器了,例如,$("body #image")this.element就是选择的元素们。

8. IE6/IE7肿么办?
IE6/IE7不认识querySelectorAll,咋办?
怎么办?

jQuery就使用了一个比较强大的选择器框架-Sizzle. 知道就好,重在演示原理,因此,下面还是使用原生的选择器API示意,故demo效果需要IE8+浏览器下查看。

8. 遍历是个麻烦事
this.element此时类型是NodeList, 因此,直接this.element.style.xxx的做法一定是报错,看来有必要循环下:

F.prototype.hide = function() {
    var i=0, length = this.element.length;
    for (; i<length; i+=1) {
        this.element[i].style.display = "none";
    }    
};

于是乎:

$("img").hide();  <span style="color: green;">// 页面所有图片都隐藏啦!</span>

上面代码的demo地址应该不会被人看到吧……

单纯一个hide方法还可以应付,再来个show方法,岂不是还要循环遍历一次,岂不是要烦死~ 

因此,急需一个遍历包装器元素的方法,姑且叫做each吧~

于是有:

F.prototype<span style="color: #cd0000;">.each</span> = function(fn) {
    var i=0, length = this.element.length;
    for (; i&lt;length; i+=1) {
        fn.call(this.element[i], i, this.element[i]);
    }
    return this;
};
F.prototype.hide = function() {
    this<span style="color: #cd0000;">.each</span>(function() {
       this.style.display = "none";
    });
};

$("img").hide();  <span style="color: green;">// 页面所有图片都隐藏啦!</span>

上面代码的demo地址应该不会被人看到吧……

9. 我不喜欢this.element, 可以去掉吗?
现在包装器对象结构类似这样:

F.prototype = {
    element: [NodeList],
    each: function() {},
    hide: function() {}
}

element看上去好碍眼,就不能去掉吗?可以啊,宝贝,NodeList是个类数组结构,我们把它以数值索引形式分配到对象中就好啦!一来去除冗余element属性,二来让原型对象成为类数组结构,可以有一些特殊的功能。

于是,F.prototype.getNodeList需要换一个名字了,比方说初始化init, 于是有:

F.prototype<span style="color: #cd0000;">.init</span> = function(selector, context) {
    var nodeList = (context || document).querySelectorAll(selector);
    <span style="color: #cd0000;">this.length</span> = nodeList.length;
    for (var i=0; i&lt;this.length; i+=1) {
        <span style="color: #cd0000;">this[i]</span> = nodeList[i];    
    }
    return this;
};

此时,each方法中,就没有烦人碍眼的this.element[i]出现了,而是直接的this[i].

F.prototype.each = function(fn) {
    var i=0, length = <span style="color: #cd0000;">this.length</span>;
    for (; i&lt;length; i+=1) {
        fn.call(<span style="color: #cd0000;">this[i]</span>, i, <span style="color: #cd0000;">this[i]</span>);
    }
    return this;
};

我们也可以直接使用索引访问包装器中的DOM元素。例如:$("img")[0]就是第一张图片啦!

上面代码的demo地址应该不会被人看到吧……

10. 我是完美主义者,我特不喜欢F名称,可以换掉吗?
F这个名称从头到尾出现,我好不喜欢的来,我要换成$, 我就是要换成$符号……

这个……$已经用了啊,再用冲突的吧。再说,你又不是狐后,耍无赖也没用啊……

狐后耍无赖

御姐发飙了

 好吧,想想其他办法吧。一步一步来,那我把所有的F换成$.fn.

就有:
所有的F换成$.fn之后~

上图代码的demo地址应该不会被人看到吧……

显然,运行是OK的。似乎也非常有jQuery的模样了,但是,实际上,跟jQuery比还是有差别的,有个较大的差别。如果是上图代码所示的JS结构,则包装器对象要扩展新方法,每个都需要再写一个原型的。例如,扩展一个attr方法,则要写成:

$.fn.prototype.attr = function() {
    <span style="color: green;">// ...</span>
};

又看到prototype了,高级的东西应该要隐藏住,否则会给人难以上手的感觉。那该怎么办呢?御姐不是好惹的。

脑子动一下就知道了,把F.prototype换成$.fn不久好了。这样,扩展新方法的时候,直接就是

$.fn.attr = function() {
    <span style="color: green;">// ...</span>
};

至此,就使用上讲,与jQuery非常接近了。 但是,还有几个F怎么办呢,总不能就像下面这样放着吧:

var $ = function(selector, context) {
    return new F(selector, context);
};
var F = function(selector, context) {
    return this.init(selector, context);
};

$.fn = F.prototype;

$.fn.init = function(selector, context) {
    <span style="color: green;">// ...</span>
    return this;
};
$.fn.each = function(fn) {
   <span style="color: green;">// ...</span>
};
$.fn.hide = function() {
   <span style="color: green;">// ...</span>
};

数学中,我们都学过合并同类项。仔细观察上面的的代码:
$()返回的是new F(),而new F()又是返回的对象的引用。擦,这返回来返回去的,参数又是一样的,我们是不是可以一次性返回,然后再做些手脚,让$.fn.init返回的this依然能够正确指向。

于是,一番调整有:

var $ = function(selector, context) {
    return new $.fn.init(selector, context);
};
var F = function() { };

$.fn = F.prototype;
$.fn.init = function(selector, context) {
    <span style="color: green;">// ...</span>
    return this;
};

<span style="color: green;">// ...</span>

上面代码显然是有问题的,new的是$.fn.init$.fn.init的返回值是this. 也就是$()的返回值是$.fn.init的原型对象,尼玛$.fn.initprototype原型现在就是个光杆司令啊,哟,正好,$.fn对应的原型方法,除了init没用外,其他hide()each()就是我们需要的。因此,我们需要加上这么一行:

$.fn.init.prototype = $.fn

于是,$()的返回值从$.fn.init.prototype一下子变成$.fn,正好就是我们一开始的扩展方法。

于是乎,大功告成。慢着……
慢着……

上面明明还有残留的F呢!

 哦,那个啊。F是任意函数,$本身就是函数,因此,直接使用$替换就可以了:

var $ = function(selector, context) {
    return new $.fn.init(selector, context);
};
<del datetime="2013-07-17T03:12:44+00:00">var F = function() { };</del>   // 这个直接删除
$.fn = <span style="color: #cd0000;">$</span>.prototype;
$.fn.init = function(selector, context) {
    <span style="color: green;">// ...</span>
    return this;
};

<span style="color: green;">// ...</span>

上图代码的demo地址应该不会被人看到吧……

实际上,如果你不是非得一个$行便天下的话,到了上面进阶第9步就足够了。jQuery在第10步的处理是为了彰显其$用得如此的出神入化,代码完美,令人惊叹!

至此,jQuery大核心已经一步一步走完了,可以看到,所有的这些进阶都是根据需求、实际开发需要来的,慢慢完善,慢慢扩充的!

11. 每个扩展方法都要$.fn.xxxx, 好闹心的来

$.fn.css = function() {}
$.fn.attr = function() {}
$.fn.data = function() {}
<span style="color: green;">// ...</span>

每个扩展前面都有个$.fn, 好讨厌的感觉,就不能合并吗?

于是,jQuery搞了个extend方法。

$.fn.extend({
    css: function() {},
    attr: function() {},
    data: function() {},
    <span style="color: green;">// ...</span>
});

12. $()不仅可以是选择器字符串,还可以是DOM
init方法中,判断第一个参数,如果是节点,直接this[0] = this_node. over!

以下13~?都是完善啊,补充啊,兼容性处理啊什么的,没有价值,到此为止!

三、排了很长队的结束语

网上也有其他一些介绍jQuery原理或机制的文章,可能当事人自己理解,而阅读者本来就不懂,说来说去,越说越绕,可能更不懂了。

jQuery是很优秀,好比身为灵长类的人类。但是,其诞生显然是从简单开始的。因此,要了解人类,可以通过追溯其起源。如果你是上帝,要让你造一个人,你会怎么造,是一口气出来?女娲造人还要捏泥人呢!不妨从单细胞生物开始,随着自然进化,淘汰,自然而然,就会出现人类,上帝他就是这么干的。

jQuery的诞生也大致如此,要想了解jQuery,可以试试踏着本文jQuery的成长足迹,一点一点逐步深入,您就会了解为何jQuery要这么设计,它是如何设计的等。

虽然,内容由浅及深,但是,其中涉及的原型以及new构造函数的一些特性,对于新人而言,还是有一些理解门槛的,希望我的描述与解释可以让你有一丝豁然开朗,那就再好不过了。

感谢您的阅读至此,欢迎指出文章可能书写不准确的地方,再次感谢!

月底在百姓网有个小分享,演示文档连个肉渣子还没准备呢。因此,未来一周休文。

原创文章,转载请注明来自张鑫旭-鑫空间-鑫生活[http://www.zhangxinxu.com]
本文地址:http://www.zhangxinxu.com/wordpress/?p=3520

(本篇完)

发表在 Javascript | 【转】jQuery诞生记-原理与机制已关闭评论

Introduction to Transaction Locks in InnoDB Storage Engine

From: https://blogs.oracle.com/mysqlinnodb/entry/introduction_to_transaction_locks_in

Introduction

Transaction locks are an important feature of any transactional storage engine. There are two types of transaction locks – table locks and row locks. Table locks are used to avoid a table being altered or dropped by one transaction when another transaction is using the table. It is also used to prohibit a transaction from accessing a table, when it is being altered. InnoDB supports multiple granularity locking (MGL). So to access rows in a table, intention locks must be taken on the tables.

Row locks are at finer granularity than table level locks, different threads can work on different parts of the table without interfering with each other. This is in contrast with MyISAM where the entire table has to be locked when updating even unrelated rows. Having row locks means that multiple transactions can read and write into a single table. This increases the concurrency level of the storage engine. InnoDB being an advanced transactional storage engine, provides both table and row level transaction locks.

This article will provide information about how transaction locks are implemented in InnoDB storage engine. The lock subsystem of InnoDB provides many services to the overall system, like:

  • Creating, acquiring, releasing and destroying row locks.
  • Creating, acquiring, releasing and destroying table locks.
  • Providing multi-thread safe access to row and table locks.
  • Data structures useful for locating a table lock or a row lock.
  • Maintaining a list of user threads suspended while waiting for transaction locks.
  • Notification of suspended threads when a lock is released.
  • Deadlock detection

The lock subsystem helps to isolate one transaction from another transaction. This article will provide information about how transaction locks are created, maintained and used in the InnoDB storage engine. All reference to locks means transaction locks, unless specified otherwise.

Internal Data Structures of InnoDB

Before we proceed with scenarios and algorithms, I would like to present the following data structures. We need to be familiar with these data structures to understand how transaction locks work in InnoDB. The data structures of interest are:

  1. The enum lock_mode – provides the list of modes in which the transaction locks can be obtained.
  2. The lock struct lock_t. This represents either a table lock or a row lock.
  3. The struct trx_t which represents one transaction within InnoDB.
  4. The struct trx_lock_t which associates one transaction with all its transaction locks.
  5. The global object of type lock_sys_t holds the hash table of row locks.
  6. The table descriptor dict_table_t, which uniquely identifies a table in InnoDB. Each table descriptor contains a list of locks on the table.
  7. The global object trx_sys of type trx_sys_t, which holds the active transaction table (ATT).

The Lock Modes

The locks can be obtained in the following modes. I’ll not discuss about the LOCK_AUTO_INC in this article.

/* Basic lock modes */

enum lock_mode {

        LOCK_IS = 0,    /* intention shared */

        LOCK_IX,        /* intention exclusive */

        LOCK_S,         /* shared */

        LOCK_X,         /* exclusive */

        LOCK_AUTO_INC,  /* locks the auto-inc counter of a table

                        in an exclusive mode */

        LOCK_NONE,      /* this is used elsewhere to note consistent read */

        LOCK_NUM = LOCK_NONE, /* number of lock modes */

        LOCK_NONE_UNSET = 255

};

The lock struct or lock object

The structure lock_t represents either a table lock (lock_table_t) or a group of row locks (lock_rec_t) for all the rows belonging to the same page. For different lock modes, different lock structs will be used. For example, if a row in a page is locked in LOCK_X mode, and if another row in the same page is locked in LOCK_S mode, then these two row locks will be held in different lock structs.

This structure is defined as follows:

struct lock_t {

        trx_t*          trx;

        ulint           type_mode;

        hash_node_t     hash;

        dict_index_t*   index;

        union {

                lock_table_t    tab_lock;/*!< table lock */

                lock_rec_t      rec_lock;/*!< record lock */

        } un_member;                    /*!< lock        details */

};

/** A table lock */

struct lock_table_t {

        dict_table_t*   table;          /*!< database table in dictionary

                                        cache */

        UT_LIST_NODE_T(lock_t)

                        locks;          /*!< list of locks on the same

                                        table */

};

/** Record lock for a page */

struct lock_rec_t {

        ulint   space;                  /*!< space id */

        ulint   page_no;                /*!< page number */

        ulint   n_bits;                 /*!< number of bits in the lock

                                        bitmap; NOTE: the lock bitmap is

                                        placed immediately after the

                                        lock struct */

};

The important point here is the lock bitmap. The lock bitmap is a space efficient way to represent the row locks. This space efficient way of representing the row locks avoids the need for lock escalation and lock data persistence. (Note: For prepared transactions, it would be useful to have lock data persistence, but InnoDB currently do not support lock data persistence.)

The lock bitmap is placed immediately after the lock struct object. If a page can contain a maximum of 100 records, then the lock bitmap would be of size 100 (or more). Each bit in this bitmap will represent a row in the page. The heap_no of the row is used to index into the bitmap. If the 5th bit in the bitmap is enabled, then the row with heap_no 5 is locked.

The Transaction And Lock Relationship

The struct trx_t is used to represent the transaction within InnoDB. The struct trx_lock_t is used to represent all locks associated to a given transaction. Here I have listed down only those members relevant to this article.

struct trx_t {

      trx_id_t        id;             /*!< transaction id */

      trx_lock_t      lock;           /*!< Information about the transaction

                                        locks and state. Protected by

                                        trx->mutex or lock_sys->mutex

                                        or both */

};

struct trx_lock_t {

        ib_vector_t*    table_locks;    /*!< All table locks requested by this

                                        transaction, including AUTOINC locks */

        UT_LIST_BASE_NODE_T(lock_t)

                        trx_locks;      /*!< locks requested

                                        by the transaction;

                                        insertions are protected by trx->mutex

                                        and lock_sys->mutex; removals are

                                        protected by lock_sys->mutex */

};

Global hash table of row locks

Before we look at how the row locks internally works, we need to be aware of this global data structure. The lock subsystem of the InnoDB storage engine has a global object lock_sys of type lock_sys_t. The class lock_sys_t is defined as follows:

struct lock_sys_t {

        ib_mutex_t      mutex;

        hash_table_t*   rec_hash;

        ulint           n_lock_max_wait_time;

        // more …

};

The lock_sys_t::rec_hash member is the hash table of the record locks. Every page within InnoDB is uniquely identified by the (space_id, page_no) combination, called the page address. The hashing is done based on the page address. So given the page address, we can locate the list of lock_t objects of that page. All lock structs of the given page will be in the same hash bucket. So using this mechanism we can locate the row lock of any row.

The Transaction Subsystem Global Object

The transaction subsystem of InnoDB has one global object trx_sys of type trx_sys_t, which is an important internal data structure. It is defined as follows:

/** The transaction system central memory data structure. */

struct trx_sys_t{

        // more …

        trx_list_t      rw_trx_list;    /*!< List of active and committed in

                                        memory read-write transactions, sorted

                                        on trx id, biggest first. Recovered

                                        transactions are always on this list. */

        trx_list_t      ro_trx_list;    /*!< List of active and committed in

                                        memory read-only transactions, sorted

                                        on trx id, biggest first. NOTE:

                                        The order for read-only transactions

                                        is not necessary. We should exploit

                                        this and increase concurrency during

                                        add/remove. */

        // more …

};

This global data structure contains the active transaction table (ATT) of InnoDB storage engine. In the following sections, I’ll use this global object to access my transaction object through the debugger to demonstrate the transaction locks.

The table descriptor (dict_table_t)

Each table in InnoDB is uniquely identified by its name in the form of databasename/tablename. For each table, the data dictionary of InnoDB will contain exactly one table descriptor object of type dict_table_t. Given the table name, the table descriptor can be obtained. This table descriptor contains a list of locks on the table. This list can be used to check if the table has already been locked by a transaction.

struct dict_table_t{

        // more …

        table_id_t      id;     /*!< id of the table */

        char*           name;   /*!< table name */

        UT_LIST_BASE_NODE_T(lock_t)

                        locks;  /*!< list of locks on the table; protected

                                by lock_sys->mutex */

};

The heap_no of a row

Every row in InnoDB is uniquely identified by space_id, page_no and heap_no of the row. I assume that you know about space_id and page_no. I’ll explain here only about the heap_no of the row. Each row in the page has a heap_no. The heap_no of the infimum record is 0, the heap_no of the supremum record is 1, and the heap_no of the first user record in page is 2.

If we have inserted 10 records in the page, and if there has been no updates on the page, then the heap_no of the user records would be 2, 3, 4, 5 … 10, 11. The heap_no will be in the same order in which the records will be accessed in ascending order.

The heap_no of the row is used to locate the bit in the lock bitmap corresponding to the row. If the row has a heap_no of 10, then the 10th bit in the lock bitmap corresponds to the row. This means that if the heap_no of the row is changed, then the associated lock structs must be adjusted accordingly.

The Schema

To demonstrate the transaction locks, I use the following schema in this article. There is one table t1 which has 3 rows (1, ‘அ’), (2, ‘ஆ’) and (3, ‘இ’). In this article, we will see when and how the transaction locks (table and row) are created and used. We will also cover the internal steps involved in creating table and row locks.

set names utf8;

drop table if exists t1;

create table t1 (f1 int primary key, f2 char(10)) charset=’utf8′;

insert into t1 values (1, ‘அ’), (2, ‘ஆ’), (3, ‘இ’);

Table Level Transaction Locks

The purpose of table level transaction locks or simply table locks is to ensure that no transactions modify the structure of the table when another transaction is accessing or modifying the table or the rows in a table. There are two types of table locks in MySQL – one is the meta-data locking (MDL) provided by the SQL engine and the other is the table level locks within InnoDB storage engine. Here the discussion is only about the table level locks within InnoDB.

On tables, InnoDB normally acquires only intentional shared (LOCK_IS) or intentional exclusive (LOCK_IX) modes. It does not lock the tables in shared mode (LOCK_S) or exclusive mode (LOCK_X) unless explicitly requested via LOCK TABLES command. One exception to this is in the prepare phase of the online alter table command, where the table is locked in shared mode. Please refer to Multiple Granularity Locking to know about intention shared and intention exclusive locks.

Scenario () for LOCK_IS table lock

Here is an example scenario that will take intention shared (LOCK_IS) lock on the table.

mysql> set transaction isolation level serializable;

mysql> start transaction;

mysql> select * from t1;

When the above 3 statements are executed, one table lock would be taken in LOCK_IS mode. In mysql-5.6, there is no way to verify this other than using the debugger. I verified it as follows:

(gdb) set $trx_locklist = trx_sys->rw_trx_list->start->lock->trx_locks

(gdb) p $trx_locklist.start->un_member->tab_lock->table->name

$21 = 0x7fffb0014f70 “test/t1”

(gdb) p lock_get_mode(trx_sys->rw_trx_list->start->lock->trx_locks->start)

$25 = LOCK_IS

(gdb)

You need to access the correct transaction object and the lock object.

Scenario () for LOCK_IX table lock

Here is an extension to the previous scenario. Adding an INSERT statement to the scenario will take an intention exclusive (LOCK_IX) lock on the table.

mysql> set transaction isolation level serializable;

mysql> start transaction;

mysql> select * from t1;

mysql> insert into t1 values (4, ‘ஃ’);

When the above 4 statements are executed, there would be two locks on the table – LOCK_IS and LOCK_IX. The select statement would have taken the table lock in LOCK_IS mode and the INSERT statement would take the table lock in LOCK_IX mode.

This can also be verified using the debugger. I’ll leave it as an exercise for the reader.

What Happens Internally When Acquiring Table Locks

Each table is uniquely identified within the InnoDB storage engine using the table descriptor object of type dict_table_t. In this section we will see the steps taken internally by InnoDB to obtain a table lock. The function to refer to is lock_table() in the source code. Necessary mutexes are taken during these steps to ensure that everything works correctly in a multi-thread environment. This aspect is not discussed here.

  1. The request for a table lock comes with the following information – the table to lock (dict_table_t), the mode in which to lock (enum lock_mode), and the transaction which wants the lock (trx_t).
  2. Check whether the transaction is already holding an equal or stronger lock on the given table. Each transaction maintains a list of table locks obtained by itself (trx_t::trx_lock_t::table_locks). Searching this list for the given table and mode is sufficient to answer this question. If the current transaction is already holding an equal or stronger lock on the table, then the lock request is reported as success. If not, then go to next step.
  3. Check if any other transaction has an incompatible lock request in the lock queue of the table. Each table descriptor has a lock queue (dict_table_t::locks). Searching this queue is sufficient to answer this question. If some other transaction holds an incompatible lock on the table, then the lock request needs to wait. Waiting for a lock can lead to time out or deadlock error. If there is no contention from other transactions for this table, then proceed further.
  4. Allocate a lock struct object (lock_t). Initialize with table, trx and lock mode information. Add this object to the queue in dict_table_t::locks object of the table as well as the trx_t::trx_lock_t::table_locks.
  5. Complete.

You can re-visit the above scenario (௨) and then follow the above steps and verify that the number of lock structs created is 2.

Row Level Transaction Locks

Each row in the InnoDB storage engine needs to be uniquely identified in order to be able to lock it. A row is uniquely identified by the following pieces of information:

  • The space identifier
  • The page number within the space.
  • The heap number of the record within the page.
  • The descriptor of the index to which the row belongs (dict_index_t). Stricly speaking, this is not necessary to uniquely identify the row. But associating the row to its index will help to provide user friendly diagnosis and also help the developers to debug a problem.

There are two types of row locks in InnoDB – the implicit and the explicit. The explicit row locks are the locks that make use of the global row lock hash table and the lock_t structures. The implicit row locks are logically arrived at based on the transaction information in the clustered index or secondary index record. These are explained in the following sections.

Implicit Row Locks

Implicit row locks do not have an associated lock_t object allocated. This is purely calculated based on the ID of the requesting transaction and the transaction ID available in each record. First, let use see how implicit locks are “acquired” (here is comment from lock0lock.cc):

“If a transaction has modified or inserted an index record, then it owns an implicit x-lock on the record. On a secondary index record, a transaction has an implicit x-lock also if it has modified the clustered index record, the max trx id of the page where the secondary index record resides is >= trx id of the transaction (or database recovery is running), and there are no explicit non-gap lock requests on the secondary index record. ”

As we can see, the implicit locks are a logical entity and whether a transaction has implicit locks or not is calculated using certain procedures. This procedure is explained here briefly.

If a transaction wants to acquire a row lock (implicit or explicit), then it needs to determine whether any other transaction has an implicit lock on the row before checking on the explicit lock. As explained above this procedure is different for clustered index and secondary index.

For the clustered index, get the transaction id from the given record. If it is a valid transaction id, then that is the transaction which is holding the implicit exclusive lock on the row. Refer to the function lock_clust_rec_some_has_impl() for details.

For the secondary index, it is more cumbersome to calculate. Here are the steps:

  1. Let R1 be the secondary index row for which we want to check if another transaction is holding an implicit exclusive lock.
  2. Obtain the maximum transaction id (T1) of the page that contains the secondary index row R1.
  3. Let T2 be the minimum transaction id of the InnoDB system. If T1 is less than T2, then there can be no transaction holding implicit lock on the row. Otherwise, go to next step.
  4. Obtain the corresponding clustered index record for the given secondary index record R1.
  5. Get the transaction id (T3) from the clustered index record. By looking at the clustered index record, including its older versions, find out if T3 could have modified or inserted the secondary index row R1. If yes, then T3 has an implicit exclusive lock on row R1. Otherwise it does not have.

In the case of secondary indexes, we need to make use of the undo logs to determine if any transactions have an implicit exclusive row lock on record. Refer to the function lock_sec_rec_some_has_impl() for details.

Also note that the implicit row locks do not affect the gaps.

Explicit Row Locks

Explicit row locks are represented by the lock_t structures. This section provides some scenarios in which explicit row locks are obtained in different modes. It also briefly discusses the internal procedure to acquire an explicit row lock.

Scenario () for LOCK_S row lock

For transaction isolation level REPEATABLE READ and less stronger levels, InnoDB does not take shared locks on rows. So in the following scenario, we use SERIALIZABLE transaction isolation level for demonstrating shared row locks:

mysql> set transaction isolation level serializable;

mysql> start transaction;

mysql> select * from t1;

This scenario is the same as the Scenario (௧). The verification via debugger alone is different. In the case of row locks, each lock object represents a row lock for all rows of a page (of the same lock mode). So a lock bitmap is used for this purpose which exists at the end of the lock struct object. In the above scenario, we can verify the locks as follows:

The lock_t object allocated for the row locks is

(gdb) set $trx_locklist = trx_sys->rw_trx_list->start->lock->trx_locks

(gdb) set $rowlock = $trx_locklist.start->trx_locks->next

(gdb) p $rowlock

$47 = (ib_lock_t *) 0x7fffb00103f0

Verify the lock mode of the lock object.

(gdb) p lock_get_mode($rowlock)

$48 = LOCK_S

(gdb)

Verify that it is actually a lock struct object allocated for rows (and not a table lock).

(gdb) p *$rowlock

$43 = {trx = 0x7fffb0013f78, trx_locks = {prev = 0x7fffb00103a8, next = 0x0},

  type_mode = 34, hash = 0x0, index = 0x7fffb001a6b8, un_member = {tab_lock = {

      table = 0xc, locks = {prev = 0x3, next = 0x48}}, rec_lock = {space = 12,

      page_no = 3, n_bits = 72}}}

(gdb)

The row lock bit map is at the end of the lock object. Even though the number of bits in the lock bitmap is given as n_bits = 72 (9 bytes) above, I am examining only 4 bytes here.

(gdb) x /4t $rowlock + 1

0x7fffb0010438:     00011110  00000000  00000000  00000000

(gdb)

Note that there are 4 bits enabled. This means that there are 4 row locks obtained. The row in the page, and the bit in the lock bit map are related via the heap_no of the row, as described previously.

Scenario () for LOCK_X row lock

Changing the above scenario slightly as follows, will obtain LOCK_X locks on the rows.

mysql> set transaction isolation level serializable;

mysql> start transaction;

mysql> select * from t1 for update;

Verification of this through the debugger is left as an exercise for the reader.

What Happens Internally When Acquiring Explicit Row Locks

To lock a row, all information necessary to uniquely identify the row – the trx, lock mode, table space id, page_no and heap_no – must be supplied. The entry point for row locking is the lock_rec_lock() function in the source code.

  1. Check if the given transaction has a granted explicit lock on the row with equal or stronger lock mode. To do this search, the global hash table of row locks is used. If the transaction already has a strong enough lock on the row, then nothing more to do. Otherwise go to next step.
  2. Check if other transactions have a conflicting lock on the row. For this search also, the global hash table of row locks is used. If yes, then the current transaction must wait. Waiting can lead to timeout or deadlock error. If there is no contention for this row from other transactions then proceed further.
  3. Check if there is already a lock struct object for the given row. If yes, reuse the same lock struct object. Otherwise allocate a lock struct object.
  4. Initialize the trx, lock mode, page_no, space_id and the size of the lock bit map. Set the bit of the lock bitmap based on the heap_no of the row.
  5. Insert this lock struct object in the global hash table of row locks.
  6. Add this to the list of transaction locks in the transaction object (trx_t::trx_lock_t::trx_locks).

Releasing transaction locks

All the transaction locks acquired by a transaction is released by InnoDB at transaction end (commit or rollback). In the case of REPEATABLE READ isolation level or SERIALIZABLE, it is not possible for the SQL layer to release locks before transaction end. In the case of READ COMMITTED isolation level, it is possible for the SQL layer to release locks before transaction end by making use of ha_innobase::unlock_row() handler interface API call.

To obtain the list of all transaction locks of a transaction, the following member can be used – trx_t::trx_lock_t::trx_locks.

Conclusion

This article provided an overview of the transaction locks in InnoDB. We looked at the data structures used to represent transaction locks. We analysed some scenarios in which the various locks are created. We also looked at the internal steps that happen when a table lock or a row lock is created.

You can download this article in pdf.

 

发表在 MySQL | Introduction to Transaction Locks in InnoDB Storage Engine已关闭评论