linux驱动-基础知识

CSDN 仅用增加百度收录，这里的文章内容不再更新维护。请访问：baron-z.cn 查看、评论，-------------目前网站正在备案可能暂时无法访问，过段时间就能正常访问。

前言:

整理 linux 相关基础知识点，参考文献

• linux 字符设备驱动详解
• LDD3
• 韦东山驱动大全/linux 应用开发完全手册 4.0
• 文中提到的相关博客

特别说明：这篇文章为摘抄总结，非原创文章，如果内容涉及侵权请及时告知，作者会立即删除相关内容。

一、字符设备

    字符设备是指只能一个字节一个字节读写的设备，不能随机读取设备内存中的某一数据，读取数据需要按照先后数据。字符设备是面向流的设备，常见的字符设备有鼠标、键盘、串口、控制台和LED设备等，而字符设备用到的核心数据结构有file、inode、cdev、file_operations。

1、struct file 数据结构

    struct file 结构与用户空间程序中的FILE结构没有任何关联，FILE结构在C库中定义不会出现在内核代码中，struct file 是一个内核结构，它不会出现在用户程序中。struct file 结构代表一个打开的文件(它不仅仅限定于设备驱动程序，系统中每个打开的文件在内核空间都有一个对应的 file 结构)。它由内核在open时创建，并且传递给在该文件上操作的所有函数，直到最后的close函数，在文件的所有实例都被关闭后，内核会释放这个数据结构。在内核和驱动源代码中，struct file 的指针通常被命名为 file 或 filp ，为了不和这个结构本身混淆，我们一致将指向该结构的指针称为 filp，file 则为结构本身。

struct file {
 union {
     struct llist_node        fu_llist;
     struct rcu_head          fu_rcuhead;
 } f_u;
 struct path                  f_path;
#define f_dentry              f_path.dentry
 struct inode                 *f_inode;		
 const struct file_operations *f_op;		

 
 spinlock_t           f_lock;
 atomic_long_t        f_count;
 unsigned int         f_flags;			
 fmode_t              f_mode;			
 struct mutex         f_pos_lock;
 loff_t               f_pos;			
 struct fown_struct   f_owner;
 const struct cred    *f_cred;
 struct file_ra_state f_ra;

　 u64                 f_version;
#ifdef CONFiG_SECURITY
 void         *f_security;
#endif
 
 void         *private_data;           

#ifdef CONFiG_EPOLL
 
 struct list_head     f_ep_links;
 struct list_head     f_tfile_llink;
#endif                                
 struct address_space *f_mapping;
} __attribute__((aligned(4)));        

这个数据结构中驱动相关的几个重要成员变量如下表所示：

重要成员	说明
loff_t f_pos	当前读/写位置。loff_t有64位，驱动程序要知道文件中的当前位置，可以读取这个值，但不要去修改它。read/write会使用他们接收到的最后那个指针参数来更新这一位置，而不是直接针对filp->f_pos进行操作。这一规则的一个例外是llseek方法，该方法的目的本身就是为了修改文件位置
unsigned int f_flags	文件标志，如O_RDONLY、O_NONBLOCK、O_SYNC，检查用户的请求是否是非阻塞式的操作，驱动程序需要检查O_NONBLOCK标志，而其他标志很少用到。注意：检测读写权限应该使用f_mode而不是f_flags。所有这些标志都被定义在中
struct file_operations *f_op;	与文件相关的操作。内核在执行open操作时对这个指针赋值，以后需要处理这个操作时就读取这个指针。
void *private_data;	file 结构的私有数据，被初始化为NULL

2、struct inode 结构体

    内核用inode结构在内部表示文件，因此它和file结构不同，后者表示打开的文件描述。对单个文件可能有多个打开的file文件描述(上层可以多次open一个文件)，但他们都指向同一个inode文件。inode包含文件访问权限、属主、组、大小、生成时间、访问时间、最后修改时间等大量文件信息。部分数据结构如下：

struct inode {
    ...
    umode_t i_mode;        
    uid_t i_uid;           
    gid_t i_gid;           
    dev_t i_rdev;          
    loff_t i_size;         

    struct timespec i_atime; 
    struct timespec i_mtime; 
    struct timespec i_ctime; 

    unsigned int        i_blkbits;
    blkcnt_t        i_blocks;    
    union {
      struct pipe_inode_info  *i_pipe;
      struct block_device *i_bdev; 
      struct cdev *i_cdev;       
    }
    ...
};

    其中驱动对驱动编程有用的成员变量只有两个如下：

成员变量	含义
dev_t i_rdev	表示设备文件inode结构，它包含了真正的设备编号
struct cdev *i_cdev	当inode指向一个字符设备文件时，i_cdev为其对应的cdev结构体指针

    在驱动中也可通过i_rdev获取设备号，内核提供了下面两个函数来获取inode结构中i_rdev字段中的设备号：

unsigned int imajor(struct inode* inode);  //获取主设备号
unsigned int iminor(struct inode* inode);  //获取次设备号

3、struct file_operations 结构体

    该结构体是系统调用与驱动连接的桥梁，例如：当我们在应用层使用open函数打开一个设备的时候，内核会创建一个file结构并关联file_operations中的一组函数，最终会调用到驱动中关联的file_operations结构体实例中open函数。而file_operations定义了一组操作函数，我们不一定全部用到，通常用到什么函数就关联什么函数。

struct file_operations {
  struct module *owner;
  loff_t (*llseek) (struct file *, loff_t, int);
  ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
  ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
  ssize_t (*aio_read) (struct kiocb *, const struct iovec *, unsigned long, loff_t);
  ssize_t (*aio_write) (struct kiocb *, const struct iovec *, unsigned long, loff_t);
  int (*iterate) (struct file *, struct dir_context *);
  unsigned int (*poll) (struct file *, struct poll_table_struct *);
  long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long);
  long (*compat_ioctl) (struct file *, unsigned int, unsigned long);
  int (*mmap) (struct file *, struct vm_area_struct *);
  int (*open) (struct inode *, struct file *);
  int (*flush) (struct file *, fl_owner_t id);
  int (*release) (struct inode *, struct file *);
  int (*fsync) (struct file *, loff_t, loff_t, int datasync);
  int (*aio_fsync) (struct kiocb *, int datasync);
  int (*fasync) (int, struct file *, int);
  int (*lock) (struct file *, int, struct file_lock *);
  ssize_t (*sendpage) (struct file *, struct page *, int, size_t, loff_t *, int);
  unsigned long (*get_unmapped_area)(struct file *, unsigned long, unsigned long, unsigned long, unsigned long);
  int (*check_flags)(int);
  int (*flock) (struct file *, int, struct file_lock *);
  ssize_t (*splice_write)(struct pipe_inode_info *, struct file *, loff_t *, size_t, unsigned int);
  ssize_t (*splice_read)(struct file *, loff_t *, struct pipe_inode_info *, size_t, unsigned int);
  int (*setlease)(struct file *, long, struct file_lock **);
  long (*fallocate)(struct file *file, int mode, loff_t offset,loff_t len);
  int (*show_fdinfo)(struct seq_file *m, struct file *f);
};

    file_operations的重要性不言而喻，因此以下详细给出重要成员的说明.

1）struct module *owner;

    一个指向拥有这个结构的模块的指针，内核使用这个字段以避免在模块的操作正在被使用时卸载该模块，几乎所有情况被初始化为THIS_MODULE。

2）open() 函数

    对设备文件进行的第一个操作，不要求驱动声明一个对应的方法。如果这个函数没有实现，当用户调用open()时，一直显示成功，但是你的驱动不会得到通知。open函数提供给驱动程序以初始化的能力，从而为以后的操作完成初始化做准备。大部分驱动程序中应当完成下面工作。

1. 检测设备特定的错误（注入设备未就绪或类似的硬件问题）
2. 如果设备是首次打开，则对其进行初始化。
3. 如果有必要，更新fop指针
4. 分配并填写置于 filp->private_date 里的数据结构

函数接口	int (*open) (struct inode *inode , struct file *filp);
函数参数	参数含义
inode	为文件节点(详细见前面inode结构)
filp	指向内核创建的文件结构(详细见前面file结构)

3）read() 函数

    用来从设备读取数据，成功时函数返回读取的字节数，返回值是一个 “signed size” 类型, 常常是目标平台本地的整数类型，出错时返回一个负值,如果此函数未实现(被指为NULL)，当用户调用read()时，将得到 -EINVAL 的返回值，它与用户空间的fread()函数对应。

函数接口	ssize_t (*read) (struct file *filp, char __user *buffer, size_t size , loff_t *ppos);
函数参数	参数含义
filp	指向内核创建的文件结构
buffer	为对应放置信息的缓冲区（即用户空间内存地址）
size	为要读取的信息长度,以字节为单位
ppos	为读的位置相对于文件开头的偏移，在读取信息后，这个指针一般都会移动，移动的值为要读取信息的长度值

3）write() 函数

    向设备发送数据，成功时返回写入的字节数，如果此函数未实现，当用户调用write()时，将得到 -EINVAL 的返回值，它与用户空间的fwrite()函数对应

