Mailing-List: contact cvs-help@httpd.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@httpd.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r1591622 [27/33] - in /httpd/mod_spdy/trunk: ./ base/
 base/base.xcodeproj/ base/metrics/ build/ build/all.xcodeproj/
 build/build_util.xcodeproj/ build/install.xcodeproj/ build/internal/
 build/linux/ build/mac/ build/util/ build/win/ install...
Date: Thu, 01 May 2014 11:43:45 -0000
To: cvs@httpd.apache.org
From: jim@apache.org
Message-Id: <20140501114405.448152388C7C@eris.apache.org>

Added: httpd/mod_spdy/trunk/net/instaweb/util/shared_circular_buffer.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/shared_circular_buffer.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/shared_circular_buffer.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/shared_circular_buffer.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,125 @@
+/*
+ * Copyright 2011 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Author: fangfei@google.com (Fangfei Zhou)
+
+#include "net/instaweb/util/public/shared_circular_buffer.h"
+
+#include <cstddef>
+#include "base/scoped_ptr.h"
+#include "net/instaweb/util/public/abstract_mutex.h"
+#include "net/instaweb/util/public/abstract_shared_mem.h"
+#include "net/instaweb/util/public/circular_buffer.h"
+#include "net/instaweb/util/public/message_handler.h"
+#include "net/instaweb/util/public/string.h"
+#include "net/instaweb/util/public/string_util.h"
+#include "net/instaweb/util/public/writer.h"
+
+namespace {
+  const char kSharedCircularBufferObjName[] = "SharedCircularBuffer";
+}    // namespace
+
+namespace net_instaweb {
+
+SharedCircularBuffer::SharedCircularBuffer(AbstractSharedMem* shm_runtime,
+                                           const int buffer_capacity,
+                                           const GoogleString& filename_prefix,
+                                           const GoogleString& filename_suffix)
+    : shm_runtime_(shm_runtime),
+      buffer_capacity_(buffer_capacity),
+      filename_prefix_(filename_prefix),
+      filename_suffix_(filename_suffix) {
+}
+
+SharedCircularBuffer::~SharedCircularBuffer() {
+}
+
+// Initialize shared mutex.
+bool SharedCircularBuffer::InitMutex(MessageHandler* handler) {
+  if (!segment_->InitializeSharedMutex(0, handler)) {
+    handler->Message(
+        kError, "Unable to create mutex for shared memory circular buffer");
+    return false;
+  }
+  return true;
+}
+
+bool SharedCircularBuffer::InitSegment(bool parent,
+                                       MessageHandler* handler) {
+  // Size of segment includes mutex and circular buffer.
+  int buffer_size = CircularBuffer::Sizeof(buffer_capacity_);
+  size_t total = shm_runtime_->SharedMutexSize() + buffer_size;
+  if (parent) {
+    // In root process -> initialize the shared memory.
+    segment_.reset(
+        shm_runtime_->CreateSegment(SegmentName(), total, handler));
+    // Initialize mutex.
+    if (segment_.get() != NULL && !InitMutex(handler)) {
+      segment_.reset(NULL);
+      shm_runtime_->DestroySegment(SegmentName(), handler);
+      return false;
+    }
+  } else {
+    // In child process -> attach to exisiting segment.
+    segment_.reset(
+        shm_runtime_->AttachToSegment(SegmentName(), total, handler));
+    if (segment_.get() == NULL) {
+      return false;
+    }
+  }
+  // Attach Mutex.
+  mutex_.reset(segment_->AttachToSharedMutex(0));
+  // Initialize the circular buffer.
+  int pos = shm_runtime_->SharedMutexSize();
+  buffer_ = CircularBuffer::Init(
+                parent,
+                static_cast<void*>(const_cast<char*>(segment_->Base() + pos)),
+                buffer_size, buffer_capacity_);
+  return true;
+}
+
+void SharedCircularBuffer::Clear() {
+  ScopedMutex hold_lock(mutex_.get());
+  buffer_->Clear();
+}
+
+bool SharedCircularBuffer::Write(const StringPiece& message) {
+  ScopedMutex hold_lock(mutex_.get());
+  return buffer_->Write(message);
+}
+
+bool SharedCircularBuffer::Dump(Writer* writer, MessageHandler* handler) {
+  ScopedMutex hold_lock(mutex_.get());
+  return (writer->Write(buffer_->ToString(handler), handler));
+}
+
+GoogleString SharedCircularBuffer::ToString(MessageHandler* handler) {
+  ScopedMutex hold_lock(mutex_.get());
+  return buffer_->ToString(handler);
+}
+
+void SharedCircularBuffer::GlobalCleanup(MessageHandler* handler) {
+  if (segment_.get() != NULL) {
+    shm_runtime_->DestroySegment(SegmentName(), handler);
+  }
+}
+
+GoogleString SharedCircularBuffer::SegmentName() const {
+  return StrCat(filename_prefix_, kSharedCircularBufferObjName, ".",
+                filename_suffix_);
+}
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/shared_circular_buffer_test_base.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/shared_circular_buffer_test_base.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/shared_circular_buffer_test_base.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/shared_circular_buffer_test_base.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,169 @@
+// Copyright 2011 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Author: fangfei@google.com (Fangfei Zhou)
+
+#include "base/scoped_ptr.h"
+#include "net/instaweb/util/public/function.h"
+#include "net/instaweb/util/public/gtest.h"
+#include "net/instaweb/util/public/mock_message_handler.h"
+#include "net/instaweb/util/public/shared_circular_buffer.h"
+#include "net/instaweb/util/public/shared_circular_buffer_test_base.h"
+#include "net/instaweb/util/public/shared_mem_test_base.h"
+#include "net/instaweb/util/public/string_util.h"
+
+namespace net_instaweb {
+
+namespace {
+const int kBufferSize = 10;
+const char kPrefix[] = "/prefix/";
+const char kPostfix[] = "postfix";
+const char kString[] = "012";
+}  // namespace
+
+SharedCircularBufferTestBase::SharedCircularBufferTestBase(
+    SharedMemTestEnv* test_env)
+    : test_env_(test_env),
+      shmem_runtime_(test_env->CreateSharedMemRuntime()) {
+}
+
+bool SharedCircularBufferTestBase::CreateChild(TestMethod method) {
+  Function* callback =
+      new MemberFunction0<SharedCircularBufferTestBase>(method, this);
+  return test_env_->CreateChild(callback);
+}
+
+SharedCircularBuffer* SharedCircularBufferTestBase::ChildInit() {
+  SharedCircularBuffer* buff =
+      new SharedCircularBuffer(shmem_runtime_.get(), kBufferSize, kPrefix,
+                               kPostfix);
+  buff->InitSegment(false, &handler_);
+  return buff;
+}
+
+SharedCircularBuffer* SharedCircularBufferTestBase::ParentInit() {
+  SharedCircularBuffer* buff =
+      new SharedCircularBuffer(shmem_runtime_.get(), kBufferSize, kPrefix,
+                               kPostfix);
+  buff->InitSegment(true, &handler_);
+  return buff;
+}
+
+// Basic initialization/writing/cleanup test
+void SharedCircularBufferTestBase::TestCreate() {
+  // Create buffer from root Process.
+  scoped_ptr<SharedCircularBuffer> buff(ParentInit());
+  buff->Write("parent");
+  EXPECT_EQ("parent", buff->ToString(&handler_));
+  ASSERT_TRUE(CreateChild(&SharedCircularBufferTestBase::TestCreateChild));
+  test_env_->WaitForChildren();
+  // After the child process writes to buffer,
+  // the content should be updated.
+  EXPECT_EQ("parentkid", buff->ToString(&handler_));
+  buff->GlobalCleanup(&handler_);
+  EXPECT_EQ(0, handler_.SeriousMessages());
+}
+
+void SharedCircularBufferTestBase::TestCreateChild() {
+  scoped_ptr<SharedCircularBuffer> buff(ChildInit());
+  // Child writes to buffer.
+  if (!buff->Write("kid")) {
+    test_env_->ChildFailed();
+  }
+}
+
+void SharedCircularBufferTestBase::TestAdd() {
+  // Every child process writes "012" to buffer.
+  scoped_ptr<SharedCircularBuffer> buff(ParentInit());
+  for (int i = 0; i < 2; ++i) {
+    ASSERT_TRUE(CreateChild(&SharedCircularBufferTestBase::TestAddChild));
+  }
+  test_env_->WaitForChildren();
+  EXPECT_EQ("012012", buff->ToString(&handler_));
+
+  buff->GlobalCleanup(&handler_);
+  EXPECT_EQ(0, handler_.SeriousMessages());
+}
+
+void SharedCircularBufferTestBase::TestAddChild() {
+  scoped_ptr<SharedCircularBuffer> buff(ChildInit());
+  buff->Write("012");
+}
+
+void SharedCircularBufferTestBase::TestClear() {
+  // We can clear things from the child
+  scoped_ptr<SharedCircularBuffer> buff(ParentInit());
+  // Write a string to buffer.
+  buff->Write("012");
+  EXPECT_EQ("012", buff->ToString(&handler_));
+  ASSERT_TRUE(CreateChild(&SharedCircularBufferTestBase::TestClearChild));
+  test_env_->WaitForChildren();
+  // Now the buffer should be empty as the child cleared it.
+  EXPECT_EQ("", buff->ToString(&handler_));
+  buff->GlobalCleanup(&handler_);
+  EXPECT_EQ(0, handler_.SeriousMessages());
+}
+
+void SharedCircularBufferTestBase::TestClearChild() {
+  scoped_ptr<SharedCircularBuffer> buff(ChildInit());
+  buff->InitSegment(false, &handler_);
+  buff->Clear();
+}
+
+void SharedCircularBufferTestBase::TestChildWrite() {
+  scoped_ptr<SharedCircularBuffer> buff(ChildInit());
+  buff->InitSegment(false, &handler_);
+  buff->Write(message_);
+}
+
+void SharedCircularBufferTestBase::TestChildBuff() {
+  scoped_ptr<SharedCircularBuffer> buff(ChildInit());
+  buff->InitSegment(false, &handler_);
+  // Check if buffer content is correct.
+  if (expected_result_ != buff->ToString(&handler_)) {
+    test_env_->ChildFailed();
+  }
+}
+
+// Check various operations, and wraparound, with multiple processes.
+void SharedCircularBufferTestBase::TestCircular() {
+  scoped_ptr<SharedCircularBuffer> parent(ParentInit());
+  parent->Clear();
+  // Write in parent process.
+  parent->Write("012345");
+  EXPECT_EQ("012345", parent->ToString(&handler_));
+  // Write in a child process.
+  message_ = "67";
+  ASSERT_TRUE(CreateChild(
+      &SharedCircularBufferTestBase::TestChildWrite));
+  test_env_->WaitForChildren();
+  EXPECT_EQ("01234567", parent->ToString(&handler_));
+  // Write in parent process.
+  parent->Write("89");
+  // Check buffer content in a child process.
+  // Buffer size is 10. It should be filled exactly so far.
+  expected_result_ = "0123456789";
+  ASSERT_TRUE(CreateChild(
+      &SharedCircularBufferTestBase::TestChildBuff));
+  test_env_->WaitForChildren();
+  // Lose the first char.
+  parent->Write("a");
+  EXPECT_EQ("123456789a", parent->ToString(&handler_));
+  // Write a message with length larger than buffer.
+  parent->Write("bcdefghijkl");
+  EXPECT_EQ("cdefghijkl", parent->ToString(&handler_));
+  parent->GlobalCleanup(&handler_);
+}
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/shared_dynamic_string_map.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/shared_dynamic_string_map.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/shared_dynamic_string_map.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/shared_dynamic_string_map.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,298 @@
+/*
+ * Copyright 2011 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Author: jhoch@google.com (Jason Hoch)
+
+#include "net/instaweb/util/public/shared_dynamic_string_map.h"
+
+#include "base/logging.h"
+#include "net/instaweb/util/public/basictypes.h"
+#include "net/instaweb/util/public/rolling_hash.h"
+#include "net/instaweb/util/public/string_util.h"
+#include "net/instaweb/util/public/writer.h"
+
+namespace net_instaweb {
+
+namespace {
+
+const int kTableFactor = 2;
+const char kSharedDynamicStringMapSegmentName[] = "SharedDynamicStringMap";
+const size_t kPointerSize = sizeof(char*); // NOLINT
+const size_t kOffsetSize = sizeof(size_t); // NOLINT
+const size_t kIntSize = sizeof(int); // NOLINT
+const size_t kEntrySize = sizeof(Entry); // NOLINT
+
+}  // namespace
+
+SharedDynamicStringMap::SharedDynamicStringMap(
+    size_t number_of_strings,
+    size_t average_string_length,
+    AbstractSharedMem* shm_runtime,
+    const GoogleString& filename_prefix,
+    const GoogleString& filename_suffix)
+    : number_of_strings_(NextPowerOfTwo(number_of_strings)),
+      average_string_length_(average_string_length),
+      segment_name_(StrCat(filename_prefix,
+                           kSharedDynamicStringMapSegmentName,
+                           ".",
+                           filename_suffix)),
+      shm_runtime_(shm_runtime) {
+  // Check to make sure number_of_strings_ is a power of 2.
+  DCHECK_EQ(static_cast<size_t>(0),
+            number_of_strings_ & (number_of_strings_ - 1));
+  mutex_size_ = shm_runtime_->SharedMutexSize();
+  table_size_ = number_of_strings_ * kTableFactor;
+  // (See drawing in header file for further explanation)
+  // First we have (table_size_ + 1) mutexes.
+  // Then we have the strings, which are inserted one at a time and are
+  //   of variable size.
+  // Then we have the string_offset of the next string to be inserted.
+  // Then we have the number of strings inserted.
+  // Finally we have the table_size_ entries that contain values and string
+  //   offsets.
+  mutex_offset_ = 0;
+  strings_offset_ = mutex_size_ * (table_size_ + 1);
+  string_offset_offset_ =
+      strings_offset_ + number_of_strings * average_string_length_;
+  number_inserted_offset_ = string_offset_offset_ + kOffsetSize;
+  table_offset_ = number_inserted_offset_ + kIntSize;
+  total_size_ = table_offset_ + table_size_ * kEntrySize;
+}
+
+bool SharedDynamicStringMap::InitSegment(bool parent,
+                                         MessageHandler* message_handler) {
+  // Pointer returned by segment_->Base() is a char*
+  // Table contains a pointer and an int for each entry.
+  bool ok = true;
+  if (parent) {
+    // Initialize shared memory
+    segment_.reset(shm_runtime_->CreateSegment(segment_name_,
+                                               total_size_,
+                                               message_handler));
+    if (segment_.get() == NULL) {
+      ok = false;
+    } else {
+      // Initialize mutexes - there is an extra mutex, the last one, shared
+      // by the string_offset and number_inserted values known as the "insert
+      // string mutex"
+      for (int i = 0; i < static_cast<int>(table_size_) + 1; i++) {
+        if (!segment_->InitializeSharedMutex(i * mutex_size_,
+                                                 message_handler)) {
+          ok = false;
+          break;
+        }
+      }
+    }
+  } else {
+    // In child process -> attach to existing segment
+    segment_.reset(shm_runtime_->AttachToSegment(segment_name_,
+                                                 total_size_,
+                                                 message_handler));
+    if (segment_.get() == NULL) {
+      ok = false;
+    }
+  }
+  if (ok) {
+    insert_string_mutex_.reset(GetMutex(table_size_));
+  } else {
+    ClearSegment(message_handler);
+  }
+  return ok;
+}
+
+void SharedDynamicStringMap::ClearSegment(MessageHandler* message_handler) {
+  segment_.reset(NULL);
+  shm_runtime_->DestroySegment(segment_name_, message_handler);
+}
+
+int SharedDynamicStringMap::IncrementElement(const StringPiece& string) {
+  if (segment_.get() == NULL) {
+    return 0;
+  }
+  Entry* entry_pointer = 0;
+  // We need to lock the entry for incrementation
+  int entry = FindEntry(string, true, &entry_pointer);
+  int value;
+  // If entry is -1 then the table is full.
+  if (entry == -1) {
+    value = 0;
+  } else {
+    // The mutex for the entry is locked by FindEntry for continued use
+    scoped_ptr<AbstractMutex> mutex(GetMutex(entry));
+    if (entry_pointer->value == 0) {
+      // The string is not yet in the table.
+      value = InsertString(string, entry_pointer);
+    } else {
+      // The string is already in the table.
+      value = ++(entry_pointer->value);
+    }
+    mutex->Unlock();
+  }
+  return value;
+}
+
+int SharedDynamicStringMap::LookupElement(const StringPiece& string) const {
+  if (segment_.get() == NULL) {
+    return 0;
+  }
+  Entry* entry_pointer = 0;
+  // We don't need to lock the entry for lookup
+  int entry = FindEntry(string, false, &entry_pointer);
+  // If entry is -1 then the table is full.
+  return (entry == -1) ? 0 : entry_pointer->value;
+}
+
+int SharedDynamicStringMap::FindEntry(const StringPiece& string,
+                                      bool lock,
+                                      Entry** entry_pointer_pointer) const {
+  // lock should always be set to true for writes, and having lock set to false
+  // for a read can occasionally result in a mistake - see header file.
+  uint64 hash = RollingHash(string.data(), 0, string.size());
+  // First 32 bits
+  uint32 hash1 = hash >> 32;
+  // Second 32 bits
+  uint32 hash2 = hash;
+  // For now we assume table_size_ is a power of two, so having hash2 be odd
+  // makes sure that our secondary hashing cycles through all table entries
+  hash2 |= 1;
+  // hash1 dictates starting entry
+  size_t entry = hash1 % table_size_;
+  size_t starting_entry = entry;
+  scoped_ptr<AbstractMutex> mutex;
+  do {
+    // Lock this entry
+    mutex.reset(GetMutex(entry));
+    if (lock) {
+      mutex->Lock();
+    }
+    // Table contains value and then pointer to char
+    *entry_pointer_pointer = GetEntry(entry);
+    char* entry_string_data =
+        GetStringAtOffset((*entry_pointer_pointer)->string_offset);
+    if ((*entry_pointer_pointer)->value == 0) {
+      // If the value is 0 the string is not yet in the table and/or this is the
+      // place to insert it.
+      return entry;
+    } else if (strcmp(entry_string_data, string.data()) == 0) {
+      // We've found the string
+      return entry;
+    } else {
+      // Use secondary hashing to proceed to the next entry
+      entry += hash2;
+      // Same as entry %= table_size_ since table_size_ is a power of 2.
+      entry &= (table_size_ - 1);
+    }
+    if (lock) {
+      mutex->Unlock();
+    }
+  } while (entry != starting_entry);
+  // If the above condition fails, the table is full.
+  return -1;
+}
+
+Entry* SharedDynamicStringMap::GetEntry(size_t n) const {
+  Entry* first_entry = SharedDynamicStringMap::GetFirstEntry();
+  return first_entry + n;
+}
+
+Entry* SharedDynamicStringMap::GetFirstEntry() const {
+  return reinterpret_cast<Entry*>(
+      const_cast<char*>(segment_->Base() + table_offset_));
+}
+
+AbstractMutex* SharedDynamicStringMap::GetMutex(size_t n) const {
+  return segment_->AttachToSharedMutex(mutex_offset_ + n * mutex_size_);
+}
+
+int SharedDynamicStringMap::InsertString(const StringPiece& string,
+                                         Entry* entry_pointer) {
+  // We store the offset of the next string to be inserted at
+  // string_offset_offset_, which has an associated mutex
+  ScopedMutex mutex(insert_string_mutex_.get());
+  size_t* string_offset = reinterpret_cast<size_t*>(
+      const_cast<char*>(segment_->Base() + string_offset_offset_));
+  size_t size = string.size();
+  // If we can't insert the string then we return 0;
+  if (strings_offset_ + *string_offset + size >= table_offset_) {
+    return 0;
+  }
+  char* inserted_string = GetStringAtOffset(*string_offset);
+  memcpy(inserted_string, string.data(), size);
+  // After copying the string we add a terminating null character
+  *(inserted_string + size) = '\0';
+  // Store the offset in the entry
+  entry_pointer->string_offset = *string_offset;
+  // +1 for the terminating null character
+  *string_offset += size + 1;
+  // Increment the number inserted
+  int* number_inserted = reinterpret_cast<int*>(
+      const_cast<char*>(segment_->Base() + number_inserted_offset_));
+  ++(*number_inserted);
+  // Finally, increment the entry value
+  return ++(entry_pointer->value);
+}
+
+char* SharedDynamicStringMap::GetStringAtOffset(size_t offset) const {
+  return const_cast<char*>(segment_->Base() + strings_offset_ + offset);
+}
+
+void SharedDynamicStringMap::GetKeys(StringSet* strings) {
+  int number_inserted = GetNumberInserted();
+  char* string = const_cast<char*>(segment_->Base() + strings_offset_);
+  for (int i = 0; i < number_inserted; i++) {
+    strings->insert(string);
+    int size = strlen(string);
+    string += size + 1;
+  }
+}
+
+int SharedDynamicStringMap::GetNumberInserted() const {
+  return *(reinterpret_cast<int*>(
+      const_cast<char*> (segment_->Base() + number_inserted_offset_)));
+}
+
+void SharedDynamicStringMap::GlobalCleanup(MessageHandler* message_handler) {
+  if (segment_.get() != NULL) {
+    shm_runtime_->DestroySegment(segment_name_, message_handler);
+  }
+}
+
+void SharedDynamicStringMap::Dump(Writer* writer,
+                                  MessageHandler* message_handler) {
+  int number_inserted = GetNumberInserted();
+  char* string = const_cast<char*>(segment_->Base() + strings_offset_);
+  for (int i = 0; i < number_inserted; i++) {
+    int value = LookupElement(string);
+    writer->Write(string, message_handler);
+    writer->Write(": ", message_handler);
+    writer->Write(IntegerToString(value), message_handler);
+    writer->Write("\n", message_handler);
+    int size = strlen(string);
+    string += size + 1;
+  }
+}
+
+size_t SharedDynamicStringMap::NextPowerOfTwo(size_t n) {
+  if (n == 0) {
+    return 1;
+  }
+  n--;
+  for (int shift = 1; shift < static_cast<int>(kOffsetSize); shift *= 2)
+    n |= n >> shift;
+  return n + 1;
+}
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/shared_dynamic_string_map_test_base.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/shared_dynamic_string_map_test_base.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/shared_dynamic_string_map_test_base.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/shared_dynamic_string_map_test_base.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,269 @@
+// Copyright 2011 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Author: jhoch@google.com (Jason Hoch)
+
+#include "net/instaweb/util/public/shared_dynamic_string_map_test_base.h"
+
+#include <cmath>
+#include <cstdlib>
+#include "base/logging.h"
+#include "net/instaweb/util/public/function.h"
+#include "net/instaweb/util/public/shared_dynamic_string_map.h"
+#include "net/instaweb/util/public/string_util.h"
+#include "net/instaweb/util/public/string_writer.h"
+
+namespace net_instaweb {
+
+namespace {
+
+const int kIntSize = sizeof(int); // NOLINT
+// Should be a multiple of 4
+const int kTableSize = 1024;
+// +1 for string that causes overflow
+const int kNumberOfStrings = kTableSize + 1;
+const int kStringSize = 64;
+const char kPrefix[] = "/prefix/";
+const char kSuffix[] = "suffix";
+const char kExampleString1[] = "http://www.example1.com";
+const char kExampleString2[] = "http://www.example2.com";
+
+}  // namespace
+
+SharedDynamicStringMapTestBase::SharedDynamicStringMapTestBase(
+    SharedMemTestEnv* test_env)
+    : test_env_(test_env),
+      shmem_runtime_(test_env->CreateSharedMemRuntime()) {
+  // We must be able to fit a unique int in our string
+  CHECK(2 * kIntSize < kStringSize - 1);
+  // 255 because we can't use null char
+  CHECK(kNumberOfStrings < pow(16, 2 * kIntSize));
+  // After the int at the front we add random chars
+  for (int i = 0; i < kNumberOfStrings; i++) {
+    // We pad the beginning with the hex representation of i, a unique string
+    // or non-null characters
+    GoogleString string = StringPrintf("%0*x", 2 * kIntSize, i);
+    // We fill the rest of the string with random lower-case letters
+    // -1 so there's room for the terminating null character
+    while (string.length() < kStringSize - 1) {
+      string.push_back(random() % 26 + 'a');
+    }
+    strings_.push_back(string);
+  }
+}
+
+bool SharedDynamicStringMapTestBase::CreateChild(TestMethod0 method) {
+  Function* callback =
+      new MemberFunction0<SharedDynamicStringMapTestBase>(method, this);
+  return test_env_->CreateChild(callback);
+}
+
+bool SharedDynamicStringMapTestBase::CreateFillChild(TestMethod2 method,
+                                                     int start,
+                                                     int number_of_strings) {
+  Function* callback =
+      new MemberFunction2<SharedDynamicStringMapTestBase, int, int>(
+          method, this, start, number_of_strings);
+  return test_env_->CreateChild(callback);
+}
+
+SharedDynamicStringMap* SharedDynamicStringMapTestBase::ChildInit() {
+  SharedDynamicStringMap* map =
+      new SharedDynamicStringMap(kTableSize,
+                                 kStringSize,
+                                 shmem_runtime_.get(),
+                                 kPrefix,
+                                 kSuffix);
+  map->InitSegment(false, &handler_);
+  return map;
+}
+
+SharedDynamicStringMap* SharedDynamicStringMapTestBase::ParentInit() {
+  SharedDynamicStringMap* map =
+      new SharedDynamicStringMap(kTableSize,
+                                 kStringSize,
+                                 shmem_runtime_.get(),
+                                 kPrefix,
+                                 kSuffix);
+  map->InitSegment(true, &handler_);
+  return map;
+}
+
+void SharedDynamicStringMapTestBase::TestSimple() {
+  scoped_ptr<SharedDynamicStringMap> map(ParentInit());
+  GoogleString output;
+  StringWriter writer(&output);
+  map->Dump(&writer, &handler_);
+  EXPECT_EQ(output, "");
+  EXPECT_EQ(0, map->GetNumberInserted());
+  map->IncrementElement(kExampleString1);
+  EXPECT_EQ(1, map->LookupElement(kExampleString1));
+  output.clear();
+  map->Dump(&writer, &handler_);
+  EXPECT_EQ(output, "http://www.example1.com: 1\n");
+  EXPECT_EQ(1, map->GetNumberInserted());
+  map->GlobalCleanup(&handler_);
+  EXPECT_EQ(0, handler_.SeriousMessages());
+}
+
+void SharedDynamicStringMapTestBase::TestCreate() {
+  scoped_ptr<SharedDynamicStringMap> map(ParentInit());
+  EXPECT_EQ(0, map->LookupElement(kExampleString1));
+  EXPECT_EQ(0, map->LookupElement(kExampleString2));
+  EXPECT_EQ(0, map->GetNumberInserted());
+  map->IncrementElement(kExampleString1);
+  map->IncrementElement(kExampleString2);
+  EXPECT_EQ(1, map->LookupElement(kExampleString1));
+  EXPECT_EQ(1, map->LookupElement(kExampleString2));
+  EXPECT_EQ(2, map->GetNumberInserted());
+  ASSERT_TRUE(CreateChild(&SharedDynamicStringMapTestBase::AddChild));
+  test_env_->WaitForChildren();
+  EXPECT_EQ(2, map->LookupElement(kExampleString1));
+  EXPECT_EQ(2, map->LookupElement(kExampleString2));
+  EXPECT_EQ(2, map->GetNumberInserted());
+  map->GlobalCleanup(&handler_);
+  EXPECT_EQ(0, handler_.SeriousMessages());
+}
+
+void SharedDynamicStringMapTestBase::AddChild() {
+  scoped_ptr<SharedDynamicStringMap> map(ChildInit());
+  if ((map->IncrementElement(kExampleString1) == 0) ||
+      (map->IncrementElement(kExampleString2) == 0)) {
+    test_env_->ChildFailed();
+  }
+}
+
+void SharedDynamicStringMapTestBase::TestAdd() {
+  scoped_ptr<SharedDynamicStringMap> map(ParentInit());
+  for (int i = 0; i < 2; i++)
+    ASSERT_TRUE(CreateChild(&SharedDynamicStringMapTestBase::AddChild));
+  test_env_->WaitForChildren();
+  EXPECT_EQ(2, map->LookupElement(kExampleString1));
+  EXPECT_EQ(2, map->LookupElement(kExampleString2));
+  EXPECT_EQ(2, map->GetNumberInserted());
+  map->GlobalCleanup(&handler_);
+  EXPECT_EQ(0, handler_.SeriousMessages());
+}
+
+void SharedDynamicStringMapTestBase::TestQuarterFull() {
+  scoped_ptr<SharedDynamicStringMap> map(ParentInit());
+  ASSERT_TRUE(CreateFillChild(&SharedDynamicStringMapTestBase::AddFillChild,
+                              0,
+                              kTableSize / 4));
+  test_env_->WaitForChildren();
+  EXPECT_EQ(kTableSize / 4, map->GetNumberInserted());
+  GoogleString output;
+  StringWriter writer(&output);
+  map->Dump(&writer, &handler_);
+  // Dump outputs the table data in the form
+  // "<string1>: <value1>\n<string2>: <value2>\n<string3>: <value3>\n..."
+  // In this case all values should be 1 so for each of the (kTableSize / 4)
+  // strings there should be kStringSize characters plus a ":", " ", "1", and
+  // "\n" and minus a null character; hence (kTablsize / 4) * (kStringSize + 3)
+  EXPECT_EQ((kTableSize / 4) * (kStringSize + 3), output.length());
+  map->GlobalCleanup(&handler_);
+  EXPECT_EQ(0, handler_.SeriousMessages());
+}
+
+void SharedDynamicStringMapTestBase::TestFillSingleThread() {
+  scoped_ptr<SharedDynamicStringMap> map(ParentInit());
+  EXPECT_EQ(0, map->GetNumberInserted());
+  // One child fills the entire table.
+  ASSERT_TRUE(CreateFillChild(&SharedDynamicStringMapTestBase::AddFillChild,
+                              0,
+                              kTableSize));
+  test_env_->WaitForChildren();
+  // Each entry should have been incremented once.
+  for (int i = 0; i < kTableSize; i++)
+    EXPECT_EQ(1, map->LookupElement(strings_[i]));
+  EXPECT_EQ(kTableSize, map->GetNumberInserted());
+  // One child increments the entire table.
+  ASSERT_TRUE(CreateFillChild(&SharedDynamicStringMapTestBase::AddFillChild,
+                              0,
+                              kTableSize));
+  test_env_->WaitForChildren();
+  // Each entry should have been incremented twice.
+  for (int i = 0; i < kTableSize; i++)
+    EXPECT_EQ(2, map->LookupElement(strings_[i]));
+  EXPECT_EQ(kTableSize, map->GetNumberInserted());
+  // Once the table is full it should not accept additional strings.
+  ASSERT_TRUE(CreateChild(&SharedDynamicStringMapTestBase::AddToFullTable));
+  test_env_->WaitForChildren();
+  EXPECT_EQ(kTableSize, map->GetNumberInserted());
+  map->GlobalCleanup(&handler_);
+  EXPECT_EQ(0, handler_.SeriousMessages());
+}
+
+void SharedDynamicStringMapTestBase::TestFillMultipleNonOverlappingThreads() {
+  scoped_ptr<SharedDynamicStringMap> map(ParentInit());
+  CHECK_EQ(kTableSize % 4, 0);
+  // Each child will fill up 1/4 of the table.
+  for (int i = 0; i < 4; i++)
+    ASSERT_TRUE(CreateFillChild(&SharedDynamicStringMapTestBase::AddFillChild,
+                                i * kTableSize / 4,
+                                kTableSize / 4));
+  test_env_->WaitForChildren();
+  for (int i = 0; i < kTableSize; i++)
+    EXPECT_EQ(1, map->LookupElement(strings_[i]));
+  EXPECT_EQ(kTableSize, map->GetNumberInserted());
+  // Once the table is full it should not accept additional strings.
+  ASSERT_TRUE(CreateChild(&SharedDynamicStringMapTestBase::AddToFullTable));
+  EXPECT_EQ(kTableSize, map->GetNumberInserted());
+  test_env_->WaitForChildren();
+  map->GlobalCleanup(&handler_);
+  EXPECT_EQ(0, handler_.SeriousMessages());
+}
+
+void SharedDynamicStringMapTestBase::TestFillMultipleOverlappingThreads() {
+  scoped_ptr<SharedDynamicStringMap> map(ParentInit());
+  // Ensure that kTableSize is a multiple of 4.
+  CHECK_EQ(kTableSize & 3, 0);
+  // Each child will fill up 1/2 of the table - the table will get covered
+  // twice.
+  for (int i = 0; i < 4; i++)
+    ASSERT_TRUE(CreateFillChild(&SharedDynamicStringMapTestBase::AddFillChild,
+                                i * kTableSize / 4,
+                                kTableSize / 2));
+  // In addition, the parent is going to fill up the entire table.
+  for (int i = 0; i < kTableSize; i++)
+    ASSERT_NE(0, map->IncrementElement(strings_[i]));
+  test_env_->WaitForChildren();
+  EXPECT_EQ(kTableSize, map->GetNumberInserted());
+  // Hence, we check that the values are equal to 3.
+  for (int i = 0; i < kTableSize; i++)
+    EXPECT_EQ(3, map->LookupElement(strings_[i]));
+  // Once the table is full it should not accept additional strings.
+  ASSERT_TRUE(CreateChild(&SharedDynamicStringMapTestBase::AddToFullTable));
+  test_env_->WaitForChildren();
+  EXPECT_EQ(kTableSize, map->GetNumberInserted());
+  map->GlobalCleanup(&handler_);
+  EXPECT_EQ(0, handler_.SeriousMessages());
+}
+
+void SharedDynamicStringMapTestBase::AddFillChild(int start,
+                                                  int number_of_strings) {
+  scoped_ptr<SharedDynamicStringMap> map(ChildInit());
+  for (int i = 0; i < number_of_strings; i++) {
+    if (0 == map->IncrementElement(strings_[(i + start) % kTableSize]))
+      test_env_->ChildFailed();
+  }
+}
+
+void SharedDynamicStringMapTestBase::AddToFullTable() {
+  scoped_ptr<SharedDynamicStringMap> map(ChildInit());
+  const char* string = strings_[kTableSize].c_str();
+  EXPECT_EQ(0, map->IncrementElement(string));
+}
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_lock_manager.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_lock_manager.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_lock_manager.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_lock_manager.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,333 @@
+/*
+ * Copyright 2011 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Author: morlovich@google.com (Maksim Orlovich)
+#include "net/instaweb/util/public/shared_mem_lock_manager.h"
+
+#include <cstddef>
+#include "base/logging.h"
+#include "base/scoped_ptr.h"
+#include "net/instaweb/util/public/abstract_mutex.h"
+#include "net/instaweb/util/public/abstract_shared_mem.h"
+#include "net/instaweb/util/public/basictypes.h"
+#include "net/instaweb/util/public/hasher.h"
+#include "net/instaweb/util/public/message_handler.h"
+#include "net/instaweb/util/public/string.h"
+#include "net/instaweb/util/public/string_util.h"
+#include "net/instaweb/util/public/scheduler.h"
+#include "net/instaweb/util/public/scheduler_based_abstract_lock.h"
+#include "net/instaweb/util/public/timer.h"
+
+namespace net_instaweb {
+
+namespace SharedMemLockData {
+
+// Memory structure:
+//
+// Bucket 0:
+//  Slot 0
+//     lock name hash (64-bit)
+//     acquire timestamp (64-bit)
+//  Slot 1
+//  ...
+//  Slot 15
+//  Mutex
+//  (pad to 64-byte alignment)
+// Bucket 1:
+//  ..
+// Bucket 63:
+//  ..
+//
+// Each key is statically assigned to a bucket based on its hash.
+// When we're trying to lock or unlock the given named lock, we lock
+// the corresponding bucket.
+//
+// Whenever a lock is held, some slot in the corresponding bucket has its hash
+// and the time of acquisition. When a slot is free (or unlocked), its timestamp
+// is set to kNotAcquired.
+//
+// Very old locks can be stolen by new clients, in which case the timestamp gets
+// updated. This serves multiple purposes:
+// 1) It means only one extra process will grab it for each timeout period,
+// as all others will see the new timestamp.
+// 2) It makes it possible for the last grabber to be the one to unlock the
+// lock, as we check the grabber's acquisition timestamp versus the lock's.
+//
+// A further issue is what happens when a bucket is overflowed. In that case,
+// however, we simply state that lock acquisition failed. This is because the
+// purpose of this service is to limit the load on the system, and the table
+// getting filled suggests it's under heavy load as it is, in which case
+// blocking further operations is desirable.
+//
+const size_t kBuckets = 64;   // assumed to be <= 256
+const size_t kSlotsPerBucket = 32;
+
+struct Slot {
+  uint64 hash;
+  int64 acquired_at_ms;  // kNotAcquired if free.
+};
+
+const int64 kNotAcquired = 0;
+
+struct Bucket {
+  Slot slots[kSlotsPerBucket];
+  char mutex_base[1];
+};
+
+inline size_t Align64(size_t in) {
+  return (in + 63) & ~63;
+}
+
+inline size_t BucketSize(size_t lock_size) {
+  return Align64(offsetof(Bucket, mutex_base) + lock_size);
+}
+
+inline size_t SegmentSize(size_t lock_size) {
+  return kBuckets * BucketSize(lock_size);
+}
+
+}  // namespace SharedMemLockData
+
+namespace Data = SharedMemLockData;
+
+class SharedMemLock : public SchedulerBasedAbstractLock {
+ public:
+  virtual ~SharedMemLock() {
+    Unlock();
+  }
+
+  virtual bool TryLock() {
+    return TryLockImpl(false, 0);
+  }
+
+  virtual bool TryLockStealOld(int64 timeout_ms) {
+    return TryLockImpl(true, timeout_ms);
+  }
+
+  virtual void Unlock() {
+    if (acquisition_time_ == Data::kNotAcquired) {
+      return;
+    }
+
+    // Protect the bucket.
+    scoped_ptr<AbstractMutex> lock(AttachMutex());
+    ScopedMutex hold_lock(lock.get());
+
+    // Search for this lock.
+    // note: we permit empty slots in the middle, and start search at different
+    // positions depending on the hash to increase chance of quick hit.
+    // TODO(morlovich): Consider remembering which bucket we locked to avoid
+    // the search. (Could potentially be made lock-free, too).
+    size_t base = hash_ % Data::kSlotsPerBucket;
+    for (size_t offset = 0; offset < Data::kSlotsPerBucket; ++offset) {
+      size_t s = (base + offset) % Data::kSlotsPerBucket;
+      Data::Slot& slot = bucket_->slots[s];
+      if (slot.hash == hash_ && slot.acquired_at_ms == acquisition_time_) {
+        slot.acquired_at_ms = Data::kNotAcquired;
+        break;
+      }
+    }
+
+    acquisition_time_ = Data::kNotAcquired;
+  }
+
+  virtual GoogleString name() {
+    return name_;
+  }
+
+  virtual bool Held() {
+    return (acquisition_time_ != Data::kNotAcquired);
+  }
+
+ protected:
+  virtual Scheduler* scheduler() const {
+    return manager_->scheduler_;
+  }
+
+ private:
+  friend class SharedMemLockManager;
+
+  // ctor should only be called by CreateNamedLock below.
+  SharedMemLock(SharedMemLockManager* manager, const StringPiece& name)
+      : manager_(manager),
+        name_(name.data(), name.size()),
+        acquisition_time_(Data::kNotAcquired) {
+    size_t bucket_num;
+    GetHashAndBucket(name_, &hash_, &bucket_num);
+    bucket_ = manager_->Bucket(bucket_num);
+  }
+
+  // Compute hash and bucket used to store the lock for a given lock name.
+  void GetHashAndBucket(const StringPiece& name, uint64* hash_out,
+                        size_t* bucket_out) {
+    GoogleString raw_hash = manager_->hasher_->RawHash(name);
+
+    // We use separate hash bits to determine the hash and the bucket.
+    *bucket_out = static_cast<unsigned char>(raw_hash[8]) % Data::kBuckets;
+
+    uint64 hash = 0;
+    for (int c = 0; c < 8; ++c) {
+      hash = (hash << 8) | static_cast<unsigned char>(raw_hash[c]);
+    }
+    *hash_out = hash;
+  }
+
+  AbstractMutex* AttachMutex() const {
+    return manager_->seg_->AttachToSharedMutex(
+        manager_->MutexOffset(bucket_));
+  }
+
+  bool TryLockImpl(bool steal, int64 steal_timeout_ms) {
+    // Protect the bucket.
+    scoped_ptr<AbstractMutex> lock(AttachMutex());
+    ScopedMutex hold_lock(lock.get());
+
+    int64 now_ms = manager_->scheduler_->timer()->NowMs();
+    if (now_ms == Data::kNotAcquired) {
+      ++now_ms;
+    }
+
+    // Search for existing lock or empty slot. We need to check everything
+    // for existing lock, of course.
+    size_t empty_slot = Data::kSlotsPerBucket;
+    size_t base = hash_ % Data::kSlotsPerBucket;
+    for (size_t offset = 0; offset < Data::kSlotsPerBucket; ++offset) {
+      size_t s = (base + offset) % Data::kSlotsPerBucket;
+      Data::Slot& slot = bucket_->slots[s];
+      if (slot.hash == hash_) {
+        if (slot.acquired_at_ms == Data::kNotAcquired ||
+            (steal && ((now_ms - slot.acquired_at_ms) >= steal_timeout_ms))) {
+          // Stealing lock, or re-using a free slot we ourselves unlocked.
+          //
+          // We know we don't have an actual locked entry with our key elsewhere
+          // because:
+          // 1) After our last unlock of it no one else has ever locked it (or
+          // our key would have been overwritten), so if we ever performed an
+          // another lock operation we would have done it with this slot in
+          // present state.
+          //
+          // 2) We always chose the first candidate.
+          DoLockSlot(s, now_ms);
+          return true;
+        } else {
+          // Not permitted to steal or not stale enough to steal.
+          return false;
+        }
+      } else if (slot.acquired_at_ms == Data::kNotAcquired) {
+        if (empty_slot == Data::kSlotsPerBucket) {
+          empty_slot = s;
+        }
+      }
+    }
+
+    if (empty_slot != Data::kSlotsPerBucket) {
+      DoLockSlot(empty_slot, now_ms);
+      return true;
+    }
+
+    manager_->handler_->Message(kInfo,
+                                "Overflowed bucket trying to grab lock.");
+    return false;
+  }
+
+  // Writes out our ID and current timestamp into the slot, and marks the
+  // fact of our acquisition.
+  void DoLockSlot(size_t s, int64 now_ms) {
+    Data::Slot& slot = bucket_->slots[s];
+    slot.hash = hash_;
+    slot.acquired_at_ms = now_ms;
+    acquisition_time_ = now_ms;
+  }
+
+  SharedMemLockManager* manager_;
+  GoogleString name_;
+
+  uint64 hash_;
+
+  // Time at which we acquired the lock...
+  int64 acquisition_time_;
+
+  // base pointer for the bucket we are in.
+  Data::Bucket* bucket_;
+
+  DISALLOW_COPY_AND_ASSIGN(SharedMemLock);
+};
+
+SharedMemLockManager::SharedMemLockManager(
+    AbstractSharedMem* shm, const GoogleString& path, Scheduler* scheduler,
+    Hasher* hasher, MessageHandler* handler)
+    : shm_runtime_(shm),
+      path_(path),
+      scheduler_(scheduler),
+      hasher_(hasher),
+      handler_(handler),
+      lock_size_(shm->SharedMutexSize()) {
+  CHECK_GE(hasher_->RawHashSizeInBytes(), 9) << "Need >= 9 byte hashes";
+}
+
+SharedMemLockManager::~SharedMemLockManager() {
+}
+
+bool SharedMemLockManager::Initialize() {
+  seg_.reset(shm_runtime_->CreateSegment(path_, Data::SegmentSize(lock_size_),
+                                         handler_));
+  if (seg_.get() == NULL) {
+    handler_->Message(kError, "Unable to create memory segment for locks.");
+    return false;
+  }
+
+  // Create the mutexes for each bucket
+  for (size_t bucket = 0; bucket < Data::kBuckets; ++bucket) {
+    if (!seg_->InitializeSharedMutex(MutexOffset(Bucket(bucket)), handler_)) {
+      handler_->Message(kError, "%s",
+                        StrCat("Unable to create lock service mutex #",
+                               Integer64ToString(bucket)).c_str());
+      return false;
+    }
+  }
+  return true;
+}
+
+bool SharedMemLockManager::Attach() {
+  size_t size = Data::SegmentSize(shm_runtime_->SharedMutexSize());
+  seg_.reset(shm_runtime_->AttachToSegment(path_, size, handler_));
+  if (seg_.get() == NULL) {
+    handler_->Message(kWarning, "Unable to attach to lock service SHM segment");
+    return false;
+  }
+
+  return true;
+}
+
+void SharedMemLockManager::GlobalCleanup(
+  AbstractSharedMem* shm, const GoogleString& path, MessageHandler* handler) {
+  shm->DestroySegment(path, handler);
+}
+
+NamedLock* SharedMemLockManager::CreateNamedLock(const StringPiece& name) {
+  return new SharedMemLock(this, name);
+}
+
+Data::Bucket* SharedMemLockManager::Bucket(size_t bucket) {
+  return reinterpret_cast<Data::Bucket*>(
+      const_cast<char*>(seg_->Base()) + bucket * Data::BucketSize(lock_size_));
+}
+
+size_t SharedMemLockManager::MutexOffset(SharedMemLockData::Bucket* bucket) {
+  return &bucket->mutex_base[0] - seg_->Base();
+}
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_lock_manager_test_base.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_lock_manager_test_base.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_lock_manager_test_base.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_lock_manager_test_base.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,187 @@
+// Copyright 2011 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Author: morlovich@google.com (Maksim Orlovich)
+
+#include "net/instaweb/util/public/shared_mem_lock_manager_test_base.h"
+
+#include "base/scoped_ptr.h"
+#include "net/instaweb/util/public/function.h"
+#include "net/instaweb/util/public/gtest.h"
+#include "net/instaweb/util/public/md5_hasher.h"
+#include "net/instaweb/util/public/mock_message_handler.h"
+#include "net/instaweb/util/public/mock_timer.h"
+#include "net/instaweb/util/public/named_lock_manager.h"
+#include "net/instaweb/util/public/shared_mem_lock_manager.h"
+#include "net/instaweb/util/public/shared_mem_test_base.h"
+#include "net/instaweb/util/public/thread_system.h"
+
+namespace net_instaweb {
+
+namespace {
+
+const char kPath[] = "shm_locks";
+const char kLockA[] = "lock_a";
+const char kLockB[] = "lock_b";
+
+}  // namespace
+
+SharedMemLockManagerTestBase::SharedMemLockManagerTestBase(
+    SharedMemTestEnv* test_env)
+    : test_env_(test_env),
+      shmem_runtime_(test_env->CreateSharedMemRuntime()),
+      timer_(0),
+      thread_system_(ThreadSystem::CreateThreadSystem()),
+      scheduler_(thread_system_.get(), &timer_) {
+}
+
+void SharedMemLockManagerTestBase::SetUp() {
+  root_lock_manager_.reset(CreateLockManager());
+  EXPECT_TRUE(root_lock_manager_->Initialize());
+}
+
+void SharedMemLockManagerTestBase::TearDown() {
+  SharedMemLockManager::GlobalCleanup(shmem_runtime_.get(), kPath, &handler_);
+}
+
+bool SharedMemLockManagerTestBase::CreateChild(TestMethod method) {
+  Function* callback =
+      new MemberFunction0<SharedMemLockManagerTestBase>(method, this);
+  return test_env_->CreateChild(callback);
+}
+
+SharedMemLockManager* SharedMemLockManagerTestBase::CreateLockManager() {
+  return new SharedMemLockManager(shmem_runtime_.get(), kPath, &scheduler_,
+                                  &hasher_, &handler_);
+}
+
+SharedMemLockManager* SharedMemLockManagerTestBase::AttachDefault() {
+  SharedMemLockManager* lock_man = CreateLockManager();
+  if (!lock_man->Attach()) {
+    delete lock_man;
+    lock_man = NULL;
+  }
+  return lock_man;
+}
+
+void SharedMemLockManagerTestBase::TestBasic() {
+  scoped_ptr<SharedMemLockManager> lock_manager_(AttachDefault());
+  ASSERT_TRUE(lock_manager_.get() != NULL);
+  scoped_ptr<NamedLock> lock_a(lock_manager_->CreateNamedLock(kLockA));
+  scoped_ptr<NamedLock> lock_b(lock_manager_->CreateNamedLock(kLockB));
+
+  ASSERT_TRUE(lock_a.get() != NULL);
+  ASSERT_TRUE(lock_b.get() != NULL);
+
+  EXPECT_FALSE(lock_a->Held());
+  EXPECT_FALSE(lock_b->Held());
+
+  // Can lock exactly once...
+  EXPECT_TRUE(lock_a->TryLock());
+  EXPECT_TRUE(lock_b->TryLock());
+  EXPECT_TRUE(lock_a->Held());
+  EXPECT_TRUE(lock_b->Held());
+  EXPECT_FALSE(lock_a->TryLock());
+  EXPECT_FALSE(lock_b->TryLock());
+  EXPECT_TRUE(lock_a->Held());
+  EXPECT_TRUE(lock_b->Held());
+
+  // Unlocking lets one lock again
+  lock_b->Unlock();
+  EXPECT_FALSE(lock_b->Held());
+  EXPECT_FALSE(lock_a->TryLock());
+  EXPECT_TRUE(lock_b->TryLock());
+
+  // Now unlock A, and let kid confirm the state
+  lock_a->Unlock();
+  EXPECT_FALSE(lock_a->Held());
+  CreateChild(&SharedMemLockManagerTestBase::TestBasicChild);
+  test_env_->WaitForChildren();
+
+  // A should still be unlocked since child's locks should get cleaned up
+  // by ~NamedLock.. but not lock b, which we were holding
+  EXPECT_TRUE(lock_a->TryLock());
+  EXPECT_FALSE(lock_b->TryLock());
+}
+
+void SharedMemLockManagerTestBase::TestBasicChild() {
+  scoped_ptr<SharedMemLockManager> lock_manager_(AttachDefault());
+  scoped_ptr<NamedLock> lock_a(lock_manager_->CreateNamedLock(kLockA));
+  scoped_ptr<NamedLock> lock_b(lock_manager_->CreateNamedLock(kLockB));
+
+  if (lock_a.get() == NULL || lock_b.get() == NULL) {
+    test_env_->ChildFailed();
+  }
+
+  // A should lock fine
+  if (!lock_a->TryLock() || !lock_a->Held()) {
+    test_env_->ChildFailed();
+  }
+
+  // B shouldn't lock fine.
+  if (lock_b->TryLock() || lock_b->Held()) {
+    test_env_->ChildFailed();
+  }
+
+  // Note: here we should unlock a due to destruction of A.
+}
+
+void SharedMemLockManagerTestBase::TestDestructorUnlock() {
+  // Standalone test for destructors cleaning up. It is covered by the
+  // above, but this does it single-threaded, without weird things.
+  scoped_ptr<SharedMemLockManager> lock_manager_(AttachDefault());
+  ASSERT_TRUE(lock_manager_.get() != NULL);
+
+  {
+    scoped_ptr<NamedLock> lock_a(lock_manager_->CreateNamedLock(kLockA));
+    EXPECT_TRUE(lock_a->TryLock());
+  }
+
+  {
+    scoped_ptr<NamedLock> lock_a(lock_manager_->CreateNamedLock(kLockA));
+    EXPECT_TRUE(lock_a->TryLock());
+  }
+}
+
+void SharedMemLockManagerTestBase::TestSteal() {
+  scoped_ptr<SharedMemLockManager> lock_manager_(AttachDefault());
+  ASSERT_TRUE(lock_manager_.get() != NULL);
+  scoped_ptr<NamedLock> lock_a(lock_manager_->CreateNamedLock(kLockA));
+  EXPECT_TRUE(lock_a->TryLock());
+  EXPECT_TRUE(lock_a->Held());
+  CreateChild(&SharedMemLockManagerTestBase::TestStealChild);
+  test_env_->WaitForChildren();
+}
+
+void SharedMemLockManagerTestBase::TestStealChild() {
+  const int kStealTimeMs = 1000;
+
+  scoped_ptr<SharedMemLockManager> lock_manager_(AttachDefault());
+  ASSERT_TRUE(lock_manager_.get() != NULL);
+  scoped_ptr<NamedLock> lock_a(lock_manager_->CreateNamedLock(kLockA));
+
+  // First, attempting to steal should fail, as 'time' hasn't moved yet.
+  if (lock_a->TryLockStealOld(kStealTimeMs) || lock_a->Held()) {
+    test_env_->ChildFailed();
+  }
+
+  timer_.AdvanceMs(kStealTimeMs + 1);
+
+  // Now it should succeed.
+  if (!lock_a->TryLockStealOld(kStealTimeMs) || !lock_a->Held()) {
+    test_env_->ChildFailed();
+  }
+}
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_referer_statistics.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_referer_statistics.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_referer_statistics.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_referer_statistics.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,307 @@
+/*
+ * Copyright 2011 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Author: jhoch@google.com (Jason Hoch)
+
+#include "net/instaweb/util/public/shared_mem_referer_statistics.h"
+
+#include <map>
+#include <set>
+#include "net/instaweb/util/public/google_url.h"
+#include "net/instaweb/util/public/query_params.h"
+#include "net/instaweb/util/public/shared_dynamic_string_map.h"
+#include "net/instaweb/util/public/writer.h"
+
+namespace net_instaweb {
+
+// We don't want this to conflict with another query parameter name, and length
+// also matters (shorter is better).  I picked this somewhat arbitrarily...
+const char SharedMemRefererStatistics::kParamName[] = "div_location";
+
+namespace {
+
+// The encoding scheme for referrals is the following:
+//   <target> + <separator string> + <type string> + <referer>
+// where separator string is kSeparatorString and type string is either
+// kPageString, kDivLocationString, or kResourceString, depending on the type
+// of the target.
+//   The type string is used to differentiate different types of targets at the
+// time of decoding, while the separator string is used to make the information
+// parseable.  Therefore the separator string has to be distinguishable from a
+// URL (e.g. a space character, since there are no spaces in URLs).
+const char kSeparatorString[] = " ";
+const char kPageString[] = "p";
+const char kDivLocationString[] = "d";
+const char kResourceString[] = "r";
+
+}  // namespace
+
+SharedMemRefererStatistics::SharedMemRefererStatistics(
+    size_t number_of_strings,
+    size_t average_string_length,
+    AbstractSharedMem* shm_runtime,
+    const GoogleString& filename_prefix,
+    const GoogleString& filename_suffix)
+    : shared_dynamic_string_map_(new SharedDynamicStringMap(
+          number_of_strings,
+          average_string_length,
+          shm_runtime,
+          filename_prefix,
+          filename_suffix)) {
+}
+
+SharedMemRefererStatistics::~SharedMemRefererStatistics() {}
+
+bool SharedMemRefererStatistics::InitSegment(bool parent,
+                                             MessageHandler* message_handler) {
+  return shared_dynamic_string_map_->InitSegment(parent, message_handler);
+}
+
+void SharedMemRefererStatistics::LogPageRequestWithoutReferer(
+    const GoogleUrl& target) {
+  // We don't need to use target_string later, but we need a placeholder
+  // variable.  We still use LogPageRequest(target, target_string) so we
+  // don't duplicate code with LogReferedPageRequest
+  GoogleString placeholder;
+  LogPageRequest(target, &placeholder);
+}
+
+void SharedMemRefererStatistics::LogPageRequestWithReferer(
+    const GoogleUrl& target,
+    const GoogleUrl& referer) {
+  GoogleString target_string;
+  LogPageRequest(target, &target_string);
+  GoogleString referer_string = GetUrlEntryStringForUrl(referer);
+  GoogleString reference_entry = GetEntryForReferedPage(target_string,
+                                                        referer_string);
+  shared_dynamic_string_map_->IncrementElement(reference_entry);
+  GoogleString div_location = GetDivLocationEntryStringForUrl(target);
+  if (!div_location.empty()) {
+    GoogleString div_location_entry =
+        GetEntryForReferedDivLocation(div_location, referer_string);
+    shared_dynamic_string_map_->IncrementElement(div_location_entry);
+  }
+}
+
+void SharedMemRefererStatistics::LogResourceRequestWithReferer(
+    const GoogleUrl& target,
+    const GoogleUrl& referer) {
+  GoogleString entry = GetEntryForReferedResource(
+      GetUrlEntryStringForUrl(target),
+      GetUrlEntryStringForUrl(referer));
+  shared_dynamic_string_map_->IncrementElement(entry);
+}
+
+// We want to avoid duplicating code between LogReferedPageRequest and
+// LogVisitedPageRequest, but we also don't want to perform GetEntryStringForUrl
+// twice.
+void SharedMemRefererStatistics::LogPageRequest(
+    const GoogleUrl& target,
+    GoogleString* target_string) {
+  *target_string = GetUrlEntryStringForUrl(target);
+  GoogleString visit_entry = GetEntryForVisitedPage(*target_string);
+  shared_dynamic_string_map_->IncrementElement(visit_entry);
+}
+
+int SharedMemRefererStatistics::GetNumberOfVisitsForUrl(const GoogleUrl& url) {
+  GoogleString entry = GetEntryForVisitedPage(GetUrlEntryStringForUrl(url));
+  return shared_dynamic_string_map_->LookupElement(entry);
+}
+
+int SharedMemRefererStatistics::GetNumberOfReferencesFromUrlToPage(
+    const GoogleUrl& from_url,
+    const GoogleUrl& to_url) {
+  GoogleString entry = GetEntryForReferedPage(
+      GetUrlEntryStringForUrl(to_url),
+      GetUrlEntryStringForUrl(from_url));
+  return shared_dynamic_string_map_->LookupElement(entry);
+}
+
+int SharedMemRefererStatistics::GetNumberOfReferencesFromUrlToDivLocation(
+    const GoogleUrl& from_url,
+    const GoogleString& div_location) {
+  GoogleString entry = GetEntryForReferedDivLocation(
+      GetEntryStringForDivLocation(div_location),
+      GetUrlEntryStringForUrl(from_url));
+  return shared_dynamic_string_map_->LookupElement(entry);
+}
+
+int SharedMemRefererStatistics::GetNumberOfReferencesFromUrlToResource(
+    const GoogleUrl& from_url,
+    const GoogleUrl& resource_url) {
+  GoogleString entry = GetEntryForReferedResource(
+      GetUrlEntryStringForUrl(resource_url),
+      GetUrlEntryStringForUrl(from_url));
+  return shared_dynamic_string_map_->LookupElement(entry);
+}
+
+GoogleString SharedMemRefererStatistics::GetDivLocationFromUrl(
+    const GoogleUrl& url) {
+  QueryParams query_params;
+  query_params.Parse(url.Query());
+  ConstStringStarVector div_locations;
+  if ((query_params.Lookup(kParamName, &div_locations)) &&
+      (!div_locations.empty())) {
+    return *div_locations[0];
+  }
+  return "";
+}
+
+GoogleString SharedMemRefererStatistics::GetEntryStringForUrlString(
+    const StringPiece& url_string) const {
+  // Default implementation does nothing
+  return url_string.as_string();
+}
+
+GoogleString SharedMemRefererStatistics::GetEntryStringForDivLocation(
+    const StringPiece& div_location) const {
+  // Default implementation does nothing
+  return div_location.as_string();
+}
+
+GoogleString SharedMemRefererStatistics::GetUrlEntryStringForUrl(
+    const GoogleUrl& url) const {
+  return GetEntryStringForUrlString(url.AllExceptQuery());
+}
+
+GoogleString SharedMemRefererStatistics::GetDivLocationEntryStringForUrl(
+    const GoogleUrl& url) const {
+  return GetEntryStringForDivLocation(GetDivLocationFromUrl(url));
+}
+
+GoogleString SharedMemRefererStatistics::GetEntryForReferedPage(
+    const StringPiece& target,
+    const StringPiece& referer) {
+  return StrCat(target, kSeparatorString, kPageString, referer);
+}
+
+GoogleString SharedMemRefererStatistics::GetEntryForReferedDivLocation(
+    const StringPiece& target,
+    const StringPiece& referer) {
+  return StrCat(target, kSeparatorString, kDivLocationString, referer);
+}
+
+GoogleString SharedMemRefererStatistics::GetEntryForVisitedPage(
+    const StringPiece& target) {
+  return target.as_string();
+}
+
+GoogleString SharedMemRefererStatistics::GetEntryForReferedResource(
+    const StringPiece& target,
+    const StringPiece& referer) {
+  return StrCat(target, kSeparatorString, kResourceString, referer);
+}
+
+GoogleString SharedMemRefererStatistics::DecodeEntry(
+    const StringPiece& entry,
+    GoogleString* target,
+    GoogleString* referer) const {
+  size_t separator_pos = entry.find(kSeparatorString);
+  if (separator_pos == StringPiece::npos) {
+    *target = entry.as_string();
+    *referer = "";
+    return StrCat(*target, " visits: ");
+  } else {
+    StringPiece basic_target(entry.data(), separator_pos);
+    *referer = StringPiece(entry.data() + separator_pos + 2).as_string();
+    char type_char = *(entry.data() + separator_pos + 1);
+    const char* type_string = "";
+    if (type_char == kPageString[0]) {
+      type_string = "page ";
+    } else if (type_char == kDivLocationString[0]) {
+      type_string = "div location ";
+    } else if (type_char == kResourceString[0]) {
+      type_string = "resource ";
+    }
+    *target = StrCat(type_string, basic_target, " : ");
+    return StrCat(*referer, " refered ", *target);
+  }
+}
+
+GoogleString SharedMemRefererStatistics::DecodeEntry(
+    const StringPiece& entry) const {
+  GoogleString target;
+  GoogleString referer;
+  return DecodeEntry(entry, &target, &referer);
+}
+
+void SharedMemRefererStatistics::GlobalCleanup(
+    MessageHandler* message_handler) {
+  shared_dynamic_string_map_->GlobalCleanup(message_handler);
+}
+
+void SharedMemRefererStatistics::DumpFast(Writer* writer,
+                                          MessageHandler* message_handler) {
+  shared_dynamic_string_map_->Dump(writer, message_handler);
+}
+
+void SharedMemRefererStatistics::DumpSimple(Writer* writer,
+                                            MessageHandler* message_handler) {
+  StringSet strings;
+  shared_dynamic_string_map_->GetKeys(&strings);
+  for (StringSet::iterator i = strings.begin(); i != strings.end(); i++) {
+    GoogleString string = *i;
+    int value = shared_dynamic_string_map_->LookupElement(string);
+    writer->Write(DecodeEntry(string), message_handler);
+    writer->Write(IntegerToString(value), message_handler);
+    writer->Write("\n", message_handler);
+  }
+}
+
+void SharedMemRefererStatistics::DumpOrganized(
+    Writer* writer,
+    MessageHandler* message_handler) {
+  StringSet strings;
+  shared_dynamic_string_map_->GetKeys(&strings);
+  // We first accumulate referers and group referrals by referer
+  StringSet referers;
+  std::map<GoogleString, StringSet> referees_by_referer;
+  StringStringMap visits_by_referer;
+  for (StringSet::iterator i = strings.begin(); i != strings.end(); i++) {
+    GoogleString string = *i;
+    int value = shared_dynamic_string_map_->LookupElement(string);
+    GoogleString target;
+    GoogleString referer;
+    GoogleString output = DecodeEntry(string, &target, &referer);
+    if (referer.empty()) {
+      visits_by_referer[target] = StrCat(output, IntegerToString(value));
+      referers.insert(target);
+    } else {
+      referees_by_referer[referer].insert(
+          StrCat(target, IntegerToString(value)));
+      referers.insert(referer);
+    }
+  }
+  // We now dump the grouped referals in a nice readable format
+  for (StringSet::iterator i = referers.begin(); i != referers.end(); i++) {
+    GoogleString referer = *i;
+    writer->Write(visits_by_referer[referer], message_handler);
+    writer->Write("\n", message_handler);
+    StringSet referees = referees_by_referer[referer];
+    if (referees.size() > 0) {
+      writer->Write(referer, message_handler);
+      writer->Write(" refered:\n", message_handler);
+      for (StringSet::iterator j = referees.begin(); j != referees.end(); j++) {
+        GoogleString referee = *j;
+        writer->Write("  ", message_handler);
+        writer->Write(referee, message_handler);
+        writer->Write("\n", message_handler);
+      }
+    }
+  }
+}
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_referer_statistics_test_base.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_referer_statistics_test_base.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_referer_statistics_test_base.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/shared_mem_referer_statistics_test_base.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,380 @@
+/*
+ * Copyright 2011 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Author: jhoch@google.com (Jason Hoch)
+
+#include "net/instaweb/util/public/shared_mem_referer_statistics_test_base.h"
+
+#include "net/instaweb/util/public/function.h"
+#include "net/instaweb/util/public/google_url.h"
+#include "net/instaweb/util/public/shared_mem_referer_statistics.h"
+#include "net/instaweb/util/public/string_util.h"
+#include "net/instaweb/util/public/string_writer.h"
+
+namespace net_instaweb {
+
+const int SharedMemRefererStatisticsTestBase::kNumberOfStrings = 1024;
+const int SharedMemRefererStatisticsTestBase::kStringSize = 64;
+const char SharedMemRefererStatisticsTestBase::kPrefix[] = "/prefix/";
+const char SharedMemRefererStatisticsTestBase::kSuffix[] = "suffix";
+
+namespace {
+
+// kEmptyUrl is used to convey a break in referrals to LogSequenceOfPageRequests
+const GoogleUrl kEmptyUrl("");
+const GoogleString kBase("http://www.example.com/");
+
+const TestUrl kNews(kBase + GoogleString("news"),
+                    GoogleString(""));
+const TestUrl kUSNews(kBase + GoogleString("news/us"),
+                      GoogleString("1.1.0.1"));
+const TestUrl kUSNewsArticle(kBase + GoogleString("news/us/article"),
+                             GoogleString("1.1.2.0"));
+const TestUrl kUSNewsArticleImage(
+                  kBase + GoogleString("images/news_us_article.jpg"),
+                  GoogleString(""));
+const TestUrl kNewUSNewsArticle(kBase + GoogleString("news/us/article2"),
+                                GoogleString("1.1.2.0"));
+const TestUrl kNewOldUSNewsArticle(kBase + GoogleString("news/us/article"),
+                                   GoogleString("1.1.2.1.0"));
+const TestUrl kAccount(kBase + GoogleString("account"),
+                       GoogleString("0.0.9"));
+const TestUrl kProfile(kBase + GoogleString("account/profile.html"),
+                       GoogleString("1.3.0"),
+                       GoogleString("user=jason"));
+const TestUrl kOtherProfile(kBase + GoogleString("account/profile.html"),
+                            GoogleString("1.3.0"),
+                            GoogleString("user=jhoch"));
+
+}  // namespace
+
+GoogleString TestUrl::FormUrl(GoogleString input_string,
+                              GoogleString input_div_location,
+                              GoogleString query_params) {
+  if (input_div_location.empty()) {
+    if (query_params.empty()) {
+      return input_string;
+    } else {
+      return StrCat(input_string, "?", query_params);
+    }
+  } else {
+    if (query_params.empty()) {
+      return StrCat(input_string, "?div_location=", input_div_location);
+    } else {
+      return StrCat(input_string, "?div_location=", input_div_location,
+                    "&", query_params);
+    }
+  }
+}
+
+SharedMemRefererStatisticsTestBase::SharedMemRefererStatisticsTestBase(
+    SharedMemTestEnv* test_env)
+    : test_env_(test_env),
+      shmem_runtime_(test_env->CreateSharedMemRuntime()) {
+}
+
+bool SharedMemRefererStatisticsTestBase::CreateChild(TestMethod method) {
+  Function* callback =
+      new MemberFunction0<SharedMemRefererStatisticsTestBase>(method, this);
+  return test_env_->CreateChild(callback);
+}
+
+SharedMemRefererStatistics* SharedMemRefererStatisticsTestBase::ChildInit() {
+  SharedMemRefererStatistics* stats = new SharedMemRefererStatistics(
+      kNumberOfStrings,
+      kStringSize,
+      shmem_runtime_.get(),
+      kPrefix,
+      kSuffix);
+  stats->InitSegment(false, &message_handler_);
+  return stats;
+}
+
+SharedMemRefererStatistics* SharedMemRefererStatisticsTestBase::ParentInit() {
+  SharedMemRefererStatistics* stats = new SharedMemRefererStatistics(
+      kNumberOfStrings,
+      kStringSize,
+      shmem_runtime_.get(),
+      kPrefix,
+      kSuffix);
+  stats->InitSegment(true, &message_handler_);
+  return stats;
+}
+
+void SharedMemRefererStatisticsTestBase::LogSequenceOfPageRequests(
+    SharedMemRefererStatistics* stats,
+    const GoogleUrl* urls[],
+    int number_of_urls) {
+  bool previous_was_null = true;
+  for (int i = 0; i < number_of_urls; i++) {
+    // kEmptyUrl("") is used to signify break in referrals
+    if (urls[i]->UncheckedSpec().empty()) {
+      previous_was_null = true;
+    } else {
+      if (previous_was_null) {
+        stats->LogPageRequestWithoutReferer(*urls[i]);
+      } else {
+        stats->LogPageRequestWithReferer(*urls[i], *urls[i - 1]);
+      }
+      previous_was_null = false;
+    }
+  }
+}
+
+void SharedMemRefererStatisticsTestBase::TestGetDivLocationFromUrl() {
+  scoped_ptr<SharedMemRefererStatistics> stats(ParentInit());
+  const char value[] = "0.0.0";
+  GoogleString url = GoogleString("http://a.com/?") +
+                     SharedMemRefererStatistics::kParamName +
+                     GoogleString("=") + value;
+  GoogleUrl test_url(url);
+  EXPECT_EQ(value, stats->GetDivLocationFromUrl(test_url));
+  stats->GlobalCleanup(&message_handler_);
+  EXPECT_EQ(0, message_handler_.SeriousMessages());
+}
+
+void SharedMemRefererStatisticsTestBase::TestSimple() {
+  scoped_ptr<SharedMemRefererStatistics> stats(ParentInit());
+  EXPECT_EQ(0, stats->GetNumberOfVisitsForUrl(kNews.url));
+  EXPECT_EQ(0, stats->GetNumberOfVisitsForUrl(kUSNews.url));
+  stats->LogPageRequestWithoutReferer(kNews.url);
+  EXPECT_EQ(1, stats->GetNumberOfVisitsForUrl(kNews.url));
+  EXPECT_EQ(0, stats->GetNumberOfVisitsForUrl(kUSNews.url));
+  stats->LogPageRequestWithReferer(kUSNews.url, kNews.url);
+  EXPECT_EQ(1, stats->GetNumberOfVisitsForUrl(kNews.url));
+  EXPECT_EQ(1, stats->GetNumberOfVisitsForUrl(kUSNews.url));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToPage(kNews.url,
+                                                         kUSNews.url));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kNews.url, kUSNews.div_location));
+  stats->GlobalCleanup(&message_handler_);
+  EXPECT_EQ(0, message_handler_.SeriousMessages());
+}
+
+void SharedMemRefererStatisticsTestBase::TestResource() {
+  scoped_ptr<SharedMemRefererStatistics> stats(ParentInit());
+  const GoogleUrl* urls[] = {&kNews.url, &kUSNews.url, &kUSNewsArticle.url};
+  LogSequenceOfPageRequests(stats.get(), urls, arraysize(urls));
+  stats->LogResourceRequestWithReferer(kUSNewsArticleImage.url,
+                                       kUSNewsArticle.url);
+  EXPECT_EQ(1, stats->GetNumberOfVisitsForUrl(kNews.url));
+  EXPECT_EQ(1, stats->GetNumberOfVisitsForUrl(kUSNews.url));
+  EXPECT_EQ(1, stats->GetNumberOfVisitsForUrl(kUSNewsArticle.url));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToPage(kNews.url,
+                                                         kUSNews.url));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToPage(kUSNews.url,
+                                                         kUSNewsArticle.url));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kNews.url, kUSNews.div_location));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kUSNews.url, kUSNewsArticle.div_location));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToResource(
+      kUSNewsArticle.url, kUSNewsArticleImage.url));
+  EXPECT_EQ(0, stats->GetNumberOfVisitsForUrl(kUSNewsArticleImage.url));
+  EXPECT_EQ(0, stats->GetNumberOfReferencesFromUrlToPage(
+      kUSNewsArticle.url, kUSNewsArticleImage.url));
+  stats->GlobalCleanup(&message_handler_);
+  EXPECT_EQ(0, message_handler_.SeriousMessages());
+}
+
+void SharedMemRefererStatisticsTestBase::TestIgnoreQueryParams() {
+  scoped_ptr<SharedMemRefererStatistics> stats(ParentInit());
+  const GoogleUrl* urls[] = {&kNews.url, &kAccount.url, &kProfile.url};
+  LogSequenceOfPageRequests(stats.get(), urls, arraysize(urls));
+  stats->LogPageRequestWithReferer(kOtherProfile.url, kAccount.url);
+  EXPECT_EQ(1, stats->GetNumberOfVisitsForUrl(kNews.url));
+  EXPECT_EQ(1, stats->GetNumberOfVisitsForUrl(kAccount.url));
+  EXPECT_EQ(2, stats->GetNumberOfVisitsForUrl(kProfile.url));
+  EXPECT_EQ(2, stats->GetNumberOfVisitsForUrl(kOtherProfile.url));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToPage(kNews.url,
+                                                         kAccount.url));
+  EXPECT_EQ(2, stats->GetNumberOfReferencesFromUrlToPage(kAccount.url,
+                                                         kProfile.url));
+  EXPECT_EQ(2, stats->GetNumberOfReferencesFromUrlToPage(kAccount.url,
+                                                         kOtherProfile.url));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kNews.url, kAccount.div_location));
+  EXPECT_EQ(2, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kAccount.url, kProfile.div_location));
+  EXPECT_EQ(2, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kAccount.url, kOtherProfile.div_location));
+  stats->GlobalCleanup(&message_handler_);
+  EXPECT_EQ(0, message_handler_.SeriousMessages());
+}
+
+void SharedMemRefererStatisticsTestBase::TestDivLocation() {
+  scoped_ptr<SharedMemRefererStatistics> stats(ParentInit());
+  const GoogleUrl* urls[] = {&kNews.url, &kUSNews.url, &kUSNewsArticle.url};
+  LogSequenceOfPageRequests(stats.get(), urls, arraysize(urls));
+  stats->LogPageRequestWithReferer(kNewUSNewsArticle.url, kUSNews.url);
+  stats->LogPageRequestWithReferer(kNewOldUSNewsArticle.url, kUSNews.url);
+  EXPECT_EQ(1, stats->GetNumberOfVisitsForUrl(kNews.url));
+  EXPECT_EQ(1, stats->GetNumberOfVisitsForUrl(kUSNews.url));
+  EXPECT_EQ(2, stats->GetNumberOfVisitsForUrl(kUSNewsArticle.url));
+  EXPECT_EQ(1, stats->GetNumberOfVisitsForUrl(kNewUSNewsArticle.url));
+  EXPECT_EQ(2, stats->GetNumberOfVisitsForUrl(kNewOldUSNewsArticle.url));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToPage(kNews.url,
+                                                         kUSNews.url));
+  EXPECT_EQ(2, stats->GetNumberOfReferencesFromUrlToPage(kUSNews.url,
+                                                         kUSNewsArticle.url));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToPage(
+      kUSNews.url, kNewUSNewsArticle.url));
+  EXPECT_EQ(2, stats->GetNumberOfReferencesFromUrlToPage(
+      kUSNews.url, kNewOldUSNewsArticle.url));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kNews.url, kUSNews.div_location));
+  EXPECT_EQ(2, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kUSNews.url, kUSNewsArticle.div_location));
+  EXPECT_EQ(2, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kUSNews.url, kNewUSNewsArticle.div_location));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kUSNews.url, kNewOldUSNewsArticle.div_location));
+  stats->GlobalCleanup(&message_handler_);
+  EXPECT_EQ(0, message_handler_.SeriousMessages());
+}
+
+void SharedMemRefererStatisticsTestBase::TestDumpFast() {
+  scoped_ptr<SharedMemRefererStatistics> stats(ParentInit());
+  const GoogleUrl* urls[] = {&kNews.url, &kUSNews.url, &kUSNewsArticle.url};
+  LogSequenceOfPageRequests(stats.get(), urls, arraysize(urls));
+  stats->LogResourceRequestWithReferer(kUSNewsArticleImage.url,
+                                       kUSNewsArticle.url);
+  GoogleString expected_dump =
+      kNews.string + ": 1\n" +
+      kUSNews.string + ": 1\n" +
+      kUSNews.string + " p" + kNews.string + ": 1\n" +
+      kUSNews.div_location + " d" + kNews.string + ": 1\n" +
+      kUSNewsArticle.string + ": 1\n" +
+      kUSNewsArticle.string + " p" + kUSNews.string + ": 1\n" +
+      kUSNewsArticle.div_location + " d" + kUSNews.string + ": 1\n" +
+      kUSNewsArticleImage.string + " r" + kUSNewsArticle.string + ": 1\n";
+  GoogleString string;
+  StringWriter writer(&string);
+  stats->DumpFast(&writer, &message_handler_);
+  EXPECT_EQ(expected_dump, string);
+  stats->GlobalCleanup(&message_handler_);
+  EXPECT_EQ(0, message_handler_.SeriousMessages());
+}
+
+void SharedMemRefererStatisticsTestBase::TestDumpSimple() {
+  scoped_ptr<SharedMemRefererStatistics> stats(ParentInit());
+  const GoogleUrl* urls[] = {&kNews.url, &kUSNews.url, &kUSNewsArticle.url};
+  LogSequenceOfPageRequests(stats.get(), urls, arraysize(urls));
+  stats->LogResourceRequestWithReferer(kUSNewsArticleImage.url,
+                                       kUSNewsArticle.url);
+  GoogleString expected_dump =
+      kNews.string + " refered div location " +
+          kUSNews.div_location + " : 1\n" +
+      kUSNews.string + " refered div location " +
+          kUSNewsArticle.div_location + " : 1\n" +
+      kUSNewsArticle.string + " refered resource " +
+          kUSNewsArticleImage.string + " : 1\n" +
+      kNews.string + " visits: 1\n" +
+      kUSNews.string + " visits: 1\n" +
+      kNews.string + " refered page " + kUSNews.string + " : 1\n" +
+      kUSNewsArticle.string + " visits: 1\n" +
+      kUSNews.string + " refered page " + kUSNewsArticle.string + " : 1\n";
+  GoogleString string;
+  StringWriter writer(&string);
+  stats->DumpSimple(&writer, &message_handler_);
+  EXPECT_EQ(expected_dump, string);
+  stats->GlobalCleanup(&message_handler_);
+  EXPECT_EQ(0, message_handler_.SeriousMessages());
+}
+
+void SharedMemRefererStatisticsTestBase::TestDumpOrganized() {
+  scoped_ptr<SharedMemRefererStatistics> stats(ParentInit());
+  const GoogleUrl* urls[] = {&kNews.url, &kUSNews.url, &kUSNewsArticle.url};
+  LogSequenceOfPageRequests(stats.get(), urls, arraysize(urls));
+  stats->LogResourceRequestWithReferer(kUSNewsArticleImage.url,
+                                       kUSNewsArticle.url);
+  GoogleString expected_dump =
+      kNews.string + " visits: 1\n" +
+      kNews.string + " refered:\n" +
+      "  div location " + kUSNews.div_location + " : 1\n" +
+      "  page " + kUSNews.string + " : 1\n" +
+      kUSNews.string + " visits: 1\n" +
+      kUSNews.string + " refered:\n" +
+      "  div location " + kUSNewsArticle.div_location + " : 1\n" +
+      "  page " + kUSNewsArticle.string + " : 1\n" +
+      kUSNewsArticle.string + " visits: 1\n" +
+      kUSNewsArticle.string + " refered:\n" +
+      "  resource " + kUSNewsArticleImage.string + " : 1\n";
+  GoogleString string;
+  StringWriter writer(&string);
+  stats->DumpOrganized(&writer, &message_handler_);
+  EXPECT_EQ(expected_dump, string);
+  stats->GlobalCleanup(&message_handler_);
+  EXPECT_EQ(0, message_handler_.SeriousMessages());
+}
+
+void SharedMemRefererStatisticsTestBase::TestMultiProcess() {
+  scoped_ptr<SharedMemRefererStatistics> stats(ParentInit());
+  for (int i = 0; i < 2; i++)
+    ASSERT_TRUE(CreateChild(&SharedMemRefererStatisticsTestBase::AddChild));
+  const GoogleUrl* urls[] = {&kNews.url, &kAccount.url, &kProfile.url,
+                             &kEmptyUrl, &kNews.url, &kUSNews.url,
+                             &kNewOldUSNewsArticle.url};
+  LogSequenceOfPageRequests(stats.get(), urls, arraysize(urls));
+  test_env_->WaitForChildren();
+  EXPECT_EQ(6, stats->GetNumberOfVisitsForUrl(kNews.url));
+  EXPECT_EQ(5, stats->GetNumberOfVisitsForUrl(kUSNews.url));
+  EXPECT_EQ(3, stats->GetNumberOfVisitsForUrl(kUSNewsArticle.url));
+  EXPECT_EQ(2, stats->GetNumberOfVisitsForUrl(kNewUSNewsArticle.url));
+  EXPECT_EQ(3, stats->GetNumberOfVisitsForUrl(kNewOldUSNewsArticle.url));
+  EXPECT_EQ(3, stats->GetNumberOfVisitsForUrl(kAccount.url));
+  EXPECT_EQ(3, stats->GetNumberOfVisitsForUrl(kProfile.url));
+  EXPECT_EQ(5, stats->GetNumberOfReferencesFromUrlToPage(kNews.url,
+                                                         kUSNews.url));
+  EXPECT_EQ(3, stats->GetNumberOfReferencesFromUrlToPage(kUSNews.url,
+                                                         kUSNewsArticle.url));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToPage(kNews.url,
+                                                         kAccount.url));
+  EXPECT_EQ(2, stats->GetNumberOfReferencesFromUrlToPage(kUSNewsArticle.url,
+                                                         kAccount.url));
+  EXPECT_EQ(3, stats->GetNumberOfReferencesFromUrlToPage(kAccount.url,
+                                                         kProfile.url));
+  EXPECT_EQ(2, stats->GetNumberOfReferencesFromUrlToPage(
+      kUSNews.url, kNewUSNewsArticle.url));
+  EXPECT_EQ(3, stats->GetNumberOfReferencesFromUrlToPage(
+      kUSNews.url, kNewOldUSNewsArticle.url));
+  EXPECT_EQ(5, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kNews.url, kUSNews.div_location));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kNews.url, kAccount.div_location));
+  EXPECT_EQ(4, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kUSNews.url, kUSNewsArticle.div_location));
+  EXPECT_EQ(2, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kUSNewsArticle.url, kAccount.div_location));
+  EXPECT_EQ(3, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kAccount.url, kProfile.div_location));
+  EXPECT_EQ(4, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kUSNews.url, kNewUSNewsArticle.div_location));
+  EXPECT_EQ(1, stats->GetNumberOfReferencesFromUrlToDivLocation(
+      kUSNews.url, kNewOldUSNewsArticle.div_location));
+  stats->GlobalCleanup(&message_handler_);
+  EXPECT_EQ(0, message_handler_.SeriousMessages());
+}
+
+void SharedMemRefererStatisticsTestBase::AddChild() {
+  scoped_ptr<SharedMemRefererStatistics> stats(ChildInit());
+  const GoogleUrl* urls[] = {&kNews.url, &kUSNews.url, &kUSNewsArticle.url,
+                             &kAccount.url, &kProfile.url, &kEmptyUrl,
+                             &kNews.url, &kUSNews.url, &kNewUSNewsArticle.url};
+  LogSequenceOfPageRequests(stats.get(), urls, arraysize(urls));
+}
+
+}  // namespace net_instaweb