]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - db/btblock.c
89e550c347dad85e9e286848a9b392dbf3d781d6
2 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
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.
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.
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
19 #include <xfs/libxfs.h>
31 * Definition of the possible btree block layouts.
39 [/*0x424d415*/0] = { /* BMAP */
40 sizeof(struct xfs_btree_lblock
),
41 sizeof(xfs_bmbt_key_t
),
42 sizeof(xfs_bmbt_rec_t
),
45 [/*0x4142544*/2] = { /* ABTB */
46 sizeof(struct xfs_btree_sblock
),
47 sizeof(xfs_alloc_key_t
),
48 sizeof(xfs_alloc_rec_t
),
51 [/*0x4142544*/3] = { /* ABTC */
52 sizeof(struct xfs_btree_sblock
),
53 sizeof(xfs_alloc_key_t
),
54 sizeof(xfs_alloc_rec_t
),
57 [/*0x4941425*/4] = { /* IABT */
58 sizeof(struct xfs_btree_sblock
),
59 sizeof(xfs_inobt_key_t
),
60 sizeof(xfs_inobt_rec_t
),
66 * Find the right block defintion for a given ondisk block.
68 * We use the least significant bit of the magic number as index into
69 * the array of block defintions.
71 #define block_to_bt(bb) \
72 (&btrees[be32_to_cpu((bb)->bb_magic) & 0xf])
74 /* calculate max records. Only for non-leaves. */
76 btblock_maxrecs(struct xfs_db_btree
*bt
, int blocksize
)
78 blocksize
-= bt
->block_len
;
80 return blocksize
/ (bt
->key_len
+ bt
->ptr_len
);
84 * Get the number of keys in a btree block.
86 * Note: can also be used to get the number of ptrs because there are
87 * always the same number of keys and ptrs in a block.
94 struct xfs_btree_block
*block
= obj
;
96 ASSERT(startoff
== 0);
98 if (block
->bb_level
== 0)
100 return be16_to_cpu(block
->bb_numrecs
);
104 * Get the number of keys in a btree block.
111 struct xfs_btree_block
*block
= obj
;
113 ASSERT(startoff
== 0);
115 if (block
->bb_level
!= 0)
117 return be16_to_cpu(block
->bb_numrecs
);
121 * Get the offset of the key at idx in a btree block.
129 struct xfs_btree_block
*block
= obj
;
130 struct xfs_db_btree
*bt
= block_to_bt(block
);
133 ASSERT(startoff
== 0);
134 ASSERT(block
->bb_level
!= 0);
136 offset
= bt
->block_len
+ (idx
- 1) * bt
->key_len
;
137 return bitize(offset
);
141 * Get the offset of the ptr at idx in a btree block.
149 struct xfs_btree_block
*block
= obj
;
150 struct xfs_db_btree
*bt
= block_to_bt(block
);
154 ASSERT(startoff
== 0);
155 ASSERT(block
->bb_level
!= 0);
157 maxrecs
= btblock_maxrecs(bt
, mp
->m_sb
.sb_blocksize
);
158 offset
= bt
->block_len
+
159 maxrecs
* bt
->key_len
+
160 (idx
- 1) * bt
->ptr_len
;
162 return bitize(offset
);
166 * Get the offset of the record at idx in a btree block.
174 struct xfs_btree_block
*block
= obj
;
175 struct xfs_db_btree
*bt
= block_to_bt(block
);
178 ASSERT(startoff
== 0);
179 ASSERT(block
->bb_level
== 0);
181 offset
= bt
->block_len
+ (idx
- 1) * bt
->rec_len
;
182 return bitize(offset
);
186 * Get the size of a btree block.
194 return bitize(mp
->m_sb
.sb_blocksize
);
202 const field_t bmapbta_hfld
[] = {
203 { "", FLDT_BMAPBTA
, OI(0), C1
, 0, TYP_NONE
},
206 const field_t bmapbtd_hfld
[] = {
207 { "", FLDT_BMAPBTD
, OI(0), C1
, 0, TYP_NONE
},
211 #define OFF(f) bitize(offsetof(xfs_bmbt_block_t, bb_ ## f))
212 const field_t bmapbta_flds
[] = {
213 { "magic", FLDT_UINT32X
, OI(OFF(magic
)), C1
, 0, TYP_NONE
},
214 { "level", FLDT_UINT16D
, OI(OFF(level
)), C1
, 0, TYP_NONE
},
215 { "numrecs", FLDT_UINT16D
, OI(OFF(numrecs
)), C1
, 0, TYP_NONE
},
216 { "leftsib", FLDT_DFSBNO
, OI(OFF(leftsib
)), C1
, 0, TYP_BMAPBTA
},
217 { "rightsib", FLDT_DFSBNO
, OI(OFF(rightsib
)), C1
, 0, TYP_BMAPBTA
},
218 { "recs", FLDT_BMAPBTAREC
, btblock_rec_offset
, btblock_rec_count
,
219 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_NONE
},
220 { "keys", FLDT_BMAPBTAKEY
, btblock_key_offset
, btblock_key_count
,
221 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_NONE
},
222 { "ptrs", FLDT_BMAPBTAPTR
, btblock_ptr_offset
, btblock_key_count
,
223 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_BMAPBTA
},
226 const field_t bmapbtd_flds
[] = {
227 { "magic", FLDT_UINT32X
, OI(OFF(magic
)), C1
, 0, TYP_NONE
},
228 { "level", FLDT_UINT16D
, OI(OFF(level
)), C1
, 0, TYP_NONE
},
229 { "numrecs", FLDT_UINT16D
, OI(OFF(numrecs
)), C1
, 0, TYP_NONE
},
230 { "leftsib", FLDT_DFSBNO
, OI(OFF(leftsib
)), C1
, 0, TYP_BMAPBTD
},
231 { "rightsib", FLDT_DFSBNO
, OI(OFF(rightsib
)), C1
, 0, TYP_BMAPBTD
},
232 { "recs", FLDT_BMAPBTDREC
, btblock_rec_offset
, btblock_rec_count
,
233 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_NONE
},
234 { "keys", FLDT_BMAPBTDKEY
, btblock_key_offset
, btblock_key_count
,
235 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_NONE
},
236 { "ptrs", FLDT_BMAPBTDPTR
, btblock_ptr_offset
, btblock_key_count
,
237 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_BMAPBTD
},
242 #define KOFF(f) bitize(offsetof(xfs_bmbt_key_t, br_ ## f))
243 const field_t bmapbta_key_flds
[] = {
244 { "startoff", FLDT_DFILOFFA
, OI(KOFF(startoff
)), C1
, 0, TYP_ATTR
},
247 const field_t bmapbtd_key_flds
[] = {
248 { "startoff", FLDT_DFILOFFD
, OI(KOFF(startoff
)), C1
, 0, TYP_INODATA
},
253 #ifndef XFS_NATIVE_HOST
255 #define BMBT_EXNTFLAG_BITOFF 0
256 #define BMBT_STARTOFF_BITOFF (BMBT_EXNTFLAG_BITOFF + BMBT_EXNTFLAG_BITLEN)
257 #define BMBT_STARTBLOCK_BITOFF (BMBT_STARTOFF_BITOFF + BMBT_STARTOFF_BITLEN)
258 #define BMBT_BLOCKCOUNT_BITOFF \
259 (BMBT_STARTBLOCK_BITOFF + BMBT_STARTBLOCK_BITLEN)
263 #define BMBT_EXNTFLAG_BITOFF 63
264 #define BMBT_STARTOFF_BITOFF (BMBT_EXNTFLAG_BITOFF - BMBT_STARTOFF_BITLEN)
265 #define BMBT_STARTBLOCK_BITOFF 85 /* 128 - 43 (other 9 is in first word) */
266 #define BMBT_BLOCKCOUNT_BITOFF 64 /* Start of second 64 bit container */
268 #endif /* XFS_NATIVE_HOST */
270 const field_t bmapbta_rec_flds
[] = {
271 { "startoff", FLDT_CFILEOFFA
, OI(BMBT_STARTOFF_BITOFF
), C1
, 0,
273 { "startblock", FLDT_CFSBLOCK
, OI(BMBT_STARTBLOCK_BITOFF
), C1
, 0,
275 { "blockcount", FLDT_CEXTLEN
, OI(BMBT_BLOCKCOUNT_BITOFF
), C1
, 0,
277 { "extentflag", FLDT_CEXTFLG
, OI(BMBT_EXNTFLAG_BITOFF
), C1
, 0,
281 const field_t bmapbtd_rec_flds
[] = {
282 { "startoff", FLDT_CFILEOFFD
, OI(BMBT_STARTOFF_BITOFF
), C1
, 0,
284 { "startblock", FLDT_CFSBLOCK
, OI(BMBT_STARTBLOCK_BITOFF
), C1
, 0,
286 { "blockcount", FLDT_CEXTLEN
, OI(BMBT_BLOCKCOUNT_BITOFF
), C1
, 0,
288 { "extentflag", FLDT_CEXTFLG
, OI(BMBT_EXNTFLAG_BITOFF
), C1
, 0,
295 * Inode allocation btree.
298 const field_t inobt_hfld
[] = {
299 { "", FLDT_INOBT
, OI(0), C1
, 0, TYP_NONE
},
303 #define OFF(f) bitize(offsetof(struct xfs_btree_sblock, bb_ ## f))
304 const field_t inobt_flds
[] = {
305 { "magic", FLDT_UINT32X
, OI(OFF(magic
)), C1
, 0, TYP_NONE
},
306 { "level", FLDT_UINT16D
, OI(OFF(level
)), C1
, 0, TYP_NONE
},
307 { "numrecs", FLDT_UINT16D
, OI(OFF(numrecs
)), C1
, 0, TYP_NONE
},
308 { "leftsib", FLDT_AGBLOCK
, OI(OFF(leftsib
)), C1
, 0, TYP_INOBT
},
309 { "rightsib", FLDT_AGBLOCK
, OI(OFF(rightsib
)), C1
, 0, TYP_INOBT
},
310 { "recs", FLDT_INOBTREC
, btblock_rec_offset
, btblock_rec_count
,
311 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_NONE
},
312 { "keys", FLDT_INOBTKEY
, btblock_key_offset
, btblock_key_count
,
313 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_NONE
},
314 { "ptrs", FLDT_INOBTPTR
, btblock_ptr_offset
, btblock_key_count
,
315 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_INOBT
},
320 #define KOFF(f) bitize(offsetof(xfs_inobt_key_t, ir_ ## f))
321 const field_t inobt_key_flds
[] = {
322 { "startino", FLDT_AGINO
, OI(KOFF(startino
)), C1
, 0, TYP_INODE
},
327 #define ROFF(f) bitize(offsetof(xfs_inobt_rec_t, ir_ ## f))
328 const field_t inobt_rec_flds
[] = {
329 { "startino", FLDT_AGINO
, OI(ROFF(startino
)), C1
, 0, TYP_INODE
},
330 { "freecount", FLDT_INT32D
, OI(ROFF(freecount
)), C1
, 0, TYP_NONE
},
331 { "free", FLDT_INOFREE
, OI(ROFF(free
)), C1
, 0, TYP_NONE
},
340 const field_t bnobt_hfld
[] = {
341 { "", FLDT_BNOBT
, OI(0), C1
, 0, TYP_NONE
},
345 #define OFF(f) bitize(offsetof(xfs_alloc_block_t, bb_ ## f))
346 const field_t bnobt_flds
[] = {
347 { "magic", FLDT_UINT32X
, OI(OFF(magic
)), C1
, 0, TYP_NONE
},
348 { "level", FLDT_UINT16D
, OI(OFF(level
)), C1
, 0, TYP_NONE
},
349 { "numrecs", FLDT_UINT16D
, OI(OFF(numrecs
)), C1
, 0, TYP_NONE
},
350 { "leftsib", FLDT_AGBLOCK
, OI(OFF(leftsib
)), C1
, 0, TYP_BNOBT
},
351 { "rightsib", FLDT_AGBLOCK
, OI(OFF(rightsib
)), C1
, 0, TYP_BNOBT
},
352 { "recs", FLDT_BNOBTREC
, btblock_rec_offset
, btblock_rec_count
,
353 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_NONE
},
354 { "keys", FLDT_BNOBTKEY
, btblock_key_offset
, btblock_key_count
,
355 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_NONE
},
356 { "ptrs", FLDT_BNOBTPTR
, btblock_ptr_offset
, btblock_key_count
,
357 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_BNOBT
},
362 #define KOFF(f) bitize(offsetof(xfs_alloc_key_t, ar_ ## f))
363 const field_t bnobt_key_flds
[] = {
364 { "startblock", FLDT_AGBLOCK
, OI(KOFF(startblock
)), C1
, 0, TYP_DATA
},
365 { "blockcount", FLDT_EXTLEN
, OI(KOFF(blockcount
)), C1
, 0, TYP_NONE
},
370 #define ROFF(f) bitize(offsetof(xfs_alloc_rec_t, ar_ ## f))
371 const field_t bnobt_rec_flds
[] = {
372 { "startblock", FLDT_AGBLOCK
, OI(ROFF(startblock
)), C1
, 0, TYP_DATA
},
373 { "blockcount", FLDT_EXTLEN
, OI(ROFF(blockcount
)), C1
, 0, TYP_NONE
},
378 const field_t cntbt_hfld
[] = {
379 { "", FLDT_CNTBT
, OI(0), C1
, 0, TYP_NONE
},
383 #define OFF(f) bitize(offsetof(xfs_alloc_block_t, bb_ ## f))
384 const field_t cntbt_flds
[] = {
385 { "magic", FLDT_UINT32X
, OI(OFF(magic
)), C1
, 0, TYP_NONE
},
386 { "level", FLDT_UINT16D
, OI(OFF(level
)), C1
, 0, TYP_NONE
},
387 { "numrecs", FLDT_UINT16D
, OI(OFF(numrecs
)), C1
, 0, TYP_NONE
},
388 { "leftsib", FLDT_AGBLOCK
, OI(OFF(leftsib
)), C1
, 0, TYP_CNTBT
},
389 { "rightsib", FLDT_AGBLOCK
, OI(OFF(rightsib
)), C1
, 0, TYP_CNTBT
},
390 { "recs", FLDT_CNTBTREC
, btblock_rec_offset
, btblock_rec_count
,
391 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_NONE
},
392 { "keys", FLDT_CNTBTKEY
, btblock_key_offset
, btblock_key_count
,
393 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_NONE
},
394 { "ptrs", FLDT_CNTBTPTR
, btblock_ptr_offset
, btblock_key_count
,
395 FLD_ARRAY
|FLD_ABASE1
|FLD_COUNT
|FLD_OFFSET
, TYP_CNTBT
},
400 #define KOFF(f) bitize(offsetof(xfs_alloc_key_t, ar_ ## f))
401 const field_t cntbt_key_flds
[] = {
402 { "blockcount", FLDT_EXTLEN
, OI(KOFF(blockcount
)), C1
, 0, TYP_NONE
},
403 { "startblock", FLDT_AGBLOCK
, OI(KOFF(startblock
)), C1
, 0, TYP_DATA
},
408 #define ROFF(f) bitize(offsetof(xfs_alloc_rec_t, ar_ ## f))
409 const field_t cntbt_rec_flds
[] = {
410 { "startblock", FLDT_AGBLOCK
, OI(ROFF(startblock
)), C1
, 0, TYP_DATA
},
411 { "blockcount", FLDT_EXTLEN
, OI(ROFF(blockcount
)), C1
, 0, TYP_NONE
},