source: rtems/cpukit/httpd/balloc.c @ 4bf1801

/*
 * balloc.c -- Block allocation module
 *
 * Copyright (c) GoAhead Software Inc., 1995-1999. All Rights Reserved.
 *
 * See the file "license.txt" for usage and redistribution license requirements
 */

/******************************** Description *********************************/

/*
 *      This module implements a very fast block allocation scheme suitable for
 *      ROMed environments. It maintains block class queues for rapid allocation
 *      and minimal fragmentation. This modules does not coalesce blocks. The 
 *      storage space may be populated statically or via the traditional malloc 
 *      mechanisms. Large blocks greater than the maximum class size may be 
 *      allocated from the O/S or run-time system via malloc. To permit the use 
 *      of malloc, call bopen with flags set to B_USE_MALLOC (this is the default).
 *      It is recommended that bopen be called first thing in the application. 
 *      If it is not, it will be called with default values on the first call to 
 *      balloc(). Note that this code is not designed for multi-threading purposes
 *      and it depends on newly declared variables being initialized to zero.
 */  

/********************************* Includes ***********************************/

#define IN_BALLOC

#if UEMF
        #include        "uemf.h"
#else
        #include        "basic/basicInternal.h"
#endif

#include        <stdarg.h>
#include        <stdlib.h>

#if !NO_BALLOC
/********************************* Defines ************************************/

typedef struct {
        union {
                void    *next;                                                  /* Pointer to next in q */
                int             size;                                                   /* Actual requested size */
        } u;
        int                     flags;                                                  /* Per block allocation flags */
} bType;

/*
 *      Define B_STATS if you wish to track memory block and stack usage
 */
#if B_STATS
/*
 *      Optional statistics
 */

typedef struct {
        long    alloc;                                                          /* Block allocation calls */
        long    inuse;                                                          /* Blocks in use */
} bStatsType;

typedef struct {
        char_t  file[FNAMESIZE];
        long    allocated;                                                      /* Bytes currently allocated */
        long    count;                                                          /* Current block count */
        long    allocs;                                                         /* Count of alloc attempts */
} bStatsFileType;

/*
 *      This one is very expensive but great stats
 */
typedef struct {
        void                    *ptr;                                           /* Pointer to memory */
        bStatsFileType  *who;                                           /* Who allocated the memory */
} bStatsBlkType;

static bStatsType               bStats[B_MAX_CLASS];    /* Per class stats */
static bStatsFileType   bStatsFiles[B_MAX_FILES];/* Per file stats */
static bStatsBlkType    bStatsBlks[B_MAX_BLOCKS];/* Per block stats */
static int                              bStatsBlksMax;                  /* Max block entry */
static int                              bStatsFilesMax;                 /* Max file entry */
static int                              bStatsMemInUse;                 /* Memory currently in use */
static int                              bStatsMemMax;                   /* Max memory ever used */
static void                             *bStackMin = (void*) -1;/* Miniumum stack position */
static void                             *bStackStart;                   /* Starting stack position */
static int                              bStatsMemMalloc;                /* Malloced memory */
#endif /* B_STATS */


/********************************** Locals ************************************/
/*
 *      bQhead blocks are created as the original memory allocation is freed up.
 *      See bfree.
 */
static bType                    *bQhead[B_MAX_CLASS];   /* Per class block q head */
static char                             *bFreeBuf;                              /* Pointer to free memory */
static char                             *bFreeNext;                             /* Pointer to next free mem */
static int                              bFreeSize;                              /* Size of free memory */
static int                              bFreeLeft;                              /* Size of free left for use */
static int                              bFlags = B_USE_MALLOC;  /* Default to auto-malloc */

/*************************** Forward Declarations *****************************/

#if B_STATS
static void bStatsAlloc(B_ARGS_DEC, void *ptr, int q, int size);
static void bStatsFree(B_ARGS_DEC, void *ptr, int q, int size);
static void bstatsWrite(int handle, char_t *fmt, ...);
static int      bStatsFileSort(const void *cp1, const void *cp2);
#endif /* B_STATS */

#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
static void bFillBlock(void *buf, int bufsize);
#endif

