[XFS] endianess annotations for xfs_inobt_rec_t / xfs_inobt_key_t
[linux-2.6.git] / fs / xfs / xfs_ialloc.c
1 /*
2  * Copyright (c) 2000-2002,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_dir2.h"
28 #include "xfs_dmapi.h"
29 #include "xfs_mount.h"
30 #include "xfs_bmap_btree.h"
31 #include "xfs_alloc_btree.h"
32 #include "xfs_ialloc_btree.h"
33 #include "xfs_dir2_sf.h"
34 #include "xfs_attr_sf.h"
35 #include "xfs_dinode.h"
36 #include "xfs_inode.h"
37 #include "xfs_btree.h"
38 #include "xfs_ialloc.h"
39 #include "xfs_alloc.h"
40 #include "xfs_rtalloc.h"
41 #include "xfs_error.h"
42 #include "xfs_bmap.h"
43
44 /*
45  * Log specified fields for the inode given by bp and off.
46  */
47 STATIC void
48 xfs_ialloc_log_di(
49         xfs_trans_t     *tp,            /* transaction pointer */
50         xfs_buf_t       *bp,            /* inode buffer */
51         int             off,            /* index of inode in buffer */
52         int             fields)         /* bitmask of fields to log */
53 {
54         int                     first;          /* first byte number */
55         int                     ioffset;        /* off in bytes */
56         int                     last;           /* last byte number */
57         xfs_mount_t             *mp;            /* mount point structure */
58         static const short      offsets[] = {   /* field offsets */
59                                                 /* keep in sync with bits */
60                 offsetof(xfs_dinode_core_t, di_magic),
61                 offsetof(xfs_dinode_core_t, di_mode),
62                 offsetof(xfs_dinode_core_t, di_version),
63                 offsetof(xfs_dinode_core_t, di_format),
64                 offsetof(xfs_dinode_core_t, di_onlink),
65                 offsetof(xfs_dinode_core_t, di_uid),
66                 offsetof(xfs_dinode_core_t, di_gid),
67                 offsetof(xfs_dinode_core_t, di_nlink),
68                 offsetof(xfs_dinode_core_t, di_projid),
69                 offsetof(xfs_dinode_core_t, di_pad),
70                 offsetof(xfs_dinode_core_t, di_atime),
71                 offsetof(xfs_dinode_core_t, di_mtime),
72                 offsetof(xfs_dinode_core_t, di_ctime),
73                 offsetof(xfs_dinode_core_t, di_size),
74                 offsetof(xfs_dinode_core_t, di_nblocks),
75                 offsetof(xfs_dinode_core_t, di_extsize),
76                 offsetof(xfs_dinode_core_t, di_nextents),
77                 offsetof(xfs_dinode_core_t, di_anextents),
78                 offsetof(xfs_dinode_core_t, di_forkoff),
79                 offsetof(xfs_dinode_core_t, di_aformat),
80                 offsetof(xfs_dinode_core_t, di_dmevmask),
81                 offsetof(xfs_dinode_core_t, di_dmstate),
82                 offsetof(xfs_dinode_core_t, di_flags),
83                 offsetof(xfs_dinode_core_t, di_gen),
84                 offsetof(xfs_dinode_t, di_next_unlinked),
85                 offsetof(xfs_dinode_t, di_u),
86                 offsetof(xfs_dinode_t, di_a),
87                 sizeof(xfs_dinode_t)
88         };
89
90
91         ASSERT(offsetof(xfs_dinode_t, di_core) == 0);
92         ASSERT((fields & (XFS_DI_U|XFS_DI_A)) == 0);
93         mp = tp->t_mountp;
94         /*
95          * Get the inode-relative first and last bytes for these fields
96          */
97         xfs_btree_offsets(fields, offsets, XFS_DI_NUM_BITS, &first, &last);
98         /*
99          * Convert to buffer offsets and log it.
100          */
101         ioffset = off << mp->m_sb.sb_inodelog;
102         first += ioffset;
103         last += ioffset;
104         xfs_trans_log_buf(tp, bp, first, last);
105 }
106
107 /*
108  * Allocation group level functions.
109  */
110
111 /*
112  * Allocate new inodes in the allocation group specified by agbp.
113  * Return 0 for success, else error code.
114  */
115 STATIC int                              /* error code or 0 */
116 xfs_ialloc_ag_alloc(
117         xfs_trans_t     *tp,            /* transaction pointer */
118         xfs_buf_t       *agbp,          /* alloc group buffer */
119         int             *alloc)
120 {
121         xfs_agi_t       *agi;           /* allocation group header */
122         xfs_alloc_arg_t args;           /* allocation argument structure */
123         int             blks_per_cluster;  /* fs blocks per inode cluster */
124         xfs_btree_cur_t *cur;           /* inode btree cursor */
125         xfs_daddr_t     d;              /* disk addr of buffer */
126         int             error;
127         xfs_buf_t       *fbuf;          /* new free inodes' buffer */
128         xfs_dinode_t    *free;          /* new free inode structure */
129         int             i;              /* inode counter */
130         int             j;              /* block counter */
131         int             nbufs;          /* num bufs of new inodes */
132         xfs_agino_t     newino;         /* new first inode's number */
133         xfs_agino_t     newlen;         /* new number of inodes */
134         int             ninodes;        /* num inodes per buf */
135         xfs_agino_t     thisino;        /* current inode number, for loop */
136         int             version;        /* inode version number to use */
137         int             isaligned = 0;  /* inode allocation at stripe unit */
138                                         /* boundary */
139
140         args.tp = tp;
141         args.mp = tp->t_mountp;
142
143         /*
144          * Locking will ensure that we don't have two callers in here
145          * at one time.
146          */
147         newlen = XFS_IALLOC_INODES(args.mp);
148         if (args.mp->m_maxicount &&
149             args.mp->m_sb.sb_icount + newlen > args.mp->m_maxicount)
150                 return XFS_ERROR(ENOSPC);
151         args.minlen = args.maxlen = XFS_IALLOC_BLOCKS(args.mp);
152         /*
153          * First try to allocate inodes contiguous with the last-allocated
154          * chunk of inodes.  If the filesystem is striped, this will fill
155          * an entire stripe unit with inodes.
156          */
157         agi = XFS_BUF_TO_AGI(agbp);
158         newino = be32_to_cpu(agi->agi_newino);
159         args.agbno = XFS_AGINO_TO_AGBNO(args.mp, newino) +
160                         XFS_IALLOC_BLOCKS(args.mp);
161         if (likely(newino != NULLAGINO &&
162                   (args.agbno < be32_to_cpu(agi->agi_length)))) {
163                 args.fsbno = XFS_AGB_TO_FSB(args.mp,
164                                 be32_to_cpu(agi->agi_seqno), args.agbno);
165                 args.type = XFS_ALLOCTYPE_THIS_BNO;
166                 args.mod = args.total = args.wasdel = args.isfl =
167                         args.userdata = args.minalignslop = 0;
168                 args.prod = 1;
169                 args.alignment = 1;
170                 /*
171                  * Allow space for the inode btree to split.
172                  */
173                 args.minleft = XFS_IN_MAXLEVELS(args.mp) - 1;
174                 if ((error = xfs_alloc_vextent(&args)))
175                         return error;
176         } else
177                 args.fsbno = NULLFSBLOCK;
178
179         if (unlikely(args.fsbno == NULLFSBLOCK)) {
180                 /*
181                  * Set the alignment for the allocation.
182                  * If stripe alignment is turned on then align at stripe unit
183                  * boundary.
184                  * If the cluster size is smaller than a filesystem block
185                  * then we're doing I/O for inodes in filesystem block size
186                  * pieces, so don't need alignment anyway.
187                  */
188                 isaligned = 0;
189                 if (args.mp->m_sinoalign) {
190                         ASSERT(!(args.mp->m_flags & XFS_MOUNT_NOALIGN));
191                         args.alignment = args.mp->m_dalign;
192                         isaligned = 1;
193                 } else if (XFS_SB_VERSION_HASALIGN(&args.mp->m_sb) &&
194                            args.mp->m_sb.sb_inoalignmt >=
195                            XFS_B_TO_FSBT(args.mp,
196                                 XFS_INODE_CLUSTER_SIZE(args.mp)))
197                                 args.alignment = args.mp->m_sb.sb_inoalignmt;
198                 else
199                         args.alignment = 1;
200                 /*
201                  * Need to figure out where to allocate the inode blocks.
202                  * Ideally they should be spaced out through the a.g.
203                  * For now, just allocate blocks up front.
204                  */
205                 args.agbno = be32_to_cpu(agi->agi_root);
206                 args.fsbno = XFS_AGB_TO_FSB(args.mp,
207                                 be32_to_cpu(agi->agi_seqno), args.agbno);
208                 /*
209                  * Allocate a fixed-size extent of inodes.
210                  */
211                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
212                 args.mod = args.total = args.wasdel = args.isfl =
213                         args.userdata = args.minalignslop = 0;
214                 args.prod = 1;
215                 /*
216                  * Allow space for the inode btree to split.
217                  */
218                 args.minleft = XFS_IN_MAXLEVELS(args.mp) - 1;
219                 if ((error = xfs_alloc_vextent(&args)))
220                         return error;
221         }
222
223         /*
224          * If stripe alignment is turned on, then try again with cluster
225          * alignment.
226          */
227         if (isaligned && args.fsbno == NULLFSBLOCK) {
228                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
229                 args.agbno = be32_to_cpu(agi->agi_root);
230                 args.fsbno = XFS_AGB_TO_FSB(args.mp,
231                                 be32_to_cpu(agi->agi_seqno), args.agbno);
232                 if (XFS_SB_VERSION_HASALIGN(&args.mp->m_sb) &&
233                         args.mp->m_sb.sb_inoalignmt >=
234                         XFS_B_TO_FSBT(args.mp, XFS_INODE_CLUSTER_SIZE(args.mp)))
235                                 args.alignment = args.mp->m_sb.sb_inoalignmt;
236                 else
237                         args.alignment = 1;
238                 if ((error = xfs_alloc_vextent(&args)))
239                         return error;
240         }
241
242         if (args.fsbno == NULLFSBLOCK) {
243                 *alloc = 0;
244                 return 0;
245         }
246         ASSERT(args.len == args.minlen);
247         /*
248          * Convert the results.
249          */
250         newino = XFS_OFFBNO_TO_AGINO(args.mp, args.agbno, 0);
251         /*
252          * Loop over the new block(s), filling in the inodes.
253          * For small block sizes, manipulate the inodes in buffers
254          * which are multiples of the blocks size.
255          */
256         if (args.mp->m_sb.sb_blocksize >= XFS_INODE_CLUSTER_SIZE(args.mp)) {
257                 blks_per_cluster = 1;
258                 nbufs = (int)args.len;
259                 ninodes = args.mp->m_sb.sb_inopblock;
260         } else {
261                 blks_per_cluster = XFS_INODE_CLUSTER_SIZE(args.mp) /
262                                    args.mp->m_sb.sb_blocksize;
263                 nbufs = (int)args.len / blks_per_cluster;
264                 ninodes = blks_per_cluster * args.mp->m_sb.sb_inopblock;
265         }
266         /*
267          * Figure out what version number to use in the inodes we create.
268          * If the superblock version has caught up to the one that supports
269          * the new inode format, then use the new inode version.  Otherwise
270          * use the old version so that old kernels will continue to be
271          * able to use the file system.
272          */
273         if (XFS_SB_VERSION_HASNLINK(&args.mp->m_sb))
274                 version = XFS_DINODE_VERSION_2;
275         else
276                 version = XFS_DINODE_VERSION_1;
277
278         for (j = 0; j < nbufs; j++) {
279                 /*
280                  * Get the block.
281                  */
282                 d = XFS_AGB_TO_DADDR(args.mp, be32_to_cpu(agi->agi_seqno),
283                                      args.agbno + (j * blks_per_cluster));
284                 fbuf = xfs_trans_get_buf(tp, args.mp->m_ddev_targp, d,
285                                          args.mp->m_bsize * blks_per_cluster,
286                                          XFS_BUF_LOCK);
287                 ASSERT(fbuf);
288                 ASSERT(!XFS_BUF_GETERROR(fbuf));
289                 /*
290                  * Set initial values for the inodes in this buffer.
291                  */
292                 xfs_biozero(fbuf, 0, ninodes << args.mp->m_sb.sb_inodelog);
293                 for (i = 0; i < ninodes; i++) {
294                         free = XFS_MAKE_IPTR(args.mp, fbuf, i);
295                         INT_SET(free->di_core.di_magic, ARCH_CONVERT, XFS_DINODE_MAGIC);
296                         INT_SET(free->di_core.di_version, ARCH_CONVERT, version);
297                         INT_SET(free->di_next_unlinked, ARCH_CONVERT, NULLAGINO);
298                         xfs_ialloc_log_di(tp, fbuf, i,
299                                 XFS_DI_CORE_BITS | XFS_DI_NEXT_UNLINKED);
300                 }
301                 xfs_trans_inode_alloc_buf(tp, fbuf);
302         }
303         be32_add(&agi->agi_count, newlen);
304         be32_add(&agi->agi_freecount, newlen);
305         down_read(&args.mp->m_peraglock);
306         args.mp->m_perag[be32_to_cpu(agi->agi_seqno)].pagi_freecount += newlen;
307         up_read(&args.mp->m_peraglock);
308         agi->agi_newino = cpu_to_be32(newino);
309         /*
310          * Insert records describing the new inode chunk into the btree.
311          */
312         cur = xfs_btree_init_cursor(args.mp, tp, agbp,
313                         be32_to_cpu(agi->agi_seqno),
314                         XFS_BTNUM_INO, (xfs_inode_t *)0, 0);
315         for (thisino = newino;
316              thisino < newino + newlen;
317              thisino += XFS_INODES_PER_CHUNK) {
318                 if ((error = xfs_inobt_lookup_eq(cur, thisino,
319                                 XFS_INODES_PER_CHUNK, XFS_INOBT_ALL_FREE, &i))) {
320                         xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
321                         return error;
322                 }
323                 ASSERT(i == 0);
324                 if ((error = xfs_inobt_insert(cur, &i))) {
325                         xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
326                         return error;
327                 }
328                 ASSERT(i == 1);
329         }
330         xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
331         /*
332          * Log allocation group header fields
333          */
334         xfs_ialloc_log_agi(tp, agbp,
335                 XFS_AGI_COUNT | XFS_AGI_FREECOUNT | XFS_AGI_NEWINO);
336         /*
337          * Modify/log superblock values for inode count and inode free count.
338          */
339         xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, (long)newlen);
340         xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, (long)newlen);
341         *alloc = 1;
342         return 0;
343 }
344
345 STATIC __inline xfs_agnumber_t
346 xfs_ialloc_next_ag(
347         xfs_mount_t     *mp)
348 {
349         xfs_agnumber_t  agno;
350
351         spin_lock(&mp->m_agirotor_lock);
352         agno = mp->m_agirotor;
353         if (++mp->m_agirotor == mp->m_maxagi)
354                 mp->m_agirotor = 0;
355         spin_unlock(&mp->m_agirotor_lock);
356
357         return agno;
358 }
359
360 /*
361  * Select an allocation group to look for a free inode in, based on the parent
362  * inode and then mode.  Return the allocation group buffer.
363  */
364 STATIC xfs_buf_t *                      /* allocation group buffer */
365 xfs_ialloc_ag_select(
366         xfs_trans_t     *tp,            /* transaction pointer */
367         xfs_ino_t       parent,         /* parent directory inode number */
368         mode_t          mode,           /* bits set to indicate file type */
369         int             okalloc)        /* ok to allocate more space */
370 {
371         xfs_buf_t       *agbp;          /* allocation group header buffer */
372         xfs_agnumber_t  agcount;        /* number of ag's in the filesystem */
373         xfs_agnumber_t  agno;           /* current ag number */
374         int             flags;          /* alloc buffer locking flags */
375         xfs_extlen_t    ineed;          /* blocks needed for inode allocation */
376         xfs_extlen_t    longest = 0;    /* longest extent available */
377         xfs_mount_t     *mp;            /* mount point structure */
378         int             needspace;      /* file mode implies space allocated */
379         xfs_perag_t     *pag;           /* per allocation group data */
380         xfs_agnumber_t  pagno;          /* parent (starting) ag number */
381
382         /*
383          * Files of these types need at least one block if length > 0
384          * (and they won't fit in the inode, but that's hard to figure out).
385          */
386         needspace = S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode);
387         mp = tp->t_mountp;
388         agcount = mp->m_maxagi;
389         if (S_ISDIR(mode))
390                 pagno = xfs_ialloc_next_ag(mp);
391         else {
392                 pagno = XFS_INO_TO_AGNO(mp, parent);
393                 if (pagno >= agcount)
394                         pagno = 0;
395         }
396         ASSERT(pagno < agcount);
397         /*
398          * Loop through allocation groups, looking for one with a little
399          * free space in it.  Note we don't look for free inodes, exactly.
400          * Instead, we include whether there is a need to allocate inodes
401          * to mean that blocks must be allocated for them,
402          * if none are currently free.
403          */
404         agno = pagno;
405         flags = XFS_ALLOC_FLAG_TRYLOCK;
406         down_read(&mp->m_peraglock);
407         for (;;) {
408                 pag = &mp->m_perag[agno];
409                 if (!pag->pagi_init) {
410                         if (xfs_ialloc_read_agi(mp, tp, agno, &agbp)) {
411                                 agbp = NULL;
412                                 goto nextag;
413                         }
414                 } else
415                         agbp = NULL;
416
417                 if (!pag->pagi_inodeok) {
418                         xfs_ialloc_next_ag(mp);
419                         goto unlock_nextag;
420                 }
421
422                 /*
423                  * Is there enough free space for the file plus a block
424                  * of inodes (if we need to allocate some)?
425                  */
426                 ineed = pag->pagi_freecount ? 0 : XFS_IALLOC_BLOCKS(mp);
427                 if (ineed && !pag->pagf_init) {
428                         if (agbp == NULL &&
429                             xfs_ialloc_read_agi(mp, tp, agno, &agbp)) {
430                                 agbp = NULL;
431                                 goto nextag;
432                         }
433                         (void)xfs_alloc_pagf_init(mp, tp, agno, flags);
434                 }
435                 if (!ineed || pag->pagf_init) {
436                         if (ineed && !(longest = pag->pagf_longest))
437                                 longest = pag->pagf_flcount > 0;
438                         if (!ineed ||
439                             (pag->pagf_freeblks >= needspace + ineed &&
440                              longest >= ineed &&
441                              okalloc)) {
442                                 if (agbp == NULL &&
443                                     xfs_ialloc_read_agi(mp, tp, agno, &agbp)) {
444                                         agbp = NULL;
445                                         goto nextag;
446                                 }
447                                 up_read(&mp->m_peraglock);
448                                 return agbp;
449                         }
450                 }
451 unlock_nextag:
452                 if (agbp)
453                         xfs_trans_brelse(tp, agbp);
454 nextag:
455                 /*
456                  * No point in iterating over the rest, if we're shutting
457                  * down.
458                  */
459                 if (XFS_FORCED_SHUTDOWN(mp)) {
460                         up_read(&mp->m_peraglock);
461                         return (xfs_buf_t *)0;
462                 }
463                 agno++;
464                 if (agno >= agcount)
465                         agno = 0;
466                 if (agno == pagno) {
467                         if (flags == 0) {
468                                 up_read(&mp->m_peraglock);
469                                 return (xfs_buf_t *)0;
470                         }
471                         flags = 0;
472                 }
473         }
474 }
475
476 /*
477  * Visible inode allocation functions.
478  */
479
480 /*
481  * Allocate an inode on disk.
482  * Mode is used to tell whether the new inode will need space, and whether
483  * it is a directory.
484  *
485  * The arguments IO_agbp and alloc_done are defined to work within
486  * the constraint of one allocation per transaction.
487  * xfs_dialloc() is designed to be called twice if it has to do an
488  * allocation to make more free inodes.  On the first call,
489  * IO_agbp should be set to NULL. If an inode is available,
490  * i.e., xfs_dialloc() did not need to do an allocation, an inode
491  * number is returned.  In this case, IO_agbp would be set to the
492  * current ag_buf and alloc_done set to false.
493  * If an allocation needed to be done, xfs_dialloc would return
494  * the current ag_buf in IO_agbp and set alloc_done to true.
495  * The caller should then commit the current transaction, allocate a new
496  * transaction, and call xfs_dialloc() again, passing in the previous
497  * value of IO_agbp.  IO_agbp should be held across the transactions.
498  * Since the agbp is locked across the two calls, the second call is
499  * guaranteed to have a free inode available.
500  *
501  * Once we successfully pick an inode its number is returned and the
502  * on-disk data structures are updated.  The inode itself is not read
503  * in, since doing so would break ordering constraints with xfs_reclaim.
504  */
505 int
506 xfs_dialloc(
507         xfs_trans_t     *tp,            /* transaction pointer */
508         xfs_ino_t       parent,         /* parent inode (directory) */
509         mode_t          mode,           /* mode bits for new inode */
510         int             okalloc,        /* ok to allocate more space */
511         xfs_buf_t       **IO_agbp,      /* in/out ag header's buffer */
512         boolean_t       *alloc_done,    /* true if we needed to replenish
513                                            inode freelist */
514         xfs_ino_t       *inop)          /* inode number allocated */
515 {
516         xfs_agnumber_t  agcount;        /* number of allocation groups */
517         xfs_buf_t       *agbp;          /* allocation group header's buffer */
518         xfs_agnumber_t  agno;           /* allocation group number */
519         xfs_agi_t       *agi;           /* allocation group header structure */
520         xfs_btree_cur_t *cur;           /* inode allocation btree cursor */
521         int             error;          /* error return value */
522         int             i;              /* result code */
523         int             ialloced;       /* inode allocation status */
524         int             noroom = 0;     /* no space for inode blk allocation */
525         xfs_ino_t       ino;            /* fs-relative inode to be returned */
526         /* REFERENCED */
527         int             j;              /* result code */
528         xfs_mount_t     *mp;            /* file system mount structure */
529         int             offset;         /* index of inode in chunk */
530         xfs_agino_t     pagino;         /* parent's a.g. relative inode # */
531         xfs_agnumber_t  pagno;          /* parent's allocation group number */
532         xfs_inobt_rec_incore_t rec;     /* inode allocation record */
533         xfs_agnumber_t  tagno;          /* testing allocation group number */
534         xfs_btree_cur_t *tcur;          /* temp cursor */
535         xfs_inobt_rec_incore_t trec;    /* temp inode allocation record */
536
537
538         if (*IO_agbp == NULL) {
539                 /*
540                  * We do not have an agbp, so select an initial allocation
541                  * group for inode allocation.
542                  */
543                 agbp = xfs_ialloc_ag_select(tp, parent, mode, okalloc);
544                 /*
545                  * Couldn't find an allocation group satisfying the
546                  * criteria, give up.
547                  */
548                 if (!agbp) {
549                         *inop = NULLFSINO;
550                         return 0;
551                 }
552                 agi = XFS_BUF_TO_AGI(agbp);
553                 ASSERT(be32_to_cpu(agi->agi_magicnum) == XFS_AGI_MAGIC);
554         } else {
555                 /*
556                  * Continue where we left off before.  In this case, we
557                  * know that the allocation group has free inodes.
558                  */
559                 agbp = *IO_agbp;
560                 agi = XFS_BUF_TO_AGI(agbp);
561                 ASSERT(be32_to_cpu(agi->agi_magicnum) == XFS_AGI_MAGIC);
562                 ASSERT(be32_to_cpu(agi->agi_freecount) > 0);
563         }
564         mp = tp->t_mountp;
565         agcount = mp->m_sb.sb_agcount;
566         agno = be32_to_cpu(agi->agi_seqno);
567         tagno = agno;
568         pagno = XFS_INO_TO_AGNO(mp, parent);
569         pagino = XFS_INO_TO_AGINO(mp, parent);
570
571         /*
572          * If we have already hit the ceiling of inode blocks then clear
573          * okalloc so we scan all available agi structures for a free
574          * inode.
575          */
576
577         if (mp->m_maxicount &&
578             mp->m_sb.sb_icount + XFS_IALLOC_INODES(mp) > mp->m_maxicount) {
579                 noroom = 1;
580                 okalloc = 0;
581         }
582
583         /*
584          * Loop until we find an allocation group that either has free inodes
585          * or in which we can allocate some inodes.  Iterate through the
586          * allocation groups upward, wrapping at the end.
587          */
588         *alloc_done = B_FALSE;
589         while (!agi->agi_freecount) {
590                 /*
591                  * Don't do anything if we're not supposed to allocate
592                  * any blocks, just go on to the next ag.
593                  */
594                 if (okalloc) {
595                         /*
596                          * Try to allocate some new inodes in the allocation
597                          * group.
598                          */
599                         if ((error = xfs_ialloc_ag_alloc(tp, agbp, &ialloced))) {
600                                 xfs_trans_brelse(tp, agbp);
601                                 if (error == ENOSPC) {
602                                         *inop = NULLFSINO;
603                                         return 0;
604                                 } else
605                                         return error;
606                         }
607                         if (ialloced) {
608                                 /*
609                                  * We successfully allocated some inodes, return
610                                  * the current context to the caller so that it
611                                  * can commit the current transaction and call
612                                  * us again where we left off.
613                                  */
614                                 ASSERT(be32_to_cpu(agi->agi_freecount) > 0);
615                                 *alloc_done = B_TRUE;
616                                 *IO_agbp = agbp;
617                                 *inop = NULLFSINO;
618                                 return 0;
619                         }
620                 }
621                 /*
622                  * If it failed, give up on this ag.
623                  */
624                 xfs_trans_brelse(tp, agbp);
625                 /*
626                  * Go on to the next ag: get its ag header.
627                  */
628 nextag:
629                 if (++tagno == agcount)
630                         tagno = 0;
631                 if (tagno == agno) {
632                         *inop = NULLFSINO;
633                         return noroom ? ENOSPC : 0;
634                 }
635                 down_read(&mp->m_peraglock);
636                 if (mp->m_perag[tagno].pagi_inodeok == 0) {
637                         up_read(&mp->m_peraglock);
638                         goto nextag;
639                 }
640                 error = xfs_ialloc_read_agi(mp, tp, tagno, &agbp);
641                 up_read(&mp->m_peraglock);
642                 if (error)
643                         goto nextag;
644                 agi = XFS_BUF_TO_AGI(agbp);
645                 ASSERT(be32_to_cpu(agi->agi_magicnum) == XFS_AGI_MAGIC);
646         }
647         /*
648          * Here with an allocation group that has a free inode.
649          * Reset agno since we may have chosen a new ag in the
650          * loop above.
651          */
652         agno = tagno;
653         *IO_agbp = NULL;
654         cur = xfs_btree_init_cursor(mp, tp, agbp, be32_to_cpu(agi->agi_seqno),
655                                     XFS_BTNUM_INO, (xfs_inode_t *)0, 0);
656         /*
657          * If pagino is 0 (this is the root inode allocation) use newino.
658          * This must work because we've just allocated some.
659          */
660         if (!pagino)
661                 pagino = be32_to_cpu(agi->agi_newino);
662 #ifdef DEBUG
663         if (cur->bc_nlevels == 1) {
664                 int     freecount = 0;
665
666                 if ((error = xfs_inobt_lookup_ge(cur, 0, 0, 0, &i)))
667                         goto error0;
668                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
669                 do {
670                         if ((error = xfs_inobt_get_rec(cur, &rec.ir_startino,
671                                         &rec.ir_freecount, &rec.ir_free, &i)))
672                                 goto error0;
673                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
674                         freecount += rec.ir_freecount;
675                         if ((error = xfs_inobt_increment(cur, 0, &i)))
676                                 goto error0;
677                 } while (i == 1);
678
679                 ASSERT(freecount == be32_to_cpu(agi->agi_freecount) ||
680                        XFS_FORCED_SHUTDOWN(mp));
681         }
682 #endif
683         /*
684          * If in the same a.g. as the parent, try to get near the parent.
685          */
686         if (pagno == agno) {
687                 if ((error = xfs_inobt_lookup_le(cur, pagino, 0, 0, &i)))
688                         goto error0;
689                 if (i != 0 &&
690                     (error = xfs_inobt_get_rec(cur, &rec.ir_startino,
691                             &rec.ir_freecount, &rec.ir_free, &j)) == 0 &&
692                     j == 1 &&
693                     rec.ir_freecount > 0) {
694                         /*
695                          * Found a free inode in the same chunk
696                          * as parent, done.
697                          */
698                 }
699                 /*
700                  * In the same a.g. as parent, but parent's chunk is full.
701                  */
702                 else {
703                         int     doneleft;       /* done, to the left */
704                         int     doneright;      /* done, to the right */
705
706                         if (error)
707                                 goto error0;
708                         ASSERT(i == 1);
709                         ASSERT(j == 1);
710                         /*
711                          * Duplicate the cursor, search left & right
712                          * simultaneously.
713                          */
714                         if ((error = xfs_btree_dup_cursor(cur, &tcur)))
715                                 goto error0;
716                         /*
717                          * Search left with tcur, back up 1 record.
718                          */
719                         if ((error = xfs_inobt_decrement(tcur, 0, &i)))
720                                 goto error1;
721                         doneleft = !i;
722                         if (!doneleft) {
723                                 if ((error = xfs_inobt_get_rec(tcur,
724                                                 &trec.ir_startino,
725                                                 &trec.ir_freecount,
726                                                 &trec.ir_free, &i)))
727                                         goto error1;
728                                 XFS_WANT_CORRUPTED_GOTO(i == 1, error1);
729                         }
730                         /*
731                          * Search right with cur, go forward 1 record.
732                          */
733                         if ((error = xfs_inobt_increment(cur, 0, &i)))
734                                 goto error1;
735                         doneright = !i;
736                         if (!doneright) {
737                                 if ((error = xfs_inobt_get_rec(cur,
738                                                 &rec.ir_startino,
739                                                 &rec.ir_freecount,
740                                                 &rec.ir_free, &i)))
741                                         goto error1;
742                                 XFS_WANT_CORRUPTED_GOTO(i == 1, error1);
743                         }
744                         /*
745                          * Loop until we find the closest inode chunk
746                          * with a free one.
747                          */
748                         while (!doneleft || !doneright) {
749                                 int     useleft;  /* using left inode
750                                                      chunk this time */
751
752                                 /*
753                                  * Figure out which block is closer,
754                                  * if both are valid.
755                                  */
756                                 if (!doneleft && !doneright)
757                                         useleft =
758                                                 pagino -
759                                                 (trec.ir_startino +
760                                                  XFS_INODES_PER_CHUNK - 1) <
761                                                  rec.ir_startino - pagino;
762                                 else
763                                         useleft = !doneleft;
764                                 /*
765                                  * If checking the left, does it have
766                                  * free inodes?
767                                  */
768                                 if (useleft && trec.ir_freecount) {
769                                         /*
770                                          * Yes, set it up as the chunk to use.
771                                          */
772                                         rec = trec;
773                                         xfs_btree_del_cursor(cur,
774                                                 XFS_BTREE_NOERROR);
775                                         cur = tcur;
776                                         break;
777                                 }
778                                 /*
779                                  * If checking the right, does it have
780                                  * free inodes?
781                                  */
782                                 if (!useleft && rec.ir_freecount) {
783                                         /*
784                                          * Yes, it's already set up.
785                                          */
786                                         xfs_btree_del_cursor(tcur,
787                                                 XFS_BTREE_NOERROR);
788                                         break;
789                                 }
790                                 /*
791                                  * If used the left, get another one
792                                  * further left.
793                                  */
794                                 if (useleft) {
795                                         if ((error = xfs_inobt_decrement(tcur, 0,
796                                                         &i)))
797                                                 goto error1;
798                                         doneleft = !i;
799                                         if (!doneleft) {
800                                                 if ((error = xfs_inobt_get_rec(
801                                                             tcur,
802                                                             &trec.ir_startino,
803                                                             &trec.ir_freecount,
804                                                             &trec.ir_free, &i)))
805                                                         goto error1;
806                                                 XFS_WANT_CORRUPTED_GOTO(i == 1,
807                                                         error1);
808                                         }
809                                 }
810                                 /*
811                                  * If used the right, get another one
812                                  * further right.
813                                  */
814                                 else {
815                                         if ((error = xfs_inobt_increment(cur, 0,
816                                                         &i)))
817                                                 goto error1;
818                                         doneright = !i;
819                                         if (!doneright) {
820                                                 if ((error = xfs_inobt_get_rec(
821                                                             cur,
822                                                             &rec.ir_startino,
823                                                             &rec.ir_freecount,
824                                                             &rec.ir_free, &i)))
825                                                         goto error1;
826                                                 XFS_WANT_CORRUPTED_GOTO(i == 1,
827                                                         error1);
828                                         }
829                                 }
830                         }
831                         ASSERT(!doneleft || !doneright);
832                 }
833         }
834         /*
835          * In a different a.g. from the parent.
836          * See if the most recently allocated block has any free.
837          */
838         else if (be32_to_cpu(agi->agi_newino) != NULLAGINO) {
839                 if ((error = xfs_inobt_lookup_eq(cur,
840                                 be32_to_cpu(agi->agi_newino), 0, 0, &i)))
841                         goto error0;
842                 if (i == 1 &&
843                     (error = xfs_inobt_get_rec(cur, &rec.ir_startino,
844                             &rec.ir_freecount, &rec.ir_free, &j)) == 0 &&
845                     j == 1 &&
846                     rec.ir_freecount > 0) {
847                         /*
848                          * The last chunk allocated in the group still has
849                          * a free inode.
850                          */
851                 }
852                 /*
853                  * None left in the last group, search the whole a.g.
854                  */
855                 else {
856                         if (error)
857                                 goto error0;
858                         if ((error = xfs_inobt_lookup_ge(cur, 0, 0, 0, &i)))
859                                 goto error0;
860                         ASSERT(i == 1);
861                         for (;;) {
862                                 if ((error = xfs_inobt_get_rec(cur,
863                                                 &rec.ir_startino,
864                                                 &rec.ir_freecount, &rec.ir_free,
865                                                 &i)))
866                                         goto error0;
867                                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
868                                 if (rec.ir_freecount > 0)
869                                         break;
870                                 if ((error = xfs_inobt_increment(cur, 0, &i)))
871                                         goto error0;
872                                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
873                         }
874                 }
875         }
876         offset = XFS_IALLOC_FIND_FREE(&rec.ir_free);
877         ASSERT(offset >= 0);
878         ASSERT(offset < XFS_INODES_PER_CHUNK);
879         ASSERT((XFS_AGINO_TO_OFFSET(mp, rec.ir_startino) %
880                                    XFS_INODES_PER_CHUNK) == 0);
881         ino = XFS_AGINO_TO_INO(mp, agno, rec.ir_startino + offset);
882         XFS_INOBT_CLR_FREE(&rec, offset);
883         rec.ir_freecount--;
884         if ((error = xfs_inobt_update(cur, rec.ir_startino, rec.ir_freecount,
885                         rec.ir_free)))
886                 goto error0;
887         be32_add(&agi->agi_freecount, -1);
888         xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
889         down_read(&mp->m_peraglock);
890         mp->m_perag[tagno].pagi_freecount--;
891         up_read(&mp->m_peraglock);
892 #ifdef DEBUG
893         if (cur->bc_nlevels == 1) {
894                 int     freecount = 0;
895
896                 if ((error = xfs_inobt_lookup_ge(cur, 0, 0, 0, &i)))
897                         goto error0;
898                 do {
899                         if ((error = xfs_inobt_get_rec(cur, &rec.ir_startino,
900                                         &rec.ir_freecount, &rec.ir_free, &i)))
901                                 goto error0;
902                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
903                         freecount += rec.ir_freecount;
904                         if ((error = xfs_inobt_increment(cur, 0, &i)))
905                                 goto error0;
906                 } while (i == 1);
907                 ASSERT(freecount == be32_to_cpu(agi->agi_freecount) ||
908                        XFS_FORCED_SHUTDOWN(mp));
909         }
910 #endif
911         xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
912         xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1);
913         *inop = ino;
914         return 0;
915 error1:
916         xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
917 error0:
918         xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
919         return error;
920 }
921
922 /*
923  * Free disk inode.  Carefully avoids touching the incore inode, all
924  * manipulations incore are the caller's responsibility.
925  * The on-disk inode is not changed by this operation, only the
926  * btree (free inode mask) is changed.
927  */
928 int
929 xfs_difree(
930         xfs_trans_t     *tp,            /* transaction pointer */
931         xfs_ino_t       inode,          /* inode to be freed */
932         xfs_bmap_free_t *flist,         /* extents to free */
933         int             *delete,        /* set if inode cluster was deleted */
934         xfs_ino_t       *first_ino)     /* first inode in deleted cluster */
935 {
936         /* REFERENCED */
937         xfs_agblock_t   agbno;  /* block number containing inode */
938         xfs_buf_t       *agbp;  /* buffer containing allocation group header */
939         xfs_agino_t     agino;  /* inode number relative to allocation group */
940         xfs_agnumber_t  agno;   /* allocation group number */
941         xfs_agi_t       *agi;   /* allocation group header */
942         xfs_btree_cur_t *cur;   /* inode btree cursor */
943         int             error;  /* error return value */
944         int             i;      /* result code */
945         int             ilen;   /* inodes in an inode cluster */
946         xfs_mount_t     *mp;    /* mount structure for filesystem */
947         int             off;    /* offset of inode in inode chunk */
948         xfs_inobt_rec_incore_t rec;     /* btree record */
949
950         mp = tp->t_mountp;
951
952         /*
953          * Break up inode number into its components.
954          */
955         agno = XFS_INO_TO_AGNO(mp, inode);
956         if (agno >= mp->m_sb.sb_agcount)  {
957                 cmn_err(CE_WARN,
958                         "xfs_difree: agno >= mp->m_sb.sb_agcount (%d >= %d) on %s.  Returning EINVAL.",
959                         agno, mp->m_sb.sb_agcount, mp->m_fsname);
960                 ASSERT(0);
961                 return XFS_ERROR(EINVAL);
962         }
963         agino = XFS_INO_TO_AGINO(mp, inode);
964         if (inode != XFS_AGINO_TO_INO(mp, agno, agino))  {
965                 cmn_err(CE_WARN,
966                         "xfs_difree: inode != XFS_AGINO_TO_INO() "
967                         "(%llu != %llu) on %s.  Returning EINVAL.",
968                         (unsigned long long)inode,
969                         (unsigned long long)XFS_AGINO_TO_INO(mp, agno, agino),
970                         mp->m_fsname);
971                 ASSERT(0);
972                 return XFS_ERROR(EINVAL);
973         }
974         agbno = XFS_AGINO_TO_AGBNO(mp, agino);
975         if (agbno >= mp->m_sb.sb_agblocks)  {
976                 cmn_err(CE_WARN,
977                         "xfs_difree: agbno >= mp->m_sb.sb_agblocks (%d >= %d) on %s.  Returning EINVAL.",
978                         agbno, mp->m_sb.sb_agblocks, mp->m_fsname);
979                 ASSERT(0);
980                 return XFS_ERROR(EINVAL);
981         }
982         /*
983          * Get the allocation group header.
984          */
985         down_read(&mp->m_peraglock);
986         error = xfs_ialloc_read_agi(mp, tp, agno, &agbp);
987         up_read(&mp->m_peraglock);
988         if (error) {
989                 cmn_err(CE_WARN,
990                         "xfs_difree: xfs_ialloc_read_agi() returned an error %d on %s.  Returning error.",
991                         error, mp->m_fsname);
992                 return error;
993         }
994         agi = XFS_BUF_TO_AGI(agbp);
995         ASSERT(be32_to_cpu(agi->agi_magicnum) == XFS_AGI_MAGIC);
996         ASSERT(agbno < be32_to_cpu(agi->agi_length));
997         /*
998          * Initialize the cursor.
999          */
1000         cur = xfs_btree_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_INO,
1001                 (xfs_inode_t *)0, 0);
1002 #ifdef DEBUG
1003         if (cur->bc_nlevels == 1) {
1004                 int freecount = 0;
1005
1006                 if ((error = xfs_inobt_lookup_ge(cur, 0, 0, 0, &i)))
1007                         goto error0;
1008                 do {
1009                         if ((error = xfs_inobt_get_rec(cur, &rec.ir_startino,
1010                                         &rec.ir_freecount, &rec.ir_free, &i)))
1011                                 goto error0;
1012                         if (i) {
1013                                 freecount += rec.ir_freecount;
1014                                 if ((error = xfs_inobt_increment(cur, 0, &i)))
1015                                         goto error0;
1016                         }
1017                 } while (i == 1);
1018                 ASSERT(freecount == be32_to_cpu(agi->agi_freecount) ||
1019                        XFS_FORCED_SHUTDOWN(mp));
1020         }
1021 #endif
1022         /*
1023          * Look for the entry describing this inode.
1024          */
1025         if ((error = xfs_inobt_lookup_le(cur, agino, 0, 0, &i))) {
1026                 cmn_err(CE_WARN,
1027                         "xfs_difree: xfs_inobt_lookup_le returned()  an error %d on %s.  Returning error.",
1028                         error, mp->m_fsname);
1029                 goto error0;
1030         }
1031         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1032         if ((error = xfs_inobt_get_rec(cur, &rec.ir_startino, &rec.ir_freecount,
1033                         &rec.ir_free, &i))) {
1034                 cmn_err(CE_WARN,
1035                         "xfs_difree: xfs_inobt_get_rec()  returned an error %d on %s.  Returning error.",
1036                         error, mp->m_fsname);
1037                 goto error0;
1038         }
1039         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1040         /*
1041          * Get the offset in the inode chunk.
1042          */
1043         off = agino - rec.ir_startino;
1044         ASSERT(off >= 0 && off < XFS_INODES_PER_CHUNK);
1045         ASSERT(!XFS_INOBT_IS_FREE(&rec, off));
1046         /*
1047          * Mark the inode free & increment the count.
1048          */
1049         XFS_INOBT_SET_FREE(&rec, off);
1050         rec.ir_freecount++;
1051
1052         /*
1053          * When an inode cluster is free, it becomes eligible for removal
1054          */
1055         if ((mp->m_flags & XFS_MOUNT_IDELETE) &&
1056             (rec.ir_freecount == XFS_IALLOC_INODES(mp))) {
1057
1058                 *delete = 1;
1059                 *first_ino = XFS_AGINO_TO_INO(mp, agno, rec.ir_startino);
1060
1061                 /*
1062                  * Remove the inode cluster from the AGI B+Tree, adjust the
1063                  * AGI and Superblock inode counts, and mark the disk space
1064                  * to be freed when the transaction is committed.
1065                  */
1066                 ilen = XFS_IALLOC_INODES(mp);
1067                 be32_add(&agi->agi_count, -ilen);
1068                 be32_add(&agi->agi_freecount, -(ilen - 1));
1069                 xfs_ialloc_log_agi(tp, agbp, XFS_AGI_COUNT | XFS_AGI_FREECOUNT);
1070                 down_read(&mp->m_peraglock);
1071                 mp->m_perag[agno].pagi_freecount -= ilen - 1;
1072                 up_read(&mp->m_peraglock);
1073                 xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, -ilen);
1074                 xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -(ilen - 1));
1075
1076                 if ((error = xfs_inobt_delete(cur, &i))) {
1077                         cmn_err(CE_WARN, "xfs_difree: xfs_inobt_delete returned an error %d on %s.\n",
1078                                 error, mp->m_fsname);
1079                         goto error0;
1080                 }
1081
1082                 xfs_bmap_add_free(XFS_AGB_TO_FSB(mp,
1083                                 agno, XFS_INO_TO_AGBNO(mp,rec.ir_startino)),
1084                                 XFS_IALLOC_BLOCKS(mp), flist, mp);
1085         } else {
1086                 *delete = 0;
1087
1088                 if ((error = xfs_inobt_update(cur, rec.ir_startino, rec.ir_freecount, rec.ir_free))) {
1089                         cmn_err(CE_WARN,
1090                                 "xfs_difree: xfs_inobt_update()  returned an error %d on %s.  Returning error.",
1091                                 error, mp->m_fsname);
1092                         goto error0;
1093                 }
1094                 /* 
1095                  * Change the inode free counts and log the ag/sb changes.
1096                  */
1097                 be32_add(&agi->agi_freecount, 1);
1098                 xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
1099                 down_read(&mp->m_peraglock);
1100                 mp->m_perag[agno].pagi_freecount++;
1101                 up_read(&mp->m_peraglock);
1102                 xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, 1);
1103         }
1104
1105 #ifdef DEBUG
1106         if (cur->bc_nlevels == 1) {
1107                 int freecount = 0;
1108
1109                 if ((error = xfs_inobt_lookup_ge(cur, 0, 0, 0, &i)))
1110                         goto error0;
1111                 do {
1112                         if ((error = xfs_inobt_get_rec(cur,
1113                                         &rec.ir_startino,
1114                                         &rec.ir_freecount,
1115                                         &rec.ir_free, &i)))
1116                                 goto error0;
1117                         if (i) {
1118                                 freecount += rec.ir_freecount;
1119                                 if ((error = xfs_inobt_increment(cur, 0, &i)))
1120                                         goto error0;
1121                         }
1122                 } while (i == 1);
1123                 ASSERT(freecount == be32_to_cpu(agi->agi_freecount) ||
1124                        XFS_FORCED_SHUTDOWN(mp));
1125         }
1126 #endif
1127         xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1128         return 0;
1129
1130 error0:
1131         xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
1132         return error;
1133 }
1134
1135 /*
1136  * Return the location of the inode in bno/off, for mapping it into a buffer.
1137  */
1138 /*ARGSUSED*/
1139 int
1140 xfs_dilocate(
1141         xfs_mount_t     *mp,    /* file system mount structure */
1142         xfs_trans_t     *tp,    /* transaction pointer */
1143         xfs_ino_t       ino,    /* inode to locate */
1144         xfs_fsblock_t   *bno,   /* output: block containing inode */
1145         int             *len,   /* output: num blocks in inode cluster */
1146         int             *off,   /* output: index in block of inode */
1147         uint            flags)  /* flags concerning inode lookup */
1148 {
1149         xfs_agblock_t   agbno;  /* block number of inode in the alloc group */
1150         xfs_buf_t       *agbp;  /* agi buffer */
1151         xfs_agino_t     agino;  /* inode number within alloc group */
1152         xfs_agnumber_t  agno;   /* allocation group number */
1153         int             blks_per_cluster; /* num blocks per inode cluster */
1154         xfs_agblock_t   chunk_agbno;    /* first block in inode chunk */
1155         xfs_agino_t     chunk_agino;    /* first agino in inode chunk */
1156         __int32_t       chunk_cnt;      /* count of free inodes in chunk */
1157         xfs_inofree_t   chunk_free;     /* mask of free inodes in chunk */
1158         xfs_agblock_t   cluster_agbno;  /* first block in inode cluster */
1159         xfs_btree_cur_t *cur;   /* inode btree cursor */
1160         int             error;  /* error code */
1161         int             i;      /* temp state */
1162         int             offset; /* index of inode in its buffer */
1163         int             offset_agbno;   /* blks from chunk start to inode */
1164
1165         ASSERT(ino != NULLFSINO);
1166         /*
1167          * Split up the inode number into its parts.
1168          */
1169         agno = XFS_INO_TO_AGNO(mp, ino);
1170         agino = XFS_INO_TO_AGINO(mp, ino);
1171         agbno = XFS_AGINO_TO_AGBNO(mp, agino);
1172         if (agno >= mp->m_sb.sb_agcount || agbno >= mp->m_sb.sb_agblocks ||
1173             ino != XFS_AGINO_TO_INO(mp, agno, agino)) {
1174 #ifdef DEBUG
1175                 /* no diagnostics for bulkstat, ino comes from userspace */
1176                 if (flags & XFS_IMAP_BULKSTAT)
1177                         return XFS_ERROR(EINVAL);
1178                 if (agno >= mp->m_sb.sb_agcount) {
1179                         xfs_fs_cmn_err(CE_ALERT, mp,
1180                                         "xfs_dilocate: agno (%d) >= "
1181                                         "mp->m_sb.sb_agcount (%d)",
1182                                         agno,  mp->m_sb.sb_agcount);
1183                 }
1184                 if (agbno >= mp->m_sb.sb_agblocks) {
1185                         xfs_fs_cmn_err(CE_ALERT, mp,
1186                                         "xfs_dilocate: agbno (0x%llx) >= "
1187                                         "mp->m_sb.sb_agblocks (0x%lx)",
1188                                         (unsigned long long) agbno,
1189                                         (unsigned long) mp->m_sb.sb_agblocks);
1190                 }
1191                 if (ino != XFS_AGINO_TO_INO(mp, agno, agino)) {
1192                         xfs_fs_cmn_err(CE_ALERT, mp,
1193                                         "xfs_dilocate: ino (0x%llx) != "
1194                                         "XFS_AGINO_TO_INO(mp, agno, agino) "
1195                                         "(0x%llx)",
1196                                         ino, XFS_AGINO_TO_INO(mp, agno, agino));
1197                 }
1198 #endif /* DEBUG */
1199                 return XFS_ERROR(EINVAL);
1200         }
1201         if ((mp->m_sb.sb_blocksize >= XFS_INODE_CLUSTER_SIZE(mp)) ||
1202             !(flags & XFS_IMAP_LOOKUP)) {
1203                 offset = XFS_INO_TO_OFFSET(mp, ino);
1204                 ASSERT(offset < mp->m_sb.sb_inopblock);
1205                 *bno = XFS_AGB_TO_FSB(mp, agno, agbno);
1206                 *off = offset;
1207                 *len = 1;
1208                 return 0;
1209         }
1210         blks_per_cluster = XFS_INODE_CLUSTER_SIZE(mp) >> mp->m_sb.sb_blocklog;
1211         if (*bno != NULLFSBLOCK) {
1212                 offset = XFS_INO_TO_OFFSET(mp, ino);
1213                 ASSERT(offset < mp->m_sb.sb_inopblock);
1214                 cluster_agbno = XFS_FSB_TO_AGBNO(mp, *bno);
1215                 *off = ((agbno - cluster_agbno) * mp->m_sb.sb_inopblock) +
1216                         offset;
1217                 *len = blks_per_cluster;
1218                 return 0;
1219         }
1220         if (mp->m_inoalign_mask) {
1221                 offset_agbno = agbno & mp->m_inoalign_mask;
1222                 chunk_agbno = agbno - offset_agbno;
1223         } else {
1224                 down_read(&mp->m_peraglock);
1225                 error = xfs_ialloc_read_agi(mp, tp, agno, &agbp);
1226                 up_read(&mp->m_peraglock);
1227                 if (error) {
1228 #ifdef DEBUG
1229                         xfs_fs_cmn_err(CE_ALERT, mp, "xfs_dilocate: "
1230                                         "xfs_ialloc_read_agi() returned "
1231                                         "error %d, agno %d",
1232                                         error, agno);
1233 #endif /* DEBUG */
1234                         return error;
1235                 }
1236                 cur = xfs_btree_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_INO,
1237                         (xfs_inode_t *)0, 0);
1238                 if ((error = xfs_inobt_lookup_le(cur, agino, 0, 0, &i))) {
1239 #ifdef DEBUG
1240                         xfs_fs_cmn_err(CE_ALERT, mp, "xfs_dilocate: "
1241                                         "xfs_inobt_lookup_le() failed");
1242 #endif /* DEBUG */
1243                         goto error0;
1244                 }
1245                 if ((error = xfs_inobt_get_rec(cur, &chunk_agino, &chunk_cnt,
1246                                 &chunk_free, &i))) {
1247 #ifdef DEBUG
1248                         xfs_fs_cmn_err(CE_ALERT, mp, "xfs_dilocate: "
1249                                         "xfs_inobt_get_rec() failed");
1250 #endif /* DEBUG */
1251                         goto error0;
1252                 }
1253                 if (i == 0) {
1254 #ifdef DEBUG
1255                         xfs_fs_cmn_err(CE_ALERT, mp, "xfs_dilocate: "
1256                                         "xfs_inobt_get_rec() failed");
1257 #endif /* DEBUG */
1258                         error = XFS_ERROR(EINVAL);
1259                 }
1260                 xfs_trans_brelse(tp, agbp);
1261                 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
1262                 if (error)
1263                         return error;
1264                 chunk_agbno = XFS_AGINO_TO_AGBNO(mp, chunk_agino);
1265                 offset_agbno = agbno - chunk_agbno;
1266         }
1267         ASSERT(agbno >= chunk_agbno);
1268         cluster_agbno = chunk_agbno +
1269                 ((offset_agbno / blks_per_cluster) * blks_per_cluster);
1270         offset = ((agbno - cluster_agbno) * mp->m_sb.sb_inopblock) +
1271                 XFS_INO_TO_OFFSET(mp, ino);
1272         *bno = XFS_AGB_TO_FSB(mp, agno, cluster_agbno);
1273         *off = offset;
1274         *len = blks_per_cluster;
1275         return 0;
1276 error0:
1277         xfs_trans_brelse(tp, agbp);
1278         xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
1279         return error;
1280 }
1281
1282 /*
1283  * Compute and fill in value of m_in_maxlevels.
1284  */
1285 void
1286 xfs_ialloc_compute_maxlevels(
1287         xfs_mount_t     *mp)            /* file system mount structure */
1288 {
1289         int             level;
1290         uint            maxblocks;
1291         uint            maxleafents;
1292         int             minleafrecs;
1293         int             minnoderecs;
1294
1295         maxleafents = (1LL << XFS_INO_AGINO_BITS(mp)) >>
1296                 XFS_INODES_PER_CHUNK_LOG;
1297         minleafrecs = mp->m_alloc_mnr[0];
1298         minnoderecs = mp->m_alloc_mnr[1];
1299         maxblocks = (maxleafents + minleafrecs - 1) / minleafrecs;
1300         for (level = 1; maxblocks > 1; level++)
1301                 maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs;
1302         mp->m_in_maxlevels = level;
1303 }
1304
1305 /*
1306  * Log specified fields for the ag hdr (inode section)
1307  */
1308 void
1309 xfs_ialloc_log_agi(
1310         xfs_trans_t     *tp,            /* transaction pointer */
1311         xfs_buf_t       *bp,            /* allocation group header buffer */
1312         int             fields)         /* bitmask of fields to log */
1313 {
1314         int                     first;          /* first byte number */
1315         int                     last;           /* last byte number */
1316         static const short      offsets[] = {   /* field starting offsets */
1317                                         /* keep in sync with bit definitions */
1318                 offsetof(xfs_agi_t, agi_magicnum),
1319                 offsetof(xfs_agi_t, agi_versionnum),
1320                 offsetof(xfs_agi_t, agi_seqno),
1321                 offsetof(xfs_agi_t, agi_length),
1322                 offsetof(xfs_agi_t, agi_count),
1323                 offsetof(xfs_agi_t, agi_root),
1324                 offsetof(xfs_agi_t, agi_level),
1325                 offsetof(xfs_agi_t, agi_freecount),
1326                 offsetof(xfs_agi_t, agi_newino),
1327                 offsetof(xfs_agi_t, agi_dirino),
1328                 offsetof(xfs_agi_t, agi_unlinked),
1329                 sizeof(xfs_agi_t)
1330         };
1331 #ifdef DEBUG
1332         xfs_agi_t               *agi;   /* allocation group header */
1333
1334         agi = XFS_BUF_TO_AGI(bp);
1335         ASSERT(be32_to_cpu(agi->agi_magicnum) == XFS_AGI_MAGIC);
1336 #endif
1337         /*
1338          * Compute byte offsets for the first and last fields.
1339          */
1340         xfs_btree_offsets(fields, offsets, XFS_AGI_NUM_BITS, &first, &last);
1341         /*
1342          * Log the allocation group inode header buffer.
1343          */
1344         xfs_trans_log_buf(tp, bp, first, last);
1345 }
1346
1347 /*
1348  * Read in the allocation group header (inode allocation section)
1349  */
1350 int
1351 xfs_ialloc_read_agi(
1352         xfs_mount_t     *mp,            /* file system mount structure */
1353         xfs_trans_t     *tp,            /* transaction pointer */
1354         xfs_agnumber_t  agno,           /* allocation group number */
1355         xfs_buf_t       **bpp)          /* allocation group hdr buf */
1356 {
1357         xfs_agi_t       *agi;           /* allocation group header */
1358         int             agi_ok;         /* agi is consistent */
1359         xfs_buf_t       *bp;            /* allocation group hdr buf */
1360         xfs_perag_t     *pag;           /* per allocation group data */
1361         int             error;
1362
1363         ASSERT(agno != NULLAGNUMBER);
1364         error = xfs_trans_read_buf(
1365                         mp, tp, mp->m_ddev_targp,
1366                         XFS_AG_DADDR(mp, agno, XFS_AGI_DADDR(mp)),
1367                         XFS_FSS_TO_BB(mp, 1), 0, &bp);
1368         if (error)
1369                 return error;
1370         ASSERT(bp && !XFS_BUF_GETERROR(bp));
1371
1372         /*
1373          * Validate the magic number of the agi block.
1374          */
1375         agi = XFS_BUF_TO_AGI(bp);
1376         agi_ok =
1377                 be32_to_cpu(agi->agi_magicnum) == XFS_AGI_MAGIC &&
1378                 XFS_AGI_GOOD_VERSION(be32_to_cpu(agi->agi_versionnum));
1379         if (unlikely(XFS_TEST_ERROR(!agi_ok, mp, XFS_ERRTAG_IALLOC_READ_AGI,
1380                         XFS_RANDOM_IALLOC_READ_AGI))) {
1381                 XFS_CORRUPTION_ERROR("xfs_ialloc_read_agi", XFS_ERRLEVEL_LOW,
1382                                      mp, agi);
1383                 xfs_trans_brelse(tp, bp);
1384                 return XFS_ERROR(EFSCORRUPTED);
1385         }
1386         pag = &mp->m_perag[agno];
1387         if (!pag->pagi_init) {
1388                 pag->pagi_freecount = be32_to_cpu(agi->agi_freecount);
1389                 pag->pagi_init = 1;
1390         } else {
1391                 /*
1392                  * It's possible for these to be out of sync if
1393                  * we are in the middle of a forced shutdown.
1394                  */
1395                 ASSERT(pag->pagi_freecount == be32_to_cpu(agi->agi_freecount) ||
1396                         XFS_FORCED_SHUTDOWN(mp));
1397         }
1398
1399 #ifdef DEBUG
1400         {
1401                 int     i;
1402
1403                 for (i = 0; i < XFS_AGI_UNLINKED_BUCKETS; i++)
1404                         ASSERT(agi->agi_unlinked[i]);
1405         }
1406 #endif
1407
1408         XFS_BUF_SET_VTYPE_REF(bp, B_FS_AGI, XFS_AGI_REF);
1409         *bpp = bp;
1410         return 0;
1411 }