Spin lock in Linux kernel_ T mechanism

osc_ l8ylygdq 2021-01-21 10:58:21
spin lock linux kernel_ kernel


In depth explanation Linux Kernel network structure and distribution
epoll The concrete realization of and epoll Thread safety , The mutex , spinlocks ,CAS, Atomic manipulation .

spinlock In what scenario ?

Spin locking is used when there is very little code in the critical region .

spinlock What should I pay attention to when I use it ?

  • The critical area code should be as concise as possible
  • Sleep is not allowed ( A deadlock occurs )
  • Need to have interrupts disabled when locked by ordinary threads, if
    shared by an interrupt handler.( A deadlock occurs )

spinlock How did it happen ?

Take a look at the source code :

typedef struct raw_spinlock {

arch_spinlock_t raw_lock;
#ifdef CONFIG_GENERIC_LOCKBREAK
unsigned int break_lock;
#endif
#ifdef CONFIG_DEBUG_SPINLOCK
unsigned int magic, owner_cpu;
void *owner;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
struct lockdep_map dep_map;
#endif
} raw_spinlock_t;
typedef struct spinlock {

union {

struct raw_spinlock rlock;
#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define LOCK_PADSIZE (offsetof(struct raw_spinlock, dep_map))
struct {

u8 __padding[LOCK_PADSIZE];
struct lockdep_map dep_map;
};
#endif
};
} spinlock_t;

If you ignore CONFIG_DEBUG_LOCK_ALLOC word ,spinlock It mainly includes a arch_spinlock_t Structure , You can tell by the name , This structure is related to architecture .

Linux、C/C++ Technology exchange group :【960994558】 I have sorted out some learning books that I think are better 、 Interview questions of Dachang 、 Interesting projects and popular technology teaching videos are shared in it ( Include C/C++,Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK, Streaming media ,CDN,P2P,K8S,Docker,TCP/IP, coroutines ,DPDK wait .), If necessary, you can add it by yourself !~ Insert picture description here

Lock process

Lock the relevant source code as follows :

#define raw_spin_lock(lock) _raw_spin_lock(lock)
static inline void spin_lock(spinlock_t *lock)
{

raw_spin_lock(&lock->rlock);
}

_raw_spin_lock Complete the actual locking action .

according to CPU Architecture ,spinlock It is divided into SMP Version and UP edition , Here we use SMP Version as an example to analyze .SMP In the version ,_raw_spin_lock To declare as :

static inline void __raw_spin_lock(raw_spinlock_t *lock)
{

// No preemption 
preempt_disable();
// for debug
spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
// real work done here
LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}

LOCK_CONTENDED It's a general locking process .do_raw_spin_trylock and do_raw_spin_lock The implementation of depends on the specific architecture , With x86 For example ,do_raw_spin_trylock The final call is :

do_raw_spin_trylock Source code :

static inline int do_raw_spin_trylock(raw_spinlock_t *lock)
{

// Architecture related 
return arch_spin_trylock(&(lock)->raw_lock);
}

With x86 For example ,arch_spin_trylock The final call __ticket_spin_trylock function . Its source code is as follows :

