malloc.cpp

一个经典的词法分析器

//
// A shared memory management module, using virtual memory mapped to a memory
// file. Adapted from a UNIX-based malloc routine originally conceived by
// William L. Sebok, obtained from UUNET comp.sources.unix.
//
#define MALLOC
#include "afxwin.h"
#include "EMBSQL.h"

#define NULL	0

#define MEMORY_LIMIT 10000000
//
// Shared memory management variables
#pragma data_seg("shared")
SCCollection* tables = NULL;
SCTable *sharedTable = NULL;
char mapFileName[256] = {""};
char *sharedMemoryFile = NULL;
char *memoryLimitF = NULL;
char *curPtrF = NULL;
int memCounter = 0;
#pragma data_seg()

HANDLE hMapFile = INVALID_HANDLE_VALUE;
CString dllError = "";

BOOL APIENTRY DllMain(HANDLE hModule, DWORD reason, LPVOID reserved)
{
	if (reason == DLL_PROCESS_ATTACH)  {
		memCounter++;
		if (memCounter == 1) {
			CreateMappedFile(MEMORY_LIMIT);
			CESql* first = new CESql();
			first->Sql("create table embsqlCatalog (name char(64))");
		}
		else {
			if (!CreateMappedFile(0))
				dllError = "FATAL ERROR: Shared memory is misaligned (LINK EMBSQL FIRST!)";
		}
	}
	if (reason == DLL_PROCESS_DETACH) {
		memCounter--;
		CloseMappedFile(false);
	}
	return true;
}
//
// Create the mapped file int the temp directory
BOOL CreateMappedFile(int size)
{
	HANDLE h;
	char szTmpFile[256];
	char *testbase;
//
// If size == 0 then this is not the first instance. Just get the shared
// memory by opening the file mapping. The pointers are already set into 
// the DLLs shared memory, but they aren't valid until you map the file
//
	if (size == 0) {
		h = OpenFileMapping (FILE_MAP_WRITE,TRUE,"embsqlmemory");
		if (h != NULL) {
			testbase = (char *)MapViewOfFileEx(h, FILE_MAP_WRITE,0,0,0,sharedMemoryFile);
			if (sharedMemoryFile != testbase) 
				return false;
			sharedMemoryFile = testbase;
			hMapFile = h;
			return true;
		}
		return false;
	}

	// Get the path for the temp directory, make the file name, then create the file
	GetTempPath (256, szTmpFile);    
	sprintf(mapFileName,"%s%s",szTmpFile,"embsql.tmp");
	
	// Create the file, stomp on whatever was there
	h = CreateFile (mapFileName,
                       GENERIC_WRITE | GENERIC_READ,
                       FILE_SHARE_WRITE, NULL,
                       CREATE_ALWAYS,
                       FILE_ATTRIBUTE_TEMPORARY,
                       NULL);
	if (h == (HANDLE)INVALID_HANDLE_VALUE)
		return false;

	// Create the mapping, this sets the shared memory regions object name so
	// subsequent users can get at it
	h = CreateFileMapping (h,
                           NULL,PAGE_READWRITE,
                           0,size,
                           "embsqlmemory"); 

	// Set the pointers into the shared memory region
	sharedMemoryFile = (char *)MapViewOfFile (h, FILE_MAP_WRITE,0,0,0);
	memoryLimitF = &sharedMemoryFile[size];
	curPtrF = sharedMemoryFile;
	hMapFile = h;
	return true;
}

//
// Close the mapped file
BOOL CloseMappedFile(BOOL remove)
{
	int rc;
	extern int errno;
	UnmapViewOfFile(sharedMemoryFile);
	CloseHandle (hMapFile);
	if (remove)
		rc = unlink(mapFileName);
	return true;
}

