linux 内核klist分析

朱雀 2022-04-04 15:39 268阅读 0赞

--------------------

记录一下内核的的klist实现，以防以后忘记。内核目录文件所在位置：\\include\\linux\\klist.c和\\include\\linux\\klist.h

本文仅仅是对源代码进行分析，分析的部分参看每段代码的注释部分。

关于klist详细的文字介绍，请参考其他文章：

[Linux内核中的klist分析][Linux_klist]

[linux内核源代码分析----内核基础设施之klist][linux_----_klist]

[Linux内核链表list\_head扩展---klist][Linux_list_head_---klist]

[linux内核部件分析（四）——更强的链表klist][linux_klist]

--------------------

![klist][]

--------------------

进入正文：klist.h代码如下

--------------------

/*
     *	klist.h - Some generic list helpers, extending struct list_head a bit.
     *
     *	Implementations are found in lib/klist.c
     *
     *
     *	Copyright (C) 2005 Patrick Mochel
     *
     *	This file is rleased under the GPL v2.
     */
    
    #ifndef _LINUX_KLIST_H
    #define _LINUX_KLIST_H
    
    #include <linux/spinlock.h>
    #include <linux/kref.h>
    #include <linux/list.h>
    
    struct klist_node;
    
    /* 注意这里的  __attribute__ ((aligned (sizeof(void *))))对齐属性，在以后会用的，
     * 假如是4字节对齐，因此 struct klist结构体的地址的最低两位永远都是00，不可能出现
     * 1,2,3，因此内核局可以利用该地址的最低两位，一般是由 struct klist_node节点指向
     * struct klist节点的地址，因此struct klist_node节点可以利用struct klist节点对齐做一些文章。
     *
     */
    struct klist {
    	spinlock_t		k_lock;
    	struct list_head	k_list;
    	void			(*get)(struct klist_node *);
    	void			(*put)(struct klist_node *);
    } __attribute__ ((aligned (sizeof(void *))));
    
    
    #define KLIST_INIT(_name, _get, _put)					\
    	{ .k_lock	= __SPIN_LOCK_UNLOCKED(_name.k_lock),		\
    	  .k_list	= LIST_HEAD_INIT(_name.k_list),			\
    	  .get		= _get,						\
    	  .put		= _put, }
    
    #define DEFINE_KLIST(_name, _get, _put)					\
    	struct klist _name = KLIST_INIT(_name, _get, _put)
    
    extern void klist_init(struct klist *k, void (*get)(struct klist_node *),
    		       void (*put)(struct klist_node *));
    
    struct klist_node {
    	void			*n_klist;	/* never access directly */
    	struct list_head	n_node;
    	struct kref		n_ref;
    };
    
    extern void klist_add_tail(struct klist_node *n, struct klist *k);
    extern void klist_add_head(struct klist_node *n, struct klist *k);
    extern void klist_add_behind(struct klist_node *n, struct klist_node *pos);
    extern void klist_add_before(struct klist_node *n, struct klist_node *pos);
    
    extern void klist_del(struct klist_node *n);
    extern void klist_remove(struct klist_node *n);
    
    extern int klist_node_attached(struct klist_node *n);
    
    /* 该结构体用于klist迭代使用，也就是为了遍历klist链表中的klist_node节点 */
    struct klist_iter {
    	struct klist		*i_klist;
    	struct klist_node	*i_cur;
    };
    
    
    extern void klist_iter_init(struct klist *k, struct klist_iter *i);
    extern void klist_iter_init_node(struct klist *k, struct klist_iter *i,
    				 struct klist_node *n);
    extern void klist_iter_exit(struct klist_iter *i);
    extern struct klist_node *klist_next(struct klist_iter *i);
    
    #endif

klist.c

--------------------

