path: root/src/include/btmem.h

/*-
 * Copyright (c) 2014-2015 MongoDB, Inc.
 * Copyright (c) 2008-2014 WiredTiger, Inc.
 *	All rights reserved.
 *
 * See the file LICENSE for redistribution information.
 */

/*
 * WT_PAGE_HEADER --
 *	Blocks have a common header, a WT_PAGE_HEADER structure followed by a
 * block-manager specific structure.
 */
struct __wt_page_header {
	/*
	 * The record number of the first record of the page is stored on disk
	 * so we can figure out where the column-store leaf page fits into the
	 * key space during salvage.
	 */
	uint64_t recno;			/* 00-07: column-store starting recno */

	/*
	 * We maintain page write-generations in the non-transactional case
	 * as that's how salvage can determine the most recent page between
	 * pages overlapping the same key range.
	 */
	uint64_t write_gen;		/* 08-15: write generation */

	/*
	 * The page's in-memory size isn't rounded or aligned, it's the actual
	 * number of bytes the disk-image consumes when instantiated in memory.
	 */
	uint32_t mem_size;		/* 16-19: in-memory page size */

	union {
		uint32_t entries;	/* 20-23: number of cells on page */
		uint32_t datalen;	/* 20-23: overflow data length */
	} u;

	uint8_t type;			/* 24: page type */

#define	WT_PAGE_COMPRESSED	0x01	/* Page is compressed on disk */
#define	WT_PAGE_EMPTY_V_ALL	0x02	/* Page has all zero-length values */
#define	WT_PAGE_EMPTY_V_NONE	0x04	/* Page has no zero-length values */
	uint8_t flags;			/* 25: flags */

	/*
	 * End the structure with 2 bytes of padding: it wastes space, but it
	 * leaves the structure 32-bit aligned and having a few bytes to play
	 * with in the future can't hurt.
	 */
	uint8_t unused[2];		/* 26-27: unused padding */
};
/*
 * WT_PAGE_HEADER_SIZE is the number of bytes we allocate for the structure: if
 * the compiler inserts padding it will break the world.
 */
#define	WT_PAGE_HEADER_SIZE		28

/*
 * The block-manager specific information immediately follows the WT_PAGE_HEADER
 * structure.
 */
#define	WT_BLOCK_HEADER_REF(dsk)					\
	((void *)((uint8_t *)(dsk) + WT_PAGE_HEADER_SIZE))

/*
 * WT_PAGE_HEADER_BYTE --
 * WT_PAGE_HEADER_BYTE_SIZE --
 *	The first usable data byte on the block (past the combined headers).
 */
#define	WT_PAGE_HEADER_BYTE_SIZE(btree)					\
	((u_int)(WT_PAGE_HEADER_SIZE + (btree)->block_header))
#define	WT_PAGE_HEADER_BYTE(btree, dsk)					\
	((void *)((uint8_t *)(dsk) + WT_PAGE_HEADER_BYTE_SIZE(btree)))

/*
 * WT_ADDR --
 *	An in-memory structure to hold a block's location.
 */
struct __wt_addr {
	uint8_t *addr;			/* Block-manager's cookie */
	uint8_t  size;			/* Block-manager's cookie length */

#define	WT_ADDR_INT	1		/* Internal page */
#define	WT_ADDR_LEAF	2		/* Leaf page */
#define	WT_ADDR_LEAF_NO	3		/* Leaf page, no overflow */
	uint8_t  type;

	/*
	 * If an address is both as an address for the previous and the current
	 * multi-block reconciliations, that is, a block we're writing matches
	 * the block written the last time, it will appear in both the current
	 * boundary points as well as the page modification's list of previous
	 * blocks.  The reuse flag is how we know that's happening so the block
	 * is treated correctly (not free'd on error, for example).
	 */
	uint8_t	 reuse;
};

/*
 * Overflow tracking for reuse: When a page is reconciled, we write new K/V
 * overflow items.  If pages are reconciled multiple times, we need to know
 * if we've already written a particular overflow record (so we don't write
 * it again), as well as if we've modified an overflow record previously
 * written (in which case we want to write a new record and discard blocks
 * used by the previously written record).  Track overflow records written
 * for the page, storing the values in a skiplist with the record's value as
 * the "key".
 */
struct __wt_ovfl_reuse {
	uint32_t value_offset;		/* Overflow value offset */
	uint32_t value_size;		/* Overflow value size */
	uint8_t  addr_offset;		/* Overflow addr offset */
	uint8_t  addr_size;		/* Overflow addr size */

	/*
	 * On each page reconciliation, we clear the entry's in-use flag, and
	 * reset it as the overflow record is re-used.  After reconciliation
	 * completes, unused skiplist entries are discarded, along with their
	 * underlying blocks.
	 *
	 * On each page reconciliation, set the just-added flag for each new
	 * skiplist entry; if reconciliation fails for any reason, discard the
	 * newly added skiplist entries, along with their underlying blocks.
	 */
#define	WT_OVFL_REUSE_INUSE		0x01
#define	WT_OVFL_REUSE_JUST_ADDED	0x02
	uint8_t	 flags;

	/*
	 * The untyped address immediately follows the WT_OVFL_REUSE structure,
	 * the untyped value immediately follows the address.
	 */
#define	WT_OVFL_REUSE_ADDR(p)						\
	((void *)((uint8_t *)(p) + (p)->addr_offset))
#define	WT_OVFL_REUSE_VALUE(p)						\
	((void *)((uint8_t *)(p) + (p)->value_offset))

