implement generic xfs_btree_lshift
PATCH 16/21 implement generic xfs_btree_lshift
Make the btree left shift code generic. Based on a patch from David Chinner with lots of changes to follow the original btree implementations more closely. While this loses some of the generic helper routines for inserting/moving/removing records it also solves some of the one off bugs in the original code and makes it easier to verify.
fs/xfs/xfs_btree.c +197 -0
@@ -976,6 +976,21 @@ xfs_btree_move_ptrs( } } +STATIC void +xfs_btree_copy_ptrs ( +struct xfs_btree_cur *cur, +union xfs_btree_ptr *src_ptr, +union xfs_btree_ptr *dst_ptr, +int numptrs) +{ +ASSERT (numptrs >0 ); + +if (cur->bc_flags &XFS_BTREE_LONG_PTRS ) +memcpy (dst_ptr, src_ptr, numptrs *sizeof (__be64)); +else +memcpy (dst_ptr, src_ptr, numptrs *sizeof (__be32)); +} +/* * Log block pointer fields from a btree block (nonleaf). */
@@ -1597,6 +1612,188 @@ error0: }/* +* Move 1 record left from cur/level if possible. +* Update cur to reflect the new path. +*/ +int /* error */ +xfs_btree_lshift ( +struct xfs_btree_cur *cur, +int level, +int *stat)/* success/failure */ +{ +union xfs_btree_key key;/* btree key */ +struct xfs_buf *lbp;/* left buffer pointer */ +struct xfs_btree_block *left;/* left btree block */ +int lrecs;/* left record count */ +struct xfs_buf *rbp;/* right buffer pointer */ +struct xfs_btree_block *right;/* right btree block */ +int rrecs;/* right record count */ +union xfs_btree_ptr lptr;/* left btree pointer */ +union xfs_btree_key *rkp =NULL ;/* right btree key */ +union xfs_btree_ptr *rpp =NULL ;/* right address pointer */ +union xfs_btree_rec *rrp =NULL ;/* right record pointer */ +int error;/* error return value */ +#ifdef DEBUG +int i;/* loop index */ +#endif + +XFS_BTREE_TRACE_CURSOR (cur,XBT_ENTRY ); +XFS_BTREE_TRACE_ARGI (cur, level); + +if ((cur->bc_flags &XFS_BTREE_ROOT_IN_INODE ) && + level == cur->bc_nlevels -1 ) + goto out0; + +/* Set up variables for this block as "right". */ + right =xfs_btree_get_block (cur, level, &rbp); + +#ifdef DEBUG + error =xfs_btree_check_block (cur, right, level, rbp); +if (error) + goto error0; +#endif + +/* If we've got no left sibling then we can't shift an entry left. */ +xfs_btree_get_sibling (cur, right, &lptr,XFS_BB_LEFTSIB ); +if (xfs_btree_ptr_is_null (cur, &lptr)) + goto out0; + +/* +* If the cursor entry is the one that would be moved, don't +* do it... it's too complicated. +*/ +if (cur->bc_ptrs[level] <=1 ) + goto out0; + +/* Set up the left neighbor as "left". */ + error =xfs_btree_read_buf_block (cur, &lptr, level,0 , &left, &lbp); +if (error) + goto error0; + +/* If it's full, it can't take another entry. */ + lrecs =xfs_btree_get_numrecs (left); +if (lrecs == cur->bc_ops->get_maxrecs (cur, level)) + goto out0; + + rrecs =xfs_btree_get_numrecs (right); + +/* +* We add one entry to the left side and remove one for the right side. +* Accout for it here, the changes will be updated on disk and logged +* later. +*/ + lrecs++; + rrecs--; + +XFS_BTREE_STATS_INC (cur, lshift); + +/* +* If non-leaf, copy a key and a ptr to the left block. +* Log the changes to the left block. +*/ +XFS_BTREE_STATS_ADD (cur, moves,1 ); +if (level >0 ) { +/* It's a non-leaf. Move keys and pointers. */ +union xfs_btree_key *lkp;/* left btree key */ +union xfs_btree_ptr *lpp;/* left address pointer */ + + lkp = cur->bc_ops->key_addr (cur, lrecs, left); + rkp = cur->bc_ops->key_addr (cur,1 , right); + + lpp = cur->bc_ops->ptr_addr (cur, lrecs, left); + rpp = cur->bc_ops->ptr_addr (cur,1 , right); +#ifdef DEBUG + error =xfs_btree_check_ptr (cur, rpp,0 , level); +if (error) + goto error0; +#endif + cur->bc_ops->copy_keys (cur, rkp, lkp,1 ); +xfs_btree_copy_ptrs (cur, rpp, lpp,1 ); + + cur->bc_ops->log_keys (cur, lbp, lrecs, lrecs); +xfs_btree_log_ptrs (cur, lbp, lrecs, lrecs); + +xfs_btree_check_key (cur->bc_btnum, + cur->bc_ops->key_addr (cur, lrecs -1 , left), + lkp); + }else { +/* It's a leaf. Move records. */ +union xfs_btree_rec *lrp;/* left record pointer */ + + lrp = cur->bc_ops->rec_addr (cur, lrecs, left); + rrp = cur->bc_ops->rec_addr (cur,1 , right); + + cur->bc_ops->copy_recs (cur, rrp, lrp,1 ); + cur->bc_ops->log_recs (cur, lbp, lrecs, lrecs); + +xfs_btree_check_rec (cur->bc_btnum, + cur->bc_ops->rec_addr (cur, lrecs -1 , left), + lrp); + } + +xfs_btree_set_numrecs (left, lrecs); +xfs_btree_log_block (cur, lbp,XFS_BB_NUMRECS ); + +xfs_btree_set_numrecs (right, rrecs); +xfs_btree_log_block (cur, rbp,XFS_BB_NUMRECS ); + +/* +* Slide the contents of right down one entry. +*/ +XFS_BTREE_STATS_ADD (cur, moves, rrecs -1 ); +if (level >0 ) { +/* It's a nonleaf. operate on keys and ptrs */ + +#ifdef DEBUG +for (i =0 ; i < rrecs; i++) { + error =xfs_btree_check_ptr (cur, rpp, i +1 , level); +if (error) + goto error0; + } +#endif + + cur->bc_ops->move_keys (cur, rkp,1 ,0 , rrecs); +xfs_btree_move_ptrs (cur, rpp,1 ,0 , rrecs); + cur->bc_ops->log_keys (cur, rbp,1 , rrecs); +xfs_btree_log_ptrs (cur, rbp,1 , rrecs); + }else { +/* It's a leaf. operate on records */ + + rrp = cur->bc_ops->rec_addr (cur,1 , right); + cur->bc_ops->move_recs (cur, rrp,1 ,0 , rrecs); + cur->bc_ops->log_recs (cur, rbp,1 , rrecs); + +/* +* If it's the first record in the block, we'll need a key +* structure to pass up to the next level (updkey). +*/ + cur->bc_ops->init_key_from_rec (cur, &key, rrp); + rkp = &key; + } + +/* Update the parent key values of right. */ + error =xfs_btree_updkey (cur, rkp, level +1 ); +if (error) + goto error0; + +/* Slide the cursor value left one. */ + cur->bc_ptrs[level]--; + +XFS_BTREE_TRACE_CURSOR (cur,XBT_EXIT ); + *stat =1 ; +return 0 ; + +out0: +XFS_BTREE_TRACE_CURSOR (cur,XBT_EXIT ); + *stat =0 ; +return 0 ; + +error0: +XFS_BTREE_TRACE_CURSOR (cur,XBT_ERROR ); +return error; +} + +/* * Move 1 record right from cur/level if possible. * Update cur to reflect the new path. */
fs/xfs/xfs_alloc_btree.c +2 -144
170 lines not on this page · raw message
fs/xfs/xfs_bmap_btree.c +2 -136
162 lines not on this page · raw message
fs/xfs/xfs_btree.h +1 -0
@@ -575,6 +575,7 @@ int xfs_btree_decrement(struct xfs_btreeint xfs_btree_lookup (struct xfs_btree_cur *,xfs_lookup_t ,int *);int xfs_btree_updkey (struct xfs_btree_cur *,union xfs_btree_key *,int );int xfs_btree_update (struct xfs_btree_cur *,union xfs_btree_rec *); +int xfs_btree_lshift (struct xfs_btree_cur *,int ,int *);int xfs_btree_rshift (struct xfs_btree_cur *,int ,int *);
fs/xfs/xfs_ialloc_btree.c +2 -145
171 lines not on this page · raw message
Quoted 20 lines · Christoph Hellwig
Make the btree left shift code generic. Based on a patch from David Chinner with lots of changes to follow the original btree implementations more closely. While this loses some of the generic helper routines for inserting/moving/removing records it also solves some of the one off bugs in the original code and makes it easier to verify.
Signed-off-by Christoph Hellwig <[email protected]>Index:
linux-2.6-xfs/fs/xfs/xfs_btree.c
===================================================================fs/xfs/xfs_btree.c +4
-0@@ -976,6 +976,21 @@ xfs_btree_move_ptrs( } } +STATIC void +xfs_btree_copy_ptrs( + struct xfs_btree_cur *cur, + union xfs_btree_ptr *src_ptr,
fs/xfs/xfs_btree.c xfs_btree_move_ptrs( · line 992
Quoted 10 lines
fs/xfs/xfs_btree.c +10
-0+union xfs_btree_ptr *dst_ptr, + int numptrs) +{ + ASSERT(numptrs > 0); + +if (cur->bc_flags &XFS_BTREE_LONG_PTRS ) +memcpy (dst_ptr, src_ptr, numptrs *sizeof (__be64)); +else +memcpy (dst_ptr, src_ptr, numptrs *sizeof (__be32)); +}
These should really use memmove, not memcpy. There is no guarantee the source and destination do not overlap.
At minimum, we need comments to say this must only be used to copy between blocks, and xfs_btree_move_ptrs() must be used to copy within a block. I note the original patchset of mine commented on this distinction when defining the ->move_* and ->copy_* operations.
FWIW, that also helps explain why they have different interfaces...
Quoted 22 lines
fs/xfs/xfs_btree.c +15
-0+/* * Log block pointer fields from a btree block (nonleaf). */ @@ -1597,6 +1612,188 @@ error0: }/* +* Move 1 record left from cur/level if possible. +* Update cur to reflect the new path. +*/ +int /* error */ +xfs_btree_lshift ( +struct xfs_btree_cur *cur, +int level, +int *stat)/* success/failure */ +{ +union xfs_btree_key key;/* btree key */ +struct xfs_buf *lbp;/* left buffer pointer */ +struct xfs_btree_block *left;/* left btree block */ +int lrecs;/* left record count */ +struct xfs_buf *rbp;/* right buffer pointer */
fs/xfs/xfs_btree.c error0: · line 1638
Quoted 10 lines
fs/xfs/xfs_btree.c +10
-0+struct xfs_btree_block *right;/* right btree block */ +int rrecs;/* right record count */ +union xfs_btree_ptr lptr;/* left btree pointer */ +union xfs_btree_key *rkp =NULL ;/* right btree key */ +union xfs_btree_ptr *rpp =NULL ;/* right address pointer */ +union xfs_btree_rec *rrp =NULL ;/* right record pointer */ +int error;/* error return value */ +#ifdef DEBUG +int i;/* loop index */ +#endif
This can be moved inside the branch it is used in.
fs/xfs/xfs_btree.c error0: · line 1694
Quoted 10 lines
fs/xfs/xfs_btree.c +10
-0+ lrecs++; + rrecs--; + +XFS_BTREE_STATS_INC (cur, lshift); + +/* +* If non-leaf, copy a key and a ptr to the left block. +* Log the changes to the left block. +*/ +XFS_BTREE_STATS_ADD (cur, moves,1 );
Move the XFS_BTREE_STATS_ADD() above the comment to match the rshift code.
Otherwise looks good.
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Quoted 17 lines
fs/xfs/xfs_btree.c xfs_btree_move_ptrs( · line 992
Quoted 13 lines
fs/xfs/xfs_btree.c +13
-0+xfs_btree_copy_ptrs ( + struct xfs_btree_cur *cur, + union xfs_btree_ptr *src_ptr, + union xfs_btree_ptr *dst_ptr, + int numptrs) +{ + ASSERT(numptrs > 0); + +if (cur->bc_flags &XFS_BTREE_LONG_PTRS ) +memcpy (dst_ptr, src_ptr, numptrs *sizeof (__be64)); +else +memcpy (dst_ptr, src_ptr, numptrs *sizeof (__be32)); +}These should really use memmove, not memcpy. There is no guarantee the source and destination do not overlap.
Quoted 7 lines
At minimum, we need comments to say this must only be used to copy between blocks, and
xfs_btree_move_ptrs()must be used to copy within a block. I note the original patchset of mine commented on this distinction when defining the ->move_* and ->copy_* operations.FWIW, that also helps explain why they have different interfaces...
There were some comments in the pre-walkthru cleanup version but they were already lost in that patch. But yes, adding some comments makes sense. Or moving back to single one that unlike your very first version always passes src and dst pointers and always uses memmove.
Quoted 1 line
This can be moved inside the branch it is used in.
Done.
Quoted 2 lines
Move the
XFS_BTREE_STATS_ADD()above the comment to match the rshift code.
Done.
Quoted 23 lines · Christoph Hellwig
Quoted 23 lines
fs/xfs/xfs_btree.c xfs_btree_move_ptrs( · line 992
Quoted 13 lines
fs/xfs/xfs_btree.c +13
-0+xfs_btree_copy_ptrs ( + struct xfs_btree_cur *cur, + union xfs_btree_ptr *src_ptr, + union xfs_btree_ptr *dst_ptr, + int numptrs) +{ + ASSERT(numptrs > 0); + +if (cur->bc_flags &XFS_BTREE_LONG_PTRS ) +memcpy (dst_ptr, src_ptr, numptrs *sizeof (__be64)); +else +memcpy (dst_ptr, src_ptr, numptrs *sizeof (__be32)); +}These should really use memmove, not memcpy. There is no guarantee the source and destination do not overlap.
At minimum, we need comments to say this must only be used to copy between blocks, and
xfs_btree_move_ptrs()must be used to copy within a block. I note the original patchset of mine commented on this distinction when defining the ->move_* and ->copy_* operations.
Quoted 6 lines
Quoted 1 line
FWIW, that also helps explain why they have different interfaces...
There were some comments in the pre-walkthru cleanup version but they were already lost in that patch. But yes, adding some comments makes sense. Or moving back to single one that unlike your very first version always passes src and dst pointers and always uses memmove.
It might make sense to go back to a single implementation, though at the time I did it it made sense to split the move/copy operations because it made both cases simpler. Seeing as you've stuck more closely to the original structure of the code, the distinction is not as great as so it might be best to go back to a single memmove based interface.
Cheers,
Dave.
Signature · 2 lines
Dave Chinner [email protected]
Quoted 6 lines · Dave Chinner
It might make sense to go back to a single implementation, though at the time I did it it made sense to split the move/copy operations because it made both cases simpler. Seeing as you've stuck more closely to the original structure of the code, the distinction is not as great as so it might be best to go back to a single memmove based interface.
Btw, one other idea I still have in my mind is to add rec_len and key_len methods to the core btree code, that way quite a few methods (ptr_addr, key_addr, rec_addr, set_key, move_keys, move_recs, copy_keys, copy_recs, log_keys, and log_recs) could be implemented in common code, leaving the actual btree implementations really small.