/*
================================ COPYRIGHT ================================
The contents of this file are subject to the VTech Informations Ltd. License
of VT-OS Ver. 1.1 operating system (the "License"); you may not use this 
file except in compliance with the License.  

Software distributed under the License is distributed on an "AS IS" basis, 
WITHOUT WARRANTY OF ANY KIND, either express or implied.  See the License 
for the specific language governing rights and limitations under the License.
  
The Original Code is VT-OS Ver. 1.1 Operating System, released 
on October 1st, 1999
	
The Initial Developer of the Original Code is VTech Informations Ltd.  All 
codes are Copyright (C) VTech Informations Ltd. 1999.  All Rights Reserved.
===========================================================================
*/

/*
===========================================================================
File        :   qmalloc.c
Author(s)   :   Kenny Ng
Company     :   VTech Informations Ltd.
Project     :   Helio 
Date:       :   1 Feb 00'
Purpose:    :   Dynamic memory allocation in user memory space
Revision    :   1.1
Note        :   
Modification History
*/

#include "datatype.h"
#include "dm.h"
#include "mmu.h"

BYTE user_mem_init = 0;

extern UWORD *app_page;

#undef DEBUG_GENERAL_ERROR     /* define this for showing general error */
#undef MM_CHECK_RANGE           /* define this for more secure allocation, but slower */
#undef DEBUG_TRACE_PTR          /* define this to trace the pointer size and address */
#undef MM_INIT_MEM              /* define this to init/erase memory when a click is allocated/free */
#undef MM_FREE_EXTRA            /* define this to free unused page after qfree() */

#ifdef PC_SIM
#ifdef DEBUG
#include <stdio.h>
#endif
#endif

#ifdef PC_SIM
extern BYTE *buffer;
#endif

#define BLOCK_RESERVE_SPACE             (sizeof(struct block_header) + sizeof(struct page_identifier))
/* The following definitions only valid for 4KB page size */
const UWORD blocksize[] =
{
	32,
	64,
	128,
	252,
	508,
	1020,
	2040,
	4096 - BLOCK_RESERVE_SPACE,
	8192 - BLOCK_RESERVE_SPACE,
	16384 - BLOCK_RESERVE_SPACE,
	32768 - BLOCK_RESERVE_SPACE,
	65536 - BLOCK_RESERVE_SPACE,
	131072 - BLOCK_RESERVE_SPACE,
	262144 - BLOCK_RESERVE_SPACE,
	0
};

const struct size_identifier mm_link_default[] =
{
/*	entry 0 is the pointer to next free block
entry 1 is max number of click in the block ( (blocksize[i] - BLOCK_RESERVE_SPACE) / PAGE_SIZE) )
entry 2 is the number of allocated page that has free space
entry 3 is number of 4-KB block need for each allocation
	*/
    {NULL, 126, 0, 0}, /* 32     */
    {NULL, 62, 0, 0},   /* 64     */
    {NULL, 30, 0, 0},   /* 128    */
    {NULL, 15, 0, 0},   /* 252    */
    {NULL, 7,  0, 0}, /* 508    */
    {NULL, 4,  0, 0}, /* 1020   */
    {NULL, 2,  0, 0}, /* 2040   */
    {NULL, 1,  0, 0}, /* 4080   */
    {NULL, 1,  0, 1},    /* 8176   */
    {NULL, 1,  0, 3},    /* 16368  */
    {NULL, 1,  0, 7},    /* 32752  */
    {NULL, 1,  0, 15},    /* 65520  */
    {NULL, 1,  0, 31},    /* 131056 */
    {NULL, 1,  0, 63},    /* 262128 */
    {NULL, 0,  0, 0}     /* END    */
};

struct size_identifier user_mm_link[MM_MAX_ORDER];

#define NUM_BLOCK(index)    (user_mm_link[index].nclick)
#define BLOCKSIZE(index)    (blocksize[index])
#define AREASIZE(index) (PAGE_SIZE << (user_mm_link[index].npage_need))
#define PAGE_DESC(p)        (struct page_identifier *)(((UWORD)(p)) & PAGE_MASK)
#define BH(p)   ((struct block_header*)(p))
#define FBH(p)   ((struct free_block_header*)(p))

#ifdef PC_SIM
static USHORT mm_used_block = 0;
#endif

void user_mm_init()
{
	int i;
	
	dmuser_first_block = 0xFFFF;
	user_dynamic_mem_address = (UWORD*) 0xFFFFFFFF;
	user_dynamic_mem_size  = 0;
	user_mem_init = 0;
	
	for(i=0;i<MM_MAX_ORDER-1;i++)
		user_mm_link[i] = mm_link_default[i];
}

