Add base to the repository.

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

1 files changed, 545 insertions, 0 deletions

diff --git a/base/stats_table.cc b/base/stats_table.cc
new file mode 100644
index 0000000..8213c34
--- /dev/null
+++ b/base/stats_table.cc
@@ -0,0 +1,545 @@
+// Copyright 2008, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//    * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//    * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//    * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#include "base/stats_table.h"
+
+#include "base/logging.h"
+#include "base/thread_local_storage.h"
+
+// The StatsTable uses a shared memory segment that is laid out as follows
+//
+// +-------------------------------------------+
+// | Version | Size | MaxCounters | MaxThreads |
+// +-------------------------------------------+
+// | Thread names table                        |
+// +-------------------------------------------+
+// | Thread TID table                          |
+// +-------------------------------------------+
+// | Thread PID table                          |
+// +-------------------------------------------+
+// | Counter names table                       |
+// +-------------------------------------------+
+// | Data                                      |
+// +-------------------------------------------+
+//
+// The data layout is a grid, where the columns are the thread_ids and the
+// rows are the counter_ids.
+//
+// If the first character of the thread_name is '\0', then that column is
+// empty.
+// If the first character of the counter_name is '\0', then that row is
+// empty.
+//
+// About Locking:
+// This class is designed to be both multi-thread and multi-process safe.
+// Aside from initialization, this is done by partitioning the data which
+// each thread uses so that no locking is required.  However, to allocate
+// the rows and columns of the table to particular threads, locking is
+// required.
+//
+// At the shared-memory level, we have a lock.  This lock protects the
+// shared-memory table only, and is used when we create new counters (e.g.
+// use rows) or when we register new threads (e.g. use columns).  Reading
+// data from the table does not require any locking at the shared memory
+// level.
+//
+// Each process which accesses the table will create a StatsTable object.
+// The StatsTable maintains a hash table of the existing counters in the
+// table for faster lookup.  Since the hash table is process specific,
+// each process maintains its own cache.  We avoid complexity here by never
+// de-allocating from the hash table.  (Counters are dynamically added,
+// but not dynamically removed).
+
+// In order for external viewers to be able to read our shared memory,
+// we all need to use the same size ints.
+COMPILE_ASSERT(sizeof(int)==4, expect_4_byte_ints);
+
+namespace {
+
+// An internal version in case we ever change the format of this
+// file, and so that we can identify our table.
+const int kTableVersion = 0x13131313;
+
+// The name for un-named counters and threads in the table.
+const wchar_t kUnknownName[] = L"<unknown>";
+
+// Various header information contained in the memory mapped segment.
+struct TableHeader {
+  int version;
+  int size;
+  int max_counters;
+  int max_threads;
+};
+
+// Calculates delta to align an offset to the size of an int
+inline int AlignOffset(int offset) {
+  return (sizeof(int) - (offset % sizeof(int))) % sizeof(int);
+}
+
+inline int AlignedSize(int size) {
+  return size + AlignOffset(size);
+}
+
+// StatsTableTLSData carries the data stored in the TLS slots for the
+// StatsTable.  This is used so that we can properly cleanup when the
+// thread exits and return the table slot.
+//
+// Each thread that calls RegisterThread in the StatsTable will have
+// a StatsTableTLSData stored in its TLS.
+struct StatsTableTLSData {
+  StatsTable* table;
+  int slot;
+};
+
+// The SlotReturnFunction is called at thread exit for each thread
+// which used the StatsTable.
+static void SlotReturnFunction(void* data) {
+  StatsTableTLSData* tls_data = static_cast<StatsTableTLSData*>(data);
+  if (tls_data) {
+    DCHECK(tls_data->table);
+    tls_data->table->UnregisterThread();
+  }
+}
+
+}  // namespace
+
+// The StatsTablePrivate maintains convenience pointers into the
+// shared memory segment.  Use this class to keep the data structure
+// clean and accessible.
+class StatsTablePrivate {
+ public:
+  // Create the StatsTablePrivate based on expected size parameters.
+  StatsTablePrivate(void* memory, int size, int max_threads, int max_counters);
+
+  // Accessors for our header pointers
+  TableHeader* table_header() const { return table_header_; }
+  int version() const { return table_header_->version; }
+  int size() const { return table_header_->size; }
+  int max_counters() const { return table_header_->max_counters; }
+  int max_threads() const { return table_header_->max_threads; }
+
+  // Accessors for our tables
+  wchar_t* thread_name(int slot_id) const {
+    return &thread_names_table_[
+      (slot_id-1) * (StatsTable::kMaxThreadNameLength)];
+  }
+  int* thread_tid(int slot_id) const {
+    return &(thread_tid_table_[slot_id-1]);
+  }
+  int* thread_pid(int slot_id) const {
+    return &(thread_pid_table_[slot_id-1]);
+  }
+  wchar_t* counter_name(int counter_id) const {
+    return &counter_names_table_[
+      (counter_id-1) * (StatsTable::kMaxCounterNameLength)];
+  }
+  int* row(int counter_id) const {
+    return &data_table_[(counter_id-1) * max_threads()];
+  }
+
+ private:
+  // Initializes the table on first access.  Sets header values
+  // appropriately and zeroes all counters.
+  void InitializeTable(void* memory, int size, int max_counters,
+                       int max_threads);
+
+  // Initializes our in-memory pointers into a pre-created StatsTable.
+  void ComputeMappedPointers(void* memory);
+
+  TableHeader* table_header_;
+  wchar_t* thread_names_table_;
+  int* thread_tid_table_;
+  int* thread_pid_table_;
+  wchar_t* counter_names_table_;
+  int* data_table_;
+};
+
+StatsTablePrivate::StatsTablePrivate(void* memory, int size, int max_threads,
+                                     int max_counters) {
+  TableHeader* header = static_cast<TableHeader*>(memory);
+  // If the version does not match, then assume the table needs
+  // to be initialized.
+  if (header->version != kTableVersion)
+    InitializeTable(memory, size, max_counters, max_threads);
+
+  // We have a valid table, so compute our pointers.
+  ComputeMappedPointers(memory);
+}
+
+void StatsTablePrivate::InitializeTable(void* memory, int size,
+                                        int max_counters,
+                                        int max_threads) {
+  // Zero everything.
+  memset(memory, 0, size);
+
+  // Initialize the header.
+  TableHeader* header = static_cast<TableHeader*>(memory);
+  header->version = kTableVersion;
+  header->size = size;
+  header->max_counters = max_counters;
+  header->max_threads = max_threads;
+}
+
+void StatsTablePrivate::ComputeMappedPointers(void* memory) {
+  char* data = static_cast<char*>(memory);
+  int offset = 0;
+
+  table_header_ = reinterpret_cast<TableHeader*>(data);
+  offset += sizeof(*table_header_);
+  offset += AlignOffset(offset);
+
+  // Verify we're looking at a valid StatsTable.
+  DCHECK_EQ(table_header_->version, kTableVersion);
+
+  thread_names_table_ = reinterpret_cast<wchar_t*>(data + offset);
+  offset += sizeof(wchar_t) *
+            max_threads() * StatsTable::kMaxThreadNameLength;
+  offset += AlignOffset(offset);
+
+  thread_tid_table_ = reinterpret_cast<int*>(data + offset);
+  offset += sizeof(int) * max_threads();
+  offset += AlignOffset(offset);
+
+  thread_pid_table_ = reinterpret_cast<int*>(data + offset);
+  offset += sizeof(int) * max_threads();
+  offset += AlignOffset(offset);
+
+  counter_names_table_ = reinterpret_cast<wchar_t*>(data + offset);
+  offset += sizeof(wchar_t) *
+            max_counters() * StatsTable::kMaxCounterNameLength;
+  offset += AlignOffset(offset);
+
+  data_table_ = reinterpret_cast<int*>(data + offset);
+  offset += sizeof(int) * max_threads() * max_counters();
+
+  DCHECK_EQ(offset, size());
+}
+
+
+
+// We keep a singleton table which can be easily accessed.
+StatsTable* StatsTable::global_table_ = NULL;
+
+StatsTable::StatsTable(const std::wstring& name, int max_threads,
+                       int max_counters)
+    : tls_index_(ThreadLocalStorage::Alloc(SlotReturnFunction)) {
+  int table_size =
+    AlignedSize(sizeof(TableHeader)) +
+    AlignedSize((max_counters * sizeof(wchar_t) * kMaxCounterNameLength)) +
+    AlignedSize((max_threads * sizeof(wchar_t) * kMaxThreadNameLength)) +
+    AlignedSize(max_threads * sizeof(int)) +
+    AlignedSize(max_threads * sizeof(int)) +
+    AlignedSize((sizeof(int) * (max_counters * max_threads)));
+
+  impl_ = NULL;
+  // TODO(mbelshe): Move this out of the constructor
+  if (shared_memory_.Create(name, false, true, table_size))
+    if (shared_memory_.Map(table_size))
+      impl_ = new StatsTablePrivate(shared_memory_.memory(), table_size,
+                                    max_threads, max_counters);
+  if (!impl_)
+    LOG(ERROR) << "StatsTable did not initialize:" << GetLastError();
+}
+
+StatsTable::~StatsTable() {
+  // Before we tear down our copy of the table, be sure to
+  // unregister our thread.
+  UnregisterThread();
+
+  // Return ThreadLocalStorage.  At this point, if any registered threads
+  // still exist, they cannot Unregister.
+  ThreadLocalStorage::Free(tls_index_);
+
+  // Cleanup our shared memory.
+  delete impl_;
+
+  // If we are the global table, unregister ourselves.
+  if (global_table_ == this)
+    global_table_ = NULL;
+}
+
+int StatsTable::RegisterThread(const std::wstring& name) {
+  int slot = 0;
+
+  // Registering a thread requires that we lock the shared memory
+  // so that two threads don't grab the same slot.  Fortunately,
+  // thread creation shouldn't happen in inner loops.
+  {
+    SharedMemoryAutoLock lock(&shared_memory_);
+    slot = FindEmptyThread();
+    if (!slot) {
+      return 0;
+    }
+
+    DCHECK(impl_);
+
+    // We have space, so consume a column in the table.
+    std::wstring thread_name = name;
+    if (name.empty())
+      thread_name = kUnknownName;
+    wcsncpy_s(impl_->thread_name(slot), kMaxThreadNameLength,
+      thread_name.c_str(), _TRUNCATE);
+    *(impl_->thread_tid(slot)) = GetCurrentThreadId();
+    *(impl_->thread_pid(slot)) = GetCurrentProcessId();
+  }
+
+  // Set our thread local storage.
+  StatsTableTLSData* data = new StatsTableTLSData;
+  data->table = this;
+  data->slot = slot;
+  ThreadLocalStorage::Set(tls_index_, data);
+  return slot;
+}
+
+StatsTableTLSData* StatsTable::GetTLSData() const {
+  StatsTableTLSData* data =
+    static_cast<StatsTableTLSData*>(ThreadLocalStorage::Get(tls_index_));
+  if (!data)
+    return NULL;
+
+  DCHECK(data->slot);
+  DCHECK_EQ(data->table, this);
+  return data;
+}
+
+void StatsTable::UnregisterThread() {
+  StatsTableTLSData* data = GetTLSData();
+  if (!data)
+    return;
+  DCHECK(impl_);
+
+  // Mark the slot free by zeroing out the thread name.
+  wchar_t* name = impl_->thread_name(data->slot);
+  *name = L'\0';
+
+  // Remove the calling thread's TLS so that it cannot use the slot.
+  ThreadLocalStorage::Set(tls_index_, NULL);
+  delete data;
+}
+
+int StatsTable::CountThreadsRegistered() const {
+  if (!impl_)
+    return 0;
+
+  // Loop through the shared memory and count the threads that are active.
+  // We intentionally do not lock the table during the operation.
+  int count = 0;
+  for (int index = 1; index <= impl_->max_threads(); index++) {
+    wchar_t* name = impl_->thread_name(index);
+    if (*name != L'\0')
+      count++;
+  }
+  return count;
+}
+
+int StatsTable::GetSlot() const {
+  StatsTableTLSData* data = GetTLSData();
+  if (!data)
+    return 0;
+  return data->slot;
+}
+
+int StatsTable::FindEmptyThread() const {
+  // Note: the API returns slots numbered from 1..N, although
+  // internally, the array is 0..N-1.  This is so that we can return
+  // zero as "not found".
+  //
+  // The reason for doing this is because the thread 'slot' is stored
+  // in TLS, which is always initialized to zero, not -1.  If 0 were
+  // returned as a valid slot number, it would be confused with the
+  // uninitialized state.
+  if (!impl_)
+    return 0;
+
+  int index = 1;
+  for (; index <= impl_->max_threads(); index++) {
+    wchar_t* name = impl_->thread_name(index);
+    if (!*name)
+      break;
+  }
+  if (index > impl_->max_threads())
+    return 0;  // The table is full.
+  return index;
+}
+
+int StatsTable::FindCounterOrEmptyRow(const std::wstring& name) const {
+  // Note: the API returns slots numbered from 1..N, although
+  // internally, the array is 0..N-1.  This is so that we can return
+  // zero as "not found".
+  //
+  // There isn't much reason for this other than to be consistent
+  // with the way we track columns for thread slots.  (See comments
+  // in FindEmptyThread for why it is done this way).
+  if (!impl_)
+    return 0;
+
+  int free_slot = 0;
+  for (int index = 1; index <= impl_->max_counters(); index++) {
+    wchar_t* row_name = impl_->counter_name(index);
+    if (!*row_name && !free_slot)
+      free_slot = index;  // save that we found a free slot
+    else if (!wcsncmp(row_name, name.c_str(), kMaxCounterNameLength))
+      return index;
+  }
+  return free_slot;
+}
+
+int StatsTable::FindCounter(const std::wstring& name) {
+  // Note: the API returns counters numbered from 1..N, although
+  // internally, the array is 0..N-1.  This is so that we can return
+  // zero as "not found".
+  if (!impl_)
+    return 0;
+
+  // Create a scope for our auto-lock.
+  {
+    AutoLock scoped_lock(counters_lock_);
+
+    // Attempt to find the counter.
+    CountersMap::const_iterator iter;
+    iter = counters_.find(name);
+    if (iter != counters_.end())
+      return iter->second;
+  }
+
+  // Counter does not exist, so add it.
+  return AddCounter(name);
+}
+
+int StatsTable::AddCounter(const std::wstring& name) {
+  DCHECK(impl_);
+
+  if (!impl_)
+    return 0;
+
+  int counter_id = 0;
+  {
+    // To add a counter to the shared memory, we need the
+    // shared memory lock.
+    SharedMemoryAutoLock lock(&shared_memory_);
+
+    // We have space, so create a new counter.
+    counter_id = FindCounterOrEmptyRow(name);
+    if (!counter_id)
+      return 0;
+
+    std::wstring counter_name = name;
+    if (name.empty())
+      counter_name = kUnknownName;
+    wcsncpy_s(impl_->counter_name(counter_id), kMaxCounterNameLength,
+      counter_name.c_str(), _TRUNCATE);
+  }
+
+  // now add to our in-memory cache
+  {
+    AutoLock lock(counters_lock_);
+    counters_[name] = counter_id;
+  }
+  return counter_id;
+}
+
+int* StatsTable::GetLocation(int counter_id, int slot_id) const {
+  if (!impl_)
+    return NULL;
+  if (slot_id > impl_->max_threads())
+    return NULL;
+
+  int* row = impl_->row(counter_id);
+  return &(row[slot_id-1]);
+}
+
+const wchar_t* StatsTable::GetRowName(int index) const {
+  if (!impl_)
+    return NULL;
+
+  return impl_->counter_name(index);
+}
+
+int StatsTable::GetRowValue(int index, int pid) const {
+  if (!impl_)
+    return 0;
+
+  int rv = 0;
+  int* row = impl_->row(index);
+  for (int index = 0; index < impl_->max_threads(); index++) {
+    if (pid == 0 || *impl_->thread_pid(index) == pid)
+      rv += row[index];
+  }
+  return rv;
+}
+
+int StatsTable::GetRowValue(int index) const {
+  return GetRowValue(index, 0);
+}
+
+int StatsTable::GetCounterValue(const std::wstring& name, int pid) {
+  if (!impl_)
+    return 0;
+
+  int row = FindCounter(name);
+  if (!row)
+    return 0;
+  return GetRowValue(row, pid);
+}
+
+int StatsTable::GetCounterValue(const std::wstring& name) {
+  return GetCounterValue(name, 0);
+}
+
+int StatsTable::GetMaxCounters() const {
+  if (!impl_)
+    return 0;
+  return impl_->max_counters();
+}
+
+int StatsTable::GetMaxThreads() const {
+  if (!impl_)
+    return 0;
+  return impl_->max_threads();
+}
+
+int* StatsTable::FindLocation(const wchar_t* name) {
+  // Get the static StatsTable
+  StatsTable *table = StatsTable::current();
+  if (!table)
+    return NULL;
+
+  // Get the slot for this thread.  Try to register
+  // it if none exists.
+  int slot = table->GetSlot();
+  if (!slot && !(slot = table->RegisterThread(L"")))
+      return NULL;
+
+  // Find the counter id for the counter.
+  std::wstring str_name(name);
+  int counter = table->FindCounter(str_name);
+
+  // Now we can find the location in the table.
+  return table->GetLocation(counter, slot);
+}