Chapter 2: The Art of Structures

Kernel Sources Covered: , ,

Prologue

Lin Xiaoyuan followed the pointers in a circle and returned to where he began.

He now knew this: everything in the kernel is connected through pointers. But he also discovered a problem. A pointer only tells him "from here to there". It does not tell him "what is there".

He saw a pointer point to a region of memory. What was stored in that region? A number? A character? Or the complete state of a process?

He did not know.

So he began observing the contents of that memory. He found that the data was not piled together at random. It was arranged according to rules, forming meaningful wholes.

He saw something that contained fields such as , , , and . These fields were organized together, jointly describing all information about a process.

Only later did he learn that this was called a structure.

And that thing was called .

He spent a long time studying structure layout. He discovered gaps between fields, known as padding bytes. He discovered that field order affects structure size. He discovered a miraculous macro that can infer the address of an entire structure from a pointer to any one of its fields.

That macro was called .

The first time he saw it, he could not understand it at all. How could a pointer to one field infer the entire structure?

Only after he understood did it make sense: treat address 0 as the starting address of the structure, and the address of a member is its offset.

At that moment, he felt he had seen one of the most exquisite designs in the kernel world.

One: Structure Memory Layout

Lin Xiaoyuan first met the master of structures in a ruin of memory.

It was a giant humanoid assembled from fragments. Each fragment bore the name of a field: , , , ... The fragments varied in width. Some pressed tightly together, while others were separated by clear gaps.

"Are you ?" Lin Xiaoyuan asked.

The humanoid lowered its head. Its voice was steady as bedrock. "I am the container of all processes. Every process's state, priority, and name are stored in my body. But do you see it? My body is not compact."

Lin Xiaoyuan did see it. Between the fragments were gaps filled with zero: padding bytes inserted by the compiler.

"Why are these gaps here?"

"Alignment," the humanoid said. "When the CPU reads memory, it does not necessarily read byte by byte. It reads fixed-size chunks. If a 4-byte int happens to straddle the boundary between two chunks, the CPU may have to read twice and combine the result, wasting time. So the compiler inserts padding bytes between fields to ensure that each field lands on its natural boundary."

The humanoid raised one hand. That hand was made of char a (1 byte), int b (4 bytes), char c (1 byte), and long d (8 bytes). "If arranged in this order, a needs 3 bytes of padding after it so b aligns to a 4-byte boundary, and c needs 7 bytes of padding after it so d aligns to an 8-byte boundary. The total is 24 bytes."

Then it raised the other hand: long d, int b, char a, char c. "But if you put the large fields first and the small fields later, d takes 8 bytes, b takes 4, and a and c take 1 byte each. Only 2 bytes of padding are needed at the end. The total is 16 bytes."

"The same fields, but a different order, and the size differs by 8 bytes?"

"In the kernel, a structure may have hundreds, thousands, or millions of instances. Waste 8 bytes a thousand times, and that is 8KB. Waste it a million times, and that is 8MB. Kernel developers must arrange field order carefully, preserving alignment while reducing waste."

Two: , Compact Layout

The humanoid brought Lin Xiaoyuan before a special wall. On it hung a blueprint of a network packet: version, header length, type of service, total length, identification, flags, time to live, protocol, checksum, source address, destination address. The fields were densely arranged, and the distance between each field was precise down to the byte.

"This is an IP header," the humanoid said. "The format of a network protocol is fixed. Not one byte more, not one byte less. But under normal alignment rules, the compiler may insert padding bytes between fields."

"Then what can we do?"

"Use __attribute__((packed))." The humanoid's voice became solemn. "This attribute tells the compiler: do not insert any padding. Lay the fields out exactly in the order I defined."

Lin Xiaoyuan looked at the blueprint. Every field was packed tightly with no gaps, like an alloy compressed to its limit.

"But has a cost," the humanoid warned. "Unaligned memory access can trigger exceptions or performance penalties on some architectures. x86 may tolerate it. ARM may throw an exception directly. So the kernel uses and to access these fields safely."