函数接口	ssize_t (*write) (struct file * filp, const char __user *buffer, size_t size, loff_t * ppos);
函数参数	参数含义
filp	指向系统open时内核创建的文件结构
buffe	用户要写入文件的信息缓冲区
size	要写入信息的长度
ppos	当前的读/写位置，这个值通常是用来判断写文件是否越界

注：这个操作和上面的对文件进行读的操作均为阻塞操作

4）ioctl() 函数

    提供设备相关控制命令的实现（既不是读操作也不是写操作），当调用成功时，返回给调用程序一个非负值。如果设备不提供ioctl入口点，则对于任何内核未预先定义的请求，ioctl系统调用将返回错误。(-ENOTTY,“No such ioctl for device, 该设备无此iotcl命令”)。

函数接口	int (*ioctl) (struct inode *inode, struct file *flip, unsigned int cmd, unsigned long arg);
函数参数	参数含义
inode	为文件节点
filp	指向系统open时内核创建的文件结构
cmd	从用户那里不改变地传下来的命令
arg	对应命令的参数

    为了保证用户传递下来的命令安全可靠，内核定义了iotcl命令的组成方式，当使用这个函数是应当遵循这个规则。

a. 命令的组成

• 设备类型
      设备类型由8位组成，在linux下我们将它称为“幻数”，可以是0~0xFF之间的值，内核中的 ioctl-number.txt 给出了一些推荐的和已经被使用的“幻数”，新设备驱动定义“幻数”的时候要避免与其冲突。
• 方向
      方向由2位组成，表示数据传输的方向

参数	参数含义
_IOC_NONE	无数据传输
_IOC_READ	读操作
_IOC_WRITE	写操作
_IOC_READ | _IOC_WRITE	双向操作

• 数据尺寸

    数据长度字段表示涉及的用户数据的大小，这个成员的宽度依赖于体系结构，通常是 13 位或者14 位。

b. 命令生成方式

    linux也给出了该命令生成的方式，用户空间与内核空间应声明为相同方式。声明方式如下：

• _IO()

    用于生成不涉及数据传输的简单命令

#define _IO(type,nr) _IOC(_IOC_NONE,(type),(nr),0)

• _IOR()

    用于生成读操作命令

#define _IOR(type,nr,size) _IOC(_IOC_READ,(type),(nr),
  (_IOC_TYPECHECK(size)))

• _IOW()

    用于生成写操作命令

#define _IOW(type,nr,size) _IOC(_IOC_WRITE,(type),(nr),
  (_IOC_TYPECHECK(size)))

• _IOWR()

    用于生成即可读也可写的操作命令

#define _IOWR(type,nr,size) _IOC(_IOC_READ|_IOC_WRITE,(type),(nr), 
  (_IOC_TYPECHECK(size)))

• _IO、_IOR 等使用的_IOC 宏

#define _IOC(dir,type,nr,size) 
   (((dir) << _IOC_DIRSHIFT) | 
   ((type) << _IOC_TYPESHIFT) | 
   ((nr) << _IOC_NRSHIFT) | 
   ((size) << _IOC_SIZESHIFT))

c. 简单使用

    下面的代码为伪代码，主要用于说明使用方式

#define		DEV_NAME 'D'
#define		DEV_CMD				_IO( DEV_NAME, 0)	//只向内核传递一条DEV_CMD命令
#define		DEV_CMD_READ_SOMTHING	_IOR(DEV_NAME, 1, unsigned int)	//从内核读取一些数据(数据类型 unsigned int)
#define		DEV_CMD_WRITE_SOMTHING	_IOW(DEV_NAME, 2, unsigned int)	//向内核写入一些数据(数据类型 int)

5）llseek()函数

    用来修改一个文件当前读写位置，并将新位置返回，出错时这个函数返回一个负值。如果这个函数指针是NULL，对seek的钓鱼用将会以某种不可预期的方式修改file结构中的位置计数器。

函数接口	loff_t (*llseek) (struct file *filp , loff_t p, int orig);
filp	指向系统open时内核创建的文件结构
p	当前的读/写位置，这个值通常是用来判断写文件是否越界
orig	文件定位的地址，文件开头（SEEK_SET、0），当前位置（SEEK_CUR、1），文件末尾（SEEK_END、2）

更多请参考博客Ph_one以及书籍linux设备驱动开发详解

4、struct cdev 结构体

    这也是字符设备最重要的数据结构之一，在当前的liux内核中每一个字符设备都有一个cdev描述，即一个cdev结构表示一个字符设备。

struct cdev {
  struct kobject kobj; 			
  struct module *owner;			 
  struct file_operations *ops;		
  struct list_head list;
  dev_t dev;				
  unsigned int count;
};

    利用这个数据结构就可以在内核创建一个字符设备，分配和初始化cdev的方式有两种，第一种是直接利用同struct cdev类型创建，除此之外还可以使用运行时使用动态创建以及释放，函数接口如下表所示

函数接口	函数功能
struct cdev *cdev_alloc(void)	动态申请一个cdev内存。
void cdev_put(struct cdev *p)	释放cdev_alloc申请的内存

5、字符设备的注册与卸载

    获得cdev这个结构之后我们还需将其初始化以及注册到内核。

1）cdev_init()初始化函数

void cdev_init(struct cdev *cdev, const struct file_operations *fops)
{
    memset(cdev, 0, sizeof *cdev);            // 将整个结构体清零；
    INIT_LIST_HEAD(&cdev->list);              // 初始化list成员使其指向自身；
    cdev->kobj.ktype = &ktype_cdev_default;   // 初始ktype
    kobject_init(&cdev->kobj);                // 初始化kobj成员；
    cdev->ops = fops                          // 初始化ops成员；
}

    初始化函数主要完成以下几个功能，其中就包括建立cdev和file_operation 之间的连接

1. 将整个cdev结构体清零
2. 初始化list成员使其指向自身
3. 初适化kobj成员
4. 初始化cdev->ops，即建立cdev和file_operation 之间的连接

2）cdev_add()函数

int cdev_add(struct cdev *p, dev_t dev, unsigned count)
{
    p->dev = dev;
    p->count = count;
    return kobj_map(cdev_map, dev, count, NULL, exact_match, exact_lock, p);
}

    其中count参数是应该和该设备关联的设备编号的数量，count经常取1，但是也存在多个设备编号对应一个特定的设备的特殊情况。cdev_add()可能会失败，如果它返回一个负的错误码，则设备不会被添加到系统中。但这个调用几乎总会成功。对cdev_add的调用通常发生在字符设备驱动模块加载函数中，一旦调用成功，我们的设备就"活”了，他的操作就会被内核调用，因此在驱动设备还没有完全准备好处理设备上的操作时，不能调用cdev_add。这个函数主要完成的功能如下：

1. 初始化cdev结构的dev设备号
2. 初始化cdev的设备数目
3. 向系统添加一个cdev，完成字符设备的注册

3）cdev_del()函数

void cdev_del(struct cdev *p)
{
    cdev_unmap(p->dev, p->count);
    kobject_put(&p->kobj);
}

    向系统删除一个cdev，完成字符设备的卸载，对cdev_del的调用通常发生在字符设备驱动模块卸载函数中，当cdev_del被调用后对应的cdev结构就不应被访问了。在早期的内核中还有另外一种注册卸载字符设备的方式，使用register_chrdev()注册用unregister_chrdev()卸载具体如下表所示：

函数接口	int register_chrdev(unsigned int major, const char* name, struct file_operations* fops)
函数参数	参数含义
major	设备的主设备号
name	驱动程序的名称
fops	默认的file_operations结构

    调用这个函数将为给定的主设备号注册0~255作为次设备号，并为每个设备建立一个对应默认cdev结构。使用这一接口的驱动程序必须能够处理所有256个次设备号的open调用，而且也不能使用大于255的主设备号和次设备号。

函数接口	int unregister_chrdev(unsigned int major, const char* name)
函数参数	参数含义
major	要卸载的设备的主设备号
name	要卸载驱动程序的名称

    新的代码中不应在使用这些接口，这种机制在未来的内核中将会消失。

6、设备节点

    设备节点设备驱动程序的接口，出现在文件系统中就好像它是普通文件一样，通常在/dev目录下，创建设备节点的方式有两种，一种是手动创建，linux内核在运行起来之后，在系统中通过命令手动创建，命令如下：

// 创建设备节点
mknod /dev/xyz c（表示是字符设备） 主设备号 次设备号

//查看设备信息：
ls -l /dev/xyz

    除此之外还可以在驱动中自动创建设备文件，该方式依赖于设备模型，字符设备和设备模型的通过设备号关联在一起，只要有设备号就会在 /dev/ 下创建设备节点，参考设备驱动模型，在这篇文章中搜索 devtmpfs_create_node。，一般情况下我们通常按照下面步骤创建

1. 调用class_create()函数，可以用它来创建一个类，这个类存放于sys/class/下面，
2. 再调用 device_create() 函数来在/dev目录下创建相应的设备节点，同时也会在sys/class/下创建出对应的设备文件

