[FREELDR] Formatting only.
[reactos.git] / boot / freeldr / freeldr / lib / fs / btrfs.c
1 /*
2 * PROJECT: FreeLoader
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)
6 */
7
8 /* Some code was taken from u-boot, https://github.com/u-boot/u-boot/tree/master/fs/btrfs */
9
10 #include <freeldr.h>
11
12 #include <debug.h>
13 DBG_DEFAULT_CHANNEL(FILESYSTEM);
14
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'
20
21 #define INVALID_INODE _UI64_MAX
22 #define INVALID_ADDRESS _UI64_MAX
23 #define READ_ERROR _UI64_MAX
24
25 struct BTRFS_INFO {
26 ULONG DeviceId;
27 struct btrfs_super_block SuperBlock;
28 struct btrfs_chunk_map ChunkMap;
29 struct btrfs_root_item FsRoot;
30 struct btrfs_root_item ExtentRoot;
31 };
32
33 struct BTRFS_INFO *BtrFsInfo;
34
35 /* compare function used for bin_search */
36 typedef int (*cmp_func)(const void *ptr1, const void *ptr2);
37
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)
41 {
42 int low = min;
43 int high = max;
44 int mid;
45 int ret;
46 unsigned long offset;
47 UCHAR *item;
48
49 while (low < high)
50 {
51 mid = (low + high) / 2;
52 offset = mid * item_size;
53
54 item = (UCHAR *) ptr + offset;
55 ret = func((void *) item, cmp_item);
56
57 if (ret < 0)
58 {
59 low = mid + 1;
60 }
61 else if (ret > 0)
62 {
63 high = mid;
64 }
65 else
66 {
67 *slot = mid;
68 return 0;
69 }
70 }
71 *slot = low;
72 return 1;
73 }
74
75 static int btrfs_comp_chunk_map(struct btrfs_chunk_map_item *m1,
76 struct btrfs_chunk_map_item *m2)
77 {
78 if (m1->logical > m2->logical)
79 return 1;
80 if (m1->logical < m2->logical)
81 return -1;
82 return 0;
83 }
84
85 /* insert a new chunk mapping item */
86 static void insert_chunk_item(struct btrfs_chunk_map_item *item)
87 {
88 struct btrfs_chunk_map *chunk_map = &BtrFsInfo->ChunkMap;
89 int ret;
90 int slot;
91 int i;
92
93 if (chunk_map->map == NULL)
94 {
95 /* first item */
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;
100 return;
101 }
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 */
106 return;
107
108 if (chunk_map->cur_length == BTRFS_MAX_CHUNK_ENTRIES)
109 {
110 /* should be impossible */
111 TRACE("too many chunk items\n");
112 return;
113 }
114
115 for (i = chunk_map->cur_length; i > slot; i--)
116 chunk_map->map[i] = chunk_map->map[i - 1];
117
118 chunk_map->map[slot] = *item;
119 chunk_map->cur_length++;
120 }
121
122 static inline void insert_map(const struct btrfs_disk_key *key, struct btrfs_chunk *chunk)
123 {
124 struct btrfs_stripe *stripe = &chunk->stripe;
125 struct btrfs_stripe *stripe_end = stripe + chunk->num_stripes;
126 struct btrfs_chunk_map_item item;
127
128 item.logical = key->offset;
129 item.length = chunk->length;
130 for (; stripe < stripe_end; stripe++)
131 {
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,
136 item.physical);
137 insert_chunk_item(&item);
138 }
139
140 #if 0
141 struct btrfs_chunk_map *chunk_map = &BtrFsInfo->ChunkMap;
142 struct btrfs_chunk_map_item *itm;
143 int i;
144
145 TRACE("insert finished. Printing chunk map:\n------------------------------\n");
146
147 for (i = 0; i < chunk_map->cur_length; i++)
148 {
149 itm = &chunk_map->map[i];
150 TRACE("%llx..%llx -> %llx..%llx, devid: %llu\n",
151 itm->logical,
152 itm->logical + itm->length,
153 itm->physical,
154 itm->physical + itm->length,
155 itm->devid
156 );
157 }
158 #endif
159 }
160
161 static inline unsigned long btrfs_chunk_item_size(int num_stripes)
162 {
163 return sizeof(struct btrfs_chunk) +
164 sizeof(struct btrfs_stripe) * (num_stripes - 1);
165 }
166
167 static inline void init_path(struct btrfs_path *path)
168 {
169 memset(path, 0, sizeof(*path));
170 path->tree_buf = FrLdrTempAlloc(BtrFsInfo->SuperBlock.nodesize, TAG_BTRFS_NODE);
171 }
172
173 static inline void free_path(struct btrfs_path *path)
174 {
175 if (path->tree_buf) FrLdrTempFree(path->tree_buf, TAG_BTRFS_NODE);
176 }
177
178 static inline struct btrfs_item *path_current_item(struct btrfs_path *path)
179 {
180 return &path->tree_buf->leaf.items[path->slots[0]];
181 }
182
183 static inline UCHAR *path_current_data(struct btrfs_path *path)
184 {
185 return (UCHAR *) path->tree_buf->leaf.items + path_current_item(path)->offset;
186 }
187
188 static inline const struct btrfs_disk_key *path_current_disk_key(struct btrfs_path *path)
189 {
190 return (const struct btrfs_disk_key *) &path_current_item(path)->key;
191 }
192
193
194 static int btrfs_comp_keys(const struct btrfs_disk_key *k1,
195 const struct btrfs_disk_key *k2)
196 {
197 if (k1->objectid > k2->objectid)
198 return 1;
199 if (k1->objectid < k2->objectid)
200 return -1;
201 if (k1->type > k2->type)
202 return 1;
203 if (k1->type < k2->type)
204 return -1;
205 if (k1->offset > k2->offset)
206 return 1;
207 if (k1->offset < k2->offset)
208 return -1;
209 return 0;
210 }
211
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)
215 {
216 if (k1->objectid > k2->objectid)
217 return 1;
218 if (k1->objectid < k2->objectid)
219 return -1;
220 if (k1->type > k2->type)
221 return 1;
222 if (k1->type < k2->type)
223 return -1;
224 return 0;
225 }
226
227 /*
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
230 */
231 static u64 logical_physical(u64 logical)
232 {
233 struct btrfs_chunk_map *chunk_map = &BtrFsInfo->ChunkMap;
234 struct btrfs_chunk_map_item item;
235 int slot, ret;
236
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);
241 if (ret == 0)
242 slot++;
243 else if (slot == 0)
244 return INVALID_ADDRESS;
245 if (logical >= chunk_map->map[slot - 1].logical + chunk_map->map[slot - 1].length)
246 return INVALID_ADDRESS;
247
248 TRACE("Address translation: 0x%llx -> 0x%llx\n", logical,
249 chunk_map->map[slot - 1].physical + logical - chunk_map->map[slot - 1].logical);
250
251 return chunk_map->map[slot - 1].physical + logical - chunk_map->map[slot - 1].logical;
252 }
253
254 static BOOLEAN disk_read(u64 physical, void *dest, u32 count)
255 {
256 LARGE_INTEGER Position;
257 ULONG Count;
258 ARC_STATUS Status;
259
260 if (!dest)
261 return FALSE;
262
263 Position.QuadPart = physical;
264 Status = ArcSeek(BtrFsInfo->DeviceId, &Position, SeekAbsolute);
265 if (Status != ESUCCESS)
266 {
267 ERR("ArcSeek returned status %lu\n", Status);
268 return FALSE;
269 }
270
271 Status = ArcRead(BtrFsInfo->DeviceId, dest, count, &Count);
272 if (Status != ESUCCESS || Count != count)
273 {
274 ERR("ArcRead returned status %lu\n", Status);
275 return FALSE;
276 }
277
278 return TRUE;
279 }
280
281 static BOOLEAN _BtrFsSearchTree(u64 loffset, u8 level, struct btrfs_disk_key *key,
282 struct btrfs_path *path)
283 {
284 struct btrfs_super_block *sb = &BtrFsInfo->SuperBlock;
285 union tree_buf *tree_buf = path->tree_buf;
286 int slot, ret, lvl;
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);
290
291 if (!tree_buf)
292 {
293 ERR("Path struct is not allocated\n");
294 return FALSE;
295 }
296
297 for (lvl = level; lvl >= 0; lvl--)
298 {
299 physical = logical_physical(logical);
300
301 if (!disk_read(physical, &tree_buf->header, sb->nodesize))
302 {
303 ERR("Error when reading tree node, loffset: 0x%llx, poffset: 0x%llx, level: %u\n", logical, physical, lvl);
304 return FALSE;
305 }
306
307
308 if (tree_buf->header.level != lvl)
309 {
310 ERR("Error when searching in tree: expected lvl=%u but got %u\n", lvl, tree_buf->header.level);
311 return FALSE;
312 }
313
314 TRACE("BtrFsSearchTree loop, level %u, loffset: 0x%llx\n", lvl, logical);
315
316 if (lvl)
317 {
318 ret = bin_search(tree_buf->node.ptrs,
319 sizeof(struct btrfs_key_ptr),
320 key, (cmp_func) btrfs_comp_keys,
321 path->slots[lvl],
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])
325 --slot;
326 }
327 else
328 {
329 ret = bin_search(tree_buf->leaf.items,
330 sizeof(struct btrfs_item),
331 key, (cmp_func) btrfs_comp_keys,
332 path->slots[0],
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)
336 --slot;
337 }
338
339 path->itemsnr[lvl] = tree_buf->header.nritems;
340 path->offsets[lvl] = logical;
341 path->slots[lvl] = slot;
342
343 logical = tree_buf->node.ptrs[slot].blockptr;
344 }
345
346 TRACE("Found slot no=%lu\n", slot);
347
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);
351
352 return !ret;
353 }
354
355 static inline BOOLEAN
356 BtrFsSearchTree(const struct btrfs_root_item *root, struct btrfs_disk_key *key, struct btrfs_path *path)
357 {
358 return _BtrFsSearchTree(root->bytenr, root->level, key, path);
359 }
360
361 static inline BOOLEAN
362 BtrFsSearchTreeType(const struct btrfs_root_item *root, u64 objectid, u8 type, struct btrfs_path *path)
363 {
364 struct btrfs_disk_key key;
365
366 key.objectid = objectid;
367 key.type = type;
368 key.offset = 0;
369
370 _BtrFsSearchTree(root->bytenr, root->level, &key, path);
371
372 if (path_current_disk_key(path)->objectid && !btrfs_comp_keys_type(&key, path_current_disk_key(path)))
373 return TRUE;
374 else
375 return FALSE;
376 }
377
378 /* return 0 if slot found */
379 static int next_slot(struct btrfs_disk_key *key,
380 struct btrfs_path *path)
381 {
382 int slot, level = 1;
383
384 if (!path->itemsnr[0])
385 return 1;
386 slot = path->slots[0] + 1;
387 if (slot >= path->itemsnr[0])
388 {
389 /* jumping to next leaf */
390 while (level < BTRFS_MAX_LEVEL)
391 {
392 if (!path->itemsnr[level]) /* no more nodes */
393 return 1;
394 slot = path->slots[level] + 1;
395 if (slot >= path->itemsnr[level])
396 {
397 level++;
398 continue;;
399 }
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);
405 break;
406 }
407 if (level == BTRFS_MAX_LEVEL)
408 return 1;
409 goto out;
410 }
411 path->slots[0] = slot;
412
413 out:
414 if (path_current_disk_key(path)->objectid && !btrfs_comp_keys_type(key, path_current_disk_key(path)))
415 return 0;
416 else
417 return 1;
418 }
419
420 static int prev_slot(struct btrfs_disk_key *key,
421 struct btrfs_path *path)
422 {
423 if (!path->slots[0])
424 return 1;
425 --path->slots[0];
426 if (path_current_disk_key(path)->objectid && !btrfs_comp_keys_type(key, path_current_disk_key(path)))
427 return 0;
428 else
429 return 1;
430 }
431
432 /*
433 * read chunk_array in super block
434 */
435 static void btrfs_read_sys_chunk_array()
436 {
437 struct btrfs_super_block *sb = &BtrFsInfo->SuperBlock;
438 struct btrfs_disk_key *key;
439 struct btrfs_chunk *chunk;
440 u16 cur;
441
442 /* read chunk array in superblock */
443 TRACE("reading chunk array\n-----------------------------\n");
444 cur = 0;
445 while (cur < sb->sys_chunk_array_size)
446 {
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);
449 cur += sizeof(*key);
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);
460
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);
464 }
465 }
466
467
468 /*
469 * read chunk items from chunk_tree and insert them to chunk map
470 * */
471 static void btrfs_read_chunk_tree()
472 {
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;
478
479 if (!(sb->flags & BTRFS_SUPER_FLAG_METADUMP))
480 {
481 if (sb->num_devices > 1)
482 TRACE("warning: only support single device btrfs\n");
483
484 ignore_key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
485 ignore_key.type = BTRFS_DEV_ITEM_KEY;
486
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;
491 init_path(&path);
492 _BtrFsSearchTree(sb->chunk_root, sb->chunk_root_level, &search_key, &path);
493 do
494 {
495 /* skip information about underlying block
496 * devices.
497 */
498 if (!btrfs_comp_keys_type(&ignore_key, path_current_disk_key(&path)))
499 continue;
500 if (btrfs_comp_keys_type(&search_key, path_current_disk_key(&path)))
501 break;
502
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));
506 free_path(&path);
507 }
508 }
509
510 ////////////////////////////////////////
511 ///////////// DIR ITEM
512 ////////////////////////////////////////
513
514 static BOOLEAN verify_dir_item(struct btrfs_dir_item *item, u32 start, u32 total)
515 {
516 u16 max_len = BTRFS_NAME_MAX;
517 u32 end;
518
519 if (item->type >= BTRFS_FT_MAX)
520 {
521 ERR("Invalid dir item type: %i\n", item->type);
522 return TRUE;
523 }
524
525 if (item->type == BTRFS_FT_XATTR)
526 max_len = 255; /* XATTR_NAME_MAX */
527
528 end = start + sizeof(*item) + item->name_len;
529 if (item->name_len > max_len || end > total)
530 {
531 ERR("Invalid dir item name len: %u\n", item->name_len);
532 return TRUE;
533 }
534
535 return FALSE;
536 }
537
538
539 static struct btrfs_dir_item *BtrFsMatchDirItemName(struct btrfs_path *path, const char *name, int name_len)
540 {
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;
544
545 while (cur < path_current_item(path)->size)
546 {
547 this_len = sizeof(*item) + item->name_len + item->data_len;
548 name_ptr = (const char *) item + sizeof(*item);
549
550 if (verify_dir_item(item, cur, this_len))
551 return NULL;
552 if (item->name_len == name_len && !memcmp(name_ptr, name, name_len))
553 return item;
554
555 cur += this_len;
556 item = (struct btrfs_dir_item *) ((u8 *) item + this_len);
557 }
558
559 return NULL;
560 }
561
562 static BOOLEAN BtrFsLookupDirItem(const struct btrfs_root_item *root, u64 dir, const char *name, int name_len,
563 struct btrfs_dir_item *item)
564 {
565 struct btrfs_path path;
566 struct btrfs_disk_key key;
567 struct btrfs_dir_item *res = NULL;
568
569 key.objectid = dir;
570 key.type = BTRFS_DIR_ITEM_KEY;
571 key.offset = btrfs_crc32c(name, name_len);
572 init_path(&path);
573
574 if (!BtrFsSearchTree(root, &key, &path))
575 {
576 free_path(&path);
577 return FALSE;
578 }
579
580 res = BtrFsMatchDirItemName(&path, name, name_len);
581 if (res)
582 *item = *res;
583 free_path(&path);
584
585 return res != NULL;
586 }
587
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)
590 {
591 struct btrfs_path path;
592 struct btrfs_disk_key key;
593 struct btrfs_dir_item *item;
594 char *name_buf;
595 BOOLEAN result = FALSE;
596
597 key.objectid = dir_haystack;
598 key.type = BTRFS_DIR_INDEX_KEY;
599 key.offset = 0;
600 init_path(&path);
601
602 BtrFsSearchTree(root, &key, &path);
603
604 if (btrfs_comp_keys_type(&key, path_current_disk_key(&path)))
605 goto cleanup;
606
607 do
608 {
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));
613
614 if (verify_dir_item(item, 0, sizeof(*item) + item->name_len))
615 continue;
616 if (item->type == BTRFS_FT_XATTR)
617 continue;
618
619 name_buf = (char *) item + sizeof(*item);
620 TRACE("Compare names %.*s and %.*s\n", name_len, name, item->name_len, name_buf);
621
622 if (_strnicmp(name, name_buf, name_len) == 0)
623 {
624 *ret_item = *item;
625 result = TRUE;
626 goto cleanup;
627 }
628
629 } while (!next_slot(&key, &path));
630
631 cleanup:
632 free_path(&path);
633 return result;
634 }
635
636 ////////////////////////////////////////
637 ///////////// EXTENTS
638 ////////////////////////////////////////
639
640 static u64 btrfs_read_extent_inline(struct btrfs_path *path,
641 struct btrfs_file_extent_item *extent, u64 offset,
642 u64 size, char *out)
643 {
644 u32 dlen;
645 const char *cbuf;
646 const int data_off = offsetof(
647 struct btrfs_file_extent_item, disk_bytenr);
648
649 cbuf = (const char *) extent + data_off;
650 dlen = extent->ram_bytes;
651
652 TRACE("read_extent_inline offset=%llu size=%llu gener=%llu\n", offset, size, extent->generation);
653
654 if (offset > dlen)
655 {
656 ERR("Tried to read offset (%llu) beyond extent length (%lu)\n", offset, dlen);
657 return READ_ERROR;
658 }
659
660 if (size > dlen - offset)
661 size = dlen - offset;
662
663 if (extent->compression == BTRFS_COMPRESS_NONE)
664 {
665 TRACE("read_extent_inline %lu, \n", data_off);
666 memcpy(out, cbuf + offset, size);
667 return size;
668 }
669
670 ERR("No compression supported right now\n");
671 return READ_ERROR;
672 }
673
674 static u64 btrfs_read_extent_reg(struct btrfs_path *path, struct btrfs_file_extent_item *extent,
675 u64 offset, u64 size, char *out)
676 {
677 u64 physical, dlen;
678 char *temp_out;
679 dlen = extent->num_bytes;
680
681 if (offset > dlen)
682 {
683 ERR("Tried to read offset (%llu) beyond extent length (%lu)\n", offset, dlen);
684 return READ_ERROR;
685 }
686
687 if (size > dlen - offset)
688 size = dlen - offset;
689
690 physical = logical_physical(extent->disk_bytenr);
691 if (physical == INVALID_ADDRESS)
692 {
693 ERR("Unable to convert logical address to physical: %llu\n", extent->disk_bytenr);
694 return READ_ERROR;
695 }
696
697 if (extent->compression == BTRFS_COMPRESS_NONE)
698 {
699 physical += extent->offset + offset;
700 if (physical & (512 - 1))
701 {
702 /* If somebody tried to do unaligned access */
703 physical -= offset;
704 temp_out = FrLdrTempAlloc(size + offset, TAG_BTRFS_FILE);
705
706 if (!disk_read(physical, temp_out, size + offset))
707 {
708 FrLdrTempFree(temp_out, TAG_BTRFS_FILE);
709 return READ_ERROR;
710 }
711
712 memcpy(out, temp_out + offset, size);
713 FrLdrTempFree(temp_out, TAG_BTRFS_FILE);
714 } else
715 {
716 if (!disk_read(physical, out, size))
717 return READ_ERROR;
718 }
719
720 return size;
721 }
722
723 ERR("No compression supported right now\n");
724 return READ_ERROR;
725 }
726
727 static u64 btrfs_file_read(const struct btrfs_root_item *root, u64 inr, u64 offset, u64 size, char *buf)
728 {
729 struct btrfs_path path;
730 struct btrfs_disk_key key;
731 struct btrfs_file_extent_item *extent;
732 int res = 0;
733 u64 rd, seek_pointer = READ_ERROR, offset_in_extent;
734 BOOLEAN find_res;
735
736 TRACE("btrfs_file_read inr=%llu offset=%llu size=%llu\n", inr, offset, size);
737
738 key.objectid = inr;
739 key.type = BTRFS_EXTENT_DATA_KEY;
740 key.offset = offset;
741 init_path(&path);
742
743 find_res = BtrFsSearchTree(root, &key, &path);
744
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)
747 {
748 if (prev_slot(&key, &path))
749 goto out;
750
751 } else if (btrfs_comp_keys_type(&key, path_current_disk_key(&path)))
752 {
753 goto out;
754 }
755
756 seek_pointer = offset;
757
758 do
759 {
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);
764
765 extent = (struct btrfs_file_extent_item *) path_current_data(&path);
766
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;
771
772 if (extent->type == BTRFS_FILE_EXTENT_INLINE)
773 {
774 rd = btrfs_read_extent_inline(&path, extent, offset_in_extent, size, buf);
775 }
776 else
777 {
778 rd = btrfs_read_extent_reg(&path, extent, offset_in_extent, size, buf);
779 }
780
781 if (rd == READ_ERROR)
782 {
783 ERR("Error while reading extent\n");
784 seek_pointer = READ_ERROR;
785 goto out;
786 }
787
788 buf += rd;
789 seek_pointer += rd;
790 size -= rd;
791 TRACE("file_read size=%llu rd=%llu seek_pointer=%llu\n", size, rd, seek_pointer);
792
793 if (!size)
794 break;
795 } while (!(res = next_slot(&key, &path)));
796
797 if (res)
798 {
799 seek_pointer = READ_ERROR;
800 goto out;
801 }
802
803 seek_pointer -= offset;
804 out:
805 free_path(&path);
806 return seek_pointer;
807 }
808
809 ////////////////////////////////////////
810 ///////////// INODE
811 ////////////////////////////////////////
812
813
814 static u64 btrfs_lookup_inode_ref(const struct btrfs_root_item *root, u64 inr,
815 struct btrfs_inode_ref *refp, char *name)
816 {
817 struct btrfs_path path;
818 struct btrfs_inode_ref *ref;
819 u64 ret = INVALID_INODE;
820 init_path(&path);
821
822 if (BtrFsSearchTreeType(root, inr, BTRFS_INODE_REF_KEY, &path))
823 {
824 ref = (struct btrfs_inode_ref *) path_current_data(&path);
825
826 if (refp)
827 *refp = *ref;
828 ret = path_current_disk_key(&path)->offset;
829 }
830
831 free_path(&path);
832 return ret;
833 }
834
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)
839 {
840 const struct btrfs_root_item tmp_root = *root;
841 struct btrfs_path path;
842 int res = -1;
843
844 // if (location->type == BTRFS_ROOT_ITEM_KEY) {
845 // if (btrfs_find_root(location->objectid, &tmp_root, NULL))
846 // return -1;
847 //
848 // location->objectid = tmp_root.root_dirid;
849 // location->type = BTRFS_INODE_ITEM_KEY;
850 // location->offset = 0;
851 // }
852 init_path(&path);
853 TRACE("Searching inode (%llu %u %llu)\n", location->objectid, location->type, location->offset);
854
855 if (BtrFsSearchTree(&tmp_root, location, &path))
856 {
857 if (item)
858 *item = *((struct btrfs_inode_item *) path_current_data(&path));
859
860 if (new_root)
861 *new_root = tmp_root;
862
863 res = 0;
864 }
865
866 free_path(&path);
867 return res;
868 }
869
870 static BOOLEAN btrfs_readlink(const struct btrfs_root_item *root, u64 inr, char **target)
871 {
872 struct btrfs_path path;
873 struct btrfs_file_extent_item *extent;
874 char *data_ptr;
875 BOOLEAN res = FALSE;
876
877 init_path(&path);
878
879 if (!BtrFsSearchTreeType(root, inr, BTRFS_EXTENT_DATA_KEY, &path))
880 goto out;
881
882 extent = (struct btrfs_file_extent_item *) path_current_data(&path);
883 if (extent->type != BTRFS_FILE_EXTENT_INLINE)
884 {
885 ERR("Extent for symlink %llu not of INLINE type\n", inr);
886 goto out;
887 }
888
889 if (extent->compression != BTRFS_COMPRESS_NONE)
890 {
891 ERR("Symlink %llu extent data compressed!\n", inr);
892 goto out;
893 }
894 else if (extent->encryption != 0)
895 {
896 ERR("Symlink %llu extent data encrypted!\n", inr);
897 goto out;
898 }
899 else if (extent->ram_bytes >= BtrFsInfo->SuperBlock.sectorsize)
900 {
901 ERR("Symlink %llu extent data too long (%llu)!\n", inr, extent->ram_bytes);
902 goto out;
903 }
904
905 data_ptr = (char *) extent + offsetof(
906 struct btrfs_file_extent_item, disk_bytenr);
907
908 *target = FrLdrTempAlloc(extent->ram_bytes + 1, TAG_BTRFS_LINK);
909 if (!*target)
910 {
911 ERR("Cannot allocate %llu bytes\n", extent->ram_bytes + 1);
912 goto out;
913 }
914
915 memcpy(*target, data_ptr, extent->ram_bytes);
916 (*target)[extent->ram_bytes] = '\0';
917
918 res = TRUE;
919
920 out:
921 free_path(&path);
922 return res;
923 }
924
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)
929 {
930 struct btrfs_disk_key key;
931 u64 res;
932
933 if (inr == BTRFS_FIRST_FREE_OBJECTID)
934 {
935 // if (root->objectid != btrfs_info.fs_root.objectid) {
936 // u64 parent;
937 // struct btrfs_root_ref ref;
938 //
939 // parent = btrfs_lookup_root_ref(root->objectid, &ref,
940 // NULL);
941 // if (parent == -1ULL)
942 // return -1ULL;
943 //
944 // if (btrfs_find_root(parent, root, NULL))
945 // return -1ULL;
946 //
947 // inr = ref.dirid;
948 // }
949
950 if (inode_item)
951 {
952 key.objectid = inr;
953 key.type = BTRFS_INODE_ITEM_KEY;
954 key.offset = 0;
955
956 if (btrfs_lookup_inode(root, &key, inode_item, NULL))
957 return INVALID_INODE;
958 }
959
960 return inr;
961 }
962
963 res = btrfs_lookup_inode_ref(root, inr, NULL, NULL);
964 if (res == INVALID_INODE)
965 return INVALID_INODE;
966
967 if (inode_item)
968 {
969 key.objectid = res;
970 key.type = BTRFS_INODE_ITEM_KEY;
971 key.offset = 0;
972
973 if (btrfs_lookup_inode(root, &key, inode_item, NULL))
974 return INVALID_INODE;
975 }
976
977 return res;
978 }
979
980 static inline int next_length(const char *path)
981 {
982 int res = 0;
983 while (*path != '\0' && *path != '/' && *path != '\\' && res <= BTRFS_NAME_MAX)
984 ++res, ++path;
985 return res;
986 }
987
988 static inline const char *skip_current_directories(const char *cur)
989 {
990 while (1)
991 {
992 if (cur[0] == '/' || cur[0] == '\\')
993 ++cur;
994 else if (cur[0] == '.' && (cur[1] == '/' || cur[1] == '\\'))
995 cur += 2;
996 else
997 break;
998 }
999
1000 return cur;
1001 }
1002
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)
1005 {
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;
1013
1014 if (*cur == '/' || *cur == '\\')
1015 {
1016 ++cur;
1017 inr = root->root_dirid;
1018 }
1019
1020 do
1021 {
1022 cur = skip_current_directories(cur);
1023
1024 len = next_length(cur);
1025 if (len > BTRFS_NAME_MAX)
1026 {
1027 ERR("%s: Name too long at \"%.*s\"\n", BTRFS_NAME_MAX, cur);
1028 return INVALID_INODE;
1029 }
1030
1031 if (len == 1 && cur[0] == '.')
1032 break;
1033
1034 if (len == 2 && cur[0] == '.' && cur[1] == '.')
1035 {
1036 cur += 2;
1037 inr = get_parent_inode(root, inr, &inode_item);
1038 if (inr == INVALID_INODE)
1039 return INVALID_INODE;
1040
1041 type = BTRFS_FT_DIR;
1042 continue;
1043 }
1044
1045 if (!*cur)
1046 break;
1047
1048 if (!BtrFsLookupDirItem(root, inr, cur, len, &item))
1049 {
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;
1053 }
1054
1055 type = item.type;
1056 have_inode = 1;
1057 if (btrfs_lookup_inode(root, &item.location, &inode_item, NULL))
1058 return INVALID_INODE;
1059
1060 if (type == BTRFS_FT_SYMLINK && symlink_limit >= 0)
1061 {
1062 if (!symlink_limit)
1063 {
1064 TRACE("%s: Too much symlinks!\n");
1065 return INVALID_INODE;
1066 }
1067
1068 /* btrfs_readlink allocates link_target by itself */
1069 if (!btrfs_readlink(root, item.location.objectid, &link_target))
1070 return INVALID_INODE;
1071
1072 inr = btrfs_lookup_path(root, inr, link_target, &type, &inode_item, symlink_limit - 1);
1073
1074 FrLdrTempFree(link_target, TAG_BTRFS_LINK);
1075
1076 if (inr == INVALID_INODE)
1077 return INVALID_INODE;
1078 } else if (type != BTRFS_FT_DIR && cur[len])
1079 {
1080 TRACE("%s: \"%.*s\" not a directory\n", (int) (cur - path + len), path);
1081 return INVALID_INODE;
1082 } else
1083 {
1084 inr = item.location.objectid;
1085 }
1086
1087 cur += len;
1088 } while (*cur);
1089
1090 if (type_p)
1091 *type_p = type;
1092
1093 if (inode_item_p)
1094 {
1095 if (!have_inode)
1096 {
1097 key.objectid = inr;
1098 key.type = BTRFS_INODE_ITEM_KEY;
1099 key.offset = 0;
1100
1101 if (btrfs_lookup_inode(root, &key, &inode_item, NULL))
1102 return INVALID_INODE;
1103 }
1104
1105 *inode_item_p = inode_item;
1106 }
1107
1108 return inr;
1109 }
1110
1111
1112 ARC_STATUS BtrFsClose(ULONG FileId)
1113 {
1114 pbtrfs_file_info phandle = FsGetDeviceSpecific(FileId);
1115 TRACE("BtrFsClose %lu\n", FileId);
1116
1117 FrLdrTempFree(phandle, TAG_BTRFS_FILE);
1118
1119 return ESUCCESS;
1120 }
1121
1122 ARC_STATUS BtrFsGetFileInformation(ULONG FileId, FILEINFORMATION *Information)
1123 {
1124 pbtrfs_file_info phandle = FsGetDeviceSpecific(FileId);
1125
1126 RtlZeroMemory(Information, sizeof(*Information));
1127 Information->EndingAddress.QuadPart = phandle->inode.size;
1128 Information->CurrentAddress.QuadPart = phandle->position;
1129
1130 TRACE("BtrFsGetFileInformation(%lu) -> FileSize = %llu, FilePointer = 0x%llx\n",
1131 FileId, Information->EndingAddress.QuadPart, Information->CurrentAddress.QuadPart);
1132
1133 return ESUCCESS;
1134 }
1135
1136 ARC_STATUS BtrFsOpen(CHAR *Path, OPENMODE OpenMode, ULONG *FileId)
1137 {
1138 u64 inr;
1139 u8 type;
1140
1141 btrfs_file_info temp_file_info;
1142 pbtrfs_file_info phandle;
1143
1144 TRACE("BtrFsOpen %s\n", Path);
1145
1146 if (OpenMode != OpenReadOnly)
1147 return EACCES;
1148
1149 inr = btrfs_lookup_path(&BtrFsInfo->FsRoot, BtrFsInfo->FsRoot.root_dirid, Path, &type, &temp_file_info.inode, 40);
1150
1151 if (inr == INVALID_INODE)
1152 {
1153 TRACE("Cannot lookup file %s\n", Path);
1154 return ENOENT;
1155 }
1156
1157 if (type != BTRFS_FT_REG_FILE)
1158 {
1159 TRACE("Not a regular file: %s\n", Path);
1160 return EISDIR;
1161 }
1162
1163 TRACE("found inode inr=%llu size=%llu\n", inr, temp_file_info.inode.size);
1164
1165 temp_file_info.inr = inr;
1166 temp_file_info.position = 0;
1167
1168 phandle = FrLdrTempAlloc(sizeof(btrfs_file_info), TAG_BTRFS_FILE);
1169 if (!phandle)
1170 return ENOMEM;
1171
1172 memcpy(phandle, &temp_file_info, sizeof(btrfs_file_info));
1173
1174 FsSetDeviceSpecific(*FileId, phandle);
1175 return ESUCCESS;
1176 }
1177
1178 ARC_STATUS BtrFsRead(ULONG FileId, VOID *Buffer, ULONG Size, ULONG *BytesRead)
1179 {
1180 pbtrfs_file_info phandle = FsGetDeviceSpecific(FileId);
1181 u64 rd;
1182
1183 TRACE("BtrFsRead %lu, size=%lu \n", FileId, Size);
1184
1185 if (!Size)
1186 Size = phandle->inode.size;
1187
1188 if (Size > phandle->inode.size)
1189 Size = phandle->inode.size;
1190
1191 rd = btrfs_file_read(&BtrFsInfo->FsRoot, phandle->inr, phandle->position, Size, Buffer);
1192 if (rd == READ_ERROR)
1193 {
1194 TRACE("An error occured while reading file %lu\n", FileId);
1195 return ENOENT;
1196 }
1197
1198 *BytesRead = rd;
1199 return ESUCCESS;
1200 }
1201
1202 ARC_STATUS BtrFsSeek(ULONG FileId, LARGE_INTEGER *Position, SEEKMODE SeekMode)
1203 {
1204 pbtrfs_file_info phandle = FsGetDeviceSpecific(FileId);
1205
1206 TRACE("BtrFsSeek %lu NewFilePointer = %llu\n", FileId, Position->QuadPart);
1207
1208 if (SeekMode != SeekAbsolute)
1209 return EINVAL;
1210 if (Position->QuadPart >= phandle->inode.size)
1211 return EINVAL;
1212
1213 phandle->position = Position->QuadPart;
1214 return ESUCCESS;
1215 }
1216
1217 const DEVVTBL BtrFsFuncTable =
1218 {
1219 BtrFsClose,
1220 BtrFsGetFileInformation,
1221 BtrFsOpen,
1222 BtrFsRead,
1223 BtrFsSeek,
1224 L"btrfs",
1225 };
1226
1227 const DEVVTBL *BtrFsMount(ULONG DeviceId)
1228 {
1229 struct btrfs_path path;
1230 struct btrfs_root_item fs_root_item;
1231
1232 TRACE("Enter BtrFsMount(%lu)\n", DeviceId);
1233
1234 BtrFsInfo = FrLdrTempAlloc(sizeof(struct BTRFS_INFO), TAG_BTRFS_INFO);
1235 if (!BtrFsInfo)
1236 return NULL;
1237 RtlZeroMemory(BtrFsInfo, sizeof(struct BTRFS_INFO));
1238
1239 /* Read the SuperBlock */
1240 if (!disk_read(BTRFS_SUPER_INFO_OFFSET, &BtrFsInfo->SuperBlock, sizeof(struct btrfs_super_block)))
1241 {
1242 FrLdrTempFree(BtrFsInfo, TAG_BTRFS_INFO);
1243 return NULL;
1244 }
1245
1246 /* Check if SuperBlock is valid. If yes, return BTRFS function table */
1247 if (BtrFsInfo->SuperBlock.magic != BTRFS_MAGIC_N)
1248 {
1249 FrLdrTempFree(BtrFsInfo, TAG_BTRFS_INFO);
1250 return NULL;
1251 }
1252
1253 BtrFsInfo->DeviceId = DeviceId;
1254 TRACE("BtrFsMount(%lu) superblock magic ok\n", DeviceId);
1255
1256 btrfs_init_crc32c();
1257
1258 btrfs_read_sys_chunk_array();
1259 btrfs_read_chunk_tree();
1260
1261 /* setup roots */
1262 fs_root_item.bytenr = BtrFsInfo->SuperBlock.root;
1263 fs_root_item.level = BtrFsInfo->SuperBlock.root_level;
1264
1265 init_path(&path);
1266 if (!BtrFsSearchTreeType(&fs_root_item, BTRFS_FS_TREE_OBJECTID, BTRFS_ROOT_ITEM_KEY, &path))
1267 {
1268 FrLdrTempFree(BtrFsInfo, TAG_BTRFS_INFO);
1269 free_path(&path);
1270 return NULL;
1271 }
1272
1273 BtrFsInfo->FsRoot = *(struct btrfs_root_item *) path_current_data(&path);
1274
1275 free_path(&path);
1276
1277 TRACE("BtrFsMount(%lu) success\n", DeviceId);
1278 return &BtrFsFuncTable;
1279 }