//
// shared memory malloc
char *shared_malloc(int nbytes)
{
	struct overhead *p, *q;
	struct qelem *bucket;
	Size surplus;

	nbytes = ((nbytes + (NALIGN-1)) & ~(NALIGN-1))
		+ sizeof(struct overhead);

	for (
	    bucket = &buckets[mlindx(nbytes)];
	    bucket < &buckets[NBUCKETS];
	    bucket++
	) { 
		struct qelem *b;
		for(b = bucket->q_forw; b != bucket; b = b->q_forw) {
			p = FROMBUK(b);
			//ASSERT(p->ov_magic == MAGIC_FREE);
				//"\nmalloc: Entry not marked FREE found on Free List!\n");
			if (p->ov_length >= nbytes) {
				remque(b);
				surplus = p->ov_length - nbytes;
				goto foundit;
			}
		}
	}

	/* obtain additional memory from system */
	{
		Size i;
		p = (struct overhead *)CURBRK;

		i = ((Size)p)&(NALIGN-1);
		if (i != 0)
			p = (struct overhead *)((char *)p + NALIGN - i);

		if (BRK((char *)p + nbytes))
			return(NULL);

		p->ov_length = nbytes;
		surplus = 0;
		insque(TOADJ(p),adjhead.q_back);
	}

foundit:
	/* mark surplus memory free */
	if (surplus > sizeof(struct overhead)) {
		/* if big enough, split it up */
		q = (struct overhead *)((char *)p + nbytes);

		q->ov_length = surplus;
		p->ov_length = nbytes;
		q->ov_magic = MAGIC_FREE;

		/* add surplus into adjacency chain */
		insque(TOADJ(q),TOADJ(p));

		/* add surplus into bucket chain */
		insque(TOBUK(q),&buckets[mlindx(surplus)]);
	}

	p->ov_magic = MAGIC_BUSY;
	return((char*)p + sizeof(struct overhead));
}

/*
 * select the proper size bucket
 */
Size mlindx(Size n)
{
	Size *p, *q, *r;
	p = &mlsizes[0];
	r = &mlsizes[NBUCKETS];
	/* binary search */
	while ((q = (p + (r-p)/2)) > p) {
		if (n < *q)
			r = q;
		else
			p = q;
	}
	return(q - &mlsizes[0]);
}

void mllcerr(char *p)
{
	printf(p);
#ifdef debug
	else
		abort();
#endif debug
}

#ifndef vax
/*
 * The vax has wondrous instructions for inserting and removing items into
 * doubly linked queues.  On the vax the assembler output of the C compiler is
 * massaged by an sed script to turn these function calls into invocations of
 * the insque and remque machine instructions.
 */

void insque(struct qelem *item, struct qelem *queu)
/* insert "item" after "queu" */
{
	struct qelem *pueu;
	pueu = queu->q_forw;
	item->q_forw = pueu;
	item->q_back = queu;
	queu->q_forw = item;
	pueu->q_back = item;
}

void remque(struct qelem *item)
/* remove "item" */
{
	struct qelem *queu, *pueu;
	pueu = item->q_forw;
	queu = item->q_back;
	queu->q_forw = pueu;
	pueu->q_back = queu;
}
#endif

char *sbrk()
{
	return curPtrF;
}

int brk(char *p)
{
	if (p >= memoryLimitF)
		return -1;
	curPtrF = p;	
	return 0;
}

/**************************************************************/

