[2/3] Re: CpuSet on PAGG (Re: PAGG in Open Source projects?)

[Kaigai Kohei <kaigai@xxxxxxxxxxxxx>]

[2/3] linux-2.6.11-rc2-mm1-pagg_on_RCU
  When we call pagg_get(), we must hold the task->pagg_sem read-semaphore.
  This make it difficult to refere the PAGG object in the interruption
  context or under the any types of spinlock.
  This patch make it possible to refere the PAGG object without any locking.
  (CpuSet-patch needs lockless references.)

Notice:
- task_struct->pagg_sem was replaced by pagg_lock (spinlock_t).
- We must call pagg_get() under the rcu_read_lock(), and the existance of
  the returned PAGG object is guaranteed until rcu_read_unlock().
- We must call pagg_alloc() and pagg_free() under the 
spin_lock(&task->pagg_lock)
  to make sure the processing serialization.

--
Linux Promotion Center, NEC
KaiGai Kohei <kaigai@xxxxxxxxxxxxx>


diff -rpNU3 linux-2.6.11-rc2-mm1.pagg/include/linux/pagg.h 
linux-2.6.11-rc2-mm1.pagg.rcu/include/linux/pagg.h
--- linux-2.6.11-rc2-mm1.pagg/include/linux/pagg.h      2005-01-27 
17:02:10.000000000 +0900
+++ linux-2.6.11-rc2-mm1.pagg.rcu/include/linux/pagg.h  2005-01-27 
17:09:40.000000000 +0900
@@ -44,6 +44,7 @@
 #define _LINUX_PAGG_H

 #include <linux/sched.h>
+#include <linux/rcupdate.h>

 #ifdef CONFIG_PAGG

@@ -57,8 +58,8 @@
  */
 #define INIT_PAGG_LIST(_l)                                             \
 do {                                                                   \
-       INIT_LIST_HEAD(&(_l)->pagg_list);                                       
 \
-       init_rwsem(&(_l)->pagg_sem);                                            
 \
+       INIT_LIST_HEAD(&(_l)->pagg_list);                                \
+       spin_lock_init(&(_l)->pagg_lock);                                \
 } while(0)

