[PATCH 0/6] ipc/sem.c: Fix semctl(,,{GETNCNT,GETZCNT})

[PATCH 0/6] ipc/sem.c: Fix semctl(,,{GETNCNT,GETZCNT})

[Manfred Spraul]

Hi all,

According to the man page of semop(), semzcnt or semncnt are increased
exactly for the operation that couldn't proceed.

The Linux implementation always tried to be clever and to increase the counters
for all operations that might be the reason why a task sleeps.

The following patches fix that and make the code conform to the 
documentation.

The series got fairly long, because I also noticed that semzcnt was calculated
incorrectly.

What do you think?
I ran a few test cases, and the semncnt and semzcnt counts now match
the expectation.

Is anyone aware of an application that uses GETNCNT or GETZCNT?

--
	Manfred

[PATCH 1/6] ipc/sem.c: further whitespace cleanups

[Manfred Spraul]

Somehow <TAB>$ was overlooked in the last round of whitespace
cleanups.
Do that now, before making further changes.

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
---
 ipc/sem.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/ipc/sem.c b/ipc/sem.c
index bee5554..5749b9c 100644
--- a/ipc/sem.c
+++ b/ipc/sem.c
@@ -160,7 +160,7 @@ static int sysvipc_sem_proc_show(struct seq_file *s, void *it);
  *	sem_array.pending{_alter,_cont},
  *	sem_array.sem_undo: global sem_lock() for read/write
  *	sem_undo.proc_next: only "current" is allowed to read/write that field.
- *	
+ *
  *	sem_array.sem_base[i].pending_{const,alter}:
  *		global or semaphore sem_lock() for read/write
  */
@@ -1161,7 +1161,7 @@ static int semctl_nolock(struct ipc_namespace *ns, int semid,
 		err = security_sem_semctl(NULL, cmd);
 		if (err)
 			return err;
-		
+
 		memset(&seminfo, 0, sizeof(seminfo));
 		seminfo.semmni = ns->sc_semmni;
 		seminfo.semmns = ns->sc_semmns;
@@ -1883,7 +1883,7 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
 	/* We need to sleep on this operation, so we put the current
 	 * task into the pending queue and go to sleep.
 	 */
-		
+
 	queue.sops = sops;
 	queue.nsops = nsops;
 	queue.undo = un;
-- 
1.9.0

[PATCH 2/6] ipc/sem.c: Bugfix for semctl(,,GETZCNT)

[Manfred Spraul]

GETZCNT is supposed to return the number of threads that wait until
a semaphore value becomes 0.
The current implementation overlooks complex operations that contain
both wait-for-zero operation and operations that alter at least one semaphore.

The patch fixes that.
It's intentionally copy&paste, this will be cleaned up in the next patch.

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
---
 ipc/sem.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/ipc/sem.c b/ipc/sem.c
index 5749b9c..dc648f8 100644
--- a/ipc/sem.c
+++ b/ipc/sem.c
@@ -1047,6 +1047,16 @@ static int count_semzcnt(struct sem_array *sma, ushort semnum)
 			    && !(sops[i].sem_flg & IPC_NOWAIT))
 				semzcnt++;
 	}
+	list_for_each_entry(q, &sma->pending_alter, list) {
+		struct sembuf *sops = q->sops;
+		int nsops = q->nsops;
+		int i;
+		for (i = 0; i < nsops; i++)
+			if (sops[i].sem_num == semnum
+			    && (sops[i].sem_op == 0)
+			    && !(sops[i].sem_flg & IPC_NOWAIT))
+				semzcnt++;
+	}
 	return semzcnt;
 }
 
-- 
1.9.0

[PATCH 3/6] ipc/sem.c: remove code duplication

[Manfred Spraul]

count_semzcnt and count_semncnt are more of less identical.
The patch creates a single function that either counts the number of tasks
waiting for zero or waiting due to a decrease operation.

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
---
 ipc/sem.c | 103 ++++++++++++++++++++++++++++++--------------------------------
 1 file changed, 50 insertions(+), 53 deletions(-)

diff --git a/ipc/sem.c b/ipc/sem.c
index dc648f8..821aba7 100644
--- a/ipc/sem.c
+++ b/ipc/sem.c
@@ -47,8 +47,7 @@
  *   Thus: Perfect SMP scaling between independent semaphore arrays.
  *         If multiple semaphores in one array are used, then cache line
  *         trashing on the semaphore array spinlock will limit the scaling.
- * - semncnt and semzcnt are calculated on demand in count_semncnt() and
- *   count_semzcnt()
+ * - semncnt and semzcnt are calculated on demand in count_semcnt()
  * - the task that performs a successful semop() scans the list of all
  *   sleeping tasks and completes any pending operations that can be fulfilled.
  *   Semaphores are actively given to waiting tasks (necessary for FIFO).
@@ -989,6 +988,31 @@ static void do_smart_update(struct sem_array *sma, struct sembuf *sops, int nsop
 		set_semotime(sma, sops);
 }
 