// owner: 模块的拥有着，一般为"THIS_MODULE"
// name : 类名，创建成功后显示 "/sys/class/xxx"
struct class *class_create(struct module *owner, const char *name);

// class: 设备模型中设备所属的类
// parent: 要创建的设备的父设备
// devt: 添加该设备的设备号 dev_t，用于关联字符设备
// drvdata: 该设备的私有数据
// fmt: 备名的名称,创建成功后，将出现 "dev/fmt" 已经 "/sys/class/xxx/fmt"
struct device *device_create(struct class *class, struct device *parent, dev_t devt, void *drvdata, const char *fmt, ...)

    当卸载设备的时候使用函数 device_destroy()从linux内核系统设备驱动程序模型中移除一个设备，并删除/sys/devices/virtual目录下对应的设备目录及/dev/目录下对应的设备文

// dev:  创建的设备类
// devt: 对应的设备号
void device_destroy(struct class *dev, dev_t devt);

7、字符设备驱动流程

1）应用层使用open、write、read函数操作dev目录下的设备文件
2）设备文件通过内核中对应设备的主设备号，次设备号，找到对应的file_operations结构
3）调用file_operations结构中对应的open、write、read函数驱动相关硬件进行操作

8、用户与内核内存交互

    用户空间与内核空间之间的数据不能直接进行简单的赋值交互，linux内核提供了两者交互的函数通过 copy_from_user 获取用户空间的数据，通过 copy_to_user 将内核空间的数据传给用户空间，当操作成功后均返回0，操作失败返回负值。

函数接口	static inline unsigned long __must_check copy_from_user(void *to, const void __user *from, unsigned long n)
函数参数	参数含义
to	目标地址，内核空间地址
from	源地址，用户空间地址
n	要拷贝的数据字节数
函数接口	**unsigned long copy_to_user(void __user to, const void from, unsigned long n)
to	目标地址，用户空间地址
from	源地址，内核空间地址
n	要拷贝的数据字节数

二、同步与互斥

    互斥指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。同步指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

参考【干货】同步与互斥的失败例子

1、原子变量 1) 基本概念

     原子操作的基本单位，原子操作指的是由多步操作组成的一个操作。如果操作不能原子地执行，则要么执行完所有的步骤，要么一步也不执行，不可能执行所有步骤的一个子集。原子操作就是不能打断的操作，内核定义的原子变量结构如下:

kernel-4.4/include/linux/types.h

typedef struct{
    volatile int counter;
} atomic_t;

    armv6 之前的架构 soc 不支持 smp，因此原子变量的实现非常简单，直接采用关中断的方式，如下所示

archarmincludeasmatomic.h
#define ATOMIC_OP(op, c_op, asm_op)                 
static inline void atomic_##op(int i, atomic_t *v)  
{                                   
    unsigned long flags;              
                                      // 直接关闭中断
    raw_local_irq_save(flags);      
    v->counter c_op i;              
    raw_local_irq_restore(flags);     // 打开中断
}                                   

#define ATOMIC_OP_RETURN(op, c_op, asm_op)              
static inline int atomic_##op##_return(int i, atomic_t *v)      
{                                   
    unsigned long flags;            
    int val;                        
                                    
    raw_local_irq_save(flags);         // 直接关闭中断 
    v->counter c_op i;              
    val = v->counter;               
    raw_local_irq_restore(flags);     // 打开中断
                                    
    return val;                     
}

#define ATOMIC_FETCH_OP(op, c_op, asm_op)               
static inline int atomic_fetch_##op(int i, atomic_t *v)         
{                                   
    unsigned long flags;            
    int val;                        
                                    
    raw_local_irq_save(flags);        // 直接关闭中断 
    val = v->counter;               
    v->counter c_op i;              
    raw_local_irq_restore(flags);     // 打开中断
                                    
    return val;                     
}

#define ATOMIC_OPS(op, c_op, asm_op)                    
    ATOMIC_OP(op, c_op, asm_op)                 
    ATOMIC_OP_RETURN(op, c_op, asm_op)              
    ATOMIC_FETCH_OP(op, c_op, asm_op)

    smp 系统则是使用内联汇编来实现的。对于 atomic_read 和 atomic_set 这些操作都只需要一条汇编指令，他们本身就是原子的。而 atomic_add 等操作，需要读出，修改，写入则需要特别处理,以 atomic_add 为例说明。

// 删除接续符方便代码阅读
archarmincludeasmatomic.h

#if __LINUX_ARM_ARCH__ >= 6  // 当 arm 架构 > armv6 的实现

#define ATOMIC_OP(op, c_op, asm_op)                 
static inline void atomic_##op(int i, atomic_t *v)          
{                                                     
    unsigned long tmp;                                
    int result;                                       
                                                      
    prefetchw(&v->counter);                           
    __asm__ __volatile__("@ atomic_" #op "n"         
"1: ldrex   %0, [%3]n"         // 从第 3 个操作数 "r" 的地址读出值，存入第 1 个操作数 "=&r"
"   " #asm_op " %0, %0, %4n"   // 将第 0 个操作数 "=&r" 加上第 4 个操作数 "Ir" 结果存回第 0 个操作数 "=&r"
"   strex   %1, %0, [%3]n"     // 将第 0 个操作数的值，即计算的结果，存入第 3 个操作数的值，即 v->counter 中
"   teq %1, #0n"               // 判断返回值是否为 0 如果不是跳转到 1: 重新执行上述操作。
"   bne 1b" 
    // 第 0 个操作数为 "=&r"  值为 result
    // 第 1 个操作数为 "=&r"  值为 tmp
    // 第 2 个操作数为 "+Qo"  值为 v->counter
    // 第 3 个操作数为 "r"    值为 &v->counter
    // 第 4 个操作数为 "cc"   值为 i
    : "=&r" (result), "=&r" (tmp), "+Qo" (v->counter) 
    : "r" (&v->counter), "Ir" (i)                     
    : "cc");                                          
}                                                     

#define ATOMIC_OPS(op, c_op, asm_op)            
    ATOMIC_OP(op, c_op, asm_op)                 
    ATOMIC_OP_RETURN(op, c_op, asm_op)          
    ATOMIC_FETCH_OP(op, c_op, asm_op)

ATOMIC_OPS(add)
ATOMIC_OPS(sub)

    原子操作的实现也主要依靠上述的两条指令 ldrex 和 strex

• ldrex r0, [r1]
  读取 r1 所指内存的数据，存入 r0；

• strex r2, r0, [r1]
  把 r0 的值写入 r1 所指内存，把 r2 设为 0 表示成功。如果没有写入则把 r2 设为 1 表示失败。

    这两条指令怎么实现原子操作的呢，是通过 Local monitor 和 Global monitor 来实现的。Local monitor ：对非共享内存和共享内存都会使用到，是对该 CPU 本地的内存进行标记。 Global monitor ： 对共享内存使用，也就是多个 CPU 都依赖于Global monitor。

对于同一个 cpu 的多线程处理方式如下

thread 1	thread 2	local monitor的状态
		Open Access state
LDREX		Exclusive Access state
	LDREX	Exclusive Access state
	Modify	Exclusive Access state
	STREX	Open Access state
Modify		Open Access state
STREX		在 Open Access state 的状态下，执行 STREX 指令会导致该指令执行失败
		保持Open Access state，直到下一个 LDREX 指令

• 刚开始默认情况 local monitor 的状态为 Open Access state
• thread 1 运行 LDREX 这条指令将 local monitor 的状态修改为 Exclusive Access state。
• 后切换到 thread 2 执行 LDREX 这时检测到 local monitor 的状态为 Exclusive Access state
• 执行 Modify
• 执行 STREX，执行完 STREX 之后 local monitor 被设置为 Open Access state
• 回到 thread 1 执行 Modify
• 执行 STREX ，当执行 STREX 指令会导致该指令执行失败
• 结合前面的汇编实现。这时候 thread 1 又会重新执行 LDREX，Modify，STREX 直到执行成功。以此来实现原子操作。

可以总结出 ldrex 和 strex 的特性如下。

local monitor state	ldrex	strex
Open Access state	指令正常执行且修改 local monitor 状态为 Exclusive Access state	STREX 指令执行失败并返回 1
Exclusive Access state	指令正常执行且修改 local monitor 状态为 Exclusive Access state	STREX 正常执行且 local monitor 被设置为 Open Access state 同时返回 0

    Global monitor 则用于多 cpu 之间的，状态和 local monitor 是一样的，这里就不再赘述了。

参考博客armv7实现原子操作的本质——ldrex和strex指令、ARM同步指令之LDREX和STREX

2) 原子操作

