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