Messages in this thread | | | Date | Thu, 29 May 2008 17:06:59 +0200 | From | Nadia Derbey <> | Subject | Re: [PATCH 3/4] ipc/sem.c: convert sem_array.sem_pending to struct list_head |
| |
Manfred Spraul wrote: > sem_array.sem_pending is a double linked list, the attached > patch converts it to struct list_head. > > Signed-Off-By: Manfred Spraul <manfred@colorfullife.com>
Reviewed-By: Nadia Derbey <Nadia.Derbey@bull.net>
2 small comments embedded.
> --- > include/linux/sem.h | 12 +++---- > ipc/sem.c | 90 ++++++++++++++++++-------------------------------- > 2 files changed, 38 insertions(+), 64 deletions(-) > > diff --git a/include/linux/sem.h b/include/linux/sem.h > index 87756ef..d425993 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 8cd96f1..38996c0 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) {
I guess here you are not using list_first_entry() because the pending requests might be empty?
> 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,24 @@ 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 +450,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 +470,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 +482,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 +509,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 +521,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 +1143,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 +1171,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);
Instead of removing it why not replacing the bug_ON() by a check on the queue still being linked?
> error = -EIDRM; > goto out_free; > } > @@ -1212,7 +1188,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:
Will have a look at the last patch + do some tests tomorrow.
Regards, Nadia
| |