"Like using special tools to disassemble precision parts?"

"A good metaphor." The humanoid nodded slightly. " belongs in places where layout must be controlled exactly, such as hardware register maps and network protocol headers. For ordinary kernel data structures, do not use it."

Three: Bit Fields, Finer Than Bytes

Beside that wall, Lin Xiaoyuan found an even more precise panel. The panel was only eight bytes, 64 bits, yet it was divided into more than a dozen regions, each only a few bits wide.

"This is a page table entry," the humanoid said. "A 64-bit integer packed full of information."

It pointed at the marks on the panel. "Bit 0: whether the page is present in memory. Bit 1: whether it is writable. Bit 2: whether user space may access it. Bit 5: whether it has been accessed. Bit 6: whether it has been written. Bits 12 through 51: the physical address. Bit 63: whether execution is forbidden."

Lin Xiaoyuan widened his "eyes". More than a dozen flags and a 40-bit physical address were packed into 64 bits?

"That is a bit field," the humanoid said. "Control finer than a byte. Page table entries, interrupt descriptors, device registers: the kernel is full of bit fields."

"Does kernel code use C bit-field syntax?"

The humanoid shook its head. "Usually, no. The kernel tends to prefer explicit shifts and masks, because the layout of C bit fields is defined by the compiler. The standard does not say which bit comes first. With shifts and masks, the programmer controls the position of every bit, which is more portable."

Four: , Finding a Field's Position

The humanoid led Lin Xiaoyuan to a clock tower. On the front of the tower was an enormous dial, but the dial had no numbers, only offsets: at 0, at 8, at 12, at 16, at 20.

"These are the results of ," the humanoid said. "It tells you where each field begins inside a structure."

Lin Xiaoyuan stared at the dial for a long time. "How are these offsets calculated?"

The humanoid's mouth lifted slightly, if a face made of fragments could smile. "Imagine you have a pointer to a structure, but the value of that pointer is 0, NULL. When you access one of its fields, the compiler calculates that field's offset relative to the starting address. Since the starting address is 0, the field's address itself is the offset."

"So offsetof(struct task_struct, pid) is..."

"The value of &((struct task_struct *)0)->pid. Treat NULL as the starting address of the structure, then take the address of . It sounds mad, but the compiler can compute the result at compile time. There is no runtime cost."

Lin Xiaoyuan thought for a while. The trick was almost brutally simple, yet so elegant that it made him sigh in admiration.

Five: , the Kernel's Most Famous Macro

At the top of the clock tower was a door. Three words were carved on it: .

The humanoid stood before the door, its voice turning solemn. "This is one of the most widely used macros in the kernel. What it does is infer the pointer to an outer structure from a pointer to one of its members."

"Infer the whole from one part?"

"Exactly." The humanoid pushed the door open. Inside was an empty space, and at the center sat a . The address of the field was marked by a ray of light. Lin Xiaoyuan could see only that one field pointer, not the entire structure.

"Suppose you only have the pointer to the field," the humanoid said. "How do you find the it belongs to?"

Lin Xiaoyuan shook his head.

"It is simple. The offset of inside the structure is known. can calculate it. Therefore, the starting address of is the address of minus that offset."

The humanoid drew a formula in the air:

task_struct * = (char *)pid_ptr - offsetof(struct task_struct, pid)

Lin Xiaoyuan stared at the formula three times. Then he suddenly understood. It was like seeing a hand stretched through a window and knowing the owner of the hand stood inside. The hand's position minus the arm's length gives the body's position.

"From known to unknown. From part to whole," the humanoid said. "That is . Kernel list traversal, device driver callbacks, file operations: all depend on it. It lets C implement inheritance. As long as a base object is embedded inside a derived object, a base pointer can lead back to the derived object."

Six: Kernel Lists, the Art of Doubly Circular Links

