cgroup: allow dropping RCU read lock while iterating
Subsystems (2)
PATCH 1/1 cgroup: allow dropping RCU read lock while iterating
Currently all cgroup iterators require the whole traversal to be contained in a single RCU read critical section, which can be too restrictive as there are times when blocking operations are necessary during traversal. This forces controllers to implement specific workarounds in those cases - building separate iteration list, punting actual operations to work items and so on.
This patchset updates cgroup iterators so that they allow dropping RCU read lock while iteration is in progress so that controllers which require sleeping during iteration don't need to implement their own mechanisms.
Dropping RCU read lock during iteration is unsafe because cgroup->sibling.next can't be trusted once RCU read lock is dropped. The sibling list is a RCU list and when a cgroup is removed the next pointer is retained to keep RCU traversal working. If the next sibling is removed while RCU read lock is dropped, the removed current cgroup's next won't be updated and the next sibling may complete its grace period and get freed leaving the next pointer dangling.
Working around the problem is relatiely simple. Whether ->sibling.next can be trusted can be trusted can be decided by looking at CGRP_REMOVED - as cgroup removals are fully serialized, the flag is guaranteed to be visible before the next sibling finishes its grace period. For those cases, each cgroup is assigned a monotonically increasing serial number. Because new cgroups are always appeneded to the children list, it's guaranteed that all children list are sorted in the ascending order of the serial numbers. When the next pointer can't be trusted, the next sibling can be located by walking the parent's children list from the beginning looking for the first cgroup with higher serial number.
The above is implemented in cgroup_next_sibling() and all iterators are updated to use it to find out the next sibling thus allowing droppping RCU read lock while iteration is in progress. This patchset replaces separate iteration list in device_cgroup with direct descendant walk and there will be further patches making use of this update.
This patchset contains the following five patches.
0001-cgroup-fix-a-subtle-bug-in-descendant-pre-order-walk.patch 0002-cgroup-make-cgroup_is_removed-static.patch 0003-cgroup-add-cgroup-serial_nr-and-implement-cgroup_nex.patch 0004-cgroup-update-iterators-to-use-cgroup_next_sibling.patch 0005-device_cgroup-simplify-cgroup-tree-walk-in-propagate.patch
0001 fixes a subtle iteration bug. Will be applied to for-3.10-fixes.
0002 is a trivial prep patch.
0003 implements cgroup_next_sibling() which can find out the next sibling regardless of the state of the current cgroup.
0004 updates all iterators to use cgroup_next_sibling().
0005 replaces iteration list work around in device_cgroup with direct iteration.
This patchset is on top of cgroup/for-3.11 23958e729e ("cgroup.h:
remove some functions that are now gone") and available in the following git branch.
git://git.kernel.org/pub/scm/linux/kernel/git/tj/cgroup.git review-interruptible-iter
diffstat follows.
include/linux/cgroup.h | 31 +++++++++++--- kernel/cgroup.c | 98 ++++++++++++++++++++++++++++++++++++++++------- security/device_cgroup.c | 56 ++++++++------------------ 3 files changed, 128 insertions(+), 57 deletions(-)
Thanks.
--
tejun
A message that is not in the archive (sent off-list or not yet received): 1369101025-28335-1-git-send-email-tj-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org
PATCH 1/5 cgroup: fix a subtle bug in descendant pre-order walk
When cgroup_next_descendant_pre() initiates a walk, it checks whether the subtree root doesn't have any children and if not returns NULL. Later code assumes that the subtree isn't empty. This is broken because the subtree may become empty inbetween, which can lead to the traversal escaping the subtree by walking to the sibling of the subtree root.
There's no reason to have the early exit path. Remove it along with the later assumption that the subtree isn't empty. This simplifies the code a bit and fixes the subtle bug.
While at it, fix the comment of cgroup_for_each_descendant_pre() which was incorrectly referring to ->css_offline() instead of ->css_online().
--- include/linux/cgroup.h | 2 +- kernel/cgroup.c | 9 +++------ 2 files changed, 4 insertions(+), 7 deletions(-)
include/linux/cgroup.h +1 -1
@@ -709,7 +709,7 @@ struct cgroup *cgroup_rightmost_descendant(struct cgroup *pos);* * If a subsystem synchronizes against the parent in its ->css_online() and * before starting iterating, and synchronizes against @pos on each -* iteration, any descendant cgroup which finished ->css_offline() is +* iteration, any descendant cgroup which finished ->css_online() is * guaranteed to be visible in the future iterations. * * In other words, the following guarantees that a descendant can't escape
kernel/cgroup.c +3 -6
@@ -2990,11 +2990,8 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,WARN_ON_ONCE (!rcu_read_lock_held ());/* if first iteration, pretend we just visited @cgroup */ -if (!pos) { -if (list_empty (&cgroup->children)) -return NULL ; +if (!pos) pos = cgroup; - }/* visit the first child if exists */ next = list_first_or_null_rcu(&pos->children, struct cgroup, sibling);
@@ -3002,14 +2999,14 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,return next;/* no child, visit my or the closest ancestor's next sibling */ -do { +while (pos != cgroup) { 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 ; }
Signature · 1 line
1.8.1.4
A message that is not in the archive (sent off-list or not yet received): 1369101025-28335-2-git-send-email-tj-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org
Michal Hocko
Reviewed-byRe: [PATCH 1/5] cgroup: fix a subtle bug in descendant pre-order walk
Quoted 11 lines · Tejun Heo
When
cgroup_next_descendant_pre()initiates a walk, it checks whether the subtree root doesn't have any children and if not returns NULL. Later code assumes that the subtree isn't empty. This is broken because the subtree may become empty inbetween, which can lead to the traversal escaping the subtree by walking to the sibling of the subtree root.There's no reason to have the early exit path. Remove it along with the later assumption that the subtree isn't empty. This simplifies the code a bit and fixes the subtle bug.
Quoted 6 lines
While at it, fix the comment of
cgroup_for_each_descendant_pre()which was incorrectly referring to ->css_offline() instead of ->css_online().Signed-off-by Tejun Heo <[email protected]>
Well spotted and looks good to me
Quoted 55 lines
--- include/linux/cgroup.h | 2 +- kernel/cgroup.c | 9 +++------ 2 files changed, 4 insertions(+), 7 deletions(-)include/linux/cgroup.h +1
-1@@ -709,7 +709,7 @@ struct cgroup *cgroup_rightmost_descendant(struct cgroup *pos);* * If a subsystem synchronizes against the parent in its ->css_online() and * before starting iterating, and synchronizes against @pos on each -* iteration, any descendant cgroup which finished ->css_offline() is +* iteration, any descendant cgroup which finished ->css_online() is * guaranteed to be visible in the future iterations. * * In other words, the following guarantees that a descendant can't escape kernel/cgroup.c +3
-6@@ -2990,11 +2990,8 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,WARN_ON_ONCE (!rcu_read_lock_held ());/* if first iteration, pretend we just visited @cgroup */ -if (!pos) { -if (list_empty (&cgroup->children)) -return NULL ; +if (!pos) pos = cgroup; - }/* visit the first child if exists */ next = list_first_or_null_rcu(&pos->children, struct cgroup, sibling);@@ -3002,14 +2999,14 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,return next;/* no child, visit my or the closest ancestor's next sibling */ -do { +while (pos != cgroup) { 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 ; }Signature · 1 line
1.8.1.4
Signature · 2 lines
Michal Hocko SUSE Labs
Michal Hocko
Reviewed-byRe: [PATCH 1/5] cgroup: fix a subtle bug in descendant pre-order walk
In reply to a message not in the archiveQuoted 11 lines · Tejun Heo
When
cgroup_next_descendant_pre()initiates a walk, it checks whether the subtree root doesn't have any children and if not returns NULL. Later code assumes that the subtree isn't empty. This is broken because the subtree may become empty inbetween, which can lead to the traversal escaping the subtree by walking to the sibling of the subtree root.There's no reason to have the early exit path. Remove it along with the later assumption that the subtree isn't empty. This simplifies the code a bit and fixes the subtle bug.
Quoted 6 lines
While at it, fix the comment of
cgroup_for_each_descendant_pre()which was incorrectly referring to ->css_offline() instead of ->css_online().Signed-off-by Tejun Heo <[email protected]>
Well spotted and looks good to me
Quoted 55 lines
--- include/linux/cgroup.h | 2 +- kernel/cgroup.c | 9 +++------ 2 files changed, 4 insertions(+), 7 deletions(-)include/linux/cgroup.h +1
-1@@ -709,7 +709,7 @@ struct cgroup *cgroup_rightmost_descendant(struct cgroup *pos);* * If a subsystem synchronizes against the parent in its ->css_online() and * before starting iterating, and synchronizes against @pos on each -* iteration, any descendant cgroup which finished ->css_offline() is +* iteration, any descendant cgroup which finished ->css_online() is * guaranteed to be visible in the future iterations. * * In other words, the following guarantees that a descendant can't escape kernel/cgroup.c +3
-6@@ -2990,11 +2990,8 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,WARN_ON_ONCE (!rcu_read_lock_held ());/* if first iteration, pretend we just visited @cgroup */ -if (!pos) { -if (list_empty (&cgroup->children)) -return NULL ; +if (!pos) pos = cgroup; - }/* visit the first child if exists */ next = list_first_or_null_rcu(&pos->children, struct cgroup, sibling);@@ -3002,14 +2999,14 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,return next;/* no child, visit my or the closest ancestor's next sibling */ -do { +while (pos != cgroup) { 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 ; }Signature · 1 line
1.8.1.4
Signature · 2 lines
Michal Hocko SUSE Labs
Tejun Heo
AppliedRe: [PATCH 1/5] cgroup: fix a subtle bug in descendant pre-order walk
In reply to a message not in the archiveQuoted 11 lines · Tejun Heo
When
cgroup_next_descendant_pre()initiates a walk, it checks whether the subtree root doesn't have any children and if not returns NULL. Later code assumes that the subtree isn't empty. This is broken because the subtree may become empty inbetween, which can lead to the traversal escaping the subtree by walking to the sibling of the subtree root.There's no reason to have the early exit path. Remove it along with the later assumption that the subtree isn't empty. This simplifies the code a bit and fixes the subtle bug.
Quoted 6 lines
While at it, fix the comment of
cgroup_for_each_descendant_pre()which was incorrectly referring to ->css_offline() instead of ->css_online().Signed-off-by Tejun Heo <[email protected]>
Applied to cgroup/for-3.10-fixes.
Thanks.
Signature · 1 line
tejun
PATCH 1/5 cgroup: fix a subtle bug in descendant pre-order walk
In reply to a message not in the archiveWhen cgroup_next_descendant_pre() initiates a walk, it checks whether the subtree root doesn't have any children and if not returns NULL. Later code assumes that the subtree isn't empty. This is broken because the subtree may become empty inbetween, which can lead to the traversal escaping the subtree by walking to the sibling of the subtree root.
There's no reason to have the early exit path. Remove it along with the later assumption that the subtree isn't empty. This simplifies the code a bit and fixes the subtle bug.
While at it, fix the comment of cgroup_for_each_descendant_pre() which was incorrectly referring to ->css_offline() instead of ->css_online().
--- include/linux/cgroup.h | 2 +- kernel/cgroup.c | 9 +++------ 2 files changed, 4 insertions(+), 7 deletions(-)
include/linux/cgroup.h +1 -1
@@ -709,7 +709,7 @@ struct cgroup *cgroup_rightmost_descendant(struct cgroup *pos);* * If a subsystem synchronizes against the parent in its ->css_online() and * before starting iterating, and synchronizes against @pos on each -* iteration, any descendant cgroup which finished ->css_offline() is +* iteration, any descendant cgroup which finished ->css_online() is * guaranteed to be visible in the future iterations. * * In other words, the following guarantees that a descendant can't escape
kernel/cgroup.c +3 -6
@@ -2990,11 +2990,8 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,WARN_ON_ONCE (!rcu_read_lock_held ());/* if first iteration, pretend we just visited @cgroup */ -if (!pos) { -if (list_empty (&cgroup->children)) -return NULL ; +if (!pos) pos = cgroup; - }/* visit the first child if exists */ next = list_first_or_null_rcu(&pos->children, struct cgroup, sibling);
@@ -3002,14 +2999,14 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,return next;/* no child, visit my or the closest ancestor's next sibling */ -do { +while (pos != cgroup) { 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 ; }
Signature · 1 line
1.8.1.4
PATCH 2/5 cgroup: make cgroup_is_removed() static
In reply to a message not in the archivecgroup_is_removed() no longer has external users and it shouldn't grow any - controllers should deal with cgroup_subsys_state on/offline state instead of cgroup removal state. Make it static.
While at it, make it return bool.
--- include/linux/cgroup.h | 1 - kernel/cgroup.c | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-)
include/linux/cgroup.h +0 -1
@@ -538,7 +538,6 @@ static inline const char *cgroup_name(const struct cgroup *cgrp)int cgroup_add_cftypes (struct cgroup_subsys *ss,struct cftype *cfts);int cgroup_rm_cftypes (struct cgroup_subsys *ss,struct cftype *cfts); -int cgroup_is_removed (const struct cgroup *cgrp);bool cgroup_is_descendant (struct cgroup *cgrp,struct cgroup *ancestor);int cgroup_path (const struct cgroup *cgrp,char *buf,int buflen);
kernel/cgroup.c +1 -1
@@ -226,7 +226,7 @@ static int css_refcnt(struct cgroup_subsys_state *css) }/* convenient tests for these bits */ -inline int cgroup_is_removed (const struct cgroup *cgrp) +static inline bool cgroup_is_removed (const struct cgroup *cgrp) {return test_bit (CGRP_REMOVED , &cgrp->flags); }
Signature · 1 line
1.8.1.4
A message that is not in the archive (sent off-list or not yet received): 1369101025-28335-3-git-send-email-tj-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org
Re: [PATCH 2/5] cgroup: make cgroup_is_removed() static
Quoted 7 lines · Tejun Heo
cgroup_is_removed()no longer has external users and it shouldn't grow any - controllers should deal withcgroup_subsys_stateon/offline state instead of cgroup removal state. Make it static.While at it, make it return bool.
Signed-off-by Tejun Heo <[email protected]>
Applied 2-5 to cgroup/for-3.11.
Thanks.
Signature · 1 line
tejun
A message that is not in the archive (sent off-list or not yet received): 20130524015613.GB19755-9pTldWuhBndy/[email protected]
Li Zefan
Acked-byRe: [PATCH 2/5] cgroup: make cgroup_is_removed() static
Quoted 11 lines · Tejun Heo
Quoted 7 lines · Tejun Heo
cgroup_is_removed()no longer has external users and it shouldn't grow any - controllers should deal withcgroup_subsys_stateon/offline state instead of cgroup removal state. Make it static.While at it, make it return bool.
Signed-off-by Tejun Heo <[email protected]>Applied 2-5 to cgroup/for-3.11.
Has been kind of busy with internal work. I'll update the cpuset patchset to use this.
Li Zefan
Acked-byRe: [PATCH 2/5] cgroup: make cgroup_is_removed() static
In reply to a message not in the archiveQuoted 11 lines · Tejun Heo
Quoted 7 lines · Tejun Heo
cgroup_is_removed()no longer has external users and it shouldn't grow any - controllers should deal withcgroup_subsys_stateon/offline state instead of cgroup removal state. Make it static.While at it, make it return bool.
Signed-off-by Tejun Heo <[email protected]>Applied 2-5 to cgroup/for-3.11.
Has been kind of busy with internal work. I'll update the cpuset patchset to use this.
PATCH 2/5 cgroup: make cgroup_is_removed() static
In reply to a message not in the archivecgroup_is_removed() no longer has external users and it shouldn't grow any - controllers should deal with cgroup_subsys_state on/offline state instead of cgroup removal state. Make it static.
While at it, make it return bool.
--- include/linux/cgroup.h | 1 - kernel/cgroup.c | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-)
include/linux/cgroup.h +0 -1
@@ -538,7 +538,6 @@ static inline const char *cgroup_name(const struct cgroup *cgrp)int cgroup_add_cftypes (struct cgroup_subsys *ss,struct cftype *cfts);int cgroup_rm_cftypes (struct cgroup_subsys *ss,struct cftype *cfts); -int cgroup_is_removed (const struct cgroup *cgrp);bool cgroup_is_descendant (struct cgroup *cgrp,struct cgroup *ancestor);int cgroup_path (const struct cgroup *cgrp,char *buf,int buflen);
kernel/cgroup.c +1 -1
@@ -226,7 +226,7 @@ static int css_refcnt(struct cgroup_subsys_state *css) }/* convenient tests for these bits */ -inline int cgroup_is_removed (const struct cgroup *cgrp) +static inline bool cgroup_is_removed (const struct cgroup *cgrp) {return test_bit (CGRP_REMOVED , &cgrp->flags); }
Signature · 1 line
1.8.1.4
PATCH 3/5 cgroup: add cgroup->serial_nr and implement cgroup_next_sibling()
In reply to a message not in the archiveCurrently, there's no easy way to find out the next sibling cgroup unless it's known that the current cgroup is accessed from the parent's children list in a single RCU critical section. This in turn forces all iterators to require whole iteration to be enclosed in a single RCU critical section, which sometimes is too restrictive. This patch implements cgroup_next_sibling() which can reliably determine the next sibling regardless of the state of the current cgroup as long as it's accessible.
It currently is impossible to determine the next sibling after dropping RCU read lock because the cgroup being iterated could be removed anytime and if RCU read lock is dropped, nothing guarantess its ->sibling.next pointer is accessible. A removed cgroup would continue to point to its next sibling for RCU accesses but stop receiving updates from the sibling. IOW, the next sibling could be removed and then complete its grace period while RCU read lock is dropped, making it unsafe to dereference ->sibling.next after dropping and re-acquiring RCU read lock.
This can be solved by adding a way to traverse to the next sibling without dereferencing ->sibling.next. This patch adds a monotonically increasing cgroup serial number, cgroup->serial_nr, which guarantees that all cgroup->children lists are kept in increasing serial_nr order. A new function, cgroup_next_sibling(), is implemented, which, if CGRP_REMOVED is not set on the current cgroup, follows ->sibling.next; otherwise, traverses the parent's ->children list until it sees a sibling with higher ->serial_nr.
This allows the function to always return the next sibling regardless of the state of the current cgroup without adding overhead in the fast path.
Further patches will update the iterators to use cgroup_next_sibling() so that they allow dropping RCU read lock and blocking while iteration is in progress which in turn will be used to simplify controllers.
--- include/linux/cgroup.h | 10 ++++++++ kernel/cgroup.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 72 insertions(+)
include/linux/cgroup.h +10 -0
@@ -189,6 +189,14 @@ struct cgroup {struct dentry *dentry;/* cgroup fs entry, RCU protected */ /* +* Monotonically increasing unique serial number which defines a +* uniform order among all cgroups. It's guaranteed that all +* ->children lists are in the ascending order of ->serial_nr. +* It's used to allow interrupting and resuming iterations. +*/ +u64 serial_nr; + +/* * This is a copy of dentry->d_name, and it's needed because * we can't use dentry->d_name in cgroup_path(). *
@@ -675,6 +683,8 @@ static inline struct cgroup* task_cgroup(struct task_struct *task,return task_subsys_state (task, subsys_id)->cgroup; } +struct cgroup *cgroup_next_sibling (struct cgroup *pos); +/** * cgroup_for_each_child - iterate through children of a cgroup * @pos: the cgroup * to use as the loop cursor
kernel/cgroup.c +62 -0
86 lines not on this page · raw message
Signature · 1 line
1.8.1.4
A message that is not in the archive (sent off-list or not yet received): 1369101025-28335-4-git-send-email-tj-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org
Serge Hallyn
Acked-byRe: [PATCH 3/5] cgroup: add cgroup->serial_nr and implement cgroup_next_sibling()
Quoted 32 lines · Tejun Heo
Currently, there's no easy way to find out the next sibling cgroup unless it's known that the current cgroup is accessed from the parent's children list in a single RCU critical section. This in turn forces all iterators to require whole iteration to be enclosed in a single RCU critical section, which sometimes is too restrictive. This patch implements
cgroup_next_sibling()which can reliably determine the next sibling regardless of the state of the current cgroup as long as it's accessible.It currently is impossible to determine the next sibling after dropping RCU read lock because the cgroup being iterated could be removed anytime and if RCU read lock is dropped, nothing guarantess its ->sibling.next pointer is accessible. A removed cgroup would continue to point to its next sibling for RCU accesses but stop receiving updates from the sibling. IOW, the next sibling could be removed and then complete its grace period while RCU read lock is dropped, making it unsafe to dereference ->sibling.next after dropping and re-acquiring RCU read lock.
This can be solved by adding a way to traverse to the next sibling without dereferencing ->sibling.next. This patch adds a monotonically increasing cgroup serial number,
cgroup->serial_nr, which guarantees that allcgroup->childrenlists are kept in increasingserial_nrorder. A new function,cgroup_next_sibling(), is implemented, which, ifCGRP_REMOVEDis not set on the current cgroup, follows ->sibling.next; otherwise, traverses the parent's ->children list until it sees a sibling with higher ->serial_nr.This allows the function to always return the next sibling regardless of the state of the current cgroup without adding overhead in the fast path.
Quoted 5 lines
Further patches will update the iterators to use
cgroup_next_sibling()so that they allow dropping RCU read lock and blocking while iteration is in progress which in turn will be used to simplify controllers.Signed-off-by Tejun Heo <[email protected]>
Looks sensible, thanks.
(ultra-nit: typo @ "reomval")
Quoted 134 lines
--- include/linux/cgroup.h | 10 ++++++++ kernel/cgroup.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 72 insertions(+)include/linux/cgroup.h +10
-0@@ -189,6 +189,14 @@ struct cgroup {struct dentry *dentry;/* cgroup fs entry, RCU protected */ /* +* Monotonically increasing unique serial number which defines a +* uniform order among all cgroups. It's guaranteed that all +* ->children lists are in the ascending order of ->serial_nr. +* It's used to allow interrupting and resuming iterations. +*/ +u64 serial_nr; + +/* * This is a copy of dentry->d_name, and it's needed because * we can't use dentry->d_name in cgroup_path(). * @@ -675,6 +683,8 @@ static inline struct cgroup* task_cgroup(struct task_struct *task,return task_subsys_state (task, subsys_id)->cgroup; } +struct cgroup *cgroup_next_sibling (struct cgroup *pos); +/** * cgroup_for_each_child - iterate through children of a cgroup * @pos: the cgroup * to use as the loop cursor kernel/cgroup.c +62
-0@@ -2975,6 +2975,55 @@ static void cgroup_enable_task_cg_lists(void) }/** +* cgroup_next_sibling - find the next sibling of a given cgroup +* @pos: the current cgroup +* +* This function returns the next sibling of @pos and should be called +* under RCU read lock. The only requirement is that @pos is accessible. +* The next sibling is guaranteed to be returned regardless of @pos's +* state. +*/ +struct cgroup *cgroup_next_sibling (struct cgroup *pos) +{ +struct cgroup *next; + +WARN_ON_ONCE (!rcu_read_lock_held ()); + +/* +* @pos could already have been removed. Once a cgroup is removed, +* its ->sibling.next is no longer updated when its next sibling +* changes. As CGRP_REMOVED is set on removal which is fully +* serialized, if we see it unasserted, it's guaranteed that the +* next sibling hasn't finished its grace period even if it's +* already removed, and thus safe to dereference from this RCU +* critical section. If ->sibling.next is inaccessible, +* cgroup_is_removed() is guaranteed to be visible as %true here. +*/ +if (likely (!cgroup_is_removed (pos))) { + next = list_entry_rcu(pos->sibling.next, struct cgroup, sibling); +if (&next->sibling != &pos->parent->children) +return next; +return NULL ; + } + +/* +* Can't dereference the next pointer. Each cgroup is given a +* monotonically increasing unique serial number and always +* appended to the sibling list, so the next one can be found by +* walking the parent's children until we see a cgroup with higher +* serial number than @pos's. +* +* While this path can be slow, it's taken only when either the +* current cgroup is removed or iteration and reomval race. +*/ +list_for_each_entry_rcu (next, &pos->parent->children, sibling) +if (next->serial_nr > pos->serial_nr) +return next; +return NULL ; +} +EXPORT_SYMBOL_GPL (cgroup_next_sibling); + +/** * 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 @@ -4136,6 +4185,7 @@ static void offline_css(struct cgroup_subsys *ss, struct cgroup *cgrp)static long cgroup_create (struct cgroup *parent,struct dentry *dentry,umode_t mode) { +static atomic64_t serial_nr_cursor =ATOMIC64_INIT (0 );struct cgroup *cgrp;struct cgroup_name *name;struct cgroupfs_root *root = parent->root;@@ -4216,6 +4266,14 @@ static long cgroup_create(struct cgroup *parent, struct dentry *dentry, goto err_free_all;lockdep_assert_held (&dentry->d_inode->i_mutex); +/* +* Assign a monotonically increasing serial number. With the list +* appending below, it guarantees that sibling cgroups are always +* sorted in the ascending serial number order on the parent's +* ->children. +*/ + cgrp->serial_nr =atomic64_inc_return (&serial_nr_cursor); +/* allocation complete, commit to creation */ list_add_tail (&cgrp->allcg_node, &root->allcg_list);list_add_tail_rcu (&cgrp->sibling, &cgrp->parent->children);@@ -4303,6 +4361,10 @@ static int cgroup_destroy_locked(struct cgroup *cgrp)* removed. This makes future css_tryget() and child creation * attempts fail thus maintaining the removal conditions verified * above. +* +* Note that CGRP_REMVOED clearing is depended upon by +* cgroup_next_sibling() to resume iteration after dropping RCU +* read lock. See cgroup_next_sibling() for details. */ for_each_subsys (cgrp->root, ss) {struct cgroup_subsys_state *css = cgrp->subsys[ss->subsys_id];Signature · 6 lines
1.8.1.4 _______________________________________________ Containers mailing list Containers-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org https://lists.linuxfoundation.org/mailman/listinfo/containers
Serge Hallyn
Acked-byRe: [PATCH 3/5] cgroup: add cgroup->serial_nr and implement cgroup_next_sibling()
In reply to a message not in the archiveQuoted 32 lines · Tejun Heo
Currently, there's no easy way to find out the next sibling cgroup unless it's known that the current cgroup is accessed from the parent's children list in a single RCU critical section. This in turn forces all iterators to require whole iteration to be enclosed in a single RCU critical section, which sometimes is too restrictive. This patch implements
cgroup_next_sibling()which can reliably determine the next sibling regardless of the state of the current cgroup as long as it's accessible.It currently is impossible to determine the next sibling after dropping RCU read lock because the cgroup being iterated could be removed anytime and if RCU read lock is dropped, nothing guarantess its ->sibling.next pointer is accessible. A removed cgroup would continue to point to its next sibling for RCU accesses but stop receiving updates from the sibling. IOW, the next sibling could be removed and then complete its grace period while RCU read lock is dropped, making it unsafe to dereference ->sibling.next after dropping and re-acquiring RCU read lock.
This can be solved by adding a way to traverse to the next sibling without dereferencing ->sibling.next. This patch adds a monotonically increasing cgroup serial number,
cgroup->serial_nr, which guarantees that allcgroup->childrenlists are kept in increasingserial_nrorder. A new function,cgroup_next_sibling(), is implemented, which, ifCGRP_REMOVEDis not set on the current cgroup, follows ->sibling.next; otherwise, traverses the parent's ->children list until it sees a sibling with higher ->serial_nr.This allows the function to always return the next sibling regardless of the state of the current cgroup without adding overhead in the fast path.
Quoted 5 lines
Further patches will update the iterators to use
cgroup_next_sibling()so that they allow dropping RCU read lock and blocking while iteration is in progress which in turn will be used to simplify controllers.Signed-off-by Tejun Heo <[email protected]>
Looks sensible, thanks.
(ultra-nit: typo @ "reomval")
Quoted 134 lines
--- include/linux/cgroup.h | 10 ++++++++ kernel/cgroup.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 72 insertions(+)include/linux/cgroup.h +10
-0@@ -189,6 +189,14 @@ struct cgroup {struct dentry *dentry;/* cgroup fs entry, RCU protected */ /* +* Monotonically increasing unique serial number which defines a +* uniform order among all cgroups. It's guaranteed that all +* ->children lists are in the ascending order of ->serial_nr. +* It's used to allow interrupting and resuming iterations. +*/ +u64 serial_nr; + +/* * This is a copy of dentry->d_name, and it's needed because * we can't use dentry->d_name in cgroup_path(). * @@ -675,6 +683,8 @@ static inline struct cgroup* task_cgroup(struct task_struct *task,return task_subsys_state (task, subsys_id)->cgroup; } +struct cgroup *cgroup_next_sibling (struct cgroup *pos); +/** * cgroup_for_each_child - iterate through children of a cgroup * @pos: the cgroup * to use as the loop cursor kernel/cgroup.c +62
-0@@ -2975,6 +2975,55 @@ static void cgroup_enable_task_cg_lists(void) }/** +* cgroup_next_sibling - find the next sibling of a given cgroup +* @pos: the current cgroup +* +* This function returns the next sibling of @pos and should be called +* under RCU read lock. The only requirement is that @pos is accessible. +* The next sibling is guaranteed to be returned regardless of @pos's +* state. +*/ +struct cgroup *cgroup_next_sibling (struct cgroup *pos) +{ +struct cgroup *next; + +WARN_ON_ONCE (!rcu_read_lock_held ()); + +/* +* @pos could already have been removed. Once a cgroup is removed, +* its ->sibling.next is no longer updated when its next sibling +* changes. As CGRP_REMOVED is set on removal which is fully +* serialized, if we see it unasserted, it's guaranteed that the +* next sibling hasn't finished its grace period even if it's +* already removed, and thus safe to dereference from this RCU +* critical section. If ->sibling.next is inaccessible, +* cgroup_is_removed() is guaranteed to be visible as %true here. +*/ +if (likely (!cgroup_is_removed (pos))) { + next = list_entry_rcu(pos->sibling.next, struct cgroup, sibling); +if (&next->sibling != &pos->parent->children) +return next; +return NULL ; + } + +/* +* Can't dereference the next pointer. Each cgroup is given a +* monotonically increasing unique serial number and always +* appended to the sibling list, so the next one can be found by +* walking the parent's children until we see a cgroup with higher +* serial number than @pos's. +* +* While this path can be slow, it's taken only when either the +* current cgroup is removed or iteration and reomval race. +*/ +list_for_each_entry_rcu (next, &pos->parent->children, sibling) +if (next->serial_nr > pos->serial_nr) +return next; +return NULL ; +} +EXPORT_SYMBOL_GPL (cgroup_next_sibling); + +/** * 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 @@ -4136,6 +4185,7 @@ static void offline_css(struct cgroup_subsys *ss, struct cgroup *cgrp)static long cgroup_create (struct cgroup *parent,struct dentry *dentry,umode_t mode) { +static atomic64_t serial_nr_cursor =ATOMIC64_INIT (0 );struct cgroup *cgrp;struct cgroup_name *name;struct cgroupfs_root *root = parent->root;@@ -4216,6 +4266,14 @@ static long cgroup_create(struct cgroup *parent, struct dentry *dentry, goto err_free_all;lockdep_assert_held (&dentry->d_inode->i_mutex); +/* +* Assign a monotonically increasing serial number. With the list +* appending below, it guarantees that sibling cgroups are always +* sorted in the ascending serial number order on the parent's +* ->children. +*/ + cgrp->serial_nr =atomic64_inc_return (&serial_nr_cursor); +/* allocation complete, commit to creation */ list_add_tail (&cgrp->allcg_node, &root->allcg_list);list_add_tail_rcu (&cgrp->sibling, &cgrp->parent->children);@@ -4303,6 +4361,10 @@ static int cgroup_destroy_locked(struct cgroup *cgrp)* removed. This makes future css_tryget() and child creation * attempts fail thus maintaining the removal conditions verified * above. +* +* Note that CGRP_REMVOED clearing is depended upon by +* cgroup_next_sibling() to resume iteration after dropping RCU +* read lock. See cgroup_next_sibling() for details. */ for_each_subsys (cgrp->root, ss) {struct cgroup_subsys_state *css = cgrp->subsys[ss->subsys_id];Signature · 6 lines
1.8.1.4 _______________________________________________ Containers mailing list Containers-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org https://lists.linuxfoundation.org/mailman/listinfo/containers
Re: [PATCH 3/5] cgroup: add cgroup->serial_nr and implement cgroup_next_sibling()
In reply to a message not in the archiveHi Tejun,
kernel/cgroup.c static void cgroup_enable_task_cg_lists(void) · line 3017
Quoted 1 line · Tejun Heo
kernel/cgroup.c +1
-0+* current cgroup is removed or iteration and reomval race.
^^^^^^^
small typo
Signature · 1 line
Aristeu
A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: [PATCH 3/5] cgroup: add cgroup->serial_nr and implement cgroup_next_sibling()
Quoted 5 lines · Aristeu Rozanski
Hi Tejun,
kernel/cgroup.c static void cgroup_enable_task_cg_lists(void) · line 3017
Quoted 1 line · Tejun Heo
kernel/cgroup.c +1
-0+* current cgroup is removed or iteration and reomval race. ^^^^^^^small typo
Yeap, Serge spotted it too. Updated.
Thanks.
Signature · 1 line
tejun
Michal Hocko
Reviewed-byRe: [PATCH 3/5] cgroup: add cgroup->serial_nr and implement cgroup_next_sibling()
In reply to a message not in the archiveQuoted 32 lines · Tejun Heo
Currently, there's no easy way to find out the next sibling cgroup unless it's known that the current cgroup is accessed from the parent's children list in a single RCU critical section. This in turn forces all iterators to require whole iteration to be enclosed in a single RCU critical section, which sometimes is too restrictive. This patch implements
cgroup_next_sibling()which can reliably determine the next sibling regardless of the state of the current cgroup as long as it's accessible.It currently is impossible to determine the next sibling after dropping RCU read lock because the cgroup being iterated could be removed anytime and if RCU read lock is dropped, nothing guarantess its ->sibling.next pointer is accessible. A removed cgroup would continue to point to its next sibling for RCU accesses but stop receiving updates from the sibling. IOW, the next sibling could be removed and then complete its grace period while RCU read lock is dropped, making it unsafe to dereference ->sibling.next after dropping and re-acquiring RCU read lock.
This can be solved by adding a way to traverse to the next sibling without dereferencing ->sibling.next. This patch adds a monotonically increasing cgroup serial number,
cgroup->serial_nr, which guarantees that allcgroup->childrenlists are kept in increasingserial_nrorder. A new function,cgroup_next_sibling(), is implemented, which, ifCGRP_REMOVEDis not set on the current cgroup, follows ->sibling.next; otherwise, traverses the parent's ->children list until it sees a sibling with higher ->serial_nr.This allows the function to always return the next sibling regardless of the state of the current cgroup without adding overhead in the fast path.
Quoted 5 lines
Further patches will update the iterators to use
cgroup_next_sibling()so that they allow dropping RCU read lock and blocking while iteration is in progress which in turn will be used to simplify controllers.Signed-off-by Tejun Heo <[email protected]>
OK, I was about to object that the given pos could be freed already but I can see that the next patch documents that the caller has to make sure that pos will not go away (by elevating css count) before rcu is dropped.
Quoted 130 lines
--- include/linux/cgroup.h | 10 ++++++++ kernel/cgroup.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 72 insertions(+)include/linux/cgroup.h +10
-0@@ -189,6 +189,14 @@ struct cgroup {struct dentry *dentry;/* cgroup fs entry, RCU protected */ /* +* Monotonically increasing unique serial number which defines a +* uniform order among all cgroups. It's guaranteed that all +* ->children lists are in the ascending order of ->serial_nr. +* It's used to allow interrupting and resuming iterations. +*/ +u64 serial_nr; + +/* * This is a copy of dentry->d_name, and it's needed because * we can't use dentry->d_name in cgroup_path(). * @@ -675,6 +683,8 @@ static inline struct cgroup* task_cgroup(struct task_struct *task,return task_subsys_state (task, subsys_id)->cgroup; } +struct cgroup *cgroup_next_sibling (struct cgroup *pos); +/** * cgroup_for_each_child - iterate through children of a cgroup * @pos: the cgroup * to use as the loop cursor kernel/cgroup.c +62
-0@@ -2975,6 +2975,55 @@ static void cgroup_enable_task_cg_lists(void) }/** +* cgroup_next_sibling - find the next sibling of a given cgroup +* @pos: the current cgroup +* +* This function returns the next sibling of @pos and should be called +* under RCU read lock. The only requirement is that @pos is accessible. +* The next sibling is guaranteed to be returned regardless of @pos's +* state. +*/ +struct cgroup *cgroup_next_sibling (struct cgroup *pos) +{ +struct cgroup *next; + +WARN_ON_ONCE (!rcu_read_lock_held ()); + +/* +* @pos could already have been removed. Once a cgroup is removed, +* its ->sibling.next is no longer updated when its next sibling +* changes. As CGRP_REMOVED is set on removal which is fully +* serialized, if we see it unasserted, it's guaranteed that the +* next sibling hasn't finished its grace period even if it's +* already removed, and thus safe to dereference from this RCU +* critical section. If ->sibling.next is inaccessible, +* cgroup_is_removed() is guaranteed to be visible as %true here. +*/ +if (likely (!cgroup_is_removed (pos))) { + next = list_entry_rcu(pos->sibling.next, struct cgroup, sibling); +if (&next->sibling != &pos->parent->children) +return next; +return NULL ; + } + +/* +* Can't dereference the next pointer. Each cgroup is given a +* monotonically increasing unique serial number and always +* appended to the sibling list, so the next one can be found by +* walking the parent's children until we see a cgroup with higher +* serial number than @pos's. +* +* While this path can be slow, it's taken only when either the +* current cgroup is removed or iteration and reomval race. +*/ +list_for_each_entry_rcu (next, &pos->parent->children, sibling) +if (next->serial_nr > pos->serial_nr) +return next; +return NULL ; +} +EXPORT_SYMBOL_GPL (cgroup_next_sibling); + +/** * 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 @@ -4136,6 +4185,7 @@ static void offline_css(struct cgroup_subsys *ss, struct cgroup *cgrp)static long cgroup_create (struct cgroup *parent,struct dentry *dentry,umode_t mode) { +static atomic64_t serial_nr_cursor =ATOMIC64_INIT (0 );struct cgroup *cgrp;struct cgroup_name *name;struct cgroupfs_root *root = parent->root;@@ -4216,6 +4266,14 @@ static long cgroup_create(struct cgroup *parent, struct dentry *dentry, goto err_free_all;lockdep_assert_held (&dentry->d_inode->i_mutex); +/* +* Assign a monotonically increasing serial number. With the list +* appending below, it guarantees that sibling cgroups are always +* sorted in the ascending serial number order on the parent's +* ->children. +*/ + cgrp->serial_nr =atomic64_inc_return (&serial_nr_cursor); +/* allocation complete, commit to creation */ list_add_tail (&cgrp->allcg_node, &root->allcg_list);list_add_tail_rcu (&cgrp->sibling, &cgrp->parent->children);@@ -4303,6 +4361,10 @@ static int cgroup_destroy_locked(struct cgroup *cgrp)* removed. This makes future css_tryget() and child creation * attempts fail thus maintaining the removal conditions verified * above. +* +* Note that CGRP_REMVOED clearing is depended upon by +* cgroup_next_sibling() to resume iteration after dropping RCU +* read lock. See cgroup_next_sibling() for details. */ for_each_subsys (cgrp->root, ss) {struct cgroup_subsys_state *css = cgrp->subsys[ss->subsys_id];Signature · 1 line
1.8.1.4
Signature · 2 lines
Michal Hocko SUSE Labs
PATCH 3/5 cgroup: add cgroup->serial_nr and implement cgroup_next_sibling()
In reply to a message not in the archiveCurrently, there's no easy way to find out the next sibling cgroup unless it's known that the current cgroup is accessed from the parent's children list in a single RCU critical section. This in turn forces all iterators to require whole iteration to be enclosed in a single RCU critical section, which sometimes is too restrictive. This patch implements cgroup_next_sibling() which can reliably determine the next sibling regardless of the state of the current cgroup as long as it's accessible.
It currently is impossible to determine the next sibling after dropping RCU read lock because the cgroup being iterated could be removed anytime and if RCU read lock is dropped, nothing guarantess its ->sibling.next pointer is accessible. A removed cgroup would continue to point to its next sibling for RCU accesses but stop receiving updates from the sibling. IOW, the next sibling could be removed and then complete its grace period while RCU read lock is dropped, making it unsafe to dereference ->sibling.next after dropping and re-acquiring RCU read lock.
This can be solved by adding a way to traverse to the next sibling without dereferencing ->sibling.next. This patch adds a monotonically increasing cgroup serial number, cgroup->serial_nr, which guarantees that all cgroup->children lists are kept in increasing serial_nr order. A new function, cgroup_next_sibling(), is implemented, which, if CGRP_REMOVED is not set on the current cgroup, follows ->sibling.next; otherwise, traverses the parent's ->children list until it sees a sibling with higher ->serial_nr.
This allows the function to always return the next sibling regardless of the state of the current cgroup without adding overhead in the fast path.
Further patches will update the iterators to use cgroup_next_sibling() so that they allow dropping RCU read lock and blocking while iteration is in progress which in turn will be used to simplify controllers.
--- include/linux/cgroup.h | 10 ++++++++ kernel/cgroup.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 72 insertions(+)
include/linux/cgroup.h +10 -0
@@ -189,6 +189,14 @@ struct cgroup {struct dentry *dentry;/* cgroup fs entry, RCU protected */ /* +* Monotonically increasing unique serial number which defines a +* uniform order among all cgroups. It's guaranteed that all +* ->children lists are in the ascending order of ->serial_nr. +* It's used to allow interrupting and resuming iterations. +*/ +u64 serial_nr; + +/* * This is a copy of dentry->d_name, and it's needed because * we can't use dentry->d_name in cgroup_path(). *
@@ -675,6 +683,8 @@ static inline struct cgroup* task_cgroup(struct task_struct *task,return task_subsys_state (task, subsys_id)->cgroup; } +struct cgroup *cgroup_next_sibling (struct cgroup *pos); +/** * cgroup_for_each_child - iterate through children of a cgroup * @pos: the cgroup * to use as the loop cursor
kernel/cgroup.c +62 -0
86 lines not on this page · raw message
Signature · 1 line
1.8.1.4
PATCH 4/5 cgroup: update iterators to use cgroup_next_sibling()
In reply to a message not in the archiveThis patch converts cgroup_for_each_child(), cgroup_next_descendant_pre/post() and thus cgroup_for_each_descendant_pre/post() to use cgroup_next_sibling() instead of manually dereferencing ->sibling.next.
The only reason the iterators couldn't allow dropping RCU read lock while iteration is in progress was because they couldn't determine the next sibling safely once RCU read lock is dropped. Using cgroup_next_sibling() removes that problem and enables all iterators to allow dropping RCU read lock in the middle. Comments are updated accordingly.
This makes the iterators easier to use and will simplify controllers.
Note that @cgroup argument is renamed to @cgrp in cgroup_for_each_child() because it conflicts with "struct cgroup" used in the new macro body.
--- include/linux/cgroup.h | 18 ++++++++++++++---- kernel/cgroup.c | 25 +++++++++++++++++++------ 2 files changed, 33 insertions(+), 10 deletions(-)
include/linux/cgroup.h +14 -4
@@ -688,9 +688,9 @@ struct cgroup *cgroup_next_sibling(struct cgroup *pos);/** * cgroup_for_each_child - iterate through children of a cgroup * @pos: the cgroup * to use as the loop cursor -* @cgroup: cgroup whose children to walk +* @cgrp: cgroup whose children to walk * -* Walk @cgroup's children. Must be called under rcu_read_lock(). A child +* Walk @cgrp's children. Must be called under rcu_read_lock(). A child * cgroup which hasn't finished ->css_online() or already has finished * ->css_offline() may show up during traversal and it's each subsystem's * responsibility to verify that each @pos is alive.
@@ -698,9 +698,15 @@ struct cgroup *cgroup_next_sibling(struct cgroup *pos);* If a subsystem synchronizes against the parent in its ->css_online() and * before starting iterating, a cgroup which finished ->css_online() is * guaranteed to be visible in the future iterations. +* +* It is allowed to temporarily drop RCU read lock during iteration. The +* caller is responsible for ensuring that @pos remains accessible until +* the start of the next iteration by, for example, bumping the css refcnt. */ -#define cgroup_for_each_child (pos, cgroup) \ - list_for_each_entry_rcu(pos, &(cgroup)->children, sibling) +#define cgroup_for_each_child (pos, cgrp) \ + for ((pos) = list_first_or_null_rcu(&(cgrp)->children, \ + struct cgroup, sibling); \ + (pos); (pos) = cgroup_next_sibling((pos)))struct cgroup *cgroup_next_descendant_pre (struct cgroup *pos,struct cgroup *cgroup);
@@ -759,6 +765,10 @@ struct cgroup *cgroup_rightmost_descendant(struct cgroup *pos);* Alternatively, a subsystem may choose to use a single global lock to * synchronize ->css_online() and ->css_offline() against tree-walking * operations. +* +* It is allowed to temporarily drop RCU read lock during iteration. The +* caller is responsible for ensuring that @pos remains accessible until +* the start of the next iteration by, for example, bumping the css refcnt. */ #define cgroup_for_each_descendant_pre (pos, cgroup) \ for (pos = cgroup_next_descendant_pre(NULL, (cgroup)); (pos); \
kernel/cgroup.c +19 -6
@@ -3030,6 +3030,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_sibling);* * To be used by cgroup_for_each_descendant_pre(). Find the next * descendant to visit for pre-order traversal of @cgroup's descendants. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct next descendant as long as both @pos +* and @cgroup are accessible and @pos is a descendant of @cgroup. */ struct cgroup *cgroup_next_descendant_pre (struct cgroup *pos,struct cgroup *cgroup)
@@ -3049,11 +3054,9 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,/* no child, visit my or the closest ancestor's next sibling */ while (pos != cgroup) { - next = list_entry_rcu(pos->sibling.next, struct cgroup, - sibling); -if (&next->sibling != &pos->parent->children) + next =cgroup_next_sibling (pos); +if (next)return next; - pos = pos->parent; }
@@ -3068,6 +3071,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre);* Return the rightmost descendant of @pos. If there's no descendant, * @pos is returned. This can be used during pre-order traversal to skip * subtree of @pos. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct rightmost descendant as long as @pos is +* accessible. */ struct cgroup *cgroup_rightmost_descendant (struct cgroup *pos) {
@@ -3107,6 +3115,11 @@ static struct cgroup *cgroup_leftmost_descendant(struct cgroup *pos)* * To be used by cgroup_for_each_descendant_post(). Find the next * descendant to visit for post-order traversal of @cgroup's descendants. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct next descendant as long as both @pos +* and @cgroup are accessible and @pos is a descendant of @cgroup. */ struct cgroup *cgroup_next_descendant_post (struct cgroup *pos,struct cgroup *cgroup)
@@ -3122,8 +3135,8 @@ struct cgroup *cgroup_next_descendant_post(struct cgroup *pos, }/* 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) + next =cgroup_next_sibling (pos); +if (next)return cgroup_leftmost_descendant (next);/* no sibling left, visit parent */
Signature · 1 line
1.8.1.4
A message that is not in the archive (sent off-list or not yet received): 1369101025-28335-5-git-send-email-tj-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org
Serge Hallyn
Acked-byRe: [PATCH 4/5] cgroup: update iterators to use cgroup_next_sibling()
Quoted 12 lines · Tejun Heo
This patch converts
cgroup_for_each_child(), cgroup_next_descendant_pre/post() and thus cgroup_for_each_descendant_pre/post() to usecgroup_next_sibling()instead of manually dereferencing ->sibling.next.The only reason the iterators couldn't allow dropping RCU read lock while iteration is in progress was because they couldn't determine the next sibling safely once RCU read lock is dropped. Using
cgroup_next_sibling()removes that problem and enables all iterators to allow dropping RCU read lock in the middle. Comments are updated accordingly.
Quoted 7 lines
This makes the iterators easier to use and will simplify controllers.
Note that @cgroup argument is renamed to @cgrp in
cgroup_for_each_child()because it conflicts with "struct cgroup" used in the new macro body.Signed-off-by Tejun Heo <[email protected]>
I didn't test, but it looks correct, thanks.
Quoted 122 lines
--- include/linux/cgroup.h | 18 ++++++++++++++---- kernel/cgroup.c | 25 +++++++++++++++++++------ 2 files changed, 33 insertions(+), 10 deletions(-)include/linux/cgroup.h +14
-4@@ -688,9 +688,9 @@ struct cgroup *cgroup_next_sibling(struct cgroup *pos);/** * cgroup_for_each_child - iterate through children of a cgroup * @pos: the cgroup * to use as the loop cursor -* @cgroup: cgroup whose children to walk +* @cgrp: cgroup whose children to walk * -* Walk @cgroup's children. Must be called under rcu_read_lock(). A child +* Walk @cgrp's children. Must be called under rcu_read_lock(). A child * cgroup which hasn't finished ->css_online() or already has finished * ->css_offline() may show up during traversal and it's each subsystem's * responsibility to verify that each @pos is alive. @@ -698,9 +698,15 @@ struct cgroup *cgroup_next_sibling(struct cgroup *pos);* If a subsystem synchronizes against the parent in its ->css_online() and * before starting iterating, a cgroup which finished ->css_online() is * guaranteed to be visible in the future iterations. +* +* It is allowed to temporarily drop RCU read lock during iteration. The +* caller is responsible for ensuring that @pos remains accessible until +* the start of the next iteration by, for example, bumping the css refcnt. */ -#define cgroup_for_each_child (pos, cgroup) \ - list_for_each_entry_rcu(pos, &(cgroup)->children, sibling) +#define cgroup_for_each_child (pos, cgrp) \ + for ((pos) = list_first_or_null_rcu(&(cgrp)->children, \ + struct cgroup, sibling); \ + (pos); (pos) = cgroup_next_sibling((pos)))struct cgroup *cgroup_next_descendant_pre (struct cgroup *pos,struct cgroup *cgroup);@@ -759,6 +765,10 @@ struct cgroup *cgroup_rightmost_descendant(struct cgroup *pos);* Alternatively, a subsystem may choose to use a single global lock to * synchronize ->css_online() and ->css_offline() against tree-walking * operations. +* +* It is allowed to temporarily drop RCU read lock during iteration. The +* caller is responsible for ensuring that @pos remains accessible until +* the start of the next iteration by, for example, bumping the css refcnt. */ #define cgroup_for_each_descendant_pre (pos, cgroup) \ for (pos = cgroup_next_descendant_pre(NULL, (cgroup)); (pos); \kernel/cgroup.c +19
-6@@ -3030,6 +3030,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_sibling);* * To be used by cgroup_for_each_descendant_pre(). Find the next * descendant to visit for pre-order traversal of @cgroup's descendants. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct next descendant as long as both @pos +* and @cgroup are accessible and @pos is a descendant of @cgroup. */ struct cgroup *cgroup_next_descendant_pre (struct cgroup *pos,struct cgroup *cgroup)@@ -3049,11 +3054,9 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,/* no child, visit my or the closest ancestor's next sibling */ while (pos != cgroup) { - next = list_entry_rcu(pos->sibling.next, struct cgroup, - sibling); -if (&next->sibling != &pos->parent->children) + next =cgroup_next_sibling (pos); +if (next)return next; - pos = pos->parent; }@@ -3068,6 +3071,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre);* Return the rightmost descendant of @pos. If there's no descendant, * @pos is returned. This can be used during pre-order traversal to skip * subtree of @pos. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct rightmost descendant as long as @pos is +* accessible. */ struct cgroup *cgroup_rightmost_descendant (struct cgroup *pos) {@@ -3107,6 +3115,11 @@ static struct cgroup *cgroup_leftmost_descendant(struct cgroup *pos)* * To be used by cgroup_for_each_descendant_post(). Find the next * descendant to visit for post-order traversal of @cgroup's descendants. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct next descendant as long as both @pos +* and @cgroup are accessible and @pos is a descendant of @cgroup. */ struct cgroup *cgroup_next_descendant_post (struct cgroup *pos,struct cgroup *cgroup)@@ -3122,8 +3135,8 @@ struct cgroup *cgroup_next_descendant_post(struct cgroup *pos, }/* 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) + next =cgroup_next_sibling (pos); +if (next)return cgroup_leftmost_descendant (next);/* no sibling left, visit parent */ Signature · 6 lines
1.8.1.4 _______________________________________________ Containers mailing list Containers-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org https://lists.linuxfoundation.org/mailman/listinfo/containers
Serge Hallyn
Acked-byRe: [PATCH 4/5] cgroup: update iterators to use cgroup_next_sibling()
In reply to a message not in the archiveQuoted 12 lines · Tejun Heo
This patch converts
cgroup_for_each_child(), cgroup_next_descendant_pre/post() and thus cgroup_for_each_descendant_pre/post() to usecgroup_next_sibling()instead of manually dereferencing ->sibling.next.The only reason the iterators couldn't allow dropping RCU read lock while iteration is in progress was because they couldn't determine the next sibling safely once RCU read lock is dropped. Using
cgroup_next_sibling()removes that problem and enables all iterators to allow dropping RCU read lock in the middle. Comments are updated accordingly.
Quoted 7 lines
This makes the iterators easier to use and will simplify controllers.
Note that @cgroup argument is renamed to @cgrp in
cgroup_for_each_child()because it conflicts with "struct cgroup" used in the new macro body.Signed-off-by Tejun Heo <[email protected]>
I didn't test, but it looks correct, thanks.
Quoted 122 lines
--- include/linux/cgroup.h | 18 ++++++++++++++---- kernel/cgroup.c | 25 +++++++++++++++++++------ 2 files changed, 33 insertions(+), 10 deletions(-)include/linux/cgroup.h +14
-4@@ -688,9 +688,9 @@ struct cgroup *cgroup_next_sibling(struct cgroup *pos);/** * cgroup_for_each_child - iterate through children of a cgroup * @pos: the cgroup * to use as the loop cursor -* @cgroup: cgroup whose children to walk +* @cgrp: cgroup whose children to walk * -* Walk @cgroup's children. Must be called under rcu_read_lock(). A child +* Walk @cgrp's children. Must be called under rcu_read_lock(). A child * cgroup which hasn't finished ->css_online() or already has finished * ->css_offline() may show up during traversal and it's each subsystem's * responsibility to verify that each @pos is alive. @@ -698,9 +698,15 @@ struct cgroup *cgroup_next_sibling(struct cgroup *pos);* If a subsystem synchronizes against the parent in its ->css_online() and * before starting iterating, a cgroup which finished ->css_online() is * guaranteed to be visible in the future iterations. +* +* It is allowed to temporarily drop RCU read lock during iteration. The +* caller is responsible for ensuring that @pos remains accessible until +* the start of the next iteration by, for example, bumping the css refcnt. */ -#define cgroup_for_each_child (pos, cgroup) \ - list_for_each_entry_rcu(pos, &(cgroup)->children, sibling) +#define cgroup_for_each_child (pos, cgrp) \ + for ((pos) = list_first_or_null_rcu(&(cgrp)->children, \ + struct cgroup, sibling); \ + (pos); (pos) = cgroup_next_sibling((pos)))struct cgroup *cgroup_next_descendant_pre (struct cgroup *pos,struct cgroup *cgroup);@@ -759,6 +765,10 @@ struct cgroup *cgroup_rightmost_descendant(struct cgroup *pos);* Alternatively, a subsystem may choose to use a single global lock to * synchronize ->css_online() and ->css_offline() against tree-walking * operations. +* +* It is allowed to temporarily drop RCU read lock during iteration. The +* caller is responsible for ensuring that @pos remains accessible until +* the start of the next iteration by, for example, bumping the css refcnt. */ #define cgroup_for_each_descendant_pre (pos, cgroup) \ for (pos = cgroup_next_descendant_pre(NULL, (cgroup)); (pos); \kernel/cgroup.c +19
-6@@ -3030,6 +3030,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_sibling);* * To be used by cgroup_for_each_descendant_pre(). Find the next * descendant to visit for pre-order traversal of @cgroup's descendants. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct next descendant as long as both @pos +* and @cgroup are accessible and @pos is a descendant of @cgroup. */ struct cgroup *cgroup_next_descendant_pre (struct cgroup *pos,struct cgroup *cgroup)@@ -3049,11 +3054,9 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,/* no child, visit my or the closest ancestor's next sibling */ while (pos != cgroup) { - next = list_entry_rcu(pos->sibling.next, struct cgroup, - sibling); -if (&next->sibling != &pos->parent->children) + next =cgroup_next_sibling (pos); +if (next)return next; - pos = pos->parent; }@@ -3068,6 +3071,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre);* Return the rightmost descendant of @pos. If there's no descendant, * @pos is returned. This can be used during pre-order traversal to skip * subtree of @pos. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct rightmost descendant as long as @pos is +* accessible. */ struct cgroup *cgroup_rightmost_descendant (struct cgroup *pos) {@@ -3107,6 +3115,11 @@ static struct cgroup *cgroup_leftmost_descendant(struct cgroup *pos)* * To be used by cgroup_for_each_descendant_post(). Find the next * descendant to visit for post-order traversal of @cgroup's descendants. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct next descendant as long as both @pos +* and @cgroup are accessible and @pos is a descendant of @cgroup. */ struct cgroup *cgroup_next_descendant_post (struct cgroup *pos,struct cgroup *cgroup)@@ -3122,8 +3135,8 @@ struct cgroup *cgroup_next_descendant_post(struct cgroup *pos, }/* 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) + next =cgroup_next_sibling (pos); +if (next)return cgroup_leftmost_descendant (next);/* no sibling left, visit parent */ Signature · 6 lines
1.8.1.4 _______________________________________________ Containers mailing list Containers-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org https://lists.linuxfoundation.org/mailman/listinfo/containers
Re: [PATCH 4/5] cgroup: update iterators to use cgroup_next_sibling()
In reply to a message not in the archivekernel/cgroup.c EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre); · line 3081
Quoted 12 lines
kernel/cgroup.c +5
-0@@ -3068,6 +3071,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre);* Return the rightmost descendant of @pos. If there's no descendant, * @pos is returned. This can be used during pre-order traversal to skip * subtree of @pos. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct rightmost descendant as long as @pos is +* accessible. */ struct cgroup *cgroup_rightmost_descendant (struct cgroup *pos) {
Forgot to convert cgroup_rightmost_descendat() to use cgroup_next_sibling()?
do {
last = pos;
/* ->prev isn't RCU safe, walk ->next till the end */
pos = NULL;
list_for_each_entry_rcu(tmp, &last->children, sibling)
pos = tmp;
} while (pos);A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: [PATCH 4/5] cgroup: update iterators to use cgroup_next_sibling()
Quoted 15 lines · Li Zefan
kernel/cgroup.c EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre); · line 3081
Quoted 12 lines
kernel/cgroup.c +5
-0@@ -3068,6 +3071,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre);* Return the rightmost descendant of @pos. If there's no descendant, * @pos is returned. This can be used during pre-order traversal to skip * subtree of @pos. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct rightmost descendant as long as @pos is +* accessible. */ struct cgroup *cgroup_rightmost_descendant (struct cgroup *pos) {Forgot to convert
cgroup_rightmost_descendat()to usecgroup_next_sibling()?
Quoted 7 lines
do {
last = pos;
/* ->prev isn't RCU safe, walk ->next till the end */
pos = NULL;
list_for_each_entry_rcu(tmp, &last->children, sibling)
pos = tmp;
} while (pos);It's always walking from the parent->children with RCU read locked, so it doesn't need to be converted. We can still convert it for consistency and I had that in the patch originally but dropped it as the conversion seemed a bit misleading as it covers a case which can never happen. Hmmm....
Thanks.
Signature · 1 line
tejun
Re: [PATCH 4/5] cgroup: update iterators to use cgroup_next_sibling()
In reply to a message not in the archivekernel/cgroup.c EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre); · line 3081
Quoted 12 lines
kernel/cgroup.c +5
-0@@ -3068,6 +3071,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre);* Return the rightmost descendant of @pos. If there's no descendant, * @pos is returned. This can be used during pre-order traversal to skip * subtree of @pos. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct rightmost descendant as long as @pos is +* accessible. */ struct cgroup *cgroup_rightmost_descendant (struct cgroup *pos) {
Forgot to convert cgroup_rightmost_descendat() to use cgroup_next_sibling()?
do {
last = pos;
/* ->prev isn't RCU safe, walk ->next till the end */
pos = NULL;
list_for_each_entry_rcu(tmp, &last->children, sibling)
pos = tmp;
} while (pos);Michal Hocko
Reviewed-byRe: [PATCH 4/5] cgroup: update iterators to use cgroup_next_sibling()
In reply to a message not in the archiveQuoted 12 lines · Tejun Heo
This patch converts
cgroup_for_each_child(), cgroup_next_descendant_pre/post() and thus cgroup_for_each_descendant_pre/post() to usecgroup_next_sibling()instead of manually dereferencing ->sibling.next.The only reason the iterators couldn't allow dropping RCU read lock while iteration is in progress was because they couldn't determine the next sibling safely once RCU read lock is dropped. Using
cgroup_next_sibling()removes that problem and enables all iterators to allow dropping RCU read lock in the middle. Comments are updated accordingly.
Quoted 7 lines
This makes the iterators easier to use and will simplify controllers.
Note that @cgroup argument is renamed to @cgrp in
cgroup_for_each_child()because it conflicts with "struct cgroup" used in the new macro body.Signed-off-by Tejun Heo <[email protected]>
Looks good to me
Quoted 122 lines
--- include/linux/cgroup.h | 18 ++++++++++++++---- kernel/cgroup.c | 25 +++++++++++++++++++------ 2 files changed, 33 insertions(+), 10 deletions(-)include/linux/cgroup.h +14
-4@@ -688,9 +688,9 @@ struct cgroup *cgroup_next_sibling(struct cgroup *pos);/** * cgroup_for_each_child - iterate through children of a cgroup * @pos: the cgroup * to use as the loop cursor -* @cgroup: cgroup whose children to walk +* @cgrp: cgroup whose children to walk * -* Walk @cgroup's children. Must be called under rcu_read_lock(). A child +* Walk @cgrp's children. Must be called under rcu_read_lock(). A child * cgroup which hasn't finished ->css_online() or already has finished * ->css_offline() may show up during traversal and it's each subsystem's * responsibility to verify that each @pos is alive. @@ -698,9 +698,15 @@ struct cgroup *cgroup_next_sibling(struct cgroup *pos);* If a subsystem synchronizes against the parent in its ->css_online() and * before starting iterating, a cgroup which finished ->css_online() is * guaranteed to be visible in the future iterations. +* +* It is allowed to temporarily drop RCU read lock during iteration. The +* caller is responsible for ensuring that @pos remains accessible until +* the start of the next iteration by, for example, bumping the css refcnt. */ -#define cgroup_for_each_child (pos, cgroup) \ - list_for_each_entry_rcu(pos, &(cgroup)->children, sibling) +#define cgroup_for_each_child (pos, cgrp) \ + for ((pos) = list_first_or_null_rcu(&(cgrp)->children, \ + struct cgroup, sibling); \ + (pos); (pos) = cgroup_next_sibling((pos)))struct cgroup *cgroup_next_descendant_pre (struct cgroup *pos,struct cgroup *cgroup);@@ -759,6 +765,10 @@ struct cgroup *cgroup_rightmost_descendant(struct cgroup *pos);* Alternatively, a subsystem may choose to use a single global lock to * synchronize ->css_online() and ->css_offline() against tree-walking * operations. +* +* It is allowed to temporarily drop RCU read lock during iteration. The +* caller is responsible for ensuring that @pos remains accessible until +* the start of the next iteration by, for example, bumping the css refcnt. */ #define cgroup_for_each_descendant_pre (pos, cgroup) \ for (pos = cgroup_next_descendant_pre(NULL, (cgroup)); (pos); \kernel/cgroup.c +19
-6@@ -3030,6 +3030,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_sibling);* * To be used by cgroup_for_each_descendant_pre(). Find the next * descendant to visit for pre-order traversal of @cgroup's descendants. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct next descendant as long as both @pos +* and @cgroup are accessible and @pos is a descendant of @cgroup. */ struct cgroup *cgroup_next_descendant_pre (struct cgroup *pos,struct cgroup *cgroup)@@ -3049,11 +3054,9 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,/* no child, visit my or the closest ancestor's next sibling */ while (pos != cgroup) { - next = list_entry_rcu(pos->sibling.next, struct cgroup, - sibling); -if (&next->sibling != &pos->parent->children) + next =cgroup_next_sibling (pos); +if (next)return next; - pos = pos->parent; }@@ -3068,6 +3071,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre);* Return the rightmost descendant of @pos. If there's no descendant, * @pos is returned. This can be used during pre-order traversal to skip * subtree of @pos. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct rightmost descendant as long as @pos is +* accessible. */ struct cgroup *cgroup_rightmost_descendant (struct cgroup *pos) {@@ -3107,6 +3115,11 @@ static struct cgroup *cgroup_leftmost_descendant(struct cgroup *pos)* * To be used by cgroup_for_each_descendant_post(). Find the next * descendant to visit for post-order traversal of @cgroup's descendants. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct next descendant as long as both @pos +* and @cgroup are accessible and @pos is a descendant of @cgroup. */ struct cgroup *cgroup_next_descendant_post (struct cgroup *pos,struct cgroup *cgroup)@@ -3122,8 +3135,8 @@ struct cgroup *cgroup_next_descendant_post(struct cgroup *pos, }/* 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) + next =cgroup_next_sibling (pos); +if (next)return cgroup_leftmost_descendant (next);/* no sibling left, visit parent */ Signature · 6 lines
1.8.1.4 -- To unsubscribe from this list: send the line "unsubscribe cgroups" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Signature · 2 lines
Michal Hocko SUSE Labs
PATCH 4/5 cgroup: update iterators to use cgroup_next_sibling()
In reply to a message not in the archiveThis patch converts cgroup_for_each_child(), cgroup_next_descendant_pre/post() and thus cgroup_for_each_descendant_pre/post() to use cgroup_next_sibling() instead of manually dereferencing ->sibling.next.
The only reason the iterators couldn't allow dropping RCU read lock while iteration is in progress was because they couldn't determine the next sibling safely once RCU read lock is dropped. Using cgroup_next_sibling() removes that problem and enables all iterators to allow dropping RCU read lock in the middle. Comments are updated accordingly.
This makes the iterators easier to use and will simplify controllers.
Note that @cgroup argument is renamed to @cgrp in cgroup_for_each_child() because it conflicts with "struct cgroup" used in the new macro body.
--- include/linux/cgroup.h | 18 ++++++++++++++---- kernel/cgroup.c | 25 +++++++++++++++++++------ 2 files changed, 33 insertions(+), 10 deletions(-)
include/linux/cgroup.h +14 -4
@@ -688,9 +688,9 @@ struct cgroup *cgroup_next_sibling(struct cgroup *pos);/** * cgroup_for_each_child - iterate through children of a cgroup * @pos: the cgroup * to use as the loop cursor -* @cgroup: cgroup whose children to walk +* @cgrp: cgroup whose children to walk * -* Walk @cgroup's children. Must be called under rcu_read_lock(). A child +* Walk @cgrp's children. Must be called under rcu_read_lock(). A child * cgroup which hasn't finished ->css_online() or already has finished * ->css_offline() may show up during traversal and it's each subsystem's * responsibility to verify that each @pos is alive.
@@ -698,9 +698,15 @@ struct cgroup *cgroup_next_sibling(struct cgroup *pos);* If a subsystem synchronizes against the parent in its ->css_online() and * before starting iterating, a cgroup which finished ->css_online() is * guaranteed to be visible in the future iterations. +* +* It is allowed to temporarily drop RCU read lock during iteration. The +* caller is responsible for ensuring that @pos remains accessible until +* the start of the next iteration by, for example, bumping the css refcnt. */ -#define cgroup_for_each_child (pos, cgroup) \ - list_for_each_entry_rcu(pos, &(cgroup)->children, sibling) +#define cgroup_for_each_child (pos, cgrp) \ + for ((pos) = list_first_or_null_rcu(&(cgrp)->children, \ + struct cgroup, sibling); \ + (pos); (pos) = cgroup_next_sibling((pos)))struct cgroup *cgroup_next_descendant_pre (struct cgroup *pos,struct cgroup *cgroup);
@@ -759,6 +765,10 @@ struct cgroup *cgroup_rightmost_descendant(struct cgroup *pos);* Alternatively, a subsystem may choose to use a single global lock to * synchronize ->css_online() and ->css_offline() against tree-walking * operations. +* +* It is allowed to temporarily drop RCU read lock during iteration. The +* caller is responsible for ensuring that @pos remains accessible until +* the start of the next iteration by, for example, bumping the css refcnt. */ #define cgroup_for_each_descendant_pre (pos, cgroup) \ for (pos = cgroup_next_descendant_pre(NULL, (cgroup)); (pos); \
kernel/cgroup.c +19 -6
@@ -3030,6 +3030,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_sibling);* * To be used by cgroup_for_each_descendant_pre(). Find the next * descendant to visit for pre-order traversal of @cgroup's descendants. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct next descendant as long as both @pos +* and @cgroup are accessible and @pos is a descendant of @cgroup. */ struct cgroup *cgroup_next_descendant_pre (struct cgroup *pos,struct cgroup *cgroup)
@@ -3049,11 +3054,9 @@ struct cgroup *cgroup_next_descendant_pre(struct cgroup *pos,/* no child, visit my or the closest ancestor's next sibling */ while (pos != cgroup) { - next = list_entry_rcu(pos->sibling.next, struct cgroup, - sibling); -if (&next->sibling != &pos->parent->children) + next =cgroup_next_sibling (pos); +if (next)return next; - pos = pos->parent; }
@@ -3068,6 +3071,11 @@ EXPORT_SYMBOL_GPL(cgroup_next_descendant_pre);* Return the rightmost descendant of @pos. If there's no descendant, * @pos is returned. This can be used during pre-order traversal to skip * subtree of @pos. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct rightmost descendant as long as @pos is +* accessible. */ struct cgroup *cgroup_rightmost_descendant (struct cgroup *pos) {
@@ -3107,6 +3115,11 @@ static struct cgroup *cgroup_leftmost_descendant(struct cgroup *pos)* * To be used by cgroup_for_each_descendant_post(). Find the next * descendant to visit for post-order traversal of @cgroup's descendants. +* +* While this function requires RCU read locking, it doesn't require the +* whole traversal to be contained in a single RCU critical section. This +* function will return the correct next descendant as long as both @pos +* and @cgroup are accessible and @pos is a descendant of @cgroup. */ struct cgroup *cgroup_next_descendant_post (struct cgroup *pos,struct cgroup *cgroup)
@@ -3122,8 +3135,8 @@ struct cgroup *cgroup_next_descendant_post(struct cgroup *pos, }/* 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) + next =cgroup_next_sibling (pos); +if (next)return cgroup_leftmost_descendant (next);/* no sibling left, visit parent */
Signature · 1 line
1.8.1.4
PATCH 5/5 device_cgroup: simplify cgroup tree walk in propagate_exception()
In reply to a message not in the archiveDuring a config change, propagate_exception() needs to traverse the subtree to update config on the subtree. Because such config updates need to allocate memory, it couldn't directly use cgroup_for_each_descendant_pre() which required the whole iteration to be contained in a single RCU read critical section. To work around the limitation, propagate_exception() built a linked list of descendant cgroups while read-locking RCU and then walked the list afterwards, which is safe as the whole iteration is protected by devcgroup_mutex. This works but is cumbersome.
With the recent updates, cgroup iterators now allow dropping RCU read lock while iteration is in progress making this workaround no longer necessary. This patch replaces dev_cgroup->propagate_pending list and get_online_devcg() with direct cgroup_for_each_descendant_pre() walk.
--- security/device_cgroup.c | 56 ++++++++++++++++-------------------------------- 1 file changed, 18 insertions(+), 38 deletions(-)
security/device_cgroup.c +18 -38
@@ -49,8 +49,6 @@ struct dev_cgroup {struct cgroup_subsys_state css;struct list_head exceptions;enum devcg_behavior behavior; -/* temporary list for pending propagation operations */ -struct list_head propagate_pending; };static inline struct dev_cgroup *css_to_devcgroup (struct cgroup_subsys_state *s)
@@ -241,7 +239,6 @@ static struct cgroup_subsys_state *devcgroup_css_alloc(struct cgroup *cgroup)if (!dev_cgroup)return ERR_PTR (-ENOMEM );INIT_LIST_HEAD (&dev_cgroup->exceptions); -INIT_LIST_HEAD (&dev_cgroup->propagate_pending); dev_cgroup->behavior =DEVCG_DEFAULT_NONE ;return &dev_cgroup->css;
@@ -445,34 +442,6 @@ static void revalidate_active_exceptions(struct dev_cgroup *devcg) }/** -* get_online_devcg - walks the cgroup tree and fills a list with the online -* groups -* @root: cgroup used as starting point -* @online: list that will be filled with online groups -* -* Must be called with devcgroup_mutex held. Grabs RCU lock. -* Because devcgroup_mutex is held, no devcg will become online or offline -* during the tree walk (see devcgroup_online, devcgroup_offline) -* A separated list is needed because propagate_behavior() and -* propagate_exception() need to allocate memory and can block. -*/ -static void get_online_devcg (struct cgroup *root,struct list_head *online) -{ -struct cgroup *pos; -struct dev_cgroup *devcg; - -lockdep_assert_held (&devcgroup_mutex); - -rcu_read_lock (); -cgroup_for_each_descendant_pre (pos, root) { - devcg =cgroup_to_devcgroup (pos); -if (is_devcg_online (devcg)) -list_add_tail (&devcg->propagate_pending, online); - } -rcu_read_unlock (); -} - -/** * propagate_exception - propagates a new exception to the children * @devcg_root: device cgroup that added a new exception * @ex: new exception to be propagated
@@ -482,15 +451,24 @@ static void get_online_devcg(struct cgroup *root, struct list_head *online)static int propagate_exception (struct dev_cgroup *devcg_root,struct dev_exception_item *ex) { -struct cgroup *root = devcg_root->css.cgroup; -struct dev_cgroup *devcg, *parent, *tmp; +struct cgroup *root = devcg_root->css.cgroup, *pos;int rc =0 ; -LIST_HEAD (pending); -get_online_devcg (root, &pending); +rcu_read_lock (); -list_for_each_entry_safe (devcg, tmp, &pending, propagate_pending) { - parent =cgroup_to_devcgroup (devcg->css.cgroup->parent); +cgroup_for_each_descendant_pre (pos, root) { +struct dev_cgroup *devcg =cgroup_to_devcgroup (pos); + +/* +* Because devcgroup_mutex is held, no devcg will become +* online or offline during the tree walk (see on/offline +* methods), and online ones are safe to access outside RCU +* read lock without bumping refcnt. +*/ +if (!is_devcg_online (devcg)) +continue ; + +rcu_read_unlock ();/* * in case both root's behavior and devcg is allow, a new
@@ -512,8 +490,10 @@ static int propagate_exception(struct dev_cgroup *devcg_root, }revalidate_active_exceptions (devcg); -list_del_init (&devcg->propagate_pending); +rcu_read_lock (); } + +rcu_read_unlock ();return rc; }
Signature · 1 line
1.8.1.4
A message that is not in the archive (sent off-list or not yet received): 1369101025-28335-6-git-send-email-tj-DgEjT+Ai2ygdnm+yROfE0A@public.gmane.org
Serge Hallyn
Acked-byRe: [PATCH 5/5] device_cgroup: simplify cgroup tree walk in propagate_exception()
Quoted 10 lines · Tejun Heo
During a config change,
propagate_exception()needs to traverse the subtree to update config on the subtree. Because such config updates need to allocate memory, it couldn't directly usecgroup_for_each_descendant_pre()which required the whole iteration to be contained in a single RCU read critical section. To work around the limitation,propagate_exception()built a linked list of descendant cgroups while read-locking RCU and then walked the list afterwards, which is safe as the whole iteration is protected bydevcgroup_mutex. This works but is cumbersome.
Quoted 8 lines
With the recent updates, cgroup iterators now allow dropping RCU read lock while iteration is in progress making this workaround no longer necessary. This patch replaces
dev_cgroup->propagate_pendinglist andget_online_devcg()with directcgroup_for_each_descendant_pre()walk.Signed-off-by Tejun Heo <[email protected]>Cc Aristeu Rozanski <[email protected]>Cc Serge E. Hallyn <serue-r/[email protected]>
Quoted 110 lines
--- security/device_cgroup.c | 56 ++++++++++++++++-------------------------------- 1 file changed, 18 insertions(+), 38 deletions(-)security/device_cgroup.c +18
-38@@ -49,8 +49,6 @@ struct dev_cgroup {struct cgroup_subsys_state css;struct list_head exceptions;enum devcg_behavior behavior; -/* temporary list for pending propagation operations */ -struct list_head propagate_pending; };static inline struct dev_cgroup *css_to_devcgroup (struct cgroup_subsys_state *s)@@ -241,7 +239,6 @@ static struct cgroup_subsys_state *devcgroup_css_alloc(struct cgroup *cgroup)if (!dev_cgroup)return ERR_PTR (-ENOMEM );INIT_LIST_HEAD (&dev_cgroup->exceptions); -INIT_LIST_HEAD (&dev_cgroup->propagate_pending); dev_cgroup->behavior =DEVCG_DEFAULT_NONE ;return &dev_cgroup->css;@@ -445,34 +442,6 @@ static void revalidate_active_exceptions(struct dev_cgroup *devcg) }/** -* get_online_devcg - walks the cgroup tree and fills a list with the online -* groups -* @root: cgroup used as starting point -* @online: list that will be filled with online groups -* -* Must be called with devcgroup_mutex held. Grabs RCU lock. -* Because devcgroup_mutex is held, no devcg will become online or offline -* during the tree walk (see devcgroup_online, devcgroup_offline) -* A separated list is needed because propagate_behavior() and -* propagate_exception() need to allocate memory and can block. -*/ -static void get_online_devcg (struct cgroup *root,struct list_head *online) -{ -struct cgroup *pos; -struct dev_cgroup *devcg; - -lockdep_assert_held (&devcgroup_mutex); - -rcu_read_lock (); -cgroup_for_each_descendant_pre (pos, root) { - devcg =cgroup_to_devcgroup (pos); -if (is_devcg_online (devcg)) -list_add_tail (&devcg->propagate_pending, online); - } -rcu_read_unlock (); -} - -/** * propagate_exception - propagates a new exception to the children * @devcg_root: device cgroup that added a new exception * @ex: new exception to be propagated @@ -482,15 +451,24 @@ static void get_online_devcg(struct cgroup *root, struct list_head *online)static int propagate_exception (struct dev_cgroup *devcg_root,struct dev_exception_item *ex) { -struct cgroup *root = devcg_root->css.cgroup; -struct dev_cgroup *devcg, *parent, *tmp; +struct cgroup *root = devcg_root->css.cgroup, *pos;int rc =0 ; -LIST_HEAD (pending); -get_online_devcg (root, &pending); +rcu_read_lock (); -list_for_each_entry_safe (devcg, tmp, &pending, propagate_pending) { - parent =cgroup_to_devcgroup (devcg->css.cgroup->parent); +cgroup_for_each_descendant_pre (pos, root) { +struct dev_cgroup *devcg =cgroup_to_devcgroup (pos); + +/* +* Because devcgroup_mutex is held, no devcg will become +* online or offline during the tree walk (see on/offline +* methods), and online ones are safe to access outside RCU +* read lock without bumping refcnt. +*/ +if (!is_devcg_online (devcg)) +continue ; + +rcu_read_unlock ();/* * in case both root's behavior and devcg is allow, a new @@ -512,8 +490,10 @@ static int propagate_exception(struct dev_cgroup *devcg_root, }revalidate_active_exceptions (devcg); -list_del_init (&devcg->propagate_pending); +rcu_read_lock (); } + +rcu_read_unlock ();return rc; }Signature · 6 lines
1.8.1.4 _______________________________________________ Containers mailing list Containers-cunTk1MwBs9QetFLy7KEm3xJsTq8ys+cHZ5vskTnxNA@public.gmane.org https://lists.linuxfoundation.org/mailman/listinfo/containers
PATCH 5/5 device_cgroup: simplify cgroup tree walk in propagate_exception()
In reply to a message not in the archiveDuring a config change, propagate_exception() needs to traverse the subtree to update config on the subtree. Because such config updates need to allocate memory, it couldn't directly use cgroup_for_each_descendant_pre() which required the whole iteration to be contained in a single RCU read critical section. To work around the limitation, propagate_exception() built a linked list of descendant cgroups while read-locking RCU and then walked the list afterwards, which is safe as the whole iteration is protected by devcgroup_mutex. This works but is cumbersome.
With the recent updates, cgroup iterators now allow dropping RCU read lock while iteration is in progress making this workaround no longer necessary. This patch replaces dev_cgroup->propagate_pending list and get_online_devcg() with direct cgroup_for_each_descendant_pre() walk.
--- security/device_cgroup.c | 56 ++++++++++++++++-------------------------------- 1 file changed, 18 insertions(+), 38 deletions(-)
security/device_cgroup.c +18 -38
@@ -49,8 +49,6 @@ struct dev_cgroup {struct cgroup_subsys_state css;struct list_head exceptions;enum devcg_behavior behavior; -/* temporary list for pending propagation operations */ -struct list_head propagate_pending; };static inline struct dev_cgroup *css_to_devcgroup (struct cgroup_subsys_state *s)
@@ -241,7 +239,6 @@ static struct cgroup_subsys_state *devcgroup_css_alloc(struct cgroup *cgroup)if (!dev_cgroup)return ERR_PTR (-ENOMEM );INIT_LIST_HEAD (&dev_cgroup->exceptions); -INIT_LIST_HEAD (&dev_cgroup->propagate_pending); dev_cgroup->behavior =DEVCG_DEFAULT_NONE ;return &dev_cgroup->css;
@@ -445,34 +442,6 @@ static void revalidate_active_exceptions(struct dev_cgroup *devcg) }/** -* get_online_devcg - walks the cgroup tree and fills a list with the online -* groups -* @root: cgroup used as starting point -* @online: list that will be filled with online groups -* -* Must be called with devcgroup_mutex held. Grabs RCU lock. -* Because devcgroup_mutex is held, no devcg will become online or offline -* during the tree walk (see devcgroup_online, devcgroup_offline) -* A separated list is needed because propagate_behavior() and -* propagate_exception() need to allocate memory and can block. -*/ -static void get_online_devcg (struct cgroup *root,struct list_head *online) -{ -struct cgroup *pos; -struct dev_cgroup *devcg; - -lockdep_assert_held (&devcgroup_mutex); - -rcu_read_lock (); -cgroup_for_each_descendant_pre (pos, root) { - devcg =cgroup_to_devcgroup (pos); -if (is_devcg_online (devcg)) -list_add_tail (&devcg->propagate_pending, online); - } -rcu_read_unlock (); -} - -/** * propagate_exception - propagates a new exception to the children * @devcg_root: device cgroup that added a new exception * @ex: new exception to be propagated
@@ -482,15 +451,24 @@ static void get_online_devcg(struct cgroup *root, struct list_head *online)static int propagate_exception (struct dev_cgroup *devcg_root,struct dev_exception_item *ex) { -struct cgroup *root = devcg_root->css.cgroup; -struct dev_cgroup *devcg, *parent, *tmp; +struct cgroup *root = devcg_root->css.cgroup, *pos;int rc =0 ; -LIST_HEAD (pending); -get_online_devcg (root, &pending); +rcu_read_lock (); -list_for_each_entry_safe (devcg, tmp, &pending, propagate_pending) { - parent =cgroup_to_devcgroup (devcg->css.cgroup->parent); +cgroup_for_each_descendant_pre (pos, root) { +struct dev_cgroup *devcg =cgroup_to_devcgroup (pos); + +/* +* Because devcgroup_mutex is held, no devcg will become +* online or offline during the tree walk (see on/offline +* methods), and online ones are safe to access outside RCU +* read lock without bumping refcnt. +*/ +if (!is_devcg_online (devcg)) +continue ; + +rcu_read_unlock ();/* * in case both root's behavior and devcg is allow, a new
@@ -512,8 +490,10 @@ static int propagate_exception(struct dev_cgroup *devcg_root, }revalidate_active_exceptions (devcg); -list_del_init (&devcg->propagate_pending); +rcu_read_lock (); } + +rcu_read_unlock ();return rc; }
Signature · 1 line
1.8.1.4
(oops, used Serge's old address, using the new canonical one)
Serge, the original thread can be read from
http://thread.gmane.org/gmane.linux.kernel.containers/26037
Li, the cpuset patchset you posted a couple weeks ago should be able to make use of this, right?
Thanks.
Signature · 1 line
tejun
(oops, used Serge's old address, using the new canonical one)
Serge, the original thread can be read from
http://thread.gmane.org/gmane.linux.kernel.containers/26037
Li, the cpuset patchset you posted a couple weeks ago should be able to make use of this, right?
Thanks.
Signature · 1 line
tejun
Aristeu Rozanski
Acked-byHi Tejun,
Quoted 56 lines · Tejun Heo
Currently all cgroup iterators require the whole traversal to be contained in a single RCU read critical section, which can be too restrictive as there are times when blocking operations are necessary during traversal. This forces controllers to implement specific workarounds in those cases - building separate iteration list, punting actual operations to work items and so on.
This patchset updates cgroup iterators so that they allow dropping RCU read lock while iteration is in progress so that controllers which require sleeping during iteration don't need to implement their own mechanisms.
Dropping RCU read lock during iteration is unsafe because
cgroup->sibling.nextcan't be trusted once RCU read lock is dropped. The sibling list is a RCU list and when a cgroup is removed the next pointer is retained to keep RCU traversal working. If the next sibling is removed while RCU read lock is dropped, the removed current cgroup's next won't be updated and the next sibling may complete its grace period and get freed leaving the next pointer dangling.Working around the problem is relatiely simple. Whether ->sibling.next can be trusted can be trusted can be decided by looking at
CGRP_REMOVED- as cgroup removals are fully serialized, the flag is guaranteed to be visible before the next sibling finishes its grace period. For those cases, each cgroup is assigned a monotonically increasing serial number. Because new cgroups are always appeneded to the children list, it's guaranteed that all children list are sorted in the ascending order of the serial numbers. When the next pointer can't be trusted, the next sibling can be located by walking the parent's children list from the beginning looking for the first cgroup with higher serial number.The above is implemented in
cgroup_next_sibling()and all iterators are updated to use it to find out the next sibling thus allowing droppping RCU read lock while iteration is in progress. This patchset replaces separate iteration list indevice_cgroupwith direct descendant walk and there will be further patches making use of this update.This patchset contains the following five patches.
0001-cgroup-fix-a-subtle-bug-in-descendant-pre-order-walk.patch 0002-cgroup-make-cgroup_is_removed-static.patch 0003-cgroup-add-cgroup-serial_nr-and-implement-cgroup_nex.patch 0004-cgroup-update-iterators-to-use-cgroup_next_sibling.patch 0005-device_cgroup-simplify-cgroup-tree-walk-in-propagate.patch
0001 fixes a subtle iteration bug. Will be applied to for-3.10-fixes.
0002 is a trivial prep patch.
0003 implements
cgroup_next_sibling()which can find out the next sibling regardless of the state of the current cgroup.0004 updates all iterators to use
cgroup_next_sibling().
Quoted 8 lines
0005 replaces iteration list work around in
device_cgroupwith direct iteration.This patchset is on top of cgroup/for-3.11
23958e729e("cgroup.h:
remove some functions that are now gone") and available in the following git branch.
git://git.kernel.org/pub/scm/linux/kernel/git/tj/cgroup.gitreview-interruptible-iter
patchset looks good to me. ran some tests in a kernel with it without problems.
Signature · 1 line
Aristeu