blob: 803d75866a135663e3957c0d385092e1adbf11b6 [file] [log] [blame]
package gkvlite
import (
"fmt"
"sync"
"sync/atomic"
"unsafe"
)
var freeNodeLock sync.Mutex
var freeNodes *node
var freeNodeLocLock sync.Mutex
var freeNodeLocs *nodeLoc
var freeRootNodeLocLock sync.Mutex
var freeRootNodeLocs *rootNodeLoc
var allocStats AllocStats
type AllocStats struct {
MkNodes int64
FreeNodes int64 // Number of invocations of the freeNode() API.
AllocNodes int64
CurFreeNodes int64 // Current length of freeNodes list.
MkNodeLocs int64
FreeNodeLocs int64 // Number of invocations of the freeNodeLoc() API.
AllocNodeLocs int64
CurFreeNodeLocs int64 // Current length of freeNodeLocs list.
MkRootNodeLocs int64
FreeRootNodeLocs int64 // Number of invocations of the freeRootNodeLoc() API.
AllocRootNodeLocs int64
CurFreeRootNodeLocs int64 // Current length of freeRootNodeLocs list.
}
func withAllocLocks(cb func()) {
freeNodeLock.Lock()
freeNodeLocLock.Lock()
freeRootNodeLocLock.Lock()
defer freeNodeLock.Unlock()
defer freeNodeLocLock.Unlock()
defer freeRootNodeLocLock.Unlock()
cb()
}
func (t *Collection) markReclaimable(n *node, reclaimMark *node) {
t.rootLock.Lock()
defer t.rootLock.Unlock()
if n == nil || n.next != nil || n == reclaimMark {
return
}
n.next = reclaimMark
}
func (t *Collection) reclaimMarkUpdate(nloc *nodeLoc,
oldReclaimMark, newReclaimMark *node) *node {
if nloc.isEmpty() {
return nil
}
n := nloc.Node()
t.rootLock.Lock()
if n != nil && n.next == oldReclaimMark {
n.next = newReclaimMark
t.rootLock.Unlock()
t.reclaimMarkUpdate(&n.left, oldReclaimMark, newReclaimMark)
t.reclaimMarkUpdate(&n.right, oldReclaimMark, newReclaimMark)
} else {
t.rootLock.Unlock()
}
return n
}
func (t *Collection) reclaimNodes_unlocked(n *node,
reclaimLater *[3]*node, reclaimMark *node) int64 {
if n == nil {
return 0
}
if reclaimLater != nil {
for i := 0; i < len(reclaimLater); i++ {
if reclaimLater[i] == n {
reclaimLater[i] = nil
}
}
}
if n.next != reclaimMark {
return 0
}
var left *node
var right *node
if !n.left.isEmpty() {
left = n.left.Node()
}
if !n.right.isEmpty() {
right = n.right.Node()
}
t.freeNode_unlocked(n, reclaimMark)
numLeft := t.reclaimNodes_unlocked(left, reclaimLater, reclaimMark)
numRight := t.reclaimNodes_unlocked(right, reclaimLater, reclaimMark)
return 1 + numLeft + numRight
}
// Assumes that the caller serializes invocations.
func (t *Collection) mkNode(itemIn *itemLoc, leftIn *nodeLoc, rightIn *nodeLoc,
numNodesIn uint64, numBytesIn uint64) *node {
freeNodeLock.Lock()
allocStats.MkNodes++
t.allocStats.MkNodes++
n := freeNodes
if n == nil {
allocStats.AllocNodes++
t.allocStats.AllocNodes++
freeNodeLock.Unlock()
atomic.AddUint64(&t.store.nodeAllocs, 1)
n = &node{}
} else {
freeNodes = n.next
allocStats.CurFreeNodes--
freeNodeLock.Unlock()
}
if itemIn != nil {
i := itemIn.Item()
if i != nil {
t.store.ItemAddRef(t, i)
}
}
n.item.Copy(itemIn)
n.left.Copy(leftIn)
n.right.Copy(rightIn)
n.numNodes = numNodesIn
n.numBytes = numBytesIn
n.next = nil
return n
}
func (t *Collection) freeNode_unlocked(n *node, reclaimMark *node) {
if n == nil || n == reclaimMark {
return
}
if n.next != nil && n.next != reclaimMark {
panic("double free node")
}
i := n.item.Item()
if i != nil {
t.store.ItemDecRef(t, i)
}
n.item = *empty_itemLoc
n.left = *empty_nodeLoc
n.right = *empty_nodeLoc
n.numNodes = 0
n.numBytes = 0
n.next = freeNodes
freeNodes = n
allocStats.CurFreeNodes++
allocStats.FreeNodes++
t.allocStats.FreeNodes++
}
// Assumes that the caller serializes invocations.
func (t *Collection) mkNodeLoc(n *node) *nodeLoc {
freeNodeLocLock.Lock()
allocStats.MkNodeLocs++
t.allocStats.MkNodeLocs++
nloc := freeNodeLocs
if nloc == nil {
allocStats.AllocNodeLocs++
t.allocStats.AllocNodeLocs++
freeNodeLocLock.Unlock()
nloc = &nodeLoc{}
} else {
freeNodeLocs = nloc.next
allocStats.CurFreeNodeLocs--
freeNodeLocLock.Unlock()
}
nloc.loc = unsafe.Pointer(nil)
nloc.node = unsafe.Pointer(n)
nloc.next = nil
return nloc
}
// Assumes that the caller serializes invocations.
func (t *Collection) freeNodeLoc(nloc *nodeLoc) {
if nloc == nil || nloc == empty_nodeLoc {
return
}
if nloc.next != nil {
panic("double free nodeLoc")
}
nloc.loc = unsafe.Pointer(nil)
nloc.node = unsafe.Pointer(nil)
freeNodeLocLock.Lock()
nloc.next = freeNodeLocs
freeNodeLocs = nloc
allocStats.CurFreeNodeLocs++
allocStats.FreeNodeLocs++
t.allocStats.FreeNodeLocs++
freeNodeLocLock.Unlock()
}
func (t *Collection) mkRootNodeLoc(root *nodeLoc) *rootNodeLoc {
freeRootNodeLocLock.Lock()
allocStats.MkRootNodeLocs++
t.allocStats.MkRootNodeLocs++
rnl := freeRootNodeLocs
if rnl == nil {
allocStats.AllocRootNodeLocs++
t.allocStats.AllocRootNodeLocs++
freeRootNodeLocLock.Unlock()
rnl = &rootNodeLoc{}
} else {
freeRootNodeLocs = rnl.next
allocStats.CurFreeRootNodeLocs--
freeRootNodeLocLock.Unlock()
}
rnl.refs = 1
rnl.root = root
rnl.next = nil
rnl.chainedCollection = nil
rnl.chainedRootNodeLoc = nil
for i := 0; i < len(rnl.reclaimLater); i++ {
rnl.reclaimLater[i] = nil
}
return rnl
}
func (t *Collection) freeRootNodeLoc(rnl *rootNodeLoc) {
if rnl == nil {
return
}
if rnl.next != nil {
panic("double free rootNodeLoc")
}
rnl.refs = 0
rnl.root = nil
rnl.chainedCollection = nil
rnl.chainedRootNodeLoc = nil
for i := 0; i < len(rnl.reclaimLater); i++ {
if rnl.reclaimLater[i] != nil {
panic(fmt.Sprintf("non-nil rnl.reclaimLater[%d]: %v",
i, rnl.reclaimLater[i]))
}
}
freeRootNodeLocLock.Lock()
rnl.next = freeRootNodeLocs
freeRootNodeLocs = rnl
allocStats.CurFreeRootNodeLocs++
allocStats.FreeRootNodeLocs++
t.allocStats.FreeRootNodeLocs++
freeRootNodeLocLock.Unlock()
}