英語

中文 (簡體)

ID 分配¶

作者:: Matthew Wilcox

概述¶

一個常見的待解決問題是分配識別符號 (ID)；通常是用於標識某個事物的較小數字。例如檔案描述符、程序 ID、網路協議中的資料包識別符號、SCSI 標籤和裝置例項號。IDR 和 IDA 為此問題提供了合理的解決方案，避免了每個人都發明自己的方案。IDR 提供了將 ID 對映到指標的能力，而 IDA 僅提供 ID 分配，因此記憶體效率更高。

IDR 介面已棄用；請改用 XArray。

IDR 用法¶

首先初始化一個 IDR，可以透過 DEFINE_IDR() 用於靜態分配的 IDR，或者透過 idr_init() 用於動態分配的 IDR。

您可以呼叫 idr_alloc() 來分配一個未使用的 ID。透過呼叫 idr_find() 查詢與該 ID 關聯的指標，並透過呼叫 idr_remove() 釋放該 ID。

如果您需要更改與某個 ID 關聯的指標，可以呼叫 idr_replace()。這樣做的常見原因之一是透過向分配函式傳遞 NULL 指標來保留一個 ID；然後使用保留的 ID 初始化物件，最後將初始化後的物件插入到 IDR 中。

一些使用者需要分配大於 INT_MAX 的 ID。到目前為止，所有這些使用者都滿足於 UINT_MAX 的限制，他們使用 idr_alloc_u32()。如果您需要無法容納在 u32 中的 ID，我們將與您合作解決您的需求。

如果您需要按順序分配 ID，可以使用 idr_alloc_cyclic()。IDR 在處理較大 ID 時效率會降低，因此使用此函式會帶來輕微的開銷。

要對 IDR 使用的所有指標執行操作，可以使用基於回撥的 idr_for_each() 或迭代器風格的 idr_for_each_entry()。您可能需要使用 idr_for_each_entry_continue() 來繼續迭代。如果迭代器不符合您的需求，您也可以使用 idr_get_next()。

當您使用完一個 IDR 後，可以呼叫 idr_destroy() 來釋放 IDR 使用的記憶體。這不會釋放 IDR 指向的物件；如果您想這樣做，請使用其中一個迭代器來完成。

您可以使用 idr_is_empty() 來查明當前是否分配了任何 ID。

如果在從 IDR 分配新 ID 時需要加鎖，您可能需要傳遞一組限制性的 GFP 標誌，這可能導致 IDR 無法分配記憶體。為了解決這個問題，您可以在加鎖前呼叫 idr_preload()，然後在分配後呼叫 idr_preload_end()。

idr 同步（摘自 radix-tree.h）

idr_find() 能夠使用 RCU 無鎖呼叫。呼叫者必須確保在此函式呼叫是在 rcu_read_lock() 區域內進行的。其他讀者（無鎖或其他）和修改可能併發執行。

仍然要求呼叫者管理專案的同步和生命週期。因此，如果使用 RCU 無鎖查詢，通常這意味著專案有自己的鎖，或者適合無鎖訪問；並且專案由 RCU 釋放（或者僅在從 idr 樹中刪除後以及經過 synchronize_rcu() 寬限期後才釋放）。

IDA 用法¶

IDA 是一種 ID 分配器，它不提供將 ID 與指標關聯的能力。因此，它只需為每個 ID 儲存一位，從而比 IDR 更節省空間。要使用 IDA，請使用 DEFINE_IDA() 定義它（或將 struct ida 嵌入到資料結構中，然後使用 ida_init() 初始化）。要分配新 ID，請呼叫 ida_alloc()、ida_alloc_min()、ida_alloc_max() 或 ida_alloc_range()。要釋放 ID，請呼叫 ida_free()。

ida_destroy() 可用於處理 IDA，而無需釋放其中的單個 ID。您可以使用 ida_is_empty() 來查明 IDA 當前是否分配了任何 ID。

IDA 處理其自身的鎖。在您的程式碼中，安全地呼叫任何 IDA 函式都無需同步。

ID 目前限制在 [0-INT_MAX] 範圍內。如果這是一個不便的限制，那麼提高最大值應該相當簡單。

函式和結構¶

IDR_INIT¶

IDR_INIT (name)

初始化一個 IDR。

引數

名稱: IDR 的名稱。

描述

一個新初始化的 IDR 不包含任何 ID。

DEFINE_IDR¶

DEFINE_IDR (name)

定義一個靜態分配的 IDR。

