extent.c revision aa8e2f1c31374bfc6e479aea008896d179b100b4
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#include "ss/ss.h"
31
32/*
33 * Definitions to be dropped in lib/ext2fs/ext2fs.h
34 */
35
36/*
37 * Private definitions
38 */
39
40struct extent_path {
41	char		*buf;
42	int		entries;
43	int		max_entries;
44	int		left;
45	int		visit_num;
46	int		flags;
47	blk64_t		end_blk;
48	void		*curr;
49};
50
51
52struct ext2_extent_handle {
53	errcode_t		magic;
54	ext2_filsys		fs;
55	ext2_ino_t 		ino;
56	struct ext2_inode	*inode;
57	int			type;
58	int			level;
59	int			max_depth;
60	struct extent_path	*path;
61};
62
63struct 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
74static 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	       eh->eh_magic, eh->eh_entries, eh->eh_max, eh->eh_depth,
78	       eh->eh_generation);
79}
80
81static void dbg_show_index(struct ext3_extent_idx *ix)
82{
83	printf("index: block=%u leaf=%u leaf_hi=%u unused=%u\n",
84	       ix->ei_block, ix->ei_leaf, ix->ei_leaf_hi, ix->ei_unused);
85}
86
87static void dbg_show_extent(struct ext3_extent *ex)
88{
89	printf("extent: block=%u-%u len=%u start=%u start_hi=%u\n",
90	       ex->ee_block, ex->ee_block + ex->ee_len - 1,
91	       ex->ee_len, ex->ee_start, ex->ee_start_hi);
92}
93
94static void dbg_print_extent(char *desc, struct ext2fs_extent *extent)
95{
96	if (desc)
97		printf("%s: ", desc);
98	printf("extent: lblk %llu--%llu, len %lu, pblk %llu, flags: ",
99	       extent->e_lblk, extent->e_lblk + extent->e_len - 1,
100	       extent->e_len, extent->e_pblk);
101	if (extent->e_flags & EXT2_EXTENT_FLAGS_LEAF)
102		fputs("LEAF ", stdout);
103	if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT)
104		fputs("UNINIT ", stdout);
105	if (extent->e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT)
106		fputs("2ND_VISIT ", stdout);
107	if (!extent->e_flags)
108		fputs("(none)", stdout);
109	fputc('\n', stdout);
110
111}
112
113#define dbg_printf(fmt, args...) printf(fmt, ## args)
114#else
115#define dbg_show_header(eh) do { } while (0)
116#define dbg_show_index(ix) do { } while (0)
117#define dbg_show_extent(ex) do { } while (0)
118#define dbg_print_extent(desc, ex) do { } while (0)
119#define dbg_printf(fmt, args...) do { } while (0)
120#endif
121
122/*
123 * Verify the extent header as being sane
124 */
125errcode_t ext2fs_extent_header_verify(void *ptr, int size)
126{
127	int eh_max, entry_size;
128	struct ext3_extent_header *eh = ptr;
129
130	dbg_show_header(eh);
131	if (ext2fs_le16_to_cpu(eh->eh_magic) != EXT3_EXT_MAGIC)
132		return EXT2_ET_EXTENT_HEADER_BAD;
133	if (ext2fs_le16_to_cpu(eh->eh_entries) > ext2fs_le16_to_cpu(eh->eh_max))
134		return EXT2_ET_EXTENT_HEADER_BAD;
135	if (eh->eh_depth == 0)
136		entry_size = sizeof(struct ext3_extent);
137	else
138		entry_size = sizeof(struct ext3_extent_idx);
139
140	eh_max = (size - sizeof(*eh)) / entry_size;
141	/* Allow two extent-sized items at the end of the block, for
142	 * ext4_extent_tail with checksum in the future. */
143	if ((ext2fs_le16_to_cpu(eh->eh_max) > eh_max) ||
144	    (ext2fs_le16_to_cpu(eh->eh_max) < (eh_max - 2)))
145		return EXT2_ET_EXTENT_HEADER_BAD;
146
147	return 0;
148}
149
150
151/*
152 * Begin functions to handle an inode's extent information
153 */
154extern void ext2fs_extent_free(ext2_extent_handle_t handle)
155{
156	int			i;
157
158	if (!handle)
159		return;
160
161	if (handle->inode)
162		ext2fs_free_mem(&handle->inode);
163	if (handle->path) {
164		for (i=1; i < handle->max_depth; i++) {
165			if (handle->path[i].buf)
166				ext2fs_free_mem(&handle->path[i].buf);
167		}
168		ext2fs_free_mem(&handle->path);
169	}
170	ext2fs_free_mem(&handle);
171}
172
173extern errcode_t ext2fs_extent_open(ext2_filsys fs, ext2_ino_t ino,
174				    ext2_extent_handle_t *ret_handle)
175{
176	struct ext2_extent_handle	*handle;
177	errcode_t			retval;
178	int				isize = EXT2_INODE_SIZE(fs->super);
179	int				i;
180	struct ext3_extent_header	*eh;
181
182	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
183
184	if ((ino == 0) || (ino > fs->super->s_inodes_count))
185		return EXT2_ET_BAD_INODE_NUM;
186
187	retval = ext2fs_get_mem(sizeof(struct ext2_extent_handle), &handle);
188	if (retval)
189		return retval;
190	memset(handle, 0, sizeof(struct ext2_extent_handle));
191
192	retval = ext2fs_get_mem(isize, &handle->inode);
193	if (retval)
194		goto errout;
195
196	handle->ino = ino;
197	handle->fs = fs;
198
199	retval = ext2fs_read_inode_full(fs, ino, handle->inode, isize);
200	if (retval)
201		goto errout;
202
203	eh = (struct ext3_extent_header *) &handle->inode->i_block[0];
204
205	for (i=0; i < EXT2_N_BLOCKS; i++)
206		if (handle->inode->i_block[i])
207			break;
208	if (i >= EXT2_N_BLOCKS) {
209		eh->eh_magic = ext2fs_cpu_to_le16(EXT3_EXT_MAGIC);
210		eh->eh_depth = 0;
211		eh->eh_entries = 0;
212		i = (sizeof(handle->inode->i_block) - sizeof(*eh)) /
213			sizeof(struct ext3_extent);
214		eh->eh_max = ext2fs_cpu_to_le16(i);
215		handle->inode->i_flags |= EXT4_EXTENTS_FL;
216	}
217
218	if (!(handle->inode->i_flags & EXT4_EXTENTS_FL))
219		return EXT2_ET_INODE_NOT_EXTENT;
220
221	retval = ext2fs_extent_header_verify(eh, sizeof(handle->inode->i_block));
222	if (retval)
223		return (retval);
224
225	handle->max_depth = ext2fs_le16_to_cpu(eh->eh_depth);
226	handle->type = ext2fs_le16_to_cpu(eh->eh_magic);
227
228	retval = ext2fs_get_mem(((handle->max_depth+1) *
229				 sizeof(struct extent_path)),
230				&handle->path);
231	memset(handle->path, 0,
232	       (handle->max_depth+1) * sizeof(struct extent_path));
233	handle->path[0].buf = (char *) handle->inode->i_block;
234
235	handle->path[0].left = handle->path[0].entries =
236		ext2fs_le16_to_cpu(eh->eh_entries);
237	handle->path[0].max_entries = ext2fs_le16_to_cpu(eh->eh_max);
238	handle->path[0].curr = 0;
239	handle->path[0].end_blk =
240		((((__u64) handle->inode->i_size_high << 32) +
241		  handle->inode->i_size + (fs->blocksize - 1))
242		 >> EXT2_BLOCK_SIZE_BITS(fs->super));
243	handle->path[0].visit_num = 1;
244	handle->level = 0;
245	handle->magic = EXT2_ET_MAGIC_EXTENT_HANDLE;
246
247	*ret_handle = handle;
248	return 0;
249
250errout:
251	ext2fs_extent_free(handle);
252	return retval;
253}
254
255/*
256 * This function is responsible for (optionally) moving through the
257 * extent tree and then returning the current extent
258 */
259errcode_t ext2fs_extent_get(ext2_extent_handle_t handle,
260			    int flags, struct ext2fs_extent *extent)
261{
262	struct extent_path	*path, *newpath;
263	struct ext3_extent_header	*eh;
264	struct ext3_extent_idx		*ix = 0;
265	struct ext3_extent		*ex;
266	errcode_t			retval;
267	blk_t				blk;
268	blk64_t				end_blk;
269	int				orig_op, op;
270
271	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
272
273	if (!handle->path)
274		return EXT2_ET_NO_CURRENT_NODE;
275
276	orig_op = op = flags & EXT2_EXTENT_MOVE_MASK;
277
278retry:
279	path = handle->path + handle->level;
280	if ((orig_op == EXT2_EXTENT_NEXT) ||
281	    (orig_op == EXT2_EXTENT_NEXT_LEAF)) {
282		if (handle->level < handle->max_depth) {
283			/* interior node */
284			if (path->visit_num == 0) {
285				path->visit_num++;
286				op = EXT2_EXTENT_DOWN;
287			} else if (path->left > 0)
288				op = EXT2_EXTENT_NEXT_SIB;
289			else if (handle->level > 0)
290				op = EXT2_EXTENT_UP;
291			else
292				return EXT2_ET_EXTENT_NO_NEXT;
293		} else {
294			/* leaf node */
295			if (path->left > 0)
296				op = EXT2_EXTENT_NEXT_SIB;
297			else if (handle->level > 0)
298				op = EXT2_EXTENT_UP;
299			else
300				return EXT2_ET_EXTENT_NO_NEXT;
301		}
302		if (op != EXT2_EXTENT_NEXT_SIB) {
303			dbg_printf("<<<< OP = %s\n",
304			       (op == EXT2_EXTENT_DOWN) ? "down" :
305			       ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));
306		}
307	}
308
309	if ((orig_op == EXT2_EXTENT_PREV) ||
310	    (orig_op == EXT2_EXTENT_PREV_LEAF)) {
311		if (handle->level < handle->max_depth) {
312			/* interior node */
313			if (path->visit_num > 0 ) {
314				/* path->visit_num = 0; */
315				op = EXT2_EXTENT_DOWN_AND_LAST;
316			} else if (path->left < path->entries-1)
317				op = EXT2_EXTENT_PREV_SIB;
318			else if (handle->level > 0)
319				op = EXT2_EXTENT_UP;
320			else
321				return EXT2_ET_EXTENT_NO_PREV;
322		} else {
323			/* leaf node */
324			if (path->left < path->entries-1)
325				op = EXT2_EXTENT_PREV_SIB;
326			else if (handle->level > 0)
327				op = EXT2_EXTENT_UP;
328			else
329				return EXT2_ET_EXTENT_NO_PREV;
330		}
331		if (op != EXT2_EXTENT_PREV_SIB) {
332			dbg_printf("<<<< OP = %s\n",
333			       (op == EXT2_EXTENT_DOWN_AND_LAST) ? "down/last" :
334			       ((op == EXT2_EXTENT_UP) ? "up" : "unknown"));
335		}
336	}
337
338	if (orig_op == EXT2_EXTENT_LAST_LEAF) {
339		if ((handle->level < handle->max_depth) &&
340		    (path->left == 0))
341			op = EXT2_EXTENT_DOWN;
342		else
343			op = EXT2_EXTENT_LAST_SIB;
344		dbg_printf("<<<< OP = %s\n",
345			   (op == EXT2_EXTENT_DOWN) ? "down" : "last_sib");
346	}
347
348	switch (op) {
349	case EXT2_EXTENT_CURRENT:
350		ix = path->curr;
351		break;
352	case EXT2_EXTENT_ROOT:
353		handle->level = 0;
354		path = handle->path + handle->level;
355	case EXT2_EXTENT_FIRST_SIB:
356		path->left = path->entries;
357		path->curr = 0;
358	case EXT2_EXTENT_NEXT_SIB:
359		if (path->left <= 0)
360			return EXT2_ET_EXTENT_NO_NEXT;
361		if (path->curr) {
362			ix = path->curr;
363			ix++;
364		} else {
365			eh = (struct ext3_extent_header *) path->buf;
366			ix = EXT_FIRST_INDEX(eh);
367		}
368		path->left--;
369		path->curr = ix;
370		path->visit_num = 0;
371		break;
372	case EXT2_EXTENT_PREV_SIB:
373		if (!path->curr ||
374		    path->left+1 >= path->entries)
375			return EXT2_ET_EXTENT_NO_PREV;
376		ix = path->curr;
377		ix--;
378		path->curr = ix;
379		path->left++;
380		if (handle->level < handle->max_depth)
381			path->visit_num = 1;
382		break;
383	case EXT2_EXTENT_LAST_SIB:
384		eh = (struct ext3_extent_header *) path->buf;
385		path->curr = EXT_LAST_EXTENT(eh);
386		ix = path->curr;
387		path->left = 0;
388		path->visit_num = 0;
389		break;
390	case EXT2_EXTENT_UP:
391		if (handle->level <= 0)
392			return EXT2_ET_EXTENT_NO_UP;
393		handle->level--;
394		path--;
395		ix = path->curr;
396		if ((orig_op == EXT2_EXTENT_PREV) ||
397		    (orig_op == EXT2_EXTENT_PREV_LEAF))
398			path->visit_num = 0;
399		break;
400	case EXT2_EXTENT_DOWN:
401	case EXT2_EXTENT_DOWN_AND_LAST:
402		if (!path->curr ||(handle->level >= handle->max_depth))
403			return EXT2_ET_EXTENT_NO_DOWN;
404
405		ix = path->curr;
406		newpath = path + 1;
407		if (!newpath->buf) {
408			retval = ext2fs_get_mem(handle->fs->blocksize,
409						&newpath->buf);
410			if (retval)
411				return retval;
412		}
413		blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
414			((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
415		if ((handle->fs->flags & EXT2_FLAG_IMAGE_FILE) &&
416		    (handle->fs->io != handle->fs->image_io))
417			memset(newpath->buf, 0, handle->fs->blocksize);
418		else {
419			retval = io_channel_read_blk(handle->fs->io,
420						     blk, 1, newpath->buf);
421			if (retval)
422				return retval;
423		}
424		handle->level++;
425
426		eh = (struct ext3_extent_header *) newpath->buf;
427
428		retval = ext2fs_extent_header_verify(eh, handle->fs->blocksize);
429		if (retval)
430			return retval;
431
432		newpath->left = newpath->entries =
433			ext2fs_le16_to_cpu(eh->eh_entries);
434		newpath->max_entries = ext2fs_le16_to_cpu(eh->eh_max);
435
436		if (path->left > 0) {
437			ix++;
438			newpath->end_blk = ext2fs_le32_to_cpu(ix->ei_block);
439		} else
440			newpath->end_blk = path->end_blk;
441
442		path = newpath;
443		if (op == EXT2_EXTENT_DOWN) {
444			ix = EXT_FIRST_INDEX((struct ext3_extent_header *) eh);
445			path->curr = ix;
446			path->left = path->entries - 1;
447			path->visit_num = 0;
448		} else {
449			ix = EXT_LAST_INDEX((struct ext3_extent_header *) eh);
450			path->curr = ix;
451			path->left = 0;
452			if (handle->level < handle->max_depth)
453				path->visit_num = 1;
454		}
455
456		dbg_printf("Down to level %d/%d, end_blk=%llu\n",
457			   handle->level, handle->max_depth,
458			   path->end_blk);
459
460		break;
461	default:
462		return EXT2_ET_OP_NOT_SUPPORTED;
463	}
464
465	if (!ix)
466		return EXT2_ET_NO_CURRENT_NODE;
467
468	extent->e_flags = 0;
469	dbg_printf("(Left %d)\n", path->left);
470
471	if (handle->level == handle->max_depth) {
472		ex = (struct ext3_extent *) ix;
473
474		extent->e_pblk = ext2fs_le32_to_cpu(ex->ee_start) +
475			((__u64) ext2fs_le16_to_cpu(ex->ee_start_hi) << 32);
476		extent->e_lblk = ext2fs_le32_to_cpu(ex->ee_block);
477		extent->e_len = ext2fs_le16_to_cpu(ex->ee_len);
478		extent->e_flags |= EXT2_EXTENT_FLAGS_LEAF;
479		if (extent->e_len > EXT_INIT_MAX_LEN) {
480			extent->e_len -= EXT_INIT_MAX_LEN;
481			extent->e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
482		}
483	} else {
484		extent->e_pblk = ext2fs_le32_to_cpu(ix->ei_leaf) +
485			((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
486		extent->e_lblk = ext2fs_le32_to_cpu(ix->ei_block);
487		if (path->left > 0) {
488			ix++;
489			end_blk = ext2fs_le32_to_cpu(ix->ei_block);
490		} else
491			end_blk = path->end_blk;
492
493		extent->e_len = end_blk - extent->e_lblk;
494	}
495	if (path->visit_num)
496		extent->e_flags |= EXT2_EXTENT_FLAGS_SECOND_VISIT;
497
498	if (((orig_op == EXT2_EXTENT_NEXT_LEAF) ||
499	     (orig_op == EXT2_EXTENT_PREV_LEAF)) &&
500	    (handle->level != handle->max_depth))
501		goto retry;
502
503	if ((orig_op == EXT2_EXTENT_LAST_LEAF) &&
504	    ((handle->level != handle->max_depth) ||
505	     (path->left != 0)))
506		goto retry;
507
508	return 0;
509}
510
511static errcode_t update_path(ext2_extent_handle_t handle)
512{
513	blk64_t				blk;
514	errcode_t			retval;
515	struct ext3_extent_idx		*ix;
516
517	if (handle->level == 0) {
518		retval = ext2fs_write_inode_full(handle->fs, handle->ino,
519			   handle->inode, EXT2_INODE_SIZE(handle->fs->super));
520	} else {
521		ix = handle->path[handle->level - 1].curr;
522		blk = ext2fs_le32_to_cpu(ix->ei_leaf) +
523			((__u64) ext2fs_le16_to_cpu(ix->ei_leaf_hi) << 32);
524
525		retval = io_channel_write_blk(handle->fs->io,
526				      blk, 1, handle->path[handle->level].buf);
527	}
528	return retval;
529}
530
531#if 0
532errcode_t ext2fs_extent_save_path(ext2_extent_handle_t handle,
533				  ext2_extent_path_t *ret_path)
534{
535	ext2_extent_path_t	save_path;
536	struct ext2fs_extent	extent;
537	struct ext2_extent_info	info;
538	errcode_t		retval;
539
540	retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
541	if (retval)
542		return retval;
543
544	retval = ext2fs_extent_get_info(handle, &info);
545	if (retval)
546		return retval;
547
548	retval = ext2fs_get_mem(sizeof(struct ext2_extent_path), &save_path);
549	if (retval)
550		return retval;
551	memset(save_path, 0, sizeof(struct ext2_extent_path));
552
553	save_path->magic = EXT2_ET_MAGIC_EXTENT_PATH;
554	save_path->leaf_height = info.max_depth - info.curr_level - 1;
555	save_path->lblk = extent.e_lblk;
556
557	*ret_path = save_path;
558	return 0;
559}
560
561errcode_t ext2fs_extent_free_path(ext2_extent_path_t path)
562{
563	EXT2_CHECK_MAGIC(path, EXT2_ET_MAGIC_EXTENT_PATH);
564
565	ext2fs_free_mem(&path);
566	return 0;
567}
568#endif
569
570/*
571 * Go to the node at leaf_level which contains logical block blk.
572 *
573 * leaf_level is height from the leaf node level, i.e.
574 * leaf_level 0 is at leaf node, leaf_level 1 is 1 above etc.
575 *
576 * If "blk" has no mapping (hole) then handle is left at last
577 * extent before blk.
578 */
579static errcode_t extent_goto(ext2_extent_handle_t handle,
580			     int leaf_level, blk64_t blk)
581{
582	struct ext2fs_extent	extent;
583	errcode_t		retval;
584
585	retval = ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent);
586	if (retval)
587		return retval;
588
589	if (leaf_level > handle->max_depth) {
590		dbg_printf("leaf level %d greater than tree depth %d\n",
591			leaf_level, handle->max_depth);
592		return EXT2_ET_OP_NOT_SUPPORTED;
593	}
594
595	dbg_print_extent("root", &extent);
596	while (1) {
597		if (handle->max_depth - handle->level == leaf_level) {
598			/* block is in this &extent */
599			if ((blk >= extent.e_lblk) &&
600			    (blk < extent.e_lblk + extent.e_len))
601				return 0;
602			if (blk < extent.e_lblk) {
603				retval = ext2fs_extent_get(handle,
604							   EXT2_EXTENT_PREV_SIB,
605							   &extent);
606				return EXT2_ET_EXTENT_NOT_FOUND;
607			}
608			retval = ext2fs_extent_get(handle,
609						   EXT2_EXTENT_NEXT_SIB,
610						   &extent);
611			if (retval == EXT2_ET_EXTENT_NO_NEXT)
612				return EXT2_ET_EXTENT_NOT_FOUND;
613			if (retval)
614				return retval;
615			continue;
616		}
617
618		retval = ext2fs_extent_get(handle, EXT2_EXTENT_NEXT_SIB,
619					   &extent);
620		if (retval == EXT2_ET_EXTENT_NO_NEXT)
621			goto go_down;
622		if (retval)
623			return retval;
624
625		dbg_print_extent("next", &extent);
626		if (blk == extent.e_lblk)
627			goto go_down;
628		if (blk > extent.e_lblk)
629			continue;
630
631		retval = ext2fs_extent_get(handle, EXT2_EXTENT_PREV_SIB,
632					   &extent);
633		if (retval)
634			return retval;
635
636		dbg_print_extent("prev", &extent);
637
638	go_down:
639		retval = ext2fs_extent_get(handle, EXT2_EXTENT_DOWN,
640					   &extent);
641		if (retval)
642			return retval;
643
644		dbg_print_extent("down", &extent);
645	}
646}
647
648errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle,
649			     blk64_t blk)
650{
651	return extent_goto(handle, 0, blk);
652}
653
654errcode_t ext2fs_extent_replace(ext2_extent_handle_t handle,
655				int flags EXT2FS_ATTR((unused)),
656				struct ext2fs_extent *extent)
657{
658	struct extent_path		*path;
659	struct ext3_extent_idx		*ix;
660	struct ext3_extent		*ex;
661
662	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
663
664	if (!(handle->fs->flags & EXT2_FLAG_RW))
665		return EXT2_ET_RO_FILSYS;
666
667	if (!handle->path)
668		return EXT2_ET_NO_CURRENT_NODE;
669
670	path = handle->path + handle->level;
671	if (!path->curr)
672		return EXT2_ET_NO_CURRENT_NODE;
673
674	if (handle->level == handle->max_depth) {
675		ex = path->curr;
676
677		ex->ee_block = ext2fs_cpu_to_le32(extent->e_lblk);
678		ex->ee_start = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);
679		ex->ee_start_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);
680		if (extent->e_flags & EXT2_EXTENT_FLAGS_UNINIT) {
681			if (extent->e_len > EXT_UNINIT_MAX_LEN)
682				return EXT2_ET_EXTENT_INVALID_LENGTH;
683			ex->ee_len = ext2fs_cpu_to_le16(extent->e_len +
684							EXT_INIT_MAX_LEN);
685		} else {
686			if (extent->e_len > EXT_INIT_MAX_LEN)
687				return EXT2_ET_EXTENT_INVALID_LENGTH;
688			ex->ee_len = ext2fs_cpu_to_le16(extent->e_len);
689		}
690	} else {
691		ix = path->curr;
692
693		ix->ei_leaf = ext2fs_cpu_to_le32(extent->e_pblk & 0xFFFFFFFF);
694		ix->ei_leaf_hi = ext2fs_cpu_to_le16(extent->e_pblk >> 32);
695		ix->ei_block = ext2fs_cpu_to_le32(extent->e_lblk);
696		ix->ei_unused = 0;
697	}
698	update_path(handle);
699	return 0;
700}
701
702errcode_t ext2fs_extent_insert(ext2_extent_handle_t handle, int flags,
703				      struct ext2fs_extent *extent)
704{
705	struct extent_path		*path;
706	struct ext3_extent_idx		*ix;
707	struct ext3_extent_header	*eh;
708	errcode_t			retval;
709
710	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
711
712	if (!(handle->fs->flags & EXT2_FLAG_RW))
713		return EXT2_ET_RO_FILSYS;
714
715	if (!handle->path)
716		return EXT2_ET_NO_CURRENT_NODE;
717
718	path = handle->path + handle->level;
719
720	if (path->entries >= path->max_entries)
721		return EXT2_ET_CANT_INSERT_EXTENT;
722
723	eh = (struct ext3_extent_header *) path->buf;
724	if (path->curr) {
725		ix = path->curr;
726		if (flags & EXT2_EXTENT_INSERT_AFTER) {
727			ix++;
728			path->left--;
729		}
730	} else
731		ix = EXT_FIRST_INDEX(eh);
732
733	path->curr = ix;
734
735	if (path->left >= 0)
736		memmove(ix + 1, ix,
737			(path->left+1) * sizeof(struct ext3_extent_idx));
738	path->left++;
739	path->entries++;
740
741	eh = (struct ext3_extent_header *) path->buf;
742	eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
743
744	retval = ext2fs_extent_replace(handle, 0, extent);
745	if (retval)
746		goto errout;
747
748	retval = update_path(handle);
749	if (retval)
750		goto errout;
751
752	return 0;
753
754errout:
755	ext2fs_extent_delete(handle, 0);
756	return retval;
757}
758
759errcode_t ext2fs_extent_delete(ext2_extent_handle_t handle,
760			       int flags EXT2FS_ATTR((unused)))
761{
762	struct extent_path		*path;
763	char 				*cp;
764	struct ext3_extent_header	*eh;
765	errcode_t			retval;
766
767	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
768
769	if (!(handle->fs->flags & EXT2_FLAG_RW))
770		return EXT2_ET_RO_FILSYS;
771
772	if (!handle->path)
773		return EXT2_ET_NO_CURRENT_NODE;
774
775	path = handle->path + handle->level;
776	if (!path->curr)
777		return EXT2_ET_NO_CURRENT_NODE;
778
779	cp = path->curr;
780
781	if (path->left) {
782		memmove(cp, cp + sizeof(struct ext3_extent_idx),
783			path->left * sizeof(struct ext3_extent_idx));
784		path->left--;
785	} else {
786		struct ext3_extent_idx	*ix = path->curr;
787		ix--;
788		path->curr = ix;
789	}
790	path->entries--;
791	if (path->entries == 0)
792		path->curr = 0;
793
794	eh = (struct ext3_extent_header *) path->buf;
795	eh->eh_entries = ext2fs_cpu_to_le16(path->entries);
796
797	retval = update_path(handle);
798
799	return retval;
800}
801
802errcode_t ext2fs_extent_get_info(ext2_extent_handle_t handle,
803				 struct ext2_extent_info *info)
804{
805	struct extent_path		*path;
806
807	EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE);
808
809	memset(info, 0, sizeof(struct ext2_extent_info));
810
811	path = handle->path + handle->level;
812	if (path) {
813		if (path->curr)
814			info->curr_entry = ((char *) path->curr - path->buf) /
815				sizeof(struct ext3_extent_idx);
816		else
817			info->curr_entry = 0;
818		info->num_entries = path->entries;
819		info->max_entries = path->max_entries;
820		info->bytes_avail = (path->max_entries - path->entries) *
821			sizeof(struct ext3_extent);
822	}
823
824	info->curr_level = handle->level;
825	info->max_depth = handle->max_depth;
826	info->max_lblk = ((__u64) 1 << 32) - 1;
827	info->max_pblk = ((__u64) 1 << 48) - 1;
828	info->max_len = (1UL << 15);
829	info->max_uninit_len = (1UL << 15) - 1;
830
831	return 0;
832}
833
834#ifdef DEBUG
835
836#include "debugfs.h"
837
838/*
839 * Hook in new commands into debugfs
840 */
841const char *debug_prog_name = "tst_extents";
842extern ss_request_table extent_cmds;
843ss_request_table *extra_cmds = &extent_cmds;
844
845ext2_ino_t	current_ino = 0;
846ext2_extent_handle_t current_handle;
847
848void do_inode(int argc, char *argv[])
849{
850	ext2_ino_t	inode;
851	int		i;
852	struct ext3_extent_header *eh;
853	errcode_t retval;
854
855	if (check_fs_open(argv[0]))
856		return;
857
858	if (argc == 1) {
859		if (current_ino)
860			printf("Current inode is %d\n", current_ino);
861		else
862			printf("No current inode\n");
863		return;
864	}
865
866	if (common_inode_args_process(argc, argv, &inode, 0)) {
867		return;
868	}
869
870	current_ino = 0;
871
872	retval = ext2fs_extent_open(current_fs, inode, &current_handle);
873	if (retval) {
874		com_err(argv[1], retval, "while opening extent handle");
875		return;
876	}
877
878	current_ino = inode;
879
880	printf("Loaded inode %d\n", current_ino);
881
882	return;
883}
884
885void generic_goto_node(char *cmd_name, int op)
886{
887	struct ext2fs_extent	extent;
888	errcode_t		retval;
889
890	if (check_fs_open(cmd_name))
891		return;
892
893	if (!current_handle) {
894		com_err(cmd_name, 0, "Extent handle not open");
895		return;
896	}
897
898	retval = ext2fs_extent_get(current_handle, op, &extent);
899	if (retval) {
900		com_err(cmd_name, retval, 0);
901		return;
902	}
903	dbg_print_extent(0, &extent);
904}
905
906void do_current_node(int argc, char *argv[])
907{
908	generic_goto_node(argv[0], EXT2_EXTENT_CURRENT);
909}
910
911void do_root_node(int argc, char *argv[])
912{
913	generic_goto_node(argv[0], EXT2_EXTENT_ROOT);
914}
915
916void do_last_leaf(int argc, char *argv[])
917{
918	generic_goto_node(argv[0], EXT2_EXTENT_LAST_LEAF);
919}
920
921void do_first_sib(int argc, char *argv[])
922{
923	generic_goto_node(argv[0], EXT2_EXTENT_FIRST_SIB);
924}
925
926void do_last_sib(int argc, char *argv[])
927{
928	generic_goto_node(argv[0], EXT2_EXTENT_LAST_SIB);
929}
930
931void do_next_sib(int argc, char *argv[])
932{
933	generic_goto_node(argv[0], EXT2_EXTENT_NEXT_SIB);
934}
935
936void do_prev_sib(int argc, char *argv[])
937{
938	generic_goto_node(argv[0], EXT2_EXTENT_PREV_SIB);
939}
940
941void do_next_leaf(int argc, char *argv[])
942{
943	generic_goto_node(argv[0], EXT2_EXTENT_NEXT_LEAF);
944}
945
946void do_prev_leaf(int argc, char *argv[])
947{
948	generic_goto_node(argv[0], EXT2_EXTENT_PREV_LEAF);
949}
950
951void do_next(int argc, char *argv[])
952{
953	generic_goto_node(argv[0], EXT2_EXTENT_NEXT);
954}
955
956void do_prev(int argc, char *argv[])
957{
958	generic_goto_node(argv[0], EXT2_EXTENT_PREV);
959}
960
961void do_up(int argc, char *argv[])
962{
963	generic_goto_node(argv[0], EXT2_EXTENT_UP);
964}
965
966void do_down(int argc, char *argv[])
967{
968	generic_goto_node(argv[0], EXT2_EXTENT_DOWN);
969}
970
971void do_delete_node(int argc, char *argv[])
972{
973	errcode_t	retval;
974	int		err;
975
976	if (check_fs_read_write(argv[0]))
977		return;
978
979	retval = ext2fs_extent_delete(current_handle, 0);
980	if (retval) {
981		com_err(argv[0], retval, 0);
982		return;
983	}
984	if (current_handle->path && current_handle->path[0].curr)
985		do_current_node(argc, argv);
986}
987
988void do_replace_node(int argc, char *argv[])
989{
990	errcode_t	retval;
991	struct ext2fs_extent extent;
992	int err;
993
994	if (check_fs_read_write(argv[0]))
995		return;
996
997	extent.e_flags = 0;
998
999	if (!strcmp(argv[1], "--uninit")) {
1000		argc--;
1001		argv++;
1002		extent.e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
1003	}
1004
1005	if (argc != 4) {
1006		fprintf(stderr, "usage: %s <lblk> <len> <pblk>\n", argv[0]);
1007		return;
1008	}
1009
1010	extent.e_lblk = parse_ulong(argv[1], argv[0],
1011				    "logical block", &err);
1012	if (err)
1013		return;
1014
1015	extent.e_len = parse_ulong(argv[2], argv[0],
1016				    "logical block", &err);
1017	if (err)
1018		return;
1019
1020	extent.e_pblk = parse_ulong(argv[3], argv[0],
1021				    "logical block", &err);
1022	if (err)
1023		return;
1024
1025	retval = ext2fs_extent_replace(current_handle, 0, &extent);
1026	if (retval) {
1027		com_err(argv[0], retval, 0);
1028		return;
1029	}
1030	do_current_node(argc, argv);
1031}
1032
1033void do_insert_node(int argc, char *argv[])
1034{
1035	errcode_t	retval;
1036	struct ext2fs_extent extent;
1037	char *cmd;
1038	int err;
1039	int flags = 0;
1040
1041	if (check_fs_read_write(argv[0]))
1042		return;
1043
1044	cmd = argv[0];
1045
1046	extent.e_flags = 0;
1047
1048	while (argc > 2) {
1049		if (!strcmp(argv[1], "--after")) {
1050			argc--;
1051			argv++;
1052			flags |= EXT2_EXTENT_INSERT_AFTER;
1053			continue;
1054		}
1055		if (!strcmp(argv[1], "--uninit")) {
1056			argc--;
1057			argv++;
1058			extent.e_flags |= EXT2_EXTENT_FLAGS_UNINIT;
1059			continue;
1060		}
1061		break;
1062	}
1063
1064	if (argc != 4) {
1065		fprintf(stderr, "usage: %s <lblk> <len> <pblk>\n", cmd);
1066		return;
1067	}
1068
1069	extent.e_lblk = parse_ulong(argv[1], cmd,
1070				    "logical block", &err);
1071	if (err)
1072		return;
1073
1074	extent.e_len = parse_ulong(argv[2], cmd,
1075				    "length", &err);
1076	if (err)
1077		return;
1078
1079	extent.e_pblk = parse_ulong(argv[3], cmd,
1080				    "pysical block", &err);
1081	if (err)
1082		return;
1083
1084	retval = ext2fs_extent_insert(current_handle, flags, &extent);
1085	if (retval) {
1086		com_err(cmd, retval, 0);
1087		return;
1088	}
1089	do_current_node(argc, argv);
1090}
1091
1092void do_print_all(int argc, char **argv)
1093{
1094	struct ext2fs_extent	extent;
1095	errcode_t		retval;
1096	errcode_t		end_err = EXT2_ET_EXTENT_NO_NEXT;
1097	int			op = EXT2_EXTENT_NEXT;
1098	int			first_op = EXT2_EXTENT_ROOT;
1099
1100
1101	if (check_fs_open(argv[0]))
1102		return;
1103
1104	if (!current_handle) {
1105		com_err(argv[0], 0, "Extent handle not open");
1106		return;
1107	}
1108
1109	if (argc > 2) {
1110	print_usage:
1111		fprintf(stderr,
1112			"Usage: %s [--leaf-only|--reverse|--reverse-leaf]\n",
1113			argv[0]);
1114		return;
1115	}
1116
1117	if (argc == 2) {
1118		if (!strcmp(argv[1], "--leaf-only"))
1119			op = EXT2_EXTENT_NEXT_LEAF;
1120		else if (!strcmp(argv[1], "--reverse")) {
1121			op = EXT2_EXTENT_PREV;
1122			first_op = EXT2_EXTENT_LAST_LEAF;
1123			end_err = EXT2_ET_EXTENT_NO_PREV;
1124		} else if (!strcmp(argv[1], "--reverse-leaf")) {
1125			op = EXT2_EXTENT_PREV_LEAF;
1126			first_op = EXT2_EXTENT_LAST_LEAF;
1127			end_err = EXT2_ET_EXTENT_NO_PREV;
1128		} else
1129			  goto print_usage;
1130	}
1131
1132	retval = ext2fs_extent_get(current_handle, first_op, &extent);
1133	if (retval) {
1134		com_err(argv[0], retval, 0);
1135		return;
1136	}
1137	dbg_print_extent(0, &extent);
1138
1139	while (1) {
1140		retval = ext2fs_extent_get(current_handle, op, &extent);
1141		if (retval == end_err)
1142			break;
1143
1144		if (retval) {
1145			com_err(argv[0], retval, 0);
1146			return;
1147		}
1148		dbg_print_extent(0, &extent);
1149	}
1150}
1151
1152void do_info(int argc, char **argv)
1153{
1154	struct ext2fs_extent	extent;
1155	struct ext2_extent_info	info;
1156	errcode_t		retval;
1157
1158	if (check_fs_open(argv[0]))
1159		return;
1160
1161	if (!current_handle) {
1162		com_err(argv[0], 0, "Extent handle not open");
1163		return;
1164	}
1165
1166	retval = ext2fs_extent_get_info(current_handle, &info);
1167	if (retval) {
1168		com_err(argv[0], retval, 0);
1169		return;
1170	}
1171
1172	retval = ext2fs_extent_get(current_handle,
1173				   EXT2_EXTENT_CURRENT, &extent);
1174	if (retval) {
1175		com_err(argv[0], retval, 0);
1176		return;
1177	}
1178
1179	dbg_print_extent(0, &extent);
1180
1181	printf("Current handle location: %d/%d (max: %d, bytes %d), level %d/%d\n",
1182	       info.curr_entry, info.num_entries, info.max_entries,
1183	       info.bytes_avail, info.curr_level, info.max_depth);
1184	printf("\tmax lblk: %llu, max pblk: %llu\n", info.max_lblk,
1185	       info.max_pblk);
1186	printf("\tmax_len: %u, max_uninit_len: %u\n", info.max_len,
1187	       info.max_uninit_len);
1188}
1189
1190void do_goto_block(int argc, char **argv)
1191{
1192	struct ext2fs_extent	extent;
1193	errcode_t		retval;
1194	int			op = EXT2_EXTENT_NEXT_LEAF;
1195	blk_t			blk;
1196	int			level = 0;
1197
1198	if (check_fs_open(argv[0]))
1199		return;
1200
1201	if (!current_handle) {
1202		com_err(argv[0], 0, "Extent handle not open");
1203		return;
1204	}
1205
1206	if (argc < 2 || argc > 3) {
1207		fprintf(stderr, "%s block [level]\n", argv[0]);
1208		return;
1209	}
1210
1211	if (strtoblk(argv[0], argv[1], &blk))
1212		return;
1213
1214	if (argc == 3)
1215		if (strtoblk(argv[0], argv[2], &level))
1216			return;
1217
1218	retval = extent_goto(current_handle, level, (blk64_t) blk);
1219
1220	if (retval) {
1221		com_err(argv[0], retval, "while trying to go to block %lu, level %d",
1222			blk, level);
1223		return;
1224	}
1225
1226	generic_goto_node(argv[0], EXT2_EXTENT_CURRENT);
1227}
1228#endif
1229
1230