Home | History | Annotate | Download | only in net 
      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 }
    153