aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--fs/xfs/xfs_alloc_btree.c3
-rw-r--r--fs/xfs/xfs_bmap_btree.c3
-rw-r--r--fs/xfs/xfs_btree.c130
-rw-r--r--fs/xfs/xfs_btree.h13
-rw-r--r--fs/xfs/xfs_ialloc_btree.c3
5 files changed, 152 insertions, 0 deletions
diff --git a/fs/xfs/xfs_alloc_btree.c b/fs/xfs/xfs_alloc_btree.c
index 1f268b6f4362..9e2421c31a36 100644
--- a/fs/xfs/xfs_alloc_btree.c
+++ b/fs/xfs/xfs_alloc_btree.c
@@ -2294,6 +2294,9 @@ xfs_allocbt_trace_record(
2294#endif /* XFS_BTREE_TRACE */ 2294#endif /* XFS_BTREE_TRACE */
2295 2295
2296static const struct xfs_btree_ops xfs_allocbt_ops = { 2296static const struct xfs_btree_ops xfs_allocbt_ops = {
2297 .rec_len = sizeof(xfs_alloc_rec_t),
2298 .key_len = sizeof(xfs_alloc_key_t),
2299
2297 .dup_cursor = xfs_allocbt_dup_cursor, 2300 .dup_cursor = xfs_allocbt_dup_cursor,
2298 .get_maxrecs = xfs_allocbt_get_maxrecs, 2301 .get_maxrecs = xfs_allocbt_get_maxrecs,
2299 2302
diff --git a/fs/xfs/xfs_bmap_btree.c b/fs/xfs/xfs_bmap_btree.c
index bdcfbea1e062..a71010abf6ec 100644
--- a/fs/xfs/xfs_bmap_btree.c
+++ b/fs/xfs/xfs_bmap_btree.c
@@ -2509,6 +2509,9 @@ xfs_bmbt_trace_record(
2509#endif /* XFS_BTREE_TRACE */ 2509#endif /* XFS_BTREE_TRACE */
2510 2510
2511static const struct xfs_btree_ops xfs_bmbt_ops = { 2511static const struct xfs_btree_ops xfs_bmbt_ops = {
2512 .rec_len = sizeof(xfs_bmbt_rec_t),
2513 .key_len = sizeof(xfs_bmbt_key_t),
2514
2512 .dup_cursor = xfs_bmbt_dup_cursor, 2515 .dup_cursor = xfs_bmbt_dup_cursor,
2513 .get_maxrecs = xfs_bmbt_get_maxrecs, 2516 .get_maxrecs = xfs_bmbt_get_maxrecs,
2514 2517
diff --git a/fs/xfs/xfs_btree.c b/fs/xfs/xfs_btree.c
index 893e86f2ad57..4aec7c7d5ba9 100644
--- a/fs/xfs/xfs_btree.c
+++ b/fs/xfs/xfs_btree.c
@@ -403,6 +403,136 @@ xfs_btree_dup_cursor(
403} 403}
404 404
405/* 405/*
406 * XFS btree block layout and addressing:
407 *
408 * There are two types of blocks in the btree: leaf and non-leaf blocks.
409 *
410 * The leaf record start with a header then followed by records containing
411 * the values. A non-leaf block also starts with the same header, and
412 * then first contains lookup keys followed by an equal number of pointers
413 * to the btree blocks at the previous level.
414 *
415 * +--------+-------+-------+-------+-------+-------+-------+
416 * Leaf: | header | rec 1 | rec 2 | rec 3 | rec 4 | rec 5 | rec N |
417 * +--------+-------+-------+-------+-------+-------+-------+
418 *
419 * +--------+-------+-------+-------+-------+-------+-------+
420 * Non-Leaf: | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
421 * +--------+-------+-------+-------+-------+-------+-------+
422 *
423 * The header is called struct xfs_btree_block for reasons better left unknown
424 * and comes in different versions for short (32bit) and long (64bit) block
425 * pointers. The record and key structures are defined by the btree instances
426 * and opaque to the btree core. The block pointers are simple disk endian
427 * integers, available in a short (32bit) and long (64bit) variant.
428 *
429 * The helpers below calculate the offset of a given record, key or pointer
430 * into a btree block (xfs_btree_*_offset) or return a pointer to the given
431 * record, key or pointer (xfs_btree_*_addr). Note that all addressing
432 * inside the btree block is done using indices starting at one, not zero!
433 */
434
435/*
436 * Return size of the btree block header for this btree instance.
437 */
438static inline size_t xfs_btree_block_len(struct xfs_btree_cur *cur)
439{
440 return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
441 sizeof(struct xfs_btree_lblock) :
442 sizeof(struct xfs_btree_sblock);
443}
444
445/*
446 * Return size of btree block pointers for this btree instance.
447 */
448static inline size_t xfs_btree_ptr_len(struct xfs_btree_cur *cur)
449{
450 return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
451 sizeof(__be64) : sizeof(__be32);
452}
453
454/*
455 * Calculate offset of the n-th record in a btree block.
456 */
457STATIC size_t
458xfs_btree_rec_offset(
459 struct xfs_btree_cur *cur,
460 int n)
461{
462 return xfs_btree_block_len(cur) +
463 (n - 1) * cur->bc_ops->rec_len;
464}
465
466/*
467 * Calculate offset of the n-th key in a btree block.
468 */
469STATIC size_t
470xfs_btree_key_offset(
471 struct xfs_btree_cur *cur,
472 int n)
473{
474 return xfs_btree_block_len(cur) +
475 (n - 1) * cur->bc_ops->key_len;
476}
477
478/*
479 * Calculate offset of the n-th block pointer in a btree block.
480 */
481STATIC size_t
482xfs_btree_ptr_offset(
483 struct xfs_btree_cur *cur,
484 int n,
485 int level)
486{
487 return xfs_btree_block_len(cur) +
488 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len +
489 (n - 1) * xfs_btree_ptr_len(cur);
490}
491
492/*
493 * Return a pointer to the n-th record in the btree block.
494 */
495STATIC union xfs_btree_rec *
496xfs_btree_rec_addr(
497 struct xfs_btree_cur *cur,
498 int n,
499 struct xfs_btree_block *block)
500{
501 return (union xfs_btree_rec *)
502 ((char *)block + xfs_btree_rec_offset(cur, n));
503}
504
505/*
506 * Return a pointer to the n-th key in the btree block.
507 */
508STATIC union xfs_btree_key *
509xfs_btree_key_addr(
510 struct xfs_btree_cur *cur,
511 int n,
512 struct xfs_btree_block *block)
513{
514 return (union xfs_btree_key *)
515 ((char *)block + xfs_btree_key_offset(cur, n));
516}
517
518/*
519 * Return a pointer to the n-th block pointer in the btree block.
520 */
521STATIC union xfs_btree_ptr *
522xfs_btree_ptr_addr(
523 struct xfs_btree_cur *cur,
524 int n,
525 struct xfs_btree_block *block)
526{
527 int level = xfs_btree_get_level(block);
528
529 ASSERT(block->bb_level != 0);
530
531 return (union xfs_btree_ptr *)
532 ((char *)block + xfs_btree_ptr_offset(cur, n, level));
533}
534
535/*
406 * Get a the root block which is stored in the inode. 536 * Get a the root block which is stored in the inode.
407 * 537 *
408 * For now this btree implementation assumes the btree root is always 538 * For now this btree implementation assumes the btree root is always
diff --git a/fs/xfs/xfs_btree.h b/fs/xfs/xfs_btree.h
index 5398cd0d4d4d..593f82b01b6f 100644
--- a/fs/xfs/xfs_btree.h
+++ b/fs/xfs/xfs_btree.h
@@ -180,6 +180,10 @@ do { \
180#define XFS_BTREE_MAXLEVELS 8 /* max of all btrees */ 180#define XFS_BTREE_MAXLEVELS 8 /* max of all btrees */
181 181
182struct xfs_btree_ops { 182struct xfs_btree_ops {
183 /* size of the key and record structures */
184 size_t key_len;
185 size_t rec_len;
186
183 /* cursor operations */ 187 /* cursor operations */
184 struct xfs_btree_cur *(*dup_cursor)(struct xfs_btree_cur *); 188 struct xfs_btree_cur *(*dup_cursor)(struct xfs_btree_cur *);
185 189
@@ -497,6 +501,15 @@ xfs_btree_setbuf(
497 int lev, /* level in btree */ 501 int lev, /* level in btree */
498 struct xfs_buf *bp); /* new buffer to set */ 502 struct xfs_buf *bp); /* new buffer to set */
499 503
504
505/*
506 * Helpers.
507 */
508static inline int xfs_btree_get_level(struct xfs_btree_block *block)
509{
510 return be16_to_cpu(block->bb_level);
511}
512
500#endif /* __KERNEL__ */ 513#endif /* __KERNEL__ */
501 514
502 515
diff --git a/fs/xfs/xfs_ialloc_btree.c b/fs/xfs/xfs_ialloc_btree.c
index 18867f1aacac..fc6db94492dc 100644
--- a/fs/xfs/xfs_ialloc_btree.c
+++ b/fs/xfs/xfs_ialloc_btree.c
@@ -2160,6 +2160,9 @@ xfs_inobt_trace_record(
2160#endif /* XFS_BTREE_TRACE */ 2160#endif /* XFS_BTREE_TRACE */
2161 2161
2162static const struct xfs_btree_ops xfs_inobt_ops = { 2162static const struct xfs_btree_ops xfs_inobt_ops = {
2163 .rec_len = sizeof(xfs_inobt_rec_t),
2164 .key_len = sizeof(xfs_inobt_key_t),
2165
2163 .dup_cursor = xfs_inobt_dup_cursor, 2166 .dup_cursor = xfs_inobt_dup_cursor,
2164 .get_maxrecs = xfs_inobt_get_maxrecs, 2167 .get_maxrecs = xfs_inobt_get_maxrecs,
2165 2168