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