On 2026-01-14 12:06, Michal Hocko wrote:

On Wed 14-01-26 09:59:15, Mathieu Desnoyers wrote:

quoted

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.

quoted

   #!/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