// It's defined in arch/x86/include/asm/spinlock_types.h
typedef struct arch_spinlock {

union {

__ticketpair_t head_tail;
struct __raw_tickets {

__ticket_t head, tail; // Be careful ,x86 It's the small end mode , What has a high address space is tail
} tickets;
};
} arch_spinlock_t;
// It's defined in arch/x86/include/asm in 
static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
{

arch_spinlock_t old, new;
// Get the old ticket Information 
old.tickets = ACCESS_ONCE(lock->tickets);
// head and tail atypism , Indicates that the lock is in use , Lock failed 
if (old.tickets.head != old.tickets.tail)
return 0;
new.head_tail = old.head_tail + (1 << TICKET_SHIFT); // take tail + 1
/* cmpxchg is a full barrier, so nothing can move before it */
return cmpxchg(&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail;
}

As you can see from the above code ,__ticket_spin_trylock Core functions , Is to determine whether the spin lock is occupied , If it's not occupied , Try to update... Atomically lock Medium head_tail Value , take tail+1, Returns whether the lock is successful .

Don't consider CONFIG_DEBUG_SPINLOCK Hong's words , do_raw_spin_lock The source code is as follows :

static inline void do_raw_spin_lock(raw_spinlock_t *lock) __acquires(lock)
{

__acquire(lock);
arch_spin_lock(&lock->raw_lock);
}

arch_spin_lock Source code :

static __always_inline void arch_spin_lock(arch_spinlock_t *lock)
{

__ticket_spin_lock(lock);
}

__ticket_spin_lock Source code :

static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
{

register struct __raw_tickets inc = {
 .tail = 1 };
// Atomically put ticket Medium tail+1, Back to inc yes +1 Previous raw values 
inc = xadd(&lock->tickets, inc);
for (;;) {

// Cycle until head and tail equal 
if (inc.head == inc.tail)
break;
cpu_relax();
// Read the new head value 
inc.head = ACCESS_ONCE(lock->tickets.head);
}
barrier(); /* make sure nothing creeps before the lock is taken */
}

ticket Divided into two parts , Part of it is called tail, It's the end of a queue , One part is called head, The head of a queue . When initializing ,tail and head All are 0, The lock is unoccupied .
__ticket_spin_lock It's atomic tail+1, And the +1 The previous values are recorded , And then keep talking to head Compare . Because it's an atomic operation , So different lock competitors get tail The values are different . If tail Values and head The same , It means that no one is using the lock at this time , The next one to get the lock is himself .

for instance , Assuming that thread A And thread B Competing for the same spin lock :

  • initialization tail=0, head=0, Threads A take tail+1,
    And back to tail The old value 0, take 0 and head Value comparison , equal , So the thread A I got the lock .
  • Threads A Come and get the lock at this time , take tail value +1, become 2, return tail The old value 1, And it head value 0 Compare , It's not equal , Continue to cycle .
  • Threads A I've run out of locks , take head value +1.
  • Threads B Read head value , And add it to tail Value comparison , Find the equality , Gets the lock .

Unlock process

about SMP In terms of Architecture ,spin_unlock The final call is __raw_spin_unlock, Its source code is as follows :

static inline void __raw_spin_unlock(raw_spinlock_t *lock)
{

spin_release(&lock->dep_map, 1, _RET_IP_);
// The main unlocking work 
do_raw_spin_unlock(lock);
// Enable preemption 
preempt_enable();
}
static inline void do_raw_spin_unlock(raw_spinlock_t *lock) __releases(lock)
{

arch_spin_unlock(&lock->raw_lock);
__release(lock);
}

arch_spin_unlock stay x86 The implementation code under the architecture is as follows :

static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
{

__ticket_spin_unlock(lock);
}
static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
{

// take tickers Of head It's worth adding 1
__add(&lock->tickets.head, 1, UNLOCK_LOCK_PREFIX);
}

Consider interrupt handling functions

If the spin lock could be used in interrupt processing , So before we get the spin lock , Local interruptions must be prohibited . be , The kernel code that holds the lock is interrupted by the interrupt handler , Then try to use the spin lock that has been held . The result is , Interrupt handler spin , Wait for the lock to be available again , But the holder of the lock cannot run until the interrupt handler is executed , This becomes a double request deadlock . Be careful , All that needs to be turned off is the interrupt on the current processor . Because interrupts happen on different processors , Even if the interrupt handler spins on the same lock , It won't get in the way of the lock holder ( On different processors ) Finally release .

So use spin_lock_irqsave() / spin_unlock_irqrestore() This version of locking 、 Unlock function .
function spin_lock_irqsave(): Save the current state of the interrupt , Local interruptions are prohibited , Then get the specified lock .
function spin_unlock_reqrestore(): Unlock the specified lock , Restore the interrupt to the state before locking . So even if interruptions were initially prohibited , And the code doesn't activate them by mistake .

spinlock A few varieties of

rwlock_t Read-write lock
seqlock_t Sequential lock

The above shortcomings are welcome to point out the discussion , Feel good friends hope to get your forwarding support , At the same time, you can keep an eye on me

版权声明
本文为[osc_ l8ylygdq]所创,转载请带上原文链接,感谢
https://javamana.com/2021/01/20210121105402015w.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云