#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
static void verifyUsedBlock(bType *bp, int q);
static void verifyFreeBlock(bType *bp, int q);
static void verifyBallocSpace();
#endif

/********************************** Code **************************************/
/*
 *      Initialize the balloc module. bopen should be called the very first thing
 *      after the application starts and bclose should be called the last thing 
 *      before exiting. If bopen is not called, it will be called on the first 
 *      allocation with default values. "buf" points to memory to use of size 
 *      "bufsize". If buf is NULL, memory is allocated using malloc. flags may 
 *      be set to B_USE_MALLOC if using malloc is okay. This routine will allocate
 *      an initial buffer of size bufsize for use by the application.
 */

int bopen(void *buf, int bufsize, int flags)
{
        bFlags = flags;

        if (buf == NULL) {
                if (bufsize == 0) {
                        bufsize = B_DEFAULT_MEM;
                }
                if ((buf = malloc(bufsize)) == NULL) {
                        return -1;
                }
#if B_STATS
                bStatsMemMalloc += bufsize;
#endif
        } else {
                bFlags |= B_USER_BUF;
        }

        bFreeSize = bFreeLeft = bufsize;
        bFreeBuf = bFreeNext = buf;
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
        bFillBlock(buf, bufsize);
#endif
#if B_STATS
        bStackStart = &buf;
#endif
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
        verifyFreeBlock(buf, bufsize);
#endif
        return 0;
}

/******************************************************************************/
/*
 *      Close down the balloc module and free all malloced memory.
 */

void bclose()
{
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
        verifyBallocSpace();
#endif
        if (! (bFlags & B_USER_BUF)) {
                free(bFreeBuf);
        }
}

/******************************************************************************/
/*
 *      Allocate a block of the requested size. First check the block 
 *      queues for a suitable one.
 */

void *balloc(B_ARGS_DEC, int size)
{
        bType   *bp;
        int             q, memSize, mask;

/*
 *      Call bopen with default values if the application has not yet done so
 */
        if (bFreeBuf == NULL) {
                if (bopen(NULL, B_DEFAULT_MEM , 0) < 0) {
                        return NULL;
                }
        }
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
        verifyBallocSpace();
#endif
        if (size < 0) {
                return NULL;
        }

/*
 *      Determine the relevant block queue with a block big enough --  
 *      include room for the block header. 
 */
        mask = (size + sizeof(bType)) >> B_SHIFT;
        for (q = 0; mask; mask >>= 1) {
                q++;
        }

        a_assert(0 <= q && q <= B_MAX_CLASS);
        memSize = (1 << (B_SHIFT + q));

        if (q >= B_MAX_CLASS) {
/*
 *              Size if bigger than the maximum class. Malloc if use has been okayed
 */
                if (bFlags & B_USE_MALLOC) {
#if B_STATS
                        bstats(0, NULL);
#endif
                        bp = (bType*) malloc(memSize);
                        if (bp == NULL) {
                                trace(0, T("B: malloc failed for %s:%d, size %d\n"),
                                        B_ARGS, memSize);
                                return NULL;
                        }
#if B_STATS
                        bStatsMemMalloc += memSize;
#endif
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
                        bFillBlock(bp, memSize);
#endif

                } else {
                        trace(0, T("B: balloc failed for %s:%d, size %d\n"),
                                B_ARGS, memSize);
                        return NULL;
                }
                bp->u.size = size;
                bp->flags = B_MALLOCED;

        } else if ((bp = bQhead[q]) != NULL) {
/*
 *              Take first block off the relevant q if non-empty
 */
                bQhead[q] = bp->u.next;
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
                verifyFreeBlock(bp, q);
#endif
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
                bFillBlock(bp, memSize);
#endif
                bp->u.size = size;
                bp->flags = 0;

        } else {
                if (bFreeLeft > memSize) {
/*
 *                      The q was empty, and the free list has spare memory so 
 *                      create a new block out of the primary free block
 */
                        bp = (bType*) bFreeNext;
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
                        verifyFreeBlock(bp, q);
#endif
                        bFreeNext += memSize;
                        bFreeLeft -= memSize;
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
                        bFillBlock(bp, memSize);
#endif
                        bp->u.size = size;
                        bp->flags = 0;

                } else if (bFlags & B_USE_MALLOC) {
                        static int once = 0;
                        if (once++ < 20) {
#if B_STATS
                                bstats(0, NULL);
#endif
                        }
/*
 *                      Nothing left on the primary free list, so malloc a new block
 */
                        if ((bp = (bType*) malloc(memSize)) == NULL) {
                                trace(0, T("B: malloc failed for %s:%d size %d\n"),
                                        B_ARGS, memSize);
                                return NULL;
                        }
#if B_STATS
                        bStatsMemMalloc += memSize;
#endif
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
                        bFillBlock(bp, memSize);
#endif
                        bp->u.size = size;
                        bp->flags = B_MALLOCED;

                } else {
                        trace(0, T("B: alloc failed for %s:%d size %d\n"), B_ARGS, size);
                        return NULL;
                }
        }

#if B_STATS
        bStatsAlloc(B_ARGS, bp, q, size);
#endif
        bp->flags |= B_INTEGRITY;

        return (void*) ((char*) bp + sizeof(bType));
}