	WT_OVFL_REUSE *next[0];		/* Forward-linked skip list */
};

/*
 * Overflow tracking for cached values: When a page is reconciled, we write new
 * K/V overflow items, and discard previous underlying blocks.  If there's a
 * transaction in the system that needs to read the previous value, we have to
 * cache the old value until no running transaction needs it.
 */
struct __wt_ovfl_txnc {
	uint64_t current;		/* Maximum transaction ID at store */

	uint32_t value_offset;		/* Overflow value offset */
	uint32_t value_size;		/* Overflow value size */
	uint8_t  addr_offset;		/* Overflow addr offset */
	uint8_t  addr_size;		/* Overflow addr size */

	/*
	 * The untyped address immediately follows the WT_OVFL_TXNC
	 * structure, the untyped value immediately follows the address.
	 */
#define	WT_OVFL_TXNC_ADDR(p)						\
	((void *)((uint8_t *)(p) + (p)->addr_offset))
#define	WT_OVFL_TXNC_VALUE(p)						\
	((void *)((uint8_t *)(p) + (p)->value_offset))

	WT_OVFL_TXNC *next[0];		/* Forward-linked skip list */
};

/*
 * WT_PAGE_MODIFY --
 *	When a page is modified, there's additional information to maintain.
 */
struct __wt_page_modify {
	/*
	 * Track the highest transaction ID at which the page was written to
	 * disk.  This can be used to avoid trying to write the page multiple
	 * times if a snapshot is keeping old versions pinned (e.g., in a
	 * checkpoint).
	 */
	uint64_t disk_snap_min;

	/* The first unwritten transaction ID (approximate). */
	uint64_t first_dirty_txn;

	/* In-memory split transaction ID. */
	uint64_t inmem_split_txn;

	/* Avoid checking for obsolete updates during checkpoints. */
	uint64_t obsolete_check_txn;

	/* The largest transaction ID seen on the page by reconciliation. */
	uint64_t rec_max_txn;

	/* The largest update transaction ID (approximate). */
	uint64_t update_txn;

	/* Dirty bytes added to the cache. */
	size_t bytes_dirty;

	/*
	 * When pages are reconciled, the result is one or more replacement
	 * blocks.  A replacement block can be in one of two states: it was
	 * written to disk, and so we have a block address, or it contained
	 * unresolved modifications and we have a disk image for it with a
	 * list of those unresolved modifications.  The former is the common
	 * case: we only build lists of unresolved modifications when we're
	 * evicting a page, and we only expect to see unresolved modifications
	 * on a page being evicted in the case of a hot page that's too large
	 * to keep in memory as it is.  In other words, checkpoints will skip
	 * unresolved modifications, and will write the blocks rather than
	 * build lists of unresolved modifications.
	 *
	 * Ugly union/struct layout to conserve memory, we never have both
	 * a replace address and multiple replacement blocks.
	 */
	union {
	WT_ADDR	 replace;		/* Single, written replacement block */
#define	mod_replace	u1.replace

	struct {			/* Multiple replacement blocks */
	struct __wt_multi {
		/*
		 * Block's key: either a column-store record number or a
		 * row-store variable length byte string.
		 */
		union {
			uint64_t recno;
			WT_IKEY *ikey;
		} key;

		/*
		 * Eviction, but block wasn't written: unresolved updates and
		 * associated disk image.
		 *
		 * Skipped updates are either a WT_INSERT, or a row-store leaf
		 * page entry.
		 */
		struct __wt_upd_skipped {
			WT_INSERT *ins;
			WT_ROW	  *rip;
		} *skip;
		uint32_t skip_entries;
		void	*skip_dsk;

		/*
		 * Block was written: address, size and checksum.
		 * On subsequent reconciliations of this page, we avoid writing
		 * the block if it's unchanged by comparing size and checksum;
		 * the reuse flag is set when the block is unchanged and we're
		 * reusing a previous address.
		 */
		WT_ADDR	 addr;
		uint32_t size;
		uint32_t cksum;
	} *multi;
	uint32_t multi_entries;		/* Multiple blocks element count */
	} m;
#define	mod_multi		u1.m.multi
#define	mod_multi_entries	u1.m.multi_entries
	} u1;

	/*
	 * Internal pages need to be able to chain root-page splits and have a
	 * special transactional eviction requirement.  Column-store leaf pages
	 * need update and append lists.
	 *
	 * Ugly union/struct layout to conserve memory, a page is either a leaf
	 * page or an internal page.
	 */
	union {
	struct {
		/*
		 * When a root page splits, we create a new page and write it;
		 * the new page can also split and so on, and we continue this
		 * process until we write a single replacement root page.  We
		 * use the root split field to track the list of created pages
		 * so they can be discarded when no longer needed.
		 */
		WT_PAGE *root_split;	/* Linked list of root split pages */

		/*
		 * When we deepen the tree, newly created internal pages cannot
		 * be evicted until all threads have exited the original page
		 * index structure.  We set a transaction value during the split
		 * that's checked during eviction.
		 */
		uint64_t split_txn;	/* Split eviction transaction value */
	} intl;
#define	mod_root_split		u2.intl.root_split
#define	mod_split_txn		u2.intl.split_txn
	struct {
		/*
		 * Appended items to column-stores: there is only a single one
		 * of these per column-store tree.
		 */
		WT_INSERT_HEAD **append;

