Merge with Linux 2.2.1.

3 files changed, 190 insertions, 142 deletions

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 <linux/malloc.h>
@@ -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(&current->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 <linux/mm.h>
 #include <linux/shm.h>
 #include <linux/init.h>
-
-#include <asm/uaccess.h>
+#include <linux/msg.h>
 
 #if defined(CONFIG_SYSVIPC)