XFS: xfs_trans_add_item() - don't assign in ASSERT() when compare is intended
[linux-2.6.git] / fs / xfs / xfs_bmap_btree.c
1 /*
2  * Copyright (c) 2000-2003,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 #include "xfs.h"
19 #include "xfs_fs.h"
20 #include "xfs_types.h"
21 #include "xfs_bit.h"
22 #include "xfs_log.h"
23 #include "xfs_inum.h"
24 #include "xfs_trans.h"
25 #include "xfs_sb.h"
26 #include "xfs_ag.h"
27 #include "xfs_mount.h"
28 #include "xfs_bmap_btree.h"
29 #include "xfs_alloc_btree.h"
30 #include "xfs_ialloc_btree.h"
31 #include "xfs_dinode.h"
32 #include "xfs_inode.h"
33 #include "xfs_inode_item.h"
34 #include "xfs_alloc.h"
35 #include "xfs_btree.h"
36 #include "xfs_itable.h"
37 #include "xfs_bmap.h"
38 #include "xfs_error.h"
39 #include "xfs_quota.h"
40
41 /*
42  * Determine the extent state.
43  */
44 /* ARGSUSED */
45 STATIC xfs_exntst_t
46 xfs_extent_state(
47         xfs_filblks_t           blks,
48         int                     extent_flag)
49 {
50         if (extent_flag) {
51                 ASSERT(blks != 0);      /* saved for DMIG */
52                 return XFS_EXT_UNWRITTEN;
53         }
54         return XFS_EXT_NORM;
55 }
56
57 /*
58  * Convert on-disk form of btree root to in-memory form.
59  */
60 void
61 xfs_bmdr_to_bmbt(
62         struct xfs_mount        *mp,
63         xfs_bmdr_block_t        *dblock,
64         int                     dblocklen,
65         struct xfs_btree_block  *rblock,
66         int                     rblocklen)
67 {
68         int                     dmxr;
69         xfs_bmbt_key_t          *fkp;
70         __be64                  *fpp;
71         xfs_bmbt_key_t          *tkp;
72         __be64                  *tpp;
73
74         rblock->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
75         rblock->bb_level = dblock->bb_level;
76         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
77         rblock->bb_numrecs = dblock->bb_numrecs;
78         rblock->bb_u.l.bb_leftsib = cpu_to_be64(NULLDFSBNO);
79         rblock->bb_u.l.bb_rightsib = cpu_to_be64(NULLDFSBNO);
80         dmxr = xfs_bmdr_maxrecs(mp, dblocklen, 0);
81         fkp = XFS_BMDR_KEY_ADDR(dblock, 1);
82         tkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1);
83         fpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr);
84         tpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen);
85         dmxr = be16_to_cpu(dblock->bb_numrecs);
86         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
87         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
88 }
89
90 /*
91  * Convert a compressed bmap extent record to an uncompressed form.
92  * This code must be in sync with the routines xfs_bmbt_get_startoff,
93  * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
94  */
95 STATIC void
96 __xfs_bmbt_get_all(
97                 __uint64_t l0,
98                 __uint64_t l1,
99                 xfs_bmbt_irec_t *s)
100 {
101         int     ext_flag;
102         xfs_exntst_t st;
103
104         ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
105         s->br_startoff = ((xfs_fileoff_t)l0 &
106                            xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
107 #if XFS_BIG_BLKNOS
108         s->br_startblock = (((xfs_fsblock_t)l0 & xfs_mask64lo(9)) << 43) |
109                            (((xfs_fsblock_t)l1) >> 21);
110 #else
111 #ifdef DEBUG
112         {
113                 xfs_dfsbno_t    b;
114
115                 b = (((xfs_dfsbno_t)l0 & xfs_mask64lo(9)) << 43) |
116                     (((xfs_dfsbno_t)l1) >> 21);
117                 ASSERT((b >> 32) == 0 || isnulldstartblock(b));
118                 s->br_startblock = (xfs_fsblock_t)b;
119         }
120 #else   /* !DEBUG */
121         s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
122 #endif  /* DEBUG */
123 #endif  /* XFS_BIG_BLKNOS */
124         s->br_blockcount = (xfs_filblks_t)(l1 & xfs_mask64lo(21));
125         /* This is xfs_extent_state() in-line */
126         if (ext_flag) {
127                 ASSERT(s->br_blockcount != 0);  /* saved for DMIG */
128                 st = XFS_EXT_UNWRITTEN;
129         } else
130                 st = XFS_EXT_NORM;
131         s->br_state = st;
132 }
133
134 void
135 xfs_bmbt_get_all(
136         xfs_bmbt_rec_host_t *r,
137         xfs_bmbt_irec_t *s)
138 {
139         __xfs_bmbt_get_all(r->l0, r->l1, s);
140 }
141
142 /*
143  * Extract the blockcount field from an in memory bmap extent record.
144  */
145 xfs_filblks_t
146 xfs_bmbt_get_blockcount(
147         xfs_bmbt_rec_host_t     *r)
148 {
149         return (xfs_filblks_t)(r->l1 & xfs_mask64lo(21));
150 }
151
152 /*
153  * Extract the startblock field from an in memory bmap extent record.
154  */
155 xfs_fsblock_t
156 xfs_bmbt_get_startblock(
157         xfs_bmbt_rec_host_t     *r)
158 {
159 #if XFS_BIG_BLKNOS
160         return (((xfs_fsblock_t)r->l0 & xfs_mask64lo(9)) << 43) |
161                (((xfs_fsblock_t)r->l1) >> 21);
162 #else
163 #ifdef DEBUG
164         xfs_dfsbno_t    b;
165
166         b = (((xfs_dfsbno_t)r->l0 & xfs_mask64lo(9)) << 43) |
167             (((xfs_dfsbno_t)r->l1) >> 21);
168         ASSERT((b >> 32) == 0 || isnulldstartblock(b));
169         return (xfs_fsblock_t)b;
170 #else   /* !DEBUG */
171         return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
172 #endif  /* DEBUG */
173 #endif  /* XFS_BIG_BLKNOS */
174 }
175
176 /*
177  * Extract the startoff field from an in memory bmap extent record.
178  */
179 xfs_fileoff_t
180 xfs_bmbt_get_startoff(
181         xfs_bmbt_rec_host_t     *r)
182 {
183         return ((xfs_fileoff_t)r->l0 &
184                  xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
185 }
186
187 xfs_exntst_t
188 xfs_bmbt_get_state(
189         xfs_bmbt_rec_host_t     *r)
190 {
191         int     ext_flag;
192
193         ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
194         return xfs_extent_state(xfs_bmbt_get_blockcount(r),
195                                 ext_flag);
196 }
197
198 /*
199  * Extract the blockcount field from an on disk bmap extent record.
200  */
201 xfs_filblks_t
202 xfs_bmbt_disk_get_blockcount(
203         xfs_bmbt_rec_t  *r)
204 {
205         return (xfs_filblks_t)(be64_to_cpu(r->l1) & xfs_mask64lo(21));
206 }
207
208 /*
209  * Extract the startoff field from a disk format bmap extent record.
210  */
211 xfs_fileoff_t
212 xfs_bmbt_disk_get_startoff(
213         xfs_bmbt_rec_t  *r)
214 {
215         return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
216                  xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
217 }
218
219
220 /*
221  * Set all the fields in a bmap extent record from the arguments.
222  */
223 void
224 xfs_bmbt_set_allf(
225         xfs_bmbt_rec_host_t     *r,
226         xfs_fileoff_t           startoff,
227         xfs_fsblock_t           startblock,
228         xfs_filblks_t           blockcount,
229         xfs_exntst_t            state)
230 {
231         int             extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
232
233         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
234         ASSERT((startoff & xfs_mask64hi(64-BMBT_STARTOFF_BITLEN)) == 0);
235         ASSERT((blockcount & xfs_mask64hi(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
236
237 #if XFS_BIG_BLKNOS
238         ASSERT((startblock & xfs_mask64hi(64-BMBT_STARTBLOCK_BITLEN)) == 0);
239
240         r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
241                 ((xfs_bmbt_rec_base_t)startoff << 9) |
242                 ((xfs_bmbt_rec_base_t)startblock >> 43);
243         r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
244                 ((xfs_bmbt_rec_base_t)blockcount &
245                 (xfs_bmbt_rec_base_t)xfs_mask64lo(21));
246 #else   /* !XFS_BIG_BLKNOS */
247         if (isnullstartblock(startblock)) {
248                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
249                         ((xfs_bmbt_rec_base_t)startoff << 9) |
250                          (xfs_bmbt_rec_base_t)xfs_mask64lo(9);
251                 r->l1 = xfs_mask64hi(11) |
252                           ((xfs_bmbt_rec_base_t)startblock << 21) |
253                           ((xfs_bmbt_rec_base_t)blockcount &
254                            (xfs_bmbt_rec_base_t)xfs_mask64lo(21));
255         } else {
256                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
257                         ((xfs_bmbt_rec_base_t)startoff << 9);
258                 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
259                          ((xfs_bmbt_rec_base_t)blockcount &
260                          (xfs_bmbt_rec_base_t)xfs_mask64lo(21));
261         }
262 #endif  /* XFS_BIG_BLKNOS */
263 }
264
265 /*
266  * Set all the fields in a bmap extent record from the uncompressed form.
267  */
268 void
269 xfs_bmbt_set_all(
270         xfs_bmbt_rec_host_t *r,
271         xfs_bmbt_irec_t *s)
272 {
273         xfs_bmbt_set_allf(r, s->br_startoff, s->br_startblock,
274                              s->br_blockcount, s->br_state);
275 }
276
277
278 /*
279  * Set all the fields in a disk format bmap extent record from the arguments.
280  */
281 void
282 xfs_bmbt_disk_set_allf(
283         xfs_bmbt_rec_t          *r,
284         xfs_fileoff_t           startoff,
285         xfs_fsblock_t           startblock,
286         xfs_filblks_t           blockcount,
287         xfs_exntst_t            state)
288 {
289         int                     extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
290
291         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
292         ASSERT((startoff & xfs_mask64hi(64-BMBT_STARTOFF_BITLEN)) == 0);
293         ASSERT((blockcount & xfs_mask64hi(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
294
295 #if XFS_BIG_BLKNOS
296         ASSERT((startblock & xfs_mask64hi(64-BMBT_STARTBLOCK_BITLEN)) == 0);
297
298         r->l0 = cpu_to_be64(
299                 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
300                  ((xfs_bmbt_rec_base_t)startoff << 9) |
301                  ((xfs_bmbt_rec_base_t)startblock >> 43));
302         r->l1 = cpu_to_be64(
303                 ((xfs_bmbt_rec_base_t)startblock << 21) |
304                  ((xfs_bmbt_rec_base_t)blockcount &
305                   (xfs_bmbt_rec_base_t)xfs_mask64lo(21)));
306 #else   /* !XFS_BIG_BLKNOS */
307         if (isnullstartblock(startblock)) {
308                 r->l0 = cpu_to_be64(
309                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
310                          ((xfs_bmbt_rec_base_t)startoff << 9) |
311                           (xfs_bmbt_rec_base_t)xfs_mask64lo(9));
312                 r->l1 = cpu_to_be64(xfs_mask64hi(11) |
313                           ((xfs_bmbt_rec_base_t)startblock << 21) |
314                           ((xfs_bmbt_rec_base_t)blockcount &
315                            (xfs_bmbt_rec_base_t)xfs_mask64lo(21)));
316         } else {
317                 r->l0 = cpu_to_be64(
318                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
319                          ((xfs_bmbt_rec_base_t)startoff << 9));
320                 r->l1 = cpu_to_be64(
321                         ((xfs_bmbt_rec_base_t)startblock << 21) |
322                          ((xfs_bmbt_rec_base_t)blockcount &
323                           (xfs_bmbt_rec_base_t)xfs_mask64lo(21)));
324         }
325 #endif  /* XFS_BIG_BLKNOS */
326 }
327
328 /*
329  * Set all the fields in a bmap extent record from the uncompressed form.
330  */
331 STATIC void
332 xfs_bmbt_disk_set_all(
333         xfs_bmbt_rec_t  *r,
334         xfs_bmbt_irec_t *s)
335 {
336         xfs_bmbt_disk_set_allf(r, s->br_startoff, s->br_startblock,
337                                   s->br_blockcount, s->br_state);
338 }
339
340 /*
341  * Set the blockcount field in a bmap extent record.
342  */
343 void
344 xfs_bmbt_set_blockcount(
345         xfs_bmbt_rec_host_t *r,
346         xfs_filblks_t   v)
347 {
348         ASSERT((v & xfs_mask64hi(43)) == 0);
349         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)xfs_mask64hi(43)) |
350                   (xfs_bmbt_rec_base_t)(v & xfs_mask64lo(21));
351 }
352
353 /*
354  * Set the startblock field in a bmap extent record.
355  */
356 void
357 xfs_bmbt_set_startblock(
358         xfs_bmbt_rec_host_t *r,
359         xfs_fsblock_t   v)
360 {
361 #if XFS_BIG_BLKNOS
362         ASSERT((v & xfs_mask64hi(12)) == 0);
363         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)xfs_mask64hi(55)) |
364                   (xfs_bmbt_rec_base_t)(v >> 43);
365         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)xfs_mask64lo(21)) |
366                   (xfs_bmbt_rec_base_t)(v << 21);
367 #else   /* !XFS_BIG_BLKNOS */
368         if (isnullstartblock(v)) {
369                 r->l0 |= (xfs_bmbt_rec_base_t)xfs_mask64lo(9);
370                 r->l1 = (xfs_bmbt_rec_base_t)xfs_mask64hi(11) |
371                           ((xfs_bmbt_rec_base_t)v << 21) |
372                           (r->l1 & (xfs_bmbt_rec_base_t)xfs_mask64lo(21));
373         } else {
374                 r->l0 &= ~(xfs_bmbt_rec_base_t)xfs_mask64lo(9);
375                 r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
376                           (r->l1 & (xfs_bmbt_rec_base_t)xfs_mask64lo(21));
377         }
378 #endif  /* XFS_BIG_BLKNOS */
379 }
380
381 /*
382  * Set the startoff field in a bmap extent record.
383  */
384 void
385 xfs_bmbt_set_startoff(
386         xfs_bmbt_rec_host_t *r,
387         xfs_fileoff_t   v)
388 {
389         ASSERT((v & xfs_mask64hi(9)) == 0);
390         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) xfs_mask64hi(1)) |
391                 ((xfs_bmbt_rec_base_t)v << 9) |
392                   (r->l0 & (xfs_bmbt_rec_base_t)xfs_mask64lo(9));
393 }
394
395 /*
396  * Set the extent state field in a bmap extent record.
397  */
398 void
399 xfs_bmbt_set_state(
400         xfs_bmbt_rec_host_t *r,
401         xfs_exntst_t    v)
402 {
403         ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
404         if (v == XFS_EXT_NORM)
405                 r->l0 &= xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN);
406         else
407                 r->l0 |= xfs_mask64hi(BMBT_EXNTFLAG_BITLEN);
408 }
409
410 /*
411  * Convert in-memory form of btree root to on-disk form.
412  */
413 void
414 xfs_bmbt_to_bmdr(
415         struct xfs_mount        *mp,
416         struct xfs_btree_block  *rblock,
417         int                     rblocklen,
418         xfs_bmdr_block_t        *dblock,
419         int                     dblocklen)
420 {
421         int                     dmxr;
422         xfs_bmbt_key_t          *fkp;
423         __be64                  *fpp;
424         xfs_bmbt_key_t          *tkp;
425         __be64                  *tpp;
426
427         ASSERT(rblock->bb_magic == cpu_to_be32(XFS_BMAP_MAGIC));
428         ASSERT(rblock->bb_u.l.bb_leftsib == cpu_to_be64(NULLDFSBNO));
429         ASSERT(rblock->bb_u.l.bb_rightsib == cpu_to_be64(NULLDFSBNO));
430         ASSERT(rblock->bb_level != 0);
431         dblock->bb_level = rblock->bb_level;
432         dblock->bb_numrecs = rblock->bb_numrecs;
433         dmxr = xfs_bmdr_maxrecs(mp, dblocklen, 0);
434         fkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1);
435         tkp = XFS_BMDR_KEY_ADDR(dblock, 1);
436         fpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen);
437         tpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr);
438         dmxr = be16_to_cpu(dblock->bb_numrecs);
439         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
440         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
441 }
442
443 /*
444  * Check extent records, which have just been read, for
445  * any bit in the extent flag field. ASSERT on debug
446  * kernels, as this condition should not occur.
447  * Return an error condition (1) if any flags found,
448  * otherwise return 0.
449  */
450
451 int
452 xfs_check_nostate_extents(
453         xfs_ifork_t             *ifp,
454         xfs_extnum_t            idx,
455         xfs_extnum_t            num)
456 {
457         for (; num > 0; num--, idx++) {
458                 xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, idx);
459                 if ((ep->l0 >>
460                      (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
461                         ASSERT(0);
462                         return 1;
463                 }
464         }
465         return 0;
466 }
467
468
469 STATIC struct xfs_btree_cur *
470 xfs_bmbt_dup_cursor(
471         struct xfs_btree_cur    *cur)
472 {
473         struct xfs_btree_cur    *new;
474
475         new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp,
476                         cur->bc_private.b.ip, cur->bc_private.b.whichfork);
477
478         /*
479          * Copy the firstblock, flist, and flags values,
480          * since init cursor doesn't get them.
481          */
482         new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
483         new->bc_private.b.flist = cur->bc_private.b.flist;
484         new->bc_private.b.flags = cur->bc_private.b.flags;
485
486         return new;
487 }
488
489 STATIC void
490 xfs_bmbt_update_cursor(
491         struct xfs_btree_cur    *src,
492         struct xfs_btree_cur    *dst)
493 {
494         ASSERT((dst->bc_private.b.firstblock != NULLFSBLOCK) ||
495                (dst->bc_private.b.ip->i_d.di_flags & XFS_DIFLAG_REALTIME));
496         ASSERT(dst->bc_private.b.flist == src->bc_private.b.flist);
497
498         dst->bc_private.b.allocated += src->bc_private.b.allocated;
499         dst->bc_private.b.firstblock = src->bc_private.b.firstblock;
500
501         src->bc_private.b.allocated = 0;
502 }
503
504 STATIC int
505 xfs_bmbt_alloc_block(
506         struct xfs_btree_cur    *cur,
507         union xfs_btree_ptr     *start,
508         union xfs_btree_ptr     *new,
509         int                     length,
510         int                     *stat)
511 {
512         xfs_alloc_arg_t         args;           /* block allocation args */
513         int                     error;          /* error return value */
514
515         memset(&args, 0, sizeof(args));
516         args.tp = cur->bc_tp;
517         args.mp = cur->bc_mp;
518         args.fsbno = cur->bc_private.b.firstblock;
519         args.firstblock = args.fsbno;
520
521         if (args.fsbno == NULLFSBLOCK) {
522                 args.fsbno = be64_to_cpu(start->l);
523                 args.type = XFS_ALLOCTYPE_START_BNO;
524                 /*
525                  * Make sure there is sufficient room left in the AG to
526                  * complete a full tree split for an extent insert.  If
527                  * we are converting the middle part of an extent then
528                  * we may need space for two tree splits.
529                  *
530                  * We are relying on the caller to make the correct block
531                  * reservation for this operation to succeed.  If the
532                  * reservation amount is insufficient then we may fail a
533                  * block allocation here and corrupt the filesystem.
534                  */
535                 args.minleft = xfs_trans_get_block_res(args.tp);
536         } else if (cur->bc_private.b.flist->xbf_low) {
537                 args.type = XFS_ALLOCTYPE_START_BNO;
538         } else {
539                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
540         }
541
542         args.minlen = args.maxlen = args.prod = 1;
543         args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
544         if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
545                 error = XFS_ERROR(ENOSPC);
546                 goto error0;
547         }
548         error = xfs_alloc_vextent(&args);
549         if (error)
550                 goto error0;
551
552         if (args.fsbno == NULLFSBLOCK && args.minleft) {
553                 /*
554                  * Could not find an AG with enough free space to satisfy
555                  * a full btree split.  Try again without minleft and if
556                  * successful activate the lowspace algorithm.
557                  */
558                 args.fsbno = 0;
559                 args.type = XFS_ALLOCTYPE_FIRST_AG;
560                 args.minleft = 0;
561                 error = xfs_alloc_vextent(&args);
562                 if (error)
563                         goto error0;
564                 cur->bc_private.b.flist->xbf_low = 1;
565         }
566         if (args.fsbno == NULLFSBLOCK) {
567                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
568                 *stat = 0;
569                 return 0;
570         }
571         ASSERT(args.len == 1);
572         cur->bc_private.b.firstblock = args.fsbno;
573         cur->bc_private.b.allocated++;
574         cur->bc_private.b.ip->i_d.di_nblocks++;
575         xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
576         xfs_trans_mod_dquot_byino(args.tp, cur->bc_private.b.ip,
577                         XFS_TRANS_DQ_BCOUNT, 1L);
578
579         new->l = cpu_to_be64(args.fsbno);
580
581         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
582         *stat = 1;
583         return 0;
584
585  error0:
586         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
587         return error;
588 }
589
590 STATIC int
591 xfs_bmbt_free_block(
592         struct xfs_btree_cur    *cur,
593         struct xfs_buf          *bp)
594 {
595         struct xfs_mount        *mp = cur->bc_mp;
596         struct xfs_inode        *ip = cur->bc_private.b.ip;
597         struct xfs_trans        *tp = cur->bc_tp;
598         xfs_fsblock_t           fsbno = XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(bp));
599
600         xfs_bmap_add_free(fsbno, 1, cur->bc_private.b.flist, mp);
601         ip->i_d.di_nblocks--;
602
603         xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
604         xfs_trans_mod_dquot_byino(tp, ip, XFS_TRANS_DQ_BCOUNT, -1L);
605         xfs_trans_binval(tp, bp);
606         return 0;
607 }
608
609 STATIC int
610 xfs_bmbt_get_minrecs(
611         struct xfs_btree_cur    *cur,
612         int                     level)
613 {
614         if (level == cur->bc_nlevels - 1) {
615                 struct xfs_ifork        *ifp;
616
617                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
618                                     cur->bc_private.b.whichfork);
619
620                 return xfs_bmbt_maxrecs(cur->bc_mp,
621                                         ifp->if_broot_bytes, level == 0) / 2;
622         }
623
624         return cur->bc_mp->m_bmap_dmnr[level != 0];
625 }
626
627 int
628 xfs_bmbt_get_maxrecs(
629         struct xfs_btree_cur    *cur,
630         int                     level)
631 {
632         if (level == cur->bc_nlevels - 1) {
633                 struct xfs_ifork        *ifp;
634
635                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
636                                     cur->bc_private.b.whichfork);
637
638                 return xfs_bmbt_maxrecs(cur->bc_mp,
639                                         ifp->if_broot_bytes, level == 0);
640         }
641
642         return cur->bc_mp->m_bmap_dmxr[level != 0];
643
644 }
645
646 /*
647  * Get the maximum records we could store in the on-disk format.
648  *
649  * For non-root nodes this is equivalent to xfs_bmbt_get_maxrecs, but
650  * for the root node this checks the available space in the dinode fork
651  * so that we can resize the in-memory buffer to match it.  After a
652  * resize to the maximum size this function returns the same value
653  * as xfs_bmbt_get_maxrecs for the root node, too.
654  */
655 STATIC int
656 xfs_bmbt_get_dmaxrecs(
657         struct xfs_btree_cur    *cur,
658         int                     level)
659 {
660         if (level != cur->bc_nlevels - 1)
661                 return cur->bc_mp->m_bmap_dmxr[level != 0];
662         return xfs_bmdr_maxrecs(cur->bc_mp, cur->bc_private.b.forksize,
663                                 level == 0);
664 }
665
666 STATIC void
667 xfs_bmbt_init_key_from_rec(
668         union xfs_btree_key     *key,
669         union xfs_btree_rec     *rec)
670 {
671         key->bmbt.br_startoff =
672                 cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt));
673 }
674
675 STATIC void
676 xfs_bmbt_init_rec_from_key(
677         union xfs_btree_key     *key,
678         union xfs_btree_rec     *rec)
679 {
680         ASSERT(key->bmbt.br_startoff != 0);
681
682         xfs_bmbt_disk_set_allf(&rec->bmbt, be64_to_cpu(key->bmbt.br_startoff),
683                                0, 0, XFS_EXT_NORM);
684 }
685
686 STATIC void
687 xfs_bmbt_init_rec_from_cur(
688         struct xfs_btree_cur    *cur,
689         union xfs_btree_rec     *rec)
690 {
691         xfs_bmbt_disk_set_all(&rec->bmbt, &cur->bc_rec.b);
692 }
693
694 STATIC void
695 xfs_bmbt_init_ptr_from_cur(
696         struct xfs_btree_cur    *cur,
697         union xfs_btree_ptr     *ptr)
698 {
699         ptr->l = 0;
700 }
701
702 STATIC __int64_t
703 xfs_bmbt_key_diff(
704         struct xfs_btree_cur    *cur,
705         union xfs_btree_key     *key)
706 {
707         return (__int64_t)be64_to_cpu(key->bmbt.br_startoff) -
708                                       cur->bc_rec.b.br_startoff;
709 }
710
711 #ifdef DEBUG
712 STATIC int
713 xfs_bmbt_keys_inorder(
714         struct xfs_btree_cur    *cur,
715         union xfs_btree_key     *k1,
716         union xfs_btree_key     *k2)
717 {
718         return be64_to_cpu(k1->bmbt.br_startoff) <
719                 be64_to_cpu(k2->bmbt.br_startoff);
720 }
721
722 STATIC int
723 xfs_bmbt_recs_inorder(
724         struct xfs_btree_cur    *cur,
725         union xfs_btree_rec     *r1,
726         union xfs_btree_rec     *r2)
727 {
728         return xfs_bmbt_disk_get_startoff(&r1->bmbt) +
729                 xfs_bmbt_disk_get_blockcount(&r1->bmbt) <=
730                 xfs_bmbt_disk_get_startoff(&r2->bmbt);
731 }
732 #endif  /* DEBUG */
733
734 static const struct xfs_btree_ops xfs_bmbt_ops = {
735         .rec_len                = sizeof(xfs_bmbt_rec_t),
736         .key_len                = sizeof(xfs_bmbt_key_t),
737
738         .dup_cursor             = xfs_bmbt_dup_cursor,
739         .update_cursor          = xfs_bmbt_update_cursor,
740         .alloc_block            = xfs_bmbt_alloc_block,
741         .free_block             = xfs_bmbt_free_block,
742         .get_maxrecs            = xfs_bmbt_get_maxrecs,
743         .get_minrecs            = xfs_bmbt_get_minrecs,
744         .get_dmaxrecs           = xfs_bmbt_get_dmaxrecs,
745         .init_key_from_rec      = xfs_bmbt_init_key_from_rec,
746         .init_rec_from_key      = xfs_bmbt_init_rec_from_key,
747         .init_rec_from_cur      = xfs_bmbt_init_rec_from_cur,
748         .init_ptr_from_cur      = xfs_bmbt_init_ptr_from_cur,
749         .key_diff               = xfs_bmbt_key_diff,
750 #ifdef DEBUG
751         .keys_inorder           = xfs_bmbt_keys_inorder,
752         .recs_inorder           = xfs_bmbt_recs_inorder,
753 #endif
754 };
755
756 /*
757  * Allocate a new bmap btree cursor.
758  */
759 struct xfs_btree_cur *                          /* new bmap btree cursor */
760 xfs_bmbt_init_cursor(
761         struct xfs_mount        *mp,            /* file system mount point */
762         struct xfs_trans        *tp,            /* transaction pointer */
763         struct xfs_inode        *ip,            /* inode owning the btree */
764         int                     whichfork)      /* data or attr fork */
765 {
766         struct xfs_ifork        *ifp = XFS_IFORK_PTR(ip, whichfork);
767         struct xfs_btree_cur    *cur;
768
769         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
770
771         cur->bc_tp = tp;
772         cur->bc_mp = mp;
773         cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
774         cur->bc_btnum = XFS_BTNUM_BMAP;
775         cur->bc_blocklog = mp->m_sb.sb_blocklog;
776
777         cur->bc_ops = &xfs_bmbt_ops;
778         cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE;
779
780         cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
781         cur->bc_private.b.ip = ip;
782         cur->bc_private.b.firstblock = NULLFSBLOCK;
783         cur->bc_private.b.flist = NULL;
784         cur->bc_private.b.allocated = 0;
785         cur->bc_private.b.flags = 0;
786         cur->bc_private.b.whichfork = whichfork;
787
788         return cur;
789 }
790
791 /*
792  * Calculate number of records in a bmap btree block.
793  */
794 int
795 xfs_bmbt_maxrecs(
796         struct xfs_mount        *mp,
797         int                     blocklen,
798         int                     leaf)
799 {
800         blocklen -= XFS_BMBT_BLOCK_LEN(mp);
801
802         if (leaf)
803                 return blocklen / sizeof(xfs_bmbt_rec_t);
804         return blocklen / (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t));
805 }
806
807 /*
808  * Calculate number of records in a bmap btree inode root.
809  */
810 int
811 xfs_bmdr_maxrecs(
812         struct xfs_mount        *mp,
813         int                     blocklen,
814         int                     leaf)
815 {
816         blocklen -= sizeof(xfs_bmdr_block_t);
817
818         if (leaf)
819                 return blocklen / sizeof(xfs_bmdr_rec_t);
820         return blocklen / (sizeof(xfs_bmdr_key_t) + sizeof(xfs_bmdr_ptr_t));
821 }