1 files changed, 86 insertions, 0 deletions

diff --git a/kernel/cgroup.c b/kernel/cgroup.c
index 2ed5968a04e7..0f8fa6aa371b 100644
--- a/kernel/cgroup.c
+++ b/kernel/cgroup.c
@@ -2984,6 +2984,92 @@ static void cgroup_enable_task_cg_lists(void)
         write_unlock(&css_set_lock);
 }
 
+/**
+ * cgroup_next_descendant_pre - find the next descendant for pre-order walk
+ * @pos: the current position (%NULL to initiate traversal)
+ * @cgroup: cgroup whose descendants to walk
+ *
+ * To be used by cgroup_for_each_descendant_pre().  Find the next
+ * descendant to visit for pre-order traversal of @cgroup's descendants.
+ */
+struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,
+                                          struct cgroup *cgroup)
+{
+        struct cgroup *next;
+
+        WARN_ON_ONCE(!rcu_read_lock_held());
+
+        /* if first iteration, pretend we just visited @cgroup */
+        if (!pos) {
+                if (list_empty(&cgroup->children))
+                        return NULL;
+                pos = cgroup;
+        }
+
+        /* visit the first child if exists */
+        next = list_first_or_null_rcu(&pos->children, struct cgroup, sibling);
+        if (next)
+                return next;
+
+        /* no child, visit my or the closest ancestor's next sibling */
+        do {
+                next = list_entry_rcu(pos->sibling.next, struct cgroup,
+                                      sibling);
+                if (&next->sibling != &pos->parent->children)
+                        return next;
+
+                pos = pos->parent;
+        } while (pos != cgroup);
+
+        return NULL;
+}
+EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre);
+
+static struct cgroup *cgroup_leftmost_descendant(struct cgroup *pos)
+{
+        struct cgroup *last;
+
+        do {
+                last = pos;
+                pos = list_first_or_null_rcu(&pos->children, struct cgroup,
+                                             sibling);
+        } while (pos);
+
+        return last;
+}
+
+/**
+ * cgroup_next_descendant_post - find the next descendant for post-order walk
+ * @pos: the current position (%NULL to initiate traversal)
+ * @cgroup: cgroup whose descendants to walk
+ *
+ * To be used by cgroup_for_each_descendant_post().  Find the next
+ * descendant to visit for post-order traversal of @cgroup's descendants.
+ */
+struct cgroup *cgroup_next_descendant_post(struct cgroup *pos,
+                                           struct cgroup *cgroup)
+{
+        struct cgroup *next;
+
+        WARN_ON_ONCE(!rcu_read_lock_held());
+
+        /* if first iteration, visit the leftmost descendant */
+        if (!pos) {
+                next = cgroup_leftmost_descendant(cgroup);
+                return next != cgroup ? next : NULL;
+        }
+
+        /* if there's an unvisited sibling, visit its leftmost descendant */
+        next = list_entry_rcu(pos->sibling.next, struct cgroup, sibling);
+        if (&next->sibling != &pos->parent->children)
+                return cgroup_leftmost_descendant(next);
+
+        /* no sibling left, visit parent */
+        next = pos->parent;
+        return next != cgroup ? next : NULL;
+}
+EXPORT_SYMBOL_GPL(cgroup_next_descendant_post);
+
 void cgroup_iter_start(struct cgroup *cgrp, struct cgroup_iter *it)
         __acquires(css_set_lock)
 {