/******************************************************************************/
/*
 *      Free a block back to the relevant free q. We don't free back to the O/S
 *      or run time system unless the block is greater than the maximum class size.
 *      We also do not coalesce blocks.
 */

void bfree(B_ARGS_DEC, void *mp)
{
        bType   *bp;
        int             mask, q;

#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
        verifyBallocSpace();
#endif
        a_assert(mp);

        bp = (bType*) ((char*) mp - sizeof(bType));
        a_assert((bp->flags & B_INTEGRITY_MASK) == B_INTEGRITY);
        if ((bp->flags & B_INTEGRITY_MASK) != B_INTEGRITY) {
                return;
        }

/*
 *      Determine the relevant block queue
 */
        mask = (bp->u.size + sizeof(bType)) >> B_SHIFT;
        for (q = 0; mask; mask >>= 1) {
                q++;
        }
        a_assert(0 <= q && q <= B_MAX_CLASS);

#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
        verifyUsedBlock(bp,q);
#endif
        if (bp->flags & B_MALLOCED) {
                free(bp);
                return;
        }
                
#if B_STATS
        bStatsFree(B_ARGS, bp, q, bp->u.size);
#endif
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
        bFillBlock(bp, 1 << (B_SHIFT + q));
#endif

/*
 *      Simply link onto the head of the relevant q
 */
        bp->u.next = bQhead[q];
        bQhead[q] = bp;
}

/******************************************************************************/
/*
 *      Safe free
 */

void bfreeSafe(B_ARGS_DEC, void *mp)
{
        if (mp) {
                bfree(B_ARGS, mp);
        }
}

/******************************************************************************/
#if UNICODE
/*
 *      Duplicate a string, allow NULL pointers and then dup an empty string.
 */

char *bstrdupA(B_ARGS_DEC, char *s)
{
        char    *cp;
        int             len;

        if (s == NULL) {
                s = "";
        }
        len = strlen(s) + 1;
        if (cp = balloc(B_ARGS, len)) {
                strcpy(cp, s);
        }
        return cp;
}

#endif /* UNICODE */
/******************************************************************************/
/*
 *      Duplicate an ascii string, allow NULL pointers and then dup an empty string.
 *      If UNICODE, bstrdup above works with wide chars, so we need this routine
 *      for ascii strings. 
 */

char_t *bstrdup(B_ARGS_DEC, char_t *s)
{
        char_t  *cp;
        int             len;

        if (s == NULL) {
                s = T("");
        }
        len = gstrlen(s) + 1;
        if ((cp = balloc(B_ARGS, len * sizeof(char_t))) != NULL) {
                gstrcpy(cp, s);
        }
        return cp;
}

/******************************************************************************/
/*
 *      Reallocate a block. Allow NULL pointers and just do a malloc.
 *      Note: if the realloc fails, we return NULL and the previous buffer is 
 *      preserved.
 */

