[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,
+                                      uint64_t creation_time,
+                                      content::ProcessType process_type) {
+  DCHECK(task_runner_->RunsTasksOnCurrentThread());
+  CreateProcessInfo(process_id, creation_time, process_type);
+}
+
+void ModuleDatabase::OnModuleLoad(uint32_t process_id,
+                                  uint64_t creation_time,
+                                  const base::FilePath& module_path,
+                                  uint32_t module_size,
+                                  uint32_t module_time_date_stamp,
+                                  uintptr_t module_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::OnModuleLoad,
+                              weak_ptr_factory_.GetWeakPtr(), process_id,
+                              creation_time, module_path, module_size,
+                              module_time_date_stamp, module_load_address));
+    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, creation_time);
+  if (!process_info)
+    return;
+
+  auto* module_info =
+      FindOrCreateModuleInfo(module_path, module_size, module_time_date_stamp);
+
+  // Update the list of process types that this module has been seen in.
+  module_info->process_types |= ProcessTypeToBit(process_info->process_type);
+
+  // Update the load address maps.
+  InsertLoadAddress(module_info->module_id, module_load_address,
+                    &process_info->loaded_modules);
+  RemoveLoadAddressById(module_info->module_id,
+                        &process_info->unloaded_modules);
+}
+
+void ModuleDatabase::OnModuleUnload(uint32_t process_id,
+                                    uint64_t creation_time,
+                                    uintptr_t module_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,
+                              creation_time, module_load_address));
+    return;
+  }
+
+  // See the long-winded comment in OnModuleLoad about reasons why this can
+  // fail (but shouldn't normally).
+  auto* process_info = GetProcessInfo(process_id, creation_time);
+  if (!process_info)
+    return;
+
+  // Find the module corresponding to this load address. This is O(1) in the
+  // common case of removing a recently removed module, but O(n) worst case.
+  // Thankfully, unload events occur far less often and n is quite small.
+  size_t i = FindLoadAddressIndexByAddress(module_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, module_load_address,
+                    &process_info->unloaded_modules);
+}
+
+void ModuleDatabase::OnProcessEnded(uint32_t process_id,
+                                    uint64_t creation_time) {
+  // 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, creation_time));
+    return;
+  }
+
+  DeleteProcessInfo(process_id, creation_time);
+}
+
+// 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;

[grt (UTC plus 2), 2016/12/22 14:19:06]

nit: omit this and previous line

[chrisha, 2017/01/03 21:34:47]

Done.

+}
+
+// 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);

[grt (UTC plus 2), 2016/12/22 14:19:06]

index is unsigned, so isn't this unconditionally true?

[chrisha, 2017/01/03 21:34:47]

Oops, left over from when it was as int. Removed.

+  DCHECK_GT(load_addresses->size(), index);

[grt (UTC plus 2), 2016/12/22 14:19:06]

i think this is more natural the other way: index < size

[chrisha, 2017/01/03 21:34:47]

Done.

+
+  // 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);

[grt (UTC plus 2), 2016/12/22 14:19:05]

nit: it's been established on line 223 that index == load_addresses->size() - 1,
so you could use index here. maybe that's too subtle, though.

[chrisha, 2017/01/03 21:34:47]

Done. Also made the comment more verbose.

+
+    // 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,
+    uint32_t module_size,
+    uint32_t module_time_date_stamp) {
+  ModuleInfo key(module_path, module_size, module_time_date_stamp,
+                 modules_.size());
+  auto result = modules_.emplace(key);

[grt (UTC plus 2), 2016/12/22 14:19:05]

nit: get rid of |key| so that only one instance is created in the right place.

[chrisha, 2017/01/03 21:34:47]

Done.

+  // 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,
+    uint64_t creation_time) {
+  ProcessInfo key(process_id, creation_time, 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,
+                                       uint64_t creation_time,
+                                       content::ProcessType process_type) {
+  ProcessInfo key(process_id, creation_time, process_type);
+  processes_.emplace(key);

[grt (UTC plus 2), 2016/12/22 14:19:06]

nit: get rid of |key| so that only one instance is created in the right place.

[chrisha, 2017/01/03 21:34:47]

Done.

+}
+
+void ModuleDatabase::DeleteProcessInfo(uint32_t process_id,
+                                       uint64_t creation_time) {
+  ProcessInfo key(process_id, creation_time, content::PROCESS_TYPE_UNKNOWN);
+  auto it = processes_.find(key);
+  if (it != processes_.end())
+    processes_.erase(it);
+}
+
+// ModuleDatabase::ModuleInfo --------------------------------------------------
+
+ModuleDatabase::ModuleInfo::ModuleInfo(const base::FilePath& module_path,
+                                       uint32_t module_size,
+                                       uint32_t module_time_date_stamp,
+                                       uint32_t module_id)
+    : module_path(module_path),
+      module_size(module_size),
+      module_time_date_stamp(module_time_date_stamp),
+      module_id(module_id),
+      process_types(0) {}
+
+bool ModuleDatabase::ModuleInfo::operator<(const ModuleInfo& mi) const {
+  // The key consists of the triplet of

[grt (UTC plus 2), 2016/12/22 14:19:06]

i think std::tuple implements operator< for lexicographical ordering, so maybe
this could be simplified to:
  return std::make_tuple(module_path, module_size, module_time_date_stamp) <
std::make_tuple(mi.module_path, mi.module_size, mi.module_time_date_stamp);
which should be inherently correct?

[chrisha, 2017/01/03 21:34:47]

Great idea! Done.

+  // (module_path, module_size, module_time_date_stamp).
+  if (module_path < mi.module_path)
+    return true;
+  if (mi.module_path < module_path)  // FilePath has no operator>.
+    return false;
+  if (module_size < mi.module_size)
+    return true;
+  if (module_size > mi.module_size)
+    return false;
+  return module_time_date_stamp < mi.module_time_date_stamp;
+}
+
+// ModuleDatabase::ProcessInfo -------------------------------------------------
+
+ModuleDatabase::ProcessInfo::ProcessInfo(uint32_t process_id,
+                                         uint64_t creation_time,
+                                         content::ProcessType process_type)
+    : process_id(process_id),
+      creation_time(creation_time),
+      process_type(process_type) {}
+
+bool ModuleDatabase::ProcessInfo::operator<(const ProcessInfo& pi) const {
+  // The key consists of the pair of (process_id, creation_time).

[grt (UTC plus 2), 2016/12/22 14:19:06]

maybe use tuple or pair here, too?

[chrisha, 2017/01/03 21:34:47]

Done.

+  if (process_id < pi.process_id)
+    return true;
+  if (process_id > pi.process_id)
+    return false;
+  return creation_time < pi.creation_time;
+}