Kernel

Kernel code contains algorithms that look unnecessarily peculiar until the constraints are visible. Population count, the number of set bits in a machine word, is a good example.

The obvious C version examines every bit:

unsigned int count_bits(unsigned long word)
{
        unsigned int n = 0;

        while (word) {
                n += word & 1;
                word >>= 1;
        }
        return n;
}

This performs one iteration for every bit position up to the highest set bit. A sparse bitmap still pays for all the zeros in between.

Brian Kernighan’s familiar operation removes the lowest set bit at each iteration:

unsigned int count_bits(unsigned long word)
{
        unsigned int n = 0;

        while (word) {
                word &= word - 1;
                n++;
        }
        return n;
}

Subtracting one flips the lowest set bit to zero and turns lower zeros into ones. The & keeps everything above that bit and clears the changed suffix. The loop therefore runs once per set bit.

That is excellent for sparse words and less impressive for dense ones. Kernels also use table lookups and architecture-specific instructions where available. A byte table has predictable work but adds memory access; a processor instruction can win decisively but needs dispatch or compile-time selection. There is no universally fastest source fragment independent of data and machine.

Word width matters too. Kernel types and helpers make that choice explicit, while a casual userspace benchmark can accidentally compare different widths and announce a victory produced by less work.

I benchmarked the two loops over generated sparse and dense arrays, keeping generation outside the timed section. As expected, the clear-lowest-bit version dominated sparse input. Dense input narrowed the gap considerably. Repeating one constant word produced lovely numbers and measured the compiler more than the routine, so I stopped doing that.

The broader lesson from kernel work is to understand the representation before admiring the trick. Bitmaps pack state compactly and permit word-at-a-time operations, but contention, cache placement, and scan direction can matter more than shaving an instruction from population count.

I like this algorithm because its mechanism fits in one sentence and its performance caveat requires another. Most optimization stories should have both sentences. The ones with only the first usually end in a benchmark that accidentally proves the author’s laptop exists.

I had two versions of a parser. One finished faster, so I declared victory and nearly deleted the slower one. Before doing that, I tried the new perf tools included with recent kernels and discovered that my explanation for the improvement was wrong.

The kernel’s performance-counter infrastructure provides a common way to measure hardware and software events. The perf tool can count events for a command, sample execution and report where those samples landed. Instead of beginning with a profiler tied to one processor model, I can ask through one kernel interface and use the events available on this machine.

perf stat is a useful first question. It reports elapsed time along with counts such as cycles, instructions, context switches and page faults. Ratios matter more than isolated totals. Instructions per cycle can suggest whether the processor is retiring useful work efficiently, while cache-related events may explain why an apparently smaller algorithm still stalls.

My faster parser did not execute dramatically fewer instructions. It incurred fewer cache misses because its data was laid out more compactly. I had credited a clever branch change that happened nearby. The benchmark result was real; my story about it was fan fiction.

Sampling answers a different question. perf record periodically captures the current instruction pointer, and perf report aggregates samples by symbol. With suitable symbols, hot functions become visible without instrumenting every call. Sampling has overhead and statistical uncertainty, but it is often much less disruptive than logging entry and exit around a hot path.

Counters are constrained resources. The processor can measure only a limited number simultaneously, so events may be multiplexed. Some events are model-specific, and virtualized or restricted environments may expose less. A cache-miss count without knowing which cache or how the event is defined is an attractive number with an uncertain biography.

I also avoid optimizing from one profile. Workload, input size, compiler options and machine state all matter. I run repeated measurements, preserve the input and compare complete behavior. A ten-percent gain in a microbenchmark is not useful if the changed layout doubles memory for the real service.

I strongly prefer starting performance work with perf stat, then sampling when the totals suggest a question. ftrace remains better for many scheduling and kernel-flow investigations; perf is especially convenient for connecting program hotspots to processor and kernel counters. Neither tool replaces understanding, but both are considerably more reliable than staring at source until one loop begins to look guilty.

My test laptop changes display modes several times while booting: firmware text, a console mode, the X server’s preferred resolution, and sometimes another mode after resume. Each transition blanks the screen long enough to make me wonder whether the machine is considering a different profession.

Kernel mode setting moves responsibility for configuring display modes into the kernel graphics driver. Traditionally the X server performed that setup from user space. With KMS, the kernel knows about connectors, CRTCs, encoders, framebuffers and modes early enough to establish the display before X starts.

That early ownership makes boot transitions smoother, but the architectural benefit is larger. Suspend and resume already require kernel coordination with devices. If display state is also managed there, restoration does not depend on a particular user-space server reconstructing everything after the fact. Panic and virtual-terminal paths can retain a usable framebuffer as well.

