inotify_watch.c

Go to the documentation of this file.

/*****************************************************************************/
/******************************** Documentation ******************************/
/*****************************************************************************/

/**
 * \file
 * Use inotify to establish file watches.
 *
 * \page InotifyOverview Inotify Usage Overview
 *
 * \section InotifyCookieCacheDoc How inotify rename cookies are managed.
 *
 * inotify provides notification of renames (e.g. moves) via a pair of events,
 * the IN_MOVED_FROM and IN_MOVED_TO events. In order to match these events into
 * a pair each event contains an identifier unique to the pair called a
 * "cookie". Move events only occur when watching the directory containing the
 * moved item. Thus it possible to receive just one move event instead of a
 * pair. So how do we match up move events? In the current kernel inotify
 * implementation move events are always emitted as contiguous pairs with
 * IN_MOVED_FROM immediately followed by IN_MOVED_TO. One could match move pairs
 * by checking if the next event following a IN_MOVED_FROM was a IN_MOVED_TO, if
 * so that constutes a pair, otherwise assume the matching move event will never
 * be seen. This is how inotifytools works, it never looks at the cookie to
 * perform the match nor tracks cookies, however it's depending on kernel
 * behavior that is not guaranteed. The gamin file monitor keeps cookies in a
 * hash table for subsequent lookup. However the downside of this is because the
 * matching cookie may never arrive one has to periodically flush the table of
 * old cookies based on a timestamp. This is a lot of extra logic and machine
 * cyles even though it's probably the "correct" solution, especially
 * considering it's reasonable to expect the matching cookie to be deliveried as
 * the next event.
 *
 * We take a compromise approach that allows non-sequential delivery of cookies
 * but requires little processing logic for the expected sequential delivery
 * case and minimal overhead otherwise. We keep a small ordered cache of cookies
 * in an array. The oldest cookie is the first array element, the youngest
 * cookie is the topmost element. Because we know cookie operations always occur
 * as either a single event or a pair of events the cache operator functions in
 * a binary dual mode. We present a cookie to the cache, if it's not already in
 * the cache we enter it in the cache discarding the oldest cookie if the cache
 * is full. If the cookie was found we have a matching pair and the cookie is
 * removed from the cache. The cache operator returns a boolean if the cookie
 * was found thus indicating we have a complete pair (removing the cookie from
 * the cache in the process, otherwise the cookie is entered in the cache).
 *
 * When we flush an entry from the cache due to its age we provide a callback so
 * that the user of the cache can be aware a matching cookie will never found
 * for the rename. This knowledge may be important in some scenarios.
 *
 * When a cache entry is removed it does require moving all the array elements
 * above the removed entry down one position in the array. Moving the entire
 * contents of an array is often though of as inefficient, but that is not
 * always the case. Because the array is small and because only simple pointer
 * arithmetic is used and because the memory moved has locality of reference
 * (probably fitting in a cache line) the operation is much more efficient than
 * removing an entry from a hash table or linked list (both of which probably
 * also would include malloc/free). Lookups are also much more efficient for the
 * same reason (simple array indexing in a small area of memory). But the
 * biggest benefit comes from the fact in the common case of sequential paired
 * events the cache size never grows beyond 1 and array elements are never
 * shifted. It reasonable to keep the cache size small given we expect the
 * matching cookie to arrive as the next event or shortly thereafter. We do not
 * expect there to be many intervening move events, thus a cache size on the
 * order of 4 to 8 entries is probably more than sufficient and keeps the
 * processor cycles needed to manage the cache at a minimum. This seems like a
 * good compromise between robustness and efficiency.
 *
 * \section DescendantWatchesDoc How Watch Points Watch Descendants
 *
 * Inotify can watch either directories and files. One might expect since we're
 * in the business of watching files we would elect to establish a watch on a
 * file. However Inotify can only send an event when a file is created, deleted,
 * or renamed when you are watching the directory containing the file, not the
 * file itself. This is because file existence is really a change in directory
 * contents. If you're using Inotify to watch a directory you also will be
 * informed of modifications to any file in the directory, the same information
 * that would be conveyed if you were watching an individual file. Thus it
 * really only makes sense with Inotify to watch directories and not files.
 *
 * Inotify can only establish a watch on file system objects which exist. It is
 * not possible to establish a watch on something which does not exist. The best
 * one can do is watch on an existing directory where you expect either a file
 * or a sub-directory to be created. Since you're watching an existing directory
 * you'll be notified whenever that directory has a file or directory created in
 * it or deleted from it.
 *
 * Whenever we're asked to watch a file what we really do is set a watch on the
 * directory which contains that file. Whenever the directory informs us that
 * something has been added, removed, or modified in the directory we ask "Is
 * that item something we're watching?" Thus every directory we establish a
 * watch on has a data structure associated with it (\ref path_watch_t) which
 * enumerates every item of interest in the directory.
 *
 * If we are asked to watch a file in a directory which does not exist we are
 * confronted with the problem there is nothing to set an Inotify watch on. So
 * instead we start at the directory closest to the file in the chain of
 * directories comprising the file path and start walking up that chain toward
 * the root until we find a directory which does exist. We call this the closest
 * existing ancestor of the target. This is our best option for establishing a
 * watch for the file. We inform that directory it needs to watch for the
 * creation of a sub-directory which might lead to the file. This will be a
 * descendant of the directory being watched. Thus a directory which has an
 * Inotify watch on it must watch for any files it contains which are of
 * interest and any sub-directory which leads to a descendant. Directories which
 * have Inotify watches established on them are called watch points. Technically
 * files contained in the directory are also descendants of the directory if one
 * considers a path name as a sequence of path components. Thus anything a
 * directory is watching we call a descendant watch.
 *
 * If a descendant watch is for a non-existent directory and a sub-directory
 * which might lead to the descendant watch is created in the directory then
 * that directory is no longer the closest existing ancestor, the new
 * sub-directory or one of it's descendants will now be the closest existing
 * ancestor. Thus we must move the watch to the closest existing ancestor
 * anytime directories are created or destroyed which lie along the path to the
 * target. This makes the set of watch points ephemeral and fluid. If a
 * directory has a descendant watch removed from it because it is no longer the
 * closest existing ancestor it might not have anything to watch for anymore
 * unless there are other descendant watches for it to track. So after removing
 * a descendant watch from a watch point we check to see if it's set of
 * descendant watches is now empty, if so we completly remove the watch point
 * from Inotify observation. In a similar fashion a watch point might come into
 * existence for no other reason besides the fact at the moment it's the closest
 * existing ancestor for a watch.
 *
 * \image html watch_architecture_1.jpg
 * \image html watch_architecture_2.jpg
 *
 */

/*****************************************************************************/
/******************************* Include Files *******************************/
/*****************************************************************************/

#define _GNU_SOURCE             /**< Turn on GNU extensions */
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stdint.h>
#include <string.h>
#include <errno.h>
#include <getopt.h>
#include <unistd.h>

#include <sys/types.h>
#include <sys/stat.h>
#include <sys/param.h>
#include <sys/stat.h>
#include <sys/inotify.h>
#include <signal.h>

#include "dhash.h"
#include "path_utils.h"
#include "logging.h"
#include "inotify_watch.h"
#include "util.h"
#include "lwatch.h"

/*****************************************************************************/
/****************************** Internal Defines *****************************/
/*****************************************************************************/

/**
 * size of the inotify event structure, not counting name
 */
#define INOTIFY_EVENT_SIZE  (sizeof (struct inotify_event))

/**
 * How many pending rename operations we'll track.
 * See \ref InotifyCookieCacheDoc.
 */
#define INOTIFY_COOKIE_CACHE_SIZE 10

/**
 * The inotify events we need to be informed of.
 */
#define INOTIFY_EVENTS (IN_MOVE | IN_CREATE | IN_ISDIR | IN_MODIFY | IN_OPEN | \
                        IN_CLOSE_WRITE | IN_DELETE | IN_DELETE_SELF | \
                        IN_IGNORED | IN_MOVED_FROM | IN_MOVED_TO)