函数接口	接口含义
atomic_t v = ATOMIC_INIT(0)	定义原子变量并初始化v为0
void atomic_set(atomic_t* v,int i)	设置原子变量的值为i
atomic_read(atomic_t* v)	返回原子变量的值
void atomic_add(int i, atomic_t* v)	原子变量增加i
void atomic_sub(int i, atomic_t* v)	原子变量减少i
void atomic_inc(atomic_t* v)	原子变量自增1
void atomic_dec(atomic_t* v)	源自变量自减1
int atomic_inc_and_test(atomic_t* v)	原子变量自增1，并测试其值是否为0。为0返回true，否则返回false
int atomic_dec_and_test(atomic_t* v)	原子变量自减1，并测试其值是否为0。为0返回true，否则返回false
int atomic_sub_and_test(int i, atomic_t* v)	原子变量减少i， 并测试其值是否为0。为0返回true，否则返回false
int atomic_add_return(int i, atomic_t* v)	原子变量的值增加i，并返回新的值
int atomic_sub_return(int i, atomic_t* v)	原子变量的值减少i，并返回新的值
int atomic_inc_return(atomic_t* v)	原子变量的值自增1，并返回新的值
int atomic_dec_return(atomic_t* v)	原子变量的值自减1，并返回新的值
void set_bit(nr,void* addr);	设置addr地址的第nr位，即将nr位置1
void clear_bit(nr, void* addr);	清除addr地址的nr位，即将nr位清0
void chang_bit(nr, void* addr);	将addr的nr为反置
test_bit(nr, void* addr);	返回addr的第nr位
int test_and_set_bit(nt, void* addr);	测试addr的nr位，再设置为1
int test_and_clear_bit(nr, void* addr);	测试addr的nr位，再清为0
int test_and_chang_bit(nr, void* addr);	测试addr的nr位，再反置nr位

2、linux 中的锁

    linux 内核提供了很多类型的锁，他们可以分为两类，自旋锁(spinning lock)、睡眠锁(sleeping lock)。自旋锁就是无法获得锁时，不会休眠，会一直循环等待。睡眠锁则是是无法获得锁时，当前线程就会休眠。

1) 自旋锁 spin_lock

    自旋锁的实现也需要考虑到两种情况，单 cpu 系统和多 cpu 系统(smp 系统)。对于不同的架构自旋锁的实现方式不同，arm 架构自旋锁的数据结构如下所示，其中实现自旋的关键就是 next 和 owner 两个变量。

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;

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 {
    volatile unsigned int lock;
} arch_spinlock_t;

// arch/arm/include/asm/spinlock_types.h
typedef struct {
    union {
        u32 slock;
        struct __raw_tickets { // 实现自旋锁的关键就是 next 和 owner
#ifdef __ARMEB__
            u16 next;
            u16 owner;
#else
            u16 owner;
            u16 next;
#endif
        } tickets;
    };
} arch_spinlock_t;

    对于没有其他 CPU 的单 CPU 系统，如果内核不支持进程抢占（preempt），当前在内核态执行的线程也不可能被其他线程抢占，也就没有其他进程/线程。所以对于不支持进程抢占（preempt）的单 CPU 系统，spin_lock 是空函数，不需要做其他事情。

    如果单 CPU 系统的内核支持进程抢占（preempt），即当前线程正在执行内核态函数时，它是有可能被别的线程抢占的。这时 spin_lock 的实现就是调用 preempt_disable() 函数，关闭 cpu 的进程抢占功能。

// include/linux/spinlock.h
static __always_inline void spin_lock(spinlock_t *lock)
{
    raw_spin_lock(&lock->rlock);
}

#define raw_spin_lock(lock) _raw_spin_lock(lock)

// include/linux/spinlock_api_up.h
#define _raw_spin_lock(lock)            __LOCK(lock)

#define __LOCK(lock)  // 调用 preempt_disable 关闭进程间抢占功能
  do { preempt_disable(); ___LOCK(lock); } while (0)

#define ___LOCK(lock) 
  do { __acquire(lock); (void)(lock); } while (0)

// include/linux/compiler.h
#ifdef __CHECKER__
#define __acquire(x)   __context__(x,1)
#else
define __acquire(x) (void)0 // 为空函数
#endif

    对于 spin_lock_irq()，在 UP 系统中就退化为 local_irq_disable() 和 preempt_disable()，如下所示：

// include/linux/spinlock_api_up.h
#define __LOCK_IRQ(lock)  // 多了一个关中断的操作
  do { local_irq_disable(); __LOCK(lock); } while (0)

    对于多 cpu 系统内核怎么实现自旋锁的呢，先来看一下源码。

//include/linux/spinlock.h
#define raw_spin_lock(lock) _raw_spin_lock(lock)
static __always_inline void spin_lock(spinlock_t *lock)
{
    raw_spin_lock(&lock->rlock);
}


// kernel/locking/spinlock.c
void __lockfunc _raw_spin_lock(raw_spinlock_t *lock)
{
    __raw_spin_lock(lock);
}

//include/linux/spinlock_api_smp.h
static inline void __raw_spin_lock(raw_spinlock_t *lock)
{
    preempt_disable(); // 关闭进程抢占功能
    spin_acquire(&lock->dep_map, 0, 0, _RET_IP_); // 啥也没干
    LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}

//include/linux/lockdep.h
#define spin_acquire(l, s, t, i)        lock_acquire_exclusive(l, s, t, NULL, i)
#define lock_acquire_exclusive(l, s, t, n, i)       lock_acquire(l, s, t, 0, 1, n, i
# define lock_acquire(l, s, t, r, c, n, i)  do { } while (0)

//include/linux/lockdep.h
#define LOCK_CONTENDED(_lock, try, lock)                
do {                                                    
    if (!try(_lock)) {                                   // 
        lock_contended(&(_lock)->dep_map, _RET_IP_);    
        lock(_lock);                                    
    }                                                   
    lock_acquired(&(_lock)->dep_map, _RET_IP_);         
} while (0)

// 宏替换之后得到下面函数
do {                                                    
    if (!do_raw_spin_trylock(lock)) {                                   
        lock_contended(&(lock)->dep_map, _RET_IP_);   
        do_raw_spin_lock(lock);                                   
    }                                                   
    lock_acquired(&(lock)->dep_map, _RET_IP_);        
} while (0)

// linux/spinlock.h
tatic inline int do_raw_spin_trylock(raw_spinlock_t *lock)
{
    return arch_spin_trylock(&(lock)->raw_lock);
}

//arch/alpha/include/asm/spinlock.h
static inline int arch_spin_trylock(arch_spinlock_t *lock)
{
    return !test_and_set_bit(0, &lock->lock); //原子操作测试 lock->lock 的第 0 位再设置为 1
}

// kernel/locking/spinlock_debug.c
void do_raw_spin_lock(raw_spinlock_t *lock)
{
    debug_spin_lock_before(lock);
    arch_spin_lock(&lock->raw_lock);
    debug_spin_lock_after(lock);
}

// arch/arm/include/asm/spinlock.h
static inline void arch_spin_lock(arch_spinlock_t *lock)
{
    unsigned long tmp;
    u32 newval;
    arch_spinlock_t lockval;

    prefetchw(&lock->slock);
    __asm__ __volatile__(
"1: ldrex   %0, [%3]n"       // 取出 lock->slock 中的值存入 lockval
"   add %1, %0, %4n"         // lockval += 1 << TICKET_SHIFT，TICKET_SHIFT == 16，即 ockval.tickets.next ++
"   strex   %2, %1, [%3]n"   // 将 lockval 的计算结果重新赋值给 &lock->slock
"   teq %2, #0n"             // 确认是否写入成功
"   bne 1b"                   // 写入失败则再来一次，确保操作的原子性
    : "=&r" (lockval), "=&r" (newval), "=&r" (tmp)
    : "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
    : "cc");

    // 如果 lockval.tickets.next 不等于 lockval.tickets.owner 则死循环
    while (lockval.tickets.next != lockval.tickets.owner) {
        wfe(); // 将 cpu 进入低功耗待机状态，等待一会
        lockval.tickets.owner = ACCESS_ONCE(lock->tickets.owner); // 更新一下 lock->tickets.owner 的状态。
    }

    // 拿到锁可以进行临界区的访问。
    smp_mb();
}

    由源码可以得出 spin_lock 主要做了下面的事情

• 调用 preempt_disable 关闭进程间的抢占
• 使用 ldrex 和 strex 以实现操作的原子性
• 如果 lockval.tickets.next 不等于 lockval.tickets.owner 如果不相等，循环将 cpu 进入低功耗待机状态，等待一会之后更新一下 lock->tickets.owner 的状态。直到拿到锁为止

    通过 lockval.tickets.next 实现了排队的操作，每一个 spinlock 都有一个独一无二 lockval.tickets.next ，后来的 spinlock 都是在前一个的基础上增加 1，lock->tickets.owner 则保存当前轮到谁来获取临界资源。当我们释放锁的时候只需要将 lock->tickets.owner ++，下一个等待的进程进程就能够拿到对应的锁了。

static inline void arch_spin_unlock(arch_spinlock_t *lock)
{
    smp_mb();
    lock->tickets.owner++;
    dsb_sev();
}

spin_lock 常用了接口如下

