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