Linux 内核数据结构

最后更新: 2023-02-18 08:20:51 +0800 +0800
tags: Data-Structures | Kernel | Linux
原文以英文撰写。您正在阅读AI翻译版本。

Linux’s 列表 APIs 是 intrusive: linkage 是 embedded in the 对象 owned 由 a subsystem. Intrusion removes a separate node allocation 和 lets one 对象 participate in several indexes, but the container API does 不 own 内存 或 provide synchronization.

循环双向链表 #

struct list_head 包含 仅 links:

c 
struct list_head {
    struct list_head *next, *prev;
};

struct job {
    unsigned long id;
    struct list_head pending_link;
    struct list_head owner_link;
};

A 列表 head has the same type 作为 an embedded node. 在 an empty list, next 和 prev both point back 到 the head. 在 a nonempty list, following either direction eventually returns 到 the head. Because the head 是 a sentinel rather than a payload object, iteration has no null terminator.

One 对象 可以 appear in multiple lists 通过 different members. Every operation 必须 name the correct member; mixing pending_link 和 owner_link corrupts both lists.

初始化与基本修改 #

Use LIST_HEAD() 用于 a declaration 和 INIT_LIST_HEAD() 当 initializing an existing object:

c 
static LIST_HEAD(pending_jobs);

struct queue {
    spinlock_t lock;
    struct list_head jobs;
};

static void queue_init(struct queue *queue)
{
    spin_lock_init(&queue->lock);
    INIT_LIST_HEAD(&queue->jobs);
}

LIST_HEAD_INIT(name) 是 an initializer expression, which 是 useful inside a larger static initializer. Initialization 必须 occur 在……之前 any 列表 operation.

Insertion 是 relative 到 the sentinel:

c 
list_add(&job->pending_link, &pending_jobs);      /* after head */
list_add_tail(&job->pending_link, &pending_jobs); /* before head */

list_add() implements stack-like insertion 在 the front; list_add_tail() implements queue-like insertion 在 the back. list_move() 和 list_move_tail() unlink an existing node 和 insert it 在 the destination’s front 或 tail.

list_del() unlinks a node 和 poisons its links 到 expose accidental reuse. Use list_del_init() 当 the detached node 必须 become a valid, self-linked empty node again:

c 
if (!list_empty(&pending_jobs)) {
    struct job *job =
        list_first_entry(&pending_jobs, struct job, pending_link);

    list_del_init(&job->pending_link);
    finish_job(job);
}

Do 不 add one linkage member twice. 一个 self-linked node 可以 be checked，使用 list_empty(&job->pending_link), but convention works 仅 当 every removal reinitializes the node.

Ownership Recovery，使用 container_of #

An iterator reaches a struct list_head *, but subsystem 代码 needs its containing object. container_of(ptr, type, member) subtracts the compile-time offset 的 member 来自 ptr 和 preserves compile-time type checking. list_entry() specializes pattern:

c 
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

struct job *job =
    list_entry(node, struct job, pending_link);

result 是 valid 仅 当 node really denotes the specified member 的 a live struct job. Neither macro performs dynamic type validation.

Typed iteration avoids an explicit conversion:

c 
struct job *job;

list_for_each_entry(job, &pending_jobs, pending_link)
    run_job(job);

Reverse 和 continuation variants exist 用于 less common traversal patterns. Choose the narrowest documented macro rather than open-coding next 和 prev, because the macros encode sentinel handling.

迭代时删除 #

Ordinary iteration reads the current node’s next link 在……之后 the loop body. Deleting the current node invalidates operation. 一个 _safe iterator stores the next 对象 first:

c 
struct job *job, *next;

list_for_each_entry_safe(job, next, &pending_jobs, pending_link) {
    if (job_cancelled(job)) {
        list_del(&job->pending_link);
        kfree(job);
    }
}

“Safe” means safe against deletion 由 this loop. It does 不 protect against another CPU, interrupt, 或 callback mutating the list, 和 it does 不 establish kfree() 是 legal. External 参考资料may require reference counting, RCU, 或 another lifetime protocol.

拼接链表 #

Splice 操作 relink an entire 列表 in constant time:

c 
LIST_HEAD(batch);

build_batch(&batch);
list_splice_tail_init(&batch, &pending_jobs);
  • list_splice() inserts 在……之后 the destination head.
  • list_splice_tail() inserts 在……之前 the destination head.
  • _init variants also reinitialize the 源码 head.

After list_splice() without _init, the 源码 head still points 到 the transferred chain. Iterating 源码 作为 an independent 列表 可以 loop incorrectly because its links no longer describe a separate circular list. Use an _init variant 当 ownership transfers 和 the 源码 必须 become empty.

list_cut_position() moves a prefix 到 another head. As，使用 every 列表 mutation, the caller 必须 ensure all nodes 和 heads belong 到 the expected list.

哈希单向链表 #

Hash tables need many bucket heads, so hlist 使用 a one-pointer head:

c 
struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next;
    struct hlist_node **pprev;
};

struct cache_entry {
    unsigned long key;
    struct hlist_node hash_node;
};

pprev points 到 the link points 在 the node: either the bucket’s first member 或 the previous node’s next member. Deletion 可以 therefore update the predecessor link in constant time without storing a conventional prev pointer. asymmetric representation saves one pointer in every bucket head, which matters 当 a table has many buckets.

c 
static struct hlist_head table[256];

static void cache_insert(struct cache_entry *entry)
{
    unsigned int bucket = hash_long(entry->key, 8);

    hlist_add_head(&entry->hash_node, &table[bucket]);
}

static struct cache_entry *cache_find(unsigned long key)
{
    struct cache_entry *entry;

    hlist_for_each_entry(entry, &table[hash_long(key, 8)], hash_node)
        if (entry->key == key)
            return entry;
    return NULL;
}

Initialize standalone nodes，使用 INIT_HLIST_NODE() 当 代码 relies 在 hlist_unhashed(). Use hlist_del_init() 用于 removal followed 由 reuse, 和 使用 hlist_for_each_entry_safe() 当 the current loop deletes entries.

并发与生命周期由调用方负责 #

List 和 hlist 操作 是 pointer rewrites, 不 transactions. API 提供 no implicit lock, reference count, 内存 barrier 用于 publishing payload fields, 或 reclamation grace period. 一个 subsystem 必须 define:

  1. which lock serializes insertion 和 deletion;
  2. which contexts may traverse the container;
  3. how readers acquire 对象 references;
  4. 当 removed objects 可以 be freed.

A spin lock 可以 protect both traversal 和 mutation 当 critical sections cannot sleep. 一个 mutex 是 preferable in sleepable 进程 context. For read-dominant structures, RCU-specific APIs such 作为 list_add_rcu(), list_del_rcu(), 和 hlist_for_each_entry_rcu() permit lockless readers, but only，使用 the required publication primitives 和 delayed reclamation 在……之后 a grace period. Mixing ordinary 和 RCU variants without a complete protocol 是 不 safe.

_safe iteration suffix 和 the _rcu suffix solve different problems: _safe preserves a loop cursor during local deletion, 同时 _rcu participates in a concurrent-reader lifetime scheme.

参考资料 #

评论

在 GitHub 上阅读或评论（发表评论需要登录）