irqbalance机制分析

本文档基于irqbalance-1.5.0

源码链接：/+source/irqbalance/

1. object tree

       Irqbalance是用户空间用于优化中断的一个工具，通过周期性的（默认10s）统计各个cpu上的中断情况，重新对中断进行再分配，实现各个cpu上中断负载相对均衡。中断均衡是建立再“object tree”的基础之上的，object   tree则是通过系统的拓扑结构建立的分层结构。根据系统结构属性NUMA node/packet/cache affinity可以将系统划分为自上而下的四层：node->package->cache->cpu。

       以16核双路服务器为例，系统有两个numa node，每个节点包含两个cluster，每个cluster包含4个cores，共享l2 cache。其结构简图如下：

　　 对应的object tree拓扑结构如图：

其中：

（1）每个节点为一个object，通过struct topo_obj描述。

（2）上下层之间的节点通过parent/child指针管理

（3）每一层都有一个全局链表头指针，用于组织管理处于同一层的所有节点。

2. 数据结构

2.1 Irq_info

       在树形拓扑结构建立之后，就需要统计各个节点上中断负载的信息，以便为重新分配中断提供依据。对于各个中断信息通过struct irq_info来描述。下面结合各个字段介绍下irqlabalance中几个比较关键的概念。

struct irq_info {int irq;       //中断号int class;int type;int level;int flags;struct topo_obj *numa_node;    //中断当前所在node节点对应的objectcpumask_t cpumask;uint64_t irq_count;uint64_t last_irq_count;uint64_t load;int moved;struct topo_obj *assigned_obj; //中断被分配到节点对应的objectchar *name;
};

(1) 中断类型（irq_info.class）

Irqbalance根据中断所属device的pci配置空间class code把中断分成了以下8种类型字。

#define IRQ_OTHER       0
#define IRQ_LEGACY      1
#define IRQ_SCSI        2
#define IRQ_TIMER       3
#define IRQ_ETH         4
#define IRQ_GBETH       5
#define IRQ_10GBETH     6
#define IRQ_VIRT_EVENT  7

其中：irq_info.class 与 pci配置空间 class code的映射关系如下：

(2) 中断层级（irq_info.level）

每种中断类型根据静态映射分别对应一种分配方式，分配方式一共有4种。

#define BALANCE_NONE           0  //表示中断不能进行迁移
#define BALANCE_PACKAGE        1  //表示中断只能在package层进行均衡
#define BALANCE_CACHE          2  //表示中断只能在cache层进行均衡
#define BALANCE_CORE           3  //表示中断只能在core层进行均衡

中断类型与其映射关系如表：

(3) 中断计数

       irq_info.irq_count 表示本次统计irq中断在各个cpu上产生的中断次数之和。

       irq_info.last_irq_count表示上次统计irq中断在各个cpu上的产生的中断次数之和。

(4) 中断的负载

       表示两次统计这段时间内中断增加所带来的负担。在irqbalance中把中断消耗的时间来衡量cpu的负担。

计算方法详见3.4（4）.

2.2. topo_obj

“对象树“中的每个节点均为一个对象，通过struct topo_obj进行描述。

struct topo_obj {uint64_t load;uint64_t last_load;uint64_t irq_count;enum obj_type_e obj_type;  //区别该节点位于哪一层。int number;                // object对应的索引int powersave_mode;cpumask_t mask;           //该节点下包含哪几个cpuGList *interrupts;           //组织被分配到该obj的中断struct topo_obj *parent;     //指向其上一层父对象的objGList *children;            //组织管理该obj包含的下层objGList *numa_nodes;      //指向最顶层所在node节点的objGList **obj_type_list;
};

(1) object节点的负载（topo_obj.load）

• cpu节点的load计算方法：

　　　　在/proc/stat获取每个cpu的信息如下：

　　　　其中第6/7项，分别代表自系统启动以来硬/软中断累计时间（单位是jiffies）。

　　　　cpu负载：单个周期（10s）内，cpu处理软、硬中断的时间之和。

• cpu拓扑层以上层各个节点的负载：

　　　　父节点负载等于各孩子节点负载的总和 。

(2) 节点中断管理指针(topo_obj.interrupts)

       所有被分配到该节点上的中断都挂在该指针上。

(3) 节点中断计数(topo_obj.irq_count)

分配到该节点上的所有中断（即interrupts指针管理的链表上的中断）在单位周期（10s）内增加的次数之和。

