aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDave Kleikamp <shaggy@austin.ibm.com>2005-05-02 14:25:13 -0400
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-05-03 01:23:54 -0400
commit6628465e33ca694bd8fd5c3cf4eb7ff9177bc694 (patch)
treeb023d524fb0a3b71aa0b957ce7c5540611497370
parent1c6278295d6482edaaaef5faa64b18f17b3319b7 (diff)
[PATCH] JFS: Don't allocate extents that overlap existing extents
Modify xtSearch so that it returns the next allocated block when the requested block is unmapped. This can be used to make sure we don't create a new extent that overlaps the next one. Signed-off-by: Dave Kleikamp <shaggy@austin.ibm.com> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
-rw-r--r--fs/jfs/inode.c6
-rw-r--r--fs/jfs/jfs_dtree.c4
-rw-r--r--fs/jfs/jfs_xtree.c61
3 files changed, 46 insertions, 25 deletions
diff --git a/fs/jfs/inode.c b/fs/jfs/inode.c
index 6c04f5eda135..24a689179af2 100644
--- a/fs/jfs/inode.c
+++ b/fs/jfs/inode.c
@@ -178,7 +178,7 @@ jfs_get_blocks(struct inode *ip, sector_t lblock, unsigned long max_blocks,
178 xad_t xad; 178 xad_t xad;
179 s64 xaddr; 179 s64 xaddr;
180 int xflag; 180 int xflag;
181 s32 xlen; 181 s32 xlen = max_blocks;
182 182
183 /* 183 /*
184 * Take appropriate lock on inode 184 * Take appropriate lock on inode
@@ -190,7 +190,7 @@ jfs_get_blocks(struct inode *ip, sector_t lblock, unsigned long max_blocks,
190 190
191 if (((lblock64 << ip->i_sb->s_blocksize_bits) < ip->i_size) && 191 if (((lblock64 << ip->i_sb->s_blocksize_bits) < ip->i_size) &&
192 (!xtLookup(ip, lblock64, max_blocks, &xflag, &xaddr, &xlen, 0)) && 192 (!xtLookup(ip, lblock64, max_blocks, &xflag, &xaddr, &xlen, 0)) &&
193 xlen) { 193 xaddr) {
194 if (xflag & XAD_NOTRECORDED) { 194 if (xflag & XAD_NOTRECORDED) {
195 if (!create) 195 if (!create)
196 /* 196 /*
@@ -229,7 +229,7 @@ jfs_get_blocks(struct inode *ip, sector_t lblock, unsigned long max_blocks,
229#ifdef _JFS_4K 229#ifdef _JFS_4K
230 if ((rc = extHint(ip, lblock64 << ip->i_sb->s_blocksize_bits, &xad))) 230 if ((rc = extHint(ip, lblock64 << ip->i_sb->s_blocksize_bits, &xad)))
231 goto unlock; 231 goto unlock;
232 rc = extAlloc(ip, max_blocks, lblock64, &xad, FALSE); 232 rc = extAlloc(ip, xlen, lblock64, &xad, FALSE);
233 if (rc) 233 if (rc)
234 goto unlock; 234 goto unlock;
235 235
diff --git a/fs/jfs/jfs_dtree.c b/fs/jfs/jfs_dtree.c
index 453bace608d1..ac41f72d6d50 100644
--- a/fs/jfs/jfs_dtree.c
+++ b/fs/jfs/jfs_dtree.c
@@ -212,7 +212,7 @@ static struct metapage *read_index_page(struct inode *inode, s64 blkno)
212 s32 xlen; 212 s32 xlen;
213 213
214 rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1); 214 rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1);
215 if (rc || (xlen == 0)) 215 if (rc || (xaddr == 0))
216 return NULL; 216 return NULL;
217 217
218 return read_metapage(inode, xaddr, PSIZE, 1); 218 return read_metapage(inode, xaddr, PSIZE, 1);
@@ -231,7 +231,7 @@ static struct metapage *get_index_page(struct inode *inode, s64 blkno)
231 s32 xlen; 231 s32 xlen;
232 232
233 rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1); 233 rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1);
234 if (rc || (xlen == 0)) 234 if (rc || (xaddr == 0))
235 return NULL; 235 return NULL;
236 236
237 return get_metapage(inode, xaddr, PSIZE, 1); 237 return get_metapage(inode, xaddr, PSIZE, 1);
diff --git a/fs/jfs/jfs_xtree.c b/fs/jfs/jfs_xtree.c
index 11c58c54b818..2c1f311914a1 100644
--- a/fs/jfs/jfs_xtree.c
+++ b/fs/jfs/jfs_xtree.c
@@ -111,8 +111,8 @@ static struct {
111/* 111/*
112 * forward references 112 * forward references
113 */ 113 */
114static int xtSearch(struct inode *ip, 114static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp,
115 s64 xoff, int *cmpp, struct btstack * btstack, int flag); 115 struct btstack * btstack, int flag);
116 116
117static int xtSplitUp(tid_t tid, 117static int xtSplitUp(tid_t tid,
118 struct inode *ip, 118 struct inode *ip,
@@ -159,11 +159,12 @@ int xtLookup(struct inode *ip, s64 lstart,
159 xtpage_t *p; 159 xtpage_t *p;
160 int index; 160 int index;
161 xad_t *xad; 161 xad_t *xad;
162 s64 size, xoff, xend; 162 s64 next, size, xoff, xend;
163 int xlen; 163 int xlen;
164 s64 xaddr; 164 s64 xaddr;
165 165
166 *plen = 0; 166 *paddr = 0;
167 *plen = llen;
167 168
168 if (!no_check) { 169 if (!no_check) {
169 /* is lookup offset beyond eof ? */ 170 /* is lookup offset beyond eof ? */
@@ -180,7 +181,7 @@ int xtLookup(struct inode *ip, s64 lstart,
180 * search for the xad entry covering the logical extent 181 * search for the xad entry covering the logical extent
181 */ 182 */
182//search: 183//search:
183 if ((rc = xtSearch(ip, lstart, &cmp, &btstack, 0))) { 184 if ((rc = xtSearch(ip, lstart, &next, &cmp, &btstack, 0))) {
184 jfs_err("xtLookup: xtSearch returned %d", rc); 185 jfs_err("xtLookup: xtSearch returned %d", rc);
185 return rc; 186 return rc;
186 } 187 }
@@ -198,8 +199,11 @@ int xtLookup(struct inode *ip, s64 lstart,
198 * lstart is a page start address, 199 * lstart is a page start address,
199 * i.e., lstart cannot start in a hole; 200 * i.e., lstart cannot start in a hole;
200 */ 201 */
201 if (cmp) 202 if (cmp) {
203 if (next)
204 *plen = min(next - lstart, llen);
202 goto out; 205 goto out;
206 }
203 207
204 /* 208 /*
205 * lxd covered by xad 209 * lxd covered by xad
@@ -284,7 +288,7 @@ int xtLookupList(struct inode *ip, struct lxdlist * lxdlist,
284 if (lstart >= size) 288 if (lstart >= size)
285 return 0; 289 return 0;
286 290
287 if ((rc = xtSearch(ip, lstart, &cmp, &btstack, 0))) 291 if ((rc = xtSearch(ip, lstart, NULL, &cmp, &btstack, 0)))
288 return rc; 292 return rc;
289 293
290 /* 294 /*
@@ -488,6 +492,7 @@ int xtLookupList(struct inode *ip, struct lxdlist * lxdlist,
488 * parameters: 492 * parameters:
489 * ip - file object; 493 * ip - file object;
490 * xoff - extent offset; 494 * xoff - extent offset;
495 * nextp - address of next extent (if any) for search miss
491 * cmpp - comparison result: 496 * cmpp - comparison result:
492 * btstack - traverse stack; 497 * btstack - traverse stack;
493 * flag - search process flag (XT_INSERT); 498 * flag - search process flag (XT_INSERT);
@@ -497,7 +502,7 @@ int xtLookupList(struct inode *ip, struct lxdlist * lxdlist,
497 * *cmpp is set to result of comparison with the entry returned. 502 * *cmpp is set to result of comparison with the entry returned.
498 * the page containing the entry is pinned at exit. 503 * the page containing the entry is pinned at exit.
499 */ 504 */
500static int xtSearch(struct inode *ip, s64 xoff, /* offset of extent */ 505static int xtSearch(struct inode *ip, s64 xoff, s64 *nextp,
501 int *cmpp, struct btstack * btstack, int flag) 506 int *cmpp, struct btstack * btstack, int flag)
502{ 507{
503 struct jfs_inode_info *jfs_ip = JFS_IP(ip); 508 struct jfs_inode_info *jfs_ip = JFS_IP(ip);
@@ -511,6 +516,7 @@ static int xtSearch(struct inode *ip, s64 xoff, /* offset of extent */
511 struct btframe *btsp; 516 struct btframe *btsp;
512 int nsplit = 0; /* number of pages to split */ 517 int nsplit = 0; /* number of pages to split */
513 s64 t64; 518 s64 t64;
519 s64 next = 0;
514 520
515 INCREMENT(xtStat.search); 521 INCREMENT(xtStat.search);
516 522
@@ -579,6 +585,7 @@ static int xtSearch(struct inode *ip, s64 xoff, /* offset of extent */
579 * previous and this entry 585 * previous and this entry
580 */ 586 */
581 *cmpp = 1; 587 *cmpp = 1;
588 next = t64;
582 goto out; 589 goto out;
583 } 590 }
584 591
@@ -623,6 +630,9 @@ static int xtSearch(struct inode *ip, s64 xoff, /* offset of extent */
623 /* update sequential access heuristics */ 630 /* update sequential access heuristics */
624 jfs_ip->btindex = index; 631 jfs_ip->btindex = index;
625 632
633 if (nextp)
634 *nextp = next;
635
626 INCREMENT(xtStat.fastSearch); 636 INCREMENT(xtStat.fastSearch);
627 return 0; 637 return 0;
628 } 638 }
@@ -675,10 +685,11 @@ static int xtSearch(struct inode *ip, s64 xoff, /* offset of extent */
675 685
676 return 0; 686 return 0;
677 } 687 }
678
679 /* search hit - internal page: 688 /* search hit - internal page:
680 * descend/search its child page 689 * descend/search its child page
681 */ 690 */
691 if (index < p->header.nextindex - 1)
692 next = offsetXAD(&p->xad[index + 1]);
682 goto next; 693 goto next;
683 } 694 }
684 695
@@ -694,6 +705,8 @@ static int xtSearch(struct inode *ip, s64 xoff, /* offset of extent */
694 * base is the smallest index with key (Kj) greater than 705 * base is the smallest index with key (Kj) greater than
695 * search key (K) and may be zero or maxentry index. 706 * search key (K) and may be zero or maxentry index.
696 */ 707 */
708 if (base < p->header.nextindex)
709 next = offsetXAD(&p->xad[base]);
697 /* 710 /*
698 * search miss - leaf page: 711 * search miss - leaf page:
699 * 712 *
@@ -727,6 +740,9 @@ static int xtSearch(struct inode *ip, s64 xoff, /* offset of extent */
727 jfs_ip->btorder = BT_RANDOM; 740 jfs_ip->btorder = BT_RANDOM;
728 jfs_ip->btindex = base; 741 jfs_ip->btindex = base;
729 742
743 if (nextp)
744 *nextp = next;
745
730 return 0; 746 return 0;
731 } 747 }
732 748
@@ -793,6 +809,7 @@ int xtInsert(tid_t tid, /* transaction id */
793 struct xtsplit split; /* split information */ 809 struct xtsplit split; /* split information */
794 xad_t *xad; 810 xad_t *xad;
795 int cmp; 811 int cmp;
812 s64 next;
796 struct tlock *tlck; 813 struct tlock *tlck;
797 struct xtlock *xtlck; 814 struct xtlock *xtlck;
798 815
@@ -806,7 +823,7 @@ int xtInsert(tid_t tid, /* transaction id */
806 * n.b. xtSearch() may return index of maxentry of 823 * n.b. xtSearch() may return index of maxentry of
807 * the full page. 824 * the full page.
808 */ 825 */
809 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, XT_INSERT))) 826 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
810 return rc; 827 return rc;
811 828
812 /* retrieve search result */ 829 /* retrieve search result */
@@ -814,7 +831,7 @@ int xtInsert(tid_t tid, /* transaction id */
814 831
815 /* This test must follow XT_GETSEARCH since mp must be valid if 832 /* This test must follow XT_GETSEARCH since mp must be valid if
816 * we branch to out: */ 833 * we branch to out: */
817 if (cmp == 0) { 834 if ((cmp == 0) || (next && (xlen > next - xoff))) {
818 rc = -EEXIST; 835 rc = -EEXIST;
819 goto out; 836 goto out;
820 } 837 }
@@ -1626,7 +1643,7 @@ int xtExtend(tid_t tid, /* transaction id */
1626 jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen); 1643 jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
1627 1644
1628 /* there must exist extent to be extended */ 1645 /* there must exist extent to be extended */
1629 if ((rc = xtSearch(ip, xoff - 1, &cmp, &btstack, XT_INSERT))) 1646 if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT)))
1630 return rc; 1647 return rc;
1631 1648
1632 /* retrieve search result */ 1649 /* retrieve search result */
@@ -1794,7 +1811,7 @@ printf("xtTailgate: nxoff:0x%lx nxlen:0x%x nxaddr:0x%lx\n",
1794*/ 1811*/
1795 1812
1796 /* there must exist extent to be tailgated */ 1813 /* there must exist extent to be tailgated */
1797 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, XT_INSERT))) 1814 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, XT_INSERT)))
1798 return rc; 1815 return rc;
1799 1816
1800 /* retrieve search result */ 1817 /* retrieve search result */
@@ -1977,7 +1994,7 @@ int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
1977 nxlen = lengthXAD(nxad); 1994 nxlen = lengthXAD(nxad);
1978 nxaddr = addressXAD(nxad); 1995 nxaddr = addressXAD(nxad);
1979 1996
1980 if ((rc = xtSearch(ip, nxoff, &cmp, &btstack, XT_INSERT))) 1997 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
1981 return rc; 1998 return rc;
1982 1999
1983 /* retrieve search result */ 2000 /* retrieve search result */
@@ -2291,7 +2308,7 @@ int xtUpdate(tid_t tid, struct inode *ip, xad_t * nxad)
2291 if (nextindex == le16_to_cpu(p->header.maxentry)) { 2308 if (nextindex == le16_to_cpu(p->header.maxentry)) {
2292 XT_PUTPAGE(mp); 2309 XT_PUTPAGE(mp);
2293 2310
2294 if ((rc = xtSearch(ip, nxoff, &cmp, &btstack, XT_INSERT))) 2311 if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
2295 return rc; 2312 return rc;
2296 2313
2297 /* retrieve search result */ 2314 /* retrieve search result */
@@ -2438,6 +2455,7 @@ int xtAppend(tid_t tid, /* transaction id */
2438 int nsplit, nblocks, xlen; 2455 int nsplit, nblocks, xlen;
2439 struct pxdlist pxdlist; 2456 struct pxdlist pxdlist;
2440 pxd_t *pxd; 2457 pxd_t *pxd;
2458 s64 next;
2441 2459
2442 xaddr = *xaddrp; 2460 xaddr = *xaddrp;
2443 xlen = *xlenp; 2461 xlen = *xlenp;
@@ -2452,7 +2470,7 @@ int xtAppend(tid_t tid, /* transaction id */
2452 * n.b. xtSearch() may return index of maxentry of 2470 * n.b. xtSearch() may return index of maxentry of
2453 * the full page. 2471 * the full page.
2454 */ 2472 */
2455 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, XT_INSERT))) 2473 if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
2456 return rc; 2474 return rc;
2457 2475
2458 /* retrieve search result */ 2476 /* retrieve search result */
@@ -2462,6 +2480,9 @@ int xtAppend(tid_t tid, /* transaction id */
2462 rc = -EEXIST; 2480 rc = -EEXIST;
2463 goto out; 2481 goto out;
2464 } 2482 }
2483
2484 if (next)
2485 xlen = min(xlen, (int)(next - xoff));
2465//insert: 2486//insert:
2466 /* 2487 /*
2467 * insert entry for new extent 2488 * insert entry for new extent
@@ -2600,7 +2621,7 @@ int xtDelete(tid_t tid, struct inode *ip, s64 xoff, s32 xlen, int flag)
2600 /* 2621 /*
2601 * find the matching entry; xtSearch() pins the page 2622 * find the matching entry; xtSearch() pins the page
2602 */ 2623 */
2603 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, 0))) 2624 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
2604 return rc; 2625 return rc;
2605 2626
2606 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index); 2627 XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
@@ -2852,7 +2873,7 @@ xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad, /* old XAD */
2852 */ 2873 */
2853 if (xtype == DATAEXT) { 2874 if (xtype == DATAEXT) {
2854 /* search in leaf entry */ 2875 /* search in leaf entry */
2855 rc = xtSearch(ip, xoff, &cmp, &btstack, 0); 2876 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
2856 if (rc) 2877 if (rc)
2857 return rc; 2878 return rc;
2858 2879
@@ -2958,7 +2979,7 @@ xtRelocate(tid_t tid, struct inode * ip, xad_t * oxad, /* old XAD */
2958 } 2979 }
2959 2980
2960 /* get back parent page */ 2981 /* get back parent page */
2961 if ((rc = xtSearch(ip, xoff, &cmp, &btstack, 0))) 2982 if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
2962 return rc; 2983 return rc;
2963 2984
2964 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index); 2985 XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
@@ -3991,7 +4012,7 @@ s64 xtTruncate_pmap(tid_t tid, struct inode *ip, s64 committed_size)
3991 4012
3992 if (committed_size) { 4013 if (committed_size) {
3993 xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1; 4014 xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1;
3994 rc = xtSearch(ip, xoff, &cmp, &btstack, 0); 4015 rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
3995 if (rc) 4016 if (rc)
3996 return rc; 4017 return rc;
3997 4018