Subject: [PATCH 2/2] priority System V Semaphores

Subject: [PATCH 2/2] priority System V Semaphores

[raz ben yehuda]

>From 25aa166505aff2561dd715c927c654d0bbb432ba Mon Sep 17 00:00:00 2001
From: raz <raziebe@gmail.com>
Date: Tue, 20 Dec 2011 22:54:56 +0200


Add positioning routine find_pos. find_pos returns
the place where to put the sleeper before.
I sort only rt tasks, OTHER policy is pushed back in
queue. I do not distinct between SCHED_RR and SCHED_FIFO
policies and they are treated as a single policy
for the sorting algorithm.

SETPRIO operates only when user issues a single semop
operation and not an array of opretions.

SETFIFO is the default for backward compatbility.

Signed-off-by: raz <raziebe@gmail.com>
---
 ipc/sem.c |   51 +++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 49 insertions(+), 2 deletions(-)

diff --git a/ipc/sem.c b/ipc/sem.c
index 90dc5a1..921056d 100644
--- a/ipc/sem.c
+++ b/ipc/sem.c
@@ -1343,6 +1343,51 @@ static int get_queue_result(struct sem_queue *q)
 	return error;
 }
 
+/*
+ * find the best place to put the task sorted by rt prio
+*/
+static struct list_head *find_pos(struct sem *curr, int alter,
+		struct task_struct *p)
+{
+	struct sem_queue *q;
+	struct sem_queue *ret_pos = NULL;
+	struct list_head *tasks_queue = &curr->sem_pending;
+
+	if (!alter)
+		return tasks_queue;
+
+	if (!(curr->flags & PRIO_SEM))
+		return tasks_queue;
+	/*
+	 *  make no effort to sort SCHED_OTHER,
+	 *  just push task to the back of the queue.
+	*/
+	if (!(p->policy == SCHED_FIFO || p->policy == SCHED_RR))
+		return tasks_queue;
+	/*
+	 *  make no distinction between SCHED_FIFO
+	 *  and SCHED_RR policies.
+	 */
+	list_for_each_entry(q, tasks_queue, simple_list) {
+		struct task_struct *t;
+
+		t  = q->sleeper;
+		if (current->rt_priority == t->rt_priority) {
+			/*
+			* push in a FIFO manner
+			* tasks in same priority
+			*/
+			ret_pos = q;
+			continue;
+		}
+		if (current->rt_priority < t->rt_priority)
+			continue;
+		return &q->simple_list;
+	}
+	if (ret_pos)
+		return ret_pos->simple_list.next;
+	return tasks_queue;
+}
 
 SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
 		unsigned, nsops, const struct timespec __user *, timeout)
@@ -1357,6 +1402,7 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
 	unsigned long jiffies_left = 0;
 	struct ipc_namespace *ns;
 	struct list_head tasks;
+	struct list_head *pending_pos;
 
 	ns = current->nsproxy->ipc_ns;
 
@@ -1478,10 +1524,11 @@ SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
 		struct sem *curr;
 		curr = &sma->sem_base[sops->sem_num];
 
+		pending_pos = find_pos(curr, alter, current);
 		if (alter)
-			list_add_tail(&queue.simple_list, &curr->sem_pending);
+			list_add_tail(&queue.simple_list, pending_pos);
 		else
