Re: [PATCH] kernfs: Build paths in linear time with respect to depth

[Chris Down <chris@chrisdown.name>]

Hi Tejun,

Thanks for taking a look!

Tejun Heo writes:
>I don't think a 15,000 deep cgroup chain makes much sense as a use case.
>A lot of other stuff in the controllers will break down at five-digit
>depths, and quadratic isn't that expensive when the base number is
>small. Did you see this overhead in more realistic scenarios?

Agreed that nobody should be building anything like that on purpose, and
at the depths people actually use there isn't much in it. Here's the
median read of /proc/self/cgroup in a 4 CPU VM, with single character
names:

     depth    before    after
     4        304ns     258ns
     16       549ns     396ns
     64       2.8us     1.0us
     256      69us      4.2us
     1024     2.5ms     20us
     2046     12.0ms    43us

What bothers me more is that whoever picks the depth isn't the one who is
affected by it. cgroup.max.depth defaults to max, so anyone with a
delegated subtree can make a deep chain. Every read of /proc/<pid>/cgroup
for a task at the bottom of it then takes that long with css_set_lock held
and IRQs off. It doesn't take five digits for that to become problematic,
either. Here's the median fork() + exit on another CPU of the same VM
while one task does that in a loop:

     depth of reader    before    after
     (no reader)        51us      52us
     64                 56us      53us
     256                363us     60us
     1024               5.0ms     93us
     2046               21.9ms    117us

(In case you're wondering why 2046, that's about as deep as you can go
without brushing up against PATH_MAX.)

You're right that other things break down at depths like 15,000. Just
creating that chain takes minutes. But that only slows down whoever
creates it. This slows down fork and exit for everyone else.

>Even if it is worth doing, the implementation looks too convoluted. Most
>of the complication seems to come from supporting wrapping to keep the
>head of an overlong path. The only callers that care about what the
>buffer holds on overflow are debug outputs. How about changing the
>contract so that on overflow the buffer keeps the tail end of the path
>instead of the head, which is more useful anyway, and the function
>returns -E2BIG rather than the length?

Yeah, that's a lot nicer, thanks.

The one caller I found which relies on the start of the path being kept is
SEQ_printf_task_group_path() in sched/debug. Its fallback buffer appends
"..." when the path fills it, which will now be on the wrong side. That
code is moving to sched.h in tip at the moment, so I'll send the fix for
it there separately, rather than have the two conflict in -next.

Based on what you said, in v2 I'll also drop Fixes: and Cc: stable, since
this is now a change in behaviour rather than only a speedup.

Thanks!

Chris