1 /* 2 * Copyright (C) 2013 Square, Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 /* 17 * Forked from OkHttp 2.5.0 18 */ 19 20 package io.grpc.okhttp.internal.framed; 21 22 import java.io.IOException; 23 import java.util.ArrayList; 24 import java.util.Arrays; 25 import java.util.Collections; 26 import java.util.LinkedHashMap; 27 import java.util.List; 28 import java.util.Map; 29 30 import okio.Buffer; 31 import okio.BufferedSource; 32 import okio.ByteString; 33 import okio.Okio; 34 import okio.Source; 35 36 /** 37 * Read and write HPACK v10. 38 * 39 * http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-12 40 * 41 * This implementation uses an array for the dynamic table and a list for 42 * indexed entries. Dynamic entries are added to the array, starting in the 43 * last position moving forward. When the array fills, it is doubled. 44 */ 45 final class Hpack { 46 private static final int PREFIX_4_BITS = 0x0f; 47 private static final int PREFIX_5_BITS = 0x1f; 48 private static final int PREFIX_6_BITS = 0x3f; 49 private static final int PREFIX_7_BITS = 0x7f; 50 51 private static final io.grpc.okhttp.internal.framed.Header[] STATIC_HEADER_TABLE = new io.grpc.okhttp.internal.framed.Header[] { 52 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.TARGET_AUTHORITY, ""), 53 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.TARGET_METHOD, "GET"), 54 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.TARGET_METHOD, "POST"), 55 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.TARGET_PATH, "/"), 56 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.TARGET_PATH, "/index.html"), 57 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.TARGET_SCHEME, "http"), 58 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.TARGET_SCHEME, "https"), 59 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.RESPONSE_STATUS, "200"), 60 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.RESPONSE_STATUS, "204"), 61 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.RESPONSE_STATUS, "206"), 62 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.RESPONSE_STATUS, "304"), 63 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.RESPONSE_STATUS, "400"), 64 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.RESPONSE_STATUS, "404"), 65 new io.grpc.okhttp.internal.framed.Header(io.grpc.okhttp.internal.framed.Header.RESPONSE_STATUS, "500"), 66 new io.grpc.okhttp.internal.framed.Header("accept-charset", ""), 67 new io.grpc.okhttp.internal.framed.Header("accept-encoding", "gzip, deflate"), 68 new io.grpc.okhttp.internal.framed.Header("accept-language", ""), 69 new io.grpc.okhttp.internal.framed.Header("accept-ranges", ""), 70 new io.grpc.okhttp.internal.framed.Header("accept", ""), 71 new io.grpc.okhttp.internal.framed.Header("access-control-allow-origin", ""), 72 new io.grpc.okhttp.internal.framed.Header("age", ""), 73 new io.grpc.okhttp.internal.framed.Header("allow", ""), 74 new io.grpc.okhttp.internal.framed.Header("authorization", ""), 75 new io.grpc.okhttp.internal.framed.Header("cache-control", ""), 76 new io.grpc.okhttp.internal.framed.Header("content-disposition", ""), 77 new io.grpc.okhttp.internal.framed.Header("content-encoding", ""), 78 new io.grpc.okhttp.internal.framed.Header("content-language", ""), 79 new io.grpc.okhttp.internal.framed.Header("content-length", ""), 80 new io.grpc.okhttp.internal.framed.Header("content-location", ""), 81 new io.grpc.okhttp.internal.framed.Header("content-range", ""), 82 new io.grpc.okhttp.internal.framed.Header("content-type", ""), 83 new io.grpc.okhttp.internal.framed.Header("cookie", ""), 84 new io.grpc.okhttp.internal.framed.Header("date", ""), 85 new io.grpc.okhttp.internal.framed.Header("etag", ""), 86 new io.grpc.okhttp.internal.framed.Header("expect", ""), 87 new io.grpc.okhttp.internal.framed.Header("expires", ""), 88 new io.grpc.okhttp.internal.framed.Header("from", ""), 89 new io.grpc.okhttp.internal.framed.Header("host", ""), 90 new io.grpc.okhttp.internal.framed.Header("if-match", ""), 91 new io.grpc.okhttp.internal.framed.Header("if-modified-since", ""), 92 new io.grpc.okhttp.internal.framed.Header("if-none-match", ""), 93 new io.grpc.okhttp.internal.framed.Header("if-range", ""), 94 new io.grpc.okhttp.internal.framed.Header("if-unmodified-since", ""), 95 new io.grpc.okhttp.internal.framed.Header("last-modified", ""), 96 new io.grpc.okhttp.internal.framed.Header("link", ""), 97 new io.grpc.okhttp.internal.framed.Header("location", ""), 98 new io.grpc.okhttp.internal.framed.Header("max-forwards", ""), 99 new io.grpc.okhttp.internal.framed.Header("proxy-authenticate", ""), 100 new io.grpc.okhttp.internal.framed.Header("proxy-authorization", ""), 101 new io.grpc.okhttp.internal.framed.Header("range", ""), 102 new io.grpc.okhttp.internal.framed.Header("referer", ""), 103 new io.grpc.okhttp.internal.framed.Header("refresh", ""), 104 new io.grpc.okhttp.internal.framed.Header("retry-after", ""), 105 new io.grpc.okhttp.internal.framed.Header("server", ""), 106 new io.grpc.okhttp.internal.framed.Header("set-cookie", ""), 107 new io.grpc.okhttp.internal.framed.Header("strict-transport-security", ""), 108 new io.grpc.okhttp.internal.framed.Header("transfer-encoding", ""), 109 new io.grpc.okhttp.internal.framed.Header("user-agent", ""), 110 new io.grpc.okhttp.internal.framed.Header("vary", ""), 111 new io.grpc.okhttp.internal.framed.Header("via", ""), 112 new io.grpc.okhttp.internal.framed.Header("www-authenticate", "") 113 }; 114 Hpack()115 private Hpack() { 116 } 117 118 // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-12#section-3.1 119 static final class Reader { 120 121 private final List<io.grpc.okhttp.internal.framed.Header> headerList = new ArrayList<io.grpc.okhttp.internal.framed.Header>(); 122 private final BufferedSource source; 123 124 private int headerTableSizeSetting; 125 private int maxDynamicTableByteCount; 126 // Visible for testing. 127 io.grpc.okhttp.internal.framed.Header[] dynamicTable = new io.grpc.okhttp.internal.framed.Header[8]; 128 // Array is populated back to front, so new entries always have lowest index. 129 int nextDynamicTableIndex = dynamicTable.length - 1; 130 int dynamicTableHeaderCount = 0; 131 int dynamicTableByteCount = 0; 132 Reader(int headerTableSizeSetting, Source source)133 Reader(int headerTableSizeSetting, Source source) { 134 this.headerTableSizeSetting = headerTableSizeSetting; 135 this.maxDynamicTableByteCount = headerTableSizeSetting; 136 this.source = Okio.buffer(source); 137 } 138 maxDynamicTableByteCount()139 int maxDynamicTableByteCount() { 140 return maxDynamicTableByteCount; 141 } 142 143 /** 144 * Called by the reader when the peer sent {@link Settings#HEADER_TABLE_SIZE}. 145 * While this establishes the maximum dynamic table size, the 146 * {@link #maxDynamicTableByteCount} set during processing may limit the 147 * table size to a smaller amount. 148 * <p> Evicts entries or clears the table as needed. 149 */ headerTableSizeSetting(int headerTableSizeSetting)150 void headerTableSizeSetting(int headerTableSizeSetting) { 151 this.headerTableSizeSetting = headerTableSizeSetting; 152 this.maxDynamicTableByteCount = headerTableSizeSetting; 153 adjustDynamicTableByteCount(); 154 } 155 adjustDynamicTableByteCount()156 private void adjustDynamicTableByteCount() { 157 if (maxDynamicTableByteCount < dynamicTableByteCount) { 158 if (maxDynamicTableByteCount == 0) { 159 clearDynamicTable(); 160 } else { 161 evictToRecoverBytes(dynamicTableByteCount - maxDynamicTableByteCount); 162 } 163 } 164 } 165 clearDynamicTable()166 private void clearDynamicTable() { 167 Arrays.fill(dynamicTable, null); 168 nextDynamicTableIndex = dynamicTable.length - 1; 169 dynamicTableHeaderCount = 0; 170 dynamicTableByteCount = 0; 171 } 172 173 /** Returns the count of entries evicted. */ evictToRecoverBytes(int bytesToRecover)174 private int evictToRecoverBytes(int bytesToRecover) { 175 int entriesToEvict = 0; 176 if (bytesToRecover > 0) { 177 // determine how many headers need to be evicted. 178 for (int j = dynamicTable.length - 1; j >= nextDynamicTableIndex && bytesToRecover > 0; j--) { 179 bytesToRecover -= dynamicTable[j].hpackSize; 180 dynamicTableByteCount -= dynamicTable[j].hpackSize; 181 dynamicTableHeaderCount--; 182 entriesToEvict++; 183 } 184 System.arraycopy(dynamicTable, nextDynamicTableIndex + 1, dynamicTable, 185 nextDynamicTableIndex + 1 + entriesToEvict, dynamicTableHeaderCount); 186 nextDynamicTableIndex += entriesToEvict; 187 } 188 return entriesToEvict; 189 } 190 191 /** 192 * Read {@code byteCount} bytes of headers from the source stream. This 193 * implementation does not propagate the never indexed flag of a header. 194 */ readHeaders()195 void readHeaders() throws IOException { 196 while (!source.exhausted()) { 197 int b = source.readByte() & 0xff; 198 if (b == 0x80) { // 10000000 199 throw new IOException("index == 0"); 200 } else if ((b & 0x80) == 0x80) { // 1NNNNNNN 201 int index = readInt(b, PREFIX_7_BITS); 202 readIndexedHeader(index - 1); 203 } else if (b == 0x40) { // 01000000 204 readLiteralHeaderWithIncrementalIndexingNewName(); 205 } else if ((b & 0x40) == 0x40) { // 01NNNNNN 206 int index = readInt(b, PREFIX_6_BITS); 207 readLiteralHeaderWithIncrementalIndexingIndexedName(index - 1); 208 } else if ((b & 0x20) == 0x20) { // 001NNNNN 209 maxDynamicTableByteCount = readInt(b, PREFIX_5_BITS); 210 if (maxDynamicTableByteCount < 0 211 || maxDynamicTableByteCount > headerTableSizeSetting) { 212 throw new IOException("Invalid dynamic table size update " + maxDynamicTableByteCount); 213 } 214 adjustDynamicTableByteCount(); 215 } else if (b == 0x10 || b == 0) { // 000?0000 - Ignore never indexed bit. 216 readLiteralHeaderWithoutIndexingNewName(); 217 } else { // 000?NNNN - Ignore never indexed bit. 218 int index = readInt(b, PREFIX_4_BITS); 219 readLiteralHeaderWithoutIndexingIndexedName(index - 1); 220 } 221 } 222 } 223 getAndResetHeaderList()224 public List<io.grpc.okhttp.internal.framed.Header> getAndResetHeaderList() { 225 List<io.grpc.okhttp.internal.framed.Header> result = new ArrayList<io.grpc.okhttp.internal.framed.Header>(headerList); 226 headerList.clear(); 227 return result; 228 } 229 readIndexedHeader(int index)230 private void readIndexedHeader(int index) throws IOException { 231 if (isStaticHeader(index)) { 232 io.grpc.okhttp.internal.framed.Header staticEntry = STATIC_HEADER_TABLE[index]; 233 headerList.add(staticEntry); 234 } else { 235 int dynamicTableIndex = dynamicTableIndex(index - STATIC_HEADER_TABLE.length); 236 if (dynamicTableIndex < 0 || dynamicTableIndex > dynamicTable.length - 1) { 237 throw new IOException("Header index too large " + (index + 1)); 238 } 239 headerList.add(dynamicTable[dynamicTableIndex]); 240 } 241 } 242 243 // referencedHeaders is relative to nextDynamicTableIndex + 1. dynamicTableIndex(int index)244 private int dynamicTableIndex(int index) { 245 return nextDynamicTableIndex + 1 + index; 246 } 247 readLiteralHeaderWithoutIndexingIndexedName(int index)248 private void readLiteralHeaderWithoutIndexingIndexedName(int index) throws IOException { 249 ByteString name = getName(index); 250 ByteString value = readByteString(); 251 headerList.add(new io.grpc.okhttp.internal.framed.Header(name, value)); 252 } 253 readLiteralHeaderWithoutIndexingNewName()254 private void readLiteralHeaderWithoutIndexingNewName() throws IOException { 255 ByteString name = checkLowercase(readByteString()); 256 ByteString value = readByteString(); 257 headerList.add(new io.grpc.okhttp.internal.framed.Header(name, value)); 258 } 259 readLiteralHeaderWithIncrementalIndexingIndexedName(int nameIndex)260 private void readLiteralHeaderWithIncrementalIndexingIndexedName(int nameIndex) 261 throws IOException { 262 ByteString name = getName(nameIndex); 263 ByteString value = readByteString(); 264 insertIntoDynamicTable(-1, new io.grpc.okhttp.internal.framed.Header(name, value)); 265 } 266 readLiteralHeaderWithIncrementalIndexingNewName()267 private void readLiteralHeaderWithIncrementalIndexingNewName() throws IOException { 268 ByteString name = checkLowercase(readByteString()); 269 ByteString value = readByteString(); 270 insertIntoDynamicTable(-1, new io.grpc.okhttp.internal.framed.Header(name, value)); 271 } 272 getName(int index)273 private ByteString getName(int index) { 274 if (isStaticHeader(index)) { 275 return STATIC_HEADER_TABLE[index].name; 276 } else { 277 return dynamicTable[dynamicTableIndex(index - STATIC_HEADER_TABLE.length)].name; 278 } 279 } 280 isStaticHeader(int index)281 private boolean isStaticHeader(int index) { 282 return index >= 0 && index <= STATIC_HEADER_TABLE.length - 1; 283 } 284 285 /** index == -1 when new. */ insertIntoDynamicTable(int index, io.grpc.okhttp.internal.framed.Header entry)286 private void insertIntoDynamicTable(int index, io.grpc.okhttp.internal.framed.Header entry) { 287 headerList.add(entry); 288 289 int delta = entry.hpackSize; 290 if (index != -1) { // Index -1 == new header. 291 delta -= dynamicTable[dynamicTableIndex(index)].hpackSize; 292 } 293 294 // if the new or replacement header is too big, drop all entries. 295 if (delta > maxDynamicTableByteCount) { 296 clearDynamicTable(); 297 return; 298 } 299 300 // Evict headers to the required length. 301 int bytesToRecover = (dynamicTableByteCount + delta) - maxDynamicTableByteCount; 302 int entriesEvicted = evictToRecoverBytes(bytesToRecover); 303 304 if (index == -1) { // Adding a value to the dynamic table. 305 if (dynamicTableHeaderCount + 1 > dynamicTable.length) { // Need to grow the dynamic table. 306 io.grpc.okhttp.internal.framed.Header[] doubled = new io.grpc.okhttp.internal.framed.Header[dynamicTable.length * 2]; 307 System.arraycopy(dynamicTable, 0, doubled, dynamicTable.length, dynamicTable.length); 308 nextDynamicTableIndex = dynamicTable.length - 1; 309 dynamicTable = doubled; 310 } 311 index = nextDynamicTableIndex--; 312 dynamicTable[index] = entry; 313 dynamicTableHeaderCount++; 314 } else { // Replace value at same position. 315 index += dynamicTableIndex(index) + entriesEvicted; 316 dynamicTable[index] = entry; 317 } 318 dynamicTableByteCount += delta; 319 } 320 readByte()321 private int readByte() throws IOException { 322 return source.readByte() & 0xff; 323 } 324 readInt(int firstByte, int prefixMask)325 int readInt(int firstByte, int prefixMask) throws IOException { 326 int prefix = firstByte & prefixMask; 327 if (prefix < prefixMask) { 328 return prefix; // This was a single byte value. 329 } 330 331 // This is a multibyte value. Read 7 bits at a time. 332 int result = prefixMask; 333 int shift = 0; 334 while (true) { 335 int b = readByte(); 336 if ((b & 0x80) != 0) { // Equivalent to (b >= 128) since b is in [0..255]. 337 result += (b & 0x7f) << shift; 338 shift += 7; 339 } else { 340 result += b << shift; // Last byte. 341 break; 342 } 343 } 344 return result; 345 } 346 347 /** Reads a potentially Huffman encoded byte string. */ readByteString()348 ByteString readByteString() throws IOException { 349 int firstByte = readByte(); 350 boolean huffmanDecode = (firstByte & 0x80) == 0x80; // 1NNNNNNN 351 int length = readInt(firstByte, PREFIX_7_BITS); 352 353 if (huffmanDecode) { 354 return ByteString.of(io.grpc.okhttp.internal.framed.Huffman.get().decode(source.readByteArray(length))); 355 } else { 356 return source.readByteString(length); 357 } 358 } 359 } 360 361 private static final Map<ByteString, Integer> NAME_TO_FIRST_INDEX = nameToFirstIndex(); 362 nameToFirstIndex()363 private static Map<ByteString, Integer> nameToFirstIndex() { 364 Map<ByteString, Integer> result = 365 new LinkedHashMap<ByteString, Integer>(STATIC_HEADER_TABLE.length); 366 for (int i = 0; i < STATIC_HEADER_TABLE.length; i++) { 367 if (!result.containsKey(STATIC_HEADER_TABLE[i].name)) { 368 result.put(STATIC_HEADER_TABLE[i].name, i); 369 } 370 } 371 return Collections.unmodifiableMap(result); 372 } 373 374 static final class Writer { 375 private final Buffer out; 376 Writer(Buffer out)377 Writer(Buffer out) { 378 this.out = out; 379 } 380 381 /** This does not use "never indexed" semantics for sensitive headers. */ 382 // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-12#section-6.2.3 writeHeaders(List<io.grpc.okhttp.internal.framed.Header> headerBlock)383 void writeHeaders(List<io.grpc.okhttp.internal.framed.Header> headerBlock) throws IOException { 384 // TODO: implement index tracking 385 for (int i = 0, size = headerBlock.size(); i < size; i++) { 386 ByteString name = headerBlock.get(i).name.toAsciiLowercase(); 387 Integer staticIndex = NAME_TO_FIRST_INDEX.get(name); 388 if (staticIndex != null) { 389 // Literal Header Field without Indexing - Indexed Name. 390 writeInt(staticIndex + 1, PREFIX_4_BITS, 0); 391 writeByteString(headerBlock.get(i).value); 392 } else { 393 out.writeByte(0x00); // Literal Header without Indexing - New Name. 394 writeByteString(name); 395 writeByteString(headerBlock.get(i).value); 396 } 397 } 398 } 399 400 // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-12#section-4.1.1 writeInt(int value, int prefixMask, int bits)401 void writeInt(int value, int prefixMask, int bits) throws IOException { 402 // Write the raw value for a single byte value. 403 if (value < prefixMask) { 404 out.writeByte(bits | value); 405 return; 406 } 407 408 // Write the mask to start a multibyte value. 409 out.writeByte(bits | prefixMask); 410 value -= prefixMask; 411 412 // Write 7 bits at a time 'til we're done. 413 while (value >= 0x80) { 414 int b = value & 0x7f; 415 out.writeByte(b | 0x80); 416 value >>>= 7; 417 } 418 out.writeByte(value); 419 } 420 writeByteString(ByteString data)421 void writeByteString(ByteString data) throws IOException { 422 writeInt(data.size(), PREFIX_7_BITS, 0); 423 out.write(data); 424 } 425 } 426 427 /** 428 * An HTTP/2 response cannot contain uppercase header characters and must 429 * be treated as malformed. 430 */ checkLowercase(ByteString name)431 private static ByteString checkLowercase(ByteString name) throws IOException { 432 for (int i = 0, length = name.size(); i < length; i++) { 433 byte c = name.getByte(i); 434 if (c >= 'A' && c <= 'Z') { 435 throw new IOException("PROTOCOL_ERROR response malformed: mixed case name: " + name.utf8()); 436 } 437 } 438 return name; 439 } 440 } 441