balloc.c 54 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868
  1. /*
  2. * linux/fs/ext4/balloc.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. * Enhanced block allocation by Stephen Tweedie (sct@redhat.com), 1993
  10. * Big-endian to little-endian byte-swapping/bitmaps by
  11. * David S. Miller (davem@caip.rutgers.edu), 1995
  12. */
  13. #include <linux/time.h>
  14. #include <linux/capability.h>
  15. #include <linux/fs.h>
  16. #include <linux/jbd2.h>
  17. #include <linux/ext4_fs.h>
  18. #include <linux/ext4_jbd2.h>
  19. #include <linux/quotaops.h>
  20. #include <linux/buffer_head.h>
  21. /*
  22. * balloc.c contains the blocks allocation and deallocation routines
  23. */
  24. /*
  25. * Calculate the block group number and offset, given a block number
  26. */
  27. void ext4_get_group_no_and_offset(struct super_block *sb, ext4_fsblk_t blocknr,
  28. unsigned long *blockgrpp, ext4_grpblk_t *offsetp)
  29. {
  30. struct ext4_super_block *es = EXT4_SB(sb)->s_es;
  31. ext4_grpblk_t offset;
  32. blocknr = blocknr - le32_to_cpu(es->s_first_data_block);
  33. offset = do_div(blocknr, EXT4_BLOCKS_PER_GROUP(sb));
  34. if (offsetp)
  35. *offsetp = offset;
  36. if (blockgrpp)
  37. *blockgrpp = blocknr;
  38. }
  39. /*
  40. * The free blocks are managed by bitmaps. A file system contains several
  41. * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap
  42. * block for inodes, N blocks for the inode table and data blocks.
  43. *
  44. * The file system contains group descriptors which are located after the
  45. * super block. Each descriptor contains the number of the bitmap block and
  46. * the free blocks count in the block. The descriptors are loaded in memory
  47. * when a file system is mounted (see ext4_fill_super).
  48. */
  49. #define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
  50. /**
  51. * ext4_get_group_desc() -- load group descriptor from disk
  52. * @sb: super block
  53. * @block_group: given block group
  54. * @bh: pointer to the buffer head to store the block
  55. * group descriptor
  56. */
  57. struct ext4_group_desc * ext4_get_group_desc(struct super_block * sb,
  58. unsigned int block_group,
  59. struct buffer_head ** bh)
  60. {
  61. unsigned long group_desc;
  62. unsigned long offset;
  63. struct ext4_group_desc * desc;
  64. struct ext4_sb_info *sbi = EXT4_SB(sb);
  65. if (block_group >= sbi->s_groups_count) {
  66. ext4_error (sb, "ext4_get_group_desc",
  67. "block_group >= groups_count - "
  68. "block_group = %d, groups_count = %lu",
  69. block_group, sbi->s_groups_count);
  70. return NULL;
  71. }
  72. smp_rmb();
  73. group_desc = block_group >> EXT4_DESC_PER_BLOCK_BITS(sb);
  74. offset = block_group & (EXT4_DESC_PER_BLOCK(sb) - 1);
  75. if (!sbi->s_group_desc[group_desc]) {
  76. ext4_error (sb, "ext4_get_group_desc",
  77. "Group descriptor not loaded - "
  78. "block_group = %d, group_desc = %lu, desc = %lu",
  79. block_group, group_desc, offset);
  80. return NULL;
  81. }
  82. desc = (struct ext4_group_desc *)(
  83. (__u8 *)sbi->s_group_desc[group_desc]->b_data +
  84. offset * EXT4_DESC_SIZE(sb));
  85. if (bh)
  86. *bh = sbi->s_group_desc[group_desc];
  87. return desc;
  88. }
  89. static inline int
  90. block_in_use(ext4_fsblk_t block, struct super_block *sb, unsigned char *map)
  91. {
  92. ext4_grpblk_t offset;
  93. ext4_get_group_no_and_offset(sb, block, NULL, &offset);
  94. return ext4_test_bit (offset, map);
  95. }
  96. /**
  97. * read_block_bitmap()
  98. * @sb: super block
  99. * @block_group: given block group
  100. *
  101. * Read the bitmap for a given block_group, reading into the specified
  102. * slot in the superblock's bitmap cache.
  103. *
  104. * Return buffer_head on success or NULL in case of failure.
  105. */
  106. static struct buffer_head *
  107. read_block_bitmap(struct super_block *sb, unsigned int block_group)
  108. {
  109. int i;
  110. struct ext4_group_desc * desc;
  111. struct buffer_head * bh = NULL;
  112. ext4_fsblk_t bitmap_blk;
  113. desc = ext4_get_group_desc (sb, block_group, NULL);
  114. if (!desc)
  115. return NULL;
  116. bitmap_blk = ext4_block_bitmap(sb, desc);
  117. bh = sb_bread(sb, bitmap_blk);
  118. if (!bh)
  119. ext4_error (sb, __FUNCTION__,
  120. "Cannot read block bitmap - "
  121. "block_group = %d, block_bitmap = %llu",
  122. block_group, bitmap_blk);
  123. /* check whether block bitmap block number is set */
  124. if (!block_in_use(bitmap_blk, sb, bh->b_data)) {
  125. /* bad block bitmap */
  126. goto error_out;
  127. }
  128. /* check whether the inode bitmap block number is set */
  129. bitmap_blk = ext4_inode_bitmap(sb, desc);
  130. if (!block_in_use(bitmap_blk, sb, bh->b_data)) {
  131. /* bad block bitmap */
  132. goto error_out;
  133. }
  134. /* check whether the inode table block number is set */
  135. bitmap_blk = ext4_inode_table(sb, desc);
  136. for (i = 0; i < EXT4_SB(sb)->s_itb_per_group; i++, bitmap_blk++) {
  137. if (!block_in_use(bitmap_blk, sb, bh->b_data)) {
  138. /* bad block bitmap */
  139. goto error_out;
  140. }
  141. }
  142. return bh;
  143. error_out:
  144. brelse(bh);
  145. ext4_error(sb, __FUNCTION__,
  146. "Invalid block bitmap - "
  147. "block_group = %d, block = %llu",
  148. block_group, bitmap_blk);
  149. return NULL;
  150. }
  151. /*
  152. * The reservation window structure operations
  153. * --------------------------------------------
  154. * Operations include:
  155. * dump, find, add, remove, is_empty, find_next_reservable_window, etc.
  156. *
  157. * We use a red-black tree to represent per-filesystem reservation
  158. * windows.
  159. *
  160. */
  161. /**
  162. * __rsv_window_dump() -- Dump the filesystem block allocation reservation map
  163. * @rb_root: root of per-filesystem reservation rb tree
  164. * @verbose: verbose mode
  165. * @fn: function which wishes to dump the reservation map
  166. *
  167. * If verbose is turned on, it will print the whole block reservation
  168. * windows(start, end). Otherwise, it will only print out the "bad" windows,
  169. * those windows that overlap with their immediate neighbors.
  170. */
  171. #if 1
  172. static void __rsv_window_dump(struct rb_root *root, int verbose,
  173. const char *fn)
  174. {
  175. struct rb_node *n;
  176. struct ext4_reserve_window_node *rsv, *prev;
  177. int bad;
  178. restart:
  179. n = rb_first(root);
  180. bad = 0;
  181. prev = NULL;
  182. printk("Block Allocation Reservation Windows Map (%s):\n", fn);
  183. while (n) {
  184. rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
  185. if (verbose)
  186. printk("reservation window 0x%p "
  187. "start: %llu, end: %llu\n",
  188. rsv, rsv->rsv_start, rsv->rsv_end);
  189. if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) {
  190. printk("Bad reservation %p (start >= end)\n",
  191. rsv);
  192. bad = 1;
  193. }
  194. if (prev && prev->rsv_end >= rsv->rsv_start) {
  195. printk("Bad reservation %p (prev->end >= start)\n",
  196. rsv);
  197. bad = 1;
  198. }
  199. if (bad) {
  200. if (!verbose) {
  201. printk("Restarting reservation walk in verbose mode\n");
  202. verbose = 1;
  203. goto restart;
  204. }
  205. }
  206. n = rb_next(n);
  207. prev = rsv;
  208. }
  209. printk("Window map complete.\n");
  210. if (bad)
  211. BUG();
  212. }
  213. #define rsv_window_dump(root, verbose) \
  214. __rsv_window_dump((root), (verbose), __FUNCTION__)
  215. #else
  216. #define rsv_window_dump(root, verbose) do {} while (0)
  217. #endif
  218. /**
  219. * goal_in_my_reservation()
  220. * @rsv: inode's reservation window
  221. * @grp_goal: given goal block relative to the allocation block group
  222. * @group: the current allocation block group
  223. * @sb: filesystem super block
  224. *
  225. * Test if the given goal block (group relative) is within the file's
  226. * own block reservation window range.
  227. *
  228. * If the reservation window is outside the goal allocation group, return 0;
  229. * grp_goal (given goal block) could be -1, which means no specific
  230. * goal block. In this case, always return 1.
  231. * If the goal block is within the reservation window, return 1;
  232. * otherwise, return 0;
  233. */
  234. static int
  235. goal_in_my_reservation(struct ext4_reserve_window *rsv, ext4_grpblk_t grp_goal,
  236. unsigned int group, struct super_block * sb)
  237. {
  238. ext4_fsblk_t group_first_block, group_last_block;
  239. group_first_block = ext4_group_first_block_no(sb, group);
  240. group_last_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
  241. if ((rsv->_rsv_start > group_last_block) ||
  242. (rsv->_rsv_end < group_first_block))
  243. return 0;
  244. if ((grp_goal >= 0) && ((grp_goal + group_first_block < rsv->_rsv_start)
  245. || (grp_goal + group_first_block > rsv->_rsv_end)))
  246. return 0;
  247. return 1;
  248. }
  249. /**
  250. * search_reserve_window()
  251. * @rb_root: root of reservation tree
  252. * @goal: target allocation block
  253. *
  254. * Find the reserved window which includes the goal, or the previous one
  255. * if the goal is not in any window.
  256. * Returns NULL if there are no windows or if all windows start after the goal.
  257. */
  258. static struct ext4_reserve_window_node *
  259. search_reserve_window(struct rb_root *root, ext4_fsblk_t goal)
  260. {
  261. struct rb_node *n = root->rb_node;
  262. struct ext4_reserve_window_node *rsv;
  263. if (!n)
  264. return NULL;
  265. do {
  266. rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
  267. if (goal < rsv->rsv_start)
  268. n = n->rb_left;
  269. else if (goal > rsv->rsv_end)
  270. n = n->rb_right;
  271. else
  272. return rsv;
  273. } while (n);
  274. /*
  275. * We've fallen off the end of the tree: the goal wasn't inside
  276. * any particular node. OK, the previous node must be to one
  277. * side of the interval containing the goal. If it's the RHS,
  278. * we need to back up one.
  279. */
  280. if (rsv->rsv_start > goal) {
  281. n = rb_prev(&rsv->rsv_node);
  282. rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
  283. }
  284. return rsv;
  285. }
  286. /**
  287. * ext4_rsv_window_add() -- Insert a window to the block reservation rb tree.
  288. * @sb: super block
  289. * @rsv: reservation window to add
  290. *
  291. * Must be called with rsv_lock hold.
  292. */
  293. void ext4_rsv_window_add(struct super_block *sb,
  294. struct ext4_reserve_window_node *rsv)
  295. {
  296. struct rb_root *root = &EXT4_SB(sb)->s_rsv_window_root;
  297. struct rb_node *node = &rsv->rsv_node;
  298. ext4_fsblk_t start = rsv->rsv_start;
  299. struct rb_node ** p = &root->rb_node;
  300. struct rb_node * parent = NULL;
  301. struct ext4_reserve_window_node *this;
  302. while (*p)
  303. {
  304. parent = *p;
  305. this = rb_entry(parent, struct ext4_reserve_window_node, rsv_node);
  306. if (start < this->rsv_start)
  307. p = &(*p)->rb_left;
  308. else if (start > this->rsv_end)
  309. p = &(*p)->rb_right;
  310. else {
  311. rsv_window_dump(root, 1);
  312. BUG();
  313. }
  314. }
  315. rb_link_node(node, parent, p);
  316. rb_insert_color(node, root);
  317. }
  318. /**
  319. * ext4_rsv_window_remove() -- unlink a window from the reservation rb tree
  320. * @sb: super block
  321. * @rsv: reservation window to remove
  322. *
  323. * Mark the block reservation window as not allocated, and unlink it
  324. * from the filesystem reservation window rb tree. Must be called with
  325. * rsv_lock hold.
  326. */
  327. static void rsv_window_remove(struct super_block *sb,
  328. struct ext4_reserve_window_node *rsv)
  329. {
  330. rsv->rsv_start = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
  331. rsv->rsv_end = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
  332. rsv->rsv_alloc_hit = 0;
  333. rb_erase(&rsv->rsv_node, &EXT4_SB(sb)->s_rsv_window_root);
  334. }
  335. /*
  336. * rsv_is_empty() -- Check if the reservation window is allocated.
  337. * @rsv: given reservation window to check
  338. *
  339. * returns 1 if the end block is EXT4_RESERVE_WINDOW_NOT_ALLOCATED.
  340. */
  341. static inline int rsv_is_empty(struct ext4_reserve_window *rsv)
  342. {
  343. /* a valid reservation end block could not be 0 */
  344. return rsv->_rsv_end == EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
  345. }
  346. /**
  347. * ext4_init_block_alloc_info()
  348. * @inode: file inode structure
  349. *
  350. * Allocate and initialize the reservation window structure, and
  351. * link the window to the ext4 inode structure at last
  352. *
  353. * The reservation window structure is only dynamically allocated
  354. * and linked to ext4 inode the first time the open file
  355. * needs a new block. So, before every ext4_new_block(s) call, for
  356. * regular files, we should check whether the reservation window
  357. * structure exists or not. In the latter case, this function is called.
  358. * Fail to do so will result in block reservation being turned off for that
  359. * open file.
  360. *
  361. * This function is called from ext4_get_blocks_handle(), also called
  362. * when setting the reservation window size through ioctl before the file
  363. * is open for write (needs block allocation).
  364. *
  365. * Needs truncate_mutex protection prior to call this function.
  366. */
  367. void ext4_init_block_alloc_info(struct inode *inode)
  368. {
  369. struct ext4_inode_info *ei = EXT4_I(inode);
  370. struct ext4_block_alloc_info *block_i = ei->i_block_alloc_info;
  371. struct super_block *sb = inode->i_sb;
  372. block_i = kmalloc(sizeof(*block_i), GFP_NOFS);
  373. if (block_i) {
  374. struct ext4_reserve_window_node *rsv = &block_i->rsv_window_node;
  375. rsv->rsv_start = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
  376. rsv->rsv_end = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
  377. /*
  378. * if filesystem is mounted with NORESERVATION, the goal
  379. * reservation window size is set to zero to indicate
  380. * block reservation is off
  381. */
  382. if (!test_opt(sb, RESERVATION))
  383. rsv->rsv_goal_size = 0;
  384. else
  385. rsv->rsv_goal_size = EXT4_DEFAULT_RESERVE_BLOCKS;
  386. rsv->rsv_alloc_hit = 0;
  387. block_i->last_alloc_logical_block = 0;
  388. block_i->last_alloc_physical_block = 0;
  389. }
  390. ei->i_block_alloc_info = block_i;
  391. }
  392. /**
  393. * ext4_discard_reservation()
  394. * @inode: inode
  395. *
  396. * Discard(free) block reservation window on last file close, or truncate
  397. * or at last iput().
  398. *
  399. * It is being called in three cases:
  400. * ext4_release_file(): last writer close the file
  401. * ext4_clear_inode(): last iput(), when nobody link to this file.
  402. * ext4_truncate(): when the block indirect map is about to change.
  403. *
  404. */
  405. void ext4_discard_reservation(struct inode *inode)
  406. {
  407. struct ext4_inode_info *ei = EXT4_I(inode);
  408. struct ext4_block_alloc_info *block_i = ei->i_block_alloc_info;
  409. struct ext4_reserve_window_node *rsv;
  410. spinlock_t *rsv_lock = &EXT4_SB(inode->i_sb)->s_rsv_window_lock;
  411. if (!block_i)
  412. return;
  413. rsv = &block_i->rsv_window_node;
  414. if (!rsv_is_empty(&rsv->rsv_window)) {
  415. spin_lock(rsv_lock);
  416. if (!rsv_is_empty(&rsv->rsv_window))
  417. rsv_window_remove(inode->i_sb, rsv);
  418. spin_unlock(rsv_lock);
  419. }
  420. }
  421. /**
  422. * ext4_free_blocks_sb() -- Free given blocks and update quota
  423. * @handle: handle to this transaction
  424. * @sb: super block
  425. * @block: start physcial block to free
  426. * @count: number of blocks to free
  427. * @pdquot_freed_blocks: pointer to quota
  428. */
  429. void ext4_free_blocks_sb(handle_t *handle, struct super_block *sb,
  430. ext4_fsblk_t block, unsigned long count,
  431. unsigned long *pdquot_freed_blocks)
  432. {
  433. struct buffer_head *bitmap_bh = NULL;
  434. struct buffer_head *gd_bh;
  435. unsigned long block_group;
  436. ext4_grpblk_t bit;
  437. unsigned long i;
  438. unsigned long overflow;
  439. struct ext4_group_desc * desc;
  440. struct ext4_super_block * es;
  441. struct ext4_sb_info *sbi;
  442. int err = 0, ret;
  443. ext4_grpblk_t group_freed;
  444. *pdquot_freed_blocks = 0;
  445. sbi = EXT4_SB(sb);
  446. es = sbi->s_es;
  447. if (block < le32_to_cpu(es->s_first_data_block) ||
  448. block + count < block ||
  449. block + count > ext4_blocks_count(es)) {
  450. ext4_error (sb, "ext4_free_blocks",
  451. "Freeing blocks not in datazone - "
  452. "block = %llu, count = %lu", block, count);
  453. goto error_return;
  454. }
  455. ext4_debug ("freeing block(s) %llu-%llu\n", block, block + count - 1);
  456. do_more:
  457. overflow = 0;
  458. ext4_get_group_no_and_offset(sb, block, &block_group, &bit);
  459. /*
  460. * Check to see if we are freeing blocks across a group
  461. * boundary.
  462. */
  463. if (bit + count > EXT4_BLOCKS_PER_GROUP(sb)) {
  464. overflow = bit + count - EXT4_BLOCKS_PER_GROUP(sb);
  465. count -= overflow;
  466. }
  467. brelse(bitmap_bh);
  468. bitmap_bh = read_block_bitmap(sb, block_group);
  469. if (!bitmap_bh)
  470. goto error_return;
  471. desc = ext4_get_group_desc (sb, block_group, &gd_bh);
  472. if (!desc)
  473. goto error_return;
  474. if (in_range(ext4_block_bitmap(sb, desc), block, count) ||
  475. in_range(ext4_inode_bitmap(sb, desc), block, count) ||
  476. in_range(block, ext4_inode_table(sb, desc), sbi->s_itb_per_group) ||
  477. in_range(block + count - 1, ext4_inode_table(sb, desc),
  478. sbi->s_itb_per_group))
  479. ext4_error (sb, "ext4_free_blocks",
  480. "Freeing blocks in system zones - "
  481. "Block = %llu, count = %lu",
  482. block, count);
  483. /*
  484. * We are about to start releasing blocks in the bitmap,
  485. * so we need undo access.
  486. */
  487. /* @@@ check errors */
  488. BUFFER_TRACE(bitmap_bh, "getting undo access");
  489. err = ext4_journal_get_undo_access(handle, bitmap_bh);
  490. if (err)
  491. goto error_return;
  492. /*
  493. * We are about to modify some metadata. Call the journal APIs
  494. * to unshare ->b_data if a currently-committing transaction is
  495. * using it
  496. */
  497. BUFFER_TRACE(gd_bh, "get_write_access");
  498. err = ext4_journal_get_write_access(handle, gd_bh);
  499. if (err)
  500. goto error_return;
  501. jbd_lock_bh_state(bitmap_bh);
  502. for (i = 0, group_freed = 0; i < count; i++) {
  503. /*
  504. * An HJ special. This is expensive...
  505. */
  506. #ifdef CONFIG_JBD2_DEBUG
  507. jbd_unlock_bh_state(bitmap_bh);
  508. {
  509. struct buffer_head *debug_bh;
  510. debug_bh = sb_find_get_block(sb, block + i);
  511. if (debug_bh) {
  512. BUFFER_TRACE(debug_bh, "Deleted!");
  513. if (!bh2jh(bitmap_bh)->b_committed_data)
  514. BUFFER_TRACE(debug_bh,
  515. "No commited data in bitmap");
  516. BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap");
  517. __brelse(debug_bh);
  518. }
  519. }
  520. jbd_lock_bh_state(bitmap_bh);
  521. #endif
  522. if (need_resched()) {
  523. jbd_unlock_bh_state(bitmap_bh);
  524. cond_resched();
  525. jbd_lock_bh_state(bitmap_bh);
  526. }
  527. /* @@@ This prevents newly-allocated data from being
  528. * freed and then reallocated within the same
  529. * transaction.
  530. *
  531. * Ideally we would want to allow that to happen, but to
  532. * do so requires making jbd2_journal_forget() capable of
  533. * revoking the queued write of a data block, which
  534. * implies blocking on the journal lock. *forget()
  535. * cannot block due to truncate races.
  536. *
  537. * Eventually we can fix this by making jbd2_journal_forget()
  538. * return a status indicating whether or not it was able
  539. * to revoke the buffer. On successful revoke, it is
  540. * safe not to set the allocation bit in the committed
  541. * bitmap, because we know that there is no outstanding
  542. * activity on the buffer any more and so it is safe to
  543. * reallocate it.
  544. */
  545. BUFFER_TRACE(bitmap_bh, "set in b_committed_data");
  546. J_ASSERT_BH(bitmap_bh,
  547. bh2jh(bitmap_bh)->b_committed_data != NULL);
  548. ext4_set_bit_atomic(sb_bgl_lock(sbi, block_group), bit + i,
  549. bh2jh(bitmap_bh)->b_committed_data);
  550. /*
  551. * We clear the bit in the bitmap after setting the committed
  552. * data bit, because this is the reverse order to that which
  553. * the allocator uses.
  554. */
  555. BUFFER_TRACE(bitmap_bh, "clear bit");
  556. if (!ext4_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
  557. bit + i, bitmap_bh->b_data)) {
  558. jbd_unlock_bh_state(bitmap_bh);
  559. ext4_error(sb, __FUNCTION__,
  560. "bit already cleared for block %llu",
  561. (ext4_fsblk_t)(block + i));
  562. jbd_lock_bh_state(bitmap_bh);
  563. BUFFER_TRACE(bitmap_bh, "bit already cleared");
  564. } else {
  565. group_freed++;
  566. }
  567. }
  568. jbd_unlock_bh_state(bitmap_bh);
  569. spin_lock(sb_bgl_lock(sbi, block_group));
  570. desc->bg_free_blocks_count =
  571. cpu_to_le16(le16_to_cpu(desc->bg_free_blocks_count) +
  572. group_freed);
  573. spin_unlock(sb_bgl_lock(sbi, block_group));
  574. percpu_counter_add(&sbi->s_freeblocks_counter, count);
  575. /* We dirtied the bitmap block */
  576. BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
  577. err = ext4_journal_dirty_metadata(handle, bitmap_bh);
  578. /* And the group descriptor block */
  579. BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
  580. ret = ext4_journal_dirty_metadata(handle, gd_bh);
  581. if (!err) err = ret;
  582. *pdquot_freed_blocks += group_freed;
  583. if (overflow && !err) {
  584. block += count;
  585. count = overflow;
  586. goto do_more;
  587. }
  588. sb->s_dirt = 1;
  589. error_return:
  590. brelse(bitmap_bh);
  591. ext4_std_error(sb, err);
  592. return;
  593. }
  594. /**
  595. * ext4_free_blocks() -- Free given blocks and update quota
  596. * @handle: handle for this transaction
  597. * @inode: inode
  598. * @block: start physical block to free
  599. * @count: number of blocks to count
  600. */
  601. void ext4_free_blocks(handle_t *handle, struct inode *inode,
  602. ext4_fsblk_t block, unsigned long count)
  603. {
  604. struct super_block * sb;
  605. unsigned long dquot_freed_blocks;
  606. sb = inode->i_sb;
  607. if (!sb) {
  608. printk ("ext4_free_blocks: nonexistent device");
  609. return;
  610. }
  611. ext4_free_blocks_sb(handle, sb, block, count, &dquot_freed_blocks);
  612. if (dquot_freed_blocks)
  613. DQUOT_FREE_BLOCK(inode, dquot_freed_blocks);
  614. return;
  615. }
  616. /**
  617. * ext4_test_allocatable()
  618. * @nr: given allocation block group
  619. * @bh: bufferhead contains the bitmap of the given block group
  620. *
  621. * For ext4 allocations, we must not reuse any blocks which are
  622. * allocated in the bitmap buffer's "last committed data" copy. This
  623. * prevents deletes from freeing up the page for reuse until we have
  624. * committed the delete transaction.
  625. *
  626. * If we didn't do this, then deleting something and reallocating it as
  627. * data would allow the old block to be overwritten before the
  628. * transaction committed (because we force data to disk before commit).
  629. * This would lead to corruption if we crashed between overwriting the
  630. * data and committing the delete.
  631. *
  632. * @@@ We may want to make this allocation behaviour conditional on
  633. * data-writes at some point, and disable it for metadata allocations or
  634. * sync-data inodes.
  635. */
  636. static int ext4_test_allocatable(ext4_grpblk_t nr, struct buffer_head *bh)
  637. {
  638. int ret;
  639. struct journal_head *jh = bh2jh(bh);
  640. if (ext4_test_bit(nr, bh->b_data))
  641. return 0;
  642. jbd_lock_bh_state(bh);
  643. if (!jh->b_committed_data)
  644. ret = 1;
  645. else
  646. ret = !ext4_test_bit(nr, jh->b_committed_data);
  647. jbd_unlock_bh_state(bh);
  648. return ret;
  649. }
  650. /**
  651. * bitmap_search_next_usable_block()
  652. * @start: the starting block (group relative) of the search
  653. * @bh: bufferhead contains the block group bitmap
  654. * @maxblocks: the ending block (group relative) of the reservation
  655. *
  656. * The bitmap search --- search forward alternately through the actual
  657. * bitmap on disk and the last-committed copy in journal, until we find a
  658. * bit free in both bitmaps.
  659. */
  660. static ext4_grpblk_t
  661. bitmap_search_next_usable_block(ext4_grpblk_t start, struct buffer_head *bh,
  662. ext4_grpblk_t maxblocks)
  663. {
  664. ext4_grpblk_t next;
  665. struct journal_head *jh = bh2jh(bh);
  666. while (start < maxblocks) {
  667. next = ext4_find_next_zero_bit(bh->b_data, maxblocks, start);
  668. if (next >= maxblocks)
  669. return -1;
  670. if (ext4_test_allocatable(next, bh))
  671. return next;
  672. jbd_lock_bh_state(bh);
  673. if (jh->b_committed_data)
  674. start = ext4_find_next_zero_bit(jh->b_committed_data,
  675. maxblocks, next);
  676. jbd_unlock_bh_state(bh);
  677. }
  678. return -1;
  679. }
  680. /**
  681. * find_next_usable_block()
  682. * @start: the starting block (group relative) to find next
  683. * allocatable block in bitmap.
  684. * @bh: bufferhead contains the block group bitmap
  685. * @maxblocks: the ending block (group relative) for the search
  686. *
  687. * Find an allocatable block in a bitmap. We honor both the bitmap and
  688. * its last-committed copy (if that exists), and perform the "most
  689. * appropriate allocation" algorithm of looking for a free block near
  690. * the initial goal; then for a free byte somewhere in the bitmap; then
  691. * for any free bit in the bitmap.
  692. */
  693. static ext4_grpblk_t
  694. find_next_usable_block(ext4_grpblk_t start, struct buffer_head *bh,
  695. ext4_grpblk_t maxblocks)
  696. {
  697. ext4_grpblk_t here, next;
  698. char *p, *r;
  699. if (start > 0) {
  700. /*
  701. * The goal was occupied; search forward for a free
  702. * block within the next XX blocks.
  703. *
  704. * end_goal is more or less random, but it has to be
  705. * less than EXT4_BLOCKS_PER_GROUP. Aligning up to the
  706. * next 64-bit boundary is simple..
  707. */
  708. ext4_grpblk_t end_goal = (start + 63) & ~63;
  709. if (end_goal > maxblocks)
  710. end_goal = maxblocks;
  711. here = ext4_find_next_zero_bit(bh->b_data, end_goal, start);
  712. if (here < end_goal && ext4_test_allocatable(here, bh))
  713. return here;
  714. ext4_debug("Bit not found near goal\n");
  715. }
  716. here = start;
  717. if (here < 0)
  718. here = 0;
  719. p = ((char *)bh->b_data) + (here >> 3);
  720. r = memscan(p, 0, ((maxblocks + 7) >> 3) - (here >> 3));
  721. next = (r - ((char *)bh->b_data)) << 3;
  722. if (next < maxblocks && next >= start && ext4_test_allocatable(next, bh))
  723. return next;
  724. /*
  725. * The bitmap search --- search forward alternately through the actual
  726. * bitmap and the last-committed copy until we find a bit free in
  727. * both
  728. */
  729. here = bitmap_search_next_usable_block(here, bh, maxblocks);
  730. return here;
  731. }
  732. /**
  733. * claim_block()
  734. * @block: the free block (group relative) to allocate
  735. * @bh: the bufferhead containts the block group bitmap
  736. *
  737. * We think we can allocate this block in this bitmap. Try to set the bit.
  738. * If that succeeds then check that nobody has allocated and then freed the
  739. * block since we saw that is was not marked in b_committed_data. If it _was_
  740. * allocated and freed then clear the bit in the bitmap again and return
  741. * zero (failure).
  742. */
  743. static inline int
  744. claim_block(spinlock_t *lock, ext4_grpblk_t block, struct buffer_head *bh)
  745. {
  746. struct journal_head *jh = bh2jh(bh);
  747. int ret;
  748. if (ext4_set_bit_atomic(lock, block, bh->b_data))
  749. return 0;
  750. jbd_lock_bh_state(bh);
  751. if (jh->b_committed_data && ext4_test_bit(block,jh->b_committed_data)) {
  752. ext4_clear_bit_atomic(lock, block, bh->b_data);
  753. ret = 0;
  754. } else {
  755. ret = 1;
  756. }
  757. jbd_unlock_bh_state(bh);
  758. return ret;
  759. }
  760. /**
  761. * ext4_try_to_allocate()
  762. * @sb: superblock
  763. * @handle: handle to this transaction
  764. * @group: given allocation block group
  765. * @bitmap_bh: bufferhead holds the block bitmap
  766. * @grp_goal: given target block within the group
  767. * @count: target number of blocks to allocate
  768. * @my_rsv: reservation window
  769. *
  770. * Attempt to allocate blocks within a give range. Set the range of allocation
  771. * first, then find the first free bit(s) from the bitmap (within the range),
  772. * and at last, allocate the blocks by claiming the found free bit as allocated.
  773. *
  774. * To set the range of this allocation:
  775. * if there is a reservation window, only try to allocate block(s) from the
  776. * file's own reservation window;
  777. * Otherwise, the allocation range starts from the give goal block, ends at
  778. * the block group's last block.
  779. *
  780. * If we failed to allocate the desired block then we may end up crossing to a
  781. * new bitmap. In that case we must release write access to the old one via
  782. * ext4_journal_release_buffer(), else we'll run out of credits.
  783. */
  784. static ext4_grpblk_t
  785. ext4_try_to_allocate(struct super_block *sb, handle_t *handle, int group,
  786. struct buffer_head *bitmap_bh, ext4_grpblk_t grp_goal,
  787. unsigned long *count, struct ext4_reserve_window *my_rsv)
  788. {
  789. ext4_fsblk_t group_first_block;
  790. ext4_grpblk_t start, end;
  791. unsigned long num = 0;
  792. /* we do allocation within the reservation window if we have a window */
  793. if (my_rsv) {
  794. group_first_block = ext4_group_first_block_no(sb, group);
  795. if (my_rsv->_rsv_start >= group_first_block)
  796. start = my_rsv->_rsv_start - group_first_block;
  797. else
  798. /* reservation window cross group boundary */
  799. start = 0;
  800. end = my_rsv->_rsv_end - group_first_block + 1;
  801. if (end > EXT4_BLOCKS_PER_GROUP(sb))
  802. /* reservation window crosses group boundary */
  803. end = EXT4_BLOCKS_PER_GROUP(sb);
  804. if ((start <= grp_goal) && (grp_goal < end))
  805. start = grp_goal;
  806. else
  807. grp_goal = -1;
  808. } else {
  809. if (grp_goal > 0)
  810. start = grp_goal;
  811. else
  812. start = 0;
  813. end = EXT4_BLOCKS_PER_GROUP(sb);
  814. }
  815. BUG_ON(start > EXT4_BLOCKS_PER_GROUP(sb));
  816. repeat:
  817. if (grp_goal < 0 || !ext4_test_allocatable(grp_goal, bitmap_bh)) {
  818. grp_goal = find_next_usable_block(start, bitmap_bh, end);
  819. if (grp_goal < 0)
  820. goto fail_access;
  821. if (!my_rsv) {
  822. int i;
  823. for (i = 0; i < 7 && grp_goal > start &&
  824. ext4_test_allocatable(grp_goal - 1,
  825. bitmap_bh);
  826. i++, grp_goal--)
  827. ;
  828. }
  829. }
  830. start = grp_goal;
  831. if (!claim_block(sb_bgl_lock(EXT4_SB(sb), group),
  832. grp_goal, bitmap_bh)) {
  833. /*
  834. * The block was allocated by another thread, or it was
  835. * allocated and then freed by another thread
  836. */
  837. start++;
  838. grp_goal++;
  839. if (start >= end)
  840. goto fail_access;
  841. goto repeat;
  842. }
  843. num++;
  844. grp_goal++;
  845. while (num < *count && grp_goal < end
  846. && ext4_test_allocatable(grp_goal, bitmap_bh)
  847. && claim_block(sb_bgl_lock(EXT4_SB(sb), group),
  848. grp_goal, bitmap_bh)) {
  849. num++;
  850. grp_goal++;
  851. }
  852. *count = num;
  853. return grp_goal - num;
  854. fail_access:
  855. *count = num;
  856. return -1;
  857. }
  858. /**
  859. * find_next_reservable_window():
  860. * find a reservable space within the given range.
  861. * It does not allocate the reservation window for now:
  862. * alloc_new_reservation() will do the work later.
  863. *
  864. * @search_head: the head of the searching list;
  865. * This is not necessarily the list head of the whole filesystem
  866. *
  867. * We have both head and start_block to assist the search
  868. * for the reservable space. The list starts from head,
  869. * but we will shift to the place where start_block is,
  870. * then start from there, when looking for a reservable space.
  871. *
  872. * @size: the target new reservation window size
  873. *
  874. * @group_first_block: the first block we consider to start
  875. * the real search from
  876. *
  877. * @last_block:
  878. * the maximum block number that our goal reservable space
  879. * could start from. This is normally the last block in this
  880. * group. The search will end when we found the start of next
  881. * possible reservable space is out of this boundary.
  882. * This could handle the cross boundary reservation window
  883. * request.
  884. *
  885. * basically we search from the given range, rather than the whole
  886. * reservation double linked list, (start_block, last_block)
  887. * to find a free region that is of my size and has not
  888. * been reserved.
  889. *
  890. */
  891. static int find_next_reservable_window(
  892. struct ext4_reserve_window_node *search_head,
  893. struct ext4_reserve_window_node *my_rsv,
  894. struct super_block * sb,
  895. ext4_fsblk_t start_block,
  896. ext4_fsblk_t last_block)
  897. {
  898. struct rb_node *next;
  899. struct ext4_reserve_window_node *rsv, *prev;
  900. ext4_fsblk_t cur;
  901. int size = my_rsv->rsv_goal_size;
  902. /* TODO: make the start of the reservation window byte-aligned */
  903. /* cur = *start_block & ~7;*/
  904. cur = start_block;
  905. rsv = search_head;
  906. if (!rsv)
  907. return -1;
  908. while (1) {
  909. if (cur <= rsv->rsv_end)
  910. cur = rsv->rsv_end + 1;
  911. /* TODO?
  912. * in the case we could not find a reservable space
  913. * that is what is expected, during the re-search, we could
  914. * remember what's the largest reservable space we could have
  915. * and return that one.
  916. *
  917. * For now it will fail if we could not find the reservable
  918. * space with expected-size (or more)...
  919. */
  920. if (cur > last_block)
  921. return -1; /* fail */
  922. prev = rsv;
  923. next = rb_next(&rsv->rsv_node);
  924. rsv = rb_entry(next,struct ext4_reserve_window_node,rsv_node);
  925. /*
  926. * Reached the last reservation, we can just append to the
  927. * previous one.
  928. */
  929. if (!next)
  930. break;
  931. if (cur + size <= rsv->rsv_start) {
  932. /*
  933. * Found a reserveable space big enough. We could
  934. * have a reservation across the group boundary here
  935. */
  936. break;
  937. }
  938. }
  939. /*
  940. * we come here either :
  941. * when we reach the end of the whole list,
  942. * and there is empty reservable space after last entry in the list.
  943. * append it to the end of the list.
  944. *
  945. * or we found one reservable space in the middle of the list,
  946. * return the reservation window that we could append to.
  947. * succeed.
  948. */
  949. if ((prev != my_rsv) && (!rsv_is_empty(&my_rsv->rsv_window)))
  950. rsv_window_remove(sb, my_rsv);
  951. /*
  952. * Let's book the whole avaliable window for now. We will check the
  953. * disk bitmap later and then, if there are free blocks then we adjust
  954. * the window size if it's larger than requested.
  955. * Otherwise, we will remove this node from the tree next time
  956. * call find_next_reservable_window.
  957. */
  958. my_rsv->rsv_start = cur;
  959. my_rsv->rsv_end = cur + size - 1;
  960. my_rsv->rsv_alloc_hit = 0;
  961. if (prev != my_rsv)
  962. ext4_rsv_window_add(sb, my_rsv);
  963. return 0;
  964. }
  965. /**
  966. * alloc_new_reservation()--allocate a new reservation window
  967. *
  968. * To make a new reservation, we search part of the filesystem
  969. * reservation list (the list that inside the group). We try to
  970. * allocate a new reservation window near the allocation goal,
  971. * or the beginning of the group, if there is no goal.
  972. *
  973. * We first find a reservable space after the goal, then from
  974. * there, we check the bitmap for the first free block after
  975. * it. If there is no free block until the end of group, then the
  976. * whole group is full, we failed. Otherwise, check if the free
  977. * block is inside the expected reservable space, if so, we
  978. * succeed.
  979. * If the first free block is outside the reservable space, then
  980. * start from the first free block, we search for next available
  981. * space, and go on.
  982. *
  983. * on succeed, a new reservation will be found and inserted into the list
  984. * It contains at least one free block, and it does not overlap with other
  985. * reservation windows.
  986. *
  987. * failed: we failed to find a reservation window in this group
  988. *
  989. * @rsv: the reservation
  990. *
  991. * @grp_goal: The goal (group-relative). It is where the search for a
  992. * free reservable space should start from.
  993. * if we have a grp_goal(grp_goal >0 ), then start from there,
  994. * no grp_goal(grp_goal = -1), we start from the first block
  995. * of the group.
  996. *
  997. * @sb: the super block
  998. * @group: the group we are trying to allocate in
  999. * @bitmap_bh: the block group block bitmap
  1000. *
  1001. */
  1002. static int alloc_new_reservation(struct ext4_reserve_window_node *my_rsv,
  1003. ext4_grpblk_t grp_goal, struct super_block *sb,
  1004. unsigned int group, struct buffer_head *bitmap_bh)
  1005. {
  1006. struct ext4_reserve_window_node *search_head;
  1007. ext4_fsblk_t group_first_block, group_end_block, start_block;
  1008. ext4_grpblk_t first_free_block;
  1009. struct rb_root *fs_rsv_root = &EXT4_SB(sb)->s_rsv_window_root;
  1010. unsigned long size;
  1011. int ret;
  1012. spinlock_t *rsv_lock = &EXT4_SB(sb)->s_rsv_window_lock;
  1013. group_first_block = ext4_group_first_block_no(sb, group);
  1014. group_end_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
  1015. if (grp_goal < 0)
  1016. start_block = group_first_block;
  1017. else
  1018. start_block = grp_goal + group_first_block;
  1019. size = my_rsv->rsv_goal_size;
  1020. if (!rsv_is_empty(&my_rsv->rsv_window)) {
  1021. /*
  1022. * if the old reservation is cross group boundary
  1023. * and if the goal is inside the old reservation window,
  1024. * we will come here when we just failed to allocate from
  1025. * the first part of the window. We still have another part
  1026. * that belongs to the next group. In this case, there is no
  1027. * point to discard our window and try to allocate a new one
  1028. * in this group(which will fail). we should
  1029. * keep the reservation window, just simply move on.
  1030. *
  1031. * Maybe we could shift the start block of the reservation
  1032. * window to the first block of next group.
  1033. */
  1034. if ((my_rsv->rsv_start <= group_end_block) &&
  1035. (my_rsv->rsv_end > group_end_block) &&
  1036. (start_block >= my_rsv->rsv_start))
  1037. return -1;
  1038. if ((my_rsv->rsv_alloc_hit >
  1039. (my_rsv->rsv_end - my_rsv->rsv_start + 1) / 2)) {
  1040. /*
  1041. * if the previously allocation hit ratio is
  1042. * greater than 1/2, then we double the size of
  1043. * the reservation window the next time,
  1044. * otherwise we keep the same size window
  1045. */
  1046. size = size * 2;
  1047. if (size > EXT4_MAX_RESERVE_BLOCKS)
  1048. size = EXT4_MAX_RESERVE_BLOCKS;
  1049. my_rsv->rsv_goal_size= size;
  1050. }
  1051. }
  1052. spin_lock(rsv_lock);
  1053. /*
  1054. * shift the search start to the window near the goal block
  1055. */
  1056. search_head = search_reserve_window(fs_rsv_root, start_block);
  1057. /*
  1058. * find_next_reservable_window() simply finds a reservable window
  1059. * inside the given range(start_block, group_end_block).
  1060. *
  1061. * To make sure the reservation window has a free bit inside it, we
  1062. * need to check the bitmap after we found a reservable window.
  1063. */
  1064. retry:
  1065. ret = find_next_reservable_window(search_head, my_rsv, sb,
  1066. start_block, group_end_block);
  1067. if (ret == -1) {
  1068. if (!rsv_is_empty(&my_rsv->rsv_window))
  1069. rsv_window_remove(sb, my_rsv);
  1070. spin_unlock(rsv_lock);
  1071. return -1;
  1072. }
  1073. /*
  1074. * On success, find_next_reservable_window() returns the
  1075. * reservation window where there is a reservable space after it.
  1076. * Before we reserve this reservable space, we need
  1077. * to make sure there is at least a free block inside this region.
  1078. *
  1079. * searching the first free bit on the block bitmap and copy of
  1080. * last committed bitmap alternatively, until we found a allocatable
  1081. * block. Search start from the start block of the reservable space
  1082. * we just found.
  1083. */
  1084. spin_unlock(rsv_lock);
  1085. first_free_block = bitmap_search_next_usable_block(
  1086. my_rsv->rsv_start - group_first_block,
  1087. bitmap_bh, group_end_block - group_first_block + 1);
  1088. if (first_free_block < 0) {
  1089. /*
  1090. * no free block left on the bitmap, no point
  1091. * to reserve the space. return failed.
  1092. */
  1093. spin_lock(rsv_lock);
  1094. if (!rsv_is_empty(&my_rsv->rsv_window))
  1095. rsv_window_remove(sb, my_rsv);
  1096. spin_unlock(rsv_lock);
  1097. return -1; /* failed */
  1098. }
  1099. start_block = first_free_block + group_first_block;
  1100. /*
  1101. * check if the first free block is within the
  1102. * free space we just reserved
  1103. */
  1104. if (start_block >= my_rsv->rsv_start && start_block <= my_rsv->rsv_end)
  1105. return 0; /* success */
  1106. /*
  1107. * if the first free bit we found is out of the reservable space
  1108. * continue search for next reservable space,
  1109. * start from where the free block is,
  1110. * we also shift the list head to where we stopped last time
  1111. */
  1112. search_head = my_rsv;
  1113. spin_lock(rsv_lock);
  1114. goto retry;
  1115. }
  1116. /**
  1117. * try_to_extend_reservation()
  1118. * @my_rsv: given reservation window
  1119. * @sb: super block
  1120. * @size: the delta to extend
  1121. *
  1122. * Attempt to expand the reservation window large enough to have
  1123. * required number of free blocks
  1124. *
  1125. * Since ext4_try_to_allocate() will always allocate blocks within
  1126. * the reservation window range, if the window size is too small,
  1127. * multiple blocks allocation has to stop at the end of the reservation
  1128. * window. To make this more efficient, given the total number of
  1129. * blocks needed and the current size of the window, we try to
  1130. * expand the reservation window size if necessary on a best-effort
  1131. * basis before ext4_new_blocks() tries to allocate blocks,
  1132. */
  1133. static void try_to_extend_reservation(struct ext4_reserve_window_node *my_rsv,
  1134. struct super_block *sb, int size)
  1135. {
  1136. struct ext4_reserve_window_node *next_rsv;
  1137. struct rb_node *next;
  1138. spinlock_t *rsv_lock = &EXT4_SB(sb)->s_rsv_window_lock;
  1139. if (!spin_trylock(rsv_lock))
  1140. return;
  1141. next = rb_next(&my_rsv->rsv_node);
  1142. if (!next)
  1143. my_rsv->rsv_end += size;
  1144. else {
  1145. next_rsv = rb_entry(next, struct ext4_reserve_window_node, rsv_node);
  1146. if ((next_rsv->rsv_start - my_rsv->rsv_end - 1) >= size)
  1147. my_rsv->rsv_end += size;
  1148. else
  1149. my_rsv->rsv_end = next_rsv->rsv_start - 1;
  1150. }
  1151. spin_unlock(rsv_lock);
  1152. }
  1153. /**
  1154. * ext4_try_to_allocate_with_rsv()
  1155. * @sb: superblock
  1156. * @handle: handle to this transaction
  1157. * @group: given allocation block group
  1158. * @bitmap_bh: bufferhead holds the block bitmap
  1159. * @grp_goal: given target block within the group
  1160. * @count: target number of blocks to allocate
  1161. * @my_rsv: reservation window
  1162. * @errp: pointer to store the error code
  1163. *
  1164. * This is the main function used to allocate a new block and its reservation
  1165. * window.
  1166. *
  1167. * Each time when a new block allocation is need, first try to allocate from
  1168. * its own reservation. If it does not have a reservation window, instead of
  1169. * looking for a free bit on bitmap first, then look up the reservation list to
  1170. * see if it is inside somebody else's reservation window, we try to allocate a
  1171. * reservation window for it starting from the goal first. Then do the block
  1172. * allocation within the reservation window.
  1173. *
  1174. * This will avoid keeping on searching the reservation list again and
  1175. * again when somebody is looking for a free block (without
  1176. * reservation), and there are lots of free blocks, but they are all
  1177. * being reserved.
  1178. *
  1179. * We use a red-black tree for the per-filesystem reservation list.
  1180. *
  1181. */
  1182. static ext4_grpblk_t
  1183. ext4_try_to_allocate_with_rsv(struct super_block *sb, handle_t *handle,
  1184. unsigned int group, struct buffer_head *bitmap_bh,
  1185. ext4_grpblk_t grp_goal,
  1186. struct ext4_reserve_window_node * my_rsv,
  1187. unsigned long *count, int *errp)
  1188. {
  1189. ext4_fsblk_t group_first_block, group_last_block;
  1190. ext4_grpblk_t ret = 0;
  1191. int fatal;
  1192. unsigned long num = *count;
  1193. *errp = 0;
  1194. /*
  1195. * Make sure we use undo access for the bitmap, because it is critical
  1196. * that we do the frozen_data COW on bitmap buffers in all cases even
  1197. * if the buffer is in BJ_Forget state in the committing transaction.
  1198. */
  1199. BUFFER_TRACE(bitmap_bh, "get undo access for new block");
  1200. fatal = ext4_journal_get_undo_access(handle, bitmap_bh);
  1201. if (fatal) {
  1202. *errp = fatal;
  1203. return -1;
  1204. }
  1205. /*
  1206. * we don't deal with reservation when
  1207. * filesystem is mounted without reservation
  1208. * or the file is not a regular file
  1209. * or last attempt to allocate a block with reservation turned on failed
  1210. */
  1211. if (my_rsv == NULL ) {
  1212. ret = ext4_try_to_allocate(sb, handle, group, bitmap_bh,
  1213. grp_goal, count, NULL);
  1214. goto out;
  1215. }
  1216. /*
  1217. * grp_goal is a group relative block number (if there is a goal)
  1218. * 0 <= grp_goal < EXT4_BLOCKS_PER_GROUP(sb)
  1219. * first block is a filesystem wide block number
  1220. * first block is the block number of the first block in this group
  1221. */
  1222. group_first_block = ext4_group_first_block_no(sb, group);
  1223. group_last_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
  1224. /*
  1225. * Basically we will allocate a new block from inode's reservation
  1226. * window.
  1227. *
  1228. * We need to allocate a new reservation window, if:
  1229. * a) inode does not have a reservation window; or
  1230. * b) last attempt to allocate a block from existing reservation
  1231. * failed; or
  1232. * c) we come here with a goal and with a reservation window
  1233. *
  1234. * We do not need to allocate a new reservation window if we come here
  1235. * at the beginning with a goal and the goal is inside the window, or
  1236. * we don't have a goal but already have a reservation window.
  1237. * then we could go to allocate from the reservation window directly.
  1238. */
  1239. while (1) {
  1240. if (rsv_is_empty(&my_rsv->rsv_window) || (ret < 0) ||
  1241. !goal_in_my_reservation(&my_rsv->rsv_window,
  1242. grp_goal, group, sb)) {
  1243. if (my_rsv->rsv_goal_size < *count)
  1244. my_rsv->rsv_goal_size = *count;
  1245. ret = alloc_new_reservation(my_rsv, grp_goal, sb,
  1246. group, bitmap_bh);
  1247. if (ret < 0)
  1248. break; /* failed */
  1249. if (!goal_in_my_reservation(&my_rsv->rsv_window,
  1250. grp_goal, group, sb))
  1251. grp_goal = -1;
  1252. } else if (grp_goal >= 0) {
  1253. int curr = my_rsv->rsv_end -
  1254. (grp_goal + group_first_block) + 1;
  1255. if (curr < *count)
  1256. try_to_extend_reservation(my_rsv, sb,
  1257. *count - curr);
  1258. }
  1259. if ((my_rsv->rsv_start > group_last_block) ||
  1260. (my_rsv->rsv_end < group_first_block)) {
  1261. rsv_window_dump(&EXT4_SB(sb)->s_rsv_window_root, 1);
  1262. BUG();
  1263. }
  1264. ret = ext4_try_to_allocate(sb, handle, group, bitmap_bh,
  1265. grp_goal, &num, &my_rsv->rsv_window);
  1266. if (ret >= 0) {
  1267. my_rsv->rsv_alloc_hit += num;
  1268. *count = num;
  1269. break; /* succeed */
  1270. }
  1271. num = *count;
  1272. }
  1273. out:
  1274. if (ret >= 0) {
  1275. BUFFER_TRACE(bitmap_bh, "journal_dirty_metadata for "
  1276. "bitmap block");
  1277. fatal = ext4_journal_dirty_metadata(handle, bitmap_bh);
  1278. if (fatal) {
  1279. *errp = fatal;
  1280. return -1;
  1281. }
  1282. return ret;
  1283. }
  1284. BUFFER_TRACE(bitmap_bh, "journal_release_buffer");
  1285. ext4_journal_release_buffer(handle, bitmap_bh);
  1286. return ret;
  1287. }
  1288. /**
  1289. * ext4_has_free_blocks()
  1290. * @sbi: in-core super block structure.
  1291. *
  1292. * Check if filesystem has at least 1 free block available for allocation.
  1293. */
  1294. static int ext4_has_free_blocks(struct ext4_sb_info *sbi)
  1295. {
  1296. ext4_fsblk_t free_blocks, root_blocks;
  1297. free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
  1298. root_blocks = ext4_r_blocks_count(sbi->s_es);
  1299. if (free_blocks < root_blocks + 1 && !capable(CAP_SYS_RESOURCE) &&
  1300. sbi->s_resuid != current->fsuid &&
  1301. (sbi->s_resgid == 0 || !in_group_p (sbi->s_resgid))) {
  1302. return 0;
  1303. }
  1304. return 1;
  1305. }
  1306. /**
  1307. * ext4_should_retry_alloc()
  1308. * @sb: super block
  1309. * @retries number of attemps has been made
  1310. *
  1311. * ext4_should_retry_alloc() is called when ENOSPC is returned, and if
  1312. * it is profitable to retry the operation, this function will wait
  1313. * for the current or commiting transaction to complete, and then
  1314. * return TRUE.
  1315. *
  1316. * if the total number of retries exceed three times, return FALSE.
  1317. */
  1318. int ext4_should_retry_alloc(struct super_block *sb, int *retries)
  1319. {
  1320. if (!ext4_has_free_blocks(EXT4_SB(sb)) || (*retries)++ > 3)
  1321. return 0;
  1322. jbd_debug(1, "%s: retrying operation after ENOSPC\n", sb->s_id);
  1323. return jbd2_journal_force_commit_nested(EXT4_SB(sb)->s_journal);
  1324. }
  1325. /**
  1326. * ext4_new_blocks() -- core block(s) allocation function
  1327. * @handle: handle to this transaction
  1328. * @inode: file inode
  1329. * @goal: given target block(filesystem wide)
  1330. * @count: target number of blocks to allocate
  1331. * @errp: error code
  1332. *
  1333. * ext4_new_blocks uses a goal block to assist allocation. It tries to
  1334. * allocate block(s) from the block group contains the goal block first. If that
  1335. * fails, it will try to allocate block(s) from other block groups without
  1336. * any specific goal block.
  1337. *
  1338. */
  1339. ext4_fsblk_t ext4_new_blocks(handle_t *handle, struct inode *inode,
  1340. ext4_fsblk_t goal, unsigned long *count, int *errp)
  1341. {
  1342. struct buffer_head *bitmap_bh = NULL;
  1343. struct buffer_head *gdp_bh;
  1344. unsigned long group_no;
  1345. int goal_group;
  1346. ext4_grpblk_t grp_target_blk; /* blockgroup relative goal block */
  1347. ext4_grpblk_t grp_alloc_blk; /* blockgroup-relative allocated block*/
  1348. ext4_fsblk_t ret_block; /* filesyetem-wide allocated block */
  1349. int bgi; /* blockgroup iteration index */
  1350. int fatal = 0, err;
  1351. int performed_allocation = 0;
  1352. ext4_grpblk_t free_blocks; /* number of free blocks in a group */
  1353. struct super_block *sb;
  1354. struct ext4_group_desc *gdp;
  1355. struct ext4_super_block *es;
  1356. struct ext4_sb_info *sbi;
  1357. struct ext4_reserve_window_node *my_rsv = NULL;
  1358. struct ext4_block_alloc_info *block_i;
  1359. unsigned short windowsz = 0;
  1360. #ifdef EXT4FS_DEBUG
  1361. static int goal_hits, goal_attempts;
  1362. #endif
  1363. unsigned long ngroups;
  1364. unsigned long num = *count;
  1365. *errp = -ENOSPC;
  1366. sb = inode->i_sb;
  1367. if (!sb) {
  1368. printk("ext4_new_block: nonexistent device");
  1369. return 0;
  1370. }
  1371. /*
  1372. * Check quota for allocation of this block.
  1373. */
  1374. if (DQUOT_ALLOC_BLOCK(inode, num)) {
  1375. *errp = -EDQUOT;
  1376. return 0;
  1377. }
  1378. sbi = EXT4_SB(sb);
  1379. es = EXT4_SB(sb)->s_es;
  1380. ext4_debug("goal=%lu.\n", goal);
  1381. /*
  1382. * Allocate a block from reservation only when
  1383. * filesystem is mounted with reservation(default,-o reservation), and
  1384. * it's a regular file, and
  1385. * the desired window size is greater than 0 (One could use ioctl
  1386. * command EXT4_IOC_SETRSVSZ to set the window size to 0 to turn off
  1387. * reservation on that particular file)
  1388. */
  1389. block_i = EXT4_I(inode)->i_block_alloc_info;
  1390. if (block_i && ((windowsz = block_i->rsv_window_node.rsv_goal_size) > 0))
  1391. my_rsv = &block_i->rsv_window_node;
  1392. if (!ext4_has_free_blocks(sbi)) {
  1393. *errp = -ENOSPC;
  1394. goto out;
  1395. }
  1396. /*
  1397. * First, test whether the goal block is free.
  1398. */
  1399. if (goal < le32_to_cpu(es->s_first_data_block) ||
  1400. goal >= ext4_blocks_count(es))
  1401. goal = le32_to_cpu(es->s_first_data_block);
  1402. ext4_get_group_no_and_offset(sb, goal, &group_no, &grp_target_blk);
  1403. goal_group = group_no;
  1404. retry_alloc:
  1405. gdp = ext4_get_group_desc(sb, group_no, &gdp_bh);
  1406. if (!gdp)
  1407. goto io_error;
  1408. free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
  1409. /*
  1410. * if there is not enough free blocks to make a new resevation
  1411. * turn off reservation for this allocation
  1412. */
  1413. if (my_rsv && (free_blocks < windowsz)
  1414. && (rsv_is_empty(&my_rsv->rsv_window)))
  1415. my_rsv = NULL;
  1416. if (free_blocks > 0) {
  1417. bitmap_bh = read_block_bitmap(sb, group_no);
  1418. if (!bitmap_bh)
  1419. goto io_error;
  1420. grp_alloc_blk = ext4_try_to_allocate_with_rsv(sb, handle,
  1421. group_no, bitmap_bh, grp_target_blk,
  1422. my_rsv, &num, &fatal);
  1423. if (fatal)
  1424. goto out;
  1425. if (grp_alloc_blk >= 0)
  1426. goto allocated;
  1427. }
  1428. ngroups = EXT4_SB(sb)->s_groups_count;
  1429. smp_rmb();
  1430. /*
  1431. * Now search the rest of the groups. We assume that
  1432. * i and gdp correctly point to the last group visited.
  1433. */
  1434. for (bgi = 0; bgi < ngroups; bgi++) {
  1435. group_no++;
  1436. if (group_no >= ngroups)
  1437. group_no = 0;
  1438. gdp = ext4_get_group_desc(sb, group_no, &gdp_bh);
  1439. if (!gdp)
  1440. goto io_error;
  1441. free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
  1442. /*
  1443. * skip this group if the number of
  1444. * free blocks is less than half of the reservation
  1445. * window size.
  1446. */
  1447. if (free_blocks <= (windowsz/2))
  1448. continue;
  1449. brelse(bitmap_bh);
  1450. bitmap_bh = read_block_bitmap(sb, group_no);
  1451. if (!bitmap_bh)
  1452. goto io_error;
  1453. /*
  1454. * try to allocate block(s) from this group, without a goal(-1).
  1455. */
  1456. grp_alloc_blk = ext4_try_to_allocate_with_rsv(sb, handle,
  1457. group_no, bitmap_bh, -1, my_rsv,
  1458. &num, &fatal);
  1459. if (fatal)
  1460. goto out;
  1461. if (grp_alloc_blk >= 0)
  1462. goto allocated;
  1463. }
  1464. /*
  1465. * We may end up a bogus ealier ENOSPC error due to
  1466. * filesystem is "full" of reservations, but
  1467. * there maybe indeed free blocks avaliable on disk
  1468. * In this case, we just forget about the reservations
  1469. * just do block allocation as without reservations.
  1470. */
  1471. if (my_rsv) {
  1472. my_rsv = NULL;
  1473. windowsz = 0;
  1474. group_no = goal_group;
  1475. goto retry_alloc;
  1476. }
  1477. /* No space left on the device */
  1478. *errp = -ENOSPC;
  1479. goto out;
  1480. allocated:
  1481. ext4_debug("using block group %d(%d)\n",
  1482. group_no, gdp->bg_free_blocks_count);
  1483. BUFFER_TRACE(gdp_bh, "get_write_access");
  1484. fatal = ext4_journal_get_write_access(handle, gdp_bh);
  1485. if (fatal)
  1486. goto out;
  1487. ret_block = grp_alloc_blk + ext4_group_first_block_no(sb, group_no);
  1488. if (in_range(ext4_block_bitmap(sb, gdp), ret_block, num) ||
  1489. in_range(ext4_inode_bitmap(sb, gdp), ret_block, num) ||
  1490. in_range(ret_block, ext4_inode_table(sb, gdp),
  1491. EXT4_SB(sb)->s_itb_per_group) ||
  1492. in_range(ret_block + num - 1, ext4_inode_table(sb, gdp),
  1493. EXT4_SB(sb)->s_itb_per_group))
  1494. ext4_error(sb, "ext4_new_block",
  1495. "Allocating block in system zone - "
  1496. "blocks from %llu, length %lu",
  1497. ret_block, num);
  1498. performed_allocation = 1;
  1499. #ifdef CONFIG_JBD2_DEBUG
  1500. {
  1501. struct buffer_head *debug_bh;
  1502. /* Record bitmap buffer state in the newly allocated block */
  1503. debug_bh = sb_find_get_block(sb, ret_block);
  1504. if (debug_bh) {
  1505. BUFFER_TRACE(debug_bh, "state when allocated");
  1506. BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap state");
  1507. brelse(debug_bh);
  1508. }
  1509. }
  1510. jbd_lock_bh_state(bitmap_bh);
  1511. spin_lock(sb_bgl_lock(sbi, group_no));
  1512. if (buffer_jbd(bitmap_bh) && bh2jh(bitmap_bh)->b_committed_data) {
  1513. int i;
  1514. for (i = 0; i < num; i++) {
  1515. if (ext4_test_bit(grp_alloc_blk+i,
  1516. bh2jh(bitmap_bh)->b_committed_data)) {
  1517. printk("%s: block was unexpectedly set in "
  1518. "b_committed_data\n", __FUNCTION__);
  1519. }
  1520. }
  1521. }
  1522. ext4_debug("found bit %d\n", grp_alloc_blk);
  1523. spin_unlock(sb_bgl_lock(sbi, group_no));
  1524. jbd_unlock_bh_state(bitmap_bh);
  1525. #endif
  1526. if (ret_block + num - 1 >= ext4_blocks_count(es)) {
  1527. ext4_error(sb, "ext4_new_block",
  1528. "block(%llu) >= blocks count(%llu) - "
  1529. "block_group = %lu, es == %p ", ret_block,
  1530. ext4_blocks_count(es), group_no, es);
  1531. goto out;
  1532. }
  1533. /*
  1534. * It is up to the caller to add the new buffer to a journal
  1535. * list of some description. We don't know in advance whether
  1536. * the caller wants to use it as metadata or data.
  1537. */
  1538. ext4_debug("allocating block %lu. Goal hits %d of %d.\n",
  1539. ret_block, goal_hits, goal_attempts);
  1540. spin_lock(sb_bgl_lock(sbi, group_no));
  1541. gdp->bg_free_blocks_count =
  1542. cpu_to_le16(le16_to_cpu(gdp->bg_free_blocks_count)-num);
  1543. spin_unlock(sb_bgl_lock(sbi, group_no));
  1544. percpu_counter_sub(&sbi->s_freeblocks_counter, num);
  1545. BUFFER_TRACE(gdp_bh, "journal_dirty_metadata for group descriptor");
  1546. err = ext4_journal_dirty_metadata(handle, gdp_bh);
  1547. if (!fatal)
  1548. fatal = err;
  1549. sb->s_dirt = 1;
  1550. if (fatal)
  1551. goto out;
  1552. *errp = 0;
  1553. brelse(bitmap_bh);
  1554. DQUOT_FREE_BLOCK(inode, *count-num);
  1555. *count = num;
  1556. return ret_block;
  1557. io_error:
  1558. *errp = -EIO;
  1559. out:
  1560. if (fatal) {
  1561. *errp = fatal;
  1562. ext4_std_error(sb, fatal);
  1563. }
  1564. /*
  1565. * Undo the block allocation
  1566. */
  1567. if (!performed_allocation)
  1568. DQUOT_FREE_BLOCK(inode, *count);
  1569. brelse(bitmap_bh);
  1570. return 0;
  1571. }
  1572. ext4_fsblk_t ext4_new_block(handle_t *handle, struct inode *inode,
  1573. ext4_fsblk_t goal, int *errp)
  1574. {
  1575. unsigned long count = 1;
  1576. return ext4_new_blocks(handle, inode, goal, &count, errp);
  1577. }
  1578. /**
  1579. * ext4_count_free_blocks() -- count filesystem free blocks
  1580. * @sb: superblock
  1581. *
  1582. * Adds up the number of free blocks from each block group.
  1583. */
  1584. ext4_fsblk_t ext4_count_free_blocks(struct super_block *sb)
  1585. {
  1586. ext4_fsblk_t desc_count;
  1587. struct ext4_group_desc *gdp;
  1588. int i;
  1589. unsigned long ngroups = EXT4_SB(sb)->s_groups_count;
  1590. #ifdef EXT4FS_DEBUG
  1591. struct ext4_super_block *es;
  1592. ext4_fsblk_t bitmap_count;
  1593. unsigned long x;
  1594. struct buffer_head *bitmap_bh = NULL;
  1595. es = EXT4_SB(sb)->s_es;
  1596. desc_count = 0;
  1597. bitmap_count = 0;
  1598. gdp = NULL;
  1599. smp_rmb();
  1600. for (i = 0; i < ngroups; i++) {
  1601. gdp = ext4_get_group_desc(sb, i, NULL);
  1602. if (!gdp)
  1603. continue;
  1604. desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
  1605. brelse(bitmap_bh);
  1606. bitmap_bh = read_block_bitmap(sb, i);
  1607. if (bitmap_bh == NULL)
  1608. continue;
  1609. x = ext4_count_free(bitmap_bh, sb->s_blocksize);
  1610. printk("group %d: stored = %d, counted = %lu\n",
  1611. i, le16_to_cpu(gdp->bg_free_blocks_count), x);
  1612. bitmap_count += x;
  1613. }
  1614. brelse(bitmap_bh);
  1615. printk("ext4_count_free_blocks: stored = %llu"
  1616. ", computed = %llu, %llu\n",
  1617. EXT4_FREE_BLOCKS_COUNT(es),
  1618. desc_count, bitmap_count);
  1619. return bitmap_count;
  1620. #else
  1621. desc_count = 0;
  1622. smp_rmb();
  1623. for (i = 0; i < ngroups; i++) {
  1624. gdp = ext4_get_group_desc(sb, i, NULL);
  1625. if (!gdp)
  1626. continue;
  1627. desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
  1628. }
  1629. return desc_count;
  1630. #endif
  1631. }
  1632. static inline int test_root(int a, int b)
  1633. {
  1634. int num = b;
  1635. while (a > num)
  1636. num *= b;
  1637. return num == a;
  1638. }
  1639. static int ext4_group_sparse(int group)
  1640. {
  1641. if (group <= 1)
  1642. return 1;
  1643. if (!(group & 1))
  1644. return 0;
  1645. return (test_root(group, 7) || test_root(group, 5) ||
  1646. test_root(group, 3));
  1647. }
  1648. /**
  1649. * ext4_bg_has_super - number of blocks used by the superblock in group
  1650. * @sb: superblock for filesystem
  1651. * @group: group number to check
  1652. *
  1653. * Return the number of blocks used by the superblock (primary or backup)
  1654. * in this group. Currently this will be only 0 or 1.
  1655. */
  1656. int ext4_bg_has_super(struct super_block *sb, int group)
  1657. {
  1658. if (EXT4_HAS_RO_COMPAT_FEATURE(sb,
  1659. EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER) &&
  1660. !ext4_group_sparse(group))
  1661. return 0;
  1662. return 1;
  1663. }
  1664. static unsigned long ext4_bg_num_gdb_meta(struct super_block *sb, int group)
  1665. {
  1666. unsigned long metagroup = group / EXT4_DESC_PER_BLOCK(sb);
  1667. unsigned long first = metagroup * EXT4_DESC_PER_BLOCK(sb);
  1668. unsigned long last = first + EXT4_DESC_PER_BLOCK(sb) - 1;
  1669. if (group == first || group == first + 1 || group == last)
  1670. return 1;
  1671. return 0;
  1672. }
  1673. static unsigned long ext4_bg_num_gdb_nometa(struct super_block *sb, int group)
  1674. {
  1675. if (EXT4_HAS_RO_COMPAT_FEATURE(sb,
  1676. EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER) &&
  1677. !ext4_group_sparse(group))
  1678. return 0;
  1679. return EXT4_SB(sb)->s_gdb_count;
  1680. }
  1681. /**
  1682. * ext4_bg_num_gdb - number of blocks used by the group table in group
  1683. * @sb: superblock for filesystem
  1684. * @group: group number to check
  1685. *
  1686. * Return the number of blocks used by the group descriptor table
  1687. * (primary or backup) in this group. In the future there may be a
  1688. * different number of descriptor blocks in each group.
  1689. */
  1690. unsigned long ext4_bg_num_gdb(struct super_block *sb, int group)
  1691. {
  1692. unsigned long first_meta_bg =
  1693. le32_to_cpu(EXT4_SB(sb)->s_es->s_first_meta_bg);
  1694. unsigned long metagroup = group / EXT4_DESC_PER_BLOCK(sb);
  1695. if (!EXT4_HAS_INCOMPAT_FEATURE(sb,EXT4_FEATURE_INCOMPAT_META_BG) ||
  1696. metagroup < first_meta_bg)
  1697. return ext4_bg_num_gdb_nometa(sb,group);
  1698. return ext4_bg_num_gdb_meta(sb,group);
  1699. }