page.c

T-kernel 的extension源代码

/*
 *----------------------------------------------------------------------
 *    T-Kernel / Standard Extension
 *
 *    Copyright (C) 2006 by Ken Sakamura. All rights reserved.
 *    T-Kernel / Standard Extension is distributed 
 *      under the T-License for T-Kernel / Standard Extension.
 *----------------------------------------------------------------------
 *
 *    Version:   1.00.00
 *    Released by T-Engine Forum(http://www.t-engine.org) at 2006/8/11.
 *
 *----------------------------------------------------------------------
 */

/*
 *	page.c (memory)
 *
 *	Segment management (Virtual storage version)
 *	Page frame management
 */

#include "segmgr.h"

#define TSD_DSI_VAL_100		100
#define TSD_SCP_MAT_0XFFFFFFFF	0xffffffffU
#define TSD_DPP_MSK_0XF000	0xf000U
#define TSD_DPP_MSK_0XF0000	0xF0000U
#define TSD_MAT_SFT_4		4
#define TSD_MAT_VAL_7		7U
#define TSD_IPE_SAF_32		32
#define TSD_ICP_ITP_136		136
#define TSD_ICP_STK_2048	2048
#define TSD_CIP_DIV_2		2
#define TSD_DP1_MSK_4		4U
#define TSD_DP1_MSK_2		2U
#define TSD_DP1_MSK_1		1U
#define TSD_DPP_VAL_MC1		((opt >> 12) & 0xfU)
#define TSD_DPP_MSK_0X0F00	0x0f00
#define TSD_DPP_VAL_MC2		((opt >> 8) & 0xfU)
#define TSD_DPP_MSK_0X00F0	0x00f0U
#define TSD_DPP_VAL_MC3		((opt >> 4) & 0xfU)
#define TSD_DPP_MSK_0X000F	0x000fU
#define TSD_DPP_VAL_MC4		opt & 0xfU
#define TSD_DPP_VAL_MC5		((opt >> 16) & 0xfU)

Inline UW MATCH( PFE *pfe );
LOCAL void removeUninitPageQ( PFE *ent );
LOCAL void insertUninitPageQ( PFE *que, PFE *ent, UW npage );
LOCAL PFE* RemoveUninitPFE( PFE *pfe );
LOCAL PFE* GetUninitPFE( void );
LOCAL void PutUninitPFE( PFE *pfe );
LOCAL void InitUninitPages( void );
LOCAL PFE* SearchDBH( DBN dbn );
LOCAL ER PageOut( PFE *pfe, BOOL nowrite );
LOCAL void insertPageFrameQue( PFE *pfe, PFS stat );
LOCAL void removePageFrameQue( PFE *pfe );
LOCAL PFE* getNextPageFrame( PFE *ppfe, UW rank );
LOCAL PFE* getFreePageFrame( BOOL nowrite );
LOCAL PFE* searchContinuousFreePFE( UW npage );
LOCAL void AccessCheck( void );
LOCAL void CyclicProcess( void );

#if DEBUGFUNC_SUPPORT
LOCAL BOOL dumpPF1( PFE *pfe, UW opt );
LOCAL BOOL dumpPFque( PFE_Q *pfe_q, UW opt );
LOCAL BOOL dumpPFuninit( UW opt );
LOCAL BOOL dumpPFhash( UW opt );
#endif

/*
 * Page frame management information
 *	Use the start of PageFrameEntry as a queue for managing uninitialized pages.
 */
LOCAL RealMemoryInfo *MemInfo;	/* Page frame memory area */
LOCAL UW MaxPages;		/* Total number of pages */
LOCAL PFE *PageFrameEntry;	/* PFE table */
LOCAL UW MaxDBH;			/* Number of entries in DBH table */
LOCAL DBH *DiskBlockHash;		/* DBH table */

LOCAL PFE_Q LockPFE_Q;		/* Queue for lock page */
LOCAL PFE_Q UsePFE_Q;		/* Queue for page in use */
LOCAL PFE_Q FreePFE_Q;		/* Queue for free page */

LOCAL W	SafetyMargin;		/* Number of pages to be left as a safety margin */

/*
 * Statistical information
 */
LOCAL UW HashHitCount;		/* Number of DBH hits */
LOCAL UW HashMissCount;		/* Number of DBH mishits */
LOCAL UW SnatchCount;		/* Number of intercepted pages */

/*
 * PFN <--> PFE interconversion
 */
#define	PFNtoPFE(pfn)	( &PageFrameEntry[pfn] )
#define	PFEtoPFN(pfe)	( (PFN)((pfe) - PageFrameEntry) )


/*
 * PFE -> LADR
 *	Determine logical addresses of PFE page frames.
 */
