xfs_alloc_btree.h 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155
  1. /*
  2. * Copyright (c) 2000,2005 Silicon Graphics, Inc.
  3. * All Rights Reserved.
  4. *
  5. * This program is free software; you can redistribute it and/or
  6. * modify it under the terms of the GNU General Public License as
  7. * published by the Free Software Foundation.
  8. *
  9. * This program is distributed in the hope that it would be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. * GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with this program; if not, write the Free Software Foundation,
  16. * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  17. */
  18. #ifndef __XFS_ALLOC_BTREE_H__
  19. #define __XFS_ALLOC_BTREE_H__
  20. /*
  21. * Freespace on-disk structures
  22. */
  23. struct xfs_buf;
  24. struct xfs_btree_cur;
  25. struct xfs_btree_sblock;
  26. struct xfs_mount;
  27. /*
  28. * There are two on-disk btrees, one sorted by blockno and one sorted
  29. * by blockcount and blockno. All blocks look the same to make the code
  30. * simpler; if we have time later, we'll make the optimizations.
  31. */
  32. #define XFS_ABTB_MAGIC 0x41425442 /* 'ABTB' for bno tree */
  33. #define XFS_ABTC_MAGIC 0x41425443 /* 'ABTC' for cnt tree */
  34. /*
  35. * Data record/key structure
  36. */
  37. typedef struct xfs_alloc_rec {
  38. __be32 ar_startblock; /* starting block number */
  39. __be32 ar_blockcount; /* count of free blocks */
  40. } xfs_alloc_rec_t, xfs_alloc_key_t;
  41. typedef struct xfs_alloc_rec_incore {
  42. xfs_agblock_t ar_startblock; /* starting block number */
  43. xfs_extlen_t ar_blockcount; /* count of free blocks */
  44. } xfs_alloc_rec_incore_t;
  45. /* btree pointer type */
  46. typedef __be32 xfs_alloc_ptr_t;
  47. /* btree block header type */
  48. typedef struct xfs_btree_sblock xfs_alloc_block_t;
  49. #define XFS_BUF_TO_ALLOC_BLOCK(bp) ((xfs_alloc_block_t *)XFS_BUF_PTR(bp))
  50. /*
  51. * Real block structures have a size equal to the disk block size.
  52. */
  53. #define XFS_ALLOC_BLOCK_MAXRECS(lev,cur) ((cur)->bc_mp->m_alloc_mxr[lev != 0])
  54. #define XFS_ALLOC_BLOCK_MINRECS(lev,cur) ((cur)->bc_mp->m_alloc_mnr[lev != 0])
  55. /*
  56. * Minimum and maximum blocksize and sectorsize.
  57. * The blocksize upper limit is pretty much arbitrary.
  58. * The sectorsize upper limit is due to sizeof(sb_sectsize).
  59. */
  60. #define XFS_MIN_BLOCKSIZE_LOG 9 /* i.e. 512 bytes */
  61. #define XFS_MAX_BLOCKSIZE_LOG 16 /* i.e. 65536 bytes */
  62. #define XFS_MIN_BLOCKSIZE (1 << XFS_MIN_BLOCKSIZE_LOG)
  63. #define XFS_MAX_BLOCKSIZE (1 << XFS_MAX_BLOCKSIZE_LOG)
  64. #define XFS_MIN_SECTORSIZE_LOG 9 /* i.e. 512 bytes */
  65. #define XFS_MAX_SECTORSIZE_LOG 15 /* i.e. 32768 bytes */
  66. #define XFS_MIN_SECTORSIZE (1 << XFS_MIN_SECTORSIZE_LOG)
  67. #define XFS_MAX_SECTORSIZE (1 << XFS_MAX_SECTORSIZE_LOG)
  68. /*
  69. * Block numbers in the AG:
  70. * SB is sector 0, AGF is sector 1, AGI is sector 2, AGFL is sector 3.
  71. */
  72. #define XFS_BNO_BLOCK(mp) ((xfs_agblock_t)(XFS_AGFL_BLOCK(mp) + 1))
  73. #define XFS_CNT_BLOCK(mp) ((xfs_agblock_t)(XFS_BNO_BLOCK(mp) + 1))
  74. /*
  75. * Record, key, and pointer address macros for btree blocks.
  76. */
  77. #define XFS_ALLOC_REC_ADDR(bb,i,cur) \
  78. XFS_BTREE_REC_ADDR(xfs_alloc, bb, i)
  79. #define XFS_ALLOC_KEY_ADDR(bb,i,cur) \
  80. XFS_BTREE_KEY_ADDR(xfs_alloc, bb, i)
  81. #define XFS_ALLOC_PTR_ADDR(bb,i,cur) \
  82. XFS_BTREE_PTR_ADDR(xfs_alloc, bb, i, XFS_ALLOC_BLOCK_MAXRECS(1, cur))
  83. /*
  84. * Decrement cursor by one record at the level.
  85. * For nonzero levels the leaf-ward information is untouched.
  86. */
  87. extern int xfs_alloc_decrement(struct xfs_btree_cur *cur, int level, int *stat);
  88. /*
  89. * Delete the record pointed to by cur.
  90. * The cursor refers to the place where the record was (could be inserted)
  91. * when the operation returns.
  92. */
  93. extern int xfs_alloc_delete(struct xfs_btree_cur *cur, int *stat);
  94. /*
  95. * Get the data from the pointed-to record.
  96. */
  97. extern int xfs_alloc_get_rec(struct xfs_btree_cur *cur, xfs_agblock_t *bno,
  98. xfs_extlen_t *len, int *stat);
  99. /*
  100. * Increment cursor by one record at the level.
  101. * For nonzero levels the leaf-ward information is untouched.
  102. */
  103. extern int xfs_alloc_increment(struct xfs_btree_cur *cur, int level, int *stat);
  104. /*
  105. * Insert the current record at the point referenced by cur.
  106. * The cursor may be inconsistent on return if splits have been done.
  107. */
  108. extern int xfs_alloc_insert(struct xfs_btree_cur *cur, int *stat);
  109. /*
  110. * Lookup the record equal to [bno, len] in the btree given by cur.
  111. */
  112. extern int xfs_alloc_lookup_eq(struct xfs_btree_cur *cur, xfs_agblock_t bno,
  113. xfs_extlen_t len, int *stat);
  114. /*
  115. * Lookup the first record greater than or equal to [bno, len]
  116. * in the btree given by cur.
  117. */
  118. extern int xfs_alloc_lookup_ge(struct xfs_btree_cur *cur, xfs_agblock_t bno,
  119. xfs_extlen_t len, int *stat);
  120. /*
  121. * Lookup the first record less than or equal to [bno, len]
  122. * in the btree given by cur.
  123. */
  124. extern int xfs_alloc_lookup_le(struct xfs_btree_cur *cur, xfs_agblock_t bno,
  125. xfs_extlen_t len, int *stat);
  126. /*
  127. * Update the record referred to by cur, to the value given by [bno, len].
  128. * This either works (return 0) or gets an EFSCORRUPTED error.
  129. */
  130. extern int xfs_alloc_update(struct xfs_btree_cur *cur, xfs_agblock_t bno,
  131. xfs_extlen_t len);
  132. #endif /* __XFS_ALLOC_BTREE_H__ */