(4) 节点的object类型（topo_obj.obj_type）

       object的类型，用来表明该对象处在对象树的哪一层次。Irqbalance 定义了如下4种类型。

     OBJ_TYPE_CPU,OBJ_TYPE_CACHE,OBJ_TYPE_PACKAGE,OBJ_TYPE_NODE

(5) powersave_mode

       用来表示该object是否处在省电模式。具体介绍详见4。

       Irqbalance默认是关闭powersave_mode的，但是用户可以通过irqbalance -p <n>来设置power_thresh。当系统内object的负载较小时，会自动切换到省电模式。

3. irqbalance处理流程

Irqbalance会周期性的（10s）统计系统中断的情况，主要的处理流程图如下：

下面针对各个部分作具体介绍：

 3.1 build_object_tree

（1）作用：

主要实现建立拓扑结构各个节点以及中断数据结构，并初始化。

（2）实现：

       通过遍历/sys/devices/system/node/node[*],决定有多少OBJ_TYPE_NODE的对象。

　　通过遍历/sys/devices/system/cpu/cpu[*],以及是否online，决定有多少OBJ_TYPE_CPU的对象

　　通过遍历/sys/devices/system/cpu/cpu[*]/cache/index[MAX]/shared_cpu_map决定有多少OBJ_TYPE_CACHE对象。

　　通过遍历/topology/physical_package_id决定有多少OBJ_TYPE_PACKAGE的对象。

　　通过遍历/sys/bus/pci/devices/0000:00:[**].[*]/下irq以及msi，建立各个irq的数据，并结合proc/irq/下文件初始化中断数据结构。这样irqbalance就知道该irq属于哪个node以及smp_affinity.

3.2 clear_work_stats

清除各个对象节点上分配中的负载值，以便重新赋值。

3.3 parse_proc_interrupts

       通过分析/proc/interrupts文件，更新各个irq在所有cpu上中断次数的累加和。

3.4 parse_proc_stats

(1) 计算各个对象节点的load，并更新到topo_obj.load。

cpu节点的负载: 通过分析/proc/stats统计硬/软中断的累计时间。

其余节点的负载：父节点负载=各孩子节点负载的总和

(2) 计算各个对象节点上所有中断在单位周期(10s) 内新增加的次数，并更新到load_slice.irq_count。

(3) 计算各个对象节点上单位周期内平均中断数local_count。

       由于分配到上层节点的中断最终要“均分”给下层，所以obj平均中断数loacl_count=obj.irq_cpunt +parent_obj.irq_count/(parent_obj的子节点数)。如图所示：

 (4) 计算对象上各个中断负载 irq_info.load

       单次中断对obj节点的负载贡献值（load_slice），即节点负载除以平均中断数：

      　　　　 load_slice = topo_obj.load/local_count.

       那么该对象节点上各个中断负载就等于单次中断负载贡献值与中断次数的乘积：

　　　　　　irq_info.load= load_slice*（irq_info.irq_count- irq_info.last_irq_count）

3.5 update_migration_status

通过平衡算法找出需要重新分配的中断。自下而上遍历各个拓扑层，针对每一层：

（1）遍历该层各个对象节点，计算该层的平均负载avg_load、标准方差std_deviation以及节点中负载最小值min_load.

（2）再次遍历该层各个拓扑节点，找到大于min­_load的节点，然后把该节点中的中断按照中断的irq_info.class由大到小并负载情况由大到小进行排序，然后依次从该节点移除，放到表头为rebalance_irq_list的链表中。

注意：中断从节点迁移后会更新该节点的负载以及min_load，当两者最接近时停止迁移中断。

　　  也就是说该步骤过后，需要迁移的中断都被放在了表头为rebalance_irq_list的链表中，后续会将这些中断重新分配。

3.6 calculate_placement

(1) 将存在rebalance_irq_list链表中的中断重新排序：优先按照中断的irq_info.class由大到小排列，如果class相同则按照load由大到小排列。

(2) 首先根据中断所在的numa nodeid将中断分配到不同的node 节点上。从这里可以看出中断是不会跨numa 节点迁移的，只能在同一numa node内部进行优化。

(3) 自上而下遍历各个个拓扑层，对于每一拓扑层：

　　　　　　遍历该层节点上的中断，对每一个中断：

　　　　　　　　遍历该节点所有孩子节点，将其迁移到负载最小的孩子节点上。

