Bug Summary

File:home/bhubbard/working/src/ceph/src/rocksdb/memtable/skiplistrep.cc
Warning:line 826, column 13
The left operand of '!=' is a garbage value

Annotated Source Code

[?] Use j/k keys for keyboard navigation

/home/bhubbard/working/src/ceph/src/rocksdb/memtable/skiplistrep.cc

→
1// Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2// This source code is licensed under both the GPLv2 (found in the
3// COPYING file in the root directory) and Apache 2.0 License
4// (found in the LICENSE.Apache file in the root directory).
5//
6#include "memtable/inlineskiplist.h"
7#include "db/memtable.h"
8#include "rocksdb/memtablerep.h"
9#include "util/arena.h"
10
11namespace rocksdb {
12namespace {
13class SkipListRep : public MemTableRep {
14 InlineSkipList<const MemTableRep::KeyComparator&> skip_list_;
15 const MemTableRep::KeyComparator& cmp_;
16 const SliceTransform* transform_;
17 const size_t lookahead_;
18
19 friend class LookaheadIterator;
20public:
21 explicit SkipListRep(const MemTableRep::KeyComparator& compare,
22 Allocator* allocator, const SliceTransform* transform,
23 const size_t lookahead)
24 : MemTableRep(allocator),
25 skip_list_(compare, allocator),
26 cmp_(compare),
27 transform_(transform),
28 lookahead_(lookahead) {}
29
30 KeyHandle Allocate(const size_t len, char** buf) override {
31 *buf = skip_list_.AllocateKey(len);
32 return static_cast<KeyHandle>(*buf);
33 }
34
35 // Insert key into the list.
36 // REQUIRES: nothing that compares equal to key is currently in the list.
37 void Insert(KeyHandle handle) override {
38 skip_list_.Insert(static_cast<char*>(handle));
39 }
40
41 bool InsertKey(KeyHandle handle) override {
42 return skip_list_.Insert(static_cast<char*>(handle));
43 }
44
45 void InsertWithHint(KeyHandle handle, void** hint) override {
46 skip_list_.InsertWithHint(static_cast<char*>(handle), hint);
47 }
48
49 bool InsertKeyWithHint(KeyHandle handle, void** hint) override {
50 return skip_list_.InsertWithHint(static_cast<char*>(handle), hint);
51 }
52
53 void InsertConcurrently(KeyHandle handle) override {
54 skip_list_.InsertConcurrently(static_cast<char*>(handle));
55 }
56
57 bool InsertKeyConcurrently(KeyHandle handle) override {
58 return skip_list_.InsertConcurrently(static_cast<char*>(handle));
1
Calling 'InlineSkipList::InsertConcurrently'
→
59 }
60
61 // Returns true iff an entry that compares equal to key is in the list.
62 bool Contains(const char* key) const override {
63 return skip_list_.Contains(key);
64 }
65
66 size_t ApproximateMemoryUsage() override {
67 // All memory is allocated through allocator; nothing to report here
68 return 0;
69 }
70
71 void Get(const LookupKey& k, void* callback_args,
72 bool (*callback_func)(void* arg, const char* entry)) override {
73 SkipListRep::Iterator iter(&skip_list_);
74 Slice dummy_slice;
75 for (iter.Seek(dummy_slice, k.memtable_key().data());
76 iter.Valid() && callback_func(callback_args, iter.key()); iter.Next()) {
77 }
78 }
79
80 uint64_t ApproximateNumEntries(const Slice& start_ikey,
81 const Slice& end_ikey) override {
82 std::string tmp;
83 uint64_t start_count =
84 skip_list_.EstimateCount(EncodeKey(&tmp, start_ikey));
85 uint64_t end_count = skip_list_.EstimateCount(EncodeKey(&tmp, end_ikey));
86 return (end_count >= start_count) ? (end_count - start_count) : 0;
87 }
88
89 ~SkipListRep() override {}
90
91 // Iteration over the contents of a skip list
92 class Iterator : public MemTableRep::Iterator {
93 InlineSkipList<const MemTableRep::KeyComparator&>::Iterator iter_;
94
95 public:
96 // Initialize an iterator over the specified list.
97 // The returned iterator is not valid.
98 explicit Iterator(
99 const InlineSkipList<const MemTableRep::KeyComparator&>* list)
100 : iter_(list) {}
101
102 ~Iterator() override {}
103
104 // Returns true iff the iterator is positioned at a valid node.
105 bool Valid() const override { return iter_.Valid(); }
106
107 // Returns the key at the current position.
108 // REQUIRES: Valid()
109 const char* key() const override { return iter_.key(); }
110
111 // Advances to the next position.
112 // REQUIRES: Valid()
113 void Next() override { iter_.Next(); }
114
115 // Advances to the previous position.
116 // REQUIRES: Valid()
117 void Prev() override { iter_.Prev(); }
118
119 // Advance to the first entry with a key >= target
120 void Seek(const Slice& user_key, const char* memtable_key) override {
121 if (memtable_key != nullptr) {
122 iter_.Seek(memtable_key);
123 } else {
124 iter_.Seek(EncodeKey(&tmp_, user_key));
125 }
126 }
127
128 // Retreat to the last entry with a key <= target
129 void SeekForPrev(const Slice& user_key, const char* memtable_key) override {
130 if (memtable_key != nullptr) {
131 iter_.SeekForPrev(memtable_key);
132 } else {
133 iter_.SeekForPrev(EncodeKey(&tmp_, user_key));
134 }
135 }
136
137 // Position at the first entry in list.
138 // Final state of iterator is Valid() iff list is not empty.
139 void SeekToFirst() override { iter_.SeekToFirst(); }
140
141 // Position at the last entry in list.
142 // Final state of iterator is Valid() iff list is not empty.
143 void SeekToLast() override { iter_.SeekToLast(); }
144
145 protected:
146 std::string tmp_; // For passing to EncodeKey
147 };
148
149 // Iterator over the contents of a skip list which also keeps track of the
150 // previously visited node. In Seek(), it examines a few nodes after it
151 // first, falling back to O(log n) search from the head of the list only if
152 // the target key hasn't been found.
153 class LookaheadIterator : public MemTableRep::Iterator {
154 public:
155 explicit LookaheadIterator(const SkipListRep& rep) :
156 rep_(rep), iter_(&rep_.skip_list_), prev_(iter_) {}
157
158 ~LookaheadIterator() override {}
159
160 bool Valid() const override { return iter_.Valid(); }
161
162 const char* key() const override {
163 assert(Valid())(static_cast<void> (0));
164 return iter_.key();
165 }
166
167 void Next() override {
168 assert(Valid())(static_cast<void> (0));
169
170 bool advance_prev = true;
171 if (prev_.Valid()) {
172 auto k1 = rep_.UserKey(prev_.key());
173 auto k2 = rep_.UserKey(iter_.key());
174
175 if (k1.compare(k2) == 0) {
176 // same user key, don't move prev_
177 advance_prev = false;
178 } else if (rep_.transform_) {
179 // only advance prev_ if it has the same prefix as iter_
180 auto t1 = rep_.transform_->Transform(k1);
181 auto t2 = rep_.transform_->Transform(k2);
182 advance_prev = t1.compare(t2) == 0;
183 }
184 }
185
186 if (advance_prev) {
187 prev_ = iter_;
188 }
189 iter_.Next();
190 }
191
192 void Prev() override {
193 assert(Valid())(static_cast<void> (0));
194 iter_.Prev();
195 prev_ = iter_;
196 }
197
198 void Seek(const Slice& internal_key, const char* memtable_key) override {
199 const char *encoded_key =
200 (memtable_key != nullptr) ?
201 memtable_key : EncodeKey(&tmp_, internal_key);
202
203 if (prev_.Valid() && rep_.cmp_(encoded_key, prev_.key()) >= 0) {
204 // prev_.key() is smaller or equal to our target key; do a quick
205 // linear search (at most lookahead_ steps) starting from prev_
206 iter_ = prev_;
207
208 size_t cur = 0;
209 while (cur++ <= rep_.lookahead_ && iter_.Valid()) {
210 if (rep_.cmp_(encoded_key, iter_.key()) <= 0) {
211 return;
212 }
213 Next();
214 }
215 }
216
217 iter_.Seek(encoded_key);
218 prev_ = iter_;
219 }
220
221 void SeekForPrev(const Slice& internal_key,
222 const char* memtable_key) override {
223 const char* encoded_key = (memtable_key != nullptr)
224 ? memtable_key
225 : EncodeKey(&tmp_, internal_key);
226 iter_.SeekForPrev(encoded_key);
227 prev_ = iter_;
228 }
229
230 void SeekToFirst() override {
231 iter_.SeekToFirst();
232 prev_ = iter_;
233 }
234
235 void SeekToLast() override {
236 iter_.SeekToLast();
237 prev_ = iter_;
238 }
239
240 protected:
241 std::string tmp_; // For passing to EncodeKey
242
243 private:
244 const SkipListRep& rep_;
245 InlineSkipList<const MemTableRep::KeyComparator&>::Iterator iter_;
246 InlineSkipList<const MemTableRep::KeyComparator&>::Iterator prev_;
247 };
248
249 MemTableRep::Iterator* GetIterator(Arena* arena = nullptr) override {
250 if (lookahead_ > 0) {
251 void *mem =
252 arena ? arena->AllocateAligned(sizeof(SkipListRep::LookaheadIterator))
253 : operator new(sizeof(SkipListRep::LookaheadIterator));
254 return new (mem) SkipListRep::LookaheadIterator(*this);
255 } else {
256 void *mem =
257 arena ? arena->AllocateAligned(sizeof(SkipListRep::Iterator))
258 : operator new(sizeof(SkipListRep::Iterator));
259 return new (mem) SkipListRep::Iterator(&skip_list_);
260 }
261 }
262};
263}
264
265MemTableRep* SkipListFactory::CreateMemTableRep(
266 const MemTableRep::KeyComparator& compare, Allocator* allocator,
267 const SliceTransform* transform, Logger* /*logger*/) {
268 return new SkipListRep(compare, allocator, transform, lookahead_);
269}
270
271} // namespace rocksdb
←

