Just FYI, There are some additional ways to do this, with lower chance
of having to retry.
They increase either space or write cost, so they're not panaceas,
but do reduce the number of read retries to near-zero.
A problem with the current version is that there is only one
guaranteed-consistent copy, so a write always forces concurrent
readers to retry.
So if reading takes a while (the "extract the info I want" is slow)
and writes are frequent, you might retry a lot.
There are two ways to expand the read window.
One is to keep four copies, not two. I have a private patch to the
PPS code that does this, since the data being protected is very small:
a few timestamps. This gives three guaranteed-consistent copies, and a
reader doesn't have to retry unless there have been three writes between
the beginning and end of the sequence.
I.e.
void latch_query(struct latch_struct *latch, struct data *data)
{
unsigned seq;
do {
int idx = (seq = latch->seq) & 3;
smp_rmb();
*data = latch->data[idx]; /* Or extract the portion of interest */
smp_rmb();
} while (latch->seq - seq >= 3u);
}
The second is to update the seqlock twice per write.
While the lsbit of the seqlock is zero, *both* copies are valid, but
the one identified by the second-lsbit is more up to date and preferred.
While the lsbit of the seqlock is one, an update is in progress.
But I may read the old copy. And even if the update completes while
I'm reading, I know my copy is still consistent until the *next*
update starts.
void latch_query(struct latch_struct *latch, struct data *data)
{
unsigned seq;
do {
int idx = (seq = latch->seq) >> 1 & 1;
smp_rmb();
*data = latch->data[idx]; /* Or extract the portion of interest */
smp_rmb();
seq |= 1; /* Could OR or AND, but OR is more available than ANDN. */
} while (latch->seq - seq >= 2u);
}
One note about this version is that, although you need to update the seq variable
twice, it doesn't increase the number of smp_wmb you need. It's:
void latch_modify(struct latch_struct *latch, ...)
{
unsigned seq = latch->seq |= 1;
smp_wmb();
modify(latch->data[++seq >> 1 & 1], ...);
smp_wmb();
latch->seq = seq;
}
> I'm assuming you're writing to me because of the latched rb-tree;
> because that's the most recent related thing I posted ;-)
Basically yes, although it was the documentation you added to the
latched seqlock code in particular.
I haven't checked the users of your rb-tree code to see how large and
frequently read the trees are, but if a read is expensive, then avoiding
retries by incrementing the seqlock twice per update starts to become
interesting.
On Mon, Apr 13, 2015 at 05:26:05AM -0400, George Spelvin wrote:
> > I'm assuming you're writing to me because of the latched rb-tree;
> > because that's the most recent related thing I posted ;-)
>
> Basically yes, although it was the documentation you added to the
> latched seqlock code in particular.
>
> I haven't checked the users of your rb-tree code to see how large and
> frequently read the trees are, but if a read is expensive, then avoiding
> retries by incrementing the seqlock twice per update starts to become
> interesting.
Right, so I use it for modules, and updates are near non existent
under normal usage.