Lines 43-56
Link Here
|
43 |
#include <fs/ext2fs/ext2_extents.h> |
43 |
#include <fs/ext2fs/ext2_extents.h> |
44 |
#include <fs/ext2fs/ext2_extern.h> |
44 |
#include <fs/ext2fs/ext2_extern.h> |
45 |
|
45 |
|
46 |
static void ext4_ext_binsearch_index(struct inode *ip, struct ext4_extent_path |
46 |
static int ext4_ext_binsearch_index(struct inode *ip, struct ext4_extent_path |
47 |
*path, daddr_t lbn) |
47 |
*path, daddr_t lbn, daddr_t *first_lbn, daddr_t *last_lbn) |
48 |
{ |
48 |
{ |
49 |
struct ext4_extent_header *ehp = path->ep_header; |
49 |
struct ext4_extent_header *ehp = path->ep_header; |
50 |
struct ext4_extent_index *l, *r, *m; |
50 |
struct ext4_extent_index *first, *last, *l, *r, *m; |
51 |
|
51 |
|
52 |
l = (struct ext4_extent_index *)(char *)(ehp + 1); |
52 |
first = (struct ext4_extent_index *)(char *)(ehp + 1); |
53 |
r = (struct ext4_extent_index *)(char *)(ehp + 1) + ehp->eh_ecount - 1; |
53 |
last = first + ehp->eh_ecount - 1; |
|
|
54 |
l = first; |
55 |
r = last; |
54 |
while (l <= r) { |
56 |
while (l <= r) { |
55 |
m = l + (r - l) / 2; |
57 |
m = l + (r - l) / 2; |
56 |
if (lbn < m->ei_blk) |
58 |
if (lbn < m->ei_blk) |
Lines 59-69
static void ext4_ext_binsearch_index(struct inode *ip, struct ext4_extent_path
Link Here
|
59 |
l = m + 1; |
61 |
l = m + 1; |
60 |
} |
62 |
} |
61 |
|
63 |
|
|
|
64 |
if (l == first) { |
65 |
path->ep_sparse_ext.e_blk = *first_lbn; |
66 |
path->ep_sparse_ext.e_len = first->ei_blk - *first_lbn; |
67 |
path->ep_sparse_ext.e_start_hi = 0; |
68 |
path->ep_sparse_ext.e_start_lo = 0; |
69 |
path->ep_is_sparse = 1; |
70 |
return 1; |
71 |
} |
62 |
path->ep_index = l - 1; |
72 |
path->ep_index = l - 1; |
|
|
73 |
*first_lbn = path->ep_index->ei_blk; |
74 |
if (path->ep_index < last) |
75 |
*last_lbn = l->ei_blk - 1; |
76 |
return 0; |
63 |
} |
77 |
} |
64 |
|
78 |
|
65 |
static void |
79 |
static void |
66 |
ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn) |
80 |
ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn, |
|
|
81 |
daddr_t first_lbn, daddr_t last_lbn) |
67 |
{ |
82 |
{ |
68 |
struct ext4_extent_header *ehp = path->ep_header; |
83 |
struct ext4_extent_header *ehp = path->ep_header; |
69 |
struct ext4_extent *first, *l, *r, *m; |
84 |
struct ext4_extent *first, *l, *r, *m; |
Lines 83-90
ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn)
Link Here
|
83 |
} |
98 |
} |
84 |
|
99 |
|
85 |
if (l == first) { |
100 |
if (l == first) { |
86 |
path->ep_sparse_ext.e_blk = lbn; |
101 |
path->ep_sparse_ext.e_blk = first_lbn; |
87 |
path->ep_sparse_ext.e_len = first->e_blk - lbn; |
102 |
path->ep_sparse_ext.e_len = first->e_blk - first_lbn; |
88 |
path->ep_sparse_ext.e_start_hi = 0; |
103 |
path->ep_sparse_ext.e_start_hi = 0; |
89 |
path->ep_sparse_ext.e_start_lo = 0; |
104 |
path->ep_sparse_ext.e_start_lo = 0; |
90 |
path->ep_is_sparse = 1; |
105 |
path->ep_is_sparse = 1; |
Lines 92-102
ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn)
Link Here
|
92 |
} |
107 |
} |
93 |
path->ep_ext = l - 1; |
108 |
path->ep_ext = l - 1; |
94 |
if (path->ep_ext->e_blk + path->ep_ext->e_len <= lbn) { |
109 |
if (path->ep_ext->e_blk + path->ep_ext->e_len <= lbn) { |
95 |
path->ep_sparse_ext.e_blk = lbn; |
110 |
path->ep_sparse_ext.e_blk = path->ep_ext->e_blk + path->ep_ext->e_len; |
96 |
if (l <= (first + ehp->eh_ecount - 1)) |
111 |
if (l <= (first + ehp->eh_ecount - 1)) |
97 |
path->ep_sparse_ext.e_len = l->e_blk - lbn; |
112 |
path->ep_sparse_ext.e_len = l->e_blk - path->ep_sparse_ext.e_blk; |
98 |
else // XXX: where does it end? |
113 |
else |
99 |
path->ep_sparse_ext.e_len = 1; |
114 |
path->ep_sparse_ext.e_len = last_lbn - path->ep_sparse_ext.e_blk + 1; |
100 |
path->ep_sparse_ext.e_start_hi = 0; |
115 |
path->ep_sparse_ext.e_start_hi = 0; |
101 |
path->ep_sparse_ext.e_start_lo = 0; |
116 |
path->ep_sparse_ext.e_start_lo = 0; |
102 |
path->ep_is_sparse = 1; |
117 |
path->ep_is_sparse = 1; |
Lines 162-171
ext4_ext_find_extent(struct m_ext2fs *fs, struct inode *ip,
Link Here
|
162 |
|
177 |
|
163 |
path->ep_header = ehp; |
178 |
path->ep_header = ehp; |
164 |
|
179 |
|
|
|
180 |
daddr_t first_lbn = 0; |
181 |
daddr_t last_lbn = lblkno(ip->i_e2fs, ip->i_size); |
182 |
|
165 |
for (i = ehp->eh_depth; i != 0; --i) { |
183 |
for (i = ehp->eh_depth; i != 0; --i) { |
166 |
ext4_ext_binsearch_index(ip, path, lbn); |
184 |
path->ep_depth = i; |
167 |
path->ep_depth = 0; |
|
|
168 |
path->ep_ext = NULL; |
185 |
path->ep_ext = NULL; |
|
|
186 |
if (ext4_ext_binsearch_index(ip, path, lbn, &first_lbn, &last_lbn)) { |
187 |
return (path); |
188 |
} |
169 |
|
189 |
|
170 |
nblk = (daddr_t)path->ep_index->ei_leaf_hi << 32 | |
190 |
nblk = (daddr_t)path->ep_index->ei_leaf_hi << 32 | |
171 |
path->ep_index->ei_leaf_lo; |
191 |
path->ep_index->ei_leaf_lo; |
Lines 190-195
ext4_ext_find_extent(struct m_ext2fs *fs, struct inode *ip,
Link Here
|
190 |
path->ep_index = NULL; |
210 |
path->ep_index = NULL; |
191 |
path->ep_is_sparse = 0; |
211 |
path->ep_is_sparse = 0; |
192 |
|
212 |
|
193 |
ext4_ext_binsearch(ip, path, lbn); |
213 |
ext4_ext_binsearch(ip, path, lbn, first_lbn, last_lbn); |
194 |
return (path); |
214 |
return (path); |
195 |
} |
215 |
} |
196 |
- |
|
|