flex proportions基础设施的作用是:根据不同类型的事件,计算其所占的比例部分。

注意,本文中的代码是基于稳定版本的内核v4.4.128

其数学公式如下:

$$ p_j=\frac{\sum_{i>=0} \frac{x_{i,j}}{2^{i+1}}}{\sum_{i>=0} \frac{x_i}{2^{i+1}}} $$

其中 j代表事件类型,$p_j$为j类型的事件所占总体的比例。$x_{i,j}$为j类型的事件,在第i周期的计数,$x_i$ 为第i周期内各种类型的事件总数。

所以,有如下的等式:

$$ \sum_{j>0} p_{j} = 1 $$

该算法可以简单的通过维护分母来计算。假设d表示总事件的计数,$n_j$代表j类型事件的计数,当一个j类型事件发生时,我们只需要做如下操作:

$$ n_j=n_j+1;d=d+1 $$

当新的统计周期被声明时,执行如下操作即可

d /= 2;
for_each j
	n_j /= 2;

为了避免循环计算每种类型事件的技术,这里的算法进行了优化,只有当询问该类型事件所占的比例,或者该类型事件发生时,才进行计算。

数据结构

fprop_global

用于描述全局事件计数:

include/linux/flex_proportions.h(line 24)
/*
 * ---- Global proportion definitions ----
 */
struct fprop_global {
        /* Number of events in the current period */
        struct percpu_counter events;
        /* Current period */
        unsigned int period;
        /* Synchronization with period transitions */
        seqcount_t sequence;
};

fprop_local_single

用于描述每种类型的事件计数:

include/linux/flex_proportions.h(line 40)
/*
 *  ---- SINGLE ----
 */
struct fprop_local_single {
        /* the local events counter */
        unsigned long events;
        /* Period in which we last updated events */
        unsigned int period;
        raw_spinlock_t lock;    /* Protect period and numerator */
};

fprop_local_percpu

用于描述每种类型的事件计数,不过其计数使用的percpu_counter

include/linux/flex_proportions.h(line 72)
/*
 * ---- PERCPU ----
 */
struct fprop_local_percpu {
        /* the local events counter */
        struct percpu_counter events;
        /* Period in which we last updated events */
        unsigned int period;
        raw_spinlock_t lock;    /* Protect period and numerator */
};

编程接口

以下函数所在的文件为: include/linux/flex_proportions.h lib/flex_proportions.c

global

fprop_global_init

该函数完成以下任务:

  • 初始化period0
  • 分配用于全局计数的percpu_counter变量events,并初始化计数为1
  • 初始化顺序锁sequence

fprop_global_destroy

该函数用于释放fprop_global_init分配的percpu_counter变量events

fprop_new_period

该函数用于增加周期period,并根据period来调整events的值。同时该函数使用顺序锁sequence保证了不会并发修改periodevents的值。

local_single

fprop_local_init_single

该函数完成以下工作:

  • 初始化period0
  • 初始化events0
  • 初始化自旋锁lock

fprop_local_destroy_single

该函数为空

__fprop_inc_single

该函数将某种类型的事件计数和全局计数都递增1,同时也根据需要调整特定事件的计数events和周期period。当然调整过程需要使用自旋锁进行保护,保证其不会并发的被修改。

fprop_inc_single

用于在关闭本地中断的情况下,调用函数__fprop_inc_single

fprop_fraction_single

该函数用于计算某种特定事件在整体事件中所占的比例,其结果通过函数参数numeratordenominator返回,分别代表分子和分母。

  • 分子返回特定类型事件的计数
  • 分母返回所有事件的计数
  • 同时做了修正,保证分子除以分母的结果永远保证在01之间。

local_percpu

fprop_local_init_percpu

该函数完成以下工作:

  • 初始化特定类型事件的period0
  • 分配用于计数特定类型事件的percpu_counter变量events,并初始化为0
  • 初始化自旋锁lock

fprop_local_destroy_percpu

释放由fprop_local_init_percpu分配的percpu_counter变量events

__fprop_inc_percpu

该函数将某种类型的事件计数和全局计数都递增1,同时也根据需要调整特定事件的计数events和周期period。当然调整过程需要使用自旋锁进行保护,保证其不会并发的被修改。唯一跟__fprop_inc_single不同的是计数使用的是percpu_counter

fprop_fraction_percpu

fprop_fraction_single类似,用于计算某种特定事件在整体事件中所占的比例,只不过计数使用的percpu_counter

fprop_inc_percpu

用于在关闭本地中断的情况下,调用函数 __fprop_inc_percpu

__fprop_inc_percpu_max

该函数跟 __fprop_inc_percpu类似,唯一不同的时,可以确保特定事件计数所占的比例不会超过某个指定的比例。

内核中的用途

TODO