From 6c725d6393bb17f74cb581052faf8dfe9209cf83 Mon Sep 17 00:00:00 2001 From: Tor Egge Date: Fri, 25 Feb 2022 15:36:45 +0100 Subject: Add member functions to get and set btree internal node child refs that will use relaxed memory order instead of acquire and release. --- vespalib/src/vespa/vespalib/btree/btreebuilder.hpp | 24 +++++++++++----------- .../src/vespa/vespalib/btree/btreeinserter.hpp | 8 ++++---- .../src/vespa/vespalib/btree/btreeiterator.hpp | 4 ++-- vespalib/src/vespa/vespalib/btree/btreenode.h | 4 +++- vespalib/src/vespa/vespalib/btree/btreeremover.hpp | 6 +++--- 5 files changed, 24 insertions(+), 22 deletions(-) (limited to 'vespalib') diff --git a/vespalib/src/vespa/vespalib/btree/btreebuilder.hpp b/vespalib/src/vespa/vespalib/btree/btreebuilder.hpp index 5abe2b2cebd..3162dfb4820 100644 --- a/vespalib/src/vespa/vespalib/btree/btreebuilder.hpp +++ b/vespalib/src/vespa/vespalib/btree/btreebuilder.hpp @@ -106,10 +106,10 @@ normalize() /* Adjust validLeaves for rightmost nodes */ for (level = 0; level < _inodes.size(); level++) { InternalNodeType *inode = _inodes[level].data; - NodeRef lcRef(inode->getLastChild()); + NodeRef lcRef(inode->get_last_child_relaxed()); assert(NodeAllocatorType::isValidRef(lcRef)); assert((level == 0) == _allocator.isLeafRef(lcRef)); - inode->incValidLeaves(_allocator.validLeaves(inode->getLastChild())); + inode->incValidLeaves(_allocator.validLeaves(inode->get_last_child_relaxed())); inode->update(inode->validSlots() - 1, level == 0 ? _allocator.mapLeafRef(lcRef)->getLastKey() : @@ -134,10 +134,10 @@ normalize() inode = _allocator.mapInternalRef(iRef); assert(inode != nullptr); assert(inode->validSlots() >= 1); - child = inode->getLastChild(); + child = inode->get_last_child_relaxed(); } else { /* Use next to last child of rightmost node on level */ - child = inode->getChild(inode->validSlots() - 2); + child = inode->get_child_relaxed(inode->validSlots() - 2); } if (level == 0) break; @@ -190,11 +190,11 @@ normalize() } if (pnode->validSlots() > 0) { uint32_t s = pnode->validSlots() - 1; - LeafNodeType *l = _allocator.mapLeafRef(pnode->getChild(s)); + LeafNodeType *l = _allocator.mapLeafRef(pnode->get_child_relaxed(s)); pnode->writeKey(s, l->getLastKey()); if (s > 0) { --s; - l = _allocator.mapLeafRef(pnode->getChild(s)); + l = _allocator.mapLeafRef(pnode->get_child_relaxed(s)); pnode->writeKey(s, l->getLastKey()); } } @@ -202,7 +202,7 @@ normalize() InternalNodeType *lpnode = _allocator.mapInternalRef(leftInodes[0]); uint32_t s = lpnode->validSlots() - 1; - LeafNodeType *l = _allocator.mapLeafRef(lpnode->getChild(s)); + LeafNodeType *l = _allocator.mapLeafRef(lpnode->get_child_relaxed(s)); lpnode->writeKey(s, l->getLastKey()); } } @@ -256,11 +256,11 @@ normalize() if (pnode->validSlots() > 0) { uint32_t s = pnode->validSlots() - 1; InternalNodeType *n = - _allocator.mapInternalRef(pnode->getChild(s)); + _allocator.mapInternalRef(pnode->get_child_relaxed(s)); pnode->writeKey(s, n->getLastKey()); if (s > 0) { --s; - n = _allocator.mapInternalRef(pnode->getChild(s)); + n = _allocator.mapInternalRef(pnode->get_child_relaxed(s)); pnode->writeKey(s, n->getLastKey()); } } @@ -270,7 +270,7 @@ normalize() _allocator.mapInternalRef(leftInodes[level + 1]); uint32_t s = lpnode->validSlots() - 1; InternalNodeType *n = - _allocator.mapInternalRef(lpnode->getChild(s)); + _allocator.mapInternalRef(lpnode->get_child_relaxed(s)); lpnode->writeKey(s, n->getLastKey()); } } @@ -333,7 +333,7 @@ allocNewLeafNode() } inode = _inodes[level].data; assert(inode->validSlots() > 0); - NodeRef lcRef(inode->getLastChild()); + NodeRef lcRef(inode->get_last_child_relaxed()); inode->incValidLeaves(_allocator.validLeaves(lcRef)); inode->update(inode->validSlots() - 1, level == 0 ? @@ -358,7 +358,7 @@ allocNewLeafNode() } while (level > 0) { assert(inode->validSlots() > 0); - child = inode->getLastChild(); + child = inode->get_last_child_relaxed(); assert(!_allocator.isLeafRef(child)); inode = _allocator.mapInternalRef(child); level--; diff --git a/vespalib/src/vespa/vespalib/btree/btreeinserter.hpp b/vespalib/src/vespa/vespalib/btree/btreeinserter.hpp index b5980e53f93..de6454f8bae 100644 --- a/vespalib/src/vespa/vespalib/btree/btreeinserter.hpp +++ b/vespalib/src/vespa/vespalib/btree/btreeinserter.hpp @@ -34,17 +34,17 @@ BTreeInserter::rebalanceLeafEn auto &pathElem = itr.getPath(0); InternalNodeType *parentNode = pathElem.getWNode(); uint32_t parentIdx = pathElem.getIdx(); - BTreeNode::Ref leafRef = parentNode->getChild(parentIdx); + BTreeNode::Ref leafRef = parentNode->get_child_relaxed(parentIdx); BTreeNode::Ref leftRef = BTreeNode::Ref(); LeafNodeType *leftNode = nullptr; BTreeNode::Ref rightRef = BTreeNode::Ref(); LeafNodeType *rightNode = nullptr; if (parentIdx > 0) { - leftRef = parentNode->getChild(parentIdx - 1); + leftRef = parentNode->get_child_relaxed(parentIdx - 1); leftNode = allocator.mapLeafRef(leftRef); } if (parentIdx + 1 < parentNode->validSlots()) { - rightRef = parentNode->getChild(parentIdx + 1); + rightRef = parentNode->get_child_relaxed(parentIdx + 1); rightNode = allocator.mapLeafRef(rightRef); } if (leftNode != nullptr && leftNode->validSlots() < LeafNodeType::maxSlots() && @@ -138,7 +138,7 @@ insert(BTreeNode::Ref &root, idx = pe.getIdx(); AggrT olda(AggrCalcT::hasAggregated() ? node->getAggregated() : AggrT()); - BTreeNode::Ref subNode = node->getChild(idx); + BTreeNode::Ref subNode = node->get_child_relaxed(idx); node->update(idx, *lastKey, subNode); node->incValidLeaves(1); if (NodeAllocatorType::isValidRef(splitNodeRef)) { diff --git a/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp b/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp index 042779f1b1b..8ecd26835c4 100644 --- a/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp +++ b/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp @@ -1163,13 +1163,13 @@ thaw(BTreeNode::Ref rootRef) rootRef; assert(node == allocator.mapInternalRef(nodeRef)); if (!node->getFrozen()) { - node->setChild(pe.getIdx(), childRef); + node->set_child_relaxed(pe.getIdx(), childRef); return rootRef; } InternalNodeTypeRefPair thawed = allocator.thawNode(nodeRef, node); node = thawed.data; pe.setNode(node); - node->setChild(pe.getIdx(), childRef); + node->set_child_relaxed(pe.getIdx(), childRef); childRef = thawed.ref; ++level; } diff --git a/vespalib/src/vespa/vespalib/btree/btreenode.h b/vespalib/src/vespa/vespalib/btree/btreenode.h index 468f17fcd1a..deeaad40ae6 100644 --- a/vespalib/src/vespa/vespalib/btree/btreenode.h +++ b/vespalib/src/vespa/vespalib/btree/btreenode.h @@ -336,8 +336,10 @@ private: public: BTreeNode::Ref getChild(uint32_t idx) const { return getData(idx); } + BTreeNode::Ref get_child_relaxed(uint32_t idx) const { return getData(idx); } void setChild(uint32_t idx, BTreeNode::Ref child) { setData(idx, child); } - BTreeNode::Ref getLastChild() const { return getChild(validSlots() - 1); } + void set_child_relaxed(uint32_t idx, BTreeNode::Ref child) { setData(idx, child); } + BTreeNode::Ref get_last_child_relaxed() const { return get_child_relaxed(validSlots() - 1); } uint32_t validLeaves() const { return _validLeaves; } void setValidLeaves(uint32_t newValidLeaves) { _validLeaves = newValidLeaves; } void incValidLeaves(uint32_t delta) { _validLeaves += delta; } diff --git a/vespalib/src/vespa/vespalib/btree/btreeremover.hpp b/vespalib/src/vespa/vespalib/btree/btreeremover.hpp index e0e41c1dd2d..24155abcff9 100644 --- a/vespalib/src/vespa/vespalib/btree/btreeremover.hpp +++ b/vespalib/src/vespa/vespalib/btree/btreeremover.hpp @@ -25,11 +25,11 @@ steal(InternalNodeType *pNode, BTreeNode::Ref rightVictimRef = BTreeNode::Ref(); NodeType * rightVictim = nullptr; if (idx > 0) { - leftVictimRef = pNode->getChild(idx - 1); + leftVictimRef = pNode->get_child_relaxed(idx - 1); leftVictim = allocator.template mapRef(leftVictimRef); } if (idx + 1 < pNode->validSlots()) { - rightVictimRef = pNode->getChild(idx + 1); + rightVictimRef = pNode->get_child_relaxed(idx + 1); rightVictim = allocator.template mapRef(rightVictimRef); } if (leftVictim != nullptr && @@ -141,7 +141,7 @@ remove(BTreeNode::Ref &root, idx = pe.getIdx(); AggrT olda(AggrCalcT::hasAggregated() ? node->getAggregated() : AggrT()); - BTreeNode::Ref subNode = node->getChild(idx); + BTreeNode::Ref subNode = node->get_child_relaxed(idx); node->update(idx, allocator.getLastKey(subNode), subNode); node->decValidLeaves(1); if (level == 0) { -- cgit v1.2.3