/* * Copyright (c) 2009-2021, Google LLC * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * Neither the name of Google LLC nor the * names of its contributors may be used to endorse or promote products * derived from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY DIRECT, * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ // Fast decoder: ~3x the speed of decode.c, but requires x86-64/ARM64. // Also the table size grows by 2x. // // Could potentially be ported to other 64-bit archs that pass at least six // arguments in registers and have 8 unused high bits in pointers. // // The overall design is to create specialized functions for every possible // field type (eg. oneof boolean field with a 1 byte tag) and then dispatch // to the specialized function as quickly as possible. #include "upb/decode_fast.h" #include "upb/internal/decode.h" /* Must be last. */ #include "upb/port_def.inc" #if UPB_FASTTABLE // The standard set of arguments passed to each parsing function. // Thanks to x86-64 calling conventions, these will stay in registers. #define UPB_PARSE_PARAMS … #define UPB_PARSE_ARGS … #define RETURN_GENERIC … typedef enum { CARD_s = 0, /* Singular (optional, non-repeated) */ CARD_o = 1, /* Oneof */ CARD_r = 2, /* Repeated */ CARD_p = 3 /* Packed Repeated */ } upb_card; UPB_NOINLINE static const char* fastdecode_isdonefallback(UPB_PARSE_PARAMS) { int overrun = data; int status; ptr = decode_isdonefallback_inl(d, ptr, overrun, &status); if (ptr == NULL) { return fastdecode_err(d, status); } data = fastdecode_loadtag(ptr); UPB_MUSTTAIL return fastdecode_tagdispatch(UPB_PARSE_ARGS); } UPB_FORCEINLINE static const char* fastdecode_dispatch(UPB_PARSE_PARAMS) { if (UPB_UNLIKELY(ptr >= d->limit_ptr)) { int overrun = ptr - d->end; if (UPB_LIKELY(overrun == d->limit)) { // Parse is finished. *(uint32_t*)msg |= hasbits; // Sync hasbits. const upb_MiniTable* l = decode_totablep(table); return UPB_UNLIKELY(l->required_count) ? decode_checkrequired(d, ptr, msg, l) : ptr; } else { data = overrun; UPB_MUSTTAIL return fastdecode_isdonefallback(UPB_PARSE_ARGS); } } // Read two bytes of tag data (for a one-byte tag, the high byte is junk). data = fastdecode_loadtag(ptr); UPB_MUSTTAIL return fastdecode_tagdispatch(UPB_PARSE_ARGS); } UPB_FORCEINLINE static bool fastdecode_checktag(uint16_t data, int tagbytes) { if (tagbytes == 1) { return (data & 0xff) == 0; } else { return data == 0; } } UPB_FORCEINLINE static const char* fastdecode_longsize(const char* ptr, int* size) { int i; UPB_ASSERT(*size & 0x80); *size &= 0xff; for (i = 0; i < 3; i++) { ptr++; size_t byte = (uint8_t)ptr[-1]; *size += (byte - 1) << (7 + 7 * i); if (UPB_LIKELY((byte & 0x80) == 0)) return ptr; } ptr++; size_t byte = (uint8_t)ptr[-1]; // len is limited by 2gb not 4gb, hence 8 and not 16 as normally expected // for a 32 bit varint. if (UPB_UNLIKELY(byte >= 8)) return NULL; *size += (byte - 1) << 28; return ptr; } UPB_FORCEINLINE static bool fastdecode_boundscheck(const char* ptr, size_t len, const char* end) { uintptr_t uptr = (uintptr_t)ptr; uintptr_t uend = (uintptr_t)end + 16; uintptr_t res = uptr + len; return res < uptr || res > uend; } UPB_FORCEINLINE static bool fastdecode_boundscheck2(const char* ptr, size_t len, const char* end) { // This is one extra branch compared to the more normal: // return (size_t)(end - ptr) < size; // However it is one less computation if we are just about to use "ptr + len": // https://godbolt.org/z/35YGPz // In microbenchmarks this shows an overall 4% improvement. uintptr_t uptr = (uintptr_t)ptr; uintptr_t uend = (uintptr_t)end; uintptr_t res = uptr + len; return res < uptr || res > uend; } typedef const char* fastdecode_delimfunc(upb_Decoder* d, const char* ptr, void* ctx); UPB_FORCEINLINE static const char* fastdecode_delimited(upb_Decoder* d, const char* ptr, fastdecode_delimfunc* func, void* ctx) { ptr++; int len = (int8_t)ptr[-1]; if (fastdecode_boundscheck2(ptr, len, d->limit_ptr)) { // Slow case: Sub-message is >=128 bytes and/or exceeds the current buffer. // If it exceeds the buffer limit, limit/limit_ptr will change during // sub-message parsing, so we need to preserve delta, not limit. if (UPB_UNLIKELY(len & 0x80)) { // Size varint >1 byte (length >= 128). ptr = fastdecode_longsize(ptr, &len); if (!ptr) { // Corrupt wire format: size exceeded INT_MAX. return NULL; } } if (ptr - d->end + (int)len > d->limit) { // Corrupt wire format: invalid limit. return NULL; } int delta = decode_pushlimit(d, ptr, len); ptr = func(d, ptr, ctx); decode_poplimit(d, ptr, delta); } else { // Fast case: Sub-message is <128 bytes and fits in the current buffer. // This means we can preserve limit/limit_ptr verbatim. const char* saved_limit_ptr = d->limit_ptr; int saved_limit = d->limit; d->limit_ptr = ptr + len; d->limit = d->limit_ptr - d->end; UPB_ASSERT(d->limit_ptr == d->end + UPB_MIN(0, d->limit)); ptr = func(d, ptr, ctx); d->limit_ptr = saved_limit_ptr; d->limit = saved_limit; UPB_ASSERT(d->limit_ptr == d->end + UPB_MIN(0, d->limit)); } return ptr; } /* singular, oneof, repeated field handling ***********************************/ typedef struct { upb_Array* arr; void* end; } fastdecode_arr; typedef enum { FD_NEXT_ATLIMIT, FD_NEXT_SAMEFIELD, FD_NEXT_OTHERFIELD } fastdecode_next; typedef struct { void* dst; fastdecode_next next; uint32_t tag; } fastdecode_nextret; UPB_FORCEINLINE static void* fastdecode_resizearr(upb_Decoder* d, void* dst, fastdecode_arr* farr, int valbytes) { if (UPB_UNLIKELY(dst == farr->end)) { size_t old_size = farr->arr->size; size_t old_bytes = old_size * valbytes; size_t new_size = old_size * 2; size_t new_bytes = new_size * valbytes; char* old_ptr = _upb_array_ptr(farr->arr); char* new_ptr = upb_Arena_Realloc(&d->arena, old_ptr, old_bytes, new_bytes); uint8_t elem_size_lg2 = __builtin_ctz(valbytes); farr->arr->size = new_size; farr->arr->data = _upb_array_tagptr(new_ptr, elem_size_lg2); dst = (void*)(new_ptr + (old_size * valbytes)); farr->end = (void*)(new_ptr + (new_size * valbytes)); } return dst; } UPB_FORCEINLINE static bool fastdecode_tagmatch(uint32_t tag, uint64_t data, int tagbytes) { if (tagbytes == 1) { return (uint8_t)tag == (uint8_t)data; } else { return (uint16_t)tag == (uint16_t)data; } } UPB_FORCEINLINE static void fastdecode_commitarr(void* dst, fastdecode_arr* farr, int valbytes) { farr->arr->len = (size_t)((char*)dst - (char*)_upb_array_ptr(farr->arr)) / valbytes; } UPB_FORCEINLINE static fastdecode_nextret fastdecode_nextrepeated(upb_Decoder* d, void* dst, const char** ptr, fastdecode_arr* farr, uint64_t data, int tagbytes, int valbytes) { fastdecode_nextret ret; dst = (char*)dst + valbytes; if (UPB_LIKELY(!decode_isdone(d, ptr))) { ret.tag = fastdecode_loadtag(*ptr); if (fastdecode_tagmatch(ret.tag, data, tagbytes)) { ret.next = FD_NEXT_SAMEFIELD; } else { fastdecode_commitarr(dst, farr, valbytes); ret.next = FD_NEXT_OTHERFIELD; } } else { fastdecode_commitarr(dst, farr, valbytes); ret.next = FD_NEXT_ATLIMIT; } ret.dst = dst; return ret; } UPB_FORCEINLINE static void* fastdecode_fieldmem(upb_Message* msg, uint64_t data) { size_t ofs = data >> 48; return (char*)msg + ofs; } UPB_FORCEINLINE static void* fastdecode_getfield(upb_Decoder* d, const char* ptr, upb_Message* msg, uint64_t* data, uint64_t* hasbits, fastdecode_arr* farr, int valbytes, upb_card card) { switch (card) { case CARD_s: { uint8_t hasbit_index = *data >> 24; // Set hasbit and return pointer to scalar field. *hasbits |= 1ull << hasbit_index; return fastdecode_fieldmem(msg, *data); } case CARD_o: { uint16_t case_ofs = *data >> 32; uint32_t* oneof_case = UPB_PTR_AT(msg, case_ofs, uint32_t); uint8_t field_number = *data >> 24; *oneof_case = field_number; return fastdecode_fieldmem(msg, *data); } case CARD_r: { // Get pointer to upb_Array and allocate/expand if necessary. uint8_t elem_size_lg2 = __builtin_ctz(valbytes); upb_Array** arr_p = fastdecode_fieldmem(msg, *data); char* begin; *(uint32_t*)msg |= *hasbits; *hasbits = 0; if (UPB_LIKELY(!*arr_p)) { farr->arr = _upb_Array_New(&d->arena, 8, elem_size_lg2); *arr_p = farr->arr; } else { farr->arr = *arr_p; } begin = _upb_array_ptr(farr->arr); farr->end = begin + (farr->arr->size * valbytes); *data = fastdecode_loadtag(ptr); return begin + (farr->arr->len * valbytes); } default: UPB_UNREACHABLE(); } } UPB_FORCEINLINE static bool fastdecode_flippacked(uint64_t* data, int tagbytes) { *data ^= (0x2 ^ 0x0); // Patch data to match packed wiretype. return fastdecode_checktag(*data, tagbytes); } #define FASTDECODE_CHECKPACKED … /* varint fields **************************************************************/ UPB_FORCEINLINE static uint64_t fastdecode_munge(uint64_t val, int valbytes, bool zigzag) { if (valbytes == 1) { return val != 0; } else if (zigzag) { if (valbytes == 4) { uint32_t n = val; return (n >> 1) ^ -(int32_t)(n & 1); } else if (valbytes == 8) { return (val >> 1) ^ -(int64_t)(val & 1); } UPB_UNREACHABLE(); } return val; } UPB_FORCEINLINE static const char* fastdecode_varint64(const char* ptr, uint64_t* val) { ptr++; *val = (uint8_t)ptr[-1]; if (UPB_UNLIKELY(*val & 0x80)) { int i; for (i = 0; i < 8; i++) { ptr++; uint64_t byte = (uint8_t)ptr[-1]; *val += (byte - 1) << (7 + 7 * i); if (UPB_LIKELY((byte & 0x80) == 0)) goto done; } ptr++; uint64_t byte = (uint8_t)ptr[-1]; if (byte > 1) { return NULL; } *val += (byte - 1) << 63; } done: UPB_ASSUME(ptr != NULL); return ptr; } #define FASTDECODE_UNPACKEDVARINT … typedef struct { uint8_t valbytes; bool zigzag; void* dst; fastdecode_arr farr; } fastdecode_varintdata; UPB_FORCEINLINE static const char* fastdecode_topackedvarint(upb_Decoder* d, const char* ptr, void* ctx) { fastdecode_varintdata* data = ctx; void* dst = data->dst; uint64_t val; while (!decode_isdone(d, &ptr)) { dst = fastdecode_resizearr(d, dst, &data->farr, data->valbytes); ptr = fastdecode_varint64(ptr, &val); if (ptr == NULL) return NULL; val = fastdecode_munge(val, data->valbytes, data->zigzag); memcpy(dst, &val, data->valbytes); dst = (char*)dst + data->valbytes; } fastdecode_commitarr(dst, &data->farr, data->valbytes); return ptr; } #define FASTDECODE_PACKEDVARINT … #define FASTDECODE_VARINT … #define z_ZZ … #define b_ZZ … #define v_ZZ … /* Generate all combinations: * {s,o,r,p} x {b1,v4,z4,v8,z8} x {1bt,2bt} */ #define F … #define TYPES … #define TAGBYTES … TAGBYTES(s) TAGBYTES(o) TAGBYTES(r) TAGBYTES(p) #undef z_ZZ #undef b_ZZ #undef v_ZZ #undef o_ONEOF #undef s_ONEOF #undef r_ONEOF #undef F #undef TYPES #undef TAGBYTES #undef FASTDECODE_UNPACKEDVARINT #undef FASTDECODE_PACKEDVARINT #undef FASTDECODE_VARINT /* fixed fields ***************************************************************/ #define FASTDECODE_UNPACKEDFIXED … #define FASTDECODE_PACKEDFIXED … #define FASTDECODE_FIXED … /* Generate all combinations: * {s,o,r,p} x {f4,f8} x {1bt,2bt} */ #define F … #define TYPES … #define TAGBYTES … TAGBYTES(s) TAGBYTES(o) TAGBYTES(r) TAGBYTES(p) #undef F #undef TYPES #undef TAGBYTES #undef FASTDECODE_UNPACKEDFIXED #undef FASTDECODE_PACKEDFIXED /* string fields **************************************************************/ typedef const char* fastdecode_copystr_func(struct upb_Decoder* d, const char* ptr, upb_Message* msg, const upb_MiniTable* table, uint64_t hasbits, upb_StringView* dst); UPB_NOINLINE static const char* fastdecode_verifyutf8(upb_Decoder* d, const char* ptr, upb_Message* msg, intptr_t table, uint64_t hasbits, uint64_t data) { upb_StringView* dst = (upb_StringView*)data; if (!decode_verifyutf8_inl(dst->data, dst->size)) { return fastdecode_err(d, kUpb_DecodeStatus_BadUtf8); } UPB_MUSTTAIL return fastdecode_dispatch(UPB_PARSE_ARGS); } #define FASTDECODE_LONGSTRING … UPB_NOINLINE static const char* fastdecode_longstring_utf8(struct upb_Decoder* d, const char* ptr, upb_Message* msg, intptr_t table, uint64_t hasbits, uint64_t data) { upb_StringView* dst = (upb_StringView*)data; FASTDECODE_LONGSTRING(d, ptr, msg, table, hasbits, dst, true); } UPB_NOINLINE static const char* fastdecode_longstring_noutf8( struct upb_Decoder* d, const char* ptr, upb_Message* msg, intptr_t table, uint64_t hasbits, uint64_t data) { upb_StringView* dst = (upb_StringView*)data; FASTDECODE_LONGSTRING(d, ptr, msg, table, hasbits, dst, false); } UPB_FORCEINLINE static void fastdecode_docopy(upb_Decoder* d, const char* ptr, uint32_t size, int copy, char* data, upb_StringView* dst) { d->arena.head.ptr += copy; dst->data = data; UPB_UNPOISON_MEMORY_REGION(data, copy); memcpy(data, ptr, copy); UPB_POISON_MEMORY_REGION(data + size, copy - size); } #define FASTDECODE_COPYSTRING … #define FASTDECODE_STRING … /* Generate all combinations: * {p,c} x {s,o,r} x {s, b} x {1bt,2bt} */ #define s_VALIDATE … #define b_VALIDATE … #define F … #define UTF8 … #define TAGBYTES … TAGBYTES(s) TAGBYTES(o) TAGBYTES(r) #undef s_VALIDATE #undef b_VALIDATE #undef F #undef TAGBYTES #undef FASTDECODE_LONGSTRING #undef FASTDECODE_COPYSTRING #undef FASTDECODE_STRING /* message fields *************************************************************/ UPB_INLINE upb_Message* decode_newmsg_ceil(upb_Decoder* d, const upb_MiniTable* l, int msg_ceil_bytes) { size_t size = l->size + sizeof(upb_Message_Internal); char* msg_data; if (UPB_LIKELY(msg_ceil_bytes > 0 && _upb_ArenaHas(&d->arena) >= msg_ceil_bytes)) { UPB_ASSERT(size <= (size_t)msg_ceil_bytes); msg_data = d->arena.head.ptr; d->arena.head.ptr += size; UPB_UNPOISON_MEMORY_REGION(msg_data, msg_ceil_bytes); memset(msg_data, 0, msg_ceil_bytes); UPB_POISON_MEMORY_REGION(msg_data + size, msg_ceil_bytes - size); } else { msg_data = (char*)upb_Arena_Malloc(&d->arena, size); memset(msg_data, 0, size); } return msg_data + sizeof(upb_Message_Internal); } typedef struct { intptr_t table; upb_Message* msg; } fastdecode_submsgdata; UPB_FORCEINLINE static const char* fastdecode_tosubmsg(upb_Decoder* d, const char* ptr, void* ctx) { fastdecode_submsgdata* submsg = ctx; ptr = fastdecode_dispatch(d, ptr, submsg->msg, submsg->table, 0, 0); UPB_ASSUME(ptr != NULL); return ptr; } #define FASTDECODE_SUBMSG … #define F … #define SIZES … #define TAGBYTES … TAGBYTES(s) TAGBYTES(o) TAGBYTES(r) #undef TAGBYTES #undef SIZES #undef F #undef FASTDECODE_SUBMSG #endif /* UPB_FASTTABLE */
Codebase Browser
chromium