From 4daa28f6d8f5cda8ea0f55048e3c8811c384cbdd Mon Sep 17 00:00:00 2001 From: Manfred Spraul Date: Fri, 25 Jul 2008 01:48:04 -0700 Subject: ipc/sem.c: convert undo structures to struct list_head The undo structures contain two linked lists, the attached patch replaces them with generic struct list_head lists. [akpm@linux-foundation.org: coding-style fixes] Signed-off-by: Manfred Spraul Cc: Nadia Derbey Cc: Pierre Peiffer Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- ipc/sem.c | 163 ++++++++++++++++++++++++++++++++++---------------------------- 1 file changed, 89 insertions(+), 74 deletions(-) (limited to 'ipc/sem.c') diff --git a/ipc/sem.c b/ipc/sem.c index e9418df5ff3e..4f26c7157356 100644 --- a/ipc/sem.c +++ b/ipc/sem.c @@ -274,7 +274,7 @@ static int newary(struct ipc_namespace *ns, struct ipc_params *params) sma->sem_base = (struct sem *) &sma[1]; /* sma->sem_pending = NULL; */ sma->sem_pending_last = &sma->sem_pending; - /* sma->undo = NULL; */ + INIT_LIST_HEAD(&sma->list_id); sma->sem_nsems = nsems; sma->sem_ctime = get_seconds(); sem_unlock(sma); @@ -536,7 +536,8 @@ static void freeary(struct ipc_namespace *ns, struct kern_ipc_perm *ipcp) * (They will be freed without any further action in exit_sem() * or during the next semop.) */ - for (un = sma->undo; un; un = un->id_next) + assert_spin_locked(&sma->sem_perm.lock); + list_for_each_entry(un, &sma->list_id, list_id) un->semid = -1; /* Wake up all pending processes and let them fail with EIDRM. */ @@ -763,9 +764,12 @@ static int semctl_main(struct ipc_namespace *ns, int semid, int semnum, for (i = 0; i < nsems; i++) sma->sem_base[i].semval = sem_io[i]; - for (un = sma->undo; un; un = un->id_next) + + assert_spin_locked(&sma->sem_perm.lock); + list_for_each_entry(un, &sma->list_id, list_id) { for (i = 0; i < nsems; i++) un->semadj[i] = 0; + } sma->sem_ctime = get_seconds(); /* maybe some queued-up processes were waiting for this */ update_queue(sma); @@ -797,12 +801,15 @@ static int semctl_main(struct ipc_namespace *ns, int semid, int semnum, { int val = arg.val; struct sem_undo *un; + err = -ERANGE; if (val > SEMVMX || val < 0) goto out_unlock; - for (un = sma->undo; un; un = un->id_next) + assert_spin_locked(&sma->sem_perm.lock); + list_for_each_entry(un, &sma->list_id, list_id) un->semadj[semnum] = 0; + curr->semval = val; curr->sempid = task_tgid_vnr(current); sma->sem_ctime = get_seconds(); @@ -952,6 +959,8 @@ static inline int get_undo_list(struct sem_undo_list **undo_listp) return -ENOMEM; spin_lock_init(&undo_list->lock); atomic_set(&undo_list->refcnt, 1); + INIT_LIST_HEAD(&undo_list->list_proc); + current->sysvsem.undo_list = undo_list; } *undo_listp = undo_list; @@ -960,25 +969,30 @@ 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 **last, *un; - - last = &ulp->proc_list; - un = *last; - while(un != NULL) { - if(un->semid==semid) - break; - if(un->semid==-1) { - *last=un->proc_next; - kfree(un); - } else { - last=&un->proc_next; + struct sem_undo *walk, *tmp; + + assert_spin_locked(&ulp->lock); + list_for_each_entry_safe(walk, tmp, &ulp->list_proc, list_proc) { + if (walk->semid == semid) + return walk; + if (walk->semid == -1) { + list_del(&walk->list_proc); + kfree(walk); } - un=*last; } - return un; + return NULL; } -static struct sem_undo *find_undo(struct ipc_namespace *ns, int semid) +/** + * find_alloc_undo - Lookup (and if not present create) undo array + * @ns: namespace + * @semid: semaphore array id + * + * 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. + */ +static struct sem_undo *find_alloc_undo(struct ipc_namespace *ns, int semid) { struct sem_array *sma; struct sem_undo_list *ulp; @@ -997,6 +1011,7 @@ static struct sem_undo *find_undo(struct ipc_namespace *ns, int semid) goto out; /* no undo structure around - allocate one. */ + /* step 1: figure out the size of the semaphore array */ sma = sem_lock_check(ns, semid); if (IS_ERR(sma)) return ERR_PTR(PTR_ERR(sma)); @@ -1004,15 +1019,19 @@ static struct sem_undo *find_undo(struct ipc_namespace *ns, int semid) nsems = sma->sem_nsems; sem_getref_and_unlock(sma); + /* step 2: allocate new undo structure */ new = kzalloc(sizeof(struct sem_undo) + sizeof(short)*nsems, GFP_KERNEL); if (!new) { sem_putref(sma); return ERR_PTR(-ENOMEM); } - new->semadj = (short *) &new[1]; - new->semid = semid; + /* 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); @@ -1028,13 +1047,17 @@ static struct sem_undo *find_undo(struct ipc_namespace *ns, int semid) un = ERR_PTR(-EIDRM); goto out; } - new->proc_next = ulp->proc_list; - ulp->proc_list = new; - new->id_next = sma->undo; - sma->undo = new; + /* step 5: initialize & link new undo structure */ + new->semadj = (short *) &new[1]; + new->semid = semid; + assert_spin_locked(&ulp->lock); + list_add(&new->list_proc, &ulp->list_proc); + assert_spin_locked(&sma->sem_perm.lock); + list_add(&new->list_id, &sma->list_id); + sem_unlock(sma); - un = new; spin_unlock(&ulp->lock); + un = new; out: return un; } @@ -1090,9 +1113,8 @@ asmlinkage long sys_semtimedop(int semid, struct sembuf __user *tsops, alter = 1; } -retry_undos: if (undos) { - un = find_undo(ns, semid); + un = find_alloc_undo(ns, semid); if (IS_ERR(un)) { error = PTR_ERR(un); goto out_free; @@ -1107,14 +1129,14 @@ retry_undos: } /* - * semid identifiers are not unique - find_undo may have + * 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 retry. + * and now a new array with received the same id. Check and fail. */ - if (un && un->semid == -1) { - sem_unlock(sma); - goto retry_undos; - } + error = -EIDRM; + if (un && un->semid == -1) + goto out_unlock_free; + error = -EFBIG; if (max >= sma->sem_nsems) goto out_unlock_free; @@ -1243,56 +1265,44 @@ int copy_semundo(unsigned long clone_flags, struct task_struct *tsk) */ void exit_sem(struct task_struct *tsk) { - struct sem_undo_list *undo_list; - struct sem_undo *u, **up; - struct ipc_namespace *ns; + struct sem_undo_list *ulp; + struct sem_undo *un, *tmp; - undo_list = tsk->sysvsem.undo_list; - if (!undo_list) + ulp = tsk->sysvsem.undo_list; + if (!ulp) return; tsk->sysvsem.undo_list = NULL; - if (!atomic_dec_and_test(&undo_list->refcnt)) + if (!atomic_dec_and_test(&ulp->refcnt)) return; - ns = tsk->nsproxy->ipc_ns; - /* There's no need to hold the semundo list lock, as current - * is the last task exiting for this undo list. - */ - for (up = &undo_list->proc_list; (u = *up); *up = u->proc_next, kfree(u)) { + spin_lock(&ulp->lock); + + list_for_each_entry_safe(un, tmp, &ulp->list_proc, list_proc) { struct sem_array *sma; - int nsems, i; - struct sem_undo *un, **unp; - int semid; - - semid = u->semid; - - if(semid == -1) - continue; - sma = sem_lock(ns, semid); + int i; + + if (un->semid == -1) + goto free; + + sma = sem_lock(tsk->nsproxy->ipc_ns, un->semid); if (IS_ERR(sma)) - continue; + goto free; - if (u->semid == -1) - goto next_entry; + if (un->semid == -1) + goto unlock_free; - BUG_ON(sem_checkid(sma, u->semid)); + BUG_ON(sem_checkid(sma, un->semid)); - /* remove u from the sma->undo list */ - for (unp = &sma->undo; (un = *unp); unp = &un->id_next) { - if (u == un) - goto found; - } - printk ("exit_sem undo list error id=%d\n", u->semid); - goto next_entry; -found: - *unp = un->id_next; - /* perform adjustments registered in u */ - nsems = sma->sem_nsems; - for (i = 0; i < nsems; i++) { + /* remove un from sma->list_id */ + assert_spin_locked(&sma->sem_perm.lock); + list_del(&un->list_id); + + /* perform adjustments registered in un */ + for (i = 0; i < sma->sem_nsems; i++) { struct sem * semaphore = &sma->sem_base[i]; - if (u->semadj[i]) { - semaphore->semval += u->semadj[i]; + if (un->semadj[i]) { + semaphore->semval += un->semadj[i]; /* * Range checks of the new semaphore value, * not defined by sus: @@ -1316,10 +1326,15 @@ found: sma->sem_otime = get_seconds(); /* maybe some queued-up processes were waiting for this */ update_queue(sma); -next_entry: +unlock_free: sem_unlock(sma); +free: + assert_spin_locked(&ulp->lock); + list_del(&un->list_proc); + kfree(un); } - kfree(undo_list); + spin_unlock(&ulp->lock); + kfree(ulp); } #ifdef CONFIG_PROC_FS -- cgit v1.2.3 From 2c0c29d414087f3b021059673c20a7088f5f1fff Mon Sep 17 00:00:00 2001 From: Manfred Spraul Date: Fri, 25 Jul 2008 01:48:05 -0700 Subject: ipc/sem.c: remove unused entries from struct sem_queue sem_queue.sma and sem_queue.id were never used, the attached patch removes them. Signed-off-by: Manfred Spraul Reviewed-by: Nadia Derbey Cc: Pierre Peiffer Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/sem.h | 2 -- ipc/sem.c | 2 -- 2 files changed, 4 deletions(-) (limited to 'ipc/sem.c') diff --git a/include/linux/sem.h b/include/linux/sem.h index 6a1af1b49a13..87756ef1198e 100644 --- a/include/linux/sem.h +++ b/include/linux/sem.h @@ -107,8 +107,6 @@ struct sem_queue { struct sem_undo * undo; /* undo structure */ int pid; /* process id of requesting process */ int status; /* completion status of operation */ - struct sem_array * sma; /* semaphore array for operations */ - int id; /* internal sem id */ struct sembuf * sops; /* array of pending operations */ int nsops; /* number of operations */ int alter; /* does the operation alter the array? */ diff --git a/ipc/sem.c b/ipc/sem.c index 4f26c7157356..d5ce4000ca17 100644 --- a/ipc/sem.c +++ b/ipc/sem.c @@ -1160,12 +1160,10 @@ asmlinkage long sys_semtimedop(int semid, struct sembuf __user *tsops, * task into the pending queue and go to sleep. */ - queue.sma = sma; queue.sops = sops; queue.nsops = nsops; queue.undo = un; queue.pid = task_tgid_vnr(current); - queue.id = semid; queue.alter = alter; if (alter) append_to_queue(sma ,&queue); -- cgit v1.2.3 From a1193f8ec091cd8fd309cc2982abe4499f6f2b4d Mon Sep 17 00:00:00 2001 From: Manfred Spraul Date: Fri, 25 Jul 2008 01:48:06 -0700 Subject: ipc/sem.c: convert sem_array.sem_pending to struct list_head sem_array.sem_pending is a double linked list, the attached patch converts it to struct list_head. [akpm@linux-foundation.org: coding-style fixes] Signed-off-by: Manfred Spraul Reviewed-by: Nadia Derbey Cc: Pierre Peiffer Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/sem.h | 12 +++---- ipc/sem.c | 92 ++++++++++++++++++++--------------------------------- 2 files changed, 40 insertions(+), 64 deletions(-) (limited to 'ipc/sem.c') diff --git a/include/linux/sem.h b/include/linux/sem.h index 87756ef1198e..d42599395d79 100644 --- a/include/linux/sem.h +++ b/include/linux/sem.h @@ -93,21 +93,19 @@ struct sem_array { time_t sem_otime; /* last semop time */ time_t sem_ctime; /* last change time */ struct sem *sem_base; /* ptr to first semaphore in array */ - struct sem_queue *sem_pending; /* pending operations to be processed */ - struct sem_queue **sem_pending_last; /* last pending operation */ + struct list_head sem_pending; /* pending operations to be processed */ struct list_head list_id; /* undo requests on this array */ unsigned long sem_nsems; /* no. of semaphores in array */ }; /* One queue for each sleeping process in the system. */ struct sem_queue { - struct sem_queue * next; /* next entry in the queue */ - struct sem_queue ** prev; /* previous entry in the queue, *(q->prev) == q */ - struct task_struct* sleeper; /* this process */ - struct sem_undo * undo; /* undo structure */ + struct list_head list; /* queue of pending operations */ + struct task_struct *sleeper; /* this process */ + struct sem_undo *undo; /* undo structure */ int pid; /* process id of requesting process */ int status; /* completion status of operation */ - struct sembuf * sops; /* array of pending operations */ + struct sembuf *sops; /* array of pending operations */ int nsops; /* number of operations */ int alter; /* does the operation alter the array? */ }; diff --git a/ipc/sem.c b/ipc/sem.c index d5ce4000ca17..3ca232736b31 100644 --- a/ipc/sem.c +++ b/ipc/sem.c @@ -272,8 +272,7 @@ static int newary(struct ipc_namespace *ns, struct ipc_params *params) ns->used_sems += nsems; sma->sem_base = (struct sem *) &sma[1]; - /* sma->sem_pending = NULL; */ - sma->sem_pending_last = &sma->sem_pending; + INIT_LIST_HEAD(&sma->sem_pending); INIT_LIST_HEAD(&sma->list_id); sma->sem_nsems = nsems; sma->sem_ctime = get_seconds(); @@ -331,38 +330,6 @@ asmlinkage long sys_semget(key_t key, int nsems, int semflg) return ipcget(ns, &sem_ids(ns), &sem_ops, &sem_params); } -/* Manage the doubly linked list sma->sem_pending as a FIFO: - * insert new queue elements at the tail sma->sem_pending_last. - */ -static inline void append_to_queue (struct sem_array * sma, - struct sem_queue * q) -{ - *(q->prev = sma->sem_pending_last) = q; - *(sma->sem_pending_last = &q->next) = NULL; -} - -static inline void prepend_to_queue (struct sem_array * sma, - struct sem_queue * q) -{ - q->next = sma->sem_pending; - *(q->prev = &sma->sem_pending) = q; - if (q->next) - q->next->prev = &q->next; - else /* sma->sem_pending_last == &sma->sem_pending */ - sma->sem_pending_last = &q->next; -} - -static inline void remove_from_queue (struct sem_array * sma, - struct sem_queue * q) -{ - *(q->prev) = q->next; - if (q->next) - q->next->prev = q->prev; - else /* sma->sem_pending_last == &q->next */ - sma->sem_pending_last = q->prev; - q->prev = NULL; /* mark as removed */ -} - /* * Determine whether a sequence of semaphore operations would succeed * all at once. Return 0 if yes, 1 if need to sleep, else return error code. @@ -438,16 +405,15 @@ static void update_queue (struct sem_array * sma) int error; struct sem_queue * q; - q = sma->sem_pending; - while(q) { + q = list_entry(sma->sem_pending.next, struct sem_queue, list); + while (&q->list != &sma->sem_pending) { error = try_atomic_semop(sma, q->sops, q->nsops, q->undo, q->pid); /* Does q->sleeper still need to sleep? */ if (error <= 0) { struct sem_queue *n; - remove_from_queue(sma,q); - q->status = IN_WAKEUP; + /* * Continue scanning. The next operation * that must be checked depends on the type of the @@ -458,11 +424,26 @@ static void update_queue (struct sem_array * sma) * for semaphore values to become 0. * - if the operation didn't modify the array, * then just continue. + * The order of list_del() and reading ->next + * is crucial: In the former case, the list_del() + * must be done first [because we might be the + * first entry in ->sem_pending], in the latter + * case the list_del() must be done last + * [because the list is invalid after the list_del()] */ - if (q->alter) - n = sma->sem_pending; - else - n = q->next; + if (q->alter) { + list_del(&q->list); + n = list_entry(sma->sem_pending.next, + struct sem_queue, list); + } else { + n = list_entry(q->list.next, struct sem_queue, + list); + list_del(&q->list); + } + + /* wake up the waiting thread */ + q->status = IN_WAKEUP; + wake_up_process(q->sleeper); /* hands-off: q will disappear immediately after * writing q->status. @@ -471,7 +452,7 @@ static void update_queue (struct sem_array * sma) q->status = error; q = n; } else { - q = q->next; + q = list_entry(q->list.next, struct sem_queue, list); } } } @@ -491,7 +472,7 @@ static int count_semncnt (struct sem_array * sma, ushort semnum) struct sem_queue * q; semncnt = 0; - for (q = sma->sem_pending; q; q = q->next) { + list_for_each_entry(q, &sma->sem_pending, list) { struct sembuf * sops = q->sops; int nsops = q->nsops; int i; @@ -503,13 +484,14 @@ static int count_semncnt (struct sem_array * sma, ushort semnum) } return semncnt; } + static int count_semzcnt (struct sem_array * sma, ushort semnum) { int semzcnt; struct sem_queue * q; semzcnt = 0; - for (q = sma->sem_pending; q; q = q->next) { + list_for_each_entry(q, &sma->sem_pending, list) { struct sembuf * sops = q->sops; int nsops = q->nsops; int i; @@ -529,7 +511,7 @@ static int count_semzcnt (struct sem_array * sma, ushort semnum) static void freeary(struct ipc_namespace *ns, struct kern_ipc_perm *ipcp) { struct sem_undo *un; - struct sem_queue *q; + struct sem_queue *q, *t; struct sem_array *sma = container_of(ipcp, struct sem_array, sem_perm); /* Invalidate the existing undo structures for this semaphore set. @@ -541,17 +523,14 @@ static void freeary(struct ipc_namespace *ns, struct kern_ipc_perm *ipcp) un->semid = -1; /* Wake up all pending processes and let them fail with EIDRM. */ - q = sma->sem_pending; - while(q) { - struct sem_queue *n; - /* lazy remove_from_queue: we are killing the whole queue */ - q->prev = NULL; - n = q->next; + + list_for_each_entry_safe(q, t, &sma->sem_pending, list) { + list_del(&q->list); + q->status = IN_WAKEUP; wake_up_process(q->sleeper); /* doesn't sleep */ smp_wmb(); q->status = -EIDRM; /* hands-off q */ - q = n; } /* Remove the semaphore set from the IDR */ @@ -1166,9 +1145,9 @@ asmlinkage long sys_semtimedop(int semid, struct sembuf __user *tsops, queue.pid = task_tgid_vnr(current); queue.alter = alter; if (alter) - append_to_queue(sma ,&queue); + list_add_tail(&queue.list, &sma->sem_pending); else - prepend_to_queue(sma ,&queue); + list_add(&queue.list, &sma->sem_pending); queue.status = -EINTR; queue.sleeper = current; @@ -1194,7 +1173,6 @@ asmlinkage long sys_semtimedop(int semid, struct sembuf __user *tsops, sma = sem_lock(ns, semid); if (IS_ERR(sma)) { - BUG_ON(queue.prev != NULL); error = -EIDRM; goto out_free; } @@ -1212,7 +1190,7 @@ asmlinkage long sys_semtimedop(int semid, struct sembuf __user *tsops, */ if (timeout && jiffies_left == 0) error = -EAGAIN; - remove_from_queue(sma,&queue); + list_del(&queue.list); goto out_unlock_free; out_unlock_free: -- cgit v1.2.3 From 380af1b33b3ff92df5cda96329b58f5d1b6b5a53 Mon Sep 17 00:00:00 2001 From: Manfred Spraul Date: Fri, 25 Jul 2008 01:48:06 -0700 Subject: 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. [akpm@linux-foundation.org: coding-style fixes] Signed-off-by: Manfred Spraul Reviewed-by: Nadia Derbey Cc: Pierre Peiffer Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/sem.h | 6 ++- ipc/sem.c | 147 +++++++++++++++++++++++++++++++++------------------- 2 files changed, 98 insertions(+), 55 deletions(-) (limited to 'ipc/sem.c') diff --git a/include/linux/sem.h b/include/linux/sem.h index d42599395d79..1b191c176bcd 100644 --- a/include/linux/sem.h +++ b/include/linux/sem.h @@ -78,6 +78,7 @@ struct seminfo { #ifdef __KERNEL__ #include +#include 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 */ diff --git a/ipc/sem.c b/ipc/sem.c index 3ca232736b31..bf1bc36cb7ee 100644 --- a/ipc/sem.c +++ b/ipc/sem.c @@ -504,27 +504,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; @@ -948,16 +956,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; } @@ -970,6 +973,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) { @@ -983,11 +988,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); if (likely(un!=NULL)) goto out; + rcu_read_unlock(); /* no undo structure around - allocate one. */ /* step 1: figure out the size of the semaphore array */ @@ -1005,38 +1012,38 @@ 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); + 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(); + sem_unlock(sma); out: return un; } @@ -1103,6 +1110,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; } @@ -1111,10 +1120,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) @@ -1242,7 +1267,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) @@ -1252,28 +1276,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; - /* remove un from sma->list_id */ + 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 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]; @@ -1302,14 +1345,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: - assert_spin_locked(&ulp->lock); - list_del(&un->list_proc); - kfree(un); + + call_rcu(&un->rcu, free_un); } - spin_unlock(&ulp->lock); kfree(ulp); } -- cgit v1.2.3