/**
 * How many entries to initially reserve in global hash tables.
 */
#define INITIAL_HASH_TABLE_SIZE 16

/**
 * How many entries to initially reserve in the path watch object descendant
 * hash table.
 */
#define INITIAL_DESCENDANT_HASH_TABLE_SIZE 2

/*****************************************************************************/
/************************** Internal Type Definitions ************************/
/*****************************************************************************/


/**
 * Struct used to track inotifiy MOVE operations (e.g. rename).
 * See \ref InotifyCookieCacheDoc.
 */
struct inotify_cookie_cache_entry_t {
    uint32_t cookie;            /**< the unique cookie which associates two MOVE events*/
    int prev_watch_id;          /**< the watch_id for the previous pathname*/
    int new_watch_id;           /**< the watch_id for the new pathname */
    char prev_path[PATH_MAX];   /**< the previous pathname */
    char new_path[PATH_MAX];    /**< the new pathname */
};

/**
 * Convenience struct used in callbacks to test a path and get return a boolean
 * result.
 */
struct path_and_result_t {
    const char *path;           /**< the path name which is the subject of the test */
    bool result;                /**< the boolean result which is returned */
};

/**
 * Definition of callback signature used when interested party wants to be
 * informed that a rename operation never saw both the previous and new names,
 * only either the previous or the new name was ever seen.
 * See \ref InotifyCookieCacheDoc.
 */
typedef void (*inotify_lost_cookie_callback_t)(struct inotify_cookie_cache_entry_t *move);

/*****************************************************************************/
/**********************  External Function Declarations  *********************/
/*****************************************************************************/

/*****************************************************************************/
/**********************  Internal Function Declarations  *********************/
/*****************************************************************************/

static bool visit_descendants_and_test_for_ancestor(hash_entry_t *item, void *user_data);
static bool is_path_an_ancestor_of_any_watch_descendants(struct path_watch_t *pw, const char *subject_path);
static int free_path_watch(struct path_watch_t **ppw);
static int new_path_watch(const char *path, struct path_watch_t **pw_return);
static int destroy_path_watch(struct path_watch_t **ppw);
static int destroy_path_watch_if_empty(struct path_watch_t **ppw);
static int add_path_to_target_list(const char *path);
static int remove_path_from_target_list(const char *path);
static int track_path_watch(struct path_watch_t *pw);
static int untrack_path_watch(struct path_watch_t *pw);
static void lost_rename_callback(struct inotify_cookie_cache_entry_t *move);
static int process_event(struct inotify_event *event);
static int relocate_watches(struct path_watch_t *pw);
static struct inotify_cookie_cache_entry_t *
inotify_cookie_cache_operator(struct inotify_event *event, const char *path);
static void flush_inotify_cookie_cache(void);
static void log_watch_path_table(const char *fmt, ...);
static void log_target_table(const char *fmt, ...);

/*****************************************************************************/
/*************************  External Global Variables  ***********************/
/*****************************************************************************/

bool keep_watching = true;       /* FIXME */

/*****************************************************************************/
/*************************  Internal Global Variables  ***********************/
/*****************************************************************************/

/**
 * User callback invoked when an inotify move has a "lost" old or new name as
 * part of a rename (MOVE) event.
 * See \ref InotifyCookieCacheDoc for more explanation.
 */
static inotify_lost_cookie_callback_t inotify_lost_cookie_callback = NULL;
/**
 * Cache of incomplete inotify rename (MOVE) events.
 * See \ref InotifyCookieCacheDoc for more explanation.
 */
static struct inotify_cookie_cache_entry_t inotify_cookie_cache[INOTIFY_COOKIE_CACHE_SIZE];
/**
 * Number of entries in the cache of incomplete inotify rename (MOVE) events.
 * See \ref InotifyCookieCacheDoc for more explanation.
 */
static int n_cookies = 0;

/**
 * Hash table which maps from a path name being watched by inotify to a path
 * watch object. See \ref VocabularyDoc
 */
static hash_table_t *watch_path_table = NULL;
/**
 * Hash table which maps from an id provided by inotify to a path watch
 * object. See \ref VocabularyDoc
 */
static hash_table_t *watch_id_table = NULL;
/**
 * Hash table of watch targets. See \ref VocabularyDoc
 */
static hash_table_t *target_table = NULL;

/**
 * The file descriptor provided by inotify to read inotify events from.
 */
static int inotify_fd = -1;

/**
 * User callback for sending log watch events from the inotify back end to the
 * log watcher. See \ref IndependentWatchBackEndDoc for an explantion of how
 * inotify serves as a backend for the log watching code.
 */
static lwatch_event_callback_t lwatch_event_callback = NULL;

/*****************************************************************************/
/****************************  Inline Functions  *****************************/
/*****************************************************************************/

/*****************************************************************************/
/***************************  Internal Functions  ****************************/
/*****************************************************************************/

/**
 * Hash iteration callback used to determine if subject path is an ancestor of
 * any descendant.
 * \param[in] item      A hash table entry, the key is one of the descendant paths
 * \param[in] user_data Contains the subject path, and the return result of the test.
 * \return          Returns false to terminate iteration as soon as result is known.
 *
 * \ref DescendantWatchesDoc
 */
static bool visit_descendants_and_test_for_ancestor(hash_entry_t *item, void *user_data)
{
    struct path_and_result_t *data = (struct path_and_result_t *) user_data;
    const char *descendant_path = item->key.str;
    const char *subject_path = data->path;

    data->result = is_ancestor_path(subject_path, descendant_path);
    return !data->result;       /* returning false terminates the iteration */
}

/**
 * Return true if a portion of the path could be one of the descendants being
 * watched.
 * \param[in] pw           Path watch object
 * \param[in] subject_path The path being tested
 * \return             True if the subject path is an ancestor of any descandant watches
 *
 * Iterate over the list of descendant paths this watch is responsible for.  If
 * the subject path is contained in a descendant path (e.g. the subject path an
 * ancestor of the descendant path) then return true. If the subject_path is not
 * an ancestor of any of the descendants being watched return false.
 *
 * Example:
 *
 * The watch is established on "/a/b"
 *
 * The watch on "/a/b" has a descendant "/a/b/c/d" it's responsible for watching
 * for.
 *
 * The subject path being tested is "/a/b/c"<br>
 *
 * In this instance the subject "/a/b/c" is an ancestor of "/a/b/c/d" and the
 * function would return true.
 *
 * This test is typically done when a new directory is added to the directory
 * being watched. So lets say directory "c" was created in "/a/b" forming a new
 * path of "a/b/c". We call this function asking if "/a/b/c" belongs to any of
 * the descendants being watched. In our example one of the descendants being
 * watched by "/a/b" is "/a/b/c/d" (we're waiting for "/a/b/c" to be created
 * which is why "/a/b/c/d" a descendant watch of "a/b"). The function returns
 * true indicating that the newly formed directory "/a/b/c" is indeed part of
 * what this directory is responsible watching for and as a consequence the
 * descendant watch for "/a/b/c/d" will be moved from "/a/b" to one of the newly
 * created descendants of "/a/b", i.e. it will be moved to "/a/b/c" (or further
 * down the list of path components if we discover more path components exist at
 * the time we move the watch.
 *
 * \see DescendantWatchesDoc
 */
static bool is_path_an_ancestor_of_any_watch_descendants(struct path_watch_t *pw, const char *subject_path)
{
    struct path_and_result_t data;

    data.path = subject_path;
    data.result = false;

    hash_iterate(pw->descendant_path_table, visit_descendants_and_test_for_ancestor, &data);
    return data.result;
}


/**
 * Free a watch object when no longer needed
 * \param[out] ppw Pointer to the path watch object to free, will be set to NULL
 * \return         SUCCESS (0) or non-zero error code otherwise
 */