EXPORT VP PFEtoLADR( PFE *pfe )
{
	UW	n = (UW)PFEtoPFN(pfe) - 1U;
	UW	i;

	for ( i = 0; i < (UW)MemInfo->n; i++ ) {
		if ( n < MemInfo->a[i].p.npage ) {
			return (VB*)MemInfo->a[i].p.laddr + (n * (UW)PAGESIZE);
		}
		n -= MemInfo->a[i].p.npage;
	}
	return NULL; /* Invalid */
}

/*
 * LADR -> PFE
 *	Determine PFE from logical addresses of PFE page frames.
 */
EXPORT PFE* LADRtoPFE( VP laddr )
{
	PFE	*pfe = PageFrameEntry + 1;
	UW	i, n;

	for ( i = 0; i < (UW)MemInfo->n; i++ ) {
		n = ((UW)laddr - (UW)MemInfo->a[i].p.laddr) / (UW)PAGESIZE;
		if ( n < MemInfo->a[i].p.npage ) {
			return pfe + n;
		}
		pfe += MemInfo->a[i].p.npage;
	}
	return NULL; /* Invalid */
}

/* ------------------------------------------------------------------------ */
/*
 *	PageFrameEntryQueue handling function
 */

/*
 * Initialize pfe_q
 */
EXPORT void InitPFE_Q( PFE_Q *pfe_q )
{
	pfe_q->top      = NULL;
	pfe_q->diskmap  = 0;
	pfe_q->other    = 0;
}

/*
 * Move queue top
 */
EXPORT void SetTopPFE_Q( PFE_Q *pfe_q, PFE *pfe )
{
	pfe_q->top = pfe;
}

/*
 * Insert pfe at the end of pfe_q
 */
EXPORT void InsertPFE_Q( PFE_Q *pfe_q, PFE *pfe )
{
	PFN	pfn = PFEtoPFN(pfe);

	/* Connect to queue */
	if ( pfe_q->top == NULL ) {
		pfe->next = pfn;
		pfe->prev = pfn;
		pfe_q->top = pfe;
	} else {
		PFE *npfe = pfe_q->top;
		PFN  npfn = PFEtoPFN(npfe);
		PFN  ppfn = npfe->prev;
		PFE *ppfe = PFNtoPFE(ppfn);
		pfe->next = npfn;
		pfe->prev = ppfn;
		npfe->prev = pfn;
		ppfe->next = pfn;
	}

	/* Count by type */
	if ( pfe->dbn_id != PAGEFILE_ID ) {
		pfe_q->diskmap++;
	}else{
		pfe_q->other++;
	}
}

/*
 * Delete pfe from pfe_q
 */
EXPORT void RemovePFE_Q( PFE_Q *pfe_q, PFE *pfe )
{
	PFE	*npfe = PFNtoPFE(pfe->next);
	PFE	*ppfe = PFNtoPFE(pfe->prev);

	/* Disconnect from queue */
	if ( npfe == pfe ) {
		pfe_q->top = NULL;
	} else {
		npfe->prev = pfe->prev;
		ppfe->next = pfe->next;
		if ( pfe_q->top == pfe ) {
			pfe_q->top = npfe;
		}
	}

	/* Count by type */
	if ( pfe->dbn_id != PAGEFILE_ID ) {
		pfe_q->diskmap--;
	}else{
		pfe_q->other--;
	}
}

/*
 * Fetch pfe from the start of pfe_q
 */
EXPORT PFE* RemoveNextPFE_Q( PFE_Q *pfe_q )
{
	PFE	*pfe = pfe_q->top;

	if ( pfe != NULL ) {
		RemovePFE_Q(pfe_q, pfe);
	}
	return pfe;
}

/*
 * Return the next entry in pfe_q
 *	When "pfe = NULL", return the first entry.
 *	When pfe is the last entry, return NULL.
 */
EXPORT PFE* NextPFE_Q( PFE_Q *pfe_q, PFE *pfe )
{
	if ( pfe == NULL ) {
		pfe = pfe_q->top;
	}else{
		pfe = PFNtoPFE(pfe->next);
		if ( pfe == pfe_q->top ) {
			pfe = NULL;
		}
	}
	return pfe;
}

/* ------------------------------------------------------------------------ */
/*
 *	Management of uninitialized page
 */

#define	UninitPageQ	( PageFrameEntry )
LOCAL	UW		UninitPageCount;	/* Nubmer of uninitialized pages */

/*
 * Disconnect from UninitPageQ
 */
