Lines Matching full:sequence
58 * The basic approach is to maintain a monotonic write sequence
60 * Readers record the most recent write sequence number they have
61 * observed. A shared read sequence number records the lowest
62 * sequence number observed by any reader as of the last poll. Any
65 * readers by storing an invalid sequence number in the per-cpu
69 * The write and read sequence numbers can be thought of as a two
72 * that was visible at the time they loaded their copy of the sequence
73 * number. Periodically the read sequence or hand is polled and
74 * advanced as far towards the write sequence as active readers allow.
75 * Memory which was freed between the old and new global read sequence
78 * any sequence number, they only observe them. The shared read
79 * sequence number is consequently never higher than the write sequence.
80 * A stored sequence number that falls outside of this range has expired
84 * that advancing the sequence number is decoupled from detecting its
86 * sequence numbers is not bound. This can be thought of as a more
88 * apart. This results in a more granular assignment of sequence
90 * It also allows writers to advance the sequence number and save the
99 * sequence advancement and waiting. The allocator accumulates a full
100 * per-cpu cache of memory before advancing the sequence. It then
101 * delays waiting for this sequence to expire until the memory is
102 * selected for reuse. In this way we only increment the sequence
104 * after the sequence has been expired so they need only be verified
106 * sequence. Tying the sequence number to the bucket size has the
108 * and the sequence writes become fewer. If the coherency of advancing
109 * the write sequence number becomes too costly we can advance
115 * sequence. The algorithm would then only need to maintain the minimum
124 * | -------------------- sequence number space -------------------- |
126 * | ----- valid sequence numbers ---- |
131 * In this example cpuA has the lowest sequence number and poll can
135 * Freed memory that is tagged with a sequence number between rd seq and
147 #define SMR_SEQ_INIT 1 /* All valid sequence numbers are odd. */
156 * We will block until SMR_SEQ_MAX_ADVANCE sequence numbers have progressed
189 * The maximum sequence number ahead of wr_seq that may still be valid. The
190 * sequence may not be advanced on write for lazy or deferred SMRs. In this
191 * case poll needs to attempt to forward the sequence number if the goal is
210 * Advance a lazy write sequence number. These move forward at the rate of
213 * This returns the goal write sequence number.
253 * Increment the shared write sequence by 2. Since it is initialized
265 * Advance the write sequence number for a normal smr section. If the
266 * write sequence is too far behind the read sequence we have to poll
287 * far ahead of the read sequence number. This keeps the in smr_default_advance()
314 * Advance the write sequence and return the value for use as the
320 * sequence numbers behind the writers.
363 * Poll to determine the currently observed sequence number on a cpu
396 * If the sequence number meets the goal we are done in smr_poll_cpu()
411 * Loop until all cores have observed the goal sequence or have
412 * gone inactive. Returns the oldest sequence currently active;
414 * This function assumes a snapshot of sequence values has
428 * The read sequence can be no larger than the write sequence at in smr_poll_scan()
434 * Query the active sequence on this cpu. If we're not in smr_poll_scan()
464 * sequence number.
468 * This routine will updated the minimum observed read sequence number in
513 * observe an updated read sequence that is larger than write. in smr_poll()
518 * If we have already observed the sequence number we can immediately in smr_poll()
541 * sequence number is valid. in smr_poll()
565 /* Determine the lowest visible sequence number. */ in smr_poll()