AU: Extent Mapper class

Extent Mapper will use the FIBMAP (widely supported) ioctl to find
out, for a given regular file, which extents it takes up on disk.

Review URL: http://codereview.chromium.org/650199
diff --git a/SConstruct b/SConstruct
index 0f600a2..e92a895 100644
--- a/SConstruct
+++ b/SConstruct
@@ -89,6 +89,7 @@
                    decompressing_file_writer.cc
                    delta_diff_parser.cc
                    download_action.cc
+                   extent_mapper.cc
                    extent_writer.cc
                    filesystem_copier_action.cc
                    filesystem_iterator.cc
@@ -114,6 +115,7 @@
                             decompressing_file_writer_unittest.cc
                             delta_diff_generator_unittest.cc
                             download_action_unittest.cc
+                            extent_mapper_unittest.cc
                             extent_writer_unittest.cc
                             file_writer_unittest.cc
                             filesystem_copier_action_unittest.cc
diff --git a/extent_mapper.cc b/extent_mapper.cc
new file mode 100755
index 0000000..ed528fd
--- /dev/null
+++ b/extent_mapper.cc
@@ -0,0 +1,87 @@
+// Copyright (c) 2010 The Chromium OS 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 "update_engine/extent_mapper.h"
+
+#include <sys/ioctl.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+
+#include <assert.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <linux/fs.h>
+
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace extent_mapper {
+
+namespace {
+const int kBlockSize = 4096;
+}
+
+bool ExtentsForFileFibmap(const std::string& path, std::vector<Extent>* out) {
+  CHECK(out);
+  // TODO(adlr): verify path is a file
+  struct stat stbuf;
+  int rc = stat(path.c_str(), &stbuf);
+  TEST_AND_RETURN_FALSE_ERRNO(rc == 0);
+  TEST_AND_RETURN_FALSE(S_ISREG(stbuf.st_mode));
+  
+  int fd = open(path.c_str(), O_RDONLY, 0);
+  TEST_AND_RETURN_FALSE_ERRNO(fd >= 0);
+  ScopedFdCloser fd_closer(&fd);
+  
+  // Get file size in blocks
+  rc = fstat(fd, &stbuf);
+  if (rc < 0) {
+    perror("fstat");
+    return false;
+  }
+  const int block_count = (stbuf.st_size + kBlockSize - 1) / kBlockSize;
+  Extent current;
+  current.set_start_block(0);
+  current.set_num_blocks(0);
+
+  for (int i = 0; i < block_count; i++) {
+    unsigned int block = i;
+    rc = ioctl(fd, FIBMAP, &block);
+    TEST_AND_RETURN_FALSE_ERRNO(rc == 0);
+    
+    // Add next block to extents
+    if (current.num_blocks() == 0) {
+      // We're starting a new extent
+      current.set_start_block(block);
+      current.set_num_blocks(1);
+      continue;
+    }
+    if ((current.start_block() + current.num_blocks()) == block) {
+      // We're continuing the last extent
+      current.set_num_blocks(current.num_blocks() + 1);
+      continue;
+    }
+    // We're starting a new extent and keeping the current one
+    out->push_back(current);
+    current.set_start_block(block);
+    current.set_num_blocks(1);
+    continue;
+  }
+  
+  if (current.num_blocks() > 0)
+    out->push_back(current);
+
+  return true;
+}
+
+}  // namespace extent_mapper
+
+}  // namespace chromeos_update_engine
diff --git a/extent_mapper.h b/extent_mapper.h
new file mode 100755
index 0000000..acdd418
--- /dev/null
+++ b/extent_mapper.h
@@ -0,0 +1,22 @@
+// Copyright (c) 2010 The Chromium OS 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 CHROMEOS_PLATFORM_UPDATE_ENGINE_EXTENT_MAPPER_H__
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_EXTENT_MAPPER_H__
+
+#include <string>
+#include <vector>
+#include "update_engine/update_metadata.pb.h"
+
+namespace chromeos_update_engine {
+
+namespace extent_mapper {
+
+bool ExtentsForFileFibmap(const std::string& path, std::vector<Extent>* out);
+
+}  // namespace extent_mapper
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_EXTENT_MAPPER_H__
diff --git a/extent_mapper_unittest.cc b/extent_mapper_unittest.cc
new file mode 100644
index 0000000..6962004
--- /dev/null
+++ b/extent_mapper_unittest.cc
@@ -0,0 +1,54 @@
+// Copyright (c) 2010 The Chromium OS 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 <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+#include <set>
+#include <string>
+#include <vector>
+#include <gtest/gtest.h>
+#include "base/basictypes.h"
+#include "update_engine/extent_mapper.h"
+#include "update_engine/utils.h"
+
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class ExtentMapperTest : public ::testing::Test {};
+
+TEST(ExtentMapperTest, RunAsRootSimpleTest) {
+  // It's hard to have a concrete test for extent mapping without including
+  // a specific filesystem image.
+  // In lieu of this, we do a weak test: make sure the extents of the unittest
+  // executable are consistent and they match with the size of the file.
+  const string kFilename = "/proc/self/exe";
+  const off_t kBlockSize = 4096;
+  
+  vector<Extent> extents;
+  
+  ASSERT_TRUE(extent_mapper::ExtentsForFileFibmap(kFilename, &extents));
+  
+  EXPECT_FALSE(extents.empty());
+  set<uint64> blocks;
+  
+  for (vector<Extent>::const_iterator it = extents.begin();
+       it != extents.end(); ++it) {
+    for (uint64 block = it->start_block();
+         block < it->start_block() + it->num_blocks();
+         block++) {
+      EXPECT_FALSE(utils::SetContainsKey(blocks, block));
+      blocks.insert(block);
+    }
+  }
+  
+  struct stat stbuf;
+  EXPECT_EQ(0, stat(kFilename.c_str(), &stbuf));
+  EXPECT_EQ(blocks.size(), (stbuf.st_size + kBlockSize - 1)/kBlockSize);
+}
+
+}  // namespace chromeos_update_engine