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

TOMOYO Linux Cross Reference
Linux/fs/xfs/libxfs/xfs_alloc_btree.c

Version: ~ [ linux-5.8-rc3 ] ~ [ linux-5.7.5 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.48 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.129 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.185 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.228 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.228 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ 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-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 // SPDX-License-Identifier: GPL-2.0
  2 /*
  3  * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
  4  * All Rights Reserved.
  5  */
  6 #include "xfs.h"
  7 #include "xfs_fs.h"
  8 #include "xfs_shared.h"
  9 #include "xfs_format.h"
 10 #include "xfs_log_format.h"
 11 #include "xfs_trans_resv.h"
 12 #include "xfs_sb.h"
 13 #include "xfs_mount.h"
 14 #include "xfs_btree.h"
 15 #include "xfs_alloc_btree.h"
 16 #include "xfs_alloc.h"
 17 #include "xfs_extent_busy.h"
 18 #include "xfs_error.h"
 19 #include "xfs_trace.h"
 20 #include "xfs_cksum.h"
 21 #include "xfs_trans.h"
 22 
 23 
 24 STATIC struct xfs_btree_cur *
 25 xfs_allocbt_dup_cursor(
 26         struct xfs_btree_cur    *cur)
 27 {
 28         return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp,
 29                         cur->bc_private.a.agbp, cur->bc_private.a.agno,
 30                         cur->bc_btnum);
 31 }
 32 
 33 STATIC void
 34 xfs_allocbt_set_root(
 35         struct xfs_btree_cur    *cur,
 36         union xfs_btree_ptr     *ptr,
 37         int                     inc)
 38 {
 39         struct xfs_buf          *agbp = cur->bc_private.a.agbp;
 40         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
 41         xfs_agnumber_t          seqno = be32_to_cpu(agf->agf_seqno);
 42         int                     btnum = cur->bc_btnum;
 43         struct xfs_perag        *pag = xfs_perag_get(cur->bc_mp, seqno);
 44 
 45         ASSERT(ptr->s != 0);
 46 
 47         agf->agf_roots[btnum] = ptr->s;
 48         be32_add_cpu(&agf->agf_levels[btnum], inc);
 49         pag->pagf_levels[btnum] += inc;
 50         xfs_perag_put(pag);
 51 
 52         xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);
 53 }
 54 
 55 STATIC int
 56 xfs_allocbt_alloc_block(
 57         struct xfs_btree_cur    *cur,
 58         union xfs_btree_ptr     *start,
 59         union xfs_btree_ptr     *new,
 60         int                     *stat)
 61 {
 62         int                     error;
 63         xfs_agblock_t           bno;
 64 
 65         /* Allocate the new block from the freelist. If we can't, give up.  */
 66         error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
 67                                        &bno, 1);
 68         if (error)
 69                 return error;
 70 
 71         if (bno == NULLAGBLOCK) {
 72                 *stat = 0;
 73                 return 0;
 74         }
 75 
 76         xfs_extent_busy_reuse(cur->bc_mp, cur->bc_private.a.agno, bno, 1, false);
 77 
 78         xfs_trans_agbtree_delta(cur->bc_tp, 1);
 79         new->s = cpu_to_be32(bno);
 80 
 81         *stat = 1;
 82         return 0;
 83 }
 84 
 85 STATIC int
 86 xfs_allocbt_free_block(
 87         struct xfs_btree_cur    *cur,
 88         struct xfs_buf          *bp)
 89 {
 90         struct xfs_buf          *agbp = cur->bc_private.a.agbp;
 91         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
 92         xfs_agblock_t           bno;
 93         int                     error;
 94 
 95         bno = xfs_daddr_to_agbno(cur->bc_mp, XFS_BUF_ADDR(bp));
 96         error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1);
 97         if (error)
 98                 return error;
 99 
