【原創】Linux RCU原理剖析(一)-初窺門徑

来源:https://www.cnblogs.com/LoyenWang/archive/2020/04/11/12681494.html
-Advertisement-
Play Games

背景 By 魯迅 By 高爾基 說明: 1. Kernel版本:4.14 2. ARM64處理器,Contex A53,雙核 3. 使用工具:Source Insight 3.5, Visio 1. 概述 ,是Linux內核中的一種同步機制。 常被描述為讀寫鎖的替代品,它的特點是讀者並不需要直接與寫 ...


背景

  • Read the fucking source code! --By 魯迅
  • A picture is worth a thousand words. --By 高爾基

說明:

  1. Kernel版本:4.14
  2. ARM64處理器,Contex-A53,雙核
  3. 使用工具:Source Insight 3.5, Visio

1. 概述

RCU, Read-Copy-Update,是Linux內核中的一種同步機制。
RCU常被描述為讀寫鎖的替代品,它的特點是讀者並不需要直接與寫者進行同步,讀者與寫者也能併發的執行。RCU的目標就是最大程度來減少讀者側的開銷,因此也常用於對讀者性能要求高的場景。

  • 優點:

    1. 讀者側開銷很少、不需要獲取任何鎖,不需要執行原子指令或者記憶體屏障;
    2. 沒有死鎖問題;
    3. 沒有優先順序反轉的問題;
    4. 沒有記憶體泄露的危險問題;
    5. 很好的實時延遲;
  • 缺點:

    1. 寫者的同步開銷比較大,寫者之間需要互斥處理;
    2. 使用上比其他同步機制複雜;

來一張圖片來描述下大體的操作吧:

  • 多個讀者可以併發訪問臨界資源,同時使用rcu_read_lock/rcu_read_unlock來標定臨界區;
  • 寫者(updater)在更新臨界資源的時候,拷貝一份副本作為基礎進行修改,當所有讀者離開臨界區後,把指向舊臨界資源的指針指向更新後的副本,並對舊資源進行回收處理;
  • 圖中只顯示一個寫者,當存在多個寫者的時候,需要在寫者之間進行互斥處理;

上述的描述比較簡單,RCU的實現很複雜。本文先對RCU來一個初印象,並結合介面進行實例分析,後續文章再逐層深入到背後的實現原理。開始吧!

2. RCU基礎

2.1 RCU基本要素

RCU的基本思想是將更新Update操作分為兩個部分:1)Removal移除;2)Reclamation回收。
直白點來理解就是,臨界資源被多個讀者讀取,寫者在拷貝副本修改後進行更新時,第一步需要先把舊的臨界資源數據移除(修改指針指向),第二步需要把舊的數據進行回收(比如kfree)。

因此,從功能上分為以下三個基本的要素:Reader/Updater/Reclaimer,三者之間的交互如下圖:

  1. Reader

    • 使用rcu_read_lockrcu_read_unlock來界定讀者的臨界區,訪問受RCU保護的數據時,需要始終在該臨界區域內訪問;
    • 在訪問受保護的數據之前,需要使用rcu_dereference來獲取RCU-protected指針;
    • 當使用不可搶占的RCU時,rcu_read_lock/rcu_read_unlock之間不能使用可以睡眠的代碼;
  2. Updater

    • 多個Updater更新數據時,需要使用互斥機制進行保護;
    • Updater使用rcu_assign_pointer來移除舊的指針指向,指向更新後的臨界資源;
    • Updater使用synchronize_rcucall_rcu來啟動Reclaimer,對舊的臨界資源進行回收,其中synchronize_rcu表示同步等待回收,call_rcu表示非同步回收;
  3. Reclaimer

    • Reclaimer回收的是舊的臨界資源;
    • 為了確保沒有讀者正在訪問要回收的臨界資源,Reclaimer需要等待所有的讀者退出臨界區,這個等待的時間叫做寬限期(Grace Period);

2.2 RCU三個基本機制

用來提供上述描述的功能,RCU基於三種機制來實現。