void shared_free(char *mem)
{
	struct overhead *p, *q;
	void mlfree_end();

	if (mem == NULL)
		return;

	p = (struct overhead *)(mem - sizeof(struct overhead));

	/* not advised but allowed */
	if (p->ov_magic == MAGIC_FREE)
		return;

	if (p->ov_magic != MAGIC_BUSY) {	// wrong free called, help out
		return;
	}

	/* try to merge with previous free area */
	q = FROMADJ((TOADJ(p))->q_back);

	if (q != FROMADJ(&adjhead)) {
		ASSERT(q < p);
		//"\nfree: While trying to merge a free area with a lower adjacent free area,\n\
		// addresses were found out of order!\n");
		/* If lower segment can be merged */
		if (   q->ov_magic == MAGIC_FREE
		   && (char *)q + q->ov_length == (char *)p
		) {
			/* remove lower address area from bucket chain */
			remque(TOBUK(q));

			/* remove upper address area from adjacency chain */
			remque(TOADJ(p));

			q->ov_length += p->ov_length;
			p->ov_magic = NULL;	/* decommission */
			p = q;
		}
	}

	/* try to merge with next higher free area */
	q = FROMADJ((TOADJ(p))->q_forw);

	if (q != FROMADJ(&adjhead)) {
		/* upper segment can be merged */
		ASSERT(q > p);
		//"\nfree: While trying to merge a free area with a higher adjacent free area,\n\
		// addresses were found out of order!\n");
		if ( 	q->ov_magic == MAGIC_FREE
		   &&	(char *)p + p->ov_length == (char *)q
		) {
			/* remove upper from bucket chain */
			remque(TOBUK(q));

			/* remove upper from adjacency chain */
			remque(TOADJ(q));

			p->ov_length += q->ov_length;
			q->ov_magic = NULL;	/* decommission */
		}
	}

	p->ov_magic = MAGIC_FREE;

	/* place in bucket chain */
	insque(TOBUK(p),&buckets[mlindx(p->ov_length)]);

	if (endfree)
		mlfree_end();

	return;
}

void mlfree_end()
{
	struct overhead *p;

	p = FROMADJ(adjhead.q_back);
	if (	/* area is free and at end of memory */
	        p->ov_magic == MAGIC_FREE
	    &&	(char*)p + p->ov_length == (char *)CURBRK
	) {
		p->ov_magic = NULL;	/* decommission (just in case) */

		/* remove from end of adjacency chain */
		remque(TOADJ(p));

		/* remove from bucket chain */
		remque(TOBUK(p));

		/* release memory to system */
		(void)BRK((char *)p);
	}
	return;
}

/**********************************************/

char *shared_realloc(char *mem, int nbytes)
{
	char *newmem;
	struct overhead *p, *q;
	Size surplus, length;
	char oendfree;

	if (mem == NULL)
		return((char*)shared_malloc((int)nbytes));

	/* if beyond current arena it has to be bad */
	if(mem > (char*)FROMADJ(adjhead.q_back) + sizeof(struct overhead))
		return(NULL);
	
	p = (struct overhead *)(mem - sizeof(struct overhead));

	if (p->ov_magic != MAGIC_BUSY && p->ov_magic != MAGIC_FREE)
		return(NULL);	/* already gone */

	length = p->ov_length;

	nbytes = (nbytes + (NALIGN-1)) & (~(NALIGN-1));

	if (p->ov_magic == MAGIC_BUSY) {
		oendfree = endfree;	endfree = 0;
		shared_free(mem);	/* free it but don't let it contract break */
		endfree = oendfree;
	}

	if(  p->ov_magic == MAGIC_FREE
	 && (surplus = length - nbytes - sizeof(struct overhead)) >= 0
	) {
		/* shrink area in place */
		if (surplus > sizeof(struct overhead)) {
			q = (struct overhead *)( (char *)p + nbytes
				+ sizeof(struct overhead));
			q->ov_length = surplus;
			q->ov_magic = MAGIC_FREE;
			insque(TOADJ(q),TOADJ(p));
			insque(TOBUK(q),&buckets[mlindx(surplus)]);
			p->ov_length -= surplus;
		}
		/* declare it to be busy */
		remque(TOBUK(p));
		p->ov_magic = MAGIC_BUSY;

		if (endfree)
			mlfree_end();
		return(mem);
	}

	/* if at break, grow in place */
	if (p->ov_magic == MAGIC_FREE && ((char *)p + p->ov_length) == CURBRK) {
		nbytes += sizeof(struct overhead);
		BRK((char *)p + nbytes);
		p->ov_length = nbytes;
		return(mem);
	}

	newmem = shared_malloc((int)nbytes);

	if (newmem != mem && newmem != NULL) {
		Size n;
		n = length - sizeof(struct overhead);
		nbytes = (nbytes < n) ? nbytes: n;
		(void)memcpy(mem,newmem,nbytes);
		/* note:
		 * it is assumed that bcopy does the right thing on overlapping
		 * extents (true on the vax)
		 */
	}

	if (endfree)
		mlfree_end();

	return(newmem);
}