From ab7bb61092308e83130b8d15725aee1672991d65 Mon Sep 17 00:00:00 2001 From: Dave Chinner Date: Wed, 29 Jul 2015 11:51:01 +1000 Subject: xfs: xfs_bunmapi() does not need XFS_BMAPI_METADATA flag xfs_bunmapi() doesn't care what type of extent is being freed and does not look at the XFS_BMAPI_METADATA flag at all. As such we can remove the XFS_BMAPI_METADATA from all callers that use it. Signed-off-by: Dave Chinner Reviewed-by: Brian Foster Signed-off-by: Dave Chinner diff --git a/fs/xfs/libxfs/xfs_attr_remote.c b/fs/xfs/libxfs/xfs_attr_remote.c index 20de88d..707362e 100644 --- a/fs/xfs/libxfs/xfs_attr_remote.c +++ b/fs/xfs/libxfs/xfs_attr_remote.c @@ -594,9 +594,8 @@ xfs_attr_rmtval_remove( xfs_bmap_init(args->flist, args->firstblock); error = xfs_bunmapi(args->trans, args->dp, lblkno, blkcnt, - XFS_BMAPI_ATTRFORK | XFS_BMAPI_METADATA, - 1, args->firstblock, args->flist, - &done); + XFS_BMAPI_ATTRFORK, 1, args->firstblock, + args->flist, &done); if (!error) { error = xfs_bmap_finish(&args->trans, args->flist, &committed); diff --git a/fs/xfs/libxfs/xfs_da_btree.c b/fs/xfs/libxfs/xfs_da_btree.c index 2385f8c..2ae91e8 100644 --- a/fs/xfs/libxfs/xfs_da_btree.c +++ b/fs/xfs/libxfs/xfs_da_btree.c @@ -2351,8 +2351,8 @@ xfs_da_shrink_inode( * the last block to the place we want to kill. */ error = xfs_bunmapi(tp, dp, dead_blkno, count, - xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA, - 0, args->firstblock, args->flist, &done); + xfs_bmapi_aflag(w), 0, args->firstblock, + args->flist, &done); if (error == -ENOSPC) { if (w != XFS_DATA_FORK) break; diff --git a/fs/xfs/libxfs/xfs_dir2.c b/fs/xfs/libxfs/xfs_dir2.c index a69fb3a..e0ba976 100644 --- a/fs/xfs/libxfs/xfs_dir2.c +++ b/fs/xfs/libxfs/xfs_dir2.c @@ -674,25 +674,22 @@ xfs_dir2_shrink_inode( mp = dp->i_mount; tp = args->trans; da = xfs_dir2_db_to_da(args->geo, db); - /* - * Unmap the fsblock(s). - */ - if ((error = xfs_bunmapi(tp, dp, da, args->geo->fsbcount, - XFS_BMAPI_METADATA, 0, args->firstblock, args->flist, - &done))) { + + /* Unmap the fsblock(s). */ + error = xfs_bunmapi(tp, dp, da, args->geo->fsbcount, 0, 0, + args->firstblock, args->flist, &done); + if (error) { /* - * ENOSPC actually can happen if we're in a removename with - * no space reservation, and the resulting block removal - * would cause a bmap btree split or conversion from extents - * to btree. This can only happen for un-fragmented - * directory blocks, since you need to be punching out - * the middle of an extent. - * In this case we need to leave the block in the file, - * and not binval it. - * So the block has to be in a consistent empty state - * and appropriately logged. - * We don't free up the buffer, the caller can tell it - * hasn't happened since it got an error back. + * ENOSPC actually can happen if we're in a removename with no + * space reservation, and the resulting block removal would + * cause a bmap btree split or conversion from extents to btree. + * This can only happen for un-fragmented directory blocks, + * since you need to be punching out the middle of an extent. + * In this case we need to leave the block in the file, and not + * binval it. So the block has to be in a consistent empty + * state and appropriately logged. We don't free up the buffer, + * the caller can tell it hasn't happened since it got an error + * back. */ return error; } diff --git a/fs/xfs/xfs_symlink.c b/fs/xfs/xfs_symlink.c index 4be27b0..05c44bf 100644 --- a/fs/xfs/xfs_symlink.c +++ b/fs/xfs/xfs_symlink.c @@ -501,7 +501,7 @@ xfs_inactive_symlink_rmt( /* * Unmap the dead block(s) to the free_list. */ - error = xfs_bunmapi(tp, ip, 0, size, XFS_BMAPI_METADATA, nmaps, + error = xfs_bunmapi(tp, ip, 0, size, 0, nmaps, &first_block, &free_list, &done); if (error) goto error_bmap_cancel; -- cgit v0.10.2 From 4703da7b78776140477a023c99683d3be84b7fca Mon Sep 17 00:00:00 2001 From: Brian Foster Date: Wed, 29 Jul 2015 11:51:01 +1000 Subject: xfs: close xc_cil list_empty() races with cil commit sequence We have seen somewhat rare reports of the following assert from xlog_cil_push_background() failing during ltp tests or somewhat innocuous desktop root fs workloads (e.g., virt operations, initramfs construction): ASSERT(!list_empty(&cil->xc_cil)); The reasoning behind the assert is that the transaction has inserted items to the CIL and hit background push codepath all with cil->xc_ctx_lock held for reading. This locks out background commit from emptying the CIL, which acquires the lock for writing. Therefore, the reasoning is that the items previously inserted in the CIL should still be present. The cil->xc_ctx_lock read lock is not sufficient to protect the xc_cil list, however, due to how CIL insertion is handled. xlog_cil_insert_items() inserts and reorders the dirty transaction items to the tail of the CIL under xc_cil_lock. It uses list_move_tail() to achieve insertion and reordering in the same block of code. This function removes and reinserts an item to the tail of the list. If a transaction commits an item that was already logged and thus already resides in the CIL, and said item is the sole item on the list, the removal and reinsertion creates a temporary state where the list is actually empty. This state is not valid and thus should never be observed by concurrent transaction commit-side checks in the circumstances outlined above. We do not want to acquire the xc_cil_lock in all of these instances as it was previously removed and replaced with a separate push lock for performance reasons. Therefore, close any races with list_empty() on the insertion side by ensuring that the list is never in a transient empty state. Signed-off-by: Brian Foster Reviewed-by: Dave Chinner Signed-off-by: Dave Chinner diff --git a/fs/xfs/xfs_log_cil.c b/fs/xfs/xfs_log_cil.c index abc2ccb..4e76493 100644 --- a/fs/xfs/xfs_log_cil.c +++ b/fs/xfs/xfs_log_cil.c @@ -307,7 +307,13 @@ xlog_cil_insert_items( if (!(lidp->lid_flags & XFS_LID_DIRTY)) continue; - list_move_tail(&lip->li_cil, &cil->xc_cil); + /* + * Only move the item if it isn't already at the tail. This is + * to prevent a transient list_empty() state when reinserting + * an item that is already the only item in the CIL. + */ + if (!list_is_last(&lip->li_cil, &cil->xc_cil)) + list_move_tail(&lip->li_cil, &cil->xc_cil); } /* account for space used by new iovec headers */ -- cgit v0.10.2 From 89cebc8477290b152618ffa110bbeae340d50900 Mon Sep 17 00:00:00 2001 From: Brian Foster Date: Wed, 29 Jul 2015 11:51:10 +1000 Subject: xfs: validate transaction header length on log recovery When log recovery hits a new transaction, it copies the transaction header from the expected location in the log to the in-core structure using the length from the op record header. This length is validated to ensure it doesn't exceed the length of the record, but not against the expected size of a transaction header (and thus the size of the in-core structure). If the on-disk length is corrupted, the associated memcpy() can overflow, write to unrelated memory and lead to crashes. This has been reproduced via filesystem fuzzing. The code currently handles the possibility that the transaction header is split across two op records. Neither instance accounts for corruption where the op record length might be larger than the in-core transaction header. Update both sites to detect such corruption, warn and return an error from log recovery. Also add some comments and assert that if the record is split, the copy of the second portion is less than a full header. Otherwise, this suggests the copy of the second portion could have overwritten bits from the first and thus that something could be wrong. Signed-off-by: Brian Foster Reviewed-by: Dave Chinner Signed-off-by: Dave Chinner diff --git a/fs/xfs/xfs_log_recover.c b/fs/xfs/xfs_log_recover.c index 01dd228..493a8ef 100644 --- a/fs/xfs/xfs_log_recover.c +++ b/fs/xfs/xfs_log_recover.c @@ -3380,14 +3380,24 @@ xlog_recover_add_to_cont_trans( char *ptr, *old_ptr; int old_len; + /* + * If the transaction is empty, the header was split across this and the + * previous record. Copy the rest of the header. + */ if (list_empty(&trans->r_itemq)) { - /* finish copying rest of trans header */ + ASSERT(len < sizeof(struct xfs_trans_header)); + if (len > sizeof(struct xfs_trans_header)) { + xfs_warn(log->l_mp, "%s: bad header length", __func__); + return -EIO; + } + xlog_recover_add_item(&trans->r_itemq); ptr = (char *)&trans->r_theader + - sizeof(xfs_trans_header_t) - len; + sizeof(struct xfs_trans_header) - len; memcpy(ptr, dp, len); return 0; } + /* take the tail entry */ item = list_entry(trans->r_itemq.prev, xlog_recover_item_t, ri_list); @@ -3436,7 +3446,19 @@ xlog_recover_add_to_trans( ASSERT(0); return -EIO; } - if (len == sizeof(xfs_trans_header_t)) + + if (len > sizeof(struct xfs_trans_header)) { + xfs_warn(log->l_mp, "%s: bad header length", __func__); + ASSERT(0); + return -EIO; + } + + /* + * The transaction header can be arbitrarily split across op + * records. If we don't have the whole thing here, copy what we + * do have and handle the rest in the next record. + */ + if (len == sizeof(struct xfs_trans_header)) xlog_recover_add_item(&trans->r_itemq); memcpy(&trans->r_theader, dp, len); return 0; -- cgit v0.10.2 From f41febd2eb5bdaa1c5685fe8a9b09276645013bc Mon Sep 17 00:00:00 2001 From: Joe Perches Date: Wed, 29 Jul 2015 11:52:04 +1000 Subject: xfs: Use consistent logging message prefixes The second and subsequent lines of multi-line logging messages are not prefixed with the same information as the first line. Separate messages with newlines into multiple calls to ensure consistent prefixing and allow easier grep use. Signed-off-by: Joe Perches Reviewed-by: Dave Chinner Signed-off-by: Dave Chinner diff --git a/fs/xfs/libxfs/xfs_dir2_node.c b/fs/xfs/libxfs/xfs_dir2_node.c index 41b80d3..d68326a 100644 --- a/fs/xfs/libxfs/xfs_dir2_node.c +++ b/fs/xfs/libxfs/xfs_dir2_node.c @@ -1845,8 +1845,7 @@ xfs_dir2_node_addname_int( if (dp->d_ops->db_to_fdb(args->geo, dbno) != fbno) { xfs_alert(mp, - "%s: dir ino %llu needed freesp block %lld for\n" - " data block %lld, got %lld ifbno %llu lastfbno %d", +"%s: dir ino %llu needed freesp block %lld for data block %lld, got %lld ifbno %llu lastfbno %d", __func__, (unsigned long long)dp->i_ino, (long long)dp->d_ops->db_to_fdb( args->geo, dbno), diff --git a/fs/xfs/libxfs/xfs_sb.c b/fs/xfs/libxfs/xfs_sb.c index df9851c..a3f4504 100644 --- a/fs/xfs/libxfs/xfs_sb.c +++ b/fs/xfs/libxfs/xfs_sb.c @@ -131,10 +131,11 @@ xfs_mount_validate_sb( if (xfs_sb_has_compat_feature(sbp, XFS_SB_FEAT_COMPAT_UNKNOWN)) { xfs_warn(mp, -"Superblock has unknown compatible features (0x%x) enabled.\n" -"Using a more recent kernel is recommended.", +"Superblock has unknown compatible features (0x%x) enabled.", (sbp->sb_features_compat & XFS_SB_FEAT_COMPAT_UNKNOWN)); + xfs_warn(mp, +"Using a more recent kernel is recommended."); } if (xfs_sb_has_ro_compat_feature(sbp, @@ -145,18 +146,21 @@ xfs_mount_validate_sb( XFS_SB_FEAT_RO_COMPAT_UNKNOWN)); if (!(mp->m_flags & XFS_MOUNT_RDONLY)) { xfs_warn(mp, -"Attempted to mount read-only compatible filesystem read-write.\n" +"Attempted to mount read-only compatible filesystem read-write."); + xfs_warn(mp, "Filesystem can only be safely mounted read only."); + return -EINVAL; } } if (xfs_sb_has_incompat_feature(sbp, XFS_SB_FEAT_INCOMPAT_UNKNOWN)) { xfs_warn(mp, -"Superblock has unknown incompatible features (0x%x) enabled.\n" -"Filesystem can not be safely mounted by this kernel.", +"Superblock has unknown incompatible features (0x%x) enabled.", (sbp->sb_features_incompat & XFS_SB_FEAT_INCOMPAT_UNKNOWN)); + xfs_warn(mp, +"Filesystem can not be safely mounted by this kernel."); return -EINVAL; } } diff --git a/fs/xfs/xfs_buf.c b/fs/xfs/xfs_buf.c index a4b7d92..d7dbd81 100644 --- a/fs/xfs/xfs_buf.c +++ b/fs/xfs/xfs_buf.c @@ -1533,9 +1533,10 @@ xfs_wait_buftarg( list_del_init(&bp->b_lru); if (bp->b_flags & XBF_WRITE_FAIL) { xfs_alert(btp->bt_mount, -"Corruption Alert: Buffer at block 0x%llx had permanent write failures!\n" -"Please run xfs_repair to determine the extent of the problem.", +"Corruption Alert: Buffer at block 0x%llx had permanent write failures!", (long long)bp->b_bn); + xfs_alert(btp->bt_mount, +"Please run xfs_repair to determine the extent of the problem."); } xfs_buf_rele(bp); } diff --git a/fs/xfs/xfs_log.c b/fs/xfs/xfs_log.c index 08d4fe4..6b5a84a 100644 --- a/fs/xfs/xfs_log.c +++ b/fs/xfs/xfs_log.c @@ -668,9 +668,9 @@ xfs_log_mount( ASSERT(0); goto out_free_log; } + xfs_crit(mp, "Log size out of supported range."); xfs_crit(mp, -"Log size out of supported range. Continuing onwards, but if log hangs are\n" -"experienced then please report this message in the bug report."); +"Continuing onwards, but if log hangs are experienced then please report this message in the bug report."); } /* @@ -1142,11 +1142,13 @@ xlog_space_left( * In this case we just want to return the size of the * log as the amount of space left. */ + xfs_alert(log->l_mp, "xlog_space_left: head behind tail"); xfs_alert(log->l_mp, - "xlog_space_left: head behind tail\n" - " tail_cycle = %d, tail_bytes = %d\n" - " GH cycle = %d, GH bytes = %d", - tail_cycle, tail_bytes, head_cycle, head_bytes); + " tail_cycle = %d, tail_bytes = %d", + tail_cycle, tail_bytes); + xfs_alert(log->l_mp, + " GH cycle = %d, GH bytes = %d", + head_cycle, head_bytes); ASSERT(0); free_bytes = log->l_logsize; } @@ -2028,26 +2030,24 @@ xlog_print_tic_res( "SWAPEXT" }; - xfs_warn(mp, - "xlog_write: reservation summary:\n" - " trans type = %s (%u)\n" - " unit res = %d bytes\n" - " current res = %d bytes\n" - " total reg = %u bytes (o/flow = %u bytes)\n" - " ophdrs = %u (ophdr space = %u bytes)\n" - " ophdr + reg = %u bytes\n" - " num regions = %u", - ((ticket->t_trans_type <= 0 || - ticket->t_trans_type > XFS_TRANS_TYPE_MAX) ? + xfs_warn(mp, "xlog_write: reservation summary:"); + xfs_warn(mp, " trans type = %s (%u)", + ((ticket->t_trans_type <= 0 || + ticket->t_trans_type > XFS_TRANS_TYPE_MAX) ? "bad-trans-type" : trans_type_str[ticket->t_trans_type-1]), - ticket->t_trans_type, - ticket->t_unit_res, - ticket->t_curr_res, - ticket->t_res_arr_sum, ticket->t_res_o_flow, - ticket->t_res_num_ophdrs, ophdr_spc, - ticket->t_res_arr_sum + - ticket->t_res_o_flow + ophdr_spc, - ticket->t_res_num); + ticket->t_trans_type); + xfs_warn(mp, " unit res = %d bytes", + ticket->t_unit_res); + xfs_warn(mp, " current res = %d bytes", + ticket->t_curr_res); + xfs_warn(mp, " total reg = %u bytes (o/flow = %u bytes)", + ticket->t_res_arr_sum, ticket->t_res_o_flow); + xfs_warn(mp, " ophdrs = %u (ophdr space = %u bytes)", + ticket->t_res_num_ophdrs, ophdr_spc); + xfs_warn(mp, " ophdr + reg = %u bytes", + ticket->t_res_arr_sum + ticket->t_res_o_flow + ophdr_spc); + xfs_warn(mp, " num regions = %u", + ticket->t_res_num); for (i = 0; i < ticket->t_res_num; i++) { uint r_type = ticket->t_res_arr[i].r_type; diff --git a/fs/xfs/xfs_log_recover.c b/fs/xfs/xfs_log_recover.c index 493a8ef..8b00730 100644 --- a/fs/xfs/xfs_log_recover.c +++ b/fs/xfs/xfs_log_recover.c @@ -4549,11 +4549,13 @@ xlog_recover( xfs_sb_has_incompat_log_feature(&log->l_mp->m_sb, XFS_SB_FEAT_INCOMPAT_LOG_UNKNOWN)) { xfs_warn(log->l_mp, -"Superblock has unknown incompatible log features (0x%x) enabled.\n" -"The log can not be fully and/or safely recovered by this kernel.\n" -"Please recover the log on a kernel that supports the unknown features.", +"Superblock has unknown incompatible log features (0x%x) enabled.", (log->l_mp->m_sb.sb_features_log_incompat & XFS_SB_FEAT_INCOMPAT_LOG_UNKNOWN)); + xfs_warn(log->l_mp, +"The log can not be fully and/or safely recovered by this kernel."); + xfs_warn(log->l_mp, +"Please recover the log on a kernel that supports the unknown features."); return -EINVAL; } -- cgit v0.10.2 From d6077aa339d6580d12bd1089231eea2940383e32 Mon Sep 17 00:00:00 2001 From: Jan Kara Date: Wed, 29 Jul 2015 11:52:08 +1000 Subject: xfs: Remove duplicate jumps to the same label xfs_create() and xfs_create_tmpfile() have useless jumps to identical labels. Simplify them. Signed-off-by: Jan Kara Reviewed-by: Dave Chinner Signed-off-by: Dave Chinner diff --git a/fs/xfs/xfs_inode.c b/fs/xfs/xfs_inode.c index 3da9f4d..d22a984 100644 --- a/fs/xfs/xfs_inode.c +++ b/fs/xfs/xfs_inode.c @@ -1175,11 +1175,8 @@ xfs_create( */ error = xfs_dir_ialloc(&tp, dp, mode, is_dir ? 2 : 1, rdev, prid, resblks > 0, &ip, &committed); - if (error) { - if (error == -ENOSPC) - goto out_trans_cancel; + if (error) goto out_trans_cancel; - } /* * Now we join the directory inode to the transaction. We do not do it @@ -1318,11 +1315,8 @@ xfs_create_tmpfile( error = xfs_dir_ialloc(&tp, dp, mode, 1, 0, prid, resblks > 0, &ip, NULL); - if (error) { - if (error == -ENOSPC) - goto out_trans_cancel; + if (error) goto out_trans_cancel; - } if (mp->m_flags & XFS_MOUNT_WSYNC) xfs_trans_set_sync(tp); -- cgit v0.10.2 From 1cfc4a9cf89d23727c6678170aa5949a676fc566 Mon Sep 17 00:00:00 2001 From: Dave Chinner Date: Wed, 29 Jul 2015 11:52:08 +1000 Subject: libxfs: add xfs_bit.c The header side of xfs_bit.c is already in libxfs, and the sparse inode code requires the xfs_next_bit() function so pull in the xfs_bit.c file so that a sparse inode enabled libxfs compiles cleanly in userspace. Signed-off-by: Dave Chinner Reviewed-by: Brian Foster Signed-off-by: Dave Chinner diff --git a/fs/xfs/Makefile b/fs/xfs/Makefile index df68285..a096841 100644 --- a/fs/xfs/Makefile +++ b/fs/xfs/Makefile @@ -33,6 +33,7 @@ xfs-y += $(addprefix libxfs/, \ xfs_attr.o \ xfs_attr_leaf.o \ xfs_attr_remote.o \ + xfs_bit.o \ xfs_bmap.o \ xfs_bmap_btree.o \ xfs_btree.o \ @@ -63,7 +64,6 @@ xfs-$(CONFIG_XFS_RT) += $(addprefix libxfs/, \ xfs-y += xfs_aops.o \ xfs_attr_inactive.o \ xfs_attr_list.o \ - xfs_bit.o \ xfs_bmap_util.o \ xfs_buf.o \ xfs_dir2_readdir.o \ diff --git a/fs/xfs/libxfs/xfs_bit.c b/fs/xfs/libxfs/xfs_bit.c new file mode 100644 index 0000000..0e8885a --- /dev/null +++ b/fs/xfs/libxfs/xfs_bit.c @@ -0,0 +1,118 @@ +/* + * Copyright (c) 2000-2005 Silicon Graphics, Inc. + * 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_log_format.h" +#include "xfs_bit.h" + +/* + * XFS bit manipulation routines, used in non-realtime code. + */ + +/* + * Return whether bitmap is empty. + * Size is number of words in the bitmap, which is padded to word boundary + * Returns 1 for empty, 0 for non-empty. + */ +int +xfs_bitmap_empty(uint *map, uint size) +{ + uint i; + uint ret = 0; + + for (i = 0; i < size; i++) { + ret |= map[i]; + } + + return (ret == 0); +} + +/* + * Count the number of contiguous bits set in the bitmap starting with bit + * start_bit. Size is the size of the bitmap in words. + */ +int +xfs_contig_bits(uint *map, uint size, uint start_bit) +{ + uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT); + uint result = 0; + uint tmp; + + size <<= BIT_TO_WORD_SHIFT; + + ASSERT(start_bit < size); + size -= start_bit & ~(NBWORD - 1); + start_bit &= (NBWORD - 1); + if (start_bit) { + tmp = *p++; + /* set to one first offset bits prior to start */ + tmp |= (~0U >> (NBWORD-start_bit)); + if (tmp != ~0U) + goto found; + result += NBWORD; + size -= NBWORD; + } + while (size) { + if ((tmp = *p++) != ~0U) + goto found; + result += NBWORD; + size -= NBWORD; + } + return result - start_bit; +found: + return result + ffz(tmp) - start_bit; +} + +/* + * This takes the bit number to start looking from and + * returns the next set bit from there. It returns -1 + * if there are no more bits set or the start bit is + * beyond the end of the bitmap. + * + * Size is the number of words, not bytes, in the bitmap. + */ +int xfs_next_bit(uint *map, uint size, uint start_bit) +{ + uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT); + uint result = start_bit & ~(NBWORD - 1); + uint tmp; + + size <<= BIT_TO_WORD_SHIFT; + + if (start_bit >= size) + return -1; + size -= result; + start_bit &= (NBWORD - 1); + if (start_bit) { + tmp = *p++; + /* set to zero first offset bits prior to start */ + tmp &= (~0U << start_bit); + if (tmp != 0U) + goto found; + result += NBWORD; + size -= NBWORD; + } + while (size) { + if ((tmp = *p++) != 0U) + goto found; + result += NBWORD; + size -= NBWORD; + } + return -1; +found: + return result + ffs(tmp) - 1; +} diff --git a/fs/xfs/xfs_bit.c b/fs/xfs/xfs_bit.c deleted file mode 100644 index 0e8885a..0000000 --- a/fs/xfs/xfs_bit.c +++ /dev/null @@ -1,118 +0,0 @@ -/* - * Copyright (c) 2000-2005 Silicon Graphics, Inc. - * 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_log_format.h" -#include "xfs_bit.h" - -/* - * XFS bit manipulation routines, used in non-realtime code. - */ - -/* - * Return whether bitmap is empty. - * Size is number of words in the bitmap, which is padded to word boundary - * Returns 1 for empty, 0 for non-empty. - */ -int -xfs_bitmap_empty(uint *map, uint size) -{ - uint i; - uint ret = 0; - - for (i = 0; i < size; i++) { - ret |= map[i]; - } - - return (ret == 0); -} - -/* - * Count the number of contiguous bits set in the bitmap starting with bit - * start_bit. Size is the size of the bitmap in words. - */ -int -xfs_contig_bits(uint *map, uint size, uint start_bit) -{ - uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT); - uint result = 0; - uint tmp; - - size <<= BIT_TO_WORD_SHIFT; - - ASSERT(start_bit < size); - size -= start_bit & ~(NBWORD - 1); - start_bit &= (NBWORD - 1); - if (start_bit) { - tmp = *p++; - /* set to one first offset bits prior to start */ - tmp |= (~0U >> (NBWORD-start_bit)); - if (tmp != ~0U) - goto found; - result += NBWORD; - size -= NBWORD; - } - while (size) { - if ((tmp = *p++) != ~0U) - goto found; - result += NBWORD; - size -= NBWORD; - } - return result - start_bit; -found: - return result + ffz(tmp) - start_bit; -} - -/* - * This takes the bit number to start looking from and - * returns the next set bit from there. It returns -1 - * if there are no more bits set or the start bit is - * beyond the end of the bitmap. - * - * Size is the number of words, not bytes, in the bitmap. - */ -int xfs_next_bit(uint *map, uint size, uint start_bit) -{ - uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT); - uint result = start_bit & ~(NBWORD - 1); - uint tmp; - - size <<= BIT_TO_WORD_SHIFT; - - if (start_bit >= size) - return -1; - size -= result; - start_bit &= (NBWORD - 1); - if (start_bit) { - tmp = *p++; - /* set to zero first offset bits prior to start */ - tmp &= (~0U << start_bit); - if (tmp != 0U) - goto found; - result += NBWORD; - size -= NBWORD; - } - while (size) { - if ((tmp = *p++) != 0U) - goto found; - result += NBWORD; - size -= NBWORD; - } - return -1; -found: - return result + ffs(tmp) - 1; -} -- cgit v0.10.2