ialloc.c 37 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331
  1. /*
  2. * linux/fs/ext4/ialloc.c
  3. *
  4. * Copyright (C) 1992, 1993, 1994, 1995
  5. * Remy Card (card@masi.ibp.fr)
  6. * Laboratoire MASI - Institut Blaise Pascal
  7. * Universite Pierre et Marie Curie (Paris VI)
  8. *
  9. * BSD ufs-inspired inode and directory allocation by
  10. * Stephen Tweedie (sct@redhat.com), 1993
  11. * Big-endian to little-endian byte-swapping/bitmaps by
  12. * David S. Miller (davem@caip.rutgers.edu), 1995
  13. */
  14. #include <linux/time.h>
  15. #include <linux/fs.h>
  16. #include <linux/jbd2.h>
  17. #include <linux/stat.h>
  18. #include <linux/string.h>
  19. #include <linux/quotaops.h>
  20. #include <linux/buffer_head.h>
  21. #include <linux/random.h>
  22. #include <linux/bitops.h>
  23. #include <linux/blkdev.h>
  24. #include <asm/byteorder.h>
  25. #include "ext4.h"
  26. #include "ext4_jbd2.h"
  27. #include "xattr.h"
  28. #include "acl.h"
  29. #include <trace/events/ext4.h>
  30. /*
  31. * ialloc.c contains the inodes allocation and deallocation routines
  32. */
  33. /*
  34. * The free inodes are managed by bitmaps. A file system contains several
  35. * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap
  36. * block for inodes, N blocks for the inode table and data blocks.
  37. *
  38. * The file system contains group descriptors which are located after the
  39. * super block. Each descriptor contains the number of the bitmap block and
  40. * the free blocks count in the block.
  41. */
  42. /*
  43. * To avoid calling the atomic setbit hundreds or thousands of times, we only
  44. * need to use it within a single byte (to ensure we get endianness right).
  45. * We can use memset for the rest of the bitmap as there are no other users.
  46. */
  47. void ext4_mark_bitmap_end(int start_bit, int end_bit, char *bitmap)
  48. {
  49. int i;
  50. if (start_bit >= end_bit)
  51. return;
  52. ext4_debug("mark end bits +%d through +%d used\n", start_bit, end_bit);
  53. for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
  54. ext4_set_bit(i, bitmap);
  55. if (i < end_bit)
  56. memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3);
  57. }
  58. /* Initializes an uninitialized inode bitmap */
  59. static unsigned ext4_init_inode_bitmap(struct super_block *sb,
  60. struct buffer_head *bh,
  61. ext4_group_t block_group,
  62. struct ext4_group_desc *gdp)
  63. {
  64. struct ext4_sb_info *sbi = EXT4_SB(sb);
  65. J_ASSERT_BH(bh, buffer_locked(bh));
  66. /* If checksum is bad mark all blocks and inodes use to prevent
  67. * allocation, essentially implementing a per-group read-only flag. */
  68. if (!ext4_group_desc_csum_verify(sbi, block_group, gdp)) {
  69. ext4_error(sb, "Checksum bad for group %u", block_group);
  70. ext4_free_blks_set(sb, gdp, 0);
  71. ext4_free_inodes_set(sb, gdp, 0);
  72. ext4_itable_unused_set(sb, gdp, 0);
  73. memset(bh->b_data, 0xff, sb->s_blocksize);
  74. return 0;
  75. }
  76. memset(bh->b_data, 0, (EXT4_INODES_PER_GROUP(sb) + 7) / 8);
  77. ext4_mark_bitmap_end(EXT4_INODES_PER_GROUP(sb), sb->s_blocksize * 8,
  78. bh->b_data);
  79. return EXT4_INODES_PER_GROUP(sb);
  80. }
  81. /*
  82. * Read the inode allocation bitmap for a given block_group, reading
  83. * into the specified slot in the superblock's bitmap cache.
  84. *
  85. * Return buffer_head of bitmap on success or NULL.
  86. */
  87. static struct buffer_head *
  88. ext4_read_inode_bitmap(struct super_block *sb, ext4_group_t block_group)
  89. {
  90. struct ext4_group_desc *desc;
  91. struct buffer_head *bh = NULL;
  92. ext4_fsblk_t bitmap_blk;
  93. desc = ext4_get_group_desc(sb, block_group, NULL);
  94. if (!desc)
  95. return NULL;
  96. bitmap_blk = ext4_inode_bitmap(sb, desc);
  97. bh = sb_getblk(sb, bitmap_blk);
  98. if (unlikely(!bh)) {
  99. ext4_error(sb, "Cannot read inode bitmap - "
  100. "block_group = %u, inode_bitmap = %llu",
  101. block_group, bitmap_blk);
  102. return NULL;
  103. }
  104. if (bitmap_uptodate(bh))
  105. return bh;
  106. lock_buffer(bh);
  107. if (bitmap_uptodate(bh)) {
  108. unlock_buffer(bh);
  109. return bh;
  110. }
  111. ext4_lock_group(sb, block_group);
  112. if (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
  113. ext4_init_inode_bitmap(sb, bh, block_group, desc);
  114. set_bitmap_uptodate(bh);
  115. set_buffer_uptodate(bh);
  116. ext4_unlock_group(sb, block_group);
  117. unlock_buffer(bh);
  118. return bh;
  119. }
  120. ext4_unlock_group(sb, block_group);
  121. if (buffer_uptodate(bh)) {
  122. /*
  123. * if not uninit if bh is uptodate,
  124. * bitmap is also uptodate
  125. */
  126. set_bitmap_uptodate(bh);
  127. unlock_buffer(bh);
  128. return bh;
  129. }
  130. /*
  131. * submit the buffer_head for read. We can
  132. * safely mark the bitmap as uptodate now.
  133. * We do it here so the bitmap uptodate bit
  134. * get set with buffer lock held.
  135. */
  136. trace_ext4_load_inode_bitmap(sb, block_group);
  137. set_bitmap_uptodate(bh);
  138. if (bh_submit_read(bh) < 0) {
  139. put_bh(bh);
  140. ext4_error(sb, "Cannot read inode bitmap - "
  141. "block_group = %u, inode_bitmap = %llu",
  142. block_group, bitmap_blk);
  143. return NULL;
  144. }
  145. return bh;
  146. }
  147. /*
  148. * NOTE! When we get the inode, we're the only people
  149. * that have access to it, and as such there are no
  150. * race conditions we have to worry about. The inode
  151. * is not on the hash-lists, and it cannot be reached
  152. * through the filesystem because the directory entry
  153. * has been deleted earlier.
  154. *
  155. * HOWEVER: we must make sure that we get no aliases,
  156. * which means that we have to call "clear_inode()"
  157. * _before_ we mark the inode not in use in the inode
  158. * bitmaps. Otherwise a newly created file might use
  159. * the same inode number (not actually the same pointer
  160. * though), and then we'd have two inodes sharing the
  161. * same inode number and space on the harddisk.
  162. */
  163. void ext4_free_inode(handle_t *handle, struct inode *inode)
  164. {
  165. struct super_block *sb = inode->i_sb;
  166. int is_directory;
  167. unsigned long ino;
  168. struct buffer_head *bitmap_bh = NULL;
  169. struct buffer_head *bh2;
  170. ext4_group_t block_group;
  171. unsigned long bit;
  172. struct ext4_group_desc *gdp;
  173. struct ext4_super_block *es;
  174. struct ext4_sb_info *sbi;
  175. int fatal = 0, err, count, cleared;
  176. if (atomic_read(&inode->i_count) > 1) {
  177. printk(KERN_ERR "ext4_free_inode: inode has count=%d\n",
  178. atomic_read(&inode->i_count));
  179. return;
  180. }
  181. if (inode->i_nlink) {
  182. printk(KERN_ERR "ext4_free_inode: inode has nlink=%d\n",
  183. inode->i_nlink);
  184. return;
  185. }
  186. if (!sb) {
  187. printk(KERN_ERR "ext4_free_inode: inode on "
  188. "nonexistent device\n");
  189. return;
  190. }
  191. sbi = EXT4_SB(sb);
  192. ino = inode->i_ino;
  193. ext4_debug("freeing inode %lu\n", ino);
  194. trace_ext4_free_inode(inode);
  195. /*
  196. * Note: we must free any quota before locking the superblock,
  197. * as writing the quota to disk may need the lock as well.
  198. */
  199. dquot_initialize(inode);
  200. ext4_xattr_delete_inode(handle, inode);
  201. dquot_free_inode(inode);
  202. dquot_drop(inode);
  203. is_directory = S_ISDIR(inode->i_mode);
  204. /* Do this BEFORE marking the inode not in use or returning an error */
  205. ext4_clear_inode(inode);
  206. es = EXT4_SB(sb)->s_es;
  207. if (ino < EXT4_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) {
  208. ext4_error(sb, "reserved or nonexistent inode %lu", ino);
  209. goto error_return;
  210. }
  211. block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
  212. bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
  213. bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
  214. if (!bitmap_bh)
  215. goto error_return;
  216. BUFFER_TRACE(bitmap_bh, "get_write_access");
  217. fatal = ext4_journal_get_write_access(handle, bitmap_bh);
  218. if (fatal)
  219. goto error_return;
  220. fatal = -ESRCH;
  221. gdp = ext4_get_group_desc(sb, block_group, &bh2);
  222. if (gdp) {
  223. BUFFER_TRACE(bh2, "get_write_access");
  224. fatal = ext4_journal_get_write_access(handle, bh2);
  225. }
  226. ext4_lock_group(sb, block_group);
  227. cleared = ext4_clear_bit(bit, bitmap_bh->b_data);
  228. if (fatal || !cleared) {
  229. ext4_unlock_group(sb, block_group);
  230. goto out;
  231. }
  232. count = ext4_free_inodes_count(sb, gdp) + 1;
  233. ext4_free_inodes_set(sb, gdp, count);
  234. if (is_directory) {
  235. count = ext4_used_dirs_count(sb, gdp) - 1;
  236. ext4_used_dirs_set(sb, gdp, count);
  237. percpu_counter_dec(&sbi->s_dirs_counter);
  238. }
  239. gdp->bg_checksum = ext4_group_desc_csum(sbi, block_group, gdp);
  240. ext4_unlock_group(sb, block_group);
  241. percpu_counter_inc(&sbi->s_freeinodes_counter);
  242. if (sbi->s_log_groups_per_flex) {
  243. ext4_group_t f = ext4_flex_group(sbi, block_group);
  244. atomic_inc(&sbi->s_flex_groups[f].free_inodes);
  245. if (is_directory)
  246. atomic_dec(&sbi->s_flex_groups[f].used_dirs);
  247. }
  248. BUFFER_TRACE(bh2, "call ext4_handle_dirty_metadata");
  249. fatal = ext4_handle_dirty_metadata(handle, NULL, bh2);
  250. out:
  251. if (cleared) {
  252. BUFFER_TRACE(bitmap_bh, "call ext4_handle_dirty_metadata");
  253. err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
  254. if (!fatal)
  255. fatal = err;
  256. ext4_mark_super_dirty(sb);
  257. } else
  258. ext4_error(sb, "bit already cleared for inode %lu", ino);
  259. error_return:
  260. brelse(bitmap_bh);
  261. ext4_std_error(sb, fatal);
  262. }
  263. /*
  264. * There are two policies for allocating an inode. If the new inode is
  265. * a directory, then a forward search is made for a block group with both
  266. * free space and a low directory-to-inode ratio; if that fails, then of
  267. * the groups with above-average free space, that group with the fewest
  268. * directories already is chosen.
  269. *
  270. * For other inodes, search forward from the parent directory\'s block
  271. * group to find a free inode.
  272. */
  273. static int find_group_dir(struct super_block *sb, struct inode *parent,
  274. ext4_group_t *best_group)
  275. {
  276. ext4_group_t ngroups = ext4_get_groups_count(sb);
  277. unsigned int freei, avefreei;
  278. struct ext4_group_desc *desc, *best_desc = NULL;
  279. ext4_group_t group;
  280. int ret = -1;
  281. freei = percpu_counter_read_positive(&EXT4_SB(sb)->s_freeinodes_counter);
  282. avefreei = freei / ngroups;
  283. for (group = 0; group < ngroups; group++) {
  284. desc = ext4_get_group_desc(sb, group, NULL);
  285. if (!desc || !ext4_free_inodes_count(sb, desc))
  286. continue;
  287. if (ext4_free_inodes_count(sb, desc) < avefreei)
  288. continue;
  289. if (!best_desc ||
  290. (ext4_free_blks_count(sb, desc) >
  291. ext4_free_blks_count(sb, best_desc))) {
  292. *best_group = group;
  293. best_desc = desc;
  294. ret = 0;
  295. }
  296. }
  297. return ret;
  298. }
  299. #define free_block_ratio 10
  300. static int find_group_flex(struct super_block *sb, struct inode *parent,
  301. ext4_group_t *best_group)
  302. {
  303. struct ext4_sb_info *sbi = EXT4_SB(sb);
  304. struct ext4_group_desc *desc;
  305. struct flex_groups *flex_group = sbi->s_flex_groups;
  306. ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
  307. ext4_group_t parent_fbg_group = ext4_flex_group(sbi, parent_group);
  308. ext4_group_t ngroups = ext4_get_groups_count(sb);
  309. int flex_size = ext4_flex_bg_size(sbi);
  310. ext4_group_t best_flex = parent_fbg_group;
  311. int blocks_per_flex = sbi->s_blocks_per_group * flex_size;
  312. int flexbg_free_clusters;
  313. int flex_freeb_ratio;
  314. ext4_group_t n_fbg_groups;
  315. ext4_group_t i;
  316. n_fbg_groups = (ngroups + flex_size - 1) >>
  317. sbi->s_log_groups_per_flex;
  318. find_close_to_parent:
  319. flexbg_free_clusters = atomic_read(&flex_group[best_flex].free_clusters);
  320. flex_freeb_ratio = EXT4_C2B(sbi, flexbg_free_clusters) * 100 /
  321. blocks_per_flex;
  322. if (atomic_read(&flex_group[best_flex].free_inodes) &&
  323. flex_freeb_ratio > free_block_ratio)
  324. goto found_flexbg;
  325. if (best_flex && best_flex == parent_fbg_group) {
  326. best_flex--;
  327. goto find_close_to_parent;
  328. }
  329. for (i = 0; i < n_fbg_groups; i++) {
  330. if (i == parent_fbg_group || i == parent_fbg_group - 1)
  331. continue;
  332. flexbg_free_clusters = atomic_read(&flex_group[i].free_clusters);
  333. flex_freeb_ratio = EXT4_C2B(sbi, flexbg_free_clusters) * 100 /
  334. blocks_per_flex;
  335. if (flex_freeb_ratio > free_block_ratio &&
  336. (atomic_read(&flex_group[i].free_inodes))) {
  337. best_flex = i;
  338. goto found_flexbg;
  339. }
  340. if ((atomic_read(&flex_group[best_flex].free_inodes) == 0) ||
  341. ((atomic_read(&flex_group[i].free_clusters) >
  342. atomic_read(&flex_group[best_flex].free_clusters)) &&
  343. atomic_read(&flex_group[i].free_inodes)))
  344. best_flex = i;
  345. }
  346. if (!atomic_read(&flex_group[best_flex].free_inodes) ||
  347. !atomic_read(&flex_group[best_flex].free_clusters))
  348. return -1;
  349. found_flexbg:
  350. for (i = best_flex * flex_size; i < ngroups &&
  351. i < (best_flex + 1) * flex_size; i++) {
  352. desc = ext4_get_group_desc(sb, i, NULL);
  353. if (ext4_free_inodes_count(sb, desc)) {
  354. *best_group = i;
  355. goto out;
  356. }
  357. }
  358. return -1;
  359. out:
  360. return 0;
  361. }
  362. struct orlov_stats {
  363. __u32 free_inodes;
  364. __u32 free_clusters;
  365. __u32 used_dirs;
  366. };
  367. /*
  368. * Helper function for Orlov's allocator; returns critical information
  369. * for a particular block group or flex_bg. If flex_size is 1, then g
  370. * is a block group number; otherwise it is flex_bg number.
  371. */
  372. static void get_orlov_stats(struct super_block *sb, ext4_group_t g,
  373. int flex_size, struct orlov_stats *stats)
  374. {
  375. struct ext4_group_desc *desc;
  376. struct flex_groups *flex_group = EXT4_SB(sb)->s_flex_groups;
  377. if (flex_size > 1) {
  378. stats->free_inodes = atomic_read(&flex_group[g].free_inodes);
  379. stats->free_clusters = atomic_read(&flex_group[g].free_clusters);
  380. stats->used_dirs = atomic_read(&flex_group[g].used_dirs);
  381. return;
  382. }
  383. desc = ext4_get_group_desc(sb, g, NULL);
  384. if (desc) {
  385. stats->free_inodes = ext4_free_inodes_count(sb, desc);
  386. stats->free_clusters = ext4_free_blks_count(sb, desc);
  387. stats->used_dirs = ext4_used_dirs_count(sb, desc);
  388. } else {
  389. stats->free_inodes = 0;
  390. stats->free_clusters = 0;
  391. stats->used_dirs = 0;
  392. }
  393. }
  394. /*
  395. * Orlov's allocator for directories.
  396. *
  397. * We always try to spread first-level directories.
  398. *
  399. * If there are blockgroups with both free inodes and free blocks counts
  400. * not worse than average we return one with smallest directory count.
  401. * Otherwise we simply return a random group.
  402. *
  403. * For the rest rules look so:
  404. *
  405. * It's OK to put directory into a group unless
  406. * it has too many directories already (max_dirs) or
  407. * it has too few free inodes left (min_inodes) or
  408. * it has too few free blocks left (min_blocks) or
  409. * Parent's group is preferred, if it doesn't satisfy these
  410. * conditions we search cyclically through the rest. If none
  411. * of the groups look good we just look for a group with more
  412. * free inodes than average (starting at parent's group).
  413. */
  414. static int find_group_orlov(struct super_block *sb, struct inode *parent,
  415. ext4_group_t *group, int mode,
  416. const struct qstr *qstr)
  417. {
  418. ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
  419. struct ext4_sb_info *sbi = EXT4_SB(sb);
  420. ext4_group_t real_ngroups = ext4_get_groups_count(sb);
  421. int inodes_per_group = EXT4_INODES_PER_GROUP(sb);
  422. unsigned int freei, avefreei;
  423. ext4_fsblk_t freeb, avefreec;
  424. unsigned int ndirs;
  425. int max_dirs, min_inodes;
  426. ext4_grpblk_t min_clusters;
  427. ext4_group_t i, grp, g, ngroups;
  428. struct ext4_group_desc *desc;
  429. struct orlov_stats stats;
  430. int flex_size = ext4_flex_bg_size(sbi);
  431. struct dx_hash_info hinfo;
  432. ngroups = real_ngroups;
  433. if (flex_size > 1) {
  434. ngroups = (real_ngroups + flex_size - 1) >>
  435. sbi->s_log_groups_per_flex;
  436. parent_group >>= sbi->s_log_groups_per_flex;
  437. }
  438. freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
  439. avefreei = freei / ngroups;
  440. freeb = EXT4_C2B(sbi,
  441. percpu_counter_read_positive(&sbi->s_freeclusters_counter));
  442. avefreec = freeb;
  443. do_div(avefreec, ngroups);
  444. ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);
  445. if (S_ISDIR(mode) &&
  446. ((parent == sb->s_root->d_inode) ||
  447. (ext4_test_inode_flag(parent, EXT4_INODE_TOPDIR)))) {
  448. int best_ndir = inodes_per_group;
  449. int ret = -1;
  450. if (qstr) {
  451. hinfo.hash_version = DX_HASH_HALF_MD4;
  452. hinfo.seed = sbi->s_hash_seed;
  453. ext4fs_dirhash(qstr->name, qstr->len, &hinfo);
  454. grp = hinfo.hash;
  455. } else
  456. get_random_bytes(&grp, sizeof(grp));
  457. parent_group = (unsigned)grp % ngroups;
  458. for (i = 0; i < ngroups; i++) {
  459. g = (parent_group + i) % ngroups;
  460. get_orlov_stats(sb, g, flex_size, &stats);
  461. if (!stats.free_inodes)
  462. continue;
  463. if (stats.used_dirs >= best_ndir)
  464. continue;
  465. if (stats.free_inodes < avefreei)
  466. continue;
  467. if (stats.free_clusters < avefreec)
  468. continue;
  469. grp = g;
  470. ret = 0;
  471. best_ndir = stats.used_dirs;
  472. }
  473. if (ret)
  474. goto fallback;
  475. found_flex_bg:
  476. if (flex_size == 1) {
  477. *group = grp;
  478. return 0;
  479. }
  480. /*
  481. * We pack inodes at the beginning of the flexgroup's
  482. * inode tables. Block allocation decisions will do
  483. * something similar, although regular files will
  484. * start at 2nd block group of the flexgroup. See
  485. * ext4_ext_find_goal() and ext4_find_near().
  486. */
  487. grp *= flex_size;
  488. for (i = 0; i < flex_size; i++) {
  489. if (grp+i >= real_ngroups)
  490. break;
  491. desc = ext4_get_group_desc(sb, grp+i, NULL);
  492. if (desc && ext4_free_inodes_count(sb, desc)) {
  493. *group = grp+i;
  494. return 0;
  495. }
  496. }
  497. goto fallback;
  498. }
  499. max_dirs = ndirs / ngroups + inodes_per_group / 16;
  500. min_inodes = avefreei - inodes_per_group*flex_size / 4;
  501. if (min_inodes < 1)
  502. min_inodes = 1;
  503. min_clusters = avefreec - EXT4_CLUSTERS_PER_GROUP(sb)*flex_size / 4;
  504. /*
  505. * Start looking in the flex group where we last allocated an
  506. * inode for this parent directory
  507. */
  508. if (EXT4_I(parent)->i_last_alloc_group != ~0) {
  509. parent_group = EXT4_I(parent)->i_last_alloc_group;
  510. if (flex_size > 1)
  511. parent_group >>= sbi->s_log_groups_per_flex;
  512. }
  513. for (i = 0; i < ngroups; i++) {
  514. grp = (parent_group + i) % ngroups;
  515. get_orlov_stats(sb, grp, flex_size, &stats);
  516. if (stats.used_dirs >= max_dirs)
  517. continue;
  518. if (stats.free_inodes < min_inodes)
  519. continue;
  520. if (stats.free_clusters < min_clusters)
  521. continue;
  522. goto found_flex_bg;
  523. }
  524. fallback:
  525. ngroups = real_ngroups;
  526. avefreei = freei / ngroups;
  527. fallback_retry:
  528. parent_group = EXT4_I(parent)->i_block_group;
  529. for (i = 0; i < ngroups; i++) {
  530. grp = (parent_group + i) % ngroups;
  531. desc = ext4_get_group_desc(sb, grp, NULL);
  532. if (desc && ext4_free_inodes_count(sb, desc) &&
  533. ext4_free_inodes_count(sb, desc) >= avefreei) {
  534. *group = grp;
  535. return 0;
  536. }
  537. }
  538. if (avefreei) {
  539. /*
  540. * The free-inodes counter is approximate, and for really small
  541. * filesystems the above test can fail to find any blockgroups
  542. */
  543. avefreei = 0;
  544. goto fallback_retry;
  545. }
  546. return -1;
  547. }
  548. static int find_group_other(struct super_block *sb, struct inode *parent,
  549. ext4_group_t *group, int mode)
  550. {
  551. ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
  552. ext4_group_t i, last, ngroups = ext4_get_groups_count(sb);
  553. struct ext4_group_desc *desc;
  554. int flex_size = ext4_flex_bg_size(EXT4_SB(sb));
  555. /*
  556. * Try to place the inode is the same flex group as its
  557. * parent. If we can't find space, use the Orlov algorithm to
  558. * find another flex group, and store that information in the
  559. * parent directory's inode information so that use that flex
  560. * group for future allocations.
  561. */
  562. if (flex_size > 1) {
  563. int retry = 0;
  564. try_again:
  565. parent_group &= ~(flex_size-1);
  566. last = parent_group + flex_size;
  567. if (last > ngroups)
  568. last = ngroups;
  569. for (i = parent_group; i < last; i++) {
  570. desc = ext4_get_group_desc(sb, i, NULL);
  571. if (desc && ext4_free_inodes_count(sb, desc)) {
  572. *group = i;
  573. return 0;
  574. }
  575. }
  576. if (!retry && EXT4_I(parent)->i_last_alloc_group != ~0) {
  577. retry = 1;
  578. parent_group = EXT4_I(parent)->i_last_alloc_group;
  579. goto try_again;
  580. }
  581. /*
  582. * If this didn't work, use the Orlov search algorithm
  583. * to find a new flex group; we pass in the mode to
  584. * avoid the topdir algorithms.
  585. */
  586. *group = parent_group + flex_size;
  587. if (*group > ngroups)
  588. *group = 0;
  589. return find_group_orlov(sb, parent, group, mode, NULL);
  590. }
  591. /*
  592. * Try to place the inode in its parent directory
  593. */
  594. *group = parent_group;
  595. desc = ext4_get_group_desc(sb, *group, NULL);
  596. if (desc && ext4_free_inodes_count(sb, desc) &&
  597. ext4_free_blks_count(sb, desc))
  598. return 0;
  599. /*
  600. * We're going to place this inode in a different blockgroup from its
  601. * parent. We want to cause files in a common directory to all land in
  602. * the same blockgroup. But we want files which are in a different
  603. * directory which shares a blockgroup with our parent to land in a
  604. * different blockgroup.
  605. *
  606. * So add our directory's i_ino into the starting point for the hash.
  607. */
  608. *group = (*group + parent->i_ino) % ngroups;
  609. /*
  610. * Use a quadratic hash to find a group with a free inode and some free
  611. * blocks.
  612. */
  613. for (i = 1; i < ngroups; i <<= 1) {
  614. *group += i;
  615. if (*group >= ngroups)
  616. *group -= ngroups;
  617. desc = ext4_get_group_desc(sb, *group, NULL);
  618. if (desc && ext4_free_inodes_count(sb, desc) &&
  619. ext4_free_blks_count(sb, desc))
  620. return 0;
  621. }
  622. /*
  623. * That failed: try linear search for a free inode, even if that group
  624. * has no free blocks.
  625. */
  626. *group = parent_group;
  627. for (i = 0; i < ngroups; i++) {
  628. if (++*group >= ngroups)
  629. *group = 0;
  630. desc = ext4_get_group_desc(sb, *group, NULL);
  631. if (desc && ext4_free_inodes_count(sb, desc))
  632. return 0;
  633. }
  634. return -1;
  635. }
  636. /*
  637. * claim the inode from the inode bitmap. If the group
  638. * is uninit we need to take the groups's ext4_group_lock
  639. * and clear the uninit flag. The inode bitmap update
  640. * and group desc uninit flag clear should be done
  641. * after holding ext4_group_lock so that ext4_read_inode_bitmap
  642. * doesn't race with the ext4_claim_inode
  643. */
  644. static int ext4_claim_inode(struct super_block *sb,
  645. struct buffer_head *inode_bitmap_bh,
  646. unsigned long ino, ext4_group_t group, int mode)
  647. {
  648. int free = 0, retval = 0, count;
  649. struct ext4_sb_info *sbi = EXT4_SB(sb);
  650. struct ext4_group_info *grp = ext4_get_group_info(sb, group);
  651. struct ext4_group_desc *gdp = ext4_get_group_desc(sb, group, NULL);
  652. /*
  653. * We have to be sure that new inode allocation does not race with
  654. * inode table initialization, because otherwise we may end up
  655. * allocating and writing new inode right before sb_issue_zeroout
  656. * takes place and overwriting our new inode with zeroes. So we
  657. * take alloc_sem to prevent it.
  658. */
  659. down_read(&grp->alloc_sem);
  660. ext4_lock_group(sb, group);
  661. if (ext4_set_bit(ino, inode_bitmap_bh->b_data)) {
  662. /* not a free inode */
  663. retval = 1;
  664. goto err_ret;
  665. }
  666. ino++;
  667. if ((group == 0 && ino < EXT4_FIRST_INO(sb)) ||
  668. ino > EXT4_INODES_PER_GROUP(sb)) {
  669. ext4_unlock_group(sb, group);
  670. up_read(&grp->alloc_sem);
  671. ext4_error(sb, "reserved inode or inode > inodes count - "
  672. "block_group = %u, inode=%lu", group,
  673. ino + group * EXT4_INODES_PER_GROUP(sb));
  674. return 1;
  675. }
  676. /* If we didn't allocate from within the initialized part of the inode
  677. * table then we need to initialize up to this inode. */
  678. if (EXT4_HAS_RO_COMPAT_FEATURE(sb, EXT4_FEATURE_RO_COMPAT_GDT_CSUM)) {
  679. if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
  680. gdp->bg_flags &= cpu_to_le16(~EXT4_BG_INODE_UNINIT);
  681. /* When marking the block group with
  682. * ~EXT4_BG_INODE_UNINIT we don't want to depend
  683. * on the value of bg_itable_unused even though
  684. * mke2fs could have initialized the same for us.
  685. * Instead we calculated the value below
  686. */
  687. free = 0;
  688. } else {
  689. free = EXT4_INODES_PER_GROUP(sb) -
  690. ext4_itable_unused_count(sb, gdp);
  691. }
  692. /*
  693. * Check the relative inode number against the last used
  694. * relative inode number in this group. if it is greater
  695. * we need to update the bg_itable_unused count
  696. *
  697. */
  698. if (ino > free)
  699. ext4_itable_unused_set(sb, gdp,
  700. (EXT4_INODES_PER_GROUP(sb) - ino));
  701. }
  702. count = ext4_free_inodes_count(sb, gdp) - 1;
  703. ext4_free_inodes_set(sb, gdp, count);
  704. if (S_ISDIR(mode)) {
  705. count = ext4_used_dirs_count(sb, gdp) + 1;
  706. ext4_used_dirs_set(sb, gdp, count);
  707. if (sbi->s_log_groups_per_flex) {
  708. ext4_group_t f = ext4_flex_group(sbi, group);
  709. atomic_inc(&sbi->s_flex_groups[f].used_dirs);
  710. }
  711. }
  712. gdp->bg_checksum = ext4_group_desc_csum(sbi, group, gdp);
  713. err_ret:
  714. ext4_unlock_group(sb, group);
  715. up_read(&grp->alloc_sem);
  716. return retval;
  717. }
  718. /*
  719. * There are two policies for allocating an inode. If the new inode is
  720. * a directory, then a forward search is made for a block group with both
  721. * free space and a low directory-to-inode ratio; if that fails, then of
  722. * the groups with above-average free space, that group with the fewest
  723. * directories already is chosen.
  724. *
  725. * For other inodes, search forward from the parent directory's block
  726. * group to find a free inode.
  727. */
  728. struct inode *ext4_new_inode(handle_t *handle, struct inode *dir, int mode,
  729. const struct qstr *qstr, __u32 goal)
  730. {
  731. struct super_block *sb;
  732. struct buffer_head *inode_bitmap_bh = NULL;
  733. struct buffer_head *group_desc_bh;
  734. ext4_group_t ngroups, group = 0;
  735. unsigned long ino = 0;
  736. struct inode *inode;
  737. struct ext4_group_desc *gdp = NULL;
  738. struct ext4_inode_info *ei;
  739. struct ext4_sb_info *sbi;
  740. int ret2, err = 0;
  741. struct inode *ret;
  742. ext4_group_t i;
  743. static int once = 1;
  744. ext4_group_t flex_group;
  745. /* Cannot create files in a deleted directory */
  746. if (!dir || !dir->i_nlink)
  747. return ERR_PTR(-EPERM);
  748. sb = dir->i_sb;
  749. ngroups = ext4_get_groups_count(sb);
  750. trace_ext4_request_inode(dir, mode);
  751. inode = new_inode(sb);
  752. if (!inode)
  753. return ERR_PTR(-ENOMEM);
  754. ei = EXT4_I(inode);
  755. sbi = EXT4_SB(sb);
  756. if (!goal)
  757. goal = sbi->s_inode_goal;
  758. if (goal && goal <= le32_to_cpu(sbi->s_es->s_inodes_count)) {
  759. group = (goal - 1) / EXT4_INODES_PER_GROUP(sb);
  760. ino = (goal - 1) % EXT4_INODES_PER_GROUP(sb);
  761. ret2 = 0;
  762. goto got_group;
  763. }
  764. if (sbi->s_log_groups_per_flex && test_opt(sb, OLDALLOC)) {
  765. ret2 = find_group_flex(sb, dir, &group);
  766. if (ret2 == -1) {
  767. ret2 = find_group_other(sb, dir, &group, mode);
  768. if (ret2 == 0 && once) {
  769. once = 0;
  770. printk(KERN_NOTICE "ext4: find_group_flex "
  771. "failed, fallback succeeded dir %lu\n",
  772. dir->i_ino);
  773. }
  774. }
  775. goto got_group;
  776. }
  777. if (S_ISDIR(mode)) {
  778. if (test_opt(sb, OLDALLOC))
  779. ret2 = find_group_dir(sb, dir, &group);
  780. else
  781. ret2 = find_group_orlov(sb, dir, &group, mode, qstr);
  782. } else
  783. ret2 = find_group_other(sb, dir, &group, mode);
  784. got_group:
  785. EXT4_I(dir)->i_last_alloc_group = group;
  786. err = -ENOSPC;
  787. if (ret2 == -1)
  788. goto out;
  789. for (i = 0; i < ngroups; i++, ino = 0) {
  790. err = -EIO;
  791. gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
  792. if (!gdp)
  793. goto fail;
  794. brelse(inode_bitmap_bh);
  795. inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
  796. if (!inode_bitmap_bh)
  797. goto fail;
  798. repeat_in_this_group:
  799. ino = ext4_find_next_zero_bit((unsigned long *)
  800. inode_bitmap_bh->b_data,
  801. EXT4_INODES_PER_GROUP(sb), ino);
  802. if (ino < EXT4_INODES_PER_GROUP(sb)) {
  803. BUFFER_TRACE(inode_bitmap_bh, "get_write_access");
  804. err = ext4_journal_get_write_access(handle,
  805. inode_bitmap_bh);
  806. if (err)
  807. goto fail;
  808. BUFFER_TRACE(group_desc_bh, "get_write_access");
  809. err = ext4_journal_get_write_access(handle,
  810. group_desc_bh);
  811. if (err)
  812. goto fail;
  813. if (!ext4_claim_inode(sb, inode_bitmap_bh,
  814. ino, group, mode)) {
  815. /* we won it */
  816. BUFFER_TRACE(inode_bitmap_bh,
  817. "call ext4_handle_dirty_metadata");
  818. err = ext4_handle_dirty_metadata(handle,
  819. NULL,
  820. inode_bitmap_bh);
  821. if (err)
  822. goto fail;
  823. /* zero bit is inode number 1*/
  824. ino++;
  825. goto got;
  826. }
  827. /* we lost it */
  828. ext4_handle_release_buffer(handle, inode_bitmap_bh);
  829. ext4_handle_release_buffer(handle, group_desc_bh);
  830. if (++ino < EXT4_INODES_PER_GROUP(sb))
  831. goto repeat_in_this_group;
  832. }
  833. /*
  834. * This case is possible in concurrent environment. It is very
  835. * rare. We cannot repeat the find_group_xxx() call because
  836. * that will simply return the same blockgroup, because the
  837. * group descriptor metadata has not yet been updated.
  838. * So we just go onto the next blockgroup.
  839. */
  840. if (++group == ngroups)
  841. group = 0;
  842. }
  843. err = -ENOSPC;
  844. goto out;
  845. got:
  846. /* We may have to initialize the block bitmap if it isn't already */
  847. if (EXT4_HAS_RO_COMPAT_FEATURE(sb, EXT4_FEATURE_RO_COMPAT_GDT_CSUM) &&
  848. gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
  849. struct buffer_head *block_bitmap_bh;
  850. block_bitmap_bh = ext4_read_block_bitmap(sb, group);
  851. BUFFER_TRACE(block_bitmap_bh, "get block bitmap access");
  852. err = ext4_journal_get_write_access(handle, block_bitmap_bh);
  853. if (err) {
  854. brelse(block_bitmap_bh);
  855. goto fail;
  856. }
  857. BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap");
  858. err = ext4_handle_dirty_metadata(handle, NULL, block_bitmap_bh);
  859. brelse(block_bitmap_bh);
  860. /* recheck and clear flag under lock if we still need to */
  861. ext4_lock_group(sb, group);
  862. if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
  863. gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
  864. ext4_free_blks_set(sb, gdp,
  865. ext4_free_blocks_after_init(sb, group, gdp));
  866. gdp->bg_checksum = ext4_group_desc_csum(sbi, group,
  867. gdp);
  868. }
  869. ext4_unlock_group(sb, group);
  870. if (err)
  871. goto fail;
  872. }
  873. BUFFER_TRACE(group_desc_bh, "call ext4_handle_dirty_metadata");
  874. err = ext4_handle_dirty_metadata(handle, NULL, group_desc_bh);
  875. if (err)
  876. goto fail;
  877. percpu_counter_dec(&sbi->s_freeinodes_counter);
  878. if (S_ISDIR(mode))
  879. percpu_counter_inc(&sbi->s_dirs_counter);
  880. ext4_mark_super_dirty(sb);
  881. if (sbi->s_log_groups_per_flex) {
  882. flex_group = ext4_flex_group(sbi, group);
  883. atomic_dec(&sbi->s_flex_groups[flex_group].free_inodes);
  884. }
  885. if (test_opt(sb, GRPID)) {
  886. inode->i_mode = mode;
  887. inode->i_uid = current_fsuid();
  888. inode->i_gid = dir->i_gid;
  889. } else
  890. inode_init_owner(inode, dir, mode);
  891. inode->i_ino = ino + group * EXT4_INODES_PER_GROUP(sb);
  892. /* This is the optimal IO size (for stat), not the fs block size */
  893. inode->i_blocks = 0;
  894. inode->i_mtime = inode->i_atime = inode->i_ctime = ei->i_crtime =
  895. ext4_current_time(inode);
  896. memset(ei->i_data, 0, sizeof(ei->i_data));
  897. ei->i_dir_start_lookup = 0;
  898. ei->i_disksize = 0;
  899. /*
  900. * Don't inherit extent flag from directory, amongst others. We set
  901. * extent flag on newly created directory and file only if -o extent
  902. * mount option is specified
  903. */
  904. ei->i_flags =
  905. ext4_mask_flags(mode, EXT4_I(dir)->i_flags & EXT4_FL_INHERITED);
  906. ei->i_file_acl = 0;
  907. ei->i_dtime = 0;
  908. ei->i_block_group = group;
  909. ei->i_last_alloc_group = ~0;
  910. ext4_set_inode_flags(inode);
  911. if (IS_DIRSYNC(inode))
  912. ext4_handle_sync(handle);
  913. if (insert_inode_locked(inode) < 0) {
  914. err = -EINVAL;
  915. goto fail_drop;
  916. }
  917. spin_lock(&sbi->s_next_gen_lock);
  918. inode->i_generation = sbi->s_next_generation++;
  919. spin_unlock(&sbi->s_next_gen_lock);
  920. ext4_clear_state_flags(ei); /* Only relevant on 32-bit archs */
  921. ext4_set_inode_state(inode, EXT4_STATE_NEW);
  922. ei->i_extra_isize = EXT4_SB(sb)->s_want_extra_isize;
  923. ret = inode;
  924. dquot_initialize(inode);
  925. err = dquot_alloc_inode(inode);
  926. if (err)
  927. goto fail_drop;
  928. err = ext4_init_acl(handle, inode, dir);
  929. if (err)
  930. goto fail_free_drop;
  931. err = ext4_init_security(handle, inode, dir, qstr);
  932. if (err)
  933. goto fail_free_drop;
  934. if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
  935. /* set extent flag only for directory, file and normal symlink*/
  936. if (S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) {
  937. ext4_set_inode_flag(inode, EXT4_INODE_EXTENTS);
  938. ext4_ext_tree_init(handle, inode);
  939. }
  940. }
  941. if (ext4_handle_valid(handle)) {
  942. ei->i_sync_tid = handle->h_transaction->t_tid;
  943. ei->i_datasync_tid = handle->h_transaction->t_tid;
  944. }
  945. err = ext4_mark_inode_dirty(handle, inode);
  946. if (err) {
  947. ext4_std_error(sb, err);
  948. goto fail_free_drop;
  949. }
  950. ext4_debug("allocating inode %lu\n", inode->i_ino);
  951. trace_ext4_allocate_inode(inode, dir, mode);
  952. goto really_out;
  953. fail:
  954. ext4_std_error(sb, err);
  955. out:
  956. iput(inode);
  957. ret = ERR_PTR(err);
  958. really_out:
  959. brelse(inode_bitmap_bh);
  960. return ret;
  961. fail_free_drop:
  962. dquot_free_inode(inode);
  963. fail_drop:
  964. dquot_drop(inode);
  965. inode->i_flags |= S_NOQUOTA;
  966. inode->i_nlink = 0;
  967. unlock_new_inode(inode);
  968. iput(inode);
  969. brelse(inode_bitmap_bh);
  970. return ERR_PTR(err);
  971. }
  972. /* Verify that we are loading a valid orphan from disk */
  973. struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
  974. {
  975. unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
  976. ext4_group_t block_group;
  977. int bit;
  978. struct buffer_head *bitmap_bh;
  979. struct inode *inode = NULL;
  980. long err = -EIO;
  981. /* Error cases - e2fsck has already cleaned up for us */
  982. if (ino > max_ino) {
  983. ext4_warning(sb, "bad orphan ino %lu! e2fsck was run?", ino);
  984. goto error;
  985. }
  986. block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
  987. bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
  988. bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
  989. if (!bitmap_bh) {
  990. ext4_warning(sb, "inode bitmap error for orphan %lu", ino);
  991. goto error;
  992. }
  993. /* Having the inode bit set should be a 100% indicator that this
  994. * is a valid orphan (no e2fsck run on fs). Orphans also include
  995. * inodes that were being truncated, so we can't check i_nlink==0.
  996. */
  997. if (!ext4_test_bit(bit, bitmap_bh->b_data))
  998. goto bad_orphan;
  999. inode = ext4_iget(sb, ino);
  1000. if (IS_ERR(inode))
  1001. goto iget_failed;
  1002. /*
  1003. * If the orphans has i_nlinks > 0 then it should be able to be
  1004. * truncated, otherwise it won't be removed from the orphan list
  1005. * during processing and an infinite loop will result.
  1006. */
  1007. if (inode->i_nlink && !ext4_can_truncate(inode))
  1008. goto bad_orphan;
  1009. if (NEXT_ORPHAN(inode) > max_ino)
  1010. goto bad_orphan;
  1011. brelse(bitmap_bh);
  1012. return inode;
  1013. iget_failed:
  1014. err = PTR_ERR(inode);
  1015. inode = NULL;
  1016. bad_orphan:
  1017. ext4_warning(sb, "bad orphan inode %lu! e2fsck was run?", ino);
  1018. printk(KERN_NOTICE "ext4_test_bit(bit=%d, block=%llu) = %d\n",
  1019. bit, (unsigned long long)bitmap_bh->b_blocknr,
  1020. ext4_test_bit(bit, bitmap_bh->b_data));
  1021. printk(KERN_NOTICE "inode=%p\n", inode);
  1022. if (inode) {
  1023. printk(KERN_NOTICE "is_bad_inode(inode)=%d\n",
  1024. is_bad_inode(inode));
  1025. printk(KERN_NOTICE "NEXT_ORPHAN(inode)=%u\n",
  1026. NEXT_ORPHAN(inode));
  1027. printk(KERN_NOTICE "max_ino=%lu\n", max_ino);
  1028. printk(KERN_NOTICE "i_nlink=%u\n", inode->i_nlink);
  1029. /* Avoid freeing blocks if we got a bad deleted inode */
  1030. if (inode->i_nlink == 0)
  1031. inode->i_blocks = 0;
  1032. iput(inode);
  1033. }
  1034. brelse(bitmap_bh);
  1035. error:
  1036. return ERR_PTR(err);
  1037. }
  1038. unsigned long ext4_count_free_inodes(struct super_block *sb)
  1039. {
  1040. unsigned long desc_count;
  1041. struct ext4_group_desc *gdp;
  1042. ext4_group_t i, ngroups = ext4_get_groups_count(sb);
  1043. #ifdef EXT4FS_DEBUG
  1044. struct ext4_super_block *es;
  1045. unsigned long bitmap_count, x;
  1046. struct buffer_head *bitmap_bh = NULL;
  1047. es = EXT4_SB(sb)->s_es;
  1048. desc_count = 0;
  1049. bitmap_count = 0;
  1050. gdp = NULL;
  1051. for (i = 0; i < ngroups; i++) {
  1052. gdp = ext4_get_group_desc(sb, i, NULL);
  1053. if (!gdp)
  1054. continue;
  1055. desc_count += ext4_free_inodes_count(sb, gdp);
  1056. brelse(bitmap_bh);
  1057. bitmap_bh = ext4_read_inode_bitmap(sb, i);
  1058. if (!bitmap_bh)
  1059. continue;
  1060. x = ext4_count_free(bitmap_bh, EXT4_INODES_PER_GROUP(sb) / 8);
  1061. printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
  1062. (unsigned long) i, ext4_free_inodes_count(sb, gdp), x);
  1063. bitmap_count += x;
  1064. }
  1065. brelse(bitmap_bh);
  1066. printk(KERN_DEBUG "ext4_count_free_inodes: "
  1067. "stored = %u, computed = %lu, %lu\n",
  1068. le32_to_cpu(es->s_free_inodes_count), desc_count, bitmap_count);
  1069. return desc_count;
  1070. #else
  1071. desc_count = 0;
  1072. for (i = 0; i < ngroups; i++) {
  1073. gdp = ext4_get_group_desc(sb, i, NULL);
  1074. if (!gdp)
  1075. continue;
  1076. desc_count += ext4_free_inodes_count(sb, gdp);
  1077. cond_resched();
  1078. }
  1079. return desc_count;
  1080. #endif
  1081. }
  1082. /* Called at mount-time, super-block is locked */
  1083. unsigned long ext4_count_dirs(struct super_block * sb)
  1084. {
  1085. unsigned long count = 0;
  1086. ext4_group_t i, ngroups = ext4_get_groups_count(sb);
  1087. for (i = 0; i < ngroups; i++) {
  1088. struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL);
  1089. if (!gdp)
  1090. continue;
  1091. count += ext4_used_dirs_count(sb, gdp);
  1092. }
  1093. return count;
  1094. }
  1095. /*
  1096. * Zeroes not yet zeroed inode table - just write zeroes through the whole
  1097. * inode table. Must be called without any spinlock held. The only place
  1098. * where it is called from on active part of filesystem is ext4lazyinit
  1099. * thread, so we do not need any special locks, however we have to prevent
  1100. * inode allocation from the current group, so we take alloc_sem lock, to
  1101. * block ext4_claim_inode until we are finished.
  1102. */
  1103. extern int ext4_init_inode_table(struct super_block *sb, ext4_group_t group,
  1104. int barrier)
  1105. {
  1106. struct ext4_group_info *grp = ext4_get_group_info(sb, group);
  1107. struct ext4_sb_info *sbi = EXT4_SB(sb);
  1108. struct ext4_group_desc *gdp = NULL;
  1109. struct buffer_head *group_desc_bh;
  1110. handle_t *handle;
  1111. ext4_fsblk_t blk;
  1112. int num, ret = 0, used_blks = 0;
  1113. /* This should not happen, but just to be sure check this */
  1114. if (sb->s_flags & MS_RDONLY) {
  1115. ret = 1;
  1116. goto out;
  1117. }
  1118. gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
  1119. if (!gdp)
  1120. goto out;
  1121. /*
  1122. * We do not need to lock this, because we are the only one
  1123. * handling this flag.
  1124. */
  1125. if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_ZEROED))
  1126. goto out;
  1127. handle = ext4_journal_start_sb(sb, 1);
  1128. if (IS_ERR(handle)) {
  1129. ret = PTR_ERR(handle);
  1130. goto out;
  1131. }
  1132. down_write(&grp->alloc_sem);
  1133. /*
  1134. * If inode bitmap was already initialized there may be some
  1135. * used inodes so we need to skip blocks with used inodes in
  1136. * inode table.
  1137. */
  1138. if (!(gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)))
  1139. used_blks = DIV_ROUND_UP((EXT4_INODES_PER_GROUP(sb) -
  1140. ext4_itable_unused_count(sb, gdp)),
  1141. sbi->s_inodes_per_block);
  1142. if ((used_blks < 0) || (used_blks > sbi->s_itb_per_group)) {
  1143. ext4_error(sb, "Something is wrong with group %u\n"
  1144. "Used itable blocks: %d"
  1145. "itable unused count: %u\n",
  1146. group, used_blks,
  1147. ext4_itable_unused_count(sb, gdp));
  1148. ret = 1;
  1149. goto err_out;
  1150. }
  1151. blk = ext4_inode_table(sb, gdp) + used_blks;
  1152. num = sbi->s_itb_per_group - used_blks;
  1153. BUFFER_TRACE(group_desc_bh, "get_write_access");
  1154. ret = ext4_journal_get_write_access(handle,
  1155. group_desc_bh);
  1156. if (ret)
  1157. goto err_out;
  1158. /*
  1159. * Skip zeroout if the inode table is full. But we set the ZEROED
  1160. * flag anyway, because obviously, when it is full it does not need
  1161. * further zeroing.
  1162. */
  1163. if (unlikely(num == 0))
  1164. goto skip_zeroout;
  1165. ext4_debug("going to zero out inode table in group %d\n",
  1166. group);
  1167. ret = sb_issue_zeroout(sb, blk, num, GFP_NOFS);
  1168. if (ret < 0)
  1169. goto err_out;
  1170. if (barrier)
  1171. blkdev_issue_flush(sb->s_bdev, GFP_NOFS, NULL);
  1172. skip_zeroout:
  1173. ext4_lock_group(sb, group);
  1174. gdp->bg_flags |= cpu_to_le16(EXT4_BG_INODE_ZEROED);
  1175. gdp->bg_checksum = ext4_group_desc_csum(sbi, group, gdp);
  1176. ext4_unlock_group(sb, group);
  1177. BUFFER_TRACE(group_desc_bh,
  1178. "call ext4_handle_dirty_metadata");
  1179. ret = ext4_handle_dirty_metadata(handle, NULL,
  1180. group_desc_bh);
  1181. err_out:
  1182. up_write(&grp->alloc_sem);
  1183. ext4_journal_stop(handle);
  1184. out:
  1185. return ret;
  1186. }