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

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

339–341

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

389

407

538

Why?

552–571

Why not check the bitset instead?

sys/sys/runq.h

89

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

sys/sys/sched.h

80

This change should be committed on its own, IMO.

[olce]

Incorporate suggestions.

[olce]

sys/kern/kern_switch.c

339–341

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?

538

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

552–571

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.

sys/sys/runq.h

57

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.

89

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

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

339–341

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

339–341

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

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.

89

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.