Line data    Source code

       1             : /*
       2             :  * Copyright 2017 Dgraph Labs, Inc. and Contributors
       3             :  * Modifications copyright (C) 2017 Andy Kimball and Contributors
       4             :  *
       5             :  * Licensed under the Apache License, Version 2.0 (the "License");
       6             :  * you may not use this file except in compliance with the License.
       7             :  * You may obtain a copy of the License at
       8             :  *
       9             :  *     http://www.apache.org/licenses/LICENSE-2.0
      10             :  *
      11             :  * Unless required by applicable law or agreed to in writing, software
      12             :  * distributed under the License is distributed on an "AS IS" BASIS,
      13             :  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      14             :  * See the License for the specific language governing permissions and
      15             :  * limitations under the License.
      16             :  */
      17             : 
      18             : package arenaskl
      19             : 
      20             : import (
      21             :         "math"
      22             :         "sync/atomic"
      23             : 
      24             :         "github.com/cockroachdb/pebble/internal/base"
      25             : )
      26             : 
      27             : // MaxNodeSize returns the maximum space needed for a node with the specified
      28             : // key and value sizes. This could overflow a uint32, which is why a uint64
      29             : // is used here. If a key/value overflows a uint32, it should not be added to
      30             : // the skiplist.
      31           2 : func MaxNodeSize(keySize, valueSize uint32) uint64 {
      32           2 :         const maxPadding = nodeAlignment - 1
      33           2 :         return uint64(maxNodeSize) + uint64(keySize) + uint64(valueSize) + maxPadding
      34           2 : }
      35             : 
      36             : type links struct {
      37             :         nextOffset atomic.Uint32
      38             :         prevOffset atomic.Uint32
      39             : }
      40             : 
      41           2 : func (l *links) init(prevOffset, nextOffset uint32) {
      42           2 :         l.nextOffset.Store(nextOffset)
      43           2 :         l.prevOffset.Store(prevOffset)
      44           2 : }
      45             : 
      46             : type node struct {
      47             :         // Immutable fields, so no need to lock to access key.
      48             :         keyOffset  uint32
      49             :         keySize    uint32
      50             :         keyTrailer base.InternalKeyTrailer
      51             :         valueSize  uint32
      52             : 
      53             :         // Padding to align tower on an 8-byte boundary, so that 32-bit and 64-bit
      54             :         // architectures use the same memory layout for node. Needed for tests which
      55             :         // expect a certain struct size. The padding can be removed if we add or
      56             :         // remove a field from the node.
      57             :         _ [4]byte
      58             : 
      59             :         // Most nodes do not need to use the full height of the tower, since the
      60             :         // probability of each successive level decreases exponentially. Because
      61             :         // these elements are never accessed, they do not need to be allocated.
      62             :         // Therefore, when a node is allocated in the arena, its memory footprint
      63             :         // is deliberately truncated to not include unneeded tower elements.
      64             :         //
      65             :         // All accesses to elements should use CAS operations, with no need to lock.
      66             :         tower [maxHeight]links
      67             : }
      68             : 
      69             : func newNode(
      70             :         arena *Arena, height uint32, key base.InternalKey, value []byte,
      71           2 : ) (nd *node, err error) {
      72           2 :         if height < 1 || height > maxHeight {
      73           0 :                 panic("height cannot be less than one or greater than the max height")
      74             :         }
      75           2 :         keySize := len(key.UserKey)
      76           2 :         if int64(keySize) > math.MaxUint32 {
      77           0 :                 panic("key is too large")
      78             :         }
      79           2 :         valueSize := len(value)
      80           2 :         if int64(len(value)) > math.MaxUint32 {
      81           0 :                 panic("value is too large")
      82             :         }
      83           2 :         if int64(len(value))+int64(keySize)+int64(maxNodeSize) > math.MaxUint32 {
      84           0 :                 panic("combined key and value size is too large")
      85             :         }
      86             : 
      87           2 :         nd, err = newRawNode(arena, height, uint32(keySize), uint32(valueSize))
      88           2 :         if err != nil {
      89           1 :                 return
      90           1 :         }
      91           2 :         nd.keyTrailer = key.Trailer
      92           2 :         copy(nd.getKeyBytes(arena), key.UserKey)
      93           2 :         copy(nd.getValue(arena), value)
      94           2 :         return
      95             : }
      96             : 
      97           2 : func newRawNode(arena *Arena, height uint32, keySize, valueSize uint32) (nd *node, err error) {
      98           2 :         // Compute the amount of the tower that will never be used, since the height
      99           2 :         // is less than maxHeight.
     100           2 :         unusedSize := uint32((maxHeight - int(height)) * linksSize)
     101           2 :         nodeSize := uint32(maxNodeSize) - unusedSize
     102           2 : 
     103           2 :         nodeOffset, err := arena.alloc(nodeSize+keySize+valueSize, nodeAlignment, unusedSize)
     104           2 :         if err != nil {
     105           1 :                 return
     106           1 :         }
     107             : 
     108           2 :         nd = (*node)(arena.getPointer(nodeOffset))
     109           2 :         nd.keyOffset = nodeOffset + nodeSize
     110           2 :         nd.keySize = keySize
     111           2 :         nd.valueSize = valueSize
     112           2 :         return
     113             : }
     114             : 
     115           2 : func (n *node) getKeyBytes(arena *Arena) []byte {
     116           2 :         return arena.getBytes(n.keyOffset, n.keySize)
     117           2 : }
     118             : 
     119           2 : func (n *node) getValue(arena *Arena) []byte {
     120           2 :         return arena.getBytes(n.keyOffset+n.keySize, uint32(n.valueSize))
     121           2 : }
     122             : 
     123           1 : func (n *node) nextOffset(h int) uint32 {
     124           1 :         return n.tower[h].nextOffset.Load()
     125           1 : }
     126             : 
     127           2 : func (n *node) prevOffset(h int) uint32 {
     128           2 :         return n.tower[h].prevOffset.Load()
     129           2 : }
     130             : 
     131           2 : func (n *node) casNextOffset(h int, old, val uint32) bool {
     132           2 :         return n.tower[h].nextOffset.CompareAndSwap(old, val)
     133           2 : }
     134             : 
     135           2 : func (n *node) casPrevOffset(h int, old, val uint32) bool {
     136           2 :         return n.tower[h].prevOffset.CompareAndSwap(old, val)
     137           2 : }