init_main: Switch from sysinit array to SLIST

[cperciva]

Summary

This has two effects:

1. We can mergesort the sysinits instead of bubblesorting them, which

shaves about 2 ms off the boot time in Firecracker.

2. Adding more sysinits (e.g. from a KLD) can be performed by sorting

them and then merging the sorted lists, which is both faster than
the previous "append and sort" approach and avoids needing malloc.

Sponsored by: https://www.patreon.com/cperciva

[cperciva]

This performs as well as D39916 in my testing, and has the advantage of guaranteed O(n log n) rather than merely expected O(n log n) time.

[emaste]

D39916 has the advantage of simplicity and not changing the size of struct sysint though

[jhb]

The bubble sort is also in linker_file_sysinit(). It might be nice to factor out some shared code for the two so that they can not diverge. There are also sysuninit's to consider, but only in linker_file_sysuninit. For those you just want an inverted compar function I think.

sys/kern/init_main.c

907–908

This no longer "works" the same as it no longe lists completed sysinits. That might be ok though.

[jhb]

In D41075#935731, @emaste wrote:

D39916 has the advantage of simplicity and not changing the size of struct sysint though

My worry about using qsort_r is that it recurses, and the kernel stack is not very deep. I'd prefer a non-recursive sort even if it means a pointer in struct sysinit.

[cperciva]

sys/kern/init_main.c

907–908

Ah, I've never used this debugger command so I wasn't sure whether that mattered. If you'd like I could put all of the completed sysinits onto a separate list and have those printed here as well; it would only take a few extra lines of code.

[cperciva]

In D41075#935731, @emaste wrote:

D39916 has the advantage of simplicity and not changing the size of struct sysint though

Agreed, but I figured it was ok to break ABI in HEAD... I wouldn't MFC this to stable/13. (Among other things, firecracker support is never going to be in stable/13.)

[jhb]

sys/kern/init_main.c

907–908

I'm trying to think of when it would be useful to use this, and I think actually what is most useful is the new behavior where you are just seeing what is going to run next vs what has run before. If anything, if someone wants to they can add a "done" list with a separate DDB command to walk that list in the future, but I don't think it's necessary to have that right now.

[imp]

One of the thinkgs that hans and I were talking about when he passed was to make this into a heap so we don't have to sorty it at alll, just have to put it into a heap to walk through. Have you considered that at all? It would mean no changes to the queue stuff are needed, but would require an array of pointers to the sysinit thta can be kept in a heap... This is how CAM implements its priority queue stuff so we never have to sort or resort requests.

[cperciva]

In D41075#937112, @imp wrote:

One of the thinkgs that hans and I were talking about when he passed was to make this into a heap so we don't have to sorty it at alll, just have to put it into a heap to walk through. Have you considered that at all? It would mean no changes to the queue stuff are needed, but would require an array of pointers to the sysinit thta can be kept in a heap... This is how CAM implements its priority queue stuff so we never have to sort or resort requests.

Yes, I considered using a heap. But I thought it was important to keep the sorting stable in order to avoid hard-to-track-down issues with sysinit ordering; using a linked list and a mergesort significantly simplifies the handling of sysinits being added from klds (and removes the requirement that malloc is working prior to registering new sysinits); and I thought having a generic "sort a linked list" macro might be useful in the future considering how many linked lists the kernel uses.

[jrtc27]

You're going to need malloc long before you can possibly hope to kldload, so I don't think that restriction is a big deal, and besides, that exists today.

[cperciva]

In D41075#937291, @jrtc27 wrote:

You're going to need malloc long before you can possibly hope to kldload, so I don't think that restriction is a big deal, and besides, that exists today.

Right. It doesn't exist after this commit. I agree that it's not really an issue for kldload but potentially some code might want to register a sysinit to complete some work later? (Although more likely it would be an unconditional sysinit which sometimes does nothing.)

[cperciva]

Does anyone object to this change? Not sure if the lack of approvals indicates disapproval or disinterest.

[jrtc27]

sys/kern/init_main.c

175

style(9) is no space after *

178

Is that preferred over __unused on the argument?

[cperciva]

Fixes per jrtc27

style (no space after *) and __unused