Opened 7 years ago

Closed 7 years ago

#2092 closed task (fixed)

RBNode parent pointer updates

Reported by: jinmei Owned by: muks
Priority: medium Milestone: Sprint-20120731
Component: data source Version:
Keywords: Cc:
CVSS Scoring: Parent Tickets:
Sensitive: no Defect Severity: N/A
Sub-Project: DNS Feature Depending on Ticket: scalable inmemory
Estimated Difficulty: 4 Add Hours to Ticket: 0
Total Hours: 2.06 Internal?: no

Description (last modified by jinmei)

  • Make sure the parent of a root node (of some subtree) points to the upper level node (it's currently NULL; the root node should be distinguishable by the newly introduced "ROOT" flag - See #2089, so this ticket depends on it).
  • Introduce a new method "getUpLevelNode" (or rename it as appropriate). It takes a node and returns the parent of the root of its subtree (i.e, it returns the node's immediate ancestor in the tree-of-tree hierarchy). If the node is at the top level (which should be absolute), it will return the null node. Use getParent() introduced in #2090 (so it's better to do this task after #2090)
  • at this point, we should probably consider replacing the sentinel NULL node with a NULL pointer. In my experiment I found it could be quite confusing if we have both the concept of "root" and "NULL node"

Subtickets

Change History (19)

comment:1 Changed 7 years ago by jinmei

  • Description modified (diff)

comment:2 Changed 7 years ago by jinmei

  • Description modified (diff)

comment:3 Changed 7 years ago by shane

  • Estimated Difficulty changed from 0 to 4

comment:4 Changed 7 years ago by jinmei

  • Milestone set to Next-Sprint-Proposed

comment:5 Changed 7 years ago by jelte

  • Milestone changed from Next-Sprint-Proposed to Sprint-20120731

comment:6 Changed 7 years ago by muks

  • Owner set to muks
  • Status changed from new to assigned

Picking.

comment:7 follow-up: Changed 7 years ago by muks

This work is ready for review in the trac2092 branch, but unittests still need to be added for the bugs in #2089.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 7 years ago by jinmei

Replying to muks:

This work is ready for review in the trac2092 branch, but unittests still need to be added for the bugs in #2089.

Is there any reason you've not changed the ticket to "reviewing" (or
releasing the ownership)? Is the intent to complete the
above-mentioned tests and then move it to the review queue?

comment:9 in reply to: ↑ 8 Changed 7 years ago by muks

Replying to jinmei:

Is there any reason you've not changed the ticket to "reviewing" (or
releasing the ownership)? Is the intent to complete the
above-mentioned tests and then move it to the review queue?

You are spot on. It was not put to review because a test had to be added for the issue found in #2089 (so it doesn't happen again). The issue is already fixed and is in the trac2092 branch. The branch was pushed on Friday morning before our daily status meeting. The bug was not put to review because of the missing test.

comment:10 Changed 7 years ago by muks

  • Owner changed from muks to UnAssigned
  • Status changed from assigned to reviewing

The branch is up for review now.

comment:11 Changed 7 years ago by vorner

  • Owner changed from UnAssigned to vorner

comment:12 Changed 7 years ago by vorner

  • Owner changed from vorner to muks

Hello

The code looks mostly OK. Just:

  • The test (getUpperNode), when it expects NULL, it should check it actually got one. It seems to me there's no checking if the expected is NULL.
  • While merging, a care should be taken, as the internal data are now using offset_ptr instead of bare pointers. Some of your new code will need to be adjusted.
  • As noted in #2090, it expected this ticket will stop using the sentinel nodes and replace them by real NULLs. As it doesn't seem to have happened, either of these need to be done:
    • Replace the sentinels with NULLs
    • Replace the NULL node in the tree with an offset_ptr, so it can be shared too.

Thank you

comment:13 follow-up: Changed 7 years ago by jinmei

If not discussed in the review and not done in the branch, please
update the following comment. This branch will deprecate the
statement:

/// to a subtree of subdomains. Note that we can traverse the hierarchy down,
/// but not up.

comment:14 in reply to: ↑ 13 Changed 7 years ago by muks

  • Owner changed from muks to vorner

Hi vorner

Replying to vorner:

Hello

The code looks mostly OK. Just:

  • The test (getUpperNode), when it expects NULL, it should check it actually got one. It seems to me there's no checking if the expected is NULL.

Nice catch. :) Fixed.

  • While merging, a care should be taken, as the internal data are now using offset_ptr instead of bare pointers. Some of your new code will need to be adjusted.

A rebased tree is on trac2092_2 branch.

  • As noted in #2090, it expected this ticket will stop using the sentinel nodes and replace them by real NULLs. As it doesn't seem to have happened, either of these need to be done:
    • Replace the sentinels with NULLs
    • Replace the NULL node in the tree with an offset_ptr, so it can be shared too.

