ialloc.c 45 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * linux/fs/ext4/ialloc.c
  4. *
  5. * Copyright (C) 1992, 1993, 1994, 1995
  6. * Remy Card (card@masi.ibp.fr)
  7. * Laboratoire MASI - Institut Blaise Pascal
  8. * Universite Pierre et Marie Curie (Paris VI)
  9. *
  10. * BSD ufs-inspired inode and directory allocation by
  11. * Stephen Tweedie (sct@redhat.com), 1993
  12. * Big-endian to little-endian byte-swapping/bitmaps by
  13. * David S. Miller (davem@caip.rutgers.edu), 1995
  14. */
  15. #include <linux/time.h>
  16. #include <linux/fs.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 <linux/cred.h>
  25. #include <asm/byteorder.h>
  26. #include "ext4.h"
  27. #include "ext4_jbd2.h"
  28. #include "xattr.h"
  29. #include "acl.h"
  30. #include <trace/events/ext4.h>
  31. /*
  32. * ialloc.c contains the inodes allocation and deallocation routines
  33. */
  34. /*
  35. * The free inodes are managed by bitmaps. A file system contains several
  36. * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap
  37. * block for inodes, N blocks for the inode table and data blocks.
  38. *
  39. * The file system contains group descriptors which are located after the
  40. * super block. Each descriptor contains the number of the bitmap block and
  41. * the free blocks count in the block.
  42. */
  43. /*
  44. * To avoid calling the atomic setbit hundreds or thousands of times, we only
  45. * need to use it within a single byte (to ensure we get endianness right).
  46. * We can use memset for the rest of the bitmap as there are no other users.
  47. */
  48. void ext4_mark_bitmap_end(int start_bit, int end_bit, char *bitmap)
  49. {
  50. int i;
  51. if (start_bit >= end_bit)
  52. return;
  53. ext4_debug("mark end bits +%d through +%d used\n", start_bit, end_bit);
  54. for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
  55. ext4_set_bit(i, bitmap);
  56. if (i < end_bit)
  57. memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3);
  58. }
  59. void ext4_end_bitmap_read(struct buffer_head *bh, int uptodate)
  60. {
  61. if (uptodate) {
  62. set_buffer_uptodate(bh);
  63. set_bitmap_uptodate(bh);
  64. }
  65. unlock_buffer(bh);
  66. put_bh(bh);
  67. }
  68. static int ext4_validate_inode_bitmap(struct super_block *sb,
  69. struct ext4_group_desc *desc,
  70. ext4_group_t block_group,
  71. struct buffer_head *bh)
  72. {
  73. ext4_fsblk_t blk;
  74. struct ext4_group_info *grp;
  75. if (EXT4_SB(sb)->s_mount_state & EXT4_FC_REPLAY)
  76. return 0;
  77. grp = ext4_get_group_info(sb, block_group);
  78. if (buffer_verified(bh))
  79. return 0;
  80. if (EXT4_MB_GRP_IBITMAP_CORRUPT(grp))
  81. return -EFSCORRUPTED;
  82. ext4_lock_group(sb, block_group);
  83. if (buffer_verified(bh))
  84. goto verified;
  85. blk = ext4_inode_bitmap(sb, desc);
  86. if (!ext4_inode_bitmap_csum_verify(sb, block_group, desc, bh,
  87. EXT4_INODES_PER_GROUP(sb) / 8) ||
  88. ext4_simulate_fail(sb, EXT4_SIM_IBITMAP_CRC)) {
  89. ext4_unlock_group(sb, block_group);
  90. ext4_error(sb, "Corrupt inode bitmap - block_group = %u, "
  91. "inode_bitmap = %llu", block_group, blk);
  92. ext4_mark_group_bitmap_corrupted(sb, block_group,
  93. EXT4_GROUP_INFO_IBITMAP_CORRUPT);
  94. return -EFSBADCRC;
  95. }
  96. set_buffer_verified(bh);
  97. verified:
  98. ext4_unlock_group(sb, block_group);
  99. return 0;
  100. }
  101. /*
  102. * Read the inode allocation bitmap for a given block_group, reading
  103. * into the specified slot in the superblock's bitmap cache.
  104. *
  105. * Return buffer_head of bitmap on success, or an ERR_PTR on error.
  106. */
  107. static struct buffer_head *
  108. ext4_read_inode_bitmap(struct super_block *sb, ext4_group_t block_group)
  109. {
  110. struct ext4_group_desc *desc;
  111. struct ext4_sb_info *sbi = EXT4_SB(sb);
  112. struct buffer_head *bh = NULL;
  113. ext4_fsblk_t bitmap_blk;
  114. int err;
  115. desc = ext4_get_group_desc(sb, block_group, NULL);
  116. if (!desc)
  117. return ERR_PTR(-EFSCORRUPTED);
  118. bitmap_blk = ext4_inode_bitmap(sb, desc);
  119. if ((bitmap_blk <= le32_to_cpu(sbi->s_es->s_first_data_block)) ||
  120. (bitmap_blk >= ext4_blocks_count(sbi->s_es))) {
  121. ext4_error(sb, "Invalid inode bitmap blk %llu in "
  122. "block_group %u", bitmap_blk, block_group);
  123. ext4_mark_group_bitmap_corrupted(sb, block_group,
  124. EXT4_GROUP_INFO_IBITMAP_CORRUPT);
  125. return ERR_PTR(-EFSCORRUPTED);
  126. }
  127. bh = sb_getblk(sb, bitmap_blk);
  128. if (unlikely(!bh)) {
  129. ext4_warning(sb, "Cannot read inode bitmap - "
  130. "block_group = %u, inode_bitmap = %llu",
  131. block_group, bitmap_blk);
  132. return ERR_PTR(-ENOMEM);
  133. }
  134. if (bitmap_uptodate(bh))
  135. goto verify;
  136. lock_buffer(bh);
  137. if (bitmap_uptodate(bh)) {
  138. unlock_buffer(bh);
  139. goto verify;
  140. }
  141. ext4_lock_group(sb, block_group);
  142. if (ext4_has_group_desc_csum(sb) &&
  143. (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT))) {
  144. if (block_group == 0) {
  145. ext4_unlock_group(sb, block_group);
  146. unlock_buffer(bh);
  147. ext4_error(sb, "Inode bitmap for bg 0 marked "
  148. "uninitialized");
  149. err = -EFSCORRUPTED;
  150. goto out;
  151. }
  152. memset(bh->b_data, 0, (EXT4_INODES_PER_GROUP(sb) + 7) / 8);
  153. ext4_mark_bitmap_end(EXT4_INODES_PER_GROUP(sb),
  154. sb->s_blocksize * 8, bh->b_data);
  155. set_bitmap_uptodate(bh);
  156. set_buffer_uptodate(bh);
  157. set_buffer_verified(bh);
  158. ext4_unlock_group(sb, block_group);
  159. unlock_buffer(bh);
  160. return bh;
  161. }
  162. ext4_unlock_group(sb, block_group);
  163. if (buffer_uptodate(bh)) {
  164. /*
  165. * if not uninit if bh is uptodate,
  166. * bitmap is also uptodate
  167. */
  168. set_bitmap_uptodate(bh);
  169. unlock_buffer(bh);
  170. goto verify;
  171. }
  172. /*
  173. * submit the buffer_head for reading
  174. */
  175. trace_ext4_load_inode_bitmap(sb, block_group);
  176. ext4_read_bh(bh, REQ_META | REQ_PRIO, ext4_end_bitmap_read);
  177. ext4_simulate_fail_bh(sb, bh, EXT4_SIM_IBITMAP_EIO);
  178. if (!buffer_uptodate(bh)) {
  179. put_bh(bh);
  180. ext4_error_err(sb, EIO, "Cannot read inode bitmap - "
  181. "block_group = %u, inode_bitmap = %llu",
  182. block_group, bitmap_blk);
  183. ext4_mark_group_bitmap_corrupted(sb, block_group,
  184. EXT4_GROUP_INFO_IBITMAP_CORRUPT);
  185. return ERR_PTR(-EIO);
  186. }
  187. verify:
  188. err = ext4_validate_inode_bitmap(sb, desc, block_group, bh);
  189. if (err)
  190. goto out;
  191. return bh;
  192. out:
  193. put_bh(bh);
  194. return ERR_PTR(err);
  195. }
  196. /*
  197. * NOTE! When we get the inode, we're the only people
  198. * that have access to it, and as such there are no
  199. * race conditions we have to worry about. The inode
  200. * is not on the hash-lists, and it cannot be reached
  201. * through the filesystem because the directory entry
  202. * has been deleted earlier.
  203. *
  204. * HOWEVER: we must make sure that we get no aliases,
  205. * which means that we have to call "clear_inode()"
  206. * _before_ we mark the inode not in use in the inode
  207. * bitmaps. Otherwise a newly created file might use
  208. * the same inode number (not actually the same pointer
  209. * though), and then we'd have two inodes sharing the
  210. * same inode number and space on the harddisk.
  211. */
  212. void ext4_free_inode(handle_t *handle, struct inode *inode)
  213. {
  214. struct super_block *sb = inode->i_sb;
  215. int is_directory;
  216. unsigned long ino;
  217. struct buffer_head *bitmap_bh = NULL;
  218. struct buffer_head *bh2;
  219. ext4_group_t block_group;
  220. unsigned long bit;
  221. struct ext4_group_desc *gdp;
  222. struct ext4_super_block *es;
  223. struct ext4_sb_info *sbi;
  224. int fatal = 0, err, count, cleared;
  225. struct ext4_group_info *grp;
  226. if (!sb) {
  227. printk(KERN_ERR "EXT4-fs: %s:%d: inode on "
  228. "nonexistent device\n", __func__, __LINE__);
  229. return;
  230. }
  231. if (atomic_read(&inode->i_count) > 1) {
  232. ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: count=%d",
  233. __func__, __LINE__, inode->i_ino,
  234. atomic_read(&inode->i_count));
  235. return;
  236. }
  237. if (inode->i_nlink) {
  238. ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: nlink=%d\n",
  239. __func__, __LINE__, inode->i_ino, inode->i_nlink);
  240. return;
  241. }
  242. sbi = EXT4_SB(sb);
  243. ino = inode->i_ino;
  244. ext4_debug("freeing inode %lu\n", ino);
  245. trace_ext4_free_inode(inode);
  246. dquot_initialize(inode);
  247. dquot_free_inode(inode);
  248. is_directory = S_ISDIR(inode->i_mode);
  249. /* Do this BEFORE marking the inode not in use or returning an error */
  250. ext4_clear_inode(inode);
  251. es = sbi->s_es;
  252. if (ino < EXT4_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) {
  253. ext4_error(sb, "reserved or nonexistent inode %lu", ino);
  254. goto error_return;
  255. }
  256. block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
  257. bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
  258. bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
  259. /* Don't bother if the inode bitmap is corrupt. */
  260. if (IS_ERR(bitmap_bh)) {
  261. fatal = PTR_ERR(bitmap_bh);
  262. bitmap_bh = NULL;
  263. goto error_return;
  264. }
  265. if (!(sbi->s_mount_state & EXT4_FC_REPLAY)) {
  266. grp = ext4_get_group_info(sb, block_group);
  267. if (unlikely(EXT4_MB_GRP_IBITMAP_CORRUPT(grp))) {
  268. fatal = -EFSCORRUPTED;
  269. goto error_return;
  270. }
  271. }
  272. BUFFER_TRACE(bitmap_bh, "get_write_access");
  273. fatal = ext4_journal_get_write_access(handle, bitmap_bh);
  274. if (fatal)
  275. goto error_return;
  276. fatal = -ESRCH;
  277. gdp = ext4_get_group_desc(sb, block_group, &bh2);
  278. if (gdp) {
  279. BUFFER_TRACE(bh2, "get_write_access");
  280. fatal = ext4_journal_get_write_access(handle, bh2);
  281. }
  282. ext4_lock_group(sb, block_group);
  283. cleared = ext4_test_and_clear_bit(bit, bitmap_bh->b_data);
  284. if (fatal || !cleared) {
  285. ext4_unlock_group(sb, block_group);
  286. goto out;
  287. }
  288. count = ext4_free_inodes_count(sb, gdp) + 1;
  289. ext4_free_inodes_set(sb, gdp, count);
  290. if (is_directory) {
  291. count = ext4_used_dirs_count(sb, gdp) - 1;
  292. ext4_used_dirs_set(sb, gdp, count);
  293. if (percpu_counter_initialized(&sbi->s_dirs_counter))
  294. percpu_counter_dec(&sbi->s_dirs_counter);
  295. }
  296. ext4_inode_bitmap_csum_set(sb, block_group, gdp, bitmap_bh,
  297. EXT4_INODES_PER_GROUP(sb) / 8);
  298. ext4_group_desc_csum_set(sb, block_group, gdp);
  299. ext4_unlock_group(sb, block_group);
  300. if (percpu_counter_initialized(&sbi->s_freeinodes_counter))
  301. percpu_counter_inc(&sbi->s_freeinodes_counter);
  302. if (sbi->s_log_groups_per_flex) {
  303. struct flex_groups *fg;
  304. fg = sbi_array_rcu_deref(sbi, s_flex_groups,
  305. ext4_flex_group(sbi, block_group));
  306. atomic_inc(&fg->free_inodes);
  307. if (is_directory)
  308. atomic_dec(&fg->used_dirs);
  309. }
  310. BUFFER_TRACE(bh2, "call ext4_handle_dirty_metadata");
  311. fatal = ext4_handle_dirty_metadata(handle, NULL, bh2);
  312. out:
  313. if (cleared) {
  314. BUFFER_TRACE(bitmap_bh, "call ext4_handle_dirty_metadata");
  315. err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
  316. if (!fatal)
  317. fatal = err;
  318. } else {
  319. ext4_error(sb, "bit already cleared for inode %lu", ino);
  320. ext4_mark_group_bitmap_corrupted(sb, block_group,
  321. EXT4_GROUP_INFO_IBITMAP_CORRUPT);
  322. }
  323. error_return:
  324. brelse(bitmap_bh);
  325. ext4_std_error(sb, fatal);
  326. }
  327. struct orlov_stats {
  328. __u64 free_clusters;
  329. __u32 free_inodes;
  330. __u32 used_dirs;
  331. };
  332. /*
  333. * Helper function for Orlov's allocator; returns critical information
  334. * for a particular block group or flex_bg. If flex_size is 1, then g
  335. * is a block group number; otherwise it is flex_bg number.
  336. */
  337. static void get_orlov_stats(struct super_block *sb, ext4_group_t g,
  338. int flex_size, struct orlov_stats *stats)
  339. {
  340. struct ext4_group_desc *desc;
  341. if (flex_size > 1) {
  342. struct flex_groups *fg = sbi_array_rcu_deref(EXT4_SB(sb),
  343. s_flex_groups, g);
  344. stats->free_inodes = atomic_read(&fg->free_inodes);
  345. stats->free_clusters = atomic64_read(&fg->free_clusters);
  346. stats->used_dirs = atomic_read(&fg->used_dirs);
  347. return;
  348. }
  349. desc = ext4_get_group_desc(sb, g, NULL);
  350. if (desc) {
  351. stats->free_inodes = ext4_free_inodes_count(sb, desc);
  352. stats->free_clusters = ext4_free_group_clusters(sb, desc);
  353. stats->used_dirs = ext4_used_dirs_count(sb, desc);
  354. } else {
  355. stats->free_inodes = 0;
  356. stats->free_clusters = 0;
  357. stats->used_dirs = 0;
  358. }
  359. }
  360. /*
  361. * Orlov's allocator for directories.
  362. *
  363. * We always try to spread first-level directories.
  364. *
  365. * If there are blockgroups with both free inodes and free clusters counts
  366. * not worse than average we return one with smallest directory count.
  367. * Otherwise we simply return a random group.
  368. *
  369. * For the rest rules look so:
  370. *
  371. * It's OK to put directory into a group unless
  372. * it has too many directories already (max_dirs) or
  373. * it has too few free inodes left (min_inodes) or
  374. * it has too few free clusters left (min_clusters) or
  375. * Parent's group is preferred, if it doesn't satisfy these
  376. * conditions we search cyclically through the rest. If none
  377. * of the groups look good we just look for a group with more
  378. * free inodes than average (starting at parent's group).
  379. */
  380. static int find_group_orlov(struct super_block *sb, struct inode *parent,
  381. ext4_group_t *group, umode_t mode,
  382. const struct qstr *qstr)
  383. {
  384. ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
  385. struct ext4_sb_info *sbi = EXT4_SB(sb);
  386. ext4_group_t real_ngroups = ext4_get_groups_count(sb);
  387. int inodes_per_group = EXT4_INODES_PER_GROUP(sb);
  388. unsigned int freei, avefreei, grp_free;
  389. ext4_fsblk_t freec, avefreec;
  390. unsigned int ndirs;
  391. int max_dirs, min_inodes;
  392. ext4_grpblk_t min_clusters;
  393. ext4_group_t i, grp, g, ngroups;
  394. struct ext4_group_desc *desc;
  395. struct orlov_stats stats;
  396. int flex_size = ext4_flex_bg_size(sbi);
  397. struct dx_hash_info hinfo;
  398. ngroups = real_ngroups;
  399. if (flex_size > 1) {
  400. ngroups = (real_ngroups + flex_size - 1) >>
  401. sbi->s_log_groups_per_flex;
  402. parent_group >>= sbi->s_log_groups_per_flex;
  403. }
  404. freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
  405. avefreei = freei / ngroups;
  406. freec = percpu_counter_read_positive(&sbi->s_freeclusters_counter);
  407. avefreec = freec;
  408. do_div(avefreec, ngroups);
  409. ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);
  410. if (S_ISDIR(mode) &&
  411. ((parent == d_inode(sb->s_root)) ||
  412. (ext4_test_inode_flag(parent, EXT4_INODE_TOPDIR)))) {
  413. int best_ndir = inodes_per_group;
  414. int ret = -1;
  415. if (qstr) {
  416. if (ext4_hash_in_dirent(parent))
  417. hinfo.hash_version = DX_HASH_SIPHASH;
  418. else
  419. hinfo.hash_version = DX_HASH_HALF_MD4;
  420. hinfo.seed = sbi->s_hash_seed;
  421. ext4fs_dirhash(parent, qstr->name, qstr->len, &hinfo);
  422. grp = hinfo.hash;
  423. } else
  424. grp = prandom_u32();
  425. parent_group = (unsigned)grp % ngroups;
  426. for (i = 0; i < ngroups; i++) {
  427. g = (parent_group + i) % ngroups;
  428. get_orlov_stats(sb, g, flex_size, &stats);
  429. if (!stats.free_inodes)
  430. continue;
  431. if (stats.used_dirs >= best_ndir)
  432. continue;
  433. if (stats.free_inodes < avefreei)
  434. continue;
  435. if (stats.free_clusters < avefreec)
  436. continue;
  437. grp = g;
  438. ret = 0;
  439. best_ndir = stats.used_dirs;
  440. }
  441. if (ret)
  442. goto fallback;
  443. found_flex_bg:
  444. if (flex_size == 1) {
  445. *group = grp;
  446. return 0;
  447. }
  448. /*
  449. * We pack inodes at the beginning of the flexgroup's
  450. * inode tables. Block allocation decisions will do
  451. * something similar, although regular files will
  452. * start at 2nd block group of the flexgroup. See
  453. * ext4_ext_find_goal() and ext4_find_near().
  454. */
  455. grp *= flex_size;
  456. for (i = 0; i < flex_size; i++) {
  457. if (grp+i >= real_ngroups)
  458. break;
  459. desc = ext4_get_group_desc(sb, grp+i, NULL);
  460. if (desc && ext4_free_inodes_count(sb, desc)) {
  461. *group = grp+i;
  462. return 0;
  463. }
  464. }
  465. goto fallback;
  466. }
  467. max_dirs = ndirs / ngroups + inodes_per_group / 16;
  468. min_inodes = avefreei - inodes_per_group*flex_size / 4;
  469. if (min_inodes < 1)
  470. min_inodes = 1;
  471. min_clusters = avefreec - EXT4_CLUSTERS_PER_GROUP(sb)*flex_size / 4;
  472. /*
  473. * Start looking in the flex group where we last allocated an
  474. * inode for this parent directory
  475. */
  476. if (EXT4_I(parent)->i_last_alloc_group != ~0) {
  477. parent_group = EXT4_I(parent)->i_last_alloc_group;
  478. if (flex_size > 1)
  479. parent_group >>= sbi->s_log_groups_per_flex;
  480. }
  481. for (i = 0; i < ngroups; i++) {
  482. grp = (parent_group + i) % ngroups;
  483. get_orlov_stats(sb, grp, flex_size, &stats);
  484. if (stats.used_dirs >= max_dirs)
  485. continue;
  486. if (stats.free_inodes < min_inodes)
  487. continue;
  488. if (stats.free_clusters < min_clusters)
  489. continue;
  490. goto found_flex_bg;
  491. }
  492. fallback:
  493. ngroups = real_ngroups;
  494. avefreei = freei / ngroups;
  495. fallback_retry:
  496. parent_group = EXT4_I(parent)->i_block_group;
  497. for (i = 0; i < ngroups; i++) {
  498. grp = (parent_group + i) % ngroups;
  499. desc = ext4_get_group_desc(sb, grp, NULL);
  500. if (desc) {
  501. grp_free = ext4_free_inodes_count(sb, desc);
  502. if (grp_free && grp_free >= avefreei) {
  503. *group = grp;
  504. return 0;
  505. }
  506. }
  507. }
  508. if (avefreei) {
  509. /*
  510. * The free-inodes counter is approximate, and for really small
  511. * filesystems the above test can fail to find any blockgroups
  512. */
  513. avefreei = 0;
  514. goto fallback_retry;
  515. }
  516. return -1;
  517. }
  518. static int find_group_other(struct super_block *sb, struct inode *parent,
  519. ext4_group_t *group, umode_t mode)
  520. {
  521. ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
  522. ext4_group_t i, last, ngroups = ext4_get_groups_count(sb);
  523. struct ext4_group_desc *desc;
  524. int flex_size = ext4_flex_bg_size(EXT4_SB(sb));
  525. /*
  526. * Try to place the inode is the same flex group as its
  527. * parent. If we can't find space, use the Orlov algorithm to
  528. * find another flex group, and store that information in the
  529. * parent directory's inode information so that use that flex
  530. * group for future allocations.
  531. */
  532. if (flex_size > 1) {
  533. int retry = 0;
  534. try_again:
  535. parent_group &= ~(flex_size-1);
  536. last = parent_group + flex_size;
  537. if (last > ngroups)
  538. last = ngroups;
  539. for (i = parent_group; i < last; i++) {
  540. desc = ext4_get_group_desc(sb, i, NULL);
  541. if (desc && ext4_free_inodes_count(sb, desc)) {
  542. *group = i;
  543. return 0;
  544. }
  545. }
  546. if (!retry && EXT4_I(parent)->i_last_alloc_group != ~0) {
  547. retry = 1;
  548. parent_group = EXT4_I(parent)->i_last_alloc_group;
  549. goto try_again;
  550. }
  551. /*
  552. * If this didn't work, use the Orlov search algorithm
  553. * to find a new flex group; we pass in the mode to
  554. * avoid the topdir algorithms.
  555. */
  556. *group = parent_group + flex_size;
  557. if (*group > ngroups)
  558. *group = 0;
  559. return find_group_orlov(sb, parent, group, mode, NULL);
  560. }
  561. /*
  562. * Try to place the inode in its parent directory
  563. */
  564. *group = parent_group;
  565. desc = ext4_get_group_desc(sb, *group, NULL);
  566. if (desc && ext4_free_inodes_count(sb, desc) &&
  567. ext4_free_group_clusters(sb, desc))
  568. return 0;
  569. /*
  570. * We're going to place this inode in a different blockgroup from its
  571. * parent. We want to cause files in a common directory to all land in
  572. * the same blockgroup. But we want files which are in a different
  573. * directory which shares a blockgroup with our parent to land in a
  574. * different blockgroup.
  575. *
  576. * So add our directory's i_ino into the starting point for the hash.
  577. */
  578. *group = (*group + parent->i_ino) % ngroups;
  579. /*
  580. * Use a quadratic hash to find a group with a free inode and some free
  581. * blocks.
  582. */
  583. for (i = 1; i < ngroups; i <<= 1) {
  584. *group += i;
  585. if (*group >= ngroups)
  586. *group -= ngroups;
  587. desc = ext4_get_group_desc(sb, *group, NULL);
  588. if (desc && ext4_free_inodes_count(sb, desc) &&
  589. ext4_free_group_clusters(sb, desc))
  590. return 0;
  591. }
  592. /*
  593. * That failed: try linear search for a free inode, even if that group
  594. * has no free blocks.
  595. */
  596. *group = parent_group;
  597. for (i = 0; i < ngroups; i++) {
  598. if (++*group >= ngroups)
  599. *group = 0;
  600. desc = ext4_get_group_desc(sb, *group, NULL);
  601. if (desc && ext4_free_inodes_count(sb, desc))
  602. return 0;
  603. }
  604. return -1;
  605. }
  606. /*
  607. * In no journal mode, if an inode has recently been deleted, we want
  608. * to avoid reusing it until we're reasonably sure the inode table
  609. * block has been written back to disk. (Yes, these values are
  610. * somewhat arbitrary...)
  611. */
  612. #define RECENTCY_MIN 60
  613. #define RECENTCY_DIRTY 300
  614. static int recently_deleted(struct super_block *sb, ext4_group_t group, int ino)
  615. {
  616. struct ext4_group_desc *gdp;
  617. struct ext4_inode *raw_inode;
  618. struct buffer_head *bh;
  619. int inodes_per_block = EXT4_SB(sb)->s_inodes_per_block;
  620. int offset, ret = 0;
  621. int recentcy = RECENTCY_MIN;
  622. u32 dtime, now;
  623. gdp = ext4_get_group_desc(sb, group, NULL);
  624. if (unlikely(!gdp))
  625. return 0;
  626. bh = sb_find_get_block(sb, ext4_inode_table(sb, gdp) +
  627. (ino / inodes_per_block));
  628. if (!bh || !buffer_uptodate(bh))
  629. /*
  630. * If the block is not in the buffer cache, then it
  631. * must have been written out.
  632. */
  633. goto out;
  634. offset = (ino % inodes_per_block) * EXT4_INODE_SIZE(sb);
  635. raw_inode = (struct ext4_inode *) (bh->b_data + offset);
  636. /* i_dtime is only 32 bits on disk, but we only care about relative
  637. * times in the range of a few minutes (i.e. long enough to sync a
  638. * recently-deleted inode to disk), so using the low 32 bits of the
  639. * clock (a 68 year range) is enough, see time_before32() */
  640. dtime = le32_to_cpu(raw_inode->i_dtime);
  641. now = ktime_get_real_seconds();
  642. if (buffer_dirty(bh))
  643. recentcy += RECENTCY_DIRTY;
  644. if (dtime && time_before32(dtime, now) &&
  645. time_before32(now, dtime + recentcy))
  646. ret = 1;
  647. out:
  648. brelse(bh);
  649. return ret;
  650. }
  651. static int find_inode_bit(struct super_block *sb, ext4_group_t group,
  652. struct buffer_head *bitmap, unsigned long *ino)
  653. {
  654. bool check_recently_deleted = EXT4_SB(sb)->s_journal == NULL;
  655. unsigned long recently_deleted_ino = EXT4_INODES_PER_GROUP(sb);
  656. next:
  657. *ino = ext4_find_next_zero_bit((unsigned long *)
  658. bitmap->b_data,
  659. EXT4_INODES_PER_GROUP(sb), *ino);
  660. if (*ino >= EXT4_INODES_PER_GROUP(sb))
  661. goto not_found;
  662. if (check_recently_deleted && recently_deleted(sb, group, *ino)) {
  663. recently_deleted_ino = *ino;
  664. *ino = *ino + 1;
  665. if (*ino < EXT4_INODES_PER_GROUP(sb))
  666. goto next;
  667. goto not_found;
  668. }
  669. return 1;
  670. not_found:
  671. if (recently_deleted_ino >= EXT4_INODES_PER_GROUP(sb))
  672. return 0;
  673. /*
  674. * Not reusing recently deleted inodes is mostly a preference. We don't
  675. * want to report ENOSPC or skew allocation patterns because of that.
  676. * So return even recently deleted inode if we could find better in the
  677. * given range.
  678. */
  679. *ino = recently_deleted_ino;
  680. return 1;
  681. }
  682. int ext4_mark_inode_used(struct super_block *sb, int ino)
  683. {
  684. unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
  685. struct buffer_head *inode_bitmap_bh = NULL, *group_desc_bh = NULL;
  686. struct ext4_group_desc *gdp;
  687. ext4_group_t group;
  688. int bit;
  689. int err = -EFSCORRUPTED;
  690. if (ino < EXT4_FIRST_INO(sb) || ino > max_ino)
  691. goto out;
  692. group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
  693. bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
  694. inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
  695. if (IS_ERR(inode_bitmap_bh))
  696. return PTR_ERR(inode_bitmap_bh);
  697. if (ext4_test_bit(bit, inode_bitmap_bh->b_data)) {
  698. err = 0;
  699. goto out;
  700. }
  701. gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
  702. if (!gdp || !group_desc_bh) {
  703. err = -EINVAL;
  704. goto out;
  705. }
  706. ext4_set_bit(bit, inode_bitmap_bh->b_data);
  707. BUFFER_TRACE(inode_bitmap_bh, "call ext4_handle_dirty_metadata");
  708. err = ext4_handle_dirty_metadata(NULL, NULL, inode_bitmap_bh);
  709. if (err) {
  710. ext4_std_error(sb, err);
  711. goto out;
  712. }
  713. err = sync_dirty_buffer(inode_bitmap_bh);
  714. if (err) {
  715. ext4_std_error(sb, err);
  716. goto out;
  717. }
  718. /* We may have to initialize the block bitmap if it isn't already */
  719. if (ext4_has_group_desc_csum(sb) &&
  720. gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
  721. struct buffer_head *block_bitmap_bh;
  722. block_bitmap_bh = ext4_read_block_bitmap(sb, group);
  723. if (IS_ERR(block_bitmap_bh)) {
  724. err = PTR_ERR(block_bitmap_bh);
  725. goto out;
  726. }
  727. BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap");
  728. err = ext4_handle_dirty_metadata(NULL, NULL, block_bitmap_bh);
  729. sync_dirty_buffer(block_bitmap_bh);
  730. /* recheck and clear flag under lock if we still need to */
  731. ext4_lock_group(sb, group);
  732. if (ext4_has_group_desc_csum(sb) &&
  733. (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {
  734. gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
  735. ext4_free_group_clusters_set(sb, gdp,
  736. ext4_free_clusters_after_init(sb, group, gdp));
  737. ext4_block_bitmap_csum_set(sb, group, gdp,
  738. block_bitmap_bh);
  739. ext4_group_desc_csum_set(sb, group, gdp);
  740. }
  741. ext4_unlock_group(sb, group);
  742. brelse(block_bitmap_bh);
  743. if (err) {
  744. ext4_std_error(sb, err);
  745. goto out;
  746. }
  747. }
  748. /* Update the relevant bg descriptor fields */
  749. if (ext4_has_group_desc_csum(sb)) {
  750. int free;
  751. ext4_lock_group(sb, group); /* while we modify the bg desc */
  752. free = EXT4_INODES_PER_GROUP(sb) -
  753. ext4_itable_unused_count(sb, gdp);
  754. if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
  755. gdp->bg_flags &= cpu_to_le16(~EXT4_BG_INODE_UNINIT);
  756. free = 0;
  757. }
  758. /*
  759. * Check the relative inode number against the last used
  760. * relative inode number in this group. if it is greater
  761. * we need to update the bg_itable_unused count
  762. */
  763. if (bit >= free)
  764. ext4_itable_unused_set(sb, gdp,
  765. (EXT4_INODES_PER_GROUP(sb) - bit - 1));
  766. } else {
  767. ext4_lock_group(sb, group);
  768. }
  769. ext4_free_inodes_set(sb, gdp, ext4_free_inodes_count(sb, gdp) - 1);
  770. if (ext4_has_group_desc_csum(sb)) {
  771. ext4_inode_bitmap_csum_set(sb, group, gdp, inode_bitmap_bh,
  772. EXT4_INODES_PER_GROUP(sb) / 8);
  773. ext4_group_desc_csum_set(sb, group, gdp);
  774. }
  775. ext4_unlock_group(sb, group);
  776. err = ext4_handle_dirty_metadata(NULL, NULL, group_desc_bh);
  777. sync_dirty_buffer(group_desc_bh);
  778. out:
  779. return err;
  780. }
  781. static int ext4_xattr_credits_for_new_inode(struct inode *dir, mode_t mode,
  782. bool encrypt)
  783. {
  784. struct super_block *sb = dir->i_sb;
  785. int nblocks = 0;
  786. #ifdef CONFIG_EXT4_FS_POSIX_ACL
  787. struct posix_acl *p = get_acl(dir, ACL_TYPE_DEFAULT);
  788. if (IS_ERR(p))
  789. return PTR_ERR(p);
  790. if (p) {
  791. int acl_size = p->a_count * sizeof(ext4_acl_entry);
  792. nblocks += (S_ISDIR(mode) ? 2 : 1) *
  793. __ext4_xattr_set_credits(sb, NULL /* inode */,
  794. NULL /* block_bh */, acl_size,
  795. true /* is_create */);
  796. posix_acl_release(p);
  797. }
  798. #endif
  799. #ifdef CONFIG_SECURITY
  800. {
  801. int num_security_xattrs = 1;
  802. #ifdef CONFIG_INTEGRITY
  803. num_security_xattrs++;
  804. #endif
  805. /*
  806. * We assume that security xattrs are never more than 1k.
  807. * In practice they are under 128 bytes.
  808. */
  809. nblocks += num_security_xattrs *
  810. __ext4_xattr_set_credits(sb, NULL /* inode */,
  811. NULL /* block_bh */, 1024,
  812. true /* is_create */);
  813. }
  814. #endif
  815. if (encrypt)
  816. nblocks += __ext4_xattr_set_credits(sb,
  817. NULL /* inode */,
  818. NULL /* block_bh */,
  819. FSCRYPT_SET_CONTEXT_MAX_SIZE,
  820. true /* is_create */);
  821. return nblocks;
  822. }
  823. /*
  824. * There are two policies for allocating an inode. If the new inode is
  825. * a directory, then a forward search is made for a block group with both
  826. * free space and a low directory-to-inode ratio; if that fails, then of
  827. * the groups with above-average free space, that group with the fewest
  828. * directories already is chosen.
  829. *
  830. * For other inodes, search forward from the parent directory's block
  831. * group to find a free inode.
  832. */
  833. struct inode *__ext4_new_inode(handle_t *handle, struct inode *dir,
  834. umode_t mode, const struct qstr *qstr,
  835. __u32 goal, uid_t *owner, __u32 i_flags,
  836. int handle_type, unsigned int line_no,
  837. int nblocks)
  838. {
  839. struct super_block *sb;
  840. struct buffer_head *inode_bitmap_bh = NULL;
  841. struct buffer_head *group_desc_bh;
  842. ext4_group_t ngroups, group = 0;
  843. unsigned long ino = 0;
  844. struct inode *inode;
  845. struct ext4_group_desc *gdp = NULL;
  846. struct ext4_inode_info *ei;
  847. struct ext4_sb_info *sbi;
  848. int ret2, err;
  849. struct inode *ret;
  850. ext4_group_t i;
  851. ext4_group_t flex_group;
  852. struct ext4_group_info *grp = NULL;
  853. bool encrypt = false;
  854. /* Cannot create files in a deleted directory */
  855. if (!dir || !dir->i_nlink)
  856. return ERR_PTR(-EPERM);
  857. sb = dir->i_sb;
  858. sbi = EXT4_SB(sb);
  859. if (unlikely(ext4_forced_shutdown(sbi)))
  860. return ERR_PTR(-EIO);
  861. ngroups = ext4_get_groups_count(sb);
  862. trace_ext4_request_inode(dir, mode);
  863. inode = new_inode(sb);
  864. if (!inode)
  865. return ERR_PTR(-ENOMEM);
  866. ei = EXT4_I(inode);
  867. /*
  868. * Initialize owners and quota early so that we don't have to account
  869. * for quota initialization worst case in standard inode creating
  870. * transaction
  871. */
  872. if (owner) {
  873. inode->i_mode = mode;
  874. i_uid_write(inode, owner[0]);
  875. i_gid_write(inode, owner[1]);
  876. } else if (test_opt(sb, GRPID)) {
  877. inode->i_mode = mode;
  878. inode->i_uid = current_fsuid();
  879. inode->i_gid = dir->i_gid;
  880. } else
  881. inode_init_owner(inode, dir, mode);
  882. if (ext4_has_feature_project(sb) &&
  883. ext4_test_inode_flag(dir, EXT4_INODE_PROJINHERIT))
  884. ei->i_projid = EXT4_I(dir)->i_projid;
  885. else
  886. ei->i_projid = make_kprojid(&init_user_ns, EXT4_DEF_PROJID);
  887. if (!(i_flags & EXT4_EA_INODE_FL)) {
  888. err = fscrypt_prepare_new_inode(dir, inode, &encrypt);
  889. if (err)
  890. goto out;
  891. }
  892. err = dquot_initialize(inode);
  893. if (err)
  894. goto out;
  895. if (!handle && sbi->s_journal && !(i_flags & EXT4_EA_INODE_FL)) {
  896. ret2 = ext4_xattr_credits_for_new_inode(dir, mode, encrypt);
  897. if (ret2 < 0) {
  898. err = ret2;
  899. goto out;
  900. }
  901. nblocks += ret2;
  902. }
  903. if (!goal)
  904. goal = sbi->s_inode_goal;
  905. if (goal && goal <= le32_to_cpu(sbi->s_es->s_inodes_count)) {
  906. group = (goal - 1) / EXT4_INODES_PER_GROUP(sb);
  907. ino = (goal - 1) % EXT4_INODES_PER_GROUP(sb);
  908. ret2 = 0;
  909. goto got_group;
  910. }
  911. if (S_ISDIR(mode))
  912. ret2 = find_group_orlov(sb, dir, &group, mode, qstr);
  913. else
  914. ret2 = find_group_other(sb, dir, &group, mode);
  915. got_group:
  916. EXT4_I(dir)->i_last_alloc_group = group;
  917. err = -ENOSPC;
  918. if (ret2 == -1)
  919. goto out;
  920. /*
  921. * Normally we will only go through one pass of this loop,
  922. * unless we get unlucky and it turns out the group we selected
  923. * had its last inode grabbed by someone else.
  924. */
  925. for (i = 0; i < ngroups; i++, ino = 0) {
  926. err = -EIO;
  927. gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
  928. if (!gdp)
  929. goto out;
  930. /*
  931. * Check free inodes count before loading bitmap.
  932. */
  933. if (ext4_free_inodes_count(sb, gdp) == 0)
  934. goto next_group;
  935. if (!(sbi->s_mount_state & EXT4_FC_REPLAY)) {
  936. grp = ext4_get_group_info(sb, group);
  937. /*
  938. * Skip groups with already-known suspicious inode
  939. * tables
  940. */
  941. if (EXT4_MB_GRP_IBITMAP_CORRUPT(grp))
  942. goto next_group;
  943. }
  944. brelse(inode_bitmap_bh);
  945. inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
  946. /* Skip groups with suspicious inode tables */
  947. if (((!(sbi->s_mount_state & EXT4_FC_REPLAY))
  948. && EXT4_MB_GRP_IBITMAP_CORRUPT(grp)) ||
  949. IS_ERR(inode_bitmap_bh)) {
  950. inode_bitmap_bh = NULL;
  951. goto next_group;
  952. }
  953. repeat_in_this_group:
  954. ret2 = find_inode_bit(sb, group, inode_bitmap_bh, &ino);
  955. if (!ret2)
  956. goto next_group;
  957. if (group == 0 && (ino + 1) < EXT4_FIRST_INO(sb)) {
  958. ext4_error(sb, "reserved inode found cleared - "
  959. "inode=%lu", ino + 1);
  960. ext4_mark_group_bitmap_corrupted(sb, group,
  961. EXT4_GROUP_INFO_IBITMAP_CORRUPT);
  962. goto next_group;
  963. }
  964. if ((!(sbi->s_mount_state & EXT4_FC_REPLAY)) && !handle) {
  965. BUG_ON(nblocks <= 0);
  966. handle = __ext4_journal_start_sb(dir->i_sb, line_no,
  967. handle_type, nblocks, 0,
  968. ext4_trans_default_revoke_credits(sb));
  969. if (IS_ERR(handle)) {
  970. err = PTR_ERR(handle);
  971. ext4_std_error(sb, err);
  972. goto out;
  973. }
  974. }
  975. BUFFER_TRACE(inode_bitmap_bh, "get_write_access");
  976. err = ext4_journal_get_write_access(handle, inode_bitmap_bh);
  977. if (err) {
  978. ext4_std_error(sb, err);
  979. goto out;
  980. }
  981. ext4_lock_group(sb, group);
  982. ret2 = ext4_test_and_set_bit(ino, inode_bitmap_bh->b_data);
  983. if (ret2) {
  984. /* Someone already took the bit. Repeat the search
  985. * with lock held.
  986. */
  987. ret2 = find_inode_bit(sb, group, inode_bitmap_bh, &ino);
  988. if (ret2) {
  989. ext4_set_bit(ino, inode_bitmap_bh->b_data);
  990. ret2 = 0;
  991. } else {
  992. ret2 = 1; /* we didn't grab the inode */
  993. }
  994. }
  995. ext4_unlock_group(sb, group);
  996. ino++; /* the inode bitmap is zero-based */
  997. if (!ret2)
  998. goto got; /* we grabbed the inode! */
  999. if (ino < EXT4_INODES_PER_GROUP(sb))
  1000. goto repeat_in_this_group;
  1001. next_group:
  1002. if (++group == ngroups)
  1003. group = 0;
  1004. }
  1005. err = -ENOSPC;
  1006. goto out;
  1007. got:
  1008. BUFFER_TRACE(inode_bitmap_bh, "call ext4_handle_dirty_metadata");
  1009. err = ext4_handle_dirty_metadata(handle, NULL, inode_bitmap_bh);
  1010. if (err) {
  1011. ext4_std_error(sb, err);
  1012. goto out;
  1013. }
  1014. BUFFER_TRACE(group_desc_bh, "get_write_access");
  1015. err = ext4_journal_get_write_access(handle, group_desc_bh);
  1016. if (err) {
  1017. ext4_std_error(sb, err);
  1018. goto out;
  1019. }
  1020. /* We may have to initialize the block bitmap if it isn't already */
  1021. if (ext4_has_group_desc_csum(sb) &&
  1022. gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
  1023. struct buffer_head *block_bitmap_bh;
  1024. block_bitmap_bh = ext4_read_block_bitmap(sb, group);
  1025. if (IS_ERR(block_bitmap_bh)) {
  1026. err = PTR_ERR(block_bitmap_bh);
  1027. goto out;
  1028. }
  1029. BUFFER_TRACE(block_bitmap_bh, "get block bitmap access");
  1030. err = ext4_journal_get_write_access(handle, block_bitmap_bh);
  1031. if (err) {
  1032. brelse(block_bitmap_bh);
  1033. ext4_std_error(sb, err);
  1034. goto out;
  1035. }
  1036. BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap");
  1037. err = ext4_handle_dirty_metadata(handle, NULL, block_bitmap_bh);
  1038. /* recheck and clear flag under lock if we still need to */
  1039. ext4_lock_group(sb, group);
  1040. if (ext4_has_group_desc_csum(sb) &&
  1041. (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {
  1042. gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
  1043. ext4_free_group_clusters_set(sb, gdp,
  1044. ext4_free_clusters_after_init(sb, group, gdp));
  1045. ext4_block_bitmap_csum_set(sb, group, gdp,
  1046. block_bitmap_bh);
  1047. ext4_group_desc_csum_set(sb, group, gdp);
  1048. }
  1049. ext4_unlock_group(sb, group);
  1050. brelse(block_bitmap_bh);
  1051. if (err) {
  1052. ext4_std_error(sb, err);
  1053. goto out;
  1054. }
  1055. }
  1056. /* Update the relevant bg descriptor fields */
  1057. if (ext4_has_group_desc_csum(sb)) {
  1058. int free;
  1059. struct ext4_group_info *grp = NULL;
  1060. if (!(sbi->s_mount_state & EXT4_FC_REPLAY)) {
  1061. grp = ext4_get_group_info(sb, group);
  1062. down_read(&grp->alloc_sem); /*
  1063. * protect vs itable
  1064. * lazyinit
  1065. */
  1066. }
  1067. ext4_lock_group(sb, group); /* while we modify the bg desc */
  1068. free = EXT4_INODES_PER_GROUP(sb) -
  1069. ext4_itable_unused_count(sb, gdp);
  1070. if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
  1071. gdp->bg_flags &= cpu_to_le16(~EXT4_BG_INODE_UNINIT);
  1072. free = 0;
  1073. }
  1074. /*
  1075. * Check the relative inode number against the last used
  1076. * relative inode number in this group. if it is greater
  1077. * we need to update the bg_itable_unused count
  1078. */
  1079. if (ino > free)
  1080. ext4_itable_unused_set(sb, gdp,
  1081. (EXT4_INODES_PER_GROUP(sb) - ino));
  1082. if (!(sbi->s_mount_state & EXT4_FC_REPLAY))
  1083. up_read(&grp->alloc_sem);
  1084. } else {
  1085. ext4_lock_group(sb, group);
  1086. }
  1087. ext4_free_inodes_set(sb, gdp, ext4_free_inodes_count(sb, gdp) - 1);
  1088. if (S_ISDIR(mode)) {
  1089. ext4_used_dirs_set(sb, gdp, ext4_used_dirs_count(sb, gdp) + 1);
  1090. if (sbi->s_log_groups_per_flex) {
  1091. ext4_group_t f = ext4_flex_group(sbi, group);
  1092. atomic_inc(&sbi_array_rcu_deref(sbi, s_flex_groups,
  1093. f)->used_dirs);
  1094. }
  1095. }
  1096. if (ext4_has_group_desc_csum(sb)) {
  1097. ext4_inode_bitmap_csum_set(sb, group, gdp, inode_bitmap_bh,
  1098. EXT4_INODES_PER_GROUP(sb) / 8);
  1099. ext4_group_desc_csum_set(sb, group, gdp);
  1100. }
  1101. ext4_unlock_group(sb, group);
  1102. BUFFER_TRACE(group_desc_bh, "call ext4_handle_dirty_metadata");
  1103. err = ext4_handle_dirty_metadata(handle, NULL, group_desc_bh);
  1104. if (err) {
  1105. ext4_std_error(sb, err);
  1106. goto out;
  1107. }
  1108. percpu_counter_dec(&sbi->s_freeinodes_counter);
  1109. if (S_ISDIR(mode))
  1110. percpu_counter_inc(&sbi->s_dirs_counter);
  1111. if (sbi->s_log_groups_per_flex) {
  1112. flex_group = ext4_flex_group(sbi, group);
  1113. atomic_dec(&sbi_array_rcu_deref(sbi, s_flex_groups,
  1114. flex_group)->free_inodes);
  1115. }
  1116. inode->i_ino = ino + group * EXT4_INODES_PER_GROUP(sb);
  1117. /* This is the optimal IO size (for stat), not the fs block size */
  1118. inode->i_blocks = 0;
  1119. inode->i_mtime = inode->i_atime = inode->i_ctime = current_time(inode);
  1120. ei->i_crtime = inode->i_mtime;
  1121. memset(ei->i_data, 0, sizeof(ei->i_data));
  1122. ei->i_dir_start_lookup = 0;
  1123. ei->i_disksize = 0;
  1124. /* Don't inherit extent flag from directory, amongst others. */
  1125. ei->i_flags =
  1126. ext4_mask_flags(mode, EXT4_I(dir)->i_flags & EXT4_FL_INHERITED);
  1127. ei->i_flags |= i_flags;
  1128. ei->i_file_acl = 0;
  1129. ei->i_dtime = 0;
  1130. ei->i_block_group = group;
  1131. ei->i_last_alloc_group = ~0;
  1132. ext4_set_inode_flags(inode, true);
  1133. if (IS_DIRSYNC(inode))
  1134. ext4_handle_sync(handle);
  1135. if (insert_inode_locked(inode) < 0) {
  1136. /*
  1137. * Likely a bitmap corruption causing inode to be allocated
  1138. * twice.
  1139. */
  1140. err = -EIO;
  1141. ext4_error(sb, "failed to insert inode %lu: doubly allocated?",
  1142. inode->i_ino);
  1143. ext4_mark_group_bitmap_corrupted(sb, group,
  1144. EXT4_GROUP_INFO_IBITMAP_CORRUPT);
  1145. goto out;
  1146. }
  1147. inode->i_generation = prandom_u32();
  1148. /* Precompute checksum seed for inode metadata */
  1149. if (ext4_has_metadata_csum(sb)) {
  1150. __u32 csum;
  1151. __le32 inum = cpu_to_le32(inode->i_ino);
  1152. __le32 gen = cpu_to_le32(inode->i_generation);
  1153. csum = ext4_chksum(sbi, sbi->s_csum_seed, (__u8 *)&inum,
  1154. sizeof(inum));
  1155. ei->i_csum_seed = ext4_chksum(sbi, csum, (__u8 *)&gen,
  1156. sizeof(gen));
  1157. }
  1158. ext4_clear_state_flags(ei); /* Only relevant on 32-bit archs */
  1159. ext4_set_inode_state(inode, EXT4_STATE_NEW);
  1160. ei->i_extra_isize = sbi->s_want_extra_isize;
  1161. ei->i_inline_off = 0;
  1162. if (ext4_has_feature_inline_data(sb) &&
  1163. (!(ei->i_flags & EXT4_DAX_FL) || S_ISDIR(mode)))
  1164. ext4_set_inode_state(inode, EXT4_STATE_MAY_INLINE_DATA);
  1165. ret = inode;
  1166. err = dquot_alloc_inode(inode);
  1167. if (err)
  1168. goto fail_drop;
  1169. /*
  1170. * Since the encryption xattr will always be unique, create it first so
  1171. * that it's less likely to end up in an external xattr block and
  1172. * prevent its deduplication.
  1173. */
  1174. if (encrypt) {
  1175. err = fscrypt_set_context(inode, handle);
  1176. if (err)
  1177. goto fail_free_drop;
  1178. }
  1179. if (!(ei->i_flags & EXT4_EA_INODE_FL)) {
  1180. err = ext4_init_acl(handle, inode, dir);
  1181. if (err)
  1182. goto fail_free_drop;
  1183. err = ext4_init_security(handle, inode, dir, qstr);
  1184. if (err)
  1185. goto fail_free_drop;
  1186. }
  1187. if (ext4_has_feature_extents(sb)) {
  1188. /* set extent flag only for directory, file and normal symlink*/
  1189. if (S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) {
  1190. ext4_set_inode_flag(inode, EXT4_INODE_EXTENTS);
  1191. ext4_ext_tree_init(handle, inode);
  1192. }
  1193. }
  1194. if (ext4_handle_valid(handle)) {
  1195. ei->i_sync_tid = handle->h_transaction->t_tid;
  1196. ei->i_datasync_tid = handle->h_transaction->t_tid;
  1197. }
  1198. err = ext4_mark_inode_dirty(handle, inode);
  1199. if (err) {
  1200. ext4_std_error(sb, err);
  1201. goto fail_free_drop;
  1202. }
  1203. ext4_debug("allocating inode %lu\n", inode->i_ino);
  1204. trace_ext4_allocate_inode(inode, dir, mode);
  1205. brelse(inode_bitmap_bh);
  1206. return ret;
  1207. fail_free_drop:
  1208. dquot_free_inode(inode);
  1209. fail_drop:
  1210. clear_nlink(inode);
  1211. unlock_new_inode(inode);
  1212. out:
  1213. dquot_drop(inode);
  1214. inode->i_flags |= S_NOQUOTA;
  1215. iput(inode);
  1216. brelse(inode_bitmap_bh);
  1217. return ERR_PTR(err);
  1218. }
  1219. /* Verify that we are loading a valid orphan from disk */
  1220. struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
  1221. {
  1222. unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
  1223. ext4_group_t block_group;
  1224. int bit;
  1225. struct buffer_head *bitmap_bh = NULL;
  1226. struct inode *inode = NULL;
  1227. int err = -EFSCORRUPTED;
  1228. if (ino < EXT4_FIRST_INO(sb) || ino > max_ino)
  1229. goto bad_orphan;
  1230. block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
  1231. bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
  1232. bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
  1233. if (IS_ERR(bitmap_bh))
  1234. return ERR_CAST(bitmap_bh);
  1235. /* Having the inode bit set should be a 100% indicator that this
  1236. * is a valid orphan (no e2fsck run on fs). Orphans also include
  1237. * inodes that were being truncated, so we can't check i_nlink==0.
  1238. */
  1239. if (!ext4_test_bit(bit, bitmap_bh->b_data))
  1240. goto bad_orphan;
  1241. inode = ext4_iget(sb, ino, EXT4_IGET_NORMAL);
  1242. if (IS_ERR(inode)) {
  1243. err = PTR_ERR(inode);
  1244. ext4_error_err(sb, -err,
  1245. "couldn't read orphan inode %lu (err %d)",
  1246. ino, err);
  1247. brelse(bitmap_bh);
  1248. return inode;
  1249. }
  1250. /*
  1251. * If the orphans has i_nlinks > 0 then it should be able to
  1252. * be truncated, otherwise it won't be removed from the orphan
  1253. * list during processing and an infinite loop will result.
  1254. * Similarly, it must not be a bad inode.
  1255. */
  1256. if ((inode->i_nlink && !ext4_can_truncate(inode)) ||
  1257. is_bad_inode(inode))
  1258. goto bad_orphan;
  1259. if (NEXT_ORPHAN(inode) > max_ino)
  1260. goto bad_orphan;
  1261. brelse(bitmap_bh);
  1262. return inode;
  1263. bad_orphan:
  1264. ext4_error(sb, "bad orphan inode %lu", ino);
  1265. if (bitmap_bh)
  1266. printk(KERN_ERR "ext4_test_bit(bit=%d, block=%llu) = %d\n",
  1267. bit, (unsigned long long)bitmap_bh->b_blocknr,
  1268. ext4_test_bit(bit, bitmap_bh->b_data));
  1269. if (inode) {
  1270. printk(KERN_ERR "is_bad_inode(inode)=%d\n",
  1271. is_bad_inode(inode));
  1272. printk(KERN_ERR "NEXT_ORPHAN(inode)=%u\n",
  1273. NEXT_ORPHAN(inode));
  1274. printk(KERN_ERR "max_ino=%lu\n", max_ino);
  1275. printk(KERN_ERR "i_nlink=%u\n", inode->i_nlink);
  1276. /* Avoid freeing blocks if we got a bad deleted inode */
  1277. if (inode->i_nlink == 0)
  1278. inode->i_blocks = 0;
  1279. iput(inode);
  1280. }
  1281. brelse(bitmap_bh);
  1282. return ERR_PTR(err);
  1283. }
  1284. unsigned long ext4_count_free_inodes(struct super_block *sb)
  1285. {
  1286. unsigned long desc_count;
  1287. struct ext4_group_desc *gdp;
  1288. ext4_group_t i, ngroups = ext4_get_groups_count(sb);
  1289. #ifdef EXT4FS_DEBUG
  1290. struct ext4_super_block *es;
  1291. unsigned long bitmap_count, x;
  1292. struct buffer_head *bitmap_bh = NULL;
  1293. es = EXT4_SB(sb)->s_es;
  1294. desc_count = 0;
  1295. bitmap_count = 0;
  1296. gdp = NULL;
  1297. for (i = 0; i < ngroups; i++) {
  1298. gdp = ext4_get_group_desc(sb, i, NULL);
  1299. if (!gdp)
  1300. continue;
  1301. desc_count += ext4_free_inodes_count(sb, gdp);
  1302. brelse(bitmap_bh);
  1303. bitmap_bh = ext4_read_inode_bitmap(sb, i);
  1304. if (IS_ERR(bitmap_bh)) {
  1305. bitmap_bh = NULL;
  1306. continue;
  1307. }
  1308. x = ext4_count_free(bitmap_bh->b_data,
  1309. EXT4_INODES_PER_GROUP(sb) / 8);
  1310. printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
  1311. (unsigned long) i, ext4_free_inodes_count(sb, gdp), x);
  1312. bitmap_count += x;
  1313. }
  1314. brelse(bitmap_bh);
  1315. printk(KERN_DEBUG "ext4_count_free_inodes: "
  1316. "stored = %u, computed = %lu, %lu\n",
  1317. le32_to_cpu(es->s_free_inodes_count), desc_count, bitmap_count);
  1318. return desc_count;
  1319. #else
  1320. desc_count = 0;
  1321. for (i = 0; i < ngroups; i++) {
  1322. gdp = ext4_get_group_desc(sb, i, NULL);
  1323. if (!gdp)
  1324. continue;
  1325. desc_count += ext4_free_inodes_count(sb, gdp);
  1326. cond_resched();
  1327. }
  1328. return desc_count;
  1329. #endif
  1330. }
  1331. /* Called at mount-time, super-block is locked */
  1332. unsigned long ext4_count_dirs(struct super_block * sb)
  1333. {
  1334. unsigned long count = 0;
  1335. ext4_group_t i, ngroups = ext4_get_groups_count(sb);
  1336. for (i = 0; i < ngroups; i++) {
  1337. struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL);
  1338. if (!gdp)
  1339. continue;
  1340. count += ext4_used_dirs_count(sb, gdp);
  1341. }
  1342. return count;
  1343. }
  1344. /*
  1345. * Zeroes not yet zeroed inode table - just write zeroes through the whole
  1346. * inode table. Must be called without any spinlock held. The only place
  1347. * where it is called from on active part of filesystem is ext4lazyinit
  1348. * thread, so we do not need any special locks, however we have to prevent
  1349. * inode allocation from the current group, so we take alloc_sem lock, to
  1350. * block ext4_new_inode() until we are finished.
  1351. */
  1352. int ext4_init_inode_table(struct super_block *sb, ext4_group_t group,
  1353. int barrier)
  1354. {
  1355. struct ext4_group_info *grp = ext4_get_group_info(sb, group);
  1356. struct ext4_sb_info *sbi = EXT4_SB(sb);
  1357. struct ext4_group_desc *gdp = NULL;
  1358. struct buffer_head *group_desc_bh;
  1359. handle_t *handle;
  1360. ext4_fsblk_t blk;
  1361. int num, ret = 0, used_blks = 0;
  1362. unsigned long used_inos = 0;
  1363. /* This should not happen, but just to be sure check this */
  1364. if (sb_rdonly(sb)) {
  1365. ret = 1;
  1366. goto out;
  1367. }
  1368. gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
  1369. if (!gdp)
  1370. goto out;
  1371. /*
  1372. * We do not need to lock this, because we are the only one
  1373. * handling this flag.
  1374. */
  1375. if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_ZEROED))
  1376. goto out;
  1377. handle = ext4_journal_start_sb(sb, EXT4_HT_MISC, 1);
  1378. if (IS_ERR(handle)) {
  1379. ret = PTR_ERR(handle);
  1380. goto out;
  1381. }
  1382. down_write(&grp->alloc_sem);
  1383. /*
  1384. * If inode bitmap was already initialized there may be some
  1385. * used inodes so we need to skip blocks with used inodes in
  1386. * inode table.
  1387. */
  1388. if (!(gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT))) {
  1389. used_inos = EXT4_INODES_PER_GROUP(sb) -
  1390. ext4_itable_unused_count(sb, gdp);
  1391. used_blks = DIV_ROUND_UP(used_inos, sbi->s_inodes_per_block);
  1392. /* Bogus inode unused count? */
  1393. if (used_blks < 0 || used_blks > sbi->s_itb_per_group) {
  1394. ext4_error(sb, "Something is wrong with group %u: "
  1395. "used itable blocks: %d; "
  1396. "itable unused count: %u",
  1397. group, used_blks,
  1398. ext4_itable_unused_count(sb, gdp));
  1399. ret = 1;
  1400. goto err_out;
  1401. }
  1402. used_inos += group * EXT4_INODES_PER_GROUP(sb);
  1403. /*
  1404. * Are there some uninitialized inodes in the inode table
  1405. * before the first normal inode?
  1406. */
  1407. if ((used_blks != sbi->s_itb_per_group) &&
  1408. (used_inos < EXT4_FIRST_INO(sb))) {
  1409. ext4_error(sb, "Something is wrong with group %u: "
  1410. "itable unused count: %u; "
  1411. "itables initialized count: %ld",
  1412. group, ext4_itable_unused_count(sb, gdp),
  1413. used_inos);
  1414. ret = 1;
  1415. goto err_out;
  1416. }
  1417. }
  1418. blk = ext4_inode_table(sb, gdp) + used_blks;
  1419. num = sbi->s_itb_per_group - used_blks;
  1420. BUFFER_TRACE(group_desc_bh, "get_write_access");
  1421. ret = ext4_journal_get_write_access(handle,
  1422. group_desc_bh);
  1423. if (ret)
  1424. goto err_out;
  1425. /*
  1426. * Skip zeroout if the inode table is full. But we set the ZEROED
  1427. * flag anyway, because obviously, when it is full it does not need
  1428. * further zeroing.
  1429. */
  1430. if (unlikely(num == 0))
  1431. goto skip_zeroout;
  1432. ext4_debug("going to zero out inode table in group %d\n",
  1433. group);
  1434. ret = sb_issue_zeroout(sb, blk, num, GFP_NOFS);
  1435. if (ret < 0)
  1436. goto err_out;
  1437. if (barrier)
  1438. blkdev_issue_flush(sb->s_bdev, GFP_NOFS);
  1439. skip_zeroout:
  1440. ext4_lock_group(sb, group);
  1441. gdp->bg_flags |= cpu_to_le16(EXT4_BG_INODE_ZEROED);
  1442. ext4_group_desc_csum_set(sb, group, gdp);
  1443. ext4_unlock_group(sb, group);
  1444. BUFFER_TRACE(group_desc_bh,
  1445. "call ext4_handle_dirty_metadata");
  1446. ret = ext4_handle_dirty_metadata(handle, NULL,
  1447. group_desc_bh);
  1448. err_out:
  1449. up_write(&grp->alloc_sem);
  1450. ext4_journal_stop(handle);
  1451. out:
  1452. return ret;
  1453. }