La réponse à cette partie comportera :
Les fonctions récrites devront respecter strictement la description des fonctions originales (prototypes et valeurs retournées, y compris en cas d'erreur).
struct dirent { ino_t d_ino; off_t d_off; unsigned short d_reclen; char d_name[1]; }; typedef struct{ int dd_fd; /* file descriptor */ int dd_loc; /* offset in block */ int dd_size; /* amount of valid data */ char *dd_buf; /* directory block */ } DIR; /* stream data from opendir() */Voici le programme utilisé pour étudier expérimentalement la stratégie d'allocation mémoire des fonctions opendir() et readdir(). Ce programme comporte trois options :
chemin
, afin de ne pas perturber
l'observation de la stratégie d'allocation mémoire
des fonctions opendir() et readdir().
/* Parcours, éventuellement récursif, de répertoires, avec options pour étude de l'allocation mémoire. */ #include <dirent.h> #include <limits.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <sys/stat.h> static char chemin [PATH_MAX]; /* PATH_MAX défini dans limits.h */ static int recursif = 0, verbose = 0; static void afficher (struct dirent *entree); static void afficher_dir (DIR *rep); static void chemincat (char *s); static int isdir (); static void message (char *fonction, char *rep); void catalogue () { int i = 0; DIR *rep; struct dirent *ligne; rep = opendir (chemin); if (!rep) { message ("opendir", chemin); return; } else if (verbose > 0) { printf ("\nOpendir(%s)\n", chemin); afficher_dir (rep); } while ( (ligne = readdir (rep) ) != NULL ) { if (verbose >= 0) { afficher (ligne); if (verbose > 0) afficher_dir (rep); } if (recursif && ++i > 2) { /* sauter . et .. */ int l = strlen (chemin); chemincat (ligne->d_name); if (isdir () > 0) catalogue (); chemin [l] = '\0'; } } closedir (rep); if (verbose > 0) printf ("Closedir(%s)\n\n", chemin); } static void afficher (struct dirent *entree){ if (verbose > 0) printf ("%u: d_off %d, d_reclen %d, ", entree, entree->d_off, entree->d_reclen); printf ("inode %6u, %s\n", entree->d_ino, entree->d_name); } static void afficher_dir (DIR *rep) { printf ("%u: dd_loc %d, dd_size %d, dd_buf %u\n", rep, rep->dd_loc, rep->dd_size, rep->dd_buf); } static int isdir () { struct stat attribut; int code; code = stat (chemin, &attribut); if (code == -1) { message ("stat", chemin); return code; } return S_ISDIR (attribut.st_mode); /* (st_mode & S_IFMT) == S_IFDIR */ } static void chemincat (char *s) { int a = strlen (chemin), b = strlen (s); if (b == 0) return; if (a + b + 1 < PATH_MAX) { chemin [a++] = '/'; strcpy (chemin + a, s); } } static void message (char *fonction, char *rep) { int n = strlen (fonction) + strlen (rep) + 8; char *buf = (char *) malloc (n); sprintf (buf, "%s(%s)", fonction, rep); perror (buf); } main (int argc, char **argv) { char option; while ((option = getopt(argc, argv, "rsv")) != EOF) switch (option) { case 'r': recursif = 1; break; case 's': verbose = -1; /* pour exécution avec truss */ break; case 'v': verbose = 1; break; } if (optind < argc) strcpy (chemin, argv [optind]); else strcpy (chemin, "."); if (verbose > 0) printf ("sizeof (struct dirent): %d (d_ino %d, d_off %d, d_reclen %d)\n", sizeof (struct dirent), sizeof (ino_t), sizeof (off_t), sizeof (short) ); catalogue (); }
aliboron% dir -v sizeof (struct dirent): 12 (d_ino 4, d_off 4, d_reclen 2) Opendir(.) 136416: dd_loc 0, dd_size 0, dd_buf 136432 136432: d_off 12, d_reclen 12, inode 200129, . 136416: dd_loc 0, dd_size 488, dd_buf 136432 136444: d_off 24, d_reclen 16, inode 83072, .. 136416: dd_loc 12, dd_size 488, dd_buf 136432 136460: d_off 44, d_reclen 20, inode 200132, chemin 136416: dd_loc 28, dd_size 488, dd_buf 136432 136480: d_off 64, d_reclen 20, inode 200134, Makefile 136416: dd_loc 48, dd_size 488, dd_buf 136432 136500: d_off 88, d_reclen 24, inode 200135, catalogue.c 136416: dd_loc 68, dd_size 488, dd_buf 136432 136524: d_off 104, d_reclen 16, inode 200203, Memo 136416: dd_loc 92, dd_size 488, dd_buf 136432 136540: d_off 120, d_reclen 16, inode 200137, elf.c 136416: dd_loc 108, dd_size 488, dd_buf 136432 136556: d_off 132, d_reclen 16, inode 200138, elf 136416: dd_loc 124, dd_size 488, dd_buf 136432 136572: d_off 148, d_reclen 16, inode 200139, elf.o 136416: dd_loc 140, dd_size 488, dd_buf 136432 136588: d_off 164, d_reclen 20, inode 200347, acces.c 136416: dd_loc 156, dd_size 488, dd_buf 136432 136608: d_off 188, d_reclen 24, inode 200348, simple_chemin 136416: dd_loc 176, dd_size 488, dd_buf 136432 136632: d_off 208, d_reclen 20, inode 200349, chemin.c 136416: dd_loc 200, dd_size 488, dd_buf 136432 136652: d_off 228, d_reclen 20, inode 200350, catalogue 136416: dd_loc 220, dd_size 488, dd_buf 136432 136672: d_off 244, d_reclen 16, inode 200351, dir.c 136416: dd_loc 240, dd_size 488, dd_buf 136432 136688: d_off 256, d_reclen 16, inode 200352, dir 136416: dd_loc 256, dd_size 488, dd_buf 136432 136704: d_off 280, d_reclen 28, inode 200353, chemin.session 136416: dd_loc 272, dd_size 488, dd_buf 136432 136732: d_off 304, d_reclen 28, inode 200371, chemin.session% 136416: dd_loc 300, dd_size 488, dd_buf 136432 136760: d_off 332, d_reclen 24, inode 200378, catalogue.c% 136416: dd_loc 328, dd_size 488, dd_buf 136432 136784: d_off 356, d_reclen 28, inode 419386, simple_chemin.c 136416: dd_loc 352, dd_size 488, dd_buf 136432 136812: d_off 368, d_reclen 16, inode 275833, tmp 136416: dd_loc 380, dd_size 488, dd_buf 136432 136828: d_off 380, d_reclen 16, inode 419324, bak 136416: dd_loc 396, dd_size 488, dd_buf 136432 136844: d_off 412, d_reclen 32, inode 200373, simple_chemin.session 136416: dd_loc 412, dd_size 488, dd_buf 136432 136876: d_off 428, d_reclen 20, inode 200379, dir.c% 136416: dd_loc 444, dd_size 488, dd_buf 136432 136896: d_off 512, d_reclen 24, inode 200380, dir.session 136416: dd_loc 464, dd_size 488, dd_buf 136432 Closedir(.)Commentaires :
Noter que la commande truss est peu utile ici :
les allocations de mémoire sont effectuées par la fonction
malloc(), qui effectue rarement un appel-système brk() ;
la présence, dans la trace suivante, d'un seul brk(),
ne permet pas de conclure à un seul appel de malloc().
aliboron% truss dir
execve("./dir", 0xDFFFFCF0, 0xDFFFFCFC) argc = 2
open("/usr/lib/libelf.so.1", O_RDONLY) = 3
fstat(3, 0xDFFFF960) = 0
mmap(0x00000000, 4096, PROT_READ, MAP_SHARED, 3, 0) = 0xDF7C0000
etc...
open(".", O_RDONLY|O_NDELAY) = 3
fcntl(3, F_SETFD, 0x00000001) = 0
fstat(3, 0xDFFFFB18) = 0
brk(0x000214D8) = 0
brk(0x000234D8) = 0
getdents(3, 0x000214F0, 1048) = 488
sigfillset(0xDF784060) = 0
ioctl(1, TCGETA, 0xDFFFF174) = 0
ioctl(1, TCGETA, 0xDFFFF174) = 0
inode 200129, .
write(1, " i n o d e 2 0 0 1 2 9".., 16) = 16
inode 83072, ..
write(1, " i n o d e 8 3 0 7 2".., 17) = 17
inode 200132, chemin
write(1, " i n o d e 2 0 0 1 3 2".., 21) = 21
inode 200134, Makefile
etc...
write(1, " i n o d e 2 0 0 3 7 9".., 21) = 21
inode 200380, dir.session
write(1, " i n o d e 2 0 0 3 8 0".., 26) = 26
getdents(3, 0x000214F0, 1048) = 0
close(3) = 0
lseek(0, 0, SEEK_CUR) = 13529
_exit(1)
On note que l'adresse du buffer, fournie en paramètre à
getdents(), vaut 214F0 en hexadécimal, soit 136432
en décimal, ce qui est bien la valeur du champ dd_buf.
Il reste à étudier deux situations :
aliboron% dir -rv .. sizeof (struct dirent): 12 (d_ino 4, d_off 4, d_reclen 2) Opendir(..) 136416: dd_loc 0, dd_size 0, dd_buf 136432 136432: d_off 12, d_reclen 12, inode 83072, . 136416: dd_loc 0, dd_size 908, dd_buf 136432 136444: d_off 24, d_reclen 16, inode 3776, .. 136416: dd_loc 12, dd_size 908, dd_buf 136432 136460: d_off 44, d_reclen 24, inode 83073, .Xdefaults 136416: dd_loc 28, dd_size 908, dd_buf 136432 etc ... 136568: d_off 132, d_reclen 16, inode 109504, elf 136416: dd_loc 136, dd_size 908, dd_buf 136432 Opendir(../elf) 137488: dd_loc 0, dd_size 0, dd_buf 137504 137504: d_off 12, d_reclen 12, inode 109504, . 137488: dd_loc 0, dd_size 168, dd_buf 137504 137516: d_off 24, d_reclen 16, inode 83072, .. 137488: dd_loc 12, dd_size 168, dd_buf 137504 137532: d_off 44, d_reclen 20, inode 109506, reloc1.c 137488: dd_loc 28, dd_size 168, dd_buf 137504 137552: d_off 64, d_reclen 20, inode 109508, reloc2.c 137488: dd_loc 48, dd_size 168, dd_buf 137504 etc... 137652: d_off 512, d_reclen 20, inode 109514, session 137488: dd_loc 148, dd_size 168, dd_buf 137504 Closedir(../elf) 136584: d_off 148, d_reclen 20, inode 83378, vfstab 136416: dd_loc 152, dd_size 908, dd_buf 136432 136604: d_off 164, d_reclen 20, inode 83379, mnttab 136416: dd_loc 172, dd_size 908, dd_buf 136432 etc... 136844: d_off 364, d_reclen 12, inode 200129, c 136416: dd_loc 412, dd_size 908, dd_buf 136432 Opendir(../c) 137488: dd_loc 0, dd_size 0, dd_buf 137504 137504: d_off 12, d_reclen 12, inode 200129, . 137488: dd_loc 0, dd_size 488, dd_buf 137504 137516: d_off 24, d_reclen 16, inode 83072, .. 137488: dd_loc 12, dd_size 488, dd_buf 137504 137532: d_off 44, d_reclen 20, inode 200132, chemin 137488: dd_loc 28, dd_size 488, dd_buf 137504 137552: d_off 64, d_reclen 20, inode 200134, Makefile 137488: dd_loc 48, dd_size 488, dd_buf 137504 etc... 137884: d_off 368, d_reclen 16, inode 275833, tmp 137488: dd_loc 380, dd_size 488, dd_buf 137504 Opendir(../c/tmp) 138560: dd_loc 0, dd_size 0, dd_buf 138576 138576: d_off 12, d_reclen 12, inode 275833, . 138560: dd_loc 0, dd_size 28, dd_buf 138576 138588: d_off 512, d_reclen 16, inode 200129, .. 138560: dd_loc 12, dd_size 28, dd_buf 138576 Closedir(../c/tmp) 137900: d_off 380, d_reclen 16, inode 419324, bak 137488: dd_loc 396, dd_size 488, dd_buf 137504 Opendir(../c/bak) 138560: dd_loc 0, dd_size 0, dd_buf 138576 138576: d_off 12, d_reclen 12, inode 419324, . 138560: dd_loc 0, dd_size 56, dd_buf 138576 138588: d_off 24, d_reclen 16, inode 200129, .. 138560: dd_loc 12, dd_size 56, dd_buf 138576 138604: d_off 512, d_reclen 28, inode 200354, chemin.session 138560: dd_loc 28, dd_size 56, dd_buf 138576 Closedir(../c/bak) 137916: d_off 412, d_reclen 32, inode 200373, simple_chemin.session 137488: dd_loc 412, dd_size 488, dd_buf 137504 137948: d_off 428, d_reclen 20, inode 200379, dir.c% 137488: dd_loc 444, dd_size 488, dd_buf 137504 137968: d_off 512, d_reclen 24, inode 200380, dir.session 137488: dd_loc 464, dd_size 488, dd_buf 137504 Closedir(../c) 136856: d_off 384, d_reclen 20, inode 83089, .xinitrc% 136416: dd_loc 424, dd_size 908, dd_buf 136432 etc ... 137272: d_off 792, d_reclen 20, inode 83417, .forward 136416: dd_loc 840, dd_size 908, dd_buf 136432 137292: d_off 812, d_reclen 20, inode 83418, .forward% 136416: dd_loc 860, dd_size 908, dd_buf 136432 137312: d_off 1024, d_reclen 28, inode 83402, devoir_unix.dvi 136416: dd_loc 880, dd_size 908, dd_buf 136432 Closedir(..)On constate que les buffers sont alloués successivement à des adresses (en gras ci-dessus) espacées de 1072 octets. D'autre part la valeur du champ dd_buf est toujours égale à 16 + adresse de la structure DIR : ces 16 octets correspondent aux quatre champs entiers de la structure DIR. Le fichier
dirent.h
contient la taille DIRBUF = 1048
du buffer alloué aux entrées
du répertoire, et on retrouve cette taille comme paramètre
de l'appel-système getdents(). Les 8 octets restants
sont utilisés par malloc(),
pour le chaînage et l'identification des blocs alloués.
La fonction closedir() libère la mémoire allouée
par opendir(), et celle-ci est réutilisée pour parcourir
un répertoire de même hauteur hiérarchique que le précédent
(par exemple ../elf
et ../c
ci-dessus).
aliboron% cat tmp/creer #!/bin/sh for i do >1234567890123456.$i; done for i do >2234567890123456.$i; done for i do >3234567890123456.$i; done for i do >4234567890123456.$i; done aliboron% creer a b c d e f g h i j k l m n o p aliboron%La trace suivante (extraits) permet alors de conclure que les enregistrements (entrées de répertoires) sont stockés de façon circulaire dans le buffer ; lorsque ce dernier est plein, les enregistrements suivants écrasent ceux du début du buffer ; ce qui explique l'avertissement qui figure dans la page de manuel de readdir :
aliboron% dir -v tmp Opendir(tmp) 136416: dd_loc 0, dd_size 0, dd_buf 136432 136432: d_off 12, d_reclen 12, inode 275833, . 136416: dd_loc 0, dd_size 1024, dd_buf 136432 136444: d_off 24, d_reclen 16, inode 200129, .. 136416: dd_loc 12, dd_size 1024, dd_buf 136432 136460: d_off 40, d_reclen 16, inode 275834, creer 136416: dd_loc 28, dd_size 1024, dd_buf 136432 136476: d_off 56, d_reclen 20, inode 275835, creer% 136416: dd_loc 44, dd_size 1024, dd_buf 136432 136496: d_off 84, d_reclen 32, inode 275836, 1234567890123456.a 136416: dd_loc 64, dd_size 1024, dd_buf 136432 136528: d_off 112, d_reclen 32, inode 275837, 1234567890123456.b 136416: dd_loc 96, dd_size 1024, dd_buf 136432 136560: d_off 140, d_reclen 32, inode 275838, 1234567890123456.c 136416: dd_loc 128, dd_size 1024, dd_buf 136432 etc... 137392: d_off 876, d_reclen 32, inode 276043, 2234567890123456.m 136416: dd_loc 960, dd_size 1024, dd_buf 136432 137424: d_off 904, d_reclen 32, inode 276044, 2234567890123456.n 136416: dd_loc 992, dd_size 1024, dd_buf 136432 136432: d_off 932, d_reclen 32, inode 276045, 2234567890123456.o 136416: dd_loc 0, dd_size 736, dd_buf 136432 136464: d_off 960, d_reclen 32, inode 276046, 2234567890123456.p 136416: dd_loc 32, dd_size 736, dd_buf 136432 136496: d_off 988, d_reclen 32, inode 276047, 3234567890123456.a 136416: dd_loc 64, dd_size 736, dd_buf 136432 etc... 137104: d_off 1536, d_reclen 32, inode 276066, 4234567890123456.d 136416: dd_loc 672, dd_size 736, dd_buf 136432 137136: d_off 1564, d_reclen 32, inode 276067, 4234567890123456.e 136416: dd_loc 704, dd_size 736, dd_buf 136432 136432: d_off 1592, d_reclen 32, inode 276068, 4234567890123456.f 136416: dd_loc 0, dd_size 352, dd_buf 136432 136464: d_off 1620, d_reclen 32, inode 276069, 4234567890123456.g 136416: dd_loc 32, dd_size 352, dd_buf 136432 etc... 136720: d_off 1844, d_reclen 32, inode 276077, 4234567890123456.o 136416: dd_loc 288, dd_size 352, dd_buf 136432 136752: d_off 2048, d_reclen 32, inode 276078, 4234567890123456.p 136416: dd_loc 320, dd_size 352, dd_buf 136432 Closedir(tmp)On remarque aussi sur cet exemple les changements de valeur du champ dd_size ; ces valeurs sont retournées par getdents(), comme le montre la trace suivante :
aliboron% truss dir -s tmp execve("./dir", 0xDFFFFCE8, 0xDFFFFCF8) argc = 3 open("/usr/lib/libelf.so.1", O_RDONLY) = 3 fstat(3, 0xDFFFF958) = 0 mmap(0x00000000, 4096, PROT_READ, MAP_SHARED, 3, 0) = 0xDF7C0000 etc... open("tmp", O_RDONLY|O_NDELAY) = 3 fcntl(3, F_SETFD, 0x00000001) = 0 fstat(3, 0xDFFFFB08) = 0 brk(0x000214D8) = 0 brk(0x000234D8) = 0 getdents(3, 0x000214F0, 1048) = 1024 getdents(3, 0x000214F0, 1048) = 736 getdents(3, 0x000214F0, 1048) = 352 getdents(3, 0x000214F0, 1048) = 0 close(3) = 0 lseek(0, 0, SEEK_CUR) = 108228 _exit(3)Les entrées de répertoire ne sont pas chargées une à une par la fonction readdir() ; elles sont chargées par paquets, par l'appel-système getdents(), substitut de read() pour lire les répertoires indépendamment du système de fichiers. La comparaison des champs d_off et dd_size montre que :
Note : la raison pour laquelle la seconde exécution de getdents() ne lit que 660 octets, reste mystérieuse.
entree
pour les
entrées physiques, et dirent
pour les entrées
virtuelles, sont de taille variable ; donc l'arithmétique
sur les pointeurs doit utiliser des pointeurs d'octets.
C'est pourquoi, dans le code ci-dessous,
à chaque pointeur d'enregistrement p
,
correspond un pointeur de caractères nommé cp
.
/* Entrée physique de répertoire (UFS) */ struct entree { int inode; short taille, /* taille de l'entrée (jusqu'à l'entrée valide suivante) */ longueur; /* longueur du nom */ char nom[1]; }; DIR *ouvrir_repertoire (const char *nom) { DIR *rep; char *crep; /* pour l'arithmétique sur le pointeur rep */ int fd; rep = (DIR *) malloc (sizeof (DIR) + DIRBUF); if (!rep) return NULL; crep = (char *) rep; fd = open (nom, O_RDONLY); if (fd < 0) return NULL; rep->dd_fd = fd; rep->dd_loc = 0; rep->dd_size = 0; rep->dd_buf = crep + sizeof (DIR); return rep; } int fermer_repertoire (DIR *rep) { int ok = close (rep->dd_fd); free (rep); return ok; } /* charger_entrees() imite getdents(), et charge dans 'buf' des entrées du répertoire de descripteur 'fd', après conversion au format dirent ; 'buf' est de taille 'max', et la fonction retourne la taille utile de 'buf', c'est à dire la somme des tailles des entrées effectivement chargées. */ int charger_entrees (int fd, struct dirent *buf, int max) { struct dirent *b; struct entree *source, *s; char *cb, *cs; /* pour l'arithmétique sur les pointeurs b, s */ int k, n, offset, /* position du curseur de lecture */ reclen, /* taille d'un enregistrement de type dirent */ base = 1 + sizeof (ino_t) + sizeof (off_t) + sizeof (short), size = 0; /* taille utile de buf */ source = (struct entree *) malloc (max); if (!source) return -1; offset = lseek (fd, 0, SEEK_CUR); n = read (fd, source, max); if (n < 0) return n; cb = (char *) buf; cs = (char *) source; /* k désigne l'adresse relative d'une entrée dans le buffer source */ for (k = 0; k < n; k += s->taille) { s = (struct entree *) cs; b = (struct dirent *) cb; reclen = arrondi (base + s->longueur); if (size + reclen > max) { /* buf est plein; repositionner le curseur de lecture avant de sortir */ lseek (fd, offset + k, SEEK_SET); break; } else size += reclen; b->d_ino = s->inode; b->d_off = offset + k + s->taille; b->d_reclen = reclen; strcpy (b->d_name, s->nom); cs += s->taille; cb += reclen; } free (source); return size; } struct dirent *lire_repertoire (DIR *rep) { struct dirent *e; char *ce; /* pour l'arithmétique sur le pointeur e */ int loc = 0; /* adresse relative dans le buffer */ ce = rep ->dd_buf; if (rep->dd_size > 0) { ce += rep->dd_loc; /* début de l'enregistrement courant */ e = (struct dirent *) ce; loc = rep->dd_loc + e->d_reclen; /* enregistrement suivant */ } if (loc < rep->dd_size) { /* en particulier rep->dd_size > 0 */ rep->dd_loc = loc; ce += e->d_reclen; return (struct dirent *) ce; } /* (re)charger le buffer */ e = (struct dirent *) rep ->dd_buf; rep->dd_size = charger_entrees (rep->dd_fd, e, DIRBUF); rep->dd_loc = 0; if (rep->dd_size > 0) return e; else return NULL; }
catalogue
,
est le même que celui utilisé pour l'enquête,
nommé dir
, au nom des fonctions près.
Les deux programmes donnent des résultats identiques,
en particulier sur de "grands" répertoires.
aliboron% dir -rv | wc 574 4134 28643 aliboron% catalogue -rv | wc 574 4134 28793