input子系統事件處理層(evdev)的環形緩衝區【轉】

在事件處理層(evdev.c)中結構體evdev_client定義了一個環形緩衝區(circular buffer)，其原理是用數組的方式實現了一個先進先出的迴圈隊列(circular queue)，用以緩存內核驅動上報給用戶層的input_event事件。

struct evdev_client {
    unsigned int head;                  // 頭指針
    unsigned int tail;                  // 尾指針
    unsigned int packet_head;           // 包指針
    spinlock_t buffer_lock; 
    struct fasync_struct *fasync;
    struct evdev *evdev;
    struct list_head node;
    unsigned int clk_type;
    bool revoked;
    unsigned long *evmasks[EV_CNT];
    unsigned int bufsize;               // 迴圈隊列大小
    struct input_event buffer[];        // 迴圈隊列數組
};

evdev_client對象維護了三個偏移量：head、tail以及packet_head。head、tail作為迴圈隊列的頭尾指針記錄入口與出口偏移，那麼包指針packet_head有什麼作用呢？

packet_head
內核驅動處理一次輸入，可能上報一到多個input_event事件，為表示處理完成，會在上報這些input_event事件後再上報一次同步事件。頭指針head以input_event事件為單位，記錄緩衝區的入口偏移量，而包指針packet_head則以“數據包”（一到多個input_event事件）為單位，記錄緩衝區的入口偏移量。

環形緩衝區的工作機制

• 迴圈隊列入隊演算法：

  head++;
  head &= bufsize - 1;

• 迴圈隊列出隊演算法：

  tail++;
  tail &= bufsize - 1;

• 迴圈隊列已滿條件：

  head == tail

• 迴圈隊列為空條件：

  packet_head == tail

  “求餘”和“求與”
  為解決頭尾指針的上溢和下溢現象，使隊列的元素空間可重覆使用，一般迴圈隊列的出入隊演算法都採用“求餘”操作：
  　　　　head = (head + 1) % bufsize; // 入隊
  　　　　tail = (tail + 1) % bufsize; // 出隊
  為避免計算代價高昂的“求餘”操作，使內核運作更高效，input子系統的環形緩衝區採用了“求與”演算法，這要求bufsize必須為2的冪，在後文中可以看到bufsize的值實際上是為64或者8的n倍，符合“求與”運算的要求。

環形緩衝區的構造以及初始化

用戶層通過open()函數打開input設備節點時，調用過程如下：

open() -> sys_open() -> evdev_open()

在evdev_open()函數中完成了對evdev_client對象的構造以及初始化，每一個打開input設備節點的用戶都在內核中維護了一個evdev_client對象，這些evdev_client對象通過evdev_attach_client()函數註冊在evdev1對象的內核鏈表上。

接下來我們具體分析evdev_open()函數：

static int evdev_open(struct inode *inode, struct file *file)
{
    struct evdev *evdev = container_of(inode->i_cdev, struct evdev, cdev);
    // 1.計算環形緩衝區大小bufsize以及evdev_client對象大小size
    unsigned int bufsize = evdev_compute_buffer_size(evdev->handle.dev);
    unsigned int size = sizeof(struct evdev_client) +
                    bufsize * sizeof(struct input_event);
    struct evdev_client *client;
    int error;

    // 2. 分配內核空間
    client = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
    if (!client)
        client = vzalloc(size);
    if (!client)
        return -ENOMEM;

    client->bufsize = bufsize;
    spin_lock_init(&client->buffer_lock);
    client->evdev = evdev;

    // 3. 註冊到內核鏈表
    evdev_attach_client(evdev, client);

    error = evdev_open_device(evdev);
    if (error)
        goto err_free_client;

    file->private_data = client;
    nonseekable_open(inode, file);

    return 0;

 err_free_client:
    evdev_detach_client(evdev, client);
    kvfree(client);
    return error;
}

在evdev_open()函數中，我們看到了evdev_client對象從構造到註冊到內核鏈表的過程，然而它是在哪裡初始化的呢？其實kzalloc()函數在分配空間的同時就通過__GFP_ZERO標誌做了初始化：

static inline void *kzalloc(size_t size, gfp_t flags)
{
    return kmalloc(size, flags | __GFP_ZERO);
}

生產者/消費者模型

內核驅動與用戶程式就是典型的生產者/消費者模型，內核驅動產生input_event事件，然後通過input_event()函數寫入環形緩衝區，用戶程式通過read()函數從環形緩衝區中獲取input_event事件。

環形緩衝區的生產者

內核驅動作為生產者，通過input_event()上報input_event事件時，最終調用___pass_event()函數將事件寫入環形緩衝區：

static void __pass_event(struct evdev_client *client,
             const struct input_event *event)
{
    // 將input_event事件存入緩衝區，隊頭head自增指向下一個元素空間
    client->buffer[client->head++] = *event;
    client->head &= client->bufsize - 1;

    // 當隊頭head與隊尾tail相等時，說明緩衝區空間已滿
    if (unlikely(client->head == client->tail)) {
        /*
         * This effectively "drops" all unconsumed events, leaving
         * EV_SYN/SYN_DROPPED plus the newest event in the queue.
         */
        client->tail = (client->head - 2) & (client->bufsize - 1);

        client->buffer[client->tail].time = event->time;
        client->buffer[client->tail].type = EV_SYN;
        client->buffer[client->tail].code = SYN_DROPPED;
        client->buffer[client->tail].value = 0;

        client->packet_head = client->tail;
    }

    // 當遇到EV_SYN/SYN_REPORT同步事件時，packet_head移動到隊頭head位置
    if (event->type == EV_SYN && event->code == SYN_REPORT) {
        client->packet_head = client->head;
        kill_fasync(&client->fasync, SIGIO, POLL_IN);
    }
}

環形緩衝區的消費者

用戶程式作為消費者，通過read()函數讀取input設備節點時，最終在內核調用evdev_fetch_next_event()函數從環形緩衝區中讀取input_event事件：

static int evdev_fetch_next_event(struct evdev_client *client,
                  struct input_event *event)
{
    int have_event;

    spin_lock_irq(&client->buffer_lock);

    // 判緩衝區中是否有input_event事件
    have_event = client->packet_head != client->tail;
    if (have_event) {
    // 從緩衝區中讀取一次input_event事件，隊尾tail自增指向下一個元素空間
        *event = client->buffer[client->tail++];
        client->tail &= client->bufsize - 1;
        if (client->use_wake_lock &&
            client->packet_head == client->tail)
            wake_unlock(&client->wake_lock);
    }

    spin_unlock_irq(&client->buffer_lock);

    return have_event;
}