函数接口	接口含义
spin_lock_init	初始化自旋锁 lock
spin_lock	如果能够获得自旋锁则立刻返回，否则将在那里等待，直到该自旋锁的持有者释放。
spin_unlock	释放自旋锁 lock
spin_try_lock	尝试获得自旋锁，如果能立刻获得锁返回 true，否则立刻返回 false
spin_lock_bh/spin_unlock_bh	加锁时禁止下半部(软中断)，解锁时使能下半部(软中断)
spin_lock_irq/spin_unlock_irq	加锁时禁止中断，解锁时使能中断
spin_lock_irqsave/spin_lock_restore	加锁时禁止并中断并记录状态，解锁时恢复中断为所记录的状态

2) 信号量

    一个信号量本质上是一个整数值，它和一对函数联合使用，这对函数通常称为 P 和 V。希望进入临界区的进程将在相关信号量上调用 P;如果信号量的值大于 0,则该值会减1，而进程可以继续。相反，如果信号量的值为 0(或者更小)，进程进入休眠并等待直到其他人释放该信号量。对信号量的解锁通过调用 V 来完成；该函数增加信号量的值，并在必要时唤醒等待的进程。当我们需要将信号量用于互斥时，只需将信号量的值设为 1。这样的信号量在任何给定时刻只能由单个线程拥有。内核定义的信号量如下

// include/linux/semaphore.h
struct semaphore {
    raw_spinlock_t      lock;
    unsigned int        count;
    struct list_head    wait_list;
};

可以看出信号量其实也使用了 raw_spinlock_t 这个结构体，来看看源码实现

// kernel/locking/semaphore.c
void down(struct semaphore *sem)
{
    unsigned long flags;

    raw_spin_lock_irqsave(&sem->lock, flags); // 使用自旋锁实现互斥，防止在操作过程被打断
    if (likely(sem->count > 0))
        sem->count--;
    else
        __down(sem);
    raw_spin_unlock_irqrestore(&sem->lock, flags);
}
EXPORT_SYMBOL(down);

static noinline void __sched __down(struct semaphore *sem)
{
    __down_common(sem, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
}

static inline int __sched __down_common(struct semaphore *sem, long state,
                                long timeout)
{
    struct task_struct *task = current; 
    struct semaphore_waiter waiter;

    list_add_tail(&waiter.list, &sem->wait_list); // 将当前信号量添加进 sem->wait_list 链表。
    waiter.task = task;
    waiter.up = false; // 初始化唤醒状态为 false

    for (;;) {
        if (signal_pending_state(state, task)) 
            goto interrupted;
        if (unlikely(timeout <= 0))
            goto timed_out;
        __set_task_state(task, state);        // 设置进程状态为 TASK_UNINTERRUPTIBLE
        raw_spin_unlock_irq(&sem->lock);      // 将前面拿到的锁释放掉，以便其他进行在获取不到信号量是能跑到这里。
        timeout = schedule_timeout(timeout);  // 当今进程进入休眠，调度其他进行运行
        raw_spin_lock_irq(&sem->lock);        // 唤醒后要先拿锁，两个作用防止后面的状态被打断，同时要和后面 raw_spin_unlock_irqrestore 进行配对。
        if (waiter.up)
            return 0;
    }

 timed_out:
    list_del(&waiter.list);
    return -ETIME;

 interrupted:
    list_del(&waiter.list);
    return -EINTR;
}

    总的来说只有得到信号量的进程才能执行临界区的代码，当得不到信号量时，进程会进入休眠等待状态。并将当前进程放入对应的链表中。当有信号量被释放时遍历这个链表，唤醒被休眠的进程继续执行。信号量释放的流程如下。

void up(struct semaphore *sem)
{
    unsigned long flags;

    raw_spin_lock_irqsave(&sem->lock, flags); // 拿锁实现互斥，防止同时间其他信号量的释放带来的异常。
    if (likely(list_empty(&sem->wait_list))) // 当队列中没有需要获取信号量的进程时释放信号量
        sem->count++; 
    else
        __up(sem); // 唤醒队列中的第一个进行并将信号量交给该进程。
    raw_spin_unlock_irqrestore(&sem->lock, flags);
}
EXPORT_SYMBOL(up);

static noinline void __sched __up(struct semaphore *sem)
{
    struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
                        struct semaphore_waiter, list); // 获取队列中的第一项
    list_del(&waiter->list);       // 从队列中将其删除
    waiter->up = true;             // 设置其唤醒状态
    wake_up_process(waiter->task); // 唤醒这个进程
}

    常用接口

函数接口	接口含义
DECLARE_MUTEX(name);	将信号量name初始化为1
DECLARE_MUTEX_LOCKED(name);	将信号量name初始化为0
void init_MUTEX(struct semaphore *sem)	将信号量sem初始化为1
void init_NUTEX_LOCKED(struct semaphore *sem);	将信号量sem初始化为0
void sema_init(struct semaphore* sem, int val);	初始化信号量的值为 val
void down(struct semaphore *sem);	递减信号量的值，获取不到是进程进入休眠
int down_interruptible(struct semaphore *sem);	递减信号量的值，获取不到是进程进入休眠，但是操作是可以中断的，它允许一个在等待的信号量的用户空间进程被用户中断。如果在操作中被中断，函数会返回一个非零值，并且调用者不持有信号量，真确的使用它需要一直检查返回值并针对性地响应。
int down_trylock(struct seamphore* sem);	永远不会休眠，如果信号量在调用时不可获得，它会返回一个非零值
void up(struct semaphore *sem);	当队列中没有需要获取信号量的进程时释放信号量，如果有则唤醒队列中的第一个线程同时将信号量的持有转交给该线程

    任何拿到信号量的线程都必须通过一次对 up 的调用而释放该信号量。在出现错误的情况下，经常需要特别小心。如果在拥有一个信号量时发生错误，必须将错误状态返回给调用者之前释放该信号量。忘记释放信号量将导致进程在某些无关的位置被意外挂起，很难复现和跟踪

3) 互斥锁

    互斥锁主要用于实现内核中的互斥访问功能。一般用来保护一段代码，的数据结构如下：

struct mutex {
    
    atomic_t        count; // 1 表示unlocked，0 表示有线程拿锁，但是没有其他线程排队， -1 表示有线程拿锁，并且有其他线程在排队。
    spinlock_t      wait_lock;
    struct list_head    wait_list;
#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_MUTEX_SPIN_ON_OWNER)
    struct task_struct  *owner; // 用来调试或者优化性能，只有位两个不同的 cpu 进程同时拿锁时，并且只有一个在等待时，就不会休眠会多等待一回合，提高效率。
#endif
#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
    struct optimistic_spin_queue osq; 
#endif
#ifdef CONFIG_DEBUG_MUTEXES
    void            *magic;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
    struct lockdep_map  dep_map;
#endif
};

    mutex 的实现分为两个部分 fastpath 和 slowpath。如果 fastpath 成功就不再使用 slowpath。同样的 mutex 的实现在不同的架构下实现方式也不同

// arch/arm/include/asm/mutex.h
#if __LINUX_ARM_ARCH__ < 6
#include 
#else
#include 
#endif
#endif  

armv6 之前的实现就不贴出来了，基本差不多。

// kernel/locking/mutex.c
void __sched mutex_lock(struct mutex *lock)
{
    might_sleep();
    
    __mutex_fastpath_lock(&lock->count, __mutex_lock_slowpath);
    mutex_set_owner(lock);
}

// include/asm-generic/mutex-dec.h
static inline void
__mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
{
    // 如果 count 的初始值 为 1
    // 减 1 后为 0, if 条件不成立直接得到锁返回
    // 如果初始 count < = 0 减 1 后 <= 0 调用回调函数 fail_fn 即 __mutex_lock_slowpath
    if (unlikely(atomic_dec_return_acquire(count) < 0))
        fail_fn(count);
}

// kernel/locking/mutex.c
__mutex_lock_slowpath(atomic_t *lock_count)
{
    struct mutex *lock = container_of(lock_count, struct mutex, count);

    __mutex_lock_common(lock, TASK_UNINTERRUPTIBLE, 0,
                NULL, _RET_IP_, NULL, 0);
}

 
static __always_inline int __sched
__mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
            struct lockdep_map *nest_lock, unsigned long ip,
            struct ww_acquire_ctx *ww_ctx, const bool use_ww_ctx)
{
    struct task_struct *task = current;
    struct mutex_waiter waiter;
    unsigned long flags;
    int ret;

    if (use_ww_ctx) { // 为 0 直接跳过
        struct ww_mutex *ww = container_of(lock, struct ww_mutex, base);
        if (unlikely(ww_ctx == READ_ONCE(ww->ctx)))
            return -EALREADY;
    }

    preempt_disable(); // 关闭 cpu 线程抢占功能
    mutex_acquire_nest(&lock->dep_map, subclass, 0, nest_lock, ip);

