aboutsummaryrefslogtreecommitdiffstats
path: root/Documentation/trace/ring-buffer-design.txt
diff options
context:
space:
mode:
Diffstat (limited to 'Documentation/trace/ring-buffer-design.txt')
-rw-r--r--Documentation/trace/ring-buffer-design.txt56
1 files changed, 28 insertions, 28 deletions
diff --git a/Documentation/trace/ring-buffer-design.txt b/Documentation/trace/ring-buffer-design.txt
index 5b1d23d604c5..d299ff31df57 100644
--- a/Documentation/trace/ring-buffer-design.txt
+++ b/Documentation/trace/ring-buffer-design.txt
@@ -33,9 +33,9 @@ head_page - a pointer to the page that the reader will use next
33 33
34tail_page - a pointer to the page that will be written to next 34tail_page - a pointer to the page that will be written to next
35 35
36commit_page - a pointer to the page with the last finished non nested write. 36commit_page - a pointer to the page with the last finished non-nested write.
37 37
38cmpxchg - hardware assisted atomic transaction that performs the following: 38cmpxchg - hardware-assisted atomic transaction that performs the following:
39 39
40 A = B iff previous A == C 40 A = B iff previous A == C
41 41
@@ -52,15 +52,15 @@ The Generic Ring Buffer
52The ring buffer can be used in either an overwrite mode or in 52The ring buffer can be used in either an overwrite mode or in
53producer/consumer mode. 53producer/consumer mode.
54 54
55Producer/consumer mode is where the producer were to fill up the 55Producer/consumer mode is where if the producer were to fill up the
56buffer before the consumer could free up anything, the producer 56buffer before the consumer could free up anything, the producer
57will stop writing to the buffer. This will lose most recent events. 57will stop writing to the buffer. This will lose most recent events.
58 58
59Overwrite mode is where the produce were to fill up the buffer 59Overwrite mode is where if the producer were to fill up the buffer
60before the consumer could free up anything, the producer will 60before the consumer could free up anything, the producer will
61overwrite the older data. This will lose the oldest events. 61overwrite the older data. This will lose the oldest events.
62 62
63No two writers can write at the same time (on the same per cpu buffer), 63No two writers can write at the same time (on the same per-cpu buffer),
64but a writer may interrupt another writer, but it must finish writing 64but a writer may interrupt another writer, but it must finish writing
65before the previous writer may continue. This is very important to the 65before the previous writer may continue. This is very important to the
66algorithm. The writers act like a "stack". The way interrupts works 66algorithm. The writers act like a "stack". The way interrupts works
@@ -79,16 +79,16 @@ the interrupt doing a write as well.
79 79
80Readers can happen at any time. But no two readers may run at the 80Readers can happen at any time. But no two readers may run at the
81same time, nor can a reader preempt/interrupt another reader. A reader 81same time, nor can a reader preempt/interrupt another reader. A reader
82can not preempt/interrupt a writer, but it may read/consume from the 82cannot preempt/interrupt a writer, but it may read/consume from the
83buffer at the same time as a writer is writing, but the reader must be 83buffer at the same time as a writer is writing, but the reader must be
84on another processor to do so. A reader may read on its own processor 84on another processor to do so. A reader may read on its own processor
85and can be preempted by a writer. 85and can be preempted by a writer.
86 86
87A writer can preempt a reader, but a reader can not preempt a writer. 87A writer can preempt a reader, but a reader cannot preempt a writer.
88But a reader can read the buffer at the same time (on another processor) 88But a reader can read the buffer at the same time (on another processor)
89as a writer. 89as a writer.
90 90
91The ring buffer is made up of a list of pages held together by a link list. 91The ring buffer is made up of a list of pages held together by a linked list.
92 92
93At initialization a reader page is allocated for the reader that is not 93At initialization a reader page is allocated for the reader that is not
94part of the ring buffer. 94part of the ring buffer.
@@ -102,7 +102,7 @@ the head page.
102 102
103The reader has its own page to use. At start up time, this page is 103The reader has its own page to use. At start up time, this page is
104allocated but is not attached to the list. When the reader wants 104allocated but is not attached to the list. When the reader wants
105to read from the buffer, if its page is empty (like it is on start up) 105to read from the buffer, if its page is empty (like it is on start-up),
106it will swap its page with the head_page. The old reader page will 106it will swap its page with the head_page. The old reader page will
107become part of the ring buffer and the head_page will be removed. 107become part of the ring buffer and the head_page will be removed.
108The page after the inserted page (old reader_page) will become the 108The page after the inserted page (old reader_page) will become the
@@ -206,7 +206,7 @@ The main pointers:
206 206
207 commit page - the page that last finished a write. 207 commit page - the page that last finished a write.
208 208
209The commit page only is updated by the outer most writer in the 209The commit page only is updated by the outermost writer in the
210writer stack. A writer that preempts another writer will not move the 210writer stack. A writer that preempts another writer will not move the
211commit page. 211commit page.
212 212
@@ -281,7 +281,7 @@ with the previous write.
281The commit pointer points to the last write location that was 281The commit pointer points to the last write location that was
282committed without preempting another write. When a write that 282committed without preempting another write. When a write that
283preempted another write is committed, it only becomes a pending commit 283preempted another write is committed, it only becomes a pending commit
284and will not be a full commit till all writes have been committed. 284and will not be a full commit until all writes have been committed.
285 285
286The commit page points to the page that has the last full commit. 286The commit page points to the page that has the last full commit.
287The tail page points to the page with the last write (before 287The tail page points to the page with the last write (before
@@ -292,7 +292,7 @@ be several pages ahead. If the tail page catches up to the commit
292page then no more writes may take place (regardless of the mode 292page then no more writes may take place (regardless of the mode
293of the ring buffer: overwrite and produce/consumer). 293of the ring buffer: overwrite and produce/consumer).
294 294
295The order of pages are: 295The order of pages is:
296 296
297 head page 297 head page
298 commit page 298 commit page
@@ -311,7 +311,7 @@ Possible scenario:
311There is a special case that the head page is after either the commit page 311There is a special case that the head page is after either the commit page
312and possibly the tail page. That is when the commit (and tail) page has been 312and possibly the tail page. That is when the commit (and tail) page has been
313swapped with the reader page. This is because the head page is always 313swapped with the reader page. This is because the head page is always
314part of the ring buffer, but the reader page is not. When ever there 314part of the ring buffer, but the reader page is not. Whenever there
315has been less than a full page that has been committed inside the ring buffer, 315has been less than a full page that has been committed inside the ring buffer,
316and a reader swaps out a page, it will be swapping out the commit page. 316and a reader swaps out a page, it will be swapping out the commit page.
317 317
@@ -338,7 +338,7 @@ and a reader swaps out a page, it will be swapping out the commit page.
338In this case, the head page will not move when the tail and commit 338In this case, the head page will not move when the tail and commit
339move back into the ring buffer. 339move back into the ring buffer.
340 340
341The reader can not swap a page into the ring buffer if the commit page 341The reader cannot swap a page into the ring buffer if the commit page
342is still on that page. If the read meets the last commit (real commit 342is still on that page. If the read meets the last commit (real commit
343not pending or reserved), then there is nothing more to read. 343not pending or reserved), then there is nothing more to read.
344The buffer is considered empty until another full commit finishes. 344The buffer is considered empty until another full commit finishes.
@@ -395,7 +395,7 @@ The main idea behind the lockless algorithm is to combine the moving
395of the head_page pointer with the swapping of pages with the reader. 395of the head_page pointer with the swapping of pages with the reader.
396State flags are placed inside the pointer to the page. To do this, 396State flags are placed inside the pointer to the page. To do this,
397each page must be aligned in memory by 4 bytes. This will allow the 2 397each page must be aligned in memory by 4 bytes. This will allow the 2
398least significant bits of the address to be used as flags. Since 398least significant bits of the address to be used as flags, since
399they will always be zero for the address. To get the address, 399they will always be zero for the address. To get the address,
400simply mask out the flags. 400simply mask out the flags.
401 401
@@ -460,7 +460,7 @@ When the reader tries to swap the page with the ring buffer, it
460will also use cmpxchg. If the flag bit in the pointer to the 460will also use cmpxchg. If the flag bit in the pointer to the
461head page does not have the HEADER flag set, the compare will fail 461head page does not have the HEADER flag set, the compare will fail
462and the reader will need to look for the new head page and try again. 462and the reader will need to look for the new head page and try again.
463Note, the flag UPDATE and HEADER are never set at the same time. 463Note, the flags UPDATE and HEADER are never set at the same time.
464 464
465The reader swaps the reader page as follows: 465The reader swaps the reader page as follows:
466 466
@@ -539,7 +539,7 @@ updated to the reader page.
539 | +-----------------------------+ | 539 | +-----------------------------+ |
540 +------------------------------------+ 540 +------------------------------------+
541 541
542Another important point. The page that the reader page points back to 542Another important point: The page that the reader page points back to
543by its previous pointer (the one that now points to the new head page) 543by its previous pointer (the one that now points to the new head page)
544never points back to the reader page. That is because the reader page is 544never points back to the reader page. That is because the reader page is
545not part of the ring buffer. Traversing the ring buffer via the next pointers 545not part of the ring buffer. Traversing the ring buffer via the next pointers
@@ -572,7 +572,7 @@ not be able to swap the head page from the buffer, nor will it be able to
572move the head page, until the writer is finished with the move. 572move the head page, until the writer is finished with the move.
573 573
574This eliminates any races that the reader can have on the writer. The reader 574This eliminates any races that the reader can have on the writer. The reader
575must spin, and this is why the reader can not preempt the writer. 575must spin, and this is why the reader cannot preempt the writer.
576 576
577 tail page 577 tail page
578 | 578 |
@@ -659,9 +659,9 @@ before pushing the head page. If it is, then it can be assumed that the
659tail page wrapped the buffer, and we must drop new writes. 659tail page wrapped the buffer, and we must drop new writes.
660 660
661This is not a race condition, because the commit page can only be moved 661This is not a race condition, because the commit page can only be moved
662by the outter most writer (the writer that was preempted). 662by the outermost writer (the writer that was preempted).
663This means that the commit will not move while a writer is moving the 663This means that the commit will not move while a writer is moving the
664tail page. The reader can not swap the reader page if it is also being 664tail page. The reader cannot swap the reader page if it is also being
665used as the commit page. The reader can simply check that the commit 665used as the commit page. The reader can simply check that the commit
666is off the reader page. Once the commit page leaves the reader page 666is off the reader page. Once the commit page leaves the reader page
667it will never go back on it unless a reader does another swap with the 667it will never go back on it unless a reader does another swap with the
@@ -733,7 +733,7 @@ The write converts the head page pointer to UPDATE.
733--->| |<---| |<---| |<---| |<--- 733--->| |<---| |<---| |<---| |<---
734 +---+ +---+ +---+ +---+ 734 +---+ +---+ +---+ +---+
735 735
736But if a nested writer preempts here. It will see that the next 736But if a nested writer preempts here, it will see that the next
737page is a head page, but it is also nested. It will detect that 737page is a head page, but it is also nested. It will detect that
738it is nested and will save that information. The detection is the 738it is nested and will save that information. The detection is the
739fact that it sees the UPDATE flag instead of a HEADER or NORMAL 739fact that it sees the UPDATE flag instead of a HEADER or NORMAL
@@ -761,7 +761,7 @@ to NORMAL.
761--->| |<---| |<---| |<---| |<--- 761--->| |<---| |<---| |<---| |<---
762 +---+ +---+ +---+ +---+ 762 +---+ +---+ +---+ +---+
763 763
764After the nested writer finishes, the outer most writer will convert 764After the nested writer finishes, the outermost writer will convert
765the UPDATE pointer to NORMAL. 765the UPDATE pointer to NORMAL.
766 766
767 767
@@ -812,7 +812,7 @@ head page.
812 +---+ +---+ +---+ +---+ 812 +---+ +---+ +---+ +---+
813 813
814The nested writer moves the tail page forward. But does not set the old 814The nested writer moves the tail page forward. But does not set the old
815update page to NORMAL because it is not the outer most writer. 815update page to NORMAL because it is not the outermost writer.
816 816
817 tail page 817 tail page
818 | 818 |
@@ -892,7 +892,7 @@ It will return to the first writer.
892--->| |<---| |<---| |<---| |<--- 892--->| |<---| |<---| |<---| |<---
893 +---+ +---+ +---+ +---+ 893 +---+ +---+ +---+ +---+
894 894
895The first writer can not know atomically test if the tail page moved 895The first writer cannot know atomically if the tail page moved
896while it updates the HEAD page. It will then update the head page to 896while it updates the HEAD page. It will then update the head page to
897what it thinks is the new head page. 897what it thinks is the new head page.
898 898
@@ -923,9 +923,9 @@ if the tail page is either where it use to be or on the next page:
923--->| |<---| |<---| |<---| |<--- 923--->| |<---| |<---| |<---| |<---
924 +---+ +---+ +---+ +---+ 924 +---+ +---+ +---+ +---+
925 925
926If tail page != A and tail page does not equal B, then it must reset the 926If tail page != A and tail page != B, then it must reset the pointer
927pointer back to NORMAL. The fact that it only needs to worry about 927back to NORMAL. The fact that it only needs to worry about nested
928nested writers, it only needs to check this after setting the HEAD page. 928writers means that it only needs to check this after setting the HEAD page.
929 929
930 930
931(first writer) 931(first writer)
@@ -939,7 +939,7 @@ nested writers, it only needs to check this after setting the HEAD page.
939 +---+ +---+ +---+ +---+ 939 +---+ +---+ +---+ +---+
940 940
941Now the writer can update the head page. This is also why the head page must 941Now the writer can update the head page. This is also why the head page must
942remain in UPDATE and only reset by the outer most writer. This prevents 942remain in UPDATE and only reset by the outermost writer. This prevents
943the reader from seeing the incorrect head page. 943the reader from seeing the incorrect head page.
944 944
945 945