Skip to contentSkip to conversation

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

PATCH raz ben yehuda 4 participants 7 messages Dec 20, 2011 – Dec 22, 2011

lore
Share & tools
lore
#0 lore raw
Quoted 1 line

From 25aa166505aff2561dd715c927c654d0bbb432ba Mon Sep 17 00:00:00 2001

From: raz <[email protected]>
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.

---
 ipc/sem.c |   51 +++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 49 insertions(+), 2 deletions(-)
ipc/sem.c +49 -2
index 90dc5a1..921056d 100644
@@ -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++;
Signature · 1 line
1.7.5.4
#1 lore raw

Hi raz,

Quoted 12 lines · raz ben yehuda
Quoted 1 line

From 25aa166505aff2561dd715c927c654d0bbb432ba Mon Sep 17 00:00:00 2001

From: raz<[email protected]>
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.

Quoted 2 lines

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?

Quoted 18 lines

SETFIFO is the default for backward compatbility.

---
  ipc/sem.c |   51 +++++++++++++++++++++++++++++++++++++++++++++++++--
  1 files changed, 49 insertions(+), 2 deletions(-)
ipc/sem.c +3 -0
index 90dc5a1..921056d 100644
@@ -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
+*/

ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1358

Quoted 10 lines
ipc/sem.c +10 -0
+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.

Quoted 18 lines
ipc/sem.c +18 -0
+	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) {
+			/*

ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1386

Quoted 10 lines
ipc/sem.c +10 -0
+			* 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

#2 lore raw
Quoted 16 lines · Manfred Spraul

Hi raz,

Quoted 12 lines · raz ben yehuda
Quoted 1 line

From 25aa166505aff2561dd715c927c654d0bbb432ba Mon Sep 17 00:00:00 2001

From: raz<[email protected]>
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.

Quoted 8 lines
Quoted 2 lines

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.

Quoted 64 lines
Quoted 18 lines

SETFIFO is the default for backward compatbility.

---
  ipc/sem.c |   51 +++++++++++++++++++++++++++++++++++++++++++++++++--
  1 files changed, 49 insertions(+), 2 deletions(-)

e

ipc/sem.c +3 -0
index 90dc5a1..921056d 100644
@@ -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
+*/

ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1358

Quoted 10 lines
ipc/sem.c +10 -0
+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.

Quoted 18 lines
ipc/sem.c +18 -0
+	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) {
+			/*

ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1386

Quoted 10 lines
ipc/sem.c +10 -0
+			* 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.

Quoted 3 lines

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 ?

Quoted 2 lines

--
Manfred

#3 lore raw
Quoted 101 lines · raz ben yehuda
Quoted 16 lines · Manfred Spraul

Hi raz,

Quoted 12 lines · raz ben yehuda
Quoted 1 line

From 25aa166505aff2561dd715c927c654d0bbb432ba Mon Sep 17 00:00:00 2001

From: raz<[email protected]>
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.

Quoted 8 lines
Quoted 2 lines

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.

Quoted 64 lines
Quoted 18 lines

SETFIFO is the default for backward compatbility.

---
  ipc/sem.c |   51 +++++++++++++++++++++++++++++++++++++++++++++++++--
  1 files changed, 49 insertions(+), 2 deletions(-)

e

ipc/sem.c +3 -0
index 90dc5a1..921056d 100644
@@ -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
+*/

ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1358

Quoted 10 lines
ipc/sem.c +10 -0
+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.

Quoted 18 lines
ipc/sem.c +18 -0
+	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) {
+			/*

ipc/sem.c static int get_queue_result(struct sem_queue *q) · line 1386

Quoted 10 lines
ipc/sem.c +10 -0
+			* 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.

Quoted 3 lines

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?

Quoted 7 lines

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

#4 lore raw
In reply to raz ben yehuda
Quoted 8 lines · raz ben yehuda

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.

author
#5 lore raw
Quoted 14 lines · Peter Zijlstra
Quoted 8 lines · raz ben yehuda

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.

Quoted 5 lines

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 ?
--
To unsubscribe from this list: send the line "unsubscribe linux-rt-users" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#6 lore raw
Quoted 2 lines · Raz

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.

Quoted 3 lines

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.

Quoted 3 lines

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.