balloc.c 54 KB

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