linux-kernel - Re: [RFC][PATCH] ring-buffer: Have nested events still record running time stamp

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Fri, 26 Jun 2020 09:58:01 -0400
From:   Steven Rostedt <rostedt@...dmis.org>
To:     Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Cc:     linux-kernel <linux-kernel@...r.kernel.org>,
        Ingo Molnar <mingo@...nel.org>,
        Peter Zijlstra <peterz@...radead.org>,
        Thomas Gleixner <tglx@...utronix.de>,
        Masami Hiramatsu <mhiramat@...nel.org>,
        Arnaldo Carvalho de Melo <acme@...hat.com>,
        Jiri Olsa <jolsa@...hat.com>,
        Namhyung Kim <namhyung@...nel.org>,
        Yordan Karadzhov <y.karadz@...il.com>,
        Tzvetomir Stoyanov <tz.stoyanov@...il.com>,
        Tom Zanussi <zanussi@...nel.org>,
        Jason Behmer <jbehmer@...gle.com>,
        Julia Lawall <julia.lawall@...ia.fr>,
        Clark Williams <williams@...hat.com>,
        bristot <bristot@...hat.com>, Daniel Wagner <wagi@...om.org>,
        Darren Hart <dvhart@...are.com>,
        Jonathan Corbet <corbet@....net>,
        "Suresh E. Warrier" <warrier@...ux.vnet.ibm.com>
Subject: Re: [RFC][PATCH] ring-buffer: Have nested events still record
 running time stamp

On Thu, 25 Jun 2020 23:35:52 -0400
Steven Rostedt <rostedt@...dmis.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