1 /* $NetBSD: ext2fs_extents.c,v 1.3 2016/08/13 07:40:10 christos Exp $ */
2
3 /*-
4 * Copyright (c) 2010 Zheng Liu <lz@freebsd.org>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 *
28 * $FreeBSD: head/sys/fs/ext2fs/ext2_extents.c 295523 2016-02-11 15:27:14Z pfg $
29 */
30
31 #include <sys/cdefs.h>
32 __KERNEL_RCSID(0, "$NetBSD: ext2fs_extents.c,v 1.3 2016/08/13 07:40:10 christos Exp $");
33
34 #include <sys/param.h>
35 #include <sys/systm.h>
36 #include <sys/resourcevar.h>
37 #include <sys/kernel.h>
38 #include <sys/file.h>
39 #include <sys/stat.h>
40 #include <sys/buf.h>
41 #include <sys/proc.h>
42 #include <sys/mount.h>
43 #include <sys/vnode.h>
44 #include <sys/signalvar.h>
45 #include <sys/kauth.h>
46
47 #include <ufs/ufs/inode.h>
48 #include <ufs/ufs/ufsmount.h>
49 #include <ufs/ufs/ufs_extern.h>
50
51
52 #include <ufs/ext2fs/ext2fs.h>
53 #include <ufs/ext2fs/ext2fs_extents.h>
54 #include <ufs/ext2fs/ext2fs_extern.h>
55
56
57
58 static bool
ext4_ext_binsearch_index(struct inode * ip,struct ext4_extent_path * path,daddr_t lbn,daddr_t * first_lbn,daddr_t * last_lbn)59 ext4_ext_binsearch_index(struct inode *ip, struct ext4_extent_path *path,
60 daddr_t lbn, daddr_t *first_lbn, daddr_t *last_lbn)
61 {
62 struct ext4_extent_header *ehp = path->ep_header;
63 struct ext4_extent_index *first, *last, *l, *r, *m;
64
65 first = (struct ext4_extent_index *)(char *)(ehp + 1);
66 last = first + ehp->eh_ecount - 1;
67 l = first;
68 r = last;
69 while (l <= r) {
70 m = l + (r - l) / 2;
71 if (lbn < m->ei_blk)
72 r = m - 1;
73 else
74 l = m + 1;
75 }
76
77 if (l == first) {
78 path->ep_sparse_ext.e_blk = *first_lbn;
79 path->ep_sparse_ext.e_len = first->ei_blk - *first_lbn;
80 path->ep_sparse_ext.e_start_hi = 0;
81 path->ep_sparse_ext.e_start_lo = 0;
82 path->ep_is_sparse = true;
83 return true;
84 }
85 path->ep_index = l - 1;
86 *first_lbn = path->ep_index->ei_blk;
87 if (path->ep_index < last)
88 *last_lbn = l->ei_blk - 1;
89 return false;
90 }
91
92 static void
ext4_ext_binsearch(struct inode * ip,struct ext4_extent_path * path,daddr_t lbn,daddr_t first_lbn,daddr_t last_lbn)93 ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn,
94 daddr_t first_lbn, daddr_t last_lbn)
95 {
96 struct ext4_extent_header *ehp = path->ep_header;
97 struct ext4_extent *first, *l, *r, *m;
98
99 if (ehp->eh_ecount == 0)
100 return;
101
102 first = (struct ext4_extent *)(char *)(ehp + 1);
103 l = first;
104 r = first + ehp->eh_ecount - 1;
105 while (l <= r) {
106 m = l + (r - l) / 2;
107 if (lbn < m->e_blk)
108 r = m - 1;
109 else
110 l = m + 1;
111 }
112
113 if (l == first) {
114 path->ep_sparse_ext.e_blk = first_lbn;
115 path->ep_sparse_ext.e_len = first->e_blk - first_lbn;
116 path->ep_sparse_ext.e_start_hi = 0;
117 path->ep_sparse_ext.e_start_lo = 0;
118 path->ep_is_sparse = true;
119 return;
120 }
121 path->ep_ext = l - 1;
122 if (path->ep_ext->e_blk + path->ep_ext->e_len <= lbn) {
123 path->ep_sparse_ext.e_blk = path->ep_ext->e_blk +
124 path->ep_ext->e_len;
125 if (l <= (first + ehp->eh_ecount - 1))
126 path->ep_sparse_ext.e_len = l->e_blk -
127 path->ep_sparse_ext.e_blk;
128 else
129 path->ep_sparse_ext.e_len = last_lbn -
130 path->ep_sparse_ext.e_blk + 1;
131 path->ep_sparse_ext.e_start_hi = 0;
132 path->ep_sparse_ext.e_start_lo = 0;
133 path->ep_is_sparse = true;
134 }
135 }
136
137 /*
138 * Find a block in ext4 extent cache.
139 */
140 int
ext4_ext_in_cache(struct inode * ip,daddr_t lbn,struct ext4_extent * ep)141 ext4_ext_in_cache(struct inode *ip, daddr_t lbn, struct ext4_extent *ep)
142 {
143 struct ext4_extent_cache *ecp;
144 int ret = EXT4_EXT_CACHE_NO;
145
146 ecp = &ip->inode_ext.e2fs.i_ext_cache;
147
148 /* cache is invalid */
149 if (ecp->ec_type == EXT4_EXT_CACHE_NO)
150 return ret;
151
152 if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) {
153 ep->e_blk = ecp->ec_blk;
154 ep->e_start_lo = ecp->ec_start & 0xffffffff;
155 ep->e_start_hi = ecp->ec_start >> 32 & 0xffff;
156 ep->e_len = ecp->ec_len;
157 ret = ecp->ec_type;
158 }
159 return ret;
160 }
161
162 /*
163 * Put an ext4_extent structure in ext4 cache.
164 */
165 void
ext4_ext_put_cache(struct inode * ip,struct ext4_extent * ep,int type)166 ext4_ext_put_cache(struct inode *ip, struct ext4_extent *ep, int type)
167 {
168 struct ext4_extent_cache *ecp;
169
170 ecp = &ip->inode_ext.e2fs.i_ext_cache;
171 ecp->ec_type = type;
172 ecp->ec_blk = ep->e_blk;
173 ecp->ec_len = ep->e_len;
174 ecp->ec_start = (daddr_t)ep->e_start_hi << 32 | ep->e_start_lo;
175 }
176
177 /*
178 * Find an extent.
179 */
180 struct ext4_extent_path *
ext4_ext_find_extent(struct m_ext2fs * fs,struct inode * ip,daddr_t lbn,struct ext4_extent_path * path)181 ext4_ext_find_extent(struct m_ext2fs *fs, struct inode *ip,
182 daddr_t lbn, struct ext4_extent_path *path)
183 {
184 struct ext4_extent_header *ehp;
185 uint16_t i;
186 int error, size;
187 daddr_t nblk;
188
189 ehp = (struct ext4_extent_header *)ip->i_din.e2fs_din->e2di_blocks;
190
191 if (ehp->eh_magic != EXT4_EXT_MAGIC)
192 return NULL;
193
194 path->ep_header = ehp;
195
196 daddr_t first_lbn = 0;
197 daddr_t last_lbn = lblkno(ip->i_e2fs, ip->i_size);
198
199 for (i = ehp->eh_depth; i != 0; --i) {
200 path->ep_depth = i;
201 path->ep_ext = NULL;
202 if (ext4_ext_binsearch_index(ip, path, lbn, &first_lbn,
203 &last_lbn)) {
204 return path;
205 }
206
207 nblk = (daddr_t)path->ep_index->ei_leaf_hi << 32 |
208 path->ep_index->ei_leaf_lo;
209 size = blksize(fs, ip, nblk);
210 if (path->ep_bp != NULL) {
211 brelse(path->ep_bp, 0);
212 path->ep_bp = NULL;
213 }
214 error = bread(ip->i_devvp, fsbtodb(fs, nblk), size, 0,
215 &path->ep_bp);
216 if (error) {
217 brelse(path->ep_bp, 0);
218 path->ep_bp = NULL;
219 return NULL;
220 }
221 ehp = (struct ext4_extent_header *)path->ep_bp->b_data;
222 path->ep_header = ehp;
223 }
224
225 path->ep_depth = i;
226 path->ep_ext = NULL;
227 path->ep_index = NULL;
228 path->ep_is_sparse = false;
229
230 ext4_ext_binsearch(ip, path, lbn, first_lbn, last_lbn);
231 return path;
232 }
233