From 86464aed71025541805e7b1515541aee89879e33 Mon Sep 17 00:00:00 2001 From: Ralf Baechle Date: Mon, 15 Feb 1999 02:15:32 +0000 Subject: Merge with Linux 2.2.1. --- ipc/sem.c | 316 ++++++++++++++++++++++++++++++++++--------------------------- ipc/shm.c | 13 ++- ipc/util.c | 3 +- 3 files changed, 190 insertions(+), 142 deletions(-) (limited to 'ipc') diff --git a/ipc/sem.c b/ipc/sem.c index 199a08ff7..5c67a5409 100644 --- a/ipc/sem.c +++ b/ipc/sem.c @@ -29,6 +29,25 @@ * see a clean way to get the old behavior with the new design. * The POSIX standard and SVID should be consulted to determine * what behavior is mandated. + * + * Further notes on refinement (Christoph Rohland, December 1998): + * - The POSIX standard says, that the undo adjustments simply should + * redo. So the current implementation is o.K. + * - The previous code had two flaws: + * 1) It actively gave the semaphore to the next waiting process + * sleeping on the semaphore. Since this process did not have the + * cpu this led to many unnecessary context switches and bad + * performance. Now we only check which process should be able to + * get the semaphore and if this process wants to reduce some + * semaphore value we simply wake it up without doing the + * operation. So it has to try to get it later. Thus e.g. the + * running process may reaquire the semaphore during the current + * time slice. If it only waits for zero or increases the semaphore, + * we do the operation in advance and wake it up. + * 2) It did not wake up all zero waiting processes. We try to do + * better but only get the semops right which only wait for zero or + * increase. If there are decrement operations in the operations + * array we do the same as before. */ #include @@ -158,12 +177,26 @@ out: /* 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 insert_into_queue (struct semid_ds * sma, struct sem_queue * q) +static inline void append_to_queue (struct semid_ds * sma, + struct sem_queue * q) { *(q->prev = sma->sem_pending_last) = q; *(sma->sem_pending_last = &q->next) = NULL; } -static inline void remove_from_queue (struct semid_ds * sma, struct sem_queue * q) + +static inline void prepend_to_queue (struct semid_ds * 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 semid_ds * sma, + struct sem_queue * q) { *(q->prev) = q->next; if (q->next) @@ -173,112 +206,100 @@ static inline void remove_from_queue (struct semid_ds * sma, struct sem_queue * q->prev = NULL; /* mark as removed */ } -/* Determine whether a sequence of semaphore operations would succeed +/* + * 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. */ -static int try_semop (struct semid_ds * sma, struct sembuf * sops, int nsops) -{ - int result = 0; - int i = 0; - - while (i < nsops) { - struct sembuf * sop = &sops[i]; - struct sem * curr = &sma->sem_base[sop->sem_num]; - if (sop->sem_op + curr->semval > SEMVMX) { - result = -ERANGE; - break; - } - if (!sop->sem_op && curr->semval) { - if (sop->sem_flg & IPC_NOWAIT) - result = -EAGAIN; - else - result = 1; - break; - } - i++; - curr->semval += sop->sem_op; - if (curr->semval < 0) { - if (sop->sem_flg & IPC_NOWAIT) - result = -EAGAIN; - else - result = 1; - break; - } - } - while (--i >= 0) { - struct sembuf * sop = &sops[i]; - struct sem * curr = &sma->sem_base[sop->sem_num]; - curr->semval -= sop->sem_op; - } - return result; -} -/* Actually perform a sequence of semaphore operations. Atomically. */ -/* This assumes that try_semop() already returned 0. */ -static int do_semop (struct semid_ds * sma, struct sembuf * sops, int nsops, - struct sem_undo * un, int pid) +static int try_atomic_semop (struct semid_ds * sma, struct sembuf * sops, + int nsops, struct sem_undo *un, int pid, + int do_undo) { - int i; + int result, sem_op; + struct sembuf *sop; + struct sem * curr; - for (i = 0; i < nsops; i++) { - struct sembuf * sop = &sops[i]; - struct sem * curr = &sma->sem_base[sop->sem_num]; - if (sop->sem_op + curr->semval > SEMVMX) { - printk("do_semop: race\n"); - break; - } - if (!sop->sem_op) { - if (curr->semval) { - printk("do_semop: race\n"); - break; - } - } else { - curr->semval += sop->sem_op; - if (curr->semval < 0) { - printk("do_semop: race\n"); - break; - } - if (sop->sem_flg & SEM_UNDO) - un->semadj[sop->sem_num] -= sop->sem_op; - } - curr->sempid = pid; + for (sop = sops; sop < sops + nsops; sop++) { + curr = sma->sem_base + sop->sem_num; + sem_op = sop->sem_op; + + if (!sem_op && curr->semval) + goto would_block; + + curr->sempid = (curr->sempid << 16) | pid; + curr->semval += sem_op; + if (sop->sem_flg & SEM_UNDO) + un->semadj[sop->sem_num] -= sem_op; + + if (curr->semval < 0) + goto would_block; + if (curr->semval > SEMVMX) + goto out_of_range; } - sma->sem_otime = CURRENT_TIME; - /* Previous implementation returned the last semaphore's semval. - * This is wrong because we may not have checked read permission, - * only write permission. - */ + if (do_undo) + { + sop--; + result = 0; + goto undo; + } + + sma->sem_otime = CURRENT_TIME; return 0; + +out_of_range: + result = -ERANGE; + goto undo; + +would_block: + if (sop->sem_flg & IPC_NOWAIT) + result = -EAGAIN; + else + result = 1; + +undo: + while (sop >= sops) { + curr = sma->sem_base + sop->sem_num; + curr->semval -= sop->sem_op; + curr->sempid >>= 16; + + if (sop->sem_flg & SEM_UNDO) + un->semadj[sop->sem_num] += sop->sem_op; + sop--; + } + + return result; } /* Go through the pending queue for the indicated semaphore - * looking for tasks that can be completed. Keep cycling through - * the queue until a pass is made in which no process is woken up. + * looking for tasks that can be completed. */ static void update_queue (struct semid_ds * sma) { - int wokeup, error; + int error; struct sem_queue * q; - do { - wokeup = 0; - for (q = sma->sem_pending; q; q = q->next) { - error = try_semop(sma, q->sops, q->nsops); - /* Does q->sleeper still need to sleep? */ - if (error > 0) - continue; - /* Perform the operations the sleeper was waiting for */ - if (!error) - error = do_semop(sma, q->sops, q->nsops, q->undo, q->pid); - q->status = error; - /* Remove it from the queue */ - remove_from_queue(sma,q); - /* Wake it up */ - wake_up_interruptible(&q->sleeper); /* doesn't sleep! */ - wokeup++; - } - } while (wokeup); + for (q = sma->sem_pending; q; q = q->next) { + + if (q->status == 1) + return; /* wait for other process */ + + error = try_atomic_semop(sma, q->sops, q->nsops, + q->undo, q->pid, q->alter); + + /* Does q->sleeper still need to sleep? */ + if (error <= 0) { + /* Found one, wake it up */ + wake_up_interruptible(&q->sleeper); + if (error == 0 && q->alter) { + /* if q-> alter let it self try */ + q->status = 1; + return; + } + q->status = error; + remove_from_queue(sma,q); + } + } } /* The following counts are associated to each semaphore: @@ -460,7 +481,7 @@ asmlinkage int sys_semctl (int semid, int semnum, int cmd, union semun arg) goto out; switch (cmd) { case GETVAL : err = curr->semval; goto out; - case GETPID : err = curr->sempid; goto out; + case GETPID : err = curr->sempid & 0xffff; goto out; case GETNCNT: err = count_semncnt(sma,semnum); goto out; case GETZCNT: err = count_semzcnt(sma,semnum); goto out; case GETALL: @@ -582,11 +603,12 @@ out: asmlinkage int sys_semop (int semid, struct sembuf *tsops, unsigned nsops) { - int i, id, size, error = -EINVAL; + int id, size, error = -EINVAL; struct semid_ds *sma; struct sembuf sops[SEMOPM], *sop; struct sem_undo *un; - int undos = 0, alter = 0; + int undos = 0, decrease = 0, alter = 0; + struct sem_queue queue; lock_kernel(); if (nsops < 1 || semid < 0) @@ -595,8 +617,6 @@ asmlinkage int sys_semop (int semid, struct sembuf *tsops, unsigned nsops) if (nsops > SEMOPM) goto out; error = -EFAULT; - if (!tsops) - goto out; if (copy_from_user (sops, tsops, nsops * sizeof(*tsops))) goto out; id = (unsigned int) semid % SEMMNI; @@ -606,22 +626,23 @@ asmlinkage int sys_semop (int semid, struct sembuf *tsops, unsigned nsops) error = -EIDRM; if (sma->sem_perm.seq != (unsigned int) semid / SEMMNI) goto out; - for (i = 0; i < nsops; i++) { - sop = &sops[i]; + error = -EFBIG; + for (sop = sops; sop < sops + nsops; sop++) { if (sop->sem_num >= sma->sem_nsems) goto out; if (sop->sem_flg & SEM_UNDO) undos++; - if (sop->sem_op) - alter++; + if (sop->sem_op < 0) + decrease = 1; + if (sop->sem_op > 0) + alter = 1; } + alter |= decrease; + error = -EACCES; if (ipcperms(&sma->sem_perm, alter ? S_IWUGO : S_IRUGO)) goto out; - error = try_semop(sma, sops, nsops); - if (error < 0) - goto out; if (undos) { /* Make sure we have an undo structure * for this process and this semaphore set. @@ -646,40 +667,59 @@ asmlinkage int sys_semop (int semid, struct sembuf *tsops, unsigned nsops) } } else un = NULL; - if (error == 0) { - /* the operations go through immediately */ - error = do_semop(sma, sops, nsops, un, current->pid); - /* maybe some queued-up processes were waiting for this */ - update_queue(sma); - goto out; - } else { - /* We need to sleep on this operation, so we put the current - * task into the pending queue and go to sleep. - */ - struct sem_queue queue; - - queue.sma = sma; - queue.sops = sops; - queue.nsops = nsops; - queue.undo = un; - queue.pid = current->pid; - queue.status = 0; - insert_into_queue(sma,&queue); - queue.sleeper = NULL; - current->semsleeping = &queue; - interruptible_sleep_on(&queue.sleeper); - current->semsleeping = NULL; - /* When we wake up, either the operation is finished, - * or some kind of error happened. - */ - if (!queue.prev) { - /* operation is finished, update_queue() removed us */ - error = queue.status; - } else { - remove_from_queue(sma,&queue); - error = -EINTR; - } - } + + error = try_atomic_semop (sma, sops, nsops, un, current->pid, 0); + if (error <= 0) + goto update; + + /* We need to sleep on this operation, so we put the current + * task into the pending queue and go to sleep. + */ + + queue.sma = sma; + queue.sops = sops; + queue.nsops = nsops; + queue.undo = un; + queue.pid = current->pid; + queue.alter = decrease; + current->semsleeping = &queue; + if (alter) + append_to_queue(sma ,&queue); + else + prepend_to_queue(sma ,&queue); + + for (;;) { + queue.status = -EINTR; + queue.sleeper = NULL; + interruptible_sleep_on(&queue.sleeper); + + /* + * If queue.status == 1 we where woken up and + * have to retry else we simply return. + * If an interrupt occurred we have to clean up the + * queue + * + */ + if (queue.status == 1) + { + error = try_atomic_semop (sma, sops, nsops, un, + current->pid,0); + if (error <= 0) + break; + } else { + error = queue.status;; + if (queue.prev) /* got Interrupt */ + break; + /* Everything done by update_queue */ + current->semsleeping = NULL; + goto out; + } + } + current->semsleeping = NULL; + remove_from_queue(sma,&queue); +update: + if (alter) + update_queue (sma); out: unlock_kernel(); return error; diff --git a/ipc/shm.c b/ipc/shm.c index e3866e1f0..b7224f330 100644 --- a/ipc/shm.c +++ b/ipc/shm.c @@ -126,6 +126,8 @@ found: return (unsigned int) shp->u.shm_perm.seq * SHMMNI + id; } +int shmmax = SHMMAX; + asmlinkage int sys_shmget (key_t key, int size, int shmflg) { struct shmid_kernel *shp; @@ -133,7 +135,7 @@ asmlinkage int sys_shmget (key_t key, int size, int shmflg) down(¤t->mm->mmap_sem); lock_kernel(); - if (size < 0 || size > SHMMAX) { + if (size < 0 || size > shmmax) { err = -EINVAL; } else if (key == IPC_PRIVATE) { err = newseg(key, shmflg, size); @@ -228,7 +230,7 @@ asmlinkage int sys_shmctl (int shmid, int cmd, struct shmid_ds *buf) if (!buf) goto out; shminfo.shmmni = SHMMNI; - shminfo.shmmax = SHMMAX; + shminfo.shmmax = shmmax; shminfo.shmmin = SHMMIN; shminfo.shmall = SHMALL; shminfo.shmseg = SHMSEG; @@ -622,6 +624,7 @@ static pte_t shm_swap_in(struct vm_area_struct * shmd, unsigned long offset, uns unsigned int id, idx; id = SWP_OFFSET(code) & SHM_ID_MASK; +#ifdef DEBUG_SHM if (id != (SWP_OFFSET(shmd->vm_pte) & SHM_ID_MASK)) { printk ("shm_swap_in: code id = %d and shmd id = %ld differ\n", id, SWP_OFFSET(shmd->vm_pte) & SHM_ID_MASK); @@ -631,12 +634,17 @@ static pte_t shm_swap_in(struct vm_area_struct * shmd, unsigned long offset, uns printk ("shm_swap_in: id=%d too big. proc mem corrupted\n", id); return BAD_PAGE; } +#endif shp = shm_segs[id]; + +#ifdef DEBUG_SHM if (shp == IPC_UNUSED || shp == IPC_NOID) { printk ("shm_swap_in: id=%d invalid. Race.\n", id); return BAD_PAGE; } +#endif idx = (SWP_OFFSET(code) >> SHM_IDX_SHIFT) & SHM_IDX_MASK; +#ifdef DEBUG_SHM if (idx != (offset >> PAGE_SHIFT)) { printk ("shm_swap_in: code idx = %u and shmd idx = %lu differ\n", idx, offset >> PAGE_SHIFT); @@ -646,6 +654,7 @@ static pte_t shm_swap_in(struct vm_area_struct * shmd, unsigned long offset, uns printk ("shm_swap_in : too large page index. id=%d\n", id); return BAD_PAGE; } +#endif pte = __pte(shp->shm_pages[idx]); if (!pte_present(pte)) { diff --git a/ipc/util.c b/ipc/util.c index 83d35f35d..3fbd14833 100644 --- a/ipc/util.c +++ b/ipc/util.c @@ -12,8 +12,7 @@ #include #include #include - -#include +#include #if defined(CONFIG_SYSVIPC) -- cgit v1.2.3