mmlist.c

mmstatd包含一个 C库和服务器

/* $Id: mmlist.c,v 1.3 2003/01/08 20:57:46 mmondor Exp $ */

/*
 * Copyright (C) 2000-2003, Matthew Mondor
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software written by Matthew Mondor.
 * 4. The name of Matthew Mondor may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY MATTHEW MONDOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL MATTHEW MONDOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */




#include <sys/types.h>
#include <stdlib.h>

#include <mmtypes.h>
#include <mmstring.h>
#include <mmlist.h>




MMCOPYRIGHT("@(#) Copyright (c) 2002-2003\n\
\tMatthew Mondor. All rights reserved.\n");
MMRCSID("$Id: mmlist.c,v 1.3 2003/01/08 20:57:46 mmondor Exp $");




/* This function allocates a node in a very efficient way, only extracting it
 * from a pre-allocated list. If no more buffered nodes, a new page buffer is
 * prepared for more if the maximum pages limit is not reached, and the first
 * new node returned. NULL is returned on error.
 */
node *
allocnode(list *lst, bool zero)
{
    register node *nod;
    bpool *pol = lst->pool;

    /* First attempt to quickly return any available node from buffer */
    if ((nod = pol->bnodes.top)) {
	nod->page->used++;
	UNLINKNODE(&pol->bnodes, nod);
	if (zero) {
	    register bpage *bp = nod->page;

	    mm_memclr(nod, pol->nodesize);
	    nod->page = bp;
	}
	return (nod);
    } else {
	bpage *pag;
	register char *ptr, *toptr;
	register size_t nodelen = pol->nodesize, nodesize;

	/* We need to setup a new page of prebuffered nodes */
	if (!pol->maxpages || pol->bpages.nodes < pol->maxpages) {
	    /* Quickly get any pre-buffered page, or allocate a new
	     * one if none available.
	     */
	    if ((pag = (bpage *)pol->bfpages.top) != NULL)
		UNLINKNODE(&pol->bfpages, (node *)pag);
	    else pag = pol->malloc(sizeof(bpage) + pol->pagesize);
	    if (pag) {
		/* Prepare prebuffered nodes from new page */
		pag->pool = pol;
		pag->used = 0;
		APPENDNODE(&pol->bpages, (node *)pag);
		/* Prepare page buffered nodes */
		ptr = (char *)pag;
		ptr += sizeof(bpage);
		toptr = ptr + pol->pagesize;
		ptr = (char *)MMALIGN_CEIL(ptr, long);
		nodesize = (size_t)MMALIGN_CEIL(nodelen, long);
		while (ptr + nodelen < toptr) {
		    ((node *)ptr)->page = pag;
		    APPENDNODE(&pol->bnodes, (node *)ptr);
		    ptr += nodesize;
		}
		/* Now extract first node and return it */
		nod = pol->bnodes.top;
		nod->page->used++;
		UNLINKNODE(&pol->bnodes, nod);
		if (zero) {
		    register bpage *bp = nod->page;

		    mm_memclr(nod, pol->nodesize);
		    nod->page = bp;
		}
		return (nod);
	    }
	}

	return (NULL);
    }
}


/* This function is similar to openlist() but is technically different. We
 * specify the number of maximum nodes we will need, as well as size of a node.
 * The function then allocates a single block of memory which will be managed
 * to allow allocnode()/freenode() to function properly. When the block/list
 * is no longer required a simple free() can be performed on the returned
 * address (list structure pointer) to free the whole block back. Of course
 * unlike dynamic lists created with openlist() these are fixed. This is
 * particularly useful under some circumstances, for instance to init a shared
 * memory linked list using shmget() for other processes to share. closelist()
 * can still be called on this list, but it's obvious that freeing the memory
 * block is enough. Interesting uses for this list type consist of stacks,
 * FIFOs using a fixed buffer size, for message queues, etc.
 */