		/*
		 * Updated items in column-stores: variable-length RLE entries
		 * can expand to multiple entries which requires some kind of
		 * list we can expand on demand.  Updated items in fixed-length
		 * files could be done based on an WT_UPDATE array as in
		 * row-stores, but there can be a very large number of bits on
		 * a single page, and the cost of the WT_UPDATE array would be
		 * huge.
		 */
		WT_INSERT_HEAD **update;
	} leaf;
#define	mod_append		u2.leaf.append
#define	mod_update		u2.leaf.update
	} u2;

	/*
	 * Overflow record tracking for reconciliation.  We assume overflow
	 * records are relatively rare, so we don't allocate the structures
	 * to track them until we actually see them in the data.
	 */
	struct __wt_ovfl_track {
		/*
		 * Overflow key/value address/byte-string pairs we potentially
		 * reuse each time we reconcile the page.
		 */
		WT_OVFL_REUSE	*ovfl_reuse[WT_SKIP_MAXDEPTH];

		/*
		 * Overflow value address/byte-string pairs cached until no
		 * running transaction will possibly read them.
		 */
		WT_OVFL_TXNC	*ovfl_txnc[WT_SKIP_MAXDEPTH];

		/*
		 * Overflow key/value addresses to be discarded from the block
		 * manager after reconciliation completes successfully.
		 */
		WT_CELL **discard;
		size_t	  discard_entries;
		size_t	  discard_allocated;
	} *ovfl_track;

	/*
	 * The write generation is incremented when a page is modified, a page
	 * is clean if the write generation is 0.
	 *
	 * !!!
	 * 4B values are probably larger than required, but I'm more confident
	 * 4B types will always be backed by atomic writes to memory.
	 */
	uint32_t write_gen;

#define	WT_PAGE_LOCK(s, p)						\
	__wt_spin_lock((s), &S2C(s)->page_lock[(p)->modify->page_lock])
#define	WT_PAGE_UNLOCK(s, p)						\
	__wt_spin_unlock((s), &S2C(s)->page_lock[(p)->modify->page_lock])
	uint8_t page_lock;		/* Page's spinlock */

#define	WT_PM_REC_EMPTY		0x01	/* Reconciliation: no replacement */
#define	WT_PM_REC_MULTIBLOCK	0x02	/* Reconciliation: multiple blocks */
#define	WT_PM_REC_REPLACE	0x04	/* Reconciliation: single block */
#define	WT_PM_REC_REWRITE	0x08	/* Reconciliation: rewrite in place */
#define	WT_PM_REC_MASK							\
	(WT_PM_REC_EMPTY | WT_PM_REC_MULTIBLOCK |			\
	 WT_PM_REC_REPLACE | WT_PM_REC_REWRITE)
	uint8_t flags;			/* Page flags */
};

/*
 * WT_PAGE --
 * The WT_PAGE structure describes the in-memory page information.
 */
struct __wt_page {
	/* Per page-type information. */
	union {
		/*
		 * Internal pages (both column- and row-store).
		 *
		 * The page record number is only used by column-store, but it
		 * makes some things simpler and it doesn't cost us any memory,
		 * other structures in this union are still as large.
		 *
		 * In-memory internal pages have an array of pointers to child
		 * structures, maintained in collated order.  When a page is
		 * read into memory, the initial list of children is stored in
		 * the "orig_index" field, and it and the collated order are
		 * the same.  After a page splits, the collated order and the
		 * original order will differ.
		 *
		 * Multiple threads of control may be searching the in-memory
		 * internal page and a child page of the internal page may
		 * cause a split at any time.  When a page splits, a new array
		 * is allocated and atomically swapped into place.  Threads in
		 * the old array continue without interruption (the old array is
		 * still valid), but have to avoid racing.  No barrier is needed
		 * because the array reference is updated atomically, but code
		 * reading the fields multiple times would be a very bad idea.
		 * Specifically, do not do this:
		 *	WT_REF **refp = page->u.intl__index->index;
		 *	uint32_t entries = page->u.intl__index->entries;
		 *
		 * The field is declared volatile (so the compiler knows not to
		 * read it multiple times), and we obscure the field name and
		 * use a copy macro in all references to the field (so the code
		 * doesn't read it multiple times).
		 */
		struct {
			uint64_t recno;		/* Starting recno */
			WT_REF	*parent_ref;	/* Parent reference */

			struct __wt_page_index {
				uint32_t entries;
				WT_REF	**index;
			} * volatile __index;	/* Collated children */
		} intl;
#undef	pg_intl_recno
#define	pg_intl_recno			u.intl.recno
#define	pg_intl_parent_ref		u.intl.parent_ref

	/*
	 * Macros to copy/set the index because the name is obscured to ensure
	 * the field isn't read multiple times.
	 */
#define	WT_INTL_INDEX_COPY(page)	((page)->u.intl.__index)
#define	WT_INTL_INDEX_SET(page, v) do {					\
	WT_WRITE_BARRIER();						\
	((page)->u.intl.__index) = (v);					\
} while (0)

