disk-io.c 26 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062
  1. // SPDX-License-Identifier: GPL-2.0+
  2. #include <common.h>
  3. #include <fs_internal.h>
  4. #include <uuid.h>
  5. #include <memalign.h>
  6. #include "kernel-shared/btrfs_tree.h"
  7. #include "common/rbtree-utils.h"
  8. #include "disk-io.h"
  9. #include "ctree.h"
  10. #include "btrfs.h"
  11. #include "volumes.h"
  12. #include "extent-io.h"
  13. #include "crypto/hash.h"
  14. /* specified errno for check_tree_block */
  15. #define BTRFS_BAD_BYTENR (-1)
  16. #define BTRFS_BAD_FSID (-2)
  17. #define BTRFS_BAD_LEVEL (-3)
  18. #define BTRFS_BAD_NRITEMS (-4)
  19. /* Calculate max possible nritems for a leaf/node */
  20. static u32 max_nritems(u8 level, u32 nodesize)
  21. {
  22. if (level == 0)
  23. return ((nodesize - sizeof(struct btrfs_header)) /
  24. sizeof(struct btrfs_item));
  25. return ((nodesize - sizeof(struct btrfs_header)) /
  26. sizeof(struct btrfs_key_ptr));
  27. }
  28. static int check_tree_block(struct btrfs_fs_info *fs_info,
  29. struct extent_buffer *buf)
  30. {
  31. struct btrfs_fs_devices *fs_devices = fs_info->fs_devices;
  32. u32 nodesize = fs_info->nodesize;
  33. bool fsid_match = false;
  34. int ret = BTRFS_BAD_FSID;
  35. if (buf->start != btrfs_header_bytenr(buf))
  36. return BTRFS_BAD_BYTENR;
  37. if (btrfs_header_level(buf) >= BTRFS_MAX_LEVEL)
  38. return BTRFS_BAD_LEVEL;
  39. if (btrfs_header_nritems(buf) > max_nritems(btrfs_header_level(buf),
  40. nodesize))
  41. return BTRFS_BAD_NRITEMS;
  42. /* Only leaf can be empty */
  43. if (btrfs_header_nritems(buf) == 0 &&
  44. btrfs_header_level(buf) != 0)
  45. return BTRFS_BAD_NRITEMS;
  46. while (fs_devices) {
  47. /*
  48. * Checking the incompat flag is only valid for the current
  49. * fs. For seed devices it's forbidden to have their uuid
  50. * changed so reading ->fsid in this case is fine
  51. */
  52. if (fs_devices == fs_info->fs_devices &&
  53. btrfs_fs_incompat(fs_info, METADATA_UUID))
  54. fsid_match = !memcmp_extent_buffer(buf,
  55. fs_devices->metadata_uuid,
  56. btrfs_header_fsid(),
  57. BTRFS_FSID_SIZE);
  58. else
  59. fsid_match = !memcmp_extent_buffer(buf,
  60. fs_devices->fsid,
  61. btrfs_header_fsid(),
  62. BTRFS_FSID_SIZE);
  63. if (fsid_match) {
  64. ret = 0;
  65. break;
  66. }
  67. fs_devices = fs_devices->seed;
  68. }
  69. return ret;
  70. }
  71. static void print_tree_block_error(struct btrfs_fs_info *fs_info,
  72. struct extent_buffer *eb,
  73. int err)
  74. {
  75. char fs_uuid[BTRFS_UUID_UNPARSED_SIZE] = {'\0'};
  76. char found_uuid[BTRFS_UUID_UNPARSED_SIZE] = {'\0'};
  77. u8 buf[BTRFS_UUID_SIZE];
  78. if (!err)
  79. return;
  80. fprintf(stderr, "bad tree block %llu, ", eb->start);
  81. switch (err) {
  82. case BTRFS_BAD_FSID:
  83. read_extent_buffer(eb, buf, btrfs_header_fsid(),
  84. BTRFS_UUID_SIZE);
  85. uuid_unparse(buf, found_uuid);
  86. uuid_unparse(fs_info->fs_devices->metadata_uuid, fs_uuid);
  87. fprintf(stderr, "fsid mismatch, want=%s, have=%s\n",
  88. fs_uuid, found_uuid);
  89. break;
  90. case BTRFS_BAD_BYTENR:
  91. fprintf(stderr, "bytenr mismatch, want=%llu, have=%llu\n",
  92. eb->start, btrfs_header_bytenr(eb));
  93. break;
  94. case BTRFS_BAD_LEVEL:
  95. fprintf(stderr, "bad level, %u > %d\n",
  96. btrfs_header_level(eb), BTRFS_MAX_LEVEL);
  97. break;
  98. case BTRFS_BAD_NRITEMS:
  99. fprintf(stderr, "invalid nr_items: %u\n",
  100. btrfs_header_nritems(eb));
  101. break;
  102. }
  103. }
  104. int btrfs_csum_data(u16 csum_type, const u8 *data, u8 *out, size_t len)
  105. {
  106. memset(out, 0, BTRFS_CSUM_SIZE);
  107. switch (csum_type) {
  108. case BTRFS_CSUM_TYPE_CRC32:
  109. return hash_crc32c(data, len, out);
  110. case BTRFS_CSUM_TYPE_XXHASH:
  111. return hash_xxhash(data, len, out);
  112. case BTRFS_CSUM_TYPE_SHA256:
  113. return hash_sha256(data, len, out);
  114. default:
  115. printf("Unknown csum type %d\n", csum_type);
  116. return -EINVAL;
  117. }
  118. }
  119. /*
  120. * Check if the super is valid:
  121. * - nodesize/sectorsize - minimum, maximum, alignment
  122. * - tree block starts - alignment
  123. * - number of devices - something sane
  124. * - sys array size - maximum
  125. */
  126. static int btrfs_check_super(struct btrfs_super_block *sb)
  127. {
  128. u8 result[BTRFS_CSUM_SIZE];
  129. u16 csum_type;
  130. int csum_size;
  131. u8 *metadata_uuid;
  132. if (btrfs_super_magic(sb) != BTRFS_MAGIC)
  133. return -EIO;
  134. csum_type = btrfs_super_csum_type(sb);
  135. if (csum_type >= btrfs_super_num_csums()) {
  136. error("unsupported checksum algorithm %u", csum_type);
  137. return -EIO;
  138. }
  139. csum_size = btrfs_super_csum_size(sb);
  140. btrfs_csum_data(csum_type, (u8 *)sb + BTRFS_CSUM_SIZE,
  141. result, BTRFS_SUPER_INFO_SIZE - BTRFS_CSUM_SIZE);
  142. if (memcmp(result, sb->csum, csum_size)) {
  143. error("superblock checksum mismatch");
  144. return -EIO;
  145. }
  146. if (btrfs_super_root_level(sb) >= BTRFS_MAX_LEVEL) {
  147. error("tree_root level too big: %d >= %d",
  148. btrfs_super_root_level(sb), BTRFS_MAX_LEVEL);
  149. goto error_out;
  150. }
  151. if (btrfs_super_chunk_root_level(sb) >= BTRFS_MAX_LEVEL) {
  152. error("chunk_root level too big: %d >= %d",
  153. btrfs_super_chunk_root_level(sb), BTRFS_MAX_LEVEL);
  154. goto error_out;
  155. }
  156. if (btrfs_super_log_root_level(sb) >= BTRFS_MAX_LEVEL) {
  157. error("log_root level too big: %d >= %d",
  158. btrfs_super_log_root_level(sb), BTRFS_MAX_LEVEL);
  159. goto error_out;
  160. }
  161. if (!IS_ALIGNED(btrfs_super_root(sb), 4096)) {
  162. error("tree_root block unaligned: %llu", btrfs_super_root(sb));
  163. goto error_out;
  164. }
  165. if (!IS_ALIGNED(btrfs_super_chunk_root(sb), 4096)) {
  166. error("chunk_root block unaligned: %llu",
  167. btrfs_super_chunk_root(sb));
  168. goto error_out;
  169. }
  170. if (!IS_ALIGNED(btrfs_super_log_root(sb), 4096)) {
  171. error("log_root block unaligned: %llu",
  172. btrfs_super_log_root(sb));
  173. goto error_out;
  174. }
  175. if (btrfs_super_nodesize(sb) < 4096) {
  176. error("nodesize too small: %u < 4096",
  177. btrfs_super_nodesize(sb));
  178. goto error_out;
  179. }
  180. if (!IS_ALIGNED(btrfs_super_nodesize(sb), 4096)) {
  181. error("nodesize unaligned: %u", btrfs_super_nodesize(sb));
  182. goto error_out;
  183. }
  184. if (btrfs_super_sectorsize(sb) < 4096) {
  185. error("sectorsize too small: %u < 4096",
  186. btrfs_super_sectorsize(sb));
  187. goto error_out;
  188. }
  189. if (!IS_ALIGNED(btrfs_super_sectorsize(sb), 4096)) {
  190. error("sectorsize unaligned: %u", btrfs_super_sectorsize(sb));
  191. goto error_out;
  192. }
  193. if (btrfs_super_total_bytes(sb) == 0) {
  194. error("invalid total_bytes 0");
  195. goto error_out;
  196. }
  197. if (btrfs_super_bytes_used(sb) < 6 * btrfs_super_nodesize(sb)) {
  198. error("invalid bytes_used %llu", btrfs_super_bytes_used(sb));
  199. goto error_out;
  200. }
  201. if ((btrfs_super_stripesize(sb) != 4096)
  202. && (btrfs_super_stripesize(sb) != btrfs_super_sectorsize(sb))) {
  203. error("invalid stripesize %u", btrfs_super_stripesize(sb));
  204. goto error_out;
  205. }
  206. if (btrfs_super_incompat_flags(sb) & BTRFS_FEATURE_INCOMPAT_METADATA_UUID)
  207. metadata_uuid = sb->metadata_uuid;
  208. else
  209. metadata_uuid = sb->fsid;
  210. if (memcmp(metadata_uuid, sb->dev_item.fsid, BTRFS_FSID_SIZE) != 0) {
  211. char fsid[BTRFS_UUID_UNPARSED_SIZE];
  212. char dev_fsid[BTRFS_UUID_UNPARSED_SIZE];
  213. uuid_unparse(sb->metadata_uuid, fsid);
  214. uuid_unparse(sb->dev_item.fsid, dev_fsid);
  215. error("dev_item UUID does not match fsid: %s != %s",
  216. dev_fsid, fsid);
  217. goto error_out;
  218. }
  219. /*
  220. * Hint to catch really bogus numbers, bitflips or so
  221. */
  222. if (btrfs_super_num_devices(sb) > (1UL << 31)) {
  223. error("suspicious number of devices: %llu",
  224. btrfs_super_num_devices(sb));
  225. }
  226. if (btrfs_super_num_devices(sb) == 0) {
  227. error("number of devices is 0");
  228. goto error_out;
  229. }
  230. /*
  231. * Obvious sys_chunk_array corruptions, it must hold at least one key
  232. * and one chunk
  233. */
  234. if (btrfs_super_sys_array_size(sb) > BTRFS_SYSTEM_CHUNK_ARRAY_SIZE) {
  235. error("system chunk array too big %u > %u",
  236. btrfs_super_sys_array_size(sb),
  237. BTRFS_SYSTEM_CHUNK_ARRAY_SIZE);
  238. goto error_out;
  239. }
  240. if (btrfs_super_sys_array_size(sb) < sizeof(struct btrfs_disk_key)
  241. + sizeof(struct btrfs_chunk)) {
  242. error("system chunk array too small %u < %zu",
  243. btrfs_super_sys_array_size(sb),
  244. sizeof(struct btrfs_disk_key) +
  245. sizeof(struct btrfs_chunk));
  246. goto error_out;
  247. }
  248. return 0;
  249. error_out:
  250. error("superblock checksum matches but it has invalid members");
  251. return -EIO;
  252. }
  253. /*
  254. * btrfs_read_dev_super - read a valid primary superblock from a block device
  255. * @desc,@part: file descriptor of the device
  256. * @sb: buffer where the superblock is going to be read in
  257. *
  258. * Unlike the btrfs-progs/kernel version, here we ony care about the first
  259. * super block, thus it's much simpler.
  260. */
  261. int btrfs_read_dev_super(struct blk_desc *desc, struct disk_partition *part,
  262. struct btrfs_super_block *sb)
  263. {
  264. char tmp[BTRFS_SUPER_INFO_SIZE];
  265. struct btrfs_super_block *buf = (struct btrfs_super_block *)tmp;
  266. int ret;
  267. ret = __btrfs_devread(desc, part, tmp, BTRFS_SUPER_INFO_SIZE,
  268. BTRFS_SUPER_INFO_OFFSET);
  269. if (ret < BTRFS_SUPER_INFO_SIZE)
  270. return -EIO;
  271. if (btrfs_super_bytenr(buf) != BTRFS_SUPER_INFO_OFFSET)
  272. return -EIO;
  273. if (btrfs_check_super(buf))
  274. return -EIO;
  275. memcpy(sb, buf, BTRFS_SUPER_INFO_SIZE);
  276. return 0;
  277. }
  278. static int __csum_tree_block_size(struct extent_buffer *buf, u16 csum_size,
  279. int verify, int silent, u16 csum_type)
  280. {
  281. u8 result[BTRFS_CSUM_SIZE];
  282. u32 len;
  283. len = buf->len - BTRFS_CSUM_SIZE;
  284. btrfs_csum_data(csum_type, (u8 *)buf->data + BTRFS_CSUM_SIZE,
  285. result, len);
  286. if (verify) {
  287. if (memcmp_extent_buffer(buf, result, 0, csum_size)) {
  288. /* FIXME: format */
  289. if (!silent)
  290. printk("checksum verify failed on %llu found %08X wanted %08X\n",
  291. (unsigned long long)buf->start,
  292. result[0],
  293. buf->data[0]);
  294. return 1;
  295. }
  296. } else {
  297. write_extent_buffer(buf, result, 0, csum_size);
  298. }
  299. return 0;
  300. }
  301. int csum_tree_block_size(struct extent_buffer *buf, u16 csum_size, int verify,
  302. u16 csum_type)
  303. {
  304. return __csum_tree_block_size(buf, csum_size, verify, 0, csum_type);
  305. }
  306. static int csum_tree_block(struct btrfs_fs_info *fs_info,
  307. struct extent_buffer *buf, int verify)
  308. {
  309. u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
  310. u16 csum_type = btrfs_super_csum_type(fs_info->super_copy);
  311. return csum_tree_block_size(buf, csum_size, verify, csum_type);
  312. }
  313. struct extent_buffer *btrfs_find_tree_block(struct btrfs_fs_info *fs_info,
  314. u64 bytenr, u32 blocksize)
  315. {
  316. return find_extent_buffer(&fs_info->extent_cache,
  317. bytenr, blocksize);
  318. }
  319. struct extent_buffer* btrfs_find_create_tree_block(
  320. struct btrfs_fs_info *fs_info, u64 bytenr)
  321. {
  322. return alloc_extent_buffer(fs_info, bytenr, fs_info->nodesize);
  323. }
  324. static int verify_parent_transid(struct extent_io_tree *io_tree,
  325. struct extent_buffer *eb, u64 parent_transid,
  326. int ignore)
  327. {
  328. int ret;
  329. if (!parent_transid || btrfs_header_generation(eb) == parent_transid)
  330. return 0;
  331. if (extent_buffer_uptodate(eb) &&
  332. btrfs_header_generation(eb) == parent_transid) {
  333. ret = 0;
  334. goto out;
  335. }
  336. printk("parent transid verify failed on %llu wanted %llu found %llu\n",
  337. (unsigned long long)eb->start,
  338. (unsigned long long)parent_transid,
  339. (unsigned long long)btrfs_header_generation(eb));
  340. if (ignore) {
  341. eb->flags |= EXTENT_BAD_TRANSID;
  342. printk("Ignoring transid failure\n");
  343. return 0;
  344. }
  345. ret = 1;
  346. out:
  347. clear_extent_buffer_uptodate(eb);
  348. return ret;
  349. }
  350. int read_whole_eb(struct btrfs_fs_info *info, struct extent_buffer *eb, int mirror)
  351. {
  352. unsigned long offset = 0;
  353. struct btrfs_multi_bio *multi = NULL;
  354. struct btrfs_device *device;
  355. int ret = 0;
  356. u64 read_len;
  357. unsigned long bytes_left = eb->len;
  358. while (bytes_left) {
  359. read_len = bytes_left;
  360. device = NULL;
  361. ret = btrfs_map_block(info, READ, eb->start + offset,
  362. &read_len, &multi, mirror, NULL);
  363. if (ret) {
  364. printk("Couldn't map the block %Lu\n", eb->start + offset);
  365. kfree(multi);
  366. return -EIO;
  367. }
  368. device = multi->stripes[0].dev;
  369. if (!device->desc || !device->part) {
  370. kfree(multi);
  371. return -EIO;
  372. }
  373. if (read_len > bytes_left)
  374. read_len = bytes_left;
  375. ret = read_extent_from_disk(device->desc, device->part,
  376. multi->stripes[0].physical, eb,
  377. offset, read_len);
  378. kfree(multi);
  379. multi = NULL;
  380. if (ret)
  381. return -EIO;
  382. offset += read_len;
  383. bytes_left -= read_len;
  384. }
  385. return 0;
  386. }
  387. struct extent_buffer* read_tree_block(struct btrfs_fs_info *fs_info, u64 bytenr,
  388. u64 parent_transid)
  389. {
  390. int ret;
  391. struct extent_buffer *eb;
  392. u64 best_transid = 0;
  393. u32 sectorsize = fs_info->sectorsize;
  394. int mirror_num = 1;
  395. int good_mirror = 0;
  396. int candidate_mirror = 0;
  397. int num_copies;
  398. int ignore = 0;
  399. /*
  400. * Don't even try to create tree block for unaligned tree block
  401. * bytenr.
  402. * Such unaligned tree block will free overlapping extent buffer,
  403. * causing use-after-free bugs for fuzzed images.
  404. */
  405. if (bytenr < sectorsize || !IS_ALIGNED(bytenr, sectorsize)) {
  406. error("tree block bytenr %llu is not aligned to sectorsize %u",
  407. bytenr, sectorsize);
  408. return ERR_PTR(-EIO);
  409. }
  410. eb = btrfs_find_create_tree_block(fs_info, bytenr);
  411. if (!eb)
  412. return ERR_PTR(-ENOMEM);
  413. if (btrfs_buffer_uptodate(eb, parent_transid))
  414. return eb;
  415. num_copies = btrfs_num_copies(fs_info, eb->start, eb->len);
  416. while (1) {
  417. ret = read_whole_eb(fs_info, eb, mirror_num);
  418. if (ret == 0 && csum_tree_block(fs_info, eb, 1) == 0 &&
  419. check_tree_block(fs_info, eb) == 0 &&
  420. verify_parent_transid(&fs_info->extent_cache, eb,
  421. parent_transid, ignore) == 0) {
  422. /*
  423. * check_tree_block() is less strict to allow btrfs
  424. * check to get raw eb with bad key order and fix it.
  425. * But we still need to try to get a good copy if
  426. * possible, or bad key order can go into tools like
  427. * btrfs ins dump-tree.
  428. */
  429. if (btrfs_header_level(eb))
  430. ret = btrfs_check_node(fs_info, NULL, eb);
  431. else
  432. ret = btrfs_check_leaf(fs_info, NULL, eb);
  433. if (!ret || candidate_mirror == mirror_num) {
  434. btrfs_set_buffer_uptodate(eb);
  435. return eb;
  436. }
  437. if (candidate_mirror <= 0)
  438. candidate_mirror = mirror_num;
  439. }
  440. if (ignore) {
  441. if (candidate_mirror > 0) {
  442. mirror_num = candidate_mirror;
  443. continue;
  444. }
  445. if (check_tree_block(fs_info, eb))
  446. print_tree_block_error(fs_info, eb,
  447. check_tree_block(fs_info, eb));
  448. else
  449. fprintf(stderr, "Csum didn't match\n");
  450. ret = -EIO;
  451. break;
  452. }
  453. if (num_copies == 1) {
  454. ignore = 1;
  455. continue;
  456. }
  457. if (btrfs_header_generation(eb) > best_transid) {
  458. best_transid = btrfs_header_generation(eb);
  459. good_mirror = mirror_num;
  460. }
  461. mirror_num++;
  462. if (mirror_num > num_copies) {
  463. if (candidate_mirror > 0)
  464. mirror_num = candidate_mirror;
  465. else
  466. mirror_num = good_mirror;
  467. ignore = 1;
  468. continue;
  469. }
  470. }
  471. /*
  472. * We failed to read this tree block, it be should deleted right now
  473. * to avoid stale cache populate the cache.
  474. */
  475. free_extent_buffer(eb);
  476. return ERR_PTR(ret);
  477. }
  478. int read_extent_data(struct btrfs_fs_info *fs_info, char *data, u64 logical,
  479. u64 *len, int mirror)
  480. {
  481. u64 offset = 0;
  482. struct btrfs_multi_bio *multi = NULL;
  483. struct btrfs_device *device;
  484. int ret = 0;
  485. u64 max_len = *len;
  486. ret = btrfs_map_block(fs_info, READ, logical, len, &multi, mirror,
  487. NULL);
  488. if (ret) {
  489. fprintf(stderr, "Couldn't map the block %llu\n",
  490. logical + offset);
  491. goto err;
  492. }
  493. device = multi->stripes[0].dev;
  494. if (*len > max_len)
  495. *len = max_len;
  496. if (!device->desc || !device->part) {
  497. ret = -EIO;
  498. goto err;
  499. }
  500. ret = __btrfs_devread(device->desc, device->part, data, *len,
  501. multi->stripes[0].physical);
  502. if (ret != *len)
  503. ret = -EIO;
  504. else
  505. ret = 0;
  506. err:
  507. kfree(multi);
  508. return ret;
  509. }
  510. void btrfs_setup_root(struct btrfs_root *root, struct btrfs_fs_info *fs_info,
  511. u64 objectid)
  512. {
  513. root->node = NULL;
  514. root->track_dirty = 0;
  515. root->fs_info = fs_info;
  516. root->objectid = objectid;
  517. root->last_trans = 0;
  518. root->last_inode_alloc = 0;
  519. memset(&root->root_key, 0, sizeof(root->root_key));
  520. memset(&root->root_item, 0, sizeof(root->root_item));
  521. root->root_key.objectid = objectid;
  522. }
  523. static int find_and_setup_root(struct btrfs_root *tree_root,
  524. struct btrfs_fs_info *fs_info,
  525. u64 objectid, struct btrfs_root *root)
  526. {
  527. int ret;
  528. u64 generation;
  529. btrfs_setup_root(root, fs_info, objectid);
  530. ret = btrfs_find_last_root(tree_root, objectid,
  531. &root->root_item, &root->root_key);
  532. if (ret)
  533. return ret;
  534. generation = btrfs_root_generation(&root->root_item);
  535. root->node = read_tree_block(fs_info,
  536. btrfs_root_bytenr(&root->root_item), generation);
  537. if (!extent_buffer_uptodate(root->node))
  538. return -EIO;
  539. return 0;
  540. }
  541. int btrfs_free_fs_root(struct btrfs_root *root)
  542. {
  543. if (root->node)
  544. free_extent_buffer(root->node);
  545. kfree(root);
  546. return 0;
  547. }
  548. static void __free_fs_root(struct rb_node *node)
  549. {
  550. struct btrfs_root *root;
  551. root = container_of(node, struct btrfs_root, rb_node);
  552. btrfs_free_fs_root(root);
  553. }
  554. FREE_RB_BASED_TREE(fs_roots, __free_fs_root);
  555. struct btrfs_root *btrfs_read_fs_root_no_cache(struct btrfs_fs_info *fs_info,
  556. struct btrfs_key *location)
  557. {
  558. struct btrfs_root *root;
  559. struct btrfs_root *tree_root = fs_info->tree_root;
  560. struct btrfs_path *path;
  561. struct extent_buffer *l;
  562. u64 generation;
  563. int ret = 0;
  564. root = calloc(1, sizeof(*root));
  565. if (!root)
  566. return ERR_PTR(-ENOMEM);
  567. if (location->offset == (u64)-1) {
  568. ret = find_and_setup_root(tree_root, fs_info,
  569. location->objectid, root);
  570. if (ret) {
  571. free(root);
  572. return ERR_PTR(ret);
  573. }
  574. goto insert;
  575. }
  576. btrfs_setup_root(root, fs_info,
  577. location->objectid);
  578. path = btrfs_alloc_path();
  579. if (!path) {
  580. free(root);
  581. return ERR_PTR(-ENOMEM);
  582. }
  583. ret = btrfs_search_slot(NULL, tree_root, location, path, 0, 0);
  584. if (ret != 0) {
  585. if (ret > 0)
  586. ret = -ENOENT;
  587. goto out;
  588. }
  589. l = path->nodes[0];
  590. read_extent_buffer(l, &root->root_item,
  591. btrfs_item_ptr_offset(l, path->slots[0]),
  592. sizeof(root->root_item));
  593. memcpy(&root->root_key, location, sizeof(*location));
  594. /* If this root is already an orphan, no need to read */
  595. if (btrfs_root_refs(&root->root_item) == 0) {
  596. ret = -ENOENT;
  597. goto out;
  598. }
  599. ret = 0;
  600. out:
  601. btrfs_free_path(path);
  602. if (ret) {
  603. free(root);
  604. return ERR_PTR(ret);
  605. }
  606. generation = btrfs_root_generation(&root->root_item);
  607. root->node = read_tree_block(fs_info,
  608. btrfs_root_bytenr(&root->root_item), generation);
  609. if (!extent_buffer_uptodate(root->node)) {
  610. free(root);
  611. return ERR_PTR(-EIO);
  612. }
  613. insert:
  614. root->ref_cows = 1;
  615. return root;
  616. }
  617. static int btrfs_fs_roots_compare_objectids(struct rb_node *node,
  618. void *data)
  619. {
  620. u64 objectid = *((u64 *)data);
  621. struct btrfs_root *root;
  622. root = rb_entry(node, struct btrfs_root, rb_node);
  623. if (objectid > root->objectid)
  624. return 1;
  625. else if (objectid < root->objectid)
  626. return -1;
  627. else
  628. return 0;
  629. }
  630. int btrfs_fs_roots_compare_roots(struct rb_node *node1, struct rb_node *node2)
  631. {
  632. struct btrfs_root *root;
  633. root = rb_entry(node2, struct btrfs_root, rb_node);
  634. return btrfs_fs_roots_compare_objectids(node1, (void *)&root->objectid);
  635. }
  636. struct btrfs_root *btrfs_read_fs_root(struct btrfs_fs_info *fs_info,
  637. struct btrfs_key *location)
  638. {
  639. struct btrfs_root *root;
  640. struct rb_node *node;
  641. int ret;
  642. u64 objectid = location->objectid;
  643. if (location->objectid == BTRFS_ROOT_TREE_OBJECTID)
  644. return fs_info->tree_root;
  645. if (location->objectid == BTRFS_CHUNK_TREE_OBJECTID)
  646. return fs_info->chunk_root;
  647. if (location->objectid == BTRFS_CSUM_TREE_OBJECTID)
  648. return fs_info->csum_root;
  649. BUG_ON(location->objectid == BTRFS_TREE_RELOC_OBJECTID ||
  650. location->offset != (u64)-1);
  651. node = rb_search(&fs_info->fs_root_tree, (void *)&objectid,
  652. btrfs_fs_roots_compare_objectids, NULL);
  653. if (node)
  654. return container_of(node, struct btrfs_root, rb_node);
  655. root = btrfs_read_fs_root_no_cache(fs_info, location);
  656. if (IS_ERR(root))
  657. return root;
  658. ret = rb_insert(&fs_info->fs_root_tree, &root->rb_node,
  659. btrfs_fs_roots_compare_roots);
  660. BUG_ON(ret);
  661. return root;
  662. }
  663. void btrfs_free_fs_info(struct btrfs_fs_info *fs_info)
  664. {
  665. free(fs_info->tree_root);
  666. free(fs_info->chunk_root);
  667. free(fs_info->csum_root);
  668. free(fs_info->super_copy);
  669. free(fs_info);
  670. }
  671. struct btrfs_fs_info *btrfs_new_fs_info(void)
  672. {
  673. struct btrfs_fs_info *fs_info;
  674. fs_info = calloc(1, sizeof(struct btrfs_fs_info));
  675. if (!fs_info)
  676. return NULL;
  677. fs_info->tree_root = calloc(1, sizeof(struct btrfs_root));
  678. fs_info->chunk_root = calloc(1, sizeof(struct btrfs_root));
  679. fs_info->csum_root = calloc(1, sizeof(struct btrfs_root));
  680. fs_info->super_copy = calloc(1, BTRFS_SUPER_INFO_SIZE);
  681. if (!fs_info->tree_root || !fs_info->chunk_root ||
  682. !fs_info->csum_root || !fs_info->super_copy)
  683. goto free_all;
  684. extent_io_tree_init(&fs_info->extent_cache);
  685. fs_info->fs_root_tree = RB_ROOT;
  686. cache_tree_init(&fs_info->mapping_tree.cache_tree);
  687. mutex_init(&fs_info->fs_mutex);
  688. return fs_info;
  689. free_all:
  690. btrfs_free_fs_info(fs_info);
  691. return NULL;
  692. }
  693. static int setup_root_or_create_block(struct btrfs_fs_info *fs_info,
  694. struct btrfs_root *info_root,
  695. u64 objectid, char *str)
  696. {
  697. struct btrfs_root *root = fs_info->tree_root;
  698. int ret;
  699. ret = find_and_setup_root(root, fs_info, objectid, info_root);
  700. if (ret) {
  701. error("could not setup %s tree", str);
  702. return -EIO;
  703. }
  704. return 0;
  705. }
  706. int btrfs_setup_all_roots(struct btrfs_fs_info *fs_info)
  707. {
  708. struct btrfs_super_block *sb = fs_info->super_copy;
  709. struct btrfs_root *root;
  710. struct btrfs_key key;
  711. u64 root_tree_bytenr;
  712. u64 generation;
  713. int ret;
  714. root = fs_info->tree_root;
  715. btrfs_setup_root(root, fs_info, BTRFS_ROOT_TREE_OBJECTID);
  716. generation = btrfs_super_generation(sb);
  717. root_tree_bytenr = btrfs_super_root(sb);
  718. root->node = read_tree_block(fs_info, root_tree_bytenr, generation);
  719. if (!extent_buffer_uptodate(root->node)) {
  720. fprintf(stderr, "Couldn't read tree root\n");
  721. return -EIO;
  722. }
  723. ret = setup_root_or_create_block(fs_info, fs_info->csum_root,
  724. BTRFS_CSUM_TREE_OBJECTID, "csum");
  725. if (ret)
  726. return ret;
  727. fs_info->csum_root->track_dirty = 1;
  728. fs_info->last_trans_committed = generation;
  729. key.objectid = BTRFS_FS_TREE_OBJECTID;
  730. key.type = BTRFS_ROOT_ITEM_KEY;
  731. key.offset = (u64)-1;
  732. fs_info->fs_root = btrfs_read_fs_root(fs_info, &key);
  733. if (IS_ERR(fs_info->fs_root))
  734. return -EIO;
  735. return 0;
  736. }
  737. void btrfs_release_all_roots(struct btrfs_fs_info *fs_info)
  738. {
  739. if (fs_info->csum_root)
  740. free_extent_buffer(fs_info->csum_root->node);
  741. if (fs_info->tree_root)
  742. free_extent_buffer(fs_info->tree_root->node);
  743. if (fs_info->chunk_root)
  744. free_extent_buffer(fs_info->chunk_root->node);
  745. }
  746. static void free_map_lookup(struct cache_extent *ce)
  747. {
  748. struct map_lookup *map;
  749. map = container_of(ce, struct map_lookup, ce);
  750. kfree(map);
  751. }
  752. FREE_EXTENT_CACHE_BASED_TREE(mapping_cache, free_map_lookup);
  753. void btrfs_cleanup_all_caches(struct btrfs_fs_info *fs_info)
  754. {
  755. free_mapping_cache_tree(&fs_info->mapping_tree.cache_tree);
  756. extent_io_tree_cleanup(&fs_info->extent_cache);
  757. }
  758. static int btrfs_scan_fs_devices(struct blk_desc *desc,
  759. struct disk_partition *part,
  760. struct btrfs_fs_devices **fs_devices)
  761. {
  762. u64 total_devs;
  763. int ret;
  764. if (round_up(BTRFS_SUPER_INFO_SIZE + BTRFS_SUPER_INFO_OFFSET,
  765. desc->blksz) > (part->size << desc->log2blksz)) {
  766. error("superblock end %u is larger than device size " LBAFU,
  767. BTRFS_SUPER_INFO_SIZE + BTRFS_SUPER_INFO_OFFSET,
  768. part->size << desc->log2blksz);
  769. return -EINVAL;
  770. }
  771. ret = btrfs_scan_one_device(desc, part, fs_devices, &total_devs);
  772. if (ret) {
  773. fprintf(stderr, "No valid Btrfs found\n");
  774. return ret;
  775. }
  776. return 0;
  777. }
  778. int btrfs_check_fs_compatibility(struct btrfs_super_block *sb)
  779. {
  780. u64 features;
  781. features = btrfs_super_incompat_flags(sb) &
  782. ~BTRFS_FEATURE_INCOMPAT_SUPP;
  783. if (features) {
  784. printk("couldn't open because of unsupported "
  785. "option features (%llx).\n",
  786. (unsigned long long)features);
  787. return -ENOTSUPP;
  788. }
  789. features = btrfs_super_incompat_flags(sb);
  790. if (!(features & BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF)) {
  791. features |= BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF;
  792. btrfs_set_super_incompat_flags(sb, features);
  793. }
  794. return 0;
  795. }
  796. static int btrfs_setup_chunk_tree_and_device_map(struct btrfs_fs_info *fs_info)
  797. {
  798. struct btrfs_super_block *sb = fs_info->super_copy;
  799. u64 chunk_root_bytenr;
  800. u64 generation;
  801. int ret;
  802. btrfs_setup_root(fs_info->chunk_root, fs_info,
  803. BTRFS_CHUNK_TREE_OBJECTID);
  804. ret = btrfs_read_sys_array(fs_info);
  805. if (ret)
  806. return ret;
  807. generation = btrfs_super_chunk_root_generation(sb);
  808. chunk_root_bytenr = btrfs_super_chunk_root(sb);
  809. fs_info->chunk_root->node = read_tree_block(fs_info,
  810. chunk_root_bytenr,
  811. generation);
  812. if (!extent_buffer_uptodate(fs_info->chunk_root->node)) {
  813. error("cannot read chunk root");
  814. return -EIO;
  815. }
  816. ret = btrfs_read_chunk_tree(fs_info);
  817. if (ret) {
  818. fprintf(stderr, "Couldn't read chunk tree\n");
  819. return ret;
  820. }
  821. return 0;
  822. }
  823. struct btrfs_fs_info *open_ctree_fs_info(struct blk_desc *desc,
  824. struct disk_partition *part)
  825. {
  826. struct btrfs_fs_info *fs_info;
  827. struct btrfs_super_block *disk_super;
  828. struct btrfs_fs_devices *fs_devices = NULL;
  829. struct extent_buffer *eb;
  830. int ret;
  831. fs_info = btrfs_new_fs_info();
  832. if (!fs_info) {
  833. fprintf(stderr, "Failed to allocate memory for fs_info\n");
  834. return NULL;
  835. }
  836. ret = btrfs_scan_fs_devices(desc, part, &fs_devices);
  837. if (ret)
  838. goto out;
  839. fs_info->fs_devices = fs_devices;
  840. ret = btrfs_open_devices(fs_devices);
  841. if (ret)
  842. goto out;
  843. disk_super = fs_info->super_copy;
  844. ret = btrfs_read_dev_super(desc, part, disk_super);
  845. if (ret) {
  846. printk("No valid btrfs found\n");
  847. goto out_devices;
  848. }
  849. if (btrfs_super_flags(disk_super) & BTRFS_SUPER_FLAG_CHANGING_FSID) {
  850. fprintf(stderr, "ERROR: Filesystem UUID change in progress\n");
  851. goto out_devices;
  852. }
  853. ASSERT(!memcmp(disk_super->fsid, fs_devices->fsid, BTRFS_FSID_SIZE));
  854. if (btrfs_fs_incompat(fs_info, METADATA_UUID))
  855. ASSERT(!memcmp(disk_super->metadata_uuid,
  856. fs_devices->metadata_uuid, BTRFS_FSID_SIZE));
  857. fs_info->sectorsize = btrfs_super_sectorsize(disk_super);
  858. fs_info->nodesize = btrfs_super_nodesize(disk_super);
  859. fs_info->stripesize = btrfs_super_stripesize(disk_super);
  860. ret = btrfs_check_fs_compatibility(fs_info->super_copy);
  861. if (ret)
  862. goto out_devices;
  863. ret = btrfs_setup_chunk_tree_and_device_map(fs_info);
  864. if (ret)
  865. goto out_chunk;
  866. /* Chunk tree root is unable to read, return directly */
  867. if (!fs_info->chunk_root)
  868. return fs_info;
  869. eb = fs_info->chunk_root->node;
  870. read_extent_buffer(eb, fs_info->chunk_tree_uuid,
  871. btrfs_header_chunk_tree_uuid(eb),
  872. BTRFS_UUID_SIZE);
  873. ret = btrfs_setup_all_roots(fs_info);
  874. if (ret)
  875. goto out_chunk;
  876. return fs_info;
  877. out_chunk:
  878. btrfs_release_all_roots(fs_info);
  879. btrfs_cleanup_all_caches(fs_info);
  880. out_devices:
  881. btrfs_close_devices(fs_devices);
  882. out:
  883. btrfs_free_fs_info(fs_info);
  884. return NULL;
  885. }
  886. int close_ctree_fs_info(struct btrfs_fs_info *fs_info)
  887. {
  888. int ret;
  889. int err = 0;
  890. free_fs_roots_tree(&fs_info->fs_root_tree);
  891. btrfs_release_all_roots(fs_info);
  892. ret = btrfs_close_devices(fs_info->fs_devices);
  893. btrfs_cleanup_all_caches(fs_info);
  894. btrfs_free_fs_info(fs_info);
  895. if (!err)
  896. err = ret;
  897. return err;
  898. }
  899. int btrfs_buffer_uptodate(struct extent_buffer *buf, u64 parent_transid)
  900. {
  901. int ret;
  902. ret = extent_buffer_uptodate(buf);
  903. if (!ret)
  904. return ret;
  905. ret = verify_parent_transid(&buf->fs_info->extent_cache, buf,
  906. parent_transid, 1);
  907. return !ret;
  908. }
  909. int btrfs_set_buffer_uptodate(struct extent_buffer *eb)
  910. {
  911. return set_extent_buffer_uptodate(eb);
  912. }