ipc/sem.c: rewrite undo list locking
PATCH 4/4 ipc/sem.c: rewrite undo list locking
The attached patch:
- reverses the locking order of ulp->lock and sem_lock:
Previously, it was first ulp->lock, then inside sem_lock. Now it's the other way around.
- converts the undo structure to rcu.
Benefits:
- With the old locking order, IPC_RMID could not kfree the undo structures. The stale entries remained in the linked lists and were released later.
- The patch fixes a a race in semtimedop(): if both IPC_RMID and a semget() that recreates exactly the same id happen between find_alloc_undo() and sem_lock, then semtimedop() would access already kfree'd memory.
--- include/linux/sem.h | 6 ++- ipc/sem.c | 145 ++++++++++++++++++++++++++++++++------------------- 2 files changed, 96 insertions(+), 55 deletions(-)
include/linux/sem.h +5 -1
@@ -78,6 +78,7 @@ struct seminfo {#ifdef __KERNEL__#include <asm/atomic.h> +#include <linux/rcupdate.h> struct task_struct ;
@@ -114,7 +115,10 @@ struct sem_queue {* when the process exits. */ struct sem_undo { -struct list_head list_proc;/* per-process list: all undos from one process */ +struct list_head list_proc;/* per-process list: all undos from one process. */ +/* rcu protected */ +struct rcu_head rcu;/* rcu struct for sem_undo() */ +struct sem_undo_list *ulp;/* sem_undo_list for the process */ struct list_head list_id;/* per semaphore array list: all undos for one array */ int semid;/* semaphore set identifier */ short * semadj;/* array of adjustments, one per semaphore */
ipc/sem.c +91 -54
254 lines not on this page · raw message
Signature · 1 line
1.5.4.1
Quoted 6 lines · Manfred Spraul
The attached patch:
- reverses the locking order ofulp->lockandsem_lock:
Previously, it was firstulp->lock, then insidesem_lock. Now it's the other way around.
- converts the undo structure to rcu.
Quoted 8 lines
Benefits:
- With the old locking order,IPC_RMIDcould not kfree the undo structures. The stale entries remained in the linked lists and were released later.
- The patch fixes a a race insemtimedop(): if bothIPC_RMIDand asemget()that recreates exactly the same id happen betweenfind_alloc_undo()andsem_lock, thensemtimedop()would access already kfree'd memory.Signed-off-by Manfred Spraul <[email protected]>
2 comments embedded.
Quoted 107 lines
--- include/linux/sem.h | 6 ++- ipc/sem.c | 145 ++++++++++++++++++++++++++++++++------------------- 2 files changed, 96 insertions(+), 55 deletions(-)include/linux/sem.h +5
-1@@ -78,6 +78,7 @@ struct seminfo {#ifdef __KERNEL__#include <asm/atomic.h> +#include <linux/rcupdate.h> struct task_struct ;@@ -114,7 +115,10 @@ struct sem_queue {* when the process exits. */ struct sem_undo { -struct list_head list_proc;/* per-process list: all undos from one process */ +struct list_head list_proc;/* per-process list: all undos from one process. */ +/* rcu protected */ +struct rcu_head rcu;/* rcu struct for sem_undo() */ +struct sem_undo_list *ulp;/* sem_undo_list for the process */ struct list_head list_id;/* per semaphore array list: all undos for one array */ int semid;/* semaphore set identifier */ short * semadj;/* array of adjustments, one per semaphore */ ipc/sem.c +21
-16@@ -502,27 +502,35 @@ static int count_semzcnt (struct sem_array * sma, ushort semnum)return semzcnt; } +void free_un (struct rcu_head *head) +{ + struct sem_undo *un = container_of(head, struct sem_undo, rcu); +kfree (un); +} +/* Free a semaphore set. freeary() is called with sem_ids.rw_mutex locked * as a writer and the spinlock for this semaphore set hold. sem_ids.rw_mutex * remains locked on exit. */ static void freeary (struct ipc_namespace *ns,struct kern_ipc_perm *ipcp) { -struct sem_undo *un; -struct sem_queue *q, *t; +struct sem_undo *un, *tu; +struct sem_queue *q, *tq; struct sem_array *sma = container_of(ipcp, struct sem_array, sem_perm); -/* Invalidate the existing undo structures for this semaphore set. -* (They will be freed without any further action in exit_sem() -* or during the next semop.) -*/ +/* Free the existing undo structures for this semaphore set. */ assert_spin_locked (&sma->sem_perm.lock); -list_for_each_entry (un, &sma->list_id, list_id) +list_for_each_entry_safe (un, tu, &sma->list_id, list_id) { +list_del (&un->list_id); +spin_lock (&un->ulp->lock); un->semid =-1 ; +list_del_rcu (&un->list_proc); +spin_unlock (&un->ulp->lock); +call_rcu (&un->rcu, free_un); + }/* Wake up all pending processes and let them fail with EIDRM. */ - -list_for_each_entry_safe (q, t, &sma->sem_pending, list) { +list_for_each_entry_safe (q, tq, &sma->sem_pending, list) {list_del (&q->list); q->status =IN_WAKEUP ;@@ -946,16 +954,11 @@ static inline int get_undo_list(struct sem_undo_list **undo_listp)static struct sem_undo *lookup_undo (struct sem_undo_list *ulp,int semid) { -struct sem_undo *walk, *tmp; +struct sem_undo *walk; -assert_spin_locked (&ulp->lock); -list_for_each_entry_safe (walk, tmp, &ulp->list_proc, list_proc) { +list_for_each_entry_rcu (walk, &ulp->list_proc, list_proc) {if (walk->semid==semid)return walk; -if (walk->semid==-1 ) { -list_del (&walk->list_proc); -kfree (walk); - } }return NULL ; }@@ -968,6 +971,8 @@ static struct sem_undo *lookup_undo(struct sem_undo_list *ulp, int semid)* The function looks up (and if not present creates) the undo structure. * The size of the undo structure depends on the size of the semaphore * array, thus the alloc path is not that straightforward. +* Lifetime-rules: sem_undo is rcu-protected, on success, the function +* performs a rcu_read_lock(). */ static struct sem_undo *find_alloc_undo (struct ipc_namespace *ns,int semid) {
ipc/sem.c static struct sem_undo *find_alloc_undo(struct ipc_namespace *ns, int semid) · line 992
Quoted 7 lines
ipc/sem.c +1
-0@@ -981,11 +986,13 @@ static struct sem_undo *find_alloc_undo(struct ipc_namespace *ns, int semid)if (error)return ERR_PTR (error); +rcu_read_lock ();spin_lock (&ulp->lock); un =lookup_undo (ulp, semid);spin_unlock (&ulp->lock);
Why are we locking the sem_undo_list: in the lookup, we are traversing the proc_list that is rcu_protected.
Quoted 46 lines
ipc/sem.c +11
-15if (likely (un!=NULL )) goto out; +rcu_read_unlock ();/* no undo structure around - allocate one. */ /* step 1: figure out the size of the semaphore array */ @@ -1003,38 +1010,36 @@ static struct sem_undo *find_alloc_undo(struct ipc_namespace *ns, int semid)return ERR_PTR (-ENOMEM ); } -/* step 3: Acquire the lock on the undo list pointer */ -spin_lock (&ulp->lock); - -/* step 4: check for races: someone else allocated the undo struct, -* semaphore array was destroyed. -*/ - un =lookup_undo (ulp, semid); -if (un) { -spin_unlock (&ulp->lock); -kfree (new); -sem_putref (sma); - goto out; - } +/* step 3: Acquire the lock on semaphore array */ sem_lock_and_putref (sma);if (sma->sem_perm.deleted) {sem_unlock (sma); -spin_unlock (&ulp->lock);kfree (new); un =ERR_PTR (-EIDRM ); goto out; } +spin_lock (&ulp->lock); + +/* step 4: check for races: did someone else allocate the undo struct? */ + un =lookup_undo (ulp, semid); +if (un) { +kfree (new); + goto success; + }/* step 5: initialize & link new undo structure */ new->semadj = (short *) &new[1 ]; + new->ulp = ulp; new->semid = semid;assert_spin_locked (&ulp->lock); -list_add (&new->list_proc, &ulp->list_proc);
ipc/sem.c static struct sem_undo *find_alloc_undo(struct ipc_namespace *ns, int semid) · line 1041
Quoted 10 lines
ipc/sem.c +4
-2+list_add_rcu (&new->list_proc, &ulp->list_proc);assert_spin_locked (&sma->sem_perm.lock);list_add (&new->list_id, &sma->list_id); + un = new; -sem_unlock (sma); +success:spin_unlock (&ulp->lock); - un = new; +rcu_read_lock ();
Oh, I'm realizing that we should leave the routine with an rcu_read_lock? Why not adding a comment everywhere find_alloc_undo() is called?
Quoted 117 lines
ipc/sem.c +52
-17+sem_unlock (sma); out:return un; }@@ -1101,6 +1106,8 @@ asmlinkage long sys_semtimedop(int semid, struct sembuf __user *tsops, sma =sem_lock_check (ns, semid);if (IS_ERR (sma)) { +if (un) +rcu_read_unlock (); error =PTR_ERR (sma); goto out_free; }@@ -1109,10 +1116,26 @@ asmlinkage long sys_semtimedop(int semid, struct sembuf __user *tsops,* semid identifiers are not unique - find_alloc_undo may have * allocated an undo structure, it was invalidated by an RMID * and now a new array with received the same id. Check and fail. +* This case can be detected checking un->semid. The existance of +* "un" itself is guaranteed by rcu. */ error = -EIDRM ; -if (un && un->semid ==-1 ) - goto out_unlock_free; +if (un) { +if (un->semid ==-1 ) { +rcu_read_unlock (); + goto out_unlock_free; + }else { +/* +* rcu lock can be released, "un" cannot disappear: +* - sem_lock is acquired, thus IPC_RMID is +* impossible. +* - exit_sem is impossible, it always operates on +* current (or a dead task). +*/ + +rcu_read_unlock (); + } + } error = -EFBIG ;if (max >= sma->sem_nsems)@@ -1240,7 +1263,6 @@ int copy_semundo(unsigned long clone_flags, struct task_struct *tsk)void exit_sem (struct task_struct *tsk) {struct sem_undo_list *ulp; -struct sem_undo *un, *tmp; ulp= tsk->sysvsem.undo_list;if (!ulp)@@ -1250,28 +1272,47 @@ void exit_sem(struct task_struct *tsk)if (!atomic_dec_and_test (&ulp->refcnt))return ; -spin_lock (&ulp->lock); - -list_for_each_entry_safe (un, tmp, &ulp->list_proc, list_proc) { +for (;;) {struct sem_array *sma; +struct sem_undo *un; +int semid;int i; -if (un->semid ==-1 ) - goto free; +rcu_read_lock (); + un =list_entry (rcu_dereference (ulp->list_proc.next), + struct sem_undo, list_proc); +if (&un->list_proc == &ulp->list_proc) + semid =-1 ; +else + semid = un->semid; +rcu_read_unlock (); - sma =sem_lock (tsk->nsproxy->ipc_ns, un->semid); -if (IS_ERR (sma)) - goto free; +if (semid ==-1 ) +break ; -if (un->semid ==-1 ) - goto unlock_free; + sma =sem_lock_check (tsk->nsproxy->ipc_ns, un->semid); -BUG_ON (sem_checkid (sma, un->semid)); +/* exit_sem raced with IPC_RMID, nothing to do */ +if (IS_ERR (sma)) +continue ; + + un =lookup_undo (ulp, semid); +if (un ==NULL ) { +/* exit_sem raced with IPC_RMID+semget() that created +* exactly the same semid. Nothing to do. +*/ +sem_unlock (sma); +continue ; + } -/* remove un from sma->list_id */ +/* remove un from the linked lists */ assert_spin_locked (&sma->sem_perm.lock);list_del (&un->list_id); +spin_lock (&ulp->lock); +list_del_rcu (&un->list_proc); +spin_unlock (&ulp->lock); +/* perform adjustments registered in un */ for (i =0 ; i < sma->sem_nsems; i++) {struct sem * semaphore = &sma->sem_base[i];@@ -1300,14 +1341,10 @@ void exit_sem(struct task_struct *tsk) sma->sem_otime =get_seconds ();/* maybe some queued-up processes were waiting for this */ update_queue (sma); -unlock_free:sem_unlock (sma); -free:
ipc/sem.c void exit_sem(struct task_struct *tsk) · line 1350
Quoted 10 lines
ipc/sem.c +2
-4-assert_spin_locked (&ulp->lock); -list_del (&un->list_proc); -kfree (un); + +call_rcu (&un->rcu, free_un); } -spin_unlock (&ulp->lock);kfree (ulp); }
Regards,
Nadia