/*
 * ppm.c - Per-cluster Physical Pages Manager implementation
 *
 * Authors  Ghassan Almaless (2008,2009,2010,2011,2012)
 *          Alain Greiner    (2016,2017)
 *
 * Copyright (c) UPMC Sorbonne Universites
 *
 * This file is part of ALMOS-MKH.
 *
 * ALMOS-MKH.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; version 2.0 of the License.
 *
 * ALMOS-MKH.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 ALMOS-MKH.; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <kernel_config.h>
#include <hal_types.h>
#include <hal_special.h>
#include <printk.h>
#include <list.h>
#include <bits.h>
#include <page.h>
#include <spinlock.h>
#include <thread.h>
#include <cluster.h>
#include <kmem.h>
#include <process.h>
#include <dqdt.h>
#include <ppm.h>

////////////////////////////////////////////////
inline bool_t ppm_page_is_valid( page_t * page )
{
	ppm_t    * ppm  = &LOCAL_CLUSTER->ppm;
	uint32_t   pgnr = (uint32_t)( page - ppm->pages_tbl );
	return (pgnr <= ppm->pages_nr);
}


/////////////////////////////////////////////
inline void * ppm_page2vaddr( page_t * page )
{
	ppm_t * ppm = &LOCAL_CLUSTER->ppm;
	return ppm->vaddr_base + ((page - ppm->pages_tbl) << CONFIG_PPM_PAGE_SHIFT);
}

//////////////////////////////////////////////
inline page_t * ppm_vaddr2page( void * vaddr )
{
	ppm_t * ppm = &LOCAL_CLUSTER->ppm;
	return ppm->pages_tbl + (vaddr - ppm->vaddr_base);
}

//////////////////////////////////////////
inline ppn_t ppm_page2ppn( page_t * page )
{
	ppm_t  * ppm = &LOCAL_CLUSTER->ppm;
	return (ppn_t)( page - ppm->pages_tbl );
}

/////////////////////////////////////////
inline page_t * ppm_ppn2page( ppn_t ppn )
{
	ppm_t  * ppm = &LOCAL_CLUSTER->ppm;
	return &ppm->pages_tbl[ppn];
}

///////////////////////////////////////
inline void * ppm_ppn2vaddr( ppn_t ppn )
{
	ppm_t  * ppm  = &LOCAL_CLUSTER->ppm;
	return ppm->vaddr_base + (ppn << CONFIG_PPM_PAGE_SHIFT);
}

//////////////////////////////////////////
inline ppn_t ppm_vaddr2ppn( void * vaddr )
{
	ppm_t  * ppm  = &LOCAL_CLUSTER->ppm;
	return ( (ppm->vaddr_base - vaddr) >> CONFIG_PPM_PAGE_SHIFT );
}


///////////////////////////////////////////
void ppm_free_pages_nolock( page_t * page )
{
	page_t   * buddy;            // searched buddy page descriptor
	uint32_t   buddy_index;      // buddy page index
	page_t   * current;          // current (merged) page descriptor
	uint32_t   current_index;    // current (merged) page index
	uint32_t   current_order;    // current (merged) page order

	ppm_t    * ppm         = &LOCAL_CLUSTER->ppm;
	page_t   * pages_tbl   = ppm->pages_tbl;

	assert( !page_is_flag( page , PG_FREE ) , __FUNCTION__ , "page already freed" );
	assert( !page_is_flag( page , PG_RESERVED ) , __FUNCTION__ , "freeing reserved page" );

	// update released page descriptor flags
	page_set_flag( page , PG_FREE );

	// search the buddy page descriptor
	// - merge with current page descriptor if found
	// - exit to release the current page descriptor if not found
	current       = page ,
	current_index = (uint32_t)(page - ppm->pages_tbl);
	for( current_order = page->order ;
	     current_order < CONFIG_PPM_MAX_ORDER ;
	     current_order++ )
	{
		buddy_index = current_index ^ (1 << current_order);
		buddy       = pages_tbl + buddy_index;

		if( !page_is_flag( buddy , PG_FREE ) || (buddy->order != current_order) ) break;

		// remove buddy from free list
		list_unlink( &buddy->list );
		ppm->free_pages_nr[current_order] --;

		// merge buddy with current
		buddy->order = 0;
		current_index &= buddy_index;
	}

	// update merged page descriptor order
	current        = pages_tbl + current_index;
	current->order = current_order;

	// insert current in free list
	list_add_first( &ppm->free_pages_root[current_order] , &current->list );
	ppm->free_pages_nr[current_order] ++;
}

////////////////////////////////////////////
page_t * ppm_alloc_pages( uint32_t   order )
{
	uint32_t   current_order;
	page_t   * remaining_block;
	uint32_t   current_size;

	ppm_t    * ppm = &LOCAL_CLUSTER->ppm;

	assert( (order < CONFIG_PPM_MAX_ORDER) , __FUNCTION__ , "illegal order argument" );

	page_t * block = NULL;

	ppm_dmsg("\n[INFO] %s : enters / order = %d\n",
	         __FUNCTION__ , order );

	// take lock protecting free lists
	spinlock_lock( &ppm->free_lock );

	// find a free block equal or larger to requested size
	for( current_order = order ; current_order < CONFIG_PPM_MAX_ORDER ; current_order ++ )
	{
		if( !list_is_empty( &ppm->free_pages_root[current_order] ) )
		{
			block = LIST_FIRST( &ppm->free_pages_root[current_order] , page_t , list );
			list_unlink( &block->list );
			break;
		}
	}

	if( block == NULL ) // return failure
	{
		// release lock protecting free lists
		spinlock_unlock( &ppm->free_lock );

		return NULL;
	}

	// update free-lists after removing a block
	ppm->free_pages_nr[current_order] --;
	current_size = (1 << current_order);

	// split the removed block in smaller sub-blocks if required
	// and update the free-lists accordingly
	while( current_order > order )
	{
		current_order --;
		current_size >>= 1;

		remaining_block = block + current_size;
		remaining_block->order = current_order;

		list_add_first( &ppm->free_pages_root[current_order] , &remaining_block->list );
		ppm->free_pages_nr[current_order] ++;
	}

	// update page descriptor
	page_clear_flag( block , PG_FREE );
	page_refcount_up( block );
	block->order = order;

	// release lock protecting free lists
	spinlock_unlock( &ppm->free_lock );

	ppm_dmsg("\n[INFO] %s : base = %x / order = %d\n",
	         __FUNCTION__ , (uint32_t)ppm_page2base( block ) , order );

	return block;
}


////////////////////////////////////
void ppm_free_pages( page_t * page )
{
	ppm_t * ppm = &LOCAL_CLUSTER->ppm;

	// get lock protecting free_pages[] array
	spinlock_lock( &ppm->free_lock );

	ppm_free_pages_nolock( page );

	// release lock protecting free_pages[] array
	spinlock_unlock( &ppm->free_lock );
}

////////////////////////////
void ppm_print( ppm_t * ppm,
                char  * string )
{
	uint32_t       order;
	list_entry_t * iter;
	page_t       * page;

	// get lock protecting free lists
	spinlock_lock( &ppm->free_lock );

	printk("\n***  PPM in cluster %x : %d pages / &pages_tbl = %x / vaddr_base = %x ***\n",
	       local_cxy , ppm->pages_nr , (intptr_t)ppm->pages_tbl , (intptr_t)ppm->vaddr_base );

	for( order = 0 ; order < CONFIG_PPM_MAX_ORDER ; order++ )
	{
		printk("- order = %d / free_pages = %d  [",
		       order , ppm->free_pages_nr[order] );

		LIST_FOREACH( &ppm->free_pages_root[order] , iter )
		{
			page = LIST_ELEMENT( iter , page_t , list );
			printk("%d," , page - ppm->pages_tbl );
		}

		printk("]\n", NULL );
	}

	// release lock protecting free lists
	spinlock_unlock( &ppm->free_lock );
}

///////////////////////////////////////
error_t ppm_assert_order( ppm_t * ppm )
{
	uint32_t       order;
	list_entry_t * iter;
	page_t       * page;

	for(order=0; order < CONFIG_PPM_MAX_ORDER; order++)
	{
		if( list_is_empty( &ppm->free_pages_root[order] ) ) continue;

		LIST_FOREACH( &ppm->free_pages_root[order] , iter )
		{
			page = LIST_ELEMENT( iter , page_t , list );

			if( page->order != order )  return -1;
		}
	}

	return 0;
}

