16a861427c48653abb5339e5c7a5b86ceed8d746
[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 (name_len == item->name_len && _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 /* Handle sparse extent */
691 if (extent->disk_bytenr == 0 && extent->disk_num_bytes == 0)
692 {
693 RtlZeroMemory(out, size);
694 return size;
695 }
696
697 physical = logical_physical(extent->disk_bytenr);
698 if (physical == INVALID_ADDRESS)
699 {
700 ERR("Unable to convert logical address to physical: %llu\n", extent->disk_bytenr);
701 return READ_ERROR;
702 }
703
704 if (extent->compression == BTRFS_COMPRESS_NONE)
705 {
706 physical += extent->offset + offset;
707 if (physical & (512 - 1))
708 {
709 /* If somebody tried to do unaligned access */
710 physical -= offset;
711 temp_out = FrLdrTempAlloc(size + offset, TAG_BTRFS_FILE);
712
713 if (!disk_read(physical, temp_out, size + offset))
714 {
715 FrLdrTempFree(temp_out, TAG_BTRFS_FILE);
716 return READ_ERROR;
717 }
718
719 memcpy(out, temp_out + offset, size);
720 FrLdrTempFree(temp_out, TAG_BTRFS_FILE);
721 } else
722 {
723 if (!disk_read(physical, out, size))
724 return READ_ERROR;
725 }
726
727 return size;
728 }
729
730 ERR("No compression supported right now\n");
731 return READ_ERROR;
732 }
733
734 static u64 btrfs_file_read(const struct btrfs_root_item *root, u64 inr, u64 offset, u64 size, char *buf)
735 {
736 struct btrfs_path path;
737 struct btrfs_disk_key key;
738 struct btrfs_file_extent_item *extent;
739 int res = 0;
740 u64 rd, seek_pointer = READ_ERROR, offset_in_extent;
741 BOOLEAN find_res;
742
743 TRACE("btrfs_file_read inr=%llu offset=%llu size=%llu\n", inr, offset, size);
744
745 key.objectid = inr;
746 key.type = BTRFS_EXTENT_DATA_KEY;
747 key.offset = offset;
748 init_path(&path);
749
750 find_res = BtrFsSearchTree(root, &key, &path);
751
752 /* if we found greater key, switch to the previous one */
753 if (!find_res && btrfs_comp_keys(&key, path_current_disk_key(&path)) < 0)
754 {
755 if (prev_slot(&key, &path))
756 goto out;
757
758 } else if (btrfs_comp_keys_type(&key, path_current_disk_key(&path)))
759 {
760 goto out;
761 }
762
763 seek_pointer = offset;
764
765 do
766 {
767 TRACE("Current extent: (%llu %u %llu) \n",
768 path_current_disk_key(&path)->objectid,
769 path_current_disk_key(&path)->type,
770 path_current_disk_key(&path)->offset);
771
772 extent = (struct btrfs_file_extent_item *) path_current_data(&path);
773
774 offset_in_extent = seek_pointer;
775 /* check if we need clean extent offset when switching to the next extent */
776 if ((seek_pointer) >= path_current_disk_key(&path)->offset)
777 offset_in_extent -= path_current_disk_key(&path)->offset;
778
779 if (extent->type == BTRFS_FILE_EXTENT_INLINE)
780 {
781 rd = btrfs_read_extent_inline(&path, extent, offset_in_extent, size, buf);
782 }
783 else
784 {
785 rd = btrfs_read_extent_reg(&path, extent, offset_in_extent, size, buf);
786 }
787
788 if (rd == READ_ERROR)
789 {
790 ERR("Error while reading extent\n");
791 seek_pointer = READ_ERROR;
792 goto out;
793 }
794
795 buf += rd;
796 seek_pointer += rd;
797 size -= rd;
798 TRACE("file_read size=%llu rd=%llu seek_pointer=%llu\n", size, rd, seek_pointer);
799
800 if (!size)
801 break;
802 } while (!(res = next_slot(&key, &path)));
803
804 if (res)
805 {
806 seek_pointer = READ_ERROR;
807 goto out;
808 }
809
810 seek_pointer -= offset;
811 out:
812 free_path(&path);
813 return seek_pointer;
814 }
815
816 ////////////////////////////////////////
817 ///////////// INODE
818 ////////////////////////////////////////
819
820
821 static u64 btrfs_lookup_inode_ref(const struct btrfs_root_item *root, u64 inr,
822 struct btrfs_inode_ref *refp, char *name)
823 {
824 struct btrfs_path path;
825 struct btrfs_inode_ref *ref;
826 u64 ret = INVALID_INODE;
827 init_path(&path);
828
829 if (BtrFsSearchTreeType(root, inr, BTRFS_INODE_REF_KEY, &path))
830 {
831 ref = (struct btrfs_inode_ref *) path_current_data(&path);
832
833 if (refp)
834 *refp = *ref;
835 ret = path_current_disk_key(&path)->offset;
836 }
837
838 free_path(&path);
839 return ret;
840 }
841
842 static int btrfs_lookup_inode(const struct btrfs_root_item *root,
843 struct btrfs_disk_key *location,
844 struct btrfs_inode_item *item,
845 struct btrfs_root_item *new_root)
846 {
847 const struct btrfs_root_item tmp_root = *root;
848 struct btrfs_path path;
849 int res = -1;
850
851 // if (location->type == BTRFS_ROOT_ITEM_KEY) {
852 // if (btrfs_find_root(location->objectid, &tmp_root, NULL))
853 // return -1;
854 //
855 // location->objectid = tmp_root.root_dirid;
856 // location->type = BTRFS_INODE_ITEM_KEY;
857 // location->offset = 0;
858 // }
859 init_path(&path);
860 TRACE("Searching inode (%llu %u %llu)\n", location->objectid, location->type, location->offset);
861
862 if (BtrFsSearchTree(&tmp_root, location, &path))
863 {
864 if (item)
865 *item = *((struct btrfs_inode_item *) path_current_data(&path));
866
867 if (new_root)
868 *new_root = tmp_root;
869
870 res = 0;
871 }
872
873 free_path(&path);
874 return res;
875 }
876
877 static BOOLEAN btrfs_readlink(const struct btrfs_root_item *root, u64 inr, char **target)
878 {
879 struct btrfs_path path;
880 struct btrfs_file_extent_item *extent;
881 char *data_ptr;
882 BOOLEAN res = FALSE;
883
884 init_path(&path);
885
886 if (!BtrFsSearchTreeType(root, inr, BTRFS_EXTENT_DATA_KEY, &path))
887 goto out;
888
889 extent = (struct btrfs_file_extent_item *) path_current_data(&path);
890 if (extent->type != BTRFS_FILE_EXTENT_INLINE)
891 {
892 ERR("Extent for symlink %llu not of INLINE type\n", inr);
893 goto out;
894 }
895
896 if (extent->compression != BTRFS_COMPRESS_NONE)
897 {
898 ERR("Symlink %llu extent data compressed!\n", inr);
899 goto out;
900 }
901 else if (extent->encryption != 0)
902 {
903 ERR("Symlink %llu extent data encrypted!\n", inr);
904 goto out;
905 }
906 else if (extent->ram_bytes >= BtrFsInfo->SuperBlock.sectorsize)
907 {
908 ERR("Symlink %llu extent data too long (%llu)!\n", inr, extent->ram_bytes);
909 goto out;
910 }
911
912 data_ptr = (char *) extent + offsetof(
913 struct btrfs_file_extent_item, disk_bytenr);
914
915 *target = FrLdrTempAlloc(extent->ram_bytes + 1, TAG_BTRFS_LINK);
916 if (!*target)
917 {
918 ERR("Cannot allocate %llu bytes\n", extent->ram_bytes + 1);
919 goto out;
920 }
921
922 memcpy(*target, data_ptr, extent->ram_bytes);
923 (*target)[extent->ram_bytes] = '\0';
924
925 res = TRUE;
926
927 out:
928 free_path(&path);
929 return res;
930 }
931
932 /* inr must be a directory (for regular files with multiple hard links this
933 function returns only one of the parents of the file) */
934 static u64 get_parent_inode(const struct btrfs_root_item *root, u64 inr,
935 struct btrfs_inode_item *inode_item)
936 {
937 struct btrfs_disk_key key;
938 u64 res;
939
940 if (inr == BTRFS_FIRST_FREE_OBJECTID)
941 {
942 // if (root->objectid != btrfs_info.fs_root.objectid) {
943 // u64 parent;
944 // struct btrfs_root_ref ref;
945 //
946 // parent = btrfs_lookup_root_ref(root->objectid, &ref,
947 // NULL);
948 // if (parent == -1ULL)
949 // return -1ULL;
950 //
951 // if (btrfs_find_root(parent, root, NULL))
952 // return -1ULL;
953 //
954 // inr = ref.dirid;
955 // }
956
957 if (inode_item)
958 {
959 key.objectid = inr;
960 key.type = BTRFS_INODE_ITEM_KEY;
961 key.offset = 0;
962
963 if (btrfs_lookup_inode(root, &key, inode_item, NULL))
964 return INVALID_INODE;
965 }
966
967 return inr;
968 }
969
970 res = btrfs_lookup_inode_ref(root, inr, NULL, NULL);
971 if (res == INVALID_INODE)
972 return INVALID_INODE;
973
974 if (inode_item)
975 {
976 key.objectid = res;
977 key.type = BTRFS_INODE_ITEM_KEY;
978 key.offset = 0;
979
980 if (btrfs_lookup_inode(root, &key, inode_item, NULL))
981 return INVALID_INODE;
982 }
983
984 return res;
985 }
986
987 static inline int next_length(const char *path)
988 {
989 int res = 0;
990 while (*path != '\0' && *path != '/' && *path != '\\' && res <= BTRFS_NAME_MAX)
991 ++res, ++path;
992 return res;
993 }
994
995 static inline const char *skip_current_directories(const char *cur)
996 {
997 while (1)
998 {
999 if (cur[0] == '/' || cur[0] == '\\')
1000 ++cur;
1001 else if (cur[0] == '.' && (cur[1] == '/' || cur[1] == '\\'))
1002 cur += 2;
1003 else
1004 break;
1005 }
1006
1007 return cur;
1008 }
1009
1010 static u64 btrfs_lookup_path(const struct btrfs_root_item *root, u64 inr, const char *path,
1011 u8 *type_p, struct btrfs_inode_item *inode_item_p, int symlink_limit)
1012 {
1013 struct btrfs_dir_item item;
1014 struct btrfs_inode_item inode_item;
1015 u8 type = BTRFS_FT_DIR;
1016 int len, have_inode = 0;
1017 const char *cur = path;
1018 struct btrfs_disk_key key;
1019 char *link_target = NULL;
1020
1021 if (*cur == '/' || *cur == '\\')
1022 {
1023 ++cur;
1024 inr = root->root_dirid;
1025 }
1026
1027 do
1028 {
1029 cur = skip_current_directories(cur);
1030
1031 len = next_length(cur);
1032 if (len > BTRFS_NAME_MAX)
1033 {
1034 ERR("%s: Name too long at \"%.*s\"\n", BTRFS_NAME_MAX, cur);
1035 return INVALID_INODE;
1036 }
1037
1038 if (len == 1 && cur[0] == '.')
1039 break;
1040
1041 if (len == 2 && cur[0] == '.' && cur[1] == '.')
1042 {
1043 cur += 2;
1044 inr = get_parent_inode(root, inr, &inode_item);
1045 if (inr == INVALID_INODE)
1046 return INVALID_INODE;
1047
1048 type = BTRFS_FT_DIR;
1049 continue;
1050 }
1051
1052 if (!*cur)
1053 break;
1054
1055 if (!BtrFsLookupDirItem(root, inr, cur, len, &item))
1056 {
1057 TRACE("Try to find case-insensitive, path=%s inr=%llu s=%.*s\n", path, inr, len, cur);
1058 if (!BtrFsLookupDirItemI(root, inr, cur, len, &item))
1059 return INVALID_INODE;
1060 }
1061
1062 type = item.type;
1063 have_inode = 1;
1064 if (btrfs_lookup_inode(root, &item.location, &inode_item, NULL))
1065 return INVALID_INODE;
1066
1067 if (type == BTRFS_FT_SYMLINK && symlink_limit >= 0)
1068 {
1069 if (!symlink_limit)
1070 {
1071 TRACE("%s: Too much symlinks!\n");
1072 return INVALID_INODE;
1073 }
1074
1075 /* btrfs_readlink allocates link_target by itself */
1076 if (!btrfs_readlink(root, item.location.objectid, &link_target))
1077 return INVALID_INODE;
1078
1079 inr = btrfs_lookup_path(root, inr, link_target, &type, &inode_item, symlink_limit - 1);
1080
1081 FrLdrTempFree(link_target, TAG_BTRFS_LINK);
1082
1083 if (inr == INVALID_INODE)
1084 return INVALID_INODE;
1085 } else if (type != BTRFS_FT_DIR && cur[len])
1086 {
1087 TRACE("%s: \"%.*s\" not a directory\n", (int) (cur - path + len), path);
1088 return INVALID_INODE;
1089 } else
1090 {
1091 inr = item.location.objectid;
1092 }
1093
1094 cur += len;
1095 } while (*cur);
1096
1097 if (type_p)
1098 *type_p = type;
1099
1100 if (inode_item_p)
1101 {
1102 if (!have_inode)
1103 {
1104 key.objectid = inr;
1105 key.type = BTRFS_INODE_ITEM_KEY;
1106 key.offset = 0;
1107
1108 if (btrfs_lookup_inode(root, &key, &inode_item, NULL))
1109 return INVALID_INODE;
1110 }
1111
1112 *inode_item_p = inode_item;
1113 }
1114
1115 return inr;
1116 }
1117
1118
1119 ARC_STATUS BtrFsClose(ULONG FileId)
1120 {
1121 pbtrfs_file_info phandle = FsGetDeviceSpecific(FileId);
1122 TRACE("BtrFsClose %lu\n", FileId);
1123
1124 FrLdrTempFree(phandle, TAG_BTRFS_FILE);
1125 return ESUCCESS;
1126 }
1127
1128 ARC_STATUS BtrFsGetFileInformation(ULONG FileId, FILEINFORMATION *Information)
1129 {
1130 pbtrfs_file_info phandle = FsGetDeviceSpecific(FileId);
1131
1132 RtlZeroMemory(Information, sizeof(*Information));
1133 Information->EndingAddress.QuadPart = phandle->inode.size;
1134 Information->CurrentAddress.QuadPart = phandle->position;
1135
1136 TRACE("BtrFsGetFileInformation(%lu) -> FileSize = %llu, FilePointer = 0x%llx\n",
1137 FileId, Information->EndingAddress.QuadPart, Information->CurrentAddress.QuadPart);
1138
1139 return ESUCCESS;
1140 }
1141
1142 ARC_STATUS BtrFsOpen(CHAR *Path, OPENMODE OpenMode, ULONG *FileId)
1143 {
1144 u64 inr;
1145 u8 type;
1146
1147 btrfs_file_info temp_file_info;
1148 pbtrfs_file_info phandle;
1149
1150 TRACE("BtrFsOpen %s\n", Path);
1151
1152 if (OpenMode != OpenReadOnly)
1153 return EACCES;
1154
1155 inr = btrfs_lookup_path(&BtrFsInfo->FsRoot, BtrFsInfo->FsRoot.root_dirid, Path, &type, &temp_file_info.inode, 40);
1156
1157 if (inr == INVALID_INODE)
1158 {
1159 TRACE("Cannot lookup file %s\n", Path);
1160 return ENOENT;
1161 }
1162
1163 if (type != BTRFS_FT_REG_FILE)
1164 {
1165 TRACE("Not a regular file: %s\n", Path);
1166 return EISDIR;
1167 }
1168
1169 TRACE("found inode inr=%llu size=%llu\n", inr, temp_file_info.inode.size);
1170
1171 temp_file_info.inr = inr;
1172 temp_file_info.position = 0;
1173
1174 phandle = FrLdrTempAlloc(sizeof(btrfs_file_info), TAG_BTRFS_FILE);
1175 if (!phandle)
1176 return ENOMEM;
1177
1178 memcpy(phandle, &temp_file_info, sizeof(btrfs_file_info));
1179
1180 FsSetDeviceSpecific(*FileId, phandle);
1181 return ESUCCESS;
1182 }
1183
1184 ARC_STATUS BtrFsRead(ULONG FileId, VOID *Buffer, ULONG Size, ULONG *BytesRead)
1185 {
1186 pbtrfs_file_info phandle = FsGetDeviceSpecific(FileId);
1187 u64 rd;
1188
1189 TRACE("BtrFsRead %lu, size=%lu \n", FileId, Size);
1190
1191 if (!Size)
1192 Size = phandle->inode.size;
1193
1194 if (Size > phandle->inode.size)
1195 Size = phandle->inode.size;
1196
1197 rd = btrfs_file_read(&BtrFsInfo->FsRoot, phandle->inr, phandle->position, Size, Buffer);
1198 if (rd == READ_ERROR)
1199 {
1200 TRACE("An error occured while reading file %lu\n", FileId);
1201 return ENOENT;
1202 }
1203
1204 *BytesRead = rd;
1205 return ESUCCESS;
1206 }
1207
1208 ARC_STATUS BtrFsSeek(ULONG FileId, LARGE_INTEGER *Position, SEEKMODE SeekMode)
1209 {
1210 pbtrfs_file_info phandle = FsGetDeviceSpecific(FileId);
1211 LARGE_INTEGER NewPosition = *Position;
1212
1213 switch (SeekMode)
1214 {
1215 case SeekAbsolute:
1216 break;
1217 case SeekRelative:
1218 NewPosition.QuadPart += phandle->position;
1219 break;
1220 default:
1221 ASSERT(FALSE);
1222 return EINVAL;
1223 }
1224
1225 if (NewPosition.QuadPart >= phandle->inode.size)
1226 return EINVAL;
1227
1228 phandle->position = NewPosition.QuadPart;
1229 return ESUCCESS;
1230 }
1231
1232 const DEVVTBL BtrFsFuncTable =
1233 {
1234 BtrFsClose,
1235 BtrFsGetFileInformation,
1236 BtrFsOpen,
1237 BtrFsRead,
1238 BtrFsSeek,
1239 L"btrfs",
1240 };
1241
1242 const DEVVTBL *BtrFsMount(ULONG DeviceId)
1243 {
1244 struct btrfs_path path;
1245 struct btrfs_root_item fs_root_item;
1246
1247 TRACE("Enter BtrFsMount(%lu)\n", DeviceId);
1248
1249 BtrFsInfo = FrLdrTempAlloc(sizeof(struct BTRFS_INFO), TAG_BTRFS_INFO);
1250 if (!BtrFsInfo)
1251 return NULL;
1252 RtlZeroMemory(BtrFsInfo, sizeof(struct BTRFS_INFO));
1253
1254 /* Read the SuperBlock */
1255 if (!disk_read(BTRFS_SUPER_INFO_OFFSET, &BtrFsInfo->SuperBlock, sizeof(struct btrfs_super_block)))
1256 {
1257 FrLdrTempFree(BtrFsInfo, TAG_BTRFS_INFO);
1258 return NULL;
1259 }
1260
1261 /* Check if SuperBlock is valid. If yes, return BTRFS function table */
1262 if (BtrFsInfo->SuperBlock.magic != BTRFS_MAGIC_N)
1263 {
1264 FrLdrTempFree(BtrFsInfo, TAG_BTRFS_INFO);
1265 return NULL;
1266 }
1267
1268 BtrFsInfo->DeviceId = DeviceId;
1269 TRACE("BtrFsMount(%lu) superblock magic ok\n", DeviceId);
1270
1271 btrfs_init_crc32c();
1272
1273 btrfs_read_sys_chunk_array();
1274 btrfs_read_chunk_tree();
1275
1276 /* setup roots */
1277 fs_root_item.bytenr = BtrFsInfo->SuperBlock.root;
1278 fs_root_item.level = BtrFsInfo->SuperBlock.root_level;
1279
1280 init_path(&path);
1281 if (!BtrFsSearchTreeType(&fs_root_item, BTRFS_FS_TREE_OBJECTID, BTRFS_ROOT_ITEM_KEY, &path))
1282 {
1283 FrLdrTempFree(BtrFsInfo, TAG_BTRFS_INFO);
1284 free_path(&path);
1285 return NULL;
1286 }
1287
1288 BtrFsInfo->FsRoot = *(struct btrfs_root_item *) path_current_data(&path);
1289
1290 free_path(&path);
1291
1292 TRACE("BtrFsMount(%lu) success\n", DeviceId);
1293 return &BtrFsFuncTable;
1294 }