	/*
	 * Macro to walk the list of references in an internal page.
	 * Two flavors: by default, check that we have a split_gen, but
	 * provide a "SAFE" version for code that can safely read the
	 * page index without a split_gen.
	 */
#define	WT_INTL_FOREACH_BEGIN_SAFE(session, page, ref) do {		\
	WT_PAGE_INDEX *__pindex;					\
	WT_REF **__refp;						\
	uint32_t __entries;						\
	for (__pindex = WT_INTL_INDEX_COPY(page),			\
	    __refp = __pindex->index,					\
	    __entries = __pindex->entries; __entries > 0; --__entries) {\
		(ref) = *__refp++;
#define	WT_INTL_FOREACH_BEGIN(session, page, ref)			\
	WT_ASSERT(session, session->split_gen != 0);			\
	WT_INTL_FOREACH_BEGIN_SAFE(session, page, ref)
#define	WT_INTL_FOREACH_END						\
	}								\
} while (0)

		/* Row-store leaf page. */
		struct {
			/*
			 * The column-store leaf page modification structures
			 * live in the WT_PAGE_MODIFY structure to keep the
			 * WT_PAGE structure as small as possible for read-only
			 * pages.  For consistency, we could move the row-store
			 * modification structures into WT_PAGE_MODIFY too, but
			 * that doesn't shrink WT_PAGE any further and it would
			 * require really ugly naming inside of WT_PAGE_MODIFY
			 * to avoid growing that structure.
			 */
			WT_INSERT_HEAD	**ins;	/* Inserts */
			WT_UPDATE	**upd;	/* Updates */

			WT_ROW *d;		/* Key/value pairs */
			uint32_t entries;	/* Entries */
		} row;
#undef	pg_row_d
#define	pg_row_d	u.row.d
#undef	pg_row_ins
#define	pg_row_ins	u.row.ins
#undef	pg_row_upd
#define	pg_row_upd	u.row.upd
#define	pg_row_entries	u.row.entries
#define	pg_row_entries	u.row.entries

		/* Fixed-length column-store leaf page. */
		struct {
			uint64_t recno;		/* Starting recno */

			uint8_t	*bitf;		/* Values */
			uint32_t entries;	/* Entries */
		} col_fix;
#undef	pg_fix_recno
#define	pg_fix_recno	u.col_fix.recno
#undef	pg_fix_bitf
#define	pg_fix_bitf	u.col_fix.bitf
#undef	pg_fix_entries
#define	pg_fix_entries	u.col_fix.entries

		/* Variable-length column-store leaf page. */
		struct {
			uint64_t recno;		/* Starting recno */

			WT_COL *d;		/* Values */

			/*
			 * Variable-length column-store files maintain a list of
			 * RLE entries on the page so it's unnecessary to walk
			 * the page counting records to find a specific entry.
			 */
			WT_COL_RLE *repeats;	/* RLE array for lookups */
			uint32_t    nrepeats;	/* Number of repeat slots */

			uint32_t    entries;	/* Entries */
		} col_var;
#undef	pg_var_recno
#define	pg_var_recno	u.col_var.recno
#undef	pg_var_d
#define	pg_var_d	u.col_var.d
#undef	pg_var_repeats
#define	pg_var_repeats	u.col_var.repeats
#undef	pg_var_nrepeats
#define	pg_var_nrepeats	u.col_var.nrepeats
#undef	pg_var_entries
#define	pg_var_entries	u.col_var.entries
	} u;

	/*
	 * The page's type and flags are positioned at the end of the WT_PAGE
	 * union, it reduces cache misses in the row-store search function.
	 */
#define	WT_PAGE_IS_INTERNAL(page)					\
	((page)->type == WT_PAGE_COL_INT || (page)->type == WT_PAGE_ROW_INT)
#define	WT_PAGE_INVALID		0	/* Invalid page */
#define	WT_PAGE_BLOCK_MANAGER	1	/* Block-manager page */
#define	WT_PAGE_COL_FIX		2	/* Col-store fixed-len leaf */
#define	WT_PAGE_COL_INT		3	/* Col-store internal page */
#define	WT_PAGE_COL_VAR		4	/* Col-store var-length leaf page */
#define	WT_PAGE_OVFL		5	/* Overflow page */
#define	WT_PAGE_ROW_INT		6	/* Row-store internal page */
#define	WT_PAGE_ROW_LEAF	7	/* Row-store leaf page */
	uint8_t type;			/* Page type */

#define	WT_PAGE_BUILD_KEYS	0x01	/* Keys have been built in memory */
#define	WT_PAGE_DISK_ALLOC	0x02	/* Disk image in allocated memory */
#define	WT_PAGE_DISK_MAPPED	0x04	/* Disk image in mapped memory */
#define	WT_PAGE_EVICT_LRU	0x08	/* Page is on the LRU queue */
#define	WT_PAGE_SCANNING	0x10	/* Obsolete updates are being scanned */
#define	WT_PAGE_SPLIT_INSERT	0x20	/* A leaf page was split for append */
#define	WT_PAGE_SPLITTING	0x40	/* An internal page is growing */
	uint8_t flags_atomic;		/* Atomic flags, use F_*_ATOMIC */

	/*
	 * The page's read generation acts as an LRU value for each page in the
	 * tree; it is used by the eviction server thread to select pages to be
	 * discarded from the in-memory tree.
	 *
	 * The read generation is a 64-bit value, if incremented frequently, a
	 * 32-bit value could overflow.
	 *
	 * The read generation is a piece of shared memory potentially read
	 * by many threads.  We don't want to update page read generations for
	 * in-cache workloads and suffer the cache misses, so we don't simply
	 * increment the read generation value on every access.  Instead, the
	 * read generation is incremented by the eviction server each time it
	 * becomes active.  To avoid incrementing a page's read generation too
	 * frequently, it is set to a future point.
	 */
