Recorrer un sistema de archivos con restricciones

En esta entrada nos ponemos a resolver un problema que parece bastante sencillo: recorrer el árbol de directorios a partir de un directorio dado en un filesystem Linux e imprimir los nombres de los archivos contenidos en cada uno de ellos. Con este propósito empezaremos con un breve tratamiento de las herramientas del lenguaje C que facilitan el manejo de directorios y archivos. Como prueba usaremos un conjunto de directorios anidados y archivos con la estructura siguiente:

Ya veremos que la implementación más sencilla tiene algunas propiedades no deseables. Entonces jugueteamos el uso de la lógica formal (y en particular la lógica temporal lineal) para especificar propiedades potencialmente deseables de un algoritmo que recorre un árbol de directorios.

Manejo de directorios en C

En esta sección me pongo a describir el funcionamiento de los ordenes esenciales para el trabajo con directorios en C. En un sistema Linux cada archivo tiene un estructura asociada llamada stat que se puede obtener usando una de las llamadas de la familia stat. En el campo st_ino de esta estructura se encuentra el inodo de un archivo que sirve como un identificador único de este archivo que lo distingue de todos los otros archivos del sistema. Por eso nuestro programa imprimirá el inodo de cada archivo además de su nombre.

Vamos a elegir el orden lstat para recoger los datos de cada archivo debido a su tratamiento de enlaces simbólicos. Un enlace simbólico es más o menos un archivo que consiste en un puntero a otro archivo del sistema que se usa a veces para fingir que un solo archivo esté en dos directorios a la vez. Cuando el orden stat se topa con un enlace simbólico entonces devuelve los datos del archivo al que se refiere mientras que lstat devuelve los datos del enlace simbólico en sí. Si en nuestro árbol de directorios existe un enlace simbólico a otro archivo que reside en el árbol entonces el uso de stat provocaría que nuestro algoritmo imprima el mismo inodo dos veces.

Para el tratamiento de directorios hay dos estructuras que nos interesarán. El primero se llama DIR y almacena los datos de un directorio. No alisto sus distintos campos porque no tendremos que trabajar con ellos manualmente, pues los ordenes de manejo de directorios que veremos a continuación nos proporcionan los datos que necesitamos sin tener nosotros que hurgar en los campos del DIR. El segundo se llama dirent y almacena los datos de una sola entrada de un directorio. Tiene los campos siguientes:

struct dirent {
             ino_t      d_ino;
             __uint16_t d_reclen;
             __uint8_t  d_type;
             __uint8_t  d_namlen;
             char    d_name[255 + 1];
 };

Los campos que más nos interesan son d_ino que es el inodo del archivo indicado y d_name que es su nombre. (Cuando imprimimos los inodos de los archivos, recogeremos el inodo del stat en vez del dirent por motivos de modularidad, por si acaso en algún instante queremos imprimir más datos de cada archivo.)

A partir del nombre de un directorio (o su path relativo al directorio en el cual se ejecuta el programa) se puede abrirlo con la llamada opendir y ésta devolverá una estructura de tipo DIR. Entonces a partir del DIR se puede iterar por las entradas del directorio (cada una un dirent) usando el orden readdir que juega el papel de un iterador que devuelve un dirent distinto cada vez que se lo invoca y un puntero NULL cuando ya no quedan entradas nuevas. En concreto cada directorio abierto posee un puntero en la lista de entradas que se avanza con cada llamada a readdir. Una particularidad que tendremos que tener en cuenta a continuación es que el puntero no permanece después del cierre del directorio mediante la llamada closedir - entonces no es posible empezar a iterar por las entradas de un directorio, cerrar el directorio, volver a abrirlo más tarde y seguir iterando desde donde dejamos el puntero antes. Otro detalle importante es que no se puede garantizar nada acerca del orden en el cual aparecen las entradas.

Ejemplos y una solución recursiva

Para demostrar el funcionamiento de estas herramientas, aquí está una función con código comentado que sólo imprime las entradas de un directorio dado pero sin recorrer todo el árbol:

