Lines Matching full:page
63 /* There are four page types: meta, index, leaf and overflow.
64 * They all share the same page header.
66 struct page { /* represents an on-disk page */ struct
67 pgno_t pgno; /* page number */ argument
68 #define P_BRANCH 0x01 /* branch page */
69 #define P_LEAF 0x02 /* leaf page */
70 #define P_OVERFLOW 0x04 /* overflow page */
71 #define P_META 0x08 /* meta page */
72 #define P_HEAD 0x10 /* header page */
82 pgno_t pb_next_pgno; /* overflow page linked list */ argument
87 #define PAGEHDRSZ offsetof(struct page, ptrs) argument
90 #define NUMKEYS(mp) (((mp)->page->lower - PAGEHDRSZ) >> 1)
91 #define SIZELEFT(mp) (indx_t)((mp)->page->upper - (mp)->page->lower)
94 #define IS_LEAF(mp) F_ISSET((mp)->page->flags, P_LEAF)
95 #define IS_BRANCH(mp) F_ISSET((mp)->page->flags, P_BRANCH)
96 #define IS_OVERFLOW(mp) F_ISSET((mp)->page->flags, P_OVERFLOW)
98 struct bt_head { /* header page content */
102 uint32_t psize; /* page size */
105 struct bt_meta { /* meta (footer) page content */
108 pgno_t root; /* page number of root page */
109 pgno_t prev_meta; /* previous meta page number */
125 struct mpage { /* an in-memory cached page */
126 RB_ENTRY(mpage) entry; /* page cache entry */
132 struct page *page; member
133 pgno_t pgno; /* copy of page->pgno */
158 unsigned int ki; /* cursor index on page */
182 pgno_t np_pgno; /* child page number */
186 #define F_BIGDATA 0x01 /* data put on overflow page */
192 pgno_t root; /* current / new root page */
193 pgno_t next_pgno; /* next unallocated page */
222 #define NODEPTR(mp, i) NODEPTRP((mp)->page, i)
232 struct page *page);
245 static int btree_is_meta_page(struct page *p);
275 struct page *p, struct btval *data);
476 /* Update LRU queue. Move page to the end. */ in mpage_lookup()
495 free(mp->page); in mpage_free()
527 if ((copy->page = malloc(bt->head.psize)) == NULL) { in mpage_copy()
531 bcopy(mp->page, copy->page, bt->head.psize); in mpage_copy()
560 /* Mark a page as dirty and push it on the dirty queue.
574 /* Touch a page: make it dirty and re-insert into tree with updated pgno.
584 DPRINTF("touching page %u -> %u", mp->pgno, bt->txn->next_pgno); in mpage_touch()
591 mp->pgno = mp->page->pgno = bt->txn->next_pgno++; in mpage_touch()
595 /* Update the page number to new touched page. */ in mpage_touch()
605 btree_read_page(struct btree *bt, pgno_t pgno, struct page *page) in btree_read_page() argument
609 DPRINTF("reading page %u", pgno); in btree_read_page()
611 if ((rc = pread(bt->fd, page, bt->head.psize, (off_t)pgno*bt->head.psize)) == 0) { in btree_read_page()
612 DPRINTF("page %u doesn't exist", pgno); in btree_read_page()
622 if (page->pgno != pgno) { in btree_read_page()
623 DPRINTF("page numbers don't match: %u != %u", pgno, page->pgno); in btree_read_page()
628 DPRINTF("page %u has flags 0x%X", pgno, page->flags); in btree_read_page()
687 DPRINTF("begin transaction on btree %p, root page %u", bt, txn->root); in btree_txn_begin()
702 DPRINTF("abort transaction on btree %p, root page %u", bt, txn->root); in btree_txn_abort()
770 DPRINTF("extending to multiple of page size: %llu", size); in btree_txn_commit()
779 DPRINTF("committing transaction on btree %p, root page %u", in btree_txn_commit()
788 DPRINTF("committing page %u", mp->pgno); in btree_txn_commit()
790 iov[n].iov_base = mp->page; in btree_txn_commit()
841 struct page *p; in btree_write_header()
845 DPRINTF("writing header page"); in btree_write_header()
880 char page[PAGESIZE]; in btree_read_header() local
881 struct page *p; in btree_read_header()
887 /* We don't know the page size yet, so use a minimum value. in btree_read_header()
890 if ((rc = pread(bt->fd, page, PAGESIZE, 0)) == 0) { in btree_read_header()
900 p = (struct page *)page; in btree_read_header()
903 DPRINTF("page %d not a header page", p->pgno); in btree_read_header()
933 DPRINTF("writing meta page for root page %u", root); in btree_write_meta()
948 /* Copy the meta data changes to the new meta page. */ in btree_write_meta()
949 meta = METADATA(mp->page); in btree_write_meta()
952 rc = write(bt->fd, mp->page, bt->head.psize); in btree_write_meta()
969 /* Returns true if page p is a valid meta page, false otherwise.
972 btree_is_meta_page(struct page *p) in btree_is_meta_page()
979 DPRINTF("page %d not a meta page", p->pgno); in btree_is_meta_page()
985 DPRINTF("page %d points to an invalid root page", p->pgno); in btree_is_meta_page()
992 DPRINTF("page %d has an invalid digest", p->pgno); in btree_is_meta_page()
1037 DPRINTF("filesize not a multiple of the page size!"); in btree_read_meta()
1046 DPRINTF("size unchanged, keeping current meta page"); in btree_read_meta()
1059 if (btree_is_meta_page(mp->page)) { in btree_read_meta()
1060 meta = METADATA(mp->page); in btree_read_meta()
1067 /* Make copy of last meta page. */ in btree_read_meta()
1072 --meta_pgno; /* scan backwards to first valid meta page */ in btree_read_meta()
1129 DPRINTF("previous meta page: %u", bt->meta.prev_meta); in btree_open_fd()
1189 /* Search for key within a leaf page, using binary search.
1206 DPRINTF("searching %lu keys in %s page %u with prefix [%.*s]", in btree_search_node()
1268 DPRINTF("popped page %u off cursor %p", top->mpage->pgno, cursor); in cursor_pop_page()
1278 DPRINTF("pushing page %u on cursor %p", mp->pgno, cursor); in cursor_push_page()
1297 if ((mp->page = malloc(bt->head.psize)) == NULL) { in btree_get_mpage()
1301 if (btree_read_page(bt, pgno, mp->page) != BT_SUCCESS) { in btree_get_mpage()
1308 DPRINTF("returning page %u from cache", pgno); in btree_get_mpage()
1365 DPRINTF("found common prefix [%.*s] (len %zu) for page %u", in find_common_prefix()
1383 DPRINTF("branch page %u has %lu keys", mp->pgno, NUMKEYS(mp)); in btree_search_page_root()
1385 DPRINTF("found index 0 to page %u", NODEPGNO(NODEPTR(mp, 0))); in btree_search_page_root()
1387 if (key == NULL) /* Initialize cursor to first page. */ in btree_search_page_root()
1424 DPRINTF("internal error, index points to a %02X page!?", in btree_search_page_root()
1425 mp->page->flags); in btree_search_page_root()
1429 DPRINTF("found leaf page %u for key %.*s", mp->pgno, in btree_search_page_root()
1436 /* Search for the page a given key should be in.
1437 * Stores a pointer to the found page in *mpp.
1438 * If key is NULL, search for the lowest page (used by btree_cursor_first).
1440 * If modify is true, visited pages are updated with new page numbers.
1456 /* Choose which root page to start with. If a transaction is given in btree_search_page()
1457 * use the root page from the transaction, otherwise read the last in btree_search_page()
1458 * committed root page. in btree_search_page()
1480 DPRINTF("root page has flags 0x%X", mp->page->flags); in btree_search_page()
1537 !F_ISSET(omp->page->flags, P_OVERFLOW)) { in btree_read_data()
1538 DPRINTF("read overflow page %u failed", pgno); in btree_read_data()
1546 bcopy(omp->page->ptrs, (char *)data->data + sz, psz); in btree_read_data()
1548 pgno = omp->page->p_next_pgno; in btree_read_data()
1613 DPRINTF("parent page is page %u, index %u", in btree_sibling()
1691 DPRINTF("cursor_next: top page is %u in cursor %p", mp->pgno, cursor); in btree_cursor_next()
1694 DPRINTF("=====> move to next sibling page"); in btree_cursor_next()
1701 DPRINTF("next page is %u, key index %u", mp->pgno, top->ki); in btree_cursor_next()
1705 DPRINTF("==> cursor points to page %u with %lu keys, key index %u", in btree_cursor_next()
1848 DPRINTF("allocating new mpage %u, page size %u", in btree_new_page()
1852 if ((mp->page = malloc(bt->head.psize)) == NULL) { in btree_new_page()
1856 mp->pgno = mp->page->pgno = bt->txn->next_pgno++; in btree_new_page()
1857 mp->page->flags = flags; in btree_new_page()
1858 mp->page->lower = PAGEHDRSZ; in btree_new_page()
1859 mp->page->upper = bt->head.psize; in btree_new_page()
1881 /* put on overflow page */ in bt_leaf_size()
1895 /* put on overflow page */ in bt_branch_size()
1904 btree_write_overflow_data(struct btree *bt, struct page *p, struct btval *data) in btree_write_overflow_data()
1909 pgno_t *linkp; /* linked page stored here */ in btree_write_overflow_data()
1916 p = next->page; in btree_write_overflow_data()
1919 /* need another overflow page */ in btree_write_overflow_data()
1923 DPRINTF("linking overflow page %u", next->pgno); in btree_write_overflow_data()
1929 DPRINTF("copying %zu bytes to overflow page %u", sz, p->pgno); in btree_write_overflow_data()
1947 struct page *p; in btree_add_node()
1948 struct mpage *ofp = NULL; /* overflow page */ in btree_add_node()
1950 p = mp->page; in btree_add_node()
1953 DPRINTF("add node [%.*s] to %s page %u at index %d, key size %zu", in btree_add_node()
1965 /* Data already on overflow page. */ in btree_add_node()
1968 /* Put data on overflow page. */ in btree_add_node()
1969 DPRINTF("data size is %zu, put on overflow page", in btree_add_node()
1974 DPRINTF("allocated overflow page %u", ofp->pgno); in btree_add_node()
1980 DPRINTF("not enough room in page %u, got %lu ptrs", in btree_add_node()
2023 if (btree_write_overflow_data(bt, ofp->page, in btree_add_node()
2040 DPRINTF("delete node %u on %s page %u", indx, in btree_del_node()
2053 ptr = mp->page->ptrs[indx]; in btree_del_node()
2057 mp->page->ptrs[j] = mp->page->ptrs[i]; in btree_del_node()
2058 if (mp->page->ptrs[i] < ptr) in btree_del_node()
2059 mp->page->ptrs[j] += sz; in btree_del_node()
2064 base = (char *)mp->page + mp->page->upper; in btree_del_node()
2065 bcopy(base, base + sz, ptr - mp->page->upper); in btree_del_node()
2067 mp->page->lower -= sizeof(indx_t); in btree_del_node()
2068 mp->page->upper += sz; in btree_del_node()
2122 ptr = mp->page->ptrs[indx]; in btree_update_key()
2123 DPRINTF("update key %u (ofs %u) [%.*s] to [%.*s] on page %u", in btree_update_key()
2138 if (mp->page->ptrs[i] <= ptr) in btree_update_key()
2139 mp->page->ptrs[i] -= delta; in btree_update_key()
2142 base = (char *)mp->page + mp->page->upper; in btree_update_key()
2143 len = ptr - mp->page->upper + NODESIZE; in btree_update_key()
2145 mp->page->upper -= delta; in btree_update_key()
2164 DPRINTF("adjusting prefix lengths on page %u with delta %d", in btree_adjust_prefix()
2215 DPRINTF("moving %s node %u [%.*s] on page %u to node %u on page %u", in btree_move_node()
2225 /* Need to check if the page the moved node points to in btree_move_node()
2243 /* Check if src node has destination page prefix. Otherwise the in btree_move_node()
2244 * destination page must expand its prefix on all its nodes. in btree_move_node()
2264 DPRINTF("found lowest key [%.*s] on leaf page %u", in btree_move_node()
2277 /* Add the node to the destination page. Adjust prefix for in btree_move_node()
2278 * destination page. in btree_move_node()
2290 /* Delete the node from the source page. in btree_move_node()
2302 DPRINTF("update separator for source page %u to [%.*s]", in btree_move_node()
2321 DPRINTF("update separator for destination page %u to [%.*s]", in btree_move_node()
2334 /* We can get a new page prefix here! in btree_move_node()
2335 * Must update keys in all nodes of this page! in btree_move_node()
2381 DPRINTF("merging page %u and %u", src->pgno, dst->pgno); in btree_merge()
2383 assert(src->parent); /* can't merge root page */ in btree_merge()
2395 /* Check if source nodes has destination page prefix. Otherwise in btree_merge()
2396 * the destination page must expand its prefix on all its nodes. in btree_merge()
2421 DPRINTF("found lowest key [%.*s] on leaf page %u", in btree_merge()
2439 DPRINTF("dst page %u now has %lu keys (%.1f%% filled)", in btree_merge()
2442 /* Unlink the src page from parent. in btree_merge()
2478 DPRINTF("rebalancing %s page %u (has %lu keys, %.1f%% full)", in btree_rebalance()
2483 DPRINTF("no need to rebalance page %u, above fill threshold", in btree_rebalance()
2497 DPRINTF("collapsing root page!"); in btree_rebalance()
2505 DPRINTF("root page doesn't need rebalancing"); in btree_rebalance()
2509 /* The parent (branch page) must have at least 2 pointers, in btree_rebalance()
2514 /* Leaf page fill factor is below the threshold. in btree_rebalance()
2516 * merge with a neighbor page. in btree_rebalance()
2544 DPRINTF("found neighbor page %u (%lu keys, %.1f%% full)", in btree_rebalance()
2547 /* If the neighbor page is above threshold and has at least two in btree_rebalance()
2690 /* Split page <*mpp>, and insert <key,(data|newpgno)> in either left or
2693 * refer to a node in the new right sibling page.
2709 struct page *copy; in btree_split()
2717 DPRINTF("-----> splitting %s page %u and adding [%.*s] at index %d", in btree_split()
2720 DPRINTF("page %u has prefix [%.*s]", mp->pgno, in btree_split()
2737 DPRINTF("parent branch page is %u", mp->parent->pgno); in btree_split()
2741 if ((pright = btree_new_page(bt, mp->page->flags)) == NULL) in btree_split()
2745 DPRINTF("new right sibling: page %u", pright->pgno); in btree_split()
2750 bcopy(mp->page, copy, bt->head.psize); in btree_split()
2752 memset(&mp->page->ptrs, 0, bt->head.psize - PAGEHDRSZ); in btree_split()
2753 mp->page->lower = PAGEHDRSZ; in btree_split()
2754 mp->page->upper = bt->head.psize; in btree_split()
2795 /* Right page might now have changed parent. in btree_split()
2796 * Check if left page also changed parent. in btree_split()
2813 /* Update prefix for right and left page, if the parent was split. in btree_split()
2851 /* Update page and index for the new key. */ in btree_split()
2946 /* new file, just write a root leaf page */ in btree_txn_put()
2947 DPRINTF("allocating new root leaf page"); in btree_txn_put()
2972 /* There is room already in this leaf page. */ in btree_txn_put()
3000 struct page *p; in btree_compact_tree()
3003 /* Get the page and make a copy of it. in btree_compact_tree()
3009 bcopy(mp->page, p, bt->head.psize); in btree_compact_tree()
3011 /* Go through all nodes in the (copied) page and update the in btree_compact_tree()
3012 * page pointers. in btree_compact_tree()
3111 /* Write a "tombstone" meta page so other processes can pick up in btree_compact()
3134 /* Reverts the last change. Truncates the file at the last root page.
3142 DPRINTF("truncating file at page %u", bt->meta.root); in btree_revert()