#define	WT_READGEN_NOTSET	0
#define	WT_READGEN_OLDEST	1
#define	WT_READGEN_STEP		100
	uint64_t read_gen;

	size_t memory_footprint;	/* Memory attached to the page */

	/* Page's on-disk representation: NULL for pages created in memory. */
	const WT_PAGE_HEADER *dsk;

	/* If/when the page is modified, we need lots more information. */
	WT_PAGE_MODIFY *modify;
};

/*
 * WT_PAGE_DISK_OFFSET, WT_PAGE_REF_OFFSET --
 *	Return the offset/pointer of a pointer/offset in a page disk image.
 */
#define	WT_PAGE_DISK_OFFSET(page, p)					\
	WT_PTRDIFF32(p, (page)->dsk)
#define	WT_PAGE_REF_OFFSET(page, o)					\
	((void *)((uint8_t *)((page)->dsk) + (o)))

/*
 * Page state.
 *
 * Synchronization is based on the WT_REF->state field, which has a number of
 * possible states:
 *
 * WT_REF_DISK:
 *	The initial setting before a page is brought into memory, and set as a
 *	result of page eviction; the page is on disk, and must be read into
 *	memory before use.  WT_REF_DISK has a value of 0 (the default state
 *	after allocating cleared memory).
 *
 * WT_REF_DELETED:
 *	The page is on disk, but has been deleted from the tree; we can delete
 *	row-store leaf pages without reading them if they don't reference
 *	overflow items.
 *
 * WT_REF_LOCKED:
 *	Locked for exclusive access.  In eviction, this page or a parent has
 *	been selected for eviction; once hazard pointers are checked, the page
 *	will be evicted.  When reading a page that was previously deleted, it
 *	is locked until the page is in memory with records marked deleted.  The
 *	thread that set the page to WT_REF_LOCKED has exclusive access, no
 *	other thread may use the WT_REF until the state is changed.
 *
 * WT_REF_MEM:
 *	Set by a reading thread once the page has been read from disk; the page
 *	is in the cache and the page reference is OK.
 *
 * WT_REF_READING:
 *	Set by a reading thread before reading an ordinary page from disk;
 *	other readers of the page wait until the read completes.  Sync can
 *	safely skip over such pages: they are clean by definition.
 *
 * WT_REF_SPLIT:
 *	Set when the page is split; the WT_REF is dead and can no longer be
 *	used.
 *
 * The life cycle of a typical page goes like this: pages are read into memory
 * from disk and their state set to WT_REF_MEM.  When the page is selected for
 * eviction, the page state is set to WT_REF_LOCKED.  In all cases, evicting
 * threads reset the page's state when finished with the page: if eviction was
 * successful (a clean page was discarded, and a dirty page was written to disk
 * and then discarded), the page state is set to WT_REF_DISK; if eviction failed
 * because the page was busy, page state is reset to WT_REF_MEM.
 *
 * Readers check the state field and if it's WT_REF_MEM, they set a hazard
 * pointer to the page, flush memory and re-confirm the page state.  If the
 * page state is unchanged, the reader has a valid reference and can proceed.
 *
 * When an evicting thread wants to discard a page from the tree, it sets the
 * WT_REF_LOCKED state, flushes memory, then checks hazard pointers.  If a
 * hazard pointer is found, state is reset to WT_REF_MEM, restoring the page
 * to the readers.  If the evicting thread does not find a hazard pointer,
 * the page is evicted.
 */
typedef enum __wt_page_state {
	WT_REF_DISK=0,			/* Page is on disk */
	WT_REF_DELETED,			/* Page is on disk, but deleted */
	WT_REF_LOCKED,			/* Page locked for exclusive access */
	WT_REF_MEM,			/* Page is in cache and valid */
	WT_REF_READING,			/* Page being read */
	WT_REF_SPLIT			/* Page was split */
} WT_PAGE_STATE;

/*
 * WT_PAGE_DELETED --
 *	Related information for fast-delete, on-disk pages.
 */
struct __wt_page_deleted {
	uint64_t txnid;			/* Transaction ID */

	WT_UPDATE **update_list;	/* List of updates for abort */
};

/*
 * WT_REF --
 *	A single in-memory page and the state information used to determine if
 * it's OK to dereference the pointer to the page.
 */
struct __wt_ref {
	WT_PAGE *page;			/* Page */

	/*
	 * When the tree deepens as a result of a split, the home page value
	 * changes.  Don't cache it, we need to see that change when looking
	 * up our slot in the page's index structure.
	 */
	WT_PAGE * volatile home;	/* Reference page */
	uint32_t ref_hint;		/* Reference page index hint */

	volatile WT_PAGE_STATE state;	/* Page state */

	/*
	 * Address: on-page cell if read from backing block, off-page WT_ADDR
	 * if instantiated in-memory, or NULL if page created in-memory.
	 */
	void	*addr;