引數

名稱: IDR 的名稱。

描述

使用此宏定義的 IDR 可直接使用，無需額外初始化。它不包含任何 ID。

unsigned int idr_get_cursor(const struct idr *idr)¶: 返回迴圈分配器的當前位置

引數

const struct idr *idr: idr 控制代碼

描述

返回值是 idr_alloc_cyclic() 下次將返回的值，如果該值是空閒的（否則搜尋將從該位置開始）。

void idr_set_cursor(struct idr *idr, unsigned int val)¶: 設定迴圈分配器的當前位置

引數

struct idr *idr: idr 控制代碼
unsigned int val: 新位置

描述

下次呼叫 idr_alloc_cyclic() 將返回 val，如果它空閒（否則搜尋將從該位置開始）。

void idr_init_base(struct idr *idr, int base)¶: 初始化一個 IDR。

引數

struct idr *idr: IDR 控制代碼。
int base: IDR 的基值。

描述

此 idr_init() 變體建立了一個 IDR，它將從 base 開始分配 ID。

void idr_init(struct idr *idr)¶: 初始化一個 IDR。

引數

struct idr *idr: IDR 控制代碼。

描述

初始化一個動態分配的 IDR。要初始化靜態分配的 IDR，請使用 DEFINE_IDR()。

bool idr_is_empty(const struct idr *idr)¶: 是否分配了任何 ID？

引數

const struct idr *idr: IDR 控制代碼。

返回

如果已從該 IDR 分配了任何 ID，則為 true。

void idr_preload_end(void)¶: 結束由 idr_preload() 開始的預載入段

引數

void: 無引數

描述

每個 idr_preload() 都應該與此函式的呼叫相匹配。有關詳細資訊，請參閱 idr_preload()。

idr_for_each_entry¶

idr_for_each_entry (idr, entry, id)

迭代 IDR 中給定型別的元素。

引數

idr: IDR 控制代碼。
entry: 用作遊標的型別 *
id: 條目 ID。

描述

entry 和 id 在迴圈之前無需初始化，正常終止後 entry 將保留 NULL 值。這對於表示“未找到”的值很方便。

idr_for_each_entry_ul¶

idr_for_each_entry_ul (idr, entry, tmp, id)

迭代 IDR 中給定型別的元素。

引數

idr: IDR 控制代碼。
entry: 用作遊標的型別 *。
tmp: ID 的臨時佔位符。
id: 條目 ID。

描述

entry 和 id 在迴圈之前無需初始化，正常終止後 entry 將保留 NULL 值。這對於表示“未找到”的值很方便。

idr_for_each_entry_continue¶

idr_for_each_entry_continue (idr, entry, id)

繼續迭代 IDR 中給定型別的元素

引數

idr: IDR 控制代碼。
entry: 用作遊標的型別 *。
id: 條目 ID。

描述

繼續迭代條目，從當前位置之後繼續。

idr_for_each_entry_continue_ul¶

idr_for_each_entry_continue_ul (idr, entry, tmp, id)

繼續迭代 IDR 中給定型別的元素

引數

idr: IDR 控制代碼。
entry: 用作遊標的型別 *。
tmp: ID 的臨時佔位符。
id: 條目 ID。

描述

繼續迭代條目，從當前位置之後繼續。正常終止後，entry 將保留 NULL 值。這對於表示“未找到”的值很方便。

int ida_alloc(struct ida *ida, gfp_t gfp)¶: 分配一個未使用的 ID。

引數

struct ida *ida: IDA 控制代碼。
gfp_t gfp: 記憶體分配標誌。

描述

分配一個介於 0 和 INT_MAX（含）之間的 ID。

上下文

任何上下文。在您的程式碼中，安全地呼叫此函式無需加鎖。

返回

已分配的 ID，如果無法分配記憶體則為 -ENOMEM，如果沒有空閒 ID 則為 -ENOSPC。

int ida_alloc_min(struct ida *ida, unsigned int min, gfp_t gfp)¶: 分配一個未使用的 ID。

引數

struct ida *ida: IDA 控制代碼。
unsigned int min: 要分配的最低 ID。
gfp_t gfp: 記憶體分配標誌。

描述

分配一個介於 min 和 INT_MAX（含）之間的 ID。

上下文

任何上下文。在您的程式碼中，安全地呼叫此函式無需加鎖。

返回

已分配的 ID，如果無法分配記憶體則為 -ENOMEM，如果沒有空閒 ID 則為 -ENOSPC。

