Seastar
High performance C++ framework for concurrent servers
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
chunked_fifo.hh
1/*
2 * This file is open source software, licensed to you under the terms
3 * of the Apache License, Version 2.0 (the "License"). See the NOTICE file
4 * distributed with this work for additional information regarding copyright
5 * ownership. You may not use this file except in compliance with the License.
6 *
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,
12 * software distributed under the License is distributed on an
13 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14 * KIND, either express or implied. See the License for the
15 * specific language governing permissions and limitations
16 * under the License.
17 */
18/*
19 * Copyright (C) 2016 ScyllaDB Ltd.
20 */
21
22#pragma once
23
24#ifndef SEASTAR_MODULE
25#include <algorithm>
26#include <cassert>
27#include <type_traits>
28#include <seastar/util/modules.hh>
29#endif
30
31namespace seastar {
32
33// An unbounded FIFO queue of objects of type T.
34//
35// It provides operations to push items in one end of the queue, and pop them
36// from the other end of the queue - both operations are guaranteed O(1)
37// (not just amortized O(1)). The size() operation is also O(1).
38// chunked_fifo also guarantees that the largest contiguous memory allocation
39// it does is O(1). The total memory used is, of course, O(N).
40//
41// How does chunked_fifo differ from std::list<>, circular_buffer<> and
42// std::deque()?
43//
44// std::list<> can also make all the above guarantees, but is inefficient -
45// both at run speed (every operation requires an allocation), and in memory
46// use. Much more efficient than std::list<> is our circular_buffer<>, which
47// allocates a contiguous array to hold the items and only reallocates it,
48// exponentially, when the queue grows. On one test of several different
49// push/pop scenarios, circular_buffer<> was between 5 and 20 times faster
50// than std::list, and also used considerably less memory.
51// The problem with circular_buffer<> is that gives up on the last guarantee
52// we made above: circular_buffer<> allocates all the items in one large
53// contiguous allocation - that might not be possible when the memory is
54// highly fragmented.
55// std::deque<> aims to solve the contiguous allocation problem by allocating
56// smaller chunks of the queue, and keeping a list of them in an array. This
57// array is necessary to allow for O(1) random access to any element, a
58// feature which we do not need; But this array is itself contiguous so
59// std::deque<> attempts larger contiguous allocations the larger the queue
60// gets: std::deque<>'s contiguous allocation is still O(N) and in fact
61// exactly 1/64 of the size of circular_buffer<>'s contiguous allocation.
62// So it's an improvement over circular_buffer<>, but not a full solution.
63//
64// chunked_fifo<> is such a solution: it also allocates the queue in fixed-
65// size chunks (just like std::deque) but holds them in a linked list, not
66// a contiguous array, so there are no large contiguous allocations.
67//
68// Unlike std::deque<> or circular_buffer<>, chunked_fifo only provides the
69// operations needed by std::queue, i.e.,: empty(), size(), front(), back(),
70// push_back() and pop_front(). For simplicity, we do *not* implement other
71// possible operations, like inserting or deleting elements from the "wrong"
72// side of the queue or from the middle, nor random-access to items in the
73// middle of the queue. However, chunked_fifo does allow iterating over all
74// of the queue's elements without popping them, a feature which std::queue
75// is missing.
76//
77// Another feature of chunked_fifo which std::deque is missing is the ability
78// to control the chunk size, as a template parameter. In std::deque the
79// chunk size is undocumented and fixed - in gcc, it is always 512 bytes.
80// chunked_fifo, on the other hand, makes the chunk size (in number of items
81// instead of bytes) a template parameter; In situations where the queue is
82// expected to become very long, using a larger chunk size might make sense
83// because it will result in fewer allocations.
84//
85// chunked_fifo uses uninitialized storage for unoccupied elements, and thus
86// uses move/copy constructors instead of move/copy assignments, which are
87// less efficient.
88
89SEASTAR_MODULE_EXPORT
90template <typename T, size_t items_per_chunk = 128>
92 static_assert((items_per_chunk & (items_per_chunk - 1)) == 0,
93 "chunked_fifo chunk size must be power of two");
94 union maybe_item {
95 maybe_item() noexcept {}
96 ~maybe_item() {}
97 T data;
98 };
99 struct chunk {
100 maybe_item items[items_per_chunk];
101 struct chunk* next;
102 // begin and end interpreted mod items_per_chunk
103 unsigned begin;
104 unsigned end;
105
106 // the number of elements in this chunk
107 size_t size() const {
108 return end - begin;
109 }
110 };
111 // We pop from the chunk at _front_chunk. This chunk is then linked to
112 // the following chunks via the "next" link. _back_chunk points to the
113 // last chunk in this list, and it is where we push.
114 chunk* _front_chunk = nullptr; // where we pop
115 chunk* _back_chunk = nullptr; // where we push
116 // We want an O(1) size but don't want to maintain a size() counter
117 // because this will slow down every push and pop operation just for
118 // the rare size() call. Instead, we just keep a count of chunks (which
119 // doesn't change on every push or pop), from which we can calculate
120 // size() when needed, and still be O(1).
121 // This assumes the invariant that all middle chunks (except the front
122 // and back) are always full.
123 size_t _nchunks = 0;
124 // A list of freed chunks, to support reserve() and to improve
125 // performance of repeated push and pop, especially on an empty queue.
126 // It is a performance/memory tradeoff how many freed chunks to keep
127 // here (see save_free_chunks constant below).
128 chunk* _free_chunks = nullptr;
129 size_t _nfree_chunks = 0;
130public:
131 using value_type = T;
132 using size_type = size_t;
133 using reference = T&;
134 using pointer = T*;
135 using const_reference = const T&;
136 using const_pointer = const T*;
137
138private:
139 template <bool IsConst>
140 class basic_iterator {
141 friend class chunked_fifo;
142
143 public:
144 using iterator_category = std::forward_iterator_tag;
145 using difference_type = std::ptrdiff_t;
146 using value_type = std::conditional_t<IsConst, const T, T>;
147 using pointer = value_type*;
148 using reference = value_type&;
149
150 private:
151 using chunk_t = std::conditional_t<IsConst, const chunk, chunk>;
152 chunk_t* _chunk = nullptr;
153 size_t _item_index = 0;
154
155 protected:
156 inline explicit basic_iterator(chunk_t* c) noexcept;
157 inline basic_iterator(chunk_t* c, size_t item_index) noexcept;
158
159 public:
160 basic_iterator() noexcept = default;
161 template<bool OtherIsConst, std::enable_if_t<IsConst && !OtherIsConst, int> = 0>
162 inline basic_iterator(const basic_iterator<OtherIsConst>& o) noexcept
163 : basic_iterator{o._chunk, o._item_index} {}
164 inline bool operator==(const basic_iterator& o) const noexcept;
165 inline bool operator!=(const basic_iterator& o) const noexcept;
166 inline pointer operator->() const noexcept;
167 inline reference operator*() const noexcept;
168 inline basic_iterator operator++(int) noexcept;
169 basic_iterator& operator++() noexcept;
170 };
171
172public:
173 using iterator = basic_iterator<false>;
174 using const_iterator = basic_iterator<true>;
175
176public:
177 chunked_fifo() noexcept = default;
178 chunked_fifo(chunked_fifo&& x) noexcept;
179 chunked_fifo(const chunked_fifo& X) = delete;
181 chunked_fifo& operator=(const chunked_fifo&) = delete;
182 chunked_fifo& operator=(chunked_fifo&&) noexcept;
183 inline void push_back(const T& data);
184 inline void push_back(T&& data);
185 T& back() noexcept;
186 const T& back() const noexcept;
187 template <typename... A>
188 inline void emplace_back(A&&... args);
189 inline T& front() const noexcept;
190 inline void pop_front() noexcept;
191 inline bool empty() const noexcept;
192 inline size_t size() const noexcept;
193 // Pop the first n elements from the fifo. Equivalent to calling pop_front()
194 // n times, though likely to be faster for n greater than 1. The fifo must
195 // contain at least n elements or the behavior is undefined.
196 void pop_front_n(size_t n) noexcept;
197 void clear() noexcept;
198 // reserve(n) ensures that at least (n - size()) further push() calls can
199 // be served without needing new memory allocation.
200 // Calling pop()s between these push()es is also allowed and does not
201 // alter this guarantee.
202 // Note that reserve() does not reduce the amount of memory already
203 // reserved - use shrink_to_fit() for that.
204 void reserve(size_t n);
205 // shrink_to_fit() frees memory held, but unused, by the queue. Such
206 // unused memory might exist after pops, or because of reserve().
207 void shrink_to_fit() noexcept;
208 inline iterator begin() noexcept;
209 inline iterator end() noexcept;
210 inline const_iterator begin() const noexcept;
211 inline const_iterator end() const noexcept;
212 inline const_iterator cbegin() const noexcept;
213 inline const_iterator cend() const noexcept;
214private:
215 void back_chunk_new();
216 void front_chunk_delete() noexcept;
217 inline void ensure_room_back();
218 void undo_room_back() noexcept;
219 static inline size_t mask(size_t idx) noexcept;
220
221};
222
223template <typename T, size_t items_per_chunk>
224template <bool IsConst>
225inline
226chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::basic_iterator(chunk_t* c) noexcept : _chunk(c), _item_index(_chunk ? _chunk->begin : 0) {
227}
228
229template <typename T, size_t items_per_chunk>
230template <bool IsConst>
231inline
232chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::basic_iterator(chunk_t* c, size_t item_index) noexcept : _chunk(c), _item_index(item_index) {
233}
234
235template <typename T, size_t items_per_chunk>
236template <bool IsConst>
237inline bool
238chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator==(const basic_iterator& o) const noexcept {
239 return _chunk == o._chunk && _item_index == o._item_index;
240}
241
242template <typename T, size_t items_per_chunk>
243template <bool IsConst>
244inline bool
245chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator!=(const basic_iterator& o) const noexcept {
246 return !(*this == o);
247}
248
249template <typename T, size_t items_per_chunk>
250template <bool IsConst>
251inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>::pointer
252chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator->() const noexcept {
253 return &_chunk->items[chunked_fifo::mask(_item_index)].data;
254}
255
256template <typename T, size_t items_per_chunk>
257template <bool IsConst>
258inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>::reference
259chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator*() const noexcept {
260 return _chunk->items[chunked_fifo::mask(_item_index)].data;
261}
262
263template <typename T, size_t items_per_chunk>
264template <bool IsConst>
265inline typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>
266chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator++(int) noexcept {
267 auto it = *this;
268 ++(*this);
269 return it;
270}
271
272template <typename T, size_t items_per_chunk>
273template <bool IsConst>
274typename chunked_fifo<T, items_per_chunk>::template basic_iterator<IsConst>&
275chunked_fifo<T, items_per_chunk>::basic_iterator<IsConst>::operator++() noexcept {
276 ++_item_index;
277 if (_item_index == _chunk->end) {
278 _chunk = _chunk->next;
279 _item_index = _chunk ? _chunk->begin : 0;
280 }
281 return *this;
282}
283
284template <typename T, size_t items_per_chunk>
285inline
286chunked_fifo<T, items_per_chunk>::chunked_fifo(chunked_fifo&& x) noexcept
287 : _front_chunk(x._front_chunk)
288 , _back_chunk(x._back_chunk)
289 , _nchunks(x._nchunks)
290 , _free_chunks(x._free_chunks)
291 , _nfree_chunks(x._nfree_chunks) {
292 x._front_chunk = nullptr;
293 x._back_chunk = nullptr;
294 x._nchunks = 0;
295 x._free_chunks = nullptr;
296 x._nfree_chunks = 0;
297}
298
299template <typename T, size_t items_per_chunk>
300inline
301chunked_fifo<T, items_per_chunk>&
302chunked_fifo<T, items_per_chunk>::operator=(chunked_fifo&& x) noexcept {
303 if (&x != this) {
304 this->~chunked_fifo();
305 new (this) chunked_fifo(std::move(x));
306 }
307 return *this;
308}
309
310template <typename T, size_t items_per_chunk>
311inline size_t
312chunked_fifo<T, items_per_chunk>::mask(size_t idx) noexcept {
313 return idx & (items_per_chunk - 1);
314}
315
316template <typename T, size_t items_per_chunk>
317inline bool
318chunked_fifo<T, items_per_chunk>::empty() const noexcept {
319 return _front_chunk == nullptr;
320}
321
322template <typename T, size_t items_per_chunk>
323inline size_t
324chunked_fifo<T, items_per_chunk>::size() const noexcept{
325 if (_front_chunk == nullptr) {
326 return 0;
327 } else if (_back_chunk == _front_chunk) {
328 // Single chunk.
329 return _front_chunk->end - _front_chunk->begin;
330 } else {
331 return _front_chunk->end - _front_chunk->begin
332 +_back_chunk->end - _back_chunk->begin
333 + (_nchunks - 2) * items_per_chunk;
334 }
335}
336
337template <typename T, size_t items_per_chunk>
338void chunked_fifo<T, items_per_chunk>::clear() noexcept {
339 pop_front_n(size());
340}
341
342template <typename T, size_t items_per_chunk>
343void chunked_fifo<T, items_per_chunk>::pop_front_n(size_t n) noexcept {
344 while (n) {
345 assert(_front_chunk && "pop_front_n n too large");
346
347 auto target = _front_chunk;
348 unsigned delete_count = std::min(target->size(), n);
349
350 for (auto i = target->begin, e = i + delete_count; i != e; i++) {
351 target->items[mask(i)].data.~T();
352 }
353
354 target->begin += delete_count;
355 n -= delete_count;
356
357 if (target->size() == 0) {
358 front_chunk_delete();
359 }
360 }
361}
362
363
364
365template <typename T, size_t items_per_chunk> void
366chunked_fifo<T, items_per_chunk>::shrink_to_fit() noexcept {
367 while (_free_chunks) {
368 auto next = _free_chunks->next;
369 delete _free_chunks;
370 _free_chunks = next;
371 }
372 _nfree_chunks = 0;
373}
374
375template <typename T, size_t items_per_chunk>
376chunked_fifo<T, items_per_chunk>::~chunked_fifo() {
377 clear();
378 shrink_to_fit();
379}
380
381template <typename T, size_t items_per_chunk>
382void
383chunked_fifo<T, items_per_chunk>::back_chunk_new() {
384 chunk *old = _back_chunk;
385 if (_free_chunks) {
386 _back_chunk = _free_chunks;
387 _free_chunks = _free_chunks->next;
388 --_nfree_chunks;
389 } else {
390 _back_chunk = new chunk;
391 }
392 _back_chunk->next = nullptr;
393 _back_chunk->begin = 0;
394 _back_chunk->end = 0;
395 if (old) {
396 old->next = _back_chunk;
397 }
398 if (_front_chunk == nullptr) {
399 _front_chunk = _back_chunk;
400 }
401 _nchunks++;
402}
403
404
405template <typename T, size_t items_per_chunk>
406inline void
407chunked_fifo<T, items_per_chunk>::ensure_room_back() {
408 // If we don't have a back chunk or it's full, we need to create a new one
409 if (_back_chunk == nullptr ||
410 (_back_chunk->end - _back_chunk->begin) == items_per_chunk) {
411 back_chunk_new();
412 }
413}
414
415template <typename T, size_t items_per_chunk>
416void
417chunked_fifo<T, items_per_chunk>::undo_room_back() noexcept {
418 // If we failed creating a new item after ensure_room_back() created a
419 // new empty chunk, we must remove it, or empty() will be incorrect
420 // (either immediately, if the fifo was empty, or when all the items are
421 // popped, if it already had items).
422 if (_back_chunk->begin == _back_chunk->end) {
423 delete _back_chunk;
424 --_nchunks;
425 if (_nchunks == 0) {
426 _back_chunk = nullptr;
427 _front_chunk = nullptr;
428 } else {
429 // Because we don't usually pop from the back, we don't have a "prev"
430 // pointer so we need to find the previous chunk the hard and slow
431 // way. B
432 chunk *old = _back_chunk;
433 _back_chunk = _front_chunk;
434 while (_back_chunk->next != old) {
435 _back_chunk = _back_chunk->next;
436 }
437 _back_chunk->next = nullptr;
438 }
439 }
440
441}
442
443template <typename T, size_t items_per_chunk>
444template <typename... Args>
445inline void
446chunked_fifo<T, items_per_chunk>::emplace_back(Args&&... args) {
447 ensure_room_back();
448 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
449 try {
450 new(p) T(std::forward<Args>(args)...);
451 } catch(...) {
452 undo_room_back();
453 throw;
454 }
455 ++_back_chunk->end;
456}
457
458template <typename T, size_t items_per_chunk>
459inline void
460chunked_fifo<T, items_per_chunk>::push_back(const T& data) {
461 ensure_room_back();
462 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
463 try {
464 new(p) T(data);
465 } catch(...) {
466 undo_room_back();
467 throw;
468 }
469 ++_back_chunk->end;
470}
471
472template <typename T, size_t items_per_chunk>
473inline void
474chunked_fifo<T, items_per_chunk>::push_back(T&& data) {
475 ensure_room_back();
476 auto p = &_back_chunk->items[mask(_back_chunk->end)].data;
477 try {
478 new(p) T(std::move(data));
479 } catch(...) {
480 undo_room_back();
481 throw;
482 }
483 ++_back_chunk->end;
484}
485
486template <typename T, size_t items_per_chunk>
487inline
488T&
489chunked_fifo<T, items_per_chunk>::back() noexcept {
490 return _back_chunk->items[mask(_back_chunk->end - 1)].data;
491}
492
493template <typename T, size_t items_per_chunk>
494inline
495const T&
496chunked_fifo<T, items_per_chunk>::back() const noexcept {
497 return _back_chunk->items[mask(_back_chunk->end - 1)].data;
498}
499
500template <typename T, size_t items_per_chunk>
501inline T&
502chunked_fifo<T, items_per_chunk>::front() const noexcept {
503 return _front_chunk->items[mask(_front_chunk->begin)].data;
504}
505
506template <typename T, size_t items_per_chunk>
507inline void
508chunked_fifo<T, items_per_chunk>::front_chunk_delete() noexcept {
509 chunk *next = _front_chunk->next;
510 // Certain use cases may need to repeatedly allocate and free a chunk -
511 // an obvious example is an empty queue to which we push, and then pop,
512 // repeatedly. Another example is pushing and popping to a non-empty queue
513 // we push and pop at different chunks so we need to free and allocate a
514 // chunk every items_per_chunk operations.
515 // The solution is to keep a list of freed chunks instead of freeing them
516 // immediately. There is a performance/memory tradeoff of how many freed
517 // chunks to save: If we save them all, the queue can never shrink from
518 // its maximum memory use (this is how circular_buffer behaves).
519 // The ad-hoc choice made here is to limit the number of saved chunks to 1,
520 // but this could easily be made a configuration option.
521 static constexpr int save_free_chunks = 1;
522 if (_nfree_chunks < save_free_chunks) {
523 _front_chunk->next = _free_chunks;
524 _free_chunks = _front_chunk;
525 ++_nfree_chunks;
526 } else {
527 delete _front_chunk;
528 }
529 // If we only had one chunk, _back_chunk is gone too.
530 if (_back_chunk == _front_chunk) {
531 _back_chunk = nullptr;
532 }
533 _front_chunk = next;
534 --_nchunks;
535}
536
537template <typename T, size_t items_per_chunk>
538inline void
539chunked_fifo<T, items_per_chunk>::pop_front() noexcept {
540 front().~T();
541 // If the front chunk has become empty, we need to free remove it and use
542 // the next one.
543 if (++_front_chunk->begin == _front_chunk->end) {
544 front_chunk_delete();
545 }
546}
547
548template <typename T, size_t items_per_chunk>
549void chunked_fifo<T, items_per_chunk>::reserve(size_t n) {
550 // reserve() guarantees that (n - size()) additional push()es will
551 // succeed without reallocation:
552 if (n <= size()) {
553 return;
554 }
555 size_t need = n - size();
556 // If we already have a back chunk, it might have room for some pushes
557 // before filling up, so decrease "need":
558 if (_back_chunk) {
559 size_t back_chunk_n = items_per_chunk - (_back_chunk->end - _back_chunk->begin);
560 need -= std::min(back_chunk_n, need);
561 }
562 size_t needed_chunks = (need + items_per_chunk - 1) / items_per_chunk;
563 // If we already have some freed chunks saved, we need to allocate fewer
564 // additional chunks, or none at all
565 if (needed_chunks <= _nfree_chunks) {
566 return;
567 }
568 needed_chunks -= _nfree_chunks;
569 while (needed_chunks--) {
570 chunk *c = new chunk;
571 c->next = _free_chunks;
572 _free_chunks = c;
573 ++_nfree_chunks;
574 }
575}
576
577template <typename T, size_t items_per_chunk>
578inline typename chunked_fifo<T, items_per_chunk>::iterator
579chunked_fifo<T, items_per_chunk>::begin() noexcept {
580 return iterator(_front_chunk);
581}
582
583template <typename T, size_t items_per_chunk>
584inline typename chunked_fifo<T, items_per_chunk>::iterator
585chunked_fifo<T, items_per_chunk>::end() noexcept {
586 return iterator(nullptr);
587}
588
589template <typename T, size_t items_per_chunk>
590inline typename chunked_fifo<T, items_per_chunk>::const_iterator
591chunked_fifo<T, items_per_chunk>::begin() const noexcept {
592 return const_iterator(_front_chunk);
593}
594
595template <typename T, size_t items_per_chunk>
596inline typename chunked_fifo<T, items_per_chunk>::const_iterator
597chunked_fifo<T, items_per_chunk>::end() const noexcept {
598 return const_iterator(nullptr);
599}
600
601template <typename T, size_t items_per_chunk>
602inline typename chunked_fifo<T, items_per_chunk>::const_iterator
603chunked_fifo<T, items_per_chunk>::cbegin() const noexcept {
604 return const_iterator(_front_chunk);
605}
606
607template <typename T, size_t items_per_chunk>
608inline typename chunked_fifo<T, items_per_chunk>::const_iterator
609chunked_fifo<T, items_per_chunk>::cend() const noexcept {
610 return const_iterator(nullptr);
611}
612
613}
Definition: chunked_fifo.hh:91
Seastar API namespace.
Definition: abort_on_ebadf.hh:26