2 * Copyright (C) International Business Machines Corp., 2000-2004
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
12 * the GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 #include <linux/quotaops.h>
21 #include <linux/vs_dlimit.h>
22 #include "jfs_incore.h"
23 #include "jfs_inode.h"
24 #include "jfs_superblock.h"
26 #include "jfs_extent.h"
27 #include "jfs_debug.h"
32 static int extBalloc(struct inode *, s64, s64 *, s64 *);
34 static int extBrealloc(struct inode *, s64, s64, s64 *, s64 *);
36 static s64 extRoundDown(s64 nb);
38 #define DPD(a) (printk("(a): %d\n",(a)))
39 #define DPC(a) (printk("(a): %c\n",(a)))
43 printk("(a): %x%08x ",(a)); \
45 printk("(a): %x ",(a) << 32); \
50 printk("(a): %x%08x\n",(a)); \
52 printk("(a): %x\n",(a) << 32); \
55 #define DPD1(a) (printk("(a): %d ",(a)))
56 #define DPX(a) (printk("(a): %08x\n",(a)))
57 #define DPX1(a) (printk("(a): %08x ",(a)))
58 #define DPS(a) (printk("%s\n",(a)))
59 #define DPE(a) (printk("\nENTERING: %s\n",(a)))
60 #define DPE1(a) (printk("\nENTERING: %s",(a)))
61 #define DPS1(a) (printk(" %s ",(a)))
67 * FUNCTION: allocate an extent for a specified page range within a
71 * ip - the inode of the file.
72 * xlen - requested extent length.
73 * pno - the starting page number with the file.
74 * xp - pointer to an xad. on entry, xad describes an
75 * extent that is used as an allocation hint if the
76 * xaddr of the xad is non-zero. on successful exit,
77 * the xad describes the newly allocated extent.
78 * abnr - boolean_t indicating whether the newly allocated extent
79 * should be marked as allocated but not recorded.
84 * -ENOSPC - insufficient disk resources.
87 extAlloc(struct inode *ip, s64 xlen, s64 pno, xad_t * xp, boolean_t abnr)
89 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
90 s64 nxlen, nxaddr, xoff, hint, xaddr = 0;
94 /* This blocks if we are low on resources */
95 txBeginAnon(ip->i_sb);
97 /* Avoid race with jfs_commit_inode() */
98 mutex_lock(&JFS_IP(ip)->commit_mutex);
100 /* validate extent length */
104 /* get the page's starting extent offset */
105 xoff = pno << sbi->l2nbperpage;
107 /* check if an allocation hint was provided */
108 if ((hint = addressXAD(xp))) {
109 /* get the size of the extent described by the hint */
110 nxlen = lengthXAD(xp);
112 /* check if the hint is for the portion of the file
113 * immediately previous to the current allocation
114 * request and if hint extent has the same abnr
115 * value as the current request. if so, we can
116 * extend the hint extent to include the current
117 * extent if we can allocate the blocks immediately
118 * following the hint extent.
120 if (offsetXAD(xp) + nxlen == xoff &&
121 abnr == ((xp->flag & XAD_NOTRECORDED) ? TRUE : FALSE))
122 xaddr = hint + nxlen;
124 /* adjust the hint to the last block of the extent */
128 /* allocate the disk blocks for the extent. initially, extBalloc()
129 * will try to allocate disk blocks for the requested size (xlen).
130 * if this fails (xlen contiguous free blocks not avaliable), it'll
131 * try to allocate a smaller number of blocks (producing a smaller
132 * extent), with this smaller number of blocks consisting of the
133 * requested number of blocks rounded down to the next smaller
134 * power of 2 number (i.e. 16 -> 8). it'll continue to round down
135 * and retry the allocation until the number of blocks to allocate
136 * is smaller than the number of blocks per page.
139 if ((rc = extBalloc(ip, hint ? hint : INOHINT(ip), &nxlen, &nxaddr))) {
140 mutex_unlock(&JFS_IP(ip)->commit_mutex);
144 /* Allocate blocks to quota. */
145 if (DQUOT_ALLOC_BLOCK(ip, nxlen)) {
146 dbFree(ip, nxaddr, (s64) nxlen);
147 mutex_unlock(&JFS_IP(ip)->commit_mutex);
150 /* Allocate blocks to dlimit. */
151 if (DLIMIT_ALLOC_BLOCK(ip, nxlen)) {
152 DQUOT_FREE_BLOCK(ip, nxlen);
153 dbFree(ip, nxaddr, (s64) nxlen);
154 mutex_unlock(&JFS_IP(ip)->commit_mutex);
158 /* determine the value of the extent flag */
159 xflag = (abnr == TRUE) ? XAD_NOTRECORDED : 0;
161 /* if we can extend the hint extent to cover the current request,
162 * extend it. otherwise, insert a new extent to
163 * cover the current request.
165 if (xaddr && xaddr == nxaddr)
166 rc = xtExtend(0, ip, xoff, (int) nxlen, 0);
168 rc = xtInsert(0, ip, xflag, xoff, (int) nxlen, &nxaddr, 0);
170 /* if the extend or insert failed,
171 * free the newly allocated blocks and return the error.
174 dbFree(ip, nxaddr, nxlen);
175 DLIMIT_FREE_BLOCK(ip, nxlen);
176 DQUOT_FREE_BLOCK(ip, nxlen);
177 mutex_unlock(&JFS_IP(ip)->commit_mutex);
181 /* set the results of the extent allocation */
182 XADaddress(xp, nxaddr);
183 XADlength(xp, nxlen);
187 mark_inode_dirty(ip);
189 mutex_unlock(&JFS_IP(ip)->commit_mutex);
191 * COMMIT_SyncList flags an anonymous tlock on page that is on
193 * We need to commit the inode to get the page written disk.
195 if (test_and_clear_cflag(COMMIT_Synclist,ip))
196 jfs_commit_inode(ip, 0);
206 * FUNCTION: extend the allocation of a file extent containing a
207 * partial back last page.
210 * ip - the inode of the file.
211 * cp - cbuf for the partial backed last page.
212 * xlen - request size of the resulting extent.
213 * xp - pointer to an xad. on successful exit, the xad
214 * describes the newly allocated extent.
215 * abnr - boolean_t indicating whether the newly allocated extent
216 * should be marked as allocated but not recorded.
221 * -ENOSPC - insufficient disk resources.
223 int extRealloc(struct inode *ip, s64 nxlen, xad_t * xp, boolean_t abnr)
225 struct super_block *sb = ip->i_sb;
226 s64 xaddr, xlen, nxaddr, delta, xoff;
227 s64 ntail, nextend, ninsert;
228 int rc, nbperpage = JFS_SBI(sb)->nbperpage;
231 /* This blocks if we are low on resources */
232 txBeginAnon(ip->i_sb);
234 mutex_lock(&JFS_IP(ip)->commit_mutex);
235 /* validate extent length */
239 /* get the extend (partial) page's disk block address and
242 xaddr = addressXAD(xp);
243 xlen = lengthXAD(xp);
244 xoff = offsetXAD(xp);
246 /* if the extend page is abnr and if the request is for
247 * the extent to be allocated and recorded,
248 * make the page allocated and recorded.
250 if ((xp->flag & XAD_NOTRECORDED) && !abnr) {
252 if ((rc = xtUpdate(0, ip, xp)))
256 /* try to allocated the request number of blocks for the
257 * extent. dbRealloc() first tries to satisfy the request
258 * by extending the allocation in place. otherwise, it will
259 * try to allocate a new set of blocks large enough for the
260 * request. in satisfying a request, dbReAlloc() may allocate
261 * less than what was request but will always allocate enough
262 * space as to satisfy the extend page.
264 if ((rc = extBrealloc(ip, xaddr, xlen, &nxlen, &nxaddr)))
267 /* Allocat blocks to quota. */
268 if (DQUOT_ALLOC_BLOCK(ip, nxlen)) {
269 dbFree(ip, nxaddr, (s64) nxlen);
270 mutex_unlock(&JFS_IP(ip)->commit_mutex);
273 /* Allocate blocks to dlimit. */
274 if (DLIMIT_ALLOC_BLOCK(ip, nxlen)) {
275 DQUOT_FREE_BLOCK(ip, nxlen);
276 dbFree(ip, nxaddr, (s64) nxlen);
277 up(&JFS_IP(ip)->commit_sem);
281 delta = nxlen - xlen;
283 /* check if the extend page is not abnr but the request is abnr
284 * and the allocated disk space is for more than one page. if this
285 * is the case, there is a miss match of abnr between the extend page
286 * and the one or more pages following the extend page. as a result,
287 * two extents will have to be manipulated. the first will be that
288 * of the extent of the extend page and will be manipulated thru
289 * an xtExtend() or an xtTailgate(), depending upon whether the
290 * disk allocation occurred as an inplace extension. the second
291 * extent will be manipulated (created) through an xtInsert() and
292 * will be for the pages following the extend page.
294 if (abnr && (!(xp->flag & XAD_NOTRECORDED)) && (nxlen > nbperpage)) {
296 nextend = ntail - xlen;
297 ninsert = nxlen - nbperpage;
299 xflag = XAD_NOTRECORDED;
308 /* if we were able to extend the disk allocation in place,
309 * extend the extent. otherwise, move the extent to a
312 if (xaddr == nxaddr) {
313 /* extend the extent */
314 if ((rc = xtExtend(0, ip, xoff + xlen, (int) nextend, 0))) {
315 dbFree(ip, xaddr + xlen, delta);
316 DLIMIT_FREE_BLOCK(ip, nxlen);
317 DQUOT_FREE_BLOCK(ip, nxlen);
322 * move the extent to a new location:
324 * xtTailgate() accounts for relocated tail extent;
326 if ((rc = xtTailgate(0, ip, xoff, (int) ntail, nxaddr, 0))) {
327 dbFree(ip, nxaddr, nxlen);
328 DLIMIT_FREE_BLOCK(ip, nxlen);
329 DQUOT_FREE_BLOCK(ip, nxlen);
335 /* check if we need to also insert a new extent */
337 /* perform the insert. if it fails, free the blocks
338 * to be inserted and make it appear that we only did
339 * the xtExtend() or xtTailgate() above.
341 xaddr = nxaddr + ntail;
342 if (xtInsert (0, ip, xflag, xoff + ntail, (int) ninsert,
344 dbFree(ip, xaddr, (s64) ninsert);
351 /* set the return results */
352 XADaddress(xp, nxaddr);
353 XADlength(xp, nxlen);
357 mark_inode_dirty(ip);
359 mutex_unlock(&JFS_IP(ip)->commit_mutex);
368 * FUNCTION: produce an extent allocation hint for a file offset.
371 * ip - the inode of the file.
372 * offset - file offset for which the hint is needed.
373 * xp - pointer to the xad that is to be filled in with
380 int extHint(struct inode *ip, s64 offset, xad_t * xp)
382 struct super_block *sb = ip->i_sb;
387 int rc, nbperpage = JFS_SBI(sb)->nbperpage;
389 /* init the hint as "no hint provided" */
392 /* determine the starting extent offset of the page previous
393 * to the page containing the offset.
395 prev = ((offset & ~POFFSET) >> JFS_SBI(sb)->l2bsize) - nbperpage;
397 /* if the offsets in the first page of the file,
403 /* prepare to lookup the previous page's extent info */
407 LXDoffset(&lxd, prev)
408 LXDlength(&lxd, nbperpage);
414 /* perform the lookup */
415 if ((rc = xtLookupList(ip, &lxdl, &xadl, 0)))
418 /* check if not extent exists for the previous page.
419 * this is possible for sparse files.
421 if (xadl.nxad == 0) {
422 // assert(ISSPARSE(ip));
426 /* only preserve the abnr flag within the xad flags
427 * of the returned hint.
429 xp->flag &= XAD_NOTRECORDED;
431 if(xadl.nxad != 1 || lengthXAD(xp) != nbperpage) {
432 jfs_error(ip->i_sb, "extHint: corrupt xtree");
443 * FUNCTION: change a page with a file from not recorded to recorded.
446 * ip - inode of the file.
447 * cp - cbuf of the file page.
452 * -ENOSPC - insufficient disk resources.
454 int extRecord(struct inode *ip, xad_t * xp)
458 txBeginAnon(ip->i_sb);
460 mutex_lock(&JFS_IP(ip)->commit_mutex);
462 /* update the extent */
463 rc = xtUpdate(0, ip, xp);
465 mutex_unlock(&JFS_IP(ip)->commit_mutex);
474 * FUNCTION: allocate disk space for a file page that represents
478 * ip - the inode of the file.
479 * cp - cbuf of the file page represent the hole.
484 * -ENOSPC - insufficient disk resources.
486 int extFill(struct inode *ip, xad_t * xp)
488 int rc, nbperpage = JFS_SBI(ip->i_sb)->nbperpage;
489 s64 blkno = offsetXAD(xp) >> ip->i_blkbits;
491 // assert(ISSPARSE(ip));
493 /* initialize the extent allocation hint */
496 /* allocate an extent to fill the hole */
497 if ((rc = extAlloc(ip, nbperpage, blkno, xp, FALSE)))
500 assert(lengthPXD(xp) == nbperpage);
510 * FUNCTION: allocate disk blocks to form an extent.
512 * initially, we will try to allocate disk blocks for the
513 * requested size (nblocks). if this fails (nblocks
514 * contiguous free blocks not avaliable), we'll try to allocate
515 * a smaller number of blocks (producing a smaller extent), with
516 * this smaller number of blocks consisting of the requested
517 * number of blocks rounded down to the next smaller power of 2
518 * number (i.e. 16 -> 8). we'll continue to round down and
519 * retry the allocation until the number of blocks to allocate
520 * is smaller than the number of blocks per page.
523 * ip - the inode of the file.
524 * hint - disk block number to be used as an allocation hint.
525 * *nblocks - pointer to an s64 value. on entry, this value specifies
526 * the desired number of block to be allocated. on successful
527 * exit, this value is set to the number of blocks actually
529 * blkno - pointer to a block address that is filled in on successful
530 * return with the starting block number of the newly
531 * allocated block range.
536 * -ENOSPC - insufficient disk resources.
539 extBalloc(struct inode *ip, s64 hint, s64 * nblocks, s64 * blkno)
541 struct jfs_inode_info *ji = JFS_IP(ip);
542 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
543 s64 nb, nblks, daddr, max;
544 int rc, nbperpage = sbi->nbperpage;
545 struct bmap *bmp = sbi->bmap;
548 /* get the number of blocks to initially attempt to allocate.
549 * we'll first try the number of blocks requested unless this
550 * number is greater than the maximum number of contiguous free
551 * blocks in the map. in that case, we'll start off with the
554 max = (s64) 1 << bmp->db_maxfreebud;
555 if (*nblocks >= max && *nblocks > nbperpage)
556 nb = nblks = (max > nbperpage) ? max : nbperpage;
558 nb = nblks = *nblocks;
560 /* try to allocate blocks */
561 while ((rc = dbAlloc(ip, hint, nb, &daddr)) != 0) {
562 /* if something other than an out of space error,
563 * stop and return this error.
568 /* decrease the allocation request size */
569 nb = min(nblks, extRoundDown(nb));
571 /* give up if we cannot cover a page */
579 if (S_ISREG(ip->i_mode) && (ji->fileset == FILESYSTEM_I)) {
580 ag = BLKTOAG(daddr, sbi);
581 spin_lock_irq(&ji->ag_lock);
582 if (ji->active_ag == -1) {
583 atomic_inc(&bmp->db_active[ag]);
585 } else if (ji->active_ag != ag) {
586 atomic_dec(&bmp->db_active[ji->active_ag]);
587 atomic_inc(&bmp->db_active[ag]);
590 spin_unlock_irq(&ji->ag_lock);
599 * NAME: extBrealloc()
601 * FUNCTION: attempt to extend an extent's allocation.
603 * initially, we will try to extend the extent's allocation
604 * in place. if this fails, we'll try to move the extent
605 * to a new set of blocks. if moving the extent, we initially
606 * will try to allocate disk blocks for the requested size
607 * (nnew). if this fails (new contiguous free blocks not
608 * avaliable), we'll try to allocate a smaller number of
609 * blocks (producing a smaller extent), with this smaller
610 * number of blocks consisting of the requested number of
611 * blocks rounded down to the next smaller power of 2
612 * number (i.e. 16 -> 8). we'll continue to round down and
613 * retry the allocation until the number of blocks to allocate
614 * is smaller than the number of blocks per page.
617 * ip - the inode of the file.
618 * blkno - starting block number of the extents current allocation.
619 * nblks - number of blocks within the extents current allocation.
620 * newnblks - pointer to a s64 value. on entry, this value is the
621 * the new desired extent size (number of blocks). on
622 * successful exit, this value is set to the extent's actual
623 * new size (new number of blocks).
624 * newblkno - the starting block number of the extents new allocation.
629 * -ENOSPC - insufficient disk resources.
632 extBrealloc(struct inode *ip,
633 s64 blkno, s64 nblks, s64 * newnblks, s64 * newblkno)
637 /* try to extend in place */
638 if ((rc = dbExtend(ip, blkno, nblks, *newnblks - nblks)) == 0) {
646 /* in place extension not possible.
647 * try to move the extent to a new set of blocks.
649 return (extBalloc(ip, blkno, newnblks, newblkno));
655 * NAME: extRoundDown()
657 * FUNCTION: round down a specified number of blocks to the next
658 * smallest power of 2 number.
661 * nb - the inode of the file.
664 * next smallest power of 2 number.
666 static s64 extRoundDown(s64 nb)
671 for (i = 0, m = (u64) 1 << 63; i < 64; i++, m >>= 1) {
678 k = ((k - 1) & nb) ? k : k >> 1;