chrome/renderer/net/predictor_queue.cc

   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 }