runq: API rationalization, code factorization, revised implementation

[olce]

Summary

Please see overview of project at D45393.

1. Deduce most parameters, remove machine-specific headers.
2. More selective includes of <sys/runq.h> to reduce pollution
3. Hide function prototypes under _KERNEL
4. API tidy up: 'pri' => 'idx', 'idx' as int, remove runq_remove_idx() (knows some ULE's internals).
5. Code clarity and style
6. Better and more consistent naming; More macros
7. Re-order functions more logically
8. Revamp runq_find*(), new runq_find_range()
9. runq_check(): Re-implement on top of runq_findq()
10. Tidy up and rename runq_setbit() and runq_clrbit()
11. New function runq_is_queue_empty(); Use it in ULE
12. New runq_findq(), common/unique low-level search implementation taking a range of queue indices and a predicate.

[imp]

Hopefully this is actually multiple commits. This change looks on its surface too large to review due to the 12 different things going on. .

[olce]

In D45387#1035485, @imp wrote:

Hopefully this is actually multiple commits. This change looks on its surface too large to review due to the 12 different things going on. .

Yes, 12 commits exactly. Given they are in the same area and some of the same lines are changed by a few of them, I thought it would be best to start with grouping them to give an overview. I can of course publish all of them independently if/when needed. Perhaps some other grouping may ease the review. Let's see what others say.

[jrtc27]

sys/sys/runq.h

57 ↗

(On Diff #139156)

Please check __SIZEOF_LONG__ == 4/8; you care about long here, not pointer size, but ILP32 / LP64 conflate the two (on 64-bit CHERI architectures like Morello and CHERI-RISC-V we have 8 byte long, unchanged, but 16 byte pointers)

[markj]

sys/kern/kern_switch.c

306–308

Missing newlines here and in the other runq_sw_apply() wrappers below.

382

397

455

Why not check the bitset instead?

459

Why?

sys/sys/runq.h

99 ↗

(On Diff #139156)

Is there some reason we can't use bitset(9) for this?

sys/sys/sched.h

80 ↗

(On Diff #139156)

This change should be committed on its own, IMO.

[olce]

Incorporate suggestions.

[olce]

sys/kern/kern_switch.c

306–308

This was kind of "passively deliberate". I usually put an empty new line at start if there are no declarations (old style), but at the same time style(9) now allows not putting them. I'm fine with both approaches.

The lines you're pointing at are indeed somewhat inconsistent with some other uses in this file, including some I introduced. I've just fixed that and settled for the old style. Given the extent of the changes, I could as well switch all relevant parts to the new style. What do you think?

455

That's what runq_first_thread() already does. It also fetches the first available thread which is not strictly necessary here, but then the caller (4BSD) needs to fetch it also, so I don't think this will make a practical difference with respect to the data cache and performance. Calling runq_first_thread() allows to save on instruction cache by not duplicating assembly code (which would be the case using bitset macros; but this could most probably be factorized in a separate function also). I'll see if/how I can rework that.

459

Because it is then used by sched_ule.c in D45390. I could move it to <sys/runq.h> though.

sys/sys/runq.h

57 ↗

(On Diff #139156)

I thought we were only supporting ILP32 or LP64 (see also arch(7)), that's the reason I chose to test for that. I've just changed it with your suggestion instead.

Even if CheriBSD is not FreeBSD, I would suggest that you (or some people working on it) update arch(7) in FreeBSD to reflect what CheriBSD as a downstream consumer does, so that people can generally be aware of such fundamental extensions that need support from upstream.

99 ↗

(On Diff #139156)

No special reason other than the original code didn't use it and, although aware of it, somehow I didn't connect the dots.

It seems some of the functionality that this work requires is missing in bitset(9), and I think it's a good opportunity to add it there. Otherwise, the functionality is really the same, so it would indeed be better to avoid code duplication.

I'll change that as a separate commit, for ease of commit/review, which will be grouped with the commits of this differential revision (so the change will appear here when it's done).

sys/sys/sched.h

80 ↗

(On Diff #139156)

Yes. This whole review in fact consists of 12 commits coalesced. This particular change is (currently) part of commit 4 ("API tidy up: 'pri' => 'idx', 'idx' as int, remove runq_remove_idx() (knows some ULE's internals)."). Does that answer your concern, or would like to see, e.g., the content of that specific commit?

[emaste]

sys/kern/kern_switch.c

306–308

It's the newline between } and static inline void not the first line of the fn Mark's talking about here

[olce]

sys/kern/kern_switch.c

306–308

Checked with Mark, you're right.

This was also deliberate... I wanted to have a single herald comment for both the public function and the callback used to implement it (passed to runq_sw_apply()). Can I keep that like that? Else I'd move the herald comment close to the public function, unless you have some better suggestion?

[olce]

Rebase. Address comments. Remove RQSW_L2BPW.

[olce]

sys/sys/runq.h

57 ↗

(On Diff #139156)

I finally decided to completely remove RQSW_L2BPW and let the compiler optimize / and % with RQSW_BPW as the dividend to simplify code a bit.

99 ↗

(On Diff #139156)

After an attempt to add the missing functionality in bitset(9) (last June), I concluded that doing so wasn't worth it, as it requires a lot of macrology, making it very hard to use, and potentially impacting changes for users (bitset(9)'s model is to have macros define all the required code, leading to unnecessary code and produced assembly duplication; departing from this scheme requires having macros that declare/define common functions which must then be used by consumers).

Additionally, implementing range scanning with predicates efficiently requires knowing the internals of bitset(9), and it seems they are supposed to stay opaque. So, I'm keeping the current implementation for now.

[kib]

sys/kern/kern_switch.c

376

Since runq already means 'run queue', the name is tautological.

sys/kern/sched_ule.c

2673

Since you changing the return type, the function can be written much more concise now.
Also we have TD_IS_IDLETHREAD().

return (TDQ_LOAD(tdq) > (TD_IS_IDLETHREAD(curthread) ? 0 : 1);

sys/sys/runq.h

47 ↗

(On Diff #143028)

Move this somewhere like sys/_param.h or sys/_howmany.h, and include the _header from there and from sys/param.h.

63 ↗

(On Diff #143028)

This is GNU extension, and for all installed headers we do mark it with extension

64 ↗

(On Diff #143028)

ffsl() requires strings.h in userspace, and sys/libkern.h in kernel.

82 ↗

(On Diff #143028)

And this requires sys/queue.h.
To put it differently, I do not see why include some random headers, but not other, from the header.

112 ↗

(On Diff #143028)

constness for the value parameters is not too useful.

sys/sys/sched.h

67 ↗

(On Diff #143028)

Again, there is a lot of stuff that is needed to make the header compilable, and adding a random one there is not useful.

[olce]

Changes prompted by kib@ comments.

[olce]

sys/kern/kern_switch.c

376

Although unfortunate, "run queue" designates the top structure holding all queues, and the predicate here only applies to a single queue within the run queue. The current naming respects that and is deliberate. Completely changing the terminology was out of scope for this change.

sys/kern/sched_ule.c

2673

It could have been even with the previous type, as essentially the returned value has not changed.

That's much easier to read indeed.

sys/sys/runq.h

47 ↗

(On Diff #143028)

Done, see D50880.

64 ↗

(On Diff #143028)

Done here, but removing the include of strings.h later in this series, as I'm then preventing use of <sys/runq.h> from userspace. There's really nothing in this header that is user-serviceable, especially given that this series switches RQ_PPQ to 1 (and RQ_PPQ should just disappear, at least from userland, as it's an implementation detail irrelevant to the outside work after this work).

82 ↗

(On Diff #143028)

Simple: The includes you're talking about were already missing. I just added those related to my own additions.

I've just added them.

112 ↗

(On Diff #143028)

Not useful on x86, as these are passed in registers that are not callee-saved, but might be useful on other architectures. Anyway, I prefer that the signature reflects the expected implementation behavior.

sys/sys/sched.h

67 ↗

(On Diff #143028)

It's not a random one, but just the new one needed given modifications here (and that is useful, even if incomplete).

I've added others now. That said, I'll now refrain for doing such changes in this series. This wastes too much time because every following commit has to be rebased, and we can fix these issues afterwards.

[kib]

sys/kern/kern_switch.c

354

BTW, I am curious, is compiler smart enough to inline through the function pointer and directly emit andl instruction there, instead of generating a call to the op stub? Did you looked at the generated code?

[olce]

sys/kern/kern_switch.c

354

I looked at the generated code a while ago and the compiler was completely getting rid of the stub and inlining runq_sw_set_empty(). I've just check now and that hasn't changed (and same for runq_sw_set_not_empty()).