crush: prevent loops from insert_item

If the insertion would create a loop, return -EINVAL.

Fixes: #3515
Signed-off-by: Sage Weil <sage@inktank.com>

2 files changed, 34 insertions, 0 deletions

diff --git a/src/crush/CrushWrapper.cc b/src/crush/CrushWrapper.cc
index 8d33839bbb7..475c8c105e9 100644
--- a/src/crush/CrushWrapper.cc
+++ b/src/crush/CrushWrapper.cc
@@ -20,6 +20,25 @@ void CrushWrapper::find_roots(set<int>& roots) const
   }
 }
 
+bool CrushWrapper::subtree_contains(int root, int item) const
+{
+  if (root == item)
+    return true;
+
+  if (root >= 0)
+    return false;  // root is a leaf
+
+  const crush_bucket *b = get_bucket(root);
+  if (!b)
+    return false;
+
+  for (unsigned j=0; j<b->size; j++) {
+    if (subtree_contains(b->items[j], item))
+      return true;
+  }
+  return false;
+}
+
 
 int CrushWrapper::remove_item(CephContext *cct, int item)
 {
@@ -230,6 +249,12 @@ int CrushWrapper::insert_item(CephContext *cct, int item, float weight, string n
       return -EINVAL;
     }
 
+    // check that we aren't creating a cycle.
+    if (subtree_contains(id, cur)) {
+      ldout(cct, 1) << "insert_item item " << cur << " already exists beneath " << id << dendl;
+      return -EINVAL;
+    }
+
     crush_bucket *b = get_bucket(id);
     assert(b);
 
diff --git a/src/crush/CrushWrapper.h b/src/crush/CrushWrapper.h
index e8120931103..5ea68b9a83d 100644
--- a/src/crush/CrushWrapper.h
+++ b/src/crush/CrushWrapper.h
@@ -212,6 +212,15 @@ public:
   void find_roots(set<int>& roots) const;
 
   /**
+   * see if an item is contained within a subtree
+   *
+   * @param root haystack
+   * @param item needle
+   * @return true if the item is located beneath the given node
+   */
+  bool subtree_contains(int root, int item) const;
+
+  /**
    * see if item is located where we think it is
    *
    * This verifies that the given item is located at a particular