/*
 * @(#)palloc.h 22.1 89/08/10 SMI
 */

/*
 * Copyright (c) 1988 by Sun Microsystems, Inc.
 */

/*
 * palloc.h
 *	Definitions for the interface to the page localizing
 *	memory allocation mechanism.
 */

#ifndef PALLOC

#define Sgn16	Signed16

#ifndef FILE
#include <stdio.h>
#endif

#ifndef assert
#ifdef DEBUG
#define assert(x) (!(x) ? fprintf(stderr,"Assertion failed \"x\" [file %s, line %d]\n", __FILE__, __LINE__),fflush(stderr),abort() : 0)
#else
#define assert(x)
#endif /* DEBUG */
#endif /* assert */

typedef unsigned short	Uns16;
typedef short		Sgn16;
typedef unsigned	Uns32;

/*
 * The enumerator for the different types of pools (and pages).
 */
enum pool_type {
    hpa_allocation,
    pom_allocation,
    pa_allocation,
    tail_allocation
};

/*
 * The page descriptor for a Homogeneous Pages Allocation page.
 * The machine page described by this descriptor will contain
 * objects of a predetermined size.  The current_block field will
 * point to the free list of the given page which will be a singly
 * linked list of all of the free blocks on that page.
 */
typedef struct hpa_page_desc {
    struct pool_desc		*pool_descriptor;	/* back-ptr to pool */
    Uns16			next_page;		/* next page in pool */
    Uns16			last_page;		/* last page in pool */
    struct hpa_block		*current_block;		/* ptr to free blocks */
    Uns32			num_free_blocks;	/* # of free blocks */
} HPA_Page;

/*
 * The page descriptor for a Page Oriented Malloc page.  The
 * machine page described by this descriptor will contain a
 * list of free blocks of varying sizes.  The current_block
 * is the block currently being used for allocation.  If this
 * block is unable to support a request, the list of blocks
 * is scanned to see if any other blocks on the page can
 * support the request.  This list of free blocks is a circular
 * bi-directional linked list whose "head" is the current block.
 * The current_free field contains the size of the current block.
 * It is the size of the biggest block only if allocations are not
 * being performed off of this page, otherwise it may be out of date.
 */
typedef struct pom_page_desc {
    struct pool_desc		*pool_descriptor;	/* back-ptr to pool */
    Uns16			next_page;		/* next page in pool */
    Uns16			last_page;		/* last page in pool */
    struct pom_block		*current_block;		/* biggest free block */
    Uns16			current_free;		/* size of that block */
    Uns16			total_free;		/* total free space */
} POM_Page;

/*
 * The page descriptor for a Page Allocator page.  The machine page
 * described by this descriptor has been allocated to one of the
 * HPA or POM schemes, a huge generic request, or is on the list
 * of free pages to be used for any of those purposes.  The pointer
 * to the pool descriptor points to either the one PA free pool or
 * the one PA allocated pool.  The PA free pool is the list of all
 * of the unassigned pages.  The PA allocated pool is merely a
 * pool_descriptor value so that allocated PA pages can be detected.
 * A linked list of them is not maintained (yet? - REMIND?)
 */
typedef struct pa_page_desc {
    struct pool_desc		*pool_descriptor;	/* back-ptr to pool */
    Uns16			next_page;		/* next set of pages */
    Uns16			last_page;		/* prev set of pages */
    Uns32			pages_in_set;		/* pages in this set */
    Uns32			tail_wastage;		/* left on last page */
} PA_Page;

/*
 * The page descriptor for any kind of page.  This structure contains
 * the data common to all three page types.
 */
typedef struct gen_page_desc {
    struct pool_desc		*pool_descriptor;	/* back-ptr to pool */
    Uns16			next_page;		/* next set of pages */
    Uns16			last_page;		/* prev set of pages */
    Uns32			pad1;
    Uns32			pad2;
} Gen_Page;

/*
 * The union of all of the page descriptor types.
 */
typedef union {
    HPA_Page	hpa;
    POM_Page	pom;
    PA_Page	pa;
    Gen_Page	gen;
} Page;

/*
 * The pool descriptor for any of the three schemes.  This structure
 * points to the descriptor of the "current" page of all of the pages
 * assigned to this scheme.  This is the page from which we are
 * currently trying to allocate all data.  If the allocation from this
 * page fails, then we search (linearly) for the next page to allocate
 * from.  Until that search occurs, the allocations should go quickly.
 * The scheme_data is only used by HPA currently (to store the size of
 * the objects on its pages.)
 */
