1 /*-
2 * Copyright (c) 2010 Zheng Liu <lz@freebsd.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * $FreeBSD: head/sys/fs/ext2fs/ext2_extents.c 254260 2013-08-12 21:34:48Z pfg $
27 */
28
29 #include <sys/param.h>
30 #include <sys/systm.h>
31 #include <sys/kernel.h>
32 #include <sys/malloc.h>
33 #include <sys/vnode.h>
34 #include <sys/mount.h>
35 #include <sys/buf.h>
36
37 #include <ufs/ufs/quota.h>
38 #include <ufs/ufs/ufsmount.h>
39 #include <ufs/ufs/inode.h>
40 #include <ufs/ext2fs/ext2fs.h>
41 #include <ufs/ext2fs/ext2fs_extents.h>
42 #include <ufs/ext2fs/ext2fs_extern.h>
43
ext4_ext_binsearch_index(struct inode * ip,struct ext4_extent_path * path,daddr_t lbn)44 static void ext4_ext_binsearch_index(struct inode *ip, struct ext4_extent_path
45 *path, daddr_t lbn)
46 {
47 struct ext4_extent_header *ehp = path->ep_header;
48 struct ext4_extent_index *l, *r, *m;
49
50 l = (struct ext4_extent_index *)(char *)(ehp + 1);
51 r = (struct ext4_extent_index *)(char *)(ehp + 1) + ehp->eh_ecount - 1;
52 while (l <= r) {
53 m = l + (r - l) / 2;
54 if (lbn < m->ei_blk)
55 r = m - 1;
56 else
57 l = m + 1;
58 }
59
60 path->ep_index = l - 1;
61 }
62
63 static void
ext4_ext_binsearch(struct inode * ip,struct ext4_extent_path * path,daddr_t lbn)64 ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn)
65 {
66 struct ext4_extent_header *ehp = path->ep_header;
67 struct ext4_extent *l, *r, *m;
68
69 if (ehp->eh_ecount == 0)
70 return;
71
72 l = (struct ext4_extent *)(char *)(ehp + 1);
73 r = (struct ext4_extent *)(char *)(ehp + 1) + ehp->eh_ecount - 1;
74 while (l <= r) {
75 m = l + (r - l) / 2;
76 if (lbn < m->e_blk)
77 r = m - 1;
78 else
79 l = m + 1;
80 }
81
82 path->ep_ext = l - 1;
83 }
84
85 /*
86 * Find a block in ext4 extent cache.
87 */
88 int
ext4_ext_in_cache(struct inode * ip,daddr_t lbn,struct ext4_extent * ep)89 ext4_ext_in_cache(struct inode *ip, daddr_t lbn, struct ext4_extent *ep)
90 {
91 struct ext4_extent_cache *ecp;
92 int ret = EXT4_EXT_CACHE_NO;
93
94 ecp = &ip->i_e2fs_ext_cache;
95
96 /* cache is invalid */
97 if (ecp->ec_type == EXT4_EXT_CACHE_NO)
98 return (ret);
99
100 if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) {
101 ep->e_blk = ecp->ec_blk;
102 ep->e_start_lo = ecp->ec_start & 0xffffffff;
103 ep->e_start_hi = ecp->ec_start >> 32 & 0xffff;
104 ep->e_len = ecp->ec_len;
105 ret = ecp->ec_type;
106 }
107 return (ret);
108 }
109
110 /*
111 * Put an ext4_extent structure in ext4 cache.
112 */
113 void
ext4_ext_put_cache(struct inode * ip,struct ext4_extent * ep,int type)114 ext4_ext_put_cache(struct inode *ip, struct ext4_extent *ep, int type)
115 {
116 struct ext4_extent_cache *ecp;
117
118 ecp = &ip->i_e2fs_ext_cache;
119 ecp->ec_type = type;
120 ecp->ec_blk = ep->e_blk;
121 ecp->ec_len = ep->e_len;
122 ecp->ec_start = (daddr_t)ep->e_start_hi << 32 | ep->e_start_lo;
123 }
124
125 /*
126 * Find an extent.
127 */
128 struct ext4_extent_path *
ext4_ext_find_extent(struct m_ext2fs * fs,struct inode * ip,daddr_t lbn,struct ext4_extent_path * path)129 ext4_ext_find_extent(struct m_ext2fs *fs, struct inode *ip,
130 daddr_t lbn, struct ext4_extent_path *path)
131 {
132 struct vnode *vp;
133 struct ext4_extent_header *ehp;
134 uint16_t i;
135 int error;
136 daddr_t nblk;
137
138 vp = ITOV(ip);
139 ehp = (struct ext4_extent_header *)(char *)ip->i_e2fs_blocks;
140
141 if (ehp->eh_magic != EXT4_EXT_MAGIC)
142 return (NULL);
143
144 path->ep_header = ehp;
145
146 for (i = ehp->eh_depth; i != 0; --i) {
147 ext4_ext_binsearch_index(ip, path, lbn);
148 path->ep_depth = 0;
149 path->ep_ext = NULL;
150
151 nblk = (daddr_t)path->ep_index->ei_leaf_hi << 32 |
152 path->ep_index->ei_leaf_lo;
153 if (path->ep_bp != NULL) {
154 brelse(path->ep_bp);
155 path->ep_bp = NULL;
156 }
157 error = bread(ip->i_devvp, fsbtodb(fs, nblk), fs->e2fs_fsize,
158 &path->ep_bp);
159 if (error) {
160 brelse(path->ep_bp);
161 path->ep_bp = NULL;
162 return (NULL);
163 }
164 ehp = (struct ext4_extent_header *)path->ep_bp->b_data;
165 path->ep_header = ehp;
166 }
167
168 path->ep_depth = i;
169 path->ep_ext = NULL;
170 path->ep_index = NULL;
171
172 ext4_ext_binsearch(ip, path, lbn);
173 return (path);
174 }
175