I preferred keeping NULL_NODE as the red-black property is more apparent and existing code depended on the properties of NULL_NODE (de-referenceable and pointing to itself). But workarounds for the originally static NULL_NODE becoming a shareable object in shared memory would have led to hackish code.

So sentinels are replaced with NULLs now.

Hi Jinmei

Replying to jinmei:

If not discussed in the review and not done in the branch, please
update the following comment. This branch will deprecate the
statement:

/// to a subtree of subdomains. Note that we can traverse the hierarchy down,
/// but not up.

This has been fixed now.

comment:15 follow-up: Changed 7 years ago by jinmei

I guess this comment was intended for this ticket, not #2091:
http://bind10.isc.org/ticket/2091#comment:14

So I'm copying it here and changing the ticket owner.

Hello

The code looks mostly OK, but:

  • The rebasing is not good for reviewing. Since rebasing could have changed (or you, because of the conflicts) the old commits, I needed to review the whole thing once again.
  • Inspired by what Jinmei mentioned yesterday in Jabber, this (and similar ones) looks unsafe:
    if (parent == parent->getParent()->getLeft())
    
    The code checks only that the node is not root, so the parent can be. And it could be the root of the top-most tree, in which case the parent would be NULL. So parent->getParent() would return NULL and the getLeft would segfault. I think this is one of the places where the code assumed the link-to-self property of the sentinel.

comment:16 Changed 7 years ago by jinmei

  • Owner changed from vorner to muks

comment:17 in reply to: ↑ 15 ; follow-up: Changed 7 years ago by muks

  • Owner changed from muks to vorner

Hi vorner

Replying to jinmei:

The code looks mostly OK, but:

  • The rebasing is not good for reviewing. Since rebasing could have changed (or you, because of the conflicts) the old commits, I needed to review the whole thing once again.

I am very sorry. I'll do merges from now on. In this particular case, the commits are still identical to the last ones (if that is any consolation).

  • Inspired by what Jinmei mentioned yesterday in Jabber, this (and similar ones) looks unsafe:
    if (parent == parent->getParent()->getLeft())
    
    The code checks only that the node is not root, so the parent can be. And it could be the root of the top-most tree, in which case the parent would be NULL. So parent->getParent() would return NULL and the getLeft would segfault. I think this is one of the places where the code assumed the link-to-self property of the sentinel.

In our trees, root is always black. So the dereference will always work.

comment:18 in reply to: ↑ 17 Changed 7 years ago by vorner

  • Owner changed from vorner to muks
  • Total Hours changed from 0 to 2.06

Hello

Replying to muks:

Replying to jinmei:

The code looks mostly OK, but:

  • The rebasing is not good for reviewing. Since rebasing could have changed (or you, because of the conflicts) the old commits, I needed to review the whole thing once again.

I am very sorry. I'll do merges from now on. In this particular case, the commits are still identical to the last ones (if that is any consolation).

That's OK. I just wanted to point it out. If you said before the review the commits are the same, it would help also.

  • Inspired by what Jinmei mentioned yesterday in Jabber, this (and similar ones) looks unsafe:
    if (parent == parent->getParent()->getLeft())
    
    The code checks only that the node is not root, so the parent can be. And it could be the root of the top-most tree, in which case the parent would be NULL. So parent->getParent() would return NULL and the getLeft would segfault. I think this is one of the places where the code assumed the link-to-self property of the sentinel.

In our trees, root is always black. So the dereference will always work.

Could you put a comment above the condition, explaining why it is safe?

After that, please merge.

comment:19 Changed 7 years ago by muks

  • Resolution set to fixed
  • Status changed from reviewing to closed

Merged to master in commit 0ae269325e8667b8f91555b655d001b3a5b217ae:

* ae25a3b (origin/trac2092_2) [2092] Add comment about pointer dereference asked by reviewer
* 8cbfc95 [2092] Remove some initializers
* 07d6576 [2092] Stop using NULLNODE inside RBNode and RBTree
* 45642a1 [2092] Test the case when the upper node is indeed the null node
* 22fdee1 [2092] Update doc comment
* 3eafbef [2092] Add support for showing pointers in Graphviz output
* 5d3e852 Add RBNode::getUpperNode()
* b93f098 [2092] Set/update the parent_ pointer to the upper tree's leaf
* d5e953d [2092] Use isSubTreeRoot() instead of comparing with NULLNODE
* 3bdd3af [2092] Restore subtree root flag after node fission
* 7c1d637 [2092] Remove unnecessary code
* 0f380c4 [2092] Add a testcase for checking if FLAG_SUBTREE_ROOT is being set properly
* ba30151 [2092] Dump RBTree to Graphviz dot output

which also fixes some API and data differences between master and trac2092_2 branches which caused several compile and test failures.

Resolving as fixed.

Note: See TracTickets for help on using tickets.