static int free_path_watch(struct path_watch_t **ppw)
{
    struct path_watch_t *pw = *ppw;
    int error = SUCCESS;

    if (pw->descendant_path_table) {
        if ((error = hash_destroy(pw->descendant_path_table)) != HASH_SUCCESS) {
            log_msg(LOG_ERROR, _("could not free file hash table error=%d\n"),  error);
        }
    }

    free(pw);
    *ppw = NULL;

    return error;
}

/**
 * Create and intialize a new path watch object, add it's path to the watch subsystem
 * \param[in]  path      The path being watched by this watch object
 * \param[out] pw_return The newly created path watch object is assigned to this variable
 * \return               SUCCESS (0) or non-zero error code otherwise
 *
 */
int new_path_watch(const char *path, struct path_watch_t **pw_return)
{
    struct path_watch_t *pw;
    int error;

    *pw_return = NULL;

    if ((pw = (struct path_watch_t *)malloc(sizeof(struct path_watch_t))) == NULL) {
        error = ENOMEM;
        log_msg(LOG_ERROR, _("\"%s\" (%s)\n"),  path, error_string(error));
        return error;
    }

    if ((error = copy_path(pw->path, path, sizeof(pw->path))) != SUCCESS) {
        log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), path, error_string(error));
        free_path_watch(&pw);
        return error;
    }

    pw->watch_id = -1;
    pw->descendant_path_table = NULL;

    if ((error = hash_create(INITIAL_DESCENDANT_HASH_TABLE_SIZE,
                             &pw->descendant_path_table, NULL)) != HASH_SUCCESS) {
        log_msg(LOG_ERROR, _("cannot create file hash table in path_watch_t object for path \"%s\"\n"), path);
        free_path_watch(&pw);
        return error;
    }

    log_msg(LOG_DEBUG, _("adding directory watch for \"%s\"\n"), path);
    if ((pw->watch_id = inotify_add_watch(inotify_fd, path, INOTIFY_EVENTS)) < 0) {
        error = errno;
        log_msg(LOG_ERROR, _("could not add inotify watch for \"%s\" (%s)\n"),
                path, error_string(error));
        free_path_watch(&pw);
        return error;
    }
    log_msg(LOG_DEBUG, _("newly watching [%d] \"%s\"\n"), pw->watch_id, path);

    *pw_return = pw;
    return SUCCESS;
}

/**
 * Destroy the path watch object; remove it's path from watch subsystem, then free
 * it's memory and resources, set the variable pointed to by ppw to NULL;
 * \param[out] ppw Pointer to the path watch object to destroy, will be set to NULL on SUCCESS.
 * \return     SUCCESS (0) or non-zero error code otherwise
 */
static int destroy_path_watch(struct path_watch_t **ppw)
{
    struct path_watch_t *pw = *ppw;
    int error;

    log_msg(LOG_DEBUG, _("destroying watch for [%d] \"%s\"\n"),  pw->watch_id, pw->path);
    inotify_rm_watch(inotify_fd, pw->watch_id);
    if ((error = untrack_path_watch(pw)) != SUCCESS) {
        log_msg(LOG_ERROR, _("Could not untrack_path_watch for \"%s\" (%s)\n"),
                pw->path, error_string(error));
    }
    free_path_watch(ppw);
    return SUCCESS;
}

/**
 * If the path watch object has no descendant targets to watch then destroy it.
 * If the path watch is destroyed the variable pointed to by ppw will be set to NULL.
 * \param[out] ppw Pointer to the path watch object to destroy, will be set to NULL if destroyed.
 * \return     SUCCESS (0) or non-zero error code otherwise
 */
static int destroy_path_watch_if_empty(struct path_watch_t **ppw)
{
    struct path_watch_t *pw = *ppw;
    int error;

    error = SUCCESS;
    if (hash_count(pw->descendant_path_table) == 0) {
        log_msg(LOG_DEBUG, _("destroying empty watch for [%d] \"%s\"\n"), pw->watch_id, pw->path);
        if ((error = destroy_path_watch(ppw)) != SUCCESS) {
            log_msg(LOG_ERROR, _("destroy_path_watch() failed (%s)\n"), error_string(error));
        }
    }
    return error;
}

/**
 * Add this path to list of watch targets
 * \param[in] path The path to add to the list of watch targets
 * \return     SUCCESS (0) or non-zero error code otherwise
 */
static int add_path_to_target_list(const char *path)
{
    int error;
    hash_key_t key;
    hash_value_t value;

    key.type = HASH_KEY_STRING;
    key.str = path;
    value.type = HASH_VALUE_UNDEF;

    if ((error = hash_enter(target_table, &key, &value)) != HASH_SUCCESS) {
        log_msg(LOG_ERROR, _("cannot add to target table \"%s\" (%s)\n"),
                path, error_string(error));
        return error;
    }
    return SUCCESS;
}

/**
 * Removes a path from the list of watch targets
 * \param[in] path The path to remove from the list of watch targets
 * \return     SUCCESS (0) or non-zero error code otherwise
 */
static int remove_path_from_target_list(const char *path)
{
    int error;
    hash_key_t key;

    key.type = HASH_KEY_STRING;
    key.str = path;

    if ((error = hash_delete(target_table, &key)) != HASH_SUCCESS) {
        log_msg(LOG_ERROR, _("cannot remove from target table \"%s\" (%s)\n"),
                path, error_string(error));
        return error;
    }
    return SUCCESS;
}

/**
 * Do the bookkeeping to track a path watch object
 * \param[in] pw The path watch object to track in our internal data structures
 * \return   SUCCESS (0) or non-zero error code otherwise
 */
static int track_path_watch(struct path_watch_t *pw)
{
    int error = SUCCESS;
    hash_key_t key;
    hash_value_t value;

    key.type = HASH_KEY_STRING;
    key.str = pw->path;
    value.type = HASH_VALUE_PTR;
    value.ptr = pw;

    if ((error = hash_enter(watch_path_table, &key, &value)) != HASH_SUCCESS) {
        log_msg(LOG_ERROR, _("cannot add to pathname table \"%s\" (%s)\n"),
                pw->path, error_string(error));
        return error;
    }

    key.type = HASH_KEY_ULONG;
    key.ul = pw->watch_id;

    if ((error = hash_enter(watch_id_table, &key, &value)) != HASH_SUCCESS) {
        log_msg(LOG_ERROR, _("cannot add to watch id table %d (%s)\n"),
                pw->watch_id, error_string(error));
        return error;
    }

    if (debug > 1) log_watch_path_table("after inserting \"%s\"",  pw->path);
    return SUCCESS;
}

/**
 * Remove a path watch object from our tracking data structures
 * \param[in] pw The path watch object to remove from our internal data structures
 * \return   SUCCESS (0) or non-zero error code otherwise
 */
static int untrack_path_watch(struct path_watch_t *pw)
{
    int error = SUCCESS;
    hash_key_t key;

    if (!pw) {
        error = INOTIFY_WATCH_ERROR_NULL_WATCH;
        log_msg(LOG_ERROR, _("NULL path_watch (%s)\n"),  error_string(error));
        return error;
    }

    key.type = HASH_KEY_STRING;
    key.str = pw->path;

    if ((error = hash_delete(watch_path_table, &key)) != HASH_SUCCESS) {
        log_msg(LOG_ERROR, _("cannot delete from pathname table \"%s\" (%s)\n"),
                pw->path, error_string(error));
        return error;
    }

    key.type = HASH_KEY_ULONG;
    key.ul = pw->watch_id;

    if ((error = hash_delete(watch_id_table, &key) != HASH_SUCCESS)) {
        log_msg(LOG_ERROR, _("cannot delete from watch id table \"%s\" (%d)\n"),
                pw->watch_id, error_string(error));
        return error;
    }

    if (debug > 1) log_watch_path_table("after deleting \"%s\"", pw->path);
    return SUCCESS;
}

/**
 * A directory or file was renamed but we don't have both names,
 * invoke this to emit a rename event.
 * \param[in] move an entry in inotify cookie cache which is being flushed
               even though incomplete
 * \return     SUCCESS (0) or non-zero error code otherwise
 *
 * See \ref InotifyCookieCacheDoc for an explanation of how inotifiy handles
 * renames and the issues surrounding it.
 */