LOCAL void removeUninitPageQ( PFE *ent )
{
	PFN	pfn = PFEtoPFN(ent);

	if ( ent->next != pfn ) {
		PFNtoPFE(ent->prev)->next = ent->next;
		PFNtoPFE(ent->next)->prev = ent->prev;
	}
}

/*
 * Insert in UninitPageQ
 *	Insert npage starting from ent immediately anterior to que
 */
LOCAL void insertUninitPageQ( PFE *que, PFE *ent, UW npage )
{
	PFN	pfn = PFEtoPFN(ent);

	/* Set uninitialized page */
	ent->stat = PFS_uninit;
	ent->dbn_no = (W)npage;
	if ( npage > 1U ) {
		(ent + npage - 1)->stat = PFS_uninit;
		(ent + npage - 1)->dbn_no = (W)npage;
	}

	/* Register free page */
	ent->next = PFEtoPFN(que);
	ent->prev = que->prev;
	PFNtoPFE(que->prev)->next = pfn;
	que->prev = pfn;
}

/*
 * Fetch uninitialized page pfe
 *	pfe needs to be located at the start of consecutive free areas.
 *	The obtained pfe must be set in other state
 *	than PFS_uninit.
 */
LOCAL PFE* RemoveUninitPFE( PFE *pfe )
{
	PFN	ins;
	W	free;

	/* Temporarily remove all of pq consecutive free pages from the free queue. */
	ins = pfe->next;
	removeUninitPageQ(pfe);

	/* Separate one page */
	free = pfe->dbn_no - 1;

	if ( free > 0 ) {
		/* Return the remaining pages to free the queue. */
		insertUninitPageQ(PFNtoPFE(ins), pfe + 1, (UW)free);
	}
	UninitPageCount--;

	return pfe;
}

/*
 * Fetch one page from uninitialized pages.
 *	If there is no uninitialized page, return NULL.
 */
LOCAL PFE* GetUninitPFE( void )
{
	PFN	pfn = UninitPageQ->next;

	if ( pfn == 0U ) {
		return NULL;
	}

	return RemoveUninitPFE(PFNtoPFE(pfn));
}

/*
 * Register pfe as an uninitialized page.
 */
LOCAL void PutUninitPFE( PFE *pfe )
{
	PFN	pfn = PFEtoPFN(pfe);
	PFN	ins = 0;
	W	npage = 1;
	PFE	*q;

	/* Check if there are free pages in the posterior. */
	if (((pfn + 1U) <= MaxPages)
	  && ((q = pfe + 1U)->stat == PFS_uninit )) {

		/* Temporarily remove free pages located posterior from the free queue. */
		ins = q->next;
		removeUninitPageQ(q);

		/* Merge free and new pages. */
		npage += q->dbn_no;
	}

	/* Check if there are free pages in the anterior. */
	if ( (pfn > 1U)
	  && ((q = pfe - 1U)->stat == PFS_uninit )) {

		/* Number of free pages in the anterior */
		UW n = (UW)q->dbn_no;

		/* Temporarily remove free pages located anterior from the free queue. */
		ins = (pfe - n)->next;
		removeUninitPageQ(pfe - n);

		/* Merge free and new pages. */
		pfe -= n;
		npage += (W)n;
	}

	/* Register new page in free page. */
	insertUninitPageQ(PFNtoPFE(ins), pfe, (UW)npage);
	UninitPageCount++;
}

/*
 * Initialize management information for uninitialized page
 */
LOCAL void InitUninitPages( void )
{
	UninitPageQ->next = 0;
	UninitPageQ->prev = 0;

	insertUninitPageQ(UninitPageQ, UninitPageQ + 1, MaxPages);
	UninitPageCount = MaxPages;
}

/* ------------------------------------------------------------------------ */
/*
 *	Management of DiskBlockHash
 */

#define	DBHindex(dbn_no)	( ((UW)(dbn_no) >> 3) % MaxDBH )

/*
 * Register in DBH
 */
EXPORT void RegistDBH( PFE *pfe )
{
	UW	hash;

	/* Do not register if no page file has been allocated. */
	if (( pfe->dbn_id == 0 )&&( pfe->dbn_no == 0 )) {
		return;
	}

	hash = DBHindex(pfe->dbn_no);
	pfe->dbh = DiskBlockHash[hash];
	DiskBlockHash[hash] = (DBH)PFEtoPFN(pfe);
}

/*
 * Deregister from DBH
 */
