1 /*
2 * Copyright (c) 2007 Travis Geiselbrecht
3 *
4 * Use of this source code is governed by a MIT-style
5 * license that can be found in the LICENSE file or at
6 * https://opensource.org/licenses/MIT
7 */
8
9 #include <string.h>
10 #include <stdlib.h>
11 #include <lk/debug.h>
12 #include <lk/trace.h>
13 #include "ext2_priv.h"
14
15 #define LOCAL_TRACE 0
16
ext2_read_block(ext2_t * ext2,void * buf,blocknum_t bnum)17 int ext2_read_block(ext2_t *ext2, void *buf, blocknum_t bnum) {
18 return bcache_read_block(ext2->cache, buf, bnum);
19 }
20
ext2_get_block(ext2_t * ext2,void ** ptr,blocknum_t bnum)21 int ext2_get_block(ext2_t *ext2, void **ptr, blocknum_t bnum) {
22 return bcache_get_block(ext2->cache, ptr, bnum);
23 }
24
ext2_put_block(ext2_t * ext2,blocknum_t bnum)25 int ext2_put_block(ext2_t *ext2, blocknum_t bnum) {
26 return bcache_put_block(ext2->cache, bnum);
27 }
28
ext2_calculate_block_pointer_pos(ext2_t * ext2,blocknum_t block_to_find,uint32_t * level,uint32_t pos[])29 static int ext2_calculate_block_pointer_pos(ext2_t *ext2, blocknum_t block_to_find, uint32_t *level, uint32_t pos[]) {
30 uint32_t block_ptr_per_block, block_ptr_per_2nd_block;
31
32 // XXX optimize this
33
34 // See if it's in the direct blocks
35 if (block_to_find < EXT2_NDIR_BLOCKS) {
36 *level = 0;
37 pos[0] = block_to_find;
38 return 0;
39 }
40
41 block_ptr_per_block = EXT2_ADDR_PER_BLOCK(ext2->sb);
42 block_to_find -= EXT2_NDIR_BLOCKS;
43 // See if it's in the first indirect block
44 if (block_to_find < block_ptr_per_block) {
45 *level = 1;
46 pos[0] = EXT2_IND_BLOCK;
47 pos[1] = block_to_find;
48 return 0;
49 }
50
51 block_to_find -= block_ptr_per_block;
52 block_ptr_per_2nd_block = block_ptr_per_block * block_ptr_per_block;
53 // See if it's in the second indirect block
54 if (block_to_find < (block_ptr_per_2nd_block)) {
55 *level = 2;
56 pos[0] = EXT2_DIND_BLOCK;
57 pos[1] = block_to_find / block_ptr_per_block;
58 pos[2] = block_to_find % block_ptr_per_block;
59 return 0;
60 }
61
62 block_to_find -= block_ptr_per_2nd_block;
63 // See if it's in the third indirect block
64 if (block_to_find < (block_ptr_per_2nd_block * block_ptr_per_block)) {
65 *level = 3;
66 pos[0] = EXT2_TIND_BLOCK;
67 pos[1] = block_to_find / block_ptr_per_2nd_block;
68 pos[2] = (block_to_find % block_ptr_per_2nd_block) / block_ptr_per_block;
69 pos[3] = (block_to_find % block_ptr_per_2nd_block) % block_ptr_per_block;
70 return 0;
71 }
72
73 // The block requested must be too big.
74 return -1;
75 }
76
77 // This function returns a pointer to the cache block that corresponds to the indirect block pointer.
ext2_get_indirect_block_pointer_cache_block(ext2_t * ext2,struct ext2_inode * inode,blocknum_t ** cache_block,uint32_t level,uint32_t pos[],uint * block_loaded)78 static int ext2_get_indirect_block_pointer_cache_block(ext2_t *ext2, struct ext2_inode *inode,
79 blocknum_t **cache_block, uint32_t level, uint32_t pos[], uint *block_loaded) {
80 uint32_t current_level = 0;
81 uint current_block = 0, last_block;
82 blocknum_t *block = NULL;
83 int err;
84
85 if ((level > 3) || (level == 0)) {
86 err = -1;
87 goto error;
88 }
89
90 // Dig down into the indirect blocks. When done, current_block should point to the target.
91 while (current_level < level) {
92 if (current_level == 0) {
93 // read the direct block, simulates a prior loop
94 current_block = LE32(inode->i_block[pos[0]]);
95 }
96
97 if (current_block == 0) {
98 err = -1;
99 goto error;
100 }
101
102 last_block = current_block;
103 current_level++;
104 *block_loaded = current_block;
105
106 err = ext2_get_block(ext2, (void **)(void *)&block, current_block);
107 if (err < 0) {
108 goto error;
109 }
110
111 if (current_level < level) {
112 current_block = LE32(block[pos[current_level]]);
113 ext2_put_block(ext2, last_block);
114 }
115 }
116
117 *cache_block = block;
118 return 0;
119
120 error:
121 *cache_block = NULL;
122 *block_loaded = 0;
123 return err;
124 }
125
126 /* translate a file block to a physical block */
file_block_to_fs_block(ext2_t * ext2,struct ext2_inode * inode,uint fileblock)127 static blocknum_t file_block_to_fs_block(ext2_t *ext2, struct ext2_inode *inode, uint fileblock) {
128 int err;
129 blocknum_t block;
130
131 LTRACEF("inode %p, fileblock %u\n", inode, fileblock);
132
133 uint32_t pos[4];
134 uint32_t level = 0;
135 ext2_calculate_block_pointer_pos(ext2, fileblock, &level, pos);
136
137 LTRACEF("level %d, pos 0x%x 0x%x 0x%x 0x%x\n", level, pos[0], pos[1], pos[2], pos[3]);
138
139 if (level == 0) {
140 /* direct block, just return it directly */
141 block = LE32(inode->i_block[fileblock]);
142 } else {
143 /* at least one level of indirection, get a pointer to the final indirect block table and dereference it */
144 blocknum_t *ind_table;
145 blocknum_t phys_block;
146 err = ext2_get_indirect_block_pointer_cache_block(ext2, inode, &ind_table, level, pos, &phys_block);
147 if (err < 0)
148 return 0;
149
150 /* dereference the final entry in the final table */
151 block = LE32(ind_table[pos[level]]);
152 LTRACEF("block %u, indirect_block %u\n", block, phys_block);
153
154 /* release the ref on the cache block */
155 ext2_put_block(ext2, phys_block);
156 }
157
158 LTRACEF("returning %u\n", block);
159
160 return block;
161 }
162
ext2_read_inode(ext2_t * ext2,struct ext2_inode * inode,void * _buf,off_t offset,size_t len)163 ssize_t ext2_read_inode(ext2_t *ext2, struct ext2_inode *inode, void *_buf, off_t offset, size_t len) {
164 int err = 0;
165 size_t bytes_read = 0;
166 uint8_t *buf = _buf;
167
168 /* calculate the file size */
169 off_t file_size = ext2_file_len(ext2, inode);
170
171 LTRACEF("inode %p, offset %lld, len %zd, file_size %lld\n", inode, offset, len, file_size);
172
173 /* trim the read */
174 if (offset > file_size)
175 return 0;
176 if ((off_t)(offset + len) >= file_size)
177 len = file_size - offset;
178 if (len == 0)
179 return 0;
180
181 /* calculate the starting file block */
182 uint file_block = offset / EXT2_BLOCK_SIZE(ext2->sb);
183
184 /* handle partial first block */
185 if ((offset % EXT2_BLOCK_SIZE(ext2->sb)) != 0) {
186 uint8_t temp[EXT2_BLOCK_SIZE(ext2->sb)];
187
188 /* calculate the block and read it */
189 blocknum_t phys_block = file_block_to_fs_block(ext2, inode, file_block);
190 if (phys_block == 0) {
191 memset(temp, 0, EXT2_BLOCK_SIZE(ext2->sb));
192 } else {
193 ext2_read_block(ext2, temp, phys_block);
194 }
195
196 /* copy out what we need */
197 size_t block_offset = offset % EXT2_BLOCK_SIZE(ext2->sb);
198 size_t tocopy = MIN(len, EXT2_BLOCK_SIZE(ext2->sb) - block_offset);
199 memcpy(buf, temp + block_offset, tocopy);
200
201 /* increment our stuff */
202 file_block++;
203 len -= tocopy;
204 bytes_read += tocopy;
205 buf += tocopy;
206 }
207
208 /* handle middle blocks */
209 while (len >= EXT2_BLOCK_SIZE(ext2->sb)) {
210 /* calculate the block and read it */
211 blocknum_t phys_block = file_block_to_fs_block(ext2, inode, file_block);
212 if (phys_block == 0) {
213 memset(buf, 0, EXT2_BLOCK_SIZE(ext2->sb));
214 } else {
215 ext2_read_block(ext2, buf, phys_block);
216 }
217
218 /* increment our stuff */
219 file_block++;
220 len -= EXT2_BLOCK_SIZE(ext2->sb);
221 bytes_read += EXT2_BLOCK_SIZE(ext2->sb);
222 buf += EXT2_BLOCK_SIZE(ext2->sb);
223 }
224
225 /* handle partial last block */
226 if (len > 0) {
227 uint8_t temp[EXT2_BLOCK_SIZE(ext2->sb)];
228
229 /* calculate the block and read it */
230 blocknum_t phys_block = file_block_to_fs_block(ext2, inode, file_block);
231 if (phys_block == 0) {
232 memset(temp, 0, EXT2_BLOCK_SIZE(ext2->sb));
233 } else {
234 ext2_read_block(ext2, temp, phys_block);
235 }
236
237 /* copy out what we need */
238 memcpy(buf, temp, len);
239
240 /* increment our stuff */
241 bytes_read += len;
242 }
243
244 LTRACEF("err %d, bytes_read %zu\n", err, bytes_read);
245
246 return (err < 0) ? err : (ssize_t)bytes_read;
247 }
248
249