void *brealloc(B_ARGS_DEC, void *mp, int newsize)
{
        bType*  bp;
        void    *newbuf;

        if (mp == NULL) {
                return balloc(B_ARGS, newsize);
        }
        bp = (bType*) ((char*) mp - sizeof(bType));
        a_assert((bp->flags & B_INTEGRITY_MASK) == B_INTEGRITY);
        if ((newbuf = balloc(B_ARGS, newsize)) != NULL) {
                memcpy(newbuf, mp, bp->u.size);
                bfree(B_ARGS, mp);
        }
        return newbuf;
}


/******************************************************************************/
#if B_FILL || B_VERIFY_CAUSES_SEVERE_OVERHEAD
/*
 *      Fill the block (useful during development to catch zero fill assumptions)
 */

static void bFillBlock(void *buf, int bufsize)
{
        memset(buf, B_FILL_CHAR, bufsize);
}
#endif

/******************************************************************************/
#if B_STATS
/*
 *      Statistics. Do output via calling the writefn callback function with 
 *      "handle" as the output file handle.
 */

void bstats(int handle, void (*writefn)(int handle, char_t *fmt, ...))
{
        bStatsFileType  *fp;
        bType                   *bp;
        int                             q, count, mem, total;
        static  int     recurseProtect = 0;

        if (recurseProtect++ > 0) {
                return;
        }

        if (writefn == NULL) {
                writefn = bstatsWrite;
        }

/*
 *      Print stats for each memory block
 */
        (*writefn)(handle, T("\nMemory Stats\n"));

/*
 *      The following tabular format is now used for the output.
 *   Q  Size  Free Bytes Inuse Bytes Allocs
 *      dd ddddd   ddd ddddd  dddd ddddd   dddd
 */
        (*writefn)(handle, " Q  Size  Free Bytes Inuse Bytes Allocs\n");

        total = 0;
        for (q = 0; q < B_MAX_CLASS; q++) {
                count = 0;
                for (bp = bQhead[q]; bp; bp = bp->u.next) {
                        a_assert((bp->flags & B_INTEGRITY_MASK) == B_INTEGRITY);
                        count++;
                }
                mem = count * (1 << (q + B_SHIFT));
                total += mem;
                (*writefn)(handle, 
                        T("%2d %5d   %3d %5d  %4d %5d   %4d\n"),
                        q, 1 << (q + B_SHIFT), count, mem, bStats[q].inuse, 
                        bStats[q].inuse * (1 << (q + B_SHIFT)), bStats[q].alloc);
        }

        (*writefn)(handle, T("\n"));

/*
 *      Print summary stats
 */
        (*writefn)(handle, T("Initial free list size    %7d\n"), bFreeSize);
        (*writefn)(handle, T("Max memory malloced       %7d\n"), bStatsMemMalloc);
        (*writefn)(handle, T("Max memory ever used      %7d\n"), bStatsMemMax);
        (*writefn)(handle, T("Memory currently in use   %7d\n"), bStatsMemInUse);
        (*writefn)(handle, T("Max blocks allocated      %7d\n"), bStatsBlksMax);
        (*writefn)(handle, T("Maximum stack used        %7d\n"), 
                (int) bStackStart - (int) bStackMin);

        (*writefn)(handle, T("Free memory on all queues %7d\n"), total);
        (*writefn)(handle, T("Free list buffer left     %7d\n"), bFreeLeft);
        (*writefn)(handle, T("Total free memory         %7d\n"), bFreeLeft + total);

/*
 *      Print per file allocation stats
 */
        qsort(bStatsFiles, bStatsFilesMax, sizeof(bStatsFileType), bStatsFileSort);
        (*writefn)(handle, T("\nPer File Memory Stats\n"));
        total = 0;
        for (fp = bStatsFiles; fp < &bStatsFiles[bStatsFilesMax]; fp++) {
                if (fp->file[0]) {
                        (*writefn)(handle, 
                                T("%18s, bytes %7d, blocks in use %5d, total allocs %6d\n"),
                                fp->file, fp->allocated, fp->count, fp->allocs);
                        total += fp->allocated;
                }
        }
        (*writefn)(handle, T("\nTotal allocated %7d\n"), total);
        recurseProtect--;
}

