/*
 * tclThreadAlloc.c --
 *
 *	This is a very fast storage allocator for used with threads (designed
 *	avoid lock contention). The basic strategy is to allocate memory in
 *	fixed size blocks from block caches.
 *
 * The Initial Developer of the Original Code is America Online, Inc.
 * Portions created by AOL are Copyright (C) 1999 America Online, Inc.
 *
 * See the file "license.terms" for information on usage and redistribution of
 * this file, and for a DISCLAIMER OF ALL WARRANTIES.
 *
 * RCS: @(#) $Id: tclThreadAlloc.c,v 1.24 2007/12/13 15:23:20 dgp Exp $
 * RCS: @(#) $Id: tclThreadAlloc.c,v 1.25 2007/12/17 15:28:28 msofer Exp $
 */

#include "tclInt.h"
#if defined(TCL_THREADS) && defined(USE_THREAD_ALLOC)

/*
 * If range checking is enabled, an additional byte will be allocated to store

 * the high water mark to prune a per-thread cache. On a 32 bit system,
 * sizeof(Tcl_Obj) = 24 so 800 * 24 = ~16k.
 */

#define NOBJALLOC	800
#define NOBJHIGH	1200

/*
 * Alignment for allocated memory.
 */

#if defined(__APPLE__)
#define ALLOCALIGN	16
#else
#define ALLOCALIGN	8
#endif

/*
 * The following union stores accounting information for each block including
 * two small magic numbers and a bucket number when in use or a next pointer
 * when free. The original requested size (not including the Block overhead)
 * is also maintained.
 */

typedef union Block {
    struct {
	union {
	    union Block *next;		/* Next in free list. */
	    struct {
		unsigned char magic1;	/* First magic number. */
		unsigned char bucket;	/* Bucket block allocated from. */
		unsigned char unused;	/* Padding. */
		unsigned char magic2;	/* Second magic number. */
	    } s;
	} u;
	size_t reqSize;			/* Requested allocation size. */
    } b;
    unsigned char padding[ALLOCALIGN];
    unsigned char padding[TCL_ALLOCALIGN];
} Block;
#define nextBlock	b.u.next
#define sourceBucket	b.u.s.bucket
#define magicNum1	b.u.s.magic1
#define magicNum2	b.u.s.magic2
#define MAGIC		0xEF
#define blockReqSize	b.reqSize

/*
 * The following defines the minimum and and maximum block sizes and the number
 * of buckets in the bucket cache.
 */

#define MINALLOC	((sizeof(Block) + 8 + (ALLOCALIGN-1)) & ~(ALLOCALIGN-1))
#define MINALLOC	((sizeof(Block) + 8 + (TCL_ALLOCALIGN-1)) & ~(TCL_ALLOCALIGN-1))
#define NBUCKETS	(11 - (MINALLOC >> 5))
#define MAXALLOC	(MINALLOC << (NBUCKETS - 1))

/*
 * The following structure defines a bucket of blocks with various accounting
 * and statistics information.
 */