Repository: dragonflyoss/Dragonfly2
Pull request #1469 (2022-07-18 11:52:47)

fix: infinite loop in peer.Ancestors()
Signed-off-by: Gaius <gaius.qi@gmail.com>

<!--- Provide a general summary of your changes in the Title above -->

## Description
Fix infinite loop in `peer.Ancestors()`.
<!--- Describe your changes in detail -->

## Related Issue

<!--- This project only accepts pull requests related to open issues -->
<!--- If suggesting a new feature or change, please discuss it in an issue first -->
<!--- If fixing a bug, there should be an issue describing it with steps to reproduce -->
<!--- Please link to the issue here: -->

## Motivation and Context

<!--- Why is this change required? What problem does it solve? -->

## Screenshots (if appropriate)

## Types of changes

<!--- What types of changes does your code introduce? Put an `x` in all the boxes that apply: -->

- [ ] Bug fix (non-breaking change which fixes an issue)
- [x] New feature (non-breaking change which adds functionality)
- [ ] Breaking change (fix or feature that would cause existing functionality to change)
- [ ] Documentation Update (if none of the other choices apply)

## Checklist

<!--- Go over all the following points, and put an `x` in all the boxes that apply. -->
<!--- If you're unsure about any of these, don't hesitate to ask. We're here to help! -->

- [ ] My change requires a change to the documentation.
- [ ] I have updated the documentation accordingly.
- [x] I have read the **CONTRIBUTING** document.
- [ ] I have added tests to cover my changes.


