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 <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 struct ext2_inode inodebuf;
57 int type;
58 int level;
59 int max_depth;
60 struct extent_path *path;
61 };
62
63 struct ext2_extent_path {
64 errcode_t magic;
65 int leaf_height;
66 blk64_t lblk;
67 };
68
69 /*
70 * Useful Debugging stuff
71 */
72
73 #ifdef DEBUG
dbg_show_header(struct ext3_extent_header * eh)74 static void dbg_show_header(struct ext3_extent_header *eh)
75 {
76 printf("header: magic=%x entries=%u max=%u depth=%u generation=%u\n",
77 ext2fs_le16_to_cpu(eh->eh_magic),
78 ext2fs_le16_to_cpu(eh->eh_entries),
79 ext2fs_le16_to_cpu(eh->eh_max),
80 ext2fs_le16_to_cpu(eh->eh_depth),
81 ext2fs_le32_to_cpu(eh->eh_generation));
82 }
83
dbg_show_index(struct ext3_extent_idx * ix)84 static void dbg_show_index(struct ext3_extent_idx *ix)
85 {
86 printf("index: block=%u leaf=%u leaf_hi=%u unused=%u\n",
87 ext2fs_le32_to_cpu(ix->ei_block),
88 ext2fs_le32_to_cpu(ix->ei_leaf),
89 ext2fs_le16_to_cpu(ix->ei_leaf_hi),
90 ext2fs_le16_to_cpu(ix->ei_unused));
91 }
92
dbg_show_extent(struct ext3_extent * ex)93 static void dbg_show_extent(struct ext3_extent *ex)
94 {
95 printf("extent: block=%u-%u len=%u start=%u start_hi=%u\n",
96 ext2fs_le32_to_cpu(ex->ee_block),
97 ext2fs_le32_to_cpu(ex->ee_block) +
98 ext2fs_le16_to_cpu(ex->ee_len) - 1,
99 ext2fs_le16_to_cpu(ex->ee_len),
100 ext2fs_le32_to_cpu(ex->ee_start),
101 ext2fs_le16_to_cpu(ex->ee_start_hi));
102 }
103
dbg_print_extent(char * desc,struct ext2fs_extent * extent)104 static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)
105 {
106 if (desc)
107 printf("%s: ", desc);
108 printf("extent: lblk %llu--%llu, len %u, pblk %llu, flags: ",
109 extent->e_lblk, extent->e_lblk + extent->e_len - 1,
110 extent->e_len, extent->e_pblk);
111 if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF)
112 fputs("LEAF ", stdout);
113 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT)
114 fputs("UNINIT ", stdout);
115 if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT)
116 fputs("2ND_VISIT ", stdout);
117 if (!extent->e_flags)
118 fputs("(none)", stdout);
119 fputc('\n', stdout);
120
121 }
122
123 #else
124 #define dbg_show_header(eh) do { } while (0)
125 #define dbg_show_index(ix) do { } while (0)
126 #define dbg_show_extent(ex) do { } while (0)
127 #define dbg_print_extent(desc, ex) do { } while (0)
128 #endif
129
130 /*
131 * Verify the extent header as being sane
132 */
ext2fs_extent_header_verify(void * ptr,int size)133 errcode_t ext2fs_extent_header_verify(void *ptr, int size)
134 {
135 int eh_max, entry_size;
136 struct ext3_extent_header *eh = ptr;
137
138 dbg_show_header(eh);
139 if (ext2fs_le16_to_cpu(eh->eh_magic) != EXT3_EXT_MAGIC)
140 return EXT2_ET_EXTENT_HEADER_BAD;
141 if (ext2fs_le16_to_cpu(eh->eh_entries) > ext2fs_le16_to_cpu(eh->eh_max))
142 return EXT2_ET_EXTENT_HEADER_BAD;
143 if (eh->eh_depth == 0)
144 entry_size = sizeof(struct ext3_extent);
145 else
146 entry_size = sizeof(struct ext3_extent_idx);
147
148 eh_max = (size - sizeof(*eh)) / entry_size;
149 /* Allow two extent-sized items at the end of the block, for
150 * ext4_extent_tail with checksum in the future. */
151 if ((ext2fs_le16_to_cpu(eh->eh_max) > eh_max) ||
152 (ext2fs_le16_to_cpu(eh->eh_max) < (eh_max - 2)))
153 return EXT2_ET_EXTENT_HEADER_BAD;
154
155 return 0;
156 }
157
158
159 /*
160 * Begin functions to handle an inode's extent information
161 */
ext2fs_extent_free(ext2_extent_handle_t handle)162 void ext2fs_extent_free(ext2_extent_handle_t handle)
163 {
164 int i;
165
166 if (!handle)
167 return;
168
169 if (handle->path) {
170 for (i=1; i <= handle->max_depth; i++) {
171 if (handle->path[i].buf)
172 ext2fs_free_mem(&handle->path[i].buf);
173 }
174 ext2fs_free_mem(&handle->path);
175 }
176 ext2fs_free_mem(&handle);
177 }
178
ext2fs_extent_open(ext2_filsys fs,ext2_ino_t ino,ext2_extent_handle_t * ret_handle)179 errcode_t ext2fs_extent_open(ext2_filsys fs, ext2_ino_t ino,
180 ext2_extent_handle_t *ret_handle)
181 {
182 return ext2fs_extent_open2(fs, ino, NULL, ret_handle);
183 }
184
ext2fs_extent_open2(ext2_filsys fs,ext2_ino_t ino,struct ext2_inode * inode,ext2_extent_handle_t * ret_handle)185 errcode_t ext2fs_extent_open2(ext2_filsys fs, ext2_ino_t ino,
186 struct ext2_inode *inode,
187 ext2_extent_handle_t *ret_handle)
188 {
189 struct ext2_extent_handle *handle;
190 errcode_t retval;
191 int i;
192 struct ext3_extent_header *eh;
193
194 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
195
196 if (!inode)
197 if ((ino == 0) || (ino > fs->super->s_inodes_count))
198 return EXT2_ET_BAD_INODE_NUM;
199
200 retval = ext2fs_get_mem(sizeof(struct ext2_extent_handle), &handle);
201 if (retval)
202 return retval;
203 memset(handle, 0, sizeof(struct ext2_extent_handle));
204
205 handle->ino = ino;
206 handle->fs = fs;
207
208 if (inode) {
209 handle->inode = inode;
210 } else {
211 handle->inode = &handle->inodebuf;
212 retval = ext2fs_read_inode(fs, ino, handle->inode);
213 if (retval)
214 goto errout;
215 }
216
217 eh = (struct ext3_extent_header *) &handle->inode->i_block[0];
218
219 for (i=0; i < EXT2_N_BLOCKS; i++)
220 if (handle->inode->i_block[i])
221 break;
222 if (i >= EXT2_N_BLOCKS) {
223 eh->eh_magic = ext2fs_cpu_to_le16(EXT3_EXT_MAGIC);
224 eh->eh_depth = 0;
225 eh->eh_entries = 0;
226 i = (sizeof(handle->inode->i_block) - sizeof(*eh)) /
227 sizeof(struct ext3_extent);
228 eh->eh_max = ext2fs_cpu_to_le16(i);
229 handle->inode->i_flags |= EXT4_EXTENTS_FL;
230 }
231
232 if (!(handle->inode->i_flags & EXT4_EXTENTS_FL)) {
233 retval = EXT2_ET_INODE_NOT_EXTENT;
234 goto errout;
235 }
236
237 retval = ext2fs_extent_header_verify(eh, sizeof(handle->inode->i_block));
238 if (retval)
239 goto errout;
240
241 handle->max_depth = ext2fs_le16_to_cpu(eh->eh_depth);
242 handle->type = ext2fs_le16_to_cpu(eh->eh_magic);
243
244 retval = ext2fs_get_mem(((handle->max_depth+1) *
245 sizeof(struct extent_path)),
246 &handle->path);
247 memset(handle->path, 0,
248 (handle->max_depth+1) * sizeof(struct extent_path));
249 handle->path[0].buf = (char *) handle->inode->i_block;
250
251 handle->path[0].left = handle->path[0].entries =
252 ext2fs_le16_to_cpu(eh->eh_entries);
253 handle->path[0].max_entries = ext2fs_le16_to_cpu(eh->eh_max);
254 handle->path[0].curr = 0;
255 handle->path[0].end_blk =
256 (EXT2_I_SIZE(handle->inode) + fs->blocksize - 1) >>
257 EXT2_BLOCK_SIZE_BITS(fs->super);
258 handle->path[0].visit_num = 1;
259 handle->level = 0;
260 handle->magic = EXT2_ET_MAGIC_EXTENT_HANDLE;
261
262 *ret_handle = handle;
263 return 0;
264
265 errout:
266 ext2fs_extent_free(handle);
267 return retval;
268 }
269
270 /*
271 * This function is responsible for (optionally) moving through the
272 * extent tree and then returning the current extent
273 */
ext2fs_extent_get(ext2_extent_handle_t handle,int flags,struct ext2fs_extent * extent)274 errcode_t ext2fs_extent_get(ext2_extent_handle_t handle,
275 int flags, struct ext2fs_extent *extent)
276 {
277 struct extent_path *path, *newpath;
278 struct ext3_extent_header *eh;
279 struct ext3_extent_idx *ix = 0;
280 struct ext3_extent *ex;
281 errcode_t retval;
282 blk64_t blk;
283 blk64_t end_blk;
284 int orig_op, op;
285
286 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
287
288 if (!handle->path)
289 return EXT2_ET_NO_CURRENT_NODE;
290
291 orig_op = op = flags & EXT2_EXTENT_MOVE_MASK;
292
293 retry:
294 path = handle->path + handle->level;
295 if ((orig_op == EXT2_EXTENT_NEXT) ||
296 (orig_op == EXT2_EXTENT_NEXT_LEAF)) {
297 if (handle->level < handle->max_depth) {
298 /* interior node */
299 if (path->visit_num == 0) {
300 path->visit_num++;
301 op = EXT2_EXTENT_DOWN;
302 } else if (path->left > 0)
303 op = EXT2_EXTENT_NEXT_SIB;
304 else if (handle->level > 0)
305 op = EXT2_EXTENT_UP;
306 else
307 return EXT2_ET_EXTENT_NO_NEXT;
308 } else {
309 /* leaf node */
310 if (path->left > 0)
311 op = EXT2_EXTENT_NEXT_SIB;
312 else if (handle->level > 0)
313 op = EXT2_EXTENT_UP;
314 else
315 return EXT2_ET_EXTENT_NO_NEXT;
316 }
317 if (op != EXT2_EXTENT_NEXT_SIB) {
318 #ifdef DEBUG_GET_EXTENT
319 printf("<<<< OP = %s\n",
320 (op == EXT2_EXTENT_DOWN) ? "down" :
321 ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));
322 #endif
323 }
324 }
325
326 if ((orig_op == EXT2_EXTENT_PREV) ||
327 (orig_op == EXT2_EXTENT_PREV_LEAF)) {
328 if (handle->level < handle->max_depth) {
329 /* interior node */
330 if (path->visit_num > 0 ) {
331 /* path->visit_num = 0; */
332 op = EXT2_EXTENT_DOWN_AND_LAST;
333 } else if (path->left < path->entries-1)
334 op = EXT2_EXTENT_PREV_SIB;
335 else if (handle->level > 0)
336 op = EXT2_EXTENT_UP;
337 else
338 return EXT2_ET_EXTENT_NO_PREV;
339 } else {
340 /* leaf node */
341 if (path->left < path->entries-1)
342 op = EXT2_EXTENT_PREV_SIB;
343 else if (handle->level > 0)
344 op = EXT2_EXTENT_UP;
345 else
346 return EXT2_ET_EXTENT_NO_PREV;
347 }
348 if (op != EXT2_EXTENT_PREV_SIB) {
349 #ifdef DEBUG_GET_EXTENT
350 printf("<<<< OP = %s\n",
351 (op == EXT2_EXTENT_DOWN_AND_LAST) ? "down/last" :
352 ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));
353 #endif
354 }
355 }
356
357 if (orig_op == EXT2_EXTENT_LAST_LEAF) {
358 if ((handle->level < handle->max_depth) &&
359 (path->left == 0))
360 op = EXT2_EXTENT_DOWN;
361 else
362 op = EXT2_EXTENT_LAST_SIB;
363 #ifdef DEBUG_GET_EXTENT
364 printf("<<<< OP = %s\n",
365 (op == EXT2_EXTENT_DOWN) ? "down" : "last_sib");
366 #endif
367 }
368
369 switch (op) {
370 case EXT2_EXTENT_CURRENT:
371 ix = path->curr;
372 break;
373 case EXT2_EXTENT_ROOT:
374 handle->level = 0;
375 path = handle->path + handle->level;
376 /* fallthrough */
377 case EXT2_EXTENT_FIRST_SIB:
378 path->left = path->entries;
379 path->curr = 0;
380 /* fallthrough */
381 case EXT2_EXTENT_NEXT_SIB:
382 if (path->left <= 0)
383 return EXT2_ET_EXTENT_NO_NEXT;
384 if (path->curr) {
385 ix = path->curr;
386 ix++;
387 } else {
388 eh = (struct ext3_extent_header *) path->buf;
389 ix = EXT_FIRST_INDEX(eh);
390 }
391 path->left--;
392 path->curr = ix;
393 path->visit_num = 0;
394 break;
395 case EXT2_EXTENT_PREV_SIB:
396 if (!path->curr ||
397 path->left+1 >= path->entries)
398 return EXT2_ET_EXTENT_NO_PREV;
399 ix = path->curr;
400 ix--;
401 path->curr = ix;
402 path->left++;
403 if (handle->level < handle->max_depth)
404 path->visit_num = 1;
405 break;
406 case EXT2_EXTENT_LAST_SIB:
407 eh = (struct ext3_extent_header *) path->buf;
408 path->curr = EXT_LAST_EXTENT(eh);
409 ix = path->curr;
410 path->left = 0;
411 path->visit_num = 0;
412 break;
413 case EXT2_EXTENT_UP:
414 if (handle->level <= 0)
415 return EXT2_ET_EXTENT_NO_UP;
416 handle->level--;
417 path--;
418 ix = path->curr;
419 if ((orig_op == EXT2_EXTENT_PREV) ||
420 (orig_op == EXT2_EXTENT_PREV_LEAF))
421 path->visit_num = 0;
422 break;
423 case EXT2_EXTENT_DOWN:
424 case EXT2_EXTENT_DOWN_AND_LAST:
425 if (!path->curr ||(handle->level >= handle->max_depth))
426 return EXT2_ET_EXTENT_NO_DOWN;
427
428 ix = path->curr;
429 newpath = path + 1;
430 if (!newpath->buf) {
431 retval = ext2fs_get_mem(handle->fs->blocksize,
432 &newpath->buf);
433 if (retval)
434 return retval;
435 }
436 blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
437 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
438 if ((handle->fs->flags & EXT2_FLAG_IMAGE_FILE) &&
439 (handle->fs->io != handle->fs->image_io))
440 memset(newpath->buf, 0, handle->fs->blocksize);
441 else {
442 retval = io_channel_read_blk64(handle->fs->io,
443 blk, 1, newpath->buf);
444 if (retval)
445 return retval;
446 }
447 handle->level++;
448
449 eh = (struct ext3_extent_header *) newpath->buf;
450
451 retval = ext2fs_extent_header_verify(eh, handle->fs->blocksize);
452 if (retval) {
453 handle->level--;
454 return retval;
455 }
456
457 newpath->left = newpath->entries =
458 ext2fs_le16_to_cpu(eh->eh_entries);
459 newpath->max_entries = ext2fs_le16_to_cpu(eh->eh_max);
460
461 if (path->left > 0) {
462 ix++;
463 newpath->end_blk = ext2fs_le32_to_cpu(ix->ei_block);
464 } else
465 newpath->end_blk = path->end_blk;
466
467 path = newpath;
468 if (op == EXT2_EXTENT_DOWN) {
469 ix = EXT_FIRST_INDEX((struct ext3_extent_header *) eh);
470 path->curr = ix;
471 path->left = path->entries - 1;
472 path->visit_num = 0;
473 } else {
474 ix = EXT_LAST_INDEX((struct ext3_extent_header *) eh);
475 path->curr = ix;
476 path->left = 0;
477 if (handle->level < handle->max_depth)
478 path->visit_num = 1;
479 }
480 #ifdef DEBUG_GET_EXTENT
481 printf("Down to level %d/%d, end_blk=%llu\n",
482 handle->level, handle->max_depth,
483 path->end_blk);
484 #endif
485 break;
486 default:
487 return EXT2_ET_OP_NOT_SUPPORTED;
488 }
489
490 if (!ix)
491 return EXT2_ET_NO_CURRENT_NODE;
492
493 extent->e_flags = 0;
494 #ifdef DEBUG_GET_EXTENT
495 printf("(Left %d)\n", path->left);
496 #endif
497
498 if (handle->level == handle->max_depth) {
499 ex = (struct ext3_extent *) ix;
500
501 extent->e_pblk = ext2fs_le32_to_cpu(ex->ee_start) +
502 ((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32);
503 extent->e_lblk = ext2fs_le32_to_cpu(ex->ee_block);
504 extent->e_len = ext2fs_le16_to_cpu(ex->ee_len);
505 extent->e_flags |= EXT2_EXTENT_FLAGS_LEAF;
506 if (extent->e_len > EXT_INIT_MAX_LEN) {
507 extent->e_len -= EXT_INIT_MAX_LEN;
508 extent->e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
509 }
510 } else {
511 extent->e_pblk = ext2fs_le32_to_cpu(ix->ei_leaf) +
512 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
513 extent->e_lblk = ext2fs_le32_to_cpu(ix->ei_block);
514 if (path->left > 0) {
515 ix++;
516 end_blk = ext2fs_le32_to_cpu(ix->ei_block);
517 } else
518 end_blk = path->end_blk;
519
520 extent->e_len = end_blk - extent->e_lblk;
521 }
522 if (path->visit_num)
523 extent->e_flags |= EXT2_EXTENT_FLAGS_SECOND_VISIT;
524
525 if (((orig_op == EXT2_EXTENT_NEXT_LEAF) ||
526 (orig_op == EXT2_EXTENT_PREV_LEAF)) &&
527 (handle->level != handle->max_depth))
528 goto retry;
529
530 if ((orig_op == EXT2_EXTENT_LAST_LEAF) &&
531 ((handle->level != handle->max_depth) ||
532 (path->left != 0)))
533 goto retry;
534
535 return 0;
536 }
537
update_path(ext2_extent_handle_t handle)538 static errcode_t update_path(ext2_extent_handle_t handle)
539 {
540 blk64_t blk;
541 errcode_t retval;
542 struct ext3_extent_idx *ix;
543
544 if (handle->level == 0) {
545 retval = ext2fs_write_inode(handle->fs, handle->ino,
546 handle->inode);
547 } else {
548 ix = handle->path[handle->level - 1].curr;
549 blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
550 ((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
551
552 retval = io_channel_write_blk64(handle->fs->io,
553 blk, 1, handle->path[handle->level].buf);
554 }
555 return retval;
556 }
557
558 #if 0
559 errcode_t ext2fs_extent_save_path(ext2_extent_handle_t handle,
560 ext2_extent_path_t *ret_path)
561 {
562 ext2_extent_path_t save_path;
563 struct ext2fs_extent extent;
564 struct ext2_extent_info info;
565 errcode_t retval;
566
567 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
568 if (retval)
569 return retval;
570
571 retval = ext2fs_extent_get_info(handle, &info);
572 if (retval)
573 return retval;
574
575 retval = ext2fs_get_mem(sizeof(struct ext2_extent_path), &save_path);
576 if (retval)
577 return retval;
578 memset(save_path, 0, sizeof(struct ext2_extent_path));
579
580 save_path->magic = EXT2_ET_MAGIC_EXTENT_PATH;
581 save_path->leaf_height = info.max_depth - info.curr_level - 1;
582 save_path->lblk = extent.e_lblk;
583
584 *ret_path = save_path;
585 return 0;
586 }
587
588 errcode_t ext2fs_extent_free_path(ext2_extent_path_t path)
589 {
590 EXT2_CHECK_MAGIC(path, EXT2_ET_MAGIC_EXTENT_PATH);
591
592 ext2fs_free_mem(&path);
593 return 0;
594 }
595 #endif
596
597 /*
598 * Go to the node at leaf_level which contains logical block blk.
599 *
600 * leaf_level is height from the leaf node level, i.e.
601 * leaf_level 0 is at leaf node, leaf_level 1 is 1 above etc.
602 *
603 * If "blk" has no mapping (hole) then handle is left at last
604 * extent before blk.
605 */
ext2fs_extent_goto2(ext2_extent_handle_t handle,int leaf_level,blk64_t blk)606 errcode_t ext2fs_extent_goto2(ext2_extent_handle_t handle,
607 int leaf_level, blk64_t blk)
608 {
609 struct ext2fs_extent extent;
610 errcode_t retval;
611
612 retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent);
613 if (retval) {
614 if (retval == EXT2_ET_EXTENT_NO_NEXT)
615 retval = EXT2_ET_EXTENT_NOT_FOUND;
616 return retval;
617 }
618
619 if (leaf_level > handle->max_depth) {
620 #ifdef DEBUG
621 printf("leaf level %d greater than tree depth %d\n",
622 leaf_level, handle->max_depth);
623 #endif
624 return EXT2_ET_OP_NOT_SUPPORTED;
625 }
626
627 #ifdef DEBUG
628 printf("goto extent ino %u, level %d, %llu\n", handle->ino,
629 leaf_level, blk);
630 #endif
631
632 #ifdef DEBUG_GOTO_EXTENTS
633 dbg_print_extent("root", &extent);
634 #endif
635 while (1) {
636 if (handle->max_depth - handle->level == leaf_level) {
637 /* block is in this &extent */
638 if ((blk >= extent.e_lblk) &&
639 (blk < extent.e_lblk + extent.e_len))
640 return 0;
641 if (blk < extent.e_lblk) {
642 retval = ext2fs_extent_get(handle,
643 EXT2_EXTENT_PREV_SIB,
644 &extent);
645 return EXT2_ET_EXTENT_NOT_FOUND;
646 }
647 retval = ext2fs_extent_get(handle,
648 EXT2_EXTENT_NEXT_SIB,
649 &extent);
650 if (retval == EXT2_ET_EXTENT_NO_NEXT)
651 return EXT2_ET_EXTENT_NOT_FOUND;
652 if (retval)
653 return retval;
654 continue;
655 }
656
657 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_SIB,
658 &extent);
659 if (retval == EXT2_ET_EXTENT_NO_NEXT)
660 goto go_down;
661 if (retval)
662 return retval;
663
664 #ifdef DEBUG_GOTO_EXTENTS
665 dbg_print_extent("next", &extent);
666 #endif
667 if (blk == extent.e_lblk)
668 goto go_down;
669 if (blk > extent.e_lblk)
670 continue;
671
672 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_SIB,
673 &extent);
674 if (retval)
675 return retval;
676
677 #ifdef DEBUG_GOTO_EXTENTS
678 dbg_print_extent("prev", &extent);
679 #endif
680
681 go_down:
682 retval = ext2fs_extent_get(handle, EXT2_EXTENT_DOWN,
683 &extent);
684 if (retval)
685 return retval;
686
687 #ifdef DEBUG_GOTO_EXTENTS
688 dbg_print_extent("down", &extent);
689 #endif
690 }
691 }
692
ext2fs_extent_goto(ext2_extent_handle_t handle,blk64_t blk)693 errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle,
694 blk64_t blk)
695 {
696 return ext2fs_extent_goto2(handle, 0, blk);
697 }
698
699 /*
700 * Traverse back up to root fixing parents of current node as needed.
701 *
702 * If we changed start of first entry in a node, fix parent index start
703 * and so on.
704 *
705 * Safe to call for any position in node; if not at the first entry,
706 * will simply return.
707 */
ext2fs_extent_fix_parents(ext2_extent_handle_t handle)708 errcode_t ext2fs_extent_fix_parents(ext2_extent_handle_t handle)
709 {
710 int retval = 0;
711 int orig_height;
712 blk64_t start;
713 struct extent_path *path;
714 struct ext2fs_extent extent;
715 struct ext2_extent_info info;
716
717 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
718
719 if (!(handle->fs->flags & EXT2_FLAG_RW))
720 return EXT2_ET_RO_FILSYS;
721
722 if (!handle->path)
723 return EXT2_ET_NO_CURRENT_NODE;
724
725 path = handle->path + handle->level;
726 if (!path->curr)
727 return EXT2_ET_NO_CURRENT_NODE;
728
729 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
730 if (retval)
731 goto done;
732
733 /* modified node's start block */
734 start = extent.e_lblk;
735
736 if ((retval = ext2fs_extent_get_info(handle, &info)))
737 return retval;
738 orig_height = info.max_depth - info.curr_level;
739
740 /* traverse up until index not first, or startblk matches, or top */
741 while (handle->level > 0 &&
742 (path->left == path->entries - 1)) {
743 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
744 if (retval)
745 goto done;
746 if (extent.e_lblk == start)
747 break;
748 path = handle->path + handle->level;
749 extent.e_len += (extent.e_lblk - start);
750 extent.e_lblk = start;
751 retval = ext2fs_extent_replace(handle, 0, &extent);
752 if (retval)
753 goto done;
754 update_path(handle);
755 }
756
757 /* put handle back to where we started */
758 retval = ext2fs_extent_goto2(handle, orig_height, start);
759 done:
760 return retval;
761 }
762
ext2fs_extent_replace(ext2_extent_handle_t handle,int flags EXT2FS_ATTR ((unused)),struct ext2fs_extent * extent)763 errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle,
764 int flags EXT2FS_ATTR((unused)),
765 struct ext2fs_extent *extent)
766 {
767 struct extent_path *path;
768 struct ext3_extent_idx *ix;
769 struct ext3_extent *ex;
770
771 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
772
773 if (!(handle->fs->flags & EXT2_FLAG_RW))
774 return EXT2_ET_RO_FILSYS;
775
776 if (!handle->path)
777 return EXT2_ET_NO_CURRENT_NODE;
778
779 path = handle->path + handle->level;
780 if (!path->curr)
781 return EXT2_ET_NO_CURRENT_NODE;
782
783 #ifdef DEBUG
784 printf("extent replace: %u ", handle->ino);
785 dbg_print_extent(0, extent);
786 #endif
787
788 if (handle->level == handle->max_depth) {
789 ex = path->curr;
790
791 ex->ee_block = ext2fs_cpu_to_le32(extent->e_lblk);
792 ex->ee_start = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);
793 ex->ee_start_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);
794 if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) {
795 if (extent->e_len > EXT_UNINIT_MAX_LEN)
796 return EXT2_ET_EXTENT_INVALID_LENGTH;
797 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len +
798 EXT_INIT_MAX_LEN);
799 } else {
800 if (extent->e_len > EXT_INIT_MAX_LEN)
801 return EXT2_ET_EXTENT_INVALID_LENGTH;
802 ex->ee_len = ext2fs_cpu_to_le16(extent->e_len);
803 }
804 } else {
805 ix = path->curr;
806
807 ix->ei_leaf = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);
808 ix->ei_leaf_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);
809 ix->ei_block = ext2fs_cpu_to_le32(extent->e_lblk);
810 ix->ei_unused = 0;
811 }
812 update_path(handle);
813 return 0;
814 }
815
816 /*
817 * allocate a new block, move half the current node to it, and update parent
818 *
819 * handle will be left pointing at original record.
820 */
ext2fs_extent_node_split(ext2_extent_handle_t handle)821 errcode_t ext2fs_extent_node_split(ext2_extent_handle_t handle)
822 {
823 errcode_t retval = 0;
824 blk64_t new_node_pblk;
825 blk64_t new_node_start;
826 blk64_t orig_lblk;
827 blk64_t goal_blk = 0;
828 int orig_height;
829 char *block_buf = NULL;
830 struct ext2fs_extent extent;
831 struct extent_path *path, *newpath = 0;
832 struct ext3_extent_header *eh, *neweh;
833 int tocopy;
834 int new_root = 0;
835 struct ext2_extent_info info;
836
837 /* basic sanity */
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 #ifdef DEBUG
847 printf("splitting node at level %d\n", handle->level);
848 #endif
849 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
850 if (retval)
851 goto done;
852
853 retval = ext2fs_extent_get_info(handle, &info);
854 if (retval)
855 goto done;
856
857 /* save the position we were originally splitting... */
858 orig_height = info.max_depth - info.curr_level;
859 orig_lblk = extent.e_lblk;
860
861 /* Is there room in the parent for a new entry? */
862 if (handle->level &&
863 (handle->path[handle->level - 1].entries >=
864 handle->path[handle->level - 1].max_entries)) {
865
866 #ifdef DEBUG
867 printf("parent level %d full; splitting it too\n",
868 handle->level - 1);
869 #endif
870 /* split the parent */
871 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
872 if (retval)
873 goto done;
874 goal_blk = extent.e_pblk;
875
876 retval = ext2fs_extent_node_split(handle);
877 if (retval)
878 goto done;
879
880 /* get handle back to our original split position */
881 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk);
882 if (retval)
883 goto done;
884 }
885
886 /* At this point, parent should have room for this split */
887 path = handle->path + handle->level;
888 if (!path->curr)
889 return EXT2_ET_NO_CURRENT_NODE;
890
891 /* extent header of the current node we'll split */
892 eh = (struct ext3_extent_header *)path->buf;
893
894 /* splitting root level means moving them all out */
895 if (handle->level == 0) {
896 new_root = 1;
897 tocopy = ext2fs_le16_to_cpu(eh->eh_entries);
898 retval = ext2fs_get_mem(((handle->max_depth+2) *
899 sizeof(struct extent_path)),
900 &newpath);
901 if (retval)
902 goto done;
903 memset(newpath, 0,
904 ((handle->max_depth+2) * sizeof(struct extent_path)));
905 } else {
906 tocopy = ext2fs_le16_to_cpu(eh->eh_entries) / 2;
907 }
908
909 #ifdef DEBUG
910 printf("will copy out %d of %d entries at level %d\n",
911 tocopy, ext2fs_le16_to_cpu(eh->eh_entries),
912 handle->level);
913 #endif
914
915 if (!tocopy) {
916 #ifdef DEBUG
917 printf("Nothing to copy to new block!\n");
918 #endif
919 retval = EXT2_ET_CANT_SPLIT_EXTENT;
920 goto done;
921 }
922
923 /* first we need a new block, or can do nothing. */
924 block_buf = malloc(handle->fs->blocksize);
925 if (!block_buf) {
926 retval = ENOMEM;
927 goto done;
928 }
929
930 if (!goal_blk) {
931 dgrp_t group = ext2fs_group_of_ino(handle->fs, handle->ino);
932 __u8 log_flex = handle->fs->super->s_log_groups_per_flex;
933
934 if (log_flex)
935 group = group & ~((1 << (log_flex)) - 1);
936 goal_blk = ext2fs_group_first_block2(handle->fs, group);
937 }
938 retval = ext2fs_alloc_block2(handle->fs, goal_blk, block_buf,
939 &new_node_pblk);
940 if (retval)
941 goto done;
942
943 #ifdef DEBUG
944 printf("will copy to new node at block %lu\n",
945 (unsigned long) new_node_pblk);
946 #endif
947
948 /* Copy data into new block buffer */
949 /* First the header for the new block... */
950 neweh = (struct ext3_extent_header *) block_buf;
951 memcpy(neweh, eh, sizeof(struct ext3_extent_header));
952 neweh->eh_entries = ext2fs_cpu_to_le16(tocopy);
953 neweh->eh_max = ext2fs_cpu_to_le16((handle->fs->blocksize -
954 sizeof(struct ext3_extent_header)) /
955 sizeof(struct ext3_extent));
956
957 /* then the entries for the new block... */
958 memcpy(EXT_FIRST_INDEX(neweh),
959 EXT_FIRST_INDEX(eh) +
960 (ext2fs_le16_to_cpu(eh->eh_entries) - tocopy),
961 sizeof(struct ext3_extent_idx) * tocopy);
962
963 new_node_start = ext2fs_le32_to_cpu(EXT_FIRST_INDEX(neweh)->ei_block);
964
965 /* ...and write the new node block out to disk. */
966 retval = io_channel_write_blk64(handle->fs->io, new_node_pblk, 1,
967 block_buf);
968
969 if (retval)
970 goto done;
971
972 /* OK! we've created the new node; now adjust the tree */
973
974 /* current path now has fewer active entries, we copied some out */
975 if (handle->level == 0) {
976 memcpy(newpath, path,
977 sizeof(struct extent_path) * (handle->max_depth+1));
978 handle->path = newpath;
979 newpath = path;
980 path = handle->path;
981 path->entries = 1;
982 path->left = path->max_entries - 1;
983 handle->max_depth++;
984 eh->eh_depth = ext2fs_cpu_to_le16(handle->max_depth);
985 } else {
986 path->entries -= tocopy;
987 path->left -= tocopy;
988 }
989
990 eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
991 /* this writes out the node, incl. the modified header */
992 retval = update_path(handle);
993 if (retval)
994 goto done;
995
996 /* now go up and insert/replace index for new node we created */
997 if (new_root) {
998 retval = ext2fs_extent_get(handle, EXT2_EXTENT_FIRST_SIB, &extent);
999 if (retval)
1000 goto done;
1001
1002 extent.e_lblk = new_node_start;
1003 extent.e_pblk = new_node_pblk;
1004 extent.e_len = handle->path[0].end_blk - extent.e_lblk;
1005 retval = ext2fs_extent_replace(handle, 0, &extent);
1006 if (retval)
1007 goto done;
1008 } else {
1009 __u32 new_node_length;
1010
1011 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP, &extent);
1012 /* will insert after this one; it's length is shorter now */
1013 new_node_length = new_node_start - extent.e_lblk;
1014 extent.e_len -= new_node_length;
1015 retval = ext2fs_extent_replace(handle, 0, &extent);
1016 if (retval)
1017 goto done;
1018
1019 /* now set up the new extent and insert it */
1020 extent.e_lblk = new_node_start;
1021 extent.e_pblk = new_node_pblk;
1022 extent.e_len = new_node_length;
1023 retval = ext2fs_extent_insert(handle, EXT2_EXTENT_INSERT_AFTER, &extent);
1024 if (retval)
1025 goto done;
1026 }
1027
1028 /* get handle back to our original position */
1029 retval = ext2fs_extent_goto2(handle, orig_height, orig_lblk);
1030 if (retval)
1031 goto done;
1032
1033 /* new node hooked in, so update inode block count (do this here?) */
1034 handle->inode->i_blocks += (handle->fs->blocksize *
1035 EXT2FS_CLUSTER_RATIO(handle->fs)) / 512;
1036 retval = ext2fs_write_inode(handle->fs, handle->ino,
1037 handle->inode);
1038 if (retval)
1039 goto done;
1040
1041 done:
1042 if (newpath)
1043 ext2fs_free_mem(&newpath);
1044 free(block_buf);
1045
1046 return retval;
1047 }
1048
ext2fs_extent_insert(ext2_extent_handle_t handle,int flags,struct ext2fs_extent * extent)1049 errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
1050 struct ext2fs_extent *extent)
1051 {
1052 struct extent_path *path;
1053 struct ext3_extent_idx *ix;
1054 struct ext3_extent_header *eh;
1055 errcode_t retval;
1056
1057 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1058
1059 if (!(handle->fs->flags & EXT2_FLAG_RW))
1060 return EXT2_ET_RO_FILSYS;
1061
1062 if (!handle->path)
1063 return EXT2_ET_NO_CURRENT_NODE;
1064
1065 #ifdef DEBUG
1066 printf("extent insert: %u ", handle->ino);
1067 dbg_print_extent(0, extent);
1068 #endif
1069
1070 path = handle->path + handle->level;
1071
1072 if (path->entries >= path->max_entries) {
1073 if (flags & EXT2_EXTENT_INSERT_NOSPLIT) {
1074 return EXT2_ET_CANT_INSERT_EXTENT;
1075 } else {
1076 #ifdef DEBUG
1077 printf("node full (level %d) - splitting\n",
1078 handle->level);
1079 #endif
1080 retval = ext2fs_extent_node_split(handle);
1081 if (retval)
1082 return retval;
1083 path = handle->path + handle->level;
1084 }
1085 }
1086
1087 eh = (struct ext3_extent_header *) path->buf;
1088 if (path->curr) {
1089 ix = path->curr;
1090 if (flags & EXT2_EXTENT_INSERT_AFTER) {
1091 ix++;
1092 path->left--;
1093 }
1094 } else
1095 ix = EXT_FIRST_INDEX(eh);
1096
1097 path->curr = ix;
1098
1099 if (path->left >= 0)
1100 memmove(ix + 1, ix,
1101 (path->left+1) * sizeof(struct ext3_extent_idx));
1102 path->left++;
1103 path->entries++;
1104
1105 eh = (struct ext3_extent_header *) path->buf;
1106 eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
1107
1108 retval = ext2fs_extent_replace(handle, 0, extent);
1109 if (retval)
1110 goto errout;
1111
1112 retval = update_path(handle);
1113 if (retval)
1114 goto errout;
1115
1116 return 0;
1117
1118 errout:
1119 ext2fs_extent_delete(handle, 0);
1120 return retval;
1121 }
1122
1123 /*
1124 * Sets the physical block for a logical file block in the extent tree.
1125 *
1126 * May: map unmapped, unmap mapped, or remap mapped blocks.
1127 *
1128 * Mapping an unmapped block adds a single-block extent.
1129 *
1130 * Unmapping first or last block modifies extent in-place
1131 * - But may need to fix parent's starts too in first-block case
1132 *
1133 * Mapping any unmapped block requires adding a (single-block) extent
1134 * and inserting into proper point in tree.
1135 *
1136 * Modifying (unmapping or remapping) a block in the middle
1137 * of an extent requires splitting the extent.
1138 * - Remapping case requires new single-block extent.
1139 *
1140 * Remapping first or last block adds an extent.
1141 *
1142 * We really need extent adding to be smart about merging.
1143 */
1144
ext2fs_extent_set_bmap(ext2_extent_handle_t handle,blk64_t logical,blk64_t physical,int flags)1145 errcode_t ext2fs_extent_set_bmap(ext2_extent_handle_t handle,
1146 blk64_t logical, blk64_t physical, int flags)
1147 {
1148 errcode_t ec, retval = 0;
1149 int mapped = 1; /* logical is mapped? */
1150 int orig_height;
1151 int extent_uninit = 0;
1152 int prev_uninit = 0;
1153 int next_uninit = 0;
1154 int new_uninit = 0;
1155 int max_len = EXT_INIT_MAX_LEN;
1156 int has_prev, has_next;
1157 blk64_t orig_lblk;
1158 struct extent_path *path;
1159 struct ext2fs_extent extent, next_extent, prev_extent;
1160 struct ext2fs_extent newextent;
1161 struct ext2_extent_info info;
1162
1163 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1164
1165 #ifdef DEBUG
1166 printf("set_bmap ino %u log %lld phys %lld flags %d\n",
1167 handle->ino, logical, physical, flags);
1168 #endif
1169
1170 if (!(handle->fs->flags & EXT2_FLAG_RW))
1171 return EXT2_ET_RO_FILSYS;
1172
1173 if (!handle->path)
1174 return EXT2_ET_NO_CURRENT_NODE;
1175
1176 path = handle->path + handle->level;
1177
1178 if (flags & EXT2_EXTENT_SET_BMAP_UNINIT) {
1179 new_uninit = 1;
1180 max_len = EXT_UNINIT_MAX_LEN;
1181 }
1182
1183 /* if (re)mapping, set up new extent to insert */
1184 if (physical) {
1185 newextent.e_len = 1;
1186 newextent.e_pblk = physical;
1187 newextent.e_lblk = logical;
1188 newextent.e_flags = EXT2_EXTENT_FLAGS_LEAF;
1189 if (new_uninit)
1190 newextent.e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
1191 }
1192
1193 /* special case if the extent tree is completely empty */
1194 if ((handle->max_depth == 0) && (path->entries == 0)) {
1195 retval = ext2fs_extent_insert(handle, 0, &newextent);
1196 return retval;
1197 }
1198
1199 /* save our original location in the extent tree */
1200 if ((retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
1201 &extent))) {
1202 if (retval != EXT2_ET_NO_CURRENT_NODE)
1203 return retval;
1204 memset(&extent, 0, sizeof(extent));
1205 }
1206 if ((retval = ext2fs_extent_get_info(handle, &info)))
1207 return retval;
1208 orig_height = info.max_depth - info.curr_level;
1209 orig_lblk = extent.e_lblk;
1210
1211 /* go to the logical spot we want to (re/un)map */
1212 retval = ext2fs_extent_goto(handle, logical);
1213 if (retval) {
1214 if (retval == EXT2_ET_EXTENT_NOT_FOUND) {
1215 retval = 0;
1216 mapped = 0;
1217 if (!physical) {
1218 #ifdef DEBUG
1219 printf("block %llu already unmapped\n",
1220 logical);
1221 #endif
1222 goto done;
1223 }
1224 } else
1225 goto done;
1226 }
1227
1228 /*
1229 * This may be the extent *before* the requested logical,
1230 * if it's currently unmapped.
1231 *
1232 * Get the previous and next leaf extents, if they are present.
1233 */
1234 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
1235 if (retval)
1236 goto done;
1237 if (extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT)
1238 extent_uninit = 1;
1239 retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_LEAF, &next_extent);
1240 if (retval) {
1241 has_next = 0;
1242 if (retval != EXT2_ET_EXTENT_NO_NEXT)
1243 goto done;
1244 } else {
1245 dbg_print_extent("set_bmap: next_extent",
1246 &next_extent);
1247 has_next = 1;
1248 if (next_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT)
1249 next_uninit = 1;
1250 }
1251 retval = ext2fs_extent_goto(handle, logical);
1252 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND)
1253 goto done;
1254 retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_LEAF, &prev_extent);
1255 if (retval) {
1256 has_prev = 0;
1257 if (retval != EXT2_ET_EXTENT_NO_PREV)
1258 goto done;
1259 } else {
1260 has_prev = 1;
1261 dbg_print_extent("set_bmap: prev_extent",
1262 &prev_extent);
1263 if (prev_extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT)
1264 prev_uninit = 1;
1265 }
1266 retval = ext2fs_extent_goto(handle, logical);
1267 if (retval && retval != EXT2_ET_EXTENT_NOT_FOUND)
1268 goto done;
1269
1270 /* check if already pointing to the requested physical */
1271 if (mapped && (new_uninit == extent_uninit) &&
1272 (extent.e_pblk + (logical - extent.e_lblk) == physical)) {
1273 #ifdef DEBUG
1274 printf("physical block (at %llu) unchanged\n", logical);
1275 #endif
1276 goto done;
1277 }
1278
1279 if (!mapped) {
1280 #ifdef DEBUG
1281 printf("mapping unmapped logical block %llu\n", logical);
1282 #endif
1283 if ((logical == extent.e_lblk + extent.e_len) &&
1284 (physical == extent.e_pblk + extent.e_len) &&
1285 (new_uninit == extent_uninit) &&
1286 ((int) extent.e_len < max_len-1)) {
1287 extent.e_len++;
1288 retval = ext2fs_extent_replace(handle, 0, &extent);
1289 } else if ((logical == extent.e_lblk - 1) &&
1290 (physical == extent.e_pblk - 1) &&
1291 (new_uninit == extent_uninit) &&
1292 ((int) extent.e_len < max_len - 1)) {
1293 extent.e_len++;
1294 extent.e_lblk--;
1295 extent.e_pblk--;
1296 retval = ext2fs_extent_replace(handle, 0, &extent);
1297 } else if (has_next &&
1298 (logical == next_extent.e_lblk - 1) &&
1299 (physical == next_extent.e_pblk - 1) &&
1300 (new_uninit == next_uninit) &&
1301 ((int) next_extent.e_len < max_len - 1)) {
1302 retval = ext2fs_extent_get(handle,
1303 EXT2_EXTENT_NEXT_LEAF,
1304 &next_extent);
1305 if (retval)
1306 goto done;
1307 next_extent.e_len++;
1308 next_extent.e_lblk--;
1309 next_extent.e_pblk--;
1310 retval = ext2fs_extent_replace(handle, 0, &next_extent);
1311 } else if (logical < extent.e_lblk)
1312 retval = ext2fs_extent_insert(handle, 0, &newextent);
1313 else
1314 retval = ext2fs_extent_insert(handle,
1315 EXT2_EXTENT_INSERT_AFTER, &newextent);
1316 if (retval)
1317 goto done;
1318 retval = ext2fs_extent_fix_parents(handle);
1319 if (retval)
1320 goto done;
1321 } else if ((logical == extent.e_lblk) && (extent.e_len == 1)) {
1322 #ifdef DEBUG
1323 printf("(re/un)mapping only block in extent\n");
1324 #endif
1325 if (physical) {
1326 retval = ext2fs_extent_replace(handle, 0, &newextent);
1327 } else {
1328 retval = ext2fs_extent_delete(handle, 0);
1329 if (retval)
1330 goto done;
1331 ec = ext2fs_extent_fix_parents(handle);
1332 if (ec != EXT2_ET_NO_CURRENT_NODE)
1333 retval = ec;
1334 }
1335
1336 if (retval)
1337 goto done;
1338 } else if (logical == extent.e_lblk + extent.e_len - 1) {
1339 #ifdef DEBUG
1340 printf("(re/un)mapping last block in extent\n");
1341 #endif
1342 if (physical) {
1343 if (has_next &&
1344 (logical == (next_extent.e_lblk - 1)) &&
1345 (physical == (next_extent.e_pblk - 1)) &&
1346 (new_uninit == next_uninit) &&
1347 ((int) next_extent.e_len < max_len - 1)) {
1348 retval = ext2fs_extent_get(handle,
1349 EXT2_EXTENT_NEXT_LEAF, &next_extent);
1350 if (retval)
1351 goto done;
1352 next_extent.e_len++;
1353 next_extent.e_lblk--;
1354 next_extent.e_pblk--;
1355 retval = ext2fs_extent_replace(handle, 0,
1356 &next_extent);
1357 if (retval)
1358 goto done;
1359 retval = ext2fs_extent_fix_parents(handle);
1360 if (retval)
1361 goto done;
1362 } else
1363 retval = ext2fs_extent_insert(handle,
1364 EXT2_EXTENT_INSERT_AFTER, &newextent);
1365 if (retval)
1366 goto done;
1367 /* Now pointing at inserted extent; move back to prev */
1368 retval = ext2fs_extent_get(handle,
1369 EXT2_EXTENT_PREV_LEAF,
1370 &extent);
1371 if (retval)
1372 goto done;
1373 }
1374 extent.e_len--;
1375 retval = ext2fs_extent_replace(handle, 0, &extent);
1376 if (retval)
1377 goto done;
1378 } else if (logical == extent.e_lblk) {
1379 #ifdef DEBUG
1380 printf("(re/un)mapping first block in extent\n");
1381 #endif
1382 if (physical) {
1383 if (has_prev &&
1384 (logical == (prev_extent.e_lblk +
1385 prev_extent.e_len)) &&
1386 (physical == (prev_extent.e_pblk +
1387 prev_extent.e_len)) &&
1388 (new_uninit == prev_uninit) &&
1389 ((int) prev_extent.e_len < max_len-1)) {
1390 retval = ext2fs_extent_get(handle,
1391 EXT2_EXTENT_PREV_LEAF, &prev_extent);
1392 if (retval)
1393 goto done;
1394 prev_extent.e_len++;
1395 retval = ext2fs_extent_replace(handle, 0,
1396 &prev_extent);
1397 } else
1398 retval = ext2fs_extent_insert(handle,
1399 0, &newextent);
1400 if (retval)
1401 goto done;
1402 retval = ext2fs_extent_get(handle,
1403 EXT2_EXTENT_NEXT_LEAF,
1404 &extent);
1405 if (retval)
1406 goto done;
1407 }
1408 extent.e_pblk++;
1409 extent.e_lblk++;
1410 extent.e_len--;
1411 retval = ext2fs_extent_replace(handle, 0, &extent);
1412 if (retval)
1413 goto done;
1414 retval = ext2fs_extent_fix_parents(handle);
1415 if (retval)
1416 goto done;
1417 } else {
1418 __u32 orig_length;
1419
1420 #ifdef DEBUG
1421 printf("(re/un)mapping in middle of extent\n");
1422 #endif
1423 /* need to split this extent; later */
1424
1425 orig_length = extent.e_len;
1426
1427 /* shorten pre-split extent */
1428 extent.e_len = (logical - extent.e_lblk);
1429 retval = ext2fs_extent_replace(handle, 0, &extent);
1430 if (retval)
1431 goto done;
1432 /* insert our new extent, if any */
1433 if (physical) {
1434 /* insert new extent after current */
1435 retval = ext2fs_extent_insert(handle,
1436 EXT2_EXTENT_INSERT_AFTER, &newextent);
1437 if (retval)
1438 goto done;
1439 }
1440 /* add post-split extent */
1441 extent.e_pblk += extent.e_len + 1;
1442 extent.e_lblk += extent.e_len + 1;
1443 extent.e_len = orig_length - extent.e_len - 1;
1444 retval = ext2fs_extent_insert(handle,
1445 EXT2_EXTENT_INSERT_AFTER, &extent);
1446 if (retval)
1447 goto done;
1448 }
1449
1450 done:
1451 /* get handle back to its position */
1452 if (orig_height > handle->max_depth)
1453 orig_height = handle->max_depth; /* In case we shortened the tree */
1454 ext2fs_extent_goto2(handle, orig_height, orig_lblk);
1455 return retval;
1456 }
1457
ext2fs_extent_delete(ext2_extent_handle_t handle,int flags)1458 errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle, int flags)
1459 {
1460 struct extent_path *path;
1461 char *cp;
1462 struct ext3_extent_header *eh;
1463 errcode_t retval = 0;
1464
1465 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1466
1467 if (!(handle->fs->flags & EXT2_FLAG_RW))
1468 return EXT2_ET_RO_FILSYS;
1469
1470 if (!handle->path)
1471 return EXT2_ET_NO_CURRENT_NODE;
1472
1473 #ifdef DEBUG
1474 {
1475 struct ext2fs_extent extent;
1476
1477 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT,
1478 &extent);
1479 if (retval == 0) {
1480 printf("extent delete %u ", handle->ino);
1481 dbg_print_extent(0, &extent);
1482 }
1483 }
1484 #endif
1485
1486 path = handle->path + handle->level;
1487 if (!path->curr)
1488 return EXT2_ET_NO_CURRENT_NODE;
1489
1490 cp = path->curr;
1491
1492 if (path->left) {
1493 memmove(cp, cp + sizeof(struct ext3_extent_idx),
1494 path->left * sizeof(struct ext3_extent_idx));
1495 path->left--;
1496 } else {
1497 struct ext3_extent_idx *ix = path->curr;
1498 ix--;
1499 path->curr = ix;
1500 }
1501 if (--path->entries == 0)
1502 path->curr = 0;
1503
1504 /* if non-root node has no entries left, remove it & parent ptr to it */
1505 if (path->entries == 0 && handle->level) {
1506 if (!(flags & EXT2_EXTENT_DELETE_KEEP_EMPTY)) {
1507 struct ext2fs_extent extent;
1508
1509 retval = ext2fs_extent_get(handle, EXT2_EXTENT_UP,
1510 &extent);
1511 if (retval)
1512 return retval;
1513
1514 retval = ext2fs_extent_delete(handle, flags);
1515 handle->inode->i_blocks -=
1516 (handle->fs->blocksize *
1517 EXT2FS_CLUSTER_RATIO(handle->fs)) / 512;
1518 retval = ext2fs_write_inode(handle->fs, handle->ino,
1519 handle->inode);
1520 ext2fs_block_alloc_stats2(handle->fs,
1521 extent.e_pblk, -1);
1522 }
1523 } else {
1524 eh = (struct ext3_extent_header *) path->buf;
1525 eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
1526 if ((path->entries == 0) && (handle->level == 0))
1527 eh->eh_depth = handle->max_depth = 0;
1528 retval = update_path(handle);
1529 }
1530 return retval;
1531 }
1532
ext2fs_extent_get_info(ext2_extent_handle_t handle,struct ext2_extent_info * info)1533 errcode_t ext2fs_extent_get_info(ext2_extent_handle_t handle,
1534 struct ext2_extent_info *info)
1535 {
1536 struct extent_path *path;
1537
1538 EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
1539
1540 memset(info, 0, sizeof(struct ext2_extent_info));
1541
1542 path = handle->path + handle->level;
1543 if (path) {
1544 if (path->curr)
1545 info->curr_entry = ((char *) path->curr - path->buf) /
1546 sizeof(struct ext3_extent_idx);
1547 else
1548 info->curr_entry = 0;
1549 info->num_entries = path->entries;
1550 info->max_entries = path->max_entries;
1551 info->bytes_avail = (path->max_entries - path->entries) *
1552 sizeof(struct ext3_extent);
1553 }
1554
1555 info->curr_level = handle->level;
1556 info->max_depth = handle->max_depth;
1557 info->max_lblk = ((__u64) 1 << 32) - 1;
1558 info->max_pblk = ((__u64) 1 << 48) - 1;
1559 info->max_len = (1UL << 15);
1560 info->max_uninit_len = (1UL << 15) - 1;
1561
1562 return 0;
1563 }
1564
1565 #ifdef DEBUG
1566 /*
1567 * Override debugfs's prompt
1568 */
1569 const char *debug_prog_name = "tst_extents";
1570
1571 #endif
1572
1573