[PATCH] 2.5: MAX_PRIO cleanup

[PATCH] 2.5: MAX_PRIO cleanup

[Robert Love]

Linus,

Attached patch replaces occurrences of the magic numbers representing
maximum priority / maximum RT priority with the (already defined and
used) MAX_PRIO and MAX_RT_PRIO defines.  The patch also contains some
comment additions/changes (particularly to address the double_rq_lock
ambiguity).  Very simple.

This is the invariant cleanup portion of another patch I am working on:
compile-time configurable maximum RT priorities.  But whether you buy
that or not, this is a sane cleanup.

Patch is against 2.5.9, super-duper-please apply.  Thank you,

	Robert Love

diff -urN linux-2.5.9/kernel/sched.c linux/kernel/sched.c
--- linux-2.5.9/kernel/sched.c	Mon Apr 22 18:28:20 2002
+++ linux/kernel/sched.c	Mon Apr 22 22:12:26 2002
@@ -24,17 +24,18 @@
 #include <linux/kernel_stat.h>
 
 /*
- * Priority of a process goes from 0 to 139. The 0-99
- * priority range is allocated to RT tasks, the 100-139
- * range is for SCHED_OTHER tasks. Priority values are
- * inverted: lower p->prio value means higher priority.
+ * Priority of a process goes from 0 to MAX_PRIO-1.  The
+ * 0 to MAX_RT_PRIO-1 priority range is allocated to RT tasks,
+ * the MAX_RT_PRIO to MAX_PRIO range is for SCHED_OTHER tasks.
+ * Priority values are inverted: lower p->prio value means higher
+ * priority.
  */
 #define MAX_RT_PRIO		100
 #define MAX_PRIO		(MAX_RT_PRIO + 40)
 
 /*
  * Convert user-nice values [ -20 ... 0 ... 19 ]
- * to static priority [ 100 ... 139 (MAX_PRIO-1) ],
+ * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
  * and back.
  */
 #define NICE_TO_PRIO(nice)	(MAX_RT_PRIO + (nice) + 20)
@@ -1071,7 +1072,7 @@
  */
 int task_prio(task_t *p)
 {
-	return p->prio - 100;
+	return p->prio - MAX_RT_PRIO;
 }
 
 int task_nice(task_t *p)
@@ -1131,13 +1132,13 @@
 				policy != SCHED_OTHER)
 			goto out_unlock;
 	}
-	
+
 	/*
-	 * Valid priorities for SCHED_FIFO and SCHED_RR are 1..99, valid
-	 * priority for SCHED_OTHER is 0.
+	 * Valid priorities for SCHED_FIFO and SCHED_RR are 1..MAX_RT_PRIO-1,
+	 * valid priority for SCHED_OTHER is 0.
 	 */
 	retval = -EINVAL;
-	if (lp.sched_priority < 0 || lp.sched_priority > 99)
+	if (lp.sched_priority < 0 || lp.sched_priority > MAX_RT_PRIO - 1)
 		goto out_unlock;
 	if ((policy == SCHED_OTHER) != (lp.sched_priority == 0))
 		goto out_unlock;
@@ -1157,7 +1158,7 @@
 	p->policy = policy;
 	p->rt_priority = lp.sched_priority;
 	if (policy != SCHED_OTHER)
-		p->prio = 99 - p->rt_priority;
+		p->prio = (MAX_RT_PRIO - 1) - p->rt_priority;
 	else
 		p->prio = p->static_prio;
 	if (array)