list *
blocklist(void *(*mallocfunc)(size_t), void (*freefunc)(void *),
	size_t nodelen, long mnodes)
{
    list *lst;
    bpool *pol;
    bpage *pag;
    register char *ptr, *toptr;
    size_t listsize, bpoolsize, bpagesize, blocksize, nodesize;
    void *block;

    /* First evaluate required buffer size to hold the list with all
     * requested nodes. The size of the list and node structures are
     * rounded so that all units remain long-aligned always.
     */
    listsize = (size_t)MMALIGN_CEIL(sizeof(list), long);
    bpoolsize = (size_t)MMALIGN_CEIL(sizeof(bpool), long);
    bpagesize = (size_t)MMALIGN_CEIL(sizeof(bpage), long);
    nodesize = (size_t)MMALIGN_CEIL(nodelen, long);
    blocksize = listsize + bpoolsize + bpagesize + (nodesize * (mnodes + 1));

    /* Allocate single memory block */
    if ((block = mallocfunc(blocksize)) != NULL) {

	/* Fix pointers */
	ptr = block;
	lst = (list *)ptr;
	ptr += listsize;
	pol = (bpool *)ptr;
	ptr += bpoolsize;
	pag = (bpage *)ptr;
	ptr += bpagesize;
	toptr = ptr;
	toptr += (nodesize * (mnodes + 1));

	/* Finally initialize everything */
	lst->top = lst->bottom = NULL;
	lst->nodes = 0;
	lst->pool = pol;
	pol->malloc = mallocfunc;
	pol->free = freefunc;
	pol->maxpages = pol->avgtotal = pol->avgcnt = 1;
	pol->nodesize = nodelen;
	pol->pagesize = (nodesize * mnodes);
	INITLIST(&pol->bpages);
	INITLIST(&pol->bfpages);
	INITLIST(&pol->bnodes);
	pol->block = TRUE;
	pag->pool = pol;
	pag->used = 0;
	APPENDNODE(&pol->bpages, (node *)pag);
	while (mnodes && ptr + nodesize < toptr) {
	    ((node *)ptr)->page = pag;
	    APPENDNODE(&pol->bnodes, (node *)ptr);
	    ptr += nodesize;
	    mnodes--;
	}

	return (lst);
    }

    return (NULL);
}


/* Frees all memory in use by a list, including any optional pool of pages.
 * Of course, all nodes allocated with allocnode() for this list if a pool
 * was setup, are no longer useable, as they are part of the allocated pages
 * which we free, even if they were swapped to other lists and not swapped
 * back in the master list.
 */
list *
closelist(list *lst)
{
    if (lst->pool) {
	register void (*freefunc)(void *) = lst->pool->free;
	if (!lst->pool->block) {
	    register list *pages = &(lst->pool->bpages);
	    register bpage *pag;
	    /* We are holding a pool of pages, simply free them all, all
	     * our allocated nodes are part of our pages, and we want to
	     * free all nodes anyways (which will get magically discarded).
	     */
	    while ((pag = (bpage *)pages->top)) {
		UNLINKNODE(pages, (node *)pag);
		freefunc(pag);
	    }
	    pages = &(lst->pool->bfpages);
	    while ((pag = (bpage *)pages->top)) {
		UNLINKNODE(pages, (node *)pag);
		freefunc(pag);
	    }
	}
	freefunc(lst);
    }

    return (NULL);
}


/* This function returns a node in the available nodes pool, it thus should
 * be very efficient. The freed node is then available again for allocnode().
 * If a buffered page becomes unused, we keep it for some while until usage
 * statistics show that we should free them. We also always make sure that
 * at least one page of buffered nodes remain. Of course, before calling
 * freenode() the programmer should ensure that the node was first unlinked
 * from any previous list it was part of. We insert the freed nodes
 * at the top of the available nodes list, which privileges previously
 * allocated ones, thus reducing memory useage.
 */
