[win] Create ModuleDatabase and ModuleEventSinkImpl.

chrome/browser/conflicts/module_database_win.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 "chrome/browser/conflicts/module_database_win.h"
+
+#include <algorithm>
+
+#include "base/bind.h"
+
+namespace {
+
+// Document the assumptions made on the ProcessType enum in order to convert
+// them to bits.
+static_assert(content::PROCESS_TYPE_UNKNOWN == 1,
+              "assumes unknown process type has value 1");
+static_assert(content::PROCESS_TYPE_BROWSER == 2,
+              "assumes browser process type has value 2");
+constexpr uint32_t kMinProcessType = content::PROCESS_TYPE_BROWSER;
+
+}  // namespace
+
+ModuleDatabase::ModuleDatabase(
+    scoped_refptr<base::SequencedTaskRunner> task_runner)
+    : task_runner_(std::move(task_runner)), weak_ptr_factory_(this) {}
+
+ModuleDatabase::~ModuleDatabase() = default;
+
+void ModuleDatabase::OnProcessStarted(uint32_t process_id,
+                                      content::ProcessType process_type) {
+  DCHECK(task_runner_->RunsTasksOnCurrentThread());
+  CreateProcessInfo(process_id, process_type);
+}
+
+void ModuleDatabase::OnModuleEvent(uint32_t process_id,
+                                   const ModuleWatcher::ModuleEvent& event) {
+  // Messages can arrive from any thread (UI thread for calls over IPC, and
+  // anywhere at all for calls from ModuleWatcher), so bounce if necessary.
+  if (!task_runner_->RunsTasksOnCurrentThread()) {
+    task_runner_->PostTask(FROM_HERE, base::Bind(&ModuleDatabase::OnModuleEvent,
+                                                 weak_ptr_factory_.GetWeakPtr(),
+                                                 process_id, event));
+    return;
+  }
+
+  // In theory this should always succeed. However, it is possible for a client
+  // to misbehave and send out-of-order messages. It is easy to be tolerant of
+  // this by simply not updating the process info in this case. It's not worth
+  // crashing if this data is slightly out of sync as this is purely
+  // informational.
+  auto* process_info = GetProcessInfo(process_id);
+  if (!process_info)
+    return;
+
+  auto* module_info = FindOrCreateModuleInfo(event.module_path);
+
+  // Update the list of process types that this module has been seen in.
+  module_info->process_types |= ProcessTypeToBit(process_info->process_type);
+
+  uintptr_t load_address =
+      reinterpret_cast<uintptr_t>(event.module_load_address);
+
+  // Update the module lists for this process.
+  switch (event.event_type) {
+    case mojom::ModuleEventType::MODULE_ALREADY_LOADED:
+    case mojom::ModuleEventType::MODULE_LOADED:
+      InsertLoadAddress(module_info->module_id, load_address,
+                        &process_info->loaded_modules);
+      RemoveLoadAddressById(module_info->module_id,
+                            &process_info->unloaded_modules);
+      break;
+    case mojom::ModuleEventType::MODULE_UNLOADED:
+      RemoveLoadAddressById(module_info->module_id,
+                            &process_info->loaded_modules);
+      InsertLoadAddress(module_info->module_id, load_address,
+                        &process_info->unloaded_modules);
+      break;
+  }
+}
+
+void ModuleDatabase::OnModuleUnload(uint32_t process_id,
+                                    uintptr_t load_address) {
+  // Messages can arrive from any thread (UI thread for calls over IPC, and
+  // anywhere at all for calls from ModuleWatcher), so bounce if necessary.
+  if (!task_runner_->RunsTasksOnCurrentThread()) {
+    task_runner_->PostTask(
+        FROM_HERE,
+        base::Bind(&ModuleDatabase::OnModuleUnload,
+                   weak_ptr_factory_.GetWeakPtr(), process_id, load_address));
+    return;
+  }
+
+  // See the long-winded comment in OnModuleEvent about reasons why this can
+  // fail (but shouldn't normally).
+  auto* process_info = GetProcessInfo(process_id);
+  if (!process_info)
+    return;
+
+  // Find the module corresponding to this load address.
+  size_t i =
+      FindLoadAddressIndexByAddress(load_address, process_info->loaded_modules);
+
+  // No such module found. This shouldn't happen either, unless messages are
+  // malformed or out of order. Gracefully fail in this case.
+  if (i == kInvalidIndex)
+    return;
+
+  ModuleId module_id = process_info->loaded_modules[i].first;
+
+  // Remove from the loaded module list and insert into the unloaded module
+  // list.
+  RemoveLoadAddressByIndex(i, &process_info->loaded_modules);
+  InsertLoadAddress(module_id, load_address, &process_info->unloaded_modules);
+}
+
+void ModuleDatabase::OnProcessEnded(uint32_t process_id) {
+  // Messages can arrive from any thread (UI thread for calls over IPC, and
+  // anywhere at all for calls from ModuleWatcher), so bounce if necessary.
+  if (!task_runner_->RunsTasksOnCurrentThread()) {
+    task_runner_->PostTask(
+        FROM_HERE, base::Bind(&ModuleDatabase::OnProcessEnded,
+                              weak_ptr_factory_.GetWeakPtr(), process_id));
+    return;
+  }
+
+  DeleteProcessInfo(process_id);
+}
+
+// static
+uint32_t ModuleDatabase::ProcessTypeToBit(content::ProcessType process_type) {
+  uint32_t bit_index = static_cast<uint32_t>(process_type) - kMinProcessType;
+  DCHECK_LE(0u, bit_index);
+  DCHECK_GE(31u, bit_index);
+  uint32_t bit = (1 << bit_index);
+  return bit;
+}
+
+// static
+content::ProcessType ModuleDatabase::BitIndexToProcessType(uint32_t bit_index) {
+  DCHECK_LE(0u, bit_index);
+  DCHECK_GE(31u, bit_index);
+  return static_cast<content::ProcessType>(bit_index + kMinProcessType);
+}
+
+// static
+size_t ModuleDatabase::FindLoadAddressIndexById(
+    ModuleId module_id,
+    const ModuleLoadAddresses& load_addresses) {
+  // Process elements in reverse order so that RemoveLoadAddressById can handle
+  // the more common case of removing the maximum element in O(1).
+  for (size_t i = load_addresses.size() - 1; i < load_addresses.size(); --i) {
+    if (load_addresses[i].first == module_id)
+      return i;
+  }
+  return kInvalidIndex;
+}
+
+// static
+size_t ModuleDatabase::FindLoadAddressIndexByAddress(
+    uintptr_t load_address,
+    const ModuleLoadAddresses& load_addresses) {
+  for (size_t i = 0; i < load_addresses.size(); ++i) {
+    if (load_addresses[i].second == load_address)
+      return i;
+  }
+  return kInvalidIndex;
+}
+
+// static
+void ModuleDatabase::InsertLoadAddress(ModuleId module_id,
+                                       uintptr_t load_address,
+                                       ModuleLoadAddresses* load_addresses) {
+  // A very small optimization: the largest module_id is always placed at the
+  // end of the array. This is the most common case, and allows O(1)
+  // determination that a |module_id| isn't present when it's bigger than the
+  // maximum already in the array. This keeps insertions to O(1) in the usual
+  // case.
+  if (load_addresses->empty() || module_id > load_addresses->back().first) {
+    load_addresses->emplace_back(module_id, load_address);
+    return;
+  }
+
+  // If the module exists in the collection then update the load address and
+  // return. This should never really occur, unless the client is deliberately
+  // misbehaving or a race causes a reload event (at a different address) to be
+  // processed before the corresponding unload. This is very unlikely.
+  size_t i = FindLoadAddressIndexById(module_id, *load_addresses);
+  if (i != kInvalidIndex) {
+    (*load_addresses)[i].second = load_address;
+    return;
+  }
+
+  // The module does not exist, and by definition is smaller in value than
+  // the largest module ID already present. Add it, ensuring that the largest
+  // module ID stays at the end.
+  load_addresses->emplace(--load_addresses->end(), module_id, load_address);
+
+  return;
+}
+
+// static
+void ModuleDatabase::RemoveLoadAddressById(
+    ModuleId module_id,
+    ModuleLoadAddresses* load_addresses) {
+  if (load_addresses->empty())
+    return;
+
+  // This handles the special case of removing the max element in O(1), as
+  // FindLoadAddressIndexById processes the elements in reverse order.
+  size_t i = FindLoadAddressIndexById(module_id, *load_addresses);
+  RemoveLoadAddressByIndex(i, load_addresses);
+}
+
+// static
+void ModuleDatabase::RemoveLoadAddressByIndex(
+    size_t index,
+    ModuleLoadAddresses* load_addresses) {
+  DCHECK_LE(0u, index);
+  DCHECK_GT(load_addresses->size(), index);
+
+  // Special case: removing the last module (with maximum id). Need to find the
+  // new maximum element and ensure it goes to the end.
+  if (load_addresses->size() > 2 && index + 1 == load_addresses->size()) {
+    // Find the index of the new maximum element.
+    ModuleId max_id = -1;  // These start at zero.
+    int max_index = kInvalidIndex;
+    for (size_t i = 0; i < load_addresses->size() - 1; ++i) {
+      if ((*load_addresses)[i].first > max_id) {
+        max_id = (*load_addresses)[i].first;
+        max_index = i;
+      }
+    }
+
+    // Remove the max element.
+    load_addresses->resize(load_addresses->size() - 1);
+
+    // If the new max element isn't in the last position, then swap it so it is.
+    int last_index = load_addresses->size() - 1;
+    if (max_index != last_index)
+      std::swap((*load_addresses)[max_index], (*load_addresses)[last_index]);
+
+    return;
+  }
+
+  // If the element to be removed is second last then a single copy is
+  // sufficient.
+  if (index + 2 == load_addresses->size()) {
+    (*load_addresses)[index] = (*load_addresses)[index + 1];
+  } else {
+    // In the general case two copies are necessary.
+    int max_index = load_addresses->size() - 1;
+    (*load_addresses)[index] = (*load_addresses)[max_index - 1];
+    (*load_addresses)[max_index - 1] = (*load_addresses)[max_index];
+  }
+
+  // Remove the last element, which is now duplicated.
+  load_addresses->resize(load_addresses->size() - 1);
+}
+
+ModuleDatabase::ModuleInfo* ModuleDatabase::FindOrCreateModuleInfo(
+    const base::FilePath& module_path) {
+  ModuleInfo key(module_path, modules_.size());
+  auto result = modules_.insert(key);
+  // Cast away constness so that the non-key portions of the object can be
+  // modified. The key portions of the object are themselves marked const, so
+  // this causes no trouble with std::set.
+  return const_cast<ModuleInfo*>(&(*result.first));
+}
+
+ModuleDatabase::ProcessInfo* ModuleDatabase::GetProcessInfo(
+    uint32_t process_id) {
+  ProcessInfo key(process_id, content::PROCESS_TYPE_UNKNOWN);
+  auto it = processes_.find(key);
+  if (it == processes_.end())
+    return nullptr;
+  // Cast away constness so that the non-key portions of the object can be
+  // modified. The key portions of the object are themselves marked const, so
+  // this causes no trouble with std::set.
+  return const_cast<ProcessInfo*>(&(*it));
+}
+
+void ModuleDatabase::CreateProcessInfo(uint32_t process_id,
+                                       content::ProcessType process_type) {
+  ProcessInfo key(process_id, process_type);
+  processes_.insert(key);

[grt (UTC plus 2), 2016/12/20 21:09:53]

https://youtu.be/Aharq3PFX54
  processes_.emplace(process_id, process_type);

[chrisha, 2016/12/21 20:15:00]

Done.

+}
+
+void ModuleDatabase::DeleteProcessInfo(uint32_t process_id) {
+  ProcessInfo key(process_id, content::PROCESS_TYPE_UNKNOWN);
+  auto it = processes_.find(key);
+  if (it == processes_.end())

[grt (UTC plus 2), 2016/12/20 21:09:53]

nit: flip logic and move the "else" into the "if" part so that "return;" becomes
unnecessary?

[chrisha, 2016/12/21 20:15:00]

Done.

+    return;
+  processes_.erase(it);
+}
+
+// ModuleDatabase::ModuleInfo --------------------------------------------------
+
+ModuleDatabase::ModuleInfo::ModuleInfo(const base::FilePath& module_path,
+                                       uint32_t module_id)
+    : module_path(module_path), module_id(module_id), process_types(0) {}
+
+bool ModuleDatabase::ModuleInfo::operator<(const ModuleInfo& mi) const {
+  return module_path < mi.module_path;
+}
+
+// ModuleDatabase::ProcessInfo -------------------------------------------------
+
+ModuleDatabase::ProcessInfo::ProcessInfo(uint32_t process_id,
+                                         content::ProcessType process_type)
+    : process_id(process_id), process_type(process_type) {}
+
+bool ModuleDatabase::ProcessInfo::operator<(const ProcessInfo& pi) const {
+  return process_id < pi.process_id;
+}