/*
 * Inode based directory notifications for Linux.
 *
 * Copyright (C) 2004 John McCutchan
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2, or (at your option) any
 * later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 */

#include <linux/bitops.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/spinlock.h>
#include <linux/slab.h>
#include <linux/fs.h>
#include <linux/namei.h>
#include <linux/poll.h>
#include <linux/miscdevice.h>
#include <linux/device.h>
#include <linux/init.h>
#include <linux/types.h>
#include <linux/stddef.h>
#include <linux/kernel.h>
#include <linux/list.h>
#include <linux/inotify.h>

/* TODO:
 * change umount code
 * write user space test app
 * get more events sent to the queue
 * 	rename
 * 	move
 * 	close
 * 	open
 * 	unmount
 */

#define MAX_INOTIFY_DEVS 8 /* We only support 8 watchers */
#define MAX_INOTIFY_DEV_INODES 128 /* A watcher can only be watching 128 inodes */
#define MAX_INOTIFY_QUEUED_EVENTS 256 /* Only the first 256 events will be queued */
#define __BITMASK_SIZE (MAX_INOTIFY_DEV_INODES / 8)

static atomic_t watcher_count;

/* A list of these structures is attached to each inotify_device
 * each item in the list represents an inode being watched by
 *
 * the device
 */
struct inotify_watch {
	struct list_head	list;
	struct inode *		inode;
	int			wid;
};
#define list_to_inotify_watch(pos) list_entry((pos),struct inotify_watch,list)

/* A list of these structures is attached to each inode that is being watched.
 * each item in the list represents a unique watcher.
 * it tell us what events we are looking at and what device this watcher belongs to
 */
struct inotify_inode_watcher {
	struct list_head        list;
	unsigned long           mask;
	int 			wid;
	struct inode *          inode;
	void *                  private_data; // the driver instance
};
#define list_to_inotify_inode_watcher(pos) list_entry((pos), struct inofiy_inode_watcher, list)

/* A list of these is attached to each instance of the driver
 * when the drivers read() gets called, this list is walked and
 * all events that can fit in the buffer get delivered
 */
struct inotify_event {
        struct list_head        list;
	int			wid; // watcher id
        unsigned long           mask;
};
#define list_to_inotify_event(pos) list_entry((pos), struct inotify_event, list)

/* For each inotify device we need to keep a list of events queued on it,
 * a list of inodes that we are watching and other stuff.
 */
struct inotify_device {
	struct list_head *	events;
	atomic_t		event_count;
	struct list_head *	watch;
	atomic_t		watch_count;
	char 			read_state;
	wait_queue_head_t 	wait;
	spinlock_t		lock;
	void *			bitmask;
};

static struct inotify_inode_watcher *inotify_inode_find_watcher (struct inotify_device *dev, struct inode *inode)
{
	struct inotify_inode_watcher *watcher;

	spin_lock(&inode->i_lock);
	list_for_each_entry (watcher, &inode->watchers, list) {
		/* This is the watcher from this device */
		if (watcher->private_data == dev)
		{
			spin_unlock(&inode->i_lock);
			return watcher;
		}
	}
	spin_unlock(&inode->i_lock);
	return NULL;
}

static int inotify_inode_add_watcher (struct inotify_device *dev, struct inode *inode, int wid, unsigned long mask)
{
	int error;
	struct inotify_inode_watcher *watcher;

	watcher = inotify_inode_find_watcher(dev, inode);

	error = 0;


	spin_lock(&inode->i_lock);

		/* Check if we are already watching this inode */
	if (watcher) {
		watcher->mask = mask;
	} else if (atomic_read(&inode->watcher_count) < MAX_INOTIFY_DEV_INODES) {
		watcher = kmalloc(sizeof(struct inotify_inode_watcher), GFP_KERNEL);
		watcher->private_data = dev;
		watcher->inode = inode;
		watcher->mask = mask;
		watcher->wid = wid;
		
		atomic_inc(&inode->watcher_count);
		list_add(&watcher->list, &inode->watchers);
	} else {
		error = -ENOSPC;
		goto out;
	}

	inotify_inode_update_mask (inode);
out:
	spin_unlock(&inode->i_lock);
	return error;
}

static void inotify_inode_rm_watcher (struct inotify_device *dev, struct inode *inode)
{
	struct inotify_inode_watcher *watcher;

	watcher = inotify_inode_find_watcher(dev, inode);

	spin_lock(&inode->i_lock);
	if (NULL != watcher) {
		list_del(&watcher->list);
		kfree(watcher);

		atomic_dec(&inode->watcher_count);
	}
	spin_unlock(&inode->i_lock);
}

