net/spdy/write_blocked_list.h

   1 // Copyright 2013 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 #ifndef NET_SPDY_WRITE_BLOCKED_LIST_H_
   6 #define NET_SPDY_WRITE_BLOCKED_LIST_H_
   7
   8 #include <algorithm>
   9 #include <deque>
  10
  11 #include "base/containers/hash_tables.h"
  12 #include "base/logging.h"
  13 #include "net/spdy/spdy_protocol.h"
  14
  15 namespace {
  16 class WriteBlockedListPeer;
  17 }
  18
  19 namespace net {
  20
  21 const int kHighestPriority = 0;
  22 const int kLowestPriority = 7;
  23
  24 template <typename IdType>
  25 class WriteBlockedList {
  26  public:
  27   // 0(1) size lookup.  0(1) insert at front or back.
  28   typedef std::deque<IdType> BlockedList;
  29   typedef typename BlockedList::iterator iterator;
  30
  31   explicit WriteBlockedList(bool use_stream_to_priority_map)
  32       : use_stream_to_priority_(use_stream_to_priority_map) {}
  33
  34   static SpdyPriority ClampPriority(SpdyPriority priority) {
  35     if (priority < kHighestPriority) {
  36       LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority);
  37       return kHighestPriority;
  38     }
  39     if (priority > kLowestPriority) {
  40       LOG(DFATAL) << "Invalid priority: " << static_cast<int>(priority);
  41       return kLowestPriority;
  42     }
  43     return priority;
  44   }
  45
  46   // Returns the priority of the highest priority list with sessions on it.
  47   SpdyPriority GetHighestPriorityWriteBlockedList() const {
  48     for (SpdyPriority i = 0; i <= kLowestPriority; ++i) {
  49       if (write_blocked_lists_[i].size() > 0)
  50         return i;
  51     }
  52     LOG(DFATAL) << "No blocked streams";
  53     return kHighestPriority;
  54   }
  55
  56   IdType PopFront(SpdyPriority priority) {
  57     priority = ClampPriority(priority);
  58     DCHECK(!write_blocked_lists_[priority].empty());
  59     IdType stream_id = write_blocked_lists_[priority].front();
  60     write_blocked_lists_[priority].pop_front();
  61     if (use_stream_to_priority_) {
  62       stream_to_priority_.erase(stream_id);
  63     }
  64     return stream_id;
  65   }
  66
  67   bool HasWriteBlockedStreamsGreaterThanPriority(SpdyPriority priority) const {
  68     priority = ClampPriority(priority);
  69     for (SpdyPriority i = kHighestPriority; i < priority; ++i) {
  70       if (!write_blocked_lists_[i].empty()) {
  71         return true;
  72       }
  73     }
  74     return false;
  75   }
  76
  77   bool HasWriteBlockedStreams() const {
  78     for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) {
  79       if (!write_blocked_lists_[i].empty()) {
  80         return true;
  81       }
  82     }
  83     return false;
  84   }
  85
  86   void PushBack(IdType stream_id, SpdyPriority priority) {
  87     priority = ClampPriority(priority);
  88     DVLOG(2) << "Adding stream " << stream_id << " at priority "
  89              << static_cast<int>(priority);
  90     bool should_insert_stream = true;
  91     if (use_stream_to_priority_) {
  92       typename StreamToPriorityMap::iterator iter =
  93           stream_to_priority_.find(stream_id);
  94       if (iter != stream_to_priority_.end()) {
  95         DVLOG(1) << "Stream " << stream_id << " already in write blocked list.";
  96         if (iter->second == priority) {
  97           // The stream is already in the write blocked list for the priority.
  98           should_insert_stream = false;
  99         } else {
 100           // The stream is in a write blocked list for a different priority.
 101           bool removed =
 102               RemoveStreamFromWriteBlockedList(stream_id, iter->second);
 103           DCHECK(removed);
 104         }
 105       }
 106       if (should_insert_stream) {
 107         stream_to_priority_[stream_id] = priority;
 108         write_blocked_lists_[priority].push_back(stream_id);
 109       }
 110     } else {
 111       write_blocked_lists_[priority].push_back(stream_id);
 112     }
 113   }
 114
 115   bool RemoveStreamFromWriteBlockedList(IdType stream_id,
 116                                         SpdyPriority priority) {
 117     if (use_stream_to_priority_) {
 118       typename StreamToPriorityMap::iterator iter =
 119           stream_to_priority_.find(stream_id);
 120       if (iter == stream_to_priority_.end()) {
 121         // The stream is not present in the write blocked list.
 122         return false;
 123       } else if (iter->second == priority) {
 124         stream_to_priority_.erase(iter);
 125       } else {
 126         // The stream is not present at the specified priority level.
 127         return false;
 128       }
 129     }
 130     // We shouldn't really add a stream_id to a list multiple times,
 131     // but under some conditions it does happen. Doing a check in PushBack
 132     // would be too costly, so instead we check here to eliminate duplicates.
 133     bool found = false;
 134     iterator it = std::find(write_blocked_lists_[priority].begin(),
 135                             write_blocked_lists_[priority].end(), stream_id);
 136     while (it != write_blocked_lists_[priority].end()) {
 137       found = true;
 138       iterator next_it = write_blocked_lists_[priority].erase(it);
 139       it = std::find(next_it, write_blocked_lists_[priority].end(), stream_id);
 140     }
 141     return found;
 142   }
 143
 144   void UpdateStreamPriorityInWriteBlockedList(IdType stream_id,
 145                                               SpdyPriority old_priority,
 146                                               SpdyPriority new_priority) {
 147     if (old_priority == new_priority) {
 148       return;
 149     }
 150     bool found = RemoveStreamFromWriteBlockedList(stream_id, old_priority);
 151     if (found) {
 152       PushBack(stream_id, new_priority);
 153     }
 154   }
 155
 156   size_t NumBlockedStreams() const {
 157     size_t num_blocked_streams = 0;
 158     for (SpdyPriority i = kHighestPriority; i <= kLowestPriority; ++i) {
 159       num_blocked_streams += write_blocked_lists_[i].size();
 160     }
 161     return num_blocked_streams;
 162   }
 163
 164   bool avoids_inserting_duplicates() const { return use_stream_to_priority_; }
 165
 166  private:
 167   friend WriteBlockedListPeer;
 168
 169   typedef base::hash_map<IdType, SpdyPriority> StreamToPriorityMap;
 170
 171   BlockedList write_blocked_lists_[kLowestPriority + 1];
 172   StreamToPriorityMap stream_to_priority_;
 173   bool use_stream_to_priority_;
 174 };
 175
 176 }  // namespace net
 177
 178 #endif  // NET_SPDY_WRITE_BLOCKED_LIST_H_