/*
 * Copyright (C) 2010-2011, 2013-2014 ARM Limited. All rights reserved.
 * 
 * This program is free software and is provided to you under the terms of the GNU General Public License version 2
 * as published by the Free Software Foundation, and any use by you of this program is subject to the terms of such GNU licence.
 * 
 * A copy of the licence is included with the program, and can also be obtained from Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "mali_kernel_common.h"
#include "mali_osk.h"
#include "ump_osk.h"
#include "ump_kernel_common.h"
#include "ump_kernel_types.h"
#include "ump_kernel_random_mapping.h"

#include <linux/random.h>
#include <linux/rbtree.h>
#include <linux/sched.h>
#include <linux/jiffies.h>


static ump_dd_mem *search(struct rb_root *root, int id)
{
	struct rb_node *node = root->rb_node;

	while (node) {
		ump_dd_mem *e = container_of(node, ump_dd_mem, node);

		if (id < e->secure_id) {
			node = node->rb_left;
		} else if (id > e->secure_id) {
			node = node->rb_right;
		} else {
			return e;
		}
	}

	return NULL;
}

static mali_bool insert(struct rb_root *root, int id, ump_dd_mem *mem)
{
	struct rb_node **new = &(root->rb_node);
	struct rb_node *parent = NULL;

	while (*new) {
		ump_dd_mem *this = container_of(*new, ump_dd_mem, node);

		parent = *new;
		if (id < this->secure_id) {
			new = &((*new)->rb_left);
		} else if (id > this->secure_id) {
			new = &((*new)->rb_right);
		} else {
			printk(KERN_ERR "UMP: ID already used %x\n", id);
			return MALI_FALSE;
		}
	}

	rb_link_node(&mem->node, parent, new);
	rb_insert_color(&mem->node, root);

	return MALI_TRUE;
}


ump_random_mapping *ump_random_mapping_create(void)
{
	ump_random_mapping *map = _mali_osk_calloc(1, sizeof(ump_random_mapping));

	if (NULL == map)
		return NULL;

	map->lock = _mali_osk_mutex_rw_init(_MALI_OSK_LOCKFLAG_ORDERED,
					    _MALI_OSK_LOCK_ORDER_DESCRIPTOR_MAP);
	if (NULL != map->lock) {
		map->root = RB_ROOT;
#if UMP_RANDOM_MAP_DELAY
		map->failed.count = 0;
		map->failed.timestamp = jiffies;
#endif
		return map;
	}
	return NULL;
}

void ump_random_mapping_destroy(ump_random_mapping *map)
{
	_mali_osk_mutex_rw_term(map->lock);
	_mali_osk_free(map);
}

int ump_random_mapping_insert(ump_random_mapping *map, ump_dd_mem *mem)
{
	_mali_osk_mutex_rw_wait(map->lock, _MALI_OSK_LOCKMODE_RW);

	while (1) {
		u32 id;

		get_random_bytes(&id, sizeof(id));

		/* Try a new random number if id happened to be the invalid
		 * secure ID (-1). */
		if (unlikely(id == UMP_INVALID_SECURE_ID))
			continue;

		/* Insert into the tree. If the id was already in use, get a
		 * new random id and try again. */
		if (insert(&map->root, id, mem)) {
			mem->secure_id = id;
			break;
		}
	}
	_mali_osk_mutex_rw_signal(map->lock, _MALI_OSK_LOCKMODE_RW);

	return 0;
}

ump_dd_mem *ump_random_mapping_get(ump_random_mapping *map, int id)
{
	ump_dd_mem *mem = NULL;
#if UMP_RANDOM_MAP_DELAY
	int do_delay = 0;
#endif

	DEBUG_ASSERT(map);

	_mali_osk_mutex_rw_wait(map->lock, _MALI_OSK_LOCKMODE_RO);
	mem = search(&map->root, id);

	if (unlikely(NULL == mem)) {
#if UMP_RANDOM_MAP_DELAY
		map->failed.count++;

		if (time_is_before_jiffies(map->failed.timestamp +
					   UMP_FAILED_LOOKUP_DELAY * HZ)) {
			/* If it is a long time since last failure, reset
			 * the counter and skip the delay this time. */
			map->failed.count = 0;
		} else if (map->failed.count > UMP_FAILED_LOOKUPS_ALLOWED) {
			do_delay = 1;
		}

		map->failed.timestamp = jiffies;
#endif /* UMP_RANDOM_MAP_DELAY */
	} else {
		ump_dd_reference_add(mem);
	}
	_mali_osk_mutex_rw_signal(map->lock, _MALI_OSK_LOCKMODE_RO);

#if UMP_RANDOM_MAP_DELAY
	if (do_delay) {
		/* Apply delay */
		schedule_timeout_killable(UMP_FAILED_LOOKUP_DELAY);
	}
#endif /* UMP_RANDOM_MAP_DELAY */

	return mem;
}

static ump_dd_mem *ump_random_mapping_remove_internal(ump_random_mapping *map, int id)
{
	ump_dd_mem *mem = NULL;

	mem = search(&map->root, id);

	if (mem) {
		rb_erase(&mem->node, &map->root);
	}

	return mem;
}

void ump_random_mapping_put(ump_dd_mem *mem)
{
	int new_ref;

	_mali_osk_mutex_rw_wait(device.secure_id_map->lock, _MALI_OSK_LOCKMODE_RW);

	new_ref = _ump_osk_atomic_dec_and_read(&mem->ref_count);
	DBG_MSG(5, ("Memory reference decremented. ID: %u, new value: %d\n",
		    mem->secure_id, new_ref));

	if (0 == new_ref) {
		DBG_MSG(3, ("Final release of memory. ID: %u\n", mem->secure_id));

		ump_random_mapping_remove_internal(device.secure_id_map, mem->secure_id);

		mem->release_func(mem->ctx, mem);
		_mali_osk_free(mem);
	}

	_mali_osk_mutex_rw_signal(device.secure_id_map->lock, _MALI_OSK_LOCKMODE_RW);
}

ump_dd_mem *ump_random_mapping_remove(ump_random_mapping *map, int descriptor)
{
	ump_dd_mem *mem;

	_mali_osk_mutex_rw_wait(map->lock, _MALI_OSK_LOCKMODE_RW);
	mem = ump_random_mapping_remove_internal(map, descriptor);
	_mali_osk_mutex_rw_signal(map->lock, _MALI_OSK_LOCKMODE_RW);

	return mem;
}