Re: [RFC][PATCH 1/2] CGROUP ID and Hierarchy Code

From: KAMEZAWA Hiroyuki
Date: Thu Nov 27 2008 - 03:01:18 EST

Next message: Rusty Russell: "Re: core_param: call these really, really early."
Previous message: Mathieu Desnoyers: "Re: [PATCH] markers: comment marker_synchronize_unregister() ondata dependency"
In reply to: Daisuke Nishimura: "Re: [RFC][PATCH 1/2] CGROUP ID and Hierarchy Code"
Next in thread: Balbir Singh: "Re: [RFC][PATCH 1/2] CGROUP ID and Hierarchy Code"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

On Thu, 27 Nov 2008 16:46:32 +0900
Daisuke Nishimura <nishimura@xxxxxxxxxxxxxxxxx> wrote:

> On Thu, 27 Nov 2008 16:05:48 +0900, KAMEZAWA Hiroyuki <kamezawa.hiroyu@xxxxxxxxxxxxxx> wrote:
> > Patches for CGROUP ID and Hierarchy Code.
> > (based on mmotm Nov/24...I'll update later.)
> >
> > CGROUP ID is a unique value for each cgroup (struct cgroup)
> > Hierarchy Code is array of CGROUP ID which contains all ID od ancestors.
> > and tries to remove cgroup_lock() to walk tree.
> >
> > This is just an example-level patch but I'm now testing/refleshing this.
> > Works well with memcg's hierarchy relcaim.
> > Any comment is welcome.
> >
> Great work!
>
thanks.

> I've not reviewed these patches in detail yet, I agree to this direction
> to remove cgroup_lock() at hierarcal reclaim.
> Actualy, I was thinking it would be better to manage some array or list
> at mkdir/rmdir.
>
I have to check races in detail before removing RFC ;)

> hmm, but should this ID be implemented in cgroup level, not in memcg level?
>
Yes. 2 reasons.
1. When I added cgroup-ID to swap_cgroup, some people said "please do in cgroup
generic layer".
2. bio-cgroup people will use this.

Thanks,
-Kame

