1// Copyright (c) 2010 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include <sstream>
6
7#include "chrome/renderer/net/predictor_queue.h"
8#include "testing/gtest/include/gtest/gtest.h"
9
10// Single threaded tests of DnsQueue functionality.
11
12namespace {
13
14class DnsQueueTest : public testing::Test {
15};
16
17// Define a helper class that does Push'es and Pop's of numbers.
18// This makes it easy to test a LOT of reads, and keep the expected Pop
19// value in sync with the Push value.
20class DnsQueueSequentialTester {
21 public:
22  DnsQueueSequentialTester(DnsQueue& buffer, int32 read_counter = 0,
23                           int32 write_counter = 0);
24
25  // Return of false means buffer was full, or would not take entry.
26  bool Push(void);  // Push the string value of next number.
27
28  // Return of false means buffer returned wrong value.
29  bool Pop(void);  // Validate string value of next read.
30
31 private:
32  DnsQueue* buffer_;
33  int32 read_counter_;  // expected value of next read string.
34  int32 write_counter_;  // Numerical value to write next string.
35  DISALLOW_COPY_AND_ASSIGN(DnsQueueSequentialTester);
36};
37
38
39DnsQueueSequentialTester::DnsQueueSequentialTester(
40  DnsQueue& buffer, int32 read_counter, int32 write_counter)
41    : buffer_(&buffer),
42      read_counter_(read_counter),
43      write_counter_(write_counter) {
44}
45
46bool DnsQueueSequentialTester::Push(void) {
47  std::ostringstream value;
48  value << write_counter_;
49
50  // Exercise both write methods intermittently.
51  DnsQueue::PushResult result = (write_counter_ % 2) ?
52       buffer_->Push(value.str().c_str(), value.str().size()) :
53       buffer_->Push(value.str());
54  if (DnsQueue::SUCCESSFUL_PUSH == result)
55    write_counter_++;
56  return DnsQueue::OVERFLOW_PUSH != result;
57}
58
59bool DnsQueueSequentialTester::Pop(void) {
60  std::string string;
61  if (buffer_->Pop(&string)) {
62    std::ostringstream expected_value;
63    expected_value << read_counter_++;
64    EXPECT_STREQ(expected_value.str().c_str(), string.c_str())
65        << "Pop did not match write for value " << read_counter_;
66    return true;
67  }
68  return false;
69}
70
71
72TEST(DnsQueueTest, BufferUseCheck) {
73  // Use a small buffer so we can see that we can't write a string as soon as it
74  // gets longer than one less than the buffer size.  The extra empty character
75  // is used to keep read and write pointers from overlapping when buffer is
76  // full.  This shows the buffer size can constrain writes (and we're not
77  // scribbling all over memory).
78  const int buffer_size = 3;  // Just room for 2 digts plus '\0' plus blank.
79  std::string string;
80  DnsQueue buffer(buffer_size);
81  DnsQueueSequentialTester tester(buffer);
82
83  EXPECT_FALSE(tester.Pop()) << "Pop from empty buffer succeeded";
84
85  int i;
86  for (i = 0; i < 102; i++) {
87    if (!tester.Push())
88      break;  // String was too large.
89    EXPECT_TRUE(tester.Pop()) << "Unable to read back data " << i;
90    EXPECT_FALSE(buffer.Pop(&string))
91                << "read from empty buffer not flagged";
92  }
93
94  EXPECT_GE(i, 100) << "Can't write 2 digit strings in 4 character buffer";
95  EXPECT_LT(i, 101) << "We wrote 3 digit strings into a 4 character buffer";
96}
97
98TEST(DnsQueueTest, SubstringUseCheck) {
99  // Verify that only substring is written/read.
100  const int buffer_size = 100;
101  const char big_string[] = "123456789";
102  std::string string;
103  DnsQueue buffer(buffer_size);
104
105  EXPECT_FALSE(buffer.Pop(&string)) << "Initial buffer not empty";
106
107  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push(big_string, 3))
108      << "Can't write string";
109  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push(big_string, 0))
110      << "Can't write null string";
111  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push(big_string, 5))
112      << "Can't write string";
113
114  EXPECT_TRUE(buffer.Pop(&string)) << "Filled buffer marked as empty";
115  EXPECT_STREQ(string.c_str(), "123") << "Can't read actual data";
116  EXPECT_TRUE(buffer.Pop(&string)) << "Filled buffer marked as empty";
117  EXPECT_STREQ(string.c_str(), "") << "Can't read null string";
118  EXPECT_TRUE(buffer.Pop(&string)) << "Filled buffer marked as empty";
119  EXPECT_STREQ(string.c_str(), "12345") << "Can't read actual data";
120
121  EXPECT_FALSE(buffer.Pop(&string))
122              << "read from empty buffer not flagged";
123}
124
125TEST(DnsQueueTest, SizeCheck) {
126  // Verify that size is correctly accounted for in buffer.
127  const int buffer_size = 100;
128  std::string input_string = "Hello";
129  std::string string;
130  DnsQueue buffer(buffer_size);
131
132  EXPECT_EQ(0U, buffer.Size());
133  EXPECT_FALSE(buffer.Pop(&string));
134  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push(input_string));
135  EXPECT_EQ(1U, buffer.Size());
136  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push("Hi There"));
137  EXPECT_EQ(2U, buffer.Size());
138  EXPECT_TRUE(buffer.Pop(&string));
139  EXPECT_EQ(1U, buffer.Size());
140  EXPECT_TRUE(buffer.Pop(&string));
141  EXPECT_EQ(0U, buffer.Size());
142  EXPECT_EQ(DnsQueue::SUCCESSFUL_PUSH, buffer.Push(input_string));
143  EXPECT_EQ(1U, buffer.Size());
144
145  // Check to see that the first string, if repeated, is discarded.
146  EXPECT_EQ(DnsQueue::REDUNDANT_PUSH, buffer.Push(input_string));
147  EXPECT_EQ(1U, buffer.Size());
148}
149
150TEST(DnsQueueTest, FillThenEmptyCheck) {
151  // Use a big buffer so we'll get a bunch of writes in.
152  // This tests to be sure the buffer holds many strings.
153  // We also make sure they all come out intact.
154  const size_t buffer_size = 1000;
155  size_t byte_usage_counter = 1;  // Separation character between pointer.
156  DnsQueue buffer(buffer_size);
157  DnsQueueSequentialTester tester(buffer);
158
159  size_t write_success;
160  for (write_success = 0; write_success < buffer_size; write_success++) {
161    if (!tester.Push())
162      break;
163    EXPECT_EQ(buffer.Size(), write_success + 1);
164    if (write_success > 99)
165      byte_usage_counter += 4;  // 3 digit plus '\0'.
166    else if (write_success > 9)
167      byte_usage_counter += 3;  // 2 digits plus '\0'.
168    else
169      byte_usage_counter += 2;  // Digit plus '\0'.
170  }
171  EXPECT_LE(byte_usage_counter, buffer_size)
172      << "Written data exceeded buffer size";
173  EXPECT_GE(byte_usage_counter, buffer_size - 4)
174      << "Buffer does not appear to have filled";
175
176  EXPECT_GE(write_success, 10U) << "Couldn't even write 10 one digit strings "
177      "in " << buffer_size << " byte buffer";
178
179
180  while (1) {
181    if (!tester.Pop())
182      break;
183    write_success--;
184  }
185  EXPECT_EQ(write_success, 0U) << "Push and Pop count were different";
186
187  EXPECT_FALSE(tester.Pop()) << "Read from empty buffer succeeded";
188}
189
190TEST(DnsQueueTest, ClearCheck) {
191  // Use a big buffer so we'll get a bunch of writes in.
192  const size_t buffer_size = 1000;
193  DnsQueue buffer(buffer_size);
194  std::string string("ABC");
195  DnsQueueSequentialTester tester(buffer);
196
197  size_t write_success;
198  for (write_success = 0; write_success < buffer_size; write_success++) {
199    if (!tester.Push())
200      break;
201    EXPECT_EQ(buffer.Size(), write_success + 1);
202  }
203
204  buffer.Clear();
205  EXPECT_EQ(buffer.Size(), 0U);
206
207  size_t write_success2;
208  for (write_success2 = 0; write_success2 < buffer_size; write_success2++) {
209    if (!tester.Push())
210      break;
211    EXPECT_EQ(buffer.Size(), write_success2 + 1);
212  }
213
214  for (; write_success2 > 0; write_success2--) {
215    EXPECT_EQ(buffer.Size(), write_success2);
216    EXPECT_TRUE(buffer.Pop(&string));
217  }
218
219  EXPECT_EQ(buffer.Size(), 0U);
220  buffer.Clear();
221  EXPECT_EQ(buffer.Size(), 0U);
222}
223
224TEST(DnsQueueTest, WrapOnVariousSubstrings) {
225  // Use a prime number for the allocated buffer size so that we tend
226  // to exercise all possible edge conditions (in circular text buffer).
227  // Once we're over 10 writes, all our strings are 2 digits long,
228  // with a '\0' terminator added making 3 characters per write.
229  // Since 3 is relatively prime to 23, we'll soon wrap (about
230  // every 6 writes).  Hence after 18 writes, we'll have tested all
231  // edge conditions.  We'll first do this where we empty the buffer
232  // after each write, and then again where there are some strings
233  // still in the buffer after each write.
234  const int prime_number = 23;
235  // Circular buffer needs an extra extra space to distinguish full from empty.
236  const int buffer_size = prime_number - 1;
237  DnsQueue buffer(buffer_size);
238  DnsQueueSequentialTester tester(buffer);
239
240  // First test empties between each write. Second loop
241  // has writes for each pop.  Third has three pushes per pop.
242  // Third has two items pending during each write.
243  for (int j = 0; j < 3; j++) {
244    // Each group does 30 tests, which is more than 10+18
245    // which was needed to get into the thorough testing zone
246    // mentioned above.
247    for (int i = 0; i < 30; i++) {
248      EXPECT_TRUE(tester.Push()) << "write failed with only " << j
249                                    << " blocks in buffer";
250      EXPECT_TRUE(tester.Pop()) << "Unable to read back data ";
251    }
252    EXPECT_TRUE(tester.Push());
253  }
254
255  // Read back the accumulated 3 extra blocks.
256  EXPECT_TRUE(tester.Pop());
257  EXPECT_TRUE(tester.Pop());
258  EXPECT_TRUE(tester.Pop());
259  EXPECT_FALSE(tester.Pop());
260}
261
262};  // namespace
263