开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Linux/Unix编程 > 查看源码
super.c
资源名称：linux-2.4.20.tar.gz　[点击查看]
上传用户：jlfgdled
上传日期：2013-04-10
资源大小：33168k
文件大小：45k
源码类别：

Linux/Unix编程

开发平台：

Unix_Linux

super.c：源码内容
  1. /*
  2.  * super.c
  3.  *
  4.  * Copyright (C) 1995-1997, 1999 Martin von L鰓is
  5.  * Copyright (C) 1996-1997 R間is Duchesne
  6.  * Copyright (C) 1999 Steve Dodd
  7.  * Copyright (C) 2000-2001 Anton Altparmakov (AIA)
  8.  */
  10. #include <linux/ntfs_fs.h>
  11. #include <linux/errno.h>
  12. #include <linux/bitops.h>
  13. #include <linux/module.h>
  14. #include "ntfstypes.h"
  15. #include "struct.h"
  16. #include "super.h"
  17. #include "macros.h"
  18. #include "inode.h"
  19. #include "support.h"
  20. #include "util.h"
  21. #include <linux/smp_lock.h>
  23. /* All important structures in NTFS use 2 consistency checks:
  24.  * . a magic structure identifier (FILE, INDX, RSTR, RCRD...)
  25.  * . a fixup technique : the last word of each sector (called a fixup) of a
  26.  *   structure's record should end with the word at offset <n> of the first
  27.  *   sector, and if it is the case, must be replaced with the words following
  28.  *   <n>. The value of <n> and the number of fixups is taken from the fields
  29.  *   at the offsets 4 and 6. Note that the sector size is defined as
  30.  *   NTFS_SECTOR_SIZE and not as the hardware sector size (this is concordant
  31.  *   with what the Windows NTFS driver does).
  32.  *
  33.  * This function performs these 2 checks, and _fails_ if:
  34.  * . the input size is invalid
  35.  * . the fixup header is invalid
  36.  * . the size does not match the number of sectors
  37.  * . the magic identifier is wrong
  38.  * . a fixup is invalid
  39.  */
  40. int ntfs_fixup_record(char *record, char *magic, int size)
  41. {
  42. int start, count, offset;
  43. ntfs_u16 fixup;
  45. if (!IS_MAGIC(record, magic))
  46. return 0;
  47. start = NTFS_GETU16(record + 4);
  48. count = NTFS_GETU16(record + 6) - 1;
  49. if (size & (NTFS_SECTOR_SIZE - 1) || start & 1 ||
  50. start + count * 2 > size || size >> 9 != count) {
  51. if (size <= 0)
  52. printk(KERN_ERR "NTFS: BUG: ntfs_fixup_record() got "
  53. "zero size! Please report this to "
  54. "linux-ntfs-dev@lists.sf.netn");
  55. return 0;
  56. }
  57. fixup = NTFS_GETU16(record + start);
  58. start += 2;
  59. offset = NTFS_SECTOR_SIZE - 2;
  60. while (count--) {
  61. if (NTFS_GETU16(record + offset) != fixup)
  62. return 0;
  63. NTFS_PUTU16(record + offset, NTFS_GETU16(record + start));
  64. start += 2;
  65. offset += NTFS_SECTOR_SIZE;
  66. }
  67. return 1;
  68. }
  70. /*
  71.  * Get vital informations about the ntfs partition from the boot sector.
  72.  * Return 0 on success or -1 on error.
  73.  */
  74. int ntfs_init_volume(ntfs_volume *vol, char *boot)
  75. {
  76. int sectors_per_cluster_bits;
  77. __s64 ll;
  78. ntfs_cluster_t mft_zone_size, tc;
  80. /* System defined default values, in case we don't load $AttrDef. */
  81. vol->at_standard_information = 0x10;
  82. vol->at_attribute_list = 0x20;
  83. vol->at_file_name = 0x30;
  84. vol->at_volume_version = 0x40;
  85. vol->at_security_descriptor = 0x50;
  86. vol->at_volume_name = 0x60;
  87. vol->at_volume_information = 0x70;
  88. vol->at_data = 0x80;
  89. vol->at_index_root = 0x90;
  90. vol->at_index_allocation = 0xA0;
  91. vol->at_bitmap = 0xB0;
  92. vol->at_symlink = 0xC0;
  93. /* Sector size. */
  94. vol->sector_size = NTFS_GETU16(boot + 0xB);
  95. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->sector_size = 0x%xn",
  96. vol->sector_size);
  97. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: sectors_per_cluster = "
  98. "0x%xn", NTFS_GETU8(boot + 0xD));
  99. sectors_per_cluster_bits = ffs(NTFS_GETU8(boot + 0xD)) - 1;
  100. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: sectors_per_cluster_bits "
  101. "= 0x%xn", sectors_per_cluster_bits); 
  102. vol->mft_clusters_per_record = NTFS_GETS8(boot + 0x40);
  103. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_clusters_per_record"
  104. " = 0x%xn", vol->mft_clusters_per_record); 
  105. vol->index_clusters_per_record = NTFS_GETS8(boot + 0x44);
  106. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: "
  107. "vol->index_clusters_per_record = 0x%xn",
  108. vol->index_clusters_per_record); 
  109. vol->cluster_size = vol->sector_size << sectors_per_cluster_bits;
  110. vol->cluster_size_bits = ffs(vol->cluster_size) - 1;
  111. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->cluster_size = 0x%xn",
  112. vol->cluster_size); 
  113. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->cluster_size_bits = "
  114. "0x%xn", vol->cluster_size_bits); 
  115. if (vol->mft_clusters_per_record > 0)
  116. vol->mft_record_size = vol->cluster_size <<
  117. (ffs(vol->mft_clusters_per_record) - 1);
  118. else
  119. /*
  120.  * When mft_record_size < cluster_size, mft_clusters_per_record
  121.  * = -log2(mft_record_size) bytes. mft_record_size normaly is
  122.  * 1024 bytes, which is encoded as 0xF6 (-10 in decimal).
  123.  */
  124. vol->mft_record_size = 1 << -vol->mft_clusters_per_record;
  125. vol->mft_record_size_bits = ffs(vol->mft_record_size) - 1;
  126. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_record_size = 0x%x"
  127. "n", vol->mft_record_size); 
  128. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_record_size_bits = "
  129. "0x%xn", vol->mft_record_size_bits); 
  130. if (vol->index_clusters_per_record > 0)
  131. vol->index_record_size = vol->cluster_size <<
  132. (ffs(vol->index_clusters_per_record) - 1);
  133. else
  134. /*
  135.  * When index_record_size < cluster_size,
  136.  * index_clusters_per_record = -log2(index_record_size) bytes.
  137.  * index_record_size normaly equals 4096 bytes, which is
  138.  * encoded as 0xF4 (-12 in decimal).
  139.  */
  140. vol->index_record_size = 1 << -vol->index_clusters_per_record;
  141. vol->index_record_size_bits = ffs(vol->index_record_size) - 1;
  142. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->index_record_size = "
  143. "0x%xn", vol->index_record_size);
  144. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->index_record_size_bits "
  145. "= 0x%xn", vol->index_record_size_bits);
  146. /*
  147.  * Get the size of the volume in clusters (ofs 0x28 is nr_sectors) and
  148.  * check for 64-bit-ness. Windows currently only uses 32 bits to save
  149.  * the clusters so we do the same as it is much faster on 32-bit CPUs.
  150.  */
  151. ll = NTFS_GETS64(boot + 0x28) >> sectors_per_cluster_bits;
  152. if (ll >= (__s64)1 << 31) {
  153. ntfs_error("Cannot handle 64-bit clusters. Please inform "
  154. "linux-ntfs-dev@lists.sf.net that you got this "
  155. "error.n");
  156. return -1;
  157. }
  158. vol->nr_clusters = (ntfs_cluster_t)ll;
  159. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->nr_clusters = 0x%xn",
  160. vol->nr_clusters);
  161. vol->mft_lcn = (ntfs_cluster_t)NTFS_GETS64(boot + 0x30);
  162. vol->mft_mirr_lcn = (ntfs_cluster_t)NTFS_GETS64(boot + 0x38);
  163. /* Determine MFT zone size. */
  164. mft_zone_size = vol->nr_clusters;
  165. switch (vol->mft_zone_multiplier) {  /* % of volume size in clusters */
  166. case 4:
  167. mft_zone_size >>= 1; /* 50%   */
  168. break;
  169. case 3:
  170. mft_zone_size = mft_zone_size * 3 >> 3; /* 37.5% */
  171. break;
  172. case 2:
  173. mft_zone_size >>= 2; /* 25%   */
  174. break;
  175. /* case 1: */
  176. default:
  177. mft_zone_size >>= 3; /* 12.5% */
  178. break;
  179. }
  180. /* Setup mft zone. */
  181. vol->mft_zone_start = vol->mft_zone_pos = vol->mft_lcn;
  182. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_zone_pos = %xn",
  183. vol->mft_zone_pos);
  184. /*
  185.  * Calculate the mft_lcn for an unmodified NTFS volume (see mkntfs
  186.  * source) and if the actual mft_lcn is in the expected place or even
  187.  * further to the front of the volume, extend the mft_zone to cover the
  188.  * beginning of the volume as well. This is in order to protect the
  189.  * area reserved for the mft bitmap as well within the mft_zone itself.
  190.  * On non-standard volumes we don't protect it as well as the overhead
  191.  * would be higher than the speed increase we would get by doing it.
  192.  */
  193. tc = (8192 + 2 * vol->cluster_size - 1) / vol->cluster_size;
  194. if (tc * vol->cluster_size < 16 * 1024)
  195. tc = (16 * 1024 + vol->cluster_size - 1) / vol->cluster_size;
  196. if (vol->mft_zone_start <= tc)
  197. vol->mft_zone_start = (ntfs_cluster_t)0;
  198. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_zone_start = %xn",
  199. vol->mft_zone_start);
  200. /*
  201.  * Need to cap the mft zone on non-standard volumes so that it does
  202.  * not point outside the boundaries of the volume, we do this by
  203.  * halving the zone size until we are inside the volume.
  204.  */
  205. vol->mft_zone_end = vol->mft_lcn + mft_zone_size;
  206. while (vol->mft_zone_end >= vol->nr_clusters) {
  207. mft_zone_size >>= 1;
  208. vol->mft_zone_end = vol->mft_lcn + mft_zone_size;
  209. }
  210. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->mft_zone_end = %xn",
  211. vol->mft_zone_end);
  212. /*
  213.  * Set the current position within each data zone to the start of the
  214.  * respective zone.
  215.  */
  216. vol->data1_zone_pos = vol->mft_zone_end;
  217. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->data1_zone_pos = %xn",
  218. vol->data1_zone_pos);
  219. vol->data2_zone_pos = (ntfs_cluster_t)0;
  220. ntfs_debug(DEBUG_FILE3, "ntfs_init_volume: vol->data2_zone_pos = %xn",
  221. vol->data2_zone_pos);
  222. /* Set the mft data allocation position to mft record 24. */
  223. vol->mft_data_pos = 24UL;
  224. /* This will be initialized later. */
  225. vol->upcase = 0;
  226. vol->upcase_length = 0;
  227. vol->mft_ino = 0;
  228. return 0;
  229. }
  231. static void ntfs_init_upcase(ntfs_inode *upcase)
  232. {
  233. ntfs_io io;
  234. #define UPCASE_LENGTH  256
  235. upcase->vol->upcase = ntfs_malloc(UPCASE_LENGTH << 1);
  236. if (!upcase->vol->upcase)
  237. return;
  238. io.fn_put = ntfs_put;
  239. io.fn_get = 0;
  240. io.param = (char*)upcase->vol->upcase;
  241. io.size = UPCASE_LENGTH << 1;
  242. ntfs_read_attr(upcase, upcase->vol->at_data, 0, 0, &io);
  243. upcase->vol->upcase_length = io.size >> 1;
  244. }
  246. static int process_attrdef(ntfs_inode* attrdef, ntfs_u8* def)
  247. {
  248. int type = NTFS_GETU32(def+0x80);
  249. int check_type = 0;
  250. ntfs_volume *vol = attrdef->vol;
  251. ntfs_u16* name = (ntfs_u16*)def;
  253. if (!type) {
  254. ntfs_debug(DEBUG_OTHER, "process_atrdef: finished processing "
  255. "and returning 1n");
  256. return 1;
  257. }
  258. if (ntfs_ua_strncmp(name, "$STANDARD_INFORMATION", 64) == 0) {
  259. vol->at_standard_information = type;
  260. check_type = 0x10;
  261. } else if (ntfs_ua_strncmp(name, "$ATTRIBUTE_LIST", 64) == 0) {
  262. vol->at_attribute_list = type;
  263. check_type = 0x20;
  264. } else if (ntfs_ua_strncmp(name, "$FILE_NAME", 64) == 0) {
  265. vol->at_file_name = type;
  266. check_type = 0x30;
  267. } else if (ntfs_ua_strncmp(name, "$VOLUME_VERSION", 64) == 0) {
  268. vol->at_volume_version = type;
  269. check_type = 0x40;
  270. } else if (ntfs_ua_strncmp(name, "$SECURITY_DESCRIPTOR", 64) == 0) {
  271. vol->at_security_descriptor = type;
  272. check_type = 0x50;
  273. } else if (ntfs_ua_strncmp(name, "$VOLUME_NAME", 64) == 0) {
  274. vol->at_volume_name = type;
  275. check_type = 0x60;
  276. } else if (ntfs_ua_strncmp(name, "$VOLUME_INFORMATION", 64) == 0) {
  277. vol->at_volume_information = type;
  278. check_type = 0x70;
  279. } else if (ntfs_ua_strncmp(name, "$DATA", 64) == 0) {
  280. vol->at_data = type;
  281. check_type = 0x80;
  282. } else if (ntfs_ua_strncmp(name, "$INDEX_ROOT", 64) == 0) {
  283. vol->at_index_root = type;
  284. check_type = 0x90;
  285. } else if (ntfs_ua_strncmp(name, "$INDEX_ALLOCATION", 64) == 0) {
  286. vol->at_index_allocation = type;
  287. check_type = 0xA0;
  288. } else if (ntfs_ua_strncmp(name, "$BITMAP", 64) == 0) {
  289. vol->at_bitmap = type;
  290. check_type = 0xB0;
  291. } else if (ntfs_ua_strncmp(name, "$SYMBOLIC_LINK", 64) == 0 ||
  292.  ntfs_ua_strncmp(name, "$REPARSE_POINT", 64) == 0) {
  293. vol->at_symlink = type;
  294. check_type = 0xC0;
  295. }
  296. if (check_type && check_type != type) {
  297. ntfs_error("process_attrdef: unexpected type 0x%x for 0x%xn",
  298. type, check_type);
  299. return -EINVAL;
  300. }
  301. ntfs_debug(DEBUG_OTHER, "process_attrdef: found %s attribute of type "
  302. "0x%xn", check_type ? "known" : "unknown", type);
  303. return 0;
  304. }
  306. int ntfs_init_attrdef(ntfs_inode* attrdef)
  307. {
  308. ntfs_u8 *buf;
  309. ntfs_io io;
  310. __s64 offset;
  311. unsigned i;
  312. int error;
  313. ntfs_attribute *data;
  315. ntfs_debug(DEBUG_BSD, "Entered ntfs_init_attrdef()n");
  316. buf = ntfs_malloc(4050); /* 90*45 */
  317. if (!buf)
  318. return -ENOMEM;
  319. io.fn_put = ntfs_put;
  320. io.fn_get = ntfs_get;
  321. io.do_read = 1;
  322. offset = 0;
  323. data = ntfs_find_attr(attrdef, attrdef->vol->at_data, 0);
  324. ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() after call to "
  325. "ntfs_find_attr.n");
  326. if (!data) {
  327. ntfs_free(buf);
  328. return -EINVAL;
  329. }
  330. do {
  331. io.param = buf;
  332. io.size = 4050;
  333. ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() going to call "
  334. "ntfs_readwrite_attr.n");
  335. error = ntfs_readwrite_attr(attrdef, data, offset, &io);
  336. ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() after call to "
  337. "ntfs_readwrite_attr.n");
  338. for (i = 0; !error && i <= io.size - 0xA0; i += 0xA0) {
  339. ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() going "
  340. "to call process_attrdef.n");
  341. error = process_attrdef(attrdef, buf + i);
  342. ntfs_debug(DEBUG_BSD, "In ntfs_init_attrdef() after "
  343. "call to process_attrdef.n");
  344. }
  345. offset += 4096;
  346. } while (!error && io.size);
  347. ntfs_debug(DEBUG_BSD, "Exiting ntfs_init_attrdef()n");
  348. ntfs_free(buf);
  349. return error == 1 ? 0 : error;
  350. }
  352. /* ntfs_get_version will determine the NTFS version of the volume and will
  353.  * return the version in a BCD format, with the MSB being the major version
  354.  * number and the LSB the minor one. Otherwise return <0 on error.
  355.  * Example: version 3.1 will be returned as 0x0301. This has the obvious
  356.  * limitation of not coping with version numbers above 0x80 but that shouldn't
  357.  * be a problem... */
  358. int ntfs_get_version(ntfs_inode* volume)
  359. {
  360. ntfs_attribute *volinfo;
  362. volinfo = ntfs_find_attr(volume, volume->vol->at_volume_information, 0);
  363. if (!volinfo) 
  364. return -EINVAL;
  365. if (!volinfo->resident) {
  366. ntfs_error("Volume information attribute is not resident!n");
  367. return -EINVAL;
  368. }
  369. return ((ntfs_u8*)volinfo->d.data)[8] << 8 | 
  370.        ((ntfs_u8*)volinfo->d.data)[9];
  371. }
  373. int ntfs_load_special_files(ntfs_volume *vol)
  374. {
  375. int error;
  376. ntfs_inode upcase, attrdef, volume;
  378. vol->mft_ino = (ntfs_inode*)ntfs_calloc(sizeof(ntfs_inode));
  379. vol->mftmirr = (ntfs_inode*)ntfs_calloc(sizeof(ntfs_inode));
  380. vol->bitmap = (ntfs_inode*)ntfs_calloc(sizeof(ntfs_inode));
  381. vol->ino_flags = 4 | 2 | 1;
  382. error = -ENOMEM;
  383. ntfs_debug(DEBUG_BSD, "Going to load MFTn");
  384. if (!vol->mft_ino || (error = ntfs_init_inode(vol->mft_ino, vol,
  385. FILE_Mft))) {
  386. ntfs_error("Problem loading MFTn");
  387. return error;
  388. }
  389. ntfs_debug(DEBUG_BSD, "Going to load MIRRn");
  390. if ((error = ntfs_init_inode(vol->mftmirr, vol, FILE_MftMirr))) {
  391. ntfs_error("Problem %d loading MFTMirrn", error);
  392. return error;
  393. }
  394. ntfs_debug(DEBUG_BSD, "Going to load BITMAPn");
  395. if ((error = ntfs_init_inode(vol->bitmap, vol, FILE_BitMap))) {
  396. ntfs_error("Problem loading Bitmapn");
  397. return error;
  398. }
  399. ntfs_debug(DEBUG_BSD, "Going to load UPCASEn");
  400. error = ntfs_init_inode(&upcase, vol, FILE_UpCase);
  401. if (error)
  402. return error;
  403. ntfs_init_upcase(&upcase);
  404. ntfs_clear_inode(&upcase);
  405. ntfs_debug(DEBUG_BSD, "Going to load ATTRDEFn");
  406. error = ntfs_init_inode(&attrdef, vol, FILE_AttrDef);
  407. if (error)
  408. return error;
  409. error = ntfs_init_attrdef(&attrdef);
  410. ntfs_clear_inode(&attrdef);
  411. if (error)
  412. return error;
  414. /* Check for NTFS version and if Win2k version (ie. 3.0+) do not allow
  415.  * write access since the driver write support is broken. */
  416. ntfs_debug(DEBUG_BSD, "Going to load VOLUMEn");
  417. error = ntfs_init_inode(&volume, vol, FILE_Volume);
  418. if (error)
  419. return error;
  420. if ((error = ntfs_get_version(&volume)) >= 0x0300 &&
  421.     !(NTFS_SB(vol)->s_flags & MS_RDONLY)) {
  422. NTFS_SB(vol)->s_flags |= MS_RDONLY;
  423. ntfs_error("Warning! NTFS volume version is Win2k+: Mounting "
  424.    "read-onlyn");
  425. }
  426. ntfs_clear_inode(&volume);
  427. if (error < 0)
  428. return error;
  429. ntfs_debug(DEBUG_BSD, "NTFS volume is v%d.%dn", error >> 8,
  430. error & 0xff);
  431. return 0;
  432. }
  434. int ntfs_release_volume(ntfs_volume *vol)
  435. {
  436. if (((vol->ino_flags & 1) == 1) && vol->mft_ino) {
  437. ntfs_clear_inode(vol->mft_ino);
  438. ntfs_free(vol->mft_ino);
  439. vol->mft_ino = 0;
  440. }
  441. if (((vol->ino_flags & 2) == 2) && vol->mftmirr) {
  442. ntfs_clear_inode(vol->mftmirr);
  443. ntfs_free(vol->mftmirr);
  444. vol->mftmirr = 0;
  445. }
  446. if (((vol->ino_flags & 4) == 4) && vol->bitmap) {
  447. ntfs_clear_inode(vol->bitmap);
  448. ntfs_free(vol->bitmap);
  449. vol->bitmap = 0;
  450. }
  451. ntfs_free(vol->mft);
  452. ntfs_free(vol->upcase);
  453. return 0;
  454. }
  456. /*
  457.  * Writes the volume size (units of clusters) into vol_size.
  458.  * Returns 0 if successful or error.
  459.  */
  460. int ntfs_get_volumesize(ntfs_volume *vol, ntfs_s64 *vol_size)
  461. {
  462. ntfs_io io;
  463. char *cluster0;
  465. if (!vol_size)
  466. return -EFAULT;
  467. cluster0 = ntfs_malloc(vol->cluster_size);
  468. if (!cluster0)
  469. return -ENOMEM;
  470. io.fn_put = ntfs_put;
  471. io.fn_get = ntfs_get;
  472. io.param = cluster0;
  473. io.do_read = 1;
  474. io.size = vol->cluster_size;
  475. ntfs_getput_clusters(vol, 0, 0, &io);
  476. *vol_size = NTFS_GETU64(cluster0 + 0x28) >>
  477. (ffs(NTFS_GETU8(cluster0 + 0xD)) - 1);
  478. ntfs_free(cluster0);
  479. return 0;
  480. }
  482. static int nc[16]={4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0};
  484. int ntfs_get_free_cluster_count(ntfs_inode *bitmap)
  485. {
  486. ntfs_io io;
  487. int offset, error, clusters;
  488. unsigned char *bits = ntfs_malloc(2048);
  489. if (!bits)
  490. return -ENOMEM;
  491. offset = clusters = 0;
  492. io.fn_put = ntfs_put;
  493. io.fn_get = ntfs_get;
  494. while (1) {
  495. register int i;
  496. io.param = bits;
  497. io.size = 2048;
  498. error = ntfs_read_attr(bitmap, bitmap->vol->at_data, 0, offset,
  499. &io);
  500. if (error || io.size == 0)
  501. break;
  502. /* I never thought I would do loop unrolling some day */
  503. for (i = 0; i < io.size - 8; ) {
  504. clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  505. clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  506. clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  507. clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  508. clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  509. clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  510. clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  511. clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
  512. }
  513. while (i < io.size) {
  514. clusters += nc[bits[i] >> 4];
  515. clusters += nc[bits[i++] & 0xF];
  516. }
  517. offset += io.size;
  518. }
  519. ntfs_free(bits);
  520. return clusters;
  521. }
  523. /*
  524.  * Insert the fixups for the record. The number and location of the fixes
  525.  * is obtained from the record header but we double check with @rec_size and
  526.  * use that as the upper boundary, if necessary overwriting the count value in
  527.  * the record header.
  528.  *
  529.  * We return 0 on success or -1 if fixup header indicated the beginning of the
  530.  * update sequence array to be beyond the valid limit.
  531.  */
  532. int ntfs_insert_fixups(unsigned char *rec, int rec_size)
  533. {
  534. int first;
  535. int count;
  536. int offset = -2;
  537. ntfs_u16 fix;
  539. first = NTFS_GETU16(rec + 4);
  540. count = (rec_size >> NTFS_SECTOR_BITS) + 1;
  541. if (first + count * 2 > NTFS_SECTOR_SIZE - 2) {
  542. printk(KERN_CRIT "NTFS: ntfs_insert_fixups() detected corrupt "
  543. "NTFS record update sequence array position. - "
  544. "Cannot hotfix.n");
  545. return -1;
  546. }
  547. if (count != NTFS_GETU16(rec + 6)) {
  548. printk(KERN_ERR "NTFS: ntfs_insert_fixups() detected corrupt "
  549. "NTFS record update sequence array size. - "
  550. "Applying hotfix.n");
  551. NTFS_PUTU16(rec + 6, count);
  552. }
  553. fix = (NTFS_GETU16(rec + first) + 1) & 0xffff;
  554. if (fix == 0xffff || !fix)
  555. fix = 1;
  556. NTFS_PUTU16(rec + first, fix);
  557. count--;
  558. while (count--) {
  559. first += 2;
  560. offset += NTFS_SECTOR_SIZE;
  561. NTFS_PUTU16(rec + first, NTFS_GETU16(rec + offset));
  562. NTFS_PUTU16(rec + offset, fix);
  563. }
  564. return 0;
  565. }
  567. /**
  568.  * ntfs_allocate_clusters - allocate logical clusters on an ntfs volume
  569.  * @vol: volume on which to allocate clusters
  570.  * @location: preferred location for first allocated cluster
  571.  * @count: number of clusters to allocate
  572.  * @rl: address of pointer in which to return the allocated run list
  573.  * @rl_len: the number of elements returned in @*rl
  574.  *
  575.  * Allocate @*count clusters (LCNs), preferably beginning at @*location in the
  576.  * bitmap of the volume @vol. If @*location is -1, it does not matter where the
  577.  * clusters are. @rl is the address of a ntfs_runlist pointer which this
  578.  * function will allocate and fill with the runlist of the allocated clusters.
  579.  * It is the callers responsibility to ntfs_vfree() @*rl after she is finished
  580.  * with it. If the function was not successful, @*rl will be set to NULL.
  581.  * @*rl_len will contain the number of ntfs_runlist elements in @*rl or 0 if
  582.  * @*rl is NULL.
  583.  *
  584.  * Return 0 on success, or -errno on error. On success, @*location and @*count
  585.  * say what was really allocated. On -ENOSPC, @*location and @*count say what
  586.  * could have been allocated. If nothing could be allocated or a different
  587.  * error occured, @*location = -1 and @*count = 0.
  588.  *
  589.  * There are two data zones. First is the area between the end of the mft zone
  590.  * and the end of the volume, and second is the area between the start of the
  591.  * volume and the start of the mft zone. On unmodified/standard volumes, the
  592.  * second mft zone doesn't exist due to the mft zone being expanded to cover
  593.  * the start of volume in order to reserve space for the mft bitmap attribute.
  594.  *
  595.  * This is not the prettiest function but the complexity stems from the need of
  596.  * implementing the mft vs data zoned approach and from the fact that we have
  597.  * access to the lcn bitmap in portions of PAGE_SIZE bytes at a time, so we
  598.  * need to cope with crossing over boundaries of two pages. Further, the fact
  599.  * that the allocator allows for caller supplied hints as to the location of
  600.  * where allocation should begin and the fact that the allocator keeps track of
  601.  * where in the data zones the next natural allocation should occur, contribute
  602.  * to the complexity of the function. But it should all be worthwhile, because
  603.  * this allocator should: 1) be a full implementation of the MFT zone approach
  604.  * used by Windows, 2) cause reduction in fragmentation as much as possible,
  605.  * and 3) be speedy in allocations (the code is not optimized for speed, but
  606.  * the algorithm is, so further speed improvements are probably possible).
  607.  *
  608.  * FIXME: Really need finer-grained locking but this will do for the moment. I
  609.  * just want to kill all races and have a working allocator. When that is done,
  610.  * we can beautify... (AIA)
  611.  * 
  612.  * FIXME: We should be monitoring cluster allocation and increment the MFT zone
  613.  * size dynamically but this is something for the future. We will just cause
  614.  * heavier fragmentation by not doing it and I am not even sure Windows would
  615.  * grow the MFT zone dynamically, so might even be correct not doing this. The
  616.  * overhead in doing dynamic MFT zone expansion would be very large and unlikely
  617.  * worth the effort. (AIA)
  618.  *
  619.  * TODO: I have added in double the required zone position pointer wrap around
  620.  * logic which can be optimized to having only one of the two logic sets.
  621.  * However, having the double logic will work fine, but if we have only one of
  622.  * the sets and we get it wrong somewhere, then we get into trouble, so
  623.  * removing the duplicate logic requires _very_ careful consideration of _all_
  624.  * possible code paths. So at least for now, I am leaving the double logic -
  625.  * better safe than sorry... (AIA)
  626.  */
  627. int ntfs_allocate_clusters(ntfs_volume *vol, ntfs_cluster_t *location,
  628. ntfs_cluster_t *count, ntfs_runlist **rl, int *rl_len,
  629. const NTFS_CLUSTER_ALLOCATION_ZONES zone)
  630. {
  631. ntfs_runlist *rl2 = NULL, *rlt;
  632. ntfs_attribute *data;
  633. ntfs_cluster_t buf_pos, zone_start, zone_end, mft_zone_size;
  634. ntfs_cluster_t lcn, last_read_pos, prev_lcn = (ntfs_cluster_t)0;
  635. ntfs_cluster_t initial_location, prev_run_len = (ntfs_cluster_t)0;
  636. ntfs_cluster_t clusters = (ntfs_cluster_t)0;
  637. unsigned char *buf, *byte, bit, search_zone, done_zones;
  638. unsigned char pass, need_writeback;
  639. int rlpos = 0, rlsize, buf_size, err = 0;
  640. ntfs_io io;
  642. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Entering with *location = "
  643. "0x%x, *count = 0x%x, zone = %s_ZONE.n", *location,
  644. *count, zone == DATA_ZONE ? "DATA" : "MFT");
  645. buf = (char*)__get_free_page(GFP_NOFS);
  646. if (!buf) {
  647. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Returning "
  648. "-ENOMEM.n");
  649. return -ENOMEM;
  650. }
  651. io.fn_put = ntfs_put;
  652. io.fn_get = ntfs_get;
  653. lock_kernel();
  654. /* Get the $DATA attribute of $Bitmap. */
  655. data = ntfs_find_attr(vol->bitmap, vol->at_data, 0);
  656. if (!data) {
  657. err = -EINVAL;
  658. goto err_ret;
  659. }
  660. /*
  661.  * If no specific location was requested, use the current data zone
  662.  * position, otherwise use the requested location but make sure it lies
  663.  * outside the mft zone. Also set done_zones to 0 (no zones done) and
  664.  * pass depending on whether we are starting inside a zone (1) or
  665.  * at the beginning of a zone (2). If requesting from the MFT_ZONE, then
  666.  * we either start at the current position within the mft zone or at the
  667.  * specified position and if the latter is out of bounds then we start
  668.  * at the beginning of the MFT_ZONE.
  669.  */
  670. done_zones = 0;
  671. pass = 1;
  672. /*
  673.  * zone_start and zone_end are the current search range. search_zone
  674.  * is 1 for mft zone, 2 for data zone 1 (end of mft zone till end of
  675.  * volume) and 4 for data zone 2 (start of volume till start of mft
  676.  * zone).
  677.  */
  678. zone_start = *location;
  679. if (zone_start < 0) {
  680. if (zone == DATA_ZONE)
  681. zone_start = vol->data1_zone_pos;
  682. else
  683. zone_start = vol->mft_zone_pos;
  684. if (!zone_start)
  685. /*
  686.  * Zone starts at beginning of volume which means a
  687.  * single pass is sufficient.
  688.  */
  689. pass = 2;
  690. } else if (zone_start >= vol->mft_zone_start && zone_start <
  691. vol->mft_zone_end && zone == DATA_ZONE) {
  692. zone_start = vol->mft_zone_end;
  693. pass = 2;
  694. } else if ((zone_start < vol->mft_zone_start || zone_start >=
  695. vol->mft_zone_end) && zone == MFT_ZONE) {
  696. zone_start = vol->mft_lcn;
  697. if (!vol->mft_zone_end)
  698. zone_start = (ntfs_cluster_t)0;
  699. pass = 2;
  700. }
  701. if (zone == DATA_ZONE) {
  702. /* Skip searching the mft zone. */
  703. done_zones |= 1;
  704. if (zone_start >= vol->mft_zone_end) {
  705. zone_end = vol->nr_clusters;
  706. search_zone = 2;
  707. } else {
  708. zone_end = vol->mft_zone_start;
  709. search_zone = 4;
  710. }
  711. } else /* if (zone == MFT_ZONE) */ {
  712. zone_end = vol->mft_zone_end;
  713. search_zone = 1;
  714. }
  715. /*
  716.  * buf_pos is the current bit position inside the bitmap. We use
  717.  * initial_location to determine whether or not to do a zone switch.
  718.  */
  719. buf_pos = initial_location = zone_start;
  720. /* Loop until all clusters are allocated, i.e. clusters == 0. */
  721. clusters = *count;
  722. rlpos = rlsize = 0;
  723. if (*count <= 0) {
  724. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): *count <= 0, "
  725. "returning -EINVAL.n");
  726. err = -EINVAL;
  727. goto err_ret;
  728. }
  729. while (1) {
  730. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Start of outer while "
  731. "loop: done_zones = 0x%x, search_zone = %i, "
  732. "pass = %i, zone_start = 0x%x, zone_end = "
  733. "0x%x, initial_location = 0x%x, buf_pos = "
  734. "0x%x, rlpos = %i, rlsize = %i.n",
  735. done_zones, search_zone, pass, zone_start,
  736. zone_end, initial_location, buf_pos, rlpos,
  737. rlsize);
  738. /* Loop until we run out of free clusters. */
  739. io.param = buf;
  740. io.size = PAGE_SIZE;
  741. io.do_read = 1;
  742. last_read_pos = buf_pos >> 3;
  743. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): last_read_pos = "
  744. "0x%x.n", last_read_pos);
  745. err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
  746. &io);
  747. if (err) {
  748. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  749. "ntfs_read_attr failed with error "
  750. "code %i, going to err_ret.n", -err);
  751. goto err_ret;
  752. }
  753. if (!io.size) {
  754. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): !io.size, "
  755. "going to zone_pass_done.n");
  756. goto zone_pass_done;
  757. }
  758. buf_size = io.size << 3;
  759. lcn = buf_pos & 7;
  760. buf_pos &= ~7;
  761. need_writeback = 0;
  762. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Before inner while "
  763. "loop: buf_size = 0x%x, lcn = 0x%x, buf_pos = "
  764. "0x%x, need_writeback = %i.n", buf_size, lcn,
  765. buf_pos, need_writeback);
  766. while (lcn < buf_size && lcn + buf_pos < zone_end) {
  767. byte = buf + (lcn >> 3);
  768. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): In inner "
  769. "while loop: buf_size = 0x%x, lcn = "
  770. "0x%x, buf_pos = 0x%x, need_writeback "
  771. "= %i, byte ofs = 0x%x, *byte = "
  772. "0x%x.n", buf_size, lcn, buf_pos,
  773. need_writeback, lcn >> 3, *byte);
  774. /* Skip full bytes. */
  775. if (*byte == 0xff) {
  776. lcn += 8;
  777. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  778. "continuing while loop 1.n");
  779. continue;
  780. }
  781. bit = 1 << (lcn & 7);
  782. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): bit = %i.n",
  783. bit);
  784. /* If the bit is already set, go onto the next one. */
  785. if (*byte & bit) {
  786. lcn++;
  787. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  788. "continuing while loop 2.n");
  789. continue;
  790. }
  791. /* Allocate the bitmap bit. */
  792. *byte |= bit;
  793. /* We need to write this bitmap buffer back to disk! */
  794. need_writeback = 1;
  795. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): *byte = "
  796. "0x%x, need_writeback = %i.n", *byte,
  797. need_writeback);
  798. /* Reallocate memory if necessary. */
  799. if ((rlpos + 2) * sizeof(ntfs_runlist) >= rlsize) {
  800. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  801. "Reallocating space.n");
  802. /* Setup first free bit return value. */
  803. if (!rl2) {
  804. *location = lcn + buf_pos;
  805. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  806. "(): *location = "
  807. "0x%x.n", *location);
  808. }
  809. rlsize += PAGE_SIZE;
  810. rlt = ntfs_vmalloc(rlsize);
  811. if (!rlt) {
  812. err = -ENOMEM;
  813. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  814. "(): Failed to "
  815. "allocate memory, "
  816. "returning -ENOMEM, "
  817. "going to "
  818. "wb_err_ret.n");
  819. goto wb_err_ret;
  820. }
  821. if (rl2) {
  822. ntfs_memcpy(rlt, rl2, rlsize -
  823. PAGE_SIZE);
  824. ntfs_vfree(rl2);
  825. }
  826. rl2 = rlt;
  827. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  828. "Reallocated memory, rlsize = "
  829. "0x%x.n", rlsize);
  830. }
  831. /*
  832.  * Coalesce with previous run if adjacent LCNs.
  833.  * Otherwise, append a new run.
  834.  */
  835. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Adding run "
  836. "(lcn 0x%x, len 0x%x), prev_lcn = "
  837. "0x%x, lcn = 0x%x, buf_pos = 0x%x, "
  838. "prev_run_len = 0x%x, rlpos = %i.n",
  839. lcn + buf_pos, 1, prev_lcn, lcn,
  840. buf_pos, prev_run_len, rlpos);
  841. if (prev_lcn == lcn + buf_pos - prev_run_len && rlpos) {
  842. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  843. "Coalescing to run (lcn 0x%x, "
  844. "len 0x%x).n",
  845. rl2[rlpos - 1].lcn,
  846. rl2[rlpos - 1].len);
  847. rl2[rlpos - 1].len = ++prev_run_len;
  848. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  849. "Run now (lcn 0x%x, len 0x%x), "
  850. "prev_run_len = 0x%x.n",
  851. rl2[rlpos - 1].lcn,
  852. rl2[rlpos - 1].len,
  853. prev_run_len);
  854. } else {
  855. if (rlpos)
  856. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  857. "(): Adding new run, "
  858. "(previous run lcn "
  859. "0x%x, len 0x%x).n",
  860. rl2[rlpos - 1].lcn,
  861. rl2[rlpos - 1].len);
  862. else
  863. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  864. "(): Adding new run, "
  865. "is first run.n");
  866. rl2[rlpos].lcn = prev_lcn = lcn + buf_pos;
  867. rl2[rlpos].len = prev_run_len =
  868. (ntfs_cluster_t)1;
  870. rlpos++;
  871. }
  872. /* Done? */
  873. if (!--clusters) {
  874. ntfs_cluster_t tc;
  875. /*
  876.  * Update the current zone position. Positions
  877.  * of already scanned zones have been updated
  878.  * during the respective zone switches.
  879.  */
  880. tc = lcn + buf_pos + 1;
  881. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  882. "Done. Updating current zone "
  883. "position, tc = 0x%x, "
  884. "search_zone = %i.n", tc,
  885. search_zone);
  886. switch (search_zone) {
  887. case 1:
  888. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  889. "(): Before checks, "
  890. "vol->mft_zone_pos = "
  891. "0x%x.n",
  892. vol->mft_zone_pos);
  893. if (tc >= vol->mft_zone_end) {
  894. vol->mft_zone_pos =
  895. vol->mft_lcn;
  896. if (!vol->mft_zone_end)
  897. vol->mft_zone_pos =
  898.      (ntfs_cluster_t)0;
  899. } else if ((initial_location >=
  900. vol->mft_zone_pos ||
  901. tc > vol->mft_zone_pos)
  902. && tc >= vol->mft_lcn)
  903. vol->mft_zone_pos = tc;
  904. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  905. "(): After checks, "
  906. "vol->mft_zone_pos = "
  907. "0x%x.n",
  908. vol->mft_zone_pos);
  909. break;
  910. case 2:
  911. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  912. "(): Before checks, "
  913. "vol->data1_zone_pos = "
  914. "0x%x.n",
  915. vol->data1_zone_pos);
  916. if (tc >= vol->nr_clusters)
  917. vol->data1_zone_pos =
  918.      vol->mft_zone_end;
  919. else if ((initial_location >=
  920.     vol->data1_zone_pos ||
  921.     tc > vol->data1_zone_pos)
  922.     && tc >= vol->mft_zone_end)
  923. vol->data1_zone_pos = tc;
  924. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  925. "(): After checks, "
  926. "vol->data1_zone_pos = "
  927. "0x%x.n",
  928. vol->data1_zone_pos);
  929. break;
  930. case 4:
  931. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  932. "(): Before checks, "
  933. "vol->data2_zone_pos = "
  934. "0x%x.n",
  935. vol->data2_zone_pos);
  936. if (tc >= vol->mft_zone_start)
  937. vol->data2_zone_pos =
  938. (ntfs_cluster_t)0;
  939. else if (initial_location >=
  940.       vol->data2_zone_pos ||
  941.       tc > vol->data2_zone_pos)
  942. vol->data2_zone_pos = tc;
  943. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  944. "(): After checks, "
  945. "vol->data2_zone_pos = "
  946. "0x%x.n",
  947. vol->data2_zone_pos);
  948. break;
  949. default:
  950. BUG();
  951. }
  952. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  953. "Going to done_ret.n");
  954. goto done_ret;
  955. }
  956. lcn++;
  957. }
  958. buf_pos += buf_size;
  959. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After inner while "
  960. "loop: buf_size = 0x%x, lcn = 0x%x, buf_pos = "
  961. "0x%x, need_writeback = %i.n", buf_size, lcn,
  962. buf_pos, need_writeback);
  963. if (need_writeback) {
  964. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Writing "
  965. "back.n");
  966. need_writeback = 0;
  967. io.param = buf;
  968. io.do_read = 0;
  969. err = ntfs_readwrite_attr(vol->bitmap, data,
  970. last_read_pos, &io);
  971. if (err) {
  972. ntfs_error(__FUNCTION__ "(): Bitmap writeback "
  973. "failed in read next buffer "
  974. "code path with error code "
  975. "%i.n", -err);
  976. goto err_ret;
  977. }
  978. }
  979. if (buf_pos < zone_end) {
  980. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Continuing "
  981. "outer while loop, buf_pos = 0x%x, "
  982. "zone_end = 0x%x.n", buf_pos,
  983. zone_end);
  984. continue;
  985. }
  986. zone_pass_done: /* Finished with the current zone pass. */
  987. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At zone_pass_done, "
  988. "pass = %i.n", pass);
  989. if (pass == 1) {
  990. /*
  991.  * Now do pass 2, scanning the first part of the zone
  992.  * we omitted in pass 1.
  993.  */
  994. pass = 2;
  995. zone_end = zone_start;
  996. switch (search_zone) {
  997. case 1: /* mft_zone */
  998. zone_start = vol->mft_zone_start;
  999. break;
  1000. case 2: /* data1_zone */
  1001. zone_start = vol->mft_zone_end;
  1002. break;
  1003. case 4: /* data2_zone */
  1004. zone_start = (ntfs_cluster_t)0;
  1005. break;
  1006. default:
  1007. BUG();
  1008. }
  1009. /* Sanity check. */
  1010. if (zone_end < zone_start)
  1011. zone_end = zone_start;
  1012. buf_pos = zone_start;
  1013. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Continuing "
  1014. "outer while loop, pass = 2, "
  1015. "zone_start = 0x%x, zone_end = 0x%x, "
  1016. "buf_pos = 0x%x.n");
  1017. continue;
  1018. } /* pass == 2 */
  1019. done_zones_check:
  1020. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At done_zones_check, "
  1021. "search_zone = %i, done_zones before = 0x%x, "
  1022. "done_zones after = 0x%x.n",
  1023. search_zone, done_zones, done_zones |
  1024. search_zone);
  1025. done_zones |= search_zone;
  1026. if (done_zones < 7) {
  1027. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Switching "
  1028. "zone.n");
  1029. /* Now switch to the next zone we haven't done yet. */
  1030. pass = 1;
  1031. switch (search_zone) {
  1032. case 1:
  1033. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  1034. "Switching from mft zone to "
  1035. "data1 zone.n");
  1036. /* Update mft zone position. */
  1037. if (rlpos) {
  1038. ntfs_cluster_t tc;
  1039. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  1040. "(): Before checks, "
  1041. "vol->mft_zone_pos = "
  1042. "0x%x.n",
  1043. vol->mft_zone_pos);
  1044. tc = rl2[rlpos - 1].lcn +
  1045. rl2[rlpos - 1].len;
  1046. if (tc >= vol->mft_zone_end) {
  1047. vol->mft_zone_pos =
  1048. vol->mft_lcn;
  1049. if (!vol->mft_zone_end)
  1050. vol->mft_zone_pos =
  1051.      (ntfs_cluster_t)0;
  1052. } else if ((initial_location >=
  1053. vol->mft_zone_pos ||
  1054. tc > vol->mft_zone_pos)
  1055. && tc >= vol->mft_lcn)
  1056. vol->mft_zone_pos = tc;
  1057. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  1058. "(): After checks, "
  1059. "vol->mft_zone_pos = "
  1060. "0x%x.n",
  1061. vol->mft_zone_pos);
  1062. }
  1063. /* Switch from mft zone to data1 zone. */
  1064. switch_to_data1_zone: search_zone = 2;
  1065. zone_start = initial_location =
  1066. vol->data1_zone_pos;
  1067. zone_end = vol->nr_clusters;
  1068. if (zone_start == vol->mft_zone_end)
  1069. pass = 2;
  1070. if (zone_start >= zone_end) {
  1071. vol->data1_zone_pos = zone_start =
  1072. vol->mft_zone_end;
  1073. pass = 2;
  1074. }
  1075. break;
  1076. case 2:
  1077. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  1078. "Switching from data1 zone to "
  1079. "data2 zone.n");
  1080. /* Update data1 zone position. */
  1081. if (rlpos) {
  1082. ntfs_cluster_t tc;
  1083. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  1084. "(): Before checks, "
  1085. "vol->data1_zone_pos = "
  1086. "0x%x.n",
  1087. vol->data1_zone_pos);
  1088. tc = rl2[rlpos - 1].lcn +
  1089. rl2[rlpos - 1].len;
  1090. if (tc >= vol->nr_clusters)
  1091. vol->data1_zone_pos =
  1092.      vol->mft_zone_end;
  1093. else if ((initial_location >=
  1094.     vol->data1_zone_pos ||
  1095.     tc > vol->data1_zone_pos)
  1096.     && tc >= vol->mft_zone_end)
  1097. vol->data1_zone_pos = tc;
  1098. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  1099. "(): After checks, "
  1100. "vol->data1_zone_pos = "
  1101. "0x%x.n",
  1102. vol->data1_zone_pos);
  1103. }
  1104. /* Switch from data1 zone to data2 zone. */
  1105. search_zone = 4;
  1106. zone_start = initial_location =
  1107. vol->data2_zone_pos;
  1108. zone_end = vol->mft_zone_start;
  1109. if (!zone_start)
  1110. pass = 2;
  1111. if (zone_start >= zone_end) {
  1112. vol->data2_zone_pos = zone_start =
  1113. initial_location =
  1114. (ntfs_cluster_t)0;
  1115. pass = 2;
  1116. }
  1117. break;
  1118. case 4:
  1119. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  1120. "Switching from data2 zone to "
  1121. "data1 zone.n");
  1122. /* Update data2 zone position. */
  1123. if (rlpos) {
  1124. ntfs_cluster_t tc;
  1125. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  1126. "(): Before checks, "
  1127. "vol->data2_zone_pos = "
  1128. "0x%x.n",
  1129. vol->data2_zone_pos);
  1130. tc = rl2[rlpos - 1].lcn +
  1131. rl2[rlpos - 1].len;
  1132. if (tc >= vol->mft_zone_start)
  1133. vol->data2_zone_pos =
  1134.      (ntfs_cluster_t)0;
  1135. else if (initial_location >=
  1136.       vol->data2_zone_pos ||
  1137.       tc > vol->data2_zone_pos)
  1138. vol->data2_zone_pos = tc;
  1139. ntfs_debug(DEBUG_OTHER, __FUNCTION__
  1140. "(): After checks, "
  1141. "vol->data2_zone_pos = "
  1142. "0x%x.n",
  1143. vol->data2_zone_pos);
  1144. }
  1145. /* Switch from data2 zone to data1 zone. */
  1146. goto switch_to_data1_zone; /* See above. */
  1147. default:
  1148. BUG();
  1149. }
  1150. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After zone "
  1151. "switch, search_zone = %i, pass = %i, "
  1152. "initial_location = 0x%x, zone_start "
  1153. "= 0x%x, zone_end = 0x%x.n",
  1154. search_zone, pass, initial_location,
  1155. zone_start, zone_end);
  1156. buf_pos = zone_start;
  1157. if (zone_start == zone_end) {
  1158. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): "
  1159. "Empty zone, going to "
  1160. "done_zones_check.n");
  1161. /* Empty zone. Don't bother searching it. */
  1162. goto done_zones_check;
  1163. }
  1164. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Continuing "
  1165. "outer while loop.n");
  1166. continue;
  1167. } /* done_zones == 7 */
  1168. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): All zones are "
  1169. "finished.n");
  1170. /*
  1171.  * All zones are finished! If DATA_ZONE, shrink mft zone. If
  1172.  * MFT_ZONE, we have really run out of space.
  1173.  */
  1174. mft_zone_size = vol->mft_zone_end - vol->mft_zone_start;
  1175. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): vol->mft_zone_start "
  1176. "= 0x%x, vol->mft_zone_end = 0x%x, "
  1177. "mft_zone_size = 0x%x.n", vol->mft_zone_start,
  1178. vol->mft_zone_end, mft_zone_size);
  1179. if (zone == MFT_ZONE || mft_zone_size <= (ntfs_cluster_t)0) {
  1180. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): No free "
  1181. "clusters left, returning -ENOSPC, "
  1182. "going to fail_ret.n");
  1183. /* Really no more space left on device. */
  1184. err = -ENOSPC;
  1185. goto fail_ret;
  1186. } /* zone == DATA_ZONE && mft_zone_size > 0 */
  1187. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Shrinking mft "
  1188. "zone.n");
  1189. zone_end = vol->mft_zone_end;
  1190. mft_zone_size >>= 1;
  1191. if (mft_zone_size > (ntfs_cluster_t)0)
  1192. vol->mft_zone_end = vol->mft_zone_start + mft_zone_size;
  1193. else /* mft zone and data2 zone no longer exist. */
  1194. vol->data2_zone_pos = vol->mft_zone_start =
  1195. vol->mft_zone_end = (ntfs_cluster_t)0;
  1196. if (vol->mft_zone_pos >= vol->mft_zone_end) {
  1197. vol->mft_zone_pos = vol->mft_lcn;
  1198. if (!vol->mft_zone_end)
  1199. vol->mft_zone_pos = (ntfs_cluster_t)0;
  1200. }
  1201. buf_pos = zone_start = initial_location =
  1202. vol->data1_zone_pos = vol->mft_zone_end;
  1203. search_zone = 2;
  1204. pass = 2;
  1205. done_zones &= ~2;
  1206. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After shrinking mft "
  1207. "zone, mft_zone_size = 0x%x, "
  1208. "vol->mft_zone_start = 0x%x, vol->mft_zone_end "
  1209. "= 0x%x, vol->mft_zone_pos = 0x%x, search_zone "
  1210. "= 2, pass = 2, dones_zones = 0x%x, zone_start "
  1211. "= 0x%x, zone_end = 0x%x, vol->data1_zone_pos "
  1212. "= 0x%x, continuing outer while loop.n",
  1213. mft_zone_size, vol->mft_zone_start,
  1214. vol->mft_zone_end, vol->mft_zone_pos,
  1215. search_zone, pass, done_zones, zone_start,
  1216. zone_end, vol->data1_zone_pos);
  1217. }
  1218. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): After outer while loop.n");
  1219. done_ret:
  1220. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At done_ret.n");
  1221. rl2[rlpos].lcn = (ntfs_cluster_t)-1;
  1222. rl2[rlpos].len = (ntfs_cluster_t)0;
  1223. *rl = rl2;
  1224. *rl_len = rlpos;
  1225. if (need_writeback) {
  1226. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Writing back.n");
  1227. need_writeback = 0;
  1228. io.param = buf;
  1229. io.do_read = 0;
  1230. err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
  1231. &io);
  1232. if (err) {
  1233. ntfs_error(__FUNCTION__ "(): Bitmap writeback failed "
  1234. "in done code path with error code "
  1235. "%i.n", -err);
  1236. goto err_ret;
  1237. }
  1238. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Wrote 0x%Lx bytes.n",
  1239. io.size);
  1240. }
  1241. done_fail_ret:
  1242. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At done_fail_ret (follows "
  1243. "done_ret).n");
  1244. unlock_kernel();
  1245. free_page((unsigned long)buf);
  1246. if (err)
  1247. ntfs_debug(DEBUG_FILE3, __FUNCTION__ "(): Failed to allocate "
  1248. "clusters. Returning with error code %i.n",
  1249. -err);
  1250. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Syncing $Bitmap inode.n");
  1251. if (ntfs_update_inode(vol->bitmap))
  1252. ntfs_error(__FUNCTION__ "(): Failed to sync inode $Bitmap. "
  1253. "Continuing anyway.n");
  1254. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Returning with code %i.n",
  1255. err);
  1256. return err;
  1257. fail_ret:
  1258. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At fail_ret.n");
  1259. if (rl2) {
  1260. if (err == -ENOSPC) {
  1261. /* Return first free lcn and count of free clusters. */
  1262. *location = rl2[0].lcn;
  1263. *count -= clusters;
  1264. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): err = "
  1265. "-ENOSPC, *location = 0x%x, *count = "
  1266. "0x%x.n", *location, *count);
  1267. }
  1268. /* Deallocate all allocated clusters. */
  1269. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Deallocating "
  1270. "allocated clusters.n");
  1271. ntfs_deallocate_clusters(vol, rl2, rlpos);
  1272. /* Free the runlist. */
  1273. ntfs_vfree(rl2);
  1274. } else {
  1275. if (err == -ENOSPC) {
  1276. /* Nothing free at all. */
  1277. *location = vol->data1_zone_pos; /* Irrelevant... */
  1278. *count = 0;
  1279. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): No space "
  1280. "left at all, err = -ENOSPC, *location "
  1281. "= 0x%x, *count = 0.n", *location);
  1282. }
  1283. }
  1284. *rl = NULL;
  1285. *rl_len = 0;
  1286. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): *rl = NULL, *rl_len = 0, "
  1287. "going to done_fail_ret.n");
  1288. goto done_fail_ret;
  1289. wb_err_ret:
  1290. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At wb_err_ret.n");
  1291. if (need_writeback) {
  1292. int __err;
  1293. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): Writing back.n");
  1294. io.param = buf;
  1295. io.do_read = 0;
  1296. __err = ntfs_readwrite_attr(vol->bitmap, data, last_read_pos,
  1297. &io);
  1298. if (__err)
  1299. ntfs_error(__FUNCTION__ "(): Bitmap writeback failed "
  1300. "in error code path with error code "
  1301. "%i.n", -__err);
  1302. need_writeback = 0;
  1303. }
  1304. err_ret:
  1305. ntfs_debug(DEBUG_OTHER, __FUNCTION__ "(): At err_ret, *location = -1, "
  1306. "*count = 0, going to fail_ret.n");
  1307. *location = -1;
  1308. *count = 0;
  1309. goto fail_ret;
  1310. }
  1312. /*
  1313.  * IMPORTANT: Caller has to hold big kernel lock or the race monster will come
  1314.  * to get you! (-;
  1315.  * TODO: Need our own lock for bitmap accesses but BKL is more secure for now,
  1316.  * considering we might not have covered all places with a lock yet. In that
  1317.  * case the BKL offers a one way exclusion which is better than no exclusion
  1318.  * at all... (AIA)
  1319.  */
  1320. static int ntfs_clear_bitrange(ntfs_inode *bitmap,
  1321. const ntfs_cluster_t start_bit, const ntfs_cluster_t count)
  1322. {
  1323. ntfs_cluster_t buf_size, bit, nr_bits = count;
  1324. unsigned char *buf, *byte;
  1325. int err;
  1326. ntfs_io io;
  1328. io.fn_put = ntfs_put;
  1329. io.fn_get = ntfs_get;
  1330. /* Calculate the required buffer size in bytes. */
  1331. buf_size = (ntfs_cluster_t)((start_bit & 7) + nr_bits + 7) >> 3;
  1332. if (buf_size <= (ntfs_cluster_t)(64 * 1024))
  1333. buf = ntfs_malloc(buf_size);
  1334. else
  1335. buf = ntfs_vmalloc(buf_size);
  1336. if (!buf)
  1337. return -ENOMEM;
  1338. /* Read the bitmap from the data attribute. */
  1339. io.param = byte = buf;
  1340. io.size = buf_size;
  1341. err = ntfs_read_attr(bitmap, bitmap->vol->at_data, 0, start_bit >> 3,
  1342. &io);
  1343. if (err || io.size != buf_size)
  1344. goto err_out;
  1345. /* Now clear the bits in the read bitmap. */
  1346. bit = start_bit & 7;
  1347. while (bit && nr_bits) { /* Process first partial byte, if present. */
  1348. *byte &= ~(1 << bit++);
  1349. nr_bits--;
  1350. bit &= 7;
  1351. if (!bit)
  1352. byte++;
  1353. }
  1354. while (nr_bits >= 8) { /* Process full bytes. */
  1355. *byte = 0;
  1356. nr_bits -= 8;
  1357. byte++;
  1358. }
  1359. bit = 0;
  1360. while (nr_bits) { /* Process last partial byte, if present. */
  1361. *byte &= ~(1 << bit);
  1362. nr_bits--;
  1363. bit++;
  1364. }
  1365. /* Write the modified bitmap back to disk. */
  1366. io.param = buf;
  1367. io.size = buf_size;
  1368. err = ntfs_write_attr(bitmap, bitmap->vol->at_data, 0, start_bit >> 3,
  1369. &io);
  1370. err_out:
  1371. if (buf_size <= (ntfs_cluster_t)(64 * 1024))
  1372. ntfs_free(buf);
  1373. else
  1374. ntfs_vfree(buf);
  1375. if (!err && io.size != buf_size)
  1376. err = -EIO;
  1377. return err;
  1378. }
  1380. /*
  1381.  * See comments for lack of zone adjustments below in the description of the
  1382.  * function ntfs_deallocate_clusters().
  1383.  */
  1384. int ntfs_deallocate_cluster_run(const ntfs_volume *vol,
  1385. const ntfs_cluster_t lcn, const ntfs_cluster_t len)
  1386. {
  1387. int err;
  1389. lock_kernel();
  1390. err = ntfs_clear_bitrange(vol->bitmap, lcn, len);
  1391. unlock_kernel();
  1392. return err;
  1393. }
  1395. /*
  1396.  * This is inefficient, but logically trivial, so will do for now. Note, we
  1397.  * do not touch the mft nor the data zones here because we want to minimize
  1398.  * recycling of clusters to enhance the chances of data being undeleteable.
  1399.  * Also we don't want the overhead. Instead we do one additional sweep of the
  1400.  * current data zone during cluster allocation to check for freed clusters.
  1401.  */
  1402. int ntfs_deallocate_clusters(const ntfs_volume *vol, const ntfs_runlist *rl,
  1403. const int rl_len)
  1404. {
  1405. int i, err;
  1407. lock_kernel();
  1408. for (i = err = 0; i < rl_len && !err; i++)
  1409. err = ntfs_clear_bitrange(vol->bitmap, rl[i].lcn, rl[i].len);
  1410. unlock_kernel();
  1411. return err;
  1412. }