diff options
Diffstat (limited to 'src/core/lib/slice')
| -rw-r--r-- | src/core/lib/slice/percent_encoding.c | 180 | ||||
| -rw-r--r-- | src/core/lib/slice/percent_encoding.h | 78 | ||||
| -rw-r--r-- | src/core/lib/slice/slice.c | 350 | ||||
| -rw-r--r-- | src/core/lib/slice/slice_buffer.c | 284 | ||||
| -rw-r--r-- | src/core/lib/slice/slice_string_helpers.c | 89 | ||||
| -rw-r--r-- | src/core/lib/slice/slice_string_helpers.h | 58 |
6 files changed, 1039 insertions, 0 deletions
diff --git a/src/core/lib/slice/percent_encoding.c b/src/core/lib/slice/percent_encoding.c new file mode 100644 index 0000000000..b9e35f1c71 --- /dev/null +++ b/src/core/lib/slice/percent_encoding.c @@ -0,0 +1,180 @@ +/* + * + * Copyright 2016, Google Inc. + * 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 Inc. 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 THE COPYRIGHT + * OWNER OR CONTRIBUTORS 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. + * + */ + +#include "src/core/lib/slice/percent_encoding.h" + +#include <grpc/support/log.h> + +const uint8_t grpc_url_percent_encoding_unreserved_bytes[256 / 8] = { + 0x00, 0x00, 0x00, 0x00, 0x00, 0x60, 0xff, 0x03, 0xfe, 0xff, 0xff, + 0x87, 0xfe, 0xff, 0xff, 0x47, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; +const uint8_t grpc_compatible_percent_encoding_unreserved_bytes[256 / 8] = { + 0x00, 0x00, 0x00, 0x00, 0xdf, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; + +static bool is_unreserved_character(uint8_t c, + const uint8_t *unreserved_bytes) { + return ((unreserved_bytes[c / 8] >> (c % 8)) & 1) != 0; +} + +grpc_slice grpc_percent_encode_slice(grpc_slice slice, + const uint8_t *unreserved_bytes) { + static const uint8_t hex[] = "0123456789ABCDEF"; + + // first pass: count the number of bytes needed to output this string + size_t output_length = 0; + const uint8_t *slice_start = GRPC_SLICE_START_PTR(slice); + const uint8_t *slice_end = GRPC_SLICE_END_PTR(slice); + const uint8_t *p; + bool any_reserved_bytes = false; + for (p = slice_start; p < slice_end; p++) { + bool unres = is_unreserved_character(*p, unreserved_bytes); + output_length += unres ? 1 : 3; + any_reserved_bytes |= !unres; + } + // no unreserved bytes: return the string unmodified + if (!any_reserved_bytes) { + return grpc_slice_ref(slice); + } + // second pass: actually encode + grpc_slice out = grpc_slice_malloc(output_length); + uint8_t *q = GRPC_SLICE_START_PTR(out); + for (p = slice_start; p < slice_end; p++) { + if (is_unreserved_character(*p, unreserved_bytes)) { + *q++ = *p; + } else { + *q++ = '%'; + *q++ = hex[*p >> 4]; + *q++ = hex[*p & 15]; + } + } + GPR_ASSERT(q == GRPC_SLICE_END_PTR(out)); + return out; +} + +static bool valid_hex(const uint8_t *p, const uint8_t *end) { + if (p >= end) return false; + return (*p >= '0' && *p <= '9') || (*p >= 'a' && *p <= 'f') || + (*p >= 'A' && *p <= 'F'); +} + +static uint8_t dehex(uint8_t c) { + if (c >= '0' && c <= '9') return (uint8_t)(c - '0'); + if (c >= 'A' && c <= 'F') return (uint8_t)(c - 'A' + 10); + if (c >= 'a' && c <= 'f') return (uint8_t)(c - 'a' + 10); + GPR_UNREACHABLE_CODE(return 255); +} + +bool grpc_strict_percent_decode_slice(grpc_slice slice_in, + const uint8_t *unreserved_bytes, + grpc_slice *slice_out) { + const uint8_t *p = GRPC_SLICE_START_PTR(slice_in); + const uint8_t *in_end = GRPC_SLICE_END_PTR(slice_in); + size_t out_length = 0; + bool any_percent_encoded_stuff = false; + while (p != in_end) { + if (*p == '%') { + if (!valid_hex(++p, in_end)) return false; + if (!valid_hex(++p, in_end)) return false; + p++; + out_length++; + any_percent_encoded_stuff = true; + } else if (is_unreserved_character(*p, unreserved_bytes)) { + p++; + out_length++; + } else { + return false; + } + } + if (!any_percent_encoded_stuff) { + *slice_out = grpc_slice_ref(slice_in); + return true; + } + p = GRPC_SLICE_START_PTR(slice_in); + *slice_out = grpc_slice_malloc(out_length); + uint8_t *q = GRPC_SLICE_START_PTR(*slice_out); + while (p != in_end) { + if (*p == '%') { + *q++ = (uint8_t)(dehex(p[1]) << 4) | (dehex(p[2])); + p += 3; + } else { + *q++ = *p++; + } + } + GPR_ASSERT(q == GRPC_SLICE_END_PTR(*slice_out)); + return true; +} + +grpc_slice grpc_permissive_percent_decode_slice(grpc_slice slice_in) { + const uint8_t *p = GRPC_SLICE_START_PTR(slice_in); + const uint8_t *in_end = GRPC_SLICE_END_PTR(slice_in); + size_t out_length = 0; + bool any_percent_encoded_stuff = false; + while (p != in_end) { + if (*p == '%') { + if (!valid_hex(p + 1, in_end) || !valid_hex(p + 2, in_end)) { + p++; + out_length++; + } else { + p += 3; + out_length++; + any_percent_encoded_stuff = true; + } + } else { + p++; + out_length++; + } + } + if (!any_percent_encoded_stuff) { + return grpc_slice_ref(slice_in); + } + p = GRPC_SLICE_START_PTR(slice_in); + grpc_slice out = grpc_slice_malloc(out_length); + uint8_t *q = GRPC_SLICE_START_PTR(out); + while (p != in_end) { + if (*p == '%') { + if (!valid_hex(p + 1, in_end) || !valid_hex(p + 2, in_end)) { + *q++ = *p++; + } else { + *q++ = (uint8_t)(dehex(p[1]) << 4) | (dehex(p[2])); + p += 3; + } + } else { + *q++ = *p++; + } + } + GPR_ASSERT(q == GRPC_SLICE_END_PTR(out)); + return out; +} diff --git a/src/core/lib/slice/percent_encoding.h b/src/core/lib/slice/percent_encoding.h new file mode 100644 index 0000000000..189bdbe312 --- /dev/null +++ b/src/core/lib/slice/percent_encoding.h @@ -0,0 +1,78 @@ +/* + * + * Copyright 2016, Google Inc. + * 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 Inc. 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 THE COPYRIGHT + * OWNER OR CONTRIBUTORS 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. + * + */ + +#ifndef GRPC_CORE_LIB_SLICE_PERCENT_ENCODING_H +#define GRPC_CORE_LIB_SLICE_PERCENT_ENCODING_H + +/* Percent encoding and decoding of slices. + Transforms arbitrary strings into safe-for-transmission strings by using + variants of percent encoding (RFC 3986). + Two major variants are supplied: one that strictly matches URL encoding, + and another which applies percent encoding only to non-http2 header + bytes (the 'compatible' variant) */ + +#include <stdbool.h> + +#include <grpc/slice.h> + +/* URL percent encoding spec bitfield (usabel as 'unreserved_bytes' in + grpc_percent_encode_slice, grpc_strict_percent_decode_slice). + Flags [A-Za-z0-9-_.~] as unreserved bytes for the percent encoding routines + */ +extern const uint8_t grpc_url_percent_encoding_unreserved_bytes[256 / 8]; +/* URL percent encoding spec bitfield (usabel as 'unreserved_bytes' in + grpc_percent_encode_slice, grpc_strict_percent_decode_slice). + Flags ascii7 non-control characters excluding '%' as unreserved bytes for the + percent encoding routines */ +extern const uint8_t grpc_compatible_percent_encoding_unreserved_bytes[256 / 8]; + +/* Percent-encode a slice, returning the new slice (this cannot fail): + unreserved_bytes is a bitfield indicating which bytes are considered + unreserved and thus do not need percent encoding */ +grpc_slice grpc_percent_encode_slice(grpc_slice slice, + const uint8_t *unreserved_bytes); +/* Percent-decode a slice, strictly. + If the input is legal (contains no unreserved bytes, and legal % encodings), + returns true and sets *slice_out to the decoded slice. + If the input is not legal, returns false and leaves *slice_out untouched. + unreserved_bytes is a bitfield indicating which bytes are considered + unreserved and thus do not need percent encoding */ +bool grpc_strict_percent_decode_slice(grpc_slice slice_in, + const uint8_t *unreserved_bytes, + grpc_slice *slice_out); +/* Percent-decode a slice, permissively. + If a % triplet can not be decoded, pass it through verbatim. + This cannot fail. */ +grpc_slice grpc_permissive_percent_decode_slice(grpc_slice slice_in); + +#endif /* GRPC_CORE_LIB_SLICE_PERCENT_ENCODING_H */ diff --git a/src/core/lib/slice/slice.c b/src/core/lib/slice/slice.c new file mode 100644 index 0000000000..3dac18df61 --- /dev/null +++ b/src/core/lib/slice/slice.c @@ -0,0 +1,350 @@ +/* + * + * Copyright 2015, Google Inc. + * 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 Inc. 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 THE COPYRIGHT + * OWNER OR CONTRIBUTORS 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. + * + */ + +#include <grpc/slice.h> +#include <grpc/support/alloc.h> +#include <grpc/support/log.h> + +#include <string.h> + +grpc_slice gpr_empty_slice(void) { + grpc_slice out; + out.refcount = 0; + out.data.inlined.length = 0; + return out; +} + +grpc_slice grpc_slice_ref(grpc_slice slice) { + if (slice.refcount) { + slice.refcount->ref(slice.refcount); + } + return slice; +} + +void grpc_slice_unref(grpc_slice slice) { + if (slice.refcount) { + slice.refcount->unref(slice.refcount); + } +} + +/* grpc_slice_from_static_string support structure - a refcount that does + nothing */ +static void noop_ref_or_unref(void *unused) {} + +static grpc_slice_refcount noop_refcount = {noop_ref_or_unref, + noop_ref_or_unref}; + +grpc_slice grpc_slice_from_static_string(const char *s) { + grpc_slice slice; + slice.refcount = &noop_refcount; + slice.data.refcounted.bytes = (uint8_t *)s; + slice.data.refcounted.length = strlen(s); + return slice; +} + +/* grpc_slice_new support structures - we create a refcount object extended + with the user provided data pointer & destroy function */ +typedef struct new_slice_refcount { + grpc_slice_refcount rc; + gpr_refcount refs; + void (*user_destroy)(void *); + void *user_data; +} new_slice_refcount; + +static void new_slice_ref(void *p) { + new_slice_refcount *r = p; + gpr_ref(&r->refs); +} + +static void new_slice_unref(void *p) { + new_slice_refcount *r = p; + if (gpr_unref(&r->refs)) { + r->user_destroy(r->user_data); + gpr_free(r); + } +} + +grpc_slice grpc_slice_new_with_user_data(void *p, size_t len, + void (*destroy)(void *), + void *user_data) { + grpc_slice slice; + new_slice_refcount *rc = gpr_malloc(sizeof(new_slice_refcount)); + gpr_ref_init(&rc->refs, 1); + rc->rc.ref = new_slice_ref; + rc->rc.unref = new_slice_unref; + rc->user_destroy = destroy; + rc->user_data = user_data; + + slice.refcount = &rc->rc; + slice.data.refcounted.bytes = p; + slice.data.refcounted.length = len; + return slice; +} + +grpc_slice grpc_slice_new(void *p, size_t len, void (*destroy)(void *)) { + /* Pass "p" to *destroy when the slice is no longer needed. */ + return grpc_slice_new_with_user_data(p, len, destroy, p); +} + +/* grpc_slice_new_with_len support structures - we create a refcount object + extended with the user provided data pointer & destroy function */ +typedef struct new_with_len_slice_refcount { + grpc_slice_refcount rc; + gpr_refcount refs; + void *user_data; + size_t user_length; + void (*user_destroy)(void *, size_t); +} new_with_len_slice_refcount; + +static void new_with_len_ref(void *p) { + new_with_len_slice_refcount *r = p; + gpr_ref(&r->refs); +} + +static void new_with_len_unref(void *p) { + new_with_len_slice_refcount *r = p; + if (gpr_unref(&r->refs)) { + r->user_destroy(r->user_data, r->user_length); + gpr_free(r); + } +} + +grpc_slice grpc_slice_new_with_len(void *p, size_t len, + void (*destroy)(void *, size_t)) { + grpc_slice slice; + new_with_len_slice_refcount *rc = + gpr_malloc(sizeof(new_with_len_slice_refcount)); + gpr_ref_init(&rc->refs, 1); + rc->rc.ref = new_with_len_ref; + rc->rc.unref = new_with_len_unref; + rc->user_destroy = destroy; + rc->user_data = p; + rc->user_length = len; + + slice.refcount = &rc->rc; + slice.data.refcounted.bytes = p; + slice.data.refcounted.length = len; + return slice; +} + +grpc_slice grpc_slice_from_copied_buffer(const char *source, size_t length) { + grpc_slice slice = grpc_slice_malloc(length); + memcpy(GRPC_SLICE_START_PTR(slice), source, length); + return slice; +} + +grpc_slice grpc_slice_from_copied_string(const char *source) { + return grpc_slice_from_copied_buffer(source, strlen(source)); +} + +typedef struct { + grpc_slice_refcount base; + gpr_refcount refs; +} malloc_refcount; + +static void malloc_ref(void *p) { + malloc_refcount *r = p; + gpr_ref(&r->refs); +} + +static void malloc_unref(void *p) { + malloc_refcount *r = p; + if (gpr_unref(&r->refs)) { + gpr_free(r); + } +} + +grpc_slice grpc_slice_malloc(size_t length) { + grpc_slice slice; + + if (length > sizeof(slice.data.inlined.bytes)) { + /* Memory layout used by the slice created here: + + +-----------+----------------------------------------------------------+ + | refcount | bytes | + +-----------+----------------------------------------------------------+ + + refcount is a malloc_refcount + bytes is an array of bytes of the requested length + Both parts are placed in the same allocation returned from gpr_malloc */ + malloc_refcount *rc = gpr_malloc(sizeof(malloc_refcount) + length); + + /* Initial refcount on rc is 1 - and it's up to the caller to release + this reference. */ + gpr_ref_init(&rc->refs, 1); + + rc->base.ref = malloc_ref; + rc->base.unref = malloc_unref; + + /* Build up the slice to be returned. */ + /* The slices refcount points back to the allocated block. */ + slice.refcount = &rc->base; + /* The data bytes are placed immediately after the refcount struct */ + slice.data.refcounted.bytes = (uint8_t *)(rc + 1); + /* And the length of the block is set to the requested length */ + slice.data.refcounted.length = length; + } else { + /* small slice: just inline the data */ + slice.refcount = NULL; + slice.data.inlined.length = (uint8_t)length; + } + return slice; +} + +grpc_slice grpc_slice_sub_no_ref(grpc_slice source, size_t begin, size_t end) { + grpc_slice subset; + + GPR_ASSERT(end >= begin); + + if (source.refcount) { + /* Enforce preconditions */ + GPR_ASSERT(source.data.refcounted.length >= end); + + /* Build the result */ + subset.refcount = source.refcount; + /* Point into the source array */ + subset.data.refcounted.bytes = source.data.refcounted.bytes + begin; + subset.data.refcounted.length = end - begin; + } else { + /* Enforce preconditions */ + GPR_ASSERT(source.data.inlined.length >= end); + subset.refcount = NULL; + subset.data.inlined.length = (uint8_t)(end - begin); + memcpy(subset.data.inlined.bytes, source.data.inlined.bytes + begin, + end - begin); + } + return subset; +} + +grpc_slice grpc_slice_sub(grpc_slice source, size_t begin, size_t end) { + grpc_slice subset; + + if (end - begin <= sizeof(subset.data.inlined.bytes)) { + subset.refcount = NULL; + subset.data.inlined.length = (uint8_t)(end - begin); + memcpy(subset.data.inlined.bytes, GRPC_SLICE_START_PTR(source) + begin, + end - begin); + } else { + subset = grpc_slice_sub_no_ref(source, begin, end); + /* Bump the refcount */ + subset.refcount->ref(subset.refcount); + } + return subset; +} + +grpc_slice grpc_slice_split_tail(grpc_slice *source, size_t split) { + grpc_slice tail; + + if (source->refcount == NULL) { + /* inlined data, copy it out */ + GPR_ASSERT(source->data.inlined.length >= split); + tail.refcount = NULL; + tail.data.inlined.length = (uint8_t)(source->data.inlined.length - split); + memcpy(tail.data.inlined.bytes, source->data.inlined.bytes + split, + tail.data.inlined.length); + source->data.inlined.length = (uint8_t)split; + } else { + size_t tail_length = source->data.refcounted.length - split; + GPR_ASSERT(source->data.refcounted.length >= split); + if (tail_length < sizeof(tail.data.inlined.bytes)) { + /* Copy out the bytes - it'll be cheaper than refcounting */ + tail.refcount = NULL; + tail.data.inlined.length = (uint8_t)tail_length; + memcpy(tail.data.inlined.bytes, source->data.refcounted.bytes + split, + tail_length); + } else { + /* Build the result */ + tail.refcount = source->refcount; + /* Bump the refcount */ + tail.refcount->ref(tail.refcount); + /* Point into the source array */ + tail.data.refcounted.bytes = source->data.refcounted.bytes + split; + tail.data.refcounted.length = tail_length; + } + source->data.refcounted.length = split; + } + + return tail; +} + +grpc_slice grpc_slice_split_head(grpc_slice *source, size_t split) { + grpc_slice head; + + if (source->refcount == NULL) { + GPR_ASSERT(source->data.inlined.length >= split); + + head.refcount = NULL; + head.data.inlined.length = (uint8_t)split; + memcpy(head.data.inlined.bytes, source->data.inlined.bytes, split); + source->data.inlined.length = + (uint8_t)(source->data.inlined.length - split); + memmove(source->data.inlined.bytes, source->data.inlined.bytes + split, + source->data.inlined.length); + } else if (split < sizeof(head.data.inlined.bytes)) { + GPR_ASSERT(source->data.refcounted.length >= split); + + head.refcount = NULL; + head.data.inlined.length = (uint8_t)split; + memcpy(head.data.inlined.bytes, source->data.refcounted.bytes, split); + source->data.refcounted.bytes += split; + source->data.refcounted.length -= split; + } else { + GPR_ASSERT(source->data.refcounted.length >= split); + + /* Build the result */ + head.refcount = source->refcount; + /* Bump the refcount */ + head.refcount->ref(head.refcount); + /* Point into the source array */ + head.data.refcounted.bytes = source->data.refcounted.bytes; + head.data.refcounted.length = split; + source->data.refcounted.bytes += split; + source->data.refcounted.length -= split; + } + + return head; +} + +int grpc_slice_cmp(grpc_slice a, grpc_slice b) { + int d = (int)(GRPC_SLICE_LENGTH(a) - GRPC_SLICE_LENGTH(b)); + if (d != 0) return d; + return memcmp(GRPC_SLICE_START_PTR(a), GRPC_SLICE_START_PTR(b), + GRPC_SLICE_LENGTH(a)); +} + +int grpc_slice_str_cmp(grpc_slice a, const char *b) { + size_t b_length = strlen(b); + int d = (int)(GRPC_SLICE_LENGTH(a) - b_length); + if (d != 0) return d; + return memcmp(GRPC_SLICE_START_PTR(a), b, b_length); +} diff --git a/src/core/lib/slice/slice_buffer.c b/src/core/lib/slice/slice_buffer.c new file mode 100644 index 0000000000..990ef128bd --- /dev/null +++ b/src/core/lib/slice/slice_buffer.c @@ -0,0 +1,284 @@ +/* + * + * Copyright 2015, Google Inc. + * 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 Inc. 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 THE COPYRIGHT + * OWNER OR CONTRIBUTORS 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. + * + */ + +#include <grpc/slice_buffer.h> +#include <grpc/support/port_platform.h> + +#include <string.h> + +#include <grpc/support/alloc.h> +#include <grpc/support/log.h> +#include <grpc/support/useful.h> + +/* grow a buffer; requires GRPC_SLICE_BUFFER_INLINE_ELEMENTS > 1 */ +#define GROW(x) (3 * (x) / 2) + +static void maybe_embiggen(grpc_slice_buffer *sb) { + if (sb->count == sb->capacity) { + sb->capacity = GROW(sb->capacity); + GPR_ASSERT(sb->capacity > sb->count); + if (sb->slices == sb->inlined) { + sb->slices = gpr_malloc(sb->capacity * sizeof(grpc_slice)); + memcpy(sb->slices, sb->inlined, sb->count * sizeof(grpc_slice)); + } else { + sb->slices = gpr_realloc(sb->slices, sb->capacity * sizeof(grpc_slice)); + } + } +} + +void grpc_slice_buffer_init(grpc_slice_buffer *sb) { + sb->count = 0; + sb->length = 0; + sb->capacity = GRPC_SLICE_BUFFER_INLINE_ELEMENTS; + sb->slices = sb->inlined; +} + +void grpc_slice_buffer_destroy(grpc_slice_buffer *sb) { + grpc_slice_buffer_reset_and_unref(sb); + if (sb->slices != sb->inlined) { + gpr_free(sb->slices); + } +} + +uint8_t *grpc_slice_buffer_tiny_add(grpc_slice_buffer *sb, size_t n) { + grpc_slice *back; + uint8_t *out; + + sb->length += n; + + if (sb->count == 0) goto add_new; + back = &sb->slices[sb->count - 1]; + if (back->refcount) goto add_new; + if ((back->data.inlined.length + n) > sizeof(back->data.inlined.bytes)) + goto add_new; + out = back->data.inlined.bytes + back->data.inlined.length; + back->data.inlined.length = (uint8_t)(back->data.inlined.length + n); + return out; + +add_new: + maybe_embiggen(sb); + back = &sb->slices[sb->count]; + sb->count++; + back->refcount = NULL; + back->data.inlined.length = (uint8_t)n; + return back->data.inlined.bytes; +} + +size_t grpc_slice_buffer_add_indexed(grpc_slice_buffer *sb, grpc_slice s) { + size_t out = sb->count; + maybe_embiggen(sb); + sb->slices[out] = s; + sb->length += GRPC_SLICE_LENGTH(s); + sb->count = out + 1; + return out; +} + +void grpc_slice_buffer_add(grpc_slice_buffer *sb, grpc_slice s) { + size_t n = sb->count; + /* if both the last slice in the slice buffer and the slice being added + are inlined (that is, that they carry their data inside the slice data + structure), and the back slice is not full, then concatenate directly + into the back slice, preventing many small slices being passed into + writes */ + if (!s.refcount && n) { + grpc_slice *back = &sb->slices[n - 1]; + if (!back->refcount && + back->data.inlined.length < GRPC_SLICE_INLINED_SIZE) { + if (s.data.inlined.length + back->data.inlined.length <= + GRPC_SLICE_INLINED_SIZE) { + memcpy(back->data.inlined.bytes + back->data.inlined.length, + s.data.inlined.bytes, s.data.inlined.length); + back->data.inlined.length = + (uint8_t)(back->data.inlined.length + s.data.inlined.length); + } else { + size_t cp1 = GRPC_SLICE_INLINED_SIZE - back->data.inlined.length; + memcpy(back->data.inlined.bytes + back->data.inlined.length, + s.data.inlined.bytes, cp1); + back->data.inlined.length = GRPC_SLICE_INLINED_SIZE; + maybe_embiggen(sb); + back = &sb->slices[n]; + sb->count = n + 1; + back->refcount = NULL; + back->data.inlined.length = (uint8_t)(s.data.inlined.length - cp1); + memcpy(back->data.inlined.bytes, s.data.inlined.bytes + cp1, + s.data.inlined.length - cp1); + } + sb->length += s.data.inlined.length; + return; /* early out */ + } + } + grpc_slice_buffer_add_indexed(sb, s); +} + +void grpc_slice_buffer_addn(grpc_slice_buffer *sb, grpc_slice *s, size_t n) { + size_t i; + for (i = 0; i < n; i++) { + grpc_slice_buffer_add(sb, s[i]); + } +} + +void grpc_slice_buffer_pop(grpc_slice_buffer *sb) { + if (sb->count != 0) { + size_t count = --sb->count; + sb->length -= GRPC_SLICE_LENGTH(sb->slices[count]); + } +} + +void grpc_slice_buffer_reset_and_unref(grpc_slice_buffer *sb) { + size_t i; + + for (i = 0; i < sb->count; i++) { + grpc_slice_unref(sb->slices[i]); + } + + sb->count = 0; + sb->length = 0; +} + +void grpc_slice_buffer_swap(grpc_slice_buffer *a, grpc_slice_buffer *b) { + GPR_SWAP(size_t, a->count, b->count); + GPR_SWAP(size_t, a->capacity, b->capacity); + GPR_SWAP(size_t, a->length, b->length); + + if (a->slices == a->inlined) { + if (b->slices == b->inlined) { + /* swap contents of inlined buffer */ + grpc_slice temp[GRPC_SLICE_BUFFER_INLINE_ELEMENTS]; + memcpy(temp, a->slices, b->count * sizeof(grpc_slice)); + memcpy(a->slices, b->slices, a->count * sizeof(grpc_slice)); + memcpy(b->slices, temp, b->count * sizeof(grpc_slice)); + } else { + /* a is inlined, b is not - copy a inlined into b, fix pointers */ + a->slices = b->slices; + b->slices = b->inlined; + memcpy(b->slices, a->inlined, b->count * sizeof(grpc_slice)); + } + } else if (b->slices == b->inlined) { + /* b is inlined, a is not - copy b inlined int a, fix pointers */ + b->slices = a->slices; + a->slices = a->inlined; + memcpy(a->slices, b->inlined, a->count * sizeof(grpc_slice)); + } else { + /* no inlining: easy swap */ + GPR_SWAP(grpc_slice *, a->slices, b->slices); + } +} + +void grpc_slice_buffer_move_into(grpc_slice_buffer *src, + grpc_slice_buffer *dst) { + /* anything to move? */ + if (src->count == 0) { + return; + } + /* anything in dst? */ + if (dst->count == 0) { + grpc_slice_buffer_swap(src, dst); + return; + } + /* both buffers have data - copy, and reset src */ + grpc_slice_buffer_addn(dst, src->slices, src->count); + src->count = 0; + src->length = 0; +} + +void grpc_slice_buffer_move_first(grpc_slice_buffer *src, size_t n, + grpc_slice_buffer *dst) { + size_t src_idx; + size_t output_len = dst->length + n; + size_t new_input_len = src->length - n; + GPR_ASSERT(src->length >= n); + if (src->length == n) { + grpc_slice_buffer_move_into(src, dst); + return; + } + src_idx = 0; + while (src_idx < src->capacity) { + grpc_slice slice = src->slices[src_idx]; + size_t slice_len = GRPC_SLICE_LENGTH(slice); + if (n > slice_len) { + grpc_slice_buffer_add(dst, slice); + n -= slice_len; + src_idx++; + } else if (n == slice_len) { + grpc_slice_buffer_add(dst, slice); + src_idx++; + break; + } else { /* n < slice_len */ + src->slices[src_idx] = grpc_slice_split_tail(&slice, n); + GPR_ASSERT(GRPC_SLICE_LENGTH(slice) == n); + GPR_ASSERT(GRPC_SLICE_LENGTH(src->slices[src_idx]) == slice_len - n); + grpc_slice_buffer_add(dst, slice); + break; + } + } + GPR_ASSERT(dst->length == output_len); + memmove(src->slices, src->slices + src_idx, + sizeof(grpc_slice) * (src->count - src_idx)); + src->count -= src_idx; + src->length = new_input_len; + GPR_ASSERT(src->count > 0); +} + +void grpc_slice_buffer_trim_end(grpc_slice_buffer *sb, size_t n, + grpc_slice_buffer *garbage) { + GPR_ASSERT(n <= sb->length); + sb->length -= n; + for (;;) { + size_t idx = sb->count - 1; + grpc_slice slice = sb->slices[idx]; + size_t slice_len = GRPC_SLICE_LENGTH(slice); + if (slice_len > n) { + sb->slices[idx] = grpc_slice_split_head(&slice, slice_len - n); + grpc_slice_buffer_add_indexed(garbage, slice); + return; + } else if (slice_len == n) { + grpc_slice_buffer_add_indexed(garbage, slice); + sb->count = idx; + return; + } else { + grpc_slice_buffer_add_indexed(garbage, slice); + n -= slice_len; + sb->count = idx; + } + } +} + +grpc_slice grpc_slice_buffer_take_first(grpc_slice_buffer *sb) { + grpc_slice slice; + GPR_ASSERT(sb->count > 0); + slice = sb->slices[0]; + memmove(&sb->slices[0], &sb->slices[1], (sb->count - 1) * sizeof(grpc_slice)); + sb->count--; + sb->length -= GRPC_SLICE_LENGTH(slice); + return slice; +} diff --git a/src/core/lib/slice/slice_string_helpers.c b/src/core/lib/slice/slice_string_helpers.c new file mode 100644 index 0000000000..4731762ece --- /dev/null +++ b/src/core/lib/slice/slice_string_helpers.c @@ -0,0 +1,89 @@ +/* + * + * Copyright 2015, Google Inc. + * 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 Inc. 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 THE COPYRIGHT + * OWNER OR CONTRIBUTORS 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. + * + */ + +#include "src/core/lib/slice/slice_string_helpers.h" + +#include <string.h> + +#include <grpc/support/log.h> + +#include "src/core/lib/support/string.h" + +char *grpc_dump_slice(grpc_slice s, uint32_t flags) { + return gpr_dump((const char *)GRPC_SLICE_START_PTR(s), GRPC_SLICE_LENGTH(s), + flags); +} + +/** Finds the initial (\a begin) and final (\a end) offsets of the next + * substring from \a str + \a read_offset until the next \a sep or the end of \a + * str. + * + * Returns 1 and updates \a begin and \a end. Returns 0 otherwise. */ +static int slice_find_separator_offset(const grpc_slice str, const char *sep, + const size_t read_offset, size_t *begin, + size_t *end) { + size_t i; + const uint8_t *str_ptr = GRPC_SLICE_START_PTR(str) + read_offset; + const size_t str_len = GRPC_SLICE_LENGTH(str) - read_offset; + const size_t sep_len = strlen(sep); + if (str_len < sep_len) { + return 0; + } + + for (i = 0; i <= str_len - sep_len; i++) { + if (memcmp(str_ptr + i, sep, sep_len) == 0) { + *begin = read_offset; + *end = read_offset + i; + return 1; + } + } + return 0; +} + +void grpc_slice_split(grpc_slice str, const char *sep, grpc_slice_buffer *dst) { + const size_t sep_len = strlen(sep); + size_t begin, end; + + GPR_ASSERT(sep_len > 0); + + if (slice_find_separator_offset(str, sep, 0, &begin, &end) != 0) { + do { + grpc_slice_buffer_add_indexed(dst, grpc_slice_sub(str, begin, end)); + } while (slice_find_separator_offset(str, sep, end + sep_len, &begin, + &end) != 0); + grpc_slice_buffer_add_indexed( + dst, grpc_slice_sub(str, end + sep_len, GRPC_SLICE_LENGTH(str))); + } else { /* no sep found, add whole input */ + grpc_slice_buffer_add_indexed(dst, grpc_slice_ref(str)); + } +} diff --git a/src/core/lib/slice/slice_string_helpers.h b/src/core/lib/slice/slice_string_helpers.h new file mode 100644 index 0000000000..151c720777 --- /dev/null +++ b/src/core/lib/slice/slice_string_helpers.h @@ -0,0 +1,58 @@ +/* + * + * Copyright 2015, Google Inc. + * 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 Inc. 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 THE COPYRIGHT + * OWNER OR CONTRIBUTORS 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. + * + */ + +#ifndef GRPC_CORE_LIB_SLICE_SLICE_STRING_HELPERS_H +#define GRPC_CORE_LIB_SLICE_SLICE_STRING_HELPERS_H + +#include <stddef.h> + +#include <grpc/slice.h> +#include <grpc/slice_buffer.h> +#include <grpc/support/port_platform.h> + +#ifdef __cplusplus +extern "C" { +#endif + +/* Calls gpr_dump on a slice. */ +char *grpc_dump_slice(grpc_slice slice, uint32_t flags); + +/** Split \a str by the separator \a sep. Results are stored in \a dst, which + * should be a properly initialized instance. */ +void grpc_slice_split(grpc_slice str, const char *sep, grpc_slice_buffer *dst); + +#ifdef __cplusplus +} +#endif + +#endif /* GRPC_CORE_LIB_SLICE_SLICE_STRING_HELPERS_H */ |