注意：这篇文章上次更新于689天前，文章内容可能已经过时。
This article was last updated689 days ago, the content may be outdated.
Scheduler 翻译成中文叫做调度器。
调度器这个词对于学计算机的同学来说应该并不陌生，因为在大学操作系统的课堂上我们学过很多关于进程调度的知识。
- 先来先服务（FCFS）
- 短作业优先（SJF）
- 优先级调度
- 时间片轮转
- 多级反馈队列
等等。
在这篇文章中，我们将会讨论高通 WLAN Host Driver 中调度器的实现。
为什么先学习调度器呢?
因为调度器是 WLAN Host Driver 中相对简单的部分，仅有 4 个源代码文件，而且调度器是 WLAN Host Driver 的核心部分，是各个模块之间沟通的桥梁。
源代码我转存到了我的 GitHub 仓库中，今天要看的部分在这里：
也可以使用我的 opengrok 服务器来查看源代码，如果它还在线的话。
https://opengrok.dijk.eu.org/xref/wlan-driver/qca-wifi-host-cmn/scheduler/
Scheduler translates to 调度器 (dispatcher) in Chinese.
The word scheduler should be familiar to anyone in computer science — in university OS classes we learned a lot about process scheduling.
- First Come First Served (FCFS)
- Shortest Job First (SJF)
- Priority scheduling
- Round-robin
- Multi-level feedback queue
and so on.
In this article, we’ll discuss the scheduler implementation in Qualcomm’s WLAN Host Driver.
Why study the scheduler first?
Because the scheduler is one of the simpler parts of the WLAN Host Driver — only 4 source files — and it’s also the core of the driver, acting as the bridge between all modules.
I’ve mirrored the source code to my GitHub repo; the part we’re looking at today is here:
You can also browse the source on my opengrok server, if it’s still online.
https://opengrok.dijk.eu.org/xref/wlan-driver/qca-wifi-host-cmn/scheduler/
数据部分
scheduler 上下文
代码位置：
⭐
根据类型，消息体指针可以是指向内存的 bodyptr 指针，也可以是作为 32 位数据的 bodyval。bodyptr 总是可以被释放的指针，应始终确保 bodyptr 是可以被释放的。消息应该使用 bodyptr 或 bodyval，但不应同时使用两者！
👀
关于链表节点，我曾经在这篇文章中讨论过。
sched_history_item
代码位置：
这个数据结构同于记录调度器的历史记录。
在 Scheduler 模块中，有一个全局变量 sched_history，它是一个数组，用于记录最近的 WLAN_SCHED_HISTORY_SIZE 条历史记录。
1 | static struct sched_history_item sched_history[WLAN_SCHED_HISTORY_SIZE]; |
提醒一下，这些代码是否生效取决于 WLAN_SCHED_HISTORY_SIZE 是否被定义。如果没有定义 WLAN_SCHED_HISTORY_SIZE，那么和调度器历史有关的代码都不会参与编译。
sched_pool 🌶️
又到了内核代码极其抽象的宏定义时间了 🤣
这部分由 ChatGPT 给我们协助讲解。
其实内存池应该在一个单独的文章中讲解。
如果你学习过 malloc 的原理的话，其实可以把这里的
sched_pool理解为用于分配scheduler_msg的数据结构。
代码位置：
定义一个内存池，用下面这个宏函数。
1 | DEFINE_QDF_FLEX_MEM_POOL(sched_pool, sizeof(struct scheduler_msg), |
这个宏函数被写成了下面的样子。
1 | /** |
这些代码被写在 qdf 模块里，已经超出了本文所介绍的范围，关于 QDF_FM_BITMAP_BITS, QDF_LIST_NODE_INIT_SINGLE, QDF_LIST_ANCHOR, QDF_LIST_INIT_SINGLE 等宏定义就不再继续展开了。
我们可以简单理解一下这个宏定义做了什么事。
对话 GPT-4o
Q1:
这个宏函数做了什么？
A1:
这个宏 DEFINE_QDF_FLEX_MEM_POOL 用于在C程序中定义并初始化一个带有一个段（segment）的灵活内存池。我们来详细解释一下这个宏的功能，然后应用到给定的例子中。
宏的详细解析
-
定义一个内存池结构体变量:
1
struct qdf_flex_mem_pool name;
这行代码定义了一个类型为
struct qdf_flex_mem_pool的新变量name，用于表示内存池。 -
为段头部分配字节:
1
uint8_t __ #
这行代码定义了一个名为
__name_head_bytes的字节数组，大小为QDF_FM_BITMAP_BITS * (size_of_item)。这个数组用于存储内存池的第一个段的数据。其中，QDF_FM_BITMAP_BITS可能是一个常量，表示位图的位数，而size_of_item是每个池分配项的大小。 -
定义初始段:
1
2
3
4
5struct qdf_flex_mem_segment __ ## name ## _head = { \
.node = QDF_LIST_NODE_INIT_SINGLE( \
QDF_LIST_ANCHOR(name.seg_list)), \
.bytes = __ #这段代码定义了一个名为
__name_head的段结构体：node: 使用QDF_LIST_NODE_INIT_SINGLE和QDF_LIST_ANCHOR初始化为连接到内存池段列表的单节点。bytes: 指向前面定义的__name_head_bytes数组，这是这个段实际的内存区域。
-
初始化内存池:
1
2
3
4
5struct qdf_flex_mem_pool name = { \
.seg_list = QDF_LIST_INIT_SINGLE(__ #这行代码初始化名为
name的内存池结构体：seg_list: 初始化为一个只包含一个段（__name_head.node）的列表。reduction_limit: 设置为rm_limit，表示在减少内存池时保留的最小段数。item_size: 设置为size_of_item，表示内存池管理的每个项的大小。
应用该宏
给定的用法：
1 | DEFINE_QDF_FLEX_MEM_POOL(sched_pool, sizeof(struct scheduler_msg), WLAN_SCHED_REDUCTION_LIMIT); |
name = sched_pool: 这会创建一个名为sched_pool的struct qdf_flex_mem_pool类型的变量。size_of_item = sizeof(struct scheduler_msg): 该池中每个项的大小为struct scheduler_msg的大小。rm_limit = WLAN_SCHED_REDUCTION_LIMIT: 在减少内存池时保留的最小段数由WLAN_SCHED_REDUCTION_LIMIT定义。
宏的功能总结
宏 DEFINE_QDF_FLEX_MEM_POOL:
- 定义一个带有指定名称的新的灵活内存池。
- 根据它将管理的项的大小为第一个段分配预定义数量的内存。
- 初始化内存池，设置链表和其他属性，比如项的大小和减少时保留的最小段数。
这个宏简化了灵活内存池的创建和初始化，使得能够更容易地使用设置好的结构和参数动态管理内存。
Q2:
如果理解“带有一个段（segment）”
A2:
“带有一个段（segment）” 指的是在创建内存池时，内存池初始化时包含一个内存段。每个段是内存池中的一个独立块，用于存储特定数量的内存项。
在这个宏的上下文中，一个“段”就是一个内存块，其中包含了若干个固定大小的内存项。段的用途在于管理内存的分配和释放，通常在需要动态分配和回收大量小内存块的情况下使用。通过使用段，可以减少内存碎片，优化内存使用，同时也便于内存管理操作（如扩展、缩减内存池）。
具体来说，“带有一个段”在这里的含义可以理解为：
-
初始内存分配: 宏定义的内存池在创建时，会先分配一段固定大小的内存，这段内存称为“段”。在代码中，使用一个字节数组
__name_head_bytes来实际存储这些内存数据。 -
段的结构: 每个段都有一个管理节点（
node），用于在池的段列表中进行链表管理；并且有一个指向实际数据的指针（bytes），即__name_head_bytes。 -
段的数量: 虽然这里初始化时只有一个段，但整个设计是支持多个段的（如通过链表结构管理多个段）。段的数量可以根据需要增加或减少，
reduction_limit参数指定了在减少段时，池中最少需要保留的段数量。
总结来说，“带有一个段”意味着这个内存池一开始就包含了一个已经分配好的内存块，这个块被组织成段，用于存储和管理内存项。随着需求变化，可以动态调整段的数量来管理内存使用。
Q3:
当需要更多内存时，这个内存池会做哪些事情
A3:
当需要更多内存时，这个内存池可能会执行以下操作来分配更多的内存段。这些操作的具体实现取决于内存池的设计和用途。一般来说，灵活的内存池在内存需求增加时会按需扩展，并进行以下步骤：
-
分配新的内存段：
- 如果现有的段已满或无法满足新的内存请求，内存池会分配一个新的内存段（segment）。
- 这涉及为新段分配一个大小为
QDF_FM_BITMAP_BITS * size_of_item的字节数组。QDF_FM_BITMAP_BITS和size_of_item共同决定了每个段中可以存储多少项。 - 新的段通常会使用类似于初始化第一个段的过程，即创建一个新字节数组来保存数据，并将其链接到段链表中。
-
将新段加入段链表：
- 新分配的段通过链表加入到内存池的段列表中。这些段是通过链表结构（如双向链表或单向链表）管理的，以便快速插入和删除。
- 在宏中，有
QDF_LIST_INIT_SINGLE和QDF_LIST_NODE_INIT_SINGLE这样的宏，可能用于初始化和操作链表节点，这些节点帮助管理不同段之间的关系。
-
更新内存池的管理结构：
- 内存池的元数据需要更新，例如：
- 段列表的头部指针或尾部指针。
- 内存池中当前段的数量。
- 可能还有内存池的总大小或已使用的内存总量。
- 内存池的元数据需要更新，例如：
-
扩展段的管理：
- 如果内存池有内存回收机制，当内存段不再需要时（例如，当内存项被释放后），池会检查是否可以回收某些段，以节省内存资源。
- 宏中提到的
reduction_limit是用于减少内存段时的最小段数限制，在增加段时也会考虑到这个限制，以确保内存管理的稳定性和性能。
-
重分配失败时的错误处理：
- 如果内存池在尝试分配新段时失败（例如，没有足够的系统内存），内存池需要有一定的错误处理机制，如记录错误、触发报警、或执行垃圾回收来释放未使用的内存。
-
可能的内存对齐和优化：
- 在某些情况下，内存池可能会进行内存对齐操作，以确保内存访问的效率。
- 对齐和优化可以避免内存碎片，并确保高效的内存使用。
代码示例
虽然你提供的宏并没有完整展示内存池的动态扩展机制，但假设这部分逻辑在内存池实现的其他部分中可以是这样的：
1 | void expand_memory_pool(struct qdf_flex_mem_pool *pool) { |
总结
当需要更多内存时，这个内存池会通过分配新的内存段、将新段加入管理链表、更新元数据，以及可能的错误处理来满足需求。这种机制使得内存池能够灵活地适应内存需求的变化，同时有效管理内存的分配和回收。
Q4:
现在让我来解释一下内存池，你来给我指正：
这个内存池就是预先申请了一大块内存，然后把这个内存组织成若干小块。每个小块包含两部分，一部分是实际使用的内存项，另一部分相当于一个头部，利用头部的指针信息把这些小块串联成一个链表。这个内存池可以对外部提供 get 内存项 和 free 内存项的 api，就像 malloc 和 free 一样。当一个内存项被 free 给内存池时，内存池不一定把这个内存交给操作系统，而是通过调整"头部"的指针信息来合并一些小的内存块，避免内存碎片。
A4:
你的解释总体来说是正确的，清晰地描述了内存池的基本工作原理。内存池的确通过预先申请一大块内存，将其分割成小块来高效管理内存分配和释放。下面是一些具体的指正和补充，帮助更好地理解内存池的运作：
-
头部与数据部分的关系：
- 你提到每个小块包含两部分：实际使用的内存项和一个头部。这是准确的。头部通常包含管理信息，例如指向下一个块的指针、块的状态（空闲或已用），以及其他管理所需的元数据。
- 这种设计可以让内存池在不需要额外的内存分配和释放的情况下管理内存块，减少内存碎片的产生。
-
链表的使用：
- 你提到利用头部的指针信息把这些小块串联成一个链表。这也是正确的。链表结构在内存池中很常见，因为它允许高效地插入和删除块，适合动态内存分配的场景。
- 通常，空闲块会被组织成一个空闲链表。每次分配时，内存池从空闲链表中取出一个合适大小的块；每次释放时，将块插回空闲链表。
-
get 和 free API 的实现：
- 内存池的 get 和 free 操作类似于
malloc和free，但通常会更高效，因为它们不涉及系统调用。get可能从空闲链表中找到一个适当大小的块并返回给调用者。free则把块返回到空闲链表中。 - 内存池的好处是减少了频繁的系统级内存分配操作，系统调用通常较慢且可能引入碎片。而内存池管理的内存通常在堆上，是应用级的。
- 内存池的 get 和 free 操作类似于
-
内存碎片管理：
- 你提到内存池在释放时可能不会将内存返还给操作系统，而是通过调整头部指针来合并小的内存块。这种做法可以减少内存碎片，提高内存使用效率。
- 具体来说，内存池可能实现某种内存合并策略，如相邻空闲块的合并（coalescing），以此来减少内存碎片，使得内存池中有足够大的连续空间来满足未来的内存分配请求。
-
可能的扩展：
- 当内存池中没有足够的空闲块时，内存池可能会扩展，即再申请一块内存并将其加入内存池的管理结构中。这可以通过追加新的段来实现，如前面描述的那样。
总结
你对内存池的描述基本上是正确的，并且涵盖了主要概念。内存池通过预先申请一大块内存，并将其组织成多个小块来管理内存。这种方法避免了频繁的系统调用，从而提高了性能，并通过合并和管理内存块的策略来减少碎片。内存池的实现涉及对内存块的分配、释放、以及碎片管理策略的设计。总体来说，你对内存池的理解是准确的，描述也是很清楚的！
逻辑部分
初始化
Scheduler 模块的初始化函数是 scheduler_init, 它在 hdd_module_init 中被调用。
整个函数的调用链如下：
module_init(hdd_module_init);
–>
hdd_module_init
–>
hdd_driver_load
–>
hdd_component_init
–>
dispatcher_init
–>
/*
- scheduler INIT has to be the last as each component’s
- initialization has to happen first and then at the end
- scheduler needs to start accepting the service.
*/
if (QDF_STATUS_SUCCESS !=scheduler_init())
goto scheduler_init_fail;
然后进入我们的主题：scheduler_init。
1 | QDF_STATUS scheduler_init(void) |
scheduler_all_queues_init：
1 | static qdf_atomic_t __sched_queue_depth; |
Enable
开启调度器的入口是 Kernel 来调用驱动程序的 probe 函数，在这里是 wlan_hdd_pld_probe。
1 | struct pld_driver_ops wlan_drv_ops = { |
整个函数的调用链如下：
wlan_hdd_pld_probe
–>
hdd_soc_probe
–>
__hdd_soc_probe
–>
hdd_wlan_startup
–>
hdd_wlan_start_modules
–>
cds_open
–>
dispatcher_enable
–>
scheduler_enable
到这里就进入了本节主题：scheduler_enable。
这里也是调度器多线程开始的地方。
1 | QDF_STATUS scheduler_enable(void) |
那么 sch_start_event 什么时候会变成非 0 呢？应该在 scheduler_thread 函数里面进行设置。
我先大概画了一下这两个线程的状态迁移过程，如下图。
然后我们再继续看代码。
1 | int scheduler_thread(void *arg) |
scheduler_thread_process_queues 用于处理 6 个队列中的消息，这 6 个队列按优先级排序，首先处理第一个队列的所有消息，如果第一个队列的所有消息处理完毕，然后检查第二个队列，以此类推，直到所有队列的消息都处理完毕，或者收到 shutdown 信号。
这里再解释一下上面为什么要先清除 MC_POST_EVENT_MASK 位，再处理消息。
我们首先要知道 MC_POST_EVENT_MASK 位是在哪里设置的，这个位是在 scheduler_post_message 函数中设置的，这个函数是用来向调度器线程发送消息的，当发送消息时，会设置 MC_POST_EVENT_MASK 位，这个位是用来通知调度器线程有新的消息需要处理。
考虑下面这一种情况。
- 调度器处理完成了第一个队列的所有消息，然后开始检查第二个队列。
- 此时有一个新消息被 post 到第一个消息队列，然后设置了
MC_POST_EVENT_MASK位。 - 调度器依次检查了所有队列，处理完成了所有消息，然后执行了
qdf_atomic_clear_bit(MC_POST_EVENT_MASK, &sch_ctx->sch_event_flag);，这就导致了再调度器线程进行循环检查消息队列时，会发现暂时没有MC_POST_EVENT_MASK被设置，就会持续等待。但请注意，此时第一个队列中有一个新消息，这个消息并没有被处理。它会等到下一次 post 消息到来时，才会被处理。这就导致了延迟。
1 | static void scheduler_thread_process_queues(struct scheduler_ctx *sch_ctx, |
如果 sch_ctx->timeout 时间内 handler 没有处理完成，那么就会调用 scheduler_watchdog_timeout
1 | static void scheduler_watchdog_timeout(void *arg) |
handler 注册
上一节中提到了每个消息队列有自己的handler，这个 handler 是在哪里注册的呢？
在上一节中的 cds_open 函数中，调用了 cds_register_all_modules 函数，这个函数会调用scheduler_register_module来为每个队列注册 handler。
cds_open
–>
dispatcher_enable
cds_register_all_modules
–>
scheduler_register_module
1 | static QDF_STATUS cds_register_all_modules(void) |
每个 handler 都会调用 msg 中设置的 callback 函数，但针对不同队列的消息，可能会有属于这个队列的特殊处理，所以要为每个队列注册一个 handler。
本文写到这里我已经发现我写的很烂。想要用文字讲解代码还是很困难。有时我又比较拘泥于细节，但仍然还有很多细节没有讲到。我觉的我继续讲下去只会更加混乱，所以本文暂时讲到这里。
希望对你有所帮助!
外部 API
2024-09-22 更新
最后再补充一下外部模块如何和调度器模块交互的。
最频繁被调用的外部 API 就是 scheduler_post_message，这个函数用来向调度器线程发送消息。
它是一个宏定义，参数分别是 源模块 ID，目标模块 ID，队列 ID，消息指针。
它被定义为 scheduler_post_message_debug，这个函数会在原始参数的基础上加上行号和函数名两个参数，这样在调试的时候可以知道是哪个函数调用了 scheduler_post_message。
1 | /** |
scheduler_post_message_debug 会继续调用 scheduler_post_msg，这个函数会将消息放入到消息队列中。
只不过这里做了一个简单的加工，将消息的源模块 ID，目标模块 ID，队列 ID 转换为 qid。
1 | QDF_STATUS scheduler_post_message_debug(QDF_MODULE_ID src_id, |
scheduler_get_qid 极其相关的宏定义如下。
0x3FF 的二进制表示就是 10 个 1，也就是说，scheduler_get_src_id 取的是 qid 的高 10 位，scheduler_get_dest_id 取的是 qid 的中间 10 位，scheduler_get_que_id 取的是 qid 的低 10 位。
scheduler_get_qid 则是一种逆运算，将 src_id，dest_id，que_id 通过移位的方式放在 qid 的不同位置。
这样做可以理解为一种压缩内存的方式，将三个取值范围小于 1024 的数值压缩到一个 32 位的整数中。
1 |
继续向下追踪，
scheduler_post_msg 会调用 scheduler_post_msg_by_priority 函数，这个函数会根据消息的优先级，将消息放入消息队列的不同位置中。
1 | static inline QDF_STATUS scheduler_post_msg(uint32_t qid, |
scheduler_post_msg_by_priority 才是最通用的函数，它的第三个参数是一个布尔值，用来决定是否按照优先级插入消息队列。
在常规模式下，如果外部模块调用的是 scheduler_post_message，那么这个参数就是 false。
这个函数的实现比较长，大家可以查看我的注释。
1 | QDF_STATUS scheduler_post_msg_by_priority(uint32_t qid, |
至此，关于 scheduler_post_message 的调用过程就介绍完了。
下面看一个例子，在 scan 模块中，如何向调度器模块发送消息。
wlan_scan_start 函数内部调用了 scheduler_post_message 函数，向调度器模块发送消息。
1 | QDF_STATUS wlan_scan_start(struct scan_start_request *req) |
根据上面的介绍，这个消息被放到了 QDF_MODULE_ID_OS_IF 的消息队列中，然后调度器线程会处理这个消息。
在调度器模块中，为 QDF_MODULE_ID_OS_IF 消息队列注册的 handler 是 scheduler_os_if_mq_handler，
也就是说调度器线程会调用 scheduler_os_if_mq_handler 函数来处理这个消息。
这个函数的内部实现是这样的。
本质就是调用消息的 callback 函数，然后参数是消息本身。
1 | QDF_STATUS scheduler_os_if_mq_handler(struct scheduler_msg *msg) |
对于上面的 scan 消息，当执行完 scheduler_post_message 后，调度器线程会被唤醒，然后调用 scheduler_os_if_mq_handler 函数，这个函数会调用 scm_scan_start_req 函数，然后将消息作为参数传递给 scm_scan_start_req 函数。
我们可以继续看一下 scm_scan_start_req 函数的实现。
1 | QDF_STATUS |
当我起初查看 WLAN 驱动的代码时，每次追踪函数调用时，看到
scheduler_post_message函数我总是很困惑。因为这里发生了线程切换，无法继续向下追踪。但好在 scheduler 模块的代码比较简单，只要理解了消息队列的概念，就能很好的理解这个模块的作用。
下次再看到
scheduler_post_message函数时，只需要知道接下来将切换到调度器线程中执行msg->callback函数，参数是msg本身就可以继续追踪了。
Data structures
Scheduler context
Code location:
⭐
根据类型，消息体指针可以是指向内存的 bodyptr 指针，也可以是作为 32 位数据的 bodyval。bodyptr 总是可以被释放的指针，应始终确保 bodyptr 是可以被释放的。消息应该使用 bodyptr 或 bodyval，但不应同时使用两者！
👀
关于链表节点，我曾经在这篇文章中讨论过。
sched_history_item
Code location:
This structure records the scheduler’s history.
In the Scheduler module, there’s a global variable sched_history — an array used to record the most recent WLAN_SCHED_HISTORY_SIZE history entries.
1 | static struct sched_history_item sched_history[WLAN_SCHED_HISTORY_SIZE]; |
A reminder: whether this code takes effect depends on whether WLAN_SCHED_HISTORY_SIZE is defined. If it isn’t, all scheduler-history-related code won’t be compiled.
sched_pool 🌶️
Here come the notoriously abstract kernel macro definitions again 🤣
ChatGPT will help us explain this part.
Actually, the memory pool deserves an article of its own.
If you’ve learned how malloc works, you can simply think of
sched_poolhere as the data structure used to allocatescheduler_msg.
Code location:
A memory pool is defined with this macro function.
1 | DEFINE_QDF_FLEX_MEM_POOL(sched_pool, sizeof(struct scheduler_msg), |
This macro is written as follows.
1 | /** |
This code lives in the qdf module, which is beyond the scope of this article, so I won’t expand on macros like QDF_FM_BITMAP_BITS, QDF_LIST_NODE_INIT_SINGLE, QDF_LIST_ANCHOR, QDF_LIST_INIT_SINGLE.
Let’s just understand at a high level what this macro does.
Conversation with GPT-4o
Q1:
What does this macro do?
A1:
The macro DEFINE_QDF_FLEX_MEM_POOL is used to define and initialize a flexible memory pool with one segment in C programs. Let’s explain the macro in detail and then apply it to the given example.
Detailed analysis of the macro
-
Define a memory pool struct variable:
1
struct qdf_flex_mem_pool name;
This line defines a new variable
nameof typestruct qdf_flex_mem_pool, representing the memory pool. -
Allocate bytes for the head segment:
1
uint8_t __ #
This defines a byte array named
__name_head_byteswith sizeQDF_FM_BITMAP_BITS * (size_of_item). This array stores the data of the pool’s first segment.QDF_FM_BITMAP_BITSis likely a constant representing the number of bits in the bitmap, andsize_of_itemis the size of each pooled item. -
Define the initial segment:
1
2
3
4
5struct qdf_flex_mem_segment __ ## name ## _head = { \
.node = QDF_LIST_NODE_INIT_SINGLE( \
QDF_LIST_ANCHOR(name.seg_list)), \
.bytes = __ #This defines a segment struct named
__name_head:node: initialized withQDF_LIST_NODE_INIT_SINGLEandQDF_LIST_ANCHORas a single node linked into the pool’s segment list.bytes: points to the__name_head_bytesarray defined above — the actual memory region of this segment.
-
Initialize the memory pool:
1
2
3
4
5struct qdf_flex_mem_pool name = { \
.seg_list = QDF_LIST_INIT_SINGLE(__ #This initializes the memory pool struct named
name:seg_list: initialized as a list containing a single segment (__name_head.node).reduction_limit: set torm_limit, the minimum number of segments to keep when reducing the pool.item_size: set tosize_of_item, the size of each item the pool manages.
Applying the macro
The given usage:
1 | DEFINE_QDF_FLEX_MEM_POOL(sched_pool, sizeof(struct scheduler_msg), WLAN_SCHED_REDUCTION_LIMIT); |
name = sched_pool: creates astruct qdf_flex_mem_poolvariable namedsched_pool.size_of_item = sizeof(struct scheduler_msg): each item in the pool is the size ofstruct scheduler_msg.rm_limit = WLAN_SCHED_REDUCTION_LIMIT: the minimum number of segments to keep during reduction.
Summary of the macro
The macro DEFINE_QDF_FLEX_MEM_POOL:
- Defines a new flexible memory pool with the given name.
- Allocates a predefined amount of memory for the first segment based on the size of the items it will manage.
- Initializes the pool, setting up the linked list and other attributes like item size and minimum segments to keep during reduction.
This macro simplifies the creation and initialization of a flexible memory pool, making it easier to dynamically manage memory with ready-made structures and parameters.
Q2:
What does “with one segment” mean?
A2:
“With one segment” means that when the memory pool is created, it is initialized with one memory segment. Each segment is an independent block in the pool, used to store a certain number of memory items.
In the context of this macro, a “segment” is a memory block containing several fixed-size memory items. Segments exist to manage allocation and deallocation, typically used when large numbers of small memory blocks need to be dynamically allocated and recycled. By using segments, memory fragmentation is reduced, memory usage is optimized, and memory management operations (like expanding or shrinking the pool) become easier.
Specifically, “with one segment” can be understood as:
-
Initial memory allocation: when created, the macro’s pool allocates one fixed-size memory block called a “segment”. In the code, a byte array
__name_head_bytesstores this data. -
Segment structure: each segment has a management node (
node) for linked-list management within the pool’s segment list, and a pointer to actual data (bytes), namely__name_head_bytes. -
Number of segments: although only one segment exists at initialization, the design supports multiple segments (managed via the linked-list structure). The number of segments can grow or shrink as needed; the
reduction_limitparameter specifies the minimum number of segments the pool must keep during reduction.
In short, “with one segment” means the pool starts with one pre-allocated memory block, organized as a segment, for storing and managing memory items. As requirements change, the pool can dynamically adjust the number of segments to manage memory usage.
Q3:
What does this pool do when more memory is needed?
A3:
When more memory is needed, this memory pool may do the following to allocate more segments. The exact implementation depends on the pool’s design and purpose. Generally, a flexible memory pool expands on demand when memory demand grows:
-
Allocate a new segment:
- If existing segments are full or can’t satisfy the new request, the pool allocates a new segment.
- This involves allocating a byte array of size
QDF_FM_BITMAP_BITS * size_of_item. Together,QDF_FM_BITMAP_BITSandsize_of_itemdetermine how many items each segment can store. - The new segment is typically created similarly to the first, i.e., a new byte array is created for the data and linked into the segment list.
-
Add the new segment to the segment list:
- The newly allocated segment is added to the pool’s segment list via the linked list. These segments are managed by a linked-list structure (doubly or singly linked) for fast insertion and removal.
- In the macro, macros like
QDF_LIST_INIT_SINGLEandQDF_LIST_NODE_INIT_SINGLElikely initialize and manipulate list nodes that help manage the relationships between segments.
-
Update the pool’s management structures:
- Pool metadata needs updating, e.g.:
- Head or tail pointers of the segment list.
- The current number of segments in the pool.
- Possibly the pool’s total size or total used memory.
- Pool metadata needs updating, e.g.:
-
Segment management for shrinking:
- If the pool has a reclamation mechanism, when segments are no longer needed (e.g., after items are freed), the pool may check whether to reclaim segments to save memory.
- The
reduction_limitin the macro limits the minimum number of segments during reduction; it’s also considered when growing, to keep memory management stable and performant.
-
Error handling on allocation failure:
- If the pool fails to allocate a new segment (e.g., insufficient system memory), the pool needs error handling, such as logging the error, raising an alarm, or running garbage collection to free unused memory.
-
Possible memory alignment and optimization:
- In some cases, the pool may align memory to ensure efficient access.
- Alignment and optimization avoid fragmentation and ensure efficient memory usage.
Code example
Although the macro doesn’t show the pool’s dynamic expansion logic in full, that logic might look like this elsewhere in the pool implementation:
1 | void expand_memory_pool(struct qdf_flex_mem_pool *pool) { |
Summary
When more memory is needed, the pool allocates new segments, adds them to the management list, updates metadata, and handles errors as needed. This mechanism lets the pool flexibly adapt to changing memory requirements while efficiently managing allocation and reclamation.
Q4:
Now let me explain the memory pool, and you correct me:
The pool pre-allocates a large chunk of memory and organizes it into many small blocks. Each small block has two parts: the actual memory item in use, and a header. The header’s pointer info links these small blocks into a linked list. The pool provides get and free APIs externally, like malloc and free. When an item is freed back to the pool, the pool doesn’t necessarily return that memory to the OS; instead it adjusts the header pointers to merge some small blocks, avoiding fragmentation.
A4:
Your explanation is generally correct and clearly describes the basic workings of a memory pool. A pool indeed pre-allocates a large chunk of memory and splits it into small blocks to manage allocation and deallocation efficiently. Some specific corrections and additions:
-
Header-data relationship:
- You mentioned each small block has two parts: the actual memory item and a header. That’s accurate. The header usually contains management info, such as a pointer to the next block, block state (free or in use), and other metadata.
- This design lets the pool manage memory blocks without extra allocations, reducing fragmentation.
-
Linked-list usage:
- Using header pointers to link small blocks into a list is also correct. Linked lists are common in pools because they allow efficient insertion/removal, ideal for dynamic allocation.
- Typically, free blocks form a free list. On each allocation, the pool takes a suitably sized block from the free list; on each free, the block goes back into the free list.
-
get and free API implementation:
- The pool’s get/free operations resemble
malloc/freebut are usually more efficient since they don’t involve system calls.getmay find a suitably sized block in the free list and return it;freereturns the block to the free list. - The benefit: fewer frequent system-level allocations, which are slow and can introduce fragmentation. Pool memory is usually app-level heap memory.
- The pool’s get/free operations resemble
-
Fragmentation management:
- You noted the pool may not return memory to the OS on free, instead merging small blocks by adjusting header pointers. This reduces fragmentation and improves efficiency.
- Specifically, the pool may implement a merging strategy, such as coalescing adjacent free blocks, to keep enough contiguous space for future requests.
-
Possible expansion:
- When the pool has no free blocks, it may expand — allocate another chunk and add it to the pool’s management structure, e.g., by appending a new segment as described above.
Summary
Your description is essentially correct and covers the main concepts. A pool pre-allocates a large chunk and organizes it into small blocks for management, avoiding frequent system calls for better performance, and reduces fragmentation via merging and management strategies. The implementation involves designing allocation, deallocation, and fragmentation strategies. Overall, your understanding is accurate and clearly described!
Logic
Initialization
The Scheduler module’s init function is scheduler_init, called in hdd_module_init.
The call chain:
module_init(hdd_module_init);
–>
hdd_module_init
–>
hdd_driver_load
–>
hdd_component_init
–>
dispatcher_init
–>
/*
- scheduler INIT has to be the last as each component’s
- initialization has to happen first and then at the end
- scheduler needs to start accepting the service.
*/
if (QDF_STATUS_SUCCESS !=scheduler_init())
goto scheduler_init_fail;
Then we get to our topic: scheduler_init.
1 | QDF_STATUS scheduler_init(void) |
scheduler_all_queues_init:
1 | static qdf_atomic_t __sched_queue_depth; |
Enable
The entry point to enabling the scheduler is the kernel calling the driver’s probe function, which is wlan_hdd_pld_probe here.
1 | struct pld_driver_ops wlan_drv_ops = { |
The call chain:
wlan_hdd_pld_probe
–>
hdd_soc_probe
–>
__hdd_soc_probe
–>
hdd_wlan_startup
–>
hdd_wlan_start_modules
–>
cds_open
–>
dispatcher_enable
–>
scheduler_enable
That brings us to this section’s topic: scheduler_enable.
This is also where the scheduler’s multithreading begins.
1 | QDF_STATUS scheduler_enable(void) |
So when does sch_start_event become non-zero? It should be set inside the scheduler_thread function.
I roughly drew the state transitions of these two threads below.
Then let’s continue with the code.
1 | int scheduler_thread(void *arg) |
scheduler_thread_process_queues processes messages in the 6 queues, which are ordered by priority: first process all messages in queue 1; when queue 1 is done, check queue 2, and so on, until all queues are drained or a shutdown signal is received.
Let me also explain why the MC_POST_EVENT_MASK bit is cleared before processing messages, as mentioned above.
- The scheduler finished processing all messages in the first queue, then started checking the second queue.
- At this moment, a new message is posted to the first queue, and the
MC_POST_EVENT_MASKbit is set. - The scheduler checked all queues in turn and processed all messages, then executed
qdf_atomic_clear_bit(MC_POST_EVENT_MASK, &sch_ctx->sch_event_flag);— as a result, when the scheduler thread loops back to check the message queues, it finds noMC_POST_EVENT_MASKset for now and keeps waiting. But note: at this point there’s a new message in the first queue that hasn’t been processed. It will only be processed when the next post arrives. This causes a delay.
1 | static void scheduler_thread_process_queues(struct scheduler_ctx *sch_ctx, |
If the handler doesn’t finish within sch_ctx->timeout, scheduler_watchdog_timeout is called.
1 | static void scheduler_watchdog_timeout(void *arg) |
Handler registration
In the previous section, each message queue has its own handler. Where is it registered?
In cds_open from the previous section, the cds_register_all_modules function is called, which in turn calls scheduler_register_module to register a handler for each queue.
cds_open
–>
dispatcher_enable
cds_register_all_modules
–>
scheduler_register_module
1 | static QDF_STATUS cds_register_all_modules(void) |
Each handler calls the callback set in the message, but messages on different queues may need queue-specific handling, so each queue gets its own registered handler.
By this point in the article, I’ve realized I’m writing poorly. Explaining code with text is really hard. Sometimes I get hung up on details, yet there are still plenty of details I haven’t covered. I think continuing would only make things more confusing, so this article ends here for now.
Hope it helps!
External APIs
2024-09-22 update
Finally, let me add how external modules interact with the scheduler module.
The most frequently called external API is scheduler_post_message, which sends a message to the scheduler thread.
It’s a macro whose parameters are: source module ID, destination module ID, queue ID, and message pointer.
It’s defined as scheduler_post_message_debug, which adds the line number and function name to the original parameters, so when debugging you can tell which function called scheduler_post_message.
1 | /** |
scheduler_post_message_debug continues by calling scheduler_post_msg, which puts the message into the message queue.
It just does a simple transformation: converting the message’s source module ID, destination module ID, and queue ID into a qid.
1 | QDF_STATUS scheduler_post_message_debug(QDF_MODULE_ID src_id, |
The macros related to scheduler_get_qid are as follows.
0x3FF in binary is 10 ones — that is, scheduler_get_src_id takes the top 10 bits of qid, scheduler_get_dest_id takes the middle 10 bits, and scheduler_get_que_id takes the low 10 bits.
scheduler_get_qid is the inverse operation, placing src_id, dest_id, and que_id into different bit positions of qid via shifts.
This is a way to compress memory: three values each less than 1024 are packed into a single 32-bit integer.
1 |
Tracing further down,
scheduler_post_msg calls scheduler_post_msg_by_priority, which places the message at different positions in the queue based on its priority.
1 | static inline QDF_STATUS scheduler_post_msg(uint32_t qid, |
scheduler_post_msg_by_priority is the most general function; its third parameter is a boolean deciding whether to insert into the queue by priority.
In normal mode, if an external module calls scheduler_post_message, this parameter is false.
This function is fairly long; check my comments.
1 | QDF_STATUS scheduler_post_msg_by_priority(uint32_t qid, |
That concludes the call path of scheduler_post_message.
Let’s look at an example: how the scan module sends a message to the scheduler module.
Inside wlan_scan_start, scheduler_post_message is called to send a message to the scheduler.
1 | QDF_STATUS wlan_scan_start(struct scan_start_request *req) |
Based on the above, this message goes into the QDF_MODULE_ID_OS_IF message queue, and then the scheduler thread processes it.
In the scheduler module, the handler registered for the QDF_MODULE_ID_OS_IF queue is scheduler_os_if_mq_handler,
meaning the scheduler thread calls scheduler_os_if_mq_handler to process this message.
The implementation is essentially: call the message’s callback with the message itself as the argument.
1 | QDF_STATUS scheduler_os_if_mq_handler(struct scheduler_msg *msg) |
For the scan message above, after scheduler_post_message completes, the scheduler thread wakes up and calls scheduler_os_if_mq_handler, which calls scm_scan_start_req, passing the message as the argument.
Let’s look at scm_scan_start_req.
1 | QDF_STATUS |
When I first looked at the WLAN driver code, every time I traced a function call and saw
scheduler_post_message, I was confused. A thread switch happens there, so I couldn’t keep tracing.Fortunately, the scheduler module’s code is simple — once you understand the message queue concept, you can understand this module well.
Next time you see
scheduler_post_message, just know that execution will switch to the scheduler thread, which runsmsg->callbackwithmsgas the argument — then you can keep tracing.
