[CacheTool] Add a "list_dups" command

net/tools/cachetool/cachetool.cc

 // Copyright 2016 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 <iostream>
 #include <memory>
+#include <unordered_map>
 
 #include "base/at_exit.h"
 #include "base/command_line.h"
 #include "base/files/file_path.h"
+#include "base/format_macros.h"
 #include "base/logging.h"
 #include "base/macros.h"
+#include "base/md5.h"
 #include "base/message_loop/message_loop.h"
 #include "base/run_loop.h"
 #include "base/strings/string_number_conversions.h"
+#include "base/strings/string_piece.h"
+#include "base/strings/stringprintf.h"
 #include "net/base/io_buffer.h"
 #include "net/base/test_completion_callback.h"
 #include "net/disk_cache/disk_cache.h"
 #include "net/http/http_cache.h"
 #include "net/http/http_response_headers.h"
 #include "net/http/http_util.h"
 
 using disk_cache::Backend;
 using disk_cache::Entry;
 
 namespace {
 
+struct EntryData {
+  std::string url;
+  std::string mime_type;
+  int size;
+};
+
 constexpr int kResponseInfoIndex = 0;
+constexpr int kResponseContentIndex = 1;
 
 const char* const kCommandNames[] = {
     "stop",          "get_size",   "list_keys",          "get_stream_for_key",
-    "delete_stream", "delete_key", "update_raw_headers",
+    "delete_stream", "delete_key", "update_raw_headers", "list_dups",
 };
 
 // Prints the command line help.
 void PrintHelp() {
   std::cout << "cachetool <cache_path> <cache_backend_type> <subcommand> "
             << std::endl
             << std::endl;
   std::cout << "Available cache backend types: simple, blockfile" << std::endl;
   std::cout << "Available subcommands:" << std::endl;
   std::cout << "  batch: Starts cachetool to process serialized commands "
             << "passed down by the standard input and return commands output "
             << "in the stdout until the stop command is received." << std::endl;
   std::cout << "  delete_key <key>: Delete key from cache." << std::endl;
   std::cout << "  delete_stream <key> <index>: Delete a particular stream of a"
             << " given key." << std::endl;
   std::cout << "  get_size: Calculate the total size of the cache in bytes."
             << std::endl;
   std::cout << "  get_stream <key> <index>: Print a particular stream for a"
             << " given key." << std::endl;
   std::cout << "  list_keys: List all keys in the cache." << std::endl;
+  std::cout << "  list_dups: List all resources with duplicate bodies in the "
+            << "cache." << std::endl;
   std::cout << "  update_raw_headers <key>: Update stdin as the key's raw "
             << "response headers." << std::endl;
   std::cout << "  stop: Verify that the cache can be opened and return, "
             << "confirming the cache exists and is of the right type."
             << std::endl;
   std::cout << "Expected values of <index> are:" << std::endl;
   std::cout << "  0 (HTTP response headers)" << std::endl;
   std::cout << "  1 (transport encoded content)" << std::endl;
   std::cout << "  2 (compiled content)" << std::endl;
 }
 
 // Generic command input/output.
 class CommandMarshal {
  public:
-  CommandMarshal(Backend* cache_backend)
-      : command_failed_(false), cache_backend_(cache_backend){};
-  virtual ~CommandMarshal(){};
+  explicit CommandMarshal(Backend* cache_backend)
+      : command_failed_(false), cache_backend_(cache_backend) {}
+  virtual ~CommandMarshal() {}
 
   // Reads the next command's name to execute.
   virtual std::string ReadCommandName() = 0;
 
   // Reads the next parameter as an integer.
   virtual int ReadInt() = 0;
 
   // Reads the next parameter as stream index.
   int ReadStreamIndex() {
     if (has_failed())
@@ skipping 18 matching lines @@
   // Communicates back a string.
   virtual void ReturnString(const std::string& string) = 0;
 
   // Communicates back a buffer.
   virtual void ReturnBuffer(net::GrowableIOBuffer* buffer) = 0;
 
   // Communicates back command failure.
   virtual void ReturnFailure(const std::string& error_msg) = 0;
 
   // Communicates back command success.
-  virtual void ReturnSuccess() { DCHECK(!command_failed_); };
+  virtual void ReturnSuccess() { DCHECK(!command_failed_); }
 
   // Returns whether the command has failed.
   inline bool has_failed() { return command_failed_; }
 
   // Returns the opened cache backend.
   Backend* cache_backend() { return cache_backend_; }
 
  protected:
   bool command_failed_;
   Backend* const cache_backend_;
@@ skipping 73 matching lines @@
  private:
   const base::CommandLine::StringVector command_line_args_;
   size_t args_id_;
 };
 
 // Online command input/output that receives pickled commands from stdin and
 // returns their results back in stdout. Send the stop command to properly exit
 // cachetool's main loop.
 class StreamCommandMarshal final : public CommandMarshal {
  public:
-  StreamCommandMarshal(Backend* cache_backend)
+  explicit StreamCommandMarshal(Backend* cache_backend)
       : CommandMarshal(cache_backend) {}
 
   // Implements CommandMarshal.
   std::string ReadCommandName() override {
     if (has_failed())
       return "";
     std::cout.flush();
     size_t command_id = static_cast<size_t>(std::cin.get());
     if (command_id >= arraysize(kCommandNames)) {
       ReturnFailure("Unknown command.");
@@ skipping 82 matching lines @@
     std::string url = entry->GetKey();
     command_marshal->ReturnString(url);
     entry->Close();
     entry = nullptr;
     rv = entry_iterator->OpenNextEntry(&entry, cb.callback());
   }
   command_marshal->ReturnString("");
   return true;
 }
 
+bool GetResponseInfoForEntry(disk_cache::Entry* entry,
+                             net::HttpResponseInfo* response_info) {
+  int size = entry->GetDataSize(kResponseInfoIndex);
+  if (size == 0)
+    return false;
+  scoped_refptr<net::IOBuffer> buffer = new net::IOBufferWithSize(size);
+  net::TestCompletionCallback cb;
+
+  int bytes_read = 0;
+  while (true) {
+    int rv = entry->ReadData(kResponseInfoIndex, bytes_read, buffer.get(), size,
+                             cb.callback());
+    rv = cb.GetResult(rv);
+    if (rv < 0) {
+      entry->Close();
+      return false;
+    }
+
+    if (rv == 0) {
+      bool truncated_response_info = false;
+      net::HttpCache::ParseResponseInfo(buffer->data(), size, response_info,
+                                        &truncated_response_info);
+      return !truncated_response_info;
+    }
+
+    bytes_read += rv;
+  }
+
+  NOTREACHED();
+  return false;
+}
+
+std::string GetMD5ForResponseBody(disk_cache::Entry* entry) {
+  if (entry->GetDataSize(kResponseContentIndex) == 0)
+    return "";
+
+  const int kInitBufferSize = 80 * 1024;
+  scoped_refptr<net::IOBuffer> buffer =
+      new net::IOBufferWithSize(kInitBufferSize);
+  net::TestCompletionCallback cb;
+
+  base::MD5Context ctx;
+  base::MD5Init(&ctx);
+
+  int bytes_read = 0;
+  while (true) {
+    int rv = entry->ReadData(kResponseContentIndex, bytes_read, buffer.get(),
+                             kInitBufferSize, cb.callback());
+    rv = cb.GetResult(rv);
+    if (rv < 0) {
+      entry->Close();
+      return "";
+    }
+
+    if (rv == 0) {
+      base::MD5Digest digest;
+      base::MD5Final(&digest, &ctx);
+      return base::MD5DigestToBase16(digest);
+    }
+
+    bytes_read += rv;
+    MD5Update(&ctx, base::StringPiece(buffer->data(), rv));
+  }
+
+  NOTREACHED();
+  return "";
+}
+
+void ListDups(CommandMarshal* command_marshal) {
+  std::unique_ptr<Backend::Iterator> entry_iterator =
+      command_marshal->cache_backend()->CreateIterator();
+  Entry* entry = nullptr;
+  net::TestCompletionCallback cb;
+  int rv = entry_iterator->OpenNextEntry(&entry, cb.callback());
+  command_marshal->ReturnSuccess();
+
+  std::unordered_map<std::string, std::vector<EntryData>> md5_entries;
+
+  int total_entries = 0;
+
+  while (cb.GetResult(rv) == net::OK) {
+    total_entries += 1;
+    net::HttpResponseInfo response_info;
+    if (!GetResponseInfoForEntry(entry, &response_info)) {
+      entry->Close();
+      entry = nullptr;
+      rv = entry_iterator->OpenNextEntry(&entry, cb.callback());
+      continue;
+    }
+
+    std::string hash = GetMD5ForResponseBody(entry);
+    if (hash.empty()) {
+      // Sparse entries and empty bodies are skipped.
+      entry->Close();
+      entry = nullptr;
+      rv = entry_iterator->OpenNextEntry(&entry, cb.callback());
+      continue;
+    }
+
+    EntryData entry_data;
+
+    entry_data.url = entry->GetKey();
+    entry_data.size = entry->GetDataSize(kResponseContentIndex);
+    if (response_info.headers)
+      response_info.headers->GetMimeType(&entry_data.mime_type);
+
+    auto iter = md5_entries.find(hash);
+    if (iter == md5_entries.end())
+      md5_entries.insert(
+          std::make_pair(hash, std::vector<EntryData>{entry_data}));
+    else
+      iter->second.push_back(entry_data);
+
+    entry->Close();
+    entry = nullptr;
+    rv = entry_iterator->OpenNextEntry(&entry, cb.callback());
+  }
+
+  // Print the duplicates and collect stats.
+  int total_duped_entries = 0;
+  int64_t total_duped_bytes = 0u;
+  for (const auto& hash_and_entries : md5_entries) {
+    if (hash_and_entries.second.size() == 1)
+      continue;
+
+    int dups = hash_and_entries.second.size() - 1;
+    total_duped_entries += dups;
+    total_duped_bytes += hash_and_entries.second[0].size * dups;
+
+    for (const auto& entry : hash_and_entries.second) {
+      std::string out = base::StringPrintf(
+          "%d, %s, %s", entry.size, entry.url.c_str(), entry.mime_type.c_str());
+      command_marshal->ReturnString(out);
+    }
+  }
+
+  // Print the stats.
+  rv = command_marshal->cache_backend()->CalculateSizeOfAllEntries(
+      cb.callback());
+  rv = cb.GetResult(rv);
+  LOG(ERROR) << "Wasted bytes = " << total_duped_bytes;
+  LOG(ERROR) << "Wasted entries = " << total_duped_entries;
+  LOG(ERROR) << "Total entries = " << total_entries;
+  LOG(ERROR) << "Cache size = " << rv;
+  LOG(ERROR) << "Percentage of cache wasted = " << total_duped_bytes * 100 / rv;
+}
+
 // Gets a key's stream to a buffer.
 scoped_refptr<net::GrowableIOBuffer> GetStreamForKeyBuffer(
     CommandMarshal* command_marshal,
     const std::string& key,
     int index) {
   DCHECK(!command_marshal->has_failed());
   Entry* cache_entry;
   net::TestCompletionCallback cb;
   int rv = command_marshal->cache_backend()->OpenEntry(key, &cache_entry,
                                                        cb.callback());
@@ skipping 138 matching lines @@
     } else if (subcommand == "delete_stream") {
       DeleteStreamForKey(command_marshal);
     } else if (subcommand == "get_size") {
       GetSize(command_marshal);
     } else if (subcommand == "get_stream") {
       GetStreamForKey(command_marshal);
     } else if (subcommand == "list_keys") {
       ListKeys(command_marshal);
     } else if (subcommand == "update_raw_headers") {
       UpdateRawResponseHeaders(command_marshal);
+    } else if (subcommand == "list_dups") {
+      ListDups(command_marshal);
     } else {
       // The wrong subcommand is originated from the command line.
       command_marshal->ReturnFailure("Unknown command.");
       PrintHelp();
     }
   }
   return false;
 }
 
 }  // namespace
@@ skipping 38 matching lines @@
   ProgramArgumentCommandMarshal program_argument_marshal(
       cache_backend.get(),
       base::CommandLine::StringVector(args.begin() + 2, args.end()));
   bool successful_commands = ExecuteCommands(&program_argument_marshal);
 
   base::RunLoop().RunUntilIdle();
   cache_backend = nullptr;
   base::RunLoop().RunUntilIdle();
   return !successful_commands;
 }