void *get_pages(WORD a, USHORT *blk)
{
#ifdef PC_SIM
	void *ptr = (buffer + (mm_used_block + a) * PAGE_SIZE);
	if(mm_used_block + a + 1 >= 10)
	{
#ifdef DEBUG
		printf("\n[Malloc]: No more Page in system ");
#endif
		return NULL;
	}
	mm_used_block += ++a;
	return ptr;
#else
	void *ptr;
	
	if((ptr = MemoryDMANew(DM_USER, a+1, blk)) == NULL)
	{
#ifdef DEBUG
		printf("\n[QMalloc]: No more Page in system ");
#endif               
		return NULL;
	}
	else
	{
#ifdef DEBUG_TRACE_PTR
		printf("\n[QMalloc] Allocate block %d, num page = %d ", *blk, a + 1);
#endif
		return ptr;
	}
#endif
}

#ifdef MM_FREE_EXTRA
void free_pages(void *pg)
{
#ifdef PC_SIM                       
	mm_used_block -= mm_link_default[((struct page_identifier *) pg)->npage_order].npage_need + 1;
#else
	USHORT mmu_block_num = ((struct page_identifier *) pg)->block;
	WORD num_page = mm_link_default[((struct page_identifier *) pg)->npage_order].npage_need;
	USHORT next_block;
	
#ifdef DEBUG_TRACE_PTR
	printf("\nPage %d num page = %d: Freeing page ", mmu_block_num, num_page + 1);
#endif
	
	do
	{
#ifdef DEBUG_TRACE_PTR               
		printf("  %d  ", mmu_block_num);
#endif
		if(num_page)
		{
			if( MemoryNextBlock2(mmu_block_num, &next_block) != TRUE )
				next_block = 0xffff;
		}
		MemoryReleaseBlock2(mmu_block_num, FALSE, TRUE);
		mmu_block_num = next_block;
		
	} while(num_page--);
#endif
}
#endif  //MM_FREE_EXTRA

void *qmalloc(WORD size)
{
    WORD order;
    struct free_block_header *p;
    struct page_identifier *page, **pg;
    struct size_identifier *bucket = user_mm_link;
	
	
#ifdef DEBUG_TRACE_PTR
    printf("\n[QMalloc] size = %d ", size);
#endif
	
    order = 0;	/* calculate the order for the size, including the 4-byte header */
    {
        UWORD real_size = size + sizeof(struct block_header);
        for (;;) {
			UWORD ordersize = BLOCKSIZE(order);
			if (real_size <= ordersize)
				break;
			order++;   /* block size */
			bucket++;  /* mm_link */
			if (ordersize) /* == 0 means end */
				continue;
			
            printf("\n[QMalloc] allocate size %d which is larger than max size", size);
			
			return NULL;
		}
    }
	
    pg = (struct page_identifier**)&bucket->pfree_head;   /* pg point to the value of mm_link[x].pfree_head */
	
    page = *pg;					/* page point to the first free block */
	
	if (!page)                                  /* mm_link[x].pfree_head = NULL */
		goto no_bucket_page;
	
    p = (struct free_block_header*) page->first_free_click; /* p point to a free click in the page */
	
#ifdef MM_CHECK_RANGE
    if( ( (UWORD) p >> 24)  != ( (UWORD)page >> 24 ) )
    {
#ifdef DEBUG_GENERAL_ERROR
        {
			WORD d0=0x3ffffff;
			printf("\n[QMalloc] ********* Wrong free click number for page %08x ", page);
			while(d0--);
        }
#endif
        goto no_bucket_page;
    }
	
    if( ( (UWORD)p - ((UWORD) page + sizeof(struct page_identifier)) ) % blocksize[order])
    {
#ifdef DEBUG_GENERAL_ERROR
        {
			WORD d1 = 0x3ffffff;
			printf("\n[QMalloc] ************** Invalid page boundary for ptr %08x ", p);
			while(d1--);
        }
#endif
        goto no_bucket_page;
    }
#endif   // MM_CHECK_RANGE
	
    if (p->flag != MM_FREE)     /* the click should be free */
        goto not_free_on_freelist;
	
found_it:
    page->first_free_click = (struct block_header*) p->next;  /* update free list pointer in the page header*/
    page->nfree_click--;
	
    if (!page->nfree_click)     /* total free = 0  ==>  block full */
        *pg = page->next;		/* mm_link[x].pfree_head pointer to next linked block */
	
    p->flag = MM_USED;                /* mark the allocated click in used */
	
#ifdef MM_INIT_MEM
    memset(p+1, 0xf0, size);
#endif
	
#ifdef DEBUG_TRACE_PTR
	printf("\n[QMalloc] Alloc ptr %08x ", ((UWORD)p + sizeof(struct block_header)));
#endif
	
    return (void*)((UWORD)p + sizeof(struct block_header));		/* skip header */
    
no_bucket_page:
	/* need to allocate a new page */
    {
        WORD i, sz;
        USHORT mem_block;
		
#ifdef DEBUG_TRACE_PTR
        printf("\n[Qmalloc] no bucket");
#endif
		sz = BLOCKSIZE(order);	/* calculate request size */
		
        page = get_pages(bucket->npage_need, &mem_block);   /* request new page from OS */
		if (!page)								/* no more page */
            goto no_free_page;
		
		bucket->npages++;						/* mm_link[x].npages ++ */
		
		/* init the new block */
		page->npage_order = (USHORT) order;
        page->block = mem_block;
		
		i = (page->nfree_click = bucket->nclick) - 1;
        p = (struct free_block_header *)(page + 1);
		
		while (i) {
			i--;
			p->flag = MM_FREE;
            p->next = (struct free_block_header*)((UWORD)p + sz);
			p = p->next;
		}
		
		p->flag = MM_FREE;		/* this is the last block, set next to NULL */
		p->next = NULL;
		p = (struct free_block_header *)(page + 1);
    }
    
    page->next = *pg;  /* append the list to mm_list[x] */
    *pg = page;
	
    goto found_it;		/* go back and find again */
    
no_free_page:
#ifdef DEBUG_GENERAL_ERROR
    printf("\n[QMalloc] No more DM");
    return NULL;
#endif
not_free_on_freelist:
#ifdef DEBUG_GENERAL_ERROR
    printf("\n[QMalloc] Ptr %08x not on free list", p);
#endif
    return NULL;
}

