You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
130 lines
2.9 KiB
130 lines
2.9 KiB
// Copyright 2019 PingCAP, Inc.
|
|
//
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
// you may not use this file except in compliance with the License.
|
|
// You may obtain a copy of the License at
|
|
//
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
//
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
|
// See the License for the specific language governing permissions and
|
|
// limitations under the License.
|
|
|
|
package deadlock
|
|
|
|
import (
|
|
"fmt"
|
|
"sync"
|
|
)
|
|
|
|
// Detector detects deadlock.
|
|
type Detector struct {
|
|
waitForMap map[uint64]*txnList
|
|
lock sync.Mutex
|
|
}
|
|
|
|
type txnList struct {
|
|
txns []txnKeyHashPair
|
|
}
|
|
|
|
type txnKeyHashPair struct {
|
|
txn uint64
|
|
keyHash uint64
|
|
}
|
|
|
|
// NewDetector creates a new Detector.
|
|
func NewDetector() *Detector {
|
|
return &Detector{
|
|
waitForMap: map[uint64]*txnList{},
|
|
}
|
|
}
|
|
|
|
// ErrDeadlock is returned when deadlock is detected.
|
|
type ErrDeadlock struct {
|
|
KeyHash uint64
|
|
}
|
|
|
|
func (e *ErrDeadlock) Error() string {
|
|
return fmt.Sprintf("deadlock(%d)", e.KeyHash)
|
|
}
|
|
|
|
// Detect detects deadlock for the sourceTxn on a locked key.
|
|
func (d *Detector) Detect(sourceTxn, waitForTxn, keyHash uint64) *ErrDeadlock {
|
|
d.lock.Lock()
|
|
err := d.doDetect(sourceTxn, waitForTxn)
|
|
if err == nil {
|
|
d.register(sourceTxn, waitForTxn, keyHash)
|
|
}
|
|
d.lock.Unlock()
|
|
return err
|
|
}
|
|
|
|
func (d *Detector) doDetect(sourceTxn, waitForTxn uint64) *ErrDeadlock {
|
|
list := d.waitForMap[waitForTxn]
|
|
if list == nil {
|
|
return nil
|
|
}
|
|
for _, nextTarget := range list.txns {
|
|
if nextTarget.txn == sourceTxn {
|
|
return &ErrDeadlock{KeyHash: nextTarget.keyHash}
|
|
}
|
|
if err := d.doDetect(sourceTxn, nextTarget.txn); err != nil {
|
|
return err
|
|
}
|
|
}
|
|
return nil
|
|
}
|
|
|
|
func (d *Detector) register(sourceTxn, waitForTxn, keyHash uint64) {
|
|
list := d.waitForMap[sourceTxn]
|
|
pair := txnKeyHashPair{txn: waitForTxn, keyHash: keyHash}
|
|
if list == nil {
|
|
d.waitForMap[sourceTxn] = &txnList{txns: []txnKeyHashPair{pair}}
|
|
return
|
|
}
|
|
for _, tar := range list.txns {
|
|
if tar.txn == waitForTxn && tar.keyHash == keyHash {
|
|
return
|
|
}
|
|
}
|
|
list.txns = append(list.txns, pair)
|
|
}
|
|
|
|
// CleanUp removes the wait for entry for the transaction.
|
|
func (d *Detector) CleanUp(txn uint64) {
|
|
d.lock.Lock()
|
|
delete(d.waitForMap, txn)
|
|
d.lock.Unlock()
|
|
}
|
|
|
|
// CleanUpWaitFor removes a key in the wait for entry for the transaction.
|
|
func (d *Detector) CleanUpWaitFor(txn, waitForTxn, keyHash uint64) {
|
|
pair := txnKeyHashPair{txn: waitForTxn, keyHash: keyHash}
|
|
d.lock.Lock()
|
|
l := d.waitForMap[txn]
|
|
if l != nil {
|
|
for i, tar := range l.txns {
|
|
if tar == pair {
|
|
l.txns = append(l.txns[:i], l.txns[i+1:]...)
|
|
break
|
|
}
|
|
}
|
|
if len(l.txns) == 0 {
|
|
delete(d.waitForMap, txn)
|
|
}
|
|
}
|
|
d.lock.Unlock()
|
|
|
|
}
|
|
|
|
// Expire removes entries with TS smaller than minTS.
|
|
func (d *Detector) Expire(minTS uint64) {
|
|
d.lock.Lock()
|
|
for ts := range d.waitForMap {
|
|
if ts < minTS {
|
|
delete(d.waitForMap, ts)
|
|
}
|
|
}
|
|
d.lock.Unlock()
|
|
}
|
|
|