2.2.1 Publish-Subscribe Mechanism

訂閱機制是個什麼概念,來張圖:

  • UpdaterReader類似於PublisherSubsriber的關係;
  • Updater更新內容後調用介面進行發佈,Reader調用介面讀取發佈內容;

那麼這種訂閱機制,需要做點什麼來保證呢?來看一段偽代碼:

 /* Definiton of global structure */
 1 struct foo {
  2   int a;
  3   int b;
  4   int c;
  5 };
  6 struct foo *gp = NULL;
  7 
  8 /* . . . */
  9 /* =========Updater======== */ 
 10 p = kmalloc(sizeof(*p), GFP_KERNEL);
 11 p->a = 1;
 12 p->b = 2;
 13 p->c = 3;
 14 gp = p;
 15 
 16 /* =========Reader======== */
 17 p = gp;
 18 if (p != NULL) {
 19   do_something_with(p->a, p->b, p->c);
 20 }

乍一看似乎問題不大,Updater進行賦值更新,Reader進行讀取和其他處理。然而,由於存在編譯亂序和執行亂序的問題,上述代碼的執行順序不見得就是代碼的順序,比如在某些架構(DEC Alpha)中,讀者的操作部分,可能在p賦值之前就操作了do_something_with()

為瞭解決這個問題,Linux提供了rcu_assign_pointer/rcu_dereference巨集來確保執行順序,Linux內核也基於rcu_assign_pointer/rcu_dereference巨集進行了更高層的封裝,比如list, hlist,因此,在內核中有三種被RCU保護的場景:1)指針;2)list鏈表;3)hlist哈希鏈表。

針對這三種場景,Publish-Subscribe介面如下表:

2.2.2 Wait For Pre-Existing RCU Readers to Complete

Reclaimer需要對舊的臨界資源進行回收,那麼問題來了,什麼時候進行呢?因此RCU需要提供一種機制來確保之前的RCU讀者全部都已經完成,也就是退出了rcu_read_lock/rcu_read_unlock標定的臨界區後,才能進行回收處理。

  • 圖中Readers和Updater併發執行;
  • 當Updater執行Removal操作後,調用synchronize_rcu,標志著更新結束並開始進入回收階段;
  • synchronize_rcu調用後,此時可能還有新的讀者來讀取臨界資源(更新後的內容),但是,Grace Period只等待Pre-Existing的讀者,也就是在圖中的Reader-4, Reader-5。只要這些之前就存在的RCU讀者退出臨界區後,意味著寬限期的結束,因此就進行回收處理工作了;
  • synchronize_rcu並不是在最後一個Pre-ExistingRCU讀者離開臨界區後立馬就返回,它可能存在一個調度延遲;

2.2.3 Maintain Multiple Versions of Recently Updated Objects

2.2.2節可以看出,在Updater進行更新後,在Reclaimer進行回收之前,是會存在新舊兩個版本的臨界資源的,只有在synchronize_rcu返回後,Reclaimer對舊的臨界資源進行回收,最後剩下一個版本。顯然,在有多個Updater時,臨界資源的版本會更多。

還是來張圖吧,分別以指針和鏈表為例:

  • 調用synchronize_rcu開始為臨界點,分別維護不同版本的臨界資源;
  • 等到Reclaimer回收舊版本資源後,最終歸一統;

3. RCU示例分析

是時候來一波fucking sample code了。

  • 整體的代碼邏輯:
    1. 構造四個內核線程,兩個內核線程測試指針的RCU保護操作,兩個內核線程用於測試鏈表的RCU保護操作;
    2. 在回收的時候,分別用了synchronize_rcu同步回收和call_rcu非同步回收兩種機制;
    3. 為了簡化代碼,基本的容錯判斷都已經省略了;
    4. 沒有考慮多個Updater的機制,因此,也省略掉了Updater之間的互斥操作;
#include <linux/module.h>
#include <linux/init.h>
#include <linux/slab.h>
#include <linux/kthread.h>
#include <linux/rcupdate.h>
#include <linux/delay.h>