static void lost_rename_callback(struct inotify_cookie_cache_entry_t *move)
{
    int error;

    if (lwatch_event_callback) {
        struct lwatch_event_t event;

        event.event_type = LWATCH_EVENT_RENAME;
        if ((error = copy_path(event.rename.prev_path, move->prev_path, sizeof(event.rename.prev_path))) != SUCCESS) {
            log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), move->prev_path, error_string(error));
        }
        if ((error = copy_path(event.rename.new_path,  move->new_path,  sizeof(event.rename.new_path))) != SUCCESS) {
            log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), move->new_path, error_string(error));
        }
        lwatch_event_callback(&event);
    }
}

/**
 * Given an inotify event, process it and transform it into a generic lwatch_event
 * \param[in] event The inotify event to process.
 * \return      SUCCESS (0) or non-zero error code otherwise
 *
 * We read inotify_events one at a time from a file descriptor the kernel
 * provides us. Each inotify_event contains an integer watch descriptor (wd)
 * which identifies the specific watch on a filesystem entry, a bitmask
 * describing the contents of the event, a cookie to synchronize events, and the
 * length of the event which indicates if an optional name is part of the event.
 *
 * To isolate the log watcher code from specific monitoring backends a generic
 * monitoring event (lwatch_event_t) is defined. Each monitoring backend is
 * responsible for translating to the generic lwatch_event_t event and emiting
 * an event of that type.
 *
 * This routine takes an inotify_event, processes it, and then emits a
 * generic lwatch_event_t event which the log watcher code then processes.
 *
 * See \ref IndependentWatchBackEndDoc for an explantion of how inotify serves
 * as a backend for the log watching code.
 */

static int process_event(struct inotify_event *event)
{
    int error;                  /* FIXME: need to check error on all calls */
    struct path_watch_t *pw;
    char event_path[PATH_MAX];

    /* Lookup the watch info associated with this event in our hash table */
    if (!(pw = find_watch_by_watch_id(event->wd))) {
        log_msg(LOG_ERROR, _("could not look up watch id %d\n"),  event->wd);
        return INOTIFY_WATCH_ERROR_WATCH_ID_NOT_FOUND;
    }

    /* If the event has a name associated with it, form it's complete path */
    if (event->len) {
        if ((error = path_concat(event_path, sizeof(event_path), pw->path, event->name)) != SUCCESS) {
            log_msg(LOG_ERROR, _("failed to concatenate path \"%s\" + \"%s\" (%s)\n"),
                    pw->path, event->name, error_string(error));
            return error;
        }
    } else {
        if ((error = copy_path(event_path, pw->path, sizeof(event_path))) != SUCCESS) {
            log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), pw->path, error_string(error));
            return error;
        }
    }

    log_msg(LOG_DEBUG, _("wd=%d mask=[%s] cookie=%u len=%u name=\"%s\" path=\"%s\"\n"),
            event->wd, inotify_mask_string(event->mask, ","),
            event->cookie, event->len, event->len ? event->name : NULL,
            event->len ? event_path : pw->path);

    /*
     * Extra debug information. Print the watch info associated with this event
     * and the full contents of the watch table, i.e. the watch info for all existing
     * watches. Print the target table.
     * Generating these strings is expensive, only do if debugging.
     */
    if (debug) {
        char *fw_string = path_watch_string(pw);

        log_msg(LOG_DEBUG, _("[%s] pw=%s\n"),
                inotify_mask_string(event->mask, ","), fw_string);

        log_watch_path_table("On entry to: %s", __FUNCTION__);
        log_target_table("On entry to: %s", __FUNCTION__);
        free(fw_string);
    }

    /*
     * A file or directory in this watched directory was renamed.
     */
    if (event->mask & IN_MOVE) {
        struct inotify_cookie_cache_entry_t *move;

        if ((move = inotify_cookie_cache_operator(event, event_path))) {
            log_msg(LOG_DEBUG, _("renamed \"%s\" --> \"%s\"\n"),
                    move->prev_path, move->new_path);

            if (is_watch_target(move->prev_path) || is_watch_target(move->new_path)) {
                if (lwatch_event_callback) {
                    struct lwatch_event_t lw_event;

                    lw_event.event_type = LWATCH_EVENT_RENAME;
                    if ((error = copy_path(lw_event.rename.prev_path, move->prev_path,
                                           sizeof(lw_event.rename.prev_path))) != SUCCESS) {
                        log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"),
                                move->prev_path, error_string(error));
                        return error;
                    }
                    if ((error = copy_path(lw_event.rename.new_path,  move->new_path,
                                           sizeof(lw_event.rename.new_path))) != SUCCESS) {
                        log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"),
                                move->new_path, error_string(error));
                        return error;
                    }
                    lwatch_event_callback(&lw_event);
                }
            }
        }
    /*
     * A file or directory was created in this watched directory.
     */
    } else if (event->mask & IN_CREATE) {
        char *new_path = event_path;

        if (is_path_an_ancestor_of_any_watch_descendants(pw, new_path)) {
            log_msg(LOG_DEBUG, _("new path %s \"%s\" is a watch target\n"),
                    event->mask & IN_ISDIR ? "directory":"file", new_path);

            if ((error = relocate_watches(pw)) != SUCCESS) {
                log_msg(LOG_ERROR, _("could not relocate_watches for \"%s\" (%s)\n"),
                        new_path, error_string(error));
            }

            if (lwatch_event_callback) {
                struct lwatch_event_t lw_event;

                lw_event.event_type = LWATCH_EVENT_CREATE;
                if ((error = copy_path(lw_event.path, new_path, sizeof(lw_event.path))) != SUCCESS) {
                    log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), new_path, error_string(error));
                    return error;
                }
                lwatch_event_callback(&lw_event);
            }
        } else {
            log_msg(LOG_DEBUG, _("new path %s \"%s\" is not within a watch target\n"),
                    event->mask & IN_ISDIR ? "directory":"file", new_path);
        }
    /*
     * A file or directory in this watched directory was modifed.
     */
    } else if (event->mask & IN_MODIFY) {
        char *modified_path = event_path;

        log_msg(LOG_DEBUG, _("modified \"%s\"\n"),  modified_path);

        if (is_watch_target(modified_path)) {
            log_msg(LOG_DEBUG, _("watched file is modified \"%s\"\n"),  modified_path);
            if (lwatch_event_callback) {
                struct lwatch_event_t lw_event;

                lw_event.event_type = LWATCH_EVENT_MODIFY;
                if ((error = copy_path(lw_event.path, modified_path, sizeof(lw_event.path))) != SUCCESS) {
                    log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), modified_path, error_string(error));
                    return error;
                }
                lwatch_event_callback(&lw_event);
            }
        }
    /*
     * A file or directory in this watched directory was opened.
     */
    } else if (event->mask & IN_OPEN) {
        char *opened_path = event_path;

        if (is_watch_target(opened_path)) {
            log_msg(LOG_DEBUG, _("opened watched \"%s\"\n"),  opened_path);
            if (lwatch_event_callback) {
                struct lwatch_event_t lw_event;

                lw_event.event_type = LWATCH_EVENT_OPEN;
                if ((error = copy_path(lw_event.path, opened_path, sizeof(lw_event.path))) != SUCCESS) {
                    log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), opened_path, error_string(error));
                    return error;
                }
                lwatch_event_callback(&lw_event);
            }
        } else {
            log_msg(LOG_DEBUG, _("opened unwatched \"%s\"\n"),  opened_path);
        }
    /*
     * A file or directory in this watched directory was closed.
     */
    } else if (event->mask & IN_CLOSE_WRITE) {
        char *closed_path = event_path;

        if (is_watch_target(closed_path)) {
            log_msg(LOG_DEBUG, _("closed watched \"%s\"\n"),  closed_path);
            if (lwatch_event_callback) {
                struct lwatch_event_t lw_event;

                lw_event.event_type = LWATCH_EVENT_CLOSE;
                if ((error = copy_path(lw_event.path, closed_path, sizeof(lw_event.path))) != SUCCESS) {
                    log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), closed_path, error_string(error));
                    return error;
                }
                lwatch_event_callback(&lw_event);
            }
        } else {
            log_msg(LOG_DEBUG, _("closed unwatched \"%s\"\n"),  closed_path);
        }
    /*
     * A file or directory in this watched directory was deleted.
     */
    } else if (event->mask & IN_DELETE) {
        char *deleted_path = event_path;

        if (is_watch_target(deleted_path)) {
            log_msg(LOG_DEBUG, _("deleted watched \"%s\"\n"),  deleted_path);
            if (lwatch_event_callback) {
                struct lwatch_event_t lw_event;

                lw_event.event_type = LWATCH_EVENT_DELETE;
                if ((error = copy_path(lw_event.path, deleted_path, sizeof(lw_event.path))) != SUCCESS) {
                    log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), deleted_path, error_string(error));
                    return error;
                }
                lwatch_event_callback(&lw_event);
            }
        } else {
            log_msg(LOG_DEBUG, _("deleted unwatched \"%s\"\n"),  deleted_path);
        }

    /*
     * This file or directory on which a watch was established was deleted.
     */
    } else if (event->mask & IN_DELETE_SELF) {
        char deleted_path[PATH_MAX];

        if ((error = copy_path(deleted_path, pw->path, sizeof(deleted_path))) != SUCCESS) {
            log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), pw->path, error_string(error));
            return error;
        }
        if ((error = relocate_watches(pw)) != SUCCESS) {
            log_msg(LOG_ERROR, _("IN_DELETE_SELF could not relocate_watches for \"%s\" (%s)\n"),
                    deleted_path, error_string(error));
        }
    /*
     * This watch has been removed.
     */
    } else if (event->mask & IN_IGNORED) {
        if ((error = untrack_path_watch(pw)) != SUCCESS) {
            log_msg(LOG_ERROR, _("IN_IGNORED could not untrack_path_watch for \"%s\" (%s)\n"),
                    pw->path, error_string(error));
        }
        if ((error = free_path_watch(&pw)) != SUCCESS) {
            log_msg(LOG_ERROR, _("IN_IGNORED could not free_path_watch (%s)\n"), error_string(error));
        }

    }
    return SUCCESS;
}

