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

// 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]
}