int ida_alloc_max(struct ida *ida, unsigned int max, gfp_t gfp)¶: 分配一個未使用的 ID。

引數

struct ida *ida: IDA 控制代碼。
unsigned int max: 要分配的最高 ID。
gfp_t gfp: 記憶體分配標誌。

描述

分配一個介於 0 和 max（含）之間的 ID。

上下文

任何上下文。在您的程式碼中，安全地呼叫此函式無需加鎖。

返回

已分配的 ID，如果無法分配記憶體則為 -ENOMEM，如果沒有空閒 ID 則為 -ENOSPC。

int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid, unsigned long max, gfp_t gfp)¶: 分配一個 ID。

引數

struct idr *idr: IDR 控制代碼。
void *ptr: 與新 ID 關聯的指標。
u32 *nextid: 指向一個 ID 的指標。
unsigned long max: 要分配的最大 ID（含）。
gfp_t gfp: 記憶體分配標誌。

描述

在由 nextid 和 max 指定的範圍內分配一個未使用的 ID。請注意，max 是包含的，而 idr_alloc() 的 end 引數是排他的。新 ID 在指標插入 IDR 之前被分配給 nextid，因此如果 nextid 指向 ptr 所指向的物件，併發查詢將不會找到未初始化的 ID。

呼叫者應提供自己的鎖，以確保不可能對 IDR 進行兩次併發修改。對 IDR 的只讀訪問可以在 RCU 讀鎖下進行，或者可以排除同時寫入。

返回

如果分配了 ID 則為 0，如果記憶體分配失敗則為 -ENOMEM，如果找不到空閒 ID 則為 -ENOSPC。如果發生錯誤，nextid 不變。

int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)¶: 分配一個 ID。

引數

struct idr *idr: IDR 控制代碼。
void *ptr: 與新 ID 關聯的指標。
int start: 最小 ID（含）。
int end: 最大 ID（不含）。
gfp_t gfp: 記憶體分配標誌。

描述

在由 start 和 end 指定的範圍內分配一個未使用的 ID。如果 end <= 0，則將其視為比 INT_MAX 大一。這允許呼叫者使用 start + N 作為 end，只要 N 在整數範圍內即可。

呼叫者應提供自己的鎖，以確保不可能對 IDR 進行兩次併發修改。對 IDR 的只讀訪問可以在 RCU 讀鎖下進行，或者可以排除同時寫入。

返回

新分配的 ID；如果記憶體分配失敗則為 -ENOMEM；如果找不到空閒 ID 則為 -ENOSPC。

int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)¶: 迴圈分配一個 ID。

引數

struct idr *idr: IDR 控制代碼。
void *ptr: 與新 ID 關聯的指標。
int start: 最小 ID（含）。
int end: 最大 ID（不含）。
gfp_t gfp: 記憶體分配標誌。

描述

在由 start 和 end 指定的範圍內分配一個未使用的 ID。如果 end <= 0，則將其視為比 INT_MAX 大一。這允許呼叫者使用 start + N 作為 end，只要 N 在整數範圍內即可。對未使用 ID 的搜尋將從上次分配的 ID 開始，如果未在到達 end 之前找到空閒 ID，則將環繞到 start。

呼叫者應提供自己的鎖，以確保不可能對 IDR 進行兩次併發修改。對 IDR 的只讀訪問可以在 RCU 讀鎖下進行，或者可以排除同時寫入。

返回

新分配的 ID；如果記憶體分配失敗則為 -ENOMEM；如果找不到空閒 ID 則為 -ENOSPC。

void *idr_remove(struct idr *idr, unsigned long id)¶: 從 IDR 中移除一個 ID。

引數

struct idr *idr: IDR 控制代碼。
unsigned long id: 指標 ID。

描述

從 IDR 中移除此 ID。如果此 ID 之前不在 IDR 中，此函式返回 NULL。

由於此函式修改 IDR，呼叫者應提供自己的鎖以確保不可能對同一 IDR 進行併發修改。

返回

以前與此 ID 關聯的指標。

void *idr_find(const struct idr *idr, unsigned long id)¶: 返回給定 ID 的指標。

引數

const struct idr *idr: IDR 控制代碼。
unsigned long id: 指標 ID。

描述

查詢與此 ID 關聯的指標。NULL 指標可能表示 id 未分配，或者 NULL 指標與此 ID 關聯。

在葉指標生命週期正確管理的情況下，此函式可以在 rcu_read_lock() 下呼叫。