    // 也许其他 cpu 获得了 mutex 它会很快释放，可能不需要休眠
    if (mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx)) {
        
        preempt_enable();
        return 0;
    }

    // 获取 spin_lock 实现操作的互斥性
    spin_lock_mutex(&lock->wait_lock, flags);

    // 再次尝试获取 mutex 锁。 
    if (!mutex_is_locked(lock) &&
        (atomic_xchg_acquire(&lock->count, 0) == 1))
        goto skip_wait;

    debug_mutex_lock_common(lock, &waiter);
    debug_mutex_add_waiter(lock, &waiter, task);

    // 将当前进程放入 mutex 的 wait_list,这个 wait_list 是 FIFO ，谁先排队，谁就可以先得到 mutex。
    list_add_tail(&waiter.list, &lock->wait_list);
    waiter.task = task;

    lock_contended(&lock->dep_map, ip);

    for (;;) {
   
        // 再次尝试获取锁
        // 如果 count == 1 ，表示锁没有人用，我们将其设置为 -1 ，直接退出
        // 如果 count == 0 ，表示锁被人拿走，并且没人排队，我们将其设置为 -1，继续往下
        // 如果 count < 0 ，表示锁被别人拿走，并且有人在排队，继续往下
        if (atomic_read(&lock->count) >= 0 &&
            (atomic_xchg_acquire(&lock->count, -1) == 1))
            break;

        // 检测进程是否可以休眠，如果有信号在 pending 状态，而且 state 状态还是UNINTERRUPTIBLE 状态的话，是不能休眠等待的
        if (unlikely(signal_pending_state(state, task))) {
            ret = -EINTR;
            goto err;
        }

        if (use_ww_ctx && ww_ctx->acquired > 0) { // use_ww_ctx 为 0
            ret = __ww_mutex_lock_check_stamp(lock, ww_ctx);
            if (ret)
                goto err;
        }

       // 设置进程状态
        __set_task_state(task, state);

        
        spin_unlock_mutex(&lock->wait_lock, flags);
        schedule_preempt_disabled(); // 调度进程进入休眠
        spin_lock_mutex(&lock->wait_lock, flags);
    }
    __set_task_state(task, TASK_RUNNING);

    // 将当前进程从 mutex 链表中删除
    mutex_remove_waiter(lock, &waiter, task);
    
    // 如过没有其他进程等待获取 mutex 锁将 count 设置为 0
    if (likely(list_empty(&lock->wait_list)))
        atomic_set(&lock->count, 0);
    debug_mutex_free_waiter(&waiter);

skip_wait:
    
    lock_acquired(&lock->dep_map, ip);
    mutex_set_owner(lock);

    if (use_ww_ctx) {
        struct ww_mutex *ww = container_of(lock, struct ww_mutex, base);
        ww_mutex_set_context_slowpath(ww, ww_ctx);
    }

    spin_unlock_mutex(&lock->wait_lock, flags); // 关闭前面获取的 spin lock
    preempt_enable(); // 打开进程抢占功能，到这里我们已经获取到 mutex 锁，可以正常访问临界区了。
    return 0;

err:
    mutex_remove_waiter(lock, &waiter, task);
    spin_unlock_mutex(&lock->wait_lock, flags);
    debug_mutex_free_waiter(&waiter);
    mutex_release(&lock->dep_map, 1, ip);
    preempt_enable();
    return ret;
}

    总结：进程在获取 mutex 锁时 count 为 1 时，将 count 减 1 直接获取该锁，访问临界区。如果获取锁时获取不到，则进入如下的休眠流程。

• 将当前进程放入 mutex 的 wait_list
• 将 count 设置为 -1 ，表示有进程正在排队
• 设置进程状态，进程休眠，调度其他进程工作

    再来看一下释放流程

// kernel/locking/mutex.c
void __sched mutex_unlock(struct mutex *lock)
{

#ifndef CONFIG_DEBUG_MUTEXES
    mutex_clear_owner(lock);
#endif
    __mutex_fastpath_unlock(&lock->count, __mutex_unlock_slowpath);
}

EXPORT_SYMBOL(mutex_unlock);

// include/asm-generic/mutex-dec.h
 
static inline void
__mutex_fastpath_unlock(atomic_t *count, void (*fail_fn)(atomic_t *))
{
    // count 曾加 1 如果结果 > 0 表示无人等待直接返回。
    if (unlikely(atomic_inc_return_release(count) <= 0))
        fail_fn(count);
}

// kernel/locking/mutex.c
__visible void __mutex_unlock_slowpath(atomic_t *lock_count)
{
    struct mutex *lock = container_of(lock_count, struct mutex, count);

    __mutex_unlock_common_slowpath(lock, 1);
}

// kernel/locking/mutex.c
__mutex_unlock_common_slowpath(struct mutex *lock, int nested)
{
    unsigned long flags;
    WAKE_Q(wake_q);

    // __mutex_slowpath_needs_to_unlock() 这是个宏被初始化为 1
    // 因此这里就是将 count 设置为 1
    if (__mutex_slowpath_needs_to_unlock())
        atomic_set(&lock->count, 1);

    // 获取 spin lock
    spin_lock_mutex(&lock->wait_lock, flags);
    mutex_release(&lock->dep_map, nested, _RET_IP_);
    debug_mutex_unlock(lock);

    if (!list_empty(&lock->wait_list)) {
        // 如果还有进程在等待获取锁则，从 wait_list 中取出第一个进程
        struct mutex_waiter *waiter =
                list_entry(lock->wait_list.next,
                       struct mutex_waiter, list);

        debug_mutex_wake_waiter(lock, waiter);
        wake_q_add(&wake_q, waiter->task);
    }
    
    // 释放前面获取的 spin lock
    spin_unlock_mutex(&lock->wait_lock, flags);
    wake_up_q(&wake_q); // 唤醒这个进程
}

    总结：如果 count = 0 表示没线程等待，直接将 count 加 1。如果 count 等于 -1 表示有线程等待，进入唤醒流程

• 从 wait_list 中取出第一个进程，并将其唤醒
• 根据是否还有进程在等待设置 count 的状态，有进程等待设置为 -1，没有则设置为 0
• 唤醒的进程从 mutex 链表中删除自己
• 被唤醒的进程访问临界区资源

    常用接口如下

函数接口	接口含义
DEFINE_MUTEX(name);	静态创建化互斥锁 name
mutex_init(&mutex);	动态初始化互斥锁 mutex
mutex_lock(lock)；	获取互斥锁，获取不到则进入睡眠
mutex_trylock(lock)；	尝试获取互斥锁，成功返回1， 失败返回0
mutex_unlock(lock)；	释放互斥锁
mutex_is_lock(lock)；	如果锁已被使用返回1，否则返回0

4) 锁的使用场景

• 在可以睡眠的用户上下文中加锁使用信号量(semaphore)和互斥锁(mutex)。其中 mutex 一般不会被长期持有，用于保护一段代码。
• 在用户上下文与 Softirqs 之间加锁使用 spin_lock_bh/spin_unlock_bh
• 在用户上下文与 Tasklet 之间加锁 spin_lock_bh/spin_unlock_bh
• 在用户上下文与 Timer 之间加锁 spin_lock_bh/spin_unlock_bh
• 不同 cpu 之间在 Tasklet 与 Timer 之间无需加锁
• 在 Softirq 之间加锁 spin_lock/pin_unlock

三、linux 队列 1、等待队列

    等待队列从功能上可以简单理解为：让进程进入睡眠，在你想让他工作的时候唤醒。它有两部分组成首先是挂接我们等待队列项的等待头，等待队列头的数据结构描述如下

include/linux/wait.h

struct __wait_queue_head {
    spinlock_t      lock; // 在对task_list与操作的过程中，使用该锁实现对等待队列的互斥访问。
    struct list_head    task_list; // 链接等待进程 wait_queue_t
};
typedef struct __wait_queue_head wait_queue_head_t;

而挂接在其上面的等待队列项的数据局结构如下

typedef struct wait_queue_entry wait_queue_entry_t;


#define WQ_FLAG_EXCLUSIVE   0x01
#define WQ_FLAG_WOKEN       0x02
#define WQ_FLAG_BOOKMARK    0x04

struct wait_queue_entry {
    unsigned int        flags;
    void            *private;  // 保存当前任务的 task_struct 对象地址，一般默认为 current
    wait_queue_func_t   func;  // 唤醒函数的回调函数，一般默认为 default_wake_function
    struct list_head    entry; // 用于将该结构挂接到 wait_queue_head_t
};

他们的创建与与初始化如下

函数接口	接口含义
DECLARE_WAIT_QUEUE_HEAD(name)	声明等待队列头 name
init_waitqueue_head(name)	初始化等待队列头 name
DECLARE_WAITQUEUE(name, tsk)	定义等待队列成员 name

2. 添加/删除等待队列成员

void add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
    unsigned long flags;

    wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE; //将 WQ_FLAG_EXCLUSIVE 清零
    spin_lock_irqsave(&wq_head->lock, flags);
    __add_wait_queue(wq_head, wq_entry);
    spin_unlock_irqrestore(&wq_head->lock, flags);
}
EXPORT_SYMBOL(add_wait_queue);

static inline void __add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
    list_add(&wq_entry->entry, &wq_head->head);
}

void add_wait_queue_exclusive(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
    unsigned long flags;

    wq_entry->flags |= WQ_FLAG_EXCLUSIVE; //将 WQ_FLAG_EXCLUSIVE 置为
    spin_lock_irqsave(&wq_head->lock, flags);
    __add_wait_queue_entry_tail(wq_head, wq_entry);
    spin_unlock_irqrestore(&wq_head->lock, flags);
}
EXPORT_SYMBOL(add_wait_queue_exclusive);