codecov-commenter: # [Codecov](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1469?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) Report
> Merging [#1469](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1469?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) (74a6ef9) into [main](https://codecov.io/gh/dragonflyoss/Dragonfly2/commit/e90ac74debf8ba1d6f52968aed2dc1d85b39f68d?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) (e90ac74) will **increase** coverage by `0.06%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1469/graphs/tree.svg?width=650&height=150&src=pr&token=PUICJYSAT7&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss)](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1469?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss)

```diff
@@            Coverage Diff             @@
##             main    #1469      +/-   ##
==========================================
+ Coverage   43.74%   43.81%   +0.06%     
==========================================
  Files         118      120       +2     
  Lines       10735    10821      +86     
==========================================
+ Hits         4696     4741      +45     
- Misses       5571     5597      +26     
- Partials      468      483      +15     
```

| Flag | Coverage Δ | |
|---|---|---|
| Object-compatibility-e2etests | `?` | |
| e2etests | `?` | |
| unittests | `43.81% <100.00%> (+0.06%)` | :arrow_up: |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#carryforward-flags-in-the-pull-request-comment) to find out more.

| [Impacted Files](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1469?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) | Coverage Δ | |
|---|---|---|
| [scheduler/resource/peer.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1469/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-c2NoZWR1bGVyL3Jlc291cmNlL3BlZXIuZ28=) | `77.55% <100.00%> (ø)` | |
| [client/daemon/rpcserver/subscriber.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1469/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-Y2xpZW50L2RhZW1vbi9ycGNzZXJ2ZXIvc3Vic2NyaWJlci5nbw==) | `47.76% <0.00%> (-2.24%)` | :arrow_down: |
| [...ent/daemon/peer/peertask\_piecetask\_synchronizer.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1469/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-Y2xpZW50L2RhZW1vbi9wZWVyL3BlZXJ0YXNrX3BpZWNldGFza19zeW5jaHJvbml6ZXIuZ28=) | `45.45% <0.00%> (-2.17%)` | :arrow_down: |
| [client/daemon/peer/peertask\_conductor.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1469/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-Y2xpZW50L2RhZW1vbi9wZWVyL3BlZXJ0YXNrX2NvbmR1Y3Rvci5nbw==) | `57.11% <0.00%> (-0.70%)` | :arrow_down: |
| [pkg/dag/dag.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1469/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-cGtnL2RhZy9kYWcuZ28=) | `66.66% <0.00%> (ø)` | |
| [pkg/dag/vertex.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1469/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-cGtnL2RhZy92ZXJ0ZXguZ28=) | `100.00% <0.00%> (ø)` | |


Patch:
diff --git a/pkg/slices/slices.go b/pkg/slices/slices.go
index f744da7e..47488c59 100644
--- a/pkg/slices/slices.go
+++ b/pkg/slices/slices.go
@@ -26,3 +26,18 @@ func Contains[T comparable](s []T, e T) bool {
 
 	return false
 }
+
+// FindDuplicate returns duplicate element in a collection.
+func FindDuplicate[T comparable](s []T) (T, bool) {
+	visited := make(map[T]struct{})
+	for _, v := range s {
+		if _, ok := visited[v]; ok {
+			return v, true
+		}
+
+		visited[v] = struct{}{}
+	}
+
+	var zero T
+	return zero, false
+}
diff --git a/scheduler/resource/peer.go b/scheduler/resource/peer.go
index dfa04716..32ec3887 100644
--- a/scheduler/resource/peer.go
+++ b/scheduler/resource/peer.go
@@ -33,6 +33,7 @@ import (
 	logger "d7y.io/dragonfly/v2/internal/dflog"
 	"d7y.io/dragonfly/v2/pkg/container/set"
 	"d7y.io/dragonfly/v2/pkg/rpc/scheduler"
+	"d7y.io/dragonfly/v2/pkg/slices"
 )
 
 const (
@@ -373,11 +374,11 @@ func (p *Peer) Depth() int {
 	p.mu.RLock()
 	defer p.mu.RUnlock()
 
-	node := p
-	var depth int
+	var (
+		node      = p
+		ancestors = []string{p.ID}
+	)
 	for node != nil {
-		depth++
-
 		if node.Host.Type != HostTypeNormal {
 			break
 		}
@@ -387,8 +388,10 @@ func (p *Peer) Depth() int {
 			break
 		}
 
+		ancestors = append(ancestors, parent.ID)
+
 		// Prevent traversal tree from infinite loop.
-		if p.ID == parent.ID {
+		if _, found := slices.FindDuplicate(ancestors); found {
 			p.Log.Error("tree structure produces an infinite loop")
 			break
 		}
@@ -396,7 +399,7 @@ func (p *Peer) Depth() int {
 		node = parent
 	}
 
-	return depth
+	return len(ancestors)
 }
 
 // Ancestors returns peer's ancestors.
@@ -404,22 +407,25 @@ func (p *Peer) Ancestors() []string {
 	p.mu.RLock()
 	defer p.mu.RUnlock()
 
-	var ancestors []string
-	node := p
+	var (
+		node      = p
+		ancestors = []string{p.ID}
+	)
 	for node != nil {
 		parent, ok := node.LoadParent()
 		if !ok {
 			return ancestors
 		}
 
+		ancestors = append(ancestors, parent.ID)
+
 		// Prevent traversal tree from infinite loop.
-		if parent.ID == node.ID {
+		if _, found := slices.FindDuplicate(ancestors); found {
 			p.Log.Error("tree structure produces an infinite loop")
-			return ancestors
+			break
 		}
 
 		node = parent
-		ancestors = append(ancestors, node.ID)
 	}
 
 	return ancestors
@@ -427,34 +433,39 @@ func (p *Peer) Ancestors() []string {
 
 // IsDescendant determines whether it is ancestor of peer.
 func (p *Peer) IsDescendant(ancestor *Peer) bool {
-	return p.isDescendant(ancestor, p)
+	return ancestor.isDescendant(p)
 }
 
 // IsAncestor determines whether it is descendant of peer.
 func (p *Peer) IsAncestor(descendant *Peer) bool {
-	return p.isDescendant(p, descendant)
+	return p.isDescendant(descendant)
 }
 
 // isDescendant determines whether it is ancestor of peer.
-func (p *Peer) isDescendant(ancestor, descendant *Peer) bool {
+func (p *Peer) isDescendant(descendant *Peer) bool {
 	p.mu.RLock()
 	defer p.mu.RUnlock()
 
-	node := descendant
+	var (
+		node      = descendant
+		ancestors = []string{descendant.ID}
+	)
 	for node != nil {
 		parent, ok := node.LoadParent()
 		if !ok {
 			return false
 		}
 
-		if parent.ID == ancestor.ID {
+		if parent.ID == p.ID {
 			return true
 		}
 
+		ancestors = append(ancestors, parent.ID)
+
 		// Prevent traversal tree from infinite loop.
-		if parent.ID == descendant.ID {
+		if _, found := slices.FindDuplicate(ancestors); found {
 			p.Log.Error("tree structure produces an infinite loop")
-			return true
+			break
 		}
 
 		node = parent


Test patch:
diff --git a/pkg/slices/slices_test.go b/pkg/slices/slices_test.go
index 9aefd352..7a0751a0 100644
--- a/pkg/slices/slices_test.go
+++ b/pkg/slices/slices_test.go
@@ -29,3 +29,25 @@ func TestContains(t *testing.T) {
 	assert.True(Contains([]string{"a", "b", "c"}, "a"))
 	assert.False(Contains([]string{"a", "b", "c"}, "d"))
 }
+
+func TestFindDuplicate(t *testing.T) {
+	assert := assert.New(t)
+	var (
+		dupi  int
+		dups  string
+		found bool
+	)
+	dupi, found = FindDuplicate([]int{1, 2, 1, 3})
+	assert.True(found)
+	assert.Equal(dupi, 1)
+
+	_, found = FindDuplicate([]int{1, 2, 3})
+	assert.False(found)
+
+	dups, found = FindDuplicate([]string{"a", "b", "c", "b"})
+	assert.True(found)
+	assert.Equal(dups, "b")
+
+	_, found = FindDuplicate([]string{"a", "b", "c"})
+	assert.False(found)
+}
diff --git a/scheduler/resource/peer_test.go b/scheduler/resource/peer_test.go
index 964eb145..9d8e2b0e 100644
--- a/scheduler/resource/peer_test.go
+++ b/scheduler/resource/peer_test.go
@@ -526,7 +526,7 @@ func TestPeer_Depth(t *testing.T) {
 				peer.StoreParent(peer)
 
 				assert := assert.New(t)
-				assert.Equal(peer.Depth(), 1)
+				assert.Equal(peer.Depth(), 2)
 			},
 		},
 	}
@@ -557,8 +557,8 @@ func TestPeer_Ancestors(t *testing.T) {
 			expect: func(t *testing.T, peer *Peer, mockChildPeer *Peer) {
 				assert := assert.New(t)
 				peer.StoreChild(mockChildPeer)
-				assert.Equal(len(mockChildPeer.Ancestors()), 1)
-				assert.EqualValues(mockChildPeer.Ancestors(), []string{peer.ID})
+				assert.Equal(len(mockChildPeer.Ancestors()), 2)
+				assert.EqualValues(mockChildPeer.Ancestors(), []string{mockChildPeer.ID, peer.ID})
 			},
 		},
 		{
@@ -566,8 +566,8 @@ func TestPeer_Ancestors(t *testing.T) {
 			childID: idgen.PeerID("127.0.0.1"),
 			expect: func(t *testing.T, peer *Peer, mockChildPeer *Peer) {
 				assert := assert.New(t)
-				assert.Equal(len(mockChildPeer.Ancestors()), 0)
-				assert.EqualValues(mockChildPeer.Ancestors(), []string(nil))
+				assert.Equal(len(mockChildPeer.Ancestors()), 1)
+				assert.EqualValues(mockChildPeer.Ancestors(), []string{mockChildPeer.ID})
 			},
 		},
 		{
@@ -576,8 +576,8 @@ func TestPeer_Ancestors(t *testing.T) {
 			expect: func(t *testing.T, peer *Peer, mockChildPeer *Peer) {
 				assert := assert.New(t)
 				peer.StoreChild(peer)
-				assert.Equal(len(peer.Ancestors()), 0)
-				assert.Equal(peer.Ancestors(), []string(nil))
+				assert.Equal(len(peer.Ancestors()), 2)
+				assert.Equal(peer.Ancestors(), []string{peer.ID, peer.ID})
 			},
 		},
 	}