The Direct Rendering Manager interface exposes the resources to user space. A display server can discover connectors and available modes, choose how framebuffers map to scanout hardware, and request changes through a common kernel boundary. The kernel arbitrates access to the device rather than allowing unrelated programs to reprogram it optimistically.

KMS also fits the broader memory-management work in graphics drivers. Rendering buffers and scanout buffers share hardware constraints, and transitions between them need synchronization. Putting mode setting beside DRM’s device and buffer management reduces the number of components that must agree through private arrangements.

My Intel machine with a recent kernel now reaches its native mode earlier and switches to X with less flashing. Resume has also become more predictable. This is not universal evidence. Driver support varies, hardware contains creative surprises, and a failed early mode set can replace a merely ugly boot with a completely dark one.

Debugging changes too. Problems that once belonged entirely to the X log may now begin in kernel messages and driver parameters. Distributions need rescue paths and conservative defaults while support matures. The mechanism is better placed, but moving code into the kernel also raises the cost of mistakes.

I strongly prefer KMS as the long-term division of responsibility. Display hardware is a shared device whose state matters before, during and after the graphical session; the kernel is the natural owner. For current machines I enable it where the driver is known to work and keep a boot option that disables it. Architectural conviction is comforting, but a visible console is more immediately useful.

I was chasing a latency spike in a kernel path and began adding printk() calls. This is the kernel equivalent of looking for a gas leak with a candle: familiar, illuminating and likely to influence the situation under investigation.

Recent kernels include ftrace, with controls under debugfs, normally in /sys/kernel/debug/tracing. It started as a function tracer and has grown useful tracing modes and events. The useful bit is that tracing can often be selected and controlled at runtime rather than compiled into a private forest of diagnostic messages.

The function tracer records kernel function activity in per-CPU ring buffers. Filters can restrict collection to relevant functions, which matters because tracing everything creates enormous output and changes timing. The function-graph tracer adds entry and return relationships, making nested execution and duration easier to see.

For my problem, the scheduler tracing facilities were more revealing than raw function calls. They showed when the task stopped running, which task replaced it and when it returned. The delay I had blamed on one function was mostly time spent waiting to be scheduled. A timestamp around the function could show elapsed time, but not explain where that time went.

Ring buffers are a sensible mechanism for this job. Each CPU can record events with less cross-CPU contention, and old entries can be overwritten when configured as a rolling trace. I can leave tracing ready, reproduce the spike and stop collection soon afterward. The final seconds are usually more valuable than a complete account of the machine booting and becoming bored.

Tracing still has overhead. Function tracing a hot path produces work, filters cost something, and reading the trace while collecting it can perturb results. I begin with the narrowest event set that can answer the question and compare behavior with tracing disabled. A trace is evidence gathered by an instrument, not the unobserved universe itself.

printk() remains appropriate for durable diagnostics that users or administrators need. It is poor as an ad hoc high-volume performance recorder: messages contend for shared facilities, flood logs and require source edits to move the probe. Temporary tracing and permanent logging solve different problems.

For kernel execution and scheduling questions, I try ftrace first. A carefully placed message can fill in semantic information the trace lacks. This is faster and leaves less debris in the source, including my traditional final patch removing forty-seven increasingly desperate print statements.

One of two batch jobs was eating the workstation, but their worker processes came and went too quickly for top to give me a useful total. Watching individual PIDs was the wrong level. I wanted the CPU bill for each job and all of its children.

The cpuacct cgroup controller does that accounting. I put each launcher in its own group before it forked workers. The children inherited the group, so short-lived compiler and helper processes charged CPU time to the same job without a polling script trying to catch them.

cpuacct.usage gives accumulated CPU time in nanoseconds. Reading it before and after a run gave me a simple total for the whole process tree. cpuacct.stat split the charge into user and system time in clock ticks, which showed that the troublesome job was spending most of its time in user code rather than hammering the kernel.

The counters are cumulative, so I record a starting value or create a fresh group for a run. A single reading is not a percentage. Dividing the delta by elapsed wall time gives a rough average, and a multithreaded job can legitimately consume more than one CPU-second per second on a multicore machine.

This also avoids a trap in process snapshots. If a parent exits after launching workers, summing only its current descendants misses work already completed. The group’s counter keeps the charge after those tasks are gone.

Accounting did not slow either job or reserve a processor. That was fine. It showed that the job I had blamed was innocent and the other one used nearly three times the CPU I expected. Only then did scheduler policy seem worth discussing.

For now I am leaving the groups as meters. A reliable number is already an improvement over glaring at whichever PID happens to be at the top of top.