Line data Source code
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 :
44 0 : static void ext4_ext_binsearch_index(struct inode *ip, struct ext4_extent_path
45 : *path, daddr_t lbn)
46 : {
47 0 : struct ext4_extent_header *ehp = path->ep_header;
48 : struct ext4_extent_index *l, *r, *m;
49 :
50 0 : l = (struct ext4_extent_index *)(char *)(ehp + 1);
51 0 : r = (struct ext4_extent_index *)(char *)(ehp + 1) + ehp->eh_ecount - 1;
52 0 : while (l <= r) {
53 0 : m = l + (r - l) / 2;
54 0 : if (lbn < m->ei_blk)
55 0 : r = m - 1;
56 : else
57 0 : l = m + 1;
58 : }
59 :
60 0 : path->ep_index = l - 1;
61 0 : }
62 :
63 : static void
64 0 : ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn)
65 : {
66 0 : struct ext4_extent_header *ehp = path->ep_header;
67 : struct ext4_extent *l, *r, *m;
68 :
69 0 : if (ehp->eh_ecount == 0)
70 0 : return;
71 :
72 0 : l = (struct ext4_extent *)(char *)(ehp + 1);
73 0 : r = (struct ext4_extent *)(char *)(ehp + 1) + ehp->eh_ecount - 1;
74 0 : while (l <= r) {
75 0 : m = l + (r - l) / 2;
76 0 : if (lbn < m->e_blk)
77 0 : r = m - 1;
78 : else
79 0 : l = m + 1;
80 : }
81 :
82 0 : path->ep_ext = l - 1;
83 0 : }
84 :
85 : /*
86 : * Find a block in ext4 extent cache.
87 : */
88 : int
89 0 : 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 0 : ecp = &ip->i_e2fs_ext_cache;
95 :
96 : /* cache is invalid */
97 0 : if (ecp->ec_type == EXT4_EXT_CACHE_NO)
98 0 : return (ret);
99 :
100 0 : if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) {
101 0 : ep->e_blk = ecp->ec_blk;
102 0 : ep->e_start_lo = ecp->ec_start & 0xffffffff;
103 0 : ep->e_start_hi = ecp->ec_start >> 32 & 0xffff;
104 0 : ep->e_len = ecp->ec_len;
105 0 : ret = ecp->ec_type;
106 0 : }
107 0 : return (ret);
108 0 : }
109 :
110 : /*
111 : * Put an ext4_extent structure in ext4 cache.
112 : */
113 : void
114 0 : ext4_ext_put_cache(struct inode *ip, struct ext4_extent *ep, int type)
115 : {
116 : struct ext4_extent_cache *ecp;
117 :
118 0 : ecp = &ip->i_e2fs_ext_cache;
119 0 : ecp->ec_type = type;
120 0 : ecp->ec_blk = ep->e_blk;
121 0 : ecp->ec_len = ep->e_len;
122 0 : ecp->ec_start = (daddr_t)ep->e_start_hi << 32 | ep->e_start_lo;
123 0 : }
124 :
125 : /*
126 : * Find an extent.
127 : */
128 : struct ext4_extent_path *
129 0 : 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 0 : vp = ITOV(ip);
139 0 : ehp = (struct ext4_extent_header *)(char *)ip->i_e2fs_blocks;
140 :
141 0 : if (ehp->eh_magic != EXT4_EXT_MAGIC)
142 0 : return (NULL);
143 :
144 0 : path->ep_header = ehp;
145 :
146 0 : for (i = ehp->eh_depth; i != 0; --i) {
147 0 : ext4_ext_binsearch_index(ip, path, lbn);
148 0 : path->ep_depth = 0;
149 0 : path->ep_ext = NULL;
150 :
151 0 : nblk = (daddr_t)path->ep_index->ei_leaf_hi << 32 |
152 0 : path->ep_index->ei_leaf_lo;
153 0 : if (path->ep_bp != NULL) {
154 0 : brelse(path->ep_bp);
155 0 : path->ep_bp = NULL;
156 0 : }
157 0 : error = bread(ip->i_devvp, fsbtodb(fs, nblk), fs->e2fs_fsize,
158 : &path->ep_bp);
159 0 : if (error) {
160 0 : brelse(path->ep_bp);
161 0 : path->ep_bp = NULL;
162 0 : return (NULL);
163 : }
164 0 : ehp = (struct ext4_extent_header *)path->ep_bp->b_data;
165 0 : path->ep_header = ehp;
166 : }
167 :
168 0 : path->ep_depth = i;
169 0 : path->ep_ext = NULL;
170 0 : path->ep_index = NULL;
171 :
172 0 : ext4_ext_binsearch(ip, path, lbn);
173 0 : return (path);
174 0 : }
|
