/*- * Copyright (c) 2008-2014 WiredTiger, Inc. * All rights reserved. * * See the file LICENSE for redistribution information. */ /* * __wt_page_is_modified -- * Return if the page is dirty. */ static inline int __wt_page_is_modified(WT_PAGE *page) { return (page->modify != NULL && page->modify->write_gen != 0 ? 1 : 0); } /* * Estimate the per-allocation overhead. All implementations of malloc / free * have some kind of header and pad for alignment. We can't know for sure what * that adds up to, but this is an estimate based on some measurements of heap * size versus bytes in use. */ #define WT_ALLOC_OVERHEAD 32 /* * __wt_cache_page_inmem_incr -- * Increment a page's memory footprint in the cache. */ static inline void __wt_cache_page_inmem_incr(WT_SESSION_IMPL *session, WT_PAGE *page, size_t size) { WT_CACHE *cache; size += WT_ALLOC_OVERHEAD; cache = S2C(session)->cache; (void)WT_ATOMIC_ADD(cache->bytes_inmem, size); (void)WT_ATOMIC_ADD(page->memory_footprint, size); if (__wt_page_is_modified(page)) { (void)WT_ATOMIC_ADD(cache->bytes_dirty, size); (void)WT_ATOMIC_ADD(page->modify->bytes_dirty, size); } } /* * __wt_cache_page_inmem_decr -- * Decrement a page's memory footprint in the cache. */ static inline void __wt_cache_page_inmem_decr(WT_SESSION_IMPL *session, WT_PAGE *page, size_t size) { WT_CACHE *cache; size += WT_ALLOC_OVERHEAD; cache = S2C(session)->cache; (void)WT_ATOMIC_SUB(cache->bytes_inmem, size); (void)WT_ATOMIC_SUB(page->memory_footprint, size); if (__wt_page_is_modified(page)) { (void)WT_ATOMIC_SUB(cache->bytes_dirty, size); (void)WT_ATOMIC_SUB(page->modify->bytes_dirty, size); } } /* * __wt_cache_dirty_incr -- * Increment the cache dirty page/byte counts. */ static inline void __wt_cache_dirty_incr(WT_SESSION_IMPL *session, WT_PAGE *page) { WT_CACHE *cache; size_t size; cache = S2C(session)->cache; (void)WT_ATOMIC_ADD(cache->pages_dirty, 1); /* * Take care to read the memory_footprint once in case we are racing * with updates. */ size = page->memory_footprint; (void)WT_ATOMIC_ADD(cache->bytes_dirty, size); (void)WT_ATOMIC_ADD(page->modify->bytes_dirty, size); } /* * __wt_cache_dirty_decr -- * Decrement the cache dirty page/byte counts. */ static inline void __wt_cache_dirty_decr(WT_SESSION_IMPL *session, WT_PAGE *page) { WT_CACHE *cache; size_t size; cache = S2C(session)->cache; if (cache->pages_dirty < 1) { (void)__wt_errx(session, "cache dirty decrement failed: cache dirty page count went " "negative"); cache->pages_dirty = 0; } else (void)WT_ATOMIC_SUB(cache->pages_dirty, 1); /* * It is possible to decrement the footprint of the page without making * the page dirty (for example when freeing an obsolete update list), * so the footprint could change between read and decrement, and we * might attempt to decrement by a different amount than the bytes held * by the page. * * We catch that by maintaining a per-page dirty size, and fixing the * cache stats if that is non-zero when the page is discarded. * * Also take care that the global size doesn't go negative. This may * lead to small accounting errors (particularly on the last page of the * last file in a checkpoint), but that will come out in the wash when * the page is evicted. */ size = WT_MIN(page->memory_footprint, cache->bytes_dirty); (void)WT_ATOMIC_SUB(cache->bytes_dirty, size); (void)WT_ATOMIC_SUB(page->modify->bytes_dirty, size); } /* * __wt_cache_page_evict -- * Evict pages from the cache. */ static inline void __wt_cache_page_evict(WT_SESSION_IMPL *session, WT_PAGE *page) { WT_CACHE *cache; WT_PAGE_MODIFY *mod; cache = S2C(session)->cache; mod = page->modify; /* * In rare cases, we may race tracking a page's dirty footprint. * If so, we will get here with a non-zero dirty_size in the page, and * we can fix the global stats. */ if (mod != NULL && mod->bytes_dirty != 0) (void)WT_ATOMIC_SUB(cache->bytes_dirty, mod->bytes_dirty); WT_ASSERT(session, page->memory_footprint != 0); (void)WT_ATOMIC_ADD(cache->bytes_evict, page->memory_footprint); page->memory_footprint = 0; (void)WT_ATOMIC_ADD(cache->pages_evict, 1); } static inline uint64_t __wt_cache_read_gen(WT_SESSION_IMPL *session) { return (S2C(session)->cache->read_gen); } static inline void __wt_cache_read_gen_incr(WT_SESSION_IMPL *session) { ++S2C(session)->cache->read_gen; } static inline uint64_t __wt_cache_read_gen_set(WT_SESSION_IMPL *session) { /* * We return read-generations from the future (where "the future" is * measured by increments of the global read generation). The reason * is because when acquiring a new hazard pointer for a page, we can * check its read generation, and if the read generation isn't less * than the current global generation, we don't bother updating the * page. In other words, the goal is to avoid some number of updates * immediately after each update we have to make. */ return (__wt_cache_read_gen(session) + WT_READ_GEN_STEP); } /* * __wt_cache_pages_inuse -- * Return the number of pages in use. */ static inline uint64_t __wt_cache_pages_inuse(WT_CACHE *cache) { return (cache->pages_inmem - cache->pages_evict); } /* * __wt_cache_bytes_inuse -- * Return the number of bytes in use. */ static inline uint64_t __wt_cache_bytes_inuse(WT_CACHE *cache) { return (cache->bytes_inmem - cache->bytes_evict); } /* * __wt_page_modify_init -- * A page is about to be modified, allocate the modification structure. */ static inline int __wt_page_modify_init(WT_SESSION_IMPL *session, WT_PAGE *page) { WT_CONNECTION_IMPL *conn; WT_PAGE_MODIFY *modify; if (page->modify != NULL) return (0); conn = S2C(session); WT_RET(__wt_calloc_def(session, 1, &modify)); /* * Select a spinlock for the page; let the barrier immediately below * keep things from racing too badly. */ modify->page_lock = ++conn->page_lock_cnt % WT_PAGE_LOCKS(conn); /* * Multiple threads of control may be searching and deciding to modify * a page. If our modify structure is used, update the page's memory * footprint, else discard the modify structure, another thread did the * work. */ if (WT_ATOMIC_CAS(page->modify, NULL, modify)) __wt_cache_page_inmem_incr(session, page, sizeof(*modify)); else __wt_free(session, modify); return (0); } /* * __wt_page_only_modify_set -- * Mark the page (but only the page) dirty. */ static inline void __wt_page_only_modify_set(WT_SESSION_IMPL *session, WT_PAGE *page) { /* * We depend on atomic-add being a write barrier, that is, a barrier to * ensure all changes to the page are flushed before updating the page * write generation and/or marking the tree dirty, otherwise checkpoints * and/or page reconciliation might be looking at a clean page/tree. * * Every time the page transitions from clean to dirty, update the cache * and transactional information. */ if (WT_ATOMIC_ADD(page->modify->write_gen, 1) == 1) { __wt_cache_dirty_incr(session, page); /* * The page can never end up with changes older than the oldest * running transaction. */ if (F_ISSET(&session->txn, TXN_RUNNING)) page->modify->disk_snap_min = session->txn.snap_min; } /* Check if this is the largest transaction ID to update the page. */ if (TXNID_LT(page->modify->update_txn, session->txn.id)) page->modify->update_txn = session->txn.id; } /* * __wt_page_modify_set -- * Mark the page and tree dirty. */ static inline void __wt_page_modify_set(WT_SESSION_IMPL *session, WT_PAGE *page) { /* * Mark the tree dirty (even if the page is already marked dirty, newly * created pages to support "empty" files are dirty, but the file isn't * marked dirty until there's a real change needing to be written. Test * before setting the dirty flag, it's a hot cache line. * * The tree's modified flag is cleared by the checkpoint thread: set it * and insert a barrier before dirtying the page. (I don't think it's * a problem if the tree is marked dirty with all the pages clean, it * might result in an extra checkpoint that doesn't do any work but it * shouldn't cause problems; regardless, let's play it safe.) */ if (S2BT(session)->modified == 0) { S2BT(session)->modified = 1; WT_FULL_BARRIER(); } __wt_page_only_modify_set(session, page); } /* * __wt_off_page -- * Return if a pointer references off-page data. */ static inline int __wt_off_page(WT_PAGE *page, const void *p) { /* * There may be no underlying page, in which case the reference is * off-page by definition. */ return (page->dsk == NULL || p < (void *)page->dsk || p >= (void *)((uint8_t *)page->dsk + page->dsk->mem_size)); } /* * __wt_ref_key -- * Return a reference to a row-store internal page key as cheaply as * possible. */ static inline void __wt_ref_key(WT_PAGE *page, WT_REF *ref, void *keyp, size_t *sizep) { /* * An internal page key is in one of two places: if we instantiated the * key (for example, when reading the page), WT_REF.key.ikey references * a WT_IKEY structure, otherwise, WT_REF.key.pkey references an on-page * key. * * Now the magic: Any allocated memory will have a low-order bit of 0 * (the return from malloc must be aligned to store any standard type, * and we assume there's always going to be a standard type requiring * even-byte alignment). An on-page key consists of an offset/length * pair. We can fit the maximum page size into 31 bits, so we use the * low-order bit in the on-page value to flag the next 31 bits as a * page offset and the other 32 bits as the key's length, not a WT_IKEY * pointer. This breaks if allocation chunks aren't even-byte aligned * or pointers and uint64_t's don't always map their low-order bits to * the same location. */ if (ref->key.pkey & 0x01) { *(void **)keyp = WT_PAGE_REF_OFFSET(page, (ref->key.pkey & 0xFFFFFFFF) >> 1); *sizep = ref->key.pkey >> 32; } else { *(void **)keyp = WT_IKEY_DATA(ref->key.ikey); *sizep = ((WT_IKEY *)ref->key.ikey)->size; } } /* * __wt_ref_key_onpage_set -- * Set a WT_REF to reference an on-page key. */ static inline void __wt_ref_key_onpage_set(WT_PAGE *page, WT_REF *ref, WT_CELL_UNPACK *unpack) { /* * See the comment in __wt_ref_key for an explanation of the magic. */ ref->key.pkey = (uint64_t)unpack->size << 32 | (uint32_t)WT_PAGE_DISK_OFFSET(page, unpack->data) << 1 | 0x01; } /* * __wt_ref_key_instantiated -- * Return an instantiated key from a WT_REF. */ static inline WT_IKEY * __wt_ref_key_instantiated(WT_REF *ref) { /* * See the comment in __wt_ref_key for an explanation of the magic. */ return (ref->key.pkey & 0x01 ? NULL : ref->key.ikey); } /* * __wt_ref_key_clear -- * Clear a WT_REF key. */ static inline void __wt_ref_key_clear(WT_REF *ref) { /* The key union has 3 fields, all of which are 8B. */ ref->key.recno = 0; } /* * __wt_row_leaf_key -- * Set a buffer to reference a row-store leaf page key as cheaply as * possible. */ static inline int __wt_row_leaf_key(WT_SESSION_IMPL *session, WT_PAGE *page, WT_ROW *rip, WT_ITEM *key, int instantiate) { WT_BTREE *btree; WT_IKEY *ikey; WT_CELL_UNPACK unpack; btree = S2BT(session); /* * A subset of __wt_row_leaf_key_work, that is, calling that function * should give you the same results as calling this one; this function * exists to inline fast-path checks for already instantiated keys and * on-page uncompressed keys. */ retry: ikey = WT_ROW_KEY_COPY(rip); /* * Key copied. * If the key has been instantiated for any reason, off-page, use it. */ if (__wt_off_page(page, ikey)) { key->data = WT_IKEY_DATA(ikey); key->size = ikey->size; return (0); } /* If the key isn't compressed or an overflow, take it from the page. */ if (btree->huffman_key == NULL) { __wt_cell_unpack((WT_CELL *)ikey, &unpack); if (unpack.type == WT_CELL_KEY && unpack.prefix == 0) { key->data = unpack.data; key->size = unpack.size; return (0); } } /* * We have to build the key (it's never been instantiated, and it's some * kind of compressed or overflow key). * * Magic: the row-store leaf page search loop calls us to instantiate * keys, and it's not prepared to handle memory being allocated in the * key's WT_ITEM. Call __wt_row_leaf_key_work to instantiate the key * with no buffer reference, then retry to pick up a simple reference * to the instantiated key. */ if (instantiate) { WT_RET(__wt_row_leaf_key_work(session, page, rip, NULL, 1)); goto retry; } /* * If instantiate wasn't set, our caller is prepared to handle memory * allocations in the key's WT_ITEM, pass the key. */ return (__wt_row_leaf_key_work(session, page, rip, key, 0)); } /* * __wt_row_leaf_value -- * Return a pointer to the value cell for a row-store leaf page key, or * NULL if there isn't one. */ static inline WT_CELL * __wt_row_leaf_value(WT_PAGE *page, WT_ROW *rip) { WT_CELL *cell; WT_CELL_UNPACK unpack; cell = WT_ROW_KEY_COPY(rip); /* * Key copied. * * Cell now either references a WT_IKEY structure with a cell offset, * or references the on-page key WT_CELL. Both can be processed * regardless of what other threads are doing. If it's the former, * use it to get the latter. */ if (__wt_off_page(page, cell)) cell = WT_PAGE_REF_OFFSET(page, ((WT_IKEY *)cell)->cell_offset); /* Unpack the key cell, then return its associated value cell. */ __wt_cell_unpack(cell, &unpack); cell = (WT_CELL *)((uint8_t *)cell + __wt_cell_total_len(&unpack)); return (__wt_cell_leaf_value_parse(page, cell)); } /* * __wt_ref_info -- * Return the addr/size and type triplet for a reference. */ static inline int __wt_ref_info(WT_SESSION_IMPL *session, WT_PAGE *page, WT_REF *ref, const uint8_t **addrp, size_t *sizep, u_int *typep) { WT_ADDR *addr; WT_CELL_UNPACK *unpack, _unpack; addr = ref->addr; unpack = &_unpack; /* * If NULL, there is no location. * If off-page, the pointer references a WT_ADDR structure. * If on-page, the pointer references a cell. * * The type is of a limited set: internal, leaf or no-overflow leaf. */ if (addr == NULL) { *addrp = NULL; *sizep = 0; if (typep != NULL) *typep = 0; } else if (__wt_off_page(page, addr)) { *addrp = addr->addr; *sizep = addr->size; if (typep != NULL) switch (addr->type) { case WT_ADDR_INT: *typep = WT_CELL_ADDR_INT; break; case WT_ADDR_LEAF: *typep = WT_CELL_ADDR_LEAF; break; case WT_ADDR_LEAF_NO: *typep = WT_CELL_ADDR_LEAF_NO; break; WT_ILLEGAL_VALUE(session); } } else { __wt_cell_unpack((WT_CELL *)addr, unpack); *addrp = unpack->data; *sizep = unpack->size; if (typep != NULL) *typep = unpack->type; } return (0); } /* * __wt_eviction_force_check -- * Check if a page matches the criteria for forced eviction. */ static inline int __wt_eviction_force_check(WT_SESSION_IMPL *session, WT_PAGE *page) { WT_BTREE *btree; btree = S2BT(session); /* Pages are usually small enough, check that first. */ if (page->memory_footprint < btree->maxmempage) return (0); /* Leaf pages only. */ if (page->type != WT_PAGE_COL_FIX && page->type != WT_PAGE_COL_VAR && page->type != WT_PAGE_ROW_LEAF) return (0); /* Eviction may be turned off, although that's rare. */ if (F_ISSET(btree, WT_BTREE_NO_EVICTION)) return (0); /* * It's hard to imagine a page with a huge memory footprint that has * never been modified, but check to be sure. */ if (page->modify == NULL) return (0); return (1); } /* * __wt_eviction_force_txn_check -- * Check if the current transaction permits forced eviction of a page. */ static inline int __wt_eviction_force_txn_check(WT_SESSION_IMPL *session, WT_PAGE *page) { WT_TXN_STATE *txn_state; /* * Only try if there is a chance of success. If the page has already * been split and this transaction is already pinning the oldest ID so * that the page can't be evicted, it has to complete before eviction * can succeed. */ txn_state = &S2C(session)->txn_global.states[session->id]; if (!F_ISSET_ATOMIC(page, WT_PAGE_WAS_SPLIT) || txn_state->snap_min == WT_TXN_NONE || TXNID_LT(page->modify->update_txn, txn_state->snap_min)) return (1); return (0); } /* * __wt_page_release -- * Release a reference to a page. */ static inline int __wt_page_release(WT_SESSION_IMPL *session, WT_PAGE *page) { WT_DECL_RET; /* * Discard our hazard pointer. Ignore pages we don't have and the root * page, which sticks in memory, regardless. */ if (page == NULL || WT_PAGE_IS_ROOT(page)) return (0); /* * Try to immediately evict pages if they have the special "oldest" * read generation and we have some chance of succeeding. */ if (page->read_gen == WT_READ_GEN_OLDEST && __wt_eviction_force_txn_check(session, page) && WT_ATOMIC_CAS(page->ref->state, WT_REF_MEM, WT_REF_LOCKED)) { if ((ret = __wt_hazard_clear(session, page)) != 0) { page->ref->state = WT_REF_MEM; return (ret); } WT_TRET(__wt_evict_page(session, page)); if (ret == 0) WT_STAT_FAST_CONN_INCR(session, cache_eviction_force); else WT_STAT_FAST_CONN_INCR( session, cache_eviction_force_fail); if (ret == EBUSY) ret = 0; return (ret); } return (__wt_hazard_clear(session, page)); } /* * __wt_page_swap_func -- * Swap one page's hazard pointer for another one when hazard pointer * coupling up/down the tree. */ static inline int __wt_page_swap_func( WT_SESSION_IMPL *session, WT_PAGE *out, WT_PAGE *in, WT_REF *inref #ifdef HAVE_DIAGNOSTIC , const char *file, int line #endif ) { WT_DECL_RET; int acquired; /* * This function is here to simplify the error handling during hazard * pointer coupling so we never leave a hazard pointer dangling. The * assumption is we're holding a hazard pointer on "out", and want to * read page "in", acquiring a hazard pointer on it, then release page * "out" and its hazard pointer. If something fails, discard it all. */ ret = __wt_page_in_func(session, in, inref #ifdef HAVE_DIAGNOSTIC , file, line #endif ); acquired = ret == 0; WT_TRET(__wt_page_release(session, out)); if (ret != 0 && acquired) WT_TRET(__wt_page_release(session, inref->page)); return (ret); } /* * __wt_page_hazard_check -- * Return if there's a hazard pointer to the page in the system. */ static inline WT_HAZARD * __wt_page_hazard_check(WT_SESSION_IMPL *session, WT_PAGE *page) { WT_CONNECTION_IMPL *conn; WT_HAZARD *hp; WT_SESSION_IMPL *s; uint32_t i, hazard_size, session_cnt; conn = S2C(session); /* * No lock is required because the session array is fixed size, but it * may contain inactive entries. We must review any active session * that might contain a hazard pointer, so insert a barrier before * reading the active session count. That way, no matter what sessions * come or go, we'll check the slots for all of the sessions that could * have been active when we started our check. */ WT_ORDERED_READ(session_cnt, conn->session_cnt); for (s = conn->sessions, i = 0; i < session_cnt; ++s, ++i) { if (!s->active) continue; WT_ORDERED_READ(hazard_size, s->hazard_size); for (hp = s->hazard; hp < s->hazard + hazard_size; ++hp) if (hp->page == page) return (hp); } return (NULL); } /* * __wt_eviction_force -- * Forcefully evict a page, if possible. */ static inline int __wt_eviction_force(WT_SESSION_IMPL *session, WT_PAGE *page) { /* * Check if eviction or splitting has a chance of succeeding, otherwise * stall to give other transactions a chance to complete. */ __wt_txn_update_oldest(session); if (!F_ISSET_ATOMIC(page, WT_PAGE_WAS_SPLIT) || __wt_txn_visible_all(session, page->modify->update_txn)) { page->read_gen = WT_READ_GEN_OLDEST; WT_RET(__wt_page_release(session, page)); /* * Forced eviction can create chains of internal pages before * the cache is full. Setup the eviction server to look for * internal page merges after we successfully force evict. */ F_SET(S2C(session)->cache, WT_EVICT_INTERNAL); WT_RET(__wt_evict_server_wake(session)); } else { WT_RET(__wt_page_release(session, page)); __wt_sleep(0, 10000); } return (0); } /* * __wt_skip_choose_depth -- * Randomly choose a depth for a skiplist insert. */ static inline u_int __wt_skip_choose_depth(void) { u_int d; for (d = 1; d < WT_SKIP_MAXDEPTH && __wt_random() < WT_SKIP_PROBABILITY; d++) ; return (d); } /* * __wt_btree_size_overflow -- * Check if the size of an in-memory tree with a single leaf page is over * a specified maximum. If called on anything other than a simple tree with a * single leaf page, returns true so the calling code will switch to a new tree. */ static inline int __wt_btree_size_overflow(WT_SESSION_IMPL *session, uint64_t maxsize) { WT_BTREE *btree; WT_PAGE *child, *root; btree = S2BT(session); root = btree->root_page; if (root == NULL || (child = root->u.intl.t->page) == NULL) return (0); /* Make sure this is a simple tree, or LSM should switch. */ if (!F_ISSET(btree, WT_BTREE_NO_EVICTION) || root->entries != 1 || root->u.intl.t->state != WT_REF_MEM || child->type != WT_PAGE_ROW_LEAF) return (1); return (child->memory_footprint > maxsize); } /* * __wt_lex_compare -- * Lexicographic comparison routine. * * Returns: * < 0 if user_item is lexicographically < tree_item * = 0 if user_item is lexicographically = tree_item * > 0 if user_item is lexicographically > tree_item * * We use the names "user" and "tree" so it's clear in the btree code which * the application is looking at when we call its comparison func. */ static inline int __wt_lex_compare(const WT_ITEM *user_item, const WT_ITEM *tree_item) { const uint8_t *userp, *treep; size_t len, usz, tsz; usz = user_item->size; tsz = tree_item->size; len = WT_MIN(usz, tsz); for (userp = user_item->data, treep = tree_item->data; len > 0; --len, ++userp, ++treep) if (*userp != *treep) return (*userp < *treep ? -1 : 1); /* Contents are equal up to the smallest length. */ return ((usz == tsz) ? 0 : (usz < tsz) ? -1 : 1); } #define WT_LEX_CMP(s, collator, k1, k2, cmp) \ ((collator) == NULL ? \ (((cmp) = __wt_lex_compare((k1), (k2))), 0) : \ (collator)->compare(collator, &(s)->iface, (k1), (k2), &(cmp))) /* * __wt_lex_compare_skip -- * Lexicographic comparison routine, but skipping leading bytes. * * Returns: * < 0 if user_item is lexicographically < tree_item * = 0 if user_item is lexicographically = tree_item * > 0 if user_item is lexicographically > tree_item * * We use the names "user" and "tree" so it's clear in the btree code which * the application is looking at when we call its comparison func. */ static inline int __wt_lex_compare_skip( const WT_ITEM *user_item, const WT_ITEM *tree_item, size_t *matchp) { const uint8_t *userp, *treep; size_t len, usz, tsz; usz = user_item->size; tsz = tree_item->size; len = WT_MIN(usz, tsz) - *matchp; for (userp = (uint8_t *)user_item->data + *matchp, treep = (uint8_t *)tree_item->data + *matchp; len > 0; --len, ++userp, ++treep, ++*matchp) if (*userp != *treep) return (*userp < *treep ? -1 : 1); /* Contents are equal up to the smallest length. */ return ((usz == tsz) ? 0 : (usz < tsz) ? -1 : 1); } #define WT_LEX_CMP_SKIP(s, collator, k1, k2, cmp, matchp) \ ((collator) == NULL ? \ (((cmp) = __wt_lex_compare_skip((k1), (k2), matchp)), 0) : \ (collator)->compare(collator, &(s)->iface, (k1), (k2), &(cmp))) /* * __wt_btree_mergeable -- * Determines whether the given page is a candidate for merging. */ static inline int __wt_btree_mergeable(WT_PAGE *page) { if (WT_PAGE_IS_ROOT(page) || page->modify == NULL || !F_ISSET(page->modify, WT_PM_REC_SPLIT_MERGE)) return (0); return (!WT_PAGE_IS_ROOT(page->parent)); }