	/*
	 * The child page's key.  Do NOT change this union without reviewing
	 * __wt_ref_key.
	 */
	union {
		uint64_t recno;		/* Column-store: starting recno */
		void	*ikey;		/* Row-store: key */
	} key;

	WT_PAGE_DELETED	*page_del;	/* Deleted on-disk page information */
};
/*
 * WT_REF_SIZE is the expected structure size -- we verify the build to ensure
 * the compiler hasn't inserted padding which would break the world.
 */
#define	WT_REF_SIZE	48

/*
 * WT_ROW --
 * Each in-memory page row-store leaf page has an array of WT_ROW structures:
 * this is created from on-page data when a page is read from the file.  It's
 * sorted by key, fixed in size, and starts with a reference to on-page data.
 *
 * Multiple threads of control may be searching the in-memory row-store pages,
 * and the key may be instantiated at any time.  Code must be able to handle
 * both when the key has not been instantiated (the key field points into the
 * page's disk image), and when the key has been instantiated (the key field
 * points outside the page's disk image).  We don't need barriers because the
 * key is updated atomically, but code that reads the key field multiple times
 * is a very, very bad idea.  Specifically, do not do this:
 *
 *	key = rip->key;
 *	if (key_is_on_page(key)) {
 *		cell = rip->key;
 *	}
 *
 * The field is declared volatile (so the compiler knows it shouldn't read it
 * multiple times), and we obscure the field name and use a copy macro in all
 * references to the field (so the code doesn't read it multiple times), all
 * to make sure we don't introduce this bug (again).
 */
struct __wt_row {	/* On-page key, on-page cell, or off-page WT_IKEY */
	void * volatile __key;
};
#define	WT_ROW_KEY_COPY(rip)	((rip)->__key)
#define	WT_ROW_KEY_SET(rip, v)	((rip)->__key) = (void *)(v)

/*
 * WT_ROW_FOREACH --
 *	Walk the entries of an in-memory row-store leaf page.
 */
#define	WT_ROW_FOREACH(page, rip, i)					\
	for ((i) = (page)->pg_row_entries,				\
	    (rip) = (page)->pg_row_d; (i) > 0; ++(rip), --(i))
#define	WT_ROW_FOREACH_REVERSE(page, rip, i)				\
	for ((i) = (page)->pg_row_entries,				\
	    (rip) = (page)->pg_row_d + ((page)->pg_row_entries - 1);	\
	    (i) > 0; --(rip), --(i))

/*
 * WT_ROW_SLOT --
 *	Return the 0-based array offset based on a WT_ROW reference.
 */
#define	WT_ROW_SLOT(page, rip)						\
	((uint32_t)(((WT_ROW *)(rip)) - (page)->pg_row_d))

/*
 * WT_COL --
 * Each in-memory variable-length column-store leaf page has an array of WT_COL
 * structures: this is created from on-page data when a page is read from the
 * file.  It's fixed in size, and references data on the page.
 */
struct __wt_col {
	/*
	 * Variable-length column-store data references are page offsets, not
	 * pointers (we boldly re-invent short pointers).  The trade-off is 4B
	 * per K/V pair on a 64-bit machine vs. a single cycle for the addition
	 * of a base pointer.  The on-page data is a WT_CELL (same as row-store
	 * pages).
	 *
	 * If the value is 0, it's a single, deleted record.
	 *
	 * Obscure the field name, code shouldn't use WT_COL->__col_value, the
	 * public interface is WT_COL_PTR and WT_COL_PTR_SET.
	 */
	uint32_t __col_value;
};

/*
 * WT_COL_RLE --
 * In variable-length column store leaf pages, we build an array of entries
 * with RLE counts greater than 1 when reading the page.  We can do a binary
 * search in this array, then an offset calculation to find the cell.
 */
WT_PACKED_STRUCT_BEGIN(__wt_col_rle)
	uint64_t recno;			/* Record number of first repeat. */
	uint64_t rle;			/* Repeat count. */
	uint32_t indx;			/* Slot of entry in col_var.d */
WT_PACKED_STRUCT_END

/*
 * WT_COL_PTR, WT_COL_PTR_SET --
 *	Return/Set a pointer corresponding to the data offset. (If the item does
 * not exist on the page, return a NULL.)
 */
#define	WT_COL_PTR(page, cip)						\
	((cip)->__col_value == 0 ?					\
	    NULL : WT_PAGE_REF_OFFSET(page, (cip)->__col_value))
#define	WT_COL_PTR_SET(cip, value)					\
	(cip)->__col_value = (value)

/*
 * WT_COL_FOREACH --
 *	Walk the entries of variable-length column-store leaf page.
 */
#define	WT_COL_FOREACH(page, cip, i)					\
	for ((i) = (page)->pg_var_entries,				\
	    (cip) = (page)->pg_var_d; (i) > 0; ++(cip), --(i))

/*
 * WT_COL_SLOT --
 *	Return the 0-based array offset based on a WT_COL reference.
 */
#define	WT_COL_SLOT(page, cip)						\
	((uint32_t)(((WT_COL *)cip) - (page)->pg_var_d))

/*
 * WT_IKEY --
 * Instantiated key: row-store keys are usually prefix compressed and sometimes
 * Huffman encoded or overflow objects.  Normally, a row-store page in-memory
 * key points to the on-page WT_CELL, but in some cases, we instantiate the key
 * in memory, in which case the row-store page in-memory key points to a WT_IKEY
 * structure.
 */
