3 * ReiserFS file system driver code.
7 * Copyright (c) 2006 Christoph Pfisterer
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * as published by the Free Software Foundation; either version 2
12 * of the License, or (at your option) any later version.
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
24 #include "fsw_reiserfs.h"
29 static fsw_status_t
fsw_reiserfs_volume_mount(struct fsw_reiserfs_volume
*vol
);
30 static void fsw_reiserfs_volume_free(struct fsw_reiserfs_volume
*vol
);
31 static fsw_status_t
fsw_reiserfs_volume_stat(struct fsw_reiserfs_volume
*vol
, struct fsw_volume_stat
*sb
);
33 static fsw_status_t
fsw_reiserfs_dnode_fill(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
);
34 static void fsw_reiserfs_dnode_free(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
);
35 static fsw_status_t
fsw_reiserfs_dnode_stat(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
,
36 struct fsw_dnode_stat
*sb
);
37 static fsw_status_t
fsw_reiserfs_get_extent(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
,
38 struct fsw_extent
*extent
);
40 static fsw_status_t
fsw_reiserfs_dir_lookup(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
,
41 struct fsw_string
*lookup_name
, struct fsw_reiserfs_dnode
**child_dno
);
42 static fsw_status_t
fsw_reiserfs_dir_read(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
,
43 struct fsw_shandle
*shand
, struct fsw_reiserfs_dnode
**child_dno
);
45 static fsw_status_t
fsw_reiserfs_readlink(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
,
46 struct fsw_string
*link
);
48 static fsw_status_t
fsw_reiserfs_item_search(struct fsw_reiserfs_volume
*vol
,
49 fsw_u32 dir_id
, fsw_u32 objectid
, fsw_u64 offset
,
50 struct fsw_reiserfs_item
*item
);
51 static fsw_status_t
fsw_reiserfs_item_next(struct fsw_reiserfs_volume
*vol
,
52 struct fsw_reiserfs_item
*item
);
53 static void fsw_reiserfs_item_release(struct fsw_reiserfs_volume
*vol
,
54 struct fsw_reiserfs_item
*item
);
60 struct fsw_fstype_table
FSW_FSTYPE_TABLE_NAME(reiserfs
) = {
61 { FSW_STRING_TYPE_ISO88591
, 8, 8, "reiserfs" },
62 sizeof(struct fsw_reiserfs_volume
),
63 sizeof(struct fsw_reiserfs_dnode
),
65 fsw_reiserfs_volume_mount
,
66 fsw_reiserfs_volume_free
,
67 fsw_reiserfs_volume_stat
,
68 fsw_reiserfs_dnode_fill
,
69 fsw_reiserfs_dnode_free
,
70 fsw_reiserfs_dnode_stat
,
71 fsw_reiserfs_get_extent
,
72 fsw_reiserfs_dir_lookup
,
73 fsw_reiserfs_dir_read
,
74 fsw_reiserfs_readlink
,
79 static fsw_u32 superblock_offsets
[3] = {
80 REISERFS_DISK_OFFSET_IN_BYTES
>> REISERFS_SUPERBLOCK_BLOCKSIZEBITS
,
81 REISERFS_OLD_DISK_OFFSET_IN_BYTES
>> REISERFS_SUPERBLOCK_BLOCKSIZEBITS
,
86 * Mount an reiserfs volume. Reads the superblock and constructs the
87 * root directory dnode.
90 static fsw_status_t
fsw_reiserfs_volume_mount(struct fsw_reiserfs_volume
*vol
)
98 // allocate memory to keep the superblock around
99 status
= fsw_alloc(sizeof(struct reiserfs_super_block
), &vol
->sb
);
103 // read the superblock into its buffer
104 fsw_set_blocksize(vol
, REISERFS_SUPERBLOCK_BLOCKSIZE
, REISERFS_SUPERBLOCK_BLOCKSIZE
);
105 for (i
= 0; superblock_offsets
[i
]; i
++) {
106 status
= fsw_block_get(vol
, superblock_offsets
[i
], 0, &buffer
);
109 fsw_memcpy(vol
->sb
, buffer
, sizeof(struct reiserfs_super_block
));
110 fsw_block_release(vol
, superblock_offsets
[i
], buffer
);
112 // check for one of the magic strings
113 if (fsw_memeq(vol
->sb
->s_v1
.s_magic
,
114 REISERFS_SUPER_MAGIC_STRING
, 8)) {
115 vol
->version
= REISERFS_VERSION_1
;
117 } else if (fsw_memeq(vol
->sb
->s_v1
.s_magic
,
118 REISER2FS_SUPER_MAGIC_STRING
, 9)) {
119 vol
->version
= REISERFS_VERSION_2
;
121 } else if (fsw_memeq(vol
->sb
->s_v1
.s_magic
,
122 REISER2FS_JR_SUPER_MAGIC_STRING
, 9)) {
123 vol
->version
= vol
->sb
->s_v1
.s_version
;
124 if (vol
->version
== REISERFS_VERSION_1
|| vol
->version
== REISERFS_VERSION_2
)
128 if (superblock_offsets
[i
] == 0)
129 return FSW_UNSUPPORTED
;
131 // check the superblock
132 if (vol
->sb
->s_v1
.s_root_block
== -1) // unfinished 'reiserfsck --rebuild-tree'
133 return FSW_VOLUME_CORRUPTED
;
136 if (vol->sb->s_rev_level != EXT2_GOOD_OLD_REV &&
137 vol->sb->s_rev_level != EXT2_DYNAMIC_REV)
138 return FSW_UNSUPPORTED;
139 if (vol->sb->s_rev_level == EXT2_DYNAMIC_REV &&
140 (vol->sb->s_feature_incompat & ~(EXT2_FEATURE_INCOMPAT_FILETYPE | EXT3_FEATURE_INCOMPAT_RECOVER)))
141 return FSW_UNSUPPORTED;
144 // set real blocksize
145 blocksize
= vol
->sb
->s_v1
.s_blocksize
;
146 fsw_set_blocksize(vol
, blocksize
, blocksize
);
148 // get other info from superblock
150 vol->ind_bcnt = EXT2_ADDR_PER_BLOCK(vol->sb);
151 vol->dind_bcnt = vol->ind_bcnt * vol->ind_bcnt;
152 vol->inode_size = EXT2_INODE_SIZE(vol->sb);
155 for (i
= 0; i
< 16; i
++)
156 if (vol
->sb
->s_label
[i
] == 0)
158 s
.type
= FSW_STRING_TYPE_ISO88591
;
160 s
.data
= vol
->sb
->s_label
;
161 status
= fsw_strdup_coerce(&vol
->g
.label
, vol
->g
.host_string_type
, &s
);
165 // setup the root dnode
166 status
= fsw_dnode_create_root(vol
, REISERFS_ROOT_OBJECTID
, &vol
->g
.root
);
169 vol
->g
.root
->dir_id
= REISERFS_ROOT_PARENT_OBJECTID
;
171 FSW_MSG_DEBUG((FSW_MSGSTR("fsw_reiserfs_volume_mount: success, blocksize %d tree height %d\n"),
172 blocksize
, vol
->sb
->s_v1
.s_tree_height
));
178 * Free the volume data structure. Called by the core after an unmount or after
179 * an unsuccessful mount to release the memory used by the file system type specific
180 * part of the volume structure.
183 static void fsw_reiserfs_volume_free(struct fsw_reiserfs_volume
*vol
)
190 * Get in-depth information on a volume.
193 static fsw_status_t
fsw_reiserfs_volume_stat(struct fsw_reiserfs_volume
*vol
, struct fsw_volume_stat
*sb
)
195 sb
->total_bytes
= (fsw_u64
)vol
->sb
->s_v1
.s_block_count
* vol
->g
.log_blocksize
;
196 sb
->free_bytes
= (fsw_u64
)vol
->sb
->s_v1
.s_free_blocks
* vol
->g
.log_blocksize
;
201 * Get full information on a dnode from disk. This function is called by the core
202 * whenever it needs to access fields in the dnode structure that may not
203 * be filled immediately upon creation of the dnode. In the case of reiserfs, we
204 * delay fetching of the stat data until dnode_fill is called. The size and
205 * type fields are invalid until this function has been called.
208 static fsw_status_t
fsw_reiserfs_dnode_fill(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
)
211 fsw_u32 item_len
, mode
;
212 struct fsw_reiserfs_item item
;
214 if (dno
->sd_v1
|| dno
->sd_v2
)
217 FSW_MSG_DEBUG((FSW_MSGSTR("fsw_reiserfs_dnode_fill: object %d/%d\n"), dno
->dir_id
, dno
->g
.dnode_id
));
219 // find stat data item in reiserfs tree
220 status
= fsw_reiserfs_item_search(vol
, dno
->dir_id
, dno
->g
.dnode_id
, 0, &item
);
221 if (status
== FSW_NOT_FOUND
) {
222 FSW_MSG_ASSERT((FSW_MSGSTR("fsw_reiserfs_dnode_fill: cannot find stat_data for object %d/%d\n"),
223 dno
->dir_id
, dno
->g
.dnode_id
));
224 return FSW_VOLUME_CORRUPTED
;
228 if (item
.item_offset
!= 0) {
229 FSW_MSG_ASSERT((FSW_MSGSTR("fsw_reiserfs_dnode_fill: got item that's not stat_data\n")));
230 fsw_reiserfs_item_release(vol
, &item
);
231 return FSW_VOLUME_CORRUPTED
;
233 item_len
= item
.ih
.ih_item_len
;
235 // get data in appropriate version
236 if (item
.ih
.ih_version
== KEY_FORMAT_3_5
&& item_len
== SD_V1_SIZE
) {
237 // have stat_data_v1 structure
238 status
= fsw_memdup((void **)&dno
->sd_v1
, item
.item_data
, item_len
);
239 fsw_reiserfs_item_release(vol
, &item
);
243 // get info from the inode
244 dno
->g
.size
= dno
->sd_v1
->sd_size
;
245 mode
= dno
->sd_v1
->sd_mode
;
247 } else if (item
.ih
.ih_version
== KEY_FORMAT_3_6
&& item_len
== SD_V2_SIZE
) {
248 // have stat_data_v2 structure
249 status
= fsw_memdup((void **)&dno
->sd_v2
, item
.item_data
, item_len
);
250 fsw_reiserfs_item_release(vol
, &item
);
254 // get info from the inode
255 dno
->g
.size
= dno
->sd_v2
->sd_size
;
256 mode
= dno
->sd_v2
->sd_mode
;
259 FSW_MSG_ASSERT((FSW_MSGSTR("fsw_reiserfs_dnode_fill: version %d(%d) and size %d(%d) not recognized for stat_data\n"),
260 item
.ih
.ih_version
, KEY_FORMAT_3_6
, item_len
, SD_V2_SIZE
));
261 fsw_reiserfs_item_release(vol
, &item
);
262 return FSW_VOLUME_CORRUPTED
;
265 // get node type from mode field
267 dno
->g
.type
= FSW_DNODE_TYPE_FILE
;
268 else if (S_ISDIR(mode
))
269 dno
->g
.type
= FSW_DNODE_TYPE_DIR
;
270 else if (S_ISLNK(mode
))
271 dno
->g
.type
= FSW_DNODE_TYPE_SYMLINK
;
273 dno
->g
.type
= FSW_DNODE_TYPE_SPECIAL
;
279 * Free the dnode data structure. Called by the core when deallocating a dnode
280 * structure to release the memory used by the file system type specific part
281 * of the dnode structure.
284 static void fsw_reiserfs_dnode_free(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
)
287 fsw_free(dno
->sd_v1
);
289 fsw_free(dno
->sd_v2
);
293 * Get in-depth information on a dnode. The core makes sure that fsw_reiserfs_dnode_fill
294 * has been called on the dnode before this function is called. Note that some
295 * data is not directly stored into the structure, but passed to a host-specific
296 * callback that converts it to the host-specific format.
299 static fsw_status_t
fsw_reiserfs_dnode_stat(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
,
300 struct fsw_dnode_stat
*sb
)
303 if (dno
->g
.type
== FSW_DNODE_TYPE_SPECIAL
)
306 sb
->used_bytes
= dno
->sd_v1
->u
.sd_blocks
* vol
->g
.log_blocksize
;
307 sb
->store_time_posix(sb
, FSW_DNODE_STAT_CTIME
, dno
->sd_v1
->sd_ctime
);
308 sb
->store_time_posix(sb
, FSW_DNODE_STAT_ATIME
, dno
->sd_v1
->sd_atime
);
309 sb
->store_time_posix(sb
, FSW_DNODE_STAT_MTIME
, dno
->sd_v1
->sd_mtime
);
310 sb
->store_attr_posix(sb
, dno
->sd_v1
->sd_mode
);
311 } else if (dno
->sd_v2
) {
312 sb
->used_bytes
= dno
->sd_v2
->sd_blocks
* vol
->g
.log_blocksize
;
313 sb
->store_time_posix(sb
, FSW_DNODE_STAT_CTIME
, dno
->sd_v2
->sd_ctime
);
314 sb
->store_time_posix(sb
, FSW_DNODE_STAT_ATIME
, dno
->sd_v2
->sd_atime
);
315 sb
->store_time_posix(sb
, FSW_DNODE_STAT_MTIME
, dno
->sd_v2
->sd_mtime
);
316 sb
->store_attr_posix(sb
, dno
->sd_v2
->sd_mode
);
323 * Retrieve file data mapping information. This function is called by the core when
324 * fsw_shandle_read needs to know where on the disk the required piece of the file's
325 * data can be found. The core makes sure that fsw_reiserfs_dnode_fill has been called
326 * on the dnode before. Our task here is to get the physical disk block number for
327 * the requested logical block number.
330 static fsw_status_t
fsw_reiserfs_get_extent(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
,
331 struct fsw_extent
*extent
)
334 fsw_u64 search_offset
, intra_offset
;
335 struct fsw_reiserfs_item item
;
336 fsw_u32 intra_bno
, nr_item
;
338 // Preconditions: The caller has checked that the requested logical block
339 // is within the file's size. The dnode has complete information, i.e.
340 // fsw_reiserfs_dnode_read_info was called successfully on it.
342 FSW_MSG_DEBUG((FSW_MSGSTR("fsw_reiserfs_get_extent: mapping block %d of object %d/%d\n"),
343 extent
->log_start
, dno
->dir_id
, dno
->g
.dnode_id
));
345 extent
->type
= FSW_EXTENT_TYPE_SPARSE
;
346 extent
->log_count
= 1;
348 // get the item for the requested block
349 search_offset
= (fsw_u64
)extent
->log_start
* vol
->g
.log_blocksize
+ 1;
350 status
= fsw_reiserfs_item_search(vol
, dno
->dir_id
, dno
->g
.dnode_id
, search_offset
, &item
);
353 if (item
.item_offset
== 0) {
354 fsw_reiserfs_item_release(vol
, &item
);
355 return FSW_SUCCESS
; // no data items found, assume all-sparse file
357 intra_offset
= search_offset
- item
.item_offset
;
359 // check the kind of block
360 if (item
.item_type
== TYPE_INDIRECT
|| item
.item_type
== V1_INDIRECT_UNIQUENESS
) {
361 // indirect item, contains block numbers
363 if (intra_offset
& (vol
->g
.log_blocksize
- 1)) {
364 FSW_MSG_ASSERT((FSW_MSGSTR("fsw_reiserfs_get_extent: intra_offset not block-aligned for indirect block\n")));
367 intra_bno
= (fsw_u32
)FSW_U64_DIV(intra_offset
, vol
->g
.log_blocksize
);
368 nr_item
= item
.ih
.ih_item_len
/ sizeof(fsw_u32
);
369 if (intra_bno
>= nr_item
) {
370 FSW_MSG_ASSERT((FSW_MSGSTR("fsw_reiserfs_get_extent: indirect block too small\n")));
373 extent
->type
= FSW_EXTENT_TYPE_PHYSBLOCK
;
374 extent
->phys_start
= ((fsw_u32
*)item
.item_data
)[intra_bno
];
376 // TODO: check if the following blocks can be aggregated into one extent
378 fsw_reiserfs_item_release(vol
, &item
);
381 } else if (item
.item_type
== TYPE_DIRECT
|| item
.item_type
== V1_DIRECT_UNIQUENESS
) {
382 // direct item, contains file data
384 // TODO: Check if direct items always start on block boundaries. If not, we may have
385 // to do extra work here.
387 if (intra_offset
!= 0) {
388 FSW_MSG_ASSERT((FSW_MSGSTR("fsw_reiserfs_get_extent: intra_offset not aligned for direct block\n")));
392 extent
->type
= FSW_EXTENT_TYPE_BUFFER
;
393 status
= fsw_memdup(&extent
->buffer
, item
.item_data
, item
.ih
.ih_item_len
);
394 fsw_reiserfs_item_release(vol
, &item
);
403 fsw_reiserfs_item_release(vol
, &item
);
404 return FSW_VOLUME_CORRUPTED
;
407 // check if the following blocks can be aggregated into one extent
408 file_bcnt = (fsw_u32)((dno->g.size + vol->g.log_blocksize - 1) & (vol->g.log_blocksize - 1));
409 while (path[i] + extent->log_count < buf_bcnt && // indirect block has more block pointers
410 extent->log_start + extent->log_count < file_bcnt) { // file has more blocks
411 if (buffer[path[i] + extent->log_count] == buffer[path[i] + extent->log_count - 1] + 1)
420 * Lookup a directory's child dnode by name. This function is called on a directory
421 * to retrieve the directory entry with the given name. A dnode is constructed for
422 * this entry and returned. The core makes sure that fsw_reiserfs_dnode_fill has been called
423 * and the dnode is actually a directory.
426 static fsw_status_t
fsw_reiserfs_dir_lookup(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
,
427 struct fsw_string
*lookup_name
, struct fsw_reiserfs_dnode
**child_dno_out
)
430 struct fsw_reiserfs_item item
;
431 fsw_u32 nr_item
, i
, name_offset
, next_name_offset
, name_len
;
432 fsw_u32 child_dir_id
;
433 struct reiserfs_de_head
*dhead
;
434 struct fsw_string entry_name
;
436 // Preconditions: The caller has checked that dno is a directory node.
438 // BIG TODOS: Use the hash function to start with the item containing the entry.
439 // Use binary search within the item.
441 entry_name
.type
= FSW_STRING_TYPE_ISO88591
;
443 // get the item for that position
444 status
= fsw_reiserfs_item_search(vol
, dno
->dir_id
, dno
->g
.dnode_id
, FIRST_ITEM_OFFSET
, &item
);
447 if (item
.item_offset
== 0) {
448 fsw_reiserfs_item_release(vol
, &item
);
449 return FSW_NOT_FOUND
; // empty directory or something
454 // search the directory item
455 dhead
= (struct reiserfs_de_head
*)item
.item_data
;
456 nr_item
= item
.ih
.u
.ih_entry_count
;
457 next_name_offset
= item
.ih
.ih_item_len
;
458 for (i
= 0; i
< nr_item
; i
++, dhead
++, next_name_offset
= name_offset
) {
460 name_offset
= dhead
->deh_location
;
461 name_len
= next_name_offset
- name_offset
;
462 while (name_len
> 0 && item
.item_data
[name_offset
+ name_len
- 1] == 0)
465 entry_name
.len
= entry_name
.size
= name_len
;
466 entry_name
.data
= item
.item_data
+ name_offset
;
469 if (fsw_streq(lookup_name
, &entry_name
)) {
470 // found the entry we're looking for!
472 // setup a dnode for the child item
473 status
= fsw_dnode_create(dno
, dhead
->deh_objectid
, FSW_DNODE_TYPE_UNKNOWN
, &entry_name
, child_dno_out
);
474 child_dir_id
= dhead
->deh_dir_id
;
475 fsw_reiserfs_item_release(vol
, &item
);
478 (*child_dno_out
)->dir_id
= child_dir_id
;
484 // We didn't find the next directory entry in this item. Look for the next
485 // item of the directory.
487 status
= fsw_reiserfs_item_next(vol
, &item
);
495 * Get the next directory entry when reading a directory. This function is called during
496 * directory iteration to retrieve the next directory entry. A dnode is constructed for
497 * the entry and returned. The core makes sure that fsw_reiserfs_dnode_fill has been called
498 * and the dnode is actually a directory. The shandle provided by the caller is used to
499 * record the position in the directory between calls.
502 static fsw_status_t
fsw_reiserfs_dir_read(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
,
503 struct fsw_shandle
*shand
, struct fsw_reiserfs_dnode
**child_dno_out
)
506 struct fsw_reiserfs_item item
;
507 fsw_u32 nr_item
, i
, name_offset
, next_name_offset
, name_len
;
508 fsw_u32 child_dir_id
;
509 struct reiserfs_de_head
*dhead
;
510 struct fsw_string entry_name
;
512 // Preconditions: The caller has checked that dno is a directory node. The caller
513 // has opened a storage handle to the directory's storage and keeps it around between
516 // BIG TODOS: Use binary search within the item.
518 // adjust pointer to first entry if necessary
520 shand
->pos
= FIRST_ITEM_OFFSET
;
522 // get the item for that position
523 status
= fsw_reiserfs_item_search(vol
, dno
->dir_id
, dno
->g
.dnode_id
, shand
->pos
, &item
);
526 if (item
.item_offset
== 0) {
527 fsw_reiserfs_item_release(vol
, &item
);
528 return FSW_NOT_FOUND
; // empty directory or something
533 // search the directory item
534 dhead
= (struct reiserfs_de_head
*)item
.item_data
;
535 nr_item
= item
.ih
.u
.ih_entry_count
;
536 for (i
= 0; i
< nr_item
; i
++, dhead
++) {
537 if (dhead
->deh_offset
< shand
->pos
)
538 continue; // not yet past the last entry returned
539 if (dhead
->deh_offset
== DOT_OFFSET
|| dhead
->deh_offset
== DOT_DOT_OFFSET
)
540 continue; // never report . or ..
543 name_offset
= dhead
->deh_location
;
545 next_name_offset
= item
.ih
.ih_item_len
;
547 next_name_offset
= dhead
[-1].deh_location
;
548 name_len
= next_name_offset
- name_offset
;
549 while (name_len
> 0 && item
.item_data
[name_offset
+ name_len
- 1] == 0)
552 entry_name
.type
= FSW_STRING_TYPE_ISO88591
;
553 entry_name
.len
= entry_name
.size
= name_len
;
554 entry_name
.data
= item
.item_data
+ name_offset
;
556 if (fsw_streq_cstr(&entry_name
, ".reiserfs_priv"))
557 continue; // never report this special file
559 // found the next entry!
560 shand
->pos
= dhead
->deh_offset
+ 1;
562 // setup a dnode for the child item
563 status
= fsw_dnode_create(dno
, dhead
->deh_objectid
, FSW_DNODE_TYPE_UNKNOWN
, &entry_name
, child_dno_out
);
564 child_dir_id
= dhead
->deh_dir_id
;
565 fsw_reiserfs_item_release(vol
, &item
);
568 (*child_dno_out
)->dir_id
= child_dir_id
;
573 // We didn't find the next directory entry in this item. Look for the next
574 // item of the directory.
576 status
= fsw_reiserfs_item_next(vol
, &item
);
584 * Get the target path of a symbolic link. This function is called when a symbolic
585 * link needs to be resolved. The core makes sure that the fsw_reiserfs_dnode_fill has been
586 * called on the dnode and that it really is a symlink.
589 static fsw_status_t
fsw_reiserfs_readlink(struct fsw_reiserfs_volume
*vol
, struct fsw_reiserfs_dnode
*dno
,
590 struct fsw_string
*link_target
)
592 return fsw_dnode_readlink_data(dno
, link_target
);
596 * Compare an on-disk tree key against the search key.
599 static int fsw_reiserfs_compare_key(struct reiserfs_key
*key
,
600 fsw_u32 dir_id
, fsw_u32 objectid
, fsw_u64 offset
)
605 if (key
->k_dir_id
> dir_id
)
606 return FIRST_GREATER
;
607 if (key
->k_dir_id
< dir_id
)
608 return SECOND_GREATER
;
610 if (key
->k_objectid
> objectid
)
611 return FIRST_GREATER
;
612 if (key
->k_objectid
< objectid
)
613 return SECOND_GREATER
;
615 // determine format of the on-disk key
616 key_type
= (fsw_u32
)FSW_U64_SHR(key
->u
.k_offset_v2
.v
, 60);
617 if (key_type
!= TYPE_DIRECT
&& key_type
!= TYPE_INDIRECT
&& key_type
!= TYPE_DIRENTRY
) {
618 // detected 3.5 format (_v1)
619 key_offset
= key
->u
.k_offset_v1
.k_offset
;
621 // detected 3.6 format (_v2)
622 key_offset
= key
->u
.k_offset_v2
.v
& (~0ULL >> 4);
624 if (key_offset
> offset
)
625 return FIRST_GREATER
;
626 if (key_offset
< offset
)
627 return SECOND_GREATER
;
628 return KEYS_IDENTICAL
;
632 * Find an item by key in the reiserfs tree.
635 static fsw_status_t
fsw_reiserfs_item_search(struct fsw_reiserfs_volume
*vol
,
636 fsw_u32 dir_id
, fsw_u32 objectid
, fsw_u64 offset
,
637 struct fsw_reiserfs_item
*item
)
641 fsw_u32 tree_bno
, next_tree_bno
, tree_level
, nr_item
, i
;
643 struct block_head
*bhead
;
644 struct reiserfs_key
*key
;
645 struct item_head
*ihead
;
647 FSW_MSG_DEBUG((FSW_MSGSTR("fsw_reiserfs_item_search: searching %d/%d/%lld\n"), dir_id
, objectid
, offset
));
649 // BIG TODOS: Use binary search within the item.
650 // Remember tree path for "get next item" function.
656 tree_bno
= vol
->sb
->s_v1
.s_root_block
;
657 for (tree_level
= vol
->sb
->s_v1
.s_tree_height
- 1; ; tree_level
--) {
659 // get the current tree block into memory
660 status
= fsw_block_get(vol
, tree_bno
, tree_level
, (void **)&buffer
);
663 bhead
= (struct block_head
*)buffer
;
664 if (bhead
->blk_level
!= tree_level
) {
665 FSW_MSG_ASSERT((FSW_MSGSTR("fsw_reiserfs_item_search: tree block %d has not expected level %d\n"), tree_bno
, tree_level
));
666 fsw_block_release(vol
, tree_bno
, buffer
);
667 return FSW_VOLUME_CORRUPTED
;
669 nr_item
= bhead
->blk_nr_item
;
670 FSW_MSG_DEBUGV((FSW_MSGSTR("fsw_reiserfs_item_search: visiting block %d level %d items %d\n"), tree_bno
, tree_level
, nr_item
));
671 item
->path_bno
[tree_level
] = tree_bno
;
673 // check if we have reached a leaf block
674 if (tree_level
== DISK_LEAF_NODE_LEVEL
)
677 // search internal node block, look for the path to follow
678 key
= (struct reiserfs_key
*)(buffer
+ BLKH_SIZE
);
679 for (i
= 0; i
< nr_item
; i
++, key
++) {
680 if (fsw_reiserfs_compare_key(key
, dir_id
, objectid
, offset
) == FIRST_GREATER
)
683 item
->path_index
[tree_level
] = i
;
684 next_tree_bno
= ((struct disk_child
*)(buffer
+ BLKH_SIZE
+ nr_item
* KEY_SIZE
))[i
].dc_block_number
;
685 fsw_block_release(vol
, tree_bno
, buffer
);
686 tree_bno
= next_tree_bno
;
689 // search leaf node block, look for our data
690 ihead
= (struct item_head
*)(buffer
+ BLKH_SIZE
);
691 for (i
= 0; i
< nr_item
; i
++, ihead
++) {
692 comp_result
= fsw_reiserfs_compare_key(&ihead
->ih_key
, dir_id
, objectid
, offset
);
693 if (comp_result
== KEYS_IDENTICAL
)
695 if (comp_result
== FIRST_GREATER
) {
696 // Current key is greater than the search key. Use the last key before this
697 // one as the preliminary result.
699 fsw_block_release(vol
, tree_bno
, buffer
);
700 return FSW_NOT_FOUND
;
707 // Go back to the last key, it was smaller than the search key.
708 // NOTE: The first key of the next leaf block is guaranteed to be greater than
712 item
->path_index
[tree_level
] = i
;
713 // Since we may have a key that is smaller than the search key, verify that
714 // it is for the same object.
715 if (ihead
->ih_key
.k_dir_id
!= dir_id
|| ihead
->ih_key
.k_objectid
!= objectid
) {
716 fsw_block_release(vol
, tree_bno
, buffer
);
717 return FSW_NOT_FOUND
; // Found no key for this object at all
721 fsw_memcpy(&item
->ih
, ihead
, sizeof(struct item_head
));
722 item
->item_type
= (fsw_u32
)FSW_U64_SHR(ihead
->ih_key
.u
.k_offset_v2
.v
, 60);
723 if (item
->item_type
!= TYPE_DIRECT
&&
724 item
->item_type
!= TYPE_INDIRECT
&&
725 item
->item_type
!= TYPE_DIRENTRY
) {
727 item
->item_type
= ihead
->ih_key
.u
.k_offset_v1
.k_uniqueness
;
728 item
->item_offset
= ihead
->ih_key
.u
.k_offset_v1
.k_offset
;
731 item
->item_offset
= ihead
->ih_key
.u
.k_offset_v2
.v
& (~0ULL >> 4);
733 item
->item_data
= buffer
+ ihead
->ih_item_location
;
736 // add information for block release
737 item
->block_bno
= tree_bno
;
738 item
->block_buffer
= buffer
;
740 FSW_MSG_DEBUG((FSW_MSGSTR("fsw_reiserfs_item_search: found %d/%d/%lld (%d)\n"),
741 ihead
->ih_key
.k_dir_id
, ihead
->ih_key
.k_objectid
, item
->item_offset
, item
->item_type
));
746 * Find the next item in the reiserfs tree for an already-found item.
749 static fsw_status_t
fsw_reiserfs_item_next(struct fsw_reiserfs_volume
*vol
,
750 struct fsw_reiserfs_item
*item
)
753 fsw_u32 dir_id
, objectid
;
754 fsw_u32 tree_bno
, next_tree_bno
, tree_level
, nr_item
, nr_ptr_item
;
756 struct block_head
*bhead
;
757 struct item_head
*ihead
;
760 return FSW_NOT_FOUND
;
761 fsw_reiserfs_item_release(vol
, item
); // TODO: maybe delay this and/or use the cached block!
763 dir_id
= item
->ih
.ih_key
.k_dir_id
;
764 objectid
= item
->ih
.ih_key
.k_objectid
;
766 FSW_MSG_DEBUG((FSW_MSGSTR("fsw_reiserfs_item_next: next for %d/%d/%lld\n"), dir_id
, objectid
, item
->item_offset
));
768 // find a node that has more items, moving up until we find one
770 for (tree_level
= DISK_LEAF_NODE_LEVEL
; tree_level
< vol
->sb
->s_v1
.s_tree_height
; tree_level
++) {
772 // get the current tree block into memory
773 tree_bno
= item
->path_bno
[tree_level
];
774 status
= fsw_block_get(vol
, tree_bno
, tree_level
, (void **)&buffer
);
777 bhead
= (struct block_head
*)buffer
;
778 if (bhead
->blk_level
!= tree_level
) {
779 FSW_MSG_ASSERT((FSW_MSGSTR("fsw_reiserfs_item_next: tree block %d has not expected level %d\n"), tree_bno
, tree_level
));
780 fsw_block_release(vol
, tree_bno
, buffer
);
781 return FSW_VOLUME_CORRUPTED
;
783 nr_item
= bhead
->blk_nr_item
;
784 FSW_MSG_DEBUGV((FSW_MSGSTR("fsw_reiserfs_item_next: visiting block %d level %d items %d\n"), tree_bno
, tree_level
, nr_item
));
786 nr_ptr_item
= nr_item
+ ((tree_level
> DISK_LEAF_NODE_LEVEL
) ? 1 : 0); // internal nodes have (nr_item) keys and (nr_item+1) pointers
787 item
->path_index
[tree_level
]++;
788 if (item
->path_index
[tree_level
] >= nr_ptr_item
) {
789 item
->path_index
[tree_level
] = 0;
790 fsw_block_release(vol
, tree_bno
, buffer
);
791 continue; // this node doesn't have any more items, move up one level
794 // we have a new path to follow, move down to the leaf node again
795 while (tree_level
> DISK_LEAF_NODE_LEVEL
) {
796 // get next pointer from current block
797 next_tree_bno
= ((struct disk_child
*)(buffer
+ BLKH_SIZE
+ nr_item
* KEY_SIZE
))[item
->path_index
[tree_level
]].dc_block_number
;
798 fsw_block_release(vol
, tree_bno
, buffer
);
799 tree_bno
= next_tree_bno
;
802 // get the current tree block into memory
803 status
= fsw_block_get(vol
, tree_bno
, tree_level
, (void **)&buffer
);
806 bhead
= (struct block_head
*)buffer
;
807 if (bhead
->blk_level
!= tree_level
) {
808 FSW_MSG_ASSERT((FSW_MSGSTR("fsw_reiserfs_item_next: tree block %d has not expected level %d\n"), tree_bno
, tree_level
));
809 fsw_block_release(vol
, tree_bno
, buffer
);
810 return FSW_VOLUME_CORRUPTED
;
812 nr_item
= bhead
->blk_nr_item
;
813 FSW_MSG_DEBUGV((FSW_MSGSTR("fsw_reiserfs_item_next: visiting block %d level %d items %d\n"), tree_bno
, tree_level
, nr_item
));
814 item
->path_bno
[tree_level
] = tree_bno
;
817 // get the item from the leaf node
818 ihead
= ((struct item_head
*)(buffer
+ BLKH_SIZE
)) + item
->path_index
[tree_level
];
820 // We now have the item that follows the previous one in the tree. Check that it
821 // belongs to the same object.
822 if (ihead
->ih_key
.k_dir_id
!= dir_id
|| ihead
->ih_key
.k_objectid
!= objectid
) {
823 fsw_block_release(vol
, tree_bno
, buffer
);
824 return FSW_NOT_FOUND
; // Found no next key for this object
828 fsw_memcpy(&item
->ih
, ihead
, sizeof(struct item_head
));
829 item
->item_type
= (fsw_u32
)FSW_U64_SHR(ihead
->ih_key
.u
.k_offset_v2
.v
, 60);
830 if (item
->item_type
!= TYPE_DIRECT
&&
831 item
->item_type
!= TYPE_INDIRECT
&&
832 item
->item_type
!= TYPE_DIRENTRY
) {
834 item
->item_type
= ihead
->ih_key
.u
.k_offset_v1
.k_uniqueness
;
835 item
->item_offset
= ihead
->ih_key
.u
.k_offset_v1
.k_offset
;
838 item
->item_offset
= ihead
->ih_key
.u
.k_offset_v2
.v
& (~0ULL >> 4);
840 item
->item_data
= buffer
+ ihead
->ih_item_location
;
843 // add information for block release
844 item
->block_bno
= tree_bno
;
845 item
->block_buffer
= buffer
;
847 FSW_MSG_DEBUG((FSW_MSGSTR("fsw_reiserfs_item_next: found %d/%d/%lld (%d)\n"),
848 ihead
->ih_key
.k_dir_id
, ihead
->ih_key
.k_objectid
, item
->item_offset
, item
->item_type
));
852 // we went to the highest level node and there still were no more items...
853 return FSW_NOT_FOUND
;
857 * Release the disk block still referenced by an item search result.
860 static void fsw_reiserfs_item_release(struct fsw_reiserfs_volume
*vol
,
861 struct fsw_reiserfs_item
*item
)
866 if (item
->block_bno
> 0) {
867 fsw_block_release(vol
, item
->block_bno
, item
->block_buffer
);