[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations
From: |
Paolo Bonzini |
Subject: |
Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations |
Date: |
Thu, 15 Nov 2012 12:24:09 +0100 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:16.0) Gecko/20121016 Thunderbird/16.0.1 |
Il 15/11/2012 08:47, liu ping fan ha scritto:
>>>> RCU prototype required pointer-sized access, which you cannot make type-
>>> But I think that your RCU prototype should rely on atomic of CPU, not
>>> gcc‘s atomic.
>>
>> What's the difference? gcc's atomic produces the same instructions as
>> hand-written assembly (or should).
>>
> Probably I made a mistake here, in vhost, log =
> __sync_fetch_and_and(from, 0) is used to fetch 64bits atomically in
> the case 32bits qemu running on 64bits linux. Right? But how can
> we read 32bits twice in atomic?
You can use cmpxchg8b.
>>> Otherwise, it could be slow (I guess something like spinlock there).
>>
>> Not sure what you mean. I'm using two things: 1) write barriers; 2)
>> atomic_xchg of a pointer for fast, wait-free enqueuing of call_rcu
>> callbacks.
>
> Got your main idea. Will go through your prototype. Just one more
> question, why here atomic_xchg needed? Could not the sequence "read
> old pointer, set new pointer" satisfy your requirement?
No, it would be racy. Say you have this:
wrong right
-----------------------------------------
ref(new) ref(new)
old = tail old = new
tail = new xchg(&old, &tail)
old->next = new old->next = new
up(&sem) up(&sem)
where sem and tail are global, while old and new are local. There can
be any number of producers as in the above scheme, and one consumer. In
the consumer, iteration of the list starts from the second element (the
first element is dummy):
dummy = new Node;
tail = dummy;
for(;;) {
down(&sem);
node = dummy->next;
unref(dummy);
visit node;
dummy = node;
}
Then the invariants are:
- the number of elements N in the list (starting from the dummy node and
following ->next) is always >1. Because of this, you never have to
touch head when adding an element.
- the number of excess signals in the semaphore sem is always <= N-1.
Because of this, it doesn't matter that there is an instant in time
where tail is not reachable from head. The element is really in the
list (as far as the consumer goes) only after the semaphore is signaled.
In the wrong version, two threads could read the same pointer:
x = tail |
y = tail |
tail = new_x |
tail = new_y |
x->next = new_x | old_tail->next = new_x
up(&sem) |
y->next = new_y | old_tail->next = new_x
up(&sem) |
No node points to new_x, so you have 2 nodes reachable from the head
(the dummy node, and new_y) with 2 signals on the semaphore,
contradicting the second invariant.
This instead works:
x = new_x |
y = new_y |
xchg(&x, &tail) | tail = x, x = old_tail
xchg(&y, &tail) | tail = y, y = x
x->next = new_x | old_tail->next = new_x
up(&sem) |
y->next = new_y | x->next = new_y
up(&sem) |
because you have 3 nodes and 2 signals.
Paolo
- [Qemu-devel] [PATCH v6 0/8] push mmio dispatch out of big lock, Liu Ping Fan, 2012/11/05
- [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, Liu Ping Fan, 2012/11/05
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, Paolo Bonzini, 2012/11/12
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, liu ping fan, 2012/11/13
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, Paolo Bonzini, 2012/11/13
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, liu ping fan, 2012/11/14
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, Paolo Bonzini, 2012/11/14
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, liu ping fan, 2012/11/15
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations,
Paolo Bonzini <=
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, Richard Henderson, 2012/11/15
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, liu ping fan, 2012/11/21
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, Avi Kivity, 2012/11/18
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, liu ping fan, 2012/11/21
- Re: [Qemu-devel] [PATCH v6 1/8] atomic: introduce atomic operations, Paolo Bonzini, 2012/11/13
[Qemu-devel] [PATCH v6 2/8] qom: apply atomic on object's refcount, Liu Ping Fan, 2012/11/05
[Qemu-devel] [PATCH v6 3/8] hotplug: introduce qdev_unplug_complete() to remove device from views, Liu Ping Fan, 2012/11/05
[Qemu-devel] [PATCH v6 4/8] pci: remove pci device from mem view when unplug, Liu Ping Fan, 2012/11/05