xfs_extent_busy.rar_Able

/* * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc. * Copyright (c) 2010 David Chinner. * Copyright (c) 2011 Christoph Hellwig. * All Rights Reserved. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation. * * This program is distributed in the hope that it would be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #include "xfs.h" #include "xfs_fs.h" #include "xfs_format.h" #include "xfs_log_format.h" #include "xfs_shared.h" #include "xfs_trans_resv.h" #include "xfs_sb.h" #include "xfs_mount.h" #include "xfs_alloc.h" #include "xfs_extent_busy.h" #include "xfs_trace.h" #include "xfs_trans.h" #include "xfs_log.h" void xfs_extent_busy_insert( struct xfs_trans *tp, xfs_agnumber_t agno, xfs_agblock_t bno, xfs_extlen_t len, unsigned int flags) { struct xfs_extent_busy *new; struct xfs_extent_busy *busyp; struct xfs_perag *pag; struct rb_node **rbp; struct rb_node *parent = NULL; new = kmem_zalloc(sizeof(struct xfs_extent_busy), KM_MAYFAIL); if (!new) { /* * No Memory! Since it is now not possible to track the free * block, make this a synchronous transaction to insure that * the block is not reused before this transaction commits. */ trace_xfs_extent_busy_enomem(tp->t_mountp, agno, bno, len); xfs_trans_set_sync(tp); return; } new->agno = agno; new->bno = bno; new->length = len; INIT_LIST_HEAD(&new->list); new->flags = flags; /* trace before insert to be able to see failed inserts */ trace_xfs_extent_busy(tp->t_mountp, agno, bno, len); pag = xfs_perag_get(tp->t_mountp, new->agno); spin_lock(&pag->pagb_lock); rbp = &pag->pagb_tree.rb_node; while (*rbp) { parent = *rbp; busyp = rb_entry(parent, struct xfs_extent_busy, rb_node); if (new->bno < busyp->bno) { rbp = &(*rbp)->rb_left; ASSERT(new->bno + new->length <= busyp->bno); } else if (new->bno > busyp->bno) { rbp = &(*rbp)->rb_right; ASSERT(bno >= busyp->bno + busyp->length); } else { ASSERT(0); } } rb_link_node(&new->rb_node, parent, rbp); rb_insert_color(&new->rb_node, &pag->pagb_tree); list_add(&new->list, &tp->t_busy); spin_unlock(&pag->pagb_lock); xfs_perag_put(pag); } /* * Search for a busy extent within the range of the extent we are about to * allocate. You need to be holding the busy extent tree lock when calling * xfs_extent_busy_search(). This function returns 0 for no overlapping busy * extent, -1 for an overlapping but not exact busy extent, and 1 for an exact * match. This is done so that a non-zero return indicates an overlap that * will require a synchronous transaction, but it can still be * used to distinguish between a partial or exact match. */ int xfs_extent_busy_search( struct xfs_mount *mp, xfs_agnumber_t agno, xfs_agblock_t bno, xfs_extlen_t len) { struct xfs_perag *pag; struct rb_node *rbp; struct xfs_extent_busy *busyp; int match = 0; pag = xfs_perag_get(mp, agno); spin_lock(&pag->pagb_lock); rbp = pag->pagb_tree.rb_node; /* find closest start bno overlap */ while (rbp) { busyp = rb_entry(rbp, struct xfs_extent_busy, rb_node); if (bno < busyp->bno) { /* may overlap, but exact start block is lower */ if (bno + len > busyp->bno) match = -1; rbp = rbp->rb_left; } else if (bno > busyp->bno) { /* may overlap, but exact start block is higher */ if (bno < busyp->bno + busyp->length) match = -1; rbp = rbp->rb_right; } else { /* bno matches busyp, length determines exact match */ match = (busyp->length == len) ? 1 : -1; break; } } spin_unlock(&pag->pagb_lock); xfs_perag_put(pag); return match; } /* * The found free extent [fbno, fend] overlaps part or all of the given busy * extent. If the overlap covers the beginning, the end, or all of the busy * extent, the overlapping portion can be made unbusy and used for the * allocation. We can't split a busy extent because we can't modify a * transaction/CIL context busy list, but we can update an entry's block * number or length. * * Returns true if the extent can safely be reused, or false if the search * needs to be restarted. */ STATIC bool xfs_extent_busy_update_extent( struct xfs_mount *mp, struct xfs_perag *pag, struct xfs_extent_busy *busyp, xfs_agblock_t fbno, xfs_extlen_t flen, bool userdata) __releases(&pag->pagb_lock) __acquires(&pag->pagb_lock) { xfs_agblock_t fend = fbno + flen; xfs_agblock_t bbno = busyp->bno; xfs_agblock_t bend = bbno + busyp->length; /* * This extent is currently being discarded. Give the thread * performing the discard a chance to mark the extent unbusy * and retry. */ if (busyp->flags & XFS_EXTENT_BUSY_DISCARDED) { spin_unlock(&pag->pagb_lock); delay(1); spin_lock(&pag->pagb_lock); return false; } /* * If there is a busy extent overlapping a user allocation, we have * no choice but to force the log and retry the search. * * Fortunately this does not happen during normal operation, but * only if the filesystem is very low on space and has to dip into * the AGFL for normal allocations. */ if (userdata) goto out_force_log; if (bbno < fbno && bend > fend) { /* * Case 1: * bbno bend * +BBBBBBBBBBBBBBBBB+ * +---------+ * fbno fend */ /* * We would have to split the busy extent to be able to track * it correct, which we cannot do because we would have to * modify the list of busy extents attached to the transaction * or CIL context, which is immutable. * * Force out the log to clear the busy extent and retry the * search. */ goto out_force_log; } else if (bbno >= fbno && bend <= fend) { /* * Case 2: * bbno bend * +BBBBBBBBBBBBBBBBB+ * +-----------------+ * fbno fend * * Case 3: * bbno bend * +BBBBBBBBBBBBBBBBB+ * +--------------------------+ * fbno fend * * Case 4: * bbno bend * +BBBBBBBBBBBBBBBBB+ * +--------------------------+ * fbno fend * * Case 5: * bbno bend * +BBBBBBBBBBBBBBBBB+ * +-----------------------------------+ * fbno fend * */ /* * The busy extent is fully covered by the extent we are * allocating, and can simply be removed from the rbtree. * However we cannot remove it from the immutable list * tracking busy extents in the transaction or CIL context, * so set the length to zero to mark it invalid. * * We also need to restart the busy extent search from the * tree root, because erasing the node can rearrange the * tree topology. */ rb_erase(&busyp->rb_node, &pag->pagb_tree); busyp->length = 0; return false; } else if (fend < bend) { /* * Case 6: * bbno bend * +BBBBBBBBBBBBBBBBB+ * +---------+ * fbno fend * * Case 7: * bbno bend * +BBBBBBBBBBBBBBBBB+ * +------------------+ * fbno fend * */ busyp->bno = fend; } else if (bbno < fbno) { /* * Case 8: * bbno bend * +BBBBBBBBBBBBBBBBB+ * +-------------+ * fbno fend * * Case 9: * bbno bend * +BBBBBBBBBBBBBBBBB+ * +----------------------+ * fbno fend */ busyp->length = fbno -