struct foo {
	int a;
	int b;
	int c;
	struct rcu_head rcu;
	struct list_head list;
};

static struct foo *g_pfoo = NULL;

LIST_HEAD(g_rcu_list);

struct task_struct *rcu_reader_t;
struct task_struct *rcu_updater_t;
struct task_struct *rcu_reader_list_t;
struct task_struct *rcu_updater_list_t;

/* 指針的Reader操作 */
static int rcu_reader(void *data)
{
	struct foo *p = NULL;
	int cnt = 100;

	while (cnt--) {
		msleep(100);
		rcu_read_lock();
		p = rcu_dereference(g_pfoo);
		pr_info("%s: a = %d, b = %d, c = %d\n",
				__func__, p->a, p->b, p->c);
		rcu_read_unlock();
	}

	return 0;
}

/*  回收處理操作 */
static void rcu_reclaimer(struct rcu_head *rh)
{
	struct foo *p = container_of(rh, struct foo, rcu);
	pr_info("%s: a = %d, b = %d, c = %d\n",
			__func__, p->a, p->b, p->c);
	kfree(p);
}

/* 指針的Updater操作 */
static int rcu_updater(void *data)
{
	int value = 1;
	int cnt = 100;

	while (cnt--) {
		struct foo *old;
		struct foo *new = (struct foo *)kzalloc(sizeof(struct foo), GFP_KERNEL);

		msleep(200);

		old = g_pfoo;

		*new = *g_pfoo;
		new->a = value;
		new->b = value + 1;
		new->c = value + 2;
		rcu_assign_pointer(g_pfoo, new);

		pr_info("%s: a = %d, b = %d, c = %d\n",
				__func__, new->a, new->b, new->c);

		call_rcu(&old->rcu, rcu_reclaimer);

		value++;
	}

	return 0;
}

/* 鏈表的Reader操作 */
static int rcu_reader_list(void *data)
{
	struct foo *p = NULL;
	int cnt = 100;

	while (cnt--) {
		msleep(100);
		rcu_read_lock();
		list_for_each_entry_rcu(p, &g_rcu_list, list) {
			pr_info("%s: a = %d, b = %d, c = %d\n",
					__func__, p->a, p->b, p->c);
		}
		rcu_read_unlock();
	}

	return 0;
}

/* 鏈表的Updater操作 */
static int rcu_updater_list(void *data)
{
	int cnt = 100;
	int value = 1000;

	while (cnt--) {
		msleep(100);
		struct foo *p = list_first_or_null_rcu(&g_rcu_list, struct foo, list);
		struct foo *q = (struct foo *)kzalloc(sizeof(struct foo), GFP_KERNEL);

		*q = *p;
		q->a = value;
		q->b = value + 1;
		q->c = value + 2;

		list_replace_rcu(&p->list, &q->list);

		pr_info("%s: a = %d, b = %d, c = %d\n",
				__func__, q->a, q->b, q->c);

		synchronize_rcu();
		kfree(p);

		value++; 
	}

	return 0;
}

/* module初始化 */
static int rcu_test_init(void)
{
	struct foo *p;

	rcu_reader_t = kthread_run(rcu_reader, NULL, "rcu_reader");
	rcu_updater_t = kthread_run(rcu_updater, NULL, "rcu_updater");
	rcu_reader_list_t = kthread_run(rcu_reader_list, NULL, "rcu_reader_list");
	rcu_updater_list_t = kthread_run(rcu_updater_list, NULL, "rcu_updater_list");

	g_pfoo = (struct foo *)kzalloc(sizeof(struct foo), GFP_KERNEL);

	p = (struct foo *)kzalloc(sizeof(struct foo), GFP_KERNEL);
	list_add_rcu(&p->list, &g_rcu_list);

	return 0;
}