typedef struct pool_desc {
    enum pool_type	type:8;			/* allocation scheme type */
    unsigned char	desclen;		/* length of description */
    Uns16		scheme_data;		/* ?? - (size for HPA) */
    Page		*current_page;		/* current "hot" alloc page */
    char		*description;		/* string description of pool */
} Pool;

/*
 * This is the structure describing the data stored in each
 * block on a Homogeneous Pages Allocation free list.
 */
typedef struct hpa_block {
    struct hpa_block	*nextfreeblock;
} HPA_Block;

/*
 * This is the structure describing the data stored in each
 * Page Oriented Malloc block.  The prevblocksize is marked
 * when the block is free, since it is only used to coalesce
 * the block at the time of its freeing.  It is zero for the
 * first block on the page.
 */
typedef struct pom_block {
    Uns16	thisblocksize;		/* size of this block */
    Uns16	prevblocksize;		/* size of previous block */
    struct {
	Sgn16	nextfreeoffset;		/* offset to next block in free chain */
	Sgn16	lastfreeoffset;		/* offset to last block in free chain */
    } data;
} POM_Block;

/*
 * Constant values used by the palloc mechanism.
 *
 * unsigned	LOG_PAGE_SIZE
 *	the number of bits in (log base 2 of) the size of a palloc page.
 *
 * unsigned	PAGE_SIZE
 *	the size of a palloc page.
 *
 * unsigned	MAX_VM_ADDRESS
 *	the maximum numerical address supported by the palloc mechanism.
 *
 * unsigned	NUM_VM_PAGES
 *	the number of virtual pages the palloc mechanism deals with.
 */
#define LOG_PAGE_SIZE	13
#define PAGE_SIZE	(1<<LOG_PAGE_SIZE)
#define MAX_VM_ADDRESS	(1<<26)
#define NUM_VM_PAGES	(MAX_VM_ADDRESS/PAGE_SIZE)

/*
 * Generic block and page descriptor manipulation macros.
 *
 * unsigned	roundup(unsigned s, m)
 *	round size, s, up to next multiple of m
 *
 * Pool		*bucket_slot(unsigned s)
 *	return the generic HPA pool for input size s (NULL for none).
 *
 * unsigned	btoi(void *b)
 *	return the index of the page which block b is on.
 *
 * Page		*btod(void *b)
 *	return the page descriptor for the page which block b is on.
 *
 * void		*dtop(Page *d)
 *	return the start address of the page described by page descriptor d.
 *
 * void		*btop(void *b)
 *	return the start address of the page which block, b, is on.
 *
 * bool		samepage(void	*b1, *b2)
 *	test whether the two blocks are on the same page.
 *
 * POM_Block	*nextblk(void	*b, int	s)
 *	return the block at offset s from block b.
 *
 * POM_Block	*prevblk(void	*b, int s)
 *	return the block at offset s backwards from block b.
 *
 * void		*new_page()
 *	return a pointer to a brand new page.
 */
#define roundup(s,m)	(((s)+((m)-1))&(~((m)-1)))
#define bucket_slot(s)	(((s) > 24) ? NULL : &generic_hpa_bucket[((s)-1) / 4])
#define btoi(b)		(((Uns32)(b))>>LOG_PAGE_SIZE)
#define btod(b)		(&page_table[btoi(b)])
#define dtoi(d)		((int)(((Page *)d)-page_table))
#define dtop(d)		((void *)(dtoi(d)<<LOG_PAGE_SIZE))
#define btop(b)		((void *)(((int)(b))&(~(PAGE_SIZE - 1))))
#define samepage(b1,b2)	(((((int)b1) ^ ((int)b2)) & (~(PAGE_SIZE-1))) == 0)
#define nextblk(b,s)	((POM_Block *)(((char *)(b))+(s)))
#define prevblk(b,s)	((POM_Block *)(((char *)(b))-(s)))
#define new_page()	page_alloc((Uns32)1)

/*
 * HPA block manipulation macros.
 *
 * HPA_Block	*hpa_link(HPA_Block	*b)
 *	return the HPA link field of the block b (for get or set).
 */
#define hpa_link(b)	((b)->nextfreeblock)

