1 /* 2 * Copyright (c) Facebook, Inc. and its affiliates. 3 * All rights reserved. 4 * 5 * This source code is licensed under the BSD-style license found in the 6 * LICENSE file in the root directory of this source tree. 7 */ 8 9 #pragma once 10 11 #include <glog/logging.h> 12 13 #include <proxygen/lib/http/codec/compress/HPACKHeader.h> 14 #include <proxygen/lib/http/codec/compress/HeaderTable.h> 15 16 namespace proxygen { 17 18 /** 19 * Data structure for maintaining indexed headers, based on a fixed-length ring 20 * with FIFO semantics. Externally it acts as an array. 21 */ 22 23 class QPACKHeaderTable : public HeaderTable { 24 public: 25 enum { UNACKED = std::numeric_limits<uint32_t>::max() }; 26 27 QPACKHeaderTable(uint32_t capacityVal, bool trackReferences); 28 ~QPACKHeaderTable()29 ~QPACKHeaderTable() { 30 } 31 QPACKHeaderTable(const QPACKHeaderTable&) = delete; 32 QPACKHeaderTable& operator=(const QPACKHeaderTable&) = delete; 33 34 /** 35 * Returns true if the absolute index has not been ack'ed yet. 36 */ isVulnerable(uint32_t absIndex)37 bool isVulnerable(uint32_t absIndex) const { 38 return (absIndex > ackedInsertCount_); 39 } 40 41 /** 42 * Returns true if the header can be added to the table. May be linear 43 * in the number of entries 44 */ canIndex(const HPACKHeaderName & name,folly::StringPiece value)45 bool canIndex(const HPACKHeaderName& name, folly::StringPiece value) { 46 auto headerBytes = HPACKHeader::bytes(name.size(), value.size()); 47 auto totalBytes = bytes_ + headerBytes; 48 // Don't index headers that would immediately be drained 49 return ((headerBytes <= (capacity_ - minFree_)) && 50 (totalBytes <= capacity_ || canEvict(totalBytes - capacity_))); 51 } 52 53 /** 54 * Returns true if the index should not be used so table space can be freed 55 */ isDraining(uint32_t relativeIndex)56 bool isDraining(uint32_t relativeIndex) { 57 return relativeToAbsolute(relativeIndex) < minUsable_; 58 } 59 60 /** 61 * Returns the absolute index for a reference to the header at relativeIndex, 62 * along with a boolean indicating if the returned index is a duplicate. It 63 * may return 0 if the entry at relativeIndex was draining and could not be 64 * duplicated, or vulnerable references are not allowed. 65 */ 66 std::pair<bool, uint32_t> maybeDuplicate(uint32_t relativeIndex, 67 bool allowVulnerable); 68 69 /** 70 * Add the header entry at the beginning of the table (index=1) 71 * 72 * @return true if it was able to add the entry 73 */ 74 bool add(HPACKHeader header) override; 75 76 bool setCapacity(uint32_t capacity) override; 77 78 // This API is only for tests, and doesn't work correctly if the table is 79 // already populated. setMinFreeForTesting(uint32_t minFree)80 void setMinFreeForTesting(uint32_t minFree) { 81 minFree_ = minFree; 82 } 83 84 /** 85 * Get the index of the given header, if found. The index is relative to 86 * head/insertCount. If allowVulnerable is true, the index returned may not 87 * have been acknowledged by the decoder. 88 * 89 * @return 0 in case the header is not found 90 */ 91 uint32_t getIndex(const HPACKHeader& header, 92 bool allowVulnerable = true) const; 93 94 uint32_t getIndex(const HPACKHeaderName& name, 95 folly::StringPiece value, 96 bool allowVulnerable = true) const; 97 98 /** 99 * Get the table entry at the given external index. If base is 0, 100 * index is relative to head/insertCount. If base is non-zero, index is 101 * relative to base. 102 * 103 * @return the header entry 104 */ 105 const HPACKHeader& getHeader(uint32_t index, uint32_t base = 0) const; 106 107 /** 108 * Checks if an external index is valid. If base is 0, 109 * index is relative to head/insertCount. If base is non-zero, index is 110 * relative to base. 111 */ 112 bool isValid(uint32_t index, uint32_t base = 0) const; 113 114 /** 115 * Get any index of a header that has the given name. From all the 116 * headers with the given name we pick the last one added to the header 117 * table, but the way we pick the header can be arbitrary. 118 * 119 * See getIndex for a description of base/allowVulnerable 120 */ 121 uint32_t nameIndex(const HPACKHeaderName& headerName, 122 bool allowVulnerable = true) const; 123 onInsertCountIncrement(uint32_t numInserts)124 bool onInsertCountIncrement(uint32_t numInserts) { 125 // compare this way to avoid overflow 126 if (numInserts > insertCount_ || 127 ackedInsertCount_ > insertCount_ - numInserts) { 128 LOG(ERROR) 129 << "Decoder ack'd too much: ackedInsertCount_=" << ackedInsertCount_ 130 << " insertCount_=" << insertCount_ << " numInserts=" << numInserts; 131 return false; 132 } 133 ackedInsertCount_ += numInserts; 134 CHECK_LE(ackedInsertCount_, insertCount_); 135 return true; 136 } 137 setAcknowledgedInsertCount(uint32_t ackInsertCount)138 void setAcknowledgedInsertCount(uint32_t ackInsertCount) { 139 if (ackInsertCount < ackedInsertCount_) { 140 return; 141 } 142 CHECK_LE(ackInsertCount, insertCount_); 143 ackedInsertCount_ = ackInsertCount; 144 } 145 146 /** 147 * Convert a relative index to an absolute index 148 */ relativeToAbsolute(uint32_t relativeIndex)149 uint32_t relativeToAbsolute(uint32_t relativeIndex) const { 150 DCHECK(isValid(relativeIndex, 0)); 151 return insertCount_ - relativeIndex + 1; 152 } 153 154 /** 155 * Convert an absolute index to a relative index 156 */ absoluteToRelative(uint32_t absIndex)157 uint32_t absoluteToRelative(uint32_t absIndex) const { 158 CHECK_LE(absIndex, insertCount_); 159 return insertCount_ - absIndex + 1; 160 } 161 162 /** 163 * Add a reference for the given index. Entries with non-zero references 164 * cannot be evicted 165 */ 166 void addRef(uint32_t absIndex); 167 168 /** 169 * Subtract a reference for the given index 170 */ 171 void subRef(uint32_t absIndex); 172 173 private: 174 /* 175 * Shared implementation for getIndex and nameIndex 176 */ 177 uint32_t getIndexImpl(const HPACKHeaderName& header, 178 folly::StringPiece value, 179 bool nameOnly, 180 bool allowVulnerable = true) const; 181 182 /* 183 * Increase table length to newLength 184 */ 185 void increaseTableLengthTo(uint32_t newLength) override; 186 187 void resizeTable(uint32_t newLength) override; 188 189 void updateResizedTable(uint32_t oldTail, 190 uint32_t oldLength, 191 uint32_t newLength) override; 192 /** 193 * Removes one header entry from the beginning of the header table. 194 */ 195 uint32_t removeLast() override; 196 197 /** 198 * Return true if the table can evict needed bytes 199 */ 200 bool canEvict(uint32_t needed); 201 202 /** 203 * Evict entries to make space for the needed amount of bytes. 204 */ 205 uint32_t evict(uint32_t needed, uint32_t desiredCapacity) override; 206 207 /** 208 * Translate external index to internal one. 209 */ 210 uint32_t toInternal(uint32_t externalIndex, uint32_t base) const; 211 212 uint32_t internalToAbsolute(uint32_t internalIndex) const; 213 uint32_t absoluteToInternal(uint32_t absoluteIndex) const; 214 215 uint32_t drainedBytes_{0}; 216 uint32_t minUsable_{1}; 217 uint32_t ackedInsertCount_{0}; 218 uint32_t minFree_{0}; 219 std::unique_ptr<std::vector<uint16_t>> refCount_; 220 }; 221 222 } // namespace proxygen 223