3 * LICENSE: GPL-2.0+ (https://spdx.org/licenses/GPL-2.0+)
4 * PURPOSE: BTRFS support for FreeLoader
5 * COPYRIGHT: Copyright 2018 Victor Perevertkin (victor@perevertkin.ru)
8 /* Some code was taken from u-boot, https://github.com/u-boot/u-boot/tree/master/fs/btrfs */
13 DBG_DEFAULT_CHANNEL(FILESYSTEM
);
15 #define TAG_BTRFS_INFO 'IftB'
16 #define TAG_BTRFS_CHUNK_MAP 'CftB'
17 #define TAG_BTRFS_NODE 'NftB'
18 #define TAG_BTRFS_FILE 'FftB'
19 #define TAG_BTRFS_LINK 'LftB'
21 #define INVALID_INODE _UI64_MAX
22 #define INVALID_ADDRESS _UI64_MAX
23 #define READ_ERROR _UI64_MAX
27 struct btrfs_super_block SuperBlock
;
28 struct btrfs_chunk_map ChunkMap
;
29 struct btrfs_root_item FsRoot
;
30 struct btrfs_root_item ExtentRoot
;
33 struct BTRFS_INFO
*BtrFsInfo
;
35 /* compare function used for bin_search */
36 typedef int (*cmp_func
)(const void *ptr1
, const void *ptr2
);
38 /* simple but useful bin search, used for chunk search and btree search */
39 static int bin_search(void *ptr
, int item_size
, void *cmp_item
, cmp_func func
,
40 int min
, int max
, int *slot
)
51 mid
= (low
+ high
) / 2;
52 offset
= mid
* item_size
;
54 item
= (UCHAR
*) ptr
+ offset
;
55 ret
= func((void *) item
, cmp_item
);
75 static int btrfs_comp_chunk_map(struct btrfs_chunk_map_item
*m1
,
76 struct btrfs_chunk_map_item
*m2
)
78 if (m1
->logical
> m2
->logical
)
80 if (m1
->logical
< m2
->logical
)
85 /* insert a new chunk mapping item */
86 static void insert_chunk_item(struct btrfs_chunk_map_item
*item
)
88 struct btrfs_chunk_map
*chunk_map
= &BtrFsInfo
->ChunkMap
;
93 if (chunk_map
->map
== NULL
)
96 chunk_map
->map_length
= BTRFS_MAX_CHUNK_ENTRIES
;
97 chunk_map
->map
= FrLdrTempAlloc(chunk_map
->map_length
* sizeof(chunk_map
->map
[0]), TAG_BTRFS_CHUNK_MAP
);
98 chunk_map
->map
[0] = *item
;
99 chunk_map
->cur_length
= 1;
102 ret
= bin_search(chunk_map
->map
, sizeof(*item
), item
,
103 (cmp_func
) btrfs_comp_chunk_map
, 0,
104 chunk_map
->cur_length
, &slot
);
105 if (ret
== 0)/* already in map */
108 if (chunk_map
->cur_length
== BTRFS_MAX_CHUNK_ENTRIES
)
110 /* should be impossible */
111 TRACE("too many chunk items\n");
115 for (i
= chunk_map
->cur_length
; i
> slot
; i
--)
116 chunk_map
->map
[i
] = chunk_map
->map
[i
- 1];
118 chunk_map
->map
[slot
] = *item
;
119 chunk_map
->cur_length
++;
122 static inline void insert_map(const struct btrfs_disk_key
*key
, struct btrfs_chunk
*chunk
)
124 struct btrfs_stripe
*stripe
= &chunk
->stripe
;
125 struct btrfs_stripe
*stripe_end
= stripe
+ chunk
->num_stripes
;
126 struct btrfs_chunk_map_item item
;
128 item
.logical
= key
->offset
;
129 item
.length
= chunk
->length
;
130 for (; stripe
< stripe_end
; stripe
++)
132 TRACE("stripe: %p\n", stripe
);
133 item
.devid
= stripe
->devid
;
134 item
.physical
= stripe
->offset
;
135 TRACE("inserting chunk log: %llx len: %llx devid: %llx phys: %llx\n", item
.logical
, item
.length
, item
.devid
,
137 insert_chunk_item(&item
);
141 struct btrfs_chunk_map
*chunk_map
= &BtrFsInfo
->ChunkMap
;
142 struct btrfs_chunk_map_item
*itm
;
145 TRACE("insert finished. Printing chunk map:\n------------------------------\n");
147 for (i
= 0; i
< chunk_map
->cur_length
; i
++)
149 itm
= &chunk_map
->map
[i
];
150 TRACE("%llx..%llx -> %llx..%llx, devid: %llu\n",
152 itm
->logical
+ itm
->length
,
154 itm
->physical
+ itm
->length
,
161 static inline unsigned long btrfs_chunk_item_size(int num_stripes
)
163 return sizeof(struct btrfs_chunk
) +
164 sizeof(struct btrfs_stripe
) * (num_stripes
- 1);
167 static inline void init_path(struct btrfs_path
*path
)
169 memset(path
, 0, sizeof(*path
));
170 path
->tree_buf
= FrLdrTempAlloc(BtrFsInfo
->SuperBlock
.nodesize
, TAG_BTRFS_NODE
);
173 static inline void free_path(struct btrfs_path
*path
)
175 if (path
->tree_buf
) FrLdrTempFree(path
->tree_buf
, TAG_BTRFS_NODE
);
178 static inline struct btrfs_item
*path_current_item(struct btrfs_path
*path
)
180 return &path
->tree_buf
->leaf
.items
[path
->slots
[0]];
183 static inline UCHAR
*path_current_data(struct btrfs_path
*path
)
185 return (UCHAR
*) path
->tree_buf
->leaf
.items
+ path_current_item(path
)->offset
;
188 static inline const struct btrfs_disk_key
*path_current_disk_key(struct btrfs_path
*path
)
190 return (const struct btrfs_disk_key
*) &path_current_item(path
)->key
;
194 static int btrfs_comp_keys(const struct btrfs_disk_key
*k1
,
195 const struct btrfs_disk_key
*k2
)
197 if (k1
->objectid
> k2
->objectid
)
199 if (k1
->objectid
< k2
->objectid
)
201 if (k1
->type
> k2
->type
)
203 if (k1
->type
< k2
->type
)
205 if (k1
->offset
> k2
->offset
)
207 if (k1
->offset
< k2
->offset
)
212 /* compare keys but ignore offset, is useful to enumerate all same kind keys */
213 static int btrfs_comp_keys_type(const struct btrfs_disk_key
*k1
,
214 const struct btrfs_disk_key
*k2
)
216 if (k1
->objectid
> k2
->objectid
)
218 if (k1
->objectid
< k2
->objectid
)
220 if (k1
->type
> k2
->type
)
222 if (k1
->type
< k2
->type
)
228 * from sys_chunk_array or chunk_tree, we can convert a logical address to
229 * a physical address we can not support multi device case yet
231 static u64
logical_physical(u64 logical
)
233 struct btrfs_chunk_map
*chunk_map
= &BtrFsInfo
->ChunkMap
;
234 struct btrfs_chunk_map_item item
;
237 item
.logical
= logical
;
238 ret
= bin_search(chunk_map
->map
, sizeof(chunk_map
->map
[0]), &item
,
239 (cmp_func
) btrfs_comp_chunk_map
, 0,
240 chunk_map
->cur_length
, &slot
);
244 return INVALID_ADDRESS
;
245 if (logical
>= chunk_map
->map
[slot
- 1].logical
+ chunk_map
->map
[slot
- 1].length
)
246 return INVALID_ADDRESS
;
248 TRACE("Address translation: 0x%llx -> 0x%llx\n", logical
,
249 chunk_map
->map
[slot
- 1].physical
+ logical
- chunk_map
->map
[slot
- 1].logical
);
251 return chunk_map
->map
[slot
- 1].physical
+ logical
- chunk_map
->map
[slot
- 1].logical
;
254 static BOOLEAN
disk_read(u64 physical
, void *dest
, u32 count
)
256 LARGE_INTEGER Position
;
263 Position
.QuadPart
= physical
;
264 Status
= ArcSeek(BtrFsInfo
->DeviceId
, &Position
, SeekAbsolute
);
265 if (Status
!= ESUCCESS
)
267 ERR("ArcSeek returned status %lu\n", Status
);
271 Status
= ArcRead(BtrFsInfo
->DeviceId
, dest
, count
, &Count
);
272 if (Status
!= ESUCCESS
|| Count
!= count
)
274 ERR("ArcRead returned status %lu\n", Status
);
281 static BOOLEAN
_BtrFsSearchTree(u64 loffset
, u8 level
, struct btrfs_disk_key
*key
,
282 struct btrfs_path
*path
)
284 struct btrfs_super_block
*sb
= &BtrFsInfo
->SuperBlock
;
285 union tree_buf
*tree_buf
= path
->tree_buf
;
287 u64 physical
, logical
= loffset
;
288 TRACE("BtrFsSearchTree called: offset: 0x%llx, level: %u (%llu %u %llu)\n",
289 loffset
, level
, key
->objectid
, key
->type
, key
->offset
);
293 ERR("Path struct is not allocated\n");
297 for (lvl
= level
; lvl
>= 0; lvl
--)
299 physical
= logical_physical(logical
);
301 if (!disk_read(physical
, &tree_buf
->header
, sb
->nodesize
))
303 ERR("Error when reading tree node, loffset: 0x%llx, poffset: 0x%llx, level: %u\n", logical
, physical
, lvl
);
308 if (tree_buf
->header
.level
!= lvl
)
310 ERR("Error when searching in tree: expected lvl=%u but got %u\n", lvl
, tree_buf
->header
.level
);
314 TRACE("BtrFsSearchTree loop, level %u, loffset: 0x%llx\n", lvl
, logical
);
318 ret
= bin_search(tree_buf
->node
.ptrs
,
319 sizeof(struct btrfs_key_ptr
),
320 key
, (cmp_func
) btrfs_comp_keys
,
322 tree_buf
->header
.nritems
, &slot
);
323 TRACE("Inner node, min=%lu max=%lu\n", path
->slots
[0], tree_buf
->header
.nritems
);
324 if (ret
&& slot
> path
->slots
[lvl
])
329 ret
= bin_search(tree_buf
->leaf
.items
,
330 sizeof(struct btrfs_item
),
331 key
, (cmp_func
) btrfs_comp_keys
,
333 tree_buf
->header
.nritems
, &slot
);
334 TRACE("Leaf node, min=%lu max=%lu\n", path
->slots
[0], tree_buf
->header
.nritems
);
335 if (slot
== tree_buf
->header
.nritems
)
339 path
->itemsnr
[lvl
] = tree_buf
->header
.nritems
;
340 path
->offsets
[lvl
] = logical
;
341 path
->slots
[lvl
] = slot
;
343 logical
= tree_buf
->node
.ptrs
[slot
].blockptr
;
346 TRACE("Found slot no=%lu\n", slot
);
348 TRACE("BtrFsSearchTree found item (%llu %u %llu) offset: %lu, size: %lu, returning %lu\n",
349 path_current_disk_key(path
)->objectid
, path_current_disk_key(path
)->type
, path_current_disk_key(path
)->offset
,
350 path_current_item(path
)->offset
, path_current_item(path
)->size
, !ret
);
355 static inline BOOLEAN
356 BtrFsSearchTree(const struct btrfs_root_item
*root
, struct btrfs_disk_key
*key
, struct btrfs_path
*path
)
358 return _BtrFsSearchTree(root
->bytenr
, root
->level
, key
, path
);
361 static inline BOOLEAN
362 BtrFsSearchTreeType(const struct btrfs_root_item
*root
, u64 objectid
, u8 type
, struct btrfs_path
*path
)
364 struct btrfs_disk_key key
;
366 key
.objectid
= objectid
;
370 _BtrFsSearchTree(root
->bytenr
, root
->level
, &key
, path
);
372 if (path_current_disk_key(path
)->objectid
&& !btrfs_comp_keys_type(&key
, path_current_disk_key(path
)))
378 /* return 0 if slot found */
379 static int next_slot(struct btrfs_disk_key
*key
,
380 struct btrfs_path
*path
)
384 if (!path
->itemsnr
[0])
386 slot
= path
->slots
[0] + 1;
387 if (slot
>= path
->itemsnr
[0])
389 /* jumping to next leaf */
390 while (level
< BTRFS_MAX_LEVEL
)
392 if (!path
->itemsnr
[level
]) /* no more nodes */
394 slot
= path
->slots
[level
] + 1;
395 if (slot
>= path
->itemsnr
[level
])
400 path
->slots
[level
] = slot
;
401 path
->slots
[level
- 1] = 0; /* reset low level slots info */
402 path
->itemsnr
[level
- 1] = 0;
403 path
->offsets
[level
- 1] = 0;
404 _BtrFsSearchTree(path
->offsets
[level
], level
, key
, path
);
407 if (level
== BTRFS_MAX_LEVEL
)
411 path
->slots
[0] = slot
;
414 if (path_current_disk_key(path
)->objectid
&& !btrfs_comp_keys_type(key
, path_current_disk_key(path
)))
420 static int prev_slot(struct btrfs_disk_key
*key
,
421 struct btrfs_path
*path
)
426 if (path_current_disk_key(path
)->objectid
&& !btrfs_comp_keys_type(key
, path_current_disk_key(path
)))
433 * read chunk_array in super block
435 static void btrfs_read_sys_chunk_array()
437 struct btrfs_super_block
*sb
= &BtrFsInfo
->SuperBlock
;
438 struct btrfs_disk_key
*key
;
439 struct btrfs_chunk
*chunk
;
442 /* read chunk array in superblock */
443 TRACE("reading chunk array\n-----------------------------\n");
445 while (cur
< sb
->sys_chunk_array_size
)
447 key
= (struct btrfs_disk_key
*) (sb
->sys_chunk_array
+ cur
);
448 TRACE("chunk key objectid: %llx, offset: %llx, type: %u\n", key
->objectid
, key
->offset
, key
->type
);
450 chunk
= (struct btrfs_chunk
*) (sb
->sys_chunk_array
+ cur
);
451 TRACE("chunk length: %llx\n", chunk
->length
);
452 TRACE("chunk owner: %llu\n", chunk
->owner
);
453 TRACE("chunk stripe_len: %llx\n", chunk
->stripe_len
);
454 TRACE("chunk type: %llu\n", chunk
->type
);
455 TRACE("chunk io_align: %u\n", chunk
->io_align
);
456 TRACE("chunk io_width: %u\n", chunk
->io_width
);
457 TRACE("chunk sector_size: %u\n", chunk
->sector_size
);
458 TRACE("chunk num_stripes: %u\n", chunk
->num_stripes
);
459 TRACE("chunk sub_stripes: %u\n", chunk
->sub_stripes
);
461 cur
+= btrfs_chunk_item_size(chunk
->num_stripes
);
462 TRACE("read_sys_chunk_array() cur=%d\n", cur
);
463 insert_map((const struct btrfs_disk_key
*) key
, chunk
);
469 * read chunk items from chunk_tree and insert them to chunk map
471 static void btrfs_read_chunk_tree()
473 struct btrfs_super_block
*sb
= &BtrFsInfo
->SuperBlock
;
474 struct btrfs_disk_key ignore_key
;
475 struct btrfs_disk_key search_key
;
476 struct btrfs_chunk
*chunk
;
477 struct btrfs_path path
;
479 if (!(sb
->flags
& BTRFS_SUPER_FLAG_METADUMP
))
481 if (sb
->num_devices
> 1)
482 TRACE("warning: only support single device btrfs\n");
484 ignore_key
.objectid
= BTRFS_DEV_ITEMS_OBJECTID
;
485 ignore_key
.type
= BTRFS_DEV_ITEM_KEY
;
487 /* read chunk from chunk_tree */
488 search_key
.objectid
= BTRFS_FIRST_CHUNK_TREE_OBJECTID
;
489 search_key
.type
= BTRFS_CHUNK_ITEM_KEY
;
490 search_key
.offset
= 0;
492 _BtrFsSearchTree(sb
->chunk_root
, sb
->chunk_root_level
, &search_key
, &path
);
495 /* skip information about underlying block
498 if (!btrfs_comp_keys_type(&ignore_key
, path_current_disk_key(&path
)))
500 if (btrfs_comp_keys_type(&search_key
, path_current_disk_key(&path
)))
503 chunk
= (struct btrfs_chunk
*) (path_current_data(&path
));
504 insert_map(path_current_disk_key(&path
), chunk
);
505 } while (!next_slot(&search_key
, &path
));
510 ////////////////////////////////////////
511 ///////////// DIR ITEM
512 ////////////////////////////////////////
514 static BOOLEAN
verify_dir_item(struct btrfs_dir_item
*item
, u32 start
, u32 total
)
516 u16 max_len
= BTRFS_NAME_MAX
;
519 if (item
->type
>= BTRFS_FT_MAX
)
521 ERR("Invalid dir item type: %i\n", item
->type
);
525 if (item
->type
== BTRFS_FT_XATTR
)
526 max_len
= 255; /* XATTR_NAME_MAX */
528 end
= start
+ sizeof(*item
) + item
->name_len
;
529 if (item
->name_len
> max_len
|| end
> total
)
531 ERR("Invalid dir item name len: %u\n", item
->name_len
);
539 static struct btrfs_dir_item
*BtrFsMatchDirItemName(struct btrfs_path
*path
, const char *name
, int name_len
)
541 struct btrfs_dir_item
*item
= (struct btrfs_dir_item
*) path_current_data(path
);
542 u32 cur
= 0, this_len
;
543 const char *name_ptr
;
545 while (cur
< path_current_item(path
)->size
)
547 this_len
= sizeof(*item
) + item
->name_len
+ item
->data_len
;
548 name_ptr
= (const char *) item
+ sizeof(*item
);
550 if (verify_dir_item(item
, cur
, this_len
))
552 if (item
->name_len
== name_len
&& !memcmp(name_ptr
, name
, name_len
))
556 item
= (struct btrfs_dir_item
*) ((u8
*) item
+ this_len
);
562 static BOOLEAN
BtrFsLookupDirItem(const struct btrfs_root_item
*root
, u64 dir
, const char *name
, int name_len
,
563 struct btrfs_dir_item
*item
)
565 struct btrfs_path path
;
566 struct btrfs_disk_key key
;
567 struct btrfs_dir_item
*res
= NULL
;
570 key
.type
= BTRFS_DIR_ITEM_KEY
;
571 key
.offset
= btrfs_crc32c(name
, name_len
);
574 if (!BtrFsSearchTree(root
, &key
, &path
))
580 res
= BtrFsMatchDirItemName(&path
, name
, name_len
);
588 static BOOLEAN
BtrFsLookupDirItemI(const struct btrfs_root_item
*root
, u64 dir_haystack
, const char *name
, int name_len
,
589 struct btrfs_dir_item
*ret_item
)
591 struct btrfs_path path
;
592 struct btrfs_disk_key key
;
593 struct btrfs_dir_item
*item
;
595 BOOLEAN result
= FALSE
;
597 key
.objectid
= dir_haystack
;
598 key
.type
= BTRFS_DIR_INDEX_KEY
;
602 BtrFsSearchTree(root
, &key
, &path
);
604 if (btrfs_comp_keys_type(&key
, path_current_disk_key(&path
)))
609 item
= (struct btrfs_dir_item
*) path_current_data(&path
);
610 // TRACE("slot: %ld, KEY (%llu %u %llu) %.*s\n",
611 // path.slots[0], path.item.key.objectid, path.item.key.type,
612 // path.item.key.offset, item->name_len, (char *)item + sizeof(*item));
614 if (verify_dir_item(item
, 0, sizeof(*item
) + item
->name_len
))
616 if (item
->type
== BTRFS_FT_XATTR
)
619 name_buf
= (char *) item
+ sizeof(*item
);
620 TRACE("Compare names %.*s and %.*s\n", name_len
, name
, item
->name_len
, name_buf
);
622 if (_strnicmp(name
, name_buf
, name_len
) == 0)
629 } while (!next_slot(&key
, &path
));
636 ////////////////////////////////////////
637 ///////////// EXTENTS
638 ////////////////////////////////////////
640 static u64
btrfs_read_extent_inline(struct btrfs_path
*path
,
641 struct btrfs_file_extent_item
*extent
, u64 offset
,
646 const int data_off
= offsetof(
647 struct btrfs_file_extent_item
, disk_bytenr
);
649 cbuf
= (const char *) extent
+ data_off
;
650 dlen
= extent
->ram_bytes
;
652 TRACE("read_extent_inline offset=%llu size=%llu gener=%llu\n", offset
, size
, extent
->generation
);
656 ERR("Tried to read offset (%llu) beyond extent length (%lu)\n", offset
, dlen
);
660 if (size
> dlen
- offset
)
661 size
= dlen
- offset
;
663 if (extent
->compression
== BTRFS_COMPRESS_NONE
)
665 TRACE("read_extent_inline %lu, \n", data_off
);
666 memcpy(out
, cbuf
+ offset
, size
);
670 ERR("No compression supported right now\n");
674 static u64
btrfs_read_extent_reg(struct btrfs_path
*path
, struct btrfs_file_extent_item
*extent
,
675 u64 offset
, u64 size
, char *out
)
679 dlen
= extent
->num_bytes
;
683 ERR("Tried to read offset (%llu) beyond extent length (%lu)\n", offset
, dlen
);
687 if (size
> dlen
- offset
)
688 size
= dlen
- offset
;
690 physical
= logical_physical(extent
->disk_bytenr
);
691 if (physical
== INVALID_ADDRESS
)
693 ERR("Unable to convert logical address to physical: %llu\n", extent
->disk_bytenr
);
697 if (extent
->compression
== BTRFS_COMPRESS_NONE
)
699 physical
+= extent
->offset
+ offset
;
700 if (physical
& (512 - 1))
702 /* If somebody tried to do unaligned access */
704 temp_out
= FrLdrTempAlloc(size
+ offset
, TAG_BTRFS_FILE
);
706 if (!disk_read(physical
, temp_out
, size
+ offset
))
708 FrLdrTempFree(temp_out
, TAG_BTRFS_FILE
);
712 memcpy(out
, temp_out
+ offset
, size
);
713 FrLdrTempFree(temp_out
, TAG_BTRFS_FILE
);
716 if (!disk_read(physical
, out
, size
))
723 ERR("No compression supported right now\n");
727 static u64
btrfs_file_read(const struct btrfs_root_item
*root
, u64 inr
, u64 offset
, u64 size
, char *buf
)
729 struct btrfs_path path
;
730 struct btrfs_disk_key key
;
731 struct btrfs_file_extent_item
*extent
;
733 u64 rd
, seek_pointer
= READ_ERROR
, offset_in_extent
;
736 TRACE("btrfs_file_read inr=%llu offset=%llu size=%llu\n", inr
, offset
, size
);
739 key
.type
= BTRFS_EXTENT_DATA_KEY
;
743 find_res
= BtrFsSearchTree(root
, &key
, &path
);
745 /* if we found greater key, switch to the previous one */
746 if (!find_res
&& btrfs_comp_keys(&key
, path_current_disk_key(&path
)) < 0)
748 if (prev_slot(&key
, &path
))
751 } else if (btrfs_comp_keys_type(&key
, path_current_disk_key(&path
)))
756 seek_pointer
= offset
;
760 TRACE("Current extent: (%llu %u %llu) \n",
761 path_current_disk_key(&path
)->objectid
,
762 path_current_disk_key(&path
)->type
,
763 path_current_disk_key(&path
)->offset
);
765 extent
= (struct btrfs_file_extent_item
*) path_current_data(&path
);
767 offset_in_extent
= seek_pointer
;
768 /* check if we need clean extent offset when switching to the next extent */
769 if ((seek_pointer
) >= path_current_disk_key(&path
)->offset
)
770 offset_in_extent
-= path_current_disk_key(&path
)->offset
;
772 if (extent
->type
== BTRFS_FILE_EXTENT_INLINE
)
774 rd
= btrfs_read_extent_inline(&path
, extent
, offset_in_extent
, size
, buf
);
778 rd
= btrfs_read_extent_reg(&path
, extent
, offset_in_extent
, size
, buf
);
781 if (rd
== READ_ERROR
)
783 ERR("Error while reading extent\n");
784 seek_pointer
= READ_ERROR
;
791 TRACE("file_read size=%llu rd=%llu seek_pointer=%llu\n", size
, rd
, seek_pointer
);
795 } while (!(res
= next_slot(&key
, &path
)));
799 seek_pointer
= READ_ERROR
;
803 seek_pointer
-= offset
;
809 ////////////////////////////////////////
811 ////////////////////////////////////////
814 static u64
btrfs_lookup_inode_ref(const struct btrfs_root_item
*root
, u64 inr
,
815 struct btrfs_inode_ref
*refp
, char *name
)
817 struct btrfs_path path
;
818 struct btrfs_inode_ref
*ref
;
819 u64 ret
= INVALID_INODE
;
822 if (BtrFsSearchTreeType(root
, inr
, BTRFS_INODE_REF_KEY
, &path
))
824 ref
= (struct btrfs_inode_ref
*) path_current_data(&path
);
828 ret
= path_current_disk_key(&path
)->offset
;
835 static int btrfs_lookup_inode(const struct btrfs_root_item
*root
,
836 struct btrfs_disk_key
*location
,
837 struct btrfs_inode_item
*item
,
838 struct btrfs_root_item
*new_root
)
840 const struct btrfs_root_item tmp_root
= *root
;
841 struct btrfs_path path
;
844 // if (location->type == BTRFS_ROOT_ITEM_KEY) {
845 // if (btrfs_find_root(location->objectid, &tmp_root, NULL))
848 // location->objectid = tmp_root.root_dirid;
849 // location->type = BTRFS_INODE_ITEM_KEY;
850 // location->offset = 0;
853 TRACE("Searching inode (%llu %u %llu)\n", location
->objectid
, location
->type
, location
->offset
);
855 if (BtrFsSearchTree(&tmp_root
, location
, &path
))
858 *item
= *((struct btrfs_inode_item
*) path_current_data(&path
));
861 *new_root
= tmp_root
;
870 static BOOLEAN
btrfs_readlink(const struct btrfs_root_item
*root
, u64 inr
, char **target
)
872 struct btrfs_path path
;
873 struct btrfs_file_extent_item
*extent
;
879 if (!BtrFsSearchTreeType(root
, inr
, BTRFS_EXTENT_DATA_KEY
, &path
))
882 extent
= (struct btrfs_file_extent_item
*) path_current_data(&path
);
883 if (extent
->type
!= BTRFS_FILE_EXTENT_INLINE
)
885 ERR("Extent for symlink %llu not of INLINE type\n", inr
);
889 if (extent
->compression
!= BTRFS_COMPRESS_NONE
)
891 ERR("Symlink %llu extent data compressed!\n", inr
);
894 else if (extent
->encryption
!= 0)
896 ERR("Symlink %llu extent data encrypted!\n", inr
);
899 else if (extent
->ram_bytes
>= BtrFsInfo
->SuperBlock
.sectorsize
)
901 ERR("Symlink %llu extent data too long (%llu)!\n", inr
, extent
->ram_bytes
);
905 data_ptr
= (char *) extent
+ offsetof(
906 struct btrfs_file_extent_item
, disk_bytenr
);
908 *target
= FrLdrTempAlloc(extent
->ram_bytes
+ 1, TAG_BTRFS_LINK
);
911 ERR("Cannot allocate %llu bytes\n", extent
->ram_bytes
+ 1);
915 memcpy(*target
, data_ptr
, extent
->ram_bytes
);
916 (*target
)[extent
->ram_bytes
] = '\0';
925 /* inr must be a directory (for regular files with multiple hard links this
926 function returns only one of the parents of the file) */
927 static u64
get_parent_inode(const struct btrfs_root_item
*root
, u64 inr
,
928 struct btrfs_inode_item
*inode_item
)
930 struct btrfs_disk_key key
;
933 if (inr
== BTRFS_FIRST_FREE_OBJECTID
)
935 // if (root->objectid != btrfs_info.fs_root.objectid) {
937 // struct btrfs_root_ref ref;
939 // parent = btrfs_lookup_root_ref(root->objectid, &ref,
941 // if (parent == -1ULL)
944 // if (btrfs_find_root(parent, root, NULL))
953 key
.type
= BTRFS_INODE_ITEM_KEY
;
956 if (btrfs_lookup_inode(root
, &key
, inode_item
, NULL
))
957 return INVALID_INODE
;
963 res
= btrfs_lookup_inode_ref(root
, inr
, NULL
, NULL
);
964 if (res
== INVALID_INODE
)
965 return INVALID_INODE
;
970 key
.type
= BTRFS_INODE_ITEM_KEY
;
973 if (btrfs_lookup_inode(root
, &key
, inode_item
, NULL
))
974 return INVALID_INODE
;
980 static inline int next_length(const char *path
)
983 while (*path
!= '\0' && *path
!= '/' && *path
!= '\\' && res
<= BTRFS_NAME_MAX
)
988 static inline const char *skip_current_directories(const char *cur
)
992 if (cur
[0] == '/' || cur
[0] == '\\')
994 else if (cur
[0] == '.' && (cur
[1] == '/' || cur
[1] == '\\'))
1003 static u64
btrfs_lookup_path(const struct btrfs_root_item
*root
, u64 inr
, const char *path
,
1004 u8
*type_p
, struct btrfs_inode_item
*inode_item_p
, int symlink_limit
)
1006 struct btrfs_dir_item item
;
1007 struct btrfs_inode_item inode_item
;
1008 u8 type
= BTRFS_FT_DIR
;
1009 int len
, have_inode
= 0;
1010 const char *cur
= path
;
1011 struct btrfs_disk_key key
;
1012 char *link_target
= NULL
;
1014 if (*cur
== '/' || *cur
== '\\')
1017 inr
= root
->root_dirid
;
1022 cur
= skip_current_directories(cur
);
1024 len
= next_length(cur
);
1025 if (len
> BTRFS_NAME_MAX
)
1027 ERR("%s: Name too long at \"%.*s\"\n", BTRFS_NAME_MAX
, cur
);
1028 return INVALID_INODE
;
1031 if (len
== 1 && cur
[0] == '.')
1034 if (len
== 2 && cur
[0] == '.' && cur
[1] == '.')
1037 inr
= get_parent_inode(root
, inr
, &inode_item
);
1038 if (inr
== INVALID_INODE
)
1039 return INVALID_INODE
;
1041 type
= BTRFS_FT_DIR
;
1048 if (!BtrFsLookupDirItem(root
, inr
, cur
, len
, &item
))
1050 TRACE("Try to find case-insensitive, path=%s inr=%llu s=%.*s\n", path
, inr
, len
, cur
);
1051 if (!BtrFsLookupDirItemI(root
, inr
, cur
, len
, &item
))
1052 return INVALID_INODE
;
1057 if (btrfs_lookup_inode(root
, &item
.location
, &inode_item
, NULL
))
1058 return INVALID_INODE
;
1060 if (type
== BTRFS_FT_SYMLINK
&& symlink_limit
>= 0)
1064 TRACE("%s: Too much symlinks!\n");
1065 return INVALID_INODE
;
1068 /* btrfs_readlink allocates link_target by itself */
1069 if (!btrfs_readlink(root
, item
.location
.objectid
, &link_target
))
1070 return INVALID_INODE
;
1072 inr
= btrfs_lookup_path(root
, inr
, link_target
, &type
, &inode_item
, symlink_limit
- 1);
1074 FrLdrTempFree(link_target
, TAG_BTRFS_LINK
);
1076 if (inr
== INVALID_INODE
)
1077 return INVALID_INODE
;
1078 } else if (type
!= BTRFS_FT_DIR
&& cur
[len
])
1080 TRACE("%s: \"%.*s\" not a directory\n", (int) (cur
- path
+ len
), path
);
1081 return INVALID_INODE
;
1084 inr
= item
.location
.objectid
;
1098 key
.type
= BTRFS_INODE_ITEM_KEY
;
1101 if (btrfs_lookup_inode(root
, &key
, &inode_item
, NULL
))
1102 return INVALID_INODE
;
1105 *inode_item_p
= inode_item
;
1112 ARC_STATUS
BtrFsClose(ULONG FileId
)
1114 pbtrfs_file_info phandle
= FsGetDeviceSpecific(FileId
);
1115 TRACE("BtrFsClose %lu\n", FileId
);
1117 FrLdrTempFree(phandle
, TAG_BTRFS_FILE
);
1122 ARC_STATUS
BtrFsGetFileInformation(ULONG FileId
, FILEINFORMATION
*Information
)
1124 pbtrfs_file_info phandle
= FsGetDeviceSpecific(FileId
);
1126 RtlZeroMemory(Information
, sizeof(*Information
));
1127 Information
->EndingAddress
.QuadPart
= phandle
->inode
.size
;
1128 Information
->CurrentAddress
.QuadPart
= phandle
->position
;
1130 TRACE("BtrFsGetFileInformation(%lu) -> FileSize = %llu, FilePointer = 0x%llx\n",
1131 FileId
, Information
->EndingAddress
.QuadPart
, Information
->CurrentAddress
.QuadPart
);
1136 ARC_STATUS
BtrFsOpen(CHAR
*Path
, OPENMODE OpenMode
, ULONG
*FileId
)
1141 btrfs_file_info temp_file_info
;
1142 pbtrfs_file_info phandle
;
1144 TRACE("BtrFsOpen %s\n", Path
);
1146 if (OpenMode
!= OpenReadOnly
)
1149 inr
= btrfs_lookup_path(&BtrFsInfo
->FsRoot
, BtrFsInfo
->FsRoot
.root_dirid
, Path
, &type
, &temp_file_info
.inode
, 40);
1151 if (inr
== INVALID_INODE
)
1153 TRACE("Cannot lookup file %s\n", Path
);
1157 if (type
!= BTRFS_FT_REG_FILE
)
1159 TRACE("Not a regular file: %s\n", Path
);
1163 TRACE("found inode inr=%llu size=%llu\n", inr
, temp_file_info
.inode
.size
);
1165 temp_file_info
.inr
= inr
;
1166 temp_file_info
.position
= 0;
1168 phandle
= FrLdrTempAlloc(sizeof(btrfs_file_info
), TAG_BTRFS_FILE
);
1172 memcpy(phandle
, &temp_file_info
, sizeof(btrfs_file_info
));
1174 FsSetDeviceSpecific(*FileId
, phandle
);
1178 ARC_STATUS
BtrFsRead(ULONG FileId
, VOID
*Buffer
, ULONG Size
, ULONG
*BytesRead
)
1180 pbtrfs_file_info phandle
= FsGetDeviceSpecific(FileId
);
1183 TRACE("BtrFsRead %lu, size=%lu \n", FileId
, Size
);
1186 Size
= phandle
->inode
.size
;
1188 if (Size
> phandle
->inode
.size
)
1189 Size
= phandle
->inode
.size
;
1191 rd
= btrfs_file_read(&BtrFsInfo
->FsRoot
, phandle
->inr
, phandle
->position
, Size
, Buffer
);
1192 if (rd
== READ_ERROR
)
1194 TRACE("An error occured while reading file %lu\n", FileId
);
1202 ARC_STATUS
BtrFsSeek(ULONG FileId
, LARGE_INTEGER
*Position
, SEEKMODE SeekMode
)
1204 pbtrfs_file_info phandle
= FsGetDeviceSpecific(FileId
);
1206 TRACE("BtrFsSeek %lu NewFilePointer = %llu\n", FileId
, Position
->QuadPart
);
1208 if (SeekMode
!= SeekAbsolute
)
1210 if (Position
->QuadPart
>= phandle
->inode
.size
)
1213 phandle
->position
= Position
->QuadPart
;
1217 const DEVVTBL BtrFsFuncTable
=
1220 BtrFsGetFileInformation
,
1227 const DEVVTBL
*BtrFsMount(ULONG DeviceId
)
1229 struct btrfs_path path
;
1230 struct btrfs_root_item fs_root_item
;
1232 TRACE("Enter BtrFsMount(%lu)\n", DeviceId
);
1234 BtrFsInfo
= FrLdrTempAlloc(sizeof(struct BTRFS_INFO
), TAG_BTRFS_INFO
);
1237 RtlZeroMemory(BtrFsInfo
, sizeof(struct BTRFS_INFO
));
1239 /* Read the SuperBlock */
1240 if (!disk_read(BTRFS_SUPER_INFO_OFFSET
, &BtrFsInfo
->SuperBlock
, sizeof(struct btrfs_super_block
)))
1242 FrLdrTempFree(BtrFsInfo
, TAG_BTRFS_INFO
);
1246 /* Check if SuperBlock is valid. If yes, return BTRFS function table */
1247 if (BtrFsInfo
->SuperBlock
.magic
!= BTRFS_MAGIC_N
)
1249 FrLdrTempFree(BtrFsInfo
, TAG_BTRFS_INFO
);
1253 BtrFsInfo
->DeviceId
= DeviceId
;
1254 TRACE("BtrFsMount(%lu) superblock magic ok\n", DeviceId
);
1256 btrfs_init_crc32c();
1258 btrfs_read_sys_chunk_array();
1259 btrfs_read_chunk_tree();
1262 fs_root_item
.bytenr
= BtrFsInfo
->SuperBlock
.root
;
1263 fs_root_item
.level
= BtrFsInfo
->SuperBlock
.root_level
;
1266 if (!BtrFsSearchTreeType(&fs_root_item
, BTRFS_FS_TREE_OBJECTID
, BTRFS_ROOT_ITEM_KEY
, &path
))
1268 FrLdrTempFree(BtrFsInfo
, TAG_BTRFS_INFO
);
1273 BtrFsInfo
->FsRoot
= *(struct btrfs_root_item
*) path_current_data(&path
);
1277 TRACE("BtrFsMount(%lu) success\n", DeviceId
);
1278 return &BtrFsFuncTable
;