/* module清理工作 */
static void rcu_test_exit(void)
{
	kfree(g_pfoo);
	kfree(list_first_or_null_rcu(&g_rcu_list, struct foo, list));

	kthread_stop(rcu_reader_t);
	kthread_stop(rcu_updater_t);
	kthread_stop(rcu_reader_list_t);
	kthread_stop(rcu_updater_list_t);
}

module_init(rcu_test_init);
module_exit(rcu_test_exit);

MODULE_AUTHOR("Loyen");
MODULE_LICENSE("GPL");

為了證明沒有騙人,貼出在開發板上運行的輸出log,如下圖:

4. API介紹

4.1 核心API

下邊的這些介面,不能更核心了。

a.      rcu_read_lock()  //標記讀者臨界區的開始
b.      rcu_read_unlock()  //標記讀者臨界區的結束
c.      synchronize_rcu() / call_rcu() //等待Grace period結束後進行資源回收
d.      rcu_assign_pointer()  //Updater使用這個巨集對受RCU保護的指針進行賦值
e.      rcu_dereference()  //Reader使用這個巨集來獲取受RCU保護的指針

4.2 其他相關API

基於核心的API,擴展了其他相關的API,如下,不再詳述:

RCU list traversal::

        list_entry_rcu
        list_entry_lockless
        list_first_entry_rcu
        list_next_rcu
        list_for_each_entry_rcu
        list_for_each_entry_continue_rcu
        list_for_each_entry_from_rcu
        list_first_or_null_rcu
        list_next_or_null_rcu
        hlist_first_rcu
        hlist_next_rcu
        hlist_pprev_rcu
        hlist_for_each_entry_rcu
        hlist_for_each_entry_rcu_bh
        hlist_for_each_entry_from_rcu
        hlist_for_each_entry_continue_rcu
        hlist_for_each_entry_continue_rcu_bh
        hlist_nulls_first_rcu
        hlist_nulls_for_each_entry_rcu
        hlist_bl_first_rcu
        hlist_bl_for_each_entry_rcu

RCU pointer/list update::

        rcu_assign_pointer
        list_add_rcu
        list_add_tail_rcu
        list_del_rcu
        list_replace_rcu
        hlist_add_behind_rcu
        hlist_add_before_rcu
        hlist_add_head_rcu
        hlist_add_tail_rcu
        hlist_del_rcu
        hlist_del_init_rcu
        hlist_replace_rcu
        list_splice_init_rcu
        list_splice_tail_init_rcu
        hlist_nulls_del_init_rcu
        hlist_nulls_del_rcu
        hlist_nulls_add_head_rcu
        hlist_bl_add_head_rcu
        hlist_bl_del_init_rcu
        hlist_bl_del_rcu
        hlist_bl_set_first_rcu

RCU::

        Critical sections       Grace period            Barrier

        rcu_read_lock           synchronize_net         rcu_barrier
        rcu_read_unlock         synchronize_rcu
        rcu_dereference         synchronize_rcu_expedited
        rcu_read_lock_held      call_rcu
        rcu_dereference_check   kfree_rcu
        rcu_dereference_protected

bh::

        Critical sections       Grace period            Barrier

        rcu_read_lock_bh        call_rcu                rcu_barrier
        rcu_read_unlock_bh      synchronize_rcu
        [local_bh_disable]      synchronize_rcu_expedited
        [and friends]
        rcu_dereference_bh
        rcu_dereference_bh_check
        rcu_dereference_bh_protected
        rcu_read_lock_bh_held

sched::

        Critical sections       Grace period            Barrier

        rcu_read_lock_sched     call_rcu                rcu_barrier
        rcu_read_unlock_sched   synchronize_rcu
        [preempt_disable]       synchronize_rcu_expedited
        [and friends]
        rcu_read_lock_sched_notrace
        rcu_read_unlock_sched_notrace
        rcu_dereference_sched
        rcu_dereference_sched_check
        rcu_dereference_sched_protected
        rcu_read_lock_sched_held


SRCU::

        Critical sections       Grace period            Barrier

        srcu_read_lock          call_srcu               srcu_barrier
        srcu_read_unlock        synchronize_srcu
        srcu_dereference        synchronize_srcu_expedited
        srcu_dereference_check
        srcu_read_lock_held