void pfree(void *pool);
void qfree(void *__ptr)
{
    USHORT order;
    struct page_identifier *page, **pg;
    struct size_identifier *bucket;
    
    if (!__ptr)				/* try to free a NULL pointer */
		goto null_free;
	
    if(__ptr >= (void*)0x40000000)      /* freeing system pointer */
		return pfree(__ptr);  
	
#ifdef DEBUG_TRACE_PTR
    printf("\n[QFree] Free ptr %08x ", __ptr);
#endif
	
#define ptr ((struct free_block_header *) __ptr)
	
    __ptr = (void*) ((UWORD) __ptr - sizeof(struct block_header));  /* point to click header */
	
    if(ptr->flag != MM_USED)        /* invalid header */
		goto invalid_free;
	
    page = PAGE_DESC(ptr);		/* page point to page header */
    
    order = page->npage_order;
    if (order >= MM_MAX_ORDER)	/* invalid page header */
		goto bad_order;
	
    bucket = user_mm_link + order;       /* point to mm_link */
	
    if(page->nfree_click > bucket->nclick)  /* invalid page header */
		goto bad_header;
    
    pg = (struct page_identifier **)&bucket->pfree_head;
    
    ptr->flag = MM_FREE;    /* mark the click free */
	
    ptr->next = (struct free_block_header *) page->first_free_click;		/* append to page header's free list */
    page->first_free_click = (struct block_header *) ptr;
    if (!page->nfree_click++) {				/* this page can only hold 1 page */
#ifdef MM_FREE_EXTRA
        if (bucket->nclick == 1)			/* this should always happen */
            goto free_page;					/* when a large click is free, should release the memory to system */
#endif
        page->next = *pg;					/* else, link it to mm_list[x] */
        *pg = page;
    }
	
#ifdef MM_FREE_EXTRA
    if (page->nfree_click == bucket->nclick) {	/* all clicks are free */
		if((bucket->npage_need == 0) && (bucket->npages == 1))
			goto do_not_free;  /* if it only need 1 page, don't free it and let it occupy the memory */
        for (;;) {
            struct page_identifier *tmp = *pg;
            if (!tmp)
                goto not_on_freelist;
            if (tmp == page)
                break;
            pg = &tmp->next;
        }
        *pg = page->next;
		
free_page:
        bucket->npages--;
        free_pages(page);
    }
#endif
	return;
	
null_free:
	return;
invalid_free:
#ifdef DEBUG_GENERALL_ERROR
	printf("\n[QFree] Inv Free");
#endif
	return;
	
not_on_freelist:
#ifdef DEBUG_GENERAL_ERROR
	printf("\n[QFree] Not in Free List");
#endif
	return;
	
bad_order:
#ifdef DEBUG_GENERAL_ERROR
	printf("\n[QFree] Bad order");
#endif
	return;
	
bad_header:
#ifdef DEBUG_GENERAL_ERROR
	printf("\n[QFree] Bad header");
#endif
	return;
	
do_not_free:
#ifdef DEBUG_GENERAL_ERROR
	printf("\n[QFree] Do not free");
#endif
	return;
}


/* pcalloc                                                           */
/* Purpose : allocate memory & set value to NULL                     */
/* Input   : size       byte to allocate                             */
/* Output  : None                                                    */
/* Return  : NULL       if fail                                      */
/*           a pointer to allocated memory if success                */
/* Comment : None                                                    */
void *qcalloc(size_t num, size_t size)
{
    size_t i       = size * num;
    void  *result  = qmalloc(i);
	
    if (result)
    {
		BYTE *cp   = result;
		if (i) do *cp++ = 0; while (--i);
    }
    return result;
}
