1 /*
2 * extent.c --- routines to implement extents support
3 *
4 * Copyright (C) 2007 Theodore Ts'o.
5 *
6 * %Begin-Header%
7 * This file may be redistributed under the terms of the GNU Library
8 * General Public License, version 2.
9 * %End-Header%
10 */
11
12 #include "config.h"
13 #include <stdio.h>
14 #include <string.h>
15 #if HAVE_UNISTD_H
16 #include <unistd.h>
17 #endif
18 #if HAVE_ERRNO_H
19 #include <errno.h>
20 #endif
21 #if HAVE_SYS_STAT_H
22 #include <sys/stat.h>
23 #endif
24 #if HAVE_SYS_TYPES_H
25 #include <sys/types.h>
26 #endif
27
28 #include "ext2_fs.h"
29 #include "ext2fsP.h"
30 #include "e2image.h"
31
32 #undef DEBUG
33
34 /*
35 * Definitions to be dropped in lib/ext2fs/ext2fs.h
36 */
37
38 /*
39 * Private definitions
40 */
41
42 struct extent_path {
43 char *buf;
44 int entries;
45 int max_entries;
46 int left;
47 int visit_num;
48 int flags;
49 blk64_t end_blk;
50 blk64_t blk;
51 void *curr;
52 };
53
54
55 struct ext2_extent_handle {
56 errcode_t magic;
57 ext2_filsys fs;
58 ext2_ino_t ino;
59 struct ext2_inode *inode;
60 struct ext2_inode inodebuf;
61 int type;
62 int level;
63 int max_depth;
64 int max_paths;
65 struct extent_path *path;
66 };
67
68 struct ext2_extent_path {
69 errcode_t magic;
70 int leaf_height;
71 blk64_t lblk;
72 };
73
74 /*
75 * Useful Debugging stuff
76 */
77
78 #ifdef DEBUG
dbg_show_header(struct ext3_extent_header * eh)79 static void dbg_show_header(struct ext3_extent_header *eh)
80 {
81 printf("header: magic=%x entries=%u max=%u depth=%u generation=%u\n",
82 ext2fs_le16_to_cpu(eh->eh_magic),
83 ext2fs_le16_to_cpu(eh->eh_entries),
84 ext2fs_le16_to_cpu(eh->eh_max),
85 ext2fs_le16_to_cpu(eh->eh_depth),
86 ext2fs_le32_to_cpu(eh->eh_generation));
87 }
88
dbg_show_index(struct ext3_extent_idx * ix)89 static void dbg_show_index(struct ext3_extent_idx *ix)
90 {
91 printf("index: block=%u leaf=%u leaf_hi=%u unused=%u\n",
92 ext2fs_le32_to_cpu(ix->ei_block),
93 ext2fs_le32_to_cpu(ix->ei_leaf),
94 ext2fs_le16_to_cpu(ix->ei_leaf_hi),
95 ext2fs_le16_to_cpu(ix->ei_unused));
96 }
97
dbg_show_extent(struct ext3_extent * ex)98 static void dbg_show_extent(struct ext3_extent *ex)
99 {
100 printf("extent: block=%u-%u len=%u start=%u start_hi=%u\n",
101 ext2fs_le32_to_cpu(ex->ee_block),
102 ext2fs_le32_to_cpu(ex->ee_block) +
103 ext2fs_le16_to_cpu(ex->ee_len) - 1,
104 ext2fs_le16_to_cpu(ex->ee_len),
105 ext2fs_le32_to_cpu(ex->ee_start),
106 ext2fs_le16_to_cpu(ex->ee_start_hi));
107 }
108
dbg_print_extent(char * desc,struct ext2fs_extent * extent)109 static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)
110 {
111 if (desc)
112 printf("%s: ", desc);
113 printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ",
114 extent->e_lblk, extent->e_lblk + extent->e_len - 1,
115 extent->e_len, extent->e_pblk);
116 if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF)
117 fputs("LEAF ", stdout);
118 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT)
119 fputs("UNINIT ", stdout);
120 if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT)
121 fputs("2ND_VISIT ", stdout);
122 if (!extent->e_flags)
123 fputs("(none)", stdout);
124 fputc('\n', stdout);
125
126 }
127
dump_path(const char * tag,struct ext2_extent_handle * handle,struct extent_path * path)128 static void dump_path(const char *tag, struct ext2_extent_handle *handle,
129 struct extent_path *path)
130 {
131 struct extent_path *ppp = path;
132 printf("%s: level=%d\n", tag, handle->level);
133
134 do {
135 printf("%s: path=%ld buf=%p entries=%d max_entries=%d left=%d "
136 "visit_num=%d flags=0x%x end_blk=%llu curr=%p(%ld)\n",
137 tag, (ppp - handle->path), ppp->buf, ppp->entries,
138 ppp->max_entries, ppp->left, ppp->visit_num, ppp->flags,
139 ppp->end_blk, ppp->curr, ppp->curr - (void *)ppp->buf);
140 printf(" ");
141 dbg_show_header((struct ext3_extent_header *)ppp->buf);
142 if (ppp->curr) {
143 printf(" ");
144 dbg_show_index(ppp->curr);
145 printf(" ");
146 dbg_show_extent(ppp->curr);
147 }
148 ppp--;
149 } while (ppp >= handle->path);
150 fflush(stdout);
151
152 return;
153 }
154
155 #else
156 #define dbg_show_header(eh) do { } while (0)
157 #define dbg_show_index(ix) do { } while (0)
158 #define dbg_show_extent(ex) do { } while (0)
159 #define dbg_print_extent(desc, ex) do { } while (0)
160 #define dump_path(tag, handle, path) do { } while (0)
161 #endif
162
163 /*
164 * Verify the extent header as being sane
165 */
ext2fs_extent_header_verify(void * ptr,int size)166 errcode_t ext2fs_extent_header_verify(void *ptr, int size)
167 {
168 int eh_max, entry_size;
169 struct ext3_extent_header *eh = ptr;
170
171 dbg_show_header(eh);
172 if (ext2fs_le16_to_cpu(eh->eh_magic) != EXT3_EXT_MAGIC)
173 return EXT2_ET_EXTENT_HEADER_BAD;
174 if (ext2fs_le16_to_cpu(eh->eh_entries) > ext2fs_le16_to_cpu(eh->eh_max))
175 return EXT2_ET_EXTENT_HEADER_BAD;
176 if (eh->eh_depth == 0)
177 entry_size = sizeof(struct ext3_extent);
178 else
179 entry_size = sizeof(struct ext3_extent_idx);
180
181 eh_max = (size - sizeof(*eh)) / entry_size;
182 /* Allow two extent-sized items at the end of the block, for
183 * ext4_extent_tail with checksum in the future. */
184 if ((ext2fs_le16_to_cpu(eh->eh_max) > eh_max) ||
185 (ext2fs_le16_to_cpu(eh->eh_max) < (eh_max - 2)))
186 return EXT2_ET_EXTENT_HEADER_BAD;
187
188 return 0;
189 }
190
191
192 /*
193 * Begin functions to handle an inode's extent information
194 */
ext2fs_extent_free(ext2_extent_handle_t handle)195 void ext2fs_extent_free(ext2_extent_handle_t handle)
196 {
197 int i;
198
199 if (!handle)
200 return;
201
202 if (handle->path) {
203 for (i = 1; i < handle->max_paths; i++) {
204 if (handle->path[i].buf)
205 ext2fs_free_mem(&handle->path[i].buf);
206 }
207 ext2fs_free_mem(&handle->path);
208 }
209 ext2fs_free_mem(&handle);
210 }
211
ext2fs_extent_open(ext2_filsys fs,ext2_ino_t ino,ext2_extent_handle_t * ret_handle)212 errcode_t ext2fs_extent_open(ext2_filsys fs, ext2_ino_t ino,
213 ext2_extent_handle_t *ret_handle)
214 {
215 return ext2fs_extent_open2(fs, ino, NULL, ret_handle);
216 }
217
ext2fs_extent_open2(ext2_filsys fs,ext2_ino_t ino,struct ext2_inode * inode,ext2_extent_handle_t * ret_handle)218 errcode_t ext2fs_extent_open2(ext2_filsys fs, ext2_ino_t ino,
219 struct ext2_inode *inode,
220 ext2_extent_handle_t *ret_handle)
221 {
222 struct ext2_extent_handle *handle;
223 errcode_t retval;
224 int i;
225 struct ext3_extent_header *eh;
226
227 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
228
229 if (!inode)
230 if ((ino == 0) || (ino > fs->super->s_inodes_count))
231 return EXT2_ET_BAD_INODE_NUM;
232
233 retval = ext2fs_get_mem(sizeof(struct ext2_extent_handle), &handle);
234 if (retval)
235 return retval;
236 memset(handle, 0, sizeof(struct ext2_extent_handle));
237
238 handle->ino = ino;
239 handle->fs = fs;
240
241 if (inode) {
242 handle->inode = inode;
243 } else {
244 handle->inode = &handle->inodebuf;
245 retval = ext2fs_read_inode(fs, ino, handle->inode);
246 if (retval)
247 goto errout;
248 }
249
250 eh = (struct ext3_extent_header *) &handle->inode->i_block[0];
251
252 for (i=0; i < EXT2_N_BLOCKS; i++)
253 if (handle->inode->i_block[i])
254 break;
255 if (i >= EXT2_N_BLOCKS) {
256 eh->eh_magic = ext2fs_cpu_to_le16(EXT3_EXT_MAGIC);
257 eh->eh_depth = 0;
258 eh->eh_entries = 0;
259 i = (sizeof(handle->inode->i_block) - sizeof(*eh)) /
260 sizeof(struct ext3_extent);
261 eh->eh_max = ext2fs_cpu_to_le16(i);
262 handle->inode->i_flags |= EXT4_EXTENTS_FL;
263 }
264
265 if (!(handle->inode->i_flags & EXT4_EXTENTS_FL)) {
266 retval = EXT2_ET_INODE_NOT_EXTENT;
267 goto errout;
268 }
269
270 retval = ext2fs_extent_header_verify(eh, sizeof(handle->inode->i_block));
271 if (retval)
272 goto errout;
273
274 handle->max_depth = ext2fs_le16_to_cpu(eh->eh_depth);
275 handle->type = ext2fs_le16_to_cpu(eh->eh_magic);
276
277 handle->max_paths = handle->max_depth + 1;
278 retval = ext2fs_get_memzero(handle->max_paths *
279 sizeof(struct extent_path),
280 &handle->path);
281 handle->path[0].buf = (char *) handle->inode->i_block;
282
283 handle->path[0].left = handle->path[0].entries =
284 ext2fs_le16_to_cpu(eh->eh_entries);
285 handle->path[0].max_entries = ext2fs_le16_to_cpu(eh->eh_max);
286 handle->path[0].curr = 0;
287 handle->path[0].end_blk =
288 (EXT2_I_SIZE(handle->inode) + fs->blocksize - 1) >>
289 EXT2_BLOCK_SIZE_BITS(fs->super);
290 handle->path[0].blk = 0;
291 handle->path[0].visit_num = 1;
292 handle->level = 0;
293 handle->magic = EXT2_ET_MAGIC_EXTENT_HANDLE;
294
295 *ret_handle = handle;
296 return 0;
297
298 errout:
299 ext2fs_extent_free(handle);
300 return retval;
301 }
302
303 /*
304 * This function is responsible for (optionally) moving through the
305 * extent tree and then returning the current extent
306 */
ext2fs_extent_get(ext2_extent_handle_t handle,int flags,struct ext2fs_extent * extent)307 errcode_t ext2fs_extent_get(ext2_extent_handle_t handle,
308 int flags, struct ext2fs_extent *extent)
309 {
310 struct extent_path *path, *newpath, *tp;
311 struct ext3_extent_header *eh;
312 struct ext3_extent_idx *ix = 0;
313 struct ext3_extent *ex;
314 errcode_t retval;
315 blk64_t blk;
316 blk64_t end_blk;
317 int orig_op, op, l;
318 int failed_csum = 0;
319
320 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
321
322 if (!handle->path)
323 return EXT2_ET_NO_CURRENT_NODE;
324
325 orig_op = op = flags & EXT2_EXTENT_MOVE_MASK;
326
327 retry:
328 path = handle->path + handle->level;
329 if ((orig_op == EXT2_EXTENT_NEXT) ||
330 (orig_op == EXT2_EXTENT_NEXT_LEAF)) {
331 if (handle->level < handle->max_depth) {
332 /* interior node */
333 if (path->visit_num == 0) {
334 path->visit_num++;
335 op = EXT2_EXTENT_DOWN;
336 } else if (path->left > 0)
337 op = EXT2_EXTENT_NEXT_SIB;
338 else if (handle->level > 0)
339 op = EXT2_EXTENT_UP;
340 else
341 return EXT2_ET_EXTENT_NO_NEXT;
342 } else {
343 /* leaf node */
344 if (path->left > 0)
345 op = EXT2_EXTENT_NEXT_SIB;
346 else if (handle->level > 0)
347 op = EXT2_EXTENT_UP;
348 else
349 return EXT2_ET_EXTENT_NO_NEXT;
350 }
351 if (op != EXT2_EXTENT_NEXT_SIB) {
352 #ifdef DEBUG_GET_EXTENT
353 printf("<<<< OP = %s\n",
354 (op == EXT2_EXTENT_DOWN) ? "down" :
355 ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));
356 #endif
357 }
358 }
359
360 if ((orig_op == EXT2_EXTENT_PREV) ||
361 (orig_op == EXT2_EXTENT_PREV_LEAF)) {
362 if (handle->level < handle->max_depth) {
363 /* interior node */
364 if (path->visit_num > 0 ) {
365 /* path->visit_num = 0; */
366 op = EXT2_EXTENT_DOWN_AND_LAST;
367 } else if (path->left < path->entries-1)
368 op = EXT2_EXTENT_PREV_SIB;
369 else if (handle->level > 0)
370 op = EXT2_EXTENT_UP;
371 else
372 return EXT2_ET_EXTENT_NO_PREV;
373 } else {
374 /* leaf node */
375 if (path->left < path->entries-1)
376 op = EXT2_EXTENT_PREV_SIB;
377 else if (handle->level > 0)
378 op = EXT2_EXTENT_UP;
379 else
380 return EXT2_ET_EXTENT_NO_PREV;
381 }
382 if (op != EXT2_EXTENT_PREV_SIB) {
383 #ifdef DEBUG_GET_EXTENT
384 printf("<<<< OP = %s\n",
385 (op == EXT2_EXTENT_DOWN_AND_LAST) ? "down/last" :
386 ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));
387 #endif
388 }
389 }
390
391 if (orig_op == EXT2_EXTENT_LAST_LEAF) {
392 if ((handle->level < handle->max_depth) &&
393 (path->left == 0))
394 op = EXT2_EXTENT_DOWN;
395 else
396 op = EXT2_EXTENT_LAST_SIB;
397 #ifdef DEBUG_GET_EXTENT
398 printf("<<<< OP = %s\n",
399 (op == EXT2_EXTENT_DOWN) ? "down" : "last_sib");
400 #endif
401 }
402
403 switch (op) {
404 case EXT2_EXTENT_CURRENT:
405 ix = path->curr;
406 break;
407 case EXT2_EXTENT_ROOT:
408 handle->level = 0;
409 path = handle->path + handle->level;
410 /* fallthrough */
411 case EXT2_EXTENT_FIRST_SIB:
412 path->left = path->entries;
413 path->curr = 0;
414 /* fallthrough */
415 case EXT2_EXTENT_NEXT_SIB:
416 if (path->left <= 0)
417 return EXT2_ET_EXTENT_NO_NEXT;
418 if (path->curr) {
419 ix = path->curr;
420 ix++;
421 } else {
422 eh = (struct ext3_extent_header *) path->buf;
423 ix = EXT_FIRST_INDEX(eh);
424 }
425 path->left--;
426 path->curr = ix;
427 path->visit_num = 0;
428 break;
429 case EXT2_EXTENT_PREV_SIB:
430 if (!path->curr ||
431 path->left+1 >= path->entries)
432 return EXT2_ET_EXTENT_NO_PREV;
433 ix = path->curr;
434 ix--;
435 path->curr = ix;
436 path->left++;
437 if (handle->level < handle->max_depth)
438 path->visit_num = 1;
439 break;
440 case EXT2_EXTENT_LAST_SIB:
441 eh = (struct ext3_extent_header *) path->buf;
442 path->curr = EXT_LAST_EXTENT(eh);
443 ix = path->curr;
444 path->left = 0;
445 path->visit_num = 0;
446 break;
447 case EXT2_EXTENT_UP:
448 if (handle->level <= 0)
449 return EXT2_ET_EXTENT_NO_UP;
450 handle->level--;
451 path--;
452 ix = path->curr;
453 if ((orig_op == EXT2_EXTENT_PREV) ||
454 (orig_op == EXT2_EXTENT_PREV_LEAF))
455 path->visit_num = 0;
456 break;
457 case EXT2_EXTENT_DOWN:
458 case EXT2_EXTENT_DOWN_AND_LAST:
459 if (!path->curr ||(handle->level >= handle->max_depth))
460 return EXT2_ET_EXTENT_NO_DOWN;
461
462 ix = path->curr;
463 newpath = path + 1;
464 if (!newpath->buf) {
465 retval = ext2fs_get_mem(handle->fs->blocksize,
466 &newpath->buf);
467 if (retval)
468 return retval;
469 }
470 blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
471 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
472 for (l = handle->level, tp = path; l > 0; l--, tp--) {
473 if (blk == tp->blk)
474 return EXT2_ET_EXTENT_CYCLE;
475 }
476 newpath->blk = blk;
477 if ((handle->fs->flags & EXT2_FLAG_IMAGE_FILE) &&
478 (handle->fs->io != handle->fs->image_io))
479 memset(newpath->buf, 0, handle->fs->blocksize);
480 else {
481 retval = io_channel_read_blk64(handle->fs->io,
482 blk, 1, newpath->buf);
483 if (retval)
484 return retval;
485 }
486 handle->level++;
487
488 eh = (struct ext3_extent_header *) newpath->buf;
489
490 retval = ext2fs_extent_header_verify(eh, handle->fs->blocksize);
491 if (retval) {
492 handle->level--;
493 return retval;
494 }
495
496 if (!(handle->fs->flags & EXT2_FLAG_IGNORE_CSUM_ERRORS) &&
497 !ext2fs_extent_block_csum_verify(handle->fs, handle->ino,
498 eh))
499 failed_csum = 1;
500
501 newpath->left = newpath->entries =
502 ext2fs_le16_to_cpu(eh->eh_entries);
503 newpath->max_entries = ext2fs_le16_to_cpu(eh->eh_max);
504
505 /* Make sure there is at least one extent present */
506 if (newpath->left <= 0)
507 return EXT2_ET_EXTENT_NO_DOWN;
508
509 if (path->left > 0) {
510 ix++;
511 newpath->end_blk = ext2fs_le32_to_cpu(ix->ei_block);
512 } else
513 newpath->end_blk = path->end_blk;
514
515 path = newpath;
516 if (op == EXT2_EXTENT_DOWN) {
517 ix = EXT_FIRST_INDEX((struct ext3_extent_header *) eh);
518 path->curr = ix;
519 path->left = path->entries - 1;
520 path->visit_num = 0;
521 } else {
522 ix = EXT_LAST_INDEX((struct ext3_extent_header *) eh);
523 path->curr = ix;
524 path->left = 0;
525 if (handle->level < handle->max_depth)
526 path->visit_num = 1;
527 }
528 #ifdef DEBUG_GET_EXTENT
529 printf("Down to level %d/%d, end_blk=%llu\n",
530 handle->level, handle->max_depth,
531 path->end_blk);
532 #endif
533 break;
534 default:
535 return EXT2_ET_OP_NOT_SUPPORTED;
536 }
537
538 if (!ix)
539 return EXT2_ET_NO_CURRENT_NODE;
540
541 extent->e_flags = 0;
542 #ifdef DEBUG_GET_EXTENT
543 printf("(Left %d)\n", path->left);
544 #endif
545
546 if (handle->level == handle->max_depth) {
547 ex = (struct ext3_extent *) ix;
548
549 extent->e_pblk = ext2fs_le32_to_cpu(ex->ee_start) +
550 ((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32);
551 extent->e_lblk = ext2fs_le32_to_cpu(ex->ee_block);
552 extent->e_len = ext2fs_le16_to_cpu(ex->ee_len);
553 extent->e_flags |= EXT2_EXTENT_FLAGS_LEAF;
554 if (extent->e_len > EXT_INIT_MAX_LEN) {
555 extent->e_len -= EXT_INIT_MAX_LEN;
556 extent->e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
557 }
558 } else {
559 extent->e_pblk = ext2fs_le32_to_cpu(ix->ei_leaf) +
560 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
561 extent->e_lblk = ext2fs_le32_to_cpu(ix->ei_block);
562 if (path->left > 0) {
563 ix++;
564 end_blk = ext2fs_le32_to_cpu(ix->ei_block);
565 } else
566 end_blk = path->end_blk;
567
568 extent->e_len = end_blk - extent->e_lblk;
569 }
570 if (path->visit_num)
571 extent->e_flags |= EXT2_EXTENT_FLAGS_SECOND_VISIT;
572
573 if (((orig_op == EXT2_EXTENT_NEXT_LEAF) ||
574 (orig_op == EXT2_EXTENT_PREV_LEAF)) &&
575 (handle->level != handle->max_depth))
576 goto retry;
577
578 if ((orig_op == EXT2_EXTENT_LAST_LEAF) &&
579 ((handle->level != handle->max_depth) ||
580 (path->left != 0)))
581 goto retry;
582
583 if (failed_csum)
584 return EXT2_ET_EXTENT_CSUM_INVALID;
585
586 return 0;
587 }
588
update_path(ext2_extent_handle_t handle)589 static errcode_t update_path(ext2_extent_handle_t handle)
590 {
591 blk64_t blk;
592 errcode_t retval;
593 struct ext3_extent_idx *ix;
594 struct ext3_extent_header *eh;
595
596 if (handle->level == 0) {
597 retval = ext2fs_write_inode(handle->fs, handle->ino,
598 handle->inode);
599 } else {
600 ix = handle->path[handle->level - 1].curr;
601 blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
602 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
603
604 /* then update the checksum */
605 eh = (struct ext3_extent_header *)
606 handle->path[handle->level].buf;
607 retval = ext2fs_extent_block_csum_set(handle->fs, handle->ino,
608 eh);
609 if (retval)
610 return retval;
611
612 retval = io_channel_write_blk64(handle->fs->io,
613 blk, 1, handle->path[handle->level].buf);
614 }
615 return retval;
616 }
617
618 #if 0
619 errcode_t ext2fs_extent_save_path(ext2_extent_handle_t handle,
620 ext2_extent_path_t *ret_path)
621 {
622 ext2_extent_path_t save_path;
623 struct ext2fs_extent extent;
624 struct ext2_extent_info info;
625 errcode_t retval;
626
627 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
628 if (retval)
629 return retval;
630
631 retval = ext2fs_extent_get_info(handle, &info);
632 if (retval)
633 return retval;
634
635 retval = ext2fs_get_mem(sizeof(struct ext2_extent_path), &save_path);
636 if (retval)
637 return retval;
638 memset(save_path, 0, sizeof(struct ext2_extent_path));
639
640 save_path->magic = EXT2_ET_MAGIC_EXTENT_PATH;
641 save_path->leaf_height = info.max_depth - info.curr_level - 1;
642 save_path->lblk = extent.e_lblk;
643
644 *ret_path = save_path;
645 return 0;
646 }
647
648 errcode_t ext2fs_extent_free_path(ext2_extent_path_t path)
649 {
650 EXT2_CHECK_MAGIC(path, EXT2_ET_MAGIC_EXTENT_PATH);
651
652 ext2fs_free_mem(&path);
653 return 0;
654 }
655 #endif
656
657 /*
658 * Go to the node at leaf_level which contains logical block blk.
659 *
660 * leaf_level is height from the leaf node level, i.e.
661 * leaf_level 0 is at leaf node, leaf_level 1 is 1 above etc.
662 *
663 * If "blk" has no mapping (hole) then handle is left at last
664 * extent before blk.
665 */
ext2fs_extent_goto2(ext2_extent_handle_t handle,int leaf_level,blk64_t blk)666 errcode_t ext2fs_extent_goto2(ext2_extent_handle_t handle,
667 int leaf_level, blk64_t blk)
668 {
669 struct ext2fs_extent extent;
670 errcode_t retval;
671
672 retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent);
673 if (retval) {
674 if (retval == EXT2_ET_EXTENT_NO_NEXT)
675 retval = EXT2_ET_EXTENT_NOT_FOUND;
676 return retval;
677 }
678
679 if (leaf_level > handle->max_depth) {
680 #ifdef DEBUG
681 printf("leaf level %d greater than tree depth %d\n",
682 leaf_level, handle->max_depth);
683 #endif
684 return EXT2_ET_OP_NOT_SUPPORTED;
685 }
686
687 #ifdef DEBUG
688 printf("goto extent ino %u, level %d, %llu\n", handle->ino,
689 leaf_level, blk);
690 #endif
691
692 #ifdef DEBUG_GOTO_EXTENTS
693 dbg_print_extent("root", &extent);
694 #endif
695 while (1) {
696 if (handle->max_depth - handle->level == leaf_level) {
697 /* block is in this &extent */
698 if ((blk >= extent.e_lblk) &&
699 (blk < extent.e_lblk + extent.e_len))
700 return 0;
701 if (blk < extent.e_lblk) {
702 retval = ext2fs_extent_get(handle,
703 EXT2_EXTENT_PREV_SIB,
704 &extent);
705 return EXT2_ET_EXTENT_NOT_FOUND;
706 }
707 retval = ext2fs_extent_get(handle,
708 EXT2_EXTENT_NEXT_SIB,
709 &extent);
710 if (retval == EXT2_ET_EXTENT_NO_NEXT)
711 return EXT2_ET_EXTENT_NOT_FOUND;
712 if (retval)
713 return retval;
714 continue;
715 }
716
717 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_SIB,
718 &extent);
719 if (retval == EXT2_ET_EXTENT_NO_NEXT)
720 goto go_down;
721 if (retval)
722 return retval;
723
724 #ifdef DEBUG_GOTO_EXTENTS
725 dbg_print_extent("next", &extent);
726 #endif
727 if (blk == extent.e_lblk)
728 goto go_down;
729 if (blk > extent.e_lblk)
730 continue;
731
732 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_SIB,
733 &extent);
734 if (retval)
735 return retval;
736
737 #ifdef DEBUG_GOTO_EXTENTS
738 dbg_print_extent("prev", &extent);
739 #endif
740
741 go_down:
742 retval = ext2fs_extent_get(handle, EXT2_EXTENT_DOWN,
743 &extent);
744 if (retval)
745 return retval;
746
747 #ifdef DEBUG_GOTO_EXTENTS
748 dbg_print_extent("down", &extent);
749 #endif
750 }
751 }
752
ext2fs_extent_goto(ext2_extent_handle_t handle,blk64_t blk)753 errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle,
754 blk64_t blk)
755 {
756 return ext2fs_extent_goto2(handle, 0, blk);
757 }
758
759 /*
760 * Traverse back up to root fixing parents of current node as needed.
761 *
762 * If we changed start of first entry in a node, fix parent index start
763 * and so on.
764 *
765 * Safe to call for any position in node; if not at the first entry,
766 * it will simply return.
767 *
768 * Note a subtlety of this function -- if there happen to be two extents
769 * mapping the same lblk and someone calls fix_parents on the second of the two
770 * extents, the position of the extent handle after the call will be the second
771 * extent if nothing happened, or the first extent if something did. A caller
772 * in this situation must use ext2fs_extent_goto() after calling this function.
773 * Or simply don't map the same lblk with two extents, ever.
774 */
ext2fs_extent_fix_parents(ext2_extent_handle_t handle)775 errcode_t ext2fs_extent_fix_parents(ext2_extent_handle_t handle)
776 {
777 int retval = 0;
778 int orig_height;
779 blk64_t start;
780 struct extent_path *path;
781 struct ext2fs_extent extent;
782 struct ext2_extent_info info;
783
784 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
785
786 if (!(handle->fs->flags & EXT2_FLAG_RW))
787 return EXT2_ET_RO_FILSYS;
788
789 if (!handle->path)
790 return EXT2_ET_NO_CURRENT_NODE;
791
792 path = handle->path + handle->level;
793 if (!path->curr)
794 return EXT2_ET_NO_CURRENT_NODE;
795
796 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
797 if (retval)
798 goto done;
799
800 /* modified node's start block */
801 start = extent.e_lblk;
802
803 if ((retval = ext2fs_extent_get_info(handle, &info)))
804 return retval;
805 orig_height = info.max_depth - info.curr_level;
806
807 /* traverse up until index not first, or startblk matches, or top */
808 while (handle->level > 0 &&
809 (path->left == path->entries - 1)) {
810 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
811 if (retval)
812 goto done;
813 if (extent.e_lblk == start)
814 break;
815 path = handle->path + handle->level;
816 extent.e_len += (extent.e_lblk - start);
817 extent.e_lblk = start;
818 retval = ext2fs_extent_replace(handle, 0, &extent);
819 if (retval)
820 goto done;
821 update_path(handle);
822 }
823
824 /* put handle back to where we started */
825 retval = ext2fs_extent_goto2(handle, orig_height, start);
826 done:
827 return retval;
828 }
829
ext2fs_extent_replace(ext2_extent_handle_t handle,int flags EXT2FS_ATTR ((unused)),struct ext2fs_extent * extent)830 errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle,
831 int flags EXT2FS_ATTR((unused)),
832 struct ext2fs_extent *extent)
833 {
834 struct extent_path *path;
835 struct ext3_extent_idx *ix;
836 struct ext3_extent *ex;
837
838 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
839
840 if (!(handle->fs->flags & EXT2_FLAG_RW))
841 return EXT2_ET_RO_FILSYS;
842
843 if (!handle->path)
844 return EXT2_ET_NO_CURRENT_NODE;
845
846 path = handle->path + handle->level;
847 if (!path->curr)
848 return EXT2_ET_NO_CURRENT_NODE;
849
850 #ifdef DEBUG
851 printf("extent replace: %u ", handle->ino);
852 dbg_print_extent(0, extent);
853 #endif
854
855 if (handle->level == handle->max_depth) {
856 ex = path->curr;
857
858 ex->ee_block = ext2fs_cpu_to_le32(extent->e_lblk);
859 ex->ee_start = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);
860 ex->ee_start_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);
861 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) {
862 if (extent->e_len > EXT_UNINIT_MAX_LEN)
863 return EXT2_ET_EXTENT_INVALID_LENGTH;
864 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len +
865 EXT_INIT_MAX_LEN);
866 } else {
867 if (extent->e_len > EXT_INIT_MAX_LEN)
868 return EXT2_ET_EXTENT_INVALID_LENGTH;
869 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len);
870 }
871 } else {
872 ix = path->curr;
873
874 ix->ei_leaf = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);
875 ix->ei_leaf_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);
876 ix->ei_block = ext2fs_cpu_to_le32(extent->e_lblk);
877 ix->ei_unused = 0;
878 }
879 update_path(handle);
880 return 0;
881 }
882
splitting_at_eof(struct ext2_extent_handle * handle,struct extent_path * path)883 static int splitting_at_eof(struct ext2_extent_handle *handle,
884 struct extent_path *path)
885 {
886 struct extent_path *ppp = path;
887 dump_path(__func__, handle, path);
888
889 if (handle->level == 0)
890 return 0;
891
892 do {
893 if (ppp->left)
894 return 0;
895 ppp--;
896 } while (ppp >= handle->path);
897
898 return 1;
899 }
900
901 /*
902 * allocate a new block, move half the current node to it, and update parent
903 *
904 * handle will be left pointing at original record.
905 */
extent_node_split(ext2_extent_handle_t handle,int expand_allowed)906 static errcode_t extent_node_split(ext2_extent_handle_t handle,
907 int expand_allowed)
908 {
909 errcode_t retval = 0;
910 blk64_t new_node_pblk;
911 blk64_t new_node_start;
912 blk64_t orig_lblk;
913 blk64_t goal_blk = 0;
914 int orig_height;
915 char *block_buf = NULL;
916 struct ext2fs_extent extent;
917 struct extent_path *path, *newpath = 0;
918 struct ext3_extent_header *eh, *neweh;
919 int tocopy;
920 int new_root = 0;
921 struct ext2_extent_info info;
922 int no_balance;
923
924 /* basic sanity */
925 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
926
927 if (!(handle->fs->flags & EXT2_FLAG_RW))
928 return EXT2_ET_RO_FILSYS;
929
930 if (!handle->path)
931 return EXT2_ET_NO_CURRENT_NODE;
932
933 #ifdef DEBUG
934 printf("splitting node at level %d\n", handle->level);
935 #endif
936 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
937 if (retval)
938 goto done;
939
940 retval = ext2fs_extent_get_info(handle, &info);
941 if (retval)
942 goto done;
943
944 /* save the position we were originally splitting... */
945 orig_height = info.max_depth - info.curr_level;
946 orig_lblk = extent.e_lblk;
947
948 /* Try to put the index block before the first extent */
949 path = handle->path + handle->level;
950 eh = (struct ext3_extent_header *) path->buf;
951 if (handle->level == handle->max_depth) {
952 struct ext3_extent *ex;
953
954 ex = EXT_FIRST_EXTENT(eh);
955 goal_blk = ext2fs_le32_to_cpu(ex->ee_start) +
956 ((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32);
957 } else {
958 struct ext3_extent_idx *ix;
959
960 ix = EXT_FIRST_INDEX(eh);
961 goal_blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
962 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
963 }
964 goal_blk -= EXT2FS_CLUSTER_RATIO(handle->fs);
965 goal_blk &= ~EXT2FS_CLUSTER_MASK(handle->fs);
966
967 /* Is there room in the parent for a new entry? */
968 if (handle->level &&
969 (handle->path[handle->level - 1].entries >=
970 handle->path[handle->level - 1].max_entries)) {
971
972 #ifdef DEBUG
973 printf("parent level %d full; splitting it too\n",
974 handle->level - 1);
975 #endif
976 /* split the parent */
977 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
978 if (retval)
979 goto done;
980
981 retval = extent_node_split(handle, expand_allowed);
982 if (retval)
983 goto done;
984
985 /* get handle back to our original split position */
986 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk);
987 if (retval)
988 goto done;
989 }
990
991 /* At this point, parent should have room for this split */
992 path = handle->path + handle->level;
993 if (!path->curr)
994 return EXT2_ET_NO_CURRENT_NODE;
995
996 /*
997 * Normally, we try to split a full node in half. This doesn't turn
998 * out so well if we're tacking extents on the end of the file because
999 * then we're stuck with a tree of half-full extent blocks. This of
1000 * course doesn't apply to the root level.
1001 */
1002 no_balance = expand_allowed ? splitting_at_eof(handle, path) : 0;
1003
1004 /* extent header of the current node we'll split */
1005 eh = (struct ext3_extent_header *)path->buf;
1006
1007 /* splitting root level means moving them all out */
1008 if (handle->level == 0) {
1009 new_root = 1;
1010 tocopy = ext2fs_le16_to_cpu(eh->eh_entries);
1011 retval = ext2fs_get_memzero((handle->max_paths + 1) *
1012 sizeof(struct extent_path),
1013 &newpath);
1014 if (retval)
1015 goto done;
1016 } else {
1017 if (no_balance)
1018 tocopy = 1;
1019 else
1020 tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2;
1021 }
1022
1023 #ifdef DEBUG
1024 printf("will copy out %d of %d entries at level %d\n",
1025 tocopy, ext2fs_le16_to_cpu(eh->eh_entries),
1026 handle->level);
1027 #endif
1028
1029 if (!tocopy && !no_balance) {
1030 #ifdef DEBUG
1031 printf("Nothing to copy to new block!\n");
1032 #endif
1033 retval = EXT2_ET_CANT_SPLIT_EXTENT;
1034 goto done;
1035 }
1036
1037 /* first we need a new block, or can do nothing. */
1038 block_buf = malloc(handle->fs->blocksize);
1039 if (!block_buf) {
1040 retval = ENOMEM;
1041 goto done;
1042 }
1043
1044 if (!goal_blk)
1045 goal_blk = ext2fs_find_inode_goal(handle->fs, handle->ino,
1046 handle->inode, 0);
1047 retval = ext2fs_alloc_block2(handle->fs, goal_blk, block_buf,
1048 &new_node_pblk);
1049 if (retval)
1050 goto done;
1051
1052 #ifdef DEBUG
1053 printf("will copy to new node at block %lu\n",
1054 (unsigned long) new_node_pblk);
1055 #endif
1056
1057 /* Copy data into new block buffer */
1058 /* First the header for the new block... */
1059 neweh = (struct ext3_extent_header *) block_buf;
1060 memcpy(neweh, eh, sizeof(struct ext3_extent_header));
1061 neweh->eh_entries = ext2fs_cpu_to_le16(tocopy);
1062 neweh->eh_max = ext2fs_cpu_to_le16((handle->fs->blocksize -
1063 sizeof(struct ext3_extent_header)) /
1064 sizeof(struct ext3_extent));
1065
1066 /* then the entries for the new block... */
1067 memcpy(EXT_FIRST_INDEX(neweh),
1068 EXT_FIRST_INDEX(eh) +
1069 (ext2fs_le16_to_cpu(eh->eh_entries) - tocopy),
1070 sizeof(struct ext3_extent_idx) * tocopy);
1071
1072 new_node_start = ext2fs_le32_to_cpu(EXT_FIRST_INDEX(neweh)->ei_block);
1073
1074 /* then update the checksum */
1075 retval = ext2fs_extent_block_csum_set(handle->fs, handle->ino, neweh);
1076 if (retval)
1077 goto done;
1078
1079 /* ...and write the new node block out to disk. */
1080 retval = io_channel_write_blk64(handle->fs->io, new_node_pblk, 1,
1081 block_buf);
1082
1083 if (retval)
1084 goto done;
1085
1086 /* OK! we've created the new node; now adjust the tree */
1087
1088 /* current path now has fewer active entries, we copied some out */
1089 if (handle->level == 0) {
1090 memcpy(newpath, path,
1091 sizeof(struct extent_path) * handle->max_paths);
1092 handle->path = newpath;
1093 newpath = path;
1094 path = handle->path;
1095 path->entries = 1;
1096 path->left = path->max_entries - 1;
1097 handle->max_depth++;
1098 handle->max_paths++;
1099 eh->eh_depth = ext2fs_cpu_to_le16(handle->max_depth);
1100 } else {
1101 path->entries -= tocopy;
1102 path->left -= tocopy;
1103 }
1104
1105 eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
1106 /* this writes out the node, incl. the modified header */
1107 retval = update_path(handle);
1108 if (retval)
1109 goto done;
1110
1111 /* now go up and insert/replace index for new node we created */
1112 if (new_root) {
1113 retval = ext2fs_extent_get(handle, EXT2_EXTENT_FIRST_SIB, &extent);
1114 if (retval)
1115 goto done;
1116
1117 extent.e_lblk = new_node_start;
1118 extent.e_pblk = new_node_pblk;
1119 extent.e_len = handle->path[0].end_blk - extent.e_lblk;
1120 retval = ext2fs_extent_replace(handle, 0, &extent);
1121 if (retval)
1122 goto done;
1123 } else {
1124 __u32 new_node_length;
1125
1126 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
1127 /* will insert after this one; it's length is shorter now */
1128 new_node_length = new_node_start - extent.e_lblk;
1129 extent.e_len -= new_node_length;
1130 retval = ext2fs_extent_replace(handle, 0, &extent);
1131 if (retval)
1132 goto done;
1133
1134 /* now set up the new extent and insert it */
1135 extent.e_lblk = new_node_start;
1136 extent.e_pblk = new_node_pblk;
1137 extent.e_len = new_node_length;
1138 retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER, &extent);
1139 if (retval)
1140 goto done;
1141 }
1142
1143 /* get handle back to our original position */
1144 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk);
1145 if (retval)
1146 goto done;
1147
1148 /* new node hooked in, so update inode block count (do this here?) */
1149 ext2fs_iblk_add_blocks(handle->fs, handle->inode, 1);
1150 retval = ext2fs_write_inode(handle->fs, handle->ino,
1151 handle->inode);
1152 if (retval)
1153 goto done;
1154
1155 done:
1156 if (newpath)
1157 ext2fs_free_mem(&newpath);
1158 free(block_buf);
1159
1160 return retval;
1161 }
1162
ext2fs_extent_node_split(ext2_extent_handle_t handle)1163 errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
1164 {
1165 return extent_node_split(handle, 0);
1166 }
1167
ext2fs_extent_insert(ext2_extent_handle_t handle,int flags,struct ext2fs_extent * extent)1168 errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
1169 struct ext2fs_extent *extent)
1170 {
1171 struct extent_path *path;
1172 struct ext3_extent_idx *ix;
1173 struct ext3_extent_header *eh;
1174 errcode_t retval;
1175
1176 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1177
1178 if (!(handle->fs->flags & EXT2_FLAG_RW))
1179 return EXT2_ET_RO_FILSYS;
1180
1181 if (!handle->path)
1182 return EXT2_ET_NO_CURRENT_NODE;
1183
1184 #ifdef DEBUG
1185 printf("extent insert: %u ", handle->ino);
1186 dbg_print_extent(0, extent);
1187 #endif
1188
1189 path = handle->path + handle->level;
1190
1191 if (path->entries >= path->max_entries) {
1192 if (flags & EXT2_EXTENT_INSERT_NOSPLIT) {
1193 return EXT2_ET_CANT_INSERT_EXTENT;
1194 } else {
1195 #ifdef DEBUG
1196 printf("node full (level %d) - splitting\n",
1197 handle->level);
1198 #endif
1199 retval = extent_node_split(handle, 1);
1200 if (retval)
1201 return retval;
1202 path = handle->path + handle->level;
1203 }
1204 }
1205
1206 eh = (struct ext3_extent_header *) path->buf;
1207 if (path->curr) {
1208 ix = path->curr;
1209 if (flags & EXT2_EXTENT_INSERT_AFTER) {
1210 ix++;
1211 path->left--;
1212 }
1213 } else {
1214 ix = EXT_FIRST_INDEX(eh);
1215 path->left = -1;
1216 }
1217
1218 path->curr = ix;
1219
1220 if (path->left >= 0)
1221 memmove(ix + 1, ix,
1222 (path->left+1) * sizeof(struct ext3_extent_idx));
1223 path->left++;
1224 path->entries++;
1225
1226 eh = (struct ext3_extent_header *) path->buf;
1227 eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
1228
1229 retval = ext2fs_extent_replace(handle, 0, extent);
1230 if (retval)
1231 goto errout;
1232
1233 retval = update_path(handle);
1234 if (retval)
1235 goto errout;
1236
1237 return 0;
1238
1239 errout:
1240 ext2fs_extent_delete(handle, 0);
1241 return retval;
1242 }
1243
1244 /*
1245 * Sets the physical block for a logical file block in the extent tree.
1246 *
1247 * May: map unmapped, unmap mapped, or remap mapped blocks.
1248 *
1249 * Mapping an unmapped block adds a single-block extent.
1250 *
1251 * Unmapping first or last block modifies extent in-place
1252 * - But may need to fix parent's starts too in first-block case
1253 *
1254 * Mapping any unmapped block requires adding a (single-block) extent
1255 * and inserting into proper point in tree.
1256 *
1257 * Modifying (unmapping or remapping) a block in the middle
1258 * of an extent requires splitting the extent.
1259 * - Remapping case requires new single-block extent.
1260 *
1261 * Remapping first or last block adds an extent.
1262 *
1263 * We really need extent adding to be smart about merging.
1264 */
1265
ext2fs_extent_set_bmap(ext2_extent_handle_t handle,blk64_t logical,blk64_t physical,int flags)1266 errcode_t ext2fs_extent_set_bmap(ext2_extent_handle_t handle,
1267 blk64_t logical, blk64_t physical, int flags)
1268 {
1269 errcode_t ec, retval = 0;
1270 int mapped = 1; /* logical is mapped? */
1271 int orig_height;
1272 int extent_uninit = 0;
1273 int prev_uninit = 0;
1274 int next_uninit = 0;
1275 int new_uninit = 0;
1276 int max_len = EXT_INIT_MAX_LEN;
1277 int has_prev, has_next;
1278 blk64_t orig_lblk;
1279 struct extent_path *path;
1280 struct ext2fs_extent extent, next_extent, prev_extent;
1281 struct ext2fs_extent newextent;
1282 struct ext2_extent_info info;
1283
1284 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1285
1286 #ifdef DEBUG
1287 printf("set_bmap ino %u log %lld phys %lld flags %d\n",
1288 handle->ino, logical, physical, flags);
1289 #endif
1290
1291 if (!(handle->fs->flags & EXT2_FLAG_RW))
1292 return EXT2_ET_RO_FILSYS;
1293
1294 if (!handle->path)
1295 return EXT2_ET_NO_CURRENT_NODE;
1296
1297 path = handle->path + handle->level;
1298
1299 if (flags & EXT2_EXTENT_SET_BMAP_UNINIT) {
1300 new_uninit = 1;
1301 max_len = EXT_UNINIT_MAX_LEN;
1302 }
1303
1304 /* if (re)mapping, set up new extent to insert */
1305 if (physical) {
1306 newextent.e_len = 1;
1307 newextent.e_pblk = physical;
1308 newextent.e_lblk = logical;
1309 newextent.e_flags = EXT2_EXTENT_FLAGS_LEAF;
1310 if (new_uninit)
1311 newextent.e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
1312 }
1313
1314 /* special case if the extent tree is completely empty */
1315 if ((handle->max_depth == 0) && (path->entries == 0)) {
1316 retval = ext2fs_extent_insert(handle, 0, &newextent);
1317 return retval;
1318 }
1319
1320 /* save our original location in the extent tree */
1321 if ((retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
1322 &extent))) {
1323 if (retval != EXT2_ET_NO_CURRENT_NODE)
1324 return retval;
1325 memset(&extent, 0, sizeof(extent));
1326 }
1327 if ((retval = ext2fs_extent_get_info(handle, &info)))
1328 return retval;
1329 orig_height = info.max_depth - info.curr_level;
1330 orig_lblk = extent.e_lblk;
1331
1332 /* go to the logical spot we want to (re/un)map */
1333 retval = ext2fs_extent_goto(handle, logical);
1334 if (retval) {
1335 if (retval == EXT2_ET_EXTENT_NOT_FOUND) {
1336 retval = 0;
1337 mapped = 0;
1338 if (!physical) {
1339 #ifdef DEBUG
1340 printf("block %llu already unmapped\n",
1341 logical);
1342 #endif
1343 goto done;
1344 }
1345 } else
1346 goto done;
1347 }
1348
1349 /*
1350 * This may be the extent *before* the requested logical,
1351 * if it's currently unmapped.
1352 *
1353 * Get the previous and next leaf extents, if they are present.
1354 */
1355 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
1356 if (retval)
1357 goto done;
1358 if (extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT)
1359 extent_uninit = 1;
1360 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_LEAF, &next_extent);
1361 if (retval) {
1362 has_next = 0;
1363 if (retval != EXT2_ET_EXTENT_NO_NEXT)
1364 goto done;
1365 } else {
1366 dbg_print_extent("set_bmap: next_extent",
1367 &next_extent);
1368 has_next = 1;
1369 if (next_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT)
1370 next_uninit = 1;
1371 }
1372 retval = ext2fs_extent_goto(handle, logical);
1373 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND)
1374 goto done;
1375 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_LEAF, &prev_extent);
1376 if (retval) {
1377 has_prev = 0;
1378 if (retval != EXT2_ET_EXTENT_NO_PREV)
1379 goto done;
1380 } else {
1381 has_prev = 1;
1382 dbg_print_extent("set_bmap: prev_extent",
1383 &prev_extent);
1384 if (prev_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT)
1385 prev_uninit = 1;
1386 }
1387 retval = ext2fs_extent_goto(handle, logical);
1388 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND)
1389 goto done;
1390
1391 /* check if already pointing to the requested physical */
1392 if (mapped && (new_uninit == extent_uninit) &&
1393 (extent.e_pblk + (logical - extent.e_lblk) == physical)) {
1394 #ifdef DEBUG
1395 printf("physical block (at %llu) unchanged\n", logical);
1396 #endif
1397 goto done;
1398 }
1399
1400 if (!mapped) {
1401 #ifdef DEBUG
1402 printf("mapping unmapped logical block %llu\n", logical);
1403 #endif
1404 if ((logical == extent.e_lblk + extent.e_len) &&
1405 (physical == extent.e_pblk + extent.e_len) &&
1406 (new_uninit == extent_uninit) &&
1407 ((int) extent.e_len < max_len-1)) {
1408 extent.e_len++;
1409 retval = ext2fs_extent_replace(handle, 0, &extent);
1410 } else if ((logical == extent.e_lblk - 1) &&
1411 (physical == extent.e_pblk - 1) &&
1412 (new_uninit == extent_uninit) &&
1413 ((int) extent.e_len < max_len - 1)) {
1414 extent.e_len++;
1415 extent.e_lblk--;
1416 extent.e_pblk--;
1417 retval = ext2fs_extent_replace(handle, 0, &extent);
1418 } else if (has_next &&
1419 (logical == next_extent.e_lblk - 1) &&
1420 (physical == next_extent.e_pblk - 1) &&
1421 (new_uninit == next_uninit) &&
1422 ((int) next_extent.e_len < max_len - 1)) {
1423 retval = ext2fs_extent_get(handle,
1424 EXT2_EXTENT_NEXT_LEAF,
1425 &next_extent);
1426 if (retval)
1427 goto done;
1428 next_extent.e_len++;
1429 next_extent.e_lblk--;
1430 next_extent.e_pblk--;
1431 retval = ext2fs_extent_replace(handle, 0, &next_extent);
1432 } else if (logical < extent.e_lblk)
1433 retval = ext2fs_extent_insert(handle, 0, &newextent);
1434 else
1435 retval = ext2fs_extent_insert(handle,
1436 EXT2_EXTENT_INSERT_AFTER, &newextent);
1437 if (retval)
1438 goto done;
1439 retval = ext2fs_extent_fix_parents(handle);
1440 if (retval)
1441 goto done;
1442 } else if ((logical == extent.e_lblk) && (extent.e_len == 1)) {
1443 #ifdef DEBUG
1444 printf("(re/un)mapping only block in extent\n");
1445 #endif
1446 if (physical) {
1447 retval = ext2fs_extent_replace(handle, 0, &newextent);
1448 } else {
1449 retval = ext2fs_extent_delete(handle, 0);
1450 if (retval)
1451 goto done;
1452 ec = ext2fs_extent_fix_parents(handle);
1453 if (ec != EXT2_ET_NO_CURRENT_NODE)
1454 retval = ec;
1455 }
1456
1457 if (retval)
1458 goto done;
1459 } else if (logical == extent.e_lblk + extent.e_len - 1) {
1460 #ifdef DEBUG
1461 printf("(re/un)mapping last block in extent\n");
1462 #endif
1463 if (physical) {
1464 if (has_next &&
1465 (logical == (next_extent.e_lblk - 1)) &&
1466 (physical == (next_extent.e_pblk - 1)) &&
1467 (new_uninit == next_uninit) &&
1468 ((int) next_extent.e_len < max_len - 1)) {
1469 retval = ext2fs_extent_get(handle,
1470 EXT2_EXTENT_NEXT_LEAF, &next_extent);
1471 if (retval)
1472 goto done;
1473 next_extent.e_len++;
1474 next_extent.e_lblk--;
1475 next_extent.e_pblk--;
1476 retval = ext2fs_extent_replace(handle, 0,
1477 &next_extent);
1478 if (retval)
1479 goto done;
1480 } else
1481 retval = ext2fs_extent_insert(handle,
1482 EXT2_EXTENT_INSERT_AFTER, &newextent);
1483 if (retval)
1484 goto done;
1485 retval = ext2fs_extent_fix_parents(handle);
1486 if (retval)
1487 goto done;
1488 /*
1489 * Now pointing at inserted extent; move back to prev.
1490 *
1491 * We cannot use EXT2_EXTENT_PREV to go back; note the
1492 * subtlety in the comment for fix_parents().
1493 */
1494 retval = ext2fs_extent_goto(handle, logical);
1495 if (retval)
1496 goto done;
1497 retval = ext2fs_extent_get(handle,
1498 EXT2_EXTENT_CURRENT,
1499 &extent);
1500 if (retval)
1501 goto done;
1502 }
1503 extent.e_len--;
1504 retval = ext2fs_extent_replace(handle, 0, &extent);
1505 if (retval)
1506 goto done;
1507 } else if (logical == extent.e_lblk) {
1508 #ifdef DEBUG
1509 printf("(re/un)mapping first block in extent\n");
1510 #endif
1511 if (physical) {
1512 if (has_prev &&
1513 (logical == (prev_extent.e_lblk +
1514 prev_extent.e_len)) &&
1515 (physical == (prev_extent.e_pblk +
1516 prev_extent.e_len)) &&
1517 (new_uninit == prev_uninit) &&
1518 ((int) prev_extent.e_len < max_len-1)) {
1519 retval = ext2fs_extent_get(handle,
1520 EXT2_EXTENT_PREV_LEAF, &prev_extent);
1521 if (retval)
1522 goto done;
1523 prev_extent.e_len++;
1524 retval = ext2fs_extent_replace(handle, 0,
1525 &prev_extent);
1526 } else
1527 retval = ext2fs_extent_insert(handle,
1528 0, &newextent);
1529 if (retval)
1530 goto done;
1531 retval = ext2fs_extent_fix_parents(handle);
1532 if (retval)
1533 goto done;
1534 retval = ext2fs_extent_get(handle,
1535 EXT2_EXTENT_NEXT_LEAF,
1536 &extent);
1537 if (retval)
1538 goto done;
1539 }
1540 extent.e_pblk++;
1541 extent.e_lblk++;
1542 extent.e_len--;
1543 retval = ext2fs_extent_replace(handle, 0, &extent);
1544 if (retval)
1545 goto done;
1546 retval = ext2fs_extent_fix_parents(handle);
1547 if (retval)
1548 goto done;
1549 } else {
1550 __u32 save_length;
1551 blk64_t save_lblk;
1552 struct ext2fs_extent save_extent;
1553 errcode_t r2;
1554
1555 #ifdef DEBUG
1556 printf("(re/un)mapping in middle of extent\n");
1557 #endif
1558 /* need to split this extent; later */
1559 save_lblk = extent.e_lblk;
1560 save_length = extent.e_len;
1561 save_extent = extent;
1562
1563 /* shorten pre-split extent */
1564 extent.e_len = (logical - extent.e_lblk);
1565 retval = ext2fs_extent_replace(handle, 0, &extent);
1566 if (retval)
1567 goto done;
1568 /* insert our new extent, if any */
1569 if (physical) {
1570 /* insert new extent after current */
1571 retval = ext2fs_extent_insert(handle,
1572 EXT2_EXTENT_INSERT_AFTER, &newextent);
1573 if (retval) {
1574 r2 = ext2fs_extent_goto(handle, save_lblk);
1575 if (r2 == 0)
1576 (void)ext2fs_extent_replace(handle, 0,
1577 &save_extent);
1578 goto done;
1579 }
1580 }
1581 /* add post-split extent */
1582 extent.e_pblk += extent.e_len + 1;
1583 extent.e_lblk += extent.e_len + 1;
1584 extent.e_len = save_length - extent.e_len - 1;
1585 retval = ext2fs_extent_insert(handle,
1586 EXT2_EXTENT_INSERT_AFTER, &extent);
1587 if (retval) {
1588 if (physical) {
1589 r2 = ext2fs_extent_goto(handle,
1590 newextent.e_lblk);
1591 if (r2 == 0)
1592 (void)ext2fs_extent_delete(handle, 0);
1593 }
1594 r2 = ext2fs_extent_goto(handle, save_lblk);
1595 if (r2 == 0)
1596 (void)ext2fs_extent_replace(handle, 0,
1597 &save_extent);
1598 goto done;
1599 }
1600 }
1601
1602 done:
1603 /* get handle back to its position */
1604 if (orig_height > handle->max_depth)
1605 orig_height = handle->max_depth; /* In case we shortened the tree */
1606 ext2fs_extent_goto2(handle, orig_height, orig_lblk);
1607 return retval;
1608 }
1609
ext2fs_extent_delete(ext2_extent_handle_t handle,int flags)1610 errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags)
1611 {
1612 struct extent_path *path;
1613 char *cp;
1614 struct ext3_extent_header *eh;
1615 errcode_t retval = 0;
1616
1617 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1618
1619 if (!(handle->fs->flags & EXT2_FLAG_RW))
1620 return EXT2_ET_RO_FILSYS;
1621
1622 if (!handle->path)
1623 return EXT2_ET_NO_CURRENT_NODE;
1624
1625 #ifdef DEBUG
1626 {
1627 struct ext2fs_extent extent;
1628
1629 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
1630 &extent);
1631 if (retval == 0) {
1632 printf("extent delete %u ", handle->ino);
1633 dbg_print_extent(0, &extent);
1634 }
1635 }
1636 #endif
1637
1638 path = handle->path + handle->level;
1639 if (!path->curr)
1640 return EXT2_ET_NO_CURRENT_NODE;
1641
1642 cp = path->curr;
1643
1644 /* Sanity check before memmove() */
1645 if (path->left < 0)
1646 return EXT2_ET_EXTENT_LEAF_BAD;
1647
1648 if (path->left) {
1649 memmove(cp, cp + sizeof(struct ext3_extent_idx),
1650 path->left * sizeof(struct ext3_extent_idx));
1651 path->left--;
1652 } else {
1653 struct ext3_extent_idx *ix = path->curr;
1654 ix--;
1655 path->curr = ix;
1656 }
1657 if (--path->entries == 0)
1658 path->curr = 0;
1659
1660 /* if non-root node has no entries left, remove it & parent ptr to it */
1661 if (path->entries == 0 && handle->level) {
1662 if (!(flags & EXT2_EXTENT_DELETE_KEEP_EMPTY)) {
1663 struct ext2fs_extent extent;
1664
1665 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP,
1666 &extent);
1667 if (retval)
1668 return retval;
1669
1670 retval = ext2fs_extent_delete(handle, flags);
1671 handle->inode->i_blocks -=
1672 (handle->fs->blocksize *
1673 EXT2FS_CLUSTER_RATIO(handle->fs)) / 512;
1674 retval = ext2fs_write_inode(handle->fs, handle->ino,
1675 handle->inode);
1676 ext2fs_block_alloc_stats2(handle->fs,
1677 extent.e_pblk, -1);
1678 }
1679 } else {
1680 eh = (struct ext3_extent_header *) path->buf;
1681 eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
1682 if ((path->entries == 0) && (handle->level == 0)) {
1683 eh->eh_depth = 0;
1684 handle->max_depth = 0;
1685 }
1686 retval = update_path(handle);
1687 }
1688 return retval;
1689 }
1690
ext2fs_extent_get_info(ext2_extent_handle_t handle,struct ext2_extent_info * info)1691 errcode_t ext2fs_extent_get_info(ext2_extent_handle_t handle,
1692 struct ext2_extent_info *info)
1693 {
1694 struct extent_path *path;
1695
1696 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1697
1698 memset(info, 0, sizeof(struct ext2_extent_info));
1699
1700 path = handle->path + handle->level;
1701 if (path) {
1702 if (path->curr)
1703 info->curr_entry = ((char *) path->curr - path->buf) /
1704 sizeof(struct ext3_extent_idx);
1705 else
1706 info->curr_entry = 0;
1707 info->num_entries = path->entries;
1708 info->max_entries = path->max_entries;
1709 info->bytes_avail = (path->max_entries - path->entries) *
1710 sizeof(struct ext3_extent);
1711 }
1712
1713 info->curr_level = handle->level;
1714 info->max_depth = handle->max_depth;
1715 info->max_lblk = EXT_MAX_EXTENT_LBLK;
1716 info->max_pblk = EXT_MAX_EXTENT_PBLK;
1717 info->max_len = EXT_INIT_MAX_LEN;
1718 info->max_uninit_len = EXT_UNINIT_MAX_LEN;
1719
1720 return 0;
1721 }
1722
ul_log2(unsigned long arg)1723 static int ul_log2(unsigned long arg)
1724 {
1725 int l = 0;
1726
1727 arg >>= 1;
1728 while (arg) {
1729 l++;
1730 arg >>= 1;
1731 }
1732 return l;
1733 }
1734
ext2fs_max_extent_depth(ext2_extent_handle_t handle)1735 size_t ext2fs_max_extent_depth(ext2_extent_handle_t handle)
1736 {
1737 size_t iblock_sz = sizeof(((struct ext2_inode *)NULL)->i_block);
1738 size_t iblock_extents = (iblock_sz - sizeof(struct ext3_extent_header)) /
1739 sizeof(struct ext3_extent);
1740 size_t extents_per_block = (handle->fs->blocksize -
1741 sizeof(struct ext3_extent_header)) /
1742 sizeof(struct ext3_extent);
1743 static unsigned int last_blocksize = 0;
1744 static size_t last_result = 0;
1745
1746 if (last_blocksize && last_blocksize == handle->fs->blocksize)
1747 return last_result;
1748
1749 last_result = 1 + ((ul_log2(EXT_MAX_EXTENT_LBLK) - ul_log2(iblock_extents)) /
1750 ul_log2(extents_per_block));
1751 last_blocksize = handle->fs->blocksize;
1752 return last_result;
1753 }
1754
ext2fs_fix_extents_checksums(ext2_filsys fs,ext2_ino_t ino,struct ext2_inode * inode)1755 errcode_t ext2fs_fix_extents_checksums(ext2_filsys fs, ext2_ino_t ino,
1756 struct ext2_inode *inode)
1757 {
1758 ext2_extent_handle_t handle;
1759 struct ext2fs_extent extent;
1760 errcode_t errcode;
1761 int save_flags = fs->flags;
1762
1763 if (!ext2fs_has_feature_metadata_csum(fs->super) ||
1764 (inode && !(inode->i_flags & EXT4_EXTENTS_FL)))
1765 return 0;
1766
1767 errcode = ext2fs_extent_open2(fs, ino, inode, &handle);
1768 if (errcode) {
1769 if (errcode == EXT2_ET_INODE_NOT_EXTENT)
1770 errcode = 0;
1771 return errcode;
1772 }
1773
1774 fs->flags &= ~EXT2_FLAG_IGNORE_CSUM_ERRORS;
1775 errcode = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent);
1776 if (errcode)
1777 goto out;
1778
1779 do {
1780 /* Skip to the end of a block of leaf nodes */
1781 if (extent.e_flags & EXT2_EXTENT_FLAGS_LEAF) {
1782 errcode = ext2fs_extent_get(handle,
1783 EXT2_EXTENT_LAST_SIB,
1784 &extent);
1785 if (errcode)
1786 break;
1787 }
1788
1789 errcode = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT, &extent);
1790 if (errcode == EXT2_ET_EXTENT_CSUM_INVALID)
1791 errcode = update_path(handle);
1792 } while (errcode == 0);
1793
1794 out:
1795 /* Ok if we run off the end */
1796 if (errcode == EXT2_ET_EXTENT_NO_NEXT)
1797 errcode = 0;
1798 ext2fs_extent_free(handle);
1799 fs->flags = save_flags;
1800 return errcode;
1801 }
1802
ext2fs_decode_extent(struct ext2fs_extent * to,void * addr,int len)1803 errcode_t ext2fs_decode_extent(struct ext2fs_extent *to, void *addr, int len)
1804 {
1805 struct ext3_extent *from = (struct ext3_extent *)addr;
1806
1807 if (len != sizeof(struct ext3_extent))
1808 return EXT2_ET_INVALID_ARGUMENT;
1809
1810 to->e_pblk = ext2fs_le32_to_cpu(from->ee_start) +
1811 ((__u64) ext2fs_le16_to_cpu(from->ee_start_hi)
1812 << 32);
1813 to->e_lblk = ext2fs_le32_to_cpu(from->ee_block);
1814 to->e_len = ext2fs_le16_to_cpu(from->ee_len);
1815 to->e_flags = EXT2_EXTENT_FLAGS_LEAF;
1816 if (to->e_len > EXT_INIT_MAX_LEN) {
1817 to->e_len -= EXT_INIT_MAX_LEN;
1818 to->e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
1819 }
1820
1821 return 0;
1822 }
1823
ext2fs_count_blocks(ext2_filsys fs,ext2_ino_t ino,struct ext2_inode * inode,blk64_t * ret_count)1824 errcode_t ext2fs_count_blocks(ext2_filsys fs, ext2_ino_t ino,
1825 struct ext2_inode *inode, blk64_t *ret_count)
1826 {
1827 ext2_extent_handle_t handle = NULL;
1828 struct ext2fs_extent extent;
1829 errcode_t errcode;
1830 int i;
1831 blk64_t blkcount = 0;
1832 blk64_t *intermediate_nodes;
1833
1834 errcode = ext2fs_extent_open2(fs, ino, inode, &handle);
1835 if (errcode)
1836 goto out;
1837
1838 errcode = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent);
1839 if (errcode)
1840 goto out;
1841
1842 errcode = ext2fs_get_array(handle->max_depth, sizeof(blk64_t),
1843 &intermediate_nodes);
1844 if (errcode)
1845 goto out;
1846
1847 blkcount = handle->level;
1848 while (!errcode) {
1849 if (extent.e_flags & EXT2_EXTENT_FLAGS_LEAF) {
1850 blkcount += extent.e_len;
1851 for (i = 0; i < handle->level; i++) {
1852 if (intermediate_nodes[i] !=
1853 handle->path[i].end_blk) {
1854 blkcount++;
1855 intermediate_nodes[i] =
1856 handle->path[i].end_blk;
1857 }
1858 }
1859 }
1860 errcode = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT, &extent);
1861 }
1862 ext2fs_free_mem(&intermediate_nodes);
1863 out:
1864 *ret_count = blkcount;
1865 ext2fs_extent_free(handle);
1866
1867 return 0;
1868 }
1869
1870 #ifdef DEBUG
1871 /*
1872 * Override debugfs's prompt
1873 */
1874 const char *debug_prog_name = "tst_extents";
1875
1876 #endif
1877
1878