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