sched_4bsd: use DPCPU for runq

[minsoochoo0122_proton.me]

Summary

'struct runq' currently takes 4128 bytes per cpu. With the 1024 default
value for MAXCPU on amd64, runq_pcpu[] takes more than 4 MiB of memory.
Considering that most systems have less than 32 cores with SMT, this is
clearly a waste of memory.

Besides providing per-CPU runqueues, runq_pcpu[] is used to determine
the CPU ID of a given thread's associated runqueue through pointer
arithmetic.

To save space, move the runqueues to per-CPU fields then add 'int
ts_rqcpu' and remove 'struct runq *ts_runq' from 'struct ts_sched' to
track the per-cpu runqueue it is on. Per-CPU structures indeed are only
allocated for present CPUs. Note that this is different from td_oncpu
which is set to NOCPU when it is not running. Set ts_sched to NOCPU when
it is running on the global runqueue although the value becomes
irrelevant under that circumstance.

Drop SKE_RUNQ_PCPU() macro as it can simply replaced with `ts_rqcpu !=
NOCPU`. Instead, introduce TS_RUNQ_PTR() macro to get pointer to the
runq for runq_add() and runq_remove().

The added 'ts_rqcpu' field consumes 4 more bytes per thread, to be
compared with the savings of 4128 * (MAXCPU - ncpu_on_system) / 4. For
example, on a 32-core system, we can save around 4 MB of memory when
there are no threads and the memory efficiency will hold until there are
1,023,744 threads.

[minsoochoo0122_proton.me]

update commit message (int -> u_int)

[olce]

The commit message is not completely clear on first read, in particular with respect to why the change here saves memory. Also, there are typos. Suggestions:

struct runq currently takes 4128 bytes per cpu.
With MAXPU, the runq_pcpu takes more than 4 MiB of memory.

"With the 1024 default value for MAXCPU on amd64, runq_pcpu[] takes more than..."

Considering that most systems have less than 32 cores with SMT, this is clearly waste of memory.

"...clearly a waste..."

Add something like:

Besides providing per-CPU runqueues, runq_pcpu[] is used to determine the CPU ID of a given thread's associated runqueue through pointer arithmetic."

To save space, move the runqueues to per-CPU fields and...

followed by the existing text:

Add a u_int ts_rqcpu in struct ts_sched to track the pcpu runq it is on.

Add, e.g.:

Per-CPU structures indeed are only allocated for present CPUs.

(snip)

To keep.

Since u_int takes 4 bytes on amd64, we can spend memory up to 4128 *
(MAXCPU - ncpu_on_system) / 4.

This is really unclear at first. Replace by something like:
"The added 'ts_rqcpu' field consumes 4 more bytes per thread, to be compared with the savings of ... bytes."

For example, on a 32-core system, we can
save around 4 MB of memory when there are no threads and the memory
efficiency will hold until there are 1,023,744 threads.

Not sure I would keep the example, but if you want to:
"Savings happens on a 32-core system up to a little more than 1M threads, and for a 512-core system a little more than 500k threads."

The actual numbers are subject to code changes. In particular, the suggestions below obsolete the last two paragraphs.

---

Now, on the code itself.

Everywhere you introduced prev_length and used a DPCPU_*GET() and DPCPU_*SET() pair to update runq_length, please consider using instead the incrementation or decrementation operators around (*DPCPU_*PTR()), as this causes less churn and makes it (marginally) easier to understand what these accesses are about.

Introducing ts_rqcpu actually makes ts_runq redundant, so please remove that last field, possibly adding helpers to get the corresponding runqueue/change the runqueue length variable, and renaming the global runq to global_runq so that you can introduce runq local variables (separate commit). With this, there is no case where memory consumption isn't improved by this whole change, for absolutely zero change in performance if I'm not mistaken (except for sched_4bsd_rem()'s access, but that looks negligible).

See also inline comments.

sys/kern/sched_4bsd.c

102–103

I'd rather use a fixed value here, such as UINT_MAX, this makes for easier debugging (or switch to an int and use -1).

Actually, there is already a NOCPU for you to use. Try to fit a reference to it in the first line's comment, suppressing the second line bracketed by SMP if possible.

Oh, and you'll have to suppress the SMP bracketing when removing ts_runq.

1382

See some inline comment above for the value to use.

I'd put this reset under INVARIANTS. In any case, resetting it alone is not terribly useful if not accompanied by a check then ts_rqcpu is supposed to be used as a CPU ID.

But if going a step further, as suggested in the herald comment, then this setting must occur also on !INVARIANTS.

[minsoochoo0122_proton.me]

In D58000#1331427, @olce wrote:

Introducing ts_rqcpu actually makes ts_runq redundant, so please remove that last field, possibly adding helpers to get the corresponding runqueue/change the runqueue length variable, and renaming the global runq to global_runq so that you can introduce runq local variables (separate commit). With this, there is no case where memory consumption isn't improved by this whole change, for absolutely zero change in performance if I'm not mistaken (except for sched_4bsd_rem()'s access, but that looks negligible).

sched_4bsd_choose() already uses the name rq as a pointer to struct runq so I think we can do the same for other local variables. However, if you feel that the renaming is necessary and local variables should be named runq, I'm learning towards runq_global over global_runq since it has similar naming to runq_pcpu although the name is not grammatically correct.

How do you think?

[olce]

However, if you feel that the renaming is necessary and local variables should be named runq, I'm learning towards runq_global over global_runq since it has similar naming to runq_pcpu although the name is not grammatically correct.

Yes, I think we should do the rename as the current name is too confusing (I haven't checked but I suspect it comes from an era where there was only the global runqueue, so runq was fine back then). Let's go for runq_global then.

[minsoochoo0122_proton.me]

Update commit message
Reflect @olce's suggestion

[minsoochoo0122_proton.me]

sys/kern/sched_4bsd.c

102–103

I wanted to include "the current thread's runq" in the comment, but the 80 column limit didn't allow me by one character.

I don't know how to have fixed value for c structs. I did some search on the internet and found out that it's impossible. However, sched_4bsd_add() initializes this in all code paths.

1382

The ts->ts_rqcpu == NOCPU is used in the new TS_RUNQ_PTR() macro so I didn't put the reset under INVARIANTS.

ts_runq can track runq_global as well, but I cannot do it with ts_rqcpu. Thus I'm using NOCPU (alias to -1) to route ts_rqcpu to runq_global.

[olce]

Looks good (see also inline comment). Could you update the Phab revision's description with the new commit message?

sys/kern/sched_4bsd.c

102–103

Sorry, that wasn't clear, with "fixed" value, I meant a value that does not depend on MAXCPU.

The 80-column limit is not completely strict. If you can fit the comment in a 81-column line, then I'd go for that instead of two lines.

About automatic structure member initialization, e.g., from an initializer coming from the structure declaration, yes, to my knowledge, this is not possible even in C23.

[minsoochoo0122_proton.me]

Fit comment in one line (99 columns)

[minsoochoo0122_proton.me]

sys/kern/sched_4bsd.c

102–103

It takes 99 columns minimum, but I think it's fine.

[olce]

In D58000#1332042, @minsoochoo0122_proton.me wrote:

Fit comment in one line (99 columns)

Ah, 99 columns is really a lot. See the inline comment for a suggestion under 80 columns. If you want something longer, then move the comment to the line just before the member itself.

sys/kern/sched_4bsd.c

100

A suggestion just at the 80-char limit.

[minsoochoo0122_proton.me]

Update comment (83 columns)

[minsoochoo0122_proton.me]

Actually it works without "On " in the front