/**
 * Move each descendant watch target of this directory to it's optimal watch directory
 * \param[in] pw The path watch object to track in our internal data structures
 * \return   SUCCESS (0) or non-zero error code otherwise
 *
 * Watch targets are assigned to directories (e.g. a path watch on a
 * directory). The optimal directory is the directory containing the watch
 * target, however that directory may not exist thus a watch cannot be
 * established. The most optimal directory to establish the watch on is the
 * closest existing ancestor directory for the watch target. When a watch is
 * established on the closest existing ancestor directory that directory can
 * watch for the creation of a subdirectory leading to the watch target. When
 * that occurs we move the ownership of the watch to it's closest watch
 * point. This is the purpose of this function. When a directory containing a
 * set of watches is removed the analogous process must take place, rather than
 * moving the watch owner further down the target path as is done with
 * subdirectory creation the the watch owner must be moved up the target path.
 *
 * A path watch object on a directory owns the responsibility for watching for a
 * set of watch targets. It's targets may be in it's own directory or they may
 * be further down a path hierarchy branching from this directory (in other
 * words the basename component of the path watch appears somewhere in the chain
 * of path components leading to the target). One consequence of this
 * restriction is that every watch target belonging to a path watch object is a
 * descendant of this directory, hence the name "descendent watch".
 *
 * WARNING: Race Condition. There is an inherent race condition. We receive
 * notifications of modifications to the filesystem asynchronously which
 * triggers the processing performed here. We must assume the filesystem is
 * changing underneath us all the time. To minimize effects of this we defer as
 * long as possible the determination of existing directories and the
 * computation of the optimal watch directory for a given watch target. That
 * responsibility is given to the inotify_start_monitoring() function.
 */
static int relocate_watches(struct path_watch_t *pw)
{
    int error;
    hash_key_t *descendant, *descendant_keys;
    unsigned long i, count;
    char existing_directory_ancestor[PATH_MAX];
    char descendant_path[PATH_MAX];

    log_msg(LOG_DEBUG, _("relocate_watches for \"%s\"\n"), pw->path);

    /*
     * Because we may modify the descendant table as we iterate over all the
     * descendants we must use a temporary copy of the list of descendants.
     */
    if ((error = hash_keys(pw->descendant_path_table, &count, &descendant_keys)) != HASH_SUCCESS) {
        log_msg(LOG_ERROR, _("could not get descendant_path_table key list in \"%s\" (%s)\n"),
                pw->path, error_string(error));
        return error;
    }

    /* Iterate over all descendant watches of this path watch object */
    for (i = 0, descendant = descendant_keys; i < count; i++, descendant++) {
        if ((error = copy_path(descendant_path, descendant->str, sizeof(descendant_path))) != SUCCESS) {
            log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), descendant->str, error_string(error));
            continue;
        }
        /* Find what is currently the closest directory avaliable for watching the descendant */
        if ((error = find_existing_directory_ancestor(existing_directory_ancestor,
                                                      sizeof(existing_directory_ancestor),
                                                      descendant_path) != SUCCESS)) {
            log_msg(LOG_ERROR, _("failed find_existing_directory_ancestor \"%s\" (%s)\n"),
                    descendant_path, error_string(error));
            continue;
        }
        /*
         * If the closest existing directory is different than this directory
         * then move the watch from here to a closer directory by deleting it
         * from our table and re-creating the watch.
         */
        if (strcmp(descendant_path, existing_directory_ancestor) != 0) {
            log_msg(LOG_VERBOSE_DEBUG, _("existing watch \"%s\" not equal to new watch \"%s\"\n"),
                    descendant_path, existing_directory_ancestor);

            if ((error = hash_delete(pw->descendant_path_table, descendant)) != HASH_SUCCESS) {
                log_msg(LOG_ERROR, _("cannot delete from descendant_path_table \"%s\" (%s)\n"),
                        descendant_path, error_string(error));
                continue;
            }

            /* Set the watch on the optimal watch directory for this target */
            if ((error = inotify_start_monitoring(descendant_path)) != SUCCESS) {
                log_msg(LOG_ERROR, _("cannot inotify_start_monitoring for \"%s\" (%s)\n"),
                        descendant_path, error_string(error));
                continue;
            }
        }
    }
    free(descendant_keys);      /* clean up our temporary copy of the descendant list */

    /*
     * After processing all descendant watches it's possible they have all been
     * moved elsewhere leaving this directory without any targets to watch for,
     * if so delete ourself.
     */
    if ((error = destroy_path_watch_if_empty(&pw)) != SUCCESS) {
        log_msg(LOG_ERROR, _("destroy_path_watch_if_empty failed (%s)\n"),
                error_string(error));
    }

    return SUCCESS;
}


/**
 * Process an inotify MOVE (i.e. rename) event which come in pairs.
 * \param[in] event An inotify MOVE event to process
 * \param[in] path  The path name associated with the event
 * \return      Pointer to matching event if found, NULL otherwise
 *
 * Inotify MOVE (i.e. rename) events potentially come in pairs, one event for
 * the old name and one event for the new name. The cookie field in the event
 * matches the two events together. It is possible that either the old or the
 * new name is not known because the directory containing it did not have a
 * watch established on it (these are called "lost" rename events because either
 * the old or the new name has been lost). For those instances only one event
 * will be generated. When a MOVE event arrives we enter it in a cache where it
 * may be paired with it's matching mate. When entering an event if it's mate is
 * found then a struct is returned describing the pair and the pair is removed
 * from the cache. Otherwise NULL is returned indicating we must wait for the
 * other half of the pair.
 *
 * See \ref InotifyCookieCacheDoc.
 */