/******************************************************************************/
/*
 *      File sort function. Used to sort per file stats
 */

static int bStatsFileSort(const void *cp1, const void *cp2)
{
        bStatsFileType  *s1, *s2;

        s1 = (bStatsFileType*) cp1;
        s2 = (bStatsFileType*) cp2;

        if (s1->allocated < s2->allocated)
                return -1;
        else if (s1->allocated == s2->allocated)
                return 0;
        return 1;
}

/******************************************************************************/
/*
 *      Default output function. Just send to trace channel.
 */

static void bstatsWrite(int handle, char_t *fmt, ...)
{
        va_list         args;
        char_t          *buf;

        va_start(args, fmt);
        buf = NULL;
        gvsnprintf(&buf, VALUE_MAX_STRING, fmt, args);
        va_end(args);
        trace(0, buf);
        if (buf) {
                bfree(B_L, buf);
        }
}

/******************************************************************************/
/*
 *      Accumulate allocation statistics
 */

static void bStatsAlloc(B_ARGS_DEC, void *ptr, int q, int size)
{
        bStatsFileType  *fp;
        bStatsBlkType   *bp;
        char_t                  name[FNAMESIZE + 10];

        a_assert(file && *file);
        a_assert(0 <= q && q <= B_MAX_CLASS);
        a_assert(size > 0);

        gsprintf(name, T("%s:%d"), B_ARGS);

        bStats[q].alloc++;
        bStats[q].inuse++;
        bStatsMemInUse += size;

        if (bStatsMemInUse > bStatsMemMax) {
                bStatsMemMax = bStatsMemInUse;
        }

/*
 *      Track maximum stack usage. Assumes a stack growth down. Approximate as
 *      we only measure this on block allocation.
 */
        if ((void*) &file < bStackMin) {
                bStackMin = (void*) &file;
        }

/*
 *      Find the file and adjust the stats for this file
 */
        for (fp = bStatsFiles; fp < &bStatsFiles[bStatsFilesMax]; fp++) {
                if (fp->file[0] == file[0] && gstrcmp(fp->file, name) == 0) {
                        fp->allocated += size;
                        fp->count++;
                        fp->allocs++;
                        break;
                }
        }

/*
 *      Find the first free slot for this file and add current block size.
 */
        if (fp >= &bStatsFiles[bStatsFilesMax]) {
                for (fp = bStatsFiles; fp < &bStatsFiles[B_MAX_FILES]; fp++) {
                        if (fp->file[0] == '\0') {
                                gstrncpy(fp->file, name, TSZ(fp->file));
                                fp->allocated += size;
                                fp->count++;
                                fp->allocs++;
                                if ((fp - bStatsFiles) >= bStatsFilesMax) {
                                        bStatsFilesMax = (fp - bStatsFiles) + 1;
                                }
                                break;
                        }
                }
        }

/*
 *      Update the per block stats. Allocate a new slot.
 */
        for (bp = bStatsBlks; bp < &bStatsBlks[B_MAX_BLOCKS]; bp++) {
                if (bp->ptr == NULL) {
                        bp->ptr = ptr;
                        bp->who = fp;
                        if ((bp - bStatsBlks) >= bStatsBlksMax) {
                                bStatsBlksMax = (bp - bStatsBlks) + 1;
                        }
                        break;
                }
        }
}

/******************************************************************************/
/*
 *      Free statistics
 */

static void bStatsFree(B_ARGS_DEC, void *ptr, int q, int size)
{
        bStatsFileType  *fp;
        bStatsBlkType   *bp;
        char_t                  name[FNAMESIZE + 10];

        a_assert(file && *file);
        a_assert(0 <= q && q <= B_MAX_CLASS);
        a_assert(size > 0);

        bStatsMemInUse -= size;
        bStats[q].inuse--;

        gsprintf(name, T("%s:%d"), B_ARGS);

/*
 *      Update the per block stats 
 */
        for (bp = bStatsBlks; bp < &bStatsBlks[bStatsBlksMax]; bp++) {
                if (bp->ptr == ptr) {
                        bp->ptr = NULL;
                        fp = bp->who;
                        fp->allocated -= size;
                        fp->count--;
                        return;
                }
        }
        a_assert(0);

}