struct __wt_ikey {
	uint32_t size;			/* Key length */

	/*
	 * If we no longer point to the key's on-page WT_CELL, we can't find its
	 * related value.  Save the offset of the key cell in the page.
	 *
	 * Row-store cell references are page offsets, not pointers (we boldly
	 * re-invent short pointers).  The trade-off is 4B per K/V pair on a
	 * 64-bit machine vs. a single cycle for the addition of a base pointer.
	 */
	uint32_t  cell_offset;

	/* The key bytes immediately follow the WT_IKEY structure. */
#define	WT_IKEY_DATA(ikey)						\
	((void *)((uint8_t *)(ikey) + sizeof(WT_IKEY)))
};

/*
 * WT_UPDATE --
 * Entries on leaf pages can be updated, either modified or deleted.  Updates
 * to entries referenced from the WT_ROW and WT_COL arrays are stored in the
 * page's WT_UPDATE array.  When the first element on a page is updated, the
 * WT_UPDATE array is allocated, with one slot for every existing element in
 * the page.  A slot points to a WT_UPDATE structure; if more than one update
 * is done for an entry, WT_UPDATE structures are formed into a forward-linked
 * list.
 */
WT_PACKED_STRUCT_BEGIN(__wt_update)
	uint64_t txnid;			/* update transaction */

	WT_UPDATE *next;		/* forward-linked list */

	/*
	 * We use the maximum size as an is-deleted flag, which means we can't
	 * store 4GB objects; I'd rather do that than increase the size of this
	 * structure for a flag bit.
	 */
#define	WT_UPDATE_DELETED_ISSET(upd)	((upd)->size == UINT32_MAX)
#define	WT_UPDATE_DELETED_SET(upd)	((upd)->size = UINT32_MAX)
	uint32_t size;			/* update length */

	/* The untyped value immediately follows the WT_UPDATE structure. */
#define	WT_UPDATE_DATA(upd)						\
	((void *)((uint8_t *)(upd) + sizeof(WT_UPDATE)))

	/*
	 * The memory size of an update: include some padding because this is
	 * such a common case that overhead of tiny allocations can swamp our
	 * cache overhead calculation.
	 */
#define	WT_UPDATE_MEMSIZE(upd)						\
	WT_ALIGN(sizeof(WT_UPDATE) +					\
	    (WT_UPDATE_DELETED_ISSET(upd) ? 0 : (upd)->size), 32)
};

/*
 * WT_INSERT --
 *
 * Row-store leaf pages support inserts of new K/V pairs.  When the first K/V
 * pair is inserted, the WT_INSERT_HEAD array is allocated, with one slot for
 * every existing element in the page, plus one additional slot.  A slot points
 * to a WT_INSERT_HEAD structure for the items which sort after the WT_ROW
 * element that references it and before the subsequent WT_ROW element; the
 * skiplist structure has a randomly chosen depth of next pointers in each
 * inserted node.
 *
 * The additional slot is because it's possible to insert items smaller than any
 * existing key on the page: for that reason, the first slot of the insert array
 * holds keys smaller than any other key on the page.
 *
 * In column-store variable-length run-length encoded pages, a single indx
 * entry may reference a large number of records, because there's a single
 * on-page entry representing many identical records.   (We don't expand those
 * entries when the page comes into memory, as that would require resources as
 * pages are moved to/from the cache, including read-only files.)  Instead, a
 * single indx entry represents all of the identical records originally found
 * on the page.
 *
 * Modifying (or deleting) run-length encoded column-store records is hard
 * because the page's entry no longer references a set of identical items.  We
 * handle this by "inserting" a new entry into the insert array, with its own
 * record number.  (This is the only case where it's possible to insert into a
 * column-store: only appends are allowed, as insert requires re-numbering
 * subsequent records.  Berkeley DB did support mutable records, but it won't
 * scale and it isn't useful enough to re-implement, IMNSHO.)
 */
struct __wt_insert {
	WT_UPDATE *upd;				/* value */

	union {
		uint64_t recno;			/* column-store record number */
		struct {
			uint32_t offset;	/* row-store key data start */
			uint32_t size;		/* row-store key data size */
		} key;
	} u;

#define	WT_INSERT_KEY_SIZE(ins) (((WT_INSERT *)ins)->u.key.size)
#define	WT_INSERT_KEY(ins)						\
	((void *)((uint8_t *)(ins) + ((WT_INSERT *)ins)->u.key.offset))
#define	WT_INSERT_RECNO(ins)	(((WT_INSERT *)ins)->u.recno)

	WT_INSERT *next[0];			/* forward-linked skip list */
};

/*
 * Skiplist helper macros.
 */
#define	WT_SKIP_FIRST(ins_head)						\
	(((ins_head) == NULL) ? NULL : ((WT_INSERT_HEAD *)ins_head)->head[0])
#define	WT_SKIP_LAST(ins_head)						\
	(((ins_head) == NULL) ? NULL : ((WT_INSERT_HEAD *)ins_head)->tail[0])
#define	WT_SKIP_NEXT(ins)  ((ins)->next[0])
#define	WT_SKIP_FOREACH(ins, ins_head)					\
	for ((ins) = WT_SKIP_FIRST(ins_head);				\
	    (ins) != NULL;						\
	    (ins) = WT_SKIP_NEXT(ins))

