Re: [RFC PATCH 16/22 -v2] add get_monotonic_cycles

* Steven Rostedt (rostedt@xxxxxxxxxxx) wrote:

On Wed, 16 Jan 2008, Mathieu Desnoyers wrote:
Hrm, I will reply to the rest of this email in a separate mail, but
there is another concern, simpler than memory ordering, that just hit
me :

If we have CPU A calling clocksource_accumulate while CPU B is calling
get_monotonic_cycles, but events happens in the following order (because
of preemption or interrupts). Here, to make things worse, we would be on
x86 where cycle_t is not an atomic write (64 bits) :


CPU A CPU B

clocksource read
update cycle_mono (1st 32 bits)
read cycle_mono
read cycle_last
clocksource read
read cycle_mono
read cycle_last
update cycle_mono (2nd 32 bits)
update cycle_last
update cycle_acc

Therefore, we have :
- an inconsistant cycle_monotonic value
- inconsistant cycle_monotonic and cycle_last values.

Or is there something I have missed ?

No, there's probably issues there too, but no need to worry about it,
since I already showed that allowing for clocksource_accumulate to happen
inside the get_monotonic_cycles loop is already flawed.


Yep, I just re-read through your previous email, and totally agree that
the algorithm is flawed in the way you pointed out.



If you really want an seqlock free algorithm (I _do_ want this for
tracing!) :) maybe going in the RCU direction could help (I refer to my
RCU-based 32-to-64 bits lockless timestamp counter extension, which
could be turned into the clocksource updater).

I know you pointed me the code, but lets assume that I'm still ignorant
;-)

do you actually use the RCU internals? or do you just reimplement an RCU
algorithm?


Nope, I don't use RCU internals in this code. Preempt disable seemed
like the best way to handle this utterly short code path and I wanted
the write side to be fast enough to be called periodically. What I do is:

- Disable preemption at the read-side :
it makes sure the pointer I get will point to a data structure that
will never change while I am in the preempt disabled code. (see *)
- I use per-cpu data to allow the read-side to be as fast as possible
(only need to disable preemption, does not race against other CPUs and
won't generate cache line bouncing). It also allows dealing with
unsynchronized TSCs if needed.
- Periodical write side : it's called from an IPI running on each CPU.

(*) We expect the read-side (preempt off region) to last shorter than
the interval between IPI updates so we can guarantee the data structure
it uses won't be modified underneath it. Since the IPI update is
launched each seconds or so (depends on the frequency of the counter we
are trying to extend), it's more than ok.

Mathieu

-- Steve

--
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Relevant Pages

  • Re: [2.6.18 PATCH]: Filesystem Event Reporter V4
    ... variuables without turning preemption off. ... Only rmmod will set exit_flag, other users are readers, so I think the lock is unnecessary, ... Each time you add skb into socket queue appropriate socket is ... this issue, missed_refcnt is just for this, start_cpuid is used to identify the cpu ...
    (Linux-Kernel)
  • Re: is minimum udelay() not respected in preemptible SMP kernel-2.6.23?
    ... In my device driver I have to write to a MMIO register, ... If the flag is not reset I write a message via printk. ... Switched to high resolution mode on CPU 0 ... I suppose a lameo fix would be to disable preemption in delay_tsc. ...
    (Linux-Kernel)
  • Re: 2.6.13-rc6-rt6
    ... The do_stop is bound to a CPU when it was created, ... In stopmachine, when PREPARE is seen, it turns off preemption and stops ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)
  • [RFC] Add thread_info flag for "no cpu migration"
    ... The thread below talks about disabling preemption in udelaybecause ... uses per cpu variables and/or hardware often only has the requirement ... Could we add a TIF_ flag that says "no migration to another cpu"? ...
    (Linux-Kernel)
  • Re: [PATCH] release quicklist before free_page
    ... So no need to keep preemption disabled over the whole function. ... We cannot call the page allocator with preemption-disabled, ... per_cpu_locked construct to allow preemption while guarding the per cpu ... * The fast patch in quicklist_alloc touched only a per cpu cacheline and ...
    (Linux-Kernel)