/*
 * POM block manipulation macros.
 *
 * unsigned	POM_OVERHEAD
 *	the overhead of a POM block (data stored for POM's use).
 *
 * unsigned	POM_MARK
 *	the marking value to be used to mark a POM block as free.
 *
 * unsigned	pom_size(POM_Block	*b)
 *	return the POM size field of the block b (for get or set).
 *
 * int		pom_next(POM_Block	*b)
 *	return the POM next free block field of the block b (for get or set).
 *
 * int		pom_last(POM_Block	*b)
 *	return the POM last free block field of the block b (for get or set).
 *
 * void		*pom_data(POM_Block	*b)
 *	return the address of the user data portion of block b.
 *
 * POM_Block	*pom_block(void		*p)
 *	return the POM block whose user data portion is b.
 *
 * unsigned	set_prev(POM_Block	*b, unsigned	v)
 *	set the value of the prev size field of block b to v.
 *
 * unsigned	get_prev(POM_Block	*b)
 *	return the value of the prev size field of block b (for get only).
 *
 * unsigned	markalloc(POM_Block	*b)
 *	mark block b as allocated.
 *
 * unsigned	markfree(POM_Block	*b)
 *	mark block b as free.
 *
 * bool		isfree(POM_Block	*b)
 *	test if block b is a free block.
 *
 * unsigned	round_pom_size(unsigned	s)
 *	round user requested size s to the size of a POM block which
 *	contains at least that much space in the user portion.
 */
#define POM_OVERHEAD	((unsigned)&(((POM_Block *)0)->data))
#define POM_MARK	0x8000
#define pom_size(b)	((b)->thisblocksize)
#define pom_next(b)	((b)->data.nextfreeoffset)
#define pom_last(b)	((b)->data.lastfreeoffset)
#define pom_data(b)	((void *)&((b)->data))
#define pom_block(p)	((POM_Block *)(((char *)(p))-POM_OVERHEAD))
#define set_prev(b,v)	((b)->prevblocksize = (isfree(b) | (v)))
#define get_prev(b)	((b)->prevblocksize & ~POM_MARK)
#define markalloc(b)	((b)->prevblocksize &= ~POM_MARK)
#define markfree(b)	((b)->prevblocksize |= POM_MARK)
#define isfree(b)	((b)->prevblocksize & POM_MARK)
#define round_pom_size(s)	(((s) < POM_OVERHEAD) ? sizeof(POM_Block) : \
				    roundup(s + POM_OVERHEAD,POM_OVERHEAD))

extern Pool		generic_pom_pool;
extern Pool		pom_cess_pool;
extern Pool		pa_free_pool;
extern Pool		pa_alloc_pool;
extern Pool		generic_hpa_bucket[];
extern Page		*page_table;

/*
 * The following functions are the lowest-level page-based
 * allocation functions.  They only deal with pages and PA pools.
 */
void	*page_alloc();		/* Allocate a number of pages */
void	*page_realloc();	/* Re-size a set of pages */
void	page_free();		/* Free a number of pages */

/*
 * The following functions are the second-level allocation
 * functions.  This should be the lowest level of allocation
 * function that the programmer sees, however, some allocation
 * needs may be best satisfied by using the page functions
 * directly.
 */
void	*palloc();		/* Allocate a block from HPA, POM or PA */
void	*prealloc();		/* Re-size a block from (HPA), POM, or PA */
void	pfree();		/* Free a block to HPA, POM, or PA */
Pool	*new_pool();		/* Create a new HPA or POM pool */
void	discard_pool();		/* Discard a POM pool, save its pages. */
Pool	*pset_default_pool();	/* Set the default pool used by palloc */
void	name_pool();		/* Set the name for a pool */
void	palloc_status();	/* Return memory usage statistics */

#define pool_of(ptr)		((btod(ptr)->pa.pool_descriptor->type \
				  != pom_allocation) ? ((Pool *)NULL) \
				 : btod(ptr)->pa.pool_descriptor)

#define NUMBERS		0	/* Dump pages by printing numbers. */
#define BARGRAPH	1	/* Dump pages by graphing percents. */
#define PICTURE		2	/* Dump pages by picturing used blocks. */
#define POOLSUMMARY	3	/* Dump summary of in-core pages in pools */

#undef Sgn16

#define PALLOC

#endif /* PALLOC */