summaryrefslogtreecommitdiffstats
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.txt955
1 files changed, 0 insertions, 955 deletions
diff --git a/Documentation/trace/ring-buffer-design.txt b/Documentation/trace/ring-buffer-design.txt
deleted file mode 100644
index 7d350b4..0000000
--- a/Documentation/trace/ring-buffer-design.txt
+++ /dev/null
@@ -1,955 +0,0 @@
- Lockless Ring Buffer Design
- ===========================
-
-Copyright 2009 Red Hat Inc.
- Author: Steven Rostedt <srostedt@redhat.com>
- License: The GNU Free Documentation License, Version 1.2
- (dual licensed under the GPL v2)
-Reviewers: Mathieu Desnoyers, Huang Ying, Hidetoshi Seto,
- and Frederic Weisbecker.
-
-
-Written for: 2.6.31
-
-Terminology used in this Document
----------------------------------
-
-tail - where new writes happen in the ring buffer.
-
-head - where new reads happen in the ring buffer.
-
-producer - the task that writes into the ring buffer (same as writer)
-
-writer - same as producer
-
-consumer - the task that reads from the buffer (same as reader)
-
-reader - same as consumer.
-
-reader_page - A page outside the ring buffer used solely (for the most part)
- by the reader.
-
-head_page - a pointer to the page that the reader will use next
-
-tail_page - a pointer to the page that will be written to next
-
-commit_page - a pointer to the page with the last finished non-nested write.
-
-cmpxchg - hardware-assisted atomic transaction that performs the following:
-
- A = B iff previous A == C
-
- R = cmpxchg(A, C, B) is saying that we replace A with B if and only if
- current A is equal to C, and we put the old (current) A into R
-
- R gets the previous A regardless if A is updated with B or not.
-
- To see if the update was successful a compare of R == C may be used.
-
-The Generic Ring Buffer
------------------------
-
-The ring buffer can be used in either an overwrite mode or in
-producer/consumer mode.
-
-Producer/consumer mode is where if the producer were to fill up the
-buffer before the consumer could free up anything, the producer
-will stop writing to the buffer. This will lose most recent events.
-
-Overwrite mode is where if the producer were to fill up the buffer
-before the consumer could free up anything, the producer will
-overwrite the older data. This will lose the oldest events.
-
-No two writers can write at the same time (on the same per-cpu buffer),
-but a writer may interrupt another writer, but it must finish writing
-before the previous writer may continue. This is very important to the
-algorithm. The writers act like a "stack". The way interrupts works
-enforces this behavior.
-
-
- writer1 start
- <preempted> writer2 start
- <preempted> writer3 start
- writer3 finishes
- writer2 finishes
- writer1 finishes
-
-This is very much like a writer being preempted by an interrupt and
-the interrupt doing a write as well.
-
-Readers can happen at any time. But no two readers may run at the
-same time, nor can a reader preempt/interrupt another reader. A reader
-cannot preempt/interrupt a writer, but it may read/consume from the
-buffer at the same time as a writer is writing, but the reader must be
-on another processor to do so. A reader may read on its own processor
-and can be preempted by a writer.
-
-A writer can preempt a reader, but a reader cannot preempt a writer.
-But a reader can read the buffer at the same time (on another processor)
-as a writer.
-
-The ring buffer is made up of a list of pages held together by a linked list.
-
-At initialization a reader page is allocated for the reader that is not
-part of the ring buffer.
-
-The head_page, tail_page and commit_page are all initialized to point
-to the same page.
-
-The reader page is initialized to have its next pointer pointing to
-the head page, and its previous pointer pointing to a page before
-the head page.
-
-The reader has its own page to use. At start up time, this page is
-allocated but is not attached to the list. When the reader wants
-to read from the buffer, if its page is empty (like it is on start-up),
-it will swap its page with the head_page. The old reader page will
-become part of the ring buffer and the head_page will be removed.
-The page after the inserted page (old reader_page) will become the
-new head page.
-
-Once the new page is given to the reader, the reader could do what
-it wants with it, as long as a writer has left that page.
-
-A sample of how the reader page is swapped: Note this does not
-show the head page in the buffer, it is for demonstrating a swap
-only.
-
- +------+
- |reader| RING BUFFER
- |page |
- +------+
- +---+ +---+ +---+
- | |-->| |-->| |
- | |<--| |<--| |
- +---+ +---+ +---+
- ^ | ^ |
- | +-------------+ |
- +-----------------+
-
-
- +------+
- |reader| RING BUFFER
- |page |-------------------+
- +------+ v
- | +---+ +---+ +---+
- | | |-->| |-->| |
- | | |<--| |<--| |<-+
- | +---+ +---+ +---+ |
- | ^ | ^ | |
- | | +-------------+ | |
- | +-----------------+ |
- +------------------------------------+
-
- +------+
- |reader| RING BUFFER
- |page |-------------------+
- +------+ <---------------+ v
- | ^ +---+ +---+ +---+
- | | | |-->| |-->| |
- | | | | | |<--| |<-+
- | | +---+ +---+ +---+ |
- | | | ^ | |
- | | +-------------+ | |
- | +-----------------------------+ |
- +------------------------------------+
-
- +------+
- |buffer| RING BUFFER
- |page |-------------------+
- +------+ <---------------+ v
- | ^ +---+ +---+ +---+
- | | | | | |-->| |
- | | New | | | |<--| |<-+
- | | Reader +---+ +---+ +---+ |
- | | page ----^ | |
- | | | |
- | +-----------------------------+ |
- +------------------------------------+
-
-
-
-It is possible that the page swapped is the commit page and the tail page,
-if what is in the ring buffer is less than what is held in a buffer page.
-
-
- reader page commit page tail page
- | | |
- v | |
- +---+ | |
- | |<----------+ |
- | |<------------------------+
- | |------+
- +---+ |
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-This case is still valid for this algorithm.
-When the writer leaves the page, it simply goes into the ring buffer
-since the reader page still points to the next location in the ring
-buffer.
-
-
-The main pointers:
-
- reader page - The page used solely by the reader and is not part
- of the ring buffer (may be swapped in)
-
- head page - the next page in the ring buffer that will be swapped
- with the reader page.
-
- tail page - the page where the next write will take place.
-
- commit page - the page that last finished a write.
-
-The commit page only is updated by the outermost writer in the
-writer stack. A writer that preempts another writer will not move the
-commit page.
-
-When data is written into the ring buffer, a position is reserved
-in the ring buffer and passed back to the writer. When the writer
-is finished writing data into that position, it commits the write.
-
-Another write (or a read) may take place at anytime during this
-transaction. If another write happens it must finish before continuing
-with the previous write.
-
-
- Write reserve:
-
- Buffer page
- +---------+
- |written |
- +---------+ <--- given back to writer (current commit)
- |reserved |
- +---------+ <--- tail pointer
- | empty |
- +---------+
-
- Write commit:
-
- Buffer page
- +---------+
- |written |
- +---------+
- |written |
- +---------+ <--- next position for write (current commit)
- | empty |
- +---------+
-
-
- If a write happens after the first reserve:
-
- Buffer page
- +---------+
- |written |
- +---------+ <-- current commit
- |reserved |
- +---------+ <--- given back to second writer
- |reserved |
- +---------+ <--- tail pointer
-
- After second writer commits:
-
-
- Buffer page
- +---------+
- |written |
- +---------+ <--(last full commit)
- |reserved |
- +---------+
- |pending |
- |commit |
- +---------+ <--- tail pointer
-
- When the first writer commits:
-
- Buffer page
- +---------+
- |written |
- +---------+
- |written |
- +---------+
- |written |
- +---------+ <--(last full commit and tail pointer)
-
-
-The commit pointer points to the last write location that was
-committed without preempting another write. When a write that
-preempted another write is committed, it only becomes a pending commit
-and will not be a full commit until all writes have been committed.
-
-The commit page points to the page that has the last full commit.
-The tail page points to the page with the last write (before
-committing).
-
-The tail page is always equal to or after the commit page. It may
-be several pages ahead. If the tail page catches up to the commit
-page then no more writes may take place (regardless of the mode
-of the ring buffer: overwrite and produce/consumer).
-
-The order of pages is:
-
- head page
- commit page
- tail page
-
-Possible scenario:
- tail page
- head page commit page |
- | | |
- v v v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-There is a special case that the head page is after either the commit page
-and possibly the tail page. That is when the commit (and tail) page has been
-swapped with the reader page. This is because the head page is always
-part of the ring buffer, but the reader page is not. Whenever there
-has been less than a full page that has been committed inside the ring buffer,
-and a reader swaps out a page, it will be swapping out the commit page.
-
-
- reader page commit page tail page
- | | |
- v | |
- +---+ | |
- | |<----------+ |
- | |<------------------------+
- | |------+
- +---+ |
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
- ^
- |
- head page
-
-
-In this case, the head page will not move when the tail and commit
-move back into the ring buffer.
-
-The reader cannot swap a page into the ring buffer if the commit page
-is still on that page. If the read meets the last commit (real commit
-not pending or reserved), then there is nothing more to read.
-The buffer is considered empty until another full commit finishes.
-
-When the tail meets the head page, if the buffer is in overwrite mode,
-the head page will be pushed ahead one. If the buffer is in producer/consumer
-mode, the write will fail.
-
-Overwrite mode:
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
- ^
- |
- head page
-
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
- ^
- |
- head page
-
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
- ^
- |
- head page
-
-Note, the reader page will still point to the previous head page.
-But when a swap takes place, it will use the most recent head page.
-
-
-Making the Ring Buffer Lockless:
---------------------------------
-
-The main idea behind the lockless algorithm is to combine the moving
-of the head_page pointer with the swapping of pages with the reader.
-State flags are placed inside the pointer to the page. To do this,
-each page must be aligned in memory by 4 bytes. This will allow the 2
-least significant bits of the address to be used as flags, since
-they will always be zero for the address. To get the address,
-simply mask out the flags.
-
- MASK = ~3
-
- address & MASK
-
-Two flags will be kept by these two bits:
-
- HEADER - the page being pointed to is a head page
-
- UPDATE - the page being pointed to is being updated by a writer
- and was or is about to be a head page.
-
-
- reader page
- |
- v
- +---+
- | |------+
- +---+ |
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-H->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-
-The above pointer "-H->" would have the HEADER flag set. That is
-the next page is the next page to be swapped out by the reader.
-This pointer means the next page is the head page.
-
-When the tail page meets the head pointer, it will use cmpxchg to
-change the pointer to the UPDATE state:
-
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-H->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-"-U->" represents a pointer in the UPDATE state.
-
-Any access to the reader will need to take some sort of lock to serialize
-the readers. But the writers will never take a lock to write to the
-ring buffer. This means we only need to worry about a single reader,
-and writes only preempt in "stack" formation.
-
-When the reader tries to swap the page with the ring buffer, it
-will also use cmpxchg. If the flag bit in the pointer to the
-head page does not have the HEADER flag set, the compare will fail
-and the reader will need to look for the new head page and try again.
-Note, the flags UPDATE and HEADER are never set at the same time.
-
-The reader swaps the reader page as follows:
-
- +------+
- |reader| RING BUFFER
- |page |
- +------+
- +---+ +---+ +---+
- | |--->| |--->| |
- | |<---| |<---| |
- +---+ +---+ +---+
- ^ | ^ |
- | +---------------+ |
- +-----H-------------+
-
-The reader sets the reader page next pointer as HEADER to the page after
-the head page.
-
-
- +------+
- |reader| RING BUFFER
- |page |-------H-----------+
- +------+ v
- | +---+ +---+ +---+
- | | |--->| |--->| |
- | | |<---| |<---| |<-+
- | +---+ +---+ +---+ |
- | ^ | ^ | |
- | | +---------------+ | |
- | +-----H-------------+ |
- +--------------------------------------+
-
-It does a cmpxchg with the pointer to the previous head page to make it
-point to the reader page. Note that the new pointer does not have the HEADER
-flag set. This action atomically moves the head page forward.
-
- +------+
- |reader| RING BUFFER
- |page |-------H-----------+
- +------+ v
- | ^ +---+ +---+ +---+
- | | | |-->| |-->| |
- | | | |<--| |<--| |<-+
- | | +---+ +---+ +---+ |
- | | | ^ | |
- | | +-------------+ | |
- | +-----------------------------+ |
- +------------------------------------+
-
-After the new head page is set, the previous pointer of the head page is
-updated to the reader page.
-
- +------+
- |reader| RING BUFFER
- |page |-------H-----------+
- +------+ <---------------+ v
- | ^ +---+ +---+ +---+
- | | | |-->| |-->| |
- | | | | | |<--| |<-+
- | | +---+ +---+ +---+ |
- | | | ^ | |
- | | +-------------+ | |
- | +-----------------------------+ |
- +------------------------------------+
-
- +------+
- |buffer| RING BUFFER
- |page |-------H-----------+ <--- New head page
- +------+ <---------------+ v
- | ^ +---+ +---+ +---+
- | | | | | |-->| |
- | | New | | | |<--| |<-+
- | | Reader +---+ +---+ +---+ |
- | | page ----^ | |
- | | | |
- | +-----------------------------+ |
- +------------------------------------+
-
-Another important point: The page that the reader page points back to
-by its previous pointer (the one that now points to the new head page)
-never points back to the reader page. That is because the reader page is
-not part of the ring buffer. Traversing the ring buffer via the next pointers
-will always stay in the ring buffer. Traversing the ring buffer via the
-prev pointers may not.
-
-Note, the way to determine a reader page is simply by examining the previous
-pointer of the page. If the next pointer of the previous page does not
-point back to the original page, then the original page is a reader page:
-
-
- +--------+
- | reader | next +----+
- | page |-------->| |<====== (buffer page)
- +--------+ +----+
- | | ^
- | v | next
- prev | +----+
- +------------->| |
- +----+
-
-The way the head page moves forward:
-
-When the tail page meets the head page and the buffer is in overwrite mode
-and more writes take place, the head page must be moved forward before the
-writer may move the tail page. The way this is done is that the writer
-performs a cmpxchg to convert the pointer to the head page from the HEADER
-flag to have the UPDATE flag set. Once this is done, the reader will
-not be able to swap the head page from the buffer, nor will it be able to
-move the head page, until the writer is finished with the move.
-
-This eliminates any races that the reader can have on the writer. The reader
-must spin, and this is why the reader cannot preempt the writer.
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-H->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-The following page will be made into the new head page.
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |-H->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-After the new head page has been set, we can set the old head page
-pointer back to NORMAL.
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |-H->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-After the head page has been moved, the tail page may now move forward.
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |-H->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-
-The above are the trivial updates. Now for the more complex scenarios.
-
-
-As stated before, if enough writes preempt the first write, the
-tail page may make it all the way around the buffer and meet the commit
-page. At this time, we must start dropping writes (usually with some kind
-of warning to the user). But what happens if the commit was still on the
-reader page? The commit page is not part of the ring buffer. The tail page
-must account for this.
-
-
- reader page commit page
- | |
- v |
- +---+ |
- | |<----------+
- | |
- | |------+
- +---+ |
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-H->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
- ^
- |
- tail page
-
-If the tail page were to simply push the head page forward, the commit when
-leaving the reader page would not be pointing to the correct page.
-
-The solution to this is to test if the commit page is on the reader page
-before pushing the head page. If it is, then it can be assumed that the
-tail page wrapped the buffer, and we must drop new writes.
-
-This is not a race condition, because the commit page can only be moved
-by the outermost writer (the writer that was preempted).
-This means that the commit will not move while a writer is moving the
-tail page. The reader cannot swap the reader page if it is also being
-used as the commit page. The reader can simply check that the commit
-is off the reader page. Once the commit page leaves the reader page
-it will never go back on it unless a reader does another swap with the
-buffer page that is also the commit page.
-
-
-Nested writes
--------------
-
-In the pushing forward of the tail page we must first push forward
-the head page if the head page is the next page. If the head page
-is not the next page, the tail page is simply updated with a cmpxchg.
-
-Only writers move the tail page. This must be done atomically to protect
-against nested writers.
-
- temp_page = tail_page
- next_page = temp_page->next
- cmpxchg(tail_page, temp_page, next_page)
-
-The above will update the tail page if it is still pointing to the expected
-page. If this fails, a nested write pushed it forward, the the current write
-does not need to push it.
-
-
- temp page
- |
- v
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-Nested write comes in and moves the tail page forward:
-
- tail page (moved by nested writer)
- temp page |
- | |
- v v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-The above would fail the cmpxchg, but since the tail page has already
-been moved forward, the writer will just try again to reserve storage
-on the new tail page.
-
-But the moving of the head page is a bit more complex.
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-H->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-The write converts the head page pointer to UPDATE.
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-But if a nested writer preempts here, it will see that the next
-page is a head page, but it is also nested. It will detect that
-it is nested and will save that information. The detection is the
-fact that it sees the UPDATE flag instead of a HEADER or NORMAL
-pointer.
-
-The nested writer will set the new head page pointer.
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |-H->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-But it will not reset the update back to normal. Only the writer
-that converted a pointer from HEAD to UPDATE will convert it back
-to NORMAL.
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |-H->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-After the nested writer finishes, the outermost writer will convert
-the UPDATE pointer to NORMAL.
-
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |-H->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-
-It can be even more complex if several nested writes came in and moved
-the tail page ahead several pages:
-
-
-(first writer)
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-H->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-The write converts the head page pointer to UPDATE.
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |--->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-Next writer comes in, and sees the update and sets up the new
-head page.
-
-(second writer)
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |-H->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-The nested writer moves the tail page forward. But does not set the old
-update page to NORMAL because it is not the outermost writer.
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |-H->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-Another writer preempts and sees the page after the tail page is a head page.
-It changes it from HEAD to UPDATE.
-
-(third writer)
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |-U->| |--->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-The writer will move the head page forward:
-
-
-(third writer)
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |-U->| |-H->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-But now that the third writer did change the HEAD flag to UPDATE it
-will convert it to normal:
-
-
-(third writer)
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |--->| |-H->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-
-Then it will move the tail page, and return back to the second writer.
-
-
-(second writer)
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |--->| |-H->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-
-The second writer will fail to move the tail page because it was already
-moved, so it will try again and add its data to the new tail page.
-It will return to the first writer.
-
-
-(first writer)
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |--->| |-H->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-The first writer cannot know atomically if the tail page moved
-while it updates the HEAD page. It will then update the head page to
-what it thinks is the new head page.
-
-
-(first writer)
-
- tail page
- |
- v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |-H->| |-H->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-Since the cmpxchg returns the old value of the pointer the first writer
-will see it succeeded in updating the pointer from NORMAL to HEAD.
-But as we can see, this is not good enough. It must also check to see
-if the tail page is either where it use to be or on the next page:
-
-
-(first writer)
-
- A B tail page
- | | |
- v v v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |-H->| |-H->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-If tail page != A and tail page != B, then it must reset the pointer
-back to NORMAL. The fact that it only needs to worry about nested
-writers means that it only needs to check this after setting the HEAD page.
-
-
-(first writer)
-
- A B tail page
- | | |
- v v v
- +---+ +---+ +---+ +---+
-<---| |--->| |-U->| |--->| |-H->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-
-Now the writer can update the head page. This is also why the head page must
-remain in UPDATE and only reset by the outermost writer. This prevents
-the reader from seeing the incorrect head page.
-
-
-(first writer)
-
- A B tail page
- | | |
- v v v
- +---+ +---+ +---+ +---+
-<---| |--->| |--->| |--->| |-H->
---->| |<---| |<---| |<---| |<---
- +---+ +---+ +---+ +---+
-