static struct inotify_watch *inotify_dev_find_watcher (struct inotify_device *dev, int wid)
{	
	struct inotify_watch *watch;

	list_for_each_entry(watch, dev->watch, list) {
		if (watch->wid == wid) {
			return watch;
		}
	}

	return NULL;
}

static char inotify_dev_is_watching_inode (struct inotify_device *dev, struct inode *inode)
{
	struct inotify_watch *watch;

	list_for_each_entry(watch, dev->watch, list) {
		if (watch->inode == inode) {
			return 1;
		}
	}

	return 0;
}

static struct inode *inotify_dev_find_inode (struct inotify_device *dev, int wid)
{
	struct inotify_watch *watch;

	list_for_each_entry(watch, dev->watch, list) {
		if (watch->wid == wid) {
			return watch->inode;
		}
	}

	return NULL;
}

static int inotify_dev_add_watcher (struct inotify_device *dev, int wid, struct inode *inode)
{
	int error;
	struct inotify_watch *watch;

	error = 0;

	/* We only allow a device to watch an inode once */
	if (inotify_dev_is_watching_inode (dev, inode)) {
		goto out;
	}

	/* Make sure we aren't watching too many inodes */
	if (atomic_read (&dev->watch_count) < MAX_INOTIFY_DEV_INODES) {
		watch = kmalloc(sizeof(struct inotify_watch), GFP_KERNEL);
		watch->inode = inode;
		watch->wid = wid;

		atomic_inc(&dev->watch_count);
		list_add(&watch->list, dev->watch);
	} else {
		error = -ENOSPC;
	}
	
out:
	return error;
}

static void inotify_dev_rm_watcher (struct inotify_device *dev, int wid)
{
	struct inotify_watch *watch;

	watch = inotify_dev_find_watcher(dev, wid);

	if (NULL != watch) {
		list_del(&watch->list);
		kfree(watch);

		atomic_dec(&dev->watch_count);
	} 
}

#define inotify_dev_has_events(dev) (dev->events && !list_empty(dev->events))

static void inotify_dev_event_dequeue (struct inotify_device *dev)
{
	struct inotify_event *event;

	if (list_empty(dev->events)) {
		return;
	}

	/* Get the first entry from the event queue */
	event = list_to_inotify_event(dev->events->next);
	list_del(&event->list);
	kfree(event);
	atomic_dec(&dev->event_count);
}

static void inotify_dev_event_queue (struct inotify_device *dev, int wid, unsigned long mask)
{
	struct inotify_event *event;

	/* If we have MAX_INOTIFY_QUEUED_EVENTS events queued, then we just drop
	 * the event. It is the the clients responsibility to read from the
	 * device often enough
	 */
	if (atomic_read(&dev->event_count) < MAX_INOTIFY_QUEUED_EVENTS) {
		event = kmalloc(sizeof(struct inotify_event), GFP_KERNEL);
		event->wid = wid;
		event->mask = mask;

		list_add_tail (&event->list, dev->events);

		atomic_inc(&dev->event_count);
	} 
}

/* Kernel API */
void inotify_inode_queue_event (struct inode *inode, unsigned long mask)
{
	struct inotify_inode_watcher *watcher;

	/* If this inode isn't interested in the event */
	if (!(inode->watchers_mask & mask)) {
		return;
	}

	list_for_each_entry(watcher, &inode->watchers, list) {
		if (watcher->mask & mask) {
			inotify_dev_event_queue(watcher->private_data, watcher->wid, mask);
		}
	}
}
EXPORT_SYMBOL_GPL(inotify_inode_queue_event);

void inotify_dentry_queue_event(struct dentry *dentry, unsigned long mask)
{
	struct dentry *parent;

	spin_lock(&dentry->d_lock);
	dget (dentry->d_parent);
	parent = dentry->d_parent;
	inotify_inode_queue_event(parent->d_inode, mask);
	dput (parent);
	spin_unlock(&dentry->d_lock);
}
EXPORT_SYMBOL_GPL(inotify_dentry_queue_event);


void inotify_inode_update_mask(struct inode *inode)
{
	struct inotify_inode_watcher *watcher;
	unsigned long new_mask;

	new_mask = 0;
	list_for_each_entry(watcher, &inode->watchers, list) {
		new_mask |= watcher->mask;
	}
	inode->watchers_mask = new_mask;
}
EXPORT_SYMBOL_GPL(inotify_inode_update_mask);

