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