Linux-2.6.12-rc2
[linux-2.6.git] / fs / jfs / jfs_extent.c
1 /*
2  *   Copyright (C) International Business Machines Corp., 2000-2004
3  *
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.
8  * 
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.
13  *
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
17  */
18
19 #include <linux/fs.h>
20 #include <linux/quotaops.h>
21 #include "jfs_incore.h"
22 #include "jfs_superblock.h"
23 #include "jfs_dmap.h"
24 #include "jfs_extent.h"
25 #include "jfs_debug.h"
26
27 /*
28  * forward references
29  */
30 static int extBalloc(struct inode *, s64, s64 *, s64 *);
31 #ifdef _NOTYET
32 static int extBrealloc(struct inode *, s64, s64, s64 *, s64 *);
33 #endif
34 static s64 extRoundDown(s64 nb);
35
36 /*
37  * external references
38  */
39 extern int jfs_commit_inode(struct inode *, int);
40
41
42 #define DPD(a)          (printk("(a): %d\n",(a)))
43 #define DPC(a)          (printk("(a): %c\n",(a)))
44 #define DPL1(a)                                 \
45 {                                               \
46         if ((a) >> 32)                          \
47                 printk("(a): %x%08x  ",(a));    \
48         else                                    \
49                 printk("(a): %x  ",(a) << 32);  \
50 }
51 #define DPL(a)                                  \
52 {                                               \
53         if ((a) >> 32)                          \
54                 printk("(a): %x%08x\n",(a));    \
55         else                                    \
56                 printk("(a): %x\n",(a) << 32);  \
57 }
58
59 #define DPD1(a)         (printk("(a): %d  ",(a)))
60 #define DPX(a)          (printk("(a): %08x\n",(a)))
61 #define DPX1(a)         (printk("(a): %08x  ",(a)))
62 #define DPS(a)          (printk("%s\n",(a)))
63 #define DPE(a)          (printk("\nENTERING: %s\n",(a)))
64 #define DPE1(a)          (printk("\nENTERING: %s",(a)))
65 #define DPS1(a)         (printk("  %s  ",(a)))
66
67
68 /*
69  * NAME:        extAlloc()
70  *
71  * FUNCTION:    allocate an extent for a specified page range within a
72  *              file.
73  *
74  * PARAMETERS:
75  *      ip      - the inode of the file.
76  *      xlen    - requested extent length.
77  *      pno     - the starting page number with the file.
78  *      xp      - pointer to an xad.  on entry, xad describes an
79  *                extent that is used as an allocation hint if the
80  *                xaddr of the xad is non-zero.  on successful exit,
81  *                the xad describes the newly allocated extent.
82  *      abnr    - boolean_t indicating whether the newly allocated extent
83  *                should be marked as allocated but not recorded.
84  *
85  * RETURN VALUES:
86  *      0       - success
87  *      -EIO    - i/o error.
88  *      -ENOSPC - insufficient disk resources.
89  */
90 int
91 extAlloc(struct inode *ip, s64 xlen, s64 pno, xad_t * xp, boolean_t abnr)
92 {
93         struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
94         s64 nxlen, nxaddr, xoff, hint, xaddr = 0;
95         int rc;
96         int xflag;
97
98         /* This blocks if we are low on resources */
99         txBeginAnon(ip->i_sb);
100
101         /* Avoid race with jfs_commit_inode() */
102         down(&JFS_IP(ip)->commit_sem);
103
104         /* validate extent length */
105         if (xlen > MAXXLEN)
106                 xlen = MAXXLEN;
107
108         /* get the page's starting extent offset */
109         xoff = pno << sbi->l2nbperpage;
110
111         /* check if an allocation hint was provided */
112         if ((hint = addressXAD(xp))) {
113                 /* get the size of the extent described by the hint */
114                 nxlen = lengthXAD(xp);
115
116                 /* check if the hint is for the portion of the file
117                  * immediately previous to the current allocation
118                  * request and if hint extent has the same abnr
119                  * value as the current request.  if so, we can
120                  * extend the hint extent to include the current
121                  * extent if we can allocate the blocks immediately
122                  * following the hint extent.
123                  */
124                 if (offsetXAD(xp) + nxlen == xoff &&
125                     abnr == ((xp->flag & XAD_NOTRECORDED) ? TRUE : FALSE))
126                         xaddr = hint + nxlen;
127
128                 /* adjust the hint to the last block of the extent */
129                 hint += (nxlen - 1);
130         }
131
132         /* allocate the disk blocks for the extent.  initially, extBalloc()
133          * will try to allocate disk blocks for the requested size (xlen). 
134          * if this fails (xlen contigious free blocks not avaliable), it'll
135          * try to allocate a smaller number of blocks (producing a smaller
136          * extent), with this smaller number of blocks consisting of the
137          * requested number of blocks rounded down to the next smaller
138          * power of 2 number (i.e. 16 -> 8).  it'll continue to round down
139          * and retry the allocation until the number of blocks to allocate
140          * is smaller than the number of blocks per page.
141          */
142         nxlen = xlen;
143         if ((rc = extBalloc(ip, hint ? hint : INOHINT(ip), &nxlen, &nxaddr))) {
144                 up(&JFS_IP(ip)->commit_sem);
145                 return (rc);
146         }
147
148         /* Allocate blocks to quota. */
149         if (DQUOT_ALLOC_BLOCK(ip, nxlen)) {
150                 dbFree(ip, nxaddr, (s64) nxlen);
151                 up(&JFS_IP(ip)->commit_sem);
152                 return -EDQUOT;
153         }
154
155         /* determine the value of the extent flag */
156         xflag = (abnr == TRUE) ? XAD_NOTRECORDED : 0;
157
158         /* if we can extend the hint extent to cover the current request, 
159          * extend it.  otherwise, insert a new extent to
160          * cover the current request.
161          */
162         if (xaddr && xaddr == nxaddr)
163                 rc = xtExtend(0, ip, xoff, (int) nxlen, 0);
164         else
165                 rc = xtInsert(0, ip, xflag, xoff, (int) nxlen, &nxaddr, 0);
166
167         /* if the extend or insert failed, 
168          * free the newly allocated blocks and return the error.
169          */
170         if (rc) {
171                 dbFree(ip, nxaddr, nxlen);
172                 DQUOT_FREE_BLOCK(ip, nxlen);
173                 up(&JFS_IP(ip)->commit_sem);
174                 return (rc);
175         }
176
177         /* set the results of the extent allocation */
178         XADaddress(xp, nxaddr);
179         XADlength(xp, nxlen);
180         XADoffset(xp, xoff);
181         xp->flag = xflag;
182
183         mark_inode_dirty(ip);
184
185         up(&JFS_IP(ip)->commit_sem);
186         /*
187          * COMMIT_SyncList flags an anonymous tlock on page that is on
188          * sync list.
189          * We need to commit the inode to get the page written disk.
190          */
191         if (test_and_clear_cflag(COMMIT_Synclist,ip))
192                 jfs_commit_inode(ip, 0);
193
194         return (0);
195 }
196
197
198 #ifdef _NOTYET
199 /*
200  * NAME:        extRealloc()
201  *
202  * FUNCTION:    extend the allocation of a file extent containing a
203  *              partial back last page.
204  *
205  * PARAMETERS:
206  *      ip      - the inode of the file.
207  *      cp      - cbuf for the partial backed last page.
208  *      xlen    - request size of the resulting extent.
209  *      xp      - pointer to an xad. on successful exit, the xad
210  *                describes the newly allocated extent.
211  *      abnr    - boolean_t indicating whether the newly allocated extent
212  *                should be marked as allocated but not recorded.
213  *
214  * RETURN VALUES:
215  *      0       - success
216  *      -EIO    - i/o error.
217  *      -ENOSPC - insufficient disk resources.
218  */
219 int extRealloc(struct inode *ip, s64 nxlen, xad_t * xp, boolean_t abnr)
220 {
221         struct super_block *sb = ip->i_sb;
222         s64 xaddr, xlen, nxaddr, delta, xoff;
223         s64 ntail, nextend, ninsert;
224         int rc, nbperpage = JFS_SBI(sb)->nbperpage;
225         int xflag;
226
227         /* This blocks if we are low on resources */
228         txBeginAnon(ip->i_sb);
229
230         down(&JFS_IP(ip)->commit_sem);
231         /* validate extent length */
232         if (nxlen > MAXXLEN)
233                 nxlen = MAXXLEN;
234
235         /* get the extend (partial) page's disk block address and
236          * number of blocks.
237          */
238         xaddr = addressXAD(xp);
239         xlen = lengthXAD(xp);
240         xoff = offsetXAD(xp);
241
242         /* if the extend page is abnr and if the request is for
243          * the extent to be allocated and recorded, 
244          * make the page allocated and recorded.
245          */
246         if ((xp->flag & XAD_NOTRECORDED) && !abnr) {
247                 xp->flag = 0;
248                 if ((rc = xtUpdate(0, ip, xp)))
249                         goto exit;
250         }
251
252         /* try to allocated the request number of blocks for the
253          * extent.  dbRealloc() first tries to satisfy the request
254          * by extending the allocation in place. otherwise, it will
255          * try to allocate a new set of blocks large enough for the
256          * request.  in satisfying a request, dbReAlloc() may allocate
257          * less than what was request but will always allocate enough
258          * space as to satisfy the extend page.
259          */
260         if ((rc = extBrealloc(ip, xaddr, xlen, &nxlen, &nxaddr)))
261                 goto exit;
262
263         /* Allocat blocks to quota. */
264         if (DQUOT_ALLOC_BLOCK(ip, nxlen)) {
265                 dbFree(ip, nxaddr, (s64) nxlen);
266                 up(&JFS_IP(ip)->commit_sem);
267                 return -EDQUOT;
268         }
269
270         delta = nxlen - xlen;
271
272         /* check if the extend page is not abnr but the request is abnr
273          * and the allocated disk space is for more than one page.  if this
274          * is the case, there is a miss match of abnr between the extend page
275          * and the one or more pages following the extend page.  as a result,
276          * two extents will have to be manipulated. the first will be that
277          * of the extent of the extend page and will be manipulated thru
278          * an xtExtend() or an xtTailgate(), depending upon whether the
279          * disk allocation occurred as an inplace extension.  the second
280          * extent will be manipulated (created) through an xtInsert() and
281          * will be for the pages following the extend page.
282          */
283         if (abnr && (!(xp->flag & XAD_NOTRECORDED)) && (nxlen > nbperpage)) {
284                 ntail = nbperpage;
285                 nextend = ntail - xlen;
286                 ninsert = nxlen - nbperpage;
287
288                 xflag = XAD_NOTRECORDED;
289         } else {
290                 ntail = nxlen;
291                 nextend = delta;
292                 ninsert = 0;
293
294                 xflag = xp->flag;
295         }
296
297         /* if we were able to extend the disk allocation in place,
298          * extend the extent.  otherwise, move the extent to a
299          * new disk location.
300          */
301         if (xaddr == nxaddr) {
302                 /* extend the extent */
303                 if ((rc = xtExtend(0, ip, xoff + xlen, (int) nextend, 0))) {
304                         dbFree(ip, xaddr + xlen, delta);
305                         DQUOT_FREE_BLOCK(ip, nxlen);
306                         goto exit;
307                 }
308         } else {
309                 /*
310                  * move the extent to a new location:
311                  *
312                  * xtTailgate() accounts for relocated tail extent;
313                  */
314                 if ((rc = xtTailgate(0, ip, xoff, (int) ntail, nxaddr, 0))) {
315                         dbFree(ip, nxaddr, nxlen);
316                         DQUOT_FREE_BLOCK(ip, nxlen);
317                         goto exit;
318                 }
319         }
320
321
322         /* check if we need to also insert a new extent */
323         if (ninsert) {
324                 /* perform the insert.  if it fails, free the blocks
325                  * to be inserted and make it appear that we only did
326                  * the xtExtend() or xtTailgate() above.
327                  */
328                 xaddr = nxaddr + ntail;
329                 if (xtInsert (0, ip, xflag, xoff + ntail, (int) ninsert,
330                               &xaddr, 0)) {
331                         dbFree(ip, xaddr, (s64) ninsert);
332                         delta = nextend;
333                         nxlen = ntail;
334                         xflag = 0;
335                 }
336         }
337
338         /* set the return results */
339         XADaddress(xp, nxaddr);
340         XADlength(xp, nxlen);
341         XADoffset(xp, xoff);
342         xp->flag = xflag;
343
344         mark_inode_dirty(ip);
345 exit:
346         up(&JFS_IP(ip)->commit_sem);
347         return (rc);
348 }
349 #endif                  /* _NOTYET */
350
351
352 /*
353  * NAME:        extHint()
354  *
355  * FUNCTION:    produce an extent allocation hint for a file offset.
356  *
357  * PARAMETERS:
358  *      ip      - the inode of the file.
359  *      offset  - file offset for which the hint is needed.
360  *      xp      - pointer to the xad that is to be filled in with
361  *                the hint.
362  *
363  * RETURN VALUES:
364  *      0       - success
365  *      -EIO    - i/o error.
366  */
367 int extHint(struct inode *ip, s64 offset, xad_t * xp)
368 {
369         struct super_block *sb = ip->i_sb;
370         struct xadlist xadl;
371         struct lxdlist lxdl;
372         lxd_t lxd;
373         s64 prev;
374         int rc, nbperpage = JFS_SBI(sb)->nbperpage;
375
376         /* init the hint as "no hint provided" */
377         XADaddress(xp, 0);
378
379         /* determine the starting extent offset of the page previous
380          * to the page containing the offset.
381          */
382         prev = ((offset & ~POFFSET) >> JFS_SBI(sb)->l2bsize) - nbperpage;
383
384         /* if the offsets in the first page of the file,
385          * no hint provided.
386          */
387         if (prev < 0)
388                 return (0);
389
390         /* prepare to lookup the previous page's extent info */
391         lxdl.maxnlxd = 1;
392         lxdl.nlxd = 1;
393         lxdl.lxd = &lxd;
394         LXDoffset(&lxd, prev)
395             LXDlength(&lxd, nbperpage);
396
397         xadl.maxnxad = 1;
398         xadl.nxad = 0;
399         xadl.xad = xp;
400
401         /* perform the lookup */
402         if ((rc = xtLookupList(ip, &lxdl, &xadl, 0)))
403                 return (rc);
404
405         /* check if not extent exists for the previous page.  
406          * this is possible for sparse files.
407          */
408         if (xadl.nxad == 0) {
409 //              assert(ISSPARSE(ip));
410                 return (0);
411         }
412
413         /* only preserve the abnr flag within the xad flags
414          * of the returned hint.
415          */
416         xp->flag &= XAD_NOTRECORDED;
417
418         if(xadl.nxad != 1 || lengthXAD(xp) != nbperpage) {          
419                 jfs_error(ip->i_sb, "extHint: corrupt xtree");
420                 return -EIO;
421         }
422
423         return (0);
424 }
425
426
427 /*
428  * NAME:        extRecord()
429  *
430  * FUNCTION:    change a page with a file from not recorded to recorded.
431  *
432  * PARAMETERS:
433  *      ip      - inode of the file.
434  *      cp      - cbuf of the file page.
435  *
436  * RETURN VALUES:
437  *      0       - success
438  *      -EIO    - i/o error.
439  *      -ENOSPC - insufficient disk resources.
440  */
441 int extRecord(struct inode *ip, xad_t * xp)
442 {
443         int rc;
444
445         txBeginAnon(ip->i_sb);
446
447         down(&JFS_IP(ip)->commit_sem);
448
449         /* update the extent */
450         rc = xtUpdate(0, ip, xp);
451
452         up(&JFS_IP(ip)->commit_sem);
453         return rc;
454 }
455
456
457 #ifdef _NOTYET
458 /*
459  * NAME:        extFill()
460  *
461  * FUNCTION:    allocate disk space for a file page that represents
462  *              a file hole.
463  *
464  * PARAMETERS:
465  *      ip      - the inode of the file.
466  *      cp      - cbuf of the file page represent the hole.
467  *
468  * RETURN VALUES:
469  *      0       - success
470  *      -EIO    - i/o error.
471  *      -ENOSPC - insufficient disk resources.
472  */
473 int extFill(struct inode *ip, xad_t * xp)
474 {
475         int rc, nbperpage = JFS_SBI(ip->i_sb)->nbperpage;
476         s64 blkno = offsetXAD(xp) >> ip->i_blksize;
477
478 //      assert(ISSPARSE(ip));
479
480         /* initialize the extent allocation hint */
481         XADaddress(xp, 0);
482
483         /* allocate an extent to fill the hole */
484         if ((rc = extAlloc(ip, nbperpage, blkno, xp, FALSE)))
485                 return (rc);
486
487         assert(lengthPXD(xp) == nbperpage);
488
489         return (0);
490 }
491 #endif                  /* _NOTYET */
492
493
494 /*
495  * NAME:        extBalloc()
496  *
497  * FUNCTION:    allocate disk blocks to form an extent.
498  *
499  *              initially, we will try to allocate disk blocks for the
500  *              requested size (nblocks).  if this fails (nblocks 
501  *              contigious free blocks not avaliable), we'll try to allocate
502  *              a smaller number of blocks (producing a smaller extent), with
503  *              this smaller number of blocks consisting of the requested
504  *              number of blocks rounded down to the next smaller power of 2
505  *              number (i.e. 16 -> 8).  we'll continue to round down and
506  *              retry the allocation until the number of blocks to allocate
507  *              is smaller than the number of blocks per page.
508  *              
509  * PARAMETERS:
510  *      ip       - the inode of the file.
511  *      hint     - disk block number to be used as an allocation hint.
512  *      *nblocks - pointer to an s64 value.  on entry, this value specifies
513  *                 the desired number of block to be allocated. on successful
514  *                 exit, this value is set to the number of blocks actually
515  *                 allocated.
516  *      blkno    - pointer to a block address that is filled in on successful
517  *                 return with the starting block number of the newly 
518  *                 allocated block range.
519  *
520  * RETURN VALUES:
521  *      0       - success
522  *      -EIO    - i/o error.
523  *      -ENOSPC - insufficient disk resources.
524  */
525 static int
526 extBalloc(struct inode *ip, s64 hint, s64 * nblocks, s64 * blkno)
527 {
528         struct jfs_inode_info *ji = JFS_IP(ip);
529         struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
530         s64 nb, nblks, daddr, max;
531         int rc, nbperpage = sbi->nbperpage;
532         struct bmap *bmp = sbi->bmap;
533         int ag;
534
535         /* get the number of blocks to initially attempt to allocate.
536          * we'll first try the number of blocks requested unless this
537          * number is greater than the maximum number of contigious free
538          * blocks in the map. in that case, we'll start off with the 
539          * maximum free.
540          */
541         max = (s64) 1 << bmp->db_maxfreebud;
542         if (*nblocks >= max && *nblocks > nbperpage)
543                 nb = nblks = (max > nbperpage) ? max : nbperpage;
544         else
545                 nb = nblks = *nblocks;
546
547         /* try to allocate blocks */
548         while ((rc = dbAlloc(ip, hint, nb, &daddr)) != 0) {
549                 /* if something other than an out of space error,
550                  * stop and return this error.
551                  */
552                 if (rc != -ENOSPC)
553                         return (rc);
554
555                 /* decrease the allocation request size */
556                 nb = min(nblks, extRoundDown(nb));
557
558                 /* give up if we cannot cover a page */
559                 if (nb < nbperpage)
560                         return (rc);
561         }
562
563         *nblocks = nb;
564         *blkno = daddr;
565
566         if (S_ISREG(ip->i_mode) && (ji->fileset == FILESYSTEM_I)) {
567                 ag = BLKTOAG(daddr, sbi);
568                 spin_lock_irq(&ji->ag_lock);
569                 if (ji->active_ag == -1) {
570                         atomic_inc(&bmp->db_active[ag]);
571                         ji->active_ag = ag;
572                 } else if (ji->active_ag != ag) {
573                         atomic_dec(&bmp->db_active[ji->active_ag]);
574                         atomic_inc(&bmp->db_active[ag]);
575                         ji->active_ag = ag;
576                 }
577                 spin_unlock_irq(&ji->ag_lock);
578         }
579
580         return (0);
581 }
582
583
584 #ifdef _NOTYET
585 /*
586  * NAME:        extBrealloc()
587  *
588  * FUNCTION:    attempt to extend an extent's allocation.
589  *
590  *              initially, we will try to extend the extent's allocation
591  *              in place.  if this fails, we'll try to move the extent
592  *              to a new set of blocks. if moving the extent, we initially
593  *              will try to allocate disk blocks for the requested size
594  *              (nnew).  if this fails  (nnew contigious free blocks not
595  *              avaliable), we'll try  to allocate a smaller number of
596  *              blocks (producing a smaller extent), with this smaller
597  *              number of blocks consisting of the requested number of
598  *              blocks rounded down to the next smaller power of 2
599  *              number (i.e. 16 -> 8).  we'll continue to round down and
600  *              retry the allocation until the number of blocks to allocate
601  *              is smaller than the number of blocks per page.
602  *              
603  * PARAMETERS:
604  *      ip       - the inode of the file.
605  *      blkno    - starting block number of the extents current allocation.
606  *      nblks    - number of blocks within the extents current allocation.
607  *      newnblks - pointer to a s64 value.  on entry, this value is the
608  *                 the new desired extent size (number of blocks).  on
609  *                 successful exit, this value is set to the extent's actual
610  *                 new size (new number of blocks).
611  *      newblkno - the starting block number of the extents new allocation.
612  *
613  * RETURN VALUES:
614  *      0       - success
615  *      -EIO    - i/o error.
616  *      -ENOSPC - insufficient disk resources.
617  */
618 static int
619 extBrealloc(struct inode *ip,
620             s64 blkno, s64 nblks, s64 * newnblks, s64 * newblkno)
621 {
622         int rc;
623
624         /* try to extend in place */
625         if ((rc = dbExtend(ip, blkno, nblks, *newnblks - nblks)) == 0) {
626                 *newblkno = blkno;
627                 return (0);
628         } else {
629                 if (rc != -ENOSPC)
630                         return (rc);
631         }
632
633         /* in place extension not possible.  
634          * try to move the extent to a new set of blocks.
635          */
636         return (extBalloc(ip, blkno, newnblks, newblkno));
637 }
638 #endif                  /* _NOTYET */
639
640
641 /*
642  * NAME:        extRoundDown()
643  *
644  * FUNCTION:    round down a specified number of blocks to the next
645  *              smallest power of 2 number.
646  *
647  * PARAMETERS:
648  *      nb      - the inode of the file.
649  *
650  * RETURN VALUES:
651  *      next smallest power of 2 number.
652  */
653 static s64 extRoundDown(s64 nb)
654 {
655         int i;
656         u64 m, k;
657
658         for (i = 0, m = (u64) 1 << 63; i < 64; i++, m >>= 1) {
659                 if (m & nb)
660                         break;
661         }
662
663         i = 63 - i;
664         k = (u64) 1 << i;
665         k = ((k - 1) & nb) ? k : k >> 1;
666
667         return (k);
668 }