/* The driver interface is implemented below */

#define INOTIFY_READ_STATE_WID  0
#define INOTIFY_READ_STATE_MASK 1

static ssize_t inotify_read(struct file *file, char *buf,
			   size_t count, loff_t *pos) {
	struct inotify_device *dev;
	size_t out;
	unsigned long flags;
	char *obuf;

	out = 0;
	obuf = buf;

	dev = file->private_data;

	spin_lock_irqsave(&dev->lock, flags);

	if (!inotify_dev_has_events(dev)) {
		goto out;
	}

	while (out < count && inotify_dev_has_events (dev)) {
		struct inotify_event *event;

		event = list_to_inotify_event(dev->events->next);

		switch (dev->read_state) {
			case INOTIFY_READ_STATE_WID:
				if (sizeof(event->wid) + out > count) {
					break;
				}
				if (put_user(event->wid, buf)) {
					out = -EFAULT;
					goto out;
				}
				buf += sizeof(event->wid);
				dev->read_state++;
			break;
			case INOTIFY_READ_STATE_MASK:
				if (sizeof(event->mask) + out > count) {
					break;
				}
				if (put_user(event->mask, buf)) {
					out = -EFAULT;
					goto out;
				}
				buf += sizeof(event->mask);
				dev->read_state = INOTIFY_READ_STATE_WID;
				/* We have finished delivering the complete event, so dequeue it */
				inotify_dev_event_dequeue(dev);
			break;
			default:
				/* BUG */
			break;
		}
		out = buf - obuf;
	}

	out = buf - obuf;
out:
	spin_unlock_irqrestore(&dev->lock, flags);
	return out;
}

static unsigned int inotify_poll(struct file *file, poll_table *wait) {
	struct inotify_device *dev;

	dev = file->private_data;

	poll_wait(file, &dev->wait, wait);

	if (inotify_dev_has_events(dev))
		return POLLIN | POLLRDNORM;

	return 0;
}

static int inotify_open(struct inode *inode, struct file *file) {
	struct inotify_device *dev;

	if (atomic_read(&watcher_count) == MAX_INOTIFY_DEVS)
		return -ENODEV;

	atomic_inc(&watcher_count);

	dev = kmalloc(sizeof(struct inotify_device), GFP_KERNEL);
	dev->events = kmalloc(sizeof(struct list_head), GFP_KERNEL);
	INIT_LIST_HEAD(dev->events);
	atomic_set(&dev->event_count, 0);
	dev->watch = kmalloc(sizeof(struct list_head), GFP_KERNEL);
	INIT_LIST_HEAD(dev->watch);
	atomic_set(&dev->watch_count, 0);
	dev->read_state = INOTIFY_READ_STATE_WID;
	init_waitqueue_head(&dev->wait);
	dev->lock = SPIN_LOCK_UNLOCKED;
	dev->bitmask = kmalloc(__BITMASK_SIZE, GFP_KERNEL);
	memset(dev->bitmask, 0, __BITMASK_SIZE);

	file->private_data = dev;

	return 0;
}

static void inotify_release_all_watchers (struct inotify_device *dev)
{
	struct inotify_watch *watch;

	list_for_each_entry(watch, dev->watch, list) {
		/* Remove the watcher from the inode */
		inotify_inode_rm_watcher(dev, watch->inode);
		/* Remove the inode from the device */
		inotify_dev_rm_watcher(dev, watch->wid);

	}
}

static void inotify_release_all_events (struct inotify_device *dev)
{
	while (inotify_dev_has_events(dev)) {
		inotify_dev_event_dequeue(dev);
	}
}


static int inotify_release(struct inode *inode, struct file *file)
{
	if (file->private_data) {
		struct inotify_device *dev;

		dev = (struct inotify_device *)file->private_data;

		inotify_release_all_watchers(dev);
		kfree(dev->watch);

		inotify_release_all_events(dev);
		kfree(dev->events);

		kfree (dev);
	}

	atomic_dec(&watcher_count);
	return 0;
}

static int inotify_find_inode (const char __user *dirname, struct inode **inode)
{
	struct nameidata nd;
	int error;

	error = __user_walk (dirname, LOOKUP_FOLLOW|LOOKUP_DIRECTORY, &nd);
	if (error) 
		goto out;

	*inode = nd.dentry->d_inode;
	__iget (*inode);
	path_release(&nd);
out:
	return error;
}

