OLD | NEW |
| (Empty) |
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 | |
12 DnsQueue::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 | |
22 DnsQueue::~DnsQueue(void) { | |
23 } | |
24 | |
25 void 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. | |
35 DnsQueue::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. | |
105 bool 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 | |
145 bool 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 } | |
OLD | NEW |