Lines Matching full:page
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.
110 At initialization a reader page is allocated for the reader that is not
114 to the same page.
116 The reader page is initialized to have its next pointer pointing to
117 the head page, and its previous pointer pointing to a page before
118 the head page.
120 The reader has its own page to use. At start up time, this page is
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
125 The page after the inserted page (old reader_page) will become the
126 new head page.
128 Once the new page is given to the reader, the reader could do what
129 it wants with it, as long as a writer has left that page.
131 A sample of how the reader page is swapped: Note this does not
132 show the head page in the buffer, it is for demonstrating a swap
139 |page |
152 |page |-------------------+
165 |page |-------------------+
178 |page |-------------------+
184 | | page ----^ | |
191 It is possible that the page swapped is the commit page and the tail page,
192 if what is in the ring buffer is less than what is held in a buffer page.
196 reader page commit page tail page
212 When the writer leaves the page, it simply goes into the ring buffer
213 since the reader page still points to the next location in the ring
219 reader page
220 - The page used solely by the reader and is not part
223 head page
224 - the next page in the ring buffer that will be swapped
225 with the reader page.
227 tail page
228 - the page where the next write will take place.
230 commit page
231 - the page that last finished a write.
233 The commit page only is updated by the outermost writer in the
235 commit page.
248 Buffer page
259 Buffer page
271 Buffer page
283 Buffer page
295 Buffer page
310 The commit page points to the page that has the last full commit.
311 The tail page points to the page with the last write (before
314 The tail page is always equal to or after the commit page. It may
315 be several pages ahead. If the tail page catches up to the commit
316 page then no more writes may take place (regardless of the mode
321 head page
322 commit page
323 tail page
327 tail page
328 head page commit page |
336 There is a special case that the head page is after either the commit page
337 and possibly the tail page. That is when the commit (and tail) page has been
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
340 has been less than a full page that has been committed inside the ring buffer,
341 and a reader swaps out a page, it will be swapping out the commit page.
345 reader page commit page tail page
361 head page
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
368 is still on that page. If the read meets the last commit (real commit
372 When the tail meets the head page, if the buffer is in overwrite mode,
373 the head page will be pushed ahead one. If the buffer is in producer/consumer
378 tail page
387 head page
390 tail page
399 head page
402 tail page
411 head page
413 Note, the reader page will still point to the previous head page.
414 But when a swap takes place, it will use the most recent head page.
422 State flags are placed inside the pointer to the page. To do this,
423 each page must be aligned in memory by 4 bytes. This will allow the 2
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.
443 reader page
458 the next page is the next page to be swapped out by the reader.
459 This pointer means the next page is the head page.
461 When the tail page meets the head pointer, it will use cmpxchg to
465 tail page
473 tail page
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.
494 The reader swaps the reader page as follows::
498 |page |
508 The reader sets the reader page next pointer as HEADER to the page after
509 the head page::
514 |page |-------H-----------+
525 It does a cmpxchg with the pointer to the previous head page to make it
526 point to the reader page. Note that the new pointer does not have the HEADER
527 flag set. This action atomically moves the head page forward::
531 |page |-------H-----------+
542 After the new head page is set, the previous pointer of the head page is
543 updated to the reader page::
547 |page |-------H-----------+
560 |page |-------H-----------+ <--- New head page
566 | | page ----^ | |
571 Another important point: The page that the reader page points back to
572 by its previous pointer (the one that now points to the new head page)
573 never points back to the reader page. That is because the reader page is
578 Note, the way to determine a reader page is simply by examining the previous
579 pointer of the page. If the next pointer of the previous page does not
580 point back to the original page, then the original page is a reader page::
585 | page |-------->| |<====== (buffer page)
593 The way the head page moves forward:
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
597 writer may move the tail page. The way this is done is that the writer
598 performs a cmpxchg to convert the pointer to the head page from the HEADER
600 not be able to swap the head page from the buffer, nor will it be able to
601 move the head page, until the writer is finished with the move.
606 tail page
614 tail page
622 The following page will be made into the new head page::
624 tail page
632 After the new head page has been set, we can set the old head page
635 tail page
643 After the head page has been moved, the tail page may now move forward::
645 tail page
658 tail page may make it all the way around the buffer and meet the commit
659 page. At this time, we must start dropping writes (usually with some kind
661 reader page? The commit page is not part of the ring buffer. The tail page
665 reader page commit page
681 tail page
683 If the tail page were to simply push the head page forward, the commit when
684 leaving the reader page would not be pointing to the correct page.
686 The solution to this is to test if the commit page is on the reader page
687 before pushing the head page. If it is, then it can be assumed that the
688 tail page wrapped the buffer, and we must drop new writes.
690 This is not a race condition, because the commit page can only be moved
693 tail page. The reader cannot swap the reader page if it is also being
694 used as the commit page. The reader can simply check that the commit
695 is off the reader page. Once the commit page leaves the reader page
697 buffer page that is also the commit page.
703 In the pushing forward of the tail page we must first push forward
704 the head page if the head page is the next page. If the head page
705 is not the next page, the tail page is simply updated with a cmpxchg.
707 Only writers move the tail page. This must be done atomically to protect
714 The above will update the tail page if it is still pointing to the expected
715 page. If this fails, a nested write pushed it forward, the current write
719 temp page
722 tail page
730 Nested write comes in and moves the tail page forward::
732 tail page (moved by nested writer)
733 temp page |
741 The above would fail the cmpxchg, but since the tail page has already
743 on the new tail page.
745 But the moving of the head page is a bit more complex::
747 tail page
755 The write converts the head page pointer to UPDATE::
757 tail page
766 page is a head page, but it is also nested. It will detect that
771 The nested writer will set the new head page pointer::
773 tail page
785 tail page
797 tail page
807 the tail page ahead several pages::
812 tail page
820 The write converts the head page pointer to UPDATE::
822 tail page
831 head page::
835 tail page
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::
846 tail page
854 Another writer preempts and sees the page after the tail page is a head page.
859 tail page
867 The writer will move the head page forward::
872 tail page
886 tail page
895 Then it will move the tail page, and return back to the second writer::
900 tail page
909 The second writer will fail to move the tail page because it was already
910 moved, so it will try again and add its data to the new tail page.
916 tail page
924 The first writer cannot know atomically if the tail page moved
925 while it updates the HEAD page. It will then update the head page to
926 what it thinks is the new head page::
931 tail page
942 if the tail page is either where it use to be or on the next page::
947 A B tail page
955 If tail page != A and tail page != B, then it must reset the pointer
957 writers means that it only needs to check this after setting the HEAD page::
962 A B tail page
970 Now the writer can update the head page. This is also why the head page must
972 the reader from seeing the incorrect head page::
977 A B tail page