1.锁对象的定义：

关键结构体：

UNIV_INTERN lock_sys_t* lock_sys = NULL;

lock_sys是一个全局变量，用于控制整个Innodb锁系统的全部锁结构，其对应的结构体为lock_sys_t，该结构体只包含两个成员：

struct lock_sys_struct{

    hash_table_t* rec_hash;

    ulint rec_num;

};

从函数lock_rec_create可以很容易看出这两个变量的作用：

quoted code:

    HASH_INSERT(lock_t, hash, lock_sys->rec_hash,

            lock_rec_fold(space, page_no), lock);

    lock_sys->rec_num++;

每次新建一个锁对象，都要插入到lock_sys->rec_hash中，这里会根据space id 和page no来计算对应的哈希桶，然后再将锁对象插入到其中，并递增lock_sys->rec_num。

注意只有记录锁会存在lock_sys->rec_hash中，表锁是不会存这里，只会插入到事务trx->trx_locks链表和对应表对象的table->locks中,并且都是加到链表的尾部(lock_table_create)。

每个锁对象的类型为lock_t，在lock0priv.h中定义，描述如下：

trx* trx	持有该锁对象的事务
UT_LIST_NODE_T(lock_t) trx_locks	在事务锁链表trx->trx_locks中对应的节点
ulint type_mode	锁类型，在前文已有介绍
hash_node_t hash	在lock_sys->rec_hash对应哈希桶中的下一个节点
dict_index_t* index;	锁对应的索引
union {
lock_table_t tab_lock;	表锁节点
lock_rec_t rec_lock;	记录锁，lock_rec_t包含成员： space id page no n_bits //锁bitmap的比特位数，值的大小为： (1+(page_dir_get_n_heap(page) + 64)/8))*8 在锁对象结构体后面会分配对应的bitmap内存。
} un_member

2.锁系统接口函数

a.加锁函数

记录锁

lock_rec_bitmap_reset，根据记录的heap no（在一个page上是唯一的）设置锁对象的bitmap相应位为1.

表锁：

lock_table函数用于加表级别锁

b.lock_rec_lock

参数：

@1，impl ，当设置为true时，如果无需等待，则不设置锁。这里假定调用者已经设置了一个隐式锁

@2，mode,  加锁模式

@3，block，记录所在的文件块

@4，heap_no，记录在Page中的堆号，可以标示其在Page内的物理地址

@5，index,记录所在的索引

@6，thr

在函数lock_clust_rec_modify_check_and_lock和lock_sec_rec_modify_check_and_lock中调用时被设置为TRUE

在函数lock_clust_rec_read_check_and_lock和lock_sec_rec_read_check_and_lock中调用时被设置为FALSE

该函数是底层的对记录加锁函数，这里实现了快速和慢速加锁方式，加锁代码逻辑都是在kernel_mutex下进行的。

>>首先调用lock_rec_lock_fast

|–>先看该block上是否有记录锁(lock = lock_rec_get_first_on_page(block);)

没有的话，且impl为false时候,直接创建锁对象(lock_rec_create)，返回成功

|–>如果该page上有超过1个锁对象(lock_rec_get_next_on_page(lock)不为空)，则返回失败，走SLOW逻辑

|–>如果当前page上第一个锁锁对应的事务不是当前事务(lock->trx != trx)、或者lock->type_mode != (mode | LOCK_REC)、或者lock_rec_get_n_bits(lock) <= heap_no时，满足这三个条件时，返回失败，走SLOW逻辑

|–>当逻辑走到这里时，且impl=false时，设置记录锁lock_rec_set_nth_bit(lock, heap_no)，返回成功

>>如果快速加锁失败，则调用lock_rec_lock_slow

|–>首先判断lock_rec_has_expl(mode, block, heap_no, trx)

检查该事务是否已经在该记录拥有了对应的记录锁或者更强级别的锁，如果有的话，就无需继续建锁，直接从lock_rec_lock_slow返回。

判断时依次读取该记录对应heap no的锁对象，做如下判断：

lock->trx == trx       //锁对象的事务为当前事务

&& lock_mode_stronger_or_eq(lock_get_mode(lock),precise_mode & LOCK_MODE_MASK)  //比较锁强度是否大于当前申请锁

