(Option 1) Fixed O(N^2) performance when handling --bind flags

[witaway]

Issue #384. I'll need some help from the bubblewrap maintainers to land this change. Please, review this. I'm not completely sure does it break something or not. But seems like it's okay

I ran the tests that already exist in the project, and they passed. I also launched various software from flatpak. I replaced the system bwrap with the ones I built, with and without algorithm changes. In both, I output the contents of mountinfo at the very end of setup_newroot() execution. The list of mount points and their flags seem to be exactly the same on the data I've tried.

It improves the complexity to O(N log N). I also have tried to measure performance difference on some Flatpak software:

For example, flatpak run com.microsoft.Edge without optimization and with optimization (the execution time of setup_newroot, excluding the launch of the application itself)

1. 0.013712 => 0.004324
2. 0.040225 => 0.006671
3. 0.004751 => 0.002611

A test where I pass bwrap 2000 "--bind" flags: bwrap --dev-bind / / --bind /usr /tmp/1 --bind /usr /tmp/2 ... --bind /usr /tmp/2000 /bin/true

1. Before: 14.038314
2. After: 0.218774

Below I'll describe how algorithm basically works:

First, our problem isn't interactive type, because we have all bind operations and their order in arguments. The algorithm use it. Instead of rechecking /proc/self/mountinfo before every --bind operation we:

1. Just mount what user asked without any questions. Automatic mount propagation is expected too. At this stage, we are not doing anything with the security flags.
2. Save all these "requests" in a list to process and optimize later
3. Remount all mount points with correct security flags non-recursively. Thus, there is only one remount operation per mount point

More about point 3. After all the mount operations completed, we call bind_mount_fixup() function to remount all the mount points with correct flags. It does:

1. Collects all the data about mount points from /proc/self/mountinfo
2. Using received information, build the tree of mount points
3. Go through array of mount operations and collect all the nodes that correspond mount operations
4. And at the same time "virtually" popagates security flags in the graph to submounts
5. Goes through all actual mount points from mountinfo, requests correct flags from graph and remounts mount points with them if needed

Important notes:

1. When we collect mount operations, we also add to the list all mount's of proc, dev, mqueue, tmp. That's because we will anyway collect them from mount info to the graph and remount. If we wont add them to list, we will popagate unneeded flags. So we should avoid that.

2. When we bind file we create temp file as before. In older version we delete them right after they become unneeded. After changes we save all paths of those temp files and unlink() all of them later, right after we performed bind_mount_fixup(). That's because if we delete them, their soft links becomes incorrect and this break retrieve_kernel_case() function (used in fixup). Because under the hood it calls readlink(). Read this.

Below is more context about lazy propagation of flags:

If we propagate flags naively with DFS algorithm we'll still have O(N^2) complexity. That's why the main part of algorithm is lazy propagation on the graph.

After tree of mount points is built (step 2):

1. Start Euler tour on the graph, so start DFS from root and assign:

start[node] - which denotes the time at which we enter this node during DFS finish[node] - which denotes the time at which we leave this node during DFS.

Now for any node say X and another node Y in subtree, start[X] < start[Y] <= finish[Y] <= finish[X]. That way we can map each node to index in array. That way when we assign interval start[X] .. finish[X] on array with flag, we assign it for all the sub mounts of the mount.

2. Initialize segment tree with lazy propagation of assignment.

Segment tree is data structure that is useful when you have an array with values and you want to:

1. Change values of array fast.
2. Query sum on interval fast.

When we set flag on subtree, we assign 1 on all the needed interval. When we unset flag on subtree, we assign 0 on interval. When we check if flag set on somewhat node, we just query the sum of 1-length interval [start[X], start[X]] on segment tree.

So when we set/unset NODEV/RDONLY flag to subtree of X, we do a lazy update of adding flag to all indices from start[X] to finish[X].

Note: Right now segment tree implementation is not optimal! May be replaced with more optimized and and designed for this task data structure.

[witaway]

I hope this works as expected. It took me a while to figure out how everything works here. 😅

[witaway]

Also please check #630. I've coded the second more simple version of the same optimization with the same general approach. It has it's own advantages :)