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