void recorrer_dir(char* dirnomb, void (*tramitar) ()) {
        DIR* direc;
        struct dirent* entrada;
        char* ent_path = malloc(PATH_MAX_LOCAL * sizeof(char));
        struct stat ent_stat;

        // Intentar abrir el directorio
        if ((direc = opendir(dirnomb)) == NULL) {
                printf("No se puede abrir el directorio.\n");
        }

        // Iterar por las entradas uno por uno
        while ((entrada = readdir(direc)) != NULL) {

                // Ignorar las entradas . y ..
                if (strcmp(entrada->d_name, ".") == 0) continue;
                if (strcmp(entrada->d_name, "..") == 0) continue;

                // Construir el path del archivo
                sprintf(ent_path, "%s/%s", dirnomb, entrada->d_name);

                // Intentar coger el stat del archivo
                if (lstat(ent_path, &ent_stat) == -1) {
                        printf("No se puede coger el stat de %s\n", ent_path);
                }

                // Tramitar el archivo de la manera especificada
                tramitar(ent_path, &ent_stat);
        }

        // Intentar cerrar el directorio.
        if (closedir(direc) != 0) {
                printf("No se puede cerrar el directorio.\n");
        }
}

Nota que esta función no imprime los nombres de los archivos dentro del directorio sino que los pasa como argumento a otra función tramitar que acepta recorrer_dir como argumento. Eso hacemos por motivos de modularidad. En el caso de que queremos imprimir datos distintos en formatos distintos de los archivos que encontramos, no hará falta modificar el código de la función recorrer_dir sino simplemente pasarle otra función para el argumento tramitar. La función que usaremos para este argumento es lo siguiente:

void imprimir_datos(char* path, struct stat* entrada_stat) {
        printf("inodo %ld: %s\n", entrada_stat->st_ino, path);
}

Así que si ejecutamos recorrer_dir("exterior", &imprimir_datos) en nuestra función main entonces recibiremos (por ejemplo) la salida siguiente:

inodo 475: exterior/exterior-archivo1
inodo 476: exterior/exterior-archivo2
inodo 477: exterior/interior1
inodo 478: exterior/interior2

Fíjate que a partir de este código nos hace falta muy poco para resolver el problema original, que era recorrer todo el árbol de directorios a partir de un directorio dado. Lo único que tenemos que añadir es una línea que detecta cuáles de los elementos del directorio son directorios en si y entonces lanzar otra llamada a la función dentro de si mismo para recorrer también las entradas de estos directorios. Para cumplir esto usaremos el macro S_ISDIR de C que detecta si un archivo es un directorio a partir del campo st_mode de su stat. Entonces si añadimos la línea siguiente inmediatamente después de la línea que invoca a tramitar:

if (S_ISDIR(ent_stat.st_mode)) recorrer_dir(ent_path, tramitar);

entonces ya está. Si lanzamos el programa de nuevo recibimos la salida siguiente:

inodo 475: exterior/exterior-archivo1
inodo 476: exterior/exterior-archivo2
inodo 477: exterior/interior1
inodo 483: exterior/interior1/interior1-archivo
inodo 478: exterior/interior2
inodo 479: exterior/interior2/interior2-archivo1
inodo 480: exterior/interior2/interior2-archivo2
inodo 481: exterior/interior2/interior3
inodo 482: exterior/interior2/interior3/interior3-archivo

Pues ya hemos resuelto el problema. Pero esta solución no me satisface por completo. Considera cuáles directorios quedarán abiertos o cerrados a la misma vez a lo largo de la ejecución del programa. Podemos visualizar cuáles directorios quedan abiertos en cuáles instantes usando el diagrama siguiente:

Fíjate que el directorio exterior quedará abierto casi desde el principio del programa hasta el final puesto que su apertura y su cierre ocurren en la primera llamada a recorrer_dir aunque no accedemos a sus entradas durante la mayoría de este intervalo. Por eso me parece "poco higiénico" dejar abierto el directorio exterior durante toda la ejecución de la función. De hecho podemos anotar el diagrama anterior para destacar los directorios abiertos que ya no necesitan estar abiertos, o sea directorios todos cuyos elementos ya han sido leídos:

Vemos también que el directorio interior2 permanece abierto por un ratito durante el que no estamos accediendo a sus entradas. Debido a la particularidad que notamos antes - que no es posible cerrar un directorio y reabrir lo más tarde de manera que la posición del puntero esté preservado - no veo cómo modificar la función recursiva para evitar los intervalos innecesariamente largos de apertura.

Propiedades formales del programa