static struct inotify_cookie_cache_entry_t *inotify_cookie_cache_operator(struct inotify_event *event, const char *path)
{
    int error;
    int i;
    struct inotify_cookie_cache_entry_t *entry;
    static struct inotify_cookie_cache_entry_t result; /* FIXME */

    /* see if the cookie is present, if so remove it and return True */
    for (i = 0; i < n_cookies; i++) {
        if (inotify_cookie_cache[i].cookie == event->cookie) { /* Found, delete the entry */
            entry = &inotify_cookie_cache[i];
            if (event->mask & IN_MOVED_FROM) {
                entry->prev_watch_id = event->wd;
                if ((error = copy_path(entry->prev_path, path, sizeof(entry->prev_path))) != SUCCESS) {
                    log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), path, error_string(error));
                }
            } else if (event->mask & IN_MOVED_TO) {
                entry->new_watch_id = event->wd;
                if ((error = copy_path(entry->new_path, path, sizeof(entry->new_path))) != SUCCESS) {
                    log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), path, error_string(error));
                }
            }
            result = *entry;

            /* fill gap of deleted entry by shifting all entries above the gap downward */
            for (i++; i < n_cookies; i++) {
                inotify_cookie_cache[i - 1] = inotify_cookie_cache[i];
            }
            n_cookies--;
            return &result;
        }
    }
    /* Not Found */
    if (n_cookies == INOTIFY_COOKIE_CACHE_SIZE) {
         /* Cache full, remove oldest by shifting all entries down,
          * provide notification if requested. */
        if (inotify_lost_cookie_callback)
            inotify_lost_cookie_callback(&inotify_cookie_cache[0]);
        n_cookies--;
        for (i = 0; i < n_cookies; i++) {
            inotify_cookie_cache[i] = inotify_cookie_cache[i + 1];
        }
    }
    entry = &inotify_cookie_cache[n_cookies];
    entry->cookie = event->cookie;
    if (event->mask & IN_MOVED_FROM) {
        entry->prev_watch_id = event->wd;
        entry->new_watch_id = -1;
        if ((error = copy_path(entry->prev_path, path, sizeof(entry->prev_path))) != SUCCESS) {
            log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), path, error_string(error));
        }
        entry->new_path[0] = 0;
    } else if (event->mask & IN_MOVED_TO) {
        entry->prev_watch_id = -1;
        entry->new_watch_id = event->wd;
        entry->prev_path[0] = 0;
        if ((error = copy_path(entry->new_path, path, sizeof(entry->new_path))) != SUCCESS) {
            log_msg(LOG_ERROR, _("failed to copy path \"%s\" (%s)\n"), path, error_string(error));
        }
    }
    n_cookies++;
    return NULL;
}

/**
 * Flush any pending inotify MOVE (rename) events from the cache
 * \return void
 *
 * Inotify rename events which do not yet have a matching entry for either the
 * old or the new name are considered "lost" and persist in the cache waiting
 * for their matching mate (other member of the rename pair). This routine
 * flushes any pending rename events from the cache. By definition each flushed
 * event will be incomplete (either the old or the new path information was
 * lost). Flushed events are emited via the lost cookie callback. After flushing
 * the cache will be empty.
 *
 * See \ref InotifyCookieCacheDoc.
 */
static void flush_inotify_cookie_cache(void)
{
    int i;
    struct inotify_cookie_cache_entry_t *entry;

    for (i = 0; i < n_cookies; i++) {
        entry = &inotify_cookie_cache[i];
        if (inotify_lost_cookie_callback)
            inotify_lost_cookie_callback(entry);
    }
    n_cookies = 0;
}

/**
 * Write the watch path table to our log with formatted message prepended
 * \param[in] fmt printf style format followed by optional arguments used to
 *            identify the table.
 * \return    void
 */
static void log_watch_path_table(const char *fmt, ...)
{
    char buf[1024];
    va_list ap;
    char *watch_path_table_str = watch_path_table_string(watch_path_table);

    va_start(ap, fmt);
    if (fmt) {
        vsnprintf(buf, sizeof(buf), fmt, ap);
    } else {
        *buf = 0;
    }

    log_msg(LOG_DEBUG, _("pathname table: %s\n%s\n"), buf, watch_path_table_str);
    free(watch_path_table_str);
}

/**
 * Write the target table to our log with formatted message prepended
 * \param[in] fmt printf style format followed by optional arguments used to
 *            identify the table.
 * \return    void
 */
static void log_target_table(const char *fmt, ...)
{
    char buf[1024];
    va_list ap;
    char *targets = keys_string(target_table, "    ", "\n");

    va_start(ap, fmt);
    if (fmt) {
        vsnprintf(buf, sizeof(buf), fmt, ap);
    } else {
        *buf = 0;
    }

    log_msg(LOG_DEBUG, _("target table: %s\n%s\n"), buf, targets);
    free(targets);
}

/*****************************************************************************/
/****************************  Exported Functions  ***************************/
/*****************************************************************************/

/**
 * Initialize the inotify monitoring back end
 * \return SUCCESS (0) or non-zero error code otherwise
 */
int inotify_watch_init()
{
    int error;

    inotify_lost_cookie_callback = lost_rename_callback;

    if ((inotify_fd = inotify_init()) < 0) {
        error = errno;
        log_msg(LOG_ERROR, _("inotify_init() failed (%s)\n"), error_string(error));
        return error;
    }


    if ((error = hash_create(INITIAL_HASH_TABLE_SIZE, &watch_path_table, NULL)) != HASH_SUCCESS) {
        log_msg(LOG_ERROR, _("inotify_watch_init: cannot create pathname hash table\n"));
        return error;
    }

    if ((error = hash_create(INITIAL_HASH_TABLE_SIZE, &watch_id_table, NULL)) != HASH_SUCCESS) {
        log_msg(LOG_ERROR, _("inotify_watch_init: cannot create watch id hash table\n"));
        return error;
    }

    if ((error = hash_create(INITIAL_HASH_TABLE_SIZE, &target_table, NULL)) != HASH_SUCCESS) {
        log_msg(LOG_ERROR, _("%s: cannot create target hash table\n"));
        return error;
    }

    return SUCCESS;
}

/**
 * Close the inotify monitoring back end, stop all monitoring, free all resources
 * \return SUCCESS (0) or non-zero error code otherwise
 */
int inotify_watch_fini()
{
    unsigned long i, count;
    hash_entry_t *entries, *entry;
    struct path_watch_t *pw;

    flush_inotify_cookie_cache();

    hash_entries(watch_id_table, &count, &entries);
    for (i = 0, entry = entries; i < count; i++, entry++) {
        pw = entry->value.ptr;
        log_msg(LOG_VERBOSE_DEBUG, _("destroying [%d] \"%s\"\n"),  pw->watch_id, pw->path);
        destroy_path_watch(&pw);
    }
    free(entries);

    if (hash_count(watch_path_table) != 0) {
        log_msg(LOG_ERROR, _("watch_path_table not empty (%d) after removing all watches\n"),
                hash_count(watch_path_table));
    }

    if (hash_count(watch_id_table) != 0) {
        log_msg(LOG_ERROR, _("watch_id_table not empty (%d) after removing all watches\n"),
                hash_count(watch_id_table));
    }

    hash_destroy(watch_path_table);
    hash_destroy(watch_id_table);
    hash_destroy(target_table);
    close(inotify_fd);

    return SUCCESS;
}

/**
 * Return true if path parameter is a watch target
 * \param[in] path The path we're testing to see if it's a watch target
 * \return     True if path parameter is a watch target
 *
 * Note, This answers the question if the path is a target to monitor. In other
 * words it's something we've specifically been asked to monitor. Our
 * implementation will establish inotify watches as a consequence of monitoring
 * a target and is_path_watched() is correct way to ask if inotify is watching a
 * path as opposed to this function which reports if path is target to monitor.
 *
 * \see is_path_watched() Also see \ref VocabularyDoc for an explanation of
 * targets vs. watched objects.
 */
bool is_watch_target(const char *path)
{
    hash_key_t key;

    key.type = HASH_KEY_STRING;
    key.str = path;

    return hash_has_key(target_table, &key);
}

