source: mainline/uspace/lib/ext4/libext4_extent.c@ 9463b245

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 9463b245 was 30ac3c3, checked in by Frantisek Princ <frantisek.princ@…>, 13 years ago

some debugging modifications, not yet completely debugged binary search in index node
  • Property mode set to 100644
File size: 9.4 KB
Line 
1/*
2 * Copyright (c) 2011 Frantisek Princ
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup libext4
30 * @{
31 */
32
33/**
34 * @file libext4_extent.c
35 * @brief Ext4 extent structures operations.
36 */
37
38#include <byteorder.h>
39#include <errno.h>
40#include <malloc.h>
41#include "libext4.h"
42
43uint32_t ext4_extent_get_first_block(ext4_extent_t *extent)
44{
45 return uint32_t_le2host(extent->first_block);
46}
47
48void ext4_extent_set_first_block(ext4_extent_t *extent, uint32_t first_block)
49{
50 extent->first_block = host2uint32_t_le(first_block);
51}
52
53uint16_t ext4_extent_get_block_count(ext4_extent_t *extent)
54{
55 return uint16_t_le2host(extent->block_count);
56}
57
58void ext4_extent_set_block_count(ext4_extent_t *extent, uint16_t block_count)
59{
60 extent->block_count = host2uint16_t_le(block_count);
61}
62
63uint64_t ext4_extent_get_start(ext4_extent_t *extent)
64{
65 return ((uint64_t)uint16_t_le2host(extent->start_hi)) << 32 |
66 ((uint64_t)uint32_t_le2host(extent->start_lo));
67}
68
69void ext4_extent_set_start(ext4_extent_t *extent, uint64_t start)
70{
71 extent->start_lo = host2uint32_t_le((start << 32) >> 32);
72 extent->start_hi = host2uint16_t_le((uint16_t)(start >> 32));
73}
74
75uint32_t ext4_extent_index_get_first_block(ext4_extent_index_t *index)
76{
77 return uint32_t_le2host(index->first_block);
78}
79
80void ext4_extent_index_set_first_block(ext4_extent_index_t *index,
81 uint32_t first)
82{
83 index->first_block = host2uint32_t_le(first);
84}
85
86uint64_t ext4_extent_index_get_leaf(ext4_extent_index_t *index)
87{
88 return ((uint64_t)uint16_t_le2host(index->leaf_hi)) << 32 |
89 ((uint64_t)uint32_t_le2host(index->leaf_lo));
90}
91
92void ext4_extent_index_set_leaf(ext4_extent_index_t *index, uint64_t leaf)
93{
94 index->leaf_lo = host2uint32_t_le((leaf << 32) >> 32);
95 index->leaf_hi = host2uint16_t_le((uint16_t)(leaf >> 32));
96}
97
98uint16_t ext4_extent_header_get_magic(ext4_extent_header_t *header)
99{
100 return uint16_t_le2host(header->magic);
101}
102
103void ext4_extent_header_set_magic(ext4_extent_header_t *header, uint16_t magic)
104{
105 header->magic = host2uint16_t_le(magic);
106}
107
108uint16_t ext4_extent_header_get_entries_count(ext4_extent_header_t *header)
109{
110 return uint16_t_le2host(header->entries_count);
111}
112
113void ext4_extent_header_set_entries_count(ext4_extent_header_t *header,
114 uint16_t count)
115{
116 header->entries_count = host2uint16_t_le(count);
117}
118
119uint16_t ext4_extent_header_get_max_entries_count(ext4_extent_header_t *header)
120{
121 return uint16_t_le2host(header->max_entries_count);
122}
123
124void ext4_extent_header_set_max_entries_count(ext4_extent_header_t *header,
125 uint16_t max_count)
126{
127 header->max_entries_count = host2uint16_t_le(max_count);
128}
129
130uint16_t ext4_extent_header_get_depth(ext4_extent_header_t *header)
131{
132 return uint16_t_le2host(header->depth);
133}
134
135void ext4_extent_header_set_depth(ext4_extent_header_t *header, uint16_t depth)
136{
137 header->depth = host2uint16_t_le(depth);
138}
139
140uint32_t ext4_extent_header_get_generation(ext4_extent_header_t *header)
141{
142 return uint32_t_le2host(header->generation);
143}
144
145void ext4_extent_header_set_generation(ext4_extent_header_t *header,
146 uint32_t generation)
147{
148 header->generation = host2uint32_t_le(generation);
149}
150
151//static void ext4_extent_binsearch_idx(ext4_extent_header_t *header,
152// ext4_extent_index_t **index, uint32_t iblock)
153//{
154// ext4_extent_index_t *r, *l, *m;
155//
156// uint16_t entries_count = ext4_extent_header_get_entries_count(header);
157// l = EXT4_EXTENT_FIRST_INDEX(header) + 1;
158// r = l + entries_count - 1;
159//
160// while (l <= r) {
161// m = l + (r - l) / 2;
162// uint32_t block = ext4_extent_index_get_first_block(m);
163// if (iblock < block) {
164// r = m - 1;
165// } else {
166// l = m + 1;
167// }
168// }
169//
170// *index = l - 1;
171//}
172//
173static void ext4_extent_binsearch(ext4_extent_header_t *header,
174 ext4_extent_t **extent, uint32_t iblock)
175{
176 ext4_extent_t *r, *l, *m;
177
178 uint16_t entries_count = ext4_extent_header_get_entries_count(header);
179
180 if (entries_count == 0) {
181 // this leaf is empty
182 return;
183 }
184
185 l = EXT4_EXTENT_FIRST(header) + 1;
186 r = l + entries_count - 1;
187
188 while (l <= r) {
189 m = l + (r - l) / 2;
190 uint32_t block = ext4_extent_get_first_block(m);
191 if (iblock < block) {
192 r = m - 1;
193 } else {
194 l = m + 1;
195 }
196 }
197
198 *extent = l - 1;
199
200}
201
202static int ext4_extent_find_extent(ext4_filesystem_t *fs,
203 ext4_inode_ref_t *inode_ref, uint32_t iblock, ext4_extent_t **ret_extent)
204{
205 int rc;
206
207 block_t* block = NULL;
208
209 ext4_extent_header_t *header = ext4_inode_get_extent_header(inode_ref->inode);
210 while (ext4_extent_header_get_depth(header) != 0) {
211
212// ext4_extent_path_t path2;
213// path2.header = header;
214// path2.index = NULL;
215// ext4_extent_binsearch_idx(header, &path2.index, iblock);
216//
217// uint64_t child = ext4_extent_index_get_leaf(path2.index);
218// if (block != NULL) {
219// block_put(block);
220// }
221//
222// rc = block_get(&block, fs->device, child, BLOCK_FLAGS_NONE);
223// if (rc != EOK) {
224// return rc;
225// }
226//
227// header = block->data;
228// break;
229
230
231 ext4_extent_index_t *extent_index = EXT4_EXTENT_FIRST_INDEX(header);
232
233 for (uint16_t i = 0; i < ext4_extent_header_get_entries_count(header); ++i, extent_index++) {
234 if (iblock >= ext4_extent_index_get_first_block(extent_index)) {
235
236 uint64_t child = ext4_extent_index_get_leaf(extent_index);
237
238 if (block != NULL) {
239 block_put(block);
240 }
241
242 rc = block_get(&block, fs->device, child, BLOCK_FLAGS_NONE);
243 if (rc != EOK) {
244 return rc;
245 }
246
247 header = (ext4_extent_header_t *)block->data;
248 break;
249 }
250 }
251 }
252
253
254 ext4_extent_path_t path;
255
256 path.header = header;
257 path.extent = NULL;
258
259 ext4_extent_binsearch(path.header, &path.extent, iblock);
260
261 *ret_extent = path.extent;
262
263 return EOK;
264}
265
266int ext4_extent_find_block(ext4_filesystem_t *fs,
267 ext4_inode_ref_t *inode_ref, uint32_t iblock, uint32_t *fblock)
268{
269 int rc;
270
271 ext4_extent_t *extent = NULL;
272 rc = ext4_extent_find_extent(fs, inode_ref, iblock, &extent);
273 if (rc != EOK) {
274 return rc;
275 }
276
277 uint32_t phys_block;
278 phys_block = ext4_extent_get_start(extent) + iblock;
279 phys_block -= ext4_extent_get_first_block(extent);
280
281
282 *fblock = phys_block;
283
284 return EOK;
285
286
287// ext4_extent_header_t *eh =
288// ext4_inode_get_extent_header(inode_ref->inode);
289//
290// uint16_t depth = ext4_extent_header_get_depth(eh);
291//
292// ext4_extent_path_t *tmp_path;
293//
294// // Added 2 for possible tree growing
295// tmp_path = malloc(sizeof(ext4_extent_path_t) * (depth + 2));
296// if (tmp_path == NULL) {
297// *path = NULL;
298// return ENOMEM;
299// }
300//
301// tmp_path[0].block = inode_ref->block;
302// tmp_path[0].header = eh;
303//
304// uint16_t pos = 0;
305// while (ext4_extent_header_get_depth(eh) != 0) {
306//
307// EXT4FS_DBG("count == \%u", ext4_extent_header_get_entries_count(eh));
308//
309// ext4_extent_binsearch_idx(tmp_path + pos, iblock);
310//
311// uint32_t offset = (void *)tmp_path[pos].index - (void *)EXT4_EXTENT_FIRST_INDEX(eh);
312//
313// EXT4FS_DBG("offset = \%u", offset);
314//
315// EXT4FS_DBG("first block = \%u, leaf = \%u",
316// ext4_extent_index_get_first_block(tmp_path[pos].index),
317// (uint32_t)ext4_extent_index_get_leaf(tmp_path[pos].index));
318//
319// tmp_path[pos].depth = depth;
320// tmp_path[pos].extent = NULL;
321//
322// assert(tmp_path[pos].index != NULL);
323//
324// uint64_t fblock = ext4_extent_index_get_leaf(tmp_path[pos].index);
325//
326// EXT4FS_DBG("fblock = \%u", (uint32_t)fblock);
327//
328// block_t *block;
329// rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE);
330// if (rc != EOK) {
331// // TODO cleanup
332// EXT4FS_DBG("ERRRR");
333// return rc;
334// }
335//
336// EXT4FS_DBG("block loaded");
337//
338// pos++;
339//
340// eh = (ext4_extent_header_t *)block->data;
341// tmp_path[pos].block = block;
342// tmp_path[pos].header = eh;
343//
344// }
345//
346// tmp_path[pos].depth = 0;
347// tmp_path[pos].extent = NULL;
348// tmp_path[pos].index = NULL;
349//
350// EXT4FS_DBG("pos = \%u", pos);
351//
352// /* find extent */
353// ext4_extent_binsearch(tmp_path + pos, iblock);
354//
355// EXT4FS_DBG("after binsearch in extent");
356//
357// /* if not an empty leaf */
358// if (tmp_path[pos].extent) {
359// EXT4FS_DBG("nonempty leaf");
360//
361//// uint64_t fblock = ext4_extent_get_start(tmp_path[pos].extent);
362//// block_t *block;
363//// rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE);
364//// if (rc != EOK) {
365//// // TODO cleanup
366//// }
367//// tmp_path[pos].block = block;
368// }
369//
370// *path = tmp_path;
371//
372// return EOK;
373}
374
375/**
376 * @}
377 */
Note: See TracBrowser for help on using the repository browser.