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 1 : func MaxNodeSize(keySize, valueSize uint32) uint64 {
32 1 : const maxPadding = nodeAlignment - 1
33 1 : return uint64(maxNodeSize) + uint64(keySize) + uint64(valueSize) + maxPadding
34 1 : }
35 :
36 : type links struct {
37 : nextOffset atomic.Uint32
38 : prevOffset atomic.Uint32
39 : }
40 :
41 1 : func (l *links) init(prevOffset, nextOffset uint32) {
42 1 : l.nextOffset.Store(nextOffset)
43 1 : l.prevOffset.Store(prevOffset)
44 1 : }
45 :
46 : type node struct {
47 : // Immutable fields, so no need to lock to access key.
48 : keyOffset uint32
49 : keySize uint32
50 : keyTrailer uint64
51 : valueSize uint32
52 : allocSize uint32
53 :
54 : // Most nodes do not need to use the full height of the tower, since the
55 : // probability of each successive level decreases exponentially. Because
56 : // these elements are never accessed, they do not need to be allocated.
57 : // Therefore, when a node is allocated in the arena, its memory footprint
58 : // is deliberately truncated to not include unneeded tower elements.
59 : //
60 : // All accesses to elements should use CAS operations, with no need to lock.
61 : tower [maxHeight]links
62 : }
63 :
64 : func newNode(
65 : arena *Arena, height uint32, key base.InternalKey, value []byte,
66 1 : ) (nd *node, err error) {
67 1 : if height < 1 || height > maxHeight {
68 0 : panic("height cannot be less than one or greater than the max height")
69 : }
70 1 : keySize := len(key.UserKey)
71 1 : if int64(keySize) > math.MaxUint32 {
72 0 : panic("key is too large")
73 : }
74 1 : valueSize := len(value)
75 1 : if int64(len(value)) > math.MaxUint32 {
76 0 : panic("value is too large")
77 : }
78 1 : if int64(len(value))+int64(keySize)+int64(maxNodeSize) > math.MaxUint32 {
79 0 : panic("combined key and value size is too large")
80 : }
81 :
82 1 : nd, err = newRawNode(arena, height, uint32(keySize), uint32(valueSize))
83 1 : if err != nil {
84 1 : return
85 1 : }
86 1 : nd.keyTrailer = key.Trailer
87 1 : copy(nd.getKeyBytes(arena), key.UserKey)
88 1 : copy(nd.getValue(arena), value)
89 1 : return
90 : }
91 :
92 1 : func newRawNode(arena *Arena, height uint32, keySize, valueSize uint32) (nd *node, err error) {
93 1 : // Compute the amount of the tower that will never be used, since the height
94 1 : // is less than maxHeight.
95 1 : unusedSize := uint32((maxHeight - int(height)) * linksSize)
96 1 : nodeSize := uint32(maxNodeSize) - unusedSize
97 1 :
98 1 : nodeOffset, allocSize, err := arena.alloc(nodeSize+keySize+valueSize, nodeAlignment, unusedSize)
99 1 : if err != nil {
100 1 : return
101 1 : }
102 :
103 1 : nd = (*node)(arena.getPointer(nodeOffset))
104 1 : nd.keyOffset = nodeOffset + nodeSize
105 1 : nd.keySize = keySize
106 1 : nd.valueSize = valueSize
107 1 : nd.allocSize = allocSize
108 1 : return
109 : }
110 :
111 1 : func (n *node) getKeyBytes(arena *Arena) []byte {
112 1 : return arena.getBytes(n.keyOffset, n.keySize)
113 1 : }
114 :
115 1 : func (n *node) getValue(arena *Arena) []byte {
116 1 : return arena.getBytes(n.keyOffset+n.keySize, uint32(n.valueSize))
117 1 : }
118 :
119 1 : func (n *node) nextOffset(h int) uint32 {
120 1 : return n.tower[h].nextOffset.Load()
121 1 : }
122 :
123 1 : func (n *node) prevOffset(h int) uint32 {
124 1 : return n.tower[h].prevOffset.Load()
125 1 : }
126 :
127 1 : func (n *node) casNextOffset(h int, old, val uint32) bool {
128 1 : return n.tower[h].nextOffset.CompareAndSwap(old, val)
129 1 : }
130 :
131 1 : func (n *node) casPrevOffset(h int, old, val uint32) bool {
132 1 : return n.tower[h].prevOffset.CompareAndSwap(old, val)
133 1 : }
|
