Floating proportions with flexible aging period

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 $$

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

1
2
3

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

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

数据结构

fprop_global

用于描述全局事件计数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

/*
 * ---- 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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/*
 *  ---- 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 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/*
 * ---- 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

该函数完成以下任务：

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

fprop_global_destroy

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

fprop_new_period

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

local_single

fprop_local_init_single

该函数完成以下工作：

• 初始化period为0
• 初始化events为0
• 初始化自旋锁lock

fprop_local_destroy_single

该函数为空

__fprop_inc_single

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

fprop_inc_single

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

fprop_fraction_single

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

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

local_percpu

fprop_local_init_percpu

该函数完成以下工作:

• 初始化特定类型事件的period为0
• 分配用于计数特定类型事件的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