Table of Contents
Si vous êtes un ingénieur utilisateur Linux, vous êtes curieux de savoir comment fonctionne Linux. Je pense qu'il y a beaucoup de gens qui veulent un jour en savoir plus sur le noyau Linux.
Dans cet article, j'aimerais jeter un œil à la "structure list \ _head", un mur que les débutants qui cherchent à se familiariser avec le noyau Linux peuvent être perdus au début.
Cet article a également été publié sur mon blog https://achiwa912.github.io/.
Tout d'abord, récupérez le code source du noyau Linux.
Puisque le développement du noyau Linux est en cours depuis longtemps, le code cité dans les livres, etc. est déjà dépassé. C'est une bonne idée, vous voulez donc obtenir la dernière version. Clonons git le code source du noyau Linux et apportons-le.
git clone http://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git
Cela prend environ 20-30 minutes. Laissons-le et attendons.
~/git % git clone http://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git
Cloning into 'linux-stable'...
warning: redirecting to https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git/
remote: Enumerating objects: 1189260, done.
remote: Counting objects: 100% (1189260/1189260), done.
remote: Compressing objects: 100% (165947/165947), done.
remote: Total 8680156 (delta 1022459), reused 1186934 (delta 1020762), pack-reused 7490896
Receiving objects: 100% (8680156/8680156), 1.57 GiB | 3.01 MiB/s, done.
Resolving deltas: 100% (7328421/7328421), done.
Updating files: 100% (69365/69365), done.
warning: the following paths have collided (e.g. case-sensitive paths
on a case-insensitive filesystem) and only one from the same
colliding group is in the working tree:
'include/uapi/linux/netfilter/xt_CONNMARK.h'
'include/uapi/linux/netfilter/xt_connmark.h'
'include/uapi/linux/netfilter/xt_DSCP.h'
'include/uapi/linux/netfilter/xt_dscp.h'
'include/uapi/linux/netfilter/xt_MARK.h'
'include/uapi/linux/netfilter/xt_mark.h'
'include/uapi/linux/netfilter/xt_RATEEST.h'
'include/uapi/linux/netfilter/xt_rateest.h'
'include/uapi/linux/netfilter/xt_TCPMSS.h'
'include/uapi/linux/netfilter/xt_tcpmss.h'
'include/uapi/linux/netfilter_ipv4/ipt_ECN.h'
'include/uapi/linux/netfilter_ipv4/ipt_ecn.h'
'include/uapi/linux/netfilter_ipv4/ipt_TTL.h'
'include/uapi/linux/netfilter_ipv4/ipt_ttl.h'
'include/uapi/linux/netfilter_ipv6/ip6t_HL.h'
'include/uapi/linux/netfilter_ipv6/ip6t_hl.h'
'net/netfilter/xt_DSCP.c'
'net/netfilter/xt_dscp.c'
'net/netfilter/xt_HL.c'
'net/netfilter/xt_hl.c'
'net/netfilter/xt_RATEEST.c'
'net/netfilter/xt_rateest.c'
'net/netfilter/xt_TCPMSS.c'
'net/netfilter/xt_tcpmss.c'
'tools/memory-model/litmus-tests/Z6.0+pooncelock+poonceLock+pombonce.litmus'
'tools/memory-model/litmus-tests/Z6.0+pooncelock+pooncelock+pombonce.litmus'
Toutes nos félicitations. Vous disposez maintenant d'un ensemble complet de code source du noyau Linux. C'est étonnamment facile.
Le noyau Linux est énorme. Je ne sais pas où commencer. C'est généralement une bonne idée d'utiliser un livre sur le noyau Linux comme dans les références comme guide. Au fait, je suis intéressé par VFS. C'est inode ou superbloc. Cela peut sembler un peu trop soudain, mais jetons un coup d'œil à la structure de données du superbloc. C'était dans linux-stable / include / linux / fs.h.
struct super_block {
struct list_head s_list; /* Keep this first */
dev_t s_dev; /* search index; _not_ kdev_t */
unsigned char s_blocksize_bits;
unsigned long s_blocksize;
loff_t s_maxbytes; /* Max file size */
struct file_system_type *s_type;
const struct super_operations *s_op;
const struct dquot_operations *dq_op;
const struct quotactl_ops *s_qcop;
const struct export_operations *s_export_op;
unsigned long s_flags;
unsigned long s_iflags; /* internal SB_I_* flags */
unsigned long s_magic;
struct dentry *s_root;
struct rw_semaphore s_umount;
int s_count;
atomic_t s_active;
<snip>
C'est la structure de données du superbloc. Je ne sais pas ce qu'il y a dedans. .. .. Concentrez-vous sur la première ligne de la structure.
struct list_head s_list; /* Keep this first */
Cette. structure de la tête de liste. C'est un dur à cuire qui pousse les débutants comme moi qui veulent lire encore un peu le code source du noyau. De plus, beaucoup d'entre eux sortent. Dans cet article, j'aimerais jeter un coup d'œil à ce que cela signifie.
Le noyau Linux est écrit en langage C. Contrairement aux langages de programmation plus modernes, le langage C prend en charge de mauvaises structures de données et n'inclut pas de mécanisme orienté objet. Par exemple, la structure de liste en Python etc. (comme ['abc', 'def']) est très pratique, et il est trop facile d'écrire un programme, mais il n'y a pas de liste en langage C. De même, il n'y a pas de classes dans C. Il n'y a qu'une structure.
Les développeurs du noyau Linux implémentent ces structures de données modernes d'une manière unique. L'un d'eux est la structure d'en-tête de liste qui réalise la structure de liste.
Regardons maintenant la définition de la structure d'en-tête de liste. Il se trouve dans linux-stable / include / linux / types.h.
struct list_head {
struct list_head *next, *prev;
};
C'est si simple que vous ne pouvez pas le battre. Il contenait juste des pointeurs vers la même structure d'en-tête de liste que lui-même, en avant et en arrière. Je vois, c'est une liste chaînée bidirectionnelle. C'est le bon. (Strictement parlant, il s'agit d'une liste chaînée bidirectionnelle circulaire)
+------+ +------+------+------+ +------+-----+------+ +------+
| null | <-> | prev | ... | next | <-> | prev | ... | next | <-> | null |
+------+ +------+------+------+ +------+-----+------+ +------+
Non, veuillez patienter un moment. Il n'y a aucun point dans une liste même si elle ne contient que les pointeurs avant et après. Si les données de chaque nœud qui compose la liste ne sont pas incluses. Par exemple, si vous avez un inode dans une liste chaînée, l'inode doit avoir beaucoup de données propres à l'inode. Nom de fichier, propriétaire, autorisations, etc. Dans la figure ci-dessus, c'est la partie de ...
En fait, la structure d'en-tête de liste est pratique qui vous permet de relier la structure parent intégrée en l'incorporant dans une autre structure. Hou la la! C'est un changement de pensée.
À propos, la structure de superbloc avait une structure d'en-tête de liste en tant que membre.
struct super_block {
struct list_head s_list; /* Keep this first */
dev_t s_dev; /* search index; _not_ kdev_t */
unsigned char s_blocksize_bits;
<snip>
En faisant cela, le superbloc devient un nœud de liste chaînée.
De plus, en incorporant plusieurs structures list \ _head, il est possible de s'inscrire à plusieurs listes liées en même temps. En regardant simplement la définition de la structure, vous pouvez voir ce qu'elle est et ce qu'elle est dans la liste chaînée (car elle contient des commentaires). Cela ne peut pas être imité dans les liens Python.
Je comprends le but de la réalisation d'une liste chaînée en langage C qui n'a pas de liste, mais un problème demeure. La structure de tête de poignet relie uniquement les mêmes structures de tête de liste, mais ce que je veux vraiment, c'est un pointeur vers la structure parente dans laquelle elle est intégrée. Je souhaite lier la structure parente.
Une fonction est définie pour faire cela.
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_head within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
La fonction list \ _entry (). Ces trois arguments sont
--ptr: pointeur vers cette liste \ _head structure --type: Le type de structure parente qui incorpore la liste \ _head (super \ _block dans l'exemple ci-dessus) --member: Le nom du membre de cette structure list \ _head dans la structure parent (s \ _list dans l'exemple ci-dessus)
Et renvoie un pointeur vers la structure parente.
C'était bien, c'était bien. Cependant, je suis curieux de connaître la définition de la fonction list \ _entry (). Qu'est-ce que container \ _of ()? Quand j'ai cherché avec grep, il y avait une définition dans linux-stable / include / linux / kernel.h.
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) && \
!__same_type(*(ptr), void), \
"pointer type mismatch in container_of()"); \
((type *)(__mptr - offsetof(type, member))); })
Extrayez uniquement les points.
#define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
((type *)(__mptr - offsetof(type, member))); })
Tout d'abord, le pointeur vers void \ _ \ _mptr est attribué en convertissant le pointeur ptr vers la structure list \ _head vers le pointeur vers void. Vous ne pouvez pas l'utiliser comme pointeur vers la structure list \ _head.
Dans la ligne suivante, \ _ \ _mptr semble être compensé par offsetof (type, membre) minutes. offsetof (type, membre) est le décalage de la liste de structure de membre \ _head s \ _list dans la structure super \ _block dans l'exemple ci-dessus. En d'autres termes, il se convertissait en un pointeur vers la structure parent super \ _block. Et je lance ceci sur un pointeur vers une structure super \ _block.
Résumé,
C'était ça.
Notez que le conteneur \ _of a été défini comme suit dans le développement du noyau Linux dans la référence.
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
Quand j'ai vu ça, je m'inquiétais pour "((type \ *) 0) -> membre? Qu'est-ce que ça fait ???", qui a été la motivation pour écrire cet article. Cependant, dans la dernière source, c'était un peu plus facile à comprendre.
S'il existe une structure dans laquelle la structure list \ _head est intégrée dans la structure de données définie dans le noyau Linux, vous savez qu'elle est incluse dans une liste chaînée. Si vous lisez les commentaires dans la source, vous trouverez généralement ce qu'est la liste liée.
Vous pouvez utiliser la fonction list \ _entry () pour convertir un pointeur vers la structure list \ _head en un pointeur vers la structure parent dans laquelle il est incorporé. Ensuite, j'ai jeté un œil à l'implémentation de list \ _entry () --contaier \ _of () dans le noyau Linux.
Recommended Posts