src/core/lib/slice/slice_buffer.cc

   1 /*
   2  *
   3  * Copyright 2015 gRPC authors.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  */
  18
  19 #include <grpc/support/port_platform.h>
  20
  21 #include <grpc/slice_buffer.h>
  22
  23 #include <string.h>
  24
  25 #include <grpc/support/alloc.h>
  26 #include <grpc/support/log.h>
  27
  28 #include "src/core/lib/gpr/useful.h"
  29 #include "src/core/lib/iomgr/exec_ctx.h"
  30 #include "src/core/lib/slice/slice_internal.h"
  31
  32 /* grow a buffer; requires GRPC_SLICE_BUFFER_INLINE_ELEMENTS > 1 */
  33 #define GROW(x) (3 * (x) / 2)
  34
  35 /* Typically, we do not actually need to embiggen (by calling
  36  * memmove/malloc/realloc) - only if we were up against the full capacity of the
  37  * slice buffer. If do_embiggen is inlined, the compiler clobbers multiple
  38  * registers pointlessly in the common case. */
  39 static void GPR_ATTRIBUTE_NOINLINE do_embiggen(grpc_slice_buffer* sb,
  40                                                const size_t slice_count,
  41                                                const size_t slice_offset) {
  42   if (slice_offset != 0) {
  43     /* Make room by moving elements if there's still space unused */
  44     memmove(sb->base_slices, sb->slices, sb->count * sizeof(grpc_slice));
  45     sb->slices = sb->base_slices;
  46   } else {
  47     /* Allocate more memory if no more space is available */
  48     const size_t new_capacity = GROW(sb->capacity);
  49     sb->capacity = new_capacity;
  50     if (sb->base_slices == sb->inlined) {
  51       sb->base_slices = static_cast<grpc_slice*>(
  52           gpr_malloc(new_capacity * sizeof(grpc_slice)));
  53       memcpy(sb->base_slices, sb->inlined, slice_count * sizeof(grpc_slice));
  54     } else {
  55       sb->base_slices = static_cast<grpc_slice*>(
  56           gpr_realloc(sb->base_slices, new_capacity * sizeof(grpc_slice)));
  57     }
  58
  59     sb->slices = sb->base_slices + slice_offset;
  60   }
  61 }
  62
  63 static void maybe_embiggen(grpc_slice_buffer* sb) {
  64   if (sb->count == 0) {
  65     sb->slices = sb->base_slices;
  66     return;
  67   }
  68
  69   /* How far away from sb->base_slices is sb->slices pointer */
  70   size_t slice_offset = static_cast<size_t>(sb->slices - sb->base_slices);
  71   size_t slice_count = sb->count + slice_offset;
  72   if (GPR_UNLIKELY(slice_count == sb->capacity)) {
  73     do_embiggen(sb, slice_count, slice_offset);
  74   }
  75 }
  76
  77 void grpc_slice_buffer_init(grpc_slice_buffer* sb) {
  78   sb->count = 0;
  79   sb->length = 0;
  80   sb->capacity = GRPC_SLICE_BUFFER_INLINE_ELEMENTS;
  81   sb->base_slices = sb->slices = sb->inlined;
  82 }
  83
  84 void grpc_slice_buffer_destroy_internal(grpc_slice_buffer* sb) {
  85   grpc_slice_buffer_reset_and_unref_internal(sb);
  86   if (sb->base_slices != sb->inlined) {
  87     gpr_free(sb->base_slices);
  88   }
  89 }
  90
  91 void grpc_slice_buffer_destroy(grpc_slice_buffer* sb) {
  92   if (grpc_core::ExecCtx::Get() == nullptr) {
  93     grpc_core::ExecCtx exec_ctx;
  94     grpc_slice_buffer_destroy_internal(sb);
  95   } else {
  96     grpc_slice_buffer_destroy_internal(sb);
  97   }
  98 }
  99
 100 uint8_t* grpc_slice_buffer_tiny_add(grpc_slice_buffer* sb, size_t n) {
 101   grpc_slice* back;
 102   uint8_t* out;
 103
 104   sb->length += n;
 105
 106   if (sb->count == 0) goto add_new;
 107   back = &sb->slices[sb->count - 1];
 108   if (back->refcount) goto add_new;
 109   if ((back->data.inlined.length + n) > sizeof(back->data.inlined.bytes))
 110     goto add_new;
 111   out = back->data.inlined.bytes + back->data.inlined.length;
 112   back->data.inlined.length =
 113       static_cast<uint8_t>(back->data.inlined.length + n);
 114   return out;
 115
 116 add_new:
 117   maybe_embiggen(sb);
 118   back = &sb->slices[sb->count];
 119   sb->count++;
 120   back->refcount = nullptr;
 121   back->data.inlined.length = static_cast<uint8_t>(n);
 122   return back->data.inlined.bytes;
 123 }
 124
 125 size_t grpc_slice_buffer_add_indexed(grpc_slice_buffer* sb, grpc_slice s) {
 126   size_t out = sb->count;
 127   maybe_embiggen(sb);
 128   sb->slices[out] = s;
 129   sb->length += GRPC_SLICE_LENGTH(s);
 130   sb->count = out + 1;
 131   return out;
 132 }
 133
 134 void grpc_slice_buffer_add(grpc_slice_buffer* sb, grpc_slice s) {
 135   size_t n = sb->count;
 136   /* if both the last slice in the slice buffer and the slice being added
 137      are inlined (that is, that they carry their data inside the slice data
 138      structure), and the back slice is not full, then concatenate directly
 139      into the back slice, preventing many small slices being passed into
 140      writes */
 141   if (!s.refcount && n) {
 142     grpc_slice* back = &sb->slices[n - 1];
 143     if (!back->refcount &&
 144         back->data.inlined.length < GRPC_SLICE_INLINED_SIZE) {
 145       if (s.data.inlined.length + back->data.inlined.length <=
 146           GRPC_SLICE_INLINED_SIZE) {
 147         memcpy(back->data.inlined.bytes + back->data.inlined.length,
 148                s.data.inlined.bytes, s.data.inlined.length);
 149         back->data.inlined.length = static_cast<uint8_t>(
 150             back->data.inlined.length + s.data.inlined.length);
 151       } else {
 152         size_t cp1 = GRPC_SLICE_INLINED_SIZE - back->data.inlined.length;
 153         memcpy(back->data.inlined.bytes + back->data.inlined.length,
 154                s.data.inlined.bytes, cp1);
 155         back->data.inlined.length = GRPC_SLICE_INLINED_SIZE;
 156         maybe_embiggen(sb);
 157         back = &sb->slices[n];
 158         sb->count = n + 1;
 159         back->refcount = nullptr;
 160         back->data.inlined.length =
 161             static_cast<uint8_t>(s.data.inlined.length - cp1);
 162         memcpy(back->data.inlined.bytes, s.data.inlined.bytes + cp1,
 163                s.data.inlined.length - cp1);
 164       }
 165       sb->length += s.data.inlined.length;
 166       return; /* early out */
 167     }
 168   }
 169   grpc_slice_buffer_add_indexed(sb, s);
 170 }
 171
 172 void grpc_slice_buffer_addn(grpc_slice_buffer* sb, grpc_slice* s, size_t n) {
 173   size_t i;
 174   for (i = 0; i < n; i++) {
 175     grpc_slice_buffer_add(sb, s[i]);
 176   }
 177 }
 178
 179 void grpc_slice_buffer_pop(grpc_slice_buffer* sb) {
 180   if (sb->count != 0) {
 181     size_t count = --sb->count;
 182     sb->length -= GRPC_SLICE_LENGTH(sb->slices[count]);
 183   }
 184 }
 185
 186 void grpc_slice_buffer_reset_and_unref_internal(grpc_slice_buffer* sb) {
 187   size_t i;
 188   for (i = 0; i < sb->count; i++) {
 189     grpc_slice_unref_internal(sb->slices[i]);
 190   }
 191
 192   sb->count = 0;
 193   sb->length = 0;
 194   sb->slices = sb->base_slices;
 195 }
 196
 197 void grpc_slice_buffer_reset_and_unref(grpc_slice_buffer* sb) {
 198   if (grpc_core::ExecCtx::Get() == nullptr) {
 199     grpc_core::ExecCtx exec_ctx;
 200     grpc_slice_buffer_reset_and_unref_internal(sb);
 201   } else {
 202     grpc_slice_buffer_reset_and_unref_internal(sb);
 203   }
 204 }
 205
 206 void grpc_slice_buffer_swap(grpc_slice_buffer* a, grpc_slice_buffer* b) {
 207   size_t a_offset = static_cast<size_t>(a->slices - a->base_slices);
 208   size_t b_offset = static_cast<size_t>(b->slices - b->base_slices);
 209
 210   size_t a_count = a->count + a_offset;
 211   size_t b_count = b->count + b_offset;
 212
 213   if (a->base_slices == a->inlined) {
 214     if (b->base_slices == b->inlined) {
 215       /* swap contents of inlined buffer */
 216       grpc_slice temp[GRPC_SLICE_BUFFER_INLINE_ELEMENTS];
 217       memcpy(temp, a->base_slices, a_count * sizeof(grpc_slice));
 218       memcpy(a->base_slices, b->base_slices, b_count * sizeof(grpc_slice));
 219       memcpy(b->base_slices, temp, a_count * sizeof(grpc_slice));
 220     } else {
 221       /* a is inlined, b is not - copy a inlined into b, fix pointers */
 222       a->base_slices = b->base_slices;
 223       b->base_slices = b->inlined;
 224       memcpy(b->base_slices, a->inlined, a_count * sizeof(grpc_slice));
 225     }
 226   } else if (b->base_slices == b->inlined) {
 227     /* b is inlined, a is not - copy b inlined int a, fix pointers */
 228     b->base_slices = a->base_slices;
 229     a->base_slices = a->inlined;
 230     memcpy(a->base_slices, b->inlined, b_count * sizeof(grpc_slice));
 231   } else {
 232     /* no inlining: easy swap */
 233     GPR_SWAP(grpc_slice*, a->base_slices, b->base_slices);
 234   }
 235
 236   /* Update the slices pointers (cannot do a GPR_SWAP on slices fields here).
 237    * Also note that since the base_slices pointers are already swapped we need
 238    * use 'b_offset' for 'a->base_slices' and vice versa */
 239   a->slices = a->base_slices + b_offset;
 240   b->slices = b->base_slices + a_offset;
 241
 242   /* base_slices and slices fields are correctly set. Swap all other fields */
 243   GPR_SWAP(size_t, a->count, b->count);
 244   GPR_SWAP(size_t, a->capacity, b->capacity);
 245   GPR_SWAP(size_t, a->length, b->length);
 246 }
 247
 248 void grpc_slice_buffer_move_into(grpc_slice_buffer* src,
 249                                  grpc_slice_buffer* dst) {
 250   /* anything to move? */
 251   if (src->count == 0) {
 252     return;
 253   }
 254   /* anything in dst? */
 255   if (dst->count == 0) {
 256     grpc_slice_buffer_swap(src, dst);
 257     return;
 258   }
 259   /* both buffers have data - copy, and reset src */
 260   grpc_slice_buffer_addn(dst, src->slices, src->count);
 261   src->count = 0;
 262   src->length = 0;
 263 }
 264
 265 static void slice_buffer_move_first_maybe_ref(grpc_slice_buffer* src, size_t n,
 266                                               grpc_slice_buffer* dst,
 267                                               bool incref) {
 268   GPR_ASSERT(src->length >= n);
 269   if (src->length == n) {
 270     grpc_slice_buffer_move_into(src, dst);
 271     return;
 272   }
 273
 274   size_t output_len = dst->length + n;
 275   size_t new_input_len = src->length - n;
 276
 277   while (src->count > 0) {
 278     grpc_slice slice = grpc_slice_buffer_take_first(src);
 279     size_t slice_len = GRPC_SLICE_LENGTH(slice);
 280     if (n > slice_len) {
 281       grpc_slice_buffer_add(dst, slice);
 282       n -= slice_len;
 283     } else if (n == slice_len) {
 284       grpc_slice_buffer_add(dst, slice);
 285       break;
 286     } else if (incref) { /* n < slice_len */
 287       grpc_slice_buffer_undo_take_first(
 288           src, grpc_slice_split_tail_maybe_ref(&slice, n, GRPC_SLICE_REF_BOTH));
 289       GPR_ASSERT(GRPC_SLICE_LENGTH(slice) == n);
 290       grpc_slice_buffer_add(dst, slice);
 291       break;
 292     } else { /* n < slice_len */
 293       grpc_slice_buffer_undo_take_first(
 294           src, grpc_slice_split_tail_maybe_ref(&slice, n, GRPC_SLICE_REF_TAIL));
 295       GPR_ASSERT(GRPC_SLICE_LENGTH(slice) == n);
 296       grpc_slice_buffer_add_indexed(dst, slice);
 297       break;
 298     }
 299   }
 300   GPR_ASSERT(dst->length == output_len);
 301   GPR_ASSERT(src->length == new_input_len);
 302   GPR_ASSERT(src->count > 0);
 303 }
 304
 305 void grpc_slice_buffer_move_first(grpc_slice_buffer* src, size_t n,
 306                                   grpc_slice_buffer* dst) {
 307   slice_buffer_move_first_maybe_ref(src, n, dst, true);
 308 }
 309
 310 void grpc_slice_buffer_move_first_no_ref(grpc_slice_buffer* src, size_t n,
 311                                          grpc_slice_buffer* dst) {
 312   slice_buffer_move_first_maybe_ref(src, n, dst, false);
 313 }
 314
 315 void grpc_slice_buffer_move_first_into_buffer(grpc_slice_buffer* src, size_t n,
 316                                               void* dst) {
 317   char* dstp = static_cast<char*>(dst);
 318   GPR_ASSERT(src->length >= n);
 319
 320   while (n > 0) {
 321     grpc_slice slice = grpc_slice_buffer_take_first(src);
 322     size_t slice_len = GRPC_SLICE_LENGTH(slice);
 323     if (slice_len > n) {
 324       memcpy(dstp, GRPC_SLICE_START_PTR(slice), n);
 325       grpc_slice_buffer_undo_take_first(
 326           src, grpc_slice_sub_no_ref(slice, n, slice_len));
 327       n = 0;
 328     } else if (slice_len == n) {
 329       memcpy(dstp, GRPC_SLICE_START_PTR(slice), n);
 330       grpc_slice_unref_internal(slice);
 331       n = 0;
 332     } else {
 333       memcpy(dstp, GRPC_SLICE_START_PTR(slice), slice_len);
 334       dstp += slice_len;
 335       n -= slice_len;
 336       grpc_slice_unref_internal(slice);
 337     }
 338   }
 339 }
 340
 341 void grpc_slice_buffer_trim_end(grpc_slice_buffer* sb, size_t n,
 342                                 grpc_slice_buffer* garbage) {
 343   GPR_ASSERT(n <= sb->length);
 344   sb->length -= n;
 345   for (;;) {
 346     size_t idx = sb->count - 1;
 347     grpc_slice slice = sb->slices[idx];
 348     size_t slice_len = GRPC_SLICE_LENGTH(slice);
 349     if (slice_len > n) {
 350       sb->slices[idx] = grpc_slice_split_head(&slice, slice_len - n);
 351       if (garbage) {
 352         grpc_slice_buffer_add_indexed(garbage, slice);
 353       } else {
 354         grpc_slice_unref_internal(slice);
 355       }
 356       return;
 357     } else if (slice_len == n) {
 358       if (garbage) {
 359         grpc_slice_buffer_add_indexed(garbage, slice);
 360       } else {
 361         grpc_slice_unref_internal(slice);
 362       }
 363       sb->count = idx;
 364       return;
 365     } else {
 366       if (garbage) {
 367         grpc_slice_buffer_add_indexed(garbage, slice);
 368       } else {
 369         grpc_slice_unref_internal(slice);
 370       }
 371       n -= slice_len;
 372       sb->count = idx;
 373     }
 374   }
 375 }
 376
 377 grpc_slice grpc_slice_buffer_take_first(grpc_slice_buffer* sb) {
 378   grpc_slice slice;
 379   GPR_ASSERT(sb->count > 0);
 380   slice = sb->slices[0];
 381   sb->slices++;
 382   sb->count--;
 383   sb->length -= GRPC_SLICE_LENGTH(slice);
 384
 385   return slice;
 386 }
 387
 388 void grpc_slice_buffer_remove_first(grpc_slice_buffer* sb) {
 389   GPR_DEBUG_ASSERT(sb->count > 0);
 390   sb->length -= GRPC_SLICE_LENGTH(sb->slices[0]);
 391   grpc_slice_unref_internal(sb->slices[0]);
 392   sb->slices++;
 393   if (--sb->count == 0) {
 394     sb->slices = sb->base_slices;
 395   }
 396 }
 397
 398 void grpc_slice_buffer_sub_first(grpc_slice_buffer* sb, size_t begin,
 399                                  size_t end) {
 400   // TODO(soheil): Introduce a ptr version for sub.
 401   sb->length -= GRPC_SLICE_LENGTH(sb->slices[0]);
 402   sb->slices[0] = grpc_slice_sub_no_ref(sb->slices[0], begin, end);
 403   sb->length += end - begin;
 404 }
 405
 406 void grpc_slice_buffer_undo_take_first(grpc_slice_buffer* sb,
 407                                        grpc_slice slice) {
 408   sb->slices--;
 409   sb->slices[0] = slice;
 410   sb->count++;
 411   sb->length += GRPC_SLICE_LENGTH(slice);
 412 }