42c42
< __FBSDID("$FreeBSD: head/sys/kern/vfs_subr.c 250505 2013-05-11 11:17:44Z kib $");
---
> __FBSDID("$FreeBSD: head/sys/kern/vfs_subr.c 250551 2013-05-12 04:05:01Z jeff $");
67a68
> #include <sys/pctrie.h>
186a188,189
> static uma_zone_t buf_trie_zone;
>
286a290,307
> * Support for the bufobj clean & dirty pctrie.
> */
> static void *
> buf_trie_alloc(struct pctrie *ptree)
> {
>
> return uma_zalloc(buf_trie_zone, M_NOWAIT);
> }
>
> static void
> buf_trie_free(struct pctrie *ptree, void *node)
> {
>
> uma_zfree(buf_trie_zone, node);
> }
> PCTRIE_DEFINE(BUF, buf, b_lblkno, buf_trie_alloc, buf_trie_free);
>
> /*
331a353,361
> * Preallocate enough nodes to support one-per buf so that
> * we can not fail an insert. reassignbuf() callers can not
> * tolerate the insertion failure.
> */
> buf_trie_zone = uma_zcreate("BUF TRIE", pctrie_node_size(),
> NULL, NULL, pctrie_zone_init, NULL, UMA_ALIGN_PTR,
> UMA_ZONE_NOFREE | UMA_ZONE_VM);
> uma_prealloc(buf_trie_zone, nbuf);
> /*
1479,1543d1508
< /*
< * buf_splay() - splay tree core for the clean/dirty list of buffers in
< * a vnode.
< *
< * NOTE: We have to deal with the special case of a background bitmap
< * buffer, a situation where two buffers will have the same logical
< * block offset. We want (1) only the foreground buffer to be accessed
< * in a lookup and (2) must differentiate between the foreground and
< * background buffer in the splay tree algorithm because the splay
< * tree cannot normally handle multiple entities with the same 'index'.
< * We accomplish this by adding differentiating flags to the splay tree's
< * numerical domain.
< */
< static
< struct buf *
< buf_splay(daddr_t lblkno, b_xflags_t xflags, struct buf *root)
< {
< struct buf dummy;
< struct buf *lefttreemax, *righttreemin, *y;
<
< if (root == NULL)
< return (NULL);
< lefttreemax = righttreemin = &dummy;
< for (;;) {
< if (lblkno < root->b_lblkno) {
< if ((y = root->b_left) == NULL)
< break;
< if (lblkno < y->b_lblkno) {
< /* Rotate right. */
< root->b_left = y->b_right;
< y->b_right = root;
< root = y;
< if ((y = root->b_left) == NULL)
< break;
< }
< /* Link into the new root's right tree. */
< righttreemin->b_left = root;
< righttreemin = root;
< } else if (lblkno > root->b_lblkno) {
< if ((y = root->b_right) == NULL)
< break;
< if (lblkno > y->b_lblkno) {
< /* Rotate left. */
< root->b_right = y->b_left;
< y->b_left = root;
< root = y;
< if ((y = root->b_right) == NULL)
< break;
< }
< /* Link into the new root's left tree. */
< lefttreemax->b_right = root;
< lefttreemax = root;
< } else {
< break;
< }
< root = y;
< }
< /* Assemble the new root. */
< lefttreemax->b_right = root->b_left;
< righttreemin->b_left = root->b_right;
< root->b_left = dummy.b_right;
< root->b_right = dummy.b_left;
< return (root);
< }
<
1547d1511
< struct buf *root;
1559,1569c1523
< if (bp != bv->bv_root) {
< root = buf_splay(bp->b_lblkno, bp->b_xflags, bv->bv_root);
< KASSERT(root == bp, ("splay lookup failed in remove"));
< }
< if (bp->b_left == NULL) {
< root = bp->b_right;
< } else {
< root = buf_splay(bp->b_lblkno, bp->b_xflags, bp->b_left);
< root->b_right = bp->b_right;
< }
< bv->bv_root = root;
---
> BUF_PCTRIE_REMOVE(&bv->bv_root, bp->b_lblkno);
1576,1577c1530
< * Add the buffer to the sorted clean or dirty block list using a
< * splay tree algorithm.
---
> * Add the buffer to the sorted clean or dirty block list.
1584d1536
< struct buf *root;
1585a1538,1539
> struct buf *n;
> int error;
1596,1599c1550,1556
< root = buf_splay(bp->b_lblkno, bp->b_xflags, bv->bv_root);
< if (root == NULL) {
< bp->b_left = NULL;
< bp->b_right = NULL;
---
> /*
> * Keep the list ordered. Optimize empty list insertion. Assume
> * we tend to grow at the tail so lookup_le should usually be cheaper
> * than _ge.
> */
> if (bv->bv_cnt == 0 ||
> bp->b_lblkno > TAILQ_LAST(&bv->bv_hd, buflists)->b_lblkno)
1601,1611c1558,1564
< } else if (bp->b_lblkno < root->b_lblkno) {
< bp->b_left = root->b_left;
< bp->b_right = root;
< root->b_left = NULL;
< TAILQ_INSERT_BEFORE(root, bp, b_bobufs);
< } else {
< bp->b_right = root->b_right;
< bp->b_left = root;
< root->b_right = NULL;
< TAILQ_INSERT_AFTER(&bv->bv_hd, root, bp, b_bobufs);
< }
---
> else if ((n = BUF_PCTRIE_LOOKUP_LE(&bv->bv_root, bp->b_lblkno)) == NULL)
> TAILQ_INSERT_HEAD(&bv->bv_hd, bp, b_bobufs);
> else
> TAILQ_INSERT_AFTER(&bv->bv_hd, n, bp, b_bobufs);
> error = BUF_PCTRIE_INSERT(&bv->bv_root, bp);
> if (error)
> panic("buf_vlist_add: Preallocated nodes insufficient.");
1613d1565
< bv->bv_root = bp;
1634c1586,1587
< if ((bp = bo->bo_clean.bv_root) != NULL && bp->b_lblkno == lblkno)
---
> bp = BUF_PCTRIE_LOOKUP(&bo->bo_clean.bv_root, lblkno);
> if (bp != NULL)
1636,1648c1589
< if ((bp = bo->bo_dirty.bv_root) != NULL && bp->b_lblkno == lblkno)
< return (bp);
< if ((bp = bo->bo_clean.bv_root) != NULL) {
< bo->bo_clean.bv_root = bp = buf_splay(lblkno, 0, bp);
< if (bp->b_lblkno == lblkno)
< return (bp);
< }
< if ((bp = bo->bo_dirty.bv_root) != NULL) {
< bo->bo_dirty.bv_root = bp = buf_splay(lblkno, 0, bp);
< if (bp->b_lblkno == lblkno)
< return (bp);
< }
< return (NULL);
---
> return BUF_PCTRIE_LOOKUP(&bo->bo_dirty.bv_root, lblkno);
2463c2404,2405
< VNASSERT(bo->bo_clean.bv_root == NULL, vp, ("cleanblkroot not NULL"));
---
> VNASSERT(pctrie_is_empty(&bo->bo_clean.bv_root), vp,
> ("clean blk trie not empty"));
2465c2407,2408
< VNASSERT(bo->bo_dirty.bv_root == NULL, vp, ("dirtyblkroot not NULL"));
---
> VNASSERT(pctrie_is_empty(&bo->bo_dirty.bv_root), vp,
> ("dirty blk trie not empty"));