static int inotify_get_wid (struct inotify_device *dev)
{
	int wid;

	if (!dev)
		return -1;

	wid = find_first_zero_bit (dev->bitmask, __BITMASK_SIZE);

	set_bit (wid, dev->bitmask);

	return wid;
}

static int inotify_put_wid (struct inotify_device *dev, int wid)
{
	if (!dev)
		return -1;

	clear_bit (wid, dev->bitmask);

	return 0;
}

static int inotify_watch(struct inotify_device *dev, struct inotify_watch_request *request)
{
	int err;
	int wid;
	struct inode *inode;
	err = 0;

	err = inotify_find_inode (request->dirname, &inode);

	if (err)
		goto out;

	if (!S_ISDIR(inode->i_mode)) {
		err = -ENOTDIR;
		goto iput_and_out;
	}

	wid = inotify_get_wid (dev);

	if (wid < 0) {
		err = -ENOSPC;
		goto iput_and_out;
	}

	err = inotify_inode_add_watcher(dev, inode, wid, request->mask);

	if (err)
		goto iput_and_out;

	err = inotify_dev_add_watcher(dev, wid, inode);

	if (err)
		goto iput_and_out;

iput_and_out:
	iput (inode);
out:
	return err;
}

static int inotify_ignore(struct inotify_device *dev, int wid)
{
	struct inode *inode;
	int err;
	err = 0;

	inode = inotify_dev_find_inode (dev, wid);

	if (!inode) {
		err = -EINVAL;
		goto out;
	}

	inotify_inode_rm_watcher(dev, inode);
	inotify_dev_rm_watcher(dev, wid);
	inotify_put_wid (dev, wid);
out:
	return err;
}

static int inotify_ioctl(struct inode *ip, struct file *fp,
			 unsigned int cmd, unsigned long arg) {
	int err;
	unsigned long flags;
	struct inotify_device *dev;
	struct inotify_watch_request *request;
	int wid;

	dev = fp->private_data;

	spin_lock_irqsave(&dev->lock, flags);

	err = 0;

	if (_IOC_TYPE(cmd) != INOTIFY_IOCTL_MAGIC) return -EINVAL;
	if (_IOC_NR(cmd) > INOTIFY_IOCTL_MAXNR) return -EINVAL;

	if (_IOC_DIR(cmd) & _IOC_READ)
		err = !access_ok(VERIFY_WRITE, (void *)arg, _IOC_SIZE(cmd));
	if (_IOC_DIR(cmd) & _IOC_WRITE)
		err = !access_ok(VERIFY_READ, (void *)arg, _IOC_SIZE(cmd));

	if (err) {
		err = -EFAULT;
		goto out;
	}


	err = -EINVAL;

	switch (cmd) {
		case INOTIFY_WATCH:
			request = kmalloc(sizeof(struct inotify_watch_request), GFP_KERNEL);
			if (copy_from_user(request, (void *)arg, sizeof(struct inotify_watch_request))) {
				err = -EFAULT;
				goto out;
			}

			printk(KERN_ALERT "inotify WATCH: %p %ld\n", request->dirname, request->mask);
			err = inotify_watch(dev, request);
			kfree (request);
		break;
		case INOTIFY_IGNORE:
			if (copy_from_user(&wid, (void *)arg, sizeof(int))) {
				err = -EFAULT;
				goto out;
			}

			printk(KERN_ALERT "inotify IGNORE: %d\n", wid);
			err = inotify_ignore(dev, wid);
		break;
	}

out:
	spin_unlock_irqrestore(&dev->lock, flags);
	return err;
}

static struct file_operations inotify_fops = {
	.owner		= THIS_MODULE,
	.read		= inotify_read,
	.poll		= inotify_poll,
	.open		= inotify_open,
	.release	= inotify_release,
	.ioctl		= inotify_ioctl,
};

struct miscdevice inotify_device = {
	.minor  = -1, // automatic
	.name	= "inotify",
	.fops	= &inotify_fops,
};


static int __init inotify_init (void)
{
	int ret;

	ret = misc_register(&inotify_device);

	if (ret) {
		goto out;
	}

	printk(KERN_ALERT "inotify 0.2 startup\n");
out:
	return ret;
}

static void inotify_exit (void)
{
	misc_deregister (&inotify_device);
	printk(KERN_ALERT "inotify 0.2 shutdown\n");
}


MODULE_AUTHOR("John McCutchan <ttb@tentacle.dhs.org>");
MODULE_DESCRIPTION("Inode event driver");
MODULE_LICENSE("GPL");

module_init (inotify_init);
module_exit (inotify_exit);