disk-io.c 27 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090
  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. ALLOC_CACHE_ALIGN_BUFFER(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. node = rb_search(&fs_info->fs_root_tree, (void *)&objectid,
  651. btrfs_fs_roots_compare_objectids, NULL);
  652. if (node)
  653. return container_of(node, struct btrfs_root, rb_node);
  654. root = btrfs_read_fs_root_no_cache(fs_info, location);
  655. if (IS_ERR(root))
  656. return root;
  657. ret = rb_insert(&fs_info->fs_root_tree, &root->rb_node,
  658. btrfs_fs_roots_compare_roots);
  659. BUG_ON(ret);
  660. return root;
  661. }
  662. void btrfs_free_fs_info(struct btrfs_fs_info *fs_info)
  663. {
  664. free(fs_info->tree_root);
  665. free(fs_info->chunk_root);
  666. free(fs_info->csum_root);
  667. free(fs_info->super_copy);
  668. free(fs_info);
  669. }
  670. struct btrfs_fs_info *btrfs_new_fs_info(void)
  671. {
  672. struct btrfs_fs_info *fs_info;
  673. fs_info = calloc(1, sizeof(struct btrfs_fs_info));
  674. if (!fs_info)
  675. return NULL;
  676. fs_info->tree_root = calloc(1, sizeof(struct btrfs_root));
  677. fs_info->chunk_root = calloc(1, sizeof(struct btrfs_root));
  678. fs_info->csum_root = calloc(1, sizeof(struct btrfs_root));
  679. fs_info->super_copy = calloc(1, BTRFS_SUPER_INFO_SIZE);
  680. if (!fs_info->tree_root || !fs_info->chunk_root ||
  681. !fs_info->csum_root || !fs_info->super_copy)
  682. goto free_all;
  683. extent_io_tree_init(&fs_info->extent_cache);
  684. fs_info->fs_root_tree = RB_ROOT;
  685. cache_tree_init(&fs_info->mapping_tree.cache_tree);
  686. mutex_init(&fs_info->fs_mutex);
  687. return fs_info;
  688. free_all:
  689. btrfs_free_fs_info(fs_info);
  690. return NULL;
  691. }
  692. static int setup_root_or_create_block(struct btrfs_fs_info *fs_info,
  693. struct btrfs_root *info_root,
  694. u64 objectid, char *str)
  695. {
  696. struct btrfs_root *root = fs_info->tree_root;
  697. int ret;
  698. ret = find_and_setup_root(root, fs_info, objectid, info_root);
  699. if (ret) {
  700. error("could not setup %s tree", str);
  701. return -EIO;
  702. }
  703. return 0;
  704. }
  705. static int get_default_subvolume(struct btrfs_fs_info *fs_info,
  706. struct btrfs_key *key_ret)
  707. {
  708. struct btrfs_root *root = fs_info->tree_root;
  709. struct btrfs_dir_item *dir_item;
  710. struct btrfs_path path;
  711. int ret = 0;
  712. btrfs_init_path(&path);
  713. dir_item = btrfs_lookup_dir_item(NULL, root, &path,
  714. BTRFS_ROOT_TREE_DIR_OBJECTID,
  715. "default", 7, 0);
  716. if (IS_ERR(dir_item)) {
  717. ret = PTR_ERR(dir_item);
  718. goto out;
  719. }
  720. btrfs_dir_item_key_to_cpu(path.nodes[0], dir_item, key_ret);
  721. out:
  722. btrfs_release_path(&path);
  723. return ret;
  724. }
  725. int btrfs_setup_all_roots(struct btrfs_fs_info *fs_info)
  726. {
  727. struct btrfs_super_block *sb = fs_info->super_copy;
  728. struct btrfs_root *root;
  729. struct btrfs_key key;
  730. u64 root_tree_bytenr;
  731. u64 generation;
  732. int ret;
  733. root = fs_info->tree_root;
  734. btrfs_setup_root(root, fs_info, BTRFS_ROOT_TREE_OBJECTID);
  735. generation = btrfs_super_generation(sb);
  736. root_tree_bytenr = btrfs_super_root(sb);
  737. root->node = read_tree_block(fs_info, root_tree_bytenr, generation);
  738. if (!extent_buffer_uptodate(root->node)) {
  739. fprintf(stderr, "Couldn't read tree root\n");
  740. return -EIO;
  741. }
  742. ret = setup_root_or_create_block(fs_info, fs_info->csum_root,
  743. BTRFS_CSUM_TREE_OBJECTID, "csum");
  744. if (ret)
  745. return ret;
  746. fs_info->csum_root->track_dirty = 1;
  747. fs_info->last_trans_committed = generation;
  748. ret = get_default_subvolume(fs_info, &key);
  749. if (ret) {
  750. /*
  751. * The default dir item isn't there. Linux kernel behaviour is
  752. * to silently use the top-level subvolume in this case.
  753. */
  754. key.objectid = BTRFS_FS_TREE_OBJECTID;
  755. key.type = BTRFS_ROOT_ITEM_KEY;
  756. key.offset = (u64)-1;
  757. }
  758. fs_info->fs_root = btrfs_read_fs_root(fs_info, &key);
  759. if (IS_ERR(fs_info->fs_root))
  760. return -EIO;
  761. return 0;
  762. }
  763. void btrfs_release_all_roots(struct btrfs_fs_info *fs_info)
  764. {
  765. if (fs_info->csum_root)
  766. free_extent_buffer(fs_info->csum_root->node);
  767. if (fs_info->tree_root)
  768. free_extent_buffer(fs_info->tree_root->node);
  769. if (fs_info->chunk_root)
  770. free_extent_buffer(fs_info->chunk_root->node);
  771. }
  772. static void free_map_lookup(struct cache_extent *ce)
  773. {
  774. struct map_lookup *map;
  775. map = container_of(ce, struct map_lookup, ce);
  776. kfree(map);
  777. }
  778. FREE_EXTENT_CACHE_BASED_TREE(mapping_cache, free_map_lookup);
  779. void btrfs_cleanup_all_caches(struct btrfs_fs_info *fs_info)
  780. {
  781. free_mapping_cache_tree(&fs_info->mapping_tree.cache_tree);
  782. extent_io_tree_cleanup(&fs_info->extent_cache);
  783. }
  784. static int btrfs_scan_fs_devices(struct blk_desc *desc,
  785. struct disk_partition *part,
  786. struct btrfs_fs_devices **fs_devices)
  787. {
  788. u64 total_devs;
  789. int ret;
  790. if (round_up(BTRFS_SUPER_INFO_SIZE + BTRFS_SUPER_INFO_OFFSET,
  791. desc->blksz) > (part->size << desc->log2blksz)) {
  792. error("superblock end %u is larger than device size " LBAFU,
  793. BTRFS_SUPER_INFO_SIZE + BTRFS_SUPER_INFO_OFFSET,
  794. part->size << desc->log2blksz);
  795. return -EINVAL;
  796. }
  797. ret = btrfs_scan_one_device(desc, part, fs_devices, &total_devs);
  798. if (ret) {
  799. fprintf(stderr, "No valid Btrfs found\n");
  800. return ret;
  801. }
  802. return 0;
  803. }
  804. int btrfs_check_fs_compatibility(struct btrfs_super_block *sb)
  805. {
  806. u64 features;
  807. features = btrfs_super_incompat_flags(sb) &
  808. ~BTRFS_FEATURE_INCOMPAT_SUPP;
  809. if (features) {
  810. printk("couldn't open because of unsupported "
  811. "option features (%llx).\n",
  812. (unsigned long long)features);
  813. return -ENOTSUPP;
  814. }
  815. features = btrfs_super_incompat_flags(sb);
  816. if (!(features & BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF)) {
  817. features |= BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF;
  818. btrfs_set_super_incompat_flags(sb, features);
  819. }
  820. return 0;
  821. }
  822. static int btrfs_setup_chunk_tree_and_device_map(struct btrfs_fs_info *fs_info)
  823. {
  824. struct btrfs_super_block *sb = fs_info->super_copy;
  825. u64 chunk_root_bytenr;
  826. u64 generation;
  827. int ret;
  828. btrfs_setup_root(fs_info->chunk_root, fs_info,
  829. BTRFS_CHUNK_TREE_OBJECTID);
  830. ret = btrfs_read_sys_array(fs_info);
  831. if (ret)
  832. return ret;
  833. generation = btrfs_super_chunk_root_generation(sb);
  834. chunk_root_bytenr = btrfs_super_chunk_root(sb);
  835. fs_info->chunk_root->node = read_tree_block(fs_info,
  836. chunk_root_bytenr,
  837. generation);
  838. if (!extent_buffer_uptodate(fs_info->chunk_root->node)) {
  839. error("cannot read chunk root");
  840. return -EIO;
  841. }
  842. ret = btrfs_read_chunk_tree(fs_info);
  843. if (ret) {
  844. fprintf(stderr, "Couldn't read chunk tree\n");
  845. return ret;
  846. }
  847. return 0;
  848. }
  849. struct btrfs_fs_info *open_ctree_fs_info(struct blk_desc *desc,
  850. struct disk_partition *part)
  851. {
  852. struct btrfs_fs_info *fs_info;
  853. struct btrfs_super_block *disk_super;
  854. struct btrfs_fs_devices *fs_devices = NULL;
  855. struct extent_buffer *eb;
  856. int ret;
  857. fs_info = btrfs_new_fs_info();
  858. if (!fs_info) {
  859. fprintf(stderr, "Failed to allocate memory for fs_info\n");
  860. return NULL;
  861. }
  862. ret = btrfs_scan_fs_devices(desc, part, &fs_devices);
  863. if (ret)
  864. goto out;
  865. fs_info->fs_devices = fs_devices;
  866. ret = btrfs_open_devices(fs_devices);
  867. if (ret)
  868. goto out;
  869. disk_super = fs_info->super_copy;
  870. ret = btrfs_read_dev_super(desc, part, disk_super);
  871. if (ret) {
  872. printk("No valid btrfs found\n");
  873. goto out_devices;
  874. }
  875. if (btrfs_super_flags(disk_super) & BTRFS_SUPER_FLAG_CHANGING_FSID) {
  876. fprintf(stderr, "ERROR: Filesystem UUID change in progress\n");
  877. goto out_devices;
  878. }
  879. ASSERT(!memcmp(disk_super->fsid, fs_devices->fsid, BTRFS_FSID_SIZE));
  880. if (btrfs_fs_incompat(fs_info, METADATA_UUID))
  881. ASSERT(!memcmp(disk_super->metadata_uuid,
  882. fs_devices->metadata_uuid, BTRFS_FSID_SIZE));
  883. fs_info->sectorsize = btrfs_super_sectorsize(disk_super);
  884. fs_info->nodesize = btrfs_super_nodesize(disk_super);
  885. fs_info->stripesize = btrfs_super_stripesize(disk_super);
  886. ret = btrfs_check_fs_compatibility(fs_info->super_copy);
  887. if (ret)
  888. goto out_devices;
  889. ret = btrfs_setup_chunk_tree_and_device_map(fs_info);
  890. if (ret)
  891. goto out_chunk;
  892. /* Chunk tree root is unable to read, return directly */
  893. if (!fs_info->chunk_root)
  894. return fs_info;
  895. eb = fs_info->chunk_root->node;
  896. read_extent_buffer(eb, fs_info->chunk_tree_uuid,
  897. btrfs_header_chunk_tree_uuid(eb),
  898. BTRFS_UUID_SIZE);
  899. ret = btrfs_setup_all_roots(fs_info);
  900. if (ret)
  901. goto out_chunk;
  902. return fs_info;
  903. out_chunk:
  904. btrfs_release_all_roots(fs_info);
  905. btrfs_cleanup_all_caches(fs_info);
  906. out_devices:
  907. btrfs_close_devices(fs_devices);
  908. out:
  909. btrfs_free_fs_info(fs_info);
  910. return NULL;
  911. }
  912. int close_ctree_fs_info(struct btrfs_fs_info *fs_info)
  913. {
  914. int ret;
  915. free_fs_roots_tree(&fs_info->fs_root_tree);
  916. btrfs_release_all_roots(fs_info);
  917. ret = btrfs_close_devices(fs_info->fs_devices);
  918. btrfs_cleanup_all_caches(fs_info);
  919. btrfs_free_fs_info(fs_info);
  920. return ret;
  921. }
  922. int btrfs_buffer_uptodate(struct extent_buffer *buf, u64 parent_transid)
  923. {
  924. int ret;
  925. ret = extent_buffer_uptodate(buf);
  926. if (!ret)
  927. return ret;
  928. ret = verify_parent_transid(&buf->fs_info->extent_cache, buf,
  929. parent_transid, 1);
  930. return !ret;
  931. }
  932. int btrfs_set_buffer_uptodate(struct extent_buffer *eb)
  933. {
  934. return set_extent_buffer_uptodate(eb);
  935. }