Move FileDescriptorShuffle to base/posix. This file is very posix-specific.

TEST=it compiles
BUG=none

Review URL: https://codereview.chromium.org/10399100

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@166970 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 470 insertions, 0 deletions

diff --git a/base/posix/file_descriptor_shuffle.cc b/base/posix/file_descriptor_shuffle.cc
new file mode 100644
index 0000000..0dde958
--- /dev/null
+++ b/base/posix/file_descriptor_shuffle.cc
@@ -0,0 +1,96 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/posix/file_descriptor_shuffle.h"
+
+#include <unistd.h>
+#include <stddef.h>
+#include <ostream>
+
+#include "base/eintr_wrapper.h"
+#include "base/logging.h"
+
+namespace base {
+
+bool PerformInjectiveMultimapDestructive(
+    InjectiveMultimap* m, InjectionDelegate* delegate) {
+  static const size_t kMaxExtraFDs = 16;
+  int extra_fds[kMaxExtraFDs];
+  unsigned next_extra_fd = 0;
+
+  // DANGER: this function may not allocate.
+
+  for (InjectiveMultimap::iterator i = m->begin(); i != m->end(); ++i) {
+    int temp_fd = -1;
+
+    // We DCHECK the injectiveness of the mapping.
+    for (InjectiveMultimap::iterator j = i + 1; j != m->end(); ++j) {
+      DCHECK(i->dest != j->dest) << "Both fd " << i->source
+          << " and " << j->source << " map to " << i->dest;
+    }
+
+    const bool is_identity = i->source == i->dest;
+
+    for (InjectiveMultimap::iterator j = i + 1; j != m->end(); ++j) {
+      if (!is_identity && i->dest == j->source) {
+        if (temp_fd == -1) {
+          if (!delegate->Duplicate(&temp_fd, i->dest))
+            return false;
+          if (next_extra_fd < kMaxExtraFDs) {
+            extra_fds[next_extra_fd++] = temp_fd;
+          } else {
+            RAW_LOG(ERROR, "PerformInjectiveMultimapDestructive overflowed "
+                           "extra_fds. Leaking file descriptors!");
+          }
+        }
+
+        j->source = temp_fd;
+        j->close = false;
+      }
+
+      if (i->close && i->source == j->dest)
+        i->close = false;
+
+      if (i->close && i->source == j->source) {
+        i->close = false;
+        j->close = true;
+      }
+    }
+
+    if (!is_identity) {
+      if (!delegate->Move(i->source, i->dest))
+        return false;
+    }
+
+    if (!is_identity && i->close)
+      delegate->Close(i->source);
+  }
+
+  for (unsigned i = 0; i < next_extra_fd; i++)
+    delegate->Close(extra_fds[i]);
+
+  return true;
+}
+
+bool PerformInjectiveMultimap(const InjectiveMultimap& m_in,
+                              InjectionDelegate* delegate) {
+  InjectiveMultimap m(m_in);
+  return PerformInjectiveMultimapDestructive(&m, delegate);
+}
+
+bool FileDescriptorTableInjection::Duplicate(int* result, int fd) {
+  *result = HANDLE_EINTR(dup(fd));
+  return *result >= 0;
+}
+
+bool FileDescriptorTableInjection::Move(int src, int dest) {
+  return HANDLE_EINTR(dup2(src, dest)) != -1;
+}
+
+void FileDescriptorTableInjection::Close(int fd) {
+  int ret = HANDLE_EINTR(close(fd));
+  DPCHECK(ret == 0);
+}
+
+}  // namespace base
diff --git a/base/posix/file_descriptor_shuffle.h b/base/posix/file_descriptor_shuffle.h
new file mode 100644
index 0000000..6888c3e
--- /dev/null
+++ b/base/posix/file_descriptor_shuffle.h
@@ -0,0 +1,87 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef BASE_POSIX_FILE_DESCRIPTOR_SHUFFLE_H_
+#define BASE_POSIX_FILE_DESCRIPTOR_SHUFFLE_H_
+
+// This code exists to perform the shuffling of file descriptors which is
+// commonly needed when forking subprocesses. The naive approve is very simple,
+// just call dup2 to setup the desired descriptors, but wrong. It's tough to
+// handle the edge cases (like mapping 0 -> 1, 1 -> 0) correctly.
+//
+// In order to unittest this code, it's broken into the abstract action (an
+// injective multimap) and the concrete code for dealing with file descriptors.
+// Users should use the code like this:
+//   base::InjectiveMultimap file_descriptor_map;
+//   file_descriptor_map.push_back(base::InjectionArc(devnull, 0, true));
+//   file_descriptor_map.push_back(base::InjectionArc(devnull, 2, true));
+//   file_descriptor_map.push_back(base::InjectionArc(pipe[1], 1, true));
+//   base::ShuffleFileDescriptors(file_descriptor_map);
+//
+// and trust the the Right Thing will get done.
+
+#include <vector>
+
+#include "base/base_export.h"
+#include "base/compiler_specific.h"
+
+namespace base {
+
+// A Delegate which performs the actions required to perform an injective
+// multimapping in place.
+class InjectionDelegate {
+ public:
+  // Duplicate |fd|, an element of the domain, and write a fresh element of the
+  // domain into |result|. Returns true iff successful.
+  virtual bool Duplicate(int* result, int fd) = 0;
+  // Destructively move |src| to |dest|, overwriting |dest|. Returns true iff
+  // successful.
+  virtual bool Move(int src, int dest) = 0;
+  // Delete an element of the domain.
+  virtual void Close(int fd) = 0;
+
+ protected:
+  virtual ~InjectionDelegate() {}
+};
+
+// An implementation of the InjectionDelegate interface using the file
+// descriptor table of the current process as the domain.
+class FileDescriptorTableInjection : public InjectionDelegate {
+  virtual bool Duplicate(int* result, int fd) OVERRIDE;
+  virtual bool Move(int src, int dest) OVERRIDE;
+  virtual void Close(int fd) OVERRIDE;
+};
+
+// A single arc of the directed graph which describes an injective multimapping.
+struct InjectionArc {
+  InjectionArc(int in_source, int in_dest, bool in_close)
+      : source(in_source),
+        dest(in_dest),
+        close(in_close) {
+  }
+
+  int source;
+  int dest;
+  bool close;  // if true, delete the source element after performing the
+               // mapping.
+};
+
+typedef std::vector<InjectionArc> InjectiveMultimap;
+
+BASE_EXPORT bool PerformInjectiveMultimap(const InjectiveMultimap& map,
+                                          InjectionDelegate* delegate);
+
+BASE_EXPORT bool PerformInjectiveMultimapDestructive(
+    InjectiveMultimap* map,
+    InjectionDelegate* delegate);
+
+// This function will not call malloc but will mutate |map|
+static inline bool ShuffleFileDescriptors(InjectiveMultimap* map) {
+  FileDescriptorTableInjection delegate;
+  return PerformInjectiveMultimapDestructive(map, &delegate);
+}
+
+}  // namespace base
+
+#endif  // BASE_POSIX_FILE_DESCRIPTOR_SHUFFLE_H_
diff --git a/base/posix/file_descriptor_shuffle_unittest.cc b/base/posix/file_descriptor_shuffle_unittest.cc
new file mode 100644
index 0000000..9e1b2500
--- /dev/null
+++ b/base/posix/file_descriptor_shuffle_unittest.cc
@@ -0,0 +1,287 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/posix/file_descriptor_shuffle.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+// 'Duplicated' file descriptors start at this number
+const int kDuplicateBase = 1000;
+
+}  // namespace
+
+namespace base {
+
+struct Action {
+  enum Type {
+    CLOSE,
+    MOVE,
+    DUPLICATE,
+  };
+
+  Action(Type in_type, int in_fd1, int in_fd2 = -1)
+      : type(in_type),
+        fd1(in_fd1),
+        fd2(in_fd2) {
+  }
+
+  bool operator==(const Action& other) const {
+    return other.type == type &&
+           other.fd1 == fd1 &&
+           other.fd2 == fd2;
+  }
+
+  Type type;
+  int fd1;
+  int fd2;
+};
+
+class InjectionTracer : public InjectionDelegate {
+ public:
+  InjectionTracer()
+      : next_duplicate_(kDuplicateBase) {
+  }
+
+  virtual bool Duplicate(int* result, int fd) OVERRIDE {
+    *result = next_duplicate_++;
+    actions_.push_back(Action(Action::DUPLICATE, *result, fd));
+    return true;
+  }
+
+  virtual bool Move(int src, int dest) OVERRIDE {
+    actions_.push_back(Action(Action::MOVE, src, dest));
+    return true;
+  }
+
+  virtual void Close(int fd) OVERRIDE {
+    actions_.push_back(Action(Action::CLOSE, fd));
+  }
+
+  const std::vector<Action>& actions() const { return actions_; }
+
+ private:
+  int next_duplicate_;
+  std::vector<Action> actions_;
+};
+
+TEST(FileDescriptorShuffleTest, Empty) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  EXPECT_EQ(0u, tracer.actions().size());
+}
+
+TEST(FileDescriptorShuffleTest, Noop) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 0, false));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  EXPECT_EQ(0u, tracer.actions().size());
+}
+
+TEST(FileDescriptorShuffleTest, NoopAndClose) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 0, true));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  EXPECT_EQ(0u, tracer.actions().size());
+}
+
+TEST(FileDescriptorShuffleTest, Simple1) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 1, false));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(1u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] == Action(Action::MOVE, 0, 1));
+}
+
+TEST(FileDescriptorShuffleTest, Simple2) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 1, false));
+  map.push_back(InjectionArc(2, 3, false));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(2u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] == Action(Action::MOVE, 0, 1));
+  EXPECT_TRUE(tracer.actions()[1] == Action(Action::MOVE, 2, 3));
+}
+
+TEST(FileDescriptorShuffleTest, Simple3) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 1, true));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(2u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] == Action(Action::MOVE, 0, 1));
+  EXPECT_TRUE(tracer.actions()[1] == Action(Action::CLOSE, 0));
+}
+
+TEST(FileDescriptorShuffleTest, Simple4) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(10, 0, true));
+  map.push_back(InjectionArc(1, 1, true));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(2u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] == Action(Action::MOVE, 10, 0));
+  EXPECT_TRUE(tracer.actions()[1] == Action(Action::CLOSE, 10));
+}
+
+TEST(FileDescriptorShuffleTest, Cycle) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 1, false));
+  map.push_back(InjectionArc(1, 0, false));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(4u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] ==
+              Action(Action::DUPLICATE, kDuplicateBase, 1));
+  EXPECT_TRUE(tracer.actions()[1] == Action(Action::MOVE, 0, 1));
+  EXPECT_TRUE(tracer.actions()[2] == Action(Action::MOVE, kDuplicateBase, 0));
+  EXPECT_TRUE(tracer.actions()[3] == Action(Action::CLOSE, kDuplicateBase));
+}
+
+TEST(FileDescriptorShuffleTest, CycleAndClose1) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 1, true));
+  map.push_back(InjectionArc(1, 0, false));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(4u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] ==
+              Action(Action::DUPLICATE, kDuplicateBase, 1));
+  EXPECT_TRUE(tracer.actions()[1] == Action(Action::MOVE, 0, 1));
+  EXPECT_TRUE(tracer.actions()[2] == Action(Action::MOVE, kDuplicateBase, 0));
+  EXPECT_TRUE(tracer.actions()[3] == Action(Action::CLOSE, kDuplicateBase));
+}
+
+TEST(FileDescriptorShuffleTest, CycleAndClose2) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 1, false));
+  map.push_back(InjectionArc(1, 0, true));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(4u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] ==
+              Action(Action::DUPLICATE, kDuplicateBase, 1));
+  EXPECT_TRUE(tracer.actions()[1] == Action(Action::MOVE, 0, 1));
+  EXPECT_TRUE(tracer.actions()[2] == Action(Action::MOVE, kDuplicateBase, 0));
+  EXPECT_TRUE(tracer.actions()[3] == Action(Action::CLOSE, kDuplicateBase));
+}
+
+TEST(FileDescriptorShuffleTest, CycleAndClose3) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 1, true));
+  map.push_back(InjectionArc(1, 0, true));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(4u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] ==
+              Action(Action::DUPLICATE, kDuplicateBase, 1));
+  EXPECT_TRUE(tracer.actions()[1] == Action(Action::MOVE, 0, 1));
+  EXPECT_TRUE(tracer.actions()[2] == Action(Action::MOVE, kDuplicateBase, 0));
+  EXPECT_TRUE(tracer.actions()[3] == Action(Action::CLOSE, kDuplicateBase));
+}
+
+TEST(FileDescriptorShuffleTest, Fanout) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 1, false));
+  map.push_back(InjectionArc(0, 2, false));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(2u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] == Action(Action::MOVE, 0, 1));
+  EXPECT_TRUE(tracer.actions()[1] == Action(Action::MOVE, 0, 2));
+}
+
+TEST(FileDescriptorShuffleTest, FanoutAndClose1) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 1, true));
+  map.push_back(InjectionArc(0, 2, false));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(3u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] == Action(Action::MOVE, 0, 1));
+  EXPECT_TRUE(tracer.actions()[1] == Action(Action::MOVE, 0, 2));
+  EXPECT_TRUE(tracer.actions()[2] == Action(Action::CLOSE, 0));
+}
+
+TEST(FileDescriptorShuffleTest, FanoutAndClose2) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 1, false));
+  map.push_back(InjectionArc(0, 2, true));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(3u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] == Action(Action::MOVE, 0, 1));
+  EXPECT_TRUE(tracer.actions()[1] == Action(Action::MOVE, 0, 2));
+  EXPECT_TRUE(tracer.actions()[2] == Action(Action::CLOSE, 0));
+}
+
+TEST(FileDescriptorShuffleTest, FanoutAndClose3) {
+  InjectiveMultimap map;
+  InjectionTracer tracer;
+  map.push_back(InjectionArc(0, 1, true));
+  map.push_back(InjectionArc(0, 2, true));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &tracer));
+  ASSERT_EQ(3u, tracer.actions().size());
+  EXPECT_TRUE(tracer.actions()[0] == Action(Action::MOVE, 0, 1));
+  EXPECT_TRUE(tracer.actions()[1] == Action(Action::MOVE, 0, 2));
+  EXPECT_TRUE(tracer.actions()[2] == Action(Action::CLOSE, 0));
+}
+
+class FailingDelegate : public InjectionDelegate {
+ public:
+  virtual bool Duplicate(int* result, int fd) OVERRIDE {
+    return false;
+  }
+
+  virtual bool Move(int src, int dest) OVERRIDE {
+    return false;
+  }
+
+  virtual void Close(int fd) OVERRIDE {}
+};
+
+TEST(FileDescriptorShuffleTest, EmptyWithFailure) {
+  InjectiveMultimap map;
+  FailingDelegate failing;
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &failing));
+}
+
+TEST(FileDescriptorShuffleTest, NoopWithFailure) {
+  InjectiveMultimap map;
+  FailingDelegate failing;
+  map.push_back(InjectionArc(0, 0, false));
+
+  EXPECT_TRUE(PerformInjectiveMultimap(map, &failing));
+}
+
+TEST(FileDescriptorShuffleTest, Simple1WithFailure) {
+  InjectiveMultimap map;
+  FailingDelegate failing;
+  map.push_back(InjectionArc(0, 1, false));
+
+  EXPECT_FALSE(PerformInjectiveMultimap(map, &failing));
+}
+
+}  // namespace base