Re: [PATCH v16 3/3] mm: Reduce latency of OOM killer task selection with 2-pass algorithm

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

On 2026-01-14 12:06, Michal Hocko wrote:
> On Wed 14-01-26 09:59:15, Mathieu Desnoyers wrote:
>> Use the hierarchical tree counter approximation (hpcc) to implement the
>> OOM killer task selection with a 2-pass algorithm. The first pass
>> selects the process that has the highest badness points approximation,
>> and the second pass compares each process using the current max badness
>> points approximation.
>>
>> The second pass uses an approximate comparison to eliminate all processes
>> which are below the current max badness points approximation accuracy
>> range.
>>
>> Summing the per-CPU counters to calculate the precise badness of tasks
>> is only required for tasks with an approximate badness within the
>> accuracy range of the current max points value.
>>
>> Limit to 16 the maximum number of badness sums allowed for an OOM killer
>> task selection before falling back to the approximated comparison. This
>> ensures bounded execution time for scenarios where many tasks have
>> badness within the accuracy of the maximum badness approximation.
>>
>> Testing the execution time of select_bad_process() with a single
>> tail -f /dev/zero:
>>
>>      AMD EPYC 9654 96-Core (2 sockets)
>>      Within a KVM, configured with 256 logical cpus.
>>
>>                                        | precise sum |   hpcc   |
>>      ----------------------------------|-------------|----------|
>>      nr_processes=40                   |    0.5 ms   |   0.3 ms |
>>      nr_processes=10000                |   80.0 ms   |   7.9 ms |
>>
>> Tested with the following script:
> 
> I am confused by these numbers. Are you saying that 2 pass over all
> tasks and evaluating all of them is 10 times faster than a single pass
> with exact sum of pcp counters?

Yes, that's correct.

This is because we can use the approximate value and the
min/max possible precise sum ranges to eliminate most tasks,
so we only have to do a precise sum on very few tasks.

So we're basically going from a 1-pass doing precise sum for
all tasks to 2-passes doing approximated sum for all tasks,
and only precise sums for the very few tasks that happen to
be in the vicinity of the task chosen by the 1st pass.

We could probably do something more clever and do all this
within a single pass if we keep track of the possible candidates
in a separate list, and then only iterate on those candidates
to do a precise sum at the end of the pass. But I chose to keep
things simple, hence the 2 pass algo.

> 
>>
>>    #!/bin/sh
>>
>>    for a in $(seq 1 10); do (tail /dev/zero &); done
>>    sleep 5
>>    for a in $(seq 1 10); do (tail /dev/zero &); done
>>    sleep 2
>>    for a in $(seq 1 10); do (tail /dev/zero &); done
>>    echo "Waiting for tasks to finish"
>>    wait
>>
>> Results: OOM kill order on a 128GB memory system
>> ================================================
> 
> I find this section confusing as well. Is that before/after comparision.
> If yes it would be great to call out explicit behavior before and after.

Not really. I'm just testing the "after" to make sure we get the
expected killing order.

> 
> My overall impression is that the implementation is really involved and
> at this moment I do not really see a big benefit of all the complexity.

Note that we can get the proc ABI RSS accuracy improvements with the
previous 2 patches without this 2-pass algo. Do you see more value in
the RSS accuracy improvements than in the oom killer latency reduction ?

> 
> It would help to explicitly mention what is the the overall imprecision
> of the oom victim selection with the new data structure (maybe this is
> good enough[*]). What if we go with exact precision with the new data
> structure comparing to the original pcp counters.

Do you mean comparing using approximate sums with the new data
structure (which has a bounded accuracy of O(nr_cpus*log(nr_cpus)))
compared to the old data structure which had an inaccuracy of
O(nr_cpus^2) ? So if the inaccuracy provided by the new data structure
is good enough for OOM task selection, we could go from precise sum
back to an approximation and just use that with the new data
structure.

Thanks,

Mathieu

> 
> 
> [*] please keep in mind that oom victim selection is by no means an
> exact science, we try to pick up a task that is likely to free up some
> memory to unlock the system from memory depletion. We want that to be a
> big memory consumer to reduce number of tasks to kill and we want to
> roughly apply oom_score_adj.


-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com