Return-Path: 
 <cvs-return-50662-apmail-httpd-cvs-archive=httpd.apache.org@httpd.apache.org>
X-Original-To: apmail-httpd-cvs-archive@www.apache.org
Delivered-To: apmail-httpd-cvs-archive@www.apache.org
Received: from mail.apache.org (hermes.apache.org [140.211.11.3])
	by minotaur.apache.org (Postfix) with SMTP id CB6FA1198A
	for <apmail-httpd-cvs-archive@www.apache.org>;
 Thu,  1 May 2014 11:47:05 +0000 (UTC)
Received: (qmail 28397 invoked by uid 500); 1 May 2014 11:46:31 -0000
Delivered-To: apmail-httpd-cvs-archive@httpd.apache.org
Received: (qmail 28041 invoked by uid 500); 1 May 2014 11:46:18 -0000
Mailing-List: contact cvs-help@httpd.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@httpd.apache.org
list-help: <mailto:cvs-help@httpd.apache.org>
list-unsubscribe: <mailto:cvs-unsubscribe@httpd.apache.org>
List-Post: <mailto:cvs@httpd.apache.org>
List-Id: <cvs.httpd.apache.org>
Delivered-To: mailing list cvs@httpd.apache.org
Received: (qmail 27980 invoked by uid 99); 1 May 2014 11:46:13 -0000
Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230)
    by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 01 May 2014 11:46:13 +0000
X-ASF-Spam-Status: No, hits=-2000.0 required=5.0
	tests=ALL_TRUSTED
X-Spam-Check-By: apache.org
Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4)
    by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 01 May 2014 11:45:36 +0000