&& !lock_get_wait(lock)  //该锁对象无需等待，即type_mode不是LOCK_WAIT

&&(!lock_rec_get_rec_not_gap(lock)                      //锁模式不是record lock(LOCK_REC_NOT_GAP)

           ||(precise_mode & LOCK_REC_NOT_GAP)          // 或者当前请求锁模式是record lock

           || heap_no == PAGE_HEAP_NO_SUPREMUM)         // 或者请求锁的heap no 为PAGE_HEAP_NO_SUPREMUM

&&(!lock_rec_get_gap(lock)                              //锁模式不是LOCK_GAP

        || (precise_mode & LOCK_GAP)                    //或者当前请求锁模式为LOCK_GAP

        || heap_no == PAGE_HEAP_NO_SUPREMUM)      //或者heap no为PAGE_HEAP_NO_SUPREMUM

&& (!lock_rec_get_insert_intention(lock))   //锁模式不是插入意向锁(LOCK_INSERT_INTENTION)

其中lock_mode_stronger_or_eq的判断矩阵如下：

      IS IX S X AI
IS +   –    –  –   –
IX +  +   –  –   –
S   +   –   +  –  –
X  +   +  + +  +
AI  –   –   –  –   +

当同时满足如上条件时，认为该事务已经拥有了一个等同或更强的记录锁。

|–>当需要创建新的锁对象时，继续检查是否有相冲突的锁

lock_rec_other_has_conflicting(mode, block, heap_no, trx)

同样是遍历该heap_no上的锁，然后调用函数lock_rec_has_to_wait，根据heap_no是否为PAGE_HEAP_NO_SUPREMUM，传递的第四个参数不同(TRUE or FALSE)

lock_rec_has_to_wait函数用于检查当前请求的锁是否需要等待其他锁，参数如下：

@1，trx，新申请锁的事务

@2，type_mode， 新申请锁的锁模式

@3，lock2，对比的锁对象

@4，lock_is_on_supremum，新申请锁是否是在supremum记录上；当为true时，实际上我们申请的就是一种GAP类型的锁。

判断逻辑如下：

  |–>if 

  trx != lock2->trx

  && !lock_mode_compatible(LOCK_MODE_MASK & type_mode,lock_get_mode(lock2))

 首先判断锁是否是相容的，显然，如果锁相容，则肯定没有冲突，直接跳出if的逻辑，返回FALSE。

 锁模式相容性判断通过函数lock_mode_compatible来判断

      IS IX S X AI
IS  +  +  + –   +
IX  + +   – –   +
S    +  –   + –   –
X    –  –   –   –  –
AI  + +   –  –  –

 注意对于行记录，只加S或者X锁，对于表锁，一般加IS活IX锁。只有当执行LOCK TABLES语句时才可能对加S/X级别的表锁  

   |–> (lock_is_on_supremum || (type_mode & LOCK_GAP)) && !(type_mode & LOCK_INSERT_INTENTION)

   如果锁不是插入意向锁并且 (在supremum记录上或者请求锁类型为LOCK_GAP)

   没有LOCK_INSERT_INTENTION标记的GAP类型的锁无需等待任何事务。这是因为不同的用户可以也难怪有冲突的GAP类型锁

   返回FALSE     

   |–>!(type_mode & LOCK_INSERT_INTENTION) && lock_rec_get_gap(lock2) 

   请求的锁类型不是LOCK_INSERT_INTENTION 并且锁对象lock2类型为LOCK_GAP

   LOCK_ORDINARY 或者 LOCK_REC_NOT_GAP类型的记录锁无需等待GAP类型锁

   返回FALSE   

   |–>(type_mode & LOCK_GAP) && lock_rec_get_rec_not_gap(lock2)

   请求的锁类型为LOCK_GAP且锁对象lock2的类型为record lock(LOCK_REC_NOT_GAP)

   在GAP上的锁无需等待LOCK_REC_NOT_GAP类型的锁

   返回FALSE

   |–>lock_rec_get_insert_intention(lock2)

   锁对象Lock2上锁类型为LOCK_INSERT_INTENTION，则无需等待

   没有必要等待一个即将被移除的插入意向锁。由于我们的规则允许在GAP上的冲突锁。这消除了由于一个next-key锁等待插入意向锁

   造成的假的死锁现象；当赋予了插入意向锁后，插入会在等待next-key锁时发生死锁。（来自注释，不太了解)

   同样的插入意向锁之间不互相影响

   返回FALSE

   |–>返回TRUE

