Merge "Replace REGEXP with LIKE for sql queries in renameForFuse" into rvc-qpr-dev
diff --git a/jni/FuseDaemon.cpp b/jni/FuseDaemon.cpp
index 942b866..ecb7092 100644
--- a/jni/FuseDaemon.cpp
+++ b/jni/FuseDaemon.cpp
@@ -427,10 +427,14 @@
// invalidate node_name if different case
// Note that we invalidate async otherwise we will deadlock the kernel
if (name != node->GetName()) {
- std::thread t([=]() {
- fuse_inval(fuse->se, fuse->ToInode(parent), fuse->ToInode(node), node->GetName(),
- path);
- });
+ // Make copies of the node name and path so we're not attempting to acquire
+ // any node locks from the invalidation thread. Depending on timing, we may end
+ // up invalidating the wrong inode but that shouldn't result in correctness issues.
+ const fuse_ino_t parent_ino = fuse->ToInode(parent);
+ const fuse_ino_t child_ino = fuse->ToInode(node);
+ const std::string& node_name = node->GetName();
+
+ std::thread t([=]() { fuse_inval(fuse->se, parent_ino, child_ino, node_name, path); });
t.detach();
}
}
diff --git a/jni/node-inl.h b/jni/node-inl.h
index d6ad0ad..364a327 100644
--- a/jni/node-inl.h
+++ b/jni/node-inl.h
@@ -19,12 +19,16 @@
#include <android-base/logging.h>
+#include <cstdint>
+#include <limits>
#include <list>
#include <memory>
#include <mutex>
+#include <set>
#include <sstream>
#include <string>
#include <unordered_set>
+#include <utility>
#include <vector>
#include "libfuse_jni/ReaddirHelper.h"
@@ -175,14 +179,18 @@
node* LookupChildByName(const std::string& name, bool acquire) const {
std::lock_guard<std::recursive_mutex> guard(*lock_);
- const char* name_char = name.c_str();
- for (node* child : children_) {
- const std::string& child_name = child->GetName();
- if (!strcasecmp(name_char, child_name.c_str()) && !child->deleted_) {
+ // lower_bound will give us the first child with strcasecmp(child->name, name) >=0.
+ // For more context see comment on the NodeCompare struct.
+ auto start = children_.lower_bound(std::make_pair(name, 0));
+ // upper_bound will give us the first child with strcasecmp(child->name, name) > 0
+ auto end =
+ children_.upper_bound(std::make_pair(name, std::numeric_limits<uintptr_t>::max()));
+ for (auto it = start; it != end; it++) {
+ node* child = *it;
+ if (!child->deleted_) {
if (acquire) {
child->Acquire();
}
-
return child;
}
}
@@ -201,10 +209,41 @@
void Rename(const std::string& name, node* new_parent) {
std::lock_guard<std::recursive_mutex> guard(*lock_);
- name_ = name;
if (new_parent != parent_) {
RemoveFromParent();
+ name_ = name;
AddToParent(new_parent);
+ return;
+ }
+
+ // Changing name_ will change the expected position of this node in parent's set of
+ // children. Consider following scenario:
+ // 1. This node: "b"; parent's set: {"a", "b", "c"}
+ // 2. Rename("b", "d")
+ //
+ // After rename, parent's set should become: {"a", "b", "d"}, but if we simply change the
+ // name it will be {"a", "d", "b"}, which violates properties of the set.
+ //
+ // To make sure that parent's set is always valid, changing name is 3 steps procedure:
+ // 1. Remove this node from parent's set.
+ // 2 Change the name.
+ // 3. Add it back to the set.
+ // Rename of node without changing its parent. Still need to remove and re-add it to make
+ // sure lookup index is correct.
+ if (name_ != name) {
+ // If this is a root node, simply rename it.
+ if (parent_ == nullptr) {
+ name_ = name;
+ return;
+ }
+
+ auto it = parent_->children_.find(this);
+ CHECK(it != parent_->children_.end());
+ parent_->children_.erase(it);
+
+ name_ = name;
+
+ parent_->children_.insert(this);
}
}
@@ -299,7 +338,7 @@
CHECK(parent != nullptr);
parent_ = parent;
- parent_->children_.push_back(this);
+ parent_->children_.insert(this);
// TODO(narayan, zezeozue): It's unclear why we need to call Acquire on the
// parent node when we're adding a child to it.
@@ -311,16 +350,55 @@
std::lock_guard<std::recursive_mutex> guard(*lock_);
if (parent_ != nullptr) {
- std::list<node*>& children = parent_->children_;
- std::list<node*>::iterator it = std::find(children.begin(), children.end(), this);
+ auto it = parent_->children_.find(this);
+ CHECK(it != parent_->children_.end());
+ parent_->children_.erase(it);
- CHECK(it != children.end());
- children.erase(it);
parent_->Release(1);
parent_ = nullptr;
}
}
+ // A custom heterogeneous comparator used for set of this node's children_ to speed up child
+ // node by name lookups.
+ //
+ // This comparator treats node* as pair (node->name_, node): two nodes* are first
+ // compared by their name using case-insenstive comparison function. If their names are equal,
+ // then pointers are compared as integers.
+ //
+ // See LookupChildByName function to see how this comparator is used.
+ //
+ // Note that it's important to first compare by name_, since it will make all nodes with same
+ // name (compared using strcasecmp) together, which allows LookupChildByName function to find
+ // range of the candidate nodes by issuing two binary searches.
+ struct NodeCompare {
+ using is_transparent = void;
+
+ bool operator()(const node* lhs, const node* rhs) const {
+ int cmp = strcasecmp(lhs->name_.c_str(), rhs->name_.c_str());
+ if (cmp != 0) {
+ return cmp < 0;
+ }
+ return reinterpret_cast<uintptr_t>(lhs) < reinterpret_cast<uintptr_t>(rhs);
+ }
+
+ bool operator()(const node* lhs, const std::pair<std::string, uintptr_t>& rhs) const {
+ int cmp = strcasecmp(lhs->name_.c_str(), rhs.first.c_str());
+ if (cmp != 0) {
+ return cmp < 0;
+ }
+ return reinterpret_cast<uintptr_t>(lhs) < rhs.second;
+ }
+
+ bool operator()(const std::pair<std::string, uintptr_t>& lhs, const node* rhs) const {
+ int cmp = strcasecmp(lhs.first.c_str(), rhs->name_.c_str());
+ if (cmp != 0) {
+ return cmp < 0;
+ }
+ return lhs.second < reinterpret_cast<uintptr_t>(rhs);
+ }
+ };
+
// A helper function to recursively construct the absolute path of a given node.
// If |safe| is true, builds a PII safe path instead
void BuildPathForNodeRecursive(bool safe, const node* node, std::stringstream* path) const;
@@ -329,9 +407,9 @@
std::string name_;
// The reference count for this node. Guarded by |lock_|.
uint32_t refcount_;
- // List of children of this node. All of them contain a back reference
+ // Set of children of this node. All of them contain a back reference
// to their parent. Guarded by |lock_|.
- std::list<node*> children_;
+ std::set<node*, NodeCompare> children_;
// Containing directory for this node. Guarded by |lock_|.
node* parent_;
// List of file handles associated with this node. Guarded by |lock_|.
diff --git a/jni/node_test.cpp b/jni/node_test.cpp
index 098bb28..357cea8 100644
--- a/jni/node_test.cpp
+++ b/jni/node_test.cpp
@@ -3,6 +3,7 @@
#include "node-inl.h"
#include <algorithm>
+#include <limits>
#include <memory>
#include <mutex>
@@ -33,6 +34,9 @@
unique_node_ptr CreateNode(node* parent, const std::string& path) {
return unique_node_ptr(node::Create(parent, path, &lock_, &tracker_), &NodeTest::destroy);
}
+
+ // Expose NodeCompare for testing.
+ node::NodeCompare cmp;
};
TEST_F(NodeTest, TestCreate) {
@@ -239,3 +243,78 @@
ASSERT_EQ(mixed_child.get(), lower_child);
ASSERT_EQ(mixed_child.get(), upper_child);
}
+
+TEST_F(NodeTest, RenameSameNameSameParent) {
+ unique_node_ptr parent = CreateNode(nullptr, "/path1");
+ unique_node_ptr child = CreateNode(parent.get(), "subdir");
+
+ ASSERT_EQ(child.get(), parent->LookupChildByName("SuBdIr", false /* acquire */));
+ ASSERT_EQ(2, GetRefCount(parent.get()));
+
+ child->Rename("subdir", parent.get());
+
+ ASSERT_EQ(child.get(), parent->LookupChildByName("SuBdIr", false /* acquire */));
+ ASSERT_EQ(2, GetRefCount(parent.get()));
+}
+
+TEST_F(NodeTest, RenameRoot) {
+ unique_node_ptr root = CreateNode(nullptr, "/root");
+ ASSERT_EQ(1, GetRefCount(root.get()));
+
+ root->Rename("/i-am-root!", nullptr);
+
+ ASSERT_EQ("/i-am-root!", root->GetName());
+ ASSERT_EQ(1, GetRefCount(root.get()));
+}
+
+TEST_F(NodeTest, NodeCompareDefinesLinearOrder) {
+ unique_node_ptr node_a = CreateNode(nullptr, "a");
+ unique_node_ptr node_b = CreateNode(nullptr, "B");
+ unique_node_ptr node_c = CreateNode(nullptr, "c");
+
+ ASSERT_FALSE(cmp.operator()(node_a.get(), node_a.get()));
+ ASSERT_FALSE(cmp.operator()(node_b.get(), node_b.get()));
+ ASSERT_FALSE(cmp.operator()(node_c.get(), node_c.get()));
+
+ auto check_fn = [&](const node* lhs_node, const node* rhs_node) {
+ ASSERT_TRUE(cmp.operator()(lhs_node, rhs_node));
+ ASSERT_FALSE(cmp.operator()(rhs_node, lhs_node));
+ };
+
+ check_fn(node_a.get(), node_b.get());
+ check_fn(node_b.get(), node_c.get());
+ check_fn(node_a.get(), node_c.get());
+
+ // ("A", 0) < node_a < ("a", max_uintptr_t) < node_b
+ ASSERT_TRUE(cmp.operator()(std::make_pair("A", 0), node_a.get()));
+ ASSERT_TRUE(cmp.operator()(node_a.get(),
+ std::make_pair("A", std::numeric_limits<uintptr_t>::max())));
+ ASSERT_TRUE(cmp.operator()(std::make_pair("A", std::numeric_limits<uintptr_t>::max()),
+ node_b.get()));
+}
+
+TEST_F(NodeTest, LookupChildByName_ChildrenWithSameName) {
+ unique_node_ptr parent = CreateNode(nullptr, "/path");
+ unique_node_ptr foo1 = CreateNode(parent.get(), "FoO");
+ unique_node_ptr foo2 = CreateNode(parent.get(), "fOo");
+ unique_node_ptr bar1 = CreateNode(parent.get(), "BAR");
+ unique_node_ptr bar2 = CreateNode(parent.get(), "bar");
+ unique_node_ptr baz1 = CreateNode(parent.get(), "baZ");
+ unique_node_ptr baz2 = CreateNode(parent.get(), "Baz");
+
+ auto test_fn = [&](const std::string& name, node* first, node* second) {
+ auto node1 = parent->LookupChildByName(name, false /* acquire */);
+ ASSERT_EQ(std::min(first, second), node1);
+ node1->SetDeleted();
+
+ auto node2 = parent->LookupChildByName(name, false /* acquire */);
+ ASSERT_EQ(std::max(first, second), node2);
+ node2->SetDeleted();
+
+ ASSERT_EQ(nullptr, parent->LookupChildByName(name, false /* acquire */));
+ };
+
+ test_fn("foo", foo1.get(), foo2.get());
+ test_fn("bAr", bar1.get(), bar2.get());
+ test_fn("BaZ", baz1.get(), baz2.get());
+}
diff --git a/src/com/android/providers/media/MediaProvider.java b/src/com/android/providers/media/MediaProvider.java
index 47f71e0..e028af4 100644
--- a/src/com/android/providers/media/MediaProvider.java
+++ b/src/com/android/providers/media/MediaProvider.java
@@ -2030,6 +2030,10 @@
return OsConstants.EPERM;
}
+ if (shouldBypassDatabaseForFuse(uid)) {
+ return renameInLowerFs(oldPath, newPath);
+ }
+
if (shouldBypassFuseRestrictions(/*forWrite*/ true, oldPath)
&& shouldBypassFuseRestrictions(/*forWrite*/ true, newPath)) {
return renameUncheckedForFuse(oldPath, newPath);
@@ -3292,6 +3296,9 @@
if (isCallingPackageSelf() || isCallingPackageLegacyWrite()) {
// Mutation allowed
+ } else if (isCallingPackageManager()) {
+ // Apps with MANAGE_EXTERNAL_STORAGE have all files access, hence they are
+ // allowed to insert files anywhere.
} else {
Log.w(TAG, "Ignoring mutation of " + column + " from "
+ getCallingPackageOrSelf());
@@ -6241,6 +6248,16 @@
return !isCallingIdentitySharedPackageName(appSpecificDir);
}
+ private boolean shouldBypassDatabaseForFuse(int uid) {
+ final LocalCallingIdentity token =
+ clearLocalCallingIdentity(getCachedCallingIdentityForFuse(uid));
+ try {
+ return uid != android.os.Process.SHELL_UID && isCallingPackageManager();
+ } finally {
+ restoreLocalCallingIdentity(token);
+ }
+ }
+
/**
* Set of Exif tags that should be considered for redaction.
*/
@@ -6669,6 +6686,10 @@
return OsConstants.EPERM;
}
+ if (shouldBypassDatabaseForFuse(uid)) {
+ return 0;
+ }
+
final String mimeType = MimeUtils.resolveMimeType(new File(path));
if (shouldBypassFuseRestrictions(/*forWrite*/ true, path)) {
@@ -6777,6 +6798,10 @@
return OsConstants.ENOENT;
}
+ if (shouldBypassDatabaseForFuse(uid)) {
+ return deleteFileUnchecked(path);
+ }
+
final boolean shouldBypass = shouldBypassFuseRestrictions(/*forWrite*/ true, path);
// Legacy apps that made is this far don't have the right storage permission and hence
