Lines Matching +full:compare +full:- +full:and +full:- +full:swap
1 .. SPDX-License-Identifier: GPL-2.0 OR GFDL-1.2-no-invariants-only
13 and Frederic Weisbecker.
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::
57 R = cmpxchg(A, C, B) is saying that we replace A with B if and only
58 if current A is equal to C, and we put the old (current)
63 To see if the update was successful a compare of ``R == C``
67 -----------------------
80 No two writers can write at the same time (on the same per-cpu buffer),
94 This is very much like a writer being preempted by an interrupt and
102 and can be preempted by a writer.
113 The head_page, tail_page and commit_page are all initialized to point
117 the head page, and its previous pointer pointing to a page before
122 to read from the buffer, if its page is empty (like it is on start-up),
123 it will swap its page with the head_page. The old reader page will
124 become part of the ring buffer and the head_page will be removed.
132 show the head page in the buffer, it is for demonstrating a swap
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
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.
238 in the ring buffer and passed back to the writer. When the writer
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.
317 of the ring buffer: overwrite and produce/consumer).
331 +---+ +---+ +---+ +---+
332 <---| |--->| |--->| |--->| |--->
333 --->| |<---| |<---| |<---| |<---
334 +---+ +---+ +---+ +---+
337 and possibly the tail page. That is when the commit (and tail) page has been
341 and a reader swaps out a page, it will be swapping out the commit page.
348 +---+ | |
349 | |<----------+ |
350 | |<------------------------+
351 | |------+
352 +---+ |
355 +---+ +---+ +---+ +---+
356 <---| |--->| |--->| |--->| |--->
357 --->| |<---| |<---| |<---| |<---
358 +---+ +---+ +---+ +---+
364 In this case, the head page will not move when the tail and commit
367 The reader cannot swap a page into the ring buffer if the commit page
381 +---+ +---+ +---+ +---+
382 <---| |--->| |--->| |--->| |--->
383 --->| |<---| |<---| |<---| |<---
384 +---+ +---+ +---+ +---+
393 +---+ +---+ +---+ +---+
394 <---| |--->| |--->| |--->| |--->
395 --->| |<---| |<---| |<---| |<---
396 +---+ +---+ +---+ +---+
405 +---+ +---+ +---+ +---+
406 <---| |--->| |--->| |--->| |--->
407 --->| |<---| |<---| |<---| |<---
408 +---+ +---+ +---+ +---+
414 But when a swap takes place, it will use the most recent head page.
418 --------------------------------
435 - the page being pointed to is a head page
438 - the page being pointed to is being updated by a writer
439 and was or is about to be a head page.
446 +---+
447 | |------+
448 +---+ |
451 +---+ +---+ +---+ +---+
452 <---| |--->| |-H->| |--->| |--->
453 --->| |<---| |<---| |<---| |<---
454 +---+ +---+ +---+ +---+
457 The above pointer "-H->" would have the HEADER flag set. That is
468 +---+ +---+ +---+ +---+
469 <---| |--->| |-H->| |--->| |--->
470 --->| |<---| |<---| |<---| |<---
471 +---+ +---+ +---+ +---+
476 +---+ +---+ +---+ +---+
477 <---| |--->| |-U->| |--->| |--->
478 --->| |<---| |<---| |<---| |<---
479 +---+ +---+ +---+ +---+
481 "-U->" represents a pointer in the UPDATE state.
486 and writes only preempt in "stack" formation.
488 When the reader tries to swap the page with the ring buffer, it
490 head page does not have the HEADER flag set, the compare will fail
491 and the reader will need to look for the new head page and try again.
492 Note, the flags UPDATE and HEADER are never set at the same time.
496 +------+
499 +------+
500 +---+ +---+ +---+
501 | |--->| |--->| |
502 | |<---| |<---| |
503 +---+ +---+ +---+
505 | +---------------+ |
506 +-----H-------------+
512 +------+
514 |page |-------H-----------+
515 +------+ v
516 | +---+ +---+ +---+
517 | | |--->| |--->| |
518 | | |<---| |<---| |<-+
519 | +---+ +---+ +---+ |
521 | | +---------------+ | |
522 | +-----H-------------+ |
523 +--------------------------------------+
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 +------------------------------------+
583 +--------+
584 | reader | next +----+
585 | page |-------->| |<====== (buffer page)
586 +--------+ +----+
589 prev | +----+
590 +------------->| |
591 +----+
595 When the tail page meets the head page and the buffer is in overwrite mode
596 and more writes take place, the head page must be moved forward before the
600 not be able to swap the head page from the buffer, nor will it be able to
604 must spin, and this is why the reader cannot preempt the writer::
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 +---+ +---+ +---+ +---+
658 tail page may make it all the way around the buffer and meet the commit
668 +---+ |
669 | |<----------+
671 | |------+
672 +---+ |
675 +---+ +---+ +---+ +---+
676 <---| |--->| |-H->| |--->| |--->
677 --->| |<---| |<---| |<---| |<---
678 +---+ +---+ +---+ +---+
688 tail page wrapped the buffer, and we must drop new writes.
693 tail page. The reader cannot swap the reader page if it is also being
696 it will never go back on it unless a reader does another swap with the
701 -------------
711 next_page = temp_page->next
725 +---+ +---+ +---+ +---+
726 <---| |--->| |--->| |--->| |--->
727 --->| |<---| |<---| |<---| |<---
728 +---+ +---+ +---+ +---+
730 Nested write comes in and moves the tail page forward::
736 +---+ +---+ +---+ +---+
737 <---| |--->| |--->| |--->| |--->
738 --->| |<---| |<---| |<---| |<---
739 +---+ +---+ +---+ +---+
750 +---+ +---+ +---+ +---+
751 <---| |--->| |-H->| |--->| |--->
752 --->| |<---| |<---| |<---| |<---
753 +---+ +---+ +---+ +---+
760 +---+ +---+ +---+ +---+
761 <---| |--->| |-U->| |--->| |--->
762 --->| |<---| |<---| |<---| |<---
763 +---+ +---+ +---+ +---+
767 it is nested and will save that information. The detection is the
776 +---+ +---+ +---+ +---+
777 <---| |--->| |-U->| |-H->| |--->
778 --->| |<---| |<---| |<---| |<---
779 +---+ +---+ +---+ +---+
788 +---+ +---+ +---+ +---+
789 <---| |--->| |-U->| |-H->| |--->
790 --->| |<---| |<---| |<---| |<---
791 +---+ +---+ +---+ +---+
800 +---+ +---+ +---+ +---+
801 <---| |--->| |--->| |-H->| |--->
802 --->| |<---| |<---| |<---| |<---
803 +---+ +---+ +---+ +---+
806 It can be even more complex if several nested writes came in and moved
815 +---+ +---+ +---+ +---+
816 <---| |--->| |-H->| |--->| |--->
817 --->| |<---| |<---| |<---| |<---
818 +---+ +---+ +---+ +---+
825 +---+ +---+ +---+ +---+
826 <---| |--->| |-U->| |--->| |--->
827 --->| |<---| |<---| |<---| |<---
828 +---+ +---+ +---+ +---+
830 Next writer comes in, and sees the update and sets up the new
838 +---+ +---+ +---+ +---+
839 <---| |--->| |-U->| |-H->| |--->
840 --->| |<---| |<---| |<---| |<---
841 +---+ +---+ +---+ +---+
849 +---+ +---+ +---+ +---+
850 <---| |--->| |-U->| |-H->| |--->
851 --->| |<---| |<---| |<---| |<---
852 +---+ +---+ +---+ +---+
854 Another writer preempts and sees the page after the tail page is a head page.
862 +---+ +---+ +---+ +---+
863 <---| |--->| |-U->| |-U->| |--->
864 --->| |<---| |<---| |<---| |<---
865 +---+ +---+ +---+ +---+
875 +---+ +---+ +---+ +---+
876 <---| |--->| |-U->| |-U->| |-H->
877 --->| |<---| |<---| |<---| |<---
878 +---+ +---+ +---+ +---+
889 +---+ +---+ +---+ +---+
890 <---| |--->| |-U->| |--->| |-H->
891 --->| |<---| |<---| |<---| |<---
892 +---+ +---+ +---+ +---+
895 Then it will move the tail page, and return back to the second writer::
903 +---+ +---+ +---+ +---+
904 <---| |--->| |-U->| |--->| |-H->
905 --->| |<---| |<---| |<---| |<---
906 +---+ +---+ +---+ +---+
910 moved, so it will try again and add its data to the new tail page.
919 +---+ +---+ +---+ +---+
920 <---| |--->| |-U->| |--->| |-H->
921 --->| |<---| |<---| |<---| |<---
922 +---+ +---+ +---+ +---+
934 +---+ +---+ +---+ +---+
935 <---| |--->| |-U->| |-H->| |-H->
936 --->| |<---| |<---| |<---| |<---
937 +---+ +---+ +---+ +---+
950 +---+ +---+ +---+ +---+
951 <---| |--->| |-U->| |-H->| |-H->
952 --->| |<---| |<---| |<---| |<---
953 +---+ +---+ +---+ +---+
955 If tail page != A and tail page != B, then it must reset the pointer
965 +---+ +---+ +---+ +---+
966 <---| |--->| |-U->| |--->| |-H->
967 --->| |<---| |<---| |<---| |<---
968 +---+ +---+ +---+ +---+
971 remain in UPDATE and only reset by the outermost writer. This prevents
980 +---+ +---+ +---+ +---+
981 <---| |--->| |--->| |--->| |-H->
982 --->| |<---| |<---| |<---| |<---
983 +---+ +---+ +---+ +---+