jail: index prison ids to optimize lookups

[yura.tkachenko_gmail.com]

Summary

Add a red-black tree index for prison IDs to accelerate exact JID lookups and finding the next jail during enumeration. Keep the index synchronized with the existing prison list across creation, dying-jail renumbering, and removal, preserving jail visibility semantics.
This will optimize prison lookup from O(n) to O(logn). In case of jls command, it speeds up it from O(n^2) to O(nlogn)
The tradeoff here is additional space to keep RB tree for prison IDS and additional tree maintenance.

Add C ATF tests covering lookup, enumeration, nested visibility, removal, dying-JID reuse, and subtree teardown.
To showcase jail lookups are now several magnitude faster and tree maintenance doesn't cause a noticeable slow down for creation/deletion of jails, add benchmark tooling for measuring performance along with tracing capability covering jail operations (see enclosed baseline and jid index benchmark reports).

jid_index_baseline_report.txt6 KBDownload

jail_jid_w_jid_index_trc.txt6 KBDownload

At 10k jails:

Operation	Baseline	Indexed	Speedup
Default listing	17,754 ms	272 ms	65.35×
JID listing	8,746 ms	123 ms	70.93×
Syscall enumeration	8,996 ms	71 ms	126.28×
Syscall JID lookup batch	8,007 ms	60 ms	134.53×

Test Plan

Build tests:

cd /usr/src/tests/sys/kern
make obj && make depend && make && make install
cd /usr/tests/sys/kern
kyua test jail_jid_index

Expected result:

jail_jid_index:dying_jid_reuse  ->  passed  [0.032s]
jail_jid_index:enumeration_after_removal  ->  passed  [0.006s]
jail_jid_index:lookup_enumeration  ->  passed  [0.007s]
jail_jid_index:nested_visibility  ->  passed  [0.007s]
jail_jid_index:subtree_removal  ->  passed  [0.006s]

Executing Benchmark suite:
On the kernel without jid index:

> cd /usr/src/tools/test/jail
> sudo make test MAX_JAILS=10000 LIST_EVERY=1000 OUTPUT=baseline
> make report INPUT=baseline

On the kernel with the patch applied:

> cd /usr/src/tools/test/jail
> sudo make test MAX_JAILS=10000 LIST_EVERY=1000 OUTPUT=jid_index
> make report INPUT=jid_index