Re: Upcoming: Notifications, FS notifications and fsinfo()

[Miklos Szeredi <miklos@szeredi.hu>]

On Tue, Apr 7, 2020 at 5:53 PM Lennart Poettering <mzxreary@0pointer.de> wrote:
>
> On Di, 07.04.20 15:59, Miklos Szeredi (miklos@szeredi.hu) wrote:
>
> > On Tue, Apr 7, 2020 at 4:22 AM Ian Kent <raven@themaw.net> wrote:
> > > > Right now, when you have n mounts, and any mount changes, or one is
> > > > added or removed then we have to parse the whole mount table again,
> > > > asynchronously, processing all n entries again, every frickin
> > > > time. This means the work to process n mounts popping up at boot is
> > > > O(n²). That sucks, it should be obvious to anyone. Now if we get that
> > > > fixed, by some mount API that can send us minimal notifications about
> > > > what happened and where, then this becomes O(n), which is totally OK.
> >
> > Something's not right with the above statement.  Hint: if there are
> > lots of events in quick succession, you can batch them quite easily to
> > prevent overloading the system.
> >
> > Wrote a pair of utilities to check out the capabilities of the current
> > API.   The first one just creates N mounts, optionally sleeping
> > between each.  The second one watches /proc/self/mountinfo and
> > generates individual (add/del/change) events based on POLLPRI and
> > comparing contents with previous instance.
> >
> > First use case: create 10,000 mounts, then start the watcher and
> > create 1000 mounts with a 50ms sleep between them.  Total time (user +
> > system) consumed by the watcher: 25s.  This is indeed pretty dismal,
> > and a per-mount query will help tremendously.  But it's still "just"
> > 25ms per mount, so if the mounts are far apart (which is what this
> > test is about), this won't thrash the system.  Note, how this is self
> > regulating: if the load is high, it will automatically batch more
> > requests, preventing overload.  It is also prone to lose pairs of add
> > + remove in these case (and so is the ring buffer based one from
> > David).
>
> We will batch requests too in systemd, of course, necessarily, given
> that the /p/s/mi inotify stuff is async. Thing though is that this
> means we buy lower CPU usage — working around the O(n²) issue — by
> introducing artifical higher latencies. We usually want to boot
> quickly, and not artificially slow.
>
> Sure one can come up with some super smart scheme how to tweak the
> artifical latencies, how to grow them, how to shrink them, depending
> on a perceived flood of events, some backing off scheme. But that's
> just polishing a turd, if all we want is proper queued change
> notification without the O(n²) behaviour.
>
> I mean, the fix for an O(n²) algorithm is to make it O(n) or so. By
> coalescing wake-up events you just lower the n again, probably
> linearly, but that still means we pay O(n²), which sucks.

Obviously.  But you keep ignoring event queue overflows; it's
basically guaranteed to happen with a sizable mount storm and then you
are back to O(n^2).

Give it some testing please, as Linus is not going to take any
solution without an actual use case and testing.  When you come back
and say that fsinfo(2) works fine with systemd and a 100k mount/umount
storm, then we can have a look at the performance budget and revisit
the fine points of API design.

Thanks,
Miklos