/***
 *
 *  ipv4/tcp/timerwheel.c - timerwheel implementation for RTnet
 *
 *  Copyright (C) 2009 Vladimir Zapolskiy <vladimir.zapolskiy@siemens.com>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License, version 2, as
 *  published by the Free Software Foundation.
 *
 *  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.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */

#include <linux/delay.h>
#include <linux/slab.h>

#include <rtdm/driver.h>
#include "timerwheel.h"

static struct {
	/* timer pivot task */
	rtdm_task_t pivot_task;

	/* time length for one period of rotation of timerwheel */
	nanosecs_rel_t timeout;

	/* timer wheel slots for storing timers up to timerwheel_timeout */
	unsigned int slots;

	/* timer wheel interval timeout */
	nanosecs_rel_t interval;

	/* timer wheel interval timeout */
	unsigned int interval_base;

	/* timerwheel array */
	struct list_head *ring;

	/* timerwheel slot counter */
	unsigned int current_slot;

	/* timerwheel current slot lock */
	rtdm_lock_t slot_lock;
} wheel;

static struct timerwheel_timer *timerwheel_get_from_current_slot(void)
{
	struct timerwheel_timer *timer = NULL;
	struct list_head *slot_list;
	rtdm_lockctx_t context;

	rtdm_lock_get_irqsave(&wheel.slot_lock, context);

	slot_list = &wheel.ring[wheel.current_slot];

	if (!list_empty(slot_list)) {
		timer = list_first_entry(slot_list, struct timerwheel_timer,
					 link);
		list_del(&timer->link);
		timer->slot = TIMERWHEEL_TIMER_UNUSED;
		timer->refcount++;
	}

	rtdm_lock_put_irqrestore(&wheel.slot_lock, context);

	return timer;
}

int timerwheel_add_timer(struct timerwheel_timer *timer, nanosecs_rel_t expires)
{
	rtdm_lockctx_t context;
	int slot;

	slot = expires >> wheel.interval_base;

	if (slot >= wheel.slots)
		return -EINVAL;

	rtdm_lock_get_irqsave(&wheel.slot_lock, context);

	/* cancel timer if it's still running */
	if (timer->slot >= 0)
		list_del(&timer->link);

	slot = slot + wheel.current_slot;
	if (slot >= wheel.slots)
		slot = slot - wheel.slots;

	list_add_tail(&timer->link, &wheel.ring[slot]);
	timer->slot = slot;

	rtdm_lock_put_irqrestore(&wheel.slot_lock, context);

	return 0;
}

static int timerwheel_sleep(void)
{
	int ret;

	ret = rtdm_task_sleep(wheel.interval);
	if (ret < 0)
		return ret;

	wheel.current_slot++;
	if (wheel.current_slot == wheel.slots)
		wheel.current_slot = 0;

	return 0;
}

static void timerwheel_pivot(void *arg)
{
	struct timerwheel_timer *timer;
	int ret;

	while (1) {
		ret = timerwheel_sleep();
		if (ret < 0) {
			rtdm_printk(
				"timerwheel: timerwheel_pivot interrupted %d\n",
				-ret);
			break;
		}

		while ((timer = timerwheel_get_from_current_slot())) {
			timer->handler(timer->data);

			smp_mb();
			timer->refcount--;
		}
	}
}

int timerwheel_remove_timer(struct timerwheel_timer *timer)
{
	rtdm_lockctx_t context;
	int ret;

	rtdm_lock_get_irqsave(&wheel.slot_lock, context);

	if (timer->slot >= 0) {
		list_del(&timer->link);
		timer->slot = TIMERWHEEL_TIMER_UNUSED;
		ret = 0;
	} else
		ret = -ENOENT;

	rtdm_lock_put_irqrestore(&wheel.slot_lock, context);

	return ret;
}

void timerwheel_remove_timer_sync(struct timerwheel_timer *timer)
{
	u64 interval_ms = wheel.interval;

	do_div(interval_ms, 1000000);

	timerwheel_remove_timer(timer);

	while (timer->refcount > 0)
		msleep(interval_ms);
}

/*
  timeout     - maximum expiration timeout for timers
  granularity - is an exponent of 2 representing nanoseconds for
  one wheel tick
  heapsize    - is a number of timers to allocate
*/
int __init timerwheel_init(nanosecs_rel_t timeout, unsigned int granularity)
{
	int i;
	int err;

	/* the least possible slot timeout is set for 1ms */
	if (granularity < 10)
		return -EINVAL;

	wheel.timeout = timeout;
	wheel.interval_base = granularity;
	wheel.slots = (timeout >> granularity) + 1;
	wheel.interval = (1 << granularity);
	wheel.current_slot = 0;

	wheel.ring =
		kmalloc(sizeof(struct list_head) * wheel.slots, GFP_KERNEL);
	if (!wheel.ring)
		return -ENOMEM;

	for (i = 0; i < wheel.slots; i++)
		INIT_LIST_HEAD(&wheel.ring[i]);

	rtdm_lock_init(&wheel.slot_lock);

	err = rtdm_task_init(&wheel.pivot_task, "rttcp timerwheel",
			     timerwheel_pivot, NULL, 1, 0);
	if (err) {
		printk("timerwheel: error on pivot task initialization: %d\n",
		       err);
		kfree(wheel.ring);
	}

	return err;
}

void timerwheel_cleanup(void)
{
	rtdm_task_destroy(&wheel.pivot_task);
	kfree(wheel.ring);
}