/**
 * Return true if the given path is being watched by inotify
 * \param[in] path The path to check for inotify watching
 * \return     true if the path is watched by inotify, false otherwise
 *
 * Note, this is distinct from asking if a path is target, a target is something
 * we've been asked to monitor. In the process of monitoring we will ask inotify
 * to watch certain directories which are not targets, but may contain targets.
 *
 * \see is_watch_target() Also see \ref VocabularyDoc for an explanation of
 * targets vs. watched objects.
 */
bool is_path_watched(const char* path)
{
    hash_key_t key;

    key.type = HASH_KEY_STRING;
    key.str = path;

    return hash_has_key(watch_path_table, &key);
}

/**
 * Translate error code to string description.
 * \param[in] error Error code whose string description is sought.
 * \return      string describing the error
 *
 * Note: IS_INOTIFY_WATCH_ERROR(error) should true otherwise the error code is
 * outside the set of values this function knows about. If the error code is not
 * recognized the string "unknown(XXX)" will be returned instead where XXX is
 * the decimal representation of the error code.
 */
const char *inotify_watch_error_string(int error)
{
    switch(error) {
    case SUCCESS:                                return _("success");
    case INOTIFY_WATCH_ERROR_NULL_WATCH:         return _("watch invalid, was NULL");
    case INOTIFY_WATCH_ERROR_WATCH_ID_NOT_FOUND: return _("could not look up watch id");
    case INOTIFY_WATCH_ALREADY_WATCHING:         return _("already being watched");
    case INOTIFY_WATCH_NOT_WATCHED:              return _("not being watched");
    }
    return NULL;
}

/**
 * Given an inotify event bitmask return a string of all the enabled flags
 * \param[in] mask Bitmask of inotify event flags
 * \param[in] separator String used to separate individual flags
 * \return  static string with each enabled flag separated by the separator string
 */
char *inotify_mask_string(unsigned int mask, const char *separator)
{
    static __thread char buf[1024]; /* thread local static buffer */
    char *p, *buf_end;
    size_t separator_len;
    unsigned int unknown;

    p = buf;                     /* current position in buffer */
    buf_end = &buf[sizeof(buf)]; /* non-inclusive end of buffer */
    separator_len = strlen(separator);
    *p = 0;

    /* validate there is nothing in the event mask we don't know about */
    unknown = mask & ~(IN_ACCESS | IN_MODIFY | IN_ATTRIB | IN_CLOSE_WRITE |
                        IN_CLOSE_NOWRITE | IN_OPEN | IN_MOVED_FROM | IN_MOVED_TO |
                        IN_CREATE | IN_DELETE | IN_DELETE_SELF | IN_MOVE_SELF |
                        IN_UNMOUNT | IN_Q_OVERFLOW | IN_IGNORED | IN_ONLYDIR |
                        IN_DONT_FOLLOW | IN_MASK_ADD | IN_ISDIR | IN_ONESHOT);

    if (unknown) p += snprintf(p, buf_end - p, "unknown bits=0x%x%s", unknown, separator);
    if (p >= buf_end) goto fail;

    if (mask & IN_ACCESS)        p += snprintf(p, buf_end - p, "ACCESS%s",        separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_MODIFY)        p += snprintf(p, buf_end - p, "MODIFY%s",        separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_ATTRIB)        p += snprintf(p, buf_end - p, "ATTRIB%s",        separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_CLOSE_WRITE)   p += snprintf(p, buf_end - p, "CLOSE_WRITE%s",   separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_CLOSE_NOWRITE) p += snprintf(p, buf_end - p, "CLOSE_NOWRITE%s", separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_OPEN)          p += snprintf(p, buf_end - p, "OPEN%s",          separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_MOVED_FROM)    p += snprintf(p, buf_end - p, "MOVED_FROM%s",    separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_MOVED_TO)      p += snprintf(p, buf_end - p, "MOVED_TO%s",      separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_CREATE)        p += snprintf(p, buf_end - p, "CREATE%s",        separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_DELETE)        p += snprintf(p, buf_end - p, "DELETE%s",        separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_DELETE_SELF)   p += snprintf(p, buf_end - p, "DELETE_SELF%s",   separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_MOVE_SELF)     p += snprintf(p, buf_end - p, "MOVE_SELF%s",     separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_UNMOUNT)       p += snprintf(p, buf_end - p, "UNMOUNT%s",       separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_Q_OVERFLOW)    p += snprintf(p, buf_end - p, "Q_OVERFLOW%s",    separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_IGNORED)       p += snprintf(p, buf_end - p, "IGNORED%s",       separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_ONLYDIR)       p += snprintf(p, buf_end - p, "ONLYDIR%s",       separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_DONT_FOLLOW)   p += snprintf(p, buf_end - p, "DONT_FOLLOW%s",   separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_MASK_ADD)      p += snprintf(p, buf_end - p, "MASK_ADD%s",      separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_ISDIR)         p += snprintf(p, buf_end - p, "ISDIR%s",         separator);
    if (p >= buf_end) goto fail;
    if (mask & IN_ONESHOT)       p += snprintf(p, buf_end - p, "ONESHOT%s",       separator);
    if (p >= buf_end) goto fail;

    if (p > buf) p[-separator_len] = 0;

    return buf;
 fail:
    /* exhausted the buffer; NULL terminate then return truncated string */
    buf_end[-1] = 0;   /* should already be NULL terminated, but be safe */
    return buf;
}

/**
 * Render a path_watch_t struct as a string
 * \param[in] pw The path watch object to render as a string
 * \return malloc'ed string, caller must free
 */
char *path_watch_string(struct path_watch_t *pw)
{
    char *files;
    char *fw_string;
    int len;

    if (!pw) return strdup("(null)");

    files = keys_string(pw->descendant_path_table, "        ", "\n");

    len = asprintf(&fw_string, "[%d] \"%s\" n_files=%ld%s%s",
                   pw->watch_id, pw->path,
                   hash_count(pw->descendant_path_table),
                   hash_count(pw->descendant_path_table) ? "\n" : "", files);

    free(files);
    return fw_string;
}


/**
 * Given a path lookup the path watch object associated with it.
 * \param[in] path The path whose matching watch object is desired.
 * \return     Pointer to the path watch object or NULL if not found.
 */
struct path_watch_t *find_watch_by_path(const char* path)
{
    int error;
    hash_key_t key;
    hash_value_t value;
    struct path_watch_t *pw;

    key.type = HASH_KEY_STRING;
    key.str = path;

    if ((error = hash_lookup(watch_path_table, &key, &value)) != HASH_SUCCESS) {
        log_msg(LOG_VERBOSE_DEBUG, _("cannot find pathname \"%s\"\n"),  path);
        return NULL;
    }

    pw = (struct path_watch_t *) value.ptr;
    return pw;
}

/**
 * Given an inotify watch id lookup the path watch object associated with it.
 * \param[in] watch_id The watch_id assigned by inotify to identify the watch
 * \return         Pointer to the path watch object or NULL if not found.
 */
struct path_watch_t *find_watch_by_watch_id(int watch_id)
{
    int error;
    hash_key_t key;
    hash_value_t value;
    struct path_watch_t *pw;

    key.type = HASH_KEY_ULONG;
    key.ul = watch_id;

    if ((error = hash_lookup(watch_id_table, &key, &value)) != HASH_SUCCESS) {
        log_msg(LOG_DEBUG, _("cannot find watch_id %d\n"),  watch_id);
        return NULL;
    }

    pw = (struct path_watch_t *) value.ptr;
    return pw;
}

/**
 * Start monitoring the target path with inotify
 * \param[in] path_arg The pathname to monitor, it will be normalized and made absolute
 * \return         SUCCESS (0) or non-zero error code otherwise
 */
