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 static void maybe_embiggen(grpc_slice_buffer* sb) {
  36   if (sb->count == 0) {
  37     sb->slices = sb->base_slices;
  38   }
  39
  40   /* How far away from sb->base_slices is sb->slices pointer */
  41   size_t slice_offset = static_cast<size_t>(sb->slices - sb->base_slices);
  42   size_t slice_count = sb->count + slice_offset;
  43
  44   if (slice_count == sb->capacity) {
  45     if (sb->base_slices != sb->slices) {
  46       /* Make room by moving elements if there's still space unused */
  47       memmove(sb->base_slices, sb->slices, sb->count * sizeof(grpc_slice));
  48       sb->slices = sb->base_slices;
  49     } else {
  50       /* Allocate more memory if no more space is available */
  51       sb->capacity = GROW(sb->capacity);
  52       GPR_ASSERT(sb->capacity > slice_count);
  53       if (sb->base_slices == sb->inlined) {
  54         sb->base_slices = static_cast<grpc_slice*>(
  55             gpr_malloc(sb->capacity * sizeof(grpc_slice)));
  56         memcpy(sb->base_slices, sb->inlined, slice_count * sizeof(grpc_slice));
  57       } else {
  58         sb->base_slices = static_cast<grpc_slice*>(
  59             gpr_realloc(sb->base_slices, sb->capacity * sizeof(grpc_slice)));
  60       }
  61
  62       sb->slices = sb->base_slices + slice_offset;
  63     }
  64   }
  65 }
  66
  67 void grpc_slice_buffer_init(grpc_slice_buffer* sb) {
  68   sb->count = 0;
  69   sb->length = 0;
  70   sb->capacity = GRPC_SLICE_BUFFER_INLINE_ELEMENTS;
  71   sb->base_slices = sb->slices = sb->inlined;
  72 }
  73
  74 void grpc_slice_buffer_destroy_internal(grpc_slice_buffer* sb) {
  75   grpc_slice_buffer_reset_and_unref_internal(sb);
  76   if (sb->base_slices != sb->inlined) {
  77     gpr_free(sb->base_slices);
  78   }
  79 }
  80
  81 void grpc_slice_buffer_destroy(grpc_slice_buffer* sb) {
  82   if (grpc_core::ExecCtx::Get() == nullptr) {
  83     grpc_core::ExecCtx exec_ctx;
  84     grpc_slice_buffer_destroy_internal(sb);
  85   } else {
  86     grpc_slice_buffer_destroy_internal(sb);
  87   }
  88 }
  89
  90 uint8_t* grpc_slice_buffer_tiny_add(grpc_slice_buffer* sb, size_t n) {
  91   grpc_slice* back;
  92   uint8_t* out;
  93
  94   sb->length += n;
  95
  96   if (sb->count == 0) goto add_new;
  97   back = &sb->slices[sb->count - 1];
  98   if (back->refcount) goto add_new;
  99   if ((back->data.inlined.length + n) > sizeof(back->data.inlined.bytes))
 100     goto add_new;
 101   out = back->data.inlined.bytes + back->data.inlined.length;
 102   back->data.inlined.length =
 103       static_cast<uint8_t>(back->data.inlined.length + n);
 104   return out;
 105
 106 add_new:
 107   maybe_embiggen(sb);
 108   back = &sb->slices[sb->count];
 109   sb->count++;
 110   back->refcount = nullptr;
 111   back->data.inlined.length = static_cast<uint8_t>(n);
 112   return back->data.inlined.bytes;
 113 }
 114
 115 size_t grpc_slice_buffer_add_indexed(grpc_slice_buffer* sb, grpc_slice s) {
 116   size_t out = sb->count;
 117   maybe_embiggen(sb);
 118   sb->slices[out] = s;
 119   sb->length += GRPC_SLICE_LENGTH(s);
 120   sb->count = out + 1;
 121   return out;
 122 }
 123
 124 void grpc_slice_buffer_add(grpc_slice_buffer* sb, grpc_slice s) {
 125   size_t n = sb->count;
 126   /* if both the last slice in the slice buffer and the slice being added
 127      are inlined (that is, that they carry their data inside the slice data
 128      structure), and the back slice is not full, then concatenate directly
 129      into the back slice, preventing many small slices being passed into
 130      writes */
 131   if (!s.refcount && n) {
 132     grpc_slice* back = &sb->slices[n - 1];
 133     if (!back->refcount &&
 134         back->data.inlined.length < GRPC_SLICE_INLINED_SIZE) {
 135       if (s.data.inlined.length + back->data.inlined.length <=
 136           GRPC_SLICE_INLINED_SIZE) {
 137         memcpy(back->data.inlined.bytes + back->data.inlined.length,
 138                s.data.inlined.bytes, s.data.inlined.length);
 139         back->data.inlined.length = static_cast<uint8_t>(
 140             back->data.inlined.length + s.data.inlined.length);
 141       } else {
 142         size_t cp1 = GRPC_SLICE_INLINED_SIZE - back->data.inlined.length;
 143         memcpy(back->data.inlined.bytes + back->data.inlined.length,
 144                s.data.inlined.bytes, cp1);
 145         back->data.inlined.length = GRPC_SLICE_INLINED_SIZE;
 146         maybe_embiggen(sb);
 147         back = &sb->slices[n];
 148         sb->count = n + 1;
 149         back->refcount = nullptr;
 150         back->data.inlined.length =
 151             static_cast<uint8_t>(s.data.inlined.length - cp1);
 152         memcpy(back->data.inlined.bytes, s.data.inlined.bytes + cp1,
 153                s.data.inlined.length - cp1);
 154       }
 155       sb->length += s.data.inlined.length;
 156       return; /* early out */
 157     }
 158   }
 159   grpc_slice_buffer_add_indexed(sb, s);
 160 }
 161
 162 void grpc_slice_buffer_addn(grpc_slice_buffer* sb, grpc_slice* s, size_t n) {
 163   size_t i;
 164   for (i = 0; i < n; i++) {
 165     grpc_slice_buffer_add(sb, s[i]);
 166   }
 167 }
 168
 169 void grpc_slice_buffer_pop(grpc_slice_buffer* sb) {
 170   if (sb->count != 0) {
 171     size_t count = --sb->count;
 172     sb->length -= GRPC_SLICE_LENGTH(sb->slices[count]);
 173   }
 174 }
 175
 176 void grpc_slice_buffer_reset_and_unref_internal(grpc_slice_buffer* sb) {
 177   size_t i;
 178   for (i = 0; i < sb->count; i++) {
 179     grpc_slice_unref_internal(sb->slices[i]);
 180   }
 181
 182   sb->count = 0;
 183   sb->length = 0;
 184   sb->slices = sb->base_slices;
 185 }
 186
 187 void grpc_slice_buffer_reset_and_unref(grpc_slice_buffer* sb) {
 188   if (grpc_core::ExecCtx::Get() == nullptr) {
 189     grpc_core::ExecCtx exec_ctx;
 190     grpc_slice_buffer_reset_and_unref_internal(sb);
 191   } else {
 192     grpc_slice_buffer_reset_and_unref_internal(sb);
 193   }
 194 }
 195
 196 void grpc_slice_buffer_swap(grpc_slice_buffer* a, grpc_slice_buffer* b) {
 197   size_t a_offset = static_cast<size_t>(a->slices - a->base_slices);
 198   size_t b_offset = static_cast<size_t>(b->slices - b->base_slices);
 199
 200   size_t a_count = a->count + a_offset;
 201   size_t b_count = b->count + b_offset;
 202
 203   if (a->base_slices == a->inlined) {
 204     if (b->base_slices == b->inlined) {
 205       /* swap contents of inlined buffer */
 206       grpc_slice temp[GRPC_SLICE_BUFFER_INLINE_ELEMENTS];
 207       memcpy(temp, a->base_slices, a_count * sizeof(grpc_slice));
 208       memcpy(a->base_slices, b->base_slices, b_count * sizeof(grpc_slice));
 209       memcpy(b->base_slices, temp, a_count * sizeof(grpc_slice));
 210     } else {
 211       /* a is inlined, b is not - copy a inlined into b, fix pointers */
 212       a->base_slices = b->base_slices;
 213       b->base_slices = b->inlined;
 214       memcpy(b->base_slices, a->inlined, a_count * sizeof(grpc_slice));
 215     }
 216   } else if (b->base_slices == b->inlined) {
 217     /* b is inlined, a is not - copy b inlined int a, fix pointers */
 218     b->base_slices = a->base_slices;
 219     a->base_slices = a->inlined;
 220     memcpy(a->base_slices, b->inlined, b_count * sizeof(grpc_slice));
 221   } else {
 222     /* no inlining: easy swap */
 223     GPR_SWAP(grpc_slice*, a->base_slices, b->base_slices);
 224   }
 225
 226   /* Update the slices pointers (cannot do a GPR_SWAP on slices fields here).
 227    * Also note that since the base_slices pointers are already swapped we need
 228    * use 'b_offset' for 'a->base_slices' and vice versa */
 229   a->slices = a->base_slices + b_offset;
 230   b->slices = b->base_slices + a_offset;
 231
 232   /* base_slices and slices fields are correctly set. Swap all other fields */
 233   GPR_SWAP(size_t, a->count, b->count);
 234   GPR_SWAP(size_t, a->capacity, b->capacity);
 235   GPR_SWAP(size_t, a->length, b->length);
 236 }
 237
 238 void grpc_slice_buffer_move_into(grpc_slice_buffer* src,
 239                                  grpc_slice_buffer* dst) {
 240   /* anything to move? */
 241   if (src->count == 0) {
 242     return;
 243   }
 244   /* anything in dst? */
 245   if (dst->count == 0) {
 246     grpc_slice_buffer_swap(src, dst);
 247     return;
 248   }
 249   /* both buffers have data - copy, and reset src */
 250   grpc_slice_buffer_addn(dst, src->slices, src->count);
 251   src->count = 0;
 252   src->length = 0;
 253 }
 254
 255 static void slice_buffer_move_first_maybe_ref(grpc_slice_buffer* src, size_t n,
 256                                               grpc_slice_buffer* dst,
 257                                               bool incref) {
 258   GPR_ASSERT(src->length >= n);
 259   if (src->length == n) {
 260     grpc_slice_buffer_move_into(src, dst);
 261     return;
 262   }
 263
 264   size_t output_len = dst->length + n;
 265   size_t new_input_len = src->length - n;
 266
 267   while (src->count > 0) {
 268     grpc_slice slice = grpc_slice_buffer_take_first(src);
 269     size_t slice_len = GRPC_SLICE_LENGTH(slice);
 270     if (n > slice_len) {
 271       grpc_slice_buffer_add(dst, slice);
 272       n -= slice_len;
 273     } else if (n == slice_len) {
 274       grpc_slice_buffer_add(dst, slice);
 275       break;
 276     } else if (incref) { /* n < slice_len */
 277       grpc_slice_buffer_undo_take_first(
 278           src, grpc_slice_split_tail_maybe_ref(&slice, n, GRPC_SLICE_REF_BOTH));
 279       GPR_ASSERT(GRPC_SLICE_LENGTH(slice) == n);
 280       grpc_slice_buffer_add(dst, slice);
 281       break;
 282     } else { /* n < slice_len */
 283       grpc_slice_buffer_undo_take_first(
 284           src, grpc_slice_split_tail_maybe_ref(&slice, n, GRPC_SLICE_REF_TAIL));
 285       GPR_ASSERT(GRPC_SLICE_LENGTH(slice) == n);
 286       grpc_slice_buffer_add_indexed(dst, slice);
 287       break;
 288     }
 289   }
 290   GPR_ASSERT(dst->length == output_len);
 291   GPR_ASSERT(src->length == new_input_len);
 292   GPR_ASSERT(src->count > 0);
 293 }
 294
 295 void grpc_slice_buffer_move_first(grpc_slice_buffer* src, size_t n,
 296                                   grpc_slice_buffer* dst) {
 297   slice_buffer_move_first_maybe_ref(src, n, dst, true);
 298 }
 299
 300 void grpc_slice_buffer_move_first_no_ref(grpc_slice_buffer* src, size_t n,
 301                                          grpc_slice_buffer* dst) {
 302   slice_buffer_move_first_maybe_ref(src, n, dst, false);
 303 }
 304
 305 void grpc_slice_buffer_move_first_into_buffer(grpc_slice_buffer* src, size_t n,
 306                                               void* dst) {
 307   char* dstp = static_cast<char*>(dst);
 308   GPR_ASSERT(src->length >= n);
 309
 310   while (n > 0) {
 311     grpc_slice slice = grpc_slice_buffer_take_first(src);
 312     size_t slice_len = GRPC_SLICE_LENGTH(slice);
 313     if (slice_len > n) {
 314       memcpy(dstp, GRPC_SLICE_START_PTR(slice), n);
 315       grpc_slice_buffer_undo_take_first(
 316           src, grpc_slice_sub_no_ref(slice, n, slice_len));
 317       n = 0;
 318     } else if (slice_len == n) {
 319       memcpy(dstp, GRPC_SLICE_START_PTR(slice), n);
 320       grpc_slice_unref_internal(slice);
 321       n = 0;
 322     } else {
 323       memcpy(dstp, GRPC_SLICE_START_PTR(slice), slice_len);
 324       dstp += slice_len;
 325       n -= slice_len;
 326       grpc_slice_unref_internal(slice);
 327     }
 328   }
 329 }
 330
 331 void grpc_slice_buffer_trim_end(grpc_slice_buffer* sb, size_t n,
 332                                 grpc_slice_buffer* garbage) {
 333   GPR_ASSERT(n <= sb->length);
 334   sb->length -= n;
 335   for (;;) {
 336     size_t idx = sb->count - 1;
 337     grpc_slice slice = sb->slices[idx];
 338     size_t slice_len = GRPC_SLICE_LENGTH(slice);
 339     if (slice_len > n) {
 340       sb->slices[idx] = grpc_slice_split_head(&slice, slice_len - n);
 341       if (garbage) {
 342         grpc_slice_buffer_add_indexed(garbage, slice);
 343       } else {
 344         grpc_slice_unref_internal(slice);
 345       }
 346       return;
 347     } else if (slice_len == n) {
 348       if (garbage) {
 349         grpc_slice_buffer_add_indexed(garbage, slice);
 350       } else {
 351         grpc_slice_unref_internal(slice);
 352       }
 353       sb->count = idx;
 354       return;
 355     } else {
 356       if (garbage) {
 357         grpc_slice_buffer_add_indexed(garbage, slice);
 358       } else {
 359         grpc_slice_unref_internal(slice);
 360       }
 361       n -= slice_len;
 362       sb->count = idx;
 363     }
 364   }
 365 }
 366
 367 grpc_slice grpc_slice_buffer_take_first(grpc_slice_buffer* sb) {
 368   grpc_slice slice;
 369   GPR_ASSERT(sb->count > 0);
 370   slice = sb->slices[0];
 371   sb->slices++;
 372   sb->count--;
 373   sb->length -= GRPC_SLICE_LENGTH(slice);
 374
 375   return slice;
 376 }
 377
 378 void grpc_slice_buffer_undo_take_first(grpc_slice_buffer* sb,
 379                                        grpc_slice slice) {
 380   sb->slices--;
 381   sb->slices[0] = slice;
 382   sb->count++;
 383   sb->length += GRPC_SLICE_LENGTH(slice);
 384 }