3.7 activate_mapping

       通过修改/proc/irq/[*]/smp_affinity，使处理生效

4. powersave mode

　　Irqbalance支持powersave mode，默认是关闭的，但是用户可以通过irqbalance -p <n>来设置阈值power_thresh。开启该mode，Irqbalance会根据系统内object的负载情况，会自动将某个cpu object切换省电模式/正常模式。

　　前面3.5小节(1)中，当遍历cpu层各个对象节点，根据load值计算出cpu平均负载avg_load、标准方差std_deviation后。

       (1) 如果load + std_deviation <= avg_load时，表明该cpu的负载较低，则会记录该cpu object，同时记录低负载的cpu个数

       (2）如果load - std_deviation >= avg_load时，表明该cpu 的负载比较高，也会记录高负载的cpu个数。

　　在遍历完整个cpu层的所有节点后，如果不存在高负载cpu，同时低负载的cpu个数大于设定阈值，则会将最后记录的cpu对象的powersaved_mode字段置1. 后续在从rebalance_irq_list的链表重新分配中断时，就不会在分配到该cpu上。

　　一旦系统中存在高负载cpu，irqlabalance就会清除所有cpu 对象的powersaved_mode，恢复正常模式。

5. 补充

1. 中断再分配时，需要先自上而下遍历各层各节点，将符合条件的节点上的中断先迁移到表头为rebalance_irq_list的链表中，然后再将链表中的中断按node->package->cache->cpu逐层分配到各个节点中（分配时会根据irq_info.level决定最终分配到哪一级节点上）。那么刚建立号中断数据库时，各个节点上还没有中断那么是如何操作的呢？

       刚建的中断数据库由指真interrupts_db来管理，初次建立好后会将所有的中断迁移到rebalance_irq_list中。然后将rebalance_irq_list链表中中断按node->package->cache->cpu逐层分配到各个节点中。

2. 如果一个package中有两个node时，irqbalance的拓扑层是如何划分的？

　　在这种情况下，cache domian的父节点是package，但是numa节点的子节点是cache domians，而不再是packages，同时package的子节点任然是是cache domians。如图所示：

欢迎大家批评指正 ：-）

irqbalance机制分析

本文档基于irqbalance-1.5.0

源码链接：/+source/irqbalance/

1. object tree

       Irqbalance是用户空间用于优化中断的一个工具，通过周期性的（默认10s）统计各个cpu上的中断情况，重新对中断进行再分配，实现各个cpu上中断负载相对均衡。中断均衡是建立再“object tree”的基础之上的，object   tree则是通过系统的拓扑结构建立的分层结构。根据系统结构属性NUMA node/packet/cache affinity可以将系统划分为自上而下的四层：node->package->cache->cpu。

       以16核双路服务器为例，系统有两个numa node，每个节点包含两个cluster，每个cluster包含4个cores，共享l2 cache。其结构简图如下：

　　 对应的object tree拓扑结构如图：

其中：

（1）每个节点为一个object，通过struct topo_obj描述。

（2）上下层之间的节点通过parent/child指针管理

（3）每一层都有一个全局链表头指针，用于组织管理处于同一层的所有节点。

2. 数据结构

2.1 Irq_info

       在树形拓扑结构建立之后，就需要统计各个节点上中断负载的信息，以便为重新分配中断提供依据。对于各个中断信息通过struct irq_info来描述。下面结合各个字段介绍下irqlabalance中几个比较关键的概念。

struct irq_info {int irq;       //中断号int class;int type;int level;int flags;struct topo_obj *numa_node;    //中断当前所在node节点对应的objectcpumask_t cpumask;uint64_t irq_count;uint64_t last_irq_count;uint64_t load;int moved;struct topo_obj *assigned_obj; //中断被分配到节点对应的objectchar *name;
};

(1) 中断类型（irq_info.class）

Irqbalance根据中断所属device的pci配置空间class code把中断分成了以下8种类型字。

#define IRQ_OTHER       0
#define IRQ_LEGACY      1
#define IRQ_SCSI        2
#define IRQ_TIMER       3
#define IRQ_ETH         4
#define IRQ_GBETH       5
#define IRQ_10GBETH     6
#define IRQ_VIRT_EVENT  7

其中：irq_info.class 与 pci配置空间 class code的映射关系如下：

(2) 中断层级（irq_info.level）

每种中断类型根据静态映射分别对应一种分配方式，分配方式一共有4种。

#define BALANCE_NONE           0  //表示中断不能进行迁移
#define BALANCE_PACKAGE        1  //表示中断只能在package层进行均衡
#define BALANCE_CACHE          2  //表示中断只能在cache层进行均衡
#define BALANCE_CORE           3  //表示中断只能在core层进行均衡

中断类型与其映射关系如表：

(3) 中断计数

       irq_info.irq_count 表示本次统计irq中断在各个cpu上产生的中断次数之和。

       irq_info.last_irq_count表示上次统计irq中断在各个cpu上的产生的中断次数之和。

(4) 中断的负载

       表示两次统计这段时间内中断增加所带来的负担。在irqbalance中把中断消耗的时间来衡量cpu的负担。

计算方法详见3.4（4）.

2.2. topo_obj

“对象树“中的每个节点均为一个对象，通过struct topo_obj进行描述。

struct topo_obj {uint64_t load;uint64_t last_load;uint64_t irq_count;enum obj_type_e obj_type;  //区别该节点位于哪一层。int number;                // object对应的索引int powersave_mode;cpumask_t mask;           //该节点下包含哪几个cpuGList *interrupts;           //组织被分配到该obj的中断struct topo_obj *parent;     //指向其上一层父对象的objGList *children;            //组织管理该obj包含的下层objGList *numa_nodes;      //指向最顶层所在node节点的objGList **obj_type_list;
};

(1) object节点的负载（topo_obj.load）

• cpu节点的load计算方法：

　　　　在/proc/stat获取每个cpu的信息如下：

　　　　其中第6/7项，分别代表自系统启动以来硬/软中断累计时间（单位是jiffies）。

　　　　cpu负载：单个周期（10s）内，cpu处理软、硬中断的时间之和。

• cpu拓扑层以上层各个节点的负载：

　　　　父节点负载等于各孩子节点负载的总和 。

(2) 节点中断管理指针(topo_obj.interrupts)

       所有被分配到该节点上的中断都挂在该指针上。

(3) 节点中断计数(topo_obj.irq_count)

分配到该节点上的所有中断（即interrupts指针管理的链表上的中断）在单位周期（10s）内增加的次数之和。

(4) 节点的object类型（topo_obj.obj_type）

       object的类型，用来表明该对象处在对象树的哪一层次。Irqbalance 定义了如下4种类型。

     OBJ_TYPE_CPU,OBJ_TYPE_CACHE,OBJ_TYPE_PACKAGE,OBJ_TYPE_NODE

(5) powersave_mode

       用来表示该object是否处在省电模式。具体介绍详见4。

       Irqbalance默认是关闭powersave_mode的，但是用户可以通过irqbalance -p <n>来设置power_thresh。当系统内object的负载较小时，会自动切换到省电模式。

3. irqbalance处理流程

Irqbalance会周期性的（10s）统计系统中断的情况，主要的处理流程图如下：

下面针对各个部分作具体介绍：

 3.1 build_object_tree

（1）作用：

主要实现建立拓扑结构各个节点以及中断数据结构，并初始化。

（2）实现：

       通过遍历/sys/devices/system/node/node[*],决定有多少OBJ_TYPE_NODE的对象。

　　通过遍历/sys/devices/system/cpu/cpu[*],以及是否online，决定有多少OBJ_TYPE_CPU的对象

　　通过遍历/sys/devices/system/cpu/cpu[*]/cache/index[MAX]/shared_cpu_map决定有多少OBJ_TYPE_CACHE对象。

　　通过遍历/topology/physical_package_id决定有多少OBJ_TYPE_PACKAGE的对象。

　　通过遍历/sys/bus/pci/devices/0000:00:[**].[*]/下irq以及msi，建立各个irq的数据，并结合proc/irq/下文件初始化中断数据结构。这样irqbalance就知道该irq属于哪个node以及smp_affinity.

3.2 clear_work_stats

清除各个对象节点上分配中的负载值，以便重新赋值。

3.3 parse_proc_interrupts

       通过分析/proc/interrupts文件，更新各个irq在所有cpu上中断次数的累加和。

3.4 parse_proc_stats

(1) 计算各个对象节点的load，并更新到topo_obj.load。

cpu节点的负载: 通过分析/proc/stats统计硬/软中断的累计时间。

其余节点的负载：父节点负载=各孩子节点负载的总和

(2) 计算各个对象节点上所有中断在单位周期(10s) 内新增加的次数，并更新到load_slice.irq_count。

(3) 计算各个对象节点上单位周期内平均中断数local_count。

       由于分配到上层节点的中断最终要“均分”给下层，所以obj平均中断数loacl_count=obj.irq_cpunt +parent_obj.irq_count/(parent_obj的子节点数)。如图所示：

 (4) 计算对象上各个中断负载 irq_info.load

       单次中断对obj节点的负载贡献值（load_slice），即节点负载除以平均中断数：

      　　　　 load_slice = topo_obj.load/local_count.

       那么该对象节点上各个中断负载就等于单次中断负载贡献值与中断次数的乘积：

　　　　　　irq_info.load= load_slice*（irq_info.irq_count- irq_info.last_irq_count）

3.5 update_migration_status

通过平衡算法找出需要重新分配的中断。自下而上遍历各个拓扑层，针对每一层：

（1）遍历该层各个对象节点，计算该层的平均负载avg_load、标准方差std_deviation以及节点中负载最小值min_load.

（2）再次遍历该层各个拓扑节点，找到大于min­_load的节点，然后把该节点中的中断按照中断的irq_info.class由大到小并负载情况由大到小进行排序，然后依次从该节点移除，放到表头为rebalance_irq_list的链表中。

注意：中断从节点迁移后会更新该节点的负载以及min_load，当两者最接近时停止迁移中断。

　　  也就是说该步骤过后，需要迁移的中断都被放在了表头为rebalance_irq_list的链表中，后续会将这些中断重新分配。

3.6 calculate_placement

(1) 将存在rebalance_irq_list链表中的中断重新排序：优先按照中断的irq_info.class由大到小排列，如果class相同则按照load由大到小排列。

(2) 首先根据中断所在的numa nodeid将中断分配到不同的node 节点上。从这里可以看出中断是不会跨numa 节点迁移的，只能在同一numa node内部进行优化。

(3) 自上而下遍历各个个拓扑层，对于每一拓扑层：

　　　　　　遍历该层节点上的中断，对每一个中断：

　　　　　　　　遍历该节点所有孩子节点，将其迁移到负载最小的孩子节点上。

3.7 activate_mapping

       通过修改/proc/irq/[*]/smp_affinity，使处理生效

4. powersave mode

　　Irqbalance支持powersave mode，默认是关闭的，但是用户可以通过irqbalance -p <n>来设置阈值power_thresh。开启该mode，Irqbalance会根据系统内object的负载情况，会自动将某个cpu object切换省电模式/正常模式。

　　前面3.5小节(1)中，当遍历cpu层各个对象节点，根据load值计算出cpu平均负载avg_load、标准方差std_deviation后。

       (1) 如果load + std_deviation <= avg_load时，表明该cpu的负载较低，则会记录该cpu object，同时记录低负载的cpu个数

       (2）如果load - std_deviation >= avg_load时，表明该cpu 的负载比较高，也会记录高负载的cpu个数。

　　在遍历完整个cpu层的所有节点后，如果不存在高负载cpu，同时低负载的cpu个数大于设定阈值，则会将最后记录的cpu对象的powersaved_mode字段置1. 后续在从rebalance_irq_list的链表重新分配中断时，就不会在分配到该cpu上。

　　一旦系统中存在高负载cpu，irqlabalance就会清除所有cpu 对象的powersaved_mode，恢复正常模式。

5. 补充

1. 中断再分配时，需要先自上而下遍历各层各节点，将符合条件的节点上的中断先迁移到表头为rebalance_irq_list的链表中，然后再将链表中的中断按node->package->cache->cpu逐层分配到各个节点中（分配时会根据irq_info.level决定最终分配到哪一级节点上）。那么刚建立号中断数据库时，各个节点上还没有中断那么是如何操作的呢？

       刚建的中断数据库由指真interrupts_db来管理，初次建立好后会将所有的中断迁移到rebalance_irq_list中。然后将rebalance_irq_list链表中中断按node->package->cache->cpu逐层分配到各个节点中。

2. 如果一个package中有两个node时，irqbalance的拓扑层是如何划分的？

　　在这种情况下，cache domian的父节点是package，但是numa节点的子节点是cache domians，而不再是packages，同时package的子节点任然是是cache domians。如图所示：

欢迎大家批评指正 ：-）