"The Linux kernel provides an implementation of a two-way linked list, which you can find in include / Linux / list. H. We start with a two-way linked list to introduce the data structure in the Linux kernel, because this is the most widely used data structure in the Linux kernel.
First, let's look at the main structures:
C
struct list_ head { struct list_ head *next, *prev;};
one
two
three
struct list_ head {
struct list_ head *next, *prev;
};
You can see that it is significantly different from the common structure implementation, such as the two-way linked list implementation used in glib.
C
struct GList { gpointer data; GList *next; GList *prev;};
one
two
three
four
five
struct GList {
gpointer data;
GList *next;
GList *prev;
};
Generally speaking, the linked list structure should include a pointer to data, but the linked list of Linux kernel does not include this implementation. So the first question: how does the linked list store data?. What the Linux kernel implements is an intrusive list, which does not contain data in the linked list structure, but only provides pointers for maintaining forward and backward access structures. This implementation makes the linked list data structure very general, because it does not need to pay attention to the specific data types maintained by the linked list.
For example:
C
struct nmi_ desc { spinlock_ t lock; struct list_ head head;};
one
two
three
four
struct nmi_ desc {
spinlock_ t lock;
struct list_ head head;
};
Next, let's look at some kernels that use lists_ A specific example of head. As mentioned earlier, many modules in the Linux kernel use list_ head。 Here, we take the partial implementation of miscellaneous character drivers in the kernel as an example. The driver API is in drivers / char / misc. C, which implements the drivers of simple hardware peripherals and virtual devices. This driver shares the major number:
C
#define MISC_ MAJOR 10
one
#define MISC_ MAJOR ten
Each equipment has its own secondary equipment number. See this column for details:
ls -l /dev | grep 10crw------- 1 root root 10, 235 Mar 21 12:01 autofsdrwxr-xr-x 10 root root 200 Mar 21 12:01 cpucrw------- 1 root root 10, 62 Mar 21 12:01 cpu_ dma_ latencycrw------- 1 root root 10, 203 Mar 21 12:01 cusedrwxr-xr-x 2 root root 100 Mar 21 12:01 dricrw-rw-rw- 1 root root 10, 229 Mar 21 12:01 fusecrw------- 1 root root 10, 228 Mar 21 12:01 hpetcrw------- 1 root root 10, 183 Mar 21 12:01 hwrngcrw-rw----+ 1 root kvm 10, 232 Mar 21 12:01 kvmcrw-rw---- 1 root disk 10, 237 Mar 21 12:01 loop-controlcrw------- 1 root root 10, 227 Mar 21 12:01 mcelogcrw------- 1 root root 10, 59 Mar 21 12:01 memory_ bandwidthcrw------- 1 root root 10, 61 Mar 21 12:01 network_ latencycrw------- 1 root root 10, 60 Mar 21 12:01 network_ throughputcrw-r----- 1 root kmem 10, 144 Mar 21 12:01 nvrambrw-rw---- 1 root disk 1, 10 Mar 21 12:01 ram10crw--w---- 1 root tty 4, 10 Mar 21 12:01 tty10crw-rw---- 1 root dialout 4, 74 Mar 21 12:01 ttyS10crw------- 1 root root 10, 63 Mar 21 12:01 vga_ arbitercrw------- 1 root root 10, 137 Mar 21 12:01 vhci
one
two
three
four
five
six
seven
eight
nine
ten
eleven
twelve
thirteen
fourteen
fifteen
sixteen
seventeen
eighteen
nineteen
twenty
twenty-one
ls -l /dev | grep 10
crw------- 1 root root 10, 235 Mar 21 12:01 autofs
drwxr-xr-x 10 root root 200 Mar 21 12:01 cpu
crw------- 1 root root 10, 62 Mar 21 12:01 cpu_ dma_ latency
crw------- 1 root root 10, 203 Mar 21 12:01 cuse
drwxr-xr-x 2 root root 100 Mar 21 12:01 dri
crw-rw-rw- 1 root root 10, 229 Mar 21 12:01 fuse
crw------- 1 root root 10, 228 Mar 21 12:01 hpet
crw------- 1 root root 10, 183 Mar 21 12:01 hwrng
crw-rw----+ 1 root kvm 10, 232 Mar 21 12:01 kvm
crw-rw---- 1 root disk 10, 237 Mar 21 12:01 loop-control
crw------- 1 root root 10, 227 Mar 21 12:01 mcelog
crw------- 1 root root 10, 59 Mar 21 12:01 memory_ bandwidth
crw------- 1 root root 10, 61 Mar 21 12:01 network_ latency
crw------- 1 root root 10, 60 Mar 21 12:01 network_ throughput
crw-r----- 1 root kmem 10, 144 Mar 21 12:01 nvram
brw-rw---- 1 root disk 1, 10 Mar 21 12:01 ram10
crw--w---- 1 root tty 4, 10 Mar 21 12:01 tty10
crw-rw---- 1 root dialout 4, 74 Mar 21 12:01 ttyS10
crw------- 1 root root 10, 63 Mar 21 12:01 vga_ arbiter
crw------- 1 root root 10, 137 Mar 21 12:01 vhci
Now let's take a look at how the device driver uses the linked list to maintain the device list. First, let's take a look at the struct definition of miscdevice:
C
struct miscdevice{ int minor; const char *name; const struct file_ operations *fops; struct list_ head list; struct device *parent; struct device *this_ device; const char *nodename; mode_ t mode;};
one
two
three
four
five
six
seven
eight
nine
ten
eleven
struct miscdevice
{
int minor;
const char *name;
const struct file_ operaTIons *fops;
struct list_ head list;
struct device *parent;
struct device *this_ device;
const char *nodename;
mode_ t mode;
};
You can see the fourth member list of miscdevice, which is the structure used to maintain the linked list of registered devices. At the beginning of the source code, we can see the following definitions:
C
staTIc LIST_ HEAD(misc_ list);
one
staTIc LIST_ HEAD(misc_ list);
Expand the definition macro to see that it is used to define the list_ Head type variable:
C
#define LIST_ HEAD(name) struct list_ head name = LIST_ HEAD_ INIT(name)
one
two
#define LIST_ HEAD(name)
struct list_ head name = LIST_ HEAD_ INIT(name)
LIST_ HEAD_ Init this macro is used to initialize the two-way pointer of the defined variable:
C
#define LIST_ HEAD_ INIT(name) { &(name), &(name) }
one
#define LIST_ HEAD_ INIT(name) { &(name), &(name) }
Now I can look at the function misc_ How register registers devices. The first is init_ LIST_ Head initializes the miscdevice - > list member variable:
C
INIT_ LIST_ HEAD(&misc->list);
one
INIT_ LIST_ HEAD(&misc->list);
This operation is similar to list_ HEAD_ Init macro consistency:
C
static inline void INIT_ LIST_ HEAD(struct list_ head *list){ list->next = list; list->prev = list;}
one
two
three
four
five
staTIc inline void INIT_ LIST_ HEAD(struct list_ head *list)
{
list->next = list;
list->prev = list;
}
Next, through the function device_ Create to create a device and add the device to the Misc device list:
C
list_ add(&misc->list, &misc_ list);
one
Our other product:
