aboutsummaryrefslogtreecommitdiff
path: root/fs/xfs/xfs_bmap_btree.c
AgeCommit message (Collapse)Author
2008-07-28[XFS] Allow xfs_bmbt_split() to fallback to the lowspace allocatorLachlan McIlroy
algorithm If xfs_bmbt_split() cannot find an AG with sufficient free space to satisfy a full extent btree split then fall back to the lowspace allocator algorithm. SGI-PV: 983338 SGI-Modid: xfs-linux-melb:xfs-kern:31359a Signed-off-by: Lachlan McIlroy <lachlan@sgi.com> Signed-off-by: David Chinner <dgc@sgi.com>
2008-07-28[XFS] Restore the lowspace extent allocator algorithmLachlan McIlroy
When free space is running low the extent allocator may choose to allocate an extent from an AG without leaving sufficient space for a btree split when inserting the new extent (see where xfs_bmap_btalloc() sets minleft to 0). In this case the allocator will enable the lowspace algorithm which is supposed to allow further allocations (such as btree splits and newroots) to allocate from sequential AGs. This algorithm has been broken for a long time and this patch restores its behaviour. SGI-PV: 983338 SGI-Modid: xfs-linux-melb:xfs-kern:31358a Signed-off-by: Lachlan McIlroy <lachlan@sgi.com> Signed-off-by: David Chinner <dgc@sgi.com>
2008-07-28[XFS] use minleft when allocating in xfs_bmbt_split()Lachlan McIlroy
The bmap btree split code relies on a previous data extent allocation (from xfs_bmap_btalloc()) to find an AG that has sufficient space to perform a full btree split, when inserting the extent. When converting unwritten extents we don't allocate a data extent so a btree split will be the first allocation. In this case we need to set minleft so the allocator will pick an AG that has space to complete the split(s). SGI-PV: 983338 SGI-Modid: xfs-linux-melb:xfs-kern:31357a Signed-off-by: Lachlan McIlroy <lachlan@sgi.com> Signed-off-by: David Chinner <dgc@sgi.com>
2008-07-28[XFS] Always reset btree cursor after an insertLachlan McIlroy
After a btree insert operation a cursor can be invalid due to block splits and a maybe a new root block. We reset the cursor in xfs_bmbt_insert() in the cases where we think we need to but it isn't enough as we still see assertions. Just do what we do elsewhere and reset the cursor unconditionally. Also remove the fix to revalidate the original cursor in xfs_bmbt_insert(). SGI-PV: 983336 SGI-Modid: xfs-linux-melb:xfs-kern:31342a Signed-off-by: Lachlan McIlroy <lachlan@sgi.com> Signed-off-by: David Chinner <dgc@sgi.com>
2008-04-18[XFS] replace remaining __FUNCTION__ occurrencesHarvey Harrison
__FUNCTION__ is gcc-specific, use __func__ SGI-PV: 976035 SGI-Modid: xfs-linux-melb:xfs-kern:30775a Signed-off-by: Harvey Harrison <harvey.harrison@gmail.com> Signed-off-by: David Chinner <dgc@sgi.com> Signed-off-by: Lachlan McIlroy <lachlan@sgi.com>
2008-04-18[XFS] Ensure a btree insert returns a valid cursor.David Chinner
When writing into preallocated regions there is a case where XFS can oops or hang doing the unwritten extent conversion on I/O completion. It turns out that the problem is related to the btree cursor being invalid. When we do an insert into the tree, we may need to split blocks in the tree. When we only split at the leaf level (i.e. level 0), everything works just fine. However, if we have a multi-level split in the btreee, the cursor passed to the insert function is no longer valid once the insert is complete. The leaf level split is handled correctly because all the operations at level 0 are done using the original cursor, hence it is updated correctly. However, when we need to update the next level up the tree, we don't use that cursor - we use a cloned cursor that points to the index in the next level up where we need to do the insert. Hence if we need to split a second level, the changes to the tree are reflected in the cloned cursor and not the original cursor. This clone-and-move-up-a-level-on-split behaviour recurses all the way to the top of the tree. The complexity here is that these cloned cursors do not point to the original index that was inserted - they point to the newly allocated block (the right block) and the original cursor pointer to that level may still point to the left block. Hence, without deep examination of the cloned cursor and buffers, we cannot update the original cursor with the new path from the cloned cursor. In these cases the original cursor could be pointing to the wrong block(s) and hence a subsequent modification to the tree using that cursor will lead to corruption of the tree. The crash case occurs when the tree changes height - we insert a new level in the tree, and the cursor does not have a buffer in it's path for that level. Hence any attempt to walk back up the cursor to the root block will result in a null pointer dereference. To make matters even more complex, the BMAP BT is rooted in an inode, so we can have a change of height in the btree *without a root split*. That is, if the root block in the inode is full when we split a leaf node, we cannot fit the pointer to the new block in the root, so we allocate a new block, migrate all the ptrs out of the inode into the new block and point the inode root block at the newly allocated block. This changes the height of the tree without a root split having occurred and hence invalidates the path in the original cursor. The patch below prevents xfs_bmbt_insert() from returning with an invalid cursor by detecting the cases that invalidate the original cursor and refresh it by do a lookup into the btree for the original index we were inserting at. Note that the INOBT, AGFBNO and AGFCNT btree implementations also have this bug, but the cursor is currently always destroyed or revalidated after an insert for those trees. Hence this patch only address the problem in the BMBT code. SGI-PV: 979339 SGI-Modid: xfs-linux-melb:xfs-kern:30701a Signed-off-by: David Chinner <dgc@sgi.com> Signed-off-by: Lachlan McIlroy <lachlan@sgi.com>
2008-02-13xfs: convert beX_add to beX_add_cpu (new common API)Marcin Slusarz
remove beX_add functions and replace all uses with beX_add_cpu Signed-off-by: Marcin Slusarz <marcin.slusarz@gmail.com> Cc: Mark Fasheh <mark.fasheh@oracle.com> Reviewed-by: Dave Chinner <dgc@sgi.com> Cc: Timothy Shimmin <tes@sgi.com> Cc: <linux-ext4@vger.kernel.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2008-02-07[XFS] optimize XFS_IS_REALTIME_INODE w/o realtime configEric Sandeen
Use XFS_IS_REALTIME_INODE in more places, and #define it to 0 if CONFIG_XFS_RT is off. This should be safe because mount checks in xfs_rtmount_init: so if we get mounted w/o CONFIG_XFS_RT, no realtime inodes should be encountered after that. Defining XFS_IS_REALTIME_INODE to 0 saves a bit of stack space, presumeably gcc can optimize around the various "if (0)" type checks: xfs_alloc_file_space -8 xfs_bmap_adjacent -16 xfs_bmapi -8 xfs_bmap_rtalloc -16 xfs_bunmapi -28 xfs_free_file_space -64 xfs_imap +8 <-- ? hmm. xfs_iomap_write_direct -12 xfs_qm_dqusage_adjust -4 xfs_qm_vop_chown_reserve -4 SGI-PV: 971186 SGI-Modid: xfs-linux-melb:xfs-kern:30014a Signed-off-by: Eric Sandeen <sandeen@sandeen.net> Signed-off-by: David Chinner <dgc@sgi.com> Signed-off-by: Lachlan McIlroy <lachlan@sgi.com>
2007-10-15[XFS] Fix build regression from mod/commit which did cleanup of ↵Michal Piotrowski
xfs_bmbt_*set_allf In sgi mod# xfs-linux-melb:xfs-kern:29319a, the variable renaming was not complete and variable 'b' was left unchanged for non-lbd 32 bit machines. SGI-PV: 968563 SGI-Modid: xfs-linux-melb:xfs-kern:29469a Signed-off-by: Michal Piotrowski <michal.k.k.piotrowski@gmail.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2007-10-15[XFS] endianess annotations for xfs_bmbt_rec_tChristoph Hellwig
SGI-PV: 968563 SGI-Modid: xfs-linux-melb:xfs-kern:29321a Signed-off-by: Christoph Hellwig <hch@infradead.org> Signed-off-by: David Chinner <dgc@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2007-10-15[XFS] clean up xfs_bmbt_set_all/xfs_bmbt_disk_set_allChristoph Hellwig
xfs_bmbt_set_all/xfs_bmbt_disk_set_all are identical to xfs_bmbt_set_allf/xfs_bmbt_disk_set_allf except that the former take a xfs_bmbt_irec_t and the latter take the individual extent fields as scalar values. This patch reimplements xfs_bmbt_set_all/xfs_bmbt_disk_set_all as trivial wrappers around xfs_bmbt_set_allf/xfs_bmbt_disk_set_allf and cleans up the variable naming in xfs_bmbt_set_allf/xfs_bmbt_disk_set_allf to have some meaning instead of one char variable names. SGI-PV: 968563 SGI-Modid: xfs-linux-melb:xfs-kern:29319a Signed-off-by: Christoph Hellwig <hch@infradead.org> Signed-off-by: David Chinner <dgc@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2007-10-15[XFS] split ondisk vs incore versions of xfs_bmbt_rec_tChristoph Hellwig
currently xfs_bmbt_rec_t is used both for ondisk extents as well as host-endian ones. This patch adds a new xfs_bmbt_rec_host_t for the native endian ones and cleans up the fallout. There have been various endianess issues in the tracing / debug printf code that are fixed by this patch. SGI-PV: 968563 SGI-Modid: xfs-linux-melb:xfs-kern:29318a Signed-off-by: Christoph Hellwig <hch@infradead.org> Signed-off-by: David Chinner <dgc@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2007-10-15[XFS] remove confusing INT_ comments in xfs_bmap_btree.cChristoph Hellwig
SGI-PV: 968563 SGI-Modid: xfs-linux-melb:xfs-kern:29317a Signed-off-by: Christoph Hellwig <hch@infradead.org> Signed-off-by: David Chinner <dgc@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2007-07-14[XFS] Clean up function name handling in tracing codeEric Sandeen
Remove the hardcoded "fnames" for tracing, and just embed them in tracing macros via __FUNCTION__. Kills a lot of #ifdefs too. SGI-PV: 967353 SGI-Modid: xfs-linux-melb:xfs-kern:29099a Signed-off-by: Eric Sandeen <sandeen@sandeen.net> Signed-off-by: David Chinner <dgc@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2007-02-10[XFS] Remove a bunch of unused functions from XFS.Eric Sandeen
Patch provided by Eric Sandeen (sandeen@sandeen.net). SGI-PV: 960897 SGI-Modid: xfs-linux-melb:xfs-kern:28038a Signed-off-by: Eric Sandeen <sandeen@sandeen.net> Signed-off-by: David Chinner <dgc@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2007-02-10[XFS] Remove unused arguments from the XFS_BTREE_*_ADDR macros.Eric Sandeen
It makes it incrementally clearer to read the code when the top of a macro spaghetti-pile only receives the 3 arguments it uses, rather than 2 extra ones which are not used. Also when you start pulling this thread out of the sweater (i.e. remove unused args from XFS_BTREE_*_ADDR), a couple other third arms etc fall off too. If they're not used in the macro, then they sometimes don't need to be passed to the function calling the macro either, etc.... Patch provided by Eric Sandeen (sandeen@sandeen.net). SGI-PV: 960197 SGI-Modid: xfs-linux-melb:xfs-kern:28037a Signed-off-by: Eric Sandeen <sandeen@sandeen.net> Signed-off-by: David Chinner <dgc@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2007-02-10[XFS] Keep stack usage down for 4k stacks by using noinline.David Chinner
gcc-4.1 and more recent aggressively inline static functions which increases XFS stack usage by ~15% in critical paths. Prevent this from occurring by adding noinline to the STATIC definition. Also uninline some functions that are too large to be inlined and were causing problems with CONFIG_FORCED_INLINING=y. Finally, clean up all the different users of inline, __inline and __inline__ and put them under one STATIC_INLINE macro. For debug kernels the STATIC_INLINE macro uninlines those functions. SGI-PV: 957159 SGI-Modid: xfs-linux-melb:xfs-kern:27585a Signed-off-by: David Chinner <dgc@sgi.com> Signed-off-by: David Chatterton <chatz@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2006-09-28[XFS] use NULL for pointer initialisation instead of zero-cast-to-ptrNathan Scott
SGI-PV: 954580 SGI-Modid: xfs-linux-melb:xfs-kern:26562a Signed-off-by: Nathan Scott <nathans@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2006-09-28[XFS] endianess annotations for xfs_bmbt_key Trivial as there are noChristoph Hellwig
incore users. SGI-PV: 954580 SGI-Modid: xfs-linux-melb:xfs-kern:26561a Signed-off-by: Christoph Hellwig <hch@lst.de> Signed-off-by: Nathan Scott <nathans@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2006-09-28[XFS] endianess annotate XFS_BMAP_BROOT_PTR_ADDR Make sure it returns aChristoph Hellwig
__be64 and let the callers use the proper macros. SGI-PV: 954580 SGI-Modid: xfs-linux-melb:xfs-kern:26560a Signed-off-by: Christoph Hellwig <hch@lst.de> Signed-off-by: Nathan Scott <nathans@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2006-09-28[XFS] add xfs_btree_check_lptr_disk variant which handles endianChristoph Hellwig
conversion SGI-PV: 954580 SGI-Modid: xfs-linux-melb:xfs-kern:26558a Signed-off-by: Christoph Hellwig <hch@lst.de> Signed-off-by: Nathan Scott <nathans@sgi.com> Signed-off-by: Tim Shimmin <tes@sgi.com>
2006-06-20[XFS] Remove version 1 directory code. Never functioned on Linux, justNathan Scott
pure bloat. SGI-PV: 952969 SGI-Modid: xfs-linux-melb:xfs-kern:26251a Signed-off-by: Nathan Scott <nathans@sgi.com>
2006-06-09[XFS] In actual allocation of file system blocks and freeing extents, theYingping Lu
transaction within each such operation may involve multiple locking of AGF buffer. While the freeing extent function has sorted the extents based on AGF number before entering into transaction, however, when the file system space is very limited, the allocation of space would try every AGF to get space allocated, this could potentially cause out-of-order locking, thus deadlock could happen. This fix mitigates the scarce space for allocation by setting aside a few blocks without reservation, and avoid deadlock by maintaining ascending order of AGF locking. SGI-PV: 947395 SGI-Modid: xfs-linux-melb:xfs-kern:210801a Signed-off-by: Yingping Lu <yingping@sgi.com> Signed-off-by: Nathan Scott <nathans@sgi.com>
2006-03-14[XFS] 929045 567344 This mod re-organizes some of the in-core file extentMandy Kirkconnell
code to prepare for an upcoming mod which will introduce multi-level in-core extent allocations. Although the in-core extent management is using a new code path in this mod, the functionality remains the same. Major changes include: - Introduce 10 new subroutines which re-orgainze the existing code but do NOT change functionality: xfs_iext_get_ext() xfs_iext_insert() xfs_iext_add() xfs_iext_remove() xfs_iext_remove_inline() xfs_iext_remove_direct() xfs_iext_realloc_direct() xfs_iext_direct_to_inline() xfs_iext_inline_to_direct() xfs_iext_destroy() - Remove 2 subroutines (functionality moved to new subroutines above): xfs_iext_realloc() -replaced by xfs_iext_add() and xfs_iext_remove() xfs_bmap_insert_exlist() - replaced by xfs_iext_insert() xfs_bmap_delete_exlist() - replaced by xfs_iext_remove() - Replace all hard-coded (indexed) extent assignments with a call to xfs_iext_get_ext() - Replace all extent record pointer arithmetic (ep++, ep--, base + lastx,..) with calls to xfs_iext_get_ext() - Update comments to remove the idea of a single "extent list" and introduce "extent record" terminology instead SGI-PV: 928864 SGI-Modid: xfs-linux-melb:xfs-kern:207390a Signed-off-by: Mandy Kirkconnell <alkirkco@sgi.com> Signed-off-by: Nathan Scott <nathans@sgi.com>
2005-11-02[XFS] Endianess annotations for various allocator data structuresChristoph Hellwig
SGI-PV: 943272 SGI-Modid: xfs-linux:xfs-kern:201006a Signed-off-by: Christoph Hellwig <hch@sgi.com> Signed-off-by: Nathan Scott <nathans@sgi.com>
2005-11-02[XFS] Update license/copyright notices to match the prefered SGINathan Scott
boilerplate. SGI-PV: 913862 SGI-Modid: xfs-linux:xfs-kern:23903a Signed-off-by: Nathan Scott <nathans@sgi.com>
2005-11-02[XFS] Remove xfs_macros.c, xfs_macros.h, rework headers a whole lot.Nathan Scott
SGI-PV: 943122 SGI-Modid: xfs-linux:xfs-kern:23901a Signed-off-by: Nathan Scott <nathans@sgi.com>
2005-09-08[XFS] Cleanup some -Wundef flag warnings in the endian macros (thanksNathan Scott
Christoph). SGI-PV: 942400 SGI-Modid: xfs-linux-melb:xfs-kern:23771a Signed-off-by: Nathan Scott <nathans@sgi.com>
2005-06-21[XFS] Remove dead code. Patch from Adrian BunkChristoph Hellwig
SGI-PV: 936255 SGI-Modid: xfs-linux:xfs-kern:192759a Signed-off-by: Christoph Hellwig <hch@sgi.com> Signed-off-by: Nathan Scott <nathans@sgi.com>
2005-04-16Linux-2.6.12-rc2Linus Torvalds
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!