Acabamos de ver que aunque resolvemos el problema fácilmente nuestra solución tiene algunas propiedades "no deseables". Ahora introducimos una manera de describir precisamente las propiedades de distintos algoritmos de recorrido del árbol de un directorio usando la lógica formal. Usaremos los variables para representar archivos y directorios, variables de entorno, variables locales del programa etcétera. También introducimos algunos predicados para describir el estado del programa en cualquier instante:

• $\mathtt{dir}(d)$ dice que $d$ es un archivo de tipo directorio.
• $\mathtt{elem}(a,d)$ dice que $d$ es un directorio y $a$ es un archivo que pertenece a $d$.
• $\mathtt{impreso}(a)$ dice que el orden más recientemente ejecutado es la impresión del nombre del archivo $a$ en la salida estándar.
• $\mathtt{abto}(a)$ dice que el archivo $a$ está abierto.

También podremos formar sentencias que involucran igualdades como $a_1 = a_2$, sentencia básica que indica que dos variables se refieren al mismo archivo. Por cierto podremos combinar varias sentencias sencillas en una más compleja usando operadores de la lógica proposicional y los cuantificadores. Por ejemplo, la sentencia $$\exists d ~ \exists d' ~ \mathtt{dir}(d)\land\mathtt{dir}(d')\land \big(\forall a ~ \neg\mathtt{es\_dir}(a) \to \mathtt{elem}(a,d)\land \mathtt{elem}(a,d')\big)$$ asevera que existen dos directorios tales que cada archivo que no sea directorio pertenece o al uno o al otro. (Por cierto, en un filesystem suficientemente complicado esta sentencia será falsa.) Claramente hay algunas propiedades de estos predicados que no son tautologías lógicas pero sí serán ciertas en cualquier filesystem que tratamos, por ejemplo:

• $\forall d ~ \forall a \mathtt{elem}(a,d)\to \mathtt{dir}(d)$ pues no tiene sentido decir que $a$ es elemento de $d$ a menos que $d$ es de tipo directorio.
• $\forall d ~ \forall d' ~ \forall a ~ \mathtt{elem}(a,d) \land \mathtt{elem}(a,d')\to (d = d')$ o sea ningún archivo pertenece a dos directorios distintos a la vez.
• $\forall a ~ \forall a' ~ \mathtt{impreso}(a)\land \mathtt{impreso}(a') \to (a=a')$ porque no es posible que dos archivos distintos sean el más recientemente impreso simultáneamente.

Todavía nos hace falta operadores para describir cómo cambia el estado del programa a lo largo de su ejecución. Para cumplir esto usaremos la lógica temporal lineal que proporciona los tres operadores siguientes. Si $\varphi$ es una sentencia que o es cierto o es falso en algún instante $t$, entonces decimos que:

• $\square\varphi$ asevera "siempre $\varphi$", o sea $\square\varphi$ es cierto en el instante $t$ ssi $\varphi$ es cierto en $t$ y en todos los momentos a partir de $t$
• $\diamondsuit\varphi$ asevera "eventualmente $\varphi$", o sea $\diamondsuit\varphi$ es cierto en el instante $t$ ssi $\varphi$ es cierto en algún momento a partir de $t$
• $\bigcirc\varphi$ asevera "$\varphi$ a continuación", o sea $\bigcirc\varphi$ es cierto en el instante $t$ ssi $\varphi$ es cierto en el instante $t+1$ (en el siguiente estado del programa)

Diremos que un programa satisface una sentencia $\varphi$ si esa sentencia es cierto desde su primer estado, o en el primer instante de su ejecución. (Si queremos aseverar que $\varphi$ es cierto en todos los estados de su ejecución equivale decir que el programa satisface $\square\varphi$.)

Hay que reconocer que este lenguaje realmente no será tan preciso como pretende ser a menos que definimos "rigurosamente" qué quiere decir un programa, un estado y otros conceptos fundamentales. Pero sí nos sirve para aumentar la claridad de las propiedades que queremos tratar de distintos algoritmos. Por ejemplo podemos usar este lenguaje para formular una especificación formal de lo que queremos cumplir con nuestro programa. En el lenguaje natural diríamos que queremos que imprima los nombres (y inodos) de todos los archivos contenido en el árbol del filesystem a partir de un directorio inicial dado. En el lenguaje formal podríamos intentar expresarlo así, si $d_0$ representa el directorio inicial:

Estas propiedades son las que consideramos esenciales para el funcionamiento correcto de nuestro programa. La propiedad $\varphi_1$ quiere decir que se imprime todos los elementos del directorio inicial eventualmente; y $\varphi_2$ quiere decir que para cada directorio cuyo nombre se imprime, también se imprime los nombres de todos los elementos de este directorio; y por fin $\varphi_3$ busca eliminar la posibilidad de impresión de archivos fuera del árbol bajo consideración exigiendo que para cada archivo cuyo nombre se imprime, o es elemento del $d_0$ o elemento de algún otro directorio cuyo nombre se imprime.

Aquí está otra lista de propiedades que podrían ser deseables aunque no esenciales al índole esencial del problema que intentamos resolver:

Las propiedades $\alpha_i$ tienen que ver con la terminación eventual del programa, las $\beta_i$ controlan la apertura de archivos y el orden relativo de operaciones de apertura y impresión, y las $\gamma_i$ restringen el orden en el cual se imprime los nombres de los archivos que encuentra. Probablemente querríamos que cualquiera implementación satisfazca $\alpha_1\land\alpha_2$ y si queremos gestionar la apertura de manera más "higiénica" (sea eso lo que signifique) podríamos exigir alguna combinación de los requisitos $\beta_i$ también. Fíjate que ninguna implementación puede satisfacer todos los requisitos $\alpha_i,\beta_i,\gamma_i$ porque algunos de ellos son incompatibles. Por ejemplo $\beta_3$ y $\beta_4$ no pueden ser implementados en el mismo programa porque $\beta_3$ dice que una vez que se imprime el nombre de un archivo no se vuelve a abrirlo otra vez, y $\beta_4$ dice que una vez que se abre un archivo no se vuelve a imprimir su nombre otra vez - pero si un archivo es un directorio entonces hay que o abrirlo primero o imprimir su nombre primero.

Solución con una cola

Ahora nos ponemos a diseñar una nueva función que cumple las especificaciones siguientes: $$\{\alpha_1,\alpha_2,\beta_1,\beta_2,\beta_4,\gamma_1,\gamma_3\}$$ Como notamos antes lo que más nos complica las cosas es el requisito de no tener dos directorios distintos abiertos a la vez porque no podemos mantener la posición del puntero después de cerrar el directorio. (Si lo pudieramos entonces lograríamos fácilmente lo que queremos con una modificación sencilla a la función recursiva en la cual cerraríamos el directorio actual antes de la llamada recursiva y lo abriríamos de nuevo después de ella.) En nuestra implementación nueva cambiaremos el uso de recursividad por el uso de una cola. En concreto nuestra cola consistirá de una lista enlazada cuyos nodos son estructuras del tipo siguiente:

struct dir_pend {
        struct dir_pend* despues;
        char path[PATH_MAX_LOCAL];
};

Cada nodo de la cola representará un directo impreso pero pendiente de apertura excepto el que se sitúa en la primera posición y éste será un directorio actualmente abierto. Nuestro algoritmo iterará por los elementos del directorio representado por el primer elemento de la cola hasta agotarlos y cada vez que encuentra un elemento del directorio actual que es directorio en sí, lo mete en la cola inmediatamente después del directorio actual. Por ejemplo, el desarrollo de la cola podría ser así:

Primero escribimos algunas funciones auxiliares para la gestión de la cola:

struct dir_pend* quitar_primero(struct dir_pend* primero) {
        struct dir_pend* despues = primero->despues;
        free(primero);
        return despues;
}

void insertar_despues(struct dir_pend* primero, struct dir_pend* nuevo) {
        nuevo->despues = primero->despues;
        primero->despues = nuevo;
}

struct dir_pend* new_dir_pend(char* path) {
        struct dir_pend* nuevo = malloc(sizeof(struct dir_pend));
        sprintf(nuevo->path, "%s", path);
        return nuevo;
}

Y aquí está la implementación:

int recorrer_higienico(char* dirnomb, void (*tramitar) ()) {
        DIR* dir_actual;
        struct dirent* entrada;
        struct dir_pend* cola;
        char* path_entrada = malloc(PATH_MAX_LOCAL * sizeof(char));
        char* path_total = malloc(PATH_MAX_LOCAL * sizeof(char));
        struct stat* ent_stat = malloc(sizeof(struct stat));

        // Inicializar la cola y abrir el directorio inicial
        cola = new_dir_pend(dirnomb);
        path_total = dirnomb;
        if ((dir_actual = opendir(dirnomb)) == NULL) {
                printf("No se puede abrir el directorio.\n");
                return 1;
        }

        // Paramos cuando ya no quedan entradas nuevas en el directorio
        //      ni directorios nuevos en la cola
        while ((entrada = readdir(dir_actual)) != NULL || cola->despues != NULL) {

                // Si alcanzamos el fin de un directorio, entonces lo quitamos
                //      de la cola, lo cerramos y abrimos el siguiente
                if (entrada == NULL) {
                        if (closedir(dir_actual) != 0) {
                                printf("No se puede cerrar el directorio %s.\n", path_total);
                                return 1;
                        }

                        cola = quitar_primero(cola);
                        path_total = cola->path;

                        while ((dir_actual = opendir(path_total)) == NULL) {
                                printf("No se puede abrir el directorio %s.\n", path_total);
                                if (cola->despues == NULL) break;
                                cola = quitar_primero(cola);
                                path_total = cola->path;
                        }

                        continue;
                }

                // Ignorar las entradas . y ..
                if (strcmp(entrada->d_name, ".") == 0) continue;
                if (strcmp(entrada->d_name, "..") == 0) continue;

                // Coger el stat del archivo indicado y tramitarlo
                sprintf(path_entrada, "%s/%s", path_total, entrada->d_name);
                if (lstat(path_entrada, ent_stat) == -1) {
                        printf("No se puede coger el stat de %s\n", path_entrada);
                }
                tramitar(path_entrada, ent_stat);

                // Si es un directorio, lo metemos en la cola
                if (S_ISDIR(ent_stat->st_mode)) {
                        insertar_despues(cola, new_dir_pend(path_entrada));
                }
        }

        free(cola);
}

Si probamos esta función con el mismo árbol de directorios que antes recibimos la salida siguiente:

inodo 475: exterior/exterior-archivo1
inodo 476: exterior/exterior-archivo2
inodo 477: exterior/interior1
inodo 478: exterior/interior2
inodo 479: exterior/interior2/interior2-archivo1
inodo 480: exterior/interior2/interior2-archivo2
inodo 481: exterior/interior2/interior3
inodo 482: exterior/interior2/interior3/interior3-archivo
inodo 483: exterior/interior1/interior1-archivo

Fíjate que el nombre de cada directorio aparece antes de los nombres de sus elementos, verificando que cumple la propiedad $\gamma_3$. También podemos dibujar el diagrama de apertura de directorios para este nuevo algoritmo para compararlo con el anterior:

Otros pensamientos

Hay mucho más que explorar aquí que no me he dado tiempo de tratar con detalle. En concreto se puede adaptar el algoritmo anterior para cumplir algunos otros subconjuntos de las propiedades alistadas con muy pocos cambios. Por ejemplo si tienes ganas de juguetear con C te desafío a modificar el algoritmo para que:

• cumple ${\alpha_1,\alpha_2,\beta_1,\beta_2,\gamma_2,\gamma_3}$
• cumple ${\alpha_1,\alpha_2,\beta_1,\beta_2,\beta_3,\gamma_1,\gamma_2,\gamma_5}$
• cumple ${\alpha_1,\alpha_2,\beta_1,\beta_2,\beta_3,\gamma_1,\gamma_3}$

El tercero me parece el más interesante y tal vez al probarlo te darás cuenta de que te hace falta otra estructura de datos...

También me pregunto si hay una manera (mecánica) de determinar cuáles subconjuntos de las propiedades $\alpha_i,\beta_i,\gamma_i$ son incompatibles. Ya hemos notado que ${\beta_3,\beta_4}$ son incompatibles y por esto cualquier subconjunto que contiene a $\beta_3$ y $\beta_4$ simultáneamente será imposible de satisfacer. Además ${\gamma_4,\gamma_5}$ es incompatible, y ${\gamma_1,\gamma_2,\gamma_3}$ es un conjunto de tres propiedades que es imposible de satisfacer aunque cada par de las tres propiedades puede ser satisfecho.