+/*
+ * check_qop: Test how often a queued operation sleeps on the semaphore semnum
+ */
+static int check_qop(struct sem_array *sma, int semnum, struct sem_queue *q,
+			bool count_zero)
+{
+	struct sembuf *sops = q->sops;
+	int nsops = q->nsops;
+	int i, semcnt;
+
+	semcnt = 0;
+
+	for (i = 0; i < nsops; i++) {
+		if (sops[i].sem_num != semnum)
+			continue;
+		if (sops[i].sem_flg & IPC_NOWAIT)
+			continue;
+		if (count_zero && sops[i].sem_op == 0)
+			semcnt++;
+		if (!count_zero && sops[i].sem_op < 0)
+			semcnt++;
+	}
+	return semcnt;
+}
+
 /* The following counts are associated to each semaphore:
  *   semncnt        number of tasks waiting on semval being nonzero
  *   semzcnt        number of tasks waiting on semval being zero
@@ -998,66 +1022,39 @@ static void do_smart_update(struct sem_array *sma, struct sembuf *sops, int nsop
  * The counts we return here are a rough approximation, but still
  * warrant that semncnt+semzcnt>0 if the task is on the pending queue.
  */
-static int count_semncnt(struct sem_array *sma, ushort semnum)
+static int count_semcnt(struct sem_array *sma, ushort semnum,
+			bool count_zero)
 {
-	int semncnt;
+	struct list_head *l;
 	struct sem_queue *q;
+	int semcnt;
 
-	semncnt = 0;
-	list_for_each_entry(q, &sma->sem_base[semnum].pending_alter, list) {
-		struct sembuf *sops = q->sops;
-		BUG_ON(sops->sem_num != semnum);
-		if ((sops->sem_op < 0) && !(sops->sem_flg & IPC_NOWAIT))
-			semncnt++;
-	}
+	semcnt = 0;
+	/* First: check the simple operations. They are easy to evaluate */
+	if (count_zero)
+		l = &sma->sem_base[semnum].pending_const;
+	else
+		l = &sma->sem_base[semnum].pending_alter;
 
-	list_for_each_entry(q, &sma->pending_alter, list) {
+	list_for_each_entry(q, l, list) {
 		struct sembuf *sops = q->sops;
-		int nsops = q->nsops;
-		int i;
-		for (i = 0; i < nsops; i++)
-			if (sops[i].sem_num == semnum
-			    && (sops[i].sem_op < 0)
-			    && !(sops[i].sem_flg & IPC_NOWAIT))
-				semncnt++;
-	}
-	return semncnt;
-}
 
-static int count_semzcnt(struct sem_array *sma, ushort semnum)
-{
-	int semzcnt;
-	struct sem_queue *q;
-
-	semzcnt = 0;
-	list_for_each_entry(q, &sma->sem_base[semnum].pending_const, list) {
-		struct sembuf *sops = q->sops;
 		BUG_ON(sops->sem_num != semnum);
-		if ((sops->sem_op == 0) && !(sops->sem_flg & IPC_NOWAIT))
-			semzcnt++;
+		BUG_ON(sops->sem_flg & IPC_NOWAIT);
+		BUG_ON(sops->sem_op > 0);
+		semcnt++;
 	}
 
-	list_for_each_entry(q, &sma->pending_const, list) {
-		struct sembuf *sops = q->sops;
-		int nsops = q->nsops;
-		int i;
-		for (i = 0; i < nsops; i++)
-			if (sops[i].sem_num == semnum
-			    && (sops[i].sem_op == 0)
-			    && !(sops[i].sem_flg & IPC_NOWAIT))
-				semzcnt++;
-	}
+	/* Then: check the complex operations. */
 	list_for_each_entry(q, &sma->pending_alter, list) {
-		struct sembuf *sops = q->sops;
-		int nsops = q->nsops;
-		int i;
-		for (i = 0; i < nsops; i++)
-			if (sops[i].sem_num == semnum
-			    && (sops[i].sem_op == 0)
-			    && !(sops[i].sem_flg & IPC_NOWAIT))
-				semzcnt++;
+		semcnt += check_qop(sma, semnum, q, count_zero);
+	}
+	if (count_zero) {
+		list_for_each_entry(q, &sma->pending_const, list) {
+			semcnt += check_qop(sma, semnum, q, count_zero);
+		}
 	}
-	return semzcnt;
+	return semcnt;
 }
 
 /* Free a semaphore set. freeary() is called with sem_ids.rwsem locked
@@ -1459,10 +1456,10 @@ static int semctl_main(struct ipc_namespace *ns, int semid, int semnum,
 		err = curr->sempid;
 		goto out_unlock;
 	case GETNCNT:
-		err = count_semncnt(sma, semnum);
+		err = count_semcnt(sma, semnum, 0);
 		goto out_unlock;
 	case GETZCNT:
-		err = count_semzcnt(sma, semnum);
+		err = count_semcnt(sma, semnum, 1);
 		goto out_unlock;
 	}
 
-- 
1.9.0

[PATCH 4/6] ipc/sem.c: Change perform_atomic_semop parameters

[Manfred Spraul]

Right now, perform_atomic_semop gets the content of sem_queue as individual
fields.
Changes that, instead pass a pointer to sem_queue.

This is a preparation for the next patch: it uses
sem_queue to store the reason why a task must sleep.

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
---
 ipc/sem.c | 38 +++++++++++++++++++-------------------
 1 file changed, 19 insertions(+), 19 deletions(-)

diff --git a/ipc/sem.c b/ipc/sem.c
index 821aba7..3962cca 100644
--- a/ipc/sem.c
+++ b/ipc/sem.c
@@ -585,21 +585,23 @@ SYSCALL_DEFINE3(semget, key_t, key, int, nsems, int, semflg)
 /**
  * perform_atomic_semop - Perform (if possible) a semaphore operation
  * @sma: semaphore array
- * @sops: array with operations that should be checked
- * @nsops: number of operations
- * @un: undo array
- * @pid: pid that did the change
+ * @q: struct sem_queue that describes the operation
  *
  * Returns 0 if the operation was possible.
  * Returns 1 if the operation is impossible, the caller must sleep.
  * Negative values are error codes.
  */
-static int perform_atomic_semop(struct sem_array *sma, struct sembuf *sops,
-			     int nsops, struct sem_undo *un, int pid)
+static int perform_atomic_semop(struct sem_array *sma, struct sem_queue *q)
 {
-	int result, sem_op;
+	int result, sem_op, nsops, pid;
 	struct sembuf *sop;
 	struct sem *curr;
+	struct sembuf *sops;
+	struct sem_undo *un;
+
+	sops = q->sops;
+	nsops = q->nsops;
+	un = q->undo;
 
 	for (sop = sops; sop < sops + nsops; sop++) {
 		curr = sma->sem_base + sop->sem_num;
@@ -627,6 +629,7 @@ static int perform_atomic_semop(struct sem_array *sma, struct sembuf *sops,
 	}
 
 	sop--;
+	pid = q->pid;
 	while (sop >= sops) {
 		sma->sem_base[sop->sem_num].sempid = pid;
 		sop--;
@@ -779,8 +782,7 @@ static int wake_const_ops(struct sem_array *sma, int semnum,
 		q = container_of(walk, struct sem_queue, list);
 		walk = walk->next;
 
-		error = perform_atomic_semop(sma, q->sops, q->nsops,
-						 q->undo, q->pid);
+		error = perform_atomic_semop(sma, q);
 
 		if (error <= 0) {
 			/* operation completed, remove from queue & wakeup */
@@ -892,8 +894,7 @@ again:
 		if (semnum != -1 && sma->sem_base[semnum].semval == 0)
 			break;
 
-		error = perform_atomic_semop(sma, q->sops, q->nsops,
-					 q->undo, q->pid);
+		error = perform_atomic_semop(sma, q);
 
 		/* Does q->sleeper still need to sleep? */
 		if (error > 0)
@@ -1873,8 +1874,13 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
 	if (un && un->semid == -1)
 		goto out_unlock_free;
 
-	error = perform_atomic_semop(sma, sops, nsops, un,
-					task_tgid_vnr(current));
+	queue.sops = sops;
+	queue.nsops = nsops;
+	queue.undo = un;
+	queue.pid = task_tgid_vnr(current);
+	queue.alter = alter;
+
+	error = perform_atomic_semop(sma, &queue);
 	if (error == 0) {
 		/* If the operation was successful, then do
 		 * the required updates.
@@ -1891,12 +1897,6 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
 	 * task into the pending queue and go to sleep.
 	 */
 
-	queue.sops = sops;
-	queue.nsops = nsops;
-	queue.undo = un;
-	queue.pid = task_tgid_vnr(current);
-	queue.alter = alter;
-
 	if (nsops == 1) {
 		struct sem *curr;
 		curr = &sma->sem_base[sops->sem_num];
-- 
1.9.0

[PATCH 5/6] ipc/sem.c: Store which operation blocks in perform_atomic_semop()

[Manfred Spraul]

Preparation for the next patch:
In the slow-path of perform_atomic_semop(), store a pointer to the operation
that caused the operation to block.

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
---
 ipc/sem.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/ipc/sem.c b/ipc/sem.c
index 3962cca..22a4c12 100644
--- a/ipc/sem.c
+++ b/ipc/sem.c
@@ -109,6 +109,7 @@ struct sem_queue {
 	int			pid;	 /* process id of requesting process */
 	int			status;	 /* completion status of operation */
 	struct sembuf		*sops;	 /* array of pending operations */
+	struct sembuf		*blocking; /* the operation that blocked */
 	int			nsops;	 /* number of operations */
 	int			alter;	 /* does *sops alter the array? */
 };
@@ -642,6 +643,8 @@ out_of_range:
 	goto undo;
 
 would_block:
+	q->blocking = sop;
+
 	if (sop->sem_flg & IPC_NOWAIT)
 		result = -EAGAIN;
 	else
-- 
1.9.0

[PATCH 6/6] ipc/sem.c: make semctl(,,{GETNCNT,GETZCNT}) standard compliant

[Manfred Spraul]

Per definition, a task waits on exactly one semaphore:
The semaphore from the first operation in the sop array that cannot proceed.

The Linux implementation never followed the standard, it tried to count all
semaphores that might be the reason why a task sleeps.

This patch fixes that.

Note:
The implementation assumes that GETNCNT and GETZCNT are rare operations,
therefore the code counts them only on demand.
(If they wouldn't be rare, then the non-compliance would have
been found earlier)

Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
---
 ipc/sem.c | 37 ++++++++++++++++---------------------
 1 file changed, 16 insertions(+), 21 deletions(-)

diff --git a/ipc/sem.c b/ipc/sem.c
index 22a4c12..5e8bcde 100644
--- a/ipc/sem.c
+++ b/ipc/sem.c
@@ -993,38 +993,33 @@ static void do_smart_update(struct sem_array *sma, struct sembuf *sops, int nsop
 }
 
 /*
- * check_qop: Test how often a queued operation sleeps on the semaphore semnum
+ * check_qop: Test if a queued operation sleeps on the semaphore semnum
  */
 static int check_qop(struct sem_array *sma, int semnum, struct sem_queue *q,
 			bool count_zero)
 {
-	struct sembuf *sops = q->sops;
-	int nsops = q->nsops;
-	int i, semcnt;
+	struct sembuf *sop = q->blocking;
 
-	semcnt = 0;
+	BUG_ON(sop->sem_flg & IPC_NOWAIT);
+	BUG_ON(sop->sem_op > 0);
 
-	for (i = 0; i < nsops; i++) {
-		if (sops[i].sem_num != semnum)
-			continue;
-		if (sops[i].sem_flg & IPC_NOWAIT)
-			continue;
-		if (count_zero && sops[i].sem_op == 0)
-			semcnt++;
-		if (!count_zero && sops[i].sem_op < 0)
-			semcnt++;
-	}
-	return semcnt;
+	if (sop->sem_num != semnum)
+		return 0;
+
+	if (count_zero && sop->sem_op == 0)
+		return 1;
+	if (!count_zero && sop->sem_op < 0)
+		return 1;
+
+	return 0;
 }
 
 /* The following counts are associated to each semaphore:
  *   semncnt        number of tasks waiting on semval being nonzero
  *   semzcnt        number of tasks waiting on semval being zero
- * This model assumes that a task waits on exactly one semaphore.
- * Since semaphore operations are to be performed atomically, tasks actually
- * wait on a whole sequence of semaphores simultaneously.
- * The counts we return here are a rough approximation, but still
- * warrant that semncnt+semzcnt>0 if the task is on the pending queue.
+ *
+ * Per definition, a task waits only on the semaphore of the first semop
+ * that cannot proceed, even if additional operation would block, too.
  */
 static int count_semcnt(struct sem_array *sma, ushort semnum,
 			bool count_zero)
-- 
1.9.0

Re: [PATCH 1/6] ipc/sem.c: further whitespace cleanups

[Davidlohr Bueso]

On Sat, 2014-05-10 at 12:03 +0200, Manfred Spraul wrote:
> Somehow <TAB>$ was overlooked in the last round of whitespace
> cleanups.
> Do that now, before making further changes.

No big deal, but this patch could easily be included in the the second
patch instead on its own. Thanks.

Re: [PATCH 0/6] ipc/sem.c: Fix semctl(,,{GETNCNT,GETZCNT})

[Davidlohr Bueso]

On Sat, 2014-05-10 at 12:03 +0200, Manfred Spraul wrote:
> Hi all,
> 
> According to the man page of semop(), semzcnt or semncnt are increased
> exactly for the operation that couldn't proceed.
> 
> The Linux implementation always tried to be clever and to increase the counters
> for all operations that might be the reason why a task sleeps.

... and I hate the fact that we do so on demand, instead of modifying
the values when semop is called. This makes the whole semctl calls less
accurate, and in fact its mentioned in the code.

> The following patches fix that and make the code conform to the 
> documentation.
> 
> The series got fairly long, because I also noticed that semzcnt was calculated
> incorrectly.
> 
> What do you think?

I'm still going through the changes, sems make my brain hurt. But
conceptually they do make sense... and hey, if semctl(GETNCNT,GETZCNT)
calls are currently incomplete, then yeah, we should fix it.

> I ran a few test cases, and the semncnt and semzcnt counts now match
> the expectation.
> 
> Is anyone aware of an application that uses GETNCNT or GETZCNT?

Given how Oracle uses sysv semaphores I wouldn't be surprised if they
make use of these, specially GETNCNT, for something like "get the amount
of waiters" as opposed to "are there waiters"... but I'm just
speculating here.

I did find that LTP does some calls to GETZNCT, GETNCNT, and these
patches do not break those tests. However, they are pretty bogus since
they always test for zero. That reminds me, it might be worthwhile
adding some more tests in the selftests/ipc dir, we only have some
trivial msgq program, for the rest I pretty much rely on LTP for
correctness runs.

Thanks,
Davidlohr

Re: [PATCH 0/6] ipc/sem.c: Fix semctl(,,{GETNCNT,GETZCNT})

[Michael Kerrisk (man-pages)]

Hi Manfred,

On Sat, May 10, 2014 at 12:03 PM, Manfred Spraul
<manfred@colorfullife.com> wrote:
> Hi all,
>
> According to the man page of semop(), semzcnt or semncnt are increased
> exactly for the operation that couldn't proceed.

Perhaps it's woth noting here that the man page is also pretty close
to the POSIX text that describes semzcnt and semncnt. Form the SUSv4
<sys/sem.h> spec:

semncnt: number of processes waiting for semval to become
        greater than current value.
semzcnt: Number of processes waiting for semval to become 0.

> The Linux implementation always tried to be clever and to increase the counters
> for all operations that might be the reason why a task sleeps.
>
> The following patches fix that and make the code conform to the
> documentation.
>
> The series got fairly long, because I also noticed that semzcnt was calculated
> incorrectly.
>
> What do you think?
> I ran a few test cases, and the semncnt and semzcnt counts now match
> the expectation.

Are any of those test cases in a form that could be used by other to
replicate your results? Also, are there any of those tests that could
go into the source tree?

> Is anyone aware of an application that uses GETNCNT or GETZCNT?

FWIW, grepping the C/CC++ sources from the Fedora 20 source DVD turns
up no uses, AFAICS. Obviously, this tells us nothing about "private"
users that may be out there, such as the Oracle case that Davidlohr
alluded to.

Cheers,

Michael

-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/

Re: [PATCH 0/6] ipc/sem.c: Fix semctl(,,{GETNCNT,GETZCNT})

[Manfred Spraul]

Hi Michael,

On 05/12/2014 10:02 AM, Michael Kerrisk (man-pages) wrote:
> Hi Manfred,
>
> On Sat, May 10, 2014 at 12:03 PM, Manfred Spraul
> <manfred@colorfullife.com> wrote:
>> Hi all,
>>
>> According to the man page of semop(), semzcnt or semncnt are increased
>> exactly for the operation that couldn't proceed.
> Perhaps it's woth noting here that the man page is also pretty close
> to the POSIX text that describes semzcnt and semncnt. Form the SUSv4
> <sys/sem.h> spec:
>
> semncnt: number of processes waiting for semval to become
>          greater than current value.
> semzcnt: Number of processes waiting for semval to become 0.
Good idea, I have updated the comments.

>> The Linux implementation always tried to be clever and to increase the counters
>> for all operations that might be the reason why a task sleeps.
>>
>> The following patches fix that and make the code conform to the
>> documentation.
>>
>> The series got fairly long, because I also noticed that semzcnt was calculated
>> incorrectly.
>>
>> What do you think?
>> I ran a few test cases, and the semncnt and semzcnt counts now match
>> the expectation.
> Are any of those test cases in a form that could be used by other to
> replicate your results? Also, are there any of those tests that could
> go into the source tree?
Unfortunately I have more or less given up writing specific tests, 
instead I use a generic "change" application that allows to create 
multi-semop operations.

# ./createary 5 3
# ./change 5 0 -1 1 -1 2 -1&
# ./getall 5 -v

I wrote a simple test for semncnt, too:
# ./ncnt

https://github.com/manfred-colorfu/ipcsemtest

Re: [PATCH 1/6] ipc/sem.c: further whitespace cleanups

[Manfred Spraul]

Hi Davidlohr,

On 05/12/2014 01:34 AM, Davidlohr Bueso wrote:
> On Sat, 2014-05-10 at 12:03 +0200, Manfred Spraul wrote:
>> Somehow <TAB>$ was overlooked in the last round of whitespace
>> cleanups.
>> Do that now, before making further changes.
> No big deal, but this patch could easily be included in the the second
> patch instead on its own. Thanks.
The patch series you see is the third approach to fix the issue:
- do not store anything, call perform_atomic_semop() in count_semncnt()
   Really cool, no impact at all for semop() - but nasty.
   A sleeping operation could fail suddenly due to -ERANGE.

- store semncnt and semzcnt in struct sem:
   Increase in perform_atomic_semop(), decrease in unlink_queue().

- Now: store the pointer to the blocking op.

That's why the series got so fine-grained...

--
     Manfred

Re: [PATCH 2/6] ipc/sem.c: Bugfix for semctl(,,GETZCNT)

[Davidlohr Bueso]

On Sat, 2014-05-10 at 12:03 +0200, Manfred Spraul wrote:
> GETZCNT is supposed to return the number of threads that wait until
> a semaphore value becomes 0.
> The current implementation overlooks complex operations that contain
> both wait-for-zero operation and operations that alter at least one semaphore.

Indeed. the pending_alter list does represent blocked processes on the
sem. Good catch. Btw, how on earth did you run into this? reading the
code or a real case?

> 
> The patch fixes that.
> It's intentionally copy&paste, this will be cleaned up in the next patch.

Instead I would have expected this patch to actually come after the
count_* refactoring.


> Signed-off-by: Manfred Spraul <manfred@colorfullife.com>

Reviewed-by: Davidlohr Bueso <davidlohr@hp.com>

Re: [PATCH 3/6] ipc/sem.c: remove code duplication

[Davidlohr Bueso]

On Sat, 2014-05-10 at 12:03 +0200, Manfred Spraul wrote:
> count_semzcnt and count_semncnt are more of less identical.
> The patch creates a single function that either counts the number of tasks
> waiting for zero or waiting due to a decrease operation.

This is a nice cleanup.

> Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
> ---
>  ipc/sem.c | 103 ++++++++++++++++++++++++++++++--------------------------------
>  1 file changed, 50 insertions(+), 53 deletions(-)
> 
> diff --git a/ipc/sem.c b/ipc/sem.c
> index dc648f8..821aba7 100644
> --- a/ipc/sem.c
> +++ b/ipc/sem.c
> @@ -47,8 +47,7 @@
>   *   Thus: Perfect SMP scaling between independent semaphore arrays.
>   *         If multiple semaphores in one array are used, then cache line
>   *         trashing on the semaphore array spinlock will limit the scaling.
> - * - semncnt and semzcnt are calculated on demand in count_semncnt() and
> - *   count_semzcnt()
> + * - semncnt and semzcnt are calculated on demand in count_semcnt()
>   * - the task that performs a successful semop() scans the list of all
>   *   sleeping tasks and completes any pending operations that can be fulfilled.
>   *   Semaphores are actively given to waiting tasks (necessary for FIFO).
> @@ -989,6 +988,31 @@ static void do_smart_update(struct sem_array *sma, struct sembuf *sops, int nsop
>  		set_semotime(sma, sops);
>  }
>  
> +/*
> + * check_qop: Test how often a queued operation sleeps on the semaphore semnum
> + */
> +static int check_qop(struct sem_array *sma, int semnum, struct sem_queue *q,
> +			bool count_zero)


Instead of directly calling check_qop(..., true/false), how about doing
something like the following? Should generate better code.

static inline int check_qop_zero(struct sem_array *sma, int semnum, struct sem_queue q)
{
	return check_qop(sma, senum, q, true);
}

static linline int check_qop_nonzero(struct sem_array *sma, int semnum, struct sem_queue q)
{
	return check_qop(sma, senum, q, false);
}

Perhaps instead of nonzero/zero we could replace it with the standard semncnt, semzcnt.

> +{
> +	struct sembuf *sops = q->sops;
> +	int nsops = q->nsops;
> +	int i, semcnt;
> +
> +	semcnt = 0;
> +
> +	for (i = 0; i < nsops; i++) {
> +		if (sops[i].sem_num != semnum)
> +			continue;
> +		if (sops[i].sem_flg & IPC_NOWAIT)
> +			continue;
> +		if (count_zero && sops[i].sem_op == 0)
> +			semcnt++;
> +		if (!count_zero && sops[i].sem_op < 0)
> +			semcnt++;
> +	}
> +	return semcnt;
> +}
> +
>  /* The following counts are associated to each semaphore:
>   *   semncnt        number of tasks waiting on semval being nonzero
>   *   semzcnt        number of tasks waiting on semval being zero
> @@ -998,66 +1022,39 @@ static void do_smart_update(struct sem_array *sma, struct sembuf *sops, int nsop
>   * The counts we return here are a rough approximation, but still
>   * warrant that semncnt+semzcnt>0 if the task is on the pending queue.
>   */
> -static int count_semncnt(struct sem_array *sma, ushort semnum)
> +static int count_semcnt(struct sem_array *sma, ushort semnum,
> +			bool count_zero)
>  {
> -	int semncnt;
> +	struct list_head *l;
>  	struct sem_queue *q;
> +	int semcnt;
>  
> -	semncnt = 0;

nit: can we unify the declaration and assignment?

> -	list_for_each_entry(q, &sma->sem_base[semnum].pending_alter, list) {
> -		struct sembuf *sops = q->sops;
> -		BUG_ON(sops->sem_num != semnum);
> -		if ((sops->sem_op < 0) && !(sops->sem_flg & IPC_NOWAIT))
> -			semncnt++;
> -	}
> +	semcnt = 0;
> +	/* First: check the simple operations. They are easy to evaluate */
> +	if (count_zero)
> +		l = &sma->sem_base[semnum].pending_const;
> +	else
> +		l = &sma->sem_base[semnum].pending_alter;
>  
> -	list_for_each_entry(q, &sma->pending_alter, list) {
> +	list_for_each_entry(q, l, list) {
>  		struct sembuf *sops = q->sops;
> -		int nsops = q->nsops;
> -		int i;
> -		for (i = 0; i < nsops; i++)
> -			if (sops[i].sem_num == semnum
> -			    && (sops[i].sem_op < 0)
> -			    && !(sops[i].sem_flg & IPC_NOWAIT))
> -				semncnt++;
> -	}
> -	return semncnt;
> -}
>  
> -static int count_semzcnt(struct sem_array *sma, ushort semnum)
> -{
> -	int semzcnt;
> -	struct sem_queue *q;
> -
> -	semzcnt = 0;
> -	list_for_each_entry(q, &sma->sem_base[semnum].pending_const, list) {
> -		struct sembuf *sops = q->sops;
>  		BUG_ON(sops->sem_num != semnum);
> -		if ((sops->sem_op == 0) && !(sops->sem_flg & IPC_NOWAIT))
> -			semzcnt++;
> +		BUG_ON(sops->sem_flg & IPC_NOWAIT);
> +		BUG_ON(sops->sem_op > 0);
> +		semcnt++;
>  	}
>  
> -	list_for_each_entry(q, &sma->pending_const, list) {
> -		struct sembuf *sops = q->sops;
> -		int nsops = q->nsops;
> -		int i;
> -		for (i = 0; i < nsops; i++)
> -			if (sops[i].sem_num == semnum
> -			    && (sops[i].sem_op == 0)
> -			    && !(sops[i].sem_flg & IPC_NOWAIT))
> -				semzcnt++;
> -	}
> +	/* Then: check the complex operations. */
>  	list_for_each_entry(q, &sma->pending_alter, list) {
> -		struct sembuf *sops = q->sops;
> -		int nsops = q->nsops;
> -		int i;
> -		for (i = 0; i < nsops; i++)
> -			if (sops[i].sem_num == semnum
> -			    && (sops[i].sem_op == 0)
> -			    && !(sops[i].sem_flg & IPC_NOWAIT))
> -				semzcnt++;
> +		semcnt += check_qop(sma, semnum, q, count_zero);
> +	}
> +	if (count_zero) {
> +		list_for_each_entry(q, &sma->pending_const, list) {
> +			semcnt += check_qop(sma, semnum, q, count_zero);
> +		}
>  	}
> -	return semzcnt;
> +	return semcnt;
>  }
>  
>  /* Free a semaphore set. freeary() is called with sem_ids.rwsem locked
> @@ -1459,10 +1456,10 @@ static int semctl_main(struct ipc_namespace *ns, int semid, int semnum,
>  		err = curr->sempid;
>  		goto out_unlock;
>  	case GETNCNT:
> -		err = count_semncnt(sma, semnum);
> +		err = count_semcnt(sma, semnum, 0);
>  		goto out_unlock;
>  	case GETZCNT:
> -		err = count_semzcnt(sma, semnum);
> +		err = count_semcnt(sma, semnum, 1);

nit: use true/false in count_semcnt().

>  		goto out_unlock;
>  	}
>  

Thanks,
Davidlohr

Re: [PATCH 4/6] ipc/sem.c: Change perform_atomic_semop parameters

[Davidlohr Bueso]

On Sat, 2014-05-10 at 12:03 +0200, Manfred Spraul wrote:
> Right now, perform_atomic_semop gets the content of sem_queue as individual
> fields.
> Changes that, instead pass a pointer to sem_queue.
> 
> This is a preparation for the next patch: it uses
> sem_queue to store the reason why a task must sleep.
> 
> Signed-off-by: Manfred Spraul <manfred@colorfullife.com>

Acked-by: Davidlohr Bueso <davidlohr@hp.com>

Re: [PATCH 2/6] ipc/sem.c: Bugfix for semctl(,,GETZCNT)

[Manfred Spraul]

Hi Davidlohr,

On 05/12/2014 08:11 PM, Davidlohr Bueso wrote:
> On Sat, 2014-05-10 at 12:03 +0200, Manfred Spraul wrote:
>> GETZCNT is supposed to return the number of threads that wait until
>> a semaphore value becomes 0.
>> The current implementation overlooks complex operations that contain
>> both wait-for-zero operation and operations that alter at least one semaphore.
> Indeed. the pending_alter list does represent blocked processes on the
> sem. Good catch. Btw, how on earth did you run into this? reading the
> code or a real case?
Reading the code.
Or more accurately:
Rewriting it, i.e. I first starting coding the new semncnt/semzcnt code, 
then I noticed that the current code is buggy.

>> The patch fixes that.
>> It's intentionally copy&paste, this will be cleaned up in the next patch.
> Instead I would have expected this patch to actually come after the
> count_* refactoring.
>
In this case:
First the bugfix, as simple as possible, then the new features.

--
     Manfred

Re: [PATCH 6/6] ipc/sem.c: make semctl(,,{GETNCNT,GETZCNT}) standard compliant

[Davidlohr Bueso]

On Sat, 2014-05-10 at 12:03 +0200, Manfred Spraul wrote:
> Per definition, a task waits on exactly one semaphore:
> The semaphore from the first operation in the sop array that cannot proceed.
> 
> The Linux implementation never followed the standard, it tried to count all
> semaphores that might be the reason why a task sleeps.
> 
> This patch fixes that.
> 
> Note:
> The implementation assumes that GETNCNT and GETZCNT are rare operations,
> therefore the code counts them only on demand.
> (If they wouldn't be rare, then the non-compliance would have
> been found earlier)
> 
> Signed-off-by: Manfred Spraul <manfred@colorfullife.com>
> ---
>  ipc/sem.c | 37 ++++++++++++++++---------------------
>  1 file changed, 16 insertions(+), 21 deletions(-)
> 
> diff --git a/ipc/sem.c b/ipc/sem.c
> index 22a4c12..5e8bcde 100644
> --- a/ipc/sem.c
> +++ b/ipc/sem.c
> @@ -993,38 +993,33 @@ static void do_smart_update(struct sem_array *sma, struct sembuf *sops, int nsop
>  }
>  
>  /*
> - * check_qop: Test how often a queued operation sleeps on the semaphore semnum
> + * check_qop: Test if a queued operation sleeps on the semaphore semnum
>   */
>  static int check_qop(struct sem_array *sma, int semnum, struct sem_queue *q,
>  			bool count_zero)
>  {
> -	struct sembuf *sops = q->sops;
> -	int nsops = q->nsops;
> -	int i, semcnt;
> +	struct sembuf *sop = q->blocking;
>  
> -	semcnt = 0;
> +	BUG_ON(sop->sem_flg & IPC_NOWAIT);
> +	BUG_ON(sop->sem_op > 0);

Hmm in light of Linus' recent criticism about randomly sprinkling
BUG_ONs in the kernel I'm not sure we want this. Yes, all those calls
are correct from a logical pov and should never occur, however, would
WARN be more suitable instead? I don't know. 

Andrew, any thoughts?

Thanks.

Re: [PATCH 6/6] ipc/sem.c: make semctl(,,{GETNCNT,GETZCNT}) standard compliant

[Andrew Morton]

On Wed, 14 May 2014 07:52:38 -0700 Davidlohr Bueso <davidlohr@hp.com> wrote:

> > --- a/ipc/sem.c
> > +++ b/ipc/sem.c
> > @@ -993,38 +993,33 @@ static void do_smart_update(struct sem_array *sma, struct sembuf *sops, int nsop
> >  }
> >  
> >  /*
> > - * check_qop: Test how often a queued operation sleeps on the semaphore semnum
> > + * check_qop: Test if a queued operation sleeps on the semaphore semnum
> >   */
> >  static int check_qop(struct sem_array *sma, int semnum, struct sem_queue *q,
> >  			bool count_zero)
> >  {
> > -	struct sembuf *sops = q->sops;
> > -	int nsops = q->nsops;
> > -	int i, semcnt;
> > +	struct sembuf *sop = q->blocking;
> >  
> > -	semcnt = 0;
> > +	BUG_ON(sop->sem_flg & IPC_NOWAIT);
> > +	BUG_ON(sop->sem_op > 0);
> 
> Hmm in light of Linus' recent criticism about randomly sprinkling
> BUG_ONs in the kernel I'm not sure we want this. Yes, all those calls
> are correct from a logical pov and should never occur, however, would
> WARN be more suitable instead? I don't know. 

Well, this BUG_ON is so old that a decent approach would be to just
delete the thing, if only Manfred wasn't changing stuff.

Yes, if we can reasonably warn-then-recover then I guess that's worth
doing.

Re: [PATCH 6/6] ipc/sem.c: make semctl(,,{GETNCNT,GETZCNT}) standard compliant

[Manfred Spraul]

Hi Andrew,

On 05/15/2014 12:30 AM, Andrew Morton wrote:
> On Wed, 14 May 2014 07:52:38 -0700 Davidlohr Bueso <davidlohr@hp.com> wrote:
>
>>> -	semcnt = 0;
>>> +	BUG_ON(sop->sem_flg & IPC_NOWAIT);
>>> +	BUG_ON(sop->sem_op > 0);
>> Hmm in light of Linus' recent criticism about randomly sprinkling
>> BUG_ONs in the kernel I'm not sure we want this. Yes, all those calls
>> are correct from a logical pov and should never occur, however, would
>> WARN be more suitable instead? I don't know.
> Well, this BUG_ON is so old that a decent approach would be to just
> delete the thing, if only Manfred wasn't changing stuff.
>
> Yes, if we can reasonably warn-then-recover then I guess that's worth
> doing.
I'll update the series anyway, then I remove the BUG_ONs entirely:
They are just debuging helpers, there is no need to keep them in the 
final code.

--
     Manfred

Re: [PATCH 0/6] ipc/sem.c: Fix semctl(,,{GETNCNT,GETZCNT})

[Davidlohr Bueso]

Hi Manfred,

On Sun, 2014-05-18 at 09:58 +0200, Manfred Spraul wrote:
> Hi Andrew,
> 
> I've applied the changes recommended by Michael and Davidlohr - and I don't 
> have any open points on my list, either.

Please keep the review/ack tags that are collected upon different
versions of the patchset.

Thanks,
Davidlohr

[PATCH 0/6] ipc/sem.c: Fix semctl(,,{GETNCNT,GETZCNT})

[Manfred Spraul]

Hi Andrew,

I've applied the changes recommended by Michael and Davidlohr - and I don't 
have any open points on my list, either.

Therefore: Could you add the series to -mm and move it towards mainline?

Background:

SUSv4 and the man page of semop() clearly define how semncnt or semzcnt must
be updated: Exactly for the single sop that cannot proceed.

The Linux implementation always tried to be clever and to increase the counters
for all operations that might be the reason why a task sleeps.

The following patches fix that and make the code conform to the standard and
the documentation.

The series got fairly long, because I also noticed that semzcnt was calculated
incorrectly.

--
	Manfred