SRCU: Initialization/cleanup::

        DEFINE_SRCU
        DEFINE_STATIC_SRCU
        init_srcu_struct
        cleanup_srcu_struct

All: lockdep-checked RCU-protected pointer access::

        rcu_access_pointer
        rcu_dereference_raw
        RCU_LOCKDEP_WARN
        rcu_sleep_check
        RCU_NONIDLE

好吧,羅列這些API有點然並卵。

RCU這個神秘的面紗算是初步揭開了,再往裡邊扒衣服的話,就會顯得有些難了,畢竟RCU背後的實現機制確實挺困難的。那麼,問題來了,要不要做一個扒衣見君者呢,敬請關註吧。

參考

Documentation/RCU
What is RCU, Fundamentally?
What is RCU? Part 2: Usage
RCU part 3: the RCU API
Introduction to RCU

歡迎關註公眾號,持續以圖文形式分享內核機制文章


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 在上次的文章中簡單介紹了 [Reface.NPI] 中的功能。 本期,將對這方法名稱解析規則進行詳細的解釋和說明, 以便開發者可以完整的使用 [Reface.NPI] 中的各種功能。 基本規則 方法名稱以 Insert , Delete , Select , Update 開頭 方法名以數個單詞構成 ...
  • 前言 上一篇文章介紹了ABP的Web API,本文在繼續介紹ABP的其他內容。 在ABP中,WEBAPI是一個值得用的東西。但其他東西,就不一定是那麼好用了。 因為越深入的學習ABP,你就越會發現,它自身有著非常強的設計約束,而而微軟的框架已經有一定的約束了,再使用一套附加約束,顯然會更辛苦。 下麵 ...
  • 在做劍指offer的題目時,發現每次需要用到樹做為參數來測試自己寫的方法時,都很是痛苦。於是乎就萌生了寫一個利用數組作為參數生成樹的方法。簡單測試了下,沒什麼毛病。在這裡貼出來,如果以後發現有bug了會持續在後面更新,也歡迎大家指出其中的不足。 public class TreeNode { pub ...
  • 其實Linux和Windows的差別還是很大的,甚至可以說沒有接觸過Linux的人是完全不懂怎麼使用這種操作系統的,至少我自己的感覺是這樣的。在學習Linux之後,我在使用這兩種系統上最直觀的感受就是Windows就是用於個人PC的,簡單明瞭的圖形界面讓即使不懂電腦原理的人也能輕易上手並很快熟練使 ...
  • 在owasp年度top 10 安全問題中,註入高居榜首。SQL註入攻擊指的是通過構建特殊的輸入作為參數傳入Web應用程式, 而這些輸入大都是SQL語法里的一些組合,通過執行SQL語句進而執行攻擊者所要的操作,其主要原因是程式沒有細緻地 過濾用戶輸入的數據,致使非法數據侵入系統。 1. 對於Web應用 ...
  • 1.XSS簡介 2.構造XSS腳本 常用HTML標簽 上面這些代碼下麵會有實驗來一一解釋,反射型xss和存儲型xss都能用。 3.反射型XSS 簡單來說反射型就是臨時的xss,只有別人把該鏈接發給你,你點開之後才會中圈套。但是你不點開,正常的去訪問該網站是沒什麼問題的。 這裡我們用kali當做被下套 ...
  • CentOS 7 LAMP搭建並且部署sqli labs 一、LAMP簡介(摘自百度百科) 1.1.簡介 LAMP是指一組通常一起使用來運行動態網站或者伺服器的自由軟體名稱首字母縮寫: L inux,操作系統 A pache,網頁伺服器 M ariaDB或MySQL,資料庫管理系統(或者資料庫伺服器 ...
  • df -Th 保持更新,更多內容請關註cnblogs.com/xuyaowen; http://man7.org/linux/man-pages/man1/df.1.html df - report file system disk space usage ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...