返回

與此 ID 關聯的指標。

int idr_for_each(const struct idr *idr, int (*fn)(int id, void *p, void *data), void *data)¶: 迭代所有儲存的指標。

引數

const struct idr *idr: IDR 控制代碼。
int (*fn)(int id, void *p, void *data): 為每個指標呼叫的函式。
void *data: 傳遞給回撥函式的資料。

描述

將為 idr 中的每個條目呼叫回撥函式，並傳遞 ID、條目和 data。

如果 fn 返回非 0 的值，則迭代停止，並從此函式返回該值。

如果受 RCU 保護，idr_for_each() 可以與 idr_alloc() 和 idr_remove() 併發呼叫。新新增的條目可能不會被看到，已刪除的條目可能會被看到，但新增和刪除條目不會導致其他條目被跳過，也不會導致虛假條目被看到。

void *idr_get_next_ul(struct idr *idr, unsigned long *nextid)¶: 查詢下一個已填充的條目。

引數

struct idr *idr: IDR 控制代碼。
unsigned long *nextid: 指向一個 ID 的指標。

描述

返回樹中 ID 大於或等於 nextid 所指向的值的下一個已填充條目。退出時，nextid 將更新為找到的值的 ID。要在迴圈中使用，使用者必須遞增 nextid 所指向的值。

void *idr_get_next(struct idr *idr, int *nextid)¶: 查詢下一個已填充的條目。

引數

struct idr *idr: IDR 控制代碼。
int *nextid: 指向一個 ID 的指標。

描述

返回樹中 ID 大於或等於 nextid 所指向的值的下一個已填充條目。退出時，nextid 將更新為找到的值的 ID。要在迴圈中使用，使用者必須遞增 nextid 所指向的值。

void *idr_replace(struct idr *idr, void *ptr, unsigned long id)¶: 替換給定 ID 的指標。

引數

struct idr *idr: IDR 控制代碼。
void *ptr: 與 ID 關聯的新指標。
unsigned long id: 要更改的 ID。

描述

替換已註冊 ID 的指標並返回舊值。此函式可以在 RCU 讀鎖下與 idr_alloc() 和 idr_remove() 併發呼叫（只要被移除的 ID 不是被替換的 ID！）。

返回

成功時的舊值。-ENOENT 表示未找到 id。-EINVAL 表示 ptr 無效。

int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, gfp_t gfp)¶: 分配一個未使用的 ID。

引數

struct ida *ida: IDA 控制代碼。
unsigned int min: 要分配的最低 ID。
unsigned int max: 要分配的最高 ID。
gfp_t gfp: 記憶體分配標誌。

描述

分配一個介於 min 和 max（含）之間的 ID。即使 max 更大，分配的 ID 也不會超過 INT_MAX。

上下文

任何上下文。在您的程式碼中，安全地呼叫此函式無需加鎖。

返回

已分配的 ID，如果無法分配記憶體則為 -ENOMEM，如果沒有空閒 ID 則為 -ENOSPC。

int ida_find_first_range(struct ida *ida, unsigned int min, unsigned int max)¶: 獲取最低使用的 ID。

引數

struct ida *ida: IDA 控制代碼。
unsigned int min: 要獲取的最低 ID。
unsigned int max: 要獲取的最高 ID。

描述

獲取介於 min 和 max（含）之間的最低已使用 ID。即使 max 更大，返回的 ID 也不會超過 INT_MAX。

上下文

任何上下文。獲取並釋放 xa_lock。

返回

最低使用的 ID，如果未找到使用的 ID 則返回 errno。

void ida_free(struct ida *ida, unsigned int id)¶: 釋放一個已分配的 ID。

引數

struct ida *ida: IDA 控制代碼。
unsigned int id: 先前分配的 ID。

上下文

任何上下文。在您的程式碼中，安全地呼叫此函式無需加鎖。

void ida_destroy(struct ida *ida)¶: 釋放所有 ID。

引數

struct ida *ida: IDA 控制代碼。

描述

呼叫此函式將釋放所有 ID 並釋放 IDA 使用的所有資源。此呼叫返回後，IDA 將為空，可以重複使用或釋放。如果 IDA 已為空，則無需呼叫此函式。

上下文

任何上下文。在您的程式碼中，安全地呼叫此函式無需加鎖。

Linux 核心

目錄

本頁

ID 分配¶

概述¶

IDR 用法¶

IDA 用法¶

函式和結構¶