/*
     * klist.c - Routines for manipulating klists.
     *
     * Copyright (C) 2005 Patrick Mochel
     *
     * This file is released under the GPL v2.
     *
     * This klist interface provides a couple of structures that wrap around
     * struct list_head to provide explicit list "head" (struct klist) and list
     * "node" (struct klist_node) objects. For struct klist, a spinlock is
     * included that protects access to the actual list itself. struct
     * klist_node provides a pointer to the klist that owns it and a kref
     * reference count that indicates the number of current users of that node
     * in the list.
     *
     * The entire point is to provide an interface for iterating over a list
     * that is safe and allows for modification of the list during the
     * iteration (e.g. insertion and removal), including modification of the
     * current node on the list.
     *
     * It works using a 3rd object type - struct klist_iter - that is declared
     * and initialized before an iteration. klist_next() is used to acquire the
     * next element in the list. It returns NULL if there are no more items.
     * Internally, that routine takes the klist's lock, decrements the
     * reference count of the previous klist_node and increments the count of
     * the next klist_node. It then drops the lock and returns.
     *
     * There are primitives for adding and removing nodes to/from a klist.
     * When deleting, klist_del() will simply decrement the reference count.
     * Only when the count goes to 0 is the node removed from the list.
     * klist_remove() will try to delete the node from the list and block until
     * it is actually removed. This is useful for objects (like devices) that
     * have been removed from the system and must be freed (but must wait until
     * all accessors have finished).
     */
    
    #include <linux/klist.h>
    #include <linux/export.h>
    #include <linux/sched.h>
    
    /*
     * Use the lowest bit of n_klist to mark deleted nodes and exclude
     * dead ones from iteration.
     */
    #define KNODE_DEAD		1LU
    #define KNODE_KLIST_MASK	~KNODE_DEAD
    
    /* 从klist_node节点中得到链表头 */
    static struct klist *knode_klist(struct klist_node *knode)
    {
    	return (struct klist *)
    		((unsigned long)knode->n_klist & KNODE_KLIST_MASK);
    }
    
    static bool knode_dead(struct klist_node *knode)
    {
    	return (unsigned long)knode->n_klist & KNODE_DEAD;
    }
    
    static void knode_set_klist(struct klist_node *knode, struct klist *klist)
    {
    	knode->n_klist = klist;
    	/* no knode deserves to start its life dead */
    	WARN_ON(knode_dead(knode));
    }
    
    /* klist_node中的n_klist指针的最低位肯定是0，因为struct klist结构体是4字节对齐的
     * 因此巧妙的利用最低位来表示该节点是否被删除
     */
    static void knode_kill(struct klist_node *knode)
    {
    	/* and no knode should die twice ever either, see we're very humane */
    	WARN_ON(knode_dead(knode));
    	*(unsigned long *)&knode->n_klist |= KNODE_DEAD;
    }
    
    /**
     * klist_init - Initialize a klist structure.
     * @k: The klist we're initializing.
     * @get: The get function for the embedding object (NULL if none)
     * @put: The put function for the embedding object (NULL if none)
     *
     * Initialises the klist structure.  If the klist_node structures are
     * going to be embedded in refcounted objects (necessary for safe
     * deletion) then the get/put arguments are used to initialise
     * functions that take and release references on the embedding
     * objects.
     */
    void klist_init(struct klist *k, void (*get)(struct klist_node *),
    		void (*put)(struct klist_node *))
    {
    	INIT_LIST_HEAD(&k->k_list);
    	spin_lock_init(&k->k_lock);
    	k->get = get;
    	k->put = put;
    }
    EXPORT_SYMBOL_GPL(klist_init);
    
    static void add_head(struct klist *k, struct klist_node *n)
    {
    	spin_lock(&k->k_lock);
    	list_add(&n->n_node, &k->k_list);
    	spin_unlock(&k->k_lock);
    }
    
    static void add_tail(struct klist *k, struct klist_node *n)
    {
    	spin_lock(&k->k_lock);
    	list_add_tail(&n->n_node, &k->k_list);
    	spin_unlock(&k->k_lock);
    }
    
    static void klist_node_init(struct klist *k, struct klist_node *n)
    {
    	INIT_LIST_HEAD(&n->n_node);
    	kref_init(&n->n_ref);
    	knode_set_klist(n, k);
    	if (k->get)
    		k->get(n);
    }
    
    /**
     * klist_add_head - Initialize a klist_node and add it to front.
     * @n: node we're adding.
     * @k: klist it's going on.
     */
    void klist_add_head(struct klist_node *n, struct klist *k)
    {
    	klist_node_init(k, n);
    	add_head(k, n);
    }
    EXPORT_SYMBOL_GPL(klist_add_head);
    
    /**
     * klist_add_tail - Initialize a klist_node and add it to back.
     * @n: node we're adding.
     * @k: klist it's going on.
     */
    void klist_add_tail(struct klist_node *n, struct klist *k)
    {
    	klist_node_init(k, n);
    	add_tail(k, n);
    }
    EXPORT_SYMBOL_GPL(klist_add_tail);
    
    /**
     * klist_add_behind - Init a klist_node and add it after an existing node
     * @n: node we're adding.
     * @pos: node to put @n after
     */
    
    /* 该函数接口是在pos后面插入一个n节点，主要原理就是list_add是在链表头加入节点，
     * 因此list_add(&n->n_node, &pos->n_node);就是以pos为链表头，在pos后面添加一个节点。
     * 
     */
    void klist_add_behind(struct klist_node *n, struct klist_node *pos)
    {
    	struct klist *k = knode_klist(pos);
    
    	klist_node_init(k, n);
    	spin_lock(&k->k_lock);
    	list_add(&n->n_node, &pos->n_node);
    	spin_unlock(&k->k_lock);
    }
    EXPORT_SYMBOL_GPL(klist_add_behind);
    
    /**
     * klist_add_before - Init a klist_node and add it before an existing node
     * @n: node we're adding.
     * @pos: node to put @n after
     */
    
    /* 该函数接口是在pos前面插入一个n节点，主要原理就是list_add_tail是在链表尾部加入节点，
     * 因此list_add_tail(&n->n_node, &pos->n_node);就是以pos为链表头，在pos尾部添加一个节点。
     * 因为pos是一个双向循环链表，以pos为表头的尾部就是pos的前一个节点。
     * 
     */
    void klist_add_before(struct klist_node *n, struct klist_node *pos)
    {
    	struct klist *k = knode_klist(pos);
    
    	klist_node_init(k, n);
    	spin_lock(&k->k_lock);
    	list_add_tail(&n->n_node, &pos->n_node);
    	spin_unlock(&k->k_lock);
    }
    EXPORT_SYMBOL_GPL(klist_add_before);
    
    /* 该结构体用于线程阻塞 */
    struct klist_waiter {
    	struct list_head list;
    	struct klist_node *node;
    	struct task_struct *process;
    	int woken;
    };
    
    static DEFINE_SPINLOCK(klist_remove_lock);
    static LIST_HEAD(klist_remove_waiters);
    
    static void klist_release(struct kref *kref)
    {
    	struct klist_waiter *waiter, *tmp;
    	struct klist_node *n = container_of(kref, struct klist_node, n_ref);
    
    	WARN_ON(!knode_dead(n));
    	/* 从struct klist链表头中删除klist_node */
    	list_del(&n->n_node);
    	spin_lock(&klist_remove_lock);
    	/* 遍历klist_remove_waiters链表，删除所有阻塞在删除n 节点的waiter，然后唤醒进程 */
    	list_for_each_entry_safe(waiter, tmp, &klist_remove_waiters, list) {
    		if (waiter->node != n)
    			continue;
    
    		list_del(&waiter->list);
    		waiter->woken = 1;
    		mb();
    		wake_up_process(waiter->process);
    	}
    	spin_unlock(&klist_remove_lock);
    	knode_set_klist(n, NULL);
    }
    
    static int klist_dec_and_del(struct klist_node *n)
    {
    	return kref_put(&n->n_ref, klist_release);
    }
    
    static void klist_put(struct klist_node *n, bool kill)
    {
    	struct klist *k = knode_klist(n);
    	void (*put)(struct klist_node *) = k->put;
    
    	spin_lock(&k->k_lock);
    	if (kill)
    		knode_kill(n);
    	if (!klist_dec_and_del(n))
    		put = NULL;
    	spin_unlock(&k->k_lock);
    	if (put)
    		put(n);
    }
    
    /**
     * klist_del - Decrement the reference count of node and try to remove.
     * @n: node we're deleting.
     */
    void klist_del(struct klist_node *n)
    {
    	klist_put(n, true);
    }
    EXPORT_SYMBOL_GPL(klist_del);
    
    /**
     * klist_remove - Decrement the refcount of node and wait for it to go away.
     * @n: node we're removing.
     */
    void klist_remove(struct klist_node *n)
    {
    	struct klist_waiter waiter;
    	/* 将当前进程和要删除的klist_node放进klist_waiter结构体中
    	 * 值得注意的是如果多个线程要删除同一个klist_node节点的话，这里n的地址是一样的，
    	 * 这在以后唤醒进程时，将会用到，也就是说将会唤醒所有阻塞在删除n节点的进程。
    	 */
    	waiter.node = n;
    	waiter.process = current;
    	waiter.woken = 0;
    	spin_lock(&klist_remove_lock);
    	/* 将线程等待者放入klist_remove_waiters链表中 */
    	list_add(&waiter.list, &klist_remove_waiters);
    	spin_unlock(&klist_remove_lock);
    
    	klist_del(n);
    
    	for (;;) {
    		set_current_state(TASK_UNINTERRUPTIBLE);
    		if (waiter.woken)
    			break;
    		schedule();
    	}
    	__set_current_state(TASK_RUNNING);
    }
    EXPORT_SYMBOL_GPL(klist_remove);
    
    /**
     * klist_node_attached - Say whether a node is bound to a list or not.
     * @n: Node that we're testing.
     */
    int klist_node_attached(struct klist_node *n)
    {
    	return (n->n_klist != NULL);
    }
    EXPORT_SYMBOL_GPL(klist_node_attached);
    
    /**
     * klist_iter_init_node - Initialize a klist_iter structure.
     * @k: klist we're iterating.
     * @i: klist_iter we're filling.
     * @n: node to start with.
     *
     * Similar to klist_iter_init(), but starts the action off with @n,
     * instead of with the list head.
     */
    void klist_iter_init_node(struct klist *k, struct klist_iter *i,
    			  struct klist_node *n)
    {
    	i->i_klist = k;
    	i->i_cur = n;
    	if (n)
    		kref_get(&n->n_ref);
    }
    EXPORT_SYMBOL_GPL(klist_iter_init_node);
    
    /**
     * klist_iter_init - Iniitalize a klist_iter structure.
     * @k: klist we're iterating.
     * @i: klist_iter structure we're filling.
     *
     * Similar to klist_iter_init_node(), but start with the list head.
     */
    void klist_iter_init(struct klist *k, struct klist_iter *i)
    {
    	klist_iter_init_node(k, i, NULL);
    }
    EXPORT_SYMBOL_GPL(klist_iter_init);
    
    /**
     * klist_iter_exit - Finish a list iteration.
     * @i: Iterator structure.
     *
     * Must be called when done iterating over list, as it decrements the
     * refcount of the current node. Necessary in case iteration exited before
     * the end of the list was reached, and always good form.
     */
    void klist_iter_exit(struct klist_iter *i)
    {
    	if (i->i_cur) {
    		klist_put(i->i_cur, false);
    		i->i_cur = NULL;
    	}
    }
    EXPORT_SYMBOL_GPL(klist_iter_exit);
    
    static struct klist_node *to_klist_node(struct list_head *n)
    {
    	return container_of(n, struct klist_node, n_node);
    }
    
    /**
     * klist_next - Ante up next node in list.
     * @i: Iterator structure.
     *
     * First grab list lock. Decrement the reference count of the previous
     * node, if there was one. Grab the next node, increment its reference
     * count, drop the lock, and return that next node.
     */
    
    /* 迭代器的主要功能 */
    struct klist_node *klist_next(struct klist_iter *i)
    {
    	void (*put)(struct klist_node *) = i->i_klist->put;
    	/* 获得迭代器的当前节点 */
    	struct klist_node *last = i->i_cur;
    	struct klist_node *next;
    
    	spin_lock(&i->i_klist->k_lock);
    
    	if (last) {
    	/* 该分支表示以klist_iter中的klist_node节点为参考节点,取出参考节点中的下一个klist_node */
    		next = to_klist_node(last->n_node.next);
    		if (!klist_dec_and_del(last))
    			put = NULL;
    	} else
    		/* 该分支表示klist_iter中没有指定当前klist_node节点，则从 klist中第一个节点算为参考节点，
    		 * 取出参考节点中的下一个klist_node。
    		 */
    		next = to_klist_node(i->i_klist->k_list.next);
    
    	i->i_cur = NULL;
    	/* 将next节点与klist_iter中的头节点比较，如果链表中的某个klist_node已经被dead，那么不遍历该节点 */
    	while (next != to_klist_node(&i->i_klist->k_list)) {
    		if (likely(!knode_dead(next))) {
    			kref_get(&next->n_ref);
    			i->i_cur = next;
    			break;
    		}
    		/* 每次next与头节点进行比较，这样会比较所有从该next节点以后到头结点之间的节点 */
    		next = to_klist_node(next->n_node.next);
    	}
    
    	spin_unlock(&i->i_klist->k_lock);
    
    	if (put && last)
    		put(last);
    	return i->i_cur;
    }
    EXPORT_SYMBOL_GPL(klist_next);

[Linux_klist]: https://blog.csdn.net/z2007b/article/details/6417293
[linux_----_klist]: http://www.itboth.com/d/aEfmUv/linux
[Linux_list_head_---klist]: https://www.linuxidc.com/Linux/2011-05/36116.htm
[linux_klist]: https://blog.csdn.net/qb_2008/article/details/6845854
[klist]: /images/20220404/793a23f3e36f4dccaa19e079f5bb4e4d.png