They came down from the clock tower and arrived at a circular square. Around the square stood a ring of figures. Each figure stretched out two hands: the left hand holding the right hand of the figure before it, the right hand holding the left hand of the figure after it. Link after link, with no beginning and no end.

"This is the kernel linked list," the humanoid said. "A doubly circular linked list."

Lin Xiaoyuan moved closer. Embedded in each figure's body was a structure: two pointers, one to the previous node and one to the next node.

"Wait," Lin Xiaoyuan frowned. "Shouldn't a list node contain data? This has only two pointers and no data."

Approval entered the humanoid's voice. "Good question. User-space linked lists usually embed the pointer inside the data structure. The kernel list does the reverse: it embeds the list node inside the data structure."

It pointed to one figure. "This is embedded inside . You cannot directly get from , but you can use to infer the address of from the address of ."

Lin Xiaoyuan suddenly understood. "So when traverses a list, it is constantly using to infer the outer structure from the list node?"

"Exactly. That is the elegance of the kernel list. does not care what structure it is embedded in. The same set of list operations can be used for process lists, file lists, module lists, anything, as long as the structure contains a member. Generic, concise, efficient."

The figures in the circular square kept turning, left hand holding right hand, right hand holding left hand, without pause.

---

Daozang Notes

Kernel Insight

is the cornerstone of object-oriented design in the kernel. In C++, the compiler helps you perform downcasts. In the kernel, does it manually.

To understand is to understand the kernel's design philosophy: do not rely on compiler magic; keep everything under the programmer's control.

Interestingly, the kernel's list traversal macro is the most common application of . This macro appears thousands of times in the kernel source. Every process traversal, file scan, and device enumeration has quietly working behind it. Even the kernel's red-black tree, , relies on a similar trick: infer the outer structure from a tree node.

In other words, the macro you just learned is the foundation for understanding process scheduling, memory management, and file systems later on. It looks simple, but it is one of the most frequently used forms of "magic" in the kernel world.

---

Code Classics

struct bad_layout {
    char  a;     /* 1 byte + 3 bytes of padding */
    int   b;     /* 4 bytes */
    char  c;     /* 1 byte + 7 bytes of padding */
    long  d;     /* 8 bytes */
};

struct good_layout {
    long  d;     /* 8 bytes */
    int   b;     /* 4 bytes */
    char  a;     /* 1 byte */
    char  c;     /* 1 byte + 2 bytes of padding */
};

printf("=== Structure Alignment ===\n");
printf("bad_layout:  %zu bytes\n", sizeof(struct bad_layout));
printf("good_layout: %zu bytes\n", sizeof(struct good_layout));
printf("\n");

printf("bad_layout field offsets:\n");
printf("  a: %zu\n", offsetof(struct bad_layout, a));
printf("  b: %zu\n", offsetof(struct bad_layout, b));
printf("  c: %zu\n", offsetof(struct bad_layout, c));
printf("  d: %zu\n", offsetof(struct bad_layout, d));

printf("\ngood_layout field offsets:\n");
printf("  d: %zu\n", offsetof(struct good_layout, d));
printf("  b: %zu\n", offsetof(struct good_layout, b));
printf("  a: %zu\n", offsetof(struct good_layout, a));
printf("  c: %zu\n", offsetof(struct good_layout, c));

struct __attribute__((packed)) network_header {
    uint8_t  version_ihl;    /* 1 byte: version + header length */
    uint8_t  tos;            /* 1 byte: type of service */
    uint16_t total_length;   /* 2 bytes: total length */
    uint16_t id;             /* 2 bytes: identification */
    uint16_t flags_offset;   /* 2 bytes: flags + fragment offset */
    uint8_t  ttl;            /* 1 byte: time to live */
    uint8_t  protocol;       /* 1 byte: protocol */
    uint16_t checksum;       /* 2 bytes: checksum */
    uint32_t src_addr;       /* 4 bytes: source address */
    uint32_t dst_addr;       /* 4 bytes: destination address */
};