/*
 * Atomically allocate and swap a structure or array into place.
 */
#define	WT_PAGE_ALLOC_AND_SWAP(s, page, dest, v, count)	do {		\
	if (((v) = (dest)) == NULL) {					\
		WT_ERR(__wt_calloc_def(s, count, &(v)));		\
		if (WT_ATOMIC_CAS8(dest, NULL, v))			\
			__wt_cache_page_inmem_incr(			\
			    s, page, (count) * sizeof(*(v)));		\
		else							\
			__wt_free(s, v);				\
	}								\
} while (0)

/*
 * WT_INSERT_HEAD --
 * 	The head of a skiplist of WT_INSERT items.
 */
struct __wt_insert_head {
	WT_INSERT *head[WT_SKIP_MAXDEPTH];	/* first item on skiplists */
	WT_INSERT *tail[WT_SKIP_MAXDEPTH];	/* last item on skiplists */
};

/*
 * The row-store leaf page insert lists are arrays of pointers to structures,
 * and may not exist.  The following macros return an array entry if the array
 * of pointers and the specific structure exist, else NULL.
 */
#define	WT_ROW_INSERT_SLOT(page, slot)					\
	((page)->pg_row_ins == NULL ? NULL : (page)->pg_row_ins[slot])
#define	WT_ROW_INSERT(page, ip)						\
	WT_ROW_INSERT_SLOT(page, WT_ROW_SLOT(page, ip))
#define	WT_ROW_UPDATE(page, ip)						\
	((page)->pg_row_upd == NULL ?					\
	    NULL : (page)->pg_row_upd[WT_ROW_SLOT(page, ip)])
/*
 * WT_ROW_INSERT_SMALLEST references an additional slot past the end of the
 * the "one per WT_ROW slot" insert array.  That's because the insert array
 * requires an extra slot to hold keys that sort before any key found on the
 * original page.
 */
#define	WT_ROW_INSERT_SMALLEST(page)					\
	((page)->pg_row_ins == NULL ?					\
	    NULL : (page)->pg_row_ins[(page)->pg_row_entries])

/*
 * The column-store leaf page update lists are arrays of pointers to structures,
 * and may not exist.  The following macros return an array entry if the array
 * of pointers and the specific structure exist, else NULL.
 */
#define	WT_COL_UPDATE_SLOT(page, slot)					\
	((page)->modify == NULL || (page)->modify->mod_update == NULL ?	\
	    NULL : (page)->modify->mod_update[slot])
#define	WT_COL_UPDATE(page, ip)						\
	WT_COL_UPDATE_SLOT(page, WT_COL_SLOT(page, ip))

/*
 * WT_COL_UPDATE_SINGLE is a single WT_INSERT list, used for any fixed-length
 * column-store updates for a page.
 */
#define	WT_COL_UPDATE_SINGLE(page)					\
	WT_COL_UPDATE_SLOT(page, 0)

/*
 * WT_COL_APPEND is an WT_INSERT list, used for fixed- and variable-length
 * appends.
 */
#define	WT_COL_APPEND(page)						\
	((page)->modify != NULL && (page)->modify->mod_append != NULL ?	\
	    (page)->modify->mod_append[0] : NULL)

/* WT_FIX_FOREACH walks fixed-length bit-fields on a disk page. */
#define	WT_FIX_FOREACH(btree, dsk, v, i)				\
	for ((i) = 0,							\
	    (v) = (i) < (dsk)->u.entries ?				\
	    __bit_getv(							\
	    WT_PAGE_HEADER_BYTE(btree, dsk), 0, (btree)->bitcnt) : 0;	\
	    (i) < (dsk)->u.entries; ++(i),				\
	    (v) = __bit_getv(						\
	    WT_PAGE_HEADER_BYTE(btree, dsk), i, (btree)->bitcnt))

/*
 * Manage split generation numbers.  Splits walk the list of sessions to check
 * when it is safe to free structures that have been replaced.  We also check
 * that list periodically (e.g., when wrapping up a transaction) to free any
 * memory we can.
 *
 * Before a thread enters code that will examine page indexes (which are
 * swapped out by splits), it publishes a copy of the current split generation
 * into its session.  Don't assume that threads never re-enter this code: if we
 * already have a split generation, leave it alone.  If our caller is examining
 * an index, we don't want the oldest split generation to move forward and
 * potentially free it.
 *
 * Check that we haven't raced with a split_gen update after publishing: we
 * rely on the published value not being missed when scanning for the oldest
 * active split_gen.
 */
#define	WT_ENTER_PAGE_INDEX(session) do {				\
	uint64_t __prev_split_gen = (session)->split_gen;		\
	if (__prev_split_gen == 0)					\
		do {                                                    \
			WT_PUBLISH((session)->split_gen,                \
			    S2C(session)->split_gen);                   \
		} while ((session)->split_gen != S2C(session)->split_gen)

#define	WT_LEAVE_PAGE_INDEX(session)					\
	if (__prev_split_gen == 0)					\
		(session)->split_gen = 0;				\
	} while (0)

#define	WT_WITH_PAGE_INDEX(session, e)					\
	WT_ENTER_PAGE_INDEX(session);					\
	(e);								\
	WT_LEAVE_PAGE_INDEX(session)