Received: from eris.apache.org (localhost [127.0.0.1])
	by eris.apache.org (Postfix) with ESMTP id 265192388C6C;
	Thu,  1 May 2014 11:44:05 +0000 (UTC)
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r1591622 [26/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
X-Mailer: svnmailer-1.0.9
Message-Id: <20140501114405.265192388C6C@eris.apache.org>
X-Virus-Checked: Checked by ClamAV on apache.org

Added: httpd/mod_spdy/trunk/net/instaweb/util/queued_worker_pool_test.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/queued_worker_pool_test.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/queued_worker_pool_test.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/queued_worker_pool_test.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,206 @@
+/*
+ * 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: jmarantz@google.com (Joshua Marantz)
+
+// Unit-test for QueuedWorkerPool
+
+#include "net/instaweb/util/public/queued_worker_pool.h"
+
+#include "base/scoped_ptr.h"
+#include "net/instaweb/util/public/basictypes.h"
+#include "net/instaweb/util/public/function.h"
+#include "net/instaweb/util/public/gtest.h"
+#include "net/instaweb/util/worker_test_base.h"
+
+namespace net_instaweb {
+namespace {
+
+class QueuedWorkerPoolTest: public WorkerTestBase {
+ public:
+  QueuedWorkerPoolTest()
+      : worker_(new QueuedWorkerPool(2, thread_runtime_.get())) {}
+
+ protected:
+  scoped_ptr<QueuedWorkerPool> worker_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(QueuedWorkerPoolTest);
+};
+
+// A function that, without protection of a mutex, increments a shared
+// integer.  The intent is that the QueuedWorkerPool::Sequence is
+// enforcing the sequentiality on our behalf so we don't have to worry
+// about mutexing in here.
+class Increment : public Function {
+ public:
+  Increment(int expected_value, int* count)
+      : expected_value_(expected_value),
+        count_(count) {
+  }
+
+ protected:
+  virtual void Run() {
+    ++*count_;
+    EXPECT_EQ(expected_value_, *count_);
+  }
+  virtual void Cancel() {
+    *count_ -= 100;
+    EXPECT_EQ(expected_value_, *count_);
+  }
+
+ private:
+  int expected_value_;
+  int* count_;
+
+  DISALLOW_COPY_AND_ASSIGN(Increment);
+};
+
+// Tests that all the jobs queued in one sequence should run sequentially.
+TEST_F(QueuedWorkerPoolTest, BasicOperation) {
+  const int kBound = 42;
+  int count = 0;
+  SyncPoint sync(thread_runtime_.get());
+
+  QueuedWorkerPool::Sequence* sequence = worker_->NewSequence();
+  for (int i = 0; i < kBound; ++i) {
+    sequence->Add(new Increment(i + 1, &count));
+  }
+
+  sequence->Add(new NotifyRunFunction(&sync));
+  sync.Wait();
+  EXPECT_EQ(kBound, count);
+  worker_->FreeSequence(sequence);
+}
+
+// Test ordinary and cancelled AddFunction callback.
+TEST_F(QueuedWorkerPoolTest, AddFunctionTest) {
+  const int kBound = 5;
+  int count1 = 0;
+  int count2 = 0;
+  SyncPoint sync(thread_runtime_.get());
+
+  QueuedWorkerPool::Sequence* sequence = worker_->NewSequence();
+  for (int i = 0; i < kBound; ++i) {
+    QueuedWorkerPool::Sequence::AddFunction
+        add(sequence, new Increment(i + 1, &count1));
+    add.set_delete_after_callback(false);
+    add.CallRun();
+    QueuedWorkerPool::Sequence::AddFunction
+        cancel(sequence, new Increment(-100 * (i + 1), &count2));
+    cancel.set_delete_after_callback(false);
+    cancel.CallCancel();
+  }
+
+  sequence->Add(new NotifyRunFunction(&sync));
+  sync.Wait();
+  EXPECT_EQ(kBound, count1);
+  EXPECT_EQ(-100 * kBound, count2);
+  worker_->FreeSequence(sequence);
+}
+
+// Makes sure that even if one sequence is blocked, another can
+// complete, because we have more than one thread at our disposal in
+// this worker.
+TEST_F(QueuedWorkerPoolTest, SlowAndFastSequences) {
+  const int kBound = 42;
+  int count = 0;
+  SyncPoint sync(thread_runtime_.get());
+  SyncPoint wait(thread_runtime_.get());
+
+  QueuedWorkerPool::Sequence* slow_sequence = worker_->NewSequence();
+  slow_sequence->Add(new WaitRunFunction(&wait));
+  slow_sequence->Add(new NotifyRunFunction(&sync));
+
+  QueuedWorkerPool::Sequence* fast_sequence = worker_->NewSequence();
+  for (int i = 0; i < kBound; ++i) {
+    fast_sequence->Add(new Increment(i + 1, &count));
+  }
+
+  // At this point the fast sequence is churning through its work, while the
+  // slow sequence is blocked waiting for SyncPoint 'wait'.  Let the fast
+  // sequence unblock it.
+  fast_sequence->Add(new NotifyRunFunction(&wait));
+
+  sync.Wait();
+  EXPECT_EQ(kBound, count);
+  worker_->FreeSequence(fast_sequence);
+  worker_->FreeSequence(slow_sequence);
+}
+
+class MakeNewSequence : public Function {
+ public:
+  MakeNewSequence(WorkerTestBase::SyncPoint* sync,
+                  QueuedWorkerPool* pool,
+                  QueuedWorkerPool::Sequence* sequence)
+      : sync_(sync),
+        pool_(pool),
+        sequence_(sequence) {
+  }
+
+  virtual void Run() {
+    pool_->FreeSequence(sequence_);
+    pool_->NewSequence()->Add(new WorkerTestBase::NotifyRunFunction(sync_));
+  }
+
+ private:
+  WorkerTestBase::SyncPoint* sync_;
+  QueuedWorkerPool* pool_;
+  QueuedWorkerPool::Sequence* sequence_;
+
+  DISALLOW_COPY_AND_ASSIGN(MakeNewSequence);
+};
+
+TEST_F(QueuedWorkerPoolTest, RestartSequenceFromFunction) {
+  SyncPoint sync(thread_runtime_.get());
+  QueuedWorkerPool::Sequence* sequence = worker_->NewSequence();
+  sequence->Add(new MakeNewSequence(&sync, worker_.get(), sequence));
+  sync.Wait();
+}
+
+// Keeps track of whether run or cancel were called.
+class LogOpsFunction : public Function {
+ public:
+  LogOpsFunction() : run_called_(false), cancel_called_(false) {}
+  virtual ~LogOpsFunction() {}
+
+  bool run_called() const { return run_called_; }
+  bool cancel_called() const { return cancel_called_; }
+
+ protected:
+  virtual void Run() { run_called_ = true; }
+  virtual void Cancel() { cancel_called_ = true; }
+
+ private:
+  bool run_called_;
+  bool cancel_called_;
+};
+
+// Make sure calling add after worker was shut down Cancel()s the function
+// properly.
+TEST_F(QueuedWorkerPoolTest, AddAfterShutDown) {
+  QueuedWorkerPool::Sequence* sequence = worker_->NewSequence();
+  worker_->ShutDown();
+  LogOpsFunction f;
+  f.set_delete_after_callback(false);
+  sequence->Add(&f);
+  worker_.reset(NULL);
+  EXPECT_TRUE(f.cancel_called());
+  EXPECT_FALSE(f.run_called());
+}
+
+}  // namespace
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/queued_worker_test.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/queued_worker_test.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/queued_worker_test.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/queued_worker_test.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,121 @@
+/*
+ * 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)
+
+// Unit-test for QueuedWorker
+
+#include "net/instaweb/util/public/queued_worker.h"
+
+#include "base/scoped_ptr.h"
+#include "net/instaweb/util/public/basictypes.h"
+#include "net/instaweb/util/public/function.h"
+#include "net/instaweb/util/public/gtest.h"
+#include "net/instaweb/util/worker_test_base.h"
+
+namespace net_instaweb {
+namespace {
+
+class QueuedWorkerTest: public WorkerTestBase {
+ public:
+  QueuedWorkerTest() : worker_(new QueuedWorker(thread_runtime_.get())) {}
+
+ protected:
+  scoped_ptr<QueuedWorker> worker_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(QueuedWorkerTest);
+};
+
+// A closure that enqueues a new version of itself 'count' times, and
+// finally schedules the running of the sync-point.
+class ChainedTask : public Function {
+ public:
+  ChainedTask(int* count, QueuedWorker* worker, WorkerTestBase::SyncPoint* sync)
+      : count_(count),
+        worker_(worker),
+        sync_(sync) {
+  }
+
+  virtual void Run() {
+    --*count_;
+    if (*count_ > 0) {
+      worker_->RunInWorkThread(new ChainedTask(count_, worker_, sync_));
+    } else {
+      worker_->RunInWorkThread(new WorkerTestBase::NotifyRunFunction(sync_));
+    }
+  }
+
+ private:
+  int* count_;
+  QueuedWorker* worker_;
+  WorkerTestBase::SyncPoint* sync_;
+
+  DISALLOW_COPY_AND_ASSIGN(ChainedTask);
+};
+
+TEST_F(QueuedWorkerTest, BasicOperation) {
+  // All the jobs we queued should be run in order
+  const int kBound = 42;
+  int count = 0;
+  SyncPoint sync(thread_runtime_.get());
+
+  worker_->Start();
+  for (int i = 0; i < kBound; ++i) {
+    worker_->RunInWorkThread(new CountFunction(&count));
+  }
+
+  worker_->RunInWorkThread(new NotifyRunFunction(&sync));
+  sync.Wait();
+  EXPECT_EQ(kBound, count);
+}
+
+TEST_F(QueuedWorkerTest, ChainedTasks) {
+  // The ChainedTask closure ensures that there is always a task
+  // queued until we've executed all 11 tasks in the chain, at which
+  // point the 'notify' function fires and we can complete the test.
+  int count = 11;
+  SyncPoint sync(thread_runtime_.get());
+  worker_->Start();
+  worker_->RunInWorkThread(new ChainedTask(&count, worker_.get(), &sync));
+  sync.Wait();
+  EXPECT_EQ(0, count);
+}
+
+TEST_F(QueuedWorkerTest, TestShutDown) {
+  // Make sure that shutdown cancels jobs put in after it --- that
+  // the job gets deleted (making clean.Wait() return), and doesn't
+  // run (which would LOG(FATAL)).
+  SyncPoint clean(thread_runtime_.get());
+  worker_->Start();
+  worker_->ShutDown();
+  worker_->RunInWorkThread(new DeleteNotifyFunction(&clean));
+  clean.Wait();
+}
+
+TEST_F(QueuedWorkerTest, TestIsBusy) {
+  worker_->Start();
+  EXPECT_FALSE(worker_->IsBusy());
+
+  SyncPoint start_sync(thread_runtime_.get());
+  worker_->RunInWorkThread(new WaitRunFunction(&start_sync));
+  EXPECT_TRUE(worker_->IsBusy());
+  start_sync.Notify();
+  worker_->ShutDown();
+  EXPECT_FALSE(worker_->IsBusy());
+}
+
+}  // namespace
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/ref_counted.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/ref_counted.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/ref_counted.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/ref_counted.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,26 @@
+/*
+ * Copyright 2010 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: jmarantz@google.com (Joshua Marantz)
+
+// This file works around an apparent omission in the Chromium
+// libraries.  The Chromium source tree includes classes for reference
+// counting, but the implementation files are not included in the
+// Chromium library.  The easiest way to ensure they are compiled into
+// Instaweb is to include them in a new .cc file:
+
+#include "base/memory/ref_counted.cc"
+#include "base/threading/thread_collision_warner.cc"

Added: httpd/mod_spdy/trunk/net/instaweb/util/ref_counted_owner_test.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/ref_counted_owner_test.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/ref_counted_owner_test.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/ref_counted_owner_test.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,117 @@
+/*
+ * 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)
+
+// Unit-test RefCountedOwner.
+
+#include "net/instaweb/util/public/ref_counted_owner.h"
+#include "net/instaweb/util/public/basictypes.h"
+#include "net/instaweb/util/public/gtest.h"
+
+namespace net_instaweb {
+
+namespace {
+
+class NoteDeleteClass {
+ public:
+  explicit NoteDeleteClass(bool* mark_destroy) : mark_destroy_(mark_destroy) {}
+  ~NoteDeleteClass() { *mark_destroy_ = true; }
+
+ private:
+  bool* mark_destroy_;
+  DISALLOW_COPY_AND_ASSIGN(NoteDeleteClass);
+};
+
+class RefCountedOwnerTest : public testing::Test {
+ protected:
+  // Note: we pass in a non-const reference here simply because we also want
+  // to cover the non-const versions of the getters.
+  void CheckPointerOps(NoteDeleteClass* instance,
+                       RefCountedOwner<NoteDeleteClass>& owner) {
+    // First we ensure that pointer got fetches
+    EXPECT_TRUE(owner.Attach());
+    EXPECT_EQ(instance, owner.Get());
+    const RefCountedOwner<NoteDeleteClass>& const_owner = owner;
+    EXPECT_EQ(instance, const_owner.Get());
+  }
+};
+
+TEST_F(RefCountedOwnerTest, Simple) {
+  bool destroyed = false;
+  {
+    RefCountedOwner<NoteDeleteClass>::Family f1;
+    RefCountedOwner<NoteDeleteClass> o1(&f1);
+    RefCountedOwner<NoteDeleteClass> o2(&f1);
+    EXPECT_FALSE(o1.Attach());
+    EXPECT_FALSE(o2.Attach());
+    EXPECT_FALSE(o1.Attach());  // didn't initialize yet ->
+                                // nothing changed.
+    EXPECT_FALSE(o2.Attach());
+
+    NoteDeleteClass* instance = new NoteDeleteClass(&destroyed);
+    o1.Initialize(instance);
+    CheckPointerOps(instance, o1);
+    CheckPointerOps(instance, o2);
+
+    {
+      RefCountedOwner<NoteDeleteClass> o3(&f1);
+      CheckPointerOps(instance, o1);
+    }
+
+    EXPECT_FALSE(destroyed);
+  }
+  EXPECT_TRUE(destroyed);
+}
+
+// Test with more than one family.
+TEST_F(RefCountedOwnerTest, MultipleFamilies) {
+  bool destroyed1 = false;
+  bool destroyed2 = false;
+  {
+    RefCountedOwner<NoteDeleteClass>::Family f1;
+    RefCountedOwner<NoteDeleteClass>::Family f2;
+
+    RefCountedOwner<NoteDeleteClass> o1(&f1);
+    RefCountedOwner<NoteDeleteClass> o2(&f1);
+    EXPECT_FALSE(o1.Attach());
+    EXPECT_FALSE(o2.Attach());
+
+    NoteDeleteClass* instance1 = new NoteDeleteClass(&destroyed1);
+    o1.Initialize(instance1);
+    CheckPointerOps(instance1, o1);
+    CheckPointerOps(instance1, o2);
+
+    {
+      RefCountedOwner<NoteDeleteClass> o3(&f2);
+      EXPECT_FALSE(o3.Attach());
+      NoteDeleteClass* instance2 = new NoteDeleteClass(&destroyed2);
+      o3.Initialize(instance2);
+      CheckPointerOps(instance1, o1);
+      CheckPointerOps(instance1, o2);
+      CheckPointerOps(instance2, o3);
+    }
+
+    EXPECT_FALSE(destroyed1);
+    EXPECT_TRUE(destroyed2);
+  }
+  EXPECT_TRUE(destroyed1);
+  EXPECT_TRUE(destroyed2);
+}
+
+}  // namespace
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/ref_counted_ptr_test.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/ref_counted_ptr_test.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/ref_counted_ptr_test.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/ref_counted_ptr_test.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,135 @@
+/*
+ * Copyright 2010 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: jmarantz@google.com (Joshua Marantz)
+
+// Unit-test RefCountedPtr.
+
+#include "net/instaweb/util/public/ref_counted_ptr.h"
+#include "net/instaweb/util/public/basictypes.h"
+#include "net/instaweb/util/public/gtest.h"
+
+namespace net_instaweb {
+
+namespace {
+
+int counter = 0;
+
+class SimpleClass {
+ public:
+  SimpleClass() : index_(counter++) {}
+  int index() const { return index_; }
+
+ private:
+  int index_;
+  DISALLOW_COPY_AND_ASSIGN(SimpleClass);
+};
+
+class BaseClass : public RefCounted<BaseClass> {
+ public:
+  BaseClass() {}
+  int index() const { return simple_.index(); }
+
+ protected:
+  virtual ~BaseClass() {}
+  REFCOUNT_FRIEND_DECLARATION(BaseClass);
+
+ private:
+  SimpleClass simple_;
+  DISALLOW_COPY_AND_ASSIGN(BaseClass);
+};
+
+struct DerivedA : public BaseClass {};
+struct DerivedB : public BaseClass {};
+
+}  // namespace
+
+typedef RefCountedObj<SimpleClass> SimplePtr;
+typedef RefCountedPtr<BaseClass> PolymorphicPtr;
+
+class RefCountedPtrTest : public testing::Test {
+ protected:
+};
+
+TEST_F(RefCountedPtrTest, Simple) {
+  SimplePtr simple1;
+  EXPECT_TRUE(simple1.unique());
+  int index = simple1->index();
+  SimplePtr simple2 = simple1;
+  EXPECT_FALSE(simple1.unique());
+  EXPECT_FALSE(simple2.unique());
+  EXPECT_EQ(index, simple2->index());
+  SimplePtr simple3(simple1);
+  EXPECT_FALSE(simple3.unique());
+  EXPECT_EQ(index, simple3->index());
+  SimplePtr simple4;
+  EXPECT_TRUE(simple4.unique());
+  EXPECT_NE(index, simple4->index());
+}
+
+TEST_F(RefCountedPtrTest, Polymorphic) {
+  PolymorphicPtr poly1(new DerivedA);
+  int index = poly1->index();
+  EXPECT_TRUE(poly1.unique());
+  PolymorphicPtr poly2(poly1);
+  EXPECT_FALSE(poly1.unique());
+  EXPECT_FALSE(poly2.unique());
+  EXPECT_EQ(index, poly2->index());
+  PolymorphicPtr poly3 = poly1;
+  EXPECT_FALSE(poly3.unique());
+  EXPECT_EQ(index, poly3->index());
+  PolymorphicPtr poly4(new DerivedB);
+  EXPECT_TRUE(poly4.unique());
+  EXPECT_NE(index, poly4->index());
+  PolymorphicPtr poly5;
+  EXPECT_TRUE(poly5.get() == NULL);
+  EXPECT_TRUE(poly5.unique());
+  poly5.clear();
+  EXPECT_TRUE(poly5.get() == NULL);
+  poly1.reset(new DerivedA);
+  EXPECT_TRUE(poly1.unique());
+}
+
+TEST_F(RefCountedPtrTest, Upcast) {
+  RefCountedPtr<DerivedA> derived(new DerivedA);
+  PolymorphicPtr base(derived);
+  EXPECT_FALSE(derived.unique());
+  EXPECT_FALSE(base.unique());
+  EXPECT_EQ(base->index(), derived->index());
+}
+
+// It is not possible to use RefCountedUpcast to perform a downcast.
+// To prove that to yourself, uncomment this and compile:
+//
+// TEST_F(RefCountedPtrTest, DownCast) {
+//   PolymorphicPtr base(new DerivedB);
+//   RefCountedPtr<DerivedA> derived(base);
+//   EXPECT_FALSE(derived.unique());
+//   EXPECT_FALSE(base.unique());
+//   EXPECT_EQ(base->index(), derived->index());
+// }
+
+// It is not possible to use RefCountedUpcast to perform a cast between two
+// unrelated pointers.  To prove that to yourself, uncomment this:
+//
+// TEST_F(RefCountedPtrTest, CrossCast) {
+//   RefCountedPtr<DerivedA> derived_a(new DerivedA);
+//   RefCountedPtr<DerivedB> derived_b(derived_a);
+//   EXPECT_FALSE(derived_a.unique());
+//   EXPECT_FALSE(derived_b.unique());
+// }
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/rolling_hash.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/rolling_hash.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/rolling_hash.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/rolling_hash.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,294 @@
+/*
+ * Copyright 2010 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: jmaessen@google.com (Jan Maessen)
+
+#include "net/instaweb/util/public/rolling_hash.h"
+
+#include <cstddef>
+#include "base/logging.h"
+#include "net/instaweb/util/public/basictypes.h"
+
+namespace net_instaweb {
+
+uint64 RollingHash(const char* buf, size_t start, size_t n) {
+  CHECK_LE(static_cast<size_t>(0), start);
+  buf += start;
+  uint64 hash = 0;
+  for (size_t i = 0; i < n; ++i) {
+    hash = (hash << 1) | (hash >> 63);  // Rotate left 1
+    hash ^= kRollingHashCharTable[static_cast<uint8>(buf[i])];
+  }
+  return hash;
+}
+
+const uint64 kRollingHashCharTable[256] = {
+    0xf0dcd27e0762b251ULL,
+    0xb621e668da0b3d53ULL,
+    0xce8c72d316e9293cULL,
+    0xe958017c3359bad5ULL,
+    0x6b11ca3935e9bb14ULL,
+    0x64f67431b8b0bcb4ULL,
+    0x8c4dd71ad988d23eULL,
+    0x24936d1c08aff78dULL,
+    0x69ecc7f3052e0396ULL,
+    0xcdc8f08d999754c5ULL,
+    0x39ab6e32568685cdULL,
+    0x4e4f289b8b96e626ULL,
+    0xa3c3cb4a32546b3dULL,
+    0xe929810fec372e4dULL,
+    0xfd94f0e82a05ac37ULL,
+    0x3b71322f12f04f66ULL,
+    0x8ad767cc6b92f018ULL,
+    0xb4fff19004481ff1ULL,
+    0xc9a1422e55e9d8bbULL,
+    0x016fccc64de16d17ULL,
+    0xd27154733cd80e3eULL,
+    0x3f837bd6c3588413ULL,
+    0x2c493e9f8c70ee0eULL,
+    0xb45526d0cdcae876ULL,
+    0xfa8778e134e91383ULL,
+    0x0e8f821f8c783f69ULL,
+    0xc28fd9493d9268e9ULL,
+    0xf5b90b302376dc19ULL,
+    0x12d5edf71944c0b9ULL,
+    0x3de65234604d9f95ULL,
+    0x6e0b7823a5ab650fULL,
+    0xf30d1b84d74f542cULL,
+    0xd59ea7a1a04daa1eULL,
+    0xc322bb145da0eaeeULL,
+    0x9f55e20e76bc821cULL,
+    0x84eb8f72c858db2cULL,
+    0x0727b30ff9b3080fULL,
+    0x40cb8bf1f3e4114fULL,
+    0x379d10f1f0166fc2ULL,
+    0x8766af09de794470ULL,
+    0x4cebe022f58b47f0ULL,
+    0x75d232d0c4a94ebbULL,
+    0xc63ba1fbd098199cULL,
+    0xa0d947c29f383a9eULL,
+    0x3bfd354a0404e6deULL,
+    0x9d3164f90bd471a3ULL,
+    0x357f031c2b1cee0eULL,
+    0x47bb2d71880becd1ULL,
+    0xc048dc946fd9dd85ULL,
+    0xa21e8226ed9b2db9ULL,
+    0xad06169fbe3a05a9ULL,
+    0x0a7b91d58f44e29bULL,
+    0x36bdd30c057a61baULL,
+    0xcb78135eb2c3b107ULL,
+    0xa65907ee1f4209ddULL,
+    0x0962bb3ccf9816f2ULL,
+    0xceb546dda951601eULL,
+    0x5e5769344a1f8f21ULL,
+    0x1fe188e97a0685eeULL,
+    0x59d0d4289c5edacbULL,
+    0xaa212857bb62f723ULL,
+    0xa527e223de884eceULL,
+    0x9c9a15c9aa56eba4ULL,
+    0x9b16d95901aee267ULL,
+    0xf4c5b630931f11e9ULL,
+    0x3df802e7e85a6750ULL,
+    0x4968f654cce17653ULL,
+    0xfc3bc0ad02761567ULL,
+    0xff18ec7e401c445dULL,
+    0x2f844385f9c31b7aULL,
+    0x88d750f43c6989edULL,
+    0x4bb020be66f231f9ULL,
+    0x12502d671fa7f487ULL,
+    0x1926420bae67fb5aULL,
+    0x2acb699d19d6c4d4ULL,
+    0x5cdb79d0349158eaULL,
+    0x67e93d1bf4815342ULL,
+    0x43dc874f7024e36dULL,
+    0xb92097281fed49b6ULL,
+    0x62ed4f7a0a6958a9ULL,
+    0x574c6b02ae6f3626ULL,
+    0xd49b443e8932f23dULL,
+    0x7dc50d1a701aab7aULL,
+    0x48621174dff0fd92ULL,
+    0x5746557ae580c35eULL,
+    0x4bc7f97a8ebc2480ULL,
+    0x07e620aad2f7b646ULL,
+    0x1285636d57e3f612ULL,
+    0x9f6cd306e5514c5cULL,
+    0x0de00632f6f709d7ULL,
+    0x7aa301698adee68bULL,
+    0x2df10184f4cfd4ecULL,
+    0x5f5b744cf78e8048ULL,
+    0x88ebe0a2615fe4b3ULL,
+    0xcb6f29a29401f98fULL,
+    0x9c306f274e66d287ULL,
+    0x88f632944f2ccdd9ULL,
+    0x63bcf4a925db4311ULL,
+    0xc6d2f5e9c0a50b72ULL,
+    0xd6a731846a17be49ULL,
+    0x2fd613caa70c235eULL,
+    0x534de67031253facULL,
+    0x4c685e47e9592796ULL,
+    0x9b153e27865bd258ULL,
+    0xd614462b61589f7dULL,
+    0x1532cb94e28d8cbfULL,
+    0x91497f579632a631ULL,
+    0x26e3a246cc96fb61ULL,
+    0xb28d962661bf129bULL,
+    0x85da5d60a6ae5aa3ULL,
+    0x0a9a1f6cb7c3e6a0ULL,
+    0xae039586bd8c7f11ULL,
+    0x0bfd1a8454e77964ULL,
+    0xd6fa6b85a423d107ULL,
+    0x015c3ab5134f69fcULL,
+    0xdab1025b8bed7c18ULL,
+    0xdf404b3edca12395ULL,
+    0xad3d2d77444e1887ULL,
+    0x92654b67bda1e990ULL,
+    0xc412fe06d4e29f1eULL,
+    0x2d382f434b99af46ULL,
+    0x8cb666ada86575a1ULL,
+    0x833d4b153f5f5405ULL,
+    0x6007f6c51629e797ULL,
+    0xd8a1f922cba896e3ULL,
+    0x2c9b5a1a249f9e47ULL,
+    0xd899781c79cb063bULL,
+    0x911f5c7513ea3c91ULL,
+    0x0c77ae198ca79978ULL,
+    0x20ba7b1e0c97d74cULL,
+    0xb3711eccdd549521ULL,
+    0x0a94dc19e59543dfULL,
+    0x3b348e9c6b0e36a6ULL,
+    0x9627b15951a7a6b8ULL,
+    0x9193dc839dbe7049ULL,
+    0xba707aa6a2add40eULL,
+    0x1777251ac57b2a2aULL,
+    0xca6c2edba50c4c4fULL,
+    0xa6c43cd31526ff60ULL,
+    0x310d05dff737a640ULL,
+    0xa8663ab4709bdd52ULL,
+    0xd05f9d24885f3b94ULL,
+    0x8c863ea5aafb221dULL,
+    0x21ef263381f8cd63ULL,
+    0x4b6fb4a8bc5458aaULL,
+    0xc1d84b559be971b0ULL,
+    0x210fb1bab7f15072ULL,
+    0xe66ee09a51a55963ULL,
+    0x39c21db635c08debULL,
+    0xf05b979841675d0dULL,
+    0x2978a9f732d96470ULL,
+    0x4dce978a19c3a1f1ULL,
+    0x5c0e92ab7319cd99ULL,
+    0x743b286678d9e686ULL,
+    0xdaf46993e90a5e81ULL,
+    0x96dc2e0adcbb0d16ULL,
+    0xd95690fe868663d8ULL,
+    0x66ef0231433f2b39ULL,
+    0x30774974792d96ccULL,
+    0x44ffb0e25c47c44eULL,
+    0x4cd9b89be5889713ULL,
+    0xe62e5a6014f07cf3ULL,
+    0xb56ac85a8af4dea0ULL,
+    0xde92b05ba2e1b34aULL,
+    0x23fd1311f823b78cULL,
+    0xff80ac0f287ec43cULL,
+    0x5d90a3866dd95fc0ULL,
+    0xdec51083823f593fULL,
+    0x86ad4349ac174faeULL,
+    0xaedff28454b16a41ULL,
+    0x3d8bc08e3f2e0c9dULL,
+    0xf86319f232a3c729ULL,
+    0xcd5e5e0f94263499ULL,
+    0x8d7ba52980b19b79ULL,
+    0xa67e8a3d335c81d2ULL,
+    0x65d09ac6aa0fdab2ULL,
+    0xc1795b7f5b644a20ULL,
+    0xec83e7447c32d0dcULL,
+    0x6f90245af445f4aeULL,
+    0x56d70cadcc4a28fcULL,
+    0xaf264eb82bcc4f90ULL,
+    0xa16010fce3634affULL,
+    0x8ea336b9c2c1e45bULL,
+    0x7680ddb84af244bbULL,
+    0xf97371315d450666ULL,
+    0x8166dfa721896adcULL,
+    0x3648e8d5b8d995d8ULL,
+    0xa63975a605b31cf2ULL,
+    0x35e60de4a3359ad4ULL,
+    0x9b81705b2e4be07bULL,
+    0xb9ae701a8eb85593ULL,
+    0xaedecc0d138f3115ULL,
+    0x8a1fdbb92e3423c1ULL,
+    0xb0c96dee77615860ULL,
+    0x629b7c06bf44e634ULL,
+    0x696eb82aa746b1e1ULL,
+    0x02efce1165256d4fULL,
+    0x69d7a6b7150117a6ULL,
+    0x9dcc2d6e896e5681ULL,
+    0xcd815845d154cfbeULL,
+    0x28ea53acb6da26f0ULL,
+    0x7100bc4d21fe52dfULL,
+    0x653e558ec969142fULL,
+    0x83d730de45a0f5d4ULL,
+    0x3831dd5c5647e4b1ULL,
+    0x0f4072bf5123e9d5ULL,
+    0xa642dce46ec285eeULL,
+    0xae995373b5193c28ULL,
+    0xf0f3dafb8a611288ULL,
+    0xbc482a9e9b15c5abULL,
+    0x41668ebcdc7cc0f4ULL,
+    0xcdaaef0cd5519603ULL,
+    0xebc0b08ad6d7c0e5ULL,
+    0xb35073399de97c08ULL,
+    0x97e4241d5f265b52ULL,
+    0x2e52578c54e99676ULL,
+    0x288a75c28fad917bULL,
+    0x466e1dd37d710926ULL,
+    0x25fd42c4845ce5fcULL,
+    0xe0a1137fa3234b76ULL,
+    0xfbfc21548eb90370ULL,
+    0x8c4cf202e1e875feULL,
+    0x9b7cd1e8a5aaa1a1ULL,
+    0x2dec3dc9615ca561ULL,
+    0xb4458b07977eea11ULL,
+    0x75cea1e7a8560366ULL,
+    0x109bf4b3b2e39a46ULL,
+    0xdf8ed90441ba266bULL,
+    0xd1856901e5f8bac7ULL,
+    0x7a8b4ab2edd81a62ULL,
+    0xb1ae8556c90ae5cbULL,
+    0x42d15186c967771fULL,
+    0xa07cdf5a38a872a9ULL,
+    0x986954db9832acebULL,
+    0xf130e68aa4fce616ULL,
+    0xcc0caef3d0c76c52ULL,
+    0x2c6a3fe49a7d500eULL,
+    0x076cb3ad48ed1b85ULL,
+    0xe6f8d0aecbb14027ULL,
+    0x2cbe5b65d4e5c490ULL,
+    0x9dac9ec2da0d12a7ULL,
+    0x14ab4abbd07e5ab0ULL,
+    0xae99ca6cb4cd1e03ULL,
+    0x3bcd346450954fbaULL,
+    0x2430fee89dd27a62ULL,
+    0x7dc551166f0c94f8ULL,
+    0x87947cbebe2a5031ULL,
+    0x67003a8dfe2fd1b0ULL,
+    0xfed080735857b507ULL,
+    0x5097a42c664d9bf9ULL,
+    0x9389590f671cf117ULL,
+    0x9c5781b4f071956dULL,
+    0x9c16eac9bd72017aULL,
+    0x45186d635717d743ULL,
+    0x3f375208bc7ce161ULL,
+    0x768cd5d30f885c47ULL };
+}  // net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/rolling_hash_test.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/rolling_hash_test.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/rolling_hash_test.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/rolling_hash_test.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,114 @@
+/*
+ * Copyright 2010 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: jmaessen@google.com (Jan Maessen)
+
+#include "net/instaweb/util/public/rolling_hash.h"
+
+#include <cstddef>
+#include <cstdio>
+#include <utility>
+#include "net/instaweb/util/public/basictypes.h"
+#include "net/instaweb/util/public/dense_hash_set.h"
+#include "net/instaweb/util/public/gtest.h"
+#include "net/instaweb/util/public/string_util.h"
+
+namespace net_instaweb {
+namespace {
+
+const char kTestString[] =
+    "The quick brown fox jumps over the lazy dog.\n"
+    "Now is the time for ALL good men to come to the aid of their party.\r\n"
+    "@$%^@#$%#^%^987293 458798\x8f\xfa\xce\t";
+const size_t kTestStringSize = STATIC_STRLEN(kTestString);
+
+TEST(RollingHashTest, EmptyString) {
+  EXPECT_EQ(0, RollingHash("", 0, 0));
+  EXPECT_EQ(0, RollingHash(NULL, 0, 0));
+}
+
+TEST(RollingHashTest, SingleChar) {
+  EXPECT_EQ(kRollingHashCharTable[' '], RollingHash(" ", 0, 1));
+}
+
+TEST(RollingHashTest, SingleRoll) {
+  static const char kCSpace[] = "C ";
+  uint64 h0 = RollingHash(kCSpace, 0, 1);
+  EXPECT_EQ(kRollingHashCharTable['C'], h0);
+  EXPECT_EQ(kRollingHashCharTable[' '], NextRollingHash(kCSpace, 1, 1, h0));
+}
+
+TEST(RollingHashTest, RollShakedown) {
+  for (size_t i = 1; i < kTestStringSize; ++i) {
+    uint64 hash = RollingHash(kTestString, 0, i);
+    for (size_t j = 1; j < kTestStringSize - i; ++j) {
+      hash = NextRollingHash(kTestString, j, i, hash);
+      EXPECT_EQ(RollingHash(kTestString, j, i), hash);
+    }
+  }
+}
+
+// Prove that there are no trivial 1-, 2-, or 3-gram overlaps.
+// Note that the open-vcdiff rolling hash cannot pass this test
+// as it only has 23 bits!
+TEST(RollingHashTest, NGrams) {
+  // Using dense_hash_set is MUCH faster (6x) than std::set.
+  // That keeps this test "small".
+  dense_hash_set<uint64> grams;
+  grams.set_empty_key(0ULL);
+  char buf[3];
+  uint64 hash;
+  bool gramOverlap = false;
+  for (int i = 0; i < 256; i++) {
+    buf[0] = i;
+    hash = RollingHash(buf, 0, 1);
+    ASSERT_NE(0, hash);
+    if (!grams.insert(hash).second) {
+      gramOverlap = true;
+      printf("Gram overlap including %2x", i);
+    }
+  }
+  for (int i = 0; i < 256; i++) {
+    buf[0] = i;
+    for (int j = 0; j < 256; j++) {
+      buf[1] = j;
+      hash = RollingHash(buf, 0, 2);
+      ASSERT_NE(0, hash);
+      if (!grams.insert(hash).second) {
+        gramOverlap = true;
+        printf("Gram overlap including %2x %2x", i, j);
+      }
+    }
+  }
+  for (int i = 0; i < 256; i++) {
+    buf[0] = i;
+    for (int j = 0; j < 256; j++) {
+      buf[1] = j;
+      for (int k = 0; k < 256; k++) {
+        buf[2] = k;
+        hash = RollingHash(buf, 0, 3);
+        ASSERT_NE(0, hash);
+        if (!grams.insert(hash).second) {
+          gramOverlap = true;
+          printf("Gram overlap including %2x %2x %2x\n", i, j, k);
+        }
+      }
+    }
+  }
+  EXPECT_FALSE(gramOverlap);
+}
+
+}  // namespace
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/scheduler.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/scheduler.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/scheduler.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/scheduler.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,399 @@
+// 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.
+//
+// Authors: jmarantz@google.com (Joshua Marantz)
+//          jmaessen@google.com (Jan Maessen)
+
+#include "net/instaweb/util/public/scheduler.h"
+
+#include <algorithm>
+#include <set>
+
+#include "base/logging.h"
+#include "base/scoped_ptr.h"
+#include "net/instaweb/util/public/abstract_mutex.h"
+#include "net/instaweb/util/public/basictypes.h"
+#include "net/instaweb/util/public/condvar.h"
+#include "net/instaweb/util/public/function.h"
+#include "net/instaweb/util/public/timer.h"
+
+namespace net_instaweb {
+
+namespace {
+
+const int kIndexNotSet = 0;
+
+}  // namespace
+
+// Basic Alarm type (forward declared in the .h file).  Note that
+// Alarms are self-cleaning; it is not valid to make use of an Alarm*
+// after RunAlarm() or CancelAlarm() has been called.  See note below
+// for AddAlarm.  Note also that Alarms hold the scheduler lock when
+// they are invoked; the alarm drops the lock before invoking its
+// embedded callback and re-takes it afterwards if that is necessary.
+class Scheduler::Alarm {
+ public:
+  virtual void RunAlarm() = 0;
+  virtual void CancelAlarm() = 0;
+
+  // Compare two alarms, based on wakeup time and insertion order.  Result
+  // like strcmp (<0 for this < that, >0 for this > that), based on wakeup
+  // time and index.
+  int Compare(const Alarm* other) const {
+    int cmp = 0;
+    if (this != other) {
+      if (wakeup_time_us_ < other->wakeup_time_us_) {
+        cmp = -1;
+      } else if (wakeup_time_us_ > other->wakeup_time_us_) {
+        cmp = 1;
+      } else if (index_ < other->index_) {
+        cmp = -1;
+      } else {
+        DCHECK(index_ > other->index_);
+        cmp = 1;
+      }
+    }
+    return cmp;
+  }
+
+ protected:
+  Alarm() : wakeup_time_us_(0),
+            index_(kIndexNotSet) { }
+  virtual ~Alarm() { }
+
+ private:
+  friend class Scheduler;
+  int64 wakeup_time_us_;
+  uint32 index_;  // Set by scheduler to disambiguate equal wakeup times.
+  DISALLOW_COPY_AND_ASSIGN(Alarm);
+};
+
+namespace {
+
+// private class to encapsulate a function being
+// scheduled as an alarm.  Owns passed-in function.
+class FunctionAlarm : public Scheduler::Alarm {
+ public:
+  explicit FunctionAlarm(Function* function, Scheduler* scheduler)
+      : scheduler_(scheduler), function_(function) { }
+  virtual ~FunctionAlarm() { }
+
+  virtual void RunAlarm() {
+    DropMutexActAndCleanup(&Function::CallRun);
+  }
+  virtual void CancelAlarm() {
+    DropMutexActAndCleanup(&Function::CallCancel);
+  }
+ private:
+  typedef void (Function::*FunctionAction)();
+  void DropMutexActAndCleanup(FunctionAction act) {
+    AbstractMutex* mutex = scheduler_->mutex();  // Save across delete.
+    mutex->Unlock();
+    ((function_)->*(act))();
+    delete this;
+    mutex->Lock();
+  }
+  Scheduler* scheduler_;
+  Function* function_;
+  DISALLOW_COPY_AND_ASSIGN(FunctionAlarm);
+};
+
+}  // namespace
+
+// The following three classes are effectively supposed to be private, and
+// should only be used internally to the scheduler, but are semi-exposed due to
+// C++ naming restrictions.  The first two implement condvar waiting.  When we
+// wait using BlockingTimedWait or TimedWait, we put a single alarm into two
+// queues: the outstanding_alarms_ queue, where it will be run if the wait times
+// out, and the waiting_alarms_ queue, where it will be canceled if a signal
+// arrives.  The system assumes the waiting_alarms_ queue is a subset of the
+// outstanding_alarms_ queue, because it holds *only* alarms from ...TimedWait
+// operations, so on signal the contents of waiting_alarms are cancelled thus
+// removing them from waiting_alarms and invoking the Cancel() method.  However,
+// on timeout the Run() method must remove the alarm from the waiting_alarms_
+// queue so it can be cleaned up safely; doing so means invoking callbacks and
+// requires us to drop the scheduler lock.  This leads to a harmless violation
+// of the subset condition; see the comment on CancelWaiting which describes the
+// handling of this condition.
+
+// Blocking condvar alarm.  Simply sets a flag for the blocking thread to
+// notice.
+class Scheduler::CondVarTimeout : public Scheduler::Alarm {
+ public:
+  CondVarTimeout(bool* set_on_timeout, Scheduler* scheduler)
+      : set_on_timeout_(set_on_timeout),
+        scheduler_(scheduler) { }
+  virtual ~CondVarTimeout() { }
+  virtual void RunAlarm() {
+    *set_on_timeout_ = true;
+    scheduler_->CancelWaiting(this);
+    delete this;
+  }
+  virtual void CancelAlarm() {
+    delete this;
+  }
+ private:
+  bool* set_on_timeout_;
+  Scheduler* scheduler_;
+  DISALLOW_COPY_AND_ASSIGN(CondVarTimeout);
+};
+
+// Non-blocking condvar alarm.  Must run the passed-in callback on either
+// timeout (Run()) or signal (Cancel()).
+class Scheduler::CondVarCallbackTimeout : public Scheduler::Alarm {
+ public:
+  CondVarCallbackTimeout(Function* callback, Scheduler* scheduler)
+      : callback_(callback),
+        scheduler_(scheduler) { }
+  virtual ~CondVarCallbackTimeout() { }
+  virtual void RunAlarm() {
+    scheduler_->CancelWaiting(this);
+    CancelAlarm();
+  }
+  virtual void CancelAlarm() {
+    callback_->CallRun();
+    delete this;
+  }
+ private:
+  Function* callback_;
+  Scheduler* scheduler_;
+  DISALLOW_COPY_AND_ASSIGN(CondVarCallbackTimeout);
+};
+
+// Comparison on Alarms.
+bool Scheduler::CompareAlarms::operator()(const Alarm* a,
+                                          const Alarm* b) const {
+  return a->Compare(b) < 0;
+}
+
+Scheduler::Scheduler(ThreadSystem* thread_system, Timer* timer)
+    : thread_system_(thread_system),
+      timer_(timer),
+      mutex_(thread_system->NewMutex()),
+      condvar_(mutex_->NewCondvar()),
+      index_(kIndexNotSet),
+      signal_count_(0),
+      running_waiting_alarms_(false) {
+}
+
+Scheduler::~Scheduler() {
+}
+
+ThreadSystem::CondvarCapableMutex* Scheduler::mutex() {
+  return mutex_.get();
+}
+
+void Scheduler::DCheckLocked() { mutex_->DCheckLocked(); }
+
+void Scheduler::BlockingTimedWait(int64 timeout_ms) {
+  mutex_->DCheckLocked();
+  int64 now_us = timer_->NowUs();
+  int64 wakeup_time_us = now_us + timeout_ms * Timer::kMsUs;
+  // We block until signal_count_ changes or we time out.
+  int64 original_signal_count = signal_count_;
+  bool timed_out = false;
+  // Schedule a timeout alarm.
+  CondVarTimeout* alarm = new CondVarTimeout(&timed_out, this);
+  AddAlarmMutexHeld(wakeup_time_us, alarm);
+  waiting_alarms_.insert(alarm);
+  int64 next_wakeup_us = RunAlarms(NULL);
+  while (signal_count_ == original_signal_count && !timed_out &&
+         next_wakeup_us > 0) {
+    // Now we have to block until either we time out, or we are signaled.  We
+    // stop when outstanding_alarms_ is empty (and thus RunAlarms(NULL) == 0) as
+    // a belt and suspenders protection against programmer error; this ought to
+    // imply timed_out.
+    AwaitWakeupUntilUs(std::min(wakeup_time_us, next_wakeup_us));
+    next_wakeup_us = RunAlarms(NULL);
+  }
+}
+
+void Scheduler::TimedWait(int64 timeout_ms, Function* callback) {
+  mutex_->DCheckLocked();
+  int64 now_us = timer_->NowUs();
+  int64 completion_time_us = now_us + timeout_ms * Timer::kMsUs;
+  // We create the alarm for this callback, and register it.  We also register
+  // the alarm with the signal queue, where the callback will be run on
+  // cancellation.
+  CondVarCallbackTimeout* alarm = new CondVarCallbackTimeout(callback, this);
+  AddAlarmMutexHeld(completion_time_us, alarm);
+  waiting_alarms_.insert(alarm);
+  RunAlarms(NULL);
+}
+
+void Scheduler::CancelWaiting(Alarm* alarm) {
+  // Called to clean up a [Blocking]TimedWait that timed out.  There used to be
+  // a benign race here that meant alarm had been erased from waiting_alarms_ by
+  // a pending Signal operation.  Tighter locking on Alarm objects should have
+  // eliminated this hole, but we continue to use presence / absence in
+  // outstanding_alarms_ to resolve signal/cancel races.
+  mutex_->DCheckLocked();
+  waiting_alarms_.erase(alarm);
+}
+
+void Scheduler::Signal() {
+  mutex_->DCheckLocked();
+  ++signal_count_;
+  // We have to be careful to not just walk over waiting_alarms_ here
+  // as new entries can be added to it by TimedWait invocations from the
+  // callbacks we run.
+  AlarmSet waiting_alarms_to_dispatch;
+  waiting_alarms_to_dispatch.swap(waiting_alarms_);
+  running_waiting_alarms_ = true;
+  if (!waiting_alarms_to_dispatch.empty()) {
+    for (AlarmSet::iterator i = waiting_alarms_to_dispatch.begin();
+         i != waiting_alarms_to_dispatch.end(); ++i) {
+      // The Cancel() methods for waiting_alarms_ retain the scheduler mutex.
+      CancelAlarm(*i);
+    }
+  }
+  condvar_->Broadcast();
+  running_waiting_alarms_ = false;
+  RunAlarms(NULL);
+}
+
+// Add alarm while holding mutex.  Don't run any alarms or otherwise drop mutex.
+void Scheduler::AddAlarmMutexHeld(int64 wakeup_time_us, Alarm* alarm) {
+  mutex_->DCheckLocked();
+  alarm->wakeup_time_us_ = wakeup_time_us;
+  alarm->index_ = ++index_;
+  // Someone may care about changes in wait time.  Broadcast if any occurred.
+  if (!outstanding_alarms_.empty()) {
+    Alarm* first_alarm = *outstanding_alarms_.begin();
+    if (wakeup_time_us < first_alarm->wakeup_time_us_) {
+      condvar_->Broadcast();
+    }
+  } else {
+    condvar_->Broadcast();
+  }
+  outstanding_alarms_.insert(alarm);
+}
+
+Scheduler::Alarm* Scheduler::AddAlarm(int64 wakeup_time_us,
+                                      Function* callback) {
+  Alarm* result = new FunctionAlarm(callback, this);
+  ScopedMutex lock(mutex_.get());
+  AddAlarmMutexHeld(wakeup_time_us, result);
+  RunAlarms(NULL);
+  return result;
+}
+
+bool Scheduler::CancelAlarm(Alarm* alarm) {
+  mutex_->DCheckLocked();
+  if (outstanding_alarms_.erase(alarm) != 0) {
+    // Note: the following call may drop and re-lock the scheduler mutex.
+    alarm->CancelAlarm();
+    return true;
+  } else {
+    return false;
+  }
+}
+
+// Run any alarms that have reached their deadline.  Requires that we hold
+// mutex_ before calling.  Returns the time of the next deadline, or 0 if no
+// further deadlines loom.  Sets *ran_alarms if non-NULL and any alarms were
+// run, otherwise leaves it untouched.
+int64 Scheduler::RunAlarms(bool* ran_alarms) {
+  while (!outstanding_alarms_.empty()) {
+    mutex_->DCheckLocked();
+    // We don't use the iterator to go through the set, because we're dropping
+    // the lock in mid-loop thus permitting new insertions and cancellations.
+    AlarmSet::iterator first_alarm_iterator = outstanding_alarms_.begin();
+    Alarm* first_alarm = *first_alarm_iterator;
+    int64 now_us = timer_->NowUs();
+    if (now_us < first_alarm->wakeup_time_us_) {
+      // The next deadline lies in the future.
+      return first_alarm->wakeup_time_us_;
+    }
+    // first_alarm should be run.  It can't have been cancelled as we've held
+    // the lock since we found it.
+    outstanding_alarms_.erase(first_alarm_iterator);  // Prevent cancellation.
+    if (ran_alarms != NULL) {
+      *ran_alarms = true;
+    }
+    // Note that the following call may drop and re-lock the scheduler lock.
+    first_alarm->RunAlarm();
+  }
+  return 0;
+}
+
+void Scheduler::AwaitWakeupUntilUs(int64 wakeup_time_us) {
+  mutex_->DCheckLocked();
+  int64 now_us = timer_->NowUs();
+  if (wakeup_time_us > now_us) {
+    // Compute how long we should wait.  Note: we overshoot, which may lead us
+    // to wake a bit later than expected.  We assume the system is likely to
+    // round wakeup time off for us in some arbitrary fashion in any case.
+    int64 wakeup_interval_ms =
+        (wakeup_time_us - now_us + Timer::kMsUs - 1) / Timer::kMsUs;
+    condvar_->TimedWait(wakeup_interval_ms);
+  }
+}
+
+void Scheduler::Wakeup() {
+  condvar_->Broadcast();
+}
+
+void Scheduler::ProcessAlarms(int64 timeout_us) {
+  mutex_->DCheckLocked();
+  bool ran_alarms = false;
+  int64 finish_us = timer_->NowUs() + timeout_us;
+  int64 next_wakeup_us = RunAlarms(&ran_alarms);
+
+  if (timeout_us > 0 && !ran_alarms) {
+    // Note: next_wakeup_us may be 0 here.
+    if (next_wakeup_us == 0 || next_wakeup_us > finish_us) {
+      next_wakeup_us = finish_us;
+    }
+    AwaitWakeupUntilUs(next_wakeup_us);
+
+    RunAlarms(&ran_alarms);
+  }
+}
+
+// For testing purposes, let a tester know when the scheduler has quiesced.
+bool Scheduler::NoPendingAlarms() {
+  mutex_->DCheckLocked();
+  return (outstanding_alarms_.empty());
+}
+
+SchedulerBlockingFunction::SchedulerBlockingFunction(Scheduler* scheduler)
+    : scheduler_(scheduler), success_(false) {
+  set_delete_after_callback(false);
+}
+
+SchedulerBlockingFunction::~SchedulerBlockingFunction() { }
+
+void SchedulerBlockingFunction::Run() {
+  success_ = true;
+  Cancel();
+}
+
+void SchedulerBlockingFunction::Cancel() {
+  done_.set_value(true);
+  scheduler_->Wakeup();
+}
+
+bool SchedulerBlockingFunction::Block() {
+  ScopedMutex lock(scheduler_->mutex());
+  while (!done_.value()) {
+    scheduler_->ProcessAlarms(10 * Timer::kSecondUs);
+  }
+  return success_;
+}
+
+void Scheduler::RegisterWorker(QueuedWorkerPool::Sequence* w) {}
+void Scheduler::UnregisterWorker(QueuedWorkerPool::Sequence* w) {}
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/scheduler_based_abstract_lock.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/scheduler_based_abstract_lock.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/scheduler_based_abstract_lock.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/scheduler_based_abstract_lock.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,230 @@
+/*
+ * 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: jmaessen@google.com (Jan Maessen)
+
+#include "net/instaweb/util/public/scheduler_based_abstract_lock.h"
+
+#include "base/logging.h"
+#include "net/instaweb/util/public/basictypes.h"
+#include "net/instaweb/util/public/debug.h"
+#include "net/instaweb/util/public/function.h"
+#include "net/instaweb/util/public/string.h"
+#include "net/instaweb/util/public/scheduler.h"
+#include "net/instaweb/util/public/timer.h"
+
+namespace net_instaweb {
+
+namespace {
+
+// Number of times we busy spin before we start to sleep.
+// TODO(jmaessen): Is this the right setting?
+const int kBusySpinIterations = 100;
+const int64 kMaxSpinSleepMs = Timer::kMinuteMs;  // Never sleep for more than 1m
+const int64 kMinTriesPerSteal = 2;  // Try to lock twice / steal interval.
+
+// We back off exponentially, with a constant of 1.5.  We add an extra ms to
+// this backoff to avoid problems with wait intervals of 0 or 1.  We bound the
+// blocking time at kMaxSpinSleepMs.
+int64 Backoff(int64 interval_ms, int64 max_interval_ms) {
+  int64 new_interval_ms = 1 + interval_ms + (interval_ms >> 1);
+  if (new_interval_ms >= max_interval_ms) {
+    new_interval_ms = max_interval_ms;
+    // Log the first time we reach or cross the threshold.
+    // TODO(jmaessen): LOG(ERROR) is deadlocking.  Why?  We're using cooperative
+    // thread cancellation in the tests that hang, and it sometimes succeeds.
+    if (false && interval_ms != max_interval_ms) {
+      LOG(ERROR) << "Reached maximum sleep time " << StackTraceString().c_str();
+    }
+  }
+  return new_interval_ms;
+}
+
+// Compute new backoff time interval given current interval_ms, but don't exceed
+// max_interval_ms or have the interval continue much past end_time_ms.
+int64 IntervalWithEnd(Timer* timer, int64 interval_ms,
+                      int64 max_interval_ms, int64 end_time_ms) {
+  int64 now_ms = timer->NowMs();
+  int64 remaining = end_time_ms - now_ms;
+  interval_ms = Backoff(interval_ms, max_interval_ms);
+  if (remaining > interval_ms) {
+    return interval_ms;
+  } else {
+    return remaining;
+  }
+}
+
+// This object actually contains the state needed for periodically polling the
+// provided lock using the try_lock method, and for eventually calling or
+// canceling the callback. While it may feel attractive to reuse this object,
+// it's not actually safe as it runs into races trying to check the
+// delete_after_callback_ bit.
+class TimedWaitPollState : public Function {
+ public:
+  typedef bool (SchedulerBasedAbstractLock::*TryLockMethod)(int64 steal_ms);
+
+  TimedWaitPollState(
+      Scheduler* scheduler, Function* callback,
+      SchedulerBasedAbstractLock* lock, TryLockMethod try_lock,
+      int64 steal_ms, int64 end_time_ms,
+      int64 max_interval_ms)
+      : scheduler_(scheduler),
+        callback_(callback),
+        lock_(lock),
+        try_lock_(try_lock),
+        steal_ms_(steal_ms),
+        end_time_ms_(end_time_ms),
+        max_interval_ms_(max_interval_ms),
+        interval_ms_(0) {}
+  virtual ~TimedWaitPollState() { }
+
+  // Note: doesn't actually clone interval_ms_.
+  TimedWaitPollState* Clone() {
+    return new TimedWaitPollState(scheduler_, callback_, lock_,
+                                  try_lock_, steal_ms_, end_time_ms_,
+                                  max_interval_ms_);
+  }
+
+ protected:
+  virtual void Run() {
+    if ((lock_->*try_lock_)(steal_ms_)) {
+      callback_->CallRun();
+      return;
+    }
+    Timer* timer = scheduler_->timer();
+    int64 now_ms = timer->NowMs();
+    if (now_ms >= end_time_ms_) {
+      callback_->CallCancel();
+      return;
+    }
+
+    TimedWaitPollState* next_try = Clone();
+    next_try->interval_ms_ =
+        IntervalWithEnd(timer, interval_ms_, max_interval_ms_, end_time_ms_);
+    scheduler_->AddAlarm((now_ms + next_try->interval_ms_) * Timer::kMsUs,
+                         next_try);
+  }
+
+ private:
+  Scheduler* scheduler_;
+  Function* callback_;
+  SchedulerBasedAbstractLock* lock_;
+  TryLockMethod try_lock_;
+  const int64 steal_ms_;
+  const int64 end_time_ms_;
+  const int64 max_interval_ms_;
+  int64 interval_ms_;
+};
+
+}  // namespace
+
+SchedulerBasedAbstractLock::~SchedulerBasedAbstractLock() { }
+
+void SchedulerBasedAbstractLock::PollAndCallback(
+    TryLockMethod try_lock, int64 steal_ms, int64 wait_ms, Function* callback) {
+  // Measure ending time from immediately after failure of the fast path.
+  int64 end_time_ms = scheduler()->timer()->NowMs() + wait_ms;
+  if (BusySpin(try_lock, steal_ms)) {
+    callback->CallRun();
+    return;
+  }
+  // Slow path.  Allocate a TimedWaitPollState object and cede control to it.
+  int64 max_interval_ms = (steal_ms + 1) / kMinTriesPerSteal;
+  TimedWaitPollState* poller =
+      new TimedWaitPollState(scheduler(), callback, this,
+                             try_lock, steal_ms,
+                             end_time_ms, max_interval_ms);
+  poller->CallRun();
+}
+
+// The basic structure of each locking operation is the same:
+// Quick check for a free lock using TryLock().
+// If that fails, call PollAndCallBack, which:
+//   * First busy spins attempting to obtain the lock
+//   * If that fails, schedules an alarm that attempts to take the lock,
+//     or failing that backs off and schedules another alarm.
+// We run callbacks as soon as possible.  We could instead defer them
+// to a scheduler sequence, but in practice we don't have an appropriate
+// sequence to hand when we we stand up the lock manager.  So it's up to
+// callers to schedule appropriate tasks when locks have been obtained.
+
+bool SchedulerBasedAbstractLock::LockTimedWait(int64 wait_ms) {
+  if (TryLock()) {
+    // Fast path.
+    return true;
+  } else {
+    SchedulerBlockingFunction block(scheduler());
+    PollAndCallback(&SchedulerBasedAbstractLock::TryLockIgnoreSteal,
+                    kMinTriesPerSteal * kMaxSpinSleepMs, wait_ms, &block);
+    return block.Block();
+  }
+}
+
+void SchedulerBasedAbstractLock::LockTimedWait(
+    int64 wait_ms, Function* callback) {
+  if (TryLock()) {
+    // Fast path.
+    callback->CallRun();
+  } else {
+    PollAndCallback(&SchedulerBasedAbstractLock::TryLockIgnoreSteal,
+                    kMinTriesPerSteal * kMaxSpinSleepMs, wait_ms, callback);
+  }
+}
+
+bool SchedulerBasedAbstractLock::LockTimedWaitStealOld(
+    int64 wait_ms, int64 steal_ms) {
+  if (TryLock()) {
+    // Fast path.
+    return true;
+  } else {
+    SchedulerBlockingFunction block(scheduler());
+    PollAndCallback(&SchedulerBasedAbstractLock::TryLockStealOld,
+                    steal_ms, wait_ms, &block);
+    return block.Block();
+  }
+}
+
+void SchedulerBasedAbstractLock::LockTimedWaitStealOld(
+    int64 wait_ms, int64 steal_ms, Function* callback) {
+  if (TryLock()) {
+    // Fast path.
+    callback->CallRun();
+  } else {
+    PollAndCallback(&SchedulerBasedAbstractLock::TryLockStealOld,
+                    steal_ms, wait_ms, callback);
+  }
+}
+
+// We implement spinning without regard to whether the underlying lock primitive
+// can time out or not.  This wrapper method is just TryLock with a bogus
+// timeout parameter, so that we can pass timeout-free TryLock to a spin
+// routine.
+bool SchedulerBasedAbstractLock::TryLockIgnoreSteal(int64 steal_ignored) {
+  return TryLock();
+}
+
+// Actively attempt to take lock without pausing.
+bool SchedulerBasedAbstractLock::BusySpin(TryLockMethod try_lock,
+                                          int64 steal_ms) {
+  for (int i = 0; i < kBusySpinIterations; i++) {
+    if ((this->*try_lock)(steal_ms)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/scheduler_based_abstract_lock_test.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/scheduler_based_abstract_lock_test.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/scheduler_based_abstract_lock_test.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/scheduler_based_abstract_lock_test.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,433 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// 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: jmaessen@google.com (Jan Maessen)
+
+#include "net/instaweb/util/public/scheduler_based_abstract_lock.h"
+
+#include "base/logging.h"
+#include "base/scoped_ptr.h"
+#include "net/instaweb/util/public/abstract_mutex.h"
+#include "net/instaweb/util/public/atomic_bool.h"
+#include "net/instaweb/util/public/basictypes.h"
+#include "net/instaweb/util/public/condvar.h"
+#include "net/instaweb/util/public/gtest.h"
+#include "net/instaweb/util/public/mock_scheduler.h"
+#include "net/instaweb/util/public/mock_timer.h"
+#include "net/instaweb/util/public/timer.h"
+#include "net/instaweb/util/public/scheduler.h"
+#include "net/instaweb/util/public/string.h"
+#include "net/instaweb/util/public/thread.h"
+#include "net/instaweb/util/public/thread_system.h"
+
+namespace net_instaweb {
+
+namespace {
+
+static const int kShortMs = 10;
+static const int kLongMs = 100;
+
+class SchedulerBasedAbstractLockTest : public testing::Test {
+ protected:
+  SchedulerBasedAbstractLockTest()
+      : timer_(0),
+        thread_system_(ThreadSystem::CreateThreadSystem()),
+        scheduler_(thread_system_.get(), &timer_) {
+  }
+
+  MockTimer timer_;
+  scoped_ptr<ThreadSystem> thread_system_;
+  MockScheduler scheduler_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(SchedulerBasedAbstractLockTest);
+};
+
+// A mock lock base class
+class MockLockBase : public SchedulerBasedAbstractLock {
+ public:
+  explicit MockLockBase(Scheduler* scheduler) : scheduler_(scheduler) { }
+  virtual ~MockLockBase() { }
+  virtual Scheduler* scheduler() const { return scheduler_; }
+  // None of the mock locks actually implement locking, so
+  // unlocking is a no-op.
+  virtual void Unlock() { held_ = false; }
+  virtual bool Held() { return held_; }
+
+ protected:
+  Scheduler* scheduler_;
+  bool held_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(MockLockBase);
+};
+
+// A mock lock that always claims locking happened
+class AlwaysLock : public MockLockBase {
+ public:
+  explicit AlwaysLock(Scheduler* scheduler) : MockLockBase(scheduler) { }
+  virtual ~AlwaysLock() { }
+  virtual bool TryLock() {
+    held_ = true;
+    return true;
+  }
+  virtual bool TryLockStealOld(int64 timeout_ms) {
+    held_ = true;
+    return true;
+  }
+  virtual GoogleString name() { return GoogleString("AlwaysLock"); }
+ private:
+  DISALLOW_COPY_AND_ASSIGN(AlwaysLock);
+};
+
+// A mock lock that always claims lock attempts failed
+class NeverLock : public MockLockBase {
+ public:
+  explicit NeverLock(Scheduler* scheduler) : MockLockBase(scheduler) { }
+  virtual ~NeverLock() { }
+  virtual bool TryLock() {
+    return false;
+  }
+  virtual bool TryLockStealOld(int64 timeout_ms) {
+    return false;
+  }
+  virtual GoogleString name() { return GoogleString("NeverLock"); }
+ private:
+  DISALLOW_COPY_AND_ASSIGN(NeverLock);
+};
+
+// A mock lock that can only be locked by stealing after a timeout.
+class StealOnlyLock : public NeverLock {
+ public:
+  explicit StealOnlyLock(Scheduler* scheduler)
+      : NeverLock(scheduler),
+        last_hold_time_ms_(scheduler_->timer()->NowMs()) {
+  }
+  virtual bool TryLockStealOld(int64 timeout_ms) {
+    int64 timeout_time_ms = last_hold_time_ms_ + timeout_ms;
+    int64 now_ms = scheduler()->timer()->NowMs();
+    if (timeout_time_ms <= now_ms) {
+      last_hold_time_ms_ = now_ms;
+      held_ = true;
+      return true;
+    } else {
+      return false;
+    }
+  }
+  virtual GoogleString name() { return GoogleString("StealOnlyLock"); }
+ private:
+  int64 last_hold_time_ms_;
+
+  DISALLOW_COPY_AND_ASSIGN(StealOnlyLock);
+};
+
+// Simple tests that involve either failed try or successfully obtaining lock.
+// Note that we always capture start times before lock construction, to account
+// for possible passage of mock time due to time queries during lock
+// construction.
+TEST_F(SchedulerBasedAbstractLockTest, AlwaysLock) {
+  int64 start = timer_.NowMs();
+  AlwaysLock always_lock(&scheduler_);
+  EXPECT_TRUE(always_lock.LockTimedWait(kLongMs));
+
+  SchedulerBlockingFunction block1(&scheduler_);
+  always_lock.LockTimedWait(kLongMs, &block1);
+  EXPECT_TRUE(block1.Block());
+
+  EXPECT_TRUE(always_lock.LockTimedWaitStealOld(kLongMs, kLongMs));
+
+  SchedulerBlockingFunction block2(&scheduler_);
+  always_lock.LockTimedWaitStealOld(kLongMs, kLongMs, &block2);
+  EXPECT_TRUE(block2.Block());
+
+  // Nothing should ever have slept.
+  int64 end = timer_.NowMs();
+  EXPECT_EQ(0, end - start);
+}
+
+TEST_F(SchedulerBasedAbstractLockTest, TimeoutHappens) {
+  int64 start = timer_.NowMs();
+  NeverLock never_lock(&scheduler_);
+  EXPECT_FALSE(never_lock.LockTimedWait(kShortMs));
+  int64 end = timer_.NowMs();
+  // At least kShortMs must have elapsed.
+  EXPECT_LE(kShortMs, end - start);
+  // But not more than twice as long.
+  EXPECT_GT(2 * kShortMs, end - start);
+}
+
+TEST_F(SchedulerBasedAbstractLockTest, CallbackTimeoutHappens) {
+  int64 start = timer_.NowMs();
+  NeverLock never_lock(&scheduler_);
+  SchedulerBlockingFunction block(&scheduler_);
+  never_lock.LockTimedWait(kShortMs, &block);
+  EXPECT_FALSE(block.Block());
+  int64 end = timer_.NowMs();
+  // At least kShortMs must have elapsed.
+  EXPECT_LE(kShortMs, end - start);
+  // But not more than twice as long.
+  EXPECT_GT(2 * kShortMs, end - start);
+}
+
+TEST_F(SchedulerBasedAbstractLockTest, TimeoutHappensStealOld) {
+  int64 start = timer_.NowMs();
+  NeverLock never_lock(&scheduler_);
+  EXPECT_FALSE(never_lock.LockTimedWaitStealOld(kShortMs, kLongMs));
+  int64 end = timer_.NowMs();
+  // Again at least kShortMs must have elapsed.
+  EXPECT_LE(kShortMs, end - start);
+  // But not more than twice as long.
+  EXPECT_GT(2 * kShortMs, end - start);
+}
+
+TEST_F(SchedulerBasedAbstractLockTest, CallbackTimeoutHappensStealOld) {
+  int64 start = timer_.NowMs();
+  NeverLock never_lock(&scheduler_);
+  SchedulerBlockingFunction block(&scheduler_);
+  never_lock.LockTimedWaitStealOld(kShortMs, kLongMs, &block);
+  EXPECT_FALSE(block.Block());
+  int64 end = timer_.NowMs();
+  // Again at least kShortMs must have elapsed.
+  EXPECT_LE(kShortMs, end - start);
+  // But not more than twice as long.
+  EXPECT_GT(2 * kShortMs, end - start);
+}
+
+TEST_F(SchedulerBasedAbstractLockTest, TimeoutBeforeSteal) {
+  int64 start = timer_.NowMs();
+  StealOnlyLock steal_only_lock(&scheduler_);
+  EXPECT_FALSE(steal_only_lock.LockTimedWaitStealOld(kShortMs, kLongMs));
+  int64 end = timer_.NowMs();
+  // Again at least kShortMs must have elapsed.
+  EXPECT_LE(kShortMs, end - start);
+  // But not more than twice as long.
+  EXPECT_GT(2 * kShortMs, end - start);
+}
+
+TEST_F(SchedulerBasedAbstractLockTest, CallbackTimeoutBeforeSteal) {
+  int64 start = timer_.NowMs();
+  StealOnlyLock steal_only_lock(&scheduler_);
+  SchedulerBlockingFunction block(&scheduler_);
+  steal_only_lock.LockTimedWaitStealOld(kShortMs, kLongMs, &block);
+  EXPECT_FALSE(block.Block());
+  int64 end = timer_.NowMs();
+  // Again at least kShortMs must have elapsed.
+  EXPECT_LE(kShortMs, end - start);
+  // But not more than twice as long.
+  EXPECT_GT(2 * kShortMs, end - start);
+}
+
+TEST_F(SchedulerBasedAbstractLockTest, StealBeforeTimeout) {
+  int64 start = timer_.NowMs();
+  StealOnlyLock steal_only_lock(&scheduler_);
+  EXPECT_TRUE(steal_only_lock.LockTimedWaitStealOld(kLongMs, kShortMs));
+  int64 end = timer_.NowMs();
+  // Again, at least kShortMs must have elapsed.
+  EXPECT_LE(kShortMs, end - start);
+  // And again, not more than twice as long.
+  EXPECT_GT(2 * kShortMs, end - start);
+}
+
+TEST_F(SchedulerBasedAbstractLockTest, CallbackStealBeforeTimeout) {
+  int64 start = timer_.NowMs();
+  StealOnlyLock steal_only_lock(&scheduler_);
+  SchedulerBlockingFunction block(&scheduler_);
+  steal_only_lock.LockTimedWaitStealOld(kLongMs, kShortMs, &block);
+  EXPECT_TRUE(block.Block());
+  int64 end = timer_.NowMs();
+  // Again, at least kShortMs must have elapsed.
+  EXPECT_LE(kShortMs, end - start);
+  // And again, not more than twice as long.
+  EXPECT_GT(2 * kShortMs, end - start);
+}
+
+// A wrapper that locks before operating on the underlying timer.  This really
+// only makes sense for a MockTimer, as most timers inherit any necessary
+// synchronization from the underlying library and OS (where it's done far more
+// efficiently).
+class LockedTimer : public Timer {
+ public:
+  LockedTimer(Timer* timer, ThreadSystem::CondvarCapableMutex* mutex)
+      : timer_(timer),
+        mutex_(mutex),
+        sleep_wakeup_condvar_(mutex->NewCondvar()) { }
+  virtual ~LockedTimer() { }
+  virtual void SleepUs(int64 us) {
+    {
+      ScopedMutex lock(mutex_);
+      timer_->SleepUs(us);
+      sleep_wakeup_condvar_->Signal();
+    }
+  }
+  virtual int64 NowUs() const {
+    ScopedMutex lock(mutex_);
+    return timer_->NowUs();
+  }
+  // Wait for other threads to advance mock time to end_ms.  Does not itself
+  // advance time; we're monitoring the activities of those other threads, which
+  // aren't going to terminate (and thus can't be monitored in line).
+  virtual void WaitUntilMs(int64 end_ms) {
+    ScopedMutex lock(mutex_);
+    while (timer_->NowMs() < end_ms) {
+      sleep_wakeup_condvar_->Wait();
+    }
+  }
+
+ private:
+  Timer* timer_;
+  ThreadSystem::CondvarCapableMutex* mutex_;
+  scoped_ptr<ThreadSystem::Condvar> sleep_wakeup_condvar_;
+};
+
+class ThreadedSchedulerBasedLockTest : public SchedulerBasedAbstractLockTest {
+ public:
+  // Various helper threads.  We could have done this with subclasses, but it's
+  // clunky for present needs (which are very simple).
+  // Grumble: C++ appears to require these methods to be public
+  // if we take their address in a subclass method.
+
+  // The default is DoNothingHelper, which just sleeps a long time and
+  // terminates.  The other helper threads do not terminate (and fail if they
+  // try).
+  void DoNothingHelper() {
+    SleepMs(kLongMs);
+  }
+  // Attempt to lock and spin forever
+  void LockHelper() {
+    while (!never_lock_.LockTimedWait(10 * kLongMs) && !done_.value()) { }
+    CHECK(done_.value()) << "Should not lock!";
+  }
+  // Attempt to Lock with a steal and spin forever.  This used to fail.
+  void LockStealHelper() {
+    while (!never_lock_.LockTimedWaitStealOld(10 * kLongMs, kShortMs) &&
+           !done_.value()) { }
+    CHECK(done_.value()) << "Shouldn't lock!";
+  }
+
+ protected:
+  typedef void (ThreadedSchedulerBasedLockTest::*HelperThreadMethod)();
+  ThreadedSchedulerBasedLockTest()
+      : never_lock_(&scheduler_),
+        startup_condvar_(scheduler_.mutex()->NewCondvar()),
+        helper_thread_(NULL),
+        helper_thread_method_(
+            &ThreadedSchedulerBasedLockTest::DoNothingHelper) { }
+  void SleepUntilMs(int64 end_ms) {
+    int64 now_ms = timer_.NowMs();
+    while (now_ms < end_ms) {
+      scheduler_.ProcessAlarms((end_ms - now_ms) * 1000);
+      now_ms = timer_.NowMs();
+    }
+  }
+  void SleepMs(int64 sleep_ms) {
+    AbstractMutex* mutex = scheduler_.mutex();
+    ScopedMutex lock(mutex);
+    int64 now_ms = timer_.NowMs();
+    SleepUntilMs(now_ms + sleep_ms);
+  }
+  // Start helper, then sleep for sleep_ms and return.
+  void SleepForHelper(int64 sleep_ms) {
+    AbstractMutex* mutex = scheduler_.mutex();
+    int64 now_ms;
+    {
+      ScopedMutex lock(mutex);
+      now_ms = timer_.NowMs();
+    }
+    StartHelper();
+    {
+      ScopedMutex lock(mutex);
+      SleepUntilMs(now_ms + sleep_ms);
+    }
+  }
+  void StartHelper() {
+    helper_thread_.reset(
+        new ThreadedSchedulerBasedLockTest::HelperThread(this));
+    helper_thread_->Start();
+    {
+      ScopedMutex lock(scheduler_.mutex());
+      while (!ready_to_start_.value()) {
+        startup_condvar_->Wait();
+      }
+      ready_to_start_.set_value(false);
+      startup_condvar_->Signal();
+    }
+  }
+  void FinishHelper() {
+    helper_thread_->Join();
+  }
+  // If the helper thread runs forever, we need to cancel it so that
+  // we can safely destruct the test objects before exit.
+  void CancelHelper() {
+    done_.set_value(true);
+    FinishHelper();
+  }
+  void set_helper(HelperThreadMethod helper) {
+    helper_thread_method_ = helper;
+  }
+
+  NeverLock never_lock_;
+
+ private:
+  class HelperThread : public ThreadSystem::Thread {
+   public:
+    explicit HelperThread(ThreadedSchedulerBasedLockTest* test)
+        : ThreadSystem::Thread(test->thread_system_.get(),
+                               ThreadSystem::kJoinable),
+          test_(test) { }
+    virtual void Run() {
+      {
+        ScopedMutex lock(test_->scheduler_.mutex());
+        test_->ready_to_start_.set_value(true);
+        test_->startup_condvar_->Signal();
+        while (test_->ready_to_start_.value()) {
+          test_->startup_condvar_->Wait();
+        }
+      }
+      (test_->*(test_->helper_thread_method_))();
+    }
+   private:
+    ThreadedSchedulerBasedLockTest* test_;
+    DISALLOW_COPY_AND_ASSIGN(HelperThread);
+  };
+
+  AtomicBool ready_to_start_;
+  AtomicBool done_;
+  scoped_ptr<ThreadSystem::Condvar> startup_condvar_;
+  scoped_ptr<HelperThread> helper_thread_;
+  HelperThreadMethod helper_thread_method_;
+
+  DISALLOW_COPY_AND_ASSIGN(ThreadedSchedulerBasedLockTest);
+};
+
+// Meta-Test that all is well.
+TEST_F(ThreadedSchedulerBasedLockTest, TestStartupHandshake) {
+  SleepForHelper(kShortMs);
+  FinishHelper();
+}
+
+TEST_F(ThreadedSchedulerBasedLockTest, TestLockBlock) {
+  set_helper(&ThreadedSchedulerBasedLockTest::LockHelper);
+  SleepForHelper(kLongMs);
+  CancelHelper();
+}
+
+TEST_F(ThreadedSchedulerBasedLockTest, TestLockStealBlock) {
+  set_helper(&ThreadedSchedulerBasedLockTest::LockStealHelper);
+  SleepForHelper(kLongMs);
+  CancelHelper();
+}
+
+}  // namespace
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/scheduler_test.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/scheduler_test.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/scheduler_test.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/scheduler_test.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,300 @@
+// 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: jmaessen@google.com (Jan-Willem Maessen)
+
+#include "net/instaweb/util/public/scheduler.h"
+
+#include "net/instaweb/util/public/abstract_mutex.h"
+#include "net/instaweb/util/public/basictypes.h"
+#include "net/instaweb/util/public/function.h"
+#include "net/instaweb/util/public/google_timer.h"
+#include "net/instaweb/util/public/gtest.h"
+#include "net/instaweb/util/public/thread_system.h"
+#include "net/instaweb/util/public/timer.h"
+#include "net/instaweb/util/worker_test_base.h"
+
+namespace net_instaweb {
+
+// Many tests cribbed from mock_timer_test, only without the mockery.  This
+// actually restricts the timing dependencies we can detect, though not in a
+// terrible way.
+class SchedulerTest : public WorkerTestBase {
+ protected:
+  SchedulerTest()
+      : thread_system_(ThreadSystem::CreateThreadSystem()),
+        timer_(),
+        scheduler_(thread_system_.get(), &timer_) { }
+
+  int Compare(const Scheduler::Alarm* a, const Scheduler::Alarm* b) const {
+    Scheduler::CompareAlarms comparator;
+    return comparator(a, b);
+  }
+
+  void LockAndProcessAlarms(int64 timeout_us) {
+    ScopedMutex lock(scheduler_.mutex());
+    scheduler_.ProcessAlarms(timeout_us);
+  }
+
+  void QuiesceAlarms(int64 timeout_us) {
+    ScopedMutex lock(scheduler_.mutex());
+    int64 now_us = timer_.NowUs();
+    int64 end_us = now_us + timeout_us;
+    while (now_us < end_us && !scheduler_.NoPendingAlarms()) {
+      scheduler_.ProcessAlarms(end_us - now_us);
+      now_us = timer_.NowUs();
+    }
+  }
+
+  scoped_ptr<ThreadSystem> thread_system_;
+  GoogleTimer timer_;
+  Scheduler scheduler_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(SchedulerTest);
+};
+
+namespace {
+
+const int64 kDsUs = Timer::kSecondUs / 10;
+const int64 kYearUs = Timer::kYearMs * Timer::kMsUs;
+
+TEST_F(SchedulerTest, AlarmsGetRun) {
+  int64 start_us = timer_.NowUs();
+  int counter = 0;
+  // Note that we give this test extra time (50ms) to start up so that
+  // we don't attempt to compare already-run (and thus deleted) alarms
+  // when running under valgrind.
+  Scheduler::Alarm* alarm1 =
+      scheduler_.AddAlarm(start_us + 52 * Timer::kMsUs,
+                          new CountFunction(&counter));
+  Scheduler::Alarm* alarm2 =
+      scheduler_.AddAlarm(start_us + 54 * Timer::kMsUs,
+                          new CountFunction(&counter));
+  Scheduler::Alarm* alarm3 =
+      scheduler_.AddAlarm(start_us + 53 * Timer::kMsUs,
+                          new CountFunction(&counter));
+  if (counter == 0) {
+    // In rare cases under Valgrind, we run over the 50ms limit and the
+    // callbacks get run and freed.  We skip these checks in that case.
+    // Ordinarily these can be observed to run (change the above test to true ||
+    // and run under valgrind to observe this).
+    EXPECT_FALSE(Compare(alarm1, alarm1));
+    EXPECT_FALSE(Compare(alarm2, alarm2));
+    EXPECT_FALSE(Compare(alarm3, alarm3));
+    EXPECT_TRUE(Compare(alarm1, alarm2));
+    EXPECT_TRUE(Compare(alarm1, alarm3));
+    EXPECT_FALSE(Compare(alarm2, alarm1));
+    EXPECT_FALSE(Compare(alarm2, alarm3));
+    EXPECT_FALSE(Compare(alarm3, alarm1));
+    EXPECT_TRUE(Compare(alarm3, alarm2));
+  }
+  {
+    ScopedMutex lock(scheduler_.mutex());
+    scheduler_.BlockingTimedWait(55);  // Never signaled, should time out.
+  }
+  int64 end_us = timer_.NowUs();
+  EXPECT_EQ(3, counter);
+  EXPECT_LT(start_us + 55 * Timer::kMsUs, end_us);
+  // Note: we assume this will terminate within 1 min., and will have hung
+  // noticeably if it didn't.
+  EXPECT_GT(start_us + Timer::kMinuteUs, end_us);
+};
+
+TEST_F(SchedulerTest, MidpointBlock) {
+  int64 start_us = timer_.NowUs();
+  int counter = 0;
+  scheduler_.AddAlarm(start_us + 2 * Timer::kMsUs, new CountFunction(&counter));
+  scheduler_.AddAlarm(start_us + 6 * Timer::kMsUs, new CountFunction(&counter));
+  scheduler_.AddAlarm(start_us + 3 * Timer::kMsUs, new CountFunction(&counter));
+  {
+    ScopedMutex lock(scheduler_.mutex());
+    scheduler_.BlockingTimedWait(4);  // Never signaled, should time out.
+  }
+  int64 mid_us = timer_.NowUs();
+  EXPECT_LT(start_us + 4 * Timer::kMsUs, mid_us);
+  EXPECT_LE(2, counter);
+  QuiesceAlarms(Timer::kMinuteUs);
+  int64 end_us = timer_.NowUs();
+  EXPECT_EQ(3, counter);
+  EXPECT_LT(start_us + 6 * Timer::kMsUs, end_us);
+  // Note: we assume this will terminate within 1 min., and will have hung
+  // noticeably if it didn't.
+  EXPECT_GT(start_us + Timer::kMinuteUs, end_us);
+};
+
+TEST_F(SchedulerTest, AlarmInPastRuns) {
+  int64 start_us = timer_.NowUs();
+  int counter = 0;
+  scheduler_.AddAlarm(start_us - 2 * Timer::kMsUs, new CountFunction(&counter));
+  Scheduler::Alarm* alarm2 =
+      scheduler_.AddAlarm(start_us + Timer::kMinuteUs,
+                          new CountFunction(&counter));
+  LockAndProcessAlarms(0);  // Don't block!
+  EXPECT_EQ(1, counter);
+  {
+    ScopedMutex lock(scheduler_.mutex());
+    scheduler_.CancelAlarm(alarm2);
+  }
+  int64 end_us = timer_.NowUs();
+  EXPECT_LT(start_us, end_us);
+  EXPECT_GT(start_us + Timer::kMinuteUs, end_us);
+};
+
+TEST_F(SchedulerTest, MidpointCancellation) {
+  int64 start_us = timer_.NowUs();
+  int counter = 0;
+  scheduler_.AddAlarm(start_us + 3 * Timer::kMsUs, new CountFunction(&counter));
+  scheduler_.AddAlarm(start_us + 2 * Timer::kMsUs, new CountFunction(&counter));
+  Scheduler::Alarm* alarm3 =
+      scheduler_.AddAlarm(start_us + Timer::kMinuteUs,
+                          new CountFunction(&counter));
+  {
+    ScopedMutex lock(scheduler_.mutex());
+    scheduler_.BlockingTimedWait(4);  // Never signaled, should time out.
+  }
+  int64 mid_us = timer_.NowUs();
+  EXPECT_LT(start_us + 4 * Timer::kMsUs, mid_us);
+  EXPECT_EQ(2, counter);
+  // No longer safe to cancel first two alarms.
+  {
+    ScopedMutex lock(scheduler_.mutex());
+    scheduler_.CancelAlarm(alarm3);
+  }
+  QuiesceAlarms(Timer::kMinuteUs);
+  int64 end_us = timer_.NowUs();
+  EXPECT_EQ(-98, counter);
+  EXPECT_LT(start_us + 3 * Timer::kMsUs, end_us);
+  // Note: we assume this will terminate within 1 min., and will have hung
+  // noticeably if it didn't.
+  EXPECT_GT(start_us + Timer::kMinuteUs, end_us);
+};
+
+TEST_F(SchedulerTest, SimultaneousAlarms) {
+  int64 start_us = timer_.NowUs();
+  int counter = 0;
+  scheduler_.AddAlarm(start_us + 2 * Timer::kMsUs, new CountFunction(&counter));
+  scheduler_.AddAlarm(start_us + 2 * Timer::kMsUs, new CountFunction(&counter));
+  scheduler_.AddAlarm(start_us + 2 * Timer::kMsUs, new CountFunction(&counter));
+  QuiesceAlarms(Timer::kMinuteUs);
+  int64 end_us = timer_.NowUs();
+  EXPECT_EQ(3, counter);
+  EXPECT_LT(start_us + 2 * Timer::kMsUs, end_us);
+  // Note: we assume this will terminate within 1 min., and will have hung
+  // noticeably if it didn't.
+  EXPECT_GT(start_us + Timer::kMinuteUs, end_us);
+};
+
+TEST_F(SchedulerTest, TimedWaitExpire) {
+  int64 start_us = timer_.NowUs();
+  int counter = 0;
+  {
+    ScopedMutex lock(scheduler_.mutex());
+    scheduler_.TimedWait(2, new CountFunction(&counter));
+    scheduler_.TimedWait(4, new CountFunction(&counter));
+    scheduler_.TimedWait(3, new CountFunction(&counter));
+    scheduler_.BlockingTimedWait(5);
+  }
+  int64 end_us = timer_.NowUs();
+  EXPECT_EQ(3, counter);
+  EXPECT_LT(start_us + 5 * Timer::kMsUs, end_us);
+  // Note: we assume this will terminate within 1 min., and will have hung
+  // noticeably if it didn't.
+  EXPECT_GT(start_us + Timer::kMinuteUs, end_us);
+};
+
+TEST_F(SchedulerTest, TimedWaitSignal) {
+  int64 start_us = timer_.NowUs();
+  int counter = 0;
+  {
+    ScopedMutex lock(scheduler_.mutex());
+    scheduler_.TimedWait(2, new CountFunction(&counter));
+    scheduler_.TimedWait(4, new CountFunction(&counter));
+    scheduler_.TimedWait(3, new CountFunction(&counter));
+    scheduler_.Signal();
+  }
+  int64 end_us = timer_.NowUs();
+  EXPECT_EQ(3, counter);
+  // Note: we assume this will terminate within 1 min., and will have hung
+  // noticeably if it didn't.
+  EXPECT_GT(start_us + Timer::kMinuteUs, end_us);
+};
+
+TEST_F(SchedulerTest, TimedWaitMidpointSignal) {
+  int64 start_us = timer_.NowUs();
+  int counter = 0;
+  {
+    ScopedMutex lock(scheduler_.mutex());
+    scheduler_.TimedWait(3, new CountFunction(&counter));
+    scheduler_.TimedWait(2, new CountFunction(&counter));
+    scheduler_.TimedWait(Timer::kYearMs, new CountFunction(&counter));
+    scheduler_.BlockingTimedWait(4);  // Will time out
+    EXPECT_EQ(2, counter);
+    scheduler_.Signal();
+  }
+  int64 end_us = timer_.NowUs();
+  EXPECT_EQ(3, counter);
+  // Note: we assume this will terminate within 1 min., and will have hung
+  // noticeably if it didn't.
+  EXPECT_GT(start_us + Timer::kMinuteUs, end_us);
+};
+
+// Function that retries a TimedWait when invoked until 10ms have passed.
+class RetryWaitFunction : public Function {
+ public:
+  RetryWaitFunction(Timer* timer, int64 start_ms, Scheduler* scheduler,
+                    int* counter)
+      : timer_(timer), start_ms_(start_ms),
+        scheduler_(scheduler), counter_(counter) {
+  }
+
+  virtual ~RetryWaitFunction() {}
+
+  virtual void Run() {
+    ++*counter_;
+    if ((timer_->NowMs() - start_ms_) < 10) {
+      // Note that we want the retry delay here to place us later than
+      // the original timeout the first invocation had, as that will
+      // place us later inside the wait queue ordering. In the past,
+      // that would cause Signal() to instantly detect us in the queue
+      // and run us w/o returning control.
+      scheduler_->TimedWait(
+          10, new RetryWaitFunction(timer_, start_ms_, scheduler_, counter_));
+    }
+  }
+
+ private:
+  Timer* timer_;
+  int64 start_ms_;
+  Scheduler* scheduler_;
+  int* counter_;
+  DISALLOW_COPY_AND_ASSIGN(RetryWaitFunction);
+};
+
+TEST_F(SchedulerTest, TimedWaitFromSignalWakeup) {
+  int counter = 0;
+  int64 start_ms = timer_.NowMs();
+  {
+    ScopedMutex lock(scheduler_.mutex());
+    scheduler_.TimedWait(
+        5, new RetryWaitFunction(&timer_, start_ms, &scheduler_, &counter));
+    scheduler_.Signal();
+  }
+  QuiesceAlarms(20 * Timer::kMsUs);
+  EXPECT_GE(2, counter);
+}
+
+}  // namespace
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/scheduler_thread.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/scheduler_thread.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/scheduler_thread.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/scheduler_thread.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,73 @@
+// 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.
+//
+// Authors: morlovich@google.com (Maksim Orlovich)
+
+#include "net/instaweb/util/public/scheduler_thread.h"
+
+#include "base/logging.h"
+#include "net/instaweb/util/public/abstract_mutex.h"
+#include "net/instaweb/util/public/function.h"
+#include "net/instaweb/util/public/scheduler.h"
+#include "net/instaweb/util/public/timer.h"
+
+namespace net_instaweb {
+
+// Helper returned by Scheduler::MakeDeleter, which signals the thread
+// to exit and joins on it.
+class SchedulerThread::CleanupFunction : public Function {
+ public:
+  explicit CleanupFunction(SchedulerThread* parent) : parent_(parent) {}
+  virtual ~CleanupFunction() {}
+
+ protected:
+  virtual void Run() {
+    {
+      ScopedMutex lock(parent_->scheduler_->mutex());
+      parent_->quit_ = true;
+      parent_->scheduler_->Signal();
+    }
+    parent_->Join();
+    delete parent_;
+  }
+
+  virtual void Cancel() {
+    LOG(DFATAL) << "CleanupFunction does not expect to be cancelled";
+  }
+
+ private:
+  SchedulerThread* parent_;
+  DISALLOW_COPY_AND_ASSIGN(CleanupFunction);
+};
+
+SchedulerThread::SchedulerThread(ThreadSystem* thread_system,
+                                 Scheduler* scheduler)
+    : Thread(thread_system, ThreadSystem::kJoinable),
+      quit_(false),
+      scheduler_(scheduler) {}
+
+SchedulerThread::~SchedulerThread() {}
+
+Function* SchedulerThread::MakeDeleter() {
+  return new CleanupFunction(this);
+}
+
+void SchedulerThread::Run() {
+  ScopedMutex lock(scheduler_->mutex());
+  while (!quit_) {
+    scheduler_->ProcessAlarms(255 * Timer::kSecondUs);
+  }
+}
+
+}  // namespace net_instaweb

Added: httpd/mod_spdy/trunk/net/instaweb/util/scheduler_thread_test.cc
URL: http://svn.apache.org/viewvc/httpd/mod_spdy/trunk/net/instaweb/util/scheduler_thread_test.cc?rev=1591622&view=auto
==============================================================================
--- httpd/mod_spdy/trunk/net/instaweb/util/scheduler_thread_test.cc (added)
+++ httpd/mod_spdy/trunk/net/instaweb/util/scheduler_thread_test.cc Thu May  1 11:43:36 2014
@@ -0,0 +1,69 @@
+// 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)
+//
+// Unit tests for SchedulerThread
+
+#include "net/instaweb/util/public/scheduler_thread.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/google_timer.h"
+#include "net/instaweb/util/public/thread_system.h"
+#include "net/instaweb/util/public/scheduler.h"
+#include "net/instaweb/util/public/timer.h"
+#include "net/instaweb/util/worker_test_base.h"
+
+namespace net_instaweb {
+
+namespace {
+
+class SchedulerThreadTest : public WorkerTestBase {
+ protected:
+  SchedulerThreadTest()
+      : thread_system_(ThreadSystem::CreateThreadSystem()),
+        timer_(),
+        scheduler_(thread_system_.get(), &timer_),
+        scheduler_thread_(
+            new SchedulerThread(thread_system_.get(), &scheduler_)) {}
+
+  scoped_ptr<ThreadSystem> thread_system_;
+  GoogleTimer timer_;
+  Scheduler scheduler_;
+  SchedulerThread* scheduler_thread_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(SchedulerThreadTest);
+};
+
+TEST_F(SchedulerThreadTest, BasicOperation) {
+  // Make sure that the thread actually dispatches an event,
+  // and cleanups safely.
+  ASSERT_TRUE(scheduler_thread_->Start());
+  SyncPoint sync(thread_system_.get());
+  int64 start_us = timer_.NowUs();
+  scheduler_.AddAlarm(start_us + 25 * Timer::kMsUs,
+                      new NotifyRunFunction(&sync));
+  sync.Wait();
+  int64 end_us = timer_.NowUs();
+  EXPECT_LT(start_us + 24 * Timer::kMsUs, end_us);
+  EXPECT_GT(start_us + Timer::kMinuteUs, end_us);
+  scheduler_thread_->MakeDeleter()->CallRun();
+};
+
+}  // namespace
+
+}  // namespace net_instaweb