#else /* not B_STATS */
/******************************************************************************/
/*
 *      Dummy bstats for external calls that aren't protected by #if B_STATS.
 */

void bstats(int handle, void (*writefn)(int handle, char_t *fmt, ...))
{
}
#endif /* B_STATS */

/******************************************************************************/
#if B_VERIFY_CAUSES_SEVERE_OVERHEAD
/*
 *      The following routines verify the integrity of the balloc memory space.
 *      These functions depend use the B_FILL feature.  Corruption is defined
 *      as bad integrity flags in allocated blocks or data other than B_FILL_CHAR
 *      being found anywhere in the space which is unallocated and that is not a
 *      next pointer in the free queues.  a_assert is called if any corruption is
 *      found.  CAUTION:  These functions add severe processing overhead and should
 *      only be used when searching for a tough corruption problem.
 */

/******************************************************************************/
/*
 *      verifyUsedBlock verifies that a block which was previously allocated is
 *      still uncorrupted.  
 */

static void verifyUsedBlock(bType *bp, int q)
{
        int             memSize, size;
        char    *p;

        memSize = (1 << (B_SHIFT + q));
        a_assert((bp->flags & ~B_MALLOCED) == B_INTEGRITY );
        size = bp->u.size;
        for (p = ((char *)bp)+sizeof(bType)+size; p < ((char*)bp)+memSize; p++) {
                a_assert(*p == B_FILL_CHAR);
        }
}

/******************************************************************************/
/*
 *      verifyFreeBlock verifies that a previously free'd block in one of the queues
 *      is still uncorrupted.
 */

static void verifyFreeBlock(bType *bp, int q)
{
        int             memSize;
        char    *p;

        memSize = (1 << (B_SHIFT + q));
        for (p = ((char *)bp)+sizeof(void*); p < ((char*)bp)+memSize; p++) {
                a_assert(*p == B_FILL_CHAR);
        }
        bp = (bType *)p;
        a_assert((bp->flags & ~B_MALLOCED) == B_INTEGRITY ||
                                bp->flags == B_FILL_WORD);
}

/******************************************************************************/
/*
 *      verifyBallocSpace reads through the entire balloc memory space and
 *      verifies that all allocated blocks are uncorrupted and that with the
 *      exception of free list next pointers all other unallocated space is
 *      filled with B_FILL_CHAR.
 */

static void verifyBallocSpace()
{
        char    *p;
        bType   *bp;

        p = bFreeBuf;
        while (p < (bFreeBuf + bFreeSize)) {
                bp = (bType *)p;
                if (bp->u.size > 0xFFFFF) {
                        p += sizeof(bp->u);
                        while (p < (bFreeBuf + bFreeSize) && *p == B_FILL_CHAR) {
                                p++;
                        }
                } else {
                        a_assert(((bp->flags & ~B_MALLOCED) == B_INTEGRITY) ||
                                                bp->flags == B_FILL_WORD);
                        p += (sizeof(bType) + bp->u.size);
                        while (p < (bFreeBuf + bFreeSize) && *p == B_FILL_CHAR) {
                                p++;
                        }
                }
        }
}
#endif /* B_VERIFY_CAUSES_SEVERE_OVERHEAD */

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

#else /* NO_BALLOC */
int bopen(void *buf, int bufsize, int flags)
{
        return 0;
}

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

void bclose()
{
}

/******************************************************************************/
#if UNICODE
char_t* bstrdupNoBalloc(char_t* s)
{
        if (s) {
                return wcsdup(s);
        } else {
                return wcsdup(T(""));
        }
}
#endif /* UNICODE */

/******************************************************************************/
char* bstrdupANoBalloc(char* s)
{
        char*   buf;

        if (s == NULL) {
                s = "";
        }
        buf = malloc(strlen(s)+1);
        strcpy(buf, s);
        return buf;
}

#endif /* NO_BALLOC */
/******************************************************************************/