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