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

// 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()
}