| // SPDX-License-Identifier: GPL-2.0 |
| /* |
| * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc. |
| * Copyright (c) 2010 David Chinner. |
| * Copyright (c) 2011 Christoph Hellwig. |
| * All Rights Reserved. |
| */ |
| #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_SLEEP); |
| 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 - busyp->bno; |
| } else { |
| ASSERT(0); |
| } |
| |
| trace_xfs_extent_busy_reuse(mp, pag->pag_agno, fbno, flen); |
| return true; |
| |
| out_force_log: |
| spin_unlock(&pag->pagb_lock); |
| xfs_log_force(mp, XFS_LOG_SYNC); |
| trace_xfs_extent_busy_force(mp, pag->pag_agno, fbno, flen); |
| spin_lock(&pag->pagb_lock); |
| return false; |
| } |
| |
| |
| /* |
| * For a given extent [fbno, flen], make sure we can reuse it safely. |
| */ |
| void |
| xfs_extent_busy_reuse( |
| struct xfs_mount *mp, |
| xfs_agnumber_t agno, |
| xfs_agblock_t fbno, |
| xfs_extlen_t flen, |
| bool userdata) |
| { |
| struct xfs_perag *pag; |
| struct rb_node *rbp; |
| |
| ASSERT(flen > 0); |
| |
| pag = xfs_perag_get(mp, agno); |
| spin_lock(&pag->pagb_lock); |
| restart: |
| rbp = pag->pagb_tree.rb_node; |
| while (rbp) { |
| struct xfs_extent_busy *busyp = |
| rb_entry(rbp, struct xfs_extent_busy, rb_node); |
| xfs_agblock_t bbno = busyp->bno; |
| xfs_agblock_t bend = bbno + busyp->length; |
| |
| if (fbno + flen <= bbno) { |
| rbp = rbp->rb_left; |
| continue; |
| } else if (fbno >= bend) { |
| rbp = rbp->rb_right; |
| continue; |
| } |
| |
| if (!xfs_extent_busy_update_extent(mp, pag, busyp, fbno, flen, |
| userdata)) |
| goto restart; |
| } |
| spin_unlock(&pag->pagb_lock); |
| xfs_perag_put(pag); |
| } |
| |
| /* |
| * For a given extent [fbno, flen], search the busy extent list to find a |
| * subset of the extent that is not busy. If *rlen is smaller than |
| * args->minlen no suitable extent could be found, and the higher level |
| * code needs to force out the log and retry the allocation. |
| * |
| * Return the current busy generation for the AG if the extent is busy. This |
| * value can be used to wait for at least one of the currently busy extents |
| * to be cleared. Note that the busy list is not guaranteed to be empty after |
| * the gen is woken. The state of a specific extent must always be confirmed |
| * with another call to xfs_extent_busy_trim() before it can be used. |
| */ |
| bool |
| xfs_extent_busy_trim( |
| struct xfs_alloc_arg *args, |
| xfs_agblock_t *bno, |
| xfs_extlen_t *len, |
| unsigned *busy_gen) |
| { |
| xfs_agblock_t fbno; |
| xfs_extlen_t flen; |
| struct rb_node *rbp; |
| bool ret = false; |
| |
| ASSERT(*len > 0); |
| |
| spin_lock(&args->pag->pagb_lock); |
| restart: |
| fbno = *bno; |
| flen = *len; |
| rbp = args->pag->pagb_tree.rb_node; |
| while (rbp && flen >= args->minlen) { |
| struct xfs_extent_busy *busyp = |
| rb_entry(rbp, struct xfs_extent_busy, rb_node); |
| xfs_agblock_t fend = fbno + flen; |
| xfs_agblock_t bbno = busyp->bno; |
| xfs_agblock_t bend = bbno + busyp->length; |
| |
| if (fend <= bbno) { |
| rbp = rbp->rb_left; |
| continue; |
| } else if (fbno >= bend) { |
| rbp = rbp->rb_right; |
| continue; |
| } |
| |
| /* |
| * If this is a metadata allocation, try to reuse the busy |
| * extent instead of trimming the allocation. |
| */ |
| if (!xfs_alloc_is_userdata(args->datatype) && |
| !(busyp->flags & XFS_EXTENT_BUSY_DISCARDED)) { |
| if (!xfs_extent_busy_update_extent(args->mp, args->pag, |
| busyp, fbno, flen, |
| false)) |
| goto restart; |
| continue; |
| } |
| |
| if (bbno <= fbno) { |
| /* start overlap */ |
| |
| /* |
| * Case 1: |
| * bbno bend |
| * +BBBBBBBBBBBBBBBBB+ |
| * +---------+ |
| * fbno fend |
| * |
| * Case 2: |
| * bbno bend |
| * +BBBBBBBBBBBBBBBBB+ |
| * +-------------+ |
| * fbno fend |
| * |
| * Case 3: |
| * bbno bend |
| * +BBBBBBBBBBBBBBBBB+ |
| * +-------------+ |
| * fbno fend |
| * |
| * Case 4: |
| * bbno bend |
| * +BBBBBBBBBBBBBBBBB+ |
| * +-----------------+ |
| * fbno fend |
| * |
| * No unbusy region in extent, return failure. |
| */ |
| if (fend <= bend) |
| goto fail; |
| |
| /* |
| * Case 5: |
| * bbno bend |
| * +BBBBBBBBBBBBBBBBB+ |
| * +----------------------+ |
| * fbno fend |
| * |
| * Case 6: |
| * bbno bend |
| * +BBBBBBBBBBBBBBBBB+ |
| * +--------------------------+ |
| * fbno fend |
| * |
| * Needs to be trimmed to: |
| * +-------+ |
| * fbno fend |
| */ |
| fbno = bend; |
| } else if (bend >= fend) { |
| /* end overlap */ |
| |
| /* |
| * Case 7: |
| * bbno bend |
| * +BBBBBBBBBBBBBBBBB+ |
| * +------------------+ |
| * fbno fend |
| * |
| * Case 8: |
| * bbno bend |
| * +BBBBBBBBBBBBBBBBB+ |
| * +--------------------------+ |
| * fbno fend |
| * |
| * Needs to be trimmed to: |
| * +-------+ |
| * fbno fend |
| */ |
| fend = bbno; |
| } else { |
| /* middle overlap */ |
| |
| /* |
| * Case 9: |
| * bbno bend |
| * +BBBBBBBBBBBBBBBBB+ |
| * +-----------------------------------+ |
| * fbno fend |
| * |
| * Can be trimmed to: |
| * +-------+ OR +-------+ |
| * fbno fend fbno fend |
| * |
| * Backward allocation leads to significant |
| * fragmentation of directories, which degrades |
| * directory performance, therefore we always want to |
| * choose the option that produces forward allocation |
| * patterns. |
| * Preferring the lower bno extent will make the next |
| * request use "fend" as the start of the next |
| * allocation; if the segment is no longer busy at |
| * that point, we'll get a contiguous allocation, but |
| * even if it is still busy, we will get a forward |
| * allocation. |
| * We try to avoid choosing the segment at "bend", |
| * because that can lead to the next allocation |
| * taking the segment at "fbno", which would be a |
| * backward allocation. We only use the segment at |
| * "fbno" if it is much larger than the current |
| * requested size, because in that case there's a |
| * good chance subsequent allocations will be |
| * contiguous. |
| */ |
| if (bbno - fbno >= args->maxlen) { |
| /* left candidate fits perfect */ |
| fend = bbno; |
| } else if (fend - bend >= args->maxlen * 4) { |
| /* right candidate has enough free space */ |
| fbno = bend; |
| } else if (bbno - fbno >= args->minlen) { |
| /* left candidate fits minimum requirement */ |
| fend = bbno; |
| } else { |
| goto fail; |
| } |
| } |
| |
| flen = fend - fbno; |
| } |
| out: |
| |
| if (fbno != *bno || flen != *len) { |
| trace_xfs_extent_busy_trim(args->mp, args->agno, *bno, *len, |
| fbno, flen); |
| *bno = fbno; |
| *len = flen; |
| *busy_gen = args->pag->pagb_gen; |
| ret = true; |
| } |
| spin_unlock(&args->pag->pagb_lock); |
| return ret; |
| fail: |
| /* |
| * Return a zero extent length as failure indications. All callers |
| * re-check if the trimmed extent satisfies the minlen requirement. |
| */ |
| flen = 0; |
| goto out; |
| } |
| |
| STATIC void |
| xfs_extent_busy_clear_one( |
| struct xfs_mount *mp, |
| struct xfs_perag *pag, |
| struct xfs_extent_busy *busyp) |
| { |
| if (busyp->length) { |
| trace_xfs_extent_busy_clear(mp, busyp->agno, busyp->bno, |
| busyp->length); |
| rb_erase(&busyp->rb_node, &pag->pagb_tree); |
| } |
| |
| list_del_init(&busyp->list); |
| kmem_free(busyp); |
| } |
| |
| static void |
| xfs_extent_busy_put_pag( |
| struct xfs_perag *pag, |
| bool wakeup) |
| __releases(pag->pagb_lock) |
| { |
| if (wakeup) { |
| pag->pagb_gen++; |
| wake_up_all(&pag->pagb_wait); |
| } |
| |
| spin_unlock(&pag->pagb_lock); |
| xfs_perag_put(pag); |
| } |
| |
| /* |
| * Remove all extents on the passed in list from the busy extents tree. |
| * If do_discard is set skip extents that need to be discarded, and mark |
| * these as undergoing a discard operation instead. |
| */ |
| void |
| xfs_extent_busy_clear( |
| struct xfs_mount *mp, |
| struct list_head *list, |
| bool do_discard) |
| { |
| struct xfs_extent_busy *busyp, *n; |
| struct xfs_perag *pag = NULL; |
| xfs_agnumber_t agno = NULLAGNUMBER; |
| bool wakeup = false; |
| |
| list_for_each_entry_safe(busyp, n, list, list) { |
| if (busyp->agno != agno) { |
| if (pag) |
| xfs_extent_busy_put_pag(pag, wakeup); |
| agno = busyp->agno; |
| pag = xfs_perag_get(mp, agno); |
| spin_lock(&pag->pagb_lock); |
| wakeup = false; |
| } |
| |
| if (do_discard && busyp->length && |
| !(busyp->flags & XFS_EXTENT_BUSY_SKIP_DISCARD)) { |
| busyp->flags = XFS_EXTENT_BUSY_DISCARDED; |
| } else { |
| xfs_extent_busy_clear_one(mp, pag, busyp); |
| wakeup = true; |
| } |
| } |
| |
| if (pag) |
| xfs_extent_busy_put_pag(pag, wakeup); |
| } |
| |
| /* |
| * Flush out all busy extents for this AG. |
| */ |
| void |
| xfs_extent_busy_flush( |
| struct xfs_mount *mp, |
| struct xfs_perag *pag, |
| unsigned busy_gen) |
| { |
| DEFINE_WAIT (wait); |
| int error; |
| |
| error = xfs_log_force(mp, XFS_LOG_SYNC); |
| if (error) |
| return; |
| |
| do { |
| prepare_to_wait(&pag->pagb_wait, &wait, TASK_KILLABLE); |
| if (busy_gen != READ_ONCE(pag->pagb_gen)) |
| break; |
| schedule(); |
| } while (1); |
| |
| finish_wait(&pag->pagb_wait, &wait); |
| } |
| |
| void |
| xfs_extent_busy_wait_all( |
| struct xfs_mount *mp) |
| { |
| DEFINE_WAIT (wait); |
| xfs_agnumber_t agno; |
| |
| for (agno = 0; agno < mp->m_sb.sb_agcount; agno++) { |
| struct xfs_perag *pag = xfs_perag_get(mp, agno); |
| |
| do { |
| prepare_to_wait(&pag->pagb_wait, &wait, TASK_KILLABLE); |
| if (RB_EMPTY_ROOT(&pag->pagb_tree)) |
| break; |
| schedule(); |
| } while (1); |
| finish_wait(&pag->pagb_wait, &wait); |
| |
| xfs_perag_put(pag); |
| } |
| } |
| |
| /* |
| * Callback for list_sort to sort busy extents by the AG they reside in. |
| */ |
| int |
| xfs_extent_busy_ag_cmp( |
| void *priv, |
| struct list_head *l1, |
| struct list_head *l2) |
| { |
| struct xfs_extent_busy *b1 = |
| container_of(l1, struct xfs_extent_busy, list); |
| struct xfs_extent_busy *b2 = |
| container_of(l2, struct xfs_extent_busy, list); |
| s32 diff; |
| |
| diff = b1->agno - b2->agno; |
| if (!diff) |
| diff = b1->bno - b2->bno; |
| return diff; |
| } |