|–> 返回FALSE

|–>如果存在相互冲突的锁(lock_rec_other_has_conflicting返回TRUE)，那么就需要将请求的锁设置为需要等待

lock_rec_enqueue_waiting(mode, block, heap_no,index, trx)

如果其他事务有一个non-gap的冲突锁请求已经在队列中，并且当前事务在记录上没有更强的锁，这里就需要等待。

函数lock_rec_enqueue_waiting用于将等待锁入队列，同时这里还会负责检查死锁

   |–>创建锁对象lock_rec_create，模式为type_mode | LOCK_WAIT

   |–>检查是否有死锁发生lock_deadlock_occurs(lock, trx)，如果发生死锁的话，则重置新建的锁对象，并返回DB_DEADLOCK

       下文单独阐述如何进行死锁检测

   |–>如果死锁发生了，但另外一个事务被选作牺牲者，则表明我们已经拥有了对应的记录锁(trx->wait_lock == NULL) ，直接返回加锁成功

   |–>设置相关变量，例如事务trx->que_state为TRX_QUE_LOCK_WAIT，并返回DB_LOCK_WAIT

|–>如果事务本身既不拥有更强等级锁，也没有相冲突的事务锁，且impl为false（显式锁），则将锁加入到队列中

lock_rec_add_to_queue(LOCK_REC | mode, block,

   |–>如果记录是supremum记录，需要重置GAP位，因为所有在supremum记录上的锁会被自动当做GAP类型的锁

        type_mode = type_mode & ~(LOCK_GAP | LOCK_REC_NOT_GAP);

   |–>查看该记录或者GAP上是否有等待的锁（lock_get_wait(lock) && (lock_rec_get_nth_bit(lock, heap_no)）

        如果有的话，则创建锁对象（lock_rec_create(type_mode, block, heap_no, index, trx)，并返回； 

   |–>如果当前请求锁模式不是LOCK_WAIT：

       |–>在该Page上查看当前事务是否有类似的记录锁对象(lock_rec_find_similar_on_page，同一个page，事务相同，type_mode相同，且锁对象的bitmap大小大于当前的heap no)

            如果有的话，则重用该结构，设置对应bit位（lock_rec_set_nth_bit(lock, heap_no)）

       |–>如果找不到相似的锁对象时，再调用lock_rec_create创建锁。

  

b.死锁检测流程

lock_deadlock_occurs

该函数是死锁检测接口函数，检查一个新的锁请求是否会产生死锁。

参数：

@1，lock，请求的锁对象

@2，锁请求所对应的事务

返回TRUE表示发生死锁且当前事务被选为牺牲者，返回FALSE表示没有死锁，或者发生死锁，但当前事务未被选成

注意死锁检测也是在持有kernel_mutex的情况下进行的。

流程如下：

|–>遍历事务列表（trx_sys->trx_list），将所有事务的deadlock_mark设置为0

|–>调用死锁检测函数

ret = lock_deadlock_recursive(trx, trx, lock, &cost, 0);该函数用于递归调用检测，算法为深度优先遍历（5.6有所改进）

参数描述：

@1,start，递归检测开始的事务

@2,trx，正在等待锁的事务

@3，wait_lock，正在等待被grant的锁对象

@4，cost

@5，depth，递归检测深度

流程如下：

1.当前事务trx->deadlock_mark=1，表明已经穷尽了从当前事务开始的子树，直接return 0；

2.*cost = *cost + 1；

3.如果wait_lock锁类型为LOCK_REC，则查询哈希锁表，找到当前page上所有不等同当前wait_lock且设置了和wait_lock对应

heap no的bit位的锁对象，如果没有这样的锁对象，则设置lock = NULL.

否则如果wait_lock锁类型为LOCK_TABLE，设置lock = wait_lock;

4.查看锁队列中，在wait_lock之前的锁

5.for (;;) //for循环

1)wait_lock为表锁时，设置lock为当前表锁的前一个锁对象

2)当lock = NULL时，设置trx->deadlock_mark = 1，返回FALSE