>
> Thanks,
> Daisuke Nishimura.
>
> > -Kame
> >
> > ==
> > A toy patch for Cgroup ID and hierarchy code.
> >
> > This patch tries to assing a ID to each cgroup. Attach unique ID to each
> > cgroup and provides following functions.
> >
> > - cgroup_lookup(id)
> > returns cgroup of id.
> > - cgroup_get_next(id, root, foundid)
> > returns the next cgroup under "root" by scanning bitmap (not by tree-walk)
> > - cgroup_is_ancestor(cgroup, root)
> > returns true if "root" is ancestor of cgroup.
> >
> > There is several reasons to develop this.
> >
> > - While trying to implement hierarchy in memory cgroup, we had to
> > implement "walk under hierarchy" code.
> > Now it's consists of cgroup_lock and tree up-down code.
> > But taking "cgroup_lock" in walking tree can cause deadlocks.
> > cgroup_lock() is too big. Easier way is helpful.
> >
> > - SwapCgroup uses array of "pointer" to record the owner of swaps.
> > By ID, we can reduce this to "short" or "int". This means ID is
> > useful for reducing space consumption by pointer if the access cost
> > is not problem.
> > (I hear bio-cgroup will use the same kind of...)
> >
> > Example) OOM-Killer under hierarchy.
> > do {
> > rcu_read_lock();
> > next = cgroup_get_next(id, root, nextid);
> > /* check sanity of next here */
> > /* increment refcnt to "next" */
> > rcu_read_unlock();
> > if (!next)
> > break;
> > cgroup_scan_tasks(select_bad_process);
> > } while (1);
> >
> >
> > Characteristics:
> > - Each cgroup get new ID when created.
> > - cgroup ID contains "ID" and "Depth in tree" and hierarchy code.
> > - hierarchy code is array of IDs of ancestors.
> >
> > Consideration:
> > - gang lookup if necessary.
> > - I'd like to use "(unsigned)short" to cgroup_id for saving space...
> > - MAX_DEPTH is bad ?
> >
> > Signed-off-by: KAMEZAWA Hiroyuki <kamezawa.hiroyu@xxxxxxxxxxxxxx>
> >
> > include/linux/cgroup.h | 42 +++++++++++
> > include/linux/idr.h | 1
> > kernel/cgroup.c | 180 ++++++++++++++++++++++++++++++++++++++++++++++++-
> > lib/idr.c | 46 ++++++++++++
> > 4 files changed, 266 insertions(+), 3 deletions(-)
> >
> > Index: mmotm-2.6.28-Nov24/include/linux/cgroup.h
> > ===================================================================
> > --- mmotm-2.6.28-Nov24.orig/include/linux/cgroup.h
> > +++ mmotm-2.6.28-Nov24/include/linux/cgroup.h
> > @@ -61,6 +61,20 @@ struct cgroup_subsys_state {
> > unsigned long flags;
> > };
> >
> > +/*
> > + * Cgroup ID for *internal* identification and lookup. For user-land,"path"
> > + * of cgroup works well.
> > + */
> > +#define MAX_CGROUP_DEPTH (10)
> > +struct cgroup_id {
> > + struct cgroup *myself;
> > + unsigned int id;
> > + atomic_t refcnt;
> > + unsigned int depth;
> > + unsigned int hierarchy_code[MAX_CGROUP_DEPTH];
> > + struct list_head list;
> > +};
> > +
> > /* bits in struct cgroup_subsys_state flags field */
> > enum {
> > CSS_ROOT, /* This CSS is the root of the subsystem */
> > @@ -145,6 +159,9 @@ struct cgroup {
> > int pids_use_count;
> > /* Length of the current tasks_pids array */
> > int pids_length;
> > +
> > + /* Cgroup ID */
> > + struct cgroup_id *id;
> > };
> >
> > /* A css_set is a structure holding pointers to a set of
> > @@ -393,6 +410,31 @@ void cgroup_iter_end(struct cgroup *cgrp
> > int cgroup_scan_tasks(struct cgroup_scanner *scan);
> > int cgroup_attach_task(struct cgroup *, struct task_struct *);
> >
> > +/*
> > + * For supporting cgroup lookup and hierarchy management.
> > + * Giving Flat view of cgroup hierarchy rather than tree.
> > + */
> > +/* An interface for usual lookup */
> > +struct cgroup *cgroup_lookup(int id);
> > +/* get next cgroup under tree (for scan) */
> > +struct cgroup *cgroup_get_next(int id, struct cgroup *root, int *foundid);
> > +
> > +static inline bool
> > +cgroup_is_ancestor(struct cgroup *cur, struct cgroup *root)
> > +{
> > + struct cgroup_id *curid = cur->id;
> > + struct cgroup_id *rootid = root->id;
> > +
> > + return (curid->hierarchy_code[rootid->depth] = rootid->id);
> > +}
> > +
> > +static inline int cgroup_myid(struct cgroup *cgrp)
> > +{
> > + return cgrp->id->id;
> > +}
> > +
> > +/* TODO: gang lookup should be */
> > +
> > #else /* !CONFIG_CGROUPS */
> >
> > static inline int cgroup_init_early(void) { return 0; }
> > Index: mmotm-2.6.28-Nov24/kernel/cgroup.c
> > ===================================================================
> > --- mmotm-2.6.28-Nov24.orig/kernel/cgroup.c
> > +++ mmotm-2.6.28-Nov24/kernel/cgroup.c
> > @@ -46,7 +46,7 @@
> > #include <linux/cgroupstats.h>
> > #include <linux/hash.h>
> > #include <linux/namei.h>
> > -
> > +#include <linux/idr.h>
> > #include <asm/atomic.h>
> >
> > static DEFINE_MUTEX(cgroup_mutex);
> > @@ -547,6 +547,162 @@ void cgroup_unlock(void)
> > mutex_unlock(&cgroup_mutex);
> > }
> >
> > +
> > +/*
> > + * Cgroup ID and lookup functions.
> > + * cgid->myself pointer is safe under rcu_read_lock() because d_put() of
> > + * cgroup, which finally frees cgroup pointer, uses rcu_synchronize().
> > + */
> > +
> > +static DEFINE_IDR(cgroup_idr);
> > +static DEFINE_SPINLOCK(cgroup_idr_lock);
> > +
> > +static int cgroup_prepare_id(struct cgroup *parent, struct cgroup_id **id)
> > +{
> > + struct cgroup_id *newid;
> > + int myid, error;
> > +
> > + /* check depth */
> > + if (parent && parent->id->depth + 1 >= MAX_CGROUP_DEPTH)
> > + return -ENOSPC;
> > + newid = kzalloc(sizeof(*newid), GFP_KERNEL);
> > + if (!newid)
> > + return -ENOMEM;
> > + /* get id */
> > + if (unlikely(!idr_pre_get(&cgroup_idr, GFP_KERNEL))) {
> > + error = -ENOMEM;
> > + goto err_out;
> > + }
> > + spin_lock_irq(&cgroup_idr_lock);
> > + error = idr_get_new(&cgroup_idr, newid, &myid);
> > + spin_unlock_irq(&cgroup_idr_lock);
> > + if (error)
> > + goto err_out;
> > +
> > + newid->id = myid;
> > + atomic_set(&newid->refcnt, 1);
> > + INIT_LIST_HEAD(&newid->list);
> > + *id = newid;
> > + return 0;
> > +err_out:
> > + kfree(newid);
> > + return error;
> > +}
> > +
> > +static void cgroup_id_put(struct cgroup_id *cgid)
> > +{
> > + unsigned long flags;
> > +
> > + if (atomic_dec_and_test(&cgid->refcnt)) {
> > + spin_lock_irqsave(&cgroup_idr_lock, flags);
> > + idr_remove(&cgroup_idr, cgid->id);
> > + spin_unlock_irqrestore(&cgroup_idr_lock, flags);
> > + kfree(cgid);
> > + }
> > +}
> > +
> > +static void cgroup_id_attach(struct cgroup_id *cgid,
> > + struct cgroup *cg, struct cgroup *parent)
> > +{
> > + if (parent) {
> > + struct cgroup_id *parent_id = parent->id;
> > + int i;
> > +
> > + cgid->depth = parent_id->depth + 1;
> > + /* Inherit hierarchy code from parent */
> > + for (i = 0; i < cgid->depth; i++) {
> > + cgid->hierarchy_code[i] =
> > + parent_id->hierarchy_code[i];
> > + cgid->hierarchy_code[cgid->depth] = cgid->id;
> > + }
> > + } else {
> > + cgid->depth = 0;
> > + cgid->hierarchy_code[0] = cgid->id;
> > + }
> > + rcu_assign_pointer(cgid->myself, cg);
> > + cg->id = cgid;
> > +
> > + return;
> > +}
> > +
> > +static void cgroup_id_detach(struct cgroup *cg)
> > +{
> > + struct cgroup_id *id = cg->id;
> > +
> > + rcu_assign_pointer(id->myself, NULL);
> > + cgroup_id_put(id);
> > +}
> > +
> > +/**
> > + * cgroup_lookup - lookup cgroup by id
> > + * @id: the id of cgroup to be looked up
> > + *
> > + * Retruns pointer to cgroup if there is vald cgroup with id, NULL if not.
> > + * Should be called under rcu_read_lock() or cgroup_lock().
> > + */
> > +
> > +struct cgroup *cgroup_lookup(int id)
> > +{
> > + struct cgroup *cgrp;
> > + struct cgroup_id *cgid;
> > +
> > + rcu_read_lock();
> > + cgid = idr_find(&cgroup_idr, id);
> > + rcu_read_unlock();
> > +
> > + if (unlikely(!cgid))
> > + return NULL;
> > +
> > + cgrp = rcu_dereference(cgid->myself);
> > + if (unlikely(!cgrp || test_bit(CGRP_REMOVED, &cgrp->flags)))
> > + return NULL;
> > +
> > + return cgrp;
> > +}
> > +
> > +/**
> > + * cgroup_get_next - lookup next cgroup under specified hierarchy.
> > + * @id: current position of iteration.
> > + * @root: search tree under this. .
> > + * @foundid: position of found object.
> > + *
> > + * Search next cgroup under the specified hierarchy. If "cur" is NULL,
> > + * start from root cgroup. Called under rcu_read_lock() or cgroup_lock()
> > + * is necessary (to access a found cgroup.).
> > + */
> > +struct cgroup *cgroup_get_next(int id, struct cgroup *root, int *foundid)
> > +{
> > + struct cgroup *ret = NULL;
> > + struct cgroup_id *tmp, *rootid;
> > + int tmpid, depth, targetid;
> > + unsigned long flags;
> > +
> > + rootid = root->id;
> > + depth = rootid->depth;
> > + targetid = rootid->id;
> > + tmpid = id;
> > +
> > + do {
> > + /* scan next entry from bitmap(tree) */
> > + spin_lock_irqsave(&cgroup_idr_lock, flags);
> > + tmp = idr_get_next(&cgroup_idr, &tmpid);
> > + spin_unlock_irqrestore(&cgroup_idr_lock, flags);
> > +
> > + if (tmp) {
> > + ret = rcu_dereference(tmp->myself);
> > + /* Sanity check and check hierarchy */
> > + if (ret && !test_bit(CGRP_REMOVED, &ret->flags)
> > + && tmp->hierarchy_code[depth] == targetid)
> > + break;
> > + tmpid = tmpid + 1;
> > + } else
> > + tmpid = 0;
> > + } while (1);
> > +
> > + *foundid = tmpid;
> > + return ret;
> > +}
> > +
> > /*
> > * A couple of forward declarations required, due to cyclic reference loop:
> > * cgroup_mkdir -> cgroup_create -> cgroup_populate_dir ->
> > @@ -991,6 +1147,7 @@ static int cgroup_get_sb(struct file_sys
> > /* New superblock */
> > struct cgroup *cgrp = &root->top_cgroup;
> > struct inode *inode;
> > + struct cgroup_id *newid;
> > int i;
> >
> > BUG_ON(sb->s_root != NULL);
> > @@ -998,6 +1155,11 @@ static int cgroup_get_sb(struct file_sys
> > ret = cgroup_get_rootdir(sb);
> > if (ret)
> > goto drop_new_super;
> > +
> > + ret = cgroup_prepare_id(NULL, &newid);
> > + if (ret)
> > + goto drop_new_super;
> > +
> > inode = sb->s_root->d_inode;
> >
> > mutex_lock(&inode->i_mutex);
> > @@ -1062,7 +1224,7 @@ static int cgroup_get_sb(struct file_sys
> > BUG_ON(!list_empty(&cgrp->sibling));
> > BUG_ON(!list_empty(&cgrp->children));
> > BUG_ON(root->number_of_cgroups != 1);
> > -
> > + cgroup_id_attach(newid, cgrp, NULL);
> > cgroup_populate_dir(cgrp);
> > mutex_unlock(&inode->i_mutex);
> > mutex_unlock(&cgroup_mutex);
> > @@ -1997,6 +2159,7 @@ int cgroup_scan_tasks(struct cgroup_scan
> > return 0;
> > }
> >
> > +
> > /*
> > * Stuff for reading the 'tasks' file.
> > *
> > @@ -2349,11 +2512,18 @@ static long cgroup_create(struct cgroup
> > int err = 0;
> > struct cgroup_subsys *ss;
> > struct super_block *sb = root->sb;
> > + struct cgroup_id *cgid = NULL;
> >
> > cgrp = kzalloc(sizeof(*cgrp), GFP_KERNEL);
> > if (!cgrp)
> > return -ENOMEM;
> >
> > + err = cgroup_prepare_id(parent, &cgid);
> > + if (err) {
> > + kfree(cgrp);
> > + return err;
> > + }
> > +
> > /* Grab a reference on the superblock so the hierarchy doesn't
> > * get deleted on unmount if there are child cgroups. This
> > * can be done outside cgroup_mutex, since the sb can't
> > @@ -2394,6 +2564,8 @@ static long cgroup_create(struct cgroup
> > err = cgroup_populate_dir(cgrp);
> > /* If err < 0, we have a half-filled directory - oh well ;) */
> >
> > + cgroup_id_attach(cgid, cgrp, parent);
> > +
> > mutex_unlock(&cgroup_mutex);
> > mutex_unlock(&cgrp->dentry->d_inode->i_mutex);
> >
> > @@ -2415,7 +2587,7 @@ static long cgroup_create(struct cgroup
> >
> > /* Release the reference count that we took on the superblock */
> > deactivate_super(sb);
> > -
> > + cgroup_id_put(cgid);
> > kfree(cgrp);
> > return err;
> > }
> > @@ -2494,6 +2666,8 @@ static int cgroup_rmdir(struct inode *un
> > return -EBUSY;
> > }
> >
> > + cgroup_id_detach(cgrp);
> > +
> > spin_lock(&release_list_lock);
> > set_bit(CGRP_REMOVED, &cgrp->flags);
> > if (!list_empty(&cgrp->release_list))
> > Index: mmotm-2.6.28-Nov24/include/linux/idr.h
> > ===================================================================
> > --- mmotm-2.6.28-Nov24.orig/include/linux/idr.h
> > +++ mmotm-2.6.28-Nov24/include/linux/idr.h
> > @@ -106,6 +106,7 @@ int idr_get_new(struct idr *idp, void *p
> > int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);
> > int idr_for_each(struct idr *idp,
> > int (*fn)(int id, void *p, void *data), void *data);
> > +void *idr_get_next(struct idr *idp, int *nextid);
> > void *idr_replace(struct idr *idp, void *ptr, int id);
> > void idr_remove(struct idr *idp, int id);
> > void idr_remove_all(struct idr *idp);
> > Index: mmotm-2.6.28-Nov24/lib/idr.c
> > ===================================================================
> > --- mmotm-2.6.28-Nov24.orig/lib/idr.c
> > +++ mmotm-2.6.28-Nov24/lib/idr.c
> > @@ -573,6 +573,52 @@ int idr_for_each(struct idr *idp,
> > EXPORT_SYMBOL(idr_for_each);
> >
> > /**
> > + * idr_get_next - lookup next opbject of id to given id.
> > + * @idp: idr handle
> > + * @id: pointer to lookup key
> > + *
> > + * Retruns pointer to registered object with id, which is next number to
> > + * given id.
> > + */
> > +
> > +void *idr_get_next(struct idr *idp, int *nextidp)
> > +{
> > + struct idr_layer *p, *pa[MAX_LEVEL];
> > + struct idr_layer **paa = &pa[0];
> > + int id = *nextidp;
> > + int n, max;
> > +
> > + /* find first ent */
> > + n = idp->layers * IDR_BITS;
> > + max = 1 << n;
> > + p = rcu_dereference(idp->top);
> > + if (!p)
> > + return NULL;
> > +
> > + while (id < max) {
> > + while (n > 0 && p) {
> > + n -= IDR_BITS;
> > + *paa++ = p;
> > + p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]);
> > + }
> > +
> > + if (p) {
> > + *nextidp = id;
> > + return p;
> > + }
> > +
> > + id += 1 << n;
> > + while (n < fls(id)) {
> > + n += IDR_BITS;
> > + p = *--paa;
> > + }
> > + }
> > + return NULL;
> > +}
> > +
> > +
> > +
> > +/**
> > * idr_replace - replace pointer for given id
> > * @idp: idr handle
> > * @ptr: pointer you want associated with the id
> >
>

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Next message: Rusty Russell: "Re: core_param: call these really, really early."
Previous message: Mathieu Desnoyers: "Re: [PATCH] markers: comment marker_synchronize_unregister() ondata dependency"
In reply to: Daisuke Nishimura: "Re: [RFC][PATCH 1/2] CGROUP ID and Hierarchy Code"
Next in thread: Balbir Singh: "Re: [RFC][PATCH 1/2] CGROUP ID and Hierarchy Code"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]