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