https://bugzilla.redhat.com/show_bug.cgi?id=1069718
--- Comment #2 from Stephen Tweedie sct@redhat.com --- Additional data forwarded from Al Viro:
On Mon, Feb 24, 2014 at 10:13:43PM +0100, Lennart Poettering wrote:
Heya,
There are some O(n^2) issues when we match mounts against each other in systemd, but so far we never had an issue with that, because the number of mounts stayed reasonably low. These are things that should be fixable though.
I am not too concerned about the bus messages issue though I must say, as they only grow O(n), but they are of course ugly to see on the bus.
No, they actually grow O(n) *per* *change*. So umount `seq 5000` will end up with ~12 millions of messages sent. All buffered in PID 1 memory - just watch the RSS.
The kernel API that requires to linearly reread the entire mount table each time and compare it with what was before is also a source of O(n^2) behaviour which we probably should look into first?
Nowhere near the top. And why would that be O(n^2), anyway? For pity sake, they have unique numeric IDs, so you don't even need to sort anything.
Before we start masking mounts for view in systemd we really should see if we can't mask them from the entire system. Because these problems won't be specific to systemd (well, the O(n^2) matching issue is), but to any software that watches mountinfo, like udisks and whatnot.
Matching is a non-issue. Here's a trivial test for you:
cd /tmp; for i in `seq 100`; do touch $i; mount --bind /proc/version $i; done dbus-monitor --system >log & umount `seq 100` kill %1
now look into log. You'll see ~5000 messages in there. And yes, it is quadratic by number of mounts. s/100/1000/ in the above and you'll see about half a million messages. 10000 will almost certainly OOM the box.
Matching is actually nowhere near quadratic, unless you have really sucky implementation of manager_get_unit(). Could've been done better (there's a reasonably dense constant integer in every line, so you could've used an array), but unless your manager_get_unit() does something on the scale of "let's hold them all in a list and walk it", you are not going to see O(n^2) there.