Informe de investigación de Watcher

Glosario

Thread safe: Programa multihilo que cumple ciertas propiedades, como exclusión mutua, acceso compartido y consistencia de datos
Reentrante: Un programa o función es reentrante cuando puede ser ejecutado con seguridad de forma concurrente, es decir, puede ser llamado otra vez cuando está ejecutándose y funcionar correctamente en todas las llamadas
Evento de cambio: cualquier suceso de los notificados por inotify (
SGBD: Sistema de Gestión de Bases de Datos. En general, cualquier aplicación de bases de datos como por ejemplo mysql.

Descripción del módulo watcher

El módulo watcher se encarga de la monitorización de cambios de HD Lorean, así como de la especificación y control de los ficheros que se encuentran bajo monitorización.

Las funcionalidades más representativas de watcher son:

  • Informar de los cambios ocurridos en un fichero/directorio monitorizado.
  • Extraer de la configuración las reglas que el usuario especifica sobre los ficheros que quiere vigilar y localizarlos en el sistema.
  • Garantizar la concurrencia en las notificaciones de cambios y en el acceso a las estructuras que mantienen los ficheros vigilados.
  • Garantizar checkpoints a partir de los que el sistema puede recuperarse ante un imprevisto.

Abstracción al problema

El objetivo de watcher es obtener de la configuración los archivos a monitorizar, crear estructuras thread safe para consultar y modificar dichos archivos vigilados, recopilar los cambios que suceden en los ficheros vigilados y mantenerlos a salvo de una caída del sistema, así como notificar a snapshot-core para que se escriban a disco.

Abstracción a la solución

Una vez definidas las reglas con las que el usuario introducirá los archivos que desea vigilar, se deben encontrar métodos que resuelvan los siguientes problemas:

  1. Extraer de las reglas introducidas por el usuario un listado de archivos a vigilar.
  2. Conseguir monitorizar todos los cambios en dichos archivos sin sobrecargar el sistema.
  3. Garantizar la exclusión mutua de las distintas partes de la aplicación en el acceso a las estructuras de archivos vigilados y de eventos de cambio.
  4. Garantizar la recuperación de HD Lorean en caso de caída o corte.

Las soluciones ideales a los distintos problemas serían las siguientes:

  1. Extraer de las reglas introducidas por el usuario un listado de archivos a vigilar.
    1. A la entrada llega la ruta del fichero de configuración
    2. Localizar patrones en las reglas del usuario aplicables a los archivos reales del sistema.
    3. Generar una estructura dinámica que los almacene y permita las operaciones básicas sobre ella.
  2. Conseguir monitorizar todos los cambios en dichos archivos sin sobrecargar el sistema.
    1. A la entrada llega el listado de ficheros a vigilar.
    2. Esperar distintos eventos sobre el conjunto de ficheros vigilados.
    3. Notificar de los eventos.
  3. Garantizar la exclusión mutua de las distintas partes de la aplicación en el acceso a las estructuras de archivos vigilados y de eventos de cambio.
    1. Se solicita el acceso concurrente a las estructuras del módulo.
    2. Determinar quién solicitó antes el acceso y evitar que el resto de solicitudes progresen hasta que la actual finalice.
  4. Garantizar la recuperación de HD Lorean en caso de caída o corte.
    1. A la entrada llega la notificación de un evento de cambio.
    2. Escribir rápidamente los rasgos esenciales del cambio en estructuras de inserción eficiente y atómica para evitar corrupción o pérdida de información.
    3. Manejar las peticiones de acceso a la estructura de recuperación en caso de caída.

Búsqueda de patrones en archivos de configuración

Permitir al usuario una mayor flexibilidad y potencia a la hora de describir las reglas que designan los archivos a monitorizar (exclusión de tipos de fichero o patrones de nombres), complica la labor de obtener la información del fichero de configuración, localizando los archivos en el árbol de directorios del sistema. Para solventar este problema, la solución más escalable y completa es el uso de las bien conocidas expresiones regulares.
La inclusión de expresiones regulares en la aplicación, más allá del módulo watcher, permite validar la configuración y los parámetros introducidos por el usuario de manera sencilla.

Monitorización de cambios en archivos

Para la monitorización de cambios se deben tener en cuenta la lista de directorios y ficheros a monitorizar, así como la "lista negra"(ficheros que no deseamos vigilar).
Con esta información se prepararán las estructuras de datos pertinentes para poder saber si los eventos producidos en un determinado fichero o directorio son relevantes o no (nótese que solo con las listas anteriores saber esto no es trivial, ya que los directorios se monitorizarán de forma recursiva y ficheros de la lista negra pueden estar en directorios que si deseamos monitorizar -obviamente los eventos producidos en ficheros que estén en esta situación deben ser ignorados-)
Los eventos relevantes producidos por los elementos monitorizados serán encolados y se proporcionará una interfaz para que otros módulos puedan acceder a esta información garantizando la consistencia

Garantía de consistencia

Watcher debe garantizar el acceso concurrente a las estructuras que soportan los ficheros bajo monitorización, así como la recepción y tratamiento en el orden adecuado de eventos de cambio concurrentes. Abordaremos el problema mediante la creación de diferentes threads que manejen cada petición y el uso de métodos de bloqueo explícitos entre los distintos threads para asegurar la consistencia de las estructuras de datos.

Garantía de recuperación frente a imprevistos

Watcher debe asegurar que un corte inesperado del flujo eléctrico o el cierre de HD Lorean no provoque la pérdida de los cambios acontecidos inmediatamente antes de la interrupción. Debe proveer checkpoints a partir de los cuales el sistema pueda continuar trabajando justo donde lo dejó la vez anterior, permitiendo de este modo interrumpir HD Lorean cuando el usuario lo desee. Se abordará el problema mediante la creación de una pequeña base de datos que garantice atomicidad y eficiencia de escritura, de tal forma que los eventos de cambio puedan ser escritos temporalmente de manera rápida en este journal con la información necesaria para continuar desde él en caso de caída.

Tecnologías empleadas

A continuación se describe brevemente cada tecnología, se otorga un ejemplo de uso y se destacan sus aspectos positivos y negativos.

Expresiones Regulares

Se han investigado las diferentes opciones para manejar expresiones regulares dentro de la aplicación. Se ha descartado desde un primer momento el uso de Perl y su estándar de expresiones regulares por complicar el diseño de la aplicación y por introducir un nuevo lenguaje que aprender y manejar. Dentro de C/C++ se han investigado dos tecnologías:

POSIX.2 Regular Expressions (GNU C Library)

Esta fue la primera opción investigada. Compatibles con el estándar POSIX, la librería de C ofrece toda la potencia de las expresiones regulares que necesita HD Lorean. Sin embargo el trabajo con esta librería es farragoso y de bajo nivel. Como se ve en el siguiente ejemplo de Ben Tindale, transportar estas librerías a HD Lorean supondría la creación de una clase envoltorio para ocultar y encapsular al resto de la aplicación el manejo interno de las expresiones regulares. Debido a estos inconvenientes se optó por seguir investigando.

/*  mygrep: A simple example to show how regular */
/*  expressions are used in the Gnu C library. */
/*  See the Gnu documentation for information about */
/*  regular expressions: http://www.gnu.org */
/*  Usage: ./mygrep -f <filename> -p <pattern> */
 
/*  author: Ben Tindale <ben@bluesat.unsw.edu.au> */
/*  (C) 2000 Ben Tindale */
 
#include <stdio.h>
#include <stdlib.h>
#include <regex.h> /* Provides regular expression matching */
#include <strings.h> /* String utillity functions */
#include <errno.h> /* Handle errors */
 
int  match_patterns(regex_t *r, FILE *FH)
{
  char line[1024];
  int line_no=1; /* Count the line numbers for nice output */
  size_t no_sub = r->re_nsub+1; /* How many matches are there in a line? */
  regmatch_t *result;
  char *cp; /* Char pointer */
  int start=0; /* The offset from the beginning of the line */
 
  if((result = (regmatch_t *) malloc(sizeof(regmatch_t) * no_sub))==0)
    {
      perror("No more memory - aaaagh! (Die kicking and screaming.)");
      exit(EXIT_FAILURE);
    }
 
  while((cp=fgets(line, 1023, FH))!=NULL)
    {
      while(regexec(r, line+start, no_sub, result, 0)==0) /* Found a match */
    {
      printf("Line %d: %s", line_no, line);
      start +=result->rm_eo; /* Update the offset */
    }
      line_no++;
    }
  return EXIT_SUCCESS;
}
 
int do_regex(regex_t *r, char *p, char *f)
{
  int err_no=0; /* For regerror() */
  FILE *FH=NULL; /* File handle */
  if((err_no=regcomp(r, p, 0))!=0) /* Compile the regex */
    {
      size_t length; 
      char *buffer;
      length = regerror (err_no, r, NULL, 0);
      buffer = malloc(length);
      regerror (err_no, r, buffer, length);
      fprintf(stderr, "%s\n", buffer); /* Print the error */
      free(buffer);
      regfree(r);
      return EXIT_FAILURE;
    }
  if((FH=fopen(f, "r"))==NULL) /* Open the file to scan */
    {
      fprintf (stderr, "Couldn't open file %s; %s\n", f, strerror (errno));
      exit(EXIT_FAILURE);
    }
  match_patterns(r, FH); /* Pass the pattern and the file to be scanned */
  regfree(r); /* Free the regular expression data structure */
  free(r);
  fclose(FH);
  return EXIT_SUCCESS;
}
 
void usage(void)
{
  printf("\n\tmygrep: A simple example to show how regular
\texpressions are used in the Gnu C library.
\tSee the Gnu documentation for information about
\tregular expressions: http://www.gnu.org\n
\tUsage: ./mygrep -f <filename> -p <pattern>\n\n");
}  
 
int main(int argc, char **argv)
{
  int c;
  char *filename=NULL;
  char *pattern=NULL;
  extern char *optarg;
  extern int optind, opterr, optopt;
  regex_t *regex;
  int err_no;
 
  /* Make space for the regular expression */
  regex = (regex_t *) malloc(sizeof(regex_t));
  memset(regex, 0, sizeof(regex_t));
 
  if(argc==1)
    {
      usage();
      return(EXIT_SUCCESS);
    }
  while((c=getopt(argc, argv, "f:p:"))!= EOF)
    {
      switch(c)
    {
    case 'f':
      filename=optarg;
      break;
    case 'p':
      pattern=optarg;
      break;
    case '?':
      fprintf (stderr, "Unknown option `-%c'.\n", optopt);
      usage();
      return EXIT_FAILURE;
    default:
      usage();
      return EXIT_SUCCESS;
    }
    }
  if((err_no=do_regex(regex, pattern, filename))!=EXIT_SUCCESS)
    {
      return EXIT_FAILURE;
    }
  return EXIT_SUCCESS;
}
Librería Boost.Regexp1 (C++)

La ventaja inicial de la librería Boost.Regexp es su orientación a objetos. Se tuvo especial cuidado en que la librería ofreciera compatibilidad absoluta con el estándar POSIX de sintaxis en expresiones regulares. Como beneficio adicional, la librería es compatible con otras librerías de expresiones regulares como la de GNU, BSD4 y de manera algo limitada con Perl 5. Cubre con creces las necesidades de HD Lorean y facilita el manejo de las expresiones regulares con respecto a la librería en C. Otra funcionalidad destacable y que marca la diferencia con otras opciones es que Boost.Regexp es thread safe. Los algoritmos de encaje de patrones regex_match, regex_search, regex_grep, regex_format y regex_merge son todos reentrantes y thread safe. Es importante destacar también que la librería hace uso de excepciones, ofreciendo una mejor forma (más adaptada a C++) de control del flujo de programa y posibles errores en el uso de las expresiones regulares.
Se ha comprobado también que la librería pueda ser instalada en el sistema y/o compilada con el resto de la aplicación, a fin de ofrecer compatibilidad con los sistemas de los laboratorios.
En el siguiente ejemplo se muestra el uso a pequeña escala de esta librería:

  1 #include <iostream>
  2 #include <string>
  3 #include <boost/regex.hpp>  // Boost.Regex lib
  4 
  5 using namespace std;
  6 
  7 int main( ) {
  8 
  9         std::string s, sre;
 10         boost::regex re;
 11         bool end = false;
 12         while(!end){
 13                 cout << "Expression: ";
 14                 cin >> sre;
 15                 if (sre == "quit"){
 16                         end = true;
 17                 }
 18                 if (!end){
 19                         cout << "String:     ";
 20                         cin >> s;
 21                         try{
 22                         // Set up the regular expression for case-insensitivity
 23                                 re.assign(sre, boost::regex_constants::icase);
 24                         }
 25                         catch (boost::regex_error& e){
 26                                 cout << sre << " is not a valid regular expression: \""<< e.what() << "\"" << endl;
 27                         }
 28                         if (boost::regex_match(s, re)){
 29                                 cout << re << " matches " << s << endl;
 30                         }
 31                 }
 32         }
 33 }

Conclusiones: El uso de la librería Boost.RegExp ofrece toda la funcionalidad necesaria, con una simplicidad elevada. Pese a no estar incluida entre las librerías del lenguaje, el inconveniente de tener que añadirla a la aplicación pesa menos que las ventajas (thread safe, estándar POSIX, excepciones, encapsulamiento) que ofrece frente a la librería de C. Se ha decidido utilizar esta última por las razones ya enumeradas.

Monitorización en tiempo real

Para la implementación de esta funcionalidad usaremos inotify-cxx2, que ofrece una interfaz orientada a objetos para trabajar con inotify

Inotify

Inotify es un subsistema del kernel de Linux que permite conocer en tiempo real diversos eventos producidos en ficheros y directorios.

Inotify-cxx

Inotify-cxx es una interfaz para trabajar con inotify en C++ con las ventajas de la programación orientada a objetos y que elimina ciertos aspectos "oscuros" de trabajar directamente con la interfaz de C de inotify (como por ejemplo, tratar a inotify como un fichero).

Opciones investigadas

Inotify-cxx

Ejemplo de uso:
Vamos a monitorizar el borrado de un directorio. Para ello creamos un objeto InotifyWatch que contiene la información necesaria para controlar los eventos (la ruta del directorio y la máscara del evento a notificar).
Ese objeto se añade a un objeto Inotify que es quien se encarga de notificar los eventos, por medio de objetos del tipo InotifyEvent, en los que se almacena, entre otras cosas, quien provocó la notificación y por qué motivo

int main(){
    InotifyWatch* watch;
    watch = new InotifyWatch("/home/user/prueba/",IN_DELETE);
    InotifyWatch* fichero;
    Inotify* n = new Inotify(); 
    InotifyEvent* pEvt;
    pEvt = new InotifyEvent();
    n->Add(watch);
    n->WaitForEvents();
    n->GetEvent (pEvt);
    if(pEvt->IsType(IN_DELETE))
        cout << "Borrado Directorio, saliendo" << '\n';
    }

Conclusiones: Nos hemos limitado a mostrar la librería inotify-cxx ya que ofece la misma funcionalidad que la librería inotify(que era la primera opción que nos planteamos para resolver este problema) pero con la ventajas que ofrece la programación orientada a objetos y porque es una solución de más alto nivel (lo que en inotify-cxx son objetos, usando el API de C se tratarían como ficheros). En contraposición a estas ventajas, la velocidad de ejecución del algoritmo al usar esta librería probablemente será inferior a usar directamente inotify

Threads

Existe una gran variedad de librerías para el manejo de threads en C/C++. Se han considerado todas de manera superficial. La mayoría son wrappers de la libthread de C que buscan ocultar el funcionamiento de los threads a bajo nivel. Las opciones consideradas han sido:

  • Boost.Thread3 (C++)
  • C++ Threads4 (C++)
  • OpenThreads (C++)
  • Libthread (C)

En este campo se ha encontrado que todas las opciones orientadas a objetos expuestas muestran una curva de aprendizaje elevada, frente al uso conocido y sencillo de las libthread de C. Se descartó en primer lugar C++ Threads, por no disponer de ninguna documentación accesible que explicase la interfaz que ofrece y por requerir la instalación en el sistema con permisos de superusuario. OpenThreads son un wrapper de la librería libthread sin más, no ofrece ventaja adicional y fue descartada en segundo lugar.

Boost.Thread es a primera vista tan simple de usar como las librerías nativas libthread de C. Se muestran algunos ejemplos:

//Creation of a thread
void foo()
{
    create_thread(&bar);
}
//Creation of multiple threads in a loop that are latter joined
void foo()
{
         for (int i=0; i<NUM_THREADS; ++i)
            threads[i] = create_thread(&bar);
         for (int i=0; i<NUM_THREADS; ++i)
            threads[i].join();
}

Se muestran ejemplos también de la librería estándar de C para comparar el uso. Este ejemplo es más completo y por tanto el más largo, no obstante la complejidad es idéntica:

 1 #include <pthread.h>
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 
  5 //Cada thread escribe una letra de esta cadena por la salida estandar
  6 char* buf = "abcdefghijklmnopqrstuvwxyz";
  7 //Determina el numero de threads
  8 int num_pthreads = 10;
  9 //Numero de veces que se repetira la ejecucion
 10 int count = 25;
 11 //Salida estandar
 12 int fd = 1;
 13 
 14 /*
 15  * Escribe por pantalla el caracter apuntado por el parametro
 16  */
 17 void* new_thread(void* arg);
 18 
 19 int main(void)
 20 {
 21         //Declaracion del thread
 22         pthread_t thread;
 23         int i;
 24         for (i = 0; i < num_pthreads; i++) {
 25                 //Creacion del thread
 26                 if (pthread_create(&thread,NULL,new_thread,(void *)(buf + i)) > 0){
 27                         fprintf(stderr, "error creating a new thread \n");
 28                         exit(1);
 29                 }
 30                 // Coloca el thread en estado detach
 31                 pthread_detach(thread);
 32         }
 33         //Sale del thread
 34         pthread_exit(NULL);
 35 }
 36 
 37 
 38 void* new_thread(void * arg)
 39 {
 40         int i;
 41         for (i = 0; i < count; i++) {
 42                 write(fd, arg, 1);
 43                 sleep(1);
 44         }
 45         return(NULL);
 46 }

Conclusiones: No se ha tomado una decisión sobre el uso de una de las dos librerías. Todas las partes implicadas del equipo deben valorar si compensa aprender a manejar Boost.Thread sólo por ser OO o usar las librerías built-in de threads de C.

Bases de Datos

Se ha buscado la forma más eficiente de estructurar la tabla con la información necesaria para iniciar una recuperación del estado anterior de la aplicación tras un corte inesperado. El diseño del pequeño journal se ha esbozado de la siguiente manera:

 12 CREATE TABLE IF NOT EXISTS journal (
 13         id INT(5)       UNSIGNED        NOT NULL        PRIMARY KEY     AUTO    _INCREMENT,
 14         timestamp       TIMESTAMP       NOT NULL,
 15         chtype          VARCHAR(255)    NOT NULL,
 16         initpath        VARCHAR(255)    NOT NULL,
 17         finalpath       VARCHAR(255)    NOT NULL,
 18         wrote           CHAR(1)         NOT NULL        DEFAULT "0",
 19         INDEX(timestamp))
 20         MAX_ROWS=300;

Se ha controlado el tamaño del journal como medida para garantizar la rápidez de escritura en la base de datos en cuanto los cambios son notificados por el sistema de ficheros. La tecnología de base de datos utilizada es el resultado de la investigación de http://hdlorean.wikidot.com/bases-de-datos

Conclusiones: La atomicidad y los mecanismos de exclusión del sgbd sqlite, junto al diseño del journal, garantizan que los cambios se escribirán de manera temporal suficientemente rápido como para que el sistema pueda recuperarse a través del journal de una caída inesperada.

Conclusión

Se han estudiado tecnologías para cubrir todas las funcionalidades que debería ofrecer Watcher y se han encontrado candidatos plausibles para cumplir con todos los requisitos. Se ha tenido en cuenta principalmente la compatibilidad, la facilidad de uso y la abstracción de las soluciones elegidas. En esta situación podemos comenzar el desarrollo del Watcher con la garantía de cumplir con los requisitos del módulo.

Opinión personal

Vistas las opciones de implementación de las tecnologías y considerando que la mayor complicación viene de la programación de funciones reentrantes y del manejo de los threads, podemos obtener un prototipo funcional sin threads en un tiempo corto, dejando abierta la puerta al uso de threads si hubiese tiempo para implementarlo.

Comentarios:

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License