xfs: convert list of extents to free into a regular list

In struct xfs_bmap_free, convert the open-coded free extent list to
a regular list, then use list_sort to sort it prior to processing.

Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
Reviewed-by: Dave Chinner <dchinner@redhat.com>
Signed-off-by: Dave Chinner <david@fromorbit.com>

5 files changed, 47 insertions, 44 deletions

diff --git a/fs/xfs/libxfs/xfs_bmap.c b/fs/xfs/libxfs/xfs_bmap.c
index 8847496f7ccb..2f2c85cc8117 100644
--- a/fs/xfs/libxfs/xfs_bmap.c
+++ b/fs/xfs/libxfs/xfs_bmap.c
@@ -575,9 +575,7 @@ xfs_bmap_add_free(
         xfs_fsblock_t           bno,            /* fs block number of extent */
         xfs_filblks_t           len)            /* length of extent */
 {
-        xfs_bmap_free_item_t    *cur;           /* current (next) element */
-        xfs_bmap_free_item_t    *new;           /* new element */
-        xfs_bmap_free_item_t    *prev;          /* previous element */
+        struct xfs_bmap_free_item       *new;           /* new element */
 #ifdef DEBUG
         xfs_agnumber_t          agno;
         xfs_agblock_t           agbno;
@@ -597,17 +595,7 @@ xfs_bmap_add_free(
         new = kmem_zone_alloc(xfs_bmap_free_item_zone, KM_SLEEP);
         new->xbfi_startblock = bno;
         new->xbfi_blockcount = (xfs_extlen_t)len;
-        for (prev = NULL, cur = flist->xbf_first;
-             cur != NULL;
-             prev = cur, cur = cur->xbfi_next) {
-                if (cur->xbfi_startblock >= bno)
-                        break;
-        }
-        if (prev)
-                prev->xbfi_next = new;
-        else
-                flist->xbf_first = new;
-        new->xbfi_next = cur;
+        list_add(&new->xbfi_list, &flist->xbf_flist);
         flist->xbf_count++;
 }
 
@@ -617,14 +605,10 @@ xfs_bmap_add_free(
  */
 void
 xfs_bmap_del_free(
-        xfs_bmap_free_t         *flist, /* free item list header */
-        xfs_bmap_free_item_t    *prev,  /* previous item on list, if any */
-        xfs_bmap_free_item_t    *free)  /* list item to be freed */
+        struct xfs_bmap_free            *flist, /* free item list header */
+        struct xfs_bmap_free_item       *free)  /* list item to be freed */
 {
-        if (prev)
-                prev->xbfi_next = free->xbfi_next;
-        else
-                flist->xbf_first = free->xbfi_next;
+        list_del(&free->xbfi_list);
         flist->xbf_count--;
         kmem_zone_free(xfs_bmap_free_item_zone, free);
 }
@@ -634,17 +618,16 @@ xfs_bmap_del_free(
  */
 void
 xfs_bmap_cancel(
-        xfs_bmap_free_t         *flist) /* list of bmap_free_items */
+        struct xfs_bmap_free            *flist) /* list of bmap_free_items */
 {
-        xfs_bmap_free_item_t    *free;  /* free list item */
-        xfs_bmap_free_item_t    *next;
+        struct xfs_bmap_free_item       *free;  /* free list item */
 
         if (flist->xbf_count == 0)
                 return;
-        ASSERT(flist->xbf_first != NULL);
-        for (free = flist->xbf_first; free; free = next) {
-                next = free->xbfi_next;
-                xfs_bmap_del_free(flist, NULL, free);
+        while (!list_empty(&flist->xbf_flist)) {
+                free = list_first_entry(&flist->xbf_flist,
+                                struct xfs_bmap_free_item, xbfi_list);
+                xfs_bmap_del_free(flist, free);
         }
         ASSERT(flist->xbf_count == 0);
 }
diff --git a/fs/xfs/libxfs/xfs_bmap.h b/fs/xfs/libxfs/xfs_bmap.h
index e081c7694fae..f1f3ae6c0a3f 100644
--- a/fs/xfs/libxfs/xfs_bmap.h
+++ b/fs/xfs/libxfs/xfs_bmap.h
@@ -62,12 +62,12 @@ struct xfs_bmalloca {
  * List of extents to be free "later".
  * The list is kept sorted on xbf_startblock.
  */
-typedef struct xfs_bmap_free_item
+struct xfs_bmap_free_item
 {
         xfs_fsblock_t           xbfi_startblock;/* starting fs block number */
         xfs_extlen_t            xbfi_blockcount;/* number of blocks in extent */
-        struct xfs_bmap_free_item *xbfi_next;   /* link to next entry */
-} xfs_bmap_free_item_t;
+        struct list_head        xbfi_list;
+};
 
 /*
  * Header for free extent list.
@@ -85,7 +85,7 @@ typedef struct xfs_bmap_free_item
  */
 typedef struct xfs_bmap_free
 {
-        xfs_bmap_free_item_t    *xbf_first;     /* list of to-be-free extents */
+        struct list_head        xbf_flist;      /* list of to-be-free extents */
         int                     xbf_count;      /* count of items on list */
         int                     xbf_low;        /* alloc in low mode */
 } xfs_bmap_free_t;
@@ -141,8 +141,10 @@ static inline int xfs_bmapi_aflag(int w)
 
 static inline void xfs_bmap_init(xfs_bmap_free_t *flp, xfs_fsblock_t *fbp)
 {
-        ((flp)->xbf_first = NULL, (flp)->xbf_count = 0, \
-                (flp)->xbf_low = 0, *(fbp) = NULLFSBLOCK);
+        INIT_LIST_HEAD(&flp->xbf_flist);
+        flp->xbf_count = 0;
+        flp->xbf_low = 0;
+        *fbp = NULLFSBLOCK;
 }
 
 /*
diff --git a/fs/xfs/xfs_bmap_util.c b/fs/xfs/xfs_bmap_util.c
index 586bb64e674b..c53e07a87cd7 100644
--- a/fs/xfs/xfs_bmap_util.c
+++ b/fs/xfs/xfs_bmap_util.c
@@ -79,6 +79,23 @@ xfs_zero_extent(
                 GFP_NOFS, true);
 }
 
+/* Sort bmap items by AG. */
+static int
+xfs_bmap_free_list_cmp(
+        void                    *priv,
+        struct list_head        *a,
+        struct list_head        *b)
+{
+        struct xfs_mount        *mp = priv;
+        struct xfs_bmap_free_item       *ra;
+        struct xfs_bmap_free_item       *rb;
+
+        ra = container_of(a, struct xfs_bmap_free_item, xbfi_list);
+        rb = container_of(b, struct xfs_bmap_free_item, xbfi_list);
+        return  XFS_FSB_TO_AGNO(mp, ra->xbfi_startblock) -
+                XFS_FSB_TO_AGNO(mp, rb->xbfi_startblock);
+}
+
 /*
  * Routine to be called at transaction's end by xfs_bmapi, xfs_bunmapi
  * caller.  Frees all the extents that need freeing, which must be done
@@ -99,14 +116,15 @@ xfs_bmap_finish(
         int                             error;  /* error return value */
         int                             committed;/* xact committed or not */
         struct xfs_bmap_free_item       *free;  /* free extent item */
-        struct xfs_bmap_free_item       *next;  /* next item on free list */
 
         ASSERT((*tp)->t_flags & XFS_TRANS_PERM_LOG_RES);
         if (flist->xbf_count == 0)
                 return 0;
 
+        list_sort((*tp)->t_mountp, &flist->xbf_flist, xfs_bmap_free_list_cmp);
+
         efi = xfs_trans_get_efi(*tp, flist->xbf_count);
-        for (free = flist->xbf_first; free; free = free->xbfi_next)
+        list_for_each_entry(free, &flist->xbf_flist, xbfi_list)
                 xfs_trans_log_efi_extent(*tp, efi, free->xbfi_startblock,
                         free->xbfi_blockcount);
 
@@ -138,15 +156,15 @@ xfs_bmap_finish(
          * on error.
          */
         efd = xfs_trans_get_efd(*tp, efi, flist->xbf_count);
-        for (free = flist->xbf_first; free != NULL; free = next) {
-                next = free->xbfi_next;
-
+        while (!list_empty(&flist->xbf_flist)) {
+                free = list_first_entry(&flist->xbf_flist,
+                                struct xfs_bmap_free_item, xbfi_list);
                 error = xfs_trans_free_extent(*tp, efd, free->xbfi_startblock,
                                               free->xbfi_blockcount);
                 if (error)
                         return error;
 
-                xfs_bmap_del_free(flist, NULL, free);
+                xfs_bmap_del_free(flist, free);
         }
 
         return 0;
@@ -799,7 +817,7 @@ xfs_bmap_punch_delalloc_range(
                 if (error)
                         break;
 
-                ASSERT(!flist.xbf_count && !flist.xbf_first);
+                ASSERT(!flist.xbf_count && list_empty(&flist.xbf_flist));
 next_block:
                 start_fsb++;
                 remaining--;
diff --git a/fs/xfs/xfs_bmap_util.h b/fs/xfs/xfs_bmap_util.h
index af97d9a1dfb4..4ec85d1043a0 100644
--- a/fs/xfs/xfs_bmap_util.h
+++ b/fs/xfs/xfs_bmap_util.h
@@ -43,7 +43,6 @@ int	xfs_getbmap(struct xfs_inode *ip, struct getbmapx *bmv,
 
 /* functions in xfs_bmap.c that are only needed by xfs_bmap_util.c */
 void    xfs_bmap_del_free(struct xfs_bmap_free *flist,
-                          struct xfs_bmap_free_item *prev,
                           struct xfs_bmap_free_item *free);
 int     xfs_bmap_extsize_align(struct xfs_mount *mp, struct xfs_bmbt_irec *gotp,
                                struct xfs_bmbt_irec *prevp, xfs_extlen_t extsz,
diff --git a/fs/xfs/xfs_super.c b/fs/xfs/xfs_super.c
index 2d2810851871..5f3c7299532b 100644
--- a/fs/xfs/xfs_super.c
+++ b/fs/xfs/xfs_super.c
@@ -1700,8 +1700,9 @@ xfs_init_zones(void)
         if (!xfs_log_ticket_zone)
                 goto out_free_ioend_bioset;
 
-        xfs_bmap_free_item_zone = kmem_zone_init(sizeof(xfs_bmap_free_item_t),
-                                                "xfs_bmap_free_item");
+        xfs_bmap_free_item_zone = kmem_zone_init(
+                        sizeof(struct xfs_bmap_free_item),
+                        "xfs_bmap_free_item");
         if (!xfs_bmap_free_item_zone)
                 goto out_destroy_log_ticket_zone;