-			list_add(&queue.simple_list, &curr->sem_pending);
+			list_add(&queue.simple_list, pending_pos);
 	} else {
 		INIT_LIST_HEAD(&queue.simple_list);
 		sma->complex_count++;
-- 
1.7.5.4

Re: Subject: [PATCH 2/2] priority System V Semaphores

[Manfred Spraul]

Hi raz,


On 12/20/2011 11:23 PM, raz ben yehuda wrote:
> > From 25aa166505aff2561dd715c927c654d0bbb432ba Mon Sep 17 00:00:00 2001
> From: raz<raziebe@gmail.com>
> Date: Tue, 20 Dec 2011 22:54:56 +0200
>
>
> Add positioning routine find_pos. find_pos returns
> the place where to put the sleeper before.
> I sort only rt tasks, OTHER policy is pushed back in
> queue. I do not distinct between SCHED_RR and SCHED_FIFO
> policies and they are treated as a single policy
> for the sorting algorithm.
>
> SETPRIO operates only when user issues a single semop
> operation and not an array of opretions.
As far as I can see, the advantages of sysvsem are backward 
compatibility and the ability to use complex ops.
You propose to add a new feature that doesn't work on complex ops.

Are there any apps that use SETPRIO?
What is the use case?
> SETFIFO is the default for backward compatbility.
>
> Signed-off-by: raz<raziebe@gmail.com>
> ---
>   ipc/sem.c |   51 +++++++++++++++++++++++++++++++++++++++++++++++++--
>   1 files changed, 49 insertions(+), 2 deletions(-)
>
> diff --git a/ipc/sem.c b/ipc/sem.c
> index 90dc5a1..921056d 100644
> --- a/ipc/sem.c
> +++ b/ipc/sem.c
> @@ -1343,6 +1343,51 @@ static int get_queue_result(struct sem_queue *q)
>   	return error;
>   }
>
> +/*
> + * find the best place to put the task sorted by rt prio
> +*/
> +static struct list_head *find_pos(struct sem *curr, int alter,
> +		struct task_struct *p)
> +{
> +	struct sem_queue *q;
> +	struct sem_queue *ret_pos = NULL;
> +	struct list_head *tasks_queue =&curr->sem_pending;
> +
> +	if (!alter)
> +		return tasks_queue;
> +
Tasks that do not alter anything end up first - IMHO correct.

> +	if (!(curr->flags&  PRIO_SEM))
> +		return tasks_queue;
> +	/*
> +	 *  make no effort to sort SCHED_OTHER,
> +	 *  just push task to the back of the queue.
> +	*/
> +	if (!(p->policy == SCHED_FIFO || p->policy == SCHED_RR))
> +		return tasks_queue;
> +	/*
> +	 *  make no distinction between SCHED_FIFO
> +	 *  and SCHED_RR policies.
> +	 */
> +	list_for_each_entry(q, tasks_queue, simple_list) {
> +		struct task_struct *t;
> +
> +		t  = q->sleeper;
> +		if (current->rt_priority == t->rt_priority) {
> +			/*
> +			* push in a FIFO manner
> +			* tasks in same priority
> +			*/
> +			ret_pos = q;
> +			continue;
> +		}
> +		if (current->rt_priority<  t->rt_priority)
> +			continue;
> +		return&q->simple_list;
> +	}
Here in the loop, non-alter tasks are evaluated as well.
I think that's wrong, it could starve non-alter tasks.

e.g. queue:
- high prio non-alter
- low prio non-alter.

Now a medium prio alter task is added.
I think it will end up in the wrong position (before the low-prio 
non-alter task), correct?

--
     Manfred

Re: Subject: [PATCH 2/2] priority System V Semaphores

[raz ben yehuda]

On Wed, 2011-12-21 at 19:31 +0100, Manfred Spraul wrote:
> Hi raz,
> 
> 
> On 12/20/2011 11:23 PM, raz ben yehuda wrote:
> > > From 25aa166505aff2561dd715c927c654d0bbb432ba Mon Sep 17 00:00:00 2001
> > From: raz<raziebe@gmail.com>
> > Date: Tue, 20 Dec 2011 22:54:56 +0200
> >
> >
> > Add positioning routine find_pos. find_pos returns
> > the place where to put the sleeper before.
> > I sort only rt tasks, OTHER policy is pushed back in
> > queue. I do not distinct between SCHED_RR and SCHED_FIFO
> > policies and they are treated as a single policy
> > for the sorting algorithm.
> >
> > SETPRIO operates only when user issues a single semop
> > operation and not an array of opretions.
> As far as I can see, the advantages of sysvsem are backward 
> compatibility and the ability to use complex ops.
> You propose to add a new feature that doesn't work on complex ops.
> 
> Are there any apps that use SETPRIO?
> What is the use case?
Vxworks is the use case. And there are plenty of companies with
vxWorks software and in i believe they will migrate sooner or later to
PreemptRT.  My current company uses old wrapper software that implements
vxWorks semaphores as system V semaphores. vxWorks semaphores have a priority
feature which is widely used.
I will probably change it some time in the future to posix semaphores , but posix 
semaphores are implemented in glibc with futexes and atomic ops and i rather 
mess with kernel and not glibc. funny , but true. glibc is harder. 

> > SETFIFO is the default for backward compatbility.
> >
> > Signed-off-by: raz<raziebe@gmail.com>
> > ---
> >   ipc/sem.c |   51 +++++++++++++++++++++++++++++++++++++++++++++++++--
> >   1 files changed, 49 insertions(+), 2 deletions(-)
> >e
> > diff --git a/ipc/sem.c b/ipc/sem.c
> > index 90dc5a1..921056d 100644
> > --- a/ipc/sem.c
> > +++ b/ipc/sem.c
> > @@ -1343,6 +1343,51 @@ static int get_queue_result(struct sem_queue *q)
> >   	return error;
> >   }
> >
> > +/*
> > + * find the best place to put the task sorted by rt prio
> > +*/
> > +static struct list_head *find_pos(struct sem *curr, int alter,
> > +		struct task_struct *p)
> > +{
> > +	struct sem_queue *q;
> > +	struct sem_queue *ret_pos = NULL;
> > +	struct list_head *tasks_queue =&curr->sem_pending;
> > +
> > +	if (!alter)
> > +		return tasks_queue;
> > +
> Tasks that do not alter anything end up first - IMHO correct.
> 
> > +	if (!(curr->flags&  PRIO_SEM))
> > +		return tasks_queue;
> > +	/*
> > +	 *  make no effort to sort SCHED_OTHER,
> > +	 *  just push task to the back of the queue.
> > +	*/
> > +	if (!(p->policy == SCHED_FIFO || p->policy == SCHED_RR))
> > +		return tasks_queue;
> > +	/*
> > +	 *  make no distinction between SCHED_FIFO
> > +	 *  and SCHED_RR policies.
> > +	 */
> > +	list_for_each_entry(q, tasks_queue, simple_list) {
> > +		struct task_struct *t;
> > +
> > +		t  = q->sleeper;
> > +		if (current->rt_priority == t->rt_priority) {
> > +			/*
> > +			* push in a FIFO manner
> > +			* tasks in same priority
> > +			*/
> > +			ret_pos = q;
> > +			continue;
> > +		}
> > +		if (current->rt_priority<  t->rt_priority)
> > +			continue;
> > +		return&q->simple_list;
> > +	}
> Here in the loop, non-alter tasks are evaluated as well.
> I think that's wrong, it could starve non-alter tasks.
> e.g. queue:
> - high prio non-alter
> - low prio non-alter.
> 
> Now a medium prio alter task is added.
> I think it will end up in the wrong position (before the low-prio 
> non-alter task), correct?
hammm.. correct. thanks. I did not check non-alter tasks at all. The entire queue might be a total mess. 
I will sort non alter tasks as well.
Also, this patch is missing scenario where a task priority is changed whilst it is waiting. 
I fixed that already. 

Who maintains this code ? 

> --
>      Manfred

Re: Subject: [PATCH 2/2] priority System V Semaphores

[Steven Rostedt]

On Wed, 2011-12-21 at 22:48 +0200, raz ben yehuda wrote:
> On Wed, 2011-12-21 at 19:31 +0100, Manfred Spraul wrote:
> > Hi raz,
> > 
> > 
> > On 12/20/2011 11:23 PM, raz ben yehuda wrote:
> > > > From 25aa166505aff2561dd715c927c654d0bbb432ba Mon Sep 17 00:00:00 2001
> > > From: raz<raziebe@gmail.com>
> > > Date: Tue, 20 Dec 2011 22:54:56 +0200
> > >
> > >
> > > Add positioning routine find_pos. find_pos returns
> > > the place where to put the sleeper before.
> > > I sort only rt tasks, OTHER policy is pushed back in
> > > queue. I do not distinct between SCHED_RR and SCHED_FIFO
> > > policies and they are treated as a single policy
> > > for the sorting algorithm.
> > >
> > > SETPRIO operates only when user issues a single semop
> > > operation and not an array of opretions.
> > As far as I can see, the advantages of sysvsem are backward 
> > compatibility and the ability to use complex ops.
> > You propose to add a new feature that doesn't work on complex ops.
> > 
> > Are there any apps that use SETPRIO?
> > What is the use case?
> Vxworks is the use case. And there are plenty of companies with
> vxWorks software and in i believe they will migrate sooner or later to
> PreemptRT.  My current company uses old wrapper software that implements
> vxWorks semaphores as system V semaphores. vxWorks semaphores have a priority
> feature which is widely used.
> I will probably change it some time in the future to posix semaphores , but posix 
> semaphores are implemented in glibc with futexes and atomic ops and i rather 
> mess with kernel and not glibc. funny , but true. glibc is harder. 
> 
> > > SETFIFO is the default for backward compatbility.
> > >
> > > Signed-off-by: raz<raziebe@gmail.com>
> > > ---
> > >   ipc/sem.c |   51 +++++++++++++++++++++++++++++++++++++++++++++++++--
> > >   1 files changed, 49 insertions(+), 2 deletions(-)
> > >e
> > > diff --git a/ipc/sem.c b/ipc/sem.c
> > > index 90dc5a1..921056d 100644
> > > --- a/ipc/sem.c
> > > +++ b/ipc/sem.c
> > > @@ -1343,6 +1343,51 @@ static int get_queue_result(struct sem_queue *q)
> > >   	return error;
> > >   }
> > >
> > > +/*
> > > + * find the best place to put the task sorted by rt prio
> > > +*/
> > > +static struct list_head *find_pos(struct sem *curr, int alter,
> > > +		struct task_struct *p)
> > > +{
> > > +	struct sem_queue *q;
> > > +	struct sem_queue *ret_pos = NULL;
> > > +	struct list_head *tasks_queue =&curr->sem_pending;
> > > +
> > > +	if (!alter)
> > > +		return tasks_queue;
> > > +
> > Tasks that do not alter anything end up first - IMHO correct.
> > 
> > > +	if (!(curr->flags&  PRIO_SEM))
> > > +		return tasks_queue;
> > > +	/*
> > > +	 *  make no effort to sort SCHED_OTHER,
> > > +	 *  just push task to the back of the queue.
> > > +	*/
> > > +	if (!(p->policy == SCHED_FIFO || p->policy == SCHED_RR))
> > > +		return tasks_queue;
> > > +	/*
> > > +	 *  make no distinction between SCHED_FIFO
> > > +	 *  and SCHED_RR policies.
> > > +	 */
> > > +	list_for_each_entry(q, tasks_queue, simple_list) {
> > > +		struct task_struct *t;
> > > +
> > > +		t  = q->sleeper;
> > > +		if (current->rt_priority == t->rt_priority) {
> > > +			/*
> > > +			* push in a FIFO manner
> > > +			* tasks in same priority
> > > +			*/
> > > +			ret_pos = q;
> > > +			continue;
> > > +		}
> > > +		if (current->rt_priority<  t->rt_priority)
> > > +			continue;
> > > +		return&q->simple_list;
> > > +	}
> > Here in the loop, non-alter tasks are evaluated as well.
> > I think that's wrong, it could starve non-alter tasks.
> > e.g. queue:
> > - high prio non-alter
> > - low prio non-alter.
> > 
> > Now a medium prio alter task is added.
> > I think it will end up in the wrong position (before the low-prio 
> > non-alter task), correct?
> hammm.. correct. thanks. I did not check non-alter tasks at all. The entire queue might be a total mess. 
> I will sort non alter tasks as well.
> Also, this patch is missing scenario where a task priority is changed whilst it is waiting. 
> I fixed that already. 
> 
> Who maintains this code ? 
> 

It's mainly core kernel code and only changes when true changes are
made. An update could be done to extend its use as long as it doesn't
break any tools in the process. IOW, it must stay backward compatible.

-- Steve

Re: Subject: [PATCH 2/2] priority System V Semaphores

[Peter Zijlstra]

On Wed, 2011-12-21 at 22:48 +0200, raz ben yehuda wrote:
> Vxworks is the use case. And there are plenty of companies with
> vxWorks software and in i believe they will migrate sooner or later to
> PreemptRT.  My current company uses old wrapper software that implements
> vxWorks semaphores as system V semaphores. vxWorks semaphores have a priority
> feature which is widely used.
> I will probably change it some time in the future to posix semaphores , but posix 
> semaphores are implemented in glibc with futexes and atomic ops and i rather 
> mess with kernel and not glibc. funny , but true. glibc is harder. 

Semaphores are a fscking trainwreck for real-time programming. Don't use
them, full stop. If you do, you're doing it wrong, it's really that
simple.

Use PI mutexes, which are already fully supported in glibc, no extra
patching needed.

Full NAK for any and all priority fudging for any semaphore
implementation.

Re: Subject: [PATCH 2/2] priority System V Semaphores

[Raz]

On Thu, Dec 22, 2011 at 10:59 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Wed, 2011-12-21 at 22:48 +0200, raz ben yehuda wrote:
>> Vxworks is the use case. And there are plenty of companies with
>> vxWorks software and in i believe they will migrate sooner or later to
>> PreemptRT.  My current company uses old wrapper software that implements
>> vxWorks semaphores as system V semaphores. vxWorks semaphores have a priority
>> feature which is widely used.
>> I will probably change it some time in the future to posix semaphores , but posix
>> semaphores are implemented in glibc with futexes and atomic ops and i rather
>> mess with kernel and not glibc. funny , but true. glibc is harder.
>
> Semaphores are a fscking trainwreck for real-time programming. Don't use
> them, full stop. If you do, you're doing it wrong, it's really that
> simple.
>
> Use PI mutexes, which are already fully supported in glibc, no extra
> patching needed.
>
> Full NAK for any and all priority fudging for any semaphore
> implementation.
please correct me if am wrong, " posix semaphores
are implemented with pi mutex. ..?" I need a counting semaphore.
vxWorks priority/fifo semaphores are different from posix semaphores in
that the behaviour is defined on the semaphore and not the thread.
Q: what happens if I want one posix semahore to be FIFO and another
posix semaphore to be PRIO while both are used by the same
thread.should i to change policies each time ?

Re: Subject: [PATCH 2/2] priority System V Semaphores

[Peter Zijlstra]

On Thu, 2011-12-22 at 15:00 +0200, Raz wrote:

> please correct me if am wrong, " posix semaphores
> are implemented with pi mutex. ..?" 

Probably not, that would be pointless. They might be implemented using a
mutex, but I've already looked at glibc this month and my eyes can't
handle more.

> I need a counting semaphore.
> vxWorks priority/fifo semaphores are different from posix semaphores in
> that the behaviour is defined on the semaphore and not the thread.

That doesn't make them sane locking primitives.

> Q: what happens if I want one posix semahore to be FIFO and another
> posix semaphore to be PRIO while both are used by the same
> thread.should i to change policies each time ?

If you need a counting semaphore your program is very likely not a
correct real-time application. So who cares what order things are woken
up in.

Semaphores don't have lock owners, therefore priority inheritance and
related schemes don't work, therefore you suffer from priority inversion
and thus your program is invalid.

Seriously, forget semaphores exist, they're a hysterical accident.