struct normal_header {
    uint8_t  version_ihl;
    uint8_t  tos;
    uint16_t total_length;
    uint16_t id;
    uint16_t flags_offset;
    uint8_t  ttl;
    uint8_t  protocol;
    uint16_t checksum;
    uint32_t src_addr;
    uint32_t dst_addr;
};

printf("=== packed vs normal structure ===\n");
printf("packed size: %zu bytes (should be 20)\n",
       sizeof(struct network_header));
printf("normal size: %zu bytes\n",
       sizeof(struct normal_header));
printf("\n");

printf("packed field offsets:\n");
printf("  version_ihl: %zu\n", offsetof(struct network_header, version_ihl));
printf("  tos:         %zu\n", offsetof(struct network_header, tos));
printf("  total_length:%zu\n", offsetof(struct network_header, total_length));
printf("  src_addr:    %zu\n", offsetof(struct network_header, src_addr));
printf("  dst_addr:    %zu\n", offsetof(struct network_header, dst_addr));

printf("\nNote: fields in packed structures may be unaligned!\n");
printf("The kernel uses get_unaligned() for unaligned fields\n");

/* Simulate the bit-field layout of a page table entry */
struct pte {
    uint64_t present   : 1;   /* bit 0: present in memory */
    uint64_t writable  : 1;   /* bit 1: writable */
    uint64_t user      : 1;   /* bit 2: accessible from user space */
    uint64_t pwt       : 1;   /* bit 3: Page Write-Through */
    uint64_t pcd       : 1;   /* bit 4: Page Cache Disable */
    uint64_t accessed  : 1;   /* bit 5: accessed */
    uint64_t dirty     : 1;   /* bit 6: written */
    uint64_t pat       : 1;   /* bit 7: Page Attribute Table */
    uint64_t global    : 1;   /* bit 8: global page */
    uint64_t available : 3;   /* bits 9-11: available */
    uint64_t address   : 40;  /* bits 12-51: physical address */
    uint64_t reserved  : 11;  /* bits 52-62: reserved */
    uint64_t nx        : 1;   /* bit 63: No Execute */
} __attribute__((packed));

struct pte entry = {0};
uint64_t raw;

enum {
    PTE_PRESENT_BIT = 0,
    PTE_WRITABLE_BIT = 1,
    PTE_USER_BIT = 2,
    PTE_ADDRESS_SHIFT = 12,
    PTE_NX_BIT = 63,
};

#define BIT_ULL(n) (1ULL << (n))
#define PTE_ADDR_MASK (((1ULL << 40) - 1) << PTE_ADDRESS_SHIFT)

printf("=== Page Table Entry (PTE) Bit Fields ===\n");
printf("PTE size: %zu bytes\n\n", sizeof(struct pte));

/* Set a page table entry */
entry.present = 1;
entry.writable = 1;
entry.user = 1;
entry.address = 0x12345;  /* physical page frame number */
entry.nx = 0;

raw = BIT_ULL(PTE_PRESENT_BIT) |
      BIT_ULL(PTE_WRITABLE_BIT) |
      BIT_ULL(PTE_USER_BIT) |
      (0x12345ULL << PTE_ADDRESS_SHIFT);

printf("Explicit mask layout:\n");
printf("  present bit: %d\n", PTE_PRESENT_BIT);
printf("  writable bit:%d\n", PTE_WRITABLE_BIT);
printf("  user bit:    %d\n", PTE_USER_BIT);
printf("  address:     bit %d..51\n", PTE_ADDRESS_SHIFT);
printf("  nx bit:      %d\n\n", PTE_NX_BIT);

printf("raw PTE: 0x%016llx\n", (unsigned long long)raw);
printf("present: %s\n", (raw & BIT_ULL(PTE_PRESENT_BIT)) ? "yes" : "no");
printf("PFN:     0x%llx\n",
       (unsigned long long)((raw & PTE_ADDR_MASK) >> PTE_ADDRESS_SHIFT));

printf("\nWarning: bit-field layout is compiler-defined!\n");
printf("The kernel usually uses shifts and masks instead of bit fields for portability\n");