EXPORT void RemoveDBH( PFE *pfe )
{
	PFN	npfn, ppfn, pfn;
	UW	hash;

	/* Not registered if no page file has been allocated. */
	if (( pfe->dbn_id == 0 )&&( pfe->dbn_no == 0 )) {
		return;
	}

	pfn  = PFEtoPFN(pfe);
	hash = DBHindex(pfe->dbn_no);
	ppfn = 0;
	npfn = DiskBlockHash[hash];
	while ( npfn != 0U ) {
		if ( npfn == pfn ) {
			if ( ppfn == 0U ) {
				DiskBlockHash[hash] = pfe->dbh;
			} else {
				PFNtoPFE(ppfn)->dbh = pfe->dbh;
			}
			break;
		}
		ppfn = npfn;
		npfn = PFNtoPFE(ppfn)->dbh;
	}
}

/*
 * Search for DBH
 */
LOCAL PFE* SearchDBH( DBN dbn )
{
	PFN	pfn;
	PFE	*pfe;

	pfn = DiskBlockHash[DBHindex(dbn.no)];
	while ( pfn != 0U ) {
		pfe = PFNtoPFE(pfn);
		if (( pfe->dbn_no == dbn.no )
		  &&( pfe->dbn_id == dbn.id )) {
			return pfe;
		}
		pfn = pfe->dbh;
	}
	return NULL;
}

/* ------------------------------------------------------------------------- */
/*
 *	Page-in/page-out processing
 */

/*
 * Page-in
 */
EXPORT ER PageIn( VP laddr, UW lsid )
{
	PTH	pth;
	PTE	pte;
	ER	err;

	InitPTH(&pth, laddr, lsid);
	err = NextPTE(&pth);
	if ( err < E_OK ) {
		goto err_ret;
	}

	pte.w = GetPTE(&pth);

	if ( isValidP(pte.w) ) {

		/* Since they are valid pages, page-in is not necessary. */
		MovePageFrame(PFAtoPFE(pte.c.pfa), PFS_use);
		(void)ChgPTE(&pth, PT_Present, ~(UW)PT_Present, TRUE);
	} else {

		if ( pte.c.pfa == 0 ) {
			err = E_MACV;
			goto err_ret;
		}

		/* Page-in */
		if ( pte.c.pfa < PB_BASE ) {
			/* Disk map */
			err = PageInMapDisk((ID)pte.c.pfa, laddr);
		} else {
			/* Page file */
			err = PageInPageFile(&pth, laddr, lsid);
		}
		if ( err < E_OK ) {
			goto err_ret;
		}
	}

	EndPTH(&pth, FALSE);
	return E_OK;

err_ret:
	EndPTH(&pth, FALSE);
	DEBUG_PRINT(("PageIn err = %d\n", err));
	return err;
}

/*
 * Page out pfe
 *	When "nowrite = TRUE", return E_BUSY instead of
 *	writing page frames to the disk (page-out).
 *
 *	pfe->stat must be PFS_use or PFS_free.
 */
LOCAL ER PageOut( PFE *pfe, BOOL nowrite )
{
	ER	err;

	/* Unregistered pages must not be paged out. */
	if ( !pfe->reg ) {
		err = E_BUSY;
		goto err_ret;
	}

	if ( pfe->md.w == 0U ) {
		return E_OK;  /* Not mapped */
	}

	/* Turn page frames into unregistered pages temporarily so that
	   they are not paged out again during page-out processing. */
	pfe->reg = FALSE;

	if ( pfe->dbn_id == PAGEFILE_ID ) {
		/* Page file */
		err = PageOutPageFile(pfe, nowrite);
	} else {
		/* Disk map */
		err = PageOutMapDisk(pfe, nowrite);
	}

	pfe->reg = TRUE;

err_ret:
#ifdef DEBUG
	if ( err < E_OK && !(nowrite && err == E_BUSY) ) {
		DEBUG_PRINT(("PageOut nowrite = %d err = %d\n", nowrite, err));
	}
#endif
	return err;
}

/*
 * Copy-on-write
 */
EXPORT ER CopyOnWrite( VP laddr, UW lsid )
{
	PTH	pth;
	PTE	pte;
	PFE	*opfe, *npfe;
	VP	p;
	ER	err;

retry:
	InitPTH(&pth, laddr, lsid);
	err = NextPTE(&pth);
	if ( err < E_OK ) {
		goto err_ret2;
	}

	pte.w = GetPTE(&pth);

	if ( !isPresentP(pte.w) ) {
		EndPTH(&pth, FALSE);

		/* Perform page-in again because they were paged out after
		   a page fault occurred. */
		err = PageIn(laddr, lsid);
		if ( err < E_OK ) {
			goto err_ret1;
		}

		goto retry;
	}

	if ( CopyOnWriteP_done(pte.w) ) {
			goto norm_ret;	/* Copy-on-write already performed */
	}

	opfe = PFAtoPFE(pte.c.pfa);

	if ( !isCopyOnWriteP(pte.w) || isWritableP(pte.w)