aboutsummaryrefslogtreecommitdiffstats
path: root/fs/xfs/xfs_btree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/xfs/xfs_btree.c')
-rw-r--r--fs/xfs/xfs_btree.c130
1 files changed, 130 insertions, 0 deletions
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