@@ -74,9 +75,10 @@ do {                                                         
        \
  *     entry:  List pointers
  */
 struct pagg {
-       struct pagg_hook        *hook;
-       void            *data;
-       struct list_head        entry;
+       struct pagg_hook        *hook;
+       void                    *data;
+       struct list_head        entry;
+       struct rcu_head         rhead;
 };

 /*
@@ -147,52 +149,10 @@ extern struct pagg *pagg_alloc(struct ta
 extern void pagg_free(struct pagg *pagg);
 extern int pagg_hook_register(struct pagg_hook *pt_new);
 extern int pagg_hook_unregister(struct pagg_hook *pt_old);
-extern int __pagg_attach(struct task_struct *to_task,
+extern int pagg_attach(struct task_struct *to_task,
                         struct task_struct *from_task);
-extern void __pagg_detach(struct task_struct *task);
-extern int __pagg_exec(struct task_struct *task);
-
-/**
- * pagg_attach - child inherits attachment to pagg containers of its parent
- * @child: child task - to inherit
- * @parent: parenet task - child inherits pagg containers from this parent
- *
- * function used when a child process must inherit attachment to pagg
- * containers from the parent.  Return code is propagated as a fork fail.
- *
- */
-static inline int pagg_attach(struct task_struct *child,
-                             struct task_struct *parent)
-{
-       INIT_PAGG_LIST(child);
-       if (!list_empty(&parent->pagg_list))
-               return __pagg_attach(child, parent);
-
-       return 0;
-}
-
-
-/**
- * pagg_detach - Detach a process from a pagg container it is a member of
- * @task: The task the pagg will be detached from
- *
- */
-static inline void pagg_detach(struct task_struct *task)
-{
-       if (!list_empty(&task->pagg_list))
-               __pagg_detach(task);
-}
-
-/**
- * pagg_exec - Used when a process exec's
- * @task: The process doing the exec
- *
- */
-static inline void pagg_exec(struct task_struct *task)
-{
-       if (!list_empty(&task->pagg_list))
-               __pagg_exec(task);
-}
+extern void pagg_detach(struct task_struct *task);
+extern int pagg_exec(struct task_struct *task);

 /**
  * INIT_TASK_PAGG - Used in INIT_TASK to set the head and sem of pagg_list
@@ -204,7 +164,7 @@ static inline void pagg_exec(struct task
  */
 #define INIT_TASK_PAGG(tsk) \
        .pagg_list = LIST_HEAD_INIT(tsk.pagg_list),     \
-       .pagg_sem  = __RWSEM_INITIALIZER(tsk.pagg_sem),
+       .pagg_lock = SPIN_LOCK_UNLOCKED,

 #else  /* CONFIG_PAGG */

diff -rpNU3 linux-2.6.11-rc2-mm1.pagg/include/linux/sched.h 
linux-2.6.11-rc2-mm1.pagg.rcu/include/linux/sched.h
--- linux-2.6.11-rc2-mm1.pagg/include/linux/sched.h     2005-01-27 
17:02:10.000000000 +0900
+++ linux-2.6.11-rc2-mm1.pagg.rcu/include/linux/sched.h 2005-01-27 
17:08:46.000000000 +0900
@@ -732,7 +732,7 @@ struct task_struct {
 #ifdef CONFIG_PAGG
 /* List of pagg (process aggregate) attachments */
        struct list_head pagg_list;
-       struct rw_semaphore pagg_sem;
+       spinlock_t pagg_lock;
 #endif

        struct list_head private_pages; /* per-process private pages */
diff -rpNU3 linux-2.6.11-rc2-mm1.pagg/kernel/pagg.c 
linux-2.6.11-rc2-mm1.pagg.rcu/kernel/pagg.c
--- linux-2.6.11-rc2-mm1.pagg/kernel/pagg.c     2005-01-27 17:02:10.000000000 
+0900
+++ linux-2.6.11-rc2-mm1.pagg.rcu/kernel/pagg.c 2005-01-27 17:35:53.000000000 
+0900
@@ -45,16 +45,15 @@ static DECLARE_RWSEM(pagg_hook_list_sem)
  * a pointer to the pagg struct that matches the search
  * key.  If the key is not found, the function will return NULL.
  *
- * The caller should hold at least a read lock on the pagg_list
- * for task using down_read(&task->pagg_list.sem).
- *
+ * The caller must be under the rcu_read_lock(), and the existance
+ * of the object which is returned is guaranteed by rcu_read_unlock().
  */
 struct pagg *
 pagg_get(struct task_struct *task, char *key)
 {
        struct pagg *pagg;

-       list_for_each_entry(pagg, &task->pagg_list, entry) {
+       list_for_each_entry_rcu(pagg, &task->pagg_list, entry) {
                if (!strcmp(pagg->hook->name,key))
                        return pagg;
        }
@@ -74,24 +73,36 @@ pagg_get(struct task_struct *task, char
  * The caller for this function should hold at least a read lock on the
  * pagg_hook_list_sem - or ensure that the pagg hook entry cannot be
  * removed. If this function was called from the pagg module (usually the
- * case), then the caller need not hold this lock. The caller should hold
- * a write lock on for the tasks pagg_sem.  This can be locked using
- * down_write(&task->pagg_sem)
+ * case), then the caller need not hold this lock. The caller must hold
+ * a spin lock on for the tasks pagg_lock.  This can be locked using
+ * spin_lock(&task->pagg_lock)
  *
  */
-struct pagg *
-pagg_alloc(struct task_struct *task, struct pagg_hook *pagg_hook)
+static struct pagg *
+__pagg_alloc(struct task_struct *task, struct pagg_hook *pagg_hook)
 {
        struct pagg *pagg;

        pagg = kmalloc(sizeof(struct pagg), GFP_KERNEL);
        if (!pagg)
                return NULL;
-
        pagg->hook = pagg_hook;
        pagg->data = NULL;
+       INIT_LIST_HEAD(&pagg->entry);
        atomic_inc(&pagg_hook->refcnt);  /* Increase hook's reference count */
-       list_add_tail(&pagg->entry, &task->pagg_list);
+
+       return pagg;
+}
+
+struct pagg *
+pagg_alloc(struct task_struct *task, struct pagg_hook *pagg_hook)
+{
+       struct pagg *pagg;
+
+       pagg = __pagg_alloc(task, pagg_hook);
+       if (!pagg)
+               return NULL;
+       list_add_tail_rcu(&pagg->entry, &task->pagg_list);
        return pagg;
 }

@@ -100,24 +111,37 @@ pagg_alloc(struct task_struct *task, str
  * pagg_free - Delete pagg from the list and free its memory
  * @pagg: The pagg to free
  *
- * This function will ensure the pagg is deleted form
+ * This function will ensure the pagg is deleted from
  * the list of pagg entries for the task. Finally, the memory for the
  * pagg is discarded.
  *
- * The caller of this function should hold a write lock on the pagg_sem
- * for the task. This can be locked using down_write(&task->pagg_sem).
+ * The caller of this function must hold a spin lock on the pagg_list
+ * for the task. This can be locked using spin_lock(&task->pagg_list).
  *
  * Prior to calling pagg_free, the pagg should have been detached from the
  * pagg container represented by this pagg.  That is usually done using
  * p->hook->detach(task, pagg);
  *
  */
+static void
+rcu_pagg_free(struct rcu_head *rhead)
+{
+       struct pagg *pg = container_of(rhead, struct pagg, rhead);
+       kfree(pg);
+}
+
+static void
+__pagg_free(struct pagg *pagg)
+{
+       atomic_dec(&pagg->hook->refcnt); /* decr the reference count on the 
hook */
+       call_rcu(&pagg->rhead, rcu_pagg_free);
+}
+
 void
 pagg_free(struct pagg *pagg)
 {
-       atomic_dec(&pagg->hook->refcnt); /* decr the reference count on the 
hook */
-       list_del(&pagg->entry);
-       kfree(pagg);
+       list_del_rcu(&pagg->entry);
+       __pagg_free(pagg);
 }


@@ -181,13 +205,20 @@ remove_client_paggs_from_all_tasks(struc

                        get_task_struct(p);
                        read_unlock(&tasklist_lock);
-                       down_write(&p->pagg_sem);
+
+                       rcu_read_lock();
+                       spin_lock(&p->pagg_lock);
                        paggp = pagg_get(p, php->name);
                        if (paggp != NULL) {
+                               list_del_rcu(&paggp->entry);
+                               spin_unlock(&p->pagg_lock);
                                (void)php->detach(p, paggp);
-                               pagg_free(paggp);
+                               __pagg_free(paggp);
+                       } else {
+                               spin_unlock(&p->pagg_lock);
                        }
-                       up_write(&p->pagg_sem);
+                       rcu_read_unlock();
+
                        read_lock(&tasklist_lock);

                        /* If a PAGG got removed from the list while we're 
going through
@@ -275,21 +306,24 @@ pagg_hook_register(struct pagg_hook *pag

                        get_task_struct(p);
                        read_unlock(&tasklist_lock);
-                       down_write(&p->pagg_sem);
+                       
+                       spin_lock(&p->pagg_lock);
                        paggp = pagg_get(p, pagg_hook_new->name);
                        if (!paggp && !(p->flags & PF_EXITING)) {
-                               paggp = pagg_alloc(p, pagg_hook_new);
+                               paggp = __pagg_alloc(p, pagg_hook_new);
                                if (paggp != NULL) {
                                        init_result = pagg_hook_new->init(p, 
paggp);
-
-                                       /* Success, but init function pointer 
doesn't want grouping */
-                                       if (init_result > 0)
-                                               pagg_free(paggp);
-                               }
-                               else
+                                       if (init_result == 0) {
+                                               list_add_tail_rcu(&paggp->entry, 
&p->pagg_list);
+                                       } else {
+                                               __pagg_free(paggp);
+                                       }
+                               } else {
                                        init_result = -ENOMEM;
+                               }
                        }
-                       up_write(&p->pagg_sem);
+                       spin_unlock(&p->pagg_lock);
+
                        read_lock(&tasklist_lock);
                        /* Like in remove_client_paggs_from_all_tasks, if the 
task
                         * disappeared on us while we were going through the
@@ -388,41 +422,46 @@ pagg_hook_unregister(struct pagg_hook *p
  * The "from" argument is the parent task.  The "to" argument is the child
  * task.
  *
- * See the attach decription in linux/include/linux/pagg.h for details on
- * how to handle return codes from the attach function pointer.
- *
+ * The child task must not be referenced yet.
  */
 int
-__pagg_attach(struct task_struct *to_task, struct task_struct *from_task)
+pagg_attach(struct task_struct *to_task, struct task_struct *from_task)
 {
        struct pagg *from_pagg;
        int ret;

-       /* lock the parents pagg_list we are copying from */
-       down_read(&from_task->pagg_sem); /* read lock the pagg list */
+       INIT_PAGG_LIST(to_task);
+
+       rcu_read_lock();

+       if (list_empty(&from_task->pagg_list)) {
+               rcu_read_unlock();
+               return 0;
+       }
+
+       /* lock the parents pagg_list we are copying from */
        list_for_each_entry(from_pagg, &from_task->pagg_list, entry) {
                struct pagg *to_pagg = NULL;

-               to_pagg = pagg_alloc(to_task, from_pagg->hook);
+               to_pagg = __pagg_alloc(to_task, from_pagg->hook);
                if (!to_pagg) {
                        ret=-ENOMEM;
                        goto error_return;
                }
                ret = to_pagg->hook->attach(to_task, to_pagg, from_pagg->data);
-
-               if (ret < 0) {
+               if (likely(ret==0)) {
+                       /* Success, and PAGG will be chained */
+                       list_add_tail_rcu(&to_pagg->entry, &to_task->pagg_list);
+               } else if (ret < 0) {
                        /* Propagates to copy_process as a fork failure */
                        goto error_return;
-               }
-               else if (ret > 0) {
+               } else {
                        /* Success, but attach function pointer doesn't want 
grouping */
-                       pagg_free(to_pagg);
+                       __pagg_free(to_pagg);
                }
        }

-       up_read(&from_task->pagg_sem); /* unlock the pagg list */
-
+       rcu_read_unlock();
        return 0;                                       /* success */

   error_return:
@@ -430,8 +469,8 @@ __pagg_attach(struct task_struct *to_tas
         * Clean up all the pagg attachments made on behalf of the new
         * task.  Set new task pagg ptr to NULL for return.
         */
-       up_read(&from_task->pagg_sem); /* unlock the pagg list */
-       __pagg_detach(to_task);
+       rcu_read_unlock();
+       pagg_detach(to_task);
        return ret;                             /* failure */
 }

@@ -443,21 +482,28 @@ __pagg_attach(struct task_struct *to_tas
  *
  */
 void
-__pagg_detach(struct task_struct *task)
+pagg_detach(struct task_struct *task)
 {
        struct pagg *pagg;
        struct pagg *paggtmp;

-       /* Remove ref. to paggs from task immediately */
-       down_write(&task->pagg_sem); /* write lock pagg list */
+       rcu_read_lock();
+       if (list_empty(&task->pagg_list))
+               goto out;

+       spin_lock(&task->pagg_lock);
        list_for_each_entry_safe(pagg, paggtmp, &task->pagg_list, entry) {
-               pagg->hook->detach(task, pagg);
-               pagg_free(pagg);
-       }
+               list_del_rcu(&pagg->entry);
+               spin_unlock(&task->pagg_lock);

-       up_write(&task->pagg_sem); /* write unlock the pagg list */
+               pagg->hook->detach(task, pagg);
+               __pagg_free(pagg);

+               spin_lock(&task->pagg_lock);
+       }
+       spin_unlock(&task->pagg_lock);
+out:
+       rcu_read_unlock();
        return;   /* 0 = success, else return last code for failure */
 }

@@ -473,18 +519,20 @@ __pagg_detach(struct task_struct *task)
  *
  */
 int
-__pagg_exec(struct task_struct *task)
+pagg_exec(struct task_struct *task)
 {
        struct pagg     *pagg;

-       down_read(&task->pagg_sem); /* lock the pagg list */
+       rcu_read_lock();
+       if (list_empty(&task->pagg_list))
+               goto out;

-       list_for_each_entry(pagg, &task->pagg_list, entry) {
+       list_for_each_entry_rcu(pagg, &task->pagg_list, entry) {
                if (pagg->hook->exec) /* conditional because it's optional */
                        pagg->hook->exec(task, pagg);
        }
-
-       up_read(&task->pagg_sem); /* unlock the pagg list */
+ out:
+       rcu_read_unlock();
        return 0;
 }