~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/xfs/xfs_btree.h

Version: ~ [ linux-5.2-rc1 ] ~ [ linux-5.1.2 ] ~ [ linux-5.0.16 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.43 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.119 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.176 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.179 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.139 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.67 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * Copyright (c) 2000-2001,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_BTREE_H__
 19 #define __XFS_BTREE_H__
 20 
 21 struct xfs_buf;
 22 struct xfs_bmap_free;
 23 struct xfs_inode;
 24 struct xfs_mount;
 25 struct xfs_trans;
 26 
 27 extern kmem_zone_t      *xfs_btree_cur_zone;
 28 
 29 /*
 30  * This nonsense is to make -wlint happy.
 31  */
 32 #define XFS_LOOKUP_EQ   ((xfs_lookup_t)XFS_LOOKUP_EQi)
 33 #define XFS_LOOKUP_LE   ((xfs_lookup_t)XFS_LOOKUP_LEi)
 34 #define XFS_LOOKUP_GE   ((xfs_lookup_t)XFS_LOOKUP_GEi)
 35 
 36 #define XFS_BTNUM_BNO   ((xfs_btnum_t)XFS_BTNUM_BNOi)
 37 #define XFS_BTNUM_CNT   ((xfs_btnum_t)XFS_BTNUM_CNTi)
 38 #define XFS_BTNUM_BMAP  ((xfs_btnum_t)XFS_BTNUM_BMAPi)
 39 #define XFS_BTNUM_INO   ((xfs_btnum_t)XFS_BTNUM_INOi)
 40 
 41 /*
 42  * Generic btree header.
 43  *
 44  * This is a combination of the actual format used on disk for short and long
 45  * format btrees.  The first three fields are shared by both format, but
 46  * the pointers are different and should be used with care.
 47  *
 48  * To get the size of the actual short or long form headers please use
 49  * the size macros below.  Never use sizeof(xfs_btree_block).
 50  */
 51 struct xfs_btree_block {
 52         __be32          bb_magic;       /* magic number for block type */
 53         __be16          bb_level;       /* 0 is a leaf */
 54         __be16          bb_numrecs;     /* current # of data records */
 55         union {
 56                 struct {
 57                         __be32          bb_leftsib;
 58                         __be32          bb_rightsib;
 59                 } s;                    /* short form pointers */
 60                 struct  {
 61                         __be64          bb_leftsib;
 62                         __be64          bb_rightsib;
 63                 } l;                    /* long form pointers */
 64         } bb_u;                         /* rest */
 65 };
 66 
 67 #define XFS_BTREE_SBLOCK_LEN    16      /* size of a short form block */
 68 #define XFS_BTREE_LBLOCK_LEN    24      /* size of a long form block */
 69 
 70 
 71 /*
 72  * Generic key, ptr and record wrapper structures.
 73  *
 74  * These are disk format structures, and are converted where necessary
 75  * by the btree specific code that needs to interpret them.
 76  */
 77 union xfs_btree_ptr {
 78         __be32                  s;      /* short form ptr */
 79         __be64                  l;      /* long form ptr */
 80 };
 81 
 82 union xfs_btree_key {
 83         xfs_bmbt_key_t          bmbt;
 84         xfs_bmdr_key_t          bmbr;   /* bmbt root block */
 85         xfs_alloc_key_t         alloc;
 86         xfs_inobt_key_t         inobt;
 87 };
 88 
 89 union xfs_btree_rec {
 90         xfs_bmbt_rec_t          bmbt;
 91         xfs_bmdr_rec_t          bmbr;   /* bmbt root block */
 92         xfs_alloc_rec_t         alloc;
 93         xfs_inobt_rec_t         inobt;
 94 };
 95 
 96 /*
 97  * For logging record fields.
 98  */
 99 #define XFS_BB_MAGIC            0x01
100 #define XFS_BB_LEVEL            0x02
101 #define XFS_BB_NUMRECS          0x04
102 #define XFS_BB_LEFTSIB          0x08
103 #define XFS_BB_RIGHTSIB         0x10
104 #define XFS_BB_NUM_BITS         5
105 #define XFS_BB_ALL_BITS         ((1 << XFS_BB_NUM_BITS) - 1)
106 
107 /*
108  * Magic numbers for btree blocks.
109  */
110 extern const __uint32_t xfs_magics[];
111 
112 /*
113  * Generic stats interface
114  */
115 #define __XFS_BTREE_STATS_INC(type, stat) \
116         XFS_STATS_INC(xs_ ## type ## _2_ ## stat)
117 #define XFS_BTREE_STATS_INC(cur, stat)  \
118 do {    \
119         switch (cur->bc_btnum) {  \
120         case XFS_BTNUM_BNO: __XFS_BTREE_STATS_INC(abtb, stat); break;   \
121         case XFS_BTNUM_CNT: __XFS_BTREE_STATS_INC(abtc, stat); break;   \
122         case XFS_BTNUM_BMAP: __XFS_BTREE_STATS_INC(bmbt, stat); break;  \
123         case XFS_BTNUM_INO: __XFS_BTREE_STATS_INC(ibt, stat); break;    \
124         case XFS_BTNUM_MAX: ASSERT(0); /* fucking gcc */ ; break;       \
125         }       \
126 } while (0)
127 
128 #define __XFS_BTREE_STATS_ADD(type, stat, val) \
129         XFS_STATS_ADD(xs_ ## type ## _2_ ## stat, val)
130 #define XFS_BTREE_STATS_ADD(cur, stat, val)  \
131 do {    \
132         switch (cur->bc_btnum) {  \
133         case XFS_BTNUM_BNO: __XFS_BTREE_STATS_ADD(abtb, stat, val); break; \
134         case XFS_BTNUM_CNT: __XFS_BTREE_STATS_ADD(abtc, stat, val); break; \
135         case XFS_BTNUM_BMAP: __XFS_BTREE_STATS_ADD(bmbt, stat, val); break; \
136         case XFS_BTNUM_INO: __XFS_BTREE_STATS_ADD(ibt, stat, val); break; \
137         case XFS_BTNUM_MAX: ASSERT(0); /* fucking gcc */ ; break;       \
138         }       \
139 } while (0)
140 
141 #define XFS_BTREE_MAXLEVELS     8       /* max of all btrees */
142 
143 struct xfs_btree_ops {
144         /* size of the key and record structures */
145         size_t  key_len;
146         size_t  rec_len;
147 
148         /* cursor operations */
149         struct xfs_btree_cur *(*dup_cursor)(struct xfs_btree_cur *);
150         void    (*update_cursor)(struct xfs_btree_cur *src,
151                                  struct xfs_btree_cur *dst);
152 
153         /* update btree root pointer */
154         void    (*set_root)(struct xfs_btree_cur *cur,
155                                 union xfs_btree_ptr *nptr, int level_change);
156         int     (*kill_root)(struct xfs_btree_cur *cur, struct xfs_buf *bp,
157                                 int level, union xfs_btree_ptr *newroot);
158 
159         /* block allocation / freeing */
160         int     (*alloc_block)(struct xfs_btree_cur *cur,
161                                union xfs_btree_ptr *start_bno,
162                                union xfs_btree_ptr *new_bno,
163                                int length, int *stat);
164         int     (*free_block)(struct xfs_btree_cur *cur, struct xfs_buf *bp);
165 
166         /* update last record information */
167         void    (*update_lastrec)(struct xfs_btree_cur *cur,
168                                   struct xfs_btree_block *block,
169                                   union xfs_btree_rec *rec,
170                                   int ptr, int reason);
171 
172         /* records in block/level */
173         int     (*get_minrecs)(struct xfs_btree_cur *cur, int level);
174         int     (*get_maxrecs)(struct xfs_btree_cur *cur, int level);
175 
176         /* records on disk.  Matter for the root in inode case. */
177         int     (*get_dmaxrecs)(struct xfs_btree_cur *cur, int level);
178 
179         /* init values of btree structures */
180         void    (*init_key_from_rec)(union xfs_btree_key *key,
181                                      union xfs_btree_rec *rec);
182         void    (*init_rec_from_key)(union xfs_btree_key *key,
183                                      union xfs_btree_rec *rec);
184         void    (*init_rec_from_cur)(struct xfs_btree_cur *cur,
185                                      union xfs_btree_rec *rec);
186         void    (*init_ptr_from_cur)(struct xfs_btree_cur *cur,
187                                      union xfs_btree_ptr *ptr);
188 
189         /* difference between key value and cursor value */
190         __int64_t (*key_diff)(struct xfs_btree_cur *cur,
191                               union xfs_btree_key *key);
192 
193 #ifdef DEBUG
194         /* check that k1 is lower than k2 */
195         int     (*keys_inorder)(struct xfs_btree_cur *cur,
196                                 union xfs_btree_key *k1,
197                                 union xfs_btree_key *k2);
198 
199         /* check that r1 is lower than r2 */
200         int     (*recs_inorder)(struct xfs_btree_cur *cur,
201                                 union xfs_btree_rec *r1,
202                                 union xfs_btree_rec *r2);
203 #endif
204 
205         /* btree tracing */
206 #ifdef XFS_BTREE_TRACE
207         void            (*trace_enter)(struct xfs_btree_cur *, const char *,
208                                        char *, int, int, __psunsigned_t,
209                                        __psunsigned_t, __psunsigned_t,
210                                        __psunsigned_t, __psunsigned_t,
211                                        __psunsigned_t, __psunsigned_t,
212                                        __psunsigned_t, __psunsigned_t,
213                                        __psunsigned_t, __psunsigned_t);
214         void            (*trace_cursor)(struct xfs_btree_cur *, __uint32_t *,
215                                         __uint64_t *, __uint64_t *);
216         void            (*trace_key)(struct xfs_btree_cur *,
217                                      union xfs_btree_key *, __uint64_t *,
218                                      __uint64_t *);
219         void            (*trace_record)(struct xfs_btree_cur *,
220                                         union xfs_btree_rec *, __uint64_t *,
221                                         __uint64_t *, __uint64_t *);
222 #endif
223 };
224 
225 /*
226  * Reasons for the update_lastrec method to be called.
227  */
228 #define LASTREC_UPDATE  0
229 #define LASTREC_INSREC  1
230 #define LASTREC_DELREC  2
231 
232 
233 /*
234  * Btree cursor structure.
235  * This collects all information needed by the btree code in one place.
236  */
237 typedef struct xfs_btree_cur
238 {
239         struct xfs_trans        *bc_tp; /* transaction we're in, if any */
240         struct xfs_mount        *bc_mp; /* file system mount struct */
241         const struct xfs_btree_ops *bc_ops;
242         uint                    bc_flags; /* btree features - below */
243         union {
244                 xfs_alloc_rec_incore_t  a;
245                 xfs_bmbt_irec_t         b;
246                 xfs_inobt_rec_incore_t  i;
247         }               bc_rec;         /* current insert/search record value */
248         struct xfs_buf  *bc_bufs[XFS_BTREE_MAXLEVELS];  /* buf ptr per level */
249         int             bc_ptrs[XFS_BTREE_MAXLEVELS];   /* key/record # */
250         __uint8_t       bc_ra[XFS_BTREE_MAXLEVELS];     /* readahead bits */
251 #define XFS_BTCUR_LEFTRA        1       /* left sibling has been read-ahead */
252 #define XFS_BTCUR_RIGHTRA       2       /* right sibling has been read-ahead */
253         __uint8_t       bc_nlevels;     /* number of levels in the tree */
254         __uint8_t       bc_blocklog;    /* log2(blocksize) of btree blocks */
255         xfs_btnum_t     bc_btnum;       /* identifies which btree type */
256         union {
257                 struct {                        /* needed for BNO, CNT, INO */
258                         struct xfs_buf  *agbp;  /* agf/agi buffer pointer */
259                         xfs_agnumber_t  agno;   /* ag number */
260                 } a;
261                 struct {                        /* needed for BMAP */
262                         struct xfs_inode *ip;   /* pointer to our inode */
263                         struct xfs_bmap_free *flist;    /* list to free after */
264                         xfs_fsblock_t   firstblock;     /* 1st blk allocated */
265                         int             allocated;      /* count of alloced */
266                         short           forksize;       /* fork's inode space */
267                         char            whichfork;      /* data or attr fork */
268                         char            flags;          /* flags */
269 #define XFS_BTCUR_BPRV_WASDEL   1                       /* was delayed */
270                 } b;
271         }               bc_private;     /* per-btree type data */
272 } xfs_btree_cur_t;
273 
274 /* cursor flags */
275 #define XFS_BTREE_LONG_PTRS             (1<<0)  /* pointers are 64bits long */
276 #define XFS_BTREE_ROOT_IN_INODE         (1<<1)  /* root may be variable size */
277 #define XFS_BTREE_LASTREC_UPDATE        (1<<2)  /* track last rec externally */
278 
279 
280 #define XFS_BTREE_NOERROR       0
281 #define XFS_BTREE_ERROR         1
282 
283 /*
284  * Convert from buffer to btree block header.
285  */
286 #define XFS_BUF_TO_BLOCK(bp)    ((struct xfs_btree_block *)XFS_BUF_PTR(bp))
287 
288 
289 /*
290  * Check that block header is ok.
291  */
292 int
293 xfs_btree_check_block(
294         struct xfs_btree_cur    *cur,   /* btree cursor */
295         struct xfs_btree_block  *block, /* generic btree block pointer */
296         int                     level,  /* level of the btree block */
297         struct xfs_buf          *bp);   /* buffer containing block, if any */
298 
299 /*
300  * Check that (long) pointer is ok.
301  */
302 int                                     /* error (0 or EFSCORRUPTED) */
303 xfs_btree_check_lptr(
304         struct xfs_btree_cur    *cur,   /* btree cursor */
305         xfs_dfsbno_t            ptr,    /* btree block disk address */
306         int                     level); /* btree block level */
307 
308 /*
309  * Delete the btree cursor.
310  */
311 void
312 xfs_btree_del_cursor(
313         xfs_btree_cur_t         *cur,   /* btree cursor */
314         int                     error); /* del because of error */
315 
316 /*
317  * Duplicate the btree cursor.
318  * Allocate a new one, copy the record, re-get the buffers.
319  */
320 int                                     /* error */
321 xfs_btree_dup_cursor(
322         xfs_btree_cur_t         *cur,   /* input cursor */
323         xfs_btree_cur_t         **ncur);/* output cursor */
324 
325 /*
326  * Get a buffer for the block, return it with no data read.
327  * Long-form addressing.
328  */
329 struct xfs_buf *                                /* buffer for fsbno */
330 xfs_btree_get_bufl(
331         struct xfs_mount        *mp,    /* file system mount point */
332         struct xfs_trans        *tp,    /* transaction pointer */
333         xfs_fsblock_t           fsbno,  /* file system block number */
334         uint                    lock);  /* lock flags for get_buf */
335 
336 /*
337  * Get a buffer for the block, return it with no data read.
338  * Short-form addressing.
339  */
340 struct xfs_buf *                                /* buffer for agno/agbno */
341 xfs_btree_get_bufs(
342         struct xfs_mount        *mp,    /* file system mount point */
343         struct xfs_trans        *tp,    /* transaction pointer */
344         xfs_agnumber_t          agno,   /* allocation group number */
345         xfs_agblock_t           agbno,  /* allocation group block number */
346         uint                    lock);  /* lock flags for get_buf */
347 
348 /*
349  * Check for the cursor referring to the last block at the given level.
350  */
351 int                                     /* 1=is last block, 0=not last block */
352 xfs_btree_islastblock(
353         xfs_btree_cur_t         *cur,   /* btree cursor */
354         int                     level); /* level to check */
355 
356 /*
357  * Compute first and last byte offsets for the fields given.
358  * Interprets the offsets table, which contains struct field offsets.
359  */
360 void
361 xfs_btree_offsets(
362         __int64_t               fields, /* bitmask of fields */
363         const short             *offsets,/* table of field offsets */
364         int                     nbits,  /* number of bits to inspect */
365         int                     *first, /* output: first byte offset */
366         int                     *last); /* output: last byte offset */
367 
368 /*
369  * Get a buffer for the block, return it read in.
370  * Long-form addressing.
371  */
372 int                                     /* error */
373 xfs_btree_read_bufl(
374         struct xfs_mount        *mp,    /* file system mount point */
375         struct xfs_trans        *tp,    /* transaction pointer */
376         xfs_fsblock_t           fsbno,  /* file system block number */
377         uint                    lock,   /* lock flags for read_buf */
378         struct xfs_buf          **bpp,  /* buffer for fsbno */
379         int                     refval);/* ref count value for buffer */
380 
381 /*
382  * Read-ahead the block, don't wait for it, don't return a buffer.
383  * Long-form addressing.
384  */
385 void                                    /* error */
386 xfs_btree_reada_bufl(
387         struct xfs_mount        *mp,    /* file system mount point */
388         xfs_fsblock_t           fsbno,  /* file system block number */
389         xfs_extlen_t            count); /* count of filesystem blocks */
390 
391 /*
392  * Read-ahead the block, don't wait for it, don't return a buffer.
393  * Short-form addressing.
394  */
395 void                                    /* error */
396 xfs_btree_reada_bufs(
397         struct xfs_mount        *mp,    /* file system mount point */
398         xfs_agnumber_t          agno,   /* allocation group number */
399         xfs_agblock_t           agbno,  /* allocation group block number */
400         xfs_extlen_t            count); /* count of filesystem blocks */
401 
402 /*
403  * Set the buffer for level "lev" in the cursor to bp, releasing
404  * any previous buffer.
405  */
406 void
407 xfs_btree_setbuf(
408         xfs_btree_cur_t         *cur,   /* btree cursor */
409         int                     lev,    /* level in btree */
410         struct xfs_buf          *bp);   /* new buffer to set */
411 
412 
413 /*
414  * Common btree core entry points.
415  */
416 int xfs_btree_increment(struct xfs_btree_cur *, int, int *);
417 int xfs_btree_decrement(struct xfs_btree_cur *, int, int *);
418 int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *);
419 int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *);
420 int xfs_btree_new_iroot(struct xfs_btree_cur *, int *, int *);
421 int xfs_btree_insert(struct xfs_btree_cur *, int *);
422 int xfs_btree_delete(struct xfs_btree_cur *, int *);
423 int xfs_btree_get_rec(struct xfs_btree_cur *, union xfs_btree_rec **, int *);
424 
425 /*
426  * Internal btree helpers also used by xfs_bmap.c.
427  */
428 void xfs_btree_log_block(struct xfs_btree_cur *, struct xfs_buf *, int);
429 void xfs_btree_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int, int);
430 
431 /*
432  * Helpers.
433  */
434 static inline int xfs_btree_get_numrecs(struct xfs_btree_block *block)
435 {
436         return be16_to_cpu(block->bb_numrecs);
437 }
438 
439 static inline void xfs_btree_set_numrecs(struct xfs_btree_block *block,
440                 __uint16_t numrecs)
441 {
442         block->bb_numrecs = cpu_to_be16(numrecs);
443 }
444 
445 static inline int xfs_btree_get_level(struct xfs_btree_block *block)
446 {
447         return be16_to_cpu(block->bb_level);
448 }
449 
450 
451 /*
452  * Min and max functions for extlen, agblock, fileoff, and filblks types.
453  */
454 #define XFS_EXTLEN_MIN(a,b)     min_t(xfs_extlen_t, (a), (b))
455 #define XFS_EXTLEN_MAX(a,b)     max_t(xfs_extlen_t, (a), (b))
456 #define XFS_AGBLOCK_MIN(a,b)    min_t(xfs_agblock_t, (a), (b))
457 #define XFS_AGBLOCK_MAX(a,b)    max_t(xfs_agblock_t, (a), (b))
458 #define XFS_FILEOFF_MIN(a,b)    min_t(xfs_fileoff_t, (a), (b))
459 #define XFS_FILEOFF_MAX(a,b)    max_t(xfs_fileoff_t, (a), (b))
460 #define XFS_FILBLKS_MIN(a,b)    min_t(xfs_filblks_t, (a), (b))
461 #define XFS_FILBLKS_MAX(a,b)    max_t(xfs_filblks_t, (a), (b))
462 
463 #define XFS_FSB_SANITY_CHECK(mp,fsb)    \
464         (XFS_FSB_TO_AGNO(mp, fsb) < mp->m_sb.sb_agcount && \
465                 XFS_FSB_TO_AGBNO(mp, fsb) < mp->m_sb.sb_agblocks)
466 
467 #endif  /* __XFS_BTREE_H__ */
468 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp