lcnalloc.c 32 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014
  1. /*
  2. * lcnalloc.c - Cluster (de)allocation code. Part of the Linux-NTFS project.
  3. *
  4. * Copyright (c) 2004-2005 Anton Altaparmakov
  5. *
  6. * This program/include file is free software; you can redistribute it and/or
  7. * modify it under the terms of the GNU General Public License as published
  8. * by the Free Software Foundation; either version 2 of the License, or
  9. * (at your option) any later version.
  10. *
  11. * This program/include file is distributed in the hope that it will be
  12. * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  13. * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14. * GNU General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU General Public License
  17. * along with this program (in the main directory of the Linux-NTFS
  18. * distribution in the file COPYING); if not, write to the Free Software
  19. * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  20. */
  21. #ifdef NTFS_RW
  22. #include <linux/pagemap.h>
  23. #include "lcnalloc.h"
  24. #include "debug.h"
  25. #include "bitmap.h"
  26. #include "inode.h"
  27. #include "volume.h"
  28. #include "attrib.h"
  29. #include "malloc.h"
  30. #include "aops.h"
  31. #include "ntfs.h"
  32. /**
  33. * ntfs_cluster_free_from_rl_nolock - free clusters from runlist
  34. * @vol: mounted ntfs volume on which to free the clusters
  35. * @rl: runlist describing the clusters to free
  36. *
  37. * Free all the clusters described by the runlist @rl on the volume @vol. In
  38. * the case of an error being returned, at least some of the clusters were not
  39. * freed.
  40. *
  41. * Return 0 on success and -errno on error.
  42. *
  43. * Locking: - The volume lcn bitmap must be locked for writing on entry and is
  44. * left locked on return.
  45. */
  46. int ntfs_cluster_free_from_rl_nolock(ntfs_volume *vol,
  47. const runlist_element *rl)
  48. {
  49. struct inode *lcnbmp_vi = vol->lcnbmp_ino;
  50. int ret = 0;
  51. ntfs_debug("Entering.");
  52. if (!rl)
  53. return 0;
  54. for (; rl->length; rl++) {
  55. int err;
  56. if (rl->lcn < 0)
  57. continue;
  58. err = ntfs_bitmap_clear_run(lcnbmp_vi, rl->lcn, rl->length);
  59. if (unlikely(err && (!ret || ret == -ENOMEM) && ret != err))
  60. ret = err;
  61. }
  62. ntfs_debug("Done.");
  63. return ret;
  64. }
  65. /**
  66. * ntfs_cluster_alloc - allocate clusters on an ntfs volume
  67. * @vol: mounted ntfs volume on which to allocate the clusters
  68. * @start_vcn: vcn to use for the first allocated cluster
  69. * @count: number of clusters to allocate
  70. * @start_lcn: starting lcn at which to allocate the clusters (or -1 if none)
  71. * @zone: zone from which to allocate the clusters
  72. * @is_extension: if 'true', this is an attribute extension
  73. *
  74. * Allocate @count clusters preferably starting at cluster @start_lcn or at the
  75. * current allocator position if @start_lcn is -1, on the mounted ntfs volume
  76. * @vol. @zone is either DATA_ZONE for allocation of normal clusters or
  77. * MFT_ZONE for allocation of clusters for the master file table, i.e. the
  78. * $MFT/$DATA attribute.
  79. *
  80. * @start_vcn specifies the vcn of the first allocated cluster. This makes
  81. * merging the resulting runlist with the old runlist easier.
  82. *
  83. * If @is_extension is 'true', the caller is allocating clusters to extend an
  84. * attribute and if it is 'false', the caller is allocating clusters to fill a
  85. * hole in an attribute. Practically the difference is that if @is_extension
  86. * is 'true' the returned runlist will be terminated with LCN_ENOENT and if
  87. * @is_extension is 'false' the runlist will be terminated with
  88. * LCN_RL_NOT_MAPPED.
  89. *
  90. * You need to check the return value with IS_ERR(). If this is false, the
  91. * function was successful and the return value is a runlist describing the
  92. * allocated cluster(s). If IS_ERR() is true, the function failed and
  93. * PTR_ERR() gives you the error code.
  94. *
  95. * Notes on the allocation algorithm
  96. * =================================
  97. *
  98. * There are two data zones. First is the area between the end of the mft zone
  99. * and the end of the volume, and second is the area between the start of the
  100. * volume and the start of the mft zone. On unmodified/standard NTFS 1.x
  101. * volumes, the second data zone does not exist due to the mft zone being
  102. * expanded to cover the start of the volume in order to reserve space for the
  103. * mft bitmap attribute.
  104. *
  105. * This is not the prettiest function but the complexity stems from the need of
  106. * implementing the mft vs data zoned approach and from the fact that we have
  107. * access to the lcn bitmap in portions of up to 8192 bytes at a time, so we
  108. * need to cope with crossing over boundaries of two buffers. Further, the
  109. * fact that the allocator allows for caller supplied hints as to the location
  110. * of where allocation should begin and the fact that the allocator keeps track
  111. * of where in the data zones the next natural allocation should occur,
  112. * contribute to the complexity of the function. But it should all be
  113. * worthwhile, because this allocator should: 1) be a full implementation of
  114. * the MFT zone approach used by Windows NT, 2) cause reduction in
  115. * fragmentation, and 3) be speedy in allocations (the code is not optimized
  116. * for speed, but the algorithm is, so further speed improvements are probably
  117. * possible).
  118. *
  119. * FIXME: We should be monitoring cluster allocation and increment the MFT zone
  120. * size dynamically but this is something for the future. We will just cause
  121. * heavier fragmentation by not doing it and I am not even sure Windows would
  122. * grow the MFT zone dynamically, so it might even be correct not to do this.
  123. * The overhead in doing dynamic MFT zone expansion would be very large and
  124. * unlikely worth the effort. (AIA)
  125. *
  126. * TODO: I have added in double the required zone position pointer wrap around
  127. * logic which can be optimized to having only one of the two logic sets.
  128. * However, having the double logic will work fine, but if we have only one of
  129. * the sets and we get it wrong somewhere, then we get into trouble, so
  130. * removing the duplicate logic requires _very_ careful consideration of _all_
  131. * possible code paths. So at least for now, I am leaving the double logic -
  132. * better safe than sorry... (AIA)
  133. *
  134. * Locking: - The volume lcn bitmap must be unlocked on entry and is unlocked
  135. * on return.
  136. * - This function takes the volume lcn bitmap lock for writing and
  137. * modifies the bitmap contents.
  138. */
  139. runlist_element *ntfs_cluster_alloc(ntfs_volume *vol, const VCN start_vcn,
  140. const s64 count, const LCN start_lcn,
  141. const NTFS_CLUSTER_ALLOCATION_ZONES zone,
  142. const bool is_extension)
  143. {
  144. LCN zone_start, zone_end, bmp_pos, bmp_initial_pos, last_read_pos, lcn;
  145. LCN prev_lcn = 0, prev_run_len = 0, mft_zone_size;
  146. s64 clusters;
  147. loff_t i_size;
  148. struct inode *lcnbmp_vi;
  149. runlist_element *rl = NULL;
  150. struct address_space *mapping;
  151. struct page *page = NULL;
  152. u8 *buf, *byte;
  153. int err = 0, rlpos, rlsize, buf_size;
  154. u8 pass, done_zones, search_zone, need_writeback = 0, bit;
  155. ntfs_debug("Entering for start_vcn 0x%llx, count 0x%llx, start_lcn "
  156. "0x%llx, zone %s_ZONE.", (unsigned long long)start_vcn,
  157. (unsigned long long)count,
  158. (unsigned long long)start_lcn,
  159. zone == MFT_ZONE ? "MFT" : "DATA");
  160. BUG_ON(!vol);
  161. lcnbmp_vi = vol->lcnbmp_ino;
  162. BUG_ON(!lcnbmp_vi);
  163. BUG_ON(start_vcn < 0);
  164. BUG_ON(count < 0);
  165. BUG_ON(start_lcn < -1);
  166. BUG_ON(zone < FIRST_ZONE);
  167. BUG_ON(zone > LAST_ZONE);
  168. /* Return NULL if @count is zero. */
  169. if (!count)
  170. return NULL;
  171. /* Take the lcnbmp lock for writing. */
  172. down_write(&vol->lcnbmp_lock);
  173. /*
  174. * If no specific @start_lcn was requested, use the current data zone
  175. * position, otherwise use the requested @start_lcn but make sure it
  176. * lies outside the mft zone. Also set done_zones to 0 (no zones done)
  177. * and pass depending on whether we are starting inside a zone (1) or
  178. * at the beginning of a zone (2). If requesting from the MFT_ZONE,
  179. * we either start at the current position within the mft zone or at
  180. * the specified position. If the latter is out of bounds then we start
  181. * at the beginning of the MFT_ZONE.
  182. */
  183. done_zones = 0;
  184. pass = 1;
  185. /*
  186. * zone_start and zone_end are the current search range. search_zone
  187. * is 1 for mft zone, 2 for data zone 1 (end of mft zone till end of
  188. * volume) and 4 for data zone 2 (start of volume till start of mft
  189. * zone).
  190. */
  191. zone_start = start_lcn;
  192. if (zone_start < 0) {
  193. if (zone == DATA_ZONE)
  194. zone_start = vol->data1_zone_pos;
  195. else
  196. zone_start = vol->mft_zone_pos;
  197. if (!zone_start) {
  198. /*
  199. * Zone starts at beginning of volume which means a
  200. * single pass is sufficient.
  201. */
  202. pass = 2;
  203. }
  204. } else if (zone == DATA_ZONE && zone_start >= vol->mft_zone_start &&
  205. zone_start < vol->mft_zone_end) {
  206. zone_start = vol->mft_zone_end;
  207. /*
  208. * Starting at beginning of data1_zone which means a single
  209. * pass in this zone is sufficient.
  210. */
  211. pass = 2;
  212. } else if (zone == MFT_ZONE && (zone_start < vol->mft_zone_start ||
  213. zone_start >= vol->mft_zone_end)) {
  214. zone_start = vol->mft_lcn;
  215. if (!vol->mft_zone_end)
  216. zone_start = 0;
  217. /*
  218. * Starting at beginning of volume which means a single pass
  219. * is sufficient.
  220. */
  221. pass = 2;
  222. }
  223. if (zone == MFT_ZONE) {
  224. zone_end = vol->mft_zone_end;
  225. search_zone = 1;
  226. } else /* if (zone == DATA_ZONE) */ {
  227. /* Skip searching the mft zone. */
  228. done_zones |= 1;
  229. if (zone_start >= vol->mft_zone_end) {
  230. zone_end = vol->nr_clusters;
  231. search_zone = 2;
  232. } else {
  233. zone_end = vol->mft_zone_start;
  234. search_zone = 4;
  235. }
  236. }
  237. /*
  238. * bmp_pos is the current bit position inside the bitmap. We use
  239. * bmp_initial_pos to determine whether or not to do a zone switch.
  240. */
  241. bmp_pos = bmp_initial_pos = zone_start;
  242. /* Loop until all clusters are allocated, i.e. clusters == 0. */
  243. clusters = count;
  244. rlpos = rlsize = 0;
  245. mapping = lcnbmp_vi->i_mapping;
  246. i_size = i_size_read(lcnbmp_vi);
  247. while (1) {
  248. ntfs_debug("Start of outer while loop: done_zones 0x%x, "
  249. "search_zone %i, pass %i, zone_start 0x%llx, "
  250. "zone_end 0x%llx, bmp_initial_pos 0x%llx, "
  251. "bmp_pos 0x%llx, rlpos %i, rlsize %i.",
  252. done_zones, search_zone, pass,
  253. (unsigned long long)zone_start,
  254. (unsigned long long)zone_end,
  255. (unsigned long long)bmp_initial_pos,
  256. (unsigned long long)bmp_pos, rlpos, rlsize);
  257. /* Loop until we run out of free clusters. */
  258. last_read_pos = bmp_pos >> 3;
  259. ntfs_debug("last_read_pos 0x%llx.",
  260. (unsigned long long)last_read_pos);
  261. if (last_read_pos > i_size) {
  262. ntfs_debug("End of attribute reached. "
  263. "Skipping to zone_pass_done.");
  264. goto zone_pass_done;
  265. }
  266. if (likely(page)) {
  267. if (need_writeback) {
  268. ntfs_debug("Marking page dirty.");
  269. flush_dcache_page(page);
  270. set_page_dirty(page);
  271. need_writeback = 0;
  272. }
  273. ntfs_unmap_page(page);
  274. }
  275. page = ntfs_map_page(mapping, last_read_pos >>
  276. PAGE_CACHE_SHIFT);
  277. if (IS_ERR(page)) {
  278. err = PTR_ERR(page);
  279. ntfs_error(vol->sb, "Failed to map page.");
  280. goto out;
  281. }
  282. buf_size = last_read_pos & ~PAGE_CACHE_MASK;
  283. buf = page_address(page) + buf_size;
  284. buf_size = PAGE_CACHE_SIZE - buf_size;
  285. if (unlikely(last_read_pos + buf_size > i_size))
  286. buf_size = i_size - last_read_pos;
  287. buf_size <<= 3;
  288. lcn = bmp_pos & 7;
  289. bmp_pos &= ~(LCN)7;
  290. ntfs_debug("Before inner while loop: buf_size %i, lcn 0x%llx, "
  291. "bmp_pos 0x%llx, need_writeback %i.", buf_size,
  292. (unsigned long long)lcn,
  293. (unsigned long long)bmp_pos, need_writeback);
  294. while (lcn < buf_size && lcn + bmp_pos < zone_end) {
  295. byte = buf + (lcn >> 3);
  296. ntfs_debug("In inner while loop: buf_size %i, "
  297. "lcn 0x%llx, bmp_pos 0x%llx, "
  298. "need_writeback %i, byte ofs 0x%x, "
  299. "*byte 0x%x.", buf_size,
  300. (unsigned long long)lcn,
  301. (unsigned long long)bmp_pos,
  302. need_writeback,
  303. (unsigned int)(lcn >> 3),
  304. (unsigned int)*byte);
  305. /* Skip full bytes. */
  306. if (*byte == 0xff) {
  307. lcn = (lcn + 8) & ~(LCN)7;
  308. ntfs_debug("Continuing while loop 1.");
  309. continue;
  310. }
  311. bit = 1 << (lcn & 7);
  312. ntfs_debug("bit 0x%x.", bit);
  313. /* If the bit is already set, go onto the next one. */
  314. if (*byte & bit) {
  315. lcn++;
  316. ntfs_debug("Continuing while loop 2.");
  317. continue;
  318. }
  319. /*
  320. * Allocate more memory if needed, including space for
  321. * the terminator element.
  322. * ntfs_malloc_nofs() operates on whole pages only.
  323. */
  324. if ((rlpos + 2) * sizeof(*rl) > rlsize) {
  325. runlist_element *rl2;
  326. ntfs_debug("Reallocating memory.");
  327. if (!rl)
  328. ntfs_debug("First free bit is at LCN "
  329. "0x%llx.",
  330. (unsigned long long)
  331. (lcn + bmp_pos));
  332. rl2 = ntfs_malloc_nofs(rlsize + (int)PAGE_SIZE);
  333. if (unlikely(!rl2)) {
  334. err = -ENOMEM;
  335. ntfs_error(vol->sb, "Failed to "
  336. "allocate memory.");
  337. goto out;
  338. }
  339. memcpy(rl2, rl, rlsize);
  340. ntfs_free(rl);
  341. rl = rl2;
  342. rlsize += PAGE_SIZE;
  343. ntfs_debug("Reallocated memory, rlsize 0x%x.",
  344. rlsize);
  345. }
  346. /* Allocate the bitmap bit. */
  347. *byte |= bit;
  348. /* We need to write this bitmap page to disk. */
  349. need_writeback = 1;
  350. ntfs_debug("*byte 0x%x, need_writeback is set.",
  351. (unsigned int)*byte);
  352. /*
  353. * Coalesce with previous run if adjacent LCNs.
  354. * Otherwise, append a new run.
  355. */
  356. ntfs_debug("Adding run (lcn 0x%llx, len 0x%llx), "
  357. "prev_lcn 0x%llx, lcn 0x%llx, "
  358. "bmp_pos 0x%llx, prev_run_len 0x%llx, "
  359. "rlpos %i.",
  360. (unsigned long long)(lcn + bmp_pos),
  361. 1ULL, (unsigned long long)prev_lcn,
  362. (unsigned long long)lcn,
  363. (unsigned long long)bmp_pos,
  364. (unsigned long long)prev_run_len,
  365. rlpos);
  366. if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos) {
  367. ntfs_debug("Coalescing to run (lcn 0x%llx, "
  368. "len 0x%llx).",
  369. (unsigned long long)
  370. rl[rlpos - 1].lcn,
  371. (unsigned long long)
  372. rl[rlpos - 1].length);
  373. rl[rlpos - 1].length = ++prev_run_len;
  374. ntfs_debug("Run now (lcn 0x%llx, len 0x%llx), "
  375. "prev_run_len 0x%llx.",
  376. (unsigned long long)
  377. rl[rlpos - 1].lcn,
  378. (unsigned long long)
  379. rl[rlpos - 1].length,
  380. (unsigned long long)
  381. prev_run_len);
  382. } else {
  383. if (likely(rlpos)) {
  384. ntfs_debug("Adding new run, (previous "
  385. "run lcn 0x%llx, "
  386. "len 0x%llx).",
  387. (unsigned long long)
  388. rl[rlpos - 1].lcn,
  389. (unsigned long long)
  390. rl[rlpos - 1].length);
  391. rl[rlpos].vcn = rl[rlpos - 1].vcn +
  392. prev_run_len;
  393. } else {
  394. ntfs_debug("Adding new run, is first "
  395. "run.");
  396. rl[rlpos].vcn = start_vcn;
  397. }
  398. rl[rlpos].lcn = prev_lcn = lcn + bmp_pos;
  399. rl[rlpos].length = prev_run_len = 1;
  400. rlpos++;
  401. }
  402. /* Done? */
  403. if (!--clusters) {
  404. LCN tc;
  405. /*
  406. * Update the current zone position. Positions
  407. * of already scanned zones have been updated
  408. * during the respective zone switches.
  409. */
  410. tc = lcn + bmp_pos + 1;
  411. ntfs_debug("Done. Updating current zone "
  412. "position, tc 0x%llx, "
  413. "search_zone %i.",
  414. (unsigned long long)tc,
  415. search_zone);
  416. switch (search_zone) {
  417. case 1:
  418. ntfs_debug("Before checks, "
  419. "vol->mft_zone_pos "
  420. "0x%llx.",
  421. (unsigned long long)
  422. vol->mft_zone_pos);
  423. if (tc >= vol->mft_zone_end) {
  424. vol->mft_zone_pos =
  425. vol->mft_lcn;
  426. if (!vol->mft_zone_end)
  427. vol->mft_zone_pos = 0;
  428. } else if ((bmp_initial_pos >=
  429. vol->mft_zone_pos ||
  430. tc > vol->mft_zone_pos)
  431. && tc >= vol->mft_lcn)
  432. vol->mft_zone_pos = tc;
  433. ntfs_debug("After checks, "
  434. "vol->mft_zone_pos "
  435. "0x%llx.",
  436. (unsigned long long)
  437. vol->mft_zone_pos);
  438. break;
  439. case 2:
  440. ntfs_debug("Before checks, "
  441. "vol->data1_zone_pos "
  442. "0x%llx.",
  443. (unsigned long long)
  444. vol->data1_zone_pos);
  445. if (tc >= vol->nr_clusters)
  446. vol->data1_zone_pos =
  447. vol->mft_zone_end;
  448. else if ((bmp_initial_pos >=
  449. vol->data1_zone_pos ||
  450. tc > vol->data1_zone_pos)
  451. && tc >= vol->mft_zone_end)
  452. vol->data1_zone_pos = tc;
  453. ntfs_debug("After checks, "
  454. "vol->data1_zone_pos "
  455. "0x%llx.",
  456. (unsigned long long)
  457. vol->data1_zone_pos);
  458. break;
  459. case 4:
  460. ntfs_debug("Before checks, "
  461. "vol->data2_zone_pos "
  462. "0x%llx.",
  463. (unsigned long long)
  464. vol->data2_zone_pos);
  465. if (tc >= vol->mft_zone_start)
  466. vol->data2_zone_pos = 0;
  467. else if (bmp_initial_pos >=
  468. vol->data2_zone_pos ||
  469. tc > vol->data2_zone_pos)
  470. vol->data2_zone_pos = tc;
  471. ntfs_debug("After checks, "
  472. "vol->data2_zone_pos "
  473. "0x%llx.",
  474. (unsigned long long)
  475. vol->data2_zone_pos);
  476. break;
  477. default:
  478. BUG();
  479. }
  480. ntfs_debug("Finished. Going to out.");
  481. goto out;
  482. }
  483. lcn++;
  484. }
  485. bmp_pos += buf_size;
  486. ntfs_debug("After inner while loop: buf_size 0x%x, lcn "
  487. "0x%llx, bmp_pos 0x%llx, need_writeback %i.",
  488. buf_size, (unsigned long long)lcn,
  489. (unsigned long long)bmp_pos, need_writeback);
  490. if (bmp_pos < zone_end) {
  491. ntfs_debug("Continuing outer while loop, "
  492. "bmp_pos 0x%llx, zone_end 0x%llx.",
  493. (unsigned long long)bmp_pos,
  494. (unsigned long long)zone_end);
  495. continue;
  496. }
  497. zone_pass_done: /* Finished with the current zone pass. */
  498. ntfs_debug("At zone_pass_done, pass %i.", pass);
  499. if (pass == 1) {
  500. /*
  501. * Now do pass 2, scanning the first part of the zone
  502. * we omitted in pass 1.
  503. */
  504. pass = 2;
  505. zone_end = zone_start;
  506. switch (search_zone) {
  507. case 1: /* mft_zone */
  508. zone_start = vol->mft_zone_start;
  509. break;
  510. case 2: /* data1_zone */
  511. zone_start = vol->mft_zone_end;
  512. break;
  513. case 4: /* data2_zone */
  514. zone_start = 0;
  515. break;
  516. default:
  517. BUG();
  518. }
  519. /* Sanity check. */
  520. if (zone_end < zone_start)
  521. zone_end = zone_start;
  522. bmp_pos = zone_start;
  523. ntfs_debug("Continuing outer while loop, pass 2, "
  524. "zone_start 0x%llx, zone_end 0x%llx, "
  525. "bmp_pos 0x%llx.",
  526. (unsigned long long)zone_start,
  527. (unsigned long long)zone_end,
  528. (unsigned long long)bmp_pos);
  529. continue;
  530. } /* pass == 2 */
  531. done_zones_check:
  532. ntfs_debug("At done_zones_check, search_zone %i, done_zones "
  533. "before 0x%x, done_zones after 0x%x.",
  534. search_zone, done_zones,
  535. done_zones | search_zone);
  536. done_zones |= search_zone;
  537. if (done_zones < 7) {
  538. ntfs_debug("Switching zone.");
  539. /* Now switch to the next zone we haven't done yet. */
  540. pass = 1;
  541. switch (search_zone) {
  542. case 1:
  543. ntfs_debug("Switching from mft zone to data1 "
  544. "zone.");
  545. /* Update mft zone position. */
  546. if (rlpos) {
  547. LCN tc;
  548. ntfs_debug("Before checks, "
  549. "vol->mft_zone_pos "
  550. "0x%llx.",
  551. (unsigned long long)
  552. vol->mft_zone_pos);
  553. tc = rl[rlpos - 1].lcn +
  554. rl[rlpos - 1].length;
  555. if (tc >= vol->mft_zone_end) {
  556. vol->mft_zone_pos =
  557. vol->mft_lcn;
  558. if (!vol->mft_zone_end)
  559. vol->mft_zone_pos = 0;
  560. } else if ((bmp_initial_pos >=
  561. vol->mft_zone_pos ||
  562. tc > vol->mft_zone_pos)
  563. && tc >= vol->mft_lcn)
  564. vol->mft_zone_pos = tc;
  565. ntfs_debug("After checks, "
  566. "vol->mft_zone_pos "
  567. "0x%llx.",
  568. (unsigned long long)
  569. vol->mft_zone_pos);
  570. }
  571. /* Switch from mft zone to data1 zone. */
  572. switch_to_data1_zone: search_zone = 2;
  573. zone_start = bmp_initial_pos =
  574. vol->data1_zone_pos;
  575. zone_end = vol->nr_clusters;
  576. if (zone_start == vol->mft_zone_end)
  577. pass = 2;
  578. if (zone_start >= zone_end) {
  579. vol->data1_zone_pos = zone_start =
  580. vol->mft_zone_end;
  581. pass = 2;
  582. }
  583. break;
  584. case 2:
  585. ntfs_debug("Switching from data1 zone to "
  586. "data2 zone.");
  587. /* Update data1 zone position. */
  588. if (rlpos) {
  589. LCN tc;
  590. ntfs_debug("Before checks, "
  591. "vol->data1_zone_pos "
  592. "0x%llx.",
  593. (unsigned long long)
  594. vol->data1_zone_pos);
  595. tc = rl[rlpos - 1].lcn +
  596. rl[rlpos - 1].length;
  597. if (tc >= vol->nr_clusters)
  598. vol->data1_zone_pos =
  599. vol->mft_zone_end;
  600. else if ((bmp_initial_pos >=
  601. vol->data1_zone_pos ||
  602. tc > vol->data1_zone_pos)
  603. && tc >= vol->mft_zone_end)
  604. vol->data1_zone_pos = tc;
  605. ntfs_debug("After checks, "
  606. "vol->data1_zone_pos "
  607. "0x%llx.",
  608. (unsigned long long)
  609. vol->data1_zone_pos);
  610. }
  611. /* Switch from data1 zone to data2 zone. */
  612. search_zone = 4;
  613. zone_start = bmp_initial_pos =
  614. vol->data2_zone_pos;
  615. zone_end = vol->mft_zone_start;
  616. if (!zone_start)
  617. pass = 2;
  618. if (zone_start >= zone_end) {
  619. vol->data2_zone_pos = zone_start =
  620. bmp_initial_pos = 0;
  621. pass = 2;
  622. }
  623. break;
  624. case 4:
  625. ntfs_debug("Switching from data2 zone to "
  626. "data1 zone.");
  627. /* Update data2 zone position. */
  628. if (rlpos) {
  629. LCN tc;
  630. ntfs_debug("Before checks, "
  631. "vol->data2_zone_pos "
  632. "0x%llx.",
  633. (unsigned long long)
  634. vol->data2_zone_pos);
  635. tc = rl[rlpos - 1].lcn +
  636. rl[rlpos - 1].length;
  637. if (tc >= vol->mft_zone_start)
  638. vol->data2_zone_pos = 0;
  639. else if (bmp_initial_pos >=
  640. vol->data2_zone_pos ||
  641. tc > vol->data2_zone_pos)
  642. vol->data2_zone_pos = tc;
  643. ntfs_debug("After checks, "
  644. "vol->data2_zone_pos "
  645. "0x%llx.",
  646. (unsigned long long)
  647. vol->data2_zone_pos);
  648. }
  649. /* Switch from data2 zone to data1 zone. */
  650. goto switch_to_data1_zone;
  651. default:
  652. BUG();
  653. }
  654. ntfs_debug("After zone switch, search_zone %i, "
  655. "pass %i, bmp_initial_pos 0x%llx, "
  656. "zone_start 0x%llx, zone_end 0x%llx.",
  657. search_zone, pass,
  658. (unsigned long long)bmp_initial_pos,
  659. (unsigned long long)zone_start,
  660. (unsigned long long)zone_end);
  661. bmp_pos = zone_start;
  662. if (zone_start == zone_end) {
  663. ntfs_debug("Empty zone, going to "
  664. "done_zones_check.");
  665. /* Empty zone. Don't bother searching it. */
  666. goto done_zones_check;
  667. }
  668. ntfs_debug("Continuing outer while loop.");
  669. continue;
  670. } /* done_zones == 7 */
  671. ntfs_debug("All zones are finished.");
  672. /*
  673. * All zones are finished! If DATA_ZONE, shrink mft zone. If
  674. * MFT_ZONE, we have really run out of space.
  675. */
  676. mft_zone_size = vol->mft_zone_end - vol->mft_zone_start;
  677. ntfs_debug("vol->mft_zone_start 0x%llx, vol->mft_zone_end "
  678. "0x%llx, mft_zone_size 0x%llx.",
  679. (unsigned long long)vol->mft_zone_start,
  680. (unsigned long long)vol->mft_zone_end,
  681. (unsigned long long)mft_zone_size);
  682. if (zone == MFT_ZONE || mft_zone_size <= 0) {
  683. ntfs_debug("No free clusters left, going to out.");
  684. /* Really no more space left on device. */
  685. err = -ENOSPC;
  686. goto out;
  687. } /* zone == DATA_ZONE && mft_zone_size > 0 */
  688. ntfs_debug("Shrinking mft zone.");
  689. zone_end = vol->mft_zone_end;
  690. mft_zone_size >>= 1;
  691. if (mft_zone_size > 0)
  692. vol->mft_zone_end = vol->mft_zone_start + mft_zone_size;
  693. else /* mft zone and data2 zone no longer exist. */
  694. vol->data2_zone_pos = vol->mft_zone_start =
  695. vol->mft_zone_end = 0;
  696. if (vol->mft_zone_pos >= vol->mft_zone_end) {
  697. vol->mft_zone_pos = vol->mft_lcn;
  698. if (!vol->mft_zone_end)
  699. vol->mft_zone_pos = 0;
  700. }
  701. bmp_pos = zone_start = bmp_initial_pos =
  702. vol->data1_zone_pos = vol->mft_zone_end;
  703. search_zone = 2;
  704. pass = 2;
  705. done_zones &= ~2;
  706. ntfs_debug("After shrinking mft zone, mft_zone_size 0x%llx, "
  707. "vol->mft_zone_start 0x%llx, "
  708. "vol->mft_zone_end 0x%llx, "
  709. "vol->mft_zone_pos 0x%llx, search_zone 2, "
  710. "pass 2, dones_zones 0x%x, zone_start 0x%llx, "
  711. "zone_end 0x%llx, vol->data1_zone_pos 0x%llx, "
  712. "continuing outer while loop.",
  713. (unsigned long long)mft_zone_size,
  714. (unsigned long long)vol->mft_zone_start,
  715. (unsigned long long)vol->mft_zone_end,
  716. (unsigned long long)vol->mft_zone_pos,
  717. done_zones, (unsigned long long)zone_start,
  718. (unsigned long long)zone_end,
  719. (unsigned long long)vol->data1_zone_pos);
  720. }
  721. ntfs_debug("After outer while loop.");
  722. out:
  723. ntfs_debug("At out.");
  724. /* Add runlist terminator element. */
  725. if (likely(rl)) {
  726. rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length;
  727. rl[rlpos].lcn = is_extension ? LCN_ENOENT : LCN_RL_NOT_MAPPED;
  728. rl[rlpos].length = 0;
  729. }
  730. if (likely(page && !IS_ERR(page))) {
  731. if (need_writeback) {
  732. ntfs_debug("Marking page dirty.");
  733. flush_dcache_page(page);
  734. set_page_dirty(page);
  735. need_writeback = 0;
  736. }
  737. ntfs_unmap_page(page);
  738. }
  739. if (likely(!err)) {
  740. up_write(&vol->lcnbmp_lock);
  741. ntfs_debug("Done.");
  742. return rl;
  743. }
  744. ntfs_error(vol->sb, "Failed to allocate clusters, aborting "
  745. "(error %i).", err);
  746. if (rl) {
  747. int err2;
  748. if (err == -ENOSPC)
  749. ntfs_debug("Not enough space to complete allocation, "
  750. "err -ENOSPC, first free lcn 0x%llx, "
  751. "could allocate up to 0x%llx "
  752. "clusters.",
  753. (unsigned long long)rl[0].lcn,
  754. (unsigned long long)(count - clusters));
  755. /* Deallocate all allocated clusters. */
  756. ntfs_debug("Attempting rollback...");
  757. err2 = ntfs_cluster_free_from_rl_nolock(vol, rl);
  758. if (err2) {
  759. ntfs_error(vol->sb, "Failed to rollback (error %i). "
  760. "Leaving inconsistent metadata! "
  761. "Unmount and run chkdsk.", err2);
  762. NVolSetErrors(vol);
  763. }
  764. /* Free the runlist. */
  765. ntfs_free(rl);
  766. } else if (err == -ENOSPC)
  767. ntfs_debug("No space left at all, err = -ENOSPC, first free "
  768. "lcn = 0x%llx.",
  769. (long long)vol->data1_zone_pos);
  770. up_write(&vol->lcnbmp_lock);
  771. return ERR_PTR(err);
  772. }
  773. /**
  774. * __ntfs_cluster_free - free clusters on an ntfs volume
  775. * @ni: ntfs inode whose runlist describes the clusters to free
  776. * @start_vcn: vcn in the runlist of @ni at which to start freeing clusters
  777. * @count: number of clusters to free or -1 for all clusters
  778. * @ctx: active attribute search context if present or NULL if not
  779. * @is_rollback: true if this is a rollback operation
  780. *
  781. * Free @count clusters starting at the cluster @start_vcn in the runlist
  782. * described by the vfs inode @ni.
  783. *
  784. * If @count is -1, all clusters from @start_vcn to the end of the runlist are
  785. * deallocated. Thus, to completely free all clusters in a runlist, use
  786. * @start_vcn = 0 and @count = -1.
  787. *
  788. * If @ctx is specified, it is an active search context of @ni and its base mft
  789. * record. This is needed when __ntfs_cluster_free() encounters unmapped
  790. * runlist fragments and allows their mapping. If you do not have the mft
  791. * record mapped, you can specify @ctx as NULL and __ntfs_cluster_free() will
  792. * perform the necessary mapping and unmapping.
  793. *
  794. * Note, __ntfs_cluster_free() saves the state of @ctx on entry and restores it
  795. * before returning. Thus, @ctx will be left pointing to the same attribute on
  796. * return as on entry. However, the actual pointers in @ctx may point to
  797. * different memory locations on return, so you must remember to reset any
  798. * cached pointers from the @ctx, i.e. after the call to __ntfs_cluster_free(),
  799. * you will probably want to do:
  800. * m = ctx->mrec;
  801. * a = ctx->attr;
  802. * Assuming you cache ctx->attr in a variable @a of type ATTR_RECORD * and that
  803. * you cache ctx->mrec in a variable @m of type MFT_RECORD *.
  804. *
  805. * @is_rollback should always be 'false', it is for internal use to rollback
  806. * errors. You probably want to use ntfs_cluster_free() instead.
  807. *
  808. * Note, __ntfs_cluster_free() does not modify the runlist, so you have to
  809. * remove from the runlist or mark sparse the freed runs later.
  810. *
  811. * Return the number of deallocated clusters (not counting sparse ones) on
  812. * success and -errno on error.
  813. *
  814. * WARNING: If @ctx is supplied, regardless of whether success or failure is
  815. * returned, you need to check IS_ERR(@ctx->mrec) and if 'true' the @ctx
  816. * is no longer valid, i.e. you need to either call
  817. * ntfs_attr_reinit_search_ctx() or ntfs_attr_put_search_ctx() on it.
  818. * In that case PTR_ERR(@ctx->mrec) will give you the error code for
  819. * why the mapping of the old inode failed.
  820. *
  821. * Locking: - The runlist described by @ni must be locked for writing on entry
  822. * and is locked on return. Note the runlist may be modified when
  823. * needed runlist fragments need to be mapped.
  824. * - The volume lcn bitmap must be unlocked on entry and is unlocked
  825. * on return.
  826. * - This function takes the volume lcn bitmap lock for writing and
  827. * modifies the bitmap contents.
  828. * - If @ctx is NULL, the base mft record of @ni must not be mapped on
  829. * entry and it will be left unmapped on return.
  830. * - If @ctx is not NULL, the base mft record must be mapped on entry
  831. * and it will be left mapped on return.
  832. */
  833. s64 __ntfs_cluster_free(ntfs_inode *ni, const VCN start_vcn, s64 count,
  834. ntfs_attr_search_ctx *ctx, const bool is_rollback)
  835. {
  836. s64 delta, to_free, total_freed, real_freed;
  837. ntfs_volume *vol;
  838. struct inode *lcnbmp_vi;
  839. runlist_element *rl;
  840. int err;
  841. BUG_ON(!ni);
  842. ntfs_debug("Entering for i_ino 0x%lx, start_vcn 0x%llx, count "
  843. "0x%llx.%s", ni->mft_no, (unsigned long long)start_vcn,
  844. (unsigned long long)count,
  845. is_rollback ? " (rollback)" : "");
  846. vol = ni->vol;
  847. lcnbmp_vi = vol->lcnbmp_ino;
  848. BUG_ON(!lcnbmp_vi);
  849. BUG_ON(start_vcn < 0);
  850. BUG_ON(count < -1);
  851. /*
  852. * Lock the lcn bitmap for writing but only if not rolling back. We
  853. * must hold the lock all the way including through rollback otherwise
  854. * rollback is not possible because once we have cleared a bit and
  855. * dropped the lock, anyone could have set the bit again, thus
  856. * allocating the cluster for another use.
  857. */
  858. if (likely(!is_rollback))
  859. down_write(&vol->lcnbmp_lock);
  860. total_freed = real_freed = 0;
  861. rl = ntfs_attr_find_vcn_nolock(ni, start_vcn, ctx);
  862. if (IS_ERR(rl)) {
  863. if (!is_rollback)
  864. ntfs_error(vol->sb, "Failed to find first runlist "
  865. "element (error %li), aborting.",
  866. PTR_ERR(rl));
  867. err = PTR_ERR(rl);
  868. goto err_out;
  869. }
  870. if (unlikely(rl->lcn < LCN_HOLE)) {
  871. if (!is_rollback)
  872. ntfs_error(vol->sb, "First runlist element has "
  873. "invalid lcn, aborting.");
  874. err = -EIO;
  875. goto err_out;
  876. }
  877. /* Find the starting cluster inside the run that needs freeing. */
  878. delta = start_vcn - rl->vcn;
  879. /* The number of clusters in this run that need freeing. */
  880. to_free = rl->length - delta;
  881. if (count >= 0 && to_free > count)
  882. to_free = count;
  883. if (likely(rl->lcn >= 0)) {
  884. /* Do the actual freeing of the clusters in this run. */
  885. err = ntfs_bitmap_set_bits_in_run(lcnbmp_vi, rl->lcn + delta,
  886. to_free, likely(!is_rollback) ? 0 : 1);
  887. if (unlikely(err)) {
  888. if (!is_rollback)
  889. ntfs_error(vol->sb, "Failed to clear first run "
  890. "(error %i), aborting.", err);
  891. goto err_out;
  892. }
  893. /* We have freed @to_free real clusters. */
  894. real_freed = to_free;
  895. };
  896. /* Go to the next run and adjust the number of clusters left to free. */
  897. ++rl;
  898. if (count >= 0)
  899. count -= to_free;
  900. /* Keep track of the total "freed" clusters, including sparse ones. */
  901. total_freed = to_free;
  902. /*
  903. * Loop over the remaining runs, using @count as a capping value, and
  904. * free them.
  905. */
  906. for (; rl->length && count != 0; ++rl) {
  907. if (unlikely(rl->lcn < LCN_HOLE)) {
  908. VCN vcn;
  909. /* Attempt to map runlist. */
  910. vcn = rl->vcn;
  911. rl = ntfs_attr_find_vcn_nolock(ni, vcn, ctx);
  912. if (IS_ERR(rl)) {
  913. err = PTR_ERR(rl);
  914. if (!is_rollback)
  915. ntfs_error(vol->sb, "Failed to map "
  916. "runlist fragment or "
  917. "failed to find "
  918. "subsequent runlist "
  919. "element.");
  920. goto err_out;
  921. }
  922. if (unlikely(rl->lcn < LCN_HOLE)) {
  923. if (!is_rollback)
  924. ntfs_error(vol->sb, "Runlist element "
  925. "has invalid lcn "
  926. "(0x%llx).",
  927. (unsigned long long)
  928. rl->lcn);
  929. err = -EIO;
  930. goto err_out;
  931. }
  932. }
  933. /* The number of clusters in this run that need freeing. */
  934. to_free = rl->length;
  935. if (count >= 0 && to_free > count)
  936. to_free = count;
  937. if (likely(rl->lcn >= 0)) {
  938. /* Do the actual freeing of the clusters in the run. */
  939. err = ntfs_bitmap_set_bits_in_run(lcnbmp_vi, rl->lcn,
  940. to_free, likely(!is_rollback) ? 0 : 1);
  941. if (unlikely(err)) {
  942. if (!is_rollback)
  943. ntfs_error(vol->sb, "Failed to clear "
  944. "subsequent run.");
  945. goto err_out;
  946. }
  947. /* We have freed @to_free real clusters. */
  948. real_freed += to_free;
  949. }
  950. /* Adjust the number of clusters left to free. */
  951. if (count >= 0)
  952. count -= to_free;
  953. /* Update the total done clusters. */
  954. total_freed += to_free;
  955. }
  956. if (likely(!is_rollback))
  957. up_write(&vol->lcnbmp_lock);
  958. BUG_ON(count > 0);
  959. /* We are done. Return the number of actually freed clusters. */
  960. ntfs_debug("Done.");
  961. return real_freed;
  962. err_out:
  963. if (is_rollback)
  964. return err;
  965. /* If no real clusters were freed, no need to rollback. */
  966. if (!real_freed) {
  967. up_write(&vol->lcnbmp_lock);
  968. return err;
  969. }
  970. /*
  971. * Attempt to rollback and if that succeeds just return the error code.
  972. * If rollback fails, set the volume errors flag, emit an error
  973. * message, and return the error code.
  974. */
  975. delta = __ntfs_cluster_free(ni, start_vcn, total_freed, ctx, true);
  976. if (delta < 0) {
  977. ntfs_error(vol->sb, "Failed to rollback (error %i). Leaving "
  978. "inconsistent metadata! Unmount and run "
  979. "chkdsk.", (int)delta);
  980. NVolSetErrors(vol);
  981. }
  982. up_write(&vol->lcnbmp_lock);
  983. ntfs_error(vol->sb, "Aborting (error %i).", err);
  984. return err;
  985. }
  986. #endif /* NTFS_RW */