free-space-tests.c 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (C) 2013 Fusion IO. All rights reserved.
  4. */
  5. #include <linux/slab.h>
  6. #include "btrfs-tests.h"
  7. #include "../ctree.h"
  8. #include "../disk-io.h"
  9. #include "../free-space-cache.h"
  10. #define BITS_PER_BITMAP (PAGE_SIZE * 8UL)
  11. /*
  12. * This test just does basic sanity checking, making sure we can add an extent
  13. * entry and remove space from either end and the middle, and make sure we can
  14. * remove space that covers adjacent extent entries.
  15. */
  16. static int test_extents(struct btrfs_block_group_cache *cache)
  17. {
  18. int ret = 0;
  19. test_msg("running extent only tests");
  20. /* First just make sure we can remove an entire entry */
  21. ret = btrfs_add_free_space(cache, 0, SZ_4M);
  22. if (ret) {
  23. test_err("error adding initial extents %d", ret);
  24. return ret;
  25. }
  26. ret = btrfs_remove_free_space(cache, 0, SZ_4M);
  27. if (ret) {
  28. test_err("error removing extent %d", ret);
  29. return ret;
  30. }
  31. if (test_check_exists(cache, 0, SZ_4M)) {
  32. test_err("full remove left some lingering space");
  33. return -1;
  34. }
  35. /* Ok edge and middle cases now */
  36. ret = btrfs_add_free_space(cache, 0, SZ_4M);
  37. if (ret) {
  38. test_err("error adding half extent %d", ret);
  39. return ret;
  40. }
  41. ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_1M);
  42. if (ret) {
  43. test_err("error removing tail end %d", ret);
  44. return ret;
  45. }
  46. ret = btrfs_remove_free_space(cache, 0, SZ_1M);
  47. if (ret) {
  48. test_err("error removing front end %d", ret);
  49. return ret;
  50. }
  51. ret = btrfs_remove_free_space(cache, SZ_2M, 4096);
  52. if (ret) {
  53. test_err("error removing middle piece %d", ret);
  54. return ret;
  55. }
  56. if (test_check_exists(cache, 0, SZ_1M)) {
  57. test_err("still have space at the front");
  58. return -1;
  59. }
  60. if (test_check_exists(cache, SZ_2M, 4096)) {
  61. test_err("still have space in the middle");
  62. return -1;
  63. }
  64. if (test_check_exists(cache, 3 * SZ_1M, SZ_1M)) {
  65. test_err("still have space at the end");
  66. return -1;
  67. }
  68. /* Cleanup */
  69. __btrfs_remove_free_space_cache(cache->free_space_ctl);
  70. return 0;
  71. }
  72. static int test_bitmaps(struct btrfs_block_group_cache *cache,
  73. u32 sectorsize)
  74. {
  75. u64 next_bitmap_offset;
  76. int ret;
  77. test_msg("running bitmap only tests");
  78. ret = test_add_free_space_entry(cache, 0, SZ_4M, 1);
  79. if (ret) {
  80. test_err("couldn't create a bitmap entry %d", ret);
  81. return ret;
  82. }
  83. ret = btrfs_remove_free_space(cache, 0, SZ_4M);
  84. if (ret) {
  85. test_err("error removing bitmap full range %d", ret);
  86. return ret;
  87. }
  88. if (test_check_exists(cache, 0, SZ_4M)) {
  89. test_err("left some space in bitmap");
  90. return -1;
  91. }
  92. ret = test_add_free_space_entry(cache, 0, SZ_4M, 1);
  93. if (ret) {
  94. test_err("couldn't add to our bitmap entry %d", ret);
  95. return ret;
  96. }
  97. ret = btrfs_remove_free_space(cache, SZ_1M, SZ_2M);
  98. if (ret) {
  99. test_err("couldn't remove middle chunk %d", ret);
  100. return ret;
  101. }
  102. /*
  103. * The first bitmap we have starts at offset 0 so the next one is just
  104. * at the end of the first bitmap.
  105. */
  106. next_bitmap_offset = (u64)(BITS_PER_BITMAP * sectorsize);
  107. /* Test a bit straddling two bitmaps */
  108. ret = test_add_free_space_entry(cache, next_bitmap_offset - SZ_2M,
  109. SZ_4M, 1);
  110. if (ret) {
  111. test_err("couldn't add space that straddles two bitmaps %d",
  112. ret);
  113. return ret;
  114. }
  115. ret = btrfs_remove_free_space(cache, next_bitmap_offset - SZ_1M, SZ_2M);
  116. if (ret) {
  117. test_err("couldn't remove overlapping space %d", ret);
  118. return ret;
  119. }
  120. if (test_check_exists(cache, next_bitmap_offset - SZ_1M, SZ_2M)) {
  121. test_err("left some space when removing overlapping");
  122. return -1;
  123. }
  124. __btrfs_remove_free_space_cache(cache->free_space_ctl);
  125. return 0;
  126. }
  127. /* This is the high grade jackassery */
  128. static int test_bitmaps_and_extents(struct btrfs_block_group_cache *cache,
  129. u32 sectorsize)
  130. {
  131. u64 bitmap_offset = (u64)(BITS_PER_BITMAP * sectorsize);
  132. int ret;
  133. test_msg("running bitmap and extent tests");
  134. /*
  135. * First let's do something simple, an extent at the same offset as the
  136. * bitmap, but the free space completely in the extent and then
  137. * completely in the bitmap.
  138. */
  139. ret = test_add_free_space_entry(cache, SZ_4M, SZ_1M, 1);
  140. if (ret) {
  141. test_err("couldn't create bitmap entry %d", ret);
  142. return ret;
  143. }
  144. ret = test_add_free_space_entry(cache, 0, SZ_1M, 0);
  145. if (ret) {
  146. test_err("couldn't add extent entry %d", ret);
  147. return ret;
  148. }
  149. ret = btrfs_remove_free_space(cache, 0, SZ_1M);
  150. if (ret) {
  151. test_err("couldn't remove extent entry %d", ret);
  152. return ret;
  153. }
  154. if (test_check_exists(cache, 0, SZ_1M)) {
  155. test_err("left remnants after our remove");
  156. return -1;
  157. }
  158. /* Now to add back the extent entry and remove from the bitmap */
  159. ret = test_add_free_space_entry(cache, 0, SZ_1M, 0);
  160. if (ret) {
  161. test_err("couldn't re-add extent entry %d", ret);
  162. return ret;
  163. }
  164. ret = btrfs_remove_free_space(cache, SZ_4M, SZ_1M);
  165. if (ret) {
  166. test_err("couldn't remove from bitmap %d", ret);
  167. return ret;
  168. }
  169. if (test_check_exists(cache, SZ_4M, SZ_1M)) {
  170. test_err("left remnants in the bitmap");
  171. return -1;
  172. }
  173. /*
  174. * Ok so a little more evil, extent entry and bitmap at the same offset,
  175. * removing an overlapping chunk.
  176. */
  177. ret = test_add_free_space_entry(cache, SZ_1M, SZ_4M, 1);
  178. if (ret) {
  179. test_err("couldn't add to a bitmap %d", ret);
  180. return ret;
  181. }
  182. ret = btrfs_remove_free_space(cache, SZ_512K, 3 * SZ_1M);
  183. if (ret) {
  184. test_err("couldn't remove overlapping space %d", ret);
  185. return ret;
  186. }
  187. if (test_check_exists(cache, SZ_512K, 3 * SZ_1M)) {
  188. test_err("left over pieces after removing overlapping");
  189. return -1;
  190. }
  191. __btrfs_remove_free_space_cache(cache->free_space_ctl);
  192. /* Now with the extent entry offset into the bitmap */
  193. ret = test_add_free_space_entry(cache, SZ_4M, SZ_4M, 1);
  194. if (ret) {
  195. test_err("couldn't add space to the bitmap %d", ret);
  196. return ret;
  197. }
  198. ret = test_add_free_space_entry(cache, SZ_2M, SZ_2M, 0);
  199. if (ret) {
  200. test_err("couldn't add extent to the cache %d", ret);
  201. return ret;
  202. }
  203. ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_4M);
  204. if (ret) {
  205. test_err("problem removing overlapping space %d", ret);
  206. return ret;
  207. }
  208. if (test_check_exists(cache, 3 * SZ_1M, SZ_4M)) {
  209. test_err("left something behind when removing space");
  210. return -1;
  211. }
  212. /*
  213. * This has blown up in the past, the extent entry starts before the
  214. * bitmap entry, but we're trying to remove an offset that falls
  215. * completely within the bitmap range and is in both the extent entry
  216. * and the bitmap entry, looks like this
  217. *
  218. * [ extent ]
  219. * [ bitmap ]
  220. * [ del ]
  221. */
  222. __btrfs_remove_free_space_cache(cache->free_space_ctl);
  223. ret = test_add_free_space_entry(cache, bitmap_offset + SZ_4M, SZ_4M, 1);
  224. if (ret) {
  225. test_err("couldn't add bitmap %d", ret);
  226. return ret;
  227. }
  228. ret = test_add_free_space_entry(cache, bitmap_offset - SZ_1M,
  229. 5 * SZ_1M, 0);
  230. if (ret) {
  231. test_err("couldn't add extent entry %d", ret);
  232. return ret;
  233. }
  234. ret = btrfs_remove_free_space(cache, bitmap_offset + SZ_1M, 5 * SZ_1M);
  235. if (ret) {
  236. test_err("failed to free our space %d", ret);
  237. return ret;
  238. }
  239. if (test_check_exists(cache, bitmap_offset + SZ_1M, 5 * SZ_1M)) {
  240. test_err("left stuff over");
  241. return -1;
  242. }
  243. __btrfs_remove_free_space_cache(cache->free_space_ctl);
  244. /*
  245. * This blew up before, we have part of the free space in a bitmap and
  246. * then the entirety of the rest of the space in an extent. This used
  247. * to return -EAGAIN back from btrfs_remove_extent, make sure this
  248. * doesn't happen.
  249. */
  250. ret = test_add_free_space_entry(cache, SZ_1M, SZ_2M, 1);
  251. if (ret) {
  252. test_err("couldn't add bitmap entry %d", ret);
  253. return ret;
  254. }
  255. ret = test_add_free_space_entry(cache, 3 * SZ_1M, SZ_1M, 0);
  256. if (ret) {
  257. test_err("couldn't add extent entry %d", ret);
  258. return ret;
  259. }
  260. ret = btrfs_remove_free_space(cache, SZ_1M, 3 * SZ_1M);
  261. if (ret) {
  262. test_err("error removing bitmap and extent overlapping %d", ret);
  263. return ret;
  264. }
  265. __btrfs_remove_free_space_cache(cache->free_space_ctl);
  266. return 0;
  267. }
  268. /* Used by test_steal_space_from_bitmap_to_extent(). */
  269. static bool test_use_bitmap(struct btrfs_free_space_ctl *ctl,
  270. struct btrfs_free_space *info)
  271. {
  272. return ctl->free_extents > 0;
  273. }
  274. /* Used by test_steal_space_from_bitmap_to_extent(). */
  275. static int
  276. check_num_extents_and_bitmaps(const struct btrfs_block_group_cache *cache,
  277. const int num_extents,
  278. const int num_bitmaps)
  279. {
  280. if (cache->free_space_ctl->free_extents != num_extents) {
  281. test_err(
  282. "incorrect # of extent entries in the cache: %d, expected %d",
  283. cache->free_space_ctl->free_extents, num_extents);
  284. return -EINVAL;
  285. }
  286. if (cache->free_space_ctl->total_bitmaps != num_bitmaps) {
  287. test_err(
  288. "incorrect # of extent entries in the cache: %d, expected %d",
  289. cache->free_space_ctl->total_bitmaps, num_bitmaps);
  290. return -EINVAL;
  291. }
  292. return 0;
  293. }
  294. /* Used by test_steal_space_from_bitmap_to_extent(). */
  295. static int check_cache_empty(struct btrfs_block_group_cache *cache)
  296. {
  297. u64 offset;
  298. u64 max_extent_size;
  299. /*
  300. * Now lets confirm that there's absolutely no free space left to
  301. * allocate.
  302. */
  303. if (cache->free_space_ctl->free_space != 0) {
  304. test_err("cache free space is not 0");
  305. return -EINVAL;
  306. }
  307. /* And any allocation request, no matter how small, should fail now. */
  308. offset = btrfs_find_space_for_alloc(cache, 0, 4096, 0,
  309. &max_extent_size);
  310. if (offset != 0) {
  311. test_err("space allocation did not fail, returned offset: %llu",
  312. offset);
  313. return -EINVAL;
  314. }
  315. /* And no extent nor bitmap entries in the cache anymore. */
  316. return check_num_extents_and_bitmaps(cache, 0, 0);
  317. }
  318. /*
  319. * Before we were able to steal free space from a bitmap entry to an extent
  320. * entry, we could end up with 2 entries representing a contiguous free space.
  321. * One would be an extent entry and the other a bitmap entry. Since in order
  322. * to allocate space to a caller we use only 1 entry, we couldn't return that
  323. * whole range to the caller if it was requested. This forced the caller to
  324. * either assume ENOSPC or perform several smaller space allocations, which
  325. * wasn't optimal as they could be spread all over the block group while under
  326. * concurrency (extra overhead and fragmentation).
  327. *
  328. * This stealing approach is beneficial, since we always prefer to allocate
  329. * from extent entries, both for clustered and non-clustered allocation
  330. * requests.
  331. */
  332. static int
  333. test_steal_space_from_bitmap_to_extent(struct btrfs_block_group_cache *cache,
  334. u32 sectorsize)
  335. {
  336. int ret;
  337. u64 offset;
  338. u64 max_extent_size;
  339. const struct btrfs_free_space_op test_free_space_ops = {
  340. .recalc_thresholds = cache->free_space_ctl->op->recalc_thresholds,
  341. .use_bitmap = test_use_bitmap,
  342. };
  343. const struct btrfs_free_space_op *orig_free_space_ops;
  344. test_msg("running space stealing from bitmap to extent");
  345. /*
  346. * For this test, we want to ensure we end up with an extent entry
  347. * immediately adjacent to a bitmap entry, where the bitmap starts
  348. * at an offset where the extent entry ends. We keep adding and
  349. * removing free space to reach into this state, but to get there
  350. * we need to reach a point where marking new free space doesn't
  351. * result in adding new extent entries or merging the new space
  352. * with existing extent entries - the space ends up being marked
  353. * in an existing bitmap that covers the new free space range.
  354. *
  355. * To get there, we need to reach the threshold defined set at
  356. * cache->free_space_ctl->extents_thresh, which currently is
  357. * 256 extents on a x86_64 system at least, and a few other
  358. * conditions (check free_space_cache.c). Instead of making the
  359. * test much longer and complicated, use a "use_bitmap" operation
  360. * that forces use of bitmaps as soon as we have at least 1
  361. * extent entry.
  362. */
  363. orig_free_space_ops = cache->free_space_ctl->op;
  364. cache->free_space_ctl->op = &test_free_space_ops;
  365. /*
  366. * Extent entry covering free space range [128Mb - 256Kb, 128Mb - 128Kb[
  367. */
  368. ret = test_add_free_space_entry(cache, SZ_128M - SZ_256K, SZ_128K, 0);
  369. if (ret) {
  370. test_err("couldn't add extent entry %d", ret);
  371. return ret;
  372. }
  373. /* Bitmap entry covering free space range [128Mb + 512Kb, 256Mb[ */
  374. ret = test_add_free_space_entry(cache, SZ_128M + SZ_512K,
  375. SZ_128M - SZ_512K, 1);
  376. if (ret) {
  377. test_err("couldn't add bitmap entry %d", ret);
  378. return ret;
  379. }
  380. ret = check_num_extents_and_bitmaps(cache, 2, 1);
  381. if (ret)
  382. return ret;
  383. /*
  384. * Now make only the first 256Kb of the bitmap marked as free, so that
  385. * we end up with only the following ranges marked as free space:
  386. *
  387. * [128Mb - 256Kb, 128Mb - 128Kb[
  388. * [128Mb + 512Kb, 128Mb + 768Kb[
  389. */
  390. ret = btrfs_remove_free_space(cache,
  391. SZ_128M + 768 * SZ_1K,
  392. SZ_128M - 768 * SZ_1K);
  393. if (ret) {
  394. test_err("failed to free part of bitmap space %d", ret);
  395. return ret;
  396. }
  397. /* Confirm that only those 2 ranges are marked as free. */
  398. if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_128K)) {
  399. test_err("free space range missing");
  400. return -ENOENT;
  401. }
  402. if (!test_check_exists(cache, SZ_128M + SZ_512K, SZ_256K)) {
  403. test_err("free space range missing");
  404. return -ENOENT;
  405. }
  406. /*
  407. * Confirm that the bitmap range [128Mb + 768Kb, 256Mb[ isn't marked
  408. * as free anymore.
  409. */
  410. if (test_check_exists(cache, SZ_128M + 768 * SZ_1K,
  411. SZ_128M - 768 * SZ_1K)) {
  412. test_err("bitmap region not removed from space cache");
  413. return -EINVAL;
  414. }
  415. /*
  416. * Confirm that the region [128Mb + 256Kb, 128Mb + 512Kb[, which is
  417. * covered by the bitmap, isn't marked as free.
  418. */
  419. if (test_check_exists(cache, SZ_128M + SZ_256K, SZ_256K)) {
  420. test_err("invalid bitmap region marked as free");
  421. return -EINVAL;
  422. }
  423. /*
  424. * Confirm that the region [128Mb, 128Mb + 256Kb[, which is covered
  425. * by the bitmap too, isn't marked as free either.
  426. */
  427. if (test_check_exists(cache, SZ_128M, SZ_256K)) {
  428. test_err("invalid bitmap region marked as free");
  429. return -EINVAL;
  430. }
  431. /*
  432. * Now lets mark the region [128Mb, 128Mb + 512Kb[ as free too. But,
  433. * lets make sure the free space cache marks it as free in the bitmap,
  434. * and doesn't insert a new extent entry to represent this region.
  435. */
  436. ret = btrfs_add_free_space(cache, SZ_128M, SZ_512K);
  437. if (ret) {
  438. test_err("error adding free space: %d", ret);
  439. return ret;
  440. }
  441. /* Confirm the region is marked as free. */
  442. if (!test_check_exists(cache, SZ_128M, SZ_512K)) {
  443. test_err("bitmap region not marked as free");
  444. return -ENOENT;
  445. }
  446. /*
  447. * Confirm that no new extent entries or bitmap entries were added to
  448. * the cache after adding that free space region.
  449. */
  450. ret = check_num_extents_and_bitmaps(cache, 2, 1);
  451. if (ret)
  452. return ret;
  453. /*
  454. * Now lets add a small free space region to the right of the previous
  455. * one, which is not contiguous with it and is part of the bitmap too.
  456. * The goal is to test that the bitmap entry space stealing doesn't
  457. * steal this space region.
  458. */
  459. ret = btrfs_add_free_space(cache, SZ_128M + SZ_16M, sectorsize);
  460. if (ret) {
  461. test_err("error adding free space: %d", ret);
  462. return ret;
  463. }
  464. /*
  465. * Confirm that no new extent entries or bitmap entries were added to
  466. * the cache after adding that free space region.
  467. */
  468. ret = check_num_extents_and_bitmaps(cache, 2, 1);
  469. if (ret)
  470. return ret;
  471. /*
  472. * Now mark the region [128Mb - 128Kb, 128Mb[ as free too. This will
  473. * expand the range covered by the existing extent entry that represents
  474. * the free space [128Mb - 256Kb, 128Mb - 128Kb[.
  475. */
  476. ret = btrfs_add_free_space(cache, SZ_128M - SZ_128K, SZ_128K);
  477. if (ret) {
  478. test_err("error adding free space: %d", ret);
  479. return ret;
  480. }
  481. /* Confirm the region is marked as free. */
  482. if (!test_check_exists(cache, SZ_128M - SZ_128K, SZ_128K)) {
  483. test_err("extent region not marked as free");
  484. return -ENOENT;
  485. }
  486. /*
  487. * Confirm that our extent entry didn't stole all free space from the
  488. * bitmap, because of the small 4Kb free space region.
  489. */
  490. ret = check_num_extents_and_bitmaps(cache, 2, 1);
  491. if (ret)
  492. return ret;
  493. /*
  494. * So now we have the range [128Mb - 256Kb, 128Mb + 768Kb[ as free
  495. * space. Without stealing bitmap free space into extent entry space,
  496. * we would have all this free space represented by 2 entries in the
  497. * cache:
  498. *
  499. * extent entry covering range: [128Mb - 256Kb, 128Mb[
  500. * bitmap entry covering range: [128Mb, 128Mb + 768Kb[
  501. *
  502. * Attempting to allocate the whole free space (1Mb) would fail, because
  503. * we can't allocate from multiple entries.
  504. * With the bitmap free space stealing, we get a single extent entry
  505. * that represents the 1Mb free space, and therefore we're able to
  506. * allocate the whole free space at once.
  507. */
  508. if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_1M)) {
  509. test_err("expected region not marked as free");
  510. return -ENOENT;
  511. }
  512. if (cache->free_space_ctl->free_space != (SZ_1M + sectorsize)) {
  513. test_err("cache free space is not 1Mb + %u", sectorsize);
  514. return -EINVAL;
  515. }
  516. offset = btrfs_find_space_for_alloc(cache,
  517. 0, SZ_1M, 0,
  518. &max_extent_size);
  519. if (offset != (SZ_128M - SZ_256K)) {
  520. test_err(
  521. "failed to allocate 1Mb from space cache, returned offset is: %llu",
  522. offset);
  523. return -EINVAL;
  524. }
  525. /*
  526. * All that remains is a sectorsize free space region in a bitmap.
  527. * Confirm.
  528. */
  529. ret = check_num_extents_and_bitmaps(cache, 1, 1);
  530. if (ret)
  531. return ret;
  532. if (cache->free_space_ctl->free_space != sectorsize) {
  533. test_err("cache free space is not %u", sectorsize);
  534. return -EINVAL;
  535. }
  536. offset = btrfs_find_space_for_alloc(cache,
  537. 0, sectorsize, 0,
  538. &max_extent_size);
  539. if (offset != (SZ_128M + SZ_16M)) {
  540. test_err("failed to allocate %u, returned offset : %llu",
  541. sectorsize, offset);
  542. return -EINVAL;
  543. }
  544. ret = check_cache_empty(cache);
  545. if (ret)
  546. return ret;
  547. __btrfs_remove_free_space_cache(cache->free_space_ctl);
  548. /*
  549. * Now test a similar scenario, but where our extent entry is located
  550. * to the right of the bitmap entry, so that we can check that stealing
  551. * space from a bitmap to the front of an extent entry works.
  552. */
  553. /*
  554. * Extent entry covering free space range [128Mb + 128Kb, 128Mb + 256Kb[
  555. */
  556. ret = test_add_free_space_entry(cache, SZ_128M + SZ_128K, SZ_128K, 0);
  557. if (ret) {
  558. test_err("couldn't add extent entry %d", ret);
  559. return ret;
  560. }
  561. /* Bitmap entry covering free space range [0, 128Mb - 512Kb[ */
  562. ret = test_add_free_space_entry(cache, 0, SZ_128M - SZ_512K, 1);
  563. if (ret) {
  564. test_err("couldn't add bitmap entry %d", ret);
  565. return ret;
  566. }
  567. ret = check_num_extents_and_bitmaps(cache, 2, 1);
  568. if (ret)
  569. return ret;
  570. /*
  571. * Now make only the last 256Kb of the bitmap marked as free, so that
  572. * we end up with only the following ranges marked as free space:
  573. *
  574. * [128Mb + 128b, 128Mb + 256Kb[
  575. * [128Mb - 768Kb, 128Mb - 512Kb[
  576. */
  577. ret = btrfs_remove_free_space(cache, 0, SZ_128M - 768 * SZ_1K);
  578. if (ret) {
  579. test_err("failed to free part of bitmap space %d", ret);
  580. return ret;
  581. }
  582. /* Confirm that only those 2 ranges are marked as free. */
  583. if (!test_check_exists(cache, SZ_128M + SZ_128K, SZ_128K)) {
  584. test_err("free space range missing");
  585. return -ENOENT;
  586. }
  587. if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_256K)) {
  588. test_err("free space range missing");
  589. return -ENOENT;
  590. }
  591. /*
  592. * Confirm that the bitmap range [0, 128Mb - 768Kb[ isn't marked
  593. * as free anymore.
  594. */
  595. if (test_check_exists(cache, 0, SZ_128M - 768 * SZ_1K)) {
  596. test_err("bitmap region not removed from space cache");
  597. return -EINVAL;
  598. }
  599. /*
  600. * Confirm that the region [128Mb - 512Kb, 128Mb[, which is
  601. * covered by the bitmap, isn't marked as free.
  602. */
  603. if (test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) {
  604. test_err("invalid bitmap region marked as free");
  605. return -EINVAL;
  606. }
  607. /*
  608. * Now lets mark the region [128Mb - 512Kb, 128Mb[ as free too. But,
  609. * lets make sure the free space cache marks it as free in the bitmap,
  610. * and doesn't insert a new extent entry to represent this region.
  611. */
  612. ret = btrfs_add_free_space(cache, SZ_128M - SZ_512K, SZ_512K);
  613. if (ret) {
  614. test_err("error adding free space: %d", ret);
  615. return ret;
  616. }
  617. /* Confirm the region is marked as free. */
  618. if (!test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) {
  619. test_err("bitmap region not marked as free");
  620. return -ENOENT;
  621. }
  622. /*
  623. * Confirm that no new extent entries or bitmap entries were added to
  624. * the cache after adding that free space region.
  625. */
  626. ret = check_num_extents_and_bitmaps(cache, 2, 1);
  627. if (ret)
  628. return ret;
  629. /*
  630. * Now lets add a small free space region to the left of the previous
  631. * one, which is not contiguous with it and is part of the bitmap too.
  632. * The goal is to test that the bitmap entry space stealing doesn't
  633. * steal this space region.
  634. */
  635. ret = btrfs_add_free_space(cache, SZ_32M, 2 * sectorsize);
  636. if (ret) {
  637. test_err("error adding free space: %d", ret);
  638. return ret;
  639. }
  640. /*
  641. * Now mark the region [128Mb, 128Mb + 128Kb[ as free too. This will
  642. * expand the range covered by the existing extent entry that represents
  643. * the free space [128Mb + 128Kb, 128Mb + 256Kb[.
  644. */
  645. ret = btrfs_add_free_space(cache, SZ_128M, SZ_128K);
  646. if (ret) {
  647. test_err("error adding free space: %d", ret);
  648. return ret;
  649. }
  650. /* Confirm the region is marked as free. */
  651. if (!test_check_exists(cache, SZ_128M, SZ_128K)) {
  652. test_err("extent region not marked as free");
  653. return -ENOENT;
  654. }
  655. /*
  656. * Confirm that our extent entry didn't stole all free space from the
  657. * bitmap, because of the small 2 * sectorsize free space region.
  658. */
  659. ret = check_num_extents_and_bitmaps(cache, 2, 1);
  660. if (ret)
  661. return ret;
  662. /*
  663. * So now we have the range [128Mb - 768Kb, 128Mb + 256Kb[ as free
  664. * space. Without stealing bitmap free space into extent entry space,
  665. * we would have all this free space represented by 2 entries in the
  666. * cache:
  667. *
  668. * extent entry covering range: [128Mb, 128Mb + 256Kb[
  669. * bitmap entry covering range: [128Mb - 768Kb, 128Mb[
  670. *
  671. * Attempting to allocate the whole free space (1Mb) would fail, because
  672. * we can't allocate from multiple entries.
  673. * With the bitmap free space stealing, we get a single extent entry
  674. * that represents the 1Mb free space, and therefore we're able to
  675. * allocate the whole free space at once.
  676. */
  677. if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_1M)) {
  678. test_err("expected region not marked as free");
  679. return -ENOENT;
  680. }
  681. if (cache->free_space_ctl->free_space != (SZ_1M + 2 * sectorsize)) {
  682. test_err("cache free space is not 1Mb + %u", 2 * sectorsize);
  683. return -EINVAL;
  684. }
  685. offset = btrfs_find_space_for_alloc(cache, 0, SZ_1M, 0,
  686. &max_extent_size);
  687. if (offset != (SZ_128M - 768 * SZ_1K)) {
  688. test_err(
  689. "failed to allocate 1Mb from space cache, returned offset is: %llu",
  690. offset);
  691. return -EINVAL;
  692. }
  693. /*
  694. * All that remains is 2 * sectorsize free space region
  695. * in a bitmap. Confirm.
  696. */
  697. ret = check_num_extents_and_bitmaps(cache, 1, 1);
  698. if (ret)
  699. return ret;
  700. if (cache->free_space_ctl->free_space != 2 * sectorsize) {
  701. test_err("cache free space is not %u", 2 * sectorsize);
  702. return -EINVAL;
  703. }
  704. offset = btrfs_find_space_for_alloc(cache,
  705. 0, 2 * sectorsize, 0,
  706. &max_extent_size);
  707. if (offset != SZ_32M) {
  708. test_err("failed to allocate %u, offset: %llu",
  709. 2 * sectorsize, offset);
  710. return -EINVAL;
  711. }
  712. ret = check_cache_empty(cache);
  713. if (ret)
  714. return ret;
  715. cache->free_space_ctl->op = orig_free_space_ops;
  716. __btrfs_remove_free_space_cache(cache->free_space_ctl);
  717. return 0;
  718. }
  719. int btrfs_test_free_space_cache(u32 sectorsize, u32 nodesize)
  720. {
  721. struct btrfs_fs_info *fs_info;
  722. struct btrfs_block_group_cache *cache;
  723. struct btrfs_root *root = NULL;
  724. int ret = -ENOMEM;
  725. test_msg("running btrfs free space cache tests");
  726. fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
  727. if (!fs_info)
  728. return -ENOMEM;
  729. /*
  730. * For ppc64 (with 64k page size), bytes per bitmap might be
  731. * larger than 1G. To make bitmap test available in ppc64,
  732. * alloc dummy block group whose size cross bitmaps.
  733. */
  734. cache = btrfs_alloc_dummy_block_group(fs_info,
  735. BITS_PER_BITMAP * sectorsize + PAGE_SIZE);
  736. if (!cache) {
  737. test_err("couldn't run the tests");
  738. btrfs_free_dummy_fs_info(fs_info);
  739. return 0;
  740. }
  741. root = btrfs_alloc_dummy_root(fs_info);
  742. if (IS_ERR(root)) {
  743. ret = PTR_ERR(root);
  744. goto out;
  745. }
  746. root->fs_info->extent_root = root;
  747. ret = test_extents(cache);
  748. if (ret)
  749. goto out;
  750. ret = test_bitmaps(cache, sectorsize);
  751. if (ret)
  752. goto out;
  753. ret = test_bitmaps_and_extents(cache, sectorsize);
  754. if (ret)
  755. goto out;
  756. ret = test_steal_space_from_bitmap_to_extent(cache, sectorsize);
  757. out:
  758. btrfs_free_dummy_block_group(cache);
  759. btrfs_free_dummy_root(root);
  760. btrfs_free_dummy_fs_info(fs_info);
  761. test_msg("free space cache tests finished");
  762. return ret;
  763. }