int inotify_start_monitoring(const char *path_arg)
{
    int error;
    char path[PATH_MAX];
    hash_key_t key;
    hash_value_t value;
    char existing_directory_ancestor[PATH_MAX];
    struct path_watch_t *pw;

    /* Normalize the path passed to us */
    if ((error = make_normalized_absolute_path(path, sizeof(path), path_arg)) != SUCCESS) {
        log_msg(LOG_ERROR, _("failed make_normalized_absolute_path from \"%s\" (%s)\n"),
                path_arg, error_string(error));
        return error;
    }

    /* Assure we're not already watching this path */
    if (is_watch_target(path)) {
        error = INOTIFY_WATCH_ALREADY_WATCHING;
        log_msg(LOG_ERROR, _("path is already being watched \"%s\"\n"),  path);
        return error;
    }

    log_msg(LOG_INFO, _("watching target \"%s\"\n"),  path);

    /*
     * We watch the directory which contains the path, not the path itself. To
     * establish a watch on a directory the directory must exist in the
     * filesystem so we search for the nearest directory ancestor containing the
     * path which exists in the file system.  This is where the watch will be
     * established.
     *
     * If the directory containing the path does not yet exist we watch the
     * closest directory to the final path component and will move the watch to
     * a closer directory when the missing directory component is later created
     * in the directory which was chosen to watch.
     *
     * FIXME
     * WARNING: Race Condition. If the missing directory is created before the
     * watch is established we won't see the directory creation event which
     * tells us we can move the watch directory closer to the target. The only
     * way to protect against this is to periodically walk all the watch targets
     * and and adjust their watch directories.
     */
    if ((error = find_existing_directory_ancestor(existing_directory_ancestor,
                                                  sizeof(existing_directory_ancestor),
                                                  path) != SUCCESS)) {
        log_msg(LOG_ERROR, _("failed find_existing_directory_ancestor \"%s\" (%s)\n"),
                path, error_string(error));
        return error;
    }

    /*
     * If we're already watching the selected directory get the watch object
     * previously created for watching that directory, otherwise create a new
     * watch object for the directory.
     */
    if ((pw = find_watch_by_path(existing_directory_ancestor)) == NULL) {
        if ((error = new_path_watch(existing_directory_ancestor, &pw)) != SUCCESS) {
            log_msg(LOG_ERROR, _("could not allocate new watch for \"%s\" (%s)\n"),
                    existing_directory_ancestor, error_string(error));
            return error;
        }
    }

    /* Do some basic bookkeeping */

    /* Add the path to our list of targets. */
    if ((error = add_path_to_target_list(path)) != SUCCESS) {
        log_msg(LOG_ERROR, _("could not insert path into target table \"%s\" (%s)\n"),
                pw->path, error_string(error));
        inotify_rm_watch(inotify_fd, pw->watch_id);
        free_path_watch(&pw);
        return error;
    }

    /* Add the watch object to our list of directories we're watching. */
    if ((error = track_path_watch(pw)) != SUCCESS) {
        log_msg(LOG_ERROR, _("could not insert watch into tables for \"%s\" (%s)\n"),
                pw->path, error_string(error));
        inotify_rm_watch(inotify_fd, pw->watch_id);
        free_path_watch(&pw);
        return error;
    }

    log_msg(LOG_DEBUG, _("adding path \"%s\" to descendant_path_table for directory \"%s\"\n"),
            path, pw->path);

    /* Add the path to the list of targets the watch object is responsible for watching (e.g. descendants). */
    key.type = HASH_KEY_STRING;
    key.str = path;
    value.type = HASH_VALUE_UNDEF;

    if ((error = hash_enter(pw->descendant_path_table, &key, &value)) != HASH_SUCCESS) {
        log_msg(LOG_ERROR, _("cannot add path \"%s\" to path_watch_t descendant_path_table \"%s\" (%s)\n"),
                path, pw->path, error_string(error));
        return error;
    }

    return SUCCESS;
}

/**
 * Stop monitoring the target path with inotify
 * \param[in] path_arg The pathname cease monitoring, it will be normalized and made absolute
 * \return         SUCCESS (0) or non-zero error code otherwise
 */
int inotify_stop_monitoring(const char *path_arg)
{
    int error;
    char path[PATH_MAX];
    unsigned long i, count;
    hash_key_t key;
    hash_entry_t *entries, *entry;
    struct path_watch_t *pw;
    int path_count;

    if ((error = make_normalized_absolute_path(path, sizeof(path), path_arg)) != SUCCESS) {
        log_msg(LOG_ERROR, _("failed make_normalized_absolute_path from \"%s\" (%s)\n"),
                path_arg, error_string(error));
        return error;
    }

    if (!is_watch_target(path)) {
        error = INOTIFY_WATCH_NOT_WATCHED;
        log_msg(LOG_ERROR, _("path was not being watched \"%s\"\n"),  path);
        return error;
    }

    log_msg(LOG_INFO, _("removing watch target \"%s\"\n"),  path);

    key.type = HASH_KEY_STRING;
    key.str = path;

    path_count = 0;
    hash_entries(watch_id_table, &count, &entries);
    for (i = 0, entry = entries; i < count; i++, entry++) {
        pw = entry->value.ptr;

        if (hash_has_key(pw->descendant_path_table, &key)) {
            path_count++;
            if ((error = hash_delete(pw->descendant_path_table, &key)) != HASH_SUCCESS) {
                log_msg(LOG_ERROR, _("cannot delete path \"%s\" from path_watch_t descendant_path_table \"%s\" (%s)\n"),
                        path, pw->path, error_string(error));
            }
            if ((error = destroy_path_watch_if_empty(&pw)) != SUCCESS) {
                log_msg(LOG_ERROR, _("destroy_path_watch_if_empty failed (%s)\n"), error_string(error));
            }
        }
    }
    free(entries);

    if (path_count != 1) {
        log_msg(LOG_ERROR, _("found %d instances of \"%s\" but expected exactly one\n"),
                path_count, path);
    }

    if ((error = remove_path_from_target_list(path)) != SUCCESS) {
        log_msg(LOG_ERROR, _("could not remove path from target table \"%s\" (%s)\n"),
                path, error_string(error));
    }

    return error;
}


/**
 * Return the file descriptor used by the inotify back end
 * \return Integer file descriptor used to read inotify events
 *
 * The inotify file descriptor is used to read inotify events.
 */
int get_inotify_fd()
{
    return inotify_fd;
}

/**
 * Loop used to read inotify events and dispatch them.
 * \return SUCCESS (0) or non-zero error code otherwise
 */
int read_events()
{
    char buf[1024 * (INOTIFY_EVENT_SIZE + 16)]; /* reasonable guess as to size of 1024 events */
    int len, error, i;
    bool done;

    /*
     * The behavior when the buffer given to read(2) is too small to return information
     * about the next event depends on the kernel version: in kernels before 2.6.21,
     * read(2) returns 0; since kernel 2.6.21, read(2) fails with the error EINVAL.
     */

    done = false;
    while (!done) {
        len = read (inotify_fd, buf, sizeof(buf));
        i = 0;
        if (len <= 0) {
            error = errno;
            if (error == EINTR || error == EAGAIN) { /* need to reissue system call */
                continue;
            }
            else if (error == EINVAL || len == 0) {
                log_msg(LOG_ERROR, _("failed, buffer too small (%s)\n"),
                        error_string(error));
                return error;
            } else {
                log_msg(LOG_ERROR, _("failed (%s)\n"),
                        error_string(error));
                return error;
            }
        }
        while (i < len) {
            struct inotify_event *event;

            event = (struct inotify_event *) &buf[i];

            process_event(event);
            i += INOTIFY_EVENT_SIZE + event->len;
        }
        done = true;
    }
    return SUCCESS;
}

/**
 * Register a callback to receive log watch events
 * \param[in]  callback The callback which will be invoked to send a log watch event.
 * \return          The previous callback pointer.
 */
lwatch_event_callback_t register_lwatch_event_callback(lwatch_event_callback_t callback)
{
    lwatch_event_callback_t prev_callback = lwatch_event_callback;
    lwatch_event_callback = callback;
    return prev_callback;
}

---