This is an automated email from the ASF dual-hosted git repository.
bmahler pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/mesos.git
The following commit(s) were added to refs/heads/master by this push:
new 66b4b16c1 Fixed sorting in MountInfoTable::read.
66b4b16c1 is described below
commit 66b4b16c1fbbf8d2cf95eeb4f91e7fb3bff17793
Author: Ilya Pronin <[email protected]>
AuthorDate: Fri Nov 6 15:36:06 2020 -0800
Fixed sorting in MountInfoTable::read.
Current implementation of MountInfoTable sorting crashes when some parts
of the mount tree are not visible in /proc/{pid}/mountinfo, which can
happen, for example, in a chrooted environment. The sorter assumes that
the / mount is always present and uses it as the starting node for the
DFS traversal.
Additionally, this sorting algorithm loses mounts that are parents of
themselves from the sorted MountInfoTable. The bug is not caught by
FsTest.MountInfoTableReadSortedParentOfSelf test, so it needs to be
updated as well.
The new sorting implementation supports multiple starting nodes and
works in situations where the visible mount tree is disconnected. It
also changes the resulting order to BFS, but that shouldn't matter
because the invariant is that all parent entries appear before their
child entries.
---
src/linux/fs.cpp | 74 ++++++++++++++++--------------------
src/tests/containerizer/fs_tests.cpp | 5 ++-
2 files changed, 35 insertions(+), 44 deletions(-)
diff --git a/src/linux/fs.cpp b/src/linux/fs.cpp
index 27536aab3..27f91d29b 100644
--- a/src/linux/fs.cpp
+++ b/src/linux/fs.cpp
@@ -193,54 +193,44 @@ Try<MountInfoTable> MountInfoTable::read(
// them according to the invariant that all parent entries
// appear before their child entries.
if (hierarchicalSort) {
- Option<int> rootParentId = None();
-
- // Construct a representation of the mount hierarchy using a hashmap.
- hashmap<int, vector<MountInfoTable::Entry>> parentToChildren;
-
- foreach (const MountInfoTable::Entry& entry, table.entries) {
- if (entry.target == "/") {
- CHECK_NONE(rootParentId);
- rootParentId = entry.parent;
+ // Build an ID to entry and a parent to children IDs map for quick
+ // lookup.
+ hashmap<int, MountInfoTable::Entry> entries;
+ hashmap<int, vector<int>> children;
+ for (const MountInfoTable::Entry& ent : table.entries) {
+ entries.emplace(ent.id, ent);
+
+ // It is legal to have a mount info table entry whose ID is the
+ // same as its parent ID. This can happen if, for example, the
+ // system boots from network and then keeps the original / in RAM.
+ // To avoid cycles when walking the mount hierarchy, we skip such
+ // entries in the children map.
+ if (ent.parent != ent.id) {
+ children[ent.parent].push_back(ent.id);
}
- parentToChildren[entry.parent].push_back(entry);
}
- // Walk the hashmap and construct a list of entries sorted
- // hierarchically. The recursion eventually terminates because
- // entries in MountInfoTable are guaranteed to have no cycles.
- // We double check though, just to make sure.
- hashset<int> visitedParents;
- vector<MountInfoTable::Entry> sortedEntries;
-
- std::function<void(int)> sortFrom = [&](int parentId) {
- CHECK(!visitedParents.contains(parentId))
- << "Cycle found in mount table hierarchy at entry"
- << " '" << stringify(parentId) << "': " << std::endl << lines;
-
- visitedParents.insert(parentId);
-
- foreach (const MountInfoTable::Entry& entry, parentToChildren[parentId])
{
- sortedEntries.push_back(entry);
-
- // It is legal to have a `MountInfoTable` entry whose
- // `entry.id` is the same as its `entry.parent`. This can
- // happen (for example), if a system boots from the network
- // and then keeps the original `/` in RAM. To avoid cycles
- // when walking the mount hierarchy, we only recurse into our
- // children if this case is not satisfied.
- if (parentId != entry.id) {
- sortFrom(entry.id);
+ // Entries without a visible parent (e.g. in a chroot) or referring
+ // to themselves are roots of visible mount trees. Sort them in BFS
+ // order.
+ vector<MountInfoTable::Entry> sorted;
+ sorted.reserve(table.entries.size());
+ for (const MountInfoTable::Entry& ent : table.entries) {
+ if (ent.parent == ent.id || !entries.contains(ent.parent)) {
+ sorted.push_back(ent);
+ }
+ }
+ for (auto it = sorted.begin(); it != sorted.end(); ++it) {
+ if (children.contains(it->id)) {
+ for (const int id : children.at(it->id)) {
+ sorted.push_back(entries.at(id));
}
}
- };
-
- // We know the node with a parent id of
- // `rootParentId` is the root mount point.
- CHECK_SOME(rootParentId);
- sortFrom(rootParentId.get());
+ }
- table.entries = std::move(sortedEntries);
+ CHECK_EQ(sorted.size(), table.entries.size())
+ << "Possible cycle in mount info table: " << std::endl << lines;
+ table.entries = std::move(sorted);
}
return table;
diff --git a/src/tests/containerizer/fs_tests.cpp
b/src/tests/containerizer/fs_tests.cpp
index 36fda9c88..8532abbc5 100644
--- a/src/tests/containerizer/fs_tests.cpp
+++ b/src/tests/containerizer/fs_tests.cpp
@@ -196,7 +196,7 @@ TEST_F(FsTest, MountInfoTableReadSorted)
// Verify that all parent entries appear *before* their children.
foreach (const MountInfoTable::Entry& entry, table->entries) {
- if (entry.target != "/") {
+ if (entry.target != "/" && entry.parent != entry.id) {
ASSERT_TRUE(ids.contains(entry.parent));
}
@@ -225,12 +225,13 @@ TEST_F(FsTest, MountInfoTableReadSortedParentOfSelf)
// Examine the calling process's mountinfo table.
Try<MountInfoTable> table = MountInfoTable::read(lines);
ASSERT_SOME(table);
+ EXPECT_EQ(table->entries.size(), strings::tokenize(lines, "\n").size());
hashset<int> ids;
// Verify that all parent entries appear *before* their children.
foreach (const MountInfoTable::Entry& entry, table->entries) {
- if (entry.target != "/") {
+ if (entry.target != "/" && entry.parent != entry.id) {
ASSERT_TRUE(ids.contains(entry.parent));
}