/home/bhubbard/working/src/ceph/src/rocksdb/memtable/inlineskiplist.h

1// Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2// This source code is licensed under both the GPLv2 (found in the
3// COPYING file in the root directory) and Apache 2.0 License
4// (found in the LICENSE.Apache file in the root directory).
5//
6// Copyright (c) 2011 The LevelDB Authors. All rights reserved. Use of
7// this source code is governed by a BSD-style license that can be found
8// in the LICENSE file. See the AUTHORS file for names of contributors.
9//
10// InlineSkipList is derived from SkipList (skiplist.h), but it optimizes
11// the memory layout by requiring that the key storage be allocated through
12// the skip list instance. For the common case of SkipList<const char*,
13// Cmp> this saves 1 pointer per skip list node and gives better cache
14// locality, at the expense of wasted padding from using AllocateAligned
15// instead of Allocate for the keys. The unused padding will be from
16// 0 to sizeof(void*)-1 bytes, and the space savings are sizeof(void*)
17// bytes, so despite the padding the space used is always less than
18// SkipList<const char*, ..>.
19//
20// Thread safety -------------
21//
22// Writes via Insert require external synchronization, most likely a mutex.
23// InsertConcurrently can be safely called concurrently with reads and
24// with other concurrent inserts. Reads require a guarantee that the
25// InlineSkipList will not be destroyed while the read is in progress.
26// Apart from that, reads progress without any internal locking or
27// synchronization.
28//
29// Invariants:
30//
31// (1) Allocated nodes are never deleted until the InlineSkipList is
32// destroyed. This is trivially guaranteed by the code since we never
33// delete any skip list nodes.
34//
35// (2) The contents of a Node except for the next/prev pointers are
36// immutable after the Node has been linked into the InlineSkipList.
37// Only Insert() modifies the list, and it is careful to initialize a
38// node and use release-stores to publish the nodes in one or more lists.
39//
40// ... prev vs. next pointer ordering ...
41//
42
43#pragma once
44#include <assert.h>
45#include <stdlib.h>
46#include <algorithm>
47#include <atomic>
48#include <type_traits>
49#include "port/likely.h"
50#include "port/port.h"
51#include "rocksdb/slice.h"
52#include "util/allocator.h"
53#include "util/coding.h"
54#include "util/random.h"
55
56namespace rocksdb {
57
58template <class Comparator>
59class InlineSkipList {
60 private:
61 struct Node;
62 struct Splice;
63
64 public:
65 using DecodedKey = \
66 typename std::remove_reference<Comparator>::type::DecodedType;
67
68 static const uint16_t kMaxPossibleHeight = 32;
69
70 // Create a new InlineSkipList object that will use "cmp" for comparing
71 // keys, and will allocate memory using "*allocator". Objects allocated
72 // in the allocator must remain allocated for the lifetime of the
73 // skiplist object.
74 explicit InlineSkipList(Comparator cmp, Allocator* allocator,
75 int32_t max_height = 12,
76 int32_t branching_factor = 4);
77
78 // Allocates a key and a skip-list node, returning a pointer to the key
79 // portion of the node. This method is thread-safe if the allocator
80 // is thread-safe.
81 char* AllocateKey(size_t key_size);
82
83 // Allocate a splice using allocator.
84 Splice* AllocateSplice();
85
86 // Inserts a key allocated by AllocateKey, after the actual key value
87 // has been filled in.
88 //
89 // REQUIRES: nothing that compares equal to key is currently in the list.
90 // REQUIRES: no concurrent calls to any of inserts.
91 bool Insert(const char* key);
92
93 // Inserts a key allocated by AllocateKey with a hint of last insert
94 // position in the skip-list. If hint points to nullptr, a new hint will be
95 // populated, which can be used in subsequent calls.
96 //
97 // It can be used to optimize the workload where there are multiple groups
98 // of keys, and each key is likely to insert to a location close to the last
99 // inserted key in the same group. One example is sequential inserts.
100 //
101 // REQUIRES: nothing that compares equal to key is currently in the list.
102 // REQUIRES: no concurrent calls to any of inserts.
103 bool InsertWithHint(const char* key, void** hint);
104
105 // Like Insert, but external synchronization is not required.
106 bool InsertConcurrently(const char* key);
107
108 // Inserts a node into the skip list. key must have been allocated by
109 // AllocateKey and then filled in by the caller. If UseCAS is true,
110 // then external synchronization is not required, otherwise this method
111 // may not be called concurrently with any other insertions.
112 //
113 // Regardless of whether UseCAS is true, the splice must be owned
114 // exclusively by the current thread. If allow_partial_splice_fix is
115 // true, then the cost of insertion is amortized O(log D), where D is
116 // the distance from the splice to the inserted key (measured as the
117 // number of intervening nodes). Note that this bound is very good for
118 // sequential insertions! If allow_partial_splice_fix is false then
119 // the existing splice will be ignored unless the current key is being
120 // inserted immediately after the splice. allow_partial_splice_fix ==
121 // false has worse running time for the non-sequential case O(log N),
122 // but a better constant factor.
123 template <bool UseCAS>
124 bool Insert(const char* key, Splice* splice, bool allow_partial_splice_fix);
125
126 // Returns true iff an entry that compares equal to key is in the list.
127 bool Contains(const char* key) const;
128
129 // Return estimated number of entries smaller than `key`.
130 uint64_t EstimateCount(const char* key) const;
131
132 // Validate correctness of the skip-list.
133 void TEST_Validate() const;
134
135 // Iteration over the contents of a skip list
136 class Iterator {
137 public:
138 // Initialize an iterator over the specified list.
139 // The returned iterator is not valid.
140 explicit Iterator(const InlineSkipList* list);
141
142 // Change the underlying skiplist used for this iterator
143 // This enables us not changing the iterator without deallocating
144 // an old one and then allocating a new one
145 void SetList(const InlineSkipList* list);
146
147 // Returns true iff the iterator is positioned at a valid node.
148 bool Valid() const;
149
150 // Returns the key at the current position.
151 // REQUIRES: Valid()
152 const char* key() const;
153
154 // Advances to the next position.
155 // REQUIRES: Valid()
156 void Next();
157
158 // Advances to the previous position.
159 // REQUIRES: Valid()
160 void Prev();
161
162 // Advance to the first entry with a key >= target
163 void Seek(const char* target);
164
165 // Retreat to the last entry with a key <= target
166 void SeekForPrev(const char* target);
167
168 // Position at the first entry in list.
169 // Final state of iterator is Valid() iff list is not empty.
170 void SeekToFirst();
171
172 // Position at the last entry in list.
173 // Final state of iterator is Valid() iff list is not empty.
174 void SeekToLast();
175
176 private:
177 const InlineSkipList* list_;
178 Node* node_;
179 // Intentionally copyable
180 };
181
182 private:
183 const uint16_t kMaxHeight_;
184 const uint16_t kBranching_;
185 const uint32_t kScaledInverseBranching_;
186
187 Allocator* const allocator_; // Allocator used for allocations of nodes
188 // Immutable after construction
189 Comparator const compare_;
190 Node* const head_;
191
192 // Modified only by Insert(). Read racily by readers, but stale
193 // values are ok.
194 std::atomic<int> max_height_; // Height of the entire list
195
196 // seq_splice_ is a Splice used for insertions in the non-concurrent
197 // case. It caches the prev and next found during the most recent
198 // non-concurrent insertion.
199 Splice* seq_splice_;
200
201 inline int GetMaxHeight() const {
202 return max_height_.load(std::memory_order_relaxed);
203 }
204
205 int RandomHeight();
206
207 Node* AllocateNode(size_t key_size, int height);
208
209 bool Equal(const char* a, const char* b) const {
210 return (compare_(a, b) == 0);
211 }
212
213 bool LessThan(const char* a, const char* b) const {
214 return (compare_(a, b) < 0);
215 }
216
217 // Return true if key is greater than the data stored in "n". Null n
218 // is considered infinite. n should not be head_.
219 bool KeyIsAfterNode(const char* key, Node* n) const;
220 bool KeyIsAfterNode(const DecodedKey& key, Node* n) const;
221
222 // Returns the earliest node with a key >= key.
223 // Return nullptr if there is no such node.
224 Node* FindGreaterOrEqual(const char* key) const;
225
226 // Return the latest node with a key < key.
227 // Return head_ if there is no such node.
228 // Fills prev[level] with pointer to previous node at "level" for every
229 // level in [0..max_height_-1], if prev is non-null.
230 Node* FindLessThan(const char* key, Node** prev = nullptr) const;
231
232 // Return the latest node with a key < key on bottom_level. Start searching
233 // from root node on the level below top_level.
234 // Fills prev[level] with pointer to previous node at "level" for every
235 // level in [bottom_level..top_level-1], if prev is non-null.
236 Node* FindLessThan(const char* key, Node** prev, Node* root, int top_level,
237 int bottom_level) const;
238
239 // Return the last node in the list.
240 // Return head_ if list is empty.
241 Node* FindLast() const;
242
243 // Traverses a single level of the list, setting *out_prev to the last
244 // node before the key and *out_next to the first node after. Assumes
245 // that the key is not present in the skip list. On entry, before should
246 // point to a node that is before the key, and after should point to
247 // a node that is after the key. after should be nullptr if a good after
248 // node isn't conveniently available.
249 template<bool prefetch_before>
250 void FindSpliceForLevel(const DecodedKey& key, Node* before, Node* after, int level,
251 Node** out_prev, Node** out_next);
252
253 // Recomputes Splice levels from highest_level (inclusive) down to
254 // lowest_level (inclusive).
255 void RecomputeSpliceLevels(const DecodedKey& key, Splice* splice,
256 int recompute_level);
257
258 // No copying allowed
259 InlineSkipList(const InlineSkipList&);
260 InlineSkipList& operator=(const InlineSkipList&);
261};
262
263// Implementation details follow
264
265template <class Comparator>
266struct InlineSkipList<Comparator>::Splice {
267 // The invariant of a Splice is that prev_[i+1].key <= prev_[i].key <
268 // next_[i].key <= next_[i+1].key for all i. That means that if a
269 // key is bracketed by prev_[i] and next_[i] then it is bracketed by
270 // all higher levels. It is _not_ required that prev_[i]->Next(i) ==
271 // next_[i] (it probably did at some point in the past, but intervening
272 // or concurrent operations might have inserted nodes in between).
273 int height_ = 0;
274 Node** prev_;
275 Node** next_;
276};
277
278// The Node data type is more of a pointer into custom-managed memory than
279// a traditional C++ struct. The key is stored in the bytes immediately
280// after the struct, and the next_ pointers for nodes with height > 1 are
281// stored immediately _before_ the struct. This avoids the need to include
282// any pointer or sizing data, which reduces per-node memory overheads.
283template <class Comparator>
284struct InlineSkipList<Comparator>::Node {
285 // Stores the height of the node in the memory location normally used for
286 // next_[0]. This is used for passing data from AllocateKey to Insert.
287 void StashHeight(const int height) {
288 assert(sizeof(int) <= sizeof(next_[0]))(static_cast<void> (0));
289 memcpy(static_cast<void*>(&next_[0]), &height, sizeof(int));
290 }
291
292 // Retrieves the value passed to StashHeight. Undefined after a call
293 // to SetNext or NoBarrier_SetNext.
294 int UnstashHeight() const {
295 int rv;
296 memcpy(&rv, &next_[0], sizeof(int));
297 return rv;
298 }
299
300 const char* Key() const { return reinterpret_cast<const char*>(&next_[1]); }
301
302 // Accessors/mutators for links. Wrapped in methods so we can add
303 // the appropriate barriers as necessary, and perform the necessary
304 // addressing trickery for storing links below the Node in memory.
305 Node* Next(int n) {
306 assert(n >= 0)(static_cast<void> (0));
307 // Use an 'acquire load' so that we observe a fully initialized
308 // version of the returned Node.
309 return ((&next_[0] - n)->load(std::memory_order_acquire));
310 }
311
312 void SetNext(int n, Node* x) {
313 assert(n >= 0)(static_cast<void> (0));
314 // Use a 'release store' so that anybody who reads through this
315 // pointer observes a fully initialized version of the inserted node.
316 (&next_[0] - n)->store(x, std::memory_order_release);
317 }
318
319 bool CASNext(int n, Node* expected, Node* x) {
320 assert(n >= 0)(static_cast<void> (0));
321 return (&next_[0] - n)->compare_exchange_strong(expected, x);
322 }
323
324 // No-barrier variants that can be safely used in a few locations.
325 Node* NoBarrier_Next(int n) {
326 assert(n >= 0)(static_cast<void> (0));
327 return (&next_[0] - n)->load(std::memory_order_relaxed);
328 }
329
330 void NoBarrier_SetNext(int n, Node* x) {
331 assert(n >= 0)(static_cast<void> (0));
332 (&next_[0] - n)->store(x, std::memory_order_relaxed);
333 }
334
335 // Insert node after prev on specific level.
336 void InsertAfter(Node* prev, int level) {
337 // NoBarrier_SetNext() suffices since we will add a barrier when
338 // we publish a pointer to "this" in prev.
339 NoBarrier_SetNext(level, prev->NoBarrier_Next(level));
340 prev->SetNext(level, this);
341 }
342
343 private:
344 // next_[0] is the lowest level link (level 0). Higher levels are
345 // stored _earlier_, so level 1 is at next_[-1].
346 std::atomic<Node*> next_[1];
347};
348
349template <class Comparator>
350inline InlineSkipList<Comparator>::Iterator::Iterator(
351 const InlineSkipList* list) {
352 SetList(list);
353}
354
355template <class Comparator>
356inline void InlineSkipList<Comparator>::Iterator::SetList(
357 const InlineSkipList* list) {
358 list_ = list;
359 node_ = nullptr;
360}
361
362template <class Comparator>
363inline bool InlineSkipList<Comparator>::Iterator::Valid() const {
364 return node_ != nullptr;
365}
366
367template <class Comparator>
368inline const char* InlineSkipList<Comparator>::Iterator::key() const {
369 assert(Valid())(static_cast<void> (0));
370 return node_->Key();
371}
372
373template <class Comparator>
374inline void InlineSkipList<Comparator>::Iterator::Next() {
375 assert(Valid())(static_cast<void> (0));
376 node_ = node_->Next(0);
377}
378
379template <class Comparator>
380inline void InlineSkipList<Comparator>::Iterator::Prev() {
381 // Instead of using explicit "prev" links, we just search for the
382 // last node that falls before key.
383 assert(Valid())(static_cast<void> (0));
384 node_ = list_->FindLessThan(node_->Key());
385 if (node_ == list_->head_) {
386 node_ = nullptr;
387 }
388}
389
390template <class Comparator>
391inline void InlineSkipList<Comparator>::Iterator::Seek(const char* target) {
392 node_ = list_->FindGreaterOrEqual(target);
393}
394
395template <class Comparator>
396inline void InlineSkipList<Comparator>::Iterator::SeekForPrev(
397 const char* target) {
398 Seek(target);
399 if (!Valid()) {
400 SeekToLast();
401 }
402 while (Valid() && list_->LessThan(target, key())) {
403 Prev();
404 }
405}
406
407template <class Comparator>
408inline void InlineSkipList<Comparator>::Iterator::SeekToFirst() {
409 node_ = list_->head_->Next(0);
410}
411
412template <class Comparator>
413inline void InlineSkipList<Comparator>::Iterator::SeekToLast() {
414 node_ = list_->FindLast();
415 if (node_ == list_->head_) {
416 node_ = nullptr;
417 }
418}
419
420template <class Comparator>
421int InlineSkipList<Comparator>::RandomHeight() {
422 auto rnd = Random::GetTLSInstance();
423
424 // Increase height with probability 1 in kBranching
425 int height = 1;
426 while (height < kMaxHeight_ && height < kMaxPossibleHeight &&
427 rnd->Next() < kScaledInverseBranching_) {
428 height++;
429 }
430 assert(height > 0)(static_cast<void> (0));
431 assert(height <= kMaxHeight_)(static_cast<void> (0));
432 assert(height <= kMaxPossibleHeight)(static_cast<void> (0));
433 return height;
434}
435
436template <class Comparator>
437bool InlineSkipList<Comparator>::KeyIsAfterNode(const char* key,
438 Node* n) const {
439 // nullptr n is considered infinite
440 assert(n != head_)(static_cast<void> (0));
441 return (n != nullptr) && (compare_(n->Key(), key) < 0);
442}
443
444template <class Comparator>
445bool InlineSkipList<Comparator>::KeyIsAfterNode(const DecodedKey& key,
446 Node* n) const {
447 // nullptr n is considered infinite
448 assert(n != head_)(static_cast<void> (0));
449 return (n != nullptr) && (compare_(n->Key(), key) < 0);
450}
451
452template <class Comparator>
453typename InlineSkipList<Comparator>::Node*
454InlineSkipList<Comparator>::FindGreaterOrEqual(const char* key) const {
455 // Note: It looks like we could reduce duplication by implementing
456 // this function as FindLessThan(key)->Next(0), but we wouldn't be able
457 // to exit early on equality and the result wouldn't even be correct.
458 // A concurrent insert might occur after FindLessThan(key) but before
459 // we get a chance to call Next(0).
460 Node* x = head_;
461 int level = GetMaxHeight() - 1;
462 Node* last_bigger = nullptr;
463 const DecodedKey key_decoded = compare_.decode_key(key);
464 while (true) {
465 Node* next = x->Next(level);
466 if (next != nullptr) {
467 PREFETCH(next->Next(level), 0, 1)__builtin_prefetch(next->Next(level), 0, 1);
468 }
469 // Make sure the lists are sorted
470 assert(x == head_ || next == nullptr || KeyIsAfterNode(next->Key(), x))(static_cast<void> (0));
471 // Make sure we haven't overshot during our search
472 assert(x == head_ || KeyIsAfterNode(key_decoded, x))(static_cast<void> (0));
473 int cmp = (next == nullptr || next == last_bigger)
474 ? 1
475 : compare_(next->Key(), key_decoded);
476 if (cmp == 0 || (cmp > 0 && level == 0)) {
477 return next;
478 } else if (cmp < 0) {
479 // Keep searching in this list
480 x = next;
481 } else {
482 // Switch to next list, reuse compare_() result
483 last_bigger = next;
484 level--;
485 }
486 }
487}
488
489template <class Comparator>
490typename InlineSkipList<Comparator>::Node*
491InlineSkipList<Comparator>::FindLessThan(const char* key, Node** prev) const {
492 return FindLessThan(key, prev, head_, GetMaxHeight(), 0);
493}
494
495template <class Comparator>
496typename InlineSkipList<Comparator>::Node*
497InlineSkipList<Comparator>::FindLessThan(const char* key, Node** prev,
498 Node* root, int top_level,
499 int bottom_level) const {
500 assert(top_level > bottom_level)(static_cast<void> (0));
501 int level = top_level - 1;
502 Node* x = root;
503 // KeyIsAfter(key, last_not_after) is definitely false
504 Node* last_not_after = nullptr;
505 const DecodedKey key_decoded = compare_.decode_key(key);
506 while (true) {
507 assert(x != nullptr)(static_cast<void> (0));
508 Node* next = x->Next(level);
509 if (next != nullptr) {
510 PREFETCH(next->Next(level), 0, 1)__builtin_prefetch(next->Next(level), 0, 1);
511 }
512 assert(x == head_ || next == nullptr || KeyIsAfterNode(next->Key(), x))(static_cast<void> (0));
513 assert(x == head_ || KeyIsAfterNode(key_decoded, x))(static_cast<void> (0));
514 if (next != last_not_after && KeyIsAfterNode(key_decoded, next)) {
515 // Keep searching in this list
516 assert(next != nullptr)(static_cast<void> (0));
517 x = next;
518 } else {
519 if (prev != nullptr) {
520 prev[level] = x;
521 }
522 if (level == bottom_level) {
523 return x;
524 } else {
525 // Switch to next list, reuse KeyIsAfterNode() result
526 last_not_after = next;
527 level--;
528 }
529 }
530 }
531}
532
533template <class Comparator>
534typename InlineSkipList<Comparator>::Node*
535InlineSkipList<Comparator>::FindLast() const {
536 Node* x = head_;
537 int level = GetMaxHeight() - 1;
538 while (true) {
539 Node* next = x->Next(level);
540 if (next == nullptr) {
541 if (level == 0) {
542 return x;
543 } else {
544 // Switch to next list
545 level--;
546 }
547 } else {
548 x = next;
549 }
550 }
551}
552
553template <class Comparator>
554uint64_t InlineSkipList<Comparator>::EstimateCount(const char* key) const {
555 uint64_t count = 0;
556
557 Node* x = head_;
558 int level = GetMaxHeight() - 1;
559 const DecodedKey key_decoded = compare_.decode_key(key);
560 while (true) {
561 assert(x == head_ || compare_(x->Key(), key_decoded) < 0)(static_cast<void> (0));
562 Node* next = x->Next(level);
563 if (next != nullptr) {
564 PREFETCH(next->Next(level), 0, 1)__builtin_prefetch(next->Next(level), 0, 1);
565 }
566 if (next == nullptr || compare_(next->Key(), key_decoded) >= 0) {
567 if (level == 0) {
568 return count;
569 } else {
570 // Switch to next list
571 count *= kBranching_;
572 level--;
573 }
574 } else {
575 x = next;
576 count++;
577 }
578 }
579}
580
581template <class Comparator>
582InlineSkipList<Comparator>::InlineSkipList(const Comparator cmp,
583 Allocator* allocator,
584 int32_t max_height,
585 int32_t branching_factor)
586 : kMaxHeight_(static_cast<uint16_t>(max_height)),
587 kBranching_(static_cast<uint16_t>(branching_factor)),
588 kScaledInverseBranching_((Random::kMaxNext + 1) / kBranching_),
589 allocator_(allocator),
590 compare_(cmp),
591 head_(AllocateNode(0, max_height)),
592 max_height_(1),
593 seq_splice_(AllocateSplice()) {
594 assert(max_height > 0 && kMaxHeight_ == static_cast<uint32_t>(max_height))(static_cast<void> (0));
595 assert(branching_factor > 1 &&(static_cast<void> (0))
596 kBranching_ == static_cast<uint32_t>(branching_factor))(static_cast<void> (0));
597 assert(kScaledInverseBranching_ > 0)(static_cast<void> (0));
598
599 for (int i = 0; i < kMaxHeight_; ++i) {
600 head_->SetNext(i, nullptr);
601 }
602}
603
604template <class Comparator>
605char* InlineSkipList<Comparator>::AllocateKey(size_t key_size) {
606 return const_cast<char*>(AllocateNode(key_size, RandomHeight())->Key());
607}
608
609template <class Comparator>
610typename InlineSkipList<Comparator>::Node*
611InlineSkipList<Comparator>::AllocateNode(size_t key_size, int height) {
612 auto prefix = sizeof(std::atomic<Node*>) * (height - 1);
613
614 // prefix is space for the height - 1 pointers that we store before
615 // the Node instance (next_[-(height - 1) .. -1]). Node starts at
616 // raw + prefix, and holds the bottom-mode (level 0) skip list pointer
617 // next_[0]. key_size is the bytes for the key, which comes just after
618 // the Node.
619 char* raw = allocator_->AllocateAligned(prefix + sizeof(Node) + key_size);
620 Node* x = reinterpret_cast<Node*>(raw + prefix);
621
622 // Once we've linked the node into the skip list we don't actually need
623 // to know its height, because we can implicitly use the fact that we
624 // traversed into a node at level h to known that h is a valid level
625 // for that node. We need to convey the height to the Insert step,
626 // however, so that it can perform the proper links. Since we're not
627 // using the pointers at the moment, StashHeight temporarily borrow
628 // storage from next_[0] for that purpose.
629 x->StashHeight(height);
630 return x;
631}
632
633template <class Comparator>
634typename InlineSkipList<Comparator>::Splice*
635InlineSkipList<Comparator>::AllocateSplice() {
636 // size of prev_ and next_
637 size_t array_size = sizeof(Node*) * (kMaxHeight_ + 1);
638 char* raw = allocator_->AllocateAligned(sizeof(Splice) + array_size * 2);
639 Splice* splice = reinterpret_cast<Splice*>(raw);
640 splice->height_ = 0;
641 splice->prev_ = reinterpret_cast<Node**>(raw + sizeof(Splice));
642 splice->next_ = reinterpret_cast<Node**>(raw + sizeof(Splice) + array_size);
643 return splice;
644}
645
646template <class Comparator>
647bool InlineSkipList<Comparator>::Insert(const char* key) {
648 return Insert<false>(key, seq_splice_, false);
649}
650
651template <class Comparator>
652bool InlineSkipList<Comparator>::InsertConcurrently(const char* key) {
653 Node* prev[kMaxPossibleHeight];
654 Node* next[kMaxPossibleHeight];
655 Splice splice;
656 splice.prev_ = prev;
657 splice.next_ = next;
658 return Insert<true>(key, &splice, false);
2
←
Calling 'InlineSkipList::Insert'
→
659}
660
661template <class Comparator>
662bool InlineSkipList<Comparator>::InsertWithHint(const char* key, void** hint) {
663 assert(hint != nullptr)(static_cast<void> (0));
664 Splice* splice = reinterpret_cast<Splice*>(*hint);
665 if (splice == nullptr) {
666 splice = AllocateSplice();
667 *hint = reinterpret_cast<void*>(splice);
668 }
669 return Insert<false>(key, splice, true);
670}
671
672template <class Comparator>
673template <bool prefetch_before>
674void InlineSkipList<Comparator>::FindSpliceForLevel(const DecodedKey& key,
675 Node* before, Node* after,
676 int level, Node** out_prev,
677 Node** out_next) {
678 while (true) {
679 Node* next = before->Next(level);
680 if (next != nullptr) {
681 PREFETCH(next->Next(level), 0, 1)__builtin_prefetch(next->Next(level), 0, 1);
682 }
683 if (prefetch_before == true) {
684 if (next != nullptr && level>0) {
685 PREFETCH(next->Next(level-1), 0, 1)__builtin_prefetch(next->Next(level-1), 0, 1);
686 }
687 }
688 assert(before == head_ || next == nullptr ||(static_cast<void> (0))
689 KeyIsAfterNode(next->Key(), before))(static_cast<void> (0));
690 assert(before == head_ || KeyIsAfterNode(key, before))(static_cast<void> (0));
691 if (next == after || !KeyIsAfterNode(key, next)) {
692 // found it
693 *out_prev = before;
694 *out_next = next;
695 return;
696 }
697 before = next;
698 }
699}
700
701template <class Comparator>
702void InlineSkipList<Comparator>::RecomputeSpliceLevels(const DecodedKey& key,
703 Splice* splice,
704 int recompute_level) {
705 assert(recompute_level > 0)(static_cast<void> (0));
706 assert(recompute_level <= splice->height_)(static_cast<void> (0));
707 for (int i = recompute_level - 1; i >= 0; --i) {
708 FindSpliceForLevel<true>(key, splice->prev_[i + 1], splice->next_[i + 1], i,
709 &splice->prev_[i], &splice->next_[i]);
710 }
711}
712
713template <class Comparator>
714template <bool UseCAS>
715bool InlineSkipList<Comparator>::Insert(const char* key, Splice* splice,
716 bool allow_partial_splice_fix) {
717 Node* x = reinterpret_cast<Node*>(const_cast<char*>(key)) - 1;
718 const DecodedKey key_decoded = compare_.decode_key(key);
719 int height = x->UnstashHeight();
720 assert(height >= 1 && height <= kMaxHeight_)(static_cast<void> (0));
721
722 int max_height = max_height_.load(std::memory_order_relaxed);
723 while (height > max_height) {
3
←
Loop condition is false. Execution continues on line 732
→
724 if (max_height_.compare_exchange_weak(max_height, height)) {
725 // successfully updated it
726 max_height = height;
727 break;
728 }
729 // else retry, possibly exiting the loop because somebody else
730 // increased it
731 }
732 assert(max_height <= kMaxPossibleHeight)(static_cast<void> (0));
733
734 int recompute_height = 0;
735 if (splice->height_ < max_height) {
4
←
Assuming the condition is false
→
5
←
Taking false branch
→
736 // Either splice has never been used or max_height has grown since
737 // last use. We could potentially fix it in the latter case, but
738 // that is tricky.
739 splice->prev_[max_height] = head_;
740 splice->next_[max_height] = nullptr;
741 splice->height_ = max_height;
742 recompute_height = max_height;
743 } else {
744 // Splice is a valid proper-height splice that brackets some
745 // key, but does it bracket this one? We need to validate it and
746 // recompute a portion of the splice (levels 0..recompute_height-1)
747 // that is a superset of all levels that don't bracket the new key.
748 // Several choices are reasonable, because we have to balance the work
749 // saved against the extra comparisons required to validate the Splice.
750 //
751 // One strategy is just to recompute all of orig_splice_height if the
752 // bottom level isn't bracketing. This pessimistically assumes that
753 // we will either get a perfect Splice hit (increasing sequential
754 // inserts) or have no locality.
755 //
756 // Another strategy is to walk up the Splice's levels until we find
757 // a level that brackets the key. This strategy lets the Splice
758 // hint help for other cases: it turns insertion from O(log N) into
759 // O(log D), where D is the number of nodes in between the key that
760 // produced the Splice and the current insert (insertion is aided
761 // whether the new key is before or after the splice). If you have
762 // a way of using a prefix of the key to map directly to the closest
763 // Splice out of O(sqrt(N)) Splices and we make it so that splices
764 // can also be used as hints during read, then we end up with Oshman's
765 // and Shavit's SkipTrie, which has O(log log N) lookup and insertion
766 // (compare to O(log N) for skip list).
767 //
768 // We control the pessimistic strategy with allow_partial_splice_fix.
769 // A good strategy is probably to be pessimistic for seq_splice_,
770 // optimistic if the caller actually went to the work of providing
771 // a Splice.
772 while (recompute_height < max_height) {
6
←
Loop condition is false. Execution continues on line 816
→
773 if (splice->prev_[recompute_height]->Next(recompute_height) !=
774 splice->next_[recompute_height]) {
775 // splice isn't tight at this level, there must have been some inserts
776 // to this
777 // location that didn't update the splice. We might only be a little
778 // stale, but if
779 // the splice is very stale it would be O(N) to fix it. We haven't used
780 // up any of
781 // our budget of comparisons, so always move up even if we are
782 // pessimistic about
783 // our chances of success.
784 ++recompute_height;
785 } else if (splice->prev_[recompute_height] != head_ &&
786 !KeyIsAfterNode(key_decoded,
787 splice->prev_[recompute_height])) {
788 // key is from before splice
789 if (allow_partial_splice_fix) {
790 // skip all levels with the same node without more comparisons
791 Node* bad = splice->prev_[recompute_height];
792 while (splice->prev_[recompute_height] == bad) {
793 ++recompute_height;
794 }
795 } else {
796 // we're pessimistic, recompute everything
797 recompute_height = max_height;
798 }
799 } else if (KeyIsAfterNode(key_decoded,
800 splice->next_[recompute_height])) {
801 // key is from after splice
802 if (allow_partial_splice_fix) {
803 Node* bad = splice->next_[recompute_height];
804 while (splice->next_[recompute_height] == bad) {
805 ++recompute_height;
806 }
807 } else {
808 recompute_height = max_height;
809 }
810 } else {
811 // this level brackets the key, we won!
812 break;
813 }
814 }
815 }
816 assert(recompute_height <= max_height)(static_cast<void> (0));
817 if (recompute_height > 0) {
7
←
Taking false branch
→
818 RecomputeSpliceLevels(key_decoded, splice, recompute_height);
819 }
820
821 bool splice_is_valid = true;
822 if (UseCAS) {
8
←
Taking true branch
→
823 for (int i = 0; i < height; ++i) {
9
←
Assuming 'i' is < 'height'
→
10
←
Loop condition is true. Entering loop body
→
824 while (true) {
11
←
Loop condition is true. Entering loop body
→
825 // Checking for duplicate keys on the level 0 is sufficient
826 if (UNLIKELY(i == 0 && splice->next_[i] != nullptr &&(__builtin_expect((i == 0 && splice->next_[i] != nullptr
&& compare_(x->Key(), splice->next_[i]->Key
()) >= 0), 0))
12
←
Within the expansion of the macro 'UNLIKELY':
a
The left operand of '!=' is a garbage value
827 compare_(x->Key(), splice->next_[i]->Key()) >= 0)(__builtin_expect((i == 0 && splice->next_[i] != nullptr
&& compare_(x->Key(), splice->next_[i]->Key
()) >= 0), 0))) {
828 // duplicate key
829 return false;
830 }
831 if (UNLIKELY(i == 0 && splice->prev_[i] != head_ &&(__builtin_expect((i == 0 && splice->prev_[i] != head_
&& compare_(splice->prev_[i]->Key(), x->Key
()) >= 0), 0))
832 compare_(splice->prev_[i]->Key(), x->Key()) >= 0)(__builtin_expect((i == 0 && splice->prev_[i] != head_
&& compare_(splice->prev_[i]->Key(), x->Key
()) >= 0), 0))) {
833 // duplicate key
834 return false;
835 }
836 assert(splice->next_[i] == nullptr ||(static_cast<void> (0))
837 compare_(x->Key(), splice->next_[i]->Key()) < 0)(static_cast<void> (0));
838 assert(splice->prev_[i] == head_ ||(static_cast<void> (0))
839 compare_(splice->prev_[i]->Key(), x->Key()) < 0)(static_cast<void> (0));
840 x->NoBarrier_SetNext(i, splice->next_[i]);
841 if (splice->prev_[i]->CASNext(i, splice->next_[i], x)) {
842 // success
843 break;
844 }
845 // CAS failed, we need to recompute prev and next. It is unlikely
846 // to be helpful to try to use a different level as we redo the
847 // search, because it should be unlikely that lots of nodes have
848 // been inserted between prev[i] and next[i]. No point in using
849 // next[i] as the after hint, because we know it is stale.
850 FindSpliceForLevel<false>(key_decoded, splice->prev_[i], nullptr, i,
851 &splice->prev_[i], &splice->next_[i]);
852
853 // Since we've narrowed the bracket for level i, we might have
854 // violated the Splice constraint between i and i-1. Make sure
855 // we recompute the whole thing next time.
856 if (i > 0) {
857 splice_is_valid = false;
858 }
859 }
860 }
861 } else {
862 for (int i = 0; i < height; ++i) {
863 if (i >= recompute_height &&
864 splice->prev_[i]->Next(i) != splice->next_[i]) {
865 FindSpliceForLevel<false>(key_decoded, splice->prev_[i], nullptr, i,
866 &splice->prev_[i], &splice->next_[i]);
867 }
868 // Checking for duplicate keys on the level 0 is sufficient
869 if (UNLIKELY(i == 0 && splice->next_[i] != nullptr &&(__builtin_expect((i == 0 && splice->next_[i] != nullptr
&& compare_(x->Key(), splice->next_[i]->Key
()) >= 0), 0))
870 compare_(x->Key(), splice->next_[i]->Key()) >= 0)(__builtin_expect((i == 0 && splice->next_[i] != nullptr
&& compare_(x->Key(), splice->next_[i]->Key
()) >= 0), 0))) {
871 // duplicate key
872 return false;
873 }
874 if (UNLIKELY(i == 0 && splice->prev_[i] != head_ &&(__builtin_expect((i == 0 && splice->prev_[i] != head_
&& compare_(splice->prev_[i]->Key(), x->Key
()) >= 0), 0))
875 compare_(splice->prev_[i]->Key(), x->Key()) >= 0)(__builtin_expect((i == 0 && splice->prev_[i] != head_
&& compare_(splice->prev_[i]->Key(), x->Key
()) >= 0), 0))) {
876 // duplicate key
877 return false;
878 }
879 assert(splice->next_[i] == nullptr ||(static_cast<void> (0))
880 compare_(x->Key(), splice->next_[i]->Key()) < 0)(static_cast<void> (0));
881 assert(splice->prev_[i] == head_ ||(static_cast<void> (0))
882 compare_(splice->prev_[i]->Key(), x->Key()) < 0)(static_cast<void> (0));
883 assert(splice->prev_[i]->Next(i) == splice->next_[i])(static_cast<void> (0));
884 x->NoBarrier_SetNext(i, splice->next_[i]);
885 splice->prev_[i]->SetNext(i, x);
886 }
887 }
888 if (splice_is_valid) {
889 for (int i = 0; i < height; ++i) {
890 splice->prev_[i] = x;
891 }
892 assert(splice->prev_[splice->height_] == head_)(static_cast<void> (0));
893 assert(splice->next_[splice->height_] == nullptr)(static_cast<void> (0));
894 for (int i = 0; i < splice->height_; ++i) {
895 assert(splice->next_[i] == nullptr ||(static_cast<void> (0))
896 compare_(key, splice->next_[i]->Key()) < 0)(static_cast<void> (0));
897 assert(splice->prev_[i] == head_ ||(static_cast<void> (0))
898 compare_(splice->prev_[i]->Key(), key) <= 0)(static_cast<void> (0));
899 assert(splice->prev_[i + 1] == splice->prev_[i] ||(static_cast<void> (0))
900 splice->prev_[i + 1] == head_ ||(static_cast<void> (0))
901 compare_(splice->prev_[i + 1]->Key(), splice->prev_[i]->Key()) <(static_cast<void> (0))
902 0)(static_cast<void> (0));
903 assert(splice->next_[i + 1] == splice->next_[i] ||(static_cast<void> (0))
904 splice->next_[i + 1] == nullptr ||(static_cast<void> (0))
905 compare_(splice->next_[i]->Key(), splice->next_[i + 1]->Key()) <(static_cast<void> (0))
906 0)(static_cast<void> (0));
907 }
908 } else {
909 splice->height_ = 0;
910 }
911 return true;
912}
913
914template <class Comparator>
915bool InlineSkipList<Comparator>::Contains(const char* key) const {
916 Node* x = FindGreaterOrEqual(key);
917 if (x != nullptr && Equal(key, x->Key())) {
918 return true;
919 } else {
920 return false;
921 }
922}
923
924template <class Comparator>
925void InlineSkipList<Comparator>::TEST_Validate() const {
926 // Interate over all levels at the same time, and verify nodes appear in
927 // the right order, and nodes appear in upper level also appear in lower
928 // levels.
929 Node* nodes[kMaxPossibleHeight];
930 int max_height = GetMaxHeight();
931 assert(max_height > 0)(static_cast<void> (0));
932 for (int i = 0; i < max_height; i++) {
933 nodes[i] = head_;
934 }
935 while (nodes[0] != nullptr) {
936 Node* l0_next = nodes[0]->Next(0);
937 if (l0_next == nullptr) {
938 break;
939 }
940 assert(nodes[0] == head_ || compare_(nodes[0]->Key(), l0_next->Key()) < 0)(static_cast<void> (0));
941 nodes[0] = l0_next;
942
943 int i = 1;
944 while (i < max_height) {
945 Node* next = nodes[i]->Next(i);
946 if (next == nullptr) {
947 break;
948 }
949 auto cmp = compare_(nodes[0]->Key(), next->Key());
950 assert(cmp <= 0)(static_cast<void> (0));
951 if (cmp == 0) {
952 assert(next == nodes[0])(static_cast<void> (0));
953 nodes[i] = next;
954 } else {
955 break;
956 }
957 i++;
958 }
959 }
960 for (int i = 1; i < max_height; i++) {
961 assert(nodes[i] != nullptr && nodes[i]->Next(i) == nullptr)(static_cast<void> (0));
962 }
963}
964
965} // namespace rocksdb