#define my_offsetof(type, member) \
    ((size_t)&((type *)0)->member)

struct task_struct {
    long   state;
    int    pid;
    int    prio;
    unsigned int policy;
    char   comm[16];
};

printf("=== offsetof ===\n");
printf("standard offsetof:\n");
printf("  state:  %zu\n", offsetof(struct task_struct, state));
printf("  pid:    %zu\n", offsetof(struct task_struct, pid));
printf("  prio:   %zu\n", offsetof(struct task_struct, prio));
printf("  policy: %zu\n", offsetof(struct task_struct, policy));
printf("  comm:   %zu\n", offsetof(struct task_struct, comm));

printf("\ncustom offsetof:\n");
printf("  state:  %zu\n", my_offsetof(struct task_struct, state));
printf("  pid:    %zu\n", my_offsetof(struct task_struct, pid));
printf("  comm:   %zu\n", my_offsetof(struct task_struct, comm));

printf("\nPrinciple: treat NULL(0) as the structure's starting address;\n");
printf("the address of a member is that member's offset\n");

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

struct task_struct {
    long   state;
    int    pid;
    int    prio;
    char   comm[16];
};

struct task_struct task = {
    .state = 0,
    .pid = 42,
    .prio = 120,
    .comm = "swapper/0",
};

/* Suppose we only have a pointer to the pid field */
int *pid_ptr = &task.pid;

/* Use container_of to infer the task_struct pointer */
struct task_struct *recovered =
    container_of(pid_ptr, struct task_struct, pid);

printf("=== container_of ===\n");
printf("original structure address: %p\n", (void *)&task);
printf("pid field address:          %p\n", (void *)pid_ptr);
printf("recovered address:          %p\n", (void *)recovered);
printf("same address: %s\n", (&task == recovered) ? "yes" : "no");
printf("\n");
printf("recovered task:\n");
printf("  pid:  %d\n", recovered->pid);
printf("  prio: %d\n", recovered->prio);
printf("  comm: %s\n", recovered->comm);

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

/* Kernel list node */
struct list_head {
    struct list_head *next;
    struct list_head *prev;
};

/* Structure carrying data */
struct task_struct {
    long state;
    int pid;
    char comm[16];
    struct list_head tasks;  /* list node embedded inside */
};

/* Initialize a list head */
static inline void INIT_LIST_HEAD(struct list_head *list) {
    list->next = list;
    list->prev = list;
}

/* Add a node at the tail */
static inline void list_add_tail(struct list_head *new,
                                  struct list_head *head) {
    new->prev = head->prev;
    new->next = head;
    head->prev->next = new;
    head->prev = new;
}

/* Get the outer structure from a list node */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

/* Traverse the list */
#define list_for_each_entry(pos, head, member) \
    for (pos = list_entry((head)->next, typeof(*pos), member); \
         &pos->member != (head); \
         pos = list_entry(pos->member.next, typeof(*pos), member))

struct list_head task_list;
INIT_LIST_HEAD(&task_list);

struct task_struct t1 = { .state = 0, .pid = 1, .comm = "init" };
struct task_struct t2 = { .state = 0, .pid = 2, .comm = "kthreadd" };
struct task_struct t3 = { .state = 0, .pid = 3, .comm = "rcu_gp" };

list_add_tail(&t1.tasks, &task_list);
list_add_tail(&t2.tasks, &task_list);
list_add_tail(&t3.tasks, &task_list);

printf("=== Kernel List Traversal ===\n");
struct task_struct *pos;
list_for_each_entry(pos, &task_list, tasks) {
    printf("PID: %d, name: %s\n", pos->pid, pos->comm);
}

printf("\nlist node addresses:\n");
printf("  t1.tasks: %p\n", (void *)&t1.tasks);
printf("  t2.tasks: %p\n", (void *)&t2.tasks);
printf("  t3.tasks: %p\n", (void *)&t3.tasks);

---

← 上一回下一回 →