1// Copyright (c) 2006-2008 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// See header file for description of DnsQueue class
6
7#include "chrome/renderer/net/predictor_queue.h"
8
9#include "base/logging.h"
10#include "base/metrics/stats_counters.h"
11
12DnsQueue::DnsQueue(BufferSize size)
13    : buffer_(new char[size + 2]),
14      buffer_size_(size + 1),
15      buffer_sentinel_(size + 1),
16      size_(0) {
17  CHECK(0 < static_cast<BufferSize>(size + 3));  // Avoid overflow worries.
18  buffer_[buffer_sentinel_] = '\0';  // Guard byte to help reading data.
19  readable_ = writeable_ = 0;  // Buffer starts empty.
20}
21
22DnsQueue::~DnsQueue(void) {
23}
24
25void DnsQueue::Clear() {
26  size_ = 0;
27  readable_ = writeable_;
28  DCHECK(Validate());
29}
30
31// Push takes an unterminated string plus its length.
32// The string must not contain a null terminator.
33// Exactly length chars are written, or nothing is written.
34// Returns true for success, false there was no room to push.
35DnsQueue::PushResult DnsQueue::Push(const char* source,
36                                    const size_t unsigned_length) {
37  BufferSize length = static_cast<BufferSize>(unsigned_length);
38  if (0 > length+1)  // Avoid overflows in conversion to signed.
39    return OVERFLOW_PUSH;
40
41  // To save on sites with a LOT of links to the SAME domain, we have a
42  // a compaction hack that removes duplicates when we try to push() a
43  // match with the last push.
44  if (0 < size_ && readable_ + length < buffer_sentinel_ &&
45    0 == strncmp(source, &buffer_[readable_], unsigned_length) &&
46    '\0' == buffer_[readable_ + unsigned_length]) {
47    SIMPLE_STATS_COUNTER("DNS.PrefetchDnsRedundantPush");
48
49    // We already wrote this name to the queue, so we'll skip this repeat.
50    return REDUNDANT_PUSH;
51  }
52
53  // Calling convention precludes nulls.
54  DCHECK(!length || '\0' != source[length - 1]);
55
56  DCHECK(Validate());
57
58  BufferSize available_space = readable_ - writeable_;
59
60  if (0 >= available_space) {
61    available_space += buffer_size_;
62  }
63
64  if (length + 1 >= available_space) {
65    SIMPLE_STATS_COUNTER("DNS.PrefetchDnsQueueFull");
66    return OVERFLOW_PUSH;  // Not enough space to push.
67  }
68
69  BufferSize dest = writeable_;
70  BufferSize space_till_wrap = buffer_sentinel_ - dest;
71  if (space_till_wrap < length + 1) {
72    // Copy until we run out of room at end of buffer.
73    std::memcpy(&buffer_[dest], source, space_till_wrap);
74    // Ensure caller didn't have embedded '\0' and also
75    // ensure trailing sentinel was in place.
76    // Relies on sentinel.
77    DCHECK(static_cast<size_t>(space_till_wrap) == strlen(&buffer_[dest]));
78
79    length -= space_till_wrap;
80    source += space_till_wrap;
81    dest = 0;  // Continue writing at start of buffer.
82  }
83
84  // Copy any remaining portion of source.
85  std::memcpy(&buffer_[dest], source, length);
86  DCHECK(dest + length < buffer_sentinel_);
87  buffer_[dest + length] = '\0';  // We need termination in our buffer.
88  // Preclude embedded '\0'.
89  DCHECK(static_cast<size_t>(length) == strlen(&buffer_[dest]));
90
91  dest += length + 1;
92  if (dest == buffer_sentinel_)
93    dest = 0;
94
95  writeable_ = dest;
96  size_++;
97  DCHECK(Validate());
98  return SUCCESSFUL_PUSH;
99}
100
101// Extracts the next available string from the buffer.
102// The returned string is null terminated, and hence has length
103// that is exactly one greater than the written string.
104// If the buffer is empty, then the Pop and returns false.
105bool DnsQueue::Pop(std::string* out_string) {
106  DCHECK(Validate());
107  // Sentinel will preclude memory reads beyond buffer's end.
108  DCHECK('\0' == buffer_[buffer_sentinel_]);
109
110  if (readable_ == writeable_) {
111    return false;  // buffer was empty
112  }
113
114  // Constructor *may* rely on sentinel for null termination.
115  (*out_string) = &buffer_[readable_];
116  // Our sentinel_ at end of buffer precludes an overflow in cast.
117  BufferSize first_fragment_size = static_cast<BufferSize> (out_string->size());
118
119  BufferSize terminal_null;
120  if (readable_ + first_fragment_size >= buffer_sentinel_) {
121    // Sentinel was used, so we need the portion after the wrap.
122    out_string->append(&buffer_[0]);  // Fragment at start of buffer.
123    // Sentinel precludes overflow in cast to signed type.
124    terminal_null = static_cast<BufferSize>(out_string->size())
125                    - first_fragment_size;
126  } else {
127    terminal_null = readable_ + first_fragment_size;
128  }
129  DCHECK('\0' == buffer_[terminal_null]);
130
131  BufferSize new_readable = terminal_null + 1;
132  if (buffer_sentinel_ == new_readable)
133    new_readable = 0;
134
135  readable_ = new_readable;
136  size_--;
137  if (readable_ == writeable_ || 0 == size_) {
138    // Queue is empty, so reset to start of buffer to help with peeking.
139    readable_ = writeable_ = 0;
140  }
141  DCHECK(Validate());
142  return true;
143}
144
145bool DnsQueue::Validate() {
146  return (readable_ >= 0) &&
147          readable_ < buffer_sentinel_ &&
148          writeable_ >= 0 &&
149          writeable_ < buffer_sentinel_ &&
150          '\0' == buffer_[buffer_sentinel_] &&
151          ((0 == size_) == (readable_ == writeable_));
152}
153