@@ -1237,7 +1238,7 @@
 /**
  * sys_sched_setaffinity - set the cpu affinity of a process
  * @pid: pid of the process
- * @len: length of the bitmask pointed to by user_mask_ptr
+ * @len: length in bytes of the bitmask pointed to by user_mask_ptr
  * @user_mask_ptr: user-space pointer to the new cpu mask
  */
 asmlinkage int sys_sched_setaffinity(pid_t pid, unsigned int len,
@@ -1289,7 +1290,7 @@
 /**
  * sys_sched_getaffinity - get the cpu affinity of a process
  * @pid: pid of the process
- * @len: length of the bitmask pointed to by user_mask_ptr
+ * @len: length in bytes of the bitmask pointed to by user_mask_ptr
  * @user_mask_ptr: user-space pointer to hold the current cpu mask
  */
 asmlinkage int sys_sched_getaffinity(pid_t pid, unsigned int len,
@@ -1371,7 +1372,7 @@
 	switch (policy) {
 	case SCHED_FIFO:
 	case SCHED_RR:
-		ret = 99;
+		ret = MAX_RT_PRIO - 1;
 		break;
 	case SCHED_OTHER:
 		ret = 0;
@@ -1511,6 +1512,12 @@
 	read_unlock(&tasklist_lock);
 }
 
+/*
+ * double_rq_lock - safely lock two runqueues
+ *
+ * Note this does not disable interrupts like task_rq_lock,
+ * you need to do so manually before calling.
+ */
 static inline void double_rq_lock(runqueue_t *rq1, runqueue_t *rq2)
 {
 	if (rq1 == rq2)
@@ -1526,6 +1533,12 @@
 	}
 }
 
+/*
+ * double_rq_unlock - safely unlock two runqueues
+ *
+ * Note this does not restore interrupts like task_rq_unlock,
+ * you need to do so manually after calling.
+ */
 static inline void double_rq_unlock(runqueue_t *rq1, runqueue_t *rq2)
 {
 	spin_unlock(&rq1->lock);
@@ -1675,7 +1688,7 @@
 static int migration_thread(void * bind_cpu)
 {
 	int cpu = cpu_logical_map((int) (long) bind_cpu);
-	struct sched_param param = { sched_priority: 99 };
+	struct sched_param param = { sched_priority: MAX_RT_PRIO - 1 };
 	runqueue_t *rq;
 	int ret;
 

Re: [PATCH] 2.5: MAX_PRIO cleanup

[Ingo Molnar]

On 22 Apr 2002, Robert Love wrote:

> Attached patch replaces occurrences of the magic numbers representing
> maximum priority / maximum RT priority with the (already defined and
> used) MAX_PRIO and MAX_RT_PRIO defines.  The patch also contains some
> comment additions/changes (particularly to address the double_rq_lock
> ambiguity).  Very simple.

i agree that this area needs cleaning up, but i dont agree with all
aspects of your patch. I intentionally left the user-space API side
separate, MAX_RT can in fact be higher than 100 (without changing the
user-space API), the only rule is that it must not be smaller. We in fact
had such a situation once.  It's a perfectly valid goal to have 'super
high prio' kernel-space threads in the future that have in fact some
priority that cannot be reached by user-space threads.

so i've re-done a variation of your patch, which defines USER_MAX_RT_PRIO,
so the user-space API can still stay separate from the kernel-internal
representation.

i've also done some other changes:

>  /*
> - * Priority of a process goes from 0 to 139. The 0-99
> - * priority range is allocated to RT tasks, the 100-139
> - * range is for SCHED_OTHER tasks. Priority values are
> - * inverted: lower p->prio value means higher priority.
> + * Priority of a process goes from 0 to MAX_PRIO-1.  The
> + * 0 to MAX_RT_PRIO-1 priority range is allocated to RT tasks,
> + * the MAX_RT_PRIO to MAX_PRIO range is for SCHED_OTHER tasks.
> + * Priority values are inverted: lower p->prio value means higher
> + * priority.

this i dont agree with either. The point of comments is easy
understanding, so i intentionally kept the 'hard' constants and i'm
updating them constantly - it's much easier to understand how things
happen if it does not happen via a define. The code itself i agree should
stay abstract, but the comments should stay as humanly readable as
possible.

(the set|get_affinity comment fixes i kept, plus the runqueue
double-lock/unlock comments as well, see the attached patch.)

	Ingo

# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher.
# This patch includes the following deltas:
#	           ChangeSet	1.544   -> 1.545  
#	      kernel/sched.c	1.71    -> 1.72   
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 02/04/23	mingo@elte.hu	1.545
# - introduce MAX_USER_RT_PRIO
# - comment fixes from rml
# --------------------------------------------
#
diff -Nru a/kernel/sched.c b/kernel/sched.c
--- a/kernel/sched.c	Tue Apr 23 09:47:59 2002
+++ b/kernel/sched.c	Tue Apr 23 09:47:59 2002
@@ -28,8 +28,11 @@
  * priority range is allocated to RT tasks, the 100-139
  * range is for SCHED_OTHER tasks. Priority values are
  * inverted: lower p->prio value means higher priority.
+ * 
+ * NOTE: MAX_RT_PRIO must not be smaller than MAX_USER_RT_PRIO.
  */
 #define MAX_RT_PRIO		100
+#define MAX_USER_RT_PRIO	100
 #define MAX_PRIO		(MAX_RT_PRIO + 40)
 
 /*
@@ -1071,7 +1074,7 @@
  */
 int task_prio(task_t *p)
 {
-	return p->prio - 100;
+	return p->prio - MAX_USER_RT_PRIO;
 }
 
 int task_nice(task_t *p)
@@ -1137,7 +1140,7 @@
 	 * priority for SCHED_OTHER is 0.
 	 */
 	retval = -EINVAL;
-	if (lp.sched_priority < 0 || lp.sched_priority > 99)
+	if (lp.sched_priority < 0 || lp.sched_priority > MAX_USER_RT_PRIO-1)
 		goto out_unlock;
 	if ((policy == SCHED_OTHER) != (lp.sched_priority == 0))
 		goto out_unlock;
@@ -1157,7 +1160,7 @@
 	p->policy = policy;
 	p->rt_priority = lp.sched_priority;
 	if (policy != SCHED_OTHER)
-		p->prio = 99 - p->rt_priority;
+		p->prio = MAX_USER_RT_PRIO-1 - p->rt_priority;
 	else
 		p->prio = p->static_prio;
 	if (array)
@@ -1237,7 +1240,7 @@
 /**
  * sys_sched_setaffinity - set the cpu affinity of a process
  * @pid: pid of the process
- * @len: length of the bitmask pointed to by user_mask_ptr
+ * @len: length in bytes of the bitmask pointed to by user_mask_ptr
  * @user_mask_ptr: user-space pointer to the new cpu mask
  */
 asmlinkage int sys_sched_setaffinity(pid_t pid, unsigned int len,
@@ -1289,7 +1292,7 @@
 /**
  * sys_sched_getaffinity - get the cpu affinity of a process
  * @pid: pid of the process
- * @len: length of the bitmask pointed to by user_mask_ptr
+ * @len: length in bytes of the bitmask pointed to by user_mask_ptr
  * @user_mask_ptr: user-space pointer to hold the current cpu mask
  */
 asmlinkage int sys_sched_getaffinity(pid_t pid, unsigned int len,
@@ -1371,7 +1374,7 @@
 	switch (policy) {
 	case SCHED_FIFO:
 	case SCHED_RR:
-		ret = 99;
+		ret = MAX_USER_RT_PRIO-1;
 		break;
 	case SCHED_OTHER:
 		ret = 0;
@@ -1511,6 +1514,12 @@
 	read_unlock(&tasklist_lock);
 }
 
+/*
+ * double_rq_lock - safely lock two runqueues
+ *
+ * Note this does not disable interrupts like task_rq_lock,
+ * you need to do so manually before calling.
+ */
 static inline void double_rq_lock(runqueue_t *rq1, runqueue_t *rq2)
 {
 	if (rq1 == rq2)
@@ -1526,6 +1535,12 @@
 	}
 }
 
+/*
+ * double_rq_unlock - safely unlock two runqueues
+ *
+ * Note this does not restore interrupts like task_rq_unlock,
+ * you need to do so manually after calling.
+ */
 static inline void double_rq_unlock(runqueue_t *rq1, runqueue_t *rq2)
 {
 	spin_unlock(&rq1->lock);
@@ -1675,7 +1690,7 @@
 static int migration_thread(void * bind_cpu)
 {
 	int cpu = cpu_logical_map((int) (long) bind_cpu);
-	struct sched_param param = { sched_priority: 99 };
+	struct sched_param param = { sched_priority: MAX_RT_PRIO-1 };
 	runqueue_t *rq;
 	int ret;
 

Re: [PATCH] 2.5: MAX_PRIO cleanup

[Ingo Molnar]

On 23 Apr 2002, Robert Love wrote:

> Now the hard part is abstracting sched_find_first_set for an arbitrary
> MAX_RT_PRIO.

i'd suggest the following: keep the current hand-optimized one for the
bitrange it's good for, and use the find_bit variant for all other values.  
(We had this before, check out some of the older versions of the O(1)  
scheduler.)

	Ingo

Re: [PATCH] 2.5: MAX_PRIO cleanup

[Ingo Molnar]

On 23 Apr 2002, Robert Love wrote:

> > i'd suggest the following: keep the current hand-optimized one for the
> > bitrange it's good for, and use the find_bit variant for all other values.  
> > (We had this before, check out some of the older versions of the O(1)  
> > scheduler.)
> 
> In earlier releases we have
> 
> 	include/asm-i386/mmu_context.h :: sched_find_first_zero_bit
> 
> but that seems to operate on a 168-bit bitmap only.  Around what time
> did we have a routine that operated on arbitrary maps?  What name/file?

hm, perhaps it was only my own internal version then.

in any case, you can use the find_first_zero_bit() library function i
added for exactly this purpose. Any problems with that? It wont be the
fastest option, but it will do.

	Ingo

Re: [PATCH] 2.5: MAX_PRIO cleanup

[Robert Love]

On Tue, 2002-04-23 at 03:53, Ingo Molnar wrote:

> i agree that this area needs cleaning up, but i dont agree with all
> aspects of your patch. I intentionally left the user-space API side
> separate, MAX_RT can in fact be higher than 100 (without changing the
> user-space API), the only rule is that it must not be smaller. We in fact
> had such a situation once.  It's a perfectly valid goal to have 'super
> high prio' kernel-space threads in the future that have in fact some
> priority that cannot be reached by user-space threads.
> 
> so i've re-done a variation of your patch, which defines USER_MAX_RT_PRIO,
> so the user-space API can still stay separate from the kernel-internal
> representation.

This is better.  I did not want to add another define or a new policy
(i.e. user != kernel maximum priority) but doing so is valid.  Actually,
I think there are a lot of kernel threads where we probably want to set
a priority above the max user-space priority.

There are circumstances in user programming where we want a larger
maximum RT priority, too.  In serious RT programming it wouldn't be
uncommon to see 100-1000 priority levels.  I think having such a wide
range is partly to make programming easier (i.e. a lame crutch) but it
does help to more readily layer real-time tasks.

Now the hard part is abstracting sched_find_first_set for an arbitrary
MAX_RT_PRIO.

> i've also done some other changes:
> 
> >  /*
> > - * Priority of a process goes from 0 to 139. The 0-99
> > - * priority range is allocated to RT tasks, the 100-139
> > - * range is for SCHED_OTHER tasks. Priority values are
> > - * inverted: lower p->prio value means higher priority.
> > + * Priority of a process goes from 0 to MAX_PRIO-1.  The
> > + * 0 to MAX_RT_PRIO-1 priority range is allocated to RT tasks,
> > + * the MAX_RT_PRIO to MAX_PRIO range is for SCHED_OTHER tasks.
> > + * Priority values are inverted: lower p->prio value means higher
> > + * priority.
> 
> this i dont agree with either. The point of comments is easy
> understanding, so i intentionally kept the 'hard' constants and i'm
> updating them constantly - it's much easier to understand how things
> happen if it does not happen via a define. The code itself i agree should
> stay abstract, but the comments should stay as humanly readable as
> possible.

Whatever you prefer...

> (the set|get_affinity comment fixes i kept, plus the runqueue
> double-lock/unlock comments as well, see the attached patch.)

Great, thank you.

Linus, Ingo's patch is fine by me.  Apply?

	Robert Love

Re: [PATCH] 2.5: MAX_PRIO cleanup

[Robert Love]

On Tue, 2002-04-23 at 11:23, Ingo Molnar wrote:

> On 23 Apr 2002, Robert Love wrote:
>
> > Now the hard part is abstracting sched_find_first_set for an arbitrary
> > MAX_RT_PRIO.
> 
> i'd suggest the following: keep the current hand-optimized one for the
> bitrange it's good for, and use the find_bit variant for all other values.  
> (We had this before, check out some of the older versions of the O(1)  
> scheduler.)

In earlier releases we have

	include/asm-i386/mmu_context.h :: sched_find_first_zero_bit

but that seems to operate on a 168-bit bitmap only.  Around what time
did we have a routine that operated on arbitrary maps?  What name/file?

Thanks,

	Robert Love

Re: [PATCH] 2.5: MAX_PRIO cleanup

[Robert Love]

On Tue, 2002-04-23 at 12:14, Ingo Molnar wrote:

> hm, perhaps it was only my own internal version then.
> 
> in any case, you can use the find_first_zero_bit() library function i
> added for exactly this purpose. Any problems with that? It wont be the
> fastest option, but it will do.

Err find_first_bit ?

I guess that will work but your hand-coded version is so much faster :)

I would need to abstract sched_find_first_bit into a generic function
that also accepted a size argument.  Something like:

Rename sched_find_first_bit to _sched_find_first_bit, and

#if MAX_RT_PRIO < 120 && MAX_RT_PRIO > 99
#define sched_find_first_bit(b, size)	_sched_find_first_bit(b)
#else
#define sched_find_first_bit(b, size)	find_first_bit(b, size)
#endif

We can let MAX_RT_PRIO go up 120 since the bitmap is actually 160, not
140, size 5*32=160.

Look good?

	Robert Love

Re: [PATCH] 2.5: MAX_PRIO cleanup

[Ingo Molnar]

On 23 Apr 2002, Robert Love wrote:

> Now that I am working on the configurable maximum RT value patch, I see
> why I did this: we can't hardcode the values like "0 to 99" because that
> 99 is set now via a compile-time define.  Even if it defaults to 100, it
> can be a range of values so the comments should be specific and give the
> exact define.

i'm not so sure whether we want to make the last step to make the maximum
RT priority value to be a .config option. Sure we can keep things flexible
so that it's just a matter of a single redefine, but do we really want
users to be able to change the API of Linux in such a way?

the applications which need 1000 RT threads are i suspect specialized, and
since it needs a kernel recompile anyway, it's not a big problem to change
a single constant in the source code - we do that for many other things.  
I'd very much suggest we keep the 0-99 range for RT tasks, it's been well
established and not making it a .config doesnt make it any harder for 1000
RT priority levels to be defined for specific applications.

	Ingo

Re: [PATCH] 2.5: MAX_PRIO cleanup

[Robert Love]

On Tue, 2002-04-23 at 03:53, Ingo Molnar wrote:

> >  /*
> > - * Priority of a process goes from 0 to 139. The 0-99
> > - * priority range is allocated to RT tasks, the 100-139
> > - * range is for SCHED_OTHER tasks. Priority values are
> > - * inverted: lower p->prio value means higher priority.
> > + * Priority of a process goes from 0 to MAX_PRIO-1.  The
> > + * 0 to MAX_RT_PRIO-1 priority range is allocated to RT tasks,
> > + * the MAX_RT_PRIO to MAX_PRIO range is for SCHED_OTHER tasks.
> > + * Priority values are inverted: lower p->prio value means higher
> > + * priority.
> 
> this i dont agree with either. The point of comments is easy
> understanding, so i intentionally kept the 'hard' constants and i'm
> updating them constantly - it's much easier to understand how things
> happen if it does not happen via a define. The code itself i agree should
> stay abstract, but the comments should stay as humanly readable as
> possible.

Now that I am working on the configurable maximum RT value patch, I see
why I did this: we can't hardcode the values like "0 to 99" because that
99 is set now via a compile-time define.  Even if it defaults to 100, it
can be a range of values so the comments should be specific and give the
exact define.

That is why I did it in the invariant patch, anyhow - and I think it
makes the most sense to do it in this patch.

	Robert Love

Re: [PATCH] 2.5: MAX_PRIO cleanup

[Robert Love]

On Tue, 2002-04-23 at 16:44, Ingo Molnar wrote:

> i'm not so sure whether we want to make the last step to make the maximum
> RT priority value to be a .config option. Sure we can keep things flexible
> so that it's just a matter of a single redefine, but do we really want
> users to be able to change the API of Linux in such a way?
>
> the applications which need 1000 RT threads are i suspect specialized, and
> since it needs a kernel recompile anyway, it's not a big problem to change
> a single constant in the source code - we do that for many other things.  
> I'd very much suggest we keep the 0-99 range for RT tasks, it's been well
> established and not making it a .config doesnt make it any harder for 1000
> RT priority levels to be defined for specific applications.

I understand your points - I am doing the patch for those that could
benefit, I felt it is useful enough to be in the kernel.  It is in fact
the only real-time item missing from your scheduler - otherwise it is an
ideal RT scheduler.

It is common for real-time schedules to either have very large RT
priority ranges or allow customizing of these ranges.

I should note that while this changes the API, it should not break any
existing applications (as long as the number only goes up).  Existing
scheduler calls will succeed.  In fact, the only difference to existing
programs would be sched_getparam returning a different maximum RT
priority value.

Finally, it is not so simple as "just setting the define" because of
sched_find_first_bit.  I have a working patch that I will post soon - I
did pretty much what I mentioned in an earlier email where if MAX_PRIO
is outside of a certain range we fall back on using find_first_bit.

Would you be open to a patch to do the rest of the invariant work and
the sched_find_first_bit switch, but not export a configure option?  Or
have I convinced you the configure option is not bad? :-)

The whole patch is not large either way.

	Robert Love