Re-writing to typedef for easy readability :::: call back pointers :
old implementation : pm_op - Execute the PM operation appropriate for given PM event.@dev: Device to handle.
********************************************************************************
********************************************************************************
typedef int (*pm_callback_t)(struct device *);
********************************************************************************
static pm_callback_t pm_op(const struct dev_pm_ops *ops, pm_message_t state)
********************************************************************************
https://groups.google.com/forum/#!msg/kernelarchive/4UhgVlliQhU/XTKV59UfUYoJ
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4322.html
Paul E. McKenney, paulmck@linux.vnet.ibm.com
At one time,
An
The
Note that a release-acquire pair does not necessarily result in a full barrier. To see this consider the following litmus test, with
The above example showed how
The Linux kernel has an embarrassingly large number of locking primitives, but
Variables of type
That said, many architectures treat
The remaining atomic operations are divided into those that return a value and those that do not. The atomic operations that do not return a value are similar to C11 atomic
The operations are summarized in the following table. An initial implementation of a tool could start with
The rows marked “(Generic)” are type-generic, applying to any aligned machine-word-sized quantity supported by all architectures that the Linux kernel runs on. The set of types is currently those of size
Grace periods can be modeled as described in Appendix D of User-Level Implementations of Read-Copy Update. There are a number of grace-period primitives in the Linux kernel, but
For example, a thread calls the atomic_cmpxchg with these arguments:
If the atomic_cmpxchg is successed, it means that no other thread changed the val variable (without considering ABA problem). The val is not changed, the val is the same to old variable, then the val is changed into new value.
If the atomic_cmpxchg is failed, other threads change the value of val. We sometimes have to make a loop like following.
old implementation : pm_op - Execute the PM operation appropriate for given PM event.@dev: Device to handle.
static int pm_op(struct device *dev, const struct dev_pm_ops *ops, pm_message_t state)
********************************************************************************
pm_op - Return the PM operation appropriate for given PM event.static int (*pm_op(const struct dev_pm_ops *ops, pm_message_t state))(struct device *)
********************************************************************************
typedef int (*pm_callback_t)(struct device *);
********************************************************************************
static pm_callback_t pm_op(const struct dev_pm_ops *ops, pm_message_t state)
********************************************************************************
https://groups.google.com/forum/#!msg/kernelarchive/4UhgVlliQhU/XTKV59UfUYoJ
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4322.html
Linux-Kernel Memory Model
ISO/IEC JTC1 SC22 WG21 N4322 - 2014-11-20Paul E. McKenney, paulmck@linux.vnet.ibm.com
Introduction
The Linux-kernel memory model is currently defined very informally in the memory-barriers.txt and atomic_ops.txt files in the source tree. Although these two files appear to have been reasonably effective at helping kernel hackers understand what is and is not permitted, they are not necessarily sufficient for deriving the corresponding formal model. This document is a first attempt to bridge this gap.- Variable Access
- Memory Barriers
- Locking Operations
- Atomic Operations
- Control Dependencies
- RCU Grace-Period Relationships
- Summary
Variable Access
Loads from and stores to normal variables should be protected with theACCESS_ONCE() macro, for example:Ar1 = ACCESS_ONCE(x); ACCESS_ONCE(y) = 1;
ACCESS_ONCE() access may be modeled as a volatile memory_order_relaxed access. However, please note that ACCESS_ONCE() is defined only for properly aligned machine-word-sized variables. ApplyingACCESS_ONCE() to a large array or structure is unlikely to do anything useful.At one time,
gcc guaranteed that properly aligned accesses to machine-word-sized variables would be atomic. Although gcc no longer documents this guarantee, there is still code in the Linux kernel that relies on it. These accesses could be modeled as non-volatile memory_order_relaxed accesses.An
smp_store_release() may be modeled as a volatile memory_order_release store. Similarly, an smp_load_acquire() may be modeled as a memory_order_acquire load.Members of ther1 = smp_load_acquire(x); smp_store_release(y, 1);
rcu_dereference() family can be modeled as memory_order_consume loads. Members of this family include: rcu_dereference(), rcu_dereference_bh(), rcu_dereference_sched(), andsrcu_dereference(). However, rcu_dereference() should be representative for litmus-test purposes, at least initially. Similarly, rcu_assign_pointer() can be modeled as a memory_order_consume load.The
set_mb() function assigns the specified value to the specified variable, then executes a full memory barrier, which is described in the next section. This isn't as strong as a memory_order_seq_cst store because the following code fragment does not guarantee that the stores to x and y will be ordered.That said,smp_store_release(x, 1); set_mb(y, 1);
set_mb() provides exactly the ordering required for manipulating task state, which is the job for which it was created.Memory Barriers
The Linux kernel has a variety of memory barriers:barrier(), which can be modeled as anatomic_signal_fence(memory_order_acq_rel)or anatomic_signal_fence(memory_order_seq_cst).smp_mb(), which does not have a direct C11 or C++11 counterpart. On an ARM, PowerPC, or x86 system, it can be modeled as a full memory-barrier instruction (dmb,sync, andmfence, respectively). On an Itanium system, it can be modeled as anmfinstruction, but this relies ongccemitting anld,acqfor anACCESS_ONCE()load and anst,relfor anACCESS_ONCE()store.smp_rmb(), which can be modeled (overly conservatively) as anatomic_thread_fence(memory_order_acq_rel). One difference is thatsmp_rmb()need not order prior loads against later stores, or prior stores against later stores. Another difference is thatsmp_rmb()need not provide any sort of transitivity, having (lack of) transitivity properties similar to ARM's or PowerPC's address/control/data dependencies.smp_wmb(), which can be modeled (again overly conservatively) as anatomic_thread_fence(memory_order_acq_rel). One difference is thatsmp_rmb()need not order prior loads against later stores, nor prior loads against later loads. Similar tosmp_rmb(),smp_wmb()need not provide any sort of transitivity.smp_read_barrier_depends(), which is a no-op on all architectures other than Alpha. On Alpha,smp_read_barrier_depends()may be modeled as aatomic_thread_fence(memory_order_acq_rel)or as aatomic_thread_fence(memory_order_seq_cst).smp_mb__before_atomic(), which provides a full memory barrier before the immediately following non-value-returning atomic operation.smp_mb__after_atomic(), which provides a full memory barrier after the immediately preceding non-value-returning atomic operation. Bothsmp_mb__before_atomic()andsmp_mb__after_atomic()are described in more detail in the later section on atomic operations.smp_mb__after_unlock_lock(), which provides a full memory barrier after the immediately preceding lock operation, but only when paired with a preceding unlock operation by this same thread or a preceding unlock operation on the same lock variable. The use ofsmp_mb__after_unlock_lock()is described in more detail in the second on locking.
mmiowb(), however, these cover interactions with memory-mapped I/O, so have no counterpart in C11 and C++11 (which is most likely as it should be for the foreseeable future).Locking Operations
The Linux kernel features “roach motel” ordering on its locking primitives: Prior operations can be reordered to follow a later acquire, and subsequent operations can be reordered to precede an earlier release. The CPU is permitted to reorder acquire and release operations in this way, but the compiler is not, as compiler-based reordering could result in deadlock.Note that a release-acquire pair does not necessarily result in a full barrier. To see this consider the following litmus test, with
x and y both initially zero, and locks l1 and l3 both initially held by the threads releasing them:In the above litmus test, the assertion can trigger, meaning that an unlock followed by a lock is not guaranteed to be a full memory barrier. And this is whereThread 1 Thread 2 -------- -------- y = 1; x = 1; spin_unlock(&l1); spin_unlock(&l3); spin_lock(&l2); spin_lock(&l4); r1 = x; r2 = y; assert(r1 != 0 || r2 != 0);
smp_mb__after_unlock_lock() comes in:In contrast, after addition ofThread 1 Thread 2 -------- -------- y = 1; x = 1; spin_unlock(&l1); spin_unlock(&l3); spin_lock(&l2); spin_lock(&l4); smp_mb__after_unlock_lock(); smp_mb__after_unlock_lock(); r1 = x; r2 = y; assert(r1 != 0 || r2 != 0);
smp_mb__after_unlock_lock(), the assertion cannot trigger.The above example showed how
smp_mb__after_unlock_lock() can cause an unlock-lock sequence in the same thread to act as a full barrier, but it also applies in cases where one thread unlocks and another thread locks the same lock, as shown below:
Thread 1 Thread 2 Thread 3
-------- -------- --------
y = 1; spin_lock(&l1); x = 1;
spin_unlock(&l1); smp_mb__after_unlock_lock(); smp_mb();
r1 = y; r3 = y;
r2 = x;
assert(r1 == 0 || r2 != 0 || r3 != 0);
Without the smp_mb__after_unlock_lock(), the above assertion can trigger, and with it, it cannot. The fact that it can trigger without might seem strange at first glance, but locks are only guaranteed to give sequentially consistent ordering to their critical sections. If you want an observer thread to see the ordering without holding the lock, you need smp_mb__after_unlock_lock(). (Note that there is some possibility that the Linux kernel's memory model will change such that an unlock followed by a lock forms a full memory barrier even without the smp_mb__after_unlock_lock().)The Linux kernel has an embarrassingly large number of locking primitives, but
spin_lock() and spin_unlock() should be representative for litmus-test purposes, at least initially.Atomic Operations
Atomic operations have three sets of operations, those that are defined onatomic_t, those that are defined on atomic_long_t, and those that are defined on aligned machine-sized variables, currently restricted to int and long. However, in the near term, it should be acceptable to focus on a small subset of these operations.Variables of type
atomic_t may be stored to using atomic_set() and variables of type atomic_long_t may be stored to using atomic_long_set(). Similarly, variables of these types may be loaded from usingatomic_read() and atomic_long_read(). The historical definition of these primitives has lacked any sort of concurrency-safe semantics, so the user is responsible for ensuring that these primitives are not used concurrently in a conflicting manner.That said, many architectures treat
atomic_read() atomic_long_read() as volatile memory_order_relaxed loads and a few architectures treat atomic_set() and atomic_long_set() as memory_order_relaxedstores. There is therefore some chance that concurrent conflicting accesses will be allowed at some point in the future, at which point their semantics will be those of volatile memory_order_relaxed accesses.The remaining atomic operations are divided into those that return a value and those that do not. The atomic operations that do not return a value are similar to C11 atomic
memory_order_relaxed operations. However, the Linux-kernel atomic operations that do return a value cannot be implemented in terms of the C11 atomic operations. These operations can instead be modeled as memory_order_relaxedoperations that are both preceded and followed by the Linux-kernel smp_mb() full memory barrier, which is implemented using the DMB instruction on ARM and the sync instruction on PowerPC. Note that in the case of the CAS operations atomic_cmpxchg(), atomic_long_cmpxchg, and cmpxchg(), the full barriers are required in both the success and failure cases. Strong memory ordering can be added to the non-value-returning atomic operations using smp_mb__before_atomic() before and/or smp_mb__after_atomic() after.The operations are summarized in the following table. An initial implementation of a tool could start with
atomic_add(), atomic_sub(), atomic_xchg(), and atomic_cmpxchg().| Operation Class | int | long |
|---|---|---|
| Add/Subtract | void atomic_add(int i, atomic_t *v)void atomic_sub(int i, atomic_t *v)void atomic_inc(atomic_t *v)void atomic_dec(atomic_t *v) | void atomic_long_add(int i, atomic_long_t *v)void atomic_long_sub(int i, atomic_long_t *v)void atomic_long_inc(atomic_long_t *v)void atomic_long_dec(atomic_long_t *v) |
| Add/Subtract, Value Returning | int atomic_inc_return(atomic_t *v)int atomic_dec_return(atomic_t *v)int atomic_add_return(int i, atomic_t *v)int atomic_sub_return(int i, atomic_t *v)int atomic_inc_and_test(atomic_t *v)int atomic_dec_and_test(atomic_t *v)int atomic_sub_and_test(int i, atomic_t *v)int atomic_add_negative(int i, atomic_t *v) | int atomic_long_inc_return(atomic_long_t *v)int atomic_long_dec_return(atomic_long_t *v)int atomic_long_add_return(int i, atomic_long_t *v)int atomic_long_sub_return(int i, atomic_long_t *v)int atomic_long_inc_and_test(atomic_long_t *v)int atomic_long_dec_and_test(atomic_long_t *v)int atomic_long_sub_and_test(int i, atomic_long_t *v)int atomic_long_add_negative(int i, atomic_long_t *v) |
| Exchange | int atomic_xchg(atomic_t *v, int new)int atomic_cmpxchg(atomic_t *v, int old, int new) | int atomic_long_xchg(atomic_long_t *v, int new)int atomic_long_cmpxchg(atomic_code_t *v, int old, int new) |
| Conditional Add/Subtract | int atomic_add_unless(atomic_t *v, int a, int u)int atomic_inc_not_zero(atomic_t *v) | int atomic_long_add_unless(atomic_long_t *v, int a, int u)int atomic_long_inc_not_zero(atomic_long_t *v) |
| Bit Test/Set/Clear (Generic) | void set_bit(unsigned long nr, volatile unsigned long *addr)void clear_bit(unsigned long nr, volatile unsigned long *addr)void change_bit(unsigned long nr, volatile unsigned long *addr) | |
| Bit Test/Set/Clear, Value Returning (Generic) | int test_and_set_bit(unsigned long nr, volatile unsigned long *addr)int _atomic_dec_and_lock(atomic_t *atomic, spinlock_t *lock)int test_and_clear_bit(unsigned long nr, volatile unsigned long *addr)int test_and_change_bit(unsigned long nr, volatile unsigned long *addr) | |
| Lock-Barrier Operations (Generic) | int test_and_set_bit_lock(unsigned long nr, unsigned long *addr)void clear_bit_unlock(unsigned long nr, unsigned long *addr)void __clear_bit_unlock(unsigned long nr, unsigned long *addr) | |
| Exchange (Generic) | T *xchg(T *p, v)T *cmpxchg(T *ptr, T o, T n) | |
intand those of size long. The “Lock-Barrier Operations” have memory_order_acquire semantics for test_and_set_bit_lock() and _atomic_dec_and_lock(), and have memory_order_release for the other primitives. Otherwise, the usual Linux-kernel rule holds: If no value is returned, memory_order_relaxed semantics apply, otherwise the operations behave as if there was smp_mb() before and after.Control Dependencies
The Linux kernel provides a limited notion of control dependencies, ordering prior loads against control-depedendent stores in some cases. Extreme care is required to avoid control-dependency-destroying compiler optimizations. The restrictions applying to control dependencies include the following:- Control dependencies can order prior loads against later dependent stores, however, they do not order prior loads against later dependent loads. (Use
memory_order_consumeormemory_order_acquireif you require this behavior. - A load heading up a control dependency must use
ACCESS_ONCE(). Similarly, the store at the other end of a control dependency must also useACCESS_ONCE(). - If both legs of a given
iforswitchstatement store the same value to the same variable, then those stores cannot participate in control-dependency ordering. - Control dependencies require at least one run-time conditional that depends on the prior load and that precedes the following store.
- The compiler must perceive both the variable loaded from and the variable stored to as being shared variables. For example, the compiler will not perceive an on-stack variable as being shared unless its address has been taken and exported to some other thread (or alias analysis has otherwise been defeated).
- Control dependencies are not transitive. In this regard, their behavior is similar to ARM or PowerPC control dependencies.
RCU Grace-Period Relationships
The publish-subscribe portions of RCU are captured by the combination ofrcu_assign_pointer(), which can be modeled as a memory_order_release store, and of the rcu_dereference() family of primitives, which can be modeled as memory_order_consume loads, as was noted earlier.Grace periods can be modeled as described in Appendix D of User-Level Implementations of Read-Copy Update. There are a number of grace-period primitives in the Linux kernel, but
rcu_read_lock(),rcu_read_unlock(), and synchronize_rcu() are good places to start. The grace-period relationships can be describe using the following abstract litmus test:If either ofThread 1 Thread 2 -------- -------- rcu_read_lock(); S2a; S1a; synchronize_rcu(); S1b; S2b; rcu_read_unlock();
S1a or S1b precedes S2a, then both must precede S2b. Conversely, if either of S1a or S1b follows S2b, then both must follow S2a.Summary
This document makes a first attempt to present a formalizable model of the Linux kernel memory model, including variable access, memory barriers, locking operations, atomic operations, control dependencies, and RCU grace-period relationships. The general approach is to reduce the kernel's memory model to some aspect of memory models that have already been formalized, in particular to those of C11, C++11, ARM, and PowerPC.NAME
atomic_cmpxchg - atomic_cmpxchg functions.
int atomic_cmpxchg(volatile global(3clc) int *p, int cmp, int val);
unsigned int atomic_cmpxchg(volatile global(3clc) unsigned int *p,
unsigned int cmp, unsigned int val);
int atomic_cmpxchg(volatile local(3clc) int *p, int cmp, int val);
unsigned int atomic_cmpxchg(volatile local(3clc) unsigned int *p,
unsigned int cmp, unsigned int val);
DESCRIPTION
Read the 32-bit value (referred to as old) stored at location pointed
by p. Compute (old == cmp) ? val : old and store result at location
pointed by p. The function returns old.
A 64-bit version of this function, atom_cmpxchg(3clc), is enabled by
cl_khr_int64_base_atomics(3clc).
SPECIFICATION
OpenCL Specification[1]
SEE ALSO
atomicFunctions(3clc), atom_cmpxchg(3clc)
Example code of atomic operation
static inline unsigned long atomic_cmpxchg(volatile void *ptr,
unsigned long old,
unsigned long new)
{
unsigned long prev;
/* "0" ; the same constraint with 0th output variable */
/* RAX = old
if RAX == *ptr
*ptr = new
else
RAX = *ptr
*/
/* If success, this returns old value (old == *ptr)
If fail, this returns *ptr value (old != *ptr)
*/
asm volatile("lock;cmpxchgq %1,%2"
: "=a"(prev)
: "r"(new), "m"(*(volatile long *)ptr), "0"(old)
: "memory");
return prev;
}
This is atomic-compare-and-exchange function in Linux kernel. "0" in the constraints means it has the same property to the first property, of 'old' variable, "=a". Therefore 'old' variable is stored in RAX. And the output of the assembly code is prev that is copy of RAX.
The sequence of this code is:
1. old is copied into RAX
2. compxchg does:
- if RAX(old) and *ptr are the same, *ptr = new is done
- otherwise RAX = *ptr is done
3. RAX is copied into prev
4. return prev
Finally if *ptr valus is change, 'old' value is returned. If it is failed to change *ptr, *ptr value is returned.
It means that the atomic_cmpxchg is successful, it returns old value, otherwise *ptr. And *ptr value is turned into new value.
If the atomic_cmpxchg is failed, it returns different value, not old.
Therefore the atomic_cmpxchg can be changed to return TRUE or FALSE like following.
The sequence of this code is:
1. old is copied into RAX
2. compxchg does:
- if RAX(old) and *ptr are the same, *ptr = new is done
- otherwise RAX = *ptr is done
3. RAX is copied into prev
4. return prev
Finally if *ptr valus is change, 'old' value is returned. If it is failed to change *ptr, *ptr value is returned.
It means that the atomic_cmpxchg is successful, it returns old value, otherwise *ptr. And *ptr value is turned into new value.
If the atomic_cmpxchg is failed, it returns different value, not old.
Therefore the atomic_cmpxchg can be changed to return TRUE or FALSE like following.
static inline unsigned long atomic_cmpxchg(volatile void *ptr,
unsigned long old,
unsigned long new)
{
unsigned long prev;
/* "0" -> the same constraint with 0th output variable */
/* RAX <= old
if RAX == *ptr
*ptr <= new
else
RAX <= *ptr
*/
/* If success, this returns old value (old == *ptr)
If fail, this returns *ptr value (old != *ptr)
*/
asm volatile("lock;cmpxchgq %1,%2"
: "=a"(prev)
: "r"(new), "m"(*(volatile long *)ptr), "0"(old)
: "memory");
if (prev == old)
return 1;
else
return 0;
}
For example, a thread calls the atomic_cmpxchg with these arguments:
val = 0x5A; (shared by multi-threads)
old = val; (local variable of the thread)
new = 0xFF; (local variable of the thread)
==> atomic_cmpxchg(val, old, new);
If the atomic_cmpxchg is successed, it means that no other thread changed the val variable (without considering ABA problem). The val is not changed, the val is the same to old variable, then the val is changed into new value.
If the atomic_cmpxchg is failed, other threads change the value of val. We sometimes have to make a loop like following.
val = 0x5A;
do
{
// change val only if its value is 0x5A into 0xFF
old = 0x5A; (local variable)
new = 0xFF; (local variable)
} while(atomic_cmpxchg(val, old, new) == 0);
http://gurugio.blogspot.in/2011/02/example-code-of-atomic-operation.html
http://gurugio.kldp.net/
Memory Consistency & memory barrier - The art of multiprocessor programming B.7.1
The art of multiprocessor programming B.7.1 내용
프로세서가 메모리에 값을 쓰면 그 값은 캐시에 저장되고 dirty로 표시되는데, 나중에 메인 메모리에 써질거라는 표시이다. 최신 프로세서 (ARM도 그렇다) 들은 여러개의 쓰기 요청이 발생했을 때 바로 메인 메모리에 쓰는 것이 아니라 write buffer (읽기는 store buffer)라는 하드웨어 큐에 모아놓고 나중에 한꺼번에 메모리에 적용한다. 쓰기 버퍼가 있는 이유는 여러개의 요청을 한꺼번에 처리하면 효율적이고, 두번째로 특정 주소에 여러번 쓰기가 발생했을 때 이전 쓰기를 취소시켜서 메모리까지 갈 필요가 적어지기 때문이다.
- 지금 디바이스의 레지스터에 연결된 메모리에 쓴 값들이 사라지는 현상때문에 디바이스가 제대로 작동하지 않는 문제가 있다. 내가 메모리에 쓴 값들을 모두 차례대로 메모리에 써야하는데 write buffer 때문에 중간에 값들이 사라지기 때문인것으로 보인다. 이것을 메모리 베리어로 해결해야만 한다.
쓰기 버퍼때문에 생기는 현상이 프로그램에 있는 읽기 쓰기가 순서대로 메모리에 반영되지 않는다는 것이다....중략...컴파일러는 더 안좋게된다. reordering이라는 취적화는 싱글 쓰레드만 고려하는 것인다. 이 reordering때문에 멀티 쓰레드 프로그램에서 알 수 없는 결과가 생길 수 있다.
(중요)예를 들면 한 쓰레드가 버퍼에 데이터를 채우고 버퍼가 찼다는 표시를 했는데 다른 쓰레드는 버퍼가 찾다는 표시는 봤지만 새로운 데이터는 보지 못할 수도 있게된다. 그래서 잘못된 데이터를 읽게 될 수도 있다.
- 지금 디바이스가 리셋되는게 이것 때문일까? 데이터 채우기와 비트 설정 사이에 베리어가 필요한게 아닐까?
메모리 베리어는 쓰기 버퍼를 비우고 베리어가 나타나기 전의 모든 쓰기가 프로세서가 볼 수 있도록 해준다. (visible to the processor that issued the barrier의 해석이 애매함) 메모리 베리어를 꼭 써야하는 곳은 프로세서가 크리티컬 섹션 밖에서 공유 변수들을 읽거나 쓸 때이다.
