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.
175 lines
3.8 KiB
175 lines
3.8 KiB
// Copyright 2020 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 memdb
|
|
|
|
import (
|
|
"math"
|
|
"sync"
|
|
"unsafe"
|
|
)
|
|
|
|
type arenaAddr struct {
|
|
blockIdx uint32
|
|
blockOffset uint32
|
|
}
|
|
|
|
func (addr arenaAddr) isNull() bool {
|
|
return addr.blockIdx == 0 && addr.blockOffset == 0
|
|
}
|
|
|
|
func newArenaAddr(idx int, offset uint32) arenaAddr {
|
|
return arenaAddr{
|
|
blockIdx: uint32(idx) + 1,
|
|
blockOffset: offset,
|
|
}
|
|
}
|
|
|
|
const (
|
|
alignMask = 1<<32 - 8 // 29 bit 1 and 3 bit 0.
|
|
|
|
nullBlockOffset = math.MaxUint32
|
|
maxBlockSize = 128 << 20
|
|
)
|
|
|
|
type arena struct {
|
|
sync.Mutex
|
|
blockSize int
|
|
blocks []arenaBlock
|
|
}
|
|
|
|
type arenaSnapshot struct {
|
|
blockSize int
|
|
blocks int
|
|
offsetInBlock int
|
|
}
|
|
|
|
func newArenaLocator() *arena {
|
|
return new(arena)
|
|
}
|
|
|
|
func (a *arena) snapshot() arenaSnapshot {
|
|
a.Lock()
|
|
snap := arenaSnapshot{
|
|
blockSize: a.blockSize,
|
|
blocks: len(a.blocks),
|
|
}
|
|
if len(a.blocks) > 0 {
|
|
snap.offsetInBlock = a.blocks[len(a.blocks)-1].length
|
|
}
|
|
a.Unlock()
|
|
return snap
|
|
}
|
|
|
|
func (a *arena) revert(snap arenaSnapshot) {
|
|
a.Lock()
|
|
for i := snap.blocks; i < len(a.blocks); i++ {
|
|
a.blocks[i] = arenaBlock{}
|
|
}
|
|
a.blocks = a.blocks[:snap.blocks]
|
|
if len(a.blocks) > 0 {
|
|
a.blocks[len(a.blocks)-1].length = snap.offsetInBlock
|
|
}
|
|
a.blockSize = snap.blockSize
|
|
a.Unlock()
|
|
}
|
|
|
|
func (a *arena) newNode(key []byte, v []byte, height int) (*node, arenaAddr) {
|
|
// The base level is already allocated in the node struct.
|
|
nodeSize := nodeHeaderSize + height*8 + 8 + len(key) + len(v)
|
|
addr, data := a.alloc(nodeSize)
|
|
node := (*node)(unsafe.Pointer(&data[0]))
|
|
node.keyLen = uint16(len(key))
|
|
node.height = uint8(height)
|
|
node.valLen = uint32(len(v))
|
|
copy(data[node.nodeLen():], key)
|
|
copy(data[node.nodeLen()+int(node.keyLen):], v)
|
|
return node, addr
|
|
}
|
|
|
|
func (a *arena) getFrom(addr arenaAddr) []byte {
|
|
a.Lock()
|
|
block := &a.blocks[addr.blockIdx-1]
|
|
a.Unlock()
|
|
return block.getFrom(addr.blockOffset)
|
|
}
|
|
|
|
func (a *arena) alloc(size int) (arenaAddr, []byte) {
|
|
if size > maxBlockSize {
|
|
panic("alloc size is larger than max block size")
|
|
}
|
|
|
|
if len(a.blocks) == 0 {
|
|
a.enlarge(size, initBlockSize)
|
|
}
|
|
|
|
addr, data := a.allocInLastBlock(size)
|
|
if !addr.isNull() {
|
|
return addr, data
|
|
}
|
|
|
|
a.enlarge(size, a.blockSize<<1)
|
|
return a.allocInLastBlock(size)
|
|
}
|
|
|
|
func (a *arena) enlarge(allocSize, blockSize int) {
|
|
a.blockSize = blockSize
|
|
for a.blockSize <= allocSize {
|
|
a.blockSize <<= 1
|
|
}
|
|
// Size will never larger than maxBlockSize.
|
|
if a.blockSize > maxBlockSize {
|
|
a.blockSize = maxBlockSize
|
|
}
|
|
block := newArenaBlock(a.blockSize)
|
|
|
|
a.Lock()
|
|
a.blocks = append(a.blocks, block)
|
|
a.Unlock()
|
|
}
|
|
|
|
func (a *arena) allocInLastBlock(size int) (arenaAddr, []byte) {
|
|
idx := len(a.blocks) - 1
|
|
offset, data := a.blocks[idx].alloc(size)
|
|
if offset == nullBlockOffset {
|
|
return arenaAddr{}, nil
|
|
}
|
|
return newArenaAddr(idx, offset), data
|
|
}
|
|
|
|
type arenaBlock struct {
|
|
buf []byte
|
|
length int
|
|
}
|
|
|
|
func newArenaBlock(blockSize int) arenaBlock {
|
|
return arenaBlock{
|
|
buf: make([]byte, blockSize),
|
|
}
|
|
}
|
|
|
|
func (a *arenaBlock) getFrom(offset uint32) []byte {
|
|
return a.buf[offset:]
|
|
}
|
|
|
|
func (a *arenaBlock) alloc(size int) (uint32, []byte) {
|
|
// We must align the allocated address for node
|
|
// to make runtime.checkptrAlignment happy.
|
|
offset := (a.length + 7) & alignMask
|
|
newLen := offset + size
|
|
if newLen > len(a.buf) {
|
|
return nullBlockOffset, nil
|
|
}
|
|
a.length = newLen
|
|
return uint32(offset), a.buf[offset : offset+size]
|
|
}
|
|
|