Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 30.328 phút đọc

Danh sách kiểu nhân Linux

Sau bài này bạn sẽ làm được

  • Phân biệt danh sách xâm nhập với danh sách thường
  • Giải thích cách macro container_of tính ngược ra struct cha
  • Cài vòng lặp duyệt bằng macro
  • Nêu ba ưu điểm khiến nhân Linux chọn cách này

Bài 21.1 cài danh sách liên kết theo cách quen thuộc: node chứa dữ liệu. Nhân Linux làm ngược lại: dữ liệu chứa node. Một phép trừ con trỏ đưa bạn từ node về lại struct cha, và toàn bộ vấn đề kiểu tổng quát biến mất.

#Đảo ngược quan hệ

Node chứa dữ liệu
/* Cach quen thuoc: node chua du lieu */
typedef struct Node {
    void        *du_lieu;      /* hoac int, hoac SinhVien, ... */
    struct Node *next;
} Node;

/* Van de:
     - moi lan them phan tu phai malloc MOT node nua
     - du lieu va node nam o hai cho, hai lan doc bo nho
     - voi void* thi mat kiem kieu
     - mot doi tuong khong the nam trong hai danh sach cung luc */
Dữ liệu chứa node
/* Cach nhan Linux: du lieu chua node */
struct list_head { struct list_head *prev, *next; };

typedef struct {
    char             ten[16];
    int              tuoi;
    struct list_head lien;      /* node NHUNG VAO trong du lieu */
} Nguoi;

/* Loi ich:
     - khong malloc rieng cho node, no la mot truong
     - du lieu va node lien nhau trong bo nho
     - khong co void* nao, kiem kieu day du
     - mot doi tuong nam trong NHIEU danh sach: them nhieu truong lien */
Danh sách xâm nhập
Danh sách mà con trỏ liên kết nằm bên trong chính đối tượng dữ liệu, chứ không nằm trong một node riêng trỏ tới dữ liệu. Tiếng Anh gọi là intrusive list.
/* Cach thuong:                    Cach xam nhap:

   [Node]---> [Nguoi]                [Nguoi              ]
    next                              ten, tuoi, [lien]---> ...
      |
      v
   [Node]---> [Nguoi]                [Nguoi              ]
                                      ten, tuoi, [lien]---> ...

   Hai lan cap phat, hai lan          Mot lan cap phat,
   doc bo nho moi phan tu             du lieu va lien ke nhau */

#Macro container_of

#include <stddef.h>

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))
terminal
./co --bo-cuc
offsetof(Nguoi, ten)  = 0
offsetof(Nguoi, tuoi) = 16
offsetof(Nguoi, lien) = 24
sizeof(Nguoi) = 40, sizeof(struct list_head) = 16

&b       = 000000000061FDD0
&b.lien  = 000000000061FDE8
container_of(&b.lien) = 000000000061FDD0
terminal
# Xem hợp ngữ: container_of biến thành một lệnh trừ
gcc -O2 -S -masm=intel -o - co.c | sed -n '/^lay_nguoi:/,/ret/p'
lay_nguoi:
    lea     rax, -24[rcx]
    ret

#Vòng lặp duyệt

Danh sách vòng có nút đầu
struct list_head { struct list_head *prev, *next; };

static void ds_khoi_tao(struct list_head *h) {
    h->prev = h->next = h;           /* tro vao chinh no: danh sach rong */
}

static void ds_them_cuoi(struct list_head *h, struct list_head *m) {
    m->prev = h->prev;
    m->next = h;
    h->prev->next = m;
    h->prev = m;
}

static void ds_xoa(struct list_head *m) {
    m->prev->next = m->next;
    m->next->prev = m->prev;
    m->prev = m->next = m;           /* de goi ds_xoa hai lan vo hai */
}

static int ds_rong(const struct list_head *h) { return h->next == h; }
Macro duyệt
#define list_for_each_entry(pos, head, type, member)                  \
    for (pos = container_of((head)->next, type, member);              \
         &pos->member != (head);                                      \
         pos = container_of(pos->member.next, type, member))

/* Dung: */
Nguoi *p;

list_for_each_entry(p, &ds, Nguoi, lien)
    printf("%s %d\n", p->ten, p->tuoi);
terminal
gcc -std=c11 -Wall -Wextra -o co co.c && ./co
An 20
Binh 21
Cuong 22

#Ba ưu điểm và ba cái giá

Tiêu chíDanh sách thườngDanh sách xâm nhập
Số lần cấp phát mỗi phần tửHai, node và dữ liệuMột, hoặc không nếu đối tượng tĩnh
Số lần đọc bộ nhớ để tới dữ liệuHai, qua node rồi qua con trỏMột, dữ liệu ngay cạnh
An toàn kiểuMất nếu dùng void *Đầy đủ
Một đối tượng trong nhiều danh sáchCần nhiều nodeThêm một trường
Xóa một phần tử khi đã có con trỏ tới nóPhải tìm node của nóO(1), node nằm ngay trong nó
Đọc mã lần đầuDễ hiểu ngayPhải hiểu container_of trước
Kiểu dữ liệu phải sửa đượcKhông cầnCần, phải thêm trường vào struct
Sai kiểu trong container_ofKhông có vấn đề nàyKhông ai bắt được

Khi nào nên dùng

Tình huốngDanh sách xâm nhậpVì sao
Nhân hệ điều hành, trình điều khiểnNênKhông cấp phát trong ngữ cảnh ngắt, và cần xóa O(1)
Hệ nhúng không cấp phát độngNênĐối tượng tĩnh, không malloc lần nào
Một đối tượng trong nhiều tập hợpNênChỉ cần thêm trường
Ứng dụng thường, vài trăm phần tửKhông cầnDanh sách thường hoặc mảng động đơn giản hơn
Kiểu dữ liệu từ thư viện ngoàiKhông đượcKhông sửa được struct
Nhóm mới học CCân nhắccontainer_of cần thời gian để quen

Tự làm thử

  1. Cài struct list_head cùng bốn hàm khởi tạo, thêm, xóa, và kiểm rỗng.
  2. Cài container_of rồi in &b, &b.lien và kết quả của macro, xác nhận cái đầu bằng cái cuối.
  3. Cài list_for_each_entry và duyệt một danh sách ba phần tử.
  4. Xóa phần tử trong vòng lặp thường, chạy dưới ASan, và đọc thông báo.
  5. Cài bản safe và xác nhận nó chạy sạch.
  6. Thêm trường list_head thứ hai vào struct và đưa cùng một đối tượng vào hai danh sách.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

  • Danh sách xâm nhập nhúng node vào dữ liệu, ngược với cách quen thuộc là node trỏ tới dữ liệu.
  • container_of chỉ là một phép trừ bằng offsetof, và trình biên dịch tính độ lệch đó lúc biên dịch.
  • Danh sách vòng có nút đầu giả làm hàm xóa chỉ còn bốn dòng, không một câu if nào.
  • Ba ưu điểm: một lần cấp phát, xóa O(1) khi đã có con trỏ, và một đối tượng nằm trong nhiều danh sách.
  • Ba cái giá: phải sửa được struct, phải hiểu container_of, và sai tên trường thì không ai bắt được.