On Thu, 25 Jun 2020 23:35:52 -0400
Steven Rostedt <rost...@goodmis.org> wrote:
> I have to think about this more, as I think there's a flaw in this
> cmpxchg algorithm.
Bah, that was all wrong. I need to incorporate the seq counter into the
time stamp. Luckily I only use 59 bits for a full time stamp (gives me
18 years of nanoseconds), which gives me 5 bits to pay with, and all I
need is 4 (2 for top and 2 for bottom). Now I can make the timestamp 60
bits with 30 bits from the top and 30 from the bottom, and using two
bits in each of those as a sequence counter.
If after reading top and bottom, if the seq bits match, then the two
match and can be put together as a valid number. Now I have this:
struct rb_time_struct {
local_t cnt;
local_t top;
local_t bottom;
};
typedef struct rb_time_struct rb_time_t;
#define RB_TIME_SHIFT 30
#define RB_TIME_VAL_MASK ((1 << RB_TIME_SHIFT) - 1)
static int rb_time_cnt(unsigned long val)
{
return (val >> RB_TIME_SHIFT) & 3;
}
static u64 rb_time_val(unsigned long top, unsigned long bottom)
{
u64 val;
val = top & RB_TIME_VAL_MASK;
val <<= RB_TIME_SHIFT;
val |= bottom & RB_TIME_VAL_MASK;
return val;
}
static inline bool __rb_time_read(rb_time_t *t, u64 *ret, unsigned long *cnt)
{
unsigned long top, bottom;
top = local_read(&t->top);
bottom = local_read(&t->bottom);
*cnt = rb_time_cnt(top);
if (*cnt != rb_time_cnt(bottom))
return false;
*ret = rb_time_val(top, bottom);
return true;
}
static bool rb_time_read(rb_time_t *t, u64 *ret)
{
unsigned long cnt;
return __rb_time_read(t, ret, &cnt);
}
static inline unsigned long rb_time_val_cnt(unsigned long val, unsigned long
cnt)
{
return (val & RB_TIME_VAL_MASK) | ((cnt & 3) << RB_TIME_SHIFT);
}
static inline void rb_time_split(u64 val, unsigned long *top, unsigned long
*bottom)
{
*top = (unsigned long)((val >> RB_TIME_SHIFT) & RB_TIME_VAL_MASK);
*bottom = (unsigned long)(val & RB_TIME_VAL_MASK);
}
static void rb_time_val_set(local_t *t, unsigned long val, unsigned long cnt)
{
val = rb_time_val_cnt(val, cnt);
local_set(t, val);
}
static void rb_time_set(rb_time_t *t, u64 val)
{
unsigned long cnt, top, bottom;
rb_time_split(val, &top, &bottom);
do {
cnt = local_inc_return(&t->cnt);
rb_time_val_set(&t->top, top, cnt);
rb_time_val_set(&t->bottom, bottom, cnt);
} while (cnt != local_read(&t->cnt));
}
static bool rb_time_read_cmpxchg(local_t *l, unsigned long expect, unsigned
long set)
{
unsigned long ret;
ret = local_cmpxchg(l, expect, set);
return ret == expect;
}
static bool rb_time_cmpxchg(rb_time_t *t, u64 expect, u64 set)
{
unsigned long cnt, top, bottom;
unsigned long cnt2, top2, bottom2;
u64 val;
if (!__rb_time_read(t, &val, &cnt))
return false;
if (val != expect)
return false;
cnt2 = local_read(&t->cnt);
if (cnt2 != cnt)
return false;
cnt2++;
rb_time_split(val, &top, &bottom);
top = rb_time_val_cnt(top, cnt);
bottom = rb_time_val_cnt(bottom, cnt);
rb_time_split(set, &top2, &bottom2);
top = rb_time_val_cnt(top2, cnt2);
bottom = rb_time_val_cnt(bottom2, cnt2);
if (!rb_time_read_cmpxchg(&t->cnt, cnt, cnt2))
return false;
if (!rb_time_read_cmpxchg(&t->top, top, top2))
return false;
if (!rb_time_read_cmpxchg(&t->bottom, bottom, bottom2))
return false;
return true;
}
Maybe I might implement this for BITS_FOR_LONG == 32.
-- Steve
