1 /*
2 * The logical block -> physical block routine.
3 *
4 * Copyright (C) 2009 Liu Aleaxander -- All rights reserved. This file
5 * may be redistributed under the terms of the GNU Public License.
6 */
7
8 #include <stdio.h>
9 #include <dprintf.h>
10 #include <fs.h>
11 #include <disk.h>
12 #include <cache.h>
13 #include "ext2_fs.h"
14
15 static const struct ext4_extent_header *
ext4_find_leaf(struct fs_info * fs,const struct ext4_extent_header * eh,block_t block)16 ext4_find_leaf(struct fs_info *fs, const struct ext4_extent_header *eh,
17 block_t block)
18 {
19 struct ext4_extent_idx *index;
20 block_t blk;
21 int i;
22
23 while (1) {
24 if (eh->eh_magic != EXT4_EXT_MAGIC)
25 return NULL;
26 if (eh->eh_depth == 0)
27 return eh;
28
29 index = EXT4_FIRST_INDEX(eh);
30 for (i = 0; i < (int)eh->eh_entries; i++) {
31 if (block < index[i].ei_block)
32 break;
33 }
34 if (--i < 0)
35 return NULL;
36
37 blk = index[i].ei_leaf_hi;
38 blk = (blk << 32) + index[i].ei_leaf_lo;
39 eh = get_cache(fs->fs_dev, blk);
40 }
41 }
42
43 /* handle the ext4 extents to get the phsical block number */
44 /* XXX: still need to handle sparse files with extents */
45 static block_t
bmap_extent(struct inode * inode,uint32_t block,size_t * nblocks)46 bmap_extent(struct inode *inode, uint32_t block, size_t *nblocks)
47 {
48 struct fs_info *fs = inode->fs;
49 const struct ext4_extent_header *leaf;
50 const struct ext4_extent *ext;
51 int i;
52 block_t start;
53
54 leaf = ext4_find_leaf(fs, &PVT(inode)->i_extent_hdr, block);
55 if (!leaf) {
56 printf("ERROR, extent leaf not found\n");
57 return 0;
58 }
59
60 ext = EXT4_FIRST_EXTENT(leaf);
61 for (i = 0; i < leaf->eh_entries; i++) {
62 if (block < ext[i].ee_block)
63 break;
64 }
65 if (--i < 0) {
66 printf("ERROR, not find the right block\n");
67 return 0;
68 }
69
70 /* got it */
71 block -= ext[i].ee_block;
72 if (block >= ext[i].ee_len)
73 return 0;
74 start = ((block_t)ext[i].ee_start_hi << 32) + ext[i].ee_start_lo;
75
76 if (nblocks)
77 *nblocks = ext[i].ee_len - block;
78
79 return start + block;
80 }
81
82 /*
83 * Scan forward in a range of blocks to see if they are contiguous,
84 * then return the initial value.
85 */
86 static uint32_t
scan_set_nblocks(const uint32_t * map,unsigned int count,size_t * nblocks)87 scan_set_nblocks(const uint32_t *map, unsigned int count, size_t *nblocks)
88 {
89 uint32_t blk = *map;
90
91 if (nblocks) {
92 uint32_t skip = blk ? 1 : 0;
93 uint32_t next = blk + skip;
94 size_t cnt = 1;
95
96 while (--count) {
97 map++;
98 if (*map == next) {
99 cnt++;
100 next += skip;
101 } else {
102 break;
103 }
104 }
105
106 *nblocks = cnt;
107 }
108
109 return blk;
110 }
111
112 /*
113 * The actual indirect block map handling - the block passed in should
114 * be relative to the beginning of the particular block hierarchy.
115 */
116 static block_t
bmap_indirect(struct fs_info * fs,uint32_t start,uint32_t block,int levels,size_t * nblocks)117 bmap_indirect(struct fs_info *fs, uint32_t start, uint32_t block,
118 int levels, size_t *nblocks)
119 {
120 int addr_shift = BLOCK_SHIFT(fs) - 2;
121 uint32_t addr_count = 1 << addr_shift;
122 const uint32_t *blk = NULL;
123 uint32_t index = 0;
124
125 while (levels--) {
126 if (!start) {
127 if (nblocks)
128 *nblocks = addr_count << (levels * addr_shift);
129 return 0;
130 }
131 blk = get_cache(fs->fs_dev, start);
132 index = (block >> (levels * addr_shift)) & (addr_count - 1);
133 start = blk[index];
134 }
135
136 return scan_set_nblocks(blk + index, addr_count - index, nblocks);
137 }
138
139 /*
140 * Handle the traditional block map, like indirect, double indirect
141 * and triple indirect
142 */
143 static block_t
bmap_traditional(struct inode * inode,block_t block,size_t * nblocks)144 bmap_traditional(struct inode *inode, block_t block, size_t *nblocks)
145 {
146 struct fs_info *fs = inode->fs;
147 const uint32_t addr_per_block = BLOCK_SIZE(fs) >> 2;
148 const int shft_per_block = BLOCK_SHIFT(fs) - 2;
149 const uint32_t direct_blocks = EXT2_NDIR_BLOCKS;
150 const uint32_t indirect_blocks = addr_per_block;
151 const uint32_t double_blocks = addr_per_block << shft_per_block;
152 const uint32_t triple_blocks = double_blocks << shft_per_block;
153
154 /* direct blocks */
155 if (block < direct_blocks)
156 return scan_set_nblocks(&PVT(inode)->i_block[block],
157 direct_blocks - block, nblocks);
158
159 /* indirect blocks */
160 block -= direct_blocks;
161 if (block < indirect_blocks)
162 return bmap_indirect(fs, PVT(inode)->i_block[EXT2_IND_BLOCK],
163 block, 1, nblocks);
164
165 /* double indirect blocks */
166 block -= indirect_blocks;
167 if (block < double_blocks)
168 return bmap_indirect(fs, PVT(inode)->i_block[EXT2_DIND_BLOCK],
169 block, 2, nblocks);
170
171 /* triple indirect block */
172 block -= double_blocks;
173 if (block < triple_blocks)
174 return bmap_indirect(fs, PVT(inode)->i_block[EXT2_TIND_BLOCK],
175 block, 3, nblocks);
176
177 /* This can't happen... */
178 return 0;
179 }
180
181
182 /**
183 * Map the logical block to physic block where the file data stores.
184 * In EXT4, there are two ways to handle the map process, extents and indirect.
185 * EXT4 uses a inode flag to mark extent file and indirect block file.
186 *
187 * @fs: the fs_info structure.
188 * @inode: the inode structure.
189 * @block: the logical block to be mapped.
190 * @nblocks: optional pointer to number of contiguous blocks (low estimate)
191 * @retrun: the physical block number.
192 *
193 */
ext2_bmap(struct inode * inode,block_t block,size_t * nblocks)194 block_t ext2_bmap(struct inode *inode, block_t block, size_t *nblocks)
195 {
196 block_t ret;
197
198 if (inode->flags & EXT4_EXTENTS_FLAG)
199 ret = bmap_extent(inode, block, nblocks);
200 else
201 ret = bmap_traditional(inode, block, nblocks);
202
203 return ret;
204 }
205
206
207 /*
208 * Next extent for getfssec
209 */
ext2_next_extent(struct inode * inode,uint32_t lstart)210 int ext2_next_extent(struct inode *inode, uint32_t lstart)
211 {
212 struct fs_info *fs = inode->fs;
213 int blktosec = BLOCK_SHIFT(fs) - SECTOR_SHIFT(fs);
214 int blkmask = (1 << blktosec) - 1;
215 block_t block;
216 size_t nblocks = 0;
217
218 block = ext2_bmap(inode, lstart >> blktosec, &nblocks);
219
220 if (!block)
221 inode->next_extent.pstart = EXTENT_ZERO;
222 else
223 inode->next_extent.pstart =
224 ((sector_t)block << blktosec) | (lstart & blkmask);
225
226 inode->next_extent.len = (nblocks << blktosec) - (lstart & blkmask);
227 return 0;
228 }
229