/* * * Copyright 2015 gRPC authors. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * */ #include #include "src/core/ext/transport/chttp2/transport/hpack_parser.h" #include #include #include #include "absl/strings/str_cat.h" #include "absl/strings/str_format.h" #include #include #include "src/core/ext/transport/chttp2/transport/bin_encoder.h" #include "src/core/ext/transport/chttp2/transport/internal.h" #include "src/core/lib/debug/stats.h" #include "src/core/lib/gpr/string.h" #include "src/core/lib/gprpp/match.h" #include "src/core/lib/profiling/timers.h" #include "src/core/lib/slice/slice_internal.h" #include "src/core/lib/slice/slice_string_helpers.h" #include "src/core/lib/surface/validate_metadata.h" #include "src/core/lib/transport/http2_errors.h" #if __cplusplus > 201103L #define GRPC_HPACK_CONSTEXPR_FN constexpr #define GRPC_HPACK_CONSTEXPR_VALUE constexpr #else #define GRPC_HPACK_CONSTEXPR_FN #define GRPC_HPACK_CONSTEXPR_VALUE const #endif namespace grpc_core { TraceFlag grpc_trace_chttp2_hpack_parser(false, "chttp2_hpack_parser"); /* state table for huffman decoding: given a state, gives an index/16 into next_sub_tbl. Taking that index and adding the value of the nibble being considered returns the next state. generated by gen_hpack_tables.c */ static const uint8_t next_tbl[256] = { 0, 1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 3, 3, 9, 10, 11, 1, 1, 1, 12, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 14, 1, 15, 16, 1, 17, 1, 15, 2, 7, 3, 18, 19, 1, 1, 1, 1, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 15, 2, 2, 7, 21, 1, 22, 1, 1, 1, 1, 1, 1, 1, 1, 15, 2, 2, 2, 2, 2, 2, 23, 24, 25, 1, 1, 1, 1, 2, 2, 2, 26, 3, 3, 27, 10, 28, 1, 1, 1, 1, 1, 1, 2, 3, 29, 10, 30, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 31, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 32, 1, 1, 15, 33, 1, 34, 35, 9, 36, 1, 1, 1, 1, 1, 1, 1, 37, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 26, 9, 38, 1, 1, 1, 1, 1, 1, 1, 15, 2, 2, 2, 2, 26, 3, 3, 39, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 7, 3, 3, 3, 40, 2, 41, 1, 1, 1, 42, 43, 1, 1, 44, 1, 1, 1, 1, 15, 2, 2, 2, 2, 2, 2, 3, 3, 3, 45, 46, 1, 1, 2, 2, 2, 35, 3, 3, 18, 47, 2, }; /* next state, based upon current state and the current nibble: see above. generated by gen_hpack_tables.c */ static const int16_t next_sub_tbl[48 * 16] = { 1, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 2, 6, 10, 13, 14, 15, 16, 17, 2, 6, 10, 13, 14, 15, 16, 17, 3, 7, 11, 24, 3, 7, 11, 24, 3, 7, 11, 24, 3, 7, 11, 24, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 199, 200, 201, 202, 203, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 3, 7, 11, 24, 3, 7, 11, 24, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 132, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18, 19, 20, 21, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 22, 23, 91, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 3, 7, 11, 24, 3, 7, 11, 24, 0, 0, 0, 0, 0, 41, 42, 43, 2, 6, 10, 13, 14, 15, 16, 17, 3, 7, 11, 24, 3, 7, 11, 24, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 44, 45, 2, 6, 10, 13, 14, 15, 16, 17, 46, 47, 48, 49, 50, 51, 52, 57, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 53, 54, 55, 56, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 74, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 73, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 3, 7, 11, 24, 3, 7, 11, 24, 3, 7, 11, 24, 0, 0, 0, 0, 3, 7, 11, 24, 3, 7, 11, 24, 4, 8, 4, 8, 0, 0, 0, 92, 0, 0, 0, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 3, 7, 11, 24, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 2, 6, 10, 13, 14, 15, 16, 17, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 148, 149, 150, 151, 3, 7, 11, 24, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 152, 153, 3, 7, 11, 24, 3, 7, 11, 24, 3, 7, 11, 24, 154, 155, 156, 164, 3, 7, 11, 24, 3, 7, 11, 24, 3, 7, 11, 24, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 157, 158, 159, 160, 161, 162, 163, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 197, 198, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 219, 220, 3, 7, 11, 24, 4, 8, 4, 8, 4, 8, 0, 0, 221, 222, 223, 224, 3, 7, 11, 24, 3, 7, 11, 24, 4, 8, 4, 8, 4, 8, 225, 228, 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 226, 227, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, }; /* emission table: indexed like next_tbl, ultimately gives the byte to be emitted, or -1 for no byte, or 256 for end of stream generated by gen_hpack_tables.c */ static const uint16_t emit_tbl[256] = { 0, 1, 2, 3, 4, 5, 6, 7, 0, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 0, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 0, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 0, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 0, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 0, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 0, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, }; /* generated by gen_hpack_tables.c */ static const int16_t emit_sub_tbl[249 * 16] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 48, 48, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49, 49, 49, 49, 49, 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 97, 97, 97, 97, 48, 48, 49, 49, 50, 50, 97, 97, 99, 99, 101, 101, 105, 105, 111, 111, 48, 49, 50, 97, 99, 101, 105, 111, 115, 116, -1, -1, -1, -1, -1, -1, 32, 32, 32, 32, 32, 32, 32, 32, 37, 37, 37, 37, 37, 37, 37, 37, 99, 99, 99, 99, 101, 101, 101, 101, 105, 105, 105, 105, 111, 111, 111, 111, 115, 115, 116, 116, 32, 37, 45, 46, 47, 51, 52, 53, 54, 55, 56, 57, 61, 61, 61, 61, 61, 61, 61, 61, 65, 65, 65, 65, 65, 65, 65, 65, 115, 115, 115, 115, 116, 116, 116, 116, 32, 32, 37, 37, 45, 45, 46, 46, 61, 65, 95, 98, 100, 102, 103, 104, 108, 109, 110, 112, 114, 117, -1, -1, 58, 58, 58, 58, 58, 58, 58, 58, 66, 66, 66, 66, 66, 66, 66, 66, 47, 47, 51, 51, 52, 52, 53, 53, 54, 54, 55, 55, 56, 56, 57, 57, 61, 61, 65, 65, 95, 95, 98, 98, 100, 100, 102, 102, 103, 103, 104, 104, 108, 108, 109, 109, 110, 110, 112, 112, 114, 114, 117, 117, 58, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 89, 106, 107, 113, 118, 119, 120, 121, 122, -1, -1, -1, -1, 38, 38, 38, 38, 38, 38, 38, 38, 42, 42, 42, 42, 42, 42, 42, 42, 44, 44, 44, 44, 44, 44, 44, 44, 59, 59, 59, 59, 59, 59, 59, 59, 88, 88, 88, 88, 88, 88, 88, 88, 90, 90, 90, 90, 90, 90, 90, 90, 33, 33, 34, 34, 40, 40, 41, 41, 63, 63, 39, 43, 124, -1, -1, -1, 35, 35, 35, 35, 35, 35, 35, 35, 62, 62, 62, 62, 62, 62, 62, 62, 0, 0, 0, 0, 36, 36, 36, 36, 64, 64, 64, 64, 91, 91, 91, 91, 69, 69, 69, 69, 69, 69, 69, 69, 70, 70, 70, 70, 70, 70, 70, 70, 71, 71, 71, 71, 71, 71, 71, 71, 72, 72, 72, 72, 72, 72, 72, 72, 73, 73, 73, 73, 73, 73, 73, 73, 74, 74, 74, 74, 74, 74, 74, 74, 75, 75, 75, 75, 75, 75, 75, 75, 76, 76, 76, 76, 76, 76, 76, 76, 77, 77, 77, 77, 77, 77, 77, 77, 78, 78, 78, 78, 78, 78, 78, 78, 79, 79, 79, 79, 79, 79, 79, 79, 80, 80, 80, 80, 80, 80, 80, 80, 81, 81, 81, 81, 81, 81, 81, 81, 82, 82, 82, 82, 82, 82, 82, 82, 83, 83, 83, 83, 83, 83, 83, 83, 84, 84, 84, 84, 84, 84, 84, 84, 85, 85, 85, 85, 85, 85, 85, 85, 86, 86, 86, 86, 86, 86, 86, 86, 87, 87, 87, 87, 87, 87, 87, 87, 89, 89, 89, 89, 89, 89, 89, 89, 106, 106, 106, 106, 106, 106, 106, 106, 107, 107, 107, 107, 107, 107, 107, 107, 113, 113, 113, 113, 113, 113, 113, 113, 118, 118, 118, 118, 118, 118, 118, 118, 119, 119, 119, 119, 119, 119, 119, 119, 120, 120, 120, 120, 120, 120, 120, 120, 121, 121, 121, 121, 121, 121, 121, 121, 122, 122, 122, 122, 122, 122, 122, 122, 38, 38, 38, 38, 42, 42, 42, 42, 44, 44, 44, 44, 59, 59, 59, 59, 88, 88, 88, 88, 90, 90, 90, 90, 33, 34, 40, 41, 63, -1, -1, -1, 39, 39, 39, 39, 39, 39, 39, 39, 43, 43, 43, 43, 43, 43, 43, 43, 124, 124, 124, 124, 124, 124, 124, 124, 35, 35, 35, 35, 62, 62, 62, 62, 0, 0, 36, 36, 64, 64, 91, 91, 93, 93, 126, 126, 94, 125, -1, -1, 60, 60, 60, 60, 60, 60, 60, 60, 96, 96, 96, 96, 96, 96, 96, 96, 123, 123, 123, 123, 123, 123, 123, 123, -1, -1, -1, -1, -1, -1, -1, -1, 92, 92, 92, 92, 92, 92, 92, 92, 195, 195, 195, 195, 195, 195, 195, 195, 208, 208, 208, 208, 208, 208, 208, 208, 128, 128, 128, 128, 130, 130, 130, 130, 131, 131, 131, 131, 162, 162, 162, 162, 184, 184, 184, 184, 194, 194, 194, 194, 224, 224, 224, 224, 226, 226, 226, 226, 153, 153, 161, 161, 167, 167, 172, 172, 176, 176, 177, 177, 179, 179, 209, 209, 216, 216, 217, 217, 227, 227, 229, 229, 230, 230, 129, 132, 133, 134, 136, 146, 154, 156, 160, 163, 164, 169, 170, 173, 178, 181, 185, 186, 187, 189, 190, 196, 198, 228, 232, 233, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 135, 135, 135, 135, 135, 135, 135, 135, 137, 137, 137, 137, 137, 137, 137, 137, 138, 138, 138, 138, 138, 138, 138, 138, 139, 139, 139, 139, 139, 139, 139, 139, 140, 140, 140, 140, 140, 140, 140, 140, 141, 141, 141, 141, 141, 141, 141, 141, 143, 143, 143, 143, 143, 143, 143, 143, 147, 147, 147, 147, 147, 147, 147, 147, 149, 149, 149, 149, 149, 149, 149, 149, 150, 150, 150, 150, 150, 150, 150, 150, 151, 151, 151, 151, 151, 151, 151, 151, 152, 152, 152, 152, 152, 152, 152, 152, 155, 155, 155, 155, 155, 155, 155, 155, 157, 157, 157, 157, 157, 157, 157, 157, 158, 158, 158, 158, 158, 158, 158, 158, 165, 165, 165, 165, 165, 165, 165, 165, 166, 166, 166, 166, 166, 166, 166, 166, 168, 168, 168, 168, 168, 168, 168, 168, 174, 174, 174, 174, 174, 174, 174, 174, 175, 175, 175, 175, 175, 175, 175, 175, 180, 180, 180, 180, 180, 180, 180, 180, 182, 182, 182, 182, 182, 182, 182, 182, 183, 183, 183, 183, 183, 183, 183, 183, 188, 188, 188, 188, 188, 188, 188, 188, 191, 191, 191, 191, 191, 191, 191, 191, 197, 197, 197, 197, 197, 197, 197, 197, 231, 231, 231, 231, 231, 231, 231, 231, 239, 239, 239, 239, 239, 239, 239, 239, 9, 9, 9, 9, 142, 142, 142, 142, 144, 144, 144, 144, 145, 145, 145, 145, 148, 148, 148, 148, 159, 159, 159, 159, 171, 171, 171, 171, 206, 206, 206, 206, 215, 215, 215, 215, 225, 225, 225, 225, 236, 236, 236, 236, 237, 237, 237, 237, 199, 199, 207, 207, 234, 234, 235, 235, 192, 193, 200, 201, 202, 205, 210, 213, 218, 219, 238, 240, 242, 243, 255, -1, 203, 203, 203, 203, 203, 203, 203, 203, 204, 204, 204, 204, 204, 204, 204, 204, 211, 211, 211, 211, 211, 211, 211, 211, 212, 212, 212, 212, 212, 212, 212, 212, 214, 214, 214, 214, 214, 214, 214, 214, 221, 221, 221, 221, 221, 221, 221, 221, 222, 222, 222, 222, 222, 222, 222, 222, 223, 223, 223, 223, 223, 223, 223, 223, 241, 241, 241, 241, 241, 241, 241, 241, 244, 244, 244, 244, 244, 244, 244, 244, 245, 245, 245, 245, 245, 245, 245, 245, 246, 246, 246, 246, 246, 246, 246, 246, 247, 247, 247, 247, 247, 247, 247, 247, 248, 248, 248, 248, 248, 248, 248, 248, 250, 250, 250, 250, 250, 250, 250, 250, 251, 251, 251, 251, 251, 251, 251, 251, 252, 252, 252, 252, 252, 252, 252, 252, 253, 253, 253, 253, 253, 253, 253, 253, 254, 254, 254, 254, 254, 254, 254, 254, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 11, 11, 11, 11, 12, 12, 12, 12, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31, 127, 127, 127, 127, 220, 220, 220, 220, 249, 249, 249, 249, 10, 13, 22, 256, 93, 93, 93, 93, 126, 126, 126, 126, 94, 94, 125, 125, 60, 96, 123, -1, 92, 195, 208, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 128, 128, 128, 128, 128, 128, 128, 128, 130, 130, 130, 130, 130, 130, 130, 130, 131, 131, 131, 131, 131, 131, 131, 131, 162, 162, 162, 162, 162, 162, 162, 162, 184, 184, 184, 184, 184, 184, 184, 184, 194, 194, 194, 194, 194, 194, 194, 194, 224, 224, 224, 224, 224, 224, 224, 224, 226, 226, 226, 226, 226, 226, 226, 226, 153, 153, 153, 153, 161, 161, 161, 161, 167, 167, 167, 167, 172, 172, 172, 172, 176, 176, 176, 176, 177, 177, 177, 177, 179, 179, 179, 179, 209, 209, 209, 209, 216, 216, 216, 216, 217, 217, 217, 217, 227, 227, 227, 227, 229, 229, 229, 229, 230, 230, 230, 230, 129, 129, 132, 132, 133, 133, 134, 134, 136, 136, 146, 146, 154, 154, 156, 156, 160, 160, 163, 163, 164, 164, 169, 169, 170, 170, 173, 173, 178, 178, 181, 181, 185, 185, 186, 186, 187, 187, 189, 189, 190, 190, 196, 196, 198, 198, 228, 228, 232, 232, 233, 233, 1, 135, 137, 138, 139, 140, 141, 143, 147, 149, 150, 151, 152, 155, 157, 158, 165, 166, 168, 174, 175, 180, 182, 183, 188, 191, 197, 231, 239, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 9, 9, 9, 9, 9, 9, 9, 142, 142, 142, 142, 142, 142, 142, 142, 144, 144, 144, 144, 144, 144, 144, 144, 145, 145, 145, 145, 145, 145, 145, 145, 148, 148, 148, 148, 148, 148, 148, 148, 159, 159, 159, 159, 159, 159, 159, 159, 171, 171, 171, 171, 171, 171, 171, 171, 206, 206, 206, 206, 206, 206, 206, 206, 215, 215, 215, 215, 215, 215, 215, 215, 225, 225, 225, 225, 225, 225, 225, 225, 236, 236, 236, 236, 236, 236, 236, 236, 237, 237, 237, 237, 237, 237, 237, 237, 199, 199, 199, 199, 207, 207, 207, 207, 234, 234, 234, 234, 235, 235, 235, 235, 192, 192, 193, 193, 200, 200, 201, 201, 202, 202, 205, 205, 210, 210, 213, 213, 218, 218, 219, 219, 238, 238, 240, 240, 242, 242, 243, 243, 255, 255, 203, 204, 211, 212, 214, 221, 222, 223, 241, 244, 245, 246, 247, 248, 250, 251, 252, 253, 254, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 127, 127, 127, 127, 127, 127, 127, 127, 220, 220, 220, 220, 220, 220, 220, 220, 249, 249, 249, 249, 249, 249, 249, 249, 10, 10, 13, 13, 22, 22, 256, 256, 67, 67, 67, 67, 67, 67, 67, 67, 68, 68, 68, 68, 68, 68, 68, 68, 95, 95, 95, 95, 95, 95, 95, 95, 98, 98, 98, 98, 98, 98, 98, 98, 100, 100, 100, 100, 100, 100, 100, 100, 102, 102, 102, 102, 102, 102, 102, 102, 103, 103, 103, 103, 103, 103, 103, 103, 104, 104, 104, 104, 104, 104, 104, 104, 108, 108, 108, 108, 108, 108, 108, 108, 109, 109, 109, 109, 109, 109, 109, 109, 110, 110, 110, 110, 110, 110, 110, 110, 112, 112, 112, 112, 112, 112, 112, 112, 114, 114, 114, 114, 114, 114, 114, 114, 117, 117, 117, 117, 117, 117, 117, 117, 58, 58, 58, 58, 66, 66, 66, 66, 67, 67, 67, 67, 68, 68, 68, 68, 69, 69, 69, 69, 70, 70, 70, 70, 71, 71, 71, 71, 72, 72, 72, 72, 73, 73, 73, 73, 74, 74, 74, 74, 75, 75, 75, 75, 76, 76, 76, 76, 77, 77, 77, 77, 78, 78, 78, 78, 79, 79, 79, 79, 80, 80, 80, 80, 81, 81, 81, 81, 82, 82, 82, 82, 83, 83, 83, 83, 84, 84, 84, 84, 85, 85, 85, 85, 86, 86, 86, 86, 87, 87, 87, 87, 89, 89, 89, 89, 106, 106, 106, 106, 107, 107, 107, 107, 113, 113, 113, 113, 118, 118, 118, 118, 119, 119, 119, 119, 120, 120, 120, 120, 121, 121, 121, 121, 122, 122, 122, 122, 38, 38, 42, 42, 44, 44, 59, 59, 88, 88, 90, 90, -1, -1, -1, -1, 33, 33, 33, 33, 33, 33, 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, 40, 40, 40, 40, 40, 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 63, 63, 63, 63, 63, 63, 63, 63, 39, 39, 39, 39, 43, 43, 43, 43, 124, 124, 124, 124, 35, 35, 62, 62, 0, 36, 64, 91, 93, 126, -1, -1, 94, 94, 94, 94, 94, 94, 94, 94, 125, 125, 125, 125, 125, 125, 125, 125, 60, 60, 60, 60, 96, 96, 96, 96, 123, 123, 123, 123, -1, -1, -1, -1, 92, 92, 92, 92, 195, 195, 195, 195, 208, 208, 208, 208, 128, 128, 130, 130, 131, 131, 162, 162, 184, 184, 194, 194, 224, 224, 226, 226, 153, 161, 167, 172, 176, 177, 179, 209, 216, 217, 227, 229, 230, -1, -1, -1, -1, -1, -1, -1, 129, 129, 129, 129, 129, 129, 129, 129, 132, 132, 132, 132, 132, 132, 132, 132, 133, 133, 133, 133, 133, 133, 133, 133, 134, 134, 134, 134, 134, 134, 134, 134, 136, 136, 136, 136, 136, 136, 136, 136, 146, 146, 146, 146, 146, 146, 146, 146, 154, 154, 154, 154, 154, 154, 154, 154, 156, 156, 156, 156, 156, 156, 156, 156, 160, 160, 160, 160, 160, 160, 160, 160, 163, 163, 163, 163, 163, 163, 163, 163, 164, 164, 164, 164, 164, 164, 164, 164, 169, 169, 169, 169, 169, 169, 169, 169, 170, 170, 170, 170, 170, 170, 170, 170, 173, 173, 173, 173, 173, 173, 173, 173, 178, 178, 178, 178, 178, 178, 178, 178, 181, 181, 181, 181, 181, 181, 181, 181, 185, 185, 185, 185, 185, 185, 185, 185, 186, 186, 186, 186, 186, 186, 186, 186, 187, 187, 187, 187, 187, 187, 187, 187, 189, 189, 189, 189, 189, 189, 189, 189, 190, 190, 190, 190, 190, 190, 190, 190, 196, 196, 196, 196, 196, 196, 196, 196, 198, 198, 198, 198, 198, 198, 198, 198, 228, 228, 228, 228, 228, 228, 228, 228, 232, 232, 232, 232, 232, 232, 232, 232, 233, 233, 233, 233, 233, 233, 233, 233, 1, 1, 1, 1, 135, 135, 135, 135, 137, 137, 137, 137, 138, 138, 138, 138, 139, 139, 139, 139, 140, 140, 140, 140, 141, 141, 141, 141, 143, 143, 143, 143, 147, 147, 147, 147, 149, 149, 149, 149, 150, 150, 150, 150, 151, 151, 151, 151, 152, 152, 152, 152, 155, 155, 155, 155, 157, 157, 157, 157, 158, 158, 158, 158, 165, 165, 165, 165, 166, 166, 166, 166, 168, 168, 168, 168, 174, 174, 174, 174, 175, 175, 175, 175, 180, 180, 180, 180, 182, 182, 182, 182, 183, 183, 183, 183, 188, 188, 188, 188, 191, 191, 191, 191, 197, 197, 197, 197, 231, 231, 231, 231, 239, 239, 239, 239, 9, 9, 142, 142, 144, 144, 145, 145, 148, 148, 159, 159, 171, 171, 206, 206, 215, 215, 225, 225, 236, 236, 237, 237, 199, 207, 234, 235, 192, 192, 192, 192, 192, 192, 192, 192, 193, 193, 193, 193, 193, 193, 193, 193, 200, 200, 200, 200, 200, 200, 200, 200, 201, 201, 201, 201, 201, 201, 201, 201, 202, 202, 202, 202, 202, 202, 202, 202, 205, 205, 205, 205, 205, 205, 205, 205, 210, 210, 210, 210, 210, 210, 210, 210, 213, 213, 213, 213, 213, 213, 213, 213, 218, 218, 218, 218, 218, 218, 218, 218, 219, 219, 219, 219, 219, 219, 219, 219, 238, 238, 238, 238, 238, 238, 238, 238, 240, 240, 240, 240, 240, 240, 240, 240, 242, 242, 242, 242, 242, 242, 242, 242, 243, 243, 243, 243, 243, 243, 243, 243, 255, 255, 255, 255, 255, 255, 255, 255, 203, 203, 203, 203, 204, 204, 204, 204, 211, 211, 211, 211, 212, 212, 212, 212, 214, 214, 214, 214, 221, 221, 221, 221, 222, 222, 222, 222, 223, 223, 223, 223, 241, 241, 241, 241, 244, 244, 244, 244, 245, 245, 245, 245, 246, 246, 246, 246, 247, 247, 247, 247, 248, 248, 248, 248, 250, 250, 250, 250, 251, 251, 251, 251, 252, 252, 252, 252, 253, 253, 253, 253, 254, 254, 254, 254, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 11, 11, 12, 12, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 127, 127, 220, 220, 249, 249, -1, -1, 10, 10, 10, 10, 10, 10, 10, 10, 13, 13, 13, 13, 13, 13, 13, 13, 22, 22, 22, 22, 22, 22, 22, 22, 256, 256, 256, 256, 256, 256, 256, 256, 45, 45, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 46, 46, 46, 46, 47, 47, 47, 47, 47, 47, 47, 47, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 53, 53, 53, 53, 53, 53, 54, 54, 54, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57, 57, 50, 50, 50, 50, 50, 50, 50, 50, 97, 97, 97, 97, 97, 97, 97, 97, 99, 99, 99, 99, 99, 99, 99, 99, 101, 101, 101, 101, 101, 101, 101, 101, 105, 105, 105, 105, 105, 105, 105, 105, 111, 111, 111, 111, 111, 111, 111, 111, 115, 115, 115, 115, 115, 115, 115, 115, 116, 116, 116, 116, 116, 116, 116, 116, 32, 32, 32, 32, 37, 37, 37, 37, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, 51, 51, 51, 51, 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55, 56, 56, 56, 56, 57, 57, 57, 57, 61, 61, 61, 61, 65, 65, 65, 65, 95, 95, 95, 95, 98, 98, 98, 98, 100, 100, 100, 100, 102, 102, 102, 102, 103, 103, 103, 103, 104, 104, 104, 104, 108, 108, 108, 108, 109, 109, 109, 109, 110, 110, 110, 110, 112, 112, 112, 112, 114, 114, 114, 114, 117, 117, 117, 117, 58, 58, 66, 66, 67, 67, 68, 68, 69, 69, 70, 70, 71, 71, 72, 72, 73, 73, 74, 74, 75, 75, 76, 76, 77, 77, 78, 78, 79, 79, 80, 80, 81, 81, 82, 82, 83, 83, 84, 84, 85, 85, 86, 86, 87, 87, 89, 89, 106, 106, 107, 107, 113, 113, 118, 118, 119, 119, 120, 120, 121, 121, 122, 122, 38, 42, 44, 59, 88, 90, -1, -1, 33, 33, 33, 33, 34, 34, 34, 34, 40, 40, 40, 40, 41, 41, 41, 41, 63, 63, 63, 63, 39, 39, 43, 43, 124, 124, 35, 62, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 36, 36, 36, 36, 36, 36, 36, 36, 64, 64, 64, 64, 64, 64, 64, 64, 91, 91, 91, 91, 91, 91, 91, 91, 93, 93, 93, 93, 93, 93, 93, 93, 126, 126, 126, 126, 126, 126, 126, 126, 94, 94, 94, 94, 125, 125, 125, 125, 60, 60, 96, 96, 123, 123, -1, -1, 92, 92, 195, 195, 208, 208, 128, 130, 131, 162, 184, 194, 224, 226, -1, -1, 153, 153, 153, 153, 153, 153, 153, 153, 161, 161, 161, 161, 161, 161, 161, 161, 167, 167, 167, 167, 167, 167, 167, 167, 172, 172, 172, 172, 172, 172, 172, 172, 176, 176, 176, 176, 176, 176, 176, 176, 177, 177, 177, 177, 177, 177, 177, 177, 179, 179, 179, 179, 179, 179, 179, 179, 209, 209, 209, 209, 209, 209, 209, 209, 216, 216, 216, 216, 216, 216, 216, 216, 217, 217, 217, 217, 217, 217, 217, 217, 227, 227, 227, 227, 227, 227, 227, 227, 229, 229, 229, 229, 229, 229, 229, 229, 230, 230, 230, 230, 230, 230, 230, 230, 129, 129, 129, 129, 132, 132, 132, 132, 133, 133, 133, 133, 134, 134, 134, 134, 136, 136, 136, 136, 146, 146, 146, 146, 154, 154, 154, 154, 156, 156, 156, 156, 160, 160, 160, 160, 163, 163, 163, 163, 164, 164, 164, 164, 169, 169, 169, 169, 170, 170, 170, 170, 173, 173, 173, 173, 178, 178, 178, 178, 181, 181, 181, 181, 185, 185, 185, 185, 186, 186, 186, 186, 187, 187, 187, 187, 189, 189, 189, 189, 190, 190, 190, 190, 196, 196, 196, 196, 198, 198, 198, 198, 228, 228, 228, 228, 232, 232, 232, 232, 233, 233, 233, 233, 1, 1, 135, 135, 137, 137, 138, 138, 139, 139, 140, 140, 141, 141, 143, 143, 147, 147, 149, 149, 150, 150, 151, 151, 152, 152, 155, 155, 157, 157, 158, 158, 165, 165, 166, 166, 168, 168, 174, 174, 175, 175, 180, 180, 182, 182, 183, 183, 188, 188, 191, 191, 197, 197, 231, 231, 239, 239, 9, 142, 144, 145, 148, 159, 171, 206, 215, 225, 236, 237, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 199, 199, 199, 199, 199, 199, 199, 199, 207, 207, 207, 207, 207, 207, 207, 207, 234, 234, 234, 234, 234, 234, 234, 234, 235, 235, 235, 235, 235, 235, 235, 235, 192, 192, 192, 192, 193, 193, 193, 193, 200, 200, 200, 200, 201, 201, 201, 201, 202, 202, 202, 202, 205, 205, 205, 205, 210, 210, 210, 210, 213, 213, 213, 213, 218, 218, 218, 218, 219, 219, 219, 219, 238, 238, 238, 238, 240, 240, 240, 240, 242, 242, 242, 242, 243, 243, 243, 243, 255, 255, 255, 255, 203, 203, 204, 204, 211, 211, 212, 212, 214, 214, 221, 221, 222, 222, 223, 223, 241, 241, 244, 244, 245, 245, 246, 246, 247, 247, 248, 248, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 2, 3, 4, 5, 6, 7, 8, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 127, 220, 249, -1, 10, 10, 10, 10, 13, 13, 13, 13, 22, 22, 22, 22, 256, 256, 256, 256, }; namespace { // The alphabet used for base64 encoding binary metadata. static constexpr char kBase64Alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="; // An inverted table: for each value in kBase64Alphabet, table contains the // index with which it's stored, so we can quickly invert the encoding without // any complicated runtime logic. struct Base64InverseTable { uint8_t table[256]{}; GRPC_HPACK_CONSTEXPR_FN Base64InverseTable() { for (int i = 0; i < 256; i++) { table[i] = 255; } for (const char* p = kBase64Alphabet; *p; p++) { uint8_t idx = *p; uint8_t ofs = p - kBase64Alphabet; table[idx] = ofs; } } }; static GRPC_HPACK_CONSTEXPR_VALUE Base64InverseTable kBase64InverseTable; } // namespace // Input tracks the current byte through the input data and provides it // via a simple stream interface. class HPackParser::Input { public: Input(grpc_slice_refcount* current_slice_refcount, const uint8_t* begin, const uint8_t* end) : current_slice_refcount_(current_slice_refcount), begin_(begin), end_(end), frontier_(begin) {} // If input is backed by a slice, retrieve its refcount. If not, return // nullptr. grpc_slice_refcount* slice_refcount() { return current_slice_refcount_; } // Have we reached the end of input? bool end_of_stream() const { return begin_ == end_; } // How many bytes until end of input size_t remaining() const { return end_ - begin_; } // Current position, as a pointer const uint8_t* cur_ptr() const { return begin_; } // End position, as a pointer const uint8_t* end_ptr() const { return end_; } // Move read position forward by n, unchecked void Advance(size_t n) { begin_ += n; } // Retrieve the current character, or nullopt if end of stream // Do not advance absl::optional peek() const { if (end_of_stream()) { return {}; } return *begin_; } // Retrieve and advance past the current character, or return nullopt if end // of stream absl::optional Next() { if (end_of_stream()) { return UnexpectedEOF(absl::optional()); } return *begin_++; } // Helper to parse a varint delta on top of value, return nullopt on failure // (setting error) absl::optional ParseVarint(uint32_t value) { // TODO(ctiller): break out a variant of this when we know there are at // least 5 bytes in input_ auto cur = Next(); if (!cur) return {}; value += *cur & 0x7f; if ((*cur & 0x80) == 0) return value; cur = Next(); if (!cur) return {}; value += (*cur & 0x7f) << 7; if ((*cur & 0x80) == 0) return value; cur = Next(); if (!cur) return {}; value += (*cur & 0x7f) << 14; if ((*cur & 0x80) == 0) return value; cur = Next(); if (!cur) return {}; value += (*cur & 0x7f) << 21; if ((*cur & 0x80) == 0) return value; cur = Next(); if (!cur) return {}; uint32_t c = (*cur) & 0x7f; // We might overflow here, so we need to be a little careful about the // addition if (c > 0xf) return ParseVarintOutOfRange(value, *cur); const uint32_t add = c << 28; if (add > 0xffffffffu - value) { return ParseVarintOutOfRange(value, *cur); } value += add; if ((*cur & 0x80) == 0) return value; // Spec weirdness: we can add an infinite stream of 0x80 at the end of a // varint and still end up with a correctly encoded varint. do { cur = Next(); if (!cur.has_value()) return {}; } while (*cur == 0x80); // BUT... the last byte needs to be 0x00 or we'll overflow dramatically! if (*cur == 0) return value; return ParseVarintOutOfRange(value, *cur); } // Prefix for a string struct StringPrefix { // Number of bytes in input for string uint32_t length; // Is it huffman compressed bool huff; }; // Parse a string prefix absl::optional ParseStringPrefix() { auto cur = Next(); if (!cur.has_value()) return {}; // Huffman if the top bit is 1 const bool huff = (*cur & 0x80) != 0; // String length uint32_t strlen = (*cur & 0x7f); if (strlen == 0x7f) { // all ones ==> varint string length auto v = ParseVarint(0x7f); if (!v.has_value()) return {}; strlen = *v; } return StringPrefix{strlen, huff}; } // Check if we saw an EOF.. must be verified before looking at TakeError bool eof_error() const { return eof_error_; } // Extract the parse error, leaving the current error as NONE. grpc_error_handle TakeError() { grpc_error_handle out = error_; error_ = GRPC_ERROR_NONE; return out; } // Set the current error - allows the rest of the code not to need to pass // around StatusOr<> which would be prohibitive here. GPR_ATTRIBUTE_NOINLINE void SetError(grpc_error_handle error) { if (error_ != GRPC_ERROR_NONE || eof_error_) { GRPC_ERROR_UNREF(error); return; } error_ = error; begin_ = end_; } // If no error is set, set it to the value produced by error_factory. // Return return_value unchanged. template GPR_ATTRIBUTE_NOINLINE T MaybeSetErrorAndReturn(F error_factory, T return_value) { if (error_ != GRPC_ERROR_NONE || eof_error_) return return_value; error_ = error_factory(); begin_ = end_; return return_value; } // Set the error to an unexpected eof, and return result (code golfed as this // is a common case) template T UnexpectedEOF(T return_value) { if (error_ != GRPC_ERROR_NONE) return return_value; eof_error_ = true; return return_value; } // Update the frontier - signifies we've successfully parsed another element void UpdateFrontier() { frontier_ = begin_; } // Get the frontier - for buffering should we fail due to eof const uint8_t* frontier() const { return frontier_; } private: // Helper to set the error to out of range for ParseVarint absl::optional ParseVarintOutOfRange(uint32_t value, uint8_t last_byte) { return MaybeSetErrorAndReturn( [value, last_byte] { return GRPC_ERROR_CREATE_FROM_CPP_STRING(absl::StrFormat( "integer overflow in hpack integer decoding: have 0x%08x, " "got byte 0x%02x on byte 5", value, last_byte)); }, absl::optional()); } // Refcount if we are backed by a slice grpc_slice_refcount* current_slice_refcount_; // Current input point const uint8_t* begin_; // End of stream point const uint8_t* const end_; // Frontier denotes the first byte past successfully processed input const uint8_t* frontier_; // Current error grpc_error_handle error_ = GRPC_ERROR_NONE; // If the error was EOF, we flag it here.. bool eof_error_ = false; }; // Helper to parse a string and turn it into a slice with appropriate memory // management characteristics class HPackParser::String { public: // Helper to specify a string should be internalized struct Intern {}; // Helper to specify a string should be externalized struct Extern {}; private: // Forward declare take functions... we'll need them in the public interface UnmanagedMemorySlice Take(Extern); ManagedMemorySlice Take(Intern); public: // If a String is a Slice then unref ~String() { if (auto* p = absl::get_if(&value_)) { grpc_slice_unref_internal(*p); } } // Take the value and leave this empty // Use Intern/Extern to choose memory management template auto Take() -> decltype(this->Take(T())) { return Take(T()); } String(const String&) = delete; String& operator=(const String&) = delete; String(String&& other) noexcept : value_(std::move(other.value_)) { other.value_ = absl::Span(); } String& operator=(String&& other) noexcept { value_ = std::move(other.value_); other.value_ = absl::Span(); return *this; } // Parse a non-binary string static absl::optional Parse(Input* input) { auto pfx = input->ParseStringPrefix(); if (!pfx.has_value()) return {}; if (pfx->huff) { // Huffman coded std::vector output; auto v = ParseHuff(input, pfx->length, [&output](uint8_t c) { output.push_back(c); }); if (!v) return {}; return String(std::move(output)); } return ParseUncompressed(input, pfx->length); } // Parse a binary string static absl::optional ParseBinary(Input* input) { auto pfx = input->ParseStringPrefix(); if (!pfx.has_value()) return {}; if (!pfx->huff) { if (pfx->length > 0 && input->peek() == 0) { // 'true-binary' input->Advance(1); return ParseUncompressed(input, pfx->length - 1); } // Base64 encoded... pull out the string, then unbase64 it auto base64 = ParseUncompressed(input, pfx->length); if (!base64.has_value()) return {}; return Unbase64(input, std::move(*base64)); } else { // Huffman encoded... std::vector decompressed; // State here says either we don't know if it's base64 or binary, or we do // and what is it. enum class State { kUnsure, kBinary, kBase64 }; State state = State::kUnsure; auto decompressed_ok = ParseHuff(input, pfx->length, [&state, &decompressed](uint8_t c) { if (state == State::kUnsure) { // First byte... if it's zero it's binary if (c == 0) { // Save the type, and skip the zero state = State::kBinary; return; } else { // Flag base64, store this value state = State::kBase64; } } // Non-first byte, or base64 first byte decompressed.push_back(c); }); if (!decompressed_ok) return {}; switch (state) { case State::kUnsure: // No bytes, empty span return String(absl::Span()); case State::kBinary: // Binary, we're done return String(std::move(decompressed)); case State::kBase64: // Base64 - unpack it return Unbase64(input, String(std::move(decompressed))); } GPR_UNREACHABLE_CODE(abort();); } } private: void AppendBytes(const uint8_t* data, size_t length); explicit String(std::vector v) : value_(std::move(v)) {} explicit String(absl::Span v) : value_(v) {} String(grpc_slice_refcount* r, const uint8_t* begin, const uint8_t* end) : value_(MakeSlice(r, begin, end)) {} // Given a refcount and a byte range, make a slice static grpc_slice MakeSlice(grpc_slice_refcount* r, const uint8_t* begin, const uint8_t* end) { grpc_slice out; out.refcount = r; r->Ref(); out.data.refcounted.bytes = const_cast(begin); out.data.refcounted.length = end - begin; return out; } // Parse some huffman encoded bytes, using output(uint8_t b) to emit each // decoded byte. template static bool ParseHuff(Input* input, uint32_t length, Out output) { GRPC_STATS_INC_HPACK_RECV_HUFFMAN(); int16_t state = 0; // Parse one half byte... we leverage some lookup tables to keep the logic // here really simple. auto nibble = [&output, &state](uint8_t nibble) { int16_t emit = emit_sub_tbl[16 * emit_tbl[state] + nibble]; int16_t next = next_sub_tbl[16 * next_tbl[state] + nibble]; if (emit != -1) { if (emit >= 0 && emit < 256) { output(static_cast(emit)); } else { assert(emit == 256); } } state = next; }; // If there's insufficient bytes remaining, return now. if (input->remaining() < length) { return input->UnexpectedEOF(false); } // Grab the byte range, and iterate through it. const uint8_t* p = input->cur_ptr(); input->Advance(length); for (uint32_t i = 0; i < length; i++) { nibble(p[i] >> 4); nibble(p[i] & 0xf); } return true; } // Parse some uncompressed string bytes. static absl::optional ParseUncompressed(Input* input, uint32_t length) { GRPC_STATS_INC_HPACK_RECV_UNCOMPRESSED(); // Check there's enough bytes if (input->remaining() < length) { return input->UnexpectedEOF(absl::optional()); } auto* refcount = input->slice_refcount(); auto* p = input->cur_ptr(); input->Advance(length); if (refcount != nullptr) { return String(refcount, p, p + length); } else { return String(absl::Span(p, length)); } } // Turn base64 encoded bytes into not base64 encoded bytes. // Only takes input to set an error on failure. static absl::optional Unbase64(Input* input, String s) { auto v = Match( s.value_, [](const grpc_slice& slice) { return Unbase64Loop(GRPC_SLICE_START_PTR(slice), GRPC_SLICE_END_PTR(slice)); }, [](absl::Span span) { return Unbase64Loop(span.begin(), span.end()); }, [](const std::vector& vec) { return Unbase64Loop(vec.data(), vec.data() + vec.size()); }); if (!v.has_value()) { return input->MaybeSetErrorAndReturn( [] { return GRPC_ERROR_CREATE_FROM_STATIC_STRING( "illegal base64 encoding"); }, absl::optional()); } return String(std::move(*v)); } // Main loop for Unbase64 static absl::optional> Unbase64Loop(const uint8_t* cur, const uint8_t* end) { while (cur != end && end[-1] == '=') { --end; } std::vector out; out.reserve(3 * (end - cur) / 4 + 3); // Decode 4 bytes at a time while we can while (end - cur >= 4) { uint32_t bits = kBase64InverseTable.table[*cur]; if (bits > 63) return {}; uint32_t buffer = bits << 18; ++cur; bits = kBase64InverseTable.table[*cur]; if (bits > 63) return {}; buffer |= bits << 12; ++cur; bits = kBase64InverseTable.table[*cur]; if (bits > 63) return {}; buffer |= bits << 6; ++cur; bits = kBase64InverseTable.table[*cur]; if (bits > 63) return {}; buffer |= bits; ++cur; out.insert(out.end(), {static_cast(buffer >> 16), static_cast(buffer >> 8), static_cast(buffer)}); } // Deal with the last 0, 1, 2, or 3 bytes. switch (end - cur) { case 0: return out; case 1: return {}; case 2: { uint32_t bits = kBase64InverseTable.table[*cur]; if (bits > 63) return {}; uint32_t buffer = bits << 18; ++cur; bits = kBase64InverseTable.table[*cur]; if (bits > 63) return {}; buffer |= bits << 12; if (buffer & 0xffff) return {}; out.push_back(static_cast(buffer >> 16)); return out; } case 3: { uint32_t bits = kBase64InverseTable.table[*cur]; if (bits > 63) return {}; uint32_t buffer = bits << 18; ++cur; bits = kBase64InverseTable.table[*cur]; if (bits > 63) return {}; buffer |= bits << 12; ++cur; bits = kBase64InverseTable.table[*cur]; if (bits > 63) return {}; buffer |= bits << 6; ++cur; if (buffer & 0xff) return {}; out.push_back(static_cast(buffer >> 16)); out.push_back(static_cast(buffer >> 8)); return out; } } GPR_UNREACHABLE_CODE(return out;); } absl::variant, std::vector> value_; }; // Parser parses one key/value pair from a byte stream. class HPackParser::Parser { public: Parser(Input* input, grpc_metadata_batch* metadata_buffer, uint32_t metadata_size_limit, HPackTable* table, uint8_t* dynamic_table_updates_allowed, uint32_t* frame_length, LogInfo log_info) : input_(input), metadata_buffer_(metadata_buffer), table_(table), dynamic_table_updates_allowed_(dynamic_table_updates_allowed), frame_length_(frame_length), metadata_size_limit_(metadata_size_limit), log_info_(log_info) {} // Skip any priority bits, or return false on failure bool SkipPriority() { if (input_->remaining() < 5) return input_->UnexpectedEOF(false); input_->Advance(5); return true; } bool Parse() { auto cur = *input_->Next(); switch (cur >> 4) { // Literal header not indexed - First byte format: 0000xxxx // Literal header never indexed - First byte format: 0001xxxx // Where xxxx: // 0000 - literal key // 1111 - indexed key, varint encoded index // other - indexed key, inline encoded index case 0: case 1: switch (cur & 0xf) { case 0: // literal key return FinishHeaderOmitFromTable(ParseLiteralKey()); case 0xf: // varint encoded key index return FinishHeaderOmitFromTable( ParseVarIdxKey(0xf)); default: // inline encoded key index return FinishHeaderOmitFromTable( ParseIdxKey(cur & 0xf)); } // Update max table size. // First byte format: 001xxxxx // Where xxxxx: // 11111 - max size is varint encoded // other - max size is stored inline case 2: // inline encoded max table size return FinishMaxTableSize(cur & 0x1f); case 3: if (cur == 0x3f) { // varint encoded max table size return FinishMaxTableSize(input_->ParseVarint(0x1f)); } else { // inline encoded max table size return FinishMaxTableSize(cur & 0x1f); } // Literal header with incremental indexing. // First byte format: 01xxxxxx // Where xxxxxx: // 000000 - literal key // 111111 - indexed key, varint encoded index // other - indexed key, inline encoded index case 4: if (cur == 0x40) { // literal key return FinishHeaderAndAddToTable(ParseLiteralKey()); } ABSL_FALLTHROUGH_INTENDED; case 5: case 6: // inline encoded key index return FinishHeaderAndAddToTable( ParseIdxKey(cur & 0x3f)); case 7: if (cur == 0x7f) { // varint encoded key index return FinishHeaderAndAddToTable( ParseVarIdxKey(0x3f)); } else { // inline encoded key index return FinishHeaderAndAddToTable( ParseIdxKey(cur & 0x3f)); } // Indexed Header Field Representation // First byte format: 1xxxxxxx // Where xxxxxxx: // 0000000 - illegal // 1111111 - varint encoded field index // other - inline encoded field index case 8: if (cur == 0x80) { // illegal value. return input_->MaybeSetErrorAndReturn( [] { return GRPC_ERROR_CREATE_FROM_STATIC_STRING( "Illegal hpack op code"); }, false); } ABSL_FALLTHROUGH_INTENDED; case 9: case 10: case 11: case 12: case 13: case 14: // inline encoded field index return FinishIndexed(cur & 0x7f); case 15: if (cur == 0xff) { // varint encoded field index return FinishIndexed(input_->ParseVarint(0x7f)); } else { // inline encoded field index return FinishIndexed(cur & 0x7f); } } GPR_UNREACHABLE_CODE(abort()); } private: void GPR_ATTRIBUTE_NOINLINE LogHeader(const HPackTable::Memento& memento) { const char* type; switch (log_info_.type) { case LogInfo::kHeaders: type = "HDR"; break; case LogInfo::kTrailers: type = "TRL"; break; case LogInfo::kDontKnow: type = "???"; break; } gpr_log(GPR_DEBUG, "HTTP:%d:%s:%s: %s", log_info_.stream_id, type, log_info_.is_client ? "CLI" : "SVR", memento.DebugString().c_str()); } bool EmitHeader(const HPackTable::Memento& md) { // Pass up to the transport if (GPR_UNLIKELY(metadata_buffer_ == nullptr)) return true; *frame_length_ += md.transport_size(); if (GPR_UNLIKELY(*frame_length_ > metadata_size_limit_)) { return HandleMetadataSizeLimitExceeded(md); } grpc_error_handle err = metadata_buffer_->Set(md); if (GPR_UNLIKELY(err != GRPC_ERROR_NONE)) { input_->SetError(err); return false; } return true; } bool FinishHeaderAndAddToTable(absl::optional md) { // Allow higher code to just pass in failures ... simplifies things a bit. if (!md.has_value()) return false; // Log if desired if (GRPC_TRACE_FLAG_ENABLED(grpc_trace_chttp2_hpack_parser)) { LogHeader(*md); } // Emit whilst we own the metadata. auto r = EmitHeader(*md); // Add to the hpack table grpc_error_handle err = table_->Add(std::move(*md)); if (GPR_UNLIKELY(err != GRPC_ERROR_NONE)) { input_->SetError(err); return false; }; return r; } bool FinishHeaderOmitFromTable(absl::optional md) { // Allow higher code to just pass in failures ... simplifies things a bit. if (!md.has_value()) return false; return FinishHeaderOmitFromTable(*md); } bool FinishHeaderOmitFromTable(const HPackTable::Memento& md) { // Log if desired if (GRPC_TRACE_FLAG_ENABLED(grpc_trace_chttp2_hpack_parser)) { LogHeader(md); } return EmitHeader(md); } // Parse a string encoded key and a string encoded value template absl::optional ParseLiteralKey() { auto key = String::Parse(input_); if (!key.has_value()) return {}; auto key_slice = key->Take(); auto value = ParseValueString(grpc_is_refcounted_slice_binary_header(key_slice)); if (GPR_UNLIKELY(!value.has_value())) { grpc_slice_unref_internal(key_slice); return {}; } return grpc_metadata_batch::Parse(key_slice, value->Take()); } // Parse an index encoded key and a string encoded value template absl::optional ParseIdxKey(uint32_t index) { const auto* elem = table_->Lookup(index); if (GPR_UNLIKELY(elem == nullptr)) { return InvalidHPackIndexError(index, absl::optional()); } auto value = ParseValueString(elem->is_binary_header()); if (GPR_UNLIKELY(!value.has_value())) return {}; return elem->WithNewValue(value->Take()); } // Parse a varint index encoded key and a string encoded value template absl::optional ParseVarIdxKey(uint32_t offset) { auto index = input_->ParseVarint(offset); if (GPR_UNLIKELY(!index.has_value())) return {}; return ParseIdxKey(*index); } // Parse a string, figuring out if it's binary or not by the key name. absl::optional ParseValueString(bool is_binary) { if (is_binary) { return String::ParseBinary(input_); } else { return String::Parse(input_); } } // Emit an indexed field bool FinishIndexed(absl::optional index) { *dynamic_table_updates_allowed_ = 0; if (!index.has_value()) return false; const auto* elem = table_->Lookup(*index); if (GPR_UNLIKELY(elem == nullptr)) { return InvalidHPackIndexError(*index, false); } GRPC_STATS_INC_HPACK_RECV_INDEXED(); return FinishHeaderOmitFromTable(*elem); } // finish parsing a max table size change bool FinishMaxTableSize(absl::optional size) { if (!size.has_value()) return false; if (*dynamic_table_updates_allowed_ == 0) { return input_->MaybeSetErrorAndReturn( [] { return GRPC_ERROR_CREATE_FROM_STATIC_STRING( "More than two max table size changes in a single frame"); }, false); } (*dynamic_table_updates_allowed_)--; grpc_error_handle err = table_->SetCurrentTableSize(*size); if (err != GRPC_ERROR_NONE) { input_->SetError(err); return false; } return true; } // Set an invalid hpack index error if no error has been set. Returns result // unmodified. template R InvalidHPackIndexError(uint32_t index, R result) { return input_->MaybeSetErrorAndReturn( [this, index] { return grpc_error_set_int( grpc_error_set_int(GRPC_ERROR_CREATE_FROM_STATIC_STRING( "Invalid HPACK index received"), GRPC_ERROR_INT_INDEX, static_cast(index)), GRPC_ERROR_INT_SIZE, static_cast(this->table_->num_entries())); }, std::move(result)); } GPR_ATTRIBUTE_NOINLINE bool HandleMetadataSizeLimitExceeded(const HPackTable::Memento&) { gpr_log(GPR_DEBUG, "received initial metadata size exceeds limit (%" PRIu32 " vs. %" PRIu32 "). GRPC_ARG_MAX_METADATA_SIZE can be set to increase this limit.", *frame_length_, metadata_size_limit_); return input_->MaybeSetErrorAndReturn( [] { return grpc_error_set_int( GRPC_ERROR_CREATE_FROM_STATIC_STRING( "received initial metadata size exceeds limit"), GRPC_ERROR_INT_GRPC_STATUS, GRPC_STATUS_RESOURCE_EXHAUSTED); }, false); } Input* const input_; grpc_metadata_batch* const metadata_buffer_; HPackTable* const table_; uint8_t* const dynamic_table_updates_allowed_; uint32_t* const frame_length_; const uint32_t metadata_size_limit_; const LogInfo log_info_; }; UnmanagedMemorySlice HPackParser::String::Take(Extern) { auto s = Match( value_, [](const grpc_slice& slice) { // TODO(ctiller): Think about this before submission. GPR_DEBUG_ASSERT(!grpc_slice_is_interned(slice)); auto out_slice = grpc_slice_copy(slice); grpc_slice_unref_internal(slice); return static_cast(out_slice); }, [](absl::Span span) { return UnmanagedMemorySlice( reinterpret_cast(const_cast(span.begin())), span.size()); }, [](const std::vector& v) { return UnmanagedMemorySlice(reinterpret_cast(v.data()), v.size()); }); value_ = absl::Span(); return s; } ManagedMemorySlice HPackParser::String::Take(Intern) { auto s = Match( value_, [](const grpc_slice& slice) { ManagedMemorySlice s(&slice); grpc_slice_unref_internal(slice); return s; }, [](absl::Span span) { return ManagedMemorySlice( reinterpret_cast(const_cast(span.data())), span.size()); }, [](const std::vector& v) { return ManagedMemorySlice(reinterpret_cast(v.data()), v.size()); }); value_ = absl::Span(); return s; } /* PUBLIC INTERFACE */ HPackParser::HPackParser() = default; HPackParser::~HPackParser() = default; void HPackParser::BeginFrame(grpc_metadata_batch* metadata_buffer, uint32_t metadata_size_limit, Boundary boundary, Priority priority, LogInfo log_info) { metadata_buffer_ = metadata_buffer; boundary_ = boundary; priority_ = priority; dynamic_table_updates_allowed_ = 2; frame_length_ = 0; metadata_size_limit_ = metadata_size_limit; log_info_ = log_info; } grpc_error_handle HPackParser::Parse(const grpc_slice& slice, bool is_last) { if (GPR_UNLIKELY(!unparsed_bytes_.empty())) { std::vector buffer = std::move(unparsed_bytes_); buffer.insert(buffer.end(), GRPC_SLICE_START_PTR(slice), GRPC_SLICE_END_PTR(slice)); return ParseInput( Input(nullptr, buffer.data(), buffer.data() + buffer.size()), is_last); } return ParseInput(Input(slice.refcount, GRPC_SLICE_START_PTR(slice), GRPC_SLICE_END_PTR(slice)), is_last); } grpc_error_handle HPackParser::ParseInput(Input input, bool is_last) { if (ParseInputInner(&input)) { return GRPC_ERROR_NONE; } if (input.eof_error()) { if (GPR_UNLIKELY(is_last && is_boundary())) { return GRPC_ERROR_CREATE_FROM_STATIC_STRING( "Incomplete header at the end of a header/continuation sequence"); } unparsed_bytes_ = std::vector(input.frontier(), input.end_ptr()); return GRPC_ERROR_NONE; } return input.TakeError(); } bool HPackParser::ParseInputInner(Input* input) { switch (priority_) { case Priority::None: break; case Priority::Included: { if (input->remaining() < 5) return input->UnexpectedEOF(false); input->Advance(5); input->UpdateFrontier(); priority_ = Priority::None; } } while (!input->end_of_stream()) { if (GPR_UNLIKELY(!Parser(input, metadata_buffer_, metadata_size_limit_, &table_, &dynamic_table_updates_allowed_, &frame_length_, log_info_) .Parse())) { return false; } input->UpdateFrontier(); } return true; } void HPackParser::FinishFrame() { metadata_buffer_ = nullptr; } } // namespace grpc_core // TODO(ctiller): this serves as an eviction notice for the remainder of this // file... it belongs elsewhere! typedef void (*maybe_complete_func_type)(grpc_chttp2_transport* t, grpc_chttp2_stream* s); static const maybe_complete_func_type maybe_complete_funcs[] = { grpc_chttp2_maybe_complete_recv_initial_metadata, grpc_chttp2_maybe_complete_recv_trailing_metadata}; static void force_client_rst_stream(void* sp, grpc_error_handle /*error*/) { grpc_chttp2_stream* s = static_cast(sp); grpc_chttp2_transport* t = s->t; if (!s->write_closed) { grpc_chttp2_add_rst_stream_to_next_write(t, s->id, GRPC_HTTP2_NO_ERROR, &s->stats.outgoing); grpc_chttp2_initiate_write(t, GRPC_CHTTP2_INITIATE_WRITE_FORCE_RST_STREAM); grpc_chttp2_mark_stream_closed(t, s, true, true, GRPC_ERROR_NONE); } GRPC_CHTTP2_STREAM_UNREF(s, "final_rst"); } static void parse_stream_compression_md(grpc_chttp2_transport* /*t*/, grpc_chttp2_stream* s, grpc_metadata_batch* initial_metadata) { if (initial_metadata->legacy_index()->named.content_encoding == nullptr || grpc_stream_compression_method_parse( GRPC_MDVALUE( initial_metadata->legacy_index()->named.content_encoding->md), false, &s->stream_decompression_method) == 0) { s->stream_decompression_method = GRPC_STREAM_COMPRESSION_IDENTITY_DECOMPRESS; } if (s->stream_decompression_method != GRPC_STREAM_COMPRESSION_IDENTITY_DECOMPRESS) { s->stream_decompression_ctx = nullptr; grpc_slice_buffer_init(&s->decompressed_data_buffer); } } grpc_error_handle grpc_chttp2_header_parser_parse(void* hpack_parser, grpc_chttp2_transport* t, grpc_chttp2_stream* s, const grpc_slice& slice, int is_last) { GPR_TIMER_SCOPE("grpc_chttp2_header_parser_parse", 0); auto* parser = static_cast(hpack_parser); if (s != nullptr) { s->stats.incoming.header_bytes += GRPC_SLICE_LENGTH(slice); } grpc_error_handle error = parser->Parse(slice, is_last != 0); if (error != GRPC_ERROR_NONE) { return error; } if (is_last) { /* need to check for null stream: this can occur if we receive an invalid stream id on a header */ if (s != nullptr) { if (parser->is_boundary()) { if (s->header_frames_received == 2) { return GRPC_ERROR_CREATE_FROM_STATIC_STRING( "Too many trailer frames"); } /* Process stream compression md element if it exists */ if (s->header_frames_received == 0) { /* Only acts on initial metadata */ parse_stream_compression_md(t, s, &s->initial_metadata_buffer); } s->published_metadata[s->header_frames_received] = GRPC_METADATA_PUBLISHED_FROM_WIRE; maybe_complete_funcs[s->header_frames_received](t, s); s->header_frames_received++; } if (parser->is_eof()) { if (t->is_client && !s->write_closed) { /* server eof ==> complete closure; we may need to forcefully close the stream. Wait until the combiner lock is ready to be released however -- it might be that we receive a RST_STREAM following this and can avoid the extra write */ GRPC_CHTTP2_STREAM_REF(s, "final_rst"); t->combiner->FinallyRun( GRPC_CLOSURE_CREATE(force_client_rst_stream, s, nullptr), GRPC_ERROR_NONE); } grpc_chttp2_mark_stream_closed(t, s, true, false, GRPC_ERROR_NONE); } } parser->FinishFrame(); } return GRPC_ERROR_NONE; }