Lines Matching +full:not +full:- +full:swapped
1 .. SPDX-License-Identifier: GPL-2.0 OR GFDL-1.2-no-invariants-only
19 ---------------------------------
22 - where new writes happen in the ring buffer.
25 - where new reads happen in the ring buffer.
28 - the task that writes into the ring buffer (same as writer)
31 - same as producer
34 - the task that reads from the buffer (same as reader)
37 - same as consumer.
40 - A page outside the ring buffer used solely (for the most part)
44 - a pointer to the page that the reader will use next
47 - a pointer to the page that will be written to next
50 - a pointer to the page with the last finished non-nested write.
53 - hardware-assisted atomic transaction that performs the following::
61 R gets the previous A regardless if A is updated with B or not.
67 -----------------------
80 No two writers can write at the same time (on the same per-cpu buffer),
110 At initialization a reader page is allocated for the reader that is not
121 allocated but is not attached to the list. When the reader wants
122 to read from the buffer, if its page is empty (like it is on start-up),
131 A sample of how the reader page is swapped: Note this does not
137 +------+
140 +------+
141 +---+ +---+ +---+
142 | |-->| |-->| |
143 | |<--| |<--| |
144 +---+ +---+ +---+
146 | +-------------+ |
147 +-----------------+
150 +------+
152 |page |-------------------+
153 +------+ v
154 | +---+ +---+ +---+
155 | | |-->| |-->| |
156 | | |<--| |<--| |<-+
157 | +---+ +---+ +---+ |
159 | | +-------------+ | |
160 | +-----------------+ |
161 +------------------------------------+
163 +------+
165 |page |-------------------+
166 +------+ <---------------+ v
167 | ^ +---+ +---+ +---+
168 | | | |-->| |-->| |
169 | | | | | |<--| |<-+
170 | | +---+ +---+ +---+ |
172 | | +-------------+ | |
173 | +-----------------------------+ |
174 +------------------------------------+
176 +------+
178 |page |-------------------+
179 +------+ <---------------+ v
180 | ^ +---+ +---+ +---+
181 | | | | | |-->| |
182 | | New | | | |<--| |<-+
183 | | Reader +---+ +---+ +---+ |
184 | | page ----^ | |
186 | +-----------------------------+ |
187 +------------------------------------+
191 It is possible that the page swapped is the commit page and the tail page,
199 +---+ | |
200 | |<----------+ |
201 | |<------------------------+
202 | |------+
203 +---+ |
206 +---+ +---+ +---+ +---+
207 <---| |--->| |--->| |--->| |--->
208 --->| |<---| |<---| |<---| |<---
209 +---+ +---+ +---+ +---+
220 - The page used solely by the reader and is not part
221 of the ring buffer (may be swapped in)
224 - the next page in the ring buffer that will be swapped
228 - the page where the next write will take place.
231 - the page that last finished a write.
234 writer stack. A writer that preempts another writer will not move the
249 +---------+
251 +---------+ <--- given back to writer (current commit)
253 +---------+ <--- tail pointer
255 +---------+
260 +---------+
262 +---------+
264 +---------+ <--- next position for write (current commit)
266 +---------+
272 +---------+
274 +---------+ <-- current commit
276 +---------+ <--- given back to second writer
278 +---------+ <--- tail pointer
284 +---------+
286 +---------+ <--(last full commit)
288 +---------+
291 +---------+ <--- tail pointer
296 +---------+
298 +---------+
300 +---------+
302 +---------+ <--(last full commit and tail pointer)
308 and will not be a full commit until all writes have been committed.
331 +---+ +---+ +---+ +---+
332 <---| |--->| |--->| |--->| |--->
333 --->| |<---| |<---| |<---| |<---
334 +---+ +---+ +---+ +---+
338 swapped with the reader page. This is because the head page is always
339 part of the ring buffer, but the reader page is not. Whenever there
348 +---+ | |
349 | |<----------+ |
350 | |<------------------------+
351 | |------+
352 +---+ |
355 +---+ +---+ +---+ +---+
356 <---| |--->| |--->| |--->| |--->
357 --->| |<---| |<---| |<---| |<---
358 +---+ +---+ +---+ +---+
364 In this case, the head page will not move when the tail and commit
369 not pending or reserved), then there is nothing more to read.
381 +---+ +---+ +---+ +---+
382 <---| |--->| |--->| |--->| |--->
383 --->| |<---| |<---| |<---| |<---
384 +---+ +---+ +---+ +---+
393 +---+ +---+ +---+ +---+
394 <---| |--->| |--->| |--->| |--->
395 --->| |<---| |<---| |<---| |<---
396 +---+ +---+ +---+ +---+
405 +---+ +---+ +---+ +---+
406 <---| |--->| |--->| |--->| |--->
407 --->| |<---| |<---| |<---| |<---
408 +---+ +---+ +---+ +---+
418 --------------------------------
435 - the page being pointed to is a head page
438 - the page being pointed to is being updated by a writer
446 +---+
447 | |------+
448 +---+ |
451 +---+ +---+ +---+ +---+
452 <---| |--->| |-H->| |--->| |--->
453 --->| |<---| |<---| |<---| |<---
454 +---+ +---+ +---+ +---+
457 The above pointer "-H->" would have the HEADER flag set. That is
458 the next page is the next page to be swapped out by the reader.
468 +---+ +---+ +---+ +---+
469 <---| |--->| |-H->| |--->| |--->
470 --->| |<---| |<---| |<---| |<---
471 +---+ +---+ +---+ +---+
476 +---+ +---+ +---+ +---+
477 <---| |--->| |-U->| |--->| |--->
478 --->| |<---| |<---| |<---| |<---
479 +---+ +---+ +---+ +---+
481 "-U->" represents a pointer in the UPDATE state.
490 head page does not have the HEADER flag set, the compare will fail
496 +------+
499 +------+
500 +---+ +---+ +---+
501 | |--->| |--->| |
502 | |<---| |<---| |
503 +---+ +---+ +---+
505 | +---------------+ |
506 +-----H-------------+
512 +------+
514 |page |-------H-----------+
515 +------+ v
516 | +---+ +---+ +---+
517 | | |--->| |--->| |
518 | | |<---| |<---| |<-+
519 | +---+ +---+ +---+ |
521 | | +---------------+ | |
522 | +-----H-------------+ |
523 +--------------------------------------+
526 point to the reader page. Note that the new pointer does not have the HEADER
529 +------+
531 |page |-------H-----------+
532 +------+ v
533 | ^ +---+ +---+ +---+
534 | | | |-->| |-->| |
535 | | | |<--| |<--| |<-+
536 | | +---+ +---+ +---+ |
538 | | +-------------+ | |
539 | +-----------------------------+ |
540 +------------------------------------+
545 +------+
547 |page |-------H-----------+
548 +------+ <---------------+ v
549 | ^ +---+ +---+ +---+
550 | | | |-->| |-->| |
551 | | | | | |<--| |<-+
552 | | +---+ +---+ +---+ |
554 | | +-------------+ | |
555 | +-----------------------------+ |
556 +------------------------------------+
558 +------+
560 |page |-------H-----------+ <--- New head page
561 +------+ <---------------+ v
562 | ^ +---+ +---+ +---+
563 | | | | | |-->| |
564 | | New | | | |<--| |<-+
565 | | Reader +---+ +---+ +---+ |
566 | | page ----^ | |
568 | +-----------------------------+ |
569 +------------------------------------+
574 not part of the ring buffer. Traversing the ring buffer via the next pointers
576 prev pointers may not.
579 pointer of the page. If the next pointer of the previous page does not
583 +--------+
584 | reader | next +----+
585 | page |-------->| |<====== (buffer page)
586 +--------+ +----+
589 prev | +----+
590 +------------->| |
591 +----+
600 not be able to swap the head page from the buffer, nor will it be able to
609 +---+ +---+ +---+ +---+
610 <---| |--->| |-H->| |--->| |--->
611 --->| |<---| |<---| |<---| |<---
612 +---+ +---+ +---+ +---+
617 +---+ +---+ +---+ +---+
618 <---| |--->| |-U->| |--->| |--->
619 --->| |<---| |<---| |<---| |<---
620 +---+ +---+ +---+ +---+
627 +---+ +---+ +---+ +---+
628 <---| |--->| |-U->| |-H->| |--->
629 --->| |<---| |<---| |<---| |<---
630 +---+ +---+ +---+ +---+
638 +---+ +---+ +---+ +---+
639 <---| |--->| |--->| |-H->| |--->
640 --->| |<---| |<---| |<---| |<---
641 +---+ +---+ +---+ +---+
648 +---+ +---+ +---+ +---+
649 <---| |--->| |--->| |-H->| |--->
650 --->| |<---| |<---| |<---| |<---
651 +---+ +---+ +---+ +---+
661 reader page? The commit page is not part of the ring buffer. The tail page
668 +---+ |
669 | |<----------+
671 | |------+
672 +---+ |
675 +---+ +---+ +---+ +---+
676 <---| |--->| |-H->| |--->| |--->
677 --->| |<---| |<---| |<---| |<---
678 +---+ +---+ +---+ +---+
684 leaving the reader page would not be pointing to the correct page.
690 This is not a race condition, because the commit page can only be moved
692 This means that the commit will not move while a writer is moving the
701 -------------
705 is not the next page, the tail page is simply updated with a cmpxchg.
711 next_page = temp_page->next
716 does not need to push it::
725 +---+ +---+ +---+ +---+
726 <---| |--->| |--->| |--->| |--->
727 --->| |<---| |<---| |<---| |<---
728 +---+ +---+ +---+ +---+
736 +---+ +---+ +---+ +---+
737 <---| |--->| |--->| |--->| |--->
738 --->| |<---| |<---| |<---| |<---
739 +---+ +---+ +---+ +---+
750 +---+ +---+ +---+ +---+
751 <---| |--->| |-H->| |--->| |--->
752 --->| |<---| |<---| |<---| |<---
753 +---+ +---+ +---+ +---+
760 +---+ +---+ +---+ +---+
761 <---| |--->| |-U->| |--->| |--->
762 --->| |<---| |<---| |<---| |<---
763 +---+ +---+ +---+ +---+
776 +---+ +---+ +---+ +---+
777 <---| |--->| |-U->| |-H->| |--->
778 --->| |<---| |<---| |<---| |<---
779 +---+ +---+ +---+ +---+
781 But it will not reset the update back to normal. Only the writer
788 +---+ +---+ +---+ +---+
789 <---| |--->| |-U->| |-H->| |--->
790 --->| |<---| |<---| |<---| |<---
791 +---+ +---+ +---+ +---+
800 +---+ +---+ +---+ +---+
801 <---| |--->| |--->| |-H->| |--->
802 --->| |<---| |<---| |<---| |<---
803 +---+ +---+ +---+ +---+
815 +---+ +---+ +---+ +---+
816 <---| |--->| |-H->| |--->| |--->
817 --->| |<---| |<---| |<---| |<---
818 +---+ +---+ +---+ +---+
825 +---+ +---+ +---+ +---+
826 <---| |--->| |-U->| |--->| |--->
827 --->| |<---| |<---| |<---| |<---
828 +---+ +---+ +---+ +---+
838 +---+ +---+ +---+ +---+
839 <---| |--->| |-U->| |-H->| |--->
840 --->| |<---| |<---| |<---| |<---
841 +---+ +---+ +---+ +---+
843 The nested writer moves the tail page forward. But does not set the old
844 update page to NORMAL because it is not the outermost writer::
849 +---+ +---+ +---+ +---+
850 <---| |--->| |-U->| |-H->| |--->
851 --->| |<---| |<---| |<---| |<---
852 +---+ +---+ +---+ +---+
862 +---+ +---+ +---+ +---+
863 <---| |--->| |-U->| |-U->| |--->
864 --->| |<---| |<---| |<---| |<---
865 +---+ +---+ +---+ +---+
875 +---+ +---+ +---+ +---+
876 <---| |--->| |-U->| |-U->| |-H->
877 --->| |<---| |<---| |<---| |<---
878 +---+ +---+ +---+ +---+
889 +---+ +---+ +---+ +---+
890 <---| |--->| |-U->| |--->| |-H->
891 --->| |<---| |<---| |<---| |<---
892 +---+ +---+ +---+ +---+
903 +---+ +---+ +---+ +---+
904 <---| |--->| |-U->| |--->| |-H->
905 --->| |<---| |<---| |<---| |<---
906 +---+ +---+ +---+ +---+
919 +---+ +---+ +---+ +---+
920 <---| |--->| |-U->| |--->| |-H->
921 --->| |<---| |<---| |<---| |<---
922 +---+ +---+ +---+ +---+
934 +---+ +---+ +---+ +---+
935 <---| |--->| |-U->| |-H->| |-H->
936 --->| |<---| |<---| |<---| |<---
937 +---+ +---+ +---+ +---+
941 But as we can see, this is not good enough. It must also check to see
950 +---+ +---+ +---+ +---+
951 <---| |--->| |-U->| |-H->| |-H->
952 --->| |<---| |<---| |<---| |<---
953 +---+ +---+ +---+ +---+
965 +---+ +---+ +---+ +---+
966 <---| |--->| |-U->| |--->| |-H->
967 --->| |<---| |<---| |<---| |<---
968 +---+ +---+ +---+ +---+
980 +---+ +---+ +---+ +---+
981 <---| |--->| |--->| |--->| |-H->
982 --->| |<---| |<---| |<---| |<---
983 +---+ +---+ +---+ +---+