Geeker
0%

Linux kernel list_for_each_entry()解析

发表于 更新于 分类于
本文先介绍Linux内核list_for_each_entry()基本用法、然后介绍list_for_each_entry一些细节解析，接下来通过实例证实分析，最后介绍内核应用实例。

1.环境介绍

  • Linux 内核代码版本：5.4.0-72
  • Gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04)
  • Clion 2017.3
  • Vim
  • GDB 8.0.1

2.list_for_each_entry()介绍

路径：include\linux\list.h

1
2
3
4
5
6
7
8
9
10
/**
 * list_for_each_entry	-	iterate over list of given type
 * @pos:	the type * to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the list_head within the struct.
 */
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_first_entry(head, typeof(*pos), member);	\
	     &pos->member != (head);					\
	     pos = list_next_entry(pos, member))

从其定义很明显能看出其作用就是：迭代给定类型的list。根据for循环特性分三部分解析：

  • 初始化

    1
    pos = list_first_entry(head, typeof(*pos), member);

    获取第一个链表里的第一个元素，注意这里的pos类型是指针类型

  • 循环条件判断

    1
    &pos->member != (head);

    因为list是双向链表，自然终止条件是头指针等于尾指针

  • for循环每次执行时

    1
    pos = list_next_entry(pos, member)

    顾名思义，每次循环时取list的pos位置的下一个元素(地址)

  • 第一部分初始化：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /**
     * list_entry - get the struct for this entry
     * @ptr:	the &struct list_head pointer.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_head within the struct.
     */
    #define list_entry(ptr, type, member) \
    	container_of(ptr, type, member)

    /**
     * list_first_entry - get the first element from a list
     * @ptr:	the list head to take the element from.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_head within the struct.
     *
     * Note, that list is expected to be not empty.
     */
    #define list_first_entry(ptr, type, member) \
    	list_entry((ptr)->next, type, member)

    可以看出list_first_entry作用就是从list里获取第一个元素，调用过程是list_first_entry->list_entry->container_of,所以我们只需要研究container_of实现即可。

    路径：include/linux/kernel.h

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /**
     * container_of - cast a member of a structure out to the containing structure
     * @ptr:	the pointer to the member.
     * @type:	the type of the container struct this is embedded in.
     * @member:	the name of the member within the struct.
     *
     */
    #define container_of(ptr, type, member) ({			\
    	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
    	(type *)( (char *)__mptr - offsetof(type,member) );})

    container_of的作用就是：获得结构体的地址。需要为其提供三个参数，分别是ptr: member的指针；type：结构体的类型；member：结构体成员member的名字。container_of能获得结构体地址的基本思想就是：结构体成员的地址减去该成员相对基址的偏移量就可以得到结构体的地址。container_of的实现里用了typeof、((type *)0)->member、offsetof，那接下来就针对这三个关键点展开分析。

    • typeof

      typeof可以视为视为一个关键字，需要注意的是typeof并不是C标准支持的，它是GCC拓展语法，作用就是可以动态获取变量的类型，实现C语言的”多态”，但这种多态性在预编译期间就已经被确定了，如下用法可以参考：

      1
      2
      #define pointer(T)  typeof(T *)
      #define array(T, N) typeof(T [N])

      T就是实际传入的类型，N为数组大小。那么声明一个指针数组就可以这样写：

      1
      array (pointer (T), N) y;

      即：y是一个容量为N数组，数组中每一个元素都是指向T的指针。

    • **((type )0)->member*

      ANSI C标准允许值为0的常量被强制转换成任何一种类型的指针，并且转换的结果是个NULL，因此((type *)0)的结果就是一个类型为type *的NULL指针。很显然不能对((type *)0)->member直接取其成员，否则肯定是空指针解引用错误。但如果只是获取member的类型，编译器是不会生成访问type->member成员的代码的，同理&((type *)0)->member也仅仅是获取member的地址，编译器亦会优化成直接取地址。这种技巧背后的思想是让编译器计算成员的地址，假设结构本身位于地址0。

    • offsetof

      路径：tools\include\linux

      1
      2
      3
      #ifndef offsetof
      #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
      #endif

      作用：获取结构体中某个成员相对于该结构体首元素地址的偏移量。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      #include <stdio.h>
      #include <stdlib.h>

      struct student {
          unsigned int age;
          unsigned int height;
          char *name;
      };

      #ifndef offsetof
      #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
      #endif

      /**
       * container_of - cast a member of a structure out to the containing structure
       * @ptr:	the pointer to the member.
       * @type:	the type of the container struct this is embedded in.
       * @member:	the name of the member within the struct.
       *
       */
      #define container_of(ptr, type, member) ({			\
      	const typeof(((type *)0)->member) * __mptr = (ptr);	\
      	(type *)((char *)__mptr - offsetof(type, member)); })


      int main() {
          struct student stu;
          struct student *pos = NULL;
          const typeof( (( struct student *)0)->height ) *__mptr = &stu.height;
          pos = (struct student *)((char *)__mptr - offsetof(struct student, height));

          printf("The offset height of student is: %u \n", offsetof(struct student, height));
          printf("container_of height is: %p \\n",((struct student *)0)->height);

          return 0;
      }

      image-20210627140024424

      综合以上关键点，从demo的运行结果可见我们的分析是正确的。

  • 第二部分for循环的逻辑判断和每次循环的处理同第一部分，因此不在赘述

3.list_for_each_entry的实际用途

查找驱动是否已经被注册：

__platform_driver_register -> driver_register -> driver_find(const char *name, struct bus_type *bus) -> kset_find_obj(struct kset *kset, const char *name)()-> list_for_each_entry(k, &kset->list, entry)

kset_find_obj()函数路径：\lib\kobject.c

1
2
3
4
5
6
struct kset {
	struct list_head list;
	spinlock_t list_lock;
	struct kobject kobj;
	const struct kset_uevent_ops *uevent_ops;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * kset_find_obj - search for object in kset.
 * @kset: kset we're looking in.
 * @name: object's name.
 *
 * Lock kset via @kset->subsys, and iterate over @kset->list,
 * looking for a matching kobject. If matching object is found
 * take a reference and return the object.
 */
struct kobject *kset_find_obj(struct kset *kset, const char *name)
{
	struct kobject *k;
	struct kobject *ret = NULL;

	spin_lock(&kset->list_lock);

	list_for_each_entry(k, &kset->list, entry) {
		if (kobject_name(k) && !strcmp(kobject_name(k), name)) {
			ret = kobject_get_unless_zero(k);
			break;
		}
	}

	spin_unlock(&kset->list_lock);
	return ret;
}
EXPORT_SYMBOL_GPL(kset_find_obj);

kset就是内核中属于特定子系统，是一系列的kobject的集合。kset_find_obj()函数的作用就是利用list_for_each_entry遍历kset循环链表，根据我们给的名字name在指定的bus中循环对比，查看是否有相同的名字name，如果相同则表示查找成功，也即表示该bus上已经有驱动注册过了。

4.总结

本文先描述了list_for_each_entry的基本用法、其实现里的一些关键点，并通过一个demo证实了分析，最后介绍了list_for_each_entry在内核里的部分应用。