node *
freenode(node * nod)
{
    bpool *pool = nod->page->pool;
    list *bnodes = &(pool->bnodes);
    list *bpages = &(pool->bpages);
    void (*freefunc)(void *) = pool->free;
    size_t nodesize;

    /* Maintain statistics to know how many pages we should keep buffered,
     * and reset them from time to time to make sure we always observe current
     * usage patterns.
     */
    if (!pool->block) {
	pool->avgtotal += bpages->nodes;
	pool->avgcnt++;
	if (pool->avgcnt > ((pool->pagesize / pool->nodesize) * 3)) {
	    pool->avgcnt = 1;
	    pool->avgtotal = bpages->nodes;
	}
    }

    /* Quickly free node by restoring it in our free nodes pool for eventual
     * recycling.
     */
    INSERTNODE(bnodes, nod);
    nod->page->used--;
    if (!nod->page->used && bpages->nodes > 1) {
	register char *ptr, *toptr;
	register size_t nodelen = pool->nodesize;
	bpage *pag = nod->page;
	long exceeding;

	/* A page is no longer in use and it's not the last one.
	 * Unlink all nodes provided from that page from buffer,
	 * and free page. We take the required CPU time to free
	 * all nodes independently, using their real address, since
	 * their links may be in any order in the free list.
	 * We cannot assume that applications free nodes in a specific
	 * order, unfortunately.
	 */
	ptr = (char *)pag;
	ptr += sizeof(bpage);
	toptr = ptr + pool->pagesize;
	ptr = (char *)MMALIGN_CEIL(ptr, long);
	nodesize = (size_t)MMALIGN_CEIL(nodelen, long);
	while (ptr + nodesize < toptr) {
	    UNLINKNODE(bnodes, (node *)ptr);
	    ptr += nodesize;
	}
	/* Move no longer used page to our free pages pool. Insert it so
	 * that it can be used again very soon for performance.
	 */
	SWAPNODE(&pool->bfpages, bpages, (node *)pag, TRUE);

	/* Verify if average page usage statistics show that we should free
	 * pages from our pool, and do so if needed.
	 */
	if ((exceeding = (bpages->nodes + pool->bfpages.nodes) -
		    (pool->avgtotal / pool->avgcnt)) > 0) {
	    register list *bfpages = &pool->bfpages;

	    /* Preferably free pages which haven't been used recently */
	    while (exceeding > 0 && (nod = bfpages->bottom)) {
		UNLINKNODE(bfpages, nod);
		freefunc(nod);
		exceeding--;
	    }
	}
    }

    return (NULL);
}


/* Prepares a list structure, and optionally a pool of prebuffered nodes,
 * consisting of one page, if pgsize is non-zero. If mpages is non-zero,
 * it specifies the maximum number of pages that should be allocated and
 * setup for prebuffering nodes. The pool is used for the implementation of
 * the efficient allocnode()/freenode() functions.
 */
list *
openlist(void *(*mallocfunc)(size_t), void (*freefunc)(void *),
	size_t nodelen, size_t pgsize, long mpages)
{
    list *lst;
    char *block = NULL;
    bpool *pol = NULL;
    bpage *pag = NULL;
    register char *ptr, *toptr;
    size_t nodesize, blocksize;

    blocksize = sizeof(list) + sizeof(bpool);
    if (pgsize && nodelen && (block = mallocfunc(blocksize)) != NULL &&
	(pag = mallocfunc(sizeof(bpage) + pgsize)) != NULL) {
	lst = (list *)block;
	lst->top = lst->bottom = NULL;
	lst->nodes = 0;
	ptr = block;
	ptr += sizeof(list);
	pol = (bpool *)ptr;
	pol->malloc = mallocfunc;
	pol->free = freefunc;
	pol->nodesize = nodelen;
	pol->pagesize = pgsize;
	pol->maxpages = mpages;
	pol->avgtotal = pol->avgcnt = 1;
	INITLIST(&pol->bpages);
	INITLIST(&pol->bfpages);
	INITLIST(&pol->bnodes);
	pag->pool = pol;
	pag->used = 0;
	APPENDNODE(&pol->bpages, (node *)pag);
	lst->pool = pol;
	/* Prepare buffered nodes from page */
	ptr = (char *)pag;
	ptr += sizeof(bpage);
	toptr = ptr + pol->pagesize;
	ptr = (char *)MMALIGN_CEIL(ptr, long);
	nodesize = (size_t)MMALIGN_CEIL(nodelen, long);
	while (ptr + nodesize < toptr) {
	    ((node *)ptr)->page = pag;
	    APPENDNODE(&pol->bnodes, (node *)ptr);
	    ptr += nodesize;
	}
	return (lst);
    }
    if (block)
	freefunc(block);

    return (NULL);
}