100         xfs_extent_busy_insert(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1,
101                               XFS_EXTENT_BUSY_SKIP_DISCARD);
102         xfs_trans_agbtree_delta(cur->bc_tp, -1);
103         return 0;
104 }
105 
106 /*
107  * Update the longest extent in the AGF
108  */
109 STATIC void
110 xfs_allocbt_update_lastrec(
111         struct xfs_btree_cur    *cur,
112         struct xfs_btree_block  *block,
113         union xfs_btree_rec     *rec,
114         int                     ptr,
115         int                     reason)
116 {
117         struct xfs_agf          *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
118         xfs_agnumber_t          seqno = be32_to_cpu(agf->agf_seqno);
119         struct xfs_perag        *pag;
120         __be32                  len;
121         int                     numrecs;
122 
123         ASSERT(cur->bc_btnum == XFS_BTNUM_CNT);
124 
125         switch (reason) {
126         case LASTREC_UPDATE:
127                 /*
128                  * If this is the last leaf block and it's the last record,
129                  * then update the size of the longest extent in the AG.
130                  */
131                 if (ptr != xfs_btree_get_numrecs(block))
132                         return;
133                 len = rec->alloc.ar_blockcount;
134                 break;
135         case LASTREC_INSREC:
136                 if (be32_to_cpu(rec->alloc.ar_blockcount) <=
137                     be32_to_cpu(agf->agf_longest))
138                         return;
139                 len = rec->alloc.ar_blockcount;
140                 break;
141         case LASTREC_DELREC:
142                 numrecs = xfs_btree_get_numrecs(block);
143                 if (ptr <= numrecs)
144                         return;
145                 ASSERT(ptr == numrecs + 1);
146 
147                 if (numrecs) {
148                         xfs_alloc_rec_t *rrp;
149 
150                         rrp = XFS_ALLOC_REC_ADDR(cur->bc_mp, block, numrecs);
151                         len = rrp->ar_blockcount;
152                 } else {
153                         len = 0;
154                 }
155 
156                 break;
157         default:
158                 ASSERT(0);
159                 return;
160         }
161 
162         agf->agf_longest = len;
163         pag = xfs_perag_get(cur->bc_mp, seqno);
164         pag->pagf_longest = be32_to_cpu(len);
165         xfs_perag_put(pag);
166         xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp, XFS_AGF_LONGEST);
167 }
168 
169 STATIC int
170 xfs_allocbt_get_minrecs(
171         struct xfs_btree_cur    *cur,
172         int                     level)
173 {
174         return cur->bc_mp->m_alloc_mnr[level != 0];
175 }
176 
177 STATIC int
178 xfs_allocbt_get_maxrecs(
179         struct xfs_btree_cur    *cur,
180         int                     level)
181 {
182         return cur->bc_mp->m_alloc_mxr[level != 0];
183 }
184 
185 STATIC void
186 xfs_allocbt_init_key_from_rec(
187         union xfs_btree_key     *key,
188         union xfs_btree_rec     *rec)
189 {
190         key->alloc.ar_startblock = rec->alloc.ar_startblock;
191         key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
192 }
193 
194 STATIC void
195 xfs_bnobt_init_high_key_from_rec(
196         union xfs_btree_key     *key,
197         union xfs_btree_rec     *rec)
198 {
199         __u32                   x;
200 
201         x = be32_to_cpu(rec->alloc.ar_startblock);
202         x += be32_to_cpu(rec->alloc.ar_blockcount) - 1;
203         key->alloc.ar_startblock = cpu_to_be32(x);
204         key->alloc.ar_blockcount = 0;
205 }
206 
207 STATIC void
208 xfs_cntbt_init_high_key_from_rec(
209         union xfs_btree_key     *key,
210         union xfs_btree_rec     *rec)
211 {
212         key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
213         key->alloc.ar_startblock = 0;
214 }
215 
216 STATIC void
217 xfs_allocbt_init_rec_from_cur(
218         struct xfs_btree_cur    *cur,
219         union xfs_btree_rec     *rec)
220 {
221         rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
222         rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
223 }
224 
225 STATIC void
226 xfs_allocbt_init_ptr_from_cur(
227         struct xfs_btree_cur    *cur,
228         union xfs_btree_ptr     *ptr)
229 {
230         struct xfs_agf          *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
231 
232         ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno));
233 
234         ptr->s = agf->agf_roots[cur->bc_btnum];
235 }
236 
237 STATIC int64_t
238 xfs_bnobt_key_diff(
239         struct xfs_btree_cur    *cur,
240         union xfs_btree_key     *key)
241 {
242         xfs_alloc_rec_incore_t  *rec = &cur->bc_rec.a;
243         xfs_alloc_key_t         *kp = &key->alloc;
244 
245         return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
246 }
247 
248 STATIC int64_t
249 xfs_cntbt_key_diff(
250         struct xfs_btree_cur    *cur,
251         union xfs_btree_key     *key)
252 {
253         xfs_alloc_rec_incore_t  *rec = &cur->bc_rec.a;
254         xfs_alloc_key_t         *kp = &key->alloc;
255         int64_t                 diff;
256 
257         diff = (int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount;
258         if (diff)
259                 return diff;
260 
261         return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
262 }
263 
264 STATIC int64_t
265 xfs_bnobt_diff_two_keys(
266         struct xfs_btree_cur    *cur,
267         union xfs_btree_key     *k1,
268         union xfs_btree_key     *k2)
269 {
270         return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) -
271                           be32_to_cpu(k2->alloc.ar_startblock);
272 }
273 
274 STATIC int64_t
275 xfs_cntbt_diff_two_keys(
276         struct xfs_btree_cur    *cur,
277         union xfs_btree_key     *k1,
278         union xfs_btree_key     *k2)
279 {
280         int64_t                 diff;
281 
282         diff =  be32_to_cpu(k1->alloc.ar_blockcount) -
283                 be32_to_cpu(k2->alloc.ar_blockcount);
284         if (diff)
285                 return diff;
286 
287         return  be32_to_cpu(k1->alloc.ar_startblock) -
288                 be32_to_cpu(k2->alloc.ar_startblock);
289 }
290 
291 static xfs_failaddr_t
292 xfs_allocbt_verify(
293         struct xfs_buf          *bp)
294 {
295         struct xfs_mount        *mp = bp->b_target->bt_mount;
296         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
297         struct xfs_perag        *pag = bp->b_pag;
298         xfs_failaddr_t          fa;
299         unsigned int            level;
300 
301         /*
302          * magic number and level verification
303          *
304          * During growfs operations, we can't verify the exact level or owner as
305          * the perag is not fully initialised and hence not attached to the
306          * buffer.  In this case, check against the maximum tree depth.
307          *
308          * Similarly, during log recovery we will have a perag structure
309          * attached, but the agf information will not yet have been initialised
310          * from the on disk AGF. Again, we can only check against maximum limits
311          * in this case.
312          */
313         level = be16_to_cpu(block->bb_level);
314         switch (block->bb_magic) {
315         case cpu_to_be32(XFS_ABTB_CRC_MAGIC):
316                 fa = xfs_btree_sblock_v5hdr_verify(bp);
317                 if (fa)
318                         return fa;
319                 /* fall through */
320         case cpu_to_be32(XFS_ABTB_MAGIC):
321                 if (pag && pag->pagf_init) {
322                         if (level >= pag->pagf_levels[XFS_BTNUM_BNOi])
323                                 return __this_address;
324                 } else if (level >= mp->m_ag_maxlevels)
325                         return __this_address;
326                 break;
327         case cpu_to_be32(XFS_ABTC_CRC_MAGIC):
328                 fa = xfs_btree_sblock_v5hdr_verify(bp);
329                 if (fa)
330                         return fa;
331                 /* fall through */
332         case cpu_to_be32(XFS_ABTC_MAGIC):
333                 if (pag && pag->pagf_init) {
334                         if (level >= pag->pagf_levels[XFS_BTNUM_CNTi])
335                                 return __this_address;
336                 } else if (level >= mp->m_ag_maxlevels)
337                         return __this_address;
338                 break;
339         default:
340                 return __this_address;
341         }
342 
343         return xfs_btree_sblock_verify(bp, mp->m_alloc_mxr[level != 0]);
344 }
345 
346 static void
347 xfs_allocbt_read_verify(
348         struct xfs_buf  *bp)
349 {
350         xfs_failaddr_t  fa;
351 
352         if (!xfs_btree_sblock_verify_crc(bp))
353                 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
354         else {
355                 fa = xfs_allocbt_verify(bp);
356                 if (fa)
357                         xfs_verifier_error(bp, -EFSCORRUPTED, fa);
358         }
359 
360         if (bp->b_error)
361                 trace_xfs_btree_corrupt(bp, _RET_IP_);
362 }
363 
364 static void
365 xfs_allocbt_write_verify(
366         struct xfs_buf  *bp)
367 {
368         xfs_failaddr_t  fa;
369 
370         fa = xfs_allocbt_verify(bp);
371         if (fa) {
372                 trace_xfs_btree_corrupt(bp, _RET_IP_);
373                 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
374                 return;
375         }
376         xfs_btree_sblock_calc_crc(bp);
377 
378 }
379 
380 const struct xfs_buf_ops xfs_allocbt_buf_ops = {
381         .name = "xfs_allocbt",
382         .verify_read = xfs_allocbt_read_verify,
383         .verify_write = xfs_allocbt_write_verify,
384         .verify_struct = xfs_allocbt_verify,
385 };
386 
387 
388 STATIC int
389 xfs_bnobt_keys_inorder(
390         struct xfs_btree_cur    *cur,
391         union xfs_btree_key     *k1,
392         union xfs_btree_key     *k2)
393 {
394         return be32_to_cpu(k1->alloc.ar_startblock) <
395                be32_to_cpu(k2->alloc.ar_startblock);
396 }
397 
398 STATIC int
399 xfs_bnobt_recs_inorder(
400         struct xfs_btree_cur    *cur,
401         union xfs_btree_rec     *r1,
402         union xfs_btree_rec     *r2)
403 {
404         return be32_to_cpu(r1->alloc.ar_startblock) +
405                 be32_to_cpu(r1->alloc.ar_blockcount) <=
406                 be32_to_cpu(r2->alloc.ar_startblock);
407 }
408 
409 STATIC int
410 xfs_cntbt_keys_inorder(
411         struct xfs_btree_cur    *cur,
412         union xfs_btree_key     *k1,
413         union xfs_btree_key     *k2)
414 {
415         return be32_to_cpu(k1->alloc.ar_blockcount) <
416                 be32_to_cpu(k2->alloc.ar_blockcount) ||
417                 (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount &&
418                  be32_to_cpu(k1->alloc.ar_startblock) <
419                  be32_to_cpu(k2->alloc.ar_startblock));
420 }
421 
422 STATIC int
423 xfs_cntbt_recs_inorder(
424         struct xfs_btree_cur    *cur,
425         union xfs_btree_rec     *r1,
426         union xfs_btree_rec     *r2)
427 {
428         return be32_to_cpu(r1->alloc.ar_blockcount) <
429                 be32_to_cpu(r2->alloc.ar_blockcount) ||
430                 (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount &&
431                  be32_to_cpu(r1->alloc.ar_startblock) <
432                  be32_to_cpu(r2->alloc.ar_startblock));
433 }
434 
435 static const struct xfs_btree_ops xfs_bnobt_ops = {
436         .rec_len                = sizeof(xfs_alloc_rec_t),
437         .key_len                = sizeof(xfs_alloc_key_t),
438 
439         .dup_cursor             = xfs_allocbt_dup_cursor,
440         .set_root               = xfs_allocbt_set_root,
441         .alloc_block            = xfs_allocbt_alloc_block,
442         .free_block             = xfs_allocbt_free_block,
443         .update_lastrec         = xfs_allocbt_update_lastrec,
444         .get_minrecs            = xfs_allocbt_get_minrecs,
445         .get_maxrecs            = xfs_allocbt_get_maxrecs,
446         .init_key_from_rec      = xfs_allocbt_init_key_from_rec,
447         .init_high_key_from_rec = xfs_bnobt_init_high_key_from_rec,
448         .init_rec_from_cur      = xfs_allocbt_init_rec_from_cur,
449         .init_ptr_from_cur      = xfs_allocbt_init_ptr_from_cur,
450         .key_diff               = xfs_bnobt_key_diff,
451         .buf_ops                = &xfs_allocbt_buf_ops,
452         .diff_two_keys          = xfs_bnobt_diff_two_keys,
453         .keys_inorder           = xfs_bnobt_keys_inorder,
454         .recs_inorder           = xfs_bnobt_recs_inorder,
455 };
456 
457 static const struct xfs_btree_ops xfs_cntbt_ops = {
458         .rec_len                = sizeof(xfs_alloc_rec_t),
459         .key_len                = sizeof(xfs_alloc_key_t),
460 
461         .dup_cursor             = xfs_allocbt_dup_cursor,
462         .set_root               = xfs_allocbt_set_root,
463         .alloc_block            = xfs_allocbt_alloc_block,
464         .free_block             = xfs_allocbt_free_block,
465         .update_lastrec         = xfs_allocbt_update_lastrec,
466         .get_minrecs            = xfs_allocbt_get_minrecs,
467         .get_maxrecs            = xfs_allocbt_get_maxrecs,
468         .init_key_from_rec      = xfs_allocbt_init_key_from_rec,
469         .init_high_key_from_rec = xfs_cntbt_init_high_key_from_rec,
470         .init_rec_from_cur      = xfs_allocbt_init_rec_from_cur,
471         .init_ptr_from_cur      = xfs_allocbt_init_ptr_from_cur,
472         .key_diff               = xfs_cntbt_key_diff,
473         .buf_ops                = &xfs_allocbt_buf_ops,
474         .diff_two_keys          = xfs_cntbt_diff_two_keys,
475         .keys_inorder           = xfs_cntbt_keys_inorder,
476         .recs_inorder           = xfs_cntbt_recs_inorder,
477 };
478 
479 /*
480  * Allocate a new allocation btree cursor.
481  */
482 struct xfs_btree_cur *                  /* new alloc btree cursor */
483 xfs_allocbt_init_cursor(
484         struct xfs_mount        *mp,            /* file system mount point */
485         struct xfs_trans        *tp,            /* transaction pointer */
486         struct xfs_buf          *agbp,          /* buffer for agf structure */
487         xfs_agnumber_t          agno,           /* allocation group number */
488         xfs_btnum_t             btnum)          /* btree identifier */
489 {
490         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
491         struct xfs_btree_cur    *cur;
492 
493         ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT);
494 
495         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS);
496 
497         cur->bc_tp = tp;
498         cur->bc_mp = mp;
499         cur->bc_btnum = btnum;
500         cur->bc_blocklog = mp->m_sb.sb_blocklog;
501 
502         if (btnum == XFS_BTNUM_CNT) {
503                 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtc_2);
504                 cur->bc_ops = &xfs_cntbt_ops;
505                 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]);
506                 cur->bc_flags = XFS_BTREE_LASTREC_UPDATE;
507         } else {
508                 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtb_2);
509                 cur->bc_ops = &xfs_bnobt_ops;
510                 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]);
511         }
512 
513         cur->bc_private.a.agbp = agbp;
514         cur->bc_private.a.agno = agno;
515 
516         if (xfs_sb_version_hascrc(&mp->m_sb))
517                 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
518 
519         return cur;
520 }
521 
522 /*
523  * Calculate number of records in an alloc btree block.
524  */
525 int
526 xfs_allocbt_maxrecs(
527         struct xfs_mount        *mp,
528         int                     blocklen,
529         int                     leaf)
530 {
531         blocklen -= XFS_ALLOC_BLOCK_LEN(mp);
532 
533         if (leaf)
534                 return blocklen / sizeof(xfs_alloc_rec_t);
535         return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t));
536 }
537 
538 /* Calculate the freespace btree size for some records. */
539 xfs_extlen_t
540 xfs_allocbt_calc_size(
541         struct xfs_mount        *mp,
542         unsigned long long      len)
543 {
544         return xfs_btree_calc_size(mp->m_alloc_mnr, len);
545 }
546 

~ [ 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