]>
Commit | Line | Data |
---|---|---|
30fab293 | 1 | /* |
80e808fc | 2 | * bmap.c --- logical to physical block mapping |
30fab293 TT |
3 | * |
4 | * Copyright (C) 1997 Theodore Ts'o. | |
5 | * | |
6 | * %Begin-Header% | |
543547a5 TT |
7 | * This file may be redistributed under the terms of the GNU Library |
8 | * General Public License, version 2. | |
30fab293 TT |
9 | * %End-Header% |
10 | */ | |
11 | ||
d1154eb4 | 12 | #include "config.h" |
30fab293 TT |
13 | #include <stdio.h> |
14 | #include <string.h> | |
15 | #if HAVE_UNISTD_H | |
16 | #include <unistd.h> | |
17 | #endif | |
cc9bf5d2 | 18 | #include <errno.h> |
30fab293 | 19 | |
b5abe6fa | 20 | #include "ext2_fs.h" |
30fab293 TT |
21 | #include "ext2fs.h" |
22 | ||
78d8f90f | 23 | #if defined(__GNUC__) && !defined(NO_INLINE_FUNCS) |
30fab293 TT |
24 | #define _BMAP_INLINE_ __inline__ |
25 | #else | |
26 | #define _BMAP_INLINE_ | |
27 | #endif | |
28 | ||
31dbecd4 | 29 | extern errcode_t ext2fs_bmap(ext2_filsys fs, ext2_ino_t ino, |
efc6f628 | 30 | struct ext2_inode *inode, |
30fab293 TT |
31 | char *block_buf, int bmap_flags, |
32 | blk_t block, blk_t *phys_blk); | |
33 | ||
30fab293 TT |
34 | #define inode_bmap(inode, nr) ((inode)->i_block[(nr)]) |
35 | ||
efc6f628 TT |
36 | static _BMAP_INLINE_ errcode_t block_ind_bmap(ext2_filsys fs, int flags, |
37 | blk_t ind, char *block_buf, | |
30fab293 TT |
38 | int *blocks_alloc, |
39 | blk_t nr, blk_t *ret_blk) | |
40 | { | |
41 | errcode_t retval; | |
42 | blk_t b; | |
43 | ||
44 | if (!ind) { | |
1d667534 TT |
45 | if (flags & BMAP_SET) |
46 | return EXT2_ET_SET_BMAP_NO_IND; | |
30fab293 TT |
47 | *ret_blk = 0; |
48 | return 0; | |
49 | } | |
50 | retval = io_channel_read_blk(fs->io, ind, 1, block_buf); | |
51 | if (retval) | |
52 | return retval; | |
53 | ||
1d667534 TT |
54 | if (flags & BMAP_SET) { |
55 | b = *ret_blk; | |
126a291c TT |
56 | #ifdef WORDS_BIGENDIAN |
57 | b = ext2fs_swab32(b); | |
1d667534 TT |
58 | #endif |
59 | ((blk_t *) block_buf)[nr] = b; | |
60 | return io_channel_write_blk(fs->io, ind, 1, block_buf); | |
61 | } | |
62 | ||
30fab293 TT |
63 | b = ((blk_t *) block_buf)[nr]; |
64 | ||
126a291c TT |
65 | #ifdef WORDS_BIGENDIAN |
66 | b = ext2fs_swab32(b); | |
5df55d7f | 67 | #endif |
30fab293 TT |
68 | |
69 | if (!b && (flags & BMAP_ALLOC)) { | |
70 | b = nr ? ((blk_t *) block_buf)[nr-1] : 0; | |
71 | retval = ext2fs_alloc_block(fs, b, | |
72 | block_buf + fs->blocksize, &b); | |
73 | if (retval) | |
74 | return retval; | |
75 | ||
126a291c TT |
76 | #ifdef WORDS_BIGENDIAN |
77 | ((blk_t *) block_buf)[nr] = ext2fs_swab32(b); | |
78 | #else | |
79 | ((blk_t *) block_buf)[nr] = b; | |
5df55d7f | 80 | #endif |
30fab293 TT |
81 | |
82 | retval = io_channel_write_blk(fs->io, ind, 1, block_buf); | |
83 | if (retval) | |
84 | return retval; | |
85 | ||
86 | (*blocks_alloc)++; | |
87 | } | |
88 | ||
89 | *ret_blk = b; | |
90 | return 0; | |
91 | } | |
92 | ||
546a1ff1 | 93 | static _BMAP_INLINE_ errcode_t block_dind_bmap(ext2_filsys fs, int flags, |
efc6f628 | 94 | blk_t dind, char *block_buf, |
30fab293 TT |
95 | int *blocks_alloc, |
96 | blk_t nr, blk_t *ret_blk) | |
97 | { | |
1d6fd6d0 | 98 | blk_t b = 0; |
30fab293 | 99 | errcode_t retval; |
2eb374c9 | 100 | blk_t addr_per_block; |
efc6f628 | 101 | |
2eb374c9 | 102 | addr_per_block = (blk_t) fs->blocksize >> 2; |
30fab293 | 103 | |
efc6f628 | 104 | retval = block_ind_bmap(fs, flags & ~BMAP_SET, dind, block_buf, |
1d667534 | 105 | blocks_alloc, nr / addr_per_block, &b); |
30fab293 TT |
106 | if (retval) |
107 | return retval; | |
108 | retval = block_ind_bmap(fs, flags, b, block_buf, blocks_alloc, | |
109 | nr % addr_per_block, ret_blk); | |
110 | return retval; | |
111 | } | |
112 | ||
546a1ff1 | 113 | static _BMAP_INLINE_ errcode_t block_tind_bmap(ext2_filsys fs, int flags, |
efc6f628 | 114 | blk_t tind, char *block_buf, |
30fab293 TT |
115 | int *blocks_alloc, |
116 | blk_t nr, blk_t *ret_blk) | |
117 | { | |
1d6fd6d0 | 118 | blk_t b = 0; |
30fab293 | 119 | errcode_t retval; |
2eb374c9 | 120 | blk_t addr_per_block; |
efc6f628 | 121 | |
2eb374c9 | 122 | addr_per_block = (blk_t) fs->blocksize >> 2; |
30fab293 | 123 | |
efc6f628 | 124 | retval = block_dind_bmap(fs, flags & ~BMAP_SET, tind, block_buf, |
1d667534 | 125 | blocks_alloc, nr / addr_per_block, &b); |
30fab293 TT |
126 | if (retval) |
127 | return retval; | |
128 | retval = block_ind_bmap(fs, flags, b, block_buf, blocks_alloc, | |
129 | nr % addr_per_block, ret_blk); | |
130 | return retval; | |
131 | } | |
132 | ||
8e8a190f TT |
133 | static errcode_t extent_bmap(ext2_filsys fs, ext2_ino_t ino, |
134 | struct ext2_inode *inode, | |
135 | ext2_extent_handle_t handle, | |
136 | char *block_buf, int bmap_flags, blk64_t block, | |
137 | int *ret_flags, int *blocks_alloc, | |
138 | blk64_t *phys_blk); | |
139 | ||
140 | static errcode_t implied_cluster_alloc(ext2_filsys fs, ext2_ino_t ino, | |
141 | struct ext2_inode *inode, | |
142 | ext2_extent_handle_t handle, | |
2a091427 | 143 | blk64_t lblk, blk64_t *phys_blk) |
8e8a190f TT |
144 | { |
145 | blk64_t base_block, pblock = 0; | |
146 | int i; | |
147 | ||
148 | if (!EXT2_HAS_RO_COMPAT_FEATURE(fs->super, | |
149 | EXT4_FEATURE_RO_COMPAT_BIGALLOC)) | |
150 | return 0; | |
151 | ||
2a091427 DW |
152 | base_block = lblk & ~EXT2FS_CLUSTER_MASK(fs); |
153 | /* | |
154 | * Except for the logical block (lblk) that was passed in, search all | |
155 | * blocks in this logical cluster for a mapping to a physical cluster. | |
156 | * If any such map exists, calculate the physical block that maps to | |
157 | * the logical block and return that. | |
158 | * | |
159 | * The old code wouldn't even look if (block % cluster_ratio) == 0; | |
160 | * this is incorrect if we're allocating blocks in reverse order. | |
161 | */ | |
8e8a190f | 162 | for (i = 0; i < EXT2FS_CLUSTER_RATIO(fs); i++) { |
2a091427 DW |
163 | if (base_block + i == lblk) |
164 | continue; | |
8e8a190f TT |
165 | extent_bmap(fs, ino, inode, handle, 0, 0, |
166 | base_block + i, 0, 0, &pblock); | |
167 | if (pblock) | |
168 | break; | |
169 | } | |
170 | if (pblock == 0) | |
171 | return 0; | |
2a091427 | 172 | *phys_blk = pblock - i + (lblk - base_block); |
8e8a190f TT |
173 | return 0; |
174 | } | |
175 | ||
84397754 DW |
176 | /* Try to map a logical block to an already-allocated physical cluster. */ |
177 | errcode_t ext2fs_map_cluster_block(ext2_filsys fs, ext2_ino_t ino, | |
178 | struct ext2_inode *inode, blk64_t lblk, | |
179 | blk64_t *pblk) | |
180 | { | |
181 | ext2_extent_handle_t handle; | |
182 | errcode_t retval; | |
183 | ||
184 | /* Need bigalloc and extents to be enabled */ | |
185 | *pblk = 0; | |
186 | if (!EXT2_HAS_RO_COMPAT_FEATURE(fs->super, | |
187 | EXT4_FEATURE_RO_COMPAT_BIGALLOC) || | |
188 | !(inode->i_flags & EXT4_EXTENTS_FL)) | |
189 | return 0; | |
190 | ||
191 | retval = ext2fs_extent_open2(fs, ino, inode, &handle); | |
192 | if (retval) | |
193 | goto out; | |
194 | ||
195 | retval = implied_cluster_alloc(fs, ino, inode, handle, lblk, pblk); | |
196 | if (retval) | |
197 | goto out2; | |
198 | ||
199 | out2: | |
200 | ext2fs_extent_free(handle); | |
201 | out: | |
202 | return retval; | |
203 | } | |
204 | ||
551e2e46 TT |
205 | static errcode_t extent_bmap(ext2_filsys fs, ext2_ino_t ino, |
206 | struct ext2_inode *inode, | |
207 | ext2_extent_handle_t handle, | |
208 | char *block_buf, int bmap_flags, blk64_t block, | |
209 | int *ret_flags, int *blocks_alloc, | |
210 | blk64_t *phys_blk) | |
211 | { | |
212 | struct ext2fs_extent extent; | |
213 | unsigned int offset; | |
214 | errcode_t retval = 0; | |
8e8a190f TT |
215 | blk64_t blk64 = 0; |
216 | int alloc = 0; | |
551e2e46 TT |
217 | |
218 | if (bmap_flags & BMAP_SET) { | |
219 | retval = ext2fs_extent_set_bmap(handle, block, | |
220 | *phys_blk, 0); | |
221 | return retval; | |
222 | } | |
223 | retval = ext2fs_extent_goto(handle, block); | |
224 | if (retval) { | |
225 | /* If the extent is not found, return phys_blk = 0 */ | |
226 | if (retval == EXT2_ET_EXTENT_NOT_FOUND) | |
227 | goto got_block; | |
228 | return retval; | |
229 | } | |
230 | retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); | |
231 | if (retval) | |
232 | return retval; | |
233 | offset = block - extent.e_lblk; | |
234 | if (block >= extent.e_lblk && (offset <= extent.e_len)) { | |
235 | *phys_blk = extent.e_pblk + offset; | |
236 | if (ret_flags && extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) | |
237 | *ret_flags |= BMAP_RET_UNINIT; | |
238 | } | |
239 | got_block: | |
240 | if ((*phys_blk == 0) && (bmap_flags & BMAP_ALLOC)) { | |
8e8a190f TT |
241 | implied_cluster_alloc(fs, ino, inode, handle, block, &blk64); |
242 | if (blk64) | |
243 | goto set_extent; | |
551e2e46 TT |
244 | retval = extent_bmap(fs, ino, inode, handle, block_buf, |
245 | 0, block-1, 0, blocks_alloc, &blk64); | |
246 | if (retval) | |
247 | blk64 = 0; | |
248 | retval = ext2fs_alloc_block2(fs, blk64, block_buf, | |
249 | &blk64); | |
250 | if (retval) | |
251 | return retval; | |
8e8a190f TT |
252 | blk64 &= ~EXT2FS_CLUSTER_MASK(fs); |
253 | blk64 += EXT2FS_CLUSTER_MASK(fs) & block; | |
254 | alloc++; | |
255 | set_extent: | |
551e2e46 TT |
256 | retval = ext2fs_extent_set_bmap(handle, block, |
257 | blk64, 0); | |
258 | if (retval) | |
259 | return retval; | |
260 | /* Update inode after setting extent */ | |
261 | retval = ext2fs_read_inode(fs, ino, inode); | |
262 | if (retval) | |
263 | return retval; | |
8e8a190f | 264 | *blocks_alloc += alloc; |
551e2e46 TT |
265 | *phys_blk = blk64; |
266 | } | |
267 | return 0; | |
268 | } | |
269 | ||
1e745149 DW |
270 | int ext2fs_file_block_offset_too_big(ext2_filsys fs, |
271 | struct ext2_inode *inode, | |
272 | blk64_t offset) | |
273 | { | |
274 | blk64_t addr_per_block, max_map_block; | |
275 | ||
276 | /* Kernel seems to cut us off at 4294967294 blocks */ | |
277 | if (offset >= (1ULL << 32) - 1) | |
278 | return 1; | |
279 | ||
280 | if (inode->i_flags & EXT4_EXTENTS_FL) | |
281 | return 0; | |
282 | ||
283 | addr_per_block = fs->blocksize >> 2; | |
284 | max_map_block = addr_per_block; | |
285 | max_map_block += addr_per_block * addr_per_block; | |
286 | max_map_block += addr_per_block * addr_per_block * addr_per_block; | |
287 | max_map_block += 12; | |
288 | ||
289 | return offset >= max_map_block; | |
290 | } | |
551e2e46 | 291 | |
cc9bf5d2 TT |
292 | errcode_t ext2fs_bmap2(ext2_filsys fs, ext2_ino_t ino, struct ext2_inode *inode, |
293 | char *block_buf, int bmap_flags, blk64_t block, | |
294 | int *ret_flags, blk64_t *phys_blk) | |
30fab293 TT |
295 | { |
296 | struct ext2_inode inode_buf; | |
cc9bf5d2 | 297 | ext2_extent_handle_t handle = 0; |
2eb374c9 | 298 | blk_t addr_per_block; |
cc9bf5d2 | 299 | blk_t b, blk32; |
30fab293 TT |
300 | char *buf = 0; |
301 | errcode_t retval = 0; | |
1d667534 | 302 | int blocks_alloc = 0, inode_dirty = 0; |
30fab293 | 303 | |
1d667534 TT |
304 | if (!(bmap_flags & BMAP_SET)) |
305 | *phys_blk = 0; | |
30fab293 | 306 | |
cc9bf5d2 TT |
307 | if (ret_flags) |
308 | *ret_flags = 0; | |
309 | ||
30fab293 TT |
310 | /* Read inode structure if necessary */ |
311 | if (!inode) { | |
312 | retval = ext2fs_read_inode(fs, ino, &inode_buf); | |
b38cd283 | 313 | if (retval) |
30fab293 TT |
314 | return retval; |
315 | inode = &inode_buf; | |
316 | } | |
2eb374c9 | 317 | addr_per_block = (blk_t) fs->blocksize >> 2; |
30fab293 | 318 | |
1e745149 DW |
319 | if (ext2fs_file_block_offset_too_big(fs, inode, block)) |
320 | return EXT2_ET_FILE_TOO_BIG; | |
321 | ||
30fab293 | 322 | if (!block_buf) { |
ee01079a | 323 | retval = ext2fs_get_array(2, fs->blocksize, &buf); |
7b4e4534 TT |
324 | if (retval) |
325 | return retval; | |
30fab293 TT |
326 | block_buf = buf; |
327 | } | |
328 | ||
551e2e46 TT |
329 | if (inode->i_flags & EXT4_EXTENTS_FL) { |
330 | retval = ext2fs_extent_open2(fs, ino, inode, &handle); | |
331 | if (retval) | |
332 | goto done; | |
333 | retval = extent_bmap(fs, ino, inode, handle, block_buf, | |
334 | bmap_flags, block, ret_flags, | |
335 | &blocks_alloc, phys_blk); | |
336 | goto done; | |
337 | } | |
338 | ||
30fab293 | 339 | if (block < EXT2_NDIR_BLOCKS) { |
1d667534 TT |
340 | if (bmap_flags & BMAP_SET) { |
341 | b = *phys_blk; | |
1d667534 TT |
342 | inode_bmap(inode, block) = b; |
343 | inode_dirty++; | |
344 | goto done; | |
345 | } | |
346 | ||
30fab293 TT |
347 | *phys_blk = inode_bmap(inode, block); |
348 | b = block ? inode_bmap(inode, block-1) : 0; | |
efc6f628 | 349 | |
30fab293 TT |
350 | if ((*phys_blk == 0) && (bmap_flags & BMAP_ALLOC)) { |
351 | retval = ext2fs_alloc_block(fs, b, block_buf, &b); | |
352 | if (retval) | |
353 | goto done; | |
354 | inode_bmap(inode, block) = b; | |
355 | blocks_alloc++; | |
356 | *phys_blk = b; | |
357 | } | |
358 | goto done; | |
359 | } | |
efc6f628 | 360 | |
30fab293 TT |
361 | /* Indirect block */ |
362 | block -= EXT2_NDIR_BLOCKS; | |
cc9bf5d2 | 363 | blk32 = *phys_blk; |
30fab293 TT |
364 | if (block < addr_per_block) { |
365 | b = inode_bmap(inode, EXT2_IND_BLOCK); | |
366 | if (!b) { | |
1d667534 TT |
367 | if (!(bmap_flags & BMAP_ALLOC)) { |
368 | if (bmap_flags & BMAP_SET) | |
369 | retval = EXT2_ET_SET_BMAP_NO_IND; | |
370 | goto done; | |
371 | } | |
30fab293 TT |
372 | |
373 | b = inode_bmap(inode, EXT2_IND_BLOCK-1); | |
374 | retval = ext2fs_alloc_block(fs, b, block_buf, &b); | |
375 | if (retval) | |
376 | goto done; | |
377 | inode_bmap(inode, EXT2_IND_BLOCK) = b; | |
378 | blocks_alloc++; | |
379 | } | |
efc6f628 | 380 | retval = block_ind_bmap(fs, bmap_flags, b, block_buf, |
cc9bf5d2 TT |
381 | &blocks_alloc, block, &blk32); |
382 | if (retval == 0) | |
383 | *phys_blk = blk32; | |
30fab293 TT |
384 | goto done; |
385 | } | |
efc6f628 | 386 | |
30fab293 TT |
387 | /* Doubly indirect block */ |
388 | block -= addr_per_block; | |
389 | if (block < addr_per_block * addr_per_block) { | |
390 | b = inode_bmap(inode, EXT2_DIND_BLOCK); | |
391 | if (!b) { | |
1d667534 TT |
392 | if (!(bmap_flags & BMAP_ALLOC)) { |
393 | if (bmap_flags & BMAP_SET) | |
394 | retval = EXT2_ET_SET_BMAP_NO_IND; | |
395 | goto done; | |
396 | } | |
30fab293 TT |
397 | |
398 | b = inode_bmap(inode, EXT2_IND_BLOCK); | |
399 | retval = ext2fs_alloc_block(fs, b, block_buf, &b); | |
400 | if (retval) | |
401 | goto done; | |
402 | inode_bmap(inode, EXT2_DIND_BLOCK) = b; | |
403 | blocks_alloc++; | |
404 | } | |
efc6f628 | 405 | retval = block_dind_bmap(fs, bmap_flags, b, block_buf, |
cc9bf5d2 TT |
406 | &blocks_alloc, block, &blk32); |
407 | if (retval == 0) | |
408 | *phys_blk = blk32; | |
30fab293 TT |
409 | goto done; |
410 | } | |
411 | ||
412 | /* Triply indirect block */ | |
413 | block -= addr_per_block * addr_per_block; | |
414 | b = inode_bmap(inode, EXT2_TIND_BLOCK); | |
415 | if (!b) { | |
1d667534 TT |
416 | if (!(bmap_flags & BMAP_ALLOC)) { |
417 | if (bmap_flags & BMAP_SET) | |
418 | retval = EXT2_ET_SET_BMAP_NO_IND; | |
30fab293 | 419 | goto done; |
1d667534 | 420 | } |
30fab293 TT |
421 | |
422 | b = inode_bmap(inode, EXT2_DIND_BLOCK); | |
423 | retval = ext2fs_alloc_block(fs, b, block_buf, &b); | |
424 | if (retval) | |
425 | goto done; | |
426 | inode_bmap(inode, EXT2_TIND_BLOCK) = b; | |
427 | blocks_alloc++; | |
428 | } | |
efc6f628 | 429 | retval = block_tind_bmap(fs, bmap_flags, b, block_buf, |
cc9bf5d2 TT |
430 | &blocks_alloc, block, &blk32); |
431 | if (retval == 0) | |
432 | *phys_blk = blk32; | |
30fab293 TT |
433 | done: |
434 | if (buf) | |
c4e3d3f3 | 435 | ext2fs_free_mem(&buf); |
cc9bf5d2 TT |
436 | if (handle) |
437 | ext2fs_extent_free(handle); | |
1d667534 | 438 | if ((retval == 0) && (blocks_alloc || inode_dirty)) { |
1ca1059f | 439 | ext2fs_iblk_add_blocks(fs, inode, blocks_alloc); |
30fab293 TT |
440 | retval = ext2fs_write_inode(fs, ino, inode); |
441 | } | |
442 | return retval; | |
443 | } | |
444 | ||
cc9bf5d2 TT |
445 | errcode_t ext2fs_bmap(ext2_filsys fs, ext2_ino_t ino, struct ext2_inode *inode, |
446 | char *block_buf, int bmap_flags, blk_t block, | |
447 | blk_t *phys_blk) | |
448 | { | |
449 | errcode_t ret; | |
9c9e1d5f | 450 | blk64_t ret_blk = *phys_blk; |
cc9bf5d2 TT |
451 | |
452 | ret = ext2fs_bmap2(fs, ino, inode, block_buf, bmap_flags, block, | |
453 | 0, &ret_blk); | |
454 | if (ret) | |
455 | return ret; | |
456 | if (ret_blk >= ((long long) 1 << 32)) | |
457 | return EOVERFLOW; | |
458 | *phys_blk = ret_blk; | |
459 | return 0; | |
460 | } |