3)检查wait_lock是否需要等待lock（lock_has_to_wait(wait_lock, lock)）

–>如果lock->trx = start，表明发现了一个死锁。打印死锁信息

通过函数trx_weight_ge(wait_lock->trx, start)选择牺牲者

>>@1，更新非事务表的事务总是权重更大

>>@2,通过trx->undo_no+trx->trx_locks的长度做简单计算来衡量事务的权重

权重小的被选作牺牲者。

>>@3,如果非当前事务(start)被选做牺牲者，则调用lock_cancel_waiting_and_release(wait_lock)将另外一个事务回滚。

–>如果depth>LOCK_MAX_DEPTH_IN_DEADLOCK_CHECK(默认200)，或者*cost>LOCK_MAX_N_STEPS_IN_DEADLOCK_CHECK(默认1000000)

则认为搜索路径太长，返回LOCK_EXCEED_MAX_DEPTH

–>如果lock->trx->que_state被标记为等待（TRX_QUE_LOCK_WAIT），则说明前面已经有一个lock->trx请求的锁的事务，递归调用：

ret = lock_deadlock_recursive(

                    start, lock_trx,

                    lock_trx->wait_lock, cost, depth + 1);

当ret为true时，返回ret,否则继续下面的逻辑

4)当heap_no ！= ULINT_UNDEFINED时，继续在当前Page上查找下一条锁记录。

#end if

综上：

两个关键参数：

一个是start，用于表示最开始的事务，也就是当前事务，这个参数是一直不变的。

另外一个是wait_lock，这个锁正在被另外一个事务等待（也就是第二个参数trx所代表的事务）

初始状态：start = trx , wait_lock为当前事务请求的锁

然后依次遍历当前page上持有wait_lock所等待的锁对象（在同一个heap no上，     且在wait_lock之前入队列的锁对象）

对于每个这样的锁对象，再深度递归遍历它也在等待的事务。

当发现存在一个这样的锁对象，其lock->trx= start时，表示发现了一个环，这说明检测到了一个死锁。

死锁检测深度太大，也会被认为出现了死锁，这主要是权衡递归检测的开销。（太大的递归深度可能导致栈溢出）

如果没有这样的锁对象，直接返回FALSE。

c.lock_rec_convert_impl_to_expl

该函数用于将隐式锁转换为显式锁

该函数在lock_clust_rec_read_check_and_lock和lock_sec_rec_read_check_and_lock中可能被调用，前者总是会调用到，

后者则在满足page上的最大事务id为活跃事务并且记录不是supremum记录时。

1.首先判断，如果是聚集索引，则调用lock_clust_rec_some_has_impl，查看记录上的事务id，判断该事务是否还是活跃的，如果活跃的，表明在该记录上的修改或者插入事务是活跃的，认为这个记录

上存在隐式锁；

如果是二级索引，则调用lock_sec_rec_some_has_impl_off_kernel来检查

1)二级索引page上的最大事务id是非活跃事务并且没有打开recovery（崩溃恢复时的事务id可能不是正确的），这时候肯定没有隐式锁，返回NULL

2)检查Page上的最大事务ID的有效性；如果事务ID不正常，表明该Page已经损坏了，这里打印page，并返回NULL（避免crash）

3)调用row_vers_impl_x_locked_off_kernel找到在该记录上持有隐式锁的事务(即最近修改或插入了该记录的事务id)，具体分析见http://mysqllover.com/?p=136

 

2.如果存在持有隐式锁的事务：

如果持有隐式锁的事务没有对该记录的显式锁（lock_rec_has_expl(LOCK_X | LOCK_REC_NOT_GAP, block,heap_no, impl_trx))，则

为其建立显式锁，并入队列:

lock_rec_add_to_queue(

                LOCK_REC | LOCK_X | LOCK_REC_NOT_GAP,

                block, heap_no, index, impl_trx);

锁类型为NOT-GAP类型的记录X锁。

所以说隐式锁并不是真正的锁，而是根据记录在记录或page上的事务id来推导出来的，当需要请求该记录上的锁时，需要先判断

是否有活跃的事务更新或插入了该记录，如果有的话，则为该事务创建一个显式锁并加入到锁哈希中。