static inline void __add_wait_queue_entry_tail(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
    list_add_tail(&wq_entry->entry, &wq_head->head);
}

void remove_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
    unsigned long flags;

    spin_lock_irqsave(&wq_head->lock, flags);
    __remove_wait_queue(wq_head, wq_entry);
    spin_unlock_irqrestore(&wq_head->lock, flags);
}
EXPORT_SYMBOL(remove_wait_queue);

static inline void __remove_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
    list_del(&wq_entry->entry);
}

3. 进程休眠

函数接口	接口含义
wait_event(wq, condition)	如果condition为0，则进程休眠，且休眠状态不能被中断打断
wait_event_timeout(wq, condition, timeout)	如果condition为0，则进入休眠，当 timeout 到了则唤醒进程不管此时condition为真为假都会返回
wait_event_interruptible(wq, condition)	如果condition为0，则进程休眠，休眠状态可以被中断打断，当休眠被中断打断时返回0，这时驱动应返回 -ERESTARTSYS
wait_event_interruptible_timeout(wq, condition, timeout)	如果condition为0，则进程休眠，休眠状态可以被中断打断，当休眠被中断打断时返回0，这时驱动应返回 -ERESTARTSY，当 timeout 到了则唤醒进程不管此时condition为真为假都会返回

源码分析如下

1) wait_event

#define wait_event(wq_head, condition)                      
do {                                        
    might_sleep();                              
    if (condition) //如果 condition  为真直接返回     
        break;                              
    __wait_event(wq_head, condition);                   
} while (0)

#define __wait_event(wq_head, condition)                    
    (void)___wait_event(wq_head, condition, TASK_UNINTERRUPTIBLE, 0, 0, schedule())

2) ___wait_event

//__wait_event 的默认值如下
//state = TASK_UNINTERRUPTIBLE
//exclusive = 0
//ret = 0
//cmd = schedule()
#define ___wait_event(wq_head, condition, state, exclusive, ret, cmd)       
({                                      
    __label__ __out;                            
    //创建一个等待队列成员 __wq_entry
    struct wait_queue_entry __wq_entry;                
    long __ret = ret;                  
                                                         
    //初始化等待队列成员 __wq_entry
    //flags 为 0
    //private 被初始化为 current
    //fun 被初始化为 autoremove_wake_function
    init_wait_entry(&__wq_entry, exclusive ? WQ_FLAG_EXCLUSIVE : 0);    
    for (;;) {    //死循环
        // 1. 检查当前信号是否有待处理的信号
        // 2. 检测链表状态防止等待队列成员未插入等待队列头
        // 3. 设置进程状态为 TASK_UNINTERRUPTIBLE
        long __int = prepare_to_wait_event(&wq_head, &__wq_entry, state);
                                        
        if (condition)    //再次检测 condition 如果为真则返回                  
            break;                          
         //进程有待处理信号且处于可中断状态(TASK_INTERRUPTIBLE、TASK_KILLABLE)则跳出循环                               
        if (___wait_is_interruptible(state) && __int) {         
            __ret = __int;                      
            goto __out;                     
        }                               
                                        
        cmd; //调用 schedule() 函数,让进程休眠，调度其他进程工作。
    }                                   
    finish_wait(&wq_head, &__wq_entry);                 
__out:  __ret;                                  
})

3) init_wait_entry

void init_wait_entry(struct wait_queue_entry *wq_entry, int flags)
{
    wq_entry->flags = flags;
    wq_entry->private = current;
    wq_entry->func = autoremove_wake_function;
    INIT_LIST_HEAD(&wq_entry->entry);
}
EXPORT_SYMBOL(init_wait_entry);

4). prepare_to_wait_event

long prepare_to_wait_event(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry, int state)
{
    unsigned long flags;
    long ret = 0;

    spin_lock_irqsave(&wq_head->lock, flags);
    if (unlikely(signal_pending_state(state, current))) { // 检测信号状态是否是待处理状态

        list_del_init(&wq_entry->entry);
        ret = -ERESTARTSYS;
    } else {
        if (list_empty(&wq_entry->entry)) { // 检查链表是否已经插入等待队列头
            if (wq_entry->flags & WQ_FLAG_EXCLUSIVE)
                __add_wait_queue_entry_tail(wq_head, wq_entry); //将其插入到队列头的尾部
            else
                __add_wait_queue(wq_head, wq_entry); //将其插入到等待队列头
        }
        set_current_state(state); //设置进程状态为 TASK_UNINTERRUPTIBLE
    }
    spin_unlock_irqrestore(&wq_head->lock, flags);

    return ret;
}
EXPORT_SYMBOL(prepare_to_wait_event);

4. 唤醒进程

函数接口	接口含义
void wake_up(wait_queue_head_t *q);	唤醒等待队列 q 上的进程，如果 condition 为真则返回
void wake_up_interruptible(wait_queue_head_t *q);	唤醒等待队列 q 上的进程，如果 condition 为真则返回

源码分析如下

1) __wake_up

void __wake_up(struct wait_queue_head *wq_head, unsigned int mode,
            int nr_exclusive, void *key)
{
    __wake_up_common_lock(wq_head, mode, nr_exclusive, 0, key);
}
EXPORT_SYMBOL(__wake_up);

static void __wake_up_common_lock(struct wait_queue_head *wq_head, unsigned int mode,
            int nr_exclusive, int wake_flags, void *key)
{
    unsigned long flags;
    wait_queue_entry_t bookmark; // 创建一个等待队列成员 bookmark

    bookmark.flags = 0;          // 初始化 flag 为 0
    bookmark.private = NULL;     // 初始化 private 为空
    bookmark.func = NULL;        // 初始化唤醒函数为空
    INIT_LIST_HEAD(&bookmark.entry);

    spin_lock_irqsave(&wq_head->lock, flags);
    nr_exclusive = __wake_up_common(wq_head, mode, nr_exclusive, wake_flags, key, &bookmark);
    spin_unlock_irqrestore(&wq_head->lock, flags);

    while (bookmark.flags & WQ_FLAG_BOOKMARK) {
        spin_lock_irqsave(&wq_head->lock, flags);
        nr_exclusive = __wake_up_common(wq_head, mode, nr_exclusive,
                        wake_flags, key, &bookmark);
        spin_unlock_irqrestore(&wq_head->lock, flags);
    }
}

2) __wake_up_common

static int __wake_up_common(struct wait_queue_head *wq_head, unsigned int mode,
            int nr_exclusive, int wake_flags, void *key,
            wait_queue_entry_t *bookmark)
{
    wait_queue_entry_t *curr, *next;
    int cnt = 0;

    if (bookmark && (bookmark->flags & WQ_FLAG_BOOKMARK)) {
        curr = list_next_entry(bookmark, entry); //获取bookmark的下一个等待队列成员

        list_del(&bookmark->entry); //删除当前成员 bookmark
        bookmark->flags = 0; //将当前的 flag 清零
    } else
        curr = list_first_entry(&wq_head->head, wait_queue_entry_t, entry); //查找等待队列头的第一个的等待队列成员

    if (&curr->entry == &wq_head->head) //如果当前等待队列是空则直接返回
        return nr_exclusive;

    list_for_each_entry_safe_from(curr, next, &wq_head->head, entry) { //从 curr 的下一个等待成员开始循环遍历一遍等待队列头中的等待队列成员。
        unsigned flags = curr->flags; //获取 flags
        int ret;

        if (flags & WQ_FLAG_BOOKMARK) //如果为 WQ_FLAG_BOOKMARK 进入下次循环
            continue;

        //调用对应的 func 成员函数,一般为默认的唤醒函数 autoremove_wake_function
        ret = curr->func(curr, mode, wake_flags, key);
        if (ret < 0)
            break;
        
        //如果唤醒的进程的 flags 为WQ_FLAG_EXCLUSIVE 且 nr_exclusive 为 0 则推出
        if (ret && (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
            break;

        if (bookmark && (++cnt > WAITQUEUE_WALK_BREAK_CNT) &&
                (&next->entry != &wq_head->head)) {
            bookmark->flags = WQ_FLAG_BOOKMARK;
            list_add_tail(&bookmark->entry, &next->entry);
            break;
        }
    }
    return nr_exclusive;
}                        

2、工作队列

    工作队列（work queue）是一种将工作推后执行的形式，它和tasklet有所不同。工作队列可以把工作推后，交由一个内核线程去执行，也就是说，这个下半部分可以在进程上下文中执行。这样，通过工作队列执行的代码能占尽进程上下文的所有优势。最重要的就是工作队列允许被重新调度甚至是睡眠。它的数据结构如下

typedef void (*work_func_t)(struct work_struct *work);

struct work_struct {
    atomic_long_t data;
    struct list_head entry;
    work_func_t func;
#ifdef CONFIG_LOCKDEP
    struct lockdep_map lockdep_map;
#endif
};

参考Linux内核实践之工作队列

3) 操作函数 1. 初始化工作队列

函数接口	接口含义
INIT_WORK(work,func)	初始化工作队列项 work，并设置回调函数func
DECLARE_WORK(name,func)	声明一个等待队列项 name，并设置回调函数func

2. 调度工作队列

函数接口	接口含义
schedule_work(&work)	调度工作队列
schedule_delayed_work(&work,tick)	延时tick个滴答应答之后调度工作队列

四、linux内核通知链 1、基本概念

    内核中不同模块间的消息通知机制，告诉其他模块，当前发生了什么事情。内核通知链只能用于内核之间，不能用于内核于用户空间之间的通信。实现原理很简单，就是通知的模块提供一个链表，被通知的模块将回调函数注册进入通知模块提供的链表中。当发生事件时通知模块遍历链表中的所有回调函数，并根据传入的参数依次调用。以原子通知链为例进行说名，原子通知链提供的链表头如下所示。

struct atomic_notifier_head {
    spinlock_t lock; //原子通知链的锁
    struct notifier_block __rcu *head; //用于挂接该链表上的 notifier_block 结构
};

无论是什么通知链，都是使用 notifier_block 作为该通知链的成员。

typedef int (*notifier_fn_t)(struct notifier_block *nb,
            unsigned long action, void *data);

struct notifier_block {
    notifier_fn_t notifier_call;
    struct notifier_block __rcu *next; //指向所属的链表头
    int priority; //优先级，越大优先级越高，且将位于队列的更前面，更先被调用
};

    实现过程很简单，就两步，第一步注册被通知模块的成员 notifier_block 到发出通知模块提供的链表头 atomic_notifier_head 上，第二步当发出通知模块要通知时，调用该链表头上的成员的回调函数即可。注册过程很简单如下所示

int atomic_notifier_chain_register(struct atomic_notifier_head *nh,
        struct notifier_block *n)
{
    unsigned long flags;
    int ret;

    spin_lock_irqsave(&nh->lock, flags);
    ret = notifier_chain_register(&nh->head, n); //将 n 注册到 nh->head 链表
    spin_unlock_irqrestore(&nh->lock, flags);
    return ret;
}
EXPORT_SYMBOL_GPL(atomic_notifier_chain_register);

static int notifier_chain_register(struct notifier_block **nl,
        struct notifier_block *n)
{
    while ((*nl) != NULL) { //遍历到 atomic_notifier_head 的尾部
        if (n->priority > (*nl)->priority)
            break;
        nl = &((*nl)->next); 
    }
    n->next = *nl; //指向对应的链表头 nl
    rcu_assign_pointer(*nl, n); //将 n 插入到链表头 nl 的尾部
    return 0;
}

再来看一下调用过程

int atomic_notifier_call_chain(struct atomic_notifier_head *nh,
                   unsigned long val, void *v)
{
    return __atomic_notifier_call_chain(nh, val, v, -1, NULL);
}
EXPORT_SYMBOL_GPL(atomic_notifier_call_chain);
NOKPROBE_SYMBOL(atomic_notifier_call_chain);

int __atomic_notifier_call_chain(struct atomic_notifier_head *nh,
                 unsigned long val, void *v,
                 int nr_to_call, int *nr_calls)
{
    int ret;

    rcu_read_lock();
    //调用 notifier_call_chain 回调 atomic_notifier_head 上成员的回调函数
    ret = notifier_call_chain(&nh->head, val, v, nr_to_call, nr_calls);
    rcu_read_unlock();
    return ret;
}
EXPORT_SYMBOL_GPL(__atomic_notifier_call_chain);
NOKPROBE_SYMBOL(__atomic_notifier_call_chain);

// nl = &nh->head
// val = val
// v = v
// nr_to_call = -1
// nr_calls = NULL
static int notifier_call_chain(struct notifier_block **nl,
                   unsigned long val, void *v,
                   int nr_to_call, int *nr_calls)
{
    int ret = NOTIFY_DONE;
    struct notifier_block *nb, *next_nb;

    nb = rcu_dereference_raw(*nl); //获取链表指针

    while (nb && nr_to_call) { //循环遍历 nb 链表上的 notifier_block ，nr_to_call 表示调用的次数。
        next_nb = rcu_dereference_raw(nb->next); //获取下一个 notifier_block

#ifdef CONFIG_DEBUG_NOTIFIERS 
        if (unlikely(!func_ptr_is_kernel_text(nb->notifier_call))) { //debug检测是否有 notifier_call 回调函数，如果没有则直接调用下一个。
            WARN(1, "Invalid notifier called!");
            nb = next_nb;
            continue;
        }
#endif
        ret = nb->notifier_call(nb, val, v); //调用回调函数 notifier_call

        if (nr_calls)
            (*nr_calls)++; //用于记调用了几个回调函数

        if (ret & NOTIFY_STOP_MASK)
            break;
        nb = next_nb;
        nr_to_call--;
    }
    return ret;
}
NOKPROBE_SYMBOL(notifier_call_chain);

2、接口整理 1、原子通知链

    可以看出原子通知链使用的是自旋锁，因此原子通知链可以用在中断上下文中，不能阻塞。

struct atomic_notifier_head {
    spinlock_t lock; //原子通知链的锁
    struct notifier_block __rcu *head; //用于挂接该链表上的 notifier_block 结构
};

    创建原子通知连

#define ATOMIC_NOTIFIER_HEAD(name)              
    struct atomic_notifier_head name =          
        ATOMIC_NOTIFIER_INIT(name)

#define ATOMIC_NOTIFIER_INIT(name) {                
        .lock = __SPIN_LOCK_UNLOCKED(name.lock),    
        .head = NULL }

    调用原子通知链

// nh 要调用的通知链头
// val = 传入回调函数的 actorn
// v = 传入回调函数的私有数据
int atomic_notifier_call_chain(struct atomic_notifier_head *nh,
        unsigned long val, void *v);

// nh 要调用的通知链头
// val = 传入回调函数的 action
// v = 传入回调函数的私有数据
// nr_to_call = 遍历多少个 atomic_notifier_head 中的成员
// nr_calls = 用于记录遍历了几个成员
int __atomic_notifier_call_chain(struct atomic_notifier_head *nh,
    unsigned long val, void *v, int nr_to_call, int *nr_calls);

    注册原子通知链

extern int atomic_notifier_chain_register(struct atomic_notifier_head *nh,
        struct notifier_block *nb)

2、阻塞通知链

    阻塞通知连使用的读写信号量，因此阻塞通知链使用在进程上下文，可以阻塞。

struct blocking_notifier_head {
    struct rw_semaphore rwsem;
    struct notifier_block __rcu *head;
};

    创建阻塞通知链

#define BLOCKING_NOTIFIER_HEAD(name)                
    struct blocking_notifier_head name =            
        BLOCKING_NOTIFIER_INIT(name)

#define BLOCKING_NOTIFIER_INIT(name) {              
        .rwsem = __RWSEM_INITIALIZER((name).rwsem), 
        .head = NULL }

    调用阻塞通知链

// nh 要调用的通知链头
// val = 传入回调函数的 actorn
// v = 传入回调函数的私有数据
int blocking_notifier_call_chain(struct blocking_notifier_head *nh, unsigned long val, void *v);

// nh 要调用的通知链头
// val = 传入回调函数的 action
// v = 传入回调函数的私有数据
// nr_to_call = 遍历多少个 atomic_notifier_head 中的成员
// nr_calls = 用于记录遍历了几个成员
int __blocking_notifier_call_chain(struct blocking_notifier_head *nh,
    unsigned long val, void *v, int nr_to_call, int *nr_calls);

    注册阻塞通知链

extern int blocking_notifier_chain_register(struct blocking_notifier_head *nh,struct notifier_block *nb);

3、原始通知链

    非常原始，啥锁都没有

struct  raw_notifier_head {  
    struct  notifier_block   *head;  
};

    创建原始通知链

#define RAW_NOTIFIER_HEAD(name)                 
    struct raw_notifier_head name =             
        RAW_NOTIFIER_INIT(name)

#define RAW_NOTIFIER_INIT(name) {               
        .head = NULL }

    调用原始通知链

// nh 要调用的通知链头
// val = 传入回调函数的 actorn
// v = 传入回调函数的私有数据
int raw_notifier_call_chain(struct raw_notifier_head *nh,
        unsigned long val, void *v);

// nh 要调用的通知链头
// val = 传入回调函数的 action
// v = 传入回调函数的私有数据
// nr_to_call = 遍历多少个 atomic_notifier_head 中的成员
// nr_calls = 用于记录遍历了几个成员
int __raw_notifier_call_chain(struct raw_notifier_head *nh,
    unsigned long val, void *v, int nr_to_call, int *nr_calls);

    注册原始通链

int raw_notifier_chain_register(struct raw_notifier_head *nh, struct notifier_block *nb);

4、SRCU 通知链

    可以阻塞的通知链。

struct  srcu_notifier_head {  
    struct  mutex mutex;  
    struct  srcu_struct  srcu;  
    struct  notifier_block  *head;  
};